CGAL users discussion list

[Kilian Demeulemeester <>]

Good morning,

I managed to identify the bug in the RANSAC class. It can be described in 
this way:

During the detect method, the process is as follows:
1. Candidates are generated
2. Among the generated candidates, the best of them is extracted: 
best_candidate - that we will name SHAPE1
3. The connected_components method is called on SHAPE1, and the value of 
m_has_connected_component changes to true.
4. For the bug to occur, we assume that SHAPE1 meets the minimum number of 
inliers condition BUT the stop_probability associated with SHAPE1 is not 
sufficient for it to be extracted. 
5. From then on, the loop starts again at step 1.
6. After studying more candidates, SHAPE1 is again the best candidate.
7. HOWEVER, during the call of score method, THE VALUE OF SHAPE1 m_indices 
HAS BEEN MODIFIED.
8. As in step (3), the connected_components method is called on SHAPE1. 
However, since m_has_connected_component is already a true, the value of 
m_indices IS NOT MODIFIED. Therefore, the largest connected_component is not 
extracted.
9. As in step 4, the stop_proability value associated with SHAPE1 is 
calculated. Let's just say this time it's enough to extract the candidate. 
Then, the inliers are extracted. Unfortunately, these do not correspond to 
good inliers.

My idea is to fix the score method as so: when this method is called, the 
value of m_has_connected_component should be set to false BECAUSE IT CHANGES 
THE value of m_indices.

In order to fix the bug locally (monkey patching), I've override the 
connected_component method so that it keeps m_has_connected_component to 
false. By doing so, the bug was fixed.

If my description seems clear, can I open a merge request to correct the 
`score` method? It would be for me the opportunity to contribute (in a tiny 
way) to the project :)

Best.

Kilian Demeulemeester 
Directeur R&D  
Snapkin | Outil de mesure et de mise en plan 2D/3D pour le bâtiment.
Tél : +33 (0)7 83 49 82 36 | Discutons !


-----Message d'origine-----
De : Kilian Demeulemeester 
Envoyé : lundi 9 juillet 2018 15:17
À : 

Objet : RE: [cgal-discuss] Point Set Shape Detection - connected component do 
not provide expected results

Hello,

The following snippet proves the bug (in my environment):
https://gitlab.com/snippets/1731486 

The part about loading the point cloud and writing down the point cloud have 
to be rewritten (because I'm using my company custom library).

The code provided in the snippet detects 343 shapes - most of them being not 
"connected".

Best.
 
-----Message d'origine-----
De : 

 
<>
 De la part de Kilian Demeulemeester Envoyé : lundi 9 juillet 2018 11:44 À : 

 Objet : RE: [cgal-discuss] Point Set Shape Detection - connected component 
do not provide expected results

I'll try to create a snippet.

The bugs occur with the parameters I've provided:
- probability=0.01
- minPoints=10000
- epsilon=0.01
- clusterEpsilon=0.05
- normalThreshold=0.9

It looks that the parameter minPoints is the one responsible for this 
behavior.

When using the default value, the extracted shapes are correct (but a lot of 
them are missing).

Best.

Bien cordialement.
Kilian Demeulemeester
Directeur R&D
Snapkin | Outil de mesure et de mise en plan 2D/3D pour le bâtiment.
Tél : +33 (0)7 83 49 82 36 | Discutons !


-----Message d'origine-----
De : 

 
<>
 De la part de Simon Giraudot Envoyé : lundi 9 juillet 2018 10:53 À : 

 Objet : Re: [cgal-discuss] Point Set Shape Detection - connected component 
do not provide expected results

Hello,

I am sorry but I cannot reproduce your bug. Does it happen all the time? 
RANSAC being based on randomness, it's possible that the result changes from 
one run to another. Do you have the (x,y,z) coordinates of where this bug 
happens?

Also, there are no normal vectors in the file you provide. Can you tell me 
how you estimate these normals? Better, can you share the source code of how 
you estimate the normals + call RANSAC (maybe just the section of the code if 
it is part of a larger project)? That way, I am sure I'm doing the same thing.

Best,


--
Simon Giraudot, PhD
R&D Engineer
GeometryFactory - http://geometryfactory.com/



Le 09/07/2018 à 10:02, Kilian Demeulemeester a écrit :
> Hello,
>
> Here is the point cloud in PLY format: 
> https://drive.google.com/file/d/1cPcxFLQCccmd2X1OWzunc0WtRIiuM9f0/view
> ?usp=sharing
>
> Best,
>
> Bien cordialement.
> Kilian Demeulemeester
> Directeur R&D
> Snapkin | Outil de mesure et de mise en plan 2D/3D pour le bâtiment.
> Tél : +33 (0)7 83 49 82 36 | Discutons !
> 
>
> -----Message d'origine-----
> De : 
> 
>  
> <>
>  De 
> la part de Simon Giraudot Envoyé : lundi 9 juillet 2018 09:27 À :
> 
>  Objet : Re: [cgal-discuss] Point Set Shape 
> Detection - connected component do not provide expected results
>
> Hello,
>
> Le 06/07/2018 à 15:33, Kilian Demeulemeester a écrit :
>> The point cloud is available here: 
>> https://drive.google.com/open?id=1r4-9vLq35L6c4SwlGvqppzv6-wrP8nfV (108Mo).
> I can't seem to open E57 files, could you convert your point cloud to 
> another format? (PLY, OFF, LAS, XYZ.)
>
> Thank you,
>
> --
> Simon Giraudot, PhD
> R&D Engineer
> GeometryFactory - http://geometryfactory.com/
>
>
>> We are using CGAL 4.10.2.
>>
>> I've seen that there has been changes relative to that package but... 
>> nothing related to this.
>>
>> I've checked the release note and didn't see anything related to that bug.
>>
>> I've also blamed the changes of the method connected_component in 
>> CGAL\Shape_detection_3\Shape_base.h - and did not find any changes lately.
>>
>> As for now, I think I will try to extend the class 
>> CGAL::Shape_detection_3::Plane<Traits> to create my own version - and 
>> overload the connected_component method to use our own version (using 
>> opencv).
>>
>>
>> Bien cordialement.
>> Kilian Demeulemeester
>> Directeur R&D
>> Snapkin | Outil de mesure et de mise en plan 2D/3D pour le bâtiment.
>> Tél : +33 (0)7 83 49 82 36 | Discutons !
>> 
>>
>> -----Message d'origine-----
>> De : 
>> 
>>  
>> <>
>>  De 
>> la part de Simon Giraudot Envoyé : vendredi 6 juillet 2018 15:04 À :
>> 
>>  Objet : Re: [cgal-discuss] Point Set Shape 
>> Detection - connected component do not provide expected results
>>
>> Hello,
>>
>> This is indeed unexpected. From what you explain in your email, I don't 
>> think you did anything wrong, so I suspect there is a bug in the package. 
>> What version of CGAL do you use? There has been some changes in the Shape 
>> Detection package lately (but if I remember correctly, nothing that 
>> addresses a bug like this one).
>>
>> Is there any way you could you share the point cloud so I can try to 
>> reproduce it and find where is the bug?
>>
>> Best,
>>
>> --
>> Simon Giraudot, PhD
>> R&D Engineer
>> GeometryFactory - http://geometryfactory.com/
>>
>>
>> Le 06/07/2018 à 10:16, KDemeul a écrit :
>>> Hello,
>>>
>>> I am trying to use the  Point Set Shape Detection 
>>> <https://doc.cgal.org/latest/Point_set_shape_detection_3/index.html#
>>> Chapter_Point_Set_Shape_Detection>
>>> package - in order to detect PLANEs only.
>>>
>>> I've defined the value of the parameters as follow:
>>> -probability=0.01
>>> - minPoints=10000
>>> - epsilon=0.01
>>> - clusterEpsilon=0.05
>>> - normalThreshold=0.9
>>>
>>> However, it seems that the clusterEpsilon parameter is not correctly 
>>> taken into account.
>>>
>>> Here is an example of a plane detected by the algorithm.
>>>
>>> As one can see, the left part is disconnected from the right part - 
>>> by a gap of approx 1.6m.
>>>
>>> <http://cgal-discuss.949826.n4.nabble.com/file/t375977/Sans_titre.pn
>>> g>
>>>
>>> Is there something I don't get?
>>>
>>> Best regards,
>>>
>>> Kilian Demeulemeester.
>>>
>>>
>>>
>>> --
>>> Sent from: http://cgal-discuss.949826.n4.nabble.com/
>>>
>>
>
>


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to 
https://sympa.inria.fr/sympa/info/cgal-discuss



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to 
https://sympa.inria.fr/sympa/info/cgal-discuss