Browse Prior Art Database

Method and system for Classifying Images Using a Web Graph

IP.com Disclosure Number: IPCOM000200483D
Publication Date: 2010-Oct-15
Document File: 4 page(s) / 73K

Publishing Venue

The IP.com Prior Art Database

Related People

Malcolm Slaney: INVENTOR [+2]

Abstract

A method and system for classifying images is disclosed. The disclosed method exploits the link structure of a web graph to classify images.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Method and system for Classifying Images Using a Web Graph

Abstract

A method and system for classifying images is disclosed. The disclosed method exploits the link structure of a web graph to classify images.

Description

Disclosed is a method and system for classifying images using the link structure of a web graph.  The method includes, calculating for each image, pixel-based and text-based features that are concatenated into a vector taking into account an image’s position in the web graph (based on the directed edges E).  To classify the images, a large-margin linear classifier is used.  If there are N web pages, then l<N labeled nodes are defined and each label is denoted as with a value of either +1 or -1. A classifier w that predicts the correct label for each labeled point and minimizes the loss of the function is then calculated as:

where is a regularization parameter that sets the importance of using a small w and limits the complexity of the decision.  The function R(⋅) controls the effect of errors and is set to , where the operator is equal to max(0,x).

This model may be enhanced by learning an additional slack variable per node, .  The score function () for a page becomes and is minimized:

where z combines the elements of in to one vector.

Neighboring nodes, as determined by the web graph, are expected to have similar scores and hence a regularization is added as shown below:

where (i,j)∈E describes all web nodes that are connected, γ is another regularization parameter and is the number of links from node i to node j. Φ is a function that compares the scores from two different nodes.  There are two kinds of information flows, symmetric and asymmetric.  A simple choice for Φ is a squared loss term .  An asymmetric version looks like . These two conditions are blended with:  COMMENTS " \begin{equation}

\Phi({f_i,f_j}) = \alpha (f_i - f_j) ^ 2 +  (1-\alpha) \max (0, f_j - f_i) ^ 2 .

\end{equation}"

Then, the total cost function is then given by:

The classification algorithm described above has a single feature vector associated with each web page.  However, images (and other multimedia objects) are treated differently on the web.  Each image has a separate feature vector where as the web page does not have any features associated with it.  Thus, the classification algorithm presented above needs to be modified to allow handling web pages and their images in the same framework.

In order to handle multiple...