Click here to Skip to main content
16,016,306 members
Articles / Programming Languages / C#

Connected Component Labeling Algorithm

Rate me:
Please Sign up or sign in to vote.
4.94/5 (32 votes)
2 Feb 2014CPOL3 min read 242.8K   887   64   37
Implementation of Connected Component Labeling.
Image 1 Image 2

Contents

Overview

In five seconds 

Detection of connected objects in an image, mainly used in image analysis and OCR.

In five minutes

Connected-component labeling (alternatively connected-component analysis, blob extraction, region labeling, blob discovery, or region extraction) is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled based on a given heuristic. Connected-component labeling is not to be confused with segmentation.

Connected-component labeling is used in computer vision to detect connected regions in binary digital images, although color images and data with higher-dimensionality can also be processed.[1][2] When integrated into an image recognition system or human-computer interaction interface, connected component labeling can operate on a variety of information.[3][4] Blob extraction is generally performed on the resulting binary image from a thresholding step. Blobs may be counted, filtered, and tracked.

Blob extraction is related to but distinct from blob detection.

What to expect

Input

An image containing two shapes:

336915/input.png

Output

Now each is separated into single images:

336915/1.png

336915/2.png

Code

The Interface IConnectedComponentLabeling holds one function That takes a Bitmap as an input an returns a collection of discovered objects. 

C#
public interface IConnectedComponentLabeling
{
    IDictionary<int, Bitmap> Process(Bitmap input);
}

Usage:

C#
IConnectedComponentLabeling target = new CCL();
Bitmap input = new Bitmap(AppDomain.CurrentDomain.BaseDirectory + @"\Test.bmp");

var images= target.Process(input);
foreach (var image in images)
{
    image.Value.Save(savePath + image.Key + ".bmp");
}

The implementation class contains the virtual function CheckIsBackGround(), so you can extend the class, and override this method it to suit the background condition of your image:

C#
#region Protected Functions

protected virtual bool CheckIsBackGround(Pixel currentPixel)
{
    return currentPixel.color.A == 255 && currentPixel.color.R == 255 && 
             currentPixel.color.G == 255 && currentPixel.color.B == 255;
}

#endregion

How it works

First pass (assigning labels)

Image 6

Second pass (aggregation)

Image 7

Step by step walkthrough

In the beginning, we have this image, we start with currentLabelCount = 1.

336915/Start.png

We found our non-background pixel:

336915/step_1.png

get its non-background neighbors:

336915/step_2.png

None of the neighbors is labeled yet, we set the current pixel to the currentLabelCount and set the label's parent to itself (we'll get into that in a second):

336915/step_3.png

on to the next pixel, this one has a neighbour which is already labeled:

336915/step_4.png

assigns the pixel's parent label to that of the neighbour:

336915/step_5.png

We continue on, none of the neighbours of this pixel is labeled:

336915/step_6.png

We increment currentLabelCount and assign it to the pixel, again its parent is set to itself: 

336915/step_7.png

It gets interesting here, when neighbors have different labels:

336915/step_8.png

 

  1. We choose main label, i.e.: that would be the smallest label in the discovered list--> (1)
  2. We set it to be the parent of the other labels

 

336915/step_9.png

A few more rounds and we should end up with this. Notice the blue number in the upper right corner, that's the parent label, the de facto one upon which we aggregate later.

336915/step_10.png

That's it, now all we have to do is pass the image again pixel by pixel, getting the root of each (if labeled) and store it in our patterns' list.

C#
private Dictionary<int, List<Pixel>> AggregatePatterns(Dictionary<int, 
          Label> allLabels, int width, int height)
{
    var patterns = new Dictionary<int, List<Pixel>>();

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            int patternNumber = _board[j, i];

            if (patternNumber != 0)
            {
                patternNumber = allLabels[patternNumber].GetRoot().Name;

                if (!patterns.ContainsKey(patternNumber))
                {
                    patterns.Add(patternNumber, new List<Pixel>());
                }

                patterns[patternNumber].Add(new Pixel(new Point(j, i), Color.Black));
            }
        }
    }

    return patterns;
}

Tricky part: Merging labels  

To join labels in a same set, we have the following class (which implements the union find algorithm):

C#
using System;
using System.Collections.Generic;
using System.Text;

namespace ConnectedComponentLabeling
{
    internal class Label
    {
        #region Public Properties

        public int Name { get; set; }

        public Label Root { get; set; }

        public int Rank { get; set; }

        #endregion

        #region Constructor

        public Label(int Name)
        {
            this.Name = Name;
            this.Root = this;
            this.Rank = 0;
        }

        #endregion

        #region Public Methods

        internal Label GetRoot()
        {
            if (this.Root != this)
            {
                this.Root = this.Root.GetRoot();//Compact tree
            }

            return this.Root;
        }

        internal void Join(Label root2)
        {
            if (root2.Rank < this.Rank)//is the rank of Root2 less than that of Root1 ?
            {
                root2.Root = this;//yes! then Root1 is the parent of Root2 (since it has the higher rank)
            }
            else //rank of Root2 is greater than or equal to that of Root1
            {
                this.Root = root2;//make Root2 the parent

                if (this.Rank == root2.Rank)//both ranks are equal ?
                {
                    root2.Rank++;//increment Root2, we need to reach a single root for the whole tree
                }
            }
        }

        #endregion
    }
}

Pay special attention to the recursive function GetRoot(), that's how we reach the parent of any label.

Remember this part? This is what the function Join(Label root) does. Now let's say we have three labels, 1, 2, and 3, and we picked 1 to be our current label; all we have to do is loop the other labels, if their roots don't match, set their root to that of the label we just picked.  

Conclusion

Hope I delivered a clear explanation, feel free to comment or ask Wink | <img src=. Drawings by zwibbler

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
Egypt Egypt
Enthusiastic programmer/researcher, passionate to learn new technologies, interested in problem solving, data structures, algorithms, AI, machine learning and nlp.

Amateur guitarist/ keyboardist, squash player.

Comments and Discussions

 
GeneralMy vote of 5 Pin
Member 1382479711-Feb-23 9:39
Member 1382479711-Feb-23 9:39 
BugImages horizontally separated by 1 pixel Pin
Member 1184586228-Apr-18 14:56
Member 1184586228-Apr-18 14:56 
Questionconnected components algorithms with C code Pin
Member 1342458411-Nov-17 3:58
Member 1342458411-Nov-17 3:58 
QuestionI ran the program but output the wrong result Pin
Member 1256737213-Feb-17 14:58
Member 1256737213-Feb-17 14:58 
AnswerRe: I ran the program but output the wrong result Pin
Omar Gameel Salem16-Feb-17 18:34
professionalOmar Gameel Salem16-Feb-17 18:34 
QuestionGet Position of the Patterns Pin
Member 116847836-Jul-16 5:39
Member 116847836-Jul-16 5:39 
Questionconnected components labelling for the color images using matlab Pin
Member 1202472330-Sep-15 20:55
Member 1202472330-Sep-15 20:55 
Questionhow to implement in Java Android? Pin
Member 1164329726-Apr-15 5:43
Member 1164329726-Apr-15 5:43 
Bugerror in ur code Pin
Member 1136651121-Mar-15 17:28
Member 1136651121-Mar-15 17:28 
GeneralRe: error in ur code Pin
Omar Gameel Salem21-Mar-15 23:25
professionalOmar Gameel Salem21-Mar-15 23:25 
QuestionHow is CCL different from Image Processing? Pin
ayeshabhatnagar4-Nov-14 2:30
ayeshabhatnagar4-Nov-14 2:30 
AnswerRe: How is CCL different from Image Processing? Pin
Omar Gameel Salem4-Nov-14 10:47
professionalOmar Gameel Salem4-Nov-14 10:47 
QuestionInquiry Pin
Member 1056383724-Apr-14 13:20
Member 1056383724-Apr-14 13:20 
AnswerRe: Inquiry Pin
Omar Gameel Salem24-Apr-14 20:01
professionalOmar Gameel Salem24-Apr-14 20:01 
Questiongood work Pin
ame1312-Mar-14 7:22
ame1312-Mar-14 7:22 
GeneralMy vote of 5 Pin
scrchhrpn17-May-13 21:30
scrchhrpn17-May-13 21:30 
GeneralMy vote of 5 Pin
Uilleam12-Feb-13 11:36
Uilleam12-Feb-13 11:36 
QuestionSome problem Pin
Member 917258413-Dec-12 5:13
Member 917258413-Dec-12 5:13 
AnswerRe: Some problem Pin
Omar Gameel Salem13-Dec-12 5:49
professionalOmar Gameel Salem13-Dec-12 5:49 
Questionsome issues Pin
feversky30-Oct-12 1:59
feversky30-Oct-12 1:59 
QuestionText detection Pin
butterflyzx412-Aug-12 6:42
butterflyzx412-Aug-12 6:42 
AnswerRe: Text detection Pin
Omar Gameel Salem12-Aug-12 11:13
professionalOmar Gameel Salem12-Aug-12 11:13 
QuestionIt's not working properly Pin
riyad parvez24-Jun-12 1:54
riyad parvez24-Jun-12 1:54 
AnswerRe: It's not working properly Pin
Omar Gameel Salem24-Jun-12 4:25
professionalOmar Gameel Salem24-Jun-12 4:25 
QuestionHow to use your dll file? Pin
nprabhu8-Apr-12 19:30
nprabhu8-Apr-12 19:30 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.