Graph-based approaches to segmentation have gained popularity in recent years both in the general computer vision literature as well as in applied biomedical research1,2,3,4
because of their ability to provide a globally optimal solution. This stands especially in contrast to another popular segmentation technique, deformable models5,6
, that can be easily confounded by local minima during the iterative segmentation (expansion) process. In this study, we present a novel graph-based algorithm for segmenting 2D and 3D objects. The algorithm sets up a graph and performs a graph cut to separate an object from the background. Typical graph-based segmentation algorithms distribute the nodes of the graph uniformly and equidistantly on the image. Then, a regularizer is added7,8
to bias the cut towards a particular shape9
. This strategy does not allow the cut to prefer more complex structures, especially when areas of the object are indistinguishable from the background. We solve this problem by introducing the concept of a “template” shape of the object when sampling the graph nodes, i.e., the nodes of the graph are distributed non-uniformly and non-equidistantly on the image. This type of template-based segmentation is particularly applicable to medical imagery, where it is easy to obtain initial landmarking10,11
and patient orientation from the information stored in the image headers. To evaluate our method, we demonstrate results on 2D images where the gray level appearance of the objects and backgrounds are quite similar. In 3D, we demonstrate the results of the segmentation algorithm on 60 clinical Magnetic Resonance Imaging (MRI) datasets of brain tumor (glioblastoma multiforme and pituitary adenoma) patients to support the time-consuming manual slice-by-slice segmentation process typically performed by neurosurgeons.
Evolving from the cerebral supportive cells, gliomas are the most common primary brain tumors. The grading system for astrocytomas according to the World Health Organization (WHO)
subdivides grades I–IV, where grade I tumors tend to be least aggressive12
. Approximately 70% of the diagnosed tumors are malignant gliomas (anaplastic astrocytoma WHO
grade III, glioblastoma multiforme WHO
grade IV). Subject to its histopathological appearance, the grade IV tumor is given the name glioblastoma multiforme (GBM). The GBM is the most frequent malignant primary tumor and is one of the most malignant human neoplasms. Due to their biological behavior, surgery alone cannot cure this disease. Thus, current interdisciplinary therapeutic management combines maximum safe resection, percutaneous radiation and in most cases, chemotherapy. Despite new radiation strategies and the development of oral alkylating substances (for example Temozolomide), the survival rate is still only approximately 15 months13
. Although in former years the surgical role was controversial, current literature shows maximum safe surgical resection as a positive predictor for extended patient survival14
. Microsurgical resection is currently optimized with the technical development of neuronavigation15
containing functional datasets such as diffusion tensor imaging (DTI), functional magnetic resonance imaging (fMRI), magnetoencephalography (MEG), magnetic resonance spectroscopy (MRS), or positron-emission-computed-tomography (PET). An early postoperative MRI with a contrast agent at the point of origin quantifies the tumor mass removal. Then, the patient undergoes frequent MRI scans during the time of adjuvant therapy. Especially in case of a remnant tumor, the tumor volume has to be rigidly registered so a new tumor growth is not missed. For glioma segmentation in general (WHO
grade I–IV), several MRI-based algorithms have been introduced in the literature.
A good overview of deterministic and statistical segmentation approaches is given by Angelini et al.16
. Most of these are region-based while the more recent ones are based on deformable models and include edge information. Segmentation based on outlier detection in T2-weighted MR data has been proposed by Prastawa et al.17
, whereby the image data is registered on a normal brain atlas to detect the abnormal tumor region. Sieg et al.18
have introduced an approach to segment contrast-enhanced, intracranial tumors and anatomical structures of registered, multispectral MRI data. Using intensity-based pixel probabilities for tumor tissue, Droske et al.19
have presented a deformable model, using a level set20
formulation, to divide the MRI data into regions of similar image properties for tumor segmentation. An interactive method for segmentation of full-enhancing, ring-enhancing and non-enhancing tumors has been proposed by Letteboer et al.21
. Clark et al.22
introduced a knowledge-based automated segmentation method for multispectral data in order to partition glioblastomas. Gibbs et al.23
introduced a combination of region growing and morphological edge detection for segmenting enhancing tumors in T1-weighted MRI data.
In the following, we describe studies that are more closely related to our contribution. For example, Song et al.24
introduced a novel framework for automatic brain MRI tissue segmentation that overcomes inherent difficulties associated with this particular segmentation problem. They use a graph cut/atlas-based registration methodology that is iteratively optimized and incorporates probabilistic atlas priors and intensity-inhomogeneity correction for image segmentation. The usage of prior knowledge to guide the segmentation has been presented in a publication of Zhang et al.25
. In a first step, they use the continuity among adjacent frames to generate a motion template according to the Displaced Frame Difference's (DFD) higher character and a color template is established by using k-means clustering. Afterwards (based upon the information derived from motion and the color templates), the segmentation image is defined as foreground, background and boundary regions. Finally, the segmentation problem is formulated as an energy minimization problem. Datteri et al.26
proposed a combination of two segmentation methods: atlas based segmentation and spectral gradient graph cuts. To combine these two methods they first use the atlas-based segmentation method to segment the image. Then, they generate a third image used in the spectral gradient method as well as the source and sink points needed to initialize the graph cut algorithm.
This article is organized as follows. In Section 2, the experimental results are presented. Section 3 discusses our study and outlines areas for prospective tasks. Section 4 describes the details of the used material and the newly proposed approach. In part two of Section 4 (Calculation), a practical development from a theoretical basis is presented. Part three of Section 4 (Theory) extends the background of the contribution and lays the foundation for further work.