TY - JOUR

T1 - N-Point Hough transform for line detection

AU - Mochizuki, Yoshihiko

AU - Torii, Akihiko

AU - Imiya, Atsushi

PY - 2009/5

Y1 - 2009/5

N2 - 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 = 2 and N = 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) 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.

AB - 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 = 2 and N = 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) 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.

KW - Continuous voting space

KW - Discrete voting space

KW - Geometric duality

KW - Hough transform

KW - Projective geometry

KW - Random sampling

KW - Randomized hough transform

KW - Spherical geometry

KW - Three-point Hough transform

UR - http://www.scopus.com/inward/record.url?scp=67349143164&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67349143164&partnerID=8YFLogxK

U2 - 10.1016/j.jvcir.2009.01.004

DO - 10.1016/j.jvcir.2009.01.004

M3 - Article

AN - SCOPUS:67349143164

VL - 20

SP - 242

EP - 253

JO - Journal of Visual Communication and Image Representation

JF - Journal of Visual Communication and Image Representation

SN - 1047-3203

IS - 4

ER -