检查两个轮廓是否相交？

Question

检查两个轮廓是否相交？

7

我有两个轮廓（cont1和cont2）由cv2.findContours()接收。如何确定它们是否相交？我不需要坐标，只需要一个布尔值True或False。

我尝试了不同的方法，并已经尝试使用

if ((cont1 & cont2).area() > 0):

但是出现了错误，错误信息为数组没有"Area()"方法。

...
cont1array = cv2.findContours(binary1, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)[0]
cont2array = cv2.findContours(binary2, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)[0]
...

for cont1 in cont1array:
  for cont2 in cont2array:
    print("cont1")
    print(cont1)
    print(type(cont1))
    print("cont2")
    print(cont2)
    print(type(cont2))
>   if cont1 and cont2 intersect: #i dont know how check intersect
      print("yes they intersect")
    else:
      print("no they do not intersect")

# cont1
# [[172 302]
#  [261 301]
#  [262 390]
#  [173 391]]
# <class 'numpy.ndarray'>
# cont2
# [[  0   0]
#  [  0 699]
#  [499 699]
#  [499   0]]
# <class 'numpy.ndarray'>

- user11309903

3

你可以首先使用边界矩形作为粗略而廉价的步骤，然后再进行细化。我会在单独的掩膜图像上绘制每个轮廓的填充，并计算掩膜交集，但这可能速度太慢了。 - Micka

1

在现实世界中，两个不同的轮廓线永远不会相交（例如，请参见https://socratic.org/questions/why-do-contour-lines-never-cross-on-a-topographic-map）。在计算机的近似中，一些轮廓线可能会相交，但其有用性取决于具体情况。您能否多说一些关于您正在尝试解决的潜在问题，这可能会让人们提供更有帮助的答案？ - Simon

1

有一张儿童游戏的图片（像乐透网格）。在游戏中，他们会把筷子放在图片上（就像冰棒棍）。我需要确定哪些单元格被棍子覆盖了。cont1 是这个游戏网格所有单元格的轮廓（在它们被放到棍子上之前）。 cont2 是来自图片中所有棍子的轮廓。在代码中，我进行了一个检查：如果单元格的轮廓与棍子的轮廓相交，则该单元格被棍子封闭。因此，我需要知道如何确定两个轮廓之间是否相交的事实。 - user11309903

由于在这种情况下，每个轮廓只是一个点向量，您是否可以将它们转换为集合（例如在https://dev59.com/B3A65IYBdhLWcg3wqQg8#33067553中描述），然后找到两个点向量的交集？ - Simon

4个回答

10

一旦你从cv2.findContours()获取了两个轮廓，你可以使用按位AND操作来检测它们是否相交。具体来说，我们可以使用np.logical_and()。思路是为每个轮廓创建两个单独的图像，然后在它们上面使用逻辑AND操作。任何具有正值（1或True）的点都是相交点。因此，由于你只需要获得是否存在相交的布尔值，我们可以检查相交的图像是否有单个正值。基本上，如果整个数组为False，则表示轮廓之间没有相交。但如果有一个单独的True，那么轮廓就接触并且相交。

def contourIntersect(original_image, contour1, contour2):
    # Two separate contours trying to check intersection on
    contours = [contour1, contour2]

    # Create image filled with zeros the same size of original image
    blank = np.zeros(original_image.shape[0:2])

    # Copy each contour into its own image and fill it with '1'
    image1 = cv2.drawContours(blank.copy(), [contours[0]], 0, 1)
    image2 = cv2.drawContours(blank.copy(), [contours[1]], 1, 1)
    
    # Use the logical AND operation on the two images
    # Since the two images had bitwise and applied to it,
    # there should be a '1' or 'True' where there was intersection
    # and a '0' or 'False' where it didnt intersect
    intersection = np.logical_and(image1, image2)
    
    # Check if there was a '1' in the intersection
    return intersection.any()

示例

原始图像

检测到的轮廓

现在我们将这两个检测到的轮廓传递给该函数并获取此交集数组：

[[False False False ... False False False]
 [False False False ... False False False]
 [False False False ... False False False]
 ...
 [False False False ... False False False]
 [False False False ... False False False]
 [False False False ... False False False]]

我们检查intersection数组，看看是否存在True。当轮廓相交时，我们将获得True或1，而当它们不相交时，将获得False或0。

return intersection.any()

因此，我们得到

错误的

完整代码

import cv2
import numpy as np

def contourIntersect(original_image, contour1, contour2):
    # Two separate contours trying to check intersection on
    contours = [contour1, contour2]

    # Create image filled with zeros the same size of original image
    blank = np.zeros(original_image.shape[0:2])

    # Copy each contour into its own image and fill it with '1'
    image1 = cv2.drawContours(blank.copy(), contours, 0, 1)
    image2 = cv2.drawContours(blank.copy(), contours, 1, 1)
    
    # Use the logical AND operation on the two images
    # Since the two images had bitwise AND applied to it,
    # there should be a '1' or 'True' where there was intersection
    # and a '0' or 'False' where it didnt intersect
    intersection = np.logical_and(image1, image2)
    
    # Check if there was a '1' in the intersection array
    return intersection.any()

original_image = cv2.imread("base.png")
image = original_image.copy()

cv2.imshow("original", image)
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
cv2.imshow("gray", gray)
blurred = cv2.GaussianBlur(gray, (5,5), 0)
cv2.imshow("blur", blurred)
threshold = cv2.threshold(blurred, 60, 255, cv2.THRESH_BINARY)[1]
cv2.imshow("thresh", threshold)

contours = cv2.findContours(threshold.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
# Depending on OpenCV version, number of arguments return by cv.findContours 
# is either 2 or 3
contours = contours[1] if len(contours) == 3 else contours[0]

contour_list = []
for c in contours:
    contour_list.append(c)
    cv2.drawContours(image, [c], 0, (0,255,0), 2)

print(contourIntersect(original_image, contour_list[0], contour_list[1]))
cv2.imshow("contour", image)
cv2.waitKey(0)

- nathancy

2

你可以只需返回 True in intersection 或者更简单的 return intersection.any()。 - alkasm

谢谢，看起来它能工作，但如果一个电路位于另一个电路内部，那么我会得到一个错误。 - user11309903

1

@Ivans和@nathancys的答案是我在这里看到的最好的答案。然而，绘制线条仍然需要大量计算，特别是如果轮廓中有许多点，直接计算位与可能会影响性能，特别是如果你的画布很大。提高性能的一个简单方法是首先检查bbox交集；如果你发现bbox不相交，你就知道轮廓不相交。如果你的bbox相交，只需为两个轮廓绘制最小的填充（或轮廓）ROI，并计算一个简单的位与。我发现这比这里列出的其他技术提供了显著的加速，并防止了在大画布上出现大型复杂轮廓的问题。我使用torch计算bbox ious以简化/易读。

import cv2
import numpy as np
import torchvision.ops.boxes as bops

def contour_intersect(cnt_ref, cnt_query):
    ## Contours are both an np array of points
    ## Check for bbox intersection, then check pixel intersection if bboxes intersect

    # first check if it is possible that any of the contours intersect
    x1, y1, w1, h1 = cv2.boundingRect(cnt_ref)
    x2, y2, w2, h2 = cv2.boundingRect(cnt_query)
    # get contour areas
    area_ref = cv2.contourArea(cnt_ref)
    area_query = cv2.contourArea(cnt_query)
    # get coordinates as tensors
    box1 = torch.tensor([[x1, y1, x1 + w1, y1 + h1]], dtype=torch.float)
    box2 = torch.tensor([[x2, y2, x2 + w2, y2 + h2]], dtype=torch.float)
    # get bbox iou
    iou = bops.box_iou(box1, box2)

    if iou == 0:
        # bboxes dont intersect, so contours dont either
        return False
    else:
        # bboxes intersect, now check pixels
        # get the height, width, x, and y of the smaller contour
        if area_ref >= area_query:
            h = h2
            w = w2
            x = x2
            y = y2
        else:
            h = h1
            w = w1
            x = x1
            y = y1

        # get a canvas to draw the small contour and subspace of the large contour
        contour_canvas_ref = np.zeros((h, w), dtype='uint8')
        contour_canvas_query = np.zeros((h, w), dtype='uint8')
        # draw the pixels areas, filled (can also be outline)
        cv2.drawContours(contour_canvas_ref, [cnt_ref], -1, 255, thickness=cv2.FILLED,
                         offset=(-x, -y))
        cv2.drawContours(contour_canvas_query, [cnt_query], -1, 255, thickness=cv2.FILLED,
                         offset=(-x, -y))

        # check for any pixel overlap
        return np.any(np.bitwise_and(contour_canvas_ref, contour_canvas_query))

- Pietro Cicalese

这对我来说非常完美，计算时间非常短！谢谢。 - Samuel Thudi

0

为了处理一个轮廓包含另一个轮廓的情况，我们可以替换

image1 = cv2.drawContours(blank.copy(), contours, 0, 1)
image2 = cv2.drawContours(blank.copy(), contours, 1, 1)

用Nathancy的答案返回

image1 = cv2.fillPoly(blank.copy(), [contour1], 1)
image2 = cv2.fillPoly(blank.copy(), [contour2], 1)

- Haoyu Xu

这个解释很不清楚。 - TheCodeNovice

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ivan · Accepted Answer

nathancy的答案是有效的，但在性能方面存在问题。举例来说，它会创建3个图像副本以绘制轮廓线，因此在执行时间方面较为迟缓。

我的替代方案如下：

def contour_intersect(cnt_ref,cnt_query, edges_only = True):
    
    intersecting_pts = []
    
    ## Loop through all points in the contour
    for pt in cnt_query:
        x,y = pt[0]

        ## find point that intersect the ref contour
        ## edges_only flag check if the intersection to detect is only at the edges of the contour
        
        if edges_only and (cv2.pointPolygonTest(cnt_ref,(x,y),True) == 0):
            intersecting_pts.append(pt[0])
        elif not(edges_only) and (cv2.pointPolygonTest(cnt_ref,(x,y),True) >= 0):
            intersecting_pts.append(pt[0])
            
    if len(intersecting_pts) > 0:
        return True
    else:
        return False

编辑!!

测试发现，当轮廓中不存在两个相似的点时，此检查会失败。因此，我已重新编写了算法，用于检查两个轮廓线是否相交。

def ccw(A,B,C):
    return (C[1]-A[1]) * (B[0]-A[0]) > (B[1]-A[1]) * (C[0]-A[0])

def contour_intersect(cnt_ref,cnt_query):

    ## Contour is a list of points
    ## Connect each point to the following point to get a line
    ## If any of the lines intersect, then break

    for ref_idx in range(len(cnt_ref)-1):
    ## Create reference line_ref with point AB
        A = cnt_ref[ref_idx][0]
        B = cnt_ref[ref_idx+1][0] 
    
        for query_idx in range(len(cnt_query)-1):
            ## Create query line_query with point CD
            C = cnt_query[query_idx][0]
            D = cnt_query[query_idx+1][0]
        
            ## Check if line intersect
            if ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D):
                ## If true, break loop earlier
                return True

    return False