incoherent 26-connectivity graph computation

[QuanticDisaster]

Hi,

I would like more informations on the GridSampling transformation. I am looking for different elements, such as the possibility of computing connected components with a 26-connectivity of voxels, or subsample points clouds with a minimum space between each point.

• what is returned by GridSampling ? I presume it is the center of each voxel but I think it would be great to add the answer to the documentation

Why am I getting 27 edges for some of my points ? I am using the following code :

size = 0.2
transfo = GridSampling(size=size)
centers = transfo(data)
centers.edges = radius_graph(centers.pos, 1.90*size)

The most distant neighboring voxel center should be situated at numpy.sqrt(3) * size (more or less 1.73 * size).

but degree(centers.edges[0]).max() returns me 27 edges.

tempo = np.linalg.norm(centers.pos[centers.edges[1,centers.edges[0] == 79725]] - centers.pos[79725], axis=1)
tempo.sort()
print(tempo)

returns me as distances :

array([0.17431274, 0.17873743, 0.18048306, 0.2194385 , 0.22816484,
       0.23076025, 0.23231013, 0.23332849, 0.25311184, 0.287963  ,
       0.30966258, 0.312008  , 0.31608492, 0.33037668, 0.33096886,
       0.3336713 , 0.34386358, 0.35156766, 0.35266453, 0.35330698,
       0.35683373, 0.3577506 , 0.35800895, 0.35821506, 0.35846823,
       0.35988536, 0.3758839 ], dtype=float32)

Nothing makes sense, all distances are different, the closest voxel centers neighbors should be at a distance of size and so on. What am i missing something ?

Thx

[rusty1s]

Currently, GridSampling returns a new point based on the mean of all points inside the given cluster, so points are not placed equidistant to each other. I agree that this might be counter-intuitive, and we should at least provide a flag to control this behavior.

[QuanticDisaster]

Alright, thx for the precision.
In this case, is there a function/ a simple way to get the voxels centers ?

At the moment I am doing it this way

data = Data(pos=Tensor(pos))

def myround(x, base):
    return base * torch.div(x, base, rounding_mode='floor')

size = 0.2
transfo = GridSampling(size=size, start=myround(data.pos.min(axis=0)[0], size))
centers = transfo(data)
centers.pos = myround(centers.pos, size)

centers.edges = radius_graph(centers.pos, 1.75*size)

And it seems to work as the distance given by this snippet seem more coherent

deg = degree(centers.edges[0]).max()
index = degree(centers.edges[0]).argmax()
tempo = np.linalg.norm(centers.pos[centers.edges[1,centers.edges[0] == index]] - centers.pos[index], axis=1)
tempo.sort()
print(tempo)

[rusty1s]

Yes, rounding seems to be a great solution to achieve that, although currently, you do not round to the center but to one of its edges (rounding_mode='floor). Adding x + 0.5 * base should help, I guess.

[QuanticDisaster]

Indeed, I forgot to add the demi base thx

I will also take this opportunity to point out minor improvements that I think would be interesting for PyG :

• add documentation on return type and nature of GridSampling
• remove the mandatory argument 'batch' for voxel_grid, defaulting it to None
• add a function to return voxels centers directly

[rusty1s]

Yes, I agree with all of these. Are you interested in contributing these features?

[QuanticDisaster]

If it is more confortable for you, yes, I made a PR for the 2 first ones.

About the third one, I could propose a PR with my above implementation but it may be redundant, maybe a more efficient way could be found at the level of torch cluster but in this case I don't know how it would be done

On a side note, a gentle ping on this discussion which could have been hidden by the stacked 'hidden conversation' : #3344 (comment)