Optimization of multi-label problems in computer vision

• US 8,503,783 B2
• Filed: 03/17/2011
• Issued: 08/06/2013
• Est. Priority Date: 09/18/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rother, Carsten, Lempitsky, Victor, Blake, Andrew
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US13/050,825
• Publication Number:
  US 20110164819A1
• Time in Patent Office: 873 Days
• Field of Search: None
• 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 for computer vision, the method comprising:

representing a label value at each pixel in an image as a binary word, wherein each binary word comprises a plurality of bits arranged in order of significance;

determining, using a computer, a value of a most significant bit for each binary word in the image using binary optimization; and

repeating the determining for each bit for each binary word in order of decreasing significance to obtain a solution comprising a label for each pixel in the image.

2. The method of claim 1, wherein the determining the value includes using a learned pairwise potential for each bit in each binary word.

3. The method of claim 2, wherein each learned 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 pairwise potential is represented in parametric form.

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

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

7. The method of claim 1, further comprising:

selecting a shift parameter;

representing a sum of the label value at each pixel in the image and the shift parameter as a binary word, wherein each binary word comprises a plurality of bits;

repeating the determining and the repeating steps 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 third solution.

8. The method of claim 7, further comprising repeating the selecting of a shift parameter and the representing, determining, repeating and fusing steps until convergence.

9. The method of claim 8, wherein the shift parameter is selected randomly.

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

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

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

representing, during a computer vision process, a label value at each pixel in an image as a binary word, wherein each binary word comprises a plurality of bits;

determining, using a computer, a value of a bit for each binary word in the image using binary optimization and a learned pairwise potential for each bit in each binary word, wherein each learned pairwise potential comprises a least-squared error approximation of a pairwise potential at each bit level; and

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

13. A method for computer vision, the method comprising:

representing a label value at each pixel in an image as a binary word, wherein each binary word comprises a plurality of bits arranged in order of significance; and

performing, using a computer, binary optimization for each bit in order of decreasing significance, starting with a most significant bit, for each binary word to obtain a solution comprising a label for each pixel in the image.

14. The method of claim 13, further comprising repeating the method until convergence of the solution.

15. The method of claim 13, further comprising using Quadratic Pseudo Boolean Optimization (QPBO) in performing the binary optimization.

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

17. The method of claim 13, wherein the performing binary optimization for each bit, starting with the most significant bit, for each binary word further comprises, when performing the binary optimization for the most significant bit for each binary word, setting each value of all less significant bits for each binary word to zero.

18. The method of claim 13, wherein the performing binary optimization for each bit, starting with the most significant bit, for each binary word further comprises, when performing the binary optimization for the most significant bit for each binary word, calculating a lower bound for setting each value of all less significant bits for each binary word.

19. The method of claim 13, wherein the performing binary optimization includes using a learned pairwise potential.