Fixed points and iterative algorithms

Some image operations are defined by repeated propagation until another update changes nothing. Others are defined by a chosen number of updates or by a numerical tolerance on a fitted model. Those stopping rules express different algorithms and need different execution contracts.

What a fixed point means

For an image update \(u^{k+1}=F(u^k;f)\) with fixed input \(f\), a fixed point satisfies \(F(u^*;f)=u^*\). The number of updates can depend on the image contents and the length of connected paths. It is not generally a parameter that can be inferred from a small block’s size.

Morphological reconstruction is a useful example. In reconstruction by dilation, a seed \(g\) lies below a mask \(f\), and each update is \(g^{k+1}=\min(\operatorname{dilate}(g^k),f)\). The mask caps propagation while dilation spreads permitted values. Along a one-voxel-wide corridor, a radius-one update moves information approximately one graph step per pass. A corridor crossing ten blocks can require information from the first block to reach the last, even though every individual update is local.

Running each tile to convergence in isolation gives a different answer: tile edges become artificial barriers. Supplying a fixed small raw-image halo and converging the tile still cannot account for an arbitrarily long connecting path outside that halo. Correct alternatives include exchanging state between local updates or using a global algorithm that explicitly resolves connectivity.

Propagation across a seam

Take a nine-pixel line with an all-one mask and a marker only at the left end. Use an update that takes the maximum of each pixel and its immediate neighbors, then caps it by the mask:

Mask:      1 1 1 1 | 1 1 1 1 1
Seed u0:   1 0 0 0 | 0 0 0 0 0
After 1:   1 1 0 0 | 0 0 0 0 0
After 2:   1 1 1 0 | 0 0 0 0 0
After 3:   1 1 1 1 | 0 0 0 0 0
After 4:   1 1 1 1 | 1 0 0 0 0
After 8:   1 1 1 1 | 1 1 1 1 1
After 9:   1 1 1 1 | 1 1 1 1 1  (unchanged)

The vertical bar is a compute seam, not a boundary in the mask. With one-pass neighbor exchange, the value crosses it after the fourth update. If the right block instead converges using only its original marker pixels, it remains all zero. Giving it a two-pixel halo of the original marker still misses the seed farther to the left. Increasing a fixed halo postpones this counterexample; it does not remove it for arbitrary path lengths. This example uses a general reconstruction marker; the h-extrema wrapper derives its own marker from the mask rather than accepting this marker as a separate input.

The unchanged ninth update is evidence of convergence, while stopping after eight updates alone is only a chosen budget. Those happen to give equal images on this fixture; the same budget fails on a longer corridor.

Which current operations use the generic fixed-point route?

HExtremaOp implements planned h-maxima/h-minima reconstruction. It derives a seed from the fixed mask, then performs geodesic dilation or its erosion dual. Reconstruction names the dual rules. The public resident reconstruct_to_fixed_point kernel also exposes the underlying reconstruction operation for caller-supplied arrays.

ConfigurationFixedPointOp repeatedly applies a caller-supplied neighborhood ConfigurationTable until the mask stops changing. ConfigurationPassOp performs one pass instead. A table can oscillate—for example, one that flips all states on every application—so the fixed-point route cannot assume every valid table converges.

These are the production implementations of IterativeOp in the current source. Binary hole filling and connected-component seam resolution have their own fragment/global algorithms; a conceptual relationship to propagation does not mean that their implementations use this executor. Nonlinear diffusion, TV denoising and RL reconstruction also involve loops, but their public routes and stopping rules must be inspected separately.

flowchart TB
  A["Running state k and fixed operands"] --> B["Read per-block neighborhoods"]
  B --> C["Update disjoint owned cores into next state"]
  C --> D["Finish all blocks and compare changes"]
  D --> E{"Anything changed?"}
  E -- yes --> F["Swap current and next state"]
  F --> A
  E -- no --> G["Publish fixed-point image"]
Figure 1: Every substage reads one consistent current state; only after all owned cores are written does the next state become visible.

Operands and one-substage reach

IterativeOp::operands returns SubstageOperand declarations. Operand::Running is the evolving image, Operand::Fixed is the original phase input, and Operand::Source names another stored image. Each declaration includes the neighborhood required by one substage. Substage exposes those operands and the substage index to the implementation.

For HExtremaOp, the running image needs the structuring element’s reach while the mask is read pointwise. The first substage derives the seed from that mask. For ConfigurationFixedPointOp, the sole operand is the running mask with one-voxel reach in each axis. An operand not used by the algorithm should not be declared: it would add a repeated read and working buffer.

The phase’s external reach is the maximum per-substage operand reach. It does not grow with the number of passes because each pass reads the previously updated neighboring cores. In contrast, composing \(k\) ordinary local update operations into one independent block task generally needs the accumulated upstream reach across all \(k\) updates. The distinction is synchronization, not an exemption from dependencies.

Convergence, failure and numerical meaning

The general image executor compares each newly computed owned core with the previous running core through Environment::same. The standard array-backed comparison uses the element type’s equality, not an implicit numerical tolerance. All blocks must be unchanged to stop. A change-count diagnostic records how many voxels differ; that count is separate from the equality decision.

A NaN is not equal to itself under the standard comparison, so an update that retains NaNs does not converge merely because their bit patterns stop changing. HExtremaOp checks invalid mask values early so this problem has an explanation about input data rather than an eventual generic convergence error.

SubstageLimit is a required runaway guard. Reaching it before convergence returns an error; it does not publish a partially converged image as if the fixed-point operation had succeeded. The limit includes the work needed to establish that another substage produces no change. Use an algorithm-derived bound or an explicit justified cap, not an arbitrary small number chosen to fit a desired runtime.

Dirty blocks require a stronger promise

IterativeOp::stationary can declare that the same operand windows always produce the same output, independently of substage index and hidden state. With that promise, the executor may skip a block when none of the blocks supplying its neighborhood changed in the previous pass. The first population of a private next-state buffer still needs correct carried-forward cores.

Stationarity is stronger than bounded reach. A seed-initialization pass or an iteration-dependent step size can invalidate it. The default is false, and the current production image implementations above do not opt into this optimization. A wrong true declaration can leave stale values without an obvious error, so it needs direct full-sweep equivalence tests.

Memory and other forms of iteration

The current general executor allocates two whole-volume private running buffers and processes their cores in blocks. The live state is constant in iteration count, but grows with image volume. It is not a disk-backed iterative state store and does not support the generic distributed image-phase route. This limitation matters even when the input environment is Zarr-backed.

IterativeReduceOp is a different interface: each pass maps image blocks to partial evidence, then updates a small shared state. StateUpdate explicitly reports whether that state has converged. Volume registration uses this shape for parameter fitting, where step or cost tolerances differ from exact image equality and the carried state is not an entire evolving image.

Finally, DiffusionStepOp is a finite-time local PDE update; its helpers can compose a stated number of steps or materialise between steps. The resident tv_denoise_into routine uses a chosen number of projection iterations. The finite-PSF deconvolution solver has its own fixed-count and relative-change stopping policies and StateStore abstraction, including ZarrState for bounded disk-backed state. Calling all these loops “fixed-point execution” would conceal the distinctions that determine correctness and memory use.