CSE/EE 585: Digital Image Processing II

Computer Project Report #2

Image Segmentation

Group: Anirudh Modi, Shin Chin and Ming Ni

Date: April 28th, 2000
A. Objectives
The goal of this project was to design, implement and test one of several region based segmentation algorithms on a set of images.  In our work, we adopted an approach based on "Edge Flow: A Framework of Boundary Detection and Image Segmentation" by W. Ma and B. Manjunath, Proc. IEEE CVPR, June 1997.
B. Methods
I. Introduction
Edge detection and image segmentation is a crucial initial step in most computer vision applications before performing high-level tasks such as object recognition and scene interpretation.  In the edge flow approach, the detection and localization of edges are performed first by identifying a flow direction at each pixel location that points to the closest boundary; then followed by the detection of locations that encounter two opposite directions of edge flow. The method based on edge flow has several salient features to solve this general problem:
a. Use a predictive coding model for identifying and integrating the different types of image boundaries;
b. Boundary detection is based on a flow field propagation;
c. Very few free parameters that control the segmentation are needed.  This makes the method more appropriate for large image datasets.
II. Algorithm and Implementation Details
All the processing mentioned below were implemented with C++ programs which can be found in the Appendix. The program can be used to segment all kinds of size and format images(gif, jpeg, pgm, .....) as input and output. We summrize the most important part of the  implementation algorithm as the following. Our program is based on these definition and equations.
1. Definition of the Edge Flow
Edge flow vector F at image location s with an orientation ø as:
,
E(s, theta): the edge energy at location s along the orientation theta.
P(s, theta): the probability of finding the image boundary if the corresponding flow at location s "flow" in  the direction theta.
P(s, theta + pi): the probability of finding the image boundary if the corresponding flow at location s flows backwards.
 

2. Intensity Edge Flow

To compute E(s,theta),  the original image I(x, y) is smoothed by with a Gaussian kernel and the result is an image at a given scale s as Isigma(x, y).  The scale parameter will control both the edge energy computation and the local flow direction estimation, so that only edges larger than the specified scale are detected. The edge flow energy E(s,theta) at scale sigma is defined to be the magnitude of the gradient of the smoothed image Isigma(x, y) along the orientation, which can be computed as: | where s = (x, y).  This edge energy indicates the strength of the intensity change.
To compute P(s, theta), two possible flow direction (theta and theta+pi) are considered for each of the edge energy along the orientation theta at location s.The prediction toward the surrounding neighbors in the two directions can be computed as:
,
where d is the distance of the prediction and it should be proportional to the scale at which the image is being analyzed.The probabilities of edge flow direction are assigned to be in proportion to their corresponding prediction errors:
.

3. Texture Edge Flow

The texture features are extracted based on a Gabor decomposition. The basic idea is to decompose images into multiple oriented spatial frequency channels, and the channel envelopes (amplitude and phase) are used to form the feature maps.
The complex Gabor filtered image are:
where, N is the total number of filters,  is the magnitude, and  is the phase. A texture feature vector can be formed as:
.
The texture edge energy, which measures the change in local texture information, is given by:
,
where  and  is the total energy of the sub band i.( = SUM(i)|wij|)
The direction of texture edge flow can be estimated using the prediction error:
 
.

4. Edge Flow Integration

Combining different types of edge flows:
The edge flows obtained from different types of image attributes can be combined together to form a single edge flow for general-purpose boundary detection:
with ,
where  and  represent the energy and probability of the edge flow computed from image attribute a where a belongs to {intensity/color, texture, and phase}. w(a) is the weighting coefficient among various types of image attributes.

Combining different directions of edge flows:
After we have edge flows , we first identify a continuous range of flow directions which maximizes the sum of probabilities in that half plan:

.

Then, the final resulting edge flow is defined to be the vector sum of the edge flows with their directions in the identified range, and is given by :

,
where F(s) is a complex number with its magnitude representing the resulting edge energy and angle representing the flow direction.
 
5. Edge Flow Propagation and Boundary Detection
After the edge flow F(s) of an image is computed, boundary detection can be performed by iteratively propagating the edge flow and identifying the locations where two opposite direction of flows encounter each other. At each location, the local edge flow is transmitted to its neighbor in the direction of flow if the neighbor also has a similar flow direction. The algorithm is as following:
(1) Set n = 0 and .
(2) Set the initial edge flow at time n+1 to zero.
(3) At each image location s = (x, y), identify the neighbor s' = (x', y') which is in the direction of edge flow , i.e., .
(4) Propagate the edge flow if , ; otherwise, .
(5) If nothing has been changed, stop the iteration.Otherwise, set n = n+1 and go to step 2.
 
  • 6. Boundary Connection and Region Merging
  • For each open contour, we associate a neighborhood search size proportional to the length of the contour. This neighborhood is defined as a half circle with its center located at the unconnected end of the contour.
  • The nearest boundary element which is within the half circle is identified.
  • If such a boundary element is found, a smooth boundary segment is generated to connect the open contour to the nearest boundary element.
  • This process is repeated few times (2 or 3) till all salient open contours are closed.
  • At the end, a region merging algorithm is used to merge similar regions based on a measurement that evaluates the distances of region color and texture features, the size of regions, and the percentage of original boundary between the two neighboring regions. This algorithm sequentially reduces the total number of regions each time by checking if the user's preferred number has been approached to the best extent. [Note: This part was not completed in our implementation because of time constraints]
    • C. Results and Observations
    Our algorithm was applied to a large number of different kinds of images. They include
        (i)      Synthetic images with little or no texture.
        (ii)     Natural or real  images with little or no texture.
        (iii)    Synthetic images with significant texture
        (iv)    Natural or real images with significant texture
        (v)    Miscellaneous images (includes those mentioned above)
    Although, we were not able to implement the region merging algorithm due to time constraints, we obtained significantly good results from the edgeflow implementation. These results can be enhanced by the use of a proper region merging algorithm, and are essential for actual segmentation of the images.
    (i) Example results of synthetic images with no texture

    Original Image

    Segmentation

    Final Segmented Image
    In figure <rgbwhite.gif> ,  we see an image consisting of the words 'R', 'G'and 'B' in a white background. This image has no texture.
    We used sigma values of 2, 3 and 4 as well as 8 number of orientations.
    As you can see the application of our algorithm yields very good segmentation.
    Each of the words 'R','G' and 'B' were completely segmented out of the white background.
    For this case, we used only intensity edge flow.  (see more detail)

     

    Original Image

    Segmentation

    Final Segmented Image
    In the above figure with the wheel, we have an example of a synthetic image with no texture. Although it may be segmented well with histogram based segmentation, it is a good test case for the edge flow algorithm. As you can see in the above figure, the different parts of the wheel are very well segmented with our edge flow algorithm.

     
     

    Original Image

    Segmentation

    Final Segmented Image
    The above figure shows an image of a wheel corrupted with white additive Gaussian noise. This is an example of a synthetic image with noise. Our edge flow algorithm segments out the various parts of the wheel very well.

     

    Original Image

    Segmentation

    Final Segmented Image
    In figure <spherel.gif>, we see a sphere with smooth change of contrast at the edges. This is not a trivial case to segment using simple edge detection. However, our edge flow algorith managed to successfully segment the sphere from the surroundings.
    (ii) Example result of natural image with little texture
    Original Image

    Segmentation

    Final Segmented Image
    In figure <flower1.gif>  we see an image of a yellow flower in a background of leaves. This real image has little texture.
    The applictaion of our edge flow algorithm yields very good segmentation.
    The yellow flower was completely segmented out of the background.
    For this case, histogram based segmentation may work well but for the edge flow method, it is more complicated. (see more detail)
    Original Image

    Segmentation

    Final Segmented Image
    In figure <anirudh.gif>,  we see a typical photograph. Although the image has little texture, but it has significant detail which makes it a good candidate to test our implementation with. As can be seen, the results obtained are quite good (lacking only in the region closing and merging aspects of the implementation). (see more detail)
    (iii) Example result of synthetic image with texture

    Original Image

    Segmentation

    Final Segmented Image
    In figure <ucsb.gif> we see an image of the words 'U', 'C', 'S' and 'B' with texture in a white background.
    This is not a trivial case to segment due to the texture.
    The texture consists of black and white lines running at a slanted angle through the words.
    We used 8, 10 and 12 orientations with sigma values of 2, 3 and 4.
    Our edge flow algorithm satisfactorily segments each of the words 'U','C', 'S' and 'B' out of the white background.
    The best cases were 12 orientations and sigma values of 3 and 4. (see more detail)

    Original Image

    Segmentation

    Final Segmented Image
    In figure <boxtext.gif>, we see an example of a synthetic image with significant texture. The texture consists of two square textures with similar intensities, one inside the other, which makes it a difficult edge detection problem. However, our implementation worked well for this case, and we got the boundaries as expected. The boundary is not closed due to a bug in our region closing algorithm, something that can be corrected with additional effort.


           (iv) Example result of real/natural image with significant texture
     


    Original Image

    Segmentation

    Final Segmented Image
    In figure <garden.gif> we see an image of a flower garden.
    This image has significant texture consisting of the red flowers in the middle, the white flowers and the green grass.
    We used 8, 10 and 12 orientations with sigma values of 2, 3 and 4.
    Our edge flow algorithm successfully segments out the red flowers from the surrounding white flowers and the white
    flowers from the green grass. The best case has the number of orientations to be 12 and sigma equals to 4. (see more detail)

    Original Image

    Segmentation

    Final Segmented Image
    In figure <beansgray.gif> we see an example of a natural image with lots of texture.
    The texture consists of different types of beans.
    We get good segmentation for 12 orientations and sigma equals 4 in our edge flow algorithm.
    When sigma=2, we get lots of noise. As sigma increases to 3 then 4, the noise reduces and the segmentation is better.(see more detail)

    Original Image

    Segmentation

    Final Segmented Image
    In figure <mandrill.gif> we see an example of a natural image with lots of texture. The texture consists of fur on the face of the Mandrill with a smooth gradation which seems difficult to segment. Again, the best edge detection is observed for the case of sigma = 4 and 12 orientations. (see more detail)
    It should be noted that the segmentation performance varies significantly depending on certain parameters supplied. Among them, the value of sigma has the maximum impact, and should be chosen appropriately by the user for a given image (or class of images). For images requiring segmentation of small scale structures (e.g., each individual bean in the beansgray.gif image discussed above), a small value of sigma should be used (typically 1-2 pixels). On the other hand, for a image requiring segmentation of larger structures (e.g., the nose of the mandrill above), a larger value of sigma should be used (typically 3-5 pixels). Also, the number of orientations should be chosen appropriately. The larger the number of orientations, the better is the resolution (or sampling), and hence better is the performance of the method. However, one cannot use a large value for this parameter, as the runtime of the program is proportional to this parameter (unlike sigma which has no impact on the runtime performance of the algorithm). For most practical purposes, a value of 8-16 is widely used. We tested all our runs for 8, 10 and 12 number of orientations. An appropriate threshold value for filtering the noise from the edge-flow intensity matrix also needs to be supplied. Any edge with strength below this threshold value is ignored. Although our implementation is very general, and allows the user to control this parameter, the default value of 0.004 (specific to our implementation) works well for most of the cases we studied. Another thing to note: for some images without any texture information (e.g., rgbwhite.gif or cleanwheel.gif), the texture flag can be turned off thus saving significant runtime while getting almost equally good results (since the texture edge flow takes 80% of the runtime).
    A statistical/graphical analysis of our results for this study is very difficult to present, since there are no known algorithms to study the quality of segmentation produced (since in fact, that is what this implementation is trying to achieve in a way). Human eye is the best judge for such results. Other than the idea and justification of the theory behind the implementation, and the observation based on the results presented above, there is little else we can say about the performance of the algorithm.


    D. Conclusions:

    The Edge Flow algorithm has been successfully and efficiently implemented and tested. It has been found that the algorithm is very general and is well-suited for all kinds of images, right from those with simple structures without any texture to those with very complicated textures. It allows the segmentation of any image as desired, with the specification of only one significant parameter, sigma, which is supplied by the user This parameter too can be fixed a-priori for certain class of images and segmentation type required, thus minimizing user interaction which is a significant advantage in automatic image recognition and segmentation. (remember: the other parameter, number of orientations, is generally fixed, and is dictated by the computational resources available today, and is typically the maximum tolerable value).
    Among the drawbacks, the algorithm is fairly complex and cumbersome to implement with a lot of minute details missing, and is also computationally very expensive. The region closing algorithm, although very sparsely dealt in the paper, seems to be fairly complex, and there are a lot of special cases needed to be handled (e.g., one has to be careful that the closing doesn't cut through other boundaries, or if it does, it splits all the boundaries accordingly). Owing to the limited time constraints and the complexity of the Edge Flow portion of the algorithm, much time could not be spent on this portion of the project, hence the results leave a lot to be desired.
    E. Links to all the graphs/results:
    F. Links to the Source Code: