{"id":1315,"date":"2015-06-18T06:26:56","date_gmt":"2015-06-18T06:26:56","guid":{"rendered":"http:\/\/biomedpharmajournal.org\/?p=1315"},"modified":"2020-04-25T02:54:45","modified_gmt":"2020-04-25T02:54:45","slug":"euclidean-distance-transform-edt-algorithm-applied-to-binary-image-for-finding-breast-cancer","status":"publish","type":"post","link":"https:\/\/biomedpharmajournal.org\/staging\/vol8no1\/euclidean-distance-transform-edt-algorithm-applied-to-binary-image-for-finding-breast-cancer\/","title":{"rendered":"Euclidean Distance Transform (EDT) Algorithm Applied to Binary Image for Finding Breast Cancer"},"content":{"rendered":"

Introduction<\/strong><\/p>\n

Breast cancer continues to be a signi\ufb01cant public health problem in the world and it is common cancer in women [1]. Early detection of breast cancer is the key for improving breast cancer prognosis. Currently the most effective method employed for Early Detection and Screening of Breast Cancers is Mammography [2]. However, it is difficult for radiologists to provide both accurate and uniform evaluation for the enormous Mammograms generated in widespread screening. The estimated sensitivity of radiologists in Breast Cancer screening is only about 75%, but the performance would be improved if they were prompted with the possible locations of abnormalities.<\/p>\n

A Mammogram is basically distinct with four levels of the intensities: background, fat tissue, breast parenchyma and calci\ufb01cations with increasing intensity. Masses develop from the epithelial and connective tissues of breasts and their densities on Mammograms blend with parenchyma patterns. Several studies have revealed a positive association of tissue type with Breast Cancer risks [3, 4 and 5]. Women who have breast cancers can easily get contra lateral cancers in the other side breast [6 and 7]. The traditional method for histological confirmation involves open surgery biopsy in which the breast is open and the tumor lump is fully taken out. Some women with Breast Cancer are treated with modified radical mastectomy which consist of surgical removal of a Breast Module [8]. In Both cases the surgeon does not have a real time indication or delineating the cancer cells.<\/p>\n

There are many different proposed systems for finding of cancer cells area in Mammogram Image. The Majority of proposed cancer detection techniques in literature share the common steps to image enhancement, segmentation and quantification [9]. These techniques lie in the difficulty of analyzing the breast region, which appears different intensity level in the Mammogram Image. In the Methodology we describe about the Triangulation of making the image highly visible from the invisible background pixel and also we describe the distance calculation through Euclidean Distance transformation Algorithm.<\/p>\n

Triangulation (Image Acquision)<\/strong><\/p>\n

In the preprocessing steps X ray film Mammogram (Gray scale) is converted in to Digital Mammogram Image .The exact pixel value depends on the range of optical densities that the scanner is capable of finding the density difference of a pixel. Delaunay triangulation is rotation and translation invariant because it consists of the direction and location only relative to its some neighboring pixel [10].Delaunay triangulation has important characteristics<\/p>\n

    \n
  1. The Delaunay Triangulation of a non degenerate set of points is unique.<\/li>\n
  2. A circle through the three points of a Delaunay triangle contains no other points.<\/li>\n
  3. If the circle is unique it is called circum circle of pixel.<\/li>\n<\/ol>\n

    Algorithm Steps<\/strong><\/p>\n

      \n
    1. Take the input image as Thinned Binary image.<\/li>\n
    2. Given a set S of pixels p1<\/sub>,p2<\/sub>\u2026.pN<\/sub>.We can compute the Delaunay Triangulation by Voronoi diagram.<\/li>\n
    3. The voronoi diagram decomposes the image in to number or regions around each pixel .Such that the entire pixel in the region around pi <\/sub>closes to pj<\/sub> than they are to any points in S.<\/li>\n
    4. Let P be a circle free set .three points p, q and r of P define a Delaunay triangle if there is no further point of P in the interior of the circle which is circumscribed to the triangle p, q, r and its centre lies on a voronoi vertex.<\/li>\n
    5. If any triangle has interior point the triangle replaced by new triangle.<\/li>\n
    6. Every time ensure that Triangulation is unique. This algorithm works by growing a current triangulation triangle by triangle.<\/li>\n<\/ol>\n

      In each iteration, the algorithm seeks a new triangle which attaches to the boundary of current triangulation.<\/p>\n\n\n\n
      \"Figure1.Input<\/td>\nFigure 1: Input Thinned Binarized Image<\/strong><\/p>\n

      Click here to View figure<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

       <\/p>\n\n\n\n
      \"Figure<\/td>\nFigure 2: Output Image after Triangulation<\/strong><\/p>\n

      Click here to View figure<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

       <\/p>\n

      The contrast Improvement by triangulation based on local information .So that weak regions of the image are enhanced more than strong regions. This method is beneficial to experts when manually defining the edges for diagnosing purposes. Next section we are going to discuss about the Euclidean Distance calculation between foreground and background of an image.<\/p>\n

      Euclidean Distance Transform<\/strong><\/p>\n

      The Method to convert a digital binary image that consist of object (foreground ) and non object (background) pixel in to another image in which each object pixel has a value corresponding to the minimum distance from the background by a distance function is Distance Transformation. By simply exchanging the roles of Object and Background.<\/p>\n

      Distance transformation can be applied on the outside pixels of a closed boundary. Among different kinds of distance transformation the Euclidean Distance Transform [EDT] is often used because of its rotation invariance property [11]. But it involves the time consuming calculation such as square, square root and the minimum over a set of floating point numbers. To overcome these difficulties in finding of distance through Distance transformation between pixels we are going to use two scan recursive algorithms by using 3*3 neighborhoods and has analyzed. This algorithm only requires two image scans that are forward and backward rater scans in a Binary image.<\/p>\n

      Characteristic<\/strong><\/p>\n

      The 8 neighbors of pixel p be denoted by\u00a0 q1,q2\u2026\u2026q8.thus N1<\/sub>(p) ={q1<\/sub>,q2<\/sub>,q3<\/sub>,q5<\/sub>} and N2<\/sub>(p)={q5<\/sub>,q6<\/sub>,q7<\/sub>,q8<\/sub>}.<\/p>\n\n\n\n\n\n
      q2<\/sub><\/td>\nq3<\/sub><\/td>\nq4<\/sub><\/td>\n<\/tr>\n
      q1<\/sub><\/td>\np<\/td>\nq5<\/sub><\/td>\n<\/tr>\n
      q8<\/sub><\/td>\nq7<\/sub><\/td>\nq6<\/sub><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

       <\/p>\n

      f: A Thinned Binarized Image.<\/p>\n

      F: The set of Object pixels.<\/p>\n

      Fo <\/sub>: The set of Background boundary pixels.<\/p>\n

      o: The set of background boundary pixels<\/p>\n

      Q: The set of Foreground pixels which already have minimum squared Euclidean Distance through a Triangulation algorithm.<\/p>\n

      H (p, q): The Difference of the Squared Euclidean Distance of p and q (op2<\/sup>-oq2<\/sup>). q\u0404N1<\/sub>UN2 .<\/sub><\/p>\n

      G (p, q): The difference of the relative coordinates of p and q.<\/p>\n

      R (p) the relative coordinate. Rx<\/sub>, Ry<\/sub> of pixel p, which records the horizontal and vertical background pixel distance between p and closet background pixel. It is initialized as all (0, 0).<\/p>\n

      \"formula1\"<\/p>\n

       <\/p>\n

      Algorithm<\/p>\n

      Forward<\/p>\n

        \n
      1. Pixel belongs to the Binary image p\u0404F<\/li>\n
      2. Pixel value of Binary image may be infinite. f(p)=\u221e<\/li>\n
      3. Select 3*3 neighboring pixel<\/li>\n
      4. If q\u0404N1 , <\/sub>q ={q1<\/sub>,q2<\/sub>,q3<\/sub>,q4<\/sub>}<\/li>\n<\/ol>\n

        4.a. f(p)=min(f(p),f(q)+H(p,q))<\/p>\n

        b. R (p) =R (q) +G (p, q)<\/p>\n

        If q\u0404N2<\/sub>, q= {q5<\/sub>, q6<\/sub>, q7<\/sub>, q8<\/sub>}<\/p>\n

        a. f(p)=min(f(p),f(q)+H(p,q))<\/p>\n

        b. R–<\/sub> (p) =R (q) +G (p, q).<\/p>\n

        E (p) = \u221af (p).<\/p>\n

        Case 1: The smallest squared Euclidean distance obtained from q1.<\/sub><\/p>\n

        When q1<\/sub>\u0404Q and o \u0404 O<\/p>\n

        o (0,0)<\/p>\n\n\n\n\n\n
        <\/td>\n<\/td>\n<\/td>\n<\/tr>\n
        q1<\/sub>(Rx-<\/sub>1,<\/sub>Ry<\/sub>)<\/td>\nP(Rx<\/sub>,Ry<\/sub>)<\/td>\nq5<\/sub><\/td>\n<\/tr>\n
        q8<\/sub><\/td>\nq7<\/sub><\/td>\nq6<\/sub><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

         <\/p>\n

        Using above conditions R (q1<\/sub>) = ((Rx<\/sub>-1), Ry<\/sub>).Squared Euclidean Distance at q1 is oq2<\/sup>= (Rx<\/sub>-1)2<\/sup>+ Ry<\/sub>2 .<\/sup>Squared Euclidean Distance at p will be op2= Rx<\/sub>2<\/sup>+<\/sub>Ry<\/sub>2<\/sup> .Since p is located on the one pixel away from q1<\/sub>.<\/p>\n

        The difference of the SED of p and q1<\/sub> according to equation (1) is<\/p>\n

        H (p, q1) = (op2<\/sup>-oq2<\/sup>)<\/p>\n

        = 2(Rx<\/sub>-1) + 1<\/p>\n

        This satisfies the first condition of H (p, q1<\/sub>).<\/p>\n

        So Rx <\/sub>(q1<\/sub>) = Rx<\/sub>-1 and G (p, q1<\/sub>) = (1, 0)<\/p>\n

        R (p) = R (q1<\/sub>) + G (p, q1<\/sub>)<\/p>\n

        R (p) = (R (q1<\/sub>) +1, Ry<\/sub> (q1<\/sub>))<\/p>\n

        Above producer can be repeated for finding the Smallest Euclidean Distance is obtained from q2<\/sub>, q3<\/sub>, q4.<\/sub><\/p>\n

        Same way nearest background pixel located on the right top side also taken care for forward scan and relative coordinate R (p) was calculated.<\/p>\n

        The Smallest Euclidean Distance of p can also be obtained by another four neighborhoods q5<\/sub>, q6<\/sub>, q7<\/sub> and q8<\/sub> by reverse scan and R (p) was calculated.<\/p>\n\n\n\n
        \"Figure<\/td>\nFigure 3: Final Output Image with Cancer<\/strong><\/p>\n

        Click here to View figure<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

         <\/p>\n

        Conclusions<\/strong><\/p>\n

        A distance transformation converts the Binary image in to Distance image. Euclidean Distance is consequently a candidate because representing images as points in a high dimensional Euclidean space, so called image space, and is a common point of most recognition algorithms. Although there is infinitely much Euclidean distance for images, they often provide counter intuitive results. Thus two scan algorithm using neighborhood Euclidean Distance Transformation algorithm use only a small image neighborhood and work with in the image itself do not need any memory. In our work we have used 3*3 neighborhoods Euclidean Distance Transformation. It is optimized and analyzed. We have implemented a set of reliable technique for Mammogram image extraction. Each pixel value is changed as a distance value shows the Mammogram Image with high level features to find the cancer cell area. Our system has potential of improving doctor\u2019s diagnostic performance.<\/p>\n

        References<\/strong><\/p>\n

          \n
        1. M. Kaczmar, N.K.P. Orzechowski, P. Iwaszko, M. Baranczyk and K.Orzechowski. Localization of Cancerous changes in Images Breast Tissue. Proceedings of the International multiconference on Computer Science and Information Technology<\/em>. Vol 4, pp. 413-419, 2009.<\/li>\n
        2. H.D.Cheng, X.P. Cai, X.W. Chen, L.M. Hu and X. Lou. Computer-aided detection and classification of microcalcifications in mammograms: a survey. Pattern Recognition<\/em>. Vol 36, pp.2967-2991, 2003.<\/li>\n
        3. K. Bovis, S. Singh, J. Fieldsend, C. Pinder, Identi\ufb01cation of masses in digital mammograms with MLP and RBF nets. In: Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks Comunications.<\/em> 342\u2013347, 2000.<\/li>\n
        4. R.L. Egan and R.C. Mosteller. Breast Cancer Mammography Patterns. Cancer<\/em> 40. pp. 2087-2090, 1977<\/li>\n
        5. J.N. Wolfe. Breast patterns as an index of risk for developing Breast Cancer. American Journal of Roentgenology<\/em>. Vol 126, pp.1130-1139, 1976.<\/li>\n
        6. H.H. Storm and O.M. Jensen. Risk of contra lateral breast cancer in Denmark 1943-80. British Journal of Cance<\/em>r. Vol.54, pp.483-492, 1986.<\/li>\n
        7. G.F. Robbins and J.W. Berg. Bilateral primary breast cancers, A Prospective Clinico Pathology. Study Cancer<\/em>. Vol 17, pp 1501\u20131527, 1964.<\/li>\n
        8. P. Lecoq and J. Varela. Clear-PEM, A dedicated PET camera for Mammography. Journal of Nuclear Instruments and Methods in Physics Research Section A. <\/em>Vol.486, pp.1\u20136, 2002.<\/li>\n
        9. Gonzalez, R. C. and Woods, R. E. Digital Image Processing<\/em>, 3rd ed<\/em>., Prentice Hall, Upper Saddle River, NJ, 2008.<\/li>\n
        10. G. Bebis, T. Deaconu and M. Georgiopoulos. Fingerprint identification using Delaunay triangulation. IEEE International Conference on Information Intelligence and Systems Proceedings<\/em>. pp.452-459, 1999.<\/li>\n
        11. H.D.Cheng, X.J.Shi, R.Min, L.M.Hu, X.P.Cai and H.N.Du. Approaches for automated detection and classification of massas in mammograms. Pattern Recognition<\/em>. Vol 39, pp.646-668, 2006.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

          Introduction Breast cancer continues to be a signi\ufb01cant public health […]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-1315","post","type-post","status-publish","format-standard","hentry","category-vol8no1"],"_links":{"self":[{"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/posts\/1315","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/comments?post=1315"}],"version-history":[{"count":4,"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/posts\/1315\/revisions"}],"predecessor-version":[{"id":32830,"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/posts\/1315\/revisions\/32830"}],"wp:attachment":[{"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/media?parent=1315"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/categories?post=1315"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/biomedpharmajournal.org\/staging\/wp-json\/wp\/v2\/tags?post=1315"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}