Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Image analysis and segmentation is challenging because of the unpredictable appearance and shape of brain tumors from multi-modal imaging data. Among different segmentation approaches in the literature, it is hard to compare existing methods because of the variability of the quality of the images, validation datasets, the type of lesion, and the state of the disease (pre- or post-treatment). The Multimodel Brian Tumor Image Segmentation Benchmark (BRATS) challenge, [6], is organized to gauge the state-of-the-art in brain tumor segmentation and compare between different methods.

Non-negative matrix factorization (NMF) has shown promise as a robust clustering and data reduction technique in DNA microarrays clustering and classification [1] and learning facial features [5]. NMF is distinguished from the other methods, such as principal components analysis and vector quantization, by its use of non-negativity constraints. These constraints lead to a parts-based representation because they allow only additive, not subtractive, combinations. The first use of NMF for image segmentation was pioneered by our group in [3].

The level set method (LSM) is one of the most powerful and advanced methods to extract object boundaries in computer vision [2, 7]. The basic idea of LSM is to evolve a curve in the image domain around the object or the region of interest until it locks onto the boundaries of the object. The level set approach represents the contour as the zero level of a higher dimensional function, referred to as the “level set function” (LSF). The segmentation is achieved by minimizing a functional that tends to attract the contour towards the objects features. The advantages of NMF-LSM is that it: (i) is robust to noise, initial condition, and intensity inhomogeneity because it relies on the distribution of the pixels rather than the intensity values and does not introduce spurious or nuisance model parameters, which have to be simultaneously estimated with the level sets, (ii) uses NMF to discover and identify the homogeneous image regions, (iii) introduces a novel spatial functional term that describes the local distribution of the regions within the image, and (iv) is scalable, i.e., able to detect a distinct region as small as desired.

In this paper, we briefly explain NMF as a region discovery and clustering used to detect the homogeneous regions in the image [4]. The framework for segmenting the data of 191 patients (flair, t1, t1c, and t2 MRI images) in a limited time frame is achieved in two steps. The first step is applying the NMF-LSM segmentation method on each image using 264 processors at the UAB Super Computer; all the images were segmented in less than 12 h. The second step is the labeling, where the segments are labeled using a multimodal, user-friendly, and interactive software as (1) for necrosis, (2) for edema, (3) for tumor core, (4) for enhancing tumor, and (0) for everything else.

The paper is organized as follows: Sect. 2 describes briefly how the clustering and region discovery performed using NMF. Section 3 demonstrates the variational level set model. Section 4 elucidates the high performance computing (HPC) implementation. Section 5 describes the interactive semi-automated and multimodal method for labeling the targets/regions of interest. We proceed to the challenges in Sect. 6 and a summary of this paper is provided in Sect. 7.

2 NMF-based Clustering

The NMF-LSM method is fully automated, pixel-wise accurate, less sensitive to the initial selection of the contour(s) or initial conditions compared to state-of-the-art LSM approaches, robust to noise and model parameters, and able to detect as small distinct regions as desired (for a detailed description, please see [4]). These advantages stem from the fact that NMF-LSM method relies on histogram information instead of intensity values and does not introduce nuisance model parameters. We have applied the NMF-LSM method to analyze the MRIs of two patients with grade 2 and 3 non-enhancing oligodendroglioma and compared its measurements to the diagnoses rendered by board-certified neuroradiologists; the results demonstrate that NMF-LSM can detect earlier progression times and may be used to monitor and measure response to treatment [4].

The basic schemes of the NMF-based clustering are summarized in Fig. 1, where the image is divided into equally sized blocks and the histogram of each block is computed to build the data matrix V. Then, NMF generates matrices W and H that include key information on the number and histograms of the regions in the image and on their local distribution. These key information is used to build an accurate and pixel-wise variational level set segmentation model.

3 Energy Minimization and Segmentation

Segmentation is achieved by minimizing the energy functional \(\mathcal{F}\) in Eq. 1 with respect ot the level set function (LSF) \(\phi \) [4]. The minimization is achieved by solving the gradient flow equation: \(\frac{\partial \phi }{\partial t} = - \frac{\partial \mathcal{F}}{\partial \phi }\).

$$\begin{aligned}&\mathcal{F}(\phi ,b)=\alpha \sum _{i=1}^{k}\left[ \int _{\varOmega }e_i(\varvec{x},b)M_i(\phi )dx \right] +\alpha \sum _{i=1}^{k}\sum _{j=1}^{m} \left( \int _{\varOmega } \mathcal{I}_{S_j}(\varvec{x}) M_i(\phi )d\varvec{x}-\frac{h_{ij} a}{\sum _{i=1}^{k}h_{ij}}\right) ^2&\nonumber \\&\quad \quad \quad \quad \quad +\frac{\beta }{2} \int _{\varOmega }{(|\nabla \phi | -1)^2 dx} +\gamma \int _{\varOmega }{g |\nabla H(\phi )| dx}.&\end{aligned}$$
(1)

By calculus of variations, we compute the derivative \(\frac{\partial \mathcal{F}}{\partial \phi }\) as follows:

$$\begin{aligned} \frac{\partial \phi }{\partial t} = -\alpha \sum _{i=1}^{k}\sum _{j=1}^{m}\left[ {I}_{S_j} \frac{\partial M_i(\phi )}{\partial \phi }\left( {I}_{S_j} M_i(\phi )-\frac{h_{ij}a}{\sum _{i=1}^{k}h_{ij}}\right) \right] +\beta (\nabla ^2 \phi - div (\frac{\nabla \phi }{|\nabla \phi |})) +\gamma \delta (\phi )~div(\frac{\nabla \phi }{|\nabla \phi |}). \end{aligned}$$
(2)
Fig. 1.
figure 1

The basic schemes of the NMF-based clustering. The data matrix V is built from the histograms of the blocks of the image. NMF of V generates W and H; the former, including the histograms of the regions in the image, is applied to compute the number of regions. H, which includes information on the local distribution of the regions in each of the blocks, is used to modify the level set equation.

Full size image

In the implementation, the membership function \(M_i(\phi )\) is approximated by \(H_\epsilon (\varvec{x})=0.5 \sin (\arctan (\frac{x}{\epsilon }))+0.5\), and its derivative, the dirac delta function, is estimated by \(\delta _\epsilon (\varvec{x}) = 0.5 \cos (\arctan (\frac{x}{\epsilon }))\text { }\frac{\epsilon }{\epsilon ^2+x^2}\).

\(\mathcal{I}_{S_j}(\varvec{x})\) is the indicator function of block \(S_j\), and is defined as follows:

$$\begin{aligned} \mathcal{I}_{S_j}(\varvec{x})= {\left\{ \begin{array}{ll} 1, \text { if}\, \varvec{x} \in S_j\\ 0, \text {otherwise}. \end{array}\right. } \end{aligned}$$
(3)

The entries of the H matrix are \(h_{ij}\), and \(\alpha \), \(\beta \), and \(\gamma \), are weighting constants. The function \(e_i(\varvec{x}, b)\) is defined as follows:

$$\begin{aligned} e_i(\varvec{x}, b)=\log (\sqrt{2 \pi } \sigma _i) + \frac{(I(x)-\mu _i b(x))^2}{2 \sigma _i^2}, \end{aligned}$$
(4)

where \(\mu _i\) and \(\sigma _i\) are the mean and standard deviation of region i computed from the matrix W in the NMF factorization. For more details about the model, please refer to [4].

4 Super Computer Implementation

The dataset for each of 191 patients consists of four MRIs: FLAIR, T2, T1, and T1c at each brain section for every patient. In order to reduce computational times, the MRIs were pre-processed to select the images that include tumor, necrosis or edema. We wrote a software that displays all four modalities for each patient and allows the user to quickly identify the range of the 2D images to be sent for segmentation. The UAB super computer (high performance computing cluster) Cheaha has 3120 CPU cores that provide over 120 TFLOP/s of combined computational performance, and 20 TB of memory. All 191 patients were segmented by 265 processors in about 12 h. A single PC processed a single MRI in about 3 h. Four PCs can also process a patient’s four MRIs in about 3 h.

5 Interactive, Multimodal, Semi-automated, Labelling Software

We have devised an interactive and semiautomated software for labelling the target regions; we were driven by the heterogeneity of the quality of the datasets and by our desire to exclude brain abnormalities (like hemorrhage) that are not related to the four target regions. For example, the poor quality of the flair or t1 sequences of some of the subjects limited their usability; in these cases, we relied on other modalities. Furthermore, some MRIs showed subdural hematomas, which are unrelated to the tumor, producing high signal on t1 and t1c images. Our objective is to sketch and illustrate the basic concepts of the interactive labelling method. We do not plan on covering every single subject, but rather the general tools that we have developed. The overall quantitative analysis of this method is presented by the organizers of the challenge. We have chosen the following examples to illustrate the methodology and to point out inconsistencies in the tumor core.

5.1 Over-Segmentation, Ranking of Segments, and Combining Segments

The datasets in the BRATS 2016 challenge are highly heterogenous in quality and form, which made the segmentation task challenging. To ensure that the tumor structures are detected and separated from the normal structures of brain (gray and white matter), we over-segment by instructing the NMF-LSM method to generate 8 segments for each image. The number of segments is a parameter in the NMF-LSM software. The 8 segments are generated by one NMF-LSM process. These segments are ranked based on their maximum intensity values. It is fairly easy to combine segments to obtain the specified regions/targets, i.e. edema, enhancement, tumor core, and necrosis.

Figure 2(I) shows the flair image and its 8 segments ranked in order of their maximal intensity values from (max = 26, rank = 1) to (max = 255, rank = 8). By combining the segments in Figs. 2(I-i), (I-j), and (I-k), we obtain the edema region shown in Fig. 2(I-b). Figure 2(I-c) shows the final result.

Figure 2(II) shows the t1c image and its 8 segments ranked based on their maximal intensity values. By combining the segments whose ranks are 3 and 4 (Figs. 2(II-f) and (II-g), we obtain the necrosis region with the gray and white matter as shown in Fig. 2(II-b). We will subtract the normal brain structures in steps that follow. Combining the segments whose ranks are \(\ge 5\) gives us the region of contrast enhancement shown in Fig. 2(II-c).

Figure 2(III-a) shows the t1 image with its 8 segments ranked based on their maximum intensity values. By combining the segments whose ranks are 3 and 4, we obtain the tumor core region and the gray matter as shown in Fig. 2(III-b). We will subtract the gray matter in order to obtain the tumor core region as shown in the final result in Fig. 2(I-c).

5.2 Identification and Using Brain Structures to Semi-automate Labelling

We recognized from the case of Fig. 2 that we need to: (1) define the location of the normal structure of the brain, i.e. gray and white matter, in the image, and (2) the ranks of the segments that include the target regions. This goal will help us subtract/remove the normal structures of the brain and isolate the target regions.

Coordinates of White and Gray Matter. The segmentation of the t2 sequence yields the coordinates of the normal white and gray matter. By examining Fig. 2(IV), we notice that the normal white matter is identified by the segment whose rank and maximal intensity are 2 and 70 respectively. Furthermore, the gray matter is delineated by the segment whose rank and maximal intensity are 3 and 95, respectively. This is not surprising given the distribution of the intensities of white and gray matter in t2 sequences. These normal gray and white matter can be subtracted from the segments that include necrosis, tumor core, and enhancing tumor.

Fig. 2.
figure 2

Illustrative High Grade Case 1. The flair image (I-a) and its 8 segments ((I-d) to (I-k)) obtained by NMF-LSM. The images are ranked by their maximal intensities (shown). (I-b) shows the combination of segments (I-i) to (I-k), which gives us the region including the edema, tumor, and a part of the necrosis. (I-c) shows the final segmentation result including the four regions, edema (yellow), tumor core (orange), enhancement (red), and necrosis (blue). The t1c image (II-a) and its 8 segments ((II-d) - (II-k) are obtained by NMF-LSM. The images are ranked by their maximal intensities (shown). (III-b) displays the combination of the segments whose ranks are 3 and 4 (Figs. (II-f) and (II-g)), which gives us the regions of necrosis combined with the gray and white matter, which will be subtracted later. (II-c) shows the combination of the segments whose ranks are 5–8 (Figs. (III-h) - (III-k)), which gives us the region of contrast enhancement. The t1 image (III-a) and its 8 segments ((III-c) - (III-j)) are obtained by NMF-LSM. The images are ranked by their maximal intensities (shown). (II-b) shows the combination of segments whose ranks are 3 and 4 (Figs. (III-e) and (III-f)), giving us the region of the tumor core. The t2 image (IV-a) and its 8 segments ((IV-b) - (IV-i)) obtained by NMF-LSM. The images are ranked by their maximal intensities (shown). (IV-b) shows the segment corresponding to the background, whose rank and maximal intensity are 1 and 32, respectively. (IV-c) shows the segment whose rank and maximal intensity are 2 and 70, respectively; this segment corresponds to the normal white matter. (IV-d) shows the segment whose rank and maximal intensity are 3 and 95, respectively; this segment corresponds to the normal gray matter. The gray (IV-d) and white (IV-c) matter from the t2 image are applied to discover the ranks of the segments corresponding to the FLAIR signal and enhancement, respectively. (Color figure online)

Full size image

Automating the Discovery of the Ranks of Interest. Recall that NMF-LSM method processes each 2D slice separately to generate its segments, which are ranked by their maximal intensities. Furthermore, the interactive software processes each 2D slice separately. Having the coordinates of the normal white matter and gray matter from the segmentation of t2, yields the ranks of the segments of t1c, t1, and flair that correspond to these structures. For example, we can identify the rank of the segment of the t1c image that corresponds to white matter; this can be easily computed by finding the segment having the largest intersection with the white matter. We denote the rank of this segment by \(Rt1c_{wm}\). This is important because the lowest rank of the contrast enhancement in the t1c image is equal to either \(Rt1c_{wm}\) or \(Rt1c_{wm} +1\), depending on the quality of the image. For example, the lowest rank of the enhancement in Fig. 2(II) is 5 = \(Rt1c_{wm} + 1\). Below, we give an example where the contrast enhancement is detected at a rank \( = Rt1c_{wm}\).

Similarly, we can define the highest rank of the segment of the flair image that has an intersection with normal gray matter; we denote this rank by Rflair. Typically, the elevated signal in the flair image, corresponding to the edema, starts either in the segment whose rank \(= Rflair_{gm} \) or \(= Rflair_{gm} +1\), depending on the quality of the image; in the example of Fig. 2(I) the high signal in the flair image starts at the segment whose rank \(= Rflair +1\).

Fig. 3.
figure 3

High Grade Glioma Case 2. The t2 image (I-a) and its 8 segments ((I-c) - (I-j)) are produced by NMF-LSM. The images are ranked by their maximal intensities (shown). The coordinates of the normal white matter and gray matter are determined by the segments whose ranks are 2 (I-d) and 3 (I-e), respectively. (I-b) shows the final segmentation result including the four regions, edema (yellow), tumor core (orange), enhancement (red), and necrosis (blue). The flair image (II) and its 8 segments are ranked by their maximal intensities (shown). (II-b) shows the combination of the segments whose ranks are \(\ge 4\), (II-f) to (II-j), which gives us the region including the edema. The t1c image is shown in (III); its 8 segments (are also ranked by their maximal intensities (shown); necrosis is includes in segments 2 and 3 while the enhancement is included in the combination of the segments whose ranks are \( \ge 4\). The t1 image is shown in (IV); its 8 segments are also ranked by their maximal intensities (shown). (IV-b) shows the combination of segments whose ranks are 3 and 4, giving us the region of the tumor core. The gray (I-d) and white (I-e) matter from the t2 image are applied to discover the ranks of the segments corresponding to the FLAIR signal and enhancement, respectively. (Color figure online)

Full size image
Fig. 4.
figure 4

Low Grade Glioma Case. The t2 image (I-a) and its 8 segments are ranked by their maximal intensities (shown). The coordinates of the normal white matter are determined by combining the segments whose ranks are 2 and 3, (I-d) and (I-e). The segments whose ranks are 4 and 5 yield the coordinates of the normal gray matter, (I-f) and (I-g). (I-b) shows the final segmentation result including the four regions, edema (yellow), tumor core (orange), enhancement (red), and necrosis (blue). The flair image is shown in (II); its 8 segments are ranked by their maximal intensities (shown). (II-b) shows the combination of segments whose ranks are \(\ge 7\), (II-h) to (I-J), which gives us the region including the edema. The t1 image is shown in (III); its 8 segments are ranked by their maximal intensities (shown). (III-b) shows the combination of segments whose ranks are 4 and 5 (III-f) and (III-g), giving us the region of the tumor core. (Color figure online)

Full size image

The tumor core is defined from the t1 image. It is included in the segments whose ranks are below the segment of the t1 image that corresponds to the gray matter; Fig. 2(III) illustrates how to obtain the tumor core.

Masking. The high signal isolated from the flair image of the case shown in Figs. 2(I) can serve as a mask that filters the parts of the t1 and t1c that are positioned outside its outer borders. This approach is not applicable if the quality of the flair image is poor; in such a case, we computed the region of edema from the segments of the t2 images whose ranks are high and we extracted the cerebrospinal fluid (CSF).

Cystic Lesions in Low Grade Tumors. Because pathological necrosis has profound clinical implications, we did not label cystic lesions in low grade tumors as necrosis. We assumed that none of the images of the BRATS 2016 challenge were obtained during treatment by bevacizumab; hence, we consider a tumor as low grade if it lacks contrast enhancement.

6 Challenges

6.1 Tumor Core in High Grade Tumors

The ranks of the segments containing the high signal in the flair image of Fig. 3(II) are from \(Rflair = 4\) to 8. The contrast enhancement is detected in the segments of the t1c image whose ranks are \(Rt1c_{wm} = 4\) to 8. For the tumor core, applying the same rule as in case 1 above, yields the sum of the segments whose ranks are 3–5 (Figs. 3(IV-e)-(IV-g)), which essentially covers most of the region of the edema. Hence, we select the segments whose ranks are 3 and 4 (Figs. 3(IV-e)-(IV-f)); the final result is shown in Fig. 3(I-b). Notice that extracting the tumor core from the segments of the t2 image, whose ranks and 4 and 5 (Figs. 3(I-f)-(I-g)) would have given us a different result.

6.2 Tumor Core in Low Grade Tumors

The next case illustrates the challenge of computing the tumor core from low grade gliomas. The coordinates of the normal white matter are computed from combining the segments of t2 whose ranks are 2 and 3; the gray matter is configured from the segments of t2 images whose ranks = 4 and 5 (see Fig. 4(I)). The region for edema is computed from the flair image as detailed above by combining the segments whose ranks are 7 and 8. The region of the tumor core was extracted from the segments of t1 whose ranks are 4 and 5; the final result is shown in (Fig. 4(I-b)). Notice that the tumor core, extracted from t1, corresponds to region 8 of the t2 image, whose maximal intensity = 255 (Fig. 4(I-j)), which is paradoxical because the segments that include high signal in the t2 of the high grade glioma case shown in Fig. 3(I-h)-(I-j) do not correspond to the tumor core.

7 Conclusion

We have applied our novel NMF-LSM segmentation approach to segment the BRATS 2016 data sets [4]. We describe an interactive and semi-automated scheme for extracting the four targets/regions from the multimodal segments. The latter are ranked by their maximal intensities; the normal structures of the brain (white and gray matter) are discovered and are applied to semi-automate the identification of the segments that include the targets/regions of interest. Here, we have used the approach of over-segmentation followed by combining segments using the interactive software (see Figs. 2, 3 and 4). The interactive method lends itself to the development of logical and medically relevant criteria/standards for image analysis. Computations of the tumor core have generated paradoxical results; we suggest either abandoning it or redefining its meaning.