This document describes the participation to ImageCLEF 2006 photographic retrieval task of the IPAL lab (Singaporean French collaboration) hosted at Institute for Infocomm Research, Singapore. This paper provides a description of the way results has been produced. The text/image database used is IAPR [1]. We have tested a cooperative use of a text retrieval and an image retrieval engine. We show in particular how inter-media re-ranking and pseudo-relevance feedback have been used for producing the results. We have also tested Latent Semantic Analysis (LSA) approach on visual runs. WordNet thesaurus has been used for pre-processing textual annotations within spell checking corrections. Our approach is completely automatic. A description of the runs submitted to the competition is also given.
One of the most interesting issues in multimedia information retrieval is to use di®erent modalities (e.g. text, image) in a cooperative way.
In this experiment, our goal is to study inter-media pseudo-relevance feedback (between text and image) and so to explore how the output of an image retrieval system can be used for expanding textual queries. This is motivated by the hypothesis that two images with a very strong visual similarity should share some common semantics.
We are also interested in studying how appearance-based re-ranking techniques can be used to enhance the output of a text retrieval system. This is motivated by the fact that high-level concepts have most of the time a large variety of visual appearances. In some cases, it can be useful for the end-user to obtain images of a concept which have a well-de¯ned appearance.
This document is structured as follows. Section 2 gives a description of the system used to produce results submitted by IPAL at ImageCLEF 2006 Photo task. Section 3 provides a description of the most important runs submitted. Section 4 provides an analysis of the results. 2 2.1
Our results have been produced by the cooperative use of a image indexing and retrieval system and a text indexing and retrieval system. An overview of the complete retrieval system can be found in ¯g. 4. The system developed contains pseudo-relevance feedback and re-ranking capabilities. 2.2
Our goal on the text runs is to experiment a mixture of knowledge and statistical
information to solve very precise short query. Knowledge comes from WordNet
[
Text indexing and retrieval were mainly achieved by the XIOTA system
[
Morpho-Syntax Texts have ¯rst been preprocessed in order to recognize part of speech and to correct spelling. The following steps have been followed in sequence: { XML correction: As XIOTA relies on a correct XML data °ow, an automatic
XML correction is applied for correcting some closing tags.
{ Part of Speech: Files are then passed through a part of speech tagger
(TreeTagger1 [
Spanish). { Spelling corrections: we make the assumption that every terms not tagged as a proper noun and unknown is misspelled (about 700 terms, ex: "buidings", "toursits"). This is false for some terms not recognized by the POS tagger because they are joint like "belltower", "blowtube"."snowcover", or because of the hyphen like "winter-jaket", "cloud-imposed". This list of unknown words is passed through aspell2 to associate a possible correct form. When aspell proposes several choices, the ¯rst one is selected.
We think that the spelling correction is important to ensure correct index in the case of short documents. Possible misspellings are detected thanks to the part of speech step. Queries are processed in the same way. All other processing including text indexing, start from the analyzed and corrected text collection. Namely, the basic vector space indexing performs only a POS ¯ltering before building vector indexes.
Noun Phrase We have used WordNet to detect noun phase. Candidates were selected using POS template: { noun (singular) + noun (singular) (e.g. "baseball cap") { noun (singular) + noun (plural) (e.g. "tennis players") { proper noun + proper noun (e.g. "South America") { verb VG + noun (e.g. "swimming pool")
If the two following conditions hold: the template and the presence in WordNet, we replace the word couple by one term with the correct stemmed version. It means that the two terms will be treated as only one indexing term. We have not used cooccurrence statistics because the corpus is too small.
Named Entity In this tourist image set, the location of the scene in the picture is important. That is why we have decided to detect geographic Named Entity. We have used two information sources: WordNet and the corpus itself. In fact, we have extracted information from the LOCATION tag to build a list of geographic names. Then we have tagged the rest of the corpus using ¯rst WordNet and then this list. Filtering is based on the proper noun POS, and on the lexical WordNet category "noun.location". If the location is not found in WordNet, then the location list is used. We have used this information to split the query and force the geographic information matching.
Concept Concept indexing seems a nice way to solve the term mismatch because all term variations is replace by one unique concept. Unfortunately the problem remains in the concept detection, because it need a disambiguation step. For this experiment, we have used the WordNet sense frequency when available. This information provides a sort of statistic on the more frequent sense of a term. Otherwise we have ¯ltered the most frequent semantic category (lexname), and choose the most frequent one. This choice is correct most of the time for this corpus. This step produces a new corpus with WordNet concept references that enables conceptual indexing and retrieval. 2.3
Feature Extraction. The feature extraction process is based on a tessellation of the images of the database. Each image is split into patches (¯g. 1). The visual indexing process is based on patch extraction on all the images of the collection followed by feature extraction on the resulting patches. Let I be the set of the N images in the document collection. First, each image i 2 I is split into np patches pik (1 · k · np). Patch extraction on the whole collection results in np £ N patches. Fig. 1 shows the result of patch extraction for one image.
The low-level features extracted on patches are the following:
{ Texture features used by our system are Gabor features [
We also de¯ne a similarity measure based on regions obtained by image
segmentation [
For a region rik, the numerical feature vector extracted from rik is noted fe(rik) 2 Rn. Additional low-level features extracted on regions are their size and the position of their centroids. This implies that in this case, n = 60+128+1+2.
We have also used Local Features to characterize ¯ne details. Note that
in this case, patches are not considered. We use bags of Sift3 [
Similarity Function. The visual similarity between two images i and j, ±I (i; j), is de¯ned as following: ±I (i; j) = ® £
Pkn=p1 L2(fe(pik); fe(pjk)) np + ¯ £ bi ¢ bj + °dR(i; j) jbijjbjj
In our experiments ® = 0:4, ¯ = 0:4, and ° = 0:2.
2.4
User Feedback is a basic way to solve the classic IR term mismatch problem
between query and documents. User relevance is used to select relevant top
retrieved document which indexing terms are injected into the initial query. This
query expansion can be done automatically assuming that the k top ranked
documents are relevant: this is called "pseudo-relevance feedback". Pseudo-relevance
feedback has been tested for example in [
We are concerned about mixed mode queries (text + image) and interested
in solving this queries using the two modalities. Other works like [
Our approach is to query both modality in parallel and to apply pseudorelevance feedback from one modality to the other. For example, the result of the image ranking drives text query expansion through documents. This information is then used to expand the textual query. We call this Inter-Media PseudoRelevance Feedback. As the queries contain both image and text, querying can be initiated whether by the text modality or by the image modality. Figure 3 illustrates this principle for text query expansion based on the image modality.
Query Text
Image
Retrieved
Documents Image
Text
In this case, retrieval is achieved in 3 main steps. (1) The initial query is used as an input of the image retrieval engine. The text contained in the query is not involved in the image retrieval process. (2) The textual annotations associated with the top k documents retrieved by the image retrieval engine are then used for query expansion purposes. (3) After this expansion, the resulting text query is processed by the text retrieval engine to produce the ¯nal set of ranked documents. In our experiments, we have set k = 3. 2.5
We have also integrated re-ranking mechanisms based on the visual appearance (see ¯g. 4) with the same hypothesis: the top k documents retrieved by text retrieval are relevant. The the k associated relevant images are used to form a class of images which hopefully corresponds to the concept represented by the query.
The goal of re-ranking is to change the rank of the images which are visually similar to the images retrieved by text retrieval. Re-ranking is used as a postprocessing step (4) of the pseudo-relevance feedback described in section 2.4.
Query Text Image
Retrieved
Documents Image
Text Image Retrieval Engine 1 2
Text
Query Expansion Indexed
Documents Image
Text
Expanded
Query Text
Text Retrieval Engine 3
Appeance
Based Re-Ranking 4
Ranked Documents Both image and text retrieval systems are implemented in C++. For text, basic IR function are part of XIOTA system, dedicated scripts are written in Perl or shell scripts. The image retrieval system heavily relies on the LTI-LIB4 computer vision library which includes image processing algorithms (e.g. feature extraction, segmentation), machine learning algorithms, and matrix algebra functionalities. This library has a very clean object-oriented design and is very well documented.
P stands for Part of Speech and W for Single word. Text are ¯rst processed as explained in section 2.2. Term ¯ltering is done on part-of-speech. Only nouns, proper nouns, abbreviations, adjectives and verbs are kept. Stemming is provided by the POS tagger. For this run, only the document ¯elds TITLE, DESCRIPTION and LOCATION are used. The weighting is the tf.idf, and ranking is computed with the cosine distance. This run results from the use of the pseudo-relevance feedback described in section 2.4. PFB3 stands for pseudo-relevance feedback involving the three top images retrieved by image retrieval. It is an extra step of the text indexing run IPAL-PW. The textual annotations associated with three images are used for expansion of the text query. It is important to note that the query is expanded from the document index with tf weighting. The query weighting is performed after the merge (pseudo feedback). Then it is equivalent to a merge of the original text from the document into the query text. If we consider the use of short query implies being under the Information Retrieval (IR) "subsumption matching" paradigm where relevant document is supposed to imply the query; building a query by merging document is closer to the IR "similarly matching" paradigm, where a relevant document is supposed to be closed to the query. It is also important to note that Image Retrieval Systems are quite always under the "similarly matching" paradigm.
The re-ranking process described in section 2.5 has been used to produce these runs. Re-ranking was applied on the 60, resp. 300 top images in the documents retrieved by the text retrieval engine for run IPAL-PW-FB3-RR60, resp. IPALPW-FB3-RR300. Re-ranking is not applied on the whole set of retrieved images. The reason for that is that images which have a low ranking, share little semantics with query. Even if they are visually similar to the query, they should not be assigned a high rank. WN stands for Indexing using WordNet concepts. Concepts are extracted from WordNet and used to expand documents and queries. Concepts and original terms are kept in the vector because of the low reliability of concept disambiguation. Hence we have not tested a real full conceptual indexing. Before query re-weighting, a classic tf.idf weighting scheme is applied to all documents and queries. Query is then split on noun and proper noun. Weighting is then linearly rescaled to maximum 1 on these sub queries. This enables to emphasis the maximum terms in the answer as every term has the same weighting scale. As a consequence, weighting scheme is no more exact tf.idf. Nevertheless, we still use the cosine distance for ranking. Geographical Named Entities are also localized and solved apart in sub queries in the same way. Finally, top documents are those who equally match nouns with concepts, proper nouns and geographical named entities. 3.5
This run results from a late fusion (by a weighted-sum) of the output of the text retrieval engine and the output of the image retrieval engine. MF stands for mixed features (described in section 2.3). The principle of late fusion is depicted in ¯g. 5.
Query Image Text EI stands for Equal Importance of all Nouns and Proper Nouns and Noun Phrase. Noun Phrases are computed using WordNet. This run tests the importance of Noun Phrase against other nouns. As tree-tagger does not recognize composed nouns (Noun Phrase), WordNet is used to detect composed nouns with only two nouns (e.g. tennis player, baseball cap, swimming pool) (see 2.2). Each name and proper noun produces a sub query which weight is normalized to 1 in the same way as IPAL-WN. Then sub query results are merged. Then, top documents are those who equally match nouns, proper nouns and noun phrases. 3.7
This run results from Latent Semantic Analysis (LSA) [
Indexing is performed as following: 1. Each image is split in 16 non-overlapping patches. 2. From each patch, RGBL histogram (128 bins = 32 * 4) and edge histogram features are extracted. 3. Patches are clustered using k-means clustering algorithm (k=4000). The cluster centroids are also computed. 4. Term-document matrix is computed A = (aij ) with i = 1; m and j = 1; n , where aij is the number of patches of image j belonging to cluster i. tf-idf is computed from this term-document matrix. In our case, the size of the term-document matrix is 4000 £ 20000. 5. Singular Value Decomposition is applied to the term-document matrix A = U SV t. Image coordinates matrix SV t and a transformation matrix U t are obtained.
Retrieval is achieved as following: 1. Images in the query are split in 16 non-overlapping patches. 2. From each patch, RGBL histogram (128 bins = 32 * 4) and edge histogram features are extracted. 3. Distance to closest clusters centroids are computed and each patch of each image in the query is assigned to the corresponding cluster. The query (Q) has the same form as a column in the term-document matrix. Tf-Idf is performed on Q. 4. The query is projected into latent semantic space by multiplication with the transformation matrix U t, Qproj = U tQ. 5. Distance between the query (Qproj ) and all images in the database (columns of SV t ) is computed and the images are ranked. 3.8
This run was produced by the use of features described in section 2.3. The similarity distance used between two images i and j is ±I (i; j). 4
Mean Average Prevision resulting from each run is summarized in table 1.
IPAL-PW-PFB3 has produced our best Mean Average Precision. In this case, textual information extracted from the 3 top images retrieved by the image retrieval engine are used for text query expansion.
One unexpected result is the degradation of the results (compared to IPALPW-PFB3) when applying the appearance based re-ranking algorithm. As expected, mean average precision is lower for the run IPAL-PW-PFB3-RR300 than for the run IPAL-PW-PFB3-RR60. The di®erence between the two runs is of 7:9%. Run IPAL-PW-PFB3-RR300 shows that when the number of images considered by re-ranking increases, MAP decreases.
For textual run only, the use of WordNet concepts decrease the MAP. We have not used any of the semantic links provided by WordNet (like hypernym between "bird" and "animal") and we have notice some problem in sense disambiguation (like "church" not recognized as a building). This may explain the lake of improvement. The role of noun phrases seems also not really crucial as IPAL-EI is lower than single terms indexing IPAL-PW. Giving equal importance to single and composed terms is hence a bad idea.
For visual only runs, Latent Semantic Analysis (LSA) leads to slightly better results compared to retrieval based on visual similarity in the feature space. However, mean average precision for visual runs remains very low. Precision at 10 documents (P10) is 0.1417 for run IPAL-LSA and 0.1050 for run IPAL-MF. Precision at 20 documents (P20) is 0.1075 for run IPAL-LSA and 0.0883 for run IPAL-MF. 5
Our approach to this year competition was based on a cooperative approach between an image retrieval and a text retrieval system. These experiments show that the combined use of a text retrieval and an image retrieval systems leads to better performance but only for inter media pseudo relevance feedback and not for late fusion. One surprising aspect of these results is that re-ranking based on visual appearance reduces mean average precision.
The IAPR image database is challenging. Many concepts are represented with a large variety of appearances. Query by content using a few images cannot lead to satisfactory results by using only appearance-based techniques. Indeed, a few samples a given concept cannot capture its conceptual essence.
MAP remains low and is probably still too low to be used in practical conditions. A lot of work has to be done to improve the quality of the system. We believe that machine learning techniques should be used to obtain an conceptual abstraction of the query images. In this case, the issue is to train the concept detectors. Providing manually a su±cient number of image samples is extremely tedious and does not really scale-up to a large number of concepts. We believe that textual annotations could help building training sets easily and to help raising low-level image features at a semantic level. One of our short-term goals is to apply Latent Semantic Analysis on both image and text modalities. In this case, the size of the resulting term-document matrix is potentially huge and technical problems related to memory management will be encountered. We plan to integrate advanced image interpretation techniques based on prior knowledge on categories of scenes of interest (e.g. indoor, outdoor). We are also interested in adding semi-automatic and ontology-driven feedback and re-ranking.