Space-Traversal-Matching

Intro

The STM code is an ongoing project to make a 3D matching code for PTV purposes. It is based on this publication:

Using ray-traversal for 3D particle matching in the context of particle tracking velocimetry in fluid mechanics
Mickaël Bourgoin, Sander G. Huisman
Rev. Sci. Instrum. 91, 085105 2020 [Link][arΧiv]

The code has been used already in a variety of geometries including water channel, Rayleigh–Bénard, Taylor–Couette, and the Lagrangian Exploration Module.

See here an example of particle tracking done in the Taylor–Couette geometry using 8 cameras. The outer cylinder is not encased in a water box for refractive index corrections. Large optical distortions are taken care of by our calibration. The matches are found using the STM code covering the full 360°, the tracking has been done by other methods.

Inner cylinder rotation only.
Counter rotating cylinders

Also in this video, the tracks are found using the STM code:

See also here

The purpose of the code is to go from rays (found using e.g. a Tsai model) for each particle and for each camera to 3D matches. It does this on a frame-per-frame basis; no information or prediction from previous frames are used. Though an extension to the code would be possible to preferentially select new matches based on predicted new spots.

The main difference between this code and most other codes is that the order in which you present the rays, or the order of the cameras is irrelevant. In most algorithm the matches are chosen based on first matching between camera 1 and 2, and then combined with camera 3 and so on. This gives some preference to the cameras, and the order of the rays. The methodology of the STM code has the main advantage that the outcome of the method is independent of the order of the input; the order of the cameras and the order of the rays presented as input to the algorithm do not influence the outcome. The time complexity of the number of particles and the number of cameras are found to scale favourably. More details can be found in our publication.

Input file

The STM code ingests a single multi-frame multi-camera multi-ray binary file. With the following specification:
<for each frame>
   number of rays (unsigned int 32 bits)
   <for each ray>
      Camera ID (unsigned int 8 bits)
      Ray ID (unsigned int 16 bits)
      x: starting point ray (float 32 bits)
      y: starting point ray (float 32 bits)
      z: starting point ray (float 32 bits)
      vx: Direction of ray (float 32 bits)
      vy: Direction of ray (float 32 bits)
      vz: Direction of ray (float 32 bits)
      tmin: (<0) travel in negative direction (float 32 bits)
      tmax: (>0) travel in positive direction (float 32 bits)
Each ray is therefore 8+16+8*32 bits = 280 bits = 35 byte. So a frame with n rays is 32+n*280 bits big. The input file is therefore just a sequence of frames, for each it start with the number of rays and then the specification for each ray (for all cameras) is given. The final file is just a long sequence of binary numbers, as such it does not have 'enters', 'newlines', 'tabs' et cetera and the file is not human readable. Input and export can be adapted to accept other file formats.

Output file

The name of the output file are based on the input file. The extension is removed and the following postfix is added: _out.bin. So for the case of an input file 256pts_4cam_100frame.dat the output file is called 256pts_4cam_100frame_out.bin.

A log file is also maintained, for this the input file name is appended with _out.log.

The format of the results are also in a binary format that can be read using Matlab, Mathematica, Python et cetera. The file has the following file format:
<for each frame>
   number of matches (unsigned int 32 bits)
   <for each match>
      Number of rays used for match (unsigned int 8 bits)
      x: match (float 32 bits)
      y: match (float 32 bits)
      z: match (float 32 bits)
      match error: match (float 32 bits)
      <for each ray used>
         Camera ID (unsigned int 8 bits)
         Ray ID (unsigned int 16 bits)
Each match is therefore 136 + 24*n bits where n is the number of rays used for that match.

Arguments of calling STM

We have 14 arguments:
  1. input file
  2. xmin
  3. xmax
  4. divisions in x direction
  5. ymin
  6. ymax
  7. divisions in y direction
  8. zmin
  9. zmax
  10. divisions in z direction
  11. Minimum amount of cameras for a match (typically 2, 3, or 4)
  12. How many matches (at most) per ray? (typically 1 or 2)
  13. Maximum error for the match. Square root of average distance of the match point to each ray squared. Can also be changed to maximum rather than average.
  14. Each ray has a start and end point, this is how far it gets extended in both direction. This can be useful to make sure it 'just' hits one of the voxels.
Example of calling the software would be:
./STM 256pts_4cam_100frame.dat -0.55 0.55 68 -0.55 0.55 68 -0.55 0.55 68 3 2 0.0015 0.005
for having the file 256pts_4cam_100frame.dat, voxels from -0.55 to 0.55 with 68 divisions in each direction. Having at least rays from 3 different cameras for a match, matching each ray at most twice, having a maximum match error of 0.0015 units, and each ray is extended 0.005 units.

Downloads

C++11 code:
Main.cpp (v0.2) (MD5 Hash: 2a8d4eaa5724d4e8bda8f66185884e6e)

Test case with perfectly crossing rays:
Test files 1: 256 particles, 4 cameras, 25 frames (MD5 Hash: 6fb2ac03e0af6c5d4359334f2b5ab9d4)
Run the code as follows:
./STM 256pts_4cam_100frame.dat -0.55 0.55 68 -0.55 0.55 68 -0.55 0.55 68 4 1 0.0015 0.005
expected output files included

Test case with not perfectly crossing rays:
Test files 2: 256 particles, 4 cameras, 25 frames (MD5 Hash: 3f6b1f94f3abc51a66cafe066f4e6d9a)
Run the code as follows:
./STM 256pts_4cam_100frame.dat -0.55 0.55 68 -0.55 0.55 68 -0.55 0.55 68 3 1 0.005 0.5
expected output files included