Transitivity property

Image registration algorithms that have a difficult time producing inverse consistent transformations have an even harder time producing transformations that satisfy the transitivity property. In this paper we investigate how an algorithm that reduces the inverse consistency error compared to another also reduces the transitivity error.

A set of image transformations $H$ is said to have the transitivity property if $h_{CB}(h_{BA}(x))= h_{CA}(x)$ or equivalently if $h_{AC}(h_{CB}(h_{BA}(x))) = x$ for all $A, B, C \in Q$ and $x \in \Omega$.

These transitivity relationships are illustrated in Fig. 1. Assume that the points $x$, $y$, and $z$ correspond to the same landmark in images $A$, $B$, and $C$, respectively. Assume that the set of transformations $H = \{h_{AB}, h_{BA}, h_{BC}, h_{CB}, h_{AC}, h_{CA} \}$ has the invertibility and transitivity properties such that

$$y = h_{BA}(x), \quad z = h_{CB}(y), \quad x = h_{AC}(z).$$

Substituting the first equation into the second and the second into the third equation gives the result

$$x = h_{AC}(h_{CB}(h_{BA}(x))).$$

The average transitivity error is defined as

$$E_{ATRAN}(h_{AB},h_{BC},h_{CA},M) = \frac 1 {M} \int_M \vert\vert h_{AB}(h_{BC}(h_{CA}(x))) - x \vert\vert dx$$ (3)

and the maximum transitivity error is defined as

$$E_{MTRAN}(h_{AB},h_{BC},h_{CA},M) = \max_{x \in M} \ \vert\vert h_{AB}(h_{BC}(h_{CA}(x))) - x \vert\vert .$$ (4)

Eqs. 3 and 4 are discretized for implementation.

Figure 2 demonstrates an advantage of producing transformations that satisfy the transitivity property. The left panels shows that the minimum number of invertible transformations required to map information from one coordinate system to another is $N-1$ where $N$ is the number of image volumes. The correspondence between any two coordinate systems is determined explicitly by one of the displayed transformations or indirectly by concatenating two of the transformations. For example, a point $x$ in coordinate system B is mapped to $y$ in coordinate system C by the mapping $y = h_{BA}(h_{AC}(x))$, etc.

Figure 2: Left panel shows the minimum number of pairwise transformations needed to map a point from one brain to its corresponding location in another. Right panel shows all of the pairwise mappings between the brains.

Figure 2 demonstrates that it is advantageous to design pairwise registration algorithms rather than N-wise registration algorithms that satisfy the transitivity property. The first advantage is that a pairwise algorithm only needs to compute $N-1$ pairwise transformations as opposed to $(N-1)!$ pairwise transformations. This reduces computation time and computer storage requirements by a factor of $(N-2)$ factorial. Another advantage is that a pairwise algorithm only requires one additional set of pairwise transformations to be computed to add a new data set to the population. An N-wise registration algorithm requires that all of the transformations to be recomputed to produce a set of transformations with the transitivity property.

In general, pairwise image registration algorithms do not produce transformations that have the transitivity property. The degree of transitivity can be evaluated by measuring the difference between the identity mapping and the composition the transformations from image $A$-to-$B$, $B$-to-$C$, and $C$-to-$A$.

Copyright © 2002 • The University of Iowa. All rights reserved. Iowa City, Iowa 52242
Questions or Comments: gary-christensen@uiowa.edu