ASTRE & CUTASTRE : (Accelerated) A contrario Smooth TRajectory Extraction

1. ASTRE : ``Point tracking: an a-contrario approach'' (Maël Primet, Lionel Moisan), preprint MAP5 nº2012-06 (download preprint MAP5 ).
2. CUTASTRE : ``Accelerated A-contrario Detection of Smooth Trajectories'' (Rémy Abergel, Lionel Moisan), proceedings of the European Signal Processing Conference (Eusipco), 2014 (download published version , , revised preprint ).

This program is released under GPL License.

Feel free to use and adapt this code. However, if you use it for your research or in software code, please be so kind as to cite the papers [1,2].

Also, if you use, adapt or improve the code, we would love to hear about it!

Dowload the C source code in your favourite format.

• Download C sources in .tar.gz format : 744 Ko.
• Download C sources in .zip format : 760 Ko.

This software is designed to have very low dependencies. Only the following standard libraries are required :

• stdio
• stdlib
• string
• math

It is composed of three independent source files astre_noholes.c and cutastre_noholes.c, corresponding to ASTRE and CUTASTRE implementations, and metrics.c, a tool dedicated to the evaluation of the detection quality by mean of comparison of a given sequence with a ground truth sequence. Those files must be compiled separately.

Open a terminal, then from the src directory of this software, run the gcc command lines displayed below (of course this can be adapted for others C-compilers).

gcc -O3 astre_noholes.c -lm -fopenmp -o astre_noholes
gcc -O3 cutastre_noholes.c -lm -fopenmp -o cutastre_noholes
gcc -O3 metrics.c -lm -o metrics

The executable files astre_noholes, cutastre_noholes and metrics are then created into the same repertory.

To check the installation was correctly done, you run ASTRE and CUTASTRE on a sample point set sequence (bundled with this software).

First, let us test the astre_noholes program. From the src directory, execute

./astre_noholes -v ../data/snowseq.txt /tmp/out_astre.txt

This must result in the extraction of 39 trajectories (go here to visualize the terminal standard output).

Now let us test the cutastre_noholes program:

./cutastre_noholes -v ../data/snowseq.txt /tmp/out_cutastre.txt

This must result in the extraction of 38 trajectories (go here to visualize the terminal standard output).

Last we check the metrics tool:

./metrics ../data/snowseq.txt /tmp/out_cutastre.txt

Go here to visualize the terminal standard output.

As usually, optional inputs are displayed inside square brackets.

Usage of ASTRE.

Usage: astre_noholes [--help] [--version] [-W width] [-H height] [-S maxspeed]
       [-m minscore] [-T numthreads] [-v] filenamein filenameout

   --help         : display help
   --version      : display program version
   -W width       : set the width (in pixels) of the image domain
		    (default = Xmax-Xmin+1, X(min/max) = smallest/highest
		    X-coordinate (horizontal axis) of the input sequence)
   -H height      : set the height (in pixels) of the image domain
		    (default = Ymax-Ymin+1, Y(min/max) = smallest/highest
		    Y-coordinate (vertical axis) of the input sequence)
   -S maxspeed    : only detect trajectories with maximal speed (that is
		    the maximal distance (in pixels) between two consecutive
		    points) less than maxpseed (may drastically reduce the
		    execution time)
   -m minscore    : (default = 0) set the score threshold, only trajectories
		    with a score higher than minscore will be extracted
   -T numthreads  : (default = 1) set the number of OpenMP threads
   -v             : verbose mode
   filenamein     : path to the input point set sequence file
   filenameout    : path to the output point set sequence file

Usage of CUTASTRE.

Usage: cutastre_noholes [--help] [--version] [-W width] [-H height] [-S maxspeed]
       [-c chunksize] [-o overlapsize] [-m minscore] [-T numthreads] [-v]
       filenamein filenameout

   --help         : display help
   --version      : display program version
   -W width       : set the width (in pixels) of the image domain
		    (default = Xmax-Xmin+1, X(min/max) = smallest/highest
		    X-coordinate (horizontal axis) of the input sequence)
   -H height      : set the height (in pixels) of the image domain
		    (default = Ymax-Ymin+1, Y(min/max) = smallest/highest
		    Y-coordinate (vertical axis) of the input sequence)
   -S maxspeed    : only detect trajectories with maximal speed (that is
		    the maximal distance (in pixels) between two consecutive
		    points) less than maxpseed (may drastically reduce the
		    execution time)
   -c chunksize   : split the frames of the sequence into chunks of specified
		    size (in number of frames), must be >=3 (default = 20)
   -o overlapsize : set the overlap size (in number of frames) between two
		    consecutive chunks, must be >= 2 and < c (default =
		    maximal value between 2 and floor(c/2))
   -m minscore    : (default = 0) set the score threshold, only trajectories
		    with a score higher than minscore will be extracted
   -T numthreads  : (default = 1) set the number of OpenMP threads
   -v             : verbose mode
   filenamein     : path to the input point set sequence file
   filenameout    : path to the output point set sequence file

Additional comments about the options

-S maxspeed : the speed threshold maxspeed is a physical parameter that can be easily adjusted in many applications. The use of this additional knowledge restricts the number of linking possibilities among the sequence, and reduces very significantly the execution time in general for both algorithms. However you must keep in mind that even using a speed threshold, the complexity of ASTRE remains quadratic with respect to the number of frames which is too much to handle long data sequences. The long data sequences must be processed with CUTASTRE which has a linear complexity with respect to the number of frames.

-c chunksize (CUTASTRE only):

-o overlapsize (CUTASTRE only):

-m minscore : you can consider that the higher is the score of a trajectory, the better is the confidence related to its detection. More rigorously, minscore controls the number of false detection that we accept when we process the sequence, we mathematically proved that in pure noise point set sequences, the average number of detected trajectories (i.e. the number of false detections) is less than \(10^{-\text{minscore}}\) (we refer to [1,2] as well as to the a-contrario methodology for more complete information). You can remember that we usually set minscore to zero in order to ensure that (in average) less than one detection is made in random (pure noise) sequences.

-T numthreads : some parts of the computation have been parallelized with OpenMP, if you are using a multicore or multi-CPU architecture, you may reduce a bit the computation time by increasing the number of threads, unfortunaltely the improvement is not very significant.

A qualitative visual inspection of the found trajectories already gives a rough idea of the algorithms performances. Yet one would sometimes rather have a way to quantify those performances.

Given a reference (or ground truth) sequence and a tested sequence (typically the output detection sequence obtained by running ASTRE or CUTASTRE on the reference), the precision and recall measurements can be used to compare the tested sequence with the reference sequence and evaluate the quality of the detection. Those quantities are defined as

$$ \text{precision} = \frac{\text{number of correct links}}{\text{number of found links}}, \quad\text{recall} = \frac{\text{number of correct links}}{\text{number of real links}},$$

where we call link two consecutive points of a trajectory, possibly separated by a hole (meaning that the two points may not belong to two consecutive frames), and a link is said to be real if it belongs to the ground truth, found if it belongs to the tested sequence, and correct if it belongs to both sequences.

More intuitively, the quantity \(1-\text{precision}\) measures the proportion of false positive links among found links while \(1-\text{recall}\) measures the proportion of false negative links among real links.

Sometimes the precision and recall measurements are combined leading to other quality metrics, such as the \(\text{F}_1\text{-score}\) (harmonic mean between precision and recall) or the G-measure (geometric mean between precision and recall),

$$\text{F}_1\text{-score} = 2 \times \frac{\text{precision} \times \text{ recall}}{\text{precision}+\text{recall}}, \quad \text{G-measure} = \sqrt{ \text{precision} \times \text{recall}}\;.$$

Usage of the metrics tool.

Usage: metrics [--help] [--version] ref seq

   --help    : display help
   --version : display program version
   ref       : path to the reference point set sequence file
   seq       : path to the tested point set sequence file

Example. Process the (short) PSMG sequence using cutastre and evaluate the quality of the detection. From the src directory, execute the following commands

./cutastre_noholes -c 30 -S 100 ../data/psmgshort.txt /tmp/out_cutastre.txt
./metrics ../data/psmgshort.txt /tmp/out_cutastre.txt