COURSES  

 

Alejandro B. Engel
Department of Mathematics and Statistics
Rochester Institute of Technology
email: abesma@rit.edu
Phone: (716) 475 2123
NICE MATH.
RESEARCH
OTHER
 

OTHER

IMAGE RENDERING USING TWO DIMENSIONAL QUADRISECTION

by

Alejandro B. Engel
Department of Mathematics and Statistics
and
Daniel B. Engel*
Department of Computer Science
Rochester Institute of Technology

*Presently at NORTEL, Raleigh, NC
PIXEL SELECTION ALGORITHM
 
 

SEE ILLUSTRATION
 
  Introduction and overview: Image rendering in one of the serious bottleneck in computer processing. Particularly in real time automation. Many, if not most times, a completely defined image in not needed until the final stage of the process; thus, one needs an algorithm which gives the most visual information about an image, using the least number of points. This optimization problem obviously depends upon the characteristics of the image, and for different images different procedures might be needed. In this note we will provide a very general -image independent- algorithm for selecting equally spaced points in a two dimensional grid, so that at each pass of the procedure a finer mesh is obtained and no point is visited more than once. After each pass the number of points selected is quadruplicated. In this way, before the last pass only 25% of the points are selected, and before the penultimate pass just 1/16 or about 6% of the points are rendered. Even with 6% of the points rendered, the equally spaced grid provides for a reasonably well defined image, in which generally the most important features can be visualized. Several image processing procedures can greatly benefit from the algorithm that will be presented, in particular image sorting , like fingerprint recognition or medical imaging for instance can be speeded up by a factor 16, thus dramatically improving productivity. Also, processes in which intensive computations must be performed for each pixel -like fractal images- can be speeded up with this algorithm. Indeed, with just about 6% of the time required to produce the complete image, one has a pretty good idea of how the final image will look like, and one can decide to stop and compute a new image or let the process finish. In this way one can save time by avoiding the complete computation of images which are not interesting.

The algorithm to select points by two dimensional quadrisection will be explained and developed using a square grid of 2n times 2n points. In this way one can divide by 2 each side n-1 times always getting even numbers. By the n-th division by 2, one gets 1. At the end of this note we will provide the cropping algorithm for rectangular grids of arbitrary dimensions.

The geometry of the two dimensional quadrisection algorithm: The geometric idea of the algorithm is than any square can be dived into four identical squares by dividing each side of the square in half. And then each one of the four identical squares can in turn be divided into four identical squares. Which divides the large square into 16 identical squares, and so on until we merely get points as the "smallest" squares. For this iterated division by two of the sides of the squares, we need to start with a square of sides 2n . In this way, after each division by two, but the last one, we get an even number. The total size of the square is 2n+1 . For instance pictures consisting of 64X64, 128X128, 256X256, 512X512 or 1024X1024 pixel are in the form needed to apply the algorithm directly and without cropping. For other picture sizes, a modification of the algorithm or copping of the square might be needed. All necessary ideas and algorithms regarding this will be provided at the end.

The geometric two dimensional quadrisection algorithm can be understood as follows:

PASS ONE: select the upper leftmost point of the square.

PASS TWO: divide the square into four identical squares, and in each square but for the upper leftmost square, select the upper leftmost point. Three new point will be selected, bringing the total number of points selected to 4.

PASS THREE: divide each of the four squares into four identical squares, and in each square, but for the upper leftmost in each of the four squares, select the upper leftmost point. Three new points per square will be selected; since we have four squares, 12 new points will be selected. This bring the total number of points selected to 4+12=16.

AND SO ON.... UNTIL THE WHOLE SQUARE IS SELECTED.

The two dimensional quadrisection algorithm: We start with a 2n X2n square, an label the pixels or points with two numbers. The upper leftmost point is labeled with (0,0) as it is usually done. A point (a,b) is a steps down and b steps to the right of (0,0).

Procedure One: Given a point (a,b) and a "side length" s, select the three points (a,b+s), (a+s,b) and (a+s,b+s). Call this procedure SELECT(a,b,s), with a,b,s integers. In reality the range of these numbers is between 0 and 2n -1, so for n=7 or less an unsigned 8-bit byte-type would suffice.

Main Body: For power=0 to n-1 do

step= 2n-power (distance between upper leftmost vertices of squares)

side=step/2 (length of the sides of each square)

nudiv= 2power - 1 (number of divisions points on each side of the original square)

Now find all upper leftmost vertices of squares:

for i=0 to numdiv

for j=1 to numdiv

x=i*step

y=j*step

(x,y) are the upper leftmost vertices of the squares.

Now, select all vertices but the upper leftmost one using our procedure one:

SELECT(x,y,side)

For each one of the points selected, at this point the coloring algorithm or scheme must be processed, and the pixel colored according to its result.

Image rendering by points and by large pixels: After each pixel is selected and its color computed or retrieved from the corresponding file, there are two options for image rendering. The first one is simply assigning the color to the pixel -rendering by points-. The second one -rendering by large pixels- renders an image "uglier" than the one rendered by points. In this second case the procedure SELECT selects all the points in the square with upper leftmost vertex at (a,b) and side length s, but point (a,b). However when it comes to "painting" the square, at this point some precious time can be saved by not "painting" the square if it is already of the desired color. The decision of whether "painting" or not "painting the square is quite simple: if the color computed for the point(a,b) is already the color that has been previously assigned to this pixel (a,b), then do not "paint", otherwise "paint". this second method with the time saving procedure of skipping the squares which are already of the desired color is the large pixel algorithm.

Another possibility: The idea of leaving 75% of the processing and image rendering to the end is mainly geared towards image sorting. In this way the bulk of the processing is only performed after an actual image is selected. There are times, however, in which more than a 25% resolution is needed for a decision on selecting an image, or when the 25% rendering has eliminated most images in the set, and only a few are left. These few images must be sorted through a finer resolution then before. The possibility is to decompose the rendering of last 75% of the image in two stages. The first one will select one third of the remaining points, completing 50% of the image processing, and leaving the last 50% (not 75%) for the second stage and final pass. For doing this all that needs to be done is to skip the last pass in the Main Body of the algorithm by replacing power=0 to n-1 by power=0 to n-2. For each value of i and j, the first stage will now select only one point not three of them: this point is (2*i+1, 2*j+1), with i and j ranging from 0 to 2n-1. One selects in this way, 2n-1X2n-1 = 2n/4 pixels or 25% of the total number of pixels. The second stage and actual final pass will select the remaining 50% of the pixels, which for i and j having the same range as before, are: (2*i+1,2*j) and (2*i,2*j+1).

Generalization to rectangular images of arbitrary dimensions: The algorithm presented can be applied to rectangular images of any dimensions, by using a 2n X 2n square in which the rectangular image can be inscribed. Cropping of the square to fit the rectangle is now to be done. That is, after selecting the pixels in the square using the quadrisection algorithm, only those within the rectangular image are to be processed, the rest must be ignored.

Generalization to higher dimensions: To handle 3D images one needs to start with a cube of dimension 2n X 2n X 2n , an its upper leftmost frontmost voxel is selected (a voxel is the 3D equivalent to a 2D pixel). The second pass divides the cube 8 "large voxels"; on each of them the upper leftmost frontmost voxel is selected. The third each of these 8 large voxels into 8 smaller "large voxels", and so on, until single voxels are left. The generalization to dimensions larger than three is now quite obvious: each side of the n-dimensional hypercube is bisected until a single point is reached. This generates finer and finer hypercubes, as before with cubes and squares. However, all of this is rather theoretical since dimensions larger than three are not of any use in computer imaging.