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

Previous Article
Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods
IPI Home
This Issue
Next Article
Inverse scattering and stability for the biharmonic operator

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 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, 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]	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
[2]	Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[3]	Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101
[4]	Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134
[5]	Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020178
[6]	Tetsuya Ishiwata, Takeshi Ohtsuka. Numerical analysis of an ODE and a level set methods for evolving spirals by crystalline eikonal-curvature flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 893-907. doi: 10.3934/dcdss.2020390
[7]	Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[8]	Xiaoxiao Li, Yingjing Shi, Rui Li, Shida Cao. Energy management method for an unpowered landing. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020180
[9]	Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095
[10]	Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[11]	Qing-Hu Hou, Yarong Wei. Telescoping method, summation formulas, and inversion pairs. Electronic Research Archive, , () : -. doi: 10.3934/era.2021007
[12]	Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[13]	Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[14]	Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020462
[15]	Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[16]	Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[17]	Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[18]	Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097
[19]	Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139
[20]	C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020058

2019 Impact Factor: 1.373

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

2019 Impact Factor: 1.373

Tools

Article outline

Figures and Tables

2019 Impact Factor: 1.373

Tools

Figures and Tables

2019 Impact Factor: 1.373

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]