Against Expectations: A Simple Greedy Heuristic Outperforms Advanced Methods in Bitmap Decomposition
Year of publication
2025
Authors
Pitkäkangas, Ville
Abstract
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.
Show moreOrganizations and authors
Publication type
Publication format
Article
Parent publication type
Journal
Article type
Original article
Audience
ScientificPeer-reviewed
Peer-ReviewedMINEDU's publication type classification code
A1 Journal article (refereed), original researchPublication channel information
Journal
Publisher
Volume
14
Issue
13
Article number
2615
ISSN
Publication forum
Publication forum level
0
Open access
Open access in the publisher’s service
Yes
Open access of publication channel
Fully open publication channel
License of the publisher’s version
CC BY
Self-archived
No
Other information
Fields of science
Mathematics; Electronic, automation and communications engineering, electronics
Keywords
[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object]
Publication country
Switzerland
Internationality of the publisher
International
Language
English
International co-publication
No
Co-publication with a company
No
DOI
10.3390/electronics14132615
The publication is included in the Ministry of Education and Culture’s Publication data collection
Yes