• PDF
• Cite
• Share
Article Contents  Article Contents

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

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

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

 Citation: • • 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

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%

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%

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
• Figures(15)

Tables(3)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint