IPL at CLEF 2013 Medical Retrieval Task

Abstract

This article presents an experimental evaluation on using a re ned approach to the Latent Semantic Analysis (LSA) for e ciently searching very large image databases. It also describes IPL's participation to the image CLEF ad-hoc textual and visual retrieval as well as modality classi cation for the Medical Task in 2013. We report on our approaches and methods and present the results of our extensive experiments applying early data fusion with LSA on several low-level visual and textual features.

Keywords

• LSA
• LSI
• CBIR
• Data Fusion

-

http://ipl.cs.aueb.gr/index_eng.html Over the years latent semantic analysis has been applied with success in text retrieval providing successful results in several applications [ 1 ]. However, due to the challenges of LSA in terms of computational and memory requirements in cases of image retrieval, only small datasets have been tested. In our approach, our aim is the visual representation of an image with a feature vector of a moderate size, (m), and the use of a by-pass solution to the singular value decomposition which overcomes all its de ciencies and makes the method attractive for content-based image retrieval [ 2 ]. In this way instead of performing SVD to the feature-by-document matrix C, (m n) we solve the eigenproblem of the feature-correlation matrix CCT , (m m).

Concerning the stability of the eigensolution for the matrix CCT , the method may be unstable for two reasons: rst, the conditioning number of the matrix is much higher, and second, perturbations introduced while forming the normal matrix (CCT ) may change its rank. In such cases, the normal matrix will be more sensitive to perturbations in the data than the data matrix (C).

However the numerical stability of an eigenproblem is ensured when the eigenvalues are well separated [ 3 ]. During preliminary experiments and previous work [ 2 ][ 4 ], we have observed that the eigenvalues of CCT follow a power law distribution. This ensures that the largest eigenvalues are well separated. It was also indicated that a value of k (k largest eigenvalues) between 50 and 100 gives optimal results. Furthermore, matrix C is stored in integer form for both visual and textual data. Thus, no rounding is introduced in the computation of CCT matrix. To further reduce the size of the CCT matrix, we have applied a variance based feature selection. Thus, the largest eigenproblem that was required to be solved for this years' challenge was that of a CCT [1400 x 1400] matrix.

In order to overcome the increased memory demands for the computation of the correlation matrix CCT , matrix C is split into a number of blocks, such that each block can be accommodated into the memory. Subsequently, the eigenproblem is solved and the k largest eigenvalues, Sk, with their corresponding eigenvectors, Uk, are selected. The original feature vectors are then projected into the k-th dimensional space, using the transformation, yk = UkT y, on the original vector representation of an image y. The same projection is also applied for a query image qk with qk = UkT q and the similarity with an image score(qk; yk), is calculated by the cosine function.

The proposed method seems to greatly improve the nal database size, query response time and memory requirements. It is also shown that the e ciency of this method still holds in cases of large databases in cases such as the PubMED Database with 306.000 gures, used in this year's medical task [ 5 ]. It should be noted that by using the traditional solution of SVD for this database, the ad-hoc visual retrieval task would be impossible with our computer resources. This approach can also exploit the dimensionality reduction and enable the early data fusion of di erent low-level visual features, without increasing the cost in memory, disk space and response time of a retrieval system. 2 2.1

Visual Retrieval

Image Representation

For the low-level representation of each image, a set of localized image descriptors was extracted. In order to address the variations in resolution between images, rst, a size normalization was performed by re-scaling each image to a xed size of 256 x 256 pixels using bi-linear interpolation. Next, each image was split into 3 x 3 xed sized blocks and a local visual descriptor was extracted from each block. The image's nal feature vector was constructed by concatenating each local vector. i.e if for an image, we extract a gray color histogram in 128 colors per block, for a total of 9 blocks, the resulting feature vector will be of size 9 x 128 = 1152. This process is depicted in Figure 1.

In our experiments, the vector representation was based on seven types of low-level visual features: 1. Gray color histogram (CH) extracted in 128 gray scales. 2. Color layout (CL). 3. Scalable color (SC). 4. Edge histogram (EH). 5. CEDD. 6. FCTH. 7. Color Correlogram (CORR).

All the features were extracted using the Java library Caliph&Emir of the Lire CBIR system [ 6 ]. Finally, by using feature selection, the vector for each descriptor was reduced into a fraction of its original size. Table 1 lists the visual descriptors along with their corresponding vector size per block and per image before and after feature selection.

Early Fusion

In order to improve retrieval e ciency, di erent low level visual descriptors were combined with early fusion. Image descriptor vectors were concatenated to create a single fused vector thus, creating the feature-by-document matrix C previously mentioned. The query feature vectors were fused with the same order and the resulting vector was projected as described in 1. For example, the early fusion of CH, CEDD and FCTH features will form the matrix C = [CH; CEDD; F CT H; ] in matlab notation of size 306:000 x 800.

The solution of the CCT U = U S2 problem was done for a CCT of size 800 x 800. The eigs function of Matlab was used for this solution. For the visual retrieval task, several data fusion combinations of di erent descriptors were tested. These combinations are presented in Table 2 along with the task's corresponding run ID. To further improve the retrieval e ciency, modality class vectors were constructed by using a subset of the classi ers used for the modality classi cation task. For this method, a combination of low level feature vectors was extracted from each image as described above. In addition, each image was classi ed into one of the 31 modalities and a very sparse vector CV of size [31x1] was created by setting the value '1' at the index that corresponds to the predicted modality. The rest of the vector's elements are set to '0'. Finally, this vector was early fused with the rest of the visual vectors, i.e for the previous example, the matrix C = [CH; CEDD; F CT H; CV ; ] was formed. Table 3 presents the runs using this method with their corresponding run ID, visual descriptors and classi er used. 2.4

Results

For the AMIA's medical task [ 5 ] we have submitted a total of eight visual runs using di erent combinations of low level feature descriptors with early fusion and class ltering. In Table 4, we list the runs ids with their corresponding results. Finally, we attempted to test how our retrieval method responds in image datasets of di erent sizes and context. Thus, in this year's ImageCLEF [ 7 ], we have also participated to the ImageCLEF's Personal photo retrieval sub-task [ 8 ] using the feature combinations listed in Table 2. Since no form of classi cation data were provided for this task, class ltering methods were not tested. In Table 5, we list the corresponding results obtained from the Average user ground truth set. The results for other types of users (non-expert, expert etc), were similar. In our approach, images were represented as structured units, consisting of several elds. We used Lucene's API in order to index and store each image as a set of elds alongside with boosting the elds of each image when submitting a query. This technique helped in experimenting with di erent weights and combinations of these elds.

For every image in the given database we stored ve features: Title, Caption, Abstract, MeSH and Textual References. MeSH terms related with each article provide extra information for the contained gures. MeSH terms were downloaded from the Pubmed ID of the article. Finally, we extracted every sentence inside the article that refers to an image, and used this set of sentences as a consistent eld named Textual References. 3.1

Experiments and Results

Details on the ad-hoc textual image retrieval task are given in [ 5 ]. Our experiments were based on previous participations [ 4 ] of the Information Processing Laboratory.

To achieve even higher MAP values than our 2012 runs, we carried out several experiments with di erent boosting factors, using as a train set the qrels from ImageClef 2012.

Motivated to achieve better results, we experimented in eld selection, which revealed that the use of the Title along with Caption provides a strong combination. Moreover, a heuristic was applied to nd the best boosting factors per eld. Experiments with the best MAP values for the CLEF-2012 database are presented in Table 6, where T, C, A, M and TR are the boosting factors for Title, Caption, Abstract, MeshTerms, Textual References respectively. In addition, TC is a joint combination of Title and Caption in one eld. The use of this eld without any boosting factor was placed second in this year's ad-hoc textual retrieval task.

T=0.65 A=0.57 C=3.50 M=0.57 T=0.625 A=0.57 C=3.50 M=0.5 T=0.625 A=0.555 C=3.50 M=0.555 T=0.1 A=0.113 C=0.335 M=0.1 T=1 A=1 C=6 M=0.2 TC (no boosting factor) T=0.3 A=0.79 C=3.50 M=0.73 TR=0.11 TC=0.26 A=0.02

MAP 0.2051 0.2051 0.2050 0.2016 0.2021 0.2177 0.2106

GMMAP 0.0763 0.0762 0.0757 0.0765 0.0729 0.0848 0.0797 bpref 0.2071 0.2071 0.2061 0.1991 0.2003 0.2322 0.2047 p10 0.3227 0.3227 0.3227 0.2955 0.3182 0.3500 0.3227 p30 0.2061 0.2076 0.2045 0.2091 0.2076 0.2045 0.2182

These runs were our submissions to the textual ad-hoc image-based retrieval task. In r4 and r5 (Table 6) we have kept the boosting factors from our former participation at ImageClef 2012. In Table 7 we present the nal results of these eight submissions of the IPL Group.

Modality Classi cation

Experiments Settings

All our experiments were run using various combinations of the seven types of low-level visual features presented in Section 2.1 and of the textual data described in Section 3, with and without early data fusion and/or LSA applied. We employed the SVMlight [ 9 ][ 10 ] implementation of Support Vector Machines (SVMs) and Transductive Support Vector Machines (TSVMs) to perform multiclass classi cation, using a one-against-all voting scheme. It should be noted here that with the term multi-class we refer to problems in which any instance is assigned exactly one class label. In our experiments, following the one-against-all method, k binary SVM/TSVM classi ers (where k is the number of classes) were trained to separate one class from the rest. The classi ers were then combined by comparing their decision values on a test data instance and labeling it according to the classi er with the highest decision value. No parameter tuning was performed. A binary classi er was constructed for each dataset, a linear kernel was used and the weight C of the slack variables was set to default. 4.2

Results

Details on the modality classi cation task are given in [ 5 ]. In Table 8, we present the results of the above experiments for the various types of classi cation, i.e. for textual, visual, and mixed classi cation. As a measure of classi cation performance we used accuracy.

As expected, mixed classi cation, on both visual and textual features, yielded the best performance in all cases compared to visual or textual only classi cation, scoring a 71.42% accuracy when applying SVMs on a combination of textual features (Title and Caption in one eld with no boosting factor (TC)) with CORR,CL,CEDD, and CH visual descriptors. LSA was tested for di erent values of the k largest eigenvalues (50, 100, 150, 200). The best results were accomplished for k = 200, for some descriptors it was almost equal to SVMs applied on the whole dataset.

Textual classi cation with SVMs succeeds a 65.29% accuracy score. When LSA is applied on the dataset for k = 150, it gives competitive results compared to the original vectors. It should be reminded that the original vectors have 147:000 features.

For classi cation on visual features only, the CEDD descriptor with SVMs has the best performance against the other descriptors with 61.19% accuracy score. When more than one low level feature descriptors are combined with early fusion into one fused vector, SVMs perform better in all cases. LSA was tested for di erent values of the k largest eigenvalues (50, 100, 150). The best results were accomplished for k = 150 and it should be noted that they highly approximate those of SVM when applied on the original feature vectors.

The runs that were submitted to the modality classi cation task were based on the experiments presented above, but other methods were also tested. A description of the runs is given in Table 9. It should be noted that the textual data used in the runs contained only terms with document frequency larger than 1000. In this case, the dimensionality of the textual dataset is dramatically reduced to 10:000 features, drastically less than the 147:000 features of the textual dataset used in the former experiments. Also, apart from using TSVMs for classi cation, we also experimented on using class-centroid-based classi cation [ 11 ]. This method had the advantage of short training and testing time due to its computational e ciency. However, the accuracy of the centroid-based classi ers was inferior. We speculate that the centroids found during construction were far from perfect locations. We have presented an approach to LSA for CBIR replacing the SVD analysis of the feature matrix C (m n) by the solution of the eigenproblem for the matrix CCT (m m). The method overcomes the high cost of SVD in terms of memory and computing time. More work on stability issues is currently underway.

Moreover, some cases of the usage of modality class vectors in early fusion techniques, have shown that can further improve retrieval results. Additional work in this direction is also in progress, by systematically testing more advanced classi ers and di erent low-level features.

Also, the inclusion of textual information, extracted from the meta-data provided, is also investigated. Speci cally, the number of the extracted textual terms ( 147; 000) is far greater in comparison to the size of visual features. Hence, increased memory requirements and complexity is introduced. This problem is open for future research on several solutions like term selection or the use of an ontology in order to extract semantic keywords that strongly de ne a document.

For the modality classi cation task, mixed classi cation, on both visual and textual features, yielded the best performance in all cases compared to visual or textual only classi cation. The application of SVMs for image classi cation had a positive impact, verifying previous ndings.

References

1. Deerwester , S.C. , Dumais , S.T. , Landauer , T.K. , Furnas , G.W. , Harshman , R.A. : Indexing by latent semantic analysis . JASIS 41 ( 6 ) ( 1990 ) 391 { 407

2. Stathopoulos , S. , Kalamboukis , T. : An svdbypass latent semantic analysis for image retrieval . In Greenspan, H., Muller , H. , Syeda-Mahmood , T., eds.: Medical Content-Based Retrieval for Clinical Decision Support . Volume 7723 of Lecture Notes in Computer Science. Springer Berlin Heidelberg ( 2013 ) 122 { 132

3. Golub , G.H., van Loan, C.F. : Matrix computations (3 . ed.). Johns Hopkins University Press ( 1996 )

4. Stathopoulos , S. , Sakiotis , N. , Kalamboukis , T. : Ipl at clef 2012 medical retrieval task . In Forner, P., Karlgren , J. , Womser-Hacker , C., eds.: CLEF (Online Working Notes/Labs/Workshop). ( 2012 )

5. Seco de Herrera , A.G. , Kalpathy-Cramer , J. , Fushman , D. , Antani , S. , Muller, H.: Overview of the imageclef 2013 medical tasks . In: Working notes of CLEF 2013 , Valencia, Spain. ( 2013 )

6. Lux , M. , Chatzichristo s , S.A.: Lire: lucene image retrieval: an extensible java cbir library . In: ACM Multimedia . ( 2008 ) 1085 { 1088

7. Caputo , B. , Muller, H., Thomee , B. , Villegas , M. , Paredes , R. , Zellhofer , D. , Goeau , H. , Joly , A. , Bonnet , P. , Martinez Gomez , J. , Garcia Varea , I. , Cazorla , M. : Imageclef 2013: the vision, the data and the open challenges . In: Proceedings of CLEF 2013 , Valencia, Spain, Springer LNCS ( 2013 )

8. Zellhofer, D.: Overview of the imageclef 2013 personal photo retrieval subtask . In: Working notes of CLEF 2013 , Valencia, Spain. ( 2013 )

9. Joachims , T. : Learning to Classify Text Using Support Vector Machines . Dissertation . Kluwer ( 2002 )

10. Joachims , T. : Transductive inference for text classi cation using support vector machines . In: 16th International Conference on Machine Learning , San Francisco: Morgan Kaufmann ( 1999 ) 200 { 209

11. Han , E.H.S. , Karypis , G.: Centroid-based document classi cation: Analysis & experimental results . In: 4th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD) . ( 2000 ) 424 { 431