Hidden bug in feature tracks building

[greenlet]

https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/tracks.hpp#L133-L136

It seems index k cannot be used in method Find here. Possible fix:

 for (uint32_t k = 0; k < map_node_to_index.size(); ++k) 
 { 
   const auto & feat = map_node_to_index[k]; 
   const uint32_t & track_id = uf_tree.Find(feat.second); 

The reason it all works is that earlier in Build method ordered set is used: https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/tracks.hpp#L74 which is copied to map_node_to_index. And sorting later https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/tracks.hpp#L100 doesn't change flat index order, so it corresponds to k

[pmoulon]

Hello @greenlet, Thank you for your feedback. What do you mean by a hidden bug, the code is working as expected...

By using find we actually retrieve in which SET the feature k has been added.

It seems index k cannot be used in method Find here. Please elaborate since the code is working as it is.

[greenlet]

    for (const auto & feat : allFeatures)
    {
      map_node_to_index.emplace_back(feat, cpt);
      ++cpt;
    }
    // Sort the flat_pair_map
    map_node_to_index.sort();
    // Clean some memory
    allFeatures.clear();```

Shouldn't you use this `cpt` that could be resorted later for `uf_tree.Find(...)`?

Consider the case where `allFeatures` is `unordered_set`

[rperrot]

Hi @greenlet,

thanks for your support, regarding your first remarks (potential bug with index k), we feel sorry but we don't understand well where is the issue.

Could you please explain again (maybe on an example ?) what is exactly the issue, for you, regarding this code ?

[greenlet]

For now there is no bug, but some manipulations tell us that it is coincidence, that there's no bug

1. There is a container for Feature-to-Index matching: flat_pair_map<indexedFeaturePair, uint32_t> map_node_to_index; wich is basically a vector of Feature-Index pairs: https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/flat_pair_map.hpp#L50 Lets denote k - index of flat_pair_map vector and Index - second value in the pair Feature-Index

2. Container is filled with Feature-Index pairs sequentially: https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/tracks.hpp#L94-L98 At this point k corresponds to Index

3. Next step is sorting it by Feature: https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/tracks.hpp#L100 https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/flat_pair_map.hpp#L35 https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/flat_pair_map.hpp#L52

From this point I assume that orders of k and Index could differ (In the current implementation they don't differ actually, but this is another question)

4. Index later is used to join Features into tracks https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/tracks.hpp#L118

5. k later is used to get access to tracks, for example, in Filter https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/tracks.hpp#L133-L136

So, for now there's no bug actually because map_node_to_index is filled sequentially from allFeatures https://github.com/openMVG/openMVG/blob/0cbb7ee342571b921194d13b9d574d58d2c1a43b/src/openMVG/tracks/tracks.hpp#L74 which is already an ordered std::set. If that was made intentionally, why do you use vector of Feature-Index pairs, why not just to use vector of Feature elements? Also why to put map_node_to_index.sort();

[pmoulon]

Thank you for your detailed explanation. Appreciated.

Our algorithm is a direct translation of this paper https://hal-enpc.archives-ouvertes.fr/hal-00769267/file/moulon_monasse_poster_CVMP12.pdf Each feature set is identified as a singleton, that's why we have an index for each feature.

I agree that every open-source algorithm could be made clearer and I respect your willingness to say that we have an opportunity here.

Feel free to modify some code (see if we can use a set) and make a Pull Request to help us make our algorithm more readable and perhaps more optimized if you see something. You can compare speed and see if you can make it faster.

Nit: As you can see our flat_map is already a vector.

[greenlet]

I feel like it is not clear what I wanted to explain In my last comment potential problem can be seen from steps 4 and 5. Index and k values in map_to_node_index are used interchangeably. But Index is contained into the map_to_node_index vector items (second value of the pair) and k is just an index from 0 to map_to_node_index.size() - 1. So after the the operation map_to_node_index.sort() which uses the order implied by the first values of pairs - we potentialy might have: Befor sorting: (k, Index) are in { (0, 0), (1, 1), (2,2) } After sorting: (k, Index) are in { (0, 1), (1, 0), (2, 2) }

Maybe it will be just easier to make pull request with some refinements here)

[pmoulon]

sort is preserving the pairs.

Please, use pull request and we can iterate here and we can also simulate case in unit test ;-)