外文文献资料(Canny 算子)

外文文献资料

Canny edge detector

1. Canny edge detector Introduction

The Canny edge detection operator was developed by John F. Canny in 1986 and uses a multi-stage algorithm to detect a wide range of edges in images. Most importantly, Canny also produced a computational theory of edge detection explaining why the technique works.

2. Development of the Canny algorithm

Canny's aim was to discover the optimal edge detection algorithm. In this situation, an \"optimal\" edge detector means:



good detection – the algorithm should mark as many real edges in the image as possible.



good localization – edges marked should be as close as possible to the edge in the real image.



minimal response – a given edge in the image should only be marked once, and where possible, image noise should not create false edges.

To satisfy these requirements Canny used the calculus of variations – a technique which finds the function which optimizes a given functional. The

1

苏州大学本科生毕业设计（论文）附件：外文文献资料与中文翻译稿

optimal function in Canny's detector is described by the sum of four exponential terms, but can be approximated by the first derivative of a Gaussian.

3. Stages of the Canny algorithm 3.1 Noise reduction

The Canny edge detector uses a filter based on the first derivative of a Gaussian, because it is susceptible to noise present on raw unprocessed image data, so to begin with, the raw image is convolved with a Gaussian filter. The result is a slightly blurred version of the original which is not affected by a single noisy pixel to any significant degree.

3.2 Finding the intensity gradient of the image

An edge in an image may point in a variety of directions, so the Canny algorithm uses four filters to detect horizontal, vertical and diagonal edges in the blurred image. The edge detection operator (Roberts, Prewitt, Sobel for example) returns a value for the first derivative in the horizontal direction (Gy) and the vertical direction (Gx). From this the edge gradient and direction can be determined.

3.3 Tracing edges through the image and hysteresis thresholding

Intensity gradients which are large are more likely to correspond to edges than if they are small. It is in most cases impossible to specify a threshold at which a

2

苏州大学本科生毕业设计（论文）附件：外文文献资料与中文翻译稿

given intensity gradient switches from corresponding to an edge into not doing so. Therefore Canny uses thresholding with hysteresis.

Thresholding with hysteresis requires two thresholds – high and low. Making the assumption that important edges should be along continuous curves in the image allows us to follow a faint section of a given line and to discard a few noisy pixels that do not constitute a line but have produced large gradients. Therefore we begin by applying a high threshold. This marks out the edges we can be fairly sure are genuine. Starting from these, using the directional information derived earlier, edges can be traced through the image. While tracing an edge, we apply the lower threshold, allowing us to trace faint sections of edges as long as we find a starting point.

Once this process is complete we have a binary image where each pixel is marked as either an edge pixel or a non-edge pixel. From complementary output from the edge tracing step, the binary edge map obtained in this way can also be treated as a set of edge curves, which after further processing can be represented as polygons in the image domain.

Differential geometric formulation of the Canny edge detector：

2L2xLxx2LxLyLxyLyLyy0 （3-1）

A more refined approach to obtain edges with sub-pixel accuracy is by using the approach of differential edge detection, where the requirement of non-maximum suppression is formulated in terms of second- and third-order

3

苏州大学本科生毕业设计（论文）附件：外文文献资料与中文翻译稿

derivatives computed from a scale-space representation (Lindeberg 1998) – see the article on edge detection for a detailed description.

Variational-geometric formulation of the Haralick-Canny edge detector：

223L3L3LLL3LLLLxxxxxyxxyxyxyyyLyyy0 （3-2）

A variational explanation for the main ingredient of the Canny edge detector, that is, finding the zero crossings of the 2nd derivative along the gradient direction, was shown to be the result of minimizing a Kronrod-Minkowski functional while maximizing the integral over the alignment of the edge with the gradient field (Kimmel and Bruckstein 2003) see article on regularized Laplacian zero crossings and other optimal edge integrators for a detailed description.

4 Parameters

The Canny algorithm contains a number of adjustable parameters, which can affect the computation time and effectiveness of the algorithm.



The size of the Gaussian filter: the smoothing filter used in the first stage directly affects the results of the Canny algorithm. Smaller filters cause less blurring, and allow detection of small, sharp lines. A larger filter causes more blurring, smearing out the value of a given pixel over a larger area of the image. Larger blurring radii are more useful for detecting larger, smoother edges – for instance, the edge of a rainbow.

4

苏州大学本科生毕业设计（论文）附件：外文文献资料与中文翻译稿



Thresholds: the use of two thresholds with hysteresis allows more flexibility than in a single-threshold approach, but general problems of thresholding approaches still apply. A threshold set too high can miss important information. On the other hand, a threshold set too low will falsely identify irrelevant information (such as noise) as important. It is difficult to give a generic threshold that works well on all images. No tried and tested approach to this problem yet exists.

5 Conclusion

The Canny algorithm is adaptable to various environments. Its parameters allow it to be tailored to recognition of edges of differing characteristics depending on the particular requirements of a given implementation. In Canny's original paper, the derivation of the optimal filter led to a Finite Impulse Response filter, which can be slow to compute in the spatial domain if the amount of smoothing required is important (the filter will have a large spatial support in that case). For this reason, it is often suggested to use Rachid Deriche's Infinite Impulse Response form of Canny's filter (the Canny-Deriche detector), which is recursive, and which can be computed in a short, fixed amount of time for any desired amount of smoothing. The second form is suitable for real time implementations in FPGAs or DSPs, or very fast embedded PCs. In this context, however, the regular recursive implementation of the Canny operator does not give a good approximation of rotational symmetry and therefore gives a bias towards horizontal and vertical edges.

5

苏州大学本科生毕业设计（论文）附件：外文文献资料与中文翻译稿

中文翻译稿 Canny算子

1 Canny算子简介

Canny 边缘检测算子是John F. Canny于 1986 年开发出来的一个多级边缘检测算法。更为重要的是 Canny 创立了边缘检测计算理论（Computational theory of edge detection）解释这项技术如何工作。

2 Canny 算法的发展

Canny 的目标是找到一个最优的边缘检测算法，最优边缘检测的含义是：  好的检测 - 算法能够尽可能多地标识出图像中的实际边缘。

 好的定位 - 标识出的边缘要尽可能与实际图像中的实际边缘尽可能接近。

 最小响应 - 图像中的边缘只能标识一次，并且可能存在的图像噪声不应标识为边缘。

为了满足这些要求 Canny 使用了变分法，这是一种寻找满足特定功能的函数的方法。最优检测使用四个指数函数项的和表示，但是它非常近似于高斯函数的一阶导数。

3 Canny 算法的步骤 3.1 去噪声

任何边缘检测算法都不可能在未经处理的原始数据上很好地处理，所以第一步是对原始数据与高斯 mask 作卷积，得到的图像与原始图像相比有些轻微的模糊（blurred）。这样，单独的一个像素噪声在经过高斯平滑的图像上变得几乎没有影响。

3.2 寻找图像中的亮度梯度

图像中的边缘可能会指向不同的方向，所以 Canny 算法使用 4 个 mask 检测水平、垂直以及对角线方向的边缘。原始图像与每个 mask 所作的卷积都存储起来。对于每个点

6

苏州大学本科生毕业设计（论文）附件：外文文献资料与中文翻译稿

我们都标识在这个点上的最大值以及生成的边缘的方向。这样我们就从原始图像生成了图像中每个点亮度梯度图以及亮度梯度的方向。

3.3 在图像中跟踪边缘

较高的亮度梯度比较有可能是边缘，但是没有一个确切的值来限定多大的亮度梯度是边缘多大又不是，所以 Canny 使用了滞后阈值。

滞后阈值需要两个阈值——高阈值与低阈值。假设图像中的重要边缘都是连续的曲线，这样我们就可以跟踪给定曲线中模糊的部分，并且避免将没有组成曲线的噪声像素当成边缘。所以我们从一个较大的阈值开始，这将标识出我们比较确信的真实边缘，使用前面导出的方向信息，我们从这些真正的边缘开始在图像中跟踪整个的边缘。在跟踪的时候，我们使用一个较小的阈值，这样就可以跟踪曲线的模糊部分直到我们回到起点。

一旦这个过程完成，我们就得到了一个二值图像，每点表示是否是一个边缘点。 一个获得亚像素精度边缘的改进实现是在梯度方向检测二阶方向导数的过零点：

2L2xLxx2LxLyLxyLyLyy0 （3-1）

它在梯度方向的三阶方向导数满足符号条件：

223L3xLxxx3LxLyLxxy3LxLyLxyyLyLyyy0 （3-2）

其中 Lx,Ly...Lyyy表示用高斯核平滑原始图像得到的尺度空间表示L计算得到的偏导数。用这种方法得到的边缘片断是连续曲线，这样就不需要另外的边缘跟踪改进。滞后阈值也可以用于亚像素边缘检测。

4 参数

Canny 算法包含许多可以调整的参数，它们将影响到算法的计算的时间与实效。  高斯滤波器的大小：第一步所有的平滑滤波器将会直接影响 Canny 算法的结果。较小

的滤波器产生的模糊效果也较少，这样就可以检测较小、变化明显的细线。较大的滤波器产生的模糊效果也较多，将较大的一块图像区域涂成一个特定点的颜色值。这样带来的结果就是对于检测较大、平滑的边缘更加有用，例如彩虹的边缘。

 阈值：使用两个阈值比使用一个阈值更加灵活，但是它还是有阈值存在的共性问题。

设置的阈值过高，可能会漏掉重要信息；阈值过低，将会把枝节信息看得很重要。很难给出一个适用于所有图像的通用阈值。目前还没有一个经过验证的实现方法。

7

苏州大学本科生毕业设计（论文）附件：外文文献资料与中文翻译稿

5 结论

Canny 算法适用于不同的场合。它的参数允许根据不同实现的特定要求进行调整以识别不同的边缘特性。对于PC上的实时图像处理来说可能慢得无法使用，尤其是在使用大的高斯滤波器的情况下。但是，我们讨论计算能力的时候，也要考虑到随着处理器速度不断提升，有望在未来几年使得这不再成为一个问题。

8