Results

In order to illustrate the efficiency of k-NN classification for the analysis of T1,T2 pairs of MRI images, we consider the images of Figure . The image on the left is a $256 \times 256 \times 120$ T1-weighted MRI. The image on the right is a $256 \times 256 \times 30$ T2-weighted MRI. The T1 image was registered into the coordinates of the T2 image, and resampled to an identical size. Slice number 22 out of 30 is displayed.
For each of 4 tissue types (background, CSF, grey matter, white matter), 300 training samples are manually selected, as illustrated at Figure . The T1 and T2 values are normalized as values between 0 and 511. The k-DT algorithm is then applied over the $512 \times 512$ pattern space. Every possible pattern is classified within the class with most occurrences in its k-nearest neighbors among the training samples. The resulting classification of the pattern space is shown at the bottom of Figure , with k=1 and k=11. The choice of this value is justified later.

  

Figure 11.4: Classification in 4 classes : lookup tables. Up: Training samples from the 4 tissue classes. Left: Division of the (T2,T1) space with the NN rule (k=1). Right: Division of the (T2,T1) plane with the k-NN rule (k=11). k-DT was limited to dist_E=10000, leaving some (T2,T1) couples unclassified.

Every voxel in the 2 MRI dataset is then labeled as belonging to the class found in this (T2,T1) values lookup table. The result of this process is found in Figure .
In Figure , we can see that the boundaries between the different classes in the lookup table are much smoother with k=11 than with k=1. A priori, we expect the unknown probabilistic distribution of (T1,T2) values for each tissue type to be smooth functions. It is therefore reasonable to believe that they are better approximated with a higher k. In Figure , it results in a classification that is significantly less noisy with a higher k, and visually appears to be better with the use of our a priori anatomical knowledge of the brain.

  

Figure 11.5: Classification in 4 tissue classes. Left: k=1. Right: k=11.

In a second experiment, training samples from a fifth tissue class were added to the training data-set. This new tissue type corresponds to white matter lesions (WML) resulting from multiple sclerosis. One such lesion can be seen slightly up and left of the center of the image at figure . From a medical point of view, WML result from a loss of myelin around the axons. This turns the macroscopic appearance of WML into a tissue similar to grey matter, located where one would expect white matter.
Because the lesions in the image are small and only cover a few slices, only 60 training samples were manually selected this time. They appear as dots in Figure .

  

Figure 11.6: Classification in 5 classes : lookup tables. Up: Training samples from the 5 tissue classes. Left: Division of the (T2,T1) space with the NN rule (k=1). Right: Division of the (T2,T1) plane with the k-NN rule (k=11).

Obviously, the 5 tissue types classification appears to be a more complex task, as illustrated by the irregularity of the borders between classes in the 1-NN lookup table of figure . Indeed, lesions and grey matter appear to have very similar characteristics. Nevertheless, with k=11, the borders between classes in the lookup table do appear rather regular.

  

Figure 11.7: Classification in 5 tissue classes. Left: k=1. Right: k=11.

In Figure , the resulting classification of the voxels of the MR images is displayed. The lesion is correctly classified, but several other voxels are mis-classified as belonging to the lesion. This happens for voxels at the border between grey matter and CSF, where partial volume effects affect their values. This is of course a limit of the classification method, since the lesion class is indeed situated partly between the CSF and the grey matter classes in the lookup table. Improving this would require to take into account the spatial information and not only the gray level values.
Finally, we make a quantitative evaluation of the gain in classification accuracy made by using a large k. The training data set - 1200 and 1260 samples respectively - is uniformally divided into 20 subsets. Each subset is classified using the 19 others as training data. The error ratio is defined as the average percentage of mis-classified samples in the subsets.
The observed error ratio for k=1 to 20 are displayed in figure . The jagged aspect of the curve results from the fact that most classification decisions are the result of a vote of the k nearest samples, choosing between two classes. In such a dual vote, an even number of voters make a decision of lesser quality than the same number minus 1.
The error ratio R depends on two main factors. First, the probabilistic distributions of observed (T1,T2) values for each tissue type can overlap each other, because of the noise in the images, because of inaccuracies in the manual selection of samples, because of the intrinsic tissue properties ... This corresponds to the Bayesian risk R^*, where the probabilistic distributions are known exactly and the best decision criterion is used. The second factor depends on the quality of the decision rule that is used, i.e. on how well we can use the available data to reach a good decision. Cover [23] showed that the error ratio associated to a k-NN decision rule was such that

$$R^{*} \leq R \leq ( 1 + \frac{1}{k} ) R^{*}$$ (11.1)

which corresponds to the shape of the curves in figure , notwithstanding the odd-even staggering. Practically, the value we selected for the above experiments (k=11) is a suitable choice. A smaller k would not take full advantage of the available training samples. A larger k would require both additional computational time and memory to store the k-DT. Worse, () only stands if $k/N \rightarrow 0$, so that using a larger k requires to take more training samples, a time-consuming operation for the user.

  

Figure 11.8: Error ratio for 4 tissues (left) and 5 tissues (right) experiments, as a function of k.