C++ efficient way to find matches between two std::map

Question

I have a data-set acquired with an RGB-D camera and a text file where for each image of the data-set, the timestamps and the filenames are stored. What I do is to parse this file and fill up two std::map, one for rgb images and the other for depth images. Now, since the timestamps don't intersect, I have to write a routine that finds matching images based on the timestamps. This is what I wrote so far:

typedef map<double,string> StampImageMap;

...

vector<string> &vstrImageFilenamesRGB;
vector<string> &vstrImageFilenamesD;
vector<double> &vTimestampsRGB;
vector<double> &vTimestampsDPT;

double tolerance = 0.02;

for(StampImageMap::iterator it=rgb_images.begin(); it != rgb_images.end(); it++) {
        bool found = false;
        StampImageMap::iterator jt=depth_images.begin();
        while(found == false && jt!=depth_images.end()) {
            if(fabs(it->first - jt->first) < tolerance) {
                found = true;
                vstrImageFilenamesRGB.push_back(it->second);
                vstrImageFilenamesD.push_back(jt->second);
                vTimestampsRGB.push_back(it->first);
                vTimestampsDPT.push_back(jt->first);
            }
            jt++;
        }
    }

and I'm wondering if there's a more efficient way to perform this task!

Do you have a one to one relationship for the RGB and D time stamps? Do they follow a fixed rule, e.g. RGB time stamps are always smaller than D time stamps for the same image? — Darien Pardinas, Sep 13 '16 at 09:50
Yes the camera has a frame rate of 30Hz, so the corresponding RGB and DEPTH images cannot have the same timestamp (for obvious reasons) but the difference between them can't be bigger than 1/33s, that's why I set the variable tolerance. — Federico Nardi, Sep 13 '16 at 10:01
@FedericoNardi If the sequences are "complete" (no gaps in either) and one-to-one, can't you just find the oldest match and then pair them up in sequence? (That is, the first rgb image with the first depth image, the second with the second, and so on.) — molbdnilo, Sep 13 '16 at 10:10
@molbdnilo unfortunately, it's not the case. Some DEPTH images have not corresponding RGB image :( — Federico Nardi, Sep 13 '16 at 10:16
@FedericoNardi That's too bad. You don't need to keep searching through the depth images from the beginning though, since you can't find a match earlier than the last one. — molbdnilo, Sep 13 '16 at 10:26
(Please put clarifications (such as _elements from one set may have no corresponding element in the other_) in the question itself.) — greybeard, Sep 22 '16 at 10:39

score 2 · Accepted Answer · edited May 23 '17 at 10:27

As your code is now written, the complexity is Θ(n m), where n, m are the sizes of the sequences. There are at least two ways to improve this (the second is more efficient, but is more difficult to code).

In the body of the outer loop, don't loop over all elements in the second map via while(found == false && jt!=depth_images.end()). Instead, use std::map::lower_bound and std::map::upper_bound to search for it->first - tolerance and it->first + tolerance, respectively. Loop only between the results of these two calls.

So, the code becomes something like this:
```
for(StampImageMap::iterator it=rgb_images.begin(); it != rgb_images.end(); it++) {
    StampImageMap::const_iterator lower = depth_images.lower_bound(it->first - tolerance);
    StampImageMap::const_iterator upper = depth_images.lower_bound(it->first + tolerance);

    // Now just search between lower and upper.
}
```
This will reduce each iteration to Θ(log(m)) + p, where p is the size of this range.
Since the keys of the maps are sorted, you can modify a standard technique of finding the intersection of two sorted arrays to this case. This will reduce the running time to Θ(m + n). Note that the modification is a bit tricky, as you're not trying to find the intersection of exact elements, but rather the intersection of "close enough" elements.

Here is the pseudocode for this case:
```
 it = rgb_image.begin();
 jt = depth_image.begin();

 while(it != rgb_image.end() && jt != depth_image.end()) {
     if(fabs(it->first - jt->first) < tolerance) {
         // Match found!
         ++it;
         ++jt;
         continue;
     }

     if(it.first > jt.first + tolerance) {
         ++jt;
         continue;
     }

     ++it;
 }
```

You will need to create special comparator which will handle comparison within tolerance (trivial. already done in OP code) — it will not relly be transitive, but it will be for all values in maps and this is what important — and maybe special output iterator which will do what you need on assigment, then you can use standard library easily. — Revolver_Ocelot, Sep 13 '16 at 10:07
@Revolver_Ocelot Right, that is a good idea. However, if one has patience for the details, the second one has the lower complexity, and I'm not sure there's a standard library algorithm for that (your correct point about the comparison functor is true there too, though). — Ami Tavory, Sep 13 '16 at 10:09
Oh, I noticed that you cannot use set_intersection, because you need values from both maps. You can just loop through second map again later, but it will be slower (however still algorithmically better than O(nm)), so your solution is basically set_intersection, but handling both values at once. — Revolver_Ocelot, Sep 13 '16 at 10:17
@Revolver_Ocelot Exactly. I completely agree with your comment that both options would be more readable with a "tolerance" compare function, though - thanks! — Ami Tavory, Sep 13 '16 at 10:19

C++ efficient way to find matches between two std::map

1 Answers1