线性四元树表示图象的距离变换

DISTANCE TRANSFORM FOR IMAGES REPRESENTED BY LINEAR QUADTREES

二元数组表示的图象使用的距离概念运用于线性四元树表示。指出棋盘距离特别适合于线性四元树。定义线性四元树的棋盘距离变换为树中各个黑四分形中心到最近边界四分形黑一白边界的距离。这里提出的距离变换算法主要特点是(1)它是一种代数方法,(2)各个四分形只计算一次距离,和(3)距离信息非常快地传递到区域内部。该算法可以推广到线性八元树表示的三维客体。

The concept of distance used in binary array representations of images is applied to a linear quadtree representation. The chessboard distance is shown to be especially suitable for the linear quadtree. A chessboard distance transform for a linear quadtree is defined as the distance from the center of each BLACK quadrant to the BLACK-WHITE border of the nearest boundary quadrant. The main attributes of the distance transform algorithm presented here are (1) it is algebraic method,(2) the distance transform of each quadrant is computed only once, and (3) distance information is very quickly propagagted to the interior of the region. The algorithm can be extended to three-dimensional objects represented by linear octrees.