fiji/TrackMate — pull request #42 by tinevez (2014-08-09 16:18:28+00:00)
Title: A Sparse tracker for the Jaqaman LAP framework.

This PR adds a new tracker module to TrackMate, the Sparse LAP Tracker.

It gives the same results and has the same settings that the LAP Tracker, but exploits the sparse structure of the cost matrices we typically have for our problems to achieve a **much better memory usage**.

In some cases, when allowing for tracks to merge and split, the double[][] cost matrix generated had almost all spots of the model as rows and almost all spots of the model as columns. Even is the vast majority of these costs were Infinite (impossible linking) they still occupied most of the memory. It gets worst as the cost matrix has to be manipulated to be completed by alternative costs. These heavy movements of large chunks of memory can crash the program and slows it down considerably.

The answer is using a data structure that takes advantage of the sparsity of the problem and algorithms that deal with such structure, which is what this PR brings. Of course, if this new tracker is optimized for memory usage, it has a cost on raw speed. However, initial tests on my small PC at home show that when tracking about 20k spots and allowing tracks to split, the memory manipulation overhead causes the Sparse version to be quicker than the non-sparse (18 s. vs 24 s.). And this even if the memory limit has not been reached. More intense tests reporting actual memory usage should follow on the TrackMate wiki page.

This is cool, but let's be honest, most modern tracking softwares offer this for a long time already. :smiling_imp: