Feeds:
Posts
Comments

Archive for the ‘Image Processing’ Category

For various projects I’ve had a need to determine how similar two images are. Some of my projects do this for hundreds of thousands of image pairs. This means I want it to work fast. This is a survey of the methods I’ve tried.

We’re going to determine how similar the following two images are.

Here’s the test harness:

    public class Test
    {
        private const int RunCount = 10000;
        private const string PathToImage1 = @"..\Release\240px-Mona_Lisa-restored.jpg";
        private const string PathToImage2 = @"..\Release\image_100138.png";

        public void TimeGettingDifference(Func<Bitmap, Bitmap, int> getDifference)
        {
            var image1 = new Bitmap(PathToImage1);
            var image2 = new Bitmap(PathToImage2);

            Assert.AreEqual(image1.GetBytesFromBitmap().Length, image2.GetBytesFromBitmap().Length);

            var stopwatch = new Stopwatch();
            stopwatch.Start();

            int difference = 0;
            for (int i = 0; i < RunCount; i++)
            {
                difference = getDifference(image1, image2);
            }
            stopwatch.Stop();
            var elapsedSeconds = stopwatch.Elapsed.TotalSeconds;
            Console.WriteLine("Average over "+RunCount+" runs: "+(elapsedSeconds/RunCount)+" seconds - "+difference);
        }
    }

This makes it easy to try different methods. All we have to do is pass in a function that takes two bitmaps and returns an integer representing the sum of the byte differences between the two Bitmaps.

Version 1

        public void Get_bytes_and_use_linq_to_sum_differences()
        {
            Func<Bitmap, Bitmap, int> getDifference = (image1, image2) =>
                {
                    var image1Bytes = image1.GetBytesFromBitmap();
                    var image2Bytes = image2.GetBytesFromBitmap();

                    return Enumerable.Range(0, image1Bytes.Length)
                        .Select(index => Math.Abs(image1Bytes[index] - image2Bytes[index]))
                        .Sum();

                };
            TimeGettingDifference(getDifference);
        }

    public static class BitmapExtensions
    {
        public static byte[] GetBytesFromBitmap(this Bitmap bitmap)
        {
            var rectangle = new System.Drawing.Rectangle(0, 0, bitmap.Width, bitmap.Height);
            var bData = bitmap.LockBits(rectangle, ImageLockMode.ReadWrite, bitmap.PixelFormat);
            byte[] data;
            try
            {
                int size = bData.Stride * bData.Height;
                data = new byte[size];
                Marshal.Copy(bData.Scan0, data, 0, size);
            }
            finally
            {
                bitmap.UnlockBits(bData);
            }
            return data;
        }
    }

result:

Average over 10000 runs: 0.00593082636 seconds - 5282185

Version 2

        public void Get_bytes_and_use_unsafe_loop_to_sum_differences()
        {
            Func<Bitmap, Bitmap, int> getDifference = (image1, image2) =>
                {
                    var image1Bytes = image1.GetBytesFromBitmap();
                    var image2Bytes = image2.GetBytesFromBitmap();

                    return GetDifferencesWithBytes(image1Bytes, image2Bytes);

                };
            TimeGettingDifference(getDifference);
        }

        public static int GetDifferencesWithBytes(byte[] image1Bytes, byte[] image2Bytes)
        {
            int size = image1Bytes.Length;
            int difference = 0;
            unsafe
            {
                fixed (byte* image1Ptr = image1Bytes, image2Ptr = image2Bytes)
                {
                    byte* ptrImage1Byte = image1Ptr, ptrImage2Byte = image2Ptr;
                    for (; size > 0; size--)
                    {
                        if (*ptrImage1Byte > *ptrImage2Byte)
                        {
                            difference += (*ptrImage1Byte - *ptrImage2Byte);
                        }
                        else
                        {
                            difference += (*ptrImage2Byte - *ptrImage1Byte);
                        }

                        ptrImage1Byte++;
                        ptrImage2Byte++;
                    }
                }
            }

            return difference;
        }

result:

Average over 10000 runs: 0.00107074605 seconds - 5282185

Version 3

        public void Pin_bytes_and_use_unsafe_byte_loop_to_sum_differences()
        {
            TimeGettingDifference(LockBitsAndGetDifferenceWithBytes);
        }

        public int LockBitsAndGetDifferenceWithBytes(Bitmap image1, Bitmap image2)
        {
            var rectangle = new System.Drawing.Rectangle(0, 0, image1.Width, image1.Height);
            var image1Data = image1.LockBits(rectangle, ImageLockMode.ReadWrite, image1.PixelFormat);
            var image2Data = image2.LockBits(rectangle, ImageLockMode.ReadWrite, image2.PixelFormat);
            int difference = 0;
            try
            {
                int size = image1Data.Stride * image1Data.Height;
                unsafe
                {
                    var image1Ptr = (byte*)(image1Data.Scan0.ToPointer());
                    var image2Ptr = (byte*)(image2Data.Scan0.ToPointer());

                    byte* ptrImage1Byte = image1Ptr, ptrImage2Byte = image2Ptr;
                    for (int len = size; len > 0; len--)
                    {
                        if (*ptrImage1Byte > *ptrImage2Byte)
                        {
                            difference += (*ptrImage1Byte - *ptrImage2Byte);
                        }
                        else
                        {
                            difference += (*ptrImage2Byte - *ptrImage1Byte);
                        }

                        ptrImage1Byte++;
                        ptrImage2Byte++;
                    }
                }
            }
            finally
            {
                image1.UnlockBits(image1Data);
                image2.UnlockBits(image2Data);
            }
            return difference;
        }

result:

Average over 10000 runs: 0.00081027626 seconds - 5282185

Version 4

        [Test]
        public void Pin_bytes_and_use_unsafe_int_loop_to_sum_differences()
        {
            TimeGettingDifference(LockBitsAndGetDifferenceWithIntegers);
        }

        public int LockBitsAndGetDifferenceWithIntegers(Bitmap image1, Bitmap image2)
        {
            var rectangle = new System.Drawing.Rectangle(0, 0, image1.Width, image1.Height);
            var image1Data = image1.LockBits(rectangle, ImageLockMode.ReadWrite, image1.PixelFormat);
            var image2Data = image2.LockBits(rectangle, ImageLockMode.ReadWrite, image2.PixelFormat);
            int difference = 0;
            try
            {
                int size = image1Data.Stride * image1Data.Height;
                int len = size/4;
                unsafe
                {
                    var image1Ptr = (int*)(image1Data.Scan0.ToPointer());
                    var image2Ptr = (int*)(image2Data.Scan0.ToPointer());

                    int* ptrImage1Byte = image1Ptr, ptrImage2Byte = image2Ptr;
                    for (; len > 0; len--)
                    {
                        var a1 = (byte)(*ptrImage1Byte >> 24);
                        var b1 = (byte)(*ptrImage2Byte >> 24);
                        difference += a1 > b1 ? a1 - b1 : b1 - a1;
                        a1 = (byte)(*ptrImage1Byte >> 16);
                        b1 = (byte)(*ptrImage2Byte >> 16);
                        difference += a1 > b1 ? a1 - b1 : b1 - a1;
                        a1 = (byte)(*ptrImage1Byte >> 8);
                        b1 = (byte)(*ptrImage2Byte >> 8);
                        difference += a1 > b1 ? a1 - b1 : b1 - a1;
                        a1 = (byte)(*ptrImage1Byte);
                        b1 = (byte)(*ptrImage2Byte);
                        difference += a1 > b1 ? a1 - b1 : b1 - a1;
                        ptrImage1Byte++;
                        ptrImage2Byte++;
                    }
                }
            }
            finally
            {
                image1.UnlockBits(image1Data);
                image2.UnlockBits(image2Data);
            }
            return difference;
        }

result:

Average over 10000 runs: 0.00086579786 seconds - 5282185

So far Version 3 is the fastest. One caveat with Versions 3 and 4 is both images must have the same stride.

Do you know of a faster way to do it without using multiple processors?

Advertisements

Read Full Post »

%d bloggers like this: