Abstract: This research proposes and implements a novel approach that integrates region and edge information for segmenting 2D Computed Tomography Image sequence. Subsequent to operation by Gaussian Filter and Edge Detection, the seed value is then calculated by transforming the image from spatial domain to frequency domain. The region is then grown from the seed value by appending each pixel into its region at successive iterations. The speed is increased by parallel region growing process. This approach is fully automatic and does not need manual intervention. The segmented image sequence finds further use in reconstructing a 3D model.
INTRODUCTION
This research proposes and implements a novel approach that integrates region and edge information for segmenting 2D Computed Tomography Image sequence. The cumbersome task of manual or interactive seed generation is overcome in this research work. This research uses automated methods for seed generation, which is accomplished by utilizing the strength of the Discrete Cosine Transform (DCT). Hence segmentation of 2D Computed Tomography (CT) image sequences is done successfully and automatically.
Previously, 2D CT image segmentation was done only on images individually. If segmentation needs to be done on another CT image, then it has to be chosen, segmented and the process continues. But, in this research work, attempts have been made to segment an entire CT image sequence, and it has also been very successful.
The actual difficulty arose in availability of published literature, because this research was one of the very first attempts at automatic segmentation of entire 2D CT image sequences using extensive hybrid techniques. Hence, studies were made on literature which was available. Their strengths and weaknesses were assessed and a new comprehensive technique for Automatic Seed Generation Using Discrete Cosine Transform For 2D Region Growing Segmentation of Computed Tomography Image Sequence was proposed and implemented.
STUDY OF PREVIOUS METHODS
Segmentation plays a vital role in image processing which partitions an image into homogeneous and disjoint regions. Marr and Hildreth (1980) has been one of the earliest papers on Segmentation. The primary goal of segmentation is to decompose an image into constituent regions which should be meaningful for further processing and certain application. Generally Image segmentation algorithms (Haralick and Shapiro, 1985) are based on one of two basic properties of intensity values: Discontinuity and Similarity (Sahoo et al., 1988).
The principal approach in the first category is to segment the image based on abrupt changes in the intensity. In the second category, the approach is to partition the image into regions that are similar according to some predefined criteria. Point detection, Line detection and Edge detection (Soltanian-Zadeh et al., 1992; Hu et al., 2001) are the three basic types of gray level discontinuities. A common way to detect discontinuities is to run a mask through the image. Thresholding (Pathak et al., 2000; Cocquerez and Philipp, 1995; Lu et al., 2003) and Region processing (Kang et al., 2003) segmentation methods are based on similarity criteria. These three discontinuity processes and two similarity processes are briefly outlined in the following paragraphs.
Point detection: An isolated point has been detected using the mask at the location on which the mask is centered. The idea is that an isolated point will be quite different from its surroundings and can be detectable by this type of mask.
Line detection: If a mask is applied and moved around an image, it would strongly respond to lines oriented horizontally, vertically or in certain direction. With a constant background, the maximum response would result when the line passed diagonally or through the middle row or column of the mask.
Edge detection: It is the most common approach for detecting discontinuities in the gray level. Edge is a set of connected pixels that lie on the boundary between two regions (Lu et al., 2003). Edges can be detected using first and second order derivatives.
Thresholding: A common and simplest of all thresholding techniques is to apply a threshold value T and segmentation is then accomplished by scanning the image pixel by pixel depending on whether the gray level of that pixel is greater or less than the value of T. Thresholding may be Global, Local or Adaptive depending on the goal of segmentation. If the value of T depends only on the image then it is called Global thresholding. If T depends on both the image and any point with in the image then it is known as Local Thresholding. In addition if the threshold value T depends on the spatial coordinates of the image, then it is adaptive thresholding.
Region based: The objective of this type of segmentation is to partition an image into regions. Region based approaches are of two types such as Region Growing (Pohle and Toennies, 2001) and Region splitting and merging. Region Growing: It is a procedure that groups the pixels or subregions into larger regions based on some predefined criteria. The basic approach is to start with a set of seed points and from these grow regions by appending the neighboring pixels to each seed points that have properties similar to the seed. It can also be further subdivided into Seeded Region Growing in which the seeds are given externally by the user and Unseeded Region Growing, in which the seeds are generated automatically according to some predefined criteria. Region splitting and Merging: It is an alternate to region growing in which an image is subdivided into a set of arbitrary, disjoint regions and then merge and/or split the regions in an attempt to satisfy certain conditions.
Previous hybrid methods: Despite of the conventional methods there are also certain hybrid methods aiming at an optimal combination of the advantages offered by the previously mentioned basic approaches available for segmentation. These methods combine either the edge and region methods or threshold and region methods or edge and threshold approaches.
DIFFICULTIES IN EARLIER METHODS
There are a number of known issues associated with existing methods. Some of these which makes the segmentation process unsuccessful has been pointed below.
The methods based on discontinuities in gray level criteria especially edge-based needs post processing such as edge linking.
In threshold based segmentation if the approach is semi automatic then user should have the prior knowledge about the entire process. Several automatic threshold selection methods exist, but they usually require bi-peak or multipeak histograms, which may not be applicable in many cases.
Descriptors alone can yield misleading results if connectivity or adjacency information is not used in the region growing process. Another problem in the region growing is stopping rule. In seeded region (Glocker, 2004) user-based seed specification allows information to be extracted about the localisation of the region of interest in complex images where multiple anatomic structures are visible.
A good segmentation result depends on a set of correct choice for the seeds. When the input images are noisy, the seeds may fall on atypical pixels that are not representative of the region statistics. This can lead to erroneous segmentation results.
A number of implementations of SRG only approximate the behavior of the original algorithm. This can result in scan-order dependencies and can have significant impacts on small regions.
The seed selection process in itself requires manual interventions, and is error-prone. Even though automatic segmentation can be achieved in a limited sense, it is application specific and will require domain-specific knowledge and training sets.
The hybrid segmentation method described in (Pohle and Toennies, 2001) combines local adaptive thresholding with region growing for the detection of skeletal structures in CT image sequences. This method requires user interaction as well as continuous input image sequences, with no missing slice and a minimal slice thickness.
The hybrid method presented by Gonzalez and Woods, ( 2002) combines adaptive region growing with a homogeneity model. Their algorithm is rather slow, consisting in two steps:
| • | The homogeneity criterion is learned from the global image appearance |
| • | The region of interest is grown around a user-specified seed pixel. |
A segmentation technique for 2-D Magnetic Resonance images of liver tumours is presented by (Lin et al., 2000). This technique integrates edge and region information in order to detect textured liver tumours with blurred boundaries of non-uniform sharpness.
NEW HYBRID SEGMENTATION METHOD
This research work proposes a new hybrid segmentation method, which combines the threshold, edge and regions methods effectively to obtain accurate and successful segmentation. This method is better than the previous methods which combine only two of the three methods in any permutation or combination.
This method effectively combines the strengths of all the three methods, namely, threshold, edge and region methods to obtain accurate and successful segmentation.
Briefly it can be said that in this new method, thresholding is applied to detect the edge and the edge is preserved to calculate the seed value from which the region growing process can be established.
EXPERIMENTS AND RESULTS
The new method proposed in this paper consists of the following steps.
Step 1: Gaussian smoothing: Smoothing filters are used for blurring and for noise reduction. Blurring is used to remove small details from an image prior to large object extraction and bridging of small gaps in lines or curves. Noise reduction can be accomplished by blurring with a linear filter. The linear filter applied in this method is the Gaussian filter in which the output is simply the average of the pixels contained in the neighborhood of the mask.
It is sometimes useful to apply a Gaussian smoothing filter to an image before performing edge detection. By using a small Gaussian filter and then applying an edge detector, see a great deal of fine detail can be achieved. The filter can be used to soften edges, and to filter out spurious points (noise) in an image. Gaussian smoothing can be achieved by convolution. Since the image is stored as a collection of discrete pixels a discrete approximation has to be produced to the Gaussian function before performing the convolution. Convolution can be defined as modification of a pixel value depending on the neighbors and can be achieved by applying a kernel. The size of the kernel applied in this method is a 5x5 kernel. Once the suitable kernel has been calculated the 2D-convolution can be achieved by first convolving with a 1-D Gaussian in the x direction, and then convolving with another 1-D Gaussian in the y direction since the Gaussian is in fact the only completely circularly symmetric operator, which can be decomposed in such a way.
The Gaussian outputs a weighted average of each pixel's neighborhood, with the average weighted more towards the value of the central pixels. Because of this, a Gaussian provides gentler smoothing and preserves edges.
Step 2: Thresholding: Thresholding plays a central role in applications of image segmentation. Suppose an image is composed of light objects on a dark background, in such a way that object and background pixels have gray levels grouped into two dominant modes. One obvious way to extract the objects from the background is to select a threshold that separates these modes.
The thresholding technique implemented in this paper is a Global Thresholding in which the image is traversed on a pixel by pixel basis. The average value of first and second pixel is calculated and the same is repeated for all the pixels in the image. The mean value is then calculated for all the average values and the value is assigned as a threshold value which is used to detect the edge. This type of segmentation can be expected to be successful in highly controlled environments. It is often used in the areas where control of illumination is usually feasible.
Step 3: Laplacian of gaussian based edge detection: Edges are formed from pixels with derivative values that exceed a preset threshold. Thus, the idea of an edge is based on a measure of graylevel discontinuity at a point. Laplacian of Gaussian together with the zero crossing of the second derivative is employed to detect the edge. i.e., The Laplacian is combined with smoothing as a precursor to find edges via zero crossings.
In most applications, the second order derivative is better suited than the first order derivative because
| • | It has the ability to enhance fine detail. |
| • | It produce a double response at step changes in gray level. |
| • | The sign of the second order derivative can be used to determine whether an edge pixel lies on the darker or lighter side of an image. |
An imaginary straight line joining the extreme positive and negative values of the second order derivative would cross zero near the midpoint of the edge. This zero crossing property of the second order derivative is quite useful for locating the centers of thick edges.
There are several reasons for using zero crossing property instead of original Laplacian form in edge detection such as:
| • | As a second order derivative, the Laplacian is sensitive to noise |
| • | Double edges are produce by the magnitude of the Laplacian |
| • | Unable to detect the direction of edge with its originality. |
For these reasons the role of Laplacian consists of using Zero crossing property for edge location. Thus the purpose of the Gaussian function in the LOG formulation is to smooth the image and the purpose of Laplacian operator is to provide an image with zero crossings used to establish the location of the edges in the image.
The edge pixels seldom characterize an edge completely because of noise, breaks in the edge from non-uniform illumination and other effects that introduce spurious discontinuities. Thus edge detection should be followed by linking to arrange pixels as meaningful edges. The two principal properties used for establishing the similarity of edge pixels are
| • | The strength of the response of the gradient operator used to produce the edge pixel and |
| • | The direction of the gradient vector. |
A point in the predefined neighborhood of (x, y) is linked to the pixel at (x, y) if both magnitude and direction criteria are satisfied. This process is repeated at every location in the image. A record of linked points must be kept as the center of the neighborhood and is moved from pixel to pixel. A simple bookkeeping procedure is to assign a different gray level to each set of linked edge pixels.
Step 4: Unseeded Region Growing (URG): URG is a technique, which is similar to SRG that is already discussed in this paper with the only difference where no explicit seed selection is necessary. The basic idea is suppose the process starts with a single pixel p and wish to expand from that seed pixel to fill a coherent region. A Convergence criteria S(i, j) has to be defined, such that it produces a high result if pixels i and j are similar and a low one otherwise. First, consider a pixel q adjacent to pixel p. We can add pixel q to pixel p’s region iff S (p, q)>T for some threshold T. Then the same steps are repeated to the other neighbors of p and do likewise. Suppose that S(p, q)>T and we added pixel q to pixel p’s region. Similarly consider the neighbors of q and add them likewise if they are similar enough. If this is continued recursively, a few unanswered questions to address may rise such as
| • | How a similarity measure is defined? |
| • | What threshold T can be used? Does it change or stay constant? |
The answers for these questions are discussed in this paper in the section where similarity measure is discussed and in the section where constant thresholding is discussed.
Seed value generation: Region growing techniques are bottom-up methods and consist in pixel aggregation around an initial set of seed pixels. The correct specification of the seed pixels is essential for the success of the approach. Choosing the wrong seeds may compromise the following process, since the similarity of the pixels to be aggregated is first computed with respect to the seed.
Seed value can be calculated using the Discrete Cosine Transform (DCT). DCT helps separate the image into parts of differing importance (with respect to the image's visual quality). It transforms a signal or image from the spatial domain to the frequency domain. The application of DCT in an image produces the output in sinusoidal waveform. The average of maximum and minimum value within the boundary is calculated and is assigned as the initial seed value. Once the seed value is calculated the image is transformed into spatial domain using inverse DCT.
Labelling of disjoint regions: Most of the seed pixels are distributed in small sized regions. Therefore, a labelling of compact seed regions is performed prior to the beginning of the pixel aggregation. The compactness of the seed regions is evaluated with respect to the 4-connectivity of adjacent pixels. After the initial labelling process, a set of compact and disjoint regions are generated.
Defining the convergence criterion: As for the seed specification is concerned, the convergence criterion is essential for the success of the region growing process. Usually, this criterion is a function related to a similarity threshold computed between the currently evaluated candidate and the corresponding instance of the growing region. The iterative pixel aggregation algorithm for a given labeled region stops when there is no candidate pixel that satisfies the similarity threshold. The convergence criteria employed in this approach is the minimum difference minimum difference between the gray level of the pixel the average gray level of its assigned region.
Pixel aggregation: The segmentation process formally initializes with region R1_ containing a single image pixel, and the running state of the segmentation process consist of a set of identified regions R1_, R2_, R3_ Rn_. Let U-be the set of all unallocated pixels which borders at least one of these regions. The value of U can then be calculated by the following equation
where N (p). $ are immediate neighboring pixels of point-Further, a difference measure can be defined as
where g (p) denotes the image value at point p_ and i I is an index of the region such that !N(p) intersect Ri. The growing process involves selecting a point pε U and region Rj where jε [1, n] such that
If δ(Z1Rj) is less than the predefined threshold, then the pixel is added to Rj. Otherwise, similar region R must be chosen such that
If δ(Z1R)< Threshold value then the pixel is assigned to R. If neither of these two conditions above apply, then it is apparent that the pixel is significantly different from all the regions found so far, so a new region, Rn+1 would be identified and initialized with point Z J . In all three cases, the statistic of the assigned region must be updated once the pixel has been added to the region. The URG segmentation procedure is inherently iterative, and the above process is repeated until all pixels have been allocated to a region. For convenience, the initial starting point has been chosen to be the first image pixel, but preliminary investigations have suggested that the starting position does not have a significant influence on the segmentation result.
Best candidate selection: At a given iteration of the pixel aggregation, only one pixel is inserted in every labelled region of the image respectively. This pixel represents the best candidate among all current candidates image. To be a candidate, a pixel must satisfy the following conditions
| • | It does not already belong to a labelled region |
| • | It is adjacent to an instance of a labelled region with respect to the 4-connectivity |
| • | The convergence criterion is not yet satisfied. |
To ensure correct behavior with respect to the homogeneity criterion, the region growing operation requires the determination of the best pixel each time a region statistic is changed. This would be an extremely expensive operation if the δ values for all pixels in U are re-evaluated and the priority queue resorted. The method is to arrange the pixels in a structure that permits rapid search for the best pixel. A combination of splay queue and heap structure has been used to keep track of all pixels currently under consideration. The queue is essentially a binary tree containing candidate pixels of each region, sorted by the pixel intensity value. Each node of the binary tree stores pixels with the same intensity in a FIFO queue. The search for best pixels of the region (pixels that are closest to the region statistic) resorts down to a simple binary search.
When selecting the global best pixel, the set of best candidate pixels for each region are found with their δ values calculated. These regional pixels are stored in a global priority queue, implemented as a heap, with priority dependent on δ. The best pixel over all regions is then simply the candidate pixel that has the smallest δ to its assigned region.
Once the global best candidate has been selected, it is removed from the priority queue and added to an appropriate region. The statistic of the corresponding region is then updated, and neighbors of that pixel added to the regional queue. New regional candidate pixel is found and added to the global queue. The above process will repeat until all pixels have been classified.
It is interesting to note that the hierarchy of the data structure used in this paper implies smaller queues that only needs to be changed when their associated region changes. The size of the global queue is dependent on the number of regions, which will typically be small. Scan order dependency can be eliminated by processing all pixels with the same priority in parallel, and updating the region statistics only when a pixel comes out of the queues with a different value.
The pixel aggregation processes are parallel and independent for every labelled region. However, the iterative evolution of the processes may result in the merging of one or more labelled regions. Moreover, this merging phenomenon is predictable, since at the initial step of the process, every structure in the image was represented by a set of disjoint seed regions. At the convergence of the region growing algorithm, we expect to obtain a pair wise correspondence between the structures present in the image and the labelled regions.
If merging of two regions occurs at a given iteration of the pixel aggregation process, the two regions will receive the same label for the next iteration and will be further considered as one region. Consequently, the number of labelled regions decreases while advancing in the pixel aggregation process. The global convergence of the parallel region growing algorithm is reached when every local convergence criterion for the labelled regions is satisfied.
Experiments were done and the results obtained were accurate. 2D CT scan image sequence which are 256x256, 8-bit gray scale images with intensity values scaled into the range (0, 1) were used. A few sample input CT images 1-4 and output CT images 1-4 are shown in Fig. 1-8.
| Fig. 1: | Input Image 1 |
|
| |
| Fig. 2: | Input Image 2 |
| Fig. 3: | Input Image 3 |
| Fig. 4: | Input Image 4 |
| Fig. 5: | Segmented Image 1 |
| Fig. 6: | Segmented Image 2 |
| Fig. 7: | Segmented Image 3 |
| Fig. 8: | Segmented Image 4 |
STRENGTH OF THE NEW PROPOSED HYBRID SEGMENTATION TECHNIQUE
It has been observed that the time taken to segment a data set containing 60 slices is less than a minute. In a Windows-95, Pentium II MMX processor, 356 MB of uncompressed hard disk and 32 MB RAM. This proves that the time taken to segment an image is in milliseconds.
This has been the real success of the new proposed technique. The New proposed hybrid segmentation technique is able to segment an entire CT image sequence, consisting of 60 images in less than a minute. Ofcourse, the configuration of the computer was also low, and the computer was not a high end system. If the new proposed hybrid segmentation technique is capable of segmenting an entire CT image sequence consisting of 60 images in less than a minute, using a low configuration computer, then, it can surely accomplish successful accurate segmentation in lesser time in high configuration computer systems. This is the real strength of the new proposed hybrid segmentation technique.
CONCLUSIONS
In this study a fully automatic, fast and robust 2D CT segmentation technique has been proposed and implemented.
This method yields excellent performances when compared to manual segmentations performed by radiologists.
Also, the new proposed hybrid segmentation technique is able to accomplish very fast segmentation time and also yield accurate segmentation results over entire CT image sequences (comprising 60 images in every sequence).
Moreover, the sequences of segmented images can also be validated by reconstructing a 3D model.
This approach is task-oriented and handles all types of CT images. The future work is to make this method, easily adaptable for the segmentation of other types of volumetric medical images and to reconstruct a 3D model which will also be useful for surgical planning.
ACKNOWLEDGMENT
The authors express their heartfelt thanks to The Management, The Secretary and Correspondent, The Administrative Director and The Principal of Velalar College of Engineering and Technology, Erode, India for their patronage and encouragement to this Research Work.
The authors also wish to thank all those who helped in this Research.