Methods

The classification methods used here are based on the well-known nearest neighbor classifier. The main contribution is the use of a distance within this classifier that effectively takes into account image distortions. In the asymmetrical matching process, always all of the test image pixels are explained by the reference image pixels.

In previous work [2] two distortion models were found to be especially appropriate for medical images: tangent distance for global deformations and a local zero-order image distortion model (IDM) allowing for small pixel displacements. This model allows to match a pixel of a test image to the best fitting counterpart in the reference image within a small region. This zero-order model does not take into account dependencies between neighboring pixels and the minimization involved in the matching process is therefore computationally inexpensive. On the other hand, tangent distance (which is not used in this work) copes with global affine and brightness transformations computationally efficiently. A further efficient method to enhance classification of medical images is the use of a pixel distance threshold limiting the local pixel-wise distance to a maximum value.

We take into account local dependencies in the matching using two methods:

Local image context. The local context within the images can be represented by using local neighborhoods of e.g. 3$\times$3 or 5$\times$5 pixels in the matching process and for the calculation of the distances. Additionally, the image gradient in horizontal and vertical direction as computed by a Sobel filter can be used to effectively model the local image structure.

Dependencies between displacements. The two-dimensional dependencies can be taken into account by restricting the possible pixel mappings with respect to the mappings of neighboring pixels. The chosen restrictions should ensure monotonicity (`no crossings') and continuity (`no holes') of the pixel displacement field. If complete two-dimensional dependencies are taken into account the matching problem is NP-complete [3] and also known approximation algorithms are computationally expensive. The dependencies can therefore be relaxed in one of the dimensions: e.g. the vertical displacements of pixels of neighboring image columns are not taken into account. This approach results in a pseudo two-dimensional hidden Markov model (P2DHMM) [4]. We propose to extend this model by additionally allowing distortions of each pixel mapping from the possible displacement fields [5], resulting in a pseudo two-dimensional hidden Markov distortion model (P2DHMDM).

We briefly give a formal description of the decision process: To classify a test image $A$ with a given training set of references $B_{1k},\ldots,B_{N_k k}$ for each class $k\in\{1,\ldots,K\}$ we use the nearest neighbor decision rule

$$r(A)=\arg \min_{k} \big\{ \;\min_{n=1,\ldots,N_k}\; D(A,B_{nk}) \;\big\},$$ (1)

i.e. the test image is assigned to the class of the nearest reference image. For the distance calculation the test image $A = \{ a_{ij} \}, i=1,\ldots,I, j=1,\ldots,J$ must be explained by a suitable deformation of the reference image $B = \{ b_{xy} \}, x=1,\ldots,X, y=1,\ldots,Y$. Here, the image pixels take ${\mathsf{D}}$-dimensional values $a_{ij},b_{xy} \in {\rm I\!R}^{\mathsf{D}}$, where the vector components are denoted by a superscript $\mathsf{d}$. We now want to determine an image deformation mapping $(x_{11}^{IJ},y_{11}^{IJ}): (i,j) \mapsto (x_{ij},y_{ij})$ that results in the distorted reference image $B_{(x_{11}^{IJ},y_{11}^{IJ})} = \{ b_{x_{ij}y_{ij}} \}$. The resulting cost given the two images and the deformation mapping is defined as

$$C\big(A,B,(x_{11}^{IJ},y_{11}^{IJ})\big)=\sum_{i,j} \sum_{\mathsf{d}} \; \vert\vert a_{ij}^\mathsf{d} - b_{x_{ij}y_{ij}}^\mathsf{d} \vert\vert ^2 ,$$ (2)

i.e. by summing up the local pixel-wise distances, which are squared Euclidean distances here. Now, the distance measure between images $A$ and $B$ is determined by minimizing the cost over the possible deformation mappings:

Table 1: Restrictions on the deformation by the different deformation models. IDM: image distortion model; P2DHMM: pseudo 2-dimensional hidden Markov model; P2DHMDM: pseudo 2-dimensional hidden Markov distortion model.

model		restrictions on $(x_{11}^{IJ},y_{11}^{IJ})$
		$x_{ij} \in \{1,\ldots, X\} \cap \{i'-w,\ldots ,i'+w\}$, $i'=\left[i\tfrac{X}{I}\right]$,
IDM		$y_{ij} \in \{1,\ldots, Y\} \cap \{j'-w,\ldots ,j'+w\}$, $j'=\left[j\tfrac{Y}{J}\right]$,
		with warp range $w$, e.g. $w=3$
		$x_{1j}=1,x_{Ij}=X,y_{i1}=1,y_{iJ}=Y$,
P2DHMM		$\exists \{\hat{x}_1,\ldots,\hat{x}_I\}: \hat{x}_{i+1} - \hat{x}_i \in \{0,1,2\}$,
		$x_{ij} - \hat{x}_i = 0$,  $y_{i,j+1}- y_{ij} \in \{0,1,2\}$
		$x_{1j}=1,x_{Ij}=X,y_{i1}=1,y_{iJ}=Y$,
P2DHMDM		$\exists \{\hat{x}_1,\ldots,\hat{x}_I\}: \hat{x}_{i+1} - \hat{x}_i \in \{0,1,2\}$,
		$x_{ij} - \hat{x}_i \in \{-1,0,1\}$,  $y_{i,j+1}- y_{ij} \in \{0,1,2\}$

$$D(A,B)=\min\limits_{(x_{11}^{IJ},y_{11}^{IJ}) \in \mathcal{M}} \Bigl\{ C\big(A,B,(x_{11}^{IJ},y_{11}^{IJ})\big) \Bigr\}$$ (3)

The set of possible deformation mappings $\mathcal{M}$ determines the type of model used. Table 1 shows the restrictions imposed on the mappings by the different models. Since the P2D-models have more restrictions on the relative positions within the displacement field, the minimization process is computationally more complex here. A pre-selection of the e.g. 100 nearest neighbors with a different distance measures like the Euclidean distance can then significantly improve the computation time at the expense of a slightly higher error rate.