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

## #2 October 7 2010

Georges
Member

### Re: Exercise - Pixel Time

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

## #3 October 7 2010

Member

### Re: Exercise - Pixel Time

And what are lone pixels counted ?

## #4 October 7 2010

Joe
Member

### Re: Exercise - Pixel Time

And what are lone pixels counted ?

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

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

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

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

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

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

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

## #11 October 8 2010

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

## #12 October 8 2010

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)

## #13 October 8 2010

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)

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

## #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);
}
}
}``````

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)

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

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

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

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

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

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

## #22 October 9 2010

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)

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