The initializing step of the algorithm is illustrated in figure 1. Consider an arbitrary point in the frame and try to find the corresponding points in and . Using the maximum speed constraint, project the location of onto and and determine the search areas of in and as those regions that may contain the candidate matching points for . Denote by and the search areas of in and , respectively. The radius of these circular areas is defined by the maximum speed .
Then consider all possible triplets of points , , , that contain the point . Find the triplet that minimizes for the cost function .
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 , with 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 as a smoothness threshold to discard obviously wrong links. (The setting of is discussed in section 4.5.)
Select the triplet as the initial hypothesis and rank the remaining triplets according to their cost values. (The triplets with are only considered.) Test the initial hypothesis by scanning , the search area of in . Let be a point in . (See figure 1.) If has a point such that , 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 in the same way. If this check is also successful, is output as the initial part of the trajectory of . The correspondences established are not altered during further processing.
If all the hypotheses for have been rejected, this point is not linked to and . It is still possible that will be linked to when the latter is processed. In such case appears and opens a trajectory.
When all points of have been processed, some points in the neighboring frames may remain unmatched. A point in that is not linked to any point in disappears, that is, either leaves the view field or temporarily disappears within the image, e.g., due to occlusion. An unmatched point in may later open a trajectory.
In the above description of the hypothesis testing procedure, the original hypothesis is rejected immediately when a `stronger' triple is found. However, can itself be overruled by still another triple if the verification proceeds by testing in a similar way, that is, by switching back to and . 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 . The version described above is . Currently, we use which is sufficient for point sets of reasonable density. (See section 4.5 for a discussion.)