We describe our approach to the ImageCLEF-Photo 2007 task. The novelty of our method consists of biclustering image segments and annotation words. Given the query words, we may select the image segment clusters that have strongest cooccurrence with the corresponding word clusters. These image segment clusters act as the selected segments relevant to a query. We rank text hits by our own tf.idf based information retrieval system and image similarities by using a 20-dimensional vector describing the visual content of image segments. Here relevant image segments were selected by the biclustering procedure. Images were segmented by a home developed segmenter. We used neither query expansion nor relevance feedback; queries were generated automatically from the title and the 0.1 weighted description words.
In this paper we describe our approach to the ImageCLEF Photo 2007 evaluation campaign [
Our CBIR method is based on segmentation of the image and on the comparison of features of the segments. The biclustering algorithm is used to lter relevant segments.
We use the Hungarian Academy of Sciences search engine [
Many of the existing CBIR systems rely on so called blobs, regions, or segments, see [
Biclustering is used in a wide variety of applications. For example documents-words clustering
[
We use the Hungarian Academy of Sciences search engine [
We created small HTML-like documents from the textual information of the images. These contain the title, description and the location part of the annotations. The ranking algorithm uses dierent weights depending on which part of the document contains the query term. As in the original HTML search engine we removed the stop words from the documents. We used a wider range of stop words than usually because words like "photo" and "image" are frequently used in annotations but does not have distinctive meaning in this task.
The queries which were submitted to the search engine were constructed from the the title and narrative parts of topics. We removed the stop words described above rst and sentences containing the phrase "not relevant" were also removed from the narrative. The resulting query is the concatenation of the remaining words of the title and the narrative parts. The words from the narrative part are marked, as the ranking algorithm uses dierent weights for the title and narrative query word hits.
The relevance score is computed by the weighted combination of the following:
• tf.idf based ranking which takes the proximity of query terms into account[
This ranking method had several parameters: weights of the tf.idf score and the number of query words, weights of the title, description and location hits and the weight of the title and narrative query terms. After several runs with dierent set-ups, we found that we get the bestlooking result if the weight of the number of query terms is much higher than the tf.idf score. In other words we rank the documents with respect to the number of query terms, then use the tf.idf score to rank those documents that have the same number of query terms.
Since many topics have location reference, we get the best results if the weight of hits inside the location is much higher than the weights of title and the description. The query terms from the topic title have ten times higher weight than the narrative terms. 3
The task of the CBIR part was to help annotation based retrieval with a content based method.
Query images had to be classied into query topics. For each topics 3 sample images were given.
For each query image we had to compute a distance, which measures how similar the query image
is to the 3 sample images in the topic. Segment, region or blob based image similarity is a common
method in content based image retrieval, see for example [
dist(Si, Sj ) = d(F (Si), F (Sj )) : Si ∈ S(Q), Sj ∈ S(I) (1) where S(q) is the set of segments of the query image Q, and S(I) is the set of segments of the sample image I, dist is the distance function of the segments, d is a distance function in the feature space (usually some of the conventional metrics in the n-dimensional real space), F is the function, which assigns features to objects and segments. We extracted features, like mean color, size, shape information, and histogram information. Our histograms had 5 bins in each channel. Altogether a 20-dimensional, real valued feature-vector was extracted for each of the segments. The same features were extracted for the segments of the sample-images. The features of the segments were written to a le. This way we obtained a data-base of the topic-samples, containing features of segments. 3.1
Most of the traditional digital image segmentation methods were based on the fact that we have no further information aside the position of pixels and their color. Fifteen or less regions are usual considered enough for processing with a Content Based Image Retrieval(CBIR) system properly.
In computer graphics we use many color representations. The most common color space is RGB. Because the equivalence of components in this three dimensional space we can use the Euclidean distance to measure the similarity of pixels P1 and P2: dif f RGB(P1, P2) = p(RP2 − RP1 )2 + (GP2 − GP1 )2 + (BP2 − BP1 )2 (2) We know that the human visual system (HVS) is more sensitive to the brightness of pixels than to the additional color. According to this we can use a dierent distance: dif f Y (P1, P2) = 0.3∗ | RP2 − RP1 | +0.59∗ | GP2 − GP1 | +0.11∗ | BP2 − BP1 | (3)
The basic idea is that we transform the image into a graph. Let G = (V, E) be an undirected graph where ∀vi ∈ V corresponds to a pixel in the image, and the edges in E connect certain pairs of neighboring pixels. The early graph-based representations contained only edges between neighboring pixels, recent works dene a full graph with a more complex distance function. This graph-based representation of the image reduces the original proposition into a graph cutting challenge.
The adequate cut is the normalized cut (Ncut developed by Shi and Malik[
With our restrictions, the graph-based algorithms are not the only option. One of the wellknown methods is pyramid-based image segmentation. Using the Gaussian-Laplacian pyramid we can dene a connection between pixels on neighboring levels and inside a level. Generally the pyramid-based segmentation methods use six or more levels with typically small thresholds. Pyramid-based algorithms have advantages over graph-based methods, such as computation time, but they oer subjectively worse quality - they suer from the so-called blocking problem, and perform badly with complicated picture regions.
When we decided to develop our own segmentation method we wanted to achieve a relatively
low running time, and to preserve a quality comparable to the graph-based algorithms used as
reference. To improve the eciency of our implementation we used some functions from the OpenCV
library (www.intel.com/technology/computing/opencv/) for resizing, smoothing the image and to
calculate the Sobel gradient. We resized all images to a xed resolution to eliminate the
downsides of dierent image resolutions. Gaussian-based smoothing helped us cut down high frequency
noise. As pre-segmentation we built a three-level Gaussian-Laplacian pyramid to dene initial
pixel groups. The original pyramid-based method which uses brightness distance was modied to
eliminate the blocking problem. After these, we had groups of 16 pixels maximum. To detect
complex segments, we implemented a modied Felzenszwalb and Huttenlocher[
Algorithm Segmentation (Isrc, τ1, τ2) τ1 and τ2 are threshold functions. Let I2 be the source image, I1 and I0 are the down-scaled images. Let P (x, y, i) be the pixel P (x, y) in the image on level i (Ii). Let G = (V, E) be an undirected weighted graph where ∀vi ∈ V corresponds to a pixel P (x, y). Each edge (vi, vj ) has a non-negative weight w(vi, vj ).
Gaussian-Laplacian Pyramid 1. For every P(x,y,1) J oin(P (x, y, 1), P (x/2, y/2, 0))
dif f Y (P (x, y, 1), P (x/2, y/2, 0)) 2. For every P(x,y,2) J oin(P (x, y, 2), P (x/2, y/2, 1)) dif f Y (P (x, y, 2), P (x/2, y/2, 1)) if if τ1 τ1 < < Graph-based Segmentation 1. Compute M axweight(R) = maxe∈MST (R,E) w(e) for every coherent group
of points R where M ST (R, E) is the minimal spanning tree 2. Compute Co(R) = τ2(R) + M axweight(R) as the measure of coherence
between points in R 3. J oin(R1, R2) if e ∈ E exists so w(e) < min(Co(R1), Co(R2)) is true, where R1 T R2 = ∅ and w(e) is the weight of the border edge e between
R1 and R2 4. Repeat steps 1,2,3 for every neighboring group ( R1, R2) until possible to
join two groups
This algorithm sometimes does not nd relevant parts with low initial thresholds. To nd the relevant borders which would disappear with the graph-based method we calculated the gradient image to select important edges from remainders. Typically we detected a hundred or less segments in a regular image. where n is the number of segments in the sample image, S(Q) is the set of segments of image Q, S(I) is the set of segments of the sample-image S. So, we took all the segments in the sample image, and searched for the closest segment in the query image. After this, we summed up all the distances for the sample image. Doing this in the other way would also be possible: for each segment in the query image we could search closest segments in the sample images. We choose our direction, because for each topic the sample images and its segments are xed, and this way, dist(Q) does not depend on the number of segments in the query image. To be sure, we are using a normalization by n, but found that this way the distances are better. From the 3 sample-images, we took the closest one. 4
Image segment annotation word biclustering Clustering is used to group together similar objects and has practical importance in a wide variety of applications such as web-log and market-basket data analysis. The data in this applications is arranged as a co-occurrence table. Most of the clustering algorithms clusters one dimension of the co-occurrence table based on the similarities along the second dimension. Biclustering is simultaneously clusters both dimensions of the table by exploiting the duality between rows and columns.
We used the following biclustering algorithm [
CX : {x1, x2, ..., xk} 7→ {xˆ1, xˆ2, ..., xˆk},
CY : {y1, y2, ..., yl} 7→ {yˆ1, yˆ2, ..., yˆl}.
For brevity we write Xˆ = CX (X) and Yˆ = CY (Y ) where Xˆ and Yˆ are random variables that are a deterministic function of X and Y , respectively. Finally let D(p k q) denote the Kullback-Leibler divergence of probability distributions p and q.
Algorithm BiClustering p, k, l, CX(0), CY(0)
Y 1. Compute segment (row) clusters: For each segment x , nd its new cluster index as
CX(t+1)(x) = argminxˆ D p(x, Y ) p(x)
p(t)(xˆ, yˆ) k p(Y ) · p(t)(xˆ) · p(t)(yˆ) , resolving ties arbitrarily. Let C(t+1) = CY(t) .
Y 2. Compute word (column) clusters: For each word y, nd its new cluster index as
C(t+2)(y) = argminyˆ D
Y p(X, y) p(y)
p(t+1)(xˆ, yˆ) k p(X) · p(t+1)(xˆ) · p(t+1)(yˆ) resolving ties arbitrarily. Let CX(t+2) = CX(t+1) .
3. set t = t + 2 and go to step 1.
We modied the above algorithm at the rst step by combining KL-divergence with euclideandistance on the segment features as follows. Let f1(x), ..., fs(x) denote the features of a segment x. Let ci(xˆ) be the avarage of fi(x) (i = 1, ..., s) where x ∈ xˆ. With this notations the modied rst step is
CX(t+1)(x) = argminxˆ D p(x, Y ) p(x)
p(t) k p(Y ) · ( xˆ, yˆ)p(t)(xˆ) · p(t)(yˆ)
vu s + utX i=1 fi(x) − ci(t)(xˆ) 2 5
Image distance with bicluster information We extended the CBIR method by using the above described biclustering method. It was supposed that these biclusters indicate some semantical connection between the features and the text. This was used to rene the CBIR method. When the segments of the 3 sample-images were examined, we tried to lter them. All the segments were examined if there is a word in a corresponding textual bicluster, which occurs in the title of the topic. The title of the topic was a short description. If there is at least one word in common, then we assumed, that the segment is semantically connected to a word, which is relevant. Consequently, we included this segment in our computation. In the rare case, when all of the segments of a sample-image was excluded, we included them all again, since an empty set of segments would not do anything good. The distance measure was done the same way with the ltered segments. 6
We have demonstrated that the biclustering of image segments and annotation words can improve the performance of an IR system.
Our future work to be done includes to improve the content based IR behind the results, to test various settings of the segmentation and the biclustering algorithm. And nally, to use query expansion and feedback in order to demonstrate whether the method can improve performance over the state of the art.