Relating TD and IDM

It is interesting to see that the positive effects of TD and IDM are additive in some cases (see section 6). Trying to relate these two approaches it becomes clear, that one can be expressed in terms of the other. Expressing the IDM in terms of TD is difficult, when a non-zero cost function is involved (it requires additional restrictions on the values permitted for $\alpha$). On the other hand generalizing the IDM leads to an expression also covering TD:

Figure 2: 1D comparison of IDM and TD

$\quad$

$$D_{C,{\mathcal F}}(x,\mu) = \mathop{\mbox{min}}\limits_{f\in... ...l F}} \{ C(f) + \sum_{i,j} \Vert x_{ij} - \mu_{f(i,j)}\Vert \}$$ (5)

where ${\mathcal F} \subset ({\rm I\!R}\times {\rm I\!R})^{I\times J}$ is a class of functions assigning to each pixel its (interpolated) counterpart and $C:{\mathcal F} \rightarrow {\rm I\!R}^{\geq 0}$ a cost function for these assignment functions. For the IDM one has

$${\mathcal F}_{\mbox{\tiny IDM}} = \{f:f(i,j)\in R_{ij}\} ,\mbox{ } C_{\mbox{\tiny IDM}}(f)= \sum_{i,j} C_{ijf(i,j)}$$ (6)

while for TD $C$ and ${\mathcal F}$ have the following representation:

$${\mathcal F}_{\mbox{\tiny TD}}=\{f\mbox{ }:\mbox{ }f\mbox{ }\mbox{affine}\},\mbox{ }\quad C_{\mbox{\tiny TD}}(f) = 0$$ (7)

This general expression is an intuitive representation of a distance being invariant to arbitrary functions $f$ of some class ${\mathcal F}$. Computing (5) may be very hard or impossible with some classes and cost functions, but TD and IDM are two examples with known solutions. (Strictly speaking (7) models the true manifold distance.) Some questions arising are e.g. which other cases are interesting in the setting of invariant pattern recognition and if one can learn the functions efficiently from training examples. For instance a model that extends the IDM naturally is to introduce a dependency between the displacements of pixels in a neighborhood, such that displacements in the same direction are cheaper than displacements in opposite directions. This leads to more complex minimization problems, which may be still efficiently solved using dynamic programming, if the number of possible displacements is small. Note that it is difficult to embed the XYI image warping approach [6] into the model (5) as the implicit XYI cost function depends on the intensity values.