Abstract
In recent years there has been a tremendous spurt in research and activity in finding efficient compression techniques for image processing applications. Particularly when an image is structured over a non-rectangular region it is always advantageous to define a method of covering a region by minimal numbers of maximal rectangles. Towards this objective, we analyze the binary image compression problem using irreducible cover of maximal rectangles. We also give a bound on the minimum rectangular cover problem for image compression under certain conditions that previously have not been analyzed. It is demonstrated for a simply connected image that, the irreducible cover proposed here uses less than four times the number of the rectangles in a minimum cover. With n pixels in a square, the parallel algorithm of obtaining the irreducible cover presented in the paper uses (n/log n) concurrent-read-exclusive-write (CREW) processors in O(log n) time.
Keywords
Image compression, maximal rectangles, covering algorithms
Date of this Version
11-1-1987
Comments
Partial support for the research of this author was provided by a grant from the Louisiana Education Quality Support Fund. ^Partial support for the research of this author was provided by the National Science Foundation and Office of Naval Research.