ICS Theory Group

Winter 2016: Theory Seminar
ICS, Room 243, 1:00pm

February 12, 2016:

Algorithms for Two-Pass Connected Component Labeling

Siddharth Gupta

Connected Component Labeling (CCL) is an algorithmic application of Graph Theory. It's is an important step in pattern recognition and image processing. It assigns labels to the pixels such that adjacent pixels sharing the same features are assigned the same label. Typically, CCL requires several passes over the data.

In this talk, I will focus on two-pass technique where each pixel is given a provisional label in the first pass whereas an actual label is assigned in the second pass. I will discuss about two algorithms for CCL along with Union-Find Technique used in those algorithms. I will also present a parallel implementation for the faster algorithm.

(Joint work with Mostofa Ali Patwary and Ankit Agrawal in IPDPSW 2014.)