A quadtree medial axis transform
A quadtree medial axis transform
复制标题
四叉树中轴变换
DOI：
10.1145/358172.358409
复制
发表时间：
1983
影响因子：
22.7
通讯作者：
H. Samet
中科院分区：
文献类型：
--
作者：
H. Samet
由于四叉树骨架是图像的精确表示，并且被使用，因为它们被观察到有效地产生空间并且与四叉树相比对移位的敏感性降低。QMAT可以用作解决大多数可以通过使用四叉树解决的问题时的底层表示。提出了一种算法，通过只检查每个BLACK节点的相邻和邻接邻居来计算给定四叉树的QMAT。更正摘要（在CACM 27，2（1984年2月）第151页中作为勘误表出版）传统图像处理表示中使用的骨架和中轴变换概念适用于四叉树表示。其结果是定义了一种新的数据结构，称为四叉树中轴变换（QMAT）。QMAT会将图像划分为一组不相交的正方形，其边长为2的幂次之和，而不是像四叉树那样，一组不相交的正方形，其边长为2的幂次。我们的动机不是为了获得图像的近似而研究骨架。相反，四叉树骨架是图像的精确表示，并被使用，因为它们被观察到产生空间效率和与四叉树相比对移位的敏感性降低。QMAT可以用作解决大多数可以通过使用四叉树解决的问题时的底层表示。提出了一种算法，通过只检查每个BLACK节点的相邻和邻接邻居来计算给定四叉树的QMAT。算法的分析揭示了与图像的复杂度成比例的平均执行时间，即，黑色区块的数量。
As printed Quadtree skeletons are exact representations of the image and are used because they are observed to yield space efficiently and a decreased sensitivity to shifts in contrast with the quadtree. The QMAT can be used as the underlying representation when solving most problems that can be solved by using a quadtree. An algorithm is presented for the computation of the QMAT of a given quadtree by only examining each BLACK node's adjacent and abutting neighbors. Corrected Abstract (published as corrigendum in CACM 27, 2 (February 1984) p. 151) The skeletal and medial axis transform concepts used in traditional image processing representations are adapted to the quadtree representation. The result is the definition of of a new data structure termed the Quadtree Medial Axis Transform (QMAT). A QMAT results in a partition of the image into a set of nondisjoint squares having sides whose lengths are sums of powers of 2 rather than, as is the case with quadtrees, a set of disjoint squares having sides of lengths which are powers of 2. The motivation is not to study skeletons for the usual purpose of obtainings approximations of the image. Instead, quadtree skeletons are exact representations of the image and are used because they are observed to yield space efficiency and a decreased sensitvity to shifts in contrast with the quadtree. The QMAT can be used as the underlying representation when solving most problems that can be solved by using a quadtree. An algorithm is presented for the computation of the QMAT of a given quadtree by only examining each BLACK node's adjacent and abutting neighbors. Analysis of the algorithm reveals an average execution time proportional to the complexity of the image, i.e., the number of BLACK blocks.