This paper describes the participation of the RECOD group on the ImageCLEF 2011 Medical Modality Classi cation sub-task. We present an approach based on genetic programming and kNN for image classi cation. In our approach the genetic programming is used for the learning of good functions for the combination of similarities obtained from a set of global descriptors for di erent visual evidences such as color, texture, and shape. For each class of the dataset a combination function was learned and used as a kNN classi er. Final classi cation results were generated by a majority voting scheme with the voting functions from each class. Preliminary experiments have shown a good e ectiveness of the approach and its potential for improvements.
Currently with the advance of the technology of acquisition and storage of images
along with the popularization of the Internet use we can notice the emerging of
big image collections. Furthermore the increase of storage and processing power
makes possible the use of intelligent computer systems for image manipulation
based on machine learning. Machine learning techniques are used, for instance,
on image processing, pattern analysis and recognition, and image retrieval, and
classi cation [
In the medical eld, the classi cation task is conducted for several types
of images (e.g., x-ray, CT, and endoscopy) [
In the image classi cation task, descriptors can be used to extract visual
features from the images. A visual descriptor can be described by two
functions; (1) an extraction algorithm that encodes visual characteristics (e.g., color,
texture, and shape) into a feature vector; (2) a similarity measure (distance
function) that computes the similarity of two images using their respective
feature vectors. Hence di erent descriptors potentially describes di erent features
for distinct visual evidences or even for the same evidence. For instance, the
BIC [
Therefore the use of learning techniques to combine di erent visual evidences
has the objective of increasing the e ectiveness of the classi ers by taking
advantage of the power of di erent but potentially complementary descriptors.
In this work we propose the use of Genetic Programming as a learning
technique together with kNN classi ers (GP+kNN) for image classi cation tasks.
This technique has been used in several application such as data mining, signal
processing, image retrieval and classi cation [
The remaining of this text is organized as follows: Section 2 brie y describes the genetic programming technique. Section 3 presents our proposed approach for image classi cation using genetic programming. In Section 4 we present experimental setup and results for the ImageCLEF 2011 Medical Modality Classication. Finally, Section 5 presents our conclusions and future work. 2
Genetic Programming [
In general, GP individuals are encoded in a tree structure that represent programs that will evolve throughout the solution space towards a good solution for the problem. A tness function is used to evaluate the individuals, and then it is possible to measure the quality of the solutions found in the evolutionary process. A basic evolution algorithm for genetic programming is presented in Algorithm 1.
Algorithm 1 Basic GP evolution algorithm. 1: Generate initial population of individuals 2: for N generations do 3: Calculate the tness of each individual 4: Select the individuals to genetic operations 5: Apply reproduction 6: Apply crossover 7: Apply mutation 8: end for
At rst the initial population is generated, usually in random fashion (line 1). The iterative process starts for the evolution of the population through N generations (line 2). For each generation the tness of the individuals are computed (line 3) and the genetic operators are then applied to the selected individuals. In order to evolve the population some individuals are properly selected (line 4) and they are subjected to genetic operators. The operators are responsible to introduce variability on the solutions making the moving through the solution space possible and consequently the discovery of better solutions. The reproduction operator just copies an individual to next generation (line 5). The crossover operator takes two individuals and exchange sub-trees from them creating two new individuals (line 6). The mutation operator just selects a random sub-tree from an individual and exchanges it for a new randomly generated sub-tree (line 7).
In our approach tree-based GP individuals are used to encode candidate functions that combine similarity measures obtained from di erent visual descriptors. In these trees inner nodes are arithmetic operators and the leaves are input nodes for similarity values computed using visual descriptors. Figure 1 presents an example combination function DP G that combines four di erent visual descriptors di.
(a)
(b)
The approach for visual image classi cation of this paper was adapted from the
one originally proposed in [
At the beginning the classi er is trained by the search of the best GP individuals (Ici ), which means the search for the best similarity functions for each class ci using the training set (D) and the validation set (V) (lines 1 to 9). For Algorithm 2 Approach for image classi cation using GP and kNN classi ers Require: Training set (D), validation set (V), and test set (T ), number of classes (Nc), number of generations (Ngen) 1: for all i j 1 <i Nc do 2: Generate individuals populations (similarity functions) for each class ci 3: for all j j 0 <j Ngen do 4: Calculate the tness of the individuals using the tness function and (D) 5: Store Ntop ttest individuals 6: Create a new population by: reproduction, crossover and mutation 7: end for 8: end for 9: Select the best Ici individual, among the Ngen Ntop candidates using (V), which is unique for each class ci 10: for all w j 1 <w T do 11: for all i j 1 <i Nc do 12: Vwi ( Ici + kN N applied to image w (Ici + kN N is the kNN classi er using the individual of the class ci) 13: end for 14: Class of w ( majority voting between all Vwi 15: end for this purpose D is used to nd the Ngen Ntop candidates individuals and V is used to nd the best individuals for each class. The classi cation step is then conducted on lines 10 to 15 for the test set (T )
For the multi-class problem the algorithm uses Nc kN N classi ers. The nal classi cation for each image w is decided by a majority voting using the output of all kN N classi ers. 3.1
The tness function used in our experiments was the FFP4 and its steps are presented in Algorithm 3. The bigger is the value of F the best is the similarity function.
1: F = 0 2: For each image D in class C 3: F itnessD = F F P 4 calculated using the jCj images most similar to D 4: F + = F itnessD 5: F = F=C
F F P 4 =
jCj
X r(di) k8 (k9)i
i=1
(1)
where r(d) is the relevance of the image(1 if it is relevant, 0 otherwise). jCj is
the total number of images similar to D. For each image in class C, the tness
value is computed based on Eq. 1, and the nal tness is calculated as the mean
FFP4 value for all images. The k8=7.0 e k9=0.982 were used according to the
exhaustive analysis in [
This section presents the methodology of the parametric search for the genetic programming approach and for the generation of nal results for the ImageCLEF 2011 Medical Modality Classi cation Task. 4.1
In this work we used a set of nine visual descriptors for global features such as color, texture and shape. Table 1 presents the descriptors used and the respective kind of evidence encoded. For the experiments on the genetic programming parametric search and for the nal classi cation generation we created three di erent sub-datasets from the original train and test dataset of the classi cation task. On the parametric search the original training dataset from the task (989 images) was split into training (ps train, 56%), validation (ps val, 24%) and testing (ps test, 20%) sub-datasets named PSdataset. With this three sub-datasets an exploratory search was conducted in order to nd a good parametric setup for the genetic programming approach that should be used for original modality classi cation test set. The best con gurations found are presented on Table 2. Table 2 presents the number of individuals on the population (Pop), the number of generations (# of Gen), the k factor on the kNN classi er, crossover, reproduction and mutation rates, and also the classi cation accuracy (Acc) obtained on the ps test for each GP con guration.
For the nal classi cation results for the original test set of the modality classi cation sub-task we used two di erent sub-datasets. The rst one has the same training and validation sub-datasets of the PSdataset previously mentioned and was named as Small. The second one has the same validation sub-dataset of the PSdataset but at this time the training sub-dataset was composed by joining the ps train and ps test sub-datasets and was named Large. All sub-datasets were randomly generated from the original ones and Table 3 summarizes the amount of image samples for each sub-dataset used on the experiments. For the ImageCLEF 2011 Medical Modality Classi cation sub-task our group submitted 10 runs with di erent sub-datasets and genetic programming con gurations. The runs from 1 to 3 were generated using the Small sub-dataset with S1, S2 and S3 GP con gurations, respectively. Similarly runs from 4 to 6 were generated using the Large sub-dataset.
For the runs 7 and 8 we conducted a majority voting on the results from 1 to 3 and 4 to 6, respectively. In case of ties the nal classi cations were decided by the classi cation present on runs 1 and 4, respectively.
Finally for runs 9 and 10 we conducted a majority voting on the results from 1 to 3 and 4 to 6, respectively. For this time, in case to ties the nal classi cation was randomly chosen from one the voting runs.
Table 4 summarizes the con gurations used for each run and their respective classi cation accuracy. The best run is highlighted. For the ImageCLEF 2011 Medical Modality Classi cation sub-task this work proposed the use of a learning technique for the combination of di erent visual evidences. The approach described in this paper is based on the use of genetic programming for the learning of e ective similarity measures for the combination of visual similarities obtained from a set of global visual descriptors. For this purpose a kNN classi er using the similarity functions discovered was built for each class of the dataset and the nal classi cation results were generated by a majority voting scheme.
In our experiments the GP+kNN classi ers were trained to combine visual evidences from images (e.g., color, texture, and shape). In the experiments the worst run submitted achieved an accuracy of 66.69% on the test set and our best run achieved 69.71%. Since we conducted only preliminary experiments we foresee a great potential of e ectiveness growing of the approach, for example, by using more folds on the training step, using di erent visual descriptors and also incorporating textual information on the similarity functions. Acknowledgments. FAPESP, CNPq and CAPES for nancial support.