Overview of tangent distance

In 1993, SIMARD et al. proposed an invariant distance measure called tangent distance, which proved to be especially effective in the domain of OCR [1]. The authors observed that reasonably small transformations of certain image objects does not affect class membership. Simple distance measures like the Euclidean distance do not account for this, instead they are very sensitive to affine transformations like scaling, translation, rotation or axis deformation. When an image $x \in {\rm I\!R}^{I \times J}$ is transformed (e.g. scaled and rotated) by a transformation $t(x,\alpha)$ which depends on $L$ parameters $\alpha \in {\rm I\!R}^L$ (e.g. the scaling factor and rotation angle), the set of all transformed patterns

$$M_x = \{t(x,\alpha) : \alpha \in {\rm I\!R}^L\} \subset {\rm I\!R}^{I \times J}$$ (1)

is a manifold of at most dimension $L$ in pattern space. The distance between two patterns can now be defined as the minimum distance between their respective manifolds, being truly invariant with respect to the $L$ regarded transformations. Unfortunately, computation of this distance is a hard non-linear optimization problem and the manifolds concerned generally do not have an analytic expression. Therefore, small transformations of the pattern $x$ are approximated by a tangent subspace $\hat{M_x}$ to the manifold $M_x$ at the point $x$. This subspace is obtained by adding to $x$ a linear combination of the vectors $T_l(x), l=1,\ldots,L$ that span the tangent subspace and are the partial derivatives of $t(x,\alpha)$ with respect to $\alpha_l$. We obtain a first-order approximation of $M_x$

$$\hat{M_x} = \{x + \sum_{l=1}^{L} \alpha_l \cdot T_l(x)\ : \alpha \in {\rm I\!R}^L \} \subset{\rm I\!R}^{I \times J}$$ (2)

The single-sided (SS) TD $D_{\mbox{\tiny TD}}(x,\mu)$ is defined as

$$D_{\mbox{\tiny TD}}(x,\mu) = \mathop{\mbox{min}}\limits_{\al... ...{ \Vert x + \sum_{l=1}^{L} \alpha_l \cdot T_l(x) - \mu\Vert \}$$ (3)

The tangent vectors $T_l(x)$ can be computed using finite differences between the original image $x$ and a reasonably small transformation of $x$ [1]. Example images that were computed using (2) are shown in Fig. 1 (with the original image on the left).

Figure 1: Examples for tangent approximation

A double-sided (DS) TD can also be defined, where both manifolds are approximated and the distance is minimized over possible combinations of the respective parameters. It is possible to achieve a better approximation of the manifolds using an iterative procedure based on Newton's method, which is computationally more expensive.