SHOT is faster than it is supposed to be: or is it normal?

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

SHOT is faster than it is supposed to be: or is it normal?

berker
This post has NOT been accepted by the mailing list yet.
I am working on descriptors for a while. I am extracting and testing them on the RGB-D (washington dataset).

In my tests, SHOT descriptors performs really well.

So far so good.

But according to my tests, I am extracting them 10 times faster than FPFH with the same support radius, which according to literature impossible (is it???). I am not using the openMP version in the code (but I don't know if I have build pcl with OpenMP support and if it automatically uses that version).

Also since I got sensible output and very good performance results, I could not figure out the problem.

What is your experience with SHOT vs FPFH in terms of extraction time?

                                pcl::NormalEstimation<pcl::PointXYZRGB, pcl::Normal> ne;
                                ne.setInputCloud (cloud);
                                ne.setSearchMethod (tree);
                                ne.setRadiusSearch (0.01);
                                ne.compute (*cloud_normals);


                                pcl::SHOTEstimation<pcl::PointXYZRGB, pcl::Normal, pcl::SHOT352> shot;
                                pcl::PointCloud<pcl::SHOT352>::Ptr shot_signature (new pcl::PointCloud<pcl::SHOT352> ());
                                shot.setSearchMethod(tree);
                                shot.setInputNormals(cloud_normals);
                                shot.setRadiusSearch(0.05);
                                shot.setSearchSurface(cloud);

                                if(KeypointsType == 1){
                                        shot.setInputCloud(keypoints_xyzrgb);
                                        shot.compute(*shot_signature);

                                       
                                }
                                else if(KeypointsType == 2){
                                        shot.setInputCloud(keypoints_xyzrgb);
                                        shot.compute(*shot_signature);

                                       
                                }
                                else{
                                        shot.setInputCloud(sampled_cloud);
                                        shot.compute(*shot_signature);
                                       
                                }
Middle East Technical University
Reply | Threaded
Open this post in threaded view
|

Re: SHOT is faster than it is supposed to be: or is it normal?

Ber461
I ran a simple test. For the same cloud, and the same support size, FPFH took almost 11.5 seconds to compute, and SHOT took 7.2 or so. But 10 times faster? That indeed sounds odd.

I don't think this has to do with the use of OpenMP, because you would need to do that explicitly, using a different class (SHOTEstimationOMP).

But, if you are getting valid results, then just... rejoice.
Reply | Threaded
Open this post in threaded view
|

Re: SHOT is faster than it is supposed to be: or is it normal?

andersgb1
FPFH has an effective radius of 2*r, where r is your specified support radius. This makes it slow, slow.

On Tue, Jan 6, 2015 at 11:34 PM, Ber461 <[hidden email]> wrote:
I ran a simple test. For the same cloud, and the same support size, FPFH took
almost 11.5 seconds to compute, and SHOT took 7.2 or so. But 10 times
faster? That indeed sounds odd.

I don't think this has to do with the use of OpenMP, because you would need
to do that explicitly, using a different class (SHOTEstimationOMP).

But, if you are getting valid results, then just... rejoice.



--
View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036781.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: SHOT is faster than it is supposed to be: or is it normal?

Radu B. Rusu
Administrator
Fede, do you remember what support SHOT is using? I don’t from the top of my head.

Berker, it might have to do with the underlying search mechanism used. I wonder if the kdtree / search is the problem here, or maybe there’s something wrong with your cloud. Do you have points with the same XYZ coordinates by any chances? (duplicates)

The difference between FPFH and SHOT should be more along the lines of what Ber461 noticed, so there’s clearly something going wrong here.

Best,
Radu.

> On Jan 6, 2015, at 10:10 PM, Anders Glent Buch <[hidden email]> wrote:
>
> FPFH has an effective radius of 2*r, where r is your specified support radius. This makes it slow, slow.
>
> On Tue, Jan 6, 2015 at 11:34 PM, Ber461 <[hidden email]> wrote:
> I ran a simple test. For the same cloud, and the same support size, FPFH took
> almost 11.5 seconds to compute, and SHOT took 7.2 or so. But 10 times
> faster? That indeed sounds odd.
>
> I don't think this has to do with the use of OpenMP, because you would need
> to do that explicitly, using a different class (SHOTEstimationOMP).
>
> But, if you are getting valid results, then just... rejoice.
>
>
>
> --
> View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036781.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

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

Re: SHOT is faster than it is supposed to be: or is it normal?

berker
This post has NOT been accepted by the mailing list yet.
Thanks for answers.

Important Note: I am working on a new descriptor based on FPFH. I am trying to make it faster and better. And if I have success, I want to add it to PCL and share with community :)

So timing is also a serious concern for me.

1 -
Radu:
I am exactly using the same tree (KdTree), same normals and same keypoints; downsampling, ISS3D, Harris3D .
I am testing not in a single cloud but a part of the dataset. So there is nothing specific to a cloud.


Can anyone test the speeds of FPFH and SHOT from a sample in Washington RGB-D dataset (segmented, for example: rgbd-dataset/binder/binder_1/binder_1_2_101.pcd)

normal search radius: 0.01
support_radius: 0.05 or 0.10


2 - I am also getting  bad performance results if I use FLANN for matching SHOT descriptors but very good results if I use BRUTEFORCE.  This is not the case for other descriptors. Flann and bruteforce gives very close results.   Is this normal? If so, do you know the cause?

Thanks.
Middle East Technical University
Reply | Threaded
Open this post in threaded view
|

Re: SHOT is faster than it is supposed to be: or is it normal?

andersgb1
In reply to this post by Radu B. Rusu
Hi Radu, Fede,

I'm quite interested in this discussion, because I am currently doing paper work, which also tests descriptor efficiencies, among others SHOT and FPFH. I am not getting a linear complexity with linearly increasing number of neighbors for FPFH (which is the case for SHOT and the others). This is supported by Federico and others' latest SHOT publication in CVIU: "SHOT: Unique signatures of histograms for surface and texture description", see Fig. 9. I know this figure does not necessarily use linearly increasing number of neighbors, but I did that and got similar superlinear complexity for FPFH.

Radu, can you figure out what is going on here? Is FPFH really not linear?

-Anders

On Wed, Jan 7, 2015 at 7:18 AM, Radu B. Rusu <[hidden email]> wrote:
Fede, do you remember what support SHOT is using? I don’t from the top of my head.

Berker, it might have to do with the underlying search mechanism used. I wonder if the kdtree / search is the problem here, or maybe there’s something wrong with your cloud. Do you have points with the same XYZ coordinates by any chances? (duplicates)

The difference between FPFH and SHOT should be more along the lines of what Ber461 noticed, so there’s clearly something going wrong here.

Best,
Radu.

> On Jan 6, 2015, at 10:10 PM, Anders Glent Buch <[hidden email]> wrote:
>
> FPFH has an effective radius of 2*r, where r is your specified support radius. This makes it slow, slow.
>
> On Tue, Jan 6, 2015 at 11:34 PM, Ber461 <[hidden email]> wrote:
> I ran a simple test. For the same cloud, and the same support size, FPFH took
> almost 11.5 seconds to compute, and SHOT took 7.2 or so. But 10 times
> faster? That indeed sounds odd.
>
> I don't think this has to do with the use of OpenMP, because you would need
> to do that explicitly, using a different class (SHOTEstimationOMP).
>
> But, if you are getting valid results, then just... rejoice.
>
>
>
> --
> View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036781.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

_______________________________________________
[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: SHOT is faster than it is supposed to be: or is it normal?

fedassa
Hi,

if you look at Fig. 9 of our SHOT journal paper (“SHOT: Unique Signatures of Histograms for Surface and Texture Description”, CVIU), you can clearly see that the computational complexity of SHOT wrt. the support radius is linear, while that of FPFH is not. This means that, when not using very small support sizes, the difference in time is already one order of magnitude (or more). E.g., if you check the operating points of the parameters we tuned for our dataset (shown by the filled red dot), the difference in computational time is already one oom.
As for FPFH, this is probably due to the fact that FPFH computes the SPFH of each point in the neighborhood defined by the support size, and each SPFH has a sub-linear complexity itself, and this should be enough to yield a non linear complexity, as well as to increase the effective support radius of FPFH. But Radu can definitely tell us more about this.

As for the last mentioned point (FLANN giving bad matches for SHOT wrt. Brute Force), this is indeed quite strange and would be worth more investigation.

Fede
Reply | Threaded
Open this post in threaded view
|

Re: SHOT is faster than it is supposed to be: or is it normal?

berker
This post has NOT been accepted by the mailing list yet.
This post was updated on .
Hi. I guess you are Federico Tombari.

Thanks for great work and contributions to the community! :)

My results are completely parallel with what you state. In the RGB-D dataset, SHOT scales linearly with increasing support radius. And FPFH not. But that's obvious, because, as the radius increase, points increase much more than linear. No problem here.

So that's what makes SHOT great if you need to use large support radius!

But even in relatively small radius (5 cm , 10 cm), it is still much faster than FPFH in my tests in RGB-D dataset (washington)

Federico, can you confirm this?  

For example, in Luis Alexandre's 2012 IROS paper "3D Descriptors for Object and Category Recognition: a Comparative
Evaluation" in Table 3, SHOT is only slightly faster than FPFH, but I don't know what support radius he used. So I cannot confirm his or my results.

For the second case, since as the owner of SHOT, you cannot confirm SHOT's FLANN dislike (in my case) :) maybe I am doing something wrong here :(

Your (everyone's) help is greatly appreciated .

Thanks.

Berker.
Middle East Technical University
Reply | Threaded
Open this post in threaded view
|

Re: SHOT is faster than it is supposed to be: or is it normal?

Radu B. Rusu
Administrator
In reply to this post by fedassa
Anders, I believe Federico’s analysis is correct.

(Thanks Fede! :) )

Best,
Radu.

> On Jan 7, 2015, at 1:22 AM, fedassa <[hidden email]> wrote:
>
> Hi,
>
> if you look at Fig. 9 of our SHOT journal paper (“SHOT: Unique Signatures of
> Histograms for Surface and Texture Description”, CVIU), you can clearly see
> that the computational complexity of SHOT wrt. the support radius is linear,
> while that of FPFH is not. This means that, when not using very small
> support sizes, the difference in time is already one order of magnitude (or
> more). E.g., if you check the operating points of the parameters we tuned
> for our dataset (shown by the filled red dot), the difference in
> computational time is already one oom.
> As for FPFH, this is probably due to the fact that FPFH computes the SPFH of
> each point in the neighborhood defined by the support size, and each SPFH
> has a sub-linear complexity itself, and this should be enough to yield a non
> linear complexity, as well as to increase the effective support radius of
> FPFH. But Radu can definitely tell us more about this.
>
> As for the last mentioned point (FLANN giving bad matches for SHOT wrt.
> Brute Force), this is indeed quite strange and would be worth more
> investigation.
>
> Fede
>
>
>
> --
> View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036789.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: SHOT is faster than it is supposed to be: or is it normal?

andersgb1
Sorry, Fede, Radu, I don't get that.

Radu, your (very nice btw.) paper on FPFH clearly argues why it should be linear: one linear sweep for the SPFHs, followed by one linear sweep of weighted summation of SPFHs.

Fede, you now mention sub-linear complexity, but it's clearly superlinear in the plots? What did you mean?

Sorry for being pedantic here, but I really don't get why FPFH is superlinear when it's just two linear sweeps. What am I missing from Fede's clarification?

On Wed, Jan 7, 2015 at 6:15 PM, Radu B. Rusu <[hidden email]> wrote:
Anders, I believe Federico’s analysis is correct.

(Thanks Fede! :) )

Best,
Radu.

> On Jan 7, 2015, at 1:22 AM, fedassa <[hidden email]> wrote:
>
> Hi,
>
> if you look at Fig. 9 of our SHOT journal paper (“SHOT: Unique Signatures of
> Histograms for Surface and Texture Description”, CVIU), you can clearly see
> that the computational complexity of SHOT wrt. the support radius is linear,
> while that of FPFH is not. This means that, when not using very small
> support sizes, the difference in time is already one order of magnitude (or
> more). E.g., if you check the operating points of the parameters we tuned
> for our dataset (shown by the filled red dot), the difference in
> computational time is already one oom.
> As for FPFH, this is probably due to the fact that FPFH computes the SPFH of
> each point in the neighborhood defined by the support size, and each SPFH
> has a sub-linear complexity itself, and this should be enough to yield a non
> linear complexity, as well as to increase the effective support radius of
> FPFH. But Radu can definitely tell us more about this.
>
> As for the last mentioned point (FLANN giving bad matches for SHOT wrt.
> Brute Force), this is indeed quite strange and would be worth more
> investigation.
>
> Fede
>
>
>
> --
> View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036789.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


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

Re: SHOT is faster than it is supposed to be: or is it normal?

Radu B. Rusu
Administrator
Anders,

You’re right - it is 2 linear sweeps. I need to look over the implementation to see if we missed on any obvious caching, etc. (like we might be calling the kdtree twice - if the data is unorganized).

RE: the initial question, there might be something about NaN checks that could be slowing down the execution significantly. If the data is not “clean” (no duplicate points, no NaN/Inf), things should be butter smooth. The devil is always in the details.

Unfortunately I’m a bit swamped right now with other things, but I hope to take a look at it soon.

In any case I think SHOT was outperforming FPFH in most cases in real-world applications, or maybe I remember it the other way around Fede? :)

Best,
Radu.


> On Jan 7, 2015, at 10:25 AM, Anders Glent Buch <[hidden email]> wrote:
>
> Sorry, Fede, Radu, I don't get that.
>
> Radu, your (very nice btw.) paper on FPFH clearly argues why it should be linear: one linear sweep for the SPFHs, followed by one linear sweep of weighted summation of SPFHs.
>
> Fede, you now mention sub-linear complexity, but it's clearly superlinear in the plots? What did you mean?
>
> Sorry for being pedantic here, but I really don't get why FPFH is superlinear when it's just two linear sweeps. What am I missing from Fede's clarification?
>
> On Wed, Jan 7, 2015 at 6:15 PM, Radu B. Rusu <[hidden email]> wrote:
> Anders, I believe Federico’s analysis is correct.
>
> (Thanks Fede! :) )
>
> Best,
> Radu.
>
> > On Jan 7, 2015, at 1:22 AM, fedassa <[hidden email]> wrote:
> >
> > Hi,
> >
> > if you look at Fig. 9 of our SHOT journal paper (“SHOT: Unique Signatures of
> > Histograms for Surface and Texture Description”, CVIU), you can clearly see
> > that the computational complexity of SHOT wrt. the support radius is linear,
> > while that of FPFH is not. This means that, when not using very small
> > support sizes, the difference in time is already one order of magnitude (or
> > more). E.g., if you check the operating points of the parameters we tuned
> > for our dataset (shown by the filled red dot), the difference in
> > computational time is already one oom.
> > As for FPFH, this is probably due to the fact that FPFH computes the SPFH of
> > each point in the neighborhood defined by the support size, and each SPFH
> > has a sub-linear complexity itself, and this should be enough to yield a non
> > linear complexity, as well as to increase the effective support radius of
> > FPFH. But Radu can definitely tell us more about this.
> >
> > As for the last mentioned point (FLANN giving bad matches for SHOT wrt.
> > Brute Force), this is indeed quite strange and would be worth more
> > investigation.
> >
> > Fede
> >
> >
> >
> > --
> > View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036789.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
>
> _______________________________________________
> [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: SHOT is faster than it is supposed to be: or is it normal?

fedassa
Hi there,

very happy to see we revamped an old 3D descriptor discussion :)

@berker:  all the comparisons we made in terms of efficiency in that paper were relatively to support sizes measured in terms of mesh resolution, so they can not be translated directly in terms of small metric radius (e.g. 5-10 cm). In any case, you can see from the graph that there is already one oom. difference at around 6-8 mesh resolution, which I would consider quite a small support size for a descriptor.

As for Flann, we've always been using Randomized Kd-tree included in Flann for matching SHOT descriptors without any noticeable degradation to Brute Force wrt. other descriptors, but it is definitely an aspect that might be worth looking at a bit more in details. Do you think you can provide some comparison in terms of  % of missed correspondences (measured against the Brute Force) for SHOT as well as for other descriptors?

@andersgb1, radu:
what I meant is that, for each point falling within the support size you need to compute a SPFH, which in turns requires solving a NN problem (which is linear or sub-linear depending on the search algorithm being used, but not constant). If you look at it in terms of support radius, the "effective" radius of FPFH approx. doubles wrt. the one used by SHOT, this meaning that, with increasing radius size, the number of points processed by each FPFH descriptor will increase more than linearly wrt. the number of points processed by each SHOT descriptor. I haven't looked at the current implementation of FPFH, so I am not sure exactly which tricks are being used, but in theory it seems to make sense that the overall complexity is super linear.
As for finding an ultimate winner between SHOT vs FPFH, to say it with Descartes, "I refrain from making any judgement on the matter" ;)

Fede

Reply | Threaded
Open this post in threaded view
|

Re: SHOT is faster than it is supposed to be: or is it normal?

Radu B. Rusu
Administrator
I just hope SHOT is better, as I had a terrible headache coming up with a name like FPFH for the descriptor. I blame my co-authors Nico and Zoltan :)

Best,
Radu.

> On Jan 7, 2015, at 4:29 PM, fedassa <[hidden email]> wrote:
>
> Hi there,
>
> very happy to see we revamped an old 3D descriptor discussion :)
>
> @berker:  all the comparisons we made in terms of efficiency in that paper
> were relatively to support sizes measured in terms of mesh resolution, so
> they can not be translated directly in terms of small metric radius (e.g.
> 5-10 cm). In any case, you can see from the graph that there is already one
> oom. difference at around 6-8 mesh resolution, which I would consider quite
> a small support size for a descriptor.
>
> As for Flann, we've always been using Randomized Kd-tree included in Flann
> for matching SHOT descriptors without any noticeable degradation to Brute
> Force wrt. other descriptors, but it is definitely an aspect that might be
> worth looking at a bit more in details. Do you think you can provide some
> comparison in terms of  % of missed correspondences (measured against the
> Brute Force) for SHOT as well as for other descriptors?
>
> @andersgb1, radu:
> what I meant is that, for each point falling within the support size you
> need to compute a SPFH, which in turns requires solving a NN problem (which
> is linear or sub-linear depending on the search algorithm being used, but
> not constant). If you look at it in terms of support radius, the "effective"
> radius of FPFH approx. doubles wrt. the one used by SHOT, this meaning that,
> with increasing radius size, the number of points processed by each FPFH
> descriptor will increase more than linearly wrt. the number of points
> processed by each SHOT descriptor. I haven't looked at the current
> implementation of FPFH, so I am not sure exactly which tricks are being
> used, but in theory it seems to make sense that the overall complexity is
> super linear.
> As for finding an ultimate winner between SHOT vs FPFH, to say it with
> Descartes, "I refrain from making any judgement on the matter" ;)
>
> Fede
>
>
>
>
>
> --
> View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036802.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: SHOT is faster than it is supposed to be: or is it normal?

berker
This post has NOT been accepted by the mailing list yet.
In reply to this post by fedassa
@Federico
Thanks for the feedback. Probably I am not doing anything wrong because the descriptors seems valid and SHOT performs really well, in fact better than FPFH in my tests on the RGB-D dataset.

As for the flann-bruteforce case my problem is with relatively small support radius, ex:5 cm.  For larger sizes there seems to be no problem and results are almost same. So there seems to be no serious problem.

@Federico, Radu

I guess which one is better depends on application but for object recognition SHOT seems a little bit better.

BUT, I am working on something too! :) results are surprise! :)

I will let you guys know when the work is accepted so that I can add it to PCL.

Best,

Berker
Middle East Technical University
Reply | Threaded
Open this post in threaded view
|

Re: SHOT is faster than it is supposed to be: or is it normal?

andersgb1
In reply to this post by Radu B. Rusu
OK, just to hopefully trigger any one of you for this discussion, and for finding an explanation here.

I tested the speed of FPFH and other features using an example scene from Fede's excellent Bologna dataset. This same scene was decimated to 20 resolution levels [0.05, 0.1, ..., 1], 1 being full resolution. So the point clouds have linearly increasing size [~5k, ~10k, ..., ~100k], and thus linearly increasing points within any fixed local neighborhood. I hope you don't mind, Fede, that I share these decimated point clouds: https://dl.dropboxusercontent.com/u/40910230/scenes_timing.tar.gz.

Then I took for each point cloud 2500 random points and computed FPFH features with a radius of 0.02 m. I first computed the average number of neighbors within the 2500 support regions of each decimated point cloud:

     76
    153
    231
    308
    383
    459
    534
    609
    683
    758
    831
    905
    980
   1054
   1129
   1202
   1277
   1351
   1425
   1497

Clearly linear, so now we have linearly increasing support through the scenes. Then I computed FPFHs for the 2500 points in each scene, timed the process, and divided the times by 2500 to get an average, per-feature estimation time [s]:

   6.9281e-05
   2.3273e-04
   4.7438e-04
   8.1922e-04
   1.2414e-03
   1.7104e-03
   2.3388e-03
   2.9628e-03
   3.7777e-03
   4.6414e-03
   5.5643e-03
   6.3996e-03
   7.5566e-03
   8.8852e-03
   1.0005e-02
   1.1102e-02
   1.2472e-02
   1.4264e-02
   1.5396e-02
   1.7018e-02

In a plot this looks... not as expected:

Displaying plot.png

So what the heck is going on? Or have I screwed up in the way I test this? I got completely linear plots for all the others, SHOT included.

-Anders

On Thu, Jan 8, 2015 at 2:18 AM, Radu B. Rusu <[hidden email]> wrote:
I just hope SHOT is better, as I had a terrible headache coming up with a name like FPFH for the descriptor. I blame my co-authors Nico and Zoltan :)

Best,
Radu.

> On Jan 7, 2015, at 4:29 PM, fedassa <[hidden email]> wrote:
>
> Hi there,
>
> very happy to see we revamped an old 3D descriptor discussion :)
>
> @berker:  all the comparisons we made in terms of efficiency in that paper
> were relatively to support sizes measured in terms of mesh resolution, so
> they can not be translated directly in terms of small metric radius (e.g.
> 5-10 cm). In any case, you can see from the graph that there is already one
> oom. difference at around 6-8 mesh resolution, which I would consider quite
> a small support size for a descriptor.
>
> As for Flann, we've always been using Randomized Kd-tree included in Flann
> for matching SHOT descriptors without any noticeable degradation to Brute
> Force wrt. other descriptors, but it is definitely an aspect that might be
> worth looking at a bit more in details. Do you think you can provide some
> comparison in terms of  % of missed correspondences (measured against the
> Brute Force) for SHOT as well as for other descriptors?
>
> @andersgb1, radu:
> what I meant is that, for each point falling within the support size you
> need to compute a SPFH, which in turns requires solving a NN problem (which
> is linear or sub-linear depending on the search algorithm being used, but
> not constant). If you look at it in terms of support radius, the "effective"
> radius of FPFH approx. doubles wrt. the one used by SHOT, this meaning that,
> with increasing radius size, the number of points processed by each FPFH
> descriptor will increase more than linearly wrt. the number of points
> processed by each SHOT descriptor. I haven't looked at the current
> implementation of FPFH, so I am not sure exactly which tricks are being
> used, but in theory it seems to make sense that the overall complexity is
> super linear.
> As for finding an ultimate winner between SHOT vs FPFH, to say it with
> Descartes, "I refrain from making any judgement on the matter" ;)
>
> Fede
>
>
>
>
>
> --
> View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036802.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


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

Re: SHOT is faster than it is supposed to be: or is it normal?

andersgb1
SOLVED!

The problem was the fact that I was using a subset of points for computing features, meaning I had a search surface much bigger than the input point cloud to FPFH. Then FPFH spends the whole first sweep of SPFH computation on the underlying surface, and the second weighting sweep only on the input feature points. So basically, the first sweep performs many, many more radius searches than the second - and all other features. This results in quadratic complexity.

For a fair comparison, I am now computing features at ALL surface points, giving linear increase in computation time for FPFH, and good efficiency relative to the others :)

One can of course discuss whether the SPFH step is a bit suboptimal, if one only needs features at few points...

On Sat, Jan 10, 2015 at 9:10 PM, Anders Glent Buch <[hidden email]> wrote:
OK, just to hopefully trigger any one of you for this discussion, and for finding an explanation here.

I tested the speed of FPFH and other features using an example scene from Fede's excellent Bologna dataset. This same scene was decimated to 20 resolution levels [0.05, 0.1, ..., 1], 1 being full resolution. So the point clouds have linearly increasing size [~5k, ~10k, ..., ~100k], and thus linearly increasing points within any fixed local neighborhood. I hope you don't mind, Fede, that I share these decimated point clouds: https://dl.dropboxusercontent.com/u/40910230/scenes_timing.tar.gz.

Then I took for each point cloud 2500 random points and computed FPFH features with a radius of 0.02 m. I first computed the average number of neighbors within the 2500 support regions of each decimated point cloud:

     76
    153
    231
    308
    383
    459
    534
    609
    683
    758
    831
    905
    980
   1054
   1129
   1202
   1277
   1351
   1425
   1497

Clearly linear, so now we have linearly increasing support through the scenes. Then I computed FPFHs for the 2500 points in each scene, timed the process, and divided the times by 2500 to get an average, per-feature estimation time [s]:

   6.9281e-05
   2.3273e-04
   4.7438e-04
   8.1922e-04
   1.2414e-03
   1.7104e-03
   2.3388e-03
   2.9628e-03
   3.7777e-03
   4.6414e-03
   5.5643e-03
   6.3996e-03
   7.5566e-03
   8.8852e-03
   1.0005e-02
   1.1102e-02
   1.2472e-02
   1.4264e-02
   1.5396e-02
   1.7018e-02

In a plot this looks... not as expected:

Displaying plot.png

So what the heck is going on? Or have I screwed up in the way I test this? I got completely linear plots for all the others, SHOT included.

-Anders

On Thu, Jan 8, 2015 at 2:18 AM, Radu B. Rusu <[hidden email]> wrote:
I just hope SHOT is better, as I had a terrible headache coming up with a name like FPFH for the descriptor. I blame my co-authors Nico and Zoltan :)

Best,
Radu.

> On Jan 7, 2015, at 4:29 PM, fedassa <[hidden email]> wrote:
>
> Hi there,
>
> very happy to see we revamped an old 3D descriptor discussion :)
>
> @berker:  all the comparisons we made in terms of efficiency in that paper
> were relatively to support sizes measured in terms of mesh resolution, so
> they can not be translated directly in terms of small metric radius (e.g.
> 5-10 cm). In any case, you can see from the graph that there is already one
> oom. difference at around 6-8 mesh resolution, which I would consider quite
> a small support size for a descriptor.
>
> As for Flann, we've always been using Randomized Kd-tree included in Flann
> for matching SHOT descriptors without any noticeable degradation to Brute
> Force wrt. other descriptors, but it is definitely an aspect that might be
> worth looking at a bit more in details. Do you think you can provide some
> comparison in terms of  % of missed correspondences (measured against the
> Brute Force) for SHOT as well as for other descriptors?
>
> @andersgb1, radu:
> what I meant is that, for each point falling within the support size you
> need to compute a SPFH, which in turns requires solving a NN problem (which
> is linear or sub-linear depending on the search algorithm being used, but
> not constant). If you look at it in terms of support radius, the "effective"
> radius of FPFH approx. doubles wrt. the one used by SHOT, this meaning that,
> with increasing radius size, the number of points processed by each FPFH
> descriptor will increase more than linearly wrt. the number of points
> processed by each SHOT descriptor. I haven't looked at the current
> implementation of FPFH, so I am not sure exactly which tricks are being
> used, but in theory it seems to make sense that the overall complexity is
> super linear.
> As for finding an ultimate winner between SHOT vs FPFH, to say it with
> Descartes, "I refrain from making any judgement on the matter" ;)
>
> Fede
>
>
>
>
>
> --
> View this message in context: http://www.pcl-users.org/SHOT-is-faster-than-it-is-supposed-to-be-or-is-it-normal-tp4036780p4036802.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



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

Re: SHOT is faster than it is supposed to be: or is it normal?

berker
This post has NOT been accepted by the mailing list yet.
In reply to this post by andersgb1
Hi Anders,

 when radius is 0.05m or 0.1m  What are the speeds of FPFH and SHOT?  how do they compare?

are you referring to this dataset?

http://vision.deis.unibo.it/research/78-cvlab/80-shot

Middle East Technical University