An alternative algorithm for clustering trajectories

[stevenstetzler]

The outputs from KBMOD consist of a list of results, each a tuple of (x, y, vx, vy, likelihood) where (x,y) is the starting position on the first image, (vx, vy) is a test velocity for a hypothesized object in pixels/day, and likelihood is the summed likelihood for the existence of the hypothesized object. A threshold on the likelihood is used to limit the list of results.

The list of results are unique with respect to their entries, but may be degenerate in their physical interpretation. Small offsets in (x, y) and (vx, vy) can produce multiple results with above-threshold likelihood levels. See e.g. the follow figure from @DinoBektesevic.

These degenerate results need to be merged into a single hypothesis for a moving object. Currently, the DBSCAN algorithm is used to cluster results on the values of (x, y, vx, vy) using parameters that are not necessarily physically motivated due to the mixing of positional quantities (x, y) and velocity quantities (vx, vy).

An alternative "friends-of-friends" algorithm for clustering trajectories that has physically motivated clustering parameters follows. Consider a single candidate trajectory (x, y, vx, vy). Compute its position at the first time in the search and the last time in the search: (x0, y0) and (xN, yN). Define a circle around the first position with radius dx0 and around the last position with radius dxN. All lines that lie completely within the volume of the cylinder defined by the circles at the endpoint are determined to be a "friend" of the candidate trajectory. The set of lines that satisfy this constrain have endpoints that lie within the circular regions defined by (x0, y0, dx0) and (xN, yN, dxN). See this figure for an illustration:

Next, determine the set of "friends" for each candidate trajectory and construct a "friends-of-friends" graph of the connections between trajectories. Within this graph, there should be subsets of trajectories which are connected to each other but are isolated from others, allowing the graph to be partitioned into disjoint subsets. Call these subsets "clusters". Filter out clusters that have a low number of members. For each of the remaining clusters, assign as its representative trajectory the trajectory with the highest likelihood. Provide the representative trajectories from the remaining clusters as the clustered set of results.

In the regime that KBMOD cares about, where results have already been filtered on likelihood, this algorithm should work because clusters of similar trajectories should appear around genuine sources with the number of duplicate trajectories depending on the likelihood cutoff used and the brightness of the source; objects are similarly bright within a few pixel radius of the center depending on their intrinsic brightness. Filtering on the number of members in each group may not work if genuine objects are found in just one trajectory with no duplicates. In this algorithm, the width of the circles corresponds to the positional uncertainty of the sources being detected, which is no more than ~1 arcsec, or might also be taken as the width of the PSF on the endpoint images, again typically ~1 arcsec.