\chapter{Affine Invariant Image Comparison}
  %\graphicspath{{/figures/}}



 If a physical object has a smooth or piecewise smooth boundary, its images  obtained by  cameras in
varying positions undergo smooth apparent deformations. These deformations are locally well approximated by affine
transforms of the image plane.

In consequence the solid object recognition  problem has often been led back to the computation of affine invariant
image local features. Such invariant features could be obtained by normalization methods, but no fully affine
normalization method exists for the time being. As a matter of fact, the scale invariance, which actually means
invariance to blur, is only dealt with by methods inspired from the scale space theory, like the SIFT method. By
simulating zooms out, this method normalizes the four translation, rotation and scale (blur) parameters, out of the six
parameters of an affine transform. Affine normalization methods like MSER or Hessian Affine normalize with respect to
all six parameters of the affine transform, but this normalization is imperfect, not dealing rigorously with blur for
MSER, or not starting with affine invariant scale space extrema for Hessian Affine.

The  method proposed in this chapter, affine SIFT (A-SIFT), simulates all image views obtainable by varying the two
camera parameters left over by the SIFT method. Then it normalizes the other four parameters by simply using the SIFT
method itself. The two additional parameters are the angles (a longitude and a latitude) defining the camera axis
orientation. Mathematical arguments will be given in Chapter \ref{TheMathematicalTheory} to prove that the resulting
method is fully affine invariant, up to an arbitrary precision.

Against any prognosis, simulating all views depending on the two camera orientation parameters is feasible with no
dramatic computational load. The method permits to reliably identify features that have undergone tilts of large
magnitude, up to 30 and more, while state-of-the-art methods do not exceed tilts of 2.5 (SIFT) or  4.5 (MSER).  This
chapter puts in evidence the role of high {\it transition tilts}: while a tilt from a frontal to an oblique view
exceeding 6 is rare, higher transition tilts are common as soon as two oblique views of an object are compared (see
Fig. \ref{hightransitiontiltsillustration}).  Thus, a fully affine invariance is required for 3D scene analysis. This
fact is substantiated by many experiments.


\begin{figure}[htbp]
\begin{center}
\begin{tabular}{c}
\includegraphics[width=8cm]{./figures/relative_tilt_MITMaga.eps} \\
\end{tabular}
\end{center}
\caption{High transition tilts\label{hightransitiontiltsillustration}}
\end{figure}


 Section \ref{AFastpresentation} gives the main decomposition formula of affine maps used throughout the paper
  and its geometric
 interpretation in terms of cameras at infinity.
 Section \ref{affinenormalizationmethods} describes and discusses a method that attempts affine invariance by
 normalization: MSER.
 Section \ref{thealgorithm} describes the A-SIFT algorithm and discusses precursors.
 Section \ref{ComputationalIssues} addresses the
   critical sampling issues for the new-simulated
 parameters in A-SIFT (tilt and longitude). It then provides a
  complexity analysis and a fast version of the method.
    Section \ref{HighTilts} presents and experiments the  crucial notion of {\it transition tilt}.



\begin{figure}[htbp]
\begin{center}
\includegraphics[width=12cm]{./figures/UccelloHostie.eps}
\end{center}
\caption{ Geometric interpretation of the Taylor formula \eqref{taylor2D}: Although the global deformation of each wall
is strongly projective (a rectangle becomes a trapezoid), the {it local deformation} is affine: each tile on the
pavement is almost a parallelogram. Indeed, projective maps are $C^1$ and therefore locally affine. The painting, due
to Uccello, is one of the first Renaissance paintings with a correct geometric perspectives following the rules
invented by Brunelleschi.} \label{fig:decomp:RTR}
\end{figure}
\section{The affine camera model\label{AFastpresentation}}

 The general (solid) shape recognition problem starts with several photographs of
a physical object, possibly taken with different cameras and view points. These digital images are the {\it query}
images. Given other digital images, the {\it search} images, the question is whether some of them contain, or not, a
view of the object taken in the query image.  A solid object's view can deform from an image to another for two obvious
reasons: First, because it underwent some physical deformation, and second, because the change of camera position
induced an apparent deformation.


Image distortions arising from viewpoint changes can be locally modeled by  affine  planar transforms, provided the
object's boundaries are piecewise smooth. In other terms, a perspective effect can be modeled by a combination of
several different affine transforms in different image regions (see Fig. \ref{multiplecamerasatinfinity}). Indeed, by
first order Taylor formula, any planar smooth deformation $(x,y)\to (X,Y)=(F_1(x,y), F_2(x,y))$ can be locally
approximated around each point $(x_0,y_0)\to (X_0,Y_0)$ by the affine map

\begin{equation}\label{taylor2D}\left(\begin{array}{c}\!\!\!X\!\!-\!\!X_0\!\!\!\\Y\!\!-\!\!Y_0
\end{array} \!\!\right)\!\! =\!\!
\left[\begin{array}{cc}
\!\!\!\frac{\partial F_1}{\partial x}(x_0,y_0) & \!\!\!\frac{\partial F_1}{\partial y}(x_0,y_0)\!\!\!  \\
\!\!\!\frac{\partial F_2}{\partial x}(x_0,y_0) & \!\!\!\frac{\partial F_2}{\partial y}(x_0,y_0)\!\!\!
\end{array} \right]
\left(\begin{array}{c}\!\!\! x\!\!-\!\!x_0\\ \!\!\!y\!\!-\!\!y_0
\end{array} \!\!\!\right)
+O\left(\begin{array}{c}
\!\!\!(x\!\!-\!\!x_0)^2+(y\!\!-\!\!y_0)^2\\\!\!\!(x\!\!-\!\!x_0)^2+(y\!\!-\!\!y_0)^2\end{array}\!\!\!
\right).\end{equation}


\begin{figure}[htbp]
\begin{center}
\begin{tabular}{c}
%\includegraphics[width=5cm]{./figures/affine_simplification2.eps}
\end{tabular}
\end{center}
\caption{Another way to understand why  the local object apparent deformations are affine.  Local planar homographies
are equivalent to multiple local cameras at infinity. Cameras at infinity generate affine deformations of planar
objects. This is true even if the object under observation is curved, because it is then locally planar. Thus, the
overall apparent deformation of the object is $C^1$, and Formula \eqref{taylor2D} applies.
\label{multiplecamerasatinfinity}}
\end{figure}


Thus, all object deformations  and all camera motions are locally approximated by affine transforms. For example, in
the case of a flat object, the deformation induced by  a camera motion  is a planar homographic transform, which is
 smooth and therefore locally tangent to affine transforms.

The converse statement is true:  {\it any affine transform with positive
 determinant
can  be interpreted as the apparent deformation induced on a planar object by a camera motion, the camera being assumed
far away from the object.} Thus, under the local smoothness assumption of the object's boundary,  the (local)
deformation model of an image $u(x,y)$ under a deformation of the object or under a camera motion is
$$u(x,y)\to u(ax+by+e, cx+dy+f),$$
where the mapping

$$\left(\begin{array}{c}x\\y
\end{array} \right) \to
\left[\!\!\!\begin{array}{cc}
a & b  \\
c & d
\end{array} \right]
\left(\begin{array}{c} x\\y
\end{array} \right)
+\left(\begin{array}{c} e\\f\end{array}\right)$$ is any affine transform of the plane with positive
 determinant.
The above statements rely on the next crucial following decomposition formula.
\begin{theorem}\label{theoremdecompositionofaffine}
 Any linear planar map whose matrix $A$  has strictly positive determinant, and which is not a similarity, has a {\it unique  decomposition}
\begin{equation} \label{decompositionofaffine}A\!=\!H_\lambda
R_1(\psi)T_tR_2(\phi)\! = \!\lambda \left[
\begin{array}{cc}
\!\!\!\cos \psi & \!\!\!-\sin \psi\!\!\! \\
\!\!\!\sin \psi & \!\!\!\cos \psi\!\!\!
\end{array} \right]
\left[
\begin{array}{cc}
\!\!t &\!\! 0 \!\!\\
\!\!0 & \!\!1\!\!
\end{array} \right]
\left[
\begin{array}{cc}
\!\!\!\cos \phi & \!\!\!-\sin \phi \!\!\!\\
\!\!\!\sin \phi & \!\!\!\cos \phi \!\!\!
\end{array} \right]
\end{equation}
 where $\lambda>0$,  $\lambda t$ is the determinant of $A$, $R_i$ are rotations, $\phi\in [0, \pi[$,  and $T_t$ is a tilt, namely a
diagonal matrix with a first eigenvalue equal to $t\geq 1$ and the second one equal to $1$. \end{theorem}

\begin{proof} Consider the real symmetric positive semi-definite matrix $A^tA$, where $A^t$
 denotes the  transposed matrix of $A$.
By classic spectral theory there is an orthogonal transform $O$ such that $A^tA=ODO^t$ where  $D$ a diagonal matrix
with ordered eigenvalues $\lambda_1\geq\lambda_2.$
 Set $O_1=AOD^{-\frac 12}.$ Then $$O_1O_1^t=AOD^{-\frac 12}D^{-\frac 12}O^tA^t=AOD^{-1}O^tA^t=A(A^tA)^{-1}A^t=I.$$
Thus, there are orthogonal matrices $O_1$ and $O$  such that
\begin{equation}\label{firstorthogonaldecomposition}A=O_1D^\frac 12O^t.\end{equation}
Since the determinant of $A$ is positive, the product of the determinants of $O$ and $O_1$ is positive.  If both
determinants are positive, then $O$ and  $O_1$ are rotations and we can write $A=R(\psi)DR(\phi)$. If $\phi$ is not in
$[0,\pi[$, changing $\phi$ into $\phi-\pi$ and $\psi$ into $\psi+\pi$  ensures that $\phi\in [0,\pi[$. If the
determinants of $O$
and $O_1$ are both negative, replacing $O$  and $O_1$ respectively by $\left(  \begin{array}{cc}  -1 & 0 \\   0 & 1 \\
\end{array} \right)O$ and $\left(  \begin{array}{cc}  -1 & 0 \\   0 & 1 \\    \end{array} \right)O_1$ makes them into
rotations without altering \eqref{firstorthogonaldecomposition}, and we can as above ensure $\phi\in [0,\pi[$ by
adapting $\phi$ and  $\psi$. The final decomposition is obtained by taking for $\lambda$ the  smaller eigenvalue of
$D^\frac 12$.
\end{proof}

\begin{exercise} The aim of the exercise is to show the uniqueness of the decomposition
\eqref{decompositionofaffine}. Assume there are two  decompositions $\lambda R_1\left[\begin{array}{cc}
\!\!t &\!\! 0 \!\!\\
\!\!0 & \!\!1\!\!
\end{array} \right] R_2=\lambda'R_1'\left[\begin{array}{cc}
\!\!t' &\!\! 0 \!\!\\
\!\!0 & \!\!1\!\!
\end{array} \right]R_2'.$   Using the uniqueness of the eigenvalues of a matrix  show first
 that $\lambda=\lambda',$ $t=t'$.
You will obtain a relation of the  form $R_1DR_2=D$ where $D$ is diagonal and $R_1$ and $R_2$ are rotations.  Deduce
from this relation that $R_1D^2R_1^t=D^2$. Deduce from this last relation the form of $R_1$, conclude carefully.
 \finex\end{exercise}



\begin{figure}[htbp]
\begin{center}
\includegraphics[width=3cm]{./figures/camera.eps}
\end{center}
\caption{ Geometric interpretation of the decomposition formula \eqref{decompositionofaffine}.} \label{fig:decomp:RTR}
\end{figure}

\begin{exercise}
 Consider two cameras looking at a flat square piece of landscape which is assimilated to an infinite resolution
 image  $u_0(x,y)$ (See Fig. \ref{fig:decomp:RTR}). The first camera is very far above the landscape and looking down perpendicularly to the landscape.

\begin{enumerate}[(i)]\setlength\itemsep{2pt}
  \item Assuming the first camera is pin-hole, show that the
 generated image is  a square image $u_0(\mu R(\psi)(x,y))$.
  Consider the coordinate system $(O, \vec i, \vec j, \vec k)$ such that
 $(\vec i, \vec j)$ are the coordinate vectors in the square image $u_0$, parallel to the image sides, and $O$ is the  image
 center.

 \item Assume a second pinhole camera has its optical axis pointing down to $O$. Assume its optical axis is
 supported by the unit vector with coordinates\linebreak $(\sin\theta \cos\phi, \sin\theta\sin\phi, \cos\theta)$. Assume again
 that this camera is very far from the square piece of landscape, so the light rays coming from the landscape to the
 camera are almost parallel. Thus the image formation on this second camera is assimilated to an orthogonal projection
 of the landscape $u_0$ onto a plane passing by the camera center $C$ and orthogonal to the optical axis.
 Taking adequate coordinates on this coordinate plane, show that the generated image is $u_0\left(R(\psi_1) T_{t_1}
 R(\phi_1)\left(
             \begin{array}{c}
              \!\! x \!\! \\
               \!\! y  \!\!\\
             \end{array}
           \right)\right)$ for some values of $\psi_1$, $\phi_1$, $t$, that you will relate to $\phi, \psi,$ and $\theta$.
\end{enumerate}
\finex
\end{exercise}

 Fig.~\ref{fig:decomp:RTR} shows a camera motion interpretation of this affine decomposition:
$\phi$ and $\theta = \arccos 1/t$ are the viewpoint angles and $\psi$ parameterizes the camera spin. Thus, this figure
illustrates the four main parameters in the affine image deformation caused by a camera motion, starting from a frontal
view $u$. The camera is assumed to stay far away from the image. The camera can first move parallel to the object's
plane: this motion induces a translation $\mathcal T$ that is not represented here. The camera can rotate around its
optical axis (rotation parameter $\psi$). Its optical axis can take a $\theta$ angle with respect to the normal to the
image plane $u$.  This parameter is called {\it latitude}. The plane containing the normal and the new position of the
optical axis makes an angle $\phi$ with a fixed vertical plane. This angle is called {\it longitude}. Last but not
least, the camera can move forward or backward. This is the zoom parameter $\lambda$. The motion of a frontal view
$\lambda=1$, $t=1$, $\phi=\psi=0$ to a slanted view corresponds to the image deformation $u(x,y)\to u(A(x,y))$ given by
\eqref{decompositionofaffine}.



\section{A-SIFT : combining simulation and normalization\label{thealgorithm}}


  The idea of combining simulation and normalization is  the main
successful ingredient of the SIFT method. This method normalizes rotations and translations, but simulates all zooms
out of the query and of the search images. Because of the feature, it is the only fully scale invariant method.





A-SIFT simulates with enough accuracy {\it all} distortions caused by a variation of the direction of the optical axis
of a camera (two parameters).  Then it normalizes the other four by the SIFT method, or any other method that is
rotation, translation, and scale invariant. More specifically, the method proceeds by the following steps.
 (See Fig. \ref{fig:CAffine:algo}.)


\subsection*{A-SIFT algorithm}
 \begin{enumerate}

 \item Each image is transformed by  simulating all possible affine distortions caused by the change of orientation of
 the camera axis of camera from a frontal position. These distortions depend upon two parameters: the longitude
 $\phi$ and the latitude $\theta$. The images undergo $\phi$-rotations followed by tilts  with parameter
 $t=|\frac 1{\cos \theta}|$  (a tilt by $t$ in the direction of $x$ is  the operation $u(x,y)\to u(tx,y)$).  For
 digital images, the tilt is performed as $t$-subsampling, and therefore requires the previous application of
  an antialiasing filter in the direction of $x$, namely the convolution by a gaussian with standard
 deviation $c\sqrt{t^2-1}$. For good antialiasing, $c\simeq 0.8$, see Chapter \ref{blurassumption}.

 \item These rotations and tilts are performed for a finite and small number of latitudes and longitudes, the sampling
 steps of these parameters ensuring that the simulated images keep close to any other possible view generated by
 other values of $\phi$ and $\theta$.


\item All simulated images are compared by SIFT.

\item To be more specific, the latitudes $\theta$ are such that the associated tilts follow a geometric series $1$, $a$, $a^2$,
, $\dots$, $a^n$, with $a>1$. The choice $a=\sqrt{2}$ is a good compromise between accuracy and sparsity. The value $n$
can go up to 6 or more, if the tilts are simulated on the query and the searched image, and up to 10 and more if the
tilts are simulated on one image only. That way, transition  tilts going up to 64 and more can be explored.

\item The longitudes $\phi$ are for each tilt an arithmetic series $0$,  $b/t$, $\dots$, $kb/t$, where $b\simeq
72^\circ$ seems again a good compromise, and $k$ is the last integer such that $kb/t<180^\circ$.

\end{enumerate}


\begin{figure}[htbp]
\begin{center}
\begin{tabular}{c}
\includegraphics[width=9cm]{./figures/brevet_fig5.eps} \\
\end{tabular}
\end{center}
\caption{Overview of the A-SIFT algorithm. The square images A and B  represent the compared images $\bu$ and $\bv$.
A-SIFT simulates arbitrary camera changes of direction by applying rotations followed by a tilts to both  images. The
simulated images, represented by the parallelograms, are then compared with an image matching algorithm like SIFT, that
is invariant to similarity transformations, i.e., invariant to scale change, rotation and translation.}
\label{fig:CAffine:algo}
\end{figure}

\section{High transition tilts\label{HighTilts}}
Equation \eqref{decompositionofaffine} and its geometric interpretation in Fig.~\ref{fig:decomp:RTR} are crucial to the
scopes of this study. This last figure associates any linear map $A$ with positive singular eigenvalues with the planar
deformation $u(A(x,y))$ of a frontal view $u(x,y)$, when the camera changes position. The parameter $\lambda$
corresponds to a change of scale. The non critical translation parameter has been eliminated by assuming that the
camera axis meets the image plane at a fixed point. Let us  now consider the case where {\it two} camera positions, not
necessarily frontal are at stake, corresponding to two different linear  maps $A$ and $B$. (Again, the translation
parameter is left out of the discussion by fixing the intersection of the camera axis with image plane.) This physical
situation is the generic one; when taking several snapshots of a scene, there is no particular reason why objects would
be taken frontally. The resulting images  are $u_1(x,y)= u(A(x,y))$ and $u_2(x,y)=u(B(x,y))$. Let us now take one of
these images as {\it reference image},
  and the other one as search image.


\begin{figure}[htbp]
\begin{center}
\includegraphics[width=8cm]{./figures/brevet_fig1_english.eps}
\end{center}
\caption{Illustration of the difference between absolute tilt and transition tilt.} \label{fig:tilt:transition}
\end{figure}

\begin{definition} Given two  views of a planar image, $u_1(x,y)=u(A(x,y))$  and $u_2(x,y)=u(B(x,y))$,
we call transition tilt $\tau (u_1,u_2)$  and transition rotation $\phi(u_1,u_2)$   the unique  parameters such that
\begin{equation} \label{decompositionofaffinerelative}BA^{-1}=H_\lambda
R_1(\psi)T_\tau R_2(\phi),
\end{equation}
 with  the notation of Formula \eqref{decompositionofaffine}.
\end{definition}
It is an easy check that the transition tilt is symmetric, namely $\tau(u_1,u_2)=\tau(u_2,u_1).$
 Fig.~\ref{fig:tilt:transition} illustrates the
affine transition between two images taken from different viewpoints, and in particular the difference between absolute
tilt and transition tilt. The camera is first put in two positions corresponding to absolute  tilts $t$ and $t'$,  but
with $\phi = \phi'$. The
 transition tilt between the resulting  images $v$ and $v'$ is $\tau=t'/t$, assuming $t'=\max (t',t)$.
  On the second illustration of
 Fig.~\ref{fig:tilt:transition}, the tilts are made in two orthogonal directions: $\phi = \phi'+{\pi/2}$. Then an
 easy calculation shows that
 the transition tilt   between $v$ and $v'$
 is the product $\tau(v,  v')= tt'$. Thus, {\it two moderate absolute tilts can lead to a large transition tilt!}
  In the first case
 considered in the figure,
  the transition tilt
 is $\sqrt{3}$ and therefore smaller than the absolute tilts. In the second case, the tilt is $tt'=8$.
 Since in realistic cases the tilt can go up to 6 or even 8,  is easily understood that the {\it transition tilt}
  can go up to 36, 84, and more.



  \begin{exercise} The aim of the exercise is to prove that, given two views $u=Au_0$ and $v=Bu_0$ of a same image, with
absolute tilts $s$ and $t$ satisfying $t\geq s$, the transition tilt $\tau=\tau(BA^{-1})$ between $u$ and $v$ satisfies
$\frac ts\leq\tau\leq st$.
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item  Set $A=H_\lambda Q_1T_sQ_2$  and  $B=H_\mu R_1T_sR_2$, where $Q_1$, $Q_2$, $R_1$, $R_2$ are rotations,
$H_\lambda$ and $H_\mu$ homotheties and $T_s$ and $T_t$  tilts with $t\geq s$. Show first that
$\tau(BA^{-1})=\tau(T_tR_2Q_2^{-1}T_s^{-1}).$

\item  Deduce that if $Q_2=R_2$, then $\tau(BA^{-1})=\frac ts.$

\item Deduce also that if  $R_2Q_2^{-1}=R(\frac \pi 2)$ then $\tau(BA^{-1})=st$.

\item  Set $R(\phi)=R_2Q_2^{-1}$. Thus $\tau(BA^{-1})=\tau(C),$ with $C=:T_tR(\phi)T_{s^{-1}}$
  Compute the matrix $C^tC$. Check that its determinant is $det(C^tC)=t^2s^{-2}$ and that its trace is
  $tr(C^tC)=(s^{-2}-1)(t^2-1)\cos^2\varphi + s^{-2}+t^2.$

\item Show that the eigenvalues $\lambda_1\geq \lambda_2$ of $C^tC$
 satisfy $\frac {t^2}{s^2}\leq \frac{\lambda_1}{\lambda_2}
\leq t^2s^2.$

\item Conclude.
   \end{enumerate}
\finex
  \end{exercise}
Each recognition method can be characterized by its transition tilt, namely the variation in relative observation angle
compatible with recognition.  Fig. \ref{fig:RecogSphere} shows the regions of the observation half sphere that can be
attained for a given transition tilt, from a fixed viewpoint with various tilts.
 This figure shows perspective and zenith views of the observation half
sphere. The central point of the bright region on the observation sphere is the original viewpoint from which an image
has been taken. The rest of the bright region depicts the attainable observation region, namely the subset of the
observation half sphere for which recognition succeeds for the given transition tilt.
  The latitude angle of the first image is  respectively $\theta = 45,\; 60, \;70,\;
80^\circ$ that correspond respectively to the absolute tilts $t=\sqrt{2},\; 2, \;2.9,\; 5.8$. The  three  columns show
the attainable regions on the half sphere for transition tilts $t<2.5,\; 5,\;$, and $ 40$. From the strong $80^\circ$,
latitude, it needs a $\tau=40$ transition tilt to attain the rest of the sphere! SIFT and MSER only attain small
regions.

Fig.~\ref{fig:numeric:CSIFT:extreme:tilt} shows the A-SIFT results for a pair of images under orthogonal viewpoints
(transition rotation $\phi=90^\circ$) that leads to an extreme transition tilt $t \approx 37$. This is not at all an
exceptional situation. It just so happens that the object's planar surface is observed at the same latitude by both
views with a tilt $t\simeq t'\simeq 6$. This figure shows two snapshots of a magazine lying on a table, not even really
flat, and with a non lambertian surface plagued with reflections. The difference of longitudes being about 90 degrees,
the transition tilt between both images is surprisingly high: $\tau=tt'\simeq 37$. Thus, it is many times larger than
the transition tilt attainable with SIFT or MSER. A-SIFT finds 120 matches out of which only 4 are wrong.


% MSER images
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{c}
\includegraphics[width=10cm]{./figures/MagaMIT_tilt6p37vs0p17.eps}
\vspace{-2ex}
\\
\includegraphics[width=10cm]{./figures/MagaMIT_tilt6p37vs0p17_CAffine2sides_tmax8_tk_sqrt2_MR_fs1_ratio0p4_0p55_94matches.eps}
\\
\end{tabular}
\end{center}
\caption{Top: Image pair with transition tilt $t \approx 37$. (SIFT,
Harris-Affine, Hessian-Affine and MSER fail completely.) Bottom:
A-SIFT finds 120 matches out which 4 are false. See comments in
text.} \label{fig:numeric:CSIFT:extreme:tilt}
\end{figure}

 The relevance of the notion of transition
 tilt is  corroborated by the fact that the highest transition tilt $\tau_{max}$ permitting to match
 two images with absolute tilts $t$ and $t'$ is fairly independent from $t$ and $t'$.
 It has been experimentally checked that for SIFT $\tau_{max}\simeq 2.5$ and for MSER $\tau_{max}\simeq 4.$

To demonstrate this for SIFT, the transition tilts attainable by SIFT have been explored by systematic tilt simulations
and tests. The experiments have been performed in the most favorable conditions for SIFT. The seed image $\bu_0$ is a
high quality frontal view of the Graffiti series.  Tilted views from this frontal view were simulated by  subsampling
the image in one direction by a factor $\sqrt{t}$, and oversampling the image in the orthogonal direction by the same
factor. That way, the absolute tilt is $t$, but the image area is not decreased.  A set of tilted-rotated images
$\bu_1=\bu_0(t_1,0)$ and $\bu_2=\bu(t_2, \phi)$ was generated by this method from $\bu$ with absolute tilts
$t_1=(\sqrt{2})^k$, $k=1$, 2, $\dots$, 5,  $t_2=(2^{\frac 14})^l,$ $l=1$, 2, $\dots$, 14, and  $\phi_2$ in a dense
subset  of $[0, \; 90^\circ]$. The table shows for each pair $t_1, t_2$ the maximal longitude $\phi_{max}$ ensuring
that $\bu_1(t_1,0^\circ)$ and $\bu_2(t_2, \phi_{max})$ match. On the right of $\phi_{max}$, the table displays in each
box the corresponding transition tilt $\tau(t_1, 0^°, t_2, \varphi_{max})$. Conspicuously enough, $\tau_{max}$ is most
of the time close to 2.5.  This experiment, and other similar ones, substantiate the empirical law that {\it SIFT works
for comparing images with transition tilts smaller than 2.5.} In all of these tests, success with SIFT means that at
least 20 correct SIFT descriptors, or SIFs,  have been found.


\begin{figure}[htbp]
\begin{center}
\begin{tabular}{c}
\includegraphics[width=14cm]{./figures/graf1vs3_sift_234match.eps}
\vspace{-5ex}\\
\hspace{-.8ex}\includegraphics[width=14cm]{./figures/graf1vs4_sift_28match.eps} \\
\end{tabular}
\end{center}
\caption{Top and bottom: SIFT detects respectively 234 and 28 matches between a frontal image and two images with tilts
 $t \approx 2$ and $t \approx 2.3$. This latter value is close to the limiting tilt for SIFT to work. } \label{fig:sift:affine}
\end{figure}



\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline & $t_1 = \sqrt{2}$ & $t_1 = 2$ & $t_1 = 2\sqrt{2}$ & $t_1 = 4$ &
$t_1 = 4\sqrt{2}$ \\
\hline $t_2=2^{1/4}$ & $90^\circ$/1.7 & $60^\circ$/2.2& $0^\circ$/2.4 &  &
 \\
\hline $t_2=2^{1/2}$ & $90^\circ$/2.0 & $56^\circ$/2.4 & $11^\circ$/2.1 &
&  \\
\hline $t_2=2^{3/4}$ & $90^\circ$/2.4 & $50^\circ$/2.6 & $20^\circ$/2.1 &
$0^\circ$/2.4 &  \\
\hline $t_2=2$ & $63^\circ$/2.6 & $36^\circ$/2.4 & $20^\circ$/2.1 &
$9^\circ$/2.2 &  \\
\hline $t_2=2\times2^{1/4}$ & $37^\circ$/2.4 & $30^\circ$/2.3 &
$23^\circ$/2.3 & $9^\circ$/1.9 &  \\
\hline $t_2=2\times2^{1/2}$ & $18^\circ$/2.6 & $22^\circ$/2.2 &
$24^\circ$/2.6 & $12^\circ$/2.0 &  $0^\circ$/1.4 \\
\hline $t_2=2\times2^{3/4}$ & $6^\circ$/2.4  & $16^\circ$/2.2 &
$21^\circ$2.6 & $16^\circ$/2.5 & $5^\circ$/1.4 \\
\hline $t_2=4$ & $0^\circ$/2.8  & $9^\circ$/2.2 & $18^\circ$/2.6 &
$14^\circ$/2.4 & $9^\circ$/1.8 \\
\hline $t_2=4\times2^{1/4}$ &  & $4^\circ$/2.4 & $11^\circ$/2.2 &
$12^\circ$/2.3 & $8^\circ$/2.0 \\
\hline $t_2=4\times2^{1/2}$ &  &  & $6^\circ$/2.2 & $7^\circ$/1.9 &
$8^\circ$/2.3 \\
\hline $t_2=4\times2^{3/4}$ &  &  & $0^\circ$/2.4 & $5^\circ$/2.0 &
$8^\circ$/2.5 \\
\hline $t_2=8$ &  &  &  & $0^\circ$/2.0 & $7^\circ$/2.5 \\
\hline $t_2=8\times2^{1/4}$ &  &  &  &  & $4^\circ$/2.6 \\
\hline $t_2=8\times2^{1/2}$ &  &  &  &  & $3^\circ$/2.9 \\
\hline
\end{tabular}
\end{center}
\caption{m/n in each entry means: maximal longitude angle $\phi$ giving at least 20 matches by SIFT / corresponding
transition tilt $\tau(t_1, t_2, \phi)$. This table shows that SIFT covers a transition tilt $\tau \approx 2.5$.}
\label{tab:sphere:sift:simul:tiltB}
\end{table}





\section{Parameter sampling and complexity \label{ComputationalIssues}}


\subsection{Sampling ranges}  The camera motion depicted in Fig.~\ref{fig:decomp:RTR} shows that $\phi$ should
naturally cover all the directions from 0 to $2 \pi$. But, by Theorem  \ref{theoremdecompositionofaffine},
 it is enough to simulate $\phi$ from 0 to $\pi$ to cover all possible linear transforms.

The sampling range of the tilt parameter $t$ determines the degree of the tilt invariance the algorithm can achieve.
Image recognition under a remarkable viewpoint change in practice requires that the scene is planar and Lambertian and
its structures are not squashed when observed from an oblique viewpoint. Due to these physical limitations, affine
image recognition is impractical under too big a tilt  $t$. The physical upper bound $t_{\max}$ can be obtained
experimentally using some images taken from indoor and outdoor scenes, each image pair being composed of a frontal view
and an oblique view.

The images used in the experiments satisfy as much as possible the physical conditions mentioned above. The indoor
scene is a magazine placed on a table with the artificial illumination coming from the ceiling as shown in
Fig.~\ref{fig:longitude:sampling:range}. The outdoor scene is a building fa\c{c}ade with some graffiti as illustrated
in Fig.~\ref{fig:longitude:sampling:range:outdoor}. For each pair of images, the true tilt parameter $t$ between them
is obtained by manual measurement. A-SIFT is applied with  very large parameter sampling ranges and small sampling
steps, so that the simulated views cover accurately the true affine distortion. The A-SIFT matching results depicted in
Figs.~\ref{fig:longitude:sampling:range} and~\ref{fig:longitude:sampling:range:outdoor} show that the limit is
$t_{\max} \approx 5.6$ that corresponds to a view angle $\theta_{\max} = \arccos 1/t_{\max} \approx 80^{\circ}$. A-SIFT
finds a large number of matches when the tilt between the frontal image and the oblique image is smaller than about
$5.6$. Therefore we set the tilt simulation range $t_{\max}=4\sqrt{2}$.

Let us emphasize that when the two images under comparison are taken from orthogonal longitude angles (see
Fig.~\ref{fig:numeric:CSIFT:extreme:tilt} as an example), i.e., $\phi=\phi'+\pi/2$, the maximum tilt invariance A-SIFT
with $t_{\max}=4\sqrt{2}$ can achieve in theory is about $t_{\max}^2=32$.

However, these experiments only fix reasonable bounds for all purpose algorithms. For high resolution images,  for very
flat lambertian surfaces, larger tilts might be recognizable.



\begin{figure}[htbp]
\begin{center}
\begin{tabular}{c}
%\includegraphics[width=9cm]{./figures/lepoint1vs3_tilt3_CSIFT_Tmax8_75match.eps} \\
%\includegraphics[width=9cm]{./figures/lepoint1vs4_tilt4p5_CSIFT_Tmax8_35match.eps} \\
%\includegraphics[width=9cm]{./figures/lepoint1vs5_tilt5_CSIFT_Tmax8_17match.eps} \\
%\includegraphics[width=9cm]{./figures/lepoint1vs9_tilt7p3_CSIFT_Tmax8_15match.eps} \\
%\includegraphics[width=9cm]{./figures/lepoint1vs8_tilt8_CSIFT_Tmax8_8matchWrong.eps} \\
\includegraphics[width=10cm]{./figures/lepoint1vs3_tilt3_CAffine2sides_Tmax2sqrt2_tk_sqrt2_MR_107match.eps} \\
\vspace{-5ex}
\includegraphics[width=10cm]{./figures/lepoint1vs5_tilt5_CAffine2sides_Tmax2sqrt2_tk_sqrt2_MR_25match.eps} \\
\vspace{-5ex}
\includegraphics[width=10cm]{./figures/lepoint1vs6_tilt8_CAffine2sides_Tmax2sqrt2_tk_sqrt2_MR_7match_fail.eps} \\
\end{tabular}
\end{center}
\caption{A-SIFT on an indoor scene. From top to bottom: tilt distortion $t$ between the two images are respectively $t
\approx 3, 5.2, 8.5$; the number of matches are respectively 107 (3 false), 25 (7 false), and 7 (all false). }
\label{fig:longitude:sampling:range}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{c}
%\includegraphics[width=9cm]{./figures/outdoorX1vs10_CSIFT_TR_tmax8_71match.eps} \\
%\includegraphics[width=9cm]{./figures/outdoorX1vs13_CSIFT_TR_tmax8_20match.eps} \\
%\includegraphics[width=9cm]{./figures/outdoorX1vs14_CSIFT_TR_tmax8_15match.eps} \\
%\includegraphics[width=9cm]{./figures/outdoorX1vs15_CSIFT_TR_tmax8_3match.eps} \\
%\includegraphics[width=9cm]{./figures/outdoorX1vs16_CSIFT_TR_tmax8_1match.eps} \\
\includegraphics[width=10cm]{./figures/Xlab1vs14_CAffine2_71match.eps}
\vspace{-5ex}
\\
\includegraphics[width=10cm]{./figures/outdoorX1vs15_CAffine2sides_tmax2sqrt2_tk_sqrt2_MR_33match.eps}
\vspace{-5ex}
\\
\includegraphics[width=10cm]{./figures/outdoorX1vs16_CAffine2sides_tmax2sqrt2_tk_sqrt2_MR_8match_fail.eps}
\vspace{-5ex}
\\
\end{tabular}
\end{center}
\caption{A-SIFT on an outdoor scene. From top to bottom: tilt distortion $t$ between the two images are respectively $t
\approx 3.8, 5.6, 8$; the number of matches are respectively 71 (4 false), 33 (4 false), 10 (all false).  }
\label{fig:longitude:sampling:range:outdoor}
\end{figure}

\subsection{Sampling steps\label{subsec:sampling}} In order to have A-SIFT invariant to any affine transform, one needs to sample the tilt
$t$ and angle $\phi$ with a
  high enough precision. The sampling steps  $\triangle t$ and $\triangle
{\phi}$ must be fixed experimentally by
  testing several natural images.

The camera motion model illustrated in Fig.~\ref{fig:decomp:RTR} indicates that the sampling precision of the latitude
angle $\theta = \arccos 1/t$ should increase with $\theta$. A geometric sampling for $t$ satisfies this requirement.
Naturally, the sampling ratio $\triangle t = t_{k+1} / t_k $ should be independent of the angle $\phi$. In the sequel,
the tilt sampling step is experimentally fixed to $\triangle t = \sqrt{2}$.


As can be observed from the camera motion model in Fig.~\ref{fig:decomp:RTR}, one needs a finer $\phi$ sampling when
$\theta = \arccos 1/t$ increases: the image distortion caused by a fixed longitude angle displacement $\triangle \phi$,
is much more drastic when  the latitude  angle $\theta$ increases. The longitude sampling step in the sequel will be
$\triangle \phi = 2\times \frac{36^{\circ}}{t} = \frac{72^{\circ}}{t}$.

Fig.~\ref{fig:CAffine:simulation} illustrates the sampling of the parameters $\theta = \arccos 1/t$ and $\phi$. At
bigger $\theta$ the sampling of $\theta$ as well as the sampling of $\phi$ are denser.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\includegraphics[width=6cm]{./figures/brevet_fig2b.eps} &
\includegraphics[width=6cm]{./figures/brevet_fig4b_english1.eps}
\end{tabular}
\end{center}
\caption{Sampling of the parameters $\theta = \arccos 1/t$ and $\phi$. Black dots represent the sampling. Left:
perspective illustration (only $t=2, 2\sqrt{2}, 4$ are shown). Right: zenith view of the observation half sphere. The
values of $\theta$ are indicated on the figure.} \label{fig:CAffine:simulation}
\end{figure}



\subsection{Acceleration with multi-resolution}
 The multi-resolution procedure accelerates A-SIFT by selecting the transforms that yield SIFT matches on low-resolution
(LR) versions of the compared images. In case of success only, the procedure simulates the identified affine transforms
on the query, and applies SIFT to compare them to the targets.

The multi-resolutions A-SIFT is summarized as follows.
\begin{enumerate}
\item Down-sample all compared digital images $\bu$ and $\bv$ by a $K \times K$ factor: $\bu'= \bS_K \bG_{K}
\bu$ and $\bv'= \bS_K \bG_{K} \bv,$ where $\bG_{K}$ is an anti-aliasing gaussian discrete filter.
\item Low-resolution (LR) A-SIFT: perform A-SIFT   between $\bu'$ and $\bv'$.

\item Identify the $M$   affine transforms  yielding the biggest numbers of matches between $\bu'$ and $\bv'$.
They are retained only if the matches are meaningful. In practice, it is enough to put a threshold on the number $k$ of
matches, and $k=15$ seems to be a good choice.
\item High-resolution (HR) A-SIFT: apply A-SIFT between $\bu$
and $\bv$ by simulating only the affine transforms previously identified.
%The complexity of this step
%is in principal $M'/M$ times as small as a normal A-SIFT routine,
%where $M'$ and $M$ are respectively the cardinals of $\{
%\mathbf{\Gamma'_t}, \mathbf{\Gamma'_\theta} \}$ and $\{
%5\mathbf{\Gamma_t}, \mathbf{\Gamma_\theta} \}$.
\end{enumerate}

Fig.~\ref{fig:MRCAffine} shows an example. The low-resolution A-SIFT that is applied on the $3 \times 3$ sub-sampled
images finds 12 correspondences and identifies the 5 best affine transforms. The high-resolution A-SIFT finds 133
matches.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\includegraphics[width=2.5cm]{./figures/77MassAve_LRASIFTx3_12matches.eps}
&
\includegraphics[width=7.5cm]{./figures/77MassAve_HRASIFTx3_133matches.eps}
\hspace{-1cm}
\end{tabular}
\end{center}
\hspace{-1cm} \caption{``77 Mass Ave''. Left: low-resolution A-SIFT, 12 matches, three of which are wrong. Right:
high-resolution A-SIFT, 133 matches. Due to the lack of details in these images, the number of matches at low
resolution is critically low.} \label{fig:MRCAffine}
\end{figure}



\subsection{A-SIFT Complexity} \label{subsubsec:CSIFT:complexity}
The complexity of the A-SIFT algorithm will be estimated under the recommended baseline configuration: The tilt and
angle ranges are $[t_{\min}, t_{\max}] = [1, 4\sqrt{2}]$ and $[\phi_{\min}, \phi_{\max}] = [0^{\circ}, 180^{\circ}]$,
and the sampling steps are $\triangle t = \sqrt{2}$,  $\triangle \phi = 36^{\circ} \times \frac{t}{2}$. Each $t$ tilt
is simulated by image sub-sampling in one direction by a $t$ factor. All images are sub-sampled by a $K \times K = 3
\times 3$ factor for the low-resolution A-SIFT.  Finally, the high-resolution A-SIFT simulates the $M=5$ best affine
transformations that are identified, but only in case they contain enough matches. When matching an image to a large
database, the most common event is failure. Thus, the final high-resolution step is only to be taken into account when
comparing images of the same scene.

The complexity of the descriptor computation is proportional to the input image area. This area is proportional to the
number of simulated tilts $t$. Indeed, the number of $\phi$ simulations is proportional to $t$ for each $t$, but the
$t$ sub-sampling for each tilt simulation divides the area by $t$. More precisely, the image area input to
low-resolution A-SIFT is

$$\frac{1+(|\Gamma_t|-1)\frac{180^{\circ}}{2 \times
36^{\circ}}}{K^2}=\frac{1+5\times2.5}{9}=1.5$$ times as large as that of the original images, where $|\Gamma_t|$ is the
number of tilt simulations. Thus, the complexity of the low-resolution A-SIFT is 1.5 times as much as that of a single
SIFT routine, and  generates 1.5 as many SIFs. Here we must distinguish two cases:

\begin{enumerate} \item If the comparisons involve a large database (where most comparisons will be failures), the complexity is propositional to the number of SIFs in
the queries multiplied by the number of SIFs in the targets. Since A-SIFT introduces a a 1.5  area factor, the final
complexity is simply $1.5^2= 2.25$ times the SIFT complexity.
\item If the comparisons involve a set of images with high match likeliness, then the high resolution step is no more
negligible. Then, it can only be asserted that the complexity will be less than $6.5 + 2.5= 9$ times a SIFT routine on
the same images. However, in that case, A-SIFT ensures many more detections than SIFT, because it explores many more
viewpoint angles.  Thus, the {\it complexity rate per detected SIF} might be much closer to, or even smaller than the
per detection complexity in a SIFT routine.
\end{enumerate}

For the high-resolution A-SIFT, this factor is $M=5$. Therefore the total complexity of the A-SIFT is $6.5$ times a
SIFT routine.

The SIFT subroutines can be implemented in parallel in A-SIFT (for both the low-resolution and the high-resolution
A-SIFT). Recently many authors have investigated SIFT accelerations~\cite{DBLP:conf/cvpr/KeS04, 1273738, 1180760}. A
realtime SIFT implementation has been proposed in~\cite{sinha2006}. Obviously, all of these accelerations directly
apply to A-SIFT.



\begin{figure}[htbp]
\begin{center}
\vspace{-5ex}
\begin{tabular}{ccc}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta45_degRelativeTilts_tmax2p5_BW.eps}
& \hspace{-5ex}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta45_degRelativeTilts_tmax5_BW.eps}
& \hspace{-4ex}\includegraphics[width=2.5cm]{./figures/RecogSphere_theta45_degRelativeTilts_tmax40_BW.eps}
\\
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta45_degRelativeTilts_tmax2p5_BW_zenith.eps}
& \hspace{-5ex}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta45_degRelativeTilts_tmax5_BW_zenith.eps}
& \hspace{-4ex}\includegraphics[width=2.5cm]{./figures/RecogSphere_theta45_degRelativeTilts_tmax40_BW_zenith.eps}
\\
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta60_degRelativeTilts_tmax2p5_BW.eps}
& \hspace{-5ex}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta60_degRelativeTilts_tmax5_BW.eps}
& \hspace{-4ex}\includegraphics[width=2.5cm]{./figures/RecogSphere_theta60_degRelativeTilts_tmax40_BW.eps}
\\
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta60_degRelativeTilts_tmax2p5_BW_zenith.eps}
& \hspace{-5ex}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta60_degRelativeTilts_tmax5_BW_zenith.eps}
& \hspace{-4ex}\includegraphics[width=2.5cm]{./figures/RecogSphere_theta60_degRelativeTilts_tmax40_BW_zenith.eps}
\\
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta70_degRelativeTilts_tmax2p5_BW.eps}
& \hspace{-5ex}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta70_degRelativeTilts_tmax5_BW.eps}
& \hspace{-4ex}\includegraphics[width=2.5cm]{./figures/RecogSphere_theta70_degRelativeTilts_tmax40_BW.eps}
\\
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta70_degRelativeTilts_tmax2p5_zenith.eps}
& \hspace{-5ex}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta70_degRelativeTilts_tmax5_BW_zenith.eps}
& \hspace{-4ex}\includegraphics[width=2.5cm]{./figures/RecogSphere_theta70_degRelativeTilts_tmax40_BW_zenith.eps}
\\
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta80_degRelativeTilts_tmax2p5.eps}
& \hspace{-5ex}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta80_degRelativeTilts_tmax5_BW.eps}
& \hspace{-4ex}\includegraphics[width=2.5cm]{./figures/RecogSphere_theta80_degRelativeTilts_tmax40_BW.eps}
\\
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta80_degRelativeTilts_tmax2p5_zenith.eps}
& \hspace{-5ex}
\includegraphics[width=2.5cm]{./figures/RecogSphere_theta80_degRelativeTilts_tmax5_BW_zenith.eps}
& \hspace{-4ex}\includegraphics[width=2.5cm]{./figures/RecogSphere_theta80_degRelativeTilts_tmax40_BW_zenith.eps}
\\
\end{tabular}
\end{center}
\caption{Each recognition method can be characterized by its transition tilt, namely the variation in relative
observation angle compatible with recognition. This figure shows perspective and zenith views of the observation
sphere. The central point of the bright region on the observation sphere is the original viewpoint from which an image
has been taken. The rest of the bright region depicts, for several positions of this original point and several
transition tilts, the attainable observation region, namely all other view angles in the observation sphere for which
recognition succeeds for the given transition tilt.
   From top to bottom: latitude angle of the first image $\theta = 45,\; 60, \;70,\;
80^\circ$ that correspond respectively to the absolute tilts $t=\sqrt{2},\; 2, \;2.9,\; 5.8$. From left to right:
transition tilt $<2.5,\; 5,\; 40$.} \label{fig:RecogSphere}
\end{figure}
