Share Email Print
cover

Proceedings Paper

Fast algorithms of constrained Delaunay triangulation and skeletonization for band images
Author(s): Wei Zeng; ChengLei Yang; XiangXu Meng; YiJun Yang; XiuKun Yang
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

For the boundary polygons of band-images, a fast constrained Delaunay triangulation algorithm is presented and based on it an efficient skeletonization algorithm is designed. In the process of triangulation the characters of uniform grid structure and the band-polygons are utilized to improve the speed of computing the third vertex for one edge within its local ranges when forming a Delaunay triangle. The final skeleton of the band-image is derived after reducing each triangle to local skeleton lines according to its topology. The algorithm with a simple data structure is easy to understand and implement. Moreover, it can deal with multiply connected polygons on the fly. Experiments show that there is a nearly linear dependence between triangulation time and size of band-polygons randomly generated. Correspondingly, the skeletonization algorithm is also an improvement over the previously known results in terms of time. Some practical examples are given in the paper.

Paper Details

Date Published: 15 September 2004
PDF: 12 pages
Proc. SPIE 5403, Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense III, (15 September 2004); doi: 10.1117/12.532615
Show Author Affiliations
Wei Zeng, Shandong Univ. (China)
ChengLei Yang, Shandong Univ. (China)
XiangXu Meng, Shandong Univ. (China)
YiJun Yang, Tsinghua Univ. (China)
XiuKun Yang, Identix Inc. (United States)


Published in SPIE Proceedings Vol. 5403:
Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense III
Edward M. Carapezza, Editor(s)

© SPIE. Terms of Use
Back to Top