0518087 20240903170644.320191217235959.9 000509991200001 85079682794 10.14736/kyb-2019-5-0755 CLOSE-TO-OPTIMAL ALGORITHM FOR RECTANGULAR DECOMPOSITION OF 3D SHAPES 27 s. P cav_un_epca*02971630023-5954Kybernetika555 (2019)755-781Ústav teorie informace a automatizace AV ČR, v. v. i. 3D binary object voxels decomposition cav_un_auth*0282545 Höschl Cyril UTIA-B Zpracování obrazové informace Department of Image Processing ZOI ZOI Department of Image Processing CZ Ústav teorie informace a automatizace AV ČR, v. v. i. cav_un_auth*0101087 Flusser Jan UTIA-B Zpracování obrazové informace Department of Image Processing ZOI ZOI Department of Image Processing Ústav teorie informace a automatizace AV ČR, v. v. i. http://library.utia.cas.cz/separaty/2019/ZOI/flusser-0518087.pdf https://www.kybernetika.cz/content/2019/5/755 cav_un_auth*0360229 GA18-07247S GA ČR 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 suboptimal polynomial heuristic approximation, which transforms the decomposition problem onto a graph-theoretical problem. We compare its performance with the state of the art Octree and Delta methods. We show by extensive experiments that the proposed method outperforms the existing ones in terms of the number of blocks on statistically signifficant level. We also discuss potential applications of the method in image processing. WOS JD 10000 10200 10201 2020 2 4 A hod sml 4ah 4as 20231122144550.7 RVO:67985556 http://hdl.handle.net/11104/0303985 1 Department of Image Processing UTIA-B 10200 COMPUTER SCIENCE, THEORY & METHODS S Copyright Form 20190512 2 Article Physiology A COMPUTERSCIENCE.CYBERNETICS 0.608 0.12 12.3 0.00084 0.215 778 43 0.241 27.97 0.81 146 Q3 0.582 50 Q4 15.751 6.8 Q4 Q4 0.16 Q4 6.818 2019 Soubory v repozitáři: flusser-0518087.pdf, flusser-0518087-CopyrightForm5004.pdf 85079682794 SCOPUS PUBMED 000509991200001 WOS cav_un_epca*0297163 Kybernetika 0023-5954 Roč. 55 č. 5 2019 755 781 Ústav teorie informace a automatizace AV ČR, v. v. i.