i-manager Publications

Effects of Unequal Bit Costs on Chain Code

Mohamed Yacine Gheraibia*

Department of Computer Science, University of Teluq, Montreal, Canada.

Periodicity:April - June'2019
DOI : https://doi.org/10.26634/jip.6.2.15895

Abstract

Contour representation of binary object is widely used in pattern recognition. Chain codes are compression methods, where the original data are reconstructed from the compressed data for representing binary objects including contours. Though a notably huge image size reduction is obtained by fixed-length chain code, so far, more efficient and reliable methods for data encoding is possible by using technique that treats the binary bits differently considering its requirement of storage space, energy consumption, speed of execution, and so on. This paper proposes a new variant of Huffman Coding (HC) by taking into consideration the fact that the costs of bits are different, the new representation of the Freeman Chain Code (FCC) is based on an eight-direction scheme. An experimentation of the cost efficiency of the new representation over the classical FCC is described and compared to other techniques. The experiments yield that the proposed FCC representation reduces overall both the storage and the transmission cost of encoded data considerably compared to the classical FCC.

Keywords

Chain Codes, Freeman Chain Code, Image Processing, Huffman Code, Data Compression, Coding Theory.

How to Cite this Article?

Gheraibia, M. Y. (2019). Effects of Unequal Bit Costs on Chain Code. i-manager's Journal on Image Processing, 6(2), 1-13. https://doi.org/10.26634/jip.6.2.15895

References

[1]. Altenkamp, D., & Mehlhorn, K. (1980). Codes: Unequal Probabilities, Unequal Letter Costs. Journal of the Association for Computing Machinery, 27(3), 412-427.

[2]. Arrebola, F., & Sandoval, F. (2005). Corner detection and curve segmentation by multiresolution chain-code linking. Pattern Recognition, 38(10), 1596-1614.

[3]. Bradford, P., Golin, M. J., Larmore, L. L., & Rytter, W. (2002). Optimal prefix-free codes for unequal letter costs: Dynamic programming with the Monge property. Journal of Algorithms, 42(2), 277-303.

[4]. Bribiesca, E. (1992). A geometric structure for twodimensional shapes and three-dimensional surfaces. Pattern Recognition, 25(5), 483-496.

[5]. Bribiesca, E. (1999). A new chain code. Pattern Recognition, 32(2), 235-251.

[6]. Cormen, T. H., Stein, C., Rivest, R. L., & Leiserson, C. E. (2001). Introduction to Algorithms, 2^nd Ed. McGraw-Hill Higher Education.

[7]. Cot, N. (1978). Characterization and Design of Optimal Prefix Codes, (Doctoral Dissertation), Stanford University.

[8]. Freeman, H. (1961). On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers,10(2), 260-268.

[9]. Gilbert, E. N. (1995). Coding with digits of unequal cost. IEEE Transactions on Information Theory, 41(2), 596- 600.

[10]. Globačnik, T., & Žalik, B. (2010). An efficient raster font compression for embedded systems. Pattern Recognition, 43(12), 4137-4147.

[11]. Golin, M. J., & Young, N. (1996). Prefix codes: Equiprobable words, unequal letter costs. SIAM Journal on Computing, 25(6), 1281-1292.

[12]. Golin, M. J., Kenyon, C., & Young, N. E. (2002, May). Huffman coding with unequal letter costs. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (pp. 785-791). ACM.

[13]. Golin, M. J., Mathieu, C., & Young, N. E. (2012). Huffman coding with letter costs: A linear-time approximation scheme. SIAM Journal on Computing, 41 (3), 684-713.

[14]. Ho, K. I., Chen, T. S., & Cheug, C. Y. (2002). An efficient face detection method using skin-color discovering and chain code. Machine Graphics & Vision International Journal, 11(2/3), 241- 256.

[15]. Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE, (Vol.40, No.9, pp.1098-1101).

[16]. Kabir, S., Azad, T., & Alam, A. A. (2014, December). Freeman chain code with digits of unequal cost. In The 8^thInternational Conference on Software, Knowledge, Information Management and Applications (SKIMA 2014) (pp. 1-6). IEEE.

[17]. Kabir, S., Azad, T., Alam, A. A., & Kaykobad, M. (2014, December). Effects of unequal bit costs on classical huffman codes. In 2014 17^thInternational Conference on Computer and Information Technology (ICCIT) (pp. 96-101). IEEE

[18]. Karp, R. (1961). Minimum-redundancy coding for the discrete noiseless channel. IRE Transactions on Information Theory, 7(1), 27-38.

[19]. Kaygın, S., & Bulut, M. M. (2001). A new one-pass algorithm to detect region boundaries. Pattern Recognition Letters, 22(10), 1169-1178.

[20]. Krause, R. M. (1962). Channels which transmit letters of unequal duration. Information and Control, 5(1), 13- 24.

[21]. Liu, Y. K., & Žalik, B. (2005). An efficient chain code with Huffman coding. Pattern Recognition, 38(4), 553- 557.

[22]. Liu, Y. K., Wei, W., Wang, P. J., & Žalik, B. (2007). Compressed vertex chain codes. Pattern Recognition, 40(11), 2908-2913.

[23]. Liu, Y. K., Žalik, B., Wang, P. J., & Podgorelec, D. (2012). Directional difference chain codes with quasilossless compression and run-length encoding. Signal Processing: Image Communication, 27(9), 973-984.

[24]. Mannanand, M. A., & Kaykobad, M. (2003). Block Huffman Coding. Computers and Mathematics with Applications, 46(10-11), 1581-1587.

[25]. Nunes, P., Marqués, F., Pereira, F., & Gasull, A. (2000). A contour-based approach to binary shape coding using a multiple grid chain code. Signal Processing: Image Communication, 15(7-8), 585-599.

[26]. Perl, Y., Garey, M. R., & Even, S. (1975). Efficient generation of optimal prefix code: Equiprobable words using unequal cost letters. Journal of the ACM (JACM), 22(2), 202-214.

[27]. Priyadarshini, S., & Sahoo, G. (2011). A new lossless chain code compression scheme based on substitution. International Journal of Signal and Imaging Systems Engineering, 4(1), 50-56.

[28]. Putra, I. K. G. D., & Sentosa, M. A. (2012). Hand geometry verification based on chain code and dynamic time warping. International Journal of Computer Applications, 38(12), 17-22.

[29]. Redmond, W. A. (1964). International Morse code. Microsoft En-carta 2009 [DVD], 275-278.

[30]. Ren, M., Yang, J., & Sun, H. (2002). Tracing boundary contours in a binary image. Image and Vision Computing, 20(2), 125-131.

[31]. Shih, F. Y., & Wong, W. T. (1999). A one-pass algorithm for local symmetry of contours from chain codes. Pattern Recognition, 32(7), 1203-1210.

[32]. Shih, F. Y., & Wong, W. T. (2001). An adaptive algorithm for conversion from quadtree to chain codes. Pattern Recognition, 34(3), 631-639.

[33]. Sun, H., Yang, J., & Ren, M. (2005). A fast watershed algorithm based on chain code and its application in image segmentation. Pattern Recognition Letters, 26(9), 1266-1274.

[34]. Varn, B. (1971). Optimal variable length codes (arbitrary symbol cost and equal code word probability). Information and Control, 19(4), 289-301.

[35]. Weng, T. L., Lin, S. J., Chang, W. Y., & Sun, Y. N. (2002). Voxel-based texture mapping for medical data. Computerized Medical Imaging and Graphics, 26(6), 445- 452.

[36]. Žalik, B., & Lukač, N. (2014). Chain code lossless compression using move-to-front transform and adaptive run-length encoding. Signal Processing: Image Communication, 29(1), 96-106.

If you have access to this article please login to view the article or kindly login to purchase the article

Single Article

	North Americas,UK, Middle East,Europe		India	Rest of world
	USD	EUR	INR	USD-ROW
Online	15	15

ADD TO CART

Options for accessing this content:

If you would like institutional access to this content, please recommend the title to your librarian.
If you already have i-manager's user account: Login above and proceed to purchase the article.
New Users: Please register, then proceed to purchase the article.