A Locality Sensitive Low-Rank Model for Image Tag Completion

A Locality Sensitive Low-Rank Model for Image Tag Completion

Abstract

Many visual applications have benefited from the outburst of web images, yet the imprecise and incomplete tags arbitrarily provided by users, as the thorn of the rose, may hamper the performance of retrieval or indexing systems relying on such data. In this paper, we propose a novel locality sensitive low-rank model for image tag completion, which approximates the global nonlinear model with a collection of local linear models. To effectively infuse the idea of locality sensitivity, a simple and effective pre-processing module is designed to learn suitable representation for data partition, and a global consensus regularizer is introduced to mitigate the risk of overfitting. Meanwhile, low-rank matrix factorization is employed as local models, where the local geometry structures are preserved for the low-dimensional representation of both tags and samples. Extensive empirical evaluations conducted on three datasets demonstrate the effectiveness and efficiency of the proposed method, where our method outperforms pervious ones by a large margin.

Existing System

The user-labeled visual data, such as images which are uploaded and shared in Flickr, are usually associated with imprecise and incomplete tags. This will pose threats to the retrieval or indexing of these images, causing them difficult to be accessed by users. Unfortunately, missing label is inevitable in the manual labeling phase, since it is infeasible for users to label every related word and avoid all possible confusions, due to the existence of synonyms and user preference. Therefore, image tag completion or refinement has emerged as a hot issue in the multimedia community.Many visual applications have benefited from the outburst of web images, yet the imprecise and incomplete tags arbitrarily provided by users, as the thorn of the rose, may hamper the performance of retrieval or indexing systems relying on such data.

Disadvantages

·        image tag completion or refinement has emerged as a hot issue in the multimedia community.

·        The existing completion methods are usually founded on linear assumptions, hence the obtained models are limited due to their incapability to capture complex correlation patterns.

Proposed System

To effectively infuse the idea of locality sensitivity, a simple and effective pre-processing module is designed to learn suitable representation for data partition, and a global consensus regularizer is introduced to mitigate the risk of overfitting. Meanwhile, low-rank matrix factorization is employed as local models, where the local geometry structures are preserved for the low-dimensional representation of both tags and samples. Extensive empirical evaluations conducted on three datasets demonstrate the effectiveness and efficiency of the proposed method, where our method outperforms pervious ones by a large margin.

Advantages

·        We propose a locality sensitive low-rank model for image tag completion, which approximates the global nonlinear model with a collection of local linear models, by which complex correlation structures can be captured.

·        Several adaptations are introduced to enable the fusion of locality sensitivity and low-rank factorization, including a simple and effective pre-processing module and a global consensus regularizer to mitigate the risk of overfitting.

MODULE DESCRIPTION

The module are:

1.     Locality Sensitive Module

2.     Pre-Processing and Data Partition

3.     Related Tag Module

4.     Automatic image Annotation

Locality Sensitive Module

Assume we are given n partially labeled images,whose visual feature matrix and initial tag matrix is denoted as X ∈ Rn×d and D ∈ Rn×m, respectively, where d is the dimension of visual feature, and m is the size of our vocabulary. Our goal for tag completion is to recover the complete tag matrix Y . The proposed method achieves this via several modules, including pre-processing, data partition, and the learning of local models. As sketched in Fig. 1(a), the low-dimensional representation is learnt for each sample in the phase of pre-processing. Based on this novel representation, all the images in the dataset are divided into multiple groups, so that samples within the same group are semantically related.

Pre-Processing and Data Partition

This section introduces two closely related modules: preprocessing and data partition. As mentioned in Section III-A, the goal of data partition is to divide the entire sample space into a collection of local neighborhoods or groups, such that samples within each group are semantically related. However, as we observed in our experiments, direct partitions usually fail to generate meaningful groups, regardless of using visual features or incomplete initial tags. The reason behind is easy to understand. For instance, images depicting people may be divided into the clusters concerning beach or building according to their backgrounds, especially when people is missing. On the other hand, despite actually describing different contents such as bear, fox or mountain, samples initially labeled as snow may be grouped into the same cluster about snow, since distance is distorted when their foreground tags are absent.

Related Tag Module

In the scenario of image tag completion, all the images are assumed to be partially labeled, for instance an image whose true labels are {c1, c2, c3} may only be labeled as {c2}, while c1 and c3 are missing. The goal of image tag completion is to accurately recover the missing labels for all the images. A plethora of algorithms have been developed to address this issue, among which many researchers explore the insight that related tags are often concurrent with each other, and images depicting similar contents tend to have related tags. However, existing completion methods are usually founded on linear assumptions, hence the obtained models are limited due to their incapability to capture complex correlation patterns.

Automatic image Annotation

Given an unlabeled image, the goal of image annotation is to identify its contents and label it with an appropriate number of tags. Numerous methods have been proposed in this area, including mixture models such as MBRM , SML , topic models such as mmLDA, cLDA , tr-mmLDA , discriminative methods , and label-transfer schemes . Among them, state-of-the-art performance is reported by label-transfer methods. Specifically, JEC adopted equal weights for each feature and transferred labels in a greedy manner. TagProp [9] embedded metric learning to learn more discriminative weights. 2PKNN extended LMNN  into a multi-label scenario and constructed semantic groups to boost annotation performance for rare tags.

System Requirements

H/W System Configuration:-

          Processor                                  -    Pentium –III

Speed                                        -    1.1 Ghz

RAM                                        -    256 MB(min)

Hard Disk                                -   20 GB

Key Board                               -    Standard Windows Keyboard

Mouse                                     -    Two or Three Button Mouse

Monitor                                    -    SVGA

 S/W System Configuration

v   Operating System            :Windows95/98/2000/XP

v   Application  Server         :   Tomcat5.0/6.X                                     

v   Front End                        :   HTML, Java, Jsp

v    Scripts                            :   JavaScript.

v   Server side Script           :   Java Server Pages.

v   Database Connectivity   :   Mysql.

Algorithm

BIRCH Algorithm

BIRCH (balanced iterative reducing and clustering using hierarchies) is an unsupervised data mining algorithm used to perform hierarchical clustering over particularly large data-sets.An advantage of BIRCH is its ability to incrementally and dynamically cluster incoming, multi-dimensional metric data points in an attempt to produce the best quality clustering for a given set of resources (memory and time constraints). In most cases, BIRCH only requires a single scan of the database.

Its inventors claim BIRCH to be the "first clustering algorithm proposed in the database area to handle 'noise' (data points that are not part of the underlying pattern) effectively", beating DBSCAN by two months. The algorithm received the SIGMOD 10 year test of time award in 2006.

Algorithm image

                

                 

Architecture Diagram