2

I have 2 sequences:

  • One is a videoclip with the image taken by a drone's camera
  • The other is a file with a list of chronological data from the sensors

Example:

time 0: speed_x=1, latitude=0.001, longitude=0.2, altitude=40 
time 112: speed_x=3, latitude=0.0021, longitude=0.221, altitude=30 
time 232: speed_x=3, latitude=0.0021, longitude=0.221, altitude=35 
time 425: speed_x=3.1, latitude=0.0024, longitude=0.222, altitude=40 
…

*time comes in milliseconds

I have created an application that plays the video (that's the easy part) but I want to display information about the flight at a given position of the video.

The problem is that, in order to display the sensor data at a given position of the video (at a given time), I would have to traverse the list of sensor data in order to find the sensor data that is closer to that position

For example:

If the video is showing the frame at 150 milliseconds, and in the list of sensor data I have these items in the list of the sensor data:

time 0:
time 90: …
time 120: …
time 200: …
time 230: …

Then, I should choose to show the sensor data at the item with time=120, because it's the one that is closer to 150 ms.

I can do a lookup algorithm to do the lookup, but I will be really inefficient to traverse the whole list of data from the sensors calculating distances and choosing the one with the minimum distance.

So, I thought about creating some kind of dictionary/hash table that, given a position in the video, it would retrieve the appropriate sensor data.

However, I have never created suck lookup data structure. I don't even know it it's feasible! I have used dictionaries and hash tables that given a discrete key, a result is obtained. But in my case, I have a virtually infinite set of values that will result in the same item.

Can you, please, tell me how to solve this problem?

Thanks!

  • This looks like it is at the complexity-level of at least a Master's Plan B [U.S.] project, if not more intricate. – JosephDoggie Oct 8 '18 at 20:56
2

If you would create a hash table, you'd need to have an entry for every possible video time code.

But you can certainly use a sorted map. You need to search for the time code and if there's no exact match, take the element before.

In C++ you could for example use an std::map, use lower_bound() to get an iterator to the first element not smaller than the time code. If it doesn't correspond exactly, just decrement the iterator.

In Java, you would for example use a TreeMap and use floorEnry() to get the first element smaller or equal than the timecode you're looking for.

1

The lookup algorithm you are looking for is called binary search, which is quite efficient.

Note when playing the video you will typically have to check the time index of the next frame repeatedly, in increasing order. So once you have done an initial lookup, finding an index i in your sensor data list for a time index t, the next lookup for t+t0 (where t0 is the time interval between two frames) can be efficiently done by subsequently checking data records i, i+1, i+2, ... , and take the nearest one (stopping when the time distance from t+t0 starts to increase). Assumed the time intervals between records in your sensor data list is not much smaller than t0, this search will end after one or two steps (if the interval is guaranteed to be bigger than t0, one can stop the search at i+1).

If you expect random positioning in your video (and so the need for random lookup in your data records) to happen seldom, and playing forward as the standard use case, it may turn out you don't even need the binary search. Don't optimize something if you don't need to.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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