Figure 7: All points within hashed area support the line (RHO, THETA).
We first apply a zero-crossing Gaussian edge detector algorithm. Surprisingly, MATLAB's implementation of Canny's edge detector did very badly on these binary images, missing major sections of edges even after varying Canny's parameters. We were unable to determine the cause of this anomalous behavior and did not pursue the problem further since the Gaussian edge detector did reasonably well. For more information on edge detection, see [Trucco and Verri 1998].
We then use the Hough transform algorithm to find the equations of the detected lines. The Hough transform [Trucco and Verri 1998] accomplishes this by summing for each possible line in the image the number of points in the image on that line. It then selects the NUMLINES lines which have the largest support, where NUMLINES is a parameter to Hough. (Thresholding the number of lines effectively implements an image-dependant support size threshold.)
Obviously, it is necessary to quantize the parameter space. Polar parameters (rho, theta) are usually used because they give better resolution for a coarser quantization than do Cartesian coordinates. (They also allow vertical lines to be captured.) Thus, RHO_MAX and THETA_MAX give the number of discrete rho and theta units, respectively, by which to divide the space. We found that 120 for RHO_MAX and 360 for THETA_MAX give satisfactory performance without becoming computationally intractable.
An unfortunate side-effect of this quantization is that each line receives support not only from points actually on the line, but from any points within an area (in image space) of the shape shown in the figure below.
Figure 7: All points within hashed area support the line (RHO, THETA).
Consequently, points on a straight line will contribute to multiple lines passing through its vicinity, causing multiple lines to be found where only one should be. Jagged edges from the edge detector only exacerbate the problem. Besides indicating the existance of more edges than there are, this can also cause us to miss edges since we threshold on the number of lines. If NUMLINES is 10, for example, and Hough returns twenty lines for one long edge, even slightly shorter edges do not stand a chance.
To partially rectify this situation, we bucket the output from Hough so that one average line replaces the set of similar lines in a neighborhood of parameter space. However, there is a tradeoff to be made here: larger buckets can result in the combination of what should be distinct lines into average lines that do not look like any of the actual lines they represent. Given that the edges of the doors in our images were usually at least fifteen rho units apart, values of 5 and 20 for RHOBUCKSIZE and THETABUCKSIZE, respectively, seemed to work well in most instances.
A disadvantage of thresholding is that short edges (relative to the size of the object image) receive small support and may be ignored, even if the effects of quantization are negligible. Noise further complicates the situation by adding support to lines which do not really exist in the image. If there is enough noise (as is the case when noise from the carpet becomes associated door objects), these spurious lines can be indistinguishable from short lines as far as their support is concerned. The most important consequence of the difficulty in detecting short lines is that top and bottom edges of doors are often impossible to catch since they are already short relative to the door sides and are made shorter still by perspective. For this reason, the recognition stage only relies on discovering the sides of doors.
In the end, we chose to use Hough because of its simplicity and because of the existance of code implementing it [D. Ioannou 1995]. However, it is certainly not the only algorithm we could have tried. Contour-finding algorithms such as the SNAKE algorithm [Trucco and Verri 1998] may have also provided fertile ground for experimentation. Also, although the parameters we found experimentally worked fairly well for most images, there, there is certainly a great deal of room for further optimization.
The following images show the output from the edge detector and the lines discovered by Hough after bucketing, with NUMLINES equal to 10.
 |
 |
|
Next: Recognition