I am currently working on a program in C which analyzes positions detected in the current frame compared to the last frame. In the case where one or more position is detected in the current frame, I need to estimate which objects are new. To do this, I can't simply find which values are the furthest from all other values as it isn't accurate enough.

Example:

vector<float> currentFramePosition = {0.08, 0.19, 0.22, 0.56, 0.7, 0.9};
vector<float> lastFramePosition = {0.09, 0.23, 0.52, 0.8, 0.98};

In this example, we can see that there is one new value. If we assume the value that is the furthest away from the last frame's values we get that the new value is the 0.7 at the 4th index. If we look at it objectively the new value should be 0.19 if we want to minimize the total distance. If we match 0.19 with 0.23, 0.22's closest value will be 0.52 and that distance is bigger than the distance between 0.7 and 0.8.
There can be more than one new value in each frame.

Is there a way to find which values are new without the function being too time complex?

Thanks!

CodePudding user response：

One way of solving this would be to frame it as a minimum-weight bipartite matching problem. Specifically, you’re trying to pair off items in the old frame with items in the new frame in a way that minimizes the total distance between the matched points. There are many standard algorithms for solving this problem in a reasonable amount of time. The Hungarian algorithm is probably the most famous, but you should be able to find an existing set of efficient libraries that will compute minimum-weight bipartite matchings.