Finding an Image Inside Another Image

Question

I'm trying to build an application that solves a puzzle (trying to develop a graph algorithm), and I don't want to enter sample input by hand all the time.

Edit: I'm not trying to build a game. I'm trying to build an agent which plays the game "SpellSeeker"

Say I have an image (see attachment) on the screen with numbers in it, and I know the locations of the boxes, and I have the exact images for these numbers. What I want to do is simply tell which image (number) is on the corresponding box.

So I guess I need to implement

bool isImageInsideImage(Bitmap numberImage,Bitmap Portion_Of_ScreenCap) or something like that.

What I've tried is (using AForge libraries)

public static bool Contains(this Bitmap template, Bitmap bmp)
{
    const Int32 divisor = 4;
    const Int32 epsilon = 10;

    ExhaustiveTemplateMatching etm = new ExhaustiveTemplateMatching(0.9f);

    TemplateMatch[] tm = etm.ProcessImage(
        new ResizeNearestNeighbor(template.Width / divisor, template.Height / divisor).Apply(template),
        new ResizeNearestNeighbor(bmp.Width / divisor, bmp.Height / divisor).Apply(bmp)
        );

    if (tm.Length == 1)
    {
        Rectangle tempRect = tm[0].Rectangle;

        if (Math.Abs(bmp.Width / divisor - tempRect.Width) < epsilon
            &&
            Math.Abs(bmp.Height / divisor - tempRect.Height) < epsilon)
        {
            return true;
        }
    }

    return false;
}

But it returns false when searching for a black dot in this image.

How can I implement this?

Chihuahua

Some sudoku or tic tac toe game? – Shontashoo

Have you seen other questions on the similar ground ? – Shontashoo

It's a game called "spellseeker". But it's not important I just want to build the algorihm to solve such a problem. And yes, actually I found this solution in other questions, but they didn't help me. And forgive me for my lazyness but I really think that there should be an easier way for this :) – Chihuahua

+1 for the interesting question. :-) let's say you lock your original puzzle. So you know where which block is - like the entire grid points of it. When a user click on something you don't have to find an image, but the respective point. And you may move (copy/paste) sub image block based on that point. just a thought. – Shontashoo

Hi bonCodigo, I don't know if I understood your comment correctly, but I just want to get numbers from images, not the other way. So that I can initialize my graph's nodes. – Chihuahua

Answer 1

I'm answering my question since I've found the solution:

this worked out for me:

System.Drawing.Bitmap sourceImage = (Bitmap)Bitmap.FromFile(@"C:\SavedBMPs\1.jpg");
            System.Drawing.Bitmap template = (Bitmap)Bitmap.FromFile(@"C:\SavedBMPs\2.jpg");
            // create template matching algorithm's instance
            // (set similarity threshold to 92.5%)

           ExhaustiveTemplateMatching tm = new ExhaustiveTemplateMatching(0.921f);
                // find all matchings with specified above similarity

                TemplateMatch[] matchings = tm.ProcessImage(sourceImage, template);
                // highlight found matchings

           BitmapData data = sourceImage.LockBits(
                new Rectangle(0, 0, sourceImage.Width, sourceImage.Height),
                ImageLockMode.ReadWrite, sourceImage.PixelFormat);
            foreach (TemplateMatch m in matchings)
            {

                    Drawing.Rectangle(data, m.Rectangle, Color.White);

                MessageBox.Show(m.Rectangle.Location.ToString());
                // do something else with matching
            }
            sourceImage.UnlockBits(data);

The only problem was it was finding all (58) boxes for said game. But changing the value 0.921f to 0.98 made it perfect, i.e. it finds only the specified number's image (template)

Edit: I actually have to enter different similarity thresholds for different pictures. I found the optimized values by trying, in the end I have a function like

float getSimilarityThreshold(int number)

Chihuahua

Answer 2

A better approach is to build a custom class which holds all the information you need instead of relying on the image itself.

For example:

public class MyTile
{
    public Bitmap TileBitmap;
    public Location CurrentPosition;
    public int Value;
}

This way you can "move around" the tile class and read the value from the Value field instead of analyzing the image. You just draw whatever image the class hold to the position it's currently holding.

You tiles can be held in an array like:

private list<MyTile> MyTiles = new list<MyTile>();

Extend class as needed (and remember to Dispose those images when they are no longer needed).

if you really want to see if there is an image inside the image, you can check out this extension I wrote for another post (although in VB code):
Vb.Net Check If Image Existing In Another Image

Kill

Thanks for this answer. I already have a class similar to this. I have a Node class with values (in textboxes), and a Tile class which has a Node array. But the problem of initializing all the Nodes still remains. I can enter them into textboxes but it still means I have to enter ~60 numbers by hand, for a 2-second running time. So I'm looking for a way to initialize them using the printscreen image. – Chihuahua