python - 使用 Python 检测 numpy 图像数组中重复项的最有效方法是什么？

Question

我正在尝试用 Python 检测 numpy 图像数组中的重复项和近似重复项。我正在使用来自 this assignment/tutorial 的 notMNIST(字符图像)数据.

我的方法包括检查一个数组中的每个图像与另一个数组中的每个图像是否完全匹配，但它很慢而且我不确定它是否正常工作。

数组的形状为 (num_of_images, 28, 28)。

exactOverlap = {} # using a dict because there are train, validation, and test arrays
exactOverlap['train-val'] = 0
eoIdxs = {}
eoIdxs['train-val'] = []

# check for exact matches
for img in range(train_dataset.shape[0]):
    if np.equal(valid_dataset, train_dataset[img]).any(1).all():
        exactOverlap['train-val'] += 1
        ims.append(train_dataset[img])
        eoIdxs['train-val'].append((img,
                np.where(valid_dataset == train_dataset[img])))
print(exactOverlap)

我想让“eoIdxs”成为 train_dataset 和 valid_dataset 中匹配的索引的元组。

This answer似乎有一些关于如何做到这一点的线索，我可以看到 PCA 和/或 cv2 很有用，但除了蛮力工作，我什么也没得到。

Answer 1

速度的关键是避免比较所有对，避免镜像是不够的，因为它仍然是 O(n^2)。

平等

相等的图像将具有相等的哈希值(在任何哈希函数下)，因此只有具有匹配哈希值的图像可能相等。

散列所有图像(线性时间)，并查找散列冲突，这些是您唯一的重复候选对象，但您只有在测试是否相等后才能确定。

相似

但是，如果你想尝试相似性，你必须找到一个合适的散列函数，使相似的图像发生碰撞，这些散列函数被称为Locality-sensitive。您现在可以简单地检查散列冲突，并假设它们是相似的，或者应用另一个可能更昂贵的相似性函数来比较图像。

(=

如果您现在再次查看相等性和相似性检测，它们非常相似。您通过哈希函数将候选者映射在一起，然后仅比较候选者。

复杂

如果您考虑一下，现在问题可能仍然是 O(n^2)，因为我们在所有存储桶中使用相同的全对比较。要获得线性复杂度，必须允许散列函数具有足够的类，以使每个桶的图像数量不超过恒定数量(这要求图像在每个数据集中不重复(不要太多次:P))。