Discretized alpha not computed correctly in PPFRegistration?

[Laxen]

Explanation of the Problem

I believe there is an error in the PPFRegistration class, where the discretization of alpha is always done in steps of 1 radian regardless of what discretization step the user has specified. I will explain how this can be tested and hope someone can help me confirm this (or tell me that I'm completely wrong).

The problem is line number 140 in ppf_registration.hpp that can be seen here: https://github.com/PointCloudLibrary/pcl/blob/master/registration/include/pcl/registration/impl/ppf_registration.hpp
This is a simple addition of two terms, the first one being the floored value of alpha. Since alpha can only be in the range [-2pi, 2pi] then its floored value can only be an integer in the range [-7, 6]. The second term is the floored value of pi divided by the discretization step specified by the user. This value is a constant, since the discretization step does not change when running the method. If we call this constant 'm', it is then trivial to see that alpha_discretized will always be in the range [m-7, m+6]. In the line below (141), alpha_discretized is used as an index for the accumulator_array. Because of the problem explained above, only 14 (7+6+1) indices will be used for this array and the rest will always be 0. I do not believe this is the correct way to discretize alpha as it does not take into account the discretization step.

This also causes a segmentation fault when the user specifies discretization steps larger than pi/7. The reason for this is that the constant in line 140 will then be smaller than 7 while floor(alpha) might still be -7, thus the addition results in a number smaller than 0 which causes the unsigned int to overflow. This in turn gives a wrong index to accumulator_array in line 141 which then causes a segmentation fault. I have created a small example demonstrating the problem here: https://github.com/Laxen/ppf_registration_bug

Your Environment

• Operating System and version: Ubuntu 16.04
• Compiler: g++ 5.4.0
• PCL Version: 1.8

Expected Behavior

The registration should complete with no errors, and the user-defined discretization step should be used when discretizing alpha.

Current Behavior

The registration fails with a segmentation fault since the discretization step is not used correctly.

Possible Solution

Changing the code that computes alpha_discretized so it accounts for the discretization step defined by the user. See the explanation above.

Code to Reproduce

See this repo for an example of the problem: https://github.com/Laxen/ppf_registration_bug

[Lanns]

Yeah,i also found that there are lots of error in the PPFRegistration class, e.g. the athor use pfh featrue instead of ppf and use the angle step of hashtable to discretize the alpha_m/alpha_s .....
I was astonished when i saw the 140line in ppf_registration.hpp,and i believe that it's wrong as well.
have you amended it?The calculatation of alpha_m and alpha_s is so complex that i dont understand why the alpha_m and alpha_s is from -2π to 2π so i find it hard to amended it.
Is it convenient for you to give me your e-mail for the further communication with me?thanks.

[Lanns]

hey,guy,I have amended it and it got much better result.
just correct the line 140 to this :
if (alpha < -M_PI)
alpha += (M_PI * 2.0);
if (alpha > M_PI)
alpha -= (M_PI * 2.0);
unsigned int alpha_discretized = static_cast (floor((alpha + M_PI) / temp_search->getAngleDiscretizationStep()));

in addition,I think the step of alpha is different from the step of hashtable's angle,but the author use the same parameter to discretize them.If dinguishing them,it could get better result.

[Laxen]

Hi, sorry for my late reply I've been a bit busy. Yes, there are definitely some problems with this class and one would have to sit down and really look through the code to find them. It's very strange that alpha goes from -2pi to 2pi and I'm pretty sure that's not how it's supposed to be. Having alpha=-pi is the same as having alpha=pi and they should be in the same bin during the voting I believe, but this is not the case right now. They are separated into two different bins even though they represent the same local coordinates, because alpha goes from -2pi to 2pi and not from -pi to pi as I expect it should.

Your fix with making sure alpha is in the range -pi to pi is correct I think. You just need to make sure that the alpha_discretized is also being computed correctly and results in the right indices for the array. Maybe it's correct, I can't tell without testing it myself and I sadly don't have time for that right now. When (and if) I get more time in the future I might look into it, but for now I won't be using this class in my work.

[Lanns]

ok,I have gotten it and thanks your reply.
I have been using this class in my works now and it got a great result,so I hope it can help you.
good luck for your work.

[uhfei]

Lanns answer is right

[SergioRAgostinho]

Thank you both for your effort. Do you mind submitting a pull request with the proposed changes?

It would also be very cool to have some "visual goodies" of situations in which before registration failed and now it succeeds after the changes.

[Lanns]

@SergioRAgostinho
I am very pleasure to submit it,could you teach me how to do so?

[SergioRAgostinho]

Start with the brief introduction to contributing. Move to the in-depth explanation on how to craft the pull request.

For more general information regarding pull requests in GitHub there's this very detailed page all about it.

Edit: @Lanns Can you assign yourself to this issue? It helps us keep track of "who's doing what".

[Lanns]

@SergioRAgostinho
Ok,but I still have an important examination at the end of this month,so I have to finish it first.After it,I will submit the request soon.
In addition,basing on PCL,I have wroten an algorithm about extracting quadric surface which based on region growing and it runs much faster than RANSAC.May I submit it together?

[SergioRAgostinho]

In addition,basing on PCL,I have wroten an algorithm about extracting quadric surface which based on region growing and it runs much faster than RANSAC.May I submit it together?

Please do but in a separate pull request.

[taketwo]

Is there any follow-up? @Lanns do you still plan to submit a patch to fix this issue?

[stale]

Marking this as stale due to 30 days of inactivity. It will be closed in 7 days if no further activity occurs.

[mvieth]

Fixed by #4975