# Automatic Image Tagging Model Based on Multigrid Image Segmentation and Object Recognition

Authors: Woogyoung Jun; Yillbyung Lee; Byoung-Min Jun
Journal: Advances in Multimedia
 (2014)

---

## Abstract

Since rapid growth of Internet technologies and mobile devices, multimedia data such as images and videos are explosively growing on the Internet. Managing large scale multimedia data with correct tags and annotations is very important task. Incorrect tags and annotations make it hard to manage multimedia data. Accurate tags and annotation ease management of multimedia data and give high quality retrieve results. Fully manual image tagging which is tagged by user will be most accurate tags when the user tags correct information. Nevertheless, most of users do not make effort on task of tagging. Therefore, we suffer from lots of noisy tags. Best solution for accurate image tagging is to tag image automatically. Robust automatic image tagging models are proposed by many researchers and it is still most interesting research field these days. Since there are still lots of limitations in automatic image tagging models, we propose efficient automatic image tagging model using multigrid based image segmentation and feature extraction method. Our model can improve the object descriptions of images and image regions. Our method is tested with Corel dataset and the result showed that our model performance is efficient and effective compared to other models.


---

## Body

## 1. Introduction

Nowadays, we are always online. Desktop computers, laptop computers, and even smartphones are connected online anytime and anywhere. It is very easy to share multimedia data with our mobile devices and explosive growth of social network services such as Facebook, Flickr, and Twitter helps with tremendous growth of multimedia data on the Internet. To manage these multimedia data, reliable tag and annotation information should be improved. How to manage such large scale of multimedia is the most famous topic these days. Well-tagged image is effective for management and retrieval. We focus on automatic image tagging model using image segmentation and feature extraction. Since an image presents multiple objects on single image, we mainly focus on how to extract multiple objects successfully. We find out image segmentation technique and propose a multigrid based image segmentation method. Sometimes an image may contain single object but most of user created contents contain multiple objects in image (Figure1). Therefore, extracting visual features from whole image has limitation for tagging or annotating an image. Feng et al. [1] also proposed grid based method which is more effective than the basic image segmentation models. But it still has limitation for multiobject problem in segmented region. Therefore, we propose a multigrid image segmentation method which is able to extract features of multiobjects presented in an image. Experimental results showed that our model presented efficient, effective, and most accurate image tagging results compared to other models.An example of images: an image contains single object (a) and an image contains multiobjects (b).
(a)
(b)We present related researches in Section2 and propose our multigrid image segmentation model in Section 3. In Section 4, we present our novel automatic image tagging model based on multigrid image segmentation method. We present experimental results in Section 5. Finally, we reach to conclusions and feature works in Section 6.


## 2. Related Researches

Typically there are three types of image tagging models. Those are automatic, manual, and half-automatic models. Manual tagging is most accurate and reliable for image tags. Nevertheless, it takes tremendous cost to tag image manually. Half-automatic models such as Google Image Labeler are good way to tag image pretty accurate, but it also has limitation that users have to spend time in playing game and it might cause suffering from noise tags. Therefore, fully automatic image tagging model is most interesting research field in these days despite of lower performance compared to manual and half-automatic models. Many researchers make effort to increase accuracy.Learning based automatic image tagging models are most recent research interests. Starting keyword based methods, semantic keyword methods are proposed. Most recently, for more effective image tagging, setting up the relationship between textual features and visual features is currently the main topic. Jeon et al. [2] and Yang et al. [3] proposed cross media model which tags images with joint probabilities of semantic information and visual features. They used discrete features to tag images and it can lose helpful visual information. Carneiro et al. [4] proposed SML model which is semisupervised learning model which is not suitable for image segmentation. Wang et al. [5] combined global and local regions and, to improve tagging performance, they used contextual features. Lindstaedt et al. [6] proposed visual folksonomy based automatic image tagging especially for fruits and vegetables. In addition, Manh and Lee [7] focus on small object segmentation based on visual saliency in natural images and Divya et al. [8], Santosh and Shyam [9], and Patil and Kokare [10] demonstrated that image segmentation and automatic image tagging models help with semantic image retrieval.Unlike these algorithms, our model focused on efficient and effective multigrid based image segmentation model and object recognition. And we propose an image tagging model based on our multigrid image segmentation method (Figure2). Our proposal for multigrid based image segmentation and object recognition is shown in next section and then we propose efficient automatic image tagging model.Figure 2
Overview of our grid based image segmentation, feature extraction, and automatic image tagging model.


## 3. Image Segmentation Model

Most of image region segmentation depends on surrounding contrast. Cheng et al. [11] proposed global contrast-based region detection algorithm. For image segmentation, Felzenszwalb and Huttenlocher [12] proposed graph-based image segmentation method, and Xiong et al. [13] proposed hierarchical deformable model for face detection. And color contrast for each image region is being calculated. In this paper, we calculate weight for each region for image region segmentation.LetDr(r1,r2) be the distance between image regions r1 and r2; then Dr(r1,r2) can be calculated as follows:
(1)Drr1,r2=∑i=1n1∑j=1n2fc1,ifc2,jDc1,i,c2,j,
where f(c1,i) is probability of color c1,i on image region r1 and f(c2,j) is probability of color c2,j on image region r2. Distance between c1,i on region r1 and c2,i on region r2  Dc1,i,c2,j is distance between the two pixels. It takes long time to calculate whole color distance because Lab color space is 2553. Therefore, we used histogram based compress Lab color space. Therefore, we can recalculate Dr(r1,r2) as follows:
(2)Drr1,r2=∑m=1nB∑n=1nBfbmfbnDbm,bn,
where bm is mth bin of color c1,i in region r1 and bn is nth bin of color c2,j in region r2. nB is number of histogram bins. Now we can calculate f(b*) as follows:
(3)fb*=#(b*)N(rk),
where #(b*) is number of bin colors b* and N(rk) denotes number of pixels in region rk·f(b*). If the pixel of certain color appears many times, it means that it is main color of certain region. If we calculate directly f(b*) within (3), then similar color may be assigned to another bin and especially it can be noise when the region is small. To overcome such problem, we redefine (3) as follows:
(4)f′b*=∑i=1lZ-Db*,bi#(b*)l-1ZN(rk),
where l is the number of similar colors with b* in histogram. D(b*,bi) is distance between b* and the ith similar color of b*. Z and (l-1)Z are normalized factor and Z-D(b*,bi) is linear transformed weight. Now we calculate weight for certain region by comparing with other regions. We calculate region importance rh as follows:
(5)Irh=∑rh≠riw(ri)Dr(rh,ri).Dr(rh,ri) can be calculated with (2). w(ri) denotes number of pixels in region ri and it can be weight of region ri as well. Since (5) does not concern spatial relationship, we recalculate (5) with spatial relationship as follows:
(6)Irh=∑rh≠riexp⁡⁡-Dsrh,riσs2w(ri)Dr(rh,ri),
where Ds(rh,ri) denotes spatial distance between regions rh and ri. Ds(rh,ri) is calculated using Euclidean distance measure. σs is used to control spatial weight.Now we propose method to segment image into multigrid to recognize objects. We segment images based on multigrid based image segmentation method. And then we extract object feature as already mentioned. Finally, we extract visual feature from each segmented image. Since we extract visual features from multigrid segmented images, we can extract most objects in image. In this paper, we segment images into 3 steps. In first step, we extract feature from entitled image. In second step, we extract features from 2 by 2 grid segmented images. In third step, we extract features from 3 by 3 grid segmented image. The number of steps increases more than 3 by 3 grid; then the well-extracted number of objects (Figure3) and accuracy (Figure 4) decrease.Figure 3
Number of well-extracted objects for segmentation steps.Figure 4
Accuracy of well-extracted objects for segmentation steps.Number of well-extracted objects and their accuracy show best result on step 3. That is, smaller objects in images are not that important in that image and more important object can be segmented into other regions which means important object feature can be lost.We can see an object extracted from segmented images (Figure5). When we extract feature from entitled image, only one object is extracted. When we extract features from 2 by 2 segmented images, we could recognize more detailed objects in images. Meanwhile, we could recognize more detailed objects in 3 by 3 segmented images.Figure 5
An illustration of objects extracted from segmented region.


## 4. Automatic Image Tagging Model

In this section, we introduce our automatic image tagging model. We combine with our multiscale segmented images introduced in Section3. Visual features extracted from each region are single object of segmented regions.For all input imageI, I is segmented into 3 by 3 grid. Let us say N is the number of segmented image regions. We extractd-dimensional feature vector Fi from each region ri. And we define visual generation probability PF~∣I. We used Multiple Bernoulli Distribution [12] to calculate visual general probability. U is unlabeled image and FU is feature vector of U. WL is subset of tag label. P(FU,WL) is similarity between FU and WL. The process of jointly generating FU and WL is as follows:(1)
select an imageI from training set with Pr(I);(2)
obtain segmented image regions;(3)
for each training imageI, i=1,…,N;(4)
generate visual descriptions fromith region by using conditional probability;(5)
for each wordv is in tag set;(6)
generate tag set by using Multiple Bernoulli Distribution;(7)
using (7), calculate joint probability of visual description and labels in our model:
(7)PFU,WL=∑I∈rPr(I)×∏i=1NPFFUi∣I×∏v∈WLPVv∣I∏v/∈WL1-PVv∣I×∏v/∈WL1-PVv∣I.In (7), Pr(I) is the probability of image I from training set. Since there is no prior knowledge, Pr(I) can be assumed to obey uniform distribution:
(8)PrI=1r,
where r is the size of training image set.ProbabilityPF~∣I is used to estimate visual generation probability of regions. Assume FI is visual features of regions in 3 by 3 segmentation; PF~∣I can be calculated as follows:
(9)PFFUi∣I=1N∑j=1Nexp⁡⁡-FUi-FIjT∑-1FUi-FIj2dπd∑,
where N is the number of image regions and d is the dimension of visual features. Equation (9) uses Gaussian kernel function to estimate the visual description FIj of each region in image I. Gaussian kernel is determined by covariance matrix ∑=μ·I.P
V
v
∣
I is vth component of Multiple Bernoulli Distribution. It means that probability of tag set WL which is generated by training image I. Bayesian estimation is used for each tag label as follows:
(10)PVv∣I=ε·∅v,I+Lvε+r,
where Lv is the number of labels v in training set and r is the size of training image set. ∅v,I is a binary function (if I contains label then 1, else 0). ε is parameter of weight ∅v,I.


## 5. Experiments

To evaluate our automatic image tagging model based on multigrid image segmentation, we compare our model with other models using Corel dataset. Corel dataset is a popular dataset in automatic image tagging, which includes over 5,000 images. This section focuses on how to construct an effective automatic image tagging model. For the convenience of comparing with other models, we do not use some new visual features. We use the same 30-dimensional features including 9-dimensional RGB color moments, 9-dimensional Lab color moments, and 12-dimensional Gabor texture features. To evaluate other automatic image tagging models, we use precision, recall, andF-measure to evaluate tagging results (Figure 6). In addition, we also count the labels that are correctly tagged at least once, denoted as NZR which reflects the coverage level of annotation words.Figure 6
Parameter determination, tag results onl.We need to determine the parameter value ofl in (4) according to experiments. l is the number of similar bins in histogram. Horizontal coordinate axis means the ratio of similar color bins in histogram (Figure 4). We can find out optimal parameter value for best annotation results when the ratio of similar color bins is 20%. Precisions and recalls of annotation results would fall if l increases, because higher l will reduce the region contrast, and then feature extracted image regions would be affected to some degrees.To improve performance of our multigrid image segmentation method, we compared with current methods introduced in Section2 which are global contrast based salient region detection method [11], graph-based image segmentation [12], and hierarchical deformable model [13]. Experimental result demonstrates accuracy for each method and our method shows best performance compared to other methods (Figure 7).Figure 7
Accuracy comparison result of various image segmentation methods.Meanwhile, we evaluate our model with other image segmentation methods with precision, recall,F-measure, and NZR (Table 1).Table 1
Experimental results of image segmentation method comparison.
Models
Precision
Recall
F-measure
NZR
Global contrast based salient region detection
0.21
0.12
0.12
57
Graph-based image segmentation
0.26
0.31
0.27
117
Hierarchical deformable model
0.26
0.32
0.28
123
Multigrid image segmentation
0.29
0.32
0.30
151Finally, we present our automatic image tagging model performance. We compared our model with some state-of-the-art models, including Cross Media Relevance Model [2, 3], Multiple Bernoulli Relevance Model [1], Transductive Multi-Instance Multilabel [14], and Supervised Learning Model [4]. We can find that our model is very effective and tagging results are better than those state-of-the-art models (Table 2). Our model obtained the highest precision 0.27 which is at least 12% higher than other models. Recall achieves 0.29 which is the same as Supervised Learning Model and the recall is higher than other models obviously. F-measure of our model achieves 0.28, and it is approximately 8% higher than Supervised Learning Model which obtained the highest F-measure in previous state-of-the-art models. In addition, in criterion of NZR which reflects the coverage of annotation words, our model reaches 144 and it is also the highest in all models.Table 2
Experimental results.
Models
Precision
Recall
F-measure
NZR
Cross Media Relevance Model
0.10
0.09
0.09
66
Multiple Bernoulli Relevance Model
0.24
0.25
0.24
122
Transductive Multi-Instance Multilabel
0.23
0.27
0.25
130
Supervised Learning Model
0.23
0.29
0.26
137
Our model
0.27
0.29
0.28
144We compare our model with MBRM model, and the rankings of tagging labels are sorted in descending order with tagging probability (Table3). If labels are in ground truths, we use bold type. Here, we do not select test images that are perfectly tagged by our model. We can easily find that tagging results of our model show better performance than MBRM model. In addition, we also find that some tag words do not appear in ground truth annotations of the dataset, but some of these words can also describe the contents of images. That is, some correct tags are ignored by users. These labels are in italic type. For example,clouds,water, andsky do not belong to the ground truth in first image, but these labels can be used to describe the contents of first image without question. Besides, some labels in other images also have the similar situations.Table 3
Tag results.
Images
Ground truth
Multiple Bernoulli Relevance Model
Our model
Beach palm people tree
Cloud stone ruins pyramid sky
Palm  beach  cloud water sky
Blooms cactus flower needle
Grass  flower  petal water sky
Flower  grass  petal  bloom  sand
Flower garden house tree
Water bird nestsky  grass
Tree  sky  house  grass stone
Bird nest tree
Flowerleaf  plant  tree sky
Bird  tree  leaf  plant  grass


## 6. Conclusions

In this paper, we proposed multigrid image segmentation method. And then we also proposed an automatic image tagging model based on our multigrid image segmentation method. Since segmented image may contain multiple objects, we proposed multigrid image segmentation method. Our model presented high performance compared to other image segmentation methods. With experimental results on automatic image tagging models, our image tagging model showed better performance compared to other state-of-the-art models especially on object feature extraction. To evaluate our proposed multigrid image segmentation method, we compared with other image segmentation methods and to evaluate our automatic image tagging model, we used Corel dataset and compared with other famous models: Cross Media Relevance Model, Multiple Bernoulli Relevance Model, Transductive Multi-Instance Multilabel, and Supervised Learning Model. Our model showed efficient, effective, and accurate performance in all evaluated functions precision, recall,F-measure, and NZR.Since there are limitations and many works to do, and multimedia data is growing even in this moment, more powerful, reliable, and accurate models must be prevented. With large amount of data being created every moment, we also need to focus on real time automatic annotation model.



---

*Source: 857682-2014-12-22.xml*