通过相似关系过滤图像列表

Question

我有一个图像名称列表和一个（阈值）相似度矩阵。相似关系是自反的和对称的，但不是必需的传递，即，如果image_i与image_j和image_k类似，则不必表示image_j和image_k类似。

例如：

images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']

sm = np.array([[1, 1, 1, 0, 1],
               [1, 1, 0, 0, 1],
               [1, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [1, 1, 0, 0, 1]])

相似度矩阵sm的解释如下：如果sm[i, j] == 1，则image_i和image_j相似，否则它们不相似。在这里我们看到image_0与image_1和image_2类似，但image_1和image_2不相似（这只是非传递性的一个示例）。

我想保留最大数量的唯一图像（根据给定的sm矩阵，它们都是成对的非相似图像）。对于此示例，它应该是[image_2, image_3, image_4]或[image_1, image_2, image_3]（通常有多个此类子集，但我不介意将其保留为最大长度）。我正在寻找一种有效的方法，因为我有成千上万张图像。

编辑：以下是我的原始解决方法

np.array(images)[np.tril(sm).sum(0) == 1]

但是，不能保证它会返回最大长度子集。考虑以下示例：

sm = np.array([[1, 1, 0, 0, 0],
               [1, 1, 0, 0, 0],
               [0, 0, 1, 1, 0],
               [0, 0, 1, 1, 1],
               [0, 0, 0, 1, 1]])

此解决方案将返回['image_1', 'image_4']，而所需的结果是['image_0', 'image_2', 'image_4']或['image_1', 'image_2', 'image_4']。

Update：请参阅我的答案，该答案使用图论更详细地解释了该问题。我仍然愿意接受建议，因为我还没有找到一种成千上万张图像的快速实现结果的方法。

Answer 1

据我了解，独特的图像是与其他图像不同的图像。如果是这种情况，那么我们可以汇总行（或列）并选择结果中等于1的那些元素。然后我们需要从图像列表中获取相同的元素。

目前，我不知道如何在第二步中删除循环。

[images[i] for i in np.where(sm.sum(0) == 1)[0]]

UPDATE＃1

上面的讨论导致对该问题有了新的理解。

一种新的想法是一次删除一个图像，选择具有最大数量的相似图像。

images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']

sm = np.array([[1, 1, 1, 0, 1],
               [1, 1, 0, 0, 1],
               [1, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [1, 1, 0, 0, 1]])

ix = list(range(len(images)))

while sm[ix].T[ix].sum() != len(ix): # exit if we got the identity matrix
  va = sm[ix].T[ix].sum(0)           # count similar images
  jx = np.argmax(va)                 # get the index of the worst image
  del ix[jx]                         # delete index of the worst image

print([images[i] for i in ix])

输出：

['image_2', 'image_3', 'image_4']

UPDATE＃2

相同，但检查具有相似性最差值的每个分支

res = []

def get_wres(sm, ix):
  if sm[ix].T[ix].sum() == len(ix):
    res.append(list(ix))
    return
  va = sm[ix].T[ix].sum(0) # count similar images
  vx = np.max(va)          # get the value of the worst
  for i in range(len(ix)): # check every image
    if va[i] == vx:        # for the worst value
      ixn = list(ix)       # isolate one worst
      del ixn[i]           # image and
      get_wres(sm, ixn)    # try without it

get_wres(sm, ix)
print(res)

输出：

[[2, 3, 4], [1, 2, 3]]

Answer 2

这里有一个foor循环，不确定如何做到这一点：

results = [images[i] for i in range(len(images)) if sum(sm[i][i:]) == 1]

编辑：

这里是一个更正的解决方案，它与@Sergey的解决方案在本质上是相同的，但是使用不同的方式

def put_zeros_to_image_with_most_similarities(arr: np.array):
    index = np.sum(arr, axis=1).argmax()
    if np.sum(arr[index], axis=0) == 1:
        return
    arr[index] = 0
    arr[:, index] = 0
for _ in sm:
    put_zeros_to_image_with_most_similarities(sm)
results = [images[i] for i in range(len(images)) if sum(sm[i][i:]) == 1]

Answer 3

经过研究后，我发现这是图论中所谓的最大独立集问题，即不幸的是NP-hard。

independent set S是一组顶点，这样对于S中的每两个顶点，G中没有连接这两个顶点的边。我们正在寻找最大独立集（MIS），即具有最大可能顶点数的独立集。

有几个用于处理图形和网络的库，例如

igraph或NetworkX，它们已实现了用于查找最大独立集的功能。我最终使用了igraph。

对于我的问题，我们可以将图像视为图G的顶点，将“相似度矩阵”视为邻接矩阵：

images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']

sm = np.array([[1, 1, 1, 0, 1],
               [1, 1, 0, 0, 1],
               [1, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [1, 1, 0, 0, 1]])

# Adjacency matrix
adj = sm.copy()
np.fill_diagonal(adj, 0)

# Create the graph
import igraph
g = igraph.Graph.Adjacency(adj.tolist(), mode='UNDIRECTED')

# Find the maximum independent sets
g.largest_independent_vertex_sets()
[(1, 2, 3), (2, 3, 4)]

不幸的是，这对于成千上万个图像（顶点）来说非常慢。因此，我仍然乐于接受建议以寻求一种更快的方法（也许不是找到所有的MIS，而是找到一个）。
Note：@ Sergey（UPDATE＃1）和@marke提出的解决方案并不总是返回MIS。为了说明这一点，请考虑以下示例：
sm = np.array([[1, 1, 0, 0, 0, 1],
               [1, 1, 0, 1, 0, 0],
               [0, 0, 1, 1, 1, 0],
               [0, 1, 1, 1, 0, 0],
               [0, 0, 1, 0, 1, 1],
               [1, 0, 0, 0, 1, 1]])

两个解决方案都返回[3, 5]，但是对于此示例，最大独立集为两个，[(0, 3, 4), (1, 2, 5)]，由igraph正确找到。要查看为什么这些解决方案无法找到MIS，下面是一张gif文件，它显示了如何在每次迭代中删除顶点和边（这是np.argmax的“副作用”，它会多次出现最大值返回第一个出现的值） ）：
Sergey的解决方案（UPDATE＃2）似乎有效，但是它比igraph的largest_independent_vertex_sets()慢得多。为了进行速度比较，您可以使用以下随机生成的长度为100的相似度矩阵：
a = np.random.randint(2, size=(100, 100))

# create a symmetric similarity matrix
sm = np.tril(a) + np.tril(a, -1).T  
np.fill_diagonal(sm, 1)  

# crerate adjacency matrix for igraph
adj = sm.copy()
np.fill_diagonal(adj, 0)