Image enhancement through discrete patch optimization

• US 8,571,349 B1
• Filed: 09/14/2012
• Issued: 10/29/2013
• Est. Priority Date: 04/27/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kwatra, Vivek, Han, Mei, Yagnik, Jay N.
• Primary Examiner(s): Thirugnanam, Gandhi
• Application Number:
  US13/619,624
• Time in Patent Office: 410 Days
• Field of Search: 382/284, 382/299
• US Class Current: 382/284
• CPC Class Codes: G06T 7/33 using feature-based methods

Abstract

An image processing system enhances the resolution of an original image using higher-resolution image data from other images. The image processing system defines a plurality of overlapping partitions for the original image, each partition defining a set of non-overlapping site patches. During an optimization phase, the system identifies, for site patches of the original images, label patches within related images that are of most relevance. During a rendering phase independent of the optimization phase, an output image with enhanced resolution is synthesized by substituting, for site patches of the original image, the identified relevant label patches from the related images.

Claims

1. A computer-implemented method of enhancing an image, comprising:

receiving an original image;

automatically defining, by a processor, a set of sites for the original image, each site being a candidate to be patched and having a first resolution;

receiving one or more images related to the original image; and

for a first site of the set of sites, performing operations comprising;

identifying a plurality of candidate labels from the one or more related images, each candidate label being a pixel region of one of the related images that is a potential patch for the first site and that has a second resolution higher than the first resolution;

producing down-sampled label data by converting a label of the candidate labels from the second resolution to the first resolution;

performing a pixel-by-pixel comparison of pixels in the down-sampled label data with corresponding pixels of the first site;

determining a degree of difference between the label and the first site based on the pixel-by-pixel comparison;

automatically selecting the label as a patch for the first site, the label selected responsive at least in part to the degree of difference between the label and the first site; and

enhancing the image by applying the patch to the first site.

2. The computer-implemented method of claim 1, further comprising selecting the label responsive at least in part to a determined degree of difference between the label and labels previously selected as patches for sites that overlap the first site.

3. The computer-implemented method of claim 1, wherein the set of sites is defined by a plurality of partitions, each partition comprising a non-overlapping subset of the sites that are aligned on a common grid, the partitions being offset such that sites in different partitions partially overlap, wherein patches selected for partially overlapping sites are combined to form composite patches.

4. The computer-implemented method of claim 1, further comprising iteratively performing the operations for the first site until an end condition is reached.

5. The computer-implemented method of claim 1, wherein enhancing the image comprises:

substituting pixel data of the patch at the second resolution for pixel data of the first site in the original image at the first resolution, thereby creating an enhanced output image; and

storing the enhanced output image.

6. The computer-implemented method of claim 5, wherein the substituting of pixel data is performed via Poisson blending of the pixel data of the first site with pixel data of surrounding sites.

7. The computer-implemented method of claim 1, wherein enhancing the image comprises:

combining pixel data of the patch at the second resolution with pixel data of the first site in the original image at the first resolution, thereby creating an enhanced output image; and

storing the enhanced output image.

8. The computer-implemented method of claim 1, wherein the pixel-by-pixel comparison includes determining at least one of:

a number of corresponding pixels that differ between the down-sampled label data and the first site, and a sum of differences of color values for corresponding pixels in the down-sampled label data and the first site.

9. A non-transitory computer-readable storage medium storing a computer program executable by a processor for enhancing an image, the actions of the computer program comprising:

receiving an original image;

automatically defining, by a processor, a set of sites for the original image, each site being a candidate to be patched and having a first resolution;

receiving one or more images related to the original image; and

for a first site of the set of sites, performing operations comprising;

identifying a plurality of candidate labels from the one or more related images, each candidate label being a pixel region of one of the related images that is a potential patch for the first site and that has a second resolution higher than the first resolution;

producing down-sampled label data by converting a label of the candidate labels from the second resolution to the first resolution;

performing a pixel-by-pixel comparison of pixels in the down-sampled label data with corresponding pixels of the first site;

determining a degree of difference between the label and the first site based on the pixel-by-pixel comparison;

automatically selecting the label as a patch for the first site, the label selected responsive at least in part to the degree of difference between the label and the first site; and

enhancing the image by applying the patch to the first site.

10. The non-transitory computer readable storage medium of claim 9, wherein the set of sites is defined by a plurality of partitions, each partition comprising a non-overlapping subset of the sites that are aligned on a common grid, the partitions being offset such that sites in different partitions partially overlap, wherein patches selected for partially overlapping sites are combined to form composite patches.

11. The non-transitory computer-readable storage medium of claim 9, wherein enhancing the image comprises:

substituting pixel data of the patch at the second resolution for pixel data of the first site in the original image at the first resolution, thereby creating an enhanced output image; and

storing the enhanced output image.

12. The non-transitory computer-readable storage medium of claim 9, wherein enhancing the image comprises:

combining pixel data of the patch at the second resolution with pixel data of the first site in the original image at the first resolution, thereby creating an enhanced output image; and

storing the enhanced output image.

13. The non-transitory computer readable storage medium of claim 9, wherein the pixel-by-pixel comparison includes determining at least one of:

a number of corresponding pixels that differ between the down-sampled label data and the first site, and a sum of differences of color values for corresponding pixels in the down-sampled label data and the first site.

14. The non-transitory computer-readable storage medium of claim 9, wherein determining the degree of difference between the label and the first site comprises:

identifying a plurality of sites partially overlapping the first site;

identifying a plurality of labels from one of the one or more related images that were previously assigned to the identified partially overlapping sites;

computing an average of the identified labels; and

computing a difference between the first site and the average of the identified labels.

15. The non-transitory computer-readable storage medium of claim 9, wherein the actions of the computer program further comprise iteratively performing the operations for the first site until an end condition is reached.

16. A computer-implemented system for enhancing an image, comprising:

a processor configured to execute computer program modules, the computer program modules comprising;

an optimization module performing actions comprising;

receiving an original image;

automatically defining, by a processor, a set of sites for the original image, each site being a candidate to be patched and having a first resolution;

receiving one or more images related to the original image; and

for a first site of the set of sites, performing operations comprising;

identifying a plurality of candidate labels from the one or more related images, each candidate label being a pixel region of one of the related images that is a potential patch for the first site and that has a second resolution higher than the first resolution;

producing down-sampled label data by converting a label of the candidate labels from the second resolution to the first resolution;

performing a pixel-by-pixel comparison of pixels in the down-sampled label data with corresponding pixels of the first site;

determining a degree of difference between the label and the first site based on the pixel-by-pixel comparison;

automatically selecting the label as a patch for the first site, the label selected responsive at least in part to the degree of difference between the label and the first site; and

enhancing the image by applying the patch to the first site.

17. The computer-implemented system of claim 16, wherein the set of sites is defined by a plurality of partitions, each partition comprising a non-overlapping subset of the sites that are aligned on a common grid, the partitions being offset such that sites in different partitions partially overlap, wherein patches selected for partially overlapping sites are combined to form composite patches.

18. The computer-implemented system of claim 16, wherein enhancing the image comprises:

combining pixel data of the patch at the second resolution with pixel data of the first site in the original image at the first resolution, thereby creating an enhanced output image; and

storing the enhanced output image.

19. The computer-implemented system of claim 16, wherein the pixel-by-pixel comparison includes determining at least one of:

a number of corresponding pixels that differ between the down-sampled label data and the first site, and a sum of differences of color values for corresponding pixels in the down-sampled label data and the first site.

20. The computer-implemented system of claim 16, wherein determining the degree of difference between the label and the first site comprises:

identifying a plurality of sites partially overlapping the first site;

identifying a plurality of labels from one of the one or more related images that were previously assigned to the identified partially overlapping sites;

computing an average of the identified labels; and

computing a difference between the first site and the average of the identified labels.