On the Performance of Connected Components Grouping.
Grouping processes may benefit computationally when simple algorithms are used as part of the grouping process. In this paper we consider a common and extremely fast grouping process based on the connected components algorithm. Relying on a probabilistic model, we focus on analyzing the algorithm's performance. In particular, we derive the expected number of addition errors and the group fragmentation rate. We show that these performance figures depend on a few inherent and intuitive parameters. Furthermore, we show that it is possible to control the grouping process so that the performance may be chosen within the bounds of a given tradeoff. The analytic results are supported by implementing the algorithm and testing it on synthetic and real images.
Introduction
Perceptual grouping is an essential ingredient in various visual processes [WT83, Low85].
A major use of grouping is to accelerate recognition processes [Gri90, CJ91]. Many implementations
of grouping processes, however, take a large computational effort themselves, as
they use computational intensive algorithms such as dynamic programming [SU88] or even
email address:mic@cs.technion.ac.il
simulated annealing [HH93]. Therefore, such grouping processes may not be effective for
reducing the total complexity of the visual process.
Simpler grouping processes, on the other hand, may require lower computational effort
but work satisfactorily only with simple, clean, images. When operating on a complex image,
such procedures result in hypothesized groups which are either fragmented or corrupted with
alien image features. Therefore, it makes sense to use the suitable process for the situation.
That is, to use simple procedures for easy tasks and reserve the more complex, computational
expensive, processes for difficult tasks. To make the right choice of the grouping process, it
is essential to study the benefits and the limitations of the various processes.
This paper is concerned with a simple grouping processes based on a connected components
graph algorithm. This process, defined in detail in the next section, is very fast and is
essentially linear in the number of data features. The paper focuses on analyzing the quality
of the groups extracted by this algorithm, and show that quantitative and meaningful
performance measures may be predicted and even, within certain constraints, controlled. In
particular, we consider the number of background features which are falsely added to the
true groups and the fragmentation of these groups, and show a tradeoff between these two
performance measures. An interesting result is that the process behaves according to an intuitively
interpreted parameter, which, if larger than a certain threshold, leads to explosion.
That is to a single hypothesized group including almost all the image features.
The main contributions of this paper are:
1. The paper provides, for the first time, an analysis of the connected components grouping
process, capable of predicting the grouping quality in terms of measurable, meaningful
quantities. The results may also be used for design, and specifically for choosing
the parameters controlling the grouping process.
2. The results of the paper, analytic as well as empirical, show that the simple connected
components algorithm is useful for many grouping tasks, provided that the appropriate
parameters are chosen, and that the expected result (which is predictable) in
acceptable. Then, this algorithm may be the algorithm of choice as it is extremely fast.
The rest of the paper is as follows. The next section describes the grouping framework
we consider, the connected components grouping process, and the probabilistic modeling
of the grouping cues. Then, the processes of adding false features and fragmentation are
considered, relative to a random image model, in sections 3 and 4, respectively, and a tradeoff
is quantitatively specified. Experiments with synthetic and real data follow (section 5) and
a discussion of the results concludes the paper (section 6).
grouping framework and the connected components
algorithm
In a common formulation of a grouping task, one is given a set of data features (e.g. pixels,
edgels) in an image and is asked to partition it into meaningful subset, requiring, for example
that, ideally, every set consists of all the features from the same imaged object. We consider
a fairly general set of grouping processes which work by testing small subsets of data features
using some criterion, denoted a grouping cue, and integrating the information into a decision
on the plausible data set partitioning. We follow the approach specified in [AL96] and specify
the grouping algorithm by three main decisions:
The grouping cues the bits of local grouping information which indicate whether two
(or more) data features belong to the same group. Common cues decide whether
two edgels are collinear, two pixel have similar intensities, etc. but more complex
cues are also used (see a very partial list of examples to various grouping cues in
[Low85, SU88, HH93, Jac96].)
The feature subsets which are tested - The grouping cues operate on subsets of data
features and those are specified using different criteria, depending on the validity of
the cues and the computational complexity allowed.
The cue integration method - Given the partial information about the subsets grouping
we may integrate it into a more global decision about the grouping (or partitioning)
of the whole data set. This task is often formulated as a minimization of some cost
function, and is carried out by some optimization method ([SU88, HH93, AL96]).
The question considered in this paper is the ability of very simple algorithms, such as
connected components (CC) algorithm, to provide good grouping results. We shall consider
this question in the context of local grouping cues, which are valid only when the two features
are close. This is the situation in the most common task of grouping the edgels on a smooth
curve.
To make our predictions useful in other grouping domains, we follow [AL96] and characterize
the cue only by its reliability. Here, we shall consider a binary cue (an inherent
choice for the connected component algorithm), which provides a value "1" if its decision is
that the two features belong to the same group and "0" otherwise. In this case, the cue's
reliability is quantified by the two error probabilities ffl fa and ffl miss , giving the probability to
make a false decision of "1" and "0" respectively.
Following [AL96], we use the following graphs to describe the information available from
the cues. First, we specify an unlabeled graph, denoted Underlying graph, G u , which represents
the data features pairs which are tested by the cues. In this graph the vertices stand
for the feature points themselves and the vertex pairs corresponding to interacting pairs (i.e.
to pairs of features which are tested by the cue) are connected by an arc. Then the results of
the cues are used to specify another graph, denoted a measured graph, Gm , in which an arc
exists only if it exists in G u and if its corresponding cues got the "1" value. In this graph
notation, the grouping process is a partitioning of the graph into subgraphs. In [AL96] we
looked for a partitioning, which maximizes the likelihood of the cue results. Here we shall
use the much simpler CC criterion.
Thus, in this particular paper, we make the following choices:
1. Cue - As described above, for the analysis we shall use an abstract binary cue, characterized
only by its miss and false alarm probabilities. In the experiments we shall
use a common cue, based on a combination of co-circularity, proximity and low curva-
ture, which is commonly used for the task of grouping edgels on a smooth curve and
is described in detail in [AL97].
2. Underlying graph - Recalling the local nature of all cues that are used to group
edgels on a smooth curve, we shall restrict the pairs of features, which are tested by
these cues, to those which are R-close (R, denoted "interaction radius", is a parameter
of the grouping process). Thus, the Underlying graph, G u , is locally connected and
every vertex is connected to a varying number of vertices corresponding to R-close
features. similar graph connecting every vertex with a fixed number of its closest
neighbors [AL96] could be used as well.)
3. Cue integration by connected components - The integration method is extremely
simple - all vertices in the same connected component of the measured graph, Gm are
hypothesized to be a single group. That is, every two vertices in the same group (and
only these vertex pairs) are connected by a sequence of arcs in Gm .
The proposed grouping (or more precisely, cue integration) criterion is definitely not new
and was used for say, clustering, in classical applications of pattern recognition. It may be
implemented by extremely fast algorithm, which is linear in the number of arcs [CLR89].
Note, however, that one path of pairwise grouped cues suffices for grouping two features,
and that any other evidence for placing this feature pairs in a separate groups is ignored.
Therefore, the grouping result is expected to be sensitive to false alarms. The main analytic
part of this paper considers this sensitivity, and analyses the quality of the grouping results
available from this simple algorithm.
Measuring the quality of grouping is a delicate issue, as in many practical cases situations,
it is not straightforward or even possible to specify the "correct" result for a grouping process
(An indirect evaluation of the grouping quality is possible by measuring its effect on higher
processes (e.g. recognition, see [Jac88, SB93]). Still, we shall assume here that such a
specification exists, in the form of image partitioning to several subsets. In the simplest
form, which we consider first, the image is partitioned into a "figure" subset and a noise
"background" subset.
One quantifier of the grouping quality is the number of background points which are
erroneously connected to the figure. Such false additions may be eliminated however by
making the interaction radius R sufficiently small. A grouping algorithm associated with
such a small R value cannot be considered to be satisfactory, however, as it will probably
break the true groups into parts (or delete elements from them). Therefore, it is the tradeoff
between false additions and fragmentation of the figure, which should be evaluated. The
next sections are devoted to calculate these quality measures.
3 Estimating the number of false additions
3.1 General
We analyze the CC grouping algorithm relative to a random image model, approximating the
common realistic case of a curve like set "figure" object embedded in a uniformly distributed
"background" clutter. We assume, for simplicity, that this curve like set, or figure, is a
straight line. More specifically, feature point distribution is modeled on a discrete image:
the figure is a set of collinear pixels (e.g. one row). The probability that we have indeed a
feature point in a pixel belonging to the line is ae f . The background noise may appear in all
non-figure pixels with probability ae bg . See Figure 1a for an instance of this random model. (If
the curve differs from the straight line, but is still associated with a low curvature, we expect
similar results, and this is indeed revealed in the simulations.) Note that four probability
parameters are involved: ae f and ae bg which characterize the image, and ffl fa and ffl miss which
characterize the cue reliability.
Our ultimate goal in this section is to find an analytic expression for the expected number
of background feature points connected to the figure. It turns out, quite intuitively, that this
number grows with both the false alarm probability ffl fa , the density of background features
ae bg , and the interaction radius. The expressions for the number of false additions reveal that
these are the result of two growth processes: one related to features in the vicinity of the
figure and one related to the other features.
The growth in the number of false additions of this second type may even lead to "explo-
sion": A connected background feature, which has many neighbors in the R radius, together
with a cue characterized by a false alarm rate which is not too low, imply that there will be
at least one neighbor feature, connected to it with high probability. If the same conditions
hold for all background features, then it is likely that almost all the image features will join
the figure in one large group, making the result of the grouping process useless. Note also
that for the sake of simplicity we shall consider an infinite image, characterized by the above
random model. This way we do not have to consider the effect of image boundaries. The
total number of addition errors and the number of fragments tend to infinity as well and
therefore we shall consider their normalized value relative to a unit length of the figure.
To quantify this behavior in an analytic simple way, which gives more insight into the
process, and provide simple design parameters, we take a continuous limit approximation,
and show that the false addition process behavior is regulated only by one parameter, N
example, determines whether the false addition
process converges or not. The critical value of this parameter is 1. That is, if the process
converges then N bg ! 1. Note that this parameter depends on R, which may be set to satisfy
the condition. If R is larger then the process "explode" and we get an infinite number of
features in the large groups (or practically, all the image becomes one large group). If R is
substantially smaller then it is likely that only little false additions exist.
3.2 Distance and connectedness layers
Intuitively, the probability of finding a connected point in a particular non-figure (i.e. back-
ground) pixel, ae c (L), depends on the distance from the figure, L (see Figure 1b): closer
background points are more likely to erroneously connect to the figure. The expected number
of false additions per unit length (pixel size) of the figure is
false additions =X
ae c (L): (1)
Background points, falsely connected to the figure may be directly connected to the
figure but may also be connected to other background points which are already connected.
For our analysis we distinguish between these types of connections using the concept of
connectedness layer (see Figure 2). A background point, directly connected to the figure is
in the 1-st layer. A background points, which is connected to a point in the i\Gammath layer, but
does not belong to any of the j \Gammath layers, is in the (i
c (L)
be the probability of finding a connected point which belongs to the i-th layer in a particular
background pixel in distance L from the figure (see Figure 1b). Clearly,
(a) (b)

Figure

1: An instance of probabilistic model (a). ae f is a density of point in figure (or
probability to find a figure point in given point of a line). ae bg is a density of background
points (it is the probability to find a feature point in a given background image pixel). For
the image (a) ae 0:05. In the analysis we consider the probabilities as
a function of the distance L of the background feature V from the figure (b). (R is an
interacting radius.)

Figure

2: The layers in the Measured Graph: a layer consists of all the feature between two
dotted curves (and some more features in the other side of the figure which are not shown
here). Note that, here, the many arcs between figure points are not shown and only the arcs
associated with false alarms are shown.
ae c
ae (i)
c (L) (2)
Estimating the number of false additions, (eq. 1), is the goal of this section, and the
rest of it is devoted to this calculation. The results are demonstrated in Figure 4: if R is
larger than some threshold (6), then the the probability to find a connected feature point in
a pixel, in distance L from the figure does not decrease with R, meaning we find connected
features over all the plane. If it is smaller then the process converges.
3.3 Directly connected points
The false addition process begins close to the figure by the features which are directly
connected to the figure. More specifically, the probability of a particular feature point v, in
distance L from the figure, to be directly connected to the figure, P (1)
c (L), is the probability
that at least one arc connecting the background point to the figure points in the underlying
graph is associated with a false alarm error. Although the values taken by the cues are not
necessarily independent random variables, we shall rely on this pragmatic assumption in our
analysis, and get
For L - R, the number, m, of figure points which are R-"close" to v is binomially distributed
with probability ae f and maximal value
Therefore, the probability ae (1)
c (L) to find a 1st layer background point in a
particular background pixel, is
ae (1)
3.4 Indirectly connected points
As mentioned above, connected background points (e.g., directly connected points) are a
potential source to additional false connections. Consider now a point v, which does not

Figure

3: A non-connected feature point,at distance L from the figure, may join the connected
set if it is connected to a another, connected background point (which is in distance X from
the figure). (This figure comes, mostly, to illustrate these distance).
belong to any of the first layers. The probability that this point is in the i-th layer,
is the probability that it is connected to at least one point of the i \Gamma 1-th layer in its R-
neighborhood (Figure 3). Note that in contrast to directly connected points (1st layer), we
refer now to background points in any distance from the figure. Let Q c
(X; L) be the
probability of point v at distance L from the figure, to be connected to at least one point of
the (i \Gamma 1)-th layer, which is X-distant from the figure. Let Q c
(X; L) be its complement.
Then,
Let m be the number of points, X-distant from the figure and R-close to v. This number
is binomially distributed with probability ae (i\Gamma1)
(X) and maximum value
defined in eq. (4)). Therefore,
ae (i\Gamma1)
The probability that a given pixel contains a point from the i-th layer, ae (i)
c (L), is equal to
the product of the probability ae (i\Gamma1)
that the pixel contains a feature point which does
not belong to the previous layers and the probability that this point, if it indeed exists in
this pixel, belongs to this layer, P (i)
ae (i)
c (L)ae (i\Gamma1)
where by definition:
ae (i)
ae (j)
Inserting (6) and (9) into (8), we get
ae (i)
ae (i)
c (L)
!/
Inserting eq. (7,8) in eq. (10) and then in eq. (2), indeed gives the expression we required for
the number of false additions. The result for particular ffl fa , ae f , ae bg is shown on the figure 4.
When the interaction radius is small the number of connected points decrease as a function
of distance. When it is even smaller, then the total number of false additions remains finite
(and in most such cases relatively small). When the interacting radius however, becomes
larger (R ? 5, for the example related to Figure 4) the total number of connected points
does not decrease to zero but remain finite for all distances. And as an interacting radius
is larger the part of the connected points for increases. For large R, about all
background points are connected to the figure.
Note that the false additions may be roughly divided into two major sets: the directly
connected point, the number of which is upper bounded and which lie close to the figure and
the indirectly connected features, which may be anywhere. The process of adding connected
points may diverge and then the second set is naturally dominant. If the process converges
however, then the first set is a substantial fraction, if not the dominant part, of the connected
points. See, for example, Figure 5 for a comparison of the number of false additions of the
first type with the total number of false additions. Therefore, we considered both processes
in our analysis and also in the continuous approximation considered now.
continuous limit expression for the number of false additions
The previous derivation provided the expression for the required number of false additions,
and looking at the graphs may give us some intuitive idea about its behavior. In this sec-
tion, we shall strengthen this intuitive understanding by showing that the results essentially
depend on two inherent parameters. The main tool that we use is a continuous limit expres-
sion, that is, a substitution of binomial distributions by the normal one. The same process
may be done without this approximation and with strict rigorous bounds, but it is somewhat
less elegant, and is not considered here.
3.5.1 Directly connected points - continuous limit expression
For directly connected background points we may approximate the binomial distribution in
eq. (5) by normal distribution and thereby write down the continuous limit expression for
probability P (1)
c (L) for a given point v to be directly connected to the figure:
c =ae
This gauss integral can
be evaluated in a closed form:
Note that this probability may be interpreted as a variation over a more intuitive expression,
This approximation is easily obtained by assuming that the
number m, of figure points which are R-close to a background feature point is not a random
variable but a deterministic number, equal to the expected value of the random variable,
m(L). The correction (1 is due to the non-proportional (higher)
contribution of small m values to the integral (eq. 11).
s
R
where

Figure

4: The probability to find a connected feature point in a pixel, in distance L from
the figure, ae c (L) for ffl
Figure

5: For low interaction radii, the main contribution to the false additions comes from
the directly connected points. Here for example, we compare between ae c (L) and ae (1)
c (L), for
situation when the number of false additions converges, ffl
ae
is the average number of feature points from the figure which are falsely connected to a
background feature, which lies just of the figure 0). Note that 2Rae f is the expected
number of R-close feature points, 2Rae f ffl fa is the expected number of these features for which
the cue makes a false (positive) decision, and the rest is just the correction factor implied
by the uneven contribution to the integral (eq. 11). We can see that the P (1)
c (L) expression
depends only on m c and normalized distance L=R.
3.5.2 Indirectly connected points
The continuous limit treatment of indirectly connected points is similar. Recall that Q c
is the probability that a feature point (L-distant from the figure) does not join the i\Gammath layer
by a false positive cue related to it and to another background feature point which belongs
to the layer and is X \Gammadistant from the figure. Approximating the binomial
distribution by the normal one, we get
where -(X;
c (X)). Note that -(X;
expected number of
background feature points, belonging to the (i \Gamma 1) which are X \Gammadistance from the figure
and R\Gammadistant from a feature point which L\Gamma distant from the figure. Again, this is a gauss
integral, and a close form evaluation is possible:
c (X)) log(1\Gammaffl fa )=2) (16)
Again, this probability may be interpreted as a variation over a more intuitive expression,
resulting from a simplifying assumption that the number m,
of background neighbors, is deterministic, and equal to the expected value -(X; L). The
meaning of an additional term
c (X)) log(1 \Gamma ffl fa )=2) is exactly the same as in the
case of directly connected points.
Replacing ffl fa by the small value approximation of
Using this expression we can rewrite the expression, (6),for the probability of the given point
v on the distance L to be connected in layer i to the figure:
where the last approximation is due to ae (i\Gamma1)
being much smaller than one in normal
conditions.
Substituting -(X; L) into eq. 18, and approximating the sum as an integral, we get
ae (i\Gamma1)
is the normalized distance. The equation 19 specifies a recursion, which
eventually determines the amount of false additions. To make the analysis more intuitive,
and to get rid of some constants, we prefer to use terms related to these numbers of false
additions. Specifically, let
c (l)
c (l)
The meaning of N (i)
c (l) is roughly the average number of connected points inside a disk of
radius R, which are added on the stage i. N (i)
free (l) is the "potential number" of new points
to be added in the next stages. Note that it depends on ffl fa as more reliable cues reduce this
potential, and that initially it is equal to N bg .
multiplying eq. 19 by N (i)
yields the following recursive relation on N (i)
c (l)
Note that, naturally, the higher the number of features added in one layer, the higher will be
the number of features added in the next layer, if there is still a sufficient "potential number".
(The meaning of the exponent term is an average of N (i)
c (l) over an R-close circle.)
The obtained evolution equation depends only on one intrinsic parameter N bg (eq. 20)
and the system evolutes according to its value.
Note now that the total number of background points connected to the figure (per unit
length of it), is proportional to
Z 1ae c (L)dL. This integral converges only when ae c (l) ! 0
for l ! 1. Since ae c (l)(=X
ae (i)
c (l)) is proportional to N c (=X
c (l)), we may find the
necessary convergence conditions for ae c (l) by evaluating this condition for N c .
3.5.3 A necessary condition for convergence
We shall make the assumption that N (i)
c (l) is a smooth function and that, for l AE 1, its
value is at most linear in l. Therefore the integral in (21) may be evaluated,
\GammaN (i\Gamma1)
\GammaN (i\Gamma1)
c (l)
We are interested in the necessary conditions for the convergence of N c to zero. Therefore,
we may assume that N (i\Gamma1)
c (l) is small and expand the exponent as a power series in N (i\Gamma1)
c (l)
up to the linear term, leading to the
c (l): (23)
This series always converges, as the number of features in any particular distance from
the curve (or in any finite distance range) is bounded. For the convergence of the sum N c ,
we should ask for a faster convergence, which for a given number of added features in one
layer adds a smaller number in the next layer. If we do not require that then the process of
adding false additions in increasing distances from the figure does not stop as more features
re available in these larger distances. Note however that if N c converges, then for large l,
very little fraction of the features are connected and thus N (i)
. Then the relation 23
becomes the geometric progression
c - N bg N (i\Gamma1)
c (24)
and the condition for convergence is simply N bg ! 1.
.
ss sssss ssssssssss
s

Figure

The model of fragmentation: to make a single break, some cues must be missed
4 The fragmentation errors and the implied tradeoff
As mentioned above, quantifying performance by counting only the number of false may
lead to absurd results. The trivial grouping algorithm, which does nothing and specify every
feature as a separate group is a perfect algorithm according to this criterion, but is of course
useless. Therefore, we add a balancing performance criterion: the number of fragments to
which a true group decomposes.
The probability of separating the figure between two particular data features on it, P frag ,
is approximately equal to the probability of missing all arcs passing there (see Figure 6).
This approximation neglects the possibility to connect the parts of the figure via background
points, which is of much lower probability as it requires two false alarms. This simplest
approximation of the process, implies that breaking the curve requires a multiple number
of misses, for all pairs of feature points on the figure lying in opposite sides of the break
point. The expected number of such pairs is roughly
and gives the
approximated probability of fragmentation:
f
This expression demonstrate that increasing the interaction radius, exponentially decreases
the probability to break the curve at that point (see similar analysis in [AL96]).
Thus, choosing a small interaction radius, reduces the number f false additions (by reducing
increases the fragmentation. This tradeoff is plotted in Figure 7. (Note
the logarithmic scale of P frag axis on this figure). The plot is done for a particular set of
scenes and cue parameters: ffl which is typical
for real images. For these parameters, we can see that choosing a low interacting radius
added

Figure

7: The tradeoff between the expected number of false additions (plotted, normalized
to the length of the figure curve, as the vertical coordinate) and the expected number of
break point for every length unit of this figure curve (horizontal coordinate) for ffl
0:2. The points on the graph correspond to
to left).
(e.g. produces acceptable fragmentation. Choosing a larger radius, gives only
a negligible improvement in fragmentation, but significantly increases the number of false
additions. Therefore, it is not advisable. Choosing a lower radius, on the other hand, causes
significant fragmentation.
5 Experimental Results
To check our model and the implied predictions we implemented the connected components
algorithm and applied it to several synthetic and real examples. We describe two of these
experiments.
5.1 Synthetic Image
Synthetic images may be created together with ground truth and therefore, may be used
to to test the theoretical aspects of the predictions. We used an image containing several
clean "blobs", edge detected it, and then removed 0.2 of the edge points in random locations.
Then, we added random shot noise in 0.05 of the rest of the pixels. (See Figure 8a ). This
image includes a little less than 1000 figure points and about 3500 background points.
We used a common co-circularity cue, developed in [AL97], which could be tuned by
changing an internal threshold so that Miss and False alarm probabilities could be traded.
We also checked it with a synthetic cue, relying on a known ground truth, which made a
mistake with controlled probabilities. The later case, of course, is not a realistic task, but it
helps to understand the algorithm behavior.
Consider the grouping results obtained with the co-circularity cue for various interacting

Figure

8). The three right images (Figure 8b, 8d, 8f) show the large groups (larger
than 20 edgels each) for three interacting radii (R = 3; 5; 7). Increasing R clearly decreases
the fragmentation and increases the number of false additions. Note that for the two smaller
radii, all the large groups are dominated by figure points. It is clear that CC grouping is
useful as an initial stage of grouping, which separates figure from background, or even as an
independent grouping algorithm by itself.
It is difficult to measure the number of false additions per unit length of the extracted
figure segments. Instead, we estimated the lengths of the groups by the number of figure
points inside them, and estimated the false additions measure as the ratio between the
number of figure points (known from ground truth) and the background points (the rest of
the points) in the relatively large hypothesized groups. (Large groups were specified either
as larger than 10 features or 20.) This false addition measure is plotted as a function of
interaction radius in figure 9 (for groups larger than 10). Note that for low R values, the
number of false additions increase slowly, but after some threshold it starts to rise much
quicker, until it saturates, due to the finite size of the image.
The fragmentation is measured indirectly by the number of groups containing more than
or 20 points. These numbers are plotted as a function of radius in Figure 10. For small R
Initial Image (a)
largest group (c)
largest group

Figure

8: Grouping results for the synthetic example: the input image (a), all groups larger
than 20, for various R values (R = 3; 5; 7), superimposed, and the largest group for 7.
Note for example, that for substantial groups which are relatively clean, and
that for the larger group is similar to the larger true groups, with still relatively little
false additions.
Figure

9: The number of false additions per unit length as a function of interacting radius
for the synthetic image and the co-cirulcar cue. Note the slow growth for low interacting
radii and the saturation for very large radii
values, increasing the radius leads to a lower number of groups and to lower fragmentation.
For the groups consist of almost only figure points, but they are very fragmented,
and only part of the figure points participate in large groups (see Figure 8b). For moderate
R values (of say the fragmentation is moderate, especially when recalling that
originally the figure consists of 8 smooth curves. Then, for larger R values, clutter groups
are created and increase the number of large groups. For such values the increased number
of groups does not reflect fragmentation but rather the additional clutter group. Finally, for
larger (say 12) R values, all groups merge into just a few (useless) groups, which contain
both the figure and almost all the clutter.
A most interesting issue, is the validity of our modeling and the implied predictions.
Qualitatively, we already found that increasing the interaction radius increases the false
additions, as implied also by our model. More quantitative results are shown in Figure 11,
which gives the false additions rates, for the co-cicularity cue described above, for a co-
circularity cue associated with a different threshold and a lower false alarm rate (the left and
right thick curves in the figure, respectively). The other curves in this figure correspond to
the synthetic cues with false alarm probabilities of (left to right) ffl
We estimated the false alarm rate of the experimental cues by simply dividing the number
Radius

Figure

10: The number of groups larger than 10 and 20 feature points as a function of
interacting radius. The top curve is the number of groups larger than 10 and the bottom
curve is the number of groups larger than 20.
of arcs in the measured graph by the number of arcs in the underlying graph, (excluding
the figure-figure arcs from both counts). These empirical false alarm rate turned out to be
for the two thresholds.
We can see that the synthetic cue provides an upper bound on the real results, which
is relatively close, especially if we compare these results to the proximity-only cue (ffl
most left curve). There are some discrepancies, though, and we attribute them to one
cause: it seems that, in contrast to our assumptions, the cue's behavior suffers from cross-
dependence. This is especially true for clutter features which are close to the figure: if a
feature is connected to one edgel on the figure, it is more likely to be co-cirular and to be
connected to others as well. We estimated from our measurements that for R = 5, the
average number connecting a clutter feature to the figure, if it is connected, is 3, which is
much more than the expected value of 1, calculated relying on the empirical ffl
and the average number of figure neighbors (about 5-6). Therefore, the effective false alarm
rate of the cue is much lower than the measured and is roughly 0:16=3 - 0:05. (Recall that
in order to add a feature to the figure, the CC algorithm requires only one connection.) If
we take this rough approximation we can see a nice agreement, for small R values, between
the real cue behavior and the behavior of the synthetic cue.
For feature points far from the figure, the cross dependence exists but is much weaker.
Therefore, the effective false alarm rate is not as measured empirically but is also not as
low as when the feature is close to the figure. Indeed we get a nice match with the curve
associated with synthetic cue and ffl We believe that the cue is more reliable near the
figure, because there, the feature points are excluded from the location of the figure itself
where the highest probability of false alarm exists.
Although we get fairly accurate results with our current analysis, we intend to incorporate
the non-independence effects quantitatively in our future predictions, and to develop methods
for measuring both the cross dependence and the effective false alarm rate of cues.
We found that a necessary condition for convergence is that N bg ! 1, where N
ae bg is first specified in eq. 20. This condition imposes an upper
bound on the interacting radius which is 6:58 (if we take ffl 0:16, as found empirically) or
8:20 (if we take ffl as seems to be the effective value - see above). Indeed, it is possible
to see from either Figure 11 or from Figure 10, that an R value of 7 \Gamma 8 is the threshold and
that using a larger interaction radius leads to excessive number of groups and large growth
in the number of false additions, which means that background features aggregate together
into groups of their own.
Regarding the speed of the algorithm, we distinguish here between the extraction of
the perceptual information stage, in which the underlying graph is calculated and the cues
are measured, and the stage of the connected components "integration". The first stage is
required in every grouping algorithm, and requires an effective means for finding the closest
neighbors for fast operation (see [AL97]). The connected components algorithm is linear in
the number of cues (or arcs of G u ). In our experiments it always ran in less than a second.
(See figure 12 where the different curves correspond to the different cases of Figure 11).
5.2 Real Images
Every algorithm should be tested on real images as well. Here we started with an even
harder task, and applied the CC algorithms to a corrupted real image, which itself was
not too simple. Specifically we took a 256 \Theta 226 CT head image, applied some standard
Radius

Figure

11: The number of false additions per unit length as a function of interacting radius.
The darker curves corrrespond to the co-circularity cue with two different thresholds. The
lighter curves correspond to a synthetic cue characterized by ffl
to right): The true cue behaves approximately as a random cue associated with false alarm
probability of 0:05 \Gamma 0:10.
Execution time
Radius
User
time
netto
(sec)

Figure

12: Execution CPU time of the connected components algorithm as a function of
interacting radius. All cases considered for the synthetic cue are superimposed.
(Khoros) edge detection process on it, left ae 0:8 of the edge points and, and added
additional clutter in the form of shot noise, in 0:05 of the pixels (see figure 13a). Note
that in fact ae bg ? 0:05, as the edge detection process itself adds much clutter. The results
for different radii (Figure 13b,d,f) show the same qualitative behaviour as described above
for the synthetic image. Due to the high density of the figure points, the grouping process
collapses to a single large group containing all the figure for relatively low interacting radius

Figure

however that much of the added clutter, is removed also in this
non-optimal choice of R. Note also that if we choose then the large groups include
the main parts of the figure (Figure 13d). Furthermore, the groups created in this stage (e.g

Figure

13c) may be the input to a more complex grouping process that will run at a reduced
computational cost due to the significantly lower amount of features.
It should have been natural to test the algorithm on the easier case of real images which
are not so corrupted, as these are the normal operation conditions. For some technical
reasons, we could not test this case at the time of submission.
6 Conclusions
The connected components approach leads to an extremely fast grouping algorithms, which
unfortunately provide grouping that is sometime inferior relative to more complex algorithms.
In this paper we considered this approach and provided, for the first time, an analysis, capable
of predicting the grouping quality in terms of measurable, meaningful quantities. These
results may be used do optimize the CC grouping algorithm by choosing the interaction
radius R, and if possible, by tuning the error probabilities (of the cue) within the given
limitation. It can also help to discriminate between an easy grouping task, which may be
carried out fast by the CC algorithm, and the more difficult tasks, which require a more
complex, slower, approach.
It seems that many grouping tasks may be decomposed into easier and more difficult
sub-tasks. For grouping edgels on smooth boundaries, for example, connecting the edgels
to short segments is relatively easy, but calculating the final image partition, requiring to
take into account occlusions, junction structure, etc., is a global process which seems more
Initial Image (a)
largest group (c)
largest group

Figure

13: Grouping results for corrupted CT image (head)
Initial Image (a)
largest group (c)
largest group

Figure

14: Grouping results for CT image (head)
difficult. Thus, one application of the CC grouping approach is as a preprocessor to more
complex grouping algorithms.
The paper describes work in progress and many directions are open for improving the
basic algorithm, and also its analysis. Characterizing the cues without the independence
assumption, which was mentioned above, is expected to lead to more accurate predictions.
Developing efficient, postprocessing, cleaning algorithms is of much practical interest as well.



--R

Quantitative analysis of grouping processes.
Ground from figure discrimination.
Space and time bounds on indexing 3-d models from 2-d images
Introduction to algorithms.
Object Recognition by Computer.

The Use of Grouping in Visual Object Recognition.
Robust and efficient detection of salient convex groups.
Perceptual Organization and Visual Recognition.
Perceptual organization in computer vision: A review and proposal for a classifactory structure.
Structural saliency: The detection of globally salient structures using locally connected network.
On the role of structure in vision.
--TR
Introduction to algorithms
Object recognition by computer
Recognizing solid objects by alignment with an image
Space and Time Bounds on Indexing 3D Models from 2D Images
Perceptual Organization for Scene Segmentation and Description
Robust and Efficient Detection of Salient Convex Groups
Random perturbation models for boundary extraction sequence
A Generic Grouping Algorithm and Its Quantitative Analysis
Perceptual organization in computer vision
Use of the Hough transformation to detect lines and curves in pictures
Perceptual Organization and Visual Recognition
Perceptual Organization for Artificial Vision Systems
Figure-Ground Discrimination
B-spline Contour Representation and Symmetry Detection
Normalized Cuts and Image Segmentation
quantitative predictions;perceptual organization;connected components algorithm;grouping performance analysis