How Hough Transform works


Hello, my name is Thales Sehn Körting and I am going to present how the Hough transform works The basics of hough Transform is to find aligned points in images that create lines Suppose that we have this input image here And then we’ll apply some edge extraction algorithm and obtain some images like these which highlights the main edges of the images and we apply the Hough transform in order to detect points in images that create these lines here highlighted in colors and how hough transform works Let’s consider this x and y plane and here we provide a very simple line in Red The Basic equation of this line can be describe it in terms of y and x and now so the parameters a and b In this case the parameters a and b are used to define the angulation of this line here. This line we have lots of combination of values of x and y and we have a fixed value a and b. Here we define the parameters of this line now. Let’s invert and consider not the plane xy but the plane a and b. So we are going to create the plane a and b which can be called the feature space and in this feature space this point here x i and y i defines a lot of possibilities here and also the other point x j and y j considering different parameters of a and b to find this line in this feature parameters, so if we Intersect these two lines here in the feature space we are going to define this point a and b where these two Lines here match and is exactly in this feature Combination of a and b which is this red line is [defined] [in] the region of space x and y? The hough Transform is based Exactly on this feature space here So if we have these two points here detected as edges in our edge image so it will define one point here if you have lots of Points here, you’re defining a line all the points will match Exactly in this point and as long as this combination of points or cure lots of time This means that we have aligned [defined] it in this feature space Another way to consider this feature space is to consider not the a and B parameters but the Data and also Row parameters which also Define a line equation But in terms of Angle the theta Angle and also our radius defined by this row value so we’re a Write the equation in terms of x times cosine of theta plus y times sin [of] theta Equal to Rho the radius here So they have transformed basically do this So they have transform can be viewed in terms of algorithms like this we have An algorithm that stays looking for all the points looking for edge images and when it finds some edge point it starts to iterate over all the Possible [Theta] in Row Values and Define exactly the occurrences of These points here in these feature space as long as this line occurs here, and it [founds] a Correspondence terms of other points here it will sum in terms of these space here and We can see that here. We have zero for all the values minus Theta from this side, plus Theta from this side minus row for this side and plus row for this side you can [see] that as long as the Algorithm runs it will discover different combinations now It will it is highlighting this possibility of a line here and define it by all these points in the end We will see peaks in terms of values in these which is they have space and all the Widest points will Define the detected lines in the input image in the end of the Hough transform Algorithm we have to Look in this image for the pigs which according to this scale is defined by the widest points So here we have a pig here another pig here another pig these pigs stands for the detected Lines in the half space We have just one example here Which is this pig based on lots of points detected here in this and this pig? Stands for exactly this line here detected. It’s easy to note that in this case We have 1 2 3 [&] 4 lines possible to be detected in this feature space which is represented by 1 2 3 and now 4, the 4th peak in terms of Detected points in the half space and the algorithm goes up to the end of the image The main reference that I have used is the well-known Digital Image Processing book written by Gonzalez and Woods So thanks for your attention, and this is how the Hough Transform works

84 thoughts on “How Hough Transform works

  1. Thank you very much for your explanation. It was exhaustive and very comprehensive. The graphics helped me a lot to understand the entire process. My compliments!

  2. I would like to have your permission to publish your video in shorter version. Please check this out.

    https://youtu.be/jsze_J7zD3c

    If you are not ok with that I will make at as personal video right away.

    Best Regards,

  3. This is one good explanation. I just have one question. Why is a point in xy plane a line in ab plane and not any other shape? Same thing or a circle?
    Please let me know.

  4. How do you know where the lines start and stop? I mean, you have detected that there is a line with r=xcos30 + ysin30. Fine. Now there are some 4 sections that lay on same line (i.e. there are gaps). How do you know where are the boundaries?

  5. Hmm.. i'm studying for a test. I didn't understand my script at all… but now it's pretty simple. Thank you Thales.

  6. Man, that's awesome, this is a terrible concept to understand without the geometric explanation…

    I suggest to you to make videos about the other variations to this transform, to detect geometric shapes and the lines in real time, for exemple…

  7. Thanks Thales. Most informative channel about AI. Please supply +1000 videos! Oh! What a wonderful day!

  8. Finally! It made sense both visually & mathematically. The animation of it's working is the best part. Thanks for sharing.

  9. This video was soooooooo useful! I have a paper due tomorrow on Hough Transform, and how it compares to Inverted Gradient Hash Maps.

    This was amazingly helpful. I was on struggle street. Thank you!!

  10. Muito bom! Este video me ajudou muito com o meu Master project. A animação ajudou muito na intuição do algoritimo.

    Matheus ~ Sheffield

  11. Hi,

    I am getting this error in OpenCV probablistic hough lines.

    please help to resolve :-

    —> for x1, y1, x2, y2 in lines[0]:

    cv2.line(image, (x1,y1), (x2,y2),(0,255,0), 3)

    ValueError: not enough values to unpack (expected 4, got 2)

  12. The animation is awesome! I have a very visual memory, and this helped me A LOT to understand exactly what's going on. Thank you so much!!!

  13. So, I have a question. On the Generalised Hough Transform, the difference is that we don't compare with line equations. Instead we compare with the target form/path – for every rotation and scale possible. Is that it? If so, it looks very heavy to calculate that.

  14. Amazing animation! For me its very hard to fallow only formulas and a lot of words. But that animation made me understand the idea behind all this! Thank you! 😀

  15. At 1:55 how can the green line have a positive slope? Both (Xi, Yi) and (Xj, Yj) have a negative value for a, so in feature space both lines should have a positive slope right? I do believe that your eplanation is correct, however I still have trouble to grasp this transformation. It doesn't make sense to me how the lines are drawn in feature space.

  16. Thank you for this video! The animation is very helpful and your explanation is easy to follow. You also sound a bit like Javier Bardem!

  17. Hi, I am not getting the exact idea behind this. So first, we are detecting edges using canny or any algorithms which leaves us with edges in the image. Now, edges can be lines in the image which is what you explained as y = ax +b where a is the slope and b is the intercept of the line. In the fitter space, I will call it as hough space, my question is "How points in the line equation of the edge becomes line in the hough space"?

  18. You have an amazing way of explaining things. Love your videos. I wish you make some more videos specially on LSTM.

  19. Thales o video é muito bom. Bem explicado. Faça um em português também. Há uma carência muito grande de videos neste nível em nossa língua.

  20. This is amazing. I mean my prof hasn't done it half that good in double the time.
    Just one little detail I had initially trouble with: we do not use y = a*x+b because a is infinite for a line that has 90 degrees.

Leave a Reply

Your email address will not be published. Required fields are marked *