最近邻搜索对于多个数据来说太长了

Question

首先，我有一个我传递给参数的图像，我用 OpenCV（使用 cv.findContours 方法）检索他的所有轮廓。我用我的 parseArray 方法解析这个列表，得到一个很好解析的 x,y 轮廓坐标列表 [(x1, y1), (x2, y2), ...] （这个列表的大小等于 24163 我的独角兽图像）

这是我的代码：

def parseArray(array):
    parsedArray = []
    for i in array:
        for j in i:
            parsedArray.append((j[0][0], j[0][1]))
    return parsedArray

def delItemList(index, list):
    del list[index: index + 1]

img = cv.imread(sys.argv[1])

canny = cv.Canny(img, 215, 275)
contours, hierarchies = cv.findContours(canny,cv.RETR_LIST, cv.CHAIN_APPROX_NONE)
parsedArray = parseArray(contours)

drawList = []

while (len(parsedArray) > 0):
    tmp = [(0,0)]
    tree = KDTree(parsedArray)
    dist, ind = tree.query(tmp, k=1)
    tmp[0] = parsedArray[int(ind)]
    drawList.append(parsedArray[int(ind)])
    delItemList(int(ind), parsedArray)

这里有一个 time :

我怎样才能大大减少我的循环时间（少于一秒），这可能吗？

Answer 1

我认为您大部分时间都花在了 while 循环中，所以我将重点关注这些行：

while (len(parsedArray) > 0):
    tmp = [(0,0)]
    tree = KDTree(parsedArray)
    dist, ind = tree.query(tmp, k=1)
    tmp[0] = parsedArray[int(ind)]
    drawList.append(parsedArray[int(ind)])
    delItemList(int(ind), parsedArray)

我的理解是，您想使用 KDTree 在轮廓点中找到点 [(0,0]] 最近的邻居，一旦找到，就将其从轮廓点中删除并重新开始。这是昂贵的，因为您正在创建一个复杂的结构，该结构经过优化以仅对一个查询执行最近邻查询，然后您一次又一次地创建它。我可以建议你两个优化：

如果你出于任何原因想要保留KDTree，那么一次查询所有点：tree.query(tmp, k=len(parsedArray)) (c.f.scipy documentation)
计算 [(0, 0)] 和等高线每个点之间的距离，并按此距离对它们进行排序。您可以在其他线程上找到解决方案，例如

最近邻搜索对于多个数据来说太长了

Nearest Neighbor Search is too long for multiple datas

python

opencv

kdtree

turtle-graphics