15 September 2004 Fast algorithms of constrained Delaunay triangulation and skeletonization for band images
Author Affiliations +
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.
© (2004) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Wei Zeng, ChengLei Yang, XiangXu Meng, YiJun Yang, XiuKun Yang, "Fast algorithms of constrained Delaunay triangulation and skeletonization for band images", 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; https://doi.org/10.1117/12.532615
PROCEEDINGS
12 PAGES


SHARE
RELATED CONTENT

Maximizing PPV in C3I systems
Proceedings of SPIE (May 05 2017)
Decentralized sensing and tracking for UAV scheduling
Proceedings of SPIE (September 15 2004)
The Institute for Security Technology Studies (ISTS): overview
Proceedings of SPIE (September 15 2004)
Hypergame theory applied to cyber attack and defense
Proceedings of SPIE (May 03 2010)

Back to Top