Title: Graph Cut Algorithms for Fast Approximate Energy Minimization in Image Analyis.
Many tasks in image analysis involve assigning a label (such as disparity) to every pixel. These tasks are naturally stated in terms of energy minimization. However, the huge computational expense involved in minimizing the energy has limited the appeal of this approach. In this paper we address the problem of minimizing a large class of energy functions that occur in image analysis. The major restriction is that the energy function's smoothness term must only involve pairs of pixels. We propose two algorithms that use graph cuts to compute a local minimum even when very large moves are allowed. The first move we consider is an "a/b"-swap: for a pair of labels "a","b" this move exchanges the labels between an arbitrary set of pixels labeled "a" and another arbitrary set labeled "b". Our first algorithm generates a labeling such that there is no swap move that decreases the energy. The second move we consider is an "a"-expansion: for a label "a", this move assigns an arbitrary set of pixels the label "a". Our second algorithm, which requires the smoothness term to be a metric, generates a labeling such that there is no expansion move that decreases the energy. Moreover, this solution is within a known factor of the global minimum. We experimentally demonstrate the effectiveness of our approach on image restoration, stereo and motion.
R. Chandrasekaran, chandra@utdallas.edu, The University of Texas at Dallas, USA
Title: Isotonic Separation
Many problems involve the separation of two sets. Examples in medical diagnosis, credit rating, cyber-nanny, bankruptcy prediction, expert systems, stock ratings, etc are few of the examples. Very often there are various parameters that go into these predictions; these are often called features. In many applications, the points in one set have larger (or smaller) values than those in the other. The idea is to develop a system that is "consistent" and accurate.
In this paper we show how to develop such a system that minimizes the weighted number of misclassifications. The problems are solved using network flow techniques. We have tested this approach on breast cancer and heart failure data. the models seems to work very well.
Danny Chen, dchen@cse.nd.edu, University of Notre Dame, USA
Title: Optimal Beam Penetration Problems in Two and Three Dimensions and Applications
The problem of determining an optimal penetrating beam among weighted regions (called beam penetration problem) arises in several applied areas such as radiation therapy, medical surgery, geological exploration, manufacturing, and environmental engineering. In this talk, we present efficient algorithmic techniques for solving various beam penetration problems among weighted regions in two and three dimensional spaces. In particular, we consider two types of problems: the covering problems (seeking an optimal beam to contain a specified target region), and the probing problems (seeking an optimal beam of a fixed shape to poke the target region). We have investigated several versions of these problems, with a variety of beam shapes and target region shapes in 2-D and 3-D. Our algorithms are based on interesting combinations of computational geometry techniques and optimization methods, and transform the beam penetration problems to solving a collection of instances of certain non-linear optimization problems. Our approach exploits useful geometric observations and generalizes the structures of Minkowski sums. Some applications and implementation results are also discussed.
Bhaskar DasGupta, bhaskar@dimacs.rutgers.edu, Rutgers University, USA
Title: On Computing Distances Between Evolutionary Trees
In this talk, I will review some recent and old results on a few transformation based distances for unweighted and/or weighted evolutionary trees, such as the nearest-neighbour-interchange distances, subtree-transfer distances, rotation distance and edit distances. I will also mention open problems regarding computation of these distances that are of interest.
Sven Dickinson, sven@cs.rutgers.edu, Rutgers University
Title: A Spectral Encoding of Tree Structure and its Application to Shape Indexing and Matching
In an object recognition system, if the extracted image features are multilevel or multiscale, the indexing structure may take the form of a tree. Such structures are not only common in computer vision, but also appear in linguistics, graphics, computational biology, and a wide range of other domains. In this talk, we first develop an indexing mechanism that maps the topological structure of a tree into a low-dimensional vector space. Based on a novel eigenvalue characterization of a tree, this topological signature allows us to efficiently retrieve a small set of candidates from a database of models. To accommodate occlusion and local deformation, local evidence is accumulated in each of the tree's topological subspaces. From the resulting set of model tree candidates, this same topological signature forms the heart of a tree matching (verification) algorithm that factors in the nodes' information. The algorithm computes the distance between two trees in the presence of spurious noise (node insertions/deletions) and occlusion, and returns a set of node correspondences. We demonstrate the approach with a series of indexing and matching experiments in the domain of \mbox{2-D} object recognition.
This talk represents joint work with Ali Shokoufandeh (Drexel University), Kaleem Siddiqi (McGill University), and Steven W. Zucker (Yale University).
Michael C. Ferris, University of Wisconsin, ferris@cs.wisc.edu
Title: Optimization of Gamma Knife Radiosurgery
The Gamma Knife is a highly specialized treatment unit that provides an advanced stereotactic approach to the treatment of tumor and vascular malformations within the head. Inside of the shielded treatment unit, beams from 201 radioactive sources are focused so that they intersect at the same location in space. The result is a spherical region of high dose referred to as a shot of radiation. Four different shot sizes are available to the user. By properly combining a set of shots, larger treatment volumes can be successfully treated with the Gamma Knife.
The goal of this project is to automate the treatment planning process. For each patient, the optimization would seek to produce a dose distribution that conforms closely to the treatment volume. The variables in the optimization would include the number of shots of radiation along with the size, location, and weight assigned to each. Preliminary optimization approaches will be described outlining modeling technique for the beam dosage along with mixed integer and nonlinear programs that have been used to solve the model. Particular emphasis will be placed on the real-time aspects of this problem.
Joint work with David Shepoard.
Yaorong Ge, gey@mthcsc.wfu.edu, Wake Forest University
Title: Discrete Problems in Virtual Colonoscopy
In this presentation we will discuss several problems in virtual colonoscopy that lead naturally to discrete mathematical solutions. Virtual colonoscopy is a new medical technology for colorectal cancer screening based on CT scans of the abdominal region. A CT scan evenly divides a target orthogonally into very small volumetric units and maps the average density of these small units into a three-dimensional matrix. The colon is inflated with gas prior to CT scanning. Therefore, matrix elements corresponding to areas inside a colon have much lower density values compared to other elements that correspond to human tissue structures. This criteria together with knowledge about human anatomy is used to determine a connected set of elements that represent the colon lumen. Colorectal cancer screening relies on careful and systematic examination of the surface of the extracted colon lumen. This requirement introduced three problems: (1) We need to determine the centerline of the colon lumen in order to guide the examination; (2) We need to determine the surface of the colon lumen for visual examination; and (3) We need to reduce the complexity of surface representation in order to visualize the colon surface efficiently. Because the colon lumen is represented by a set of connected grid points, the solutions to all three problems required fundamental tools from discrete mathematics.
Joint work with David Ahn, Jie Wang, and David Vining.
Peter Hall, Peter.Hall@cs.cf.ac.uk, University of Bath, UK
Title: A Model for Learning Human Vascular Anatomy
This paper gives a complete description of a representation for vascular anatomy that enables inter-patient variations to be incrementally acquired. We separate the vasculature into its toplogy (branching structure) and its geometry (vessel shape). For each we provide a representation, suggest similarity measures, and define addition operations; thus allowing complete vascular representations to be incrementally acquired. We review the acquisition process, and outline a typical use of the representation: three-dimensional reconstruction of vasculature from biplane angiograms. The novelty in this paper is furnished by the representation of inter-individual variations in vessel shape that permits incremental acquisition.
G. T. Herman, University of Pennsylvania, USA (joint work with Andrew Todd-Pokropek and A. Kuba)
Title: Medical applications of Discrete Tomography
Discrete tomography is a special type of tomographic inverse problem where the function to be reconstructed from its projections is discrete (i.e. has a very limited range of values). Especially of interest is the case when the range of the function is a known discrete set, for example binary with a convex support. In this case this a priory information can be used for determining discrete functions from very few (e.g., only 2 or 3) projections.
While discrete tomography as such has its own mathematical theory based mostly on discrete mathematics, in particular combinatorial and discrete geometry and has interesting theoretical problems concerning existence, uniqueness and algorithmic questions in different discrete spaces, it also has also some fascinating applications including the medical field which is one of the most promising areas.
Some of the most recent research topics in this field are:
We will present the connected theoretical and algorithmic problems and the present state of art of discrete tomography as applied to medical problems.
Leon D. Iasemidis, leon@epilepsy.health.ufl.edu, University of Florida, USA.
Title: Transition to Epileptic Seizures - An Optimization Approach into Its Dynamics
Epilepsy is among the most common disorders of the nervous system (second only to stroke). For the vast majority of patients, epileptic seizures occur in the absence of identifiable external precipitants. Thus, one needs to look into the characteristics of the epileptogenic brain itself to find an explanation for the intermittent occurrence of epileptic seizures. Given the complexity of brain circuitry and our recent results, it is highly likely that the brain behaves in a nonlinear fashion. If this is the case, the dynamical features of the epileptic brain (especially the transition to epileptic seizures) may be explained by the theory of nonlinear chaotic systems. Measures derived from the theory of nonlinear dynamics will be presented and used for prediction of impending epileptic seizures from analysis of multielectrode electroencephalographic (EEG) data. Results from the application of global optimization techniques to this problem will also be presented.
Anthony Macula, macula@geneseo.edu, SUNY-Geneseo
Title: Two-Stage Group Testing for Complexes in the Presence of Errors
Let [t] represent a finite population with t elements. Suppose we have an unknown collection of d+1 k-subsets C of [t]. We refer to C as the set of positive k-complexes and we simply call a subset in C a k-complex.
In the generalized group testing problem, C must be identified by performing 0 , 1 tests on subsets or pools of [t]. A pool is said to be positive (1) if it completely contains a k-complex; otherwise the pool is said to be negative (0). In classical group testing, each member of C is a singleton or a 1-complex.
In this talk, we exhibit a pseudo-random two-stage algorithm that identifies a large proportion of the positive complexes in the presence of testing errors. Our abstract pooling method has applications to combinatorial drug and biological library screening.
Olvi L. Mangasarian, olvi@cs.wisc.edu, University of Wisconsin - Madison, USA
(joint work with Yuh-Jye Lee and William H. Wolberg)
Title: Breast Cancer Survival Analysis and Chemotherapy via Support Vector Machines
Generalized support vector machines (SVMs) have played a prominent role recently in data classification and regression. By training an SVM with a possibly indefinite kernel, a highly nonlinear surface with good testing set correctness can often be obtained for classification or data fitting. In this work we train an SVM with a Gaussian kernel to classify 253 breast cancer patients, 140 of whom have received chemotherapy and 113 of whom have not received chemotherapy. We classify the patients into three categories based on the number of metastasized lymph nodes, a commonly used indicator for the need of chemotherapy. The features used to predict lymph node metastasis are extracted from 30 nuclear features plus the size of the tumor removed from the patient's breast. The nuclear features are determined from a non-invasive fine needle aspirate prior to surgery whereas the tumor size is determined after surgery. Three well separated Kaplan-Meier survival curves (blue, green and red) for the three categories are obtained with relative log-rank test p-values of less than 1.5%. The patients in the category with the most favorable survival curve (blue) contains mostly patients who have not received chemotherapy, whereas the category with the least favorable survival curve (red) contains mostly patients who have received chemotherapy. The intermediate green category contains patients most of whom have had chemotherapy, but with a considerably smaller percentage than that of the red category. The trained SVM can assign a new patient to one of the three categories
Hung Q. Ngo, hngo@cs.umn.edu, University of Minnesota, USA
Title: On DNA Screening
Combinatorial Group Testing has been found to be a very useful tool for DNA screening. In this paper, we study group testing algorithms with applications in DNA screening.
Joint work with Ding-Zhu Du.
Ingela Nystrom, ingela@cb.uu.se, Uppsala University, Sweden,
Joint work with Orjan Smedby, Linkoping University Hospital, Sweden.
Title: Analysis of Magnetic Resonance Angiography Images Using Skeletonization and Distance Transforms
Magnetic resonance angiography (MRA) is increasingly performed as a non-invasive method of evaluating patients with suspected vascular disease. In this study we have used images of the arteries of the pelvis obtained after intravenous injection of paramagnetic contrast material, i.e., gadolinium chelates, for arterial enhancement. These images are fairly easy to segment. When interpreting and analysing MRA images, the 3D tree structure and the thickness of the blood vessels are of interest. This shape information may be easier to obtain from the "skeleton" of the blood vessels.
The following image processing steps were performed in the analysis of the blood vessels: resampling the image to cubic voxels, segmentation of the blood vessels from the background through grey-level thresholding and morphological smoothing operations, distance transformation, skeletonization, skeleton pruning (and straightening of zig-zag parts), and finally quantitative (and qualitative) skeleton analysis.
Skeletonization of digital volume objects is either a reduction to a 2D structure consisting of 3D surfaces and curves, or a reduction to a 1D structure consisting of 3D curves only. Thin elongated objects, e.g., blood vessels, are well suited for reduction to curve skeletons. Our skeletonization method first reduces the object to a surface skeleton from which the original object can be recovered. Secondly, the surface skeleton is reduced to a curve skeleton. The topology (i.e., number of components, tunnels, and cavities) and the shape of the object are preserved. The skeletonization is based on a small number of simple local neighbourhood operations, which makes it fairly time efficient. The skeletal voxels are labelled with their (D6) distance to the original background, which in this case conveys information about the local width of the object. Positions for possible artery stenoses may be identified by locating local distance minima in our curve skeletons, which will be investigated further.
Future work will also be directed towards achieving more rotation and noise independent skeletons. We will also develop more "intelligent" and shape preserving pruning methods.
Sanguthevar Rajasekaran, raj@cise.ufl.edu, University of Florida
Title: Local Alignment Search in Biological Sequences
We present efficient algorithms for local alignment search in biological sequences. These algorithms identify maximal segment pairs (MSPs). Our algorithms are efficiently parallelizable. We employ fast Fourier transforms (FFTs). Though several attempts have been made in the past to employ FFTs in sequence analysis, they fail to capture local similarities. Our algorithms employ FFTs in a novel way to identify local similarities. FFT-based techniques have the attractive feature of benefiting from ultrafast special purpose hardware available for digital signal processing.
We also present a sorting based algorithm and a suffix tree based algorithm for the same problem.
Anand Rangarajan, anand@noodle.med.yale.edu, Depts. of Diagnostic Radiology and Electrical Engineering, Yale University
Title: An Integrated Pose and Correspondence Approach to Image Matching
A frequently encountered problem in medical imaging and computer vision is feature-based registration. When well localized point features can be extracted from images, feature-based registration requires us to solve the chicken-and-egg problem of determining the point-to-point feature correspondences and the spatial mapping (pose) between two sets of point features. Instead of eliminating either the correspondences or the pose via invariants, we attempt to simultaneously solve for them. When the correspondences are held fixed, it is possible to solve for the spatial mapping using a standard least-squares approach. Given the current state of the pose parameters, the correspondences can be obtained by solving a linear assignment or stable marriage problem. Thus, our integrated framework results in a joint assignment-least squares objective function on the spatial mapping and correspondence parameters.
We use an alternating algorithm approach to minimize this objective function. With the correspondences held fixed, we use a least-squares algorithm for the pose. With the spatial mapping is held fixed, we employ a novel deterministic annealing algorithm on the correspondences resulting in a fuzzy, doubly substochastic matrix of correspondences during the high temperature phase. As the temperature is reduced, the correspondences progressively approach a permutation matrix with binary outlier rejection. At each temperature, we use Sinkhorn's procedure of alternating row and column normalizations to ensure that the correspondence matrix is doubly substochastic. The result is a feature-based registration algorithm that avoids poor local minima, finds a good spatial mapping, determines one-to-one point correspondences and rejects a fraction of the point features as outliers. We illustrate the algorithm's performance on problems ranging from 2D rigid alignment of primate autoradiographs to 3D non-rigid registration of cortical anatomical structures.
Li Sheng, lsheng@mcs.drexel.edu, Drexel University
Title: Variants of Interval Graphs and their applications to DNA Physical Mapping
A generalization of interval graph is introduced for cosmid contig mapping of DNA. A graph is a tagged probe interval graph if its vertex set can be partitioned into two subsets of probes and nonprobes, and a closed interval can be assigned to each vertex such that two vertices are adjacent if and only if at least one of them is a probe and one end of its corresponding interval is contained in the interval corresponding to the other vertex. We show that tagged probe interval graphs are weakly triangulated graphs, hence are perfect graphs. For a tagged probe interval graph with a given partition, we give a chordal completion that is consistent to any interval completions with respect to the same vertex partition. Forbidden induced subgraph lists are given for trees with or without a given vertex partition. A heuristic that construct map candidates is given for cosmid contig mapping.
Kaleem Siddiqi, siddiqi@cim.mcgill.ca, McGill University
Title: Divergence-Based Skeletons
The Blum skeleton in 2D, as well as its generalization to a medial surface in 3D, are of significant interest for problems in bio-medicine related to shape analysis. However, the numerical computation of such descriptions has proven to be non-trivial. Most approaches are not stable with respect to perturbations of the boundary, and heuristic measures for simplification are often introduced. In this talk we introduce a new algorithm for computing such representations, which is based on the measurement of the net outward flux of a vector field per unit area/volume, and the detection of locations where a conservation of energy principle is violated. The approach leads to skeletons and medial surfaces which are stable, homotopic to the original object, and efficiently computed. We illustrate the algorithm with several computational examples.
Alan P. Sprague, sprague@cis.uab.edu, University of Alabama at Birmingham, USA
Title: Frequent Set Generation for Medical Surveillance, in the
Presence of Clones
Data Mining is a new field in Computer Science, which attempts to find patterns in databases , where the person seeking the patterns does not have a precise description of what patterns are being sought. An application of Data Mining is the analysis of the database of bacterial isolates from a hospital, to be on the lookout for increasing resistance to antibiotics. A standard method in Data Mining involves computation of 'frequent sets'. The standard algorithm to compute frequent sets blows up when the database contains several isolates from a highly resistant clone of bacteria. We consider algorithms to compute frequent sets which avoid the blowup.
Joint work with Stephen E. Brossette.
Jay Udupa, jay@mipg.upenn.edu, University of Pennsylvania, USA
Title: Some Discrete Problems in Practical Image Segmentation and Visualization
Image data, particularly medical, that are available to us today are digital. They capture information about natural objects such as human internal organs. The digital computer is a ubiquitous, indispensable tool that is utilized in processing, analyzing, and visualizing these images. It is therefore most natural to take inherently digital approaches to model, define, visualize, manipulate, and anlyze information about these objects. There are ample evidences in the literature that this approach leads to more elegant and natural mathematical theories, more efficient algorithms, and more general approaches than if we attempt to impose continuous approximations to the digital data. We will justify this premise with three exemplary tasks: iso-surface definition in nD images, 3D iso-surface rendering, and object segmentation in nD images via fuzzy connectedness. A variety of examples drawn from several medical applications including brain MR image analysis for multiple sclerosis lesion and tumor analysis, MR angiography, mammographic image analysis, and craniofacial 3D imaging will be presented to demonstrate the effectiveness and experience in these applications involving thousands of patient studies.
Jie Wang, wangjie@uncg.edu, The University of North Carolina at Greensboro
Title: Complexity of Min-Max Sphere Packing with respect to Treatment Planning
We study an optimization problem of packing unequal spheres into a 3D bounded region in connection with radiosurgical treatment planning. Given an input (R,V,S,L), where R is a 3D bounded region, V a positive integer, S a multiset of spheres, and L a location constraint on spheres, we want to find a packing of R using the minimum number of spheres in S such that the covered volume is at least V; the location constraint L is satisfied; and the number of points on the boundary of R that are touched by spheres is maximized. Such a packing arrangement corresponds to an optimal radiosurgical treatment planning. Finding an optimal solution to the problem, however, is computationally intractable. In particular, we show that this optimization problem is NP-hard. Hence, some form of approximations is needed. One approach is to consider a simplified problem with less constraints. This approach has met with certain success in medical applications (Wu,1996). We improve Wu's algorithm using a divide-and-conquer technique to reduce computation cost.
Q. Jackie Wu, qjw@po.cwru.edu, Case Western Reserve University, USA
Title: Morphology Guided Radiotherapy Treatment Planning and Optimization
The goal of radiosurgery is to deliver extremely high dose to the target while at the same time minimizing the dose to surrounding normal tissues. In gamma knife treatment planning, dose delivery is based on the unit "shot", which is approximately a spherical dose distribution in 3D space. Four collimators determine the shot size, and various weighting schemes can be used to fine adjust the shot size. For larger or irregular target volumes, multiple shots are used to cover different parts of the target region. The technique is relative simple to use. However, it results in large dose inhomogeneities inside the target volume due to the overlap of the different shots, and in large dose to normal tissues due to the enlargement of the transient region when two or more shots overlap with each other. Optimizing shot positions and sizes as well as shot positions relative to each other can significantly reduce the inhomogeneity and dose to normal tissues, resulting in an optimal treatment plan. The number of shots being used, as well as shots positions and sizes, is dependent on both the shape and the size of the target. Therefore, the treatment planning is a target shape based optimization process.
A special optimization method is described based on a morphological approach, specifically the skeletonization technique, to optimize treatment planning. Given a defined target volume, the target's skeleton, which uniquely characterizes the target, is used to determine the optimal shot positions and sizes. Only skeleton points can be candidate shot positions, so positioning of a shot is limited to the locus of the skeleton. Furthermore, the optimal size for each shot, which is a function of collimator size and weight, is also provided by skeletonization. Therefore, the shot position and size are optimized simultaneously at no extra computational cost. A set of such shot is generated using a dynamic optimization algorithm. The overall computation time is small, independent of target shape and size, and increases only slightly as the number of shots increases.
The optimal plan provides each shot's position and size, and the fusion of the boundaries of all of the shots is used to predict the final dose distribution. Results of optimal plans and the corresponding dose distributions show very good agreement. Therefore, the treatment planning process can be strictly based on skeletonization, and avoids complicated dose calculations.
By using the skeleton, the 3D optimization problem is reduced to a 1D optimization, with significant savings in complexity and computation time. Optimization based on target shape replicates and automates manual treatment planning, which makes the process more understandable, in contrast to other approaches.
Key words: computer-aided radiosurgery, computer-aided treatment planning, radiotherapy treatment planning, pattern recognition, optimization
Guoliang Xue, xue@hpc01.emba.uvm.edu, University of Vermont
Title: Fast Algorithms for Force-Field Computation in Molecular Clusters
In this paper, we study fast algorithms for force-field computation in molecular clusters. Given a cluster of N particles, conventional algorithm requires O(N*N) time to compute the force exerted on each particle by the other particles. We discuss O(N log N) algorithms and O(N) algorithms, as well as optimal parallel algorithms for this problem. Computational results will also be presented.