Find how many objects are in a bitmap

[Maximus_X]

Hi everybody,

I'm preparing to develop an algorithm that count how many objects (ex. fill circles or other simple shapes) are in a bitmap. The backdround has only one color.

I have a ideea, but any referance, sample or advice is wellcome.


Mind regards! ;)

[Maximus_X]

I found a way to count the shapes by using a recursive function. I test the algorithm on a simple integer array (10x10). The ideea it's the same like on bitmap with pots.

Perhaps, sometimes, somebody will meet the same problem so I put down the main part of this algorithm, build on a console application:

static const int ob_col = 1;
static const int no_col = 0;
static const int mark_col = 9;

static const int rows = 10;
static const int cols = 10;

int mat[rows][cols] = { { 0,0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,1,0,0 },
{ 0,0,1,0,0,0,1,1,1,0 },
{ 0,1,1,1,0,0,0,1,0,0 },
{ 0,0,1,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,1,0,0,0 },
{ 0,0,0,0,0,1,1,1,0,0 },
{ 0,1,0,0,1,1,1,1,1,0 },
{ 1,1,1,0,0,1,1,1,0,0 },
{ 0,1,0,0,0,0,1,0,0,0 }
};

int i,j;

void fill_the_shape(int ii,int jj)
{
if ((ii >= 0) && (ii < rows) && (jj >= 0) && (ii < cols))
{
if (mat[ii][jj]==ob_col)
{
mat[ii][jj] = mark_col;
fill_the_shape(ii, jj-1);
fill_the_shape(ii, jj+1);
fill_the_shape(ii-1, jj);
fill_the_shape(ii+1, jj);
}
}
}

int find_and_count_shapes()
{
int i_counter = 0;

for (i=0; i< 10; i++)
{
for (j=0; j < 10; j++)
{
cout <<" " << mat[i][j];
}
cout <<"\r\n";
}

for (i=0; i< 10; i++)
for (j=0; j < 10; j++)
{
if (mat[i][j] == ob_col)
{
fill_the_shape(i,j);
i_counter++;
}
}

return i_counter;
}


In the main functions we will call the find_and_count_shapes() function.


cout << "\r\n There is: "<< find_and_count_shapes() <<" shapes \r\n";


Soon, I'll be back with a non-recursive version of this algorithm. ;)

[yiannakop]

Nice job :thumb: . Just one note: in order to apply the region growing algorithm you have implemented in a gray-scale image, you first need to do a kind of thresholding in the image. Otherwise, you can use some some other cretrion directly in the region growing algorithm. For example you could use a texture statistic as a criterion for growing the region in your recursive algorithm.
Regards,
Theodore

[Maximus_X]

As I said, I broke the recursivity of upper function in a normal one. ;)

struct myPixel // my pixel's stack
{
int x;
int y;
};

stack <myPixel> s;
myPixel p;

//************
//
//************

int count_my_shapes()
{
int i_counter = 0;

for (i=0; i < 10; i++)
for (j=0; j < 10; j++)
{

if (mat[i][j] == ob_col)
{
p.x = i;
p.y = j;
mat[i][j] = mark_col;

s.push(p);

i_counter++;

while (!s.empty())
{
myPixel temp = (myPixel)s.top();

int ii = temp.x;
int jj = temp.y;

s.pop();

if (jj > 0)
if (mat[ii][jj-1] == ob_col)
{
p.x = ii;
p.y = jj-1;
mat[ii][jj-1] = mark_col;
s.push(p);
}

if (jj < cols-1)
if (mat[ii][jj+1] == ob_col)
{
p.x = ii;
p.y = jj+1;
mat[ii][jj+1] = mark_col;
s.push(p);
}

if (ii > 0)
if (mat[ii-1][jj] == ob_col)
{
p.x = ii-1; p.y = jj;
mat[ii-1][jj] = mark_col;
s.push(p);
}

if (ii < rows-1)
if (mat[ii+1][jj] == ob_col)
{
p.x = ii+1;
p.y = jj;
mat[ii+1][jj] = mark_col;
s.push(p);
}
}
}
}

return i_counter;
}



Enjoy, yourself! ;)

Theodore, thanks for your advice. My algorithm need to run on a gray palette.
All the best!
Silviu

[cilu]

I have one suggestion (not related to the algorithm itself). Use empty() to test if the stack has elements or not.

Replace:

while (s.size() > 0)

with

while(!s.empty())

[Maximus_X]

I have one suggestion (not related to the algorithm itself). Use empty() to test if the stack has elements or not.

Replace:

while (s.size() > 0)

with

while(!s.empty())


Thanks for your advice. I'll modify that line of the code.

[cilu]

Thanks for your advice. I'll modify that line of the code.
Usually, it's ok to use size(), but for std::list it doesn't have a constant time, so it's better to get accustomed to use empty() instead of size() when checking the emptiness of a containter, for the cases when you'll use a list.

You can read more in Scott Meyer's "Effective STL", Item 4: "Call empty instead of checking size() against zero".

[Maximus_X]

Usually, it's ok to use size(), but for std::list it doesn't have a constant time, so it's better to get accustomed to use empty() instead of size() when checking the emptiness of a containter, for the cases when you'll use a list.

You can read more in Scott Meyer's "Effective STL", Item 4: "Call empty instead of checking size() against zero".

Ok. I understood the ideea. Meantime, i found on my PC this recomanded book and "More Effective STL". :D So, I'll read it. ;)

Going on the ideea of this thread, I merge it with other thread started by me to http://www.codeguru.com/forum/showthread.php?t=395591 so, i'll put down the code of counting shapes in a simple bitmap: :rolleyes:

struct myPixel // my pixel's struct
{
int x;
int y;
};

int FindAndCountShapes(T_UBYTE* pData)
{
int i_counter = 0;

stack <myPixel> s;
myPixel p;


for (int x=0; x < sl_XRES*sl_YRES; x++)
{
m_pTempData[x] = (T_UWORD)pData[x];
}


for (int i=0; i < sl_XRES; i++)
for (int j=0; j < sl_YRES; j++)
{
if ( m_pTempData[ j*sl_XRES + i ] == sl_nuanD)
{ p.x = i;
p.y = j;
m_pTempData[ j*sl_XRES + i ] = sl_mark_col;
s.push(p);

i_counter++;

while (!s.empty())
{
myPixel temp = (myPixel)s.top();

int ii = temp.x;
int jj = temp.y;

s.pop();

if ((jj-1) >= 0)
{
if (m_pTempData[(jj-1)*sl_XRES + ii ] == sl_nuanD)
{
p.x = ii;
p.y = jj-1;
m_pTempData[(jj-1)*sl_XRES + ii ] = sl_mark_col;
s.push(p);
}
}

if ((jj+1 <= sl_YRES-1 ))
{
if (m_pTempData[(jj+1)*sl_XRES + ii ] == sl_nuanD)
{
p.x = ii;
p.y = jj+1;
m_pTempData[(jj+1)*sl_XRES + ii ] = sl_mark_col;
s.push(p);
}
}

if ((ii-1) >= 0)
{
if (m_pTempData[ jj*sl_XRES + ii-1 ] == sl_nuanD)
{
p.x = ii-1;
p.y = jj;
m_pTempData[ jj*sl_XRES + ii-1 ] = sl_mark_col;
s.push(p);
}
}

if ((ii-1) <= sl_XRES-1)
{
if (m_pTempData[ jj*sl_XRES + ii+1 ] == sl_nuanD)
{
p.x = ii+1;
p.y = jj;
m_pTempData[ jj*sl_XRES + ii+1 ] = sl_mark_col;
s.push(p);
}
}
}
}
}

InvalidateRect(&prect,FALSE);

return i_counter;
}

where pData pointer contains the bitmap image. ;)

Enjoy yourself! :thumb: