Learning structured prediction models for interactive image labeling

• US 8,774,515 B2
• Filed: 04/20/2011
• Issued: 07/08/2014
• 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
• Primary Examiner(s): BEKELE, MEKONEN T
• Application Number:
  US13/090,378
• Publication Number:
  US 20120269436A1
• Time in Patent Office: 1,175 Days
• Field of Search: 382/180, 382/159, 382/224, 382/181, 382/154, 382/131, 382/228, 715/233, 715/234, 715/229, 715/230, 704/4, 704/3, 704/5, 704/6, 704/9
• 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 comprising a graphical structure which represents predicted correlations between values assumed by labels in a set of labels, the graphical structure comprising at least one tree structure, 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 structure, the nodes of the tree having at most a predefined number k of the labels, and each of a plurality of the nodes has more than one of the labels, 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;

memory which stores instructions for;

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

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 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.

3. The system of claim 1, wherein the predefined maximum number k is at least 2 and is less than a total number of the labels.

4. The system of claim 1, wherein the at least one tree structure 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.

5. The system of claim 1, 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 1, 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.

10. 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.

11. 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.

12. 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.

25. A method for generating the annotation system of claim 1, 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; and

with a processor, based on the mutual information and feature functions, generating the 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.

26. The system of claim 3, wherein the predefined maximum number k is up to 10.

27. The system of claim 26, wherein the total number of the labels is at least fifty.

6. 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, the structured prediction model comprises at least one tree structure and 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;

memory which stores instructions for;

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

providing for receiving an assigned value for at least one label from the set of labels for the image, and

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, the predicted value being also based on an assigned value for at least one other label, if one has been assigned, the system having 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 tree structure which propagates modified predictions on values of the labels provided by the user to other labels via the edges; and

a processor for executing the instructions.

7. The system of claim 6, 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 tree structure.

8. The system of claim 7, 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.

13. A method for labeling images comprising:

providing a structured prediction model in memory which represents predictive correlations between labels in a set of labels, the structured prediction model comprising a tree structure in which each of the labels in the set of labels is in exactly one node of the tree structure 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;

receiving an image to be labeled;

eliciting a plurality of the label values for the image from a user;

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 based on an assigned label value for at least one other label, the assigned label value comprising the elicited label values, the prediction of the value for the at least one label for the input image including 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.

14. The method of claim 13, further comprising computing the tree structure using a generative model.

15. The method of claim 13, 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.

16. The method of claim 15, wherein the structured prediction model 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.

17. The method of claim 13, 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 structured prediction model.

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

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

20. The method of claim 13, wherein the method comprises generating the structured prediction model 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.

21. The method of claim 20, 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.

22. The method of claim 13, 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 structured prediction model.

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

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