\documentstyle[12pt]{article}
\setlength{\textwidth}{9.75 in}
\setlength{\evensidemargin}{-0.4 in}
\setlength{\oddsidemargin}{-0.4  in}
\setlength{\textheight}{7.2 in}
\setlength{\topmargin}{-1.05 in}
\setlength{\arraycolsep}{9pt}
\renewcommand{\baselinestretch}{1.0}
\newcommand{\psfuh}    {/u/vision/fuh/document/}
\newcommand{\open}{\mbox{\Large $\circ$}}
\newcommand{\close}{\mbox{\Large $\bullet$}}
\input{psfig}
\newcommand{\epsfig}[1]{\psfig{#1}}
\begin{document}
\bibliographystyle{plain}

\Huge
\begin{center}
Chapter 15 Motion and Surface Structure from Time-Varying Image Sequences
\end{center}

\LARGE
15.1 Introduction \\
Motion analysis involves estimating the relative motion of objects with respect
to each other and the camera, given two or more perspective projection
images in a time sequence. \\
real-world applications: \\
\hspace*{1cm} industrial automation and inspection, robot assembly,\\
\hspace*{1cm} autonomous vehicle navigation, biomedical engineering, \\
\hspace*{1cm} remote sensing, general 3D-scene understanding \\
object motion and surface structure recovery from:
\begin{itemize}
\item observed optic flow
\item point correspondences
\end{itemize}
=====Skip to Section 15.13.2 temporarily=====

\vspace{1cm}
15.2 The Fundamental Optic Flow Equation  \\
$(x,y,z)$: 3D point on moving rigid body \\
$(u,v)$: perspective projection on the image plane \\
$f$: camera constant \\
$(\dot{u},\dot{v})$: velocity of the point $(u,v)$ 
\[
\left (
\begin{array}{c}
u \\
v
\end{array} \right ) = \frac{f}{z} \left (
\begin{array}{c}
x \\
y
\end{array} \right )
\]
take time derivatives of both sides
\[
\left (
\begin{array}{c}
\dot{u} \\
\dot{v}
\end{array} \right ) = \frac{f}{z^2} \left (
\begin{array}{c}
z\dot{x}-x\dot{z} \\
z\dot{y}-y\dot{z}
\end{array} \right )
\]
yields the fundamental optic flow equation:
\[
\left (
\begin{array}{c}
\dot{u} \\
\dot{v}
\end{array} \right ) = \frac{1}{z} \left (
\begin{array}{ccc}
f & 0 & -u \\
0 & f & -v 
\end{array} \right ) \left (
\begin{array}{c}
\dot{x} \\
\dot{y} \\
\dot{z}
\end{array} \right )
\]
general solution: ($\lambda$ is a free variable)
\[
\left (
\begin{array}{c}
\dot{x} \\
\dot{y} \\
\dot{z}
\end{array} \right ) = \frac{z}{f} \left (
\begin{array}{c}
\dot{u} \\
\dot{v} \\
0
\end{array} \right ) + \lambda \left (
\begin{array}{c}
u \\
v \\
f
\end{array} \right )
\]

\vspace{1cm}
15.2.1 Translational Motion \\
known:
\begin{itemize}
\item $N$-point optic flow field: $\{(u_n,v_n,\dot{u}_n,\dot{v}_n)\}_{n=1}^N$
\end{itemize}
unknown:
\begin{itemize}
\item corresponding unknown 3D points: $\{(x_n,y_n,z_n)\}_{n=1}^N$
\item all points moving with same but unknown velocity $(\dot{x},\dot{y},\dot{z})$
\end{itemize}
can be solved up to a multiplicative constant

\vspace{1cm}
15.2.2 Focus of Expansion and Contraction \\
known:
\begin{itemize}
\item 3D motion is translational
\item one 2D projected point $(u,v)$ has no motion: $\dot{u}=\dot{v}=0$
\end{itemize}
thus, translational motion is in a direction along the ray of sight \\
focus of expansion (FOE): if 3D point field moving toward camera \\
FOE: motion-field vectors radiate outward from that point \\
focus of contraction (FOC): if 3D point field moving away from camera \\
FOC: vectors radiate inward toward diametrically opposite point\\
flow pattern of the motion field of a forward-moving observer \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 8.14=====

\vspace{1cm}
15.2.3 Moving Line Segment \\
known:
\begin{itemize}
\item fixed distance between two unknown 3D points $(x_1,y_1,z_1),(x_2,y_2,z_2)$
\item translational motion with common velocity $(\dot{x},\dot{y},\dot{z})$
\item corresponding optic flow: $(u_1,v_1,\dot{u}_1,\dot{v}_1),
(u_2,v_2,\dot{u}_2,\dot{v}_2)$
\end{itemize}
unknown:
\begin{itemize}
\item $(x_1,y_1,z_1),(x_2,y_2,z_2)$: two unknown 3D points
\item common velocity: $(\dot{x},\dot{y},\dot{z})$
\end{itemize}

\vspace{1cm}
15.2.4 Optic Flow Acceleration Invariant \\
since $\lambda f = \dot{z}$ \\
differentiating general solution in Sec. 15.2 and solve for $(\ddot{x},\ddot{y},
\ddot{z})$:
\[
\left (
\begin{array}{c}
\ddot{x} \\
\ddot{y} \\
\ddot{z}
\end{array} \right ) = \frac{z}{f} \left (
\begin{array}{c}
\ddot{u} \\
\ddot{v} \\
0
\end{array} \right ) + \frac{2\dot{z}}{f} \left (
\begin{array}{c}
\dot{u} \\
\dot{v} \\
0
\end{array} \right ) + \frac{\ddot{z}}{f} \left (
\begin{array}{c}
u \\
v \\
f
\end{array} \right )
\]

\vspace{1cm}
15.3 Rigid-Body Motion \\
rigid-body motion: no relative motion of points w.r.t. one another \\
rigid-body motion: points maintain fixed position relative to one another \\
rigid-body motion: all points move with the body as a whole \\
$R(t)$: rotation matrix \\
$T(t)$: translation vector \\
$p(0)$: initial position of given point \\
$R(0)=I, T(0)=0$ \\
$p(t)$: position of given point at time $t$ \\
rigid-body motion in displacement vectors:
\[
p(t) = R(t)p(0)+T(t)
\]
velocity vector: time derivative of its position:
\[
\dot{p}(t)=\dot{R}(t)p(0)+\dot{T}(t)
\]
since $p(0)=R^{-1}(t)[p(t)-T(t)]$
\[
\dot{p}(t)=\dot{R}(t)R^{-1}(t)p(t)-\dot{R}(t)R^{-1}(t)T(t)+\dot{T}(t)
\]
(a) translational-motion field under projection onto hemispherical surface \\
only translational-component motion useful in determining scene structure\\
(b) rotational-motion field under projection onto hemispherical surface \\
rotational-motion field provides no information about scene structure \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 8. 15===== 

\vspace{1cm}
\noindent
we can describe rigid-body motion in instantaneous velocity by
\[
\dot{p}(t)=\omega(t) \times p(t)+k(t)
\]
$\omega_x, \omega_y, \omega_z$: angular velocities in three axes \\
$k_x, k_y, k_z$: translational velocities in three axes \\
from rigid-body-motion equation
\[
\left (
\begin{array}{c}
\dot{x} \\
\dot{y} \\
\dot{z}
\end{array}
\right ) = \omega \times \left (
\begin{array}{c}
x \\
y \\
z
\end{array}
\right ) +k = \left (
\begin{array}{c}
\omega_x \\
\omega_y \\
\omega_z
\end{array}
\right ) \times
\left (
\begin{array}{c}
x \\
y \\
z
\end{array}
\right ) +\left (
\begin{array}{c}
k_x \\
k_y \\
k_z
\end{array}
\right ) =
\left (
\begin{array}{c}
\omega_y z - \omega_z y + k_x \\
\omega_z x - \omega_x z + k_y \\
\omega_x y - \omega_y x + k_z
\end{array}
\right )
\]
and perspective projection equation
\[
\left (
\begin{array}{c}
x \\
y \\
z
\end{array}
\right ) = \frac{z}{f} \left (
\begin{array}{c}
u \\
v \\
f
\end{array}
\right )
\]
we can determine an expression for $\dot{z}$:
\[
\dot{z} = \frac{z}{f}(\omega_x v - \omega_y u)+k_z
\]
after simplification
\[
\left (
\begin{array}{c}
\dot{u} \\
\dot{v}
\end{array}
\right ) = \left (
\begin{array}{cccccc}
\frac{f}{z} & 0 & -\frac{u}{z} & -\frac{uv}{f} & \frac{f^2+u^2}{f} & -v \\
0 & \frac{f}{z} & -\frac{v}{z} & -\frac{f^2+v^2}{f} & \frac{uv}{f} & u
\end{array}
\right ) \left (
\begin{array}{c}
k_x \\
k_y \\
k_z \\
\omega_x \\
\omega_y \\
\omega_z 
\end{array}
\right )
\]
image velocity: expressed as sum of translational field and rotational field 

\vspace{1cm}
\noindent
$(x,y,z)$: 3D coordinate before rigid-body motion in displacement vectors \\
$(x',y',z')$: 3D coordinate after rigid-body motion in displacement vectors \\
$(\theta_x,\theta_y,\theta_z)$: rotation angles in three axes \\
$(t_x,t_y,t_z)$: translation in three axes \\
rigid-body motion in displacement vectors:
\[
\left (
\begin{array}{c}
x' \\
y' \\
z' \\
\end{array}
\right ) = R(\theta_z)R(\theta_y)R(\theta_x) \left (
\begin{array}{c}
x \\
y \\
z \\
\end{array}
\right ) + \left (
\begin{array}{c}
t_x \\
t_y \\
t_z \\
\end{array}
\right ) 
\]
\large
\[
= \left (
\begin{array}{ccc}
\cos \theta_y \cos \theta_z & \sin \theta_x \sin \theta_y \cos \theta_z 
-\cos\theta_x\sin\theta_z & \cos\theta_x\sin\theta_y\cos\theta_z 
   +\sin\theta_x\sin\theta_z \\
\cos\theta_y\sin\theta_z & \sin\theta_x\sin\theta_y\sin\theta_z
   +\cos\theta_x\cos \theta_z 
& \cos\theta_x\sin\theta_y\sin\theta_z-\sin\theta_x\cos\theta_z \\
-\sin\theta_y & \sin\theta_x\cos\theta_y & \cos\theta_x\cos\theta_y 
\end{array}
\right ) \left (
\begin{array}{c}
x \\
y \\
z \\
\end{array}
\right ) + \left (
\begin{array}{c}
t_x \\
t_y \\
t_z \\
\end{array}
\right ) 
\]
\LARGE
motion in displacement vector and instantaneous velocity is different: \\
\hspace*{1cm} e.g. moon encircling earth \\
instantaneous velocity: first order approximation of displacement vector \\
first order approximation: when $\theta$ small, 
   $\sin \theta \approx \theta, \cos \theta \approx 1, 
   \sin \theta \sin \theta \approx 0$ \\
first order approximation: when time=1 thus $\dot{x}=(x'-x)/1$ \\
first order approximation: $\omega_x=\theta_x, \omega_y=\theta_y, 
   \omega_z=\theta_z, k_x=t_x, k_y=t_y, k_z=t_z$
\[   
\left (
\begin{array}{c}
x' \\
y' \\
z' \\
\end{array}
\right ) = 
 \left (
\begin{array}{ccc}
1 &  -\theta_z & \theta_y \\
\theta_z & 1 & -\theta_x \\
-\theta_y & \theta_x & 1
\end{array}
\right ) \left (
\begin{array}{c}
x \\
y \\
z \\
\end{array}
\right ) + \left (
\begin{array}{c}
t_x \\
t_y \\
t_z \\
\end{array}
\right ) = \left (
\begin{array}{c}
x-\theta_z y + \theta_y z + t_x \\
y-\theta_x z + \theta_z x + t_y \\
z-\theta_y x + \theta_x y + t_z 
\end{array}
\right ) 
\]
=====Garfield 17:26=====   


\vspace{1cm}
15.4 Linear Algorithms for Motion and Surface Structure from Optic Flow 

\vspace{1cm}
15.4.1 The Planar Patch Case \\
$p(t)=[x(t),y(t),z(t)]'$: arbitrary object point on planar patch at time $t$ \\
$[u(t),v(t)]$: central projective coordinates of $p(t)$ onto image plane $z=f$
\[
u(t) = f \frac{x(t)}{z(t)}
\]
\[
v(t) = f \frac{y(t)}{z(t)}
\]
\[
p(t) = \frac{z(t)}{f}[u(t),v(t),f]'
\]
$[\dot{u}(t),\dot{v}(t)]$: instantaneous velocity of moving image point $[u(t),v(t)]$ \\
$[u(t),v(t),\dot{u}(t),\dot{v}(t)]$: optic flow image point \\
$\omega(t)$: instantaneous rotational angular velocity \\
$k(t)$: instantaneous translational velocity \\
unit vector $n(t)$: orthogonal to moving planar patch \\
rigid planar patch motion represented by rigid-motion constraint:
\[
\dot{p}(t) = \omega (t) \times p(t) + k(t)
\]
\[
n(t)'p(t)=1
\]
from above two equations:
\[
\dot{p} = \omega \times p + k n'p
\]
let
\[
\omega = (\omega_1, \omega_2, \omega_3)',
\]
\[
\Omega = \left (
\begin{array}{ccc}
0 & -\omega_3 & \omega_2 \\
\omega_3 & 0 & -\omega_1 \\
-\omega_2 & \omega_1 & 0 
\end{array}
\right )
\]
rigid-motion constraint could be written as:
\[
\dot{p}=\Omega p +kn'p = (\Omega + kn') p
\]
denote the $3 \times 3$ matrix $\Omega + kn'$ by $W$ and its three row vectors
by $w'_1, w'_2, w'_3$ \\
$W$: called planar motion parameter matrix \\
$W+W'=kn'+nk'$ since $\Omega$ skew symmetric \\
above equation can be written as:
\[
\left (
\begin{array}{c}
\dot{x} \\
\dot{y} \\
\dot{z}
\end{array}
\right ) = W \left (
\begin{array}{c}
x \\
y \\
z
\end{array}
\right )
\]
from perspective projection equations:
\[
\left (
\begin{array}{c}
x \\
y
\end{array}
\right ) = \frac{z}{f} \left (
\begin{array}{c}
u \\
v
\end{array}
\right )
\]
taking time derivatives of these equations, we have
\[
\left (
\begin{array}{c}
\dot{x} \\
\dot{y}
\end{array}
\right ) = \frac{1}{f} \left (
\begin{array}{c}
z\dot{u}+u\dot{z} \\
z\dot{v}+v\dot{z}
\end{array}
\right )
\]
substitute equations into above equations:
\[
\left (
\begin{array}{c}
z\dot{u}+u\dot{z} \\
z\dot{v}+v\dot{z} \\
f\dot{z}
\end{array}
\right ) = z \left (
\begin{array}{c}
w'_1 \\
w'_2 \\
w'_3
\end{array}
\right ) \left (
\begin{array}{c}
u \\
v \\
f
\end{array}
\right )
\]
from third row:
\[
\dot{z} = \frac{z}{f} w'_3 \left (
\begin{array}{c}
u \\
v \\
f
\end{array} \right )
\]
substitute $\dot{z}$ to obtain optical flow-planar motion equation:
\[
\left [ \left (
\begin{array}{c}
w'_1 \\
w'_2
\end{array} 
\right ) - \frac{1}{f} \left (
\begin{array}{c}
u \\
v
\end{array} 
\right ) w'_3 \right ] \left (
\begin{array}{c}
u \\
v \\
f
\end{array} 
\right ) = \left (
\begin{array}{c}
\dot{u} \\
\dot{v}
\end{array} 
\right )
\]
we have $2N$ linear equations: $n=1,...,N$:
\[
\left [ \left (
\begin{array}{c}
w'_1 \\
w'_2
\end{array} 
\right ) - \frac{1}{f} \left (
\begin{array}{c}
u_n \\
v_n
\end{array} 
\right ) w'_3 \right ] \left (
\begin{array}{c}
u_n \\
v_n \\
f
\end{array} 
\right ) = \left (
\begin{array}{c}
\dot{u}_n \\
\dot{v}_n
\end{array} 
\right )
\]
optic flow-planar motion recovery: first solve $W$, then find $\omega, k, n$

\vspace{1cm}
15.4.2 General Case: Optic Flow-Motion Equation \\
1. set up optic flow-motion equation not involving depth information \\
2. solve it by using linear least-squares technique

\vspace{1cm}
15.4.3 A Linear Algorithm for Solving Optic Flow-Motion Equations 

\vspace{1cm}
15.4.4 Mode of Motion, Direction of Translation, and Surface Structure \\
mode of motion: whether translation $k=0$ or not \\
direction of translation: direction of $k$ \\
surface structure: relative depth when $k \neq 0$

\vspace{1cm}
15.4.5 Linear Optic Flow-Motion Algorithm and Simulation Results \\
motion and shape recovery algorithms should answer three questions:
\begin{enumerate}
\item minimum number of points to compute motion and shape
\item what set of optic flow points violate rank assumption e.g. collinearity ...
\item what's the accuracy of estimated motion from noisy optic flow?
\end{enumerate}
=====Oldie 33:74=====

\vspace{1cm}
15.5 The Two View-Linear Motion Algorithm 

\vspace{1cm}
15.5.1 Planar Patch Motion Recovery from Two Perspective Views: A Brief Review

\vspace{1cm}
Two View--Planar Motion Equation \\
imaging geometry for two view-planar motion \\
=====Fig. 15.1===== \\
rigid planar patch in motion in half-space $z < 0$ \\
$p_1 = (x_1,y_1,z_1)'$: arbitrary object point before motion \\
$p_2 = (x_2,y_2,z_2)'$: same object point after motion \\
$(u_1,v_1), (u_2,v_2)$: central projective coordinates of $p_1,p_2$ \\
$f$: camera constant
\[
u_1 = fx_1/z_1, \ \ \ v_1 = f y_1/z_1
\]
\[
u_2 = f x_2/z_2, \ \ \ v_2 = f y_2/z_2
\]
$R_0$: $3\times 3$ rotational matrix, $R'_0R_0=I, |R_0|=1$ \\
$t_0$: $3\times 1$ translational vector \\
$n_0$: $3\times 1$ normal vector \\
rigid-body-motion equation relates $p_1$ to $p_2$ as follows:
\[
p_2 = R_0 p_1 + t_0
\]
planarity constrains $p_1$ by 
\[
n'_0 p_1 = 1
\]
combining two equations produces planar rigid-body-motion-equation:
\[
p_2 = (R_0+t_0 n'_0)p_1
\]

\vspace{1cm}
15.5.2 General Curved Patch Motion Recovery from Two Perspective Views:
A Simplified Linear Algorithm \\
discard planar patch assumption, consider general curved patch

\vspace{1cm}
15.5.3 Determining Translational Orientation 

\vspace{1cm}
15.5.4 Determining Mode of Motion and Relative Depths

\vspace{1cm}
15.5.5 A Simplified Two View-Motion Linear Algorithm 

\vspace{1cm}
15.5.6 Discussion and Summary \\
when no noise appears: algorithm extremely accurate \\
when small noise appears: it works well except mode of motion incorrect

\vspace{1cm}
15.6 Linear Algorithm for Motion and Structure from Three Orthographic Views\\
Ullman (1979) showed that for the orthographic case four-point correspondences
over three views are sufficient to determine the motion and structure of the
four-point rigid configuration. \\
=====Shimon Ullman, {\em The Interpretation of Visual Motion}, ===== \\
=====The MIT Press, Cambridge, MA, 1979 ===== \\
to infer depth information: translation needed in perspective projection \\
to infer depth information: rotation useless in perspective projection \\
to infer depth information: rotation needed in orthographic projection \\
to infer depth information: translation useless in orthographic projection \\
=====depth from motion=====

\vspace{1cm}
15.6.1 Problem Formulation \\
image plane stationary, three orthographic views at time $t_1,t_2,t_3$ \\
$(x,y,z)$: object-space coordinates of point $P$ at $t_1$ \\
$(x',y',z')$: object-space coordinates of point $P$ at $t_2$ \\
$(x'',y'',z'')$: object-space coordinates of point $P$ at $t_3$ \\
$(u,v)$: image-space coordinates of $P$ at $t_1$ \\
$(u',v')$: image-space coordinates of $P$ at $t_2$ \\
$(u'',v'')$: image-space coordinates of $P$ at $t_3$ \\
$R=(r_{ij})_{3 \times 3},S=(s_{ij})_{3 \times 3}$: rotation matrix \\
$T_r=(t_{ri})_{3 \times 1},T_s=(t_{si})_{3 \times 1}$: translation vector 
\[
(x',y',z')' = R(x,y,z)'+T_r
\]
\[
(x'',y'',z'')'=S(x,y,z)'+T_s
\]
known:
\begin{itemize}
\item four image-point correspondences: \\
$(u_i,v_i)\leftrightarrow(u'_i,v'_i)\leftrightarrow(u''_i,v''_i),\ \ \ i=1,2,3,4$
\end{itemize}
unknown:
\begin{itemize}
\item $(R,T_r),(S,T_s)$
\item $(x_i,y_i,z_i),\ \ \ i=1,2,3,4$
\end{itemize}
note that with orthographic projections
\[
(u,v)=(x,y)
\]
\[
(u',v')=(x',y')
\]
\[
(u'',v'')=(x'',y'')
\]
therefore it is obvious that $t_{r3}, t_{s3}$ can never be determined \\
we are trying to determine: $R,S,t_{ri},t_{si},i=1,2, z_i-z_1,i=2,3,4$

\vspace{1cm}
15.6.2 Determining $r_{33},s_{33},(r_{13},r_{23},r_{31},r_{32}),(s_{13},s_{23},
s_{31},s_{32})$

\vspace{1cm}
15.6.3 Solving a Unique Orthonormal Matrix $R$

\vspace{1cm}
15.6.4 Linear Algorithm to Uniquely Solve $R,S,a_3$

\vspace{1cm}
15.6.5 Summary \\
Given two orthographic views, one cannot finitely determine the motion and
structure of a rigid body, no matter how many point correspondences are used,
as shown by Huang.

\vspace{1cm}
15.7 Developing a Highly Robust Estimator for General Regression

\vspace{1cm}
15.7.1 Inability of the Classical Robust M-Estimator to Render High Robustness\\
classical robust estimator, such as M-, L-, or R-estimator:
\begin{enumerate}
\item optimal or nearly optimal at assumed noise distribution
\item relatively small performance degradation with small number of outliers
\item larger deviations from assumed distribution do not cause catastrophe
\end{enumerate}
MF-estimator with new property much stronger than property 3
\begin{enumerate}
\item relatively small performance degradation with larger deviations from
      assumed distribution
\end{enumerate}

\vspace{1cm}
15.7.2 Partially Modeling Log Likelihood Function by Using Heuristics \\
MF-estimator: combine Bayes statistical decision rule with heuristics \\
MF-estimator: robust regression $\Rightarrow$ more appropriate model-fitting 

\vspace{1cm}
15.7.3 Discussion \\
M-, L-, R-, and MF-estimator: all residual based 

\vspace{1cm}
15.7.4 MF-Estimator 

\vspace{1cm}
15.8 Optic Flow-Instantaneous Rigid-Motion Segmentation and Estimation \\
formulate optic flow-single rigid-motion estimation into general regression

\vspace{1cm}
15.8.1 Single Rigid Motion 

\vspace{1cm}
15.8.2 Multiple Rigid Motions \\
=====joke=====

\vspace{1cm}
15.9 Experimental Protocol 

\vspace{1cm}
15.9.1 Simplest Location Estimation 

\vspace{1cm}
15.9.2 Optic Flow-Rigid-Motion Segmentation and Estimation 

\vspace{1cm}
15.10 Motion and Surface Structure from Line Correspondences 

\vspace{1cm}
15.10.1 Problem Formulation \\
Cartesian reference system--central projection \\
=====Fig. 15.8===== \\
$l$: line in 3D space \\
$L$: projection of the line on image plane $z=f$ \\
$z=f$: image plane \\
$\Pi$: known plane line $L$ is in; projective plane of $l$ \\
$\{l_1,...,l_K\}$: set of lines in 3D space \\
$\{l'_1,...,l'_K\}$: lines moved by rigid motion $(R',T')$ at time $t'$  \\
$\{l''_1,...,l''_K\}$: lines moved by rigid motion $(R'',T'')$ at time $t''$  \\
$\{L_1,...,L_K\},\{L'_1,...,L'_K\},\{L''_1,...,L''_K\}$: projections of lines \\
$\{\Pi_1,...,\Pi_K\},\{\Pi'_1,...,\Pi'_K\},\{\Pi''_1,...,\Pi''_K\}$; respective
projective planes \\
known:
\begin{itemize}
\item $K$ triples of line correspondences in three views \\
      $L_i\leftrightarrow L'_i \leftrightarrow L''_i, \ \ \ i = 1,...,K$
\end{itemize}
unknown:
\begin{itemize}
\item rotations and translations: $R',R'',T',T''$
\item 3D lines $l_i,i=1,...,K$
\end{itemize}

\vspace{1cm}
15.10.2 Solving Rotation Matrices $R',R''$ and Translations $T',T''$

\vspace{1cm}
15.10.3 Solving Three-Dimensional Line Structure

\vspace{1cm}
15.11 Multiple Rigid Motions from Two Perspective Views 

\vspace{1cm}
15.11.1 Problem Statement \\
imaging geometry for two-view-motion \\
=====Fig. 15.9===== \\
How many good point correspondences are needed in order to apply the
nonlinear least-squares estimator?

\vspace{1cm}
15.11.2 Simulated Experiments 

\vspace{1cm}
15.12 Rigid Motion from Three Orthographic Views 

\vspace{1cm}
15.12.1 Problem Formulation and Algorithm \\
same as Sec. 15.6, instead of linear algorithms, formulate model-fitting problem

\vspace{1cm}
15.12.2 Simulated Experiments

\vspace{1cm}
15.12.3 Further Research on the MF-Estimator \\
two problems to be solved for MF-estimator to be practically useful:
\begin{itemize}
\item distance problem
\item requirement for a good initial approximation
\end{itemize}
difficulty of motion and shape recovery: ambiguity of displacement field \\
=====Fuh, Ph.D. Thesis, Fig. 4.1=====














\vspace{1cm}
15.13 Literature Review 

\vspace{1cm}
15.13.1 Inferring Motion and Surface Structure \\
classifications for methods of inferring 3D motion and shape
\begin{itemize}
\item use of individual sets of feature points
\item use of local optic flow information about a single point
\item use of the entire optic flow field
\end{itemize}
Despite all the results obtained over the years, almost none of these inference
techniques have been successfully applied to feature-point correspondences
calculated from real imagery.

\vspace{1cm}
15.13.2 Computing Optic Flow or Image-Point Correspondences \\
problem source contains abundant information
\begin{itemize}
\item occlusion boundaries
\item specular points
\item near a focus of expansion
\item noise and digitization effects in image formation
\end{itemize}
motion parallax: apparent relative motion between objects and observer \\
points in observer's direction of translation remain relatively unchanged \\
information available to a moving observer \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 8.1===== \\
impart time dimension to image data \\
spatiotemporal image data block \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 8.2===== \\
motion field: assignment of vectors to image points representing motion \\
angular velocity of fixed scene: inversely proportional to distance \\
pilot in straight-ahead level flight on an overcast day \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 8.3===== \\
motion field of pilot looking straight ahead in motion direction \\
zero image velocity: at approach point and at infinity (along horizon) \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 8.5===== \\
motion field of pilot looking to the right in level flight \\
focus of expansion here: at infinity to the left \\
focus of contraction here: at infinity to the right of the figure \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 8.6===== \\
spatiotemporal image data acquired by a camera, ---caption--- \\
straight streaks at block top due to translating parallel to image plane \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 8.10===== 


\vspace{1in}
\begin{center}
\LARGE
B. K. P. Horn, {\em Robot Vision}, The MIT Press, Cambridge, MA, 1986. \\
\Huge
Chapter 12 Motion Field \& Optical Flow
\end{center}

\LARGE
\noindent
optic flow: apparent motion of brightness patterns during relative motion \\
arrows: represent angular velocities, which are zero directly ahead and behind\\
J. J. Gibson's example of flow induced by motion \\
=====Marr, {\em Vision}, Fig. 3-55=====

\vspace{1cm}
12.1 Motion Field \\
motion field: assigns velocity vector to each point in the image \\
$P_o$: some point on the surface of an object \\
$P_i$: corresponding point in the image \\
$v_o$: object point velocity relative to camera \\
$v_i$: motion in corresponding image point \\
$r_i$: distance between perspectivity center and image point \\
$r_o$: distance between perspectivity center and object point \\
$f'$: camera constant \\
$z$: depth axis, optic axis \\
object point displacement causes corresponding image point displacement \\
=====Horn, {\em Robot Vision}, Fig. 12.1===== \\
velocities:
\[
v_o = \frac{d r_o}{dt} {\rm \ and \ } v_i=\frac{d r_i}{dt}
\]
where $r_o$ and $r_i$ are related by
\[
\frac{1}{f'} r_i = \frac{1}{r_o \cdot \hat{z}} r_o
\]
differentiation of this perspective projection equation yields
\[
\frac{1}{f'} v_i = \frac{(r_o \cdot \hat{z})v_o - (v_o \cdot \hat{z})r_o}{
(r_o \cdot \hat{z})^2} = \frac{(r_o \times v_o)\times \hat{z}}{
(r_o \cdot \hat{z})^2}
\]
=====joke=====

\vspace{1cm}
12.2 Optical Flow \\
optical flow need not always correspond to the motion field \\
(a) perfectly uniform sphere rotating under constant illumination: \\
\hspace*{1cm} no optical flow, yet nonzero motion field \\
(b) fixed sphere illuminated by moving light source: \\
\hspace*{1cm} nonzero optical flow, yet zero motion field \\
=====Horn, {\em Robot Vision}, Fig. 12.2===== \\
apparent motion of brightness patterns: awkward concept \\
not easy to decide which $P'$ on contour $C'$ corresponds to $P$ on $C$ \\
=====Horn, {\em Robot Vision}, Fig. 12.3===== \\
optical flow: not uniquely determined by local information in changing image \\
$E(x,y,t)$: irradiance at time $t$ at image point $(x,y)$ \\
$u(x,y), v(x,y)$: $x, y$ components of optical flow vector \\
assumption: irradiance the same at time $t+\delta t$ at point $(x+\delta x, y+
\delta y)$
\[
E(x+\delta x, y+\delta y, t+\delta t)=E(x+u \delta t, y+v \delta t, t+\delta t)
=E(x,y,t)
\]
fact: motion field continuous almost everywhere \\
expand above equation in Taylor series
\[
E(x,y,t)+\delta x \frac{\partial E}{\partial x} + \delta y \frac{\partial E}{
\partial y} + \delta t \frac{\partial E}{\partial t} + e = E(x,y,t)
\]
$e$: second- and higher-order terms in $\delta x, \delta y, \delta t$ \\
cancelling $E(x,y,t)$, dividing through by $\delta t \rightarrow 0$:
\[
\frac{\partial E}{\partial x}\frac{dx}{dt}+\frac{\partial E}{\partial y}\frac{
dy}{dt}+ \frac{\partial E}{\partial t}=0
\]
which is actually just the expansion of the equation
\[
\frac{dE}{dt}=0
\]
abbreviations:
\[
u=\frac{dx}{dt}, \ \ \ v=\frac{dy}{dt},
\]
\[
E_x=\frac{\partial E}{\partial x}, \ \ \ 
E_y=\frac{\partial E}{\partial y}, \ \ \ 
E_t=\frac{\partial E}{\partial t}, 
\]
we obtain optical flow constraint equation:
\[
E_x u + E_y v + E_t = 0
\]
flow velocity $(u,v)$: lies along straight line perpendicular to intensity gradient \\
=====Horn, {\em Robot Vision}, Fig. 12.4===== \\
rewrite constraint equation:
\[
(E_x, E_y)\cdot(u,v) = - E_t
\]
aperture problem: cannot determine optical flow along isobrightness contour

\vspace{1cm}
12.3 Smoothness of the Optical Flow \\
motion field: usually varies smoothly in most parts of image \\
try to minimize a measure of departure from smoothness 
\[
e_s = \int \int ((u_x^2+u_y^2)+(v_x^2+v_y^2))dxdy
\]
error in optical flow constraint equation should be small
\[
e_c = \int \int (E_x u + E_y v + E_t)^2 dxdy
\]
overall, to minimize $e_s+\lambda e_c$:
\[
\int \int F(u,v,u_x,u_y,v_x,v_y)dxdy = \int \int (u_x^2+u_y^2)+(v_x^2+v_y^2)+
\lambda (E_x u + E_y v + E_t)^2 dxdy
\]
$\lambda$: large if brightness measurements are accurate \\
$\lambda$: small if brightness measurements are noisy

\vspace{1cm}
12.4 Filling in Optical Flow Information \\
regions of uniform brightness: optical flow velocity cannot be found locally \\
brightness corners: reliable information is available

\vspace{1cm}
12.5 Boundary Conditions \\
well-posed problem: solution exists and is unique \\
partial differential equation: infinite number of solution unless with boundary

\vspace{1cm}
12.6 The Discrete Case \\
first partial derivatives of $u,v$: can be estimated using difference \\
=====Horn, {\em Robot Vision}, Fig. 12.5=====  \\
measure of departure from smoothness:
\[
s_{i,j} = \frac{1}{4}((u_{i+1,j}-u_{i,j})^2+(u_{i,j+1}-u_{i,j})^2+
(v_{i+1,j}-v_{i,j})^2+(v_{i,j+1}-v_{i,j})^2)
\]
error in optical flow constraint equation:
\[
c_{ij}=(E_x u_{ij}+E_y v_{ij}+E_t)^2
\]
to seek set of values $\{u_{ij}\},\{v_{ij}\}$ that minimize
\[
e=\sum_i \sum_j(s_{ij}+ \lambda c_{ij})
\]
differentiating $e$ with respect to $u_{kl}, v_{kl}$:
\[
\frac{\partial e}{\partial u_{kl}} = 2 (u_{kl}-\bar{u}_{kl})+2\lambda
(E_x u_{kl} + E_y v_{kl} + E_t)E_x,
\]
\[
\frac{\partial e}{\partial v_{kl}} = 2 (v_{kl}-\bar{v}_{kl})+2\lambda
(E_x u_{kl} + E_y v_{kl} + E_t)E_y,
\]
where $\bar{u}, \bar{v}$ are local average of $u,v$ (9 neighbors?) \\
extremum occurs where the above derivatives of $e$ are zero:
\[
(1+\lambda E_x^2)u_{kl}+\lambda E_x E_y v_{kl} = \bar{u}_{kl}-\lambda E_x E_t
\]
\[
\lambda E_x E_y u_{kl} + (1+\lambda E_y^2)v_{kl} = \bar{v}_{kl}-\lambda E_y E_t
\]
determinant of $2 \times 2$ coefficient matrix:
\[
1+\lambda(E_x^2+E_y^2)=(1+\lambda E_x^2)(1+\lambda E_y^2)-\lambda^2E_x^2 E_y^2
\]
so that 
\[
(1+\lambda(E_x^2+E_y^2))u_{kl}=+(1+\lambda E_y^2)\bar{u}_{kl}-\lambda E_x E_y
\bar{v}_{kl}- \lambda E_x E_t
\]
\[
(1+\lambda(E_x^2+E_y^2))v_{kl}= -\lambda E_x E_y\bar{u}_{kl}+
(1+\lambda E_x^2)\bar{v}_{kl} - \lambda E_y E_t
\]
suggests iterative scheme such as
\[
u_{kl}^{n+1} = \bar{u}_{kl}^n - \frac{E_x \bar{u}_{kl}^n+E_y\bar{v}_{kl}^n+E_t
}{1+\lambda(E_x^2+E_y^2)} E_x
\]
\[
v_{kl}^{n+1} = \bar{v}_{kl}^n - \frac{E_x \bar{u}_{kl}^n+E_y\bar{v}_{kl}^n+E_t
}{1+\lambda(E_x^2+E_y^2)} E_y
\]
new value of $(u,v)$: average of surrounding values minus adjustment \\
=====Horn, {\em Robot Vision}, Fig. 12.6===== \\
first derivatives: estimated using first differences in $2\times 2 \times 2$ cube\\
=====Horn, {\em Robot Vision}, Fig. 12.7===== \\
consistent estimates of three first partial derivatives:
\[
E_x \approx \frac{1}{4 \delta x}(E_{i+1,j,k}+E_{i+1,j,k+1}+E_{i+1,j+1,k}+
E_{i+1,j+1,k+1})
\]
\[
-\frac{1}{4 \delta x}(E_{i,j,k}+E_{i,j,k+1}+E_{i,j+1,k}+ E_{i,j+1,k+1})
\]
\[
E_y \approx \frac{1}{4 \delta y}(E_{i,j+1,k}+E_{i,j+1,k+1}+E_{i+1,j+1,k}+
E_{i+1,j+1,k+1})
\]
\[
-\frac{1}{4 \delta y}(E_{i,j,k}+E_{i,j,k+1}+E_{i+1,j,k}+ E_{i+1,j,k+1})
\]
\[
E_t \approx \frac{1}{4 \delta t}(E_{i,j,k+1}+E_{i,j+1,k+1}+E_{i+1,j,k+1}+
E_{i+1,j+1,k+1})
\]
\[
-\frac{1}{4 \delta t}(E_{i,j,k}+E_{i,j+1,k}+E_{i+1,j,k}+ E_{i+1,j+1,k})
\]
four successive synthetic images of rotating sphere \\
=====Horn, {\em Robot Vision}, Fig. 12.8===== \\
estimated optical flow after 1, 4, 16, and 64 iterations \\
=====Horn, {\em Robot Vision}, Fig. 12.9===== \\
(a) estimated optical flow after several more iterations \\
(b) computed motion field \\
=====Horn, {\em Robot Vision}, Fig. 12.10===== 

\vspace{1cm}
12.7 Discontinuities in Optical Flow \\
discontinuities in optical flow: on silhouettes where occlusion occurs \\
=====joke=====

\vspace{1cm}
Project due April 26: \\
implementing Horn \& Schunck optical flow estimation as above \\
synthetically translate lena.im one pixel to the right and downward \\
Try $\lambda$ of 0.1, 1, 10

\end{document}
