# Fitting plane to 3D points using Hough transform

I have a set of $N$ points in form of their $xyz$ coordinates. I am not using all of them due to high computation time. I am looking to find best plane fit to given set of points.

I used this as reference: Hugh transform on page 3, there's algorithm number 2 that interests me

I am calculating their Hough space coordinates using this formula:

$$p = x_n \cos(\theta)\sin(\phi) + y_n\sin(\phi)\sin (\theta) + z_n\cos(\phi),$$

wher $\phi \in [-90°, 90°]$, $\theta \in [0°, 360°]$.

This is where I am probably wrong:

So for each point I am calculating $180 × 360$ possible combinations of degrees in sin and cos. I defined a matrix that has $360$ rows and $180$ columns for each combination of $\phi$ and $\theta$. I increment cells in this matrix if threshold $p$ is less than $0.03$.

If this is incorrect please tell me what I am doing wrong there.

So in the end I have matrix of votes and highest numbers in matrix represents combination of $\phi$ and $\theta$ that are best solution for algorithm.

But what I need is classic plane formula:

$$Ax + By + Cz + D = 0.$$

How do I get that equation from $\phi$ and $\theta$ that I get from algorithm?

• But why? Complexity is abysmal. Why not just solve for plane's eq? – mathreadler Apr 22 '18 at 21:10
• I need to implement 3 different algorithms for plane fit. I have already used least squares and RANSAC. My final choice was Hough – Macedon Apr 22 '18 at 22:04

You need three parameters to specify a surface in 3D: two angles $\phi$ and $\theta$, and a radius $r$.
That means you need a 3-dimensional matrix, with values for $\phi$, $\theta$ as you've done, and values for $r \in [0, R]$, where $R$ is the maximal radius possible for your data.
After running the algorithm, you will get values $\phi^\ast$, $\theta^\ast$, and $r^\ast$ which correspond to the higher number of votes in your matrix.
Now you know the points on the optimal plane satisfy $r^\ast = x \cos(\theta^\ast)\sin(\phi^\ast) + y\sin(\theta^\ast)\sin(\phi^\ast) + z\cos(\phi^\ast)$.
In other words, if we set $A = \cos(\theta^\ast)\sin(\phi^\ast)$, $B = \sin(\theta^\ast)\sin(\phi^\ast)$, $C = \cos(\phi^\ast)$, and $D = -r^\ast$, your plane is parametrized by $Ax+By+Cz+D=0$.