Image Labeling Using Multi-Scale Processing

• US 20100322525A1
• Filed: 06/19/2009
• Published: 12/23/2010
• Est. Priority Date: 06/19/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rother, Carsten, Lempitsky, Victor, Kohli, Pushmeet
• Granted Patent: US 8,213,726 B2
• Time in Patent Office: Days
• US Class Current: 382/226
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06V 30/19187 Graphical models, e.g. Bayesian networks or Markov models
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

Multi-scale processing may be used to reduce the memory and computational requirements of optimization algorithms for image labeling, for example, for object segmentation, 3D reconstruction, stereo correspondence, optical flow and other applications. For example, in order to label a large image (or 3D volume) a multi-scale process first solves the problem at a low resolution, obtaining a coarse labeling of an original high resolution problem. This labeling is refined by solving another optimization on a subset of the image elements. In examples, an energy function for a coarse level version of an input image is formed directly from an energy function of the input image. In examples, the subset of image elements may be selected using a measure of confidence in the labeling.

Claims

1. An image labeling apparatus comprising:

an input arranged to receive a first image to be labeled;

a coarsening engine arranged to repeatedly reduce the resolution of the original image according to a scaling factor to form an image pyramid;

a processor arranged to form an energy function from the coarsest image in the pyramid and by adjusting parameter values of that energy function on the basis of the scaling factor;

an optimization engine arranged to optimize the energy function to obtain a labeling of the coarsest image;

the processor being arranged to project the labeling onto the next-coarsest image in the pyramid to obtain a region of unlabeled image elements;

the processor being arranged to form another energy function using the current image in the pyramid and by adjusting parameter values of that energy function on the basis of the scaling factor;

the optimization engine being arranged to optimize the another energy function only over the region of unlabeled image elements to obtain a revised labeling; and

wherein the processor and optimization engine are arranged to repeatedly;

project the revised labeling, form another energy function and optimize that energy function;

to use all the images in the pyramid and so produce a labeled version of the first image.

2. An apparatus as claimed in claim 1 wherein the processor is arranged to adjust parameter values of pairwise potentials of the energy function.

3. An apparatus as claimed in claim 1 wherein the processor is arranged to obtain the region of unlabeled image elements by using a measure of the confidence of the labeling.

4. An apparatus as claimed in claim 3 wherein the processor is arranged to calculate and use min-marginals as the measure of the confidence of the labeling, where the min-marginal of an image element is the energy value obtained by fixing the label of that image element to a specified label and optimizing the energy function over the remaining image elements.

5. An apparatus as claimed in claim 1 wherein the processor is arranged to obtain the region of unlabeled image elements by finding a first region of unlabeled image elements using a measure of confidence of the labeling;

finding a second region of unlabeled image elements using a distance from a segmentation boundary; and

combining the first and second regions.

6. An image labeling apparatus comprising:

an input arranged to receive a first image to be labeled;

a coarsening engine arranged to repeatedly reduce the resolution of the original image to form an image pyramid;

a processor arranged to form an energy function for the coarsest image in the pyramid directly from an energy function of the original image;

an optimization engine arranged to optimize the energy function to obtain a labeling of the coarsest image;

the processor being arranged to project the labeling onto the next-coarsest image in the pyramid to obtain a region of unlabeled image elements;

the processor being arranged to form another energy function for the current image in the pyramid from the energy function of the original image;

the optimization engine being arranged to optimize the another energy function only over the region of unlabeled image elements to obtain a revised labeling; and

wherein the processor and optimization engine are arranged to repeatedly;

project the revised labeling, form another energy function and optimize that energy function;

to use all the images in the pyramid and so produce a labeled version of the first image.

7. An apparatus as claimed in claim 6 wherein the processor is arranged to form an energy function for a particular image in the pyramid by obtaining a unary potential for each image element by combining unary potentials of a child set of image elements being those image elements in the original image which are mapped to the image element concerned by the coarsening engine.

8. An apparatus as claimed in claim 6 wherein the processor is arranged to form an energy function for a particular image in the pyramid by obtaining a pairwise potential for each image element by combining pairwise potentials defined between a child set of image elements being those image elements in the original image which are mapped to the image element concerned by the coarsening engine.

9. An apparatus as claimed in claim 6 wherein the processor is arranged to form an energy function for a given image in the pyramid such that pairwise potentials defined on image elements which have the same parent are taken into account;

where the parent of an image element is an image element in a coarser level image of the pyramid which maps to that image element.

10. An apparatus as claimed in claim 6 wherein the processor is arranged to obtain the region of unlabeled image elements by using a measure of the confidence of the labeling.

11. An apparatus as claimed in claim 10 wherein the processor is arranged to calculate and use min-marginals as the measure of the confidence of the labeling where the min-marginal of an image element is the energy value obtained by fixing the label of that image element to a specified label and optimizing the energy function over the remaining image elements.

12. An apparatus as claimed in claim 6 wherein the processor is arranged to obtain the region of unlabeled image elements by finding a first region of unlabeled image elements using a measure of confidence of the labeling;

finding a second region of unlabeled image elements using a distance from a segmentation boundary; and

combining the first and second regions.

13. An apparatus as claimed in claim 6 which is an image segmentation apparatus.

14. A method of labeling an image comprising:

at an input receiving a first image to be labeled;

arranging a coarsening engine to repeatedly reduce the resolution of the original image to form an image pyramid according to a scaling factor;

arranging a processor to form an energy function for the coarsest image in the pyramid;

arranging an optimization engine to optimize the energy function to obtain a labeling of the coarsest image;

arranging the processor to project the labeling onto the next-largest image in the pyramid and to identify, using a measure of confidence of the labeling, a plurality of image elements to be reassessed;

arranging the processor to form another energy function for the current image in the pyramid;

arranging the optimization engine to optimize the another energy function only over the identified plurality of image elements to obtain a revised labeling; and

using the processor and optimization engine to repeatedly;

project the revised labeling, form another energy function and optimize that energy function;

to use all the images in the pyramid and so produce a labeled version of the first image.

15. A method as claimed in claim 14 which comprises arranging the processor to use min-marginals as the confidence measure, where the min-marginal of an image element is the energy value obtained by fixing the label of that image element to a specified label and optimizing the energy function over the remaining image elements.

16. A method as claimed in claim 14 which comprises arranging the processor to use color values of the image elements to provide a confidence measure.

17. A method as claimed in claim 14 where the processor is arranged to identify the image elements to be reassessed by finding a first plurality image elements to be reassessed using the measure of confidence of the labeling;

finding a second plurality of image elements to be reassessed using a distance from a segmentation boundary; and

combining the first and second plurality of image elements.

18. A method as claimed in claim 14 which comprises arranging the processor to form each energy function directly from an energy function of the first image.

19. A method as claimed in claim 18 which comprises arranging the processor to form each energy function such that pairwise potentials defined on image elements which have the same parent are taken into account;

where the parent of an image element is an image element in a coarser level image of the pyramid which maps to that image element.

20. A method as claimed in claim 14 which comprises arranging the processor to form each energy function from an image in the pyramid associated with that energy function and by adjusting parameter values of that energy function on the basis of a scaling factor used in creation of the image pyramid.