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噪声和高斯噪声具有抗噪性能。

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