Skip to main content

Constructing kernels for shape modelling

While this property is not easy to check, once we know that a kernel is positive semi-definite, we can use it to construct new positive semi-definite kernels using a set of rules for combining kernels. In this article (as well as in a later step this week), we show you some examples of how these rules can be used to construct powerful models of shape deformations.

Let k1,k2:Ω×Ω→Rd×dk_1 , k_2 : \Omega \times \Omega \to \mathbb{R}^{d \times d} be two positive semi-definite kernels and f:Ω→Rdf : \Omega \to \mathbb{R}^d a vector-valued function. Then the following rules can be used to generate new positive semi-definite kernels k:Ω×Ω→Rd×dk : \Omega \times \Omega \to \mathbb{R}^{d \times d}

  1. k(x,x′)=k1(x,x′)+k2(x,x′)k(x,x') = k_1(x, x') + k_2(x,x').
  2. k(x,x′)=αk1(x,x′),α∈R+,k(x,x')= \alpha k_1(x,x'), \alpha \in \mathbb{R}_+,.
  3. k(x,x′)=k1(x,x′)⊙k2(x,x′)k(x,x')= k_1(x,x') \odot k_2(x,x').
  4. k(x,x′)=f(x)f(x’)Tk(x,x')=f(x)f(x’)^T.
  5. k(x,x′)=BTk(x,x′)B,B∈Rd×rk(x,x')=B^Tk(x,x')B, B \in \mathbb{R}^{d \times r}.
  6. k(x,x′)=k3(ϕ(x),ϕ(x′)),ϕ:Ω→Rnk(x,x')=k_3(\phi(x), \phi(x')), \phi : \Omega \to \mathbb{R}^n, k3:Rn×Rn→Rd×dk_3 : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^{d \times d} a p.s.d. kernel.

Multiscale model​

We have seen that we can define a model of smooth deformation using the kernel

kσ(x,x′)=(exp⁡(−∣∣x−x′∣∣2σ2)00exp⁡(−∣∣x−x′∣∣2σ2)).k_\sigma(x,x') = \left(\begin{array}{cc} \exp(-\frac{||x - x'||^2}{\sigma^2}) & 0 \\ 0 &\exp(-\frac{||x - x'||^2}{\sigma^2}) \end{array}\right).

Choosing σ\sigma large (compared to the domain Ω\Omega) in the above model leads to very smooth deformations, choosing σ\sigma small allows us to obtain deformations that represent more local variations.

Anatomical shape variations are usually a combination of long-ranging, smooth deformations (e.g. the movement of the thumb) and small-scale local deformations (e.g. the shape of the knuckles). Combining rule 1 and 2 allows us to build a model that combines deformation on multiple scales with varying smoothness. This is achieved by defining the kernel

kms(x,x′)=∑i=1nsikσi(x,x′),k_\text{ms}(x,x')= \sum_{i=1}^n s_i k_{\sigma_i}(x,x'),

where sis_i defines the scale and σi\sigma_i the smoothness of the deformation.

Anisotropic scaling​

We have already discussed how we can obtain anisotropic deformation fields using a diagonal kernel, where we scale each component individually:

k(x,x′)=(s1exp⁡(−∣∣x−x′∣∣2σ2)00s2exp⁡(−∣∣x−x′∣∣2σ2)).k(x,x') = \left(\begin{array}{cc} s_1 \exp(-\frac{||x - x'||^2}{\sigma^2}) & 0 \\ 0 & s_2 \exp(-\frac{||x - x'||^2}{\sigma^2}) \end{array}\right).

Unfortunately, this construction can only be used to define the scale in x and y directions which have no particular significance in shape modelling. Using rule 5 with a 2×22 \times 2 rotation matrix RR, we can define the kernel

kR(x,x′)=RTk(x,x′)R,k_R(x,x') = R^T k(x,x') R,

which allows us to choose an arbitrary direction of anisotropy.

Changepoint kernels​

Sometimes the shape variations in different regions of a shape have different characteristics. In our hand example, the thumb can be moved much more freely than the other fingers, which leads to wider shape variations in the thumb region. This can be incorporated into the model using a changepoint kernel. Define

kcp(x,x′)=χ(x)χ(x′)T⊙k1(x,x′)+(1⃗2−χ(x))(1⃗2−χ(x′))T⊙k2(x,x′)k_{cp}(x,x')=\chi(x)\chi(x')^T \odot k_1(x,x') + (\vec{1}_{2}-\chi(x))(\vec{1}_{2}-\chi(x'))^T \odot k_2(x,x')

and

χ(x)={1⃗2if x∈thumb region0⃗2otherwise\chi(x)= \left\{ \begin{array}{ll} \vec{1}_2 & \text{if } x \in \text{thumb region} \\ \vec{0}_2 & \text{otherwise} \end{array} \right.

where we used the notation

0⃗2=(00) and 1⃗2=(11).\vec{0}_2 = \left( \begin{array}{l}0 \\ 0 \end{array} \right) \text { and } \vec{1}_{2} = \left( \begin{array}{l}1 \\ 1 \end{array} \right).

The function χ\chi is used to select which kernel is active in a given region (ie it acts as a mask). It is easy to see that this kernel is positive semi-definite by using rule 4, together with rule 1 and rule 3.

Figure 1 shows random samples obtained from a model that is defined using the changepoint kernel. In the thumb region (in blue), we modelled large, anisotropic deformations that go mainly in the diagonal direction in order to mimic the movement of the thumb. In the rest of the area we see smooth, isotropic deformations.

Samples from a changepoint kernel

Figure 1: random samples from a changepoint kernel, where the thumb region (in blue) is modelled differently from the rest of the shape.

Estimating the kernel from example data​

Finally, we show that the kernel ksk_s that arises from estimating the covariance function from observed deformation fields u1,…,unu_1, \ldots, u_n, ui:Ω→Rdu_i : \Omega \to \mathbb{R}^d is positive-semi definite. Recall from Step 2.4 that this covariance function is defined by

ks(x,x′)=1n∑i=1n(ui(x)−u‾(x))(ui(x′)−u‾(x′))Tk_s(x,x')=\frac{1}{n}\sum_{i=1}^n (u_i(x) - \overline{u}(x)) (u_i(x') - \overline{u}(x'))^T

where

u‾=1n∑i=1nui.\overline{u} = \frac{1}{n}\sum_{i=1}^n u_i.

It is easy to see that this is a combination of rule 4 (the part inside the sum), rule 1 (the sum) and rule 2 (the scaling factor 1n\frac{1}{n}).

Hence ksk_s is just a normal, positive semi-definite kernel, which we can in turn combine with any other positive semi-definite kernel using the same rules.