Identifying repeated-structure elements in images

• US 7,729,531 B2
• Filed: 09/19/2006
• Issued: 06/01/2010
• Est. Priority Date: 09/19/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kannan, Anitha, Winn, John, Rother, Carsten
• Primary Examiner(s): Le; Vu
• Assistant Examiner(s): LIEW, ALEX KOK SOON
• Application Number:
  US11/533,297
• Publication Number:
  US 20080069438A1
• Time in Patent Office: 1,351 Days
• Field of Search: None
• US Class Current: 382/155
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

Many problems in the fields of image processing and computer vision relate to creating good representations of information in images of objects in scenes. We provide a system for learning repeated-structure elements from one or more input images. The repeated-structure elements are patches that may be single pixels or coherent groups of pixels of varying shape, size and appearance (where those shapes and sizes are not pre-specified). Input images are mapped to a single output image using offset maps to specify the mapping. A joint probability distribution on the offset maps, output image and input images is specified and an unsupervised learning process is used to learn the offset maps and output image. The learnt output image comprises repeated-structure elements. This shape and appearance information captured in the learnt repeated-structure elements may be used for object recognition and many other tasks.

Claims

1. A computer-implemented method comprising:

performed by one or more processors executing computer-readable instructions,

receiving one or more input images;

for each input image, specifying an initial offset map comprising a mapping of image elements from the input image onto an initialized output image;

specifying a joint probability distribution on the output image, the input images and the offset maps such that the joint probability distribution comprises a neighborhood constraint such that the repeated-structure elements tend to be learned such that their size is as large as possible while still enabling the repeated-structure elements to describe as many regions in the input image(s) as possible;

optimizing the joint probability distribution to find a learned output image and offset maps, the learned output image comprising learned repeated-structure elements having variable shape, size and appearance; and

outputting the learned output image and offset maps.

2. The computer-implemented method as claimed in claim 1 wherein the output image is smaller in area than the combined area of the input images.

3. The computer-implemented method as claimed in claim 1 wherein the joint probability distribution is specified such that each of the learned repeated-structure elements are substantially the same in appearance and shape to two or more regions of the input image(s).

4. The computer-implemented method as claimed in claim 1 which comprises relaxing the neighborhood constraint such that the learned repeated-structure elements are substantially invariant to local deformations, scaling and small rotation of regions in the input images.

5. The computer-implemented method as claimed in claim 1 wherein the joint probability distribution is further specified such that any of the input images may be approximately reconstructed using only pieces from the learned output image.

6. The computer-implemented method as claimed in claim 1 wherein the optimization further comprises clustering the output image on the basis of appearance and shape, the resulting clusters being the learned repeated-structure elements.

7. The computer-implemented method as claimed in claim 1 wherein the optimization-further comprises an expectation maximization process.

8. The computer-implemented method as claimed in claim 1 wherein the optimization is an iterative process comprising:

computing possible offset maps given the initialized output image; and

given the computed offset maps, finding an output image which optimizes the joint probability distribution.

9. The computer-implemented method as claimed in claim 8 wherein computing the possible offset maps is carried out using any of:

a graph-cut algorithm and belief propagation.

10. The computer-implemented method as claimed in claim 8 wherein optimizing the joint probability distribution is carried out using an analytical process.

11. The computer-implemented method as claimed in claim 1 which further comprises:

labeling the repeated-structure elements in the learned output image with information about object classes repeated-structure elements relate to;

receiving a test image of objects for which it is required to carry out object recognition;

determining an offset map for the test image given the labeled learned output image; and

labeling the test image using the determined offset map and labeled learned output image such that objects in the test image are recognized.

12. The computer-implemented method as claimed in claim 1 which further comprises:

during receiving of the input images, receiving a sequence of images of one or more objects moving in a scene; and

wherein the method comprises obtaining two learned output images, one comprising appearance information and the other comprising flow information.

13. A computer-implemented method comprising:

performed by one or more processors executing computer-readable instructions, receiving one or more input images;

for each input image, specifying an initial offset map comprising a mapping of image elements from the input image onto an initialized output image;

specifying a probabilistic model of a relationship between the output image, the input images and the offset maps such that it comprises a neighborhood constraint such that the repeated-structure elements tend to be learned such that their size is as large as possible while still enabling the repeated-structure elements to describe as many regions as possible in the input image(s);

applying an unsupervised learning process to the probabilistic model to find a learned output image and offset maps, the learned output image comprising learned repeated-structure elements having variable shape, size and appearance; and

outputting the learned output image and offset maps.

14. The computer-implemented method as claimed in claim 13 which further comprises using the learned repeated-structure elements in any of:

an object recognition system, an object detection system, an image segmentation system, an image synthesis system, an image in-painting system, a stereo vision system, an image editing system, an image classification system, an image retrieval system, a super-resolution system, an image texture-transfer system, a motion segmentation system, a motion tracking system and an image/video compression system.

15. The computer-implemented method as claimed in claim 13 wherein the probabilistic model is specified such that any of the input images may be approximately reconstructed using only pieces from the learned output image.

16. The computer-implemented method as claimed in claim 13 wherein the unsupervised learning step comprises clustering the output image on the basis of appearance and shape, the resulting clusters being the learned repeated-structure elements.

17. One or more device-readable storage media with device-executable instructions that, when executed on a processor, configure the processor to perform acts comprising:

receiving one or more input images;

for each input image, specifying an initial offset map comprising a mapping of image elements from the input image onto an initialized output image;

specifying a joint probability distribution on the output image, the input images and the offset maps such that the joint probability distribution comprises a neighborhood constraint such that the repeated-structure elements tend to be learned such that their size is as large as possible while still enabling the repeated-structure elements to describe as many regions in the input image(s) as possible;

optimizing the joint probability distribution to find a learned output image and offset maps, the learned output image comprising learned repeated-structure elements having variable shape, size and appearance; and

outputting the learned output image and offset maps.

18. The one or more device-readable media as claimed in claim 17 wherein the output image is specified such that it is smaller in area than the combined area of the input images.