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-direction dual scan line propagation or waive 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 accordingly 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.