不同长度数组之间匹配的最佳方式

Question

我有两个长度不等的排序数值数组，我正在寻找一种方法来匹配两个数组中的元素，以便（大多数）

gt

和

pred

元素之间存在一对一匹配。仅当匹配低于某个阈值

thrsh

时才被视为有效（因此可能存在不匹配的

gt

元素），并且我们将匹配的

cost

定义为匹配的

gt

和

pred

元素之间的差异.
从这里我们可以定义三种类型的匹配：

• First Match 采用每个 gt 元素的

  first

  有效匹配，如this answer所示。
• 贪婪匹配尝试匹配尽可能多的

  gt

  元素，而不考虑匹配的“成本”。
• 最小成本匹配是“成本”最小的匹配。

例如：

thrsh=3
gt = [4,8,15,16,23,42,45]
pred = [4,5,7,16,19,44]
# some matching voodoo...
# first_match = [(4,4),(8,5),(15,16),(16,19),(42,44)]  # gt23, gt45 and pred5 are unmatched
# greedy_match is the same as first_match
# min_cost_match = [(4,4),(8,7),(16,16),(45,44)]  # gt15 and pred19 now unmatched as well

我相信First Match和Greedy Match总是相同的（直到最后一个匹配对），并且如上所述，这里有一个First Match的实现。但是，我找不到实现“最小成本匹配”的方法，因为任何迭代也可能会更改先前迭代的匹配（取决于“thrsh”有多大，这可能会导致计算量很大）。

Answer 1

thrsh=3
gt = np.array([4,8,15,16,23,42,45])
pred = np.array([4,5,7,16,19,44])

table = abs(gt[:, None] - pred[None, :])

# array([[ 0,  1,  3, 12, 15, 40],
#       [ 4,  3,  1,  8, 11, 36],
#       [11, 10,  8,  1,  4, 29],
#       [12, 11,  9,  0,  3, 28],
#       [19, 18, 16,  7,  4, 21],
#       [38, 37, 35, 26, 23,  2],
#       [41, 40, 38, 29, 26,  1]])

这里很容易观察到规律。任何行方向和列方向成本最小的项目（并且也在阈值内）必须是最小成本匹配的一部分。

rowwise = np.stack([table.argmin(0), np.arange(table.shape[1])]).T
colwise = np.stack([np.arange(table.shape[0]), table.argmin(1)]).T
rc = (rowwise[:, None] == colwise).all(-1).any(1)

idxs = rowwise[rc]
out = np.stack([gt[idxs[:, 0]], pred[idxs[:, 1]]]).T

# array([[ 4,  4],
#       [ 8,  7],
#       [16, 16],
#       [45, 44]])

获得

out

后，您可以对其进行过滤以查看是否有任何匹配超过阈值。