search

sigsep / bsseval

audio source separation evaluation metrics
MIT License
26 stars 10 forks source link

Use an efficient algorithm to find the best permutation #5

Closed fakufaku closed 2 years ago

fakufaku commented 5 years ago

The current implementation of bss_eval, in mir_eval and here, exhaustively tests all permutations of sources which has factorial cost. It is possible to find the permutation in quadratic time using a minimum weight matching algorithm for bipartite graphs. This algorithm is implemented in scipy by the function linear_sum_assignment.

I have made a PR to mir_eval with the required changes. In mir_eval it seems to start to make a difference in runtime only for 9 or more sources, but the difference is very significant then. However, since you are also implementing computationally lighter versions of bss_eval/si_sdr here, there is potentially room for improvement even with fewer sources.

I'd be happy to pitch in some code if required.

aliutkus commented 5 years ago

I never considered the setting where the order of the sources is unknown in my estimates,

but I think it's a really cool contribution, and I'd be happy if we included this, because the case of MANY sources is probably going to be a big thing in the near future, since few and known sources is working so well

fakufaku commented 5 years ago

Great! In determined separation, this is rather the norm to not know the permutation (or that's how it seemed to me).

Actually, my above comment (now edited) was a bit mis-leading, the PR I did is for mir_eval. I also took a look at the current code in this repo, but I wasn't sure if it is stable enough to accept a contribution. If you think it is the case, I'd be happy to start.

aliutkus commented 5 years ago

I'd be in to have this feature right from the start still, @faroit may have a better understanding of what needs be done before ?