algorithm - 解决没有成本矩阵的分配问题？

Question

我需要解决一个 assignment problem在两个图像的像素之间。这意味着，我想从左图像中找到与右图像中给定像素最匹配的像素。但不是以每个像素为基础，而是考虑所有分配的总体成本。

通常，您为此构建一个成本矩阵，然后逐行逐列降低，直到每列和每行中至少有一个零。那么那些零是最佳分配。但是，1920 * 1080 像素图像的成本矩阵大约需要 4TB 的内存，这是我无法处理的。

是否有使用更少空间来解决分配问题的替代方案？

Answer 1

匈牙利算法对成本矩阵所做的修改是从整行/列中添加/减去常量。您可以只存储行/列增量(即势)，而不是存储整个矩阵，并且在检索矩阵元素时，将每个元素中的适当元素添加到基本成本(根据需要重新计算)。不过，我预计运行时间仍然会令人望而却步。