2014-08-27 - TrackMate v2.5.0 released
We are happy to announce TrackMate version 2.5.0, but aren't we each time?
This version brings mainly a complete rewrite of the LAP tracker, that brings major improvement in speed performance and memory usage, as well as several enhancement in the UI of TrackScheme.
The new LAP tracker
We completely rewrote the LAP tracker and this version ships it. It gives (almost exactly) the same results and has the same settings that the former version, but exploits the sparse structure of the cost matrices we typically have in bioimaging to achieve a much better memory usage. Let's quickly review how.
The LAP tracking framework proposed by Jaqaman et al.[1] is based on generating a large cost matrix that contains the costs to link all possible spots to another, within physically reasonable bounds. Then a solver finds the links that minimize the total cost.
In some cases, when allowing for tracks to merge and split, the 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, because they are too far apart, not in suitable frames, etc...) 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 version brings. Of course, if this new tracker is optimized for memory usage, it has a cost on raw speed. However, it appears that this cost is not seen in practice.
With a 20k spots model (which is not even big), allowing all events, the memory used amounts to 10 GB with the old version. Which is madness. The new version takes 230 MB topx. And there is an added bonus: Normally the sparse version should take more time But in practice it does not; the memory manipulation overhead kills the performance of the old version: it takes 40 s. while the sparse version takes 18 s. And there is a second bonus: The main time is spent creating the cost matrix. But in the sparse version the creation can be multithreaded easily. So with 24 threads (with hyperthreading), the time for tracking goes down to 4s.
We have a new version of our tracker which is 10 times faster and takes 40 times less memory for medium-size models. It's probably longer for small models (but you would not feel it anyway), much quicker for medium-size models, and make large models doable. This is cool, but let's be honest, most modern tracking softwares offer this for a long time already.
There are tiny differences with the previous version, notably in the way cost thresholds are handled, that makes the new tracker give results that are not exactly the same as the old version. For instance, on a medium-size model, 99.73% of the links created are common to the two trackers. For this reason we did not discard the old version of the tracker, but renamed it with the prefix "old-". You can still find it in TrackMate, and it will be correctly set if you load from an XML file.
TrackScheme UI improvement
TrackScheme now features a search box and proper row and column headers.
Other improvement
A new action, called Branch hierarchy analysis features a branch-based analysis of tracks. The output is an ImageJ results table that contains for each branch the number of predecessors, the number of successors and its duration. The results table is clickable and will set the selection to be the clicked branch.
