Monochromizer

Convert images into monochrome (b/w) compositions by stacking marks as layers. The catalog covers 35 algorithms in eight groups — the same grouping and order as the GUI's algorithm dropdown:

• Edges / line drawings (5) — thin-line and bold-stroke drawings traced from the image's gradient structure (Marr-Hildreth, Canny, iso-contours, FDoG, XDoG)
• Visible dots (AM) (4) — classical print screens: periodic dots, clusters, and dither stripes whose mark size carries tone (Limb dither, clustered dot, AM dot screen, Velho-Gomes Hilbert clusters)
• Invisible dots (FM ordered) (1) — blue-noise ordered dither with unit-size, density-modulated dots (Ulichney void-and-cluster)
• Invisible dots (FM error-diffused) (10) — scan-order quantisation with error propagation, from Floyd-Steinberg to the structure-aware variants (Ostromoukhov, Pang, Chang, Li-Mould, Shi-Li, …)
• Off-grid stipple — Voronoi / Lloyd (4) — point clouds relaxed by Lloyd's method (Deussen floating points, Secord weighted Voronoi, Balzer CCVT in strict and Lloyd-approximation variants)
• Off-grid stipple — Optimal transport (3) — dot layouts computed as transport maps (De Goes power diagrams, Nader grid OT, Paulin sliced OT)
• Off-grid stipple — Other (3) — stippling by example (Kim), electrostatic (Schmaltz), Gaussian blue noise (Ahmed)
• Tone-following hatching (5) — ink lines and artistic screens driven by parametric or example templates (artistic screening, digital facial engraving, image-based dither screens, hatching by example, reaction-diffusion woodcuts)

Every mark type is composable with every other: stack a halftone fill under a Canny outline, or render a flow-based DoG over a stipple fill, and the compositor masks the tone layer where the outline runs so the line reads cleanly.

Output

Both PNG (1-bit raster) and SVG (vector) — for every algorithm. Dots export as <circle>, strokes as <polyline>, and mask outputs (the AM/FM halftone masks, XDoG/FDoG, the screen/engraving hatchings) are traced into pixel-exact boundary <path>s with even-odd fill: every ink pixel keeps its full unit square, holes stay paper, and tone is preserved exactly (no marching-squares shrinkage of isolated pixels). The GUI lets you toggle between PNG mode (1-bit pixmap, exactly what write_png saves) and SVG mode (vector ellipses / paths / polygons, exactly what render_svg saves) so you preview the same thing you'll export.

Layer-output primitives

Each algorithm produces a LayerOutput carrying any combination of:

• mask — bool ndarray of shape (height, width). The canonical raster representation; used for PNG export and PNG-mode preview, and traced into a pixel-exact even-odd <path> for SVG export. Most FM halftones produce only this; XDoG and FDoG also output mask (their paper-faithful behaviour is a filled-region tonal stylization / multi-pixel-wide ink stroke, which would be destroyed by skeletonization).
• dots — list of (x, y, radius) circles in canvas coords. All stipplers.
• strokes — list of polylines, each [(x, y), …]. Canny, Marr-Hildreth, iso-contours; Velho-Gomes (each Hilbert cluster is a polyline); Jodoin (each synthesized hatching stroke is a polyline).
• polygons — list of closed [(x, y), …] regions, rendered as one even-odd path per layer (inner loops are holes). No algorithm populates this directly; it's the vector form mask layers take in SVG output.
• keepout — derived from Layer.mask_bleed × the union of marks; subtracted from underlying tone fills so an outline reads clean against paper.

Algorithms

Every algorithm in the catalog is backed by a published reference — full citations in the References section at the end. The eight sections below mirror the GUI dropdown (dispatch.GROUPS): algorithms are grouped by visual outcome, and listed chronologically by paper publication year within each group.

Edges / line drawings (5)

Edge / contour algorithms turn an image into a thin-line drawing by finding the loci of intensity change. The mechanics differ — second-derivative zero-crossings (Marr-Hildreth), gradient-magnitude non-max suppression + hysteresis (Canny), level sets of the brightness field (iso-contours), edge-tangent-flow-aligned Difference of Gaussians (FDoG), or a tone-stylising soft-threshold variant of DoG (XDoG) — but all share the same basic idea: the ink geometry comes from the image's gradient structure. (Contrast this with the hatching family below, where the stroke geometry comes from a parametric template that's then modulated by tone.)

Key	Output	Paper	Default params	Notes
log_zero	strokes	Marr & Hildreth 1980, Theory of Edge Detection, Proc. Royal Society B	sigma=4.0, gradient_threshold=0.0	Paper Fig. 4's w = 2σ = 8. Zero-crossings are 1-pixel-wide by construction; mask_to_polylines traces them cleanly.
canny	strokes	Canny 1986, A Computational Approach to Edge Detection, IEEE PAMI	sigma=1.0	σ scales with input pixel resolution: paper σ=1.0 was on 576×454 inputs, multi-MP inputs need σ × √(area_ratio). The Normalize to resolution toggle applies this factor automatically (to every pixel-unit parameter, all algorithms).
iso_contours	strokes	Marching squares (2D restriction of Lorensen & Cline 1987 Marching Cubes, SIGGRAPH)	n_levels=5, min_level=0.1, max_level=0.9	Closed level sets at user-chosen brightness percentiles; topographic / silhouette aesthetic.
fdog	mask	Kang, Lee, Chui 2007, Coherent Line Drawing, NPAR	sigma=1.0, sigma_m=3.0, etf_radius=5, threshold=0.5, fdog_iterations=3, phi=200	Paper §4 values. Bold ink-stroke output via mask (skeletonization would strip the natural multi-pixel width).
xdog	mask	Winnemöller, Kyprianidis & Olsen 2012, XDoG: An eXtended Difference-of-Gaussians Compendium, Computers & Graphics	p=18, phi=0.6, epsilon=0.822, threshold=0.9	Reproduces Fig. 6 (Table A.1 Fig. 6 row, with ε scaled from CIE L*[0,100] to [0,1]). Tonal stylization, not thin-line.

Paper-faithfulness validation

Each edge-detection algorithm has been side-by-side compared against its source paper using test images that match the paper's own figures. Outputs in validation/output/.

Algorithm	Test images	Reproduces
log_zero	validation/inputs/marr{1,2,3}.png (vessels, texture, sculpture)	Marr-Hildreth Figs. 4 & 6 — outputs in validation/output/marr{1,2,3}/, paper figures at docs/extracted/_marr_paper_*.png
canny	validation/inputs/canny{1,2,3}.png (parts, handywipe, Dalek)	Canny Figs. 8, 9, 11 — outputs in validation/output/canny{1,2,3}/
fdog	validation/inputs/kang{1,2,3}.png (butterfly, mandrill, tiger)	Kang Fig. 11 — outputs in validation/output/kang{1,2,3}/, paper figure at docs/extracted/_kang_paper_fig11_results.png
xdog	validation/inputs/winnemoeller{1,2,3}.png (the Fig. 6 portrait, others)	Winnemöller Fig. 6 thresholded panel — outputs in validation/output/winnemoeller3/

Sample outputs

Marr-Hildreth on marr3.png (sculpture) at the three Fig. 6 scales σ=3, 6, 12 (fine → coarse zero-crossings):

σ=3 (Fig. 6b)	σ=6 (Fig. 6c)	σ=12 (Fig. 6d)

Canny on canny1.png (parts image) at σ=3.55 (paper σ=1.0 scaled to our 3.3 MP input) reproduces Fig. 8(a):

FDoG on kang3.png (tiger) at 2× scale produces the bold ink-illustration character of Fig. 11:

XDoG on winnemoeller3.png reproduces Fig. 6's tonal stylization (man in glasses against mountains, white sky):

Visible dots (AM) (4)

AM (amplitude-modulated) halftones render tone with visibly structured marks at a fixed spatial frequency — the classical print-screen aesthetic, where dots, clusters, or stripes grow with local darkness. The shared basic idea is area conservation per cell: each cell of a regular grid (or each run of a dither cycle or space-filling curve) receives ink area in proportion to its local darkness, so tone is preserved by construction rather than approximated pixel-by-pixel. The mechanics differ — a periodic dither waveform added per scan row (limb_dither), a spiral-grown clustered-dot threshold tile (clustered_dot), one variable-radius dot per cell (am_screen), a pixel cluster grown along a Hilbert curve (velho_gomes) — but in all four the mark structure is periodic and visible, in contrast to the FM families below, where unit-size dots are dispersed to be as unobtrusive as possible. am_screen outputs SVG-native circles and velho_gomes polyline strokes (both suitable for print or laser-cutting); limb_dither and clustered_dot output pixel masks (traced to pixel-exact boundary paths at SVG export).

Key	Output	Description
limb_dither	mask	Limb 1969 — Roberts-style dither, three modes: random uniform (Roberts 1962 baseline), two-step anti-correlated random (paper §III novelty), n-step deterministic LVP (paper §III).
clustered_dot	mask	Bayer 1973 / Holladay 1980 — spiral-grown clustered-dot ordered-dither tile (the offset-print screen aesthetic).
am_screen	dots	Bayer 1973 / Holladay 1980 — classical AM dot screen. One variable-radius dot per cell; radius scales with cell darkness so dot area equals the cell's ink demand (exact tone preservation, Bayer 1973 §IV invariant).
velho_gomes	strokes	Velho-Gomes 1991 — Hilbert-curve clustered dither; each cluster is a polyline along the curve.

Paper-faithfulness validation

Only Velho & Gomes 1991 publishes directly reproducible photographic figures; Limb 1969 publishes waveform / ramp diagnostics, and Bayer 1973 / Holladay 1980 are matrix-construction recipe papers. Validation therefore combines figure reproduction where available with the papers' own invariants elsewhere.

Algorithm	Test image	Reproduces
limb_dither	synthetic 1-D ramps (Δ = 0.3 → 0.7, constant Δ = 0.25 / 0.5 / 0.75) + validation/inputs/sudanese.png	Limb Figs 1 & 7 — chopping patterns from the n=4 / n=7 deterministic LVP cycles and the random-uniform baseline. Tone reproduction at constant input matches the paper-derived formula exactly (Δ=0.25 → 75 % ink; Δ=0.5 → 50 %; Δ=0.75 → 25 %). Max LVP run-length holds to 3 px across the Δ ramp. Outputs in validation/output/limb1/, paper Fig. 7 extracted at docs/extracted/_limb_paper_fig7_reference.png.
clustered_dot	validation/inputs/sudanese.png + 768-px synthetic darkness ramp	Bayer 1973 §IV / Holladay 1980 spiral-grown clustered-dot tile. No paper-image reproduction (the references are recipe papers, not photographic-figure papers); validation criterion is local tone monotonicity. On the ramp at matrix_size=8, max deviation |ink_local − (1 − bright_local)| = 0.006 — within discretisation noise. Outputs in validation/output/am_screen1/.

am_screen has no directly reproducible paper figure (Bayer 1973 and Holladay 1980 are matrix-construction / algorithmic-recipe papers, not photographic-figure papers), so it is validated against the paper invariants. On sudanese.png at cell sizes 4, 8, 12 the area-conservation ratio Σπr² / Σ(1 − I) is 1.000 to three decimal places at every cell size — exact agreement with Bayer 1973 §IV. Outputs in validation/output/am_screen1/.

velho_gomes has been side-by-side validated against the four diagnostic figures of Velho & Gomes 1991. Outputs in validation/output/velho1/ and validation/output/_velho_paper_repro/. No code changes were required — the existing closed-form vectorised implementation reproduces all four figures (Fig. 4 cluster-size sweep, Fig. 6 indian boy at 150 dpi, Fig. 7 disc-with-stripes synthetic test, Fig. 8(A) indian boy at 75 dpi).

Paper figure	Source	Reproduction recipe
Fig. 6 — indian boy, 150 dpi, clusters of 11 px	validation/inputs/velho1.png	2× downsample → cluster_size=11
Fig. 7 — disc + horizontal-stripe background, 150 dpi, clusters of 11 px	synthesised	cluster_size=11
Fig. 8(A) — indian boy, 75 dpi, clusters of 32 px	validation/inputs/velho1.png	4× downsample → cluster_size=32
Fig. 4 — gradient stripes at clusters 2, 6, 12, 20, 32, 60, 120 px	synthesised	sweep cluster_size

Sample outputs

Limb 1969 dither — all four modes applied to sudanese.png. The two random modes show classical white-noise dither; the two deterministic LVP modes show the row-aligned 1-D ordered-dither character (vertical stripes are the LVP cycle tiled per row):

random_uniform (paper §I)	random_anti (paper §III)
deterministic n=4	deterministic n=7

The deterministic chopping-pattern strips reproducing Limb Fig. 7 (1-D ramp Δ = 0.3 → 0.7, n=4 and n=7 LVP cycles). The visible step-wise vertical transitions are expected: 1-bit thresholding of a length-n LVP only produces n + 1 discrete output densities (n=4 → 5 bands at 0/25/50/75/100 %; n=7 → 8 bands). The paper's smoothness comes from its multi-level quantizer output, not from any sub-cycle interpolation. For smooth-gradient 2-D image halftoning use clustered_dot (65 levels) or void_cluster (≥ 1025 levels):

Fig. 7(a) n=4 LVP	Fig. 7(b) n=7 LVP

Clustered-dot ordered dither on sudanese.png at three matrix sizes — characteristic spiral-grown clustered tile, coarser cells as matrix_size grows but tone preserved (Σ ink ≈ Σ darkness within rounding to within 1 pp at every size):

matrix=4	matrix=8	matrix=16

AM screen on sudanese.png at cell sizes 4, 8, 12 — the classical Lichtenstein / benday variable-radius dot screen. As cell_size grows the dot resolution coarsens but per-cell ink area is preserved:

cell=4	cell=8	cell=12

Caveat — same family as the Limb 1-bit density-step limit. Both am_screen and clustered_dot are periodic AM screens at axis-aligned angle, so they show three characteristic artefacts that are inherent to the algorithm family (not bugs): visible cell/tile periodicity on smooth gradients, mid-tone tone-inversion in am_screen around 50 % gray (dots overlap, ink/paper roles flip), and a finite density LUT of n² + 1 levels per tile in clustered_dot (e.g. 65 at matrix=8 → ~ 1.5 % step spacing). Production printing avoids these by cell rotation + supercell tiling (Holladay 1980) + stochastic perturbation; our implementations are axis-aligned only, by design. For periodicity-free output use the FM blue-noise algorithms further down (void_cluster, ostromoukhov, floyd_steinberg).

Velho-Gomes on velho1.png (Indian boy, charcoal study) at the paper's two cluster sizes:

Fig. 6 (150 dpi, cluster=11)	Fig. 8(A) (75 dpi, cluster=32)

Invisible dots (FM ordered) (1)

FM (frequency-modulated) halftones keep every dot at unit pixel size and encode tone in dot density, dispersing the dots so that no periodic structure is visible at viewing distance. The ordered-dither variant compares each pixel against a per-pixel threshold from a precomputed mask — no information flows between pixels at dither time, so output is deterministic per pixel and trivially parallel; all the design effort lies in constructing a threshold mask whose every level is blue-noise distributed.

Key	Description
void_cluster	Ulichney 1993 — void-and-cluster blue-noise mask.

Paper-faithfulness validation

Algorithm	Test image	Reproduces
void_cluster	validation/inputs/ulichney1.png (Lena, 512×512)	Ulichney Figs 6(c), 7(c) — 32×32 array, σ=1.5. Outputs in validation/output/ulichney1/_void_cluster_paper_*.png

Sample outputs

Void-and-cluster on the synthesised 10-step gray ramp with the paper's 32×32 σ=1.5 array reproduces Fig. 6(c)'s diagnostic: dispersed-dot blue-noise character at every level, no directional artifacts. (The Fig. 7(c) natural-image reproduction lives in validation/output/ulichney1/.)

Invisible dots (FM error-diffused) (10)

The error-diffused variant of FM halftoning quantises pixel-by-pixel in a scan order and propagates the quantisation error to unprocessed neighbours so the running mean tracks the input — via the classic feed-forward kernels (floyd_steinberg, classical_ed), a class-matrix dispersion order (dot_diffusion), a space-filling-curve scan with decaying error history (riemersma), input-level-dependent coefficients (ostromoukhov), or carry-only IGS quantisation (kimoto_igs). Several later variants modulate the diffusion or threshold per pixel based on local structure to preserve edges and texture (structure_aware — simulated annealing on a tone+structure objective rather than strict scan-order ED — chang_edr, li_mould, shi_li).

All ten output ink/no-ink on the input grid by design — there's no underlying smooth geometry to extract. SVG export traces the ink regions into pixel-exact boundary paths (even-odd fill, holes preserved), so the SVG is true vector geometry yet renders identically to the PNG.

Key	Description
floyd_steinberg	Floyd-Steinberg 1976 — error-diffusion.
classical_ed	Jarvis-Judice-Ninke 1976 / Stucki 1981 / Burkes 1988 / Sierra 1989 (full / two-row / lite) / Atkinson 1988 — the seven canonical post-Floyd-Steinberg kernels under one dispatcher; pick via the kernel choice param. All textbook recipe papers with no algorithmic machinery beyond the kernel matrix + serpentine scan.
dot_diffusion	Knuth 1987 — class-matrix dispersion.
riemersma	Riemersma 1998 — Hilbert-curve dither with windowed exponential decay.
ostromoukhov	Ostromoukhov 2001 — variable-coefficient EDR.
structure_aware	Pang 2008 — simulated annealing on a tone+structure objective.
chang_edr	Chang 2009 — structure-aware EDR (Class II): Gabor-modulated threshold + anisotropic-Gaussian diffusion blended with Ostromoukhov standard. Paper-faithful architecture; calibration heuristic (paper's ~1.3 MB observer-tuned LUT is unpublished).
li_mould	Li & Mould 2010 — contrast-aware EDR.
kimoto_igs	Kimoto 2013 — Improved-Gray-Scale (IGS) carry-only quantization along a configurable scan path (Hilbert / raster / random). Exact DC conservation (paper §2.2 Eq. 10). Multi-level by design (paper says bi-level looks worse than Floyd-Steinberg); 1-bit output here is for catalog completeness.
shi_li	Shi & Li 2014 — Laplacian sharpening + Hwang-Haddad adaptive median filter (RAMF) + Stucki error diffusion. Edge enhancement boosts contrast in weak-texture regions before dithering.

Paper-faithfulness validation

Each algorithm has been validated end-to-end against the closest paper-faithful reference — published figure panels extracted from the PDFs at 300 dpi, author-hosted reference outputs, or, for recipe papers without reproducible figures, the papers' own invariants on synthetic ramps; per-algorithm details in the table. riemersma is the only algorithm in the catalog still pending (its reference is the CompuPhase HTML article, not a peer-reviewed paper with reproducible figures).

Algorithm	Test image	Reproduces
floyd_steinberg	validation/inputs/floyd_steinberg1.png (Michelangelo's David, 180×215, from Wikipedia)	Wikipedia's public-domain Floyd-Steinberg dither of the same source (paper-canonical 7/16, 3/16, 5/16, 1/16 weights). Outputs in validation/output/floyd_steinberg1/_floyd_steinberg_paper_*.png
classical_ed	validation/inputs/floyd_steinberg1.png (David head) + synthetic black→white ramp	Jarvis-Judice-Ninke 1976 / Stucki 1981 / Burkes 1988 / Sierra 1989 (full / two-row / lite) / Atkinson 1988 — none of the five papers ships a canonical reproducible figure (all are recipe papers). Validation criteria: (1) tone conservation on a synthetic ramp — every kernel preserves DC to within 0.01 pp by construction (Atkinson drops 25 % of the quantisation error per its 6× 1/8 weights, but the drop is uniform across the ramp and doesn't bias the mean); (2) visual side-by-side on David — each kernel reproduces its characteristic published signature (Stucki/Burkes smoother midtones than FS, Sierra-lite coarser, Atkinson the high-contrast HyperCard look). Outputs in validation/output/classical_ed/_classical_ed_david_*.png and the 8-up composite _classical_ed_david_grid.png.
dot_diffusion	validation/inputs/knuth1.png (Mona Lisa, 250×360, from Wikimedia "Digitally Restored and Color Balanced" scan)	Knuth Fig. 5 — 8×8 class matrix from §4, 2-orthogonal / 1-diagonal weighting per Knuth's dot-diff.w WEB source. Reference plate extracted from PDF saved at validation/inputs/knuth1_reference.png. Outputs in validation/output/knuth1/_knuth_paper_*.png
ostromoukhov	validation/inputs/ostromoukhov1.png (black-swallowtail butterfly, 216×216)	Ostromoukhov Fig. 3 — paper-exact input and reference halftone (input.pgm / output.pgm) come from the author's own bundled C distribution at the URL cited in the paper's footnote. We replicate the C reference pipeline (216→512 nearest-neighbour upscale, then 256 input-dependent distribution-coefficient sets from Appendix I) and compare pixel-by-pixel against output.pgm. Outputs in validation/output/ostromoukhov1/_ostromoukhov_paper_*.png
structure_aware	validation/inputs/pang1.png (Van Gogh self-portrait, 508×603)	Pang Fig. 13 — source and SAH reference from the authors' project page (V3.png / V3_eg2.png). Paper-faithful schedule (σ=1.5, w_tone=0.5, T₀=0.2, anneal=0.8, T_stop=0.01, 14 cooling steps × N swaps), warm-started from Floyd-Steinberg. Inner loop JIT-compiled with Numba (~6× faster than pure NumPy). Outputs in validation/output/pang1/_pang_paper_*.png
chang_edr	Chang 2009 Fig 7 panels — ribbon woven texture (_chang_paper_fig7_ribbon_*.png) and arm/shoulder anatomy (_chang_paper_fig7_arm_*.png), each extracted from the 300-dpi PDF page 8 reference	Chang Fig. 7 — Class II structure-aware EDR. Paper-faithful §3 architecture (Gabor-modulated threshold + anisotropic-Gaussian diffusion blended with Ostromoukhov standard); paper §3.3 psychophysical calibration LUT (~1.3 MB, observer-tuned) is unpublished, so we use heuristic calibration from structure-tensor coherence + a 4-frequency × 8-orientation Gabor bank approximating §2.1 per-pixel local-frequency selection. Outputs in validation/output/chang1/_chang_paper_fig7_*.png.
li_mould	three test images extracted from paper Figs. 1 & 6 (arm, ribbon, cat)	Li & Mould Figs. 1 & 6 — for each test the paper shows the input grayscale alongside "Our basic method", so we extract panels (a) and (d) from the PDF, run our li_mould_dither on (a) with the paper's recommended 7×7 mask and k=2.6, and compare against (d). Extracted source/reference panels in docs/extracted/_li_mould_paper_*.png, our outputs in validation/output/li_mould1/
kimoto_igs	Kimoto 2013 Figs 4 + 7 + 10 — synthetic 256×256 vertical / horizontal ramps (Fig 4a/b specs) under raster vs Hilbert scanning, uniform-tone patches for DC-conservation check (Eq. 10), and Fig 4(c) Barbara extracted from the PDF at 300 dpi with comparison against Fig 10 row (a) IGS-HIL panel	Kimoto Fig 7 — raster scanning produces the paper's characteristic looping-arc artefacts on the vertical ramp and regular vertical stripes on the horizontal ramp; Hilbert scanning suppresses both into a clean blue-noise-like distribution. DC conservation is exact (0.00 pp deviation at every uniform tone, Δ = 0.02 pp on Barbara). Outputs in validation/output/kimoto1/_kimoto_paper_*.png.
shi_li	Shi & Li 2014 Figs 3 + 4 — snail-shaped organ (Fig 2(a) Original + Fig 3(d) "Our method") and arm/shoulder (Fig 4(a) Original + Fig 4(d) "Our method"), each extracted from the 300-dpi PDF pages 4–5	Shi & Li Figs 3 & 4 — Laplacian-enhanced + RAMF + Stucki (serpentine scan) pipeline reproduces paper character: paper-white interiors in flat bright regions, dark crisp Stucki dot patterns along structural boundaries. Ink fraction matches the source tone target to 0.2 pp on both test images (arm 22.1 % vs 22.1 %, snail 21.8 % vs 22.0 %) and stays within ~3 pp of the paper's printed reference panels. Outputs in validation/output/shi_li1/_shi_li_paper_*.png.

Sample outputs

Floyd-Steinberg on floyd_steinberg1.png (David head, 180×215) side-by-side with the Wikipedia reference. Tone reproduction is exact (our 42.6% ink vs Wikipedia's 43.4% ink, both equal to 1 − source mean brightness within 1 pp); the characteristic FS "wormy" texture in flat regions and edge sharpening on the silhouette match. Pixel-wise agreement is ~67% — typical for FS implementations against each other (the same scan-direction switch in our own code, raster ↔ serpentine, also moves ~33% of pixels), since error diffusion is chaotic at the per-pixel level even when the global pattern statistics are equivalent.

Source — David, 180×215	Wikipedia reference — Floyd-Steinberg	Ours — floyd_steinberg, paper-canonical raster

The seven classical_ed kernels on the same David head, all with serpentine scan. Tone matches the FS baseline within ~1 pp on every kernel (Atkinson is 1.1 pp lighter — its 25 % error-loss pushes bright fields a touch brighter, the signature HyperCard look). The visual character differences the papers actually advertise are all present: Jarvis / Stucki / Burkes give smoother midtones than FS (slightly larger, slightly heavier diffusion footprints); Sierra-full is between Jarvis and FS; Sierra two-row drops the third row for half the work; Sierra-lite collapses to a one-row 4-coefficient kernel that runs faster than FS but reads slightly coarser; Atkinson's signature high-contrast / shorter-leg distribution is unmistakable in the shadows under the chin.

Dot diffusion on knuth1.png (Mona Lisa, 250×360) side-by-side with Knuth Fig. 5 extracted from the PDF. The 8×8 class-matrix dot pattern, the absence of any scan-direction "worm" texture, the parallel-class-order edge response, and the overall tone distribution (bright face and collar, light sky, dark hair/dress, mid-tone hands) all match the paper. Tone preservation is exact: 67.3% ink equals 1 − source mean brightness (32.7%) to within 0.1 pp. Knuth's source was a 1985 "high-quality television image" of the painting — no surviving copy of his exact bitmap exists, so we use the public-domain Wikimedia "Digitally Restored and Color Balanced" scan, downsampled to the paper's 250×360 8-bit (r+0.5)/256 grid (§7). Several Wikimedia restorations were trialled; the restored/balanced version best matches Knuth's mid-tone distribution (the C2RMF retouched scan is colorimetrically accurate but renders ~3 pp darker overall, putting too much of the background into solid black).

Source — Mona Lisa, 250×360	Knuth Fig. 5 reference (extracted from PDF)	Ours — dot_diffusion

Ostromoukhov on ostromoukhov1.png (black-swallowtail butterfly, 216×216) — the canonical Fig. 3 test image. Both source and reference halftone come from Ostromoukhov's own bundled C distribution (input.pgm / output.pgm from varcoeffED.tar, the URL given in the paper's footnote); we replicate his pipeline (216→512 nearest-neighbour upscale, then dither). Result: byte-identical to the reference (100.00% pixel match, 36.15% ink versus 36.15%).

Source — butterfly, 216×216	Reference — output.pgm from the author's C distribution	Ours — ostromoukhov after 216→512 nearest-neighbour upscale

Pang SAH on pang1.png (Van Gogh self-portrait, 508×603). Source and the SAH reference are both from the project page bundled alongside the paper. SA is stochastic so we don't expect bit-exact agreement; the comparison criterion is tone preservation, structure preservation, and visual character. Our SAH converges in ~7 minutes with the Numba-JIT inner loop; the resulting halftone clearly preserves the swirly background and beard texture, with 40.24% ink versus the reference's 39.82% (within 0.5 pp) and 77% pixel agreement.

Source — Van Gogh portrait, 508×603	Reference — SAH from the authors' project page	Ours — structure_aware, paper-default schedule

Chang 2009 SA-EDR validation, against the paper's own Fig 7 panels. Two test images from Fig 7 — the ribbon woven texture (row 1) and the arm/shoulder anatomy (row 2) — have full-size Original panels we can extract at 300 dpi from the PDF and use directly as input to chang_edr; the Our method column gives Chang's published halftone of the same image as the paper reference. Pattern matches the validation strategy used for Li & Mould 2010 below. The arm panel reproduces paper character almost pixel-for-pixel; the ribbon panel is close — woven crosshatching and ribbon contours survive, with slightly heavier ink than the paper at the ribbon edges:

Test image	Source — cropped from Fig 7 "Original" column	Paper reference — Chang Fig 7 "Our method" column	Ours — chang_edr
ribbon (Fig 7 row 1)
arm/shoulder (Fig 7 row 2)

Li-Mould against the paper's own Fig. 1 and Fig. 6 panels. Each row shows the paper's input grayscale (panel a) extracted from the PDF, the paper's "Our basic method" halftone (panel d) extracted from the same figure, and our li_mould_dither output on the same input (7×7 mask, k=2.6 per §3.1). All three reproductions show the contrast-aware ink concentration the paper claims: dots cluster along structural edges (muscle striations, woven seams, fur), while uniform-tone regions stay clean. Tone reproduction is close (within 2 pp for arm and ribbon; the cat differs by ~10 pp because of how the JPEG-rendered reference panel was extracted from the PDF and inverted to a bool ink mask). Pixel-wise agreement is 66–74%, on the same order as our other error-diffusion implementations against their references.

Test image	Source — extracted from PDF	Reference — paper's "Our basic" panel	Ours — li_mould_dither
arm (Fig. 1)
ribbon (Fig. 6)
cat (Fig. 6)

Kimoto IGS reproducing paper Fig 7. The 256×256 vertical / horizontal ramps (paper Fig 4a/b specs) are run under both raster and Hilbert scanning. Raster produces the paper's characteristic geometric artefacts (looping arcs on vertical ramp, regular stripes on horizontal ramp); Hilbert suppresses both into clean blue-noise-like distributions. DC tone preservation is exact (every uniform-tone patch matches 1 − brightness to 0.00 pp). Per paper §5, bi-level IGS is intentionally inferior to Floyd-Steinberg; the algorithm's value is for multi-level (N ≥ 3) output devices not modelled by monochromizer's 1-bit compositor.

Source	Ours — kimoto_igs, scan = raster	Ours — kimoto_igs, scan = hilbert
Vertical ramp (Fig 4a)
Horizontal ramp (Fig 4b)

Kimoto IGS on a natural image: Fig 4(c) Barbara extracted from the paper PDF at 300 dpi, halftoned via IGS-HIL (Hilbert scan, N=1). Compared against the paper's Fig 10 row (a) right-column IGS-HIL panel (cropped from the same 300 dpi PDF extract). Caveat: paper Fig 10 panels are zoomed sub-regions of Barbara (headscarf + chair caning area), while our output is the full Barbara crop — so the comparison is qualitative on visual character rather than pixel-level alignment. Visual character match: both show the grainy IGS-HIL N=1 distribution, both preserve scarf-stripe and chair-caning directional structure, both confirm the paper's §5 admission that bi-level IGS-HIL is grainier than Floyd-Steinberg (shown for comparison in the second column from Fig 10 row (a) left):

Source — Fig 4(c) Barbara	Paper reference — Fig 10 row (a), EDF-FS (Floyd-Steinberg baseline)	Paper reference — Fig 10 row (a), IGS-HIL (Hilbert N=1)	Ours — kimoto_igs, scan=hilbert N=1

Shi & Li 2014 against the paper's own Fig 3 (snail-shaped organ) and Fig 4 (arm/shoulder), each extracted from the 300-dpi PDF. The snail's source is the Fig 2(a) Original panel above the dither comparison; the arm has Original and "Our method" in the same Fig 4. The implementation is paper-faithful: §3.1 recommended kernel [1 -2 1; -2 5 -2; 1 -2 1], Hwang-Haddad RAMF (with Gonzalez-Woods edge-preserving fallback at max window), Stucki coefficients per Table 1 with serpentine scan. Tone reproduction is close (ink fractions within ~3 pp of paper references). However the visual character of the paper's Fig 3/4 panels — bold solid spiral ridges + clean paper-white interiors — is only partially reproduced; our output looks closer to a plain Floyd-Steinberg on the same input than to the paper's published ShiLi panel. The cause is unidentified after extensive auditing; the paper provides only low-resolution rendered figures and no source images or reference code, so the residual gap may stem from print/typesetting effects in the published PDF rather than from our implementation.

Test image	Source — extracted from PDF	Paper reference — "Our method" panel	Ours — shi_li_dither
arm (Fig 4)
snail (Fig 3)

Off-grid stipple — Voronoi / Lloyd (4)

Stippling renders tone as a point cloud — N dots placed in continuous 2-D space (not on the pixel grid) so the local point density matches the input darkness. The basic idea, common to all three off-grid stipple groups below, is that of equal-area cells: cover the canvas with cells whose number-of-dots-per-area follows the input density, then place one dot per cell. The groups differ in how the cells are chosen and relaxed; output is always a list of dot centres + radius — SVG-native, scalable.

This group is the classical formulation: Voronoi cells around the current dot positions, iteratively moving each dot to its cell's centroid (Lloyd's method). Density-weighted centroids (secord) give tone reproduction via the relaxation step itself; uniform centroids (deussen) rely on density-biased seeding instead; capacity constraints (balzer, balzer_lloyd) force exactly equal per-cell mass.

Key	Description
deussen	Deussen 2000 — Floating Points. Pulse-Density Modulation seeds dots in proportion to local ink density; uniform-centroid Lloyd's method then smooths the distribution into an approximate Poisson disc set. Pre-Secord; the tone is encoded by the PDM seeding, not by the relaxation.
secord	Secord 2002 weighted Voronoi (Lloyd's method).
balzer	Balzer 2009 strict pairwise-swap CCVT.
balzer_lloyd	Balzer-Lloyd CCVT approximation (same paper).

Paper-faithfulness validation

secord and balzer have been side-by-side validated against their source papers using test images named after the algorithm authors; deussen against the Fig 2 grasshopper-eye panels extracted from the PDF. Outputs in validation/output/deussen1/, validation/output/secord{1,2,3}/, validation/output/balzer1/, and validation/output/_stipple_paper_repro/.

Algorithm	Test images	Reproduces
deussen	Deussen 2000 Fig 2 grasshopper's eye, extracted from PDF page 5 at 300 dpi	Deussen Fig 2 — PDM seeding + uniform-Lloyd relaxation, with Voronoi cells auto-clipped to the inked region (paper §4.3 step 2 with auto-derived polygon in place of hand-drawn). We compare our output against the paper's Fig 2(b) PDM init panel rather than Fig 2(c) post-relaxation: ours is a single auto-polygon relaxed at full PDM tone, whereas Fig 2(c) is hand-segmented into independently-relaxed regions (eye interior, cornea, exterior) with the eye-border dots size-reduced for contrast — editor operations an auto-derived single polygon can't approximate. Outputs in validation/output/deussen1/_deussen_paper_eye_*.png.
secord	validation/inputs/secord{1,2,3}.png (peperomia, mannequin, climbing shoe)	Secord Figs. 3, 6, 7, 9 — outputs in validation/output/secord{1,2,3}/_secord_paper_*.png
secord (synthetic)	constant-tone patches	Secord Fig. 11 — 9 stipple levels at n ∈ {1000, …, 0} step 125, output validation/output/_stipple_paper_repro/fig11_composite_3x3.png
balzer / balzer_lloyd	validation/inputs/balzer1.png (bromeliad plant)	Balzer Fig. 7 — outputs in validation/output/balzer1/_balzer_paper_*.png
balzer (synthetic)	quadratic-ramp strip	Balzer Fig. 6 density-adaptation diagnostic — validation/output/_stipple_paper_repro/fig6_quadratic_ramp__*.png. Per-quarter density adaptation matches paper to <0.5% deviation; capacity error δc matches paper qualitatively (within ~5× at default samples_per_site=16, closer with higher sps).

Sample outputs

deussen reproducing Deussen 2000 Fig 2 (grasshopper's eye). PDM seeds 8500 dots in proportion to local ink density; 15 iterations of uniform-centroid Lloyd's method then relax the distribution toward Poisson disc, with Voronoi cells clipped to the inked region of the image. The "region to be stippled" boundary (paper §4.3 step 2) is auto-derived from the source's tonal envelope here — the paper's editor would have the user hand-draw it. This keeps dots from drifting into the photograph's white background. We compare against the paper's Fig 2(b) PDM initialisation rather than Fig 2(c) post-relaxation: ours is a single auto-polygon relaxed at full PDM tone (~34% ink), whereas Fig 2(c) is hand-segmented into independently-relaxed regions (eye interior, cornea, exterior) with the eye-border dots size-reduced for contrast (~26% ink) — editor operations an auto-derived single polygon can't approximate. Comparing against (b) is the honest paper-faithfulness benchmark for our single-polygon pipeline; relaxing further toward Fig 2(c) needs the paper's multi-region segmentation:

Source — Fig 2(a) grasshopper eye photograph	Paper reference — Fig 2(b) PDM initialisation	Ours — deussen, n=8500, 15 iters

Secord on secord{2,3}.png at the paper's low-N edge-preservation settings (Figs. 6 and 9):

Fig. 6 — mannequin, n=1000, r=5×10⁻³	Fig. 9 — climbing shoe, n=5000, r=3×10⁻³

Secord vs Balzer on balzer1.png (bromeliad), reproducing paper Fig. 7b vs 7c — secord (n=20000) gives slightly more uniform tone, balzer (CCVT, here at n=5000 because the paper-literal Algorithm 1 is too slow at n=20000 in pure Python) gives sparser dots with no regularity artifacts. balzer_lloyd (the Lloyd-style approximation) is shown at n=20000 with samples_per_site=64, max_iterations=10 — higher sps refines the per-iteration centroid estimates (position noise ≈ σ_cell / √sps). (An earlier clumping artifact attributed here to low sps defaults was in fact a bug in the capacity-overflow fallback — leftover samples were assigned to an arbitrary site instead of the nearest non-full one — fixed and regression-tested against a count-in-cell variance bound.):

Fig. 7b — secord, n=20000	Fig. 7c — balzer (CCVT), n=5000	Fig. 7c — balzer_lloyd, n=20000, sps=64, it=10

Off-grid stipple — Optimal transport (3)

Optimal-transport stipplers make the equal-area-cell idea exact: formulate the dot layout as the optimal-transport map from the uniform measure to the input density. Power diagrams (degoes) enforce equal per-cell mass via per-cell weight Newton iteration; grid OT (nader) inverts a Halton sequence through a grid-based transport map; sliced OT (sot) projects to 1-D for tractable iteration.

Key	Description
degoes	De Goes 2012 power-diagram optimal transport.
nader	Nader & Guennebaud 2018 grid-based instant transport.
sot	Paulin 2020 sliced optimal transport.

Paper-faithfulness validation

degoes and nader run on the same zebras test image at De Goes' Fig. 3 settings, giving a direct side-by-side of the two OT formulations; sot has no published stippling figure to reproduce. Outputs in validation/output/degoes1/.

Algorithm	Test images	Reproduces
degoes	validation/inputs/degoes1.png (zebras)	de Goes 2012 Fig. 3, n=40000, r=1.5×10⁻³ — output validation/output/degoes1/_degoes_paper_fig3_zebras_n40k.png
nader	validation/inputs/degoes1.png (zebras, reused)	Nader 2018 at n=40000, r=1.5×10⁻³ — output validation/output/degoes1/_nader_paper_fig3_zebras_n40k.png. Nader's source paper uses different test images, but the visual character (grid-OT uniform blue-noise vs power-diagram OT crispness) is the per-algorithm criterion. Same image as De Goes for direct side-by-side.
sot	—	Paulin 2020 has no stippling figures in the source paper (the paper is about Monte Carlo rendering — Fig. 1 shows San Miguel scene comparisons of white noise / Sobol / SOT). sot is in the catalog for completeness; its implementation is paper-faithful to Algorithm 1 but there's no published image to side-by-side against.

Sample outputs

degoes (paper Fig. 3 settings: n=40000) vs nader on degoes1.png (zebras, n=40000, r=1.5×10⁻³). De Goes' power-diagram OT enforces equal cell mass via capacity-Newton, giving uniform blue-noise distribution; Nader's grid-OT inverts an unscrambled Halton sequence through the OT map for similar blue-noise character:

de Goes 2012 (power-diagram OT, n=40000)	Nader 2018 (grid OT, n=40000)

Off-grid stipple — Other (3)

Three stipplers that fit neither the Lloyd-relaxation nor the optimal-transport formulation:

• Example-based (kim) — match per-tone GLCM texture statistics of an artist-supplied or proxy exemplar; synthesise new distributions via Metropolis spin-flip that share the exemplar's bigram structure.
• Physics / electrostatic (schmaltz) — treat dots as electrostatic charges that repel each other and are attracted to dark regions; simulate to equilibrium.
• Kernel-based (ahmed) — Gaussian-kernel gradient descent on a blue-noise energy.

Key	Description
kim	Kim 2009 — Stippling by Example. Captures GLCM texture statistics of an exemplar distribution, synthesizes new textures via Metropolis Spin-Flip, then renders using §4.1 probability-based tone selection. The artist's hand-drawn tone map (paper §3.1, William M. Andrews) is substituted by procedurally generated proxy exemplars — see paper-faithfulness note below.
schmaltz	Schmaltz 2010 electrostatic halftoning.
ahmed	Ahmed 2022 Gaussian Blue Noise — paper-faithful §4.10 adaptive sampling on the §4.6 bounded domain. A kd-tree neighbour cutoff at 4σ makes the paper's recommended iteration counts tractable on CPU.

Paper-faithfulness validation

Algorithm	Test images	Reproduces
kim	Procedurally-generated proxy exemplars at 10 tone levels (texture_size=64) — see note	Kim 2009 §3.3 GLCM analysis + §3.4 Metropolis Spin-Flip synthesis + §4.1 probability-based tone rendering. Algorithm-faithful core; ACE drops 10–30× from random init to synthesized for each non-degenerate tone (validation script logs initial vs. final ACE per tone). The paper's Source | Reference | Ours triplet is not reachable: the paper's figures depend on William M. Andrews' hand-drawn tone maps (Fig 3) which cannot be redistributed, and the artist character those marks carry is the part the catalog can't reproduce without them. Validation produces kim_tone_grid.png (exemplar vs. synthesized per tone) and kim_render_sudanese.png (full-pipeline render) in validation/output/kim1/.
schmaltz	validation/inputs/schmaltz{1,2}.png (Leonardo Leda head, skull)	Schmaltz Figs. 5, 6 — outputs in validation/output/schmaltz{1,2}/_schmaltz_paper_*.png.
ahmed	validation/inputs/ahmed{1,2}.png (bromeliad, cathedral interior)	Ahmed Figs. 15, 17. Reaches paper-faithful 10K iterations on CPU (~12 min for cathedral at N=100K) via kd-tree neighbour cutoff at 4σ (O(N²) → O(N·k_avg≈28), 257× per-iter speedup). Validation saves 1× PNG, 4× PNG (sub-pixel preserving), and SVG (vector-exact); the 1× raster aliases sub-pixel dot positions and looks grainier than the underlying point set actually is.

Sample outputs

kim — example-based stippling on procedural proxy exemplars. The two exemplar_style options demonstrate the algorithm's core value proposition: feeding the same pipeline an isotropic exemplar (dots) vs. a deliberately anisotropic one (hatched, full-width horizontal lines on widely-spaced rows, nested across tones) produces visibly different output character on the same input image. Both styles run through the paper's full §3.3 GLCM + §3.4 Metropolis Spin-Flip synthesis + §4.1 probability-blend rendering pipeline. The midtone patch panel below makes the transfer most obvious — at 50 % gray, the dots render is isotropic blue noise (H/V neighbour-pair ratio ≈ 0.88), the hatched render concentrates along horizontal streaks (H/V ≈ 2.71 — almost 3× more horizontal than vertical neighbour pairs even after the synthesis Metropolis pass scrambles some row geometry).

The proxy character does not mimic Kim et al.'s paper Fig 3 (William M. Andrews' hand-drawn artistic stipple — isotropic round marks with natural irregularity). The proxies are deliberately simple procedural patterns chosen so the algorithm's structure-transfer effect is visible, not so they look artistic. With a user-supplied artist exemplar in place of the proxies, the same machinery would carry the artist's mark style — elongated brushstrokes, clumped marks, directional preferences — into the output the same way hatched carries its horizontal preference here.

exemplar_style="dots" (Mitchell's best-candidate at light tones, uniform random for dense — FM-noise character baseline). Each tone grid below shows the proxy exemplar (top row) above the §3.4 Metropolis Spin-Flip synthesis output (bottom row) — same-density layouts, distinct realisations:

Exemplar (top) vs. §3.4 Metropolis synthesis (bottom) across 10 tones	Sudanese render (kim, n=5000)	50 % midtone patch (256², n=3000, r=0.6)

exemplar_style="hatched" (full-width horizontal lines on bit-reversed-ordered rows, nested across tones — tone t+1's row set is a superset of tone t's — so §4.1 adjacent-tone blending preserves the line layout instead of averaging two independent random ones). Same §3.4 Metropolis synthesis as dots, then same §4.1 render. The synthesized texture's rows are partly scrambled by greedy Metropolis (GLCM is a 2nd-order statistic and doesn't constrain full-row runs), but the horizontal anisotropy still measurably survives — the rendered output reads as visibly hatched:

Exemplar (top) vs. §3.4 Metropolis synthesis (bottom) across 10 tones	Sudanese render (kim, n=5000)	50 % midtone patch (256², n=3000, r=0.6)

Nested-tone row exemplars are a departure from paper §3.2's per-tone independent extraction; they're the procedural analog of "an artist's style is consistent across tone levels" — paper-spirit if not paper-procedure.

Schmaltz Fig 5 (Leonardo Leda head) and Fig 6 (skull). At paper-exact resolution + N + iteration count, with chunked + float32 inner loops to fit the O(n²) memory budget:

Schmaltz Fig. 5 — Leda head, paper-exact (256×256, n=20k, 300 iters; 4× upsample for display)	Schmaltz Fig. 6 — skull, r=1.0

Ahmed Fig 15 (bromeliad) and Fig 17 (cathedral interior). Paper-exact resolution and N, with the kd-tree neighbour cutoff (4σ) making the 10K-iteration paper convergence reachable on CPU (the cathedral panel below is the 5000-iteration fast render; 10K via a de Goes warm-start):

Ahmed Fig. 15 — bromeliad	Ahmed Fig. 17 — cathedral (512×768, n=100k, 5000 iters)

Tone-following hatching (5)

Hatching algorithms render the input image as a field of tone-following ink lines, dots, or artistic shapes. Unlike the contour family (which traces edges from gradients), the line / shape geometry here doesn't come from the image's gradient — it comes from an artist-supplied screen element shape (Ostromoukhov-Hersch 1995), a parametric layered threshold structure (Ostromoukhov 1999), an image used directly as a dither screen (Veryovka-Buchanan 1999), an example stroke set (Jodoin 2002), or a reaction-diffusion PDE simulation (Mesquita-Walter 2019).

Key	Family	Output	Description
artistic_screen	parametric	mask (1-bit raster)	Ostromoukhov-Hersch 1995 — Artistic Screening. Classical AM screening generalised so the dot SHAPE can be any artist-designed element (circle / diamond / star spot functions, or text glyph for the microletter character of paper Fig 17). The artist-drawn Bézier-contour sets at multiple intensity levels (paper §3) are substituted by procedural shapes and glyph rasterisation — see paper-faithfulness note below.
ostromoukhov_engrave	parametric	mask (1-bit raster)	Ostromoukhov 1999 — Digital Facial Engraving. "Universal copperplate" triangle-wave threshold matrix produces variable-width parallel lines under standard threshold dithering. Multi-layer composition via five paper §2.2 merge modes (copy / smaller / bigger / multiply / add) supports cross-etching and continuous-lines-in-dark fills. The artist-drawn Coons-patch warping (paper §2.1 Fig 5) and per-layer hand-painted Photoshop masks (Fig 5 middle row) are substituted by uniform parametric grids and scalar S, D per layer; flow_strength > 0 bows the furrows around the image's relief (smoothed-image displacement along the line normal) as an automatic stand-in for the warping — see paper-faithfulness note below.
veryovka_screen	parametric	mask (1-bit raster)	Veryovka-Buchanan 1999 — Halftoning with Image-Based Dither Screens. Generalises (1) by using an arbitrary image (CLAHE-equalised) as the dither threshold matrix. Combined with α-blended Floyd-Steinberg error diffusion (Eq. 1) for tone accuracy. Photorealistic mode uses the input image itself as the screen (dot clusters align with image features); artistic mode (Python API only) uses a separate texture image.
jodoin	example	strokes (vector)	Jodoin 2002 — Hatching by Example. Shannon's N-gram (Efros-style) texture synthesis adapted to parametric strokes: given a training stroke sequence Z_t, synthesize a longer sequence Z_g whose stroke-bigram structure matches Z_t. The artist-drawn Z_t and the artist-drawn 2D placement paths (paper §3.2, Fig 8) are substituted by procedural proxy stroke sets and tone-weighted seed sampling — see paper-faithfulness note below.
reaction_diffusion_woodcut	parametric	mask (1-bit raster)	Mesquita-Walter 2019 — Reaction-Diffusion Woodcuts (UFRGS Master's thesis, CC BY-NC-SA, substituting the paywalled Mello-Jung-Walter 2007 GRAPHITE paper that monochromizer originally targeted). Builds a per-pixel parameter map (orientation θ, stroke-size S, stripes-vs-spots δ) via Sobel + Witkin-Kass structure-tensor smoothing, then simulates anisotropic Turing reaction-diffusion (paper §3.2) with rotated 3×3 diffusion kernels per pixel. Final binarisation: 3×3 median + Otsu. Plain-black / plain-white intensity gates (paper §3.1.1 Tlow / Thigh) preserve the input's pure regions; segmentation-based preprocessing and noise filters (§3.1 borders + §3.3 Gaussian/Poisson/Contoli) are not implemented — see paper-faithfulness note below.

Paper-faithfulness validation

Algorithm	Test images	Reproduces
artistic_screen	Procedurally-generated screen shapes (circle / diamond / star spot functions, plus glyph-rasterised text); rendered on validation/inputs/ostromoukhov1.png (butterfly) and validation/inputs/sudanese.png	Ostromoukhov-Hersch 1995 §2 spot-function path (procedural shapes — circle / diamond / star) + §3 contour-based path (glyph rasterisation as a proxy for the paper's artist-drawn Bézier contour sets). Paper figures Fig 6 (Escher fish), Fig 11 (SIGGRAPH95 letters), Fig 17 (microletter portrait) are not reachable: they depend on artist-drawn Bézier-contour sets per intensity level. The §2 path with procedural spot functions is paper-faithful arithmetic; the §3 path uses PIL glyph rasterisation in place of the paper's contour interpolation, which collapses §3's "blend Bézier curves at intensity level z" step into a single rasterisation. The microletter-portrait character of Fig 17 reproduces with shape="text". Validation produces screen_growth_<shape>.png (per-intensity-level cell-growth grid analogous to Fig 9), screen_butterfly_<shape>.png / screen_sudanese_<shape>.png (full-pipeline renders), and screen_microletter_sudanese.png (Fig 17 character) in validation/output/artistic_screen1/.
ostromoukhov_engrave	Synthetic Fig 4 sample image (gradient + 4 flat patches); paper Fig 6 Michelangelo Giuliano and Fig 8 female-with-glasses (recovered from the paper's published engravings via Gaussian blur); also validation/inputs/ostromoukhov1.png (butterfly) and validation/inputs/sudanese.png	Ostromoukhov 1999 §2.1 universal copperplate (triangle-wave threshold matrix) + §2.2 five merge modes (copy, smaller, bigger, multiply, add) + §2.3 equilibration via CDF flattening. Paper Fig 4 panels (a)-(d) reproduce on the sample image to ≤ 1 % tone error. The paper's result figures are artist work, not algorithm output — §3.2: "The engraving styles in Fig. 6 and Fig. 9 have been adjusted to the photos manually", with automatic adjustment listed only as future work. Two paper-figure triplets (Source | Paper engraving | Ours) therefore make the artist-vs-automatic gap visible rather than attempt to close it: Fig 6 Michelangelo Giuliano and Fig 8 female with glasses each rendered in three styles (horizontal, crosshatch, cross_diagonal) — tone matches paper to 0.5 pp, but readers see the paper's feature-following Coons-warped lines on the middle panel vs our straight axis-aligned lines on the right, delta is the artistic warping (Fig 5 top row hand-drawn parametric grids + Fig 5 middle row range-shift / range-scale masks). Multi-layer styles use equilibrate=True in the triplets to hold tone fidelity across composition. Validation produces the machinery comparison _engrave_paper_fig4_straight_comparison.png (paper Fig 4 engravings vs ours, on the paper's own extracted sample image, with a comparable gentle flow bend), the photograph demo engrave_flow_demo_delphi.png (source
veryovka_screen	Paper Fig 3 bark texture (cropped from page 3 PDF extract); paper Fig 4 Lenna + Fig 5 eye (recovered via Gaussian-blur of the paper's published halftones — see source-recovery note in validation/paper_faithful_veryovka_screen.py); also validation/inputs/ostromoukhov1.png (butterfly) and validation/inputs/sudanese.png	Veryovka-Buchanan 1999 §3 image-as-dither-screen via CLAHE equalisation + §4 α-blended Floyd-Steinberg (Eq. 1) + §5 photorealistic / §6 artistic modes. Three paper-figure triplets (Source | Paper Reference | Ours): Fig 3 α/block-size sweep — synthesised black→white ramp dithered with the bark-texture screen, run at the five (α, error_block_size) the paper publishes (tone matches paper to <12 pp); Fig 4 Lenna (d) HE + (e) CLAHE — recovered Lenna source run in photorealistic mode at the paper's CLAHE settings (tone matches paper to 0.1 pp); Fig 5 eye artistic-mode — recovered eye run with bark (substituting for the paper's rocks texture, which isn't republishable) and a scanned-text texture cropped from the paper's own bottom-left Fig 5 panel. Validation produces _veryovka_paper_fig{3,4,5}_*_triplet.png (three Source | Paper | Ours strips per figure) in validation/output/veryovka_screen1/, alongside the earlier catalog-image sweeps (veryovka_alpha_sweep_<image>.png, veryovka_block_sweep_<image>.png, veryovka_artistic_*.png) which remain as algorithm-behaviour demonstrations.
jodoin	Procedurally-generated proxy stroke sets (parallel / crosshatch / sketch)	Jodoin 2002 §2.1 GENERATE_STROKES + GET_PLAUSIBLE_STROKES (paper-literal Gibbs threshold exp(-‖dst‖) > c, with Gibbs-weighted widening per Eq. 6 when no context passes the hard cutoff) + §2.2-§2.4 KL₂ statistical distance. §3.2 2D placement: synthesized strokes lay out along darkness-sampled drawing-path anchors, each path accumulating per-stroke (dx_step, dy_step) offsets. KL₂ values fall in the paper's reported 0.04-0.47 range across exemplar styles. The paper's Source | Reference | Ours triplet is not reachable: the paper's figures depend on Sébastien Roy's hand-drawn stroke sequences (Figs 5-7) and on the artist's interactive brush paths (Figs 8-9), neither of which is reproducible. The §2.1 N-gram synthesis is exercised on three proxy stroke distributions; the rendered Sudanese output shows the same image with three visibly different hatching styles. Validation produces jodoin_window_sweep.txt (Fig 5 N-sweep), jodoin_divergence.txt (Fig 6 long-sequence KL₂), jodoin_render_sudanese_<style>.png (per-exemplar image hatching), and jodoin_patch_midtone_<style>.png (constant-tone diagnostic) in validation/output/jodoin1/.
reaction_diffusion_woodcut	The lighthouse photograph that Mello-Jung-Walter 2007, Li-Xu 2016 and Mesquita-Walter 2019 all use as their common test image (cropped from the thesis page 20 Fig 3.2(a)); also validation/inputs/ostromoukhov1.png (butterfly) and validation/inputs/sudanese.png	Mesquita-Walter 2019 §3 reaction-diffusion pipeline (preprocessing: Witkin-Kass smoothed Sobel for per-pixel orientation θ; reaction-diffusion: paper §3.2 Turing system with anisotropic 3×3 kernels at paper defaults Da = 0.125, Db_h = 0.030, Db_v = 0.025; post-processing: 3×3 median + Otsu + paper §3.1.1 plain-region intensity gates). One paper-figure triplet (Source | Mesquita Fig 4.14(g) | Ours) on the lighthouse: tone matches paper to ~20 pp, both produce the same lighthouse silhouette with reaction-diffusion stripe patterns and same Turing pattern character — ours has finer pattern density because we run the segmentation-free pipeline (§3.1.5) where the thesis uses ADE20K segmentation. Validation produces _rd_paper_fig414g_default_triplet.png (Source | Paper | Ours), _rd_paper_fig414i_adaptive_triplet.png (paper's adaptive-orientation variant), and _rd_paper_fig414_mello_vs_mesquita.png (the two paper-published panels side-by-side for historical context) in validation/output/reaction_diffusion_woodcut1/. Numerical-discretisation note: the thesis presents two stencils — page 32 basic-isotropic (consistent with standard ∇·(D∇u) FD) and page 33 rotated-anisotropic (centre coefficient -4·(f11+f22), exactly 2× the page-32 form in the isotropic limit). The page-33 form applied as a standard convolution under explicit Euler at dt = 1 is at the stability edge and blows up around step ~500 with the bilinear reaction term (verified empirically: b → 10⁶ by step 500). Our kernel uses the page-32-consistent FD stencil for both isotropic and anisotropic cases — algorithmically equivalent at paper defaults, stable at dt = 1.

Sample outputs

artistic_screen — paper §2 spot-function path (procedural shapes) and §3 contour-based path (glyph rasterisation as a proxy for artist-drawn Bézier contour sets). The same input image rendered with four different screen elements; classical clustered-dot character on the left, microletter character with shape="text" on the right. The text panel uses cell_size=24 so the letters are readable on inspection — the same paper Fig 17 "the screen IS the artwork" device, made procedural via PIL's default bitmap font.

shape="circle" — classical clustered dot	shape="diamond" — L1-distance dot	shape="star" — 5-pointed star	shape="text" cell=24 — microletter (Fig 17 analog)

Per-intensity-level dot growth (paper Fig 9 analog), 16 levels per row — leftmost is darkest (fully inked), rightmost is lightest (empty). The growth profile is the visible signature that the algorithm reproduces the §2 / §3 "screen element shape evolution":

shape="circle"	shape="diamond"	shape="star"	shape="text"

Paper Fig 6 (Escher fish), Fig 11 (SIGGRAPH95 letters), Fig 14 (Kanji), and Fig 17 (microletter portrait) depend on artist-drawn Bézier contour sets that can't be redistributed — same proxy-honesty pattern as Jodoin's Z_t and Kim's tone map. With a user-supplied contour set fed into the same §3 contour-blending + rasterisation machinery, the catalog's algorithm would carry through to paper-style artistic screening.

ostromoukhov_engrave — paper §2.1 universal copperplate (triangle-wave threshold matrix) dithered against the input image, producing variable-width parallel ink lines (thin in highlights, thick in dark areas). Per-style on validation/inputs/ostromoukhov1.png (butterfly, n=216×216, frequency=0.15, equilibrate=False):

style="horizontal" — single horizontal layer (Fig 4a)	style="diagonal" — 45° layer	style="crosshatch" — H+V with smaller merge (Fig 4c)

Paper Fig 4 merge-mode diagnostic reproduces on the synthetic source (uniform gradient + 4 flat patches at 1/8, 3/8, 5/8, 7/8). equilibrate=True is used here so the per-patch tone fidelity is paper-exact (≤ 1% per-panel error):

The equilibrate trade-off (paper §2.3 is iterative + printer-aware; our one-shot CDF flattening is a digital-output approximation): default equilibrate=False keeps the engraving's variable-width-line character on natural images (line-centre threshold-zero pixels stay always inked). Opt-in equilibrate=True gives strict uniform-input-uniform-output tone reproduction at the cost of line structure — the right choice for diagnostic figures, the wrong choice for image hatching.

The paper's result engravings (Figs 6–9) are artist work, not algorithm output — §3.2: the engraving styles were "adjusted to the photos manually", with automatic adjustment listed only as future work. They are the artist's artwork, so they aren't embedded here (full-image triplets against them live in validation/output/ostromoukhov_engrave1/ as gap exhibits). The fair comparison targets are the paper's machinery figures, Fig 4 and Fig 3(b):

Engraving lines — paper Fig 4. Fig 4 dithers the paper's own synthetic sample image (gradient strip + step patches) through merge-mode layer compositions; its layers are mildly Coons-warped, so the published lines curve gently. We extract the sample panel itself and engrave it at matching angles and frequency, with a comparable gentle bend applied through the flow machinery (the same low-order synthetic guide, ±0.8 line periods). Top row paper, bottom row ours — copy L1 (left) and the L1 smaller L2 cross-etching (right). Ink fractions match (49.9 % vs 50.0 % single layer; 66.7 % vs 66.9 % raw smaller merge — Fig 4 demonstrates the merges before §2.3 equilibration, so both over-ink identically). The paper's "Transformed Layers" column is omitted: it is printed at a different zoom and angle than its own "Resulting Engravings" column, so the engravings are the coordinate-matched target:

Bent curves — the flow warp on a photograph. The paper bends its layers through hand-drawn Coons patches (a coordinate remap); flow_strength is the automatic counterpart — a scalar displacement of each line's transverse phase, driven by the image itself. The guide is the Gaussian-smoothed, zero-mean, contrast-normalized image, so the bend follows the picture's relief regardless of its brightness range, and the smoothing scale auto-grows with the displacement amplitude so lines tilt around forms instead of melting across hard edges (flow_sigma overrides the scale manually). Source | straight | flow_strength=1.0, same horizontal layer:

What remains visibly artist-bound after the flow warp: the paper's per-region layer scoping — per-layer hand-drawn border curves and per-pixel hand-painted Photoshop range-shift / range-scale masks (Fig 5 middle row) give hair, face, and background each their own line direction and cross-etching. That's artist work that can't be redistributed — paper-faithfulness gap acknowledged the same way as for Jodoin (the artist Z_t) and Kim (the artist tone map). With user-supplied Coons curves and mask images fed into the same §2.2 merging machinery, the catalog would carry through to paper-style facial engravings.

veryovka_screen — paper §3 image-based dither screen (CLAHE-equalised input → dither threshold matrix) + §4 α-blended Floyd-Steinberg. The α parameter blends ordered dither (texture from the screen, α=0) and Floyd-Steinberg (exact tone, α=1). At intermediate α the texture preservation and tone accuracy combine — paper §5 / Fig 4 visual character. Photorealistic mode (default, GUI-accessible) uses the input image itself as the screen source so dot clusters align with image features.

Paper Fig 3 triplet at α=0.5, error block size 1 — left is the synthesised black→white ramp source, middle is the paper's Fig 3 panel, right is ours at the same settings with the bark-texture screen. The texture carried in by the screen is visible in both halftones while tone tracks the ramp — the §4 α-blend working as published. (The Fig 4 Lenna and Fig 5 eye triplets live in validation/output/veryovka_screen1/.)

α sweep on validation/inputs/ostromoukhov1.png (butterfly) — α=0 (pure ordered dither, texture from CLAHE-screen) → α=1 (pure FS, exact tone):

jodoin — example-based hatching on procedural proxy stroke sets. The three exemplar_style options demonstrate that the same N-gram synthesis pipeline can carry a wide range of stroke styles into the output. Each style is a 50-stroke proxy Z_t that mirrors one of the three character regimes Jodoin's hand-drawn training sets cover (Fig 5 parallel hatching, Fig 7 bigram-correlated alternation, Fig 9 sketch). Per-style on the Sudanese surface image (n=3000 strokes, default window_size=6, distance_threshold=0.4, strokes_per_path=20):

exemplar_style="parallel" — single-direction runs	exemplar_style="crosshatch" — ±45° alternation (chevron pattern)	exemplar_style="sketch" — wide angle/length variation

The crosshatch render shows the §2.1 N-gram synthesis preserving the bigram structure of the training set: every other stroke flips angle, so the synthesized sequence draws as a chevron / zigzag pattern. This is the paper's core demonstration — the same algorithmic pipeline carries whatever bigram structure exists in Z_t into the output. With a hand-drawn artist Z_t (paper §3.2 Fig 9 uses four different artist training sets across four images), the artist's stroke-by-stroke variations would carry through similarly.

Stroke parametrisation is 4-D (dx_step, dy_step, dx_end, dy_end) — all in pixels, uniform scale — so paper §2.1's literal Gibbs threshold exp(-‖dst‖) > c works without standardisation. Strokes are laid out along drawing paths (paper §3.2): each path is one continuous run of strokes_per_path synthesized strokes, accumulating (dx_step, dy_step) offsets from a darkness-sampled anchor.

Paper §6 explicitly notes: "We do not control the tone of the strokes." Tone modulation is the artist's job in the paper (by how they draw the input paths). For image-input the catalog substitutes darkness-weighted path-anchor sampling — what we sacrifice is the artist's tone control, what we gain is automation.

reaction_diffusion_woodcut — Mesquita-Walter 2019's Turing-system pipeline. The input drives a per-pixel parameter map (orientation θ, reaction-speed S, stripes-vs-spots δ), and the RD simulation evolves morphogen concentrations whose patterns follow the parameter map's local structure.

Paper Fig 4.14(g) lighthouse triplet — left is the original lighthouse from page 20 of the thesis (the same image Mello-Jung-Walter 2007 and Li-Xu 2016 use as the cross-method benchmark), middle is Mesquita's published RD-woodcut result with paper-default parameters, right is ours at the same parameters (dah=0.125, dbh=0.040, dbv=0.020, n_iter=3000, invert=True). Both show the lighthouse silhouette with reaction-diffusion stripe patterns wrapping around the contours; ours has slightly finer pattern density (we run the segmentation-free §3.1.5 path, the thesis uses ADE20K segmentation):

References

Each algorithm in the catalog implements the work cited below.

Edges / line drawings

1. Marr, D. & Hildreth, E. (1980). Theory of edge detection. Proceedings of the Royal Society of London. Series B, Biological Sciences, 207(1167), 187–217. — implemented as log_zero.
2. Canny, J. (1986). A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-8(6), 679–698. — implemented as canny.
3. Lorensen, W. E. & Cline, H. E. (1987). Marching cubes: A high resolution 3D surface construction algorithm. ACM SIGGRAPH Computer Graphics, 21(4), 163–169. — 2D restriction implemented as iso_contours (marching squares).
4. Kang, H., Lee, S. & Chui, C. K. (2007). Coherent line drawing. Proc. International Symposium on Non-Photorealistic Animation and Rendering (NPAR), 43–50. — implemented as fdog.
5. Winnemöller, H., Kyprianidis, J. E. & Olsen, S. C. (2012). XDoG: An eXtended difference-of-Gaussians compendium including advanced image stylization. Computers & Graphics, 36(6), 740–753. — implemented as xdog.

Visible dots (AM)

6. Limb, J. O. (1969). Design of dither waveforms for quantized visual signals. Bell System Technical Journal, 48(7), 2555–2582. — implemented as limb_dither.
7. Bayer, B. E. (1973). An optimum method for two-level rendition of continuous-tone pictures. Proc. IEEE International Conference on Communications, 26-11–26-15. — clustered-dot half of the paper implemented as clustered_dot; its §IV tone-conservation invariant anchors am_screen's validation.
8. Holladay, T. M. (1980). An optimum algorithm for halftone generation for displays and hard copies. Proceedings of the SID, 21(2), 185–192. (Content-equivalent to US Patent 4,185,304.) — informs both am_screen (variable-radius dot screen) and clustered_dot (spiral threshold matrix).
9. Velho, L. & Gomes, J. de M. (1991). Digital halftoning with space filling curves. ACM SIGGRAPH Computer Graphics (Proc. SIGGRAPH '91), 25(4), 81–90. — implemented as velho_gomes.

Invisible dots (FM ordered)

10. Ulichney, R. A. (1993). The void-and-cluster method for dither array generation. Proc. SPIE 1913, Human Vision, Visual Processing, and Digital Display IV, 332–343. — implemented as void_cluster.

Invisible dots (FM error-diffused)

11. Floyd, R. W. & Steinberg, L. (1976). An adaptive algorithm for spatial greyscale. Proceedings of the Society for Information Display, 17(2), 75–77. — implemented as floyd_steinberg.
12. The seven classical post-Floyd-Steinberg error-diffusion kernels, all sharing a single implementation under classical_ed (kernel choice selects one): Jarvis, J. F., Judice, C. N. & Ninke, W. H. (1976). A survey of techniques for the display of continuous tone pictures on bilevel displays. Computer Graphics and Image Processing, 5(1), 13–40 (12-coefficient kernel, /48); Stucki, P. (1981). MECCA — A multiple-error correcting computation algorithm for bilevel image hardcopy reproduction. IBM Research Report RZ1060 (12-coefficient kernel, /42, smoother midtones than Jarvis on photos); Burkes, D. (1988). Presentation of the Burkes error filter for use in preparing continuous-tone images for presentation on bi-level devices. Unpublished memo, widely cited (7-coefficient two-row kernel, /32); Sierra, F. (1989). Three error-diffusion variants — full (10-coefficient, /32), two-row (7-coefficient, /16), and lite (3-coefficient, /4) — published in LIB17.ARJ on CompuServe; Atkinson, B. (1988). Six-coefficient kernel (all weights 1/8) used in HyperCard and early MacPaint — diffuses only 75 % of the quantisation error, giving the characteristic high-contrast HyperCard look. None of these is a peer-reviewed publication with a reproducible figure; the sanity check is tone preservation on a synthesised ramp + visual cross-comparison on a standard test image (here validation/inputs/floyd_steinberg1.png).
13. Knuth, D. E. (1987). Digital halftones by dot diffusion. ACM Transactions on Graphics, 6(4), 245–273. — implemented as dot_diffusion.
14. Riemersma, T. (1998). A balanced dithering technique. C/C++ Users Journal, 16(12). — implemented as riemersma.
15. Ostromoukhov, V. (2001). A simple and efficient error-diffusion algorithm. Proc. SIGGRAPH 2001, 567–572. — implemented as ostromoukhov.
16. Pang, W.-M., Qu, Y., Wong, T.-T., Cohen-Or, D. & Heng, P.-A. (2008). Structure-aware halftoning. ACM Transactions on Graphics (Proc. SIGGRAPH 2008), 27(3), Article 89. — implemented as structure_aware.
17. Chang, J., Alain, B. & Ostromoukhov, V. (2009). Structure-aware error diffusion. ACM Transactions on Graphics (Proc. SIGGRAPH Asia 2009), 28(5), Article 162. — implemented as chang_edr (paper-faithful §3 architecture; calibration heuristic — the paper's ~1.3 MB observer-tuned LUT is unpublished).
18. Li, H. & Mould, D. (2010). Contrast-aware halftoning. Computer Graphics Forum (Proc. Eurographics), 29(2), 273–280. — implemented as li_mould.
19. Kimoto, T. (2013). Multi-level halftoning by IGS quantization. Journal of Signal and Information Processing, 4(4), 351–358. — implemented as kimoto_igs.
20. Shi, X. & Li, X. (2014). An improved error diffusion algorithm based on Laplacian transform and adaptive median filter. HCII 2014 Posters, CCIS 434, 540–545. — implemented as shi_li.

Off-grid stipple — Voronoi / Lloyd

21. Deussen, O., Hiller, S., van Overveld, K. & Strothotte, T. (2000). Floating points: A method for computing stipple drawings. Computer Graphics Forum, 19(3), 41–50. — implemented as deussen.
22. Secord, A. (2002). Weighted Voronoi stippling. Proc. International Symposium on Non-Photorealistic Animation and Rendering (NPAR), 37–43. — implemented as secord.
23. Balzer, M., Schlömer, T. & Deussen, O. (2009). Capacity-constrained point distributions: A variant of Lloyd's method. ACM Transactions on Graphics (Proc. SIGGRAPH 2009), 28(3), Article 86. — implemented as both balzer (strict pairwise-swap CCVT) and balzer_lloyd (CCVT approximation).

Off-grid stipple — Optimal transport

24. de Goes, F., Breeden, K., Ostromoukhov, V. & Desbrun, M. (2012). Blue noise through optimal transport. ACM Transactions on Graphics (Proc. SIGGRAPH Asia 2012), 31(6), Article 171. — implemented as degoes.
25. Nader, G. & Guennebaud, G. (2018). Instant transport maps on 2D grids. ACM Transactions on Graphics (Proc. SIGGRAPH Asia 2018), 37(6), Article 249. — implemented as nader.
26. Paulin, L., Bonneel, N., Coeurjolly, D., Iehl, J.-C., Webanck, A., Desbrun, M. & Ostromoukhov, V. (2020). Sliced optimal transport sampling. ACM Transactions on Graphics (Proc. SIGGRAPH 2020), 39(4), Article 99. — implemented as sot.

Off-grid stipple — Other

27. Kim, S.-Y., Maciejewski, R., Isenberg, T., Andrews, W. M., Chen, W., Sousa, M. C. & Ebert, D. S. (2009). Stippling by example. Proc. International Symposium on Non-Photorealistic Animation and Rendering (NPAR), 41–50. — implemented as kim (algorithm-faithful core; proxy exemplars in place of the artist's hand-drawn tone map — see "Off-grid stipple — Other" section above for the limitation).
28. Schmaltz, C., Gwosdek, P., Bruhn, A. & Weickert, J. (2010). Electrostatic halftoning. Computer Graphics Forum, 29(8), 2313–2327. — implemented as schmaltz.
29. Ahmed, A. G. M. & Ren, P. (2022). Gaussian blue noise. ACM Transactions on Graphics (Proc. SIGGRAPH Asia 2022), 41(6), Article 260. — implemented as ahmed.

Tone-following hatching

30. Ostromoukhov, V. & Hersch, R. D. (1995). Artistic screening. Proc. SIGGRAPH 1995, 219–228. — implemented as artistic_screen (algorithm-faithful §2 spot-function path with procedural circle/diamond/star shapes; §3 contour-based path proxied by PIL glyph rasterisation in place of the artist's hand-drawn Bézier contour sets — see "Tone-following hatching" section above for the limitation).
31. Ostromoukhov, V. (1999). Digital facial engraving. Proc. SIGGRAPH 1999, 417–424. — implemented as ostromoukhov_engrave (algorithm-faithful §2.1 universal copperplate + §2.2 five merge modes + §2.3 CDF-flattening equilibration; uniform parametric grid + scalar per-layer S, D in place of the artist's hand-drawn Coons patches and per-layer Photoshop masks — see "Tone-following hatching" section above for the limitation).
32. Veryovka, O. & Buchanan, J. W. (1999). Halftoning with image-based dither screens. Proc. Graphics Interface, 167–174. — implemented as veryovka_screen (algorithm-faithful §3 CLAHE-based screen construction via skimage.exposure.equalize_adapthist, §4 α-blended Floyd-Steinberg per Eq. 1, §5 photorealistic mode, §6 artistic mode via Python API).
33. Jodoin, P.-M., Epstein, E., Granger-Piché, M. & Ostromoukhov, V. (2002). Hatching by example: A statistical approach. Proc. International Symposium on Non-Photorealistic Animation and Rendering (NPAR), 29–36. — implemented as jodoin (algorithm-faithful §2.1 N-gram + §2.2-§2.4 KL₂; proxy stroke sets in place of the artist's hand-drawn training sequence — see "Tone-following hatching" section above for the limitation).
34. Mesquita, D. P. & Walter, M. (2019). Reaction-Diffusion Woodcuts. UFRGS Master's thesis (advisor M. Walter), Porto Alegre. CC BY-NC-SA 2.5 BR, lume.ufrgs.br/handle/10183/194383. — implemented as reaction_diffusion_woodcut (algorithm-faithful §3 four-stage RD pipeline; Witkin-Kass anisotropic kernel in standard ∇·(D∇u) finite-difference form for explicit-Euler stability at paper-default D; segmentation-free preprocessing per §3.1.5 in place of the user-supplied segmentation the thesis prefers — see "Tone-following hatching" section above for the limitation). The Mello-Jung-Walter 2007 GRAPHITE paper originally targeted is paywalled; Mesquita 2019 covers the same Walter research line on virtual woodcuts, with full algorithmic detail in an open-access form.

Background references (not directly implemented). These predate the algorithms in the catalog and inform their design; the citations are anchored here so the genealogy is visible.

• Goodall, W. M. (1951). Television by pulse code modulation. Bell System Technical Journal, 30(1), 33–49. — earliest dither work; cited by Limb 1969 as reference 2.
• Roberts, L. G. (1962). Picture coding using pseudo-random noise. IRE Transactions on Information Theory, 8(2), 145–154. — the random-uniform dither baseline Limb 1969 extends (Roberts' 1961 MIT MS thesis "PCM television bandwidth reduction using pseudo-random noise" is the open-access predecessor).

GUI (monochromizer)

PySide6. Layer panel on the left, preview on the right. The layer panel stacks vertically and the splitter auto-sizes to fit one fully-populated layer.

• Algorithm dropdown — single combo over the whole catalog, grouped by visual outcome (Edges / AM dots / FM ordered / FM error-diffused / Off-grid stipple sub-families / Tone-following hatching). Group headers are disabled (un-selectable) rows. There is no vector-vs-raster filter: every algorithm exports to both PNG and SVG.
• Param form — auto-built from the algorithm's parameter list. Widget kind by name: int, float, bool, choice.
• Preview mode toggle (top toolbar) — PNG (raster) / SVG (vector). Re-uses cached LayerOutput so switching is instant.
• Preview zoom — mouse wheel zooms in/out anchored under the cursor; while zoomed, drag pans. Double-click (or a new render) returns to fit-to-window.
• Source image preview appears immediately on Load so you can see the input before rendering.
• Save PNG writes the 1-bit mask via compositor.write_png. Save SVG writes vector primitives via compositor.render_svg (mask layers traced to pixel-exact even-odd paths).

Installation

python3 -m venv .venv          # Python ≥ 3.11
source .venv/bin/activate
pip install -e ".[dev]"

scikit-sparse (CHOLMOD, used by the Nader-Guennebaud OT stippler) needs the SuiteSparse system library at build time: brew install suite-sparse on macOS, apt install libsuitesparse-dev on Debian/Ubuntu.

Tests

pytest

A comprehensive suite, all green. Every algorithm runs under a parametrised smoke + bounds suite; on top of that there is a curated 17-algorithm byte-exact golden set across the three non-contour families, a same-seed determinism sweep over the rest, and an adversarial seed-sensitivity test. The contour, hatching, and halftone families carry targeted per-algorithm correctness tests (edge geometry, serpentine scan order, dot counts, tone monotonicity). The GUI layer has Qt smoke tests via pytest-qt running headlessly under QT_QPA_PLATFORM=offscreen.

Validation harness

validation/validate.py runs every algorithm on every image in validation/inputs/ with hand-picked parameter variants, writes 1-bit PNG (and optionally SVG) to validation/output/<image_stem>/<algo>__<param_sig>.png, and prints per-output timing. Sweep outputs are disposable; the paper-reference panels embedded in this README are copied into docs/images/ by docs/collect_images.py (manifest: docs/image_sources.txt). The figure panels extracted from the source papers — the inputs and references the paper-faithfulness scripts compare against — are committed in docs/extracted/, so every comparison re-runs from a fresh clone; only re-extraction (rebuilding a missing panel from its PDF) needs the papers themselves.

python validation/validate.py                    # full sweep
python validation/validate.py --skip-existing    # incremental
python validation/validate.py --image sudanese.png --write-svg
python validation/validate.py --algo void_cluster --vector-only

Per-image scaling: n (stipple count) is multiplied by image-area ratio relative to the reference image (sudanese.png, ~180k px), capped per-algorithm — 30 000 for the vectorised Voronoi/OT stipplers (secord, degoes), 10 000 for the slower sot and nader, 5 000 for the unvectorised balzer*/schmaltz/ahmed (O(N²) or per-site Python loops). Length-scaled values (radius, matrix_size, cluster_size) are scaled by the square root of the area ratio, capped at 6×. Stipple radius additionally gets a coverage-preserving and image-darkness-aware override so dark images reach the same local ink density as the (mostly-bright) sudanese reference. The systematic harness is intentionally separate from the per-algorithm paper-faithfulness validation runs (see "Paper-faithfulness validation" tables above), which use absolute paper-faithful parameters and bypass the harness's scaling rules.

Pipeline

image
  ↓ image.load_grayscale
2-D float array in [0, 1]
  ↓ Layer.params  (per layer in the stack)
  ↓ {contour,halftone,stipple,hatching}.dispatch.run
  ↓ dispatch.run_layer  (applies Layer.mask_bleed → keepout)
list of LayerOutput  (mask / dots / strokes / polygons / keepout)
  ↓ compositor
PNG (1-bit raster) or SVG (one <g> per layer with vector primitives)

Project structure

src/monochromizer/
  image.py          load_grayscale + density (shared front-end)
  layer.py          Layer + LayerOutput dataclasses
  compositor.py     render_png_array / render_svg / write_png; PIL-batch raster
  mask_trace.py     pixel-exact boundary tracing: bool mask → even-odd SVG path loops
  dispatch.py       top-level family union (UNIFIED_ALGORITHMS) + run_layer / run_stack
  _rng.py           shared seed → Generator helper used by the family dispatchers
  contour/
    canny.py        Canny edges → polylines
    xdog.py         Winnemöller 2012 XDoG → tonal-stylization mask
    fdog.py         Kang 2007 flow-based DoG → bold line mask (faithful ETF + LIC)
    iso_contours.py marching-squares level sets → polylines
    log_zero.py     Marr-Hildreth zero-crossings → polylines
    _vectorize.py   bool mask → ordered polylines (skeletonise + 8-conn walk)
    dispatch.py
  halftone/         vendored from the halftoning research collection + vector-output extensions
  stipple/          vendored from the stippling research collection
  hatching/         tone-following hatching family (engraving, artistic screens, RD woodcuts, …)
  app.py            PySide6 composable GUI
tests/              red-green per module + GUI smoke + end-to-end
validation/
  inputs/                input images. sudanese.png is the small reference; the
                         author-named files (canny{1,2,3}, marr{1,2,3}, kang{1,2,3},
                         winnemoeller{1,2,3}, velho1, ulichney1, floyd_steinberg1,
                         knuth1, ostromoukhov1, pang1, secord{1,2,3}, balzer1,
                         degoes1, schmaltz{1,2}, ahmed{1,2}, …) reproduce each
                         source paper's own test images, for paper-faithfulness
                         validation.
  paper_faithful_*.py    per-paper figure reproductions (Source | Reference | Ours),
                         one per algorithm that has a published figure to match
  blue_noise_spectrum.py uniform-density blue-noise QA harness for the stipplers
  validate.py            systematic algorithm × image × param sweep
  _extracted.py          cached paper-figure panel loader (shared by the scripts)
  output/                diagnostic artifacts (regenerable)
docs/
  images/           publication image set — every panel embedded in this README,
                    synced from its sources by collect_images.py
                    (manifest: image_sources.txt)
  extracted/        paper-figure panels (sources + references) used by the
                    paper-faithfulness scripts — committed so comparisons
                    re-run without the source PDFs

License

Free for personal, academic, and research use. No warranty. No commercial use.