How content-aware fill decides what goes in the hole

You have a photograph with a region marked as unknown. Every pixel outside that region is known. The job is to choose values for the unknown pixels such that somebody looking at the result cannot tell where the boundary was. Note what the job is not: it is not to recover what was there. Those values are absent from the data, and no quantity of arithmetic conjures them back. Every method below is a different answer to the question what would be consistent with the surroundings, and consistency is a much weaker claim than truth.

The methods divide on where they get their answer. One copies from elsewhere in the same photograph. One propagates inward from the boundary. One has read several million other photographs and produces something statistically typical. Each is better than the others at something, and the third is the only one that can lie convincingly.

Cut the photograph into overlapping squares — seven pixels a side is a good default. For every square that overlaps the unknown region, find the square of fully-known picture that it most resembles, and use that one's contents as a vote for what belongs there. Each unknown pixel is covered by forty-nine squares, so it receives forty-nine votes; average them, weighted by how good each match was, and you have a fill.

The expensive part is finding the matches. Comparing every square to every other square in a twelve-megapixel photograph is not something anybody is going to wait for. The randomised search that makes this tractable is beautifully simple and rests on one observation: good matches are contagious. Start with a random guess for every square. Then sweep across the image; at each square, try the match your neighbour found, shifted by one pixel. If your neighbour found a good piece of sand, the sand next to it is probably good for you. Most of the improvement in the whole algorithm comes from that one step. Then, to stop everything settling into one lucky corner, try a handful of random offsets at exponentially shrinking distances. Five sweeps of propagate-and-jump get within a few per cent of the true nearest neighbour for a rounding error of the cost.

Two refinements matter in practice. The first is the pyramid: run the whole thing at a sixteenth resolution, carry the answer up, run it again at an eighth, and so on. Without it, the centre of a wide region is matching against its own invented pixels from the very first iteration. The second is determinism: the random number generator is seeded from a fixed value, so painting the same region twice gives the same result twice. A tool that produced a different answer each time would be impossible to reason about and impossible to complain about usefully.

• Excellent on texture with no long-range structure: sand, gravel, grass, water, foliage, plaster, knitwear, tarmac.
• Poor wherever a line, an edge or a repeating pattern in perspective crosses the region, because a square of railing resembles another square of railing regardless of where the railing is going.
• Fails visibly rather than convincingly. A bad exemplar fill looks like smeared or duplicated texture, which anyone can see.

The second method treats the region as a hole in a sheet and freezes it shut from the edges. Pixels are settled in order of their distance from known picture — nearest first — and each is given a weighted mean of the already-settled pixels lying within a short radius. The weights carry the whole method. A neighbour in the direction the boundary is moving is trusted further than one off to the side, and that preference is what drags a gradient across the gap rather than levelling it. A neighbour that settled at about the same moment counts for more than one that settled much earlier, which keeps an edge crossing a narrow gap joined up.

On a region two or three pixels wide this is not merely adequate, it is the better answer: every pixel has real information within a couple of steps, the average is drawn from genuine picture, and it costs a few milliseconds. On a region a hundred pixels wide the same arithmetic produces the soft grey-brown bruise everyone recognises as a failed removal, because the middle is averaging averages of averages. Knowing which of those two situations you are in is the entire trick, and the tool measures it: the half-width of the widest part of the region decides which engine gets the work.

A convolutional inpainting network is trained on a few million photographs with rectangles cut out of them, and learns a mapping from the surroundings to the missing contents. The architectures that work well at this use a Fourier-domain convolution, which gives every layer a view of the whole image rather than a local window — and that, rather than raw capacity, is what lets them continue a railing or a horizon across a gap. They know what a line is, in the only sense that matters here: they have seen enough of them to continue one.

The costs are specific. Quantised to eight-bit integers, the weights for a usable model land somewhere between forty and ninety megabytes, which is a real download on a real connection and has to be stated in megabytes before it starts rather than discovered from a progress bar. It cannot be run over a whole large photograph, so the region's bounding box is tiled into squares with an overlap that gets blended away. And on a browser without WebGPU, falling back to WebAssembly, a single tile takes seconds — so a three-tile removal on a mid-range phone is fifteen seconds of waiting for a result that, on sand, would have been better from the patch search.

The last difference is the one worth thinking about longest. A learned fill can be wrong confidently. It will produce a crisp, plausible, entirely fictional continuation, and there is nothing in the result that announces itself as invented. The patch search cannot do that; when it fails, it smears. If the photograph is going to be printed, filed, or shown to somebody as a record of something, a failure you can see is worth a great deal more than one you cannot.

Take a photograph of somebody standing in front of an iron railing, with the railing running behind them at an angle, and paint them out. The patch search returns railing — genuine railing, copied from twenty pixels away, at the wrong angle, so the bars do not meet. The marching fill returns a smooth brown-grey band where the railing was, because it is averaging bars and gaps together. The network returns a railing that continues correctly for most of the width and then drifts, because the tile it was working in could not see both ends.

The lesson is not that the tools are bad. It is that a removal whose region crosses structure is a hard problem for everything, and the practical move is to change the problem: paint a smaller region that stops at the railing, do it in two passes, or accept a crop. That is the subject of the guide on straight lines.

Is this the same thing Photoshop does?

The exemplar engine here is built on the same idea as the content-aware fill that shipped in Photoshop CS5 — a randomised patch correspondence search, published as PatchMatch in 2009 — and the differences are in the tuning rather than the principle. The later neural fills in commercial editors are a different family altogether, and the section on networks below is about those.

Why does it look worse on a big region than on a small one?

Because the middle of a large region cannot see any intact picture at all. Every patch overlapping it is matching against other invented pixels, so the search is agreeing with itself. The pyramid is what stops that being hopeless: at a low enough resolution the region is small again, a rough answer is found there, and each finer level refines rather than invents. It is why a large fill takes several times as long as a small one and still comes out softer.

Why can I not just make it sharper afterwards?

Sharpening raises local contrast; it does not put back detail that was never synthesised. On a filled region it will amplify whatever the search produced, including the seams. If the fill came out soft the fix is a smaller region, a different engine, or accepting that the answer is not in the file.