The medial axis transform (MAT) is an image representation scheme. For a binary image, the MAT is defined as a set of upright maximal squares which consist of pixels of value 1 entirely. The MAT plays an important role in image understanding. The paper presents a parallel algorithm for computing the MAT of an n/spl times binary image. We show that the algorithm can be performed in O(log n) time using n2/log n processors on the EREW PRAM and in O(log log n) time using n/sup 2//log log n processors on the common CRCW PRAM. We also show that the algorithm can be performed in O(n/sup 2//p/sup 2/+n) time on a p/spl times/p mesh and in O(n/sup 2//p/sup 2/+(n log p)/p) time on a p/sup 2/ processor hypercube (for 1/spl les/p/spl les). The algorithm is cost optimal on the PRAMs, on the mesh (for 1/spl les/p/spl les//spl radic) and on the hypercube (for 1/spl les/p/spl les/log n).
展开▼
机译：中间轴变换（MAT）是一种图像表示方案。对于二进制图像，MAT被定义为一组完全由值1的像素组成的最大直方图。 MAT在图像理解中起着重要作用。本文提出了一种并行算法，用于计算n / spl次/ n二进制图像的MAT。我们展示了该算法可以在EREW PRAM上使用n2 / log n处理器的O（log n）时间执行，并在普通CRCW PRAM上使用n / sup 2 // loglog n处理器的O（log log n）时间执行。 。我们还表明，该算法可以在ap / spl次/ p网格的O（n / sup 2 // p / sup 2 / + n）时间和O（n / sup 2 // p / sup 2 / ap / sup 2 /处理器超多维数据集上的+（n log p）/ p）时间（针对1 / spl les / p / spl les / n）。该算法在PRAM，网格（针对1 / spl les / p / spl les // spl radic / n）和超立方体（针对1 / spl les / p / spl les / n / log n）上是成本最优的）。
展开▼
