Multiple particle tracking in PEPT using Voronoi tessellations - Blakemore, Dylan (Department of Mechanical Engineering, 2017)
An algorithm is presented which makes use of three-dimensional Voronoi tessellations to track up to 20 tracers using a PET scanner. The lines of response generated by the PET scanner are discretized into sets of equidistant points, and these are used as the input seeds to the Voronoi tessellation. For each line of response, the point with the smallest Voronoi region is located; this point is assumed to be the origin of the corresponding line of response. Once these origin points have been determined, any outliers are removed, and the remaining points are clustered using the DBSCAN algorithm. The centroid of each cluster is classified as a tracer location. Once the tracer locations are determined for each time frame in the experimental data set, a custom multiple target tracking algorithm is used to associate identical tracers from frame to frame. Since there are no physical properties to distinguish the tracers from one another, the tracking algorithm uses velocity and position to extrapolate the locations of existing tracers and match the next frame's tracers to the trajectories. A series of experiments were conducted in order to test the robustness, accuracy and computational performance of the algorithm. A measure of robustness is the chance of track loss, which occurs when the algorithm fails to match a tracer location with its trajectory, and the track is terminated. The chance of track loss increases with the number of tracers; the acceleration of the tracers; the time interval between successive frames; and the proximity of tracers to each other. In the case of two tracers colliding, the two tracks merge for a short period of time, before separating and become distinguishable again. Track loss also occurs when a tracer leaves the field of view of the scanner; on return it is treated as a new object. The accuracy of location of the algorithm was found to be slightly affected by tracer velocity, but is much more dependent on the distance between consecutive points on a line of response, and the number of lines of response used per time frame. A single tracer was located to within 1.26mm. This was compared to the widely accepted Birmingham algorithm, which located the same tracer to within 0.92mm. Precisions of between 1.5 and 2.0mm were easily achieved for multiple tracers. The memory usage and processing time of the algorithm are dependent on the number of tracers used in the experiment. It was found that the processing time per frame for 20 tracers was about 15s, and the memory usage was 400MB. Because of the high processing times, the algorithm as is is not feasible for practical use. However, the location phase of the algorithm is massively parallel, so the code can be adapted to significantly increase the efficiency.