我一直在使用一些已经在 python 中实现的匈牙利/munkres 算法（munkres 包和 scipy linear_sum_assignment 是具体的）并且它们都运行良好（无论如何它们都基于相同的 C 实现），但是它们缺乏我特别需要的功能。
为了给出一些上下文，我正在跟踪从一个图像到另一个图像的点，所以成本矩阵是图像 1 中的点到图像 2 中的所有点之间的距离。
问题出现在一个非常特殊的情况下，即如果图像 1 中的一个点在第二个图像中丢失，但在图像 2 中也检测到一个新的不同点，那么图像 1 中的一个点总是与新的点匹配观点。这是匈牙利算法按预期工作，不要误会我的意思。但是我需要的是匈牙利算法返回一个“不匹配”的点，如果它想要匹配的点太远的话。在 matlab 中，文件交换中有一个名为 simpletracker.m 的示例，那里的 munkres 实现可以允许没有良好链接的情况。因此，即使您有两个图像，例如 5 个粒子，它也可能只链接这些粒子中的 2 个，因为您可以使用最大链接距离参数来决定是否应该进行分配。
举个简单的例子，如果我们有一个在 (1,1) 和 (10,1) 有两个点的 image1，并且为了争论，我们知道它们会在下一张图像中向右移动一个像素，所以我们希望它们在图像 2 中位于 (2,1) 和 (11,1) 处，如果在第二张图像中找到正确的粒子，匈牙利算法将很容易链接正确的粒子。但是，如果没有找到其中一个，就会出现问题，比如 (11,1) 处的点，而是在 (20,1) 处发现视频中出现的随机噪声点或新点。然后匈牙利算法将按预期链接点 (1,1) 和 (2,1)，但现在也将 (10,1) 链接到 (20,1)。
所以在matlab实现中你可以选择一个最大链接距离值，然后将成本矩阵条目设置为无穷大，如果只能分配一个粒子，那么没关系，算法只返回一个链接。在 munkres.py 包中，有一个叫做 DISALLOWED 的东西，但是一旦这阻止了对每个点的分配，算法就会失败。例如，差分矩阵将是 [[1, 9^2],[8^2, 10^2]]。如果我们将 70 设置为最大链接距离，则矩阵为 [[1, DISALLOWED],[64, DISALLOWED]] 这意味着唯一有效的分配是图像 1 (1,1) 中的点 1 到图像 2 中的点 1 (2 ,1)。然而，munkres 算法只会返回 UnsolvableMatrix: Matrix cannot besolved！因为它无法链接第二点。
很抱歉文字墙和可能的混乱。我要问的是，是否有人知道可以允许非赋值的 munkres 实现，它已经在 python 中实现了？或者，处理错误匹配点的最佳做法是什么？我在想我可以在分配完成后尝试过滤掉异常值，或者如果所有值都被禁用，或者在计算距离矩阵后可能从距离矩阵中删除列，但是我不确定这是否足够强大以涵盖所有可能案例。