Connected Component Labeling (CCL) is a well-known algorithm with many applications in image processing and computer vision. Given the growth in terms of inter-pixel relationships and the amount of information stored in a single pixel, the time to run CCL analysis on an image continues to increase rapidly. In this paper we present an accelerated version of CCL using NVIDIA\u2019s Compute Unified Device Architecture (CUDA) framework to address this growing overhead. Our parallelization approach decomposes CCL while respecting all global dependencies across the image. We compare our implementation against serial execution and parallelized implementations developed on OpenMP. We show that our parallelized CCL algorithm targeting NVIDIA\u2019s CUDA can significantly increase performance, while still ensuring labeling quality.<\/p>\n","protected":false},"excerpt":{"rendered":"
Connected Component Labeling (CCL) is a well-known algorithm with many applications in image processing and computer vision. Given the growth in terms of inter-pixel relationships and the amount of information stored in a single pixel, the time to run CCL analysis on an image continues to increase rapidly. In this paper we present an accelerated […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13551,13552,13547],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-field-of-study":[246691,265386,249658,256063,251905,252043,257803,248608,265383],"msr-conference":[265389],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-707389","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-graphics-and-multimedia","msr-research-area-hardware-devices","msr-research-area-systems-and-networking","msr-locale-en_us","msr-field-of-study-computer-science","msr-field-of-study-connected-component-labeling","msr-field-of-study-cuda","msr-field-of-study-image-mathematics","msr-field-of-study-image-processing","msr-field-of-study-implementation","msr-field-of-study-overhead-computing","msr-field-of-study-parallel-computing","msr-field-of-study-single-pixel"],"msr_publishername":"Springer, Cham","msr_edition":"","msr_affiliation":"","msr_published_date":"2014-9-14","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":0,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"doi","viewUrl":"false","id":"false","title":"10.1007\/978-3-319-11331-9_60","label_id":"243106","label":0},{"type":"url","viewUrl":"false","id":"false","title":"http:\/\/ece.neu.edu\/groups\/nucar\/publications\/Fanny_ICCVG.pdf","label_id":"243109","label":0},{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/dblp.uni-trier.de\/db\/conf\/iccvg\/iccvg2014.html#ParavecinoK14","label_id":"243109","label":0},{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/link.springer.com\/chapter\/10.1007\/978-3-319-11331-9_60","label_id":"243109","label":0},{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/rd.springer.com\/chapter\/10.1007\/978-3-319-11331-9_60","label_id":"243109","label":0}],"msr_related_uploader":"","msr_attachments":[],"msr-author-ordering":[{"type":"user_nicename","value":"Fanny Nina Paravecino","user_id":39883,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Fanny Nina Paravecino"},{"type":"guest","value":"david-r-kaeli","user_id":866106,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=david-r-kaeli"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/707389"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/707389\/revisions"}],"predecessor-version":[{"id":866121,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/707389\/revisions\/866121"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=707389"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=707389"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=707389"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=707389"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=707389"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=707389"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=707389"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=707389"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=707389"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=707389"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=707389"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=707389"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=707389"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=707389"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=707389"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}