TopCoder problem "CCL" used in ()



Problem Statement

    

Image Processing using GPU Accelerated Connected Component Labeling

Introduction

High performance image processing is the foundation of many applications including machine vision, real time object recognition, security and many other applications. One of the common processing steps in many of these applications is connected component labeling (CCL). CCL is a simple, but computationally intensive process.

CCL can be defined as identifying objects within a graph of elements which have the same identifiable property and are connected.

A series of high resolution digital images will be provided. This challenge is to process these high resolution images to identify all objects/areas consisting of groups of adjacent pixels of the same color within a specified threshold.

The implementation will be checked for correctness and total performance.

Input

Each image will be given to you as a int[] in row-major order (first pixel is upper left). Each pixel will be have its three color channels encoded in a single integer. The lowest order 8 bits will give the blue channel, the next highest 8 bits the green channel, and the next highest 8 bits the red channel. You will also be given W, the width of the image.

Two other parameters will control how you find the connected components. The first is degree_of_connectivity and indicates whether diagonal pixels should be considered adjacent. If degree_of_connectivity is 4, then only the 4 adjacent pixels should be considered adjacent. If it is 8, then the diagonal ones should be considered adjacent also. Finally, a int threshold will be provided. Two adjacent pixels are considered to be connected if the sum of the differences in their color components is not more than threshold. That is, if

|R1-R0| + |G1-G0| + |B1-B0| <= threshold

Output

You should return a int[] which is the same size as the input. Each element should specify the index of the connected component that pixel is in. The index of a connected component is the smallest pixel index (index into the input array) of any pixel in that component.

For example, consider the 10x10 image shown here:
If the threshold were set to 300, and degree_of_connectivity were 4, we would decompose it into the 6 connected components shown here:
The cyan one would have all its pixels labeled 0, since it's lowest indexed pixel is the upper left corner. The yellow component would have all its pixels labeled 12, since that is the index of the upper left corner of the yellow box. Moving to the end, the lowest index of the large orange region is 32. Note that if degree_of_connectivity had been 8, there would have only been two connected components.

Resources

Wikipedia has a comprehensive write up of connected component labeling at http://en.wikipedia.org/wiki/Connected_Component_Labeling. This task uses a 2D mesh of connected pixels so the generalized case of CCL or CCA of an arbitrarily connected graph does not have to be solved.

There have also been discussions about the use of NVIDIA CUDA Architecture for CCA in published papers and also on NVIDIA CUDA Developer forums.

An excellent, easy to follow, paper on the subject can be found at: http://www.massey.ac.nz/~kahawick/cstn/089/cstn-089.pdf In this paper, section 4 "Hypercubic Mesh Graphs" may be helpful.

Environment & Target Configuration

NVIDIA Tesla C1060 with 4GB of Global Memory

Intel Q8200 CPU

4GB of system memory

Centos 5.3 Linux

NVIDIA GeForce GPU for graphics

Your application should use NVIDIA CUDA 2.3 SDK.

gcc, g++, CUDA 2.3 drivers, tookit and SDK are installed on the servers, and execution path and Library paths setup.

Testing and Scoring

Your score for each test case will be a 0 if you fail to return the right answer, and otherwise will be your runtime in milliseconds. Your overall final score will be the total number of pixels processed divided by your total runtime in seconds. Note that the sum is taken before division is done, giving more weight to larger test cases. Each incorrect answer (a 0 above) will halve your score, in addition to penalizing your total time 60 seconds.
 

Definition

    
Class:CCL
Method:cuda_ccl
Parameters:int[], int, int, int
Returns:int[]
Method signature:int[] cuda_ccl(int[] image, int W, int degree_of_connectivity, int threshold)
(be sure your method is public)
    
 

Notes

-The final scores will be scaled by a constant factor.
-To facilitate debugging, the number of test cases that you fail will be encoded as the number of hundredths in your provisional score. So, a score of 234.04 would indicate that your score was about 234 (when calculated as above) and that you failed 4 of the test cases.
-IMPORTANT HINT: you can change the method signature to pass by reference. A popular choices is:
vector <int> cuda_ccl(vector <int> & image, int W, int degree_of_connectivity, int threshold)
This may be necessary to stay within the memory limit for the larger test cases, and should help your runtime. Also, you may use all of the memory available on the nVidia device. See http://forums.topcoder.com/?module=Thread&threadID=651355&start=0&mc=14#1144482.
 

Constraints

-The images will have up to 300,000,000 pixels and neither side will have more than 20,000 pixels.
-You have up to 1 minute per image.
-The system memory limit is 2500M. You may use all of the device memory.
 

Examples

0)
    
"64by64_image1.bmp 4 0"
Returns: 
"<a href=/contest/problem/CCL/64by64_image1.bmp>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 0<br>"
1)
    
"64by64_image1.bmp 8 30"
Returns: 
"<a href=/contest/problem/CCL/64by64_image1.bmp>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 30<br>"
2)
    
"100by300_image1.bmp 4 25"
Returns: 
"<a href=/contest/problem/CCL/100by300_image1.bmp>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 25<br>"
3)
    
"100by300_image1.bmp 8 0"
Returns: 
"<a href=/contest/problem/CCL/100by300_image1.bmp>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 0<br>"
4)
    
"1Kby768_image1.bmp 8 0"
Returns: 
"<a href=/contest/problem/CCL/1Kby768_image1.bmp>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 0<br>"
5)
    
"4Kby4K_image2.bmp 4 25"
Returns: 
"<a href=/contest/problem/CCL/4Kby4K_image2.bmp>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 25<br>"
6)
    
"hs-2007-13-e-full_jpg.jpg 4 10"
Returns: 
"<a href=/contest/problem/CCL/hs-2007-13-e-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 10<br>"
7)
    
"hs-2008-23-a-full_jpg.jpg 8 60"
Returns: 
"<a href=/contest/problem/CCL/hs-2008-23-a-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 60<br>"
8)
    
"hs-2008-31-a-full_jpg.jpg 4 10"
Returns: 
"<a href=/contest/problem/CCL/hs-2008-31-a-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 10<br>"
9)
    
"hs-2009-05-a-full_jpg.jpg 4 30"
Returns: 
"<a href=/contest/problem/CCL/hs-2009-05-a-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 30<br>"
10)
    
"hs-2009-23-b-full_jpg.jpg 8 60"
Returns: 
"<a href=/contest/problem/CCL/hs-2009-23-b-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 60<br>"
11)
    
"PGM_ganymede_map.bmp 4 30"
Returns: 
"<a href=/contest/problem/CCL/PGM_ganymede_map.bmp>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 30<br>"
12)
    
"venus_aphrodite_terra.bmp 4 10"
Returns: 
"<a href=/contest/problem/CCL/venus_aphrodite_terra.bmp>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 10<br>"
13)
    
"cerberus_enhanced.bmp 8 60"
Returns: 
"<a href=/contest/problem/CCL/cerberus_enhanced.bmp>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 60<br>"
14)
    
"hs-2004-28-b-full_jpg.jpg 8 60"
Returns: 
"<a href=/contest/problem/CCL/hs-2004-28-b-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 60<br>"
15)
    
"hs-2004-30-a-full_jpg.jpg 4 30"
Returns: 
"<a href=/contest/problem/CCL/hs-2004-30-a-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 30<br>"
16)
    
"hs-2006-01-a-hires_jpg.jpg 8 60"
Returns: 
"<a href=/contest/problem/CCL/hs-2006-01-a-hires_jpg.jpg>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 60<br>"
17)
    
"hs-2003-11-a-full_jpg.jpg 4 10"
Returns: 
"<a href=/contest/problem/CCL/hs-2003-11-a-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 4<br>threshold = 10<br>"
18)
    
"hs-2007-16-a-full_jpg.jpg 8 30"
Returns: 
"<a href=/contest/problem/CCL/hs-2007-16-a-full_jpg.jpg>Input Image</a><br>degree_of_connectivity = 8<br>threshold = 30<br>"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10644

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13957&pm=10644

Writer:

Testers:

Problem categories: