Let me show you some examples of how this kind of edge detectors can be used to detect more complex objects. And the first kind of such object is line. So its called line detection. And it has plenty of applications, for example, in line detections in autonomous cars and autonomous vehicles. When you have to automatically obtain the line to track some lines between track positions. So speaking about detection, we should say that first we have to express each line using its so called line equations. So each line can be defined as such kind of equation and you have to fix the theta. It's an angle between the zero point of origin and the current point of the line. It's a theta angle and you have the distance rho. So each line is expressed by this kind of parameters rho. So each point in the line expressed by this kind of parameters, rho and theta. Okay, so let me show how to detect lines using so called Hough transform. So at first for every point you again find the orientation of the gradient. You can preprocess the input images in the Canny edge detector. But anyway you have to, again, compute the gradient using the first derivative Sobel filter. And then you compute the orientation of the gradient using this equation. Using the arctan of the ratio between the output of y component of the derivative and the output of x component of the derivative. So you obtain this kind of orientation for each point in the edge. Then you estimate the distance rho between this point and given by its coordinates x and y and given this angle theta. So you can estimate this rho by using the line equation from the previous slide. And then you add 1 to accumulator array of the pair of rho and theta. So in order to implement this kind of operation, you have to understand that theta can be any angle between 0 and 180 degrees. So in order to efficiently implement it, you have to discretize the values of rho and the values of theta. It's typical to use several angles to discretize the value of angle theta and it's typical to use several to divide the whole range of any possible distance. It's between 0 and the length of the diagonal of the input image. So we quantize them. And in the accumulator array, we have a two dimensional accumulator array. The first part of this accumulator, the first dimension of this accumulator is defined by the number of different distances rho. And another dimension will be defined as the number of different angles theta. After processing all the points of an input image, or even all points in the edges, you just set some kind of threshold for this kind of accumulator and you return pairs, rho and theta. So you return all lines for which the counter exceeds threshold it means that there are several lines, several points in edges, for example, which correspond to the same line. In this particular case, you don't obtain the starting and end point of this line. So you obtain the equation just for the whole line. But this algorithm can be easily modified just by storing not only the number of points that correspond to these values of rho and theta, but also storing all the points in this accumulator array. So all the points from the edges which give us the highest values of this accumulator array. And you see here the pretty known video which shows the process of this Hough transform. By processing on the several points, we assume that these points correspond to edges or something like this. And you see that after a repeating of this kind of operation, this two dimensional accumulator clearly shows you that there are several lines. And the most important line is sees from left bottom to top right part here. This kind of Hough transform can be used to detect more difficult edges, more difficult patterns. And the original idea of Hough transformation can be used too for circle detection. So you see here the circle equation and each circle is defined by three parameters. The center, all in the center part of the circle, and the radius. So the coordinates, x and y coordinates of the center, and the radius. So three parameters. And in such case, you can use a three dimensional accumulator. So let me recall that in line detection, we have only two parameters, rho and theta. And in this case you had a two dimensional accumulator. And in this case it can be implemented much faster at first and much more robust because you don't need many points to be presented in the in the line. But in order to implement such kind of Hough detection filter you see that there are three dimensional accumulator and it's obvious that in this case the detection of circle is much more difficult. So we need to, that the circle will be really visible in order to implement such kind of algorithm. But there is some kind of modification of this algorithm which can be efficiently used and where that doesn't need a three dimensional accumulator. So let me describe it in detail. At first you use some kind of edge detector. And it's typical to use Canny edge detector because of its properties, of its nice properties. Because it's probably one of the best edge detectors used in traditional computer vision. So you detect all edges. After that, you increase the accumulator based on the gradient orientation in each pixel in the edge. So you compute the gradient magnitude. You can compute the gradient orientation similarly to what I described in the previous slide for line detection. And then you increase. So you assume that the center of the circle is located in the line which starts in this particular point, in this corner, in this part of the edge. And this line, the direction of this line is determined by the gradient orientation. So in this case, you can use very simple accumulator and you repeat this procedure for all points of the edge. And after that, you use the same accumulator values for all points inside this line. So you have plenty of lines, one for each point. So you choose such kind of points, candidates for centers for which there is some kind of intersection of most part of these lines inside this video. Again, you have some threshold for such kind of accumulator and you see that you obtain this central radius. Okay, again, it's not ideal, it's not ideally estimated. So you need some kind of quantization for this kind of accumulator. But it's much better to use only one accumulator instead of three dimensional accumulator here. And after that, after you obtain the center of each circle there. It's typical to have several circles. In this case, you have several centers with rather high value of accumulator from the second step. And after that, you just estimate the radius by using the points from this kind of accumulator. Again, you save all the points which influenced the value of accumulator, all the points from the edge. And after that you simply estimate the radius. So you have all points in the circle. You have the center. You estimated the center of the circle, and that's why you use this kind of equation from the top part of this slide in order to find the radius. And in this case, you estimated all the circles because you find all the centers and you find all their radiuses. This kind of transformation can be generalized for arbitrary curves, but in order to implement it, you need two parts. So again, you have to implement some kind of edge detector, like Canny detector. Again, you have to find gradient orientation and gradient magnitude. So you choose only points with rather high gradient magnitudes, it's a point of an edge. And after that you compute the graduate orientation at each point, it's like a theta parameter. After that, you need to define this arbitrary curve which you use, which you need to find using this operator theta. So how to do it? It depends on the particular curve. So for example, if this curve was a circle, then you saw that the angle between some kind of pivot point or reference point. It was the center of the radius. So this phi angle was equal to the theta angle of the gradient orientation, but it's not typical for any kind of curve. So it's assumed that this kind of curve can be assigned by using the angle of normal line, given the particular edge. In this case, it's assumed that this arbitrary curve can be expressed by some reference point. And you have angle between some horizontal, for example, line between the point from the edge and some reference point. It was center part of the circle in the previous slide. So we have two parameters, again, the distance to this reference point and the angle to this reference point, which can be expressed based on the gradient orientation. After that, you repeat the procedure from the previous slide. So you process all points of an edge. You compute possible potential reference point using the angle, using the distance probably. Or you just compute the line between a possible reference and the current edge point. Then we repeated this process for all reference points. And then you vote again for the best reference point. And after that, if you know this reference point, and I assume that you can draw your arbitrary curve in this particular case. So again, it's so called generalized Hough transform, and it can be implemented using class GeneralizedHough from OpenCV. And it let you define, and find any possible template, it if it's possible to define the distance and the angle as I told you previously.