Kybernetika 55 no. 5, 755-781, 2019

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

Cyril Höschl IV and Jan FlusserDOI: 10.14736/kyb-2019-5-0755

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.

Keywords:

decomposition, 3D binary object, voxels, rectangular blocks, sub-optimal algorithm, tripartite graph, maximum independent set

Classification:

65D18

paper.pdf

References:

  1. M. d. Berg, O. Cheong, M. v. Kreveld and M. Overmars: Computational Geometry: Algorithms and Applications. 3rd Edition. Springer-Verlag TELOS, Santa Clara 2008.   DOI:10.1007/978-3-540-77974-2
  2. C. Bron and J. Kerbosch: Algorithm 457: Finding all cliques of an undirected graph. Commun. ACM 16 (1973), 9, 575-577.   DOI:10.1145/362342.362367
  3. P. Campisi and K. Egiazarian: Blind Image Deconvolution: {T}heory and Applications. CRC, 2007.   DOI:10.1201/9781420007299
  4. W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver: Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization, Wiley 2011.   DOI:10.1002/9781118033142.scard
  5. M. Dai, P. Baylou and M. Najim: An efficient algorithm for computation of shape moments from run-length codes or chain codes. Pattern Recognition 25 (1992), 10, 1119-1128.   DOI:10.1016/0031-3203(92)90015-b
  6. V. J. Dielissen and A. Kaldewaij: Rectangular partition is polynomial in two dimensions but np-complete in three. Inform. Process. Lett. 38 (1991), 1, 1-6.   DOI:10.1016/0020-0190(91)90207-x
  7. E. A. Dinic: Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady 11 (1970), 1277-1280.   CrossRef
  8. J. Edmonds and R. M. Karp: Theoretical improvements in algorithmic efficiency for network flow problems. J. Assoc. Comput. Machinery 19 (1972) 2, 248-264.   DOI:10.1145/321694.321699
  9. D. Eppstein: Graph-theoretic solutions to computational geometry problems. In: 35th International Workshop on Graph-Theoretic Concepts in Computer Science WG'09, Vol. LNCS 5911, Springer, 2009, pp. 1-16.   DOI:10.1007/978-3-642-11409-0\_1
  10. L. Ferrari, P. V. Sankar and J. Sklansky: Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, Image Process. 28 (1984), 1, 58-71.   DOI:10.1016/0734-189x(84)90139-7
  11. J. Flusser: An adaptive method for image registration. Pattern Recognition 25 (1992), 1, 45-54.   DOI:10.1016/0031-3203(92)90005-4
  12. J. Flusser: Refined moment calculation using image block representation. IEEE Trans. Image Process. 9 (2000), 11, 1977-1978.   DOI:10.1109/83.877219
  13. J. Flusser, T. Suk and B. Zitová: 2D and 3D Image Analysis by Moments. Wiley, 2016.   DOI:10.1002/9781119039402
  14. A. V. Goldberg and S. Rao: Beyond the flow decomposition barrier. J. Assoc. Comput. Machinery 45 (1998), 5, 783-797.   DOI:10.1145/290179.290181
  15. A. V. Goldberg and R. E. Tarjan: A new approach to the maximum-flow problem. J. Assoc. Comput. Machinery 35 (1988), 4, 921-940.   DOI:10.1145/48014.61051
  16. K. D. Gourley and D. M. Green: A polygon-to-rectangle conversion algorithm. IEEE Computer Graphics Appl. 3 (1983) 1, 31-36.   DOI:10.1109/mcg.1983.262975
  17. H. Imai and T. Asano: Efficient algorithms for geometric graph search problems. SIAM J. Comput. 15 (1986), 2, 478-494.   DOI:10.1137/0215033
  18. A. Jain, T. Thormählen, T. Ritschel and H.-P. Seidel: Exploring shape variations by 3d-model decomposition and part-based recombination. Computer Graphics Forum 31 (2012), (2pt3), 631-640.   DOI:10.1111/j.1467-8659.2012.03042.x
  19. E. Kawaguchi and T. Endo: On a method of binary-picture representation and its application to data compression. IEEE Trans. Pattern Analysis Machine Intell. 2 (1980), 1, 27-35.   DOI:10.1109/tpami.1980.4766967
  20. J. M. Keil: Polygon decomposition. In: Handbook of Computational Geometry, Elsevier, 2000, pp. 491-518.   DOI:10.1016/b978-044482537-7/50012-7
  21. A. Levin, R. Fergus, F. Durand and W. T. Freeman: Image and depth from a conventional camera with a coded aperture. In: Special Interest Group on Computer Graphics and Interactive Techniques Conference SIGGRAPH'07, ACM, New York 2007.   DOI:10.1145/1275808.1276464
  22. B. C. Li: A new computation of geometric moments. Pattern Recognition 26 (1993), 1, 109-113.   DOI:10.1016/0031-3203(93)90092-b
  23. W. Liou, J. Tan and R. Lee: Minimum partitioning simple rectilinear polygons in $O(n \log \log n)-$time. In: Proc. Fifth Annual ACM symposium on Computational Geometry SoCG'89, ACM, New York 1989, pp. 344-353.   DOI:10.1145/73833.73871
  24. W. Lipski Jr., E. Lodi, F. Luccio, C. Mugnai and L. Pagli: On two-dimensional data organization {II}. In: Fundamenta Informaticae, Vol. II of Annales Societatis Mathematicae Polonae, Series IV, 1979, pp. 245-260.   DOI:10.1007/978-1-4613-9323-8\_18
  25. S. Marchand-Maillet and Y. M. Sharaiha: Binary Digital Image Processing: A Discrete Approach. Academic Press, 1999.   DOI:10.1016/b978-012470505-0/50007-1
  26. D. Meagher: 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.   CrossRef
  27. T. M. Murali, P. K. Agarwal and J. S. Vitter: Constructing binary space partitions for orthogonal rectangles in practice. In: Proc. 6th Annual European Symposium on Algorithms, ESA '98, Springer-Verlag, London 1998, pp. 211-222.   DOI:10.1007/3-540-68530-8\_18
  28. F. B. Neal and J. C. Russ: Measuring Shape. CRC Pres, 2012.   DOI:10.1201/b12092
  29. T. Ohtsuki: Minimum dissection of rectilinear regions. In: Proc. IEEE International Conference on Circuits and Systems ISCAS'82, IEEE, 1982, pp. 1210-1213.   CrossRef
  30. G. A. Papakostas, E. G. Karakasis and D. E. Koulouriotis: Efficient and accurate computation of geometric moments on gray-scale images. Pattern Recognition 41 (2008), 6, 1895-1904.   DOI:10.1016/j.patcog.2007.11.015
  31. Z. Ren, J. Yuan and W. Liu: Minimum near-convex shape decomposition. IEEE Trans. on Pattern Analysis and Machine Intelligence 35 (2013), 2546-2552.   DOI:10.1109/tpami.2013.67
  32. P. Shilane, P. Min, M. Kazhdan and T. Funkhouser: The Princeton Shape Benchmark. In: Proc. Shape Modelling Applications, 2004.   DOI:10.1109/smi.2004.1314504
  33. K. Siddiqi, J. Zhang, D. Macrini, A. Shokoufandeh, S. Bouix and S. Dickinson: Retrieving articulated 3-d models using medial surfaces. Mach. Vision Appl. 19 (2008), 4, 261-275.   DOI:10.1007/s00138-007-0097-8
  34. I. Sivignon and D. Coeurjolly: Minimum decomposition of a digital surface into digital plane segments is NP-hard. Discrete Appl. Math. 157 (2009), 3, 558-570.   DOI:10.1016/j.dam.2008.05.028
  35. J. H. Sossa-Azuela, C. Yáñez-Márquez and J. L. Díaz de León Santiago: Computing geometric moments using morphological erosion. Pattern Recognition 34 (2001), 2, 271-276.   DOI:10.1016/s0031-3203(99)00213-7
  36. I. M. Spiliotis and Y. S. Boutalis: Parameterized real-time moment computation on gray images using block techniques. J. Real-Time Image Process. 6 (2011), 2, 81-91.   DOI:10.1007/s11554-009-0142-0
  37. I. M. Spiliotis and B. G. Mertzios: Real-time computation of two-dimensional moments on binary images using image block representation. IEEE Trans. Image Process. 7 (1998), 11, 1609-1615.   DOI:10.1109/83.725368
  38. T. Suk and J. Flusser: Refined morphological methods of moment computation. In: 20th International Conference on Pattern Recognition ICPR'10, IEEE Computer Society, 2010, pp. 966-970.   DOI:10.1109/icpr.2010.242
  39. T. Suk, C. {Höschl IV} and J. Flusser: Decomposition of binary images - {A} survey and comparison. Pattern Recognition 45 (2012), 12, 4279-4291.   DOI:10.1016/j.patcog.2012.05.012
  40. C.-H. Wu, S.-J. Horng and P.-Z. Lee: A new computation of shape moments via quadtree decomposition. Pattern Recognition 34 (2001), 7, 1319-1330.   DOI:10.1016/s0031-3203(00)00100-x
  41. M. F. Zakaria, L. J. Vroomen, P. Zsombor-Murray and J. M. van Kessel: Fast algorithm for the computation of moment invariants. Pattern Recognition 20 (1987), 6, 639-643.   DOI:10.1016/0031-3203(87)90033-1
  42. Y. Zhou, K. Yin, H. Huang, H. Zhang, M. Gong and D. Cohen-Or: Generalized cylinder decomposition. ACM Trans. Graph. 34 (2015) 6, 171:1-171:14.   DOI:10.1145/2816795.2818074