

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