Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

ricogu
This post was updated on .
Dear all:
    I have implemented the matching of descriptors SHOT, Spin Images and PFH. I used Kdtree to search for the nearest neighbor to look for the matching point. The code works perfectly for SHOT and PFH and does not work for SI. Basically what happened is that Kdtree gives rubbish output (e.g. all point in query matchs one point in database).
    I also implemented a linear search (compare a point in query with every points in database). Given the same sets of descriptors, the result is ok. So the problem now is with the Kdtree. I tried to vary the parameter passed to kdtree but there are very little help. Please help me on this, thanks a lot!

Regards
Rico



            //Use SI descriptor
            typedef pcl::Histogram<153> SpinImage;

            //declare variables for Kd tree search
            pcl::KdTreeFLANN<SpinImage > kdtree;
            SpinImage searchFeature;


            //search for 2NN and check for ratio threshold
            int K = 2;
            std::vector<int> pointIdxNKNSearch(K);
            std::vector<float> pointNKNSquaredDistance(K);

            //initilization for kd-tree
            kdtree.setInputCloud(inputCloud);
            pointIdxNKNSearch.clear();
            pointNKNSquaredDistance.clear();


            //compare each query point with each scene point
            int numFoundMatches;
            for (int c = 0; c < src3DOR.descriptor_histograms_QuerySpinImages.size(); c++)
            {
                searchFeature = src3DOR.descriptor_histograms_QuerySpinImages.at(c);

                if(std::isnan(searchFeature.histogram[0]))
                    continue;

                numFoundMatches = kdtree.nearestKSearch(searchFeature,K,pointIdxNKNSearch,pointNKNSquaredDistance);

                if(numFoundMatches>0)
                {
                    temp_dist2NN = pointNKNSquaredDistance.at(0);
                    temp_dist2SecondNN = pointNKNSquaredDistance.at(1);

                }
          }


Reply | Threaded
Open this post in threaded view
|

[NOOB] cluster detection before RANSAC?

Claudio Carbone
Hello.
I'm quite new to pcl, and reading various tutorials to get a grasp on it.
I'm doing an applied master thesis, whose objective is to get a ground robot
to scout terrain (outdoor) and eventually RTB autonomously (not the NEXT BIG
THING OF THE CENTURY I know).
So I have a decent pre-existing knowledge in various fields, except that I
have never worked with 3D, and my sensors are 2D only too (sick/hokuyo
scanner).
But, as I understand, using many algorithms (like the RANSAC) in 2D isn't a
problem: just nullify Z (although this may pose a performance problem
depending on implementation, but I'll disregard that for the time being).

The question that is bulging in my brain is (forgive my lack of accurate
tech vocabulary, still learning that): RANSAC can help determine where
features lay inside point clouds, but a sensor sweep will surely (and
hopefully) include many features. So these many features should be
recognized and separated as distinct point clouds, to give then to the
RANSAC for analysis.
So what is the algorithm that does this cluster analysis?
Or at least what is this part of the process called?
So far all I've read has to do with all the other parts of the process but
this.

Also are there any papers/tutorials/idea/articles/blog posts detailing the
approach to integrate GPS in all of this?
I'm developing my own ideas, but it isn't plug&play so to speak.

Regards
Claudio Carbone

_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

Radu B. Rusu
Administrator
In reply to this post by ricogu
What are the SI vectors that you are passing to the tree? Are they 1D or 2D? Maybe we need a different metric for FLANN
for SI.

Cheers,
Radu.
--
http://openperception.org

On 10/08/2012 03:43 AM, ricogu wrote:

> Dear all:
>      I have implemented the matching of descriptors SHOT, Spin Images and
> PFH. I used Kdtree to search for the nearest neighbor to look for the
> matching point. The code works perfectly for SHOT and PFH and does not work
> for SI. Basically what happened is that Kdtree gives rubbish output (e.g.
> all point in query matchs one point in database).
>      I also implemented a linear search (compare a point in query with every
> points in database). Given the same sets of descriptors, the result is ok.
> So the problem now is with the Kdtree. I tried to vary the parameter passed
> to kdtree but there are very little help. Please help me on this, thanks a
> lot!
>
> Regards
> Rico
>
>
>
>   //Use SI descriptor
>              typedef pcl::Histogram<153> SpinImage;
>
>
>
> std::cout<<"CSearchMethod.cpp:matchQueryAgainstDatabase()_KDTree: Using SI
> descriptor\n";
>              std::cout<<"Query Size: "
> <<src3DOR.descriptor_histograms_QuerySpinImages.size()&lt;&lt;std::endl;
>              std::cout&lt;&lt;&quot;Database Size:
> &quot;&lt;&lt;src3DOR.descriptor_histograms_DatabaseSpinImages.size()&lt;&lt;std::endl;
>
>              //declare variables for Kd tree search
>              pcl::KdTreeFLANN&lt;SpinImage > kdtree;
>              pcl::PointCloud<SpinImage >::Ptr inputCloud (new
> pcl::PointCloud<SpinImage>);
>              SpinImage searchFeature;
>
>
>
>              //search for 2NN and check for ratio threshold
>              int K = 2;
>              std::vector<int> pointIdxNKNSearch(K);
>              std::vector<float> pointNKNSquaredDistance(K);
>
>
>              //clean storage vectors
>              dst3DOR.matchFlagVect.clear();
>              dst3DOR.pointCorelationIndexBetweenQueryAndScene.clear();
>
>
>              //create space for vector of match flag
>              for ( int a = 0; a <
> src3DOR.descriptor_histograms_QuerySpinImages.size(); a++)
>              {
>                  dst3DOR.matchFlagVect.push_back(false);
>
> dst3DOR.pointCorelationIndexBetweenQueryAndScene.push_back(-1);
>              }
>
>              //convert the descriptor vector to pointcloud structure
>              for ( int a = 0; a<
> src3DOR.descriptor_histograms_DatabaseSpinImages.size(); a++)
>              {
>                  SpinImage tempSIContext;
>                  tempSIContext =
> src3DOR.descriptor_histograms_DatabaseSpinImages.at(a);
>                  inputCloud->push_back(tempSIContext);
>              }
>
>              //initilization for kd-tree
>              kdtree.setInputCloud(inputCloud);
>              pointIdxNKNSearch.clear();
>              pointNKNSquaredDistance.clear();
>
>
>              //compare each query point with each scene point
>              int numFoundMatches;
>              for (int c = 0; c <
> src3DOR.descriptor_histograms_QuerySpinImages.size(); c++)
>              {
>                  searchFeature =
> src3DOR.descriptor_histograms_QuerySpinImages.at(c);
>
>                  if(std::isnan(searchFeature.histogram[0]))
>                      continue;
>
>                  numFoundMatches =
> kdtree.nearestKSearch(searchFeature,K,pointIdxNKNSearch,pointNKNSquaredDistance);
>
>                  if(numFoundMatches>0)
>                  {
>                      temp_dist2NN = pointNKNSquaredDistance.at(0);
>                      temp_dist2SecondNN = pointNKNSquaredDistance.at(1);
>
>                  }
>
>
>
>
>
>
> --
> View this message in context: http://www.pcl-users.org/Kdtree-Flann-have-problem-search-nearest-neighbor-for-Spin-Image-Descriptor-i-e-Histogram-153-tp4022815.html
> Sent from the Point Cloud Library (PCL) Users mailing list mailing list archive at Nabble.com.
> _______________________________________________
> [hidden email] / http://pointclouds.org
> http://pointclouds.org/mailman/listinfo/pcl-users
>
_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

ricogu
Dear Radu
    Thanks for the quick response. The SI descriptor i was passing to kdtree is Histogram<153>. I think it is a 1d vector.

Best
Rico
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

Marius Muja-2
Hi Rico,

Can you send me a minimal example that reproduces the problem? (Including the point cloud of SI descriptors you are using).

Also,  pcl::KdTreeFLANN wraps flann::KDTreeSingleIndex which is optimized for low dimensional exact search and is not ideal for 153 dimensional descriptors. For high dimensional points you should be using an approximate nearest neighbor index from FLANN, such as flann::KDTreeIndex or flann::KMeansIndex.

Cheers,
Marius


On Tue, Oct 9, 2012 at 1:11 AM, ricogu <[hidden email]> wrote:
Dear Radu
    Thanks for the quick response. The SI descriptor i was passing to kdtree
is Histogram<153>. I think it is a 1d vector.

Best
Rico



--
View this message in context: http://www.pcl-users.org/Kdtree-Flann-have-problem-search-nearest-neighbor-for-Spin-Image-Descriptor-i-e-Histogram-153-tp4022815p4022844.html
Sent from the Point Cloud Library (PCL) Users mailing list mailing list archive at Nabble.com.
_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users


_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

ricogu
Dear Marius
    Thanks so much for the reply.I am so sorry for replying so late, I was working on other stuffs earlier.
As suggested by you, I am trying to save the SI descriptor into a pcd file and upload. However, it seems that pcl::io::savePCDFileBinary report compilation error if the input pointcloud is Histogram <153>

here is the error message:
In file included from /usr/include/pcl-1.6/pcl/ros/register_point_struct.h:43:0,
                 from /usr/include/pcl-1.6/pcl/point_types.h:46,
                 from /home/rico/CoopMedia3D/search/src/../include/../../types/include/types_3DOR.h:48,
                 from /home/rico/CoopMedia3D/search/src/../include/CSearchMethod.h:11,
                 from /home/rico/CoopMedia3D/search/src/CSearchMethod.cpp:8:
/usr/include/pcl-1.6/pcl/point_traits.h: At global scope:
/usr/include/pcl-1.6/pcl/point_traits.h: In instantiation of ‘pcl::traits::fieldList<pcl::Histogram<153> >’:
/usr/include/pcl-1.6/pcl/common/impl/io.hpp:80:3:   instantiated from ‘void pcl::getFields(const pcl::PointCloud<PointT>&, std::vector<sensor_msgs::PointField>&) [with PointT = pcl::Histogram<153>]’
/usr/include/pcl-1.6/pcl/io/impl/pcd_io.hpp:160:3:   instantiated from ‘int pcl::PCDWriter::writeBinary(const string&, const pcl::PointCloud<PointT>&) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/usr/include/pcl-1.6/pcl/io/pcd_io.h:545:57:   instantiated from ‘int pcl::PCDWriter::write(const string&, const pcl::PointCloud<PointT>&, bool) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/usr/include/pcl-1.6/pcl/io/pcd_io.h:723:55:   instantiated from ‘int pcl::io::savePCDFileBinary(const string&, const pcl::PointCloud<PointT>&) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/home/rico/CoopMedia3D/search/src/CSearchMethod.cpp:519:71:   instantiated from here
/usr/include/pcl-1.6/pcl/point_traits.h:161:12: error: invalid use of incomplete type ‘struct pcl::traits::fieldList<pcl::Histogram<153> >’
/usr/include/pcl-1.6/pcl/point_traits.h:161:12: error: declaration of ‘struct pcl::traits::fieldList<pcl::Histogram<153> >’
/usr/include/pcl-1.6/pcl/point_traits.h: In instantiation of ‘pcl::traits::fieldList<pcl::Histogram<153> >’:
/usr/include/pcl-1.6/pcl/common/impl/io.hpp:80:3:   instantiated from ‘void pcl::getFields(const pcl::PointCloud<PointT>&, std::vector<sensor_msgs::PointField>&) [with PointT = pcl::Histogram<153>]’
/usr/include/pcl-1.6/pcl/io/impl/pcd_io.hpp:160:3:   instantiated from ‘int pcl::PCDWriter::writeBinary(const string&, const pcl::PointCloud<PointT>&) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/usr/include/pcl-1.6/pcl/io/pcd_io.h:545:57:   instantiated from ‘int pcl::PCDWriter::write(const string&, const pcl::PointCloud<PointT>&, bool) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/usr/include/pcl-1.6/pcl/io/pcd_io.h:723:55:   instantiated from ‘int pcl::io::savePCDFileBinary(const string&, const pcl::PointCloud<PointT>&) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/home/rico/CoopMedia3D/search/src/CSearchMethod.cpp:519:71:   instantiated from here
/usr/include/pcl-1.6/pcl/point_traits.h:167:7: error: no matching function for call to ‘assertion_failed(mpl_::failed************ (pcl::traits::fieldList<pcl::Histogram<153> >::POINT_TYPE_NOT_PROPERLY_REGISTERED::************)(pcl::Histogram<153>&))’
/usr/include/pcl-1.6/pcl/point_traits.h:167:7: note: candidate is:
/usr/include/boost/mpl/assert.hpp:79:5: note: template<bool C> int mpl_::assertion_failed(typename mpl_::assert<C>::type)
In file included from /usr/include/pcl-1.6/pcl/common/io.h:458:0,
                 from /usr/include/pcl-1.6/pcl/search/search.h:44,
                 from /usr/include/pcl-1.6/pcl/features/feature.h:51,
                 from /usr/include/pcl-1.6/pcl/features/3dsc.h:44,
                 from /home/rico/CoopMedia3D/search/src/../include/../../types/include/types_3DOR.h:49,
                 from /home/rico/CoopMedia3D/search/src/../include/CSearchMethod.h:11,
                 from /home/rico/CoopMedia3D/search/src/CSearchMethod.cpp:8:
/usr/include/pcl-1.6/pcl/common/impl/io.hpp: In function ‘void pcl::getFields(const pcl::PointCloud<PointT>&, std::vector<sensor_msgs::PointField>&) [with PointT = pcl::Histogram<153>]’:
/usr/include/pcl-1.6/pcl/io/impl/pcd_io.hpp:160:3:   instantiated from ‘int pcl::PCDWriter::writeBinary(const string&, const pcl::PointCloud<PointT>&) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/usr/include/pcl-1.6/pcl/io/pcd_io.h:545:57:   instantiated from ‘int pcl::PCDWriter::write(const string&, const pcl::PointCloud<PointT>&, bool) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/usr/include/pcl-1.6/pcl/io/pcd_io.h:723:55:   instantiated from ‘int pcl::io::savePCDFileBinary(const string&, const pcl::PointCloud<PointT>&) [with PointT = pcl::Histogram<153>, std::string = std::basic_string<char>]’
/home/rico/CoopMedia3D/search/src/CSearchMethod.cpp:519:71:   instantiated from here
/usr/include/pcl-1.6/pcl/common/impl/io.hpp:80:3: error: no type named ‘type’ in ‘struct pcl::traits::fieldList<pcl::Histogram<153> >’
make[2]: *** [CMakeFiles/coopmedia3d.dir/search/src/CSearchMethod.cpp.o] Error 1
make[1]: *** [CMakeFiles/coopmedia3d.dir/all] Error 2
make: *** [all] Error 2

Thanks again

Best
Rico
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

ricogu
In reply to this post by Marius Muja-2
kdtree_search.cpp
m300.pcd

The problem is re-produced in attached simple program, I extracted descriptor from a face model and compare the same descriptor with itself. The expected output is point o matches point 0, point 1 matches point 1 and so on.

However, the result here looks wired,:point 0 in query matches point 874 in database.
point 1 in query matches point 874 in database.
point 2 in query matches point 874 in database.
point 3 in query matches point 874 in database.
point 4 in query matches point 874 in database.
point 5 in query matches point 874 in database.
point 6 in query matches point 874 in database.
point 7 in query matches point 874 in database.
point 8 in query matches point 874 in database.
point 9 in query matches point 874 in database.
...

Basically Kdtree tells me all points matches point 874.

Could you look into this? You help is much appreciated!

Regards
Rico
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

Marius Muja-2
Hi Rico,

Thanks, I'll have a look into this.

Marius

On Mon, Oct 22, 2012 at 9:13 AM, ricogu <[hidden email]> wrote:
kdtree_search.cpp <http://www.pcl-users.org/file/n4023213/kdtree_search.cpp>
m300.pcd <http://www.pcl-users.org/file/n4023213/m300.pcd>

The problem is re-produced in attached simple program, I extracted
descriptor from a face model and compare the same descriptor with itself.
The expected output is point o matches point 0, point 1 matches point 1 and
so on.

However, the result here looks wired,:point 0 in query matches point 874 in
database.
point 1 in query matches point 874 in database.
point 2 in query matches point 874 in database.
point 3 in query matches point 874 in database.
point 4 in query matches point 874 in database.
point 5 in query matches point 874 in database.
point 6 in query matches point 874 in database.
point 7 in query matches point 874 in database.
point 8 in query matches point 874 in database.
point 9 in query matches point 874 in database.
...

Basically Kdtree tells me all points matches point 874.

Could you look into this? You help is much appreciated!

Regards
Rico



--
View this message in context: http://www.pcl-users.org/Kdtree-Flann-have-problem-search-nearest-neighbor-for-Spin-Image-Descriptor-i-e-Histogram-153-tp4022815p4023213.html
Sent from the Point Cloud Library (PCL) Users mailing list mailing list archive at Nabble.com.
_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users


_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

Marius Muja-2
Hi Rico,

The behavior you experienced is because when PCL transforms a point cloud into a matrix data structure used by FLANN, does so with the help of a PointRepresentation class and by default this class uses only the first 3 floats of each point unless a specialization for the new data type is provided.

You can get the expected behavior for your code by adding the following specialization for DefaultPointRepresentation:

namespace pcl {
template <>
class DefaultPointRepresentation<SpinImage> : public PointRepresentation<SpinImage>
{
public:
  DefaultPointRepresentation ()
  {
    nr_dimensions_ = 153;
  }

  virtual void
  copyToFloatArray (const SpinImage &p, float * out) const
  {
    for (int i = 0; i < nr_dimensions_; ++i)
      out[i] = p.histogram[i];
  }
};
}


As I mentioned before, using pcl::KdTreeFLANN for matching 153 dimensional points is not ideal, because pcl::KdTreeFLANN performs exact search using a single kd-tree which is not efficient for high dimensional features. You would get much better performance by using one of the approximate matching methods in FLANN, such as the randomized kdtree forest (flann::KDTreeIndex) or the hierachical k-means tree (flann::KMeansIndex).

Marius


On Mon, Oct 22, 2012 at 11:45 PM, Marius Muja <[hidden email]> wrote:
Hi Rico,

Thanks, I'll have a look into this.

Marius


On Mon, Oct 22, 2012 at 9:13 AM, ricogu <[hidden email]> wrote:
kdtree_search.cpp <http://www.pcl-users.org/file/n4023213/kdtree_search.cpp>
m300.pcd <http://www.pcl-users.org/file/n4023213/m300.pcd>

The problem is re-produced in attached simple program, I extracted
descriptor from a face model and compare the same descriptor with itself.
The expected output is point o matches point 0, point 1 matches point 1 and
so on.

However, the result here looks wired,:point 0 in query matches point 874 in
database.
point 1 in query matches point 874 in database.
point 2 in query matches point 874 in database.
point 3 in query matches point 874 in database.
point 4 in query matches point 874 in database.
point 5 in query matches point 874 in database.
point 6 in query matches point 874 in database.
point 7 in query matches point 874 in database.
point 8 in query matches point 874 in database.
point 9 in query matches point 874 in database.
...

Basically Kdtree tells me all points matches point 874.

Could you look into this? You help is much appreciated!

Regards
Rico



--
View this message in context: http://www.pcl-users.org/Kdtree-Flann-have-problem-search-nearest-neighbor-for-Spin-Image-Descriptor-i-e-Histogram-153-tp4022815p4023213.html
Sent from the Point Cloud Library (PCL) Users mailing list mailing list archive at Nabble.com.
_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users



_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

ricogu
Hi Marius
   It is working perfectly now. Many thanks to your help!
   The approximate nearest neighbor search is on the to-do List:)

Rico
Reply | Threaded
Open this post in threaded view
|

Re: Kdtree Flann have problem search nearest neighbor for Spin Image Descriptor (i.e. Histogram<153>)

M rezaei
Hi
I have the same problem for my point type and histogram type too and i
didn't understand your responses please guide me about that.
thanks



--
Sent from: http://www.pcl-users.org/
_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users