Algorithm to match timestamped events from two sources

Question

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.

• Robert Harvey: 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."

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

• jk.: 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