Code covered by the BSD License  

Highlights from
Simple Tracker

4.75

4.8 | 9 ratings Rate this file 59 Downloads (last 30 days) File Size: 44.8 KB File ID: #34040
image thumbnail

Simple Tracker

by

 

01 Dec 2011 (Updated )

Simple multiple particle tracker with gap closing.

| Watch this File

File Information
Description

  SIMPLETRACKER a simple particle tracking algorithm that can deal with gaps
 
  *Tracking* , or particle linking, consist in re-building the trajectories
  of one or several particles as they move along time. Their position is
  reported at each frame, but their identity is yet unknown: we do not know
  what particle in one frame corresponding to a particle in the previous
  frame. Tracking algorithms aim at providing a solution for this problem.
 
  |simpletracker.m| is - as the name says - a simple implementation of a
  tracking algorithm, that can deal with gaps. A gap happens when one
  particle that was detected in one frame is not detected in the subsequent
  one. If not dealt with, this generates a track break, or a gap, in the
  frame where the particle disappear, and a false new track in the frame
  where it re-appear.
 
  |simpletracker| first do a frame-to-frame linking step, where links are
  first created between each frame pair, using the hungarian algorithm of
  |hungarianlinker|. Links are created amongst particle paris found to be
  the closest (euclidean distance). By virtue of the hungarian algorithm,
  it is ensured that the sum of the pair distances is minimized over all
  particles between two frames.
 
  Then a second iteration is done through the data, investigating track
  ends. If a track beginning is found close to a track end in a subsequent
  track, a link spanning multiple frame can be created, bridging the gap
  and restoring the track. The gap-closing step uses the nearest neighbor
  algorithm provided by |nearestneighborlinker|.
 
  INPUT SYNTAX
 
  tracks = SIMPLETRACKER(points) rebuilds the tracks generated by the
  particle whose coordinates are in |points|. |points| must be a cell
  array, with one cell per frame considered. Each cell then contains the
  coordinates of the particles found in that frame in the shape of a
  |n_points x n_dim| double array, where |n_points| is the number of points
  in that frame (that can vary a lot from one frame to another) and |n_dim|
  is the dimensionality of the problem (1 for 1D, 2 for 2D, 3 for 3D,
  etc...).
 
  tracks = SIMPLETRACKER(points, max_linking_distance) defines a maximal
  value in particle linking. Two particles will not be linked (even if they
  are the remaining closest pair) if their distance is larger than this
  value. By default, it is infinite, not preventing nay linking.
  
  tracks = SIMPLETRACKER(points, max_linking_distance, max_gap_closing)
  defines a maximal frame distance in gap-closing. Frames further way than
  this value will not be investigated for gap closing. By default, it has
  the value of 3.
 
  track = SIMPLETRACKER(points, max_linking_distance, max_gap_closing, debug)
  adds some printed information about the tracking process.
 
  OUTPUT SYNTAX
 
  track = SIMPLETRACKER(...) return a cell array, with one cell per found
  track. Each track is made of a |n_frames x 1| integer array, containing
  the index of the particle belonging to that track in the corresponding
  frame. NaN values report that for this track at this frame, a particle
  could not be found (gap).
  
  Example output: |track{1} = [ 1 2 1 NaN 4 ]| means that the first track
  is made of the particle 1 in the first frame, the particle 2 in the
  second frame, the particle 1 in the 3rd frame, no particle in the 4th
  frame, and the 4th particle in the 5th frame.
 
  [ tracks adjacency_tracks ] = SIMPLETRACKER(...) return also a cell array
  with one cell per track, but the indices in each track are the global
  indices of the concatenated points array, that can be obtained by
  |all_points = vertcat( points{:} );|. It is very useful for plotting
  applications.
 
  [ tracks adjacency_tracks A ] = SIMPLETRACKER(...) return the sparse
  adjacency matrix. This matrix is made everywhere of 0s, expect for links
  between a source particle (row) and a target particle (column) where
  there is a 1. Rows and columns indices are for points in the concatenated
  points array. Only forward links are reported (from a frame to a frame
  later), so this matrix has no non-zero elements in the bottom left
  diagonal half. Reconstructing a crude trajectory using this matrix can be
  as simple as calling |gplot( A, vertcat( points{:} ) )|

Acknowledgements

Hungarian Algorithm For Linear Assignment Problems (V2.3), Nearest Neighbor Linker, and Hungarian Based Particle Linking inspired this file.

This file inspired Tactics Toolbox.

MATLAB release MATLAB 7.5 (R2007b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (13)
12 Sep 2014 Zafer  
17 Jul 2014 Lucia Dzinza

hi Jean,

May you please assist me. I am tracking particles and l tried running the code on test script for simple tracker function, when l ran the programme, it asked me to define tracks, l defined it like this:
tracks=SIMPLETRACKER(points);
then it asked me to define SIMPLETRACKER. How do l define it?

25 Mar 2014 Jean-Yves Tinevez

Hi @Tedo.
Unfortunately no. To be honest there is little ground for publication: the techniques used here are basic. The tracking research field is very active nowadays, and they ship very elaborate solutions, which make this tool look like a toy.
I think however you can cite this page like I did for another tool. Thank you very much anyway,

24 Mar 2014 Tedo Biresaw

Any publications for the tracker reference ?

03 Feb 2014 Valentin

What should I do if there is no particle detected in a specific frame?
Empty matrix (e.g. points{7}=[]) results in an error:
Frame to frame linking using Hungarian method.
00000000000000000000010/28624Improper assignment with rectangular empty matrix.

09 Apr 2013 suissa  
28 Feb 2013 Raz Shimoni  
27 Oct 2012 Jean-Yves Tinevez

@kittu: hi Kittu. Could you contact me per email? I am not sure I understood your bug report, and would like to fix it.
Best
jy

26 Oct 2012 kittu

Thanks for the code.But i find a small bug in the code in the line 215 of simpletracker.m file.
A = sparse(row_index, column_index, link_flag, n_total_cells, n_total_cells)
When i run and try to see A, i find some of the values has been computed as 2, which should not be the case as per definition of sparse:
A(row_index(i),col_index(i))=link_flag(i)
and link_flag is a matrix of ones.
May be this could be one of the reason that the number of tracks which it computes at the end is not equal to what i expected.
I have a large array as my number of frames is 28400 and the number of points in some frames are 10 and in some it is 9.
If you could please explain or fix this bug, it will be helpful for me.

Thanks

22 Aug 2012 Dave

New version works great, thanks for the fix!

18 Aug 2012 Jean-Yves Tinevez

@Dave: Thanks so much!
Dave found a bug and proposed a fix. It is now in v1.3

17 Aug 2012 Dave

This is a really cool algorithm, but I'm having difficulty with a specific set of data where the displayed "gaps spanned" is what I want but the resulting tracks don't match. I can send a specific file if you have any ideas.

02 Dec 2011 Sebastien PARIS  
Updates
02 Dec 2011

Added proper acknowledgements

30 Jan 2012

Modified the code to have it running o older MATLAB versions, at the very least R2007b. Following a request by Bill Betz.

14 May 2012

v1.1 - May 2012
- Solve memory problems for large number of points.
- Considerable speed improvment using properly the sparse matrices.
- Use the key/value pair syntax to configure the function.

22 May 2012

Fix a bug preventing from using the 'NearestNeighbor' option.

20 Aug 2012

 v1.3 - August 2012 - Fix a severe bug thanks to Dave Cade

Contact us