Coronary Artery Segmentation Using Edge Operators And Region Growing Technique

Coronary Artery Segmentation Using Edge Operators And Region Growing Technique

S. Sathya

Department of Biomedical Engineering,

Sri Shakthi Institute of Engineering of Technology, Coimbatore

1. Dhivya1, R. Dhanapal 2

   Department of Biomedical Engineering,

   Sri Shakthi Institute of Engineering of Technology, Coimbatore

   AbstractSegmentation of coronary artery is important in the analysis of diseases related to heart and has become an integral part of the medical field. Developing accurate segmentation algorithm is highly challenging, especially when segmenting arteries with large variations in image intensities and with the background noises.This paper, presents a novel technique through which the evaluation of the effectiveness of Region Growing and Edge Detection segmentation algorithms is carried out on a cardiac angiogram frame(s). Before any segmentation process, unwanted noises have to be eliminated in order to enhance the area that is to be segmented. In this paper, a new method is adopted in the pre-processing stage which partially removes background noises like ribcage bones. Two types of edge operator namely gradient and compass operators are implemented in edge detection. In the first segmentation technique, gradient operators are used along with Fuzzy inference system in order to enhance the edges of the given input image. In the next part of edge detection, spatial filtering of the input image is done with compass operators in different orientations.

   KeywordsSegmentation; Edge detection; Region growing; Cardiac CT angiogram

   1. INTRODUCTION

      Cardiovascular disease (CVD) is the most common cause of death. There exists many types of CVD and approximately 40 percent of people are totally affected by it leading to death. Blood pressure, congestive heart failure, stroke, coronary heart disease (CHD) and congenital cardiovascular are included in the types of CVD. Among these, CHD and CAD accounts for approximately 54 and 53 percent of deaths of CVD. Coronary arteries are nothing but those arteries that surround the heart and supplies blood to heart muscles. Coronary artery disease (CAD) is a particular type of heart disease, which disturbs or even terminates the supply of blood to the heart muscles. The restriction of blood supply is due to a block or narrowing of a coronary artery by fatty plaques which is termed as Coronary Atherosclerosis In order to facilitate the diagnosis of such type of coronary artery blocks, cardiac computed tomography angiogram procedure can be performed. Accurate visualization and quantification of blood vessels reflected in cardiac angiogram, aids the physician in many clinical applications related to heart diseases.

      Digital image processing assists in the diagnosis of diseases like image enhancement, image smoothening, reconstruction of image, area calculation of cells or organs in the image, image segmentation etc [4],[21]. Although angiogram aids in diagnosing artery blocks, in certain

      condition it may fail to show accurately the expected result due to poor contrast between the artery and the background, overlapping of blood vessels and the domination of bone shadows [25]. An efficient method has to be developed which can extract or segment coronary arteries, in spite of those difficulties mentioned above. Segmentation is nothing but the partition of an image into segments based on certain properties like image edges, regions etc. Many segmentation approaches are in existence for different images [7],[9],[11] but for complex images like cardiac angiogram [14],[24] a good segmentation algorithm has to be developed [13] and should be evaluated based on its performance by comparing it with other segmentation algorithms [18],[22].

      Even though many segmentation algorithms are in work, it cannot be concluded that all segmentation algorithms are applicable to a certain application. For this reason, this paper presents a novel technique, through which the effectiveness of two different segmentation algorithms namely edge detection [12],[16] and seed region growing [1] can be implemented, evaluated and compared on different angiogram frames.

      Conventionally, edges of an image are detected using some basic first derivative edge detectors or gradient operators like Sobel, Prewitt, Robert, Canny and Laplacian of Gaussian (LOG) [26] .Each edge detector has its own advantage and disadvantage in detecting edges in an image. Simple edge detection cannot offer any kind of useful information from images like cardiac angiogram. So a method has to be introduced that enhances the detection of edges apart from any kind of noises present in the image. Such a method is Fuzzy Inference system, which comprises of fuzzy rules that avoids double edges and reduces noises in the image [2],[3],[5],[14],[15],[23]. These first derivative edge detectors and their segmentation performances are compared with 1) A different edge detection algorithm using compass operators namely Robinson and Kirsch [19]. Here a simple spatial filtering followed by thresholding methods are followed for the coronary artery extraction 2) Region growing algorithm [8],[10]. Both edge detection and region growing algorithms are simple to perform when compared to other segmentation methods.

   2. MATERIALS AND METHODS

      The input is a cardiac CT angiogram and it is preprocessed in order to remove noises and to enhance the image for further processing. In addition to the noise present in the image, background structures like ribcage bones also

      take part in reducing the capability in segmenting the coronary artery. So in pre -processing, the background structures were removed to aid in segmentation in a better way. Along with this, high and low pass filtering are also introduced for further image enhancement. Segmentation algorithms are performed on the image after the pre processing stage .Quality measurement of an image includes both subjective and objective methods. But in this paper, only objective method namely calculation of PSNR, Elapsed time and variance are evaluated for both the segmentation algorithm. The calculated parameters are compared and the

      best segmentation algorithm is brought into the light. The flow diagram of the proposed method is shown in figure 2.1.

      • Fuzzification of the input variables

      • Rule evaluation

      • Aggregation of the rule outputs

      • Defuzzification

      1. Roberts Edge operator

         The Roberts Edge filter is use to detect edges by applying a horizontal and vertical filter in sequence. Final result is obtained by adding the images on which both the filers were applied. The two filters are basic convolution filters of the form.

         Horizontal Filter

         INPUT IMAGE

         0 1

         0

         1

         Vertical Filter

         1

         PRE-PROCESSING

         0

      2. Prewitt Edge operator

         0

         1

         EDGE DETECTION USING FIS

         SEGMENTATION

         EDGE DETECTION USING

         REGION GROWING

         Using Prewitt Edge operator, edges are calculated by using difference between corresponding pixel intensities of an image. All the masks that are used for edge detection are also known as derivative masks. It detects the edges by applying horizontal and vertical filters in sequence and summed to form the final result. The two filters are basic convolution filters which smoothes or averages along the edges with less sensitivity to noises.

         Horizontal Filter Vertical Filter

         COMPASS OPERATORS

         1

         1

         1

         0 1

         1

         0

         0 1

         1

         0

         1

         1 1

         0

         0

         1 1

         QUALITY MEASUREMENT

         EVALUATION &

      3. Sobel Edge operator

      The sobel operator is a derivative mask which is very similar to Prewitt operator and used for edge detection. Like Prewitt operator sobel operator is also used to detect two kinds of edges in an image using two filters. It shows a better smoothing along edges, even less sensitive to noise.

      Horizontal Filter Vertical Filter

      COMPARISON

      Figure 2.1 Flow Diagram

      1

      2

      1

      0 1

      2

      0

      0 1

      1 2

      0

      0

      1 2

      1

      0

      1

      a) Fuzzy Inference System (FIS)

      In the fuzzy logic system, Fuzzy Inference System plays a very important role in decision making. For framing crucial decision rules, it uses IF-THEN rules with the connectors OR or AND. FIS consists of Fuzzifier, Inference Engine, Defuzzzifer which works based on framed rules under knowledge base. The iputs and output of FIS are in the form of Crisp Sets. Among the Fuzzy inference techniques, Mamdani fuzzy Inference process is adopted here which involves four steps,

      1. Kirsch compass operator

         Using Kirsch compass kernel, the strength of image edges are calculated in all 8 directions. Through all 8 compass directions, the operator adopts a single kernel mask and rotates it in 45 degree incrementally: N, NW, W, SW, S, SE, E, and NE. The edge degree of the Kirsch operator is determined as the maximum degree across all directions.

         If NE produces the maximum value, then the edge direction is northeast.

      2. Robinsons compass operator

         It is used in a manner similar to the Kirsch masks, but is easier to implement, as they rely only on coefficients of 0, 1, and 2, and are symmetrical about their directional axis- the axis with the zeros which corresponds to the line direction. It is needed to compute the results on four of the masks; the result from the other four can be obtained by negating the results from the first four.

      3. Region growing

         Since it involves the selection of initial points, it is also known as pixel-based segmentation. This method involves neighboring pixels of initial seed points and decides whether the pixel neighbors should be added to the region. Similar to data clustering algorithms, the method is iterated on. The prime step in region growing is to choose a set of seed points. The choice of seed point relies on some user norms like pixels with even gap on a grid, pixels in a definite grayscale series.

         The initial region begins as the precise location of these seeds. The regions are then grown from these seed points to adjacent points depending on a region membership measures. like pixel intensity, grayscale texture, or color. The image information is important, since the regions are grown on the basis of the measure. Histogram information is needed in order to find the pixel intensity threshold value for region membership measure.

   3. RESULTS AND DISCUSSION

      Using edge detection and region growing algorithms, segmentation process has been implemented on an angiogram image figure 3.1. Here objective method is used to evaluate the performance of segmentation algorithms. In this objective method, Peak signal to noise ratio (PSNR), elapsed time and variance on the processed image are calculated [6],[16],[26].PSNR is calculated between segmented and reference images.

      Using masks, edge detections are performed for both gradient and compass edge operators. In the case of region growing, the reference image is generated using hysteresis thresholding method. Finally PSNR, computational time and variance are calculated. The results in figure 3.2 depicts that

      • Prewitts and Sobel edge operators are greatly affected with noises

      • Most of the edges were lost in edge detection using Roberts edge operator

      • Edge detection using kirschs and Robinsons compass operators has given a good segmented result

      • Region growing method when not compared with edge detection algorithm has given a satisfying result with minimum parameter adjustment but with more variation in intensities. In order to verify the validity of the segmentation results, Table 1 is presented as segmentation result by computing Elapsed time, PSNR (Peak Signal to Noise Ratio) and variance value.

      TABLE 1. EVALUATED VALUES OF SEGMENTATION

      Algorithm	Average PSNR (dB)	Average Elapsed Time (Sec)	Average Variance (No Unit)
      Sobel	46.7764	1874.214	0.068567
      Prewitt	44.9097	1461.523	0.045583
      Robert	37.0180	1821.963	0.00685
      Kirsch	42.5146	4.348469	0.026967
      Robinson	51.2922	4.092425	0.03175
      Region Growing	50.2964	35.17473	0.175083

      FIGURE 3.1: a) Input image b) Filtered image c) Partially background removal d) Contrast enhancement e) High pass filtering f) Low pass filtering

      FIGURE 3.2: Segmented results for a single angiogram image

      a) Prewitt b) Sobel c) Robert d) Kirsch f) Robinson and g) Region

      growing

   4. CONCLUSION AND FUTURE WORK

From the results provided, a conclusion can be framed that unless or otherwise the input image has sharp edges in the absence of noise, the segmented result cannot reach its perfection. But it is impossible to find such medical images with the above said criteria for its processing. So in addition to segmentation, quantitative assessment of the segmentation algorithms have also been performed on the image using required parameters. In objective assessment, edge detection using Robinsons compass operator provides the best result

1. with an average PSNR value, less computational time and with less variance.The major research directions that can be pursued and improvements to be made in the future segmentations are

   • Noise reduction in medical images

   • Accurate edge detections with minimum errors in the boundaries

   • Continuous edge detection in images

   • Local blood vessel contrast enhancement for automatic region growing segmentation

   • Edge based automatic region growing segmentation REFERENCES

1. Ahmed R. Khalifa Evaluating The Effectiveness Of Region Growing And Edge Detection Segmentation Algorithms Journal of American Science 2010;6(10)

2. A.A.Alshennawy, A.A.Aly,"Edge Detection in Digital Images Using Fuzzy Logic Technique", World Academy of Science, Engineering and Technology 51 2009.

3. Abdallah A. Alshennawy, and Ayman A. Aly Edge Detection in Digital Images Using Fuzzy Logic Technique World Academy of Science, Engineering and Technology 51 2009

4. Kanitsar A,Wegebkitil R,Felkel P,Fleischmann D,SAndner D,G Roller E: Com-puted Tomography Angiography: A Case Study of Peripheral Vessel Investigation. In Proc. of IEEE Visualization (2001), pp. 477 480.

5. Chunliang Wang and Orjan Smedby. Coronary artery segmentation and skeletonization based on competing fuzzy connectedness tree. Med Image Comput Comput Assist Interv Int Conf Med Image Comput Assist Interv, 10(Pt 1):3118, 2007.

6. S.CHABRIER, H.LAURENT, AND B.EMILE 2005 Performance evaluation of Image Segmentation Application to Parameters fiting

7. Cemil Kirbas and Francis K.H. Quek A review of vessel extraction techniques and algorithms Nov-2002

8. Daniel S.D. Lara and Alexandre W.C. Faria and Arnaldo A. de Albuquerque A Semi-Automatic Method for Segmentation of the Coronary Artery Tree from Angiography

9. J. Goldberger, H. Greenspan, and S. Gordon.Unsupervised image segmentation using the information bottleneck method. In Proc.DAGM, 2002.

10. 10.Hennemuth, T. Boskamp, D. Fritz, C. Kuhnel, S. Bock, D. Rinck,

    M. Scheuering, and H. O. Peit-gen. One-click coronary tree segmentation in ct angiographic images. International Congress Series,1281:317321, 2005.

11. 11.G.A.Hance,S.E.Umbaugh, .H.Moss,and W.V.Stoecker

    ,unsupervised color image segmentation with application to skin tumor borders,IEEE Eng.Med.Biol.Mag,vol no 1,pp.104-111,1996.

12. 12.Jun Li,.A Wavelet Approach to edge detection.,Thesis work, University of Sam Houston, August 2003.

13. 13.Lo Kwee-Seong, "Image Segmentation Methods for Detecting Blood vessels in Angiography,"Conf. ontrol,Automation, Robotics and vision Singapore, December 2006

14. 14.Masoomeh Ashoorirad and Rasool Baghbani Blood Vessel Segmentation in Angiograms using Fuzzy Inference System and Mathematical Morphology 2009 International Conference on Signal Processing Systems

15. 15.Mark S. Nixon, and Albreto S. Aguado., Feature Extraction & Image processing, second edition, Elsevier Ltd,2008.

16. 16.D. Martin, C. Fowlkes, D. Tal, and J. Malik, A Database of Human Segmented Natural Images and Its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics, Proc. Intl Conf. Computer Vision,2001.

17. 17.C.Pantofaru And M.Hebert- 2009 A comparison of image segmentation algorithms

18. 18.Rivest Jean, "Morphological Operators on Complex Signal," signal processing, vol. 84, pp. 133-139, January 2004.

19. 19.Sudeep K C and Dr. Jharna Majumdar A Novel Architecture for Real Time Implementation of Edge Detectors on FPGA IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 1,

    January 2011 193 ISSN (Online): 1694-0814 www.IJCSI.org

20. 20.Salem Saleh Al-amri et. al. Image segmentation by using edge detection / (IJCSE) International Journal on Computer Science and Engineering Vol. 02, No. 03, 2010, 804-807

21. 21.Shoujun et al. BioMedical Engineering OnLine 2010, 9:40 http://www.biomedical-engineering-online.com/content/9/1/40

22. 22.Scherl, H., Hornegger, J., Prummer, M., Lell, M., \ Semi- Automatic Level-set Based Segmentation and Stenosis Quantification of the Internal Carotid Artery in 3D CTA Data Sets", Medical Image Analysis, In Press, (2006)

23. 23.Timothy J. Ross. , Fuzzy Logic With Engineering Applications, second edition, John Wiley Ltd, 2005.

24. 24.Tanaka, N., Ehara, M., Surmely, J-F., Matsubara, T., Terashima, M.,Tsuchikane, E., Katoh, O., and Suzuki, T., \ Sixty-Four-Multislice Computed Tomography Image of a Ruptured Coronary Plaque",

    Circulation, (2006) 114,pp. 519-52

25. 25.Til Aach and Claudia Mayntz and Peter Rongen and Georg Schmitz and Herman Stegehuis Spatiotemporal Multiscale Vessel Enhancement for Coronary Angiograms. Medical Imaging 2002: SPIE Vol. 4684 February 2228 2002 10101021

26. 26.T. Venkat Narayana Rao Statistical Analysis for Performance Evaluation of Image Segmentation Quality Using Edge Detection Algorithms Int. J. Advanced Networking and Applications 1184 Volume: 03; Issue: 03; Pages:1184-1193 (2011)