Course Home
Administration
Syllabus
References
Lecture Notes
Readings
Assignments
Projects
Resources


Comments? Idea?























































































































































































































































































































































Edge Detection using Mean Shift Smoothing

Final project by

Edan Lerner


Introduction

Edges characterize boundaries, which define the important structural properties of an image. Therefore edge detection is a problem of fundamental importance in image processing; many tasks in image processing, to be performed successfully, depend on a reliable edge detection mechanism. Edges in images are areas with strong intensity contrasts - a jump in intensity from one pixel to its neighbor. One of the main obstacles to overcome in the edge detection task is the presence of noise, which is usually handled by filtering the image. The filtering process may lead to deterioration in edge detection quality, since it may reduce the intensity contrast along edges.

Mean shift smoothing is a filtering method, based on the mean shift clustering algorithm. Its advantage in comparison to the conventional filters is that it is an edge preserving process, i.e. the edges do not usually loose their contrast as a result of the process. In some cases mean shift smoothing might even amplify the edges' intensity contrast.

In this project an attempt was made to use the mean shift smoothing process to produce better edge detection results, compared to edge detection of images that are not preprocessed. Different cases were tested to better understand under which conditions this method seems to be efficient in the edge detection task, while special attention was given to the handling of noisy images.

 

Mean Shift Smoothing

Mean shift smoothing is based on a mathematical operation called the mean shift procedure. Given a data set {xi} in a d-dimensional Euclidean space Rd, and a window radius h, we first define the multivariate kernel density estimate:

For our discussion, we limit ourselves to the Epanechnikov kernel:

where cd is the volume of a unit d-dimensional sphere. A qualitative presentation of the density estimate function f(x) is given below, for a random 2-dimensional data set:

Random Data Set

f(x) (Qualitative)

 

Since the kernel KE(x) is differentiable, we can derive the mean shift vector based on the gradient of f(x):

where the region Sh(x) is a d-dimensional sphere of radius h, having the volume hdcd, centered at x, and containing nx data points (see [1] for detailed presentation). The mean shift vector has the direction of the density estimate‘s gradient at x, when obtained with the Epanechnikov kernel. Since it always points towards the maximum increase of density, it can define a path leading to a local density maximum.

We now define the mean shift procedure as computation of the mean shift vector Mh(x), and translation of the window Sh(x) by Mh(x):

A series of successive iterations of the mean shift procedure is guaranteed to converge, as proved in [1]. Different variations of clustering algorithms are formulated based on this convergence; applying the procedure iteratively on data points will “displace” them to high data point density regions, depending on their location. Data points belonging to the same cluster will then converge to the same areas.

 

The smoothing algorithm, based on the mean shift procedure:

Initialize data set

For each j = 1..n

1.                 Initialize k = 1 and yk = xj.

2.                 Repeat: Compute yk+1 using the mean shift procedure (5); kk+1; until convergence.

3.                 Assign Ismoothed( xj(1), xj(2) ) = yk(3).

 

The window radius h determines the resolution of the smoothing process:

Original Image:

 

 

 

 

 

 

 

 


Original Image:

 

 

 

 

 

 


Edge Detection Using Mean Shift Smoothing

The edge detector implemented computes the inputted image’s gradient amplitude estimation in the following manner:

 

 

Two threshold values are required for the edge detection process: T1 and T2. The following hysteresis process was then applied to the gradient amplitude estimate, using these threshold values:

Given: gradient amplitude estimation .

·                    Initialize all pixels of the edge map E as unlabeled.

·                    For each unlabeled pixel p:

·        If >T­2 :

Set Ep = EDGE;

For each immediate neighbor q of p:

          If > T1 set Eq = EDGE;

                   Else set Ep = NONEDGE;

          Till no remaining unlabeled pixels.

Output: Edge Map E(i,j).

 

Edge Detection Results:

1. glasses

 

No Smoothing

 

Smoothed

 


 

 

 

2. camera man

 

 

3. golf cart

 

 

 

 

 

 

No Smoothing

 

 

No Smoothing

 

 

 

 

 

 

Smoothed

 

 

Smoothed

 


 

4. sculpture

No Smoothing

Smoothed

 


 

5. noisy sculpture

No Smoothing

Smoothed

 


 

6. noisy object

 

No Smoothing

Smoothed

 


 

Discussion

The initial idea for this project was a simpler implementation of an edge detector using a clustering algorithm: The data points were to be clustered and assigned labels. Pixels were to be set as edges if their corresponding data points were located on the boundary of two or more clusters, i.e. if a pixel has a different label than one or more of its neighbors, it is set to be an edge pixel. This policy did not prove itself as useful for two main reasons: It has almost no ability to handle objects that have strong variance in their shading. Furthermore, for entire objects to be labeled as one cluster, very large values of the parameter h are required, which has a major influence on running time – due to the scanning of a square range of h × h for each pixel in the clustering process
( O(h2) per iteration, per pixel ).

After this policy was tested and found to be unsuccessful, the adjustment to only smoothing the image using the mean shift clustering iteration was made. As one can notice in the presented images, the mean shift smoothing can lead to good results in cases in which Gaussian noise is present (cases 5 and 6), as well as in cases in which the smoothing amplifies the contrast along edges (cases 1 and 4).  However, it is possible that the smoothing somewhat deteriorates the edge detection, as noticeable in case 3.

Problems:

·        RUNNING TIME. 300 X 300 pixels image, with h ~ 20: 30 minutes on a household PC…

·        Many parameters involved: h, T1, T2, ε.

·        Doesn’t always improve edge detection. In some cases even produces poor results in comparison to edge detection without the smoothing process.

Some ideas for improvements:

·        Manipulation of the rescaling process - For this project, it was decided to attempt to create a data point set that has no preference of a specific component of the vectors, as much as possible. It might be interesting to let the user set the desired scale for the intensity component of the created data set.

·        Dynamically choosing threshold values - breaking down the image to regions, according to some criteria, and producing the threshold values as a function of the gradient amplitude estimation in that region.

 

Source Code

          To use the program to process images, they are required to be in the .pgm format. The program outputs edge maps in the .pbm format. Both of these formats can be converted from any image format using Irfanview (freeware). The program also needs the definitions file to work properly. All processed files should be placed in the same directory as the executable.

·                    edge.c

·                    definitions.h

Running time can be problematic when processing images with the program. One should make sure the image size isn’t too big. Reasonable image sizes range around the 300 × 300 pixels, while the smaller the image, the faster the computation.

Useful Links & Misc.

·                     A user friendly multi-format image program, to view the .pgm and .pbm files that the edge.c program produces (freeware): IrfanView.

·                     GCC – free C compiler for windows.

·                     Computational Vision 2005 course page.

·                     Class presentation – PowerPoint, pdf.

·                     Edge Detection using Mean Shift Smoothing – Paper.

 

References

[1]        D. Comaniciu, P. Meer: Distribution Free Decomposition of Multivariate Data, (Invited), Pattern Analysis and Applications, Vol. 2, 22-30, 1999

 

[2]        Lecture Notes from “Introduction to Computational and Biological Vision” at:

http://www.cs.bgu.ac.il/~ben-shahar/Teaching/Computational-Vision/LectureNotes.php.

 

.