Low memory content aware fill

1. A method performed by data processing apparatus, the method comprising:

receiving a first image at a first resolution, the first image having a first hole therein;

generating, based on the first image, a second image at a second resolution lower than the first resolution, the second image having a second hole therein corresponding to the first hole;

identifying, in the second image, one or more second-image source patches for the second hole;

identifying at least one first-image source patch in the first image based on a location of the identified second-image source patch;

storing the identified at least one first-image source patch in memory;

identifying fill content in the at least one first-image source patch stored in the memory; and

placing the identified fill content in the first hole.

2. The method of claim 1 , wherein the first hole comprises a plurality of tiles; and

wherein i) the identification of the at least one first-image source patch in the first image; ii) the storing of the identified at least one first-image source patch; and iii) the placement of the identified fill content are performed for each first-hole tile.

3. The method of claim 2 , wherein one or more portions of some of the first-hole tiles overlap with one or more portions of other first-hole tiles, the method further comprising:

feathering at least one of the portions of first-hole tiles that overlap.

4. The method of claim 1 , the method further comprising:

determining that the first image cannot be stored in memory; and

creating the second image by progressively reducing the resolution of the first image until the second image can be stored in memory.

5. The method of claim 1 , wherein identifying the first-image source patch comprises:

generating a map of the first-image source patches, the map indicating a count of the times each source patch is identified;

generating, for each entry in the map of the first-image of source patches, a summation value that aggregates that entry and neighboring entries; and

identifying a highest summation value.

6. The method of claim 5 , wherein generating the summation value comprises convolving the map of the first-image source patches.

7. The method of claim 1 , wherein the fill content is identified using image content bordering that part of the hole as a constraint.

8. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving a first image at a first resolution, the first image having a first hole therein; generating, based on the first image, a second image at a second resolution lower than the first resolution, the second image having a second hole therein corresponding to the first hole;

identifying, in the second image, one or more second-image source patches for the second hole;

identifying at least one first-image source patch in the first image based on a location of the identified second-image source patch;

storing the identified at least one first-image source patch in memory;

identifying fill content in the at least one first-image source patch stored in the memory; and

placing the identified fill content in the first hole.

9. The medium of claim 8 , wherein the first hole comprises a plurality of tiles; and

wherein i) identifying at least one first-image source patch in the first image based on a location of the identified second-image source patch; ii) storing the identified at least one first-image source patch in memory; and iii) placing the identified fill content in the first hole is repeated for each first-hole tiles.

10. The medium of claim 9 , wherein some portions of some of the first-hole tiles overlap with some portions of other first-hole tiles, the method further comprising:

feathering the portions of first-hole tiles that overlap.

11. The medium of claim 9 , the operations further comprising:

determining that the first image cannot be stored in memory; and

creating the second image by progressively reducing the resolution of the first image until the second image can be stored in memory.

12. The medium of claim 9 , wherein identifying the first-image source patch comprises:

generating a map of the first-image source patches, the map indicating a count of the times each source patch is identified;

generating, for each entry in the map of the first-image of source patches, a summation value that aggregates that entry and neighboring entries; and

identifying a highest summation value.

13. The medium of claim 12 , wherein generating the summation value comprises convolving the map of the first-image source patches.

14. The medium of claim 9 , wherein the fill content is identified using image content bordering the hole as a constraint.

15. A system comprising:

a user device; and

one or more computers operable to interact with the device and to perform operations comprising:

receiving a first image at a first resolution, the first image having a first hole therein;

generating, based on the first image, a second image at a second resolution lower than the first resolution, the second image having a second hole therein corresponding to the first hole;

identifying, in the second image, one or more second-image source patches for the second hole;

identifying at least one first-image source patch in the first image based on a location of the identified second-image source patch;

storing the identified at least one first-image source patch in memory;

identifying fill content in the at least one first-image source patch stored in the memory; and

placing the identified fill content in the first hole.

16. The system of claim 15 , wherein the one or more computers comprise a server operable to interact with the device through a data communication network, and the device is operable to interact with the server as a client.

17. The system of claim 16 , wherein the device comprises a personal computer running a web browser, a mobile telephone running a web browser, a tablet computer running a web browser.

18. The system of claim 15 , wherein the one or more computers consist of one computer, the device is a user interface device, and the one computer comprises the user interface device.