Non Optimized Integer Image Scaling

Introduction

This algorithm demonstrates scaling an image by one positive integer value in both the x and y axis. A common use for this algorithm would be taking a game made for a GameBoy's low resolution screen and doubling or tripling it before displaying it on a PC's high resolution monitor.

This algorithm keeps the aspect ratio of the original image. Think of watching old TV shows on a widescreen monitor. You can either stretch the image to fit the screen, distorting the original image and making all the actors appear fatter, or you can watch in the original aspect ratio, but then you have black bars on either side of the screen. With this algorithm you'd have the black bars. Princess Peach won't have to worry about why she's gained so much weight!

To understand how this algorithm works, it's important to know how most libraries store image data in memory. Where an image is a two dimmensional object, most libraries store the individual pixels of the image in a single dimmensional array - a line. The game has to keep track of the height of the image and its width to manipulate the image. Some libraries, like SDL, hide this from you until you need to do something like rotate or scale the image.

Setting up the Problem

To show how this works, we'll scale one 3x3 image. In the following images, each square will represent a single pixel.

Stored in an array, that image looks like:

This image would be stored in a nine element array: int source[9]. In C and C++ the elements of an array start with 0, so purple is stored in element 0, black is element 1, red is element 2, and so on.

We'll step through the code that creates, initializes, and prints the first 9 element array, then scales that array by 3 leaving you with an 81 element array. When trippling a two dimmensional object you need to multiply its width by 3, and its height by 3 as well. So the new height is 9, the new width is 9, and you multiply those together to get an image that has 81 pixels in it.

We're going to skip the comments between blocks of /* and */. The first bit of code we see is:

// IntegerScaleNonOptimized.cpp

#include  <iostream>
#include "include/S.h"
using namespace std;

int main()
{

To use cout we need to include the C++ standard library iostream by doing: "#include<iostream>". The Input / Output Stream library <iostream> has a ton of useful features and it'll be included in most of these examples. S.h includes a class of helper functions. They do things like print out the array so that I don't have to keep re-typing the functions and so that the code is cleaner.

Every C++ program needs a main function, so that's what the line "int main() {" is. The main function is where every C or C++ program starts.

Finally, the line "using namespace std;" puts us in the "standard" namespace. Without this we'd have to do the following: "std::cout << std::endl;" every time we wanted to use cout. For a discussion on namespaces, click here: NOT YET DEFINED.

Next, let's look at our variables:

        int width  = S::sw();        // The original Array's width
        int height = S::sh(width);   // The original Array's height
        int scale = S::ss(width);    // Set the scaling factor
        int source[height*width];    // Original Array
        int dest[height*scale * width*scale]; // Scaled dest Array

It's a good idea to make your variable names meaningful, and I've tried to do that in this tutorial. If you have to go back and edit your code after leaving it fallow for some time, or if somebody else has to edit your code, it's much simpler to do so if one can glean meaningful names from your variables.

The S::sw(), S::sh(int), and S::ss(int) functions set the width, height, and scaling factor respectively. They ask the user to input the height, width, and scale, and keep the image under 80 characters wide to fit on a standard console. For purposes of this exercise I'm using 3 for width, height, and scale, but feel free to change the values to see how it affects the program.

The next two arrays, source[width*height] and dest[height*scale * width*scale], are where I store the source image and destination image. When manipulating images one often won't know the actual size of the image before hand. The program will ask the user to input them. Width * height gives us the size of the source array.

Creating the array for the destination image is a little tricker. In this exercise we're going to make an image that's 3 times larger. It will be 9 pixels wide by 9 pixels high. We have to multiply BOTH the width of 3 by the scale of 3 to get 9 wide AND the height of 3 by scale of 3 to get a 9 high. Then we have to multiply the width of 9 by the height of 9 to get a scaled image that has 81 pixels.

Now we'll create and print our image:

        cout << "\n\n";

        for(int x = 0; x < width*height; x++)
                source[x]=x;

        S::print_rect(width,height,&source[0]);
        cout << "\n\n";

The for loop creates an integer counter x, and initializes it to 0 - the first element of our array. Variables created in for loops are almost always used as counters so often only get single character names. We keep x less than the size of our image, which we're calculating here as width*height. Then we're stepping through the image one pixel at a time with the line x++.

With the line "source[x]=x;" we're setting each pixel in the image to the value of it's position. So if x = 0, the pixel at source[0] equals 0. When x is 1, pixel[1]=1, and so on.

The S::print_rect(width, height, &source[0]); line sends our image to the print_rect(int, int, int *) function to print it. After we print the array we print a couple new lines.

Now that we have the source image, we need to scale it. The original image looks like:

If you're trying to come up with an algorithm, it's handy to step through the problem a piece at a time. The first thing we're going to do is copy the first pixel three times:

We need to continue copying 3 pixels for every pixel in the source image until we hit the end of the row to properly scale the width of the image:

Then we need to repeat this 3 times to properly scale the height of the image:

Which drawn on the screen looks like:

Finally we need to continue doing this until we have the whole scaled image in memory:

Which drawn on the screen looks like:

The Algorithm in Action!

The following is the outter for loop. It keeps track of our row in the source image,only incrementing after we've copied all 3 pixels horizontally, and copied the row of the image 3 times.

        for(int h = 0; h < height; h++) // Source Height Position
        {

The next for loop copies a row of the image scale times.

                for(int hrepeat = 0; hrepeat < scale; ++hrepeat) // Repeat afull row scale times
                {

This for loop keeps track of our position in any given row of the source image.

                        for(int w = 0; w < width; w++) // Source width Offset
			{

The next for loop is the one that does the bulk of the work. It's what copies the pixel scale times. The for line is simple enough, just incrementing wrepeat scale times. The dest[ ] line is a little more intricate. To place the pixel in the dest[ ] array it needs to calculate both the position of the pixel in the source array and its position in the destination array. Let's take a closer look at the dest[ ] line.

In the first set of perenthesis (h*scale * width*scale) h is the current row in the source array. width*scale is the width of the scaled row. To get to the position of the scaled row we're going to copy, we mutiply h scale times to get scaled height in our dest array. If h is 0, and scale is 3, the first position would be 0*3, the second would be 1*3, and so on, but we have to skip a whole scaled row's worth of data. Once we have our scaled row, we multiply it by width*scale to skip over full scaled rows worth of data.

Each row in the source array must be copied multiple times. We need to calculate if we've copied the row the first time, or the third. That's where we add + (hrepeat * width*scale) to our row in the destination array. If hrepeat is 0, we add nothing. But if it's 1 or 2, we add a full scaled row to our destination array.

Finally = source[(h*width) + w]; This is our position in the source array. h is the row. We take row*width to skip over a full row if h > 0. The value w is our position in the source row, the pixel we're actually copying. Whew! Did you get all that?

				for(int wrepeat = 0; wrepeat < scale; wrepeat++)
                                        dest[ ((h*scale * width*scale) + (hrepeat * width*scale)) + (w*scale + wrepeat)] = source[(h*width) + w];
                        }
                }
        }

The Source:

// IntegerScaleNonOptimized.cpp

#include  <iostream>
#include "include/S.h"
using namespace std;

/********************************************
 *
 * This is an image scaling algorithm.  It
 * will scale an image in an array by a
 * positive integer value.
 *
 * It keeps the original image's aspect ratio.
 * If the original aspect ration was 4:3 and
 * you have a wide screen monitor, there
 * will be black vertical bars on either side
 * of the screen.  The image will not be distorted.
 * Princess Peach won't have to worry about why
 * she's suddenly so much wider.  :b
 *
 * It makes an array that is width*height sized.
 * It initializes every element in the array
 * with its array position.
 *
 * Then it makes a second array that
 * is width*scale * height*scale sized.
 *
 * It prints the first array, a couple newlines,
 * then it scales and prints the second array.
 *
 ********************************************/

int main()
{
	int width  = S::sw();    // The original Array's width
	int height = S::sh(width);   // The original Array's height
	int scale = S::ss(width);
	int source[height*width]; // Original Array
	int dest[height*scale * width*scale]; // Dest Array

	cout << "\n\n";

/*********************************************
 * The source array
 *
 * This loop constructs an "image" with a
 * unique color in each position of the array,
 *
 * width * height is the integral statement
 * here.  If width is set to 3 and height is
 * set to 3 it creates an array[9] that has
 * 9 elements, starting with element 0 and
 * continuing to element 8.
 *********************************************/
	for(int x = 0; x < width*height; x++)
		source[x]=x;

	S::print_rect(width,height,&source[0]);
	cout << "\n\n";



/*********************************************
 * The destination, scaled array
 *
 * In games most 2 dimmensional images are
 * stored in a one dimmensional array.
 *
 * A four color image
 * 0,1
 * 2,3

 * that that's been scaled up
 * by two looks like:
 *      0,0,1,1
 *      0,0,1,1
 *      2,2,3,3
 *      2,2,3,3
 * when print_rected
 *
 * and is stored in the array as:
 *      [0,0,1,1,0,0,1,1,2,2,3,3,2,2,3,3]
 *
 *********************************************/

	for(int h = 0; h < height; h++) // Source Height Position
	{
		for(int hrepeat = 0; hrepeat < scale; ++hrepeat) // Repeat a full row scale times
		{
			for(int w = 0; w < width; w++) // Source width Offset
			{
				// Repeat individual pixel scale times
				// See the tutorial for an explanation of this line.
				for(int wrepeat = 0; wrepeat < scale; wrepeat++)
					dest[ ((h*scale * width*scale) + (hrepeat * width*scale)) + (w*scale + wrepeat)] = source[(h*width) + w];
			}
		}
	}

	S::print_rect(width*scale,height*scale,&dest[0]);

	cout << "\n";
	return(0);
}