This paper describes the participation of the Bioingenium research group of Universidad Nacional de Colombia in the ImageCLEF2012 Medical Retrieval challenge, speci cally in the ad-hoc image-based retrieval task. The methods used for solving textual and visual queries with which we submitted uni-modal runs are described. They were ranked 1st and 3rd respectively. These results have been obtained by using our own implementation of Okapi-BM25 weighting scheme for text retrieval, and by adding spatial layouts to the CEDD descriptors for visual retrieval. We also used these uni-modal features to learn multimodal representations using matrix factorization for solving visual queries. Despite the potential of multimodal indexes to improve the quality of visual queries, these experiments were not as successful as uni-modal indexes. We discuss the main ndings of all these experiments.
This paper describes the participation of the Bioingenium research group of
Universidad Nacional de Colombia in the 2012 version of the Medical Image
Retrieval challenge at ImageCLEF [
For text indexing, we developed our own implementation of Okapi-BM25, which allows to determine limits on the number of terms used in the vector representation, by pruning irrelevant terms and keeping the most informative ones. For visual indexing, we introduced a spatial pyramid of CEDD features, making recursive partitions of the image and computing descriptors in each subregion. This representation extends the popular CEDD descriptor with spatial information, which results in an improved performance. We also implemented spatial extensions for bag-of-features histograms.
Our second motivation was to build an enhanced image index using both modalities, but for searching with visual examples only. The goal was to learn a multimodal representation that incorporates textual and visual information in the database, and then predict the multimodal representation for queries using visual features. This represents a very challenging problem since the medical image collection, with more than 300K images, constitutes a very large training set that poses computational di culties for most learning algorithms. Other problems arise from this large multimodal image collection, such as the high dimensionality of textual and visual representations, and the presence of noise.
The results obtained with uni-modal strategies were successful in the general pooling, which ranked rst in the case of textual queries among 54 other submissions, and third in the case of visual queries among 36 experiments. We consider that the multimodal indexing submission was not successful since it did not improve upon our own visual indexing strategy, which was the original goal. However, further experiments conducted o competition demonstrate interesting improvements. We believe that further research in this front may help to design more accurate image search systems working with the query-by-visual-example paradigm.
The structure of this paper is as follows: Section 2 brie y describes the medical image collection, Section 3 describes our text indexing approach, Section 4 presents the visual indexing strategies, Section 5 discusses the multimodal indexing approach for visual queries, and nally, conclusions and future works are outlined in Section 6. 2
The medical retrieval task of ImageCLEF 2012 is based on a subset of PubMed Central papers, containing 305,000 images extracted from biomedical articles. Participants have access to the selected images as well as all content of the corresponding articles. This year, a set of 22 topics was released for evaluation of the retrieval systems, where each one is composed of a variable number of images and associated text in 4 languages. 3
Images in the collection belong to a medical article, so they can be indexed
using the surrounding text content. Our goal was to build a term-document
matrix using a vector space model with the Okapi-BM25 weighting scheme [
The text representation adopted in this work included information from the title of the paper and the image caption, which can be found in the XML le corresponding to each image in the data set. With that, a text corpus for the image collection was built, and standard text processing operations were applied, including tokenization, stemming, and stop-word removal. These operations determined the initial list of indexing terms.
We designed a prunning criterion to discard irrelevant terms from the initial list, thus, preserving only the most informative ones. A limit for the number of terms was established depending on their document frequency. If it is outside of a prede ned interval, the term is removed from the indexing list. The thresholds were computed according to a minimum and maximum number of documents in which a term is allowed to occur. The criterion is as follows: keep(t) = (true
if min < dft < max f alse otherwise where dft is the number of documents that contain the term t, and min and max are parameters that de ne the minimum and maximum number of documents in which the term should appear. The de nitive list of indexing terms is obtained by applying this rule, which is very useful to limit the dimensionality of the resulting vector space for indexing.
The term-document matrix is built using term frequencies in each document,
and Okapi-BM25 [
N dft 2 4
(k1 + 1) tft;d k1 (1 b) + b
Ld
Lavg
+ tft;d
3
5
where tft;d is the frequency of term t in document d, Ld and Lavg are the
length of document d and the average document length in the collection,
respectively, and, k1 and b are positive tuning parameters to calibrate the term
frequency scaling. We xed k1 = 1:5 and b = 0:75 according to the suggestions
presented by Manning et al. [
We submitted 2 textual runs using the indexing strategy described above, with the goal of evaluating the di erence in performance after pruning the list of indexing terms. In both cases, we set a minimum frequency of 20 documents in which a term should be present to keep it in the list. The rst experiment used 20,000 documents as maximum frequency, and the second experiment used 5,000 documents. These parameters resulted in vector spaces with approximately 28,000 and 18,000 dimensions, respectively.
An additional experiment was evaluated after the competition nished to assess the contribution of the pruning strategy with respect to a longer list of terms. This experiment used 50,000 documents as maximum frequency, and produced a list of 29,000 terms. Notice how the number of indexing terms is controlled by the use of these two parameters, which remove rare terms as well as too common terms. We used this property to control the dimensionality of the resulting term-document matrix for further analysis, as is described later in Section 5.
Table 1 reports performance measures for the three experiments, the two rst submitted to the o cial pooling and a third experiment run after the challenge. These results show the impact of the pruning strategy in the precision of the retrieval task, showing how the performance decreases by keeping or removing the wrong terms. The best response was obtained by the index limited by a frequency of 20,000 documents. This result ranked rst in the category of textual experiments, and is the second best performance overall in the poolings for adhoc image-based medical retrieval.
Our second submission used 18,633 indexing terms, resulting in a signi cant dimensionality reduction, but also an important reduction in performance. This di erence dropped the MAP performance in about 6%, leaving this experiment in the position number 14. However, notice that keeping more terms than those actually needed, can hurt the general retrieval precision even more. The additional experiment shows that a slight increase in the number of terms resulted in a decrease in performance of about 9%. 4
Our research group is currently leading an initiative to develop a framework for large scale image analysis for academic and scienti c applications. The framework, named BIGS[8], is implemented in the Java programming language and integrates a wide variety of image processing tools, including feature extraction and learning algorithms. One of the most remarkable characteristics of BIGS is that it can easily run in a distributed environment with heterogeneous computing resources, from laptop and desktop computers to high-performance servers.
Obtaining a good quality representation for image contents in large databases is a challenging task, and BIGS was used to tune up image indexes by conducting experiments on the ImageCLEFmed 2011 data set. The experiments were run on di erent servers scattered throughout our lab, using BIGS to process all images stored on an HBase NoSQL database1. In spite of the large size of the image collection, having an lightweight experimental lifecycle as provided by BIGS was key to be able to gain understanding on how to better tune up image indexes.
As a result, we designed two indexes for content-based image retrieval for
this year's data set, focusing on including spatial information in the
representation, since it can help to better discriminate medical image arrangements. The
Color and Edge Directivity Descriptor (CEDD) [
The CEDD descriptor is a compact representation of the image content, consisting in a histogram of 144 bins to codify information of colors and edges. The small size of this descriptor makes it an excellent choice for indexing large scale image collections. This descriptor has been previously evaluated in the context of medical image retrieval at ImageCLEF, exhibiting a competitive performance due to the variety of image modalities and visual con gurations in this data set.
We extended this representation by computing the CEDD descriptor in a
recursive partition of the image in quadrants, forming a pyramid of spatially
organized regions [
This descriptor was computed by the BIGS framework using 40 workers deployed in several computers at our lab. The total time required to index the full image collection of 305,000 images using this strategy was 37 minutes. Finally, the similarity between two images is calculated on this descriptor using the Tanimoto coe cient. Assuming that x and y are vector representations of the spatial pyramids for two images, this is computed as:
TD = t(x; y) =
xT y xT x + yT y xT y (3) 4.2
An image index using the bag-of-features representation [
For local features, we extracted blocks of 32 32 pixels on a regular grid and the CEDD descriptor is computed in these patches. The k-means algorithm is used to cluster a large sample of patches extracted from the collection, for building a dictionary of 5,000 visual terms. The histogram is constructed by counting the occurrence of dictionary words in each image. Besides the global counting of visual patterns, each image is also split in 3 horizontal, non-overlapping strips, and an additional histogram is computed there to estimate the spatial distribution of visual words. This results in four bag-of-features histograms that are bounded together in a single image descriptor with 20,000 features.
This representation was also computed using the BIGS framework with 40 workers deployed in several computers at our lab. The total time required to extract this representation for all images in the collection was 116 minutes, which is less than one hour and a half. The similarity measure computed for this representation is the histogram intersection, for two images with histograms x and y:
KHI (x; y) = n Xmin fxi; yig i=1 4.3
The topics proposed for this year's challenge included 22 di erent queries with multiple images, some of them with 6 or even 7 example images. Since a single ranking is required for queries with multiple image examples, a similarity integration rule was employed. The similarity score for a database image d with respect to a multi-image query q = fq1; q2; :::; qng, is obtained as follows: score(d; q) = n Xsimilarity(d; qk) k=1 (4) (5) 4.4
We submitted two runs, one using the spatial pyramid of CEDD features and another with the spatial bag-of-features. The results are reported in Table 2, and shows that the spatial pyramid obtains a signi cantly better performance than the bag-of-features, both in general precision (MAP) and early precision (P@10 and P@30). The di erence can also be observed in the positions obtained by these experiments in the general poolings, the spatial pyramid was ranked 3rd, whereas the bag-of-features was ranked 14th.
The spatial pyramid extension for the CEDD descriptor demonstrated to be an e ective representation to discriminate more relevant images in this task. In addition, computing the spatial pyramid did not result in an excessive load of both, computational e ort and representation length. This representation is still very light to compute with respect to the bag-of-features and keeps a compact descriptor with about 3,000 features.
In our preliminary experiments, we observed that adding a spatial layout on the image representation improves the performance of the medical image retrieval task. The two visual representations proposed in this work include spatial information using recursive computations of the same descriptor in partitions of the image. One of the reasons the spatial pyramid CEDD presented better performance than the bag-of-features is because of the level of granularity in the recursive partition, that allows to introduce more spatial details. This can be achieved because of the short length of the original CEDD descriptor, as opposed to the large dictionary of visual features that we employed in these experiments. One of our motivations to design textual and visual indexes for medical image collections is to develop a multimodal framework to integrate both modalities in a common representation. We focus our attention to the speci c case of enhancing visual search functionalities by introducing available text information into the visual index. Thus, the goal is to improve the retrieval response using multimodal information even when users search with example images only.
In this work, we employed a multimodal latent factors model proposed in [
P Hk2F + kT
QHk2F + kP k2F + kQk2F + kHk2F (6) where V 2 Rn ` is the matrix of n visual features for ` training examples, T 2 Rm ` is the matrix of textual information with m terms, P 2 Rn r is the transformation from the visual space to a multimodal space with r factors, Q 2 Rm r is the transformation from the textual space to the multimodal space, and H 2 Rr ` is the multimodal latent representation for the training images. is a regularization parameter for this learning problem.
The solution to this problem presented in [
QT Q 1 P T v (7) where h is the multimodal representation for an image with visual features v, and is a regularization parameter. The purpose of using these algorithms is to obtain a multimodal latent factor representations for all images, even if they do not have available text annotations, as may be the case of the queries. Using the multimodal representation, the ranking of images is computed using the dot product similarity measure, which indicates the extent to which two images share the same latent factors.
This strategy has demonstrated to be an e ective method to learn multimodal relationships from image collections with attached texts, resulting in a datadriven representation for images that incorporates both modalities. Previous studies have shown important performance gains for these approaches, since visual features are complemented by the semantics of text descriptions, providing an enhanced mechanism of representing images. 5.1
To construct a multimodal index for image search, we employed the matrices of text terms and visual features described in Sections 3 and 4, respectively. More speci cally, we used the term-document matrix with 18,000 terms weighted with Okapi-BM25, and the visual matrix with 3,024 spatial pyramid CEDD features. One of the reasons we were interested in designing textual and visual indexes with bounded dimensionality is to reduce the computational cost of learning multimodal relationships.
The online multimodal matrix factorization (OMMF) algorithm was trained with the full collection of images in this challenge, i.e., using the 305,000 images with their corresponding text annotations. An implementation of the algorithm in the Java programming language was employed, which decomposed the matrices of 18,000 rows for text data, and 3,024 rows for visual data, with 305,000 columns in both cases, in 131 minutes in average. This algorithm has been designed to learn from as many examples as possible in a short time.
To tune up the learning algorithm and determine appropriate parameters for the factorization, experiments were conducted with the ImageCLEFmed 2011 collection. We found good parameters to solve queries in the previous year's challenge, that included 600 multimodal latent factors and other regularization parameters as needed. The criteria to select parameters for this algorithm is to observe improvements with respect to the direct visual matching, i.e., with respect to the visual indexing methods presented in Section 4, since the queries used in this experiment are also based on example images only.
With the parameters that showed improvements in the 2011 collection, we prepared and submitted a run to the o cial poolings. Table 3 reports the results of this submission, as well as two other experiments for comparison. The rst experiment in the Table is our baseline method, based on direct matching of visual features. The second result is the performance of the prepared run that has shown a decrease in performance with respect to the baseline. This loss is mainly explained by the use of parameters tuned to improve the performance in the 2011 challenge.
There are several di erences between the challenge of 2011 and 2012. First, the nature of the proposed topics varied signi cantly, as this year's queries included more example images per topic, in average. Second, the size of the collection was increased, which resulted in bigger matrices in both dimensions. Third, this year's visual queries seem to be more di cult to answer, judging by the relative decrease in MAP observed in the results from 2011 to 2012. All these aspects may require a di erent con guration for the learning algorithm, in order to make it e ective to retrieve more relevant results.
The results reported in the third row of Table 3 present the performance measures for an additional experiment run o competition to estimate the potential of the OMMF algorithm to improve upon the baseline. This result was obtained by tuning the algorithm parameters more appropriately for this year's task, and shows an important relative improvement.
The main goal of a multimodal algorithm in this context is to extract meaningful relationships between visual features and text terms. An additional challenge that makes the multimodal indexing strategy di cult to setup correctly, is attributed to the properties of the textual modality, which is very noisy and unstructured. Extracting semantic information useful for image analysis in this condition is still a very interesting research problem that requires further analysis. 6
This paper presented the participation of the Bioingenium research group of Universidad Nacional de Colombia in the ad-hoc image-based medical retrieval task at ImageCLEF 2012. We submitted 5 runs: 2 textual and 3 visual, from which one was ranked rst in the text modality and another was ranked third in the visual modality. These results were obtained by incorporating simple and e ective extensions to well-known strategies for this task. We also explored multimodal indexing to answer visual queries, which is a very challenging and interesting research problem, that still requires further analysis. We believe that this is a promising research direction for improving image search systems, and the study of these models are the focus of our future research.
One of the main di culties of this year's challenge was the size of the database, which required e cient computational tools to process and index the collection. In this work, we supported all of our visual indexing experiments on a distributed computing framework for large scale image analysis, named BIGS [8]. This framework allowed us to accelerate the exploration of visual indexing strategies, and investigate new image representation designs, such as the spatial pyramid CEDD that ranked third among 36 other experiments. We also used online learning algorithms for extracting multimodal relationships e ciently by training with the full collection of medical images in short execution times.
This work was partially funded by the project Anotacion Automatica y Recuperacion por Contenido de Imagenes Radiologicas Usando Semantica Latente, number 110152128803 and project Sistema para la Recuperacion de Imagenes Medicas Utilizando Indexacion Multimodal, number 110152128767 by Convocatoria Colciencias 521 de 2010. 8. Raul Ramos-Pollan, Fabio A. Gonzalez, Juan C. Caicedo, Angel Cruz-Roa, Jorge E.
Camargo, Jorge A. Vanegas, John E Arevalo, Paola K Rozo, Santiago A Perez, Jose D Bermeo, and Juan S Otalora. BIGS: A framework for large-scale image processing and analysis over distributed and heterogeneous computing resources. In IEEE International Conference on eScience. To appear, 2012.