\documentstyle[12pt,epsf]{article}

%****************** LINE SPACING MACRO ***************************
%
%	\ls is a macro to set the spacing between lines of 
%	text. The macro takes into account the current font 
%	size when computing the dimensions for the spacing parameters.
%       The macro is called as follows:
%
%		\ls#    where # is the desired spacing (e.g., 
%			\ls1 is single spacing \ls2 is double spacing).
%
%	# can also be a real number (e.g., \ls{.5} or \ls{3.14159}).
%	If # is a real number it must be enclosed in {...} else
%	TeX will treat the "." as a parameter delimiter.
%
%----------------------------------------------------------------------

\def\ls#1{\dimen0=\fontdimen6\the\font 
          \lineskip=#1\dimen0 \advance\lineskip.5\fontdimen5\the\font
          \advance\lineskip-\dimen0 \lineskiplimit=.9\lineskip
           \baselineskip=\lineskip  \advance\baselineskip\dimen0}

%********************** END LINE SPACING MACRO ***********************

\textwidth	6.5truein
\oddsidemargin  0.0truein
\evensidemargin 0.0truein
%\topmargin	0.25truein
\topmargin     -0.05truein
\headheight     0.0truein
\headsep        0.0truein
%\footskip	0.6truein
%\footheight	0.15truein
%\itemsep       -0.1truein
%\floatsep       0.1in
%\textfloatsep   0.15in
%\intextsep      0.1in
\floatsep       0.1in
\textfloatsep   0.15in
\intextsep      0.1in
\textheight     8.0truein

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\equ}{\Leftrightarrow}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqa}{\begin{eqnarray}}
\newcommand{\eeqa}{\end{eqnarray}}
\newcommand{\beqs}{\begin{eqnarray*}}
\newcommand{\eeqs}{\end{eqnarray*}}
\newcommand{\bbf}{\begin{bf}}
\newcommand{\ebf}{\end{bf}}
\newcommand{\bdesc}{\begin{description}}
\newcommand{\edesc}{\end{description}}
\newcommand{\sparsq}{\mbox{$\sigma_{\parallel}^{2}$}}
\newcommand{\spersq}{\mbox{$\sigma_{\bot}^{2}$}}
\newcommand{\pipr}{\mbox{\boldmath $p_{i}^{\prime}$}}
\newcommand{\bfv}[1]{\mbox{${\bf #1}$}}
\newcommand{\bftv}[1]{\mbox{${\bf \tilde{#1}}$}}
\newcommand{\tA}{\mbox{${\bf \tilde{A}}$}}
\newcommand{\tW}{\mbox{${\bf \tilde{W}}$}}
\newcommand{\tz}{\mbox{${\bf \tilde{z}}$}}
\newcommand{\transp}{t}
\newcommand{\nobins}{K}	% number of color bins
\newenvironment{proof}{\begin{quote}{\bf Proof:}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newcommand{\dhist}{d_{\rm hist}}
\newcommand{\dlow}{d_{\rm low}}
\newcommand{\dmax}{d_{\it max}}
\newcommand{\davg}{d_{\rm avg}}
\newcommand{\ddiff}{d_{\rm diff}}
\newcommand{\dk}{d_k}
\renewcommand{\vec}[1]{{\bf #1}}
\renewcommand{\bftv}[1]{\tilde{\vec{#1}}}
\newcommand{\bftmat}[1]{\tilde{\mat{#1}}}
\newcommand{\avg}{{\it avg}}
\renewcommand{\tA}{\bftmat{A}}
\renewcommand{\tW}{\bftmat{W}}
\newcommand{\tU}{\bftmat{U}}
\newcommand{\tx}{\bftv{x}}
\newcommand{\ty}{\bftv{y}}
\renewcommand{\tz}{\bftv{z}}
\newcommand{\diag}{\mathop{\rm diag}}
\newcommand{\bvec}[1]{{\bf #1}}
\newcommand{\mat}[1]{{\bf #1}}
\newcommand{\pfp}{{\bf FP}}
\newcommand{\ppp}{{\bf PP}}
\newcommand{\pwp}{{\bf WP}}
\newcommand{\Acp}{{\bf A_{c}^{\prime}}}
\newcommand{\Ac}{{\bf A_{c}}}
\newcommand{\Aci}{{\bf A_{c}}^{-1}}
\newcommand{\Ainv}{{{\bf A}^{-1}}}
\newcommand{\dpr}{{d^{\prime}}}
\newcommand{\Apr}{{\bf A^{\prime}}}
\newcommand{\Tpr}{{\bf T^{\prime}}}
\newcommand{\Ppr}{{\bf P^{\prime}}}
\newcommand{\Aprinv}{{\bf A^{\prime}}^{-1}}
\newcommand{\vs}[1]{\vspace*{#1}}

\newcommand{\ffpproj}{\begin{figure}[htb]
\epsfxsize = 5.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/bchapter/fp.psfig}}
\epsfxsize = \hsize
\caption[The Perspective Projection]
{{\bf The Perspective Projection.}}
\label{fig:fpproj}
\end{figure}
}
\newcommand{\fppproj}{\begin{figure}[htb]
\epsfxsize = 5.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/bchapter/pp.psfig}}
\epsfxsize = \hsize
\caption[The Paraperspective Projection]
{{\bf The Paraperspective Projection.}}
\label{fig:ppproj}
\end{figure}
}
\newcommand{\fwpproj}{\begin{figure}[htb]
\epsfxsize = 5.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/bchapter/wp.psfig}}
\epsfxsize = \hsize
\caption[The Weak Perspective Projection]
{{\bf The Weak Perspective Projection.}}
\label{fig:wpproj}
\end{figure}
}
\newcommand{\fboxims}{\begin{figure}[bthp]
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box02.psfig}}
\epsfxsize = \hsize}
\hspace*{0.025in}
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box03.psfig}}
\epsfxsize = \hsize}
\caption[Frames 1 and 2 of the box scene.]
{{\bf Frames 1 and 2 of the box scene.}}
\label{fig:boxims}
\end{figure}
}
\newcommand{\fboximsdum}{\begin{figure}[bthp]
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box02.psfig}}
\epsfxsize = \hsize
\caption[Frame 1 of the box scene.]
{{\bf Frame 1 of the box scene.}}
}
\hspace*{0.025in}
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box03.psfig}}
\epsfxsize = \hsize
\caption[Frame 2 of the box scene.]
{{\bf Frame 2 of the box scene.}}
}
\label{fig:boxims}
\end{figure}
}
\newcommand{\fboxtwoim}{\begin{figure}[htb]
\epsfxsize = 4.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box02.psfig}}
\epsfxsize = \hsize
\caption[Frame 1 of the box scene.]
{{\bf Frame 1 of the box scene.}}
\label{fig:box2im}
\end{figure}
}
\newcommand{\fboxthreeim}{\begin{figure}[htb]
\epsfxsize = 4.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box03.psfig}}
\epsfxsize = \hsize
\caption[Frame 2 of the box scene.]
{{\bf Frame 2 of the box scene.}}
\label{fig:box3im}
\end{figure}
}
\newcommand{\fboxthreeaffw}{\begin{figure}[htb]
\epsfxsize = 4.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box03affw.psfig}}
\epsfxsize = \hsize
\caption[Frame 2 warped using the affine transformation.]
{{\bf Frame 2 warped using the affine transformation cooresponding
to the left face.}}
\label{fig:box3imaffw}
\end{figure}
}
\newcommand{\fboxthreeaffwtwo}{\begin{figure}[htb]
\epsfxsize = 4.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box03affw2.psfig}}
\epsfxsize = \hsize
\caption[Difference between frame 2 affine warped and frame 1.]
{{\bf Difference between frame 2 affine warped and frame 1.}}
\label{fig:box3affw2}
\end{figure}
}
\newcommand{\fboxaffw}{\begin{figure}[htb]
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box03affw.psfig}}
\epsfxsize = \hsize}
\hspace*{0.025in}
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\epsffile{/afs/alm/u/sawhney/docs/planep/box03affw2.psfig}
\epsfxsize = \hsize}
\caption[Frame 2 warped using the affine transformation.]
{{\bf (i) Frame 2 warped using the affine transformation cooresponding
to the left face, and (ii) Difference between frame 2 affine warped and frame 1.}}
\label{fig:boxaffw}
\end{figure}
}
\newcommand{\fboxthreelsqtwo}{\begin{figure}[htb]
\epsfxsize = 4.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box03lsq2.psfig}}
\epsfxsize = \hsize
\caption[Difference between frame 2 lsq and frame 1.]
{{\bf Difference between affine warped and general flow warped frame 2
and frame 1.}}
\label{fig:box3lsq2}
\end{figure}
}
\newcommand{\fboxsurfone}{\begin{figure}[htb]
\epsfxsize = 5.0in
\centerline{\epsffile[72 211 531 578]
{/afs/alm/u/sawhney/docs/planep/box_surf1.psfig}}
\epsfxsize = \hsize
\caption[Grided surface plot of the box.]
{{\bf Grided surface plot of the box.}}
\label{fig:boxsurf1}
\end{figure}
}
\newcommand{\fboxsurfonetc}{\begin{figure}[htb]
\epsfxsize = 3.25in
\centerline{\epsffile[72 211 531 578]
{/afs/alm/u/sawhney/docs/planep/box_surf1.psfig}}
\epsfxsize = \hsize
\caption[Grided surface plot of the box.]
{{\bf Grided surface plot of the box.}}
\label{fig:boxsurf1}
\end{figure}
}
\newcommand{\fboxsurftwo}{\begin{figure}[htb]
\epsfxsize = 5.0in
\centerline{\epsffile[63 198 540 585]
{/afs/alm/u/sawhney/docs/planep/box_surf2.psfig}}
\epsfxsize = \hsize
\caption[Grided surface plot of the box.]
{{\bf Grided surface plot of the box.}}
\label{fig:boxsurf2}
\end{figure}
}
\newcommand{\fboxsurfs}{\begin{figure}[htb]
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\epsffile{/afs/alm/u/sawhney/docs/planep/box_surf1.psfig}
\epsfxsize = \hsize}
\hspace*{0.025in}
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\epsffile{/afs/alm/u/sawhney/docs/planep/box_surf2.psfig}
\epsfxsize = \hsize}
\caption[Grided surface plot of the box.]
{{\bf Grided surface plots of the box.}}
\label{fig:boxsurfs}
\end{figure}
}
\newcommand{\fboxshdsurf}{\begin{figure}[htb]
\epsfxsize = 6.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box_dx_ax100.psfig}}
\epsfxsize = \hsize
\caption[Shaded surface plot of the box.]
{{\bf Shaded surface plot of the box.}}
\label{fig:boxshdsurf}
\end{figure}
}
\newcommand{\fboxnpflow}{\begin{figure}[htb]
\epsfxsize = 5.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box_np_flow.psfig}}
\epsfxsize = \hsize
\caption[The non-planar residual flow.]
{{\bf The non-planar residual flow.}}
\label{fig:boxnpflow}
\end{figure}
}
\newcommand{\fboxnpflowtc}{\begin{figure}[htb]
\epsfxsize = 3.0in
\centerline{\epsffile[43 25 488 342]
{/afs/alm/u/sawhney/docs/planep/box0302_affwflo_BonW.psfig}}
\epsfxsize = \hsize
\caption[The non-planar residual flow.]
{{\bf The non-planar residual flow.}}
\label{fig:boxnpflow}
\end{figure}
}
\newcommand{\fboxrawflowtc}{\begin{figure}[htb]
\epsfxsize = 3.0in
\centerline{\epsffile[43 25 488 342]
{/afs/alm/u/sawhney/docs/planep/box0302_rawflo_BonW.psfig}}
\epsfxsize = \hsize
\caption[Raw flow b/w frames 1 and 2.]
{{\bf Raw flow b/w frames 1 and 2.}}
\label{fig:boxrawflow}
\end{figure}
}
\newcommand{\fplanepfp}{\begin{figure}[htb]
\epsfxsize = 5.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/cvpr94/planep_v2.psfig}}
\epsfxsize = \hsize
\caption[Planar Parallax.]
{{\bf Two-view Planar Parallax.}}
\label{fig:planepfp}
\end{figure}
}
\newcommand{\fplanepfptc}{\begin{figure}[htb]
\epsfxsize = 3.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/cvpr94/planep_v2.psfig}}
\epsfxsize = \hsize
\caption[Planar Parallax.]
{{\bf Two-view Planar Parallax.}}
\label{fig:planepfp}
\end{figure}
}
\newcommand{\fshashuarel}{\begin{figure}[htb]
\epsfxsize = 5.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/cvpr94/shashuarel.psfig}}
\epsfxsize = \hsize
\caption[Relationship with Shashua's two-plane cross-ratio.]
{{\bf Relationship with Shashua's two-plane cross-ratio.}}
\label{fig:shashuarel}
\end{figure}
}
\newcommand{\fshashuareltc}{\begin{figure}[htb]
\epsfxsize = 3.0in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/cvpr94/shashuarel.psfig}}
\epsfxsize = \hsize
\caption[Relationship with Shashua's two-plane cross-ratio.]
{{\bf Relationship with Shashua's two-plane cross-ratio.}}
\label{fig:shashuarel}
\end{figure}
}
\newcommand{\fboxnpflowlsq}{\begin{figure}[htb]
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box_np_flow.psfig}}
\epsfxsize = \hsize}
\hspace*{0.025in}
\parbox[t]{1.5in}{
\epsfxsize = 1.45in
\centerline{\epsffile{/afs/alm/u/sawhney/docs/planep/box03lsq2.psfig}}
\epsfxsize = \hsize}
\caption[The non-planar residual flow.]
{{\bf (i) The non-planar residual flow, and 
(ii) Difference between affine warped and general flow warped frame 2
and frame 1.}}
\label{fig:boxnpflowlsq}
\end{figure}
}

% \begin{titlepage}
% \begin{center}
\title{ 3D GEOMETRY FROM PLANAR PARALLAX}
\author{
Harpreet~S.~Sawhney \\
\email{sawhney@almaden.ibm.com}\\[\baselineskip]
IBM Research Division\\
IBM Almaden Research Center, K54/K53\\
650 Harry Road\\
San Jose, CA 95120-6099\\
}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}

Deriving 3D structure in a fixed object-centered coordinate system is
an increasingly popular trend in shape from multiple views. For weak
perspective projection, this problem has been formulated and solved in
many different ways. We show that motion parallax with respect
to a planar surface is the basis of these approaches. This paper
revisits the problem of intrinsic structure derivation for the weak
and paraperspective cases. Furthermore, a new derivation of a linear
method for intrinsic 3D shape under {\em perspective projection} is
presented. It is shown that the unifying concept underlying the
computation of 3D geometry in an intrinsic coordinate system for all
projections models is that of using an arbitrary plane in the scene
(object) as a reference plane with respect to which the rest of the
scene is reconstructed. The representation is adequate for recognition
and new view generation tasks, and can also be used for complete
metric reconstruction.

\end{abstract}

\bibliographystyle{plain}
\sloppy

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
\label{sec:intro}

The trend in 3D reconstruction from image motion (or multiple views)
has rapidly moved in the past few years from camera-centered depth and
motion recovery to scene-centered shape and pose recovery. For
orthographic projection, Tomasi and Kanade~\cite{tomasi:ijcv92}
developed an elegant method for factoring image measurements of $N$
feature points over $F$ frames into $F$ camera poses with respect to a
fixed coordinate system, and $N$ 3D point coordinates in this system.
Recently, the factorization method has been generalized to {\em
paraperspective} and {\em weak perspective}
projections~\cite{poelman:tr}. These approaches were developed for
metric reconstruction over many views. For applications involving
object recognition and new view generation, it may generally be not
necessary to compute an absolute 3D reconstruction of an object;
intrinsic shape estimates up to some arbitrary transformations may suffice.

In this paper, motion parallax with respect to an arbitrary plane in
the scene is used to compute relative 3D structure of the rest of the
scene. It is shown that the parallax motion, after the motion of the
reference plane is compensated for, neatly separates into a component
involving 3D geometry and another that depends {\em only} on translation under
perspective projection, and rotation under weak perspective.
This approach presents a unified framework for
intrinsic shape estimation for all the three commonly used models of
projection, weak perspective ({\bf WP}), paraperspective ({\bf PP}) and
(full) perspective ({\bf FP}). For weak perspective projection, under
arbitrary 3D affine transformations, shape reconstruction up to a
shear and scale was presented in~\cite{koenderink91},
\cite{lee-huang}, \cite{ashashua:mit91} and \cite{daphna:ijcv93}. We
first revisit these results for {\bf WP} and {\bf PP}. Our
formulation is different in that it makes the planar (2D affine) and the
non-planar components of the image motion explicit in terms of the
view transformation and the 3D shape. It is shown that the non-planar
image motion component is dependent directly on the non-planar depth,
and rotations in depth. Recall that under {\bf WP}, rotations in depth
are the only motion components that lead to 3D structure information.

We extend the structure-from-planar-parallax idea to perspective
projection. It is shown that if the coordinate system of an arbitrary
image is warped with respect to a reference image, such that the image
motion of a given plane becomes zero, then the residual motion of all
the points not on the reference plane leads simply to 3D structure.
The non-planar residual disparity is dependent only on the
translational component of motion, and the out-of-plane depth
component in the reference view. An alternative but tedious derivation
of this result was presented in~\cite{chlee:iccv88}. This result has
strong parallels with Shashua's~\cite{ashashua:iccv93} work on
deriving {\em projective depth} from two views under any model of
projection. The relationship is shown explicitly in the paper.

Our longer term goal is to use 3D constraints in deriving object
properties in video sequences for the purposes of automated and
semi-automated annotation and analysis. The idea of planar parallax
based structure description for various models of projection presents
a framework in which from a small number of views (minimum two), an
intrinsic representation can be derived. This is possible even if the
linear camera calibration parameters are unknown, a common situation
in video annotation for videos captured off-line from a variety of
cameras. Also, in obtaining compact descriptions of a variety of
scenes, planar structures like roads, walls and buildings can be
utilized as natural reference planes.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Planar Motion Parallax}
\label{sec:planep}

The essential principle behind planar motion parallax is that if an
image coordinate system is warped so that an environmental plane is
fixated between this image and a reference image, that is the plane's
image motion is nulled, then the residual image motion can be
factorized into a component that depends only on the non--planar shape,
and another that depends only on the epipoles (i.e. only on camera
displacements and not rotation). This is called {\em planar motion
parallax}.  It is a specific instance of the well-known notion of
motion parallax. For general motion parallax, it can be shown
\cite{lhiggins-prazdny,rieger-abbv} that if two distinct points in 3D
project to the same point in an image (that is are along the same view
ray), then the difference in their image displacements due to a change
in the viewpoint (that is the projection, in another view, of the
vector joining the two) depends only on the 3D translation
(perspective) or rotation (weak perspective) between the views and the
relative depth of the 3D points. However, using the general motion
parallax may not be practical because finding coincident points in a
view is hard; for an opaque world occluding boundaries represent such
points but these may be hard to detect and computing their image
motion may be hard too.

The use of planar parallax instead is practical. Many cultural and
other scenes naturally contain a planar surface which can serve as a
coordinate system to define the structure of the rest of the scene.
For the problem of obstacle detection, Carlsson and
Eklundh~\cite{carlsson:eccv90-abbv} and
Enkelmann~\cite{enkelmann-abbv} used the specific constraint on image
flow for a {\em ground plane}. The camera motion was modeled as the
motion on the ground plane. In contrast, our method can use any arbitrary
plane in the environment, (e.g. walls, ceilings, floor etc.) and is
applicable for general rigid motion.

Figure~\ref{fig:planepfp} is a geometric depiction of planar parallax.
Given ${\bf p}$ and ${\bf p^{\prime}}$, the projections of a 3D point
in two views, and given a reference plane $S$, if the planar motion
transformation can be computed, then a virtual projection, ${\bf
p^{w}}$, corresponding to the point of intersection of the ray ${\bf
p^{\prime}}$ and $S$ can be computed. Alternatively the primed image
coordinates (${\bf p^{\prime}}$) can be warped to create an image of
points ${\bf p^{w}}$.  Then the difference between ${\bf p^{w}}$ and
${\bf p}$ in the reference view is the planar parallax motion. It is
clear from the figure that these parallax vectors are all oriented
towards the epipole ${\bf t}$ (the point of intersection of the line
connecting the two camera centers, ${\bf O O^{\prime}}$, with the
reference image plane).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Projection Models}
\label{sec:pmodels}

\ffpproj

Consider a scene represented in a fixed scene--centered coordinate system,
$(X_{w}, Y_{w}, Z_{w})$. Let $(X, Y, Z)$ represent a camera--centered
coordinate system that changes with relative motion between the camera
and the scene. A point $\bvec{P_{w}}$ in the $w$--coordinates is
represented as $\bvec{P}$ in the camera coordinates as
\beq
\bvec{P} = \mat{R}\bvec{P_{w}} + \bvec{T},
\label{eq:wtoc}
\eeq
where $\mat{R}$ is the rotation matrix and $\bvec{T}$ the translation
vector that represent the coordinate transformation between the two
coordinate systems. If $\bvec{i}^{T}$, $\bvec{j}^{T}$ and
$\bvec{k}^{T}$ are the three rows of $\mat{R}$, then the above
equation can be written componentwise, for instance for the $x$
component,
\beq
P_{x} = \bvec{i}^T \bvec{P_{w}} + T_{x}.
\label{eq:wtocith}
\eeq

\fppproj

In (full) perspective projection ({\bf FP}), depicted in
figure~\ref{fig:fpproj}, a pin--hole model of the camera is used.
Assuming that the focal length of the camera is unity, the 2D image
projection $\bvec{p}$ of ${\bf P}$ can be written componentwise as
\beq
p_{x} = \frac{P_{x}}{P_{z}} =
\frac{\bvec{i}^T \bvec{P_{w}} + T_{x}}{\bvec{k}^T \bvec{P_{w}}
+ T_{z}}, \ \ \ \ \ 
p_{y} = \frac{P_{y}}{P_{z}} = 
\frac{\bvec{j}^T \bvec{P_{w}} + T_{y}}{\bvec{k}^T \bvec{P_{w}}
+ T_{z}}.
\label{eq:fp2d}
\eeq
That is, the $x$ and $y$ 2D components are the ratios, respectively,
of the $x$ and $y$ components of $\bvec{P}$ with its $z$ component.

\fwpproj

Paraperspective ({\bf PP}) is a particular first order
approximation to {\bf FP}. If the extent of the scene/object is small
compared to its average distance from the camera, that is
$|\bvec{P_{w}}|^{2}/|P_{0_{z}}^{2} \approx 0$ ($\bvec{P_{0}}$ is the
centroid of the object in the camera coordinates), and the object is
significantly off--centered, that is,
$|\bvec{P_{w}}|^{2}/|P_{0_{z}}^{2} \ll |\bvec{P_{w}}| |T_{x}|/|P_{0_{z}}^{2}$,
$|\bvec{P_{w}}|^{2}/|P_{0_{z}}^{2} \ll |\bvec{P_{w}}| |T_{y}|/|P_{0_{z}}^{2}$,
then, the 2D projections can be approximated by~\cite{poelman:tr}
\beq
\bvec{p} = \frac{1}{T_{z}} \left(
\left[\begin{array}{c}
       \bvec{i}^{T} - \frac{T_{x}}{T_{z}}\bvec{k}^{T} \\
       \bvec{j}^{T} - \frac{T_{y}}{T_{z}}\bvec{k}^{T}
      \end{array}\right] \bvec{P_{w}} + 
\left[\begin{array}{c}
       T_{x} \\ T_{y} \end{array}\right] \right).
\label{eq:wtocpp}
\eeq
Note that \ppp\  allows for a global scale factor for all points
corresponding to the $z$ component of the centroid, and also allows
for changes in the view angle for the object. Geometrically, \ppp\  is
shown in figure~\ref{fig:ppproj}. Each point is first projected, along
the view direction of the centroid, on a frontal plane passing through
the centroid. All the projections from this frontal plane are
projected to the image plane resulting in a common scale factor.

If only the zeroth order term in the Taylor series expansion of the
perspective equations around the $z$ component of the object centroid
is significant, then the resulting projection is called the weak
perspective projection, \pwp. Geometrically (figure~\ref{fig:wpproj}),
each point is first projected along the optical axis ($z$ direction of
the camera) on to a frontal plane passing through the centroid. All
projections from this plane are then projected on to the image plane.
The projection equations are
\beq
\bvec{p} = \frac{1}{T_{z}} \left(
\left[\begin{array}{c}
       \bvec{i}^{T} \\
       \bvec{j}^{T}
      \end{array}\right] \bvec{P_{w}} + 
\left[\begin{array}{c}
       T_{x} \\ T_{y} \end{array}\right] \right).
\label{eq:wtocwp}
\eeq

For all of the models of projection above, the measured image
coordinates, ${\bf p_{c}}$, in any arbitrary coordinate system on the
image plane can be related to the true image coordinates, ${\bf p}$
through an internal camera transformation,
\beq
{\bf p_{c}} = {\bf A_{c}}{\bf p} + {\bf T_{c}},
\label{eq:intcamtr}
\eeq
where ${\bf A_{c}}$ is a $2 \times 2$ matrix representing the $x$ and
$y$ scale factors and skew, and ${\bf T_{c}}$ is the position of the
principal point on the image plane.
When this is incorporated into the projection models, the
transformation from world to the measured image coordinates is a
general perspective transformation~\cite{mundy:book}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Weak/Paraperspective Case}
\label{sec:planepwp}

The theory of planar parallax structure for {\bf WP} (affine structure
from motion) has been derived in various forms in \cite{koenderink91},
\cite{lee-huang}, \cite{ashashua:mit91} and \cite{daphna:ijcv93}. The
formulation presented here is different in that it makes the planar
(2D affine) and the non--planar components of the image motion explicit
in terms of the view transformation and the 3D shape.

For the formulation here, it is assumed that
the scene to camera coordinate transformation of
equation~\ref{eq:wtoc} involves a general 3D affine transformation
(and not just a rigid transformation).
Then the measured image
projection, ${\bf p}$, of ${\bf P}$ under {\bf WP} is
\beq
{\bf p} = {\bf A_{c}} ( {\bf A_{23}}{\bf P_{w}} + {\bf T_{xy}} ) +
{\bf T_{c}},
\label{eq:wpproj}
\eeq
where ${\bf
A_{23}}$ is the top left $2\times3$ sub--matrix of ${\bf A}$, and
${\bf T_{xy}}$ is the vector $[T_{x} \ T_{y}]^{T}$, and ${\bf A_{c}}$
and ${\bf T_{c}}$ are the internal camera parameters. Note that for
each image, the camera parameters can be different.
Clearly, the centroid
of the image projections of a set of points is the same as the projection of the
object centroid. Therefore, if ${\bf p}$ now refers to the difference
vector between an imaged point and the centroid, the above equation
can be simplified to
\beq
{\bf p} = {\bf A_{c}} {\bf A_{23}}{\bf P_{w}}. \label{eq:wpproj2}
\eeq
We can choose the scene coordinate frame to be aligned with an
arbitrary image frame, called the reference frame. In this frame, the
projection equation simplifies to
\beq
{\bf p} = {\bf A_{c}} {\bf P_{w_{xy}}}. \label{eq:wpproj2ref}
\eeq
Projections in any other arbitrary view, whose coordinates are denoted as ${\bf
p^{\prime}}$, can be written as
\beq
{\bf p^{\prime}} = {\bf A_{c}^{\prime}} {\bf A_{22}} {\bf A_{c}}^{-1} {\bf p} +
{\bf A_{c}^{\prime}} [a_{13} \ a_{23}]^{T}P_{w_{z}},
\label{eq:ptopprimewp}
\eeq
where ${\bf A_{22}}$ is the top--left $2 \times 2$ sub--matrix and
$a_{ij}$ the $ij$th element of ${\bf A}$.

If all the scene points lie on a plane ${\bf g}^{T}{\bf P_{w_{xy}}} +
P_{w_{z}} = 0$, then the relation between projections in the reference
view and an arbitrary view can be written as:
\beq
{\bf p^{\prime}} = \Acp [{\bf A_{22}} - 
 \left[\begin{array}{l}
        a_{13} \\
        a_{23}
       \end{array}\right]{\bf g}^{T}] \Aci {\bf p} \label{eq:planepwp}
\eeq
This is the well known result that projections of a plane under weak
perspective transformation are related through an affine
transformation.

Let ${\bf g}^{T}{\bf P_{w_{xy}}} + P_{w_{z}} = 0$ be a reference plane
defined in the scene coordinate system. Consider an arbitrary point
(not lying on the reference plane) in the reference view.
The view ray for this point intersects the reference plane at some
point. So, the reference image projection for both these points (the
original point and its planar intersection) is the same. 
$P_{w_{z}}$ for the arbitrary point can be
written as a sum of the z--component of the corresponding planar
point, say $P_{w_{z}}^{pl}$, and the out--of--plane z--component,
$P_{w_{z}}^{np}$. Since, the planar component satisfies
equation~\ref{eq:planepwp}, the projection relation for the arbitrary
point in two views is
\beq
{\bf p^{\prime}} =
\Acp [{\bf A_{22}} - 
\left[\begin{array}{l} a_{13} \\
                       a_{23} 
      \end{array}\right]{\bf g}^{T}] \Aci {\bf p} + 
\Acp [r_{13} \ r_{23}]^{T}P_{w_{z}}^{np}.
\label{eq:planenopwp}
\eeq
We write this more compactly as
\beq
{\bf p^{\prime}} = {\bf A_{im}}{\bf p} + Z_{np}{\bf b}
\label{eq:planenopwp2}
\eeq
where the new symbols have the obvious
correspondence with those in equation~\ref{eq:planenopwp}. The first
part of the transformation is due to the affine planar component and
the second is due to the non--planar component.
Thus, the image motion of points has been decomposed into
a planar component with respect to a reference plane in a reference
view, and an out--of--plane component. Furthermore, the non--planar
motion is decomposed into a component that depends on the relative
structure of the scene in the reference view, and another component
that depends on the view transformation. Also note that for any
arbitrary view, the vector ${\bf b}$ is fixed for all the points. So,
the non--planar vectors for each point in the view are parallel. Their
magnitude is directly proportional to the out--of--plane depth
component. If an additional reference point is chosen, then the
relative magnitude of the non--planar displacement of any other point
with respect to this reference point gives a view--invariant
representation of the structure of the scene.

In the formulation above, the scene-to-camera transformations are
arbitrary 3D affine transformations. Therefore, the
view--invariant representation of structure derived above is invariant
to general affine view transformations. Also, since the projection
transformations in equations~(\ref{eq:wtocwp}) and (\ref{eq:wtocpp})
for {\bf WP} and {\bf PP} are similar in that they have a linear and a
translational part, the above decomposition of image motion into
planar and non--planar components is valid for {\bf PP} too.

Any three points present both in the reference view and an arbitrary
view can be used to define a 2D affine transformation corresponding to
the reference plane passing through those three points. The
correspondence of a fourth point specifies the invariant structure
completely. Three coordinates are being specified from two views to
compute an invariant structure representation of the object. The
in--plane 2D affine coordinates can be computed in the reference view
itself and the third coordinate is computed using the additional view.
Alternately, if the image plane coordinate system in an arbitrary view
is warped to account for the planar 2D affine transformation of the
reference plane, then the residual motion is due only to the
non--planar structure. This represents the one parameter of scene
structure with respect to an intrinsic coordinate system of the
reference plane.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Perspective Case}
\label{sec:planepp}

\fplanepfp

In the following formulation, a reference view and any other arbitrary
view are chosen to present the motion parallax equations.
The 3D coordinate transformation between the primed coordinates, ${\bf
P^{\prime}}$, in view 2 and the reference coordinates, ${\bf P}$, in
view 1 is written as an arbitrary 3D affine transformation:
\beq
{\bf P} = {\bf A}{\bf P^{\prime}} + {\bf T} \label{eq:rigidm2}
\eeq
Let ${\bf N^{\prime^{T}}}{\bf P^{\prime}} = \dpr $ 
represent a plane in the second
coordinate system. Substituting this in the above equation, one can
write the view transformation for the plane as~\cite{hay}:
\beq
{\bf P^{w}} \ \ = \ \ 
{\bf A}[{\bf I} + {\bf A}^{-1} {\bf TN^{\prime^{T}}}/ \dpr]{\bf
P^{\prime}}
\label{eq:ptopw}
\eeq
Note that this represents the general 8--parameter projective
relationship for plane--to--plane projection.
Using the identity $[{\bf I} + \Ainv {\bf TN^{\prime^{T}}}/ \dpr ]^{-1} = 
[{\bf I} -
\beta \Ainv {\bf TN^{\prime^{T}}}/ \dpr]$ (see~\cite{hartley:cvpr93}),
where $\beta = (1 / (1 + {\bf
N^{\prime^{T}}} \Ainv {\bf T}/ \dpr ))$, 
the above relationship can be written as the
following projective transformation:
\beq
\rho{\bf p^{\prime}} \ \ = \ \ 
[{\bf I} - \beta \Ainv {\bf TN^{\prime^{T}}}/ \dpr ] \Ainv {\bf P^{w}}
\label{eq:pwtop}
\eeq
${\bf p^{\prime}}$ is the image plane vector
$(p^{\prime}_{x}, p^{\prime}_{y}, 1)$ in the
reference view, and $\rho$ is an unknown scale factor that assures
that $\rho {\bf p^{\prime}}$ lies on the reference plane. This is
shown in figure~\ref{fig:planepfp}.
Equation~\ref{eq:rigidm2} can be written in terms of ${\bf p^{\prime}}$ and an
unknown scale factor $k$ as:
\beq
{\bf P} = {\bf A}k{\bf p^{\prime}} + {\bf T} \label{eq:ptopprime}
\eeq
Substituting for ${\bf p^{\prime}}$ from equation~\ref{eq:pwtop}, after some
algebraic manipulations (using equation~(\ref{eq:ptopw})), we get:
\beq
{\bf P^{w}} \ \ = \ \ \frac{\rho}{k} [{\bf I} + {\bf TN^{T}} / \dpr ]
({\bf P} - {\bf T}) \ \ = \ \ \frac{\rho}{k} [ {\bf P} + \frac{d_{N}}{\dpr}
{\bf T} ]
\label{eq:pprimetopw}
\eeq
where ${\bf N} = \Ainv^{T} {\bf N^{\prime}}$ is the plane normal
in the reference view, and $d_{N} =  {\bf P}^{T}{\bf N} -
{\bf T}^{T}{\bf N} - \dpr $ is the perpendicular distance 
of ${\bf P}$ from the plane. In order to see that the parallax vectors
between the warped points, $ {\bf P^{w}} $, and the actual points, $
{\bf P} $, are directed towards the epipole, it is easily shown from
equation~(\ref{eq:pprimetopw}) that
\beq
{\bf T} \cdot ({\bf P^{w}} \times {\bf P}) = 0.
\label{eq:epip}
\eeq
This is a projective relationship that shows that the projection plane
normals defined by all the parallax vectors lie on a great circle on
the unit sphere, and the translation vector is normal to the plane of
this circle. Lawn and Cipolla~\cite{lawncip} use this structure of the
motion parallax field for the {\em special case} of image velocities
(closely spaced viewpoints) 
to compute the epipole. They approximate the planar flow locally as an
affine transformation. However, they do not relate the parallax field
to the intrinsic structure of the scene which is the focus of this
paper. Also, the derivation here is valid for an arbitrary view
transformation of the type in equation~(\ref{eq:rigidm2}), that
includes the case of small displacements.
We now derive the relationship between the polar parallax field
and scene structure.

Given a view ray ${\bf p^{\prime}}$ in an arbitrary view, with the knowledge
of the plane projective transformation of equation~(\ref{eq:pwtop}), the
projection of the virtual planar point (intersection of ${\bf p^{\prime}}$ with
the plane) in the reference view can be computed using
equation~(\ref{eq:pwtop}). In other words, points in any arbitrary view
can be transformed (or warped) so that they project to the
corresponding virtual planar points in the reference view.
For points that do lie on the
plane, the warping transformation leads to their real projection in
the reference view. For the non--planar points, the planar motion
parallax vector (the difference between the virtual planar projection
and the actual projection) is given by (figure~\ref{fig:planepfp}):
\beq
{\bf p} - {\bf p^{w}} = (1/(1 +
\frac{P_{z}}{d_{N}} / \frac{T_{z}}{\dpr}))
({\bf p} - {\bf t}) \label{eq:mparallax}
\eeq
where the lower case bold letters represent the respective image
vectors with their z--components unity, $d_{N}$ is as defined above.
Note that the internal
camera transformation, $({\bf A_{c}}, {\bf T_{c}})$, can be applied to
each of the image vectors, ${\bf p}, {\bf p^{w}}, {\bf t}$, in 
equation~(\ref{eq:mparallax}) without changing its form. Thus, the
equation is valid for arbitrary camera parameters that can change from
view-to-view.

A few of the steps leading to equation~(\ref{eq:mparallax}) are:
\begin{eqnarray*}
{\bf p} - {\bf p^{w}} & = & \frac{1}{P_{z}} {\bf P} - \frac{1}{P_{z}^{w}} {\bf
P^{w}} \\ 
& = & \frac{1}{P_{z}} {\bf P} - (1/(P_{z} + \frac{d_{N}}{\dpr} T_{z}))
({\bf P} + \frac{d_{N}}{\dpr} {\bf T}) \\
& = & (1/(1 +
\frac{P_{z}}{d_{N}} / \frac{T_{z}}{\dpr}))
({\bf p} - {\bf t})
\end{eqnarray*}

In equation~(\ref{eq:mparallax}), $ \dpr $, the distance of the reference
plane from the origin of the second image coordinate system, can be
replaced by $-T_{d}$, the distance of the translation vector from the
reference plane. In fact, $ \dpr = {\bf P^{\prime}}^{T} {\bf N^{\prime}}
= {\bf P}^{T} {\bf N} - {\bf T}^{T} {\bf N} = -T_{d} $. Thus,
\beq
{\bf p} - {\bf p^{w}} = (1/(1 +
\frac{P_{z}}{d_{N}} / \frac{T_{z}}{-T_{d}}))
({\bf p} - {\bf t}).
\label{eq:mparallax2}
\eeq

When $T_{z}$ is zero, the parallax equation becomes:
\beq
{\bf p} - {\bf p^{w}} = (-d_{N}/P_{z})[T_{x} \ T_{y} \ 0]^{T}
\label{eq:mparallaxnoz}
\eeq
In this case, the parallax motion vectors are all parallel, oriented
towards the epipole at infinity as in the case of weak/paraperspective
in equation~\ref{eq:planenopwp2}. How can one decide when a {\bf WP}
assumption is good enough ? Given two frames, the first being the reference
frame, say the parallax vectors turn out to be all parallel. Then, the
parallax vectors should be computed with the other frame as the
reference frame. If the parallax vectors are again parallel, then
either there is no rotation (and $ T_{z} = 0 $ translation), or {\bf
WP} is a valid assumption. The former is not an interesting special
case. The latter is true because with rotation, under perspective projection,
the epipole in the
second frame will not be at infinity, leading to parallax vectors that
have a finite focus of expansion/contraction. In contrast, for {\bf
WP}, the parallax vectors are always parallel independent of which
frame is chosen as the reference frame.

The above derivation of planar parallax is in terms of the parallax
vector between the projections of the ``pseudo-points'' corresponding
to the planar projection, and the actual projections of the points in
the reference image (figure~\ref{fig:planepfp}). A very similar
derivation with identical results but using an explicit warping of the
{\em coordinate system} of the second image frame, according to the planar
transformation with respect to the reference frame, is shown in the
appendix.

For an alternative but more tedious derivation of the above results
see~\cite{chlee:iccv88}. A geometric derivation of the planar parallax
under perspective projection result and a similar algebraic derivation
has also been recently done independently by Kumar and
Anandan~\cite{teddy:planep}.
%parts of which are to appear
% in~\cite{sawhney:bchapter}.

We have shown that the parallax vector defined with respect to an
arbitrary plane is directed towards the epipole in the reference
image. Thus, the parallax vector field is due only to the
translational component of the 3D view transformation, as is expected
of any motion parallax field. The effect of rotations on the image
motion has been eliminated by choosing a warping transformation
corresponding to a plane in the environment. In the warped coordinate
system, the motion disparity of the plane is zero. In other words, the
points on the plane have been fixated through a coordinate
transformation. The residual image motion is due only to the
non--planar component of the environment, and translational motion.
Recall that in traditional structure from motion algorithms,
decomposing the image motion into rotational and translational
components is hard because of inherent
ambiguities~\cite{adiv-pami89,kostas:cvpr93}. This problem has been
circumvented in the planar parallax approach because the rotations
affect only the plane projective transformation of
equation~(\ref{eq:ptopw}) and not the parallax motion. If the planar
transformation is not decomposed into its rotational and translational
component, then this method does not suffer from the inherent
ambiguities.

In summary, the above derivation shows that the motion parallax
vectors, defined as the residual motion vectors after the motion of a
reference plane has been subtracted, lie along the epipolar lines, and
hence all intersect at the epipole. Therefore, their direction
directly encodes the epipolar information. Furthermore, their
relative magnitude depends only on the 3D structure of the scene with
respect to the reference plane.

\subsection{View--Invariant Representation}
\label{sec:vinvrep}

The magnitude of the parallax vector is a function of the non--planar
distance, $d_{N}$ of ${\bf P}$, and the z--components of ${\bf P}$ and
${\bf T}$. Let $\eta = 1/(1 + P_{z}/d_{N}\frac{T_{z}}{d})$ be the
magnitude and let $ \tau = 1 / \eta - 1 $. If a point $P_{0}$ not lying on
the fixated plane is chosen as a reference then for any other point
$P_{i}$:
\beq
\tau_{i}/\tau{0} =
\frac{P_{i_{z}}}{d_{i_{N}}}/\frac{P_{0_{z}}}{d_{0_{N}}}
\label{eq:tauratio}
\eeq
That is, the ratio of the magnitudes of the non--planar parallax
motion components are dependent only on the relative structure of the
environmental points not lying on the reference plane. This ratio
represents a view--independent ``coordinate'' of the structure of the
environment that does not lie on the reference plane. Given any
arbitrary viewpoint, if the new view can be warped using the
transformation corresponding to the reference plane, then the relative
magnitude of the residual parallax vectors is always that given in
equation~(\ref{eq:tauratio}). Thus, fixation with respect to the
reference plane not only compensates for the effects of rotations, but
also provides an environment centered reference surface with respect
to which the complete shape of the environment can be specified.

\subsection{Affine-Invariant Reconstruction}
\label{sec:affinv}

If the internal camera parameters are known, and the 3D transformation
between views is a rigid transformation (that is, the matrix ${\bf A}$
is a rotation matrix ${\bf R}$), then the reference plane can be
reconstructed in a Euclidean frame attached to the reference view, and
subsequently the whole scene can be reconstructed. The plane can be
reconstructed in two ways: (i) by solving for the translation from the
epipolar constraint of equation~(\ref{eq:mparallax}), and then solving
for the rotation and the plane parameters from
equation~(\ref{eq:ptopw}), or (ii) by solving for the plane and motion
parameters directly from equation~(\ref{eq:ptopw})~\cite{flustman}.
The latter case may be unstable because it relies on higher order
information (more than affine) in the image displacements; these
generally are unreliable for commonly used small field-of-view
cameras~\cite{adiv-pami89}. After solving for the plane, by choosing
the ratio $\frac{P_{0_{z}}}{d_{0_{N}}}$ for a reference non-planar
point to be unity, all the other points can be reconstructed using
their respective ratios $\frac{P_{i_{z}}}{d_{i_{N}}}$ and their view
rays ${\bf p}$. In particular, say for a given point,
$\frac{P_{z}}{d_{N}} = \alpha $, then since ${\bf P} = \lambda {\bf
p}$, the two constraints define an intersection of the view ray with a
plane. This intersection defines $\lambda$ uniquely. If the reference
plane is given by ${\bf P}^{T} {\bf N} = d$, then
\beq
{\bf P} = ((\alpha d)/{\bf p}^{T} (\alpha {\bf N} - {\bf z})) {\bf p},
\label{eq:eucp}
\eeq
where ${\bf z}$ is the unit vector along the optical axis in the
reference view.

However, when the internal camera parameters are unknown, and
euclidean reconstruction is not required, then the reconstructed ${\bf
P}$ of equation~(\ref{eq:eucp}) represents the 3D geometry of the
scene up to an arbitrary 3D affine transformation. To see this,
consider that three points on the reference plane, and a fourth
reference point not on the plane have been chosen arbitrarily and
specified a set of 3D coordinates. The coordinates of these four
points are related to their true 3D coordinates (in some coordinate
system) through a 12-parameter 3D affine transformation. This is left
unspecified in the reconstruction.

Let three points on the reference plane and a non-planar reference
point, (${\bf P_{0}}$), be given some arbitrary 3D coordinates. Assume that these
coordinates define the scene points in the coordinate system of the
reference view. Thus, these coordinates are related to their true
world coordinates through a transformation
\beq
{\bf P_{c}} = {\bf A}{\bf P_{w}} + {\bf T}.
\label{eq:wtop}
\eeq
Note that the internal camera transformation, ${\bf A_{c}}, {\bf
T_{c}}$,
relating the ideal pin-hole model image coordinates to the measured
image coordinates has been absorbed in the 3D affine transformation.
The planar points define a plane ${\bf P_{c}}^{T} {\bf N} = d$.
With ${\bf P_{0}}$ and the plane thus defined, the ratio
$\frac{P_{0_{z}}}{d_{0_{N}}}$ is fixed.

For any other non-planar point (fifth and more), say, the ratio
$\frac{P_{z}}{d_{N}}$ is $\alpha$. Then, as in
equation~(\ref{eq:eucp}),
\beq
{\bf P_{c}} = ((\alpha d)/{\bf p_{c}}^{T} (\alpha {\bf N} - {\bf z})) {\bf p_{c}},
\label{eq:affp}
\eeq
defines the 3D ${\bf P_{c}}$. However, in this case, the 3D geometry
can be specified only up to an unknown affine transformation that
brings the arbitrarily selected four reference points into
registration with the known corresponding points in the scene.
Therefore, all the scenes related through a 3D affine transformation
are indistinguishable in this approach.
This is similar to the
affine and projectively invariant reconstruction methods in~\cite{ashashua:iccv93},
\cite{faugeras:projrec} and \cite{mohr:cvpr93}.

Note that in the reconstruction above using four scene points, no
explicit reconstruction of the 3D motion is required. Also, any
arbitrary view, when warped for the reference plane with respect to
the reference view, will lead to the same 3D reconstruction in a
canonical coordinate system defined by the four chosen points.

The derived representation contains the necessary representations both
for motion and structure reconstruction and matching. If the absolute
metric motion and structure information is required, then the
translation can be computed from the parallax field leading
subsequently to the rotation~\cite{chlee:iccv88} and the absolute
coordinates in any particular view reference frame. If the goal is
recognition and matching, then absolute metric structure need not be
computed. From two views, given four planar and one out--of--plane
point, the intrinsic structure representation can be computed. For
any arbitrary view, if six points (four in-plane and two out-of-plane)
can be matched, then a synthetic
image for the new viewpoint can be created using the intrinsic
structure. This can then be compared with the given view. Similarly for
new view generation, if the mapping of the six points is available,
then a new view can be created without knowing the absolute structure
and the motion between the views. For new view generation, at least two
out-of-plane points are required because the epipole needs to be
computed. The parallax vectors for the two non-planar points can be
used for this. In practice, many more parallax vectors should be used
to solve for the epipole using least-squares.

\subsection{Interpretation of the Parallax Magnitude}
\label{sec:parmag}

In particular, the three reference points on the plane can be chosen
to be the points on the reference image plane. Thus, this image plane
becomes the reference plane. Therefore, the plane normal $ {\bf N} =
{\bf z} $ and $ d = 1 $. Given these and $ \alpha $ as above,
\beq
{\bf P_{c}} = ((\alpha d)/{\bf p_{c}}^{T} (\alpha {\bf N} - {\bf z}))
{\bf p_{c}} = (1 / (1 - \frac{1}{\alpha})) {\bf p_{c}}.
\label{eq:affp2}
\eeq
Recall that the magnitude of the parallax vector from
equation~\ref{eq:mparallax2} is proportional to $ (1/(1 +
\frac{P_{z}}{d_{N}} / \frac{T_{z}}{-T_{d}})) $. $ \frac{T_{z}}{T_{d}}
$ can be conveniently set to unity to fix the overall scale. Then, the
magnitude becomes $ (1/(1 - \frac{P_{z}}{d_{N}})) $ which is the same
as $ (1 / (1 - \frac{1}{\alpha})) $ in equation~\ref{eq:affp2} because
$ \alpha = \frac{P_{z}}{d_{N}} $.
Therefore, in the coordinates of the reference image, the length of
the parallax vector is directly {\em the depth of the corresponding
point}. Of course, the structure reconstruction is valid up to an
arbitrary 3D affine transformation as shown above. This is similar to
Koenderink's~\cite{koenderink91} and Shashua's~\cite{ashashua:mit91}
affine structure from motion under weak perspective, and
Shashua's~\cite{ashashua:iccv93} projective depth under perspective
projection.

An important point to note here is that the ``affine depth'' computed
in equation~\ref{eq:affp2} does not require the explicit computation
of the epipoles as in Shashua's method.

\subsection{Relationship to Shashua's Projective Depth}
\label{sec:shashuarel}

\fshashuarel

In \cite{ashashua:iccv93}, Shashua presented an elegant method for
computing an affine/projective 3D structure invariant from two views
under perspective projection. He called this invariant the {\em
projective depth}. His method essentially computed the location of an
arbitrary scene point by defining a cross-ratio using the point, the
principal point in a reference view, and the intersection of the view
ray with two reference planes defined in the reference view coordinate
system. In the reference view all these four points project to a
single point, but in any other view, the cross-ratio can be computed
using image measurements, namely the image correspondence of the scene
point in the second view, the epipole in the second view, and the
projections of the two planar intersections. The cross-ratio is a
projective invariant. Hence, for any view, knowing the epipole and the
planar projections, the projection of any point can be reconstructed.

Figure~\ref{fig:shashuarel} depicts the relationship between our
method and that of Shashua. A point ${\bf P}$ is viewed in a reference
view and an arbitrary view with centers of projection, ${\bf O}$ and
${\bf O}^{\prime}$, respectively. Instead of using two reference
planes in the scene to define a cross-ratio, our method uses one
reference plane and the $z = 0$ plane in the reference view. So the
cross-ratio is defined using the line ${\bf P P_{w} O^{\prime} P_{s}}$
as shown in the figure. ${\bf P_{w}}$ is the intersection of the view
ray ${\bf O^{\prime} P}$ with the reference plane, and ${\bf P_{s}}$
is its intersection with the $z = 0$ plane. A cross-ratio for the
point ${\bf P}$ can be defined as $({\bf P P_{s}}/{\bf O^{\prime}
P_{s}}) / ({\bf P P_{w}} / {\bf O^{\prime} P_{w}})$. From similar
traingles in figure~\ref{fig:shashuarel}, this is exactly the ratio
$((P_{z}/T_{z}) / (d_{N} / d))$ given by the motion parallax
equation~(\ref{eq:mparallax}). The equation shows how this ratio can
be computed using the image measurements based on the planar parallax,
similar to the computation using planar projections for two reference
planes in Shashua's case.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Experimental Results}
\label{sec:results}

We demonstrate the application of planar motion parallax on images of
a rotating box. Two frames from a sequence are shown in
figures~\ref{fig:box2im} and \ref{fig:box3im}. The box was held by a
gripper and was rotated around an axis going through the opposite face
centers. The magnitude of rotation between the two frames is
approximately $4^{o}$. The background is stationary. A SONY B/W AVC-D1
camera with effective FOV 24 by 23 degrees was used to capture $512
\times 484$ images. These were reduced to $256 \times 242$ for the
experiments. The range of depths in the scene is about 550 to 700 mm.

All the processing on the images is done using direct methods
developed by the Sarnoff Research Center group~\cite{bergen:eccv92}.
No point or discrete feature correspondence is assumed. First, the
left face of the box is specified as the reference plane in the first
image (called {\em BOX1}). The second image is registered with respect
to the first using the image flow corresponding to the reference
plane. That is, the coordinate system of the {\em whole} of the second
image is transformed according to the planar flow estimate. It was
found that a general 6-parameter affine transformation was sufficient
for this.  The second image warped corresponding to the planar affine
transformation (called {\em BOX2AFFW}) is shown in
figure~\ref{fig:box3imaffw}. The difference between this warped image
and the reference image, {\em BOX1}, is shown in
figure~\ref{fig:box3affw2}. Clearly, the motion of the reference plane
has been nulled and the residual motion is only due to the parts of
the scene not lying on the reference plane. 
% Note that for this scene,
% weak perspective seems to be a good enough model because affine
% registration of the planar facet has adequately canceled the planar
% motion without the need to compute the complete planar projective
% transformation. 
For the {\em BOX} scene {\bf WP} might be a good enough model as was
noted by Daphna Weinshall in~\cite{daphna:ijcv93}.
In the difference image (figure~\ref{fig:box3affw2}),
it is apparent from the ``motion blur'' that the residual motion is
almost translatory. This is very clear when the reference image and
the difference image are shown as a sequence on a CRT display.

Subsequently, a general flow algorithm~\cite{bergen:eccv92} is applied
between the reference image and the affine warped image, {\em
BOX2AFFW}. The flow vectors are shown in figure~\ref{fig:boxnpflow}.
(Due to the display program used, the vector display is upside down.)
This process of registration using a general flow algorithm
almost completely cancels the residual translation motion as shown in
the difference image in figure~\ref{fig:box3lsq2}. The residual non-planar
motion vectors produced by this registration correspond to the
equations~(\ref{eq:planenopwp2}) and (\ref{eq:mparallax}). 
% In this
% experiment, because {\bf WP} seems to be an adequate model, the
% residual flow magnitude can be interpreted as directly proportional to
% the non-planar depth component in the reference view. 
In this case,
because all of the scene that is not on the reference plane is on one
side of it, if we plot the magnitude of flow as a function of the
image plane $xy$-coordinate system, then this will represent the
intrinsic structure of the box up to an arbitrary 3D affine
transformation. That is, the reference plane is the image plane and
the parallax magnitude is the non-planar depth with respect to this plane.
% shear corresponding
% to the reference plane, and a scale factor for the non-planar depth.
% That is, the reference plane is identified with the $xy$-plane
% resulting in a shear, and there is an unknown scale for the non-planar
% depth.
The intrinsic shape estimate is shown as a surface plot in
figures~\ref{fig:boxsurf1} and \ref{fig:boxsurf2}. A shaded plot
(whose hard copy reproduction is not too good, unfortunately) is shown
in figure~\ref{fig:boxshdsurf}. The viewpoint has been chosen to make
the computed shape fairly explicit. (All the surface plots use some
arbitrary scale and coordinate system specific to the plotting
programs.) Note that in the regions corresponding to the background,
the flow is arbitrary because the background was stationary and only
the box was moving.

The surface plots clearly show that the qualitative estimates of the
planar facets of the box and the overall shape have been recovered
fairly well. We are in the process of computing quantitative estimates
and comparing these with the ground truth. Also, we are experimenting
with more general scenes.

% FIGS IN MAIN.TEX

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Conclusions}
\label{sec:concl}

A new derivation for 3D structure estimation using planar parallax has
been presented. It is shown that this approach unifies the ideas of
intrinsic 3D structure from weak perspective and perspective
projections. It is also shown that the plane-relative depth estimate
obtained from our method is closely related to Shashua's projective depth.
Our goal is to apply these formalisms to derive relative
arrangement of objects and surfaces in scenes for the purposes of
scene annotation in video sequences and for recognition and new view
generation. Metric structure is not very important for these
applications. Thus, the plane relative derived structure (even with
unknown camera calibration) should be adequate for the tasks. We are
in the process of developing a system for more elaborate
experimentation with the formalism presented in this paper.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Acknowledgements}

Many of the ideas in this paper evolved through discussions with
Rakesh (Teddy) Kumar and P. Anandan of the David Sarnoff Research
Center, Princeton, NJ, and with R. Manmatha, a visiting student from
the University of Massachusetts, Amherst. Thanks to Chitra Dorai, a
visiting student from Michigan State University, for her help in
implementing the affine registration code. Thanks to Teddy for his
help in the experiments.

% \bibliography{/afs/alm/u/sawhney/vision/papers}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Appendix}

Let the 3D affine transformation between a point in the reference
view, ${\bf P}$, and a second view, ${\bf P^{\prime}}$, be
\beq
{\bf P^{\prime}} = {\bf A^{\prime}}{\bf P} + {\bf T^{\prime}}. 
\label{eq:rigidm2app}
\eeq
Let ${\bf N^{T}}{\bf P} = d $ 
represent a plane in the reference
coordinate system. Substituting this in the above equation, one can
write the {\em plane projective transformation} as~\cite{hay}:
\beq
\Ppr \ \ \approx \ \ [\Apr + \Tpr {\bf N}^{T}/d] {\bf P} 
\label{eq:ptoppr2}
\eeq
If the second frame's coordinate system is warped with respect to this
plane projective transformation, then the warped projective
coordinates are
\beq
{\bf P^{w}} \ \ \approx \ \ [\Apr + \Tpr {\bf N}^{T}/d]^{-1} \Ppr .
\label{eq:pprtopw2}
\eeq
This can be written as
\begin{eqnarray}
{\bf P^{w}} & \ \ \approx \ \ & [{\bf I} - \beta \Apr^{-1} \Tpr {\bf N}^{T} / d]
\Apr^{-1} \Ppr \nonumber \\
& \ \ \approx \ \ & [{\bf I} + \beta {\bf T} {\bf N}^{T} / d] \Apr^{-1} \Ppr ,
\label{eq:pprtopw3}
\end{eqnarray}
where $ \beta = 1/(1 - {\bf N}^{T} {\bf T} / d) $, and 
$ {\bf T} = - \Apr^{-1} \Tpr $ is the translation (displacement of the
second frame's origin) in the reference coordinate system.

Equation~(\ref{eq:pprtopw3}) represents the warping transform applied
to the second image coordinates to take account for the plane
projective transformation. This warping transformation will exactly
register points in the second image lying on the plane with their
projections in the reference frame. However, the points not lying on
the plane will have some residual displacement.

Substituting equation~(\ref{eq:rigidm2app}) in
equation~(\ref{eq:pprtopw3}), we get
\begin{eqnarray}
{\bf P^{w}} & \ \ \approx \ \ & [I - \beta \Apr^{-1} \Tpr {\bf N}^{T} / d]
\Apr^{-1} ({\bf A^{\prime}}{\bf P} + {\bf T^{\prime}}) \nonumber \\
& \ \ \approx \ \ & 
[{\bf I} + \beta {\bf T} {\bf N}^{T} / d] ({\bf P} - {\bf T})
\nonumber \\
& \ \ \approx \ \ & ({\bf P} + \gamma {\bf T}) ,
\label{eq:pwpt}
\end{eqnarray}
where $ \gamma = 
-1 \ + \ \beta {\bf P}^{T} {\bf N}/d \ - \ \beta {\bf T}^{T} {\bf N}/d
= ({\bf P}^{T} {\bf N} - d)/(-({\bf T}^{T} {\bf N} - d))
= d_{N} / (- T_{d}) $, $ d_{N} $ is the perpendicular distance of
$ {\bf P} $ from the plane, and $ T_{d} $ is the distance of the
translation vector $ {\bf T} $ from the plane.

Therefore,
\begin{eqnarray}
{\bf p} - {\bf p^{w}} & \ \ = \ \ & 
\frac{1}{P_{z}} {\bf P} - \frac{1}{P_{z}^{w}} {\bf P^{w}} \nonumber \\ 
& \ \ = \ \ & \frac{1}{P_{z}} {\bf P} - 
\frac{1}{P_{z} + \gamma T_{z}} ({\bf P} + \gamma {\bf T}) \nonumber \\
& \ \ = \ \ & (1/(1 + \frac{P_{z}}{d_{N}} / \frac{T_{z}}{-T_{d}}))
({\bf p} - {\bf t}) ,
\label{eq:mparallax3}
\end{eqnarray}
which is the same as the earlier derived
equation~(\ref{eq:mparallax2}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\fboxtwoim
\fboxthreeim

\fboxthreeaffw
\fboxthreeaffwtwo

\fboxnpflow
\fboxthreelsqtwo

\fboxsurfone
\fboxsurftwo
\fboxshdsurf

\end{document}

