Initialization

The initializing step of the algorithm is illustrated in figure 1. Consider an arbitrary point $P_{2,i}$ in the frame $F_{2}$ and try to find the corresponding points in $F_{1}$ and $F_{3}$. Using the maximum speed constraint, project the location of $P_{2,i}$ onto $F_{1}$ and $F_{3}$ and determine the search areas of $P_{2,i}$ in $F_{1}$ and $F_{3}$ as those regions that may contain the candidate matching points for $P_{2,i}$. Denote by $S^-_{k,i}$ and $S^+_{k,i}$ the search areas of $P_{k,i}$ in $F_{k-1}$ and $F_{k+1}$, respectively. The radius of these circular areas is defined by the maximum speed $v_{max}$.

  

Figure 1: Initializing the tracking procedure. The filled circles are the moving points, the empty circles their locations projected to the neighboring frames. The solid lines show the competing trajectories. The dashed lines illustrate the formation of the search areas.

Then consider all possible triplets of points $(P_{1,n},P_{2,i},P_{3,m})$, $P_{1,n}\in S^-_{2,i}$, $P_{3,m}\in S^+_{2,i}$, that contain the point $P_{2,i}$. Find the triplet  $(P_{1,a},P_{2,i},P_{3,b})$that minimizes for $k=2$ the cost function $\delta(P_{k-1,n},P_{k,i},P_{k+1,m})$.

A cost function evaluates the local deviation from smoothness and penalizes changes in both direction and magnitude of the velocity vector. Its value is normalized so as to span the range $[0,1]$, with $0$ meaning no change at all. Different cost functions implemented and tested with the proposed algorithm are defined in section 4.4. The IPAN Tracker uses the cost limit $\delta_{max}\in [0,1]$ as a smoothness threshold to discard obviously wrong links. (The setting of $\delta_{max}$ is discussed in section 4.5.)

Select the triplet  $(P_{1,a},P_{2,i},P_{3,b})$ as the initial hypothesis and rank the remaining triplets according to their cost values. (The triplets with $\delta < \delta_{max}$ are only considered.) Test the initial hypothesis by scanning $S^-_{3,b}$, the search area of $P_{3,b}$ in $F_{2}$. Let $P_{2,q}$ be a point in $S^-_{3,b}$. (See figure 1.) If $S^-_{2,q}$ has a point $P_{1,r}$ such that $\delta(P_{1,r},P_{2,q},P_{3,b}) < \delta(P_{1,a},P_{2,i},P_{3,b})$, then the initial hypothesis is rejected and the second ranking hypothesis is considered and tested. Otherwise, the testing of the initial hypothesis proceeds with checking $P_{1,a}$in the same way. If this check is also successful, $(P_{1,a},P_{2,i},P_{3,b})$ is output as the initial part of the trajectory of $P_{1,a}$. The correspondences established are not altered during further processing.

If all the hypotheses for $P_{2,i}$ have been rejected, this point is not linked to $F_{1}$ and $F_{3}$. It is still possible that $P_{2,i}$ will be linked to $F_{3}$when the latter is processed. In such case $P_{2,i}$ appears and opens a trajectory.

When all points of $F_{2}$ have been processed, some points in the neighboring frames may remain unmatched. A point in $F_{1}$ that is not linked to any point in $F_{2}$ disappears, that is, either leaves the view field or temporarily disappears within the image, e.g., due to occlusion. An unmatched point in $F_{3}$ may later open a trajectory.

In the above description of the hypothesis testing procedure, the original hypothesis is rejected immediately when a `stronger' triple $(P_{1,r},P_{2,q},P_{3,b})$ is found. However, $(P_{1,r},P_{2,q},P_{3,b})$ can itself be overruled by still another triple if the verification proceeds by testing $(P_{1,r},P_{2,q},P_{3,b})$ in a similar way, that is, by switching back to $F_{2}$ and $F_{3}$. The original hypothesis can possibly be restored. This deeper verification implies a longer sequence of simultaneous events whose probability decreases rapidly with the verification depth $N_{ver}$. The version described above is $N_{ver}=1$. Currently, we use $N_{ver}=2$ which is sufficient for point sets of reasonable density. (See section 4.5 for a discussion.)