Image enhancement through discrete patch optimization

• US 8,396,325 B1
• Filed: 04/27/2009
• Issued: 03/12/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
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): Thirugnanam, Gandhi
• Application Number:
  US12/430,812
• Time in Patent Office: 1,415 Days
• Field of Search: 382/284, 382/294
• 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 having a set of sites;

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;

selecting a label for the first site, the label selected from the candidate labels responsive at least in part to evaluating a degree of difference between the label and the first site; and

storing an identifier of the selected label in association with the first site,

wherein identifying the plurality of candidate labels comprises;

identifying a second site partially overlapping the first site;

computing an offset between locations of the first site and the second site;

identifying a label having a greatest degree of similarity to the second site within one of the one or more related images; and

identifying, as a candidate label, a second label within the one of the one or more related images, wherein the second label is offset by the computed offset from the label having the greatest degree of similarity to the second site.

2. The computer-implemented method of claim 1, further comprising:

substituting pixel data of the selected label for pixel data of the first site in the original image, thereby creating an enhanced output image; and

storing the enhanced output image.

3. The computer-implemented method of claim 2, 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.

4. The computer-implemented method of claim 1, further comprising:

combining pixel data of the label with pixel data of the first site in the original image, thereby creating an enhanced output image; and

storing the enhanced output image.

5. The computer-implemented method of claim 1, wherein a site is a pixel region of the original image, and wherein a label is a pixel region of one of the one or more related images.

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

receiving an original image having a set of sites;

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;

selecting a label for the first site, the label selected from the candidate labels responsive at least in part to evaluating a degree of difference between the label and the first site; and

storing an identifier of the selected label in association with the first site,

wherein identifying the plurality of candidate labels comprises;

identifying a plurality of sites partially overlapping the first site;

identifying, within the one or more related images, labels corresponding to the plurality of partially overlapping sites;

forming a composite patch from portions of the labels corresponding to the plurality of partially overlapping sites; and

identifying, as a candidate label, a label from one of the one or more related images having a greatest degree of similarity to the composite patch.

7. The computer-implemented method of claim 6, wherein a site is a pixel region of the original image, and wherein a label is a pixel region of one of the one or more related images.

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

receiving an original image having a set of sites;

receiving one or more images related to the original image;

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;

selecting a label for the first site, the label selected from the candidate labels responsive at least in part to evaluating a degree of difference between the label and the first site; and

storing an identifier of the selected label in association with the first site; and

evaluating the degree of difference between the selected label and the first site by;

producing a set of frequency coefficients for the first site and for the label;

computing a sum of the coefficients of the first site;

identifying a minimum group of top coefficients of the first site together accounting for more than a predetermined threshold percentage of the sum;

reducing to zero the values of the coefficients of the first site not included within the minimum group, thereby producing a first set of modified coefficients;

reducing to zero values the coefficients of the label not included within the minimum group, thereby producing a second set of modified coefficients; and

computing a difference between the first and second sets of modified coefficients.

9. The computer-implemented method of claim 8, wherein a site is a pixel region of the original image, and wherein a label is a pixel region of one of the one or more related images.

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

receiving an original image having a set of sites, wherein the set of sites is defined by a plurality of partitions, each partition defining a plurality of sites not overlapping with other sites in the partition;

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;

selecting a label for the first site, the label selected from the candidate labels responsive at least in part to evaluating a degree of difference between the label and the first site; and

storing an identifier of the selected label in association with the first site,

wherein evaluating the degree of difference of the candidate label from the first site comprises;

identifying a plurality of sites partially overlapping the first site, the plurality of sites from partitions other than a partition containing the first site;

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

forming, for each of the identified partitions, a composite patch from the identified labels of the partially overlapping sites that belong to that partition;

computing an average of the composite patches; and

computing a difference between the first site and the average of the composite patches.

11. The computer-implemented method of claim 10, wherein a site is a pixel region of the original image, and wherein a label is a pixel region of one of the one or more related images.

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

receiving an original image having a set of sites;

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;

selecting a label for the first site, the label selected from the candidate labels responsive at least in part to evaluating a degree of difference between the label and the first site; and

storing an identifier of the selected label in association with the first site,

wherein identifying the plurality of candidate labels comprises;

identifying a second site partially overlapping the first site;

computing an offset between locations of the first site and the second site;

identifying a label having a greatest degree of similarity to the second site within one of the one or more related images; and

identifying, as a candidate label, a second label within the one of the one or more related images, wherein the second label is offset by the computed offset from the label having the greatest degree of similarity to the second site.

13. The non-transitory computer-readable storage medium of claim 12, the actions of the computer program further comprising:

substituting pixel data of the label for pixel data of the first site in the original image, thereby creating an enhanced output image; and

storing the enhanced output image.

14. The non-transitory computer-readable storage medium of claim 12, wherein identifying the plurality of candidate labels further comprises:

identifying a plurality of sites partially overlapping the first site;

identifying, within the one or more related images, labels corresponding to the plurality of partially overlapping sites;

forming a composite patch from portions of the labels corresponding to the plurality of partially overlapping sites; and

identifying, as a second candidate label, a label from one of the one or more related images having a greatest degree of similarity to the composite patch.

15. The non-transitory computer-readable storage medium of claim 12, wherein evaluating the degree of difference of the candidate label from the first site comprises:

identifying a plurality of sites 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 sites;

computing an average of the identified labels; and

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

16. The non-transitory computer readable storage medium of claim 12, wherein a site is a pixel region of the original image, and wherein a label is a pixel region of one of the one or more related images.

17. The non-transitory computer readable medium of claim 12, wherein the actions of the computer program further comprise:

combining pixel data of the selected label with pixel data of the first site in the original image, thereby creating an enhanced output image; and

storing the enhanced output image.

18. 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 having a set of sites;

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;

selecting a label for the first site, the label selected from the candidate labels responsive at least in part to evaluating a degree of difference between the label and the first site and

storing an identifier of the selected label in association with the first site, wherein identifying the plurality of candidate labels comprises;

 

identifying a second site partially overlapping the first site;

 

computing an offset between locations of the first site and the second site;

 

identifying a label having a greatest degree of similarity to the second site within one of the one or more related images; and

 

identifying, as a candidate label, a second label within the one of the one or more related images, wherein the second label is offset by the computed offset from the label having the greatest degree of similarity to the second site.

19. The computer-implemented system of claim 18, wherein identifying the plurality of candidate labels further comprises:

identifying a plurality of sites partially overlapping the first site;

identifying, within the one or more related images, labels corresponding to the plurality of partially overlapping sites;

forming a composite patch from portions of the labels corresponding to the plurality of partially overlapping sites; and

identifying, as a second candidate label, a label from one of the one or more related images having a greatest degree of similarity to the composite patch.

20. The computer-implemented system of claim 18, wherein a site is a pixel region of the original image, and wherein a label is a pixel region of one of the one or more related images.