Normal vector and winding number in 2D digital images with their application for hole detection

摘要

Differentiating hole from component is an important issue in digital topology. In a recent paper, Lee, Poston, and Rosenfeld proposed a method to distinguish external and internal boundaries in 2D and 3D images relying on the property of normal vector and winding number. The method uses a smoothing function to replace digital lattice for calculating normal vector on image boundary. In this paper, we show that normal vector and winding number can be defined directly in 2D digital images and used for hole detection without resorting to any smoothing operation. We analyze first the discontinuity of Freeman codes of contour and prove its properties. We define then outward normal vector in 2D images and demonstrate also its discontinuity properties. The difficulty of counting the transition of normal vector in a given direction is analyzed and a solution is proposed. Based on the theoretic properties of edge code and normal vector, we propound the first algorithm to count the transitions of normal vector in a given direction, and consequently holes and external contours can be distinguished easily. We further define winding number directly in digital images, show its properties, and propose a second algorithm implementing the idea of winding number which is conceptually simpler and easier than the first one. A proof of correctness of our both algorithms is given and computation results are presented.