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.

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

[3]

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

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

[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. CasellesR. 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. 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.

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

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

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

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

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

[20]

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

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

[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. LellmannD. A. LorenzC. Schonlieb and T. Valkonen, Imaging with Kantorovich–Rubinstein discrepancy, SIAM J. Imaging. Sci., 7 (2014), 2833-2859. doi: 10.1137/140975528.

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

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

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

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

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

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

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

[42]

C. SagivN. 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. 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.

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

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

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.

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

[3]

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

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

[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. CasellesR. 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. 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.

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

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

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

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

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

[20]

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

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

[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. LellmannD. A. LorenzC. Schonlieb and T. Valkonen, Imaging with Kantorovich–Rubinstein discrepancy, SIAM J. Imaging. Sci., 7 (2014), 2833-2859. doi: 10.1137/140975528.

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

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

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

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

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

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

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

[42]

C. SagivN. 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. 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.

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

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

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]

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

[11]

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

[12]

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

[13]

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

[14]

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

[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

2017 Impact Factor: 1.465

Metrics

  • PDF downloads (25)
  • HTML views (78)
  • Cited by (0)

Other articles
by authors

[Back to Top]