A hybrid heuristic for the rectilinear picture compression problem

Ivo Koch () and Javier Marenco ()
Additional contact information
Ivo Koch: Universidad Nacional de General Sarmiento
Javier Marenco: Universidad Nacional de General Sarmiento

4OR, 2023, vol. 21, issue 2, No 6, 329-358

Abstract: Abstract 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}$$ M ∈ { 0 , 1 } m × 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$$ 1024 × 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\%$$ 0.05 % of the optimum, outperforming the heuristic given by Litan et al.

Keywords: Integer programming; Rectilinear picture compression problem; Compression of monochromatic images; Heuristics; 90C10; 90C59 (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-022-00515-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:21:y:2023:i:2:d:10.1007_s10288-022-00515-3

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-022-00515-3

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().