[sample_consensus] Inconsistent sample validation in SampleConsensusModelLine, SampleConsensusModelStick, and SampleConsensusModelCylinder

[alexvorndran]

Describe the bug

The sample validation in isSampleGood(...) of SampleConsensusModelLine has some strong similarity to the validation block in computeModelCoefficients(...) (lines 84 - 86). The piece of code in computeModelCoefficients(...) was likely introduced as a workaround to a bug that was fixed in #2488 and also contradicts to the changes introduced in 36c2bd6.

SampleConsensusModelStick is very similar to SampleConsensusModelLine (but broken as detailed #2452 since I still haven't figured out what to do with the radius model parameter there 😓 🤦‍♂️) but hasn't received the changes of 36c2bd6.

SampleConsensusModelCylinder on the other hand doesn't do that kind of point dissimilarity validation in isSamplesGood(...) at all and leaves it up to computeModelCoefficients(...). The implementation in computeModelCoefficients(...) then is virtually identical to that of SampleConsensusModelLine.

If I managed to track down the usage of those functions correctly, they are used in computeModel(...) (isSampleGood(...) indirectly through getSamples(...)) of the various classes derived from SampleConsensus (e.g. RandomSampleConsensus) so for "practical" cases where those points really come from a sensor, there should not be much difference in the actual outcome. In some edge cases the log messages will likely differ since the validation fails in different portions of the algorithm.

Context

Real-time point cloud segmentation using RANSAC and the models above.

Expected behavior

Since these three models have quite some similarity, I would expect similar behavior of them.

Current Behavior

See description.

To Reproduce

Since this is a bug found by code analysis, you have to look at the code to reproduce my journey 😉

Screenshots/Code snippets

Links to some of the relevant code pieces are included in the description.

Your Environment (please complete the following information):

• OS: Linux Mint 19.3
• Compiler: GCC 7.5.4
• PCL Version master (6db8266)

Possible Solution

If there is a consensus which of the validations (i.e. abs vs. !=, && vs. ||) is "the right one" and where it should live (isSampleGood vs. computeModelCoefficients), I think I could contribute a PR. My gut feeling goes towards something like

if (
    std::abs ((*input_)[samples[0]].x - (*input_)[samples[1]].x) > std::numeric_limits<float>::epsilon ()
  ||
    std::abs ((*input_)[samples[0]].y - (*input_)[samples[1]].y) > std::numeric_limits<float>::epsilon ()
  ||
    std::abs ((*input_)[samples[0]].z - (*input_)[samples[1]].z) > std::numeric_limits<float>::epsilon ())
{
  return (true);
}

in isSampeGood(...). std::abs feels "more correct" than != for floating points, but is more expensive to compute.

Additional context

-/-

[mvieth]

Thank you for the very nice and detailed issue description!
I agree, there are some inconsistencies.
I agree that when checking whether two points are (almost) the same, checking with == or != is not a good idea, instead std::abs with a small threshold like epsilon should be preferred.
I think in most cases it would make sense to have these checks in isSampleGood and call that function from computeModelCoefficients to avoid code duplication. One case where I would duplicate some code is when there are some computations necessary to determine whether the sample is good, and the same computations are necessary to compute the model coefficients. There we should avoid doing the same computations twice.

[alexvorndran]

Just out of curiosity I also had a look at SampleConsensusModelPlane where the code of isSampleGood also exists more or less verbatim in computeModelCoefficients. SampleConsensusModelPlane and to lesser extent SampleConsensusModelLine (and by extension ...Stick if it were "fixed") also support your observation that there are sometimes redundant computations (and definitely redundant checks) in isSampleGood(...) and computeModelCoefficients(...).

Regarding how to work on from these observations: One could argue that the "interface documentation" in SampleConsensusModel::computeModelCoefficients states that the samples that go into computeModelCoefficients already have to be validated somehow. If I'm not mistaken that likely happens by calling isSampleGood in getSamples. Therefore I think it should not be necessary to call isSampleGood from computeModelCoefficients under "normal circumstances". On the other hand I could understand that if you want to go for "better be safe than sorry", the checks could be repeated in computeModelCoefficients with the option to duplicate the code for performance reason. Is there an official policy for PCL in that regard? I only recall OpenCV's infamous "We just assume this and don't check it, because performance!"-notes in the docs 😉

[mvieth]

You are right, there is often a trade-off between safety and performance. I am not aware of any official PCL policy on this. Here I would rather keep the checks in computeModelCoefficients, since a user might also use that function directly without calling isSampleGood before. Typically, the performance-loss is negligible since in a RANSAC-like scenario, the computed model would be used to look for inliers, which usually takes much more time than computing the model and the isSampleGood checks

[alexvorndran]

There also seem to be some inconsistencies between models using three points that must not be collinear:

• SampleConsensusCircle3D uses some dot-product magic which is maybe (?) based on triangle area computation using vectors
• SampleConsensusModelCircle2D and SampleConsensusModelPlane do something based on division of two vectors (?), with plane having an additional check to avoid division by an all-zero vector, but a set of "axis parallel" collinear points (e.g. (0, 0, 0), (1, 0, 0), (2, 0, 0)) still gets past this check 😅

I guess something like std::abs (p1.x()*p2.y() - p2.x()*p1.y()) <= std::numeric_limits<double>::epsilon () (basically a direct implementation of the Wikipedia equation) could be an option for SampleConsensusModelCircle2D.
The 3D case looks a bit more complicated, but maybe the dot-product idea in SampleConsensusCircle3D is something to start from.

[mvieth]

but a set of "axis parallel" collinear points (e.g. (0, 0, 0), (1, 0, 0), (2, 0, 0)) still gets past this check

are you sure about that? Remember that comparisons with NaNs are always false actually it does not appear to be so simple, we better avoid relying on that.
I agree that these checks could be improved, especially the tests for exact (in)equality of floats/doubles. Your suggestion for Circle2D looks good. For Circle3D and Plane, checking the magnitude of the cross-product seems right.

[alexvorndran]

are you sure about that? Remember that comparisons with NaNs are always false actually it does not appear to be so simple, we better avoid relying on that.

Pretty much. I even wrote a test for this to be sure, so I can say: doesn't work for me 😉 But it's great to see this "anecdotal evidence" supported by some references to the standard.

My suggestion would be that I push the changes for Circle2D and the tests I wrote for that model and we then discuss if these tests should also be implemented as such or in a similar fashion for Circle3D and Plane or if we just stick with the fixed check based on the cross-product there.

[alexvorndran]

Something for Plane is now up in the PR.

For Circle3D I would propose (p1 - p0).cross(p1 - p2).squaredNorm() <= std::numeric_limits<double>::epsilon () as condition, since this is directly related to the computations in computeModelCoefficients. However, if I get rid of the original check ((p1.dot (p2) < 0.000001)), this yields the exact opposite normal vector in the test (lines 638 - 640 on master). I don't consider this a real problem at the moment since the original check - whatever its exact background is - didn't account for the possibility that the dot product can be negative. But I maybe I get a second opinion from @mvieth on that regard before I (blindly) change the test 😉

[mvieth]

Sounds good. Let's change the test to EXPECT_NEAR (1.0, std::abs(coeff[5]), 1e-3); (same for refined coefficients). That makes more sense.