{"id":1663,"date":"2011-08-06T23:27:33","date_gmt":"2011-08-07T06:27:33","guid":{"rendered":"http:\/\/mcclanahoochie.com\/blog\/?post_type=portfolio&p=1663"},"modified":"2023-06-10T10:32:17","modified_gmt":"2023-06-10T17:32:17","slug":"cuda-connected-component-labeling","status":"publish","type":"post","link":"https:\/\/mcclanahoochie.com\/blog\/2011\/08\/cuda-connected-component-labeling\/","title":{"rendered":"GPU Connected Component Labeling"},"content":{"rendered":"

Connected Component Labeling<\/span> (CCL<\/a>): “is used in computer vision to detect connected regions in binary digital images”, and sometimes referred to as blob coloring<\/em>.<\/p>\n

Motivation:<\/span>
\nTo keep AccelerEyes’<\/a>\u00a0ever expanding GPU library growing, over a few weeks of this summer\u00a0I took on the project of writing a CUDA version of connected component labeling\u00a0to be used in Jacket (M)\u00a0and LibJacket (C++)<\/a>.\u00a0It turned out to be quite a fun learning experience!<\/em> I will share some of the details here.<\/p>\n

I came across several projects and papers on parallel connected component labeling. Many were very general and graph based, and most of them weren’t GPU specific (good for the authors, but more work for me!). The GPU related projects I did find were either not open source, or too complicated\/specific to get working. From this research though, I was equipped to start from scratch with my first attempt at CCL in CUDA.<\/p>\n

First approach:<\/span>
\nRead input binary image > Re-label every non-zero element (in-place) to a unique ID (global thread ID) > Scan through the image in threadblocks\/shared memory, taking the MAX of each pixel’s 4 or 8 connected neighbors > Re-label current pixel to be the max of the connected neighbors, in-place > Repeat entire process (kernel launch) for a minimum number of times, and until no thread detects a change (convergence) > A last pass scans the image for all\u00a0n<\/em> unique labels, and re-maps them into the range [1-n].<\/p>\n

This “local maximum\u00a0propagation<\/em>” approach worked well, but only for ‘small’ images, as otherwise it was really, really slow. This was mostly due to the way I was checking for convergence (high minimum number of passes), and for using unguarded shared memory updates (lots of contention).<\/p>\n

Unknowingly, I ended up writing my own variant of the kernels described in section 5.2. CUDA Implementations in this paper<\/a>, as I discovered this PDF after<\/em> I started coding. Nevertheless, this paper is a good resource of parallel CCL information, and gave me some ideas on improving my code.<\/p>\n

Second approach:<\/span>
\nVery similar to first approach, but with smarter optimization: create a look up table (LUT) image for storing labels at each pixel, and use constant memory to store the flag marking if the labeling has converged or not. The use of a global flag in constant memory enabled quicker label convergence and using a separate LUT allowed for\u00a0cleaner code.\u00a0Even though I wasn’t using shared memory this time around, the performance tremendously improved! Making use of shared memory somehow is the obvious next step for further optimization.<\/p>\n

Example Use:<\/span><\/p>\n

\"\"<\/a>
Binary Image Labeling: uniquely coloring coins<\/figcaption><\/figure>\n

The following M-script loads in the coins.png<\/em> image and performs bwlabel on the CPU and GPU to uniquely label and color each coin, while timing the process.
\n
\n%===============================%<\/code>
\n
\n% params
\nscale = 5;
\nconn = 4;
\nruns = 10;
\n<\/code>
\n% image
\nbw = imread('coins.png');
\nim = (bw > 90);
\nim = imresize(im,scale);
\nss = size(im)
\nim = logical(im);
\ngm = glogical(im);<\/code>
\n
\n% cpu time
\ntic
\nfor rr=1:runs,
\ncc = bwlabel(im,conn);
\nend
\ncpu=toc\/runs<\/code>
\n
\n% gpu time
\ntic
\nfor rr=1:runs,
\ngg = bwlabel(gm,conn);
\nend
\ngpu=toc\/runs<\/code>
\n
\n% compare
\nspeedup=cpu\/gpu<\/code>
\n
\n% plot
\nclose all
\nfigure
\nimage(bw\/10)
\nfigure
\nimage(cc*6)<\/code>
\n
\nreturn;<\/code>
\n
\n%===============================%<\/code><\/p>\n

Performance:<\/span>
\nRight now, the speed of the GPU implementation is comparable to that of the CPU for small image sizes, and really starts to shine as the image gets bigger.<\/p>\n

\"\"<\/a>
GPU CCL speedup over CPU CCL<\/figcaption><\/figure>\n

While the chart looks promising as the sizes get bigger, there is definitely room for improvement in my CUDA CCL implementation. Also note – the 0.6x speedup for the first size represents a 1.1ms difference: 1.7ms on the CPU vs 2.8ms on the GPU – still very competitive. Performance shall improve when I get around to tweaking the code more and applying different CUDA techniques.<\/p>\n

Next Steps:<\/span>
\nWhat can you do with a labeled image? The next image processing step usually involves computing statistics on each labeled region. I have an initial version of this available, for use in Jacket &\u00a0LibJacket<\/a> (extending this is another interesting and challenging exercise to be discussed later!).<\/p>\n

Example uses of connected component labeling<\/em> and labeled image region statistics<\/em> in\u00a0C++ can be found in the image processing demo, included with LibJacket: image_demo.cpp.<\/p>\n

Shameless Plug \ud83d\ude42 \u00a0\u00a0<\/span>Download a free trial of Jacket & LibJacket<\/a> today and see for yourself!<\/p>\n

\u00a0Update<\/strong>: AccelerEyes is now ArrayFire<\/a>\u00a0and the connected components labeling function is called\u00a0regions()<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Connected Component Labeling (CCL): “is used in computer vision to detect connected regions in binary digital images”, and sometimes referred to as blob coloring. Motivation: To keep AccelerEyes’\u00a0ever expanding GPU library growing, over a few weeks of this summer\u00a0I took on the project of writing a CUDA version of connected component labeling\u00a0to be used in … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[91,117,113,116,100,54,101,29],"class_list":["post-1663","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-arrayfire","tag-ccl","tag-computer-vision","tag-connected-component","tag-gpu","tag-image-processing","tag-programming","tag-projects"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/pZdXI-qP","jetpack-related-posts":[{"id":1896,"url":"https:\/\/mcclanahoochie.com\/blog\/2011\/11\/gpu-tv-l1-optical-flow-with-libjacket\/","url_meta":{"origin":1663,"position":0},"title":"GPU TV-L1 Optical Flow with ArrayFire","author":"mcclanahoochie","date":"November 6, 2011","format":false,"excerpt":"Update 1: LibJacket has been renamed to\u00a0\u00a0ArrayFire. Update 2: Huang Chao-Hui was nice enough to port the LibJacket code mentioned here to ArrayFire - see his work here. As one of my\u00a0Computer Vision\u00a0class\u00a0projects, I decided to implement optical flow, because I wanted to learn more about optical flow, and also\u2026","rel":"","context":"In \"arrayfire\"","block_context":{"text":"arrayfire","link":"https:\/\/mcclanahoochie.com\/blog\/tag\/arrayfire\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/11\/jkt-oflow-tvl1-1024x626.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/11\/jkt-oflow-tvl1-1024x626.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/11\/jkt-oflow-tvl1-1024x626.png?resize=525%2C300 1.5x"},"classes":[]},{"id":1731,"url":"https:\/\/mcclanahoochie.com\/blog\/2011\/08\/image-processing-with-libjacket-opencv\/","url_meta":{"origin":1663,"position":1},"title":"Image processing with LibJacket + OpenCV","author":"mcclanahoochie","date":"August 24, 2011","format":false,"excerpt":"Update: one year later:\u00a0ArrayFire+OpenCV The OpenCV library is the de-facto standard for doing computer vision and image processing research projects. OpenCV includes several hundreds of computer vision algorithms, aimed for use in real-time vision applications. LibJacket is a matrix library built on CUDA. LibJacket offers hundreds of general matrix and\u2026","rel":"","context":"In \"arrayfire\"","block_context":{"text":"arrayfire","link":"https:\/\/mcclanahoochie.com\/blog\/tag\/arrayfire\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/08\/Screen-shot-2011-08-24-at-2.42.52-PM-1024x640.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/08\/Screen-shot-2011-08-24-at-2.42.52-PM-1024x640.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/08\/Screen-shot-2011-08-24-at-2.42.52-PM-1024x640.png?resize=525%2C300 1.5x"},"classes":[]},{"id":1966,"url":"https:\/\/mcclanahoochie.com\/blog\/2011\/12\/computer-vision-learning-portfolio\/","url_meta":{"origin":1663,"position":2},"title":"Computer Vision Learning Portfolio","author":"mcclanahoochie","date":"December 12, 2011","format":false,"excerpt":"This page constitutes my required\u00a0external\u00a0learning portfolio for CS 7495, Computer Vision, taken in Fall 2011. In it, I discuss what I have learned throughout the course, my activities and findings, how I think I did, and what impact it had on me. About me I am a coffee fanatic that\u2026","rel":"","context":"In \"computer vision\"","block_context":{"text":"computer vision","link":"https:\/\/mcclanahoochie.com\/blog\/tag\/computer-vision\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/12\/chris-raffertys-2-150x150.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":886,"url":"https:\/\/mcclanahoochie.com\/blog\/2011\/01\/mtimes-gpu-matrix-multiplication\/","url_meta":{"origin":1663,"position":3},"title":"MTIMES – GPU Matrix Multiplication","author":"mcclanahoochie","date":"January 1, 2011","format":false,"excerpt":"July 2010 OK, it's not really a project, but I did learn a lot about GPU matrix multiplication over the summer, working\u00a0at AccelerEyes. I\u00a0re-worked the back-end CUDA code for\u00a0the MTIMES Jacket function. I also modified it to accelerate SUM, MIN, and\u00a0MAX. Checkout my MTIMES wiki page!","rel":"","context":"In \"arrayfire\"","block_context":{"text":"arrayfire","link":"https:\/\/mcclanahoochie.com\/blog\/tag\/arrayfire\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/01\/fermi_gflops_single.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":929,"url":"https:\/\/mcclanahoochie.com\/blog\/2011\/01\/p3dfft-cuda-gpu-3d-fft\/","url_meta":{"origin":1663,"position":4},"title":"P3DFFT + CUDA (GPU 3D FFT)","author":"mcclanahoochie","date":"January 1, 2011","format":false,"excerpt":"December 2010 My first project as a GRA under Rich Vuduc involved accelerating 3D Fast Fourier Transforms (3D FFT) with GPUs. The project was basically porting the open-source P3DFFT code\u00a0(written in FORTRAN) to run on GPU(instead of CPU)\u00a0clusters using CUFFT. \u00a0 Update: 04\/16\/2011 - This project has morphed into a\u2026","rel":"","context":"In \"cuda\"","block_context":{"text":"cuda","link":"https:\/\/mcclanahoochie.com\/blog\/tag\/cuda\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/mcclanahoochie.com\/blog\/wp-content\/uploads\/2011\/01\/pencil-decomp.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":1133,"url":"https:\/\/mcclanahoochie.com\/blog\/2011\/03\/the-history-and-evolution-of-gpu-hardware\/","url_meta":{"origin":1663,"position":5},"title":"The History and Evolution of GPU Hardware","author":"mcclanahoochie","date":"March 27, 2011","format":false,"excerpt":"Here is a paper survey I wrote last semester in my CS6290 class about how the Graphics Processing Units (GPUs) hardware architecture has evolved over time. I found the research quite interesting, and spent a lot of time doing it. I'm posting this here, as I feel that more people\u2026","rel":"","context":"In \"evolution\"","block_context":{"text":"evolution","link":"https:\/\/mcclanahoochie.com\/blog\/tag\/evolution\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/posts\/1663","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/comments?post=1663"}],"version-history":[{"count":0,"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/posts\/1663\/revisions"}],"wp:attachment":[{"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/media?parent=1663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/categories?post=1663"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mcclanahoochie.com\/blog\/wp-json\/wp\/v2\/tags?post=1663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}