A Generic Grouping Algorithm and Its Quantitative Analysis.
AbstractThis paper presents a generic method for perceptual grouping quality. The grouping method is fairly general: It may be used the grouping of various types of data features, and to incorporate different grouping cues operating over feature sets of different sizes. The proposed method is divided into two parts: constructing a graph representation of the available perceptual grouping evidence, and then finding the "best" partition of the graph into groups. The first stage includes a cue enhancement procedure, which integrates the information available from multifeature cues into very reliable bifeature cues. Both stages are implemented using known statistical tools such as Wald's SPRT algorithm and the Maximum Likelihood criterion. The accompanying theoretical analysis of this grouping criterion quantifies intuitive expectations and predicts that the expected grouping quality increases with cue reliability. It also shows that investing more computational effort in the grouping algorithm leads to better grouping results. This analysis, which quantifies the grouping power of the Maximum Likelihood criterion, is independent of the grouping domain. To our best knowledge, such an analysis of a grouping process is given here for the first time. Three grouping algorithms, in three different domains, are synthesized as instances of the generic method. They demonstrate the applicability and generality of this grouping method.
Introduction
This work proposes a generic algorithm for perceptual grouping. The paper presents the new
approach, and focuses on analyzing the relation between the information available to the
grouping process and the corresponding grouping quality. The proposed generic algorithm
may serve to generate domain specific grouping algorithms in different domains, and we
implement and test three of them. However, the analysis is domain independent, and thus
applies for the specific cases.
Visual processes deal with analyzing images and extracting information from them. One
reason that makes these processes hard is that only a few subsets of the data items contain the
useful information while all others are not relevant. Grouping processes, which rearrange
the given data by eliminating the irrelevant data items and sorting the rest into groups
each corresponding to a certain object, are indispensable in computer vision [WT83, Gri90,
The Gestalt psychologists already noticed that humans use some basic properties, which
may be called grouping cues ([Low85]), to recognize the existence of certain structures in a
scene and to extract the image elements associated with such structures, even before it is
recognized as a meaningful object [Wer50, WT83, Low85, Gor89]. In the field of computer
vision, Witkin and Tenenbaum [WT83], suggested that grouping processes should be part
of all processing levels. Indeed , grouping was used in many levels, starting from low-level
processes such as smoothness based figure-ground discrimination [SU88, HH93], through
motion based [AW94, JC94, Sha94] grouping, which may be considered to be mid-level
processes, to high-level vision processes such as object recognition [HMS94, ZMFL95].
The proposed method separates between two components of the grouping method: the
grouping cues that are used and the grouping mechanism that combines them into a partition
of the data set. Like most grouping methods, the grouping mechanism used here is formally
defined as the maximization of some consistency function between the group assignments and
the given data. This maximization is usually done by various methods, including dynamic
programming [SU90], relaxation labeling [PZ89, TJA92], simulated annealing [HH93], and
graph clustering [WL93], and may also be done hierarchically [HMS94, MN89, DR92]. The
proposed algorithm also maximizes a function: the likelihood of the data available relative
to the grouping decision. The crucial difference which exists however between the proposed
algorithm and all previous work is in the analysis we provide, which predict the grouping
performance based on the reliability of the data.
Our specific grouping process is based on representing the unknown partition into groups
as in the form of a special graph, in which the vertices are the observed data elements
(edges,pixels, etc.) and the arcs contain the grouping information and are estimated by
cues. (Others, e.g. [HH93, SU88, WL93], have used graphs for grouping algorithms, but we
use it differently here.) The grouping task is divided into two parts: constructing the graph
by applying the geometric knowledge on the data, and then finding the "best" partition of
the graph into groups. Both stages are implemented using known statistical tools such as
Wald's SPRT algorithm and the Maximum Likelihood criterion.
Grouping cues are the building blocks of any grouping process, and shall be treated as
the only source of information available for this task. They are used, in the first stage of
our algorithm, for constructing the graph. In general, they are domain specific and rely
on the assumed properties of the sought-for groups. Their choice is essentially made by
taste and intuition although more rigorous statistical properties are sometimes taken into
account [Low85, Jac88, Cle91, CRH93]. The well-studied task of grouping edge points lying
on a smooth boundary, is a good example for the variety of perceptual grouping cues. The
typically used cues are collinearity, co-circularity [Sau92], curvature and length [SU90, PZ89],
proximity, and some combinations of those [DR92, HH93, GM92]. In other domains, or
under different assumptions, other cues are used (e.g. motion based cues [JC94, AW94],
symmetry [HMS94], or 3D symmetry-based invariance [ZMFL95]). Although good cues are
essential for successful grouping, finding them is not our aim here. Instead we consider
the cues as given, and focus on quantifying their reliability, and its relation to the expected
grouping quality. We model the cues as random variables, and quantify their reliability using
the properties of the corresponding distribution. Moreover, we suggest a general method,
denoted cue enhancement, for improving the reliability of a cue, and show a tradeoff between
computational efforts and the achieved reliability of the enhanced cue.
Although many grouping methods were already suggested and tested, it seems that no
solid theoretical background was established. So far, the performance of the grouping algorithms
has been assessed by implementing the algorithm, testing it on a small number
of simulated or real examples, and then visually evaluating the results. This methodology
shows that some of the grouping methods perform well on the examples tested and
indeed succeed in partitioning the image elements into seemingly correct subsets. It does
not allow us, however, to predict the performance of these algorithms on other images or
to compare the algorithms whose assessment was carried out using varied examples. The
proposed quantitative analysis of the expected grouping performance, provides some relations
between the quality of the available data, the computational effort invested, and the
grouping performance, quantified by several measures.
The grouping algorithm we propose is generic and domain specific grouping algorithms
may be synthesized as instances of it by inserting the appropriate cue and topology specification
(in the form of a graph). The analysis, which applies to the generic abstract algorithm,
may be useful for predicting the results in the specific domains.
The main new contributions of this paper are:
a. A fairly general approach to grouping, which is applicable to several domains, and tested
in three of them. Most, if not all, previous algorithms were domain specific.
b. A quantification of the expected quality of the grouping results. To our best knowledge,
such an analysis was not done before.
c. A cue enhancement procedure, capable to significantly improve the reliability of many
existing grouping cues.
The rest of this paper is organized as follows: It starts with a formulation of the grouping
task as a graph clustering problem. The graph-based grouping algorithm is follows, and its
theoretical analysis is described in Section 4. Section 5 is concerned with the cue enhancement
procedure, inluding a short review of Wald's SPRT algorithm. We tested our approach
also experimentally, providing three instances of the generic algorithm in three domains, and
some comparisons to the theoretical predictions. Some open questions and further research
directions are considered in the discussion.
2 The Grouping Task and its Graph Representation
2.1 The Grouping Task
be the set of data elements. This data set may consist of the
coordinates and grey levels of all pixels in the image, the boundary points in an image, etc.
S is naturally divided into several groups (disjoint subsets) so that all data elements in the
same group belong to the same object, lie on the same smooth curve, or associated with
each other in some other manner. In the context of the
grouping task the data set is given but its partition is unknown and should be inferred from
indirect information given in the form of grouping cues.
Often, only the elements in the last L groups satisfy this description while the elements in
the first group, S 0 , are considered as a non-important background. We should also mention,
that according to another grouping concept the hypothesized groups are not necessarily
disjoint. We do not consider this different task here but we believe that at least some of the
tools developed here are useful for analysing it too.
2.2 Grouping Cues
Grouping cues are the building blocks of the grouping process and shall be treated as the
only source of information available for this task. The grouping cues are domain-dependent
and may be regarded as scalar functions C(A) defined over subsets A ae S of the data feature
set. Such cue functions should be discriminative. For example, it should be high if the data
features in the subset A belong to the same object and low if they do not. Preferably,
they should also be invariant to change of the viewing transformation and robust to noise
[Low85]. Most of the grouping cues considered in the literature were functions defined over
data subsets including only two data elements. (Some exceptions are a convexity cue [Jac88]
and an U-shape cue [MN89].) Later, in section 5, we consider Multi-feature cues, defined over
data subsets including three data features or more, and show how to integrate the evidence
available from them into very reliable bi-feature cues. At this stage, however, we consider
only bi-feature cues which may be either the cues used by common grouping processes or
the result of the cue enhancement process described later.
Following the main goal of this work, to provide a general, domain independent, frame-work
for grouping processes, we would like to predict the grouping performance, not relying
on a detailed domain-dependent knowledge about a cue, but using only some measure of
its reliability. Such reliability measure may be defined by considering the cue function to
be a random variable, the distribution of which depends on the features set being in the
same group or not. For binary cues, this dependency is simply quantified by two error prob-
abilities: p miss is the probability that the cue C(A) indicates that the data features in A
do not belong to the same group while in fact they do. p fa is the probability
that the cue function indicates that the features of A belong to the same group, while in
fact they do not (false alarm). If both is an ideal cue.
(For the more general and not necessarily binary cue, this reliability is quantified by the
average log likelihood ratio of the cue.) This characterization can sometimes be calculated
using analytical models (e.g. [Low85]), and can always be approximated using Monte-Carlo
experimentations ([Jac88]).
2.3 Representing Groups and Cues Using Graphs
Our approach to the grouping process is based on representing both the unknown partition
into groups and the data available from the cues using graphs. The nodes of all the graphs
are the observed data elements, but the arcs may take different meanings.
The unknown partition, which is to be determined, is represented by the target graph,
composed of several disconnected complete subgraphs (cliques). Every such
clique represents a different object (or group) and there is no connection (arcs) between
nodes which belong to different cliques. A graph with this characterization is called a clique
graph and the class of such graphs is denoted G c . The nodes of this graph are available to
the grouping algorithm, but its arcs, which contain the grouping information, are hidden
and are not directly observable. Knowing that G t belongs to the class of clique graphs, G c ,
the grouping algorithm should provide a hypothesis graph, G should
be as close as possible to G t .
The cue information is described by two graphs. The underlying graph, G
specifies, by its arcs, the feature pairs which are evaluated (for being in the same group) by
the cue function and are available to the grouping algorithm. The second graph, denoted
measured graph Gm , specifies the information provided by these cues. That is an arc belongs
to Gm iff it belongs to G u and the result of the cue function indicates that the feature
pair belongs to the same group. While the underlying graph is specified by the designer,
depending on the domain and the computational effort limitations, the measured graph is a
result of the cue evaluation process and a part of the grouping process.
3 The Generic Grouping Algorithm
The generic grouping algorithm described in this section consists of two main stages: cue
evaluation for (many) feature pairs and maximum likelihood graph partitioning. The two
stages are general and do not depend on the particular domain in which the grouping is done,
except from the obvious choice of a domain-dependent cue and some associated decisions
made before the process.
3.1 Some Decisions To Be Made By The Designer
The first thing is to choose a grouping cue which naturally depends on the domain and on
the assumed characterization of the sought-for groups. The performance analysis, described
latter, provide some quantitative means to choose between alternatives cues, which may
differ, for example, by the tradeoff between false alarm and miss errors. In principle, all
feature pairs, corresponding to a complete underlying graph, (V; E c (V )), should be evaluated.
Hypothesis graph
G
G u
G
G
G
(set of groups)
Grouping cue
underlying
Create
graph
Data features set
Grouping by Graph Clustering
Underlying graph Measured graph
by
Graph clustering
max. likelihood
Decide for each
edge
Desired target graph

Figure

1: The proposed grouping process: The image is a set of data features (edgels in this
every one of which is represented by a node of a graph. The first step is to decide
about a cue and about the set of feature-pairs to be evaluated using this cue. This set of
feature-pairs is specified by the arcs of the underlying graph G The second step
is to use grouping cues to decide, for every feature pair in G u , if both data features belong
to the same group. These decisions are represented by the a measured graph
every arc corresponds to a positive decision (hence Em ' E u ). The known reliability of these
decisions is used in the last step to find a maximum likelihood partitioning of the graph,
which is represented by the hypothesized (clique) graph G h . A main issue considered in
this paper is the relation between this hypothesis G h and the ground truth target graph, G t ,
which is unknown.
Some cues are meaningful, however, only for near or adjacent data elements and are not
adequate for evaluating every feature pair. Therefore, the cue evaluation is restricted only a
subset of the feature pairs, specified by the spatial extent of the available cue. For example,
in order to detect long and smooth curves using co-circularity and proximity cues we may test
only close data feature pairs. On the other hand, when testing global cues like affine motion,
all feature pairs may be tested and contribute useful information. Another consideration
which affects the choice of the underlying graph is the reliability of the grouping process
and the computational effort invested in it. As we shall see, the reliability increases with
the density of the graph, but so does the computational effort, so some compromise should
be made. In this paper we don't investigate the optimal decisions at this stage but just
assume that both the cue and the associated adequate "topology" are either given or chosen
intuitively.
3.2 First Stage: Evaluate Grouping Cues
In the first stage of the grouping process, all feature pairs corresponding to arcs in G
are considered, one arc at a time, and the cue function is used to decide whether
the two data features belong to the same group (and the arc corresponding to them is in
the unobservable graph G t ). A simple decision may be obtained by any binary cue. A more
sophisticated and reliable process is to rely on multiple evidence based on other features, as
done in our cue enhancement procedure (section 5). The positive decisions are represented
by the measured graph decisions are made, Em is an estimate of
the projection of the target graph G t on the underlying graph G u . This measured
graph carries the information accumulated in the first stage to the second one.
Note that it is also possible to postpone the decisions, and mark every arc of the underlying
graph with the likelihood of the corresponding pair to be in the same group. Then,
the maximum likelihood partition stage proceed similarly. While this approach may yield
better results, due to the larger amount of information carried to the second stage, it requires
that the actual non-binary cue distributions are given, which is rarely the case, and is not
considered further.
3.3 Second Stage: Maximum Likelihood Partition of The Graph
Recall that every decision made in the first stage is modeled as a binary random variable,
the statistics of which depends on whether the two data features belong to the same group,
or whether they not. Therefore, the likelihood that this decision is indeed correct depends
on the true and unknown grouping.
Therefore, the decisions made in the first stage (and represented by the measured graph
Gm ), specify some likelihood for every partition of the graph into subgraphs. Choosing the
partition (or a clique graph) which maximizes this likelihood yields an approximation to the
required unknown target graph G t , which is one of the clique graphs. In the context of this
paper, the cue decisions assumed to be independent and are subject to two types of errors
specified uniformly by two error probabilities:
ffl miss
The error probability pair (ffl miss ; ffl fa ) is identical to the cue probability pair (p miss
the common direct use of bi-feature cues and is equal to the error probability of the cue enhancement
process (see section 5), which is usually much better. (Making these probabilities
nonuniform, and thus associating every arc of G u with an individual pair of error probabil-
ities, may be a more accurate model but requires much more accurate knowledge about
the error mechanism.) The likelihood of the measurement graph, Gm , for every candidate
hypothesis E) 2 G c , is then given by
Y
LfejEg (2)
where the likelihood of each edge is
ffl miss if e 2 EnEm
We propose now to use the maximum likelihood principle, and to hypothesize the most
likely (but not necessarily unique) graph
G2Gc
LfGm jGg: (4)
The maximum likelihood criteria defined by eq. (4) specifies the grouping result, G h , but
is not a constructive algorithm. Moreover, this class of optimization problems is known to
have high computational complexity (exponential), in the worst case. We therefore address
the theoretical aspect and the practical side separately.
From the theoretical point of view, we shall now assume that the hypothesis which
maximizes the likelihood may be found, and address our main question: "what is the
relation between the result G h , and the unknown target graph G t ?" This question
is interesting because it is concerned with predicting the grouping performance. If we can
show that these two graphs are close in some sense, then it means that algorithms which
use the maximum likelihood principle have predictable expected behavior and that even we
can't know G t , then the grouping hypothesis G h they produces is close enough to the true
partitioning. This question is considered in the next section.
From the practical point of view, one should ask if this optimization problem can be solved
in a reasonable time. Some people use simulated annealing, or other annealing methods, to
solve similar problems [HH93]. Others use heuristic algorithms [Vos92]. We developed a
heuristic algorithm which is based on finding seeds of the groups, which form (almost) a
clique in Gm . (Random graphs theory [Pal85] implies that cliques of a certain size are most
likely to be found inside an object, and are very unlikely to be found elsewhere in the graph).
Seeds are found as the highest entries in the square of the adjacency matrix of Gm . Then,
these seeds are iteratively modified by making small changes (such as moving one element
from one group to another, merging two groups, etc.), using a greedy policy, until a (local)
maximum of the likelihood function is obtained. In our experiments (described in section
6), this algorithm performs nicely. More details can be found in [AL95].
4 Analysis of The Grouping Quality
This section quantifies some aspects of the similarity between the unknown scene grouping
(represented by G t ), and the hypothesized grouping suggested by our algorithm (represented
by G h ). As we shall see, the dissimilarity depends on the error probabilities of the individual
arcs, ffl miss ; ffl fa , and on the connectivity , or the density, of G u .
The first result demonstrates that good solutions are not rejected.
LfGm jG
G2Gc
provided that ffl miss
Proof: For every clique graph, G(V; E) 2 G:
LfGm jGg
LfGm jG   g =@ Y
ffl miss
e2E u "(E   nE)
(arcs of E u , which exist in both (or none) of the two sets, E and E   , do not affect that ratio,
and therefore are not counted) 2
Borrowing the terminology of parameter estimation, this claim shows that maximum
likelihood partition is a consistent estimator. That is, arbitrarily reliable labeling of the
underlying graph, associated with very good cues, leads to a correct decision. From now on
we assume that ffl miss consistency is not ensured. In the more realistic
case, where some hypotheses regarding arcs of the underlying graphs may be wrong, we
shall show that grouping performance degrades gracefully with the quality (reliability) of
the cues and that this performance may be predicted. In general, grouping performance is
good for groups which are densely connected within the underlying graph, and is expected
to be worse for loosely connected groups. If, for example, a node (data feature) is connected
to its group by only one edge in the underlying graph, it may be separated from this group
in the hypothesized partition with probability ffl miss , which may be quite high.
We now turn into proving a fundamental claim on which most of the other results rely.
It is a necessary condition satisfied by any partition selected according to the maximum
likelihood principle. Consider two nodes-disjoint subsets of the graph
and denote their cut by J(V g. Let
l u denote the cut width relative to the underlying graph.
Similarly, let l m denote the cut width relative to the measurement
graph
necessary condition: Let G
be the maximum likelihood hypothesis (satisfying eq. (4)), and let
log(ffl miss
Then,
1. For any disjoint partition of any group V
2. For any two groups
l m
Proof: The proof technique is similar to that of claim 1. For proving the first part,
consider the likelihood ratio between two hypotheses: One is G h and the other, denoted
~
G h , is constructed from G h by separating V i into two different groups, V 0
Y
ffl miss
l
This likelihood ratio is a non-decreasing function of l m

Figure

2: The cut involved in
splitting a group into two (proof
of claim 2)
and is larger than 1, for l m - ffl u . Therefore, if the
claim is not satisfied, then ~
G h is more likely than G h
which contradicts the assumption that (4) holds. The
second part of the claim is proved in a similar manner.Qualitatively, the claim shows that a maximum likelihood
grouping must satisfy local conditions between
many pairs of feature subsets. It further implies that
a grouping error, either in the form of adding an alien
data feature to a group or deleting its member, requires
more than a single false alarm or a single miss, provided
that the "connectivity" of the underlying graph is high
enough. An addition error, for example, merging a group
with an alien node v   , requires that a substantial fraction
of the edges in J(V i ; fv   g), which none of them is
in E t , will be included in Em . That is, it requires many false alarms. The parameter ff,
specifying the fraction of cut edges required to merge two subsets reflects the expected error
if the false alarm probability is equal to the miss probability, then
the false alarm probability is higher, so is ff.
This condition is now used to show that choosing a sufficiently dense underlying graph
can significantly improve the grouping performance. We shall consider two cases: a complete
underlying graph, and a locally connected underlying graph.
4.1 Complete Underlying Graphs
A complete underlying graph connects every data feature with all others and provides the
maximal information to the graph clustering stage. Therefore, it may lead to excellent
grouping accuracy. On the other hand, as mentioned before, it is useful only for global
grouping cues, such as being on the same straight line, being consistent with an affine
motion model, etc. There are many types of grouping inaccuracies, and the following claims
consider some of them.
be a true data feature group. Then, the probability that a maximum likelihood
process will hypothesize a group V   containing k nodes of S i and a particular additional node,
i=kmin
Proof: Use claim 2 with note that l Merging these
subsets requires that at least ffl u of the edges connecting then are included in Em . This
event happens with a binomial distribution. 2
true group and a maximum likelihood hypothesized group
containing at least k nodes of S i . Then, the probability that V   contains k 0 nodes or more
which are alien to S i , is at most
\Gammaaliens -
Proof: Use claim 2 with and V to find the probability that a
particular data subset V
merges. Then, take a worst case approach, and sum these
probabilities over all subsets of a certain size j, and over all sizes higher than k 0 . 2
k10203040

Figure

3: Two predictions of the analysis: Left: A k-connected curve-like group (e.g. smooth
curve) is likely to brake into a number of sub-groups. The graph shows an upper bound on
the expected number of sub-groups versus the minimal cut size in the group, k (eq. 13). Here
the group size (length) is 400 elements, ffl miss = 0:14 and ffl (typical values for images
like

Figure

8). It shows how increasing connectivity quickly reduces the false division of this
type of groups. Right: Upper bound on the probability for adding any k 0 alien data features
to a group of size k, using a complete underlying graph (claim 4). The error probability is
negligible
true group and the maximum likelihood hypothesized group
containing the maximal number of data features from S i . Then, the probability that V
contains jS data features from S i is at most
\Gammadeletions -
i=kmin
miss
Proof: For any particular deleted subset S 0 ae use claim 2 with
note that l Such a split of S i requires that l m - ffl u . This
event happens with a binomial distribution. To find the probability that some subset of size
k 0 is deleted, we sum over all subsets, ignoring the dependency between the events which
can only decrease this probability. 2
Claims 3,4,5 simply state that if the original group S i is big enough and the miss and false
alarm probabilities are small enough, it is very likely that the maximum likelihood partition
will include one group for each object, containing most of S i , and very few aliens. The crude
bound, plotted in Figure 3(right) shows, as an example, that even for substantial cue errors
the probability for hypothesizing highly mixed subsets is small, provided that the group is
large enough (k - 15).
An even more practical performance measure, which we calculated using some approximations
is the expected number of addition and deletion errors.
Efk delete
i=kmin
miss
i=kmin
where k is the group size, k dffke. Experimental results for
these two grouping error types are given in Figure 9(c) and Figure 9(d).
The major difficulty we see with the use of a complete underlying graph is that it does
not apply to all the cues. It's especially concerns with cues that are meaningful only locally,
such as co-circularity for smooth curve detection. Therefore, another option, the locally-
dense underlying graph is also proposed.
4.2 Locally Dense Underlying Graphs
An intuitive choice of an underlying graph which is less dense than the complete graph is
to connect every data feature only to those data features in its neighborhood, either to the
closest k data features, or to all data features in a certain radius. When specifying such
a graph, it is important to keep a substantial connectivity between the data features of
objects so that accidental deletion will be less likely. This connectivity demand is quantified
by requiring the projection of every group on the underlying graph, to be
k-connected. That is, if any k \Gamma 1 nodes are eliminated, then this projected subgraph remains
connected. A nice property of k-connected graphs is that every cut in them contains at least
edges. Therefore, a deletion of a node requires at least ffk miss errors. Alien data features
are either densely connected to a group, implying that their incorrect addition to a group is
prevented with high confidence, or are not connected enough and are not considered at all
as candidates for addition.
A significant change from the case of complete graph is that ffk miss errors can cause the
deletion of a subgroup containing more than one data feature, a fact that demonstrates the
relative weakness of the locally connected underlying graph. Being aware of this weakness, we
choose to characterize the grouping performance by another measure: the expected number
of "large" subgroups to which the group decomposes. Consider a particular cut of size k in
the projection of some object on the underlying graph. The probability that the object is
divided in this cut into two parts is exactly
divide in
i=kmin
miss
Suppose now that we can estimate the number of "potential cuts", and denote this number
by N cut . Then, the expected number of group separation will be simply N cut p divide in k\Gammacut .
Fortunately, such an estimate may be done for the interesting case of curve like groups. Let
S i be a k-connected curve-like group in which the data features are ordered along some
curve. A separation of the curve into significant "large" parts, is associated with cuts which
separate a group of consecutive curve points from another group of consecutive curve points.
The number of such cuts is N Therefore, if we can guarantee that the number
of arcs in every one of these cuts is not less than k, then the expected number of parts into
which the curve decomposes is not higher than
divide in
i=kmin
miss This number, plotted in Figure
generally decrease with increasing the cut size k, but due to the non-constant
and non-monotonic nature of the ratio kmin
ff, it is not strictly monotonic.
Locally connected underlying graphs are used in the 2nd demonstrated instance of the
algorithm, which considers grouping of curve like groups based on proximity and smoothness.
5 Cue Enhancement
The performance of the grouping algorithm depends very much on the reliability of the
cues available to it. In many situations this reliability is predetermined and the grouping
algorithm designer can only prefer the more reliable cues from the available variety. This
section, however, shows how the reliability of a grouping cue can be significantly improved
by using statistical evidence accumulation techniques. This method is not restricted only
to our grouping algorithm, and can be used also in other grouping algorithms. Two of the
three domain specific grouping algorithm that we implement as examples (the co-linearity
and the smoothness) use this procedure.
5.1 The Cue Enhancement Procedure - Overview
The cue enhancement procedure considers one pair of data features at a time, and tries to
use the other data features in order to estimate the consistency of this pair. We shall say that
a subset of data features A is consistent if it is a subset of some true group. The idea behind
the following process of evidence accumulation is that a random data subset A that contains
the data pair may be consistent only (but not necessarily) if e itself is consistent.
Therefore, a multi-feature cues operating on a feature subset A (e 2 carries statistical
information on the consistency of e. Although bi-feature cues are easier to calculate and
are more straightforward to use, cues which test larger data subsets have several significant
advantages: Several useful cues are simply not defined when only one pair of elements is
considered (e.g. convexity). Bi-feature cues usually have corresponding multi-feature cues
associated with improved reliability. (Observe, for example, that accidental collinearity is
less likely if more points are considered while the miss probability should decrease only
slightly in this case. More generally, the reliability of the shape-based multi-feature cue of
"consistent with some instance of a particular object" clearly increases with the number of
data features [GH91, Lin94].)
The algorithm is conceptually simple: for every data pair, in the underlying
graph, the algorithm draws several random data subsets, A 1 ; A
contain the pair e. Then, the corresponding multi-feature cues, are ex-
tracted. The cue values are deterministic functions of the subsets A 1 ; A but may be
also considered as instances of a random variable, the statistics of which depend on the data
pair e, and in particular, on its consistency. The number of random data subsets and their
associated cues, required for a conclusive reliable decision on the consistency of e, is determined
adaptively and efficiently by a well-known method for statistical evidence integration:
Wald's SPRT test.
5.1.1 Wald's SPRT Algorithm and its Application for Cue Enhancement
Consider a random variable, x, the distribution of which depends on an unknown binary
parameter, which takes the value of ! 0 or ! 1 . Every instance of the random variable carries
statistical information on this parameter and integrating this information corresponding
to a sequence of the random variable instances will eventually lead to a reliable inference
about it. An efficient and accurate procedure for integration the statistical evidence is
the Sequential Probability Ratio Test (SPRT) suggested by Wald [Wal52]. This procedure
quantifies the evidence obtained from each trial by the log likelihood ratio function of its
are the probability functions of the two
different populations and x is the value assigned to the random variable in this trial.
The log likelihood ratio is high when the value of the random variable x is likely for
one hypothesis (! 1 ) and is not likely for the other (! 0 ). It is negative and low when the
situation is reversed. If the probabilities of seeing x under both hypotheses are close, then x
carries only little information and h(x) - 0. When several trials are taken, the log likelihood
function of the composite event should be considered. If, however, the
trials are independent then this composite log likelihood function is equal to the sum of the
individual log likelihood functions, oe
The sum oe n serves as the statistics by
which the decision is made. Wald's procedure specifies two limits, upper and lower. If the
cumulative log likelihood function crosses one of these limits, a decision is made. Otherwise,
more trials are carried out. More formally, denote the decision made by the procedure by
let the allowed probabilities of a decision error be
The algorithm is given simply by this iterative rule:
else test for another subset
The upper and lower limits, a depend only on the allowed probability of error
(defined in eq. 1), and do not depend on the distribution of the random variable x.
We calculate a; b using a practical approximation, proposed by Wald [Wal52], which is very
accurate when ffl miss ; ffl fa are small:
The basic SPRT algorithm terminates with probability one and is optimal in the sense
that it provides the minimum expected number of tests necessary to obtain the required
decision error [Wal52]. This expected number of tests is given by:
are the conditional expected amounts of evidence from a single
its average case optimality, the worst case number of trials
required by the SPRT algorithm is not bounded. To deal with this disadvantage, the modified
Truncated SPRT [Wal52], which uses a predefined upper bound n 0 on the number of tests,
is used. We set n 0 to be few times larger than Efng.
In the context of the Cue enhancement procedure, the cue value is regarded as a random
variable. Apart from specifying the desired reliability (ffl miss ; ffl fa ) and using equation 16 to
calculate the two thresholds a and b, one must supply the two distributions (for consistent
and inconsistent feature pairs), from which the log-likelihood ratio can be determined. These
distribution should be evaluated carefully: The distributions of the cues taken over the consistent
and inconsistent populations and denoted respectively by P con (C(A)) and P incon (C(A)),
are usually quite different. It is important however to observe that even if a feature pair
(u; v) is consistent, a random set including it may not be. Therefore, these distributions
should be modified as follows: A random set containing a
feature pair fu; vg ae S i and additional randomly selected data features, v
consistent with probability
where
Therefore, the modified cue distributions, conditioned relative to
the consistency of the first two feature are
Unfortunately, these distributions are more similar and difficult to distinguish (see Figure
9(a) for such a pair of distributions considered in our experiments). Restricting ourselves to
binary cues, the distribution of which is specified by the probabilities
the conditional distributions become are
.) The log likelihood ratio of
the i th randomly-selected subset, A i , becomes:
log( p
log( 1\Gammap
The SPRT based cue enhancement procedure is summarized in Figure 5.1.1.
2. Randomly choose data features x
3. Calculate
4. Update the evidence accumulator
For every feature pair (u; v) in the underlying
1. Set the evidence accumulator, oe, and the trials counter, n, to
5. if oe - a or if n - n 0 and oe ? 0, output: (u; v) is consistent.
if oe - b or if n - n 0 and oe ! 0, output: (u; v) is inconsistent.
else, repeat (2)-(5)

Figure

4: The cue enhancement algorithm
The success of the cue enhancement procedure relies on the validity of the statistical
model, and in particular, on the following two assumptions
assumption a: The statistics of the cue values evaluated over all data subsets containing
a consistent (inconsistent) arc is approximately the same.
assumption b: The cues extracted from two random subsets including the same feature
are independent identically distributed random variables.
If the assumptions are satisfied, then
6 The cue enhancement procedure described above can identify the consistency of the
feature pair within any specified error tolerance irrespective of the reliability of the basic cue
and provided that assumptions a and b hold.
This surprising conclusion seems to contradict intuition according to which arbitrarily low
identification errors are impossible as the amount of data in the image is finite. Indeed,
arbitrarily high performance is not possible as it requires a large number of trials leading to
a contradiction of the independence assumption. Therefore, the reliability of the basic cue is
important because it leads to a lower number of trials, which is both computationally advantageous
and important to the validity of the statistical independence assumption. Indeed,
our experiments show that the SPRT significantly improves the cue reliability but that the
achievable error rate is not arbitrarily small (see experimental results in the next section).
For a constant specified reliability (ffl miss ; ffl fa ), the expected running time of the cue
enhancement procedure is constant. The total running time for evaluating all the arcs of the
underlying graph, G u , is, therefore, linear in the number of arcs. We emphasize here that this
enhancement method is completely general and may use any cue that satisfies some benign
assumptions as stated in this section. It relies on the distributions of the cues, which should
be calculated before and involve certain technicalities described in the full version [AL94].
6 Simulation and experimentation
This section presents three different grouping applications, implemented in different domains,
as instances of the generic grouping algorithm described above. To our best knowledge, it
is the first time that a generic grouping algorithm is used in multiple domains. For each
implementation, the domain, the data features, and the grouping cue are different, but the
same grouping mechanism (and computer program) is used (see Table 1). The aim of these
examples is to show that useful grouping algorithms may be obtained as instances of the
generic approach and to examine the performance predictions against experimental results.
We do not expect that our general algorithm will perform as good as domain specific
algorithm which were tailored for that domain. Still, in all tested domains, we got grouping
results comparable to those obtained from existing, domain specific methods. This is
remarkable, because except from the choice of the cues (and the associated underlying graph
determined by their extent), the process did not depend on the domain. Moreover, although
some of the analysis may help in selecting between different available cues, we did not focus
on choosing the best cues, but more on testing our approach using reasonable cues. There-
fore, we expect that even better performance will be possible by optimizing cues and their
corresponding underlying graphs. (See more results and examples in [AL94, AL95].)
6.1 Example 1: Grouping points by co-linearity cues
Given a set of points in R 2 , the algorithm should partition the data into co-linear groups
(and one background set). To remove any doubt, we do not intend to propose our grouping
approach as an efficient (or even reasonable) method for detecting co-linear clusters. Several
common solutions (e.g., Hough transform, RANSAC) exist for this particular task. We have

Table

1: The three instances of the generic grouping algorithm
The 1st example The 2nd example The 3rd example
data elements points in R 2 edgels patches of Affine
optical flow
grouping cues co-linearity co-circularity consistency with
and proximity Affine motion
Cue's extent global local global
Enhanced cue subsets of 3 points subsets of 3
underlying graph complete graph locally connected graph a complete graph
grouping mechanism maximum likelihood graph clustering (same program)
chosen this example because it is a characteristic example of grouping tasks associated with
globally valid cues (and complete underlying graphs). Moreover, it provides a convenient
way for measuring grouping performance, the quantification and prediction of which is our
main interest here.
The grouping cue is defined over data subsets containing k ? 2 data features (here
and is just the second eigenvalue of the associated covariance matrix. Clearly, if this
eigenvalue is small, the data subset is closer to linear (see, e.g. [GM92]). The cue is global,
hence the underlying graph is the complete graph. To binarize this cue we simply check if
its value is lower than a threshold T .
We consider synthetic random images containing randomly drawn points (e.g Figure
5(a)). The points are drawn according to a distribution specified by a collection of arbitrary
straight lines which are the "objects" associated with the given data, and some additional,
uniformly distributed, aliens. With this data source, it is easy to automatically create many
data sets with known noise distributions and grouping ground truth (with the exception of
a few alien points, located very close to the "objects").
A typical grouping result is shown and explained in Figure 5. We used the co-linearity
example to comprehensivly test the performance of the grouping algorithm against its pre-
dictions. The first results show the performance of the cue function and the cue enhancement
procedure. To examine the cue function, we estimate the two cue-value distributions,
differ by the consistency of the included pair fu; vg ae A. This is done
by a monte-carlo process over randomly-selected feature-triplets. These two distributions,
(defined in eq. 18), tend to be quite similar, as shown in Figure 9(a). In order to make it
a binary cue, we proceed with selecting the threshold, T , for the binary cue decision. Any
specified threshold determines different binary-cue errors, (p miss ; p fa ). While one is a non-decreasing
function of T , the other is a non-increasing function of T , so some compromise
is done. The values of (p miss ; p fa ) effects the efficiency of the SPRT algorithm, which is
measured by the average number of subsets, Efng, needed to reach a specified error rate
Using eq. 17 with P 0 (C(A)); P 1 (C(A)) of Figure 9(a), one can draw Efng in
terms of the selected threshold, as shown in Figure 9(b). The optimal threshold is found
as the cue-value of the global minimum. Note that the selection of T does NOT effects the
resulted grouping quality, but only the computational time needed for the SPRT to reach
the desired error of the enhanced cue, (ffl miss ; ffl fa ). This threshold is also optimal in the sense
that it provides the maximum information from each evaluated feature-triplet. The measured
average number of subsets needed for the SPRT, Efng is given as labels in Figure 9(e),
for 100 different pre-specified (ffl miss ; ffl fa ) values, and remarkably agrees with the predicted
average (eq. 17), shown by the curves in this graph. It is also shown that the enhanced cue
reliability can exceeds 95% (i.e. ffl miss ! 5% , and ffl fa ! 5%), even with the simple cue we
used, which has a very low discrimination power by itself.
The next results show the overall grouping quality. Regardless the choice of (ffl miss
the 5 lines were always detected as the 5 largest groups in our experiments. The selection of
does affects, however, the overall grouping quality. This is measured by counting
the addition errors and the deletion errors, as shown in Figure 9(c) and 9(d), respectively.
Note that while the deletion error is very low, as expected, the addition error is higher than
expected. The reason for this discrepancy is some alien data features which are very close
to one of the lines and are erroneously added to it. The tradeoff between grouping quality
and the computational time of the cue enhancement procedure is obtained by these three
As Efng increases (in Figure (e)), the errors decrease (in Figures 9(c) and 9(d)).
6.2 Example 2: Grouping of edgels by smoothness
Starting from an image of edgels, (data feature = edge location gradient direction), the algorithm
should group edgels which lie on the same smooth curve. This is a very useful grouping
task, considered by many researchers (see, e.g [GM92, ZMFL95, HH93, SU90, CRH93]).
A crude co-circularity cue function, operating on edgel triples, is used. It is calculated as
the maximal angular difference between the gradient direction and the corresponding normal
direction to the circular arc passing through the three points. The underlying graph is
locally connected and is constructed by connecting every edgel to its K 2 [10; 50] nearest
edgels (K is a constant).
We test this procedure both on synthetic and real images, and the results are very good
in both cases (see Figure 6 and Figure 7). Synthetic images are created by detecting the
edges of piecewise constant images which contain grey level smooth blobs (e.g. Figure 6(a)).
In the synthetic example, we found that the perimeter of each of the two big blobs splits into
3-4 groups (see Figure 6(e)). It happens in places where the connectivity in G u is low, the
minimal connectivity assumption fails, and the split probability increases. (see Figure 3).
6.3 Example 3: Segmentation from Optical Flow using Affine Mo-
tion
The third grouping algorithm is based on common motion. The data features are pixel
blocks, which should be grouped together if their motion obeys the same rule, that is if
the given optical flow over them is consistent with one Affine motion model [JC94, AW94].
Technically, every pixel block is represented by its location and six parameters of the local
Affine motion model (calculated using Least Squares). The grouping cue is defined over pairs
of blocks, and its value is the sum of the optical flow errors of each block when calculating it
using the Affine model of the other block. The cue is global and hence a complete underlying
graph is used. No cue enhancement is used here, and the cue is not very reliable: typical
error probabilities are ffl miss = 0:35 and ffl 0:2. Still, the results are comparable to those
obtained by a domain specific algorithm [AW94]. The final clustering result, shown in Figure
8(f), was obtained after a post-processing stage: the obtained grouping is used to calculate
an Affine motion model for every group, which is used to classify all the individual pixels in
the image into groups. (The same method used in [AW94].)
(a) Original image: A set of points. (b) Associated data features: same as
original image.
(c) Underlying graph Gu : A complete
graph. The pixel gray level indicates the
number of arcs passing thru.
(d) Measured graph Gm . The pixel gray
level indicates the number of arcs passing
thru.
One of the detected groups. Only
very few points, if any, were fall in a
wrong group.
(f) All the detected groups

Figure

5: Example 1: grouping of co-linear points. An example to the images used in the
experiments. This image is associated with five lines, contains points in the vicinity of
each of them, and 150 uniformally distributed additional data features. The grouping result
is near-optimal, which not surprise the predictions. It demonstrates the power of a complete
underlying graph. Quantitative results of this experiments are shown in Figure 9.
(a) Original image: (b) Associated data features: edgels.
(c) Underlying graph G locally connected
(40 nearest nbrs). The pixel
gray level indicates the number of arcs
passing thru. The brighter areas correspond
to denser regions in G u .
(d) Measured graph Gm . The pixel
gray level indicates the number of arcs
passing thru. Note that the bright
groups in the measured graph are no
longer correspond to the local density
of Gu , but to smoothness. This
byproduct can also serve as a saliency
map.
One of the 14 detected groups. (f) All the 14 detected groups.

Figure

Example 2-1: Grouping of smooth curves in a synthetic image. Edge detection
and gradient where calculated on image (a). 50% of the edge pixels were randomly removed,
and 10% of the background pixels were added, as aliens, with uniformly distributed gradient
directions. Total number of edgels is about 5,000, and about 110,000 arcs in G u . The
(a) Original image: A brain image. (b) Edge detection of (a). The associated
data features are edgels.
(c) Underlying graph G locally connected
(40 nearest nbrs) The pixel
gray level indicates the number of arcs
passing thru.
(d) Measured graph Gm . The pixel
gray level indicates the number of arcs
passing thru.
(e) The five largest detected groups. (f) All the detected groups, superimposed
on the original image.

Figure

7: Example 2-2: Grouping of smooth curves in a brain image. The underlying graph,
G u , is made of 10,400 edgels and 230,000 arcs. The processing time is about 10 minutes on
(a) Original image: Flowers sequence. (b) Associated data features: Optical flow
(blocks).
(c) Underlying graph Gu : A complete graph.
The pixel gray level indicates the number of arcs
passing thru.
(d) Measured graph Gm . The pixel gray level
indicates the number of arcs passing thru. The
low number of edges in the clouds area indicates
that the optical flow in this area does not match
with the Affine motion model.
(e) The 3 resulted groups, each in a different
gray level. Black regions were either eliminated
for high error with their Affine model (e.g. on
the tree border), or not grouped to any of the
groups.
(f) A post-processing stage: the obtained
grouping is used to calculate an Affine motion
model for every group, which is used to classify
all the individual pixels in the image into
groups (Black pixels were not classified). This
result shows that even the groups (e) are not
visually nice, they can still capture the correct
motion clustering of the image.

Figure

8: Example 3: Image segmentation into regions consistent with the same Affine
motion parameters. The underlying graph is a complete graph of about 600 nodes (180,000
arcs), and the runtime is about 5 minutes.
Cue value
Probability
densety
(a) The distribution of the co-linearity cue
values, for subsets include a consistent feature
(C(A)),(solid) and for subsets include
an inconsistent feature pair, P 1 (C(A)),
(dashed). Although these two are very similar,
their populations can be distinguished with less
then 5% error, as shown in (e).
Cue threshold
(b) The expected number of trials needed for
the cue enhancement procedure as a function
of the selected cue threshold. The optimal
cue threshold correspond to the minima of this
curve. The experimental results are shown in
E_fa20101100111111001100110210222111101111221121422411
(c)
E_fa42234345556464546577866788981511111312141413816192011111916272115192820
(d)
E_miss
E_fa
(e) The tradeoff between the enhanced cue reliability
and the computational effort invested is
clearly demonstrated in this figure, showing the
error probabilities, ffl miss ; ffl fa , associated with the
enhanced cue and the experimental average number
of trials, E(n) (the points' labels). The solid
lines show the predicted error probabilities, for
labels).
Every point represents a complete grouping
process and is labeled by the resulting number
of: deleted points (deletion error) from all 5 lines
(c), added points (addition error) to all 5 lines(d).

Figure

9: Quantitative results: Comparison between the analysis prediction to the experimental
results of example 1. The grouping results tends to reach a near-perfect grouping by
using the cue enhancement procedure.
The goal of this work is to provide a theoretical framework and a generic algorithm that
would apply to various domains and that would have predictable performance. The proposed
generic grouping algorithm relies on established statistical techniques such as sequential testing
and maximum likelihood. The maximum likelihood principle is close to some previous
grouping approaches like the use of densities for evaluating the evidence of certain cues in
[Jac88] or the cumulative pairwise interaction score used for Figure-from-Ground discrimination
in [HH93]. This paper is distinctive from previous approaches because it provides, for
the first time, an analysis of the use of these principles, which relates the expected grouping
quality to the cue reliability, the connectivity used, and in some cases the computational
effort invested. We did not limit ourselves to the theoretical study. Three grouping appli-
cations, every one of which based on a different cue, are implemented as instances of the
generic grouping algorithm, and demonstrate its usefulness. Although we made an argument
against judging the merits of vision algorithm only by visually comparing their action on a
few examples, we would like to indicate here that our results are similar to those obtained by
domain specific methods (e.g. [SU90, HH93] for smoothness based grouping and [AW94] for
motion based grouping). Note that Gm may also be used to create a saliency map, where the
saliency of every data element is its degree in Gm . This saliency map (e.g Figure 7(d),8(d)),
is visually comparable with those proposed by other works (e.g. Shashua and Ullman [SU88],
Guy and Medioni [GM92]). Its suitablity for figure-ground discrimination is now studied.
Some interesting conclusions arise from our analysis and experimentation with grouping
algorithms: It is apparent that higher connectivity, provided either by a complete underlying
graph or by a high degree locally-connected graph, can enhance the grouping quality. There-
fore, the selection of cues for a grouping algorithm, should not be based only on maximizing
their reliability but also on their extent. The cue extent determines the connectivity of the
valid underlying graph, or in other words, the amount of information which may be extracted
by this cue. Another consideration is the cue enhancement possibility: if the cue satisfies
the independent random variable assumption, then more reliable cue may be obtained, with
a relatively low computational effort.
Our analysis of the computational complexity is not complete. Although the requirements
of the cue enhancement stage were clearly stated, even as a function of the quality required,
we do not have complexity results for the second stage, of finding the maximum likelihood
partition. This task is known to be difficult. (simulated annealing is used to solve similar
problems [HH93]). We used some heuristics, based on results from random graph theory and
on a greedy search, which turned out to work surprisingly good.
In the design of a grouping algorithm, one may either invest the computational effort
in enhancing the quality of a relatively small number of cues or use a larger number of
unreliable cues and merge them by higher connectivity underlying graph. The framework
proposed in this paper makes this choice explicit by providing a cue enhancement procedure,
independent from the maximum likelihood graph clustering. Making the optimal choice is
an interesting open question which we consider. Another research direction is to use our
methodology in the context of a different grouping notion, different than partitioning, by
which the hypothesized groups are not necessarily disjoint.

Acknowledgements

We would like to thank John Wang for providing us the Flowers garden optical flow data.



--R

The construction and analysis of a generic grouping algorithm.

Representing moving images with layers.

A bayesian mulitple- hypothesis approach to edge grouping and contour segmentation
Computing curvilinear structure by token-based grouping
Fast spreading metric based approximate graph partitioning algorithms.
An algorithm for finding best matches in logarithmic expected time.
Grimson and Daniel P.
Perceptual grouping using global saliency- enhancing operators
Theories of Visual Perception.


Extraction of groups for recognition.
The Use of Grouping in Visual Object Recognition.
Finding structurally consistent motion correspondences.
On the amount of data required for reliable recognition.
Perceptual Organization and Visual Recognition.
Using perceptual organization to extract 3-d structures
Graphical Evolution.
Trace interface
Applications of Spatial Data Structures.
Labeling of curvilinear structure across scales by token grouping.
Affine Analysis of Image Sequences.
Structural saliency: The detection of globally salient structures using locally connected network.
Grouping contours by iterated pairing network.
Supervised classification of early perceptual structure in dot patterns.
Relational Matching.
Sequencial Analysis.
Laws of organization in perceptual forms.
An optimal graph theoretic approach to data clus- tering: Theory and its application to image segmentation
On the role of structure in vision.

--TR

--CTR
Shyjan Mahamud , Lance R. Williams , Karvel K. Thornber , Kanglin Xu, Segmentation of Multiple Salient Closed Contours from Real Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.433-444, April
P. Kammerer , R. Glantz, Segmentation of brush strokes by saliency preserving dual graph contraction, Pattern Recognition Letters, v.24 n.8, p.1043-1050, May
Jens Keuchel , Christoph Schnrr , Christian Schellewald , Daniel Cremers, Binary Partitioning, Perceptual Grouping, and Restoration with Semidefinite Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.11, p.1364-1379, November
Alexander Berengolts , Michael Lindenbaum, On the Performance of Connected Components Grouping, International Journal of Computer Vision, v.41 n.3, p.195-216, February/March 2001
Jacob Feldman, Perceptual Grouping by Selection of a Logically Minimal Model, International Journal of Computer Vision, v.55 n.1, p.5-25, October
Anthony Hoogs , Roderic Collins , Robert Kaucic , Joseph Mundy, A Common Set of Perceptual Observables for Grouping, Figure-Ground Discrimination, and Texture Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.458-474, April
Song Wang , Joachim S. Stahl , Adam Bailey , Michael Dropps, Global Detection of Salient Convex Boundaries, International Journal of Computer Vision, v.71 n.3, p.337-359, March     2007
A. Engbers , Arnold W. M. Smeulders, Design Considerations for Generic Grouping in Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.445-457, April
Song Wang , Toshiro Kubota , Jeffrey Mark Siskind , Jun Wang, Salient Closed Boundary Extraction with Ratio Contour, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.4, p.546-561, April 2005
Bernd Fischer , Joachim M. Buhmann, Path-Based Clustering for Grouping of Smooth Curves and Texture Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.513-518, April
Sudeep Sarkar , Padmanabhan Soundararajan, Supervised Learning of Large Perceptual Organization: Graph Spectral Partitioning and Learning Automata, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.5, p.504-525, May 2000
Stella X. Yu , Jianbo Shi, Segmentation Given Partial Grouping Constraints, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.173-183, January 2004
Sudeep Sarkar , Daniel Majchrzak , Kishore Korimilli, Perceptual organization based computational model for robust segmentation of moving objects, Computer Vision and Image Understanding, v.86 n.3, p.141-170, June 2002
maximum likelihood;generic grouping algorithm;perceptual grouping;grouping analysis;performance prediction;Wald's SPRT;graph clustering