Thursday, July 7, 2011

Digital Image Processing

Introduction

The techniques described in this article is used in The Game of Snake

Image format

Digital Image is a image that is encoded in some digital format. One of the simplest format for a digital image is an array of pixels. For example :




This is not a very obvious image pattern. But if we make manual highlight to the source code, the data format will become self-documentary.


int[] foodImage = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,
0,0,0,0,0,1,2,2,2,2,1,0,1,2,1,0,
0,0,0,0,1,1,1,1,1,2,2,1,1,2,1,0,
0,0,0,1,5,5,5,5,5,1,1,1,2,1,0,0,
0,0,1,5,5,6,6,5,1,2,2,2,1,0,0,0,
0,0,1,5,6,6,5,1,2,2,2,2,2,1,0,0,
0,1,5,5,5,5,5,1,1,1,2,2,1,2,1,0,
0,1,5,5,5,5,5,5,7,7,1,1,1,2,1,0,
0,1,7,5,5,5,7,7,7,5,3,3,1,2,1,0,
1,5,7,7,7,7,5,7,7,3,3,4,1,1,0,0,
1,3,7,5,7,7,7,3,4,3,3,3,3,1,0,0,
1,3,3,3,3,4,3,3,3,3,4,3,1,0,0,0,
1,3,4,3,3,3,3,4,3,3,1,1,0,0,0,0,
0,1,3,3,4,3,3,1,1,1,0,0,0,0,0,0,
0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0 
};

The above array actually represents the following image :






Why not use the Java Image object

Just because it hides too many implementation details. And because this article is for educational purpose. And because the pursuit of knowledge is a self-satisfactory act.


Drawing the Image Pixel by Pixel

In the above array, the value 0 is used to represent a black pixel, 1 to represent magenta, 2 to represent green, 3 to represent red, etc.

Hence we can create a color table to represent the color value :


This is known as palette graphics because the colors of the image are limited and they must come from a fixed palette.

Now we can create a nested for loop to draw the image pixel by pixel


Image Transformation

Typical transformation includes rotation and scaling. The generic way is to do matrix multiplications. However, for simple transformation, such as rotation by 90 degree, we can use simpler methods. Some examples of simple rotations will be described in this article.

Coordinate System

The image array consists of 16x16 = 256 pixels. It is a one dimensional array and the color of a pixel can be obtained by :
color = foodImage[i];
But what is the meaning of the array index ? Since the image contains 16 rows and 16 columns, we can index each row and column. The top row is row 0 and the bottom row is row 15. The leftmost column is column 0 and the rightmost column is column 15. Then to get the color of row 5 and column 6, we should write :
color = foodImage[5*16+6];
Or in general, if we know the row and column number, the color of a pixel is given by :
color = foodImage[row*W+column];

where W=16 is the width of the image.


Sometimes we wish to index the image by (x,y) coordinates. In our sample, the coordinates of the upper left corner is (0,0) and the lower right corner is (15,15). Note that a pixel with coordinates (x,y) means that it is located at row y and column x.

Hence, to get the color of pixel at (x,y), we write :
color = foodImage[y*W+x];

Simple Rotation

Upside down

It is not really a rotation but a vertically mirrored image
To create an upside down image of the original one. We may use the hard code method such as :


int[] upsideDownImage = {
0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,
0,1,3,3,4,3,3,1,1,1,0,0,0,0,0,0,
1,3,4,3,3,3,3,4,3,3,1,1,0,0,0,0,
1,3,3,3,3,4,3,3,3,3,4,3,1,0,0,0,
1,3,7,5,7,7,7,3,4,3,3,3,3,1,0,0,
1,5,7,7,7,7,5,7,7,3,3,4,1,1,0,0,
0,1,7,5,5,5,7,7,7,5,3,3,1,2,1,0,
0,1,5,5,5,5,5,5,7,7,1,1,1,2,1,0,
0,1,5,5,5,5,5,1,1,1,2,2,1,2,1,0,
0,0,1,5,6,6,5,1,2,2,2,2,2,1,0,0,
0,0,1,5,5,6,6,5,1,2,2,2,1,0,0,0,
0,0,0,1,5,5,5,5,5,1,1,1,2,1,0,0,
0,0,0,0,1,1,1,1,1,2,2,1,1,2,1,0,
0,0,0,0,0,1,2,2,2,2,1,0,1,2,1,0,
0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 
};

Or we may write an automatic conversion routine :


To write the conversion routine, make the following observation :
The first row of the original image will become the last row of the transformed image.
The second row of the original image will become the second last row of the transformed image.
...
That means :
row 0 of the original image will become row 15 of the transformed image
row 1 of the original image will become row 14 of the transformed image
...
That means :
row n of the original image => row 16-n-1 of the transformed image
or in a more generic way :
row n of the original image => row H-1-n of the transformed image where H=16 is the height of the image.


That leads to the conversion routine is below :



Anti-clockwise Rotation by 90 degree

Just do the following transformation :
(x,y) => (y,15-x)
Or the more generic formula :
(x,y) => (y,W-1-x)

That is, for any point (x,y) in the original image, make it becomes (y,15-x) of the target image. The pseudo code is :
color <= sourceImage[(x,y)];
targetImage[(y,15-x)] <= color
Implementation :

Demonstration

To compile and run the demonstration :
javac ImagePanel.java
java ImagePanel

No comments:

Post a Comment