Abstract
This paper is devoted to the study of the Monge-Kantorovich theory of optimal mass transport, in the special case of one-dimensional and circular distributions. More precisely, we study the Monge-Kantorovich problem between discrete distributions on the unit circle S 1, in the case where the ground distance between two points x and y is defined as h(d(x,y)), where d is the geodesic distance on the circle and h a convex and increasing function. This study complements previous results in the literature, holding only for a ground distance equal to the geodesic distance d. We first prove that computing a Monge-Kantorovich distance between two given sets of pairwise different points boils down to cut the circle at a well chosen point and to compute the same distance on the real line. This result is then used to obtain a dissimilarity measure between 1-D and circular discrete histograms. In a last part, a study is conducted to compare the advantages and drawbacks of transportation distances relying on convex or concave cost functions, and of the classical L 1 distance. Simple retrieval experiments based on the hue component of color images are shown to illustrate the interest of circular distances. The framework is eventually applied to the problem of color transfer between images.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ambrosio, L., Caffarelli, L.A., Brenier, Y., Buttazzo, G., Villani, C.: Optimal Transportation and Applications. Lecture Notes in Mathematics, vol. 1813. Springer, Berlin (2003)
Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. SIAM, Philadelphia (2009)
Belongie, S., Malik, J., Puzicha, J.: Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Anal. Mach. Intell. 24(4), 509–522 (2002)
Cabrelli, C.A., Molter, U.M.: The Kantorovich metric for probability measures on the circle. J. Comput. Appl. Math. 57(3), 345–361 (1995)
Cabrelli, C.A., Molter, U.M.: A linear time algorithm for a matching problem on the circle. Inf. Process. Lett. 66(3), 161–164 (1998)
Cha, S.-H., Srihari, S.N.: On measuring the distance between histograms. Pattern Recognit. 35(6), 1355–1370 (2002)
Cullen, M.J.P.: A Mathematical Theory of Large-Scale Atmospheric-Ocean Flow. Imperial College Press, London (2006)
Delon, J., Salomon, J., Sobolevskii, A.: Fast transport optimization for Monge costs on the circle. SIAM J. Appl. Math. 70(7), 2239–2258 (2010)
Dvir, G.: Context-based image modelling. In: Proceedings of the 2002 IEEE International Conference on Pattern Recognition (ICPR), vol. 4, p. 40162. IEEE Comput. Soc., Los Alamitos (2002)
Frisch, U., Matarrese, S., Mohayaee, R., Sobolevski, A.: A reconstruction of the initial conditions of the universe by optimal mass transportation. Nature (2002)
Grauman, K., Darrell, T.J.: Fast contour matching using approximate earth mover’s distance. In: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’04), pp. 220–227 (2004)
Greenspan, H., Dvir, G., Rubner, Y.: Region correspondence for image matching via emd flow. In: CBAIVL ’00: Proceedings of the IEEE Workshop on Content-Based Access of Image and Video Libraries (CBAIVL’00), p. 27. IEEE Computer Society, Washington, DC (2000)
Gangbo, W., McCann, R.J.: The geometry of optimal transportation. Acta Math. 177(2), 113–161 (1996)
Gurwitz, C.: Weighted median algorithms for L1 approximation. BIT Numer. Math. 30(2), 301–310 (1990)
Hurtut, T., Gousseau, Y., Schmitt, F.: Adaptive image retrieval based on the spatial organization of colors. Comput. Vis. Image Underst. 112(2), 101–113 (2008)
Haker, S., Zhu, L., Tannenbaum, A., Angenent, S.: Optimal mass transport for registration and warping. Int. J. Comput. Vis. 60(3), 225–240 (2004)
Indyk, P., Thaper, N.: Fast image retrieval via embeddings. In: 3rd International Workshop on Statistical and Computational Theories of Vision, Nice, France (2003)
Jalba, A.C., Wilkinson, M.H.F., Roerdink, J.B.T.M.: Shape representation and recognition through morphological curvature scale spaces. IEEE Trans. Image Process. 15(2), 331–341 (2006)
Kantorovich, L.: On the transfer of masses. Dokl. Akad. Nauk 37(2), 227–229 (1942) (in Russian)
Lv, Q., Charikar, M., Li, K.: Image similarity search with compact data structures. In: CIKM ’04: Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management, pp. 208–217. ACM, New York (2004)
Ling, H., Okada, K.: An efficient Earth Mover’s distance algorithm for robust histogram comparison. IEEE Trans. Pattern Anal. Mach. Intell. 29(5), 840–853 (2007)
Lowe, D.G.: Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vis. 60(2), 91–110 (2004)
Liu, Y., Zhang, D., Lu, G., Ma, W.-Y.: Region-based image retrieval with high-level semantic color names. In: MMM ’05: Proceedings of the 11th International Multimedia Modelling Conference, Washington, DC, USA, pp. 180–187. IEEE Comput. Soc., Los Alamitos (2005)
McCann, R.J.: Existence and uniqueness of monotone measure-preserving maps. Duke Math. J. 80(2), 309–323 (1995)
McCann, R.J.: Exact solutions to the transportation problem on the line. In: Proceedings: Mathematical, Physical and Engineering Sciences, pp. 1341–1380 (1999)
Mokhtarian, F.: Silhouette-based occluded object recognition through curvature scale space. Mach. Vis. Appl. 10(3), 87–97 (1997)
Monge, G.: Mémoire sur la théorie des déblais et des remblais. In: Histoire de l’Académie Royale des Sciences (1781)
Morovic, J., Sun, P.L.: Accurate 3d image colour histogram transformation. Pattern Recognit. Lett. 24(11), 1725–1735 (2003)
Orlin, J.: A faster strongly polynomial minimum cost flow algorithm. In: STOC (1988)
Pele, O.: Source code for EMD. http://www.cs.huji.ac.il/~ofirpele/FastEMD/code/
Pele, O.: Source code for MK T2: http://www.cs.huji.ac.il/~ofirpele/SiftDist/code/
Pitié, F., Kokaram, A., Dahyot, R.: Automated colour grading using colour distribution transfer. Comput. Vision Image Underst., February 2007
Pele, O., Werman, M.: A linear time histogram metric for improved sift matching. In: ECCV08 (2008)
Pele, O., Werman, M.: Fast and robust earth mover’s distances. In: ICCV (2009)
Rabin, J., Delon, J., Gousseau, Y.: Circular Earth Mover’s Distance for the comparison of local features. In: Proceedings of the IEEE International Conference on Pattern Recognition (ICPR). IEEE Computer Society, Los Alamitos (2008)
Rabin, J., Delon, J., Gousseau, Y.: A statistical approach to the matching of local features. SIAM J. Imaging Sci. (2009)
Rabin, J., Delon, J., Gousseau, Y.: Regularization of transportation maps for color and contrast transfer. In: Proceedings of the IEEE International Conference on Image Processing (ICIP). IEEE Computer Society, Los Alamitos (2010)
Rabin, J., Peyré, G., Cohen, L.D.: Geodesic shape retrieval via optimal mass transport. In: Proceedings of the European Conference on Computer Vision (ECCV’10) (2010)
Ruzon, M.A., Tomasi, C.: Edge, junction, and corner detection using color distributions. IEEE Trans. Pattern Anal. Mach. Intell. 23(11), 1281–1295 (2001)
Rubner, Y., Tomasi, C., Guibas, L.J.: The Earth Mover’s distance as a metric for image retrieval. Int. J. Comput. Vis. 40(2), 99–121 (2000)
Rubner, Y.: Source code for EMD. http://robotics.stanford.edu/~rubner/
Shirdhonkar, S., Jacobs, D.W.: Approximate earth mover’s distance in linear time. In: CVPR08, pp. 1–8 (2008)
Shen, H.C., Wong, A.K.C.: Generalized texture representation and metric. Comput. Vis. Graph. Image Process. 23(2), 187–206 (1983)
Villani, C.: Topics in Optimal Transportation. Am. Math. Soc., Providence (2003)
Villani, C.: Optimal Transport: Old and New. Springer, Berlin (2008)
Werman, M., Peleg, S., Melter, R., Kong, T.Y.: Bipartite graph matching for points on a line or a circle. J. Algorithms 7(2), 277–284 (1986)
Werman, M., Peleg, S., Rosenfeld, A.: A distance metric for multidimensional histograms. Comput. Vis. Graph. Image Process. 32(3), 328–336 (1985)
Zheng, Q.-F., Wang, W.-Q., Gao, W.: Effective and efficient object-based image retrieval using visual phrases. In: MULTIMEDIA ’06: Proceedings of the 14th Annual ACM International Conference on Multimedia, pp. 77–80. ACM, New York (2006)
Zhu, L., Yang, Y., Haker, S., Tannenbaum, A.: An image morphing technique based on optimal mass preserving mapping. IEEE Trans. Image Process. 16(6), 1481–1495 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work has been supported by the French National Research Agency (project OTARIE) under grant BLAN07-2_183172.
Rights and permissions
About this article
Cite this article
Rabin, J., Delon, J. & Gousseau, Y. Transportation Distances on the Circle. J Math Imaging Vis 41, 147–167 (2011). https://doi.org/10.1007/s10851-011-0284-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-011-0284-0