Optimization of Multi-Label Problems in Computer Vision

• US 20090074292A1
• Filed: 09/18/2007
• Published: 03/19/2009
• Est. Priority Date: 09/18/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rother, Carsten, Lempitsky, Victor, Blake, Andrew
• Granted Patent: US 7,925,089 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, wherein each label is selected from a set comprising at least three labels, the method comprising:

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

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

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

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

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

4. A method according to claim 2, wherein each learned approximate pairwise potential is represented in parametric form.

5. A method according to claim 1, wherein the binary optimizer comprises QPBO.

6. A method according to claim 1, further comprising repeating the method until convergence.

7. A method according to claim 1, further comprising:

storing a labeled version of the image, the labeled version comprising pixels assigned labels according to the solution.

8. A method according to claim 7, further comprising:

displaying the labeled version of the image in a user interface of an image processing application.

9. A method according to claim 1, further comprising:

selecting a shift parameter;

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

10. A method according to claim 9, further comprising:

repeating the selection of a shift parameter and the representing, determining, repeating and fusing steps until convergence.

11. A method according to claim 9, wherein the shift parameter is selected substantially randomly.

12. A method according to claim 10, wherein the shift parameter is selected to maximize a regrouping parameter, r, defined as:

$r=\underset{b=1}{\overset{B}{\sum <br><br>}}<br><br>\frac{1}{2}-<br><br><br><br>\frac{<br><br>s_1-s_2<br><br><br><br><br><br>\mathrm{mod}<br><br><br><br>2^b}{2^b}-\frac{1}{2}<br><br>$

where b is a bit level and s₁ and s₂ are two sequentially selected values of the shift parameter.

13. A computer readable medium storing information to enable a computing device to perform a process, the computing device comprising a processor and a memory, the process 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 a value of a most significant bit for each pixel in the image using a binary optimizer and learned data; and

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

14. A computer readable medium according to claim 13, wherein the process further comprises:

storing a labeled version of the image, the labeled version comprising pixels assigned labels according to the solution.

15. A computer readable medium according to claim 14, wherein the process further comprises:

displaying the labeled version of the image in a user interface of an image processing application.

16. A method of labeling each pixel in an image with one of a set of at least three labels, the method comprising:

representing labels associated with each of the pixels in the image as binary words, each word comprising a plurality of bits arranged in order of decreasing significance;

selecting a first bit level, comprising a most significant bit from each of the binary words and calculating the value of each of the bits in the first bit level using binary optimization and learned data relating to less significant bits in each word;

selecting a next bit level, comprising a next most significant bit from each of the binary words and calculating the value of each of the bits in the selected next bit level using binary optimization and learned data relating to less significant bits in each word; and

repeating the selection of a next bit level and the calculation of values of bits in the selected next bit level until the values of all bits in all binary words have been calculated to produce a fully labeled image.

17. A method according to claim 16, wherein the learned data relating to less significant bits in each word comprises:

learned approximate pairwise potentials for any less significant bits in each word.

18. A method according to claim 16, wherein the binary optimization uses QPBO.

19. A method according to claim 16, further comprising:

storing the fully labeled image, the fully labeled image comprising pixels assigned labels according to the values of bits in the binary words.

20. A method according to claim 16, further comprising:

displaying the fully labeled image in a user interface of an image processing application.