Document Type


Date of Degree

Spring 2016

Degree Name

PhD (Doctor of Philosophy)

Degree In

Electrical and Computer Engineering

First Advisor

Wu, Xiaodong

First Committee Member

Wu, Xiaodong

Second Committee Member

Garvin, Mona K.

Third Committee Member

Kim, Yusung

Fourth Committee Member

Reinhardt, Joseph M.

Fifth Committee Member

Varadarajan, Kasturi R.


Labeling problem, due to its versatile modeling ability, is widely used in various image analysis tasks. In practice, certain prior information is often available to be embedded in the model to increase accuracy and robustness. However, it is not always straightforward to formulate the problem so that the prior information is correctly incorporated. It is even more challenging that the proposed model admits efficient algorithms to find globally optimal solution.

In this dissertation, a series of natural and medical image segmentation tasks are modeled as labeling problems. Each proposed model incorporates different useful prior information. These prior information includes ordering constraints between certain labels, soft user input enforcement, multi-scale context between over-segmented regions and original voxel, multi-modality context prior, location context between multiple modalities, star-shape prior, and gradient vector flow shape prior.

With judicious exploitation of each problem's intricate structure, efficient and exact algorithms are designed for all proposed models. The efficient computation allow the proposed models to be applied on large natural and medical image datasets using small memory footprint and reasonable time assumption. The global optimality guarantee makes the methods robust to local noise and easy to debug.

The proposed models and algorithms are validated on multiple experiments, using both natural and medical images. Promising and competitive results are shown when compared to state-of-art.

Public Abstract

Image segmentation, which extracts the target object from background, is an important task for both natural and medical images. It is natural to model image segmentation as a labeling problem in which every voxel gets a label indicating object or background. Various prior information for different applications are usually available in practice problems. In fact, for many tasks, the incorporation of prior information may be the key to achieve successful segmentations.

However, it is not always straightforward to enforce certain prior constraints in the labeling formulation correctly. What's even more challenging, the designed model may not have efficient algorithm to find the globally optimal solution.

In this dissertation, a series of labeling problems incorporating various useful prior information are proposed. Moreover, the globally optimal solution for all the proposed models can be computed using efficient algorithms. The proposed models and algorithms are validated on multiple applications of natural and medical image segmentation tasks. The experiment shows promising results competitive to the state-of-art.


publicabstract, efficient optimization, globally optimal, image segmentation, labeling problem, medical image analysis, prior information


xv, 190 pages


Includes bibliographical references (pages 180-190).


Copyright 2016 Junjie Bai