C# image recognition performance - comparing list of images to dictionary of images

Question

I've managed to do recognize characters from image. For this reason:

I save all recognized blobs(images) in List

        Bitmap bpt1 = new Bitmap(@"C:\2\torec1.png", true);
        Bitmap bpt2 = new Bitmap(@"C:\2\torec2.png", true);
        List<Bitmap> toRecognize = new List<Bitmap>();
        toRecognize.Add(bpt1);
        toRecognize.Add(bpt2);

I keep a library of known letters in Dictionary.

            Bitmap le = new Bitmap(@"C:\2\e.png", true);
            Bitmap lg = new Bitmap(@"C:\2\g.png", true);
            Bitmap ln = new Bitmap(@"C:\2\n.png", true);
            Bitmap li = new Bitmap(@"C:\2\i.png", true);
            Bitmap ls = new Bitmap(@"C:\2\s.png", true);
            Bitmap lt = new Bitmap(@"C:\2\t.png", true);
            var dict = new Dictionary<string, Bitmap>();
            dict.Add("e", le);
            dict.Add("g", lg);
            dict.Add("n", ln);
            dict.Add("i", li);
            dict.Add("s", ls);
            dict.Add("t", lt);

Then I create New List with Images - from library:

var target = dict.ToList();

And do the comparison of images: (target[index].Key, target[index].Value)

for (int i = 0; i < x; i++)
{
   for (int j = 0; j < y; j++)
   {
       if (CompareMemCmp(toRecognize[i], target[j].Value) == true)
       {
       textBox3.AppendText("Found!" + Environment.NewLine);
       textBox2.AppendText(target[j].Key); //Letter is found - save it!
       }
       else {textBox3.AppendText("Don't match!" + Environment.NewLine); }
   }
}

1. [removed]

2. Is the method that I used tolerable from the perspective of performance? I'm planning to do the recornition of 10-20 images at the same time (average letter count for each is 8) and the library for letters will consist of English alphabet (26 upper + 26 lower case), special letter(~10) and Numbers (10).

So I have 80+ letters that have to be recognized and pattern library which consists of ~70+ characters. Will the performance be at a good level?

Constructive criticism gladly accepted. ;)

Answer 1

Question 1:

[removed]

Question 2:

It depends.
First of all, if performance is not enough, what's your bottleneck ?
I suspect it's CompareMemCmp() function... so can you speed-up it ?

If not, given that each iteration of your loop seems independent from the previous ones, you could try to run it in parallel.
To do this have a look at the Task Parallel Library methods of framework 4.0, in particular to Parallel.For.

EDIT :

If we are talking about perfect matching between images, you can try to use dictionary look-up to speed things up.

First, you can build a wrapper class for Bitmap that can be efficiently used as Dictionary<> key, like this:

class BitmapWrapper
{
    private readonly int hash;
    public Bitmap Image { get; private set; }
    public BitmapWrapper(Bitmap img)
    {
        this.Image = img;
        this.hash = this.ComputeHash();
    }

    private int ComputeHash()
    {
        // you could turn this code into something unsafe to speed-up GetPixel
        // e.g. using lockbits etc...
        unchecked // Overflow is fine, just wrap
        {
            int h = 17;
            for (int x = 0; x < this.Image.Size.Width; x++)
                for (int y = 0; y < this.Image.Size.Height; y++)
                    h = h * 23 + this.Image.GetPixel(x, y).GetHashCode();
            return h;
        }
    }

    public override int GetHashCode()
    {
        return this.hash;
    }
    public override bool Equals(object obj)
    {
        var objBitmap = obj as Bitmap;
        if (obj == null)
            return false;
        // use CompareMemCmp in case of hash collisions 
        return Utils.CompareMemCmp(this.Image, objBitmap); 
    }
}

This class computes the hascode in ComputeHash method that is inspired by this answer (but you can just ex-or every pixel). That surely can be improved by involving unsafe code (something like in the CompareMemCmp method).

Once you have this class, you can build a look-up dictionary like this:

Bitmap le = new Bitmap(@"C:\2\e.png", true);
Bitmap lg = new Bitmap(@"C:\2\g.png", true);
...
var lookup = new Dictionary<string, Bitmap>();
lookup.Add(new BitmapWrapper(le), "e");
lookup.Add(new BitmapWrapper(lg), "g");
...

then the search will be simply:

foreach(var imgToRecognize in toRecognize)
{
   string letterFound;
   if(lookup.TryGetValue(new BitmapWrapper(imgToRecognize), out letterFound))
   {
      textBox3.AppendText("Found!" + Environment.NewLine);
      textBox2.AppendText(letterFound); //Letter is found - save it!
   }
   else
      textBox3.AppendText("Don't match!" + Environment.NewLine);
}

The performances of this method definitely depends on the hash computation, but certainly they can save a lot of CompareMemCmp() calls.

Answer 2

If C# is the right tool for the job depends on how big your images are. A hash table is a nice approach but you need to compare the whole image before you can check if you have a match. Xoring the images is very fast but you need to xor all images until you find the matching ones which is quite inefficient.

A better approach would be to choose a fingerprint which is designed in a way that you need to read only minimal amount of data. E.g. you can generate a hash code of a vertical line in the middle if your image which would produce a different value for each of your images. If not adapt the approach until you arrive at an algorithm where you do not need to read the image as a whole but only a few bytes until you can assign the image to the right bucket. This does only work if your input data contains only the images in your dictionary. Otherwise it would be only a probabilistic method.