distance/similarity between 2 bitmap images in C#

Question

I came across the following code taken from here:

using System;
using System.Drawing;

class Program
{
    static void Main()
    {
        Bitmap img1 = new Bitmap("Lenna50.jpg");
        Bitmap img2 = new Bitmap("Lenna100.jpg");

        if (img1.Size != img2.Size)
        {
            Console.Error.WriteLine("Images are of different sizes");
            return;
        }

        float diff = 0;

        for (int y = 0; y < img1.Height; y++)
        {
            for (int x = 0; x < img1.Width; x++)
            {
                diff += (float)Math.Abs(img1.GetPixel(x, y).R - img2.GetPixel(x, y).R) / 255;
                diff += (float)Math.Abs(img1.GetPixel(x, y).G - img2.GetPixel(x, y).G) / 255;
                diff += (float)Math.Abs(img1.GetPixel(x, y).B - img2.GetPixel(x, y).B) / 255;
            }
        }

        Console.WriteLine("diff: {0} %", 100 * diff / (img1.Width * img1.Height * 3));
    }
}

Unfortunately, this is really slow. Is anyone aware of a faster way of calculating the distance between 2 images? Thanks!

To provide some more context as well. I am working on something like this:

https://rogerjohansson.blog/2008/12/07/genetic-programming-evolution-of-mona-lisa/

I evolve SVGs which are then translated into a Bitmap and compared to the target image.

Just came across the aforgenet library - see for example:

enter link description here

PS:

I start to rewrite the above using LockBits. The code below is my current attempt but I am a bit stuck. Please note, that bmp1 is the 'target picture' and does not really change - hence the copying can be factored out/only needs to be done once. The Bitmap bmp2 is passed in and to be compared with bmp1 (there are 100s of bmp2s). Ultimately, I would like to determine the similarity between bmp1 and bmp2 using some distance (e.g. Euclidean distance of bytes?). Any pointers regarding this and how to speed the code up would be very much appreciated. Thanks!

public double Compare(Bitmap bmp1, Bitmap bmp2)
{
    BitmapData bitmapData1 = bmp1.LockBits(new Rectangle(0, 0, bmp1.Width, bmp1.Height), ImageLockMode.ReadWrite, bmp1.PixelFormat);
    BitmapData bitmapData2 = bmp2.LockBits(new Rectangle(0, 0, bmp2.Width, bmp2.Height), ImageLockMode.ReadWrite, bmp2.PixelFormat);

    IntPtr ptr1 = bitmapData1.Scan0;
    int bytes1 = bitmapData1.Stride * bmp1.Height;
    byte[] rgbValues1 = new byte[bytes1];
    byte[] r1 = new byte[bytes1 / 3];
    byte[] g1 = new byte[bytes1 / 3];
    byte[] b1 = new byte[bytes1 / 3];
    Marshal.Copy(ptr1, rgbValues1, 0, bytes1);
    bmp1.UnlockBits(bitmapData1);

    IntPtr ptr2 = bitmapData2.Scan0;
    int bytes2 = bitmapData2.Stride * bmp2.Height;
    byte[] rgbValues2 = new byte[bytes2];
    byte[] r2 = new byte[bytes2 / 3];
    byte[] g2 = new byte[bytes2 / 3];
    byte[] b2 = new byte[bytes2 / 3];
    Marshal.Copy(ptr2, rgbValues2, 0, bytes2);
    bmp2.UnlockBits(bitmapData2);

    int stride = bitmapData1.Stride;
    for (int column = 0; column < bitmapData1.Height; column++)
    {
        for (int row = 0; row < bitmapData1.Width; row++)
        {
            //????      
        }
    }

    return 0;
}

PPS:

I (think I) made some more progress. The following code seems to work:

using System.Drawing;
using System.Drawing.Imaging;
using Color = System.Drawing.Color;

namespace ClassLibrary1
{
  public unsafe class BitmapComparer : IBitmapComparer
  {
    private readonly Color[] _targetBitmapColors;
    private readonly int _width;
    private readonly int _height;
    private readonly int _maxPointerLength;
    private readonly PixelFormat _pixelFormat;

    public BitmapComparer(Bitmap targetBitmap)
    {
      _width = targetBitmap.Width;
      _height = targetBitmap.Height;
      _maxPointerLength = _width * _height;
      _pixelFormat = targetBitmap.PixelFormat;
      _targetBitmapColors = new Color[_maxPointerLength];

      var bData = targetBitmap.LockBits(new Rectangle(0, 0, _width, _height), ImageLockMode.ReadWrite, _pixelFormat);
      var scan0 = (byte*) bData.Scan0.ToPointer();

      for (var i = 0; i < _maxPointerLength; i += 4)
      {
        _targetBitmapColors[i] = Color.FromArgb(scan0[i + 2], scan0[i + 1], scan0[i + 0]);
      }

      targetBitmap.UnlockBits(bData);
    }

    // https://rogerjohansson.blog/2008/12/09/genetic-programming-mona-lisa-faq/
    public double Compare(Bitmap bitmapToCompareWith)
    {
      var bData = bitmapToCompareWith.LockBits(new Rectangle(0, 0, _width, _height), ImageLockMode.ReadWrite, _pixelFormat);
      var scan0 = (byte*) bData.Scan0.ToPointer();
      double distance = 0;

      for (var i = 0; i < _maxPointerLength; i += 4)
      {
        distance += 
                ( ((_targetBitmapColors[i].R - scan0[i + 2]) * (_targetBitmapColors[i].R - scan0[i + 2]))
                + ((_targetBitmapColors[i].G - scan0[i + 1]) * (_targetBitmapColors[i].G - scan0[i + 1]))
                + ((_targetBitmapColors[i].B - scan0[i + 0]) * (_targetBitmapColors[i].B - scan0[i + 0])));
      }

      bitmapToCompareWith.UnlockBits(bData);

      return distance;
    }
  }
}

Using `GetPixel` only __once per pixel__ is a simple imnprovement. Using `LockBits` is the way to reasonable speed. — TaW, Dec 23 '18 at 18:32
See [Bitmap.LockBits](https://learn.microsoft.com/en-us/dotnet/api/system.drawing.bitmap.lockbits). But, what kind of *distance* is this? — Jimi, Dec 23 '18 at 18:34
@Jimi the distance is to determine similarity. Smaller values indicate greater similarity. I could also live with a directional value. Perhaps I should just sample a few thousand pixels and then do the comparison or reduce the resolution of the bitmaps ... — cs0815, Dec 23 '18 at 18:49
Well, since @TaW commented here, here are a couple of his answers on the subject: [How to find the difference between two images?](https://stackoverflow.com/a/26225153/7444103) -- [How to get difference between 2 images](https://stackoverflow.com/a/24409305/7444103). You may also want take a look at the K-Means clustering algo: [Implementing K-Means Image Segmentation Algorithm](https://www.codeproject.com/Articles/1203227/Implementing-K-Means-Image-Segmentation-Algorithm) -- [K-Means Data Clustering](https://visualstudiomagazine.com/articles/2013/12/01/k-means-data-clustering-using-c.aspx). — Jimi, Dec 23 '18 at 19:08
Or depending on the actual purpose of this process, a [Convolution](https://en.wikipedia.org/wiki/Kernel_(image_processing)#Convolution) applied with a [Difference of Gaussians](https://en.wikipedia.org/wiki/Difference_of_Gaussians). [General definition of Convolution](https://en.wikipedia.org/wiki/Convolution#Fast_convolution_algorithms). It is applied in combination with different image processing algorithms. — Jimi, Dec 23 '18 at 19:36
@TaW or anyone else. How could I use LockBits to speed up the above algorithm please? — cs0815, Dec 24 '18 at 14:16
Will do after x-mas :-) - __Some__ of [these](https://stackoverflow.com/search?q=user%3A3152130+lockbits) should put you on the right track. Really good advice would need a much deeper understanding of what you want to achieve and with what kind of data..!! Best try to expand the question with more details like purpose, source and format of images, sizes etc. Example: Two scans of text, one shifted by a few pixels are really similar, no? But the measure you have will find they are totally different..!? — TaW, Dec 24 '18 at 16:49
[LockBitmap with example](https://stackoverflow.com/a/42602506/3110834). It has `GetPixel` and `SetPixel` and you can easily apply to your code. — Reza Aghaei, Dec 27 '18 at 07:16
Entire books have been written on this subject. If you're concerned about speed, why don't you use existing solutions, like OpenCV with the Template Matching algorithm for example: https://docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/template_matching/template_matching.html OpenCV can be used in C# with OpenCvSharp nuget. I could provide an example. — Simon Mourier, Dec 27 '18 at 12:26
@SimonMourier I was aware of OpenCV but always thought that it can only be used in Python, which I can invoke from C# .... Thanks. — cs0815, Dec 27 '18 at 12:34

Todor Balabanov · Answer 1 · 2020-07-03T14:23:40.000

Using all pixels always will be time-consuming. What if you use a randomly selected pixels sample of the images. Also, you can apply hierarchical image granularity. In this way, you will get more information about the details presented in the images.

I am also working on a similar project. It is available in GitHub under the name Ellipses-Image-Approximator.

Something like this:

package eu.veldsoft.ellipses.image.approximator;

import java.awt.image.BufferedImage;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * Compare to raster images by using Euclidean distance between the pixels but
 * in probabilistic sampling on hierarchical image detailization.
 * 
 * @author Todor Balabanov
 */
class HierarchicalProbabilisticImageComparator implements ImageComparator {
    /** A pseudo-random number generator instance. */
    private static final Random PRNG = new Random();

    /**
     * Euclidean distance color comparator instance.
     */
    private static final ColorComparator EUCLIDEAN = new EuclideanColorComparator();

    /** Recursive descent depth level. */
    private int depthLevel = 1;

    /**
     * Size of the sample in percentages from the size of the population (from
     * 0.0 to 1.0).
     */
    private double samplePercent = 0.1;

    /** A supportive array for the first image pixels. */
    private int aPixels[] = null;

    /** A supportive array for the second image pixels. */
    private int bPixels[] = null;

    /**
     * Constructor without parameters for default members' values.
     */
    public HierarchicalProbabilisticImageComparator() {
        this(1, 0.1);
    }

    /**
     * Constructor with all parameters.
     * 
     * @param depthLevel
     *            Recursive descent depth level.
     * @param samplePercent
     *            Size of the sample in percentages from the size of the
     *            population (from 0.0 to 1.0).
     */
    public HierarchicalProbabilisticImageComparator(int depthLevel,
            double samplePercent) {
        super();

        this.depthLevel = depthLevel;
        this.samplePercent = samplePercent;
    }

    private double distance(int width, int level, int minX, int minY, int maxX,
            int maxY) {
        /*
         * At the bottom of the recursive descent, distance is zero, and
         * descending is canceled.
         */
        if (level > depthLevel) {
            return 0;
        }

        /* Rectangle's boundaries should be observed. */
        if (maxX <= minX || maxY <= minY) {
            return 0;
        }

        /*
         * Sample size calculated according formula.
         * 
         * https://www.surveymonkey.com/mp/sample-size-calculator/
         */
        int sampleSize = (int) ((maxX - minX) * (maxY - minY) * samplePercent);

        /* Generate unique indices of pixels with the size of the sample. */
        Set<Integer> indices = new HashSet<Integer>();
        while (indices.size() < sampleSize) {
            int x = minX + PRNG.nextInt(maxX - minX + 1);
            int y = minY + PRNG.nextInt(maxY - minY + 1);
            indices.add(y * width + x);
        }

        /* The Euclidean distance of the randomly selected pixels. */
        double sum = 0;
        for (int index : indices) {
            sum += EUCLIDEAN.distance(aPixels[index], bPixels[index]);
        }

        /* Do a recursive descent. */
        return (sum / sampleSize) * level
                + distance(width, level + 1, minX, minY,
                        maxX - (maxX - minX) / 2, maxY - (maxY - minY) / 2)
                + distance(width, level + 1, maxX - (maxX - minX) / 2, minY,
                        maxX, maxY - (maxY - minY) / 2)
                + distance(width, level + 1, minX, maxY - (maxY - minY) / 2,
                        maxX - (maxX - minX) / 2, maxY)
                + distance(width, level + 1, maxX - (maxX - minX) / 2,
                        maxY - (maxY - minY) / 2, maxX, maxY);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public double distance(BufferedImage a, BufferedImage b) {
        if (a.getWidth() != b.getWidth()) {
            throw new RuntimeException("Images width should be identical!");
        }

        if (a.getHeight() != b.getHeight()) {
            throw new RuntimeException("Images height should be identical!");
        }

        aPixels = a.getRGB(0, 0, a.getWidth(), a.getHeight(), null, 0,
                a.getWidth());

        bPixels = b.getRGB(0, 0, b.getWidth(), b.getHeight(), null, 0,
                b.getWidth());

        /* Do a recursive calculation. */
        return distance(Math.min(a.getWidth(), b.getWidth()), 1, 0, 0,
                Math.min(a.getWidth() - 1, b.getWidth() - 1),
                Math.min(a.getHeight() - 1, b.getHeight() - 1));
    }
}

Kvam · Accepted Answer · 2018-12-28T22:14:33.227

As others have pointed out, you can use BitMap.LockBits and use pointers instead of GetPixel. The following runs about 200 times faster than the original approach:

static float CalculateDifference(Bitmap bitmap1, Bitmap bitmap2)
{
    if (bitmap1.Size != bitmap2.Size)
    {
        return -1;
    }

    var rectangle = new Rectangle(0, 0, bitmap1.Width, bitmap1.Height);

    BitmapData bitmapData1 = bitmap1.LockBits(rectangle, ImageLockMode.ReadOnly, bitmap1.PixelFormat);
    BitmapData bitmapData2 = bitmap2.LockBits(rectangle, ImageLockMode.ReadOnly, bitmap2.PixelFormat);

    float diff = 0;
    var byteCount = rectangle.Width * rectangle.Height * 3;

    unsafe
    {
        // scan to first byte in bitmaps
        byte* pointer1 = (byte*)bitmapData1.Scan0.ToPointer();
        byte* pointer2 = (byte*)bitmapData2.Scan0.ToPointer();

        for (int x = 0; x < byteCount; x++)
        {
            diff += (float)Math.Abs(*pointer1 - *pointer2) / 255;
            pointer1++;
            pointer2++;
        }
    }

    bitmap1.UnlockBits(bitmapData1);
    bitmap2.UnlockBits(bitmapData2);

    return 100 * diff / byteCount;
}

distance/similarity between 2 bitmap images in C#

2 Answers2