Solved

Gradient value of an image

Posted on 2009-03-31
10
728 Views
Last Modified: 2013-11-26
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()
{
                   HBITMAP hBmp= (HBITMAP)LoadImage(NULL,L"C:\\Notebook.bmp", IMAGE_BITMAP, 0, 0,    LR_LOADFROMFILE);
                   // 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
Comment
Question by:andy06
  • 4
  • 3
  • 2
  • +1
10 Comments
 
LVL 84

Expert Comment

by:ozo
Comment Utility

                  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

by:DanRollins
Comment Utility
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

by:andy06
Comment Utility
>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 84

Expert Comment

by:ozo
Comment Utility
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

by:JoseParrot
Comment Utility
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
Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

 
LVL 49

Expert Comment

by:DanRollins
Comment Utility
(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

by:andy06
Comment Utility
> 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

by:
DanRollins earned 250 total points
Comment Utility
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 84

Assisted Solution

by:ozo
ozo earned 250 total points
Comment Utility
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

by:DanRollins
Comment Utility
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

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
how to split multiple lines delimiter : 8 53
Linux operating system 12 64
Get String split 5 31
Showdialog 8 20
If you use Adobe Reader X it is possible you can't open OLE PDF documents in the standard. The reason is the 'save box mode' in adobe reader X. Many people think the protected Mode of adobe reader x is only to stop the write access. But this fe…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
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.
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now