Abstract: This research presents a new approach for improving range image segmentation, based on fuzzy regularization of the detected edges. First, a degraded version of the segmentation is produced by a new region growing-based algorithm. Next, the resulting segmentation is refined by a robust fuzzy classification of the pixels on the resulting edges which correspond to borders of the extracted regions. Pixels on the boundary between tow adjacent regions are labeled taking into account the two regions as fuzzy sets in the fuzzy classification stage, using an improved version of the Fuzzy C-Mean (FCM) algorithm. The process is repeated for all region boundaries in the image. Extensive tests were performed with real images from the ABW database. The experimental results illustrate the good impact of the fuzzy regularization on the segmentation results. The high quality of the segmentation results compared with those of some well known segmentation methods show the good potential of our fuzzy approach for improving range image segmentation.
INTRODUCTION
Segmenting an image consists in assigning its pixels in homogenous, continuous and disjoint sets, called image regions. Image segmentation is often essential for high level image analysis and understanding. Like other types of images, segmentation methods in range images can be divided into two categories: edge-based and region-based segmentation. In region-based approach (Bab Hadiashar and Gheissari, 2006; Kang and Ikeuchi, 1993; Ding et al., 2005; Li and Zhao, 2003), pixels with the same proprieties are gathered in disjoint regions, forming an image partition. Region-based methods are robust and less sensitive to noise. However, their efficiency depends strongly on the selection of the region seeds. Furthermore, pixels belonging to an edge are often arbitrarily labeled, by ad hoc assignment to one of the neighboring regions. In edge-based approach, the pixels with discontinuities in range data or in surface normals are detected and linked in order to form the region boundaries (Fan et al., 1987; Jiang and Bunke, 1999). Edge-based methods have fairly low computational cost, compared to region-based methods; however, they are very sensitive to noise. In both approaches a post processing of the resulting segmentation is needed. It consists often in the enhancement of the region boundaries. In this study we focus on this problem and we provide a framestudy for segmentation improvement by fuzzy edge regularization.
Many researchers have proposed fuzzy clustering to improve MR Image (MRI) segmentation (Xue et al., 2000; Shen et al., 2005; Colliot et al., 2006). Fuzzy clustering is well appropriate for MRI segmentation because in this type of images, classes are well known and correspond to the different anatomic parts of body. However, few authors have used fuzzy clustering in range image segmentation. In range image, clusters correspond to the different visible parts of the objects in the scene. So their number and prototypes are unknown.
In order to provide a framework for geometrical feature detection in range images, Borges and Aldon (2004) has proposed a fuzzy split and merge for line extraction. They employ fuzzy clustering in a split and merge framework without the need to guess the number of clusters. Burgiss et al. (1998) incorporate features from multiple image types in order to provide a robust edge detector for 3D scene analysis. Their segmentation approach is based on applying a watershed algorithm to a fuzzy feature map. The fuzzy feature map contains fuzzy degrees of membership of pixels to a particular feature. Soodamani and Liu (2000) have used fuzzy attributes with a genetic algorithm to enhance recognition performance in a model-based vision from range images. The authors claim that the accuracy of recognizing known instances of objects and generalization capability by recognizing unknown instances of known objects is greatly improved.
Most of the proposed approaches using fuzzy clustering for image segmentation proceed by assigning pixels to clusters without ensuring the continuity of the resulting clusters. For several types of images this is not a drawback, especially when clusters are not necessarily continuous, such as in MR images. However, clusters in range images, which correspond to surface patches, must be continuous. Most of the proposed methods have not addressed and deal with this problem.
In this study we propose first, an enhanced region growing algorithm for providing an initial segmentation of the image. The initial segmentation is then refined by a fuzzy classification of pixels of the resulting edges. The introduced region growing technique is based on random sampling of region seeds. It allows to provide an initial, but degraded, region-based segmentation. In the second stage, pixels on region boundaries are labeled using the Fuzzy C-Mean algorithm (FCM) (Bezdek, 1981). The FCM algorithm is applied to every pair of adjacent regions, in order to assign each pixel of the boundary, to one of the two regions. So, contrary to the existing fuzzy-based methods, we use only two clusters with well defined initial prototypes. The proposed edge classification scheme has allowed to formulate region continuity by defining a constraint on the possible clusters of a given pixel. Indeed, the label of a given pixel is selected among the two labels corresponding to the regions for which the pixel is on their boundary. The experiments performed with real images from the ABW database (Hoover et al., 1996) show the usefulness of the fuzzy edge regularization to provide an accurate segmentation of range images.
IMAGE SEGMENTATION BY RANDOMIZED REGION SEED SAMPLING
Surface modeling: A range image is a discretized two-dimensional array where at each pixel (x, y) is recorded the distance dx, y between the range finder plane and the corresponding point of the scene. Regions in such an image represent the visible patches of object surfaces. Let d* a new representation of the row image, where d*x, y represents the tangent plane to the surface at (x, y). The best fit of the tangent plane at (x, y) is obtained by the multiple regression method using the set of neighboring pixels χ (x, y). The neighborhood χ (x, y) is made up of pixels (x’, y’) situated within a 3x3 window, centred at (x, y) and with close depths (dx’, y’) according to a given threshold (Trh). The plane equation in a 3-D coordinate system may be expressed as follows:
z = ax + by + c |
(1) |
Where, (a, b, -1)T is a normal vector to the plane and
| (2) |
The quality of estimation according to the regression model is also computed:
| (3) |
The operations performed on the new image are based on the comparison
of two planes. Indeed, we consider that two planes: z = ax + by + c and
z = a’x + b’y + c’ are equal if they have, according to some thresholds,
the same orientation and the same distance to the coordinate origin. Let
v = (a, b, -1)T and v’ = (a’, b’, -1)T and let θ
be the angle between v and v’ and h the distance between the two planes:
Region growing by randomized region seed sampling: Inspired from the RANSAC algorithm (Fischler and Bolles, 1987), our region growing technique is based on random sampling of the region seeds. A generated seed is accepted if only the surface estimation quality q at this seed is greater than a given threshold Q. For every accepted seed, a region growing is performed by recursively including homogenous pixels situated on the borders of the region in growth. A given seed centred at (xt, yt) is formed by the pixels in a WxW window, belonging to the same plane. The seed quality is represented by the minimum of estimation qualities of pixels that form the seed. Selection-growing process is repeated until no new region can be created. Random sampling of region seeds allows to select the best seeds. These latter are characterized by a good quality. This leads to include in a given region the largest possible set of homogenous pixels. Indeed, several seeds within the same region can be generated; however none of these seeds is accepted. The first generated seed for which the quality q is greater than Q will be accepted and considered for region growing. The randomized growing algorithm is described as follows:
For each generated region Rl, the residual variance σl2 is calculated as follows:
| (4) |
Where, (al, bl, cl) are the plane equation coefficients of the region Rl. The residual variance will be used to normalize distances in fuzzy edge regularization stage. Note that in 2-D images, the variance σ2 depends only on the noise. Consequently, it is considered constant for all the regions of the image. However, in range images σ2 depends on both noise and surface orientation, regarding the plane of the range finder. Its value is proportional to the angle of the surface inclination.
IMPROVING IMAGE SEGMENTATION BY FUZZY EDGE REGULARIZATION
Image segmentation modeling as fuzzy pixel clustering: Fuzzy image segmentation is based on the theory of fuzzy sets, introduced by Zadeh in (1965). In fuzzy segmentation, regions of an image are considered as fuzzy sets for which, each pixel in the image has a grade of membership to every region. Note that in classical segmentation approaches, based on crisp clustering, at each time a pixel belongs exclusively to only one region of the image. Many fuzzy clustering algorithms have been used for pattern recognition; however, the well known algorithm FCM (Fuzzy C-Mean) (Bezdek, 1981) remains widely used in image segmentation (Baraldi and Blonda, 1999). FCM algorithm consists in partition of a set of N items represented by a set of feature vectors {p1, p2, …, pN}, into C clusters, represented by their prototypes {v1, v2, …, vC}, aiming at minimizing an objective function J defined as follows (Bezdek, 1981):
| (5) |
| D (vi, pj) | = | A certain distance between the item j and the center of the cluster i and uij is the membership grade of the item j to the cluster i. |
The parameter m represents the fuzzification factor, set to the typical value 2. The best classification according to the fuzzy clustering framework, is obtained by the calculation of the matrix U = [uij], i = 1…C; j = 1...N, which minimize the objective function J. So, at each iteration t of the FCM algorithm, the prototypes and the membership grades are updated as follows:
| (6) |
| (7) |
Iterations are repeated until convergence of J:
| (8) |
| ε | = | A certain threshold, set to 10–4 in our experimentations. |
Fuzzy classification of edge pixels: In our case, we run the FCM algorithm for every pair of adjacent regions. Let R1 and R2 two adjacent regions (C = 2) and let S the set of pixels that belong to the boundary between the two regions (Fig. 1). S is obtained by examination of all pixels belonging to the boundaries of the tow regions R1 and R2 and taking into account pixels with horizontal distance to one of the two regions, less than a given threshold (W pixels).
| (9) |
Let pj = (xj, yj, zj) εS and let vi = (ai, bi, ci) the prototype of the cluster i; i = 1, 2. The prototype of each cluster i is initialized by the barycenter ri of the region Ri as follows:
| Fig. 1: | Fuzzy cluster S, defined as the boundary between two adjacent regions |
| (10) |
| pik | = | (aik, bik, cik) the plane parameters at the pixel k of the region Ri. |
The distance between a pixel pj in S and the center vi of a region Ri is defined as follows:
| (11) |
After every iteration, the set S is partitioned into R’1 and R’2, as follows:
| (12) |
So, the new center ri of the region Ri; i = 1, 2 is calculated as follows:
| (13) |
The objective function is calculated regarding the sets R’1 and R’2:
| (14) |
At the convergence, each pixel of the set S is optimally close to one of the two adjacent regions, regarding the fuzzy objective function. After defuzziffication by using the Maxima method, crisp grades of membership are obtained and each pixel of the boundary is assigned to the corresponding region. The FCM algorithm is run for each pair of adjacent regions. Finally, all edges in the image are optimally regularized, regarding the fuzzy clustering method.
Labeling edge pixels, by taking into account the only involved adjacent regions has allowed to satisfy region continuity constraint. Indeed, without this constraint pixels in coplanar regions can be equally assigned to any of these regions, because they have the same distance to each one of them. According to our classification scheme, if we assume that the horizontal distance between two coplanar regions R and R’ is greater than W, pixels of R and those of R’ can not be in the same set S, which is formed of pixels close to the boundary between the regions R and R’.
RESULTS
Evaluation framework: Hoover et al. (1996) have proposed a dedicated framework for the evaluation of range image segmentation algorithms, which has been used in several related works (Jiang and Bunke, 1999; Jiang et al., 2000; Ding et al., 2005; Bab Hadiashar and Gheissari, 2006). The framework consists of a set of real range images and a set of objective performance metrics. It allows to compare a Machine-generated Segmentation (MS) with a manually-generated segmentation, supposed ideal and representing the Ground Truth (GT). The most important performance metrics are the numbers of instances, respectively of correctly detected regions, over-segmented regions, under-segmented regions, missed regions and noise regions. Region classification is performed according to a compare tool tolerance T; 50% <T≤100%, which reflects the strictness of the classification. The 40 real images of the ABW database are divided into two subsets: 10 training images and 30 test images. The training images are used to estimate the parameters of a given segmentation method. Using these parameters, the method is applied to the test images. The Performance metrics are computed and stored in order to be used to compare the involved methods. In our case, four methods, namely USF, WSU, UB and UE, (Hoover et al., 1996) are involved in the comparative study.
Parameter selection: Since the evaluation framework provides a set of training images with Ground Truth segmentation (GT), we have opted for a supervised approach for the estimation of parameters. For the proposed method, named FRIS for Fuzzy Range Image Segmentation, four parameters should be fixed: Trθ, Trh, W, Q. They represent, respectively the angle threshold, the depth threshold, the window size and the seed quality threshold. The performance criterion used in parameter selection is the average number of correctly detected regions with the compare tool tolerance T set to 80%.
About 256 combinations namely (Trθ, Trh, W, Q) ε {15°, 18°, 21°, 24°}x{12, 16, 20, 24}x{5, 7, 9, 11}x {0.90, 0.95, 0.97, 0.99}, were run on the training images. The threshold Trθ was set to 21°. Note that higher values of this parameter under-differentiate regions regarding their orientations and lead to an under-segmentation of the image. However, lower values over-differentiate regions and lead to an over-segmentation. It results in a high number of false and small regions, which should be merged in the true neighboring regions. The threshold Trh is set to 16. Values significantly greater than 16 can lead to inappropriate merging of some parallel overlapped regions. However, if Trh is significantly less than 16, highly sloping surfaces can not be detected as planar regions (Jiang and Bunke, 1999). This results in a high rate of missed regions. Parameters W and Q were set, respectively to 5 and 0.97. The selected value of W permits to estimate the plane equation by considering a wide neighborhood (W2 pixels), whereas Q ensure that the plane parameters are reliable and the window WxW is not located between two different regions.
Performance evaluation and comparison: Region growing by randomized region seed sampling has provided better results, compared to deterministic region growing (Fig. 2c and d). However, the resulting segmentation often remains unsatisfactory. In Fig. 2c, we can note that most of the edges are not well locally smooth, because pixels on the edges are not optimally assigned to the respective regions.
Figure 3 shows the impact of the fuzzy edge regularization on the segmentation results, with all the test images. The gap between the two curves shows that the segmentation results are significantly improved for the high values of the compare tool tolerance T. Indeed, edge regularization in range images allows to improve segmentation accuracy, by optimal labeling of pixels close to region boundaries. It was reported (Hoover et al., 1996; Jiang et al., 2000) that segmentation methods provide better results when they pay particular attention to process region boundaries.
Figure 4 shows the segmentation results of the image abw.test.8, with the compare tool tolerance T set to 80%. This image was considered as a typical image to compare the involved methods (Hoover et al., 1996; Ding et al., 2005). Figure 4a and b show, respectively the range image and the rendered image. Figure 4c, shows the ground truth segmentation, whereas Fig. 4d represents the segmentation result obtained by our method.
| Fig. 2: | Segmentation results (abw.test.3 image).
(a) Range image (b) Rendered range image (c) Segmentation result by
deterministic region growingand (d) Segmentation result by randomized
region growing |
| Fig. 3: | Comparison of average results obtained
by fuzzy clustering and crisp clustering of all the test images, according
to T |
Metrics in Table 1 show that all image regions detected by the best-referenced segmenter (UE) were detected by our method. The shadowed region has not been detected by any segmenter, due to high distortions in this region (Fig. 4b). The incorrectly detected regions are those with small sizes and situated on the horizontal support.
| Fig. 4: | Segmentation results of abw.test.8
image. (a) Range image (b) Rendered image (c) Ground truth segmentation
(GT) (d) Segmentation result |
| Fig. 5: | Average results of correctly detected
regions of all methods, according to the compare tool tolerance T;
50%<T≤100% |
Compared to the other methods, values of incorrect detection metrics are also good. Our method is equivalent to UE and scored higher than the others.
Table 2 shows the average results obtained with all test images and for all performance metrics. The compare tool tolerance was set to the typical value 80%. By considering both correct detection and incorrect detection metrics, obtained results show a very good efficiency of our method.
| Table 1: | Comparison results with abw.test.8 image for T = 80% |
| Table 2: | Average results of the different involved methods with T = 80% |
Figure 5 shows the average numbers of correctly detected regions for all test images and according to the compare tool tolerance T; Tε{51, 60, 70, 80, 90 and 95%}.
Results show that the number of correctly detected regions by our method is equivalent to UE and better than those of USF, UB and WSU. For instance, our method scored higher than WSU and UB for all the values of the compare tool tolerance T. It scored higher than USF for T≥60%. For all incorrect detection metrics (Over-segmentation, Under-segmentation, Missed, Noise), our method has equivalent scores to those of UE and USF. The two latter scored higher than UB and WSU. As summary, we can say that our approach has allowed to improve the segmentation results regarding the whole of the performance criteria of the evaluation framework. Especially for the average number of correct detection, which is the most important criterion, our approach has scored an equivalent value to the one of the UE algorithm. However, the average run time scored in our case (8 sec) is widely lower than the one scored with the UE algorithm (6.3 min).
CONCLUSIONS
In this study we have presented a range image segmentation method with fuzzy edge regularization. Region growing by randomized seed sampling, introduced in this work, provides an initial segmentation which should be refined. Obtained results with randomized region rowing are better than those obtained with deterministic region growing. The refinement of the initial segmentation using an adapted version of the FCM algorithm, has allowed improving significantly the segmentation results. Using regions obtained at the fist stage, has allowed to obtain the number and the initial centers of clusters. This has permitted a supervised classification with well initialized of the involved parameters. Several tests were performed on real images from the ABW database. Obtained results show a good potential of the proposed method for providing efficient and accurate range image segmentation. The proposed method can be extended to curved objects, by defining their specific surface proprieties.