Image Inpainting: Filling Missing Regions

The monsoon cloud problem

Every monsoon, optical Earth-observation satellites like ISRO's Resourcesat-2A and Cartosat imaging platforms fly over India and come back with scenes that are partly useless: thick cloud cover blanks out large patches of farmland, riverbanks, and flood zones exactly when agencies like the National Remote Sensing Centre need that data most — for crop-acreage estimation, reservoir monitoring, or flood-extent mapping during the flood itself. The satellite still records a full grid of pixels, but a contiguous region of that grid carries no usable ground signal, only cloud. Before that image can feed an agriculture or disaster-response pipeline, something has to estimate what those obscured pixels would have shown, using only the untouched pixels around the gap and whatever prior knowledge is available about how images are structured.

Strip away the satellite framing and you have the general problem this chapter is about: given an image with a region of missing or corrupted pixels, reconstruct plausible values for that region using the rest of the image (and, in modern systems, everything the algorithm has learned from millions of other images). The same problem shows up when you remove a watermark, restore a torn photograph, delete an object from a phone photo, or repair a scratch on an old scanned negative. All of these are instances of image inpainting.

Formalizing the problem

Let an image be a function I defined on a pixel grid D. Let Ω ⊂ D (the "hole") be the set of pixels whose values are missing or to be replaced, and let δΩ denote its boundary — the pixels just outside Ω whose values are known and adjacent to unknown pixels. The known region is D \ Ω. Inpainting is the task of producing values Î(p) for every p ∈ Ω such that the completed image looks like a plausible continuation of I on D \ Ω — smooth where the surrounding image is smooth, sharp where an edge should cross the hole, and textured where a texture should continue.

There is no single correct answer to this problem in general — many different completions of a hole can look equally plausible — which is exactly why several genuinely different families of algorithms exist, each encoding a different assumption about what "plausible" means. This chapter builds one of them, diffusion-based (harmonic) inpainting, from first principles with a complete worked example, then explains two further families — exemplar-based and learned inpainting — that relax the assumptions harmonic inpainting cannot satisfy.

Approach 1: diffusion-based inpainting solves an equation, not a filter

The oldest rigorous approach treats each unknown pixel as if the image intensity were a smooth physical quantity, like temperature, diffusing across the hole from its known boundary. The mathematical object that describes a stationary diffusion state is Laplace's equation:

∇²I(p) = 0 for all p ∈ Ω, subject to I(p) = known value for p ∈ δΩ

A function satisfying ∇²I = 0 is called harmonic. Harmonic functions have a defining property, the mean value property: the value at any interior point equals the average of the values on any circle (or, discretely, any neighbourhood) centred at that point. On a pixel grid using the standard 4-neighbour discrete Laplacian, this collapses to a wonderfully simple local rule — for every unknown pixel p with neighbours North, South, East, West:

I(p) = [ I(N) + I(S) + I(E) + I(W) ] / 4

When a neighbour is itself unknown, its own value depends on p, so no unknown pixel can be computed in one shot — the whole hole is a coupled system of simultaneous equations. The standard way to solve it is Gauss–Seidel iteration: initialise every unknown pixel to some guess (zero is fine), then repeatedly sweep through the unknown pixels, each time overwriting a pixel with the average of its current neighbour values (using the most recently updated value whenever a neighbour has already been revisited in that sweep). Because the update matrix for this system is diagonally dominant, Gauss–Seidel is guaranteed to converge to the unique exact solution regardless of the initial guess or the order of the sweep.

Worked example: solving a two-pixel hole by hand

Take a 5×5 grayscale patch. Two adjacent pixels are missing, at grid positions (row 2, col 2) and (row 2, col 3) — call them x₁ and x₂. Every other pixel needed for the computation is known:

• Neighbours of x₁: North (row1,col2) = 180, South (row3,col2) = 160, West (row2,col1) = 150, East = x₂ (unknown)
• Neighbours of x₂: North (row1,col3) = 190, South (row3,col3) = 170, East (row2,col4) = 200, West = x₁ (unknown)

The coupled equations are:

x₁ = (180 + 160 + 150 + x₂) / 4 = (490 + x₂) / 4
x₂ = (190 + 170 + x₁ + 200) / 4 = (560 + x₁) / 4

Exact solution by substitution. Substitute the second equation into the first:

x₁ = [490 + (560 + x₁)/4] / 4 = 122.5 + 35 + x₁/16 = 157.5 + x₁/16

x₁ − x₁/16 = 157.5 → (15/16)·x₁ = 157.5 → x₁ = 157.5 × 16/15 = 168.0

x₂ = (560 + 168.0)/4 = 728/4 = 182.0

Check both equations: x₁ = (490+182)/4 = 672/4 = 168 ✓ and x₂ = (560+168)/4 = 728/4 = 182 ✓. The exact harmonic values are x₁ = 168, x₂ = 182.

Now trace Gauss–Seidel from a zero initial guess, updating x₁ first, then x₂, each sweep:

Each sweep shrinks the error by a factor of roughly 1/16 (a 1/4 coupling through x₂ back into x₁, applied twice), so convergence to sub-pixel precision takes only a handful of sweeps for a hole this small. Below is a direct, self-contained implementation of the same rule; running it on this exact grid reproduces the table above exactly, because the code updates pixels in the same row-major order used in the hand trace.

def harmonic_inpaint(image, mask, iterations=500):
    """
    image : 2D list of pixel intensities (values at mask==True are ignored)
    mask  : 2D list of booleans, True where the pixel is missing (in Omega)
    Returns a new grid where every masked pixel has been replaced by the
    Gauss-Seidel solution of the discrete Laplace equation.
    """
    img = [row[:] for row in image]
    rows, cols = len(img), len(img[0])
    holes = [(r, c) for r in range(rows) for c in range(cols) if mask[r][c]]

    for _ in range(iterations):
        for (r, c) in holes:
            total, n = 0.0, 0
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    total += img[nr][nc]
                    n += 1
            img[r][c] = total / n
    return img

grid = [
    [0,   0,   0,   0,   0],
    [0,   0, 180, 190,   0],
    [0, 150,   0,   0, 200],
    [0,   0, 160, 170,   0],
    [0,   0,   0,   0,   0],
]
mask = [[False] * 5 for _ in range(5)]
mask[2][2] = True
mask[2][3] = True

result = harmonic_inpaint(grid, mask, iterations=500)
print(round(result[2][2], 2), round(result[2][3], 2))
# 168.0 182.0

The diagram below shows the same grid: the two dashed orange cells are the unknowns, the solid blue cells are the known boundary values feeding the equations, and the arrows are the four terms each unknown pixel averages together. The two purple arrows show the one dependency that makes this a system rather than a one-step lookup — x₁ and x₂ each need the other's (evolving) value.

Common misconception: "filling a hole means painting it with the average colour around it"

Students who first meet inpainting almost always guess this method: take every known boundary pixel, compute one global average, and paint the entire hole that flat colour. Run that on the worked example — the six known values are 180, 190, 150, 200, 160, 170, which sum to 1050 and average to 175 — and you would fill both x₁ and x₂ with 175.

That is measurably wrong, and the harmonic solution shows exactly why. x₁'s own three known neighbours (150, 180, 160) average to 163.3, while x₂'s three known neighbours (190, 170, 200) average to 186.7 — the image is genuinely brighter on the right side of the hole than the left. A single global average erases that gradient and paints both pixels identically, producing a flat patch with a visible seam at both edges of the hole. The Gauss–Seidel solution instead lands at 168 and 182: close to each pixel's own local neighbourhood average, pulled slightly toward each other by their mutual coupling, exactly continuing the brightness gradient across the hole. The rule "average the neighbours" is correct — but it must be applied per pixel, using that pixel's own local neighbours, solved as a coupled system, not once globally over the whole boundary. Collapsing local, position-dependent averaging into one global constant is precisely the mistake harmonic inpainting is built to avoid.

It's worth noting harmonic inpainting has its own, different limitation: because a harmonic function is by construction the smoothest surface matching the boundary values (it minimises Dirichlet energy, the sum of squared gradients), it actively resists sharp changes. A straight edge or a repeating texture that should cross the hole gets diffused into a soft blur instead of continuing cleanly — correct behaviour for a scratch on a plain sky, wrong behaviour for a scratch across a brick wall or a fence line. That gap is what the next two families of methods exist to close.

Approach 2: exemplar-based inpainting copies whole patches

Criminisi, Pérez and Toyama's exemplar-based algorithm (2004) abandons per-pixel averaging and instead fills the hole one small patch at a time, copying each patch wholesale from elsewhere in the same known image. Working only along the current fill front δΩ, every candidate patch Ψp centred on a front pixel p is scored by a priority:

P(p) = C(p) · D(p)

C(p), the confidence term, is the fraction of already-known pixels inside Ψp — it starts at 1 everywhere outside the hole and 0 inside, so patches deeper into already-filled territory get higher confidence as filling proceeds. D(p), the data term, measures how strongly an image edge (an isophote) is hitting the boundary at p: it is large where a line or contour meets δΩ nearly perpendicular to the boundary, small where the boundary runs through flat texture. Multiplying the two terms means the algorithm always fills the patch that is both most reliably known and most likely to be continuing a straight structure — in practice this makes edges and object boundaries get completed first, before flat interior regions, which is exactly what keeps straight lines straight across the repaired hole.

Once the highest-priority patch Ψp̂ is chosen, the algorithm searches the entire known region for the patch Ψq that minimises sum-of-squared-differences over the already-known pixels of Ψp̂, then copies Ψq's pixel values into the unknown part of Ψp̂ and marks those pixels confident. Because whole patches of real, already-observed texture are copied — not synthesised pixel by pixel — this method reproduces repeating brick, wood grain, or grass with a fidelity harmonic diffusion cannot match. Its Achilles' heel is equally direct: it can only ever reuse content that already exists somewhere in that same image. Remove someone's eye from a photo and there is no "known" eye patch anywhere else in the frame to copy.

An exhaustive SSD search over every possible source patch is expensive; Adobe's original Content-Aware Fill (2010) made this practical in real time using PatchMatch (Barnes et al., 2009), a randomised nearest-neighbour search that starts from a few guesses and rapidly propagates good matches to neighbouring patches, turning an effectively quadratic search into something close to linear time.

Approach 3: learned inpainting fills with content it has never seen in this image

Both previous methods are fundamentally limited to material already present in the one image being repaired. Deep-learning approaches remove that limit by training on millions of images so the network carries a prior about what images in general look like. Context Encoders (Pathak et al., 2016) train an encoder–decoder CNN to reconstruct large, randomly masked regions, using a combined L2 reconstruction loss and an adversarial loss from a discriminator that penalises blurry or implausible completions — the L2 term keeps the output close to the true pixels, the adversarial term pushes the network to commit to sharp, realistic detail rather than the safe, blurry average an L2-only loss would produce.

A more subtle fix targets the convolution itself: ordinary convolutions treat the arbitrary values sitting in a masked-out region as if they were real data, which smears incorrect information as soon as the receptive field straddles the hole boundary. Partial convolutions (Liu et al., 2018) renormalise each convolution output by the fraction of valid, unmasked pixels under the kernel, and shrink the mask by one pixel after every layer — so information only ever flows outward from genuinely known pixels, layer by layer, until the mask disappears.

The current state of the art, used in tools like Adobe's Generative Fill and Google's Magic Eraser, runs the masked region through a diffusion model's reverse denoising process, conditioned on the known pixels and often a text prompt. Instead of copying or locally averaging existing pixels, the model synthesises entirely new content consistent with everything it learned across its training set — it can invent a plausible eye, a plausible cloud-free field, or a plausible missing letter on a sign, none of which existed anywhere in the source image.

Active recall

Attempt each question before reading its answer.

1. In one dimension, a chain of unknown pixels is each defined as the average of its two neighbours, with known values at both ends. What shape does the resulting sequence trace, and why?
2. Suppose the two known boundary values at the ends of a 1-D chain are 100 and 130, with three unknown pixels between them. Find their harmonic values.
3. Why does harmonic inpainting reconstruct a smoothly shaded sky correctly but blur a sharp fence line crossing the same hole?
4. In the worked 5×5 example, if the hole grew to a full 2×2 block (four unknown pixels instead of two), would Gauss–Seidel still converge to a unique answer? What changes about the iteration?
5. Why does Criminisi's algorithm fill patches along strong edges before it fills patches in flat texture, and what would go wrong if it filled in a fixed left-to-right pixel order instead?
6. A friend says "Photoshop's Content-Aware Fill and Photoshop's Generative Fill are basically the same algorithm, just newer." Is this accurate?

Answers

1. A straight line. If xᵢ = (xᵢ₋₁ + xᵢ₊₁)/2 for every interior point, the second difference xᵢ₊₁ − 2xᵢ + xᵢ₋₁ is zero everywhere, which is exactly the discrete condition for the sequence to be arithmetic (constant first difference). The discrete Laplace equation in 1-D is discrete linear interpolation between the two boundary values — the 2-D harmonic surface used in this chapter is the direct generalisation of that straight line to a smoothest-possible 2-D surface matching the boundary.

2. With four gaps of equal size between 100 and 130 (a difference of 30 spread over 4 steps of 7.5 each): the three unknowns are 100+7.5=107.5, 100+15=115, and 100+22.5=122.5. These are exactly the harmonic (Gauss–Seidel) solution, confirmed by checking each equals the average of its neighbours, e.g. 115 = (107.5+122.5)/2 ✓.

3. A harmonic function is, by construction, the smoothest possible surface consistent with the boundary — it minimises the sum of squared gradients (Dirichlet energy) over the hole. A smoothly shaded sky already has near-zero gradient, so the smoothest continuation matches it almost exactly. A sharp fence line has a large gradient concentrated at one location; the smoothest surface spreads that same total brightness change gradually across the whole width of the hole instead of keeping it sharp at one place, which is visually a blur.

4. Yes — the discrete Laplace system remains diagonally dominant for any hole shape, so Gauss–Seidel still converges to the unique harmonic solution. What changes is speed: the centre pixel of a 2×2 block is now two steps from the nearest known boundary pixel in every direction rather than one, so information from the boundary takes more sweeps to reach and "settle" the interior pixels — convergence to a fixed tolerance grows roughly with the square of the hole's diameter, since each additional pixel of distance from the boundary both slows propagation and adds another coupled unknown to the system.

5. The data term D(p) is large exactly where an isophote (a line of constant intensity — in practice, an edge) meets the fill front nearly head-on, so multiplying it into the priority pushes edge-crossing patches to be filled first, before their neighbouring flat-texture patches compete for the same pixels. If patches were instead filled in a fixed raster order, a line entering the hole from the top and a line entering from the side would be filled out of sync with each other, and whichever line's patch is filled first would already have set pixel values that the second line's search has to match against — usually breaking the second line's continuity, since the algorithm has no mechanism to revisit and correct an already-placed patch.

6. No. The original Content-Aware Fill (2010) is exemplar-based — accelerated with PatchMatch — and can only ever reuse pixels that already exist somewhere else in that same photo; ask it to fill a gap where no similar texture exists anywhere in frame and it visibly fails or smears. Generative Fill is diffusion-model based: it denoises the masked region conditioned on the surrounding pixels and a text prompt, drawing on patterns learned from a training set of billions of images, so it can synthesise content — an object, a texture, a background — that never appeared anywhere in the source photo at all. They solve the same stated problem with structurally different mechanisms and different failure modes.

Think About It

Think about this: How would you explain image inpainting: filling missing regions to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind image inpainting: filling missing regions, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.