Distance Metric Between 3D Models and 2D Images for Recognition and Classification.
AbstractSimilarity measurements between 3D objects and 2D images are useful for the tasks of object recognition and classification. We distinguish between two types of similarity metrics: metrics computed in image-space (image metrics) and metrics computed in transformation-space (transformation metrics). Existing methods typically use image metrics; namely, metrics that measure the difference in the image between the observed image and the nearest view of the object. Example for such a measure is the Euclidean distance between feature points in the image and their corresponding points in the nearest view. (This measure can be computed by solving the exterior orientation calibration problem.) In this paper we introduce a different type of metrics: transformation metrics. These metrics penalize for the deformations applied to the object to produce the observed image.In particular, we define a transformation metric that optimally penalizes for "affine deformations" under weak-perspective. A closed-form solution, together with the nearest view according to this metric, are derived. The metric is shown to be equivalent to the Euclidean image metric, in the sense that they bound each other from both above and below. It therefore provides an easy-to-use closed-form approximation for the commonly-used least-squares distance between models and images. We demonstrate an image understanding application, where the true dimensions of a photographed battery charger are estimated by minimizing the transformation metric.
Introduction
Object recognition is a process of selecting the object model that best matches the observed
image. A common approach to recognition uses features (such as points or edges) to represent
objects. An object is recognized in this approach if there exists a viewpoint from
which the model features coincide with the corresponding image features, e.g. [Roberts, 1965,
Fischler and Bolles, 1981, Lowe, 1985, Huttenlocher and Ullman, 1987, Basri and Ullman, 1988,
Thompson and Mundy, 1987, Ullman and Basri, 1991]. Since images often are noisy and models
occasionally are imperfect, it is rarely the case that a model aligns perfectly with the image.
Systems therefore look for a model that "reasonably" aligns with the image. Consequently,
measures that assess the quality of a match become necessary.
Similarity measures between 3D objects and 2D images are needed for a range of applications

ffl The recognition of specific objects in noisy images, as described above.
ffl The initial classification of novel objects. In this application a new object is associated to
similar objects in the database. This way an image of, e.g., a Victorian chair is associated
with models of (different) familiar chairs.
ffl The recognition of non-rigid objects whose geometry is not fully specified. An example
is the recognition of 3D hand gestures. In this task only the generic shape of the gesture
is known, and the particular instances differ according to the specific physiology of the
hand.
Existing recognition methods are usually tailored to solve the first of these application, namely,
the recognition of specific objects from noisy images. Many of these methods are sub-optimal
(see Section 2 for a review), which may result in large number of either mis-recognition or
false-positives. When these methods are extended to handle problems such as classification and
recognition of non-rigid objects their performance may even be less predictable. The general
problem of recognition therefore requires measures that provide a robust assessment of the
similarity between objects and images. In this paper we describe two such measures, and
develop a rigorous solution to the minimization problem that each measure entails.
A common measure for comparing 3D objects to 2D images is the Euclidean distance between
feature points in the actual image and their corresponding points in the nearest view of
the object. The assumption underlying this measure is that images are significantly less reliable
than models, and so perturbations should be measured in the image plane. This assumption
often suits recognition tasks. Other measures may better suit different assumptions. For exam-
ple, when classifying objects, there is an inherent uncertainty in the structure of the classified
object. One may therefore attempt to minimize the amount of deformations applied to the
object to account for this uncertainty. Such a distance is measured in transformation space
rather than in image space. A definition of these two types of measures is given in Section 3.
Measures to compare 3D models and 2D images generally are desired to have metrical
properties; that is, they should monotonically increase with the difference between the measured
entities. exact definition is given in Appendix A.) The Euclidean distance between
the image and the nearest view defines a metric. (We refer to this measure as the image
metric.) The difficulty with employing this measure is that a closed-form solution to the
problem has not yet been found, and therefore currently numerical methods must be employed
to compute the measure. A common method to achieve a closed-form metric is to extend the
set of transformations that objects are allowed to undergo from the rigid to the affine one. The
problem with this measure is that it bounds the rigid measure from below, but not from above.
Other methods either achieve only sub-optimal distances, or they do not define a metric. The
existing approaches are reviewed in Section 2.
This paper presents a closed-form distance metric to compare 3D models and 2D images.
The metric penalizes for the non-rigidities induced by the optimal affine transformation that
aligns the model to the image under weak-perspective projection. The metric is shown to bound
the least-square distance between the model and the image both from above and below. We
foresee three ways to use the metric developed in this paper:
1. Obtain a direct assessment of the similarity between 3D models and 2D images.
2. Obtain lower and upper bounds on the image metric. In many cases such bounds may
suffice to unequivocally determine the identity of the observed object.
3. Provide an initial guess to be then used by a numerical procedure to solve the image
distance.
The rest of this paper is organized as follows: In Section 2 we review related work. In
Section 3 we define the concepts used in this paper. In Section 4 we summarize the main
results of this paper. These results are discussed in detail and proved in section 5 for the
transformation metric, and section 6 for the image metric. Sections 5 and 6 can be omitted
in first reading. Finally, in Section 7 we compare the distances between 3D objects and 2D
images, obtained by alignment, to our results.
Previous approaches
Previous approaches to the problem of model and image comparison using point features are
divided into three major categories:
1. Least-square minimization in image space.
2. Sub-optimal methods using correspondence subsets.
3. Invariant functions.
The traditional photometric approach to the problem of model and image comparison involves
retrieving a view of the object that minimizes the least-square distance to the image.
This problem is referred to as the exterior orientation calibration problem (or the recovery of the
hand-eye transform) and is defined as follows. Given a set of n 3D points (model points) and a
corresponding set of n 2D points (image points), find the rigid transformation that minimizes
the distance in the image plane between the transformed model points and the image points.
An analytic solution to this problem has not yet been found. (Analytic solutions to the absolute
orientation problem, the least-square distance between pairs of 3D objects, have been found,
see [Horn, 1987, Horn, 1991]. An analytic solution to the least-square distance between pairs
of 2D images has not yet been found.) Consequently, numerical methods are employed (see
reviews in [Tsai, 1987, Yuan, 1989]). Such solutions often suffer from stability problems, they
are computationally intensive and require a good initial guess.
To avoid using numerical methods, frequently the object is allowed to undergo affine transformations
instead of just rigid ones. Affine transformations are composed of general linear
transformations (rather than rotations) and translations, and they include in addition to the
rigid transformations also reflection, stretch, and shear. The solution in the affine case is simpler
than that of the rigid case because the quadratic constraints imposed in the rigid case are
not taken into account, enabling the construction of a closed-form solution. At least six points
are required to find an affine solution under perspective projection [Fischler and Bolles, 1981],
and four are required under orthographic projection [Ullman and Basri, 1991].
The affine measure bounds the rigid measure from below. The rigid measure, however, is
not bounded from above, as is demonstrated by the following example. Consider the case of
matching four model points to four image points under weak-perspective. Since in this case
there always exists a unique affine solution, the affine distance between the model and the image
is zero. On the other hand, since three points uniquely determine the rigid transformation that
aligns the model to the image, by perturbating one point we can increase the rigid distance
unboundedly.
A second approach to comparing models to images involves the selection of a small sub-set
of correspondences (alignment key), solving for the transformation using this subset, and
then transforming the other points and measuring their distance from the corresponding image
points. Three [Fischler and Bolles, 1981, Rives et al., 1981, Haralick et al., 1991] or four
[Horaud et al., 1989] points are required under perspective projection, and three points under
perspective [Ullman, 1989, Huttenlocher and Ullman, 1987] . The obtained distance
critically depends on the choice of alignment key. Different choices produce different distance
measures between the model and the image. The results almost always are sub-optimal, since
it is generally better to match all points with small errors than to exactly match a subset of
points and project all the errors onto the others.
A third approach involves the application of invariant functions. Such functions return a constant
value when applied to any image of a particular model. Invariant functions were successfully
used only with special kinds of models, such as planar objects (e.g., [Lamdan et al., 1987,
Forsyth et al., 1991]). More general objects can be recognized using model-based invariant
functions [Weinshall, 1993]. For noise-free data, model-based invariant functions return zero if
the image is an exact instance of the object. To account for noise, the output of these functions
usually is required to be below some fixed threshold. In general, very little research has been
conducted to characterize the behavior of these functions when the model and the image do
not perfectly align. The result of thresholding therefore becomes arbitrary.
3 Definitions and notation
In the following discussion, we assume weak-perspective projection. Namely, the object undergoes
a 3D transformation that includes rotation, translation, and scale, and is then orthographically
projected onto the image. Perspective distortions are not accounted for and treated as
noise.
In order to define a similarity measure for comparing 3D objects to 2D images, as discussed
in section 1, we first define the best-view of a 3D object given a 2D image:
difference measure between two 2D images of n
features. Given a 2D image of an object composed of n features, the best-view of a 3D object
(model) composed of n corresponding features, is the view for which the smallest value of @ is
obtained. The minimization is performed over all the possible views of the model; the views
are obtained by applying a transformation T , taken from the set of permitted transformations
, and followed by a projection, \Pi.
We compute @, the difference between two 2D images of n features in two ways:
image metric: we measure position differences in the image, namely, it is the Euclidean distance
between corresponding points in the two images, summed over all points.
transformation metric: the images are considered to be instances of a single 3D object.
The metric measures the difference between the two transformations that align the object
with the two images. This difference can be measured, for instance, by computing the
Euclidean distance between the matrices that represent the two transformations (when
the two transformations are linear).
As mentioned above, the measure @ is applied to the given image and to the views of the
given model. These views are generated by applying a transformation from a set   of permitted
transformations. The view that minimizes the distance @ to the image is considered as the best
view, and the distance between the best view and the actual image is considered as the distance
between the object and the image.
We consider in this paper two families of transformations: rigid transformations and affine
transformations, and we discuss the following metrics:
that measures the image distance between the given image and the best rigid
view of the object.
that measures the image distance between the given image and the best affine
view of the object.
We assume that the image is an affine view of the object. (When
it is not, we substitute the image by the best affine view.) We look for the rigid view
of the object so as to minimize the difference between the two transformations: the
affine transformation (between the object and the image) and the rigid transformation
(between the object and its possible rigid views.) In other words, we look for a view so
as to minimize the amount of "affine deformations" applied to the object.
To illustrate the difference between image metrics and transformation metrics, Figure 1
shows an example of three 2D images, whose similarity relations reverse, depending on which
kind of metric is used. Consider the planar object in Figure 1(b) as a reference object, and
assume   contains the set of rigid transformations in 2D. The images in (a) and (c) are obtained
by stretching the object horizontally (by 9/7) and vertically (by 3/2) respectively. (The image
in (b) is obtained by applying a unit matrix to the object.)
a) b) c)
closer in
space
closer in
space
image-

Figure

1: The 2D image shown in (b) is closer to the image in (a) when the difference is computed in
transformation space, and closer to the image in (c) when the difference is the Euclidean difference between the
two images.
ffl The image metric between the images in (b) and (a) is 4, two pixel at each of the left
corners of the rectangle.
The image metric between the images in (b) and (c) is 2, one pixel at each of the upper
corners of the rectangle.
Therefore, according to the image metric, Figure (c) is closer to (b) than (a) is.
ffl To compute the transformation metric consider the planar object illustrated in (b). We
compute the difference between the matrices that represent the affine transformation from
(b) to both (a) and (c) and the matrix that represent the best rigid transformation (in
this case it is the unit matrix): (a) is obtained from (b) by a horizontal stretch of 9=7.
The transformation metric between (a) and (b) is therefore
(c) is obtained from (b) by a vertical stretch of 3=2. The transformation metric in this
case is
Therefore, according to the transformation metric, Figure (a) is closer to (b) than (c) is.
It is interesting to note that in this example the solution obtained by minimizing the transformation
metric seems to better correlate with human perception than the solution obtained by
minimizing the image metric.
3.1 Derivation of N im and N af
We now define the rigid and the affine image metrics explicitly. Under weak-perspective pro-
jection, the position in the image, ~q of a model point ~
rigid transformation is given by
where R is a scaled, 3 \Theta 3 rotation matrix, ~ t is a translation vector, and \Pi represents an
orthographic projection. More explicitly, denote by ~r T
1 and ~r T
2 the top two row vectors of R,
and denote ~ we have that
where
The rigid metric, N im , minimizes the difference between the two sides of Eq. (1) subject to the
constraints (2).
When the object is allowed to undergo affine transformations, the rotation matrix R is
replaced by a general 3 \Theta 3 linear matrix (denoted by A) and the constraints (2) are ignored.
That is
Denote by ~a Tand ~a Tthe top two row vectors of A, we obtain
The affine metric, N af , minimizes the difference between the two sides of Eq. (3).
To define the rigid and the affine metrics, we first note that the translation component of
both the best rigid and affine transformations can be ignored if the centroids of both model
and image points are moved to the origin. In other words, we begin by translating the model
and image points so that
We claim that now ~ The proof is given in Appendix C.
Denote
a matrix of model point coordinates, and denote
~x =B @
x nC A ~y =B @
y nC A (5)
the location vectors of the corresponding image points. A rigid metric that reflects the desired
minimization is given by
The corresponding affine metric is given by
In the affine case the solution is simple. We assume that the rank of P is 3 (the case for
general, not coplanar, 3D objects). Denote the pseudo-inverse of P ; we
obtain that
And the affine distance is given by
Since the solution in the rigid case is significantly more difficult than the solution in the
affine case, often the affine solution is considered, and the rigidity constraints are used only for
verification (e.g. [Ullman and Basri, 1991, Weinshall, 1993, DeMenthon and Davis, 1992]).
The constraints (2) (substituting ~a i for ~r i , and using Eq. (8)) can be rewritten as
~x
~x
Denote
we obtain that
where B is an n \Theta n symmetric, positive-semidefinite matrix of rank 3. (The rank would be
smaller if the object points are coplanar.)
We call B the characteristic matrix of the object. B is a natural extension to the 3 \Theta 3
model-based invariant matrix defined in [Weinshall, 1993]. A more general definition, and its
efficient computation from images, is discussed in Appendix B.
3.2 Derivation of N tr
We can now define a transformation metric as follows. Consider the affine solution. The nearest
"affine view" of the object is obtained by applying the model matrix, P , to a pair of vectors, ~a 1
and ~a 2 , defined in Eq. (8). In general, this solution is not rigid, and so the rigid constraints (2)
do not hold for these vectors. The metric described here is based on the following rule. We are
looking for another pair of vectors, ~r 1 and ~r 2 , which satisfy the rigid constraints, and minimize
the Euclidean distance to the affine vectors ~a 1 , and ~a 2 . P~r 1 and P~r 2 define the best rigid view
of the object under the defined metric. The metric, N tr , is defined by
where ~a 1 and ~a 2 constitutes the optimal affine solution, therefore
In Section 5 we present a closed-form solution for this metric, and in Section 6 we show how
this metric can be used to bound the image metric from both above and below.
4 Summary of results
In the rest of the paper we prove the following results:
4.1 Transformation space:
The transformation metric defined in Eq. (13) has the following solution
N tr =2
where B is defined in Eq. (10), and ~x; ~y in Eq. (5). The best view according to this metric is
given by
~y
are defined in Appendix D.
4.2 Image space:
Using N tr we can bound the image metric from both above and below. Denote
we show that
are the eigenvalues of P T P . A sub-optimal solution to N im is given by
where the computation of - described in Appendix E. A tighter upper bound is deduced
from this sub-optimal solution
is the Harmonic mean of - 2 , - 3 . The sub-optimal solution is
proposed as an initial guess for an iterative algorithm to compute N im .
5 Closed-form solution in transformation space
We now present a metric to compare between 3D models and 2D images under weak perspective
projection. The metric is a closed-form solution to the transformation metric, N tr defined in
Eq. (13). We use the notation developed in Section 3. B is the n \Theta n characteristic matrix
of the object, ~x; ~y 2 R n contain the x- and y-coordinates of the image features. The metric is
given by
This metric penalizes for the nonrigidities of the optimal affine transformation. Note that
if the two rigid constraints in Eq. (11) are satisfied. Otherwise, N tr ? 0 represents the
optimal penalty for a deviation from satisfying the two constraints.
Derivation of the results:
In the rest of this section we prove that the expression for N tr , given by Eq. (14), is indeed
the solution to the transformation metric defined in Eq. (13). The proof proceeds as follows:
Theorem 1 computes the minimal solution when ~r 1 and ~r 2 are restricted to the plane spanned
by ~a 1 and ~a 2 ; Theorem 2 extends this result to three-space.
a
a
r
r22

Figure

2: The vectors ~a 1 , ~a 2 , ~r 1 , and ~r 2 in the coordinate system specified in Theorem 1. ~a 1 and ~a 2 represent
the solution for the affine case. ~r 1 and ~r 2 are constrained to be in the same plane with ~a 1 and ~a 2 , to be orthogonal,
and to share the same norm.
Theorem 1: When ~r 1 and ~r 2 are limited to spanf~a 1 ; ~a 2 g, N tr is given by Eq. (14).
Proof: We first define a new coordinate system in which
(see

Figure

2). ' is the angle between ~a 1 and ~a 2 , w 1 and w 2 are the lengths of ~a 1 and ~a 2
respectively. s is the common length of the two rotation vectors, ~r 1 and ~r 2 , and \Gammaff is the angle
between ~a 1 and ~r 1 . Without loss of generality it is assumed below that 0 ffi - 180 ffi and
. Notice that w 1 , w 2 , and ' are given and that s and ff are unknown.
Denote f the term to be minimized, that is
then
The partial derivatives of f are given by
To find possible minima we equate these derivatives to zero
Solutions with are not optimal. In this case f(ff;
2 , and later we show that
solutions with s ? 0 always imply smaller values for f .
When s 6= 0, f
tan ff
therefore
cos ff min =q
Notice the similarity of this expression to the expression for f . At the minimum point f can
be rewritten as
(From which it is apparent that any solution for f with s 6= 0 would be smaller than the solution
with Substituting for ff min we obtain
and therefore
or,
Recall that w 1 and w 2 are the lengths of ~a 1 and ~a 2 , that is
and ' is the angle between the two vectors, namely
We obtain that
'In Theorem 1 we proved that if ~r 1 and ~r 2 are restricted to the plane spanned by ~a 1 and ~a 2 ,
the metric N tr is given by Eq. (14). In Theorem 2 below we prove that any other solution for
~r 1 and ~r 2 results in a larger value for f , and therefore the minimum for f is obtained inside the
plane, implying that N tr indeed is given by Eq. (14).
Theorem 2: The optimal ~r 1 and ~r 2 lie in the plane spanned by ~a 1 and ~a 2 .
Proof: Assume, by way of contradiction, that ~r 1 we show that the
corresponding value for f is not minimal.
Consider first the plane spanned by ~r 2 and ~a 1 , and assume, by way of contradiction, that
we show that there exists a vector ~r 0
1 such that
and
contradicting the optimality of f .
Assume
1 a vector with length s in the direction (~r 2 \Theta ~a 1 ) \Theta ~r 2 .
This vector lies in spanf~r 2 ; ~a 1 g and satisfies
(There exist two such vectors, opposing in their direction. We consider the one nearest to ~a 1 .)
We now show that
Denote the angle between ~a 1 and ~r 0
1 by ff, and denote the angle between ~r 0
1 and ~r 1 by fi. Also,
k. We can rotate the coordinate system so as to
obtain
and therefore, when ff
contradicting the minimality property. Therefore, ~r g. Similarly, it can be shown
that ~r 2 2 spanf~r 1 ; ~a 2 g, therefore all four vectors ~a 1 , ~a 2 , ~r 1 , and ~r 2 lie in a single plane.Corollary 3: The transformation metric is given by
and the best view for this metric is
~y
where
Proof: The expression for the metric immediately follows from Theorem 1 and 2. The
expression for the best view is developed in the Appendix D.6 Solution in image space
In order to compute the image metric as defined in section 3, we need to solve the constraint
minimization problem defined in Eq. (6)
Section 6.1 shows that N tr , computed in the previous section, can be used to bound N im
from both above and below. Section 6.2 describes a direct method to compute a sub-optimal
approximation to N im and outlines an iterative algorithm to improve this estimate to obtain
the optimal N im .
6.1 Bounding the image metric with the transformation metric
In this section we show that using the transformation metric defined in Section 5 N tr , and the
affine metric N af (given in Eq. (9)), we can bound the image metric N im from both above and
below. We prove the following theorem:
Theorem 4: Let denote the three eigenvalues of P T P , then
Proof: Denote by ~r
1 and ~r
2 the vectors that minimize the term for the image metric given
in Eq. (6), namely
and denote by ~r 1 and ~r 2 the vectors that minimize the transformation metric given in Eq. (13),
namely
We start by showing the upper bound. Since ~r
1 and ~r
2 minimize the term for N im , we can
We now break each term in this sum into two orthogonal components as follows
for which it holds that
The orthogonality readily follows from the identity
Since the two components are orthogonal it holds that
and, similarly,
Therefore (recall that ~r 1 and ~r 2 minimize N tr and that - 3 is the largest eigenvalue of P T P )
Next, we prove the lower bound. The proof is similar to the proof in the upper bound case,
but this time we start by breaking up the terms into orthogonal components. Then we use the
facts that ~r 1 and ~r 2 minimize N tr and that - 1 is the smallest eigenvalue of P T P .
Consequently
Direct solution for the image metric
In this section we develop tighter bounds on the image metric by direct methods, following
the same steps we took in the derivation of the transformation metric in Section 5. Unlike for
the transformation metric, we cannot obtain a closed-form solution for the image metric, but
we can obtain a better estimator than we have previously described. This also enables us to
develop an iterative method to compute the distance exactly.
In section 6.2.1 we describe a change of coordinate system, arriving at a minimization
problem which is similar to the one we had to solve for the transformation metric. The difference
is that the sought vectors are constrained to lie on an ellipsoid rather than a sphere, and the
ellipsoid is defined by a 3 \Theta 3 positive-definite version of the characteristic matrix B.
In section 6.2.2 we restrict the solution vectors, ~u; ~v, to lie in a plane with the data vectors,
~x; ~y and we derive the optimal solution under this constraint. The solution, however, is only
sub-optimal, since in contrast to the transformation metric, the optimal solution in this case
does not have to lie in the plane. Using this solution we derive a tighter upper bound on the
optimal solution.
In section 6.2.3 we describe the general problem that needs to be solved, and outline an
iterative method. We propose the solution obtained in the plane as an initial guess for this
method.
6.2.1 Reducing the dimensionality of the problem
In Section 6.1 we have shown that the image metric can be broken into two orthogonal terms,
implying that
This property is useful for a direct computation of the image metric. The first term, N af , does
not depend on ~r 1 ; ~r 2 . To compute N im , therefore, only the second term needs to be minimized
min
Note first that PP + ~x and PP ~y, two vectors in R n , both lie in a single linear subspace of
dimension 3. (This follows from the fact, shown in [Ullman and Basri, 1991], that every image
of a 3D object can be written as a linear combination of three independent views.) Moreover,
the three columns of P lie in the same subspace. It therefore follows that the vectors
and must also lie in this subspace.
Denote ~
~y, the projection of ~x and ~y to the column space of P ,
and denote . (Note that ~r
characteristic matrix of the object.) We rewrite the problem as follows
min
Since all the vectors, ~
Y , ~u, and ~v, lie in a 3D subspace (the column space of P ) we can
perform the minimization in R 3 . To transform the system into R 3 , we rotate the vectors and the
characteristic matrix B so as to get nontrivial (nonzero) values only in three of the coordinates.
Recall that distances and quadratic forms are invariant under rotation. The rotation
that should be applied to all terms is defined by the eigenvectors of B. Applying this matrix
to B (in the
results in a diagonal matrix with the three positive eigenvalues of B.
6.2.2 Closed-form solution in the plane
Theorem 5: When ~u and ~v are limited to spanf ~
g, the solution of Eq. (19) is given by
~
are the principal axes of the ellipse, defined by the intersection of the ellipsoid
B with the plane spanf ~
Y g.
Note the similarity between this solution and N tr in Eq. (14). In fact,
~
The proof closely follows the proof for N tr presented in Section 5 (Theorem 2). We therefore
skip some of the details.
Proof: We first define a new coordinate system in which
~
~
Without loss of generality it is assumed below that \Gamma90
are given and that s and ff are unknown.
Notice that this setting of coordinate system is similar to the one used in Theorem 1 with
the exceptions that here ~u and ~v lie on an ellipse rather than on a circle, and that in general
none of the points can be brought to lie on a principal axis.
Denote by f the term to be minimized, that is
then
The partial derivatives of f are given by
To find possible minima we equate these derivatives to zero
Again, solutions with can be ignored since they do not correspond to the global minimum
(for a similar reason as in the proof of Theorem 1).
When s 6= 0, f
tan ff
cos ff min
and, similarly to Eq. (15),
We substitute s min and cos ff min , using the identity cos
, into Eq. (22). After
some manipulations, we obtain
~
from which it follows that
We substitute the identities from Eq. (25) into Eq. (23), obtaining the expression for ~
in Eq. (20).The derivation for - 1 and - 2 is given in Appendix E.
The sub-optimal solution in the plane can be used to improve the bounds on the image
metric, which were previously discussed in Theorem 4.
Theorem 3 be the three eigenvalues of P T P , then
, the Harmonic Mean of - 2 , - 3 .
Proof: The eigenvalues of the characteristic matrix B are 1
, and 1
. (This is shown
in

Appendix

E.) Since 1=- 1 and 1=- 2 represent the eigenvalues of a section of B it holds that
(see, e.g., [Strang, 1976] p. 270)- 1
Using Eq. 21 we obtain that
~
And, using Eq. 17 we obtain the upper bound
trCorollary 7:
Note that, since H:M:fa; bg - 2 minfa; bg for every a; b, we have the following corollary.
Corollary 8:
We cannot yet improve the lower bound in theorem 4; but we conjecture that
Conjecture 1: Let 3 be the three eigenvalues of P T P , then
Motivation: We know that if the two data points ~
X, ~
Y lie on the ellipse whose principal
axes are of length - 1 , - 2 (the smallest cross-section of the ellipsoid B), then
We can show that this solution is a local minimum, namely, it is not possible to improve the
solution by applying small perturbations to the solution vectors.6.2.3 An iterative optimal solution
The solution we obtained in Theorem 5 is sub-optimal; it is not the lowest distance. We now
give the cost function, a function of four variables, which should be minimized to obtain the
precise value of the image metric.
We first define a coordinate system such that
~
~
sin ff cos fi sin fl);
sin ff sin fi sin fl);
are known, and s, ff, fi and fl are free.
Note that this setting of coordinate system is similar to the one used in Theorem 5, but
now ~u and ~v lie on an ellipsoid rather than on an ellipse.
In this notation the free parameters are selected so as to satisfy the two rigid constraints,
To compute the image metric, the following function should be
minimized.
f(s; ff; fi;
N im is the global minimum of f(s; ff; fi; fl). Assuming that f(s; ff; fi; fl) is convex in the area
that contains both the global minimum N im and the sub-optimal solution (N af
employ the following iterative method to compute N im :
1. compute ~
2. improve the solution by any gradient-descent method until a local minimum is obtained.
If the convexity assumption is correct, this method returns the correct image metric, otherwise
it may return a sub-optimal solution.
Simulations
To test the presented metric we have compared it with the alignment method. As was mentioned
in Section 2 the alignment method involves the selection of a small subset of correspondences
(alignment key), solving for the transformation using this subset, and then transforming the
rest of the points and measuring their distance from the corresponding image points. The
obtained distance critically depends on the choice of alignment key. Different choices produce
different distance measures between the model and the image. The results are almost always
sub-optimal, since it is usually better to match all points with small errors than to exactly
match a subset of points and project the errors entirely onto the others.
In our simulations, models composed of four points were projected to the image using weak
perspective projection. Gaussian noise (with standard deviation 0:05 of the radius of the 3D
object) was added to the obtained images. Using the expression for N tr given in (14), we
computed the upper and lower bounds on the image metric between the model to the noisy
images. In addition, we computed the corresponding alignment distances, each reflecting the
distance between one model point and its predicted projection in the image after the alignment
of the remaining three image points to the model.
The figures below summarize our results. Figure 3 shows the percentage of alignment
distances which actually lie within the bounds on the image metric computed by our metric
percent
inside
range
condition number
tight bounds
general bounds

Figure

3: The percent of alignment distances which lie within the bounds on the image metric computed from
our closed-form equations. The abscissa gives the condition number of the characteristic matrix, B, which
determines how far apart the lower and upper bounds on the image metric are. The larger the condition number
is, the further apart the bounds are. Solid alignment distances relative to the wide bounds from Eq. (26).
Dashed lines: alignment distances relative to the tight upper bound from Eq. (27).
(given in Eq. (26)). It can be seen that when the bounds are relatively tight (when the condition
number on the characteristic matrix B is relatively low) most of the alignment solutions
exceed the upper bound. Only when the condition number gets larger do the alignment distances
lie within the bounds. When a tighter upper bound is used (Eq. (27)), a smaller portion of the
alignment distances actually lie within the bounds.

Figure

4 shows the maximal and minimal alignment distances obtained in different runs
relative to the upper and lower bounds on the image metric, given in Eq. (26) and Eq. (27). It
can be seen that in many cases even the best alignment solution (the one that minimizes the
still exceeds the upper bound.

Summary

We have proposed a transformation metric to measure the similarity between 3D models and
2D images. The transformation metric measures the amount of affine deformation applied to
the object to produce the given image. A simple, closed-form solution for this metric has been
presented. This solution is optimal in transformation space, and it is used to bound the image
metric from both above and below.
alignment
(log
scale)
a random model and image
smallest alignment distance
largest alignment distance1.583.9810.0025.1263.10alignment
(log
scale)
a random model and image
smallest alignment distance
largest alignment distance
(a) (b)1.583.9810.0025.1263.10alignment
(log
scale)
a random model and image
smallest alignment distance
largest alignment distance1.583.9810.0025.1263.10alignment
(log
scale)
a random model and image
smallest alignment distance
largest alignment distance
(c) (d)

Figure

4: The maximal and minimal alignment distances are plotted for a number of models and objects,
varying along the abscissa. The distances in these plots were normalized so as to obtain constant lower and
upper bounds (the lower bound is set to 1; the upper bound is set to be the average ratio of the upper bound to
the lower bound in each sequence of runs). Small (between 1:5 and 2:5) and large (between 4:5 and 5:5) condition
numbers are used, and the results are compared to both the wide (Eq. (26)) and the tight (Eq. (27)) bounds. (a)
Small condition number, wide bounds. (b) Small condition number, tight bounds. (c) Large condition number,
wide bounds. (d) Large condition number, tight bounds.
The transformation metric presented in this paper can be used in several different ways in
the recognition and classification tasks:
1. It provides a direct assessment of the similarity between models and images. Measuring
the amount of deformation applied to the objects makes it suited for the task of object
classification where the uncertainty in the structure of the observed objects is inherent.
2. The transformation metric can be used to bound the image metric, the distance between
the image and the closest view of the object, from both above and below. As shown
by our simulations, these bounds often provide better estimates than those provided by
using alignment. Consequently, we believe that in many cases the bounds suffice to
unequivocally determine the identity of the observed object.
3. The transformation metric provides a sub-optimal closed-form estimate for the image
metric. A scheme which uses this measure will prefer "symmetric" objects, objects whose
convex-hull is close to a sphere, over other objects which are significantly stretched or
contracted along one spatial dimension. This solution can also be used as an initial guess
in an iterative process that computes the optimal value of the image metric numerically.
Appendices
A Metric properties
The measures described in this paper compare entities of different dimensionalities: 3D objects
and 2D images. We define a metric for comparing such entities as follows. Let P be a set of n
model points, and let q be a set of n corresponding image points. A distance function, N(P; q),
defined using a difference function @(q; q 0 ) between two views (see Section 3), is called a metric
if
1. for every model P and image q.
2. only if, q is a rigid view of P .
3.
For the image metric, N im , @ is simply the Euclidean distance between corresponding points in
the compared images. It is straightforward to see that the conditions hold for this case. In the
rest of this appendix we prove that these conditions also hold for the transformation metric,
N tr .
Transformation metric
The transformation metric, N tr , measures the amount of "affine deformation" applied to the
object in the image. The metric conditions for N tr are defined as follows.
1. for every model P and image q.
2. only if, there exists a rigid view which coincides with PP
other words, the best affine view of the object is a rigid view and there is no "affine
deformation".)
3.
Theorem 9: N tr is a metric.
Proof:
1. N tr - 0. N tr minimizes a non-negative distance function. It is therefore always non-negative

2. only if, the best affine view is rigid. Denote ~x and ~y the x and y coordinates
of the points in q, according to Eq. (14)
This equation holds if, and only if, both sides are zero implying that
The best affine view of the object is given by PP y. Following Eq. (11), the best
affine view also satisfies the rigidity constraints above, and therefore it forms a rigid view.
3. The metric N tr is defined in Eq. (13) as:
N tr
Let ~
w 2 be the optimal vectors for q 0 , that is
N tr
And we obtain
N tr
B The computation of the characteristic matrix
In Eq (10) the characteristic matrix B was defined using the matrix of Euclidean model point
coordinates P . We now give a more general (though equivalent) definition of B using a matrix of
affine model point coordinates Q. Namely, the point coordinates in Q are given in a coordinate
system whose axes are not necessarily orthonormal. This definition makes it possible to compute
B directly from three or more images with a completely linear algorithm, which requires no
more than pseudo-inverse.
We select an affine coordinate system whose independent axes are defined by three of the
object points, to be called the basis points. Let P bas denote the submatrix of P corresponding
to the coordinates of the basis points, and let Q denote the affine coordinates of all the object
points in this basis. It immediately follows that:
denote the characteristic matrix of the three basis points. From Eq (10) it follows that
bas (30)
Finally, from the definition of pseudo-inverse it can be readily verified that
We now describe B in terms of Q and B bas . Substituting Eq (31) into the definition of B
in Eq (10), and using Eq (30), we obtain
The linear and incremental computation of the matrices Q and B bas from at least three
images of the object points is described in [Weinshall and Tomasi, 1992].
Eliminating translation
In this appendix we show that translation can be ignored if we set the centroids of both model
and image points to be the origin. To show this, we prove that the best rigid and affine
transformations maps the model centroid to the image centroid. We begin by showing that,
given two sets of n 2D points (images), the best translation that relates the two images maps
the centroid of the first image to that of the second.
be two sets of corresponding points.
Denote by -
the centroids of
The translation t   2 R 2 that minimizes the term
is given by
Proof: Assume, by way of contradiction, that the best translation is given by
for some nonzero ffi 2 R 2 . Denote the new term by D 0
p, we obtain that
and, therefore,
which implies that
contradicting the initial assumption.Using Lemma 10 we prove that the best rigid and affine transformations map the model
centroid to the image centroid.
Theorem 11: Let 3 be a set of n model points, and let q be the
corresponding n image points. The rigid transformation fs   that minimizes the term
fs;R;tg
where \Pi denotes the orthographic projection, satisfies
Proof: Denote by according to Lemma
Since
we obtain that
The theorem holds also if we consider affine transformations rather then only the rigid ones.
The rotation matrix R is replaced in this case by a general linear transformation A.Theorem 11 shows that the best rigid and affine transformations map the model centroid to
the image centroid. Consequently, if the two centroids are moved to the origin, the translation
component vanishes. This follows immediately from Theorem 11, since
then
implies
In this appendix we develop an expression for the best view of the transformation metric, N tr .
The derivations here follow the notations used in the proof of Theorem 1, from which we have
that
s cos
s sin
According to Theorem 2, ~r g. We can therefore express ~r 1 and ~r 2 by
are scalars. Substituting the definitions of the vectors ~r 1 , ~r 2 , ~a 1 , and
~a 2 we obtain
s cos
\Gammas sin
and
s sin
s cos
Therefore
Substituting for s and ff we obtain
sin '
And substituting for w 1 , w 2 , and '
Now, to obtain the best view we use the following identities
~y
Therefore
~y
Computing the eigenvalues of an ellipse
In this appendix we compute the eigenvalues of the ellipsoid B and the eigenvalue of an elliptic
section of this ellipsoid.
We first show that the eigenvalues of the characteristic matrix, B, are 1
, and 1
are the three positive eigenvalues of P T P . This is derived as follows.
~a
Multiplying both sides by P T we obtain that
Denote ~
which implies that
Given ~
~y in R 3 , and a positive definite 3 \Theta 3 matrix B, let B 0
denote the ellipse defined by the intersection of the ellipsoid B with the plane spanf ~
g. We
need to find the eigenvalues of B 0 , 1
and 1
Without loss of generality we assume that ~
X and ~
Y lie on the ellipsoid defined by B (namely,
we normalize the vectors so that ~
the angle between ~
X and ~
Y . We define two orthonormal vectors ~x 0 and ~y 0 , which span the
plane spanf ~
Y g, as follows:
~
~
Y
~
Every vector ~v 2 spanf ~
Y g can be written as
and the intersection ellipse B 0 is given by
for A the 3 \Theta 2 matrix whose columns are ~x 0 and ~y 0 . We therefore have that
Substituting the expressions for ~x 0 and ~y 0 , we get
To obtain the two eigenvalues of B
and 1
, we solve the characteristic equation of B 0 ,
whose roots are

Acknowledgments

We thank Larry Maloney for valuable discussions and technical help, and Eric Grimson, Yael
Moses, and Tomasso Poggio for their comments to earlier drafts of this paper.



--R

The alignment of objects with smooth surfaces.

Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.
Invariant descriptors for 3-D object recognition and pose

An analytic solution for the perspective 4-point problem

Relative orientation revisited.
Object recognition using alignment.
On recognition of 3-d objects from 2-d images

Recovering the orientation and the position of a rigid body in space from a single view.
Machine perception of three-dimensional solids
Linear algebra and its applications.

A versatile camera calibration technique for high-accuracy 3d machine vision metrology using off-the-shelf tv cameras and lenses
Aligning pictorial descriptions: an approach to object recog- nition
Recognition by linear combinations of models.

Linear and incremental acquisition of invariant shape models from image sequences.
A general photogrammetric method for determining object position and orientation.
--TR

--CTR
Hau-San Wong , Kent K. T. Cheung , Horace H. S. Ip, An evolutionary optimization approach for 3D human head model classification, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California
Hau-San Wong , Kent K. Cheung , Chun-Ip Chiu , Yang Sha , Horace H. Ip, Hierarchical multi-classifier system design based on evolutionary computation technique, Multimedia Tools and Applications, v.33 n.1, p.91-108, April     2007
exterior orientation calibration;object recognition;affine deformations;3D-to-2D metric