April 5, 2008
WikiConvolution
Convolution
Discrete convolutions are heavily used in image processing for image smoothing, crispending, edge detection, and other effects. A convolution is merely a weighted sum of pixels in the neighborhood of the source pixel. The weights are determined by a small matrix called the convolution mask or convolution kernel. The dimensions of the matrix are usually odd so that a center can be determined. The location of the center corresponds to the location of the output pixel.
A sliding window called the convolution window centers on each pixel in an input image and generates new output pixels. The new pixel value is computed by multiplying each pixel value in the neighhborhood with the corresponding weight in the convolution mask and summing these products.
It is very important to place the new pixels into a new image, if the newly generated pixel replaces the old pixel, it will be used to calculate the value of the next new pixel. This is known as an infinite impulse response system and will not yield the desired results.
The sum of the weights in the convolution mask affect the overall intensity of the resulting image. Many convolution masks have coefficients that sum to 1. In this case, the convolved image will have the same average intensity as the original image. Some convolution masks(like many used in edge detection) have negative coefficients and sum to 0. In this case, negative pixel values may be generated. Typically, a constant is added to the newly generated pixel (like maximum intensity/2), if that addition results in a negative number, it is set to 0.
The first question you may have when implementing a convolution function is how to treat the image borders. When the convolution window is centered on the first pixel of an image 0,0, the sliding window overlaps the image on the top and left edge. What values should be multiplied by those convolution coefficients hanging over the edges? There are several ways to attack to this problem.
The first solution is to treat the empty cells in the convolution window as zeros. This is known as zero-padding. This is easy to do but not a good idea if the edges of the resulting image are just as important as the rest of the image.
The next solution is to start convolving at the first position where the window doesn’t overlap the image. If your convolution mask is 3x3 start convolving with the pixel at 1,1 instead of the pixel at 0,0. This is simple to implement and I’ve done this in the convolution code. In the output image, the convolved edges are copied to create an image with the same resolution as the input image.
Blurring
Blurring or lowpass spatial filtering removesthe finer details of an image. Surprisingly, it has a number of applications. It is sometimes used to simulate a camera out of focus, or to de-emphasize a background.
Blurring is accomplished through convolution. In one common blurring mask, all convolution coefficients are equal. In a 3x3 mask, all the elements are equal 1/9. In a 5x5 mask, all elements equal 1/25. It is easy to see from the weighting in the convolution mask that blurring is simply neighborhood averaging. Using a 3x3 mask, you add the nine elements and divide by 9. Averaging tends to remove extreme values from a group. Extremely light/dark pixels can be made more gray depending on the pixel’s neighborhood. The bigger the mask, the greater the blurring effect and the greater the computation time required.
Sharpening
Sharpening has the opposite affect of blurring. Sharpening also referred to as crispening emphasizes the details in an image. When images are fuzzy either before or during image acquisition it is possible to restore them to an acceptable state via sharpening. Sharpening an image will increase its contrast.
The convolution mask used in sharpening has a positive coefficient in its center and mostly negative coefficients around the outer edge. Some common sharpening masks are
|0|-1|0| |-1|5|-1| |0|-1|0|
Sharpening an image is based on the highpass filter. A highpass filter will remove the low frequency components (like the image’s mean) and show only high details. Coefficient sum up to 0. Some bias value will need to be added to the output to offset the negative values.
Another method of highpass filtering is to subtract a lowpass filtered image from its original. This is known as unsharp masking a term borrowed from the field of photography.
Step by Step
In our drawToBuffer function we do have an array:
double Matrix[121]={-1,-1,-1,-1,9,-1,-1,-1,-1};
the reason that we make this array size 121 is we can go up to 11x11 mask. The elements that are there for now resembles a sharpening convolution. Addition to that we have two variables in this function which are MatrixSize and Radius. The Radius is the size of the square around the mouse to be influenced.
We could have used a for loop to fill our Matrix array in any way we want. For example for a blur effect we could just use this:
for (i = 0; i< MatrixSize*MatrixSize;i++){
Matrix[i] = 1 /(double)( MatrixSize*MatrixSize)
}
We shouldn’t forget that we need to restrict accessing to the edge pixels. In order to do that we will use these two lines.
CLIP (mousepoint.h,MatrixSize/2+Radius,windRect.right-MatrixSize/2-Radius);
CLIP (mousepoint.v,MatrixSize/2+Radius,windRect.bottom-MatrixSize/2-Radius);
Those are callled MACROS in C. Those have to be defined in the header of the program. Here is the definition that should go between function declarations and global variables.
#define CLIP(val, low, high) {if(val<low) val=low; else if(val>high)val=high;}
Then we are calling our convolve function in a double loop which will effect the radius we have just declared.
for(x=mousepoint.h-Radius;x<mousepoint.h+Radius;x++){
for(y=mousepoint.v-Radius;y<mousepoint.v+Radius;y++){
Convolve(x,y,&R,&G,&B,MatrixSize,Matrix,imageRowBytes,imageBaseAddress);
ourSetPixel(x,y,R,G,B,bufferRowBytes,bufferBaseAddress);
}
}
Convolve function is pretty straightforward.
void Convolve(unsigned short horizontal,unsigned short vertical,unsigned char* R,unsigned char* G,unsigned char* B,int MatrixSize,double* Matrix,unsigned short rowbytes,Ptr pixbase){
long x,y,halfMatrix, countMatrix;
double sumR=0,sumG=0,sumB=0;
double temp;
Ptr AdressOfRed;
halfMatrix = MatrixSize/2;
for (x=-halfMatrix;x<MatrixSize-halfMatrix;x++){
for (y=-halfMatrix;y<MatrixSize-halfMatrix;y++){
AdressOfRed = rowbytes * (vertical+y) +pixbase+(horizontal+x)*4+1;
temp = (unsigned char)*(AdressOfRed);
sumR += (temp * Matrix[countMatrix]);
temp = (unsigned char)*(AdressOfRed+1);
sumG += (temp * Matrix[countMatrix]);
temp = (unsigned char)*(AdressOfRed+2);
sumB += (temp * Matrix[countMatrix]);
countMatrix++;
}
}
CLIP( sumR,0,255);
CLIP( sumG,0,255);
CLIP( sumB,0,255);
*R = sumR;
*G = sumG;
*B = sumB;
}
Source Code
void Initialize(void); // function prototypes
void DrawLine( void );
void doEventLoop( void );
void DrawToBuffer(void);
void CopyToWindow (void);
int ourRandom( int min, int max );
void ourSetPixel(unsigned short horizontal,unsigned short vertical,unsigned char R,unsigned char G,unsigned char B,unsigned short rowbytes,Ptr pixbase);
void ourGetPixel(unsigned short horizontal,unsigned short vertical,unsigned char* R,unsigned char* G,unsigned char* B,unsigned short rowbytes,Ptr pixbase);
void ImportFile(GWorldPtr destWorld,int left,int top,int right, int bottom);
void Convolve(unsigned short horizontal,unsigned short vertical,unsigned char* R,unsigned char* G,unsigned char* B,int MatrixSize,double* Matrix,unsigned short rowbytes,Ptr pixbase);
#define CLIP(val, low, high) {if(val<low) val=low; else if(val>high)val=high;}
//globals
WindowPtr ourWindow;
Rect windRect;
GWorldPtr ourBuffer,ourImage;
int count=0;
void DrawToBuffer(void) // this is where the interesting stuff happens, this is where we actually set our pixels
{
long x , y,temp,distance;
Point mousepoint;
unsigned short bufferRowBytes,imageRowBytes ;
Ptr bufferBaseAddress,imageBaseAddress;
PixMapHandle bufferPixmap, imagePixmap;
unsigned char R,G,B;
double Matrix[121]={-1,-1,-1,-1,9,-1,-1,-1,-1};// sharpen
// floating point number?
// which allows you to do 11X11.
// next thing to do is we need to populate this array with numbers.
/*
replacing lineer array into 2d array.
*/
int MatrixSize,Radius,i;
count++;
GetMouse(&mousepoint);
bufferPixmap=GetGWorldPixMap(ourBuffer); // getting the pixel map of our buffer GWorld so that we can access the pixels
bufferRowBytes = ((*(bufferPixmap))->rowBytes) & 0x7fff; * getting the number of bytes in each row of the pixel map. This is then used to * calculate the location in memory of specific pixels
bufferBaseAddress = GetPixBaseAddr(bufferPixmap ); // getting the base address in memory of the begining of the pixel data
imagePixmap=GetGWorldPixMap(ourImage); // getting the pixel map of our buffer GWorld so that we can access the pixels
imageRowBytes = ((*(imagePixmap))->rowBytes) & 0x7fff; * getting the number of bytes in each row of the pixel map. This is then used to * calculate the location in memory of specific pixels
imageBaseAddress = GetPixBaseAddr(imagePixmap );
CopyBits( GetPortBitMapForCopyBits( ourImage ), GetPortBitMapForCopyBits( ourBuffer ),
&windRect, &windRect, srcCopy, NULL ); // copying the image to our buffer, this erases anything we did last frame
MatrixSize = 7; // size of our matrix
Radius = 50; // the size of the square around the mouse that will be influenced
for (i = 0; i< MatrixSize*MatrixSize;i++){
Matrix[i] = 1/(double)( MatrixSize*MatrixSize);
// filling our matrix with values in this case all equal
// all of them together need to sum up to 1. above of that color will be brighter. down will be darker.
// we cannot go closer tot he edge more than 4th pixel.
}
CLIP (mousepoint.h,MatrixSize/2+Radius,windRect.right-MatrixSize/2-Radius);
// making sure we will not be accessing pixels that are outside of the pixelmap
CLIP (mousepoint.v,MatrixSize/2+Radius,windRect.bottom-MatrixSize/2-Radius);
// idea of macros
// similar to function.
// what we do is just use a macro define it at the top, and then call this when we need this.
for(x=mousepoint.h-Radius;x<mousepoint.h+Radius;x++){
for(y=mousepoint.v-Radius;y<mousepoint.v+Radius;y++){
Convolve(x,y,&R,&G,&B,MatrixSize,Matrix,imageRowBytes,imageBaseAddress); // calling the Convolve() method using our matrix
ourSetPixel(x,y,R,G,B,bufferRowBytes,bufferBaseAddress); // setting the new RGB values
}
}
//for a smudge effect, copy the result back to the image buffer
// CopyBits( GetPortBitMapForCopyBits( ourBuffer ), GetPortBitMapForCopyBits( ourImage ),
// &windRect, &windRect, srcCopy, NULL );
}
void CopyToWindow (void){ // copy all our buffer to the window, completely replaceing
// everything that was there
Rect sourceRect,destRect;
SetPortWindowPort(ourWindow);
GetPortBounds( GetWindowPort(ourWindow), &destRect );
GetPortBounds( ourBuffer, &sourceRect );
CopyBits( GetPortBitMapForCopyBits( ourBuffer ), GetPortBitMapForCopyBits(GetWindowPort(ourWindow)),
&sourceRect, &destRect, srcCopy, NULL );
}
void main( void )
{
Initialize();
doEventLoop();
}
void Initialize(void){
OSErr error;
SetRect(&windRect,100,100,740,580);
InitCursor();
ourWindow = NewCWindow( 0L, &windRect, "\pConvolution", true, noGrowDocProc,(WindowPtr)-1L, true, 0L );
if ( ourWindow == nil ) ExitToShell();
ShowWindow( ourWindow );
SetPortWindowPort( ourWindow );
SetRect(&windRect,0,0,640,480);
error =NewGWorld(&ourBuffer, 32, &windRect, nil, nil,0 ); // creating our offscreen buffer
if (error != noErr ) ExitToShell();
error =NewGWorld(&ourImage, 32, &windRect, nil, nil,0 );
if (error != noErr ) ExitToShell();
ImportFile(ourImage,0,0,640,480); // Calling our method that opens a picture file and returns a picture handle
}
/*************** The Event Loop ***************/
void doEventLoop()
{
EventRecord anEvent;
WindowPtr evtWind;
short clickArea;
Rect screenRect;
Point thePoint;
for (;;){
if (WaitNextEvent( everyEvent, &anEvent, 0, nil )){
if (anEvent.what == mouseDown){
clickArea = FindWindow( anEvent.where, &evtWind );
if (clickArea == inDrag){
GetRegionBounds( GetGrayRgn(), &screenRect );
DragWindow( evtWind, anEvent.where, &screenRect );
}
else if (clickArea == inContent){
if (evtWind != FrontWindow())
SelectWindow( evtWind );
else{
thePoint = anEvent.where;
GlobalToLocal( &thePoint );
}
}
else if (clickArea == inGoAway)
if (TrackGoAway( evtWind, anEvent.where ))
return;
}
}
DrawToBuffer(); // after checking for various events we call our drawing finctions
CopyToWindow();
}
}
int ourRandom( int min, int max ){ // method that returns a random number between min and max
return( (Random()+32768) /((32768*2/) (max-min)))+ min;
}
void ourSetPixel(unsigned short horizontal,unsigned short vertical,unsigned char R,unsigned char G,unsigned char B,unsigned short rowbytes,Ptr pixbase){
Ptr AdressOfRed;
AdressOfRed = rowbytes * vertical +pixbase+horizontal*4+1;
*(AdressOfRed)=R;
*(AdressOfRed+1)=G;
*(AdressOfRed+2)=B;
}
void ourGetPixel(unsigned short horizontal,unsigned short vertical,unsigned char* R,unsigned char* G,unsigned char* B,unsigned short rowbytes,Ptr pixbase){
Ptr AdressOfRed;
AdressOfRed = rowbytes * vertical +pixbase+horizontal*4+1;
*R=*(AdressOfRed);
*G=*(AdressOfRed+1);
*B=*(AdressOfRed+2);
}
void Convolve(unsigned short horizontal,unsigned short vertical,unsigned char* R,unsigned char* G,unsigned char* B,int MatrixSize,double* Matrix,unsigned short rowbytes,Ptr pixbase){
long x,y,halfMatrix ,countMatrix =0,sumMatrix=0;
double sumR=0,sumG=0,sumB=0;
double temp;
Ptr AdressOfRed;
halfMatrix = MatrixSize/2;
for (x=-halfMatrix;x<MatrixSize-halfMatrix;x++){
for (y=-halfMatrix;y<MatrixSize-halfMatrix;y++){
AdressOfRed = rowbytes * (vertical+y) +pixbase+(horizontal+x)*4+1;
temp = (unsigned char)*(AdressOfRed);
sumR += (temp * Matrix[countMatrix]);
temp = (unsigned char)*(AdressOfRed+1);
sumG += (temp * Matrix[countMatrix]);
temp = (unsigned char)*(AdressOfRed+2);
sumB += (temp * Matrix[countMatrix]);
countMatrix++;
}
}
CLIP( sumR,0,255); // calles the CLIP macro that makes sure that the value is between 0 and 255
CLIP( sumG,0,255);
CLIP( sumB,0,255);
*R = sumR;
*G = sumG;
*B = sumB;
}
void ImportFile(GWorldPtr destWorld,int left,int top,int right, int bottom){ // this method imports a file and returns a picture handle . it uses Quicktime so it can
// import almost any file format including JPG , Pict, Photoshop, EPS, BMP, GIF and many more.
Rect recti; // you must have the QuickTime.lib in your project to compile, and have Quicktime installed to run
PicHandle theNewPic;
OSErr myError;
ComponentInstance gi;
FSSpec fsp;
Point where;
AEKeyword myKeyword;
DescType myActualType;
Size myActualSize ;
NavReplyRecord navreply;
where.h=200; where.v=100; /* where the Standard File dialog window goes */
NavGetFile (NULL, &navreply,NULL,NULL,NULL,NULL,NULL,NULL);
if (AEGetNthPtr(&(navreply.selection), 1, typeFSS, &myKeyword, &myActualType, &fsp, sizeof(fsp), &myActualSize)!= noErr) SysBeep(10);
myError=GetGraphicsImporterForFile(&fsp,&gi);
myError=GraphicsImportGetAsPicture (gi,&theNewPic);
CloseComponent(gi);
SetRect(&recti,left,top,right,bottom);
SetPort((GrafPtr)destWorld);
DrawPicture(theNewPic,&recti); // drawing the imported picture onto the second buffer
KillPicture(theNewPic);
}
Continue Reading
Back to Archive