undefined

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än

Organisaatiot ja tekijät

Centria-ammattikorkeakoulu

Pitkäkangas Ville Orcid -palvelun logo

Julkaisutyyppi

Julkaisumuoto

Artikkeli

Emojulkaisun tyyppi

Lehti

Artikkelin tyyppi

Alkuperäisartikkeli

Yleisö

Tieteellinen

Vertaisarvioitu

Vertaisarvioitu

OKM:n julkaisutyyppiluokitus

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Julkaisukanavan tiedot

Kustantaja

MDPI

Volyymi

14

Numero

13

Artikkelinumero

2615

Julkaisu­foorumi

84608

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ä