Quasi-Invariant Parameterisations and Matching of Curves in Images.
In this paper, we investigate quasi-invariance on a smooth manifold, and show that there exist quasi-invariant parameterisations which are not exactly invariant but approximately invariant under group transformations and do not require high order derivatives. The affine quasi-invariant parameterisation is investigated in more detail and exploited for defining general affine semi-local invariants from second order derivatives only. The new invariants are implemented and used for matching curve segments under general affine motions and extracting symmetry axes of objects with 3D bilateral symmetry.
Introduction
The distortions of an image curve caused by the
relative motion between the observer and the
scene can be described by specific transformation
groups (Mundy and Zisserman, 1992). For exam-
ple, the corresponding pair of contour curves of
a surface of revolution projected on to an image
center can be described by a transformation of
the Euclidean group as shown in Fig. 1 (a). If a
planar object has bilateral symmetry viewed under
perspective, the corresponding contour
curves of the object in an image can be described
by the special affine group (Kanade and Kender,
1983; Van Gool et al., 1995a) (see Fig. 1 (b)).
The corresponding contour curves of a 3D bilateral
symmetry such as a butterfly are related by
a transformation of the general affine group (see
Fig. 1 (c)). Since these corresponding curves are
equivalent objects, they have the same invariants
under the specific transformation group. Thus,
invariants under these transformation groups are
very important for object recognition and identification
(Moons et al., 1995; Mundy and Zisserman,
1992; Pauwels et al., 1995; Rothwell et al., 1995;
Gool et al., 1992; Weiss, 1993).
Although geometric invariants have been studied
extensively, existing invariants suffer from occlusion
(Abu-Mostafa and Psaltis, 1984; Hu, 1962;
Reiss, 1993; Taubin and Cooper, 1992), image
noise (Cyganski et al., 1987; Weiss, 1988) and the
requirement of point or line correspondences (Bar-
rett and Payton, 1991; Rothwell et al., 1995;
Zisserman et al., 1992). To cope with these
problems, semi-local integral invariants were proposed
(Bruckstein et al., 1993; Sato and Cipolla,
1996a; Sato and Cipolla, 1996b) recently. They
showed that it is possible to define invariants semi-
locally, by which the order of derivatives in invariants
can be reduced from that of group curvatures
to that of group arc-length, and hence the invariants
are less sensitive to noise. As we have seen in
these works, the invariant parameterisation guar-
118 Sato and Cipolla
antees unique identification of corresponding intervals
on image curves and enables us to define
semi-local integral invariants even under partial
occlusions.
Although semi-local integral invariants reduce
the order of derivatives required, it is known that
the order of derivatives in group arc-length is still
high in the general affine and projective cases (see
table 1). In this paper, we introduce a quasi-invariant
parameterisation and show how it enables
us to use second order derivatives instead
of fourth and fifth. The idea of quasi-invariant
parameterisation is to approximate the group invariant
arc-length by lower order derivatives. The
new parameterisations are therefore less sensitive
to noise, and are approximately invariant under a
slightly restricted range of image distortions.
The concept of quasi-invariants was originally
proposed by Binford (Binford and Levitt, 1993),
who showed that quasi-invariants enable a reduction
in the number of corresponding points required
for computing algebraic invariants. For example
quasi-invariants require only four points for
computing planar projective invariants (Binford
and Levitt, 1993), while exact planar projective
invariants require five points (Mundy and Zisser-
man, 1992). It has also been shown that quasi-
invariants exist even under the situation where
the exact invariant does not exist (Binford and
Levitt, 1993). In spite of its potential, the quasi-invariant
has not previously been studied in de-
tail. One reason for this is that the concept of
quasiness is rather ambiguous and is difficult to
formalise. Furthermore, the existing method is
limited to the quasi-invariants based on point cor-
GA
GA
SA
Projective (8DOF)
Special
Affine
Similarity
(4DOF) (3DOF)
Euclidean
General Affine (6DOF)
(d)
(b)
(a) (c)
Fig. 1. Image distortion and transformation groups. A symmetric pair of contour curves (white curves) of (a) a surface
of revolution, (b) planar bilateral symmetry and (c) 3D bilateral symmetry can be described by Euclidean, special affine
(equi-affine) and general affine (proper affine) transformations under the weak perspective assumption. The image distortion
caused by the relative motion between the observer and the scene can also be described by group transformations as shown
in (d) and (e).
Quasi-Invariant Parameterisations 119
~
(a) (b)
Fig. 2. Identifying interval of integration semilocally. (a)
and (b) are images of a Japanese character extracted from
the first and the second viewpoints. The interval of integration
in these two images can be identified uniquely
from invariant arc-length, w. For example, if w1 and e
are a corresponding pair of points, then the interval [-1, 1]
with respect to w corresponds to the interval [-1, 1] with
respect to e w in the second image. Even though the curve
is occluded partially (second image), the semi-local integral
invariants can be defined on the remaining parts of
the curve.
respondences (Binford and Levitt, 1993), or the
quasi-invariants under specific models (Zerroug
and Nevatia, 1993; Zerroug and Nevatia, 1996).
In this paper, we investigate quasi-invariance on
smooth manifolds, and show that there exists a
quasi-invariant parameterisation, that is a parameterisation
approximately invariant under group
transformations. Although the approximated values
are no longer exact invariants, their changes
are negligible for a restricted range of transforma-
tions. Hence, the aim here is to find in parameterisations
the best tradeoff between the error caused
by the approximation and the error caused by image
noise.
Following the motivation, we investigate a measure
of invariance which describes the difference
from the exact invariant under group transforma-
tions. To formalise a measure of invariance in
differential formulae, we introduce the so called
prolongation (Olver, 1986) of vector fields. We
next define a quasi-invariant parameter as a function
which minimises the difference from the exact
invariant. A quasi invariant parameter under
general affine transformations is then proposed.
The proposed parameter is applied to semi-local
integral invariants and exploited successfully for
matching curves under general affine transformations
in real image sequences.
2. Semi-Local Integral Invariants
In this section, we review semi-local integral in-
variants, and motivate the new parameterisation,
quasi-invariant parameterisation.
If the invariants are too local such as differential
invariants (Cyganski et al., 1987; Weiss, 1988),
they suffer from noise. If the invariants are too
global such as moment (integral) invariants (Abu-
Mostafa and Psaltis, 1984; Hu, 1962; Lie, 1927;
Reiss, 1993; Taubin and Cooper, 1992), they suffer
from occlusion and the requirement of corre-
spondences. It has been shown recently (Sato and
Cipolla, 1996a; Sato and Cipolla, 1996b) that it is
possible to define integral invariants semi-locally,
so that they do not suffer from occlusion, image
noise and the requirement of correspondences.
Consider a curve, C 2 R 2 , to be parameterised
by t. It is also possible to parameterise the curve
by invariant parameters, w, under specific transformation
groups. These are called arc-length of
the group. The important property of group arc-length
in integral formulae is that it enables us
to identify the corresponding interval of integration
automatically. Consider a point, C(w 1 ), on
a curve C to be transformed to a point, e
on a curve e
C by a group transformation as shown
in Fig. 2. Since 1 e
it is clear that if we
take the same interval [01w; 1w] around C(w 1 )
and e
these two intervals correspond
to each other (see Fig. 2). That is, by integrating
with respect to the group arc-length, w, the
corresponding interval of integration of the original
and the transformed curves can be uniquely
identified.
We now define semi-local integral invariants at
point
Z w1+1w
w101w
Fdw (1)
where, F is any invariant function under the
group. The choice of F provides various kinds of
semi-local integral invariants (Sato and Cipolla,
1996b). If we choose the function F carefully,
the integral formula (1) can be solved analytically,
and the resulting invariants have simpler forms.
For example, in the affine case, if we substitute
then the integral formula is solved analytically,
120 Sato and Cipolla
and the integral invariants can be described by:
denotes the determinant of a
matrix which consists of two column vectors,
. The right hand side of (2) is
actually the area made by two vectors,
results have been proposed by Bruckstein (Bruck-
stein et al., 1993) by a different approach. The
important properties of semi-local integral invariants
are as follows:
1. The limits of integration [01w;1w] in semi-local
integral invariants are identified uniquely
in original and transformed images from invariant
parameterisations. Thus, we do not
need to worry about the correspondence problem
caused by a heuristic search of image features

2. Even though the curve is occluded partially as
shown in Fig 2 (b), the semi-local integral invariants
can be defined on the remaining parts
of the curve. Thus, they do not suffer from the
occlusion problem unlike classical moment invariants

3. In general, the lowest order differential invariant
of a transformation group is a group
curvature, and requires second, fourth, fifth
and seventh order derivatives in Euclidean,
special affine, general affine and projective
cases (Guggenheimer, 1977; Olver et al.,
1994). The semi-local integral invariants enable
us to reduce the order of derivatives required
from that of group curvatures to that of

Table

1. Order of derivatives required for the group arc-length
and curvature. In general derivatives more than the
second order are sensitive to noise, and are not available
from images. Thus, the general affine and projective arc-length
as well as curvatures are not practical.
group arc-length curvature
Euclidean 1st 2nd
special affine 2nd 4th
general affine 4th 5th
projective 5th 7th
group arc-length. Since as shown in table 1,
the order of derivatives of group arc-length
is lower than that of group curvature, the
semi-local integral invariants are more practical
than differential invariants.
From table 1 (Olver et al., 1994), it is clear that
the semi-local integral invariants are useful under
Euclidean and special affine cases, but they still
require high order derivatives in general affine and
projective cases. The distortion caused by a group
transformation is often not so large. For exam-
ple, the distortion caused by the relative motion
between the observer and the scene is restricted
because of the finite speed of the camera or object
motions. In such cases, parameters approximated
by lower order derivatives give us a good approximation
of the exact invariant parameterisation.
We call such a parameterisation a quasi-invariant
parameterisation.
In the following sections, we define the quasi-invariant
parameterisation, and derive an affine
quasi-invariant parameterisation.
3. Infinitesimal Quasi-Invariance
We first derive the concept of infinitesimal quasi-
invariance; that is quasi-invariance under infinitesimal
group transformations.
3.1. Vector Fields of the Group
Let G be a Lie group, that is a group which carries
the structure of a smooth manifold in such
a way that both the group operation (multiplica-
tion) and the inversion are smooth maps (Olver,
1986). Transformation groups such as rotation,
Euclidean, affine and projective groups are Lie
groups. Consider an image point x to be
transformed to an image point e
by a group
G:
so that a function, I(x; y), with respect to x and
y coordinates is transformed to ~
y) by h.
Infinitesimally we can interpret this phenomenon
by an action of a vector field, v:
@
@x
@
@y
Quasi-Invariant Parameterisations 121
~
~
G
Fig. 3. The vector field, v, and an integral curve, 0. The
curve C is transformed to e
C by a group transformation, so
that the point P on the curve is transformed to e
P. Locally
the orbit of the point caused by a group transformation
coincides with the integral curve, 0, of the vector field at
the point, P.
where,  and j are functions of x and y, and provide
various vector fields. Locally the orbit of the
point, x, caused by the transformation, h, is described
by an integral curve, 0, of the vector field,
v, passing through the point (see Fig. 3). v is
called an infinitesimal generator of the group ac-
tion. The uniqueness of an ordinary differential
equation guarantees the existence of such a unique
integral curve in the vector field.
Because of its linearity, any infinitesimal generator
can be described by the summation of a
finite number of independent vector fields, v i
m), of the group as follows:
is the ith independent vector field:
@
@x
@
@y
are basis coefficients of @
@x and @
@y
respectively, and are functions of x and y. These
independent vector fields form a finite dimensional
vector space called a Lie algebra (Olver, 1986).
Locally any transformation of the group can be
described by an integral of a finite number of independent
vector fields, v i . The vector field described
in (3) acts as a differential operator of the
Lie derivative.
3.2. Exact Invariance
We now state the condition of invariance of an
arbitrary function I, which is well known in Lie
Group theory.
Let v be an infinitesimal generator of the group
transformation. A real-valued function I is invariant
under group transformations, if and only
if the Lie derivative of I with respect to any infinitesimal
generator, v, of the group, G, vanishes
as follows (Olver, 1995):
where denotes the Lie derivatives with respect
to a vector field v. Since I is a scalar func-
tion, the Lie derivative is the same as the directional
derivative with respect to v. Thus, the condition
of invariance (6) can be rewritten as follows:
is the directional derivative with respect
to v.
3.3. Infinitesimal Quasi-Invariance
The idea of quasi-invariance is to approximate the
exact invariant by a certain function I(x; y), which
is not exactly invariant but nearly invariant. If the
I , is not exactly invariant the equation
no longer holds. We can however measure the
difference from the exact invariant by using (7).
By definition, the change in function I caused by
the infinitesimal group transformation induced by
a vector field, v, is described by the Lie derivative
of I as follows:
For measuring the invariance of a function irrespective
of the choice of basis vectors, we consider
an intrinsic vector field of the group, G. It
is known (Sattinger and Weaver, 1986) that if the
122 Sato and Cipolla
group is semi-simple (e.g. rotation group, special
linear group), there exists a non-degenerate symmetric
bilinear form called Killing form, K, of the
Lie algebra as follows:
where ad(v i ) denotes the adjoint representation 1
of v i , and tr denotes the trace. The Killing form
provides the metric tensor, for the algebra:
and the Casimir operator, C a , defined by the metric
tensor is independent of the choice of the basis
vectors:
ij is the inverse of g ij . That is, the met-
changes according to the choice of basis
vectors, v i , so that C a is an invariant. Since g ij is
symmetric, there exists a choice of basis vectors,
m), by which g ij is diagonalised as
follows:
ae 61 if
Such vector fields, v i are unique
in the group, G, and thus intrinsic. By using the
intrinsic vector fields in (8), we can measure the
change in value of a function, I , which is intrinsic
to the group, G.
For measuring the quasi invariance of a function
irrespective of the magnitude of the function, we
consider the change in function, ffiI , normalised by
the original function, I. We, thus, define a measure
of infinitesimal quasi invariance, Q, of a function
I by the squared sum of normalised changes
in function caused by the intrinsic vector fields,
I
This is a measure of how invariant the function, I,
is under the group transformation. If Q is small
enough, we call I a quasi-invariant under infinitesimal
group transformations.
Unfortunately, if the group is not semi-simple
(e.g. general affine group, general linear group),
the Killing form is degenerate and we do not have
such intrinsic vector fields. However, it is known
that a non-semi-simple group is decomposed into a
semi-simple group and a radical (Jacobson, 1962).
Thus, in such cases, we choose a set of vector fields
which correspond to the semi-simple group and
the radical.
4. Quasi-Invariance on Smooth Manifolds
In the last section, we introduced the concept
of infinitesimal quasi-invariance, which is the
quasi-invariance under infinitesimal group trans-
formations, and derived a measure for the invariance
of an approximated function. Unfortunately
(11) is valid only for functions which do
not include derivatives. In this section, we introduce
an important concept known as the prolongation
(Olver, 1986) of vector fields, and investigate
quasi-invariance on smooth manifolds, so that it
enables us to define quasi-invariants with a differential
formula.
4.1. Prolongation of Vector Fields
The prolongation is a method for investigating the
differential world from a geometric point of view.
Let a smooth curve C 2 R 2 be described by an
independent variable x and a dependent variable
y with a smooth function f as follows:
The curve, C, is transformed to e
C by a group
transformation, h, induced by a vector field, v, as
shown in Fig. 4. Consider a kth order prolonged
space, whose coordinates are x, y and derivatives
of y with respect to x up to kth order, so that
the prolonged space is dimensional. The
curves, C and e
C, in 2D space are prolonged and
described by space curves, C (k) and e
in the
dimensional prolonged space. The prolonged
vector field, v (k) , is a vector field in k
sion, which carries the prolonged curve, C (k) , to
the prolonged curve, e
explicitly as shown in
Fig. 4. More precisely, the kth order prolonga-
tion, v (k) , of a vector field, v, is defined so that
it transforms the kth order derivatives, y (k) , of a
into the corresponding kth order
derivatives, e
y (k) , of the transformed function
geometrically.
Quasi-Invariant Parameterisations 123
x
y
y
x
-0.4
x
y
x
y
y
x
-0.4
x
y
pr
prolonged space
~
pr
original image
prolonged space
transformed image
Fig. 4. Prolongation of a vector field. The kth order prolonged vector field, v (k) transforms kth order derivatives of y
into kth order derivatives of ey. That is the prolonged curve, C (k) , is transformed into the prolonged curve, e
by the
prolonged vector field, v (k) . This enables us to investigate derivatives of functions geometrically. pr (k) denotes kth order
prolongation. This figure illustrates the first order prolongation
m) be m independent vector
fields induced by a group transformation, h. Since
the prolongation is linear, the kth prolongation,
of a general vector field, v, can be described
by a sum of kth prolongations, v (k)
i , of the independent
vector fields, v i as follows:
Consider a vector field (5) in 2D space again. Its
first and second prolongations, v (1) , v (2) , are computed
as follows (Olver, 1986):
@y x
v (2)
@y xx
where D x and D 2
x denote the first and the second
total derivatives with respect to x, and y x , y xx ,
y xxx denote the first, second and the third derivatives
of y with respect to x. Let F (x;
function of x, y and derivatives of y with respect to
x up to kth order, which is denoted by y (k) . Since
the prolongation describes how the derivatives are
going to change under group transformations, we
can compute the change in function, ffiF , caused
by the group transformation, h, as follows:
where, v (k) is the kth order prolongation of the
infinitesimal generator, v, of a transformation h.
Note that we require only the same order of prolongation
as that of the function, F . Since the
prolongation describes how derivatives are going
to change, it is important for evaluating the quasi-
124 Sato and Cipolla
invariance of a differential formula as described in
the next section.
4.2. Quasi-Invariance on Smooth Manifolds
Let us consider the curve C in 2D space again.
Suppose I(y (n) ) is a function on the curve containing
the derivatives of y with respect to x up
to the nth order, which we denote by y (n) . Since
the nth order prolongation, v (n) , of the vector
field v transforms nth order derivatives, y (n) , of
the original curve to nth order derivatives, e y (n) ,
of the transformed curve, the change in function,
caused by the infinitesimal group transformation
induced by the ith independent vector
described by:
A quasi-invariant is a function whose variation
caused by group transformations is relatively
small compared with its original value. We thus
define a measure of invariance, Q, on smooth
curve, C, by the normalised squared sum of
integrated along the curve, C, as follows:
Z
If I(y (n) ) is close to the exact invariant, then Q
tends to zero. Thus, Q is a measure of how invariant
the function, I(y (n) ), is under the group
transformation.
5. Quasi-Invariant Parameterisation
In the last section, we have derived quasi-
invariance on smooth manifolds. We now apply
the results and investigate the quasi-invariance of
parameterisation under group transformations.
A group arc-length, w, of a curve, C, is in general
described by a group metric, g, and the independent
variable, x, of the curve as follows:
where, dw and dx are the differentials of w and x
respectively. Suppose the metric, g, is described
by the derivatives of y with respect to x up to kth
order as follows:
where y (k) denotes the kth order prolongation of y.
The change of the differential, ffidw i , caused by the
ith independent vector field, v i , is thus derived by
computing the Lie derivative of dw with respect
to the kth order prolongation of
dx
The change in dw normalised by dw itself is described
as follows:
ffid
dw
=g
dx
The measure of invariance of the parameter, w, is
thus described by integrating the squared sum of
ffid
along the curve, C, as follows:
Z
where,
dx
If the parameter is close to the exact invariant
parameter, Q tends to zero. Although there is no
exact invariant parameter unless it has enough orders
of derivatives, there still exists a parameter
which minimises Q and requires only lower order
derivatives. We call such a parameter a quasi-invariant
parameter of the group, if it minimises
(18) under the linear sum of the independent vector
fields of the group and keeps Q small enough
in a certain range of the group transformations.
To find a function, g, which minimises (18) is in
fact a variational problem (Gelfand and Formin,
1963) with the Lagrangian of L, which includes
one independent variable, x, and two dependent
variables, g and y (g is also dependent on y). In
the next section, we derive a metric, g, which minimises
the measure of invariance, Q, under general
affine transformations by solving the variational
problem.
Quasi-Invariant Parameterisations 125
6. Affine Quasi-Invariant Parameterisa-
tion
In this section, we apply quasi-invariance to derive
a quasi-invariant parameterisation under general
affine transformations which requires only second
order derivatives and is thus less sensitive to noise
than the exact invariant parameter which requires
fourth order derivatives.
Suppose the quasi-invariant parameterisation,
'  , under general affine transformation is of second
order, so that the metric, ' g, of the parameter,
, is made of derivatives up to the second:
where, y x and y xx are the first and the second
derivatives of y with respect to x. To find a
quasi-invariant parameter is thus the same as finding
a second order differential function, ' g(y x ; y xx ),
which minimises the quasi-invariance, Q, under
general affine transformations. Since the metric,
' g, is of second order, we require the second order
prolongation of the vector fields to compute the
quasi-invariance of the metric.
6.1. Prolongation of Affine Vector Fields
A two dimensional general affine transformation is
described by a 222 invertible matrix, A 2 GL(2),
and a translational component, t 2 R 2 , and transforms
e
Since the differential form, d' , in (20) does not
include x and y components, it is invariant under
translations. Thus, we here simply consider
the action of A 2 GL(2), which can be described
by four independent vector fields, v i
that is the divergence, curl, and the two
components of deformation (Cipolla and Blake,
1992; Kanatani, 1990; Koenderink and van Doorn,
@
@x
@
@y
@
@x
@
@y
@
@x
@
@y
@
@x
@
@y
Since the general linear group, GL(2), is not semi-
simple, the Killing form (9) is degenerate and
there is no unique choice of vector fields for the
group (see section 3.3). It is however decomposed
into the radical, which corresponds to the diver-
gence, and the special linear group, SL(2), which
is semi-simple and whose intrinsic vector fields coincide
with (21). Thus, we use
the vector fields in (21) for computing the quasi-
invariance of differential forms under general affine
transformations.
From (12), (13), and (21), the second prolongations
of these vector fields are computed by:
v (2)
@
@x
@
@y
@
@y xx
v (2)
@
@x
@
@y
@y x
@
@y xx
v (2)
@
@x
@
@y
@
@y x
@
@y xx
v (2)
@
@x
@y
@y x
03y x y xx
@
@y xx
These are the vector fields in four dimension,
whose coordinates are x, y, y x and y xx , and the
projection of these vector fields onto the x0y plane
coincides with the original affine vector fields in
two dimension. Since ' gdx is of second order, the
prolonged vector fields, v (2)
3 and v (2)
describe how the parameter, '  , is going to change
under general affine transformations.
6.2. Affine Quasi-Invariant Parameterisation
The measurement of the invariance, Q a , under a
general affine transformation is derived by substituting
the prolonged vector fields, v (2)
4 of (22) into (18):
Z
where, L is a function of y x , y xx , '
g and its derivatives
as follows:
v (2)
dx
126 Sato and Cipollayg
y
x
xx
x
*
y
Prolonged Space
Image
Fig. 5. Variation of ' g. The image curve C is transformed
to C (n) in the prolonged space. The curve '
varies only on
the surface 2 defined by C (n) . What we need to do is to
find a curve ' g 3 on 2 which minimises Qa . Thus, there is
no variation in yx and yxx .
where,  i denotes  of ith vector field, v i , and ' g yx
and ' g yxx are the first derivatives of ' g with respect
to y x and y xx respectively.
We now find a function, ' g, which minimises, Q a
of (23). The necessary condition of Q a to have a
minimum is that its first variation, ffiQ a vanishes:
This is a variational problem (Gelfand and
Olver, 1995) of one independent
variable, x, and two dependent variables, y and
' g, and the integrand, L, of (23) is called the Lagrangian
of the variational problem. It is known
that (25) holds if and only if its Euler-Lagrange
vanishes as follows (Olver, 1986):
denotes the Euler operator. Since, in
our case, one of the dependent variables, ' g, is a
function of the derivatives, y x , y xx , of the other
dependent variable, y, the Euler-Lagrange expression
is different from the standard form of one independent
and two dependent variables. We now
investigate how this variational problem can be
formalised.
Suppose ' g changes to ' g+1'g, so that '
to ' g yx + 1'g yx and ' g yxx changes to '
respectively, where 1'g yx and 1'g yxx denote derivatives
of 1'g with respect to y x and y xx . Then, the
first variation of the function, Q a , caused by the
change in '
g is described as follows:
Z
@'g
@'g yx
@'g yxx
1'g yxx
Note that the variation occurs only on the surface
2 as shown in Fig. 5, and therefore the variation,
ffiQ a does not include the change in y x and y xx .
As shown in Appendix A, assuming that ' g has
a form, y xx
(where ff and fi are real
values), we find that ffiQ a vanishes for any curve,
if the following function, ' g, is chosen:
We conclude that for any curve the following parameter
'  is quasi-invariant under general affine
transformations:
The quasi-invariance, Q a , of an example curve
computed by varying the power of y xx and (1+y 2
in (28) is shown in Fig. 6. We find that Q a takes
a minimum when we choose '  shown in (28). By
reformalising (28), we find that the parameter, '  ,
is described by the Euclidean arc-length, dv, and
the Euclidean curvature, , as follows:
Thus, d' , is in fact an exact invariant under ro-
tation, and quasi-invariant under divergence and
deformation. Note, it is known that the invariant
parameter under similarity transformations is dv
and that of special affine transformations is  1
The derived quasi-invariant parameter '  for general
affine transformations is between these two
as expected. We call '  the affine quasi-invariant
parameter (arc-length). Since the new parameter
requires only the second order derivatives, it is expected
to be less sensitive to noise than the exact
invariant parameter under general affine transformations

Quasi-Invariant Parameterisations 127
betaalpha
a
a
Fig. 6. Quasi-invariance of an artificial curve. The
quasi-invariance, Qa , of an example curve is computed
varying the power, ff and fl, in the parameter,
dx. As we can see, Qa takes a minimum
at This agrees with (28).
7. Quasi Affine Integral Invariants
In this section, we apply the extracted affine quasi-invariant
parameterisation to the semi-local integral
invariants described in section 2, and derive
quasi integral invariants under general affine
transformations.
defined in (29) is quasi-invariant, we
can derive quasi integral invariants under general
affine transformations by substituting '  in
into w in (1). If we substitute F ('
then we have
the following quasi semi-local integral invariant:
which is actually the area made by two vectors,
points C(' 1 +1') and C(' 1 01') are identified by
computing affine quasi-invariant arc-length,
R d' . (30) is a relative quasi-invariant of weight
one under general affine transformations as follows

e
can be computed from just second order
derivatives, the derived invariants are much less
sensitive to noise than differential invariants (i.e.
affine curvature). This is shown in the experiment
in section 9.2.
8. Validity of Quasi-Invariant Parameter-
isation
Up to now we have shown that there exists a quasi-invariant
parameter under general affine transfor-
mations, namely '  . In this section we investigate
the systematic error of the quasi-invariant
parameterisation, that is the difference from the
exact invariance, and show under how wide range
of transformations the quasi-parameterisation is
valid. As we have seen in (29), the new parameterisation
is an exact invariant under rotational
motion. We thus investigate the systematic error
90 oo
f
y
Fig. 7. Valid area of the affine quasi-invariant parame-
terisation. The tilt and the slant motion of a surface is
represented by a point on the sphere which is pointed by
the normal to the oriented disk. The motion allowed for
the affine quasi-invariant parameterisation is shown by the
shaded area on the sphere, which is approximately less than
in slant, and there is no preference in tilt angle.
128 Sato and Cipolla5030O
O
O
O
O
(a) original curve (b) distorted curves
Affine quasi-invariant arc-length
Invariants
O
O
(c) invariant signature
Fig. 8. Systematic error in invariant signatures. The original curve on a fronto-parallel planar surface shown in (a) is
distorted by the slant motion of the surface with tilt of 60 degrees (dashed lines) and slant of 30, 40, 50, and 60 degrees as
shown in (b). The distortions of the curve caused by this slant motion can be modeled by general affine transformations.
(c) shows invariant signatures made of quasi semi-local integral invariants (30) extracted from the curves in (b). If the slant
motion of the plane is 40 degrees or more, the invariant signature suffers from large systematic error, while if the slant is
less than 40 degrees, the proposed quasi-invariants are useful.
caused by the remaining components of the affine
transformation, that is the divergence and the deformation
components.
From (17), the systematic error of d' normalised
by d' itself is computed to the first order:
e =X
a i
v (2)
dx
where, a 1 , a 2 , a 3 and a 4 are the magnitude of di-
vergence, curl, and deformation vector fields. Substituting
(22) and (27) into (31), and since the curl
component of the vector field does not cause any
systematic error, we have:
x
2y x
x
Since both (10y 2
x
and 2yx
in (32) vary only
from 01 to 1, we have the following inequality:
Thus, if ja 1 j  0:1, ja 3 j  0:1 and ja 4 j  0:1, then
e  0:1, and the affine quasi-invariant parameterisation
is valid. Fig. 7 shows the valid area of
the affine quasi-invariant arc-length (parameteri-
represented by the tilt and slant angles
Quasi-Invariant Parameterisations 129
affine quasi-invariant arc-length
integral
invariants
(a) Integral invariants (std 0.1)
-0.020.020.06
affine arc-length
differential
invariants
(b) Differential invariants (std 0.1)
affine quasi-invariant arc-length
integral
invariants
(c) Integral invariants (std 0.5)
-0.020.020.06
affine arc-length
differential
invariants
(d) Differential invariants (std 0.5)
Fig. 9. Results of noise sensitivity analysis. The invariant signatures of an artificial curve are derived from the proposed
invariants (semi-local invariants based on affine quasi invariant parameterisation) and the affine differential invariants (affine
curvature), and are shown by thick lines in (a) and (b) respectively. The dots in (a) and (b) show signatures after adding
random Gaussian noise of std 0.1 pixels, and the dots in (c) and (d) show signatures after adding random Gaussian noise of
std 0.5 pixels. The thin lines show the uncertainty bounds of the signatures estimated by the linear perturbation method.
The signatures from the proposed method are much more stable than those of differential invariants.
which result in the systematic error, e, smaller
than 0:1. In Fig. 7, we find that if the slant motion
is smaller than 35 ffi , the systematic error is
approximately less than 0.1, and the affine quasi-invariant
parameterisation is valid.
9. Experiments
9.1. Systematic Error of Quasi Invariants
In this section, we present the results of systematic
error analysis of the quasi semi-local integral
invariants, that is the semi-local integral invariants
based on quasi-invariant parameterisation defined
in (30), and show how large distortion is allowed
for the quasi semi-local integral invariants.
Fig. 8 (a) shows an image of a fronto-parallel planar
surface with a curve. We slant the surface
with tilt angle of 60 degrees and slant angle of 30,
40, 50 and 60 degrees as shown in Fig. 8 (b), and
compute the invariant signatures of curves at each
slant angle. Fig. 8 (c) shows invariant signatures
of the curves computed from the quasi-invariant
arc-length and the semi-local integral invariant
(30). In this graph, we find that the invariant signature
is distorted more under large slant motion
as expected, and the proposed invariants are not
valid if the slant motion is more than 40 degrees.
Sato and Cipolla
(a) viewpoint 1 (b) viewpoint 2
Affine quasi-invariant arc-length
Invariants
(c) invariant signature from viewpoint 1
Affine quasi-invariant arc-length
Invariants
(d) invariant signature from viewpoint 2
Fig. 10. Curve matching experiment. Images of natural leaves from the first and the second viewpoint are shown in (a)
and (b). The white lines in these images show extracted contour curves. The quasi-invariant arc-length and semi-local
integral invariants are computed from the curves in (a) and (b), and shown in (c) and (d) respectively. In this example, we
chose It is clearly shown in these two signatures that the contour curve is partially occluded in (a).
9.2. Noise Sensitivity of Quasi Invariants
We next compare the noise sensitivity of the proposed
quasi semi-local integral invariants shown
in (30) and the traditional differential invariants,
i.e. affine curvature.
The invariant signatures of an artificial curve
have been computed from the proposed quasi-
invariants and the affine curvature, and are shown
by solid lines in Fig. 9 (a) and (b). The dots in (a)
and (b) show the invariant signatures after adding
random Gaussian noise of standard deviation of
pixels to the position data of the curve, and
the dots in (c) and (d) show those of standard deviation
of 0.5 pixels. As we can see in these signa-
tures, the proposed invariants are much less sensitive
to noise than the differential invariants. This
is simply because the proposed invariants require
only second order derivatives while differential in-
Quasi-Invariant Parameterisations 131
Affine quasi-invariant arc-length
Invariants
(a) invariant signatures
(b) matched curves (c) matched curves
Fig. 11. Results of curve matching experiment. The solid and dashed lines in (a) show the invariant signatures of the curves
shown in Fig. 10 (a) and (b), which are shifted horizontally minimising the total difference between the two signatures. (b)
and (c) show the corresponding curves extracted from the invariant signatures (a).
variants require fourth order derivatives. The thin
lines show the results of noise sensitivity analysis
derived by the linear perturbation method.
9.3. Curve Matching Experiments
Next we show preliminary results of curve matching
experiments under relative motion between
an observer and objects. The procedure of curve
matching is as follows:
1. Cubic B-spline curves are fitted (Cham
and Cipolla, 1996) to the Canny edge
data (Canny, 1986) of each curve. This allows
us to extract derivatives up to second order.
2. The quasi affine arc-length and the quasi
affine semi-local integral invariants (30) with
an arbitrary but constant 1' are computed
at all points along a curve, and subsequently
plotted as an invariant signature with quasi
affine arc-length along the horizontal axis and
the integral invariant along the vertical axis.
The derived curve on the graph is an invariant
signature up to a horizontal shift. We extract
the invariant signatures of both the original
and deformed curves.
3. To match curves we simply shift one invariant
signature horizontally minimising the total
difference between two signatures.
4. Corresponding points are derived by taking
identical points on these two signatures. Even
though a curve may be partially occluded
or partially asymmetric, the corresponding
points can be distinguished by the same procedure

Fig. 10 (a) and (b) show the images of natural
leaves taken from two different viewpoints. The
white lines in these images show example contour
132 Sato and Cipolla
Affine quasi-invariant arc-length
Invariants
(a)
Affine quasi-invariant arc-length
Invariants
Affine quasi-invariant arc-length
Invariants
(c)
Fig. 12. Comparison of signature. The invariant signatures in (a), (b) and (c) are computed from Fig. 10 (a) and (b) by
using three different 1' , i.e.
curves extracted from B-spline fitting. As we can
see in these curves, because of the viewer motion,
the curves are distorted and occluded partially.
Since the leaf is nearly flat and the extent of the
leaf is much less than the distance from the camera
to the leaf, we can assume that the corresponding
curves are related by a general affine transformation

The computed invariant signatures of the original
and the distorted curves are shown in Fig. 10
(c) and (d) respectively. One of these two signatures
was shifted horizontally minimising the total
difference between these two signatures (see
Fig. 11 (a)). The corresponding points on the
contour curves were extracted by taking identical
points in these two signatures, and are shown
in Fig. 11 (b) and (c). Note that the extracted
corresponding curves are fairly accurate. In this
experiment, we have chosen computing
invariant signatures. For readers' reference, we
in Fig. 12 compare the invariant signatures computed
from three different 1' .
9.4. Extracting Symmetry Axes
We next apply the quasi integral invariants for
extracting the symmetry axes of three dimensional
objects. Extracting symmetry (Brady and
Asada, 1984; Friedberg, 1986; Giblin and Bras-
sett, 1985; Gross and Boult, 1994; Van Gool et al.,
1995a) of objects in images is very important for
recognising objects (Mohan and Nevatia, 1992;
Gool et al., 1995b), focusing attention (Re-
isfeld et al., 1995) and controlling robots (Blake,
Quasi-Invariant Parameterisations 133
Rotation
l
~
~
(a) (b)
Fig. 13. Bilateral symmetry with rotation. The left and the right parts of an object with bilateral symmetry are rotated
with respect to the symmetry axis, L in (a). The intersection point, O1 , of two tangent lines, l 1 and e l 1 , at corresponding
points, P1 and e
P1 , of a bilateral symmetry with rotation lies on the symmetry axes, L in (b). If we have N cross points,
O the symmetry axis can be computed by fitting a line to these cross points, O1 , O2 , 1 1 1, ON .
1995) reliably. It is well known that the corresponding
contour curves of a planar bilateral symmetry
can be described by special affine transformations
(Kanade and Kender, 1983; Van Gool
et al., 1995a). In this section, we consider a class
of symmetry which is described by a general affine
transformation.
Consider a planar object to have bilateral symmetry
with an axis, L. Suppose the planar object
can be separated into two planes at the axis, L,
and is connected by a hinge so that two planes can
rotate around this axis, L, as shown in Fig. 13
(a). The objects derived by rotating these two
planes have a 3D bilateral symmetry. This class
of symmetry is also common in artificial and natural
objects such as butterflies and other flying in-
sects. Since the distortion in images caused by a
three dimensional motion of a planar object can be
described by a general affine transformation, this
class of symmetry can also be described by general
affine transformations under the weak perspective
assumption. Thus, the corresponding two curves
of this symmetry have the same invariant signatures
under general affine transformations. We
must note the following properties:
1. The skewed symmetry proposed by Kanade
(Kanade, 1981; Kanade and Kender, 1983) is
a special case of this class of symmetry, where
the rotational angle is equal to zero and the
distortion can be described by a special affine
transformation with determinant of 01.
2. Unlike the skewed symmetry of planar ob-
jects, 3D bilateral symmetry takes both negative
and positive determinant in its affine ma-
trix. The positive means that the two planes
are on the same side of projected symmetry
axis, and the negative means that the planes
are on opposite sides of the symmetry axis in
the image. The extracted invariant signatures
of corresponding curves of 3D bilateral symmetry
are therefore either the same (i.e. positive
determinant) or reflections of each other
(i.e. negative determinant).
3. Unlike the skewed symmetry of planar ob-
jects, the symmetry axis of 3D bilateral symmetry
is no longer on the bisecting line of
corresponding symmetric curves. Instead, the
cross points of the tangent lines at corresponding
points on the symmetric curves lie on the
symmetry axis as shown in Fig. 13 (b). Thus
the symmetry axis can be extracted by computing
a line which best fits to the intersection
points of corresponding tangent lines.
We next show the results of extracting symmetry
axes of 3D bilateral symmetry. Fig. 14
(a) shows an image of a butterfly (Small White)
with a flower. Since the two wings of the but-
134 Sato and Cipolla
(a) original image (b) contour curves
-20002000
Affine quasi-invariant arc-length
Invariants
(c) invariant signature of the left wing
-20002000
Affine quasi-invariant arc-length
Invariants
(d) invariant signature of the right wing
Fig. 14. Extraction of axis of bilateral symmetry with rotation. (a) shows the original image of a butterfly (Small White),
perched on a flower. (b) shows an example of contour curves extracted by fitting B-spline curves (Cham and Cipolla, 1996)
to the edge data (Canny, 1986). The invariant signatures of these curves are computed from the quasi-invariant arc-length
and semi-local integral invariants. (c) and (d) are the extracted signatures of the left and the right curves in (b). In this
example, we chose
terfly are not coplanar, the corresponding contour
curves of the two wings are related by a general
affine transformation as described above. Fig. 14
(b) shows example contour curves extracted from
(a). Note that not all the points on the curves
have correspondences because of the lack of edge
data and the presence of spurious edges. Fig. 14
(c) and (d) shows the invariant signatures computed
from the left and the right wings shown in
Fig. 14 (b) respectively. (In this example, we chose
computing semi-local integral invari-
ants.) Since the signatures are invariant up to a
shift, we have simply reflected and shifted one invariant
signature horizontally minimising the total
difference between two signatures (see Fig. 15 (a)).
As shown in these signatures, semi-local invariants
based on quasi-invariant parameterisation are
Quasi-Invariant Parameterisations 135
-20002000
Affine quasi-invariant arc-length
Invariants
(a) invariant signatures
(b) tangent lines (c) symmetry axis
Fig. 15. Results of extracting symmetry axis of 3D bilateral symmetry. The solid and dashed lines in (a) show the invariant
signatures of the curves shown in Fig. 14 (b), which are reflected and shifted horizontally minimising the total difference
between two signatures. The black lines in (b) connect pairs of corresponding points extracted from the invariant signatures
in (a). The white lines and the square dots show the tangent lines for the corresponding points and their cross points. The
white line in (c) shows the symmetry axis of the butterfly extracted by fitting a line to the cross points.
quite accurate and stable. Corresponding points
are derived by taking the identical points on these
two signatures, and shown in Fig. 15 (b) by connecting
the corresponding points. Tangent lines at
every corresponding pair of points are computed
and displayed in Fig. 15 (b) by white lines. The
cross points of every pair of tangent lines are extracted
and shown in Fig. 15 (b) by square dots.
The symmetry axis of the butterfly is extracted
by fitting a line to the cross points of tangent
lines and shown in Fig. 15 (c). Although the extracted
contour curves include asymmetric parts
as shown in Fig. 14 (b), the computed axis of
symmetry agrees with the body of the butterfly
quite well. Whereas purely global methods, e.g.
moment based methods (Friedberg, 1986; Gross
and Boult, 1994), would not work in such cases.
These results show the power and usefulness of the
proposed semi-local invariants and quasi-invariant
parameterisation.
10. Discussion
In this paper, we have shown that there exist
quasi-invariant parameterisations which are not
exactly invariant but approximately invariant under
group transformations and do not require high
order derivatives. The affine quasi-invariant parameterisation
is derived and applied for matching
of curves under the weak perspective assumption.
Although the range of transformations is lim-
ited, the proposed method is useful for many cases
especially for curve matching under relative motion
between a viewer and objects, since the movements
of a camera and objects are, in general,
136 Sato and Cipolla
limited. We now discuss the properties of the proposed
parameterisation.
1. Noise Sensitivity
Since quasi-invariant parameters enable us to
reduce the order of derivatives required, they
are much less sensitive to noise than exact
invariant parameters. Thus using the quasi-invariant
parameterisation is the same as finding
the best tradeoff between the systematic
error caused by the approximation and the error
caused by the noise. The derived parameters
are more feasible than traditional invariant
parameters.
2. Singularity
The general affine arc-length (Olver et al.,
1994) suffers from a singularity problem.
That is, the general affine arc-length goes to
infinity at inflection points of curves, while
the affine quasi-invariant parameterisation defined
in (29) does not. This allows the new parameterisation
to be more applicable in practice

3. Limitation of the Amount of Motion
As we have seen in section 8, the proposed
quasi-invariant parameter assumes the group
motion to be limited to a small amount. In the
affine case, this limitation is about a 1  0:1,
a 3  0:1 and a 4  0:1 for the divergence and
the deformation components (there is no limitation
on the curl component, a 2 ). Since, in
many computer vision applications, the distortion
of the image is small due to the limited
speed of the relative motion between a
camera and the scene or the finite distance
between two cameras in a stereo system, we
believe the proposed parameterisation can be
exploited in many applications.


Appendix

A
In this section, we derive the affine quasi-invariant
arc-length, '
. As we have seen in (26), ffiQ a is
described as follows:
Z
@'g
@'g yx
@'g yxx
1'g yxx
dx
By computing the Lie derivatives of ' g with respect
to v (2)
3 and v (2)
4 in (22), we have:
v (2)
@'g
@y xx
v (2)
@y x
@'g
@y xx
v (2)
@'g
@y x
@'g
@y xx
v (2)
@y x
@'g
@y xx
Note, that @'g
@x and @'g
@y components vanish. This is
because ' g does not include x and y components,
and by definition the prolonged vector fields act
only on the corresponding components given explicitly
(e.g. @
@x acts only on x component and
does not act on y, y x or other components). Substituting
into (24), we find that the La-
grangian, L, is computed from:
@y x
04'gy xx (2+3y 2
@y xx
@y xx
@y x
@y x
@'g
@y xx
Consider a derivative:
d
dy x
@'g yx
1'g dx
dy x
dy x
@'g yx
1'g dx
dy x
@'g yx
1'g yx
dx
dy x
@'g yx
dy 2
x
By integrating both sides of (A4) with respect to
dy x , the second term of (A1) can be described by:
Z
@'g yx
@L
@'g yx
1'g dx
dy x
aZ
d
dy x
@'g yx
Z
@'g yx
1'gd dx
dy x
Similarly the third term of (A1) can be described
by:
Z
@'g yxx
@L
@'g yxx
1'g dx
dy xx
aZ
d
dy xx
@'g yxx
Z
@'g yxx
1'gd dx
dy xx
Quasi-Invariant Parameterisations 137
Thus, the variation, ffiQ a , is computed from (A5)
and (A6) as follows:
Z
where,
@L
@'g yx
1'g dx
dy x
a
@L
@'g yxx
1'g dx
dy xx
a
@'gd
dy x
@'g yx@L
@'g yx
d
dx
dx
dy xd
dy xx
@'g yxx@L
@'g yxx
d
dx
dx
dy xx
where, a and b are the limit of integration specified
by the curve, C. From (A3), the derivatives of L
in (A8) and (A9) can be computed by:
@'g
@y x
@y xx
024y x y xx (1+y 2
@y x
@'g
@y xx
x )'g @'g
@y x
x )'g @'g
@y xx
@'g yx
@y xx
@y x
@'g yxx
@y xx
x )'g
@y x
Since 1'g in (A7) must be able to take any value,
ffiQ a vanishes if and only if:
The question is what sort of function, ' g, makes
the condition (A13) hold. Here, we assume that ' g
takes the following form:
and investigate the unknown parameters ff and fi
for (A13) to hold for arbitrary curves. Substituting
into (A10), (A11), and (A12), we have:
@'g
@'g yx
@'g yxx
Since y x and y xx in (A15), (A16) and (A17) take
arbitrary values, the condition (A13) holds for arbitrary
curves if:
Thus, ff and fi must be:
ff =5
Substituting (A19) and (A20) into (A14), we find
that the following form for ' g gives the extremal to
Acknowledgements

The authors acknowledge the support of the EP-
SRC, grant GR/K84202.
Notes
1. The adjoint representation, ad(v i ), provides a
matrix representation of the algebra, whose (j; component
is described by a structure constant C j
ik (Sat-
tinger and Weaver, 1986).



--R

Recognitive aspects of moment invariants.
General methods for determining projective invariants in imagery.

A symmetry theory of planar grasp.
Smoothed local symmetries and their implementation.

Invariant signatures for planar shape recognition under partial occlusion.
A computational approach to edge de- tection
Automated B-spline curve representation with MDL-based active contours

Surface orientation and time to contact from image divergence and deformation.
In Sandini
An affine transformation invariant curvature function.
Finding axes of skewed symme- try
Calculus of Variations.
Local symmetry of plane curves.
Analyzing skewed sym- metries
Differential Geometry.
Visual pattern recognition by moment in- variants
Lie algebras.
Recovery of the three-dimensional shape of an object from a single view
Mapping image properties into shape constraints: Skewed symme- try

Geometry of binocular vision and a model for stereopsis.
Gesammelte Abhandlungen
Perceptual organization for scene segmentation and description.
Pattern Analysis and Machine Intelligence

Foundations of semi-differential invariants
Geometric Invariance in Computer Vision.
Applications of Lie Groups to Differential Equations.

Differential invariant signatures and flows in computer vision.
Recognition of planar shapes under affine distortion.

Recognizing planar objects using invariant image features.

Planar object recognition using projective shape representation.
Affine integral invariants and matching of curves.
Affine integral invariants for extracting symmetry axes.
Lie groups and algebras with applications to physics
Object recognition based on moment (or algebraic) invariants.
The characterization and detection of skewed symmetry.


International Journal of Robotics Research

In
Projective invariants of shapes.

Geometric invariants and object recog- nition



Recognizing general curved objects efficiently.
--TR

--CTR
Tat-Jen Cham , Roberto Cipolla, Automated B-Spline Curve Representation Incorporating MDL and Error-Minimizing Control Point Insertion Strategies, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.1, p.49-53, January 1999
bilateral symmetry;integral invariants;semi-local invariants;differential invariants;curve matching;quasi-invariant parameterisations