Method for sliced inpainting

• US 9,870,604 B2
• Filed: 09/09/2016
• Issued: 01/16/2018
• Est. Priority Date: 11/27/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Kokemohr, Nils
• Primary Examiner(s): Li, Ruiping
• Application Number:
  US15/260,390
• Publication Number:
  US 20160379344A1
• Time in Patent Office: 494 Days
• Field of Search: 382263, 382275
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/20192 Edge enhancement; Edge preservation
• CPC Class Codes: G06T 5/00 Image enhancement or restoration
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 5/77 Retouching; Inpainting; Scratch removal
• CPC Class Codes: G06T 5/80 Geometric correction
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/90 Determination of colour characteristics

Abstract

A method for replacing image data in a destination region that is divided into sub-pieces along one or more cutting paths, which start and end at two different points on the border, and finding replacement data for the sub-pieces. The cutting paths may be determined as a function of the type of image structured at the start and the end points. The cutting paths may also be determined as a function of the area of the sub-pieces and the lengths of the cutting paths. Optionally, the destination region may be determined by a spot detection algorithm. Further optionally, the spot detection algorithm may comprise calculation of a high pass filter, or detection of areas of luminosity and border-to-volume ratios. A method for moving an image element within an image is also provided.

Claims

1. A computer-implemented method comprising:

determining a destination region in a first image including first pixels;

finding a source region in one of;

the first image and a different image, wherein finding the source region includes;

determining a set of destination margin pixels of the destination region;

selecting a candidate source region in one of the first image and the different image;

determining a set of source margin pixels of the candidate source region; and

determining a distance between pixel channel characteristics of the set of destination margin pixels and the set of source margin pixels;

replacing particular pixels of the first pixels of the destination region with copied pixels of the source region;

adapting one or more of the copied pixels in the destination region to provide one or more adapted pixels that visually fit in the destination region, wherein the source region and the destination region have margins, and wherein the adapting is based upon differences between pixel values of the margin of the source region and the margin of the destination region; and

producing a modified image that includes the one or more adapted pixels and pixels of the first pixels that are not the particular pixels replaced.

2. The computer-implemented method of claim 1, wherein determining the distance between the pixel channel characteristics of the set of destination margin pixels and the set of source margin pixels includes determining a distance between vectors of the set of destination margin pixels and the set of source margin pixels, wherein the vectors are one of:

color vectors, luminance vectors, median of luminance vectors, high pass of luminance vectors, and high pass of chroma vectors.

3. The computer-implemented method of claim 1 wherein the candidate source region is a particular candidate source region, and wherein finding the source region comprises:

selecting a plurality of candidate source regions, including the particular candidate source region, in one of the first image and the different image;

detecting a respective set of source margin pixels for each of the plurality of candidate source regions;

determining the particular candidate source region of the plurality of candidate source regions, wherein the particular candidate source region is associated with the set of source margin pixels including a minimum distance between its color vectors and the color vectors of the set of destination margin pixels; and

selecting the particular candidate source region as the source region.

4. The computer-implemented method of claim 1 further comprising applying a highpass filter to the first image before determining the set of destination margin pixels and determining the set of source margin pixels.

5. The computer-implemented method of claim 1 wherein determining the distance between the pixel channel characteristics of the set of destination margin pixels and the set of source margin pixels includes determining a distance between color vectors of the set of destination margin pixels and the set of source margin pixels, and wherein the color vectors are for at least one of:

a Lab color space, and a RGB color space.

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

partitioning the set of source margin pixels into a plurality of intervals;

moving one or more of the intervals by a spatial distance; and

after moving one or more of the intervals, determining whether the distance between the vectors is lower than the distance prior to the partitioning.

7. The computer-implemented method of claim 6, further comprising:

in response to determining that the distance between vectors is reduced, distorting an image area around the source candidate region based on the one or more moved intervals and using the distorted image area as the candidate source region.

8. The computer-implemented method of claim 1 wherein adapting the copied pixels includes iteratively applying a kernel to pixels enclosed by a number of border pixels determined by differences between pixel values of the margin of the source region and the margin of the destination region.

9. The computer-implemented method of claim 1 wherein adapting the copied pixels in the destination region to visually fit in the destination region includes adjusting an illumination of the copied pixels in the destination region, wherein the adjusting comprises multiplying an illumination of the copied pixels in the destination region by a factor that is based on an illumination function, wherein the illumination function is based on an illumination of the destination region and an illumination of the source region.

10. The computer-implemented method of claim 1, wherein the destination region is determined based on at least one of:

a) receiving user input from a user, wherein the user input selects the destination region; and

b) applying a highpass filter to the first image to generate a filtered image,

identifying, in the filtered image, one or more areas having a border-pixel-to-total-pixel count under a predetermined amount, and

selecting a particular one of the one or more identified areas as the destination region.

11. A system comprising:

a storage device; and

at least one processor operative to access the storage device and configured to;

determine a destination region in a first image including first pixels;

find a source region in one of;

the first image and a different image, wherein finding the source region includes;

determining a set of destination margin pixels of the destination region;

selecting a plurality of candidate source regions in one of the first image and the different image;

detecting sets of source margin pixels, wherein each respective set of source margin pixels is for one of the plurality of candidate source regions;

determining a particular candidate source region of the plurality of candidate source regions, wherein the particular candidate source region is associated with a determined set of source margin pixels of the sets of source margin pixels that has a smallest distance between its pixel vectors and the pixel vectors of the set of destination margin pixels; and

selecting the particular candidate source region as the source region;

replace particular pixels of the first pixels of the destination region with copied pixels of the source region; and

adapt one or more of the copied pixels in the destination region to provide one or more adapted pixels that visually fit in the destination region, wherein the source region and the destination region have margins, and wherein the adaptation is based upon differences between pixel values of the margin of the source region and the margin of the destination region; and

producing a modified image that includes the one or more adapted pixels and pixels of the first pixels that are not the particular pixels replaced.

12. The system of claim 11, wherein the pixel vectors are at least one of:

color vectors, luminance vectors, median of luminance vectors, high pass of luminance vectors, and high pass of chroma vectors.

13. A computer-implemented method comprising:

dividing a destination region of a first image into a plurality of sub-pieces along one or more cutting paths, wherein the one or more cutting paths each start and end at different points on a border of the destination region;

finding a respective set of replacement image data corresponding to one or more sub-pieces of the plurality of sub-pieces, wherein each respective set of replacement image data is obtained from a respective source region of one of;

the first image and a different image;

adapting pixels of each respective set of replacement image data to visually fit the corresponding sub-piece of the plurality of sub-pieces of the destination region; and

replacing each of the one or more sub-pieces in the first image with the respective corresponding set of replacement image data to produce a modified image.

14. The computer-implemented method of claim 13, further comprising removing cutting paths that have a distance between the different points that is less than a threshold distance.

15. The computer-implemented method of claim 14, wherein the threshold distance is a particular percentage of an arc length of the border of the destination region.

16. The computer-implemented method of claim 13, further comprising selecting the one or more cutting paths to satisfy one or more particular conditions, wherein the particular conditions include at least one of:

a color difference under a first threshold between a number of pixels closest to the different points on the border of the destination region, and

a distance from the different points to an edge within the border of the destination region, where the distance is over a second threshold.

17. The computer-implemented method of claim 13, further comprising:

expanding at least one sub-piece of the sub-pieces to include additional pixels; and

blending colors of the additional pixels with pixels in the at least one sub-piece.

18. The computer-implemented method of claim 13, further comprising interpolating pixel values along the one or more cutting paths between a start point and an end point of each of the one or more cutting paths to determine one or more pixel values along the one or more cutting paths in the destination region.

19. The computer-implemented method of claim 13, wherein the one or more cutting paths are determined based on a type of image structure at a start and an end point of the cutting path.

20. The computer-implemented method of claim 13, wherein the cutting paths are determined based on an area of the sub-pieces and lengths of the one or more cutting paths.