ESDT-based WCAG contrast computation research implementation in Futhark targeting WebGPU.

Research Paper (PDF) -- Mathematical foundations with verification status.

Pixelwise originally used precomputed WGSL shaders for GPU contrast computation with Futhark WASM multicore as the reference implementation. I am now working toward a unified Futhark WebGPU backend that generates both GPU (WebGPU/WGSL) and CPU (WASM multicore) code from a single source.

Foundation: Sebastian Paarmann's MSc Thesis (2024) introduced the Futhark WebGPU backend as part of his research at DIKU.

Current Status: Experimental fork at jesssullivan/futhark (branch development-webgpu) with Emscripten 4.x compatibility patches.

Classical distance transforms store d^2 (squared distance to nearest edge) for each pixel. This is efficient but loses information: you know how far but not which direction.

For WCAG contrast enhancement, we need to sample background colors outward from text. With only d^2, you need a separate gradient computation pass (Sobel filter, finite differences).

Instead of storing d^2 = dx^2 + dy^2, ESDT stores the offset vector (dx, dy) directly.

What you get for free:

• Distance: d = sqrt(dx^2 + dy^2) -- same as before
• Gradient direction: (dx, dy) / d -- the direction to the nearest edge
• Background sampling: Follow the gradient outward to find background pixels

This eliminates one pipeline pass and provides mathematically correct gradients.

Anti-aliased fonts produce "gray pixels" at edges where opacity L in (0, 1) encodes sub-pixel edge position. A common mistake is to add the gray offset as:

d^2 = x^2 + y^2 + (L - 0.5)^2    // WRONG: This is 3D distance!

This treats opacity as a third spatial dimension. Instead, ESDT applies the offset along the 2D gradient direction during initialization:

offset = L - 0.5
(dx, dy) = (offset * gx, offset * gy)  // where (gx, gy) is normalized gradient

This maintains correct 2D geometry.

Traditional EDT (scalar d^2):          ESDT (offset vectors):
+---------------------+               +---------------------------------+
| 9  4  1  0  1  4  9 |               | (-3,0) (-2,0) (-1,0) (0,0) ... |
| 4  1  0  0  0  1  4 |  Only         | (-2,0) (-1,0)  (0,0) (0,0) ... |  Distance
| 1  0  0  0  0  0  1 |  distances    | (-1,0)  (0,0)  (0,0) (0,0) ... |  AND direction
+---------------------+               +---------------------------------+
     v Need Sobel pass                      v Gradient = normalize(dx,dy)
     for gradient                           (no extra pass needed)

ESDT computes offset vectors (dx, dy) to the nearest edge for each pixel.

Distance:

d = sqrt(dx^2 + dy^2)

Gradient (direction to nearest edge):

grad(d) = (dx, dy) / d    when d > epsilon

Gray pixel initialization (Definition 2.3 in paper):

offset = L - 0.5

Where L in (0, 1) is pixel opacity. The offset is applied in the Sobel gradient direction.

sRGB Linearization:

C_lin = C / 12.92                        if C <= 0.03928
C_lin = ((C + 0.055) / 1.055)^2.4        otherwise

Relative Luminance:

L = 0.2126 * R_lin + 0.7152 * G_lin + 0.0722 * B_lin

Contrast Ratio:

CR = (L_lighter + 0.05) / (L_darker + 0.05)

Bounds: CR in [1, 21]. Black/white yields CR ~ 21.

w = 4 * alpha * (1 - alpha)

Where alpha = clamp(1 - d/d_max, 0, 1). Peaks at alpha = 0.5 (glyph boundaries).

1. Futhark WebGPU (GPU)   -> Fastest, requires GPU adapter + WebGPU browser
2. Futhark WASM (CPU)     -> Multicore, requires COOP/COEP headers
3. JavaScript Fallback    -> Single-threaded, always works

Both GPU and CPU backends are generated from a single Futhark source (futhark/pipeline.fut), ensuring algorithmic equivalence.

Pass 1: Grayscale -> Sobel gradient computation
Pass 2: ESDT X-pass (horizontal propagation, O(w) per row)
Pass 3: ESDT Y-pass (vertical propagation, O(h) per column)
Pass 4: Glyph extraction (distance < threshold)
Pass 5: Background sampling (outward along grad(d))
Pass 6: WCAG contrast check + luminance adjustment

When WebGPU is available, a 6-pass GPU compute pipeline is used:

nix develop          # Enter environment (includes Futhark, Emscripten, Node 22)
pnpm install         # Install dependencies
just dev             # Start server at localhost:5175 (with COOP/COEP headers)

Tests in tests/theorem-verification/ verify:

• Linearization threshold 0.03928 (not 0.04045)
• Gamma exponent 2.4 (not 2.5)
• CR bounds [1, 21]
• Edge weight peak at alpha = 0.5
• Offset vector distance/gradient derivation

Run: pnpm test tests/theorem-verification/

Futhark's WASM multicore backend uses SharedArrayBuffer for parallel execution. Browsers require Cross-Origin Isolation headers:

Cross-Origin-Opener-Policy: same-origin
Cross-Origin-Embedder-Policy: credentialless

These are configured in vite.config.ts (dev), src/hooks.server.ts (production), and nginx ingress annotations (Kubernetes).

Mathematical foundations with verification status in tex source; not finalized.

Originally developed with Rust SIMD as a project to learn Rust SIMD; this project received autonomous assistance with PBT constraining, fuzzing, verification and function composition as well as some GPU integration work performed within Tinyland with the xoxd.ai stack.

zlib

Jess Sullivan [email protected]

@software{pixelwise2026,
  author = {Sullivan, Jess},
  title = {Pixelwise: ESDT-Based WCAG Contrast Enhancement},
  year = {2026},
  url = {https://github.com/Jesssullivan/pixelwise-research}
}

References:

• Danielsson, P.E. (1980). Euclidean Distance Mapping. CGIP 14(3):227-248.
• Meijster, A. et al. (2000). A General Algorithm for Computing Distance Transforms in Linear Time.
• Wittens, S. (2023). Subpixel Distance Transform. https://acko.net/blog/subpixel-distance-transform/
• Henriksen, T. et al. (2017). Futhark: Purely Functional GPU-Programming. PLDI '17.
• Paarmann, S. (2024). A WebGPU Backend for Futhark. MSc Thesis, DIKU.