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
-
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
| 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 |
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.
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 and 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. |
| [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.
|
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. |
| [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.
|
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
Figure 3.
Original images taken from the dataset
Figure 4.
Convex hulls corresponding to the images in Figure 3 found by Algorithm 1
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
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 $
Figure 7.
Convex hulls of multi-objects by choosing proper values of $ c $
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
Figure 9.
Images with outliers and their convex hulls corresponding to the images in Figure 3
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
Figure 11.
Experiment results of the convex layers method. Each row displays three layers of one object
Figure 12.
Convex hulls of occluded objects with a large amount of outliers
Figure 13.
Convex hulls of camera with different $ \lambda $ s
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
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
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% |
| 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% |
| 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 |
| objective functional | (15) | (16) |
| average iteration number | 576 | 679 |
| average accuracy | 1.45% | 1.44% |
| average time | 6.01s | 7.30s |
| [1] |
Yong Xia. Convex hull of the orthogonal similarity set with applications in quadratic assignment problems. Journal of Industrial and Management Optimization, 2013, 9 (3) : 689-701. doi: 10.3934/jimo.2013.9.689 |
| [2] |
Jiangfeng Huang, Zhiliang Deng, Liwei Xu. A Bayesian level set method for an inverse medium scattering problem in acoustics. Inverse Problems and Imaging, 2021, 15 (5) : 1077-1097. doi: 10.3934/ipi.2021029 |
| [3] |
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 and Continuous Dynamical Systems - B, 2020, 25 (10) : 3983-3999. doi: 10.3934/dcdsb.2019228 |
| [4] |
Esther Klann, Ronny Ramlau, Wolfgang Ring. A Mumford-Shah level-set approach for the inversion and segmentation of SPECT/CT data. Inverse Problems and Imaging, 2011, 5 (1) : 137-166. doi: 10.3934/ipi.2011.5.137 |
| [5] |
Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems and Imaging, 2021, 15 (3) : 387-413. doi: 10.3934/ipi.2020073 |
| [6] |
Zhenlin Guo, Ping Lin, Guangrong Ji, Yangfan Wang. Retinal vessel segmentation using a finite element based binary level set method. Inverse Problems and 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 and 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 and Imaging, 2015, 9 (2) : 479-509. doi: 10.3934/ipi.2015.9.479 |
| [9] |
Alessandro Ferriero, Nicola Fusco. A note on the convex hull of sets of finite perimeter in the plane. Discrete and Continuous Dynamical Systems - B, 2009, 11 (1) : 103-108. doi: 10.3934/dcdsb.2009.11.103 |
| [10] |
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 and Continuous Dynamical Systems, 2008, 21 (4) : 1047-1069. doi: 10.3934/dcds.2008.21.1047 |
| [11] |
Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2022, 18 (3) : 2237-2253. doi: 10.3934/jimo.2021065 |
2020 Impact Factor: 1.639
Tools
Metrics
Other articles
by authors
[Back to Top]