The Labeled Discrete Voroni Diagram

Generalized voronoi diagrams of sets of digital curves are a helpful tool in picture anlaysis. In this paper, an algorithm for computing laberled Voronoi diagrams for digital straight line segments is given. Special emphasis was given to the use of a labeled Euclidean distance transform. This transform is the key feature of the proposed lable propagation process. The proposed parallel algorithm for computing labeled Voronoi diagrams has time complexity 0maxM,N for input pictures of size NxM using a mesh connected array processor. The proposed serial algorithm for computing labeled Voronoi diagrams has time complexity 0MN. Additional Keywords Image analysis and Pixels.