Clear Filters
Clear Filters

Knnsearch but only return values that are fully connected to one another?

1 view (last 30 days)
Is there a quick way to filter the output of knnsearch such that only coordinates that would form a cluster are returned? When I refer to a cluster I mean like clusters in an image that would be distiguished by bwlabel or bwconncomp. However, I do not want to use these functions because it would be too slow to put the coordinates into an image and run these functions.
Is there a way do something like knnsearch but set a neighbourhood connectvity such as 26 neighbours?

Answers (1)

Walter Roberson
Walter Roberson on 12 May 2019
The closest you could get to that would be to provide a custom 'Distance' function handle that calculated whether the points belonged to the same cluster and returned inf as the distance if not.
However, I think you would find that the logic that would be necessary to determine whether two points belong to the same cluster would probably not be efficient when repeated over and over again.
You can do things like head straight from the current point towards the other point as long as you can remain in the same cluster, and do the same back towards the first, and then take the two points you get to and start doing simultaneous "hold the left hand to the wall" and "hold the right hand to the wall" boundary tracing and see if you meet up at some point between the two before the left/right for each meet up. If I haven't overlooked something that should be able to figure out if they are in the same cluster. But doing that for every pair of points for every iteration is going to be considerably slower than running a bwlabel.
.. and your mention of 26 neighbours leads me to think maybe you are doing 3D objects, in which case the boundary tracing is going to get considerably messier to figure out iteratively whether two points are in the same cluster.
  1 Comment
Eric Chadwick
Eric Chadwick on 14 May 2019
Thank you for your response. It seems the best option is to just do a distance transform on my image data. The reason I am using knnsearch, however is because a distance transform is much slower and requires a high amount of memory.
It can work, but with my largest images it cancels the job due to a memory error even though it stops instelf before even exceeding half my available memory. This only ocurrs when I try to return the index instead of the distances via: [~,Idx] = bwdist(volume);
Any ideas on how to get around this? Has someone ever created a mexable version of a distance transform?

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!