[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
Solved

# Gradient value of an image

Posted on 2009-03-31
Medium Priority
758 Views
Hi Experts,
I would like to  build the following sum (gradient calculation) of a 8 bit monochromatic image (bitmap) with a resolution of 640x480 in an effective way:

j=rows-1        i=cols-1
Sum            Sum   ((A[i][j]-A[i+1][j])*(A[i][j]-A[i+1][j]))+((A[i][j]-A[i][j+1])*(A[i][j]-A[i][j+1]))
j=0              i=0

where the first sum runs from j=0 to j=number of rows and the second sum from i=0 to i= number of columns  and A[i][j] ist the pixel intensity at the position (i,j). I've created a mfc dialog and here is coding:

void CImageAppDlg::OnBnClickedButton()
{
// m_MyBmp ist der member variable associated to the picture control
m_MyBmp.SetBitmap( hBmp );

CBitmap* pcBmp= CBitmap::FromHandle( hBmp );

BITMAP rBmp;
int n= pcBmp->GetBitmap( &rBmp );

const int nWide= rBmp.bmWidth;
const int nHigh= rBmp.bmHeight;

BYTE abPixels[640][480];

CDC* pCDC= m_MyBmp.GetWindowDC();
int x,y;
int Summe;
Summe=0;
for ( y=0; y<(nHigh-1); y++ ){
for ( x=0; x<(nWide-1); x++ ){
COLORREF clrRGB= pCDC->GetPixel(x,y);
abPixels[x][y]= GetRValue( clrRGB );
Summe+=((abPixels[x][y]-abPixels[x+1][y])*(abPixels[x][y]-abPixels[x+1][y]))+
((abPixels[x][y]-abPixels[x][y+1])*(abPixels[x][y]-abPixels[x][y+1]));
}
}

CString s;
s.Format( L"Summe=%d", Summe );
MessageBox( s );
}

I tested  the coding above with the attached file below and I'm not sure if the implementation is correct...
Thank you

Notebook.bmp
0
Question by:andy06
• 4
• 3
• 2
• +1

LVL 85

Expert Comment

ID: 24036091

abPixels[x][y]= GetRValue( clrRGB );
Summe+=((abPixels[x][y]-abPixels[x+1][y])*(abPixels[x][y]-abPixels[x+1][y]))+
((abPixels[x][y]-abPixels[x][y+1])*(abPixels[x][y]-abPixels[x][y+1]));
You  seem to be looking at abPixels[x+1][y] and abPixels[x][y+1] before setting it
0

LVL 49

Expert Comment

ID: 24036116
Indeed.  You need to do a GetPixel on each of the surrounding pixels (each that will be included in the sum).
As this is a grayscale, you can work with any one of the RGB values (they are all the same).  But when you set them back into the bitmap or into another bitmap, be sure to set R,G, and B to the same value.
0

Author Comment

ID: 24036563
>You need to do a GetPixel on each of the surrounding pixels (each that will be included in the sum).

So, if I've understood you mean I have to add something like the following right:
COLORREF clrRGB1= pCDC->GetPixel(x+1,y);
COLORREF clrRGB2= pCDC->GetPixel(x,y+1);

abPixels[x+1][y]= GetRValue(clrRGB1);
abPixels[x][y+1]= GetRValue(clrRGB2);
0

LVL 85

Expert Comment

ID: 24036597
A simpler way to do it may be to run the loops backward.

But be careful of boundary conditions.

as written you never take abPixels[x][nHigh-1]-abPixels[x+1][hHigh-1]
or abPixels[nWide-1][y]-abPixels[nWide-1][y+1]
I don't know if that matters to anything
0

LVL 18

Expert Comment

ID: 24044169
Something strange at first glance.
The image is 8 bits per pixel in grey scale. This is a byte lenght.
By calling GetRValue( clrRGB ), the program gets the red component of a grey image...
Also, clrRGB is supposed to be a DWORD, say 32 bits long.
The result is very close to the real one because most of the pixels are sampled anyway.
I'll look deeply later.
Jose
0

LVL 49

Expert Comment

ID: 24044666
(abPixels[x][y]-abPixels[x+1][y]) * (abPixels[x][y]-abPixels[x+1][y])
+
(abPixels[x][y]-abPixels[x][y+1]) * (abPixels[x][y]-abPixels[x][y+1])

In words, the gradient calculation is:
The difference between this pixel and the one to the right, squared
plus
The difference between this pixel and the one below, squared

Let's look at some examples.  The focus pixel is pure white (255) and the neighbors are pure black (0)
[  ] [#]
[#]
((255-0)*(255-0)) + ((255-0)*(255-0))
255*255 + 255*255= 130050

The focus pixel is black (0) and the neighbors are white (255)
[#] [  ]
[  ]
((0-255)*(0-255)) + ((0-255)*(0-255))
-255*-255 + -255*-255= 130050

The focus pixel is grey (128) and the neighbors are white (255)
[::] [  ]
[  ]
((128-255)*(128-255)) + ((128-255)*(128-255))
-127*-127 + -127*-127= 32258
The focus pixel is grey (128) and the neighbors are grey (128)
[::] [::]
[::]
((128-128)*(128-128)) + ((128-128)*(128-128))
0*0 + 0*0= 0

So you will be summing up about 300,000 values ranging from 0 to 130,050.  Most of the time, the slope will be much closer to 0, but in a worst case scenario (checkerboard), your Summe variable will be 39,951,360,000 that is, (640*480)*130,050 which will overflow an integer variable.   Unlikely but possible, so you need to guard against it.

For clarity, I'd use this sort of code in the inner loop:
int nThis= pCDC->GetRValue( GetPixel(x,y) );
int nRight= pCDC->GetRValue( GetPixel(x+1,y) );
int nBelow= pCDC->GetRValue( GetPixel(x,y+1) );
int nDeltaRight= nThis-nRight;
int nDeltaBelow= nThis-nBelow;
Summe += (nDeltaRight*nDeltaRight)+(nDeltaBelow*nDeltaBelow);

It contains intermediate steps, but if you are worrying about efficiency, that is the least of your worries.  The real time killer will be the three calls to GetPixel for each pixel.  There are several ways to speed that up, including one complicated one, but we can worry about efficiency once the main algorithm is working.
-- Dan
0

Author Comment

ID: 24048278
> which will overflow an integer variable.Unlikely but possible, so you need to guard against it.
Thank you about the hint. I didn't even think about that possibility...

I've checked the limits header (#include ) and found the following:
#define INT_MIN            (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX            2147483647        /* maximum (signed) int value */
So I could declare my Summe variable as double right?

>>The real time killer will be the three calls to GetPixel for each pixel. There are several ways to speed that up, including one complicated one
how could that look like?
Andy

0

LVL 49

Accepted Solution

DanRollins earned 750 total points
ID: 24055295
Yes, I'd suggest using a double rather than an int for the Summe variable.
As to the alternative, faster ways to do this, they are (in brief):
1) create a 2-D array with the GetRValue() responses for every pixel, then access that array rather than doing GetPixel.  That way, you would need to use GetPixel() only once per pixel.  It would still be slow, but it will take about 1/3rd of the time.
2) Use CDC.GetBitMap, then CBitmap.GetBitmapBits that gives you a buffer full of pixel data.  You can now write specialized code to access individual values -- in effect providing your own GetPixel functions that will probably be much faster than making hundreds of thousands of call to the GetPixel() API.
I'd rather not move in that direction until you have working code using the simpler GetPixel code.  I see that you are rather new ro programming and I know that adding such complications will only make your task more difficult, and if GetPixel is fast enough, then there is no need to go there.  There is a well-know developer's maxim:  Don't start optimizing until you actully need to.
0

LVL 85

Assisted Solution

ozo earned 750 total points
ID: 24055601
after your loop, abPixels will be a 2-D array with the GetRValue() responses for every pixel,
so a simple way do it could separate your function into two loops, one to fill abPixels , and one that access that array .

A different approach, since the sums of vertical and horizontal differences are independent.
could be to run one loop to sum all the vertical differences and one loop to sum all the horizontal differences.
each of which would only need to save a single GetRValue(), so you wouldn't need a 2-D array

But I agree that you should get the code working first.
Until you understand how to do that, you probably won't understand how to do it without the array
0

LVL 49

Expert Comment

ID: 24076475
You might look in on...  What's the right grade to give  Experts might work even harder for you in the future if you awward more As than Bs.  Just a thought.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your Uā¦
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By ādivisibleā we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). Weāll follow multiple approacā¦
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201ā¦
###### Suggested Courses
Course of the Month18 days, 14 hours left to enroll