| Paper title: |
Extracting ridges of topographic surfaces using scanline algorithm |
| Published in: | Issue 2, (Vol. 3) / 2009 |
| Publishing date: | 2009-10-20 |
| Pages: | 20-27 |
| Author(s): | Chang Sukmoon |
| Abstract. | The ridge/valley-like structures of a topographic surface have been extensively studied in image processing to obtain useful skeleton-like shape descriptors. In this paper, we propose a novel method that rapidly constructs the graph representation of the skeletons of the curvilinear objects such as vascular networks and fingerprints. The method first constructs the topographic surface of a given image in such a way that the ridges of the surface reflect the medial axis of the objects in the image. The ridge points are then identified using two orthogonal scanlines and connected by tracing the maximum gradient paths on the surface. We present the very promising results of the method applied to various binary and grayscale images to demonstrate its correctness and robustness. |
| Keywords: | Ridges, Skeletonization, Scanline Algorithm |
| References: | 1. D. Eberly, R. Gardner, B. Morse, S. Pizer, and C. Scharlach, "Ridges for Image Analysis," Journal of Mathematical Imaging and Vision, vol. 4, pp. 353-373, 1994. 2. J. J. Koenderink and A. J. van Doom, "The Structure of Relief," Advances in Imaging and Electron Physics, vol. 103, pp. 65-150, 1998. 3. F. Leymarie and M. D. Levin, "Simulating the Grassfire Transform Using an Active Contour Model," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 1, pp. 56-75, 1992. 4. R. L. Ogniewicz and O. Kubler, "Hierarchic Voronoi Skeletons," Pattern Recognition, vol. 28, no. 3, pp. 343- 359, 1995. 5. S. M. Pizer, D. Eberly, D. S. Fritsch, and B. S. Morse, "Zoom-Invariant Vision of Figural Shape: The Mathematics of Cores," Computer Vision and Image Understanding, vol. 69, no. 1, pp. 55-71, 1998. 6. J. M. Gauch and S. M. Pizer, "Multiresolution Analysis of Ridges and Valleys in Grey-Scale Images," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, no. 6, pp. 635-646, 1993. 7. A. M. Lopez, F. Lumbreras, and J. Serrat, "Creaseness from Level Set Extrinsic Curvature," in Proceedings of the 5th European Conference on Computer Vision, H. Burkhardt and B. Neumann, eds., pp. 156-169, June 1998. 8. B. Kimia, A. R. Tannenbaum, and S. W. Zucker, "Shapes, Shocks, and Deformations I: The Components of Two-Dimensional Shape and the Reaction-Diffusion Space," International Journal of Computer Vision, vol. 15, pp. 189-224, 1995. 9. H. Tek and B. Kimia, "Symmetry Maps of Free-Form Curve Segments Via Wave Propagation," in Proceedings of the 7th International Conference on Computer Vision, pp. 362-369, 1999. 10.A. M. Lopez, F. Lumbreras, J. Serrat, and J. J. Villanueva, "Evaluation of Methods for Ridge and Valley Detection," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, no. 4, pp. 327-335, 1999. 11.J. B. A. Maintz, P. A. van den Elsen, and M. A. Viergever, "Evaluation of Ridge Seeking Operators for Multimodality Medical Image Matching," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 4, pp. 353-365, 1996. 12.H. Blum and R. N. Nagel, "Shape Description Using Weighted Symmetric Axis Features," Pattern Recognition, vol. 10, no. 3, pp. 167-180, 1978. 13.F. Y. Shih and C. C. Pu, "A Skeletonization Algorithm by Maxima Tracking on Euclidean Distance Transform," Pattern Recognition, vol. 28, no. 3, pp. 331-341, 1995. 14.P. Golland and W. E. L. Grimson, "Fixed Topology Skeletons," in Proceedings of Computer Vision and Pattern Recognition, pp. 10-17, June 2000. 15.N. Ahuja and J. Chuang, "Shape Representation Using a Generalized Potential Field Model," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no.2,pp. 169-176, 1997. 16.J. Chuang, C. Tsai, and M. Ko, "Skeletonization of Three-Dimensional Object Using Generalized Potential Field," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 11, pp. 1241-1251, 2000. 17.P. J. Yim, P. L. Choyke, and R. M. Summers, "Gray- Scale Skeletonization of Small Vessels in Magnetic Resonance Angiography," IEEE Transactions on Medical Imaging, vol. 19, no. 6, pp. 568-576,2000. 18. S. Aylward and E. Bullitt, "Initialization, Noise, Singularities, and Scale in Height Ridge Traversal for Tubular Object Centerline Extraction," IEEE Transactions on Medical Imaging, vol. 21, no. 2, pp. 61- 75,2002. 19. S. B. Ho and C. R. Dyer, "Shape Smoothing Using Medial Axis Properties," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8, no. 4, pp. 512- 520, 1986. 20. S. Chang, D. Metaxas, and L. Axel, "Scan-Conversion Algorithm for Ridge Point Detection on Tubular Objects," in Proceedings of the 6th International Conference on Medical Image Computing and Computer-Assisted Intervention-MICCAI 2003, pp. 158- 165,2003. 26 21.W. W. Seemuller, "The Extraction of Ordered Vector Dranage Networks from Elevation Data," Computer Vision, Graphics, and Image Processing, vol. 47, pp. 45- 58, 1989. 22. M. W. Wright, R. Cipolla, and P. J. Giblin, "Skeletonization Using an Extended Euclidean Distance Transform," Imaging and Vision Computing, vol. 13, no. 5, pp. 367-375, 1995. 23. P. E. Danielsson, "Euclidean Distance Mapping," Computer Graphics and Image Processing, vol. 14, pp. 227-248, 1980. 24.R. Kimmel, D. Shaked, N. Kiryati, and A. M. Bruckstein, "Skeletonization via Distance Maps and Level Sets," Computer Vision and Image Understanding, vol. 62, no. 3, pp. 382-391, 1995. 25. U. Montanari, "A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance," Journal of the ACM, vol. 15, no. 4,pp.600-624, 1968. 26. S. Aylward, E. Bullitt, S. Pizer, and D. Eberly, "Intensity Ridge and Widths for Tubular Object Segmentation and Description," in Proceedings of the Workshop on Mathematical Methods in Biomedical Image Analysis, pp. 495-499, January 21-22 1996. 27. L. M. J. Florack, B. M. ter Haar Romeny, J. J. Koenderink, and M. A. Viergever, "Linear Scale-Space," Journal of Mathematical Imaging and Vision, vol. 14, pp. 325-351, 1994. |
| Back to the journal content | |
