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); k←k+1; until convergence.
3.
Assign
Ismoothed( xj(1), xj(2)
) = yk(3).
The window radius h
determines the resolution of the smoothing process:
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
>T2
:
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.
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.
.