python - 在满足条件的情况下找到与另一个像素相关的最近像素的最快方法。 OpenCV NumPy

Question

我正在寻找读取图像、指定像素并在给定条件的情况下找到距离该像素最近的像素的最快方法。

我最初有一个嵌套循环，它会遍历我的 2D 图像数组中的每个像素，检查条件，然后将其添加到新数组。比遍历新数组并对每个成员进行距离计算。 那太慢了，我相信时间复杂度为 n^2。

我现在正在计算距离，并以此对数组进行排序，这在使用 numpy 时非常快。但是我仍然必须通过嵌套循环遍历 2D 排序数组来检查条件，这又是 n^2 的时间复杂度。它确实节省了一些时间，因为我通常可以在阵列中更快地找到我正在寻找的像素。

img2=cv2.imread(filename)
distances = numpy.sqrt((img2[:,:] - currR) ** 2 + (img2[:,:] - currC) ** 2)
nearest = numpy.sort(distances)
for row in range(nearest.shape[0]):
    for col in range(nearest.shape[1]):
        if pixelInLine[row*imgCol + col] == 0  and colorCheck(row,col) and numpy.any(img2[row, col] != 0):
            #do my calculations on the specified pixel. and break the loop

我不确定如何进一步优化它，并可能将时间复杂度从 n^2 降低到更合理的水平。

Answer 1

远离目标像素，一旦满足“条件”就停止。为方便起见，您可以使用正方形螺旋(实际上是嵌套正方形)。

如果距离是欧氏距离，则搜索成本将在 2d² 和 4d² 之间，其中 d 是到命中点的距离。