Finding a minimal cover for binary images: An optimal parallel algorithm

Given a black-and-white image, represented by an array of n × n binary-valued pixels, we wish to cover the black pixels with aminimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining aminimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for theminimal square cover problem, which for any desired computation timeT in logn,n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.The research reported here forms part of the author's doctoral dissertion, submitted to Cornell University in May 1989. This work was partially supported by NSF Grant DC1-86-02256, IBM Agreement 12060043, and ONR Contract N00014-83-K-0640. A preliminary version of this paper was presented at the 26th Annual Allerton Conference on Communications, Control, and Computing, Monticello, IL, September 28–30, 1988.