LEARNING STRUCTURED PREDICTION MODELS FOR INTERACTIVE IMAGE LABELING

• US 20120269436A1
• Filed: 04/20/2011
• Published: 10/25/2012
• Est. Priority Date: 04/20/2011
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mensink, Thomas, Verbeek, Jakob, Csurka, Gabriela
• Granted Patent: US 8,774,515 B2
• Time in Patent Office: Days
• US Class Current: 382/180
• CPC Class Codes: G06F 18/2431 Multiple classes
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 20/00 Scenes; Scene-specific elements control of digital cameras H04N23/60
• CPC Class Codes: G06V 30/244 using graphical properties, e.g. alphabet type or font

Abstract

A system and a method are provided for labeling images and for generating an annotation system. The labeling method includes providing a graphical structure, such as a tree structure, which graphically represents predictive correlations between labels in a set of labels. The predictive correlations can, for example, estimate the likelihood, in a training set, that knowing one label has a given value, another label will have a given value. An image to be labeled is received. Feature-based predictions for values of labels in the set of labels are computed for the image. A value for at least one label for the image from the set of labels is computed based on the feature-based label predictions and inference on the structured prediction model.

Claims

1. An annotation system comprising:

memory which stores;

a structured prediction model which represents predicted correlations between values assumed by labels in a set of labels;

instructions for;

generating feature-based predictions for values of labels in the set of labels based on features extracted from an image;

predicting a value for at least one label from the set of labels for the image based on the feature-based label predictions, and the structured prediction model, and, when the instructions include instructions for receiving an assigned value for at least one label from the set of labels for the image, the predicted value being also based on an assigned value for at least one other label, if one has been assigned; and

a processor for executing the instructions.

2. The system of claim 1, wherein the structured prediction model comprises at least one tree structure.

3. The system of claim 2, wherein in at least one of the tree structures, each of the labels in the set of labels is in exactly one node of the tree and edges between the nodes define those pairs of nodes for which predicted correlations between the values of pairs of their labels is used in the label prediction.

4. The system of claim 3, wherein the predicted correlations comprise pairwise potentials between label pairs, each pairwise potential representing a probability that a first label in the label pair which is on a first node connected by an edge to a second node has a given value from a set of values when a second label in the label pair which is on the second node has a given value from a set of values.

5. The system of claim 3, wherein in the at least one tree structure, nodes of the tree have at most a predefined number k of labels, and wherein a plurality of the nodes have more than one label.

6. The system of claim 5, wherein the predefined maximum number k is at least 2.

7. The system of claim 5, wherein the structured prediction model comprises a plurality of tree structures and the prediction is based on a weighted combination of the tree structures, each of the tree structures having a different predefined number k of labels.

8. The system of claim 3, wherein the labels are attribute labels and the system includes instructions for predicting a class of the image based on the predicted attribute label values.

9. The system of claim 3 wherein the system has a mode in which for an input image to be labeled, a plurality of the label values for the image are elicited from a user, and wherein the instructions for predicting the value for the at least one label for the input image are based on predictions using features extracted from the image which are modified by the predicted correlations of the graphical structure which propagates modified predictions on values of the labels provided by the user to other labels via the edges.

10. The system of claim 9, wherein a selection of at least one subsequent one of the plurality of label values to be elicited from a user is conditional on at least one previous one of the plurality of label values elicited from the user and the predicted correlations of the graphical structure.

11. The system of claim 10, wherein the selection of the at least one subsequent one of the plurality of label values includes selecting a label based on maximizing entropy computed over all the other labels or selecting a label which has a maximum computed marginal entropy.

12. The system of claim 3, wherein in every tree structure, each node has no more than one parent node and at least one of the nodes with a parent node has at least one child node.

13. The system of claim 1, wherein the instructions for receiving an assigned value for at least one label from the set of labels for the image comprises instructions for receiving at least one of:

an elicited label value; and

a preassigned label value.

14. The system of claim 1, further including a classifier which generates the predictions using features extracted from the image that are modified by the predictive correlations of the graphical structure.

15. The system of claim 1, wherein the system includes instructions for generating the graphical structure based on a training set of labeled images by a generative method which computes an optimal maximum spanning tree over a fully connected graph over the labels using mutual information on pairs of the labels estimated from the training set.

16. A method for labeling images comprising:

providing a structured prediction model in memory which represents predictive correlations between labels in a set of labels;

receiving an image to be labeled;

generating feature-based predictions for values of labels in the set of labels based on features extracted from the image; and

with a processor, predicting a value for at least one label from the set of labels for the image based on the feature-based label predictions and predictive correlations of the structured prediction model, and optionally based on an assigned label value for at least one other label.

17. The method of claim 16, wherein the structured prediction model comprises a tree structure and wherein in the tree structure, each of the labels in the set of labels is in exactly one node of the tree and edges between the nodes define pairs of nodes for which predicted correlations between values of pairs of labels is stored, the prediction of the value for the at least one label value being based on the predicted correlations.

18. The method of claim 17, further comprising computing a tree structure using a generative model.

19. The method of claim 17, wherein in the tree structure, nodes of the tree have at most a predefined number k of labels, and wherein a plurality of the nodes have more than one label.

20. The method of claim 19, wherein the graphical structure comprises a plurality of tree structures and the prediction comprises computing an optionally weighted combination of the predictions of the tree structures, each of the tree structures having a different predefined maximum number k of labels for its nodes.

21. The method of claim 17, wherein the assigned label value comprises elicited label values, the method further comprising, for the input image to be labeled, eliciting a plurality of the label values for the image from a user, and wherein the prediction of the value for the at least one label for the input image includes modifying at least one of the predicted correlations between values of the node which includes the label whose value has been elicited and at least those nodes linked by edges to that node based on the elicited value.

22. The method of claim 21, wherein the method includes selecting at least one subsequent one of the plurality of label values to be elicited from a user conditional on at least one previous one of the plurality of label values elicited from the user and the predictive correlations of the graphical structure.

23. The method of claim 16, wherein the labels are attribute labels and the method further includes predicting a class of the image based on the predicted attribute label values.

24. The method of claim 16, further comprising generating the feature-based predictions based on features extracted from the image with a classifier.

25. The method of claim 16, wherein the method comprises generating the graphical structure based on a training set of labeled images by a generative method which computes an optimal maximum spanning tree over a fully connected graph over the labels using mutual information on pairs of the labels estimated from the training set.

26. The method of claim 25, further comprising computing parameters of node potentials and of edge potentials of the tree-structured conditional model using log-likelihood maximization using the independent label predictors.

27. The method of claim 16, wherein the predicting of the value for at least one label from the set of labels comprises using inference on the tree-structure to find a most likely joint labeling for the new image.

28. A system comprising memory which stores instructions for performing the method of claim 16 and a processor in communication with the memory for executing the instructions.

29. A computer program product comprising a non-transitory recording medium storing instructions which, when executed by a computer, perform the method of claim 16.

30. A method for generating an annotation system comprising:

receiving a training set of manually-labeled training images;

for each of the training images, for each of a set of labels, generating a feature function based on features extracted from the image which predicts a value of the label for the image;

estimating mutual information between pairs of labels in a set of labels based on the training images;

optionally, clustering the set of labels into groups having at most a predetermined number k of labels;

with a processor, based on the mutual information and feature functions, generating a structured prediction model represented by a tree structure in which nodes of the tree structure include a respective single one of the labels or group of the labels, the nodes being linked by edges, each edge representing predicted correlations between values of labels in the pair of nodes connected by the edge, whereby when an image to be labeled is received, the tree structure allows predictions on labels to be informed by the predicted correlations in the tree structure.