We participate in the ImageCLEF 2012 Photo Annotation Tasks. We devote our attention to make our system scalable for the data amount. Therefore we train linear classi ers with our online multilabel learning. For Flickr Photo task, we extract visual Fisher Vectors (FVs) from some kinds of local descriptors and used the provided Flickr-tags for textual features. For Web Photo tasks, we just use the provided Bagof-Visual-Words (BoVW) of some kinds of SIFT descriptors. A linear classi er for each label is obtained with an online multilabel learning, Passive-Aggressive with Averaged Pairwise Loss (PAAPL). The results have shown that our scalable system achieves pretty good performances in all tasks we take part in.
In this paper, we describe our method for the ImageCLEF 2012 Photo
Annotation tasks. In particular, we attack three tasks: concept annotation using Flickr
photos [
Especially, we pay our attention to the scalability for the data amount. In this literature, many techniques are developed to improve the performance of object recognition. Though some of them have succeeded by introducing a complicated classi er such as the multiple kernel SVM, the complexity for leaning and annotating is a problem. Because many kinds of labels require a large amount of training data, the scalability for the data amount is important for generic object recognition.
Consequently, our objective is to investigate scalable methods for feature
extraction, for learning, and for annotation. Recent studies for large scale
image classi cation adopt online learning for linear classi cation. In [
Our main contribution is the investigation of our novel online learning for
multilabel problem. Because batch learning by loading all training samples is
impossible, usage of an online learning is a promising method in order to realize
scalability. In [
In this section, we describe the features we use in three tasks. For the Flickr Photo task, we extract FVs as visual features and some kinds of BoW of Flickrtags as textual features. For the Web Photo tasks, we use the provided Bag-ofVisual-Words only. 2.1
Bag-of-Visual-Words. Bag-of-Visual-Words (BoVW) is quite a popular approach for image classi cation, because it achieves good performance in spite of its simplicity. The main idea is that images are treated as loose collections of K codewords, representative local descriptors, and that each key-point patch, in which a local descriptor is extracted, is sampled independently. The BoVW feature is obtained by making a histogram of the number of local descriptors assigned to each codeword. The dictionary, which consists of K codewords, has to be generated by unsupervised clustering of training samples in advance and each local descriptor is assigned to the nearest codeword in the dictionary. BoVW vector is therefore K-dimensional.
Fisher Vectors. Fisher Vectors (FV), which is regarded as an extension of the BoVW representation, is a standard approach to the large-scale image recognition. BoVW utilizes 0-order statistics of the distribution of local descriptors, whereas FV utilizes 1- and 2-order statistics. The distribution of local descriptors is tted to the mixture model of K Gaussians, and the gradients of the likelihood in the parameter space are computed. The gradients describe which direction the model parameters are to be modi ed to get a better description of the image. The dimensions are then whitened by multiplying the square root of the Fisher information matrix.
We denote T local descriptors by X = fx1; x2; ; xT g, and the mixture weight, mean, covariance matrix of i-th Gaussian by wi, i, and i, respectively. Since the covariance matrices are assumed to be diagonal, we denote the variance vector by 2. The FV representation is thus given as,
GX;i =
1 ∑T t(i) T pwi t=1 ( xt
i GX;i = T p 1 2wi t=1
T ∑ t(i) [ (xt i )
; i)2 2 i ] 1 ; where t(i) is the soft assignment of xt to i-th Gaussian as follows, t(i) = wiui(xt) K j=1wj uj (xt) :
Then, we obtain the 2KD-Dimensional vector by concatenating GX;i and GX;i.
To enhance the performance, a power normalization is proven to be effective in
[
We use Bag-of-Words (BoW) representation, which is based on the idea that each word in a text appears independently. BoW is obtained by counting appearance of words in a text. In our method, the feature is converted in following two ways, TF-IDF and L2-normalization.
TF-IDF weight We regard the typicality of each Flickr-tag as a clue to how the tag relates to the image's contents. Therefore, we use TF-IDF value for each element of a BoW vector.
L2-normalization To reduce the effect of different numbers of tags among images, we simply L2-normalize the BoW vectors. 3
Online Multilabel Learning To learn the models for each label from various images, requirements are not only compatibility of scalability for the data amount and accuracy for label estimation, but also tolerability of noise.
Given the t-th training sample xt 2 Rd associated with a label set Yt, a subset of Y = f1; : : : ; nyg, it is classi ed with the present weight vector tyi (i = 1; : : : ; ny)1 as, y^t = arg max tyi xt:
yi 1 Here, the bias b is included in t as t⊤ [ t⊤; b] by rede ning xt⊤ (4) If necessary, multiple labels are estimated in score order.
Multilabeling for one sample is applicable by de ning ny > 1. Here, hinge-loss ℓ is given as, ℓ( trt ; tst ; (xt; Yt)) = Therein, denotes a slack variable representing the bound of the loss. C signi es a parameter to reduce the negative in uence of noisy labels. It can be derived using Lagrange's method of undetermined multipliers. Therefore we obtain, (6) (7) (8) (9) rt t+1 = trt + t xt; st t+1 = st t
t xt; t = minfC; ℓ( trt ; tst ; (xt; Yt))=(2xt2)g:
This PA is called PA-II in [
PA is online learning methods for classi cation, but it presents no problem if a
sample is associated with multiple labels. Indeed, the Passive{Aggressive Model
for Image Retrieval (PAMIR) [
However, they treat only one relevant label and one irrelevant label. Apparently, models of some labels are not well updated and that convergence becomes delayed.
Therefore, we have proposed a novel online learning algorithm for which
multiple labels are attached to one sample in [
e r o c
S correct labels e r o c
S correct labels e t a d p u
e r o c
S correct labels e r o c
S correct labels e t a d p u classi cation of a sample is O(dny), while update of a model is O(d). If we update all models with given labels Yt, its complexity becomes O(djYtj). In image annotation and especially sentence generation, we can assume ny ≫ jYtj. Therefore, since classi cation is the rate-controlling step, total computation time remains much the same whether we update one model or jYtj models. Fig.1 shows the conceptual difference between hinge-loss and the loss used in proposed method. Thus the proposed PAAPL achieves efficiency by averaging all pairwise loss between relevant and irrelevant labels. 1. Given a t-th image, de ne label set Yt of ny labels by selecting highly scored and irrelevant labels. 2. Randomly select one relevant label rt from Yt and one irrelevant label st from Yt. 3. Based on a hinge-loss between rt and st, 1 ( trt xt tst xt), update models according to PA.
Additionally, we investigate a way to reduce the complexity O(dny) for the
classi cation step. In [
PA; otherwise move on to next training sample.
In this section, we describe the details of methods we use for Flickr Photo annotion task, Web Photo subtask1, and Web Photo subtask2, respectively. 4.1
In our experiment, we extracted 5 kinds of visual descriptors from each image,
SIFT and LBP in ve patch sizes, and color-SIFTs (C-SIFT, RGB-SIFT,
OpponentSIFT) in three patch sizes. As pre-processing, the images were resized
into at most 300 300 pixels, of which aspect ratio were maintained. To
calculate SIFT and LBP, the images were rendered in gray scale, in contrast to
color-SIFTs which utilized color information. Then, each descriptor was
densesampled on regular grids (every six pixels). The dimensionalities of SIFT, LBP,
and color-SIFTs were 128, 1024, and 384 respectively. All of these descriptors
were reduced to 64 dimensions with PCA, and then coded into two
state-of-theart global feature representations. (5 2 = 10 visual features in total) One is
FV, explained in the previous section. At rst, we trained the mixture model
of 256 Gaussians using standard EM-algorithm. To embed spatial information,
FVs were calculated respectively over 1 1, 2 2, and 3 1 cells. In this way,
we obtained FVs whose dimensionality was 64 256 8 2 = 262; 144. The
other is Locality-constrained Linear Coding (LLC) [
As text features, BoW vectors were extracted from Flickr-tags, and then we also prepared the one whose dimensions were removed if the corresponding words appeared 24 times or less. Furthermore, all combinations of 2 kinds of processing (TF-IDF, L2-normalization) were done, so 2 22 = 8 text features were generated in total. Finally, the classi ers of 10 visual features and 8 text features were trained separately using PAAPL. The trade-off parameter was set to C = 105. All the experiments in the following sub-section were implemented using a workstation with CPUs of 12-core and 96GB RAM.
The validation set consisted of one-third of the training images, and validation was done only two times for the lack of time.
The size of the visual feature such as FV or LLC tends to be large. It is
known to be effective to quantize the vector with Product Quantization (PQ) as
described in [
Since the number of runs which could be submitted was limited, we examined which combinations of visual features were effective. Then we investigated which text feature should be added to achieve the best performance through the next experiment.
The Table 1 shows the top six F1-measures of the combinations of 210 = 1; 024 visual features. These features were all quantized with PQ. Note that all LLCs are shown to be inefficient here. In this way, we chosen to extract FVs from SIFT, from C-SIFT, and from LBP, which achieved the best performance.
FV-SIFT
FV-LBP FV-OpponentSIFT
FV-cSIFT FV-rgbSIFT LLC-SIFT
LLC-LBP LLC-OpponentSIFT
LLC-cSIFT LLC-rgbSIFT ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ F1-measure
The Table 2 shows the F1-measures of eight text features. As a result, thresholding w.r.t. the number of corresponding images is not effective for the performance. Therefore, we chosen only four text features which were not thresholded. threshold ✓ histgram TF-IDF
L2 L2 0.5157 0.5156 0.5135 0.5121 0.5114 0.5109 0.5020 0.4990
Finally, we present the top six F1-measures (F1) of the combinations of three visual features and for text features in the Table 3. 2 Following these results, we submitted our runs described in Table 4 and got the scores also shown in Table 4. Note that all of these visual features from test images were not quantized. 2 FV from SIFT is not quantized here.
Visual (FV) Textual (BoW) FV-SIFT FV-LBP FV-cSIFT histgram TF-IDF histgram (L2) TF-IDF (L2) ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
F1 For Photo Web tasks, we could not extract FVs because there were no images in the provided dataset. Hence we use the provide BoVWs from some kinds of SIFTs.
Moreover, our PAAPL requires labels for each training sample. We investigated a simple way to de ne the labels for each training sample. In particular, we extracted words whichever are concept words from the surrounding texts for each image. Images around which any concepts do not exist are just discarded. Subtask 1: Improving performance in Flickr concept annotation task For Flickr and Web image representation, we made use of four provided BoVWs, which were computed respectively from SIFT, C-SIFT, OpponentSIFT and RGBSIFT. Unlike Flickr data, Web data was not annotated. Therefore we needed to estimate labels of web data for using it as training data in supervised learning. In order to do this, we sought for concepts in surrounding texts. If any concept labels exist in a textual feature, then we consider that the corresponding image has that label.
To annotate images, we use PAAPL with regularization parameter from 104, 105 and 106. As a result, C = 106 achieves the best performance in almost all cases where a classi er is trained on different type descriptors. The number of training iteration is 25, same as the Flickr Photo task.
We have two ideas on how to utilize web data for improvement of annotation performance. One idea is that we use Web data and Flickr data independently. At rst, we trained eight classi ers using four types BoVWs from either Web data or Flickr data. Then, we summed the scores form the eight classi ers when we annotated the test images. To nd best combinations of descriptors, we used 10000 Flickr images or 10000 Web images for training, and 5000 Flickr data for validation. We computed F1-measure as a measure of effectiveness of a combination. Results are shown in Table 5. The best F1-measure is worse than that Flickr
SIFT C-SIFT O-SIFT RGB-SIFT
SIFT 0.2086 0.2195 0.2162 0.2119 eb C-SIFT 0.2158 0.2207 0.2220 0.2195 WO-SIFT 0.2190 0.2276 0.2252 0.2227
RGB-SIFT 0.2009 0.2112 0.2062 0.2031 obtained by the other idea, so we do not adopt this idea.
The other idea is that we merge 15000 Flickr data and 250000 web data , and uni ed 265000 data is used for training. Classi ers are trained respectively for each type of BoVW computed from different descriptor, so we have four classi ers. Scores for each label are computed by summing scores from each different classi ers. A number of ways of combining classi ers is ∑i4=1 4Ci = 15. To nd best combinations of four different classi ers, we use 10000 Flickr images and 10000 Web images for training, and 5000 Flickr data for validation. Then we computed F1-measure shown in Table 6.
Therefore we submitted the following combinations of BoVWs. 1. SIFT + C-SIFT 2. SIFT + C-SIFT + Opponent SIFT 3. SIFT + C-SIFT + RGB-SIFT 4. SIFT + C-SIFT + Opponent SIFT + RGB-SIFT In combination of Web and Flickr photos, we obtained MiAP 0.264, GMiAP 0.217 and F1 0.182. However, we obtained MiAP 0.719, GMiAP 0.689 and F1 0.553 when we use only Flickr photos. This means that improving performance in Flickr concept annotation task using Web photos is not successful. Although improving performance in Web concept annotation task using Flickr photos seems to be meaningful, Web images are too noisy with such a simple way to combine. Subtask 2: Scalable concept image annotation Before we achieved the results, we took three steps as follows.
F1 ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
First, in order to assign concepts to each image, we compared the concepts to the raw text extracted near each image. If the raw text contains a concept, the concept is assigned as one of the concepts of the image.
Second, using randomly sampled 10000 training data from web and test data from all development set, we made grid search as for the two parameters in PA, that is C = f104; 105; 106g and the iteration number N = f10; 15; 20; 25g. These candidates are empirically selected. As a result, shown in Fig.2, we chose fCC SIF T = 104; COpponentSIF T = 104; CRGB SIF T = 104; CSIF T = 106g and the iteration number N = 25.
Finally, utilizing the parameters stated above, we trained the weight vectors corresponding to each feature from all 250k web data. After training, we examined all combinations (24 = 16) calculated by summing up the candidates from the four dot products of weight vectors and BoVW feature vectors. We assigned three concepts which had highest combined scores to each image from development set. We submitted ve runs from 16 combinations as the results of the development set by calculating mean F1-measure (shown in Table 7) and used the same ve combinations in order to achieve the results of the test set.
Therefore we submitted the following combinations of BoVWs.
As a result, we obtained MiAP 0.332, GMiAP 0.227, and F1 0.254. These scores
are higher than those we obtained with Web images in Subtask 1.
CC−SIFT=104
CC−SIFT=105
CC−SIFT=106
CO−SIFT=104
CO−SIFT=105
CO−SIFT=106
CR−SIFT=104
CR−SIFT=105
CR−SIFT=106
CSIFT=104
CSIFT=105
CSIFT=106
0.21
In this working note, we describe our method to annotate images in ImageCLEF
2012 Photo Annotation and Retrieval tasks. We pay our attention to make our
method scalable for a large amount of images. Consequently, we use FVs and
BoWs in Photo Flickr task, and use the provided BoVW in Photo Web tasks.
Annotation itself is achieved using a novel online learning PAAPL, which has
been already proposed in [
For Photo Flickr task, we have achieved the top scores among all teams although our system is scalable and simple. Not only FVs from SIFTs but also FV from LBP is shown to be useful for annotation. Moreover, simple tag information with BoW improves the performance. For Photo Web tasks, there are few teams that have submitted at least one run. In Subtask 1, there are no teams that have improved the performance with Web data. The result of Subtask 2 also indicates that the Web Photoes are difficult to be extracted their proper concepts from their Web pages.
F1