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,³ watershed,⁴ 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,⁵ 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 methods^{1, 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 methods^{10, 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 framework¹ 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 contour¹ is a traditional level set method applied in boundary-based image segmentation, which uses the interface of a level set function $\varphi (t,x,y)$ , i.e., the zero level set $\left\{\right(x,y)\mid \varphi (t,x,y)=0\}$ , to conform to the object boundary. Generally, the function $\varphi$ 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:\Omega \to R^{+}$ , the geometric active contour is modeled by the following evolution equation:

3.

Proposed Binary Level Set Method

For the geometric active contour, in order to prevent the level set function $\varphi$ 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 $\varphi$ 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:

In comparison with Eq. 1, the modified evolution equation in Eq. 3 removes the term of $\mathrm{div}(\nabla \varphi ∕\parallel \nabla \varphi \parallel )$ 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:

The preceding process continues until the evolution of the binary level set function $\varphi$ has converged. In step 3, $G_{\epsilon }$ denotes a Gaussian filter, where the standard deviation $\epsilon$ 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 $\epsilon$ generally will give satisfactory results for most images. When $\epsilon$ 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 $\epsilon$ 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(K^2\times N)$ for a $K\times 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\left(N^2\right)$ for calculating a Euclidean distance map. Since $K^2⪡N$ , 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\times 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 $38\min$ , whereas for the proposed method, the evolution of the level set function converged in 60 iterations and lasted only $0.40\min$ . 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 $44\min$ , while the evolution of the proposed model converged in just 67 iterations and $0.46\min$ . 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.

Another experiment conducted on segmenting a staple-inkstand image is presented in Fig. 2 to show the influence of the parameter $\epsilon$ 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 $\epsilon$ becomes larger (which is reflected by the increasing distance between the adjacent evolving contours in each image). When $\epsilon$ 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 $\epsilon$ 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 $\epsilon$ : (a) the original staple-inkstand image; (b), (c), and (d) the evolutions of the contours of the proposed method under $\epsilon =0.3$ , $\epsilon =1.2$ , and $\epsilon =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.

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}