This paper presents the algorithms and results of our participation to the medical image annotation task of ImageCLEFmed 2007. We proposed, as a general strategy, a multi-cue approach where images are represented both by global and local descriptors, so to capture di®erent types of information. These cues are combined during the classi¯cation step following two alternative SVM-based strategies. The ¯rst algorithm, called Discriminative Accumulation Scheme (DAS), trains an SVM for each feature type, and considers as output of each classi¯er the distance from the separating hyperplane. The ¯nal decision is taken on a linear combination of these distances: in this way cues are accumulated, thus even when they both are misleaded the ¯nal result can be correct. The second algorithm uses a new Mercer kernel that can accept as input di®erent feature types while keeping them separated. In this way, cues are selected and weighted, for each class, in a statistically optimal fashion. We call this approach Multi Cue Kernel (MCK). We submitted several runs, testing the performance of the single-cue SVM and of the two cue integration methods. Our team was called BLOOM (BLance°Or-tOMed.im2) from the name of our sponsors. The DAS algorithm obtained a score of 29.9, which ranked ¯fth among all submissions. We submitted two versions of the MCK algorithm, one using the one-vs-all multiclass extension of SVMs and the other using the one-vs-one extension. They scored respectively 26.85 and 27.54, ranking ¯rst and second among all submissions.
The amount of medical image data produced nowadays is constantly growing, with average-sized radiology departments producing several tera-bites of data annually. The cost of manually annotating these images is very high; furthermore, manual classi¯cation induces errors in the tag assignment, which means that a part of the available knowledge is not accessible anymore to physicians [5]. This calls for automatic annotation algorithms able to perform the task reliably, and benchmark evaluations are thus extremely useful for boosting advances in the ¯eld. The ImageCLEFmed annotation task has been established in 2005, and in 2007 it has provided participants with 11000 training and development data, spread across 116 classes. The task consisted in assigning the correct label to 1000 test images. For further informations on the annotation task of ImageCLEF 2007 we refer the reader to [6].
This paper describes the algorithms submitted by the BLOOM (BLance°Or-tOMed.im2) team, at its ¯rst participation to the CLEF benchmark competition. In order to achieve robustness, a crucial property for a reliable automatic system, we opted for a multi-cue approach, using raw pixels as global descriptors and SIFT features as local descriptors. The two feature types were combined together using two di®erent SVM-based integration schemes. The ¯rst is the Discriminative Accumulation Scheme (DAS), proposed ¯rst in [7]. For each feature type, an SVM is trained and its output consists of the distance from the separating hyperplane. Then, the decision function is built as a linear combination of the distances, with weighting coe±cients determined via cross validation. We submitted a run using this method (BLOOM-BLOOM DAS) that obtained a score of 29.9, ranking ¯fth among all submissions.
The second integration scheme consists in designing a new Mercer kernel, able to take as input di®erent feature types for each image data. We call it Multi Cue Kernel (MCK); the main advantage of this approach is that features are selected and weighted during the SVM training, thus the ¯nal solution is optimal as it minimizes the structural risk. We submitted two runs using this algorithm, the ¯rst (BLOOM-BLOOM MCK oa) using the one-vs-all multiclass extension of SVM; the second (BLOOM-BLOOM MCK oo) using instead the one-vs-one extension. These two runs ranked ¯rst and second among all submissions, with a score of respectively 26.85 and 27.54. These results overall con¯rm the e®ectiveness of using multiple cues for automatic image annotation.
The rest of the paper is organized as follows: section 2 describes the two types of feature descriptors we used at the single cue stage. Section 3 gives details on the two alternative SVMbased cue integration approaches. Section 3 reports the experimental procedure adopted and the results obtained, with a detailed discussion on the performance of each algorithm. The paper concludes with a summary discussion. 2
The aim of the automatic image annotation task is to classify images into a set of classes. In particular classes were de¯ned in relation to the four independent axis of modality, body orientation, body region, and biological system examined, according to the IRMA code [3]. The labels are hierarchical therefore, errors in the annotation are counted depending on the level at which the error is done and on the number of possible choices. For each image the error ranges from 0 to 1, respectively if the image is correctly classi¯ed or if the predicted label is completely wrong. It is also possible to assign a \don't know" label, in this case the score is 0:5.
The strategy we propose is to extract a set of features from each image and to use then a Support Vector Machine (SVM) to classify the images. We have explored a local approach, using SIFT descriptors, and a global approach, using the raw pixels. 2.1
We explored the idea of \bag of words" for classi¯cation, a common concept in many state of the art approaches in images classi¯cation. This is based on the idea that it is possible to transform the images into a set of prespeci¯ed visual words, and to classify the images using the statistics of appearance of each word as feature vectors.
Most of these systems are based on the use of the SIFT descriptor [4]. The basic idea of SIFT is to describe an area of an image in a way that is robust to noise, illumination, scale, translation and rotation changes. The SIFT points are selected in the image as local maxima of the scalespace, in this sense the SIFT points are intrinsically easy to be tracked. Despite the usefulness of SIFT, there is no reason to believe that these points are the most informative for a classi¯cation task. This has been pointed out by di®erent works and systematically veri¯ed by [8]. In that work it is shown that a dense random sampling of the SIFT points is always superior to any strategy based on interest points detectors. Moreover due to the low contrast of the radiographs it would be di±cult to use any interest point detector. So in our approach we densely sampled each input image, extracting in each point a SIFT descriptor.
Another modi¯cation we made is based on the fact that the rotation invariance could be useless for the ImageCLEF classi¯cation task, as the various structures present in the radiographs are likely to appear always with the same orientation. Moreover the scale is not likely to change too much between images of the same class, so we extracted the SIFT at only one octave, the one that gave us the best classi¯cation performances. In this sense we have decoupled the extraction of a SIFT keypoint from the description of the point itself. To keep the complexity of the description of each image low and at the same to retain as much information as possible, we matched each extracted SIFT with a number of template SIFTs. These template SIFTs form our vocabulary of visual words. It is built using a standard K-means algorithm, with K equal to 500, on a random collection of SIFTs extracted from the training images. Various sizes of vocabulary were tested with no signi¯cant di®erences, so we have chosen the smaller one with good recognition performances. Note that in this phase also testing images can be used, because the process is not using the labels and it is unsupervised. At this point each image could be described with the raw counts of each visual word.
To add some kind of spatial information to our features we divided the images in four subimages, collecting the histograms separately for each subimage. In this way the dimension of the input space is multiplied by four, but in our tests we gained about 3% of classi¯cation performances. We have extracted 1500 SIFT in each subimage: such dense sampling adds robustness to the histograms. See Figures 1 and 2 for an example.
Another approach that we explored was the simplest possible global description method: the raw pixels. The images were resized to 32x32 pixels, regardless of the original dimension, and normalized to have sum equal to one, then the 1024 raw pixels values were used as input features. This approach is at the same time a baseline for the classi¯cation system and a useful \companion" method to boost the performance of the SIFT based classi¯er (see section 2.2). 2.2
For the classi¯cation step we used an SVM with an exponential Â2 as kernel, for both the local and global approaches: i=1 Ã ¡° X (Xi ¡ Yi)2 ! :
N
Xi + Yi K(X; Y ) = exp (1) The parameter ° was tuned through cross-validation (see section 4). This kernel has been successfully applied for histogram comparison and it has been demonstrated to be positive de¯nite [2], thus it is a valid kernel.
Even if the labels are hierarchical, we have chosen to use the standard multi-class approaches. This choice is motivated by the ¯nding that, with our features, the recognition rate was lower using an axis-wise classi¯cation. This could be due to the fact that each super-class has a variability so high that the chosen features are not able to model it, while they can very well model the small sub-classes. In particular we have tested both one-vs-one and one-vs-all multi-class extension for SVM. 3
Due to the fundamental di®erence in how local and global features are computed it is reasonable to suppose that the two representations provide di®erent kinds of information. Thus, we expect that by combining them through an integration scheme, we should achieve a better performance, namely higher classi¯cation performance and higher robustness.
In the computer vision and pattern recognition literature some authors have suggested di®erent methods to combine information derived from di®erent cues (for a review on the topic we refer the reader to [9]). Some of them are based on building new representations, but this technique does not solve the robustness problem because if one of the cues gives misleading information it is quite probable that the new feature vector will be adversely a®ected. Moreover, the dimension of such a feature vector would increase as the number of of cues grows, implying longer learning and recognition times, greater memory requirements and possibly curse of dimensionality e®ects. The strategy we follow in this paper is to use integration schemes, thus keeping the feature descriptors separated and fusing them at a mid- or high- level. In the rest of the section we describe the two alternative integration schemes we used in the ImageCLEF competition. The ¯rst, the Discriminative Accumulation Scheme (DAS, [7]), is a high-level integration scheme, meaning that each single cue ¯rst generate a set of hypotheses on the correct label of the test image, and then those hypotheses are combined together so to obtain a ¯nal output. This method is described in section 3.1. The second, the Multi Cue Kernel (MCK), is a mid-level integration scheme, meaning that the di®erent features descriptors are kept separated but they are combined in a single classi¯er generating the ¯nal hypothesis. This algorithm is described in section 3.2. 3.1
The Discriminative Accumulation Scheme is an integration scheme for multiple cues that does not neglect any cue contribution. It is based on a weak coupling method called accumulation. The main idea of this method is that information from di®erent cues can be summed together.
Suppose we are given M object classes and for each class, a set of Nj training images fIij giN=j1, j = 1; : : : M . For each image, we extract a set of P di®erent cues: (a) (b) so that for an object j we have P new training sets fTp(Iij )giN=j1; j = 1; : : : M; p = 1 : : : P . For each we train an SVM. Kernel functions may di®er from cue to cue and model parameters can be estimated during the training step via cross validation. Given a test image I^ and assuming M ¸ 2, for each single-cue SVM we compute the distance from the separating hyperplane: Dj (p) = mjp X ®ipj yij Kp ³Tp(Iij ); Tp(I^)´ + bjp: i=1
P j¤ = argmaxfX apDj(p)g;
M
j=1 p=1
ap 2 <+:
After collecting all the distances fDj (p)gpP=1 for all the j objects j = 1; : : : ; M and the p cues
p = 1; : : : ; P , we classify the image I^ using the linear combination:
(2)
(3)
(
DAS can be de¯ned a high-level integration scheme, as fusion is performed as a post-processing step after the single-cue classi¯cation stage. As an alternative, we developed a mid-level integrating scheme based on multi-class SVM with a Multi Cue Kernel KMC . This new kernel combines di®erent features extracted form images; it is a Mercer kernel, as positively weighted linear combination of Mercer kernels are Mercer kernels themselves [1]:
KMC (fTp(Ii)gp; fTp(I)gp) =
P X apKp(Tp(Ii); Tp(I)): p=1 In this way it is possible to perform only one classi¯cation step, identifying the best weighting factors ap while optimizing the other kernel parameters. Another advantage of this approach is that it makes it possible to work both with one-vs-all and one-vs-one SVM extensions to the multiclass problem. 4
Our experiments started evaluating the performance of local and global features separately before testing our integration methods. Two sets of experiments using single-cue SVM were ran to select the best kernel parameters through cross validation. The original dataset was divided in three parts: training, validation and testing. We merged them together and extracted 5 random and disjoint train/test splits of 10000=1000 images. We considered as the best parameters the one giving the best average score on the 5 splits. Note that, according to the method used for the score evaluation, the best average score is not necessary the best recognition rate. Besides obtaining the optimal parameters, these experiments showed that the SIFT features outperform the raw pixel ones. It could be predictable since the last year ImageCLEF competition results showed that local features are generally more informative than global features for the annotation task.
Then we adopted the same experimental setup for DAS and MCK. In particular for DAS we used the distances from the separating hyperplanes associated with the best results of the previous step, so the cross validation was used only to search the best weights for cue integration. On the other hand, for MCK the cross validation was applied to look for the best kernel parameters and the best feature's weights at the same time. In both cases weights could vary from 0 to 1.
Finally we used the results of the previous phases to run our submission experiment on the 1000 unlabeled images of the challenge test set using all the 11000 images of the original dataset as training.
The ranking, name and score of our submitted runs together with the score gain respect to the best run of other participants are listed in Table 1. Our two runs based on the MCK algorithm ranked ¯rst and second among all submissions stating the e®ectiveness of using multiple cues for automatic image annotation. It is interesting to note that even if DAS has a higher recognition rate, its score is worse than that obtained using the feature SIFT alone. This could be due to the fact that when the label predicted by the global approach, the raw pixels, is wrong, the true label is far from the top of the decision ranking.
In Table 2 there is a summary of the parameters used for our runs and the number of support
vectors obtained. As we could expect, the best feature weight (see (
Table 3 shows in details some examples of classi¯cation results. The ¯rst, second and third column contain examples of images misclassi¯ed by one of the two cues but correctly classi¯ed by DAS and MCK oa. The fourth column shows an example of an image misclassi¯ed by both cues and by DAS but correctly classi¯ed by MCK oa. It is interesting to note that combining local and global features can be useful to recognize images even if they are compromised by the presence of artifacts that for medical images can be prosthesis or reference labels put on the acquisition screen.
A deeper analysis of our results can be done considering the performance of the single-cue, discriminative accumulation and multicue kernel approach for each class. In Table 4 the number of images correctly recognized for each class are listed and it is possible to note that in few cases PIXEL oa outperforms SIFT oa, and to observe where MCK oa outperforms both SIFT oa and DAS. The di®erence between our approaches can be better evaluated considering the confusion matrices. They are shown as images in Figure 3. We ordered the classes following the way in which they are listed in table 4 and used a colormap corresponding to the number of images varying from zero to ¯ve to let the misclassi¯ed images stand out. It is clear that our methods di®er principally for how the wrong images are labeled. The more matrices present sparse values out of the diagonal and far away from it, the worse the method is.
PIXEL oa SIFT oa
DAS MCK oa 11± 1± 1± 1± 1± 2± 1± 1± 12± 2± 1± 1± 5± 5± 2± 1± CKM ISFT SAD IEPX TTO a o L CM ISF A IEX TO K T S
D P T
This paper presented a discriminative multi-cue approach to medical image annotation. We combined global and local information using two alternative fusion strategies, the discriminative accumulation scheme [7] and the multi cue kernel. This last method gave the best performance obtaining a score of 26.85, which ranked ¯rst among all submissions.
This work can be extended in many ways. First, we would like to use various types of local and global descriptors, so to select the best features for the task. Second, we would like to add shape descriptors in our fusion scheme, which should result in a better performance. Finally, our algorithm does not exploit at the moment the natural hierarchical structure of the data, but we believe that this information is crucial for achieving signi¯cant improvements in performance. Future work will explore these directions.
This work was supported by the ToMed.IM2 project (B. C. and F. O), under the umbrella of the Swiss National Center of Competence in Research (NCCR) on Interactive Multimodal Information Management (IM2, www.im2.ch), and by the Blance°or Boncompagni Ludovisi foundation (T. T., www.blance°or.se). The support is gratefully acknowledged. [1] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines (and Other
Kernel-Based Learning Methods). CUP, 2000. [2] C. Fowlkes, S. Belongie, F. Chung, and J. Malik. Spectral grouping using the nystroÄm method.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):214{225, 2004. [3] Schubert Henning Keysers Daniel Kohnen Michael Wein Berthold B. Lehmann, Thomas M.
The irma code for unique classi¯cation of medical images. In Proceedings of SPIE Medical 10 20 30 40 50 60 70 80 90 100 110 10 20 30 40 50 60 70 80 90 100 110 (a) 10 20 30 40 50 60 70 80 90 100 110 (c)