Connected component labelling on CUDA

Hi everybody,
I am working right now on the connected component labeling which is a part of my image segmentation algorithm. My segmentation algorithm uses spin states (let say in the range (1,4)) to cover defined regions (I can’t use more spins because of the nature this algorithm). After some iterations all regions are covered by one spin state but different objects can be covered by the same spin value. In order to be able to use this results for tasks as object tracking I have to do “connected component labeling” to assign ID to each segment. All classical algorithms for linking are not parallel friendly and I’m not sure that they would be very efficient on GPU.

doe anyone have ideas how labeling could be done highly parallel on GPU?

Thanks in advance!

Yes, it can be done. There’s some discussion here:

How about something like these algorithms: [url=“”][/url]

Hello All. is the best solution for this task. Tried it myself.
They even do not use shared memory and it runs real fast.

I am currently working on Connected Component Labelling myself. I have reached till unique labelling of each connected component.
All that is left is relabelling and size calulation stuff. Will keep you posted as the work progresses… External Image
EDIT: The timing of my code is around 1.2ms for a 320x240 image for GTS 250 graphic card