Exercise - Pixel Time

Joe

This is a somewhat longer exercise than the rest. It's also a little more complex.
Personally, I'm going to do it in Python, and strongly encourage you to do so.

In this exercise we're going to manipulate images.

PixelTime

If it's your first time manipulating images, don't panic. It's a lot easier than it looks like.
As a start, we're going to deal with the simplest images. Binary images

What are binary images?

They're the simplest kind. Each pixel is represented by 0 or 1. Here's an example:

0000000000
0011000100
0011100100
0011011100
0001011110

Every pixel represented by 1 is in the foreground, 0 are in the background. Your task is to determine how many separate objects are in the foreground.

What is an object?

When 2 pixels connect, they are part of the same object. Two pixels connect when they're on the next position vertically or horizontally. Diagonales do not count.

ABC
DEF
GHJ

E connects with DBHF.

As a quick hint, the first image had 2 objects.

You are free to do what you want for a user interface (command line, GUI, from file, ...). Have fun coding. Since code might be bigger, I would suggest you used your favorite pastebin for readability reasons.

IMPORTANT NOTE: The other exercises are still open. As a matter of fact, I will finish working on the LebInt exercise before moving to this one.

Georges

Interesting Exercise.
I'll start working on it. Looking forward for some interesting results.

Padre

And what are lone pixels counted ?

Joe

Padre wroteAnd what are lone pixels counted ?

There could be 1-pixel objects, if that's what you're asking.

mesa177

rahmu, E is said to be 4-connected to B,D,H,and F.

There's also the 8-connectivity (E is 8-connected to every neighbor in the matrix) and m-connectivity (mixed connectivity where both 4 and 8 connectivity apply; this is mostly apparent in binary images).

For example, given the binary image:

1 0 1 0
0 0 0 1-------> an 8-connected pixel since it's not possible to connect the remaining neighbors with
1 1 1 0 4-connectivity
1 1 1 1
|
|
|__ an example of an m-connected pixel (if 1 is used to define objects) where both 4 and 8 connectivity
can be used to connect the neighboring pixels

Why don't you try to develop a program that can identify what kind of connectivity a neighboring pixel has with respect to a certain selected pixel in the matrix?

Better yet, how about identifying how many objects exist in a binary image based on m-connectivity?

Joe

It could be an interesting addition to the requirements. Should I expect you to develop this idea? Show us your code.

Georges

Another Question Rahmu...
What should happen in this case:

An Object inside another

Something Like This:

mesa177

@Georges: Each rectangle is a seperate object. So you have only 2 objects in there.

arithma

Assuming white is 1 in that image that is.
It's an interesting problem, but if I can't generalize it, I won't implement it. Am thinking of exploring my template abilities in C++. We'll see. We still got that parser on our backlog.

mesa177

Hint: deal with the picture as a 2D array (2D matrix of pixels), append the original image with the first row on top, last row on bottom, first column to the left and last column to the right (for scanning purposes, nothing more), scan first top to bottom, then scan bottom to top. Upon each scan, save the current scan and the prior one for comparison (you will reach a place where there are pixels that can be a part of two objects, it might not happen a lot for binary images, but it does for grayscale images => the comparison will reveal if you have all the pixels are part of an object).

I'll post the connected component labelling code by tomorrow night (give you some time to think about it). If you want, I can post a pseudo-code for the process by tonight.

Padre

it's pretty easy to implement with recursion, no idea if i'll have time to :P
Code wont be that fast or efficient, but it's a way :D

Padre

Ok, just had lunch and decided to give it a go :)
Here's what i got

int countObjects(int **Ary)
{
	int i,j,count;
	count=0;
	for (i=0;i<SIZE_X;i++)
	{
		for (j=0;j<SIZE_Y;j++)
		{
			if (Ary[i][j]) 
			{
				count++;
				checkPixel(i,j,Ary);
			}
		}
	}
	return count;
}

void checkPixel(int X, int Y, int **Ary)
{
	if (!Ary[X][Y]) return;
	Ary[X][Y]=0;
	if (X>0) checkPixel(X-1,Y,Ary);
	if (X<SIZE_X-1) checkPixel(X+1,Y,Ary);
	if (Y>0) checkPixel(X,Y-1,Ary);
	if (X<SIZE_Y-1) checkPixel(X,Y+1,Ary);

}

SIZE_X and SIZE_Y are 2 defined constant, u can put them as variables :)

Padre

Just tested with a 10'000 x 10'000 ... not as bad as i expected. 7 seconds average time (running on a 2.26Ghz Xeon 5520) :)

arithma

@Padre: Stack Overflow. You missed testing for the obvious use case? Though the solution is mathematically sound.

#define SIZE_X 10000
#define SIZE_Y 10000

int *arr[SIZE_X];

void checkPixel(int X, int Y, int **Ary)
{
    if (!Ary[X][Y]) return;
    Ary[X][Y]=0;
    if (X>0) checkPixel(X-1,Y,Ary);
    if (X<SIZE_X-1) checkPixel(X+1,Y,Ary);
    if (Y>0) checkPixel(X,Y-1,Ary);
    if (X<SIZE_Y-1) checkPixel(X,Y+1,Ary);

}

int countObjects(int **Ary)
{
    int i,j,count;
    count=0;
    for (i=0;i<SIZE_X;i++)
    {
        for (j=0;j<SIZE_Y;j++)
        {
            if (Ary[i][j]) 
            {
                count++;
                checkPixel(i,j,Ary);
            }
        }
    }
    return count;
}

void main(){
	for(int i = 0; i < SIZE_X; i++){
		arr[i] = new int[SIZE_Y];
		for(int j = 0; j < SIZE_Y; j++){
			arr[i][j] = 1;
		}
	}

	countObjects(arr);
}

Georges

Here's My Solution. Written in C#.
The algorithm is a bit creative. And covers all the glitches that might occur during calculations...

For better readability, make sure to copy the code to Visual Studio (C# - Console Application)

using System;
using System.Collections.Generic;
using System.Text;

namespace Pixel
{
    class Program
    {
        static int nmb1 = 0;
        static int nmb0 = 0;

        public static int[,] matrix = new int[10, 5] 
        {
            { 1, 1, 0, 1, 0 },
            { 0, 0, 0, 1, 0 },
            { 1, 1, 1, 0, 0 },
            { 0, 1, 0, 1, 0 },
            { 0, 0, 1, 0, 0 },
            { 1, 0, 0, 1, 1 },
            { 0, 0, 0, 1, 1 },
            { 1, 0, 1, 1, 1 },
            { 0, 1, 1, 1, 1 },
            { 1, 0, 0, 0, 0 },
        };

        public static int[,] matrix2 = new int[12, 7];
        
        static void Main(string[] args)
        { 
            #region // Create a 2nd Matrix [Matrix2] containing Matrix1 but with all Borders set to 0.

            for (int i = 1; i < 11; i++)
            {
                for (int j = 1; j < 6; j++)
                {
                    matrix2[i, j] = matrix[i - 1, j - 1];
                }
            }

            #endregion

            #region // Delete All 1's with THREE 0-Neighbours...

            for (int i = 1; i < 11; i++)
            {
                for (int j = 1; j < 6; j++)
                {
                    if (matrix2[i, j] == 1)
                    {
                        if (((matrix2[i - 1, j] == 1) && (matrix2[i + 1, j] == 0) && (matrix2[i, j - 1] == 0) && (matrix2[i, j + 1] == 0)) ||
                            ((matrix2[i - 1, j] == 0) && (matrix2[i + 1, j] == 1) && (matrix2[i, j - 1] == 0) && (matrix2[i, j + 1] == 0)) ||
                            ((matrix2[i - 1, j] == 0) && (matrix2[i + 1, j] == 0) && (matrix2[i, j - 1] == 1) && (matrix2[i, j + 1] == 0)) ||
                            ((matrix2[i - 1, j] == 0) && (matrix2[i + 1, j] == 0) && (matrix2[i, j - 1] == 0) && (matrix2[i, j + 1] == 1)))
                        {
                            // Replace old Lone 1's with Zeros...
                            matrix2[i, j] = 0;
                        }
                    }
                }
            }

            #endregion

            #region // Delete all 1's with ONE or MORE 0-Neighbours...

            for (int i = 1; i < 11; i++)
            {
                for (int j = 1; j < 6; j++)
                {
                    if (matrix2[i, j] == 1)
                    {
                        if ((matrix2[i - 1, j] == 1) || (matrix2[i + 1, j] == 1) || (matrix2[i, j - 1] == 1) || (matrix2[i, j + 1] == 1))
                            matrix2[i, j] = 0;
                    }
                }
            }

            #endregion 

            #region // Count All Remaining 1's in the Matrix...

            for (int i = 0; i < 12; i++)
            {
                for (int j = 0; j < 7; j++)
                {
                    if (matrix2[i, j] == 1)
                        nmb1++;
                    else
                        nmb0++;
                }
            }

            #endregion

            for (int i = 1; i < 12; i++)
            {
                for (int j = 1; j < 6; j++)
                {
                    Console.Write(matrix2[i, j].ToString() + " ");
                }
                Console.Write("\n");
            }
            Console.Write("The Number Of Objects is: {0}", nmb1);
            Console.ReadKey();
        }        
    }
}

1 - Code can be edited to programmatically create the Matrix (Reading from image)

2 - I'm writing a C# Windows Form to read images and create the corresponding Color Matrix from it. (1's being all white pixels - 0's being all other pixels).

3 - The code might look BIG, but in fact it's not at all. Spacing is what makes it that big. I shrunk it to 1/3 of it's original size. But lost it's readability.

mesa177

Apparently no one noticed the obvious:

________________ neighbor a
|
(x-1,y-1) (x, y-1) (x+1,y-1)
________________________ neighbor b
|
(x-1,y) (x,y) (x+1,y)-------- neighbor c
________________ neighbor d
|
(x-1,y+1) (x,y+1) (x+1,y+1)

During the scan from top to bottom, the only 4-connected neighbors which can be checked are neighbors a and b since neighbors c and d have not yet been assigned as pixels of an object (i.e., in the upcoming looping process, they will be encountered) => If you are checking for all the neighbors at the same time, you would be actually checking most of the pixels more than once and loose track of the actual labelling => You would end up with more objects than there truely is.

However, on the scan from bottom to top, the only 4-connected neighbors which can be checked are neighbors c and d since neighbors a and b this time are considered to have not been assigned.

The multiple scanning ensures that 2 or more labelled objects that are in reality 4-connected but were assigned different labels during one scan will be connected during the next.

Psedo-code for iterative approach of 4-connected component labelling will be posted on midnight.

arithma

George's solution breaks. Na na nanana na. I thought for a little he was a pure torch of genius. He still is, but now he learned a lesson! Prove your algorithm!

This is the matrix that breaks george's code.

        public static int[,] matrix = new int[10, 5] 
        {
            { 1, 1, 1, 1, 0 },
            { 1, 0, 0, 0, 0 },
            { 1, 0, 0, 0, 0 },
            { 0, 0, 0, 1, 0 },
            { 0, 0, 1, 0, 0 },
            { 1, 0, 0, 1, 1 },
            { 0, 0, 0, 1, 1 },
            { 1, 0, 1, 1, 1 },
            { 0, 1, 1, 1, 1 },
            { 1, 0, 0, 0, 0 }

Georges

arithma wroteGeorge's solution breaks. Na na nanana na. I thought for a little he was a pure torch of genius. He still is, but now he learned a lesson! Prove your algorithm!

This is the matrix that breaks george's code.

        public static int[,] matrix = new int[10, 5] 
        {
            { 1, 1, 1, 1, 0 },
            { 1, 0, 0, 0, 0 },
            { 1, 0, 0, 0, 0 },
            { 0, 0, 0, 1, 0 },
            { 0, 0, 1, 0, 0 },
            { 1, 0, 0, 1, 1 },
            { 0, 0, 0, 1, 1 },
            { 1, 0, 1, 1, 1 },
            { 0, 1, 1, 1, 1 },
            { 1, 0, 0, 0, 0 }

Nice Arithma. Will work on the fix we discussed :) Thanks.

mesa177

Okay, so here's the pseudo-code for iterative connected-component labelling:

Iterative Approach connected component labelling:

1) Assign all pixels with binary value logic "1" to numeric label values
2) Scan the image:
    a) If the scan number is odd, scan the image top to bottom, left to right.
    b) If the scan number is even, scan the image bottom to top, right to left.
3) Determine if the neighboring pixels are of logic value "1":
    a) If none of the neighbors do, the pixel maintains its previously assigned label value.
    b) If only one of the neighbors does, the pixel is assigned a label equivalent to that of the 
       neighbor which satisfies the condition.
    c) If more than one neighbor does, the pixel is assigned the label of the neighboring pixel with 
       pre-assigned priority.
4) Repeat steps 2 and 3 until there is no more change of labels (the last two labelled images are saved 
   for comparison purposes upon which the detection of any labelling changes occur; flipping labels are 
   forced to labels with minimum numeric value between the two labels where the flipping occurs => 
   flipping labels show from the comparison conducted).

There's also another way called the classical connected component labelling. It's much harder, might take longer to execute, but the results are better for 8-connected component labelling applications where curves might cause the flipping labels in the iterative approach.

Here's the pseudo-code for the classical connected component labelling:

Classical Approach connected component labelling:

1) Determine if the neighbors of a certain pixel (whose value is logic "1") hold the logic value "1":
    a) If none of the neighbors do, a new label is assigned to the pixel and an array of count Icnt is 
       incremented by one index (i.e. Icnt(i) = 0 where i = value of label).
    b) If only one of the neighbors does, the pixel is assigned a label equivalent to that of the 
       neighbor which satisfies the condition.
    c) If more than one neighbor does:
        i)  The array Icnt is incremented by 1 (i.e. Icnt(i)++).
        ii) An equivalent table is filled with the equivalent labels (i.e. A'(i,Icnt(i)) = Equivalent label 
            where i is value of label to be equated)
    Steps i and ii are repeated until all equivalent labels are covered. The pixels of equivalent labels 
    acquire the label with the minimum numeric value.
2) Repeat step 1 until all of the image is scanned.
3) Update the labelling of the image according to the equivalence table: (i is the label currently being 
    checked)
    a) Check Icnt(i): if it is equal to zero => no equivalent labels => move to next label. Otherwise, 
       move to step b.
    b) Assign all the labels in the array of the equivalent matrix (i.e. A'(i,:)) to a temporary array 
       temp.
    c) Check if the counts of the equivalent labels are non-zero (i.e. the entries on the array Icnt for 
       the labels which are to be equated): if true => update temp to involve the new equivalent 
       labels and set Icnt for these labels to zero.
    d) Update the pixels whose label is equal to one of the equated labels to the label i.
4) Repeat step 3 until all the labels of the array Icnt have been checked.

arithma

Alaa, do you have a source? It would be appreciated if we can run your code to test it rather than having to parse pseudo-code (if you're not going to write it in compilable, I doubt someone else will do it for you).

This is a procedural approach, combining a belong-to-group and join-groups approach. There's also a double indirection (belong to the element at index of group array)
It should become clear on the 3rd read hopefully.

#include <iostream>

#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned char byte;

int count(vector<byte> const & grid, int rows, int cols){
    vector<int> groups;
    vector<int> belong(grid.size(), -1); // vector<index into groups>

#define IDX(row, col) ((row)*cols + (col))
    for(int r = 0; r < rows; r++){
        for(int c = 0; c < cols; c++){
            int idx = IDX(r, c);
            if(grid[idx] == 0)
                continue;
            int idxR = IDX(r, c - 1);
            int idxC = IDX(r - 1, c);
            bool belongR = (c - 1 >= 0 && grid[idxR]);
            bool belongC = (r - 1 >= 0 && grid[idxC]);

            if(belongR){
                belong[idx] = belong[idxR];
                if(belongC){
                    int mingroup = min(groups[belong[idxR]], groups[belong[idxC]]);
                    groups[belong[idxR]] = mingroup;
                    groups[belong[idxC]] = mingroup;
                }
            }
            else if(belongC){
                belong[idx] = belong[idxC];
            }
            else{
                groups.push_back(groups.size());
                belong[idx] = *(groups.end() - 1);
            }
        }
    }
#undef IDX
    sort(groups.begin(), groups.end());
    auto itr = unique(groups.begin(), groups.end());
    return itr - groups.begin();
}

int main(){
    byte data[] =
    {
        1, 0, 0, 1, 0, 0, 1,
        0, 0, 1, 1, 1, 0, 0,
        0, 0, 1, 0, 0, 1, 0,
        0, 1, 1, 1, 1, 1, 0
    };

    vector<byte> grid(data, data + sizeof(data)/sizeof(byte));
    int cnt = count(grid, 4, 7);

    cout << cnt << endl;

    return 0;
}

Edit 1: Fixed the lines around the mingroup to resolve corners to the earliest created group.
Edit 2: Forgot to mention that the language is C++.