Against Expectations: A Simple Greedy Heuristic Outperforms Advanced Methods in Bitmap Decomposition
Julkaisuvuosi
2025
Tekijät
Pitkäkangas, Ville
Tiivistelmä
Partitioning rectangular and rectilinear shapes in n-dimensional binary images into the smallest set of axis-aligned n-cuboids is a fundamental problem in image analysis, pattern recognition, and computational geometry, with applications in object detection, shape simplification, and data compression. This paper introduces and evaluates four deterministic decomposition methods: pure greedy selection, greedy with backtracking, greedy with a priority queue, and an iterative integer linear programming (IILP) approach. These methods are benchmarked against three established baseline techniques across 13 diverse 1D–4D images (up to 8 × 8 × 8 × 8 elements), featuring holes, concavities, and varying orientations. Surprisingly, the simplest approach—a purely greedy heuristic selecting the largest unvisited region at each step—consistently achieved optimal or near-optimal decompositions, even for complex images, and maintained optimality under rotation without post-processing. By contrast, the more sophisticated methods (backtracking, prioritization, and IILP) exhibited trade-offs between speed and quality, with IILP adding overhead without superior results. Runtime testing showed IILP was on average ~37× slower than the fastest greedy method (ranging from ~3× to 100× slower). These findings highlight that a well-designed greedy strategy can outperform more complex algorithms for practical binary shape decomposition, offering a compelling balance between computational efficiency and solution quality in pattern recognition and image analysis.
Näytä enemmänOrganisaatiot ja tekijät
Julkaisutyyppi
Julkaisumuoto
Artikkeli
Emojulkaisun tyyppi
Lehti
Artikkelin tyyppi
Alkuperäisartikkeli
Yleisö
TieteellinenVertaisarvioitu
VertaisarvioituOKM:n julkaisutyyppiluokitus
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäJulkaisukanavan tiedot
Lehti
Kustantaja
Volyymi
14
Numero
13
Artikkelinumero
2615
ISSN
Julkaisufoorumi
Julkaisufoorumitaso
0
Avoin saatavuus
Avoin saatavuus kustantajan palvelussa
Kyllä
Julkaisukanavan avoin saatavuus
Kokonaan avoin julkaisukanava
Kustantajan version lisenssi
CC BY
Rinnakkaistallennettu
Ei
Muut tiedot
Tieteenalat
Matematiikka; Sähkö-, automaatio- ja tietoliikennetekniikka, elektroniikka
Avainsanat
[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object]
Julkaisumaa
Sveitsi
Kustantajan kansainvälisyys
Kansainvälinen
Kieli
englanti
Kansainvälinen yhteisjulkaisu
Ei
Yhteisjulkaisu yrityksen kanssa
Ei
DOI
10.3390/electronics14132615
Julkaisu kuuluu opetus- ja kulttuuriministeriön tiedonkeruuseen
Kyllä