Federico Nardi Federico Nardi - 2 months ago 7
C++ Question

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

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!

Answer

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;
     }
    
Comments