Rectangle detection with Hough transform

Question

I'm trying to implement rectangle detection using the Hough transform, based on this paper.

I programmed it using Matlab, but after the detection of parallel pair lines and orthogonal pairs, I must detect the intersection of these pairs. My question is about the quality of the two line intersection in Hough space.

I found the intersection points by solving four equation systems. Do these intersection points lie in cartesian or polar coordinate space?

Answer 1

I am not a mathematician. I am willing to stand corrected...
From Hough 2) ... any line on the xy plane can be described as p = x cos theta + y sin theta. In this representation, p is the normal distance and theta is the normal angle of a straight line, ... In practical applications, the angles theta and distances p are quantized, and we obtain an array C(p, theta).
from CRC standard math tables Analytic Geometry, Polar Coordinates in a Plane section ... Such an ordered pair of numbers (r, theta) are called polar coordinates of the point p. Straight lines: let p = distance of line from O, w = counterclockwise angle from OX to the perpendicular through O to the line. Normal form: r cos(theta - w) = p. From this I conclude that the points lie in polar coordinate space.

Answer 2

The link to the referenced paper does not work, but if you used the standard hough transform than the four intersection points will be expressed in cartesian coordinates. In fact, the four lines detected with the hough tranform will be expressed using the "normal parametrization":

rho = x cos(theta) + y sin(theta)

so you will have four pairs (rho_i, theta_i) that identifies your four lines. After checking for orthogonality (for example just by comparing the angles theta_i) you solve four equation system each of the form:

rho_j = x cos(theta_j) + y sin(theta_j)
rho_k = x cos(theta_k) + y sin(theta_k)

where x and y are the unknowns that represents the cartesian coordinates of the intersection point.

Answer 3

For those of you wondering about the paper, its:

Rectangle Detection based on aWindowed Hough Transform

by Cl´audio Rosito Jung and Rodrigo Schramm (don't know how to do the ´ over the a in this text field).

Now according to the paper, the intersection points are expressed as polar coordinates, obviously you implementation maybe different (the only way to tell is to show us your code).

Assuming you are being consistent with his notation, your peaks should be express as:

H_1 = (\rho_1,\theta_1)
H_2 = (\rho_2,\theta_2)
...
H_m = (\rho_m,\theta_m)

you then must preform peak paring given by equation (3) in section 4.3 or

\delta\theta = |\theta_i - \theta_j| < T_\theta
\delta\rho= |\rho_i- \rho_j | < T_\rho
|C(\rho_i ,\theta_i ) - C(\rho_j ,\theta_j )| < T_L \frac{C(\rho_i ,\theta_i )+C(\rho_j ,\theta_j )}{2}

where T_\theta represents the angular threshold corresponding to parallel lines and T_L is the normalized threshold corresponding to lines of similar length

Note: I used LaTeX notation for clarity

Answer 4

The accuracy of the Houh space should be dependent on two main factors.

The accumulator maps onto Hough Space. To loop through the accumulator array requires that the accumulator divide the Hough Space into a discrete grid.

The second factor in accuracy in Linear Hough Space is the location of the origin in the original image. Look for a moment at what happens if you do a sweep of \theta for any given change in \rho. Near the origin, one of these sweeps will cover far less pixels than a sweep out near the edges of the image. This has the consequence that near the edges of the image you need a much higher \rho \theta resolution in your accumulator to achieve the same level of accuracy when transforming back to Cartesian.

The problem with increasing the resolution of course is that you will need more computational power and memory to increase it. Also If you uniformly increase the accumulator resolution you have wasted resolution near the origin where it is not needed.

Some ideas to help with this.

1. place the origin right at the center of the image. as opposed to using the natural bottom left or top left of an image in code.
2. try using the closest image you can get to a square. the more elongated an image is for a given area the more pronounced the resolution trap becomes at the edges
3. Try dividing your image into 4/9/16 etc different accumulators each with an origin in the center of that sub-image. It will require a little overhead to link the results of each accumulator together for rectangle detection, but it should help spread the resolution more evenly.
4. The ultimate solution would be to increase the resolution linearly depending on the distance from the origin. this can be achieved using the

---

    (x-a)^2 + (y-b)^2 = \rho^2

---

circle equation where
    - x,y are the current pixel
    - a,b are your chosen origin
    - \rho is the radius
once the radius is known adjust your accumulator
resolution accordingly. You will have to keep
track of the center of each \rho \theta bin.
for transforming back to Cartesian