💻 computer science

Bounded Repair Reachability of Residual Critical Blocks in 3D Binary Masks under SAFE-Gated Single-Voxel Flips

This paper formulates and evaluates bounded repair reachability for critical blocks in 3D binary masks using SAFE-gated single-voxel flips that preserve foreground homotopy, demonstrating through experiments on BraTS 2021 data that endpoint and pathwise fidelity constraints yield distinct repair outcomes and topological validity within specified search bounds.

Original authors: Jihun Bae, Yeonho Bae, Jinglu Hu

Published 2026-10-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jihun Bae, Yeonho Bae, Jinglu Hu

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, medical images are often reduced to simple black-and-white maps. A computer sees a patient's brain not as a complex organ of tissue and fluid, but as a grid of tiny cubes, where each cube is either part of a tumor or part of the healthy space around it. These maps, called masks, are the foundation for surgeons planning operations and researchers measuring disease. However, the way computers connect these cubes can create strange, impossible shapes. Imagine a hollow room where the walls touch only at a single corner, leaving a gap that shouldn't exist in the real world. In digital terms, these are called critical configurations. They are mathematical glitches that make the image look broken to a computer, confusing its ability to count holes, measure surfaces, or trace the true shape of a tumor. If a computer tries to analyze a mask with these glitches, it might mistake a solid mass for a hollow shell or fail to see a tunnel entirely.

To fix these glitches, scientists have developed rules for changing the value of individual cubes, or voxels, one by one. The goal is to smooth out the image so that the digital shape matches the physical reality it represents, without accidentally merging two separate tumors or filling in a cavity that should remain open. This is a delicate balancing act. A change that fixes a glitch might also destroy the very shape the doctor needs to see. The challenge is to find a path of changes that repairs the image while keeping its essential topological features intact, ensuring that the number of separate parts and the number of tunnels remain exactly as they were in the original scan.

A team of researchers at Waseda University and Dongguk University set out to test the limits of this repair process. They focused on a specific type of glitch found in 3D brain tumor masks from the BraTS 2021 dataset, a collection of scans used worldwide to train medical imaging software. They started with masks that had already undergone a preliminary repair, leaving behind 680 stubborn, unresolved glitches. The researchers asked a precise question: if they were allowed to flip the value of a single cube at a time, could they fix these remaining glitches without breaking the rules of the image? They tested this under different sets of strict constraints. Some rules required that they only touch cubes involved in the current glitch. Others demanded that once a cube was flipped, it could never be flipped again. A third set of rules focused on fidelity, ensuring that the final image did not permanently remove any part of the original tumor that was present in the initial scan.

The researchers ran thousands of computer searches to find the shortest possible sequence of flips to fix each glitch. They discovered that the rules they imposed made a massive difference in whether a solution could be found. When they allowed the computer to flip any cube in a small neighborhood around the glitch, and did not restrict which cubes could be flipped or how many times, they found a successful repair for 666 of the 680 glitches. However, as soon as they added the rule that a cube could be flipped only once, the number of successful repairs dropped to 636. When they added the rule that they could only touch cubes currently involved in a glitch, the number plummeted to just five. When they combined both restrictions, no repairs were found at all. This showed that the path to a solution is not just about the destination, but about the specific steps allowed to get there.

The study also revealed a surprising trade-off between the final result and the journey taken to get there. The researchers distinguished between two types of faithfulness to the original image. One type, called endpoint fidelity, only cares that the final image contains exactly the same tumor material as the start. The other, pathwise fidelity, forbids the computer from ever removing a piece of the original tumor, even temporarily, during the repair process. They found that strict adherence to pathwise fidelity made it much harder to find a solution. Out of the 680 glitches, only 15 could be fixed if the computer was never allowed to remove a piece of the original tumor, even for a moment. In contrast, 72 glitches could be fixed if the computer was allowed to temporarily remove a piece of the tumor, provided it put it back by the end.

One specific case illustrated this dynamic clearly. In one brain scan, a stubborn glitch was surrounded by tumor tissue. The only way to fix it was to temporarily remove a piece of the tumor, fill in the gap to smooth the shape, and then restore the removed piece. This sequence of four steps successfully repaired the image and left the final tumor identical to the original. However, if the rule forbade any temporary removal, the computer could not find a solution within the allowed number of steps. The researchers confirmed that this temporary removal was not a mistake but a necessary maneuver to navigate the digital landscape. They also found that the rule preventing a cube from being flipped twice was a different kind of barrier. In some cases, a solution existed that required flipping the same cube twice, which was forbidden by the "flip-once" rule, even though the path was otherwise valid.

The researchers concluded that the ability to repair a digital image depends heavily on the specific rules governing the repair process. They demonstrated that a repair path that works under one set of rules might be impossible under another, even if the goal is the same. Their work did not propose a new way to fix images, but rather mapped out the boundaries of what is possible with existing methods. They showed that for many of the stubborn glitches in their dataset, a solution exists if the computer is given enough freedom to move cubes around, but that solution disappears if the rules become too strict. The findings suggest that in medical imaging, the choice of repair rules is a critical design decision. Allowing a temporary, reversible change to the image might be the only way to preserve the overall shape of a tumor while eliminating digital artifacts. The study provides a clear, data-driven map of these possibilities, showing exactly where the path to a clean image ends and where it is blocked by the constraints of the repair rules.

Technical Summary: Bounded Repair Reachability of Residual Critical Blocks in 3D Binary Masks under SAFE-Gated Single-Voxel Flips

Problem Statement
Three-dimensional binary segmentation masks often contain "critical configurations" (specific local arrangements of foreground and background voxels) that violate digital well-composedness. These configurations complicate topological operations such as surface extraction and skeletonization. While prior work has established methods to generate well-composed images, often by modifying the grid resolution or using interpolation, this study addresses a specific scenario: a deterministic repair process (based on a SAFE-gated, add-only procedure) has already been applied to a mask, leaving behind "residual critical blocks" that could not be resolved.

The core problem is bounded repair reachability: determining whether these remaining critical blocks can be resolved on the original input grid using a bounded sequence of single-voxel flips. The flips must satisfy three constraints:

SAFE-gated: Each flip must preserve the homotopy type of the foreground complex (ensuring topological validity).
Admissibility Rules: The sequence must adhere to specific path constraints regarding locality (flips restricted to critical blocks), flip-once (each voxel flipped at most once), and fidelity (preservation of the original foreground).
Boundedness: The search is limited to a spatial window ( $R$ ) and a maximum depth of flips ( $L$ ).

The study investigates how different combinations of these rules affect the ability to find a repair sequence that eliminates the target critical block without introducing new ones.

Methodology
The authors analyzed 680 residual critical blocks (specifically $k=2$ blocks with shell background voxels) derived from 222 Brain Tumor Segmentation (BraTS) 2021 training cases. The starting state ( $X_T$ ) for each block was the output of a preceding two-stage deterministic repair process.

SAFE Gate: A flip is deemed "SAFE" if the attachment of the voxel to the rest of the foreground (the intersection of the voxel's cube with the foreground complex) has Betti numbers $(1, 0, 0)$ . This condition guarantees that the flip preserves the homotopy type of the foreground complex in the closed-cube model with (26,6) adjacency.
Constraint Systems: The study evaluated 14 distinct systems combining:
- Locality (Loc): Flips are restricted to voxels within currently critical blocks.
- Flip-once: Two variants were tested: Path-local (P), where a voxel is flipped at most once relative to the start state $X_T$ ; and History-based (H), where flips are restricted relative to the original RAW mask.
- Fidelity: Three criteria were tested: $F_0$ (no restriction), $F_1$ (Endpoint fidelity: the final state must not have removed any original foreground voxels), and $F_2$ (Pathwise fidelity: no original foreground voxels can be removed at any step).
Search Algorithm: A Breadth-First Search (BFS) was performed for each block, system, and horizon setting ( $G_{26}$ : radius $R=2$ , depth $L=6$ ; and $G_{14}$ : $R=1, L=4$ ).
Outcome Classification: Searches were categorized as:
- FOUND: A valid repair path was found within the bounds.
- EXH (Exhausted): The reachable component was fully enumerated with no repair found.
- DL (Depth-Limited): The search reached the depth limit without finding a repair.
- CAP (Capped): The search hit a state limit ( $2 \times 10^6$ ) before completion.

Key Contributions

Formulation of Bounded Repair Reachability: The paper defines a framework for analyzing target-block repair under SAFE-gated single-voxel flips, explicitly separating admissibility rules (locality, flip-once) from fidelity criteria (endpoint vs. pathwise).
Equivalence under Flip-once: The authors establish that under the "flip-once" constraint, Endpoint Fidelity ( $F_1$ ) and Pathwise Fidelity ( $F_2$ ) yield identical sets of successful instances and identical shortest successful depths. This is because a path that flips a voxel at most once cannot remove and then restore a foreground voxel; thus, if the final state preserves the foreground, no intermediate removal occurred.
Computational Comparison of Constraints: Through 19,040 searches, the study quantifies how locality, flip-once, and fidelity restrict the solution space. It identifies "structural zeros" (blocks where the initial move set is empty due to constraints) and distinguishes between bounded absence of repairs and resource-limited outcomes.
Path Witness Analysis: The study provides specific "witness" paths that demonstrate the non-inclusion of constraint sets. For example, it shows cases where a path satisfies endpoint fidelity but violates pathwise fidelity (by temporarily removing and restoring a voxel), and cases where a path satisfies flip-once but violates locality.

Results

Impact of Constraints:
- Unrestricted ( $F_0$ , no Loc, no Flip-once): Found repairs for 666 of 680 blocks at $G_{26}$ .
- Locality Only: Repairs dropped to 5 blocks. In 595 blocks, the initial move set was empty because no voxel in a critical block admitted a SAFE flip.
- Flip-once Only: Repairs dropped to 636 blocks.
- Combined (Locality + Flip-once): No repairs were found (0 blocks) at $G_{26}$ .
Fidelity Impact:
- Under Endpoint Fidelity ( $F_1$ ), 72 repairs were found in the unrestricted system.
- Under Pathwise Fidelity ( $F_2$ ), only 15 repairs were found.
- All 15 $F_2$ repairs belonged to cohort C2 (blocks where the critical configuration was created by the preceding repair stage, not present in the original RAW mask). No $F_2$ repairs were found for cohort C1.
Specific Case Study (BraTS2021_00110): A critical block was repaired via a 4-flip path under Endpoint Fidelity ( $F_1$ ). This path involved temporarily removing a RAW foreground voxel and an added voxel, filling the gap to resolve the critical block, and then restoring the RAW voxel. This path was excluded by Pathwise Fidelity ( $F_2$ ) at the first step and by Flip-once at the final step. A completed search confirmed that no pathwise-faithful repair exists within the stated bounds for this block.

Significance and Claims
The paper claims to distinguish the topological validity of individual moves (guaranteed by the SAFE gate) from the admissibility of repair paths defined by specific constraints.

Modest Scope: The authors explicitly state that conclusions are limited to the stated windows ( $R \le 2$ ), horizons ( $L \le 6$ ), and move rules. The results do not prove the existence or non-existence of repairs beyond these bounds.
No New Operator: The study does not propose a new repair operator but rather analyzes the reachability of residual blocks under existing constraints.
Topological Guarantee: The work relies on the SAFE condition to preserve the homotopy type of the foreground complex. It does not claim to preserve the topology of the background, ambient isotopy, or multi-label topologies.
Practical Insight: The findings suggest that strict pathwise fidelity (never removing original foreground) significantly limits repairability compared to endpoint fidelity (restoring foreground at the end). This distinction is crucial for designing repair algorithms where temporary structural changes might be necessary to resolve topological defects without permanently altering the original segmentation.

The study concludes that while bounded searches can definitively find repairs or prove their absence within specific limits, the choice of constraints (locality, flip-once, fidelity) fundamentally alters the set of resolvable blocks, with strict constraints often rendering many residual critical blocks unreachable within the tested horizons.

More like this