A connected component labeling algorithm for grayscale images and application of the algorithm on mammograms

ABSTRACT

A new algorithm for connected component labeling is presented in this paper. This algorithm requires only one scan through an image for labeling connected components. Once this algorithm encounters a starting pixel of a component, it completely traces all the contour pixels and all internal pixels of that particular component. This algorithm recognizes components one at a time in the image while scanning in raster order. This property will be very useful in areas such as image matching, image registration and content-based information retrieval etc. This algorithm is also capable of extracting contour pixels of an image and storing them in the order of clock-wise direction which will provide very useful information in many applications. Also this algorithm assigns consecutive label numbers for different components and hence needs a minimum number of labels. As our main research is on mammography image analysis for diagnosing breast cancers, we applied this algorithm to mammograms and measured performance of the algorithm in terms of processing time. This will be a useful algorithm in medical image analysis as a preprocessing tool.

REFERENCES

• 1: Fu Chang , Chun-Jen Chen , Chi-Jen Lu, A linear-time component-labeling algorithm using contour tracing technique, Computer Vision and Image Understanding, v.93 n.2, p.206-220, February 2004 [doi>10.1016/j.cviu.2003.09.002]
• 2: Christoyianni I., Dermatas E., Kokkinakis G., Automatic Detection of Abnormal Tissue in Mammography, In Proc. International Conference on Image Processing, Volume 2, p 877--880, 2001.
• 3: David R., Arnau O., Joan M., Marta P., and Joan E., Brest Segmentation with Pectoral Muscle Suppresion on Digital Mammograms, In Proc. Iberian Conference on Pattern Recognition and Image Analysis(2), p 471--478, 2005.
• 4: Christophe Fiorio , Jens Gustedt, Two linear time Union-Find strategies for image processing, Theoretical Computer Science, v.154 n.2, p.165-181, Feb. 5, 1996 [doi>10.1016/0304-3975(94)00262-2]
• 5: Rafael C. Gonzalez , Richard E. Woods, Digital Image Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 6: Haralick R. M., Some Neighborhood Operations, Real Time/Parallel Computing Image Analysis, Plenum Press, New York, p 11--35, 1981.
• 7: Hashizume A., Suzuki R., Yolouchi H., An Algorithm of Automated RBC Classification and its Evaluation, Bio Medical Engineering, vol. 28(1), p. 25--32, 1990.
• 8: Jasjit S., Suri, Rangaraj M., Rangayyan, Recent Advances in Breast Imaging, Mammography, and Computer-Aided Diagnosis of Breast Cancer, SPIE Publication, 2006.
• 9: Jung-Me P., Carl G. Looney, Hui-Chuan C., Fast Connected Component Labeling Algorithm Using a Divide and Conqure Technique, CATA 2000 Conference on Computers and Their Applications, pp 373--376, Dec. 2000.
• 10: Kesheng W., Ekow O., and Arie S., Optimizing Connected Component Labeling Algorithms, In Proceedings of SPIE Medical Imaging Conference, p. 1965--1976, Apr 2005.
• 11: Tony Lindeberg, Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, Norwell, MA, 1994
• 12: Lumia R., Shapiro L., Zuniga O., A New Connected-Components Algorithm for Virtual Memory Computers, Computer Vision Graphics and Image Processing, Vol 23, p 207--217, 1983.
• 13: Michael A., Wirth, A Non-rigid Approach to Medical Image Registration: Matching Images of the Breast, Ph.D. Thesis, 2000, RMIT University, Melbourne, Australia
• 14: Azriel Rosenfeld , John L. Pfaltz, Sequential Operations in Digital Picture Processing, Journal of the ACM (JACM), v.13 n.4, p.471-494, Oct. 1966 [doi>10.1145/321356.321357]
• 15: Kenji Suzuki , Isao Horiba , Noboru Sugie, Linear-time connected-component labeling based on sequential local operations, Computer Vision and Image Understanding, v.89 n.1, p.1-23, January 2003 [doi>10.1016/S1077-3142(02)00030-9]
• 16: Yapa R. D., Harada K., A performance Evaluation of Connected Component Labeling Algorithms on Grayscale Digital Mammograms, In Proc. 7th International Information Technology Conference, Colombo, Sri Lanka, 2006 Sept.
• 17: Digital Mammography Database Ver 1.2, The Mammographic Image Analysis Society, (http://www.wiau.man.ac.uk/services/MIAS/MIASweb.html)

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Pixel classification

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement
          Subjects: Registration
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms

Keywords:
binary image, connected component labeling, contour-tracing, grayscale image, mammogram