Finding most similar image

[Serrafine]

Hi,

I'm trying to find a way for the user to draw an image on the screen, and then return a formal version of the image. This is a tool to enable practise writing symbols from an ancient language. What I mean by a formal version is the properly drawn one, so the user can see how to improve. I need to analyse the image they draw and find the most similar image to it.

I've been doing a lot of research online for this. It seems much easier to find an exact match than the most similar one. I was wondering if convolution would be the way to do this? I thought maybe I could convolve each image and then return the image that had the highest resulting value. I've only used convolution in Matlab to find exact matches and have no experience of doing it in Java.

Could anyone with any experience in this area tell me if this idea would work or am I barking up the wrong tree?

Thanks in advance.

[jwenting]

I'd guess what you want is to overlay the image provided with one of the "ideal" version scaled to match.
Then you can detect where pixels overlap and determine hopefully whether mismatches are because of say different line thickness or because a line is in the wrong place.

[Serrafine]

I've done this by converting both images to pixel arrays and comparing the pixels. However it only works if the images are almost accurate. The images are a white background with a black symbol on it. I want it to also be able to scan over the image in case the symbols are not always in the same position in the image, which they may not be.

My attempt to do this was to create an additional method from my compare one. I called this getMovedImage(). If I did not return a reasonably accurate match from the first comparison then I moved along the array and tried to compare it to the next part. However this is not working for the images.

I tried a very simple version of it e.g.

int data1 = {0, 0, 0, 1, 2, 3, 4, 5};
int data2 = {0, 1, 2, 3, 4, 5, 0, 0};

It returned a 100% match for these 2 small arrays but I cannot get it to work for a simple image. Can anyone help me figure out why? The two images I'm trying it with are 30x30. Thanks.

import java.awt.*;
import java.awt.image.PixelGrabber;

public class CmpImprovSimple {

    public static int [] getPixels(Image img, int [] data) throws InterruptedException {
        PixelGrabber grabber = new PixelGrabber(img, 0, 0, -1, -1, false);

        if (grabber.grabPixels()) {
            data = (int[]) grabber.getPixels();
        }
        return data;
    }

    public static int [] getMovedImage(int [] data, int position) {
        int [] moved = new int[900];
        int place = 0;
        for (int i = position; i < data.length; i++)
        {
            moved[place] = data[i];
            place++;
        }
        for (int i = 0; i < position; i++)
        {
            moved[place] = data[i];
            place++;
        }
        return moved;
    }

    public static void compare(int [] data1, int [] data2, Image img1, 
            Image img2) throws InterruptedException  {
        int match = 0;
        int tries = 0;
        data1 = getPixels(img1, data1);
        data2 = getPixels(img2, data2);
        
            do{
                match = 0;
                // keep track of matched pixels in each 30 bit section
                int pixMatch = 0;
                int [] matches = new int [30];

                // from pix to pix + 30 is the current area being analysed
                int pix = 0;
                int section = 0;

                //due to image and pixel group size there are 30 full pixel groups
                while (section < 30)
                {
                    for (int i = pix; i < (pix +30); i++) {
                        if (data1[i] == data2[i])
                            pixMatch++;
                    }
                    matches[section] = pixMatch;
                    pixMatch = 0;
                    pix = pix + 30;
                    section++;
                }

                for(int i = 0; i<matches.length; i++) {
                    if (matches[i]>20)
                        match++;
                }
                
                if (match == 20) {
                    System.out.println("MATCH! matches: " + match + " ");
                }
                else {
                    data1 = getMovedImage(data1, tries);
                    tries++;
                }

            } while((tries < 900));
    }

    public static void main (String args[]) {

        Image img1 = Toolkit.getDefaultToolkit().getImage("1.jpg");
        Image img2 = Toolkit.getDefaultToolkit().getImage("2.jpg");
        int[] data1 = new int[900];
        int[] data2 = new int[900];

        try {
            compare(data1, data2, img1, img2);
        }
        catch (Exception e) {}
    }
}

[Serrafine]

Sorry just noticed that at line 16 moved is set to 14400. That should be 900 however it does not fix my problem.