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

Höschl IV, Cyril ; Flusser, Jan

Kybernetika, Tome 55 (2019) no. 5, pp. 755-781

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2019-5-0755

Classification : 65D18
Keywords: 3D binary object; voxels; decomposition; rectangular blocks; sub-optimal algorithm; tripartite graph; maximum independent set

Bibliographie

[1] Berg, M. d., Cheong, O., Kreveld, M. v., Overmars, M.: Computational Geometry: Algorithms and Applications. 3rd Edition. Springer-Verlag TELOS, Santa Clara 2008. | DOI | MR

[2] Bron, C., Kerbosch, J.: Algorithm 457: Finding all cliques of an undirected graph. Commun. ACM 16 (1973), 9, 575-577. | DOI

[3] Campisi, P., Egiazarian, K.: Blind Image Deconvolution: Theory and Applications. CRC, 2007. | DOI | MR

[4] Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A.: Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization, Wiley 2011. | DOI | MR

[5] Dai, M., Baylou, P., Najim, M.: An efficient algorithm for computation of shape moments from run-length codes or chain codes. Pattern Recognition 25 (1992), 10, 1119-1128. | DOI

[6] Dielissen, V. J., Kaldewaij, A.: Rectangular partition is polynomial in two dimensions but np-complete in three. Inform. Process. Lett. 38 (1991), 1, 1-6. | DOI | MR

[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. | MR

[8] Edmonds, J., Karp, R. M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. Assoc. Comput. Machinery 19 (1972) 2, 248-264. | DOI | MR

[9] Eppstein, D.: 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 | MR

[10] Ferrari, L., Sankar, P. V., Sklansky, J.: Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, Image Process. 28 (1984), 1, 58-71. | DOI

[11] Flusser, J.: An adaptive method for image registration. Pattern Recognition 25 (1992), 1, 45-54. | DOI

[12] Flusser, J.: Refined moment calculation using image block representation. IEEE Trans. Image Process. 9 (2000), 11, 1977-1978. | DOI | MR

[13] Flusser, J., Suk, T., Zitová, B.: 2D and 3D Image Analysis by Moments. Wiley, 2016. | DOI

[14] Goldberg, A. V., Rao, S.: Beyond the flow decomposition barrier. J. Assoc. Comput. Machinery 45 (1998), 5, 783-797. | DOI | MR

[15] Goldberg, A. V., Tarjan, R. E.: A new approach to the maximum-flow problem. J. Assoc. Comput. Machinery 35 (1988), 4, 921-940. | DOI | MR

[16] Gourley, K. D., Green, D. M.: A polygon-to-rectangle conversion algorithm. IEEE Computer Graphics Appl. 3 (1983) 1, 31-36. | DOI

[17] Imai, H., Asano, T.: Efficient algorithms for geometric graph search problems. SIAM J. Comput. 15 (1986), 2, 478-494. | DOI | MR

[18] Jain, A., Thormählen, T., Ritschel, T., Seidel, H.-P.: Exploring shape variations by 3d-model decomposition and part-based recombination. Computer Graphics Forum 31 (2012), (2pt3), 631-640. | DOI

[19] Kawaguchi, E., Endo, T.: 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

[20] Keil, J. M.: Polygon decomposition. In: Handbook of Computational Geometry, Elsevier, 2000, pp. 491-518. | DOI | MR

[21] Levin, A., Fergus, R., Durand, F., Freeman, W. T.: 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

[22] Li, B. C.: A new computation of geometric moments. Pattern Recognition 26 (1993), 1, 109-113. | DOI | MR

[23] Liou, W., Tan, J., Lee, R.: 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

[24] Jr., W. Lipski, Lodi, E., Luccio, F., Mugnai, C., Pagli, L.: On two-dimensional data organization II. In: Fundamenta Informaticae, Vol. II of Annales Societatis Mathematicae Polonae, Series IV, 1979, pp. 245-260. | DOI | MR

[25] Marchand-Maillet, S., Sharaiha, Y. M.: Binary Digital Image Processing: A Discrete Approach. Academic Press, 1999. | DOI | MR

[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.: 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 | MR

[28] Neal, F. B., Russ, J. C.: Measuring Shape. CRC Pres, 2012. | DOI

[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.: Efficient and accurate computation of geometric moments on gray-scale images. Pattern Recognition 41 (2008), 6, 1895-1904. | DOI

[31] Ren, Z., Yuan, J., Liu, W.: Minimum near-convex shape decomposition. IEEE Trans. on Pattern Analysis and Machine Intelligence 35 (2013), 2546-2552. | DOI

[32] Shilane, P., Min, P., Kazhdan, M., Funkhouser, T.: The Princeton Shape Benchmark. In: Proc. Shape Modelling Applications, 2004. | DOI

[33] Siddiqi, K., Zhang, J., Macrini, D., Shokoufandeh, A., Bouix, S., Dickinson, S.: Retrieving articulated 3-d models using medial surfaces. Mach. Vision Appl. 19 (2008), 4, 261-275. | DOI

[34] Sivignon, I., Coeurjolly, D.: Minimum decomposition of a digital surface into digital plane segments is NP-hard. Discrete Appl. Math. 157 (2009), 3, 558-570. | DOI | MR

[35] Sossa-Azuela, J. H., Yáñez-Márquez, C., Santiago, J. L. Díaz de León: Computing geometric moments using morphological erosion. Pattern Recognition 34 (2001), 2, 271-276. | DOI

[36] Spiliotis, I. M., Boutalis, Y. S.: Parameterized real-time moment computation on gray images using block techniques. J. Real-Time Image Process. 6 (2011), 2, 81-91. | DOI

[37] Spiliotis, I. M., Mertzios, B. G.: Real-time computation of two-dimensional moments on binary images using image block representation. IEEE Trans. Image Process. 7 (1998), 11, 1609-1615. | DOI

[38] Suk, T., Flusser, J.: Refined morphological methods of moment computation. In: 20th International Conference on Pattern Recognition ICPR'10, IEEE Computer Society, 2010, pp. 966-970. | DOI

[39] Suk, T., Höschl, C. IV, Flusser, J.: Decomposition of binary images – A survey and comparison. Pattern Recognition 45 (2012), 12, 4279-4291. | DOI

[40] Wu, C.-H., Horng, S.-J., Lee, P.-Z.: A new computation of shape moments via quadtree decomposition. Pattern Recognition 34 (2001), 7, 1319-1330. | DOI

[41] Zakaria, M. F., Vroomen, L. J., Zsombor-Murray, P., Kessel, J. M. van: Fast algorithm for the computation of moment invariants. Pattern Recognition 20 (1987), 6, 639-643. | DOI

[42] Zhou, Y., Yin, K., Huang, H., Zhang, H., Gong, M., Cohen-Or, D.: Generalized cylinder decomposition. ACM Trans. Graph. 34 (2015) 6, 171:1-171:14. | DOI