The Hough Transform [Part 1]

Optional Reading

  1. Duda, Richard O., Peter E. Hart, and David G. Stork. Pattern classification. Vol. 2. New York: Wiley, 1973. Section 9.2.3

Recommended Jupyter Theme for presenting this notebook:

jt -t grade3 -cellw=90% -fs=20 -tfs=20 -ofs=20

  • Today we're going to talk about how we can find lines, or other shapes, using "edge images", like the ones we computed in our lecture on the Sobel-Feldman operator.
  • One of the first people to think seriously about this problem was Paul Hough, while working on an interesting experimental physics problem.

  • In 1952 Donald A. Glaser invented a new tool for studying partical physics - the bubble chamber.
    • Glaser was awarded the Nobel Prize in 1960 for his invention.
  • The bubble chamber worked by tracing the bubbles formed by charged particles moving through a superheated liquid.
  • Physicists took pictures of the bubbles as particles moved through the chamber using multiple cameras mounted around the bubble chamber.
  • By analyzing the the radius of curvature of the bubbles, physicist could infer the momentum of individual particles.
  • Bubble chambers and the data they produce have allowed physicist to make some pretty incredible discoveries, such as weak neutral currents - Nice video from 60 symbols

A Minor Problem with the Bubble Chamber

  • One issue with the bubble chamber was handling sheer volume of data it produced.
  • In the early 1950s, Paul Hough, a recent Cornell PhD graduate joined Donald Glaser, the inventor of the Bubble Chamber, at the University of Michigan.
  • During this period, Hough began working on methods to automate the tedious task of detecting particle tracks in bubble chambers. Fun Talk from Paul Hough on the bubble chamber.
  • One particularly difficult problem was automatically detecting lines in images.
  • Let's give this problem a little thought:

  • Let's think about our pixels or edges as points on the $xy$ plane for a moment, and consider how we might fit one or more lines to a set of such points.
  • As we saw in our lecture on The Sobel Feldman Edge detector, we have some good algorithms that can return high values for edges - now we need to think about how we can group those detections into a single line.
  • [Mild Disclaimer] We're leaving out one step taken by Hough. Before fitting lines, Hough broke images into small "framelets", and analyzed each framelet seperately. This meant that Hough typically only needed to find one line within each framlet. He're we're considering the slightly more complex case of how we might find multiple lines, but the outcome will be the same.
  • What do you think?
  • What would you do if you woke up in Hough's shoes?
  • Can you think of an algorithm that would give us the best fit set of lines to a set of points, while ignoring outliers?

  • One relatively simple approach here is to "try all the lines".
  • For each unique line formed by 2 of our points, we could check to see if any on other points lie on this line.
  • We could then return all the line or lines that intersect a relateively large number of points.
    • There are lots of other valid approaches here, such as RANSAC - check out Forsyth, David A., and Jean Ponce. Computer vision: a modern approach. Prentice Hall Professional Technical Reference, 2002. Chapter 10.
  • Let's give the the "try all the lines" approach a little more thought.

Explanation

  • Each of our $n$ points could be paired with any of the other $n-1$ points, making for $n \cdot (n-1)$ possible combinations of two points.
  • However, half of these pairs are redundant, because a line from $(x_1, y_1)$ to $(x_2, y_2)$ in indistinguishable from a line from $(x_2, y_2)$ to $(x_1, y_1)$. So we need to divide our number of possible pairs, resulting in:

$$ \frac{n \cdot (n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \approx \frac{n^2}{2} $$

  • So the correct answer is b.

Ok, so we're done?

  • So we've found one way to find sets of of co-linear points, but is this a good approach?
  • Any possible problems we might run into applying to approach, to let's say, edges computed with the Sobel-Fieldman operator like the ones below?

In practice, two big issues will likely pop up when we go to code our algorithm:

1. Slow AF. As we figured out earlier, our "try all the lines" algorithm scales as $\frac{n^2}{2}$. The images above are 256x256, and have, on average 250-500 edge pixels. This makes for between 30k and 125k lines we need to test. Further, these images are quite small by modern standards, and very low noise (<1% of pixels are edges). If we had a noisy Full HD image for example, where 10% of our pixels were detected as edges, this would make for $((1920 \cdot 1080 \cdot 0.1)^2)/2 \approx 21B $ lines to test! This would be slow on a modern computer, and incomputable in the 1950s when Hough worked on this problem.

2. Susceptible to Noise. The edge points that show up in our images above are not exactly co-linear. This means that testing each of our lines is a bit more complex. We could measure the distance of points to our line, as use some kind of thresholding label points as "approximately co-linear". This may work well, but the point here is that noise complicated our "try all the lines" approach.

Here's Where it Gets Interesting

  • There is a very slick modern solution to Hough's problem that allows us to simultaneously address problems (1) and (2) above, called The Hough Transform.
  • What I think is really interesting here is that Paul V. C. Hough did not create what we call the Hough Transform today.
  • What he did figure out is the kernel of the idea.
  • After being puzzled with the tough problem of how to efficiently line detect noisy co-linear points in images, Hough had an interesting idea walking home one day from work.
In [1]:
#Little trick to progress through slides within the notebook
from IPython.display import Image, display
from ipywidgets import interact

#Quick method to let me step through "slides"
def slide_show(slide_num=1):     
    display(Image('../graphics/hough_idea_kernel/' + str(slide_num).zfill(2) + '.png'))
In [2]:
interact(slide_show, slide_num = (1, 5));
  • Hough's idea involves transforming our points into a new space.
  • Specifically, the parameter space of 2D lines (sometimes called Hough Space).
  • The key idea is simple. Every point becomes a line.
    • The slope of the line is determined by the point's $y$ value.
    • The y-intercept of the line is determined by the point's $x$ value.
    • That's it. :)

Now, why might this transformation be useful?

  • What is the relationship between colinear points after being mapped to hough space?

  • A careful look at our video suggest that colinear Points in the $xy$ plane become intersecting lines in hough space!
  • Let's see we we can prove our hunch!

  • Ok, if you were able to prove this interesting fact, great!
  • If not, don't give up yet!
  • Before we go over the answer, let's try to figure out where our lines will intersect in Hough Space.

Explanation

  1. For colinear points $\{ (x_i, y_i) \}$, there must be some values of $m$ and $b$ such that $y_i = m x_i + b$, $\forall i$. (There must be one line through the points)
  2. The equations of intersecting lines in Hough Space will be satisfied at mutual intersection points: $v_1 = y_i u_1 + x_i, \forall i$. (When we plug in the intersection point $(u_1, v_1)$ into the equations of intersecting lines, each equation will hold true)
  3. With a little re-arrangement, we can show that (2) is mathematically equivalent to (1):

$$ v_1 = y_i u_1 + x_i \\ y_i u_1 = v_1-x_i \\ y_i = -\frac{1}{u_1} x_i + \frac{v_1}{u_1} $$

This equation is equivalent to (1), given that $m = - \frac{1}{u_i}$ and $b=\frac{v_1}{u_1}$. QED.

Finally, we can use this result to solve our second problem, finding our intersection point. We just need to solve for $u_1$ and $v_1$: $u_i = -\frac{1}{m}$, and $v_1 = b \cdot u_1 = -\frac{b}{m}$.

The problem of finding colinear points is mathematically equivalent to finding intersecting lines in Hough Space.

Now What?

  • Ok, so we've seen that we can pose our finding colinear points problem as finding intersecting lines in hough space. These problems are mathematically equivalent.
  • But how does this really help us? We started out with an approach to finding colinear points, "trying all the lines", that had a couple of issues:
    • Slow
    • Susceptable to Noise
  • Does solving our problem in hough space help us resolve either of this issues?!
  • This is where we need to come back to our larger story. We really need two more ideas to make this all work.
  • Next time, we'll finish our story and add the missing pieces that make the Hough Transform work.
  • Before we wrap up part 1 of this story though, let's look at one more issue with Hough's implementation of the transform that we'll also need to resolve.
  • Specifically, what happens when we draw horizontal lines:

  • As you can see horizontal lines result in a bit of a problem! They intersect at $\infty$ in Hough Space!
    • We can see this in our equations above: $u_i = -\frac{1}{m}$ $\rightarrow$ $\infty$ as $m \rightarrow 0$.
  • Hough did have a solution to this - soving the problem twice - once with a $90^\circ$ rotation!
  • However, even with this fix, having intersection points trail off to infinity creates a potentially large computational burden.
  • Fortunately there is a good solution here, will dig in next time.
  • Questions to think about:

1. How can we use the Hough Transform to efficiently find noisy colinear points?

2. How might we modify the Hough Transform to avoid having intersection points at $\infty$?

Appendix A - Hough's Patent

  • Hough patented his idea, published in 1962.
  • The missing pieces from Hough's tranform would be published by other reserachers over the next 10 years, likeley making the patent not particularly useful.

  • Hough desicribed his idea in geometrical terms in paragraphs (2) and (3) of his 1962 patent, shown above.
  • In my opinion, Hough's description is a bit tough to follow. However, once you understand the core idea of the Hough Transform, it's interesting to go back and review how Hough presents it - patents are often dense a tough to follow like this, so spending a little time with Hough's patent is good practice!

Appendix B - Downloading Data + Videos

In [3]:
#(Optional) Download data + videos if you don't have them.
import os, sys
sys.path.append('..')
from util.get_and_unpack import get_and_unpack

if not os.path.isdir('../data/'):
    url = 'http://www.welchlabs.io/unccv/the_original_problem/data/data.zip'
    get_and_unpack(url, location='..')
    
if not os.path.isdir('../videos/'):
    url = 'http://www.welchlabs.io/unccv/the_original_problem/videos.zip'
    get_and_unpack(url, location='..')