Finding lines from a set of points (image processing)

Question

I am not sure this is the right place, but it is a math problem too so let me give it a shot. This problem comes from Robotics but can be totally extricated from there.

In brief, we have a set of points $(x,y)$ on a plane of specific dimension.. (They happen to be points where a sensor has determined there is an obstacle. In reality the obstacles are just straight walls at right angles with each other.)

We want to convert that into a list of lines which are formed by the points. Intuitively if you look at the dots on a screen it's usually quite clear where to draw the lines. Look at this image which as many points. It's sort of obvious where the line segments are (mostly.)

The algorithm we are using is a Hough transform and we admit that we are not experts in it. We've tweaked the parameters as best we can.

For the input image above it gives us 100-200 lines segments. In "reality" there are maybe 20-30.

Basically this is a function that takes a list of $(x,y)$ pairs and generates a new list of $(x_1,y_1,x_2,y_2)$ line segments.

Does anyone have experience with this or refer me somewhere else to look? Thanks!

Pito

Answer 1

With the Hough transform obtained in a python repository we obtain a good result. Here wmH1C.png is the furnished picture.

import numpy as np
from skimage.transform import hough_line, hough_line_peaks
import matplotlib.pyplot as plt
from matplotlib import cm
from PIL import Image

img = Image.open('/home/test/Desktop/wmH1C.png')
img.show()
r = img.convert('1')
r.save('/home/test/Desktop/wmH1C.bmp')

image = np.array(Image.open('/home/test/Desktop/wmH1C.bmp'))
(h, theta, d) = hough_line(image)
(fig, axes) = plt.subplots(1, 3, figsize=(15, 6), subplot_kw {'adjustable': 'box'})
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='auto')#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()

After processing