A Line Extraction Method for Chain Code Tracking with Phase Verification

doi:10.11947/j.AGCS.2017.20160303

Abstract

Abstract: A line extraction method for chain code tracking with phase verification was proposed in this study. Firstly, a complete refinement algorithm targeting the Canny edge map was presented. Secondly, an improved chain code tracking method was proposed, and the key algorithm steps were described as follows:detecting the start points of chain code; setting up dynamic main directions to determine the tracking directions of chain code; tracking edge points inside the eight neighborhoods was preferred, and then edge points outside the eight neighborhoods if no edge points existed inside the eight neighborhoods, meanwhile linear analysis was employed to perform dynamic constraints on the chain code. Finally, linear fitting and phase marshalling validation were processed upon the chain code tracking, where straight lines were output when condition were satisfied, otherwise the start points of chain code should be reset to extract straight lines. The experimental results from a variety of different optical image data showed that the proposed algorithm could not only achieve precise fit straight edge information, but also solve the linear fracture problems induced by white noise and phase grouping.

Key words: line extraction, thinning method, chain code tracking, phase verification

CLC Number:

P237

DAI Jiguang, ZHANG Li, LI Jinwei, FANG Xinxin. A Line Extraction Method for Chain Code Tracking with Phase Verification[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 218-227.

References

[1] 董银文, 苑秉成, 王航宇, 等. 一种有效的航拍图像中直线提取算法[J]. 武汉大学学报(信息科学版), 2012, 37(2):160-164. DONG Yinwen, YUAN Bingcheng, WANG Hangyu, et al. An Effective Algorithm for Line Extraction in Aerial Image[J]. Geomatics and Information Science of Wuhan University, 2012, 37(2):160-164.
[2] BALTSAVIAS E P. Object Extraction and Revision by Image Analysis Using Existing Geodata and Knowledge:Current Status and Steps towards Operational Systems[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2004, 58(3-4):129-151.
[3] ZHENG Yefeng, LI Huiping, DOERMANN D. A Parallel-line Detection Algorithm Based on HMM Decoding[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 27(5):777-792.
[4] 周绍光, 陈超, 岳建平. 形状先验和图割的高分辨率遥感影像道路段提取[J]. 测绘学报, 2014, 43(1):60-65. DOI:10.13485/j.cnki.11-2089.2014.0009. ZHOU Shaoguang, CHEN Chao, YUE Jianping. Extracting Roads from High-resolution RS Images Based on Shape Priors and Graph Cuts[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(1):60-65. DOI:10.13485/j.cnki.11-2089.2014.0009.
[5] 曹金山, 龚健雅, 袁修孝. 直线特征约束的高分辨率卫星影像区域网平差方法[J]. 测绘学报, 2015, 44(10):1100-1107, 1116. DOI:10.11947/j.AGCS2.0152.0150023. CAO Jinshan, GONG Jianya, YUAN Xiuxiao. A Block Adjustment Method of High-resolution Satellite Imagery with Straight Line Constraints[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10):1100-1107, 1116. DOI:10.11947/j.AGCS2.0152.0150023.
[6] 王竞雪, 宋伟东, 王伟玺. 同名点及高程平面约束的航空影像直线匹配算法[J]. 测绘学报, 2016, 45(1):87-95. DOI:10.11947/j.AGCS.2016.20140527. WANG Jingxue, SONG Weidong, WANG Weixi. Line Matching Algorithm for Aerial Image Based on Corresponding Points and Z-plane Constraints[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(1):87-95. DOI:10.11947/j.AGCS.2016.20140527.
[7] 徐胜华, 朱庆, 刘纪平, 等. 基于预存储权值矩阵的多尺度Hough变换直线提取算法[J]. 测绘学报, 2008, 37(1):83-88. XU Shenghua, ZHU Qing, LIU Jiping, et al. Straight Line Extraction via Multi-scale Hough Transform Based on Pre-storage Weight Matrix[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(1):83-88.
[8] 文贡坚, 王润生. 一种稳健的直线提取算法[J]. 软件学报, 2001, 12(11):1660-1666. WEN Gongjian, WANG Runsheng. A Robust Approach to Extracting Straight Lines[J]. Journal of Software, 2001, 12(11):1660-1666.
[9] CHUNG K L, CHEN T C, YAN Wenming. New Memory and Computation-efficient Hough Transform for Detecting Lines[J]. Pattern Recognition, 2004, 37(5):953-963.
[10] 王竞雪, 朱庆, 王伟玺, 等. 结合边缘编组的Hough变换直线提取[J]. 遥感学报, 2014, 18(2):378-389. WANG Jingxue, ZHU Qing, WANG Weixi, et al. Straight Line Extraction Algorithm by Hough Transform Combining Edge Grouping[J]. Journal of Remote Sensing, 2014, 18(2):378-389.
[11] XU Zezhong, SHIN B S, KLETTE R. Accurate and Robust Line Segment Extraction Using Minimum Entropy with Hough Transform[J]. IEEE Transactions on Image Processing, 2015, 24(3):813-822.
[12] FREEMAN H. Boundary Encoding and Processing[C]//LIPKIN B S, ROSENFELD A. Proceedings of Picture Processing and Psychopictorics. New York:Academic Press, 1970:241-266.
[13] 尚振宏, 刘明业. 运用Freeman准则的直线检测算法[J]. 计算机辅助设计与图形学学报, 2005, 17(1):49-53. SHANG Zhenhong, LIU Mingye. Line Detection Algorithm Using Freeman Criteria[J]. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(1):49-53.
[14] 赵丽科, 宋伟东, 王竞雪. Freeman链码优先级直线提取算法研究[J]. 武汉大学学报(信息科学版), 2014, 39(1):42-46, 122. ZHAO Like, SONG Weidong, WANG Jingxue. Straight Line Extraction Algorithm of Freeman Chain Code Priority[J]. Geomatics and Information Science of Wuhan University, 2014, 39(1):42-46, 122.
[15] 王竞雪, 宋伟东, 赵丽科, 等. 改进的Freeman链码在边缘跟踪及直线提取中的应用研究[J]. 信号处理, 2014, 30(4):422-430. WANG Jingxue, SONG Weidong, ZHAO Like, et al. Application of Improved Freeman Chain Code in Edge Tracking and Straight Line Extraction[J]. Journal of Signal Processing, 2014, 30(4):422-430.
[16] BURNS J B, HANSON A R, RISEMAN E M. Extracting Straight Lines[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 8(4):425-455.
[17] VON GIOI R G, JAKUBOWICZ J, MOREL J M, et al. LSD:A Fast Line Segment Detector with a False Detection Control[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(4):722-732.
[18] AKINLAR C, TOPAL C. EDLines:A Real-time Line Segment Detector with a False Detection Control[J]. Pattern Recognition Letters, 2011, 32(13):1633-1642.
[19] 王竞雪, 朱庆, 张云生, 等. 叠置分区辅助的相位编组直线提取算法[J]. 测绘学报, 2015, 44(7):768-774, 790. DOI:10.11947/j.AGCS.2015.20140234. WANG Jingxue, ZHU Qing, ZHANG Yunsheng, et al. Phase Grouping Line Extraction Algorithm Using Over-lapped Partition[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(7):768-774, 790. DOI:10.11947/j.AGCS.2015.20140234.
[20] CANNY J. A Computational Approach to Edge Detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 8(6):679-698.
[21] ZHANG T Y, SUEN C Y. A Fast Parallel Algorithm for Thinning Digital Patterns[J]. Communications of the ACM, 1984, 27(3):236-239.
[22] 韩建峰, 宋丽丽. 改进的字符图像细化算法[J]. 计算机辅助设计与图形学学报, 2013, 25(1):62-66. HAN Jianfeng, SONG Lili. An Improved Thinning Algorithm for Character Image[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(1):62-66.
[23] HOLT C M, STEWART A, CLINT M, et al. An Improved Parallel Thinning Algorithm[J]. Communications of the ACM, 1987, 30(2):156-160.
[24] 许宏科, 秦严严, 潘勇. 一种改进的边缘细化方法[J]. 激光与红外, 2014, 44(3):319-324. XU Hongke, QIN Yanyan, PAN Yong. Improved Edge Thinning Method[J]. Laser & Infrared, 2014, 44(3):319-324.
[25] CHIN R T, WAN H K, STOVER D L, et al. A One-pass Thinning Algorithm and Its Parallel Implementation[J]. Computer Vision, Graphics, and Image Processing, 1987, 40(1):30-40.