# Normalizing Transform of a Feature¶

Let us remark the following proposition which relates the normalizing transform $$\bT_x$$ to the feature shape $$\bSigma_x$$.

Important

Let $$L$$ be an invertible linear transformation in $$\mathbb{R}^2$$ whose matrix is denoted by $$\bL$$. For any point $$\x$$ in the zero-centered unit circle in $$\mathbb{R}^2$$, its transformed point by $$L$$ is in the ellipse defined by

$\left\{ \z \in \mathbb{R}^{2} | \z^T (\bL^{T})^{-1} \bL^{-1} \z = 1 \right\}$

Note

This note provides a proof of the proposition above.

Fix a point $$\begin{bmatrix} \cos(t) \\ \sin(t) \end{bmatrix}$$ of the unit circle in $$\mathbb{R}^2$$. We write its transformed point by $$L$$ as

$\begin{bmatrix} u \\ v \end{bmatrix} = \bL \begin{bmatrix} \cos(t) \\ \sin(t) \end{bmatrix}.$

Since $$\bL$$ is invertible

$\bL^{-1} \begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} \cos(t) \\ \sin(t) \end{bmatrix}$

The squared Euclidean norm of the equality yields

$\begin{bmatrix} u & v \end{bmatrix} (\bL^{-1})^T \bL^{-1} \begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} \cos(t) & \sin(t) \end{bmatrix} \begin{bmatrix} \cos(t) \\ \sin(t) \end{bmatrix} = 1$

We recognize the equation of an ellipse, which concludes the proof of proposition.

## Geometric interpretation of the QR factorization¶

Consider the shape matrix $$\bSigma_x$$. Recall that $$\bSigma_x$$ defines the elliptic shape $$\Shape_x$$. We want to retrieve the transformation $$L_x$$ that satisfies

(11)$\bSigma_x = (\bL_x^{-1})^T \bL_x^{-1}.$

Observe from the QR factorization $$\bL_x = \bQ \bR$$ that $$L_x$$ can be decomposed uniquely in two specific transformations $$\bQ$$ and $$\bR$$. The upper triangular matrix $$\bR$$ encodes a transformation that combines of shear and scaling transforms. The orthonormal matrix $$\bQ$$ encode a rotation. This geometric interpretation is illustrated in Figure [Geometric interpretation of the QR factorization of linear transform matrix \bL_x.].

Fig. 4 Geometric interpretation of the QR factorization of linear transform matrix $$\bL_x$$.

Unless $$L_x$$ involves no rotation, $$\bL_x$$ is an upper triangular matrix. Then, because Equation (11) is a Cholesky decomposition, $$\bL_x$$ can be identified by unicity of the Cholesky decomposition.

In general, $$\bL_x$$ is not upper triangular. Orientations $$\bo_x$$ of elliptic shape $$\bSigma_x$$ are provided from feature detectors. In SIFT, $$\bo_x$$ corresponds to a dominant local gradient orientation.

Thus, introducing $$\theta_x \eqdef \angle \left( \begin{bmatrix}1\\0\end{bmatrix}, \bo_x \right)$$, we have

$\bQ = \begin{bmatrix} \cos(\theta_x) & -\sin(\theta_x) \\ \sin(\theta_x) & \cos(\theta_x) \end{bmatrix}$

and expanding Equation (11) yields

\begin{aligned} \bSigma_x &= (\bL_x^{-1})^T \bL_x^{-1} \\ &= \bQ (\bR^{-1})^T \bR^{-1} \bQ^{T} \quad \text{since}\ \bQ^T = \bQ^{-1}\\ \bQ^T \bSigma_x \bQ &= (\bR^{-1})^T \bR^{-1} \end{aligned}

We recognize the Cholesky decomposition of matrix $$\bQ^T \bSigma_x \bQ$$ which is the rotated ellipse as shown in Figure [Geometric interpretation of the QR factorization of linear transform matrix \bL_x.], in which case $$\bL_x$$ can be determined completely.

Finally, the affinity that maps the zero-centered unit circle to ellipse $$\Shape_x$$ is of the form, in homogeneous coordinates

$\displaystyle \bT_x = \begin{bmatrix} \bL_x & \x \\ \mathbf{0}_2^T & 1 \end{bmatrix}.$

## Calculation of the Normalizing Transform¶

The algorithm below summarizes how to compute $$\bT_x$$.

Important

• Calculate the angle

$\theta_x := \mathrm{atan2}\left( \left\langle \bo_x, \begin{bmatrix}0\\1\end{bmatrix}\right\rangle, \left\langle \bo_x, \begin{bmatrix}1\\0\end{bmatrix}\right\rangle \right)$
• Form the rotation matrix

$\bQ := \begin{bmatrix} \cos(\theta_x) & -\sin(\theta_x) \\ \sin(\theta_x) & \cos(\theta_x) \end{bmatrix}$
• Decompose the ellipse matrix $$\bM := \mathrm{Cholesky}(\bQ^T \bSigma_x \bQ)$$

• $$\bM$$ is a lower triangular matrix such that

• $$\bM \bM^T = \bQ^T \bSigma_x \bQ$$
• $$\bR := (\bM^T)^{-1}$$
• $$\bL := \bQ \bR$$
• $$\bT_x := \begin{bmatrix} \bL & \x \\ \mathbf{0}_2^T & 1 \end{bmatrix}$$