Visual Analysis of Tag Co-occurrenceon Nouns and Adjectives
Yuya Kohara and Keiji Yanai
Department of Informatics, The University of Electro-Communications,Tokyo
1-5-1 Chofugaoka, Chofu-shi, Tokyo, 182-8585 Japan,
kohara-y,yanai@mm.cs.uec.ac.jp

Abstract. In recent years, due to the wide spread of photo sharing Web
sites such as Flickr and Picasa, we can put our own photos on the Web
and show them to the public easily. To make the photos searched foreasily, it is common to add several keywords which are called as “tags”
when we upload photos. However, most of the tags are added one by
one independently without much consideration of association between
the tags. Then, in this paper, as a preparation for realizing simultaneous recognition of nouns and adjectives, we examine visual relationshipbetween tags, particularly noun tags and adjective tags, by analyzing
image features of a large number of tagged photos in social media sites
on the Web with mutual information. As a result, it was turned out thatmutual information between some nouns such as “car” and “sea” andadjectives related to color such as “red” and “blue” was relatively high,which showed that their relations were stronger.

1

Introduction

In recent years, due to the wide spread of digital cameras and mobile phones
with camera, the amount of images on the Web has increased explosively. At
the same time, because photo sharing sites such as Flickr have become common
where users post their images with tags, there are so many tagged images on theWeb. These tag information are used as a keyword on image search. However,most of the tags are added one by one independently without much considerationof association between the tags. This sometimes causes irrelevant results when we
do AND-search with multiple keywords. For example, we obtain a photo showing
blue sky and a red car for the query with “blue AND car”. To remove such aphoto and to obtain only the photos including blue cars, simultaneous image
recognition of multiple tags such as “blue cars” is needed. If we can automaticallyeliminate irrelevant images, search results for multiple keywords become morecorrect. In addition, we can create dataset easily with less noise. In order toperform more accurate image acquisition and image search, it is necessary to take
into account the relationship between the tags and to focus more on contents ofimages. Then, in this paper, we analyze visual relationship between nouns andadjectives using a large number of tagged images in social media sites on the
Web such as Flickr. To do that, we use entropy and mutual information based on

2

Y. Kohara and K. Yanai

visual features extracted from image regions. Moreover, the result of analysis in
this paper can be used in simultaneous recognition where we recognize a certain
object by a noun and the state of the object by an adjective further like “there
is a car and the color of the car is red”.
In the rest of this paper, we describe related work in Section 2. We explain
the overview in Section 3 and the detail of the proposed system in Section 4. We
show experimental results in Section 5. In Section 6, we conclude this paper.

2

Related work

In the community of object recognition, recently, recognition of attributes ofobjects such as adjectives are paid attention to. In this paper, we are inspired by
the current trends of the object recognition research, and focus on “attributes”
in the tags of social media photos.
T. L. Berg et al.[1] focused on attributes on color, shape, and texture. They
extracted words associated with the attributes from the texts which were listed
in the shopping site, and labeled local regions represented by attributes corresponding text description.
D. Parikh et al.[2] focused on the attributes from the perspective of “nameable”. “Nameable” means whether human can understand and represent attributes automatically extracted from images by language. They discovered attributes of “nameable” by an interactive approach by using Amazon MechanicalTurk.
A. Farhadi et al.[3] described images by a set of attributes. They recognized
not only “dog” but “spotty dog”. By using attributes, we are able to describe“dog” which has “spots” as “spotty dog”, when we have no knowledge about thesubordinate categories of “dog”. In addition, it has become possible to mention
also distinctive attributes by using this description. That is, if attributes which“dog” has but “sheep “does not have exists, they will be the attributes which
discriminate a dog from a sheep. Moreover, discovering distinctive attributes
enables us to mention the attributes which should exist or shouldn’t exist ineach of the given classes. Therefore, a car whose doors are not visible can berecognized as a car with doors. In addition, they also estimated bounding box
regions to which the given attributes correspond.
S. Dhar et al.[4] focused on the particular attributes of aesthetics and interestingness. They dealt with two types of attributes about composition andcontents of objects in a given image as a guideline of aesthetics and interestingness. The attribute of composition contains saliency, location, and color of
objects. The attributes of contents contain type, place, and scene where objects
are shown. In this research, they mainly focused on subjective attributes.
The paper [1, 2] recognized a single attribute, and the paper [3] dealt withattributes as parts which should exist in the corresponding objects like “a door
is a part of a car”, while we limit attributes to only adjectives, and also focus
on the relationship between nouns and adjectives. The paper [4] analyzed theVisual Analysis of Tag Co-occurrence on Nouns and Adjectives

3

speciﬁc adjectives such as aesthetics and interestingness, while we dealt withmore general adjective.
Next, we introduce related works on visual concept analysis. Here, we cite
the papers of Yanai et al. [5], Akima et al. [6], and Kawakubo et al. [7]. Yanai
et al. proposed the entropy as a way to quantify the relation of visual concept,
and referred to the visual relation about 150 adjectives [5]. We use the methodof quantifying the visualness of the word by entropy and calculation of entropy.
Akima et al. built a database with hierarchical structure of between concepts
from distance relationship and hierarchical relationship [6]. They used entropy
and calculate the distribution of the images to determine the hierarchical relationship. In addition, tag information which is given to the images was also
used. Kawakubo et al. analyzed the visual and geographical distribution in word
concepts [7]. In this research, they calculated the image distribution of the classof concepts such as a noun or an adjective to evaluate visualness by using calculation of entropy and region segmentation. The diﬀerence between this researchand the above-mentioned works is that we deﬁne concept classes with the combinations of two words, and pursuit the visual relation of the combinations ofnouns and adjectives.

3

Overview

In this paper, the visual relationship between a nouns and an adjective is evaluated by the distribution of the image features of the corresponding image regions.
We judge that there is a high relation if visual distribution is narrow enough. The
extent of the distribution is quantiﬁed using the concept of entropy. Entropy isused to calculate the local features obtained from a set of image regions. Mutual
information is the diﬀerence between entropy of a noun and entropy of combination with an adjective and the noun. Mutual information becomes higher, when
visual relation between a noun and an adjective becomes higher.
Processing procedure of the experiment in this paper is shown below.
¶
Procedure³

1. Image acquisition from the Flickr by tag-based search
2. Image segmentation
3. Feature extraction and creating BoF for each region
4. Positive region detection
5. Calculation of feature distribution in each positive region by PLSA
6. Calculation of entropy and mutual informationµ´

In this paper, we also calculated similarity by co-occurrence of tags by theNormalized Google Distance (NGD) for comparison with the visual relation byentropy.

44

Y. Kohara and K. Yanai

Proposed method

In this section, we describe the methods used in the experiment. In this experiment, we calculated the entropy to refer to visual relation between an adjective
and a noun. In addition, we calculated the similarity by co-occurrence of tags
for comparison.
4.1

Image acquisition

We collect 200 positive tagged images for each class by using the Flickr API.
At the time, we use AND-search with a noun word and an adjective word. In
addition, we prepare the 800 negative images which have neither of the tags.
Note that we collected only one image from the same Flickr contributor for one
query, since the same user tends to upload many near-duplicated photos, whichsometimes causes irrelevant bias on feature distribution.
4.2

Region segmentation

To select regions directly related to the given words and remove backgroundregions, we perform region segmentation with JSEG [8]. In the experiment, we
set the number of the maximum regions as 10, and carry out post-processing tounify relatively smaller regions into larger regions.
4.3

Feature extraction

As feature representation of each region, we use Bag-of-Features (BoF) [9] with
Color-SIFT [10].
At ﬁrst, we extract the Color-SIFT feature as local features. To extract ColorSIFT, we extract the SIFT [10] features from each of the color channels such
as R, G and B, regarding each keypoint, and create new feature vectors by
concatenating SIFT vectors of the three channels. Therefore, the dimension sizeof this feature vector is 128 × 3. When extracting Color-SIFT features, we use
dense sampling where all the local features are extracted from multi-scale grids.
Bag-of-Features (BoF) [9] is a standard feature representation to convert a setof local features into one feature vector. To convert a set of local feature vectors
into a BoF vector, we vector-quantize them against the pre-speciﬁed codebook.
After that, all the BoF vectors are L1-normalized. In the experiments, we built
a 1000-dim codebook by k-means clustering with local features sampled from all
the images. Note that we construct a BoF vector for each region by using the
local features extracted inside the corresponding region.
4.4

Positive region selection

To select positive regions with the region-based BoF vectors, we use mi-SVM [11]which is a method of multiple instance learning. The mi-SVM is a support vector

Visual Analysis of Tag Co-occurrence on Nouns and Adjectives

5machine modiﬁed for multiple instance setting, and it is carried out by iteratinga training step and a classiﬁcation step using a standard SVM.
Under the multiple instance setting, training class labels are associated witha set of instances instead of individual instances. A positive set, which is called
as a ”positive bag”, has one positive instance at least, while a negative set,
which is called as a ”negative bag”, has only negative instances. This multiple instance setting ﬁts well with the situation where an image consists ofseveral foreground regions and background regions. Since we can regard foreground and background regions as positive and negative instances, respectively,by using multiple-instance learning methods we can classify regions into either
foregrounds or backgrounds without explicit knowledge on foregrounds.
The process of positive region selection is shown below.
¶³
The process of positive region selection
1. Initially, regard all the regions in the positive images as positive instances, and regard all the regions in the negative images as negative
instances.
2. Train a standard SVM using the positive and negative instances.
3. Classify all the instances in the positive images with the trained SVM.
4. Regard the instances assigned the higher scores by the SVM as positive
instances in the next step, and regard the instances having the lower
scores as negative instances in the next step.
5. Repeat from 2 through 4 several times.
µ´
4.5

Calculation of feature distribution

To calculate the feature distribution, we perform probabilistic clustering of feature vectors using the Probabilistic Latent Semantic Analysis (PLSA) [12].
pLSA The calculation of pLSA is performed as follows: First, the joint probability of an image and an element of the BoF vector, which corresponds to“visual words”, are represented as
P (di , wj ) =K∑

P (di |zk )P (wj |zk )P (zk )

(1)

k=1

where di (i = 1, 2, . . . , I) is an image, wj (j = 1, 2, . . . , J) is an element of BoF
feature vectors (visual word frequency), and zk (k = 1, 2, . . . , K) is a latent topic
variable. Then, the probability that the word will be generated within the document is given by
P (wj |di ) =

K
∑
k=1

P (wj |zk )P (zk |di )

(2)

6

Y. Kohara and K. Yanai

using latent topic variable zk . In addition, if the number of the word wj within the
document di is deﬁned as n(di , wj ), the log-likelihood of the data is represented
as the following expression:
L=

I ∑
J
∑

n(di , wj ) log P (di , wj )(3)

i=1 j=1

We determine P (zk )，P (di |zk )，and P (wj |di ) such as to maximize this loglikelihood by the iterative EM algorithm.

4.6

Calculation of entropy and mutual information

The entropy was calculated using the probability obtained by the pLSA. The
value of the entropy increases, when the distribution of the BoF feature vectors
corresponding to the positive regions becomes wider. On the other hand, theentropy value decreases, when the distribution becomes narrower. Therefore,
the value of the entropy represents the size of the image distribution belonging
to a given class concept which is the combination of a noun and an adjective.
That is, calculating the entropy leads to searching for visual relation on the
combinations of nouns and adjectives.
We calculate the entropy based on P (zk |di ) which is estimated by pLSA.
First, we calculate the probability of zk over a given concept X by:∑
P (zk |X) =di ∈X P (zk |di )

|X|

,

(4)

where X represents a set of the images corresponding to a given concept, foreach latent topic variable. Then, we calculate the entropy of a given concept X
byH(X) = −K∑

P (zk |X) log P (zk |X).

(5)

k=1

The mutual information is a value represented by the diﬀerence between theentropy and the conditional entropy, which indicates the relevance between thetags. We calculate the mutual information as
M I(X; Y ) = H(X) − H(X|Y ),(6)

where H(X) is the entropy of one class, and H(X|Y ) is the entropy of the classcombined two classes. If image distribution becomes narrow by combining the
tag X with the tag Y, we judge the visual relevance become higher from theincrease of mutual information.

Visual Analysis of Tag Co-occurrence on Nouns and Adjectives

7

Table 1. The 20 nouns used in experiment Table 2. The 15 adjectives used in experimentbeach bird boat bridge car
redblue green
black white
cat cloud cup
dog ﬂower
circle square morning night winterfruit house people sea
sky
summer new
old beautiful coolsnow sun tower train tree

4.7

Calculation of similarity by co-occurrence of tags

For comparison, we calculate similarity by co-occurrence of tags using the Normalized Google Distance (NGD) [13] as well. The formula is
N GD =

max {log f (x), log f (y)} − log f (x, y),
log N − min {log f (x), log f (y)}(7)

where x is a noun, y is an adjective, f (x) and f (y) are the image number of tag
search by a noun and an adjective in Flickr, and f (x, y) is the image numberof AND-search by combination of a noun and an adjective. Moreover, N is thenumber of all images in Flickr. However, we assume N is 50 billion since it isunable to get to know the exact number.

5

Experiments

5.1

DatasetImages were collected using the API from Flickr. We collected 800 negative
images and 200 positive images under the restriction that we obtained only one
image from the same uploader. In addition, we retrieved positive images in orderfrom the top in the search ranking of Flickr. Negative images were selected fromamong the images obtained at random from Flickr, which does not have the tagsof nouns and adjectives of a particular class. In this experiment, we selected 20
nouns as shown in Table 1, and 15 adjectives as shown in Table 2. Thus, we
calculate the entropy about 20 × 15 classes which are the combination of eachnoun and each adjective, as well as 20 classes which are only noun.
5.2

Experimental results

According to the procedure explained in the previous section, we calculated mutual information for each class. Figure 1 shows calculation result of the entropy
values in the second columns and the mutual information values after the thirdcolumns. On the other hand, Figure 2 shows the calculated results on the similarity of NGD using tag co-occurrence. We summarized the combinations of nouns
and adjectives which are judged to have high relation by mutual information
values in Table 3 and by NGD in Table 4, respectively.
With these experimental results, we compare mutual information of eachclass. Mutual information decreases when the distribution of images in each class

8

Y. Kohara and K. Yanai

Fig. 1. Calculation result of mutual information (red: high relevance class, blue: low
relevance class)Fig. 2. Calculation result of co-occurrence of tags by NGD (red: high relevance class,blue: low relevance class)spreads, and increases when the distribution of images in each class is narrow.
Then, we can judge that the classes which have amount of mutual information
have high visual relation between nouns and adjectives. Moreover, we determine
the classes which have small NGD have high visual relation between nouns andadjectives.
5.3

Discussion on visual relationsFirst, we discovered the tendency that the mutual information becomes large inthe class where a lot of images have been greatly aﬀected by color (see Figure 3).
For example, “morning sea”, “morning sky”, and “blue bridge” class would becited. Looking at the positive region of the image to be included in the “morningsky” class, there are the regions which have a lot of red region of the morning
glow and blue region of the sunny sky. We consider that image distribution inVisual Analysis of Tag Co-occurrence on Nouns and Adjectives

9

Table 3. Main classes of high similarity by Table 4. Main classes of high similarity byco-occurrence of tag
mutual information
sea+morning sky+morning
sun+redsky+night
sun+beautiful
car+redﬂower+blue sun+circle

snow+winter sky+blue
tree+green ﬂower+green
sea+blue sun+beautiful
ﬂower+red
sun+blueFig. 3. Positive regions in the class where Fig. 4. Positive regions in the class combined with an adjective about color
the color inﬂuenced greatly

these classes becomes narrow, and their mutual information increases for thatreason. However, visual relevance in “blue bridge” class becomes high, although
the class has few images of a blue bridge. We consider that visual relevanceincreases, because the positive regions include blue of sea, river, and sky aroundbridge in order to take the entire bridge in the photos.
Next, when we pay attention about the class in combination with the adjective about a color, it turns out that mutual information becomes relatively
larger in the class where the adjective about color qualiﬁes directly to the object
being indicated by the noun (see Figure 4). We would mention “red sun” and“red car” class as examples of large mutual information, and “red cat” and “reddog” class as examples of small mutual information in the class which combinedwith the adjective about a color. In such classes where mutual information isgreater, and positive regions of that class contains the particular color and object. Whereas, in the class where mutual information is smaller, positive regionsof that class do not contain the particular color and object. Therefore, it can bethought that visual relation has been correctly calculated, which is consistent
with our intuition.

5.4

Comparison with tag co-occurrence

Some classes have high visual relevance while their co-occurrence relevance by
tag is low (see Figure 5). As an example, we cite “old people” class. Both visual
relevance and relevance by tag are low in the class combined with the “old”.
However, there is a tendency that visual relevance of “old” becomes higher thanother classes, when it combined with the noun in connection with artiﬁcial thingsand living things such as “house” and “people”.

10

Y. Kohara and K. Yanai

Fig. 5. Positive regions of the class which Fig. 6. Positive regions of the class which
the relevance of co-occurrence is low, and the relevance of co-occurrence is high, andvisual relevance is highvisual relevance is low

On the other hand, there are classes which have low visual relation, although
their relation by tag is high (see Figure 6). As an example, we cite “summer
beach” and “green sky” class. It is thought that visual relation became low in“summer beach” class, because there are not only the image of a beach but many
images of the people who are doing sea bathing. Meanwhile, it is thought thatthe relation by tag became high in “green sky” class, because the “green sky”
class contains many images of grass, and the co-occurrence of “sky” and “grass”
the color of which is green is higher. However, their visual relation is shown as
being low.

6

Conclusion and Future work

In this paper, ﬁrst, we collected images tagged with both particular nouns andadjectives from Flickr. Then, we extracted local features from images, and calculated the distribution of image as the numeric value by the entropy. Finally,
we performed comparison and consideration about the visual relation between anoun and an adjective from the change in entropy for each class which combineda noun and an adjective.
As a result, we obtained the results that on mutual information represents
intuitive visual similarity. Therefore, it turned out that there was a tendency thatthe pairs of nouns and adjectives related to color have the stronger visual relation.
Regarding tag-based similarity, the degree of similarity by the co-occurrence oftag using NGD showed the results which ﬁtted our intuition as well.
For future work, we plan to use other kinds of visual features than ColorSIFT BoF. In addition, we would like to utilize the results obtained in this paper
to improve performance on simultaneous recognition of a noun and an adjective.

Visual Analysis of Tag Co-occurrence on Nouns and Adjectives

11

References
1. T. L. Berg, A. C. Berg, and A. J. Shih. Automatic attribute discovery and characterization from noisy web data. In Proc. of European Conference on Computer
Vision, pp. 663–676, 2010.
2. D. Parikh and K. Grauman. Interactively building a discriminative vocabulary of
nameable attributes. In Proc. of IEEE Computer Vision and Pattern Recognition,
2011.
3. A. Farhadi, I. Endres, D. Hoiem, and D. Forsyth. Describing objects by their
attributes. In Proc. of IEEE Computer Vision and Pattern Recognition, pp. 1778–
1785, 2009.
4. S. Dhar, V. Ordonez, and T.L. Berg. High level describable attributes for predicting
aesthetics and interestingness. In Proc. of IEEE Computer Vision and Pattern
Recognition, pp. 1657–1664, 2011.
5. K. Yanai and K. Barnard. Image region entropy: A measure of “visualness” of web
images associated with one concept. In Proc. of ACM International Conference
Multimedia, 2005.
6. H. Kawakubo, Y. Akima, and K. Yanai. Automatic construction of a folksonomybased visual ontology. In Proc. of International Symposium on Multimedia, pp.
330–335, 2010.
7. K. Yanai, H. Kawakubo, and B. Qiu. A visual analysis of the relationship between
word concepts and geographical locations. In Proceedings of the ACM International
Conference on Image and Video Retrieval, 2009.
8. Y. Deng and B. S. Manjunath. Unsupervised segmentation of color-texture regions in images and video. IEEE Transactions on Pattern Analysis and MachineIntelligence, Vol. 23, No. 8, pp. 800–810, 2001.
9. G. Csurka, C. Bray, C. Dance, and L. Fan. Visual categorization with bags of keypoints. In Proc. of ECCV Workshop on Statistical Learning in Computer Vision,
pp. 59–74, 2004.
10. D. G. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, Vol. 60, No. 2, pp. 91–110, 2004.
11. S. Andrews, I. Tsochantaridis, and T. Hofmann. Support Vector Machines forMultiple-Instance Learning. In Advances in Neural Information Processing Systems, pp. 577–584, 2003.
12. T. Hofmann. Unsupervised learning by probabilistic latent semantic analysis. Machine Learning, Vol. 43, pp. 177–196, 2001.
13. R.L. Cilibrasi and P.M.B. vitanyi. The google similarity distance. IEEE Transactions on Knowledge and Data Engineering, Vol. 19, No. 3, pp. 370–383, 2007.