# Connected Component Labeling - Equivalence Table

I am trying to write a connected component labelling program, I have done the first part to create a label based on the neighbours. For simplicity I am using a 4-connectivity. I am using ANSI C and to create the equivalence table I am using two linked lists with structures defined like this:

struct T2_node
{
size_t value;
struct T2_node *next;
};

struct T1_node
{
struct T2_node *T2;
struct T1_node *next;
};


Every newly found object has a T1_node which links to a T2_node linked list that keeps the labels of the objects that particular label is connected to. As an example you can see this thresholded image (very noisy!) I am trying to find the connected components of:

A section of the equivalence table for this image is:

label id: connected labels (including its self).

835: 847, 835,
834: 846, 834,
833: 820, 833,
832: 812, 832,
831: 831,
830: 830,
829: 818, 829,
828: 828,
827: 929, 778, 840, 783, 827,
826: 826,
825: 825,
824: 993, 944, 904, 916, 839, 824,
823: 823,
822: 957, 794, 837, 822,
821: 956, 912, 888, 848, 821,
820: 1021, 997, 915, 924, 887, 812, 833, 820,
819: 819,
818: 829, 818,
817: 817,
816: 816,


A grey scale image of the labels of the same image can be seen below:

As you see, the labelled regions within a connected component do not all touch!

My final question is: What algorithm should I use to effectively merge the labels? In other words, how can I find which labels belong to one connected object? I am a graduate student in Astronomy, so I do not know the details of graph theory and set theory or how to implement them in a computer program, take C for example! (although I am interested to learn). So if there is a specific method to do this, please also introduce a reference I can learn that method from, thanks in advance.

• Maybe my realisation will help you (from line 385). Shortly: when you make relabeling, you shouldn't forget to remove unused labels. BTW, more slowly algorithm is realised in library leptonica, for a first time you can try to use it (I did so). – Eddy_Em Aug 29 '13 at 5:28
• Thanks, I will have a detailed look at your code and also the one in leptonica. Is there a specific name for the method you are using to find which connected regions constitute one connected blob? It would really help me understand your program if I can have at least an outline of the logic. – makhlaghi Aug 29 '13 at 5:41
• No, I don't think that it have some specific name. I have read about this algorythm in some article, unfortunately, I can't remember article's title and authors name. I wrote some about this algo in my livejournal, but that's on russian. – Eddy_Em Aug 29 '13 at 7:32
• @Eddy_Em, if you could submit your comment above as an answer I will accept it so the question can be answered. Thank you. – makhlaghi Sep 2 '13 at 11:48
• Thank you for the information rwrong. It is a very long time (nearly a year) since I asked this question and during that time I found a very simple solution that I just explained as an answer. It is based on the breadth first search in graph theory. – makhlaghi Aug 18 '14 at 9:53

As I've said in my comment to question, you can use function pixConnComp from leptonica library. Another variant is to use one of a common known algorithm for connected components labeling. For example you can use my realisation (from line 385) of conncomp labeling algorithm.

Most algorithms use two or three passes over image. My version have three passes:

1. Mark neighbours in each line: you just assign labels to each connected set of pixels line by line (labels are saving in matrix with image size).
2. Fill associative array with remarking: we assign a new labels to labels that we've get at step 1. For this operation we check neighbours of non-zero labels on image and assign to it a smallest value.
3. Rename markers due to associative array.

We can combine steps 2 and 3, but in that case algorithm would be more difficult.

In the course of the year since I asked this question, I found a very easy to implement algorithm that does not rely on the very complicated equivalence table that I used to in this question. I put it in Wikipedia under the title: one component at a time method so it can have a more general audience.

A very efficient algorithm to resolve the equivalence classes is the union-find algorithm. Check it as in the links below:

MATLAB also provides nice applications: http://blogs.mathworks.com/steve/2007/05/25/connected-component-labeling-part-6/

• Thank you, but when applied to a large image (with for example millions of pixels with tens of thousands of connected components) the process (checking all the vertices, keeping all their pixels and their connections) can be very CPU and memory intensive, can't it? But the approach I introduced in my answer which finishes finding one connected component at a time seems to be much less CPU and memory intensive. – makhlaghi Aug 22 '14 at 14:42
• Union find is linear in terms of memory. So no, it will still be efficient. Yet, what I can suggest the best: First of all, run-length encode your binary image to get a sequence of runs. This will greatly reduce the resource requirements for union-find, as now, you will merge the runs instead of individual pixels. – Tolga Birdal Aug 23 '14 at 6:50