解決沒有成本矩陣的分配問題？

我需要解決兩個圖像的像素之間的assignment problem。這意味着，我想從右側圖像中找到最適合給定像素的像素。但不是以像素爲單位，而是考慮所有作業的總體成本。解決沒有成本矩陣的分配問題？

通常情況下，您會爲此生成一個成本矩陣，然後按行和列逐個降低，直到您在每列和每行中至少得到一個零。然後那些零是最佳的分配。然而，1920×1080像素圖像的成本矩陣在內存中大約爲4TB，這是我無法處理的。

是否有替代方案使用較少的空間來解決分配問題？

2014-09-03 danijar

要明確一點，你正在尋求與B最接近的（從某種意義上）B的排列？ – 2014-09-03 21:22:44

你需要一個精確的一對一比賽嗎？也許你可以將圖像細分爲塊並匹配每個塊，然後匹配每個塊中的像素？ – templatetypedef 2014-09-03 21:22:45

我不知道確切的上下文，但是您可以構建一個稀疏矩陣，其中圖片A中的每個像素只能與圖片B中的一些像素相匹配。（例如，n個空間最接近的像素） – Seb 2014-09-03 21:26:22

匈牙利算法對成本矩陣所作的修改是從整行/列中加/減常數。您可以只存儲行/列增量（即電位），而不是存儲整個矩陣，而是在檢索矩陣元素時，將每個元素中適當的一個添加到基本成本（根據需要重新計算）。不過，我預計運行時間仍然會令人望而卻步。

2014-09-03 23:13:53

即使僅存儲三角洲，矩陣將是1920倍1080平方。即使每條記錄只使用一個字節，這也是3.9TB。或者我誤解你的答案？ – danijar 2014-09-04 05:57:37

@danijar您需要1920 \ * 1080 \ * 2 = 4147200個條目，每個行和成本矩陣的每一列都有一個條目。基本成本是按需計算的，因此不存儲。 – 2014-09-04 06:13:38

所以，你的意思是我不儲存成本，但是我從每行或每列中減去了哪個值，對嗎？ – danijar 2014-09-04 06:20:33

回答