The Hough Transform: New and Improved!

  Ok, well it's still not better than a kerneled transform, but I am getting pretty pictures without the use of any trig! To sum up what I'm doing, I'm trying to use python's lambda expressions to generate a function in Cartesian space from the given points. Then I want to run BFGS over that function to find local maxima. By multiplying r = x_0 cos( theta ) + y_0 sin( theta ) through by r and rewriting as x^2 + y^2 = x_0 x + y_0 y , it's easy enough to see that the hough transform of a given point is actually a circle with one point at the origin and centered at \left( \frac{x_0}{2},\frac{y_0}{2}\right).
  This has the nice property that it's easy to calculate the distance between a given line ( point in hough space ) and the nearest point on the circle as a single square root.

  On the down side, because the hough transform usually takes advantage of the distortion of euclidean distance for small \theta , the end result has an absolute maxima at ( 0, 0 ). This maxima is very predictable, so I'm going to try just dividing by a function which is an idealized model near the origin, but quickly approaches 1 instead of 0 in every direction.
  Still, without further ado, some pictures:
 This image shows a single line: x + y = 10. In hough space this corresponds to the maxima at (5, 5). notice the nasty spurious point (0, 0).
x + y = 10, x + y = -10, and x + y = 20.

Just x + y = 10 and x + y = 20

x + y = 10, y - x = 10 and y = -7. This is a fairly unfavorable set of points. I think the top left maxima would be rather hard for a computer to locate.
The same three lines as above, but this time I picked sample points in the triangle. Much easier to locate all three maxima.

Update: Quotienting out the central maxima works! This is the same triangle data set as above.

No comments:

Post a Comment