Optimization of Multi-Label Problems in Computer Vision

• US 20110164819A1
• Filed: 03/17/2011
• Published: 07/07/2011
• Est. Priority Date: 09/18/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lempitsky, Victor, Rother, Carsten, Blake, Andrew
• Granted Patent: US 8,503,783 B2
• Time in Patent Office: Days
• US Class Current: 382/180
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

A method of labeling pixels in an image is described where the pixel label is selected from a set of three or more labels. The pixel labeling problem is reduced to a sequence of binary optimizations by representing the label value for each pixel as a binary word and then optimizing the value of each bit within the word, starting with the most significant bit. Data which has been learned from one or more training images is used in the optimization to provide information about the less significant bits within the word.

Claims

1. A method of labeling pixels in an image for image segmentation, comprising:

representing a label value at each pixel as a binary word;

determining, using a computer, a value of a bit for each pixel in the image using a binary optimizer and learned data; and

repeating the determining for each bit for each pixel to obtain a solution comprising a label for each pixel in the image.

2. The method of claim 1, wherein the learned data comprises learned approximate pairwise potentials for any less significant bits in each word.

3. The method of claim 2, wherein each learned approximate pairwise potential comprises a least-squared error approximation of a pairwise potential at each bit level.

4. The method of claim 2, wherein each learned approximate pairwise potential is represented in parametric form.

5. The method of claim 1, wherein the binary optimizer performs Quadratic Pseudo Boolean Optimization (QPBO).

6. The method of claim 1, further comprising repeating the method until convergence.

7. The method of claim 1, further comprising storing a labeled version of the image, the labeled version comprising pixels assigned to labels according to the solution.

8. The method of claim 7, further comprising displaying the labeled version of the image in a user interface of an image processing application.

9. The method of claim 1, wherein each binary word comprises a plurality of bits arranged in order of significance.

10. The method of claim 9, wherein determining the value of a bit comprises determining a value of a most significant bit, and wherein the determination is repeated for each bit for each pixel in order of decreasing significance.

11. The method of claim 10, further comprising:

selecting a shift parameter;

representing a sum of the label value at each pixel and the shift parameter as a binary word;

determining a value of a most significant bit for each pixel in the image using the binary optimizer and the learned data;

repeating the determination for each bit for each pixel in order of decreasing significance to obtain a second solution comprising a label for each pixel in the image; and

fusing the solution and the second solution to create a new solution.

12. The method of claim 11, further comprising repeating the selection of a shift parameter and the representing, determining, repeating and fusing steps until convergence.

13. The method of claim 12, wherein the shift parameter is selected substantially randomly.

14. The method of claim 13, wherein the shift parameter is selected to maximize a regrouping parameter, r, defined as:

15. The method of claim 1, wherein each label is selected from a set comprising at least three labels.

16. One or more computer-readable memory storing computer-executable instructions that, when executed on a processor, configure the processor to perform operations comprising:

representing a label value at each pixel in an image as a binary word;

determining, using a computer, a value of a bit for each pixel in the image using a binary optimizer and learned data; and

repeating the determining for each bit for each pixel to obtain a solution comprising a label for each pixel in the image.

17. The one or more computer-readable memory of claim 16, the operations further comprising storing a labeled version of the image, the labeled version comprising pixels assigned to labels according to the solution.

18. A method of labeling pixels in an image for image segmentation, comprising:

dividing, using a computer, a label space of the image into at least a first subset and a second subset;

performing an expansion algorithm on the first subset to form a first solution;

performing an expansion algorithm of the second subset to form a second solution; and

combining the first solution and the second solution.

19. The method of claim 18, wherein combining the first solution and the second solution comprises selecting, at each pixel location of the image, a pixel label of the first solution or a pixel label of the second solution.

20. The method of claim 18, further comprising determining a value of each pixel of the image using a binary optimizer that performs Quadratic Pseudo Boolean Optimization (QPBO).