Keywords

1 Introduction

Image segmentation is an essential step for image analysis and understanding, which can be applied in several practical problems such as medical research, intelligent recognition, 3D reconstruction and image retrieval/compression. An ideal segmentation algorithm should cluster pixels into salient regions which corresponding to individual surfaces, objects or nature parts of objects.

Image segmentation is an old and recurrent problem in computer vision. Various algorithms have been proposed to cope with this problem. Generally, The proposed classical algorithms including watershed [1, 2], mean shift [3–5], region-growing [6, 7], and superpixel [8, 9] are based on region, which start from the gray pixel, and cluster the pixels with similar value into different regions. As shown in Fig. 57.1, the Watershed algorithm is fast and easy to extend to n-dimensional images, but it may leads to under-segmentation in the absence of boundary cues (see Fig. 57.1b), and the result depend on the threshold; Mean shift is an effective clustering iterative algorithm, but it also creates under-segmentation and unmeaning regions because of the lacking compactness constraint; Super-pixel algorithms based on graph cut [9] and geometric flows are proposed in recent years, which can divide an image into many small regions. however most of the regions in Fig. 57.1d are not corresponding an independent part or object, and the long runtime is another disadvantage of these algorithms.

Fig. 57.1
figure 1

Segmentation results with four classical algorithms. a wateshed. b Meanshift. c N-cuts

Full size image
Fig. 57.2
figure 2

The process of our proposed algorithm. a input image; b edge detection; c breakpoints detection; d edge growth; e region merging; d segmentation result

Full size image

The other kind of algorithms is based on edges [10–13], which attain the segmentation goal by linking the edges into a series of closed boundary. For example, Chen and Sun [12] present a new edge-based interactive image segmentation method based the edge image which is generated with the edge detector; Takumi Uemura and Gou Koutaki [10] propose an algorithm by using their proposed boundary code method, which is more accurately than existing methods in images those have a narrow elongated object, shading and blurring. However, this kind of methods are not rich compared with the region based method, but it is more attractive because it can attain a more meaningful result and avoid the threshold problem.

In this paper, we propose an effective algorithm to divide the image into a series meaningful region by using the edge information. Our method is starting from the breakpoints which caused by the canny detector, and then the edge chains are grown at the breakpoints with the proposed criterions to achieve the goal of edge linking. Finally, two adjacent closed regions with similar color will be merged into one region.

Section 57.2 gives the global procedure of the proposed algorithm; Sect. 57.3 describes the key steps of the proposed algorithm; Sect. 57.4 comments on the experimental results in detail and Sect. 57.5 concludes the paper.

2 Segmentation Process

As shown in Fig. 57.2, the process of our algorithm mainly contains four steps:

  1. 1.

    Edge Detection. We choose canny detector to obtain the edges in the image because of its excellent linking ability for edges with low contrast.

  2. 2.

    Breakpoints Detection. As shown in Fig. 57.2c, there are a lot of breakpoints (the green crosses), so the boundary of the toy is not closed. In order to remove them, we extract breakpoints with the algorithm described in Sect. 57.3.1 and extract a set of edge chains which connected with the breakpoints.

  3. 3.

    Edge Growth. If the edge chain connected with the breakpoint is prolonged based on a certain criterion, all edges will be closed and the salient region will be segmented. Based on this idea, we propose our algorithm in Sect. 57.3.2, and the closed regions are labeled after edge growth (see Fig. 57.2d).

  4. 4.

    Region Merging. Because the unreasonable regions are still exist after edge growth (e.g. the regions in the head of the toy), we merge them based on the color similarity (See the detailed algorithm in Sect. 57.3.3), and the final labeled image is shown in Fig. 57.2f.

3 Key Steps in Segmentation

3.1 Breakpoint Detection

For a non-zero pixel (the gray pixel in Fig. 57.3) in the edge map and its 3-by-3 neighborhood whose label is shown in Fig. 57.3a, we define

$$ f(x) = \sum\limits_{j = 1}^{8} {(a_{j} - b_{j} )} , $$
(57.1)

Where \( a = [x(1),x(2),x(3),x(6),x(9),x(8),x(7),x(4)], \) \( b = [x(2),x(3),x(6),x(9),x(8),x(7),x(4),x(1)] \) and \( x(i) = \{ 0,1\} ,(i = 1 \ldots 9) \) is the value of each pixel in the 3-by-3 neighborhood matrix. Based on the previous study [14], the non-zero pixel is a breakpoint (See Fig. 57.3b) when \( f ( {\text{x)}} = 2 \).

Fig. 57.3
figure 3

8-neighborhood of a breakpoint. a The label; b Breakpoints

Full size image

3.2 Edge Growth

Given a breakpoint P we consider its local structure in a sliding window \( \left( {M \times M} \right) \). As shown in Fig. 57.4, the edge will be grown at the breakpoint based on two cases:

Fig. 57.4
figure 4

Edge Growth method, the black boxes are the sliding window. a \( P_{4} \) is the final point linked to P, the final linking route (black); b original edge (gray), the mapping part (black)

Full size image
  1. 1.

    Other breakpoints such as \( P_{1} ,P_{2} ,\ldots ,P_{n} , \) (Fig. 57.4a) are existed in the window:

First, the total gradient of each route (four routes in Fig. 57.4a) from P to \( P_{i} \) will be computed by

$$ G = \sum\limits_{i = 1}^{{n{ - }1}} { ( (Gr(x_{i + 1} ,y_{i + 1} )- Gr(x_{i} ,y_{i} ))^{2} + (Gr(x_{i} ,y_{i + i} ) - Gr(x_{i} ,y_{i} ))^{2} )^{1/2} } $$
(57.2)

Where G is the grayscale, \( (x,y) \) is the coordinates of the route, \( Gr(x,y) \) is the gray value;

Then the route with the maximum value of G will be chosen as the final linking route (the black route in Fig. 57.4a), and the edge will be linked in the sliding window finally.

  1. 2.

    No other breakpoints are existed in the window (Fig. 57.4.b):

In this case, we map the edges connected with P (the gray pixels in Fig. 57.4b) to its symmetric positions(the black pixels in Fig. 57.4b) in the sliding window and update P. Then above step will be repeated until P meets the image boundary or other edges.

3.3 Region Merging

After edge growth, the edge map will be segmented into many closed regions. For an added edge with a certain length, we compute the average gray value of its two adjacent regions which labeled as i and j, and defined them as \( G_{i} \) and \( G_{j} \). If their absolute difference is smaller than the predefined threshold T, this edge will be deleted in edge map B.

$$ G_{i/j} = \frac{1}{m}\sum\limits_{k = 1}^{m} {Gr(x_{k} ,y_{k} )} $$
(57.3)

Where \( Gr \) is the grayscale image, \( Gr(x_{k} ,y_{k} ) \) is the \( k{\text{th}} \) pixel’s gray value of the closed region i or j, and m is the total numbers of pixels.

4 Experiment

Figure 57.5 gives the computation time of all 72 images. In our experiments, all results are implemented on Intel Core 2 Duo CPU 2.8 GHz with Matlab 2008a. We can see that the computation time is approximately proportional to the number of breakpoints, and 91.54 % images require a time less than 40 s.

Fig. 57.5
figure 5

Time cost (in seconds) requires by our algorithm for the processing of 72 images

Full size image

Figure 57.6 shows some qualitative results of our algorithm in a part of chosen nature images which contain highly geometrical contents. We can see that the results are close with the human vision system and nearly all regions are segmented completely, and the regions connected with low contrast edges are also extracted well. Specifically, the regions in the traffic sign image and the road image are meaningful enough to the further image understanding such as shape analysis, object identification and 3D reconstruction.

Fig. 57.6
figure 6

Segmentation result. a input image; b edge map; c edge growth; d labeled segments

Full size image

Figure 57.7 shows a comparison of various classical algorithms and our proposed algorithm. As shown in the figure, the improved Watershed algorithm leads to under-segmentation because it depends much on the gray level information. For instance, the whole image was segmented into just two parts and some detailed regions such as the trees and the road sign were lost in the road image, and the cylinder is not segmented from the background in the second image; Mean shift algorithm cluster a lot of crushing and unmeaning regions(See the small regions in the human image) and need to set different parameters for different image; N-cuts algorithm divided an complete region into a lot of irregular regions, and the results around the edges with low contrast are not satisfied. Compared with the above algorithms, our algorithm gives a more encouraging result because the shadow of the person, the cylinder and the traffic signs are all segmented completely. In addition, the runtime of N-cuts is much longer than ours, as shown in Fig. 57.7.

Fig. 57.7
figure 7

A comparison of four image segment methods. a proposed algorithm; b Watershed; c Mean Shift; d N-cuts

Full size image

5 Conclusion

In this paper, we proposed a novel method to segment image by using the edges information. Our approach avoids the problem in threshold setting and seed selection, and the segmentation regions are more practical significance. However, there are still many regions are over-segmentation. The main reasons are: (1) noise interference. Canny operator takes noises as a lot of short edges, which will affect the segmentation result; (2) Errors during edge growth, Though most of edge chains can be linked or grown in a right way based on our algorithm, some edge chains whose shape is a curve will be prolonged in a wrong way. So our work was just beginning. It should be studied further to solve the above problems.