Publication details
Conference Paper (international conference)
Decomposition of 3D Binary Objects into Rectangular Blocks
,
: Digital Image Computing: Techniques and Applications (DICTA) 2016
: DICTA 2016 : Digital Image Computing: Techniques and Applications, (Gold Coast, AU, 20161130)
: GA15-16928S, GA ČR
: Algorithm design and analysis, Particle separators, Image coding
: http://library.utia.cas.cz/separaty/2016/ZOI/flusser-0468204.pdf
(eng): In this paper we propose a novel algorithm for a decomposition of 3D binary shapes to rectangular blocks. The aim is to minimize the number of blocks. Theoretically optimal brute-force algorithm is known to be NP-hard and practically infeasible. We introduce its polynomial sub-optimal approximation, which transforms the decomposition problem onto a graph-theoretical problem. We show by extensive experiments that the proposed method outperforms the the octree decomposition in terms of the number of blocks on statistically significant level. We also discuss potential applications of the method in image processing.
: JD