Soft Tuy-Completeness for Robust Projection Selection in Cone-Beam CT
Linda-Sophie Schneider, Andreas Maier · 2026
Read Soft Tuy-Completeness for Robust Projection Selection in Cone-Beam CT by Linda-Sophie Schneider, Andreas Maier (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24023.txt.
Introduction
Schneider and Maier replace the binary Tuy completeness test for cone-beam CT with a graded, differentiable score of near-orthogonality and coverage. They prove the selection problems NP-complete by reduction from Set Cover, motivating a greedy algorithm with a proven approximation guarantee and a mixed-integer program certifying bounds. Across six regions, varied budgets, and four occlusion settings, the median greedy-to-program ratio hit 0.998, with many cases certified optimal. They add Effective Spatial Resolution, a diagnostic mapping sampling gaps to feature sizes, which tracks reconstruction quality.
Catalog record
| CREATOR | Linda-Sophie Schneider, Andreas Maier |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116281 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.24023
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Soft Tuy-Completeness for Robust Projection Selection in Cone-Beam CT Linda-Sophie Schneider, Andreas Maier Abstract This work introduces a continuous soft near-orthogonality score and a resolution-aware saturated coverage objective for projection selection in region-of-interest focused cone-beam CT, grounded in Tuy’s completeness theory. Replacing the binary hit-or-miss model of classical Tuy completeness with a graded, differentiable formulation preserves a direct link to achievable feature sizes while enabling both efficient approximate and exact optimisation. We establish that the underlying discrete decision problems are NP-complete via polynomial-time reductions from Set Cover, motivating a submodular greedy algorithm with proven ( 1 − 1 / e ) (1-1/\mathrm{e}) approximation guarantees and a mixed-integer linear program (MILP) that provides certified optimality bounds. The MILP serves as a quality certificate for the greedy solution rather than a competing optimiser. The primary empirical finding confirms this relationship: across a systematic benchmark spanning six target regions, multiple projection budgets, and four controlled occlusion conditions, the pooled median greedy-to-MILP objective ratio was 0.998, with a substantial fraction of cases certified globally optimal. A binary formulation is included as a diagnostic baseline; it strengthens hard directional completeness but is weaker on the continuous coverage scale. We additionally introduce Effective Spatial Resolution (ESR), a physically interpretable trajectory-level diagnostic that maps directional sampling gaps to achievable feature sizes. ESR correlates reliably with matched reconstruction quality across projection budgets and occlusion levels, providing a practical bridge between the selection stage and the image domain without requiring reconstruction. 1 Introduction Cone-beam computed tomography (CBCT) has become an essential imaging modality across medical, industrial, and research applications. In medical imaging, CBCT is routinely deployed in interventional radiology suites, surgical navigation systems, and dentistry for real-time 3D guidance at a lower radiation dose and with faster acquisition than conventional multi-detector CT [ 41 ] . In industrial contexts, cone-beam systems enable non-destructive evaluation and inspection of complex parts with spatial resolutions and material sensitivity often exceeding conventional CT [ 20 , 1 ] . However, despite these advantages, standard circular or helical scan trajectories remain suboptimal for many applications, especially when scanning large, complex, or non-convex objects, or when operating under mechanical and dose constraints [ 21 , 24 , 36 ] . Furthermore, standard circular trajectories fundamentally fail to satisfy Tuy’s data completeness condition for off-center regions of interest (ROIs), as the source path cannot intersect all Radon planes passing through the target volume, inevitably leading to cone-beam artifacts and reduced reconstruction fidelity [ 17 ] . A fundamental challenge in CBCT system design is the trajectory completeness problem: ensuring that the acquired projections contain sufficient information for accurate 3D reconstruction. The classical answer is provided by Tuy’s data completeness condition [ 42 , 40 ] , which establishes that exact reconstruction is possible if and only if every plane intersecting the object also intersects the X-ray source path. In Radon-space terms, this corresponds to complete sampling of the 3D Radon transform over a region containing the object. While theoretically elegant, Tuy’s condition is formulated over a continuous parameter space where every plane through the object must intersect the source path, but its per-plane hit-or-miss character makes it effectively binary: a trajectory is either complete or it is not, with no gradient or degree of coverage to guide optimization. Maier et al. [ 32 ] and Liu et al. [ 31 ] later introduced practical discrete approximations by sampling the unit sphere of plane normals and counting covered directions, converting the continuous criterion into a quantitative but still binary-per-direction coverage score. This voxel-centric discretisation is computationally tractable, yet it still assumes idealized detector geometry and perfect visibility, and provides limited guidance for designing practical trajectories subject to real-world constraints. In practice, modern CBCT systems must contend with numerous physical and engineering realities: finite detector size and resolution, cone-beam geometry, spatially varying X-ray attenuation through the object and surrounding materials, scattered radiation, mechanical limits of robotic arms or C-arm gantries, and clinical or industrial dose and acquisition-time budgets. These constraints make it infeasible to fully achieve Tuy completeness; instead, practitioners must make informed trade-offs between trajectory complexity, data acquisition cost, and reconstruction quality. Furthermore, in many applications, perfect reconstruction of the entire volume is unnecessary; instead, the goal is to achieve high-quality imaging of a specific ROI such as a surgical target, a critical component, or a suspected defect. Such ROI-focused imaging offers the potential for substantial reductions in scan time and radiation dose. 1.1 Related Work and Problem Positioning Over the past two decades, several research directions have emerged to address trajectory design in CBCT under practical constraints. We situate our work within this landscape by critically reviewing four complementary research areas and identifying key gaps that motivate our contributions. Voxel-wise and local completeness metrics. To operationalize Tuy’s condition in realistic systems, researchers have developed quantitative, voxel-level measures of data completeness. The foundational direction-based sampling approach proposed by Maier et al. [ 32 ] and Liu et al. [ 31 ] reformulates Tuy’s global requirement locally: rather than requiring every Radon plane to intersect the source trajectory, they discretize the unit sphere of plane normals and check whether each sampled direction is covered by at least one source position. This voxel-centric perspective is both computationally practical and amenable to optimization. Building upon this foundation, Herl et al. [ 20 , 22 ] introduced significant extensions: they incorporate attenuation-based filtering by neglegting rays with high mean attenuation and angular-distance weighting, yielding more robust quality measures that account for ray penetration and material absorption. Their attenuation-aware completeness metrics are particularly relevant to materials with high density or high-Z components, where naive direction sampling would overestimate the utility of poorly-penetrating rays. Contemporaneous work by Clackdoyle and Noo [ 5 ] characterized incompleteness at the voxel level and validated local Tuy conditions using phantom studies, further demonstrating the practical utility of voxel-based completeness measures. However, a critical limitation of existing completeness-based work is its reliance on greedy heuristics. Standard approaches iteratively select the source that provides the largest marginal gain in coverage, but this strategy is sensitive to initialization order, unable to refine or revisit previously selected views, and lacking optimality guarantees. While greedy selection provides a scalable baseline, it foregoes the opportunity to benchmark solution quality against globally optimal trajectories. Our work directly addresses this gap by embedding these robust completeness metrics within a rigorous combinatorial optimization framework that leverages both greedy approximation algorithms with proven (1-1/\mathrm{e}) guarantees and mixed-integer linear programming (MILP) to provide certified optimality bounds and confirm that the greedy approximation is already near-optimal on the studied instances. Task-driven and object-aware trajectory optimization. A complementary paradigm to completeness-driven design is task-based image quality optimization, wherein the goal is to maximize performance on a specific diagnostic or measurement task rather than achieve universal data completeness. In medical imaging, Stayman et al. [ 41 , 3 ] developed task-driven trajectory optimization frameworks that directly optimize model-observer performance, namely the detectability index for a lesion detection task. Related work by Herl et al. [ 21 ] extended these approaches to industrial settings with multiple features of interest. In industrial CT, object-aware methods have proven particularly effective. Fischer et al. [ 10 ] proposed a detectability-index-based optimization algorithm for industrial X-ray