=Paper=
{{Paper
|id=Vol-1177/CLEF2011wn-ImageCLEF-FariaEt2011
|storemode=property
|title=RECOD at ImageCLEF 2011: Medical Modality Classification using Genetic Programming
|pdfUrl=https://ceur-ws.org/Vol-1177/CLEF2011wn-ImageCLEF-FariaEt2011.pdf
|volume=Vol-1177
}}
==RECOD at ImageCLEF 2011: Medical Modality Classification using Genetic Programming==
<pdf width="1500px">https://ceur-ws.org/Vol-1177/CLEF2011wn-ImageCLEF-FariaEt2011.pdf</pdf>
<pre>
RECOD at ImageCLEF 2011: Medical Modality
  Classification using Genetic Programming

 Fábio Augusto Faria, Rodrigo Tripodi Calumby, and Ricardo da Silva Torres

                  Institute of Computing - University of Campinas
                             Campinas, São Paulo, Brazil
                    {ffaria,tripodi,rtorres}@ic.unicamp.br
                             http://www.ic.unicamp.br



      Abstract. This paper describes the participation of the RECOD group
      on the ImageCLEF 2011 Medical Modality Classification sub-task. We
      present an approach based on genetic programming and kNN for image
      classification. 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 different visual evidences such as color,
      texture, and shape. For each class of the dataset a combination function
      was learned and used as a kNN classifier. Final classification results were
      generated by a majority voting scheme with the voting functions from
      each class. Preliminary experiments have shown a good effectiveness of
      the approach and its potential for improvements.

      Keywords: Genetic Programming, Medical Images, Image Classifica-
      tion, Pattern Recognition


1   Introduction
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
classification [1].
    In the medical field, the classification task is conducted for several types
of images (e.g., x-ray, CT, and endoscopy) [2, 7, 4]. In [2], learning techniques
are used for the detection and classification of benign and malign tumors and
in [3] it is used to determine the gestational age of newborns. Moreover intelligent
image classification approaches are used in several different fields such as diseases
diagnosis [20], biometrics [6, 14], biology [23], and remote sensing [18].
    In the image classification task, descriptors can be used to extract visual
features from the images. A visual descriptor can be described by two func-
tions; (1) an extraction algorithm that encodes visual characteristics (e.g., color,
texture, and shape) into a feature vector; (2) a similarity measure (distance
2      Fábio Augusto Faria, Rodrigo Tripodi Calumby, and Ricardo da Silva Torres

function) that computes the similarity of two images using their respective fea-
ture vectors. Hence different descriptors potentially describes different features
for distinct visual evidences or even for the same evidence. For instance, the
BIC [19] and JAC [24] descriptors characterize the color evidence by different
means. One descriptor may be more effective for a dataset than another one,
but no descriptor is perfect for all collections.
    Therefore the use of learning techniques to combine different visual evidences
has the objective of increasing the effectiveness of the classifiers by taking ad-
vantage of the power of different but potentially complementary descriptors.
In this work we propose the use of Genetic Programming as a learning tech-
nique together with kNN classifiers (GP+kNN) for image classification tasks.
This technique has been used in several application such as data mining, signal
processing, image retrieval and classification [12, 5, 8, 26, 17].
    The remaining of this text is organized as follows: Section 2 briefly describes
the genetic programming technique. Section 3 presents our proposed approach
for image classification using genetic programming. In Section 4 we present ex-
perimental setup and results for the ImageCLEF 2011 Medical Modality Classi-
fication. Finally, Section 5 presents our conclusions and future work.


2   Genetic Programming

Genetic Programming [13] is a machine learning technique based on biology evo-
lutionary concepts, such as natural selection and survival. In this context each
potential solution is seen as an individual evolving in a population. Evolution-
ary transformations are iteratively applied on the populations thus simulating
sequential generations of individuals. Hence the individuals evolve by genetic
transformations such as reproduction, mutation and crossover.
    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 fitness 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 fitness of each individual
4: Select the individuals to genetic operations
5: Apply reproduction
6: Apply crossover
7: Apply mutation
8: end for
                            Modality Classification using Genetic Programming             3

    At first the initial population is generated, usually in random fashion (line 1).
The iterative process starts for the evolution of the population through N gen-
erations (line 2). For each generation the fitness 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 reproduc-
tion 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 different visual de-
scriptors. 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 different
visual descriptors di .




                  (a)                                       (b)

    Fig. 1. (a) Individual represented as a tree (b) Corresponding similarity function.


     Details of our GP-based classification approach are presented in Section 3.


3      GP+kNN Classification Method
The approach for visual image classification of this paper was adapted from the
one originally proposed in [25] for textual documents. Our approach is presented
in Algorithm 2.
    At the beginning the classifier is trained by the search of the best GP indi-
viduals (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
4       Fábio Augusto Faria, Rodrigo Tripodi Calumby, and Ricardo da Silva Torres

Algorithm 2 Approach for image classification using GP and kNN classifiers
Require: Training set (D), validation set (V), and test set (T ), number of classes
    (Nc ), number of generations (Ngen )
 1: for all i | 1 <i ≤ Nc do
 2:    Generate individuals populations (similarity functions) for each class ci
 3:    for all j | 0 <j ≤ Ngen do
 4:      Calculate the fitness of the individuals using the fitness function and (D)
 5:      Store Ntop fittest 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 | 1 <w ≤ T do
11:    for all i | 1 <i ≤ Nc do
12:      Vwi ⇐ Ici + kN N applied to image w (Ici + kN N is the kNN classifier 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 find the Ngen × Ntop candidates individuals and V is
used to find the best individuals for each class. The classification 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 classifiers. The final
classification for each image w is decided by a majority voting using the output
of all kN N classifiers.

3.1   Fitness Function

The fitness 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.


Algorithm 3 FFP4 fitness function algorithm
1: F = 0
2: For each image D in class C
3: F itnessD = F F P 4 calculated using the |C| images most similar to D
4: F + = F itnessD
5: F = F/C
                          Modality Classification using Genetic Programming       5

      The F F P 4 equation is defined as:

                                     |C|
                                     X
                            FFP4 =          r(di ) ∗ k8 ∗ (k9 )i                (1)
                                      i=1

where r(d) is the relevance of the image(1 if it is relevant, 0 otherwise). |C| is
the total number of images similar to D. For each image in class C, the fitness
value is computed based on Eq. 1, and the final fitness 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 [25].


4      Experiments
This section presents the methodology of the parametric search for the genetic
programming approach and for the generation of final results for the ImageCLEF
2011 Medical Modality Classification Task.

4.1     Visual Descriptors
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.


                           Descriptor Visual Evidence
                           ACC [10]           Color
                           BIC [19]           Color
                           CCV [16]           Color
                           CCOM [11]          Color
                           EOAC [15]          Shape
                           GCH [21]           Color
                           JAC [24]           Color
                           LAS [22]          Texture
                           QCCH [9]          Texture
              Table 1. Visual image descriptors used in the experiments.




4.2     Data Setup
For the experiments on the genetic programming parametric search and for the
final classification generation we created three different sub-datasets from the
original train and test dataset of the classification task. On the parametric search
the original training dataset from the task (989 images) was split into training
6       Fábio Augusto Faria, Rodrigo Tripodi Calumby, and Ricardo da Silva Torres

(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 con-
ducted in order to find a good parametric setup for the genetic programming
approach that should be used for original modality classification test set. The
best configurations 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 classifier, crossover, reproduction and mutation rates,
and also the classification accuracy (Acc) obtained on the ps test for each GP
configuration.


  Setup Pop # of Gen kNN Crossover Reproduction Mutation Acc(%)
    S1    10      10       1       0.9           0.1          0.7      68.78
    S2    10      10       5       0.9           0.1          0.9      67.80
    S3    10      10       7       0.1           0.2          0.7      68.78
 Table 2. Best GP configurations found on the parametric search on the PSdataset.



    For the final classification results for the original test set of the modality
classification sub-task we used two different sub-datasets. The first 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.


                Dataset Training Validation Testing Overall
                PSdataset  547         237       205      989
                 Small     547         237       1024     1808
                  Large    752         237       1024     2013
              Table 3. Number of images samples of the sub-datasets.




4.3   Final Results
For the ImageCLEF 2011 Medical Modality Classification sub-task our group
submitted 10 runs with different sub-datasets and genetic programming config-
urations. The runs from 1 to 3 were generated using the Small sub-dataset with
S1, S2 and S3 GP configurations, 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 final classifications were decided
by the classification present on runs 1 and 4, respectively.
                          Modality Classification using Genetic Programming           7

    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 final classification
was randomly chosen from one the voting runs.
    Table 4 summarizes the configurations used for each run and their respective
classification accuracy. The best run is highlighted.


     Run    Setup                 Run name               Accuracy(%)
     1        S1        recod imageclefmed ModCla 343s      67.87
     2        S2        recod imageclefmed ModCla 357s      66.69
     3        S3        recod imageclefmed ModCla 370s      67.67
     4        S1        recod imageclefmed ModCla 343l      67.48
     5        S2      recod imageclefmed ModCla 357l        69.72
     6        S3        recod imageclefmed ModCla 370l      67.87
     7   S1,S2 and S3 recod imageclefmed ModCla VsNoR       68.35
     8   S1,S2 and S3 recod imageclefmed ModCla VlNoR       69.04
     9   S1,S2 and S3    recod imageclefmed ModCla Vs       68.06
     10 S1,S2 and S3     recod imageclefmed ModCla Vl       69.43
                        Table 4. Classification results.




5    Conclusion

For the ImageCLEF 2011 Medical Modality Classification sub-task this work
proposed the use of a learning technique for the combination of different visual
evidences. The approach described in this paper is based on the use of genetic
programming for the learning of effective similarity measures for the combination
of visual similarities obtained from a set of global visual descriptors. For this
purpose a kNN classifier using the similarity functions discovered was built for
each class of the dataset and the final classification results were generated by a
majority voting scheme.
    In our experiments the GP+kNN classifiers 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 effectiveness growing of the approach, for example,
by using more folds on the training step, using different visual descriptors and
also incorporating textual information on the similarity functions.


Acknowledgments. FAPESP, CNPq and CAPES for financial support.
8       Fábio Augusto Faria, Rodrigo Tripodi Calumby, and Ricardo da Silva Torres

References
 1. Andaló, F.A., Torres, R.d.S.: Descritores de forma baseados em tensor scale. Mas-
    ter’s thesis, Instituto de Computação, Unicamp, Campinas, SP, Brazil (2007)
 2. Antonie, M.L., Zaiane, O.R., Coman, A.: Application of Data Mining Tecniques for
    Medical Image Classification. In: 2nd Int. Workshop on Multimedia Data Mining
    MDM/KDD2001 (2001)
 3. Araújo, A.V.e.a.: Aplicando Mineração de Imagem para Auxiliar na Determinação
    da Idade Gestacional em Recém-Nascidos. XI Congresso Brasileiro de Informática
    em Saúde, Florianópolis, Brazil (2006)
 4. Bai, X., Qian, X.: Medical image classification based on fuzzy support vector ma-
    chines. In: ICICTA ’08: Proceedings of the 2008 International Conference on In-
    telligent Computation Technology and Automation. pp. 145–149. IEEE Computer
    Society, Washington, DC, USA (2008)
 5. Bhanu, B., Lin, Y.: Object Detection in Multi-Modal Images Using Genetic Pro-
    gramming. Applied Soft Computing (2004)
 6. Bowyer, K.W., Hollingsworth, K., Flynn, P.J.: Image understanding for iris bio-
    metrics: A survey. Computer Vision and Image Understanding 110(2), 281–307
    (2008)
 7. Cheng, P., Chien, B., Yang, W.: Medical image classification by supervised machine
    learning. In: AIC’06: Proceedings of the 6th WSEAS International Conference on
    Applied Informatics and Communications. pp. 106–110. World Scientific and En-
    gineering Academy and Society (WSEAS), Stevens Point, Wisconsin, USA (2006)
 8. Fan, W., Fox, E.A., Pathak, P., Wu, H.: The effects of fitness functions on genetic
    programming-based ranking discovery for web search: Research articles. J. Am.
    Soc. Inf. Sci. Technol. 55(7), 628–636 (2004)
 9. Huang, C., Liu, Q.: An orientation independent texture descriptor for image re-
    trieval. In: International Conference on Computational Science. pp. 772–776 (2007)
10. Huang, J., Kumar, R., Mitra, M., Zhu, W., Zabih, R.: Image indexing using color
    correlograms. In: IEEE Conference on Computer Vision and Pattern Recognition.
    pp. 762–768 (1997)
11. Kovalev, V., Volmer, S.: Color co-occurence descriptors for querying-by-example.
    In: Proceedings of the 1998 Conference on MultiMedia Modeling. pp. 32–38 (1998)
12. Koza, J.: Genetic Programming: On the programming of computers by natural
    selection. MIT Press (1992)
13. Koza, J.R.: Genetic Programming: On the Programming of Computers by Means
    of Natural Selection. MIT Press, Cambridge, MA, USA (1992)
14. Kumar, A., Passi, A.: Comparison and combination of iris matchers for reliable
    personal authentication. Pattern Recognition 43(3), 1016–1026 (2010)
15. Mahmoudi, F., Shanbehzadeh, J., Eftekhari-Moghadam, A., Soltanian-Zadeh, H.:
    Image retrieval based on shape similarity by edge orientation autocorrelogram.
    Pattern Recognition 36(8), 1725–1736 (2003)
16. Pass, G., Zabih, R., Miller, J.: Comparing images using color coherence vectors.
    In: ACM Multimedia. pp. 65–73 (1996)
17. da S. Torres, R., Falcão, A.X., Goncalves, M.A., Papa, J.P., Zhang, B., Fan, W.,
    Fox, E.A.: A genetic programming framework for content-based image retrieval.
    Pattern Recognition 42(2), 283–292 (2009)
18. Santos, J.A., Torres, R.d.S.: Reconhecimento Semi-Automaático e Vetorização de
    Regiões em Imagens de Sensoriamento Remoto. Master’s thesis, Campinas, SP,
    Brazil (2009)
                          Modality Classification using Genetic Programming           9

19. Stehling, R., Nascimento, M., Falcão, A.: A compact and efficient image retrieval
    approach based on border/interior pixel classification. In: CIKM. pp. 102–109
    (2002)
20. Suzuki, C.T.N.: Segmentação de Imagem de Parasitos Intestinais do Homem. Mas-
    ter’s thesis, Campinas, SP, Brazil (2007)
21. Swain, M., Ballard, D.: Color indexing. International Journal of Computer Vision
    7(1), 11–32 (1991)
22. Tao, B., Dickinson, B.: Texture recognition and image retrieval using gradient
    indexing. Journal of Visual Communication and Image Representation 11(3), 327–
    342 (2000)
23. Tofilski, A., Wing, D.: A program for numerical description of insect wings. Journal
    of Insect Science 4(17), 1–5 (2004)
24. Williams, A., Yoon, P.: Content-based image retrieval using joint correlograms.
    Multimedia Tools and Applications 34(2), 239–248 (2007)
25. Zhang, B., Chen, Y., Fan, W., Fox, E.A., Gonçalves, M., Cristo, M., Calado, P.:
    Intelligent gp fusion from multiple sources for text classification. In: CIKM ’05:
    Proceedings of the 14th ACM international conference on Information and knowl-
    edge management. pp. 477–484. ACM, New York, NY, USA (2005)
26. Zhang, B., Gonçalves, M.A., Fan, W., Chen, Y., Fox, E.A., Calado, P., Cristo, M.:
    Combining structural and citation-based evidence for text classification. In: CIKM
    ’04: Proceedings of the thirteenth ACM international conference on Information
    and knowledge management. pp. 162–163. ACM, New York, NY, USA (2004)

</pre>