Certifying That Words Stay Apart: Witness-Set Smoothing for Text Instance Separation

Scene text detectors find words by labeling each pixel as "text" or "background." They then group touching text pixels into separate words. The hard part is keeping neighboring words apart, because the gap between two lines of text is often only one or two pixels wide. If that gap fills in, two words become one blob, and the character reader downstream produces garbage. A small adversarial perturbation aimed at exactly those gaps is a cheap way to break an optical character recognition pipeline.

Randomized smoothing is the standard way to get a provable guarantee against such perturbations. It runs the model on thousands of noisy copies of the input and takes a majority vote. It is expensive, though, and in its dense-prediction form it gives up on exactly the thin boundary pixels that keep words apart. This note proposes certifying the property that actually matters, namely that two words remain separate, instead of certifying every pixel. Separation holds whenever a closed ring of background pixels surrounds each word's core. That ring can be routed through the most confidently background pixels in the gap, so it only needs to cover a few hundred pixels instead of a million. The result is a guarantee about instance topology that ignores irrelevant abstentions elsewhere and needs far fewer forward passes to reach a given radius and confidence.

Core Claim

A dense smoothed segmentation map $g$ assigns each pixel the label its base model outputs most often under Gaussian noise. Suppose that, for every input perturbation $\delta$ with $\|\delta\|_2 < R$, two sets of pixels keep their labels: a small core of pixels inside word $i$ stays "text," and a closed, 8-connected contour enclosing that core stays "background." Then no 4-connected text path can join word $i$ to any word outside the contour, so the words cannot merge. This follows from the standard digital-topology fact that an 8-connected background curve separates 4-connected foreground components. Adding a certified 4-connected text spine inside each word also rules out a word splitting in two. Together these give a certified count of separated instances.

The certificate therefore needs simultaneous tests only on a witness set $S$ (cores, spines and enclosing contours), not on all $H \times W$ pixels. The contour can sit anywhere in the gap, so it can avoid the unstable pixels where smoothing would abstain. The efficiency gain has a simple source. Certifying pixel $j$ at confidence threshold $\tau$ uses a union bound over the $m$ tested pixels plus a binomial concentration bound. With Hoeffding's inequality, this requires roughly

$$N \gtrsim \frac{\log(m/\alpha)}{2\,\min_{j \in S}(p_j - \tau)^2}$$

noisy forward passes. Here $p_j$ is the true probability that the base model gives pixel $j$ its majority label, $\alpha$ is the overall error budget, and the certified radius is $R = \sigma\Phi^{-1}(\tau)$ as in Scalable Certified Segmentation via Randomized Smoothing. Witness selection shrinks $m$ by two to three orders of magnitude. More importantly, it raises the worst-case margin $\min_j(p_j - \tau)$ by routing the contour away from fluctuating pixels, and that margin enters quadratically.

Relation to Prior Work

The certification machinery is reused from three papers. Certified Adversarial Robustness via Randomized Smoothing builds a provably robust classifier by majority vote under Gaussian noise and derives the $\ell_2$ radius. It also separates a small selection sample from a fresh estimation sample, which is the device we use to choose witnesses without invalidating the test. SEGCERTIFY, from Scalable Certified Segmentation via Randomized Smoothing, extends this to every pixel of a segmentation map, using Holm-Bonferroni correction and an abstain label. Our certificate is a strict sub-claim of theirs, restricted to a set we choose.

Two findings in that same paper motivate the proposal. Its abstentions cluster at object boundaries, and certifying one high-resolution image takes roughly 30–90 seconds. For text, those boundaries are the whole task. Adaptive Hierarchical Certification for Segmentation using Randomized Smoothing reduces boundary abstention by relaxing unstable pixels to coarser parent classes. It reports up to 35 points less abstention on COCO-Stuff-10K and about 29% better boundary coverage on Cityscapes. That approach is unavailable here: the only parent of "text" and "gap" erases the gap. We relax where we certify, not what label we certify.

Two other lines of work constrain the design. Center Smoothing: Certified Robustness for Networks with Structured Outputs certifies bounded drift of structured outputs in a metric such as $1-\text{IoU}$. A one-pixel bridge barely moves IoU yet merges two words, so a metric guarantee is the wrong kind of guarantee for topology. Localized Randomized Smoothing for Collective Robustness Certification exploits small receptive fields with spatially varying noise. The feature-pyramid backbones of text detectors mix information across the whole image, which weakens that lever. Our method needs no locality assumption.

On the text side, three papers supply the base models and evidence. Real-Time Scene Text Detection with Differentiable Binarization (DBNet) separates words by predicting shrunken kernels with a learned threshold map. Self-Organized Text Detection with Minimal Post-processing via Border Learning and WordFence: Text Detection in Natural Images with Border Awareness add an explicit border class around each instance. These are natural base models, since a trained moat should produce high-margin background contours under noise. They are also evidence that separation is structural. Border learning gained 0.27 F-score over binary segmentation with heuristic splitting on the PPT dataset.

Research Program

The base model is DBNet-ResNet50, fine-tuned with Gaussian noise augmentation at $\sigma \in \{0.12, 0.25, 0.5\}$. A variant adds a three-class border head in the style of Wu and Natarajan, which encourages a wide background moat that survives noise. Certification runs on DBNet's kernel map, the map after thresholding $P$ and before polygon expansion. Polygon expansion is deterministic but depends on kernel area, so we report two quantities. The first is kernel-level separation. The second is a stricter "expanded" separation, which requires the certified contour to be wider than the maximum expansion offset, so that expanded polygons also cannot touch.

Witness selection works as follows. Draw $n_0 \approx 64$ noisy samples and estimate per-pixel text probabilities $\hat p$. Extract candidate instances as components of the high-confidence text region, and take each instance's core and a 4-connected spine along its medial axis. For each instance, binary-search the largest threshold $t$ such that the region $\{\hat p_{\text{bg}} \ge t\}$ contains an 8-connected ring around that core alone. The inner boundary of that region becomes the contour. This is a widest-bottleneck problem: it maximizes the weakest background confidence on the ring. Words whose rings would have to enclose another core are flagged as "certified merged-or-uncertain" and not claimed.

Certification uses fresh samples. Draw $N$ new samples, compute one-sided Clopper-Pearson bounds for each witness pixel, and apply Holm-Bonferroni across $S$. A word is certified separated at radius $R$ only if every one of its witnesses passes. We also add a sequential variant that stops sampling as soon as all witnesses pass or a futility bound triggers. Validity across adaptive stopping is maintained by spending the $\alpha$ budget over a fixed geometric schedule of checkpoints.

The analysis asks three questions. How does the forward-pass count to reach a target certified separation rate scale with gap width? How much of the gain comes from smaller $m$ versus higher margin? Which training signal (noise only versus noise plus border class) produces certifiable moats?

Baselines

The naive reference point is the uncertified DBNet-ResNet50 detector, run once per image. It gives clean F-measure and speed but no guarantee. The file reports 84.7 F-measure on Total-Text for ResNet-50 and 62 FPS for ResNet-18 on MSRA-TD500, both from Real-Time Scene Text Detection with Differentiable Binarization. We will reproduce the clean number for our noise-trained model to measure the accuracy cost of noise training.

The strongest existing competitor is SEGCERTIFY with a conservative topological readout. Abstained pixels are treated as possibly text, and a pair of words counts as certified separated only if the certified-background pixels contain a separating 8-connected ring. This is a valid separation certificate built entirely from prior work, which makes it the real threat. It runs on the same noise-trained base model, the same noise samples, the same $\sigma$, $\tau$ and $\alpha$, and the same forward-pass budgets $N \in \{100, 500, 1000, 5000, 10000\}$. No reported result was found on Lacuna for SEGCERTIFY or any certified method on scene text benchmarks. The closest reported numbers are SEGCERTIFY's 88% certified pixel accuracy and 0.6 mIoU on Cityscapes, and its 30–90 seconds per high-resolution image. Beating it means either a higher certified-separated-pair rate at equal $N$, or the same rate at no more than one fifth of the forward passes on the adjacent-pair subset described below. A tie would mean the witness idea adds nothing beyond the readout.

The second competitor is center smoothing on the polygon set, using a Hungarian-matched Jaccard distance. It runs with matching budgets, and we report its certified drift together with how often a certified-small drift still coincides with an instance merge under attack. The file reports a certified Jaccard distance below 0.2 for MTCNN on CelebA at $\epsilon = 0.2$, from Center Smoothing: Certified Robustness for Networks with Structured Outputs. That figure comes from single faces, not dense text.

Two ablations isolate the key ingredient. The first keeps $m$ small but fixes contours to the geometric medial line of each gap instead of the widest-bottleneck route, which tests the margin effect. The second uses widest-bottleneck routing but certifies all pixels, which tests the effect of $m$. A third ablation compares training with and without the border class.

Why not just…?

Why not just run SEGCERTIFY and read connectivity off its output? This is the closest alternative, and it is included as the main baseline. Its weakness is that all $H \times W$ pixels share the Holm-Bonferroni budget, and its abstentions concentrate at boundaries, as reported in Scalable Certified Segmentation via Randomized Smoothing. In a one-to-two-pixel text gap, the ring it needs may simply not exist among its certified pixels. If its readout matches our rates at equal $N$ on narrow gaps, the proposal's efficiency claim fails, and the head-to-head comparison above is designed to settle that.

Why not just use adversarial training and keep single-pass speed? Adversarial training gives no guarantee. Certified Adversarial Robustness via Randomized Smoothing and Certified Adversarial Robustness with Additive Noise both document empirical defenses falling to adaptive attacks. We will still report PGD-trained DBNet under a merge-targeted attack, which maximizes text probability along the true gap, as an empirical comparison. If that model resists our strongest attack at the radii we certify, the case for certification rests on the guarantee alone, and we will say so.

Why not just certify the output polygons with center smoothing? A bounded IoU drift does not bound the instance count, since a thin bridge changes IoU by under a percent while merging two words. Center smoothing also adds pairwise distance computations over all samples. The experiment counts certified-drift cases that nonetheless merge under attack, which directly measures this gap.

Proposed Experiments

Experiments use Total-Text, CTW1500, MSRA-TD500 and ICDAR 2015. In each, we build an adjacent-pair subset: ground-truth word or line pairs whose closest gap is under four pixels at inference resolution. Results are stratified by gap width.

The primary metric is the certified-separated-pair rate at radius $R$. A secondary metric is a certified F-measure that counts a detection only if its separation and connectivity are both certified. Cost is reported as forward passes and wall-clock seconds per image on a single GPU. Curves of certified rate against $N$, compared with SEGCERTIFY plus readout, are the central figure.

The decisive check is the narrowest-gap bin, under two pixels. The proposal succeeds only if it certifies a substantially larger fraction of these pairs than the readout baseline at equal $N$. It must also show which ablation, small $m$ or widest-bottleneck routing, carries the gain. If routing contributes little, the method reduces to a cheaper Bonferroni correction, which would be a weaker but honest finding.

As a soundness check, we run merge-targeted PGD attacks within the certified radius on every certified pair and confirm zero merges. As a training check, the border-class model should raise the median contour margin $\min_j(p_j - \tau)$. Under the bound above, a doubled margin should cut the required $N$ about fourfold. Measuring whether it does tests whether the margin, rather than the hypothesis count, governs cost.