Growing Airway Trees Through Lung Opacities with a Kinematic Motion Planner

Deep networks that segment the airway tree in chest CT label each voxel as airway or not, one at a time. When disease blurs the image, as with the hazy "ground-glass" opacities of COVID-19 pneumonia, the thin outer bronchi fade into the surrounding lung and the predicted tree breaks apart. The ATM'22 benchmark measured this directly: average branch detection fell from about 90% on ordinary scans to about 64% on COVID-19 scans (ATM'22). Protein modelers faced a similar problem and solved it differently. A protein is a chain of rigid pieces joined by rotating joints, and robotics-style planners explore the shapes such a chain can take. They grow a search tree of candidate shapes, throw out any shape where atoms collide, and when progress stalls they temporarily accept worse moves so the search can cross a barrier (Molloy & Shehu).

We propose to treat airway extraction the same way. The airway becomes an articulated tree of short tubular links. Each link has a length, a radius, and a bending angle at its joint, and all three stay within anatomical limits. A sampling planner grows this tree outward from the confidently segmented central airways, guided by the network's voxel probabilities. When evidence drops inside an opacity, the planner can extend a bounded distance on geometry alone. The extension survives only if the branch picks up image evidence again further on. The claim is that hard limits on geometry, plus bounded crossing of low-evidence stretches, recover distal branches in diseased scans. Neither voxel losses nor learned gap repair can do this, because they need some signal in the probability map before they can act.

Core Claim

Networks lose branches in opacities because the network is asked to make a local decision without evidence. A planner makes a non-local decision instead. A 15 mm stretch of faint signal is acceptable when a plausible tube, bending smoothly and narrowing with depth, connects a confident parent branch to a confident distal fragment or to a region of recovered contrast. The new ingredients relative to existing airway methods are the explicit link-and-joint parameterization and the stall-triggered relaxation of the acceptance threshold. The relaxation step is the "reactive temperature" of Molloy & Shehu. The expected result is a smaller COVID-subset drop in branch detection, at a false-positive cost that we measure explicitly.

Relation to Prior Work

The planning machinery comes from macromolecular modeling. Molloy & Shehu adapted Expansive Spaces Trees, a planner that grows a tree of states and preferentially expands sparsely visited regions, to map Adenylate Kinase's hinge motion. They added a projection layer that penalizes oversampling and a Metropolis-style temperature that rises when expansion stalls. Surveys (Principles and Overview; Motion planning for molecular simulations) frame the general recipe: work in joint-angle space, and screen candidates with cheap geometric collision checks.

For the case where two fragments already exist and must be joined, we reuse inverse kinematics loop closure. Cyclic Coordinate Descent adjusts one joint at a time to bring a chain's end onto a target (Full cyclic coordinate descent; Modeling loops). The molecular setting differs from ours in one important way. There the chain's length and topology are fixed and only its shape varies. Here the planner must also decide how many links and branches exist, so tree growth and pruning are part of the output.

Two works motivate the approach and are the closest competitors. DeepTree ranked first on EXACT'09 and ATM'22. It heals breaks with a network trained on randomly broken skeletons, and it grows its pseudo-labels through iterative self-training. That approach is learned and voxel-based, and it has no explicit bending or radius constraints. It also still needs the break to be visible as a gap between detected pieces. A2-Net threads detected amino acids into a chain with Monte Carlo Tree Search guided by a bond-likelihood network. It is the nearest existing blend of volumetric detection and chain search. However, it only connects detections that already exist; it never extends into regions with no detections.

Corso et al. supply supporting evidence that a chain prior can override ambiguous appearance: they report 96.2% disc localization. Their chain is a 1D point sequence in 2D, with no joints and no branching.

Research Program

We first train a standard 3D segmentation network on ATM'22 training scans. It outputs voxel airway probabilities and, from a small auxiliary head, a local centerline direction and radius. The planner then works in link space. A state is a partial tree. Each leaf carries a position, direction, and radius. An expansion adds a link of fixed length whose joint angle is drawn from a bounded cone around the parent direction, and whose radius equals the parent's times a sampled taper factor of at most one. Occasionally the expansion instead adds a bifurcation, with child angles and radii sampled within limits we estimate empirically from ATM'22 training skeletons.

A candidate link is rejected by a collision test when it intersects another branch, exits the lung mask, or runs along a high-intensity wall. Each accepted link is scored by the mean probability inside its tube. Links above threshold are accepted outright. Below threshold, a leaf may continue in "tentative" mode with Metropolis acceptance at a temperature that rises with consecutive stalls. The number of tentative steps has a hard cap. At the cap, the tentative chain is pruned back to its last confident link unless it has regained evidence.

When the network output already contains a disconnected distal fragment within reach of a leaf, we first try Cyclic Coordinate Descent loop closure under the same joint limits. We accept the closure only if it is collision-free. The final mask is the network mask joined with the rendered tubes of accepted links.

We will analyze two things. The first is how the tentative-length cap trades branch recovery against leakage. The second is whether branches recovered only by the planner lie in opacity regions, which we check with the COVID labels in ATM'22.

Baselines

The do-nothing reference is the backbone network's own thresholded output, with largest-component extraction as ATM'22 participants commonly do. Every post-processing method runs on the same probability maps. Our planner must beat this output on branch detection in the COVID subset without lowering precision by more than a pre-registered margin. Precision here means the fraction of predicted tree length that lies inside the reference airway.

The strongest existing method is DeepTree (DeepTree). It ranked first on ATM'22 and EXACT'09 and reports gains of 7.5% in tree length detected and 4.0% in branches detected on BAS over its baseline. We will retrain it with its released recipe on the same ATM'22 training split, with the same backbone capacity and number of training epochs. The top ATM'22 entry, timi, gives the absolute reference: 95.9% tree length detected and 94.7% branches detected on the full test set (ATM'22). The file contains no COVID-subset number for DeepTree or timi specifically (no reported result found on Lacuna), so we will measure them ourselves. Beating DeepTree means a statistically significant gain in branch detection on the COVID subset, with overall tree length detected and precision at least matching it.

We also include a topology-loss baseline: the backbone trained with a centerline-continuity loss of the JCAM type that top ATM'22 teams used. Finally, we include a geodesic minimal-path baseline that links each leaf to the nearest distal fragment through a cost of one minus probability.

Three ablations isolate the key ingredients. The first removes joint-angle and taper limits, giving a free-growing planner with the same cost. The second removes the reactive temperature, so tentative steps are never allowed. The third removes Cyclic Coordinate Descent closure. All planner variants get the same wall-clock budget per scan and the same held-out tuning set.

Why not just…?

Why not just train the network with synthetic opacity augmentation? This is a real threat. If the network sees enough simulated ground-glass texture during training, it may learn to see faint bronchi itself. We will train the backbone and DeepTree with the same opacity augmentation we use for evaluation. If augmentation alone closes the COVID gap, the planner is unnecessary, and we would report that result.

Why not just connect fragments with a shortest path on the probability map? A minimal path needs both endpoints. In opacity regions the distal end is often simply missing from the network output, so there is nothing to connect to. DeepTree also reports that standard post-processing fails when terminal branches are absent from the probability map (DeepTree). The geodesic baseline tests this directly. We predict that where fragments exist, it will match our Cyclic Coordinate Descent closure. We also predict that where no distal fragment exists, it will recover nothing, while tentative growth recovers some branches. If the planner shows no gain in that second case, its value is only in the constraints.

Why not just use a topological loss or DeepTree's learned breakage repair? Losses that penalize broken centerlines still act only where the network has some gradient signal. The 90% to 64% drop persisted among ATM'22 teams that used such losses (ATM'22). DeepTree's repair is trained on random disconnections, not on long evidence-free stretches. Both appear as baselines, and the ablation without kinematic limits shows whether constrained geometry, rather than search alone, accounts for any gain.

Proposed Experiments

The primary evaluation uses ATM'22 validation and test scans. We report tree length detected, branches detected, and precision separately for the COVID and non-COVID subsets, and we also report results on BAS and EXACT'09. Because ATM'22 labels are incomplete, and the planner might find real bronchi that annotators missed and be charged with false positives, we add two checks.

The decisive check uses known ground truth. On clean ATM'22 validation scans, we overlay synthetic opacities that erase contrast over annotated distal branches and measure how much of the erased tree each method recovers. Here the true tree is known exactly, so recovery and leakage are unambiguous. The planner should recover substantially more erased length than the backbone, DeepTree, and the geodesic baseline, and the version without kinematic limits should leak more.

The second check addresses branches in real COVID scans that only the planner finds. An expert reader, blinded to method, labels a random sample of these branches as real, uncertain, or false. The idea fails if planner gains appear only on synthetic opacities, or if most planner-only branches on real scans are judged false.