Motivation
A scratch or a failed sensor may leave some pixels unknown while nearby measurements remain usable. Filling the missing locations with zeros treats absence as a measured black intensity. A different model asks for a smooth image that agrees with the known samples. On a pixel grid, the simplest version measures roughness by squared differences across neighboring pixels. Its minimizer extends the observed data into the damaged region.
Common mistake
(Filling missing pixels with zeros)
Zero is a measured intensity, not a code for “unknown”. On the path with observed values , the zero fill creates two artificial edges and has energy , while the constant fill agrees with every observation and has energy .
This construction is useful because its assumptions are visible. It is appropriate when a gradual intensity transition is plausible; it does not know whether an edge or texture ought to continue behind the scratch. We study a finite weighted graph rather than taking an unexplained continuum limit. The chosen graph and weights describe what “neighboring” means.
Definitions
Let be a finite undirected graph. Each edge has weight ; absent edges have weight zero. Split the vertices into observed pixels and unknown pixels . The measured values are fixed for . For an extension define the Dirichlet energy, with each undirected edge counted once, by
For a vertex of positive weighted degree define the weighted neighbor average . An unknown vertex is harmonic when , or equivalently . An isolated unknown vertex has no such average and its energy is independent of its value.
Theorem/proposition
Theorem 1.5.1
(Existence, uniqueness, and the boundary condition)
Assume every connected component of contains at least one observed vertex. Then there is a unique minimizer of subject to the observed values, and it is the unique extension harmonic at every unknown vertex. On each component its values lie between the smallest and largest observed values on that component.
Theorem 1.5.2
(Energy comparison)
Under the same assumption, let be the harmonic extension. For every other feasible , with on ,
The right side is strictly positive unless . Thus satisfying the harmonic equations is a global certificate, not merely a stationary-point test.
Proof sketch or proof idea
Proof
(Existence, uniqueness and the energy identity)
Write for vanishing on . If , positivity of the weights makes constant along every edge, hence on each connected component. Since vanishes at an observed vertex in every component, it vanishes everywhere. Thus is positive definite on the finite-dimensional space of free values. Its quadratic energy is coercive there: on the compact unit sphere has a positive minimum. Consequently attains a minimum, and positive definiteness gives strict convexity and uniqueness. If is empty, the unique feasible image is and the remaining statements are immediate.
Differentiating with respect to a free value gives . Therefore every minimizer is harmonic. Conversely, expand the squares for :
Collecting the cross term at vertices gives ; it vanishes at free vertices by harmonicity and at observed vertices because . This proves the energy identity, hence global optimality, and shows that a harmonic extension is unique.
Proof
(The discrete maximum principle)
Suppose the maximum value of on one component exceeds every observed value there. A vertex achieving is unknown, and it has a neighbor, since its component contains an observed vertex. Its value equals a positive weighted average of its neighbors, each no larger than , so every neighbor also achieves . Repeating along a path reaches an observed vertex, a contradiction. Applying the same argument to gives the lower bound.
Proof X-ray
Why one observed value per component matters
The anchoring hypothesis is used three times, each time for a different purpose. In the uniqueness proof it kills the only invisible direction: the energy measures differences, so a constant added on a component changes nothing unless an observation pins that constant. The energy identity itself holds for any harmonic ; anchoring enters only to make its right side strictly positive for , which is why harmonicity is a global certificate rather than a stationarity test. In the maximum principle it makes the propagation argument terminate: following equal maximal values along edges must reach a fixed observed value, or the argument proves nothing.
Positive weights are used in the same places. A zero or negative weight would break the step “zero energy forces equal neighbors” and the step “an average of no larger values that equals the maximum forces equality”.
Worked examples
Worked example 1.5.3
(A damaged interval)
Four vertices form a unit-weight path . Suppose and , and vertices 1 and 2 are missing. Harmonicity gives and . Hence , . Each of the three edge differences is one, so . Any other fill has higher energy by the comparison identity. The answer is linear interpolation because the path weights and spacing are uniform, not because harmonic extension is always linear in image coordinates.
Worked example 1.5.4
(Unequal connections)
A single missing vertex connects to known values 0 and 6 with weights 2 and 1. Its equation is , so . The stronger connection pulls the answer closer to zero. Inserting the arithmetic mean 3 would ignore the specified graph and is not the energy minimizer.
Worked example 1.5.5
(The boundary can be noisy)
If the endpoint measured as 3 in the first example is actually 4, exact interpolation instead produces . An error in a trusted boundary pixel propagates into the fill. Exact agreement is a modeling choice; when measurements are noisy a fidelity term on observed pixels can be more appropriate, but then observed values need not be matched exactly and the theorem must be adjusted.
Common mistakes
Counterexample mode
Smooth filling need not recover an edge
Suppose the unknown ground truth on the four-vertex path is , while only its endpoints are observed. The harmonic fill is , not the true sharp jump. Another ground truth, , has the same observed endpoints. The measurements alone cannot distinguish these images; the quadratic model selects the smooth one. Its maximum principle does not imply that the selected image is correct.
The counterexample concerns what the model selects; the next mistake concerns whether it selects anything.
Common mistake
(Applying the theorem to an unanchored component)
If a component has no observed vertex, the theorem does not apply. For example, two unobserved vertices joined by one edge have every constant pair as a minimizer. An isolated unknown pixel is even less constrained. Adding a small diagonal penalty would select a value, but changes the model and must not be confused with information provided by the data.
The lens below separates the harmonic equation from any procedure for solving it.
Concept lensGeometric
Averaging is an equation, not an algorithm by itself
At the solution each free pixel is a weighted average of its neighbors. Replacing all missing pixels by their current neighbor averages is one possible iterative method, but convergence depends on the update rule and graph; the equation alone does not establish it. Boundary samples must remain fixed throughout such an iteration.
Summary
Quadratic graph inpainting is a boundary-value problem: a missing pixel balances weighted differences against its neighbors. A boundary point in every graph component gives existence, uniqueness, a global energy certificate, and a maximum principle. These guarantees concern the chosen smoothness model; preservation of sharp edges or accurate recovery of unobserved structure requires further assumptions or a different prior.
Exercises
Exercise 1.5.6
(On a unit-weight path let the endpoints be and . Find the missing middle value and its energy.)
Foundation
Solution(2)
- 1
Use harmonicity
.
- 2
Compute the energy
.
Exercise 1.5.7
(A missing vertex connects to values and with weights and . Compute its value. What happens when the second weight tends to zero through positive values?)
Foundation
Solution(2)
- 1
Solve the weighted equation
gives .
- 2
Vary the weight
With second weight , . At exactly zero the second edge is absent, so the graph itself has changed.
Exercise 1.5.8
(Consider a path with values fixed to and at its endpoints and one missing middle pixel. Show directly that changing the middle value from its optimum by increases energy by .)
Foundation
Solution(2)
- 1
Find the optimum
Harmonicity gives , with energy .
- 2
Perturb
At the energy is , an increase of exactly , in agreement with the comparison identity .
Exercise 1.5.9
(A graph has two connected components, only one of which contains an observation. Explain why a unique fill is impossible and describe all minimizers on the unobserved component.)
Core
Solution(3)
- 1
Decouple the components
The energy is a sum of the energies of the two components, with no shared edge, so each can be minimized separately.
- 2
Minimize on the unobserved component
Key step
The minimizers there are exactly the constant vectors, and every constant is allowed.
Because: A connected component has zero energy precisely when adjacent values agree.
- 3
Conclude
There are infinitely many global minimizers, regardless of the anchored component's unique solution.