×

A new relative chain code in 3D. (English) Zbl 1326.68313

Summary: A new chain code to represent 3D discrete curves is proposed. The method is based on a search for relative changes in the 3D Euclidean space, composed of three main vectors: a reference vector, a support vector, and a change direction vector, utilized to obtain a directed simple path in a grid of 26 connected components. A set of rotation transformations is defined in the 3D Euclidean space, and an alphabet of only 25 symbols is required to represent any face, edge or vertex-connected discrete curve. Important properties of this code are found: independence under translation, rotation and mirror transformations, as well as high compression levels. A set of 3D curve-skeletons and digital elevation model data to study the terrain were utilized to prove the proposed code. Compared with the state-of-the-art, our method has more advantages: at first, it represents voxelized paths independently of vicinity, also it gives better representation for the tested objects and detects better the redundant parts. This fact is shown in the entropy calculated for 3D curve-skeletons: our method gives 3.03bits/symbol, whereas the state-of-the-art method gives 4.35bits/symbol. On the other hand, our proposed chain code uses 23% less memory than the well known Freeman code of 26 directions. In case of digital elevation models, our method improves memory for 36.1% regarding Freeman code and 10.7% regarding the well known relative code called orthogonal direction change chain code. Finally, average length of the chain code proposed is 14% shorter than the relative code of the state-of-the-art.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Full Text: DOI

References:

[1] Freeman, H., On the encoding of arbitrary geometric configurations, IRE Transactions on Electronic Computers, EC-10, 260-268 (1961)
[2] Kim, C. E., Three-dimensional digital segments, IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5, 231-234 (1983) · Zbl 0513.68075
[4] Bribiesca, E., A new chain code, Pattern Recognition, 32, 235-251 (1999)
[6] Echavarri-Aguinaga, L.; Neri-Calderon, R. A.; Rodriguez-Dagnino, R. M., Compression rates comparison of entropy coding for three-bit chain codes of bilevel images, Optical Engineering, 46, 8, 087007 (2007)
[7] Liu, Y. K.; Zalik, B., An efficient chain code with Huffman coding, Pattern Recognition, 38, 4, 553-557 (2005)
[8] Liu, Y. K.; Wei, W.; Wanga, P. J.; Zalik, B., Compressed vertex chain codes, Pattern Recognition, 40, 2908-2913 (2007) · Zbl 1118.68734
[9] Aghito, S. M.; Forchhammer, S., Context-based coding of bilevel images enhanced by digital straight line analysis, IEEE Transactions on Image Processing, 15, 8, 2120-2130 (2006)
[11] Sanchez-Cruz, H.; Bribiesca, E.; Rodriguez-Dagnino, R. M., Efficiency of chain codes to represent binary objects, Pattern Recognition, 40, 1660-1674 (2007) · Zbl 1111.68142
[13] Bribiesca, E., A chain code for representing 3d curves, Pattern Recognition, 33, 755-765 (2000)
[14] Bribiesca, E., A method for representing 3D tree objects using chain coding, Journal of Visual Communication and Image Representation, 19, 3, 184-198 (2008)
[15] Sanchez-Cruz, H., Proposing a new code by considering pieces of discrete straight lines in contour shapes, Journal of Visual Communication and Image Representation, 21, 311-324 (2010)
[16] Akimov, A.; Kolesnikov, A.; Franti, P., Lossless compression of map contours by context tree modelling of chain codes, Pattern Recognition, 40, 944-952 (2007) · Zbl 1119.68167
[17] Junding, S.; Heli, X., Contour-shape recognition and retrieval based on chain code, International Conference on Computational Intelligence and Security (2009)
[18] Kaneko, T.; Okudaira, M., Encoding of arbitrary curves based on chain code representation, IEEE Transactions on Communications, 33, 697-707 (1985)
[19] Kato, Y.; Hirano, T.; Nakamura, O., Fast template matching algorithm for contour images based on its chain coded description applied for human face identification, Pattern Recognition, 40, 1646-1659 (2007) · Zbl 1111.68110
[20] Shi, Z.; Govindaraju, V., A chain code based scheme for fingerprint feature extraction, Pattern Recognition Letters, 27, 462-468 (2006)
[21] Sanchez-Cruz, H.; Bribiesca, E., Polygonal approximation of contour shapes using corner detectors, Journal of Applied Research and Technology, 7, 3, 275-291 (2009)
[22] Freeman, H., Computer processing of line drawing images, ACM Computing Surveys, 6, 57-97 (1974) · Zbl 0287.68067
[23] Jonas, A.; Kiryati, N., Digital representation schemes for 3D curves, Pattern Recognition, 30, 1803-1816 (1997)
[24] Safonova, A.; Rossignac, J., Compressed piecewise-circular approximations of 3D curves, Computer-Aided Design, 35, 6, 533-547 (2003) · Zbl 1206.65108
[25] Zhao, C. S., Epipolar parameterization for reconstructing 3D rigid curve, Pattern Recognition, 30, 1817-1827 (1997)
[27] Sanchez-Cruz, H.; Bribiesca, E., Study of compression efficiency for three-dimensional discrete curves, Optical Engineering, 47, July (7), 077206 (2008)
[28] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1982), Elsevier Science Publishing Co., Inc. · Zbl 1226.05083
[31] Wang, Y.-S.; Lee, T.-Y., Curve-Skeleton extraction using iterative least squares optimization, IEEE Transactions on Visualization and Computer Graphics, 14, 4, 926-936 (2008)
[32] He, T.; Hong, L.; Chen, D.; Liang, Z., Reliable path for virtual endoscopyensuring complete examination of human organs, IEEE Transactions on Visualization and Computer Graphics, 7, Oct.-Dec. (4), 333-342 (2001)
[33] Hong, L.; Muraki, S.; Kaufman, A.; Bartz, D.; He, T., Virtual voyageinteractive navigation in the human colon, Proceedings of the SIGGRAPH, 97, 27-34 (1997)
[34] Gagvani, N.; Silver, D., Animating volumetric models, Graphical Models, 63, 6, 443-458 (2001) · Zbl 1011.68579
[35] Lin, C.-H.; Lee, T.-Y., Metamorphosis of 3D polyhedral models using progressive connectivity transformations, IEEE Transactions on Visualization and Computer Graphics, 11, 1, 2-12 (2005)
[36] Wade, L.; Parent, R. E., Automated generation of control skeletons for use in animation, The Visual Computer, 18, 2, 97-110 (2002) · Zbl 1002.68749
[37] Wu, F.-C.; Ma, W.-C.; Liang, R.-H.; Chen, B.-Y.; Ouhyoung, M., Domain connected graphthe skeleton of a closed 3D shape for animation, The Visual Computer, 22, 2, 117-135 (2006)
[42] Nooruddin, F. S.; Turk, G., Simplification and repair of polygonal models using volumetric techniques, IEEE Transactions on Visualization and Computer Graphics, 9, 2, 191-205 (2003)
[43] Palágyi, K.; Kuba, A., Directional 3D thinning using 8 subiterations, Lecture Notes in Computer Science, 1568, 325-336 (1999), Springer-Verlag
[44] Cornea, N. D.; Silver, D.; Min, P., Curve-skeleton properties, applications, and algorithms, IEEE Transactions on Visualization and Computer Graphics, 13, 3, 530-548 (2007)
[45] Ju, T.; Baker, M. L.; Chiu, W., Computing a family of skeletons of volumetric models for shape description, Computer-Aided Design, 39, 352-360 (2007)
[46] Lohou, C.; Bertrand, G., A 3D 6-subiteration curve thinning algorithm based on P-simple points, Discrete Applied Mathematics, 151, 198-228 (2005) · Zbl 1105.68108
[47] Natali, M.; Biasotti, S.; Patané, G.; Falcidieno, B., Graph-based representations of point clouds, Graphical Models, 73, 151-164 (2011)
[48] Wang, S.; Wu, J.; Wei, M.; Ma, X., Robust curve skeleton extraction for vascular structures, Graphical Models, 74, 109-120 (2012)
[49] Biasotti, S.; Giorgi, D.; Spagnuolo, M.; Falcidieno, B., Size functions for comparing 3D models, Pattern Recognition, 41, 2855-2873 (2008) · Zbl 1154.68479
[50] Serino, L.; Arcelli, C.; Sanniti di Baja, G., On the computation of the \(\langle 3, 4, 5 \rangle\) curve skeleton of 3D objects, Pattern Recognition Letters, 32, 1406-1414 (2011)
[52] de Berg, M.; Cheong, O.; Haverkort, H.; Lim, J.-G.; Toma, L., The complexity of flow on fat terrains and its i/o-efficient computation, Computational Geometry, 43, 331-356 (2010) · Zbl 1200.68265
[53] de Kok, T.; van Kreveld, M.; Löffler, M., Generating realistic terrains with higher-order Delaunay triangulations, Computational Geometry, 36, 52-65 (2007) · Zbl 1110.65022
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.