Finite-Memory Color Commitments for Streaming Video Colorization

Turning a black-and-white video into color is guesswork. The same gray shirt could be red, blue or green, and nothing in the frame decides it. Current systems handle this by training neural networks with soft penalties that discourage colors from changing between frames. They still fail in predictable ways. A dancer's dress slowly shifts hue over hundreds of frames. A person who walks behind a pillar comes back in a different color. A scene cut leaves the system clinging to colors that no longer apply.

We propose splitting the problem in two. A tiny discrete controller decides, for each tracked object, which color the object is committed to and when that commitment may be revised. A neural colorizer then paints pixels under that commitment. The controller is built with reactive synthesis, the formal-methods technique for automatically constructing controllers that provably satisfy temporal rules against any behavior of their environment. Here the environment is the object tracker and the colorizer.

The scientific question this makes answerable is how much memory such a controller needs. One view says a lookup table of per-object colors suffices. The game theory of combined logical and numerical objectives suggests something more specific. Optimal behavior needs unbounded memory. Near-optimal behavior needs only a small counter per object, and the achievable quality should improve measurably with that counter's precision.

Core Claim

Streaming colorization with per-object color commitments can be written as an energy game. An energy game is a two-player game on a graph in which one player must keep a running resource balance from going negative while also obeying logical rules.

Our claim has three parts. First, the controller's memory can be made independent of video length and image resolution. It scales only with the number of tracked identities and the precision of a per-identity "disagreement budget." Second, the gap between this streaming controller and the best color assignment chosen with hindsight over the whole video shrinks as that precision grows. The theory predicts this, and we can measure it. Third, the hard rules hold by construction even when the tracker makes errors, which no soft-loss system can promise.

The part that is new is not "use formal methods for consistency." Nothing in the literature we reviewed connects reactive synthesis to colorization. The new part is the specific question of when to hold and when to revise a color. We answer it with a synthesized, memory-bounded rule and measure its memory–quality curve.

Why the formal lens is the right tool here

Each identity faces a tension. Holding its color forever is rigid. That is the failure mode of first-frame anchoring, which Temporal Consistent Automatic Video Colorization via Semantic Correspondence concedes breaks at hard cuts and propagates first-frame errors. Following the colorizer's per-frame preference is the opposite failure: it flickers. The right behavior tolerates disagreement from the colorizer for a while and revises only when the evidence has accumulated.

This is exactly the "detour and compensate" structure studied in games that combine a logical condition with an average-reward condition. Better Quality in Synthesis through Quantitative Objectives combines a logical winning condition with maximizing long-run average reward. It shows that exactly optimal strategies need unbounded counters. It also shows that for every tolerance $\varepsilon>0$ some finite-memory strategy comes within $\varepsilon$ of optimal. That second result is what motivates our memory–quality curve.

Energy Parity Games constrains and supplies the design. It shows the system player needs memory of size $n \cdot d \cdot W$, where $n$ is the number of graph states, $d$ the number of logical priorities, and $W$ the largest weight. The adversary, by contrast, needs no memory at all. So memory must scale with the weight quantization $W$, which is what we sweep.

On Satisficing in Quantitative Games supplies the solving method. It replaces "optimize the cost" with "keep the cost under a threshold" and reduces this to linear-time safety games. It reports that numerical value iteration "struggled with games exceeding 200 states" while the automata approach "successfully solved games with over 50,000 states." We adopt satisficing precisely to avoid the unbounded-memory barrier that optimization would impose.

Stochastic games with lexicographic objectives shows that controller memory can depend only on the objectives, not on the arena's size. We test whether the same "arena-independent" property holds when the arena is a video.

Finally, Generalized Parity Games handles conjunctions of logical conditions and shows they need memory to track which conjuncts are satisfied. It warns us that coupling identities, for example by requiring distinct objects to keep distinct colors, will break the per-identity decomposition. The memory should then grow with the number of identities.

Research Program

The game. For each tracked identity $k$, the game state records four things: whether $k$ is visible, its committed color bin $b_k$, a quantized disagreement budget $E_k$, and a revision counter. The color bins are a coarse hue partition of the 313-bin quantization from Colorful Image Colorization, which treats colorization as per-pixel classification over discretized color.

At each frame the environment moves. It chooses visibility and scene-cut events, and it chooses the colorizer's probability distribution over bins inside $k$'s mask, within the range observed in real data. The controller then either holds $b_k$ or revises it to a new bin. The budget evolves as

$$E_k^{t} = \min\big(C,\; E_k^{t-1} + a - \lceil \lambda \cdot (-\log p_t(b_k)) \rceil\big),$$

where $p_t(b_k)$ is the colorizer's probability for the committed bin at frame $t$, $a$ is a fixed per-frame refill, $\lambda$ sets the integer weight scale (hence $W$), and $C$ caps the budget.

The specification. The controller wins if three conditions hold. The budget never goes negative, which is the energy condition. The rendered hue of a visible identity changes only at revision events. There are at most $R$ revisions per identity in any window of $L$ frames, which is a safety condition checked by a counting automaton. The optional coupled variant adds a fourth condition: identities that are simultaneously visible never share a bin.

We solve for the winning region and extract a Mealy machine, that is, a finite-state controller that reads events and emits hold/revise decisions. For this we use the fixpoint algorithm of Energy Parity Games on the per-identity product. The arena is small, on the order of bins × budget levels × counter values, so solving is cheap.

Rendering. The committed bin constrains the colorizer. Inside identity $k$'s mask, logits outside a neighborhood of $b_k$ are masked out before the annealed-mean decoding of Colorful Image Colorization. The background is left to the colorizer. We also run a second renderer that feeds the committed colors as instance hints to an exemplar-style network. This tests whether conclusions depend on the renderer.

Masks come from two sources. Ground-truth DAVIS masks give an oracle tracker that isolates the controller's effect. A real video object segmenter, run with injected identity swaps, reproduces the failure mode the DAVIS 2017 challenge report identifies as the main bottleneck.

The memory analysis. We sweep the budget precision (bits $\beta$ for $E_k$, from 0 to 8) and the weight scale. For each setting we record the controller's state count and its cost gap to the hindsight optimum. The hindsight optimum is computed by offline dynamic programming over the whole video, under the same revision constraints.

Baselines

The naive reference points are the two memory extremes. The memoryless colorizer applies Colorful Image Colorization independently per frame, so it always follows the model. The zero-bit "hold forever" controller is a per-identity lookup table that fixes each identity's color at first appearance. We expect the first to lose on consistency and the second to lose on long composite videos with cuts and lighting changes. Beating both on the joint consistency–plausibility measure is the minimum bar.

The strongest existing systems are two. Consistent Video Colorization via Palette Guidance conditions a video diffusion model on a global five-color palette over sliding windows. On DAVIS it reports FVD 590, colorfulness 22.64 and FID 53.76. Temporal Consistent Automatic Video Colorization via Semantic Correspondence anchors all frames to an automatically colored first frame and reports FID 46.28 on DAVIS. For the metric that matters most here, per-identity hue switches within visible stretches, we found no reported result on Lacuna for either system. We will therefore rerun both with their released settings on identical clips and resolution.

Beating them means a lower identity-switch rate and fewer specification violations at FID and FVD no worse than theirs on the same clips. We do not expect to win on raw FID with a lightweight renderer. If FID worsens by more than the gap between those two systems, we count that as a loss.

Two ablations isolate the key ingredient, the synthesized memory-bounded revision rule. A hand-tuned hysteresis rule ("revise after $T$ consecutive frames of disagreement above $\tau$") gets the same tuning budget as our specification parameters. We give each 50 configurations on a held-out DAVIS split. A fixed-lag Viterbi smoother picks bins with a switch penalty using $\ell$ frames of lookahead. It is compared at matched latency and also with extra lookahead, to show what hindsight buys.

All methods share the same masks, the same base colorizer where applicable, and the same evaluation clips.

Why not just…?

Why not just keep a lookup table of each track's color? This is the zero-bit endpoint of our sweep, and on short DAVIS clips it may genuinely match us. Our claim rests on longer composites in which objects re-enter under new lighting and scenes cut. There, a fixed table reproduces the anchor-obsolescence failure that Temporal Consistent Automatic Video Colorization via Semantic Correspondence describes. If the table matches us on the composites too, the memory story is empty and we will report that.

Why not just a hand-tuned hysteresis rule? A hysteresis rule is itself a finite-memory strategy in the same family, so it is the most serious threat. If it matches the synthesized controller at equal tuning budget, what remains of our contribution is narrower. It is the guarantee that the revision and consistency rules hold against any tracker behavior within the modeled range, plus the principled memory curve. We state in advance that we would then present the work as a verification and analysis result, not a quality result. The adversarial identity-swap experiment is where we expect a separation, because tuned thresholds are fit to typical, not worst-case, tracker behavior.

Why not just smooth offline with an HMM or Viterbi? Offline smoothing needs the future, and it bounds switches only softly through a penalty. We use it as the hindsight optimum that defines our gap. We also compare at matched latency, where the question is whether a few frames of lookahead beat a few bits of memory.

Why not just train an end-to-end video diffusion model with temporal losses? Fully Automatic Video Colorization With Self-Regularization and Diversity notes that its flow-based consistency "breakdowns" under rapid motion and blur. Consistent Video Colorization via Palette Guidance concedes that its palette acts on the whole scene rather than on individual instances. Neither offers per-identity guarantees. Our identity-switch metric on multi-object DAVIS sequences directly tests whether their soft consistency already suffices.

Proposed Experiments

We evaluate on DAVIS 2017, whose multi-object sequences come with masks, and on Videvo. We add long composite videos built by concatenating DAVIS clips with shared identities re-entering after gaps and cuts. We also run a qualitative test on the 1916 Chaplin footage used by Fully Automatic Video Colorization With Self-Regularization and Diversity.

The metrics are:

  • FID and FVD for realism.
  • Colorfulness.
  • Per-identity hue-switch count within visible stretches, measured in $ab$ space.
  • Specification-violation rate.
  • Cost gap to the hindsight optimum.
  • Controller state count.
  • A paired human preference study against the palette-guidance system.

For the preference study, the reference point is that Fully Automatic Video Colorization With Self-Regularization and Diversity reports being preferred 80% of the time on DAVIS against its baselines.

Three checks decide the proposal.

The first is the memory–quality curve on the composites. If the gap to hindsight falls monotonically with budget bits and flattens, while the zero-bit table is clearly worse, the $\varepsilon$-optimal finite-memory picture carries over to video. If the curve is flat beyond one bit, it does not.

The second is the adversarial tracker test. We inject identity swaps at increasing rates. The synthesized controller should keep zero violations and degrade gracefully in cost, while hysteresis and diffusion baselines show rising switch counts.

The third is the coupling test. When we add the distinct-colors condition, controller memory should grow with the number of simultaneously visible identities, as Generalized Parity Games predicts for conjunctions. Without the condition, memory should stay per-identity and independent of video length.