Why copying a patch needs a boundary decision
A photograph of woven cloth contains small arrangements of threads that are difficult to recreate one pixel at a time. Copying a square patch preserves those arrangements inside the square. The difficulty moves to its boundary: the next patch may begin a thread at a different height or contain a different brightness. A rectangular join exposes the disagreement even when both patches look plausible separately.
Overlap gives us a choice of where to change from the existing image to the new patch. Instead of averaging all overlapping pixels and potentially creating two faint copies of an edge, we can retain one side of a carefully chosen seam. This chapter makes that decision exact in a finite model. We will distinguish selecting a patch, selecting a seam for that patch, and evaluating the resulting image. These are three different problems.
The earlier finite-exemplar note reconciled conflicting patch proposals by updating shared pixels. Here pixels are copied from one of two proposals, using an explicit binary ownership mask. The procedure below is a fully specified teaching construction, including its corner convention. Its mathematical guarantees concern that construction; they do not establish that a particular photograph has been synthesized convincingly.
Patch positions and overlap error
Definition 1.26.1
(Patch dictionary, overlap width and stride)
Let an exemplar provide a nonempty finite dictionary of square patches, with real-valued color channels at each pixel. No rotation, scaling or color adjustment is implicit in this dictionary. If such transformations are desired, their transformed patches and admissibility rules must be specified. Choose an integer overlap width and stride .
For positive integers patch rows and patch columns, use top-left positions , with and . The final image has height and width . Visit columns from left to right within each patch row, and visit patch rows from top to bottom. A desired smaller image can be obtained by cropping this completed rectangle; the finite analysis concerns the stated rectangle before cropping.
Definition 1.26.2
(Overlap strips and covered set)
At a position other than the first, write for the existing output value at a covered local coordinate. The covered set is a left strip, a top strip, or their union:
A first-row placement has only ; a first-column placement has only ; an interior placement has both. These statements refer to the specified regular raster order, without missing patches. In the interior, the corner belongs to both strips but is one set of pixels:
Definition 1.26.3
(Discrepancy and normalized overlap error)
For a candidate , define the discrepancy and normalized overlap error by
The norm sums squared channel differences. Dividing by gives mean squared vector error per pixel; it does not also divide by the channel count. Since every candidate at this position has the same overlap, normalization does not change their order. It matters when combining this term with other errors. Set at the first position, where is empty, rather than dividing by zero.
A deterministic synthesis rule chooses the lowest-index minimizer of . A diversity rule can instead choose from candidates satisfying , for stated , using a recorded random seed. If and , a relative tolerance admits only exact zero-error matches. Random choice diversifies a run; it supplies no probability model for natural textures.
A seam through a vertical overlap
Definition 1.26.4
(Admissible seam and seam cost)
First suppose only the left strip is covered. A seam is a sequence of columns satisfying
Thus there is exactly one seam site in each row, and the path can move at most one column sideways when moving down. There is no wrap from column one to column . Both its top and bottom endpoint are free unless we explicitly restrict them. Its cost for a fixed candidate is
Our paste convention retains the old value when and copies when . In particular, the seam site itself belongs to the old image. Reversing which side retains the seam site is another possible convention, but it would change some pasted pixels and must be declared.
Common mistake
(Seam cost is neither the total overlap error nor the visible jump)
This cost samples disagreement between the two proposals at the same coordinates. It is not the sum of all discrepancies in the overlap, nor is it exactly the jump between adjacent pixels of the final image. A smoothness or gradient objective needs its own definition. The discrete seam model is useful precisely because it states a tractable proxy that we can solve and inspect.
Theorem 1.26.5
(Exact minimum seam in the stated path class)
For a fixed array of finite nonnegative errors, define and, for ,
Then is the least cost of any admissible path from the first row to . The least full-seam cost is . Recording one minimizing predecessor at every state and backtracking from a minimizing bottom state recovers an optimal seam. Ties can be broken by lowest column index for reproducibility.
Proof
(Dynamic-programming recurrence gives the exact optimum)
At row one there is only the one-site prefix ending at each column, so the initialization is exact. Suppose the statement holds at row . Every path to comes from one of the stated predecessor columns . Its prefix costs at least , so its total costs at least the displayed right-hand side. Conversely, select a minimizing predecessor. By the induction hypothesis an optimal prefix to it exists; appending is admissible and attains that right-hand side. The lower bound is therefore attainable. Induction proves all states. A full path ends at some bottom column, so minimizing those states gives the full optimum. Following the saved predecessors constructs the attaining path. The argument works because the grid has finitely many states and each step advances a row; it has no dependence on unvisited future choices.
Proof X-ray
The endpoint is the sufficient state
Two prefixes ending at the same row and column have exactly the same possible continuations. Replacing the more expensive prefix by the cheaper one cannot block a future move. This is the decisive property behind the recurrence. If an additional rule limits the total number of diagonal moves, the endpoint alone forgets relevant information: the state must also record how many such moves have been used. A recurrence proves optimality only for the constraints actually retained in its state.
If the top endpoint must lie in , initialize other columns to . If the bottom endpoint must lie in , minimize only over . Forbidden sites likewise have infinite cost. A finite final value then certifies an admissible path; an infinite one means no allowed path exists. Use the extended-real conventions for finite and . The induction now says that finite states have attaining paths, while infinite states have none: a permitted finite prefix can be extended, and a state with no permitted finite predecessor cannot be reached. These are boundary constraints, not reasons to invent off-grid predecessor values. For , there is exactly one possible seam.
Proposition 1.26.6
(Running time of the seam recurrence)
There are states and at most three predecessors per state. Computing every value takes time, with stored predecessors for straightforward reconstruction. Cost values alone can use two rows of memory, but reconstructing the path still requires saved decisions or an explicit recomputation strategy.
Proof
(Counting states and transitions)
Each of the states is computed once, as a minimum over at most three stored values, and records one predecessor index. Row depends only on row , so keeping two rows of values uses memory.
For a top strip, transpose the argument: a seam gives one row index per column, with and ; retain old pixels where .
A complete two-dimensional strip example
Worked example 1.26.7
(From two patch proposals to an actual pasted array)
Let , , and suppose the existing left overlap is zero in all twelve positions. Take the grayscale candidate
Its left-overlap error and accumulated-cost arrays are
For instance, ; there is no predecessor at column four. The unique least bottom value is three at column two. Backtracking gives , with cost . The retained-old mask and final patch footprint are
Here mask one means old, and zero means new; the uncovered fourth column must come from . The raw overlap sum is , so . The seam cost is three. These numbers sum over different sets of pixels and should not be reported as a measured percentage improvement in image quality. The output is an intentionally small arithmetic example, not evidence of attractive cloth synthesis.
Counterexample mode
Choosing the cheapest next pixel can be arbitrarily worse
Consider the error array
A rule that first chooses the cheapest top site and then the cheapest reachable next site begins at column one and stays there in row two. It must pay at least in row three, since column three is unreachable in one move. With lowest-column tie breaking it pays another in row four, for total . Yet is admissible and costs one. It is optimal: a zero-cost path would have to use columns one, one, three, three, which violates the move constraint, and every positive entry is at least one. Replacing each by any makes the greedy cost at least while the optimum remains one. The repair is to retain the best accumulated prefix at every column, rather than keeping only the cheapest immediate move.
Interior corners and the full raster construction
At an interior placement, selecting a vertical seam alone leaves the top overlap unresolved. Selecting a horizontal seam alone leaves the left unresolved. We adopt a simple, explicit combination rule. Compute a vertical seam on the complete left strip and a horizontal seam on the complete top strip, both against the same frozen existing image and candidate . Do not paste one strip before computing the other. Retain old pixels in the union of their old sides:
Copy at every other coordinate. Because and , this rule never asks for an old pixel outside . Because it makes a single binary decision at each site, the corner is neither written twice nor averaged ambiguously.
Worked example 1.26.8
(A width-one interior corner)
Take and . Both seams are forced, , so
The old image supplies the top row and left column; supplies the remaining square. The overlap has five pixels, not six.
Common mistake
(Two optimal strip seams do not make an optimal corner cut)
This union rule completely specifies a paste, but the separate seam theorem does not prove that the combined corner boundary minimizes a single energy on the L-shaped overlap. The independent paths can interact or hide parts of one another. A globally optimized binary mask on that region would require an explicitly defined mask energy and boundary constraints, followed by an algorithm justified for that problem. Do not silently substitute that stronger claim for the two strip results.
The entire finite quilting procedure is now executable:
- Fix the dictionary, , color representation, selection rule and any random seed. Choose the first patch by the stated seed rule; without randomization, use the lowest dictionary index.
- At each later raster position, freeze the current output on , count the union once, compute each candidate's , and select a candidate.
- Find the vertical and/or horizontal minimum seams on its covered strips. Use the old-side rule for one strip, or the union rule when both exist.
- Copy old values at mask-one sites and candidate values elsewhere in the footprint. Continue until every scheduled placement has been visited.
An induction on placements shows that every value needed from already exists: it is in a covered strip, and all newly exposed sites are copied from . The rectangle is filled after the finite visits. This is a termination and ownership argument, not an energy-descent theorem. Later patches may overwrite parts of earlier patches. There is no fixed global objective here whose value we have proved decreases after every paste, and there is no search over all quilts.
With exhaustive dictionary search, overlap scoring costs per placement; both seams together cost , and copying costs . Source-patch extraction, feature computation and accelerated search are separate operations.
Common mistake
(The best overlap match is not the best seam)
A dictionary patch that minimizes the entire overlap error need not minimize the best seam cost: the scoring and cutting objectives are different. Rank candidates by the quantity that the next step actually uses, or state why the proxy suffices.
Texture transfer: a second image steers the choices
Pure synthesis asks for another sample resembling a source texture. Texture transfer additionally asks that a target image influence where different parts of the texture appear. A dark target region might request dark source material, while a bright region requests bright material. This does not recover the target object's physical material or three-dimensional shape; it constrains a chosen image representation.
Let a target correspondence field be defined on the output rectangle. Give each candidate a compatible correspondence field on its patch. These may be grayscale intensities, precomputed low-frequency color fields, or explicitly selected features. Specify their dimensions, units and preprocessing: independently rescaling each patch can remove brightness information that the target was meant to control.
Definition 1.26.9
(Correspondence cost and combined transfer cost)
For a fixed nonempty set and patch position , use
Typically is the entire patch; it can instead be a documented subset with valid target information. The two errors require compatible scales or an explicitly chosen weighting convention. A value of gives equal numerical coefficients, not automatically equal perceptual influence.
Select a minimizer of , then compute the overlap seams and paste exactly as before. At the first patch, and selection uses the correspondence term when ; at all candidates tie, so use the seed rule. There is no seam at that first placement. This defines a complete single-pass transfer procedure. The seam itself still minimizes overlap disagreement, not correspondence error. Moreover, scores the candidate proposal; retained old pixels may prevent the final footprint from attaining that score. Evaluating the finished output against the target is therefore a separate step.
Worked example 1.26.10
(A target can change which two-dimensional patch is selected)
Take , , an interior overlap whose three existing values are zero, and candidates
Assign the lower dictionary index to . Their mean overlap errors are and . For this small example choose grayscale correspondence only at the newly exposed pixel: and target value three there. Thus and . The combined costs are and . Candidate wins exactly when , while wins when ; at equality use the stated index rule. With , the costs are five and , so is selected. The forced width-one seams retain the top row and left column, producing . Target error at the one newly exposed site is one. The example specifies actual patches, a target, scoring, seam and final paste; it does not infer preservation of the target's full structure from one pixel.
What the finite model leaves to image evaluation
A seam can have very low cost while a long brick edge ends on the wrong row farther inside the copied patch. A large patch preserves more internal structure but offers fewer independent arrangements; a small patch offers more freedom but may not contain a complete motif. Increasing overlap makes selection more constrained and increases search work. None of those tradeoffs gives one universal patch size.
Squared color error is sensitive to exposure, registration and the chosen color coordinates. Brightness normalization can help an illumination mismatch while destroying a deliberate target brightness relation. A blurred correspondence field may preserve broad shading but discard thin contours. A single correspondence scalar does not encode semantic identity, visibility or geometry. Even exact target-feature agreement can coexist with inappropriate texture.
A practical evaluation should identify exemplar and target, report patch/overlap sizes and seeds, show the complete result together with close-ups of seams and long structures, and compare multiple runs under the same settings. Compare a fixed rectangular paste with the seam version while keeping patch proposals fixed to isolate the cutting decision. Compare overlap-only selection with the transfer score under the same dictionary to isolate the target term. Measure correspondence on the final image, including retained pixels, with the declared feature extractor; report what that metric omits. These are proposed evaluation controls, not experiments performed in this chapter. No numerical result above establishes quality on natural images.
Exercises
Quick check
(With and , find the stride, the image dimensions for two rows and three columns of patches, and the overlap size at an interior placement. Explain the corner subtraction.)
Solution · Answer
The stride is . Height is and width is . Each overlap strip has ten pixels, and their corner is counted twice in their separate sizes. Their union has pixels. Simply adding the strip scores would give the corner double weight unless that were explicitly intended.
Quick check
(For the , left-strip error array with rows , and , compute every dynamic-programming value and an optimal free-endpoint seam. Repeat when the top endpoint is forced to column one and the bottom endpoint to column two.)
Solution · Answer
With free endpoints the accumulated array is . The bottom minimum is one in column one. Backtracking gives with cost . With the constrained top, the first row becomes , the second and the third . Restricting the bottom to column two gives cost five and path . The unconstrained cost one is infeasible under those endpoints; boundary constraints change the problem.
Quick check
(Explain why selecting a candidate by total overlap error differs from selecting by minimum seam error. Verify this with three-row, two-column left-strip errors (, ): has every row equal to and has every row equal to .)
Solution · Answer
Patch has overlap sum and an optimal straight seam in column one costing zero. Patch has overlap sum six and every full seam costs three. Mean overlap ranking divides both totals by six, so it still selects ; minimum-seam ranking selects . These strip arrays can be realized within patches by a zero old overlap and candidate values equal to the entrywise square roots on the left two columns. Their third columns can be arbitrary. Neither ranking alone says what occurs in the patches outside this overlap.
Quick check
(Add a nonnegative penalty for sideways moves. Derive the recurrence and justify its state. On the main four-row example, show that makes seam better than the previously optimal . Does that comparison alone prove the constant seam is globally optimal?)
Solution · Answer
The initialization is unchanged, while . The current endpoint still determines all permissible next moves and their transition costs, so the same prefix-replacement proof applies. At , the zigzag has discrepancy three and three sideways moves, hence cost twelve. The constant column-two path costs . A pairwise comparison alone cannot establish global optimality. Running the recurrence gives rows , , , , proving that the constant path attains the global minimum ten. Another optimum is : discrepancy seven plus one sideways penalty three gives ten. Lowest-column predecessor tie breaking recovers this latter path, since the row-two column-two state has tied predecessors one and two.
Quick check
(Use the transfer example with candidate assigned the lower index. Find the selection and final footprint at , and . Explain why using all four target pixels would be a different model.)
Solution · Answer
At , overlap alone selects , and the footprint is all zeros because its only copied interior value is zero. At , correspondence selects , yielding . At the scores tie at , and the lower-index rule selects . An all-four-pixel correspondence term would require four target values, count three sites that are retained from the old image by these seams, and generally change the scores and threshold. Those values cannot be invented from the one target value supplied here.