Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (8): 2301-2305.DOI: 10.11772/j.issn.1001-9081.2016.08.2301

Previous Articles     Next Articles

Edge extraction method based on graph theory

ZHANG Ningbo1, LIU Zhenzhong2, ZHANG Kun1, WANG Lulu1   

  1. 1. College of Engineering, Northeast Agricultural University, Harbin Heilongjiang 150030, China;
    2. College of Science, Northeast Agricultural University, Harbin Heilongjiang 150030, China
  • Received:2016-01-27 Revised:2016-03-12 Online:2016-08-10 Published:2016-08-10
  • Supported by:
    This work is partially supported by the Key Technologies R&D Programme of Science and Technology Ministry (2014BAD12B01, 2013BAD20B04), the Northeast Agricultural University Innovation Foundation for Postgraduate (yjscx14025), the Natural Science Fund Projects of Northeast Agricultural University (2011RCA01).

基于图论的边缘提取方法

张宁波1, 刘振忠2, 张昆1, 王路路1   

  1. 1. 东北农业大学 工程学院, 哈尔滨 150030;
    2. 东北农业大学 理学院, 哈尔滨 150030
  • 通讯作者: 刘振忠
  • 作者简介:张宁波(1989-),男,山东德州人,硕士研究生,主要研究方向:模式识别与优化算法;刘振忠(1956-),男,山东济南人,教授,硕士,主要研究方向:多元统计、生物数学;张昆(1991-),男,山东青岛人,硕士研究生,主要研究方向:模式识别、生态价值评估;王路路(1990-),男,山东临沂人,硕士研究生,主要研究方向:质量体系评价。
  • 基金资助:
    科技部科技攻关计划项目(2014BAD12B01,2013BAD20B04);东北农业大学研究生科技创新项目(yjscx14025);东北农业大学自然科学基金资助项目(2011RCA01)。

Abstract: Focusing on the issue that edges extracted by state-of-the-art exist some deficiencies including non-continuity, incompleteness, incline, jitter and notches etc., an edge extraction method based on graph theory was proposed, which considered the image as an undirected graph by regarding each pixel as a node and connecting two adjacent nodes in horizontal or vertical direction to constitute a side. The proposed method included three phases:in pixels similarity calculation phase, the weights were given to sides in undirected graph, which represented pixels similarity; in threshold determination phase, the mean of all the weights (the similarity of the whole image) was determined as a threshold; in edge determination phase, when weights on horizontal or vertical sides were smaller than the threshold, the left nodes of horizontal side and the upper nodes of vertical side were retained to constitute edges of the image. The experimental results show that the proposed edge extraction method based on graph theory is suitable for the images with obvious target and background, and can overcome deficiencies including non-continuity, incompleteness, incline, jitter and notches etc., and has anti-noise ability to Speckle noise and Gaussian noise.

Key words: edge extraction, graph theory, threshold, noise

摘要: 针对传统边缘方法提取的边缘具有不连续、不完整、倾斜、抖动和缺口等问题,提出基于图论的边缘提取方法。该方法视像素为节点,在水平或垂直方向上连接两个相邻的节点构成一个边,从而将图像看作无向图。它包括三个阶段:在像素相似性计算阶段,无向图的边上被赋予权值,权值代表了像素间的相似性;在阈值确定阶段,将所有权值的均值(整幅图像的相似度)确定为阈值;在边缘确定阶段,只保留权值小于阈值的水平边的左边节点与垂直边的上边节点,从而获得了图像的边缘。实验表明,该方法适用于具有明显目标与背景的图像的边缘提取,能够克服不连续、不完整、倾斜、抖动和缺口等缺陷,并且对Speckle噪声和高斯噪声具有抗噪性能。

关键词: 边缘提取, 图论, 阈值, 噪声

CLC Number: