The following code is an implementation of this algorithm in MATLAB using the 8-connectivity representation. One can easily change it to a 4-connectivity representation by only considering the pixel to the left and above it.
I will explain each part.
Part 1: Here we read our binary image and give it a padding (size=1) of zeros.
Part 2: This is the first pass of the algorithm. It loops over each pixel and gives it a label; it also records equivalences. These equivalences are recorded in a HashMap, which allows for fast and easy look-up of labels.
Part 3: The hashmap needs some restructuring, so the second pass will be easier. The hashmap produces results like:
5 -> 6 - 7 6 -> 8
We restructure the hashmap so it produces results like:
8 -> 5 7 -> 5 6 -> 5
Part 4: We can remove our padding, since we don’t need it anymore.
Part 5: Now we can do the second pass. We check each non-zero pixel. If it is a key in our hashmap, we just look at the value to know which label it should be.
Now we are done, and we return the number of blobs and the labeled image.