LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 October 7 2010

Joe
Member

Exercise - Pixel Time

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.

Offline

#2 October 7 2010

Georges
Member

Re: Exercise - Pixel Time

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

Offline

#3 October 7 2010

Padre
Member

Re: Exercise - Pixel Time

And what are lone pixels counted ?

Offline

#4 October 7 2010

Joe
Member

Re: Exercise - Pixel Time

Padre wrote:

And what are lone pixels counted ?

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

Offline

#5 October 7 2010

mesa177
Member

Re: Exercise - Pixel Time

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?

Last edited by mesa177 (October 7 2010)

Offline

#6 October 7 2010

Joe
Member

Re: Exercise - Pixel Time

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

Offline

#7 October 7 2010

Georges
Member

Re: Exercise - Pixel Time

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

An Object inside another

Something Like This:
v03t.png

Offline

#8 October 7 2010

mesa177
Member

Re: Exercise - Pixel Time

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

Offline

#9 October 8 2010

arithma
Member

Re: Exercise - Pixel Time

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.

Offline

#10 October 8 2010

mesa177
Member

Re: Exercise - Pixel Time

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.

Offline

#11 October 8 2010

Padre
Member

Re: Exercise - Pixel Time

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

Offline

#12 October 8 2010

Padre
Member

Re: Exercise - Pixel Time

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 :)

Last edited by Padre (October 8 2010)

Offline

#13 October 8 2010

Padre
Member

Re: Exercise - Pixel Time

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) :)

Last edited by Padre (October 8 2010)

Offline

#14 October 8 2010

arithma
Member

Re: Exercise - Pixel Time

@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);
}

Last edited by arithma (October 8 2010)

Offline

#15 October 8 2010

Georges
Member

Re: Exercise - Pixel Time

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.

Last edited by Georges Raad (October 8 2010)

Offline

#16 October 8 2010

mesa177
Member

Re: Exercise - Pixel Time

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.

Last edited by mesa177 (October 8 2010)

Offline

#17 October 8 2010

arithma
Member

Re: Exercise - Pixel Time

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 }

Last edited by arithma (October 8 2010)

Offline

#18 October 8 2010

Georges
Member

Re: Exercise - Pixel Time

arithma wrote:

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 }

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

Offline

#19 October 8 2010

mesa177
Member

Re: Exercise - Pixel Time

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.

Last edited by mesa177 (October 8 2010)

Offline

#20 October 8 2010

arithma
Member

Re: Exercise - Pixel Time

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++.

Last edited by arithma (October 9 2010)

Offline

#21 October 8 2010

mesa177
Member

Re: Exercise - Pixel Time

@Arithma: I can do my own programming thank you very much. The idea was to see if someone could use the pseudo-code to write the program in C/C++ or any other language. The code presented here is in Matlab, enjoy :)

(PS: If the people on this forum are interested in image processing, I did this great project on liscence plate recognition and character segmentation and could post it)

First import an RGB image, or any image really, and perfrom what is known as edge detection to turn it into a binary image. This is a good way of identfying objects (i.e. edge detection) which is based on determining the contours of the various objects in the image. If this code is to be executed for a randomly generated binary matrix, skip the code sections of figure(1) and figure(2) as they are useless then.

% Object Detection

% This program detects the objects found in the imported image. The
% technique used is the 4-connected iterative approach for connected
% component labeling.

clear all
clc

figure(1)
I = imread('image.bmp');    % Importing an RGB picture from current directory
I = rgb2gray(I);
imshow(I,[]);               % Show picture in grayscale
[M,N] = size(I);

figure(2)
I_bw = edge(I,'canny');     % Performing edge detection with Canny method
imshow(I_bw,[]);            % Show edge detection 

figure(3)                   % Labeling with connected component algorithm
label = 1;                  % iterative approach 
for i = 1:M                 
   for j = 1:N
      if I_bw(i,j)          % Generate labels for all pixels with binary 
         L(i,j) = label;    % value 1
         label = label + 1;
      else
         L(i,j) = 0; 
      end
   end
end
L1 = L;
counter = 0;
A = I_bw;                   % Temporary image used for comparison purposes
B = L1;                     % Temporary image used for comparison purposes 
flip = 0;                   % Flag for tracking path of label generation
                            % 0: top to bottom, left to right
                            % 1: bottom to top, right to left
while(~isequal(A,B))        % Reiteration for updating label continues 
  A = L1;                   % Updating comparison matrix before alteration
                            % is incurred to the original matrix L1
  if(~flip)                 % until no further change occurs                
     for i = 2:M-1          
        for j = 2:N-1
           if L1(i,j)       % Labeling with respect to 4-neighbor connections
              if L1(i,j-1)
                 L2(i,j) = L1(i,j-1);
                 L1(i,j) = L2(i,j);
              elseif L1(i-1,j)  
                 L2(i,j) = L1(i-1,j);
                 L1(i,j) = L2(i,j);
              else
                  L2(i,j) = L1(i,j);
              end
           else
                 L2(i,j) = 0;
           end
        end
     end
     L2(M,:) = 0;
     L2(:,N) = 0;
     B = L2;                % Updating comparison matrix
     L1 = L2;               % Updating labeling matrices
     flip = ~flip;
  else
    j = N - 1;
    while (j ~= 1)
       i = M - 1; 
       while (i ~= 1)
          if L1(i,j)       % Labeling with respect to 4-neighbor connections
             if L1(i+1,j)
                L2(i,j) = L1(i+1,j);
                L1(i,j) = L2(i,j);
             elseif L1(i,j+1) 
                L2(i,j) = L1(i,j+1);
                L1(i,j) = L2(i,j);
             else
                L2(i,j) = L1(i,j); 
             end
          else
                L2(i,j) = 0;
          end
          i = i - 1;
       end
       j = j - 1;
    end
    L2(M,:) = 0;
    L2(:,N) = 0;
    B = L2;                 % Updating comparison matrix
    L1 = L2;                % Updating labeling matrices
    flip = ~flip;
  end
  counter = counter + 1;
end
imshow(L2,[]);             % Displaying labelled objects

figure(4)
[W,num] = bwlabel(I_bw,4); % Labeling with Matlab command bwlabel
imshow(W,[]);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Note that the last section figure(4) is used to compare my code to the command used for connected component labeling in Matlab.

This concerns the iterative approach for the 4-connected labelling. Tomorrow I'll post that of the 8-connected iterative approach.

Last edited by mesa177 (October 8 2010)

Offline

#22 October 9 2010

Padre
Member

Re: Exercise - Pixel Time

arithma wrote:

@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);
}

well yh ... it is recusive !! if it's all ones it will overflow for the 100mil calls   it's still valid for the presented case.
and i did say tested for average running time :)
But if i have time, i'll come up with a fix :)

Last edited by Padre (October 9 2010)

Offline

#23 October 9 2010

mesa177
Member

Re: Exercise - Pixel Time

% Object Detection

% This program detects the objects found in the imported image. The
% technique used is the 8-connected iterative approach for connected
% component labeling.

clear all
clc

figure(1)
I = imread('image.bmp');    % Importing RGB image from current directory
I = rgb2gray(I);
imshow(I,[]);               % Show image as grayscale picture
[M,N] = size(I');

figure(2)
I_bin = edge(I,'canny');    % Performing edge detection with Canny method
imshow(I_bin,[]);           % Show edge detection 
I_bw = I_bin';

figure(3)                   % Labeling with connected component algorithm
label = 1;                  % iterative approach 
for i = 1:M                 
   for j = 1:N
      if I_bw(i,j)          % Generate labels for all pixels with binary 
         L(i,j) = label;    % value 1
         label = label + 1;
      else
         L(i,j) = 0; 
      end
   end
end
L1 = L;
C = zeros(M,N);
counter = 0;
A = I_bw;                   % Temporary image used for comparison purposes
B = L1;                     % Temporary image used for comparison purposes 
flip = 0;                   % Flag for tracking path of label generation
                            % 0: top to bottom, left to right
                            % 1: bottom to top, right to left
L2 = zeros(M,N);

while ~(isequal(A,B)||(isequal(B,C)&& ~isequal(A,B)))        
                            % Reiteration for updating label continues 
  C = A;                    % Matrix from two prior iterations  
  A = L1;                   % Updating comparison matrix before alteration
                            % is incurred to the original matrix L1
  if(~flip)                 % until no further change occurs                
     for i = 2:M-1          
        for j = 2:N-1
           if L1(i,j)       % Labeling with respect to 8-neighbor connections
              if L1(i-1,j-1)
                 L2(i,j) = L1(i-1,j-1);
                 if (L2(i,j) == C(i,j))&&(L2(i,j) ~= L1(i,j))
                     if L2(i-1,j-1)
                        L2(i-1,j-1) = min(C(i,j),L1(i,j));
                        L1(i-1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j)
                        L2(i-1,j) = min(C(i,j),L1(i,j));
                        L1(i-1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j+1)
                        L2(i-1,j+1) = min(C(i,j),L1(i,j));
                        L1(i-1,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j-1)
                        L2(i,j-1) = min(C(i,j),L1(i,j));
                        L1(i,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j+1)
                        L2(i,j+1) = min(C(i,j),L1(i,j));
                        L1(i,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j-1)
                        L2(i+1,j-1) = min(C(i,j),L1(i,j));
                        L1(i+1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j)
                        L2(i+1,j) = min(C(i,j),L1(i,j));
                        L1(i+1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j+1)
                        L2(i+1,j+1) = min(C(i,j),L1(i,j));
                        L1(i+1,j+1) = min(C(i,j),L1(i,j));
                     end
                 end
                 L1(i,j) = L2(i,j);
              elseif L1(i,j-1) 
                 L2(i,j) = L1(i,j-1);
                 if (L2(i,j) == C(i,j))&&(L2(i,j) ~= L1(i,j))
                     if L2(i-1,j-1)
                        L2(i-1,j-1) = min(C(i,j),L1(i,j));
                        L1(i-1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j)
                        L2(i-1,j) = min(C(i,j),L1(i,j));
                        L1(i-1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j+1)
                        L2(i-1,j+1) = min(C(i,j),L1(i,j));
                        L1(i-1,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j-1)
                        L2(i,j-1) = min(C(i,j),L1(i,j));
                        L1(i,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j+1)
                        L2(i,j+1) = min(C(i,j),L1(i,j));
                        L1(i,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j-1)
                        L2(i+1,j-1) = min(C(i,j),L1(i,j));
                        L1(i+1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j)
                        L2(i+1,j) = min(C(i,j),L1(i,j));
                        L1(i+1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j+1)
                        L2(i+1,j+1) = min(C(i,j),L1(i,j));
                        L1(i+1,j+1) = min(C(i,j),L1(i,j));
                     end
                 end
                 L1(i,j) = L2(i,j);
              elseif L1(i+1,j-1) 
                 L2(i,j) = L1(i+1,j-1);
                 if (L2(i,j) == C(i,j))&&(L2(i,j) ~= L1(i,j))
                     if L2(i-1,j-1)
                        L2(i-1,j-1) = min(C(i,j),L1(i,j));
                        L1(i-1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j)
                        L2(i-1,j) = min(C(i,j),L1(i,j));
                        L1(i-1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j+1)
                        L2(i-1,j+1) = min(C(i,j),L1(i,j));
                        L1(i-1,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j-1)
                        L2(i,j-1) = min(C(i,j),L1(i,j));
                        L1(i,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j+1)
                        L2(i,j+1) = min(C(i,j),L1(i,j));
                        L1(i,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j-1)
                        L2(i+1,j-1) = min(C(i,j),L1(i,j));
                        L1(i+1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j)
                        L2(i+1,j) = min(C(i,j),L1(i,j));
                        L1(i+1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j+1)
                        L2(i+1,j+1) = min(C(i,j),L1(i,j));
                        L1(i+1,j+1) = min(C(i,j),L1(i,j));
                     end
                 end
                 L1(i,j) = L2(i,j);
              elseif L1(i-1,j)
                 L2(i,j) = L1(i-1,j);
                 if (L2(i,j) == C(i,j))&&(L2(i,j) ~= L1(i,j))
                     if L2(i-1,j-1)
                        L2(i-1,j-1) = min(C(i,j),L1(i,j));
                        L1(i-1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j)
                        L2(i-1,j) = min(C(i,j),L1(i,j));
                        L1(i-1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j+1)
                        L2(i-1,j+1) = min(C(i,j),L1(i,j));
                        L1(i-1,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j-1)
                        L2(i,j-1) = min(C(i,j),L1(i,j));
                        L1(i,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j+1)
                        L2(i,j+1) = min(C(i,j),L1(i,j));
                        L1(i,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j-1)
                        L2(i+1,j-1) = min(C(i,j),L1(i,j));
                        L1(i+1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j)
                        L2(i+1,j) = min(C(i,j),L1(i,j));
                        L1(i+1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j+1)
                        L2(i+1,j+1) = min(C(i,j),L1(i,j));
                        L1(i+1,j+1) = min(C(i,j),L1(i,j));
                     end
                 end
                 L1(i,j) = L2(i,j);
              else
                 L2(i,j) = L1(i,j);
              end
           end
        end
     end
     B = L2;                  % Updating comparison matrix
     L1 = L2;                 % Updating labeling matrices
     flip = ~flip;
  else
    j = N - 1;
    while (j ~= 1)
       i = M - 1; 
       while (i ~= 1)
          if L1(i,j)          % Labeling with respect to 8-neighbor connections
             if L1(i+1,j+1) 
                L2(i,j) = L1(i+1,j+1);
                if (L2(i,j) == C(i,j))&&(L2(i,j) ~= L1(i,j))
                     if L2(i-1,j-1)
                        L2(i-1,j-1) = min(C(i,j),L1(i,j));
                        L1(i-1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j)
                        L2(i-1,j) = min(C(i,j),L1(i,j));
                        L1(i-1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j+1)
                        L2(i-1,j+1) = min(C(i,j),L1(i,j));
                        L1(i-1,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j-1)
                        L2(i,j-1) = min(C(i,j),L1(i,j));
                        L1(i,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j+1)
                        L2(i,j+1) = min(C(i,j),L1(i,j));
                        L1(i,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j-1)
                        L2(i+1,j-1) = min(C(i,j),L1(i,j));
                        L1(i+1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j)
                        L2(i+1,j) = min(C(i,j),L1(i,j));
                        L1(i+1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j+1)
                        L2(i+1,j+1) = min(C(i,j),L1(i,j));
                        L1(i+1,j+1) = min(C(i,j),L1(i,j));
                     end
                end
                L1(i,j) = L2(i,j);
             elseif L1(i,j+1) 
                L2(i,j) = L1(i,j+1);
                if (L2(i,j) == C(i,j))&&(L2(i,j) ~= L1(i,j))
                     if L2(i-1,j-1)
                        L2(i-1,j-1) = min(C(i,j),L1(i,j));
                        L1(i-1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j)
                        L2(i-1,j) = min(C(i,j),L1(i,j));
                        L1(i-1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j+1)
                        L2(i-1,j+1) = min(C(i,j),L1(i,j));
                        L1(i-1,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j-1)
                        L2(i,j-1) = min(C(i,j),L1(i,j));
                        L1(i,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j+1)
                        L2(i,j+1) = min(C(i,j),L1(i,j));
                        L1(i,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j-1)
                        L2(i+1,j-1) = min(C(i,j),L1(i,j));
                        L1(i+1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j)
                        L2(i+1,j) = min(C(i,j),L1(i,j));
                        L1(i+1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j+1)
                        L2(i+1,j+1) = min(C(i,j),L1(i,j));
                        L1(i+1,j+1) = min(C(i,j),L1(i,j));
                     end
                end
                L1(i,j) = L2(i,j);
             elseif L1(i-1,j+1)
                L2(i,j) = L1(i-1,j+1);
                if (L2(i,j) == C(i,j))&&(L2(i,j) ~= L1(i,j))
                     if L2(i-1,j-1)
                        L2(i-1,j-1) = min(C(i,j),L1(i,j));
                        L1(i-1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j)
                        L2(i-1,j) = min(C(i,j),L1(i,j));
                        L1(i-1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j+1)
                        L2(i-1,j+1) = min(C(i,j),L1(i,j));
                        L1(i-1,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j-1)
                        L2(i,j-1) = min(C(i,j),L1(i,j));
                        L1(i,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j+1)
                        L2(i,j+1) = min(C(i,j),L1(i,j));
                        L1(i,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j-1)
                        L2(i+1,j-1) = min(C(i,j),L1(i,j));
                        L1(i+1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j)
                        L2(i+1,j) = min(C(i,j),L1(i,j));
                        L1(i+1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j+1)
                        L2(i+1,j+1) = min(C(i,j),L1(i,j));
                        L1(i+1,j+1) = min(C(i,j),L1(i,j));
                     end
                end
                L1(i,j) = L2(i,j);   
             elseif L1(i+1,j) 
                L2(i,j) = L1(i+1,j);
                if (L2(i,j) == C(i,j))&&(L2(i,j) ~= L1(i,j))
                     if L2(i-1,j-1)
                        L2(i-1,j-1) = min(C(i,j),L1(i,j));
                        L1(i-1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j)
                        L2(i-1,j) = min(C(i,j),L1(i,j));
                        L1(i-1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i-1,j+1)
                        L2(i-1,j+1) = min(C(i,j),L1(i,j));
                        L1(i-1,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j-1)
                        L2(i,j-1) = min(C(i,j),L1(i,j));
                        L1(i,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i,j+1)
                        L2(i,j+1) = min(C(i,j),L1(i,j));
                        L1(i,j+1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j-1)
                        L2(i+1,j-1) = min(C(i,j),L1(i,j));
                        L1(i+1,j-1) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j)
                        L2(i+1,j) = min(C(i,j),L1(i,j));
                        L1(i+1,j) = min(C(i,j),L1(i,j));
                     end
                     if L2(i+1,j+1)
                        L2(i+1,j+1) = min(C(i,j),L1(i,j));
                        L1(i+1,j+1) = min(C(i,j),L1(i,j));
                     end
                end
                L1(i,j) = L2(i,j);
             else
                L2(i,j) = L1(i,j); 
             end
          end
          i = i - 1;
       end
       j = j - 1;
    end
    B = L2;                 % Updating comparison matrix
    L1 = L2;                % Updating labeling matrices
    flip = ~flip;
  end
  counter = counter + 1
end
imshow(L2',[]);             % Displaying labelled objects

figure(4)
[W,num] = bwlabel(I_bin,8); % Labeling with Matlab command bwlabel
imshow(W,[]);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Last edited by mesa177 (October 9 2010)

Offline

Board footer