August  2019, 13(4): 805-826. doi: 10.3934/ipi.2019037

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

Received  June 2018 Revised  February 2019 Published  May 2019

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.

Citation: Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037
References:
[1]

A. AdamR. 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. Google Scholar

[2]

G. AubertM. BarlaudO. 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. Google Scholar

[3]

M. Beckmann, A continuous model of transportation, Econometrica, 20 (1952), 643-660. doi: 10.2307/1907646. Google Scholar

[4]

E. BrownT. 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. Google Scholar

[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. Google Scholar

[6]

V. CasellesR. Kimmel and G. Sapiro, Geodesic active contours, Int. J. Comput. Vision., 22 (1997), 61-79. doi: 10.1109/ICCV.1995.466871. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[10]

T. ChanB. 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. Google Scholar

[11]

T. ChanS. 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. Google Scholar

[12]

D. CremersM. 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. Google Scholar

[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. Google Scholar

[14]

A. DubrovinaG. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[17]

N. HouhouX. BressonA. SzlamT. 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. Google Scholar

[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.Google Scholar

[19]

M. JungG. 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. Google Scholar

[20]

M. KassA. Witkin and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vision., 1 (1988), 321-331. doi: 10.1007/BF00133570. Google Scholar

[21]

J. KimJ. W. FisherA. YezziM. 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. Google Scholar

[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.Google Scholar

[23]

J. LellmannD. A. LorenzC. Schonlieb and T. Valkonen, Imaging with Kantorovich–Rubinstein discrepancy, SIAM J. Imaging. Sci., 7 (2014), 2833-2859. doi: 10.1137/140975528. Google Scholar

[24]

C. LiX. WangS. EberlM. Fulham and D. Feng, Robust model for segmenting images with/without intensity inhomogeneities, IEEE Trans. Image. Process., 22 (2013), 3296-3309. Google Scholar

[25]

W. Li, A study of stochastic differential equations and Fokker-Planck equations with applications, PhD thesis, 2016.Google Scholar

[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.Google Scholar

[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.Google Scholar

[28]

R. MalladiJ. 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. Google Scholar

[29]

O. MichaelovichY. 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. Google Scholar

[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. Google Scholar

[31]

K. NiX. BressonT. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[34]

O. Pele and M. Werman, Fast and robust earth mover distances, In IEEE International Conference on Computer Vision (ICCV9), 2009,460–467.Google Scholar

[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. Google Scholar

[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. Google Scholar

[37]

R. Ronfard, Region-based strategies for active contour models, Int. J. Comput. Vision., 13 (1994), 229-251. doi: 10.1007/BF01427153. Google Scholar

[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. Google Scholar

[39]

L. RudinS. 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. Google Scholar

[40]

Y. RubnerC. Tomasi and L. Guibas, The earth mover's distance as a metric for image retrieval, Int. J. Comput. Vision., 40 (2000), 99-121. Google Scholar

[41]

E. RyuW. LiP. 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. Google Scholar

[42]

C. SagivN. A. Sochen and Y. Y. Zeevi, Integrated active contours for texture segmentation, IEEE Trans. Image Process, 15 (2006), 1633-1646. Google Scholar

[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.Google Scholar

[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.Google Scholar

[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. Google Scholar

[46]

É. Villani, Topics in Optimal Transportation, Number 58. American Mathematical Soc, 2003. doi: 10.1007/b12016. Google Scholar

[47]

W. YinS. OsherD. 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. Google Scholar

[48]

M. ZhangL. ZhangK. 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. Google Scholar

[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. Google Scholar

show all references

References:
[1]

A. AdamR. 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. Google Scholar

[2]

G. AubertM. BarlaudO. 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. Google Scholar

[3]

M. Beckmann, A continuous model of transportation, Econometrica, 20 (1952), 643-660. doi: 10.2307/1907646. Google Scholar

[4]

E. BrownT. 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. Google Scholar

[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. Google Scholar

[6]

V. CasellesR. Kimmel and G. Sapiro, Geodesic active contours, Int. J. Comput. Vision., 22 (1997), 61-79. doi: 10.1109/ICCV.1995.466871. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[10]

T. ChanB. 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. Google Scholar

[11]

T. ChanS. 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. Google Scholar

[12]

D. CremersM. 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. Google Scholar

[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. Google Scholar

[14]

A. DubrovinaG. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[17]

N. HouhouX. BressonA. SzlamT. 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. Google Scholar

[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.Google Scholar

[19]

M. JungG. 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. Google Scholar

[20]

M. KassA. Witkin and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vision., 1 (1988), 321-331. doi: 10.1007/BF00133570. Google Scholar

[21]

J. KimJ. W. FisherA. YezziM. 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. Google Scholar

[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.Google Scholar

[23]

J. LellmannD. A. LorenzC. Schonlieb and T. Valkonen, Imaging with Kantorovich–Rubinstein discrepancy, SIAM J. Imaging. Sci., 7 (2014), 2833-2859. doi: 10.1137/140975528. Google Scholar

[24]

C. LiX. WangS. EberlM. Fulham and D. Feng, Robust model for segmenting images with/without intensity inhomogeneities, IEEE Trans. Image. Process., 22 (2013), 3296-3309. Google Scholar

[25]

W. Li, A study of stochastic differential equations and Fokker-Planck equations with applications, PhD thesis, 2016.Google Scholar

[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.Google Scholar

[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.Google Scholar

[28]

R. MalladiJ. 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. Google Scholar

[29]

O. MichaelovichY. 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. Google Scholar

[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. Google Scholar

[31]

K. NiX. BressonT. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[34]

O. Pele and M. Werman, Fast and robust earth mover distances, In IEEE International Conference on Computer Vision (ICCV9), 2009,460–467.Google Scholar

[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. Google Scholar

[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. Google Scholar

[37]

R. Ronfard, Region-based strategies for active contour models, Int. J. Comput. Vision., 13 (1994), 229-251. doi: 10.1007/BF01427153. Google Scholar

[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. Google Scholar

[39]

L. RudinS. 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. Google Scholar

[40]

Y. RubnerC. Tomasi and L. Guibas, The earth mover's distance as a metric for image retrieval, Int. J. Comput. Vision., 40 (2000), 99-121. Google Scholar

[41]

E. RyuW. LiP. 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. Google Scholar

[42]

C. SagivN. A. Sochen and Y. Y. Zeevi, Integrated active contours for texture segmentation, IEEE Trans. Image Process, 15 (2006), 1633-1646. Google Scholar

[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.Google Scholar

[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.Google Scholar

[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. Google Scholar

[46]

É. Villani, Topics in Optimal Transportation, Number 58. American Mathematical Soc, 2003. doi: 10.1007/b12016. Google Scholar

[47]

W. YinS. OsherD. 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. Google Scholar

[48]

M. ZhangL. ZhangK. 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. Google Scholar

[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. Google Scholar

Figure 1.  Overall framework of the proposed method
Figure 2.  The corresponding features map obtained from the test image. (a) shows the intensity features map. (b) is the texture features map
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
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
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
Figure 6.  Some segmentation examples of $ 3D $ histogram (RGB) features
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
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
Figure 9.  Unsupervised model with $ 2D $ features (the gray-intensity and the texture)
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
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
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
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
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
Figure 15.  The average Jaccard index values of the LHBS model, the NLAC model, and our method, respectively
Figure 16.  The average Hausdorff distances of the LHBS model, the NLAC model, and our method, respectively
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
Error rate $ 5\% $ $ 10\% $ $ 15\% $ $ 20\% $ $ 25\% $ $ 30\% $
JI value 0.9273 0.8856 0.8365 0.7754 0.7146 0.6543
[1]

Abbas Moameni. Invariance properties of the Monge-Kantorovich mass transport problem. Discrete & Continuous Dynamical Systems - A, 2016, 36 (5) : 2653-2671. doi: 10.3934/dcds.2016.36.2653

[2]

Jesus Garcia Azorero, Juan J. Manfredi, I. Peral, Julio D. Rossi. Limits for Monge-Kantorovich mass transport problems. Communications on Pure & Applied Analysis, 2008, 7 (4) : 853-865. doi: 10.3934/cpaa.2008.7.853

[3]

Zuo Quan Xu, Jia-An Yan. A note on the Monge-Kantorovich problem in the plane. Communications on Pure & Applied Analysis, 2015, 14 (2) : 517-525. doi: 10.3934/cpaa.2015.14.517

[4]

Giuseppe Buttazzo, Eugene Stepanov. Transport density in Monge-Kantorovich problems with Dirichlet conditions. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 607-628. doi: 10.3934/dcds.2005.12.607

[5]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[6]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031

[7]

Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030

[8]

Nassif Ghoussoub, Bernard Maurey. Remarks on multi-marginal symmetric Monge-Kantorovich problems. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1465-1480. doi: 10.3934/dcds.2014.34.1465

[9]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723

[10]

Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2019061

[11]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[12]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[13]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[14]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190

[15]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[16]

Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems & Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645

[17]

Gautier Picot. Energy-minimal transfers in the vicinity of the lagrangian point $L_1$. Conference Publications, 2011, 2011 (Special) : 1196-1205. doi: 10.3934/proc.2011.2011.1196

[18]

Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems & Imaging, 2015, 9 (1) : 257-272. doi: 10.3934/ipi.2015.9.257

[19]

Yingying Li, Stanley Osher, Richard Tsai. Heat source identification based on $l_1$ constrained minimization. Inverse Problems & Imaging, 2014, 8 (1) : 199-221. doi: 10.3934/ipi.2014.8.199

[20]

Satoshi Ito, Soon-Yi Wu, Ting-Jang Shiu, Kok Lay Teo. A numerical approach to infinite-dimensional linear programming in $L_1$ spaces. Journal of Industrial & Management Optimization, 2010, 6 (1) : 15-28. doi: 10.3934/jimo.2010.6.15

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (41)
  • HTML views (170)
  • Cited by (0)

Other articles
by authors

[Back to Top]