最优传输理论在图像处理中的应用

doi:10.15960/j.cnki.issn.1007-6093.2019.03.008

摘要/Abstract

摘要： 最优传输问题是寻找概率测度间的最优传输变换的一类特殊的优化问题，近年来在众多领域得到了广泛的关注.针对传统最优传输问题存在的计算量过大、正则性缺失等问题，学者们提出了多种改进的最优传输模型和算法，用于处理实际中的各种问题.简述最优传输问题的基本理论和方法，介绍Wasserstein距离的概念及其衍生出的Wasserstein重心，探讨离散化最优传输模型及其在正则化等方面的改进，讨论求解最优传输问题的算法进展，综述Wasserstein距离在图像处理领域的简单应用，并展望有待进一步研究的工作.

关键词: 最优传输, 图像处理, 正则化, Wasserstein距离

Abstract: The optimal transport problem which has attracted wide attentions in many fields in recent years, is a special kind of optimization problem discussed in the probabilistic measure space. In order to overcome the disadvantages of traditional optimal transport models, such as complex computation and lack of regularity, many different kinds of improved optimal transport models and algorithms are proposed to deal with various practical problems. Firstly, this paper briefly describes the basic theory and methods of optimal transport, and further introduces the concept of Wasserstein distance and Wasserstein barycenters. And then, the discrete optimal transport model and the improved regularization models are discussed. Besides, a short summary of the algorithms to solve optimal transport problem is given. Then, from Wasserstein distance aspect, a review of applications in several areas of image processing is briefly discussed. At last, the further research work is prospected.

Key words: optimal transport, image processing, regularization, Wasserstein distance

中图分类号:

O29
O224

马丽涛, 边伟. 最优传输理论在图像处理中的应用[J]. 运筹学学报, 2019, 23(3): 109-125.

MA Litao, BIAN Wei. A review of optimal transport in image processing[J]. Operations Research Transactions, 2019, 23(3): 109-125.

参考文献

[1] Arjovsky M, Chintala S, Botou L. Wasserstein GAN[J]. arXiv:1701.07875v3, 2017, 1-26.
[2] Rubner Y, Tomasi C, Guibas L J. The earth mover's distance as ametric for image retrieval[J]. International Journal ofComputer Vision, 2000, 40(2):99-121.
[3] Villani C. Optimal Transport:Old and New[M]. Berlin:Springer-Verlag, 2008.
[4] Santamorogio F. Optimal Transport for Applied Mathematics[M].Birkäuser, Cham, 2015.
[5] Monge G. Mémoire sur la Théorie des Déblais et des Remblais[M]. Paris:De ĺImprimerie Royale, 1781.
[6] Kantorovich L. On translation of mass(in Russian)[J]. Dokl. ANSSSR, 1942, 37:199-201.
[7] Kolouri S, Park S R, Thorpe M, et al. Optimal mass transport:Signalprocessing and machine-learning applications[J]. IEEE SignalProcessing Magazine, 2017, 34(4):43-59.
[8] Brenier Y. Polar factorization and monotone rearrangement of vector-valued functions[J].Communications on Pure and Applied Mathematics, 1991, 44(4):375-417.
[9] Gangbo W, McCann R J. The geometry of optimal transportation[J].Acta Mathematica, 1996, 177(2):113-161.
[10] Agueh M, Carlier G. Barycenters in the Wasserstein space[J]. SIAM Journal on Mathematical Analysis, 2011, 43(2):904-924.
[11] Ferradans S, Papadakis N, Rabin J, et al. Regularized discreteoptimal transport[J]. SIAM Journal on Imaging Sciences, 2013,7(3):428-439.
[12] Kuhn H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics Quarterly, 1955, 2(1-2):83-97.
[13] Bertsekas D P. The auction algorithm:A distributed relaxationmethod for the assignment problem[J]. Annals of OperationsResearch, 1988, 14(1):105-123.
[14] Rabin J, Ferradans S, Papadakis N. Adaptive color transfer withrelaxed optimal transport[C]//IEEE international Conferenceon Image Processing, Paris, France, Oct 2014, 4852-4856.
[15] Louet J, Santambrogio F. A sharp inequality for transport maps in W^1,p(R) via approximation[J]. AppliedMathematics Letters, 2012, 25(3):648-653.
[16] Papadakis N. Optimal Transport for Image Processing[M].Signal and Image Processing, Université de Bordeaux, 2015.
[17] Gilboa G, Osher S. Nonlocal linear image regularization andsupervised segmentation[J]. SIAM Multiscale Modeling andSimulation, 2007, 6(2):595-630.
[18] Cuturi M. Sinkhorn distances:Lightspeed computation of optimaltransport[C]//Advances in Neural Information ProcessingSystems, 2013, 2292-2300.
[19] Knight P. The sinkhorn-knopp algorithm:Convergence and applications[J]. SIAM Journal on Matrix Analysis and Applications, 2008,30(1):261-275.
[20] Courty N, Flamary R, Tuia D. Domain adaptation with regularizedoptimal transport[C]//Joint European Conference on MachineLearning and Knowledge Discovery in Databases.Springer, Berlin, Heidelberg, 2014:274-289.
[21] Courty N, Flamary R, Tuia D, et al. Optimal transport for domainadaptation[J]. IEEE Transactions on Pattern Analysis andMachine Intelligence, 2017, 39(9):1853-1865.
[22] Nesterov Y E, Nemirovsky A S. Interior Point Polynomial Methodsin Convex Programming:Theory and Algorithms[M].SIAM Publishing, 1993.
[23] 袁亚湘, 孙文瑜. 最优化理论与方法[M].北京:科学出版社, 1997.
[24] Ahuja R K, Magnanti T, Orlin J. Network Flows:Theory,Algorithms, and Applications[M]. Prentice Hall, Upper SaddleRiver, 1993.
[25] Zaslavskiy M, Bach F, Vert J P. A path following algorithm for thegraph matching problem[J]. IEEE Transactions on PatternAnalysis and Machine Intelligence, 2009, 31(12):2227-2242.
[26] Shirdhonkar S, Jacobs D W. Approximate earth mover's distance inlinear time[C]//2008 IEEE Conference on Computer Vision andPattern Recognition, IEEE, 2008, 1-8.
[27] Rabin J, Peyré G, Delon J, et al. Wasserstein barycenter and itsapplication to texture mixing[C]//International Conference onScale Space and Variational Methods in Computer Vision,Berlin:Springer, 2011, 435-446.
[28] Sinkhorn R. Diagonal equivalence to matrices with prescribed row andcolumn sums[J]. The American Mathematical Monthly, 1967,74(4):402-405.
[29] Solomon J, De Goes F, Peyré G, et al.Convolutional wasserstein distances:Efficient optimal transportation on geometric domains[J].ACM Transactions on Graphics, 2015, 34(4):66:1-66:11
[30] Zhao Q, Yang Z, Tao H. Differential earth mover's distance with itsapplications to visual tracking[J]. IEEE Transactions onPattern Analysis and Machine Intelligence, 2010, 32(2):274-287.
[31] Rubner Y, Tomasi C, Guibas L J. A metric for distributions withapplications to image databases[C]//Sixth InternationalConference on Computer Vision (IEEE Cat. No. 98CH36271), IEEE, 1998, 59-66.
[32] Ling H, Okada K. An efficient earth mover's distance algorithm forrobust histogram comparison[J]. IEEE Transactions on PatternAnalysis and Machine Intelligence, 2007, 29(5):840-853.
[33] Pele O, Werman M. Fast and robust earth mover's distances[C]//2009 IEEE 12th International Conference on Computer Vision, IEEE,2009, 460-467.
[34] Tahri O, Usman M, Demonceaux C, et al. Fast earth mover's distancecomputation for catadioptric image sequences[C]//2016 IEEEInternational Conference on Image Processing (ICIP), IEEE, 2016,2485-2489.
[35] Thibault A, Chizat L, Dossal C, et al. Overrelaxed sinkhorn-knoppalgorithm for regularized optimal transport[J]. arXiv preprintarXiv:1711.01851, 2017, 1-10.
[36] Dvurechensky P, Gasnikov A, Kroshnin A. Computational optimaltransport:Complexity by accelerated gradient descent is better thanby Sinkhorn's algorithm[J]. arXiv preprint arXiv:1802.04367, 2018, 1-25.
[37] Haker S, Zhu L, Tannenbaum A, et al.Optimal mass transport for registration and warping[J].International Journal of Computer Vision, 2004, 60(3):225-240.
[38] Angenent S, Haker S, Tannenbaum A. Minimizing flows for theMonge-Kantorovich problem[J]. SIAM Journal on MathematicalAnalysis, 2003, 35(1):61-97.
[39] Benamou J D, Froese B D, Oberman A M.Numerical solution of the optimal transportation problem using the Monge-Ampére equation[J].Journal of Computational Physics, 2014, 260:107-126.
[40] Gu X,Luo F,Sun J, et al. Variational principles for Minkowski typeproblems, discrete optimal transport and discrete Monge-Ampereequations[J]. Asian Journal of Mathematics, 2016, 20(2):383-398.
[41] Su Z, Sun J, Gu X, et al. Optimal mass transport for geometricmodeling based on variational principles in convex geometry[J].Engineering with Computers, 2014, 30(4):475-486.
[42] Liu J, Froese B D, Oberman A M, et al. A multigrid scheme for 3DMonge-Ampére equations[J]. International Journal ofComputer Mathematics, 2017, 94(9):1850-1866.
[43] Bing S, Gang H. Order-preserving optimal transport for distancesbetween sequences[J]. IEEE Transactions on Pattern Analysisand Machine Intelligence, 2018:1-14. DOI:10.1109/tpami.2018.2870154.
[44] Li P, Wang Q, Zhang L. A novel earth mover's distance methodologyfor image matching with gaussian mixture models[C]//Proceedings of the IEEE International Conference on ComputerVision, 2013, 1689-1696.
[45] Bonneel N, Peyré G, Cuturi M. Wasserstein barycentriccoordinates:histogram regression using optimal transport[J]. ACM Transactions on Graphics, 2016, 35(4):71:1-71:10.
[46] Pitie F, Kokaram A C, Dahyot R. N-dimensional probability densityfunction transfer and its application to color transfer[C]//Tenth IEEE International Conference on Computer Vision (ICCV'05),IEEE, 2005, Volume 1.2:1434-1439.
[47] Bonneel N, Rabin J, Peyré G, et al. Sliced and radon wassersteinbarycenters of measures[J]. Journal of Mathematical Imagingand Vision, 2015, 51(1):22-45.
[48] Rehman T ur, Haber E, Pryor G, et al. 3D nonrigid registration viaoptimal mass transport on the GPU[J]. Medical Image Analysis,2009, 13(6):931-940.
[49] Museyko O, Stiglmayr M, Klamroth K, et al. On the application of theMonge-Kantorovich problem to image registration[J]. SIAMJournal on Imaging Sciences, 2009, 2(4):1068-1097.
[50] Papież B W, Brady M, Schnabel J A. Mass transportation fordeformable image registration with application to Lung CT. Molecular Imaging, Reconstruction and Analysis of Moving BodyOrgans, and Stroke Imaging and Treatment, Springer, Cham, 2017, 66-74.
[51] Xu D, Yan S, Luo J. Face recognition using spatially constrainedearth mover's distance[J]. IEEE Transactions on ImageProcessing, 2008, 17(11):2256-2260.
[52] Schmitz M A, Heitz M, Bonneel N, et al. Wasserstein dictionarylearning:Optimal transport-based unsupervised nonlinear dictionarylearning[J]. SIAM Journal on Imaging Sciences, 2018,11(1):643-678.
[53] Wang F, Guibas L J. Supervised earth mover's distance learning andits computer vision applications[C]//European Conference onComputer Vision, Berlin:Springer, 2012, 442-455.
[54] Peyré G, Fadili J, Rabin J. Wasserstein active contours[C]//201219th IEEE International Conference on Image Processing,IEEE, 2012, 2541-2544.
[55] Mendoza C, Pérez-Carrasco J A, Sáez A, et al. Linearizedmultidimensional earth-mover's-distance gradient flows[J]. IEEE Transactions on Image Processing, 2013, 22(12):5322-5335.
[56] Papadakis N, Rabin J.Convex histogram-based joint image segmentation with regularized optimal transport cost[J].Journal of Mathematical Imaging and Vision, 2017, 59(2):161-186.
[57] Rabin J, Papadakis N. Convex color image segmentation with optimaltransport distances[C]//International Conference on ScaleSpace and Variational Methods in Computer Vision, Springer, Cham,2015, 256-269.
[58] Ni K, Bresson X, Chan T F, et al. Local histogram based segmentationusing the wasserstein distance[J]. International Journal ofComputer Vision, 2009, 84(1):97-111.
[59] Swoboda P, Schnörr C. Variational image segmentation andcosegmentation with the wasserstein distance. InternationalWorkshop on Energy Minimization Methods in Computer Vision andPattern Recognition, Berlin:Springer, 2013, 321-334.
[60] Yildizoglu R, Aujol J F, Papadakis N. A convex formulation forglobal histogram based binary segmentation[C]//InternationalConference on Energy Minimization Methods in Computer Vision andPattern Recognition, 2013, 335-349.
[61] Cuturi M, Peyré G. A smoothed dual approach for variationalWasserstein problems[J]. SIAM Journal on Imaging Sciences,2016, 9(1):320-343.