Second pass of the two-pass algorithm (connected components 4- Connectivity)

Question

I have an assignment which aims to extracting the biggest object from a black and white image, where black is the background.I am using The 2-pass algorithm, here is a link that explains how it works: http://en.wikipedia.org/wiki/Connected-component_labeling#Two-pass

My problems : 1.I am using an array of structure that I want to define its dimensions to be the same of the "input image" so { how can I do that }

2.I made an array of two columns and number of rows as an equivalence table but I am not sure I am getting it right, how can I fix it ?

3. How can I use the equivalence table to "relabel the pixels in the second pass?how can I write the code of the second pass ?

My code:

Image Image::MaxCC()
{
    Image obj;
    obj.height = height;
    obj.width = width;
    short ** original = image;
    short ** output = new short*[height];

    for (int i = 0; i < height; i++)
    {
        output[i] = new short[width];
    }
    obj.imageHeader = imageHeader;
    obj.image = output;

    //label array
    //structure 
    struct label
    {
        int lab;
        int counter;
    };

    label L[][]; //I want to use the dimensions of the input image which is obj.height and obj.width

    //Initialize 

    for (int i = 0; i <= obj.height; i++)
    {
        for (int j = 0; j <= obj.width; j++)
        {
            L[i][j].lab = 0;
            L[i][j].counter = 0;
        }
    }
     int N = 0;
     int count = 0;

     //equivlance tabel 
     int eq[100][2];
     int row = 1;
     int x = 1;
     int s;

// conditions [FIRST ITERATION]
    for (int c = 0; c < obj.width; c++)
    {
        for (int r = 0; r < obj.height; r++)
        {
            // If the pixel is balck , add no label
            if (image[r][c] == 0)
                obj.image[r][c] = 0;

            //Do the pixel's North and West neighbors have different pixel values than current pixel?
            else if (image[r - 1][c] == 0 && image[r][c - 1] == 0)
            {
                L[r][c].lab = N++;
                L[r][c].counter = count++;
                obj.image[r][c] = L[r][c].lab;

            }

            //Does the pixel to the left (West) have the same value as the current pixel?
            else if (image[r][c - 1] == image[r][c])
            {
                L[r][c - 1].counter = count++;
                obj.image[r][c] = L[r][c - 1].lab;

            }

            //Does the pixel to the left (West) have a different value and the one to the North the same value as the current pixel?
            else if (image[r - 1][c] == image[r][c] && image[r][c - 1] != image[r][c])
            {
                L[r - 1][c].counter = count++;
                obj.image[r][c] = L[r - 1][c].lab;
            }

            //Do both pixels to the North and West have the same value as the current pixel but not the same label?
            else if (image[r - 1][c] == image[r][c] && image[r][c - 1] == image[r][c] && L[r - 1][c].lab != L[r][c - 1].lab)
            {
                obj.image[r][c] = L[r - 1][c].lab;
                eq[row][1] = x;
                if (L[r - 1][c].counter << L[r][c - 1].counter)
                {
                    L[r - 1][c].counter = count++; 
                    s = L[r - 1][c].lab;

                }
                else
                {
                    L[r][c - 1].counter = count++;
                    s = L[r][c - 1].lab;
                    eq[row][2] = s;  //..
                    x++; row++;
                }
            }

        }

        //THE SECONF ITERATION ?

        //Iteration to get the maximum counter
        label max;
        int temp;

        for (int c = 0; c < obj.width; c++)
        {
            for (int r = 0; r < obj.height; c++)
            {
                temp = L[r][c].counter;
                if (temp > max.counter)
                    max.counter = temp;
            }
        }
            //iteratio to extract the bigger object
            for (int c = 0; c < obj.width; c++)
            {
                for (int r = 0; r < obj.height; c++)
                {
                    if (max.lab == L[r][c].lab)
                        obj.image[r][c] = 255;
                    else
                        obj.image[r][c] = 0;
                }
            }

    }

    return obj;

}

Answer 1

I have also written the python code for two pass algorithm and find if anything is relevant to your need.

from PIL import Image, ImageOps
%pylab inline

import sys
import random
import numpy


def colourize(img):
    height, width = img.shape

    colors = []
    colors.append([])
    colors.append([])
    color = 1
    # Displaying distinct components with distinct colors
    coloured_img = Image.new("RGB", (width, height))
    coloured_data = coloured_img.load()

    for i in range(len(img)):
        for j in range(len(img[0])):
            if img[i][j] > 0:
                if img[i][j] not in colors[0]:
                    colors[0].append(img[i][j])
                    colors[1].append((random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)))

                ind = colors[0].index(img[i][j])
                coloured_data[j, i] = colors[1][ind]

    return coloured_img


def binarize(img_array, threshold=130):
    for i in range(len(img_array)):
        for j in range(len(img_array[0])):
            if img_array[i][j] > threshold:
                img_array[i][j] = 0
            else:
                img_array[i][j] = 1
    return img_array


def ccl4(img_array):
    ##### first pass #####
    print ("starting first pass")
    curr_label = 1;
    img_array = numpy.array(img_array)
    labels = numpy.array(img_array)

    # storing label conversions
    label_conv = []
    label_conv.append([])
    label_conv.append([])

    count = 0
    for i in range(1, len(img_array)):
        for j in range(1, len(img_array[0])):

            if img_array[i][j] > 0:
                label_x = labels[i][j - 1]
                label_y = labels[i - 1][j]

                if label_x > 0:
                    # both x and y have a label
                    if label_y > 0:

                        if not label_x == label_y:
                            labels[i][j] = min(label_x, label_y)
                            if max(label_x, label_y) not in label_conv[0]:
                                label_conv[0].append(max(label_x, label_y))
                                label_conv[1].append(min(label_x, label_y))
                            elif max(label_x, label_y) in label_conv[0]:
                                ind = label_conv[0].index(max(label_x, label_y))
                                if label_conv[1][ind] > min(label_x, label_y):
                                    l = label_conv[1][ind]
                                    label_conv[1][ind] = min(label_x, label_y)
                                    while l in label_conv[0] and count < 100:
                                        count += 1
                                        ind = label_conv[0].index(l)
                                        l = label_conv[1][ind]
                                        label_conv[1][ind] = min(label_x, label_y)

                                    label_conv[0].append(l)
                                    label_conv[1].append(min(label_x, label_y))

                        else:
                            labels[i][j] = label_y
                    # only x has a label
                    else:
                        labels[i][j] = label_x

                # only y has a label
                elif label_y > 0:
                    labels[i][j] = label_y

                # neither x nor y has a label
                else:
                    labels[i][j] = curr_label
                    curr_label += 1

                    ##### second pass #####
    print ("starting second pass")
    count = 1
    for idx, val in enumerate(label_conv[0]):

        if label_conv[1][idx] in label_conv[0] and count < 100:
            count += 1
            ind = label_conv[0].index(label_conv[1][idx])
            label_conv[1][idx] = label_conv[1][ind]

    for i in range(1, len(labels)):
        for j in range(1, len(labels[0])):

            if labels[i][j] in label_conv[0]:
                ind = label_conv[0].index(labels[i][j])
                labels[i][j] = label_conv[1][ind]

    return labels


def main():
    numpy.set_printoptions(threshold=sys.maxsize)
    # Open the image
    img = Image.open("./image1.png")

    # Threshold the image
    img = img.convert('L')
    img = ImageOps.expand(img, border=1, fill='white')
    img = numpy.array(img)
    img = binarize(img)

    

    img = ccl4(img)

    # Colour the image using labels
    coloured_img = colourize(img)

    # Show the coloured image
    coloured_img.show()
    


if __name__ == "__main__": main()

Answer 2

Part of the code is missing, so I make the following assumption: height, width and image are members of class Image.

Regarding your questions:

1.I am using an array of structure that I want to define its dimensions to be the same of the "input image" so { how can I do that }

label L[][]; //I want to use the dimensions of the input image which is obj.height and obj.width

Why not just declare it as a pointer to pointer, like you did with output, i.e.:

label ** L = new label*[height];
for (int i = 0; i < height; i++)
{
   L[i] = new label[width];
}

2.I made an array of two columns and number of rows as an equivalence table but I am not sure I am getting it right, how can I fix it ?

Regarding the disjoint-set data structure, I think the array should be able to grow dynamically (in theory indefinitely, so I would not use static sizes). I suggest you have a look, and understand some existing implementations (here's one in C++, and another in python), and then you implement yours once you understood them.

EDIT: I just found another implementation here on SO.

3. How can I use the equivalence table to "relabel the pixels in the second pass?how can I write the code of the second pass ?

As far as I understood, the algorithm works like this: in the first pass, it labels each foreground pixel with a value, however, it might happen that parts of blobs end up containing different labels. In the second pass, we want to achieve that each pixel belonging to a blob, is labeled with the same value.

However, in the equivalence table, for each label, you can easily find the smallest label which is equivalent to it, i.e. it is within the same group.

Consider the example in the linked Wikipedia article. (Especially the table after step 2.) Here, if you are going through the image in the second pass, and find e.g. a label whose value is 5, then, with the equivalence table, you will be able to find out, that it is equivalent to label 3 (and thus change all pixels labeled 5 to 3).