Ef7df6b94ad2d5ccf5c4714be1f98c54b69e [625530]

252 IEEE TRANSACTIONS ON SYSTEMS, MAN,AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 32, NO. 3, AUGUST2002
Gaussian-Based Edge-Detection Methods—A Survey
Mitra Basu , Senior Member, IEEE
Abstract— The Gaussian filter has been used extensively in
image processing and computer vision for many years. In thissurvey paper, we discuss the various features of this operator thatmake it the filter of choice in the area of edge detection. Despitethese desirable features of the Gaussian filter, edge detectionalgorithms which use it suffer from many problems. We will re-view several linear and nonlinear Gaussian-based edge detectionmethods.
Index Terms— Adaptive techniques, edge detection, edge local-
ization, Gaussian filter, multiscale analysis.
I. INTRODUCTION
THE purpose of this paper is to present a survey of
Gaussian-based edge detection techniques. The detection
of edges in an image has been an important problem in imageprocessing for more than 50 years. In a gray level image, anedge may be defined as a sharp change in intensity. Edge de-
tection is the process which detects the presence and locations
of these intensity transitions. The edge representation of animage drastically reduces the amount of data to be processed,yet it retains important information about the shapes of objects
in the scene. This description of an image is easy to integrate
into a large number of object recognition algorithms used incomputer vision and other image processing applications.
Over the years, many methods have been proposed for de-
tecting edges in images. Some of the earlier methods, such as
the Sobel and Prewitt detectors [27], [30], used local gradientoperatorswhichonlydetectededgeshavingcertainorientationsand performed poorly when the edges were blurred and noisy.
It should be mentioned here that one can combine such direc-
tional operators to approximate the performance of a rotation-allyinvariantoperator.Sincethen,moresophisticatedoperatorshave been developed to provide some degree of immunity to
noise, to be nondirectional,
1and to detect a more accurate lo-
cation of the edge. The majority of these are linear operatorsthat are derivatives of some sort of smoothing filter. Shen andCastan[33]usedasymmetricalexponentialfilterinedgedetec-
tion.However,sinceitwasoriginallyproposedbyMarrandHil-
dreth in1980 [23],theGaussianfilterisbyfar themost widelyusedsmoothingfilterinedgedetection.Thereasonsforthisarepresented later in this paper.
Since the Gaussian filter is so commonly used, in this paper
we review several Gaussian-based edge detection techniques.
Manuscript received July 28, 2000; revised June 1, 2002 and July 1, 2002.
This work was supported by a grant from the NSF CDA-9114481. This paper
was recommended by Associate Editor V. Murino.
The author is with the Department of Electrical Engineering, The City Col-
lege of New York, New York, NY 10031 USA(e-mail: [anonimizat]).
Digital Object Identifier 10.1109/TSMCC.2002.804448
1Thisisnotnecessarilyadesirableproperty,sinceinformationonedgedirec-
tion is usually needed by high-level processes.Ourgoalisnottogiveanexhaustiveinventoryofedgedetection
algorithms. Other surveys of edge detection may be foundin [24], [40], and [41]. In Section II, we outline some of the
major problems encountered during an edge detection process.
SectionIIIdiscussesthefeaturesoftheGaussianfilterthathavecontributed to its popularity in edge detection. In Section IV,we present a discussion of the two most well-known Gaussian
edge operators: 1) the Marr-Hildrethdetector and 2) the Canny
detector. We also review several other detectors that havedeveloped in more recent years. A brief summary is given inSection V.
II. P
ROBLEMS OF EDGEDETECTION
The separation of a scene into object and background is an
essential step in image interpretation. This is a process that is
carried out effortlessly by the human visual system, but whencomputer vision algorithms are designed to mimic this action,several problems can be encountered. This section describes
someoftheproblemsinvolvedindetectingandlocalizingedges.
Due to the presence of noise and quantization of the original
image, during edge detection it is possible to locate intensitychangeswhereedgesdonotexist.Forsimilarreasons,itisalso
possible to completely miss existing edges. The degree of suc-
cess of an edge-detector depends on its ability to accurately lo-cate true edges.
Edgelocalizationisanotherproblemencounteredinedgede-
tection.Theadditionofnoisetoanimagecancausetheposition
of the detected edge to be shifted from its true location. Theabilityofanedge-detectortolocateinnoisydataanedgethatisascloseaspossibletoitstruepositionintheimageisanimpor-
tant factor in determining its performance.
Another difficulty in any edge detection system arises from
the fact that the sharp intensity transitions which indicate anedge are sharp because of their high-frequency components.
As a result, any linear filtering or smoothing performed on
these edges to suppress noise will also blur the significanttransitions. However, some form of smoothing is necessarysince edge detection depends on differentiating the image
function and this amplifies all high-frequency components of
thesignal,includingthoseofthenoise.Low-passfiltersarethemost widely used smoothing filters. The amount of smoothingapplied depends on the size or scale of the smoothing operator.
In general, for a small scale, the detector extracts fine details
of intensity changes from the image, but tends to be moresensitive to noise. A larger scale extracts coarse details ofintensity changes, but some of the detected edges tend to have
a large localization error. Selecting a single scale of smoothing
which is optimal for all edges in an image is very difficult.One filter size may not be good enough to remove noise whilekeeping good localization.
1094-6977/02$17.00 © 2002 IEEE

BASU: GAUSSIAN-BASED EDGE DETECTION METHODS—A SURVEY 253
Multiscaleedgedetectionoffersanalternative.Thisinvolves
applyingsmoothingoperatorsofdifferentsizestoanimage,ex-tracting the edges at each scale, and combining the recovered
edge informationto formamorecompletepictureof theactual
edgerepresentationoftheimage.Thebasicpremiseofthistech-niqueisthatdifferentpartsofanimagehavevaryingdegreesofnoisiness and types of edges; therefore, each part of the image
needs to be smoothed differently. However, there are problems
associatedwiththistechnique,namely,howmanyfiltersshouldbe used, how to determine the scales of the filters, and how tocombine the responses from each filter so as to create a single
edge map.
III. S
IGNIFICANCE OF THE GAUSSIANFILTER
The most widely used smoothing filters are Gaussian filters.
Such filters have been shown to play an important role in edgedetectioninthehumanvisualsystem,andtobeextremelyusefulasdetectorsforedgeandlinedetection.MarrandHildreth[23]
demonstratedthat the Gaussianfilter(along withthe Laplacian
operator) is very similar to the difference of Gaussians (DOG)filter.Thisisawell-knownapproximationtotheshapeofspatialreceptive fields in the visual system of cats that has also been
proposedforhumans.Byvariationalmethods,Canny[7]derives
an optimal edge detection operator which turns out to be well-approximated by the first derivativeof a Gaussian function.
Babaudet al.[2] proved that when one-dimensional (1-D)
signals are smoothed with a Gaussian filter, the scale spacerepresentation of their second derivatives shows that existingzero-crossings disappear when moving from a fine-to-coarse
scale, but new ones are never created.
2They also proved that
forawidecategoryofsignals,theGaussianfunctionistheonlyfilter that has this property. This unique property makes it pos-sible to track zero-crossings over a range of scales, and also
givestheabilitytorecovertheentiresignalatsufficientlysmall
scales. Yuille and Poggio [39] extended this work to two-di-mensional (2-D) signals and proved that with the Laplacian,the Gaussian function is the only filter in a wide category that
does not create zero-crossings as the scale increases. They also
showed that for nonlinear directional derivatives along the gra-dient,thereisnofilterthatdoesnotcreatezero-crossingsasthescale increases.
Another important property of the Gaussian filter is that it is
the only operator that satisfies the uncertainty relation
(1)
where andareitsvarianceinspatial andfrequencydo-
mains,respectively.ThispropertyallowstheGaussianoperator
togivethebesttradeoffbetweentheconflictinggoalsofthelo-
calization in spatial and frequencydomains simultaneously.
The 2-D Gaussian filter is also the only rotationally sym-
metric filter that is separable in Cartesian coordinates. Sepa-
rability is important for computational efficiency when imple-menting thesmoothingoperationby convolutionsinthespatialdomain.
2This ensures that no new features are introduced by the edge-detection
process and image integrity is maintained.IV. GAUSSIAN-BASEDEDGEDETECTION TECHNIQUES
MarrandHildreth[23]originallyproposedthespatialcoinci-
denceassumptionwhichledtotheideaofmultiscaleedgeanal-
ysis. Having observed that significant intensity changes occur
atdifferentscaleswithinanimage,theyconcludedthatoptimaldetection of these changes would require the use of a filter thatoperatesatseveraldifferentscales.Theyfurtherarguedthatthe
edge maps of the different scales each contained important in-
formationaboutphysicallysignificantphenomena.Ifanedgeispresentatseveraldifferentscales,thenitrepresentsthepresenceof an image intensity change due to a single physical phenom-
enon.Ifanedgeispresentatonlyonescale,thenitmaybethat
two independent physical phenomena are operating to produceintensitychangesinthesameregionoftheimage.However,thisassumption is mainly based on intuition and some aspects of it
still remain open for further research.
Marr and Hildreth also argued that the optimal smoothing
filter for images should be localized in both spatial and fre-quency domains, thereby satisfying the uncertainty relation
givenin(1).ConsidertheGaussianoperatorintwodimensions
given by
(2)
whereis the standard deviation of the Gaussian function and
aretheCartesiancoordinatesoftheimage.MarrandHil-
dreth suggested that by applying Gaussian filters of differentscales
to an image, a set of images with different levels of
smoothnesscanbeobtained.Todetecttheedgesintheseimages
it isnecessary tofind thezero-crossings of their secondderiva-tives.MarrandHildrethachievedthisbyusingtheLaplacianofa Gaussian (LOG) function as a filter
(3)
This is an orientation-independent operator and its scale is
given by . It breaks down at corners, curves, and at locations
where image intensity function varies in a nonlinear manneralong an edge [6]. As a result of the breakdown, the true po-sition of the edge is not reported by the detector.
The Marr-Hildreth operator formally introduced Gaussian
filter into the edge-detection process with so-claimed sup-
port from the biological vision. This is a turning point inthe low-level image processing research area. The newly
introduced concept multiscale/multiresolution came to play
an important role in the entire image processing area andinjected sophisticated mathematical techniques (e.g., varia-tional approach, nonlinear partial differential equations) into
the segmentation problem. It initiated three distinct research
endeavors:
1) agroupofresearchersdirectedtheireffortstoanalyzeand
improve Marr-Hildreth operator within the umbrella of
linear constraints;
2) a second group focused on biological vision to achieve
performance comparable to that of mammalian visual
system;

254 IEEE TRANSACTIONS ON SYSTEMS, MAN,AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 32, NO. 3, AUGUST2002
3) yet another group moved into nonlinear domain.
Therestofthispapersummarizeseffortsofresearchersfrom
each group in the order mentioned above.
It has been found that zero-crossings are only reliable in lo-
cating edges if they are well separated and the signal-to-noiseratio (SNR) in the image is high. An analytical study of the re-sponseofthe1-DsecondderivativeoftheGaussianedgeoper-
atoronidealinfinite-widthstepandrampedgesandfinite-width
stepandstaircasestepedgesisreportedin[32].Itisshownthatforidealstepandrampedges,thelocationofthezero-crossingisexactly at the location of the edge. However, the location shifts
from the true edge location for the finite-width case. This shift
is a function of the standard deviation
of the Gaussian. The
otherproblemisthedetectionoffalseedges.Thereasonisthatzero-crossings correspond to local maxima and minima in the
firstderivativeofanimagefunction,whereasonlylocalmaxima
indicate the presence of real edges [8], [22]. LOG filtered im-ages also suffer from the problem of missing edges—edges inthe original image may not have corresponding edges in a fil-
teredimage.Inaddition,itturnsouttobeverydifficulttocom-
bine LOG zero-crossings from different scales, primarily be-cause of the following [28]:
1) a physically significant edge does not match a zero-
crossing for more than a few and very limited number ofscales;
2) zero-crossings in larger scales move very far away from
thetrueedgepositionduetopoorlocalizationoftheLOG
operator;
3) therearetoomanyzero-crossingsinthesmallscalesofa
LOG filtered image, most of which is due to noise.
Relating image structures across scale is intrinsically prob-
lematic since, zero-crossings merge tangentially. Thus, one
cannot rely upon zero-crossings to track edges. Edge-linking
algorithms based on this approach will remain heuristic innature. Furthermore, physiological experiments have found noevidence to support zero-crossings as a model for biological
vision.
Haralick[14]proposedtheuseofzero-crossingofthesecond
directional derivative of the image intensity function. This istheoretically the same as using the maxima in the first direc-
tionalderivatives,andinonedimensionisthesameastheLOG
filter.
Canny [7] developed an operator that has also become a
standard gauge in edge detection. His technique is based on
optimizing three criteria desired for any edge detection filter:
good detection, good localization, and only one response toa single edge. For good detection, the probability of falsedetectionshoulddecreasewithincreasingSNR.TheSNRatan
edge point is given by
(4)
where
optimal operator;
the edge;
root mean squared value of the noise.Itisassumedthattheoptimalfilterhasafiniteimpulseresponse
bounded by .
Forgood localization, the expression to be maximized is
Localization
(5)
where is the derivative of .
The criterion for eliminating multiple responses to a single
edge is designed to minimize the number of spurious maximawithin the operator’s spatial extent. The expression for the dis-tance between adjacent maxima of the filter output in response
to noise is
(6)
Fixing the constant to be as large as possible results in the
distance between spuriousmaxima beingas greatas possible.
In order to simplify the analysis for step edges, Canny com-
puted the function so that the localization is maximized
while keeping the single response criterion constant. By varia-tional methods, he derived a set of filters corresponding to var-ious values of the single response criterion. Canny showed that
for a 1-D step edge, the derived optimal filter can be approxi-
mated by the first derivative of a Gaussian function with vari-ance
(7)
In two dimensions, his edge-detector uses two filters repre-
senting derivatives along the horizontal and vertical directionstooptimallydetecttheedgesinanimagewithadditiveGaussianwhitenoise.Canny’soperatorisnotuniqueasitvarieswiththe
edge profile (e.g., step edge or ramp edge). However, for step
edges,Canny’soptimaloperatorissimilartotheLOGoperatorbecause the maxima in the output of a first derivative operatorcorrespondstothezero-crossingsintheLaplacianoperatorused
by Marr and Hildreth.
Canny also proposed a scheme for combining the outputs
from different scales. His strategy is fine-to-coarse and themethod is called feature synthesis . It starts by marking all
the edges detected by the smallest operators. It then takes the
edges marked by the small operator in a specific direction andconvolves them with a Gaussian normal to the edge directionof this operator so as to synthesize the large operator outputs.
It then compares the actual operator outputs to the synthesized
outputs. Additional edges are marked if the large operatordetects a significantly greater number of edges than what is
predicted by the synthesis. This process is then repeated to
mark the edges from the second smallest scale that were notmarked by the first, and then to mark the edges from the thirdscalethat werenotmarked by eitherof thefirst two,andso on.
Inthisway,itispossibletoincludeedgesthatoccuratdifferent
scales even if they do not spatially coincide.
Canny’s edge-detector uses adaptive thresholding with hys-
teresis to eliminate streaking of edge contours. Two thresholds
are involved, with the lower threshold being used for edge ele-
mentsbelongingto edgesegmentsalreadyhavingpoints above

BASU: GAUSSIAN-BASED EDGE DETECTION METHODS—A SURVEY 255
the higher threshold. The thresholds are set according to the
amount of noise in the image, which is determined by a noiseestimation procedure.
The problem with Canny’s edge detection is that his algo-
rithmmarksapointasanedgeifitsamplitudeislargerthanthatof its neighbors without checking that the differences betweenthispointanditsneighborsarehigherthanwhatisexpectedfor
randomnoise.Histechniquecausesthealgorithmtobeslightly
moresensitivetoweakedges,butitalsomakesitmoresuscep-tible to spurious and unstable boundaries wherever there is aninsignificant change in intensity (e.g., on smoothly shaded ob-
jects and on blurred boundaries).
In[31],Schunckintroducesanalgorithmforthedetectionof
step edges using Gaussian filters at multiple scales. The initialstepsofSchunck’salgorithmarebasedonCanny’smethod.The
algorithmbeginsbyconvolvinganimagewithaGaussianfunc-
tion. The gradient magnitude and gradient angle are then com-putedforeachpointintheresultingsmootheddataarray. Next,the gradient ridges in the results of the convolution are thinned
usingnonmaximasuppression.Then,thethinnedgradientmag-
nitudes are thresholded to produce the edge map.
Multiresolution edge detection is incorporated by repeating
the steps above for several scales of the Gaussian filter. The
gradient magnitude data at the largest scale will contain large
ridges which correspond to the major edges in the image. Asthe scale decreases, the gradient magnitude data will containan increasing number of ridges, both large and small. Some of
thesecorrespondtomajoredges,sometoweakeredges,andthe
restareduetonoiseandunwanteddetails.Thegradientmagni-tudesoverthechosenrangeofscalesaremultipliedtoproduceacomposite magnitudeimage. Ridges that appear at thesmallest
scale and correspond to major edges will be reinforced by the
ridges at larger scales. Those that do not will be attenuated bytheabsenceofridgesatlargerscales.Therefore,inthecombinedmagnitudeimage,theridgesthatcorrespondtomajoredgesare
much higher than the ridges that do not. Nonmaxima suppres-
sionisthenperformedusingsectorsobtainedfromthegradientangle of the largest filter.
Schunck’s algorithm chooses the width of the smallest
Gaussianfilterto bearound
, andthefilters thatareused
differ in width by a factor of two. However, he did not discusshow to determine the number of filters to use. In addition, bychoosing such a large size for the smallest filter, Schunck’s
technique loses a lot of important details which may exist at
smaller scales.
Witkin [37] was one of the first to study the property of
zero-crossings across scales for 1-D signals. The signal is first
smoothed by a Gaussian filter of varying
. The idea is to
examine the smoothed signal at various scales. The zero-cross-ings of the second derivative are marked. This representationknown as the scale-space representation of a signal contains
the location of a zero-crossing at all scales starting from the
smallest scale to the scale at which it disappears. Witkin’swork initiated the study of edge detection as a function ofscale. The knowledge form these studies is used by various
researchers to propose algorithms to combine edges for better
edge detection. Bergholm [5] proposed an algorithm whichusestheGaussianfilterandcombinesedgeinformationmovingfromacoarse-to-finescale.Hismethodiscalled edgefocusing,
and uses a rule-based approach for detecting local features andfortrackingandpredictingapossiblescaleparameter.Boththe
Marr-Hildreth and Canny edge-detectors are possible schemes
that can be used in edge focusing.
TheimageisfirstsmoothedwithalargescaleGaussianfilter
and then the edge detection process is performed using adap-
tive thresholding. Assuming that edge contours rarely move by
more than two pixel for a unit change in the scale parameter,the exact location of the edges is determined by tracking themoverdecreasing scales. Therefore, the results from one scale of
theedge-detectorisusedtopredictthelocationsofedgesinthe
next, smaller, scale.
The idea behind edge focusing is to reverse the effect of the
blurring caused by the Gaussian operator. Blurring is not a de-sired feature as it results in poor edge localization. It is simply
used as a means of removing the noise and other unnecessary
features.Themostobviouswayofundoingtheblurringprocessis to start with edges detected at the coarse scale and graduallytrackorfocustheseedgesbacktotheiroriginal locationsinthe
fine scale.
Thereareseveralproblemsassociatedwithedgefocusing,the
foremostbeinghowtodeterminethestartingandendingscalesoftheGaussianfilter.Bergholmsuggeststherange
forthemaximumscale,butdidnotspecifyaminimumscale.Healsodidnotdiscussindetailhowtochoosethethresholdwhichis used at the coarsest level, and this is a parameter which iscritical in determining how well the algorithmperforms. If it is
too high, a number of true edge points will be eliminated right
from the start. If it is too low, the output of the edge focusingcouldbeverynoisy.Inaddition,sinceedgefocusingisobtainedat a finer resolution, some edges (i.e., the blurred ones, such as
shadows)presentajugglingeffectatsmallscales.Thisisdueto
thesplittingofacoarseedgeintoseveralfineredges,andtendsto give rise to broken, discontinuous edges.
Lacroix[20]avoidstheproblemofsplittingedgesbytracking
edges from a fine-to-coarse resolution. His algorithm detects
edgesusingtheCannymethodofnonmaximasuppressionofthemagnitudeofthegradientinthegradientdirection.Hismethodthenconsidersthreescales:1)
;2);and3) .Thesmallest
scale,, is the detection scale, and is the finest resolution at
which an edgel (i.e., a short, linear edge element) first appears.The largest scale,
, is the blurring scale, and is the coarsest
resolutionatwhichtheedgelstillremains.Theintermediateres-
olution is computed as
(8)
An edgel is validated if: 1) it is the local maximum of a
Gaussian gradient and 2) the two regions it separates are ho-
mogeneous and significantly different from one another. Onlyvalidated edgels are then tracked through the scales.
Although Lacroix avoids the problem of splitting edges, he
introduces the problem of localization erroras it is the coarsest
resolutionthatisusedtodeterminethelocationoftheedges.He
also provides no explanation as to how to decide which scalesare to be used and under what conditions.

256 IEEE TRANSACTIONS ON SYSTEMS, MAN,AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 32, NO. 3, AUGUST2002
Williams and Shah [36] devised a scheme to find edge
contours using multiple scales. They analyzed the movementof edge points smoothed with a Gaussian operator of different
sizes, and used this information to determine how to link edge
points detected at different scales. Their method, followingthe lead of Canny, uses a gradient of Gaussian operator todetermine gradient magnitude and direction, followed by
nonmaxima suppression to identify ridges in the gradient map.
Since the resulting ridges are often more than one pixel wide,the gradient maxima points are thinned and then linked usingan algorithm which assigns weights based on four measures:
1) noisiness; 2) curvature; 3) contour length; and 4) gradient
magnitude.Thesetofpointshavingthehighestaverageweightis chosen.
The algorithm extends to multiresolution by convolving the
image with the Gaussian filter at three scales: 1)
;2 ) ;
and 3) . First, the best partial edge contours are found using
the largest scale. Then, the next smaller scale is used, and theregions around the end points of the contours are examined to
determine if there are possible edge points at the smaller scale
having similar directions to the end points of the contours. Theoriginal algorithm is then carried out for each of these possibleedgepoints,andthebestarechosenasanextensiontotheorig-
inal edge contour. The scale is decreased to the smallest scale,
and the process is repeated.
AlthoughWilliamsandShahspecifythenumberofscalesto
be used and the relationship between these scales, they did not
suggest the best way to choose the value of
and under what
conditions.
Goshtasby[13]proposesanalgorithmthatworksona modi-
fiedscale-space representation of an image. The author creates
a representation of an image by recording the signs of pixels
(instead of the zero-crossings) after filtering with LOG oper-ator.Theadvantageofsucharepresentationoverthatofregularscale-space is that the new representation does not contain any
disconnected arches. The scale-step size is determined adap-
tively using the image structure in the following manner. Re-sultsofconvolutionofanimageatscales
andareoverlaid
oneontopofanother.Ifmorethantworegionsofthesamesign
fall on top of each other, the complete information on behavior
of edges between these two scales is lacking. Therefore, onemust consider an intermediate scale between
and. Oth-
erwise, there is no new edge information between these two
scales. This procedure makes a decision on step sizes as one
goes along rather than choosing step sizes before the processstarts. This also avoids the use of too many or too few scales.This is the crucial part of the algorithm. Once the scale-space
image is constructed using the correct values for
, tracking of
edgefromlowesttohighestresolutionispossiblesincethereareno disconnected arches. The major problem with Goshtasby’sedge focusing algorithm is the need for a considerable amount
memory to store the three-dimensional (3-D) edge images.
To avoid the common problems associated with integrating
edgesdetectedatmultiplescales,JeongandKim[16]proposedaschemewhichautomaticallydeterminestheoptimalscalesfor
each pixel before detecting the final edge map. To find the op-
timal scales for a Gaussian filter, they define an energy func-tionthatquantitativelydeterminestheusefulnessofthepossibleedgemap.Theyapproachtheedgedetectionproblemasfinding
the size of the Gaussian filter
which minimizes the en-
ergyfunction over ,. The parameter is chosensothat:
1) it is large at uniform intensity areas, thereby smoothing
out random noise;
2) itissmallatlocationswheretheintensitychangessignif-
icantly, thus retrieving edges accurately;
3) it does not change sharply from pixel to pixel, therefore
avoiding broken edges due to random noise.
Ifanddenotethe2-DGaussianfilterandimagefunction,
respectively, the equation to be minimized is
(9)
Since the Jeong-Kim algorithm is designed to adaptively
find the optimal scale of the Gaussian filter for every location
in the image function, it can be easily incorporated into any
Gaussian-based edge-detection technique. However, this al-gorithm does result in reduced performance when it comes todetecting straight lines in vertical or horizontal directions. The
algorithm also has the disadvantage of low-speed performance
[4].
DengandCahill[9]alsouseanadaptiveGaussianfilteringal-
gorithm for edge detection. Their method is based on adapting
the variance of the Gaussian filter to the noise characteristicsand the local variance of the image data. Based on observa-tionsofhowthehumaneyeperceivesedgesindifferentimages,
they concluded that in areas with sharp edges, the filter vari-
ance should be small to preserve the sharp edges and keep thedistortion small. In smooth areas, the variance should be largesoastofilteroutnoise.Theyproposedthatthevarianceofa1-D
Gaussian filter at location
is
(10)
where
scaling factor;
noise variance;
local variance of the signal.
The major drawback of this algorithm is that it assumes the
noise is Gaussian with known variance. In practical situations,however, the noise variance has to be estimated. The algorithmis also very computationally intensive.
In[4],Bennamoun etal.presentahybriddetectorthatdivides
the tasks of edge localization and noise suppression betweentwo subdetectors. This detector is the combination of the out-
puts from the Gradient of Gaussian and Laplacian of Gaussian
detectors. The hybrid detector performs better than both thefirst-order and second-order detectors alone, in terms of local-izationandnoiseremoval[4].Theauthorsextendedtheworkto
automatically determine the optimal scale
and threshold ,
of the hybrid detector. They do this by:
1) finding the probability of detecting an edge for a signal
with noise ;
2) findingtheprobabilityofdetectinganedgeinnoise only
;

BASU: GAUSSIAN-BASED EDGE DETECTION METHODS—A SURVEY 257
3) derivingacostfunctionwhichmaximizes andmin-
imizes ,therebygivingtheoptimal andvalues.
The minimization of is equivalent to the maximiza-
tion of its complement, therefore the cost function to be
maximized is
(11)
where . When , all the emphasis is placed
on noise suppression. When , the emphasis is on edge
detection. Choosing to be around 0.5 results in and
values which try to balance noise suppression and edge detec-
tion. However, as the authors’ results show, their technique isstill susceptible to false edge-detection, especially in the pres-
ence of high noise levels.
In [28] and [29], Qian and Huang introduce a 2-D edge de-
tection scheme. The scheme detects edges in images with anedge-detectionfunctionalthatusestheLOGzero-crossingcon-
tours as a guide to the true edge locations. The proposed edge
functional is based on a parametric 2-D edge model, and wasdeveloped to be optimal in terms of SNR and edge localizationaccuracy (ELA).
TheprocedurebeginsbyconvolvinganimagewiththeLOG
operator and finding the zero-crossing points. Zero-crossingcontours are then segmented at points with large curvatures,and the true edge locations are determined using the 2-D edge
detectionfunctional.Adaptivethresholdingbasedontheglobal
noise estimation and physiological evidence from biologicalvisual systems is then performed on the edge segments. Thisis followed by an edge regularization technique for continuity
and smoothness of the detected edges.
Edge segments are combined from different scales using a
fine-to-coarsestrategy.Sincethesmallestscaleofthedetectionfunctional gives the best ELA, and only edges with high SNR
survivetheedge-detectionproceduredescribedabove,thefinal
edgemapalwayscontainsalltheedgesfromthesmallestscale.The results from larger scales are incorporated into the finaledge map if they produce new edge segments.
The scales of the operator used by Qian and Huang were se-
lectedtospantherangeoffiltersthatoperateinthehumanfovea.They used seven scales between
and .
However, this may not be the ideal range for computational
methods. In addition, the range may also change depending on
the type of image and the amount of noise it contains.
Morerecently,Lindeberg[21]suggestedaframeworkforau-
tomatic scale selection based on maximization of two specific
measures of edge strength
(12)
(13)
where scale space representation is obtained by convolving
a Gaussian with variance with the image. The parameter
represents scale. The subscript(s) of denotes derivative(s) of
taken in the direction(s) of the subscripts(s). The parameter
provides additional control in the selection process. We will
discuss the role of later in this paragraph. First, let us look at
(12)and(13).Thefirstequation,(12),computesthemagnitudeof the gradient. This is the simplest measure of edge strength.
Thesecondequation,(13),originatesfromthesignconditionintheedgedefinition.Anedgepointisdefinedasapointatwhich
thegradient magnitude assumes amaximum in the gradient di-
rection [7]. This is the same as the second-order derivative in agiven direction being zero and the third-order derivative in thesamedirectionbeingnegative.Thisequationcombinesthesign
information with the magnitude, scale, and
. Maximization of
these measures with respect to scale yields an equation for thescale parameter with both measures producing very similar re-sults.Theparameter
makesthescaleselectionmethoddepen-
dentonthediffusenessoftheedge,i.e.,finescaleisselectedfor
sharp edges and coarse scale is selected to deal with diffused(blurred) edges. However, the authors choose
in all their
experiments. This renders the proposed approach very similar
to[10]inmanyrespects.Anoteofcautionisrequiredhere.Au-
tomatic scale selection still requires the user to specify a scalerange. For example, the authors choose 40 scales (minimumscale
0.1 and maximum scale 256) for an image of size
256256. The maximization of the measures over the range
detects the best scales. A major drawback of this approach istheneedtocomputehigh-orderderivatives,whichareknowntocontribute toward computational difficulties. One does not see
any significant advantage in the use of such high-order deriva-
tives from theoretical or experimental results. On the positiveside,thispaperusestheedgediffusenessasaparameter,whichprovides useful clues to the physical nature of the edge.
The paper by Elder and Zucker [10] supports the basic
premise of [21] that selection of scale should be made de-
pendent on the edge diffuseness. In contrast to Lindeberg’s
approach,ElderandZuckerproposeacompletelylocalmethodfor scale selection. They also make the scale a function of thesecond moment of the sensor noise; information that is usually
available. This definitely holds considerable appeal from a
practicalstandpoint.Theauthorsarguethatsincethedistinctionbetweenimportant andunimportant edges is rather difficult to
make at the early stage of processing, the goal of an edge-de-
tector should be to detect all edges over the range of contrastand blur with which they occur while avoiding detection ofartifactualedges.Toachievethis,theauthorsintroducetheidea
of a minimum reliable scale at which and at larger scales, the
possibility of detecting edges due to sensor noise is below aspecifiedtolerance.Thescaleiscomputedlocallyasafunctionofthesensornoiseandtheblurscale.Thecomputationremains
simple.Furthermore,amethodtocomputetheblurprovidesan
estimate for the depth parameter. This can be used to separateforeground and background structures in the image. The useof a single scale as opposed to the use of multiple scales for
edge-detection sets this paper apart from standard approaches.
Thus, the authors argue that the problem of edge tracking overmultiple scales has been avoided. One should keep in mindthat the process of detecting and identifying important edges
cannot be avoided. It can only be delayed as is done here and
left to be handled by the next processing stage.
Next, we review research work that has delved more into
thebiologicalvisionprocess.Theedge-detectorsweremodeledafteramammalianvisualsystem.Later,itwasshownthatthesedetectors enjoy sound mathematical support.

258 IEEE TRANSACTIONS ON SYSTEMS, MAN,AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 32, NO. 3, AUGUST2002
Kennedy and Basu [3], [17]introduced a special line-weight
function (LWF) for enhancing edges in digital images. Unlikemostoftheworkspresentedhere,whicharebasedeitheronthe
first- or second-order derivatives of Gaussian, this operator is
a linear combination of zero- and second-order Hermite func-tions.ThisisequivalenttothecombinationofaGaussiananditssecond derivative. The development of this operator was based
onseveralpiecesofphysiologicalevidence.FiorentiniandMaz-
zatini [11] suggested that the LWF of humans are shaped likethelinearcombinationofzero-andsecond-orderHermitefunc-tions. This proposition is supported by Young [38] who points
out that such a function provides edge and line enhancement
and noise suppression, while retaining all the information inthe original image. This operator can also be derived math-ematically when the contrast sensitivity experiments of psy-
chophysics are posed as an eigenvalue problem [34]. The LWF
has an excellent edge localization property and does not detectphantom edges.
The LWF enhances edges in digital images. Edges are de-
tectedbyconvolvinganLWFfilteredimagewithanedgeoper-ator, such as the Sobel mask. The size of the LWF is chosen to
achieve the best operator performance while keeping the com-
plexity under control, but as mentioned earlier, the use of asinglescaledoesnotproduceoptimalresultsforedgedetection.
Thelastpartofthispaperlooksintoedge-detectorsthatleave
the linear territory in search of better performance. NonlinearmethodsbasedontheGaussianfilterevolvedasresearchersdis-
covered the relationship between the solution to the heat equa-
tionandimagesconvolvedwithGaussianfilterforasmoothingpurpose. Consider a set of derived images,
, by con-
volving the original image with a Gaussian filter of
variance .Theparameter correspondstotimeintheheatequa-
tion, whereas in the context of image it refers to the scale. Thisone parameter family of derived images can be viewed as thesolutionoftheheatequation[15],[19].However,inthecaseof
linear heat equation as diffusion eradicates noise, it also blurs
the edges isotropically. To overcome this problem, Perona andMalik [26] proposed a multiscale or scale space representationof an image based on anisotropic diffusion. In the mathemat-
icalcontext,thiscallsfornonlinearpartialdifferentialequations
rather than the linear heat equation.
The essential idea here is to allow space variant blurring
[26]. This is achieved by making the diffusion coefficient inthe heat equation a function of space and scale. The goal isto smooth within a region and keep the boundaries sharp. A
high value for the diffusion constant within the region and a
very small value (possibly 0) on the boundary can producethe desired effect. Specifically, the heat diffusion coefficient is
allowed to vary across the image plane and is made dependent
upon the image gradient. This effectively leads to a spatiallyadaptive smoothing which tends to preserve the location ofedges throughout the scale hierarchy. When the Perona-Malik
equation is decomposed into a process across the edge and
one perpendicular to it, it can be understood how smoothingand sharpening can be carried out at the same time. The entireprocess is a combination of forward and backward diffusionprocesses.
3However, backward diffusion is well known to
be an ill-posed process where the solution, if it exists at all,is highly sensitive to even the slightest perturbations of the
initial data [18], [35]. In the context of image processing, the
main observed instability is the so-called staircasing effect ,
where a smoothed step edge evolves into piecewise almostlinear segments which are separated by jumps (see [25] for an
illustration). The extent of this effect is dictated by the process
of discretization. This effect is observable for fine spatialdiscretization and for slowly varying ramp edges. Fortunately,underpracticalsituations,thisphenomenonishardlyobserved.
It is an experimental fact that reasonable discretizations of the
Perona-Malik equation are rarely unstable. Fontaine and Basu[12]suggesttheuseofwaveletstosolvetheanistropicdiffusionequation.Wavelet-basedmultiresolutionexpansionsareknown
togivemorecompactrepresentationsofimageswithregionsof
lowcontrastseparatedbyhigh-contrastedges.Additionally,theuse of wavelets provides a way to estimate contrast value foredges on a space-varying basis in a local or global manner as
needed.Thedrawbackofthisapproachisthatthediscretization
schemeforthediffusionequationproposedinthispapercannotbe directly expressed in the wavelet transform domain. Thisrequiresaniterativeprocedureofgoingbackandforthbetween
the spatial and the wavelet domains of representation and adds
to the numerical complexity of the algorithm.
The most required property of scale-space representation is
satisfied here—which is no new features are introduced in the
derived images (i.e., in the scale-space representation of the
original image) in passing from fine to coarse scale.
4
In contrast to Perona and Malik, Aurich and Weule [1] do
not use anisotropic diffusion. Their method is based on a mod-
ification of the way the solution of the heat equation is ob-
tained by convolving the initial data with a Gaussian kernel.Thus, it avoids a large number of iterations and problems dueto convergence. The method uses a nonlinear modification of
Gaussian filters. The convolution of an image
and a non-
linear Gaussian filter is given as follows:
where image signal is defined on a bounded discrete set of
pixels and the normalization factor in the neighborhood of
pixel,, is given by
Let us rewrite the aboveequation in the following form:
Intuitively,edgeatlocation intheneighborhoodofpixel can
bepreservedif doesnotdominatethesum.Letusperform
3While the forward diffusion process blurs, the backward diffusion process
sharpens.
4Note similarity with Gaussian scale space representation.

BASU: GAUSSIAN-BASED EDGE DETECTION METHODS—A SURVEY 259
an informal analysis of the above equation to see: 1) how an
edge is preserved while the image is smoothed and 2) how anedge is enhanced while the image is smoothed.
1) How an edge is preserved : Consider a pixel
. We are
computing a new pixel value at by doing a weighted average
overneighborhoodof .Thevariance determinesthesizeof
the neighborhood.
• CaseI: issmallfor intheneighborhoodof
. The value of will be large. Thus new
will be more close to itsneighboring pixelvalues.
• Case II: is small for in the neighborhood
ofexceptatonepixel .Here, willhavea
significantly larger value than . The aim is to
reducetheimpactof .Thevalueof
will be small. Thus the weighted sum will receive only a
small fraction of .
We can conclude that a new pixel value of a nonedge pixel
willnotincreaseundulybecauseofaneighboringedgepixel
value. This will prevent blurring of the edge present at .
2)Howanedgeisenhanced :Consideranedgepixel with
pixel value . After weighted averaging is done at we ob-
tain a new value . It is obvious that .
This shows that after each convolution, pixel values at edges
are increasing. However, one must keep in mind that although
pixel value is increasing due to filtering, the overall effect maynot produce enhancement. The slope of the edge is a criticalfactor here. Enhancement is achieved if the edge is steep.
Aurich and Weul suggest that image should be convolved
with a series of such Gaussian filters. One should start with asmallvaluefor
andalargevaluefor .Insuccessivesteps,
is increased and is decreased. This continues to reduce
thecontrastofthefinedetailswhilesharpeningtheedgesofthecoarse structures.
Note that this method does not produce a scale-space rep-
resentation of the image. The possibility of the appearance of
newfeaturesintheimagehasnotbeenexploredmathematicallyorexperimentally.Furthermore,unlikeusualscale-spacerepre-sentation techniques, no order is created in the set of images
producedbysuccessivefiltering.Thus,anedgepointcannotbe
tracked from one filtered image to the next.
V. S
UMMARY
The Gaussian filter has several desirable features which ac-
counts for its wide use in many image processing applications.However, research clearly demonstrates that edge-detectiontechniques involving this filter do not give satisfactory results.
Linear methods presented in this paper suffer from problems
associated with Gaussian filtering, namely, edge displacement,vanishingedges,andfalseedges.Theintroductionofmultiscaleanalysis further complicates the issue by creating two major
problems: 1) how to choose the size of the filters and 2) how
to combine edge information from different scales. Adaptiveapproaches which avoid the multiresolution problem all tendto be computationally intensive. Nonlinear approaches show
significant improvement in edge-detection and localization
over linear methods. However, problems of computationalspeed, convergence, and difficulties associated with multiscaleanalysisremain.Asitcurrentlystands,useoftheGaussianfilter
requires making compromises when developing algorithms togive the best overall edge-detection performance.
A
CKNOWLEDGMENT
The author wishes to thank the anonymous reviewers whose
commentsled to substantial improvementsin this manuscript.
REFERENCES
[1] V. Aurich and J. Weule, “Nonlinear Gaussian filters performing edge
preservingdiffusion,”in Proc.17thDAGMSymp. ,NewYork,1995,pp.
538–545.
[2] J. Babaud, A. P. Witkin, M. Baudin, and R. O. Duda, “Uniqueness of
theGaussiankernelforscale-spacefiltering,” IEEETrans.PatternAnal.
Machine Intell. , vol. PAMI-8, pp. 26–33, Jan. 1986.
[3] M.Basu,“AGaussianderivativemodelforedgeenhancement,” Pattern
Recognit. , vol. 27, pp. 1451–1461, 1994.
[4] M.Bennamoun,B.Boashash,andJ.Koo,“Optimalparametersforedge
detection,” in Proc. IEEE Int. Conf. SMC ,vol.2, 1995,pp.1482–1488.
[5] F. Bergholm, “Edge focusing,” IEEE Trans. Pattern Anal. Machine In-
tell., vol. PAMI-9, pp. 726–741, June 1987.
[6] V.Berzins,“Accuracyoflaplacianedge-detectors,” Comput.Vis.Graph.
Image Process. , vol. 27, pp. 195–210, 1984.
[7] J. Canny, “A computational approach to edge detection,” IEEE Trans.
Pattern Anal.Machine Intell. , vol. PAMI-8,pp. 679–698,June 1986.
[8] J. J. Clark, “Authenticating edges produced by zero-crossing algo-
rithms,”IEEE Trans. Pattern Anal. Machine Intell. , vol. 11, pp. 43–57,
Jan. 1989.
[9] G.DengandL.W.Cahill,“AnadaptiveGaussianfilterfornoisereduc-
tionandedgedetection,”in Proc.IEEENucl.Sci.Symp.Med.Im.Conf. ,
1994, pp. 1615–1619.
[10] J.H.ElderandS.W.Zucker,“Localscalecontrolforedgedetectionand
blurestimation,” IEEETrans.PatternAnal.MachineIntell. ,vol.20,pp.
699–716, June 1998.
[11] A. Fiorentiniand L. Mazzatini,“Neuron inhibition in thehuman fovea:
A study of interaction between two line stimuli,” Atti Fond G Ronchi ,
vol. 21, pp. 738–747, 1966.
[12] F.L.FontaineandS.Basu,“Awavelet-basedsolutiontoanisotropicdif-
fusionequationforedgedetection,” Int.J.ImagingSci.Technol.:Special
IssueonImageSequenceProcessing,MotionEstimation,andCompres-
sion of Image Sequences , vol. 9, pp. 356–368, 1998.
[13] A. Goshtasby, “On edge focusing,” Image Vis. Comput. , vol. 12, pp.
247–256, 1994.
[14] R. M. Haralick, “Digital step edges from zero-crossing of second di-
rectional derivatives,” IEEE Trans. Pattern Anal. Machine Intell. , vol.
PAMI-6, pp. 58–68, Jan. 1984.
[15] R.A.Hummel,“Representationbasedonzero-crossingsinscalespace,”
inProc.IEEEComputerVisionandPatternRecognitionConf. ,1986,pp.
204–209.
[16] H. Jeong and C. I. Kim, “Adaptive determination of filter scales for
edge-detection,” IEEETrans.PatternAnal.MachineIntell. ,vol.14,pp.
579–585, May 1992.
[17] L.M.KennedyandM.Basu,“Imageenhancementusingahumanvisual
systemmodel,” PatternRecognit. ,vol.30,no.12,pp.2001–2014,1997.
[18] S. Kichenassamy, “The Perona-Malik paradox,” SIAM J. Appl. Math ,
vol. 57, no. 5, pp. 1328–1342, 1997.
[19] J. Koenderink, “The structure of images,” Biol. Cybern. , vol. 50, pp.
363–370, 1984.
[20] V. Lacroix, “The primary raster: A multiresolution image description,”
inProc. 10th Int. Conf. Pattern Recognition ,1990, pp. 903–907.
[21] T. Lindeberg, “Edge detection and ridge detection with automatic scale
selection,” Int. J. Comput. Vis. , vol. 30, pp. 117–156, 1998.
[22] Z. Q. Liu, “Scale space approach to directional analysis of images,”
Appl. Opt. , vol. 30, no. 11, pp. 1369–1373, 1991.
[23] D.MarrandE.Hildreth,“Theoryofedgedetection,” Proc.R.Soc.Lond.
A, Math. Phys. Sci. , vol. B 207, pp. 187–217, 1980.
[24] V. S. Nawal, A Guided Tour of Computer Vision . Reading, MA: Ad-
dison-Wesley, 1993.
[25] M. Nitzberg and T. Shiota, “Nonlinear image filtering with edge and
corner enhancement,” IEEE Trans. Pattern Anal. Machine Intell. , vol.
14, pp. 826–833, July 1992.

260 IEEE TRANSACTIONS ON SYSTEMS, MAN,AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 32, NO. 3, AUGUST2002
[26] P. Perona and J. Malik, “Scale-space and edge detection using
anisotropic diffusion,” IEEE Trans. Pattern Anal. Machine Intell. , vol.
12, pp. 629–639, July 1990.
[27] W.K.Pratt, DigitalImageProcessing . NewYork:Wiley-Interscience,
1978.
[28] R. J. Qian and T. S. Huang, “Optimal edge detection in two-dimen-
sional images,” in Proc. Image Understanding Workshop , 1994, pp.
1581–1588.
[29] , “Optimal edge detection in two-dimensional images,” IEEE
Trans. Image Processing , vol. 5, pp. 1215–1220, July 1996.
[30] A.RosenfeldandA.C.Kak, DigitalPictureProcessing ,2nded. New
York: Academic, 1982.
[31] B.G.Schunck,“EdgedetectionwithGaussianfiltersatmultiplescales,”
inProc. IEEE Comp. Soc. Work.Comp. Vis. , 1987, pp. 208–210.
[32] M. Shah, A. Sood, and R. Jain, “Pulse and stair case edge models,”
Comput.Vis. Graph.Image Process. , vol. 34, pp. 321–343, 1986.
[33] J.ShenandS.Castan,“Towardtheunificationofband-limitedderivative
operators for edge detection,” Signal Process. , vol. 31, pp. 103–119,
1993.
[34] A. L. Stewart and R. Pinkham, “A spatial-variant differential operator
for visual sensitivity,” Biol. Cybern. , vol. 64, pp. 373–379, 1991.
[35] J.WeickertandB.Benhamouda,“Asemidiscretenonlinearscale-space
theory and its relation to the Perona-Malik paradox,” in Advances in
Computer Vision , F. Solina, W. G. Kropatsch, R. Klette, and R. Bajcsy,
Eds. New York: Springer-Verlag, 1997, pp. 1–10.
[36] D. J. Williams and M. Shah, “Edge contours using multiple scales,”
Comput. Vis. Graph Image Process. , vol. 51, pp. 256–274, 1990.
[37] A.P. Witkin,“Scale-spacefiltering,” in Proc. Int. Joint.Conf.Artificial
Intelligence , vol. 2, 1983, pp. 1019–1022.[38] R. A. Young, “The Gaussian derivative model for spatial vision: Part
I—Retinalmechanisms,” Spatial Vis. , vol.2, no.4, pp. 273–293,1987.
[39] A. L. Yuille and T. A. Poggio, “Scaling theorems for zero-crossings,”
IEEETrans.PatternAnal.MachineIntell. ,vol.PAMI-8,pp.15–25,Jan.
1986.
[40] P.Zamperoni,“Imageenhancements,”in AdvencesinImagingandElec-
tron Physiscs . New York: Academic, 1995, pp. 1–76.
[41] D.ZiouandS.Tabbone,“Edgedetectiontechnique—Anoverview,” Int.
J. Pattern Recognit. ImageAnal. , vol. 8, pp. 537–559, 1998.
MitraBasu (S’84–M’85–SM’99)receivedthePh.D.
degreeinelectricalengineeringfromPurdueUniver-
sity, West Lafayette, IN, in 1985.
She is an Associate Professor in the Department
of Electrical Engineering, The City College of
New York. At present, she is on loan to the NSF,
where she is a Program Director in the CISE
Directorate. Her research interests include pattern
recognition, biological/artificial learning systems,
and bioinformatics. She is an Associate Editor of
Pattern Recognition .
Dr. Basu is a member of the New York Center for Biomedical Engineering
at the City College. She has joint appointment with the doctoral faculty of
The Graduate School and the University Center’s Ph.D. program in Computer
Science and Electrical Engineering.