Intro2Robotics: Connected Components in a Binary Image

Often in machine vision we'd like to know how many objects are in our camera image. This video illustrates a popular algorithm that requires just two raster scans through the image, from Chapter 11 in "Robot Modeling and Control" by Spong, Hutchinson, & Vidyasagar. We first convert the image to greyscale, apply a threshold value chosen to minimize the within-group-variance, and then apply two raster scans to first assign labels to object pixels while generating an equivalency list, then a second raster scan to relabel all components according to the equivalency list.
Note: this video reveals that Fig. 11.3 is actually a dead dinosaur under a comet.
The image used is imRGB below, the thresholded values are imBW, the connected components are cc:
imRGB(:,:,1) =
153 153 153 153 153 153 153 153 153 153
153 127 127 93 153 153 152 153 153 153
153 127 108 69 153 152 156 152 153 153
153 93 69 93 153 153 152 153 153 153
153 153 153 153 153 153 153 153 153 153
153 153 153 153 0 153 153 0 0 153
153 153 153 153 0 153 153 34 0 153
153 153 153 153 34 185 185 34 0 153
153 34 34 34 34 34 34 34 0 153
153 34 0 34 34 0 0 0 0 153
181 181 198 181 198 181 181 181 181 181
imRGB(:,:,2) =
217 217 217 217 217 217 217 217 217 217
217 127 127 93 217 217 216 217 217 217
217 127 108 69 217 216 218 216 217 217
217 93 69 93 217 217 216 217 217 217
217 217 217 217 217 217 217 217 217 217
217 217 217 217 94 217 217 94 94 217
217 217 217 217 128 217 217 177 128 217
217 217 217 217 177 122 122 177 128 217
217 177 177 177 177 177 177 177 128 217
217 177 0 177 177 128 128 128 128 217
230 230 236 230 236 230 230 230 230 230
imRGB(:,:,3) =
234 234 234 234 234 234 234 234 234 234
234 127 127 93 234 234 233 234 234 234
234 127 108 69 234 233 234 233 234 234
234 93 69 93 234 234 233 234 234 234
234 234 234 234 234 234 234 234 234 234
234 234 234 234 47 234 234 47 47 234
234 234 234 234 64 234 234 76 64 234
234 234 234 234 76 87 87 76 64 234
234 76 76 76 76 76 76 76 64 234
234 76 0 76 76 64 64 64 64 234
29 29 81 29 81 29 29 29 29 29
imBW =
1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 0 0 1
1 1 1 1 0 1 1 0 0 1
1 1 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
cc =
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 2 2 0
0 0 0 0 2 0 0 2 2 0
0 0 0 0 2 2 2 2 2 0
0 2 2 2 2 2 2 2 2 0
0 2 2 2 2 2 2 2 2 0
0 0 0 0 0 0 0 0 0 0

[@beltusnkwawir2908]

Thanks so much. Been going via tons of videos and articles but everything seems so perplexing till I found this video

[@AaronBecker]

Are there other topics you're interested in?

[@Pascibueri]

Thank you! Such a good and easy explanation... I don't know how my prof's able to make such a mess out of this simple thing^^

[@AaronBecker]

Let me know if there are other topics that would benefit from a short video.

[@electric_sand]

I'm self-learning, so understanding the intuition behind these concepts is something very important to me. All I can say is thank you. Neat and well explained. Subscribed!

[@AaronBecker]

@Eigen_value thanks! It has been a hard week here in Texas, and your kind words made my day.

[@electric_sand]

@@AaronBecker God bless you and I hope it all gets better over there. I'm going to share your channel with others, it's a gold-mine and you are a treasure to humanity.

[@Chickenkeeper]

This has to be one of the only videos that actually makes this algorithm understandable, the rest are bizarrely verbose lol

[@BapiKAR]

Thanks for the nicest yet simplest illustration.

[@AaronBecker]

You are welcome -- it is always a fun lecture.

[@tnmyk_]

Very well explained! Thanks a lot for making this video!

[@AhmedZahid1]

Thank you, sir, for your explanation really helped our class teacher refers to your video.

[@AaronBecker]

Glad to help! Where are you?

[@AhmedZahid1]

@@AaronBecker Pakistan, Rawalpindi

[@AaronBecker]

@@AhmedZahid1 h Greetings from Houston Texas, USA!🤓

[@haziqmasud532]

Dude , dude , guess what , We are both @Ahmed Zahid and me are class fellows and I was also not able to understand this concept and I just simply searched it , no brainer why our teacher asked @Ahmed Zahid to watch your video. And this is by all means a coincidence I didn't expected to find my dear friend here in the comment section.

[@haziqmasud532]

@@AaronBecker Greetings from Pakistan , I hope you are in good health and safe in current situation of lock down and pandemic ( COVID-19).

[@mathisart]

This is a very good, gentle explanation. But either I'm not following everything, or there's a missing step when it comes to resolving the equivalences. For example, if you have a list of equivalences [5:4, 4:3, 3:2] (where 5 maps to 4, 4 maps to 3, and 3 maps to 2), then the order in which they appear in the image matters. Eg. if first you map 4 to 3, and THEN you map 5:4, then you'll never map all the 4's to 3. This happened to me with the following image (it's the same as the one in the video except for an extra 1): 11100000 11100000 11100000 00000000 00010011 01010011 11111111 11111111 which, after the pass, becomes: 11100000 11100000 11100000 00000000 00020033 04020033 54422233 54422233 so that, at the time of applying the equivalences, for each pixel you have to iterate over all the equivalences. Eg. if your list of equivalences is [5:4, 4:3, 3:2] as before and you find a pixel with the value of 5, then you have to map 5 to 4, then 4 to 3, then 3 to 2. Otherwise some equivalences might not be correctly "resolved". Alternatively, before the 2nd pass (the pass where you apply/resolve the equivalences), you can "normalize" your list of equivalences to that the list of equivalences [5:4, 4:3, 3:2] becomes [5:2, 4:2, 3:2].

[@AaronBecker]

You are right, and this is glossed over in the book. I decided the best time to update equivalences is each time I find one with the following code: if left ~= up %if labels are different, add equivalence. minEquiv = min(equivalenceList(left), equivalenceList(up)); %update equivalence list to all have the smallest values equivalenceList(equivalenceList == equivalenceList(up)) = minEquiv; equivalenceList(equivalenceList == equivalenceList(left)) = minEquiv; end This has a penalty, since you have to iterate through the equivalence list twice each time you find an equivalence. You could do that in a single loop, but I wrote it this way for clarity.

[@diarmaiddan]

Very simply explained. Thanks!

[@sagarwalishetti9103]

Very Nicely explained Thank you

[@AaronBecker]

Thanks! Merry Christmas

[@nikhilhanda9308]

Thanks for the simple explanation.

[@ce148_rajanunagar2]

thank you for good explanation 🙌

[@concealedgun2101]

works pretty neat, thank you man.

[@meraki___]

Thanks a lot man.

[@surajchess3114]

Thankyou so much Sir ... this video was very helpful to me

[@singhsegv]

Really nice explanation. Thanks a lot.

[@yin-yinyang2425]

Very helpful! ! ! Thank you very much!

[@burhanrashidhussein6037]

nice and simple. Thank you

[@dibyajyotijena8314]

Awesome, thank you!!

[@quyenthinh7857]

Thanks for a very useful video!

[@AaronBecker]

@Quyền Thịnh you are welcome! Happy making robots in 2021!

[@stoka43]

Great explanation, what about the execution time for this algorithm ?

[@AaronBecker]

@Taki Eddine: Linear in the number of pixels. This requires two passes through the entire image (checking every pixel twice), and maintaining the equivalency list. There are other algorithms that might suit your application better. en.wikipedia.org/wiki/Connected-component_labeling has pseudo code and run time analysis for several.

[@sayantanofficial5193]

Awesome😎😎😎

[@123456omgeezy]

the squinting thing works, I do see it

[@tryniti2130]

Unfortunately the whole thing falls apart once there's a stair like step with at least two steps up and right... Imagine an extra white pixel in the corner below the bottom right corner of the top rectangle... then 4 would touch a 3 first, the eq list would be: 1->1, 2->2, 3->2, 4->3. Now you either need multiple passes (but how many?) to get a 4 label down to 2, or a chained eq list, which is extremely inefficient to implement. Am I wrong?

[@AaronBecker]

@Tryniti, you are correct that there are inefficient ways to do this. In my implementation I update the entire equivalence list any time I find a pixel that connects objects with different labels. This requires passing through the entire equivalence list, but allows us to avoid doing multiple passes. Here is my Matlab code: if left ~= up %if labels are different, add equivalence. minEquiv = min(equivalenceList(left), equivalenceList(up)); %update equivalence list to all have the smallest values equivalenceList(equivalenceList == equivalenceList(up)) = minEquiv; equivalenceList(equivalenceList == equivalenceList(left)) = minEquiv; end Please reply if this is confusing, since it is using Matlab's indexing notation. You could simplify it to only pass through the list once instead of twice as shown, but I did it this way to make it readable.

[@styleseivie9554]

awesome

[@billibons4816]

There is a serious mistake here (imho). You should check j-1, i-1 also or you gonna miss diagonal connected pixels.

[@AaronBecker]

Yes, if you use diagonals you will get more pixels. It is a fun exercise to add this to the code. (www.mathworks.com/help/images/pixel-connectivity.html)

[@DanielFiko]

Is the first 2D array the coloured image? How do I use that in Python?

[@twotwo6616]

really helpful

[@beltusnkwawir2908]

What happens if there is was a white pixel (1) at the left edge of the matrix? Seems like the algorithm will consider it a different region

[@AaronBecker]

Quite right nkwawir beltus -- a white pixel on the edge, if there is no white pixel above it, will be given a new label. Do you have binary image you'd like me to examine?

[@sampathelvitigala7011]

Thanks......

[@imdanielmartinez]

Nice but you didn't state what the second scan works.

[@imdanielmartinez]

I mean why does the 4 get 2 and 3 gets 2

[@WilliamSilversmith]

The algorithm requires building an equivalency table (watch the right hand side of the video). The second pass simply looks up the ancestor of the current value and records it in each pixel. A common way to do this is with a union-find data structure. This explanation was good: www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

[@rojikuruvilla1041]

@@imdanielmartinez Each object gets a label. There are only two objects, so the first one should get the label 1 and the second one should get 2. Here in the 1st scan some pixels are marked as part of a 3rd or a 4th object, but actually they are part of the 2nd object. The second scan fixes this.

[@juliogg3611]

thx !

[@koulicksadhu7679]

Please please provide the code for this in python. I am really stuck here for 2 days.

[@AaronBecker]

Sorry -- this is a nice homework problem.

[@koulicksadhu7679]

@@AaronBecker i know sir. It is not like that I had not tried. I did try and wrote a code. But it doesnot seem to work. Tried to rectify it, by posting it on stack overflow, but still no one amswered. If you want, I can post my work here, but please help me