\documentstyle[12pt]{article}
\input{/homes/orasis/map/sven/conferences/iccv93/ymath}
\input epsf
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{7.0in}
\setlength{\evensidemargin}{-.25in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\topmargin}{-0.125in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\pagestyle{plain}
\title{Integrating Qualitative and Quantitative Shape Recovery}
\author{{\bf Sven J. Dickinson}\\
Department of Computer Science \\
University of Toronto \\
Toronto, Ontario, Canada M5S 1A4
\and
{\bf Dimitri Metaxas}\\
Department of Computer and Information Science\\
University of Pennsylvania\\
Philadelphia, PA 19104-6389}
\date{}
\begin{document}
\maketitle

\begin{abstract}
Recent work in qualitative shape recovery and object recognition has
focused on solving the ``what is it'' problem, while avoiding the
``where is it'' problem. In contrast, typical CAD-based recognition
systems have focused on the ``where is it'' problem, while assuming
they know what the object is. Although each approach addresses an
important aspect of the \mbox{3-D} object recognition problem, each
falls short in addressing the complete problem of recognizing and
localizing \mbox{3-D} objects from a large database. In this paper, we
first synthesize a new approach to shape recovery for \mbox{3-D}
object recognition that decouples recognition from localization by
combining basic elements from these two approaches.  Specifically, we
use qualitative shape recovery and recognition techniques to provide
strong fitting constraints on physics-based deformable model recovery
techniques.  Secondly, we extend our previously developed technique of
fitting deformable models to occluding image contours to the case of
image data captured under general orthographic, perspective, and stereo
projections.  On one hand, integrating qualitative knowledge of the
object being fitted to the data, along with knowledge of occlusion
supports a much more robust and accurate quantitative fitting. 
On the other hand,
recovering object pose and quantitative surface shape not only
provides a richer description for indexing, but supports interaction
with the world when object manipulation is required.  This paper
presents the approach in detail and applies it to real imagery.
\end{abstract}
{\bf keywords: } qualitative and quantitative shape recovery, 
physics-based modeling, deformable model fitting, 
object representation, object recognition.

\pagebreak
\section{Introduction}

Since the introduction of a class of qualitatively-defined volumetric
primitives, called {\it geons} \cite{BIE85}, interest has been growing
in building \mbox{3-D} object recognition systems based on qualitative
shape \cite{BERG89,BIE92,DIC92a,DIC92b,FAI91,JAC92,NAR92}. One of the
primary motivations in these systems is that, as stated by Biederman
\cite{BIE85}, the task of recognizing (or identifying) an object
should be separated from the task of locating it.  Furthermore, the
exact shape of the object need not be recovered to facilitate
recognition; a coarse-level description of shape is sufficient to
distinguish between different classes of objects. The above systems,
therefore, address only the task of recognizing the object.  This is
in contrast to classical \mbox{3-D} object recognition systems, in
which exact viewpoint is required to verify typically weak object
hypotheses, while the object models capture the exact geometry of the
object \cite{CLE91,HUT88,LOW85,THO87}. Determining the pose of the
object is a critical component of these approaches.

Each of the above recognition schools addresses an important requirement
of recognition systems: coarse object identification and object localization.
However, there has been little effort to combine them into a single paradigm.
In cases where detailed object localization and shape recovery is required,
the qualitative shape recovery methods fall short, while in cases where 
there are large object databases whose models are invariant to minor changes
in shape, the quantitative recognition/localization methods fall short.
In this paper, we unify these two schools into a single approach
which first recovers qualitative shape from an image, and then uses that
shape to constrain a quantitative recovery of the object's shape
and pose. 

Physics-based modeling \cite{PEN91a,TER88,TER91,MET91,MET92,MET93c} provides a very powerful mechanism
for quantitatively modeling an object's shape for recognition. 
In a typical geometry-based model-driven recovery process, 
image features are matched
to a set of rigid, a priori object models 
which dictate the exact geometry of
an object and offer few degrees of freedom. 
In contrast, deformable models offer a less constrained, data-driven
recovery process, in which forces derived from the image deform the
model until it fits the data. 
In previous work, we developed a physics-based
framework for recovering shape and nonrigid motion from both
\mbox{2-D} and \mbox{3-D} data using a new class of deformable part
models \cite{TER91,MET91,MET92}.  These models incorporate global
deformation parameters which represent the salient shape features of
natural parts, and local deformation parameters which capture shape
details. Thus, unlike previous physics-based techniques 
\cite{TER88}, the shape of
an object can both be abstracted or represented in detail.  The
framework also develops physics-based constraints to recover complex
articulated models from deformable parts, and provides force-based
techniques for fitting such models to sparse, noise-corrupted 2D and
3D visual data.  These techniques lead to estimators that exploit the
dynamic formulation of deformable models to track moving 3D objects
from time-varying observations.  

As powerful as these and other
active, deformable model recovery techniques are, they have some serious
limitations. Their success relies on both the accuracy of initial
image segmentation and initial placement of the model given the
segmented data.  For example, such techniques often assume that the
bounding contour of a region belongs to the object, a problem when the
object is occluded. In addition, such techniques often require a
manual segmentation of an object into parts. 
For these techniques to be successful in an autonomous recognition system,
it is imperative that more attention
be given to the initial segmentation of an image into parts. Furthermore,
since deformable model recovery techniques are sensitive to initial
model position and orientation, the segmentation procedure should
provide at least a coarse estimate of position and orientation. Finally, 
to constrain the process
of recovering a deformable model from an image, the segmentation process
should extract the qualitative shape of the part, e.g., how many surfaces does
it have?; what shape are the surfaces?; etc.

In recent work, we presented an approach to the representation, recovery,
and recognition of qualitative 
\mbox{3-D} objects from a single \mbox{2-D} image
\cite{DIC90,DIC92a,DIC92b}.  In that approach, an object is modeled
using a set of object-centered \mbox{3-D} volumetric modeling
primitives; the primitives, in turn, are mapped to a set of
viewer-centered aspects. Unlike typical aspect-based recognition
systems that use aspects to model entire objects, the approach uses
aspects to model the finite set of {\it parts} from which the objects
are constructed; the resulting aspect set is fixed and {\it
independent} of the size of the object database.  To accommodate the
matching of partial aspects due to primitive occlusion, a hierarchical
aspect representation was introduced, called the {\it aspect
hierarchy}, based on the projected surfaces of the primitives; a set
of conditional probabilities captures the ambiguity of mappings
between the levels of the hierarchy.  Once an aspect is recovered from
an image, a qualitative volumetric shape primitive is inferred from
the aspect. However, a limitation of the recovered primitive is that
it simply encodes a shape class; no quantitative shape information
such as size and curvature, or accurate position and orientation is
specified.  The inclusion of such information would not only enhance
the descriptive power of the recovered primitives, thereby increasing
their indexing power for recognition, it is essential for object
manipulation.

In this paper, we integrate qualitative and quantitative shape recovery
from \mbox{2-D} images. In particular, we use knowledge of both
a primitive's qualitative shape and its orientation (encoded by its
aspect) to provide strong constraints in fitting a deformable model to
the contour data. Since the qualitative primitive recovery technique
supports primitive occlusion through a hierarchical aspect
representation, it can selectively pass to the model fitting stage
only those contours belonging to the object. In addition, the
correspondence between image faces and model surfaces encoded in the
recovered qualitative primitive can be exploited to provide strong
constraints on the initial placement of the deformable model. 
Furthermore, this correspondence allows us to extend our previously developed
technique for deformable model fitting, which is limited to 
orthographic projection of occluding boundaries \cite{TER91}, 
to the case of more general objects with internal surface
discontinuities under 
general orthographic, perspective, and stereo projections.

The paper is organized as follows. First we describe both the qualitative
and quantitative object modeling paradigms. Next, we describe 
both the qualitative and quantitative shape recovery processes. 
Finally, we evaluate the performance of the approach on a series 
of real images of objects under orthographic, perspective, and
stereo projection.
\section{Related Work}
Recently, several researchers have proposed various segmentation
techniques to partition image or range data, in order to automate the
process of fitting  volumetric primitives to the data.
Most of those approaches are applied to range data only
\cite{SOL90,GUP91}, while Pentland \cite{PEN90}
describes a two-stage algorithm to fit superquadrics to image data.
In the first stage, he segments the image using a filtering operation
to produce a large set of potential object ``parts'', followed by a 
quadratic optimization procedure that searches among these part hypotheses
to produce a maximum likelihood estimate of the image's part structure.
In the second stage, he fits superquadrics to the 
segmented data using a least squares
algorithm. Pentland's approach is only applicable to the case of
occluding boundary data under simple orthographic projection, as is
true of earlier work of Terzopoulos et al. \cite{TER88},
Terzopoulos and Metaxas \cite{TER91}, and
Pentland and Sclaroff \cite{PEN91a},
which address only the problem of model fitting.

The fundamental difference between our approach and the above
approaches is that we use a qualitative segmentation of the image to provide
sufficient constraints to our deformable model fitting procedure. In addition,
we generalize our deformable model fitting technique to accommodate
orthographic, perspective, and stereo projections.

\section{Object Modeling}

\subsection{Qualitative Shape Modeling}
In this section, we briefly review the qualitative shape modeling
technique described in \cite{DIC90,DIC92a,DIC92b}.
\subsubsection{Object-Centered Models}
Given a database of object models representing the domain of a
recognition task, we seek a set of three-dimensional volumetric
primitives that, when assembled together, can be used to construct the
object models.  Many \mbox{3-D} object recognition systems have
successfully employed \mbox{3-D} volumetric primitives to construct objects.
Commonly used classes of volumetric primitives include polyhedra 
(e.g., Lowe \cite{LOW85}), generalized cylinders (e.g., Brooks \cite{BRO83}), 
and superquadrics (e.g., Pentland \cite{PEN86}). 
Whichever set of volumetric modeling primitives is chosen, they will
be mapped to a set of viewer-centered aspects.  

To demonstrate our approach to object recognition, we have selected an
object representation similar to that used by Biederman \cite{BIE85},
in which the Cartesian product of contrastive shape properties gives
rise to a set of volumetric primitives called geons. 
For our investigation, we have
chosen three properties including cross-section shape, axis shape, and
cross-section size variation (Dickinson et al. \cite{DIC90}). 
The values of these properties give rise to a
set of ten primitives (a subset of Biederman's geons), modeled 
using Pentland's SuperSketch
\mbox{3-D} modeling tool \cite{PEN86}, and illustrated in
Figure~\ref{fig:object-representation}(a).
To construct objects, the primitives are attached to one another with
the restriction that any junction of two primitives involves exactly
one distinct surface from each primitive.
\begin{figure}
\makebox[1.75in][l]{
\hspace{0.0in}
\special{psfile=/homes/orasis/map/sven/optica/doc/primitives.ps hoffset=-50 voffset=-65 hscale=45 vscale=45}
}
\makebox[4.25in][l]{
\hspace{-0.125in}
\epsfysize=3.00in
\epsfbox{/homes/orasis/map/sven/optica/doc/aspect-hierarchy.eps}
}
\vspace{0.25in}
\makebox[1.75in][l]{
\hspace{1.0in}
(a)}
\makebox[4.25in][l]{
\hspace{3.00in}
(b)}
\caption{(a) The Ten Modeling Primitives, (b) The Aspect Hierarchy}
\label{fig:object-representation}
\end{figure}
\subsubsection{Viewer-Centered Models}
To recover the volumetric primitives from an image, we need some way of
modeling their appearance in the image.
Traditional aspect graph representations of \mbox{3-D} objects model
an entire object with a set of aspects, each defining a topologically
distinct view of an object in terms of its visible surfaces
\cite{KOE79}.
Our approach differs in that we use aspects to
represent a (typically small) set of volumetric primitives from which
each object in our database is constructed, rather than representing
an entire object directly.
Consequently, our goal is to use aspects to
recover the \mbox{3-D} primitives that make
up the object in order to carry out a recognition-by-parts procedure,
rather than attempting to use aspects to recognize entire objects.
The advantage of this approach is that since the number of
qualitatively different primitives is generally small, the number of
possible aspects is limited and, more important, {\it independent}
of the number of objects in the database. The disadvantage is that if
a primitive is occluded from a given \mbox{3-D} viewpoint, its
projected aspect in the image will also be occluded.  Thus we must
accommodate the matching of occluded aspects, which we accomplish by
use of a hierarchical representation we call the {\it aspect
hierarchy}.

The aspect hierarchy consists
of three levels, consisting of the set of {\it aspects} that model
the chosen primitives, the set of component {\it faces} of the aspects,
and the set of {\it boundary groups} representing all subsets of
contours bounding the faces.
Figure~\ref{fig:object-representation}(b) illustrates a portion of
the aspect hierarchy.
The ambiguous mappings between the levels of the
aspect hierarchy are captured in a set of conditional probabilities
(Dickinson et al. \cite{DIC90,DIC92a}),
mapping boundary groups to faces, faces to aspects,
and aspects to primitives. These conditional probabilities 
result from a statistical analysis of a set of images approximating
the set of {\it all} views of {\it all} the primitives.
\subsection{Quantitative Shape Modeling}

In this section we first briefly review the general formulation of deformable
models; further detail can be found in \cite{TER91,MET91}. We then extend
the formulation to the case of orthographic, perspective, and stereo
projections. 

\subsubsection{Geometry}

Geometrically, the models developed in this paper are closed surfaces
in space whose intrinsic (material) coordinates are $\ru=(u, v)$,
defined on a domain $\Omega$.  The positions of points on the model
relative to an inertial frame of reference $\Phi$ in space are given
by a vector-valued, time varying function of $\ru$:
\begin{equation}
\vx(\ru,t)=(x_1(\ru,t),x_2(\ru,t),x_3(\ru,t))\tpose,
\end{equation}
where $\tpose$ is the transpose operator.
We set up a noninertial, model-centered reference frame $\phi$, 
as shown in Fig.~\ref{fig:geometry},
and
express these positions as:
\begin{equation}
\vx=\vc + \mat R\vec p,
\end{equation}
where $\vc(t)$ is the origin of $\phi$ at the center of the model, with
the orientation of $\phi$ given by the rotation matrix $\mat R(t)$.
Thus, $\vec p(\ru, t)$ denotes the canonical positions of points on
the model relative to the model frame. In \cite{TER91}, we 
further express $\vec p$ as
the sum of a reference shape $\vec s(\ru,t)$ (global deformation)
and a displacement
function $\vec d(\ru,t)$ (local deformation): 
\begin{equation}
\vec p =\vec s + \vec d.
\label{eq:p-old}
\end{equation}
However, since computing \mbox{3-D}
local deformations from \mbox{2-D} contour data
is underconstrained, we will consider only global deformations, $\vec s$,
since they are sufficient to represent the
shapes of the ten volumetric primitives shown in 
Figure~\ref{fig:object-representation}(a).
Thus, we have:
\begin{equation}
\vec p =\vec s.
\label{eq:p} 
\end{equation}
\begin{figure}
\epsfysize=3.75in
\center\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/deform1.ps}
\caption{Geometry of Deformable Model}
\label{fig:geometry}
\end{figure}

The ensuing formulation can be carried out for any reference shape
given as a parameterized function of $\ru$. Based on the shapes we
want to recover, 
we first consider the case of superquadric ellipsoids \cite{BAR81}, which
are given by the following formula:
\begin{equation}
\vec e = a\left( \begin{array}{l}
        a_1 {C_u}^{\epsilon_1} {C_v}^{\epsilon_2}\\
        a_2 {C_u}^{\epsilon_1} {S_v}^{\epsilon_2}\\
        a_3 {S_u}^{\epsilon_1}
       \end{array} \right),
\label{eq:suqeq}
\end{equation}
where $-\pi/2\leq u\leq \pi/2$ and $-\pi\leq v<\pi$, and where
${S_w}^\epsilon=\sgn(\sin w)|\sin w|^\epsilon$ and
${C_w}^\epsilon=\sgn(\cos w)|\cos w|^\epsilon$, respectively. Here,
$a\geq0$ is a scale parameter, $0\leq a_1, a_2, a_3
\leq 1$ are aspect ratio parameters, and $\epsilon_1, \epsilon_2 \geq 0$ 
are ``squareness'' parameters. 

We then combine linear tapering along principal axes
$1$ and $2$, and
bending along principal axis $3$ of the superquadric 
$\vec e$\footnote{These coincide with
the model frame axes $x, y$ and $z$ respectively} into a single
parameterized deformation $\mat T$, and express the reference shape as:
\begin{equation}
\vec s =\mat T(\vec e, t_1, t_2, b_1, b_2, b_3) = \left(\begin{array}{l}
(\frac{t_1 e_3}{a a_3 w} + 1)~e_1 + b_1~ cos(\frac{e_3 + b_2}{a a_3 w} \pi
b_3)\\ (\frac{t_2 e_3}{a a_3 w} + 1)~e_2 \\ e_3 \end{array}\right),
\end{equation}
where $-1 \leq t_1, t_2 \leq 1$ are the tapering parameters in principal axes $1$
and $2$, respectively; where $b_1$ defines the magnitude of
the bending and can be positive or negative; $-1 \leq b_2 \leq 1$
defines the location on axis $3$ where bending is applied; and $0 <
b_3 \leq 1$ defines the region of influence of bending.  Our method for
incorporating global deformations is not restricted to only tapering
and bending deformations.  Any other deformation that can be expressed
as a continuous parameterized function can be incorporated as our global
deformation in a similar way.

We collect the parameters in $\vec s$ into the parameter vector:
\begin{equation}
\vec q_s=(a, a_1, a_2, a_3, \epsilon_1, \epsilon_2, 
t_1, t_2, b_1, b_2, b_3)\tpose.
\end{equation}
The above global deformation parameters are adequate for quantitatively
describing the ten modeling primitives shown in 
Figure~\ref{fig:object-representation}(a).

\subsubsection{Kinematics}

The velocity of points on the model is given by:
\begin{eqnarray}
\vxdot&=&\vcdot+\dot\mat R \vec p + \mat R \dot\vec p \nonumber\\
      &=&\vcdot+\mat B\vthetadot+\mat R\dot\vec s,
%+\mat R\mat S\dot\vec q_d,
\end{eqnarray}
where $\vtheta=(\dots,\theta_i,\dots)\tpose$ is the vector of
rotational coordinates of the model, and $\mat B = [\dots\partial(\mat
R\vec p)/\partial\theta_i\dots]$. Furthermore,
\begin{equation}
\dot\vec s = \left[ 
\frac {\partial \vec s} {\partial \vec q_s} 
\right] \dot\vec q_s\;\;=\;\;
\mat J\dot\vec q_s,
\end{equation}
where $\mat J$ is the Jacobian of the 
deformable superquadric model with
respect to the
global degrees of freedom.

Defining $r=\frac{e_3+b_2}{a a_3}\pi b_3$, the Jacobian matrix $\mat J$
is a $3\times11$ matrix whose non-zero entries are:
\begin{eqnarray}
\mat J_{11} &=& (t_1 {S_u}^{\epsilon_1} + 1) a_1{C_u}^{\epsilon_1}
{C_v}^{\epsilon_2} + \frac{b_1 b_2 b_3}{a^2  a_3}\pi \sin (r)\nonumber\\
\mat J_{21} &=& (t_2 {S_u}^{\epsilon_1} +1)  a_2{C_u}^{\epsilon_1}
{S_v}^{\epsilon_2} \nonumber\\
\mat J_{31} &=&  a_3 {S_u}^{\epsilon_1}\nonumber\\
\mat J_{12} &=& (t_1{S_u}^{\epsilon_1}+1) a  {C_u}^{\epsilon_1}
{C_v}^{\epsilon_2}\nonumber\\
\mat J_{23} &=& (t_2 {S_u}^{\epsilon_1}+1) a  {C_u}^{\epsilon_1}
{S_v}^{\epsilon_2}\nonumber\\
\mat J_{14} &=& \frac{b_1 b_2 b_3}{a  {a_3}^2}\pi \sin (r)\nonumber\\
\mat J_{34} &=& a  {S_u}^{\epsilon_1}\nonumber\\
\mat J_{15} &=& t_1 \ln\left (|\sin u\right |) {S_u}^{\epsilon_1}
a  a_1{C_u}^{\epsilon_1}
{C_v}^{\epsilon_2} +(t_1{S_u}^{\epsilon_1}+1) a  a_1 \ln\left (|\cos u\right |)
{C_u}^{\epsilon_1}{C_v}^{\epsilon_2} \nonumber\\
&&-b_1b_3\pi \ln\left (|\sin u\right |)
{S_u}^{\epsilon_1} \sin (r)\nonumber\\
\mat J_{25} &=& t_2 \ln\left (|\sin u\right |)
{S_u}^{\epsilon_1}a  a_2{C_u}^{\epsilon_1}
{S_v}^{\epsilon_2} +(t_2{S_u}^{\epsilon_1}+1) a  a_2 \ln\left (|\cos u\right |)
{C_u}^{\epsilon_1}{S_v}^{\epsilon_2}\nonumber\\
\mat J_{35} &=& a  a_3 \ln(\left |\sin u\right |) {S_u}^{\epsilon_1}\nonumber\\
\mat J_{16} &=& (t_1{S_u}^{\epsilon_1}+1)a  a_1 \ln(\left |\cos v\right |)
{C_u}^{\epsilon_1}{C_v}^{\epsilon_2}\nonumber\\
\mat J_{26} &=& (t_2{S_u}^{\epsilon_1}+1) a  a_2 \ln\left (|\sin v\right |)
{C_u}^{\epsilon_1}{S_v}^{\epsilon_2}\nonumber\\
\mat J_{17} &=& {S_u}^{\epsilon_1}a  a_1{C_u}^{\epsilon_1}
{C_v}^{\epsilon_2}\nonumber\\
\mat J_{28} &=& {S_u}^{\epsilon_1}a  a_2{C_u}^{\epsilon_1}
{S_v}^{\epsilon_2}\nonumber\\
\mat J_{19} &=& \cos (r)\nonumber\\
\mat J_{1\,10} &=& -\frac{b_1b_3}{aa_3}\pi \sin (r)\nonumber\\
\mat J_{1\,11} &=& -b_1 \pi \sin (r)~r,
\end{eqnarray}
where ${S_\theta}^\epsilon=\sgn(\sin \theta)|\sin \theta|^\epsilon$
and ${C_\theta}^\epsilon=\sgn(\cos \theta)|\cos \theta|^\epsilon$.


We can
therefore write:
\begin{equation}
\vxdot  = [\mat I ~\mat B~ \mat R\mat J ] \dot{\vec q}  % ~\mat R\mat S ] 
= \mat L  \dot\vec q,
\label{eq:velocity}
\end{equation}
where $\mat L$ is the Jacobian of the superquadric model,
$\vec q = (\vec q_c\tpose, \vec q_\theta\tpose, \vec q_s\tpose)\tpose$, with
$\vec q_c=\vec c$ and $\vec q_{\theta}=\vtheta$. 

\subsubsection{Dynamics}

When fitting the model to visual data, our goal is to recover $\vec
q$, the vector of degrees of freedom of the model.  The components
$\vec q_c$ and $\vec q_\theta$ are the global rigid motion
coordinates and $\vec q_s$ are the global deformation coordinates.
Our
approach carries out the coordinate fitting procedure in a
physically-based way.  We make our model dynamic in $\vec q$ by
introducing mass, damping, and a deformation strain energy. This
allows us, through the apparatus of Lagrangian dynamics, to arrive at
a set of equations of motion governing the behavior of our model under
the action of externally applied forces.

The Lagrange equations of motion take the form \cite{TER91}:
\begin{equation}
\mat M \ddot\vec q + \mat D\dot\vec q + \mat K\vec q =\vec g_q + \vec
f_q,
\label{eq:motion}
\end{equation}
where $\mat M$, $\mat D$, and $\mat K$ are the mass, damping, and
stiffness matrices, respectively, where $\vec g_q$ are inertial
(centrifugal and Coriolis) forces arising from the dynamic coupling
between the local and global degrees of freedom, and where $\vec
f_q(\ru,t)$ are the generalized external forces associated with the
degrees of freedom of the model. The generalized external forces
will be discussed in detail in Section~\ref{sec:applied-forces}.


\subsubsection{Orthographic Projection}

In the case of orthographic projection, the points on the 
model $\vec x=(x,y,z)$
project to the image points $x_p$ and $y_p$ as follows:
\begin{eqnarray}
x_p &=& x\nonumber\\
y_p &=& y.
\label{eq:orth}
\end{eqnarray}

By taking the derivative of the above equation
(\ref{eq:orth}) with respect to time,
we arrive at the following formulas:
\begin{eqnarray}
{\dot x}_p &=& \dot x \nonumber\\
{\dot y}_p &=& \dot y.
\label{eq:orth1}
\end{eqnarray}
Rewriting (\ref{eq:orth1}) in matrix form and using (\ref{eq:velocity}),
we arrive at the following matrix equations:
\begin{equation}
\left[\begin{array}{c}
\dot x_p\\
\dot y_p\end{array}\right]=
\left[\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0\end{array}\right]
\left[\begin{array}{c}
\dot x\\
\dot y\\
\dot z
\end{array}\right]=
\end{equation}

\begin{equation}
\left[\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0\end{array}\right]
\mat L\dot\vec q.
\label{eq:orth2}
\end{equation}

If we rewrite (\ref{eq:orth2})
in compact form, we get
\begin{equation}
\left[\begin{array}{c}
\dot x_p\\
\dot y_p\end{array}\right]= \mat L_o \dot\vec q,
\end{equation}
where 
\begin{equation}
\mat L_o = 
\left[\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0\end{array}\right]
\mat L.
\end{equation}


\subsubsection{Perspective Projection}

In the case of perspective projection, points on the model $\vec x=(x,y,z)$
project into image points, $x_p$ and $y_p$, based on the formula:
\begin{eqnarray}
x_p &=& \frac{x}{z} f\nonumber\\
y_p &=& \frac{y}{z} f,
\label{eq:persp}
\end{eqnarray}
where $f$ is the focal length. 

By taking the derivative of the above equation
(\ref{eq:persp}) with respect to time,
we arrive at the following formulas:
\begin{eqnarray}
{\dot x}_p &=& \dot x \frac{f}{z} - \frac{x}{z^2}f \dot z\nonumber\\
{\dot y}_p &=& \dot y \frac{f}{z} - \frac{y}{z^2}f \dot z.
\label{eq:persp1}
\end{eqnarray}
Rewriting (\ref{eq:persp1}) in matrix form and using (\ref{eq:velocity}),
we arrive at the following matrix equations
\begin{equation}
\left[\begin{array}{c}
\dot x_p\\
\dot y_p\end{array}\right]=
\left[\begin{array}{ccc}
f/z & 0 & -x/z^2f\\
0 &f/z&-y/z^2 f\end{array}\right]
\left[\begin{array}{c}
\dot x\\
\dot y\\
\dot z
\end{array}\right]=
\end{equation}

\begin{equation}
\left[\begin{array}{ccc}
f/z & 0 & -x/z^2f\\
0 &f/z&-y/z^2 f\end{array}\right]
\mat L\dot\vec q.
\label{eq:persp2}
\end{equation}

If we rewrite (\ref{eq:persp2})
in compact form, we get
\begin{equation}
\left[\begin{array}{c}
\dot x_p\\
\dot y_p\end{array}\right]= \mat L_p \dot\vec q,
\end{equation}
where 
\begin{equation}
\mat L_p = 
\left[\begin{array}{ccc}
f/z & 0 & -x/z^2f\\
0 &f/z&-y/z^2 f\end{array}\right]
\mat L.
\label{eq:persp3}
\end{equation}


The above two Jacobian matrices, $\mat L_o$ and $\mat L_p$,
will be used in the calculation of the generalized external
forces $\vec f_q$ from two dimensional external forces $\vec f$
that the data exert on the model. 


\subsubsection{Stereo Projection}

In the case of stereo projection, we assume two parallel cameras, each 
under perspective projection, resulting in two images, $L$ and $R$.
The model points $\vec x$ project on each of the images
based on (\ref{eq:persp}) and the corresponding Jacobian matrices
$\mat L_{pL}$ and $\mat L_{pR}$ are calculated using (\ref{eq:persp3}).

To recover the exact location of the model frame $\vec c$,
we apply the following procedure:
\begin{itemize}
\item We first independently fit the model to the left  and right image data.
This results in two model instances, $m_L$ and $m_R$, one per image, 
having the same scale. 
\item Choosing one of the images, say $R$, we project the 
locations $\vec c_{L}$ and $\vec c_{R}$, 
of the left and right model frames 
of the two model instances  $m_{L}$ and $m_{R}$,
into $R$. Let the locations of the projected model centers
be $\vec c_{LI}$ and $\vec c_{RI}$, respectively.
\item We then map the difference in the $x$ coordinates\footnote{Since 
the two cameras are parallel, the projections of the two model frame
centers differ only in the $x$ direction.}
of $\vec c_{LI}$ and $\vec c_{RI}$
into a force that modifies $\vec c_{L}$ and $\vec c_{R}$ in the 
direction of $\vec c_{L}$ and $\vec c_{R}$, respectively, according
to the following formula:
\begin{equation}
\dot\vec c_k = s |c_{LIx} - c_{RIx}| \frac{\vec c_k}{\|\vec c_k\|}
\end{equation}
where $k=L$ or $k=R$, $s=1$ if $c_{LIx} < c_{RIx}$, and $s=-1$ otherwise.
\item Once $\vec c_{LI} = \vec c_{RI}$, we first sum the forces 
that the left and right image data exert on the model. From their sum, we then 
compute the generalized force $f_{q_a}$ that corresponds to the
scaling parameter $a$ (\ref{eq:suqeq}), and using (\ref{eq:motion}),
we modify $a$.
\end{itemize}



\section{Shape Recovery}
\label{sec-recovery}
\subsection{Qualitative Shape Recovery}
Primitive recovery consists of the following three steps, resulting in a 
graph representation of the image in which nodes represent
recovered \mbox{3-D} primitives, and arcs represent hypothesized
connections between the primitives; details of the complete
recovery process, including algorithms to handle various
segmentation errors, can be found in Dickinson et al. \cite{DIC92a}.
In the following subsections, we briefly review the approach to
recovering qualitative shape.
\subsubsection{Face Recovery}
The first step to recovering a set of faces is a region segmentation of the
input image. We begin by applying Saint-Marc, Chen, and Medioni's
edge-preserving adaptive smoothing
filter to the image \cite{SAI91}, followed by a morphological gradient
operator \cite{LEE87}. A hysteresis thresholding
operation is then applied to produce a binary image from which a set
of connected components is extracted. Edge regions are then burned away,
resulting in a {\it region topology graph} in which nodes represent
regions and arcs specify region adjacencies.

From a region topology graph,
each region is characterized according to 
the qualitative shapes of its bounding contours. First, the bounding contour
of each region is partitioned at curvature extrema using Saint-Marc, Chen, and
Medioni's adaptive smoothing curve partitioning technique \cite{SAI91}. 
Next, each
bounding contour is classified as straight, convex, or concave, by
comparing the contour to a fitted line. Finally, 
each pair of bounding contours is checked for cotermination, parallelism, or
symmetry. The result is a {\it region boundary graph} 
representation for a region in which nodes
represent bounding contours, and arcs represent pairwise nonaccidental
relations between the contours. 

Face labeling consists of matching a
region boundary graph to the graphs representing the model
faces in the aspect hierarchy. Region boundary graphs 
that exactly match a face
in the aspect hierarchy will be given a single label with probability
1.0. For region boundary graphs that do not match due to occlusion,
segmentation errors, or errors in computing their graphs, we descend
to an analysis at the boundary group level and match subgraphs of the
region boundary graph to the graphs representing the 
boundary groups in the aspect hierarchy. Each subgraph that
matches a boundary group generates a set of possible face 
interpretations (labels), each with a corresponding probability.
The result is a {\it face topology graph} in which each node contains
a set of face labels (sorted by decreasing order of probability)
associated with a given region.
\subsubsection{Aspect Recovery}
In an unexpected object recognition domain in which there is no
a priori knowledge of scene content, we 
can formulate the problem of extracting aspects as follows:
Given a face topology graph with a set of face hypotheses (labels)
at each node (region), find an
{\it aspect covering} of the face topology graph
using aspects in the aspect hierarchy, 
such that no region is left uncovered and each region is covered by only one
aspect.  Or, more formally: Given an input face topology graph, \(FTG\),
partition the nodes (regions) of \(FTG\) into disjoint sets,
\(S_{1}, S_{2}, S_{3},\ldots, S_{k}\), such that the graph
induced by each set, \(S_{i}\), is
isomorphic to the graph representing some aspect, 
\(A_{j}\), from a fixed set of
aspects, \(A_{1}, A_{2}, A_{3},\ldots,A_{n}\).  

There is no known polynomial time algorithm to solve this problem (see
\cite{DIC92a} for a discussion on the problem's computational complexity);
however, the conditional probability matrices embedded in the aspect 
hierarchy provide a powerful
constraint that can make the problem tractable. For each face hypothesis
(for a given region), we can use the face to aspect
mapping to generate the possible {\it aspect hypotheses} that might
encompass that face\footnote{The probability of an aspect
hypothesis is the product of the face to aspect mapping and the
probability of the face hypothesis from which it was inferred.}.  
At each face, we collect all the aspect hypotheses 
(corresponding to all face hypotheses) and rank them in
decreasing order of probability.\footnote{For a detailed
discussion of aspect instantiation and how occluded aspects are
instantiated, see \cite{DIC92a}.}

We can now reformulate our bottom-up aspect recovery
problem as a search through the 
space of
aspect labelings of the regions (nodes) in the face topology graph.
In other words, we wish
to choose one aspect hypothesis from the list at each node, such that
the instantiated aspects completely cover the face topology graph. 
For our search through the possible aspect labelings of the face topology
graph, we employ Algorithm A (Nilsson \cite{NIL80}) with a heuristic
designed to meet
three objectives. 
First, we favor selections of aspects instantiated
from higher probability aspect hypotheses. Second, we favor selections
whose aspects have fewer occluded faces, since we are more confident of
their labels. Finally,
we favor those aspects covering more
faces in the image; we seek the minimal aspect covering of the 
face topology graph.
Since there may be many labelings which satisfy this constraint,
and since we cannot
guarantee that a given aspect covering represents a correct
interpretation of the scene, we must be able to enumerate, in
decreasing order of likelihood, all aspect coverings until the objects
in the scene are recognized.

In an expected object recognition domain in which we are searching
for a particular object or part, we use the aspect hierarchy as
an attention mechanism to focus the search for an aspect at appropriate
regions in the image. Moving down the aspect hierarchy, target objects map to
target volumes which, in turn, map to target aspect predictions which, 
in turn, map to target face
predictions. Verification of the target aspect prediction occurs at those
faces in the face topology graph whose labels match the target face prediction.
The scores of the matching faces are used to order the recovery process
which attends first to high-quality faces.
This attention
mechanism has been used to drive an active recognition system which moves
the cameras to obtain either a more likely or unambiguous view of an
object's part \cite{DIC93b}.

\subsubsection{Primitive Recovery} 
In the expected object recognition approach described above, primitive
recovery consists of mapping the recovered aspect directly to the
target primitive prediction. Primitive recovery for the unexpected
object recognition case is more complex.  From an {\it aspect
covering} of the regions in the image, a set of primitive labels and
their corresponding probabilities is inferred (using the aspect
hierarchy) from each aspect. Primitive recovery is formulated as a
search through the space of primitive labelings of the aspects in the
aspect covering, guided by a heuristic based on the probabilities of
the primitive labels. Each solution, or {\it primitive covering},
found by the search is a valid primitive interpretation of the input
image.  
Encoded in each recovered primitive is the aspect in which it it
viewed; the aspect, in turn, encodes the faces that were used in
instantiating the aspect, while each face specifies those contours in
the image used to instantiate the face. 

\subsubsection{Stereo Correspondence} 
In the case of stereo projection, we independently apply the qualitative
shape recovery process to the left and right images. The correspondence
problem then consists of matching qualitative primitive descriptions
in the two images. 
A pair of volumes
represents a correspondence if: (i) the volumes have the same
label, (ii) their aspects have the same label, and (iii) the ratio of
the vertical
intersection of the bounding rectangles of the two volumes to the 
vertical size of each bounding rectangle exceeds some threshold
(epipolar constraint). Intuitively, volumes from the left and right
image are said to correspond if they are of the same type, they are viewed
in roughly the same orientation, and their vertical disparity is small.
Note that this provides only a coarse correspondence; dimensions,
orientation, and curvature of the volumes may be disparate. During the
independent quantitative shape recovery of the left and right models, 
additional shape information can be used to prune weak correspondences,
providing a coarse-to-fine stereo correspondence scheme.
\subsection{Quantitative Shape Recovery}

\subsubsection{Simplified Numerical Simulation}

Equations (\ref{eq:motion}) give the general equations of motion for a
dynamic model with deformations. A full
implementation and simulation of the general equations would be
appropriate for physically-based animation where realistic motion is
important \cite{TER88c}.  However, in computer vision and
geometric design applications involving the fitting of models to data,
models governed by simplified equations of motion suffice, as the
experiments in Section \ref{sec:results} will demonstrate.

We can simplify the equations while preserving useful dynamics by
setting the mass density $\mu(\ru)$ to zero
to obtain \cite{TER91}:
\begin{equation}
\mat D\dot\vec q + \mat K\vec q =\vec
f_q.
\label{eq:motion-simple}
\end{equation}
These equations yield a model which has no inertia and comes to rest
as soon as all the applied forces vanish or equilibrate.
Equation (\ref{eq:motion-simple}) is discretized in material
coordinates $\ru$ using nodal finite element basis functions. We
carry out the discretization by tessellating the surface of the model
into linear triangular elements.

The formulation of our model yields numerically stable equations of
motion that may be integrated forward through time using explicit
procedures.  For fast interactive response, we employ a first-order
Euler method to integrate (\ref{eq:motion-simple}).  The Euler
procedure updates the degrees of freedom $\vq$ of the model at time
$t+\Delta t$ according to the formula:
\begin{equation}
\vec q\iter{t+\Delta t}=\vec q\iter t + 
\Delta t~~(\mat D\iter{t})\inv\left(\vf_q\iter t -\mat K
\vq\iter t\right),
\label{eq:eustep}
\end{equation}
where $\Delta t$ is the time step size.

Taking time steps in $\vq$ is straightforward, but the rotation
component $\vq_\theta$ is a little delicate. We represent $\vq_\theta$
using quaternions.  Updating quaternions at each time step is easier
than directly updating a rotation matrix and ensuring that it remains
orthogonal.  

A quaternion $[s, \vec v]$ with unit magnitude, $\|[s,\vec v]\| =
s^2+\vec v\tpose\vec v=1$, specifies a rotation of the model from its
reference position through an angle $\theta =2\cos\inv s$ around an
axis aligned with vector $\vec v=[v_1,v_2,v_3]\tpose$.  The rotation
matrix corresponding to $[s,\vec v]$ is:
\begin{equation}
\mat R =\left[
\begin{array}{ccc}
1-2(v_2^2 + v_3^2) & 2(v_1 v_2 - s v_3) & 2(v_1 v_3+ s v_2)\\
2(v_1 v_2 + s v_3) & 1-2(v_1^2+v_3^2) & 2(v_2 v_3 - s v_1) \\
2(v_1 v_3 - s v_2) & 2(v_2 v_3 + s v_1) & 1-2(v_1^2 + v_2^2)
\end{array}
\right].
\end{equation}
To obtain $\vq_\theta$ from (\ref{eq:eustep}), we use the generalized
torque at time $t$ given by $\vec f_\theta\tpose =\int\vec f\tpose\mat B du$, with $\mat B$ \cite{SHAB89,TER91}: 
\begin{equation}
\mat B(u) = -\mat R~\mat {\tilde p}(u)~ \mat G,
\end{equation}
where $\mat R$ represents the rotation matrix at time $t$, where
$\mat{\tilde p}(u)$ is the dual $3\times 3$ matrix of the position
vector $\vec p(u)=(p_1,p_2,p_3)\tpose$ (see (\ref{eq:p})) defined as:
\begin{equation}
\mat{\tilde p}(u) = \left[\begin{array}{ccc}
0&-p_3&p_2\\p_3&0&-p_1\\-p_2&p_1&0\end{array}\right]
\end{equation}
and where $\mat G$ is a $3\times 4$ matrix whose definition is based on the
value of the quaternion $\vec q_\theta=[s,\vec v ]$ representing the
rotation at time $t$:
\begin{equation}
\mat G =2\left[\begin{array}{cccc}
-v_1&s&v_3&-v_2\\-v_2&-v_3&s&v_1\\-v_3&v_2&-v_1&s
\end{array}\right].
\end{equation}

\subsubsection{Applied Forces}
\label{sec:applied-forces}
In the dynamic model fitting process, the data are transformed into an
externally applied force distribution $\vf(\ru,t)$.
We convert the external forces to
generalized forces $\vf_{q}$ which act on the 
generalized coordinates of the
model \cite{TER91}. 
We apply forces to the models based on differences between the model's
projection in the image and the image data. Each of these forces corresponds
to the appropriate generalized coordinate that has to be adapted so that the
model fits the data. Given that our vocabulary of primitives is limited,
we devise a systematic way of computing the
generalized forces for each primitive. 
The computation depends on the influence of
particular parts of the projected image on the model degrees of freedom.
Such parts correspond to the image faces (grouped to form an aspect)
provided by the qualitative shape extraction. In the case of
occluded primitives, resulting in both occluded aspects and occluded
faces, only those portions (boundary groups) of the faces used to
define the faces exert external forces on the models.

For each of the three projection models, we 
compute the generalized forces $\vec f_q$
from 2D image forces $f$, using the following formula:
\begin{equation}
\vec f_q\tpose=\int\vec f\tpose\mat L_k\dru=(\vec f_{q_c}\tpose,\vec f_{q_{\theta}}\tpose,\vec f_{q_s}\tpose),
\end{equation}
where $k=o$ or $k=p$, depending on whether we assume 
orthographic or perspective 
projection, respectively.
For orthographic projection, we assign forces from image data points 
to points
on the model that lie on a particular region of the model defined 
by the qualitative shape recovery.
For the case of perspective projection, we assign forces from image data points
to points
on the model that, in addition to satisfying the above property, 
are near occluding boundaries, thus satisfying the following formula:
\begin{equation}
|\vec i \cdot \vec n|<\tau,
\end{equation}
where $\vec n$ is the unit normal at any model point, $\vec i$ is the 
unit vector
from the focal point to a point on the model, and $\tau$ is a small threshold.

\subsubsection{Model Initialization}
One of the major limitations of previous deformable model fitting
approaches is their dependence on model 
initialization and prior segmentation \cite{TER88,TER91,PEN91a}. Using
the qualitative shape recovery process as a front end, 
we first segment the image into parts,
and for each part, we identify the relevant non-occluded contour data belonging
to the part. In addition, the extracted qualitative primitives explicitly
define a mapping between the image faces in their projected aspects and the
\mbox{3-D} surfaces on the quantitative models. 
Finally, although the initial model can be specified at any 
position and orientation,
the aspect that
a primitive encodes defines a qualitative orientation that can be exploited
to speed up the model fitting process.
Sensitivity of the fitting process to model initialization is also
overcome by independently solving for the degrees of freedom of the model.
By allowing each face in an aspect to exert forces on only one model
degree of freedom at a time, we remove local minima from the fitting
process and ensure correct convergence of the model.
\section{Experiments}
\label{sec:results}
To illustrate the shape recovery approach,
consider the real image of
a toy table lamp, as shown in Figure~\ref{fig:lamp-image}; 
the results of the bottom-up (unexpected)
qualitative shape recovery algorithm are shown in 
Figure~\ref{fig:qualitative-shape}.
At the top, the image window contains the
contours extracted from the image, along with the face numbers.
To the left is a window
describing the recovered primitives (primitive covering).
The mnemonics, PN, PL, and PP, refer to primitive number (simply an
enumeration of the primitives in the covering), primitive label (see 
Figure~\ref{fig:object-representation}(a)), and primitive probability,
respectively.
The mnemonics AN, AL, AP, and AS refer to the aspect number
(an enumeration), aspect label (see \cite{DIC92a}), aspect probability, and
aspect score (how well aspect was verified), respectively.
The mnemonics FN, FL, FP, and PS refer to face number (in image window),
face label (see \cite{DIC92a}), face probability, and corresponding
primitive attachment surface (see \cite{DIC92a}), respectively,
for each component face of the aspect.
\begin{figure}
\vspace{3.0in}
\special{psfile=/work/sven/talk/lamp5.ps hoffset=140 voffset=0 hscale=70 vscale=70}
\caption{Image of a Table Lamp (256 x 256)}
\label{fig:lamp-image}
\end{figure}
\begin{figure}
\hspace{2.55in}
\epsfysize=4.0in
\leavevmode\epsfbox{/work/sven/talk/lamp-di.eps}
\vspace{0.1in}
\caption{Recovered Qualitative Primitives}
\label{fig:qualitative-shape}
\end{figure}

To illustrate the fitting stage, consider the contours belonging to the
lamp shade (truncated cone). Having determined during the qualitative shape
recovery stage that we are trying to fit a deformable superquadric to
a truncated cone, we can immediately fix some of the parameters in
the model. In addition, the qualitative shape recovery stage provides
us with a mapping between faces in the image and physical surfaces on
the model. For example, we know that the elliptical face (FN 1) maps
to the top of the truncated cone, while the body face (FN 0) maps to
the side of the truncated cone. For the case of the truncated cone,
we will begin with a cylinder model (superquad) and will
compute the forces that will deform the cylinder into the truncated
cone appearing in the image.
Assuming an orthographic projection, and that the $x$ and $y$ 
dimensions are equal, we
compute the following forces:
\begin{enumerate}
\item The cylinder is initially oriented with its $z$ axis orthogonal
to the image plane. The first step involves computing the centroid of
the elliptical image face (known to correspond to the top of the
cylinder). The distance between the centroid and the projected center
of the cylinder top is converted to a force which translates the
model cylinder. Figure~\ref{fig:quantitative-shape}(a) 
shows the image contours
corresponding to the lamp shade and the cylinder following application
of this force. Figure~\ref{fig:quantitative-shape}(b) 
shows a different view of the
image plane, providing a better view of the model cylinder.
\item The distance between the two image points corresponding to the 
extrema of the principal axis of the elliptical image face
and two points that lie
on a diameter of the top of the cylinder is 
converted to a force affecting the $x$ and $y$ dimensions
with respect to the model cylinder. 
Figures~\ref{fig:quantitative-shape}(c) and 
\ref{fig:quantitative-shape}(d)
show the image and the cylinder following application of this force.
\item The distance between the projected model contour corresponding
to the top of the cylinder and the elliptical image face
corresponds to a force affecting
the orientation of the cylinder. Figures~\ref{fig:quantitative-shape}(e) and 
\ref{fig:quantitative-shape}(f)
show the image and the cylinder following application of this force. This
concludes the application of forces arising from the elliptical image
face, i.e., top of the truncated cone.
\item Next, we focus on the image face corresponding to the body of the
truncated cone to complete the fitting process. The distance 
between the points along the bottom rim of the body face and the 
projected bottom rim of the cylinder
corresponds to a force affecting the length of the cylinder in the
$z$ direction. Figures~\ref{fig:quantitative-shape}(g) 
and \ref{fig:quantitative-shape}(h)
show the image and the cylinder following application of this force.
\item Finally, the distance between points on the sides of the 
body face and the sides of the cylinder corresponds to a force which
tapers the cylinder to complete the fit. 
Figures~\ref{fig:quantitative-shape}(i) and 
\ref{fig:quantitative-shape}(j)
show the image and the tapered cylinder following application of this force.
\end{enumerate}
Figure~\ref{fig:initial-lamp} shows two views of the
the initial models for the lamp
stem and base, while Figure~\ref{fig:final-lamp} shows two views
of the results of fitting all three parts of the table lamp. Note that
with an orthographic projection, we must choose an arbitrary depth
for each part; in this case, the models were all initialized with the
same depth.

\begin{figure}
\makebox[3.0in][l]{
\hspace{1.0in}
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap2.ps}
}
\makebox[3.0in][l]{
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap2b.ps}
}
\makebox[3.0in][l]{\hspace{1.5in}(a)}
\makebox[3.0in][l]{\hspace{0.5in}(b)}
\makebox[3.0in][l]{
\hspace{1.0in}
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap3.ps}
}
\makebox[3.0in][l]{
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap4.ps}
}
\makebox[3.0in][l]{\hspace{1.5in}(c)}
\makebox[3.0in][l]{\hspace{0.5in}(d)}
\makebox[3.0in][l]{
\hspace{1.0in}
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap5.ps}
}
\makebox[3.0in][l]{
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap6.ps}
}
\makebox[3.0in][l]{\hspace{1.5in}(e)}
\makebox[3.0in][l]{\hspace{0.5in}(f)}
\makebox[3.0in][l]{
\hspace{1.0in}
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap7.ps}
}
\makebox[3.0in][l]{
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap8.ps}
}
\makebox[3.0in][l]{\hspace{1.5in}(g)}
\makebox[3.0in][l]{\hspace{0.5in}(h)}
\makebox[3.0in][l]{
\hspace{1.0in}
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap9.ps}
}
\makebox[3.0in][l]{
\epsfysize=1.5in
\leavevmode\epsfbox{/work/sven/spie/snap10.ps}
}
\makebox[3.0in][l]{\hspace{1.5in}(i)}
\makebox[3.0in][l]{\hspace{1.5in}(j)}
\caption{Quantitative Shape Recovery for Lamp Shade}
\label{fig:quantitative-shape}
\end{figure}

\begin{figure}
\hspace{1.0in}
\epsfysize=3.in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/lamp-init1.ps}
\epsfxsize=4.in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/lamp-init2.ps}
\caption{Initialization of Lamp Stem and Base Models}
\label{fig:initial-lamp}
\end{figure}
\begin{figure}
\hspace{1.0in}
\epsfysize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/lamp-final1.ps}
\epsfxsize=4.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/lamp-final2.ps}
\caption{Final Recovery of Table Lamp (Note that depth information is lost
in orthographic projection.)}
\label{fig:final-lamp}
\end{figure}

For the case of perspective projection, we apply our top-down
(expected) shape recovery technique
to the image in Figure~\ref{fig:block-image}. A top down search for the
best three instances of a qualitative block primitive yields the three
primitives shown in Figure~\ref{fig:qual-block} (ordered bottom to top
by score). Note that due to a
large shadow edge that resulted in the undersegmented region 12
on the triangular face of the wedge, the shape was misclassified
as a block since region 12 was classified as having opposites sides
parallel. If we apply the quantitative
recovery process to these three blocks, we obtain the models depicted
in Figures~\ref{fig:block1-sup}, \ref{fig:block2-sup}, 
and \ref{fig:block3-sup}.
\begin{figure}
\epsfxsize=4.0in
\center\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/table.ps}
\caption{Image of Blocks on a Table}
\label{fig:block-image}
\end{figure}
\begin{figure}
\hspace{2.50in}
\makebox[4.0in]{
\epsfysize=6.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/qual-blocks.ps}}
\vspace{0.25in}
\caption{The Best Three Instances of a Qualitative Block}
\label{fig:qual-block}
\end{figure}
\begin{figure}
\epsfysize=3.5in
\center\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/block3-fitted.ps}
\caption{Model Fitted to First Block}
\label{fig:block1-sup}
\end{figure}
\begin{figure}
\epsfysize=3.5in
\center\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/block2-fitted.ps}
\caption{Model Fitted to Second Block}
\label{fig:block2-sup}
\end{figure}
\begin{figure}
\epsfysize=3.5in
\center\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/block1-fitted.ps}
\caption{Model Fitted to Third Block}
\label{fig:block3-sup}
\end{figure}

Next, we apply the top-down shape recovery technique to the stereo
pair of an isolated cylinder shown in Figure~\ref{fig:stereo-pair};
the system is instructed to search for instances of a cylinder. 
The results of the
qualitative shape recovery are shown in Figure~\ref{fig:stereo-qual},
while the initialization of the independent fitting of the model
to the left and right images is shown in
Figure~\ref{fig:stereo-initial}. 
Following the scaling step, the projection of the final model
into the two images is shown in Figure~\ref{fig:final-stereo}.
In another example, we apply the top-down object
recognition algorithm to the stereo pair shown in
Figure~\ref{fig:stereo-blocks}; the system is instructed to search
for high-scoring instances of the block volume, i.e., unoccluded instances 
appearing as high-probability aspects. Two corresponding 
pairs were found in
each image and are highlighted in Figure~\ref{fig:stereo-blocks}. 
Volume score thresholds were set high so that volumes appearing
in only the most
probable aspect and with little or no occlusion were 
accepted.\footnote{The rules for fitting a superquad to a block assume that
the block appears as the most probable aspect, i.e., that aspect which
provides the maximum information about the shape of the block.} Although
the top block on the two-block stack to the right was recovered by
the algorithm, it was rejected due to the fact that, due to region 
undersegmentation, one of its faces
was merged with a face from the block below, resulting in a lower score.
For the smaller block,
Figure~\ref{fig:fit-stage} captures the stage in the fitting process
where each block is being fit independently. Projection rays pass from the
camera focal point, through the image contours, and on to
the fitted models whose initial depth is chosen arbitrarily.
The final step,
shown in Figure~\ref{fig:fit-final}, shows the two
models converging in depth. Finally, in Figure~\ref{fig:scene-model},
we can see both recovered blocks along with their relative depth.

\begin{figure}
\hspace{0.5in}
\makebox[3.0in]{
\epsfxsize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/left-cyl.ps}}
\makebox[3.0in]{
\epsfxsize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/right-cyl.ps}}
\caption{Left and Right Stereo Images of a Cylinder}
\label{fig:stereo-pair}
\end{figure}
\begin{figure}
\center\makebox[6.0in]{
\hspace{0.5in}
\epsfxsize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/qual-left-cyl.ps}
\epsfxsize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/qual-right-cyl.ps}}
\vspace{0.25in}
\caption{Qualitative Shape Recovery of Left and Right Images}
\label{fig:stereo-qual}
\end{figure}
\begin{figure}
\epsfxsize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/l-init.ps}
\epsfxsize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/r-init.ps}
\caption{Model Initialization for Quantitative Shape Recovery of Left and Right Images}
\label{fig:stereo-initial}
\end{figure}
\begin{figure}
\epsfxsize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/l1-fitted.ps}
\epsfxsize=3.0in
\leavevmode\epsfbox{/homes/orasis/map/sven/conferences/iccv93/r1-fitted.ps}
\caption{Unifying the Left and Right Models to Determine Scale and Depth}
\label{fig:final-stereo}
\end{figure}
\begin{figure}
\hspace{0.5in}
\makebox[3.0in]{
\epsfxsize=3.0in
\leavevmode\epsfbox{/work/sven/ijcv/left-blocks.ps}}
\makebox[3.0in]{
\epsfxsize=3.0in
\leavevmode\epsfbox{/work/sven/ijcv/right-blocks.ps}}
\caption{Left and Right Stereo Images of a Cluttered Table with
Corresponding Recovered Blocks Highlighted}
\label{fig:stereo-blocks}
\end{figure}
\begin{figure}
\hspace{0.5in}
\epsfxsize=7.0in
\leavevmode\epsfbox{/work/sven/ijcv/fit-stage.ps}
\caption{Independent Fitting of Models to the Smaller Block}
\label{fig:fit-stage}
\end{figure}
\begin{figure}
\hspace{0.5in}
\epsfxsize=7.0in
\leavevmode\epsfbox{/work/sven/ijcv/fit-final.ps}
\caption{Localization of Model in Depth}
\label{fig:fit-final}
\end{figure}
\begin{figure}
\hspace{0.5in}
\epsfxsize=3.0in
\center\leavevmode\epsfbox{/work/sven/ijcv/sm.ps}
\caption{Rendering of Two Fitted Blocks Showing Relative Depth}
\label{fig:scene-model}
\end{figure}
\section{Limitations}
The approach outlined in this paper is applicable to objects composed of
distinct volumetric parts devoid of surface markings or fine structural detail.
This is a limitation of the region segmentation scheme, and in order to
accommodate more realistic objects, we are
currently looking at ways in which salient regions can be abstracted
from image detail. Both the qualitative and quantitative shape representation
schemes are general. The approach supports
any set of qualitative volumetric shapes 
that can be mapped to a recoverable
viewer-centered aspect hierarchy. Moreover, any quantitative shape model
that can be defined using our physics-based framework can be 
deformed by image forces. However, it is important to note that
choosing one model will constrain the choice of the other, i.e., a
quantitative shape model must be chosen such that it accurately models
every possible instance of the qualitative shape model. Finally, it should
be noted that the systematic rules that govern the way in which a volume's
qualitative shape is used to constrain its quantitative shape recovery
are specific to each class of volume. Not only are we exploring how
such rules can be automatically extracted through reasoning about the
part's shape, but we are also looking at which degrees of freedom of the
model can be simultaneously affected by image forces.
\section{Conclusions}
The qualitative shape recovery component of the approach is able
to capture the coarse shape of objects composed of volumetric
primitives {\it without} solving for exact viewpoint and
{\it without} a precise geometric verification of image features.
For many tasks, simply identifying the class of the object is
sufficient and there may be no need to either accurately localize
the object beyond, for example,  ``over there'', or accurately describe
the shape of its components beyond, for example,
``cylinder-like''. If, however, 
we need to accurately locate (in order to manipulate) 
the object once it's been identified, or
we need to extract a more detailed shape description in order
to distinguish between subclasses of an object, then we can apply
the quantitative shape recovery component. 
The important idea is that
the processes of recognizing an object and locating it are decoupled,
and that recognition {\it does not} require accurate localization.
In addition, when localization is required, recovered qualitative shape
provides strong constraints on the fitting
of deformable models, so that the fitting procedure, supporting
orthographic, perspective, and stereo projections, is insensitive
to both occlusion and initial conditions.
\section{Acknowledgements}
The authors would like to gratefully
acknowledge the assistance of Michael Chan, Gene Amdur, Lars Olsson,
Winky Wai, Sean Culhane, James Maclean, Suzanne Stevenson, Yiming Ye, Feng Lu, 
Chris Colohan, and Martin Martin in developing 
the software used to generate the results. In addition, Sven
Dickinson would like to acknowledge the support of John Tsotsos
and of PRECARN Associates'
Institute for Robotics and Intelligent Systems, a Government of
Canada Network of Centers of Excellence.
\bibliographystyle{plain}
\bibliography{/homes/orasis/map/sven/optica/doc/optica}
\end{document}





