Feature-Driven Registration

In this section, we present our principal contribution: the Feature-Driven framework. This framework, in which one directly acts on warp driving features, has two main advantages. First, it often is better balanced to tune feature positions, expressed in pixels, than coefficient vectors that may be difficult to interpret, as for the TPS or the FFD warps. Second, it allows one to use the efficient compositional framework in a straightforward manner. Indeed, warp composition and inversion cannot be directly done for non-groupwise warps. We propose empirical means for approximating warp composition and inversion through their driving features, called threading and reversion respectively. Our Feature-Driven framework is generic in the sense that it can be applied to almost any parametric warps such as the TPS or the FFD warps, as shown in section A.5.

Feature-Driven Warp Parameterization

Ignoring the set of parameters, a warp is an $ \mathbb{R}^2 \rightarrow \mathbb{R}^2$ function usually parameterized by a set of $ n$ control points  $ \mathbf{p}_i = (p_i^x \; p_i^y)^\mathsf{T}\in \mathbb{R}^2$ for  $ i=1,\ldots,n$. These control points are grouped in a vector  $ \mathbf{p} = \boldsymbol{\nu}(\mathsf{P}) \in \mathbb{R}^{2n}$ where $ \mathsf{P} \in \mathbb{R}^{n \times 2}$ is the matrix defined by  $ \mathsf{P}^\mathsf{T}= \left( \mathbf{p}_1 \; \ldots \; \mathbf{p}_n\right)$. We write $ \omega$ the warp in its natural parameterization. The warp $ \omega$ is said to be linear when it can be defined as a linear combination of its control points:

$\displaystyle \omega(\mathbf{q} ; \mathbf{p}) = \boldsymbol{\ell}_{\mathbf{q}}^\mathsf{T}\mathsf{P},$ (A.8)

where  $ \boldsymbol{\ell}_{\mathbf{q}} \in \mathbb{R}^n$ is a vector that depends on the point  $ \mathbf{q}$ and on the type of warp being considered. Note that the dependency on  $ \mathbf{q}$ of  $ \boldsymbol{\ell}_{\mathbf{q}}$ is usually non linear even if the warp is linear. The control points are usually not interpolated. They just act as `attractors' to the warp. It thus makes their interpretation difficult. The Feature-Driven concept is in fact a change of parameterization. The control points are replaced by a set of features that are interpolated by the warp. We call them the driving features and denote them  $ \mathbf{u}_0$ in the texture image and  $ \mathbf{v}$ in the current one (see figure A.1). We denote  $ \mathcal {W}$ the Feature-Driven parameterization of the warp $ \omega$. Loosely speaking, matching the driving features between two images is equivalent to defining a warp since the warp can be used to transfer the driving features from one image to the other, while conversely, the warp can be computed from the driving features. Indeed, if the warp is linear with respect to its control points then it is always possible to find a matrix  $ \mathsf{E}$ such that:

$\displaystyle \mathcal{W}(\mathbf{q} ; \mathbf{v}) = \boldsymbol{\ell}_{\mathbf{q}}^\mathsf{T}\mathsf{E} \mathsf{V},$ (A.9)

with  $ \mathsf{V} = \zeta(\mathbf{v})$, i.e. $ \mathsf{V}$ equals to  $ \mathbf{v}$ reshaped on two columns. Matrix  $ \mathsf{E}$ can be pre-computed. Details on how the matrix  $ \mathsf{E}$ is obtained for the TPS and the FFD warps are given in section A.5.1 and section A.5.2 respectively. If we write  $ \mathbold{\mu}_{\mathbf{q}} = \mathsf{E}^\mathsf{T}\boldsymbol{\ell}_{\mathbf{q}}$ then the Feature-Driven parameterization of the warp  $ \mathcal {W}$ is given by:

$\displaystyle \mathcal{W}(\mathbf{q} ; \mathbf{v}) = \mathbold{\mu}_{\mathbf{q}}^\mathsf{T}\mathsf{V}.$ (A.10)

Figure A.1: Illustration of the Feature-Driven parameterization. The vector  $ \mathbf u_0$ contains the features in the texture image (the centers). $ \omega( \:{\scriptscriptstyle\bullet}\: ; \mathbf p)$ and $ \mathcal{W}(\:{\scriptscriptstyle\bullet}\: ; \mathbf v)$ are two different representations of the same warp. The first one is parameterized with the `natural' control points $ \mathbf p$ while the second one is parameterized with the driving features $ \mathbf v$.
Image fd-illus

Identity Warp.

If we denote  $ \mathbf{u}_0$ the features in the texture image then  $ \mathcal{W}( \:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{u}_0)$ is the identity warpA.3, i.e. the warp that leaves the location of the features  $ \mathbf{u}_0$ unchanged.

Threading Warps

Given two sets of driving features, $ \mathbf{v} = \boldsymbol{\nu}\left( (\mathbf{v}_1 \; \ldots \; \mathbf{v}_l)^\mathsf{T}\right)$ and  $ \mathbf{v}' = \boldsymbol{\nu}\left( (\mathbf{v}'_1 \; \ldots \; \mathbf{v}'_l)^\mathsf{T}\right)$, we want to find a third set  $ \mathbf{v}'' = \boldsymbol{\nu}\left( (\mathbf{v}''_1 \; \ldots \; \mathbf{v}''_l)^\mathsf{T}\right)$ defined such that threading the warps induced by  $ \mathbf{v}$ and  $ \mathbf{v}'$ results in the warp induced by  $ \mathbf{v}''$, as shown in figure A.2. We propose a simple and computationally cheap way to do it, as opposed to previous work. This is possible thanks to the Feature-Driven parameterization. Our idea for threading warps is very simple: we apply the $ \mathbf{v}'$ induced warp to the features  $ \mathbf{v}$; the resulting set of features is $ \mathbf{v}''$. We thus define the warp threading operator, denoted  $ \scriptscriptstyle \square$, as:

$\displaystyle \mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mat...
 \qquad \textrm{with }
 \mathbf{v}'' = \mathcal{W}(\mathbf{v} ; \mathbf{v}'),$ (A.11)

where  $ \mathcal{W}(\mathbf{v} ; \mathbf{v}')$ is meant to be applied to each feature in  $ \mathbf{v}$.

Figure A.2: The Feature-Driven warp threading process: $ \mathbf v''$ is defined by $ \mathbf{v}'' = \mathcal{W}(\mathbf v ;\mathbf v')$.
Image Threading

Examples of our warp threading process are shown in figure A.3. We synthesized two sets of driving features  $ \mathbf{v}$ and  $ \mathbf{v}'$ by randomly disturbing a  $ 3 \times 3$ regular grid from its rest position  $ \mathbf{u}_0$. As expected, threading a warp  $ \mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{v})$ with the identity  $ \mathcal{W}( \:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{u}_0)$ returns the original warp i.e. $ \mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{v}) = \ma...
...{1mm}\mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{u}_0)$ and  $ \mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{v}) = \ma...
...ce{1mm}\mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{v})$.

Figure A.3: Examples for the warp threading process.
Image ThreadingExamples

Reverting Warps

Given a set  $ \mathbf{v}$ of driving features, we want to determine the features  $ \mathbf{v}'$ such that the warp they induce is the reversion of the one induced by  $ \mathbf{v}$. This is illustrated in figure A.4. As for the threading, our Feature-Driven framework yields a very simple solution. The idea is that applying the  $ \mathbf{v}'$ induced warp to $ \mathbf{v}$ should give $ \mathbf{u}_0$ i.e. , the fixed driving features in the texture image. We thus introduce the reversion operator $ \diamond$ as:

$\displaystyle \mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mat...
...') \qquad \textrm{with $\mathcal{W}(\mathbf{v} ; \mathbf{v}') = \mathbf{u}_0$},$ (A.12)

This amounts to solving an exactly determined linear system, the size of which is the number of driving features. Using equation (A.10), we obtain:

$\displaystyle \mathsf{M} \mathsf{V}' = \mathsf{U}_0,$ (A.13)

where  $ \mathsf{M} \in \mathbb{R}^{l \times l}$ is the matrix defined by $ \mathsf{M}^\mathsf{T}= \left(\mathbold{\mu}_{\mathbf{v}_1} \; \ldots \; \mathbold{\mu}_{\mathbf{v}_l}\right)$, $ \mathsf{V}' = \zeta(\mathbf{v}')$ and $ \mathsf{U}_0 = \zeta(\mathbf{u}_0)$. The driving features  $ \mathbf{v}'$ of the reverted warp are thus given by:

$\displaystyle \mathbf{v}' = \boldsymbol{\nu}\left(\mathsf{M}^{-1}\mathsf{U}_0\right).$ (A.14)

Figure A.4: The Feature-Driven warp reversion process: $ \mathbf v'$ is defined such that $ \mathcal{W}(\mathbf v;\mathbf v') = \mathbf u _0$.
Image inverseWarp

Examples of the reverting process are shown in figure A.5. We synthesized driving features  $ \mathbf{v}$ by randomly disturbing a $ 3 \times 3$ regular grid from its rest position  $ \mathbf{u}_0$. The driving features  $ \mathbf{v}'$ result from reverting the warp  $ \mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{v})$. Threading warps  $ \mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{v})$ and  $ \mathcal{W}(\:\raisebox{1pt}{$\scriptscriptstyle\bullet$}\:; \mathbf{v}')$ introduce a new set of driving features  $ \mathbf{v}''$. As expected, the features  $ \mathbf{v}''$ are similar to the original grid  $ \mathbf{u}_0$ with an average residual error of $ 10^{-13}$ pixels.

Figure A.5: Illustration of the warp reversion process on three examples.
Image revertingExamples

Compositional Feature-Driven Registration

Relying on the Feature-Driven parameterization properties, we extend compositional algorithms to non-groupwise warps. The following three steps are repeated until convergence, as shown in figure A.6:

Note that in previous work (158,75,123) a preliminary step is required before applying the update rule, as reviewed in section A.2.2. In comparison, our Feature-Driven framework makes it naturally included into the third step.

Illumination changes are handled by globally normalizing the pixel values in the texture and the warped images at each iteration. Another approach could be used such as the light-invariant approach of (148).

Figure A.6: The three steps of the Compositional Feature-Driven registration.
Image alignementStep2

Contributions to Parametric Image Registration and 3D Surface Reconstruction (Ph.D. dissertation, November 2010) - Florent Brunet
Webpage generated on July 2011
PDF version (11 Mo)