The Complex Representation of Algebraic Curves and Its Simple Exploitation for Pose Estimation and Invariant Recognition.
AbstractNew representations are introduced for handling 2D algebraic curves (implicit polynomial curves) of arbitrary degree in the scope of computer vision applications. These representations permit fast, accurate pose-independent shape recognition under Euclidean transformations with a complete set of invariants, and fast accurate pose-estimation based on all the polynomial coefficients. The latter is accomplished by a new centering of a polynomial based on its coefficients, followed by rotation estimation by decomposing polynomial coefficient space into a union of orthogonal subspaces for which rotations within two-dimensional subspaces or identity transformations within one-dimensional subspaces result from rotations in $x,y$ measured-data space. Angles of these rotations in the two-dimensional coefficient subspaces are proportional to each other and are integer multiples of the rotation angle in the $x,y$ data space. By recasting this approach in terms of a complex variable, i.e., $x+iy=z$, and complex polynomial-coefficients, further conceptual and computational simplification results. Application to shape-based indexing into databases is presented to illustrate the usefulness and the robustness of the complex representation of algebraic curves.
Introduction
For shape recognition involving large databases, position-invariant 2D shape-recognition and
pose-estimation have to be performed by fast algorithms providing robust accurate estimates
subject to noise, missing data (perhaps due to partial occlusion) and local deformations. There
is a sizeable literature on alignment and invariants based on moments [1], B-splines [2], superquadrics
[3], conics [4], combinations of straight lines and conics, bitangeants [5], dierential
invariants [6, 7, 8, 9], and Fourier descriptors. Two observations are: these two problems (pose
estimation and pose-independent recognition) are often studied independently; though the preceding
approaches have their own signicant strengths and handle certain situations very well,
the two problems {pose-independent recognition and pose-estimation{ are unsolved if there is
large noise and large shape deformation present, there is missing data, and maximum estimation
speed and estimation accuracy are important. This paper presents an approach based on
algebraic (also referred to as implicit polynomial) curve models which meets these requirements
for pose estimation and for pose-invariant object recognition.
2D algebraic curves of degrees 4 or 6 are able to capture the global shape of curve data of
interest (see Fig. 1). However, our primary interest in algebraic curves in this paper is that
they have unparalleled features crucial to fundamental computer vision applications. First, we
derive a complete set of invariants for fast pose-invariant shape recognition. By a complete set
of independent invariants, we mean that it is possible to reconstruct, without ambiguity, the
algebraic curve shape from the set of invariants only. Since this set species the shape in a
unique way, these invariants can be used as \optimal" shape descriptors. (Of conceptual interest
is that this set of invariants, dened in the paper, is not necessarily complete algebraically).
Second, algorithms are given in the paper which permit single-computation pose estimation,
and slightly slower but more accurate iterative pose estimation based on all the polynomial
coe-cients. These features are due to the following contributions.
1. A complex basis is introduced for the space of coe-cient vectors leading to the complex
representation of algebraic curves of degree n, where n is arbitrary. The components of
the basis vectors are complex numbers, even though the resulting polynomial is still real.
This provides a representation from which we derive a complete set of rotation-invariants.
We fully describe how real and complex vector representations are related.
The complex basis arises not from consideration of the geometry of the algebraic curve
but rather from consideration of the geometry of the transformation of its coe-cients and
is built on the fact that when the (x; y) data set is rotated, the resulting coe-cient vector
undergoes an orthogonal transformation [1].
2. A new accurate estimate of an \intrinsic center" for an algebraic curve, which is based
on all of the polynomial coe-cients. The algebraic curve can then be centered by moving
its intrinsic center to the origin of the data coordinate system. This centering is invariant
to any prior translations a shape may have undergone. Computing the center requires a
single computation followed by a few iterations.
3. Pose-invariant shape recognition is realized by centering an algebraic curve, as in 2., and
then basing shape recognition on the complete set of rotation-invariant shape descriptors
indicated above in 1.
4. Fast pose-estimation. Estimating the Euclidean transformation, that has taken one shape
data-set into another using all the polynomial coe-cients is realized by: initial translation
estimation as the dierence in the estimated intrinsic centers, based on 2., of the two
curves; this is followed by rotation estimation, based on 1.; and is completed by one or
two iterations of translation estimation followed by rotation estimation, where coe-cients
for the two polynomials are compared using the representation in 1.
What is most important in the preceding methodology is that estimators used are linear
or slightly nonlinear functions, which are iterated a few times, of the original polynomial co-
e-cients, thus being stable. Highly nonlinear functions of polynomial coe-cients, which have
been used previously, usually are not as robust and repeatable.
Note, the invariant representations we use with algebraic curves are global. At this stage of
the research, we do not know if these representations are well suited to highly-accurate nely-
discriminating shape recognition and therefore look upon the recognition, when dealing with
very very large image databases, to be used for the purpose of indexing into these databases.
The idea is to reduce the number of images that must be considered in the database by a large
factor using our invariant recognition, and then do more careful comparison on the shapes that
remain. This more careful comparison would involve pose estimation for alignment followed
by careful comparison of aligned shape data. This careful comparison of aligned shapes could
then be done through our PIMs measure [10] or through other measures.
How do Fourier descriptors compare with the algebraic curve model? Fourier descriptors,
like algebraic curves, provide a global description for shapes from which pose and recognition
can be processed. But the Fourier approach has di-culty in general with open patches or is
restricted to star shapes, depending on the parameterization used. In particular, when dealing
with missing data, small extra components, and random perturbations, heuristic preprocessing
must be applied to the curve data in order to close and clean it, and then arc-length normalization
problems arise in the comparison between shapes. This is also the case with curvature
descriptors [11]. In matching open curves having inaccurately known end points, both of these
approaches require extensive computation for aligning starting and stopping points.
For algebraic 2D curves and 3D surfaces, the most basic approach to comparison of two
shapes is iterative estimation of the transformation of one algebraic model to the other followed
by recognition based on comparison of their coe-cients or based on comparing the data set
for one with the algebraic model for the other [12, 1, 10]. But the problem of initialize this
iterative process still remains. A major jump was the introduction of intrinsic coordinate
systems for pose estimation and Euclidean algebraic invariants for algebraic 2D curves and 3D
surfaces [1, 6]. These are eective and useful, but as published do not use all the information
in the coe-cients.
The present paper is an expansion of the complex representation rst presented in [13]. A
later paper [14] presented a partial complex representation for algebraic curves for obtaining
some recognition invariants related to our complete set of invariants, and for pose estimation
based on only a few polynomial coe-cients. It also uses a dierent center for an algebraic
curve. Moreover, the authors are not concerned with concepts developed in this paper such as
complex bases and invariant subspaces, complete sets of invariants, and pose estimation using
and combining information available in all the polynomial coe-cients.
In Sec. 2, we introduce the decomposition of the coe-cient space with two examples: conics
and cubics under rotation. This leads to the complex representation of algebraic curves. Then, in
Sec. 3, the proposed pose estimation technique is described with validation experiments. Sec. 4
is dedicated to recognition with invariants. The proposed recognition algorithm is applied in
the context of indexing into a database of silhouettes, where algebraic representations allow us
to easily handle missing parts along the contour.
Algebraic Curve Model
2.1 Denition
An algebraic curve is dened as the zero set of a polynomial in 2 variables. More formally, a
2D implicit polynomial (IP) curve is specied by the following polynomial of degree n:
0j;k;j+kn a jk x j y
| {z }
| {z }
a
| {z }
| {z }
Hn
(1)
Here H r (x; y) is a homogeneous binary polynomial (or form) of degree r in x and y. Usually,
we denote by H n (x; y) the leading form. An algebraic curve of degree 2 is a conic, degree 3 a
cubic, degree 4 a quartic, and so on.
Polynomial f n is conveniently represented by coe-cient vector A, having components (a jk ),
(number of coe-cients is 1(n
where
a 01 a 20 a 11 a
2.2 A Useful Basis for Conics and Cubics under Rotation
We rst consider the representation of conics and cubics under rotation in order to exhibit
properties we want to exploit. A cubic curve is dened by 10 coe-cients:
(2)
When a cubic is rotated through angle , the are transformed
as a messy function of . The rotation matrix R() for the data is:6 4
cos  sin
sin  cos 7 56 4
x
which species the counter-clockwise rotation of the curve by  radians, equivalently the clock-wise
rotation of the coordinate system by  radians. The original cubic coe-cients are vector A
and the transformed one is A 0 . We denote with a prime the representation after transformation.
By substituting (3) in (2), and after expansion, we obtain the linear relation between the two
vectors A is a function of the rotation angle only. This
matrix can be put into a block diagonal form as shown
where the block L j transforms the coe-cients of the homogeneous polynomial of degree j, i.e
the j th form. Therefore, the size of the block L j is (j 1). We have
The elements of these blocks are non-linear functions of sin . For a second
degree form, to put things into a form exhibiting invariance and simple dependence on angle ,
we dene a new parameterization,  20 ,  20 ,
11 , of the coe-cients a 20 , a 11 , a 02 of the polynomial,
by applying the following matrix transformation, N 2 :6 6 6 6 6 4
203
| {z }
a 20
a 11
a
These new parameters  20 ,  20 and
are linear functions of the original polynomial coe-
cients. With this new representation, the matrix L 2 is mapped into a matrix where 2 appears:
That is, [  0
. The reason for this ,  notation is that
jk and  jk are the real and imaginary parts, respectively, of the complex coe-cient c jk 2 j+k
introduced in the next section. When the complex coe-cient c jj is always real, and
we have
. For L 3 , it turns out that a similar simplication is possible with the
transformation
a
a 21
a 12
a
and L 3 is mapped into:
In summary, when a cubic is rotated, there exists a natural basis determined by the square
matrices mapped into diagonal 2  2 and 1  1 sub block form:
The coe-cient vector of the cubic in the new basis is B, and B 0 after rotation R(). It is
clear that in this new basis, the coe-cient space is decomposed into a union of orthogonal
one or two dimensional subspaces invariant under rotations. More specically, the vector
vectors [ jk  jk ] T which rotate
with angles , 2, or 3. This leads directly to a simple and stable way to compute the relative
orientation between cubics, namely, estimate  by comparing the angle  ij of the pairs of
coe-cients [ jk  jk ] T in B with their transformations in B 0 . Moreover, it is easy to compute a
complete set of independent invariants under rotation for a conic:
linear invariants (i.e., linear functions of the IP coe-cients): coe-cients
invariants (i.e., second degree functions of the coe-cients): squared radiuses
2+  2= a 2+ a 2, and  2+  2= (a 20 a 02 a 2, of the 2D vectors
and 1 relative angle: the angle between  20
Note, to understand the angular invariant, under coordinate system rotation of  we see from (4)
that  20 transforms to 2 Hence, the angular dierence
is invariant to rotations. For a cubic, we complete the set of independent invariants
invariants: squared radiuses  2+  2= (a
and 2 relative angles: the angle between
In order to generalize this approach to IPs of arbitrary degree, we turn to complex numbers
and thus the complex representation of IPs.
2.3 Complex Representation of Algebraic Curves
Since we are dealing with rotations and translations of 2D curves, complex representation
provides a simplication in the analysis and implementation of pose estimation or pose-invariant
object recognition. Given the polynomial f n (x;
0j;k;j+kn a jk x j y k , the main idea is to
rewrite f n (x; y) as a real polynomial of complex variables z
a jk
Using binomial expansions for (z
z) j and (z  z) k , we rewrite f n (z) with new complex coecients
c jk
Notice that coe-cients (c jk ) are complex linear combinations of the (a jk ), and that  c
since the polynomial is real. We call the vector the complex vector representation of
an algebraic curve which is dened by a real polynomial in
z and z:
z z 2 zz
z zz 2
z 3 z is the vector of complex monomials. With
this notation, j +k species the degree of the multinomial in z and
z associated with c jk . Notice
that the sub-set of polynomials in z only is the well-known set of harmonic polynomials.
For example, the complex representation of a conic is f 2
c 11
are real numbers. From the previous section, it is easy to
show that
are the real and imaginary parts of the expression within
parenthesis. The complex representation of a cubic is f 3
The principal benet of the vector complex representation is the very simple way in which
complex coe-cients transform under a rotation of the polynomial curve. Indeed, we see that if
the IP shape is rotated through angle  (see (3)), z transforms as z
and by substituting in (5):
0j;k;j+kn
e i(j
Hence, the coe-cients of the transformed polynomial are
Moreover, as presented in the appendix, there is a recursive and thus fast way to compute the
matrix providing the transformation of a given polynomial coe-cient vector A to the new basis
C for any degree (it is the N j matrices introduced in the previous section).
3 Pose Estimation
As described in the previous section, the relation between the coe-cients C of a polynomial
and C 0 of the polynomial rotated is particularly simple when using the complex representation,
allowing us to compute the dierence of orientation between two given polynomial curves, C
and C 0 (see (6)). It turns out that the complex representation also has nice properties under
translation, allowing pose estimation under Euclidean transformation in a very fast way and
using all the polynomial coe-cients. At present, we view the most computationally-attractive
approach to pose estimation to consist of two steps. 1) Compute an intrinsic center for each
algebraic curve based on the coe-cients of its IP representation. This generalizes [1] to
optimally use all the information in the coe-cients. It is an iterative process with only a few
iterations. Center each algebraic curve at the origin of the coordinate system (i.e., move the
intrinsic center to the origin of the coordinate system), and then compute the rotation of one
algebraic curve with respect to the other based on the coe-cients of their IP representations.
This optimally uses all the information about the rotation in the coe-cients. It is not an
iterative process. Note, the translation of one curve with respect to another is then given in
terms of the dierence in their intrinsic centers. Hence, we are treating location and rotation
estimation separately in dierent ways. When processing speed is less important, maximum
accuracy under Euclidean transformations is achieved by following the preceding by a few
iterations as discussed in Sec. 3.4.

Figure

1: 3L ts of 4 th degree polynomials to a butter
y, a guitar body, a mig 29 and a sky-hawk
airplane. These are followed by two 6 th degree polynomials ts.
3.1 Implicit Polynomial Fitting
Since object pose estimation and recognition are realized in terms of coe-cients of shape-
modeling algebraic curves, the process begins by tting an 2D implicit polynomial to a data
set representing the 2D shape of interest. For this purpose, we use the gradient-one tting [15],
which is a least squares linear tting of a 2D explicit polynomial to the data set where the
gradient of the polynomial at any data point is soft-constrained to be perpendicular to the
data curve and to have magnitude equal to 1. This tting is of lower computational cost and
(a) (b) (c) (d)

Figure

2: In (a), the original data set is perturbed with a colored Gaussian noise along the
normal with a standard deviation of 0:1 for a shape size of 3 (equivalently, the data is contained
in a box having side length 375 pixels and the noise has 12.5 pixels standard deviation). In (b),
10% of the curve is removed. In (c), 5 4th degree ts are superimposed with associated noisy
data sets each having standard deviation of 0:1. In (d), 5 ts are superimposed when 10% of
the curve is removed at random starting points.
has better polynomial estimated-coe-cient repeatability than all previously existing IP tting
methods [15]. This algorithm is an improved version of the 3L tting [16], taking advantage of
the ridge regression approach. The algebraic curve is the zero set of this explicit polynomial.
A side benet of use of the gradient-one soft-constraint is that the tted polynomial is then
normalized in the sense that the polynomial multiplicative constant is uniquely determined.
Fig. 1 shows measured curve data and the t obtained. This tting is numerically invariant
with respect to Euclidean transformations of the data set, and stable with respect to noise and
a moderate percentage of missing data as shown in Fig. 2. 4 th degree ts allows us to robustly
capture the global shape, and higher degree polynomials provide more accurate ts as shown
in Fig. 1 with 6 th degree polynomials.
3.2 Translation
It is well known that a non degenerate conic has a center. Given two conics, the two centers are
very useful for estimating the relative pose since each conic can be centered before computing
the relative orientation. The goal of this section is to compute a stable center in the complex
representation with similar properties for polynomials having any degrees.
From (5), if z is transformed as z translated by t and rotated with an angle
t, and
After expansion, we obtain H 0
leading form:
c jk e i(j
Consequently, complex coe-cients (c 0
jk ) of the transformed leading form H 0
are unaected by
translation in the Euclidean transformation. Continuing expansion, we obtain the transformed
next-highest degree form H 0
having the coe-cients (c 0
z
1kn
z
z
These coe-cients are linear functions of the translation component t:
The rst interesting property of (7) is that the term depending on the angle is a multiplicative
factor in this set of equations. This means that, given any polynomial, the translation
which minimizes the linear least squares problem:
does not depend on the rotation applied to the polynomial. Therefore, the algebraic curve can
be translated by t linearcenter to center it at the origin of the coordinate system. This centering is
invariant to any Euclidean transformation the algebraic curve may have originally undergone.
This center is not dierent than the Euclidean center of a polynomial derived with the real
representation of IPs in [1].
Even if t linearcenter is computed by solving a linear system as above, it is not using all the
information available about the curve location, in particular, coe-cients c jk ; j < n 1, are not
involved. To use these, we proceed as follows. Compute linearcenter . Translate the polynomial,
having coe-cient vector C, by t linearcenter . The resulting polynomial coe-cient vector ~
C will
be independent of any previous translations the original data set may have undergone (in
practice approximately independent due to measurement noise and other deviations from the
ideal). Now recenter the ~
C polynomial to obtain ( ~
C)  by computing and using translation
C) jj 2 is minimum. Note, ~
C is an nth degree polynomial in ~ t, so we
compute ~ t iteratively by using a rst order Taylor series approximation and thus only the linear
~ t monomials in ( ~
C). All the ~ c jk are used in this computation, which is why t center has smaller
variance than does t linearcenter . Generally, the optimum jj ~ t jj is small and only 2 or 3 iterations
are needed to converge to the ~
minimizing jj ~
This denes the center t center which we use.
Note, this t center , determined solely by curve coe-cients C, is of sub-optimal accuracy because
we do not weight the components of C in an optimal way to achieve maximum likelihood or
minimum mean square error estimates.
The t center of a high degree polynomial has the same property as the conic center, namely,
it is covariant with the Euclidean transformation applied to the data. Consequently, it can
be used in the same way for comparing polynomial coe-cients: each polynomial C and C 0 is
centered by computing t center and t 0
center , before computing the relative orientation using all the
transformed coe-cients.
For illustration, consider the simple case of a conic. For a conic f 2
, the set of equations (7) is reduced to c 0
t) and
its conjugate. The well known center of a conic is dened as the point for which the linear
terms vanish, i.e, its position linearcenter 2c 20
linearcenter
is dierent from the more stable t center introduced before which is the one minimizing 2 j
center 2c 20
center
that this criterion involve all the IP coe-cients of the conic.
The second advantage of the complex representation is that we can derive not only one center
but several, a dierent one for each summand in (8), with the same covariance to Euclidean
Transformations. The property used here is that c 0
depends only on c n 1 k k , c n k k , and
i.e, the complex representation decouples the rotation and the translation which
is not the case with the coe-cients a jk . For every equation in (7), we are able to dene a
new Euclidean center for the IP as t k for which the right side is 0, as done in the conic case.
Consequently, an IP of degree n has [ n] extra centers t k ([u] denotes the greatest integer not
exceeding u), dened by:
A nice property of these centers for two curves is that they match one to another without
a matching search problem since we know the degree k associated with the center t k . Hence,
given two polynomials C and C 0 of degree n, after the computation of the [ n] centers for each
polynomial, approximative but simple pose estimation is determined by [ n] matched points.
Pose estimation of 4 th degree algebraic curves can be solved by doing the pose estimation
between two centers, pose estimation of 6 th degree polynomials by doing the pose estimation
between two triangles, and so on. Of course, these centers do not use all the pose information
contained in the polynomial coe-cients, so this pose estimation can be used either for fast
computation or for a rst approximation to maximum accuracy Euclidean pose estimation.
3.3 Rotation
Experimentally, it turns out that the center is very stable in the presence of noise and small
perturbations (see Fig. 3). The computation of the rotation is in practice less accurate. There-
fore, it is important to take advantage of all the information available in the polynomial to
obtain the most accurate orientation estimation possible. Assume that the two polynomials
are each centered by using Euclidean center t center dened in the previous section.
For a cubic, under rotation R(), C transforms to the vector C
. In this equation, as seen in Sec. 2.2, complex coefcients
are rotated by angle , c 20 by angle 2, and c 30 by angle 3. We use all of
this information to estimate .
In the general case, from (6), C 0 as a function of C under a rotation  is given by c 0
c jk e i(j Given C and C 0 , we simply used least squares to estimate
min
which leads to maximization of
l jk is an
unknown integer when j k 6= 1, and 2l jk
is the unknown phase. Integer l jk is between 0 and
k 1. It is inserted to make the argument of the cosine close to 0, thus permitting the cosine
to be well approximated by its second order Taylor expansion. Then an explicit approximated
solution is derived:
where weights w jk are (j
(These weights can be easily used to test if an IP has , 2,
, or any other kind of symmetries. Consequently, we are not limited to non-symmetric shapes
in computing the pose estimate). The obtained solution is a good approximate solution, and a
few iterations may be used to obtain the closest sub-optimal solution. An optimal estimate can
be obtained using a Bayesian formulation and iterative globally optimizing techniques. In this
case, the summands in (10) would be weighted by an appropriate inverse covariance matrix.
Since the computational cost is very small, the best estimated angle can be obtained by
computing the estimate for all possible integers l jk and choosing the one which minimizes the
weighted standard deviation of arg(c 0
. An even faster alternative is to get
a good rst estimate of  by combining arg(c 0
or by using the
centers dened with (9).
3.4 Estimation of Euclidean transformations
To estimate the Euclidean transformation between two shapes:
noise missing data 20% missing data
5.7% 72.1% 2.9% 37.8%
translation 5.9% 13.4% 3.0% 6.0%

Table

1: Standard deviation in percentage of the average of the angle and the norm of one
translation component, with various perturbations for object in Fig. 2. Added colored Gaussian
data noise has standard deviations 0:1 and 0:2 (12.5 and 25 pixels respectively). Occlusions are
10% and 20% of the curve at random starting points. Statistics are for 200 dierent random
perturbations of each kind on the original shape data. As in Fig. 3, true rotation is 1 radian,
true translation is 1. (Data lies in box having side-length 375 pixels).
First each polynomial is centered by computing its center t center using information in all
the coe-cients of f n as discussed in Sec. 3.2.
Then the rotation alignment is performed by using information in all the coe-cients of
using (11) and the discussion in Sec. 3.3.
A rst estimate of the translation and rotation are the displacement from one center to
the other, and the rotation alignment.
To remove remaining small translation and rotation estimation errors, the translation and
the orientation alignment are iterated one or two times by minimizing the sum of squared
errors between the two sides of (7) and for all the other c jk , most of which involve higher
degree monomials in t and  t. This estimation of translation and rotation jointly results
in maximum accuracy.
The proposed pose estimation is numerically stable to noise and a moderate percentage of
missing data as illustrated in Fig. 3. The pose estimation error due to missing data increases
nicely in the range from 0 to 15% (19 pixels). Similar results are obtained in the range [0; 0:12]
for the standard deviation of the noise. The added noise is a colored noise [15], i.e, a Gaussian
noise in the direction normal to the shape curve at every point and then averaged along 10
consecutive points. We want to emphasis the fact that even if a noise standard deviation of 0:1
(equivalently, 12.5 pixels), is only 3% of the size of shape of the butter
y, this value of the noise
represent a very large perturbation of the shape as shown on Fig. 2(a). For greater amounts
of noise or missing data, we have the well know threshold eect [17] in estimation problems as
shown in Table 1. It arises in our problem because of the nonlinear computations in the angle
estimation.
angle
translation
error
noise std. dev. x
angle
translation
error

Figure

3: Left, variation of the standard deviation of the angle and the x component of the
translation as a function of increasing colored noise standard deviation. Right, variation as a
function of increasing percentage of missing data. Plotted values are std. deviation of the error
as a percentage of the average values of the pose components. Measurements based on 200
realizations. True rotation is 1 radian, translation is 1.
4 Recognition Using Invariants
In this section we solve the pose-independent shape recognition problem based on invariants
arising from the complex representation.
4.1 Stable Euclidean Invariants
|c40|
error
noise std. dev. x 105.0015.0025.0035.0045.000.00 100.00 200.00 300.00
|c40|
error
removed x 105.0015.0025.0035.0045.00

Figure

4: Left, variation of the standard deviations of invariants jc 40 j, c 11 , j2
as a function of increasing colored Gaussian noise std. deviation ( jk denotes
arg(c jk )). Right, variation of the standard deviation of the same invariants as a function of an
increasing percentage of missing data at random starting points. Values are std. dev. of the
error as a percentage of the average value of the invariant. 200 realizations of the shape data
were used.
When the IP is centered with the computation of the Euclidean center as described previously
in Sec. 3.2, we have canceled the dependence of the polynomial on translation, and the
only remaining unknown transformation is the rotation.
noise missing data 20% missing data
c 11 14.0% 26.8% 8.2% 16.7%

Table

2: Standard deviations as a percentage of the means of a few invariants in response
to various data perturbations. Gaussian colored noise has standard deviations 0:1 or 0:2.
Occlusions are 10% or 20% of the curve at random starting points. Statistics for each case are
computed from 200 dierent random realizations.
Since the number of coe-cients of f n is 1(n+1)(n+2) and the number of degrees of freedom
of a rotation is 1, the counting argument indicates that the number of independent geometric
invariants [18] is 1(n We directly have linear invariants which are c jj .
From (6), we deduce that all other jc jk j 2 are invariants under rotations. The number of these
independent quadratic invariants (2 nd degree functions of the c jk ) is the number of complex
This number is even degrees and
for odd degrees. Invariants jc jk j are geometric distances, but there are angles which also are
Euclidean invariants for an IP. Indeed, the o(o+1)relative angles (l m)arg(c jk ) (j k)arg(c lm )
are preserved under rotations. We can choose a maximal independent subset of these relative
angles and these along with the preceding linear and quadratic invariants provides a complete
set of independent rotation invariants for an IP of degree n, as for the cubic case in Sec. 2.2. We
want to emphasis the fact that the obtained invariants are linear, quadratic, or arctan functions
of ratios of linear combinations of coe-cients, even for high degree polynomials. This leads to
invariants less sensitive to noise than are others such as algebraic invariants which are rational
functions perhaps of high degrees, of the polynomial coe-cients. Moreover, these are the rst
complete set of Euclidean invariants for high degree IP curves appearing in the computer vision
literature.
As shown in Fig. 4 and Table 2, invariants are individually less stable than pose parameters.
In particular, angle invariants are more sensitive to curve-data perturbations. Nevertheless,
these angular invariants are useful for discriminating between shapes as illustrated in Fig. 5.
Moreover, as shown in Fig. 3, the better stability of the translation estimation in comparison
to the angle estimation allows rotation invariants to be computed out of the range of stability
of the angle estimation (0:2 noise std. dev. and 20% missing data). We observed that a few
angular invariants have a standard deviation several times larger than the others. It turns out
butterfly
guitar
butterfly
guitar

Figure

5: Left, scatter of invariants vector (jc perturbed data sets (colored noise
with 0:05 standard deviation) of the 4 IPs of degree 4 in Fig. 1. Right, scatter, in radians, of
invariants vector (3 10
that, for particular shapes, a few angular invariants become bimodal up to a particular amount
of noise such as  20  31 as shown in Fig. 5 for the sky-hawk.
4.2 Invariant Recognition
guitar butter
y sky-hawk mig
guitar 100% 0% 0% 0%
butter
y 0% 100% 0% 0%
sky-hawk 0% 0% 100% 0%
mig 0% 0% 0% 100%
guitar 95% 1.5% 3.5% 0%
butter
y 27.5% 72.5% 0% 0%
sky-hawk 2.5% 0% 97.5% 0%
mig 9.5% 0% 52% 38.5%
guitar 100% 0% 0% 0%
butter
y 0% 100% 0% 0.0%
sky-hawk 0.5% 0% 96% 3.5%
mig 4% 0% 0% 96%

Table

3: Percentage recognition on 3 sets of 200 perturbed shapes for colored noise of standard
deviations 0:05 and 0:1, and 10% missing data, respectively.
Fig. 5 shows scatter plots vectors of pairs of invariants for the 4 shapes of degree 4 of Fig. 1.
Though the scatter of individual components of invariant vectors are not always well separated,
the use of the complete set of invariants appears to yield highly accurate recognition. The
recognizer used is Bayesian recognition based on a multivariate colored Gaussian distribution
for each object and having a diagonal covariance matrix estimated from 200 noisy perturbed
shapes for each object with noise perturbation standard deviations 0:05 in the normal direction.
This model is used to do recognition on two other noisy sets having standard deviation 0:05
and 0:1 (the latter is 12.5 pixels and is at the limit of the stability for pose) and on one set with
10% missing data. Results are quite good (see Table 3). For large noise perturbations (0:1 std.
dev. colored noise), the sky-hawk becomes di-cult to recognize from the other airplane, since
details are lost in noise, but is still dierent from the guitar or the butter
y shapes. Better
accuracy would be achieved by using 6 th degree IP curves [15].
4.3 Indexing in a silhouette database
In the previous section, recognition is applied to datasets deformed by synthetic perturbations:
colored noise and missing data. To test the proposed recognition algorithm on real data, we
used a database of 1100 boundary contours of sh images obtained from a web site [11]. The
number of data points in each silhouette in this database varies from 400 to 1600. This database
contains not only shes but more generally sea animals, i.e, the diversity of shapes is large.
So as not to use size for easy discrimination between shapes, all shapes are normalized to the
same size. To prepare the database, every shape is t by a 4 th degree polynomial and then
polynomial curves are centered by setting t center at the origin. The last step is to compute
the rotation invariants as in the previous section. We rst run queries by example to test the
rotation invariants. Two examples are shown in Fig. 6 where the rotation invariance is clear.

Figure

Queries by example invariant to Euclidean Transformations and re
ections.
Then, we test the stability to small perturbations such as removing data on a few shapes and
running queries with these modied shapes. In Fig. 7, small parts are removed in the query. The
capability of the IPs to handle missing data (especially if small patches are removed at many
locations throughout a silhouette) and to handle open (non closed) curves is one of the main
advantage of this description in comparison to descriptions using arc length parameterization
such as Fourier descriptors or B-splines.
With our approach query by sketch is also possible. For every query, a Bayesian recognizer
is used since the variability of each invariant can have very dierent standard deviations. This
variability is estimated from a training set. This training set is synthetically generated from the
given sketch by adding perturbations: sample functions of a colored noise. Obtained standard
deviations are used to weight each invariant during the comparison between shapes in the
database, i.e, the Mahalanobis distance is used. (The optimal weighting is to use a full inverse

Figure

7: Queries by example where relative small parts as fans are removed.
covariance matrix in the quadratic-form recognizer, rather than the diagonal covariance matrix
approximation used in these experiments.) It turns out that depending on the talent of the
drawer and on the number of occurrences of and variability in the target shape in the database,
the user may want to control the similarity measure used between the query and the searched-for
database shapes. To handle this, the standard deviation used in generating training sets
is decreased or increased depending on whether more or less similarity is needed. Therefore,
in addition to the query, the user has to specify what degree of similarity he/she wants to
use: very similar (std. dev. is 0:02), similar (std. dev. is 0:1), weakly similar (std. dev. is
0:2). Fig 8 illustrate the database shapes found for the same query but using three dierent
similarity criteria.
Obviously, a 4 th degree polynomial is not able to discriminate shapes with only small scale
dissimilarities. Better discrimination power can be achieved by using 6 th degree polynomials,
see [15].

Figure

8: Queries using the same query example but with a recognizer trained on dierent
standard deviations of the colored noise (0:02, 0:1, and 0:2 respectively). The rst three closest
shapes are always retrieved, but increasing variability can be observed in the other retrieved
shapes.
Conclusions
Though the shape-representing IP's that we use may be of high degree, we have introduced fast
accurate pose estimation, and fast accurate pose-independent shape recognition based on geometric
invariants. Approximate initial single-computation estimates are computed, and these
are iterated 2 or 3 times to achieve the closest local minimum of the performance functionals
used. The pose estimation uses all the IP coe-cients, but is not optimal because it does not use
optimal weightings. The pose-independent recognition uses estimated centering based on all of
the IP coe-cients followed by rotation invariant recognition based on a complete set of geometric
rotation invariants. However, optimal weightings were not used here either. Nevertheless,
the eectiveness of the pose-invariant recognition is illustrated by the indexing application in a
database of 1,100 silhouettes. Though some of the invariants may not eective discriminators,
the complete set is. If put into a Bayesian or Maximum Likelihood framework, we can achieve
fully optimal pose estimation and pose-independent shape recognition.
Extensions to 3D based on tensors are undergoing further development [19], as well as
is handling local deformations. Of great importance is to extend the pose estimation and
transformation-invariant shape recognition to handle two situations. First is that for which
considerable portions of a silhouette are missing, perhaps due to partial occlusion or where the
silhouette is much more complicated. Then, pose estimation and recognition can be based on
\invariant patches". These invariant patches are discussed in [10], and the ideas in the present
paper should be applicable. The second extension is to handle a-ne rather than just Euclidean
transformations of shapes. The intermediate transformation, scaled Euclidean, should be easy
to handle, since an isotropic scaling of the data set by  simply multiplies every monomial of
degree d in the polynomial by the factor  d . The full a-ne transformation is more challenging,
and we are studying it. One approach is to convert the A-ne Transformation Problem to a
Euclidean Transformation Problem through a normalization based on the coe-cients of the
polynomials t to the data [1]. The challenge here is to develop a normalization that uses much
of the information contained in the polynomial coe-cients [18] and which is highly stable.
Another subject of interest is to consider small locally a-ne deformations along a silhouette.
6

Appendix

From Complex to Real Representation
What is the transformation relating the coe-cients in the real and complex polynomial repre-
sentations? Computing the coe-cients of the complex representation given a real IP appears to
be complicated. The transformation from the complex C to the real A vector representation,
i.e, the reverse way, is easier to compute. Vector C duplicates information since c
Therefore, it is in practice more e-cient to use the vector representation B with components
introduced in Sec. 2.2. Indeed, B
is a minimal description of C.
Transformation matrix T between B and A diagonal since the coe-cients
for a form transform independently of the coe-cients for each other form. Thus,
where T l is the transformation matrix of homogeneous polynomial H l of degree l.
The goal of this section is to nd a recursive way to compute T l . Consider the following
family of formal real homogeneous polynomials in complex representation:
D l (z) =2
0j;kl;j+k=l
with
d l j . We deduce the following second order recursive formula for D l (z):
D l (x;
l
l
where the second and third lines are the expansion of Re(d l  z l ). From the last equation, we
deduce a recursive computation for
l
kC A denotes the binomial coe-cient l!
(l k)!k!
. As an illustration, the rst three iterations
and one can check that from Sec. 2.2,
These matrices T l specify T (see (12)) which describes how a 2D polynomial is transformed
from its complex C to real A representation. In practice, to obtain the real and imaginary parts
of the complex polynomial coe-cients that represent a data set, we rst t a real polynomial
to the data set to estimate the coe-cient vector A, and then obtain B by

Acknowledgments

This work was supported in part by a postdoctoral grant from INRIA, Domaine de Voluceau,
Rocquencourt, France.



--R

Estimation of planar curves

Recovery of Parametric Models from Range Images: The Case for Superquadrics with Global Deformations.

Recognizing Planar Object Using Invariant Image Features.
Geometric Invariance in Computer Vision.
resistant invariants of curves.


Pims and invariant parts for shape recognition.
Robust and e-cient shape indexing through curvature scale space
On using CAD models to compute the pose of curved 3D objects.
A new complex basis for implicit polynomial curves and its simple exploitation for pose estimation and invariant recognition.
Complex representations of algebraic curves.
Improving the stability of algebraic curves for applications.

Information Transmission
Covariant conics decomposition of quartics for 2D object recognition and a-ne alignment
Pose estimation of free-form 3D objects without point matching using algebraic surface models
--TR

--CTR
Amir Helzer , Meir Barzohar , David Malah, Stable Fitting of 2D Curves and 3D Surfaces by Implicit Polynomials, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.10, p.1283-1294, October 2004
Cem nsalan, A model based approach for pose estimation and rotation invariant object matching, Pattern Recognition Letters, v.28 n.1, p.49-57, January, 2007
Jean-Philippe Tarel , William A. Wolovich , David B. Cooper, Covariant-Conics Decomposition of Quartics for 2D Shape Recognition and Alignment, Journal of Mathematical Imaging and Vision, v.19 n.3, p.255-273, November
Thomas B. Sebastian , Benjamin B. Kimia, Curves vs. skeletons in object recognition, Signal Processing, v.85 n.2, p.247-263, February 2005
Michael J. Black , Benjamin B. Kimia, Guest Editorial: Computational Vision at Brown, International Journal of Computer Vision, v.54 n.1-3, p.5-11, August-September
implicit polynomial curves;algebraic curves;shape recognition;complete-sets of rotation invariants;complex polynomials;euclidean invariants;pose estimation;shape representation;curve centers;pose-independent curve recognition