search

vioshyvo / mrpt

Fast and lightweight header-only C++ library (with Python bindings) for approximate nearest neighbor search
MIT License
257 stars 47 forks source link

Out-of-bounds access with certain parameter combinations #9

Closed rhiestan closed 5 years ago

rhiestan commented 6 years ago

Hi, I am trying to use MRPT in a structure-from-motion context, with LIOP keypoint descriptors (144 floats). With most parameters MRPT works very well, but with some it crashes with out-of-bounds access in Eigen Vectors. One example is with n_trees=5, depth=13, sparsity=0.088 (taken from the mrpt-comparison for sift), where MRPT crashes with the call stack:

>   Regard3D.exe!Eigen::DenseCoeffsBase<Eigen::Matrix<int,-1,1,0,-1,1>,1>::operator()(__int64 index) Line 425   C++
    Regard3D.exe!Mrpt::grow_subtree(const Eigen::Matrix<int,-1,1,0,-1,1> & indices, int tree_level, int i, int n_tree, const Eigen::Matrix<float,-1,-1,0,-1,-1> & tree_projections) Line 324    C++
    Regard3D.exe!Mrpt::grow_subtree(const Eigen::Matrix<int,-1,1,0,-1,1> & indices, int tree_level, int i, int n_tree, const Eigen::Matrix<float,-1,-1,0,-1,-1> & tree_projections) Line 340    C++
...
the same for several levels of recursion
...

    Regard3D.exe!Mrpt::grow_subtree(const Eigen::Matrix<int,-1,1,0,-1,1> & indices, int tree_level, int i, int n_tree, const Eigen::Matrix<float,-1,-1,0,-1,-1> & tree_projections) Line 339    C++
    Regard3D.exe!Mrpt::grow$omp$1() Line 68 C++

The VectorXf is of size 1, and MRPT tries to access it with index 1.

I am using Visual Studio 2015 on Windows 7, compiling for x64.

My question: Is this a bug, or are certain combinations of the parameters not allowed? If it is the latter, which combinations are allowed and which are not?

vioshyvo commented 6 years ago

Hi Roman, what is your data set size? I guess this might be because if the data set size is less than 2^13 (?), then it will try to split further even though there is only one point left at the branch, and the error is because of this.

Maybe we should make it check automatically that the given depth is not too deep for the data set size.

rhiestan commented 6 years ago

Thanks for your response. I wasn't aware that the depth parameter is related to the data set size. But in retrospect, it make complete sense :-) In my tests the data set size is around 14'000, while 2^13 is 8192. So it's at least close. I agree, a check would be good!