title: EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS.
abstract: In this paper, we study several interestingoptimal-ratio region detection (ORD)problems ind-D (d≥ 3) discrete geometric spaces, which arise in high dimensional medical image segmentation. Given ad-D voxel grid ofncells, two classes of geometric regions that are enclosed by a single or two coupled smoothheighfield surfacesdefined on the entire grid domain are considered. The objective functions are normalized by a function of the desired regions, which avoids a bias to produce an overly large or small region resulting from data noise. The normalization functions that we employ are used in real medical image segmentation. To our best knowledge, no previous results on these problems in high dimensions are known. We develop a unified algorithmic framework based on a careful characterization of the intrinsic geometric structures and a nontrivial graph transformation scheme, yielding efficient polynomial time algorithms for solving these ORD problems. Our main ideas include the following. We observe that the optimal solution to the ORD problems can be obtained via the construction of a convex hull for a set ofO(n) unknown 2-D points using the hand probing technique. The probing oracles are implemented by computing a minimums-tcut in a weighted directed graph. The ORD problems are then solved byO(n) calls to the minimums-tcut algorithm. For the class of regions bounded by a single heighfield surface, our further investigation shows that theO(n) calls to the minimums-tcut algorithm are on a monotone parametric flow network, which enables to detect the optimal-ratio region in the complexity of computing a single maximum flow.
authors.affiliation: Department of Electrical and Computer Engineering, Department of Radiation Oncology, The University of Iowa, Iowa City, IA 52242, USA, xiaodong-wu@uiowa.edu.
authors.forename: Xiaodong
authors.initials: X
authors.lastname: Wu
keywords: Hand probing; algorithms; minimum closed set; optimal-ratio region detection; parametric search