Image manipulation with J2ME, part 2

(the first article in this series is found here)

Continuing my last post about image manipulation, this article will introduce image resizing routines which are very handy in J2ME application and games where the artwork must look good on many device with different screen sizes.

Direct image mapping

Assume you have an image with the dimensions W1xH1, which you want to resize to W2xH2. The easiest way to do this is to that for each pixel (X2, Y2) in the resized image compute the corresponding pixel in the original image:

X1 = (W1 * X2) / W2

Y1 = (H1 * Y2) / H2

Then simply fill pixel (X2, Y2) with the value found at position (X1, Y1) in the original image.

This approach is very simple but the result suffers from jagged pixels that reminds me of the early 3D games:

Original image	Resized image using direct mapping

The reason for the artifacts that some reverse-mapped pints (X1, Y1) contain non-integer values and do not directly corresponds to unique pixels.

Filtered mapping

A variation of the direct mapping which produces much better results is the “filtered mapping” algorithm. It uses the interpolation of four points closest to the mapped pixel to achieve better results.

As an example, assume that the direct mapping of the pixel (X2, Y2) gives us the coordinates

P = (X1, Y1) = (10.30, 15.85)

With the direct mapping approach we would simply lookup the pixel (10, 15), but in filtered mapping we will lookup the four pixels

P1 = (10, 15), P2 = (11, 15), P3 = (10, 16), P4 = (11, 16)

Then we will blend all four pixels into a single color using the interpolation factors 30% and 85%.

C = blend( blend(C1, C2, 0.30), blend(C3, ebC4, 0.30), 0.85)

(assuming the C1 is the color of pixel P1 and so on)

Compared to the direct approach, this will produce much better results:

Resized image using direct mapping	Resized image using filtered mapping

Using mipmaps to reduce artifacts

The filtering algorithm works well when the images are stretched, but when they are shrunken another problem is observed: artifacts in small images. This problem is seen in the image to the left below, where the original phone picture is shrunken from 240×320 to 13×18:

Directly shrunken image ( and then enlarged 10 times to the right)	Mipmap-shrunken image	The original image

Without going into any technical details, we will solve this problem using a variation of tri-linear filtering implemented with the same “halve” operation that we used to generate mipmaps. This approach will result in much more accurate images as seen in the middle image above.

The tube42 basic image manipulation library

The image resizing algorithms are stuff I will use very frequently in my upcoming J2ME projects. I also know that some developers are struggling with similar problems in absence of a good standard image library, so I have decided to put together a very basic library and publish it as open source. The library is very simple and contains two short files which are used for color and image manipulation:

All color manipulation is done in the ColorUtils class:

// tube42.lib.ui.ColorUtils:
    public static final int blend(int c1, int c2, int value256 )
    public static int mix(int c1, int c2 )
    public static int mix(int c1, int c2, int c3, int c4 )

The image manipulation stuff is in the ImageUtils class:

// tube42.lib.ui.ImageUtils:
    public static Image blend(Image img1, Image img2, int value256 )
    public static Image halve(Image org )
    public static Image resize(Image src_i,
              int size_w, int size_h, boolean filter, boolean mipmap )

I have also included a very simple demo application to help you get started.

Where to get it?

The development page will contain the latest source codes.

Have fun playing with images in Java. And please post ideas, suggestions and report bug to this thread.

Image manipulation with J2ME, part 1

I often need to manipulate images within a J2ME application. The most common case is when I need to scale sprites and images to different screen resolutions. A quick Google search shows that more developers are struggling with image manipulation tasks. Therefore, I have decided to write some very basic image manipulation functions once and for all and release them under the LGPL license.

Of course, the JSR 234: (Advanced Multimedia Supplements) already implements many efficient image manipulation functions, but it is not available on all devices.

Color manipulation – 101

In Java, images are generally represented using the 32-bit ARGB8888 format. In this format, each component (Alpha/Red/Green/Blue) is represented by an 8-bit number (0 to 255). The four components are packed into a 32-bit number.

For color manipulation, you usually need to extract each component and manipulate it separately, then join them back to the original 32-bit format. As an example study the following code, which will make the color 50% “darker”:

        int color = ...
	// Extract each component
        int a = (color >> 24) & 0xFF;
        int r = (color >> 16) & 0xFF;
        int g = (color >>  8 ) & 0xFF;
        int b = (color >>  0) & 0xFF;
	// manipulate it:
	r = r / 2;
	g = g / 2;
	b = b / 2;
	// now write it back
        color = (a << 24 ) | (r << 16 ) | (g << 8 ) | b;

Color blending

Assume you have two colors c1 and c2, and you want to compute a new color c3 which is 25% of c1 and 75% of c2. This is often called “blending” and is a very common color operation. The straightforward of doing this is linear interpolation, the naive implementation of which looks like this:

    public static final int blend(int c1, int c2, int value256)
    {
        // how much should we take from each color?
        int v1 = value256 & 0xFF;
        int v2 = 255 - v1;
        // get components
        int a1 = (c1 >> 24 ) & 0xFF;
        int r1 = (c1 >> 16 ) & 0xFF;
        int g1 = (c1 >>  8 ) & 0xFF;
        int b1 = (c1 >>  0 ) & 0xFF;
        int a2 = (c2 >> 24 ) & 0xFF;
        int r2 = (c2 >> 16 ) & 0xFF;
        int g2 = (c2 >>  8 ) & 0xFF;
        int b2 = (c2 >>  0 ) & 0xFF;
        // mix them given the requested amount
        int a = (a1 * v1 + a2 * v2) >> 8;
        int r = (r1 * v1 + r2 * v2) >> 8;
        int g = (g1 * v1 + g2 * v2) >> 8;
        int b = (b1 * v1 + b2 * v2) >> 8;

        return (a << 24) | (r << 16) | (g << 8 ) | b;
    }

A slightly faster version takes advantage of the fact that you can manipulate two components at a time if they cannot overlap. Just split the color = (A, R, G,B) into color1 = (A, _, G, _) and color2 = (_, R, _, B) and you will be fine:

    public static final int blend(int c1, int c2, int value256)
    {
        int v1 = value256 & 0xFF;
        int v2 = 255 - v1;

        int c1_RB = c1 & 0x00FF00FF;
        int c2_RB = c2 & 0x00FF00FF;
        int c1_AG = (c1 >>> 8 ) & 0x00FF00FF;
        int c2_AG = (c2 >>> 8 ) & 0x00FF00FF;
        return
              (((c1_RB * v1 + c2_RB * v2) >> 8 ) & 0x00FF00FF) |
              ((c1_AG * v1 + c2_AG * v2) & 0xFF00FF00);
    }    

Please also note that ">>>" operator in the code above performs unsigned shift in Java, this is often forgotten which leads to very weird problems:

       int a = 0x80000000  >> 1; // this will become 0xC0000000
       int b = 0x80000000 >>> 1; // this will become 0x40000000

Color mixing:

A special case of blending is when you take N colors and mix them equally. Using the previous optimization, the two color version can be written like this:

    public static int mix(int c1, int c2)
    {
        // This corresponds to "blend(c1, c2, 0x7f)"
        int c_RB = (((c1 & 0x00FF00FF) + (c2 & 0x00FF00FF)) >> 1) & 0x00FF00FF;
        int c_AG = (((c1 & 0xFF00FF00) >>> 1) + ((c2 & 0xFF00FF00) >>> 1)) & 0xFF00FF00;
        return c_RB | c_AG;
    }

This becomes just slightly more complicated for four colors:

    public static int mix(int c1, int c2, int c3, int c4)
    {
        int c_RB = (
                  ((c1 & 0x00FF00FF) + (c2 & 0x00FF00FF) + (c3 & 0x00FF00FF)
                   + (c4 & 0x00FF00FF)) >> 2) & 0x00FF00FF;

        int c_AG = (
                  ((c1 & 0xFF00FF00) >>> 2) + ((c2 & 0xFF00FF00) >>> 2) +
                  ((c3 & 0xFF00FF00) >>> 2) + ((c4 & 0xFF00FF00) >>> 2)
                  ) & 0xFF00FF00;
        return c_RB | c_AG;
    }

The 4-color mix is a very handy operation for creating mip-maps,which works like this: take an NxN image and convert it to a (N/2)x(N/2) image by "mixing" every four pixels into a single one. The exact implementation will be shown in a moment.

By the way, the above code is actually more clever than it meets the eye. Notice that the Alpha and Green colors are shifted before addition while Red and Blue are shifted after addition. Can you tell me why it must be done this way?

Working with images:

To access individual pixels in an image, you can read them to an array of integers using the getRGB function:

public void Image.getRGB(int[] rgbData,
                   int offset,
                   int scanlength,
                   int x,
                   int y,
                   int width,
                   int height)

To put pixels back into an image, you will need to use the drawRGB function of the Graphics class:

public void Graphics.drawRGB(int[] rgbData,
                    int offset,
                    int scanlength,
                    int x,
                    int y,
                    int width,
                    int height,
                    boolean processAlpha)

Of course, if you want to update all pixels at once, you can instead create a new Image using the following function:

public static Image Image.createRGBImage(int[] rgb,
                                   int width,
                                   int height,
                                   boolean processAlpha)

It should be mentioned that the returned image is a memory buffer and is not hardware accelerated. To enable hardware acceleration, you need to create a new Image from it:

        Image img_not_accelerated = Image.createRGBImage(data, w, h, true);
        Image img_accelerated     = Image.createImage(img_not_accelerated);

Blending images

To give you a real example, here a functions which "blends" two whole images into one:

    // blend two images:
    public static Image blend(Image img1, Image img2, int value256)
    {
        // 1. get blended image:
        int w1 = img1.getWidth();
        int h1 = img1.getHeight();
        int w2 = img2.getWidth();
        int h2 = img2.getHeight();

        int w0 = Math.min(w1, w2);
        int h0 = Math.min(h1, h2);
        int [] data = new int[w0 * h0];
        int [] b1 = new int[w0];
        int [] b2 = new int[w0];

        for(int offset = 0, i = 0; i < h0; i++) {
            img1.getRGB( b1, 0, w1, 0, i, w0, 1); // get one line from each
            img2.getRGB( b2, 0, w2, 0, i, w0, 1);

            for(int j = 0; j < w0; j++)  // blend all pixels
                data[offset ++] = blend( b1[j], b2[j], value256);
        }

        return Image.createRGBImage(data, w0, h0, true);
    }

Notice that we read the source images one row at a time. We could read the whole images into the b1 and b2 buffers, but then we would risk running out of memory. There is actually a clever “optimization” that not only reduces memory usage but also speeds things up considerably. I leave that one as an exercise to you

The above routine was used to create the following series of images which achieve a “morphing” effect:

(blending between two images, click on the image to enlarge)

In case you are wondering, the source images are these two:

Creating mip-maps:

Another good example for image manipulation is the "halve" function which halves the input images. This function is used to create "mip-maps" , and it build upon our “mix” function which was explained earlier:

    // reduce image dimension to half
    public static Image halve(Image org)
    {
        int w1 = org.getWidth();
        int h1 = org.getHeight();
        int w2 = w1 / 2;
        int h2 = h1 / 2;
        int [] data = new int[w2 * h2];
        int [] buffer = new int[w1 * 2];
        for(int offset = 0, i = 0; i < h2; i++) {
            org.getRGB( buffer, 0, w1, 0, i * 2, w1, 2); // 2 lines from the original

            int o1 = 0, o2 = 1, o3 = w1, o4 = w1 + 1;
            for(int j = 0; j < w2; j++) {
                data[offset ++] = mix( buffer[o1], buffer[o2], buffer[o3], buffer[o4]);
                o1 += 2;
                o2 += 2;
                o3 += 2;
                o4 += 2;
            }
        }

        Image tmp = Image.createRGBImage(data, w2, h2, true);
        data = null; // can this help GC at this point?

        Image ret = Image.createImage(tmp);
        return ret;
    }    

To be continued…

This post is getting a little bit heavy on code snippets. To make things more readable, I will continue the rest in another article, where we will look into image resizing and explain how to make the produced images look “good”.

Furthermore, I will release the image manipulation library I promised earlier as open source