Electronic Thesis and Dissertation Repository


Master of Science


Computer Science


Olga Veksler


Blood vessel extraction and visualization in 2D images or 3D volumes is an essential clinical task. A blood vessel system is an example of a tubular tree like structure, and fully automated reconstruction of tubular tree like structures remains an open computer vision problem. Most vessel extraction methods are based on the vesselness measure. A vesselness measure, usually based on the eigenvalues of the Hessian matrix, assigns a high value to a voxel that is likely to be a part of a blood vessel. After the vesselness measure is computed, most methods extract vessels based on the shortest paths connecting voxels with a high measure of vesselness. Our approach is quite different. We also start with the vesselness measure, but instead of computing shortest paths, we propose to fit a geometric of vessel system to the vesselness measure. Fitting a geometric model has the advantage that we can choose a model with desired properties and the appropriate goodness-of-fit function to control the fitting results. Changing the model and goodness-of-fit function allows us to change the properties of the reconstructed vessel system structure in a principled way. In contrast, with shortest paths, any undesirable reconstruction properties, such as short-cutting, is addressed by developing ad-hock procedures that are not easy to control.

Since the geometric model has to be fitted to a discrete set of points, we threshold the vesselness measure to extract voxels that are likely to be vessels, and fit our geometric model to these thresholded voxels.

Our geometric model is a piecewise-line segment model. That is we approximate the vessel structure as a collection of 3D straight line segments of various lengths and widths. This can be regarded as the problem of fitting multiple line segments, that is a multi-model fitting problem. We approach the multi-model fitting problem in the global energy optimization framework. That is we formulate a global energy function that reflects the goodness of fit of our piecewise line segment model to the thresholded vesselness voxels and we use the efficient and effective graph cut algorithm to optimize the energy.

Our global energy function consists of the data, smoothness and label cost. The data cost encourages a good geometric fit of each voxel to the line segment it is being assigned to. The smoothness cost encourages nearby line segments to have similar angles, thus encouraging smoother blood vessels. The label cost penalizes overly complex models, that is, it encourages to explain the data with fewer line segment models.

We apply our algorithm to the challenging 3D data that are micro-CT images of a mouse heart and obtain promising results.