Contents  Introduction  Convolution  Code  Filters  Edge Enhancement  Edge Detection  Tips and Tricks  Printable version

Alright, I have explained all the normal kernals. Now for some tips and tricks. Here's one: most of the kernals that we've gone through can be rotated. For example - take the sobel horizontal from above and rotate it 45 degrees. The table on the left is the original sobel, the table on the right is the rotated sobel:

Another neat trick is to modify the kernal size. Usually if you want less of an effect, you use a larger kernal. However, there are better uses. In edge enhancement (gradient filters especially), you can actually identify lines and other neat stuff. With a kernal size of 3x3, it is hard to identify lines, for things that aren't supposed to be highlighted are. However, if you extend the kernal into a larger size, it is easier to identify objects - at the cost of more processing time. Here's an example of how to detect a horizontal line:

In fact, it is indeed possible to construct templates which can detect a specific shape in an image. These templates are very large kernals and contain characteristics of the object. The above filter that detects horizontal lines is shown in HORIZ1.CPP. The first screen is the original image, the second is when you pass it through a 3x3 filter, the third is when you pass it through a 7x3 filter, exactly like above. Here is the difference this makes:

More advanced digital filtering techniques involve statistical (nonlinear) convolution and using cross convolution, but the above filters should keep you busy for quite a while. Now I'll focus on a "true" filter procedure and optimization.

Take a look at NEAT1.CPP. This was my earliest attempt from many years ago to create a graphics primitive library. None of the shape-drawing routines are optimized at all, but it is fast enough for our purposes. Now, the program is key-sensitive: press ‘b' and the program will draw its neat little shapes. Press ‘a', and the program will first pass the image through a filter, then draw the filtered image. Press ‘x' and the program will terminate. So, what I've tried to do is implement a filter through an animation in real-time. It uses FILTER.H from above. It has two main problems. The first is obvious: it's SLOW. This is a major obstacle, for we're talking game programming here: every nanosecond counts! I'll tackle this problem last, since the next problem will require a major rewrite of FILTER.H.

The second problem is that FILTER.H uses 8-bit terminology. It assumes the palette is correctly set for digital filtering. This means that if you blur color 50 of an image to color 49, 49 should look pretty close to 50, but not be 50. However, this is 8-bit: every color definition can be extremely different. If you want to blur color 50, and you end up with color 49, and color 49 looks nothing like color 50, you have a problem. There are a number of ways to solve this problem. One is to arrange your palette so that colors 1-10 are similar, colors 11-20 are similar, etc. However, this is impractical and timecomsuming. Let's rip up FILTER.H's 8-bit filtering system and make it 24-bit, where every color is not defined by a palette, but by the color itself.

OK, we're gonna make a 24-bit FILTER.H. What does that mean? Well, in a 24-bit color mode, every color is defined by 24-bits, making a possible 16.7 million colors. Yet you don't use a palette with 16.7 million colors in it to draw pictures on the screen. The bits in the 24-bit number describe what the color looks like - you don't need a palette. Essentially, it can be divided into 3 byte (8-bit) color attributes: red, green, and blue. Mixing and matching different amounts of these color attributes will make any color in the visible color spectrum. The 24-bit version is called FILTER2.H, and you can download it here and at the end of the article.

int Filter(Picture &Source,Picture &Dest,unsigned short Filt) {
   if((Dest.picture=new unsigned char[Source.x*Source.y*3])==NULL)
      return 1; // Error allocating memory for Dest picture
   Dest.x=Source.x;
   Dest.y=Source.y;
   signed long numb;
   for(unsigned short x=0;x<Dest.x;x++)
      for(unsigned short y=0;y<Dest.y;y++) {
         if((x)&&(y)&&(x!=Dest.x-1)&&(y!=Dest.y-1)) {

It starts out almost exactly like FILTER.H. The only difference here is that Dest.picture is allocated three times the original amount of memory. This is because we are dealing with 24-bits (3 bytes), not just 8-bits (1 byte) anymore.

            numb=(long)((Source.picture[(((y-1)*Source.x+(x-1))*3)+0]*Filters[Filt]+
               Source.picture[(((y-1)*Source.x+(x ))*3)+0]*Filters[Filt+1]+
               Source.picture[(((y-1)*Source.x+(x+1))*3)+0]*Filters[Filt+2]+
               Source.picture[(((y )*Source.x+(x-1))*3)+0]*Filters[Filt+3]+
               Source.picture[(((y )*Source.x+(x ))*3)+0]*Filters[Filt+4]+
               Source.picture[(((y )*Source.x+(x+1))*3)+0]*Filters[Filt+5]+
               Source.picture[(((y+1)*Source.x+(x-1))*3)+0]*Filters[Filt+6]+
               Source.picture[(((y+1)*Source.x+(x ))*3)+0]*Filters[Filt+7]+
               Source.picture[(((y+1)*Source.x+(x+1))*3)+0]*Filters[Filt+8]));
            if(numb)
               numb/=(long)Filters[Filt+9];
            if(numb>0)
               Dest.picture[(y*Dest.x+x)*3+0]=(unsigned char)numb;
            else
               Dest.picture[(y*Dest.x+x)*3+0]=0;

Now things get a little interesting. This calculates the first of the three bytes (Red).The above procedure is actually repeated two more times, for green and blue. For green, all the +0's become +1, and for blue, all the +0's become +2. This is because every pixel on the screen takes 3 bytes, one for red, one for green, and one for blue. It is necessary to calculate each part of the color separately. Other than that, it is exactly like FILTER.H. The pointer into Source.picture works in the following way. The pixel pointer (y*Source.x+x) is multiplied by 3 (24-bits, not 8), and an addition is made to separate the different parts of the color (+0=Red, +1=Green, and +2=Blue).

         } else {
            Dest.picture[(y*Dest.x+x)*3+0]=Source.picture[(y*Dest.x+x)*3+0];
            Dest.picture[(y*Dest.x+x)*3+1]=Source.picture[(y*Dest.x+x)*3+1];
            Dest.picture[(y*Dest.x+x)*3+2]=Source.picture[(y*Dest.x+x)*3+2];
         }
      }
   return 0; // No error
}

The above occurs if the pixel is on a side. If you remember, pixels on the side of an image are simply copied. This works exactly like FILTER.H, except that this is 24-bit.

NEAT3.CPP uses the above filter. Note how SLOW it is. Without the filter, it runs on my computer at about 38.7 frames per second. With the filter, that number quickly shrinks to 5.7 frames per second. That's 7 times slower!!! In haste, I've implemented a few optimizations and stored it in FILTER3.H, which is used in NEAT4.CPP. It isn't the most optimized I could make it, and I made no changes to the unoptimized graphics primitives. Here's what I did.

• No more NEW!!!! I got rid of the new command which creates the output bitmap every single time you call Filter(). It's a big waste of time to keep deleting and creating an array you're going to keep using anyway. So, why bother? No more new.
• It doesn't return a value anymore. This doesn't do much for speed, but the only reason why I had a return value in the first place was if the new command failed. Since we don't have new anymore, we don't need to return a value.
• No more useless ‘+0' additions. Notice those calculations where I add zero to the pointers? I put it in for clarity. No need for that when you're busy optimizing. I omitted all calculations where you add zeros.
• Use of offsets. This yielded the best optimization. For each of the three times you call the pointer, you multiply and add the same stuff: (y*Dest.x+x)*3. I stored this and other frequently used calculations in offsets. This really sped things up.
• Dest.x and Dest.y aren't initialized anymore. This was just cleanup. No big speed advantage here.
• Borders are done manually. In the old Filter(), I went through every single pixel. Then there was a complicated if command which tested to see if it was a border line or not. If it was, it just copied the original contents. If it wasn't, it was time for some filtering. This takes time, so I did the filtering and copying separately. Take a look at the code that does this. Much quicker than the obvious solution.
• Numb of your business. The variable numb went through some useless if commands. I did away with those.

This sped up the procedure a little. Other possible optimizations would require a major rewrite, and I did not include these in the context of this article. I have also included NEAT5.CPP, which implements all the other filters. Pretty much every letter and number trigger a different filter. Type "x" to exit. I hope this article has been enlightening and that you will have fun with digital filtering in the future.

All the topics in this article can be downloaded here in a single download:

FILTER.ZIP

Thanks for your interest!

Ender Wiggin

EnderWiggenRules@aol.com