Decomposition of binary images—A survey and comparison

We present an overview of the most important methods that decompose an arbitrary binary object into a union of rectangles. We describe a run-length encoding and its generalization, decompositions based on quadtrees, on mathematical morphology, on the distance transform, and a theoretically optimal decomposition based on a maximal matching in bipartite graphs. We compare their performance in image compression, in moment computation and in linear filtering. We show that the choice is always a compromise between the complexity and time/memory consumption. We give advice how to select an appropriate method in particular cases.

► Decomposition of binary objects to rectangles is useful in various applications.
► Compression, backward composition, feature computation, and convolution speed-up.
► There are a few methods of such decomposition.
► They differ by efficiency of results and by computing complexity.