Institute of Information Theory and Automation

You are here

Publication details

Decomposition of 3D Binary Objects into Rectangular Blocks

Conference Paper (international conference)

Höschl Cyril, Flusser Jan

serial: Digital Image Computing: Techniques and Applications (DICTA) 2016

action: DICTA 2016 : Digital Image Computing: Techniques and Applications, (Gold Coast, AU, 20161130)

project(s): GA15-16928S, GA ČR

keywords: Algorithm design and analysis, Particle separators, Image coding

preview: Download

abstract (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.


2012-12-21 16:10