Share Email Print

Proceedings Paper

Fast distance transform computation using dual scan line propagation
Author(s): Fatih Porikli; Tekin Kocak
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

We present two fast algorithms that approximate the distance transformation of 2D binary images. Distance transformation finds the minimum distances of all data points from a set of given object points, however, such an exhaustive search for the minimum distances is infeasible in larger data spaces. Unlike the conventional approaches, we extract the minimum distances with no explicit distance computation by using either multi-directional dual scan line propagation or wave propagation methods. We iteratively move on a scan line in opposite directions and assign an incremental counter to underlying data points while checking for object points. To our advantage, the precision of dual scan propagation method can be set according to the available computational power. Alternatively, we start a wavefront from object points and propagate it outward at each step while assigning the number of steps taken as the minimum distance. Unlike the most existing approaches, the computational load of our algorithm does not depend on the number of object points either.

Paper Details

Date Published: 26 February 2007
PDF: 8 pages
Proc. SPIE 6496, Real-Time Image Processing 2007, 649608 (26 February 2007); doi: 10.1117/12.704760
Show Author Affiliations
Fatih Porikli, Mitsubishi Electric Research Labs. (United States)
Tekin Kocak, Mitsubishi Electric Research Labs. (United States)

Published in SPIE Proceedings Vol. 6496:
Real-Time Image Processing 2007
Nasser Kehtarnavaz; Matthias F. Carlsohn, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?