Design Of Dijkstra Shortest Path Algorithm For Automatic Vessel Segmentation In Support Of Eye Image Classification

Design Of Dijkstra Shortest Path Algorithm For Automatic Vessel Segmentation In Support Of Eye Image Classification

Miss. Priti K. Doad Prof. Satish J. Alaspurkar

Department of CSE, Department of CSE, G.H.Raisoni College, Amravati G.H.Raisoni College, Amravati

Abstract

This paper presents a methodology for extracting the vascular network in the human retina using shortest-path algorithm. Segmentation of anatomical and pathological structures in ophthalmic images is crucial for the diagnosis and study of ocular diseases. However, manual segmentation is often a time- consuming and subjective process. This paper presents a method for automated segmentation of the vasculature in retinal images. The method produces segmentations by classifying each image pixel as vessel or non- vessel, based on the pixels feature vector. Given method preserves vessel thickness, requires no manual intervention, and follows vessel branching naturally and efficiently. To test this method by using a retinal video indirect ophthalmoscopy (VIO) image database from paediatric patients and compared the segmentations achieved by new method. The experimental results show that algorithm outperforms for both single VIO frames and automatically generated, large field-of-view enhanced mosaics. After this work the new criteria function is develop which gives output according that the given eye image is defective or not.

1. Introduction

   Diabetic retinopathy (DR) is the leading ophthalmic pathological cause of blindness among people of working age in developed countries. The estimated prevalence of diabetes for all age groups worldwide was 2.8% in 2000 and 4.4% in 2030, meaning that the total number of diabetes patients is forecasted to rise

   from 171 million in 2000 to 366 million in 2030.Manual segmentation of retinal images is not only demanding for experts and excessively time-consuming for clinical use, but is also inherently subjective, and different annotators often yield different results. To address these difficulties, different approaches for automated segmentation of retinal vessels have been tried, with varying levels of success.

   Automatic segmentation of blood vessels in retinal images is very important in early detection and diagnosis of many eye diseases. It is an important step in screening programs for early detection of diabetic retinopathy [8], registration of retinal images for treatment evaluation [3] (to follow the evaluation of some lesions over time or to compare images obtained under different conditions), generating retinal map for diagnosis and treatment of age-related macular degeneration [5], or locating the optic disc and the fovea [4].Accurate segmentation and evaluation of the anatomical and pathological features of retinal vessels are critical for the diagnosis and study of many ocular diseases. These include retinopathy of prematurity (ROP). ROP is a disorder of the retinal blood vessels that is a major cause of vision loss in premature neonates [8]. Important features of the disease include increased diameter (dilation) as well as increased tortuosity (wiggliness) of the retinal blood vessels in the portion of the retina centered on the optic nerve (the posterior pole). Increased dilation and tortuosity of the blood vessels in the posterior pole (called pre-plus in intermediate, and plus in severe circumstances) is an important indicator of ROP severity [3].

2. Literature Review

   Manual segmentation of retinal images is not only demanding for experts and excessively time-consuming for clinical use, but is also inherently subjective, and different annotators often yield different results [4]. To

   address these difficulties, different approaches for automated segmentation of retinal vessels have been tried, with varying levels of success. Prior methods can be roughly classified into region- and path-based methods. Region-based methods [6,7,11,15], S. Chaudhuri, S. Chatterjee, N. Katz, M. Nelson, and M. Goldbaum proposed Detection of blood vessels in retinal images using two-dimensional matched filters with the help of Region-based methods classify image pixels directly into vessel and non-vessel pixels. . E. Ricci and R. Perfetti proposed method of classification Retinal blood vessel segmentation using line operators and support vector classification[6], Classification relies on local appearance, as measured by the responses of suitable filter banks at various scales and orientations[7,11]. In unsupervised region-based approaches, these filter responses are combined into a new image, which is then appropriately threshold to yield the final classification. Methods in this category employ, matched filters [15] develop by S. Chaudhuri,

   1. Chatterjee, N. Katz, M. Nelson, and M. Goldbaum,

   2. Chanwimaluang and G. Fan used An efficient blood vessel detection algorithm for retinal images using local entropy thresholding [10], local entropy [9] by M. Cree, D. Cornforth and HF. Jelinek , and quadrature filters [13]. Supervised region-based methods, on the other hand, assemble the filter responses into feature vectors that are fed to a classifier, which is trained on hand-labeled data. Techniques used within this framework include ridge detection [14], Gabor wavelet filtering [10], Retinal Blood Vessel Segmentation Using Line Operators and Support Vector Classification [6] proposed by E. Ricci and R. Perfetti, This method is based on concept of two orthogonal line detectors along with the grey level of the target pixel to construct a feature vector for supervised classification using a support vector machine. And moment invariants [9]. Other region-based approaches have used region growing [2], mathematical morphology.

   The goal of path-based methods[1] proposed by Rolando Estrada, Carlo Tomasi,1 Michelle T. Cabrera, David K. Wallace, Sharon F. Freedman and Sine Farsiu, on the other hand, is primarily to trace the centerline of individual vessels, rather than classifying every pixel in the image. Many path-based approaches also estimate vessel thickness as they track each branch, generally by determining the width of the cross-section perpendicular to the current path. Prior work on two dimensional branch extractions has addressed this topological ambiguity semi-automatically by relying on user-supplied points, requiring either a single seed point or a pair of start and end-points. User-supplied one-point methods generally employ ridge detection

   based on differential geometry, while two-point methods find a path between the points that minimizes a cost measure designed to penalize paths that stray from the middle of a vessel. These are all related work about this paper.

3. System Development

   1. Existing System

      This algorithm specially uses shortest path algorithm with explorer the each and every vessel network in a human eye. The working of algorithm shown in Figure1 below,

      Figure 1: Working of Dijkstra forest segmentation algorithm [1]

      The current work represent each VIO image (or composite) as a graph of nodes, G = (V, E), where each node corresponds to a pixel and the links connecting the nodes are called arcs. In this formulation, the ordered pair of node and arc sets is represented by V and E, respectively. Path-based methods for vessel extraction define the cost of traversing the arc that connects any two neighbouring pixels in the image in such a way that arcs between vessel pixels are more likely to have lower cost. Vessel extraction then looks for paths that traverse the image from neighbour to neighbour and have minimum aggregate cost, an are thereby likely to follow vessels. If the cost aggregation rule is associative, minimum-cost paths can be found efficiently we depart from previous work within this framework in two major ways. First, we find vessel regions, rather than simply vessel paths. In other

      words, we preserve vessel thickness, rather than merely finding the skeleton, or centreline, of each vessel. This is important, because eye disease diagnosis often requires consideration of vessel thickness. Second, we employ a sequence of searches for vessel regions that start at source points s0, s1 . . Automatically selected in decreasing order of their likelihood to be part of a vessel. This novelty eliminates the need for a user to select vessel starting points by hand. Thus, we use the single-source, multiple-destination version of Dijkstra shortest path algorithm [13], rather than the single- source, single-destination version used in prior work. In other words, rather than connecting a start point with a destination point, our method explores the image outward from an (automatically selected) source point. This exploratory strategy has two advantages: it eliminates the need for selecting a destination point manually, and it finds vessels as tree-like image regions, thereby accounting for vessel branching naturally and efficiently. The computational cost of this important change of perspective is trivial, as the only difference between the single-destination and multi- destination algorithms is when they stop: The single- destination algorithm stops when it reaches the designated vertex, while the multi destination algorithm stops when a target threshold on the path cost has been reached. Both versions of Dijkstra algorithm have the same computational complexity of O (|E|+|V| log |V|), where | · | indicates the cardinality or size of a set. This complexity is achievable with a heap based priority queue implementation.

   2. System for Proposed Work

      In this paper, the work is to propose a hybrid method that extends the path-based methodology into a region- based segmentation scheme for detecting retinal vessels and then apply some criteria function to classify the faulty eye funds images so that the one can differentiate and classify the image as defective or not. This paper complete approach works in three main stages. The input image is selected from image dataset which is used as input image for first stage image enhancement the input image to remove motion artifacts, and to construct a high-contrast vessel map. The second stage builds a forest of tree-like vessel regions through a sequence of exploration waves on the vessel map: the most vessel-like pixel s0 in the image is used as the starting point for an exploration wave that searches for the best tree-like vessel region in the image around s0 by means of the single-source, multi-destination version of shortest path algorithm. This exploration returns an entire tree region for part of the vessel system, that is, it handles branching naturally and

      efficiently, and preserves vessel thickness. In third stage generating the criteria function using some eye properties like tortuosity, blood cloth in vessel, thickness of vessel can be considered as the criteria function for classifying the defective images from normal eye images.

      The researcher work up to the segmentation phase and taking that into consideration no one up-till suggested such method which based on classification of defective eye using vessel segmentation that would be the one of the criteria for classifying the normal eye images from the defective one. Alone this is not only one criteria that can provide the output to my system. The criteria function are-

      • Blood clots in vessel.

      • Tortuosity of eye.

      • Thickness and abnormal growing of eye vessels. My proposed work is shown in Figure 4.2 as,

        Figure 2: Working of proposed System

        In this paper, we propose a hybrid method that extends the path-based methodology into Region-based segmentation scheme for detecting retinal vessels. Our complete approach works in two stages, as illustrated in Fig. 1. The first stage pre-processes the input image to remove both lens and motion artifacts, and to construct a high-contrast vessel map. The second stage builds a forest of tree-like vessel regions through a sequence of exploration waves on the vessel map: the most vessel- like pixel s0 in the image is used as the starting point for an exploration wave that searches for the best tree- like vessel region in the image around s0 by means of the single-source, multi-destination version of Dijkstra shortest path algorithm [13]. This exploration returns

        an entire tree region for part of the vessel system, that is, it handles branching naturally and efficiently, and preserves vessel thickness. When this exploration ends, a new exploration begins at the best remaining starting point s1 in the unexplored part of the image, which yields a new vessel tree region. Our method stops constructing new regions when the best unexplored starting point is no longer likely to be part of the vessel system. Unlike existing single-source, single- destination vessel analysis methods [1, 2, 9], our single-source, multiple-destinations approach automatically explores the complete vasculature in a retinal image, and requires no user intervention whatsoever.

        The system may involve the following stages as-

        1. Image Preprocessing. We may use any one of the better technique that is maintained below which is the first part of our project.

      • Preprocessing will eliminate errors caused during taking the image and to reduce brightness effects on the image.

      • Images in green bands show vessel structures most reliably. So, the green band was extracted.

      • Tools that we may applied:

      Median filters

      Laplacian filters.

      Image methods like Adaptive Contrast Enhancement, Histogram equalization.

      Edge detection like canny edge detection.

      1. Post Processing.

         The phase one output is feed to this phase in which we can use the method mention below or any better method which will provide better output in present contex.

         • The output images from blood vessel extraction were processed to get clearer contours of the vessels. The following techniques were applied

         • Sharpening by high pass spatial filters

         • Smoothing by FFT smoothing, p-mean filter.

      2. Output Data.

         The Output will be image that is segmented can be used for understanding behaviors and decease related to eye. Classifier: Gives the classification according to some criteria function applied and we can predict that the give eye image is defected or not. For above purpose a criteria function has been developed which is purely based on the application of vessel that are segmented and also the tortuosity is one of the criteria for this along with we can consider the blood clots a criteria. This supposed to classify the as per using any on criteria function or combination of more than two

         function for better effects. There are many classifier which gives better result-

         Figure 3:Vessel segmentation on a mosaic: (a) Original image (b) Manual segmentation (c) Dijkstra forest (d) Matched filters (e) Local entropy (f) GMM classifier

4. Conclusion

   As mentioned in Introduction we are trying to develop the cheap and fast system for eye image classification which can provide us accurate classification of defective and non-defective eye images. This can be possible by developing and passing an image though some phases described in our proposed work.

   Our method is successful or not can be checked with the help more and more image that can be present in dataset. If it possible to work and develop better criteria function then we can also provide accurate output of defective eye from non-defective one. We can possible to develop such system whichcan provide us defective eye classification according to deceases affecting eyes.

5. References

1. Rolando Estrada, Carlo Tomasi, 1 Michelle T. Cabrera, David K. Wallace, Sharon F. Freedman and SinaFarsiuExploratory Dijkstras forest based automatic vessel segmentation: application in video indirect Ophthalmoscopy 1 February 2012 / Vol. 3, No. 2 / BIOMEDICAL OPTICS EXPRESS 327.

2. G. A. Gole, A. L. Ells, X. Katz, G. Holmstrom, A. R. Fielder, A. Capone, Jr, J. T. Flynn, W. G. Good, J. M. Holmes, J. A. McNamara, E. A. Palmer, G. Quinn, E.,

   M. J. Shapiro, M. G. J. Trese, and D. K. Wallace, The international classification of retinopathy of prematurity revisited, Arch. Ophthalmol. 123, 991999 (2011).

3. F. Benmansour and L. Cohen, Tubular structure segmentation based on minimal path method and anisotropic enhancement, Int. J. Comput. Vision 92, 192210 (2011).

4. S. J. Chiu, X. T. Li, P. Nicholas, C. A. Toth, J. A. Izatt, and S. Farsiu, Automatic segmentation of seven retinal layers in SDOCT images congruent with expert manual segmentation, Opt. Express 18, 1941319428 (2010).

5. D. K. Wallace, G. E. Quinn, S. F. Freedman, and M. F. Chiang, Agreement among pediatric ophthalmologists

   in diagnosing plus and pre-plus disease in retinopathy of prematurity, J. Am. Assoc. Pediatric Ophthalmol. Strabismus 12, 352 356 (2008).

6. E. Ricci and R. Perfetti, Retinal blood vessel segmentation using line operators and support vector classification, IEEE Trans. Med. Image. 26, 13571365 (2007).

7. Q. Li, J. You, L. Zhang, and P. Bhattacharya, Automated retinal vessel segmentation using Gabor filters and scale multiplication, in Proceedings of System, Man and Cybernetics (IEEE, 2006), pp. 3521 3527.

8. W. Tasman, A. Patz, J. A. McNamara, R. S. Kaiser, M.

   T. Trese, and B. T. Smith, Retinopathy of prematurity: The life of a lifetime disease, Am. J. Ophthalmol. 141, 167 174 (2006).

9. M. Cree, D. Cornforth and HF. Jelinek, Vessel segmentation and tracking using a two-dimensional model, in Proceedings of Image and Vision Computing New Zealand (IVCNZ, 2005), pp. 345350.

10. T. Chanwimaluang and G. Fan, An efficient blood vessel detection algorithm for retinal images using local entropy thresholding, in Proceedings of the International Symposium on Circuits and Systems (IEEE 2003), pp.2124.

11. A. Hoover, V. Kouznetsova, and M. Goldbaum, Locating blood vessels in retinal images by piecewise threshold probing of a matched filter response, IEEE Trans. Med. Image. 19, 203210 (2002).

12. F. Zana and J. Klein, Segmentation of vessel-like patterns using mathematical morphology and curvature evaluation, IEEE Trans. Image Process. 10, 10101019 (2002).

13. L. Pedersen, M. Grunkin, B. Ersboll, K. Madsen, M. Larsen, N. Christoffersen and U. Skands, Quantitative measurement of changes in retinal vessel diameter in ocular fundus images, Pattern Recogn. Lett. (21), 1215 1223 (2000).

14. M. Mart´nez-P´erez, A. Hughes, A. Stanton, S. Thom,

    1. Bharath, and K. Parker, Retinal blood vessel segmentation by means of scale-space analysis and region growing, in Proceedings of Medical Image Computing and Computer-Assisted Intervention (Springer 1999), pp. 9097.

15. S. Chaudhuri, S. Chatterjee, N. Katz, M. Nelson, and M. Goldbaum, Detection of blood vessels in retinal images using two-dimensional matched filters, IEEE Trans. Med. Image. 8, 263269 (1989).