Fast algorithms of constrained Delaunay triangulation and skeletonization for band images

Wei Zeng; ChengLei Yang; XiangXu Meng; YiJun Yang; XiuKun Yang

doi:10.1117/12.532615

15 September 2004 Fast algorithms of constrained Delaunay triangulation and skeletonization for band images

Wei Zeng; ChengLei Yang; XiangXu Meng; YiJun Yang; XiuKun Yang;

Author Affiliations +

Proceedings Volume 5403, Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense III; (2004) https://doi.org/10.1117/12.532615
Event: Defense and Security, 2004, Orlando, Florida, United States

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.

Citation Download Citation

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

ACCESS THE FULL ARTICLE

PERSONAL SIGN IN
Full access may be available with your subscription

Email or Username Forgot your username?

Password Forgot your password?

Show

Remember Email/Username on this computer

Remember Password

No SPIE account? Create an account
or Institutional Sign In via Shibboleth

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $14.40

Non-members: $18.00 ADD TO CART

Show All Keywords

Keywords/Phrases

Search In:

Publication Years