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