# grouping/clustering of lines using Hough transform

I am new to Hough transform, though I have some basic idea about it. I am currently trying to fit the best line to a cluster of points $$\left(x_i, y_i\right), i = 1,2,\cdots , N$$, where there are many outliers, as well. The true points have very low noise. So, the main issue is to correctly identify outliers and reject them. Here is my approach to fit the best line:

1. Make accumulator matrix in Hough space of $$\left[r, \theta\right]$$, where $$r\in \left[-50 \ \ 50\right]$$ and $$\theta\in \left[-\pi/2 \ \ \pi/2\right]$$. Assume that $$r$$ is discretized in 100 values and $$\theta$$ is discretized in $$180$$ values. So, the size of accumulator matrix is $$100\times 180$$.
2. For each pair of $$\left(r_i,\theta_j\right)$$, find the number of points passing through it. Assign this number to row $$i$$ and column $$j$$ of the accumulator matrix.
3. For each value in position $$\left(i,j\right)$$, in the matrix, find if it is a local maxima. Store the row and columns of all local maxima.
4. The local maxima correspond to the prominent lines that can be created using the points in the cluster.
5. Iterate over all local maxima i.e. iterate over $$(\bar{r}_i+\Delta r, \bar{\theta}_j+\Delta \theta)$$ where $$(\bar{r}_i, \bar{\theta}_j)$$ correspond to the local maxima and $$\Delta r$$ and $$\Delta \theta$$ are the perturbations in their corresponding local maxima. Group together all $$(\bar{r}_k, \bar{\theta}_l)$$ which are part of local maxima computed in steps 3 and 4 and which lie within $$(\bar{r}_i+\Delta r, \bar{\theta}_j+\Delta \theta)$$.
6. Compute the mean of $$\bar{r}$$ and $$\bar{\theta}$$ using all the values grouped in step 5 and then perturb this value by $$\Delta r$$ and $$\Delta \theta$$ and go back to step 5. In each iteration we exclude those points which have already been grouped.
7. WE iterate only for 3 to 4 times , after which all the values which have been grouped together will be used to find an approximate line.
8. Now we start a new iteration over left-over maxima to form a new group i.e. repeat steps 5 and 6.
9. Once we have assigned a group to each maxima, we find distance between each pair of groups. We can define any robust metric for computing this distance.
10. If for a given pair the distance between clusters is within merging threshold, we repeat steps 5 to 8.
11. Once we ensure that no more groups can be merged, we fit approximate line to each group.
12. The group that has the least fitting error is the best line that can be fit in the cluster of points.

I am not sure whether this approach is correct, but there is one issue with it. a point may belong to multiple values of $$\left(r_k, \theta_l\right)$$ i.e. a point $$\left(x_i, y_j\right)$$ may belong to several $$\left(r_k, \theta_l\right)$$ and as such the points in the groups are not unique.

Is there a better way to cluster lines? I came across this paper which tries to solve similar problem. https://ieeexplore.ieee.org/document/37833

Is there any other method of better computational complexity or convergence?

• You might like to look up RANSAC. en.wikipedia.org/wiki/Random_sample_consensus Oct 16, 2022 at 11:58
• Isn't convergence one of the disadvantages of RANSAC and it seems like the method I have outlined above is a mix of RANSAC and Hough transform. Oct 16, 2022 at 21:46