algorithm - 图像中加权像素的优化配对

Question

给定一个表示图像的矩阵 X，每个像素 X(i,j) 都有一个向量 Vij，它给出了将像素 X(i,j) 与图像中的每个其他像素相关联的成本(我将实际使用它对于指定的小社区，但它不应该在算法方面产生影响)。

配对像素 X(i,j) 和 X(k,p) 的成本是将像素 X(i,j) 与 X(k,p) 关联的组合成本和关联像素 X(k) 的成本,p) 与像素 X(i,j)。请注意，成本函数是对称的，即关联 X(i,j) 与 X(k,p) 的成本等于关联 X(k,p) 与 X(i,j) 的成本。

目标是为图像中的每个像素找到一个配对，使得每个像素恰好是一个配对的一部分，并且总成本最小化/最大化。

二维空间局部性没有特殊意义，因此我们可以将X[i*w + j] 视为一维成本数组，并构造一个二维成本矩阵。鉴于对称性，我们可以只考虑对角线以上的矩阵的一半。然后我们正在寻找一组具有最小总和的点(行，列对)。每行和每列只能使用一次。 (包含 C[a][b] 会消除 a 行中的所有条目和 b 列中的所有条目，使其不再可能是解决方案的其他成员设置。)

想到的一种方法是将其视为流问题，但在那种情况下，我不知道如何构建图形。

Answer 1

如果我对您的目标的理解正确，那么您的问题本质上是在加权图中找到具有最大/最小权重的完美匹配。

阅读链接:

• Matching
• Maximal matching
• Kolmogorov's minimal matching algorithm