I have two different physical devices (one is camera, one is other device) that observe the same scene and mark when a specified event occures. (record timestamp)

So they each produce a serie of timestamps "when the event was observed". Theoretically the recorded timestamps should be very well aligned:

Visualized ideal situation on two time lines "s" and "r" as recorded from the two devices:

Visualized timestamps of events in ideal conditions

but more likely they will not be so nicely aligned and there might be missing events from timeline s or r:

Visualized timestamps of events in real world conditions

I am looking for algorithm to match events from "s" and "r" like this:

Matched events

So that the result will be something like: (s1,null); (s2,r1); (s3,null); (s4,r2); (s5,r3); (null,r4); (s6,r5); Or something similar. Maybe with some "confidence" rating.

I have some ideas, but I feel that this might be probably a well known problem, that has some good known solutions, but I don't know the right terminology. I am a little bit out of my element here, this is not my primary area of programming.. Any helps, suggestions etc will be appreciated.

  • 1
    In order to solve the problem, you will need some criteria that matches like points. Example criteria: "If time stamps are within 100 nanoseconds of each other, then they are considered the same event." Commented May 29, 2014 at 23:36

1 Answer 1


Here is my solution in C#, works good enough for my purposes:

///compute reasonably aligned pairs
        var max_tolerable_offset = 500; //do not match more then 500 miliseconds distant timestamps

        Dictionary<long, long> alignedPairs = new Dictionary<long, long>();

        foreach(var s in s_timestamps)
            //for every timestamp in first timeline find the nearest one from r
            var nearest_r = r_timestamps.OrderBy(r => Math.Abs(r - s)).First(); 

            //if that is closer than allowed offset
            if ((Math.Abs(nearest_r - s)) <= max_tolerable_offset * 10000)
                //so now I need to find nearest s mark for this r mark
                var closest_s = s_timestamps.OrderBy(s=> Math.Abs(s- nearest_r )).First();

                //if they are mutually in love, marry them
                if (closest_s == s)
                    alignedPairs.Add(s, nearest_r);

matched pairs

  • do you actually need the max offset if you are going to check both forward and backward nearest neighbours match? also this misses returning the non matched items as in the question
    – jk.
    Commented Oct 27, 2014 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.