This research is devoted to the segmentation of heart and brain anatomical structures. In the study, we present a segmentation algorithm based on the square blocks (superpixels) propagation. The square blocks propagation algorithm checks two criteria. For the first criteria, the current intensity of the pixel is compared to the average intensity of the segmented region. For the second criterion, the intensity difference of the pixels lying on the superpixel sides is compared to the threshold. Once these criteria are successfully checked, the algorithm merges homogeneous superpixels into one region. Then the following superpixels are attached to the final superpixel set. The last step of the proposed method is the spline generation. The spline delineates the borders of the region of interest. The main parameter of the algorithm is the size of a square block. The cardiac MRI dataset of the University of York and the brain tumor dataset of Southern Medical University were used to estimate the segmentation accuracy and processing time. The highest Dice similarity coefficients obtained by the presented algorithm for the left ventricle and the brain tumor are 0.93±0.03 and 0.89±0.07 respectively. One of the most important features of the border detection step is its scalability. It allows implementing different one-dimensional methods for border detection.
algorithms. The watershed segmentation is used as an initial step to 1. Introduction find a seed region.
Joung Park and Chulhee Lee used the seeded region growing
Medical image segmentation is one of the most challenging algorithm for the skull stripping [18]. In that algorithm, a tasks in the field of medical image processing. The segmentation morphological mask was used for the automatic identification of and the subsequent analysis of medical images allow clinicians to the initial seed points of background and foreground. Other regionpredict disease, plan surgery procedures or assess the condition of based methods such as watershed segmentation and morphological internal organs. At the moment, many robust two- and three- segmentation are used in tasks of the skull stripping [8, 23]. dimensional segmentation techniques have been proposed [19, 22, However, many of these approaches have drawbacks, such as 27]. The recent and the most popular articles on medical image oversegmentation and noise sensitivity. segmentation are inextricably connected with machine learning and Nor Isa in paper [13] proposed a modified seed-based region neural networks. Ozan Oktay used neural networks for cardiac growing algorithm. Several important blocks of the algorithm such image enhancement and segmentation in paper [17]. In paper [20] as setting the threshold value, determining the initial seed point, machine learning algorithms are used for brain tumor and the growing process were modified and automated. For segmentation. Similar approaches have been used in many tasks of instance, the automatic determination of the seed point is based on medical image analysis [14, 16]. However, algorithms based on the k-means clustering algorithm. However, the approaches machine learning often solve a narrow problem and require large described in the paper have high computational complexity. This is training datasets. Despite the popularity of machine learning explained by a number of preliminary calculations. For instance, algorithms, common segmentation techniques remain relevant and the k-means clustering algorithm is working with an entire image. keep improving [15, 25]. Semi-automatic image segmentation Jamshid Dehmeshki combined the region growing and the fuzzy techniques are still popular because of their simplicity, a small connectivity region growing approaches in paper [11]. number of parameters, and scalability. Paper [12] shows a modified region growing based on the
Today classical image segmentation techniques (active merging superpixels. A superpixel is a group of pixels combined contours, region growing, watershed segmentation) are used in by a certain feature. The superpixel term was introduced by many semi-automatic image processing algorithms. It is worth Xiaofeng Ren and Jitendra Malik in [21]. The superpixel concept noticing that analysis and processing of three-dimensional images is used in the presented study. However, the major difference of the are still difficult especially in the field of cardiology or brain proposed algorithm is that it does not check every pixel of the imaging. Therefore, there are cases when clinicians use two- superpixel. In general, a number of segmentation algorithms based dimensional planes for the analysis and segmentation. Moreover, on superpixels were proposed before [9, 10, 24]. It should be noted the more popular machine learning algorithms become, the more that the clustering methods are used for a superpixel generation in data they require for training machine learning models. Thus, there most studies. In this approach, each pixel included in a superpixel is a need in an easy-to-use environment for data labeling. Two- should be processed separately, thus causing a relatively high level dimensional segmentation techniques are often used as such of complexity. The complexity of such algorithms is O(n2). A environments. simple linear iterative clustering (SLIC) algorithm is used in studies
In this study, we present a two-dimensional segmentation [12], [20], and [9]. Initially, this method was presented in paper [1], algorithm based on square blocks propagation (SBP). Dana Ballard where Radhakrishna Achanta developed a superpixel-based and Rofl Adams’ algorithms [2, 4] inspired us to develop this segmentation method using k-means clustering for a fivemethod. We also used the approaches described in work [5]. The dimensional feature space. The first three dimensions are the color proposed algorithm is slightly similar to a classical region growing space and the last two are the pixel coordinates. The SLIC and based on the merging of the samples with similar properties of algorithm is a modified k-means clustering algorithm which does the region. not compare each pixel with other pixels in the image. Ovidiu Csillik in paper [10] demonstrated a method based on SLIC
superpixels for a high-resolution segmentation. The paper presents
Most of the articles devoted to the region growing (RG) a processing time of superpixels at different resolutions. This algorithms were presented more than a decade ago. Jun Tang method processes 1347 × 1042 and 3701 × 3301 images for 2 and proposed a method for color image segmentation based on a 26 seconds respectively. combination of the seeded region growing and watershed algorithm As shown above, segmentation algorithms based on [26]. However, there were no modifications or improvements in the superpixels are quite popular. However, most of the considered approaches have a high level of algorithmic complexity. In this 3.3 Square blocks propagation regard, we propose a 2D semi-automatic segmentation algorithm based on a superpixel growing where superpixels have a floating There is no conceptual difference between the classical seeded size. The latter allowed us to achieve better algorithmic region growing and the proposed algorithm. However, the SPB performance. algorithm assumes a translation to the domain of superpixels. This allows reducing the complexity of the algorithm and increasing the 3. Data and methods processing speed. In the proposed algorithm a superpixel represents a square block comprising of the pixels. All pixels inside the block 3.1 Data description have a 4-connected neighborhood by default. The SPB algorithm checks two criteria, described in Section 3.6 in more detail, and
In order to develop and validate the proposed algorithm, we used merges superpixels into one region. Then points lying on open-access datasets. The first dataset was provided by the superpixels borders are used for spline generation. The workflow University of York (York, United Kingdom) and contains 33 of the proposed algorithm is shown below in Fig. 3. subjects [3]. Each subject's sequence consists of 20 frames and 815 slices (256x256 pixels) along the long axis, for a total of 7980 Initialization of Placing of the seed Square images. Two clinicians manually segmented all the images of the the parameters square propagation dataset. The ground truth of the left ventricles' endocardial and epicardial was acquired. dataTsehteinscelcuodneds 3s0o6u4rcTe1o-wfediagthateids cthoentrbarsati-nenthuamnocerddiamtaasgeet.s.TThhies Senarocdhailnpgofionrtsthe Racenrpidteea4rtiiuonnngtiissltsemtpoespt3 Srqeudaurcetisoinze dataset was acquired at Southern Medical University and contains data from 233 patients with three kinds of brain tumors: meningioma, glioma, and pituitary tumor (Guangzhou, China) [6, 7]. The size of MRI images is 512*512 pixels. Examples of the Spline generation Gettinmgatshke final heart and the brain tumor images are shown in Fig. 1.
Both datasets were processed offline on the computer equipped Fig. 3. The workflow of the square blocks propagation algorithm with Intel Core i7-4820K 3.7GHz CPU and NVIDIA GeForce 960 GT using MATLAB (MathWorks, Natick MA).
The main difference between the proposed algorithm and the methods reflected in papers [12, 28] is that the proposed algorithm does not analyze single pixels belonging to superpixels. For instance, the standard region growing algorithm processes all 100 pixels of a 10x10 superpixel. In turn, the presented algorithm processes only 50 out of 100 pixels. Thus, the larger the initial square size is, the higher the algorithm speed is. The concept of the square propagation and the size reducing procedure is shown in Fig. 4.
(a) Propagation using initial size squares (b) Propagation using squares
with the reduced size
Starting from a seed of the region of interest (ROI) the region growing algorithm performs a segmentation. The region is growing due to the connection of the neighboring pixels, which satisfy the criterion of homogeneity. There are two versions of the algorithm: a seeded version with a manual selection of the seed point and an unseeded version with a random seed point. A classical region growing algorithm is conceptually shown in Fig. 2. where f(x) is the intensity of the current pixel, is the arithmetic mean intensity of the region, T is the threshold level. The approach described above is a standard implementation of a region growing included in the final superpixel set. algorithm. The first square center is the starting point chosen manually. A square of a given size is placed around the first point. The diagonals and the sides of the square are checked for the border crossing. If the square does not cross the border of the ROI, it is placed in an crossing the contour of the ROI, creating a list of nodal border two conditions. For the first condition, the intensity of the
shown in Fig. 7. output segmentation mask obtained using spline generation is placed squares, is the threshold level. shown, the blue line has an unusual shape for a cubic spline. The the center pixel of a certain square, is the number of already
Among the entire set of image pixels L, the algorithm finds the lying on the superpixel sides is compared with the threshold. The point where a square block sides or diagonals cross the border of a points. The coefficient, representing a slope of the straight line is set of intersection points P. Each intersection point represents a region. One of the ways to obtain a contour is to construct a regression of these points. However, we did not use a linear spline, as it gives a significant error in constructing the contour borders.
We also refused to use B-splines because they do not pass through the extreme points. The latter is not acceptable since it significantly reduces the accuracy of segmentation. approximation is performed using the method of least squares at 5 calculated as follows: ( ) = |
∑ =1
− ∑ =1 ∑
=1 ∑ =1 2 − (∑ =1 )2
where x is the edge points varied in a certain range (in our case this range is from 1 to 5), y are intensity values, n are positions of the | ≥ Thus, the result of the algorithm is the set of cubic splines edge points.
describing the contours. Such an analytical presentation may be considered that the distance between pixels is the Euclidean. more preferable than representing a segmented area in the form of
For the current pixel, the approximation is done using two pixels on the right and two on the left. If the pixels are in the corner of a superpixel, the additional pixels that slightly exceed the the first square where a number of iterations is equal to 6×N. In this borders of the square block are taken. The slope module allows the regard, the asymptotic complexity of the SBP algorithm is O(n). As algorithm to accurately detect the region borders and makes the shown, the proposed approach moves from the pixel level to the algorithm resistant to noise. Border search is applied on the sides level of the pixel groups and fragments. The latter allows and diagonals of the square blocks using conditions described remarkably reducing the execution time of the algorithm. above. If there is at least one side/diagonal crossing of the region border, the square block is not included in the final set. Thus, the 4. Results time of the algorithm. Another advantage of the proposed solution 4.1 Left ventricle segmentation reliability of the algorithm rises.
As shown in Fig. 8, each square block has six-line segments (AB, BC, CD, AD, AC, and BD). These lines consist of pixels. All that we need to do is to perform a one-dimensional segmentation for each line. This approach significantly reduces the execution is the possibility to apply any set of one-dimensional segmentation methods to a line segment. Therefore, any segmentation method can be implemented in the proposed algorithm as a plug-in for the additional verification of the border crossing. It is worth noticing that if at least one segment has crossed the border of the region, the algorithm does not process the rest of the line segments. The latter allows reducing the algorithm runtime
and increasing the performance of the algorithm by 5 times in the extreme case.
time changed with respect to different sizes of the squares. The
the accuracy assessment.
The left ventricle segmentation of the presented algorithm, region growing algorithm, and the ground truth (GT) manual segmentation is presented in Fig. 9. In the case of patient 2 and patient 3, region growing leaks out through the gaps in the borders of the ROI. This is because the region growing approach processes an image at the pixel domain. In turn, the SPB algorithm avoids the problem of the border gaps.
where N is a number of image pixels, and SF is the size of the smallest segmented object in the image. 3.8
In the case of the region growing, at least N2 steps are required to process a block of N×N pixels. Consequently, the complexity of the region growing is O(n2). Each image pixel is processed separately by the region growing algorithm. For the proposed (a) Square blocks propagation algorithm (blue) vs manual segmentation (cyan) (b) Region growing algorithm (red) vs manual segmentation
(cyan) Fig. 9. Segmentation of the left ventricle using the proposed SBP and RG algorithms in comparison with the ground truth manual
segmentation To test the segmentation accuracy and processing time of the algorithm, a number of iterations for the block size of N×N pixels left ventricle, we used a dataset comprised of 156 slices. The left varies from 3×N to 5×N. However, there is an exceptional case for ventricle segmentation accuracy for different square sizes is shown in Fig. 10 and Table 1. Additionally, the total number of lowaccuracy cases when DSC is less than 0.5 is shown in Fig. 11.
60 50 s se40 a c eg30 a k ea20 L 10 0
SBP 12-6-3 and RG do not differ significantly. However, the DSC interquartile range of SPB with parameters 20-10-5 and 16-8-4 is significantly better than RG’s one. The average accuracy of the SPB algorithm has grown significantly due to the fact that superpixels do not leak through the border gaps.
Better performance of the proposed algorithm is indirectly confirmed by a number of low-accuracy segmentation cases (see Fig. 11). A low-accuracy case is a leakage case or a case with the value of DSC less than 0.5. In 32% of the studied cases, RG leaks through the borders defects what confirms its unreliability.
The brain tumor segmentation of the presented algorithm, region growing algorithm, and the ground truth manual segmentation is presented in Fig. 12. As shown, the region growing algorithm has a problem related to the leakage through the border gaps. In this case, the bone tissue is mistakenly segmented for the three presented patients. Such properties of the image lead to low accuracy of the region growing. In turn, SPB allows configuring the size of superpixels to avoid oversegmentation and then segmenting the tumor successfully. 1 4 6 13 50
brain tumor, we used a dataset comprised of 300 slices. The brain tumor segmentation accuracy for different square sizes is shown in Fig. 13 and Table 2. Additionally, the total number of low-accuracy cases when DSC is less than 0.5 is shown in Fig. 14.
In the case of the brain tumor segmentation, pseudo proportionality between the DSC and the size of the squares is observed. The latter means that the smaller the square size is, the less the DSC value is. It should be noted that the reason for these leaks is not the borders defects. In this case, the tumor has approximately the same level of intensity as external bone tissue.
To compare the propagation speed of the region growing The proposed algorithm has opportunities to improve execution algorithm and the proposed algorithm, a synthetic test image with time, robustness, and final accuracy. All squares are processed a white circle in the center and the black background was generated. independently to each other, so the algorithm can be paralleled on This test image was created in different sizes. The dependence GPU for minimizing execution time. between processing time and image sizes for both algorithms is An important feature of the algorithm is its scalability. It means represented in Fig. 15 and Fig. 16. As seen, both algorithms have that several different algorithms can be used for border detection at asymptotic complexity O(n2) but the region growing algorithm is the same time. We used two criteria: one-dimensional region much slower, and cannot be adapted for optimal speed. growing and intensity gradient check. As an additional method, 3,5 machine learning or one-dimensional neural networks can be applied to the border detection. It should also be noted that the algorithm can be extended for three-dimensional imaging.
The proposed algorithm is devoted to the segmentation of [4] images with high resolution or medical images with ROI border [5] defects and low contrast. Additionally, this algorithm can be [6] [1] [2] [3] 400