Parallel Algorithm for the Medial Axis Transform of Binary Images

摘要

The medial axis transform (abbreviated to MAT) represents a region of a digital image as the union of maximal upright squares contained in the region. In this paper, we present an 0(1) step parallel algorithm for the medial axis transform of an n x n binary image on a reconfigurable array of processors (abbreviated to RAP) using 0(n~3) processors. Based on the divide-and-conquer technique, we also develop an 0(n/c) step parallel algorithm for the same problem on a RAP using 0(c · n~2) processors. Here c is a constant, 1 ≤ c ≤ n and n mod c = 0.