Image segmentation via $ L_1 $ Monge-Kantorovich problem

Yupeng Li; Wuchen Li; Guo Cao

doi:10.3934/ipi.2019037

Article Contents

2019, Volume 13, Issue 4: 805-826. Doi: 10.3934/ipi.2019037

This issue Previous Article Compound truncated Poisson normal distribution: Mathematical properties and Moment estimation Next Article Nash strategies for the inverse inclusion Cauchy-Stokes problem

Image segmentation via $ L_1 $ Monge-Kantorovich problem

1.
School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, 210094, China
2.
Department of Mathematics, University of California, Los Angeles, California, 90095, USA

^* Corresponding author: Wuchen Li
^* Corresponding author: Wuchen Li

Received: June 2018

Revised: February 2019

Published: May 2019

Abstract / Introduction Full Text(HTML) Figure(16) / Table(1) Related Papers Cited by

Abstract

This paper provides a fast approach to apply the Earth Mover's Distance (EMD) (a.k.a optimal transport, Wasserstein distance) for supervised and unsupervised image segmentation. The model globally incorporates the transportation costs (original Monge-Kantorovich type) among histograms of multiple dimensional features, e.g. gray intensity and texture in image's foreground and background. The computational complexity is often high for the EMD between two histograms on Euclidean spaces with dimensions larger than one. We overcome this computational difficulty by rewriting the model into a $ L_1 $ type minimization with the linear dimension of feature space. We then apply a fast algorithm based on the primal-dual method. Compare to several state-of-the-art EMD models, the experimental results based on image data sets demonstrate that the proposed method has superior performance in terms of the accuracy and the stability of the image segmentation.

Keywords:

Mathematics Subject Classification: Primary: 68Uxx.

Citation:

Full Text(HTML)

Figure 1. Overall framework of the proposed method

Download: Full-size image PowerPoint slide

Figure 2. The corresponding features map obtained from the test image. (a) shows the intensity features map. (b) is the texture features map

Download: Full-size image PowerPoint slide

Figure 3. Exemplar regions with bounding boxes of the test images. The blue bounding box is the foreground and the red bounding boxes are the background

Download: Full-size image PowerPoint slide

Figure 4. Dynamical segmentation map. (a) shows the original image with bounding boxes. (b) is the corresponding $ 2D $ histogram contour of the blue bounding box. (c) is the evolution segmentation process. (d) illustrates the corresponding movement of $ 2D $ contours

Download: Full-size image PowerPoint slide

Figure 5. Supervised model with comparison to LHBS [31] model. Row 1st shows the input images with boundary boxes. Row 2nd shows the LHBS model. Row 3rd shows the proposed method based on $ 2D $ feature histograms

Download: Full-size image PowerPoint slide

Figure 6. Some segmentation examples of $ 3D $ histogram (RGB) features

Download: Full-size image PowerPoint slide

Figure 7. The left figure shows that how we select the reference measure in each step. It is chosen as the red one, i.e. the delta measure supported at the median point of the blue histogram. The right figure demonstrates that the energy function decreases during these iterative steps

Download: Full-size image PowerPoint slide

Figure 8. The first row shows the unsupervised model with $ 1D $ gray-intensity features, and the second row shows the unsupervised model with $ 1D $ texture features

Download: Full-size image PowerPoint slide

Figure 9. Unsupervised model with $ 2D $ features (the gray-intensity and the texture)

Download: Full-size image PowerPoint slide

Figure 10. Unsupervised model with comparison to the LHBS [31] model. The 1st row shows the original images. The 2nd row shows the segmentation results achieved by the LHBS model. The 3rd row shows the proposed method segmentation results.The 4th row shows the binary results of the LHBS model. The 5th row shows the binary results of proposed method. The 6th row shows the ground truth

Download: Full-size image PowerPoint slide

Figure 11. The segmentation accuracy tested on the Microsoft GrabCut database. The magenta contour, and green contour are the segmentation accuracy of the LHBS[31] model, and our method, respectively

Download: Full-size image PowerPoint slide

Figure 12. Some comparison examples on Berkeley segmentation data set. Top to bottom: test images, results of the NLAC [19] model, the LHBS [31] model, and our method, respectively

Download: Full-size image PowerPoint slide

Figure 13. The Jaccard values of segmentation results on the 50 Berkeley data set images. The magenta contour, the green contour, and the blue contour are the Jaccard values of the proposed method, the LHBS [31] model, and the NLAC [19] model, respectively

Download: Full-size image PowerPoint slide

Figure 14. The Hausdorff distances of segmentation results on the 50 Berkeley data set images. The magenta contour, the green contour, and the blue contour are the Hausdorff distances of the proposed method, the LHBS [31] model, and the NLAC [19] model, respectively

Download: Full-size image PowerPoint slide

Figure 15. The average Jaccard index values of the LHBS model, the NLAC model, and our method, respectively

Download: Full-size image PowerPoint slide

Figure 16. The average Hausdorff distances of the LHBS model, the NLAC model, and our method, respectively

Download: Full-size image PowerPoint slide

Table 1. The JI values with different error rates of the cheetah image in Figure. 4

Error rate	$ 5\% $	$ 10\% $	$ 15\% $	$ 20\% $	$ 25\% $	$ 30\% $
JI value	0.9273	0.8856	0.8365	0.7754	0.7146	0.6543

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Adam, R. Kimmel and E. Rivlin, On scene segmentation and histograms-based curve evolution, IEEE Trans. Pattern. Anal. Mach. Intell., 31 (2009), 1708-1714. doi: 10.1109/TPAMI.2009.21.
[2]	G. Aubert, M. Barlaud, O. Faugeras and S. Jehan-Besson, Image segmentation using active contours: Calculus of variations or shape gradients?, SIAM J. Applied. Math., 63 (2003), 2128-2154. doi: 10.1137/S0036139902408928.
[3]	M. Beckmann, A continuous model of transportation, Econometrica, 20 (1952), 643-660. doi: 10.2307/1907646.
[4]	E. Brown, T. Chan and X. Bresson, Completely convex formulation of the Chan-Vese image segmentation model, Int. J. Comput. Vision., 98 (2012), 103-121. doi: 10.1007/s11263-011-0499-y.
[5]	G. Buttazzo and F. Santambrogio, A model for the optimal planning of an urban area, SIAM J. Math. Anal., 37 (2005), 514-530. doi: 10.1137/S0036141003438313.
[6]	V. Caselles, R. Kimmel and G. Sapiro, Geodesic active contours, Int. J. Comput. Vision., 22 (1997), 61-79. doi: 10.1109/ICCV.1995.466871.
[7]	A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging. Vis., 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.
[8]	A. Chambolle and J. Darbon, On total variation minimization and surface evolution using parametric maximum flows, International Journal of Computer Vision, 84 (2009), 288. doi: 10.1007/s11263-009-0238-9.
[9]	T. F. Chan and L. A. Vese, Active contours without edges, IEEE Trans. Image. Process., 10 (2001), 266-277. doi: 10.1109/83.902291.
[10]	T. Chan, B. Sandberg and L. Vese, Active contours without edges for vector-valued images, J. Vis. Commun. Image. Rep., 11 (2000), 130-141. doi: 10.1006/jvci.1999.0442.
[11]	T. Chan, S. Esedoglu and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM J. Applied. Math., 66 (2006), 1632-1648. doi: 10.1137/040615286.
[12]	D. Cremers, M. Rousson and R. Deriche, A review of statistical approaches to level set segmentation: Integrating color, texture, motion and shape, Int. J. Comput. Vision., 72 (2007), 195-215. doi: 10.1007/s11263-006-8711-1.
[13]	D. Cremers and S. Soatto, Motion competition: A variational approach to piecewise parametric motion segmentation, Int. J. Comput. Vision., 62 (2005), 249-265. doi: 10.1007/s11263-005-4882-4.
[14]	A. Dubrovina, G. Rosman and R. Kimmel, Multi-region active contours with a single level set function, IEEE Trans. Pattern. Anal. Mach. Intell., 37 (2015), 1585-1601. doi: 10.1109/TPAMI.2014.2385708.
[15]	L. Evans and W. Gangbo, Differential equations methods for the Monge-Kantorovich mass transfer problem, Mem. Amer. Math. Soc., 137 (1999), ⅷ+66 pp. doi: 10.1090/memo/0653.
[16]	D. Freedman and T. Zhang, Active Contours for Tracking Distributions, IEEE Trans. Image. Processing., 13 (2004), 518-526. doi: 10.1109/TIP.2003.821445.
[17]	N. Houhou, X. Bresson, A. Szlam, T. F. Chan and J. P. Thiran, Semi-supervised segmentation based on non-local continuous min-cut, Scale Space and Variational Methods in Computer Vision, Lecture Notes in Comput. Sci., 5567 (2009), 112-123. doi: 10.1007/978-3-642-02256-2_10.
[18]	M. Jacobs, F. Lger, W. Li and S. Osher, Solving large-scale optimization problems with a convergence rate independent of grid size, preprint, arXiv: 1805.09453.
[19]	M. Jung, G. Peyre and L. D. Cohen, Texture segmentation via non-local non-parametric active contours, International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, 6819 (2011), 74-88. doi: 10.1007/978-3-642-23094-3_6.
[20]	M. Kass, A. Witkin and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vision., 1 (1988), 321-331. doi: 10.1007/BF00133570.
[21]	J. Kim, J. W. Fisher, A. Yezzi, M. Cetin and A. S. Willsky, A nonparametric statistical method for image segmentation using information theory and curve evolution, IEEE Trans. Image. Process., 14 (2005), 1486-1502. doi: 10.1109/TIP.2005.854442.
[22]	R. Kimmel, S. Osher and N. Paragios, Eds, Fast edge integration, in Geometric Level Set Methods in Imaging, Vision, and Graphics, Springer-Verlag, New York, 2003.
[23]	J. Lellmann, D. A. Lorenz, C. Schonlieb and T. Valkonen, Imaging with Kantorovich–Rubinstein discrepancy, SIAM J. Imaging. Sci., 7 (2014), 2833-2859. doi: 10.1137/140975528.
[24]	C. Li, X. Wang, S. Eberl, M. Fulham and D. Feng, Robust model for segmenting images with/without intensity inhomogeneities, IEEE Trans. Image. Process., 22 (2013), 3296-3309.
[25]	W. Li, A study of stochastic differential equations and Fokker-Planck equations with applications, PhD thesis, 2016.
[26]	W. Li, E. Ryu, S. Osher, W. Yin and W. Gangbo, A Fast algorithm for Earth Mover's Distance based on optimal transport and $L_1$ type Regularization, preprint, arXiv: 1609.07092.
[27]	J. Liu, W. Yin, W. Li and Y.-T. Chow, Multilevel Optimal Transport: A Fast Approximation of Wasserstein-1 Distances, CAM report 18–54, 2018.
[28]	R. Malladi, J. Sethian and B. Vemuri, Shape modeling with front propagation: A level set approach, IEEE Trans. Pattern Anal. Mach. Intell., 17 (1995), 158-175. doi: 10.1109/34.368173.
[29]	O. Michaelovich, Y. Rathi and A. Tannenbaum, Image segmentation using active contours driven by the bhattacharyya gradient flow, IEEE Trans. Image Processing., 16 (2007), 2787-2801. doi: 10.1109/TIP.2007.908073.
[30]	D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685. doi: 10.1002/cpa.3160420503.
[31]	K. Ni, X. Bresson, T. Chan and S. Esedoglu, Local histogram based segmentation using the Wasserstein distance, Int. J. Comput. Vision., 84 (2009), 97-111. doi: 10.1007/s11263-009-0234-0.
[32]	S. Osher and A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulation, J. Comput. Phys., 79 (1988), 12-49. doi: 10.1016/0021-9991(88)90002-2.
[33]	N. Paragios and R. Deriche, Geodesic active regions: A new paradigm to deal with frame partition problems in computer vision, J. Vis. Commun. Image. Rep., 13 (2002), 249-268. doi: 10.1006/jvci.2001.0475.
[34]	O. Pele and M. Werman, Fast and robust earth mover distances, In IEEE International Conference on Computer Vision (ICCV9), 2009,460–467.
[35]	G. Peyre, J. Fadili and J. Rabin, Wasserstein Active Contours, Image Processing (ICIP), 19th IEEE International Conference on. IEEE, 2012. doi: 10.1109/ICIP.2012.6467416.
[36]	J. Rabin and N. Papadakis, Convex color image segmentation with optimal transport distances, Scale Space and Variational Methods in Computer Vision, 256–269, Lecture Notes in Comput. Sci., 9087, Springer, Cham, 2015. doi: 10.1007/978-3-319-18461-6_21.
[37]	R. Ronfard, Region-based strategies for active contour models, Int. J. Comput. Vision., 13 (1994), 229-251. doi: 10.1007/BF01427153.
[38]	C. Rother, T. Minka, A. Blake and V. Kolmogorov, Cosegmentation of image pairs by histogram matching-incorporating a global constraint into MRFs, In IEEE International Conference on Computer Vision and Pattern Recognition(CVPR'06), 2006,993–1000. doi: 10.1109/CVPR.2006.91.
[39]	L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.
[40]	Y. Rubner, C. Tomasi and L. Guibas, The earth mover's distance as a metric for image retrieval, Int. J. Comput. Vision., 40 (2000), 99-121.
[41]	E. Ryu, W. Li, P. Yin and S. Osher, Unbalanced and partial $L_1$ monge kantorovich problem: A scalable parallel first-order method, J. Sci. Comput., 75 (2017), 1596-1613. doi: 10.1007/s10915-017-0600-y.
[42]	C. Sagiv, N. A. Sochen and Y. Y. Zeevi, Integrated active contours for texture segmentation, IEEE Trans. Image Process, 15 (2006), 1633-1646.
[43]	B. Sandberg, T. Chan and L. Vese, A Level-set and Gabor Based Active Contour Algorithm for Segmenting Textured Images, Technical report, UCLA CAM Report 02-39, UCLA, Los Angeles, CA, 2002.
[44]	P. Swoboda and C. Schnorr, Variational Image Segmentation and Cosegmentation with the Wasserstein Distance, International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, Springer Berlin Heidelberg, 2013.
[45]	L. A. Vese and T. F. Chan, A multiphase level set framework for image segmentation using the Mumford and Shah model, Int. J. Comput. Vision., 50 (2002), 271-293.
[46]	É. Villani, Topics in Optimal Transportation, Number 58. American Mathematical Soc, 2003. doi: 10.1007/b12016.
[47]	W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $\ell_1$-minimization with applications to compressed sensing, SIAM J. Imaging. Sci., 1 (2008), 143-168. doi: 10.1137/070703983.
[48]	M. Zhang, L. Zhang, K. M. Lam and D. Zhang, A level Set approach to image segmentation with intensity inhomogeneity, IEEE Trans. Cybern., 46 (2016), 546-557. doi: 10.1109/TCYB.2015.2409119.
[49]	S. Zhu and A. Yuille, Region competition: Unifying snakes, region growing, and Bayes/MDL for multiband image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 18 (1996), 884-900. doi: 10.1109/ICCV.1995.466909.