Department of Computer Science, University of Maryland, College Park, MD 20742.
IEEE Trans Pattern Anal Mach Intell. 1982 Mar;4(3):298-303. doi: 10.1109/tpami.1982.4767246.
The concept of distance used in binary array representations of images is adapted to a quadtree representation. The chessboard distance metric is shown to be particularly suitable for the quadtree. A chessboard distance transform for a quadtree is defined as the minimum distance in the plane from each BLACK node to the border of a WHiTE node. An algorithm is presented which computes this transform by only examining the BLACK node's adjacent and abutting neighbors and their progeny. However, unlike prior work with quadtrees, computation of the distance transform requires a capability of finding neighbors in the diagonal direction rather than merely in the horizontal and vertical directions. The algorithm's average execution time is proportional to the number of leaf nodes in the quadtree.
将图像的二进制数组表示中的距离概念应用于四叉树表示。显示棋盘距离度量特别适用于四叉树。定义四叉树的棋盘距离变换为从每个 BLACK 节点到 WHiTE 节点边界的平面中的最小距离。提出了一种通过仅检查 BLACK 节点的相邻和相邻邻居及其后代来计算此变换的算法。但是，与四叉树的先前工作不同，距离变换的计算需要具有在对角线方向而不仅仅是在水平和垂直方向上查找邻居的能力。该算法的平均执行时间与四叉树中的叶节点数成正比。
