A new variational approach based on level-set function for convex hull problem with outliers

Previous Article
Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal
IPI Home
This Issue
Next Article
Imaging junctions of waveguides

April 2021, 15(2): 315-338. doi: 10.3934/ipi.2020070

A new variational approach based on level-set function for convex hull problem with outliers

Lingfeng Li ^1,2, , Shousheng Luo ^3,4,, , Xue-Cheng Tai ^1, and Jiang Yang ^2,

1.	Department of Mathematics, Hong Kong Baptist University, Hong Kong, China
2.	Department of Mathematics, Southern University of Science and Technology, Shenzhen, China
3.	School of Mathematics and Statistics, Data Analysis Technology Lab, Henan University, Kaifeng, China
4.	Henan Engineering Research Center for Artificial Intelligence Theory and Algorithms, kaifeng, China

^* Corresponding author: sluo@henu.edu.cn

Received December 2019 Revised September 2020 Published April 2021 Early access November 2020

Fund Project: Shousheng Luo: supported by the Programs for Science and Technology Development of He'nan Province (1921 02310181).Xue-Cheng Tai: supported by RG(R)-RC/17-18/02-MATH, HKBU 12300819, and NSF/RGC grant N-HKBU214-19 and RC-FNRA-IG/19-20/SCI/01

Seeking the convex hull of an object (or point set) is a very fundamental problem arising from various tasks. In this work, we propose a variational approach based on the level-set representation for convex hulls of 2-dimensional objects. This method can adapt to exact and inexact convex hull problems. In addition, this method can compute multiple convex hulls simultaneously. In this model, the convex hull is characterized by the zero sublevel-set of a level-set function. For the exact case, we require the zero sublevel-set to be convex and contain the whole given object, where the convexity is characterized by the non-negativity of Laplacian of the level-set function. Then, the convex hull can be obtained by minimizing the area of the zero sublevel-set. For the inexact case, instead of requiring all the given points are included, we penalize the distance from all given points to the zero sublevel-set. Especially, the inexact model can handle the convex hull problem of the given set with outliers very well, while most of the existing methods fail. An efficient numerical scheme using the alternating direction method of multipliers is developed. Numerical examples are given to demonstrate the advantages of the proposed methods.

Keywords: Convex hull, Level-set method, Variational method, ADMM, Outliers.

Mathematics Subject Classification: Primary:68U05, 68U10, 35A15.

Citation: Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, 2021, 15 (2) : 315-338. doi: 10.3934/ipi.2020070

References:

[1]	S. Alpert, M. Galun, A. Brandt and R. Basri, Image segmentation by probabilistic bottom-up aggregation and cue integration, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34 (2011), 315-327. doi: 10.1109/CVPR.2007.383017. Google Scholar
[2]	A. M. Andrew, Another efficient algorithm for convex hulls in two dimensions, Information Processing Letters, 9 (1979), 216-219. Google Scholar
[3]	E. Bae, X.-C. Tai and Z. Wei, Augmented lagrangian method for an Euler's elastica based segmentation model that promotes convex contours, Inverse Problems and Imaging, 11 (2017), 1-23. doi: 10.3934/ipi.2017001. Google Scholar
[4]	C. B. Barber, D. P. Dobkin and H. Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software, 22 (1996), 469-483. doi: 10.1145/235815.235821. Google Scholar
[5]	J. L. Bentley, F. P. Preparata and M. G. Faust, Approximation algorithms for convex hulls, Communications of the ACM, 25 (1982), 64-68. doi: 10.1145/358315.358392. Google Scholar
[6]	M. d. Berg, O. Cheong, M. v. Kreveld and M. Overmars, Computational Geometry: Algorithms And Applications, Springer-Verlag TELOS, 2008. doi: 10.1007/978-3-540-77974-2. Google Scholar
[7]	M. Biro, J. Bonanno, R. Ebrahimi and L. Montgomery, Approximation algorithms for outlier removal in convex hulls, In Proceedings of the 22nd Fall Workshop on Computational Geometry (FWCG 2012), 2012. Google Scholar
[8]	T. Chan and L. Vese, An active contour model without edges, In International Conference on Scale-Space Theories in Computer Vision, pages 141–151. Springer, 1999. doi: 10.1007/3-540-48236-9_13. Google Scholar
[9]	T. F. Chan and W. Zhu, Level set based shape prior segmentation, IEEE Conference on Computer Vision and Pattern Recognition, 2 (2005), 1164-1170. doi: 10.1109/CVPR.2005.212. Google Scholar
[10]	T. M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry, 16 (1996), 361-368. doi: 10.1007/BF02712873. Google Scholar
[11]	D. R. Chand and S. S. Kapur, An algorithm for convex polytopes, Journal of the ACM (JACM), 17 (1970), 78-86. doi: 10.1145/321556.321564. Google Scholar
[12]	G. Charpiat, O. Faugeras and R. Keriven, Shape metrics, warping and statistics, In Proceedings 2003 International Conference on Image Processing (Cat. No. 03CH37429), IEEE, 2 (2003), pages Ⅱ–627. doi: 10.1109/ICIP.2003.1246758. Google Scholar
[13]	B. Chazelle, On the convex layers of a planar set, IEEE Transactions on Information Theory, 31 (1985), 509-517. doi: 10.1109/TIT.1985.1057060. Google Scholar
[14]	L. Condat, A convex approach to k-means clustering and image segmentation, In 11th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, Venice, Italy, 2017, 220–234. doi: 10.1007/978-3-319-78199-0_15. Google Scholar
[15]	D. Cremers and N. Sochen, Towards recognition-based variational segmentation using shape priors and dynamic labeling, In International Conference on Scale Space Methods in Computer Vision, 2003, 388–400. doi: 10.1007/3-540-44935-3_27. Google Scholar
[16]	L.-J. Deng, R. Glowinski and X.-C. Tai, A new operator splitting method for the euler elastica model for image smoothing, SIAM Journal on Imaging Sciences, 12 (2019), 1190-1230. doi: 10.1137/18M1226361. Google Scholar
[17]	W. Gao and A. Bertozzi, Level set based multispectral segmentation with corners, SIAM Journal on Imaging Sciences, 4 (2011), 597-617. doi: 10.1137/100799538. Google Scholar
[18]	R. Glowinski and A. Quaini, On an inequality of C. Sundberg: A computational investigation via nonlinear programming, Journal of Optimization Theory and Applications, 158 (2013), 739-772. doi: 10.1007/s10957-013-0275-y. Google Scholar
[19]	R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letters, 1 (1972), 132-133. Google Scholar
[20]	S. Hert and V. Lumelsky, Motion planning in $\bf{R}^3$ for multiple tethered robots, IEEE Transactions on Robotics and Automation, 15 (1999), 623-639. Google Scholar
[21]	D. P. Huttenlocher, G. A. Klanderman and W. J. Rucklidge, Comparing images using the hausdorff distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15 (1993), 850-863. doi: 10.1109/34.232073. Google Scholar
[22]	R. A. Jarvis, On the identification of the convex hull of a finite set of points in the plane, Information Processing Letters, 2 (1973), 18-21. Google Scholar
[23]	M. Kallay, The complexity of incremental convex hull algorithms in $r^d$, Information Processing Letters, 19 (1984), 197. doi: 10.1016/0020-0190(84)90084-X. Google Scholar
[24]	L. Kavan, I. Kolingerova and J. Zara, Fast approximation of convex hull, ACST, 6 (2006), 101-104. Google Scholar
[25]	D. G. Kirkpatrick and R. Seidel, The ultimate planar convex hull algorithm?, SIAM Journal on Computing, 15 (1986), 287-299. doi: 10.1137/0215021. Google Scholar
[26]	R. Klette, On the approximation of convex hulls of finite grid point sets, Pattern Recognition Letters, 2 (1983), 19-22. doi: 10.1016/0167-8655(83)90017-X. Google Scholar
[27]	C. E. Krvr and S. Ivan, Sequential and parallel approximate convex hull algorithms, Computers and Artificial Intelligence, 14 (1995), 597-610. Google Scholar
[28]	S. S. Kutateladze, AD Alexandrov: Selected Works Part Ⅱ: Intrinsic Geometry of Convex Surfaces, CRC Press, 2005. Google Scholar
[29]	L. Li, S. Luo, X.-C. Tai and J. Yang, A variational convex hull algorithm, In International Conference on Scale Space and Variational Methods in Computer Vision, Springer, 2019, 224–235. doi: 10.1007/978-3-030-22368-7_18. Google Scholar
[30]	T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár and C. L. Zitnick, Microsoft coco: Common objects in context, In European Conference on Computer Vision, Springer, 2014, 740–755. Google Scholar
[31]	L. Liparulo, A. Proietti and M. Panella, Fuzzy clustering using the convex hull as geometrical model, Advances in Fuzzy Systems, 2015 (2015), Art. ID 265135, 13 pp. doi: 10.1155/2015/265135. Google Scholar
[32]	R. Y. Liu, J. M. Parelius and K. Singh, Multivariate analysis by data depth: Descriptive statistics, graphics and inference, The Annals of Statistics, 27 (1999), 783-858. doi: 10.1214/aos/1018031259. Google Scholar
[33]	S. Luo and X.-C. Tai, Convex shape priors for level set representation, arXiv preprint, arXiv: 1811.04715, 2018. Google Scholar
[34]	S. Luo, X.-C. Tai, L. Huo, Y. Wang and R. Glowinski, Multiple convex objects segmentation using single level set function, In International Conference on Computer Vision, 2019, 613–621. Google Scholar
[35]	F. Mémoli and G. Sapiro, A theoretical and computational framework for isometry invariant recognition of point cloud data, Foundations of Computational Mathematics, 5 (2005), 313-347. doi: 10.1007/s10208-004-0145-y. Google Scholar
[36]	S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, volume 153, Springer-Verlag, New York, 2003. doi: 10.1007/b98879. Google Scholar
[37]	S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, 79 (1988), 12-49. doi: 10.1016/0021-9991(88)90002-2. Google Scholar
[38]	D. Peng, B. Merriman, S. Osher, H. Zhao and M. Kang, A PDE-based fast local level set method, Journal of Computational Physics, 155 (1999), 410-438. doi: 10.1006/jcph.1999.6345. Google Scholar
[39]	F. P. Preparata and S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, 20 (1977), 87-93. doi: 10.1145/359423.359430. Google Scholar
[40]	R. A. Rufai, Convex Hull Problems, PhD thesis, George Mason University Fairfax, VA, 2015. Google Scholar
[41]	N. M. Sirakov, A new active convex hull model for image regions, Journal of Mathematical Imaging and Vision, 26 (2006), 309-325. doi: 10.1007/s10851-006-9004-6. Google Scholar
[42]	X.-C. Tai and J. Duan, A simple fast algorithm for minimization of the elastica energy combining binary and level set representations, International Journal of Numerical Analysis and Modeling, 14 (2017), 809-821. doi: 10.1109/tcbb.2016.2591520. Google Scholar
[43]	T. Tomic, C. Ott and S. Haddadin, External wrench estimation, collision detection, and reflex reaction for flying robots, IEEE Transactions on Robotics, 33 (2017), 1467-1482. Google Scholar
[44]	L. A. Vese and T. F. Chan, A multiphase level set framework for image segmentation using the mumford and shah model, International Journal of Computer Vision, 50 (2002), 271-293. Google Scholar
[45]	Z. Zhang, J. Liu, N. S. Cherian, Y. Sun, J. H. Lim, W. K. Wong, N. M. Tan, S. Lu, H. Li and T. Y. Wong, Convex hull based neuro-retinal optic cup ellipse optimization in glaucoma diagnosis, In Annual International Conference of Engineering in Medicine and Biology Society, IEEE, 2009, 1441–1444. Google Scholar
[46]	H.-K. Zhao, T. Chan, B. Merriman and S. Osher, A variational level set approach to multiphase motion, Journal of Computational Physics, 127 (1996), 179-195. doi: 10.1006/jcph.1996.0167. Google Scholar
[47]	H.-K. Zhao, S. Osher and R. Fedkiw, Fast surface reconstruction using the level set method, In Proceedings IEEE Workshop on Variational and Level Set Methods in Computer Vision, IEEE, 2001, 194–201. Google Scholar
[48]	H.-K. Zhao, S. Osher, B. Merriman and M. Kang, Implicit and nonparametric shape reconstruction from unorganized data using a variational level set method, Computer Vision and Image Understanding, 80 (2000), 295-314. Google Scholar
[49]	J. Žunic, Approximate convex hull algorithm–efficiency evaluations, Journal of Information Processing and Cybernetics, 26 (1990), 137-148. Google Scholar

show all references

References:

[1]	S. Alpert, M. Galun, A. Brandt and R. Basri, Image segmentation by probabilistic bottom-up aggregation and cue integration, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34 (2011), 315-327. doi: 10.1109/CVPR.2007.383017. Google Scholar
[2]	A. M. Andrew, Another efficient algorithm for convex hulls in two dimensions, Information Processing Letters, 9 (1979), 216-219. Google Scholar
[3]	E. Bae, X.-C. Tai and Z. Wei, Augmented lagrangian method for an Euler's elastica based segmentation model that promotes convex contours, Inverse Problems and Imaging, 11 (2017), 1-23. doi: 10.3934/ipi.2017001. Google Scholar
[4]	C. B. Barber, D. P. Dobkin and H. Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software, 22 (1996), 469-483. doi: 10.1145/235815.235821. Google Scholar
[5]	J. L. Bentley, F. P. Preparata and M. G. Faust, Approximation algorithms for convex hulls, Communications of the ACM, 25 (1982), 64-68. doi: 10.1145/358315.358392. Google Scholar
[6]	M. d. Berg, O. Cheong, M. v. Kreveld and M. Overmars, Computational Geometry: Algorithms And Applications, Springer-Verlag TELOS, 2008. doi: 10.1007/978-3-540-77974-2. Google Scholar
[7]	M. Biro, J. Bonanno, R. Ebrahimi and L. Montgomery, Approximation algorithms for outlier removal in convex hulls, In Proceedings of the 22nd Fall Workshop on Computational Geometry (FWCG 2012), 2012. Google Scholar
[8]	T. Chan and L. Vese, An active contour model without edges, In International Conference on Scale-Space Theories in Computer Vision, pages 141–151. Springer, 1999. doi: 10.1007/3-540-48236-9_13. Google Scholar
[9]	T. F. Chan and W. Zhu, Level set based shape prior segmentation, IEEE Conference on Computer Vision and Pattern Recognition, 2 (2005), 1164-1170. doi: 10.1109/CVPR.2005.212. Google Scholar
[10]	T. M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry, 16 (1996), 361-368. doi: 10.1007/BF02712873. Google Scholar
[11]	D. R. Chand and S. S. Kapur, An algorithm for convex polytopes, Journal of the ACM (JACM), 17 (1970), 78-86. doi: 10.1145/321556.321564. Google Scholar
[12]	G. Charpiat, O. Faugeras and R. Keriven, Shape metrics, warping and statistics, In Proceedings 2003 International Conference on Image Processing (Cat. No. 03CH37429), IEEE, 2 (2003), pages Ⅱ–627. doi: 10.1109/ICIP.2003.1246758. Google Scholar
[13]	B. Chazelle, On the convex layers of a planar set, IEEE Transactions on Information Theory, 31 (1985), 509-517. doi: 10.1109/TIT.1985.1057060. Google Scholar
[14]	L. Condat, A convex approach to k-means clustering and image segmentation, In 11th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, Venice, Italy, 2017, 220–234. doi: 10.1007/978-3-319-78199-0_15. Google Scholar
[15]	D. Cremers and N. Sochen, Towards recognition-based variational segmentation using shape priors and dynamic labeling, In International Conference on Scale Space Methods in Computer Vision, 2003, 388–400. doi: 10.1007/3-540-44935-3_27. Google Scholar
[16]	L.-J. Deng, R. Glowinski and X.-C. Tai, A new operator splitting method for the euler elastica model for image smoothing, SIAM Journal on Imaging Sciences, 12 (2019), 1190-1230. doi: 10.1137/18M1226361. Google Scholar
[17]	W. Gao and A. Bertozzi, Level set based multispectral segmentation with corners, SIAM Journal on Imaging Sciences, 4 (2011), 597-617. doi: 10.1137/100799538. Google Scholar
[18]	R. Glowinski and A. Quaini, On an inequality of C. Sundberg: A computational investigation via nonlinear programming, Journal of Optimization Theory and Applications, 158 (2013), 739-772. doi: 10.1007/s10957-013-0275-y. Google Scholar
[19]	R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letters, 1 (1972), 132-133. Google Scholar
[20]	S. Hert and V. Lumelsky, Motion planning in $\bf{R}^3$ for multiple tethered robots, IEEE Transactions on Robotics and Automation, 15 (1999), 623-639. Google Scholar
[21]	D. P. Huttenlocher, G. A. Klanderman and W. J. Rucklidge, Comparing images using the hausdorff distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15 (1993), 850-863. doi: 10.1109/34.232073. Google Scholar
[22]	R. A. Jarvis, On the identification of the convex hull of a finite set of points in the plane, Information Processing Letters, 2 (1973), 18-21. Google Scholar
[23]	M. Kallay, The complexity of incremental convex hull algorithms in $r^d$, Information Processing Letters, 19 (1984), 197. doi: 10.1016/0020-0190(84)90084-X. Google Scholar
[24]	L. Kavan, I. Kolingerova and J. Zara, Fast approximation of convex hull, ACST, 6 (2006), 101-104. Google Scholar
[25]	D. G. Kirkpatrick and R. Seidel, The ultimate planar convex hull algorithm?, SIAM Journal on Computing, 15 (1986), 287-299. doi: 10.1137/0215021. Google Scholar
[26]	R. Klette, On the approximation of convex hulls of finite grid point sets, Pattern Recognition Letters, 2 (1983), 19-22. doi: 10.1016/0167-8655(83)90017-X. Google Scholar
[27]	C. E. Krvr and S. Ivan, Sequential and parallel approximate convex hull algorithms, Computers and Artificial Intelligence, 14 (1995), 597-610. Google Scholar
[28]	S. S. Kutateladze, AD Alexandrov: Selected Works Part Ⅱ: Intrinsic Geometry of Convex Surfaces, CRC Press, 2005. Google Scholar
[29]	L. Li, S. Luo, X.-C. Tai and J. Yang, A variational convex hull algorithm, In International Conference on Scale Space and Variational Methods in Computer Vision, Springer, 2019, 224–235. doi: 10.1007/978-3-030-22368-7_18. Google Scholar
[30]	T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár and C. L. Zitnick, Microsoft coco: Common objects in context, In European Conference on Computer Vision, Springer, 2014, 740–755. Google Scholar
[31]	L. Liparulo, A. Proietti and M. Panella, Fuzzy clustering using the convex hull as geometrical model, Advances in Fuzzy Systems, 2015 (2015), Art. ID 265135, 13 pp. doi: 10.1155/2015/265135. Google Scholar
[32]	R. Y. Liu, J. M. Parelius and K. Singh, Multivariate analysis by data depth: Descriptive statistics, graphics and inference, The Annals of Statistics, 27 (1999), 783-858. doi: 10.1214/aos/1018031259. Google Scholar
[33]	S. Luo and X.-C. Tai, Convex shape priors for level set representation, arXiv preprint, arXiv: 1811.04715, 2018. Google Scholar
[34]	S. Luo, X.-C. Tai, L. Huo, Y. Wang and R. Glowinski, Multiple convex objects segmentation using single level set function, In International Conference on Computer Vision, 2019, 613–621. Google Scholar
[35]	F. Mémoli and G. Sapiro, A theoretical and computational framework for isometry invariant recognition of point cloud data, Foundations of Computational Mathematics, 5 (2005), 313-347. doi: 10.1007/s10208-004-0145-y. Google Scholar
[36]	S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, volume 153, Springer-Verlag, New York, 2003. doi: 10.1007/b98879. Google Scholar
[37]	S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, 79 (1988), 12-49. doi: 10.1016/0021-9991(88)90002-2. Google Scholar
[38]	D. Peng, B. Merriman, S. Osher, H. Zhao and M. Kang, A PDE-based fast local level set method, Journal of Computational Physics, 155 (1999), 410-438. doi: 10.1006/jcph.1999.6345. Google Scholar
[39]	F. P. Preparata and S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, 20 (1977), 87-93. doi: 10.1145/359423.359430. Google Scholar
[40]	R. A. Rufai, Convex Hull Problems, PhD thesis, George Mason University Fairfax, VA, 2015. Google Scholar
[41]	N. M. Sirakov, A new active convex hull model for image regions, Journal of Mathematical Imaging and Vision, 26 (2006), 309-325. doi: 10.1007/s10851-006-9004-6. Google Scholar
[42]	X.-C. Tai and J. Duan, A simple fast algorithm for minimization of the elastica energy combining binary and level set representations, International Journal of Numerical Analysis and Modeling, 14 (2017), 809-821. doi: 10.1109/tcbb.2016.2591520. Google Scholar
[43]	T. Tomic, C. Ott and S. Haddadin, External wrench estimation, collision detection, and reflex reaction for flying robots, IEEE Transactions on Robotics, 33 (2017), 1467-1482. Google Scholar
[44]	L. A. Vese and T. F. Chan, A multiphase level set framework for image segmentation using the mumford and shah model, International Journal of Computer Vision, 50 (2002), 271-293. Google Scholar
[45]	Z. Zhang, J. Liu, N. S. Cherian, Y. Sun, J. H. Lim, W. K. Wong, N. M. Tan, S. Lu, H. Li and T. Y. Wong, Convex hull based neuro-retinal optic cup ellipse optimization in glaucoma diagnosis, In Annual International Conference of Engineering in Medicine and Biology Society, IEEE, 2009, 1441–1444. Google Scholar
[46]	H.-K. Zhao, T. Chan, B. Merriman and S. Osher, A variational level set approach to multiphase motion, Journal of Computational Physics, 127 (1996), 179-195. doi: 10.1006/jcph.1996.0167. Google Scholar
[47]	H.-K. Zhao, S. Osher and R. Fedkiw, Fast surface reconstruction using the level set method, In Proceedings IEEE Workshop on Variational and Level Set Methods in Computer Vision, IEEE, 2001, 194–201. Google Scholar
[48]	H.-K. Zhao, S. Osher, B. Merriman and M. Kang, Implicit and nonparametric shape reconstruction from unorganized data using a variational level set method, Computer Vision and Image Understanding, 80 (2000), 295-314. Google Scholar
[49]	J. Žunic, Approximate convex hull algorithm–efficiency evaluations, Journal of Information Processing and Cybernetics, 26 (1990), 137-148. Google Scholar

Figure 1. Convex hulls of an object with outliers. (A) is the real convex hull. (B) and (C) are the results by the quickhull algorithm and the proposed algorithm, respectively. Here the boundaries of the results are colored in red

Download full-size image

Download as PowerPoint slide

Figure 2. (A) shows different level-sets of the SDF of a leaf with periodic the boundary condition and (B) shows the surface plot of the SDF

Download full-size image

Download as PowerPoint slide

Figure 3. Original images taken from the dataset

Download full-size image

Download as PowerPoint slide

Figure 4. Convex hulls corresponding to the images in Figure 3 found by Algorithm 1

Download full-size image

Download as PowerPoint slide

Figure 5. (A), (B) and (C) plot the profiles $ \phi $ at the 0th, 200th and 400th iterations. (D), (E) and (F) plot the corresponding level-set curves of $ \phi $ at the 0th, 200th and 400th iterations

Download full-size image

Download as PowerPoint slide

Figure 6. (A) shows the convex hulls result when $ c = 10 $. (B), (C) and (D) show the corresponding function values of $ \phi $, level-set curves of $ \phi $ and value of $ \Delta\phi $. (E) shows the convex hulls result when $ c = 30 $. (F), (G) and (H) show the corresponding function values of $ \phi $, level-set curves of $ \phi $ and value of $ \Delta\phi $

Download full-size image

Download as PowerPoint slide

Figure 7. Convex hulls of multi-objects by choosing proper values of $ c $

Download full-size image

Download as PowerPoint slide

Figure 8. Convex hulls in object detecting tasks. (A) and (C) are images of bus and cars with segmented masks. (B) and (D) are the associated convex hulls computed by our proposed methods

Download full-size image

Download as PowerPoint slide

Figure 9. Images with outliers and their convex hulls corresponding to the images in Figure 3

Download full-size image

Download as PowerPoint slide

Figure 10. (A), (B), (C) and (D) plot the function value of $ \phi $ at the 0th, 200th, 800th and 3200th iterations when computing the convex hull of the owl image. (E), (F), (G) and (H) show the corresponding level-set curves of $ \phi $ at the 0th, 200th, 800th and 3200th iterations

Download full-size image

Download as PowerPoint slide

Figure 11. Experiment results of the convex layers method. Each row displays three layers of one object

Download full-size image

Download as PowerPoint slide

Figure 12. Convex hulls of occluded objects with a large amount of outliers

Download full-size image

Download as PowerPoint slide

Figure 13. Convex hulls of camera with different $ \lambda $s

Download full-size image

Download as PowerPoint slide

Figure 14. Convex hulls of the aircraft with different $ \lambda $s and landmarks. Figure (D) is obtained by adding two landmarks on the end of blades

Download full-size image

Download as PowerPoint slide

Figure 15. Convex hulls of a set of isolated points. (A) is the exact solution and (B) is the approximation given by our method when the data contains noise

Download full-size image

Download as PowerPoint slide

Table 1. The relative errors of Algorithm 1

name	eggs	frog	aircraft	moth	tendril
error	1.28%	1.51%	1.13%	0.92%	0.73%
name	owl	boat	castle	cart
error	0.61%	1.08%	0.63%	0.79%

Download as excel

name	eggs	frog	aircraft	moth	tendril
error	1.28%	1.51%	1.13%	0.92%	0.73%
name	owl	boat	castle	cart
error	0.61%	1.08%	0.63%	0.79%

Table 2. The Relative Errors of Algorithm 2.

name	eggs	frog	aircraft	moth	tendril
error	1.28%	4.79%	9.63%	3.33%	4.39%
name	owl	boat	castle	cart
error	2.73%	6.85%	3.79%	3.93%

Download as excel

name	eggs	frog	aircraft	moth	tendril
error	1.28%	4.79%	9.63%	3.33%	4.39%
name	owl	boat	castle	cart
error	2.73%	6.85%	3.79%	3.93%

Table 3. Experiment results of using different objective functions

objective functional	(15)	(16)
average iteration number	576	679
average accuracy	1.45%	1.44%
average time	6.01s	7.30s

Download as excel

objective functional	(15)	(16)
average iteration number	576	679
average accuracy	1.45%	1.44%
average time	6.01s	7.30s

[1]	Jiangfeng Huang, Zhiliang Deng, Liwei Xu. A Bayesian level set method for an inverse medium scattering problem in acoustics. Inverse Problems & Imaging, 2021, 15 (5) : 1077-1097. doi: 10.3934/ipi.2021029
[2]	Yong Xia. Convex hull of the orthogonal similarity set with applications in quadratic assignment problems. Journal of Industrial & Management Optimization, 2013, 9 (3) : 689-701. doi: 10.3934/jimo.2013.9.689
[3]	Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, 2021, 15 (3) : 387-413. doi: 10.3934/ipi.2020073
[4]	Yoshikazu Giga, Hiroyoshi Mitake, Hung V. Tran. Remarks on large time behavior of level-set mean curvature flow equations with driving and source terms. Discrete & Continuous Dynamical Systems - B, 2020, 25 (10) : 3983-3999. doi: 10.3934/dcdsb.2019228
[5]	Esther Klann, Ronny Ramlau, Wolfgang Ring. A Mumford-Shah level-set approach for the inversion and segmentation of SPECT/CT data. Inverse Problems & Imaging, 2011, 5 (1) : 137-166. doi: 10.3934/ipi.2011.5.137
[6]	Zhenlin Guo, Ping Lin, Guangrong Ji, Yangfan Wang. Retinal vessel segmentation using a finite element based binary level set method. Inverse Problems & Imaging, 2014, 8 (2) : 459-473. doi: 10.3934/ipi.2014.8.459
[7]	Peter Frolkovič, Viera Kleinová. A new numerical method for level set motion in normal direction used in optical flow estimation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 851-863. doi: 10.3934/dcdss.2020347
[8]	Wangtao Lu, Shingyu Leung, Jianliang Qian. An improved fast local level set method for three-dimensional inverse gravimetry. Inverse Problems & Imaging, 2015, 9 (2) : 479-509. doi: 10.3934/ipi.2015.9.479
[9]	Mariane Bourgoing. Viscosity solutions of fully nonlinear second order parabolic equations with $L^1$ dependence in time and Neumann boundary conditions. Existence and applications to the level-set approach. Discrete & Continuous Dynamical Systems, 2008, 21 (4) : 1047-1069. doi: 10.3934/dcds.2008.21.1047
[10]	Alessandro Ferriero, Nicola Fusco. A note on the convex hull of sets of finite perimeter in the plane. Discrete & Continuous Dynamical Systems - B, 2009, 11 (1) : 103-108. doi: 10.3934/dcdsb.2009.11.103
[11]	Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201
[12]	Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091
[13]	Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial & Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811
[14]	Henning Struchtrup. Unique moment set from the order of magnitude method. Kinetic & Related Models, 2012, 5 (2) : 417-440. doi: 10.3934/krm.2012.5.417
[15]	Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[16]	Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[17]	Jing Xu, Xue-Cheng Tai, Li-Lian Wang. A two-level domain decomposition method for image restoration. Inverse Problems & Imaging, 2010, 4 (3) : 523-545. doi: 10.3934/ipi.2010.4.523
[18]	Yoshifumi Aimoto, Takayasu Matsuo, Yuto Miyatake. A local discontinuous Galerkin method based on variational structure. Discrete & Continuous Dynamical Systems - S, 2015, 8 (5) : 817-832. doi: 10.3934/dcdss.2015.8.817
[19]	Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial & Management Optimization, 2020, 16 (2) : 835-856. doi: 10.3934/jimo.2018181
[20]	Kuei-Hu Chang. A novel risk ranking method based on the single valued neutrosophic set. Journal of Industrial & Management Optimization, 2021 doi: 10.3934/jimo.2021065

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Lingfeng Li Shousheng Luo Xue-Cheng Tai Jiang Yang
on Google Scholar
Lingfeng Li Shousheng Luo Xue-Cheng Tai Jiang Yang

2020 Impact Factor: 1.639

Tools

Article outline

Figures and Tables

2020 Impact Factor: 1.639

Tools

Figures and Tables

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Lingfeng Li Shousheng Luo Xue-Cheng Tai Jiang Yang
on Google Scholar
Lingfeng Li Shousheng Luo Xue-Cheng Tai Jiang Yang

[Back to Top]