I need to solve an assignment problem between the pixels of two images. That means, I want to find the pixel from the left image that matches best to a given pixel in the right image. But not on a per pixel basis, but considering the overall cost of all assignments.
Usually, you build a cost matrix for that and then lower on a row and column basis until you get at least one zero in each column and row. Those zeros are optimal assignments then. However, the cost matrix for a 1920 * 1080 pixel image would be roughly 4TB in memory, which I can't handle.
Is there an alternative that uses less space to solve the assignment problem?
The modifications made by the Hungarian algorithm to the cost matrix are to add/subtract constants from whole rows/columns. Instead of storing the whole matrix, you can store just the row/column deltas (i.e., the potentials) and, when retrieving a matrix element, add the appropriate one of each to the base cost (recomputed as needed). I expect that the running time still would be prohibitive, however.