Interactive colorizers turn a grayscale photo into a color one from a few user "hints", which are colored dots placed on the image. They often bleed: a hint's color spills across an object boundary into a neighboring object. The worst cases are where the grayscale edge between two objects is faint or broken, and where two similar objects sit side by side, like two apples in a bowl. Current fixes either act at the coarse resolution of transformer image patches (about 16×16 pixels) or ask the user to repair the damage by hand. We propose a different kind of constraint. Each hint gets a fixed travel budget, measured as a shortest-path distance on the pixel grid that may not cross detected edges. Its color may only reach pixels within that budget. Because the budget is a path length rather than a region shape, it gives an explicit upper bound on how deep color can penetrate through any gap in an edge. Because it is computed on pixels, it is not limited by patch size.
The geometry behind this comes from work on the L1 metric, the "taxicab" distance where motion is only horizontal or vertical. On a 4-connected pixel grid, plain breadth-first search computes exactly the L1 geodesic distance: the shortest rectilinear path that stays inside a region and goes around obstacles. The set of pixels within budget $r$ of a hint is therefore an L1 geodesic ball. Inside simple regions such balls have unusually clean structure, which we use to check hint conflicts cheaply. The proposal has two parts. One is a drop-in, pixel-level mask for transformer colorizers. The other is a bleeding metric, "geodesic leakage depth", that measures how far a wrong color travels inside an object rather than whether global error went up.
Core Claim
Bleeding through a broken edge is a flooding problem. Any mask defined by connectivity, whether a connected component, a superpixel, or a segmentation region, floods the whole neighboring object as soon as the edge has a one-pixel gap. A mask defined by a distance budget leaks only as far as the remaining budget allows. Let $c$ be a hint, $r$ its budget, and $d(c,p)$ the L1 geodesic distance from $c$ to pixel $p$ on the grid graph with edge pixels removed. Every pixel colored by $c$ satisfies $d(c,p)\le r$. If the hint first reaches a gap $g$ at distance $d(c,g)$, color penetrates the far side by at most
$$ \text{leak}(c) \le r - d(c,g). $$
The bound itself is trivial. The claim we test is empirical. With $r$ set from the hint's own object, this bound turns catastrophic leaks into shallow ones, at pixel resolution and at the cost of one breadth-first search per hint. Patch-level attention masks and soft contrast-weighted distances do not give this guarantee.
Where this sits in prior work
Two lines of colorization work motivate the gap. iColoriT uses a Vision Transformer so that one hint can spread across a large region in a single layer. That is good for skies, but it gives the hint no built-in brake. Enabling Region-Specific Control via Lassos in Point-Based Colorization names the side-by-side failure "color collapse". It fixes collapse by zeroing attention between a hint and patch tokens outside a user-drawn lasso. That lasso is both manual and patch-resolution, and the file lists fine-structure leakage as an open problem. We keep their localized cross-attention mechanism, reuse it as our injection point, and replace the hand-drawn lasso with an automatically computed, pixel-level geodesic ball.
Three other lines constrain the design. Deep Edge-Aware Interactive Colorization against Color-Bleeding Effects corrects encoder features using user scribbles placed on bleeding edges, and introduces the superpixel-based Cluster Discrepancy Ratio metric. It shows that global PSNR misses bleeding, which motivates our metric. Its reliance on post-hoc scribbles is what we try to remove. Boosting… with Log-supermodular CRFs smooths chroma with attractive pairwise potentials on a 4-connected grid. It reports over-smoothing on thin structures, which is a warning against soft averaging. Pixelated Semantic Colorization and PalGAN build boundaries from semantics. PalGAN's Chromatic Attention aligns color transitions with luminance gradients. The file says palette and semantic methods fail on small, weakly featured objects, and semantic class masks merge adjacent instances of the same class, which is exactly the collapse case.
The geometry supplies the method. Computing the L1 Geodesic Diameter and Center of a Simple Polygon in Linear Time proves three facts about simple polygons. L1 geodesic balls are P-convex, meaning the shortest path inside the polygon between two points of a ball stays in the ball. Families of these balls have Helly number two, meaning a common intersection exists if and only if every pair intersects. The geodesic radius is exactly half the diameter. We use Helly-two to make hint-conflict checks pairwise. The same paper and Computing the L1 Geodesic Diameter and Center of a Polygonal Domain note that these properties fail once a region has holes. Pixel objects often do have holes, so we measure how often the simple-region case actually applies rather than assume it.
The closest tool is FastGeodis, a fast solver for contrast-weighted geodesic distance on raster grids. It already computes "geodesic distance from a seed". What we add is a different object: hard obstacles, an explicit budget, the leak bound above, and integration into colorizer attention. Whether the hard, budgeted version beats a soft FastGeodis distance is a central experiment, not an assumption.
Research Program
The first piece is the mask. We run a standard edge detector on the luminance channel and remove edge pixels from the 4-connected grid graph. For each hint we run one breadth-first search, which in this setting is exact L1 geodesic distance, and keep the pixels within budget $r$. The budget comes from a small head on the colorizer's encoder that predicts, per hint, a scalar fraction of the hint's eccentricity within its edge-bounded component. Eccentricity here means the farthest geodesic distance from the hint to any pixel of that component. When the component is intact, the budget stays inside the object. When the component has leaked through a gap, the predicted fraction must stay below one for the bound to bite. The head is supervised from COCO-Stuff instance masks by regressing the eccentricity within the true instance.
The second piece is injection. The pixel mask enters the transformer as a soft attention bias, computed as the fraction of each patch's pixels inside the ball. It is also applied as a hard gate on the final upsampled chroma. A pixel outside every ball is filled by the colorizer's unconditional prediction, mirroring the unconditional tokens of the lasso paper. Where balls of different-colored hints overlap, ownership is decided by smaller geodesic distance.
The third piece uses the geometry for conflict handling. Suppose several same-colored hints lie in a component that turns out to be a simple region, which we test via the Euler number of the component. Helly-two then says whether all their balls share a point using only pairwise checks. That tells us whether they plausibly describe one object or several. We report what fraction of real components are simple, so readers can see how much of this applies in practice.
The fourth piece is the metric, geodesic leakage depth. For each ground-truth COCO-Stuff instance, take the pixels whose predicted chroma is closer to a neighboring instance's ground-truth chroma than to their own. Record how far such pixels lie from the shared boundary, measured as L1 geodesic distance inside the instance. Normalize by the instance's geodesic radius. For simple instances, the radius is half the diameter by the Bae et al. result. Measuring depth geodesically matters because non-convex objects make Euclidean depth meaningless. We validate the metric against human bleeding judgments on a few hundred images and report its correlation alongside the Cluster Discrepancy Ratio.
Baselines
The naive reference is the unmodified iColoriT with global attention. It reports PSNR 30.63 on ImageNet with 10 hints, which is the fidelity figure we must not lose. Our mask is a plug-in on this same checkpoint, fine-tuned for the same number of steps, with the same simulated-hint sampler and identical hint locations at test time. Beating it means a lower geodesic leakage depth with PSNR within noise of the identically fine-tuned iColoriT.
The strongest existing competitor on collapse is the lasso model from Enabling Region-Specific Control via Lassos. It reports that one lasso carries information worth about 4.18 point hints on its synthetic color-collapse set. We run it in two ways. In the automatic setting, lassos are simulated as the ground-truth instance's bounding polygon, so it receives strictly more information than our hints-only method. In the realistic setting, lassos come from the same edge-bounded component our method uses. Beating it means matching its collapse-set quality without any lasso, and beating it at fine structures such as thin parts and hair, where its patch-resolution mask should leak.
The edge-aware scribble network of Deep Edge-Aware Interactive Colorization reports roughly 1.0–2.0 dB local PSNR gain using about 3 user scribbles per image. We compare at equal interaction counts by giving it simulated scribbles on bleeding edges. Beating it with zero scribbles would be a strong result. Matching it would still be useful.
The log-supermodular CRF of Boosting… with Log-supermodular CRFs is applied as a post-processing layer on the same backbone. No reported colorization number for it was found on Lacuna; the file says only "higher PSNR and SSIM than ChromaGAN", so we rerun it ourselves.
The key ablation swaps our hard, budgeted, 4-connected ball for three alternatives. The first is a thresholded contrast-weighted FastGeodis distance, with its threshold tuned on validation using the same budget. The second is the full edge-bounded connected component, which has no budget. The third is an 8-connected grid. Together these isolate whether hard obstacles and a distance budget, rather than geodesic distance in general, do the work.
Why not just…?
Why not just use FastGeodis's contrast-weighted geodesic distance as the mask? This is the most serious alternative and may work as well. A soft distance degrades smoothly at faint edges, which could be an advantage over hard edge removal. Our counter-hypothesis is that soft distances leak through gaps in proportion to how faint the edge is, with no fixed ceiling. A hard budget caps leakage regardless of edge contrast. The ablation above settles it directly. If FastGeodis matches us on leakage depth in the edge-gap stress test, the contribution reduces to the budget head and the metric, and we will say so.
Why not just mask each hint to a segmentation or superpixel region? Masking to a region inherits every mistake of the region. Semantic masks merge adjacent same-class instances, which is the collapse case. Superpixels and connected components flood through a single broken edge pixel. The "component, no budget" ablation measures exactly this. We expect it to be competitive on clean edges and to fail on the gap stress test.
Why not just apply a CRF or edge-aware upsampling of chroma? The CRF paper itself reports over-smoothing on thin structures, and smoothing redistributes leaked color rather than stopping it. The CRF baseline is run on identical inputs, and the thin-structure subset reports leakage depth there separately.
Proposed Experiments
The decisive test is a controlled edge-gap stress test. We take COCO-Stuff images with instance masks and erase a random fraction of edge pixels along true instance boundaries, at gap widths from 1 to 8 pixels. We then plot leakage depth against gap width for every method. The geodesic budget should keep depth flat. Connected-component masks should jump to full flooding at the first gap. Soft geodesic masks should rise with gap width. If our curve is not clearly flatter than FastGeodis's, the central claim fails.
Second, on the lasso paper's synthetic color-collapse set and on adjacent same-class instance pairs mined from COCO-Stuff, we compare collapse rates with no lasso against the lasso model.
Third, fidelity checks use ImageNet validation with 10 simulated hints, reporting PSNR against iColoriT's 30.63. CUB-200 and Oxford 102flowers serve as fine-structure sets, where patch-resolution masks are expected to fail.
Fourth, we report cost: per-hint breadth-first search time at 256 and 512 pixel resolution, set against iColoriT's 14 ms GPU inference.
Finally, two descriptive analyses report the fraction of COCO-Stuff instances that are simple regions, which bounds where the Helly-two conflict check applies, and the correlation of geodesic leakage depth and of the Cluster Discrepancy Ratio with human bleeding ratings.
References
- iColoriT: Towards Propagating Local Hints to the Right Region in Interactive Colorization by Leveraging Vision Transformer
- Enabling Region-Specific Control via Lassos in Point-Based Colorization
- Deep Edge-Aware Interactive Colorization against Color-Bleeding Effects
- Boosting the Performance of Generic Deep Neural Network Frameworks with Log-supermodular CRFs
- Pixelated Semantic Colorization
- PalGAN: Image Colorization with Palette Generative Adversarial Networks
- Computing the L 1 Geodesic Diameter and Center of a Simple Polygon in Linear Time
- Computing the L1 Geodesic Diameter and Center of a Polygonal Domain
- FastGeodis: Fast Generalised Geodesic Distance Transform