Digital image processing -- popular Canny edge detection

I have planned to present this series of blog posts in the form of animated interesting popular science , If you're interested Click here .

0. What is edge

Speaking of edges , It must be the lines composed of pixels with sharp changes in brightness in the image . From a visual point of view , The first thing we notice is some simple lines , Then these simple lines are combined into more abstract concepts to enable us to recognize what is in front of me . Just like the following figure , Just look at the edge map , Is it possible to see that there is a woman in the original picture ？

The edge graph on the right is actually the graph after extracting the edges from the original graph , It can also be seen intuitively , The so-called edge detection is nothing more than pixel level binary classification of the pixels of the whole image . Or the edge point （ In white ）, Or it's not the edge point （ In black ）. Showing these points becomes an edge graph .

Of course, there are many kinds of edge detection algorithms , This blog will first beep the most classic edge detection algorithm —Canny！！

1.Canny Edge detection algorithm flow

Actually Canny The steps of the algorithm are just a few ：
1. Gauss filtering
2. Calculate the gradient and gradient direction of the image
3. Non maximum suppression
4. Double threshold filter edge

Obviously, the first step is to reduce the noise in the image , Enhance the robustness of edge detection . The second step is to emphasize the edge , But there is ambiguity due to emphasis , So use the third step to filter some edge points . But the third step may not be clean , So there is the fourth step to filter it .so... Let's beep one by one .

2. Gauss filtering

Gaussian filtering is basically the same as other filter routines , It is nothing more than a filter core rubbing on the original image , Step by step like a paw , Devil like steps ... So how about the effect of Gaussian filtering , It depends on the size of the filter core and the value inside .

The main contradiction now is how to determine the value in the filter core . It's very simple , It is through such a formula ：

What is the intention of this formula ？ In fact, the value in the filter core should be filled into a two-dimensional Gaussian distribution as much as possible . We can take a chestnut ：
1. Suppose my filter core is 3*3 Of
2. Suppose the standard deviation of my Gaussian distribution is 1 That is to say σ=1
3.x and y Represents the coordinates of each point in the filter core relative to the central point , It's like soy sauce ：

With these assumptions , We can easily calculate the value corresponding to the filter core , It's like soy sauce ：

But there is a problem with the value calculated at this time , If you put all 9 All the values do not add up to 1！！！（ The probability should be 1） So we need to normalize it , Let all 9 The values add up to 1. In fact, normalization is very simple , That's it. 9 All the values add up, that is (0.0585+0.0965+0.0585+…+0.0585=0.7792), Then divide each value by this 0.7792, We can get the normalized filter kernel .（ At this time, you will find that all the values add up to 1）

And you can make up your brain , If the wave filter core size The larger , Then the value in each lattice is regarded as probability . In fact, it can be made into a dark purple picture （ A two-dimensional Gaussian distribution is obvious ）：

After determining the value of the filter kernel , You can filter happily .

3. Calculate the gradient of the image and the direction of the gradient

To calculate the gradient of the image , I will definitely think of the gradient operator of the image . stay Canny The gradient operator used in is Sobel operator , Say operator , In fact, it is the filter core .Sobel Operators are mainly divided into two , One is used to calculate the gradient in the horizontal direction , The other is used to calculate the gradient in the vertical direction .


therefore , For the original image, the gradient in the horizontal direction of the image can be calculated with the first filter kernel , With the second filter core, the vertical gradient of the image can be calculated .

With gradients in both directions , In fact, we can calculate the gradient and the direction of the gradient of the image . Because there are already horizontal and vertical , To calculate the total gradient , It's nothing more than Pythagorean theorem ~~~~

in other words
Gradient value of image = Square root （ Square of gradient amplitude in vertical direction + Square of gradient amplitude in horizontal direction ）

The direction of the image = arctan( Gradient amplitude in the vertical direction / Gradient amplitude in horizontal direction )

4. Non maximum suppression

Suppose that the graph with gradient direction now is maozi ：

The graph of gradient amplitude is maozi ：

If you want to do non maximum suppression , Just need one more thing , This is this. ：

The meaning of this expression is very simple , The square in the middle can be regarded as a 3*3 Region , Then the line represents the angle . such as （-1,1） The angle of this point is 45 degree ,(0, 1) The angle of this point is 0 degree . What's the use of this thing , Take a chestnut ：
If I want to plot the gradient magnitude 2 Xing di 2 The point listed ( The value is 144) Do non maximum suppression , Then I will see the value of my corresponding direction , apparently 26. that 26 Obviously and 45 Degrees are closer , So when I want to do non maximum suppression, the point of gradient amplitude to be compared is 45 Degree the point corresponding to that line , That is to say 5 and 3. It can be seen at this time that ,144>5 also 144>3, therefore 144 It's a maximum point , So this point will not be suppressed .

So if I want to compare the gradient amplitude graph 5 Xing di 2 The point of the column ( The value is 178) Do non maximum suppression , It's obvious that its direction, that is, the angle is 7 degree ,7 Du Li 0 Degrees closer , So when I want to do non maximum suppression, the point of gradient amplitude to be compared is 0 Degree the point corresponding to that line , That is to say 180 and 14. It can be seen at this time that ,178<180 also 178>14, therefore 178 Not a maximum point , So this point will be discarded , Assign him 0.

Obviously , After non maximum suppression of the whole graph , The point that is the maximum is preserved , Not all points of maximum value are assigned 0.

5. Double threshold filter edge

The purpose of edge detection is to set the edge points to 255, Non edge points are set to 0. But after non maximum suppression , Although some of the points in the figure have been suppressed into 0. But we still don't know which of the remaining points should be set as edge points . Some children's shoes may feel , Let me set a threshold ？ If my gradient value is greater than a certain threshold, I think it is an edge point . Of course you can , But the effect will not be very good . So the predecessors rolled out a routine of double threshold screening edges . The routine is shown in the figure ：

The routine can be easily seen from the picture , There will be two thresholds A and B(A<B), If the gradient value of my current point is smaller than A I don't think it's a marginal point when I'm young , If you compare B It must be a marginal point . This is easy to understand . That's between A and B What's your point ？Canny My strategy is if I'm somewhere between AB The point between him and greater than B The point is connected , Then I think this point is marginal , Otherwise it's not . This routine is actually very Chinese XX The exam is very similar , If my exam score is lower than the score line , That's for sure GG. If my score is much higher than the score line , Then it's delicious . If my score is moderate , Then I may look for relationships and thighs , If the relationship is hard enough , Then I may be happy .

OK, Such a process comes down ,Canny Edge detection is finished , I hope this blog will help you understand Canny The children's shoes of the general flow of the algorithm are of some help . You are also welcome to roast .