Image Description Literature Review

2004 IEEE International Conference on Multimedia and Expo (ICME)

Automatic Image Captioning*

Jia-Yu Pant, Hyung-Jeong Yang’, Pinar Duygulu’ and Christos Faloutsost tComputer Science Department, Camegie Mellon University, Pittsburgh, U.S.A.

‘Department of Computer Engineering, Bilkent University, Ankara, Turkey ‘fiypan, hjyang, christosJecs.cmu.edu, ‘duygulu@cs. bilkent.edu. f r

Abstract In this paper, we examine the problem of automatic

image captioning. Given a training set of captioned images, we want to discover correlations between image features and keywords, sa that we can automatically find good keywords for a new image. We experiment thoroughly with multiple design alternatives an large datasets of various content st$es, and our proposed methods achieve up to a 4.7% relative improvement on captioning accuracy over the state of the art.

1. Introduction and related work “Given a large image database, find images that

have tigers. Given an unseen image, find terms which best describe its content.” These are some of the problems that many imagelvideo indexing and retrieval systems deal with (see [4][5][10] for recent surveys). Content based image retrieval systems, matching images based on visual similarities, have some limitations due to the missing semantic information. Manually annotated words could provide semantic information, however, it is time consuming and error- prone. Several automatic image annotation (captioning) methods have been proposed for better indexing and retrieval of large image databases [11[21[31[61[71.

We are interested in the following problem: “Given a set of images, where each image is captioned with a set of terms describing the image content, find the association between the image features and the terms”. Furthermore, “with the association found, caption an unseen image”. Previous works caption an image by captioning its constituting regions, by a mapping from image regions to terms. Mori et al. [IO] use co- occurrence statistics of image grids and words for modeling the association. Duygulu et al. [3] view the mapping as a translation of image regions to words, and learn the mapping between region groups and

words by an EM algorithm. Recently, probabilistic models such as cross-media relevance model [6] and latent semantic analysis (LSA) based models [ I I ] are also proposed for captioning.

In this study, we experiment thoroughly with multiple d e s i s alternatives (better clustering decision; weighting image features and keywords; dimensionality reduction for noise suppression) for better association model. The proposed methods achieve a 45% relative improvement on captioning accuracy over the result of [3], o n large datasets o f various content styles.

The paper is organized as follows: Section 2 describes the data set used in the study. Section 3 describes an adaptive method for obtaining image region ngoups. The proposed uniqueness weighting scheme and correlation-based image captioning methods are given in Section 4 and S . Section 6 presents the experimental results and Section 7 concludes the paper.

2. Input representation We leam the association between image regions and

words from manuallv annotated images (examDles are

sea. sun. skv. waves cat. forest. mass. tieer

w6 w7 w8 w l w2 w9 w IO w l 1 Figure 1. Top: annotated images with their captions, bottom: corresponding blob-tokens and word tokens.

This material is based upon work suppalted by the National Science Foundation under Grants No. lR1-9817496,US-9988876, US-0113089, OS-0209107. US-0205224. NI-0318547, SENSOR-0329549. EF-0331657, by the Pennsylvania hfrastmcture Technology Alliance (PITA) Grant No. 22-901-0001, and by the Defense Advanced Research Pmjects Agency under CanVact No. N66001-00-1-8936. Additional funding was provided by donations from Intel. and by U gift from Nonhmp-Gmmman Corporation.

0-7803-8603-5/04/~20.00 WO04 IEEE 1987

An image region is represented by a vector of features regarding its color, texture, shape, size and position. These feature vectors are clustered into B clusters and each region is assigned the label of the closest cluster center as in [3]. These labels are called blob-tokens.

Formally, let 1 4 1 lr...rIN) be a set of annotated images where each image Ii is annotated with a set of terms W i = ( w , , ~ ._.., w . ~ ; ) and a set o f blob tokens Bi=(bi,,, ..., biflj]. where L; is the number of words, and Mi is the number of regions in image Ii. The goal is to construct a model that captures the association between terms and the blob-tokens, given Wi’s and Bcs.

3. Adaptive blob-token generation The quality of blob-tokens affects the accuracy of

image captioning. In [3], the blob-tokens are generated using the K-means algorithm on feature vectors of all image regions in the image collection, with the number of blob-tokens, E , set at 500. However, the choice of B=500 is by no means optimal.

In this study, we determine the number of blob- tokens B adaptively using the G-means algorithm [12]. G-means clusters the data set starting from small number of clusters, E , and increases B iteratively if some o f the current clusters Fail the Gaussianity test (e.g., Kolmogorov-Smirov test). In our work, the blob- tokens are the labels of the clusters adaptively found by G-means. The numbers of blob-tokens generated for the 10 training set are all less than 500, ranging from 339 to 495, mostly around 400.

4. Weighting by uniqueness If there are W possible terms and B possible blob-

tokens, the entire annotated image set of N images can be represented by a data matrix D L N . b y . ( ~ + ~ , I - W e now define two matrices: one is unweighted, the other is uniqueness-weighted as initial data representation.

Definition 1 (Unweighted data matrix) Given an annotated image set 1=(11, ..., IN] with a set of terms W and a set of blob-tokens B, the unweigbted data matrix D ~ l ’ D w o l D ~ ~ ] is a N-by-(W+Bj matrix, where the (i,jJ- element of the N-by-W matrix Dwo is the count of term wi in image ti, and the (i,jj-element of the N-by-B matrix DBO is the count of blob-token bi in image Ii.

W e weighted the counts in the data matrix D according to the “uniqueness” of each tendblob-token. If a term appears only once in the image set, say with image I , , then we will use that term for captioning only when we see the blob-tokens of II again, which is a small set of blob-tokens. The more common a term is, the more blob-tokens it is associated with, and the uncertainty of finding the correct term/blob-token

association goes up. The idea is to give higher weights to terms (blob-tokens) which are more “unique” in the training set, and low weights to noisy, common terms (blob-tokens).

Definition 2 (Uniqueness-weighted data matrix) Given an unweighted data matrix Do=[DwolD~ol. Let z, ( y j j be the number of images which contain the term wi (the blob-token hi). The weighted data matrix D=[DwIDu] is constructed from Do, where the (i,jj- element of Dw (DE), dni,,] (dB(i,jh is

N N (3) dwu.j, =dwou,j) X b - 1 , dmi,,) =dmv.j, Xlog(--), 2 , Y ,

where N is the total number of images in the set, and

In the following, whenever we mention the data d , , (dBoc;.jJ) is the (i,jj-element of Dwo (Duo).

matrix D, it will be always the weighted data matrix.

5. Proposed methods for image captioning We proposed 4 methods (Corr, Cos, SvdCorr,

SvdCos) to estimate a W-by-B translation table T, whose (i,jj-element can be viewed as p(w;lbjj, the probability we caption the term w i , given we see a blob-token bj

Definition 3 (Method Corrj Let T,,,,=DwTDB, The correlation-based translation table Tcom is defined by normalizing each column of T,m,o such that each column sum up to 1. Note that the (iJ-element of T,.,, can be viewed as an estimate ofp(w,lbjj.

T,= measures the association between a term and a blob-token by the co-occurrence counts. Another possible measure could be to see how similar the overall occurrence pattem (over the training images) of a term and a blob-token is. Such occurrence pattems are in fact the columns of DW or De, and the similarity can be taken as the cosine value between pairs of column vectors.

Definition 4 (Method Cos) Let the i-th column of the matrix Dw (De) bed, (d,;). Let cosjd be the cosine value of the angle column vectors dwi and dBj, and let TWJ be a W-by-B matrix whose (i,j)-element T,o(i,j)=cos;,j Normalize the columns of Tqo such that each column sums up to 1, and we get the cosine- similarity translation table T,.

Singular Value Decomposition (SVD) decomposes a given matrix XI-, into a product of three matrices U, A, VT. That is, X= UAVT, where U=[UI ,..., uJ, and V=[vl, ..., VJ with orthonormal columns ui’s. vi’s. A is a diagonal matrix, A=diag(ol ,..., G ~ ~ ( ~ , , , , ) ) , where ai > 0, for j 5 rank(X), aid, for j

Previous works [14] show that by setting small ai's to zero, yielding an optimal low rank representation a , SVD could be used to clean up noise and reveal

rank(X).

1988

informative structure in a matrix X and achieve better performance in information retrieval applications. We propose to use SVD to suppress the noise in the data matrix D before leaning the association. Following the general rule-of-thumb, we keep the first r ai's which preserve the 90% variance of the distribution, and set the others to zero. In the following, we denote the data matrix after SVD as Dsvd=[DwJrdlDBJvd].

Definition 5 (Merltod SvdCorr and SvdCos) Method SvdCorr and SvdCos generate the translation table Tcomsvd and Trmsvd following the procedure outlined in Definition 3 and 4, respectively. The only difference is that instead of starting with the weighted data matrix D, here the matrix Dsvd is used.

Algorithm 1 (Captioning) Given a translation table TIwSl (W total number of terms: B: total number of blob-tokens), and the number of captioning terms m for an image. An image I' with 1 blob-tokens B ' = {Vi, ..., b',), can be captioned by: First, form a query vector q=[q,, ..., qslT, where qi is the count of the blob-token bj in the set B'. Then, compute the term-likelihood vector p=Tq, where p+,, _... pwlT. pi is viewed as the predicted likelihood of the term w,. Finally, we caption the image I' with the m terms corresponding to the highest m pts in the p vector.

6. Experimental results The experiments are performed on 10 Core1 image

data sets. Each data set contains about 5200 training images and 1750 testing images. The sets cover a variety of themes ranging from urban scenes to natural scenes, and from artificial objects like jetlplane to animals. Each image has in average 3 captioning terms and 9 blobs.

We apply G-means and "uniqueness" weighting to show the effects of clustering and weighting. We compare our proposed methods, namely Corr, Cos, SvdCorr and SvdCos, with the state-of-the-art machine translation approach [3] as the comparison baseline. Each method constructs a translation table as the estimated conditional probability of a term wi given

seeing a blob-token b,, p(w,lb,). These translation tables are then used in Algorithm 1 for captioning.

The captioning accuracy S on a test image is measured as the percentage of correctly captioned words [ I ] . That is, S = m,,,,/m, where m,,,(m) is the number of the correctly (truth) captioned terms. The overall performance is expressed by the average accuracy over all images in a (test) set.

Figure 2(a) compares the proposed methods with the baseline algorithm 131 which is denoted as EM-B500- UW or simply EM (which means EM is applied to an unweighted matrix, denoted UW, in which the number of blob tokens is 500, denoted as BSOO). For the proposed methods, blob-tokens are generated adaptively (denoted AdaptB) and the uniqueness weighting (denoted w) is applied. The proposed methods achieve an improvement around 12% in absolute accuracy (45% relative improvement) over the baseline.

The proposed adaptive blob-token generation could also improve the baseline EM method. Figure 2(b) shows that the adaptively generated blob-tokens improve the captioning accuracy o f the E M algorithm. The improvement is around 7.5% in absolute accuracy (34.1% relative improvement) over the baseline method (whose accuracy is about 22%). In fact, we found that the improvement is not only on the EM method, but also on our proposed methods. When the number of blob-tokens is set at 500, proposed methods are 9% less accurate (detail figures not shown). This suggests that the correct size of blob-token set is not 500, since all methods perform worse when the size is set at 500.

Before applying the "uniqueness" weighting, the 4 proposed methods perform similar to the baseline EM method (accuracy difference is less than 3%). The uniqueness weighting improves the performance of all proposed methods except Cos method, which stays put. We also observed that weighting does not affect the result of EM. Due to the lack of space, we do not show detail figures here.

(a) (b) (C) Figure 2 Captioning a c c u r a c y improvement (a) proposed methods vs. the baseline EM-B500-UW, (b) adnprive blab- token generation on EM vs. the baseline, (c) proposed methods vs. EM when the adaptively generated blob-tokens ore used.

1989

Another measurement of the performance of a method is the recall and precision values for each word (Figure 3). Given a word w, let the set R, contains r test images captioned with the word w by the method we are evaluating. Let r* he the actual number of test images that have the word w (set R*,), and r’ be size of the intersection o f R, and R*,. Then, the precision of word w is r’lr, and the recall is r’lr*.

Note that some words have zero precision and recall, if they are never used or are always used for the wrong images (un-“predictable” words). W e prefer a method that has fewer unpredictable words, since it could generalize better to unseen images. Table I shows that the proposed methods have two to three times more predictable words on average than the baseline EM does. EM captions frequent words with high precision and recall, but misses many other words. That is, EM is biased to the training set.

Table 1. Averape recall and precision values and

#predicted 36 57 72 56 132

Avgprec.

Recall Precision Figure 3. Recall and precision of the top 20frequent words in the test sei. SvdCorr (white bars) gives more general pegormance than baseline EM (black bars).

As an example of how well the captioning is, for the image in Figure I(a), EM-BSOO-UW and SvdCorr-AdaptB-W both give “sky”, “cloud”, “sun” and “water”. As for the image in Figure l(h), EM- BSOO-UW gives “grass”, “rocks”, “sky” and “snow”, while SvdCorr-AdaptB-W gives “grass”, “cat”, “tiger”, and “water”. Although the captions do not match the truth (in the figure) perfectly, they describe the content quite well. This indicates that the “truth” caption may he just one of the many ways to describe the image.

7. Conclusion In this paper, we studied the problem of automatic

image captioning and proposed new methods (Corr, Cos, SvdCorr and SvdCos) that consistently

0.041I 0.1131 0.1445 0.1197 0.2079

outperfom the state of the art EM (45% relative improvement) in captioning accuracy. Specifically,

W e d o thorough experiments on 10 large datasets of different image content styles, and examine all possible combinations of the proposed techniques for improving captioning accuracy.

The proposed “uniqueness” weighting scheme o n terms and blob-tokens boosts the captioning accuracy.

Our improved, “adaptive” blob-tokens generation consistently leads to performance gains.

The proposed methods are less biased to the training set and more general in terms of retrieval precision and recall.

The proposed methods can be applied to other area, such as building an image glossary of different cell types from figures in medical journals [U].

References [I] K. Bamurd, P. Duygulu. N. de Freilas. D. Fonyth, D. Blei. M. Jordan. “Matching wards and pictures”, Journal of Machine Learning Research, 3:1107:1135,2003. [ 2 ] D. Blei, M. Jordan, “Modeling annotated data”, 26th Annual Int. ACM SlGlR Canf.. Tomnto, Canada, 2003. 131 P. Duygulu, K. Bamard, N. de Freitas. D. Fonyth, “Object recognition as machine translation: learning a lexicon for B fixed image vocabulary”. h Sevenlh European Conference on Computer Vision (ECCV), Vol. 4, pp. 97-1 12. 2002. [4] D. A. Fonyth and 1. Ponce, “Computer Vision: a mudem approach”. Prcntice-Hall, 20431. [5l A. Goodmm “Image information retrieval: An overview of current research”. Informing Science. 3(2), 2000. 161 J. Jeon, V. Lavrenko, R. Manmatha. “‘Automatic Image Annotation and Retrieval using Cross-Media Relevance Models‘’. 26th Annual Int. ACM SlGlR Conference, Tomnto, Canada, 2003. [7] J. Li and I. Z. Wmg, “Automatic linguistic indexing of pictures by a statistical modeling approach, IEEE Trans. on Pattern Analysis and Machine Intelligence. 25(10). 2003. [8] M. Markkula, E. Sonnunen, “End-user searching challenges indexing praclices in the digital newspaper pholo archive”, hformation retrievd, “0l.l. 2000. [Y] Y. Rui, T. S. Huang, S.-F. Chang, “Image Retrieval Past, Present, and Future”. Journal of Visual Communication and Image Representation. 10:1-23, 1999. [ I O ] Y. Mori. H. Takahashi, R. Oka, “hnage to word transformation based an dividing and vector quantizing images with words’: First ht. Workshop on Multimedia Intelligent Slange and Retrieval Management, 1999. [ I I ] F. Monay, D. Gatica-Perez, “On Image Auto-Annotation with Latent Space Models”, Pm. ACM hl. Conf. on Multimedia (ACM MM), Berkeley. 2003. [I21 Greg Hamerly and Charles Elkan, “Leaning the k in k- means”, proc. of the NIPS 2003. 1131 Vellirte, M. and R.F. Murphy, 2002. “Automated Delerminalion of Pmiein Subcellular Locations from 3D Fluorescence Microscope Images,” Proc 2002 IEEE Intl Symp. Biomed Imaging (ISBI 2002). pp. 867-870. [I41 G. W. Furmas, S. Deerwester, S. T. Dumais, T. K. Iandauer, R. A. Hanhman, L. A. Sweeter and K. E. Lochbaum. “lnformation retrieval using a singular value decomposition model of latent semantic sVUctue,” Proc. of the 1 Ith ACM SlGlR conf., pp. 465480,1998.

1990