README

Programs of Connected Component Labeling (CCL) on CPU / GPU

Objective:

  To solve the problem of the CUDA programming contest (TopCoder/NVIDIA CUDA Superhero Challenge 1; http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13957&pm=10644).


To compile source files:

  $ make


Create below files:

  ccl_np_cpu   # Neighbour Propagation on CPU
  ccl_np_gpu   # Neighbour Propagation on CPU
  ccl_dpl_cpu  # Directional Propagation Labelling on CPU
  ccl_dpl_gpu  # Directional Propagation Labelling on GPU
  ccl_le_cpu   # Label Equivalence on CPU
  ccl_le_gpu   # Label Equivalence on GPU


To create input data from image files:

  Usage: image2input.py input_image output_text [degree_of_connectivity=4 threashold=0]

 Example)
  $ ./image2input.py image.jpg input.dat 8 10
  $ ./ccl_le_cpu input.dat > result.txt


References:

  1. K. Hawick, A. Leist and D. Playne, Parallel graph component labelling with GPUs and CUDA, Parallel Computing 36 (12) 655-678 (2010)
  2. 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)
  3. V. M. A. Oliveira and  R. A. Lotufo, A study on connected components labeling algorithms using GPUs, SIBGRAPI (2010)