Search code examples
c++arraysalgorithmstltracking

Algorithm for fast array comparison and replacing elements with closest value. (Tracking Points)

I have two arrays currPoints and prevPoints. Both are not necessarily the same size. I want to compare each element in currPoints with prevPoints and replace the value in prevPoints that is closest to the value in currPoints.

Example:

prevPoints{2,5,10,13,84,22}
currPoints{1,15,9,99}

After applying the algorithm

prevPoints{1,5,9,15,99,22}

So what is the best algorithm/method for this? It needs to be fast.

Context: If it helps, I am trying to work on a tracking algorithm that takes points from two consecutive frames in a video and tries to figure out which points in the first frame correspond to points in the second frame. I hope to track objects and tag them with an ID this way. Speed is crucial as processing is to be done in realtime.

Solution

  • You need to sort both the arrays first. But remember the original orientation of the prevPoints array as you need to get the original array again at the end.

    So after sorting:

    prevPoints{2,5,10,13,22,84}
currPoints{1,9,15,99}

    Now you basically need to figure out which of the currPoints should get into prevPoints. The algorithm is will be similar to merge 2 sorted arrays just that you won't merge, instead replace values.

    Initially both pointers are at the start of the corresponding arrays. 1 from currpoints should replace 2 in prevPoints based on the fact that the value in currPoints is less than prevPoints and you know that the next points in PrevPoints will only be higher than 2 (sorted arry, remember). Replace and move on the pointers.

    Now currpointer is at 9 and prevpointer is at 5. Calculate the absolute difference and keep a store of the minimium absolute difference encountered so far and also the value of the number that caused the least minimum absolute difference to be encountered.(4 in this case). Move the prevpointer forward as the currpointer is pointing to a higher value.

    Now prevpointer at 10 and currpointer at 9. 9 is less than 10 and so a replacement has to be done. As this minimum absolute difference is less than the earlier one ( 1 < 4 ) so 10 will be replaced by 9.

    Now the prevpointer is at 13 and currpointer is at 15.

    Proceed in the same fashion.

    Rearrange the prevPoints array to the original orientation.

    Hope this helps!!!