A hybrid heuristic for the rectilinear picture compression problem

In the rectilinear picture compression problem we aim at selecting a minimum number of rectangular submatrices of a binary matrix \(M\in \{0,1\}^{m\times n}\), such that (a) every submatrix is composed entirely of ones, and (b) every 1-valued entry of M is present in some submatrix. This problem is motivated by the compression of monochromatic images, the synthesis of DNA arrays, the manufacture of integrated circuits, and other additional applications that have been identified in the literature. In this work we study several integer programming formulations for this problem. To tackle large-sized matrices, we propose an integer-programming-based heuristic procedure, which is based on three simple ideas: we produce a set C of M of maximal rectangles composed entirely of ones, we group the 1-valued entries of M into a set of atomic rectangles R, and we compute an optimum cover of R using only rectangles of C. We test this procedure on real image data from publicly available datasets, where we observe that image resolutions up to \(1024 \times 1024\) are processed within a few seconds. We also resort to CCITT instances used in previous works with known optima, and find for these instances a solution within \(0.05\%\) of the optimum, outperforming the heuristic given by Litan et al.