-

Augmenting Bag-of-Words { Category Speci c Features and Concept Reasoning

Eugene Mbanya

Christian Hentschel

Sebastian Gerke

Mohan Liu

Andreas Nurnberger

andreas.nuernberger@ovgu.de 0

Patrick Ndjiki-Nya

patrick.ndjiki-nyag@hhi.fraunhofer.de 1 0 Data & Knowledge Engineering Group, Faculty of Computer Science, Otto-von-Guericke-University Magdeburg , Germany 1 Fraunhofer Institute for Telecommunications, Heinrich Hertz Institute

2096

In this paper we present our approach to the 2010 ImageClef PhotoAnnotation task. Based on the well-known bag-of-words approach we suggest two extensions. First, we analyzed the impact of category speci c features and classi ers. In order to classify quality-related image categories we implemented a sharpness measure and use this as additional feature in the classi cation process. Second, we propose a postclassi cation step, which is based on the observation that many of the categories should be considered as being related to each other: Some categories exclude or allow for inference to others. We incorporate inference and exclusion rules by re ning the classi cation results. The results we obtain show that both extensions can provide a classi cation performance increase when compared the the standard BoW approach.

Visual data such as image and video represents the fastest growing data in the Internet today. Photo communities such as Flickr host more than 4 billion photos3. E cient retrieval methods are thus required to provide access to this vast amount of information, which would otherwise be useless. The sheer amount of data, however, renders manual annotation impossible and demands for automatic approaches. The ImageClef Photo Annotation Task is an annual competition, which gathers researchers to meet this challenge and provide solutions for automatic classi cation of photos taken from the Flickr community into di erent categories. In this paper we describe our approach to the 2010 ImageClef PhotoAnnotation Task [ 4 ].

We follow the widely-used visual codebook approach [ 5 ]. We extract local image descriptors, which are an extension of the standard SIFT algorithm by Lowe[ 3 ]. As many of the visual concepts provided within the task show a uniform distribution in texture space, instead of extracting features at scale-space extrema the features are densely extracted by computing the descriptor at xed grid of feature points. Following the visual codebook paradigm, we cluster similar features into groups, each represented by a visual (code)word. This is done by vector quantizing a subset of all features of all images in the training set. The codebook is the set of all visual words. It is used to describe an image in terms of the codeword frequency distribution by assigning features to codewords. Thus, for each image a simple histogram of codewords provides a compact feature representation. An extension of this approach was presented in [ 2 ]. As some concepts are more likely to be present in speci c regions of an image (e.g. sky is more likely to be present in the upper image part) the authors suggest to split an image into xed subregions. Di erent resolutions of subregions are aggregated into a so-called spatial pyramid. Histograms of codewords are computed for each of these regions and distances between images are computed region-wise.

While the described process has the strong advantage of being generic with respect to the extracted features, concept speci c peculiarities can hardly be captured. We show that a weighted combination of generic and concept-speci c features can increase the overall classi cation accuracy. As an example we extract a sharpness measure to handle quality-based image categories (such as image blur).

Category learning is done by training an kernel-based classi er. Support vector machines have been widely used for image classi cation tasks. We apply a 2-metric for distance computation as this has shown to provide good results in histogram classi cation [ 9 ].

Finally, we propose a classi cation post-processing step, which is motivated by the idea of category co-occurrences. An analysis of the di erent image categories in the training set has shown, that many of the categories interfere with each other in sense that the presence of one category gives evidence to or excludes the presence of another. Category reasoning is implemented as a postclassi cation re nement step.

In the following, we describe the aforementioned steps in more detail: Section 2 describes the feature extraction and codebook generation process in detail. In section 3 we describe the process of category learning and image classi cation while section 4 provides information on the aforementioned category postprocessing. Finally, section 5 summarizes this paper by giving some results and providing an outlook to future work. 2

Feature Extraction

For classi cation, two types of features have been used. One is the so-called OpponentSIFT [ 8 ] feature, an extension of the Scale-Invariant-Feature Transform (SIFT, [ 3 ]) features to the opponent color space while the other one is a sharpness measure for an image to be used in sharpness and blur related categories. As shown in [ 8 ], the OpponentSIFT feature with dense sampling was the best performing single feature for an annotation task and therefore has been chosen as a baseline for our submission. 2.1

OpponentSIFT

The general principle of the OpponentSIFT based feature extraction is depicted in gure 1. First, the image is converted to the opponent color space. The opponent color space is given by the following de nition from the RGB color space: 0O11 0 Rp2G 1 @O2A = B R+Gp6 2B C (1)

O3 @ R+pG3+B A Channel O3 represents the intensity channel, while O1 and O2 represent the color components. Due to the subtraction in the rst two channels, these are shift-invariant with respect to light intensity but not scale-invariant [ 8 ].

On each of the channels of the opponent color space, SIFT features are extracted on a dense grid (we use a step size of 6 pixels) at a x image scale over the image. SIFT features are extracted by rst computing a gradient image on each of the color channels. Then, for each feature point, a region of 64 64 pixels around it is considered for its feature vector. This 64 64 pixel block is subdivided into 4 4 cells, each containing 16 16 pixels. For each cell, a histogram of its gradient directions, aligned to the main gradient direction, is computed. These 16 histograms are concatenated to build the feature vector for one point.

After obtaining one 384-dimensional (3 color channels 16 cells 8 orientation histogram bins) feature vector for each point, those vectors are quantized using K-Means clustering of a random subset of 800.000 features from all 8000 training images (i.e. 100 random features per image) with 4000 cluster centers (visual words). Then each feature point on the dense grid is assigned to a visual word by using a nearest neighbor classi er. Now that each feature point is described by its visual word, a histogram over these visual words in an image is computed, resulting in a 4000-dimensional histogram for each image. Similar to [ 2 ], in addition to this single histogram for the whole image, histograms for parts of the image are created. Therefore, two spatial partitions are de ned, one (1 3) consisting of 3 vertically stacked regions and one (2 2) consisting of the four image quadrants. This yields a total of eight histograms: One for the whole image, three for 1 3 partition and four for the 2 2 partition. Each individual histogram is then L1 normalized, i.e. divided by the sum of the bin population. To equally distribute the in uence of di erent spatial partitions, the histograms of the 1 3 partition are weighted by 13 and the histograms of the 2 2 partition are weighted by 14 . Finally, the histograms for a spatial partition are concatenated, resulting in histograms of 4000, 12000 and 16000 bins respectively. These histograms are then used in the SVM for classi cation. 2.2

Sharpness Features

In addition to the OpponentSIFT based features, a sharpness measure is used as an example for category-speci c features. Therefore, the no-reference objective image sharpness measure by Ferzli and Karam described in [ 1 ] is used. This metric is based on user studies on blur perception in the human visual system (HVS). It incorporates the fact that the perception of blur in an image part is dependent on the edge statistics in this image part. Thus, a Sobel lter is used to generate an edge image. The edge image is then divided into 64 64 pixel blocks and all blocks are classi ed as edge or smooth blocks. A block is de ned as an edge block where more than 0.2% of the pixels are edge pixels. Only edge blocks are considered when calculating the sharpness measure. The sharpness measure DRb for an edge block Rb is calculated by

DRb =

X ei2Rb

w(ei) wJNB(ei) ! 1 where is a constant xed to 3:6, w(ei) is the edge width around pixel ei in vertical or horizontal direction respectively and wJNB(ei) is the just noticeable blur width corresponding to the contrast of the block Rb. The sharpness measure for the complete image is then calculated by where

D =

S =

D X Rb jDRb j ! 1 (2) (3) (4)

To incorporate this metric into a Support Vector Machine we use a Gaussian kernel: and L being the total number of blocks in the image. This resulting sharpness metric S 2 R+ ,with higher values indicating sharper images, has been used as a scalar input to the classi ers. 3

Category Learning and Classi cation

Kernel-based Support Vector Machines (SVM) have been widely used in visual codebook-based image classi cation scenarios (see e.g. [ 9 ],[ 8 ], [ 6 ]).

We use a two-class setting for binary classi cation, i.e. classifying images depicting a speci c concept or not.

As in our case, training and testing samples are histograms of codeword distributions, we use the 2 distance, which has shown to provide good results for comparing distributions [ 9 ]. Given two histograms H = (h1; :::; hm) and H0 = (h01; :::; h0m) the 2 distance is de ned as:

The normalization parameter can be optimized using grid search and crossvalidation. However, Zhang et al. [ 9 ] have shown, that setting this value to the average distance between all training image histograms gives comparable results and reduces the computational e ort. The only parameter we optimize in a cross-validation is the cost parameter C of the support vector classi cation. We precompute the kernel matrix to to speed up subsequent training of the SVM. Additional speed is gained by computing the matrix in parallel on an 8-Core SMP-System. As described in section 2, we yield three di erent histograms per image { one per spatial pyramid resolution { which results in three di erent kernels.

In addition to the codeword histograms, we extracted a scalar quality measure (see sec. 2.2). The distance between to images is based on the absolute value of the di erence value of both scalars. We use a linear kernel to compare for the quality measure as this has shown to provide better results than a Gaussian Kernel in our experiments.

Finally, we combine these four kernels by averaging their output into a single kernel, which is then used to train the Support Vector Machine. Here we use the implementation provided by the SHOGUN machine learning toolbox [ 7 ]. As the SHOGUN LibSVM implementation does not provide a probabilistic output we simply compute the sigmoid function in order to obtain values in [0::1]. (5) (6)

Category Post-processing

In its current form, each category is treated independently from all other categories, assuming that dependencies between categories do not exist. This assumption actually does not hold in reality. There are even strong dependencies between di erent categories, i.e. categories excluding each other (such as day and night ) or categories inferring other categories (e.g. plant can be inferred from ower ). These dependencies have been accounted for by post-processing the classi cation decisions and con dences from the SVMs. Therefore, dependencies have been extracted from the training set. For exclusion of categories, partitions of categories have been identi ed, i.e. sets of categories P that do not co-occur and exactly one category of this set appears in the training annotations for each image: In these de nitions, I is the set of all images, P is the set of category indices belonging to a partition and Cp is the set of images annotated with category p. For category inference, pairs of categories are determined such that the statement "If an image is annotated with category a, it is also annotated with category b" holds. Formally, for these category pairs holds: (7) (8) (9) (10) (11) [ Cp = I p2P p2P \ Cp = ; Ca

Cb This update rule can only increase the con dence value for a category, not decrease it.

After determining the sets of excluding categories and the inference rules from the training set, these rules are used to post-process the output of the SVMs. The new con dence value c0(i; p) for a category p is set to 0 if a higher con dence value for a di erent category within partition P exists. Only the largest con dence value for a category in a partition is kept.

c0(i; p) = c(i; p) 0 if c(i; p) > c(i; q) else 8q 2 P n p If there are no other categories in an exclusion set with higher con dence values, the con dence value is kept. The con dence value of an image for a category q that is on the right side of an inference rule p ) q is updated if the con dence value of the left-hand side category p is greater than 0.5 and greater than the con dence value for category q: c0(i; q) = c(i; p) c(i; q) if c(i; p) > c(i; q) ^ c(i; p) > 0:5 else

Results and Summary

We submitted 5 di erent runs. All runs use the OpponentSIFT histograms as baseline. The rst run (OpSIFT ) uses the OpponentSIFT features alone. Another run (OpSIFT+Excl+Inf+Qual ) uses the quality measure as an additional feature and applies category inference and exclusion as post-processing step. A third run (OpSIFT+Qual ) does no post-processing but uses the quality feature. The fourth run (OpSIFT+Inf+Qual ) uses the quality feature and applies only the category inference rule as we have noticed that exclusion often decreases the overall classi cation performance. A nal vth run (OpSIFT+Inf ) uses the OpponentSIFT features and applies the inference rule on the classi cation results.

Three di erent evaluation measures have been computed. For evaluating the classi cation performance per concept the Mean Average Precision (MAP) was used. The evaluation per example was performed using the example-based FMeasure (F-Ex). Additionally an ontology score based on Flickr Context Similarity was computed (OS-fcs, for a detailed description see [ 4 ]). Table 1 shows the average scores achieved for each measure. For all evaluation measures, the runs with extensions to the baseline OpponentSIFT method gave the best results.

Run-Con guration MAP Avg. F-Ex OS-fcs OpSIFT 0.3492 0.6283 0.6318 OpSIFT+Excl+Inf+Qual 0.3331 0.6341 0.6401 OpSIFT+Qual 0.3495 0.6275 0.6362 OpSIFT+Inf+Qual 0.3495 0.6278 0.6364

OpSIFT+Inf 0.3493 0.6285 0.6319

Table 2 shows that using the additional category-speci c features yields a gain of 0.00567 in terms of mean average precision for those categories where the sharpness feature has been used (i.e. motion blur, out of focus, partially blurred and no blur ). The reasons for this little gain are, in our opinion, two-fold: On one side, the weight of the sharpness feature has not been optimized yet, resulting in a potential over- or under-estimation of the importance of the category-speci c feature. On the other side, the sharpness measure disregards the orientation of edges, making it harder for the classi ers to distinguish between di erent kinds of blur as to be expected in the categories motion blur and out of focus.

Table 3 shows the detailed average precision for each category individually. As not all extensions to the baseline method are applied to all categories, the results for those categories do not di er between runs. For those categories where the results di er, the best performing run is highlighted in the table. In terms of MAP per category, the exclusion of categories often performed worse than the other runs. Especially for categories where the average precision is already low, the exclusion method even diminishes the results. We found that is due Category Motion Blur Out of Focus Partly Blurred No Blur Mean Average Precision 0.4953 si er of bad performing categories have a very small output range, e.g. values ranging from 0.94 to 0.96. In those cases, the number of support vectors used for these categories is usually near the total number of training samples. Using these categories for inference or exclusion of other categories yields a signi cant performance decrease, propagating the error introduced by one categories' classi er to other categories. In future, a check for the reliability of a classi er should be added to avoid this error propagation. This holds also for the category inference post-processing method, where this can happen as well. Error propagation also led to the decision that only inference rules with a con dence of 1.0 were used, missing opportunities were category inference could be used as well but evaluations have shown that in those cases, performance can drop signi cantly.