这是关于CCL(Connected Component Label)的算法实现,目前只包含了其中的一个算法。详细的论文描述在Parallel graph component labelling with GPUs and CUDA.
关于CCL的介绍在WIKI.
算法实现在CCL_LE_GPU.cu和CCL_LE_GPU.cuh中,其他的都是测试或者辅助文件,具体的使用在example文件中。
更新: 增加两种CCL实现方法,分别在CCL_NP.cu和CCL_DPL.cu文件中,定义分别在其cuh文件中。
初始化一个Mesh结构的原始数据:
2 1 1 1 1 1 1 0 0
2 0 0 0 1 1 1 1 0
2 0 0 0 1 1 1 1 0
2 0 0 0 0 1 1 1 1
2 0 0 0 0 0 1 1 1
2 0 0 0 1 1 1 1 1
2 0 1 1 1 1 0 0 0
2 0 1 0 0 0 0 0 0
最终输出标签Mask:
0 1 1 1 1 1 1 7 7
0 10 10 10 1 1 1 1 7
0 10 10 10 1 1 1 1 7
0 10 10 10 10 1 1 1 1
0 10 10 10 10 10 1 1 1
0 10 10 10 1 1 1 1 1
0 10 1 1 1 1 60 60 60
0 10 1 60 60 60 60 60 60
本来是用于图像分割的label,借鉴mesh结构,把图像看做是一个图的mesh表示形式(不同于图的邻接链表或者稀疏矩阵的表示,Mesh本来就是一个网络结构),然后应用算法实现Label。关于Mesh的定义在这里
- K. Hawick, A. Leist and D. Playne, Parallel graph component labelling with GPUs and CUDA, Parallel Computing 36 (12) 655-678 (2010)
- O. Kalentev, A. Rai, S. Kemnitz and R. Schneider, Connected component labeling on a 2D grid using CUDA, J. Parallel Distrib. Comput. 71 (4) 615-620 (2011)
- V. M. A. Oliveira and R. A. Lotufo, A study on connected components labeling algorithms using GPUs, SIBGRAPI (2010)
- https://github.com/foota/ccl