Danny Z. Chen

Efficient detection of multiple inter-related surfaces representing the boundaries of objects of interest in d-D images (d ≥ 3) is important and remains challenging in many medical image analysis applications. In this paper, we study several layered net surface (LNS) problems captured by an interesting type of geometric graphs called ordered multi-column graphs in the d-D discrete space (d ≥ 3 is any constant integer). The LNS problems model the simultaneous detection of multiple mutually related surfaces in three or higher dimensional medical images. Although we prove that the d-D LNS problem (d ≥ 3) on a general ordered multi-column graph is NP-hard, the (special) ordered multi-column graphs that model medical image segmentation have the self-closure structures and thus admit polynomial time exact algorithms for solving the LNS problems. Our techniques also solve the related net surface volume (NSV) problems of computing well-shaped geometric regions of an optimal total volume in a d-D weighted voxel grid. The NSV problems find applications in medical image segmentation and data mining. Our techniques yield the first polynomial time exact algorithms for several high dimensional medical image segmentation problems. Experiments and comparisons based on real medical data showed that our LNS algorithms and software are computationally efficient and produce highly accurate and consistent segmentation results.

We present an improved multileaf collimator (MLC) segmentation algorithm, denoted by (static leaf sequencing with no tongue‐and‐groove error), for step‐and‐shoot intensity‐modulated radiation therapy (IMRT) delivery. is an improvement over the MLC segmentation algorithm called SLS that was developed by Luan et al. [Med. Phys. 31(4), 695–707 (2004)], which did not consider tongue‐and‐groove error corrections. The aims of are (1) shortening the treatment times of IMRT plans by minimizing their numbers of segments and (2) minimizing the tongue‐and‐groove errors of the computed IMRT plans. The input to is intensity maps (IMs) produced by current planning systems, and its output is (modified) optimized leaf sequences without tongue‐and‐groove error. Like the previous SLS algorithm [Luan et al., Med. Phys. 31(4), 695–707 (2004)], is also based on graph algorithmic techniques in computer science. It models the MLC segmentation problem as a weighted minimum‐cost path problem, where the weight of the path is the number of segments and the cost of the path is the amount of tongue‐and‐groove error. Our comparisons of with CORVUS indicated that for the same intensity maps, the numbers of segments computed by are up to 50% less than those by CORVUS 5.0 on the Elekta LINAC system. Our clinical verifications have shown that the dose distributions of the plans do not have tongue‐and‐groove error and match those of the corresponding CORVUS plans, thus confirming the correctness of . Comparing with existing segmentation methods, also has two additional advantages: (1) can compute leaf sequences whose tongue‐and‐groove error is minimized subject to a constraint on the maximum allowed number of segments, which may be desirable in clinical situations where a treatment with the complete correction of tongue‐and‐groove error takes too much time, and (2) can be used to minimize a more general type of error called the tongue‐or‐groove error.

The problem of generating delivery options for one-dimensional intensity-modulated beams (1D IMBs) arises in intensity-modulated radiation therapy. In this paper, we present an algorithm with the optimal running time, based on the 'rightmost-preference' method, for generating all distinct delivery options for an arbitrary 1D IMB. The previously best known method for generating delivery options for a 1D IMB with N left leaf positions and N right leaf positions is a 'brute-force' solution, which first generates all N! possible combinations of the left and right leaf positions and then removes combinations that are not physically allowed delivery options. Compared with the brute-force method, our algorithm has several advantages: (1) our algorithm runs in an optimal time that is linearly proportional to the total number of distinct delivery options that it actually produces. Note that for a 1D IMB with multiple peaks, the total number of distinct delivery options in general tends to be considerably smaller than the worst case N!. (2) Our algorithm can be adapted to generating delivery options subject to additional constraints such as the 'minimum leaf separation' constraint. (3) Our algorithm can also be used to generate random subsets of delivery options; this feature is especially useful when the 1D IMBs in question have too many delivery options for a computer to store and process. The key idea of our method is that we impose an order on how left leaf positions should be paired with right leaf positions. Experiments indicated that our rightmost-preference algorithm runs dramatically faster than the brute-force algorithm. This implies that our algorithm can handle 1D IMBs whose sizes are substantially larger than those handled by the brute-force method. Applications of our algorithm in therapeutic techniques such as intensity-modulated arc therapy and 2D modulations are also discussed.