Close-to-optimal algorithm for rectangular decomposition of 3D shapes. (English) Zbl 1513.65036

Summary: 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.


65D18 Numerical aspects of computer graphics, image analysis, and computational geometry


Algorithm 457
Full Text: DOI Link


[1] Berg, M. d.; Cheong, O.; Kreveld, M. v.; Overmars, M., Computational Geometry: Algorithms and Applications. 3rd Edition., Springer-Verlag TELOS, Santa Clara 2008 · Zbl 1140.68069 · doi:10.1007/978-3-540-77974-2
[2] Bron, C.; Kerbosch, J., Algorithm 457: Finding all cliques of an undirected graph., Commun. ACM 16 (1973), 9, 575-577 · Zbl 0261.68018 · doi:10.1145/362342.362367
[3] Campisi, P.; Egiazarian, K., Blind Image Deconvolution: Theory and Applications., CRC, 2007 · Zbl 1160.68668 · doi:10.1201/9781420007299
[4] Cook, W.; Cunningham, W.; Pulleyblank, W.; Schrijver, A., Combinatorial Optimization., Wiley Series in Discrete Mathematics and Optimization, Wiley 2011 · doi:10.1002/9781118033142.scard
[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:10.1016/0031-3203(92)90015-b
[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 · Zbl 0732.68050 · doi:10.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 · Zbl 0219.90046
[8] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems., J. Assoc. Comput. Machinery 19 (1972) 2, 248-264 · Zbl 0318.90024 · doi:10.1145/321694.321699
[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 · Zbl 1273.68391 · doi:10.1007/978-3-642-11409-0_1
[10] Ferrari, L.; Sankar, P. V.; Sklansky, J., Minimal rectangular partitions of digitized blobs., Computer Vision, Graphics, Image Process. 28 (1984), 1, 58-71 · Zbl 0599.68051 · doi:10.1016/0734-189x(84)90139-7
[11] Flusser, J., An adaptive method for image registration., Pattern Recognition 25 (1992), 1, 45-54 · doi:10.1016/0031-3203(92)90005-4
[12] Flusser, J., Refined moment calculation using image block representation., IEEE Trans. Image Process. 9 (2000), 11, 1977-1978 · Zbl 0962.94017 · doi:10.1109/83.877219
[13] Flusser, J.; Suk, T.; Zitová, B., 2D and 3D Image Analysis by Moments., Wiley, 2016 · doi:10.1002/9781119039402
[14] Goldberg, A. V.; Rao, S., Beyond the flow decomposition barrier., J. Assoc. Comput. Machinery 45 (1998), 5, 783-797 · Zbl 1064.90567 · doi:10.1145/290179.290181
[15] Goldberg, A. V.; Tarjan, R. E., A new approach to the maximum-flow problem., J. Assoc. Comput. Machinery 35 (1988), 4, 921-940 · Zbl 0661.90031 · doi:10.1145/48014.61051
[16] Gourley, K. D.; Green, D. M., A polygon-to-rectangle conversion algorithm., IEEE Computer Graphics Appl. 3 (1983) 1, 31-36 · doi:10.1109/mcg.1983.262975
[17] Imai, H.; Asano, T., Efficient algorithms for geometric graph search problems., SIAM J. Comput. 15 (1986), 2, 478-494 · Zbl 0591.68068 · doi:10.1137/0215033
[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:10.1111/j.1467-8659.2012.03042.x
[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 · Zbl 0436.68062 · doi:10.1109/tpami.1980.4766967
[20] Keil, J. M., Polygon decomposition., In: Handbook of Computational Geometry, Elsevier, 2000, pp. 491-518 · Zbl 0948.68189 · doi:10.1016/b978-044482537-7/50012-7
[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:10.1145/1275808.1276464
[22] Li, B. C., A new computation of geometric moments., Pattern Recognition 26 (1993), 1, 109-113 · doi:10.1016/0031-3203(93)90092-b
[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:10.1145/73833.73871
[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 · Zbl 0447.68110 · doi:10.1007/978-1-4613-9323-8_18
[25] Marchand-Maillet, S.; Sharaiha, Y. M., Binary Digital Image Processing: A Discrete Approach., Academic Press, 1999 · doi:10.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., 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] Neal, F. B.; Russ, J. C., Measuring Shape., CRC Pres, 2012 · Zbl 1246.68006 · doi:10.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., Efficient and accurate computation of geometric moments on gray-scale images., Pattern Recognition 41 (2008), 6, 1895-1904 · Zbl 1132.68655 · doi:10.1016/j.patcog.2007.11.015
[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:10.1109/tpami.2013.67
[32] Shilane, P.; Min, P.; Kazhdan, M.; Funkhouser, T., The Princeton Shape Benchmark., In: Proc. Shape Modelling Applications, 2004 · doi:10.1109/smi.2004.1314504
[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 · Zbl 1331.68260 · doi:10.1007/s00138-007-0097-8
[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 · Zbl 1168.68049 · doi:10.1016/j.dam.2008.05.028
[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 · Zbl 0991.68126 · doi:10.1016/s0031-3203(99)00213-7
[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:10.1007/s11554-009-0142-0
[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:10.1109/83.725368
[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:10.1109/icpr.2010.242
[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:10.1016/j.patcog.2012.05.012
[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 · Zbl 0977.68094 · doi:10.1016/s0031-3203(00)00100-x
[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:10.1016/0031-3203(87)90033-1
[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:10.1145/2816795.2818074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.