Image completion including automatic cropping

• US 9,881,354 B2
• Filed: 03/15/2012
• Issued: 01/30/2018
• Est. Priority Date: 03/15/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kopf, Johannes Peter, Kang, Sing Bing, Kienzle, Wolf, Drucker, Steven M.
• Primary Examiner(s): Liew, Alex
• Application Number:
  US13/421,307
• Publication Number:
  US 20130243320A1
• Time in Patent Office: 2,147 Days
• Field of Search: 382276-308, 382181-231, 382168-172
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06T 5/77 Retouching; Inpainting; Scratch removal

Abstract

Described is a technology by which an image such as a stitched panorama is automatically cropped based upon predicted quality data with respect to filling missing pixels. The image may be completed, including by completing only those missing pixels that remain after cropping. Predicting quality data may be based on using restricted search spaces corresponding to the missing pixels. The crop is computed based upon the quality data, in which the crop is biased towards including original pixels and excluding predicted low quality pixels. Missing pixels are completed by using restricted search spaces to find replacement values for the missing pixels, and may use histogram matching for texture synthesis.

Claims

1. A method comprising:

determining, using a prediction function, a quality of at least one missing region relative to a quality threshold prior to filling in the at least one missing region with known pixels from one or more other regions of an image, the at least one missing region comprising unknown pixels;

subsequently computing a crop of the image based upon the determined quality of the at least one missing region by excluding one or more of the unknown pixels in the at least one missing region that are below the quality threshold and including one or more of the unknown pixels in the at least one missing region that are above the quality threshold; and

upon computing the crop, filling in the one or more of the unknown pixels in the at least one missing region that are above the quality threshold within the crop with one or more of the known pixels of the image.

2. The method of claim 1 wherein the determining includes determining candidate patches comprising known pixels that are useable in completing a missing region, including restricting a source location for the candidate patches based upon texture features.

3. The method of claim 2 further comprising using histogram matching for texture synthesis.

4. The method of claim 1 wherein the determining includes computing a distance to each of the unknown pixels from a corresponding source location.

5. The method of claim 1 wherein computing the crop comprises using an energy function that penalizes an inclusion of low quality pixels and penalizes an exclusion of original pixels.

6. The method of claim 5 further comprising:

computing a per-pixel energy; and

determining whether to adjust a portion of the crop based upon the combined energy of pixels corresponding to the portion of the crop.

7. The method of claim 1 further comprising, replacing at least some low quality regions with part of a decorative frame around at least part of the crop.

8. The method of claim 1 further comprising, training a prediction mechanism that predicts a quality of the unknown pixels.

9. The method of claim 1 wherein determining that the at least one missing region is a low quality region comprises inputting a feature vector into a trained prediction mechanism.

10. The method of claim 1 wherein filling in the one or more of the unknown pixels comprises finding a closest appearing known patch.

11. A system comprising:

a prediction mechanism that;

determines quality data for missing pixels associated with an image using a prediction function, the determined quality data comprising at least one missing region of the image comprising sets of unknown pixels; and

determine a quality of the at least one missing region, based on the prediction function, relative to a quality threshold prior to filling in the at least one missing region with known pixels from one or more other regions of the image; and

a cropping mechanism that;

processes the quality data to generate a crop of the image based upon the determined quality of the at least one missing region by excluding one or more unknown pixels in the sets of the unknown pixels in the at least one missing region that are below the quality threshold and including one or more of the unknown pixels in the at least one missing region that are above the quality threshold; and

upon generating the crop, fills the unknown pixels in the at least one missing region that are above the quality threshold within the crop with the known pixels of the image based on processing the quality data.

12. The system of claim 11 wherein the prediction mechanism outputs the determined quality data for a pixel by inputting a feature vector corresponding to a restricted search space that is based at least in part on a location of the pixel.

13. The system of claim 12 wherein the feature vector is based at least in part on one or more color-related histograms, edge density data, an edge orientation-related histogram, a contour-related histogram or a straight line length-related histogram, or any combination of one or more color-related histograms, edge density data, an edge orientation-related histogram, a contour-related histogram or a straight line length-related histogram.

14. The system of claim 13 wherein at least one of the histograms corresponds to entropy data, mean data or standard deviation data, or any combination of entropy data, mean data or standard deviation data.

15. The system of claim 11 further comprising a completion mechanism that uses histogram matching for texture synthesis, in which the histograms correspond to a restricted search space computed for the missing pixels.

16. One or more computer-readable storage devices having computer-executable instructions for processing an image to complete missing regions, which when executed by one or more processors, perform operations comprising:

determining a quality of a region based on the region including pixels of the image and missing pixels of the image prior to filling in the missing pixels with known pixels from one or more other regions of the image; and

based on the determined quality of the region, generating a crop of the image by excluding one or more missing pixels in the region that are below a quality threshold and including one or more of the missing pixels in the region that are above the quality threshold; and

upon generating the crop, filling the missing pixels in the region that are above the quality threshold within the crop with the pixels within the crop or the known pixels based on the determining.

17. The one or more computer-readable storage devices of claim 16 wherein the determining is based upon restricting a source location for each filled-in pixel based upon texture features.

18. The one or more computer-readable storage devices of claim 16 having further computer-executable instructions that when executed by the one or more processors, perform an operation comprising replacing a low quality region with part of a decorative frame around at least part of the crop.

19. The one or more computer-readable storage devices of claim 16 wherein the determining includes determining candidate patches comprising known pixels that are useable in completing the missing region, including restricting a source location for the candidate patches based upon texture features.

20. The one or more computer-readable storage devices of claim 16 wherein determining the quality of the region comprises inputting a feature vector into a trained prediction mechanism.