Algorithm to detect an image in another image with some noise

Question

I'm searching for the best library to search for identical area in two different images, all images being compressed in JPEG, with a lot of noise. I'm having a hard time finding one. The problem is if you zoom a jpeg, you'll see that it looks like a Monet, I mean, the noise contains a color palette that have no direct link with the original image. So instead of searching for an identical array in the image, I need to find the 'most similar array'.

These images come from random screenshot over a googlemap similar websites, and the images cannot be in another format than jpeg.

I tried a lot of manual way.

One of my method is:

Transforming my two images in smaller images

Changing them in 4bpp images, or even less colors

Taking a small part of image 1

Searching for the byte[] array version of a cropped part of image 1 in image 2

Not searching for identical, but for similar matches.

This algorithm works, but I'm doing everything in one dimension array, and it is very slow.

Is there existing libraries that would do this algorithm directly?

My algorithm is:

    // Where SRC is the bigger image in which I search
    // Offset is where in my small image I start to search
    // Len is how long is my searched array
    // Size is the size of the bigger image in which I'm searching.
    // private Point simpleSearch(byte[] src, int offset, int len, byte[] search, Size size)
    {
        byte[] ddd = new byte[len];
        Array.Copy(search, offset, ddd, 0, len);
        int lowest = 100000000;
        int locmatch = 0;
        for (int i = 0; i < src.Length - len; i++)
        {
            int thed = 0;
            for (int a = 0; a < len; a++)
            {
                int diff = Math.Abs(src[i + a] - ddd[a]);
                thed += diff;
            }

            thed = thed / len;
            if (thed < lowest)
            {
                lowest = thed;
                locmatch = i-len;
            }
        }

        int yy = (locmatch / size.Width);
        int xx = locmatch - (yy * size.Width);
        Point p = new Point(xx, yy);
        return p;
    }

Answer 1

Yep correlation or spectrum signature are ways to tell how similar two image regions are. But I think what you really want here is an algorithm to efficiently search the overlapping region.

Correspondence problem is a well defined problem in computer vision that tries to figure out which parts of an image correspond to which parts of another image. There are RANSAC based algorithms.

There's also a quad-tree algorithm that brings the complexity down to logarithm order.