A hybrid heuristic for the rectilinear picture compression problem

Ivo Koch; Javier Marenco

doi:10.1007/s10288-022-00515-3

Koch, Ivo; Marenco, Javier

2023-06-01 00:00:00

In the rectilinear picture compression problem we aim at selecting a minimum number of rectangular submatrices of a binary matrix M∈{0,1}m×n\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$M\in \{0,1\}^{m\times n}$$\end{document}, 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×1024\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$1024 \times 1024$$\end{document} 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%\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$0.05\%$$\end{document} of the optimum, outperforming the heuristic given by Litan et al.

http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

4OR Springer Journals

http://www.deepdyve.com/lp/springer-journals/a-hybrid-heuristic-for-the-rectilinear-picture-compression-problem-f31DwQJL75

$In the rectilinear picture compression problem we aim at selecting a minimum number of rectangular submatrices of a binary matrix M∈{0,1}m×n\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$M\in \{0,1\}^{m\times n}$$\end{document}, 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×1024\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$1024 \times 1024$$\end{document} 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%\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$0.05\%$$\end{document} of the optimum, outperforming the heuristic given by Litan et al.$

References (27)

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A hybrid heuristic for the rectilinear picture compression problem

A hybrid heuristic for the rectilinear picture compression problem

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A hybrid heuristic for the rectilinear picture compression problem

A hybrid heuristic for the rectilinear picture compression problem

References (27)

Abstract

Journal

Recommended Articles

There are no references for this article.

Our policy towards the use of cookies