×
Goldenshluger, Alexander; Zeevi, Assaf

The Hough transform estimator. (English) Zbl 1056.62030

Ann. Stat. 32, No. 5, 1908-1932 (2004).
Summary: This article pursues a statistical study of the Hough transform, the celebrated computer vision algorithm used to detect the presence of lines in a noisy image. We first study asymptotic properties of the Hough transform estimator, whose objective is to find the line that “best” fits a set of planar points. In particular, we establish strong consistency and rates of convergence, and characterize the limiting distribution of the Hough transform estimator. While the convergence rates are seen to be slower than those found in some standard regression methods, the Hough transform estimator is shown to be more robust as measured by its breakdown point.
We next study the Hough transform in the context of the problem of detecting multiple lines. This is addressed via the framework of excess mass functionals and modality testing. Throughout, several numerical examples help illustrate various properties of the estimator. Relations between the Hough transform and more mainstream statistical paradigms and methods are discussed as well.

Cited in 9 Documents

MSC:

62F12 Asymptotic properties of parametric estimators
68T45 Machine vision and scene understanding
65C60 Computational problems in statistics (MSC2010)
62F35 Robustness and adaptive procedures (parametric inference)
62E20 Asymptotic distribution theory in statistics
62H35 Image analysis in multivariate analysis

Keywords:

breakdown point; computer vision; cube-root asymptotics; empirical processes; excess mass; Hough transform; multi-modality; robust regression
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Anderson, T. W. (1955). The integral of a symmetric unimodal function over a symmetric convex set and some probability inequalities. Proc. Amer. Math. Soc. 6 170–176. · Zbl 0066.37402 · doi:10.2307/2032333
[2] Billingsley, P. (1968). Convergence of Probability Measures . Wiley, New York. · Zbl 0172.21201
[3] Chernoff, H. (1964). Estimation of the mode. Ann. Inst. Statist. Math. 16 31–41. · Zbl 0212.21802 · doi:10.1007/BF02868560
[4] Daniels, H. E. (1954). A distribution-free test for regression parameters. Ann. Math. Statist. 25 499–513. · Zbl 0056.13403 · doi:10.1214/aoms/1177728718
[5] Davies, L. (1990). The asymptotics of \(S\)-estimators in the linear regression model. Ann. Statist. 18 1651–1675. JSTOR: · Zbl 0719.62042 · doi:10.1214/aos/1176347871
[6] Donoho, D. (1988). One-sided inference about functionals of a density. Ann. Statist. 16 1390–1420. JSTOR: · Zbl 0665.62040 · doi:10.1214/aos/1176351045
[7] Donoho, D. and Huber, P. J. (1983). The notion of breakdown point. In A Festschrift for Eric L. Lehmann (P. J. Bickel, K. A. Doksum and J. L. Hodges, Jr., eds.) 157–184. Wadsworth, Belmont, CA. · Zbl 0523.62032
[8] Dudley, R. M. (1999). Uniform Central Limit Theorems . Cambridge Univ. Press. · Zbl 0951.60033 · doi:10.1017/CBO9780511665622
[9] Hartigan, J. A. (1987). Estimation of a convex density contour in two dimensions. J. Amer. Statist. Assoc. 82 267–270. · Zbl 0607.62045 · doi:10.2307/2289162
[10] Hough, P. V. (1959). Machine analysis of bubble chamber pictures. In International Conference on High Energy Accelerators and Instrumentation (L. Kowarski, ed.) 554–556. CERN.
[11] Groeneboom, P. (1989). Brownian motion with a parabolic drift and Airy functions. Probab. Theory Related Fields 81 79–109. · doi:10.1007/BF00343738
[12] Groeneboom, P. and Wellner, J. (2001). Computing Chernoff’s distribution. J. Comput. Graph. Statist. 10 388–400. · doi:10.1198/10618600152627997
[13] Johnstone, I. M. and Velleman, P. F. (1985). The resistant line and related regression methods (with discussion). J. Amer. Statist. Assoc. 80 1041–1059. · Zbl 0594.62077 · doi:10.2307/2288572
[14] Kim, J. and Pollard, D. (1990). Cube root asymptotics. Ann. Statist. 18 191–219. JSTOR: · Zbl 0703.62063 · doi:10.1214/aos/1176347498
[15] Kiryati, N. and Bruckstein, A. M. (1992). What’s in a set of points? (Straight line fitting). IEEE Trans. Pattern Anal. Mach. Intell. 14 496–500.
[16] Leavers, V. F. (1993). Which Hough transform? CVGIP : Image Understanding 58 250–264.
[17] Molchanov, I. S. (1998). A limit theorem for solutions of inequalities. Scand. J. Statist. 25 235–242. · Zbl 0915.60040 · doi:10.1111/1467-9469.00100
[18] Müller, D. W. and Sawitzki, G. (1991). Excess mass estimates and tests for multimodality. J. Amer. Statist. Assoc. 86 738–746. · Zbl 0733.62040 · doi:10.2307/2290406
[19] Pollard, D. (1984). Convergence of Stochastic Processes . Springer, New York. · Zbl 0544.60045
[20] Polonik, W. (1995). Measuring mass concentrations and estimating density contour clusters—an excess mass approach. Ann. Statist. 23 855–881. JSTOR: · Zbl 0841.62045 · doi:10.1214/aos/1176324626
[21] Princen, J., Illingworth, J. and Kittler, J. (1992). A formal definition of the Hough transform: Properties and relationships. J. Math. Imaging Vision 1 153–168.
[22] Princen, J., Illingworth, J. and Kittler, J. (1994). Hypothesis testing: A framework for analyzing and optimizing Hough transform performance. IEEE Trans. Pattern Anal. Mach. Intell. 16 329–341.
[23] Ritter, G. X. and Wilson, J. N. (1996). Handbook of Computer Vision Algorithms in Image Algebra . CRC Press, Boca Raton, FL. · Zbl 0855.68105
[24] Rousseeuw, P. J. (1984). Least median of squares regression. J. Amer. Statist. Assoc. 79 871–880. · Zbl 0547.62046 · doi:10.2307/2288718
[25] Rousseeuw, P. J. and Hubert, M. (1999). Regression depth (with discussion). J. Amer. Statist. Assoc. 94 388–433. · Zbl 1007.62060
[26] Rousseeuw, P. J. and Leroy, A. M. (1987). Robust Regression and Outlier Detection. Wiley, New York. · Zbl 0711.62030
[27] Rousseeuw, P. and Yohai, V. (1984). Robust regression by means of \(S\)-estimators. In Robust and Nonlinear Time Series Analysis . Lecture Notes in Statist. 26 256–272. Springer, New York. · Zbl 0567.62027
[28] Rudin, W. (1987). Real and Complex Analysis , 3rd. ed. McGraw-Hill, New York. · Zbl 0925.00005
[29] Stewart, C. V. (1999). Robust parameter estimation in computer vision. SIAM Rev. 41 513–537. · Zbl 0933.68144 · doi:10.1137/S0036144598345802
[30] van der Vaart, A. W. and Wellner, J. A. (1996). Weak Convergence and Empirical Processes. Springer, New York. · Zbl 0862.60002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.