# 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

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

Since \(\bL\) is invertible

The squared Euclidean norm of the equality yields

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

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

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

and expanding Equation (11) yields

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

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