Several important tasks in medical image analysis can be stated in the form of an optimization problem whose feasible solutions are connected subgraphs. Examples include the reconstruction of neural or vascular structures under connectedness constraints. We discuss the minimum cost connected subgraph (MCCS) problem and its approximations from the perspective of medical applications. We propose a) objective-dependent constraints and b) novel constraint generation schemes to solve this optimization problem exactly by means of a branch-and-cut algorithm. These are shown to improve scalability and allow us to solve instances of two medical benchmark datasets to optimality for the first time. This enables us to perform a quantitative comparison between exact and approximative algorithms, where we identify the geodesic tree algorithm as an excellent alternative to exact inference on the examined datasets.

本文提出了基于目标相关约束和新型约束生成方案的分支定界算法，旨在解决医学图像分析中“最小代价连通子图”问题，并在两个医学基准数据集上实现了最优求解，使得我们在精确和近似算法之间进行了定量比较，鉴定了测地线树算法是精确推理的优秀替代方案。

医学图像分析中的最小成本连通子图问题