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

Lingfeng Li; Shousheng Luo; Xue-Cheng Tai; Jiang Yang

doi:10.3934/ipi.2020070

Article Contents

2021, Volume 15, Issue 2: 315-338. Doi: 10.3934/ipi.2020070

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

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

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
^* Corresponding author: sluo@henu.edu.cn

Received: December 2019

Revised: September 2020

Early access: November 2020

Published: April 2021

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

Abstract / Introduction Full Text(HTML) Figure(15) / Table(3) Related Papers Cited by

Abstract

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:

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

Citation:

Full Text(HTML)

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 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 PowerPoint slide

Figure 3. Original images taken from the dataset

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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 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 PowerPoint slide

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

Download: Full-size image 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 PowerPoint slide

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

Download: Full-size image 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 PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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 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 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%

| Show Table

DownLoad: CSV

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%

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[2]	A. M. Andrew, Another efficient algorithm for convex hulls in two dimensions, Information Processing Letters, 9 (1979), 216-219.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[19]	R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letters, 1 (1972), 132-133.
[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.
[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.
[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.
[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.
[24]	L. Kavan, I. Kolingerova and J. Zara, Fast approximation of convex hull, ACST, 6 (2006), 101-104.
[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.
[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.
[27]	C. E. Krvr and S. Ivan, Sequential and parallel approximate convex hull algorithms, Computers and Artificial Intelligence, 14 (1995), 597-610.
[28]	S. S. Kutateladze, AD Alexandrov: Selected Works Part Ⅱ: Intrinsic Geometry of Convex Surfaces, CRC Press, 2005.
[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.
[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.
[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.
[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.
[33]	S. Luo and X.-C. Tai, Convex shape priors for level set representation, arXiv preprint, arXiv: 1811.04715, 2018.
[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.
[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.
[36]	S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, volume 153, Springer-Verlag, New York, 2003. doi: 10.1007/b98879.
[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.
[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.
[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.
[40]	R. A. Rufai, Convex Hull Problems, PhD thesis, George Mason University Fairfax, VA, 2015.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[49]	J. Žunic, Approximate convex hull algorithm–efficiency evaluations, Journal of Information Processing and Cybernetics, 26 (1990), 137-148.