In this paper we describe our experiments related to the ImageCLEF 2010 medical modality classification task using extremely randomized trees. Our best run combines bags of textual and visual features. It yields 90% recognition rate and ranks 6th among 45 runs (ranging from 94% downto 12%). Task description We participated in the ImageCLEF 2010 task related to imaging modality classification1. A set of 2390 (in color or greylevels) training images were provided. These were extracted by the organizers of the challenge from articles published in scientific journals (Radiology and Radiographics) together with the text of the figure captions and the title of articles. Images have been classified by experts into the following 8 classes that are illustrated by Figure 1: - CT: Computerized tomography (314 images) - GX: Graphics, typically drawing and graphs, (355 images) - MR: Magnetic resonance imaging (299 images) - NM: Nuclear Medicine (204 images) - PET: Positron emission tomography including PET/CT (285 images) - PX: optical imaging including photographs, micrographs, gross pathology etc (330 images) - US: ultrasound including (color) Doppler (307 images) - XR: x-ray including x-ray angiography (296 images)
The goal of the task is to build classification models able to recognize the imaging modality, using visual information only, textual information only, or both. Such models are expected to improve further content-based image retrieval. Participants submitted their predictions on a independent test set of 2620 images (for which modality classifications were not available) and classification results were later evaluated by organizers. A total of 45 runs were submitted by 7 research teams. In this paper, we report our results exploiting visual and textual information independently or combined using extremely randomized trees in a straightforward fashion.
We adopted the bag of words model that is widely used in natural language processing and information retrieval. We processed the provided XML file using a Python script to build a dictionary of all unique term (words) from the training set of image captions and article titles. More precisely, the XML file is cleaned (by removing XML tags and unuseful characters, and lowering characters) and a dictionary is built which finally consists of 13553 unique terms. Each image was then described by 13553 features where each feature is simply the term frequency ie. the number of times a given term appears for that image (in its caption and title) normalized by the number of terms for that image (in its caption and title), so that each textual feature is comprised in the [0, 1] interval. 2.2
Despite many years of research in feature extraction, decribing image content is not a trivial task when facing a new image classification problem. We adopt here a generic approach that learns a global, bag of visual words, image representation by using dense random subwindows extraction [MGPW05,MGW07] and extremely randomized trees [GEW06,MNJ08,MGW09]. More precisely, from each training image, we extracted 2000 small subwindows (which sizes were randomized between 10% and 25% of image sizes) at random positions in images, we resized them to 16 × 16 patches and described them by 768 HSV raw values, as illustrated by Figure 2.
We then built T = 10 extremely randomized trees using K = 28 random tests in each tree node and a minimum node sample size of 4000 (see Section 2.3 for algorithm details). Subwindow sizes and minimum node sample size were optimized on the training set by cross-validation. Other parameters were set to default values but further optimization might improve results. These parameter values yield 52660 terminal nodes in the ensemble of trees. Each terminal node (or leaf) of a tree is then used as visual feature (also known as “codebook” or “visual word”). By propagating image subwindows downto trees, each image is thus described by a global feature vector which dimensionality equals the number of terminal nodes in the ensemble of trees. For a given image, the value encoded for a given feature was equal to the visual term frequency, ie. the number of image subwindows that reach this terminal node divided by the total number of subwindows extracted in the image (so a leaf value is included in [0, 1], and the sum over all terminal nodes equals to 1 in a given tree for a given image), as illustrated by Figure 3. Once features are built, they are concatenated and fed into a machine learning algorithm to build a classifier. We used the extremely randomized trees algorithm [GEW06] that was successfully used in various application domains (e.g. [GdF+05,HTIWG10]) and more particularly in the context of various image classification tasks where it was already combined with random subwindows extraction [MGPW05,MGW07].
Starting with the whole training set at the root node, the Extra-Trees algorithm builds an ensemble of decision trees according to the classical top-down decision tree induction procedure [BFOS84] that uses tests on input variables to progressively partitions the input space into hyperrectangular regions so as to yield regions where the output is constant. The two main differences between this algorithm and other tree-based ensemble methods are that it splits nodes by choosing both attributes and cut-points at random (rather than choosing the best cut-point that optimizes a score measure like in Tree Bagging [Bre96] or Random Forests [Bre01]) and that it uses the whole learning sample (rather than a bootstrap replica in Tree Bagging and Random Forests) to grow the trees.
In our case, we use extremely randomized trees to build visual features from images as already mentionned in previous section, but also as final classifier either on textual or visual features or both.
In the case of construction of visual features where subwindows are described by raw pixel values, a test associated to an internal node of a tree simply compares the value of a pixel (intensity of a grey level or of a certain color component) at a fixed location within a subwindow to a cut-point value. In the case of its use as final classifier, a internal test compares the value of a (textual or visual) feature to a cut-point value.
In order to filter irrelevant attributes, the filtering parameter K corresponds to the number of input features chosen at random at each node, where K can take all possible values from 1 to the number of variables describing the training objects (e.g. 768 when building visual features from HSV subwindows; 13553 when building trees on textual features only). For each of these K attributes, a numerical threshold is randomly choosen within the range of variations of that attribute in the subset of objects available in the the current tree node. The score of each binary test is then computed on the current training subset according to an information criterion (the score measure is defined in [Weh97] and corresponds to a measure of impurity), and the best test among the K tests is chosen to split the current node into two nodes. Objects that fulfill the choosen test are propagated to the left child node, and others to the right node, and the process is repeated recursively on both child nodes. The development of a node is stopped as soon as either all input variables or the output variable are constant in the local subset of the leaf (in which cases impurity can not be further reduced), or the number of objects in the leaf is smaller than a predefined value (the minimum node sample size, nmin). A number T of such trees are grown from the training sample. 3 3.1
Using T = 10000 trees and K = √13453 = 116 random tests in each tree node, we obtain 85% recognition rate on the independent test set using textual features only. This result is comparable with results we obtained by cross-validation on the training set (86%). Table 3.1 gives the first 50 textual terms used by the ensemble of trees and their relative importance for each class. Among the 13553 terms, the model is able to select very relevant ones to discriminate imaging modalities (e.g. the active molecule FDG for PET, the term photograph for PX, the scintigraphy test for NM, . . . ) but it does not filter out several artefacts neither rather neutral words (A, B, BB, BBB, IN, . . . ). 3.2
Using T = 10000 trees and K = √52660 = 230 random tests in each tree node of the final classifier, we obtained 75% recognition rate on the independant test set. This result is slightly better than results we obtained by cross-validation on the training set (71.75%). 3.3
Building an ensemble of T = 10000 trees using both textual and visual features (ie. 62213 input features) raised results up to 90% recognition rate. This final result is comparable with results we obtained by cross-validation on the training set (90.377% recognition rate using both feature types, see the confusion matrix in Table 2). To reduce computing times and give less importance to visual features than textual features, we introduced a new parameter, p, that indicates the proportion of visual features (randomly choosen) that each tree will use as input features. The value of K was fixed to its default value K = √13453 + p × 52660. The submitted result was obtained with p = 0.05 so that each tree was able to use 13553 textual features and 2633 (52660 × 0.05) visual features. This value yielded the best results by cross-validation on the training set.
Table 3 shows contribution of both feature types for each class. Visual features are the most useful for the GX (Graphics, typically drawing and graphs) imaging modality while textual features are the most useful for the PET imaging modality. Table 4 illustrates some test images and their classification confidences using individual feature types of a combination of them.
It has to be noted that we also experimented with LIBLINEAR 2 as final classifier on both feature types but results were slightly inferior (86.42% recognition rate by cross-validation on the training set) to those obtained with extremely randomized trees. 3.4
Our approach consists in rather simple operations, especially for the prediction phase. First, the training of 10 trees for the bag of visual terms construction takes about 20 hours when using about 4.6 million subwindows (2000 subwindows for each of the 2320 training images) on a single processor. This training phase is 2 http://www.csie.ntu.edu.tw/~cjlin/liblinear/ only performed once using all training images. Building the 10000 trees of the final classifier requires about 4 hours. Once trees have been built, the bag of visual terms of one test image is constructed on average in 0.83s (0.65s for the extraction and resizing of 2000 subwindows, 0.18s for their propagation in the ensemble of 10 trees). Computing the bag of textual term frequencies for test images requires 0.03s per image on average. Propagating an image (described by both textual and visual features) into the final classifier requires 0.01s per image. In total, a new image could then be described and classified roughly in less than 1s using both feature types on a single computer. 4
We obtained 90% recognition rate on the ImageCLEF 2010 modality classification task using a rather straightfoward and fast approach that combine textual and visual features. Optimization of parameters and other combination mechanisms might further improve results.
Acknowledgments. RM is supported by the GIGA (University of Li`ege) with the help of the Walloon Region and the European Regional Development Fund. PG is Research Associate of the F.R.S.-FNRS. This paper presents research results of the Belgian Network BIOMAGNET (Bioinformatics and Modeling: from Genomes to Networks), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. This work is supported by the European Network of Excellence, PASCAL2. The scientific responsibility rests with the authors. Image
ID
True Class Textual
Visual
Both 32316
PX
PX (0.81) XR (0.43) XR (0.47) 128482
MR
GX (0.41) MR (0.38) MR (0.50) 36398
PX
PX (0.80) CT (0.26) PX (0.32) 223797
GX
XR (0.42) GX (0.98) GX (0.86) 63382 XR PX (0.29) PET (0.36) XR (0.45) Table 4. Examples of image predictions using textual, visual or both feature types.