Optimal Parallel Algorithms for Region Labeling and Medial Axis Transform of Binary Images
Sung Kwon Kim · SIAM Journal on Discrete Mathematics · 1991
Given a $\sqrt{n} \times \sqrt{n} $ binary image, region labeling labels each 1 of the image so that two 1’s have the same label if and only if they are in the same region (i.e., connected) and medial axis transform finds for each 1 of the image the largest square subimage having it as top-left corner and consisting only of 1’s. Both can be solved in $\theta ( n )$ sequential time. $O( \log n )$ time, $n/\log n$ processor parallel algorithms for both problems in the EREW PRAM are presented.