Rectangle detection with Hough transform

Question

For those of you wondering about the paper, it's:

Rectangle Detection based on a Windowed Hough Transform by Cláudio Rosito Jung and Rodrigo Schramm.

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

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

You must then perform peak paring given by equation (3) in section 4.3 or

where represents the angular threshold corresponding to parallel lines and is the normalized threshold corresponding to lines of similar length.

The accuracy of the Hough 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

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.