Editing Hough transform (section)

=== Detection of 3D objects (planes and cylinders) ===
Hough transform can also be used for the detection of 3D objects in [[Range imaging|range data]] or 3D [[point cloud]]s. The extension of classical Hough transform for plane detection is quite straightforward. A plane is represented by its explicit equation <math>z = a_x x + a_y y + d</math> for which we can use a 3D Hough space corresponding to <math>a_x</math>, <math>a_y</math> and <math>d</math>. This extension suffers from the same problems as its 2D counterpart i.e., near horizontal planes can be reliably detected, while the performance deteriorates as planar direction becomes vertical (big values of <math>a_x</math> and <math>a_y</math> amplify the noise in the data). This formulation of the plane has been used for the detection of planes in the point clouds acquired from airborne laser scanning <ref>Vosselman, G., Dijkman, S: "[https://pdfs.semanticscholar.org/bb77/54f8e928bd79baf56a1da501484a4567d8ab.pdf 3D Building Model Reconstruction from Point Clouds and Ground Plans]", International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol 34, part 3/W4, October 22–24, 2001, Annapolis, MA, USA, pp. 37–44.</ref> and works very well because in that domain all planes are nearly horizontal.

For generalized plane detection using Hough transform, the plane can be parametrized by its normal vector <math>n</math> (using spherical coordinates) and its distance from the origin <math>\rho</math> resulting in a three dimensional Hough space. This results in each point in the input data voting for a sinusoidal surface in the Hough space. The intersection of these sinusoidal surfaces indicates presence of a plane.<ref>Tahir Rabbani: [http://www.ncg.knaw.nl/Publicaties/Geodesy/62Rabbani.html "Automatic reconstruction of industrial installations – Using point clouds and images"] {{Webarchive|url=https://web.archive.org/web/20081201052227/http://www.ncg.knaw.nl/Publicaties/Geodesy/62Rabbani.html |date=2008-12-01 }}, pages 43–44, Publications on Geodesy 62, Delft, 2006. {{ISBN|978-90-6132-297-9}}.</ref> A more general approach for more than 3 dimensions requires search heuristics to remain feasible.<ref>{{cite journal | last1 = Achtert | first1 = Elke | last2 = Böhm | first2 = Christian | last3 = David | first3 = Jörn | last4 = Kröger | first4 = Peer | last5 = Zimek | first5 = Arthur |author-link5=Arthur Zimek| year = 2008 | title = Global Correlation Clustering Based on the Hough Transform | journal = Statistical Analysis and Data Mining | volume = 1 | issue = 3| pages = 111–127 | doi = 10.1002/sam.10012 | s2cid = 5111283 | citeseerx = 10.1.1.716.6006 }}</ref>

Hough transform has also been used to find cylindrical objects in point clouds using a two step approach. The first step finds the orientation of the cylinder and the second step finds the position and radius.<ref>Tahir Rabbani and Frank van den Heuvel, "[https://pdfs.semanticscholar.org/d205/b6e6f743bc62e31257b47d18b36ada95f4f1.pdf Efficient hough transform for automatic detection of cylinders in point clouds]" in Proceedings of the 11th Annual Conference of the Advanced School for Computing and Imaging (ASCI '05), The Netherlands, June 2005.</ref>