Approximate a group of line segments as a single best fit straight line

Question

Assuming I have a group of lines segments like the red lines (or green lines) in this picture

I want to know how can I replace them with just one line segment that approximates them best. Or maybe you can advise what to search for since this might be a common problem in statistics.

Problem background: This comes actually from using OpenCV's probabilistic Hough Transform. I want to detect the corners of a piece of paper. When I apply it to an image I get on the edges a group of lines that I want to convert to a single line continuous segment.

One way to do it that I was thinking of, is to take from the line a couple of points and then to use line regression to get the equation of the line. Once I have that I should just cut it to a segment.

Answer 1

Here's a potential solution:

1. Obtain binary image. Load image, convert to grayscale, and Otsu's threshold

2. Perform morphological operations. We morph close to combine the contours into a single contour

3. Find convex hull. We create a blank mask then find the convex hull on the binary image. We draw the lines onto the mask, morph close, then find contours and fill in the outline to get a solid image

4. Perform linear regression. We find the line of best fit on the binary image then draw this resulting line onto a new mask

5. Bitwise convex hull and line mask together. We bitwise-and both masks together and draw this resulting contour onto the original image.

---

Here's a visualization of each step:

Using this screenshotted input image

Binary image -> Morph close

# Load image, grayscale, Otsu's threshold
image = cv2.imread('1.png')
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)[1]

# Morph close
kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (5,5))
close = cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, kernel, iterations=3)

Convex hull outline -> convex hull filled

# Create line mask and convex hull mask
line_mask = np.zeros(image.shape, dtype=np.uint8)
convex_mask = np.zeros(image.shape, dtype=np.uint8)

# Find convex hull on the binary image
cnts = cv2.findContours(close, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
cnt = cnts[0]
hull = cv2.convexHull(cnt,returnPoints = False)
defects = cv2.convexityDefects(cnt,hull)
for i in range(defects.shape[0]):
    s,e,f,d = defects[i,0]
    start = tuple(cnt[s][0])
    end = tuple(cnt[e][0])
    far = tuple(cnt[f][0])
    cv2.line(convex_mask,start,end,[255,255,255],5)

# Morph close the convex hull mask, find contours, and fill in the outline
convex_mask = cv2.cvtColor(convex_mask, cv2.COLOR_BGR2GRAY)
kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (5,5))
convex_mask = cv2.morphologyEx(convex_mask, cv2.MORPH_CLOSE, kernel, iterations=3)
cnts = cv2.findContours(convex_mask, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
cv2.fillPoly(convex_mask, cnts, (255,255,255))

Linear regression

# Perform linear regression on the binary image
[vx,vy,x,y] = cv2.fitLine(cnt,cv2.DIST_L2,0,0.01,0.01)
lefty = int((-x*vy/vx) + y)
righty = int(((image.shape[1]-x)*vy/vx)+y)
cv2.line(line_mask,(image.shape[1]-1,righty),(0,lefty),[255,255,255],2)

Bitwise-and filled convex hull and linear regression masks together

# Bitwise-and the line and convex hull masks together
result = cv2.bitwise_and(line_mask, line_mask, mask=convex_mask)
result = cv2.cvtColor(result, cv2.COLOR_BGR2GRAY)

Result

# Find resulting contour and draw onto original image
cnts = cv2.findContours(result, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
cv2.drawContours(image, cnts, -1, (200,100,100), 3)

Here's the result with the other input image

Full code

import cv2
import numpy as np

# Load image, grayscale, Otsu's threshold
image = cv2.imread('1.png')
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)[1]

# Morph close
kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (5,5))
close = cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, kernel, iterations=3)

# Create line mask and convex hull mask
line_mask = np.zeros(image.shape, dtype=np.uint8)
convex_mask = np.zeros(image.shape, dtype=np.uint8)

# Find convex hull on the binary image
cnts = cv2.findContours(close, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
cnt = cnts[0]
hull = cv2.convexHull(cnt,returnPoints = False)
defects = cv2.convexityDefects(cnt,hull)
for i in range(defects.shape[0]):
    s,e,f,d = defects[i,0]
    start = tuple(cnt[s][0])
    end = tuple(cnt[e][0])
    far = tuple(cnt[f][0])
    cv2.line(convex_mask,start,end,[255,255,255],5)

# Morph close the convex hull mask, find contours, and fill in the outline
convex_mask = cv2.cvtColor(convex_mask, cv2.COLOR_BGR2GRAY)
kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (5,5))
convex_mask = cv2.morphologyEx(convex_mask, cv2.MORPH_CLOSE, kernel, iterations=3)
cnts = cv2.findContours(convex_mask, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
cv2.fillPoly(convex_mask, cnts, (255,255,255))

# Perform linear regression on the binary image
[vx,vy,x,y] = cv2.fitLine(cnt,cv2.DIST_L2,0,0.01,0.01)
lefty = int((-x*vy/vx) + y)
righty = int(((image.shape[1]-x)*vy/vx)+y)
cv2.line(line_mask,(image.shape[1]-1,righty),(0,lefty),[255,255,255],2)

# Bitwise-and the line and convex hull masks together
result = cv2.bitwise_and(line_mask, line_mask, mask=convex_mask)
result = cv2.cvtColor(result, cv2.COLOR_BGR2GRAY)

# Find resulting contour and draw onto original image
cnts = cv2.findContours(result, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
cv2.drawContours(image, cnts, -1, (200,100,100), 3)

cv2.imshow('thresh', thresh)
cv2.imshow('close', close)
cv2.imshow('image', image)
cv2.imshow('line_mask', line_mask)
cv2.imshow('convex_mask', convex_mask)
cv2.imshow('result', result)
cv2.waitKey()