PatchMatch alone cannot fill a gradient, and more iterations will not help

The symptom

I ported a PatchMatch content-aware fill to the browser to power a watermark remover. On textured backgrounds it looked right. On a smooth gradient it produced a flat rectangle — visibly a patch, exactly the artifact the algorithm exists to avoid.

The test case is deliberately hostile and trivially reproducible: a 600×400 image whose grey value ramps linearly from 26 at the top to 230 at the bottom, with a 140×45 hole punched into it. Because the gradient is vertical, the correct fill for any pixel is just the value of its own row. I sample the dead centre column of the hole — 70 pixels from the nearest real content in either direction — against ground truth.

y=330   filled 184   truth 195   err 11
y=339   filled 182   truth 199   err 17
y=348   filled 182   truth 204   err 22
y=357   filled 182   truth 209   err 27
y=366   filled 182   truth 213   err 31

Mean absolute error 22.9. Look at the filled column rather than the error column: it is the same number all the way down. The algorithm picked one grey and painted the hole with it.

The number that made it obvious

My first instinct was that it had not converged, so I ran it longer:

Three times the work buys one tenth of a grey level. That is not slow convergence. That is converged, to the wrong answer.

And it is worse than it looks, because there is a floor to compare against. Over the hole’s 45 rows the truth ramps from 195 to 217. The best constant you could possibly paint there is 206, and it would score 5.84. PatchMatch scored 22.9.

So the algorithm did not merely fail to follow the gradient. It produced a flat fill that is four times worse than the best flat fill — wrong slope and wrong level. Whatever it was optimising, it was not the thing I wanted.

Two fixes that made it worse

Both of these were measured against an earlier variant of the code whose baseline on this same test was 5.9. The baseline later moved for unrelated reasons; what matters is that each change moved the number hard in the wrong direction, and neither survived.

Widen the search window. If every candidate patch looks equally good, perhaps the right source lies outside the window. The window is the hole plus padding, so I scaled the padding with the hole instead of fixing it at 24 pixels.

5.9 → 21.0. Four times worse. More candidates drawn from a region where the distance function cannot discriminate is just more ways to be confidently wrong.

Onion peel. A standard trick: rather than filling the hole at once, fill the one-patch-wide band at the boundary, mark it known, repeat inwards. Every pixel then has real neighbours to match against.

5.9 → 23.6. Each layer copies from the layer before it, so the first band’s error is inherited and compounded by the next. Eighteen layers deep, the centre is a reconstruction of a reconstruction of a reconstruction.

(The first onion-peel run scored 9.7 because of a bug worth naming: source patches were still read from the pre-fill snapshot of the window, so previously-filled pixels counted as “known” while still containing the watermark. Fixing that honest bug made the score worse. Which is its own small lesson about trusting a number before you trust the code under it.)

Why matching cannot work here

PatchMatch answers one question per hole pixel: which patch elsewhere has surroundings most like mine? That question needs a discriminating answer.

On a vertical gradient it has none. Every patch in the image is a small linear ramp of the same slope. They differ only in mean value — and the mean of a hole pixel’s neighbourhood is dominated by whatever the algorithm itself seeded there. The distance function is nearly flat across candidates, and when a distance function is flat, its argmin is noise.

Worse, it is self-confirming noise. The hole is seeded near some mean, so patches near that mean score best, so the vote writes that mean, so the next iteration’s seed is still that mean. The flat fill is a fixed point of the iteration. That is precisely why more rounds changed nothing — and why the level it settles on has no reason to be the right mean, which is how you end up at 182 instead of 206.

The split

Texture and illumination are not the same kind of problem and do not have the same kind of answer.

High frequency — texture, grain, structure — has no unique correct value. Any plausible continuation will do, and “find a patch whose surroundings resemble mine” is a reasonable way to get one. This is what PatchMatch is genuinely good at.

Low frequency — overall lightness and how it varies across the hole — has exactly one correct answer: the harmonic function matching the boundary, i.e. the solution of Laplace’s equation with the surrounding ring as its Dirichlet condition. That is not a search problem at all. It is a linear system with a unique solution, and searching for it is a category error.

So: run PatchMatch for the texture, solve the equation for the low frequency, add them.

1. PatchMatch fills the hole as before              → v
2. On a coarse grid over the hole:
     T = Laplace solution, boundary = real ring just outside the hole
     L = box-average of v   (PatchMatch's own low frequency)
3. Bilinearly upsample (T − L) and add it to v

Step 3 keeps every high-frequency detail PatchMatch produced and swaps its low frequency for the smooth continuation of the surroundings. This is the core idea of Poisson image editing, applied to a fill rather than a paste.

Results

Max error drops from 33 to 4. Cost at 6 iterations: 216 ms → 280 ms, so roughly 60 ms for a seventy-fold improvement at the hardest sample point.

The iteration count still barely matters — but now for the right reason. The part that was broken was never the part iterations could fix.

End to end in a browser, through a Web Worker, on the same 6,300-pixel hole: 262 ms, zero watermark pixels remaining.

Why the grid is coarse

The Laplace solve runs on a grid of at most 24×24, not at full resolution. Two reasons, and the second is the one that matters.

Low frequency is smooth by definition, so 24 samples across the hole describe it to well under one grey level. That is the easy reason.

The real reason is convergence. Gauss–Seidel propagates boundary information one cell per sweep, so a region n cells across needs on the order of n² sweeps. At 24 cells that is a few hundred sweeps over 576 cells — microseconds. At the hole’s true 140-pixel width it would be tens of thousands of sweeps over 6,300 pixels, slower than the PatchMatch it is correcting. Solving the smooth part small and interpolating is not an approximation you tolerate; it is what makes the method cheap enough to ship.

The bug underneath all of it

While chasing this I found a separate failure that was quietly ruining every large hole.

The patch distance function originally skipped every pixel still inside the hole, counting only real observations. Sensible — until the hole is bigger than a patch. Then an interior pixel’s entire (2P+1)² neighbourhood lies inside the hole, nothing is counted, and the function returns Infinity. The update rule is if (err < best), and Infinity < Infinity is false. Those pixels kept whatever source random initialisation handed them, forever. Not a flat fill — noise, sampled uniformly from the image.

The fix is to include hole pixels at reduced weight (0.3 here) rather than excluding them. They are the algorithm’s current guess, which is weak evidence — and weak evidence beats a comparison that can never be true.

That one is worth internalising as a shape rather than a specific bug. A sentinel meaning “no information” will usually fail a strict comparison against itself, and a loop that only updates on strict improvement will silently freeze on it.

Where this still fails

None of this makes the algorithm imagine content. It relocates it. A watermark over sky, grass, wood, a wall or a gradient comes out clean. A watermark over a face does not become that half of the face; one across a line of text does not become those letters. The low-frequency correction makes the result fit its surroundings. It cannot make it correct.

The implementation is about 300 lines of dependency-free TypeScript, runs entirely in a Web Worker, and powers the watermark remover here. No upload, no account, no credits — the image never leaves your machine.