Hungarian.m returns incorrect solution in presence of infinite edges

[jvlmdr]

There seems to be a bug in Hungarian.m, which is used by matlab_devkit/utils/preprocessResult.m. This was also noticed by @JonathonLuiten. The bug seems to occur when there are infinite edges in the bipartite graph (which is the case in the preprocess script).

Here is a minimal working example. While there exists a perfect matching (size 3), the function does not find it and returns a matching of size 2

Hungarian([0 inf 10; inf 1 inf; 1 inf inf])

Expected result:

ans =
   0   0   1
   0   1   0
   1   0   0

Actual result:

ans =
   1   0   0
   0   1   0
   0   0   0

The problem may arise from the min_cover_line() function. It seems to identify the "deficiency" as 1, which leads to additional vertices being added to ensure that a perfect match exists, and the solver is applied to the matrix:

P_cond =
     0   Inf    10    10
   Inf     1   Inf    10
     1   Inf   Inf    10
    10    10    10    10

obtaining (correctly) the matching

M =
   1   0   0   0
   0   1   0   0
   0   0   0   1
   0   0   1   0

On the other hand, MinCostMatching.mex returns the correct solution. Maybe this could be fixed by simply replacing Hungarian() with MinCostMatching().

If I try using large finite values instead, the correct solution is obtained:

Hungarian([0 1e6 10; 1e6 1 1e6; 1 1e6 1e6])
ans =
   0   0   1
   0   1   0
   1   0   0

(Tested on octave 5.2.0)

[JonathonLuiten]

As @jvlmdr points out, I also found the same error.

To add to the discussion I upload a 'real world' test case, in which this problem is visible. This is extracted from one frame (I don't remember which timestep sorry) for the LPC_MOT tracker running on the MOT20-05 sequence.

test.zip

My analysis was also that:

1. By default the preprocessing script Hungarian.m gave an incorrect solution to the linear assignment problem here.
2. By replacing Inf with very large numbers it got the correct solution again.
3. By replacing the matlab hungarian code with the c mex code from the repo it gave the correct solution also.
4. Scipy's hungarian solver gives the correct solution.

I also found that simply replacing the matlab hungarian with the mex, or replacing inf with large numbers, resulted in the eval running really slow over whole sequneces for some reason (didn't look further into this).

Also note that, in my analysis, when evaluating MOT17 over 15 different trackers (AGT, GNNMatch, GSM_Tracktor, IA, ISE_MOT17R, Lif_T, Lif_TsimInt, LPC_MOT, MAT, MIFTv2, MPNTrack, SSAT, TracktorCorr, Tracktorv2, UnsupTrack) this resulted in a total difference of 13 FPs (out of approx 500k), 13 FNs (out of approx 1.5 mil) and 2 IDSWs (out of approx 13k) compared to using a non-bugged preprocessing (using scipy).

[JonathonLuiten]

Note also that to 3 decimal places this bug does not produce any difference in MOTA / MOTP / MODA etc scores.

P.s. to anyone reading, MOTChallenge is in the process of updating it's evaluation to use the code at (https://github.com/JonathonLuiten/HOTA-metrics) where this bug is fixed.