Friendly Robot Overlord

I recently saw a cool video demonstrating a different way to resize images. I was watching it late at night, and I didn't feel like wearing headphones so I just went without sound. At the end of the video I was suitably impressed. So I decided to make my own version of the program tonight. This is another one of those things where I do a bad, but workable job because of time restraints (this took a bit longer than the dithering algorithm, but I started at midnight and finished at about 1:30, so it is a pretty acceptable time scale).

The basic idea here is that when you resize an image, there are lots of parts which you care about, and lots that you don't. So if you have a person standing in front of a plain wall, it would look best if you concentrated all of your resizing efforts on the wall, since there isn't much detail there. This way, the resized image would have the person in perspective, and they would still look normal.

So, I wrote my image resizer to work like this:

1. Load an image
2. Find the edges (I don't know much about the maths behind what I did here - I used two 3x3 Sobel operators, one horizontal one vertical, and then took the sum of the absolute values for what they returned):
3. Find a path from the top of the image to the bottom, where for each step you can either go down+left, down or down+right. The path should try to go through the blackest areas in the edge picture:
4. Chop out all the pixels along this path (or more accurately, we blend the pixels on this path with the ones just on the right, and shift the rest of the image over). This gives us an image that is one pixel narrower than the original.
5. Repeat until it is narrow enough:

Pretty cool I think. Though I don't think my method is quite as robust as the inspiration. I might read the paper some day to see how they actually did it, rather than my speculation.

(test image from flickr, selected to make the algorithm look good, not to give general expected results)

If there is non-zero demand, I'm happy to put the source up (it is C) under GPL3 perhaps, just because it is new. But right now I want to go to bed.

Dither is a pretty cool idea. It is what happens when you have something that is high quality (like a photo using lots of colours, or a sound wave with high bit-depth) and for some reason you want to reduce the number of colours (or bit-depth). So you are mapping from lots of values down to less values.

The first thing you would expect is that just finding the nearest match gives good results. This is what happens when you take my favourite test photo:

And a very limited set of colours (red, green, blue, black, white), and pick the nearest colour:

We can also reduce it to black and white the same way:

It looks pretty bad, because although each dot in the image is doing its best, we are forgetting that we don't look at individual dots, we look at the picture as a whole.

One way of fixing this, is to add some noise to the image before doing the operation. If you add noise to the image, the parts which were blue before will probably still be blue, but there is a chance that they will be some other colour - especially if they were just bordering on being blue. By adding random noise to the image, each pixel has a random chance of being any of the possible new colours, so it should give ok results. Sorry, I don't have a picture for this one, but this is what most people mean when they talk about dither - adding noise to a signal before quantizing it.

What I thought would be fun would be to try this process instead:

1. Start with the nearest approximation
2. Pick a random pixel
3. Calculate average colour of pixels (in our working/dithered image) nearby (weighted by closeness) (not including this pixel)
4. Choose the colour which minimises the difference in colour between the source image and the average colour of nearby pixels (including this pixel, of whatever colour)
5. Go to 2 (lots of times)

I chose to weight a pixel by '1 / (1 + distance)', for all pixels in a fixed radius. All other pixels had weight 0. I tried this with different radii.

These are the results I got: (radius 3, 5 and 15 respectively)

For black and white it looks like this (radius 5):

It looks different to more conventional dithering algorithms. And there are some weird things (it seems to eat out the inside of blocks of colour). But for an application done in about 20 minutes, I think it is pretty cool.

A more conventional dither: (done by The GIMP) with Floyd-Steinberg dithering.

So it probably conveys the idea of a goat standing on a pole better than my algorithm, so maybe I should call it an 'effect' instead of a dithering algorithm, then I don't have to worry about things like accuracy.

So here is a fun effect you can try at home. Take an image, break it up in to small squares (I used 5x5 pixels). For each of these squares, rearrange the pixels in that square so that they are in order of intensity from top left to bottom right. If you do this, you will get a 5x5 tiled pattern which looks ok, but hardly useful. So then if you repeat this process 25 more times, but take the squares from different starting positions each time, then you can get 25 of these tiled patterns where the tile boundaries don't line up at all. Mix all of these images together, and you have what I'm calling a sorting filter.

I didn't actually use intensity, I said that a (r1, g1, b1) preceeds (r2, g2, b2) if (r1r1 + g1g1 + b1b1) < (r2r2 + g2g2 + b2b2). I don't really know what that is called, but everyone likes to square things (I wanted to make strong colours beat medium greys... I don't know why).

So my implementation is super slow because I'm lazy (not because it is a complicated effect that needs to be CPU intensive) but here are two example images:

The actual result is very similar to a normal blur, but the shapes of objects change slightly when you use this method, which makes it a bit cooler.

The C code used to generate this (so you can admire its inefficiency) is: (and one day I'll get around to giving some code that isn't so trivial that it deserves more than public domain (though I decided to include my name in this one, so I suppose I'm getting closer))

// Public domain
// by Andy Owen (http://www.ultra-premium.com/b)
#include <stdio.h>
#include <stdlib.h>
#include "image/image.h"

#define X_RADIUS (15)
#define Y_RADIUS (15)

static void swapPixels(Image img, int x1, int y1, int x2, int y2);
static Image mixImages(int numImages, Image *images);
static void sortArea(Image img, int left, int top, int w, int h);
static int rgbCompare(Rgb a, Rgb b);

int main(int argc, char* argv[]) {
    Image img = loadImage(argv[1]);
    int width = getWidth(img);
    int height = getHeight(img);

    Image copies[X_RADIUS * Y_RADIUS];

    int c = 0;
    for (int offX = 0; offX < X_RADIUS; offX++) {
        for (int offY = 0; offY < Y_RADIUS; offY++) {
            copies[c] = duplicateImage(img);        
            for (int y = offX; y < height + offX; y += Y_RADIUS) {
                for (int x = offY; x < width + offY; x += X_RADIUS) {
                    sortArea(copies[c], x, y, X_RADIUS, Y_RADIUS);
                }
            }
            c++;
        }
    }

    Image mix = mixImages(X_RADIUS * Y_RADIUS, copies);

    saveImage(mix, "copy.bmp");

    destroyImage(mix);
    for (int c = 0; c < (X_RADIUS * Y_RADIUS); c++) {
        destroyImage(copies[c]);
    }

    return 0;

}

static Image mixImages(int numImages, Image *images) {
    int width = getWidth(images[0]);
    int height = getHeight(images[1]);

    Image ret = createImage(width, height);

    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            Rgb value;
            value.red = value.green = value.blue = 0;
            for (int i = 0; i < numImages; i++) {
                Rgb add = getPixelRgb(images[i], x, y);

                value.red += add.red;
                value.green += add.green;
                value.blue += add.blue;
            }
            value.red /= numImages;
            value.green /= numImages;
            value.blue /= numImages;
            setPixelRgb(ret, x, y, value);
        }               
    }

    return ret;
}

static void sortArea(Image img, int left, int top, int w, int h) {
    int imgWidth = getWidth(img);
    int imgHeight = getHeight(img);

    int sortOrder = 1;

    for (int y = top; y < top + h; y++) {
        for (int x = left; x < left + w; x++) {

            for (int y1 = top; y1 < top + h; y1++) {
                for (int x1 = left; x1 < left + w; x1++) {
                    if (rgbCompare(
                         getPixelRgb(img, x % imgWidth, y % imgHeight), 
                         getPixelRgb(img, x1 % imgWidth, y1 % imgHeight)) == sortOrder) {
                        swapPixels(img, x  % imgWidth, y  % imgHeight, 
                                        x1 % imgWidth, y1 % imgHeight);
                    }
                }
            }
        }
    }
}

static int rgbCompare(Rgb a, Rgb b) {
    int av2 = a.red * a.red + a.green * a.green + a.blue * a.blue;
    int bv2 = b.red * b.red + b.green * b.green + b.blue * b.blue;
    if (av2 < bv2) {
        return -1;
    }
    if (av2 > bv2) {
        return 1;
    }
    return 0;
}

static void swapPixels(Image img, int x1, int y1, int x2, int y2) {
    Rgb temp = getPixelRgb(img, x1, y1);
    setPixelRgb(img, x1, y1, getPixelRgb(img, x2, y2));
    setPixelRgb(img, x2, y2, temp);
}

The image library it is using is one of my own. It isn't quite ready to face the world. But you can just substitute your own in, the interface should be simple enough.