undefined

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 more

Organizations and authors

Publication type

Publication format

Article

Parent publication type

Journal

Article type

Original article

Audience

Scientific

Peer-reviewed

Peer-Reviewed

MINEDU's publication type classification code

A1 Journal article (refereed), original research

Publication channel information

Publisher

MDPI

Volume

14

Issue

13

Article number

2615

​Publication forum

84608

​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