Probabilistic Models of Appearance for 3-D Object Recognition.
We describe how to model the appearance of a 3-D object using multiple views, learn such a model from training images, and use the model for object recognition. The model uses probability distributions to describe the range of possible variation in the object's appearance. These distributions are organized on two levels. Large variations are handled by partitioning training images into clusters corresponding to distinctly different views of the object. Within each cluster, smaller variations are represented by distributions characterizing uncertainty in the presence, position, and measurements of various discrete features of appearance. Many types of features are used, ranging in abstraction from edge segments to perceptual groupings and regions. A matching procedure uses the feature uncertainty information to guide the search for a match between model and image. Hypothesized feature pairings are used to estimate a viewpoint transformation taking account of feature uncertainty. These methods have been implemented in an object recognition system, OLIVER. Experiments show that OLIVER is capable of learning to recognize complex objects in cluttered images, while acquiring models that represent those objects using relatively few views.
Introduction
Object recognition requires a model of appearance that can be matched to new images. In
this paper, a new model representation will be described that can be derived automatically
from a sample of images of the object. The representation models an object by a probability
distribution that describes the range of possible variation in the object's appearance. Large
and complex variations are handled by dividing the range of appearance into a conjunction
of simpler probability distributions. This approach is general enough to model almost any
range of appearance, whether arising from different views of a 3-D object or from different
instances of a generic object class.
The probability distributions of individual features can help guide the matching process
that underlies recognition. Features whose presence is most strongly correlated with that
of the object can be given priority during matching. Features with the best localization can
contribute most to an estimate of the object's position, while features whose positions vary
most can be sought over the largest image neighborhoods. We hypothesize initial pairings
between model and image features, use them to estimate an aligning transformation, use the
transformation to evaluate and choose additional pairings, and so on, pairing as many features
as possible. The transformation estimate includes an estimate of its uncertainty derived
from the uncertainties of the paired model and image features. Potential feature pairings are
evaluated using the transformation, its uncertainty, and topological relations among features
so that the least ambiguous pairings are adopted earliest, constraining later pairings. The
method is called probabilistic alignment to emphasize its use of uncertainty information.
Two processes are involved in learning a multiple-view model from training images
(Fig. 1). First, the training images must be clustered into groups that correspond to distinct
views of the object. Second, each group's members must be generalized to form a model
view characterizing the most representative features of that group's images. Our method
couples these two processes in such a way that clustering decisions consider how well the
resulting groups can be generalized, and how well those generalizations describe the training
images. The multiple-view model produced thus achieves a balance between the number
of views it contains, and the descriptive accuracy of those views.
Related research
In recent years, there has been growing interest in modeling 3-D objects with information
derived from a set of 2-D views (Breuel, 1992; Murase and Nayar, 1995). For an object that
is even moderately complex, however, many qualitatively distinct views may be needed.
Thus, a multiple-view representation may require considerably more space and complexity
in matching than a 3-D one. Space requirements can be reduced somewhat by allowing
views to share common structures (Burns and Riseman, 1992) and by merging similar views
after discarding features too fine to be reliably discerned (Petitjean, Ponce, and Kriegman,
1992). In this paper, we develop a representation that combines nearby views over a wider
range of appearance by representing the probability distribution of features over a range of
Training Images
Clusters
Model Views
Clustering
Generalization

Figure

1: Learning a multiple-view model from training images requires a clustering of the
training images and a generalization of each cluster's contents.
One method for improving the space/accuracy trade-off of a multiple-view representation
is to interpolate among views. Ullman and Basri (1991) have shown that with three
views of a rigid object whose contours are defined by surface tangent discontinuities, one
can interpolate among the three views with a linear operation to produce other views under
orthographic projection. If the object has smooth contours instead, six views allow for
accurate interpolation. However, for non-rigid or generic models, a more direct form of
sampling and linear interpolation can be more general while giving adequate accuracy, as
described in this paper.
There has also been recent development of methods using dense collections of local fea-
tures, with rotational invariants computed at corner points (Schmid and Mohr, 1997). This
approach has proved very successful with textured objects, but is less suited to geometrically
defined shapes, particularly under differing illumination. The approach described in
this paper can be extended to incorporate any type of local feature into the model represen-
tation, so a future direction for improvement would be to add local image-based features.
Initially, the system has been demonstrated with edge-based features that are less sensitive
to illumination change.
Other approaches to view-based recognition include color histograms (Swain and Bal-
lard, 1991), eigenspace matching (Murase and Nayar, 1995), and receptive field histograms
(Schiele and Crowley, 1996). These approaches have all been demonstrated successfully on
isolated or pre-segmented images, but due to their more global features it has been difficult
to extend them to cluttered and partially occluded images, particularly for objects lacking
distinctive feature statistics.
2.1 Matching with uncertainty
One general strategy for object recognition hypothesizes specific viewpoint transformations
and tests each hypothesis by finding feature correspondences that are consistent with it. This
strategy was used in the first object recognition system (Roberts, 1965), and it has been used
in many other systems since then (Brooks, 1981; Bolles and Cain, 1982; Lowe, 1985; Grimson
and Lozano-P-erez, 1987; Huttenlocher and Ullman, 1990; Nelson and Selinger, 1998).
An example of this approach is the iterative matching in the SCERPO system (Lowe,
1987). A viewpoint transformation is first estimated from a small set of feature pairings.
This transformation is used to predict the visibility and image location of each remaining
model feature. For each of these projected model features, potential pairings with nearby
image features are identified and evaluated according to their expected reliability. The best
ranked pairings are adopted, all pairings are used to produce a refined estimate of the trans-
formation, and the process is repeated until acceptable pairings have been found for as many
of the model features as possible. This paper describes an enhanced version of iterative
matching that incorporates feature uncertainty information.
In a related approach, Wells (1997) has shown how transformation space search can be
cast as an iterative estimation problem solved by the EM algorithm. Using Bayesian theory
and a Gaussian error model, he defines the posterior probability of a particular set of
pairings and a transformation, given some input image. In more recent work, Burl, Weber,
and Perona (1998) provide a probabilistic model giving deformable geometry for local image
patches. The current paper differs from these other approaches by deriving a clustered
view-based representation that accounts for more general models of appearance, incorporating
different individual estimates of feature uncertainty, and making use of a broader range
of features and groupings.
2.2 Use of uncertainty information in matching
Iterative alignment has been used with a Kalman filter to estimate transformations from feature
pairings in both 2D-2D matching (Ayache and Faugeras, 1986) and 2D-3D matching
(Hel-Or and Werman, 1995). Besides being efficient, this allows feature position uncertainty
to determine transformation uncertainty, which in turn is useful in predicting feature
positions in order to rate additional feature pairings (Hel-Or and Werman, 1995). However,
this (partial) least-squares approach can only represent uncertainty in either image or model
features, not both; total least squares can represent both, but may not be accurate in predicting
feature positions from the estimated transformation (Van Huffel and Vandewalle,
1991). Most have chosen to represent image feature uncertainty; we have chosen to emphasize
model feature uncertainty, which in our case carries the most useful information.
3 Model representation
An object model is organized on two levels so that it can describe the object's range of appearance
both fully and accurately. At one level, large variations in appearance are handled
by subdividing the entire range of variation into discrete subranges corresponding to
distinctly different views of the object; this is a multiple-view representation. At a second
level, within each of the independent views, smaller variations are described by probability
distributions that characterize the position, attributes, and probability of detection for individual
features.
The only form of appearance variation not represented by the model is that due to varying
location, orientation, and scale of the object within the image plane. Two mechanisms
accommodate this variation. One is the viewpoint transformation, which aligns a model
view with an appropriate region of the image; we shall describe it in section 4. The other is
the use of position-invariant representations for attributes, which allow feature attributes to
be compared regardless of the feature positions.
3.1 Simplifying approximation of feature independence
Our method lets each model view describe a range of possible appearances by having it
define a joint probability distribution over image graphs. However, because the space of
image graphs is enormous, it is not practical to represent or learn this distribution in its most
general form. So instead, the joint distribution is approximated by treating its component
features as though they were independent. This approximation allows the joint distribution
to be decomposed into a product of marginal distributions, thereby greatly simplifying the
representation, matching, and learning of models.
One consequence of this simplification is that statistical dependence (association or co-
among model features cannot be accurately represented within a single model
view. Consider, for example, an object whose features are divided among two groups, only
one of which appears in any instance. With its strongly covariant features, this object would
be poorly represented by a single view. However, where one view cannot capture an important
statistical dependence, multiple views can. In this example, two model views, each
containing one of the two subsets of features, could represent perfectly the statistical dependence
among them.
By using a large enough set of views, we can model any object as accurately as we wish.
For economy, however, we would prefer to use relatively few views and let each represent
a moderate range of possible appearances. The model learning procedure described in section
6 gives a method for balancing the competing aims of accuracy and economy.
3.2 Model view representation
A single model view is represented by a model graph. A model graph has nodes that represent
features, and arcs that represent composition and abstraction relations among features.
Each node records the information needed to estimate three probability distributions characterizing
its feature:
1. The probability of observing this feature in an image depicting the modeled view of
the object. This is estimated from a record of the number of times the model feature
has been identified in training images by being matched to a similar image feature.
2. Given that this feature is observed, the probability of it having a particular position.
This is characterized by a probability distribution over feature positions. We approximate
this distribution as Gaussian to allow use of an efficient matching procedure
based on least squares estimation. The parameters of the distribution are estimated
from sample feature positions acquired from training images.
3. Given that this feature is observed, the probability of it having particular attribute
values. This is characterized by a probability distribution over vectors of attribute
values. Little can be assumed about the form of this distribution because it may depend
on many factors: the type of feature, how its attributes are measured, possible
deformations of the object, and various sources of measurement error. Thus we use a
non-parametric density estimator that makes relatively few assumptions. To support
this estimator, the model graph node records sample attribute vectors acquired from
training images.
3.3 Model notation
An object's appearance is modeled by a set of model graphs fG i g. A model graph G i is a
tuple hF; R; mi, where F is a set of model features, R is a relation over elements of F , and
m is the number of training images used to produce G i .
A model feature j 2 F is represented by a tuple of the form ht
j's type is represented by t j , whose value is one of a set of symbols denoting different
types of features. The element m j specifies in how many of the m training images feature
was found. The series A j contains the attribute vectors of those training image features
that matched j. The dimension and interpretation of these vectors depend on j's type. The
series contains the mean positions of the training image features that matched j. These
positions, although drawn from separate training images, are expressed in a single, common
coordinate system, which is described in the following section.
From j's type t j , one can determine whether j is a feature that represents a grouping or
abstraction of other features. If so then R will contain a single element, hk; l specifying
j's parts as being l 1 through l n . The number of parts n may depend on j. Moreover,
any l i may be the special symbol ?, which indicates that the part is not defined, and perhaps
not represented in the model graph.
4 Coordinate systems and viewpoint transformations
A feature's position is specified by a 2-D location, orientation, and scale. Image features
are located in an image coordinate system of pixel rows and columns. Model features are
located in a model coordinate system shared by all features within a model graph.
Two different schemes are used to describe a feature's position in either coordinate system

xy's The feature's location is specified by [x y], its orientation by ', and its scale by s.
xyuv The feature's location is specified by [x y], and its orientation and scale are represented
by the direction and length of the 2-D vector [u v].
We shall use the xy's scheme for measuring feature positions, and the xyuv scheme to provide
a linear approach for aligning features in the course of matching a model with an image.
They are related by
Where it is not otherwise clear we
shall indicate which scheme we are using with the superscripts xy's and xyuv .
The task of matching a model with an image includes that of determining a viewpoint
transformation that closely aligns image features with model features. The viewpoint trans-
formation, T , is a mapping from 2-D image coordinates to 2-D model coordinates-it transforms
the position of an image feature to that of a model feature.
4.1 Similarity transformations
A 2-D similarity transformation can account for translation, rotation, and scaling of an ob-
ject's projected image. It does not account for effects of rotation in depth, nor changes in
perspective as an object moves towards or away from the camera.
A 2-D similarity transformation decomposed into a rotation by ' t , a scaling by s t , and
a translation by [x t y t ], in that order, can be expressed as a linear operation using the xyuv
scheme, as Ayache and Faugeras (1986), among others, have done. The linear operation has
two formulations in terms of matrices. We shall present both formulations here, and have
occasion to use both in section 5.
We shall develop the formulations by first considering the transformation of a point location
from [x k y k ] to [x 0
k ]. We can write it as
sin ' t cos ' t
(1)
Defining allows us to rewrite this as either
(2)
or
Now consider a vector [u k v k ] whose direction represents an orientation and whose magnitude
represents a length. When mapped by the same transformation, this vector must be
rotated by ' t and scaled by s t to preserve its meaning. Continuing to use u
, we can write the transformation of [u k v k ] as either
or
Equations 3 and 5 together give us one complete formulation of the transformation. We
can write it with a matrix A k representing the position b being transformed,
and a vector t representing the transformation:
Equations 2 and 4 together give us another complete formulation. We can write it with
a matrix A t representing the rotation and scaling components of the transformation, and a
vector x t representing the translation components:
Because it can be expressed as a linear operation, the viewpoint transformation can be
estimated easily from a set of feature pairings. Given a model feature at b j and an image
feature at b k , the transformation aligning the two features can be obtained as the solution to
the system of linear equations b additional feature pairings, the problem of
estimating the transformation becomes over-constrained; then the solution that is optimal in
the least squares sense can be found by least squares estimation. We shall describe a solution
method in section 5.3.
5 Matching and recognition methods
Recognition requires finding a consistent set of pairings between some model features and
some image features, plus a viewpoint transformation that brings the paired features into
close correspondence. Identifying good matches requires searching among many possible
combinations of pairings and transformations. Although the positions, attributes, and relations
of features provide constraints for narrowing this search, a complete search is still
impractical. Instead the goal is to order the search so that it is likely to find good matches
sooner rather than later, stopping when an adequate match has been found or when many of
the most likely candidates have been examined. Information about feature uncertainty can
help by determining which model features to search for first, over what size image neighbourhoods
to search for them, and how much to allow each to influence an estimate of the
viewpoint transformation.
5.1 Match quality measure
A match is a consistent set of pairings between some model and image features, plus a transformation
closely aligning paired features. We seek a match that maximizes both the number
of features paired and the similarity of paired features.
Pairings are represented by
image feature k, and e j =? if it matches nothing. H denotes the hypothesis that the modeled
view of the object is present in the image. Match quality is associated with the probability
of H given a set of pairings E and a viewpoint transformation T , which Bayes' theorem lets
us write as
There is no practical way to represent the high-dimensional, joint probability functions P(E j
them by adopting simplifying assumptions of feature
independence. The joint probabilities are decomposed into products of low-dimensional,
marginal probability functions, one per feature:
Y
The measure is defined using log-probabilities to simplify calculations. Moreover, all positions
of a modeled view within an image are assumed equally likely, so P(T
With these simplifications the measure becomes
log P(e
log
P(H), the prior probability that the object as modeled is present in the image, can be estimated
from the proportion of training images used to construct the model. The remaining
terms are described using the following notation for random events: ~
the event that
model feature j matches image feature k; ~ e j =?, the event that it matches nothing; ~
the event that it matches a feature whose attributes are a; and ~
b, the event that it
matches a feature whose position, in model coordinates, is b.
There are two cases to consider in estimating the conditional probability, P(e
for a model feature j.
1. When j is unmatched, this probability is estimated by considering how often j was
found during training. We use a Bayesian estimator, a uniform prior, and the -
m and
recorded by the model:
2. When j is matched to image feature k, this probability is estimated by considering
how often j matched an image feature during training, and how the attributes and position
of k compare with those of previously matching features:
P( ~
Viewpoint
transformation
Image coordinates
Image feature
position pdf
Model coordinates
Model feature
position pdf
Image feature
position pdf
Transformation space

Figure

2: Comparison of image and model feature positions. An image feature's position
is transformed from image coordinates (left) to model coordinates (right) according to an
estimate of the viewpoint transformation. Uncertainty in the positions and the transformation
are characterized by Gaussian distributions that are compared in the model coordinate
space.
P(~e j 6=?) is estimated as in (10). P(~ a estimated using the series of attribute
vectors -
recorded with model feature j, and a non-parametric density estimator described
in (Pope, 1995). Estimation of P( ~
the probability that model feature j will
match an image feature at position b k with transformation T , is described in Sect. 5.2.
Estimates of the prior probabilities are based, in part, on measurements from a collection
of images typical of those in which the object will be sought. From this collection we obtain
prior probabilities of encountering various types of features with various attribute values.
Prior distributions for feature positions assume a uniform distribution throughout a bounded
region of model coordinate space.
5.2 Estimating feature match probability
The probability that a model and image feature match depends, in part, on their positions and
on the aligning transformation. This dependency is represented by the P( ~
term in (11). To estimate it, we transform the image feature's position into model coor-
dinates, and then compare it with the model feature's position (Fig. 2). This comparison
considers the uncertainties of the positions and transformation, which are characterized by
Gaussian PDFs.
Image feature k's position is reported by its feature detector as a Gaussian PDF in xy's
image coordinates with mean b xy's
k and covariance matrix C xy's
k . To allow its transformation
into model coordinates, this PDF is re-expressed in xyuv image coordinates using an
approximation adequate for small ' and s variances. The approximating PDF has a mean,
k , at the same position as b xy's
k , and a covariance matrix C xyuv
k that aligns the Gaussian
envelope radially, away from the [u v] origin:
l
l
and oe 2
l , oe 2
s and oe 2
' are the variances in image feature position, scale and orientation estimates.
T is characterized by a Gaussian PDF over [x t y t u t v t ] vectors, with mean t and covariance
t estimated from feature pairings as described in Sect. 5.4. Using it to transform the
image feature position from xyuv image to model coordinates again requires an approxima-
tion. If we would disregard the uncertainty in T , we would obtain a Gaussian PDF in model
coordinates with mean A k t and covariance A t C k A T
. Alternatively, disregarding the uncertainty
in k's position gives a Gaussian PDF in model coordinates with mean A k t and
covariance A k C t A T
. With Gaussian PDFs for both feature position and transformation,
however, the transformed position's PDF is not of Gaussian form. At best we can approximate
it as such, which we do with a mean and covariance given in xyuv coordinates by
Model feature j's position is also described by a Gaussian PDF in xyuv model coordinates.
Its mean b j and covariance C j are estimated from the series of position vectors -
recorded
by the model.
The desired probability (that j matches k according to their positions and the transforma-
tion) is estimated by integrating, over all xyuv model coordinate positions r, the probability
that both the transformed image feature is at r and the model feature matches something at
r:
P( ~
Z
r
Here ~r j and ~r kt are random variables drawn from the Gaussian distributions N(b
It would be costly to evaluate this integral by sampling it at various r, but
fortunately the integral can be rewritten as a Gaussian since it is essentially one component
in a convolution of two Gaussians:
P( ~
where G(x; C) is a Gaussian with zero mean and covariance C. In this form, the desired
probability is easily computed.
5.3 Matching procedure
Recognition and learning require the ability to find at match between a model graph and an
image graph that maximizes the match quality measure. It does not seem possible to find an
optimal match through anything less than exhaustive search. Nevertheless, good matches
can usually be found quickly by a procedure that combines qualities of both graph matching
and iterative alignment.
5.3.1 Probabilistic alignment
To choose the initial pairings, possible pairings of high level features are rated according to
the contribution each would make to the match quality measure. The pairing hj; ki receives
the rating
log P(~e
This rating favors pairings in which j has a high likelihood of matching, j and k have similar
attribute values, and the transformation estimate obtained by aligning j and k has low
variance. The maximum over T is easily computed because P(~e
in T .
Alignments are attempted from these initial pairings in order of decreasing rank. Each
alignment begins by estimating a transformation from the initial pairing, and then proceeds
by repeatedly identifying additional consistent pairings, adopting the best, and updating the
transformation estimate with them until the match quality measure cannot be improved fur-
ther. At this stage, pairings are selected according to how each might improve the match
quality measure; thus hj; ki receives the rating
This favors the same qualities as equation 12 while also favoring pairings that are aligned
closely by the estimated transformation. In order for hj; ki to be adopted, it must rate at least
as well as the alternative of leaving j unmatched, which receives the rating
Significant computation is involved in rating and ranking the pairings needed to extend
an alignment. Consequently, pairings are adopted in batches so that this computation need
only be done infrequently. Moreover, in the course of an alignment, batch size is increased
as the transformation estimate is further refined so that each batch can be made as large as
possible. A schedule that seems to work well is to start an alignment with a small batch of
pairings (we use five), and to double the batch size with each batch adopted.
5.4 Estimating the aligning transformation
From a series of feature pairings, an aligning transformation is estimated by finding the
least-squares solution to a system of linear equations. Each pairing hj; ki contributes to the
system the equations
A k is the matrix representation of image feature k's mean position,
the transformation estimate, and b j is model feature j's mean position. U j is the upper
triangular square root of j's position covariance (i.e., C
weights both sides
of the equation so that the residual error ~
e has unit variance.
A recursive estimator solves the system, efficiently updating the transformation estimate
as pairings are adopted. We use the square root information filter (SRIF) (Bierman, 1977)
form of the Kalman filter for its numerical stability, and its efficiency with batched measure-
ments. The SRIF works by updating the square root of the information matrix, which is the
inverse of the estimate's covariance matrix. The initial square root, R 1 , and state vector, z 1 ,
are obtained from the first pairing hj; ki by
With each subsequent pairing hj; ki, the estimate is updated by triangularizing a matrix composed
of the previous estimate and data from the new pairing:6 4 R
When needed, the transformation and its covariance are obtained from the triangular R i by
back substitution:
Verification
Once a match has been found between a model graph and an image graph, it must be decided
whether the match represents an actual instance of the modeled object in the image.
A general approach to this problem would use decision theory to weigh prior expectations,
evidence derived from the match, and the consequences of an incorrect decision. However,
we will use a simpler approach that only considers the number and type of matching features
and the accuracy with which they match.
The match quality measure used to guide matching provides one indication of a match's
significance. A simple way to accept or reject matches, then, might be to require that this
measure exceeds some threshold. However, the measure is unsuitable for this use because
its range differs widely among objects according to what high-level features they have. High-level
features that represent groupings of low-level ones violate the feature independence
assumption; consequently, the match quality measure is biased by an amount that depends
on what high-level features are present in the model. Whereas this bias seems to have no
adverse effect on the outcome of matching any one model graph, it makes it difficult to establish
a single threshold for testing the match quality measure of any model graph. Thus the
verification method we present here considers only the lowest-level features of the model
graph-those that do not group any other model graph features.
When counting paired model features, we weight each one according to its likelihood of
being paired, thereby assigning greatest importance to the features that contribute most to
the likelihood that the object is present. For model feature j, the likelihood of being paired,
is estimated using statistics recorded for feature j.
The count of each model feature is also weighted according to how well it is fit by image
features. When j is a curve segment, this weighting component is based on the fraction
of j matched by nearby image curve segments. The fraction is estimated using a simple
approximation: The lengths of image curve segments matching j are totaled, the total length
is transformed into model coordinates, and the transformed value is divided by the length of
j. With s t denoting the scaling component of the viewpoint transformation T , and s j and s k
denoting the lengths of j and k in model and image coordinates, respectively, the fraction
of j covered by image curve segments is defined as
curve segment.
If we were to accept matches that paired a fixed number of model features regardless of
model complexity, then with greater model complexity we would have an increased likelihood
of accepting incorrect matches. For example, requiring that ten model features be
paired may make sense for a model of twenty features, but for a model of a thousand fea-
tures, any incorrect match is likely to contain at least that many "accidental" pairings.
Thus we have chosen instead to require that some minimum fraction of the elements of
C be paired. We define this fraction as
A match hE; T i is accepted if Support(E; T ) achieves a certain threshold - . To validate
this verification method and to determine a suitable value for - , we have measured
the distribution of Support(E; T ) for correct and incorrect matches between various model
graphs and their respective training image graphs. The distributions are well separated, with
most correct matches achieving most incorrect matches achieving
6 Model learning procedure
The learning procedure assembles one or more model graphs from a series of training images
showing various views of an object. To do this, it clusters the training images into
groups and constructs model graphs generalizing the contents of each group. We shall describe
first the clustering procedure, and then the generalization procedure, which the clustering
procedure invokes repeatedly.
We use X to denote the series of training images for one object. During learning, the
object's model M consists of a series of clusters X i ' X , each with an associated model
graph -
G i . Once learning is complete, only the model graphs must be retained to support
recognition.
6.1 Clustering training images
An incremental conceptual clustering algorithm is used to create clusters among the training
images. Clustering is incremental in that, as each training image is acquired, it is assigned
to an existing cluster or used to form a new one. Like other conceptual clustering
algorithms, such as COBWEB (Fisher, 1987), the algorithm uses a global measure of over-all
clustering quality to guide clustering decisions. This measure is chosen to promote and
balance two somewhat-conflicting qualities. On one hand, it favors clusterings that result in
simple, concise, and efficient models, while on the other hand, it favors clusterings whose
resulting model graphs accurately characterize the training images.
The minimum description length principle (Rissanen, 1983) is used to quantify and balance
these two qualities. The principle suggests that the learning procedure choose a model
that minimizes the number of symbols needed to encode first the model and then the training
images. It favors simple models as they can be encoded concisely, and it favors accurate
models as they allow the training images to be encoded concisely once the model has been
provided. The clustering quality measure to be minimized is defined as L(M)+L(X j M),
where L(M) is the number of bits needed to encode the model M, and L(X j M) is the
number of bits needed to encode the training images X when M is known.
To define L(M) we specify a coding scheme for models that concisely enumerates each
of a model's graphs along with its nodes, arcs, attribute vectors and position vectors (see
(Pope, 1995) for full details of the coding scheme). Then L(M) is simply the number of
bits needed to encode M according to this scheme.
To define L(X j M) we draw on the fact that given any probability distribution P(x),
there exists a coding scheme, the most efficient possible, that achieves essentially
P(x). Recall that the match quality measure is based on an estimate of the probability
that a match represents a true occurrence of the modeled object in the image. We use this
probability to estimate P(X j -
the probability that the appearance represented by image
may occur according to the appearance distribution represented by model graph -
This probability can be computed for any given image graph X and model graph G i , using
the matching procedure (Sect. 5.3) to maximize P(H
used to estimate the length of an encoding of X given -
E)
The L u (X; E) term is the length of an encoding of unmatched features of X , which we
define using a simple coding scheme comparable to that used for model graphs. Finally, we
define L(X j M) by assuming that for any X 2 X i ' X , the best match between X and
any -
will be that between X and -
(the model graph obtained by generalizing the
group containing X). Then the length of the encoding of each X 2 X in terms of the set of
model graphs M is the sum of the lengths of the encodings of each in terms of its respective
model
As each training image is acquired it is assigned to an existing cluster or used to form a
new one. Choices among clustering alternatives are made to minimize the resulting L(M)+
evaluating an alternative, each cluster's subset of training images X i is
first generalized to form a model graph -
G i as described below.
6.2 Generalizing training images
Within each cluster, training images are merged to form a single model graph that represents
a generalization of those images. An initial model graph is formed from the first training
image's graph. That model graph is then matched with each subsequent training image's
graph and revised after each match according to the match result. A model feature j that
matches an image feature k receives an additional attribute vector a k and position b k for
its series -
A j and -
Unmatched image features are used to extend the model graph, while
model features that remain largely unmatched are eventually pruned. After several training
images have been processed in this way the model graph nears an equilibrium, containing
the most consistent features with representative populations of sample attribute vectors and
positions for each.
7 Experimental results
In this section we describe several experiments involving a system implemented to test our
recognition learning method. This system, called OLIVER, learns to recognize 3-D objects
in 2-D intensity images.
OLIVER has been implemented within the framework of Vista, a versatile and extensible
software environment designed to support computer vision research (Pope and Lowe, 1994).
Both OLIVER and Vista are written in C to run on UNIX workstations. The execution times
reported here were measured on a Sun SPARCstation 10/51 processor.
The focus of this research has been on the model learning and representation, which
is independent of the particular features used for matching. To test the approach, we have
chosen to use a basic repertoire of edge-based features. While some recent approaches to
recognition have been based on image pixel intensities or image derivative magnitudes, the
locations of intensity discontinuities may be more robust to illumination and imaging vari-
ations. For example, the silhouette boundaries of an object on a cluttered background will
have image derivatives of unknown sign and magnitude. The same is true for edges separating
surfaces of different orientation under differing directions of illumination.

Figure

3: Bunny training images. Images were acquired at 5 ffi intervals over camera elevations
of 0 ffi to 25 ffi and azimuths of 0 ffi to 90 ffi . Shown here are three of the 112 images.
In the following experiments, the lowest-level features are straight, circular and elliptical
edge segments. An edge curve of any shape can be represented by approximating it
with a series of primitive segments. Additional higher-level features represent groupings of
these, such as junctions, groups of adjacent junctions, pairs of parallel segments, and convex
regions. For full details on the derivation of these features, see (Pope, 1995). In the future,
this set could be augmented with other features, such as those based on image derivatives,
color, or texture, but the current features are suited for a wide range of objects.
7.1 Illustrative experiment
The experiment described in this section demonstrates typical performance of the system in
learning to recognize a complex object. The test object is a toy bunny shown in figure 3.
Training images of the bunny were acquired at 5 ffi increments of camera elevation and azimuth
over 25 ffi of elevation and 90 ffi of azimuth.
Feature detection, including edge detection, curve segmentation, and grouping, required
about seconds of CPU time per training image (we believe that much faster grouping
processes are possible, but this was not the focus of the research). Figure 4 depicts some of
the features found in one image, which include 4475 edgels, 81 straight lines and 67 circular
arcs.
During the first phase of clustering, the system divided the training images among 19
clusters. In the second phase, it reassigned two training images that remained the sole members
of their clusters, leaving the 17 clusters shown in figure 5. Because this object's appearance
varies smoothly with changes in viewpoint across much of the viewing range, it is not
surprising that the clusters generally occupy contiguous regions of the viewsphere.
When training images were presented to the system in other sequences, the system produced
different clusterings than that shown in figure 5. However, although cluster boundaries
varied, qualities such as the number, extent, and cohesiveness of the clusters remained
largely unaffected.
As this is a one-time batch operation, little effort was devoted to optimizing efficiency.
Altogether, 19.4 hours of CPU time were required to cluster the training images and to in-
(a) (b)
(c) (d)

Figure

4: Features of a bunny training image. Shown here are selected features found in
the 0 training image (right image in figure 3). (a) Edgels. (b) Curve
features. (c) L-junction features. (d) Parallel-curve features (depicted by parallel lines), Region
features (depicted by rectangles), and Ellipse features (depicted by circles).
duce a model graph generalization of each cluster.

Figure

5 shows features of the model graph representing cluster C. Ellipses are drawn
for certain features to show two standard deviations of location uncertainty. To reduce clutter
and to give some indication of feature significance, they are drawn only for those features
that were found in a majority of training images. Considerable variation in location
uncertainty is evident. Some L-junction features have particularly large uncertainty and,
consequently, they will be afforded little importance during matching.

Figure

7 reports the results of matching the image graph for test image 1 with each of the
bunny model graphs. For this test, match searches were allowed to examine all alignment
hypotheses. Typically, there were 10-20 hypotheses examined for each pair of model and
image graphs, and about five seconds of CPU time were needed to extend and evaluate each
one. The matches reported here are those achieving the highest match quality measure.
The model graph generalizing cluster D provides the best match with the image graph
(as judged by each match's support measure). This is to be expected as the test image was
acquired from a viewpoint surrounded by that cluster's training images. Moreover, other
model graphs that match the image graph (although not as well) are all from neighbouring
A A J J J
A A J J P
A A A B A J
D D D D M K
I O I
Elevation
Azimuth (a) (b)
(c) (d)

Figure

5: On the left are the training image clusters. Seventeen clusters, designated A
through Q, were formed from the 112 training images. Contours delineate the approximate
scope of the view classes associated with some of the clusters. On the right are selected features
of the model graph obtained by generalizing the training images assigned to cluster C.
Each feature is drawn at its mean location. (a) Curve features. (b) L-junction features. (c)
Connected edge features. (d) Parallel curve, Region and Ellipse features.

Figure

test image 1. Left: Image. Right: Match of bunny model graph D with test
image.
MODEL MATCH WITH TEST IMAGE 1 MATCH WITH TEST IMAGE 2
GRAPH Correct Quality Pairings Support Correct Quality Pairings Support
A 998 164 0.35 862 191 0.34
I 356 91 0.19 879 186 0.35
O 151 72 0.14 187 90 0.23

Figure

7: Each row documents the results of matching a model graph with the two image
graphs, those describing bunny test images 1 and 2. Reported for each match are the fol-
lowing. Correct: whether the match correctly identified most features of the object visible
in the image, as judged by the experimenter. Quality: the match's match quality measure,
Pairings: the number of image features paired. Support: the match's support mea-
regions of the viewsphere. Image features included in the best match, that with model graph
D, are shown in figure 6.
For test image 2, shown in figure 8, additional clutter was present. Figure 7 reports the
result of matching the image graph of test image 2 with each of the bunny model graphs.
This time each match search was limited to 20 alignment hypotheses and about six seconds
of CPU time were needed to extend and evaluate each hypothesis. Due to the additional
clutter in the image, only model graph D correctly matched the image.
This section has demonstrated the system's typical performance in learning models of
complex objects, and in using those models to accomplish recognition. Figure 9 shows
recognition of an even more complex object with significant occlusion.
7.2 Additional Experiments
In this section, some additional experiments are briefly described in order to illustrate certain
noteworthy aspects of the system's behaviour.

Figure

8: Left: Bunny test image 2 with clutter and occlusion. Right: Match of bunny model
graph D with test image 2.

Figure

9: Example showing recognition of a complex object with substantial occlusion.
Left: One of several training images. Right: Image curve features included in the match.
7.2.1 Effects of feature distribution
When some regions of an object are much richer in stable features than others, those regions
can dominate the matching processes that underlie learning and recognition. For example,
most features of the shoe shown in figure 10 are concentrated near its centre. Moreover, as
the shoe rotates about its vertical axis, features near the shoe's centre shift by small amounts
while those near its heel and toe undergo much larger changes. Thus, when training images
of the shoe are clustered during model learning, the many stable features near the shoe's
centre are used to match training images over a large range of rotation, while the few variable
features defining the heel and toe are dropped as being unreliable. The result is a model
graph, like that shown in figure 11 (left), with relatively few features defining the shoe's
extremities.
If the dropped features are deemed important, we can encourage the system to retain
them in the models it produces by setting a higher standard for acceptable matches. For
example, requiring a higher Support measure ensures that matches will include more of

Figure

10: Shoe training images. Images were acquired at 6 ffi intervals over camera elevations
of 0 ffi to 12 ffi and azimuths of 0 ffi to 60 ffi . Shown here are three of the 33 images.

Figure

11: Left: Curve features for a model that generalizes 14 training images (support
threshold of 0.5). Right: Model that generalizes 7 training images (support threshold of
0.6).
an object's features. Thus, fewer of those features will be judged unreliable and more will
be retained by the model. Figure 11 (right) shows a model graph that was produced with
a Support threshold of 0.6 rather than the usual value of 0.5; it provides somewhat more
accurate representation of the shoe's heel and toe. Figure 12 shows this model graph being
used for recognition.
7.2.2 Articulate objects
Just as the system will use multiple views to model an object's appearance over a range of
viewpoints, it will use additional views to model a flexible or articulate object's appearance
over a range of configurations. In general, the number of views needed increases exponen-
Figure

12: Shoe recognition example. Left: Test image. Right: Image curve features included
in a match to shoe model.
sail angleffi elevation, 0
sail angleffi elevation, 0
sail angle

Figure

13: Boat training images. Images were acquired at elevations of 0
azimuths of 0 angles of 0 Shown here are three of the
images.

Figure

14: Boat model graphs. Shown here are curve features of model graphs that have
been generalized from two clusters of boat training images.
tially with the number of dimensions along which the object's appearance may vary. This
could presumably be addressed by a part-based modeling and clustering approach that separated
the independent model parts.
The toy boat shown in figure 13 has a sail that rotates about the boat's vertical axis.
Training images were acquired at camera elevations of 0
of angles of 0 . The system's learning procedure clustered
these 120 images to produce 64 model views. Features of two of the model graphs are
shown in figure 14. In comparison, only 13 views were needed to cover the same range of
viewpoints when the sail angle was kept fixed at 0 ffi .
8 Conclusion
We have presented a method of modeling the appearance of objects, of automatically acquiring
such models from training images, and of using the models to accomplish recognition.
This method can handle complex, real-world objects. In principle, it can be used to recognize
any object by its appearance, provided it is given a sufficient range of training images,
sufficient storage for model views, and an appropriate repertoire of feature types.
The main features of the method are as follows:
(a) Objects are modeled in terms of their appearance, rather than shape, to avoid any need
to model the image formation process. This allows unusually complex objects to be
modeled and recognized efficiently and reliably.
(b) Appearance is described using discrete features of various types, ranging widely in
scale, complexity, and specificity. This repertoire can be extended considerably, still
within the framework of the approach, to accommodate a large variety of objects.
(c) An object model represents a probability distribution over possible appearances of the
object, assigning high probability to the object's most likely manifestations. Thus,
learning an object model from training images amounts to estimating a distribution
from a representative sampling of that distribution.
(d) A match quality measure provides a principled means of evaluating a match between
a model and an image. It combines probabilities that are estimated using distributions
recorded by the model. The measure leads naturally to an efficient matching proce-
dure, probabilistic alignment, used to accomplish both learning and recognition.
(e) The model learning procedure has two components. One component identifies clusters
of training images that ought to correspond to distinct model views. It does so by
maximizing a measure that, by application of the minimum description length prin-
ciple, combines the qualities of model simplicity and accuracy. The second component
induces probabilistic generalizations of the images within each cluster. Working
together, the two components construct a model by clustering training images, and,
within each cluster, generalizing the images to form a model view.
8.1 Topics for further research
Modeling a multifarious or highly flexible object with this approach may require an impractically
large number of model views. For these objects, a more effective strategy may be first
to recognize parts, and then to recognize the whole object as a configuration of those parts.
The present method could perhaps be extended to employ this strategy by assigning parts
the role of high level features.
Speed in both learning and recognition tasks could be greatly improved by the addition
of an indexing component, which would examine image features and suggest likely model
views for the matching procedure to consider. Existing indexing methods (Beis and Lowe,
1999) could be used, with the attribute vectors of high-level features serving as index keys.
Of course, more efficient methods for feature detection would also be important.
Extending the feature repertoire would allow the method to work more effectively with
a broader class of objects. It would be useful to have features representing additional groupings
of intensity edges, such as symmetric arrangements and repeated patterns, and features
representing local image regions with color or texture properties.
Some challenging issues remain regarding how to organize a large collection of acquired
models for greater efficiency. Savings in both storage and recognition time could be achieved
by identifying parts or patterns common to several objects, factoring those parts out of their
respective models, and recognizing the parts individually prior to recognizing their aggre-
gates. Associating new feature types with some of the common parts and patterns would
provide a means of automatically extending the feature repertoire and adapting it to the objects
encountered during training. Furthermore, the same techniques of identifying and abstracting
parts could be used to decompose flexible objects into simpler components, allowing
those objects to be modeled with fewer views.

Acknowledgments

The authors would like to thank Jim Little, Bob Woodham, and Alan Mackworth for their
ongoing comments on this research. This research was sponsored by the Natural Sciences
and Engineering Research Council of Canada (NSERC) and through the Institute for Robotics
and Intelligent Systems (IRIS) Network of Centres of Excellence.



--R

HYPER: A new approach for the recognition and positioning of two-dimensional objects
Indexing without invariants in 3D object recognition.
Factorization Methods for Discrete Sequential Estimation.
Recognizing and locating partially visible objects: The local- feature-focus method
Geometric Aspects of Visual Object Recognition.
Symbolic reasoning among 3-D models and 2-D images
A probabilistic approach to object recognition using local photometryand global geometry.
Knowledge acquisition via incremental conceptual clustering.

Pose estimation by fusing noisy data of different dimensions.
IEEE Trans.
Recognizing solid objects by alignment with an image.
International Journal of Computer Vision 5(2)
Perceptual Organization and Visual Recognition.

Artificial Intelligence
Visual learning and recognition of 3D objects from appear- ance
A cubist approach to object recognition.
Computing exact aspect graphs of curved ob- jects: Algebraic surfaces
Learning to Recognize Objects in Images: Acquiring and Using Probabilistic Models of Appearance.
Vista: A software environment for computer vision research.

A universal prior for integers and estimation by minimum description length.
Annals of Statistics 11(2)
Machine perception of three-dimensional solids
Object recognition using multidimensional receptive field his- tograms
Local grayvalue invariants for image retrieval.
Color indexing.
Recognition by linear combination of models.
The Total Least Squares Problem: Computational Aspects and Analysis
Statistical approaches to feature-based object recognition
--TR
HYPER: a new approach for the recognition and positioning to two-dimensional objects
Three-dimensional object recognition from single two-dimensional images
Localizing overlapping parts by searching the interpretation tree
Recognizing solid objects by alignment with an image
Recognition by Linear Combinations of Models
Color indexing
Geometric aspects of visual object recognition
Computing exact aspect graphs of curved objects
Pose Estimation by Fusing Noisy Data of Different Dimensions
Visual learning and recognition of 3-D objects from appearance
Statistical Approaches to Feature-Based Object Recognition
Local Grayvalue Invariants for Image Retrieval
Indexing without Invariants in 3D Object Recognition
Perceptual Organization and Visual Recognition
Knowledge Acquisition Via Incremental Conceptual Clustering
A Probabilistic Approach to Object Recognition Using Local Photometry and Global Geometry
Object Recognition Using Multidimensional Receptive Field Histograms
Learning to recognize objects in images
A Cubist Approach to Object Recognition

--CTR
Rui Nian , Guangrong Ji , Wencang Zhao , Chen Feng, Probabilistic 3D object recognition from 2D invariant view sequence based on similarity, Neurocomputing, v.70 n.4-6, p.785-793, January, 2007
Wei Zhang , Jana Koeck, Hierarchical building recognition, Image and Vision Computing, v.25 n.5, p.704-716, May, 2007
David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004
Manuele Bicego , Umberto Castellani , Vittorio Murino, A hidden Markov model approach for appearance-based 3D object recognition, Pattern Recognition Letters, v.26 n.16, p.2588-2599, December 2005
Christian Eckes , Jochen Triesch , Christoph von der Malsburg, Analysis of cluttered scenes using an elastic matching approach for stereo images, Neural Computation, v.18 n.6, p.1441-1471, June 2006
Fred Rothganger , Svetlana Lazebnik , Cordelia Schmid , Jean Ponce, 3D Object Modeling and Recognition Using Local Affine-Invariant Image Descriptors and Multi-View Spatial Constraints, International Journal of Computer Vision, v.66 n.3, p.231-259, March     2006
Marcus A. Maloof , Ryszard S. Michalski, Incremental learning with partial instance memory, Artificial Intelligence, v.154 n.1-2, p.95-126, April 2004
M. A. Maloof , P. Langley , T. O. Binford , R. Nevatia , S. Sage, Improved Rooftop Detection in Aerial Images with Machine Learning, Machine Learning, v.53 n.1-2, p.157-191, October-November
object recognition;model indexing;appearance representation;visual learning;model-based vision;clustering