On several geometric optimization problems in biomedical computation

Biomedical computation is an emerging field that includes the use of algorithmic approaches and optimization methods to solve challenging biomedical problems. The problems studied in this field originate from traditional medical image analysis, cancer therapy, computer aided surgery, and a variety of other areas. In this dissertation, we study several such problems motivated from important biomedical imaging applications.; The first problem we study is the Biplane Imaging Geometry Determination problem, motivated from the need for an accurate 3D coronary vasculature reconstruction from only two views in cardio-vascular interventional situations. Here, we seek to determine the orientation parameters (triplet of Euler angles and translation vector) from known corresponding points in two views. We propose a polynomial time geometric algorithm that determines the 'pose' by transforming the geometry optimization problem into a cell search problem in R6 parameter space of the geometry variables. Our algorithm then employs this construction to explain the equivalence (in terms of reconstruction errors) among existing algorithms for this problem. We show that input configuration shapes have a strong effect on what we call the solution space of feasible geometries, this can be queried to determine preferable input configurations and predict the accuracy attainable for given inputs.; The second problem we study is the Brachytherapy Seed Localization problem. Here, one seeks to localize the 3D positions of implanted seeds from multiple views in prostate brachytherapy, a common treatment for prostate cancer. An automatic reconstruction of the 3D seed configuration is not possible because correspondences between the 2 D seeds are not known and the orientation geometry could be inaccurate. We propose an optimization algorithm by formulating a minimization Integer Program with special constraints that capture the geometric information available from the imaging setup. We solve the equivalent linear program and 'round' the fractional solution vector to yield correspondences. We also present extensive evaluations on clinical datasets.; The third problem we study is the Ensemble Clustering problem. The input is in the form of multiple classifications or clustering solutions ( e.g., outputs from multiple computer assisted diagnosis procedures or image segmentations) and one seeks to "aggregate" the solutions into one solution that maximizes the agreement in the input ensemble. For this problem, we obtain several improvements over the best existing algorithms. More specifically, we show that the notion of agreement under such circumstances can be better captured using a 2D string encoding rather than a voting strategy. Our optimization proceeds by first constructing a non-linear objective function which is then transformed into a 0-1 Semidefinite program (SDP) using novel convexification techniques. We propose a polynomial time algorithm for solving the relaxed version of the SDP and discuss experimental evaluations.; The fourth problem we study is the limited view Computed Tomography reconstruction. The problem has several important clinical applications spanning coronary angiographic imaging and breast tomosynthesis. We first show that the limited view reconstruction problem can be formulated as a "constrained" version of the metric labeling problem. This lays the groundwork for a linear programming framework that brings together metric labeling classification and algebraic tomographic reconstruction (ART) in a unified model: where voxels must be reassigned subject to maximally maintaining consistency with the input reconstruction and the ART objective simultaneously. The approach can reliably reconstruct volumes with several multiple contrast objects, we present experiments on cone bean computed tomography.