Title: Convolution
Question: A little bit about convolution
Answer:
In this article, I want to demonstrate how easy is to create graphical filters. This is a part of a large tutorial (maybe a book if I can finish it and anyone is interested in it) about creating complex graphical interfaces.
We will create a special routine that is able to apply special effects on a image. This routine is CONVOLUTION. What does it mean? Convolution is a routine that applies some special distortions to an image. Lets understand how it works.
Suppose you have an image(bitmap). It is a collection of points with different colors. In fact, a color is a number that specify the color to use.
Convoluting an image is a process of changing the pixels values based on the neighbor pixels. Generally we will work with a 3X3 matrix of pixels, like bellow:
P1 P2 P3
P4 PC P6
P7 P8 P9
PC will be named the Source Pixel. For each pixel in this matrix we will apply a process of multiplication with values in the other matrix named filter:
F1 F2 F3
F4 F5 F6
F7 F8 F9
We will obtain an intermediate matrix like:
IM1 IM2 IM3
IM4 IM5 IM6
IM7 IM8 IM9
Where IMi=Pi*Fi, for i=1..9. Now we will calculate the final value of PC using the formula:
PC_Final_Value=(IM1+IM2+IM3+IM4+IM5+IM6+IM7+IM8+IM9)/divisor,
Where divisor is a user defined value (it depends on the filter you want to use). This process will be repeated for each pixel in our image. The result is a filtered image. Simple, isnt it?
A little bit about speed
Delphi came with canvas object. A graphical control easy to use. But the problem of canvases is the access of individual pixels. If you want to use the pixels property of a canvas you will have big problems. So we will use for our implementation the Scanline property of a bitmap. The Scanline allows you to access the bitmap pixel rapidly. The big problem of scanline is its quite cryptic using. That because the scanline is called differently, depending on the bitmap PixelFormat property.
PixelFormat property of a bitmap is (using a simple definition) the number of colors used by this bitmap. So, the PixelFormat is defined by Borland like:
TPixelFormat = (pfDevice, pf1bit, pf4bit, pf8bit, pf15bit, pf16bit, pf24bit, pf32bit, pfCustom);
In fact this is the representation of pixel in memory. For pf1bit we have only two different values for the pixel (1 and 0) so it is represented using only 1 bit. For simplicity and efficiency, we will work first only with pf8bit bitmaps. Why? Because for our graphical effects 256 colors are enough and because using the scanline with this type of bitmaps is very easy. The pixel is represented in one byte. Look at the following example and you will see how easy is to read each individual pixel using this bitmap type:
procedure Read_Each_Pixel(bmp:Tbitmap);
var
i,j:integer;
row:TByteArray;
mypixel:byte;
begin
if bmp.pixelformatpf8bit then exit; //this is most important for our use!!
for i:=0 to bmp.height-1 do
begin
Row:=bmp.scanline[I];
For j:=0 to bmp.width-1 do
Mypixel:=Row[j]
end;
end;
In this example, the pixel value is passed to mypixel. My pixel is a byte. Thats because the number of colors of our bitmap is 256. So we can fast access and apply our calculations for pixels. Lets look on our convolvig routine. We will start with defining the filter:
TFilter=record
TheMatrix=array[0..2,0..2] of byte;
Divisor:integer;
End;
So, in this format we will be able to access easily the filter. Now we can start coding the body of our convolving routine. But first don't forget to establish what happened for the top, bottom left and right pixels. These pixels have not the complete numbers of neighbors, so we must consider this situations in order to prevent some bad errors. We will consider the first two left, right, top and bottom lines/rows of pixels. Checking the values for these pixels can be trapped using if ..then blocks, but this is time consuming. So we will use a little trick. First we will create an enlarged bitmap. Suppose our original bitmap has a (x,y) dimension. The new bitmap we will create will has (x+2, y+2) dimension. Then, we will copy the original bitmap at (1,1) point. The new bitmap will look like in the following figure:
Now all seems to be OK. You can now look in the attached unit (rbsfilter.pas) at the convolve function. Bellow, I will describe only how it works:
The function Convolve has two parameters: bmp (the source bitmap) and Filter (the filter we want to use).
First we must verify if the source bitmap is pf8bit format. If not, the function will return the original bitmap. Then, we have to create the tempBitmap. and apply the filter. Finally we return the resulted bitmap and free the tempbitmap. Its like a piece of cake. The process of writing the final pixel value, you can see in the following code snippet:
function Convolve(bmp:TBitmap; filter:TFilter):TBitmap;
var TempBitmap:TBitmap;
Line1, line2, line3: pByteArray;
LineFinal:pByteArray;
i,j:Integer;
r:TRect;
begin
........................................................
for i:=1 to TempBitmap.height-2 do
begin
line1:=TempBitmap.ScanLine[i-1];//Read lines
line2:=TempBitmap.ScanLine[i];
line3:=TempBitmap.ScanLine[i+1];
lineFinal:=bmp.ScanLine[i-1]; //target line in source bitmap!!
for j:=1 to TempBitmap.Width-2 do
begin
lineFinal[j-1]:=SetValue(
(line1[j-1]*filter.matrix[0,0]+ line1[j]*filter.matrix[0,1]+line1[j+1]*filter.matrix[0,2]+
line2[j-1]*filter.matrix[0,0]+ line2[j]*filter.matrix[0,1]+line2[j+1]*filter.matrix[0,2]+
line3[j-1]*filter.matrix[0,0]+ line3[j]*filter.matrix[0,1]+line3[j+1]*filter.matrix[0,2])div filter.divisor);
end;
Because we work with 8 bit bitmaps we can have only 256 color. So, the pixel color cannot be greater than 255 or lower than 0. For this reason we must check the processed value. So, the SetValue function must look like:
function SetValue(Value:integer):integer;
begin
if value255 then result:=255
else if value else result:=value;
end;
In the rbsfilter.pas you have a better implementation for this function. It is written entirely in assembler (thanks to Harm for the implementation and for the idea for this article).
Our work is not complete now. We have to discuss about palettes. And after that, we can use our convolving routine.
A little bit about palettes
I shall not explain all the details about palettes. Ill say only that the palette is an enumeration of colors we are using for our bitmap. For example, for pf1bit bitmaps we have only two colors and for pf8bit bitmaps we have 256 colors. And now lets concentrate on pf8bit bitmaps. The reason for working with this bitmap type is because 256 colors can be shown by most of the computers. It is not important if you have a 8 MB video card and you can work in true color. Your user can have only a 1MB video Card and at 1024X768 resolution he can see only 256 colors. The second reason is the speed. Working with a big number of colors can be a big time/memory consuming. If you want to implement this effect in a visual component it is better to work with pf8bit bitmaps. But, for an image processing program the pf24bit bitmaps is a minimum. Now lets see the representation of colors in Windows.
If you work in 256 colors mode, Windows reserves for its needs 20 colors. It wants to be sure that all its windows are shown OK. So, if we want to create our own palette it is good to leave for Windows to use 20 colors. In the rbsfilter. pas you can see the get256pal function. It creates a palette using two basic colors (I have named them generator colors). The idea for this algorithm is original from Bjoern Ischo, the author of biLibrary.
This is all about our convolving routine used with pf8bit bitmaps. You should know that this is the common routine for many filters(like blur, as you will see in the demo project).
Now its time to start with a demo project. Lets draw a text on a form canvas. But not a common text. An outline text. Maybe you know the trick for drawing an outline text. If you dont, Ill explain it bellow.
Suppose you want to draw your text at (x,y) coordinates. In order to draw it, you must follow this steps:
1. Draw your text with outline color at (x-1,y), (x+1,y), (x,y-1), (x,y+1) coordinate (I name this procedure the outline background)
2. Draw text using text color at (x,y) coordinate(I name it Outline Face).
Dont forget to set first the canvas.brush.style property of canvas to bsclear.
In the demo project we will do the following:
1. Create a bitmap and assign to it a palette generated by clred and clgreen color
2. Draw the outline background
3. Apply for the first time the blur filter
4. Draw the Outline Face
5. Apply the filter again
This is a good starting point if you intend to create a visual component like a label or a button. It will look better than other controls on the market. Anyway, it is a good effect for an about box. But this is your inspiration.
Now we will concentrate on creating a convolving routine for pf24bit bitmaps. The process is the same, but the difference is in the scanline implementation. For pf24bit bitmaps, the pixels are represented on three bytes, a separate byte for the red, green and blue values of a pixel. So, we have to calculate the values for each color of a pixel. First, take a look on the code snipped shown bellow. Its a procedure for reading a pf24bit bitmap.
type //We have to define this type in order to access the scanline
pRGBArray=^TRGBArray;
TRGBArray=Array[0..1000] of TRGBTriple; //1000 pixel width dimension is enough
procedure Read_pf24bit_bitmap(bmp:Tbitmap);
var
row:pRGBArray;
bmp:TBitmap;
r,g,b:byte;
i,j:Integer;
begin
if bmp.PixelFormatpf24bit then exit; //we ca only read pf24bit bitmaps
for i:=1 to bmp.Height-1 do
begin
row:=bmp.ScanLine[i];
for j:=0 to bmp.Width-1 do //for each point in the line read...
begin
r:=row[j].rgbtRed; //... red value
g:=row[j].rgbtGreen; //...green value
b:=row[j].rgbtBlue; //..blue value
end;
end;
end;
Now lets create our convolution routine for pf24bit bitmaps. The processing part is:
for i:=1 to TempBitmap.height-2 do
begin
line1:=TempBitmap.ScanLine[i-1];//Read lines
line2:=TempBitmap.ScanLine[i];
line3:=TempBitmap.ScanLine[i+1];
lineFinal:=bmp.ScanLine[i-1]; //target line in source bitmap!!
for j:=1 to TempBitmap.Width-2 do
begin
//process red value
lineFinal[j-1].rgbtRed:=SetValue(
(line1[j-1].rgbtRed*filter.matrix[0,0]+ line1[j].rgbtRed*filter.matrix[0,1]+line1[j+1].rgbtRed*filter.matrix[0,2]+
line2[j-1].rgbtRed*filter.matrix[0,0]+ line2[j].rgbtRed*filter.matrix[0,1]+line2[j+1].rgbtRed*filter.matrix[0,2]+
line3[j-1].rgbtRed*filter.matrix[0,0]+ line3[j].rgbtRed*filter.matrix[0,1]+line3[j+1].rgbtRed*filter.matrix[0,2])div filter.divisor);
//process green value
lineFinal[j-1].rgbtGreen:=SetValue(
(line1[j-1].rgbtGreen*filter.matrix[0,0]+ line1[j].rgbtGreen*filter.matrix[0,1]+line1[j+1].rgbtGreen*filter.matrix[0,2]+
line2[j-1].rgbtGreen*filter.matrix[0,0]+ line2[j].rgbtGreen*filter.matrix[0,1]+line2[j+1].rgbtGreen*filter.matrix[0,2]+
line3[j-1].rgbtGreen*filter.matrix[0,0]+ line3[j].rgbtGreen*filter.matrix[0,1]+line3[j+1].rgbtGreen*filter.matrix[0,2])div filter.divisor);
//process blue value
lineFinal[j-1].rgbtBlue:=SetValue(
(line1[j-1].rgbtBlue*filter.matrix[0,0]+ line1[j].rgbtBlue*filter.matrix[0,1]+line1[j+1].rgbtBlue*filter.matrix[0,2]+
line2[j-1].rgbtBlue*filter.matrix[0,0]+ line2[j].rgbtBlue*filter.matrix[0,1]+line2[j+1].rgbtBlue*filter.matrix[0,2]+
line3[j-1].rgbtBlue*filter.matrix[0,0]+ line3[j].rgbtBlue*filter.matrix[0,1]+line3[j+1].rgbtBlue*filter.matrix[0,2])div filter.divisor);
end;
end;
And thats all! Simple and Fast. And .... what? Did you say anything about palette? Oh, I have forgotten to say... Palette is not needed for bitmaps pf24bit. As you can see, you are now able to represent virtually any color. Enjoy it!