Revision history [back]

Hi Dave,

You're correct - the ROS vocabulary tree computes distances to every document in the database when you a query. Fortunately quantizing features into words makes each individual distance computation quite fast, and for the sort of place recognition tasks (only 100s of documents) we've done with vocabulary_tree the performance is fine. For scaling to much larger databases, using the inverted files to try only relevant documents probably is a big win.

Improving vocabulary_tree isn't on my critical path at the moment, but if you're interested in contributing I'm happy to answer questions about the code and apply patches. I think this optimization is not too complicated - Database::find() just needs to be updated to do something like:

• Look at the InvertedFile for each word in the query document
• Build a std::set containing the DocId's from all the inverted files.
• Only compute distances to those documents.

I'd be very interested to see a performance comparison for a suitably large dataset.