Using OpenCV Hough Tranform for line detection in 2D point cloud

Question

I have tried my best to find out how to use OpenCV for line detection. However, I cannot find the examples that I'm looking for. I want to use it to find lines in simple 2-d point clouds. As a test I want to use the following points:

import random
import numpy as np
import matplotlib.pyplot as plt

a = np.random.randint(1,101,400)  # Random points.
b = np.random.randint(1,101,400)  # Random points.

for i in range(0, 90, 2):  # A line to detect
    a = np.append(a, [i+5])
    b = np.append(b, [0.5*i+30])

plt.plot(a, b, '.')
plt.show()

I have found a lot of initial examples of how the Hough Tranform works. However, when it comes to code examples, I can only find that images have been used.

Is there a way to use the OpenCV Hough Transform to detect the line in a set of points, or can you recommend any other methods or libraries?

---- Edit ----

After reading some great ansewers I feel like I scould discribe what i intent to use it for a little bit better. I have a high resolution 2D LiDAR and need to extract walls from the data. A typicle scan can look like this:

Where the "correct output" would look something like this:

After I have done some more research I suspect that the Hough transform is less than optimal to use in this case. Any tips on what i should look for?

(If anyone is interested, the LiDAR and wall extraction is used to generate a map and navigate a robot.)

Thanks, Jakob

Answer 1

One way would be to implement Hough Transformation yourself following these slides skipping the Edge Detection part.

Alternatively you could create an image from your list of points such as

#create an image from list of points
x_shape = int(np.max(a) - np.min(a))
y_shape = int(np.max(b) - np.min(b))

im = np.zeros((x_shape+1, y_shape+1))

indices = np.stack([a-1,b-1], axis =1).astype(int)
im[indices[:,0], indices[:,1]] = 1

plt.imshow(im)

#feed to opencv as usual

following the answer to this question

EDIT: Do not feed to OpenCV but use instead skimage such as described here in the documentation:

import numpy as np

from skimage.transform import (hough_line, hough_line_peaks,
                               probabilistic_hough_line)
from skimage.feature import canny
from skimage import data

import matplotlib.pyplot as plt
from matplotlib import cm


# Constructing test image
#image = np.zeros((100, 100))
#idx = np.arange(25, 75)
#image[idx[::-1], idx] = 255
#image[idx, idx] = 255

image = im

# Classic straight-line Hough transform
h, theta, d = hough_line(image)

# Generating figure 1
fig, axes = plt.subplots(1, 3, figsize=(15, 6))
ax = axes.ravel()

ax[0].imshow(image, cmap=cm.gray)
ax[0].set_title('Input image')
ax[0].set_axis_off()

ax[1].imshow(np.log(1 + h),
             extent=[np.rad2deg(theta[-1]), np.rad2deg(theta[0]), d[-1], d[0]],
             cmap=cm.gray, aspect=1/1.5)
ax[1].set_title('Hough transform')
ax[1].set_xlabel('Angles (degrees)')
ax[1].set_ylabel('Distance (pixels)')
ax[1].axis('image')

ax[2].imshow(image, cmap=cm.gray)
for _, angle, dist in zip(*hough_line_peaks(h, theta, d)):
    y0 = (dist - 0 * np.cos(angle)) / np.sin(angle)
    y1 = (dist - image.shape[1] * np.cos(angle)) / np.sin(angle)
    ax[2].plot((0, image.shape[1]), (y0, y1), '-r')
ax[2].set_xlim((0, image.shape[1]))
ax[2].set_ylim((image.shape[0], 0))
ax[2].set_axis_off()
ax[2].set_title('Detected lines')

plt.tight_layout()
plt.show()

# Line finding using the Probabilistic Hough Transform
image = data.camera()
edges = canny(image, 2, 1, 25)
lines = probabilistic_hough_line(edges, threshold=10, line_length=5,
                                 line_gap=3)

# Generating figure 2
fig, axes = plt.subplots(1, 3, figsize=(15, 5), sharex=True, sharey=True)
ax = axes.ravel()

ax[0].imshow(image, cmap=cm.gray)
ax[0].set_title('Input image')

ax[1].imshow(edges, cmap=cm.gray)
ax[1].set_title('Canny edges')

ax[2].imshow(edges * 0)
for line in lines:
    p0, p1 = line
    ax[2].plot((p0[0], p1[0]), (p0[1], p1[1]))
ax[2].set_xlim((0, image.shape[1]))
ax[2].set_ylim((image.shape[0], 0))
ax[2].set_title('Probabilistic Hough')

for a in ax:
    a.set_axis_off()

plt.tight_layout()
plt.show()