Problem formulation: How to decompose a binary shape in a discrete plane into rectilinear rectangles (blocks) such that their number is minimized?

Significance: The decomposition can be used for compression, efficient computation of various object features and transformations, fast computation of convolution, and in many other operations. Complexity of these algorithms is often proportional to the number of the rectangles.

Trade-off: The complexity of the decomposition itself is usually high for the methods yielding a low number of blocks and vice versa. Looking for a well-balanced algorithm is a relevant task.

Methods

1. Pixel-wise decomposition. This is not a meaningful decomposition since each pixel itself is considered as a block. This “decomposition” maximizes the number of blocks while minimizing the decomposition time.
2. Delta-method. Here, the blocks are lines or line segments.  It is the same as run-length encoding (RLE). It is very fast, but the number of blocks is uselessly high.
3. Generalized delta-method.  In the first step, delta-method is applied. In the second step, the line segments with the same beginning and end are grouped together. This is only slightly slower than the basic delta but yields much less blocks. 
4. Quad-tree decomposition divides the image into quadrants. If the quadrant contains the background pixels or the object pixels only, it is not further divided. If it contains both background and object pixels, it is divided into quadrants. The algorithm is repeated recursively until homogeneous quadrants are reached. This hierarchical decomposition is fast and can be parallelized  but generally produces too many blocks. An advantage is that all blocks are squares and many of them have the same size, which enables an efficient encoding and compression.
5. Morphological decomposition. The method places the largest rectangle inscribed in the object.  Then the largest rectangle inscribed in the rest of the object is found and this procedure is repeated until all object pixels are covered by the rectangles. The method is called „morphological“ because the centers and the dimensions of the rectangles are found by means of morphological erosion of the object. Equivalently, maximum of the distance transform can define the centers. This decomposition is slow and the number of blocks is usually far from the minimum.
6. Optimal decomposition. This method has been proven to minimize the number of blocks. It works in two stages.

Stage 1:

• Find all concave vertices of the object.
• Find all pairs of cogrid concave vertices.  Two points are cogrid if their x or y coordinates are the same.
• Construct all possible chords. The chord is a line connecting two cogrid concave vertices and lying entirely in the interior of the object.
• Find the maximum set of non-intersecting chords. This step can be resolved by means of graph theory. Construct a graph the nodes of which are all chords. Two nodes are connected with an edge if the corresponding chords have a common point. This graph is a bipartite graph since two horizontal/vertical chords never intersect each other. Finding the maximum set of non-intersecting chords is equivalent to finding the maximum independent graph nodes. In a bipartite graph, this is solvable in a polynomial time.
• Cut the object in all chords from the maximal set.
• If all resulting segments are rectangles, then STOP. If not, proceed to Stage 2.

Stage 1 of the optimal decomposition. The maximal set of the non-intersecting chords is found by means of graph theory and defines the cuts.

Stage 2:

Take the segment that is not a rectangle. It must have some concave vertices but no cogrid concave vertices. From each concave vertex, do a single cut in arbitrary direction.

This method is optimal in terms of the block numbers but the decomposition time is much higher than that of Delta and Quadtree. The optimal decomposition may not be unique; to choose one you may add other criterions such as minimizing the cut length and/or avoiding „thin“ rectangles.    For most „standard“ objects, the Generalized Delta method provides the best trade-off between the block numbers and time complexity.

An experimental comparison of decomposition methods 

(a) – morphological decomposition, 697 blocks; (b) – generalized Delta, 497 blocks; (c) – quadtree, 2513 blocks; (d) – optimal, 476 blocks.

Some objects cannot be efficiently decomposed.

Decomposition of 3D voxelized bodies

All methods can be readily adapted into 3D, except the optimal method. The minimum decomposition problem in 3D is NP-complete. A polynomial approximation of the optimal solution is available [2].

References

[1] Suk T., Hoschl C., Flusser J. : "Decomposition of Binary Images — A Survey and Comparison", Pattern Recognition, vol. 45, No. 12, pp. 4279­4291, 2012

[2] Hoschl C., Flusser J.: "Close-to-Optimal Algorithm for Rectangular Decomposition of 3D Shapes", Kybernetika, vol. 55, No. 5, pp. 755-781, 2019

Contact person: Jan Flusser