Phase Grouping Line Extraction Algorithm Using Overlapped Partition

doi:10.11947/j.AGCS.2015.20140234

Abstract

Abstract:

Aiming at solving the problem of fracture at the discontinuities area and the challenges of line fitting in each partition, an innovative line extraction algorithm is proposed based on phase grouping using overlapped partition. The proposed algorithm adopted dual partition steps, which will generate overlapped eight partitions. Between the two steps, the middle axis in the first step coincides with the border lines in the other step. Firstly, the connected edge points that share the same phase gradients are merged into the line candidates, and fitted into line segments. Then to remedy the break lines at the border areas, the break segments in the second partition steps are refitted. The proposed algorithm is robust and does not need any parameter tuning. Experiments with various datasets have confirmed that the method is not only capable of handling the linear features, but also powerful enough in handling the curve features.

Key words: overlapped-partition, phase grouping, Hough transform, line extraction, line fitting

CLC Number:

P237

WANG Jingxue, ZHU Qing, ZHANG Yunsheng, HU Han. Phase Grouping Line Extraction Algorithm Using Overlapped Partition[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(7): 768-774.

References

[1] HOUGH P V C. Methods and Means for Recognizing Complex Patterns: USA, 3069654 [P]. 1962-03-25.
[2] TANG Liang, XIE Weixin, HUANG Jianjun, et al. Adaptive Fuzzy Hough Transform[J]. Acta Electronica Sinica, 2004, 32(6): 946-949. (唐亮, 谢维信, 黄建军, 等. 自适应模糊Hough变换[J]. 电子学报, 2004, 32(6): 946-949.)
[3] BONCI A, LEO T, LONGHI S. A Bayesian Approach to the Hough Transform for Line Detection[J]. IEEE Transactions on System, Man and Cybernetics: Part A, 2005, 35(6): 945-955.
[4] 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. (徐胜华, 朱庆, 刘纪平, 等. 基于预存储权值矩阵的多尺度Hough变换直线提取算法[J]. 测绘学报, 2008, 37(1): 83-88.)
[5] SHANG Zhenhong, LIU Mingye. Line Detection Algorithm Using Freeman Criteria[J]. Journal of Computer-aided Design & Computer Graphics, 2005, 17(1): 49-53. (尚振宏, 刘明业. 运用Freeman准则的直线检测算法[J]. 计算机辅助设计与图形学学报, 2005, 17(1): 49-53.)
[6] SUN Han, REN Mingwu, YANG Jingyu. A Fast and Practical Algorithm for Line Detection[J]. Application Research of Computers, 2006, 23(2): 256-260. (孙涵, 任明武, 杨静宇. 一种快速实用的直线检测算法[J]. 计算机应用研究, 2006, 23(2): 256-260.)
[7] SHI Ce, XU Shengrong, JING Renjie, et al. The Replace Algorithm of Hough Transform in Real-time Image Processing[J]. Journal of Zhejiang University: Engineering Science, 1999, 33(5): 482-486. (史册, 徐胜荣, 荆仁杰, 等. 实时图像处理中一种快速的直线检测算法[J]. 浙江大学学报: 工学版, 1999, 33(5): 482-486.)
[8] 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.
[9] ZHOU Shaoguang, XU Yong. To Extract Roads with No Clear and Continuous Boundaries in RS Images[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(3): 301-307. (周绍光, 徐勇. 在高分辨率遥感影像中提取无清晰连续边缘线的道路[J]. 测绘学报, 2008, 37(3): 301-307.)
[10] ZHAO Jianquan. Research on the Algorithm of Road Edge Detection in High Resolution Remote Sensing Images Using Dynamic Programming[D]. Nanjing: Hohai University, 2007. (赵建泉. 基于动态规划理论的高分辨率遥感影像道路边缘检测算法研究[D]. 南京: 河海大学, 2007.)
[11] DOU Jianfang, CHEN Ying. Automatic Road Extraction from SAR Images Based on Mathematical Morphology and Phase Group[J]. Science of Surveying and Mapping, 2009, 34(2): 53-54. (窦建方, 陈鹰. 基于数学形态学和相位编组SAR影像道路自动提取[J]. 测绘科学, 2009, 34(2): 53-54.)
[12] DONG Yuefang. Research on Extracting Sea-sky-line and Target Tracking Algorithm of Sea-sky Background[D]. Beijing: University of Chinese Academy of Science, 2010. (董月芳. 海天背景下海天线定位及目标跟踪算法研究[D]. 北京: 中国科学院研究生院, 2010.)
[13] GUI Yang, YANG Xia, ZHU Xianwei, et al. Sea-sky-line Detection Based on Phase Grouping and Gray Statistics[J]. Journal of National University of Defense Technology, 2011, 33(6): 111-115. (桂阳, 杨夏, 朱宪伟, 等. 基于相位编组和灰度统计的海天线检测[J]. 国防科技大学学报, 2011, 33(6): 111-115.)
[14] PROKAJ J, DA VITORIA LOBO N. Scale Space Based Grammar for Hand Detection[C]// ZHENG N N, JIANG X Y, LAN X G. Advances in Machine Vision, Image Processing and Pattern Analysis. Lecture Notes in Computer Science Volume 4153. Berlin: Springer, 2006: 17-26.
[15] QIU Wu, YUCHI Ming, ZHANG Xuming, et al. Needle Detection Based on Phase Grouping in 3D Transrectal Ultrasound Images[J]. Acta Electronica Sinica, 2011, 39(10): 2295-2299. (邱武, 尉迟明, 张旭明, 等. 基于相位编组的三维直肠超声导引图像中针检测算法研究[J]. 电子学报, 2011, 39(10): 2295-2299.)
[16] ZHAO Siying. Needle Detection in 3D Ultrasound Images Based on Phase-grouping[D]. Wuhan: Huazhong University of Science & Technology, 2009. (赵四英. 基于相位编组的三维超声针状物体检测[D]. 武汉: 华中科技大学, 2009.)
[17] NIU Zhaodong, LIU Yang, CHEN Zengping. Line Extraction Using Adaptive Phase Partitioning and Edge Location Constraint[J]. Journal of Image and Graphics, 2010, 15(12): 1755-1761. (牛照东, 刘洋, 陈曾平. 利用自适应相位分区和边缘位置约束的直线提取新方法[J]. 中国图象图形学报, 2010, 15(12): 1755-1761.)
[18] HAN Dan, SONG Weidong, WANG Jingxue. Straight Line Extraction via Phase-grouping Method Based on Adaptive Partitioning[J]. Journal of Computer Applications, 2013, 33(6): 1691-1694. (韩丹, 宋伟东, 王竞雪. 自适应分区的相位编组直线提取算法[J]. 计算机应用, 2013, 33(6): 1691-1694.)
[19] 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.
[20] VON GIOI R G, JAKUBOWICZ J, MOREL J M, et al. LSD: A Line Segment Detector[J/OL]. Image Processing on Line, 2013. http://www.ipol.im/pub/art/2012/gjmr-lsd/.
[21] ZHANG Yunsheng. A Multi-primitive and Multi-view Image Matching Method Based on Self-adaptive Triangle Constraint [D]. Wuhan: Wuhan University, 2011. (张云生. 自适应三角形约束的多基元多视影像匹配方法[D]. 武汉: 武汉大学, 2011.)
[22] WU Bo, ZHANG Yunsheng, ZHU Qing. Integrated Point and Edge Matching on Poor Textural Images Constrained by Self-adaptive Triangulations[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2012, 68: 40-55.