Abstract

Our approach to the ImageCLEF 2009 tasks is based on image segmentation, SIFT keypoints and Okapi BM25 based text retrieval. We use feature vectors to describe the visual content of an image segment, a keypoint or the entire image. The features include color histograms, a shape descriptor as well as a 2D Fourier transform of a segment and an orientation histogram of detected keypoints. We trained a Gaussian Mixture Model (GMM) to cluster the feature vectors extracted from the image segments and keypoints independently. The normalized Fisher gradient vector computed from GMM of SIFT descriptors is a well known technique to represent an image with only one vector. Novel to our method is the combination of Fisher vectors for keypoints with those of the image segments to improve classification accuracy. We introduced training and correlation based combining methods to further improve classification quality.

-

the segments. We use the Hungarian Academy of Sciences search engine [ 2 ] as our information retrieval system that is based on Okapi BM25 [ 16 ] and query expansion by thesaurus. 2

Image processing

We transform images into a feature space both in order to define their similarity for ad hoc

retrieval and to apply classifiers over them for annotation. For image processing we deploy both

SIFT keypoints [8] and image segmentation [5, 14, 4, 9]. While SIFT is a standard procedure, we describe our home developed segmenter in more detail below.

2.1

Segmentation

Our segmentation algorithm is based on a graph of the image pixels where the eight neighbors

of a pixel are connected by edges. The weight of an edge is equal to the Euclidean distance of the pixels in the RGB space. We proceed in the order of increasing edge weight as in a minimum spanning tree algorithm except that we do not merge segments if their size and the similarity of their boundary edges are above a threshold. In the algorithm we use the notation

B(S1, S2) = average weight of edges connecting S1 and S2.

The algorithm consists of several iterations of the above minimum spanning tree type procedure. In

the first iteration we join sturdily coherent pixels into segments. In further iterations we gradually increase the limits in order to enlarge segments and reach a required number of them.

The algorithm is called with three parameters τ1, τ2 and τ3 where the first is initialized to be the difference of the minimal and maximal edge weight in the graph while the other two are chosen to have values 40 and 50, respectively.

Algorithm 1 Algorithm Segmentation(Isrc, τ1, τ2, τ3). for all pixels p do define segment Sp = {p} τ (Sp) ← τ1 {Joining sturdily coherent pixels} for all neighboring pixel pairs (p, q) in the order of edge weight do if Sp 6= Sq and min{τ (Sp), τ (Sq)} > B(Sp, Sq) then

Sp ← Sp ∪ Sq τ (Sp) ← τ (Sp) ∗ ||SSpp|| ++ |τS(qS|q) ∗ |Sq| + B(Sp, Sq) {Segment enlargement} while we reach the prescribed number of segments do for all neighboring pixel pairs (p, q) in the order of edge weight do if Sp 6= Sq and min(|Sp|, |Sq|) < τ2 and B(Sp, Sq) < τ3 then

Sp ← Sp ∪ Sq τ2 ← τ2 ∗ 1.2 and τ3 = τ3 ∗ 1.3 2.2

Feature extraction

We performed colour, shape, orientation and texture feature extraction over the segments and

environment of keypoints of images. This resulted in approximately 0.5 − 7 thousand keypoint descriptors in 128 dimensions and in approximately 0.2 thousand segment descriptors in 350 dimensions. The following features were extracted for each segment: mean RGB histogram; mean

HSV histogram; normalized RGB histogram; normalized HSV histogram; normalized contrast

histogram; shape moments (up to 3rd order); DFT phase and amplitude. 2.3

Image Similarity

For ad hoc image retrieval we considered segmentation based image similarity only. We extracted features for color histogram, shape and texture information for every segment. In addition we used contrast and 2D Fourier coefficients. The discrete Fourier transformation was sampled along a zig-zag order, i.e. the low frequency components were included. An asymmetric distance function is defined in the above feature space as d(Di, Dj) = X min dist(Sik, Sjℓ)

k ℓ where {Sdt : t ≥ 1} denotes the set of segments of image Dd. Finally image similarity rank was obtained by substracting the above distance from a sufficiently large constant. 3

The base text search engine

We use the Hungarian Academy of Sciences search engine [2] as our information retrieval system

based on Okapi BM25 ranking [ 16 ] with the proximity of query terms taken into account [ 15, 3 ].

We deployed stopword removal and stemming by the Porter stemmer. We extended of stop word list with terms such as “photo” or “image” that are frequently used in annotations but does not have a distinctive meaning in this task.

We applied query term weighting to distinguish definite and rough query terms, the latter may

be obtained from the topic description or a thesaurus. We multiplied the BM25 score of each query term by its weight; the sum of the scores gave the final rank.

We used a linear combination of the text based and image similarity based scores for ad hoc retrieval. We considered the text based score more accurate used small weight for the content based score.

4

The WikipediaMM Task

We preprocessed the annotation text by regular expressions to remove author and copyright in

formation. We made no differentiation between the title and the body of the annotation.

Since file names often contain relevant keywords and also often as substring, we gave score proportional to the length of the matching substring. Since the indexing of all substrings is infeasible, we only performed this step for those documents that already matched at least one query term in their body.

For the WikipediaMM task we also deployed query expansion by an online thesaurus1. We added groups of synonyms with reduces weight so that only the score of the first few best performing synonym was added to the final score to avoid overscoring long lists of synonyms.

As seen in Table 1, our CBIR score improved performance in terms of MAP for the price of

worse early precision. In this experiment expansion by thesaurus did not help.

Text CT

Text

Image+Text CT

Image

We preprocessed the annotation text by regular expressions to remove photographer and agency

information. This step was in particular important to get rid of the false positives for Belgiumrelated queries as the majority of the images has the Belga News Agency as annotated source.

Since the annotation was very noisy, we could only approximately cleanse the corpus.

As the main difference from the WikimediaMM task, since almost all queries were related to

names of people or places, we did not deploy the thesaurus. Some of the topics had description (denoted by CT in the topic set as well as in Table 2) that we added with weight 0.1.

We modified our method to achieve greater diversity within the top 20. For each topic in the

ImageCLEF Photo set, relevant images were manually clustered into sub-topics. Evaluation was based on two measures: precision at 20 and cluster recall at rank 20, the percentage of different clusters represented in the top 20.

The topics of this task were of two different types and we processed them separately in order

to optimize for cluster recall. The first set of topics included subtopics; we merged the hit lists of the subtopics by one by one. The last subtopic typically contained terms from other subtopics negated; we fed the query with negation into the retrieval engine.

The other class of topics had no subtopics; here we proceeded as follows. Let Orig(i) be the ith

document (0 ≤ i < 999) and OrigSc(i) be the score of this element on the original list for a given query Qj . We modified these scores by giving penalties to the scores of the documents based on their Kullback-Leibler distance. We used the following algorithm.

Algorithm 2 Algorithm Re-ranking

1. New (0) = Orig(0) and NewSc(0) = OrigSc(0) 2. For i = 1 to 20 (a) New(i) = argmaxk{CLi(k) |i <= k < 999} (b) NewSc(i) = max{CLi(k) |i <= k < 999} (c) For ℓ = 0 to (i − 1)

NewSc(ℓ) = NewSc(ℓ) + c(i)

i−1

Here CLi(k) = OrigSc(k) + α Pl=0 KL(i, k), where α is a tunable parameter and KL(i, k) is the Kullback-Leibler distance of the ith and kth documents. We used a correction term c(i) at

Step (2c) to ensure that the new scores will be also in descending order.

6

The Photo Annotation Task

The Photo Annotation data consisted of 5000 annotated training and 13000 test images. Our

overall procedure is shown in Fig. 1. We used the bag-of-visual words (BOV) generative approach in combination with the Fisher kernels method for images [ 13, 1 ]. As a first step we extracted low level features from each image. These features include the SIFT key points and the color image segment descriptors such as shape, color histogram as described in Section 2.2.

We produced a global visual vocabulary that approximate the per-image distribution of the low level features by clustering with a 64 dimensional GMM. First we obtained a variable number of visual words per image that we processed by Fisher kernels. The resulting kernel from different feature combinations were used as training input for a binary linear classifier (L2 logistic regression). We used a held-out set to rank each row from the Fisher kernel. After computing the results for all of the 53 concepts, a matrix of dimensionality N × 53 holds the concept detection results, where N is the number of images.

The concept detection results from different kernels can be combined. We followed two approaches. The first one described in Section 6.2 exploits the connection between the concepts of the training annotation while the second one (Section 6.3) applies another round of training to learn the best combination of the individual concept detectors.

6.1

Feature generation and modeling

To reduce the size of the feature vectors we modeled them with 64 Gaussians. The classical

EM algorithm with diagonal covariance matrix assumption was used for the computation of the mixture parameters. To get fixed sized image descriptors we computed g −1+g ×D×2 dimensional normalized Fisher vectors per images [13, 1], where D = 128 is the dimension of the low level feature vectors. The t × t Fisher kernel matrix contained the L1 distances of all training images

42

Sea 46

Water Beach_Holidays 40 Plants

Trees −32 Outdoor

31 Sunset_Sunrise 36

No_Visual_Time 33 67 Clouds 32

−37 45 Day 35 Sky

No_Visual_Place 63 −31

−86 33 −41

−70 Winter

69 Snow from themselves. There are t = 5000 training images. We computed the Fisher kernels for several low level feature type combinations. Such combinations were: SIFT+image segments,

SIFT+global image features, etc. We used the resulting Fisher kernels for training binary linear classifiers (L2-regularized logistic regression classifier from the LibLinear package [7]) for each of the k = 53 concepts. For prediction we used the s × t kernel matrix with the trained linear classifiers, where s = 13000 denotes the number of test images.

6.2

Correlation based combination

From the annotations of the training images we computed the auto-correlation matrix (Fig. 2).

Using this matrix we exploited the common knowledge of annotations about the relationship between the concepts. With this matrix we reweighted the output of the predictors. Let us denote A the t × k annotation matrix. Each entry of A is either 0 or 1. Moreover, let C = [cij ] be the k × k symmetric correlation matrix where cij = corr (ai, aj ), ai is the ith column of A, corr (x, y) = cov (x, y) / (std (x) · std (y)) is the normalized correlation coefficient. Let P denote the t × k matrix composed from the outputs of the predictors. Rows correspond to images, while columns correspond to concepts. The combined prediction is computed

PC = P C

The improvement is shown in Table 3.

6.3

Log-odds based combination

Our combination of the classifiers is inspired by the log-odds averaging by Lynam and Cormack

[ 10 ]. We first made a 10-fold crossvalidation on the training data to score every image by every classifier. Then for every classifier we calculated the log-odds as a feature by taking the logarithm of the fraction of the number of positive images with lower score over the number of negative images with higher score. Finally, we trained a logit-boost classifier over this feature set. The predictors were trained with the following feature sets: segmentation and SIFT (two fine tuned runs); global features only; SIFT only; segmentation only; global and SIFT features; global features and segmentation. 7

Conclusion

• For image classification, we successfully combined a pure keypoint based and a region based method, two image processing algorithms that complement each other. Further improvement could be to include the hierarchical relationship of the concepts into the combination procedure that would result in a directed graph to describe ConceptA → ConceptB relation

Segmentation

SIFT

SIFT + Segmentation

SIFT + Segmentation + Cross

Log Odds combination

• For image retrieval our content based score improved the text score in combination. The use of the thesaurus and other query expansion techniques needs further analysis and refinement. • We took minimal effort for optimizing for diversity; while our results were strong in MAP, optimization with stronger parameters could have helped.

References

[1] J. Ah-Pine , C. Cifarelli , S. Clinchant , G. Csurka, and J.M. Renders . XRCE's Participation to ImageCLEF 2008 . In Working Notes of the 2008 CLEF Workshop , 2008 .

[2] Andr´as A . Benczu´r, Ka´roly Csaloga´ny, Eszter Friedman, D´aniel Fogaras, Tam´as Sarlo´s, M´at´e Uher, and Eszter Windhager . Searching a small national domain-preliminary report . In Proceedings of the 12th World Wide Web Conference (WWW) , 2003 .

[3] Stefan Bu ¨ttcher, Charles L. A. Clarke , and Brad Lushman . Term proximity scoring for ad-hoc retrieval on very large text collections . In SIGIR '06 , pages 621 - 622 , New York, NY, USA, 2006 . ACM Press.

[4] Chad Carson , Serge Belongie, Hayit Greenspan, and Jitendra Malik . Blobworld: Image segmentation using expectation-maximization and its application to image querying . IEEE Trans. Pattern Anal. Mach . Intell., 24 ( 8 ): 1026 - 1038 , 2002 .

[5] Yixin Chen and James Z. Wang . Image categorization by learning and reasoning with regions . J. Mach. Learn. Res. , 5 : 913 - 939 , 2004 .

[6] Ba ´lint Daro´czy, Zsolt Fekete, M´atya´s Brendel, Simon R´acz, Andr´as Benczu´r, D´avid Sikl´osi, and Attila Pereszl´enyi. Cross-modal image retrieval with parameter tuning . In Carol Peters, Danilo Giampiccol, Nicola Ferro, Vivien Petras, Julio Gonzalo, Anselmo Pen˜as, Thomas Deselaers, Thomas Mandl, Gareth Jones, and Nikko Kurimo, editors, Evaluating Systems for Multilingual and Multimodal Information Access - 9th Workshop of the Cross-Language Evaluation Forum, Lecture Notes in Computer Science , Aarhus, Denmark, September 2008 (printed in 2009 ).

[7] R.E. Fan , K.W. Chang , C.J. Hsieh , X.R. Wang , and C.J. Lin . LIBLINEAR: A library for large linear classication . The Journal of Machine Learning Research , 9 : 1871 - 1874 , 2008 .

[8] D.G. Lowe. Object recognition from local scale-invariant features . In International Conference on Computer Vision , volume 2 , pages 1150 - 1157 . Corfu, Greece, 1999 .

[9] Qin Lv , Moses Charikar, and Kai Li . Image similarity search with compact data structures . In CIKM '04: Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management , pages 208 - 217 , New York, NY, USA, 2004 . ACM Press.

[10] T.R. Lynam , G.V. Cormack , and D.R. Cheriton . On-line spam filter fusion . Proc. of the 29th international ACM SIGIR conference on Research and development in information retrieval , pages 123 - 130 , 2006 .

[11] Stefanie Nowak and Peter Dunker . Overview of the CLEF 2009 large scale visual concept detection and annotation task . In Working Notes for the CLEF 2009 Workshop , 2009 .

[12] M Paramita , M Sanderson , and P Clough . Diversity in photo retrieval: overview of the ImageCLEFPhoto task 2009 . In Working Notes for the CLEF 2009 Workshop , 2009 .

[13] F. Perronnin and C. Dance . Fisher kernels on visual vocabularies for image categorization . In IEEE Conference on Computer Vision and Pattern Recognition , 2007 . CVPR' 07 , pages 1 - 8 , 2007 .

[14] B. G. Prasad , K. K. Biswas , and S. K. Gupta . Region-based image retrieval using integrated color, shape, and location index . Comput. Vis. Image Underst ., 94 ( 1-3 ): 193 - 233 , 2004 .

[15] Yves Rasolofo and Jacques Savoy . Term proximity scoring for keyword-based retrieval systems . In ECIR , pages 207 - 218 , 2003 .

[16] Stephen E. Robertson and Karen Sparck Jones. Relevance weighting of search terms . In Document retrieval systems , pages 143 - 160 . Taylor Graham Publishing, London, UK, UK, 1988 .

[17] Theodora Tsikrika and Jana Kludas . Overview of the WikipediaMM task at ImageCLEF 2009 . In Working Notes for the CLEF 2009 Workshop , 2009 .