Close-to-optimal algorithm for rectangular decomposition of 3D shapes

Cyril Höschl IV; Jan Flusser

Kybernetika (2019)

  • Volume: 55, Issue: 5, page 755-781
  • ISSN: 0023-5954

Abstract

top
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 sub-optimal 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 significant level. We also discuss potential applications of the method in image processing.

How to cite

top

Höschl IV, Cyril, and Flusser, Jan. "Close-to-optimal algorithm for rectangular decomposition of 3D shapes." Kybernetika 55.5 (2019): 755-781. <http://eudml.org/doc/295058>.

@article{HöschlIV2019,
abstract = {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 sub-optimal 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 significant level. We also discuss potential applications of the method in image processing.},
author = {Höschl IV, Cyril, Flusser, Jan},
journal = {Kybernetika},
keywords = {3D binary object; voxels; decomposition; rectangular blocks; sub-optimal algorithm; tripartite graph; maximum independent set},
language = {eng},
number = {5},
pages = {755-781},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Close-to-optimal algorithm for rectangular decomposition of 3D shapes},
url = {http://eudml.org/doc/295058},
volume = {55},
year = {2019},
}

TY - JOUR
AU - Höschl IV, Cyril
AU - Flusser, Jan
TI - Close-to-optimal algorithm for rectangular decomposition of 3D shapes
JO - Kybernetika
PY - 2019
PB - Institute of Information Theory and Automation AS CR
VL - 55
IS - 5
SP - 755
EP - 781
AB - 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 sub-optimal 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 significant level. We also discuss potential applications of the method in image processing.
LA - eng
KW - 3D binary object; voxels; decomposition; rectangular blocks; sub-optimal algorithm; tripartite graph; maximum independent set
UR - http://eudml.org/doc/295058
ER -

References

top
  1. Berg, M. d., Cheong, O., Kreveld, M. v., Overmars, M., 10.1007/978-3-540-77974-2, Springer-Verlag TELOS, Santa Clara 2008. MR2723879DOI10.1007/978-3-540-77974-2
  2. Bron, C., Kerbosch, J., 10.1145/362342.362367, Commun. ACM 16 (1973), 9, 575-577. DOI10.1145/362342.362367
  3. Campisi, P., Egiazarian, K., 10.1201/9781420007299, CRC, 2007. MR2404093DOI10.1201/9781420007299
  4. Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A., 10.1002/9781118033142.scard, Wiley Series in Discrete Mathematics and Optimization, Wiley 2011. MR1490579DOI10.1002/9781118033142.scard
  5. Dai, M., Baylou, P., Najim, M., 10.1016/0031-3203(92)90015-b, Pattern Recognition 25 (1992), 10, 1119-1128. DOI10.1016/0031-3203(92)90015-b
  6. Dielissen, V. J., Kaldewaij, A., 10.1016/0020-0190(91)90207-x, Inform. Process. Lett. 38 (1991), 1, 1-6. MR1103693DOI10.1016/0020-0190(91)90207-x
  7. Dinic, E. A., Algorithm for solution of a problem of maximum flow in a network with power estimation., Soviet Math. Doklady 11 (1970), 1277-1280. MR0287976
  8. Edmonds, J., Karp, R. M., 10.1145/321694.321699, J. Assoc. Comput. Machinery 19 (1972) 2, 248-264. MR0266680DOI10.1145/321694.321699
  9. Eppstein, D., 10.1007/978-3-642-11409-0_1, In: 35th International Workshop on Graph-Theoretic Concepts in Computer Science WG'09, Vol. LNCS 5911, Springer, 2009, pp. 1-16. MR2587695DOI10.1007/978-3-642-11409-0_1
  10. Ferrari, L., Sankar, P. V., Sklansky, J., 10.1016/0734-189x(84)90139-7, Computer Vision, Graphics, Image Process. 28 (1984), 1, 58-71. DOI10.1016/0734-189x(84)90139-7
  11. Flusser, J., 10.1016/0031-3203(92)90005-4, Pattern Recognition 25 (1992), 1, 45-54. DOI10.1016/0031-3203(92)90005-4
  12. Flusser, J., 10.1109/83.877219, IEEE Trans. Image Process. 9 (2000), 11, 1977-1978. MR1818456DOI10.1109/83.877219
  13. Flusser, J., Suk, T., Zitová, B., 10.1002/9781119039402, Wiley, 2016. DOI10.1002/9781119039402
  14. Goldberg, A. V., Rao, S., 10.1145/290179.290181, J. Assoc. Comput. Machinery 45 (1998), 5, 783-797. MR1668151DOI10.1145/290179.290181
  15. Goldberg, A. V., Tarjan, R. E., 10.1145/48014.61051, J. Assoc. Comput. Machinery 35 (1988), 4, 921-940. MR1072405DOI10.1145/48014.61051
  16. Gourley, K. D., Green, D. M., 10.1109/mcg.1983.262975, IEEE Computer Graphics Appl. 3 (1983) 1, 31-36. DOI10.1109/mcg.1983.262975
  17. Imai, H., Asano, T., 10.1137/0215033, SIAM J. Comput. 15 (1986), 2, 478-494. MR0837597DOI10.1137/0215033
  18. Jain, A., Thormählen, T., Ritschel, T., Seidel, H.-P., 10.1111/j.1467-8659.2012.03042.x, Computer Graphics Forum 31 (2012), (2pt3), 631-640. DOI10.1111/j.1467-8659.2012.03042.x
  19. Kawaguchi, E., Endo, T., 10.1109/tpami.1980.4766967, IEEE Trans. Pattern Analysis Machine Intell. 2 (1980), 1, 27-35. DOI10.1109/tpami.1980.4766967
  20. Keil, J. M., 10.1016/b978-044482537-7/50012-7, In: Handbook of Computational Geometry, Elsevier, 2000, pp. 491-518. MR1746683DOI10.1016/b978-044482537-7/50012-7
  21. Levin, A., Fergus, R., Durand, F., Freeman, W. T., 10.1145/1275808.1276464, In: Special Interest Group on Computer Graphics and Interactive Techniques Conference SIGGRAPH'07, ACM, New York 2007. DOI10.1145/1275808.1276464
  22. Li, B. C., 10.1016/0031-3203(93)90092-b, Pattern Recognition 26 (1993), 1, 109-113. MR1354114DOI10.1016/0031-3203(93)90092-b
  23. Liou, W., Tan, J., Lee, R., 10.1145/73833.73871, In: Proc. Fifth Annual ACM symposium on Computational Geometry SoCG'89, ACM, New York 1989, pp. 344-353. DOI10.1145/73833.73871
  24. Jr., W. Lipski, Lodi, E., Luccio, F., Mugnai, C., Pagli, L., 10.1007/978-1-4613-9323-8_18, In: Fundamenta Informaticae, Vol. II of Annales Societatis Mathematicae Polonae, Series IV, 1979, pp. 245-260. MR0573990DOI10.1007/978-1-4613-9323-8_18
  25. Marchand-Maillet, S., Sharaiha, Y. M., 10.1016/b978-012470505-0/50007-1, Academic Press, 1999. MR1734820DOI10.1016/b978-012470505-0/50007-1
  26. Meagher, D., Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-d Objects by Computer., Tech. Rep. IPL-TR-80-111, Rensselaer Polytechnic Institute 1980. 
  27. Murali, T. M., Agarwal, P. K., Vitter, J. S., 10.1007/3-540-68530-8_18, In: Proc. 6th Annual European Symposium on Algorithms, ESA '98, Springer-Verlag, London 1998, pp. 211-222. MR1683364DOI10.1007/3-540-68530-8_18
  28. Neal, F. B., Russ, J. C., 10.1201/b12092, CRC Pres, 2012. DOI10.1201/b12092
  29. Ohtsuki, T., Minimum dissection of rectilinear regions., In: Proc. IEEE International Conference on Circuits and Systems ISCAS'82, IEEE, 1982, pp. 1210-1213. 
  30. Papakostas, G. A., Karakasis, E. G., Koulouriotis, D. E., 10.1016/j.patcog.2007.11.015, Pattern Recognition 41 (2008), 6, 1895-1904. DOI10.1016/j.patcog.2007.11.015
  31. Ren, Z., Yuan, J., Liu, W., 10.1109/tpami.2013.67, IEEE Trans. on Pattern Analysis and Machine Intelligence 35 (2013), 2546-2552. DOI10.1109/tpami.2013.67
  32. Shilane, P., Min, P., Kazhdan, M., Funkhouser, T., 10.1109/smi.2004.1314504, In: Proc. Shape Modelling Applications, 2004. DOI10.1109/smi.2004.1314504
  33. Siddiqi, K., Zhang, J., Macrini, D., Shokoufandeh, A., Bouix, S., Dickinson, S., 10.1007/s00138-007-0097-8, Mach. Vision Appl. 19 (2008), 4, 261-275. DOI10.1007/s00138-007-0097-8
  34. Sivignon, I., Coeurjolly, D., 10.1016/j.dam.2008.05.028, Discrete Appl. Math. 157 (2009), 3, 558-570. MR2479146DOI10.1016/j.dam.2008.05.028
  35. Sossa-Azuela, J. H., Yáñez-Márquez, C., Santiago, J. L. Díaz de León, 10.1016/s0031-3203(99)00213-7, Pattern Recognition 34 (2001), 2, 271-276. DOI10.1016/s0031-3203(99)00213-7
  36. Spiliotis, I. M., Boutalis, Y. S., 10.1007/s11554-009-0142-0, J. Real-Time Image Process. 6 (2011), 2, 81-91. DOI10.1007/s11554-009-0142-0
  37. Spiliotis, I. M., Mertzios, B. G., 10.1109/83.725368, IEEE Trans. Image Process. 7 (1998), 11, 1609-1615. DOI10.1109/83.725368
  38. Suk, T., Flusser, J., 10.1109/icpr.2010.242, In: 20th International Conference on Pattern Recognition ICPR'10, IEEE Computer Society, 2010, pp. 966-970. DOI10.1109/icpr.2010.242
  39. Suk, T., Höschl, C. IV, Flusser, J., 10.1016/j.patcog.2012.05.012, Pattern Recognition 45 (2012), 12, 4279-4291. DOI10.1016/j.patcog.2012.05.012
  40. Wu, C.-H., Horng, S.-J., Lee, P.-Z., 10.1016/s0031-3203(00)00100-x, Pattern Recognition 34 (2001), 7, 1319-1330. DOI10.1016/s0031-3203(00)00100-x
  41. Zakaria, M. F., Vroomen, L. J., Zsombor-Murray, P., Kessel, J. M. van, 10.1016/0031-3203(87)90033-1, Pattern Recognition 20 (1987), 6, 639-643. DOI10.1016/0031-3203(87)90033-1
  42. Zhou, Y., Yin, K., Huang, H., Zhang, H., Gong, M., Cohen-Or, D., 10.1145/2816795.2818074, ACM Trans. Graph. 34 (2015) 6, 171:1-171:14. DOI10.1145/2816795.2818074

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.