Canny algorithm edge detection

Canny edge detection algorithm is a multi-level edge detection algorithm developed by John F. Canny in 1986. Canny’s paper, published in August 2014, has been cited more than 19,000 times. Canny created the Computational Theory of Edge Detection to explain how the technique works. In general, the purpose of edge detection is to significantly reduce the image data size while preserving the original image attributes. There are many algorithms for edge detection. Although Canny algorithm has a long history, it can be said that it is a standard algorithm for edge detection, and it is still widely used in research.

The goal of Canny is to find an optimal edge detection algorithm. The meaning of optimal edge detection is:

  • Optimal detection: the algorithm can identify as many actual edges in the image as possible, and the probability of missing real edges and false detection of non-edges is as small as possible.
  • The optimal positioning criteria are as follows: the position of the detected edge point is closest to that of the actual edge point, or the detected edge has the least deviation from the real edge of the object due to the influence of noise;
  • One-to-one correspondence between detection points and edge points: The edge points detected by the operator should be one-to-one correspondence with the actual edge points.

To meet these requirements, Canny has used calculus of Variations, a method of finding functions that optimize specific functions. The optimal detection is represented by four exponential function terms, but it is very close to the first derivative of the Gaussian function.

[Quoted from Baidu Baike]

Algorithm steps

The edge detection based on Canny algorithm mainly consists of five steps, including Gaussian filtering, pixel gradient calculation, non-maximum pixel gradient suppression, lag threshold processing and isolated weak edge suppression.

1. Gaussian filtering

Gaussian filter is used to smooth the image and reduce the noise in the image. Generally, a 5×5 Gaussian filter is used.


1 159 [ 2 4 5 4 2 4 9 12 9 4 5 12 15 12 5 4 9 12 9 4 2 4 5 4 2 ] \frac{1}{159}\left[ \begin{array}{ccc} 2 & 4 & 5 & 4 & 2\\\\ 4 & 9 & 12 & 9 & 4\\\\ 5 & 12 & 15 & 12 & 5\\\\ 4 & 9 & 12 & 9 & 4\\\\ 2 & 4 & 5 & 4 & 2\\\\ \end{array} \right]

2. Pixel gradient calculation

Sobel operator is used to detect edges of smooth images in horizontal and vertical directions to obtain first derivatives in horizontal (Gx) and vertical (Gy) directions. From these two images, we can find the gradient amplitude and direction of each pixel, as shown below:


E d g e _ G r a d i e n t    ( G ) = G x 2 + G y 2 Edge\_Gradient \; (G) = \sqrt{G_x^2 + G_y^2}

A n g l e    ( Theta. ) = tan ⁡ – 1 ( G y G x ) Angle \; (\theta) = \tan^{-1} \bigg(\frac{G_y}{G_x}\bigg)

The gradient direction is always perpendicular to the edge. For simplicity, round it to one of the four angles representing vertical, horizontal, and two diagonal directions.

3. Non-maximum pixel gradient suppression

A non-maximum suppression algorithm is used to eliminate the stray response caused by edge detection. First, the gradient intensity of the current pixel is compared with the two pixels along the positive and negative gradient directions. If the gradient intensity of the current pixel is the largest compared with the gradient intensity of the other two pixels, the pixel will be retained as the edge point; otherwise, the pixel will be suppressed.

Point A is on the edge (vertical direction). The gradient is perpendicular to the edge. B and C are in the gradient direction. Therefore, point A is checked against points B and C to see if A local maximum is formed. If so, consider using it for the next phase, otherwise suppress it (set to zero).

4. Lag threshold processing

Double threshold method is used to classify strong edge and weak edge. The gradient value at the edge is compared with the two thresholds. If the gradient amplitude of a pixel is less than the smaller threshold, it will be removed. If the gradient amplitude of a pixel is greater than the small threshold but less than the large threshold, the pixel is marked as weak edge. If the gradient amplitude of a pixel is greater than the larger threshold, the pixel is marked as strong edge.

5. Isolated weak marginal inhibition

In general, weak edge pixels caused by real edges will be connected to strong edge pixels, while the noise response will not be connected. By viewing the weak edge pixel and its 8 neighboring pixels, we can judge according to its connection with the strong edge. Generally, it can be defined that as long as one of the neighborhood pixels is a strong edge pixel, the weak edge can be retained as a strong edge, that is, a real edge point.

As shown above, edge A is above maxVal and is therefore considered A “strong edge.” Although edge C is lower than maxVal, it is connected to edge A and therefore also considered A valid edge, and we get the complete curve. But edge B, although above minVal and in the same region as edge C, is not attached to any “strong edge” and is discarded. Therefore, it is important that we use the right minVal and maxVal to get the right results.

API

public static void Canny(Mat image, Mat edges, double threshold1, double threshold2, int apertureSize, boolean L2gradient)
Copy the code

  • C Parameter 1: image, the input image must be CV_8U single-channel or three-channel image.

  • Parameter 2: Edges: output image, single channel image with the same size as input image, and data type is CV_8U.

  • Parameter 3: Threshold1: indicates the first lag threshold.

  • Parameter 4: Threshold2, the second lag threshold.

  • Parameter 5: apertureSize, diameter of Sobel operator.

  • Parameter 6: L2gradient, the symbol of the method to calculate the image gradient amplitude. The default is false, using the first calculation below


    E d g e _ G r a d i e n t    ( G ) = ∣ G x ∣ + ∣ G y ∣ Edge\_Gradient \; (G) = |G_x| + |G_y|

    E d g e _ G r a d i e n t    ( G ) = G x 2 + G y 2 Edge\_Gradient \; (G) = \sqrt{G_x^2 + G_y^2}

The first parameter is the input image that needs to extract the edge. Currently, only the image with the data type of CV_8U is supported. The input image can be gray image or color image. The second parameter is the output image of edge detection results, which is a single-channel gray image with data type CV_8U. The third and fourth parameters of the function are the two thresholds used to distinguish strong edges and weak edges in Canny algorithm. The two parameters do not distinguish large and small thresholds, so the function will automatically compare and distinguish the size of the two thresholds. However, in general, the ratio of large threshold to small threshold is between 2:1 and 3:1. The last parameter of the function is the selection flag of the method used to calculate the gradient amplitude. If no special requirements are required, use the default value.

operation

/ Canny edge detection of * * * * * @ author yidong * @ the date 2020-05-18 * / class CannyEdgeDetectionActivity: AppCompatActivity() { private lateinit var mBinding: ActivityEdgeDetectionBinding private lateinit var mRgb: Mat override fun onCreate(savedInstanceState: Bundle?) { super.onCreate(savedInstanceState) mBinding = DataBindingUtil.setContentView(this, R.layout.activity_edge_detection) val bgr = Utils.loadResource(this, R.drawable.lena) mRgb = Mat() Imgproc.cvtColor(bgr, mRgb, Imgproc.COLOR_BGR2RGB) showMat(mBinding.ivLena, mRgb) } override fun onCreateOptionsMenu(menu: Menu?) : Boolean { menuInflater.inflate(R.menu.menu_canny, menu) return true } override fun onOptionsItemSelected(item: MenuItem): Boolean { when (item.itemId) { R.id.low_canny_edge_detection -> { lowCannyEdgeDetection() } R.id.high_canny_edge_detection -> { highCannyEdgeDetection() } R.id.blur_canny_edge_detection -> { edgeDetectionAfterBlur() } } return true } private fun showMat(view: ImageView, source: Mat) { val bitmap = Bitmap.createBitmap(source.width(), source.height(), Bitmap.Config.ARGB_8888) bitmap.density = 360 Utils.matToBitmap(source, SetImageBitmap (bitmap)} private Fun lowCannyEdgeDetection() {title = "Low threshold Canny edge detection" val result = Mat() Imgproc.Canny(mRgb, result, 20.0, 40.0, 3) showMat(mBinding. IvResult, Result)} private fun highCannyEdgeDetection() {title = "high threshold Canny edge detection" val result = Mat() Imgproc.Canny(mRgb, result, 100.0, 200.0, 3) showMat (mBinding ivResult, Result)} private fun edgeDetectionAfterBlur() {title = "Canny edge detection" val resultG = Mat() val result = Mat() Imgproc.GaussianBlur(mRgb, resultG, Size(3.0, 3.0), 5.0) Imgproc.Canny(resultG, result, 100.0, 200.0, 3) showMat(mBinding.ivResult, result) } }Copy the code

The results of

A higher threshold will reduce the influence of noise information on image edge extraction results, but also reduce the edge information in the results. So, the right threshold is critical.

The source code

Github.com/onlyloveyd/…