N-Point Hough transform for line detection

In this paper, we introduce the N-point Hough transform for the detection of a large number of planar lines in a noisy image. The N  -point Hough transform yields the randomized Hough transform and the three-point Hough transform if we set N=2N=2 and N=3N=3, respectively. From the viewpoint of the number of sample points required for the computation of lines, the N-point Hough transform is a generalization of the usual randomized Hough transform. The three-point Hough transform is introduced to increase the speed of the randomized Hough transform; the third point is used to avoid the selection of meaningless first and second sample points, which are used for the computation of the parameters of a line. This additional sample point guarantees the accuracy and robustness of a line detected using the first and second sample points. The N  -point Hough transform evaluates the accuracy and robustness of a computed line using additional (N-2)(N-2) points for each line. The evaluation in the N-point Hough transform is achieved by counting the cardinality of sample points in the neighborhood of this line as the support of the sample points for the acceptance of this line. First, to define the neighborhood of a line mathematically, in this paper we clarify the relationship between a line and a set of parameters in the voting space using geometric duality. This relationship allows us to define a metric in the voting space. The metric is used for the clustering of bins in the spherical voting space to guarantee the accurate and robust computation of lines. Finally, we evaluate the performance of the N-point Hough transform by comparing it with the randomized Hough transform, which is the two-point Hough transform in our framework of the voting method. This comparative study shows the geometric and computational advantages of the N-point Hough transform.