Motivation
A small photograph of stone contains information about local texture: nearby intensity patterns, repeated edges and characteristic color combinations. To extend it, we could copy the entire photograph repeatedly, but its rectangular repetition would be conspicuous. Another possibility is to reuse smaller patches in new arrangements while making their overlaps agree. This is data-driven synthesis in a literal sense: the allowed local proposals come from measured examples rather than an analytic formula for stone.
The word “data-driven” does not remove modeling decisions. We must choose patch size, color representation, a measure of agreement, the output constraints and a search procedure. A patch that matches an overlap can still put a vertical crack where a horizontal structure should continue. Conversely, insisting that every patch match the source exactly can be impossible because neighboring placements disagree. A useful model should make these compromises visible instead of hiding them behind a single visually pleasing result.
We construct a deliberately finite exemplar model, small enough that its algorithm has a precise termination proof and can be followed by hand. It is not a complete modern texture synthesizer or a statistical model of every image class. Its value is that it separates three ideas: nearest-neighbor selection, reconciliation of overlapping proposals, and the difference between decreasing an objective and generating a convincing image.
Definitions
Definition 1.27.1
(Finite exemplar energy with observations)
For clarity, use a grayscale output on a fixed finite grid. Each value belongs to a finite nonempty alphabet . A patch extractor selects a vector of output pixels at placement , for . The finite dictionary is obtained from specified exemplar patches. Dictionary values need not exhaust the output alphabet. Color images replace scalar entries by vectors and require an explicitly chosen color distance.
A label chooses the dictionary patch assigned to placement . Let be observed positions with values , let , and optionally fix a set of output pixels to prescribed values in . Define
This is an optimization objective, not automatically a probability or a calibrated perceptual score. It says that output patches should resemble dictionary members while observed pixels resist changes. Hard constraints in differ from a finite penalty: a fixed pixel cannot move even if doing so would reduce the patch term.
Definition 1.27.2
(Energy after eliminating labels)
Eliminating labels gives
Each patch independently chooses a nearest neighbor for the current image. The overlaps couple these choices through shared output pixels. There is no implication that independently copied patches agree before reconciliation, or that the resulting objective is convex.
Definition 1.27.3
(Coefficients and proposal sums)
For fixed labels, let count patch occurrences of pixel , plus if . Let be the sum of all dictionary entries proposed at that pixel, plus if observed. These definitions count every occurrence in the objective. Assume extractors do not duplicate a pixel inside one patch; repeated occurrences across different patches are expected.
Theorem/proposition
Theorem 1.27.4
(Exact coordinate updates are nearest-patch and nearest-average decisions)
For fixed , minimizing over one label chooses a nearest dictionary patch to . For fixed labels and all other pixels, a non-fixed pixel with minimizes energy by choosing an alphabet value nearest to . If , its value does not affect the objective. These statements concern the specified squared-error model and do not assert uniqueness when ties occur.
Theorem 1.27.5
(Strict coordinate descent terminates in the finite model)
Visit every label and every non-fixed pixel in a fixed repeated order. Replace a coordinate by an exact minimizing value only when this strictly decreases energy; retain its current value on a tie. Then only finitely many changes occur. When an entire sweep makes no change, the current state is a coordinatewise minimum. It need not be a global minimum, and termination does not establish perceptual quality.
The finite-alphabet hypothesis is essential to this termination argument. If output intensities vary continuously, decreasing energy and a lower bound can imply convergence of energy values without implying finitely many updates. Nor does an approximate nearest-neighbor search automatically preserve exact coordinate minimality. Its proposal can still be accepted only after a verified decrease, but the stopping statement then has to be weakened.
Proof sketch or proof idea
Proof
(Exact label and pixel updates)
Only one term depends on a particular label, so the label decision is exactly a finite nearest-neighbor search. For a pixel, collect all terms containing it. Apart from a constant independent of , they are
when . Thus the best allowed scalar is closest to the proposed weighted average. This is a reconciliation of proposals, not a claim that their average is itself a dictionary patch. A hard-fixed pixel is excluded from these updates, regardless of its coefficient.
Proof
(Finitely many strict changes)
There are at most feasible image-label states. Every change strictly decreases their fixed objective value, so no state can recur. Finiteness therefore bounds the total number of changes by the number of states minus one. The bound can be enormous; it is a correctness argument, not a claim of efficient worst-case synthesis. In a no-change sweep, each coordinate is tested while the entire state remains fixed, so none admits a strict improvement.
Proof X-ray
Why keeping the current value on ties matters
Two distinct states can have equal energy. If a solver keeps changing between equally good labels, finiteness alone does not stop a cycle. Retaining the current value on ties makes every actual state change strict. The proof then has a concrete progress quantity. Floating-point code needs a stated comparison policy; a tolerance changes what “no improvement” means and should not be silently equated with an exact coordinatewise minimum.
For fixed labels, the objective separates by output pixel, so a simultaneous full image update using the displayed nearest-average rule also minimizes the image block exactly. This stronger update is convenient, but does not make the joint problem convex because label changes alter the proposed patches. Initial images, hard constraints and dictionary content can lead to different terminal states. Random initialization explores alternatives; a random seed records a run rather than certifying that the selected alternative is optimal.
Worked examples
Worked example 1.27.6
(A complete finite synthesis run)
Take three output pixels with alphabet , patches and , and dictionary , . Fix , , with no data penalty. Start from and labels . Initial energy is . The first patch is distance squared four from either dictionary member, so its current label stays one. The second patch chooses label two, reducing energy to four. The free middle pixel receives proposals zero and two, so its average is one. Choosing lowers energy to two. A new label sweep keeps : the patch costs are one versus five in each preferred direction. The pixel average remains one. A complete sweep makes no change, so the algorithm stops at , , energy two.
Worked example 1.27.7
(How observed data changes the proposal average)
At one free pixel, two patches propose zero and two. An observation is with . The coefficient is , and , so the unrestricted average is . On alphabet , one and two tie. Their patch-plus-data energies both equal four, while zero has energy twelve. If the current value is one, the strict-update rule keeps it. A larger observation penalty can favor two, but a penalty is still not the same as fixing the pixel exactly.
Worked example 1.27.8
(A coordinatewise minimum can miss the best state)
Use one scalar output pixel , one one-pixel patch with dictionary entries zero and two, observation , and . At state , energy is . Changing just the label gives energy ; changing just the pixel gives energy four. The state is therefore coordinatewise minimal. Yet changing both to gives energy zero. The finite algorithm can terminate at a suboptimal state even with exact updates and no numerical error.
The first run also shows what overlapping synthesis actually does. Neither final output patch equals a dictionary member: they are and . Shared-pixel reconciliation introduces a compromise. If preserving source texture elements exactly is more important than squared-error averaging, one can instead select boundaries between copied regions. That creates a different optimization problem with its own constraints; it is not a hidden feature of the present objective.
Concept lensStructural
The exemplar set is a finite vocabulary, while overlaps are grammar constraints
The dictionary lists local patterns the model knows how to propose. Overlap terms decide whether neighboring proposals can share pixels consistently. A vocabulary of valid local patches does not contain a global description of a wall, face or object. Increasing patch size adds longer-range information but increases search cost and copying risk. The chosen patch scale determines which structures can be constrained directly and which are left to emerge, or fail to emerge, from local agreement.
An exhaustive label sweep evaluates candidates of dimension at each of placements, costing order scalar operations before possible acceleration. Computing all proposal sums costs order , and an alphabet search costs order in a simple implementation. These per-sweep costs do not bound the number of sweeps by a small constant. Memory also includes the exemplar dictionary and the chosen label field. An algorithm's finite state space is not a practical reason to enumerate it.
Common mistakes
Counterexample mode
Zero local error does not certify the intended scene
Suppose a dictionary contains only constant zero and constant one patches. A completely zero output has zero patch energy wherever no data term forbids it. If the intended result is a brick wall, that objective value says nothing about brick geometry because the dictionary and constraints did not encode it. Repairing the claim requires evidence that the objective represents the desired structures, followed by appropriate evaluation; minimizing a convenient number alone does not establish realism.
Common mistake
(Treating a synthesized completion as measured data)
Do not interpret nearest-neighbor distance as a probability without a statistical model. Do not treat a patch copied from an example as an observed missing region of a damaged photograph. Example-based restoration supplies a plausible completion under its assumptions; several completions can fit the same known pixels. A sharp result may still add unsupported detail. Record the exemplar source and distinguish measured regions from synthesized ones when that distinction matters to the use of the image.
Common mistake
(Raw patch distance is not translation-invariant)
Patch distances also depend on scale and registration. A one-pixel translation can make a repeated edge appear far away in raw Euclidean patch coordinates. Rotation, illumination normalization or feature-space comparisons can change the search, but each introduces a new invariance and can discard useful distinctions. Adding such flexibility should answer an actual modeling need, not merely lower the residual by making unlike patterns indistinguishable.
Summary
An exemplar objective combines nearest local proposals with overlap and observation constraints. Exact label updates choose dictionary neighbors, while image updates reconcile their proposed pixel values. A finite alphabet and strict tie policy give finite termination at a coordinatewise minimum, with no promise of global optimality or perceptual realism. The completed small run makes the algorithm auditable and exposes the compromise created by incompatible neighboring patches.
Exercises
Quick check
(In the complete run, enumerate the four label pairs and minimize over the free alphabet value . Verify the best joint energy and identify which other label choices are worse.)
Solution · Answer
For labels the energy is , minimized at zero with value four. For it is , minimized at two with value four. For it is , minimized at one with value two. For it is , minimized at one with value ten. Thus the displayed terminal state happens to be globally best in this particular example; the separate counterexample shows why that cannot be generalized.
Quick check
(Two patch occurrences propose one and three at a free pixel, while an observation proposes zero with penalty . On alphabet , find every minimizing pixel value and compute the corresponding energy.)
Solution · Answer
Here , , so the average is one and the unique alphabet minimizer is one. Its energy is . Completing the square gives , which verifies both the minimum and uniqueness on the stated alphabet.
Quick check
(For one output pixel with alphabet and dictionary zero/two, let and . Determine exactly when the state is a coordinatewise minimum under strict updates, and compare its energy with the global optimum.)
Solution · Answer
At energy is . A label-only change increases energy by four. A pixel-only change gives energy four, so strict improvement exists exactly when . The state is a coordinatewise minimum for , with a tie at one retained by the rule. The joint state always has energy zero. Thus has positive energy for every and is globally suboptimal whenever it is a coordinatewise minimum, namely .
Quick check
(A model has five free pixels with four values each and three patch labels with two choices each. Give a finite upper bound on strict state changes. Explain why equal-energy relabeling and approximate nearest-neighbor stopping require different guarantees.)
Solution · Answer
There are states, so at most 8191 strict changes. This deliberately loose bound concerns changes, not the number of coordinate tests. Equal-energy moves can revisit states and cycle. Approximate search may overlook a better label, so a no-change sweep then certifies only that the tested proposals failed to improve, unless exact nearest-neighbor optimality is separately verified.