Normalized cut clustering on graph

[anastasiia-kornilova]

let’s assume we have for each point in the pointcloud a full set of masks (i.e. for each point, for each image, there is a mask that covers it — not sure how this is possible in reality, but okay)

one (very commonly used and seemingly pretty general) possibility for computing groups of points is to
(1) create a proxy NN-graph by connecting each point to all neighbours within a given Euclidean distance (say k * sampling distance where sampling distance = average inter-point distance computed from scan)
(2) assign each edge in this proxy graph a weight depending on (a) euclidean distance between its points, (b) a distance (TBD) between mask assignments
(3) perform normalized cuts (https://scikit-image.org/docs/stable/api/skimage.graph.html#skimage.graph.cut_normalized) on the graph to separate points into clusters

what we should discuss in more detail — how to construct weights on edges, as this is crucial to the algorithm

I would probably construct weights that factorise like:
w_ij = a_ij * b_ij
where a_ij captures geometric proximity between points and b_ij captures feature proximity between points (more terms could be added to more completely describe a and b)

for geometric proximity, if we’re viewing with p_i and p_j, something like a gaussian kernel a_ij = exp(-\alpha * ||p_i - p_j||^2) seems like a reasonable weight
for feature proximity, I would try to construct something exp(-mismatches(f_i, f_j)) where mismatches(f_i, f_j) computes number of bits that differ between features f_i and f_j