使用HoughLines OpenCV找到两条直线的交点

42

我该如何使用OpenCV的Hough线算法找到线段的交点?

以下是我的代码:

import cv2
import numpy as np
import imutils

im = cv2.imread('../data/test1.jpg')
gray = cv2.cvtColor(im,cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray, 60, 150, apertureSize=3)

img = im.copy()
lines = cv2.HoughLines(edges,1,np.pi/180,200)

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 + 3000*(-b))
        y1 = int(y0 + 3000*(a))
        x2 = int(x0 - 3000*(-b))
        y2 = int(y0 - 3000*(a))
        cv2.line(img,(x1,y1),(x2,y2),(0,255,0),10)

cv2.imshow('houghlines',imutils.resize(img, height=650))
cv2.waitKey(0)
cv2.destroyAllWindows()

输出:

Output

我想获得所有交点。

6个回答

71

你只需要获取垂直线与水平线的交点,而不是平行线的交点。此外,由于存在垂直线,计算斜率可能会导致无穷大或溢出的斜率,因此不应使用 y = mx+b 方程。您需要完成两个步骤:

  1. 根据它们的角度将线段分为两类。
  2. 计算一个类中每条线与其他类中的线的交点。

使用 HoughLines 方法后,您已经得到了结果 rho,theta,因此您可以使用 theta 将其轻松地分成两个角度类别。您可以使用例如 cv2.kmeans(),以 theta 作为要拆分的数据。

然后,要计算交点,您可以使用 给定每条线两个点的公式。您已经在每条线中计算了两个点:(x1,y1),(x2,y2),因此您可以简单地存储这些值并使用它们。编辑:实际上,如下所示的代码中,有一个公式可用于计算具有 HoughLines 给出的 rho,theta 形式的线的交点。

我之前回答过一个类似的问题,并提供了一些 Python 代码供您参考;请注意,当时使用的是仅提供线段的 HoughLinesP


代码示例

由于您没有提供原始图像,因此我不能使用它。取而代之的是,我将使用OpenCV在其Hough变换和二值化教程中使用的标准数独图像:

数独图像

首先,我们只需读取此图像并使用自适应阈值二值化,就像在这个OpenCV教程中使用的那样:

import cv2
import numpy as np

img = cv2.imread('sudoku.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
blur = cv2.medianBlur(gray, 5)
adapt_type = cv2.ADAPTIVE_THRESH_GAUSSIAN_C
thresh_type = cv2.THRESH_BINARY_INV
bin_img = cv2.adaptiveThreshold(blur, 255, adapt_type, thresh_type, 11, 2)

数独图像二值化

接下来,我们将使用cv2.HoughLines()函数查找霍夫线:

rho, theta, thresh = 2, np.pi/180, 400
lines = cv2.HoughLines(bin_img, rho, theta, thresh)

带有Hough线的数独图像

如果我们想要找出交汇点,实际上我们仅需要寻找垂直线的交汇点。我们不需要大部分平行线的交汇点。因此,我们需要对线进行分割。在这个特定的例子中,您可以根据一个简单的测试轻松地检查线是否为水平或垂直线;垂直线的 theta 大约为 0 或大约为 180;水平线的 theta 大约为 90。但是,如果您想要基于任意数量的角度进行自动分割,而无需定义这些角度,我认为最好的办法是使用 cv2.kmeans()

有一件棘手的事情需要正确处理。HoughLines 返回以 rho, theta 形式(Hesse normal form)的线,返回的 theta 在 0 到 180 度之间,并且大约在 180 和 0 度之间的线是相似的(它们都接近水平线),因此我们需要一些方法在 kmeans 中获得这种周期性。

如果我们在单位圆上绘制角度,但将角度乘以 2,则最初大约在 180 度左右的角度将变得接近 360 度,因此它们将在单位圆上具有靠近 0 度的 x, y 值。因此,我们可以通过在单位圆上用坐标绘制 2*angle 来获得一些良好的“接近度”。然后,我们可以在这些点上运行 cv2.kmeans(),并使用任意数量的分割片段进行自动分割。

因此,让我们建立一个函数来进行分割:

from collections import defaultdict
def segment_by_angle_kmeans(lines, k=2, **kwargs):
    """Groups lines based on angle with k-means.

    Uses k-means on the coordinates of the angle on the unit circle 
    to segment `k` angles inside `lines`.
    """

    # Define criteria = (type, max_iter, epsilon)
    default_criteria_type = cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER
    criteria = kwargs.get('criteria', (default_criteria_type, 10, 1.0))
    flags = kwargs.get('flags', cv2.KMEANS_RANDOM_CENTERS)
    attempts = kwargs.get('attempts', 10)

    # returns angles in [0, pi] in radians
    angles = np.array([line[0][1] for line in lines])
    # multiply the angles by two and find coordinates of that angle
    pts = np.array([[np.cos(2*angle), np.sin(2*angle)]
                    for angle in angles], dtype=np.float32)

    # run kmeans on the coords
    labels, centers = cv2.kmeans(pts, k, None, criteria, attempts, flags)[1:]
    labels = labels.reshape(-1)  # transpose to row vec

    # segment lines based on their kmeans label
    segmented = defaultdict(list)
    for i, line in enumerate(lines):
        segmented[labels[i]].append(line)
    segmented = list(segmented.values())
    return segmented

现在我们可以简单调用它来使用:

segmented = segment_by_angle_kmeans(lines)

这里好的一点是我们可以通过指定可选参数k来指定任意数量的组(默认情况下,k = 2,所以我没有在这里指定它)。

如果我们用不同的颜色绘制每个组的线:

Segmented lines

现在要做的就是找到第一组中每条线与第二组中每条线相交的位置。由于这些线处于Hesse标准形式中,有一个很好的线性代数公式可以用于计算从这种形式定义的线的交点。请参见这里。让我们在这里创建两个函数; 一个仅查找两条线的交点,另一个函数循环遍历组中的所有线,并为两条线使用该简化函数:

def intersection(line1, line2):
    """Finds the intersection of two lines given in Hesse normal form.

    Returns closest integer pixel locations.
    See https://dev59.com/IHRC5IYBdhLWcg3wMd9S#383527
    """
    rho1, theta1 = line1[0]
    rho2, theta2 = line2[0]
    A = np.array([
        [np.cos(theta1), np.sin(theta1)],
        [np.cos(theta2), np.sin(theta2)]
    ])
    b = np.array([[rho1], [rho2]])
    x0, y0 = np.linalg.solve(A, b)
    x0, y0 = int(np.round(x0)), int(np.round(y0))
    return [[x0, y0]]


def segmented_intersections(lines):
    """Finds the intersections between groups of lines."""

    intersections = []
    for i, group in enumerate(lines[:-1]):
        for next_group in lines[i+1:]:
            for line1 in group:
                for line2 in next_group:
                    intersections.append(intersection(line1, line2)) 

    return intersections

然后使用它,只需要:

intersections = segmented_intersections(segmented)

将所有交点绘制出来,我们可以得到:

Intersections


如上所述,这段代码还可以将线段分成多于两组的角度。这里展示了对一个手绘的三角形进行检测,并计算检测到的线段与k=3时的交点:

Triangle intersections


1
请注意,OpenCV 2.4x中的HoughLines返回类型似乎与基于3.2的上述内容不同。因此,需要进行一些修改才能在2.4中正常工作,但确实可以使用。 - orangepips
1
@orangepips 如果您愿意的话,我希望您能在我的 GH 存储库上开一个问题,其中实现了这段代码,并描述不同版本之间返回的不同形式。我可以更新工具以及此答案,以适应其他遇到相同问题的人:https://github.com/alkasm/houghtool/tree/master/houghtool (另外,您可以在问题中包含您所做的修复,我可以查看它 :D) - alkasm
1
这很美。谢谢。 - Hunan Rostomyan
1
嗨@orangepips,有新代码吗?我正在尝试让它工作。 - mattsmith5
2
@mattsmith5 你具体遇到了什么问题?使用Python 3.9.1和OpenCV 4.5.1,给定的代码可以直接运行。你有没有注意到orangepips说过,所提供的答案使用的是OpenCV 3.2(!),而在OpenCV 2.4(!)中使用所提供的代码需要进行一些“黑客”操作? - HansHirse
显示剩余7条评论

5

这里有一个更为直接的解决方案,可以适应这个答案。它应该比Bhupen的答案更具数值稳定性。

首先,您应该将线路分组,以便不会尝试找到平行线的交点,如其他答案所述(否则,您将得到不一致的结果和/或计算错误)。

然后,您可以使用以下方法查找一对线的交点:

def hough_inter(theta1, rho1, theta2, rho2):
    A = np.array([[cos(theta1), sin(theta1)], 
                  [cos(theta2), sin(theta2)]])
    b = np.array([rho1, rho2])
    return np.linalg.lstsq(A, b)[0] # use lstsq to solve Ax = b, not inv() which is unstable

我的数据结果:

线条 交点

说明:

在霍夫变换(rho/theta)空间中的直线会在x-y平面中被表示为这样:

rho = x cosθ + y sinθ

因此,交点(x,y)必然解决:
x cos θ1 + y sin θ1 = r1
x cos θ2 + y sin θ2 = r2

即 AX = b,其中

A = [cos θ1  sin θ1]   b = |r1|   X = |x|
    [cos θ2  sin θ2]       |r2|       |y|

因此,如果你在Python中有两条线,你可以像这样找到它们的交点。

5
如果您已经有了线段,只需将它们替换成一条直线的方程即可...
x = x1 + u * (x2-x1)
y = y1 + u * (y2-y1)

您可以使用以下任何方法找到"u"...

u = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1))
u = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1))

3
首先,您需要精炼Hough变换的输出(我通常通过基于某些标准,例如线段的斜率和/或质心等使用k-means聚类来实现这一点)。在您的问题中,似乎所有线的斜率通常接近0、180、90度左右,因此可以在此基础上进行聚类。
其次,有两种不同的方法可以获得交点(从技术上讲它们是相同的):
1. Bhupen答案中的方程式。 2. 使用几何库(如ShapelySymPy)。使用几何库的好处是,您可以访问以后可能需要的各种工具(交集、插值、凸包等等)。
附言:Shapely是一个强大的C++几何库的包装器,但SymPy是纯Python。如果您的应用程序时间关键,则可能需要考虑这一点。

2
以下是使用OpenCV 2.4和Python 2.7.x编写的完整解决方案。
该解决方案使用了来自本主题中不完整的alkasm解决方案。此外,从OpenCV 2.x到3.x,HoughLines()的返回值和kmeans()的语法也发生了变化。 结果1:桌子上的一张纸 https://i.ibb.co/VBSY7V7/paper-on-desk-intersection-points.jpg 这个回答了原问题,但是使用k = 2,3,4的k-means聚类不能分割这张纸。你需要另一种方法来找到纸的角落,例如过滤平行线。 enter image description here 结果2:数独网格 https://i.ibb.co/b6thfgr/sudoku-intersection-points.jpg enter image description here 代码:https://pastiebin.com/5f36425b7ae3d
"""
Find the intersection points of lines.
"""

import numpy as np
import cv2
from collections import defaultdict
import sys


img = cv2.imread("paper_on_desk.jpg")
#img = cv2.imread("sudoku.jpg")


def segment_by_angle_kmeans(lines, k=2, **kwargs):
    """
    Group lines by their angle using k-means clustering.

    Code from here:
    https://dev59.com/Q1YN5IYBdhLWcg3w-sp-#46572063
    """

    # Define criteria = (type, max_iter, epsilon)
    default_criteria_type = cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER
    criteria = kwargs.get('criteria', (default_criteria_type, 10, 1.0))

    flags = kwargs.get('flags', cv2.KMEANS_RANDOM_CENTERS)
    attempts = kwargs.get('attempts', 10)

    # Get angles in [0, pi] radians
    angles = np.array([line[0][1] for line in lines])

    # Multiply the angles by two and find coordinates of that angle on the Unit Circle
    pts = np.array([[np.cos(2*angle), np.sin(2*angle)] for angle in angles], dtype=np.float32)

    # Run k-means
    if sys.version_info[0] == 2:
        # python 2.x
        ret, labels, centers = cv2.kmeans(pts, k, criteria, attempts, flags)
    else: 
        # python 3.x, syntax has changed.
        labels, centers = cv2.kmeans(pts, k, None, criteria, attempts, flags)[1:]

    labels = labels.reshape(-1) # Transpose to row vector

    # Segment lines based on their label of 0 or 1
    segmented = defaultdict(list)
    for i, line in zip(range(len(lines)), lines):
        segmented[labels[i]].append(line)

    segmented = list(segmented.values())
    print("Segmented lines into two groups: %d, %d" % (len(segmented[0]), len(segmented[1])))

    return segmented


def intersection(line1, line2):
    """
    Find the intersection of two lines 
    specified in Hesse normal form.

    Returns closest integer pixel locations.

    See here:
    https://dev59.com/IHRC5IYBdhLWcg3wMd9S#383527
    """

    rho1, theta1 = line1[0]
    rho2, theta2 = line2[0]
    A = np.array([[np.cos(theta1), np.sin(theta1)],
                  [np.cos(theta2), np.sin(theta2)]])
    b = np.array([[rho1], [rho2]])
    x0, y0 = np.linalg.solve(A, b)
    x0, y0 = int(np.round(x0)), int(np.round(y0))

    return [[x0, y0]]


def segmented_intersections(lines):
    """
    Find the intersection between groups of lines.
    """

    intersections = []
    for i, group in enumerate(lines[:-1]):
        for next_group in lines[i+1:]:
            for line1 in group:
                for line2 in next_group:
                    intersections.append(intersection(line1, line2)) 

    return intersections


def drawLines(img, lines, color=(0,0,255)):
    """
    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), color, 1)


gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

blur = cv2.medianBlur(gray, 5)

# Make binary image
adapt_type = cv2.ADAPTIVE_THRESH_GAUSSIAN_C
thresh_type = cv2.THRESH_BINARY_INV
bin_img = cv2.adaptiveThreshold(blur, 255, adapt_type, thresh_type, 11, 2)
cv2.imshow("binary", bin_img)
cv2.waitKey()

# Detect lines
rho = 2
theta = np.pi/180
thresh = 350
lines = cv2.HoughLines(bin_img, rho, theta, thresh)

if sys.version_info[0] == 2:
    # python 2.x
    # Re-shape from 1xNx2 to Nx1x2
    temp_lines = []
    N = lines.shape[1]
    for i in range(N):
        rho = lines[0,i,0]
        theta = lines[0,i,1]
        temp_lines.append( np.array([[rho,theta]]) )
    lines = temp_lines

print("Found lines: %d" % (len(lines)))

# Draw all Hough lines in red
img_with_all_lines = np.copy(img)
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)

# Cluster line angles into 2 groups (vertical and horizontal)
segmented = segment_by_angle_kmeans(lines, 2)

# Find the intersections of each vertical line with each horizontal line
intersections = segmented_intersections(segmented)

img_with_segmented_lines = np.copy(img)

# Draw vertical lines in green
vertical_lines = segmented[1]
img_with_vertical_lines = np.copy(img)
drawLines(img_with_segmented_lines, vertical_lines, (0,255,0))

# Draw horizontal lines in yellow
horizontal_lines = segmented[0]
img_with_horizontal_lines = np.copy(img)
drawLines(img_with_segmented_lines, horizontal_lines, (0,255,255))

# Draw intersection points in magenta
for point in intersections:
    pt = (point[0][0], point[0][1])
    length = 5
    cv2.line(img_with_segmented_lines, (pt[0], pt[1]-length), (pt[0], pt[1]+length), (255, 0, 255), 1) # vertical line
    cv2.line(img_with_segmented_lines, (pt[0]-length, pt[1]), (pt[0]+length, pt[1]), (255, 0, 255), 1)

cv2.imshow("Segmented lines", img_with_segmented_lines)
cv2.waitKey()
cv2.imwrite("intersection_points.jpg", img_with_segmented_lines)

0

这里我使用了一些方法处理了我的图像;

1.Grayscale

2.无论是位运算还是边缘检测,都取决于图像吧,这里我选择了位运算。首先将所有检测到的线路放入一个列表中。

listOflines = cv2.HoughLines(mask_inv,1,np.pi/180,200)

我们将获取'rho'和'theta'的值, 我在这里创建了两个空列表,一个用于垂直线,一个用于水平线,并将两条线的值附加到各自的列表中。
rowsValue = []
columnValue = []

这是用于垂直和水平线的逻辑。

for line in listOflines:
if line[0][1] == 0:
    columnValue.append(line[0][0])
else:
    rowsValue.append(line[0][0])

现在重要的部分在这里, 当每条穿过并相互交叉的线都在特定像素值上与该线相交时。 我们用'rho'来表示那个像素值。
现在让我们创建元组,以(x,y)的形式传递给'cv2'函数。
tupsList = [(r,c) for r in rowsValue for c in columnValue]
for tups in tupsList:
     cv2.circle(image, tups, 1,(0,0,255), 2)
cv2.imshow('image',image)
cv2.waitKey(0)
cv2.destroyAllWindows()

就是这样!! 现在是之前和之后的图片。

原始图片

交集图片


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接