1 May 2007 Boundary-based image segmentation using binary level set method
Author Affiliations +
Abstract
A novel binary level set method for boundary-based image segmentation is proposed, which is extended from region-based binary level set methods. The proposed binary level set method is based on the geometric active contour framework, which is a traditional level set method applied in boundary-based image segmentation. However, being different from the geometric active contour, the proposed binary level set method replaces the traditional level set function with a binary level set function to reduce the expensive computational cost of redistancing the traditional level set function. The experiments and complexity analysis show that the proposed binary level set method is more efficient than the geometric active contour for image segmentation while giving similar results to the geometric active contour.
Zhu, Zhang, Zeng, and Wang: Boundary-based image segmentation using binary level set method

1.

Introduction

Image segmentation is a fundamental problem in image processing and computer vision. Various techniques have been applied in image segmentation, such as level set,1, 2 graph cut,3 watershed,4 and so on. This letter addresses the issue of the application of level set methods in image segmentation. The level set method, first introduced by Osher and Sethian,5 employs the interface of a level set function, i.e., the zero level set, to represent the object boundary in image segmentation. Generally speaking, the level set methods for image segmentation can be classified into two types, which are the boundary-based methods1, 2, 6, 7 and the region-based methods.8, 9 The boundary-based methods perform the image segmentation by using the interface of a level set function to detect the image edge formed by the object boundary. The region-based methods perform the image segmentation by optimizing the homogeneous image features, respectively, inside and outside the interface of a level set function.

The application of the level set method in image segmentation has been very popular due to its capability of automatically handling changes in topology. However, a redistance procedure, which leads to expensive computation, is required in the traditional level set method to keep the level set function as a signed distance function to its interface. Very recently, some binary level set methods10, 11, 12, 13 for region-based image segmentation were proposed to reduce the computational cost. Unlike the traditional level set method, the binary level set methods can avoid the redistance procedure by replacing the traditional level set function with a binary level set function. In this letter, we extend the binary level set concept from the region-based image segmentation to the boundary-based image segmentation by presenting a novel binary level set method based on the geometric active contour framework1 that is a traditional level set method applied in boundary-based image segmentation. The experiments and complexity analysis show the efficiency of the proposed binary level set method.

2.

Geometric Active Contour

The geometric active contour1 is a traditional level set method applied in boundary-based image segmentation, which uses the interface of a level set function ϕ(t,x,y) , i.e., the zero level set {(x,y)ϕ(t,x,y)=0} , to conform to the object boundary. Generally, the function ϕ is set to be a signed distance function that is positive in the interior and negative in the exterior of its interface. Given a gray-value image I:ΩR+ , the geometric active contour is modeled by the following evolution equation:

1

ϕt=g(I)ϕ[div(ϕϕ)+ν],
where ν is a constant parameter controlling the balloon force, and g is the edge indicator function, which is commonly defined as

2

g(I)=11+(Gσ*I),
where Gσ denotes the Gaussian filter with standard deviation σ . According to Eq. 1, the interface of the level set function ϕ can evolve from an appropriate initial position to the object boundary, where strong image edges make the edge indicator function g approach zero.

3.

Proposed Binary Level Set Method

For the geometric active contour, in order to prevent the level set function ϕ being too steep or flat near its interface, the level set function is traditionally initialized to be a signed distance function to its interface, and a redistance procedure is required during the evolution of the level set function. Unfortunately, the redistance procedure is a very expensive operation. To reduce the computational cost, here we propose a novel level set method by substituting a binary level set function for the traditional level set function in the geometric active contour. The binary level set function ϕ takes 1 in the interior and 1 in the exterior of its interface. Therefore, the redistance procedure can be avoided. Reconsidering Eq. 1, for the proposed method, we simplify the evolution equation into the following form:

3

ϕt=νg(I)ϕ.

In comparison with Eq. 1, the modified evolution equation in Eq. 3 removes the term of div(ϕϕ) that has the function of penalizing the irregular shape of the interface of the level set function. Instead, the level set function is smoothed by a Gaussian filter to keep its interface regular in the proposed method. In accordance with the schemes introduced in other papers,11, 12, 13 we implement the proposed binary level set method in an iterative procedure, which consists of the following steps:

  • 1. Initialize the binary level set function ϕ .

  • 2. Evolve the level set function ϕ according to Eq. 3.

  • 3. Smooth the level set function by a Gaussian filter, i.e., ϕ=Gε*ϕ .

  • 4. Let ϕ take 1 if ϕ0 ; otherwise, let ϕ take 1 . Go to step 2.

The preceding process continues until the evolution of the binary level set function ϕ has converged. In step 3, Gε denotes a Gaussian filter, where the standard deviation ε of the Gaussian filter is a critical parameter for the proposed method. According to our experiments, a value between 0.7 to 1.6 for ε generally will give satisfactory results for most images. When ε becomes too small, the number of iterations will increase and result in a longer computational time, and the proposed method will be sensitive to image noise or clutter. On the other hand, a large ε can significantly reduce the number of iterations and computational time; however, boundary leakage may happen in this case.

The binary level set method proposed here has a lower computational complexity than the geometric active contour. In the proposed method, the most time-consuming operation is the Gaussian convolution in step 3, which has the computational complexity of O(K2×N) for a K×K Gaussian convolution kernel implemented in the spatial domain on an image with N pixels, where K is typically less than 7. The complexity of redistancing a level set function is O(N2) for calculating a Euclidean distance map. Since K2N , the Gaussian convolution is more efficient than the redistancing procedure. Furthermore, in order to keep the evolution of the level set function stable, the step time t in Eq. 1 should take a relative small value, so the geometric active contour requires many more iterations than the proposed method, as will be shown in the following experiments. Therefore, the proposed method can be performed much faster than the geometric active contour with lower computational complexity and fewer iterations.

4.

Experimental Results

In this section, we first conduct the experiments to compare the performance of the proposed binary level set method with that of the traditional geometric active contour on image segmentation. The algorithms were implemented in MATLAB and executed on a 2.8-GHz Intel Pentium IV workstation. Figure 1 shows two examples of our experiments. The size of each tested image is 240×240 pixels. The upper row of Fig. 1 shows the segmentation results of a hand image, respectively, using the geometric active contour and the proposed binary level set method. For the geometric active contour, the evolution of the level set function converged in 6800 iterations and took 38min , whereas for the proposed method, the evolution of the level set function converged in 60 iterations and lasted only 0.40min . The lower row of Fig. 1 shows the segmentation results of a more complex corpus callosum magnetic resonance (MR) image using the geometric active contour and the proposed binary level set method, respectively. The evolution of the geometric active contour converged in 7400 iterations and 44min , while the evolution of the proposed model converged in just 67 iterations and 0.46min . Therefore, the proposed binary level set method is much more efficient than the geometric active contour. As for the segmentation performance, it can be seen from Fig. 1 that the proposed binary level set method gives similar segmentation results to the geometric active contour.

Fig. 1

Comparisons between the geometric active contour and the proposed algorithm: (a) the original hand image with the initial contour; (b) and (c) the results of the geometric active contour and the proposed method on segmenting the hand image, respectively; (d) the original corpus callosum MR image with the initial contour; (e) and (f) the segmental results of the geometric active contour and the proposed method on segmenting the corpus callosum MR image, respectively. Note that the black lines represent the initial contours, while the white lines represent the final contours at the steady states.

050501_1_1.jpg

Another experiment conducted on segmenting a staple-inkstand image is presented in Fig. 2 to show the influence of the parameter ε of the Gaussian filter on the performance of the proposed method. It is seen that the evolution speed increases as the value of the parameter ε becomes larger (which is reflected by the increasing distance between the adjacent evolving contours in each image). When ε is too small, the final contour is not smooth and is attracted by some weak edge formed by the background, as shown in Fig. 2b. On the other hand, when ε is too big, leakage appears that completely damages the segmental result, as shown in Fig. 2d.

Fig. 2

Segmental results of the proposed method under different values of ε : (a) the original staple-inkstand image; (b), (c), and (d) the evolutions of the contours of the proposed method under ε=0.3 , ε=1.2 , and ε=2.0 , respectively. Note that the white lines in (b) and (c) represent the final contours at the steady states, while the white line in (d) represents the contour at the 40th iteration. Note also that we drew the evolving contour every other 7 iterations.

050501_1_2.jpg

5.

Conclusions

We have proposed a novel binary level set method based on the geometric active contour framework for boundary-based image segmentation. By substituting a binary level set function for the traditional level set function in the geometric active contour, the proposed binary level set method can significantly reduce the expensive computational cost on redistancing the traditional level set function. The experiments show the efficiency of the proposed binary level set method. It should be pointed out that the proposed binary level set method can be easily extended to geodesic active contours.6, 7

Acknowledgments

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions.

References

1.  V. Caselles, F. Catte, T. Coll, and F. Dibos, “A geometric model for active contours in image processing,” Numer. Math.0029-599X 10.1007/BF01385685 66, 1–31 (1993). Google Scholar

2.  R. Malladi, J. A. Sethian, and B. C. Vemuri, “Shape modeling with front propagation: a level set approach,” IEEE Trans. Pattern Anal. Mach. Intell.0162-8828 10.1109/34.368173 17, 158–175 (1995). Google Scholar

3.  Y. Boykov and M. P. Jolly, “Interactive graph cuts for optimal boundary and region segmentation of objects in ND images,” in Proc. IEEE Int. Conf. on Computer Vision (ICCV), vol. 1, pp. 105–112 (2001). Google Scholar

4.  F. Meyer and S. Beucher, “Morphological segmentation,” J. Visual Commun. Image Represent1047-3203 10.1006/jvci.2001.0457 1, 21–46 (1990). Google Scholar

5.  S. Osher and J. A. Sethian, “Fronts propagating with curvature dependent speed: algorithms based on Hamilton-Jacobi formulations,” J. Comput. Phys.0021-9991 10.1016/0021-9991(88)90002-2 79, 12–49 (1988). Google Scholar

6.  S. Kichenesamy, A. Kumar, P. Olver, A. Tannenbaum, and A. Yezzi, “Conformal curvature flows: from phase transitions to active contours,” Arch. Ration. Mech. Anal.0003-9527 10.1007/BF00379537 134, 275–301 (1996). Google Scholar

7.  V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic active contours,” Int. J. Comput. Vis.0920-5691 10.1023/A:1007979827043 22, 61–79 (1997). Google Scholar

8.  T. Chan and L. Vese, “Active contours without edges,” IEEE Trans. Image Process.1057-7149 10.1109/83.902291 10, 266–277 (2001). Google Scholar

9.  G. Zhu, Q. Zeng, and C. Wang, “Dual geometric active contour for image segmentation,” Opt. Eng.0091-3286 10.1117/1.2333566 45, 080505 (2006). Google Scholar

10.  J. Lie, M. Lysaker, and X. C. Tai, “A binary level set model and some applications to Mumford-Shah image segmentation,” IEEE Trans. Image Process.1057-7149 10.1109/TIP.2005.863956 15, 1171–1181 (2006). Google Scholar

11.  X. C. Tai, O. Christiansen, P. Lin, and I. Skjælaaen, “Image segmentation using some piecewise constant level set methods with MBO type of project,” Int. J. Comput. Vis.0920-5691 10.1007/s11263-006-9140-x 73, 61–76 (2007). Google Scholar

12.  S. Esedoglu and Y.-H. R. Tsai, “Threshold dynamics for the piecewise constant Mumford-Shah functional,” J. Comput. Phys.0021-9991 211, 367–384 (2006). Google Scholar

13.  S. P. Awate, T. Tasdizen, and R. T. Whitaker, “Unsupervised texture segmentation with nonparametric neighborhood statistics,” in Proc. Int. Conf. European Conference on Computer Vision (ECCV), vol. 2, pp. 494–507 (2006). Google Scholar

© (2007) Society of Photo-Optical Instrumentation Engineers (SPIE)
Guopu Zhu, Guopu Zhu, Shuqun Zhang, Shuqun Zhang, Qingshuang Zeng, Qingshuang Zeng, Changhong Wang, Changhong Wang, } "Boundary-based image segmentation using binary level set method," Optical Engineering 46(5), 050501 (1 May 2007). https://doi.org/10.1117/1.2740762 . Submission:
JOURNAL ARTICLE
3 PAGES


SHARE
Back to Top