\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}





\chapter{The mathematical justification\label{TheMathematicalTheory}}
\def\bbG{\mathrm {G}}
This chapter gives the mathematical formalism and a mathematical proof that A-SIFT is fully affine
 invariant, up to sampling errors.   The next chapter \ref{Experiments} is devoted
 to many comparative experiments where all mentioned state-of-the art algorithms are compared for their scale and tilt
 invariance.


  In this chapter, to lighten the notation of the gaussian,  $\bbG_\sigma$ will
denote the  convolution operator on $\RR^2$  with  the gauss kernel $\bbG_\sigma(x,y)=\frac
1{2\pi(\ft2\sigma)^2}e^{-\frac{x^2+y^2}{2(\ft2\sigma)^2}}$, namely $\bbG u(x,y)=: (\bbG \ast u)(x,y).$  The constant
$\ft2\geq 0.8$ is large enough  to ensure  that all considered images can be sampled with sampling  mesh 1 after
convolution with $\bbG_1$.  The one dimensional gaussians will be denoted by $\bbG^x_\sigma(x,y)=\frac
1{\sqrt{2\pi}\ft2\sigma}e^{-\frac{x^2}{2(\ft2\sigma)^2}}$ and $\bbG^y_\sigma(x,y)=\frac
1{\sqrt{2\pi}\ft2\sigma}e^{-\frac{y^2}{2(\ft2\sigma)^2}}$.  $\bbG_\sigma$ still satisfies the semigroup property
\begin{equation}
\label{continuoussemigroupproperty}\bbG_{\sigma} \bbG_{\beta}= \bbG_{\sqrt{\sigma^2+ \beta^2}}.\end{equation} The proof
of the next formula is a mere change of variables in the integral defining the convolution.
\begin{equation}\label{commutationconvolutionzoomcontinus}\bbG_\sigma  H_\gamma u=
H_\gamma\bbG_{\sigma\gamma}  u.\end{equation}
\begin{exercise} Prove \eqref{commutationconvolutionzoomcontinus}.
\finex \end{exercise} Using the above notation, the next paragraph formalizes the SIFT method.

\subsection{The image formation model}
As developed in Section \ref{AFastpresentation}, the whole image comparison process, based on local features, can
proceed as though images where (locally) obtained by using digital cameras  that stand far away, at infinity. The
geometric deformations induced by the motion of such cameras are affine maps. A model is also needed for the two main
camera parameters not deducible from its position, namely sampling and blur. The digital image is defined on the camera
CCD plane. The pixel width can be taken as length unit, and the origin and axes chosen so that the camera pixels are
indexed by $\relative^2$. The associated image sampling operator will be denoted by $\bS_1$. The digital initial image
is always assumed well-sampled and obtained by a gaussian blur with standard deviation $0.6$. (See
\cite{GuoshenMorelSIFT} for a detailed analysis of why this model is sufficient and coherent for most digital images,
and compatible with the SIFT method.) In all that follows,  $u_0$ denotes the (theoretical) infinite resolution image
that would be obtained by a frontal snapshot of a plane object with infinitely many pixels. The digital image obtained
by any camera at infinity is $\bu=\bS_1 \bbG_1 A\mathcal Tu_0$, where $A$ is
  {\it any} linear map with positive singular values and $\mathcal T$ any plane translation.
  Thus we can summarize the
general image formation model  with cameras at infinity  as follows.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{c}
\includegraphics[width=5cm]{./figures/image_formation.eps}
\end{tabular}
\end{center}
\caption{The projective camera model $u=\bS_1 \bbG_1 \mathbf{\mathcal A} u_0$. $\mathcal A$ is a planar projective
transform (a homography).  $\bbG_1$ is an anti-aliasing gaussian filtering.  $\bS_1$ is the CCD sampling.}
\end{figure}


\begin{definition} {\bf Image formation model.}  Digital images of a planar object whose frontal infinite
resolution image is $u_0$, obtained by a digital camera far away from the object, satisfy
\begin{equation}
\label{imageformationmodel}\bu=:\bS_1\bbG_1A\mathcal Tu_0
\end{equation}
where  $A$ is any linear map and $\mathcal T$ any plane translation. $\bbG_1$ denotes a gaussian kernel broad enough to
ensure no aliasing by 1-sampling, namely $I\bS_1\bbG_1A\mathcal Tu_0=\bbG_1A\mathcal Tu_0$.
\end{definition}
  The formal description of A-SIFT will be by far simpler if sampling issues do not interfere. All operations and all reasoning
  will be made with  continuous  well sampled images. It is easy to deduce afterwards the discrete
 operators acting on samples.
 $\mathbf{\mathcal T}$ denotes an arbitrary translation, $\mathbf{R}$ an arbitrary rotation,  $\mathbf{H}_\lambda$ an
arbitrary homothety, and  $\bbG$ an arbitrary gaussian convolution, all applied to continuous images. In the particular
case in the digital image formation model \eqref{imageformationmodel} where $A$ is a frontal view of $u_0$,
$A=HR\mathcal T$ is  the composition of a translation $\mathbf{\mathcal T}$, a homothety $H$,  and a rotation $R$.
 Thus the digital image is  $\bu=\bS_1 \bbG_1H\mathcal TR u_0$.



\subsection{Inverting tilts} \label{subsec:tilt:correction}
We shall denote by  $\ast_y$  the 1-D convolution convolution operator in the $y$-direction. When we write
$\bbG\ast_y$, we mean that $\bbG$ is a one-dimensional gaussian, depending on $y$, and the 1-D convolution means
$$\bbG\ast_yu(x,y)=: \int \bbG^y(z)u(x,y-z)dz.$$
 There are {\it three different notions of tilt}, that we must carefully distinguish.
\begin{definition} \label{definitionsoftilts}Given $t>1$, the tilt factor, define
\begin{itemize}
\item the absolute tilt : $T_t^xu_0(x,y)=: u_0(tx,y).$ In case this tilt is made in the $y$ direction. It will be
denoted  by $T_t^yu_0(x,y)=:u_0(x,ty);$
\item the continuous tilt (taking into account camera blur): $\mathbb T_t^xv=:T_t^x\bbG^x_{\sqrt{t^2-1}}\ast_x v$. In case the simulated
tilt is done in the $x$ direction, it is denoted $\mathbb T_t^yv=: T_t^y\bbG^y_{\sqrt{t^2-1}}\ast_y v.$

\item the  digital tilt (transforming a  digital image $u$ into a digital image) :
$\bu\to \bS_1\mathbb T_t^x I\bu.$ This is the one  that is used in the algorithm. It is correct because, as we shall
see, the simulated tilt yields a blur permitting $\bS_1$-sampling.
\end{itemize}
\end{definition}
If $u_0$ is an infinite resolution image observed with  a $t$  camera tilt in the $x$  direction, the observed image is
$\bbG_1T_t^xu_0$. Our main problem is to reverse such tilts. This operation  is in principle impossible, because
absolute tilts do not commute with blur. However, the next lemma shows that  $\mathbb T_t^y$ is actually a pseudo
inverse to $T_t^x$.

\begin{lemma}\label{zoominversetiltgivestilt} One has
$$\mathbb T_t^y=H_t\bbG^y_{\sqrt{t^2-1}}\ast_y (T_t^x)^{-1}.$$
\end{lemma}

\paragraph{Proof} Since $(T_t^x)^{-1}u(x,y)=u(\frac xt,y)$,
$$\left(\bbG_{\sqrt{t^2-1}}^y\ast_y (T_t^x)^{-1}u\right)(x,y)=\int\bbG_{\sqrt{t^2-1}}(z)u(\frac xt, y-z)dz.$$
Thus
$$H_t\left(\bbG_{\sqrt{t^2-1}}^y\ast_y(T_t^x)^{-1}u\right)(x,y)=\int\bbG_{\sqrt{t^2-1}}(z)u(x,ty-z)dz=$$
$$\left(\bbG^y_{\sqrt{t^2-1}}\ast_yu\right)(x,ty)=\left(T_t^y\bbG^y_{\sqrt{t^2-1}}\ast_yu\right)(x,y).$$
  $\square$

The meaning of the  next result is that a tilted  image $\bbG_1T_t^xu$ can be tilted back by tilting in the orthogonal
direction. The price to pay is a $t$ zoom out. The second relation  in the theorem means that the application of the
simulated tilt to an image that can be well sampled by $\bS_1$  yields an image that keeps that well sampling property.
\begin{theorem}\label{howtocorrectthetilt} Let $t\geq 1$. Then \begin{equation}
\mathbb T_t^y(\bbG_1T_t^x)=\bbG_1H_t;\end{equation}  \begin{equation}\label{commutationtiltblur}\mathbb
T_t^y\bbG_1=\bbG_1T_t^y.\end{equation}
\end{theorem}
\paragraph{Proof}
By Lemma \ref{zoominversetiltgivestilt}, we recall that
$$\mathbb T_t^y=H_t\bbG^y_{\sqrt{t^2-1}}\ast_y (T_t^x)^{-1}.$$ Thus,
 \begin{equation}\label{decompositiongenerale}\mathbb
T_t^y(\bbG_1T_t^x)=H_t\bbG^y_{\sqrt{t^2-1}}\ast_y((T_t^x)^{-1}\bbG_1T_t^x).\end{equation} By a variable change in the
integral defining the  convolution,  it is an easy check that
\begin{equation}\label{commutationTtG1}
(T_t^x)^{-1}\bbG_1T_t^xu=\left(\frac 1t\bbG_1(\frac xt,y)\right)\ast u,
\end{equation}
and by the separability of the 2D gaussian in two 1D gaussians,
\begin{equation}\label{separationgaussians}
\frac 1t\bbG_1(\frac xt, y)=\bbG_t(x)\bbG_1(y).
\end{equation}
From \eqref{commutationTtG1} and \eqref{separationgaussians} one obtains
$$(T^x)^{-1}\bbG_1T_t^xu=((\bbG^x_t(x)\bbG^y_1(y))\ast u=\bbG^x_t(x)\ast_x\bbG^y_1(y)\ast_y u,$$
which  implies
$$\bbG^y_{\sqrt{t^2-1}}\ast_y(T^x)^{-1}\bbG_1T_t^xu=\bbG^y_{\sqrt{t^2-1}}\ast_y\left(\bbG^x_t(x)\ast_x\bbG^y_1(y)\ast_yu\right)=\bbG_tu.$$
Indeed, the 1D  convolutions  in $x$ and $y$ commute and  $\bbG^y_t\ast\bbG^y_{\sqrt{t^2-1}}=\bbG^y_t$ by the Gaussian
semigroup property \eqref{continuoussemigroupproperty}. Substituting the  last proven relation in
\eqref{decompositiongenerale} yields
$$\mathbb T_t^y\bbG_1T_t^xu=H_t\bbG_tu=\bbG_1H_tu.$$
The second relation \eqref{commutationtiltblur} follows immediately by noting that $H_t=T^y_tT^x_t.$
 $\square$


\begin{exercise}
Prove \eqref{commutationTtG1}.
 \finex
\end{exercise}
\subsection{Proof that A-SIFT works}


The meaning of Theorem \ref{howtocorrectthetilt} is that we can design an exact algorithm that simulates all inverse
tilts for comparing two images. After interpolation, A-SIFT handles two images $u=\bbG_{1}A\mathcal T_1u_0$ and
$v=\bbG_{1}B\mathcal T_2u_0$ that are two snapshots from different view points  of a flat object whose front infinite
resolution image is denoted by $u_0$.  For a sake of simplicity, we break the symmetry,
 and set
$\tilde u_0=: A\mathcal T_1u_0$, so that $u=\bbG_{1} \tilde u_0$ and $v=\bbG_{1}B\mathcal T_2\mathcal
T_1^{-1}A^{-1}\tilde u_0=\bbG_{1}BA^{-1} \mathcal T\tilde u_0$ for a translation $\mathcal T$ that depends on $\mathcal
T_1,$ $\mathcal T_2$,  and  $A$.  Let us use the decomposition given  by \eqref{decompositionofaffine},
$$BA^{-1}=R_1 T_t^x H_\lambda R_2,$$ where $R_1,$ $R_2$ are rotations, $H_\lambda$ a zoom, and
 $T_t^x(x,y)=(tx,y)$  is the transition
tilt from $u$ to $v$.
 In summary A-SIFT has to compare the interpolated images
$$v=\bbG_{1}R_1 T_t^x H_\lambda R_2 \mathcal T\tilde u_0 \hbox{ and } u= \bbG_1 \tilde u_0.$$

\subsubsection{The A-SIFT formal algorithm\label{formalalgorithm}}
The following algorithm, where  image sampling issues are eliminated by interpolation, is actually a proof that A-SIFT
manages to compare $u$ and $v$ obtained from $u_0$ by arbitrary camera positions at infinity. In this ideal algorithm,
a ```dense enough'' set of rotations and tilts is applied to $v$, so that each one of the simulated rotation-tilts is
``close enough'' to any other rotation-tilt. In the mathematical setting, this approximation must be infinitesimal. In
the practical empirical setting, we'll have to explore how dense the sets of rotations and tilts must be (see Section
\ref{ComputationalIssues}).

\medskip \noindent{\bf A-SIFT Algorithm (formal)}
\begin{enumerate}
\item Apply a dense set of all possible rotations (and therefore also a rotation close to $R_1^{-1}$) to $v$.
 Thus, some of the simulated images will
be arbitrary close to $v\rightarrow R_1^{-1}\bbG_{1}R_1H_\lambda T_t^x R_2\mathcal T\tilde u_0=\bbG_{1} T_t^x H_\lambda
R_2\mathcal T\tilde u_0;$

\item apply  in continuation a dense set of simulated  tilts $\mathbb T_t^y$, and therefore also one arbitrary close
 to the right one
$\mathbb T_{t}^y=T_t^y\bbG^y_{\sqrt{t^2-1}}\ast_y $, to $R_1^{-1}v=\bbG_{1} T_t^xH_\lambda R_2\mathcal T\tilde u_0$. By
Theorem \ref{howtocorrectthetilt} we have the commutation $T_t^y\bbG_1=\bbG_1T_t^y$,  which yields
$$\mathbb T_t^yR_1^{-1}v=
 \bbG_1H_tH_\lambda R_2\mathcal T\tilde u_0=\bbG_1H_{t\lambda}R_2\mathcal T\tilde u_0;$$

\item perform a SIFT comparison of  $\bbG_1H_{t\lambda}R_2\mathcal T\tilde u_0$,  which is a frontal view
of $\tilde u_0$, with  $u=\bbG_{1}\tilde u_0$ which also is a frontal view of $\tilde u_0$.
\end{enumerate}
The above algorithm  description is also a proof of the following consistency theorem, since the SIFT method finds all
SIFs common to two  frontal views (Theorem \ref{theo:scale}).

\begin{theorem}\label{proofthatCSIFTworks} Let
$u= \bbG_{1} A\mathcal T_1u_0 $ and $v=B\mathcal T_2u_0$ be two images obtained from an infinite resolution image $u_0$
by cameras at infinity with arbitrary position and focal lengths. Then A-SIFT, applied with a dense set of tilts and
longitudes, simulates two views of $u$ and $v$ that are obtained from each other by a translation, a rotation, and a
camera zoom. As a consequence, these images match by the SIFT algorithm.
\end{theorem}

 \begin{remark} Even if the above proof, and the statement of Lemma \ref{SIFTworks}, deal with  asymptotic statements
 when the sampling steps tend to infinity or when the SIFT scales tend to infinity, the  approximation rate is very quick,
a fact that can only be checked experimentally. This fact is actually extensively verified by the huge amount of
experimental evidence on SIFT, that shows first that the recognition of scale invariant features (SIFs) is robust to a
substantial variation of latitude and longitude, and second that the scale invariance is quite robust to moderate
errors on scale. Section \ref{ComputationalIssues} has evaluated the  adequate sampling rates and ranges for tilts and
longitudes.
 \end{remark}

\subsubsection{Simulating midway tilts}  The algorithm of Section \ref{formalalgorithm} can be implemented in several
ways. In the above description, the transition tilt $T_t^x$ is directly inverted on one of the images. This strategy is
consistent, but not optimal. As we have seen, the transition tilt can be very large. It is preferable to simulate
moderate tilts on two images that large tilts on one of them. To this aim a {\it midway image} can be reached from both
images by applying a $\sqrt{t}$ tilt to one of them and a $\sqrt{t}$ tilt to the other one. The only change to the
formal algorithm will be that rotations and tilts are applied to both images, not just to one of them.

\medskip \noindent{\bf Midway A-SIFT (formal)}
\begin{enumerate}
\item Apply a dense set of all possible rotations to both images, and therefore  $R_2$  to $u$ and
 $R_1^{-1}$ to $v$;

\item apply  in continuation a dense set of  simulated  tilts $\mathbb T_t^x$ in a fixed $[0, t_{max}]$ range;

\item perform a SIFT comparison of all pairs of resulting images.
\end{enumerate}
Let us now prove that this algorithm works, namely that two of the simulated images are deduced from each other by a
similarity. The query and target images are $u=\bbG_1A\mathcal T_1u_0$ and $v=\bbG_1B\mathcal T_2u_0.$ By the usual
decomposition of a linear map \eqref{decompositionofaffine},
$$BA^{-1}=R_1T_t^xR_2H_\lambda=(R_1T_{\sqrt{t}^x})(T_{\sqrt{t}}^xR_2H_\lambda).$$
Notice that by the relation
\begin{equation}\label{passageTxTy}\mathbb T_t^xR(-\frac\pi 2)=R(\frac\pi 2)\mathbb
T_t^y,\end{equation} the algorithm also simulates tilts in the $y$ direction, up to $R(\frac \pi 2)$ rotation. In
particular, the above algorithm applies:
\begin{enumerate}
\item $\mathbb T_{\sqrt{t}}^x R_2$ to $\bbG_1A\mathcal T_1u_0$, which by \eqref{commutationtiltblur}
 yields
 $\tilde u=\bbG_1T_{\sqrt{t}}^x R_2A\mathcal T_1u_0=:\bbG_1\tilde A\mathcal T_1u_0$;
\item  $R(\frac{\pi}2)\mathbb T_{\sqrt{t}}^yR_1^{-1}$ to $\bbG_1B\mathcal T_2u_0$, which
by \eqref{commutationtiltblur} yields
 $\bbG_1R(\frac{\pi}2)T_{\sqrt{t}}^yR_1^{-1}B\mathcal T_2u_0=: \bbG_1\tilde B\mathcal T_2u_0.$
\end{enumerate}
Let us show that $\tilde A $ and $\tilde B$ only differ by a similarity. Indeed,
$$\tilde B^{-1}R(\frac{\pi}2)H_{\sqrt{t}}\tilde A =  B^{-1}R_1 T_{\sqrt{t}^{-1}}^yT_{\sqrt{t}}^x H_{\sqrt{t}}R_2A=$$

$$ B^{-1}R_1 T_{\sqrt{t}^{-1}}^y T_{\sqrt{t}}^x H_{\sqrt{t}}R_2 A=
 B^{-1}R_1 T_t^x R(\frac{\pi}2) R_2 A=B^{-1}(BA^{-1})A=I,$$
 where $I$ is the identity. It follows that $\tilde B= R(\frac{\pi}2)H_{\sqrt{t}}\tilde A$.  Thus,
$$\tilde u=\bbG_1\tilde A\mathcal T_1u_0\; \hbox{ and }
\;\tilde v=\bbG_1R(\frac{\pi}2)H_{\sqrt{t}}\tilde A\mathcal T_2u_0,$$ that are two of the simulated images, are deduced
from each other by a rotation and a $\sqrt{t}$ zoom. It follows that their SIFs are identical as soon as the scale of
the SIF exceeds $\sqrt{t}$.

\endproof
\begin{exercise}
There is a (non crucial) error in the above proof. Read this proof carefully, find the error, and adjust the proof.
\finex
\end{exercise}

\subsection{Conclusion on the algorithms}
The above descriptions have neglected the sampling issues, but care was taken that input images and  output images be
always written in the $\bbG_1u$ form. For the digital input images, that always have the form $\bu=\bS_1\bbG_1u_0$, the
Shannon interpolation algorithm is $I$ is first applied, to give back $I\bS_1\bbG_1u_0=\bbG_1u_0$. For the output
images, that always have the form $\bbG_1v$, the sampling $\bS_1$ gives back a digital image.

Thus, the descriptions of the formal algorithm A-SIFT and of its ``midway'' version are changed into a digital
algorithm by:
\begin{itemize}
\item replacing everywhere the inputs $\bbG_1u$ by
 their digital version $\bS_1\bbG_1u$;
\item by applying digital rotations to digital images : $\bu\to \mathcal R \bu = : \bS_1R I \bu$;
\item by applying digital tilts as defined in Def. \ref{definitionsoftilts}, namely $\bu\to \bS_1\mathcal T_t^xI\bu$.
\end{itemize}
That way, the formal algorithms are transformed into digital algorithms. The proofs need not be repeated, since by
Shannon interpolation and sampling, it is equivalent to talk about $\bS_1\bbG_1u_0$ or about $\bbG_1u_0$.


Clearly the midway algorithm  is better, because it only needs simulating  tilts that are square roots of the real
transition tilts. Thus, all of the forthcoming discussion will focus on the midway version, that we'll simply call
A-SIFT.


\def\qed{$\square$}
\def\Fo{\mathcal F}
\def\nbOne{\bm 1}
\newcommand{\transposee}[1]{{#1}^{\mathrm t}}
%\newcommand{\transposee}[1]{{#1}^{\mathrm T}}

\chapter{Experiments  on affine invariant methods}
\section{Affine normalization methods: are they fully affine invariant?\label{affinenormalizationmethods}}

  Since the affine
transform depends upon six parameters, it is out of the question to just simulate all of them and compare the original
image to all deformed images by all possible affine deformations.  However, {\it simulation} can be a solution for a
few parameters: the SIFT method actually simulates zooms out.

The other way that has been tried by many authors is {\it normalization}. Normalization is a magic method that, given a
patch that has undergone an unknown affine transform, transforms the patch into a standardized one, where the effect of
the affine transform has been eliminated (see Fig. \ref{normalizationmethods}). Normalization by translation is easily
achieved: A patch around $(x_0,y_0)$ is translated back to a  patch around $(0,0)$. A rotational normalization requires
a circular patch. In this patch, a principal direction is found, and the patch is rotated so that this principal
direction coincides with a fixed direction.  Thus, of the six parameters in an affine transform, at least three are
easily eliminated by normalization.
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\includegraphics[width=3cm]{./figures/normalization_translation.eps} &
\includegraphics[width=3cm]{./figures/normalization_rotation.eps} &
\includegraphics[width=3cm]{./figures/normalization_tilt.eps} \\
\end{tabular}
\end{center}
\caption{Normalization methods can eliminate the effect of a a class of affine transforms by associating the same
standard patch to all transformed patches.\label{normalizationmethods}}
\end{figure}

However, when it comes to the other three parameters, things get difficult and controversial.  Two methods have been
recently proposed to perform a level lines based full affine normalization: MSER \cite{matas02mser} and LLD
\cite{muse04:_acontrario}. Both of them apply to image level lines, or to image pieces of level lines, an affine
normalization in the spirit of the translation and rotation normalization explained above.  We shall focus on MSER, but
the discussion applies to LLD as well.



\section{Global Normalization and Encoding}
\label{sect:globnorm}


\subsection{Global Affine Normalization}
\label{sect:cohignac}\index{global affine invariant normalization}

Classical shape normalization methods are based on the inertia matrix normalization. We shall use Cohignac's
presentation of this method, given in \cite{cao2008tsi}. Denote by $\nbOne_\Fo$ \index{indicator function} the
indicator function of a  shape domain $\Fo$. The shape is usually associated a weight function defined on the shape
domain, $u(x,y)=\varphi(x,y)\nbOne_\Fo$. Classically, $\varphi(x,y)$ is the restriction of an image to the shape
extracted from it, or the restriction to the shape of the image gradient, or the restriction to the shape of the image
gradient direction, etc. Thus when we talk about ``the shape $\Fo$'', we actually talk about $u(x,y)$.  Of course, when
$\varphi(x,y)=1$, the whole analysis of this section boils down to the analysis of the proper shape $u=\nbOne_\Fo$.  In
all that follows, a convenient abbreviation is $\Fo$ for $u(x,y)$. If  $A$ is  linear or affine map, $A\Fo$ denotes the
function $Au$ defined as usual by $Au(x,y)=u(A(x,y)).$ In order to achieve translation invariance of the normalized
representation, it may be assumed that~$\Fo$ has been previously translated so that its barycenter weighted by $u(x,y)$
is at the origin of the image plane.
 \begin{exercise} Show that this last assumption amounts to  assume that $$\mu_{1,0}(\Fo)=:\int_{\R^2}xu(x,y)dxdy=0
\; \hbox{ and }\;
   \mu_{0,1}(\Fo)=:\int_{\R^2}yu(x,y)dxdy=0.$$ More precisely, give a formula for the weighted barycenter $b(\Fo)$ of $\Fo$ and
  show that
 the barycenter is covariant by any affine transform, namely $b(A\Fo)=Ab(\Fo)$ for every linear transform $A$. Show
 that the weighted area of $\Fo$ defined by  $\mu_{0,0}(\Fo)=:\int_{\R^2}u(x,y)dxdy$ satisfies
 $\mu_{0,0}(A\Fo)=|det(A)|\mu_{0,0}(\Fo).$
\finex \end{exercise}
 The moment of order $(p,q)$ ($p$ and $q$ natural integers) of the shape $\Fo$ (weighted by $u$) is defined by
$$\mu_{p,q} (\Fo) = \int_{\R^2} x^p y^q
u(x,y) dx dy.$$ Let $S_\Fo$ be the following $2 \times 2$ positive-definite, symmetric matrix
$$
S_\Fo=\frac{1}{\mu_{0,0}} \left(\begin{array}{cc}
\mu_{2,0} & \mu_{1,1} \\
\mu_{1,1} & \mu_{0,2} \\
\end{array}
\right), $$ where $\mu_{i,j}=\mu_{i,j}(\Fo)$. By the uniqueness of Cholesky factorization~\cite{golub1996mc}, $S_\Fo$
may be uniquely decomposed as $S_\Fo = B_\Fo\transposee{B}_\Fo$ where $B_\Fo$ is a lower-triangular real matrix with
positive diagonal entries.

\begin{definition}\index{affine shape normalization by Cholesky
method} The \emph{pre-normalized shape} associated to~$\Fo$ is the shape
 $\Fo' = B_{\Fo}^{-1}(\Fo)$.
\end{definition}
The aim is to prove that the pre-normalized solid shape is invariant to affine transformations, up to a rotation.
\begin{lemma}
Let $A$ be a non-singular $2 \times 2$ matrix. Then $S_{A\Fo} = AS_{\Fo}\transposee{A}.$ \label{lemma.cohignac.1}
\end{lemma}

\begin{proof}
Let $a,b,c$ and $d$ be real numbers such that:
$$A=\left(
\begin{array}{cc}
a & b \\
c & d \\
\end{array}
\right).$$ The moment of order $(2,0)$ associated to the solid shape $A\Fo$ is
\begin{eqnarray*}
\mu_{2,0}(A\Fo) &=& \det(A) \int_{\R^2}(ax+by)^2 u(x,y) dx dy \\
&=& \det(A)( a^2 \mu_{2,0} + 2ab \mu_{1,1} + b^2 \mu_{0,2}).
\end{eqnarray*}
The same computation for moments of order $(0,2)$ and $(1,1)$ yields
\begin{eqnarray*}
 \mu_{0,2}(A\Fo) & = &\det(A)(c^2 \mu_{2,0} + 2cd \mu_{1,1} + d^2
\mu_{0,2}), \\
\mu_{1,1}(A\Fo) & = & \det(A)(ac\mu_{2,0} + bd\mu_{0,2} + (ad+bc)\mu_{1,1}).
\end{eqnarray*}
Since $\mu_{0,0}(A\Fo) = \det(A)\mu_{0,0}$, one can easily check that $S_{A\Fo} = AS_\Fo\transposee{A}.$
\end{proof}
\begin{exercise}
Make the calculation proving that $S_{A\Fo} = AS_\Fo\transposee{A}.$ \finex
\end{exercise}

\begin{lemma}
Let $X_0$ be a $2 \times 2$ invertible matrix. Then, for any $2 \times 2$ matrix $X$: $X\transposee{X} =
X_0\transposee{X_0}$ if and only if there exists an orthogonal matrix $Q$ such that $X=X_0Q.$ \label{lemma.cohignac.2}
\end{lemma}

\begin{proof}
Since $X_0$ is invertible, $X\transposee{X} = X_0\transposee{X_0}$ iff $X_0^{-1}X\transposee{(X_0^{-1}X)}=\text{Id}_2$.
Letting~$Q = X_0^{-1}X$ yields the result.
\end{proof}

\begin{proposition} \index{invariance of a normalized shape by
Cholesky method} \label{propositioncohignc} The pre-normalized solid shape is invariant to any invertible, planar,
linear transformation $\transposee{(x, y)}~\mapsto~A\transposee{(x, y)}$, up to an orthogonal transformation. Moreover,
if $\det(A)>0$, the invariance holds up to a rotation.
\end{proposition}

\begin{proof}
Since $A$ is a $2 \times 2$ non singular matrix, following Lemma~\ref{lemma.cohignac.1},  $S_{A\Fo} = A S_\Fo
\transposee{A}$.  By letting $B_\Fo$ be the lower-triangular matrix of Cholesky's decomposition of~$B_\Fo$, it follows
that $S_{A\Fo} = AB_\Fo \transposee{(AB_\Fo)}$.  Now, since $S_{A\Fo}$ is a $2 \times 2$ positive-definite, symmetric
matrix, Cholesky factorization yields $S_{A\Fo}=B_{A\Fo}\transposee{B_{A\Fo}}$, where $B_{A\Fo}$ is a $2 \times 2$
non-singular, lower-triangular real matrix. Then, by Lemma~\ref{lemma.cohignac.2}, $B_{A\Fo} = AB_\Fo Q$, where $Q$ is
a $2 \times 2$ orthogonal matrix.  Hence, $B_{A\Fo}^{-1} A\Fo = (AB_\Fo Q)^{-1} A\Fo = Q^{-1} B_\Fo^{-1} A^{-1} A \Fo =
Q^{-1} B_\Fo^{-1} \Fo$, which proves the invariance of $\Fo'=B_\Fo^{-1} \Fo$ to planar isomorphisms, up to an
orthogonal transformation. Finally, notice that if $\det(A)>0$, then $\det(Q)>0$.
\end{proof}

\begin{exercise}
Prove that a closed form for $B_{\Fo}^{-1}$ in terms of the moments of~$\Fo$ can be computed by taking the inverse of
$B_{\Fo}$, the lower-triangular matrix given by the Cholesky decomposition of $S_\Fo$,
$$B_{\Fo}^{-1} =
\sqrt{\mu_{0,0}} \left(
\begin{array}{cc}
\frac{1}{\sqrt{\mu_{2,0}}} & 0 \\
-\frac{\mu_{1,1}}{\mu_{2,0}\sqrt{\mu_{0,2}-\frac{\mu_{1,1}^2}{\mu_{2,0}}}} &
\frac{1}{\sqrt{\mu_{0,2}-\frac{\mu_{1,1}^2}{\mu_{2,0}}}} \\
\end{array} \right).$$
\end{exercise}
The pre-normalized solid shape~$\Fo'= B_{\Fo}^{-1} \Fo$ is then an affine invariant representation of~$\Fo$ {\em
modulo} a rotation. In order to obtain a full affine invariant representation, only a reference angle is needed. This
can be achieved, for instance, by computing in polar coordinates
$$\varphi = {\rm Arg} \left (\int_0^{2\pi} \int_0^{+\infty}
 (B_{\Fo}^{-1}u)(r,\theta) e^{i\theta} r dr d\theta \right),$$ then rotating~$\Fo'$ by $-\varphi$.
\smallskip

Putting all the steps together, the support of the affine invariant normalization of $\Fo$ is the set of points
$(x_N,y_N)$ given by
$$ \left( \begin{array}{c} x_N\\ y_N \end{array} \right) =
\left( \begin{array}{cc} \cos\varphi & \sin\varphi \\ -\sin\varphi &
  \cos\varphi \\ \end{array} \right)B_{\Fo}^{-1}
 \left( \begin{array}{c} x-\mu_{1,0} \\ y-\mu_{0,1} \end{array}
 \right), $$
for all $(x,y) \in \Fo$.




\subsection{Maximally Stable Extremal Regions (MSER)\label{sec:MSER}}

The MSER method introduced by Matas et al.~\cite{matas02mser} attempts to achieve  affine invariance by selecting the
most robust connected components of upper and lower level sets as image features.

{\it Extremal regions} is the name given by the authors to  the connected components of  upper or lower level sets.
Maximally stable extremal regions, or MSERs, are defined as maximally contrasted regions in the following way.  let
$Q_1, . . . ,Q_{i-1},Q_i, . . . $ be a sequence of nested extremal regions, i.e. $Q_i \subset Q_{i+1}$ where $Q_i$ is
defined by a threshold at level $i$ or, in other terms, $Q_i$ is an upper (resp. lower) level set at level $i$. An
 extremal region in the list
$Q_{i_0}$ is said to be maximally stable if the area variation $q(i) = : |Q_{i+1}\setminus Q_{i-1}|/|Q_i|$
 has a local minimum at $i_0$, where $|Q|$ denotes the area of  a region $|Q|$. Clearly the above measure
  is a  measure of contrast along the boundary $\partial Q_i$ of $Q_i$. Indeed, assuming that $u$ is $C^1$
   and that the grey level increment
  between $i$ and $i+1$ is infinitesimal,
  the area $|Q_{i+1}\setminus Q_{i-1}|$ varies least when $\int_{\partial Q_i}
 |\nabla u|$ is maximal. The MSER extraction is a first step of image matching. Once MSERs are computed, the
affine normalization  of Section \ref{sect:cohignac} is performed on the MSERs  before they can be compared.  The fact
that the method is not fully scale invariant is easily explained with the experiment of Fig.
\ref{MSERnotscaleinvariant}. In MSER the scale normalization is based on the size (area) of the detected extremal
regions. However, scale change is not just a homothety: it involves a blur followed by sub-sampling. The blur changes
drastically the size of the regions. As pointed out in \cite{caolisanimorelmusesur} this entails a strong lack of scale
invariance. It could  only be compensated by simulating actual blur on the images, as made by the SIFT method.


\begin{figure}
\centering
\includegraphics[width=12cm]{figures/LimelightVariousScalesandLevelLines.eps}
\caption{\bf Shapes change with distance: The level lines not stable by down-sampling. This is the main problem with
level lines methods (MSER).\label{MSERnotscaleinvariant}}
\end{figure}



\section{Experiments\label{Experiments}}
A-SIFT image matching performance will be compared with the state-of-the-art approaches with the detectors
DoG~\cite{lowe04:_distin}, Hessian-Affine, Harris-Affine~\cite{MikolajczykS01, MikolajczykS04} and
MSER~\cite{matas02mser} all coded by the most popular SIFT descriptor~\cite{lowe04:_distin}. The MSER detector followed
by the correlation descriptor as proposed in the original work~\cite{matas02mser} is also included in the comparison,
whose performance will be shown slightly worse than that of the MSER detector followed by the SIFT descriptor. For
simplicity, in the text the methods will be named  respectively SIFT, Harris-Affine, Hessian-Affine and MSER for short.
(The MSER detector followed by the SIFT and the correlation descriptors are sometimes denoted as MSER+SIFT and
MSER+Corr. By MSER alone, we mean the MSER detector followed by either of the two descriptors.)

The Lowe~\cite{lowedemo} reference software was used for DoG with SIFT. For all the other methods we used the
Hessian-Affine, Harris-Affine and MSER descriptor code provided by the authors and combined them with the SIFT
descriptor implemented by Mikolajczyk, all downloadable from~\cite{mikolajczyk:www}.

Applications of A-SIFT and comparisons with the other methods will also be performed for video object tracing and
symmetry detection.

The experiments will show images taken from different viewpoints with varying tilts, zooms, and transition tilts.
Correspondences will be connected by white segments. Note that the parallelism or coherent directions of the connecting
lines usually indicates that most correspondences are correct.

All images under comparison have a low resolution $600 \times 450$. As reported under each figure, A-SIFT applied an
image sub-sampling of factor $K \times K$ with $K=3$ for most images. A very few  cases where objects of interest are
too small will be shown. In those cases A-SIFT only works with a more conservative subsampling  $K=2$, and in one case
only with $K=1$.


\subsection{Exploring tilts and zooms}

Fig.~\ref{camerapositions} illustrates the two settings that we have adopted to make systematic comparisons
respectively for evaluating the maximum absolute tilt and transition tilt attained by each algorithm. A magazine and a
painting shown in Fig.~\ref{fig:adam} were photographed for the experiments. Unlike SIFT and A-SIFT, the
Hessian-Affine, Harris-Affine and MSER detectors are not robust to scale change as shown in
Fig.~\ref{fig:numeric:scaleinv}. Therefore the pairs of images under comparison were chosen free of scale
change so that the evaluation is focused on the tilt invariance. \\

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\includegraphics[width=7cm]{./figures/fig1.eps}
&
\includegraphics[width=5cm]{./figures/transtilt.eps} \\
\textrm{a} & \textrm{b}
\\
\end{tabular}
% \includegraphics[width=10cm]{./figures/fig1.eps}
\end{center}
\caption{The settings adopted to systematic comparison. Left: absolute tilt test. An object is photographed with a
latitude angle $\theta$ (between the camera axis and the normal to the object) that varies from 0 degree (frontal view)
to 80 degrees, from distances varying between 1 and 10, which is the maximum focal distance change. Right: transition
tilt test. An object is photographed with a longitude angle $\phi$ (between the camera axis projected on the object
plane and a fixed direction thereon) that varies from 0 degree to 90 degrees, from a fixed distance.}
\label{camerapositions}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\includegraphics[width=5cm]{./figures/LePoint.eps}
&
\includegraphics[width=5cm]{./figures/Adam1.eps}
\\
\end{tabular}
\end{center}
\caption{The magazine cover and the painting are photographed in the experiments.} \label{fig:adam}
\end{figure}


\subsection{Absolute Tilt Tests}
The painting illustrated in Fig.~\ref{fig:adam} is photographed with a reflex camera, with distances varying between
$\times1$ and $\times10$, which is the maximum focal distance change, and with viewpoint angles between the camera axis
and the normal to the poster that varies from 0 degree (frontal view) to 80 degrees. It is clear that beyond 80
degrees, to establish a correspondence between the frontal image and the extreme viewpoint becomes absolutely
haphazard. Even when the photo acquisition conditions and the image resolution are excellent, with such a big view
angle change the observed surface becomes in general reflective, and the image in the resulting photo is totally
different from the frontal view. Nevertheless, A-SIFT works until 80 degrees, and it would be unrealistic to insist on
bigger angles.

%Fig.~\ref{camerapositions2} shows the thumbnails of the images taken from different viewpoints with a setting as shown
%in Fig.~\ref{camerapositions}. The triple of the numbers c/s/m placed above or below each image gives the number of
%correct correspondences obtained by A-SIFT (c) compared with those obtained by SIFT (s) and MSER (m).
Table~\ref{tab:numerical} summarizes performance of each algorithm in terms of number of correct matches. Some matching
results are illustrated in Figs.~\ref{fig:numeric:CSIFT:AdamZ1:45deg} to~\ref{fig:numeric:CSIFT:AdamZ10:84degR}.

One remarks first that MSER, which uses maximally stable level lines as features, obtains for most time much less
correspondences than other methods whose features are based on local maxima in the scale-space. This has been confirmed
by LLD, a novel image matching approach independently developed at ENS Cachan that applies also level lines as
features~\cite{cao:07,muse04:_acontrario}. Let us recall that robust image matching requires a sufficiently big number
of correspondences.

For images taken at short distance as illustrated in Figs.~\ref{fig:numeric:CSIFT:AdamZ1:45deg}
and~\ref{fig:numeric:CSIFT:AdamZ1:77degR}, tilt varies on the same flat object because of the perspective effect, as
illustrated in Fig.~\ref{anglevarie}. The number of SIFT correspondences drops dramatically when the angle is bigger
than 65 degrees (that corresponds to a tilt $t \approx 2.3$) and it fails completely when the angle exceeds 75 degrees
(tilt $t \approx 3.8$). At 65 and 75 degrees, as shown in Fig.~\ref{fig:numeric:CSIFT:AdamZ1:77degR}, most matches are
located on the side closer to the camera where the actual tilt is smaller. The performance of Harris-Affine and
Hessian-Affine degrades considerably when the angle goes over 75 degrees (tilt $t \approx 3.8$). The MSER
correspondences remain at a small number with a noticeable decline over 65 degrees (tilt $t \approx 2.4$). A-SIFT works
perfectly until 80 degrees (tilt $t \approx 5.8$).

Images taken at a camera-object distance multiplied by 10, as shown in Figs.~\ref{fig:numeric:CSIFT:AdamZ10:65deg}
and~\ref{fig:numeric:CSIFT:AdamZ10:84degR}, exhibits less perspective effects but contains less meaningful pixels at
big angles. For these images the SIFT performance drops considerably: recognition is possible only with angles smaller
than 45 degrees. The performance of Harris-Affine and Hessian-Affine declines clear when the angle goes from 45 to 65
degrees and beyond 65 degrees they fail completely. MSER struggles at the angle of 45 degrees and fails at 65 degrees.
A-SIFT again functions perfectly until 80 degrees.


\begin{figure}[htbp]
\begin{center}
 \includegraphics[width=4cm]{./figures/fig7.eps}
\end{center}
\caption{When the camera view angle is large, the absolute tilt of a plane object
 can vary considerably in the same image.} \label{anglevarie}
\end{figure}


\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\mathbf{Z \times 1}$  & SIFT & Haraff & Hesaff & MSER+Corr & MSER+SIFT & A-SIFT \\
\hline $-80^\circ$/5.8 & 1 & 16 & 1 & 3 & 4 & 110 \\
\hline $-75^\circ$/3.9 & 24 & 36 & 7 & 4 & 3 & 281 \\
\hline $-65^\circ$/2.3 & 117 & 43 & 36 & 6 & 5 & 483 \\
\hline $-45^\circ$/1.4 & 245 & 83 & 51 & 9 & 13 & 559 \\
\hline $45^\circ$/1.4  & 195 & 86 & 26 & 10 & 12 & 428 \\
\hline $65^\circ$/2.3 & 92 & 58 & 32 & 10 & 11 & 444 \\
\hline $75^\circ$/3.9 & 15 & 12 & 7 & 7 & 7 & 203 \\
\hline $80^\circ$/5.8 & 2 & 6 & 6 & 5 & 5 & 204 \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\mathbf{Z \times 10}$ & SIFT & Haraff & Hesaff & MSER+Corr & MSER+SIFT & A-SIFT \\
\hline $-80^\circ$/5.8 & 1 & 3 & 0 & 4 & 4 & 116 \\
\hline $-75^\circ$/3.9 & 0 & 3 & 0 & 6 & 6 & 265 \\
\hline $-65^\circ$/2.3 & 10 & 22 & 16 & 7 & 10 & 542 \\
\hline $-45^\circ$/1.4 & 182 & 68 & 45 & 18 & 19 & 722 \\
\hline $45^\circ$/1.4  & 171 & 54 & 26 & 14 & 15 & 707 \\
\hline $65^\circ$/2.3 & 5 & 12 & 5 & 5 & 6 & 468 \\
\hline $75^\circ$/3.9 & 2 & 1 & 0 & 4 & 4 & 152 \\
\hline $80^\circ$/5.8 & 3 & 0 & 0 & 4 & 2 & 110 \\
\hline
\end{tabular}
\end{center}
\caption{Absolute tilt invariance comparison. Summary of the results of the experiments that compare A-SIFT with SIFT,
Harris-Affine (HarAff), Hessian-Affine (HesAff), MSER coded by the correlation descriptor (MSER+Corr) and by the SIFT
descriptor (MSER+SIFT) for viewpoint angles between 45 and 80 degrees. Top: images taken with zoom $\times 1$. Bottom:
images taken with zoom $\times 10$. (The camera-object distance is 10 times  bigger.) The latitude angles and the
absolute tilts are listed in the left column. With zoom $\times1$, the actual tilt varies on the same object varies
around the marked value due to the perspective effect. } \label{tab:numerical}
\end{table}


% Zoom
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=4cm]{./figures/Zoom8p1vs1p3_ASIFT_222matches.eps}
\hspace{-7ex} &
\includegraphics[width=4cm]{./figures/Zoom8p1vs1p3_SIFT_87matches.eps}
\hspace{-7ex} &
\includegraphics[width=4cm]{./figures/Zoom8p1vs1p3_HarAff_matches.eps} \vspace{-4ex}  \\
\end{tabular}
\end{center}
\caption{Robustness to scale change.  A-SIFT (shown), SIFT (shown), Harris-Affine (shown), Hessian-Affine, MSER+Corr
and MSER+SIFT find respectively 221, 86, 4, 3, 3 and 4 correct matches. Harris-Affine, Hessian-Affine and MSER are not
robust to scale change. A-SIFT is implemented with $K=2$, which means that $K=3$ doesn't work.}
\label{fig:numeric:scaleinv}
\end{figure}


%AdamZ1:45deg
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-7ex}
\includegraphics[width=4.5cm]{./figures/adam_zoom10_front-adam_zoom1_45deg_ASIFT_626matches.eps}
\hspace{-7ex} &
\includegraphics[width=5cm]{./figures/adam_zoom10_front-adam_zoom1_45deg_SIFT_236matches.eps}
\hspace{-7ex} &
\includegraphics[width=5cm]{./figures/adam_zoom10_front-adam_zoom1_45deg_HarAff_28matches.eps} \vspace{-4ex}  \\
\end{tabular}
\end{center}
\caption{Correspondences between the painting images taken from short distance (zoom $\times 1$) at frontal view and at
$-45^\circ$ angle. The absolute tilt varies: $t=2$ (middle), $t<2$ (left part), $t>2$ (right part). A-SIFT (shown),
SIFT (shown), Harris-Affine (shown), Hessian-Affine, MSER+Corr and MSER+SIFT find respectively 624, 236, 28, 15, 7 and
11 correct matches. A-SIFT is implemented with $K=3$.} \label{fig:numeric:CSIFT:AdamZ1:45deg}
\end{figure}

%AdamZ1:45deg
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=4.5cm]{./figures/adam_zoom10_front-adam_zoom1_77degR_ASIFT_202matches.eps}
\hspace{-7ex} &
\includegraphics[width=5cm]{./figures/adam_zoom10_front-adam_zoom1_77degR_SIFT_15matches.eps}
\hspace{-7ex} &
\includegraphics[width=5cm]{./figures/adam_zoom10_front-adam_zoom1_77degR_MserSift_5matches.eps}
\\
\end{tabular}
\end{center}
\caption{Correspondences between the painting images taken from short distance (zoom $\times 1$) at frontal view and at
$75^\circ$ angle. The local absolute tilt varies:  $t=4$ (middle), $t<4$ (right part), $t>4$ (left part).  A-SIFT
($K=3$, shown), SIFT (shown), Harris-Affine, Hessian-Affine, MSER+Corr and MSER+SIFT (shown) find respectively 202, 15,
3, 1, 5 and 5 correct matches. } \label{fig:numeric:CSIFT:AdamZ1:77degR}
\end{figure}

%AdamZ1:45deg
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=4.2cm]{./figures/adam_zoom10_front-adam_zoom10_65degR_ASIFT_341matches.eps}
\hspace{-7ex} &
\includegraphics[width=4.5cm]{./figures/adam_zoom10_front-adam_zoom10_65degR_SIFT_5matches.eps}
\hspace{-7ex} &
\includegraphics[width=4.5cm]{./figures/adam_zoom10_front-adam_zoom10_65degR_HarAff_3matches.eps} \vspace{-4ex}  \\
\end{tabular}
\end{center}
\caption{Correspondences between  long distance snapshots (zoom $\times 10$) at frontal and  $65^\circ$ angle, absolute
tilt $t=2.4$. A-SIFT ($K=3$, shown), SIFT (shown), Harris-Affine (shown), Hessian-Affine, MSER+Corr and MSER+SIFT find
respectively 341, 5, 3, 0, 3 and 4 correct matches.} \label{fig:numeric:CSIFT:AdamZ10:65deg}
\end{figure}

%AdamZ1:45deg
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=4.2cm]{./figures/adam_zoom10_front-adam_zoom10_84deg_ASIFT_77matches.eps}
\hspace{-7ex} &
\includegraphics[width=4.5cm]{./figures/adam_zoom10_front-adam_zoom10_84deg_MserCorr_2matches.eps}
\hspace{-7ex} &
\includegraphics[width=4.5cm]{./figures/adam_zoom10_front-adam_zoom10_84deg_MserSift_2matches.eps}
\\
\end{tabular}
\end{center}
\caption{Correspondences between  long distance views (zoom $\times 10$), frontal view and $80^\circ$ angle, absolute
tilt $t=5.8$.  A-SIFT ($K=3$, shown), SIFT, Harris-Affine, Hessian-Affine, MSER+Corr (shown) and MSER+SIFT (shown) find
respectively 75, 1, 1, 0, 2 and 2 correct matches.} \label{fig:numeric:CSIFT:AdamZ10:84degR}
\end{figure}


Rich in highly contrasted regions, the magazine shown in Fig.~\ref{fig:adam} is more favorable to MSER.
Table~\ref{tab:comparison:absolute:tilt} shows the result of a similar experiment performed with the magazine, with the
latitude angles from 50 to 80 degrees on one side and with the camera focus distance $\times 4$.
Fig.~\ref{fig:numeric:CSIFT:V1} shows the result with 80-degree angle. The performance of SIFT, Harris-Affine and
Hessian-Affine drops dramatically with the angle going from 50 to 60 degrees (tilt $t$ from 1.6 to 2). Beyond 60
degrees (tilt $t=2$) they all fail completely. MSER finds many correspondences until 70 degrees (tilt $t \approx 2.9$).
The number drops considerably when the angle exceeds 70 degrees and becomes too small at 80 degrees (tilt $t \approx
5.8$) for robust recognition. A-SIFT works perfectly until 80 degrees.

The above experiments lead us to the following conclusion of the maximum absolute tilts of the approaches under
comparison. SIFT exceeds hardly an absolute of 2 and the limit is about 2.5 for Harris-Affine and Hessian-Affine. The
performance of MSER depends heavily on the types of image. For images with highly contrasted regions, MSER reaches an
absolute tilt about 5. However if the images do not contain highly contrasted regions, the performance of MSER is very
limited even under small tilts. For A-SIFT, an absolute tilt of 5.8 that corresponds to an extreme viewpoint angle of
80 degrees does not pose any difficulty to achieve robust recognition.
\\

\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
 & SIFT & Haraff & Hesaff & MSER+Corr & MSER+SIFT & A-SIFT \\
\hline $50^\circ$/1.6 & 267 & 131 & 144 & 129 & 150 & 1692 \\
\hline $60^\circ$/2.0 & 20 & 29 & 39 & 88 & 117 & 1012 \\
\hline $70^\circ$/2.9 & 1 & 2 & 2 & 48 & 69 & 754 \\
\hline $80^\circ$/5.8 & 0 & 0 & 0 & 10 & 17 & 267 \\
\hline
\end{tabular}
\end{center}
\caption{Absolute tilt invariance comparison. Summary of the results of the experiments that compare A-SIFT with SIFT,
Harris-Affine (HarAff), Hessian-Affine (HesAff), MSER coded by the correlation descriptor (MSER+Corr) and by the SIFT
descriptor (MSER+SIFT) for viewpoint angles between 50 and 80 degrees. The latitude angles and the absolute tilts are
listed in the left column.} \label{tab:comparison:absolute:tilt}
\end{table}

% V1
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=5cm]{./figures/V1A0vsV1A8_ASIFT_349matches.eps}
\hspace{-7ex} &
\includegraphics[width=5cm]{./figures/V1A0vsV1A8_MserCorr_10matches.eps}
\hspace{-7ex} &
\includegraphics[width=5cm]{./figures/V1A0vsV1A8_MserSift_17matches.eps}
\\
\end{tabular}
\end{center}
\caption{Correspondences between images taken  with zoom $\times 4$, frontal view and $80^\circ$ angle, absolute tilt
$t=5.8$.  A-SIFT (shown, $K=3$), SIFT, Harris-Affine, Hessian-Affine, MSER+Corr (shown) and MSER+SIFT (shown) find
respectively 349, 0, 0, 0, 10 and 17 correct matches.} \label{fig:numeric:CSIFT:TR:Adam3} \label{fig:numeric:CSIFT:V1}
\end{figure}

\subsection{Transition Tilt Tests}
The magazine shown in Fig.~\ref{fig:adam} is place face-up and photographed by a reflex camera and makes two sets of
images. As illustrated in Fig.~\ref{camerapositions}-b, for each image set, the camera with a fixed latitude angle
$\theta$, i.e., a fixed absolute tilt $t$ of respectively 2 and 4, circles around with the longitude angle $\phi$ going
from 0 to 90 degrees. The camera focus distance is $\times4$. In each set the images have the same absolute tilt $t$
while the transition tilt $\tau$ (with respect to the image taken at $\phi=0$ degree) goes from $1$ to $t^2$ when
$\phi$ goes from 0 to 90 degrees. To evaluate the maximum transition tilt, the images taken at $\phi \neq 0$ are
matched against the one taken at $\phi=0$.

Table~\ref{tab:comparison:transtilt} compares the performance of the algorithms. The number of matches under the
absolute tilt $t=2$ shows clearly that performance of SIFT drops dramatically when the transition tilt goes from 1.3 to
1.7. With a transition tilt over 2.1, SIFT fails completely. Similarly a considerable performance decline is observed
for Harris-Affine and Hessian-Affine when the transition tilt goes from 1.3 to 2.1. Hessian-Affine slightly outperform
Harris-Affine but both methods fail completely when the transition tilt goes above 3. MSER and A-SIFT works stably
until the transition tilt goes to 4. A-SIFT distinguishes itself by finding more than 10 times as many as those of MSER
that cover a much larger area, as illustrated in Fig.~\ref{fig:numeric:CSIFT:H8}.

Under an absolute tilt $t=4$, SIFT, Harris-Affine and Hessian-Affine struggle at a transition tilt of $1.9$ having
comparable number of matches. They fail completely when the transition tilt goes bigger. MSER works stably until a
transition tilt of 7.7. Over this value, the number of correspondences is too small for reliable recognition. A-SIFT
works perfectly.

The transition tilt is a crucial notion that evaluates the degree of affine invariance of the image comparison
algorithms. With the ordinary viewpoint changes the transition tilt goes easily to a big value (above 16 for example).
The experiments above show that the maximum transition tilt, about 2 for SIFT and 2.5 for Harris-Affine and
Hessian-Affine, is by far not enough. MSER enables reliable recognition until a transition tilt of about 10, under the
condition that the images under comparison are free of scale change and contain highly contrasted regions. The limit of
A-SIFT goes beyond 16 largely. Images that have undergone transition tilts up to 30 and more can be reliably recognized
by A-SIFT, an example being illustrated in Fig.~\ref{fig:numeric:CSIFT:extreme:tilt}.

\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\phi_2$/$\tau$ $t=2$ & SIFT & Haraff & Hesaff & MSER+Corr & MSER+SIFT & A-SIFT \\
\hline $10^\circ$/1.3 & 408 & 233 & 176 & 110 & 124 & 1213 \\
\hline $20^\circ$/1.7 & 49 & 75 & 84 & 96 & 122 & 1173 \\
\hline $30^\circ$/2.1 & 5 & 24 & 32 & 85 & 103 & 1048 \\
\hline $40^\circ$/2.5 & 3 & 13 & 29 & 71 & 88 & 809 \\
\hline $50^\circ$/3.0 & 3 & 1 & 3 & 70 & 87 & 745 \\
\hline $60^\circ$/3.4 & 2 & 0 & 1 & 50 & 62 & 744 \\
\hline $70^\circ$/3.7 & 0 & 0 & 0 & 34 & 51 & 557 \\
\hline $80^\circ$/3.9 & 0 & 0 & 0 & 40 & 51 & 589 \\
\hline $90^\circ$/4.0 & 0 & 0 & 1 & 41 & 56 & 615 \\
\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
  $\phi_2$/$\tau$$t=4$ & SIFT & Haraff & Hesaff & MSER+Corr & MSER+SIFT & A-SIFT \\
\hline $10^\circ$/1.9 & 22 & 32 & 14 & 38 & 49 & 1054 \\
\hline $20^\circ$/3.3 & 4 & 5 & 1 & 32 & 39 & 842 \\
\hline $30^\circ$/5.3 & 3 & 2 & 1 & 24 & 32 & 564 \\
\hline $40^\circ$/7.7 & 0 & 0 & 0 & 22 & 28 & 351 \\
\hline $50^\circ$/10.2 & 0 & 0 & 0 & 15 & 19 & 293 \\
\hline $60^\circ$/12.4 & 1 & 0 & 0 & 12 & 17 & 145 \\
\hline $70^\circ$/14.3 & 0 & 0 & 0 & 6 & 13 & 90 \\
\hline $80^\circ$/15.6 & 0 & 0 & 0 & 6 & 12 & 106 \\
\hline $90^\circ$/16.0 & 0 & 0 & 0 & 5 & 9 & 88 \\
\hline
\end{tabular}

\end{center}
\caption{Transition tilt invariance comparison. Summary of the results of the experiments that compare A-SIFT with
SIFT, Harris-Affine (HarAff), Hessian-Affine (HesAff), MSER coded by the correlation descriptor (MSER+Corr) and by the
SIFT descriptor (MSER+SIFT). The affine parameters of the two images are $\phi_1=0^\circ$, $t_1=t_2=2$ (above),
$t_1=t_2=4$ (below). $\phi_2$ and the transition tilts $\tau$ are in the left column.} \label{tab:comparison:transtilt}
\end{table}


\begin{figure}[]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=5cm]{./figures/H8A0vsH8A5_ASIFT_881matches.eps}
\hspace{-7ex} &
\includegraphics[width=5cm]{./figures/H8A0vsH8A5_MserCorr_70matches.eps}
\hspace{-7ex} &
\includegraphics[width=5cm]{./figures/H8A0vsH8A5_MserSift_87matches.eps}
\end{tabular}
\end{center}
 \caption{Correspondences with absolute tilts $t_1=t_2=2$ and longitude
angles $\phi_1=0^\circ$ and $\phi_2=50^\circ$, transition tilt $\tau=3$. A-SIFT ($K=3$, shown), SIFT, Harris-Affine,
Hessian-Affine, MSER+Corr (shown) and MSER+SIFT (shown) find respectively 881, 2, 0, 2, 70 and 87 correct matches. }
\label{fig:numeric:CSIFT:H8}
\end{figure}

% H6
\subsection{Comparative experiments}

Fig. \ref{fig:numeric:CSIFT:TR:tree} compares the A-SIFT image matching with SIFT, Harris-Affine, Hessian-Affine and
MSER. Table~\ref{tab:comparison} summarizes the results. Fig.~\ref{fig:numeric:CSIFT:TR:facade1vs8} shows images of a
building facade taken from very different viewpoints. The transformation of the rectangle facade on the left to a
trapezia on the right indicates that the transformation is not affine, but strongly perspective. Nevertheless, since a
projective transformation can be locally modeled by affine transforms, a large number of correspondences is established
by A-SIFT. All the other methods fail. Fig.~\ref{fig:numeric:CSIFT:TR:graf1vs6} shows the results of the standard test
pair Graffiti 1 and Graffiti 6 proposed by Mikolajczyk~\cite{mikolajczyk:www}. A-SIFT finds 724 correspondences, out of
which 3 are false. SIFT, Harris-Affine and Hessian-Affine find respectively 0, 3 and 1 correct correspondences: the
$\tau = 3.2$ transition tilt is just a bit too large.  MSER+Corr and MSER+SIFT find respectively 50 and 70 correct
correspondences. Proposed by Matas et al. in their online demo~\cite{matas02demo} as a standard image to test
MSER~\cite{matas02mser}, the images in Fig.~\ref{fig:numeric:CSIFT:TR:boxes} show a number of containers placed on a
desktop~\footnote{We thank Michal Perdoch for having kindly provided us with the images.}. A-SIFT finds 194 correct
correspondences. SIFT, Harris-Affine, Hessian-AFfine, MSER+Corr and MSER+SIFT find respectively 10, 23, 11, 16 and 22
correct correspondences. Let us note that images in Figs.~\ref{fig:numeric:CSIFT:TR:graf1vs6}
and~\ref{fig:numeric:CSIFT:TR:boxes} provide optimal conditions for MSER: the camera-object distances are similar and
well contrasted shapes are present. But let us recall that MSER fails under large scale changes or when well contrasted
shapes are not present. Fig.~\ref{fig:numeric:CSIFT:TR:direction} contains two orthogonal road signs taken under a view
change that makes a transition tilt $\tau\approx2.6$. A-SIFT successfully matches the two signs finding 50
correspondences while all the other methods totally fail.  The monument shown in Fig.~\ref{fig:numeric:CSIFT:TR:EP} has
undergone a viewpoint change of latitude angle 65 degrees (tilt t=2.4). A-SIFT works perfectly and finds 101 correct
correspondences. SIFT struggles by establishing 13 correspondences. Harris-Affine, Hessian-Affine, MSER+Corr and
MSER+SIFT fail finding only 2, 2, 5 and 4 matches. In Fig.~\ref{fig:numeric:CSIFT:TR:tree} is the stump taking from
different viewpoints which makes a transition tilt $\tau\approx2.6$. A-SIFT achieved success finding 168 correct
correspondences while all the other methods fail.

Fig.~\ref{fig:numeric:CSIFT:TR:coffee} illustrates a complex scene in a coffee room in which divers objects are
presented. A-SIFT recognizes the scene by finding 125 correspondences over six non-coplanar objects. SIFT finds 11
correspondence on the wall and 2 on the box over the fridge. Other methods fail finding at most a few correspondences
on the wall. Fig.~\ref{fig:numeric:CSIFT:TR:can} shows a coffee can that has been rotated for about 120 degrees. Over
the cylinder transition tilt varies continuously and reaches big values. A-SIFT identifies 287 correspondences that
cover almost all visible common areas. SIFT fails completely due to the too large viewpoint change. Harris-Affine and
Hessian Affine fail by finding 3 and 6 correspondences. MSER finds a small number of correspondences that cover only
part of letters that provide highly contrasted regions but it does not catch anything on the image part on the lower
half of the can.   The Palace of Versaille in Fig.~\ref{fig:numeric:CSIFT:TR:coffee} undertakes a viewpoint change of
about 50 degrees. A-SIFT detect 67 matches uniformly distributed on the facade that can be viewed in the two images.
SIFT finds 26 correspondences, mostly located in the closer end where the transition tilt is smaller due to the
perspective effect. The other methods fail completely by finding zero or sporadic correspondences.



\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline Fig./$\tau$& SIFT & Haraff & Hesaff & MSER1 & MSER2 & A-SIFT \\
\hline Fig.~A/3.0 & 0 & 0 & 1 &
3 & 3 & 58 \\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:facade1vs8}/3.8 & 0 & 0 & 1 &
0 & 2 & 68 \\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:graf1vs6}/3.2 & 0 & 3 & 1 &
50& 50 & 721 \\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:boxes}/[1.6,3.0] & 10 & 23 & 11 & 16
& 22 & 254 \\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:direction}/2.6 & 0 & 0 & 0 & 0
& 1 & 50 \\
\hline Fig.~B/15.0 & 0 & 0 & 0 & 0
& 0 & 78 \\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:EP}/2.4 & 13 & 2 & 2 & 5
& 4 & 101 \\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:tree}/2.6 & 1 & 2 & 1 & 6
& 6 & 168 \\
\hline Fig.~C/[1.6, $\infty$]& 26 & 7 & 2 & 3
& 4 & 143 \\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:coffee}/[1.5, 3.3] & 13 & 0 & 3 & 5
& 2 & 125 \\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:can}/[2.3, $\infty$] & 0 & 6 & 3 & 12
& 22 & 287 \\
\hline Fig.~D/[2, $\infty$] & 19 & 5 & 7 & 7
& 13 & 123\\
\hline Fig.~\ref{fig:numeric:CSIFT:TR:versaille}/1.8 & 67 & 26 & 2 &
1 & 0 & 4\\
 \hline
\end{tabular}
\end{center}
\caption{Summary of the results of the experiments that compare A-SIFT with SIFT, Harris-Affine (HarAff),
Hessian-Affine (HesAff), MSER coded by the correlation descriptor (MSER+Corr) and by the SIFT descriptor (MSER+SIFT).
The transition tilts or their ranges are listed in the left column. The figures with Latin numbers are not shown in the
text.} \label{tab:comparison}
\end{table}


% OutdoorX
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\hspace{-5.5ex}
\includegraphics[width=5.8cm]{./figures/Xlab1vs14_CAffine2_71match.eps}
\hspace{-0.5ex}
\includegraphics[width=6.5cm]{./figures/outdoor1vs14_MserSift_2matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching: Facade. Absolute (and transition) tilt $t = 3.8$ ($\theta=75 ^\circ$). A-SIFT, SIFT,
Harris-Affine, Hessian-Affine, MSER+Corr and MSER+SIFT find respectively 68, 0, 1, 1, 0 and 2 correct matches.  A-SIFT
is implemented with $K=2$, which means that $K=3$ doesn't work Results shown: A-SIFT and MSER+SIFT}
\label{fig:numeric:CSIFT:TR:facade1vs8}
\end{figure}


% Graffiti
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\hspace{-5.5ex}
\includegraphics[width=5.8cm]{./figures/Graf1vs6_CAffine2_724match.eps}
\hspace{-0.5ex}
\includegraphics[width=6.5cm]{./figures/graf1vs6_MserSift_71matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching between Graffiti 1 and Graffiti 6. Transition tilt: $\tau \approx 3.2$. From top to bottom,
left to right: A-SIFT, SIFT, Harris-Affine, Hessian-Affine, MSER+Corr and MSER+SIFT find respectively 721, 0, 3, 1, 50
and 70 correct matches. A-SIFT is implemented with $K=3$. Results shown: A-SIFT and MSER+SIFT}
\label{fig:numeric:CSIFT:TR:graf1vs6}
\end{figure}

% MSER
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\hspace{-5.5ex}
\includegraphics[width=5.8cm]{./figures/MSERimage1_CAffine2sides_MR1_M10_ratio0p5_255match.eps}
\hspace{-0.5ex}
\includegraphics[width=5.8cm]{./figures/MSERimage1_SIFT_16match.eps}
\\
\end{tabular}
\begin{tabular}{cc}
\hspace{-5.5ex}
\includegraphics[width=6.5cm]{./figures/MSERimage1_HesAff_11matches.eps}
\hspace{-5.5ex}
 \includegraphics[width=6.5cm]{./figures/MSERimage1_MserSift_22matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching (images proposed by Matas et al~\cite{matas02demo}). Transition tilt: $\tau \in [1.6, 3.0]$.
From top to bottom, left to right: A-SIFT (shown), SIFT (shown), Harris-Affine, Hessian-Affine (shown), MSER+Corr and
MSER+SIFT (shown) find respectively 254, 10, 23, 11, 16 and 22 correct matches. A-SIFT is implemented with $K=3$.}
\label{fig:numeric:CSIFT:TR:boxes}
\end{figure}

% Direction
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\hspace{-2ex}
\includegraphics[width=6cm]{./figures/direction1vs3-AISFT-50matches_bis.eps}
\hspace{-2ex}
\includegraphics[width=7cm]{./figures/direction1vs2_MserSift_1matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching: road signs. Transition tilt $\tau \approx 2.6$.   A-SIFT (shown), SIFT, Harris-Affine,
Hessian-Affine, MSER+Corr and MSER+SIFT (shown) find respectively 50, 0, 0, 0, 0 and 1 correct matches. A-SIFT is
implemented with $K=3$. } \label{fig:numeric:CSIFT:TR:direction}
\end{figure}

% Parking
% Polytechnique
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=6cm]{./figures/EP1vs3_ASIFT_102matches.eps}
\includegraphics[width=6cm]{./figures/EP1vs3_MserSift_10matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching: Ecole Polytechnique. Absolute (and transition) tilt $t \approx 2.4$ ($\theta=65^\circ$).
A-SIFT (shown), SIFT, Harris-Affine, Hessian-Affine, MSER+Corr and MSER+SIFT (shown) find respectively 101, 13, 2, 2, 5
and 4 correct matches. A-SIFT is implemented with $K=3$.} \label{fig:numeric:CSIFT:TR:EP}
\end{figure}


% tree
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=6cm]{./figures/tree1vs2_ASIFT_168matches.eps}
\hspace{-7ex} &
\includegraphics[width=6cm]{./figures/tree1vs2_MserSift_6matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching: stump. Transition tilt $\tau\approx2.6$.
  A-SIFT (shown), SIFT, Harris-Affine,
Hessian-Affine, MSER+Corr and MSER+SIFT (shown) find respectively 168, 1, 2, 1, 6 and 6 correct matches. A-SIFT is
implemented with $K=3$.} \label{fig:numeric:CSIFT:TR:tree}
\end{figure}



% Cafe
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\hspace{-9ex}
\includegraphics[width=7cm]{./figures/sallecafe2vs3_ASIFT_128matches.eps}
\hspace{-10ex} &
\includegraphics[width=7cm]{./figures/sallecafe2vs3_MserSift_6matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching: coffee room. Transition tilt $\tau \in [1.5, 3.3]$.  A-SIFT (shown), SIFT, Harris-Affine,
Hessian-Affine, MSER+Corr and MSER+SIFT (shown) find respectively 125, 13, 0, 3, 5 and 2 correct matches. A-SIFT is
implemented with $K=1$, which gives one of the very few examples where details in one of the images are so small that
$K=2$ and $K=3$ do not work.} \label{fig:numeric:CSIFT:TR:coffee}
\end{figure}

% Cans
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\hspace{-9ex}
\includegraphics[width=12cm]{./figures/malongo1vs3_ASIFT_288matches.eps}
\hspace{-10ex} \\
\includegraphics[width=12cm]{./figures/malongo1vs3_MserSift_22matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching: can. Transition tilt $\tau \in [2.3, \infty]$.  A-SIFT (shown), SIFT, Harris-Affine,
Hessian-Affine, MSER+Corr and MSER+SIFT (shown) find respectively 287, 0, 6, 3, 12 and 22 correct matches.   A-SIFT is
implemented with $K=2$, which means that $K=3$ doesn't work} \label{fig:numeric:CSIFT:TR:can}
\end{figure}


% Versaille
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-5ex}
\includegraphics[width=4cm]{./figures/versaille1vs3_ASIFT_73matches.eps}
\hspace{-7ex} &
\includegraphics[width=4cm]{./figures/versaille1vs3_SIFT_28matches.eps}
\hspace{-7ex} &
\includegraphics[width=4cm]{./figures/versaille1vs3_MserSift_7matches.eps}
\\
\end{tabular}
\end{center}
\caption{Image matching: Palace of Versailles. Transition tilt $\tau=1.8$. A-SIFT (shown), SIFT (shown), Harris-Affine,
Hessian-Affine, MSER+Corr and MSER+SIFT (shown) find respectively 67, 26, 2, 1, 0 and 4 correct matches. A-SIFT is
implemented with $K=3$.} \label{fig:numeric:CSIFT:TR:versaille}
\end{figure}




\subsection{Symmetry detection in perspective}
Symmetry detection has drawn considerable attention in computer vision and has been used for numerous applications such
as image indexing, completion of occluded shapes, object detection, facial image analysis and visual attention (see,
for example,~\cite{Cornelius06} for a survey). The image projection is usually approximated by plane affine transforms
for symmetry detection in perspective~\cite{Mukherjee94}. Some recent works apply SIFT, MSER and other affine-invariant
detectors and descriptors to detect bilateral symmetry~\cite{Loy06, Cornelius06}. Conversely, symmetry has been used to
extract affine-invariant image features~\cite{Anjulan05}.

The image matching algorithm can be used to detect bilateral symmetry in an image $\bu$, by simply looking
  for correspondences between
$\bu(x,y)$ and its flipped version $\bu(-x,y)$. After being flipped, symmetric structures become either identical if
taken in frontal view, or identical up to an oblique view otherwise. A correspondence between $\bu(x,y)$ and
$\bu(-x,y)$ therefore connects a pair of bilateral symmetrical points in $\bu(x,y)$. Fig.~\ref{fig:symmetry:detection}
shows some examples of bilateral symmetry detection obtained by A-SIFT, SIFT, Harris-Affine, Hessian-Affine, MSER+Corr
and MSER+SIFT. A-SIFT that has the best performance on affine invariant image matching, results in the best symmetry
detection in perspective.


% Graffiti
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cccccc}
\hspace{-3ex}
\includegraphics[width=2.55cm]{./figures/Admiral_sym_CAffine_v2_crop.eps} &
\hspace{-3ex}
\includegraphics[width=2.5cm]{./figures/Admiral_sym_SIFT.eps}
%& \hspace{-3ex}
%\includegraphics[width=2.5cm]{./figures/Admiral_sym_HarAff.eps}
& \hspace{-3ex}
\includegraphics[width=2.5cm]{./figures/Admiral_sym_HesAff.eps}
& \hspace{-3ex}
%\includegraphics[width=2.5cm]{./figures/Admiral_sym_MserSift.eps}
%& \hspace{-3ex}
\includegraphics[width=2.5cm]{./figures/Admiral_sym_MserSift.eps}
\end{tabular}
\begin{tabular}{cccccc}
 \hspace{-3ex}
\includegraphics[width=2.53cm]{./figures/ButterflyBK_sym_CAffine_v2_crop.eps} &
\hspace{-3ex}
\includegraphics[width=2.5cm]{./figures/ButterflyBK_sym_SIFT.eps}
& \hspace{-3ex}
%\includegraphics[width=2.5cm]{./figures/ButterflyBK_sym_HarAff.eps}
%& \hspace{-3ex}
\includegraphics[width=2.5cm]{./figures/ButterflyBK_sym_HesAff.eps}
& \hspace{-3ex}
%\includegraphics[width=2.5cm]{./figures/ButterflyBK_sym_MserCorr.eps}
%& \hspace{-3ex}
\includegraphics[width=2.5cm]{./figures/ButterflyBK_sym_MserSift.eps}
\\
\end{tabular}
\end{center}
\caption{Symmetry detection in perspective. From left to right: detection results by A-SIFT, SIFT, Hessian-Affine,
  MSER+SIFT.} \label{fig:symmetry:detection}
\end{figure}


\section{Comments and references}


David Pritchard's master thesis  was  a first step toward  A-SIFT.
  Quoting \cite{pritchard2003cmc} in his 2003 master thesis  on cloth parameters and motion capture:

\begin{quotation} Cloth strongly
resists stretching, but permits substantial bending; folds and wrinkles are a distinctive characteristic of cloth. This
behaviour means that sections of the cloth are often seen at oblique angles, leading to large affine distortions of
features in certain regions of the cloth. Unfortunately, SIFT features are not invariant to large affine
distortions.(...) To compensate for this, we use an expanded set of reference features. We generate a new reference
image by using a 2 x 2 transformation matrix T to scale the reference image by half horizontally. We repeat three more
times, scaling vertically and along axes at 45 degrees, as shown in Figure 5.3. This simulates different oblique views
of the reference image. For each of these scaled oblique views, we collect a set of SIFT features. Finally, these new
SIFT features are merged into the reference feature set. When performing this merge, we must adjust feature positions,
scales and orientations by using T-1. This approach is compatible with the recommendations made by Lowe for correcting
SIFT's sensitivity to affine change.
\end{quotation}}


In recent years local image detectors have bloomed. They can be classified by their incremental invariance properties.
All of them are translation invariant. The Harris point detector~\cite{harris88combined} is also rotation invariant.
The Harris-Laplace, Hessian-Laplace and the DoG (Difference-of-Gaussian) region detectors~\cite{MikolajczykS01,
MikolajczykS04,lowe04:_distin, Fevrier07} are invariant to rotations and changes of scale. Some moment-based region
detectors~\cite{DBLP:conf/eccv/LindebergG94, baumberg00:_reliab} including the Harris-Affine and Hessian-Affine region
detectors~\cite{MikolajczykS02, MikolajczykS04}, an edge-based region detector~\cite{TuytelaarsG99, TuytelaarsG04}, an
intensity- based region detector~\cite{TuytelaarsG00, TuytelaarsG04}, an entropy-based region
detector~\cite{KadirZB04}, and two  level line-based region detectors MSER (``maximally stable extremal
region'')~\cite{matas02mser} and LLD (``level line descriptor'')~\cite{ muse03unsupervised, muse04:_acontrario, cao:07}
are designed to be invariant to affine transformations. MSER, in particular, has been demonstrated to have often better
performance than other affine invariant detectors, followed by Hessian-Affine and Harris-Affine~\cite{mikolajczyk05}.


The  mentioned methods have a varying complexity. Measured in terms of their processing times, the fastest is MSER,
followed by Harris-Affine and Hessian-Affine. SIFT is ten times slower, but a recent acceleration has been proposed in
\cite{grabner}, that equals it to the other detectors.

 However, the mentioned affine invariant detectors aren't fully affine invariant.  As pointed out
in~\cite{lowe04:_distin}, they start with initial feature scales and locations selected in a non-affine invariant
manner. As shown in~\cite{cao:07}, MSER and LLD are not fully scale invariant, because they do not take into account
the drastic changes  of level lines due to blur.
 This is also the case for other image
local descriptors, such as the distribution-based shape context~\cite{628792}, the geometric histogram~\cite{243147}
descriptors, the derivative-based complex filters~\cite{baumberg00:_reliab, schaffalitzky02:_multi_match}, and the
moment invariants~\cite{648967}.


There is, however, at least one method dealing with scale (and therefore with blur) in a fully satisfactory way. In his
milestone paper~\cite{lowe04:_distin}, Lowe has proposed a scale-invariant feature transform (SIFT) descriptor that is
invariant to image scaling and rotation and partially invariant to illumination and viewpoint changes. Although
 SIFT  is {\it a priori} less invariant to affine transforms than other descriptors such as Hessian-Affine and
Harris-Affine~\cite{MikolajczykS01, MikolajczykS04}, its performance turns out to be comparable, as we shall see in
many experiments. Furthermore, SIFT  is really scale invariant (a mathematical proof of this fact is given in
\cite{GuoshenMorelSIFT}). A number of SIFT variants and extensions, including PCA-SIFT~\cite{DBLP:conf/cvpr/KeS04},
GLOH (gradient location-orientation histogram)~\cite{mikolajczyk05:_performance} and SURF (speeded up robust
features)~\cite{bay2006ssu}, that claim to have improved robustness and distinctiveness with scaled-down complexity
have been developed ever since~\cite{1273738, 1180760}. Demonstrated to be superior to many other
descriptors~\cite{MikolajczykS03, mikolajczyk05:_performance}, SIFT and its variants have been popularly applied for
scene recognition~\cite{1178710, DBLP:conf/nips/MoreelsP04, DBLP:conf/psivt/Ruiz-del-SolarLD07, veloso-learning,
DBLP:conf/clor/GordonL06, 1291311, 1274298, 1227683} and detection~\cite{DBLP:conf/scia/FritzSKP05,
DBLP:conf/sspr/NegreTGHLC06}, robot localization~\cite{bennewitz-metric, se01, and-scalable, joseph-building}, image
registration~\cite{single-alignment}, image retrieval~\cite{DBLP:conf/civr/HareL04}, motion tracking~\cite{1018380,
1029650}, 3D modeling and reconstruction~\cite{riggi06, 1231035}, building panoramas~\cite{1141966,
brown03recognising}, photo management~\cite{1242816, 1180737, 1141964, 1160945}, as well as symmetry
detection~\cite{Loy06}.








\subsubsection*{Sampling and interpolation}

Digital images, only defined for  $(n_1,n_2)\in\relative^2$, will be denoted by $\bu(n_1,n_2)$.
 The  sampled image
 $\bu=\SA_1 u$ is  defined on $\relative^2$ by \begin{equation} \bu(n_1,n_2)=(\SA_1u) (n_1,n_2)=:u(n_1,
n_2); \label{defsampling}\end{equation}

\subsubsection{The practical Shannon interpolation: zero-padding}   Let $a>0$ and consider a function $u$ from $[0,a]^2$
to $\real$ such that $u(x+a,y+a)=u(x,y)$. Fix an integer $N$, and consider the $N^2$ samples of $u$, $\bu_{k,l}=(\SA
u)\left(\frac{ka}{N},\frac{la}{N}\right)$ on $[0,a]^2$.

\begin{definition}\label{defDFT} The  discrete Fourier transform  (DFT) of  the $N^2$ samples
 $u=(u_{k,l})_{k,l=0,1,\dots, N-1}$ is  the double sequence of
discrete Fourier coefficients for $m,n \in \{-\frac N 2,...,\frac N 2 -1\}$ defined by
\begin{equation}
\label{TFD2} DFT(u)_{m,n}=
\tilde{u}_{m,n}=\frac{1}{N^2}\sum_{k=0}^{N\!-\!1}\sum_{l=0}^{N\!-\!1}u_{k,l}\omega_N^{-mk}\omega_N^{-nl },
\end{equation}
where $\omega_N=: e^{\frac{2i\pi}N}$ is the first $N$-root of 1.
\end{definition}

\begin{proposition}\label{inverseDFT}
Consider the trigonometric polynomial
\begin{equation}\label{definitionofIonasquare}I\bu(x,y)=\sum_{m,n=-\frac
N2}^{\frac N2-1}\tilde u_{m,n}\exp(\frac{2i\pi mx}{a})\exp(\frac{2i\pi ny}{a}).
\end{equation}
 Then its coefficients
$\tilde u_{m,n}$ are the only complex numbers such that for every  $k, l \in \{0, ..., N\!-\!1\}$,
$I\bu\left(\frac{ka}{N},\frac{la}{N}\right)=\bu\left(\frac{ka}{N},\frac{la}{N}\right)$. In consequence, the discrete
inverse transform of the DFT $\bu\to \tilde u$ is nothing but the calculation of the value of the polynomial at the
samples $(\frac {ka}N, \frac {la}N)$, $0\leq k,l\leq N\!-\!1$. In other terms, setting $\tilde{u}=DFT(\bu)$, the
inverse transform $DFT^{-1}$ is given by
$$\bu(k,l)=\sum_{-\frac N2}^{\frac N2-1}\sum_{-\frac N2}^{\frac
N2-1}\tilde \bu_{m,n}\omega_N^{km+ln},$$ for every $k,l =0,1,\dots N-1$.
\end{proposition}


\begin{exercise}  Recall that $\omega_N=\exp\left(\frac{2i\pi}{N}\right)$,  $N$-th root of 1. Show that
$\sum_{k=0}^{N\!-\!1}\omega_N^k=0$, and that $\sum_{k=0}^{N\!-\!1}\omega_N^{kl}=0$ for $l\neq 0$ modulo $N$ and finally
that for every $k_0$, $\sum_{k=k_0}^{k_0+N\!-\!1}\omega_N^{kl}=0$ for all $l\neq 0$ modulo $N$. Using these relation
show the above proposition, namely that $DFT(DFT^{-1})=Id$.\finex
\end{exercise}


\begin{proposition}\label{mainsamplinginterpolationframework} If $u(x,y)$ is a $a$-periodic  band-limited function, then it is a trigonometric polynomial.  If
 its highest degree is
$\frac N2-1$, with $N$ even, then its coefficients  $\tilde u_{m,n}$ are obtained by DFT from the samples
$\bu(k,l)=u(\frac{ka}N, \frac{la}N)$.
 In consequence for such functions we have $I\SA u=u$.
\end{proposition}

\subsubsection*{Zoom in by zero-padding} Let $(u_{k,l})$ be a digital image and define its zoomed version
$\left(v_{i,j}\right)_{i,j=0,\;...,\; 2N\!-\!1}$ as the inverse discrete Fourier transform of   $\tilde v_{i,j}$
defined for $i,j=-N,\;...,\;N\!-\!1$ by

\begin{equation}
\label{TFDzoom2}
 \tilde{v}_{m,n} = \tilde u_{m,n} \hbox{  if  } -\frac N2\leq m, n\leq \frac N2-1, \;\; \tilde
v_{m,n}=0
 \hbox {  otherwise}.
\end{equation}


\begin{proposition} \index{zoom discret par Fourier} \label{zeropadding}
The image $v$ whose Discrete Fourier Transform  is given by (\ref{TFDzoom2}) satisfies $v_{2k,2l}=u_{k,l}$, for $k,l=0,
..., N\!-\!1$.
\end{proposition}


\subsubsection{Gaussians}
  $G_\sigma$
denotes the  convolution operator on $\RR^2$  with  the gauss kernel $G_\sigma(x_1,x_2)=\frac
1{2\pi(\sigma)^2}e^{-\frac{x_1^2+x_2^2}{2(\sigma)^2}}$, namely $G_\sigma u(x,y)=: (G_\sigma \ast u)(x,y).$
\begin{equation}
\label{continuoussemigroupproperty}G_{\sigma} G_{\beta}= G_{\sqrt{\sigma^2+ \beta^2}}.\end{equation}

  \begin{equation}\label{commutationconvolutionzoomcontinus}G_\sigma  H_\gamma u=
H_\gamma G_{\sigma\gamma}  u.\end{equation}

\begin{definition}\label{definitiondiscretegaussianconvolution}
The {\bf discrete gaussian convolution} applied to a digital image $\bu$ is defined as a digital operator by
\begin{equation}\label{defGdelta} \bG_\delta \bu= : \SA_1 G_\delta I\bu.\end{equation}
\end{definition}

 \begin{proposition} This definition maintains the gaussian semi-group property,
\begin{equation}\label{discretesemigroupproperty}\bG_{\delta} \bG_{\beta}= \bG_{\sqrt{\delta^2+ \beta^2}}.\end{equation}
\end{proposition}

\begin{proposition}
 For every $\sigma$  larger than 0.8 and every continuous and bounded image $u_0$, the gaussian blurred image $G_\sigma
 u_0$ is well sampled, namely $I\bS_1G_\sigma u_0=G_\sigma u_0$.
\end{proposition}




\subsubsection{Discrete sampling\label{discretesetting}}

\begin{itemize}
\item  If $\bu$ is digital and therefore only defined on  $\relative^2$ and if $\delta$ is an integer, then one can
define any sub- or over-sampling operations on $\bu$. But this requires  interpolating $\bu$ first.   Thus we define a
{\it digital subsampling operator} by
\begin{equation}\label{defdiscretesampling}\SAD_\delta \bu=: \SA_\delta I\bu.\end{equation}   Notice  that
  $\SAD_\delta$  is a
discrete filter which can be interpreted as a {\rm re-sampling} operator.


\item Zooming in by oversampling. For every $\gamma\leq 1,$
\begin{equation}\label{commutationinterpolationsampling}
I\SAD_\gamma \bu=H_\gamma I\bu.\end{equation}


\item Corollary: If $\gamma\leq 1$, then \begin{equation}\label{compositionofsampling}
\SAD_\beta\SAD_\gamma=\SAD_{\beta\gamma}.\end{equation}


\item a discrete commutation formula :  Assume $\bu$ is a digital image. Then
  for $\gamma<1$,
\begin{equation}\label{discretecommutation}\bG_\beta \SAD_\gamma \bu=\SAD_\gamma \bG_{\beta\gamma}\bu.\end{equation}

\end{itemize}
