Edge Detection by Helmholtz Principle.
We apply to edge detection a recently introduced method for computing geometric structures in a digital image, without any a priori information. According to a basic principle of perception due to Helmholtz, an observed geometric structure is perceptually meaningful if its number of occurences would be very small in a random situation: in this context, geometric structures are characterized as large deviations from randomness. This leads us to define and compute edges and boundaries (closed edges) in an image by a parameter-free method. Maximal detectable boundaries and edges are defined, computed, and the results compared with the ones obtained by classical algorithms.
Introduction
In statistical methods for image analysis, one of the main problems is
the choice of an adequate prior. For example, in the Bayesian model
(Geman and Geman, 1984), given an observation \obs", the aim is to
nd the original \model" by computing the Maximum A Posteriori
(MAP) of
The term P [obsjmodel] represents the degradation (superimposition of
a gaussian noise for example) and the term P [model] is called the prior.
This prior plays the same role as the regularity term in the variational
framework. This prior has to be xed and it is generally dicult to nd
a good prior for a given class of images. It is also probably impossible
to give an all-purpose prior!
In (Desolneux et al., 1999) and (Desolneux et al., 2000), we have
outlined a dierent statistical approach, based on phenomenological observations
coming from Gestalt theory (Wertheimer, 1923). According
to a perception principle which seems to go back to Helmholtz, every
large deviation from a \uniform noise" image should be perceptible,
provided this large deviation corresponds to an a priori xed list of
geometric structures (lines, curves, closed curves, convex sets, spots,
c
2001 Kluwer Academic Publishers. Printed in the Netherlands.
Moisan and Morel
local groups,. Thus, there still is an a priori geometric model, but,
instead of being quantitative, this model is merely qualitative. Let us
illustrate how this should work for \grouping" black dots in a white
sheet. Assume we have a white image with black dots spread out. If
some of them form a cluster, say, in the center of the image, then, in
order to decide whether this cluster indeed is a group of points, we
compute the expectation of this grouping event happening by chance
if the dots were uniformly distributed in the image. If this expectation
happens to be very low, we decide that the group in the center is
meaningful. Thus, instead of looking for objects as close as possible to
a given prior model, we consider a \wrong" and naive model, actually
a random uniform distribution, and then dene the \objects" as large
deviations from this generic model. One can nd in (Lowe, 1985) a very
close formulation of computer vision problems.
We may call this method Minimal A Posteriori Expectation, where
the prior for the image is a uniform random noise model. Indeed, the
groups (geometric structures, gestalts 1 ) are dened as the best counter-
examples, i.e. the least expected. Those counterexamples to the uniform
noise assumption are taken in a restricted geometric class. Notice that
not all such counterexamples are valid: the Gestalt theory xes a list of
perceptually relevant geometric structures which are supposedly looked
for in the perception process. The computation of their expectation in
the uniform noise model validates their detection: the least expected in
the uniform noise model, the more perceptually meaningful they will
be.
This uniform noise prior is generally easy to dene. Consider for
example the case of orientations: since we do not have any reason to
favour some directions, the prior on the circle S 1 will be the uniform
distribution. We applied this method in a previous paper dedicated
to the detection of meaningful alignments (Desolneux et al., 1999).
In (Desolneux et al., 2000) we have generalized the same method to
the denition of what we called \maximal meaningful modes" of a
histogram. This denition is crucial in the detection of many geometric
structures or gestalts, like groups of parallel lines, groups of segments
with similar lengths, etc.
It is clear that the above outlined Minimum A Posteriori method will
prove its relevance in Computer Vision only if it can be applied to each
and all of the gestalt qualities proposed by phenomenology. Actually,
we think the method might conversely contribute to a more formal and
general mathematical denition of geometric structures than just the
We choose to write gestalt(s) instead of the german original Gestalt (en). We
maintain the german spelling for \Gestalt theory"
Edge Detection by Helmholtz Principle 3
ones coming from the usual plane geometry. Now, for the time being,
we wish to validate the approach by matching the results with all of
the classicaly computed structures in image analysis. In this paper, we
shall address the comparison of edge and boundary detectors obtained
by the Minimum a Posteriori method with the ones obtained by state
of the art segmentation methods.
A main claim in favour of the Minimum a Posteriori is its reduction
to a single parameter, the meaningfulness of a geometric event depending
only on the dierence between the logarithm of the false alarm rate
and the logarithm of the image size! We just have to x this false alarm
rate and the dependance of the outcome is anyway a log-dependence
on this rate, so that the results are very insensitive to a change. Our
study of edge detection will conrm this result, with slightly dierent
formulas though.
In addition, and although the list of geometric structures looked for
is wide (probably more than ten in Gestalt theory), the theoretical
construction will make sense if they are all deduced by straightforward
adaptations of the same methodology to the dierent geometric struc-
tures. Each case of geometric structure deserves, however, a particular
study, in as much as we have to x in each case the \uniform noise"
model against which we detect the geometric structure. We do not
claim either that what we do is 100% new: many statistical studies
on images propose a \background" model against which a detection
is tested ; in many cases, the background model is a merely uniform
noise, as the one we use here. Optimal thresholds have been widely
addressed for detection or image thresholding (Abutaled, 1989; Guy
and Medioni, 1992; Pun, 1981; Weszka, 1978). Also, many applied
image analysis and engineering methods, in view of some detection,
address the computation of a \false alarm rate". Our \meaningfulness"
is nothing but such a false alarm rate, but applied to very general
geometric objects instead of particular looked for shapes and events.
As was pointed out to us by David Mumford, our method is also
related to the statistical hypothesis testing, where the asked question is:
does the observation follow the prior law given by Helmoltz principle ?
The gestalts will be the \best proofs" (in terms of the a priori xed
geometric structures) that the answer to this question is no. Let us
illustrate what is being done in the hypothesis testing language, by
taking the case of the detection of alignments.
Let us summarize: not all geometric structures are perceptually relevant
small list of the relevant ones is given in Gestalt theory ;
we can \detect" them one by one by the above explained Helmholtz
principle as large deviations from randomness. Now, the outcome is not
a global interpretation of the image, but rather, for each gestalt quality
4 Desolneux, Moisan and Morel
(alignment, parallelism, edges), a list of the maximal detectable events.
The maximality is necessary, as shows the following example, which
can be adapted to each other gestalt: assume we have detected a dense
cluster of black dots ; this means that the expectation of such a big
group is very small for a random uniform distribution of dots. Now, very
likely, many subgroups of the detected dots and also many larger groups
will have a small expectation too. So we can add spurious elements to
the group and still have a detectable group. Thus, maximality is very
relevant in order to obtain the best detectable group. We say that a
group or gestalt is \maximal detectable" if any subgroup and any group
containing it are less detectable, that is, have a smaller expectation.
We shall address here one of the serpents de mers of Computer
Vision, namely \edge" and boundary \detection". We dene an \edge"
as a level line along which the contrast of the image is strong. We call
\boundary" a closed edge. We shall in the following give a denition
of meaningfulness and of optimality for both objects. Then, we shall
show experiments and discuss them. A comparison with the classical
Mumford-Shah segmentation method will be made and also with the
Canny-Deriche edge detector. We shall give a (very simple in that case)
proof of the existence of maximal detectable gestalt, applied to the
edges. What we do on the edges won't be a totally straightforward
extension of the method we developped for alignments in (Desolneux
et al., 1999). Indeed, we cannot do for edge or boundary strength as
for orientation, i.e. we cannot assume that the modulus of the gradient
of an image is uniformly distributed.
2. Contrasted Boundaries
We call \contrasted boundary" any closed curve, long enough, with
strong enough contrast and which ts well to the geometry of the
image, namely, orthogonal to the gradient of the image at each one of
its points. We will rst dene "-meaningful contrasted boundaries, and
then maximal meaningful contrasted boundaries. Notice that this de-
nition depends upon two parameters (long enough, contrasted enough)
which will be usually xed by thresholds in a computer vision al-
gorithm, unless we have something better to say. In addition, most
boundary detection will, like the snake method (Kass et al., 1987),
introduce regularity parameters for the searched for boundary (Morel
and Solimini, 1994). If we remove the condition \long enough", we can
have boundaries everywhere, as is patent in the classical Canny lter
(Canny, 1986).
Edge Detection by Helmholtz Principle 5
The considered geometric event will be: a strong contrast along a
level line of an image. Level lines are curves directly provided by the
image itself. They are a fast and obvious way to dene global, contrast
insensitive candidates to \edges" (Caselles et al., 1996). Actually, it is
well acknowledged that edges, whatever their denition might be, are as
orthogonal as possible to the gradient (Canny, 1986; Davis, 1975; Duda
and Hart, 1973; Martelli, 1972; Rosenfeld and Thurston, 1971). As a
consequence, we can claim that level lines are the adequate candidates
for following up local edges. The converse statement is false: not all
level lines are \edges". The claim that image boundaries (i.e. closed
edges) in the senses proposed in the literature (Zucker, 1976; Pavlidis,
1986) also are level lines is a priori wrong. How wrong it is will come
out from the experiments, where we compare an edge detector with a
boundary detector. Surprisingly enough, we will see that they can give
comparable results.
We now proceed to dene precisely the geometric event: \at each
point of a length l (counted in independent points) part of a level line,
the contrast is larger than ". Then, we compute the expectation of
the number of occurrences of such an event (i.e. the number of false
alarms). This will dene the thresholds: minimal length of the level
line, and also minimal contrast in order to be meaningful. We will give
some examples of typical numerical values for these thresholds in digital
images. Then, as we mentioned has been done for other gestalts like
alignments and histograms, we will dene here a notion of maximality,
and derive some properties.
2.1. Definitions
Let u be a discrete image, of size N  N . We consider the level lines
at quantized levels  1 ; :::;  k . The quantization step q is chosen in such
a way that level lines make a dense covering of the image: if e.g. this
quantization step q is 1 and the natural image ranges 0 to 256, we get
such a dense covering of the image. A level line can be computed as a
Jordan curve contained in the boundary of a level set with level ,
Notice that along a level line, the gradient of the image must be everywhere
above zero. Otherwise the level line contains a critical point
of the image and is highly dependent upon the image interpolation
method. Thus, we consider in the following only level lines along which
the gradient is not zero. The interpolation considered in all experiments
below is the order zero interpolation (the image is considered constant
on each pixel and the level lines go between the pixels).
6 Desolneux, Moisan and Morel
Let L be a level line of the image u. We denote by l its length counted
in independent points. In the following, we will consider that points at
a geodesic distance (along the curve) larger than 2 are independent (i.e.
the contrast at these points are independent random variables). Let x 1 ,
l denote the l considered points of L. For a point x 2 L, we will
denote by c(x) the contrast at x. It is dened by
where ru is computed by a standard nite dierence on a 2  2 neighborhood
(Desolneux et al., 2000). For  2 R
, we consider the event:
i.e. each point of L has a contrast larger
than . From now on, all computations are performed in the Helmholtz
framework explained in the introduction: we make all computations
as though the contrast observations at x i were mutually independent.
Since the l points are independent, the probability of this event is
where H() is the probability for a point on any level line to have a
contrast larger than . An important question here is the choice of
H(). Shall we consider that H() is given by an a priori probability
distribution, or is it given by the image itself (i.e. by the histogram of
gradient norm in the image)? In the case of alignments, we took by
Helmholtz principle the orientation at each point of the image to be a
random, uniformly distributed variable on [0; 2]. Here, in the case of
contrast, it does not seem sound at all to consider that the contrast
is uniformly distributed. In fact, when we observe the histogram of
the gradient norm of a natural image (see Figure 1), we notice that
most of the points have a \small" contrast (between 0 and 3), and that
only a few points are highly contrasted. This is explained by the fact
that a natural image contains many
at regions (the so called \blue sky
eect", (Huang and Mumford, 1999)). In the following, we will consider
that H() is given by the image itself, which means that
where M is the number of pixels of the image where ru 6= 0. In order
to dene a meaningful event, we have to compute the expectation of
the number of occurrences of this event in the observed image. Thus,
we rst dene the number of false alarms.
DEFINITION 1 (Number of false alarms). Let L be a level line with
length l, counted in independent points. Let  be the minimal contrast
Edge Detection by Helmholtz Principle 7
of the points x 1 ,., x l of L. The number of false alarms of this event
is dened by
where N ll is the number of level lines in the image.
Notice that the number N ll of level lines is provided by the image
itself. We now dene "-meaningful level lines. The denition is analogous
to the denition of "-meaningful modes of a histogram or to the
denition of alignments: the number of false alarms of the event is less
than ".
DEFINITION 2 ("-meaningful boundary). A level line L with length l
and minimal contrast  is an "-meaningful boundary if
The above denition involves two variables: the length l of the level
line, and its minimal contrast . The number of false alarms of an event
measures the \meaningfulness" of this event: the smaller it is, the more
meaningful the event is.
Let us now proceed to dene \edges". We denote by N llp the number
of pieces of level lines in the image.
DEFINITION 3 ("-meaningful edge). A piece of level line E with length
l and minimal contrast  is an "-meaningful edge if
Here is how N llp is computed: we rst compute all level lines at uniformly
quantized levels (grey level quantization step is 1 and generally
ranges from 1 to 255. For each level line, L i with length l i , we compute
its number of pieces, sampled at pixel rate, the length unit being pixel
side. We then have
l
This xes the used number of samples. This number of samples will be
fair for a 1-pixel accurate edge detector. Clearly, we do detection and
not optimization of the detected edge: in fact, according to Shannon
conditions, edges have a between two or three pixels width. Thus, the
question of nding the \best" edge representative among the found ones
is not addressed here, but has been widely addressed in the literature
(Canny, 1986; Davis, 1975).
8 Desolneux, Moisan and Morel
norm of the gradient
percentage
of
pixels
200.20.40.60.8contrast

Figure

1. From left to right: 1. original image; 2. histogram of the norm of the
gradient; 3. its repartition function ( 7! P [jruj > ]).
2.2. Thresholds
In the following we will denote by F the function dened by
Thus, the number of false alarms of a level line of length l and minimal
contrast  is simply F (; l).
Since the function  7! is decreasing, and since for
all , we have H() 6 1, we obtain the following elementary properties:
We x  and l 6 l 0 , then
which shows that if two level lines have the same minimal contrast,
the more meaningful one is the longer one.
Edge Detection by Helmholtz Principle 9
We x l and  6  0 , then
which shows that if two level lines have the same length, the more
meaningful one is the one with higher contrast.
When the contrast  is xed, the minimal length l min () of an "-
meaningful level line with minimal contrast  is
l min
log H()
Conversely, if we x the length l, the minimal contrast  min (l) needed
to become "-meaningful is such that
2.3. Maximality
In this subsection, we address two kinds of maximality for the edges
and the boundaries. Let us start with boundaries. A natural relation
between closed level lines is given by their inclusion (Monasse, 1999).
If C and C 0 are two dierent closed level lines, then C and C 0 cannot
intersect. Let D and D 0 denote the bounded domains surrounded by C
and C 0 . Either D \ D (D  D 0 or D 0  D). We can consider,
as proposed by Monasse, the inclusion tree of all level lines. From now
on, we work on the subtree of the detected level curves, that is, the
ones for which F (; l) 6 " where " is our a priori xed expectation of
false alarms. (In practice, we take all experiments.) On this
subtree, we can, following Monasse, dene what we shall call a maximal
monotone level curve interval, that is, a sequence of level curves C i ,
is the unique son of C
- the interval is maximal (not contained in a longer one)
- the grey levels of the detected curves of the interval are either decreasing
from 1 to k, or increasing from 1 to k.
We can see many such maximal monotone intervals of detected curves
in the experiments: they roughly correspond to \fat" edges, made of
several well contrasted level lines. The edge detection ideology tends to
dene an edge by a single curve. This is easily made by selecting the
best contrasted edges along a series of parallel ones.
DEFINITION 4. We associate with each maximal monotone interval
its optimal level curves, that is, the ones for which the false alarms number
F (; l) is minimal along the interval. We call \optimal boundary
map" of an image the set of all optimal level curves.
Moisan and Morel
This optimal boundary map will be compared in the experiments
with classical edge detectors or segmentation algorithms.
We now address the problem of nding optimal edges among the detected
ones. We won't be able to proceed as for the boundaries. Although
the pieces of level lines inherit the same inclusion structure as
the level lines, we cannot compare two of them belonging to dierent
level curves for detectability, since they can have dierent positions and
lengths. We can instead compare two edges belonging to the same level
curve. Our main aim is to dene on each curve a set of disjoint maximally
detectable edges. In the following, we denote by NF
the false alarm number of a given edge E with minimal gradient norm
and length l.
DEFINITION 5. We call maximal meaningful edge any edge E such
that for any other edge E 0 on the same level curve such that E
E) we have NF
This denition follows (Desolneux et al., 1999) and (Desolneux et al.,
2000) where we apply it to the denition of maximal alignments and
maximal modes in a histogram.
PROPOSITION 1. Two maximal edges cannot meet.
Proof: Let E and E 0 be two maximal distinct and non-disjoint
meaningful edges in a given level curve and  and  0 the respective
minima of gradient of the image on E and E 0 . Assume e.g. that  6  0 .
has the same minimum as E 0 but is longer. Thus, by the
remark of the preceding subsection, we have F
which implies that E[E 0 has a smaller number of false alarms than E 0 .
Thus, E 0 is not maximal. As a consequence, two maximal edges cannot
3. Experiments
INRIA desk image (Figure 2).
In this experiment, we compare our method with two other methods
Mumford and Shah image segmentation and Canny-Deriche edge
detector.
In the Mumford and Shah model (Mumford and Shah, 1985), given
an observed image u dened on the domain D, one looks for the
piecewise approximation v of u that minimizes the functional
Z
Edge Detection by Helmholtz Principle 11

Figure

2. First row: left: original image; right: boundaries obtained with the Mum-
ford-Shah model (1000 regions). Second row: edges obtained with Canny-Deriche
edge detector, for two dierent threshold values (2 and 15). Third row: edges (left)
and boundaries (right) obtained with our model reconstruction
with the Mumford-Shah model (left) and with our model (right). This last reconstruction
is easily performed by the following algorithm: attribute to each pixel x
the level of the smallest (for inclusion) meaningful level line surrounding x (see
(Monasse, 1999)).
Moisan and Morel
where length(K(v)) is the one-dimensional measure of the discontinuity
set of v, and  a parameter. Hence, this energy is a balance between
a delity term (the approximation error in L 2 norm) and a regularity
term (the total length of the boundaries). The result v, called a segmentation
of u, depends upon the parameter , that indicates how to
weight both terms. As shown on Figure 2, the Mumford-Shah model
generally produces reasonable boundaries except in \
at" zones where
spurious boundaries often appear (see the front side of the desk for
example). This is easily explained: the a priori model is: the image
is piecewise constant with boundaries as short as possible. Now, the
image does not t exactly the model: the desk in the image is smooth
but not
at. The detected \wrong" boundary in the desk is necessary
to divide the desk into
at regions. The same phenomenon occurs in
the sky of the cheetah image (next experiment).
The Canny-Deriche lter (Canny, 1986; Deriche, 1987) is an optimization
of Canny's well known edge detector, roughly consisting in
the detection of maxima of the norm of the gradient in the direction of
the gradient. Notice that, in contrast with the Mumford-Shah model
and with our model, it does not produce a set of boundaries (ie one-dimensional
structures) but a discrete set of points that still are to be
connected. It depends on two parameters : the width of the impulse
response, generally set to 1 pixel, and a threshold on the norm of the
gradient that selects candidates for edge points. As we can see on Figure
2, the result is very dependent on this threshold. Thus, we can consider
the meaningfulness as a way to select the right edges. If Canny's lter
were completed to provide us with pieces of curves, our algorithm could
a posteriori decide which of them are meaningful. Notice that many
Canny edges are found in
at regions of the image, where no perceptual
boundary is present. If we increase the threshold, as is done on the right,
the detected edges look perceptually more correct, but are broken.
Cheetah image (Figure 3).
This experiment compares our edge detector with the Mumford-
Shah model. As before, we observe that the Mumford-Shah model
produces some spurious boundaries on the background, due to the
inadequacy of the piecewise constant model. This means that a more
sophisticated model must be applied if we wish to avoid such spurious
boundaries: the general Mumford-Shah model replaces the piece-wise
constant constraint by a smoothness term (the Dirichlet integral
R
on each region. Now, adding this term means using a
two-parameters model since, then, the Mumford-Shah functional has
three terms whose relative weights must be xed.
Edge Detection by Helmholtz Principle 13

Figure

3. First row: original image (left) and boundaries obtained with the Mum-
ford-Shah model with 1000 regions (right). Second row: edges (left) and boundaries
(right) obtained with our method
DNA image (Figure 4).
This experiment illustrates the concept of \optimal boundaries" that
we have introduced previously. When we compute the boundaries of the
original image, each \spot" produces several parallel boundaries due to
the important blur. With the denition of maximality we adopted, we
select exactly one boundary for each spot.
14 Desolneux, Moisan and Morel

Figure

4. From top to bottom: 1. original image; 2. boundaries; 3. optimal
boundaries.
Edge Detection by Helmholtz Principle 15

Figure

5. Up: original image. Downleft: boundaries. Downright: optimal boundaries.
Segments image (Figure 5).
As in the DNA experiment, the \optimal boundaries" allow to select
exactly one boundary per object (here, hand-drawn segments). In
particular, the number of boundaries we nd (21) counts exactly the
number of segments.
Noise image (Figure 6).
This image is obtained as a realization of a Gaussian noise with
standart deviation 40. For no boundaries are de-
tected. For larger values of ", some boundaries begin to be detected :
Figure 6), 148 for
Moisan and Morel

Figure

6. Left: an image of a Gaussian noise with standart deviation 40. Right: the
meaningful boundaries found for are found for
4. Discussion and conclusion
In this discussion, we shall address objections and comments made to
us by the anonymous referees and also by Jose-Luis Lisani, Yves Meyer
and Alain Trouve. In all that follows, we call respectively \boundary
detection algorithm" and \edge detection algorithm" the algorithms we
proposed. The other edge or boundary detection algorithms put into
the discussion will be called by their author's names (Mumford-Shah,
Canny).
4.1. Eight objections and their answers
Objection 1: the blue sky eect.
If a signicant part of a natural image happens to be very
at, because
of a \blue sky eect", then most level lines of the image will be detected
as meaningful. If (e.g.) one tenth of the image is a black
at region,
then the histogram of the gradient has a huge peak near zero. Thus, all
gradients slightly above this peak will have a probability 9
signicantly
smaller than 1. As a consequence, all level lines long enough (with
length larger than, say, will be meaningful. In practice, this
means that the image will be plagued with detected level lines with a
small contrast. These detected level lines are no edges under any decent
criterion ?
Answer 1: If the image has a wide \blue sky", then most level lines
of the ground are meaningful because any strong deviation from zero
becomes meaningful. This eect can be checked on the cheetah image:
the structured and contrasted ground has lots of detected boundaries
(and the sky has none). This outcome can be interpreted in the following
way: when a
at region is present in the image, it gives, via the
Edge Detection by Helmholtz Principle 17
gradient histogram, a indirect noise estimate. Every gradient which is
above the noise gradient of the
at region becomes meaningful and this
is, we think, correct.
Objection 2: dependence upon windows.
Then the detection of a given edge depends upon the window (contain-
ing the edge) on which you apply the algorithm ?
Answer 2: Yes, the algorithm is global and is aected by a reframing
of the image. If (e.g.) we detect edges on a window essentially containing
the sky, we shall detect more boundaries (see Figure 7) and if we
compute edges in a window only containing the contrasted boundaries,
it will detect less boundaries.

Figure

7. First row: left: original image (chinese landscape); right: maximal meaningful
edges row: the same algorithm, but run on a subwindow
(drawn on the left image); right: the result (in black), with in light grey the edges
that were detected in the full image.
Question 3: how to compute edges with multiple windows ?
Thus, you can apply your detection algorithm on any window of the
image and get more and more edges !
Answer 3: Yes, but, rst, if the window is too small, no edge will be
detected at all. Second, if we apply the algorithm to say, 100 windows,
we must take into account in our computations that the number of tests
is increased. Thus, we must decrease accordingly the value of " in order
to avoid false detections: an easy way is to do it is this: if we have 100
windows, we can take on each one the global number
of false alarms over all windows remains equal to 1. Thus, a multiwin-
dows version of the algorithm is doable and recommandable. Indeed,
Moisan and Morel
psychophysics and neurophysiology both advocate for a spatially local
treatment of the retinian information.
Objection 4: synthetic images where everything is meaningful.
If an image has no noise at all (synthetic image), all boundaries contain
relevant information. All the same, your algorithm won't detect them
all?
Answer 4: Right. If a synthetic binary image is made (e.g.) of a black
square with white background, then all gradients are zero except on the
square's boundary. The gradient histogram has one single value, 255.
(Remember that zero values are excluded from the gradient histogram).
Thus, which means that no line is meaningful. Thus, the
square's boundary won't be detected, which is a bit paradoxical! The
addition of a tiny noise or of a slight blur would of course restore the
detection of this square's boundary. This means that synthetic piece-wise
constant images fall out of the range or the detection algorithm.
Now, in that case, the boundary detection is trivial by any other edge
detector and our algorithm is not to be applied.
Question 5: class of images to which the algorithm is adapted ?
Is there a class of images for which the Mumford-Shah functional is
better adapted and another class of images where your algorithm is
more adapted ?
Answer 5: Our comparison of both algorithms may be misleading.
We are comparing methods with dierent scopes. The Mumford-Shah
algorithm aims at a global and minimal explanation of the image in
terms of boundaries and regions. As we pointed out in the discussion
of the experiments, this global model is robust but rough, and more
sophisticated models would give a better explanation, provided the
additional parameters can be estimated (but how?).
The detection algorithm does not aim at such a global explanation: it
is a partial detection algorithm and not a global explanation algorithm.
In particular, detected edges can be doubled or tripled or more, since
many level lines follow a given edge. In contrast, the Mumford-Shah
functional and the Canny detector attempt at selecting the best representative
of each edge. Conversely, the detection algorithm provides a
check tool to accept or reject edges proposed by any other algorithm.
Objection the algorithm depends upon the quantization
step.
The algorithm depends upon the quantication step q. When q tends to
Edge Detection by Helmholtz Principle 19
zero, you will get more and more level lines. Thus N ll and N llp (numbers
of level lines and pieces of level lines respectively) will blow up. Thus,
get less and less detections when q increases and, at the end, none!
Answer again. The numbers N ll and N llp stand for the
number of eectuated tests on the image. When the number of tests
tends to innity, the number of false alarms of Denition 1 also tends to
innity. Now, as we mentionned, q must be large enough in order to be
sure that all edges contain at least one level line. Since the quantization
noise is 1 and the standard deviation of noise never goes below 1 or
2, it is not likely to nd any edge with contrast smaller than 2. Thus,
enough, and we cannot miss any detectable edge. If we take q
smaller, we shall get more spatial accuracy to the cost of less detections.
Question 7: accuracy of the edges depends upon the quantization
step.
All the same, if q is not very small, you lose accuracy in the position
detection. Indeed, the quantized levels do not coincide with the optimal
level of the edge, as it would be found by a Canny edge detector.
Answer 7: Right again. The Canny edge detector performs two tasks in
one: detecting and optimizing the edge's position at subpixel accuracy.
The proposed detection algorithm does not nd the optimal position
of each edge. The spatial accuracy is roughly q=minjruj, where the
min is computed on the detected edge. In the case of the detection
of optimal boundaries, we therefore get this spatial accuracy for the
detected optimal boundaries. Of course, a postprocessing nding for
each edge the best position in terms of detectability is possible.
Objection 8: edges are not level lines.
You claim that every edge coincides with some level line. This is simply
not true!
Answer 8: If an edge has contrast kq, where q is the quantization step
(usually equal to 1), then k level lines coincide with the edge, locally. Of
course, one can construct long edges whose contrast is everywhere k but
whose average level varies in such a way that no level line fully coincides
with the edge. Now, long pieces of level lines coincide partially with it.
Thus, detection of this edge by the detection algorithm is possible all
the same, but it will be detected as a union of several more local edges.
Objection 9: values of the gradient on the level lines are not
independent.
Moisan and Morel
You chose as test set the set of all level lines. You claim that the gradient
amplitudes at two dierent points of every edge are independent. This
is, in most images, not true.
Answer 9: The independence assumption is, indeed, not a realistic
assumption. It is made in order to apply the Helmholtz principle,
according to which every large deviation from uniform randomness
assumption is perceptible. Thus, the independence assumption is not
a model for the image ; it is an a contrario assumption against which
the gestalts are detected.
Objection 10: A minimal description model would do the job
as well.
A minimal description model (MDL) can contain very wide classes of
models for which parameters will be estimated by the MDL principle of
shortest description in a xed language. This xed language can be the
language of Gestalt theory: explain the image in terms of lines, curves,
edges, regions, etc. Then existence and nonexistence of a given gestalt
would come out from the MDL description: a \detectable" edge would
be an edge which is used by the minimal description. Thus, thresholds
would be implicit in a MDL model, but exist all the same.
Answer 10: A MDL model is global in nature. Until we have constructed
it, we cannot make any comparison. In a MDL model, the
thresholds on edges would depend on all other gestalts. Thus, we would
be in the same situation as with the Mumford-Shah model: we have seen
that a sligth error on the region model leads to a false detection for
edges. The main advantage of the proposed method relies on its lack
of ambition: it is a partial gestalt detection algorithm, which does not
require any global explanation model in order to be applied. We may
compare the outcome of the algorithm with the computation in optimization
theory of feasible solutions. Feasible solutions are not optimal.
We provide feasible, i.e. acceptable edges. We do not provide an optimal
set of edges as is aimed at by the other considered methods.
Objection 11: is " a method parameter ?
You claim that the method has no parameter. We have seen in the
course of the discussion not less than three parameters coming out: the
choice of the windows, the choice of q, and nally the choice of ". So
what ?
Answer 11: We always Indeed, as we proved, the dependence
of detectability upon " is a Log-dependence. We also x
Edge Detection by Helmholtz Principle 21
again, the q dependence would be a Log-dependence, since the number
of level lines varies roughly linearly as a function of q. Finally, it is quite
licit to take as many windows as we wish, provided we take "
where k is the number of windows. This yields a false alarm rate of
1 over all windows. Again, since the number of windows is necessarily
small (they make a covering of the image and cannot be too small),
we can even take " because of the Log-dependence mentionned
above. To summarize, not a parameter. When we subdivide
our set of tests in subsets on several windows, we must of course divide
this value 1 by the number of sets of subtests. This does not requires
any user's input.
4.2. Conclusion
In this paper, we have tried to stress the possibility of giving a perceptually
correct check for any boundary or edge proposed by any algorithm.
Our method, based on the Helmholtz principle, computes thresholds of
detectability for any edge. This algorithm can be applied to level lines
or to pieces of level lines and computes then all detectable level lines.
One cannot view the algorithm as a new \edge detector", to be added to
the long list of existing ones ; indeed, rst, the algorithm does not select
the \best" edge as the other algorithms do. Thus, it is more primitive
and only yields \feasible" candidates to be an edge. Only in the case of
boundary detection can it be claimed to give a nal boundary detector.
this boundary detector may anyway yield multiple boundaries.
On the other hand, the proposed method has the advantage of giving
for any boundary or edge detector a sanity check.
Thus, it can, for any given edge detector, help removing all edges which
are not accepted from the Helmholtz principle viewpoint. As a sanity
check, the Helmholtz principle is hardly to be discussed, since it only
rejects any edge which could be observed in white noise.
The number of false alarms gives, in addition, a way to evaluate the
reliability of any edge and we think that the maximality criterion could
also be used in conjonction with any edge detector.
Finally, we can claim that the kind of algorithm and experiments proposed
here advocate for the necessity and usefulness of an intermediate
layer in image analysis algorithms, where feasibility of the sought for
structures is checked before any more global interpretation is attempted
by a variational method.
22 Desolneux, Moisan and Morel



--R

Automatic thresholding of gray-level pictures using two-dimensional entropy
A computational approach to edge detection.
Progress in Nonlinear Di
Elements of Information Theory.
A survey of edge detection techniques.
Using Canny's Criteria to derive a recursively implemented optimal edge detector.
Meaningful Alignments.

Maximal meaningful events and applications to image analysis.
Pattern Classi
A survey on image segmentation.
Stochastic relaxation
Inferring global perceptual contours from local features.
of Comp.
Image segmentation techniques.
Statistics of Natural Images and Models.
Grammaire du Voir.
Snakes: active contour models.
Constructing Simple Stable Descriptions for Image Partitioning.
of Comp.
Perceptual Organization and Visual Recognition.
Edge detection using heuristic search methods.
Gesetze des Sehens.

Variational Methods In Image Segmentation.
Boundary detection by minimizing functionals.
Trace inference


Entropic thresholding
A universal prior for integers and estimation by Minimum Description Length.
Edge and curve detection for visual scene analysis.
IEEE Trans.
The statistics of natural images.
Structural saliency

Untersuchungen zur Lehre der Gestalt
A survey of threshold selection techniques.
On the role of structure in vision.
Region growing: Childhood and Adolescence (Survey).

--TR

--CTR
Agns Desolneux , Lionel Moisan , Jean-Michel Morel, A Grouping Principle and Four Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.508-513, April
I. Abraham , R. Abraham , A. Desolneux , S. Li-Thiao-Te, Significant edges in the case of non-stationary Gaussian noise, Pattern Recognition, v.40 n.11, p.3277-3291, November, 2007
D. Coupier , A. Desolneux , B. Ycart, Image Denoising by Statistical Area Thresholding, Journal of Mathematical Imaging and Vision, v.22 n.2-3, p.183-197, May       2005
Frdric Cao , Julie Delon , Agns Desolneux , Pablo Mus , Frdric Sur, A Unified Framework for Detecting Groups and Application to Shape Recognition, Journal of Mathematical Imaging and Vision, v.27 n.2, p.91-119, February  2007
Andrs Almansa , Agns Desolneux , Sbastien Vamech, Vanishing Point Detection without Any A Priori Information, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.502-507, April
Thomas Veit , Frdric Cao , Patrick Bouthemy, An a contrario Decision Framework for Region-Based Motion Detection, International Journal of Computer Vision, v.68 n.2, p.163-178, June 2006
Frdric Cao , Pablo Mus , Frdric Sur, Extracting Meaningful Curves from Images, Journal of Mathematical Imaging and Vision, v.22 n.2-3, p.159-181, May       2005
Pablo Mus , Frdric Sur , Frdric Cao , Yann Gousseau , Jean-Michel Morel, An A Contrario Decision Method for Shape Element Recognition, International Journal of Computer Vision, v.69 n.3, p.295-315, September 2006
Ballester , Vicent Caselles , Laura Igual , Luis Garrido, Level Lines Selection with Variational Models for Segmentation and Encoding, Journal of Mathematical Imaging and Vision, v.27 n.1, p.5-27, January   2007
edge detection;helmholtz principle;large deviations;perception;image analysis