In this paper, we present a multiple targets classification system for visual concepts detection and image annotation. Multiple targets classification (MTC) is a variant of classification where an instance may belong to multiple classes at the same time. The system is composed of two parts: feature extraction and classification/annotation. The feature extraction part provides global and local descriptions of the images. These descriptions are then used to learn a classifier and to annotate an image with the corresponding concepts. To this end, we use predictive clustering trees (PCTs), which are capable to classify an instance to multiple classes at once, thus exploit the interactions that may occur among the different visual concepts (classes). Moreover, we constructed ensembles (random forests) of PCTs, to improve the predictive performance. We tested our system on the image database from the visual concept detection and annotation task part of ImageCLEF 2010. The extensive experiments conducted on the benchmark database show that our system has very high predictive performance and can be easily scaled to large number of images and visual concepts.
An ever increasing amount of visual information is becoming available in digital form in various digital archives. The value of the information obtained from an image depends on how easily it can be found, retrieved, accessed, filtered and managed. Therefore, tools for efficient archiving, browsing, searching and annotation of images are a necessity.
A straightforward approach, used in some existing information retrieval tools for visual materials, is to manually annotate the images by keywords and then to apply text-based query for retrieval. However, manual image annotation is an expensive and time-consuming task, especially given the large and constantly growing size of image databases.
The image search provided by major search engines, such as Google, Bing, Yahoo! and AltaVista, relies on textual or metadata descriptions of images found on the web pages containing the images and the file names of the images. The results from these search engines are very disappointing when the visual content of the images is not mentioned, or properly reflected, in the associated text.
A more sophisticated approach to image retrieval is automatic image
annotation: a computer system assigns metadata in the form of captions or keywords to
a digital image [
Most of the systems for detection of visual concepts learn a separate model
for each visual concept [
In this paper, we present a system for detection of visual concepts and
annotation of images. For the annotation of the images, we propose to exploit the
interactions between the target visual concepts (inter-class relationships among
the image labels) by using predictive clustering trees (PCTs) for MTC. PCTs
are able to handle multiple target concepts, i.e., perform MTC. To improve the
predictive performance, we use ensembles (random forests) of PCTs for MTC.
For the extraction of features, we use several techniques that are recommended
as most suitable for the type of images at hand [
We tested the proposed approaches on the image database from the visual
concept detection and annotation task part of ImageCLEF 2010 [
The remainder of this paper is organized as follows. Section 2 presents the proposed large scale visual concept detection system. Section 3 explains the experimental design. Section 4 reports the obtained results. Conclusions and a summary are given in Section 5. 2 2.1
Fig. 1 presents the architecture of the proposed system for visual concepts
detection and image annotation. The system is composed of a feature extraction
part and a classification/annotation part. We use two different sets of features
to describe the images: global and local features extracted from the image pixel
values. We employ different sampling strategies and different spatial pyramids
to extract the visual features (both global and local) [
Images (Train / Test) Feature extraction
Visual features Spatial pyramid Sampling strategy
Codebook transform Descriptors of images PCTs for MTC / Classifiers
Predictions / Annotations
As an output of the feature extraction part, we obtain several sets of
descriptors of the image content that can be used to learn a classifier to annotate the
images with the visual concepts. Tommassi et al. [
The high level fusion scheme (depicted in Fig. 2) is performed as follows. First, we learn a classifier for each set of descriptors separately. The classifier outputs the probabilities with which an image is annotated with the given visual concepts. To obtain a final prediction, we combine the probabilities output from the classifiers for the different descriptors by averaging them. Depending on the domain, different weights can be used for the predictions of the different descriptors.
Following the reccomendations from [
We define the task of multiple targets prediction as follows: Given: – A description space X that consists of tuples of primitives (boolean, discrete or continuous variables), i.e. ∀Xi ∈ X, Xi = (xi1 , xi2 , ..., xiD ), where D is the size of a tuple (or number of descriptive variables), – a target space Y , where each tuple consists of several variables that can be either continuous or discerete, i.e., ∀Yi ∈ Y, Yi = (yi1 , yi2 , ..., yiT ), where T is the size of a tuple (or number of target variables), – a set of examples/instances E, where E = {(Xi, Yi)|Xi ∈ X, Yi ∈ Y, 1 ≤ i ≤
N } and N is the number of examples of E (N = |E|), and – a quality criterion q (which rewards models with high predictive accuracy and low complexity).
Find: a function f : X → Y such that f maximizes q. Here, the function f is presented with decision trees, i.e., predictive clustering trees.
If the tuples from Y (the target space) consist of continuous/numeric variables then the task at hand is multiple targets regression. Likewise, if the tuples from Y consist of discrete/nominal variables then the task is called multiple targets classification. 2.3
In the PCT framework [
PCTs are constructed with a standard “top-down induction of decision trees” (TDIDT) algorithm. The heuristic for selecting the tests is the reduction in variance caused by partitioning the instances, where the variance V ar(S) is defined by equation (1) below. Maximizing the variance reduction maximizes cluster homogeneity and improves predictive performance.
A leaf of a PCT is labeled with/predicts the prototype of the set of examples
belonging to it. With appropriate variance and prototype functions, PCTs can
handle different types of data, e.g., multiple targets [
The prototype function returns a vector containing the probabilities that an example belongs to a given class for each target attribute. This afterwards can be used to calculate the majority class for each target attribute. The variance function is computed as the sum of the entropies of class variables:
T Var (E) = X GiniCoefficient (E , yi ) i=1 (1)
For a detailed description of PCTs for MTC the reader is referred to [
Random Forests of PCTs To improve the predictive performance of PCTs,
we use ensemble methods. An ensemble classifier is a set of classifiers. Each
new example is classified by combining the predictions of each classifier from
the ensemble. These predictions can be combined by taking the average (for
regression tasks) or the majority vote (for classification tasks) [
We use random forests as an ensemble learning technique. A random forest [
We use different commonly used types of techniques for feature extraction from
images. We employ two types of global image descriptors: gist features [
Local features include scale-invariant feature transforms (SIFT) extracted
densely on a multi-scale grid [
We computed four different sets of SIFT descriptors over the following color
spaces: RGB, opponent, normalized opponent and gray. For each set of SIFT
descriptors, we use the codebook approach to avoid using all visual features of
an image [
The generation of the codebook begins by randomly sampling 50 key-points from each image and extracting SIFT descriptors in each key-point (i.e., each key-point is described by a vector of numerical values). Then, to create the codewords, we employ k-means clustering on the set of all key-points. We set the number of clusters to 4000, thus we define a codebook with 4000 codewords (a codeword corresponds to a single cluster and a codebook to the set of all clusters). Afterwards, we assign the key-points to the discrete codewords predefined in the codebook and obtain a histogram of the occurring visual features. This histogram will contain 4000 bins, one for each codeword. To be independent of the total number of key-points in an image, the histogram bins are normalized to sum up to 1.
The number of key-points and codewords (clusters) are user defined
parameters for the system. The values used above (50 key-points and 4000 codewords)
are recommended for general images [
We evaluated our system on the image database from the visual concept
detection and annotation task part of ImageCLEF 2010. The image database consists
of training (8000) and test (10000) images. The images are labeled with 93 visual
concepts [
We generated six sets of visual descriptors for the images: four sets of SIFT descriptors (one detector, dense sampling, over four different color spaces) with 32000 bins for each set (8 sub-images, from the spatial pyramids: 1x1, 2x2 and 1x3, 4000 bins each). We also generated two sets of global descriptors (gist features with 960 bins and RGB color histogram with 512 bins).
The parameter values for the random forests were as follows: we used 100 base classifiers and the size of the feature subset was set to 10% of the number of descriptive attributes. 3.2
The evaluation of the results is done using three measures of performance
suggested by the organizers of the challenge: mean average precision (MAP),
Fmeasure and average ontology score (AOS) [
The mean average precision is widely used evaluation measure. For a given target concept, the average precision can be calculated as the area under the precision-recall curve for that target. Hence, it combines both precision and recall into a single performance value. The average precision is calculated for each visual concept separately and the obtained values are then averaged to obtain the mean average precision.
The F-measure is also widely used measure and it is well known. F-measure is calculated as the weighted harmonic mean of precision and recall: P recision · Recall F − measure = 2 · P recision + Recall (2)
The AOS measure calculates the misclassification cost for each missing or
wrongly annotated concept per image. The AOS score is based on structure
information (distance between concepts in the provided ontology of concepts),
relationships from the ontology and the agreement between annotators for a
concept extend with misclassification cost that incorporates the Flickr context
similarity costs map [
Additionally, we report Equal Error Rate (EER) and Area Under the ROC
curve (AUC). However, we do not discuss these evaluation measures because
they were not used for the evaluation of the submitted runs by the organizers of
the competition [
We have submitted four different runs (see Table 1). We do not use the EXIF metadata and the Flickr user tags provided for the photos. This means that all our runs consider automatic annotation using only visual information.
The runs can be divided using the following criteria: used descriptors and rescaling of the outputs. We used two different sets of descriptors: only SIFT (local descriptors) and SIFT combined with global descriptors (RGBHist and Gist). Since the AOS measure uses threshold 0.5 to determine wheter an image is annotated with a concept, we lineraly scale the probabilities to cope with the skewed distribution of the visual concepts. The linear scaling can be done on low level or high level. With the low level approach, we linearly scale the outputs from each classifier (obtained from the separate descriptors) and then average these values. For the high level approach, we linearly scale the averaged output of the classifiers.
The runs can be summarized as follows: – SIFT + RGBHist + Gist (HLScale): local descriptors (SIFT) and global descriptors (RGBHist and Gist) with high level linear scaling. – SIFT (HLScale): local descriptors (SIFT) with high level linear scaling. – SIFT + RGBHist + Gist (LLScale): local descriptors (SIFT) and global descriptors (RGBHist and Gist) with low level linear scaling.
– SIFT (LLScale): local descriptors (SIFT) with low level linear scaling. 4
values for the following visual concepts: Neutral-Illumination, No-Visual-Season,
No-Blur, No-Persons, Outdoor, Sky, Day, Landscape-Nature, No-Visual-Time,
Clouds, Natural, Plants. We obtain lower AP values for the concepts that are less
represented in the training set of images (e.g., rain, horse, skateboard, graffiti...)
and the ‘difficult’ concepts (e.g., abstract, technical, boring). The agreement of
human annotators on the ‘difficult’ concepts is ∼ 75% [
Further improvements can be expected if different weighting schemes are used (to combine the predictions of the various descriptors). The weight of the descriptors can be adapted for each visual concept separately. For instance, the SIFT descriptors are invariant to color changes, and they do not predict well concepts where illumination is important. Thus, the weight of the SIFT descriptors in the combined predictions for those concepts should be decreased. Also we should find better descriptors for these concepts, such as estimating the color temperature and overall light intensity.
Another approach is to tackle the problem with the skewed distribution of concepts over the images. On approach can be generation of virtual images containing the under-represented visual concepts. These virtual images can be obtained with re-scaling, translation, rotation, changing the brightness of the images from the under-represented concepts. 5
Multiple targets classification (MTC) problems are encountered increasingly often in image annotation. However, flat classification machine learning approaches are predominantly applied in this area. In this paper, we propose to exploit the dependencies between the different target attributes by using ensembles of trees for MTC. Our approach to MTC builds a single classifier that simultaneously predicts all of the visual concepts present in the images at once. This means adding new visual concepts will just slighly decrease the computational efficiency. While, for the other approaches that create a classifier for each visual concept separately this means learning an additional classifier.
Applied on the image database from the visual concept detection and annotation task part of ImageCLEF 2010 our approach was ranked fourth for the example-based performance measures (Ontology Score with FCS and Average
F-measure) and fifth for the concept-based evaluation (Mean Average Precision), out of 17 competing groups.
The system we presented is general. It can be easily extended with new feature extraction methods, and it can thus be easily applied to other domains, types of images and other classification schemes. In addition, it can handle arbitrarily sized hierarchies organized as trees or directed acyclic graphs.