IMAGE COMPLETION

• US 20090003702A1
• Filed: 06/27/2007
• Published: 01/01/2009
• Est. Priority Date: 06/27/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: CHEN, BILLY PUOSHUO, WEXLER, YONATAN, OFEK, EYAL
• Granted Patent: US 7,889,947 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77

Abstract

A computer-implemented method and media for completing images are provided. The computer-implemented method receives images having holes, identifies the holes, and searches an image database to locate images that fill the holes. Also, the computer-implemented method generates a multiscale graph of the image to locate images that fill the holes at different resolutions. A guide image may filter the located images that fill the holes at the different resolutions. The images that fill the holes and match the guide are selected to complete the images.

Claims

1. One or more computer-readable media having computer-executable instructions embodied thereon that perform a method for completing images, the method comprising:

receiving one or more images having holes;

locating a boundary for each hole;

dividing the boundary into blocks;

searching an image database to locate images that match each block;

layering matching images for each block to cover a portion of the hole associated with the block; and

combining the layered matching images to remove the holes in the one or more images.

2. The media of claim 1, wherein each boundary is a perimeter of each hole in each image.

3. The media of claim 1, wherein the blocks are portions of the image that surround the hole.

4. The media of claim 1, wherein the matching images are resized and positioned to partially cover the hole.

5. The media of claim 1, further comprising identifying a guide image.

6. The media of claim 5, further comprising searching the image database to locate images that match the guide.

7. The media of claim 6, wherein the matching images for each block comprise images that match the guide and the block.

8. The media of claim 5, further comprising applying a modification to the guide.

9. The media of claim 8, wherein the modification is one of obscuring the guide, altering color, altering contrast, altering gradients, or altering illumination.

10. A computer-implemented method for completing images, the method comprising:

receiving an image having holes;

generating a multiscale graph based on the image, wherein the multi-scale graph includes levels that represent different scales associated with the image;

identifying, for each level, the holes and a collection of image locations that are proximate to the identified holes;

searching an image database to locate images that match the collection of image locations;

calculating, for each level, a similarity between the matching images of neighboring image locations in the collection of image locations;

layering the matching images, at each level, to cover portions of the identified holes based on the similarity between the neighboring image locations of the collection of locations; and

combining, at each level, the layered images to cover the identified holes.

11. The computer-implemented method of claim 10, wherein each level has a parent-child relationship, wherein the child level is set at a resolution that is twice a resolution at the parent level.

12. The computer-implemented method of claim 10, wherein each image location is a node in the multiscale graph, and edges link overlapping image locations at different levels in the multiscale graph and overlapping image locations at the same level in the multiscale graph.

13. The computer-implemented method of claim 10, wherein each edge is associated with a weight that represents a similarity between the nodes connected by each edge.

14. The computer-implemented method of claim 10, wherein the match is based on a similarity between a portion of the image associated with the image location and the images included in the image database.

15. A computer-implemented method for completing images, the method comprising:

receiving an image having holes and a guide image;

generating a multiscale graph based on the image, wherein the multi-scale graph includes levels that represent different scales associated with the image;

identifying, for each level, the holes and a collection of image locations that are proximate to the identified holes;

searching an image database to locate images that match the collection of image locations;

calculating, for each level, a similarity between matching images for neighboring image locations in the collection of image locations;

selecting matching images for each image location in the collection of image locations based on a similarity to the guide image;

layering selected matching images, at each level, to cover portions of the identified hole based on the similarity between the neighboring image locations in the collection of image locations; and

combining, at each level, the layered images to cover the identified holes.

16. The computer-implemented method of claim 15, wherein the guide is selected from one of a synthetically rendered image, a user created image, a video frame, a photograph, or an image captured by an imaging device.

17. The computer-implemented method of claim 15, further comprising applying a modification to the guide.

18. The computer-implemented method of claim 17, wherein the modification is one of obscuring the guide, altering color, altering contrast, altering gradients, altering illumination.

19. The computer-implemented method of claim 15, wherein each image location represents a node in the multiscale graph, and edges link overlapping image locations at different levels in the multiscale graph and overlapping image location at the same level in the multiscale graph.

20. The computer-implemented method of claim 19, wherein each edge is associated with a weight that represents a similarity between the nodes connected by each edge.