Robust orthogonal linear regression on histogram in small-dimensional spaces

© 2017 E. N. Asvatov, E. I. Ershov, D. P. Nikolaev

Institute for Information Transmission Problems RAS 127051 Moscow, Bolshoi Karetny lane, 19

Received 14 Jul 2017

The article deals with the problem of orthogonal robust linear regression on histograms. It is proved that the evaluation of the M-estimate is equivalent in the given problem with the search for the maximum of a certain convolution and Radon transform of the original histogram. Next, we consider the discretization of the Radon space and its effect on the accuracy of calculating the M-estimate using the Hough transform (HT). Computational experiments have been carried out to analyze the change in the calculation accuracy of the M-estimate in the transition from HT to the fast Hough transform. The question’s essence is how strongly the type of the pattern approximating the line affects the accuracy of calculating the M-estimate. An experimental comparison of the proposed and classical methods realizing the solution of the orthogonal linear regression problem is carried out for the case of two-dimensional and three-dimensional histograms.

Key words: M-estimation, Radon transform, fast Hough transform, linear regression, orthogonal regression, robustness

Cite: Asvatov E. N., Ershov E. I., Nikolaev D. P.. Robastnaya ortogonalnaya lineinaya regressiya dlya malomernykh gistogramm [Robust orthogonal linear regression on histogram in small-dimensional spaces]. Sensornye sistemy [Sensory systems]. 2017. V. 31(4). P. 331-342 (in Russian).


  • Bezmaternyh P., Khanipov T., Nikolaev D. Reshenie zadachi linejnoj regressii s pomoshch’yu bystrogo preobrazovaniya Hafa // Informacionnye tekhnologii i sistemy. 2012. P. 354–359 [in Russian]
  • Gel’fand I.M., Gindikin S.G., Graev M.I. Izbrannye zadachi integral’noj geometrii. M.: Dobrosvet, 2000
  • Karpenko S., Nikolaev D., Nikolayev P., Postnikov V. Fast Hough transform with controllable robustness // Proc. IEEE AIS’04 CAD. 2004. P. 303–309 [in Russian]
  • Lagutin M.B. Naglyadnaya matematicheskaya statistika. M.: Binom. Laboratoriya Znan , 2013.
  • Ballard D.H. Generalizing the Hough transform to detect arbitrary shapes // Pattern recogn. 1981. V. 13 (2). P. 111–122.
  • Ballester P. Hough transform for robust regression and automated detection // Astron. Astrophys. 1994. V. 286. P. 1011–1018.
  • Brady M.L., Yong W. Fast parallel discrete approximation algorithms for the Radon transform // Proc. 4th annual ACM symp. Parallel algorithms and architect. 1992. P. 91–99.
  • Ershov E., Terekhin A., Karpenko S., Nikolaev D., Postnikov V. Fast 3D Hough Transform Computation // 30th Europ. Conf. Model. Simulat. 2016. P. 534–538.
  • Ershov E.I., Terekhin A.P., Nikolaev D.P., Postnikov V.V., Karpenko S.M. Fast Hough transform analysis: pattern deviation from line segment // 8th Int. Conf. Machine Vision. 2015. 987509I P. 1–5.
  • Frederick M.T., VanderHorn N.A., Somani A.K. Real-time h/w implementation of the approximate discrete Radon transform. // 16th IEEE Int. Conf. Applicat.-Speci c Syst. Architect. Processors. 2005. P. 399–404.
  • Goldenshluger A., Zeevi A. The Hough transform estimator // Annals Statist., 2004. V. 32. P. 1908–1932.
  • Götz W.A. Eine schnelle diskrete Radon transformation basierend auf rekursiv de niertern digitalen geraden. Dissertation. University of Insbruck. 1993.
  • Götz A.A., Druckmüller H.J. A fast digital Radon transform – an e cient means for evaluating the Hough transform // Pattern Recogn. 1995. V. 28 (12). P. 1985–1992.
  • Guil N., Zapata E.L. Lower order circle and ellipse hough transform // Pattern Recogn. 1997. V. 30(10). P. 1729–1744.
  • Hough P.V.C. Machine analysis of bubble chamber pictures // Int. Conf. High Energy Accelerat. Instrument. 1959. V. 73. P. 2.
  • Hough P.V.C., Arbor A. Method and means for recognizing complex patterns. 1962. US Patent 3069654.
  • Huber P.J. Robust statistics. Berlin Heidelberg. Springer. 2011.
  • Hartley R., Aftab K. Convergence of iteratively re-weighted least squares to robust m-estimators. IEEE Conf. Applicat. Comp. Vision. 2015. P. 480–487.
  • Kummell C.H. Reduction of observation equations which contain more than one observed quantity // The Analyst. 1879. P. 97–105.
  • Leroy A.M., Rousseeuw P.J. Robust Regression and Outlier Detection. New York. Wiley. 2003.
  • Markovsky I., Van Hu el S. Overview of total least-squares methods // Signal process. 2007. V. 87(10). P. 2283–2302.
  • Mukhopadhyay P., Chaudhuri B.B. A survey of Hough transform // Pattern Recogn. 2015. V. 48(3). P. 993–1010.
  • Nikolaev D., Karpenko S., Nikolaev I., Nikolayev P. Hough transform: underestimated tool in the computer vision eld // Proc. 22th Europ. Conf. Model. Simulat. 2008. P. 238–246.
  • Pfeil W.A. Statistical Teaching Aids. PhD thesis. Worcester Polytechnic Institute. 2006.
  • Siegel A.F. Robust regression using repeated medians // Biometrika. 1982. V. 69(1). P. 242–244.
  • Vandame B. Fast Hough transform for robust detection of satellite tracks // Mining the Sky. 2001. P. 595–597.
  • Van Ginkel M., Hendriks C.L., Van Vliet L.J. A short introduction to the Radon and Hough transforms and how they relate to each other. TU Delft. 2004.
  • Vuillemin J.E. Fast linear Hough transform // Proc. Int. Conf. Application Specific Array Processors. 1994. P. 1–9.
  • Wentzel P.D., Van Hu el S., Schuermans M., Markovsky I. On the equivalence between total least squares and maximum likelihood PCA // Analytica Chimica Acta. 2005. V. 544 (1). P. 254–267.