Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)  2018, Vol. 52 Issue (9): 1686-1693    DOI: 10.3785/j.issn.1008-973X.2018.09.008
Computer Technology     
Chain code based on independent edge number
WEI Xiao-feng1,2, CHENG Cheng-qi1, CHEN Bo1, WANG Hai-yan3
1. College of Engineering, Peking University, Beijing 100871, China;
2. Troop 96633, Beijing 100096, China;
3. Troop 61618, Beijing 100094, China
Download:   PDF(767KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A new chain code applied to various types of boundary grids was proposed. This chain code relied on counting the independent edge number of each boundary grid, called Edge Chain Code (ECC). ECC for hexagonal grids was exactly the independent edge number sequence. ECC for rectangular grids could be obtained by recording the independent edge numbers of each boundary grid and distinguishing two different contour moving directions with "0". ECC for triangular grids used "0"~"3" and "4"~"7" to express four conditions with edge number of 1 or 2 separately. Moreover, among all these chain codes, meaningless combinations were used to express the special cases and reduce the coding redundancy. ECC was invariant to start point, rotation and mirroring, which could also detect straight line segments and count boundary perimeter. Finally, ECC was compared with four classical chain codes on encoding efficiencies and storage memories. Results show that ECC can be applied to express all kinds of grid boundaries, the total coding numbers of ECC for hexagonal grids and triangular grids are separately 50% and 78% of VCC, and the compression ratio of ECC for rectangular grids can reach 0.827 5.

Received: 01 December 2017      Published: 20 September 2018
CLC:  TP391  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

WEI Xiao-feng, CHENG Cheng-qi, CHEN Bo, WANG Hai-yan. Chain code based on independent edge number. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1686-1693.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2018.09.008     OR     http://www.zjujournals.com/eng/Y2018/V52/I9/1686


基于独立边数的链码方法

提出一种适用于表达不同类型边界网格的链码方法.该链码可通过记录各边界网格的独立边数得到，称之为边链码.其中，六边形网格边链码即各边界网格的独立边数集合；四边形网格的边链码在记录独立边数的同时，可区分2种不同轮廓行进方向；三角形网格的边链码则由“0”~“3”和“4”~“7”分别表示独立边数为1或2时的4种情况；对于边界上的特殊情况，边链码分别利用无意义的编码组合对原码值进行替换，有效减少编码冗余.边链码与起始位置无关，具有旋转与翻转不变性，并能够检测直线段以及计算边界周长.将边链码与4种经典的链码方法进行编码效率对比实验，结果表明，边链码能够应用于各类网格边界表达，六边形与三角形的边链码总码数分别为VCC的50%和78%左右，四边形边链码的压缩率可达0.827 5.

[1] JAIN J, SAHOO S K, PRASANNA S M, et al. Modified chain code histogram feature for handwritten character recognition[C]//Advances in Computer Science and Information Technology, Networks and Communications. Berlin Heidelberg:Springer, 2012:611-619.
[2] RACHMAWATI E, IPING S, MASAYU L K. Bag-of-shapes descriptor using shape association based on freeman chain code[J]. Journal of Theoretical and Applied Information Technology, 2017, 95(5):1142-1153.
[3] LEE D, KIM S J. Modified chain-code-based object recognition[J]. Electronics Letters, 2015, 51(24):1996-1997.
[4] KARCZMAREK P, KIERSZTYN A, PEDRYCZ W, et al. An application of chain code-based local descriptor and its extension to face recognition[J]. Pattern Recognition, 2017, 65:26-34.
[5] YUHANDRI, MADENDA S, PRASETYO E. Object feature extraction of songket image using chain code algorithm[J]. International Journal on Advanced Science, Engineering and Information Technology, 2017, 7(1):235-241.
[6] TAWFIQ A, ASADI A, JODA F A. Removing spatial redundancy from image by using variable vertex chain code[J]. European Academic Research, 2014, 2(1):179-192.
[7] REN M, KARIMI H A. A chain-code-based map matching algorithm for wheelchair navigation, Trans[J]. Transactions in GIS, 2009, 13(2):197-214.
[8] FREEMAN H. On the encoding of arbitrary geometric configurations[J]. IRE Transactions on Electronic Computers, 1961, 10(2):260-268.
[9] BRIBIESCA E. A new chain code[J]. Pattern Recognition, 1999, 32:235-251.
[10] SANCHEZ H C, DAGNINO R M. Compressing bi-level images by means of a 3-bit chain code[J]. SPIE Optical Eng, 2005, 44(9):1-8.
[11] SANCHEZ H C, BRIBIESCA E, DAGNINO R M. Efficiency of chain codes to represent binary objects[J]. Pattern Recognition, 2007, 40(6):1660-1674.
[12] BORUT Z, MONGUS D, LIU Y K, et al. Unsigned Manhattan chain code[J]. Journal of Visual Communication and Image Representation, 2016, 38:186-194.
[13] LIU Y K, ZALIK B. An efficient chain code with Huffman coding[J]. Pattern Recognition, 2005, 38(4):553-557.
[14] CRUZ H S. Proposing a new code by considering pieces of discrete straight lines in contour shapes[J]. Journal of Visual Communication and Image Representation, 2010, 21(4):311-324.
[15] ZALIK B, MONGUS D, ZALIK K R et al. Chain code compression using string transformation techniques[J]. Digital Signal Processing, 2016, 53(6):1-10.
[1] HAN Yong, NING Lian-ju, ZHENG Xiao-lin, LIN Wei-hua, SUN Zhong-yuan. Matrix factorization recommendation based on social information and item exposure[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(1): 89-98.
[2] ZHENG Zhou, ZHANG Xue-chang, ZHENG Si-ming, SHI Yue-ding. Liver segmentation in CT images based on region-growing and unified level set method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(12): 2382-2396.
[3] ZHAO Li-ke, ZHENG Shun-yi, WANG Xiao-nan, HUANG Xia. Rigid object position and orientation measurement based on monocular sequence[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(12): 2372-2381.
[4] HE Jie-guang, PENG Zhi-ping, CUI De-long, LI Qi-rui. Teaching-learning-based optimization algorithm with local dimension improvement[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(11): 2159-2170.
[5] LI Zhi, SHAN Hong, MA Tao, HUANG Jun. Group discovery of mobile terminal users based on reverse-label propagation algorithm[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(11): 2171-2179.
[6] WANG Shuo-peng, YANG Peng, SUN Hao. Construction process optimization of fingerprint database for auditory localization[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(10): 1973-1979.
[7] CHEN Rong-hua, WANG Ying-han, BU Jia-jun, YU Zhi, GAO Fei. Website accessibility sampling evaluation based on KNN and local regression[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1702-1708.
[8] ZHANG Cheng-zhi, FENG Hua-jun, XU Zhi-hai, LI Qi, CHEN Yue-ting. Piecewise noise variance estimation of images based on wavelet transform[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1804-1810.
[9] LIU Zhou-zhou, LI Shi-ning, LI Bin, WANG Hao, ZHANG Qian-yun, ZHENG Ran. New elastic collision optimization algorithm and its application in sensor cloud resource scheduling[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1431-1443.
[10] WANG Yong-chao, ZHU Kai-lin, WU Qi-xuan, LU Dong-ming. Adaptive display technology of high precision model based on local rendering[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1461-1466.
[11] SUN Nian, LI Yu-qiang, LIU Ai-hua, LIU Chun, LI Wei-wei. Microblog sentiment analysis based on collaborative learning under loose conditions[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1452-1460.
[12] ZHENG Shou-guo, CUI Yan-min, WANG Qing, YANG Fei, CHENG Liang. Design of field data acquisition platform for aircraft assembly[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1526-1534.
[13] BI Xiao-jun, WANG Chao. Many-objective evolutionary algorithm based on hyperplane projection[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1284-1293.
[14] ZHANG Ting-rong, TENG Qi-zhi, LI Zheng-ji, QING Lin-bo, HE Xiao-hai. Super-resolution reconstruction for three-dimensional core CT image[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1294-1301.
[15] ZHAO Chuan-song, REN Hong-ge, SHI Tao, LI Fu-jin. Wheeled inverted pendulum reactive cognitive system with internal motivation[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(6): 1073-1080.