Exploiting Multi-Modal Interactions: A Unified Framework

1 Introduction

With the explosive accumulation of digital images, many imagebases have been developed. How to organize and search an imagebase effectively and efficiently poses a big challenge for researchers. Previous researches on content-based image retrieval (CBIR) suffer from the big gap between the lowlevel visual feature and the high-level semantics. Recently, much attention has been paid to exploiting some tagged images to bridge such semantic gap. Actually, given a group of tagged images, several types of tasks can be executed on an imagebase, which can be summarized as follows.

• Image-In Image-Out: This corresponds to the contentbased image retrieval task, where the user poses a query image and then the system returns a set of relevant images.
• Image-In Text-Out: This corresponds to the image annotation task, where the user poses a query image and then the system returns a set of annotation words.
• Text-In Image-Out: This corresponds to the text-based image retrieval task, where the user poses a text query and then the system returns a set of relevant images.

∗This research was supported by NSFC (60635030, 60721002), 863 Program (2007AA01Z169), JiangsuSF (BK2008018) and Jiangsu 333 Program. Currently the second author is pursuing Ph.d. degree at the University of Massachusetts at Amherst.

• Text-In Text-Out: This corresponds to the query expansion task, where the user poses a text query and then the system returns some words as hints to help the user to refine the original query.

Many successful approaches have been proposed for each type of the above tasks respectively. For example, Translation Model (TM) [Duygulu et al., 2002], Latent Dirichlet Allocation (MoM-LDA) [Barnard et al., 2003] and Hidden Markov Model (2DMHMM) [Li and Wang, 2003] have been used for image annotation. Cross Media Relevance Model (CMRM) [Jeon et al., 2003] and Structure-Composition Model [Datta et al., 2006] have demonstrated their effectiveness for textbased image retrieval. CBIR [Smeulders et al., 2000] has been studied thoroughly in pure imagebases which contain only untagged images, while query expansion [Baeza-Yates and Ribeiro-Neto, 1999] is a hot topic in pure textbases that do not involve images.

However, few studies have considered all these tasks from a unified view. In fact, although these four tasks focus on different goals, they all involve common basic elements, i.e., the blob (the visual feature used to represent an image) , the word (the unit of an image's annotation) and the image itself. Thus, a good estimation of the similarities on these elements is essential for all these tasks.

The conventional similarity between two blobs (words) is based on the co-occurrence in images. In other words, two blobs (words) that tend to appear in the same images are similar. However, this similarity could not account for the situation that two blobs (words) appear in similar but not the same images. Thus, a more reasonable estimation of similarity between blobs (words) needs to consider the similarity between images. Similarly, the similarity between images also relies on the similarity between blobs (words). It is more reasonable to consider two images as similar when they contain similar blobs (words) instead of exactly the same ones. Generally, in imagebase the similarities between one type of objects (e.g., blobs) are inevitably influenced by the similarities between other type of objects (e.g., images). It is evident that an improved similarity on one type of entity may help to improve the similarity on another type of entity. Thus, by working in a unified framework, it may be possible to improve the similarities of all types of objects by exploiting the interactions among them. Experiments show that, amazingly, simple methods with the improved similarity can even beat the state-of-the-art techniques on the four aforementioned tasks.

Above all, a different strategy is adopted in this paper: instead of designing sophisticated models for each type of the four tasks respectively, we focus on the common basis of these tasks, i.e., the similarity of the concerned objects. The improved estimation of similarity has been obtained through exploiting the interactions among different objects under a unified framework.

The rest of paper is organized as follows. Section 2 briefly reviews some related work. Section 3 proposes the unified framework for exploiting interactions among objects. Section 4 reports experimental results. Finally, Section 5 concludes.

2 RelatedWork

Many studies have been conducted for image annotation and text-based image retrieval. In addition to the work mentioned in Section 1, Blei and Jordan [2003] proposed the correspondence LDA (Corr-LDA) to model the conditional relationship between the latent variables and Xing et al. [2005] proposed the dual-wing harmoniummodel for image annotation, which bears the properties of efficient inference and robust topic mixing. Kang et al. [2006] proposed the Correlated Label Propagation (CLP) to explicitly model the correlations between class labels.

Since CMRM and CLP will be used as baselines in our experiments, here we introduce more details. CMRM is a modification of the relevance based language model. The joint probability of words and blobs are modelled through accumulating the evidence from the training set. After marginalizing this joint probability, the image can be annotated easily. Unlike previous methods which propagate the class labels independently, CLP simultaneously co-propagates multiple labels from the training set to the test set and uses an efficient algorithm to avoid combinatorial explosion.

Kandola et al. [2003] proposed the semantic similarity, which models the interaction between document and word, with application to text classification. Lafferty and Zhai [2001] used the Markov chain to model the same interaction for text retrieval.

Hardoon et al. [2003] proposed to use Kernel Canonical Correlation Analysis (KCCA) to learn a semantic representation for images with associated text. This semantic representation can be considered as a new feature space, where the correlation between the visual features of images and the associated text of images is maximized. The cross-media retrieval can be conducted through first mapping both the query and images into this semantic space and then calculating the inner-product between the query and images. The major difference between KCCA and our method lies in the fact that the maximization of the correlation between two feature sets does not necessarily lead to the minimization of the difference between two similarity matrices of images calculated from different feature sets. In our method, we implicitly achieve the latter target through modelling the interactions between image and text.

Pan et al. [2004] proposed a graph-based method (GCap). After constructing the graph for each type of objects, a random walk with restarts is executed to solve the task in imagebase. Guo et al. [2007] explicitly modelled the relations between blob and word by structural learning techniques. Our method focuses on the refined similarities of each type of objects instead of the cross type relations.

3 AUnified Framework

Here, we consider an imagebase consisting of a set of tagged images T , a set of untagged images U, a set of image blobs B and a set of annotation words W.

Formally, B = {b1, b2, · · · , bc} where bj is an image blob; W = {w1,w2, · · · ,wd} where wj is an annotation word. T = {t1, t2, · · · , tm} where ti = (⃗xi, ⃗yi) is a tagged image, ⃗xi = [#(b1, ti),#(b2, ti), · · · ,#(bc, ti)]⊤, ⃗yi = [#(w1, ti), #(w2, ti), · · · ,#(wd, ti)]⊤ . Here #(bj, ti) indicates the frequency that the blob bj appears in ti, and #(bj, ti) = 0 if bj does not appear in ti. ⃗xi is the visual representation vector of ti 1 . Similarly, ⃗yi is the annotation word vector of ti; #(wj, ti) indicates the frequency the word wj appears in the annotation of ti, and #(wj , ti) = 0 if wj does not appear in ti. U = {u1, u2, · · · , ul} where ui = (⃗zi, φ) is an untagged image, i.e., the annotation words of the image are not known, ⃗zi = [#(b1, ui), #(b2, ui), · · · , #(bc, ui)]⊤. It is also possible to describe each blob bj and each word wj by considering its appearances in the images in T as ⃗bj = [#(bj, t1),#(bj, t2), · · · ,#(bj, tm)]⊤ where #(bj, ti) indicates the frequency bj appears in the image ti, and ⃗wj = [#(wj , t1), #(wj , t2), · · · ,#(wj, tm)]⊤ where #(wj, ti) indicates the frequency wj appears in the annotation of the image ti 2 . Furthermore, c × m blob-image relation matrix is denoted as M = [⃗x1, ⃗x2, · · · , ⃗xm] = [⃗b1,⃗b2, · · · ,⃗bc]⊤ and the d × m word-image relation matrix is denoted as N = [⃗y1, ⃗y2, · · · , ⃗ym] = [ ⃗w1, ⃗w2, · · · , ⃗wd]⊤3 .

3.1 Interactions of Different Types of Objects

Assume SB denotes the similarity matrix of blobs where SB(i, j) = sim(bi, bj), SW denotes the similarity matrix of words where SW(i, j) = sim(wi,wj), and ST denotes the similarity matrix of images where ST(i, j) = sim(ti, tj). The calculation of the similarities of each type of objects is summarized in Table 1. Note that the similarity of images can be calculated based on either blobs or words they contain.

For example, the first row of Table 1 shows the initial similarity of two blobs 4 , which assumes that blobs appearing in the same images tend to be similar. By further considering the similarity of images, a refined blob similarity is shown in the second row, which assumes that blobs appearing in similar images tend to be similar.

Table 1 clearly shows that the estimations of SB, SW and ST are influenced by each other. In order to differentiate the similarity of images calculated based on their constituent blobs (as shown in Row 3 and 4 of Table 1) and their annotation words (as shown in Row 7 and 8 of Table 1), we denote the former as STB and the latter as STW . The way of substituting ST in Table 1 with STB and STW defines the following four types of interactions between blobs, images and words, as shown in Figure 1:

1 The blob-based representation is widely used for image annotation and retrieval [Duygulu et al., 2002; Jeon et al., 2003].

2 Note that bj (wj) is used to denote the blob (word) and ⃗bj (⃗wj) is used to denote its corresponding vector representation.

3 Similar matrix definition is widely used in collaborative filtering for modelling the user-item relation.

4 Here the similarity function is in the form of inner-product, but note that our basic idea can also be applied to other kinds of similarity functions.

• Type I: SB =MSTBM⊤, SW =NSTB N⊤ The interaction is restricted to images and blobs, but its influence can propagate to words via images.
• Type II: SB =MSTWM⊤, SW =NSTW N⊤ The interaction is restricted to images and words, but its influence can propagate to blobs via images.
• Type III: SB =MSTBM⊤, SW =NSTW N⊤ Blobs and words interact with images separately, and no information flows between blobs and words.
• Type IV: SB =MSTWM⊤, SW =NSTB N⊤ There exist complete interactions between blobs, images and words, and the information can flow among all types of objects.

Following the directed edges in Figure 1, we formalize the iterative similarity updates with respect to each type of interactions, where the similarity can be decomposed into the initial similarity without any interaction with other types of objects and the refined similarity from other objects based on the interactions between objects.

• Type I:

· Type II:

• Type III:

• Type IV:

Here, 0 < λ1, λ2, λ3, λ4 < 1, which balance the contribution of the refined similarities and the initial similarities S(0) B =MM⊤, S(0) TB = M⊤M, S(0) W = NN⊤, S(0) TW = N⊤N.

One question arises: Do the similarity refinement converge? In the following, we prove the convergence of the refinement of SB, SW, STB and STW . Since Type IV interaction is the most complicated one among the four interactions, we provide the convergence analysis of SB for Type IV as an example. The result is summarized in the following proposition. Similar results can be obtained for the other similarities for different types of interactions, and will be presented in a longer version.

Proposition 1. Let C = (λ1λ2λ3λ4) 12MN⊤NM⊤, whose eigenvalues are {e1, e2, · · · , ec}. If |ei| < 1 (i = 1, · · · , c), then lim n→∞ (S(n) B - S(n-1) B ) = 0.

Proof.

where n = 4p + q (q = 1, · · · , 4).

Since C is a symmetric matrix, which can be decomposed as C = QDQ⊤, where Q is an orthogonal matrix and D is a diagonal matrix whose diagonal elements are the eigenvalues of C. Substituting C in the above equation yields

Since |ei| < 1 (i = 1, · · · , c), lim p→∞ Dp = 0. Therefore, we

Based on the convergence of the similarities, we further derive the close-form solution of all the similarities for each interaction type. Due to space limitation, we only provide the derivation of SB for Type IV and the other derivation will be presented in a longer version.

By plugging Eqs.(4b)∼(4d) into Eq.(4a) in Type IV, Eq.(4a) can be rewritten as

where

If |ei| < 1 (i = 1, · · · , c), by Proposition 1, assume that the sequence S(n) B converges to S∗B. When n → ∞, since C = QDQ⊤ and D = diag(e1, e2, · · · , ec), we obtain

With some algebra, we obtain the solution for Eq. 7 as:

where Σ = [σij ]c×c, σij = (1 - eiej)-1 ; ⊙ is element-wise matrix multiplication.

Note that in many real tasks, data can be normalized before the similarity learning process to ensure the convergence.

3.2 Tackling the Four Tasks with Refined Similarities

We address how to use the refined SB and SW after exploiting multi-modal interactions to tackle the four image-text tasks as we mentioned in Section 1 5 .

5 Since these four tasks mainly concern about untagged images, the similarity matrices of tagged images, i.e., STB and STW , are not used, but these matrices are obviously very useful for other tasks such as clustering tagged images.

Table 2: Simple methods to tackle the four tasks with the improved similarities.

Task: Content-based Image Retrieval

Input:

Image Query qimg

Output: A rank of ui in U

Process: a) For each ui = (⃗zi, φ) in U, scorei = getScore(⃗qimg, ⃗zi, SB) b) Sort scorei decreasingly to get the rank of ui

Task:

Image Annotation

Input:

Image Query qimg, the number of nearest neighbors k

Output: A rank of wi inW

Process: a) For each ti = (⃗xi, ⃗yi) in T, scorei = getScore(⃗qimg, ⃗xi, SB) b) Sort scorei decreasingly to get a rank of ti. If ti belongs to the top k of this rank, set δi = 1k ;otherwise, set δi = 0.

d) Sort the element of ⃗h decreasingly to get the rank of wi.

Task: Text-based Image Retrieval

Input: Text Query qtxt, the number of nearest neighbors k

Output: A rank of ui in U

Process: a) For each ui = (⃗zi, φ) in U, repeat steps a)-c) of Image Annotation to

get corresponding ⃗hi, scorei = getScore(⃗qtxt, ⃗hi, I) % I is identity matrix

b) Sort scorei decreasingly to get the rank of ui

Task: Query Expansion

Input: Text Query qtxt

Output: A rank of wi inW

Process: a) For each wi inW, construct ⃗wi as a d × 1 vector with the ith position

as 1 and the other positions as 0, scorei = getScore(⃗qtxt, ⃗wi, SW) b) Sort scorei decreasingly to get the rank of wi

For content-based image retrieval and image annotation, the input is an image query qimg whose vector representation is ⃗qimg = [ #(b1, qimg),#(b2, qimg), · · · , #(bc, qimg )]⊤. For text-based image retrieval and query expansion, the input is a text query qtxt whose vector representation is ⃗qtxt = [#(w1, qtxt), #(w2, qtxt), · · · , #(wd, qtxt)]⊤ . We apply simple methods shown in Table 2 to solve these tasks based on the refined similarities SB and SW.

In Table 2, the function getScore(⃗v1, ⃗v2, S) first uses S to obtain the "expanded" representations of ⃗v1, ⃗v2, where ⃗v′1 = ⃗v1 × S and ⃗v′2 = ⃗v2 × S, and then, computes the score based on certain similarity measurement between ⃗v′1 and ⃗v′2 .

4 Experiments

We use the database in [Duygulu et al., 2002] in our experiments. This database contains 5,000 images from 50 COREL Stock Photo CDs, each of which contains 100 images on a topic. 499 image blobs are generated through image segmentation using normalized cuts and region clustering using kmeans. The number of blobs contained in each image ranges from 1 to 10. 374 words are used to annotate the images,and the number of words in each image ranges from 1 to 5. The training set consists of 4,500 images and the test set consists of 500 images. We use the training set as the tagged images and regard the test set as untagged images.

As shown in Table 2, the outputs of the four tasks are all ranks. Thus, we use the standard non-interpolated mean average precision (MAP) and precision at 10 (P@10) to measure the performance. MAP measures the precision of the whole ranking list and P@10 reflects the precision of the top 10 elements in the ranking list. Details can be found in [BaezaYates and Ribeiro-Neto, 1999].

First, we focus on content-based image retrieval, image annotation and text-based image retrieval. In our experiments, we compare the performance of using different values of SB for these three tasks. The 'Baseline' method does not consider the relations between blobs and assume two images are similar when they contain the same blobs, thus the identity matrix is used for SB, i.e., SB = I. The 'Initial' method uses the initial value of SB, i.e., SB = SB(0) =MM⊤. The 'Type I', 'Type II' and 'Type IV' methods use the final similarity generated by the interactions of Type I, Type II and Type IV 6 , i.e., SB = SB(∗) . By comparing 'Baseline' with 'Initial' and 'Type I/II/IV', we can show the effect of considering the relations between blobs.

For 'Type I/II/IV', the parameters λ1 to λ4 are simply set to the same value, denoted by λ0. We set λ0 = 0.5, which implies that for any type of objects, its own similarity and the influence from other types of objects are equally important. Other values of λ0 will be studied at the end of this section. For 'Baseline', 'Initial' and 'Type I/II/IV', when they are used to solve image annotation and text-based image retrieval tasks, the number of nearest neighbors k is set as 100 using the validation set (see Table 2). To avoid decomposing a large matrix, we normalize the matrices into probability transition matrices and conduct random walk solution iteratively 7 .

CMRM, CLP and SVM are the state-of-the-art techniques for image annotation. Using the strategy of Datta et al. [2006], these methods can also be applied to content-based image annotation and text-based image annotation. GCap can be used for all these three tasks. For CMRM, the parameters α and β are set to 0.1 and 0.9, respectively, which are the best parameters tuned on validation set. For CLP, the parameter β is set to 0.9 based on the validation set. For SVM, we use LibSVMwith default parameters. For GCap, the parameter c which balances the probability of random walking and restarting is very similar to λ0 of our method. c is first selected as 0.7 according to Pan et al. [2004]'s suggestion and the influence of c is studied with λ0 at the end of this section. In general, the performance of these state-of-the-art techniques provides a good baseline.

6 In Type III, SB is the same as Type I and SW is the same as Type II, thus we do not report the performance of Type III.

7 This iterative approach converges quickly. For example, for Type I interaction, it converges in no more than 10 iterations.

In the experiments on content-based image retrieval, queries consisting of 500 images in the test set and images sharing some annotation words with the query are regarded as relevant images. In the experiments on image annotation, for the returned rank of annotation words, a word is regarded as relevant if it is in the annotation of the query image. We also use 500 images in the test set as queries. For text-based image retrieval, an image is regarded as relevant to the text query if its annotation contains all the query words. The query set consists of 179 one-word queries, 385 two-word queries, 176 three-word queries and 24 four-word queries. These queries appear at least two times in the annotations in imagebase. The performances of our methods and the state-of-the-art techniques for these three tasks are reported in Table 3.

Table 3 shows that for these three tasks, 'Type I/II/IV' and 'Initial' consistently and significantly outperform the other compared methods. Such an observation indicates that considering the relation between blobs is beneficial. Comparing 'Type I/II/IV' and 'Initial', we can find that exploiting the interactions between different types of objects can further improve the performance achieved by exploiting the relation between blobs. Such superiority is obvious in terms of MAP rather than P@10, which suggests that exploiting multimodal interactions can help improve the ranks of some "hardto-identified" relevant items and hence result in a better overall ranking list. Comparing three interaction types, we can observe 'Type II/IV' consistently perform better than 'Type I'. Recall that in 'Type I', information never flows back from "words" to the other interacting types. Since information in blobs might be less reliable than words due to the semantic gap, it is natural for 'Type II/IV' to be superior.

Second, we study query expansion. This task requires the involvement of the user, thus it is difficult to measure the performance of this task directly. Instead, we attempt to measure SW, which is essential for query expansion. As mentioned above, the experimental database contains 50 topics. The correlation of words based on their distributions over these 50 topics is used to assign each word a ground truth rank of the other words according to their relatedness to the concerned word. Note that this topic information is only used here for evaluation purpose and is not used for any other step. Here, we simply regard the top 5 words of each word's ground truth rank as relevant and the others are irrelevant. Then, we measure how good the word-to-word relations reflected by SW are. The 'Baseline' method could not be applied here, since SW = I is not helpful for query expansion. The 'Initial' method uses SW = NN⊤. The 'Type I/II/IV' methods use SW = SW(∗) generated by the interactions of Type I/II/IV. Only GCap is evaluated here, since other compared methods are not applicable to query expansion. The average performance is reported in Table 3. Similar to the other three tasks, for query expansion, every interaction type performs significantly better than 'Initial' and GCap.

In the experiments, λ0 is fixed to 0.5. Now we study the influence of different λ0 on the performance of the proposed method. The performance of GCap with different c is also reported for comparison. CMRM is used here for reference. The results are provided in Figure 2. It is obvious that with different λ0, our proposed method almost always outperforms CMRM and GCap, except that when λ0 ≥ 0.8, GCap performs better than 'Type I/IV' in terms of P@10. Note that 'Type I/IV' still perform better than GCap in terms of MAP. It suggests that even if 'Type I/IV' might put fewer relevant words in the first 10 words of the ranking list, the ranks assigned to the relevant words can still be higher than that assigned by GCap to yields better MAP.

5 Conclusion

Given an imagebase which contains tagged images, four types of tasks can be executed, i.e., content-based image retrieval, image annotation, text-based image retrieval, and query expansion. For any of these tasks the similarity on the concerned type of objects is essential. Usually three major types of objects in an imagebase are image blobs, annotation words and images. Since these objects have strong interactions, it is reasonable to refine the similarity of one type of objects with the help of that of another type of objects.

In this paper, we propose a unified framework to model such interactions. Experiments show that, with the similarity refined by the proposed method, simple methods can outperform the state-of-the-art methods.

Currently we represent each image as a group of blobs. Extending our proposal to other representations is an interesting issue for future work. Automatically selecting the parameters λ1-λ4 for different types of interactions is another interesting future work.