Image region filling by exemplar-based inpainting

• US 20040164996A1
• Filed: 06/03/2003
• Published: 08/26/2004
• Est. Priority Date: 02/24/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Criminisi, Antonio, Toyama, Kentaro, Blake, Andrew, Perez, Patrick, Gangnet, Michel
• Granted Patent: US 6,987,520 B2
• Time in Patent Office: Days
• US Class Current: 345/619
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture

Abstract

An example-based filling system identifies appropriate filling material to replace a destination region in an image and fills the destination region using this material, thereby alleviating or minimizing the amount of manual editing required to fill a destination region in image. Tiles of image data are borrowed from the proximity of the destination region or some other source to generate new image data to fill in the region. Destination regions may be designated by user input (e.g., selection of an image region by a user) or by other means (e.g., specification of a color or feature to be replaced). In addition, the order in which the destination region is filled by example tiles may be configured to emphasize the continuity of linear structures and composite textures using a type of isophote-driven image-sampling process.

Claims

1. A method comprising:

computing a fill priority for each point on a fill front of a destination region in an image;

filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front;

defining a new fill front of the destination region, excluding the filled destination file;

computing a fill priority for each point on the new fill front; and

filling a destination tile associated with a point on the new fill front having the highest fill priority associated with the new fill front.

2. The method of claim 1 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a confidence factor for a point on the fill front; and

computing the fill priority for the point on the fill front based on the confidence factor.

3. The method of claim 1 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a confidence factor for a point on the fill front, wherein the confidence factor represents a measure of filled image data surrounding the point; and

computing the fill priority for the point on the fill front based on the confidence factor as a component.

4. The method of claim 1 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a strength factor for a point on the fill front; and

computing the fill priority for the point on the fill front based on the strength factor.

5. The method of claim 1 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a strength factor for a point on the fill front, wherein the strength factor represents a strength of an isophote intersecting the fill front at the point; and

computing the fill priority for the point on the fill front based on the strength factor.

6. The method of claim 1 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a strength factor for a point on the fill front;

computing a confidence factor for the point on the fill front; and

computing the fill priority for the point on the fill front based on the strength factor and the confidence factor.

7. The method of claim 1 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a strength factor for a point on the fill front;

computing a confidence factor for the point on the fill front; and

computing the fill priority for the point on the fill front to include a product of the strength factor and the confidence factor.

8. The method of claim 1 wherein the destination tile associated with the point on the fill front has a different size than the destination tile associated with the point on the new fill front.

9. The method of claim 1 wherein the destination tile associated with the point on the fill front has a different shape than the destination tile associated with to the point on the new fill front.

10. A method comprising:

computing a fill priority for each point on a fill front of a destination region in an image, the fill priority being dependent upon a confidence factor and a strength factor; and

filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front, before filling any other point on the fill front.

11. The method of claim 10 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the confidence factor for a point on the fill front, the confidence factor being defined as

$C<br><br>\left(p\right)=\frac{\underset{q\in <br><br>{\mathrm{\Psi <br><br>}}_p\bigcap <br><br>\stackrel{\_}{\mathrm{\Omega <br><br>}}}{\sum <br><br>}<br><br>C<br><br>\left(q\right)}{<br><br>{\mathrm{\Psi <br><br>}}_p<br><br>};<br><br>\mathrm{and}$

computing the fill priority for the point on the fill front based on the confidence factor.

12. The method of claim 10 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the confidence factor for a point on the fill front, wherein the confidence factor represents a measure of filled image data surrounding the point; and

computing the fill priority for the point on the fill front based on the confidence factor as a component.

13. The method of claim 10 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the strength factor for a point on the fill front, the strength factor being defined as

$S<br><br>\left(p\right)=\frac{<br><br>\nabla <br><br>I_p^{\perp <br><br>}·<br><br>n_p<br><br>}{\mathrm{\alpha <br><br>}};<br><br>\mathrm{and}$

computing the fill priority for the point on the fill front based on the strength factor.

14. The method of claim 10 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the strength factor for a point on the fill front, wherein the strength factor represents a strength of an isophote intersecting the fill front at the point; and

computing the fill priority for the point on the fill front based on the strength factor.

15. The method of claim 10 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the strength factor for a point on the fill front;

computing the confidence factor for the point on the fill front; and

computing the fill priority for the point on the fill front to include a product of the strength factor and the confidence factor.

16. A computer program product encoding a computer program for executing on a computer system a computer process, the computer process comprising:

computing a fill priority for each point on a fill front of a destination region in an image;

filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front;

defining a new fill front of the destination region, excluding the filled destination file;

computing a fill priority for each point on the new fill front; and

filling a destination tile associated with a point on the new fill front having the highest fill priority associated with the new fill front.

17. The computer program product of claim 16 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a confidence factor for a point on the fill front; and

computing the fill priority for the point on the fill front based on the confidence factor.

18. The computer program product of claim 16 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a confidence factor for a point on the fill front, wherein the confidence factor represents a measure of filled image data surrounding the point; and

computing the fill priority for the point on the fill front based on the confidence factor as a component.

19. The computer program product of claim 16 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a strength factor for a point on the fill front; and

computing the fill priority for the point on the fill front based on the strength factor.

20. The computer program product of claim 16 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a strength factor for a point on the fill front, wherein the strength factor represents a strength of an isophote intersecting the fill front at the point; and

computing the fill priority for the point on the fill front based on the strength factor.

21. The computer program product of claim 16 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a strength factor for a point on the fill front;

computing a confidence factor for the point on the fill front; and

computing the fill priority for the point on the fill front based on the strength factor and the confidence factor.

22. The computer program product of claim 16 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing a strength factor for a point on the fill front;

computing a confidence factor for the point on the fill front; and

computing the fill priority for the point on the fill front to include a product of the strength factor and the confidence factor.

23. The computer program product of claim 16 wherein the destination tile associated with the point on the fill front has a different size than the destination tile associated with the point on the new fill front.

24. The computer program product of claim 16 wherein the destination tile associated with the point on the fill front has a different shape than the destination tile associated with the point on the new fill front.

25. A computer program product encoding a computer program for executing on a computer system a computer process, the computer process comprising:

computing a fill priority for each point on a fill front of a destination region in an image, the fill priority being dependent upon a confidence factor and a strength factor; and

filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front, before filling any other point on the fill front.

26. The computer program product of claim 25 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the confidence factor for a point on the fill front, the confidence factor being defined as

$C<br><br>\left(p\right)=\frac{\underset{q\in <br><br>{\mathrm{\Psi <br><br>}}_p\bigcap <br><br>\stackrel{\_}{\mathrm{\Omega <br><br>}}}{\sum <br><br>}<br><br>C<br><br>\left(q\right)}{<br><br>{\mathrm{\Psi <br><br>}}_p<br><br>};<br><br>\mathrm{and}$

computing the fill priority for the point on the fill front based on the confidence factor.

27. The computer program product of claim 25 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the confidence factor for a point on the fill front, wherein the confidence factor represents a measure of filled image data surrounding the point; and

computing the fill priority for the point on the fill front based on the confidence factor as a component.

28. The computer program product of claim 25 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the strength factor for a point on the fill front, the strength factor being defined as

$S<br><br>\left(p\right)=\frac{<br><br>\nabla <br><br>I_p^{\perp <br><br>}·<br><br>n_p<br><br>}{\mathrm{\alpha <br><br>}};<br><br>\mathrm{and}$

computing the fill priority for the point on the fill front based on the strength factor.

29. The computer program product of claim 25 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the strength factor for a point on the fill front, wherein the strength factor represents a strength of an isophote intersecting the fill front at the point; and

computing the fill priority for the point on the fill front based on the strength factor.

30. The computer program product of claim 25 wherein the operation of computing a fill priority for each point on a fill front comprises:

computing the strength factor for a point on the fill front;

computing the confidence factor for the point on the fill front; and

computing the fill priority for the point on the fill front to include a product of the strength factor and the confidence factor.

31. A system comprising:

a priority module computing a fill priority for each point on a fill front of a destination region in an image;

a filling module filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front;

a destination region processing module defining a new fill front of the destination region, excluding the filled destination file, wherein the priority module further computes a fill priority for each point on the new fill front and the filling module further fills a destination tile associated with a point on the new fill front having the highest fill priority associated with the new fill front.

32. A system comprising:

a priority module computing a fill priority for each point on a fill front of a destination region in an image, the fill priority being dependent upon a confidence factor and a strength factor; and

a filling module filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front, before filling any other point on the fill front.

33. A method comprising:

computing a fill priority for each point in a destination region in an image;

filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front;

defining a new fill front of the destination region, excluding the filled destination file;

computing a fill priority for each point on the new fill front; and

filling a destination tile associated with a point on the new fill front having the highest fill priority associated with the new fill front.

34. A method comprising:

computing a fill priority for each point in a destination region in an image, the fill priority being dependent upon a confidence factor and a strength factor; and

filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front, before filling any other point on the fill front.

35. A computer program product encoding a computer program for executing on a computer system a computer process, the computer process comprising:

computing a fill priority for each point in a destination region in an image;

filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front;

defining a new fill front of the destination region, excluding the filled destination file;

computing a fill priority for each point on the new fill front; and

filling a destination tile associated with a point on the new fill front having the highest fill priority associated with the new fill front.

36. A computer program product encoding a computer program for executing on a computer system a computer process, the computer process comprising:

computing a fill priority for each point in a destination region in an image, the fill priority being dependent upon a confidence factor and a strength factor; and

filling a destination tile associated with a point on the fill front having the highest fill priority associated with the fill front, before filling any other point on the fill front.