Article
Full entry |
PDF
(5.2 MB)
Feedback
PDF
(5.2 MB)
Feedback
Keywords:
3D binary object; voxels; decomposition; rectangular blocks; sub-optimal algorithm; tripartite graph; maximum independent set
3D binary object; voxels; decomposition; rectangular blocks; sub-optimal algorithm; tripartite graph; maximum independent set
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.
References:
[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 10.1007/978-3-540-77974-2 | MR 2723879
[2] Bron, C., Kerbosch, J.: Algorithm 457: Finding all cliques of an undirected graph. Commun. ACM 16 (1973), 9, 575-577. DOI 10.1145/362342.362367
[3] Campisi, P., Egiazarian, K.: Blind Image Deconvolution: Theory and Applications. CRC, 2007. DOI 10.1201/9781420007299 | MR 2404093
[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 | MR 1490579
[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. DOI 10.1016/0020-0190(91)90207-x | MR 1103693
[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 0287976
[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 10.1145/321694.321699 | MR 0266680
[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 10.1007/978-3-642-11409-0_1 | MR 2587695
[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 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. DOI 10.1109/83.877219 | MR 1818456
[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. DOI 10.1145/290179.290181 | MR 1668151
[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 10.1145/48014.61051 | MR 1072405
[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. DOI 10.1137/0215033 | MR 0837597
[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. DOI 10.1109/tpami.1980.4766967
[20] Keil, J. M.: Polygon decomposition. In: Handbook of Computational Geometry, Elsevier, 2000, pp. 491-518. DOI 10.1016/b978-044482537-7/50012-7 | MR 1746683
[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 | MR 1354114
[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. DOI 10.1007/978-1-4613-9323-8_18 | MR 0573990
[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 | MR 1734820
[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 | MR 1683364
[28] Neal, F. B., Russ, J. C.: Measuring Shape. CRC Pres, 2012. 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. 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. 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. DOI 10.1016/j.dam.2008.05.028 | MR 2479146
[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 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. 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
Search
Partner of
