在没有成本矩阵的情况下解决分配问题

Question

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

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

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

Answer 1

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