A Path-Length Distance Transform for Quadtrees
Abstract
The size of a region in an image and distances between subregions of an image are useful geometric properties for describing region shape. In particular, the distance of interior points from the border is a useful measure for operations such as thinning and finding skeletons of regions. Most algorithms for finding the distance from a point inside a region to the border have involved multiple passes over the data, each pass incrementing a local counter denoting the distance of the associated point in the image. This paper presents an algorithm that computes the distance function in a single pass over an image represented by a quadtree. A distance measure is defined for a quadtree representation of a binary image. An algorithm is presented that calculates the distance from the center of each BLACK node to the border of the nearest WHITE node. The distance is defined as the path length from the center of the BLACK node, through the center of intervening BLACK nodes, to the WHITE border. The worst case average execution time is shown to be proportional to the product of the log of the image diameter and the number of blocks in the image.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1979
- Accession Number
- ADA084293
Entities
People
- Michael Shneier
Organizations
- University of Maryland