Choosing Lines From Hough Lines

Question

I'm using Hough Lines to do corner detection for this image. i plan to find the intersection of the lines as the corner. This is the image.

Unfortunately, Hough return lots of lines for each line I expect

How do I tune the Hough Lines so there is only four lines each corresponds to actual line on the image?

Answer 1

OpenCVs hough transform really could use some better Non-Maximum Suppression. Without that, you get this phenomenon of duplicate lines. Unfortunately I know of no easy way to tune that, besides reimplementing your own hough transform. (Which is a valid option. Hough transform is fairly simple)

Fortunately it is easy to fix in post-processing:

For the non-probabilistic hough transform, OpenCv will return the lines in order of their confidence, with the strongest line first. So simply take the first four lines that differ strongly in either rho or theta.

• so, add the first line found by HoughLines into a new List: strong_lines
• for each line found by HoughLines:
  • test whether its rho and theta are close to any strong_line (e.g. rho is within 50 pixels and theta is within 10° of the other line)
  • if not, put it into the list of strong_lines
  • if you have found 4 strong_lines, break

Answer 2

I implemented the approach described by HugoRune and though I would share my code as an example of how I implemented this. I used a tolerance of 5 degrees and 10 pixels.

strong_lines = np.zeros([4,1,2])

minLineLength = 2
maxLineGap = 10
lines = cv2.HoughLines(edged,1,np.pi/180,10, minLineLength, maxLineGap)

n2 = 0
for n1 in range(0,len(lines)):
    for rho,theta in lines[n1]:
        if n1 == 0:
            strong_lines[n2] = lines[n1]
            n2 = n2 + 1
        else:
            if rho < 0:
               rho*=-1
               theta-=np.pi
            closeness_rho = np.isclose(rho,strong_lines[0:n2,0,0],atol = 10)
            closeness_theta = np.isclose(theta,strong_lines[0:n2,0,1],atol = np.pi/36)
            closeness = np.all([closeness_rho,closeness_theta],axis=0)
            if not any(closeness) and n2 < 4:
                strong_lines[n2] = lines[n1]
                n2 = n2 + 1

EDIT: The code was updated to reflect the comment regarding a negative rho value

Answer 3

Collect the intersection of all line

for (int i = 0; i < lines.size(); i++)
{
    for (int j = i + 1; j < lines.size(); j++)
    {       
        cv::Point2f pt = computeIntersectionOfTwoLine(lines[i], lines[j]);
        if (pt.x >= 0 && pt.y >= 0 && pt.x < image.cols && pt.y < image.rows)
        {
            corners.push_back(pt);
        }
    }
}

You can google the algorithm to find the intersection of two lines. Once you collect all the intersection points you can easily determine the min max which will give you top-left and bottom right points. From these two points you can easily get the rectangle.

Here Sorting 2d point array to find out four corners & http://opencv-code.com/tutorials/automatic-perspective-correction-for-quadrilateral-objects/ Refer these two links.

Answer 4

Here is a complete solution written in python 2.7.x using OpenCV 2.4. It is based on ideas from this thread.

Method: Detect all lines. Assume that the Hough function returns highest ranked lines first. Filter the lines to keep those that are separated by some minimum distance and/or angle.

Image of all Hough lines: https://i.ibb.co/t3JFncJ/all-lines.jpg

Filtered lines: https://i.ibb.co/yQLNxXT/filtered-lines.jpg

Code: http://codepad.org/J57oVIzs

"""
Detect the best 4 lines for a rounded rectangle.
"""

import numpy as np
import cv2

input_image = cv2.imread("image.jpg")

def drawLines(img, lines):
    """
    Draw lines on an image
    """
    for line in lines:
        for rho,theta in line:
            a = np.cos(theta)
            b = np.sin(theta)
            x0 = a*rho
            y0 = b*rho
            x1 = int(x0 + 1000*(-b))
            y1 = int(y0 + 1000*(a))
            x2 = int(x0 - 1000*(-b))
            y2 = int(y0 - 1000*(a))
            cv2.line(img, (x1,y1), (x2,y2), (0,0,255), 1)

input_image_grey = cv2.cvtColor(input_image, cv2.COLOR_BGR2GRAY)
edged = input_image_grey

rho = 1 # 1 pixel
theta = 1.0*0.017 # 1 degree
threshold = 100
lines = cv2.HoughLines(edged, rho, theta, threshold)

# Fix negative angles
num_lines = lines.shape[1]
for i in range(0, num_lines):
    line = lines[0,i,:]
    rho = line[0]
    theta = line[1]
    if rho < 0:
        rho *= -1.0
        theta -= np.pi
        line[0] = rho
        line[1] = theta

# Draw all Hough lines in red
img_with_all_lines = np.copy(input_image)
drawLines(img_with_all_lines, lines)
cv2.imshow("Hough lines", img_with_all_lines)
cv2.waitKey()
cv2.imwrite("all_lines.jpg", img_with_all_lines)

# Find 4 lines with unique rho & theta:
num_lines_to_find = 4
filtered_lines = np.zeros([1, num_lines_to_find, 2])

if lines.shape[1] < num_lines_to_find:
    print("ERROR: Not enough lines detected!")

# Save the first line
filtered_lines[0,0,:] = lines[0,0,:]
print("Line 1: rho = %.1f theta = %.3f" % (filtered_lines[0,0,0], filtered_lines[0,0,1]))
idx = 1 # Index to store the next unique line
# Initialize all rows the same
for i in range(1,num_lines_to_find):
    filtered_lines[0,i,:] = filtered_lines[0,0,:]

# Filter the lines
num_lines = lines.shape[1]
for i in range(0, num_lines):
    line = lines[0,i,:]
    rho = line[0]
    theta = line[1]

    # For this line, check which of the existing 4 it is similar to.
    closeness_rho   = np.isclose(rho,   filtered_lines[0,:,0], atol = 10.0) # 10 pixels
    closeness_theta = np.isclose(theta, filtered_lines[0,:,1], atol = np.pi/36.0) # 10 degrees

    similar_rho = np.any(closeness_rho)
    similar_theta = np.any(closeness_theta)
    similar = (similar_rho and similar_theta)

    if not similar:
        print("Found a unique line: %d rho = %.1f theta = %.3f" % (i, rho, theta))
        filtered_lines[0,idx,:] = lines[0,i,:]
        idx += 1
   
    if idx >= num_lines_to_find:
        print("Found %d unique lines!" % (num_lines_to_find))
        break

# Draw filtered lines
img_with_filtered_lines = np.copy(input_image)
drawLines(img_with_filtered_lines, filtered_lines)
cv2.imshow("Filtered lines", img_with_filtered_lines)
cv2.waitKey()
cv2.imwrite("filtered_lines.jpg", img_with_filtered_lines)

Answer 5

The above approach (proposed by @HugoRune's and implemented by @Onamission21) is correct but has a little bug. cv2.HoughLines may return negative rho and theta upto pi. Notice for example that the line (r0,0) is very close to the line (-r0,pi-epsilon) but they would not be found in the above closeness test. I simply treated negative rhos by applying rho*=-1, theta-=pi before closeness calculations.