Connectivity in Connected Components

[jcrose]

Greetings CloudCompare forum,

I'm currently describing the CC-algorithm for a thesis and would like to know which kind of connectivity between the octants is used, ie. is it 6, 18 or 26 connectivity?

Many thanks,
kind regards

jcrose

[daniel]

I'm not sure if this really applies in the way we use the octree in general. As it's mainly for nearest neighbor search, we dont' have the choice, it's implicitly '26 connectivity'.

Or did I miss something?

[jcrose]

Thanks for the quick reply, Daniel.

Does a detailed description for the Connected Components algorithm exist besides the info on this site and the manual?
From what I understood it works like the 2D version, only that we define adjacency/connectivity based on a shared area, edge or corner.
The depth of the tree then defines the smalles volume an octant can have and also defines the threshold distance which decides if two clusters of neighboring points are disconnected. Say, if one emtpy ocant lies between two occupied octants, the latter are not connected.

I guess the neighbors of all octants are stored in a LUT based on octant indices? Or what do you mean with "implicitly"?

Thanks and kind regards

jcrose

[daniel]

Oh, I'm silly, I didn't even read the title of this thread :D

So you're right, the only algorithm where the connectivity makes sense is this one! And it's indeed 26 connectivity here by default.

The algorithm is described in my PhD manuscript (in French sadly), but it's the relatively standard 1-pass algorithm where you build a list of equivalence for the encountered components that you encounter and that may connect at one point in time. In the end you simply resolve the unique components labels. See https://en.wikipedia.org/wiki/Connected ... ss_version.

The implementation takes advantage of the octree structure, mainly to reduce the amount of memory used by the virtual grid on which the algorithm is applied.

[jcrose]

Thanks for the reply, Daniel.
I still have two questions left. It would be kind of you to answer them as well.

1. How are the neighbors of each octant determined? I found this paper by Hanan Samet (1989) which describes some methods apperently still applied today.
http://www.cs.umd.edu/~hjs/pubs/SameCVGIP89.pdf
Is it done for CloudCompare in one of these ways?

2. When the neighors of an octant are finally determined how is its unbroken connection to other octants outside its direct neighborhood tested ? You mentioned a list equivalence. For now, I understand it this way:
Say, we are starting at one octant "1" with all its neighbors known. We store the neighbors' index in the octree (the 3bit coded position) in a list. All occupied neighbors of 1 are automacially connected. Then, we iterate through the list containing the neighbors of 1 and determine all their occupied neighbors. We add these to the list and test the list for unique indices, thus removing multiple occurences of the same index. This also keeps us from visiting the same octant twice. This goes on until all octants in the list have been visited and no new neighbors were added.
Is this method a "disjoint-data structure" as described here: https://en.wikipedia.org/wiki/Disjoint- ... _structure
?

Many thanks for your time. I am no expert in octrees so forgive me the prolonged questioning :)
Kind regards

jcrose

[jcrose]

Please hold note that I am not interested in the labeling function of the tool. I mereley need the connected point regions of a 3d point cloud.

[daniel]

1) We use a specific octree structure which is an indexed structure (a kind of Morton code for each point). Therefore there's no 'tree' structure, and we can access any neighbor by a simple lookup in the table. If the cell is there, it is found in a few steps (binary search). Otherwise we know it's not there. It's quite simple.

2. Each (non empty) cell is tagged with a label index. If the 'previous' octants (see wikipedia article) are already tagged, we simply use the minimum label for the current cell. And if multiple labels are connected, then we update an equivalence table so as to resolve at the end the fact that several components are actually connected and several labels are actually equivalent.

I just realized that the wikipedia article doesn't describe the algorithm we use properly. I should try to find the article I used during my PhD (but it was a long time ago ;)

[daniel]

Here it is: R. Lumia, L. Shapiro and O. Zuniga, "A new connected components algorithm for virtual memory computers", Computer Vision, Graphics and Image Processing, Vol. 22, p. 328-339, 1983

[jcrose]

Alright, many thanks for the answers and the paper!

Cheers!
jcrose