PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing
ACM SIGGRAPH 2009 papers, 2009 · paper · Computer science
Presents a randomized algorithm for quickly finding approximate nearest-neighbor matches between image patches, reported as 20–100 times faster than prior methods. It underpins interactive tools for image retargeting, completion and reshuffling, with added user constraints.
Checked: PDF from gfx.cs.princeton.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
3 findings
Substance Simulations are said to cover "images of resolution M from 0.1 to 2 Megapixels" (Intro: "tested imagery up to 2MP"), but the example given is "after 5 iterations for a M = 2000^2 image", which is 4 megapixels.
- p. 5 Section 3.3, simulation paragraph
We performed simulations for images of resolution M from 0.1 to 2 Megapixels
- p. 5 Section 3.3, simulation paragraph
after 5 iterations for a M = 20002 image
- p. 2 Introduction
convergence properties for tested imagery up to 2MP
- p. 5 Section 3.3
after 5 iterations for a M = 2000
Only the authors can say what is right here.
Judge's note: The page-5 crop confirms the superscript 2 in 'M = 2000^2'. 2000^2 = 4,000,000 pixels = 4 MP, which is outside the stated 0.1–2 MP range. Only the authors can say whether the range or the example is wrong.
Second check: another model agreed
Report a problem with this finding
Reference or label Figure 8 caption: "Input images are shown in the first and fourth column." The figure has only three columns ((a) input, (b) our reshuffling, (c) Patch Transform), and the inputs are only in the first column.
- p. 7 Figure 8 caption
Input images are shown in the first and fourth column.
Judge's note: The full page 7 image shows Figure 8 as a single 3x3 grid labelled (a) input, (b) our reshuffling, (c) Patch Transform. There is no fourth column.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference "ASHIKHMIN, M. 2001. Synthesizing natural textures. In I3D ’06 Proc., ACM, 217–226." gives a 2001 entry year but a 2006 venue.
- p. 10 References, first entry
ASHIKHMIN, M. 2001. Synthesizing natural textures. In I3D ’06 Proc., ACM, 217–226.
- p. 10 References, Ashikhmin entry
ASHIKHMIN, M. 2001. Synthesizing natural textures. In I3D ’06 Proc.
- p. 10 References, ASHIKHMIN
Synthesizing natural textures. In I3D ’06 Proc.
- p. 10 References, ASHIKHMIN
Synthesizing natural textures. In I3D ’06 Proc., ACM, 217–226.
Judge's note: The page-10 crop confirms the entry year 2001 and the venue 'I3D ’06 Proc.', the same venue string as the Rong & Tan 2006 entry. The year and venue contradict each other within the entry, and the text cites it as Ashikhmin [2001]. The suggested fix ('I3D ’01') rests on outside knowledge of the original venue.
Second check: another model agreed
Report a problem with this finding
7 minor (typos and the like; most checked by the judge only)
Wording Symbol m is defined as patch size in the Introduction ("patches of size M and m pixels", O(mM^2)) but reused in Section 3.3 for "a distinctive region R of size m pixels" (e.g. m = 20^2), which drives <t> = M/(Cm) − 1/2.
- p. 2 Introduction
for image regions and patches of size M and m pixels, respectively
- p. 5 Section 3.3
a distinctive region R of size m pixels
Judge's note: Checked p.2 (Introduction: m = patch size, also 'm dimensions' of patch space) and p.5 crop (Section 3.3: m = size of region R, example m = 20^2 while patches are 7x7). The two quantities differ, and the same symbol is used for both. Section 3.3 does define the new meaning locally, so this is a notation overload rather than an error.
Second check: another model agreed
Report a problem with this finding
Wording Introduction states "As this field grows larger, the chance that no patch will have a correct offset becomes vanishingly small", whereas Section 3.3 gives the probability of at least one correct offset as (1−(1−1/M)^M) ≈ 1−1/e (or 1−exp(−C)) for large M, i.e. the chance of none tends to a constant.
- p. 2 Introduction, 'The law of large numbers'
As this field grows larger, the chance that no patch will have a correct offset becomes vanishingly small.
- p. 5 Section 3.3, first paragraph
approximately 1 −1/e for large M
Only the authors can say what is right here.
Judge's note: Checked p.2 ('The law of large numbers' paragraph) and p.5 (Section 3.3). Under the paper's own model, P(no correct offset) = (1−1/M)^M → 1/e ≈ 0.37 (or exp(−C) for a neighbourhood of C pixels), which does not vanish as M grows. The introduction is informal and may mean 'good guesses' in a looser sense, but as worded it overstates what Section 3.3 shows. Authors should clarify.
Second check: another model agreed
Report a problem with this finding
Wording Discussion: "for pathological inputs, such as the synthetic test case of Section 3.3, we have poor convergence properties", whereas Section 3.3 says for that test case "the algorithm converges with very high probability after 5 iterations" and expected iterations remain constant.
- p. 9 Section 5, failure cases paragraph
such as the synthetic test case of Section 3.3, we have poor convergence properties
- p. 5 Section 3.3
the algorithm converges with very high probability after 5 iterations
Only the authors can say what is right here.
Judge's note: Checked the p.5 crop and the p.9 text. Section 3.3 calls its synthetic case 'hard but not the worst one' and reports good convergence. The poor case it describes is the repetitive texture with distractors. The Discussion's reference to 'the synthetic test case' therefore misdescribes Section 3.3, unless the worst case was meant. Authors should clarify.
Second check: another model agreed
Report a problem with this finding
Typo Unbalanced parentheses: "quite good (1−(1−1/M)^M))" has two opening and three closing parentheses.
- p. 5 Section 3.3, first paragraph
(1−(1−1/M)M))
- p. 5
(1−(1−1/M)M)) or approximately 1 −1/e for large M
Judge's note: The page-5 crop shows '(1 − (1 − 1/M)^M))' with an extra closing parenthesis. There is no earlier open bracket in the sentence, and the parallel expression '(1 − (1 − C/M)^M)' is balanced. This is not an extraction artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Figure 7 caption uses "A point q_i in T has nearest neighbor NN(q_i)" and "q_i", while the figure labels and Eq. (6)/text use q_j and NN(q_j).
- p. 7 Figure 7 caption
A point qi in T has nearest neighbor NN(qi) that lies on Lk.
- p. 7 Section 4.2, Model constraints text
let {q j} ∈T|NN(qj) ∈Lk refer to all the points qj in the output
Judge's note: The crop shows the figure labels 'q_j' and 'NN(q_j)', and the text on p.7 uses {q_j} and NN(q_j). The caption alone uses the subscript i. This is an index inconsistency, and the meaning is recoverable.
Second check: none (judge only)
Report a problem with this finding
Typo "does not guarantee that the line will not bend or break (see Figures 11)" uses the plural for a single figure.
- p. 7 Section 4.2, first paragraph
(see Figures 11)
Judge's note: The full page 7 image shows '(see Figures 11)' in Section 4.2 with only one figure number. The plural is a typo, or a second figure number was dropped.
Second check: none (judge only)
Report a problem with this finding
Typo Figure 12 caption: "(k-n) The buildings in (k) the input image are (l) horizontally swapped (m) cloned, (n) vertically stretched, (o) and widened." The range label omits panel (o).
- p. 10 Figure 12 caption
(k-n) The buildings in (k) the input image are (l) horizontally swapped (m) cloned, (n) vertically stretched, (o) and widened.
- p. 10 Figure 12 caption
(k-n) The buildings in (k) the
Judge's note: The page-10 crop shows panel (o) as the widened version of the same Venice scene, and the same sentence describes it. The range should be (k-o).
Second check: none (judge only)