如何在 OpenCV 中找到两个轮廓之间的最近点

Question

对于两个轮廓c1和c2，如何找到轮廓之间最近的点。

一个解决方案可能是遍历所有点，获得欧几里得距离并使用最小欧几里得距离，但这将具有巨大的时间复杂度。

我已经用cv2.findContours找到轮廓了。

contours, _ = cv2.findContours(img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

我想找到两个轮廓之间蓝色显示的两个点。

Answer 1

由于问题中没有测试数据，因此无法测试，但这应该可以让你继续。使用 KDTrees.

from scipy.spatial import KDTree

max_distance = 10 #tune to your data

kd_trees = [KDTree(c) for c in contours]
out = {}
for i, j in zip(np.triu_indices((len(contours),)*2, 1)):
    coo = kd_trees[i].sparse_distance_matrix(kd_trees[j], 
                                             max_distance = max_distance,
                                             output_type = 'coo_matrix')
    ix = np.argmin(coo.data)
    out[(i, j)] = [contours[i][coo.row[ix]], contours[j][coo.col[ix]]]

Answer 2

使用双 for 循环可能很耗时。根据 Giovanni Tardini 的评论和 an answer from CodeReview.stackexchange，您可以只遍历单个轮廓的点。我没有做过速度对比，但是原作者说向量化可以加速计算。

代码：

# To draw the final result
img = cv2.imread('image_path', 1)

# grayscale to binary conversion -> find contours
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
th = cv2.threshold(gray,127,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)[1]
contours, hierarchy = cv2.findContours(th, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# store the 2 contours
c1, c2 = contours[0], contours[1]

# Function to index and distance of the point closest to an array of points
# borrowed shamelessly from: https://codereview.stackexchange.com/questions/28207/finding-the-closest-point-to-a-list-of-points
def closest_point(point, array):
     diff = array - point
     distance = np.einsum('ij,ij->i', diff, diff)
     return np.argmin(distance), distance

# initialize some variables
min_dist = np.max(th.shape)
chosen_point_c2 = None
chosen_point_c1 = None

# iterate through each point in contour c1
for point in c1:
    t = point[0][0], point[0][1]
    index, dist = closest_point(t, c2[:,0])
    if dist[index] < min_dist :
        min_dist = dist[index]
        chosen_point_c2 = c2[index]
        chosen_point_c1 = t     

# draw the two points and save
cv2.circle(img,(chosen_point_c1), 4, (0,255,255), -1)
cv2.circle(img,tuple(chosen_point_c2[0]), 4, (0,255,255), -1)
cv2.imshow('Result', img)

结果：

（我用的是题中分享的图片，仔细看，每条轮廓上都有一个黄点。）

提供了其他解决方案，其中 KDtrees（由 Daniel F 提出）是一个选项。

如何在 OpenCV 中找到两个轮廓之间的最近点

How to find nearest points between two contours in OpenCV

python

geometry

opencv

numpy