Construction Computer Science
Resume:
International Journal of Computer Vision **(*), ** 86, 2004
c 2004 Kluwer Academic Publishers. Manufactured in The Netherlands.
Curve and Surface Duals and the Recognition of Curved 3D Objects
from their Silhouettes
AMIT SETHI, DAVID RENAUDIE, DAVID KRIEGMAN AND JEAN PONCE
Department of Computer Science and Beckman Institute, University of Illinois, Urbana, IL 61801, USA
******@****.***
*****.********@*******.****.**
********@**.****.***
*****@**.****.***
Received June 4, 2001; Revised September 3, 2003; Accepted September 3, 2003
Abstract. This article addresses the problem of recognizing a solid bounded by a smooth surface in a single
image. The proposed approach is based on a new representation for two- and three-dimensional shapes, called
their signature, that exploits the close relationship between the dual of a surface and the dual of its silhouette in
weak-perspective images. Objects are modeled by rotating them in front of a camera without any knowledge of
or constraints on their motion. The signatures of their silhouettes are concatenated into a single object signature.
To recognize an object from novel viewpoint other than those used during modeling, the signature of the contours
extracted from a test photograph is matched to the signatures of all modeled objects signatures. This approach has
been implemented, and recognition examples are presented.
Keywords: three-dimensional object recognition, invariants, duals, pedal curves
1. Introduction occluding contour on viewpoint makes the construc-
tion of appropriate feature correspondences dif cult.
Most approaches to model-based object recognition Appearance-based methods do not rely on such cor-
are based on establishing correspondences between respondences, and they are suitable for recognizing
viewpoint-independent image features and geometric objects bounded by smooth surfaces, but they gener-
features of object models (Huttenlocher and Ullman, ally require a dense sampling of the pose/illumination
1987; Lowe, 1987). For objects with smooth surfaces, space to be effective (Murase and Nayar, 1995). Meth-
few surface markings and little texture, the most reli- ods for relating image features to 3D geometric models
able image feature is the object s silhouette, i.e., the of curved surfaces have been developed for surfaces of
projection into the image of the curve, called the oc- revolution (Kriegman and Ponce, 1990b; Glachet et al.,
cluding contour, where the cone formed by the op- 1991), generalized cylinders (Ponce and Chelberg,
tical rays grazes the surface. The dependence of the 1987; Richetin et al., 1991; Liu et al., 1993; Zeroug
and Medioni, 1995), algebraic surfaces (Kriegman
and Ponce, 1990a; Ponce et al., 1992), and triangular
D. Renaudie is with the Ecole Nationale Sup rieure d Informatique
e splines (Sullivan and Ponce, 1998). These approaches
et Math matiques Appliqu es de Grenoble, France, and David
e e require separate processes for the construction of 3D
Kriegman is with the Department of Computer Science at the Uni-
models either from image data or using CAD tools, and
versity of California at San Diego. This work was done while they
for the extraction/segmentation of the image contours
were with the Department of Computer Science and the Beckman
associated with each object.
Institute at the University of Illinois at Urbana-Champaign.
74 Sethi et al.
Surface in E3 in E3 in Rd
Pedal Surface Signature
projects onto is a planar section of lies on
Silhouette in E2 Pedal Curve in E2 in Rd
Signature
Figure 1. Hierarchy of curve and surface representations and their embeddings.
An alternative is to replace a parametric description of the viewing conditions, and can thus be constructed
of the object surface by an empirical representation of without any knowledge of the camera motion; each ob-
contour features constructed from sampled image data. ject in the database is then represented by a different
We proposed in Joshi et al. (1997) and Vijayakumar signature. At recognition time, the signature of the sil-
et al. (1998) two variants of this approach where con- houette found in the test image is matched with the sig-
tour bitangents and in ections are recorded in an image natures of all modeled surfaces, and the closest model
sequence and serve as the basis for object recognition: is recognized. The hierarchy of curve and surface rep-
In Joshi et al. (1997), the trajectory of the camera is resentations used in this paper is illustrated in Fig. 1.
assumed to be known, and it is used to explicitly re- Its components are introduced in the next sections.
construct the surface curves giving rise to bitangents A preliminary version of this paper appeared in
and in ections during modeling. In turn, these curves Renaudie et al. (2000).
are used to predict the appearance of image features ob-
served at recognition time. In Vijayakumar et al. (1998)
on the other hand, the contour tangents parallel to each
2. Duals and Pedal Curves and Surfaces
bitangent and in ection serve as image features, and
the successive distances between these parallel lines
Let us consider a smooth C 2 closed curve in E2 . We
are used as the basis for classi cation. The features
de ne the dual D of as the set of its tangent lines.
recorded during a modeling session trace a curve in
The dual also forms a closed curve in the projective
the feature space that is independent of the camera
plane formed by all lines of E2 . It will prove convenient
trajectory. At recognition time, the bitangents, in ec-
to represent the dual by yet another planar curve, the
tions, and the corresponding parallel tangents present in
pedal curve introduced by Maclaurin in 1718 (Bruce
the test image are matched to the closest model curve
and Giblin, 1992; Maclaurin, 1718; Lockwood, 1967).
in the feature space. Here we propose to replace the
Like the original curve, the pedal curve lives
sparse set of silhouette features used in that method
in E2, but unlike the dual, its de nition depends on the
with a much denser set offering greater discriminatory
choice of some origin O in the plane. Figure 2 illus-
power. Our work builds on geometric insights about
trates its construction: We associate with each point P
the occluding contour and silhouettes of smooth sur-
on the orthogonal projection P of O onto the tangent
faces (Koenderink, 1984; Giblin and Weiss, 1995) and
line T in P ; the pedal curve is the curve traced by
their use in determining geometric structure from se-
P as P varies along . If N denotes the unit normal to
quences of images (Arbogast and Mohr, 1991; Cipolla
in P, the corresponding point P on the pedal curve
and Blake, 1992; Vaillant and Faugeras, 1992; Boyer
can also be de ned by
and Berger, 1997; Cipolla et al., 1995). See Cipolla and
Giblin (2000) for an overview of this line of research.
The basic processing steps for each image include
OP = (OP N ) N . (1)
detecting the silhouette curve, computing its pedal
curve (a representation of its dual), and construct-
ing its signature, a family of curves embedded in
Rd, where d 2 depends on the geometric complexity
of the observed object. The signature only depends on
the projection direction and is unaffected by changes
in the other viewing parameters. When a solid with a
smooth surface is observed by a moving camera, the
signatures of the successive silhouettes sweep a fam-
of two-dimensional surface patches in Rd, also
ily
called the signature of . This surface is independent Figure 2. Construction of the pedal curve.
Curve and Surface Duals 75
The pedal curve can be thought of as the image of the in this paper. In general, a line passing through the ori-
dual in E2, that associates with each tangent line T to gin will intersect the pedal curve in an even number of
the orthogonal projection P of O onto this line. The points: For example, the line passing through G and
mapping from the dual curve to pedal curve is not in- H in Fig. 3 only intersects at these two points; lines
jective in general: Indeed, any tangent passing through passing through the counterclockwise angular sector
the origin O maps onto this point. Although there is no de ned by OB and OA, on the other hand, will inter-
such tangent for the curve and origin shown in Fig. 2, sect four times. For a rotating line passing through
tangents passing through the origin are guaranteed to O, the number of intersection points can only change
at cusps and double points,1 where the number of in-
exist when the origin lies outside the curve, and may
exist even when this is not the case (see Fig. 7 for an tersections is (exceptionally) odd: For example the line
example). To simplify the discussion, we will assume passing through O and B also intersects in I and
F, and the line passing through O and A = D also
in most of this paper that the pedal curve does not pass
through the origin, and identify it with the dual. We will intersects in E and J .
come back to the general case during the presentation As noted earlier, the pedal curve associated with a
of our implementation. planar curve depends on the choice of origin. However,
As shown for example in Bruce and Giblin (1992, Properties (A) to (D) are independent of this choice,
p. 166), the pedal curve associated with has the and they will be used in Section 4.1 to map the pedal
following properties: curve onto another curve which is invariant under rigid
transformations of the plane.
(A) It is smooth at all points whose preimages on The de nitions of the dual and pedal curves general-
are not in ections. ize naturally to three dimensions (Bruce and Giblin,
(B) The in ections of (the points B and C in Fig. 2) in E3 ; the
1992): Consider a smooth C 2 surface
map onto cusps of ( B and C in this case). dual of is de ned as the set of its tangent planes,
(C) The lines bitangent to (like the line L that passes and it forms a two-dimensional surface in the three-
through the points A and D in Fig. 2) map onto dimensional space of all planes. To represent the dual
double points of (the point A = D in this case). in a convenient manner, we choose an origin O in E3
(D) The points of whose tangents are parallel to each and associate with every point P on the orthogonal
other map onto the intersections of the pedal curve projection P of O onto its tangent plane. The surface
with a line through the origin whose direction is swept by P as P varies over is the pedal surface
orthogonal to the common tangent direction (con- associated with this surface. As in the two-dimensional
sider for example the two points G and H and their case, the pedal surface is an image of the dual in E3
images G and H in Fig. 3). Conversely, the in- that depends on the choice of origin. And like pedal
tersection points of with a line passing through curves, the pedal surface may contain singularities, in-
the origin are the images of points with parallel cluding swallowtails and cuspidal edges corresponding
tangents on . to parabolic lines of (Bruce and Giblin, 1992).
Property (D) will in fact be the basis for the ap-
proach to object modeling and recognition presented 3. Occluding Contours and their Projections
The brightness discontinuities in the image of an un-
textured solid bounded by a smooth surface form a
curve, called the image contour, silhouette or outline.
Under perspective projection, this curve is the inter-
section of the image plane with a viewing cone whose
apex coincides with the center of projection and whose
generators graze the object along a second (generically
Figure 3. The intersections between various lines passing through
the origin and the pedal curve are the images of point sets with nonplanar) curve, called the occluding contour or rim,
parallel tangents. The number of intersections is normally even (e.g., and the tangent plane at an occluding contour point
two intersections for the line joining G and H ) but is odd at cusps
projects onto the tangent line at the corresponding sil-
and double points, corresponding to in ections and bitangents of the
houette point (Fig. 4(a)).2 Under orthographic projec-
original curve. Lines intersecting in four points are not shown
tion, the center of projection is at in nity, the viewing
here to avoid clutter.
76 Sethi et al.
gin, we then introduce a novel representation for these
objects, called their signatures, that can be used to re-
late the geometry of a surface and its projections but is
independent of any choice of origin.
Let us consider a regular surface, an origin O,
and the corresponding pedal surface . Given some
viewing direction v, we denote by v the plane per-
pendicular to v passing through O and de ne as the
silhouette of formed under orthographic projection
onto some image plane parallel to v . Let o denote
the image of O, and denote the pedal curve of
Figure 4. Occluding boundaries under (a) perspective and (b)
de ned using o as the origin of the plane v . We have
orthographic projection.
the following result.
Lemma 1. Under orthographic (resp. weak-
cone becomes a cylinder whose generators are parallel
perspective) projection, the pedal curve can be
to the ( xed) viewing direction, and the normal to the
mapped onto the intersection of the pedal surface
image contour is the same as the surface normal at the
with the plane v via a translation (resp. a translation
corresponding occluding contour point (Fig. 4(b)).
followed by a scaling).
Under orthographic projection, the imaging process
is simply modeled as an orthogonal projection onto
v . Since Q be-
Proof: Consider a point Q in
the image plane. This is a reasonable approximation
longs to, there exists (at least) one point P on the
of perspective projection for distant objects lying at a
surface such that OQ = [OP N ( P )] N ( P ). Since
roughly constant distance from the cameras observing
Q also belongs to v, OQ is orthogonal to v and, as-
them. The weak-perspective (or scaled-orthography)
suming as usual that the pedal surface does not pass
projection model generalizes the orthographic one to
through the origin, N ( P ) must also be orthogonal to
allow for variations in the depth of an object relative
v . In other words, the point P belongs to the occluding
to the camera observing it. The projection geometry is
contour associated with the projection direction v .
the same as in the orthographic case, and the silhouette
Now, let o and p denote respectively the ortho-
and occluding contour have the same properties, but the
graphic projections of the points O and P onto some
distance between any pair of image points is a constant
image plane parallel to v . We pick o as the origin for
multiple (or magni cation) of the distance obtained
that plane and denote respectively by and the sil-
under orthographic projection. We will assume either
houette of and the corresponding pedal curve. The
orthographic or weak-perspective projection in the rest
surface at P and the silhouette at p have the same
of this paper.
normal, and it follows that p maps onto the point q of
Most real objects are opaque of course, but we will
de ned by
assume in most of the rest of this paper that all objects
are translucent. This is just to simplify the upcoming
discussion, since in this case a necessary and suf cient
oq = [op N ( P )] N ( P ) = [(oO + OP + P p ) N ( P )]
condition for a point to project onto the silhouette is
= [OP N ( P )] = OQ,
that the viewing direction belongs to its tangent plane.
The approach proposed in this paper is not limited in
since the projection vectors Oo and P p are by de ni-
any sense to transparent objects, and we will come back
tion parallel to v . It follows that Qq = Oo, and that the
to the case of opaque objects when we discuss our im-
v and are separated by the trans-
two curves
plementation.
lation Oo. The weak-perspective case is similar but
involves the scaling inherent in this projection model.
4. The Signatures of Curves and Surfaces
We begin by clarifying the relation between pedal sur- Lemma 1 identi es planar slices of the pedal sur-
faces and the pedal curves of image silhouettes. Since face with the pedal curves of the image contour in
these curves and surfaces depend on a choice of ori- a coordinate-free manner. Exploiting this lemma in
Curve and Surface Duals 77
recognition tasks requires (1) identifying the projection
3 2 1
o of the point O in every image, and (2) handling the fact 4 4
that the corresponding measurements necessarily de-
2 2
pend on the choice of a world coordinate system and ap-
O
propriate image coordinate frames. The latter problem
is not dif cult when the former one is solved: Indeed, it
44
follows immediately from Lemma 1 that the measured 4 6
5
(and therefore coordinate-dependent) descriptions of
the pedal curve and the corresponding planar slice of Figure 5. The partition of a pedal curve: A rotating line pass-
ing through O intersects the pedal curve in two points when
the pedal surface are related by a rigid transformation
is in the open range ( 3, 4 ) or ( 6, 1 ), and it intersects in
in the orthographic case, and by a similarity transfor-
four points when is in one of the open intervals ( 1, 2 ), ( 2, 3 ),
mation in the weak-perspective one. We concentrate ( 4, 5 ) and ( 5, 6 ). Hence, the partition for this pedal curve is
on the orthographic projection setting here (the weak- {( 1, 2, 4), ( 2, 3, 4), ( 3, 4, 2), ( 4, 5, 4), ( 5, 6, 4), ( 6, 1, 2)}.
perspective case easily follows), assuming that both the
camera motion and the position of o in the image plane
Pick some arbitrary direction in the plane as the hor-
are known. In this case, the pedal curve of the silhou-
izontal direction with orientation = 0, and consider
ette is easily constructed, and the viewing direction v is
the family of oriented lines with orientation pass-
used to determine the sectioning plane v ; the position
ing through the origin O associated with . As noted
of o is then used to determine the translation compo-
earlier, the number of intersections of and only
nent of the rigid transformation within v, while the
changes at cusps and double points of this curve. Let i
camera motion is used to determine the rotation an-
(i = 1, . . ., p ) denote the corresponding orientations
gle. If the set of viewing directions covers, say, half a
of . The partition of is de ned as the set of
great circle of the unit sphere, every point on the sur-
triplets ( i, i +1, n i ) (i = 1, . . ., p ), where the num-
face will lie on the occluding contour for some viewing
ber of intersections of and is equal to n i for any
direction (barring self occlusion), and the entire pedal
( i, i +1 ), and index addition is performed modulo
surface will be revealed. The object may then be recog-
p so p + 1 1.
nized from any view, including ones never seen before,
We now de ne the signature of the curve . We
by matching the corresponding pedal curve to a planar
consider again an oriented line passing through the
section passing through the origin of the pedal surface.
origin with orientation ( i, i +1 ), and denote by
Note that, for some camera motions, parts of the pedal
AB the signed distance between two points A and B
surface may be missed or in fact be covered multiple
on . The sign is determined by the orientation of
times, and the object may only be recognizable from a
the line . Let us denote by Pk (k = 1, . . ., n i ) the
subset of all possible views in this case.
intersections of with, sorted in increasing O P k
order, and de ne dk = Pk P k +1 (k = 1, . . ., n i 1).
We de ne i as the curve traced in Rni 1 by the points
4.1. The Signatures of Curves and Surfaces
(d1, . . ., dni 1 )T as varies over ( i, i +1 ) and de ne
and their Properties
the signature of the curve as the unordered set
{ 1, . . ., p } (Fig. 6).
The approach to object recognition sketched in the pre-
Note that the scalars dk associated with some orien-
vious section requires that the projection of the origin
tation are simply the (signed) distances between the
be identi ed during both modeling and recognition, and
tangent lines to that are parallel to each other and
that the viewing direction be known during modeling.
perpendicular to . We then have:
We do not know of any geometric property of arbitrary
smooth surfaces that would allow this to be determined
from a silhouette. Instead, we now de ne a new repre- Lemma 2. The signature of a curve is indepen-
sentation for curves and surfaces that is independent of dent of the choice of the origin used to de ne its pedal
curve, and it is invariant under rigid transforma-
the choice of the origin (and in fact of arbitrary rigid
transformations) and whose construction does not re- tions of the plane.
quire knowing the camera motion during modeling.
We rst use the pedal curve as a device for con- Proof: As noted earlier, the scalars dk associated with
some orientation are the signed distances between the
structing the partition of the associated curve (Fig. 5):
78 Sethi et al.
shape of the dual of a curve and therefore the shape of
the curve itself, but depend on the choice of the origin,
signatures omit some of the shape information (namely
the orientation of the parallel tangents and their position
relative to a xed point), but gain a complete indepen-
dence on any choice of origin. In this context, the pedal
curve is simply a convenient bookkeeping device for
constructing the signature.
It is also possible to de ne the signature of a sur-
face as a set { 1, . . ., q } of two-dimensional surface
patches j embedded in Rn j 1 for j = 1, . . ., q, each
patch being swept by the signed distances between par-
allel tangent planes as their surface normal varies. Like
the signature of a curve, the signature of a surface is
independent of the choice of the origin O and is invari-
ant under rigid transformations. Another fundamental
result follows from Lemmas 1 and 2, namely:
Proposition 1. Under orthographic projection, the
curve segments forming the signature of the silhouette
of a surface lie on the surface patches forming the
signature of .
Proof: Under orthographic projection, two silhou-
ette points with parallel tangent lines are the projection
of surface points with parallel tangent planes de ned
by the tangent directions and the projection direction.
The distance between these planes is the same as the
distance between the lines, and it follows that the
Figure 6. The scalars d1, d2, and d3 de ning a point on the signa-
silhouette s signature point (d1, . . ., dn 1 ) associated
ture are de ned using distances between (a) parallel tangents on the
original closed curve, or equivalently (b) intersections P1, . . ., P4 with some orientation in the image plane belongs to
of a rotating line passing through the origin (dashed) with the the signature of the surface. The proposition follows
associated pedal curve.
immediately.
In particular, a subset of the signature of a surface
tangent lines to that are parallel to each other with
can be constructed from a set of training images without
orientation /2. In particular, they are independent
any knowledge of the corresponding camera con gu-
of the choice of the origin used to de ne . Unlike the
rations. As shown in the next section, this subset can be
partition, the signature does not depend on the choice
thought of as a model of the corresponding surface, and
of horizontal direction either, since changing this direc-
object recognition can be formulated as the problem of
tion amounts to applying a circular permutation to the
deciding what surface model contains (in practice, lies
partition and the set of curves i, but does not affect
close to) the signature of some test silhouette.
the signature as an unordered set of curve segments.
The model of a surface will consist of the whole sig-
Finally, since rigid transformations of the plane pre-
nature for suf ciently rich set of input pictures,
serve the parallelism of lines and the distance between
e.g., when the viewing directions associated with a
parallel lines, the signature is also invariant under rigid
moving camera cover a half great circle of the unit
transformations.
sphere. A better understanding of the situation can be
Lemma 2 states the fundamental property of signa- gained by considering the close relation between the
tures, and it is the key to their usefulness in recognition Gaussian image of a surface and its dual. In particular,
for a given viewing direction v, the Gaussian image
tasks: Unlike pedal curves, that completely capture the
Curve and Surface Duals 79
of the occluding contour of a surface is the great cir- ture is easily shown to be invariant under af ne trans-
cle formed by the intersection of the surface s Gaus- formations of the curve . Over a sequence of im-
sian image with the plane orthogonal to v and passing ages, the quotient signatures of successive silhouettes
through the origin. For a moving camera, the great cir- sweeps out the quotient signature of the corresponding
cles associated with the successive viewing directions surface .
cover a subset of the Gauss sphere. If the camera tra-
jectory is suf ciently rich to guarantee full coverage of
5. Object Modeling and Recognition:
the entire Gauss sphere, every point on the surface will
Implementation and Results
have been observed (up to occlusion) for some view-
ing direction, and the successive silhouette signatures
As suggested in the previous section, the signatures
will completely sweep out the entire signature of the
of surfaces and their silhouettes can be used as
surface.
the basis for object modeling from image sequences
It should also be noted that the dimension of the
and object recognition in a single image. We dis-
space in which a patch i of the signature is em-
cuss below an implemented approach to these two
bedded depends on the number of intersections of a
problems. It is very important to note that the exper-
line with the pedal surface . If the number of
imental results presented in this section are not in-
intersections is 2, then i is embedded in R1 (i.e.,
tended as a de nitive characterization of the capabil-
it is simply an interval of R) and is unlikely to offer
ities and limitations of signatures as a representation
much discriminatory power for recognition. In prac-
for recognition: They merely demonstrate that signa-
tice, we only retain those components of the signature
tures are indeed easy to compute from real images
surface for which intersects at least four times in
and can support the recognition of objects with com-
which case these patches are embedded in Rn where
plex shapes. Our results also demonstrate that curved
n 3. Also note that our discussion has assumed that
3D objects can be modeled from 2D images with un-
the silhouette is a regular curve. In general, the image
known camera motions and recognized from novel
contour of a smooth surface may in fact be singular
viewpoints.
and contain cusps and crossings (Koenderink and Van
Doorn, 1976). For a moving camera, the trajectory of
the viewing direction may cross a visual event bound- 5.1. Object Modeling
ary for which other singularities are observed (i.e., tan-
gent crossings, triple points, cusp crossings, swallow- The Canny edge detector is used to obtain object bound-
tails, lips, and beaks) (Kergosien, 1981; Koenderink aries as linked, closed curves. To prevent the program
and Van Doorn, 1976). These have been studied exten- from getting confused by the internal edges while ex-
sively, particularly within the context of aspect graph tracting the silhouette, some of the internal edges are
construction. Since these singularities are not detected removed by hand. The normal vector at each point of
in our implementation, we leave a more complete char- is then computed using linear least squares, and the
acterization of their corresponding pedal curves and pedal curve is nally computed in a straightforward
signatures for future research. manner (Fig. 7(a) and (b)). The origin O in the pedal
Under weak perspective, the image magni cation is curve computation is (arbitrarily) taken to be the center
an unknown additional parameter that may vary with of mass of the edge points.
each image (i.e., it may change over the camera tra- As shown in Fig. 7(b), the pedal curve construc-
jectory used to model an object when the distance tion process ampli es the noise in the detected edge
from the camera to the object varies). We can elim- point position. Consequently, we smooth the silhouette
inate the dependency of the signature on magni ca- using active contours before constructing . The ac-
tion by normalizing the distances dk by the largest tive contour is initialized with the points obtained from
one (which is by construction dni 1 ). This yields the the Canny edge detector, and the results are shown in
quotient signature = ( 1, . . ., p ), where i is the Fig. 7(c) and (d).
curve formed in Rni 2 by the points (d 1, . . ., d ni 2 )T =
The signature associated with the curve is also
dni 2 T
( dn 1, . . ., dn 1 ), as the point (d1, . . ., dni 1 )T varies
d1
computed in a straightforward manner: The range of
i i
orientations between 0 and is sampled uniformly to
over the corresponding component i of the signa-
give a set of oriented lines { i } passing through the
ture as described in Section 4.1. The quotient signa-
80 Sethi et al.
houette in Fig. 7, and the corresponding quotient
signature.
Note that the orientation of the sample lines in the
[0, ] interval intersecting the pedal curve and de n-
ing the signature was chosen arbitrarily. Reversing this
orientation gives a second valid point on the signature
for each line. As shown in the next section, rather than
explicitly storing these extra points, we take them into
account in the matching phase of our approach.
Signature and quotient surfaces can be constructed
by concatenating together the signature and quotient
curves found in successive images. Since the silhou-
ettes of a solid observed from opposite directions are
Figure 7. Pedal curve construction: (a) the raw silhouette of a tele- the same under orthographic projection, we only sam-
phone handset and (b) its pedal curve; (c) smoothed silhouette and (d)
ple an 180 interval of viewing directions. Figure 9
the corresponding pedal curve and the directions giving the partition.
shows ten images of a 40-image sequence (4.5 sam-
pling) taken as a telephone handset (from here on,
phone) rotates about a xed axis. Obviously, the al-
origin. Every line i is intersected with the pedal curve,
at points Pk . The intersections Pk (k = 1, . . ., n i ) are gorithm for constructing the signature knows nothing
about the trajectory. Figure 10 shows the signature
now sorted based on their signed distance xk from the
of its surface.
origin (where the sign is given by the orientation of
i ). The smallest distance x 1 is subtracted from all
the signed distances of the intersections of a line from 5.2. Object Recognition
the origin to give a point (d1, . . ., dni 1 )T = (x2
x1, . . ., xni x1 )T, which forms one point of the signa- We have constructed a simple recognition system.
ture . The quotient signature is computed by dividing Figure 11 shows images of six objects, modeled us-
all coordinates of each point on the signature by the ing the technique proposed in the previous section: a
d
last one, i.e., (d 1, . . ., d ni 2 )T = ( dnd1 1, . . ., dni 2 )T .
camel, a dolphin, a duck, the phone, a pig, a stuffed toy
n i 1
i
Since the components of (x1, . . ., xni )T are sorted in (from here on, toy). Recall that objects are modeled
by rotating them about a xed axis over 180 . Ten test
increasing order, the components of (d1, . . ., dni 1 )T,
and (d 1, . . ., d ni 2 )T are also sorted. Figure 8 shows
images of each object were also acquired from novel
an example signature projected to R3 for the sil- viewing directions, and Fig. 12 shows some examples.
Figure 8. (a) The signature curve projected to R3 computed from the smoothed silhouette of the telephone handset shown in Fig. 7 and (b) the
corresponding quotient signature curve.
Curve and Surface Duals 81
Figure 9. Images of a telephone handset used to construct the signature surface. The images were acquired by rotating the phone by 180
degrees about the vertical axis.
Figure 10. (a) A single patch of the surface signature projected to R3 associated with the phone shown in Fig. 7; one of the curve components
shown in Fig. 8 was used to construct this patch and (b) the full surface signature of the phone projected to R3 .
Figure 11. Six objects used in the recognition experiments. The objects are resting on a platform and were rotated about an axis which was
approximately parallel to the vertical axis of the image plane.
The principle of the recognition method is straight- surface signatures. In practice, some care must be
forward. Each modeled object is represented by its sig- given to the construction of indexing schemes adapted
nature. The signature of the silhouette extracted from to the signature representation: Recall that a silhou-
a test image is computed and matched to the stored ette signature is actually a collection of curves i
82 Sethi et al.
Figure 12. Sample test images for each of the objects. Note that the viewing direction is different than any of those used during modeling.
embedded in Rni 1 (i = 1, . . ., p ), while a surface the robust matching techniques presented in Torr and
Zisserman (2000) and Forsyth and Ponce (2002) for
signature is a collection of patches j embedded in
Rn j 1 ( j = 1, . . ., q ). If there were no occlusion due example. We assume that the distance between two
correctly matching coordinates xi and x j is normally
to opacity or other objects, we would only need to com-
distributed with variance, and that the distribution of
pare each point p in i to the components of j for
which n i = n j . But because of occlusion and clutter distances for all other (incorrect) matches is uniform.
The maximum-likelihood match between X and Y is
during modeling and recognition, only a subset of the
determined by taking the log likelihood and assum-
features (coordinates) on i will match those on j .
ing independence. In turn, the distance between xi and
The above reasons have prompted us to implement
y j is computed as the Lorentzian of their differences
the following modeling and matching strategy: All
di j = xi y j, or
images whether acquired for modeling or as a test
image undergo the same feature extraction process. di2j 2
l (di j ) = 1 = . (2)
The silhouette from the image is detected, and its pedal
+ 2 + 2
di2j di2j
curve is computed. The 180 range of orientations of
the lines passing through the pedal curve s origin is Note that a perfect match gives a Lorentzian of 1,
sampled at 3 intervals, and a direction is chosen arbi- whereas a large mismatch gives a Lorentzian approach-
ing 0. For all i, j, we can de ne an m by n matrix
trarily for each line. The signed distances of the inter-
sections of each line with the pedal are sorted, offset and whose entries are di, j, and the best match between X
normalized as described in Section 5.1 to yield a point and Y is taken as the path (non-decreasing function
of the quotient signature. Thus, we obtain 60 sample j (i )) that maximizes the sum of the Lorentzians. This
points of the quotient signature curve from an image. optimal path can be found ef ciently using dynamic
In the experiments, an object is modeled from 40 im- programming. For voting, the sum of the Lorentzians
ages taken by rotating the object in 4.5 increments is normalized by dividing by max(m, n ).
about a xed axis. Thus, the signature surface of an Note that this simple scheme allows for the occlu-
object given by a collection of 40 60 sample points. sion of some of the internal parallel tangents but re-
Similarly, the test image is represented by 60 sample quires that both extremal tangents be visible. This has
points of the quotient signature curve extracted from proven suf cient in the experiments presented in the
a silhouette. For each sample point on a detected quo- next section, where few of the extremal tangents are
tient signature curve in a test image, the sample point ever occluded.
on the closest quotient signature surface is determined When de ning the signature, the orientation of
according to the distance criterion described below, and the line intersecting the pedal curve was chosen ar-
a vote is cast for the corresponding model. bitrarily. As noted earlier, for each sample point
X = (x1, . . ., xn )T on the signature or quotient signa-
To determine the distance between two signature
points X = (x1, . . ., xi, . . ., xn )T and Y = ( y1, . . ., ture, a second valid point X
Contact this candidate