Void-and-Cluster Method

DEFINITION

F = P ⊛ Gσ   (toroidal)
cluster = argmax_{i: P(i)=1} F(i)
void   = argmin_{i: P(i)=0} F(i)
P(cluster)←0, P(void)←1; repeat until void = cluster

NOTES

Every other dither plate in this order starts from a rule and applies it: Bayer consults a fixed matrix, Floyd and Steinberg carry a rounding error forward through a scan. Ulichney asked how a good matrix could be grown instead of designed. Scatter a chosen minority of cells at random across a lattice, blur the whole pattern with a small Gaussian that wraps at the edges, and read off two numbers: the blurred value at the busiest on cell, the tightest cluster, and the blurred value at the emptiest off cell, the largest void. Turn the cluster cell off and the void cell on, and ask again. Every swap thins a crowd somewhere and fills a gap somewhere else, and the process carries its own stopping rule rather than a step count: remove the tightest cluster, then check where the largest void has landed. If it lands back on the very cell just vacated, putting it back is already the best move available, and the pattern has nothing left to improve. What this plate draws is that sequence of swaps, a few running every frame, not a matrix computed once and displayed whole. The full method repeats this same operator across every population size to rank every cell of the lattice into a finished threshold array; what is shown here is the operator itself, balancing one fixed minority fraction until it reaches its own equilibrium, then scattering again to do it from a new start. The faint field underneath the points is the filter itself — brighter where the next cluster is waiting to be found.

PROVENANCE

Origin

R. A. Ulichney, "Void-and-cluster method for dither array generation", Proceedings of SPIE 1913 (Human Vision, Visual Processing, and Digital Display IV), 1993, pp. 332-343

Standing

Public domain — an iterative swap rule and its stopping criterion, implemented here from the description of the operator in the paper itself, not from any existing dither-array table, reference implementation or precomputed matrix

What is shown, and what is not

The method Ulichney described repeats this swap rule three more times to rank every cell of a lattice into one finished threshold array: a first pass strips the tightest cluster from the pattern balanced here, cell by cell, to rank the minority; two more passes rank the majority by the mirrored rule. This plate stops at the first stage — one minority fraction, balanced by void-and-cluster, held on screen, then scattered again from a new random start. That stage is the whole of what the ranking passes are built from, and it is also the part of the method with a life cycle worth watching — the ranking that follows is bookkeeping over the same operator, a decision made once here and worth stating rather than leaving implicit

Measured, not just plotted

The swap rule claims to reduce clumping without being told where the clumps are, so that claim was checked directly: dividing the lattice into an 8x8 grid of blocks and comparing the variance of on-cell counts per block between the random start and the balanced result, the variance falls by five to ten times over, at every lattice size checked and every seed tried — the rule is doing what the paper says, not merely settling on something. Separately, 432 tuples spanning cells at 40 to 80, frac at 0.08 to 0.45 and sigma at 0.7 to 2.2, three seeds each, all reached a balanced pattern rather than cycling; the swap count needed deepens with the lattice area, from a mean of 147 at 48 cells to 410 at 80

Constants

cells is locked from regenerate — see taxonomy.js for the measured reasoning. frac and sigma are free: every value in their declared box converges, checked both as a full grid (108 of 108 at four lattice sizes) and as random pairs jittered together the way regenerate actually moves constants (40 of 40). sigma sets the kernel radius at three standard deviations, past which a Gaussian is under half a percent of its own peak; frac stays below one half so minority never crosses into majority

Source

doi:10.1117/12.152707