C# image flood fill algorithm improvement

Question

I'm working on a screen sharing app, which runs a loop and grab fast screenshots using GDI methods . example here

Of course I also use a flood fill algorithm to find the changes areas between 2 images (previous screenshot and current).

I use another small trick - I downscale the snapshot resolution in 10, because processing 1920*1080=2073600 pixels very constantly is not very efficient.

However when I find the rectangle bounds - I apply it on the original full size bitmap and I just multiply by 10 the dimension (including top, left, width, height).

This is the scanning code:

    unsafe bool ArePixelsEqual(byte* p1, byte* p2, int bytesPerPixel)
    {
        for (int i = 0; i < bytesPerPixel; ++i)
            if (p1[i] != p2[i])
                return false;
        return true;
    }

    private unsafe List<Rectangle> CodeImage(Bitmap bmp, Bitmap bmp2)
    {
       List<Rectangle> rec = new List<Rectangle>();
        var bmData1 = bmp.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp.PixelFormat);
        var bmData2 = bmp2.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp2.PixelFormat);

        int bytesPerPixel = 4;
        IntPtr scan01 = bmData1.Scan0;
        IntPtr scan02 = bmData2.Scan0;
        int stride1 = bmData1.Stride;
        int stride2 = bmData2.Stride;
        int nWidth = bmp.Width;
        int nHeight = bmp.Height;
        bool[] visited = new bool[nWidth * nHeight];

        byte* base1 = (byte*)scan01.ToPointer();
        byte* base2 = (byte*)scan02.ToPointer();

        for (int y = 0; y < nHeight; y ++)
        {
            byte* p1 = base1;
            byte* p2 = base2;

            for (int x = 0; x < nWidth; ++x)
            {
                if (!ArePixelsEqual(p1, p2, bytesPerPixel) && !(visited[x + nWidth * y]))
                {
                    // fill the different area
                    int minX = x;
                    int maxX = x;
                    int minY = y;
                    int maxY = y;

                    var pt = new Point(x, y);

                    Stack<Point> toBeProcessed = new Stack<Point>();
                    visited[x + nWidth * y] = true;
                    toBeProcessed.Push(pt);
                    while (toBeProcessed.Count > 0)
                    {
                        var process = toBeProcessed.Pop();
                        var ptr1 = (byte*)scan01.ToPointer() + process.Y * stride1 + process.X * bytesPerPixel;
                        var ptr2 = (byte*)scan02.ToPointer() + process.Y * stride2 + process.X * bytesPerPixel;
                        //Check pixel equality
                        if (ArePixelsEqual(ptr1, ptr2, bytesPerPixel))
                            continue;

                        //This pixel is different
                        //Update the rectangle
                        if (process.X < minX) minX = process.X;
                        if (process.X > maxX) maxX = process.X;
                        if (process.Y < minY) minY = process.Y;
                        if (process.Y > maxY) maxY = process.Y;

                        Point n; int idx;
                        //Put neighbors in stack
                        if (process.X - 1 >= 0)
                        {
                            n = new Point(process.X - 1, process.Y); idx = n.X + nWidth * n.Y;
                            if (!visited[idx]) { visited[idx] = true; toBeProcessed.Push(n); }
                        }

                        if (process.X + 1 < nWidth)
                        {
                            n = new Point(process.X + 1, process.Y); idx = n.X + nWidth * n.Y;
                            if (!visited[idx]) { visited[idx] = true; toBeProcessed.Push(n); }
                        }

                        if (process.Y - 1 >= 0)
                        {
                            n = new Point(process.X, process.Y - 1); idx = n.X + nWidth * n.Y;
                            if (!visited[idx]) { visited[idx] = true; toBeProcessed.Push(n); }
                        }

                        if (process.Y + 1 < nHeight)
                        {
                            n = new Point(process.X, process.Y + 1); idx = n.X + nWidth * n.Y;
                            if (!visited[idx]) { visited[idx] = true; toBeProcessed.Push(n); }
                        }
                    }

                       //finaly set a rectangle.
                             Rectangle r = new Rectangle(minX * 10, minY * 10, (maxX - minX + 1) * 10, (maxY - minY + 1) * 10);
                            rec.Add(r);

                            //got the rectangle now i'll do whatever i want with that.
                            //notify i scaled everything by x10 becuse i want to apply the changes on the originl 1920x1080 image.

                }

            p1 += bytesPerPixel;
            p2 += bytesPerPixel;
        }

        base1 += stride1;
        base2 += stride2;
    }


        bmp.UnlockBits(bmData1);
        bmp2.UnlockBits(bmData2);

        return rec;
    }

This is my call:

  private void Start()
  {     
     full1 = GetDesktopImage();//the first,intial screen.

     while (true)
     {
         full2 = GetDesktopImage();
         a = new Bitmap(full1, 192, 108);//resizing for faster processing the images.
         b = new Bitmap(full2, 192, 108);  // resizing for faster processing the images.
         CodeImage(a, b);

         count++;          // counter for the performance.
         full1 = full2;    // assign old to current bitmap.
      }
    }

However, after all the tricks and techniques I used, the algorithm runs quite slow... on my machine - Intel i5 4670k 3.4ghz - it runs only 20 times-means CodeImage method execution is 50ms! (at the maximum! It might get lower)! It maybe sounds fast (don't forget I have to send each changed area over the network after), but I'm looking to achieve more processed image per second. I think the main bottleneck is in the resizing of the 2 images - but I just thought it would be even faster after resizing - because it would have to loop through less pixels... 192*108=200,000 only..

I would appreciate any help, any improvement.

If anything not clear enough i'll edit and rewrite it.

Answer 1

EDIT: I've done some profiling and it's not your code or the resize that's taking the longest, but the screen capture itself. I've updated my sample code with the code I've used to test:

    public static void ResizeImage(Bitmap image, Bitmap destImage)
    {
        var destRect = new Rectangle(0, 0, destImage.Width, destImage.Height);

        using (var graphics = Graphics.FromImage(destImage))
        {
            graphics.CompositingMode = CompositingMode.SourceCopy;
            graphics.CompositingQuality = CompositingQuality.HighSpeed;
            graphics.InterpolationMode = InterpolationMode.Low;
            graphics.SmoothingMode = SmoothingMode.None;
            graphics.PixelOffsetMode = PixelOffsetMode.Default;

            using (var wrapMode = new ImageAttributes())
            {
                wrapMode.SetWrapMode(WrapMode.TileFlipXY);
                graphics.DrawImage(image, destRect, 0, 0, image.Width, image.Height, GraphicsUnit.Pixel, wrapMode);
            }
        }
    }

    private void CaptureScreen(Bitmap destImage)
    {
        using (var graphics = Graphics.FromImage(destImage))
        {
            graphics.CopyFromScreen(0, 0, 0, 0, new Size(destImage.Width, destImage.Height), CopyPixelOperation.SourceCopy);
        }

    }

    public void Start()
    {
        var size = new Size(1920, 1080);
        var fullSizeImgs = new Bitmap[2]
        {
            new Bitmap(size.Width, size.Height),
            new Bitmap(size.Width, size.Height)
        };

        var resizedImgs = new Bitmap[2]
        {
            new Bitmap((int)(size.Width / 10.0f), (int)(size.Height / 10.0f)),
            new Bitmap((int)(size.Width / 10.0f), (int)(size.Height / 10.0f))
        };

        var globalWatch = new Stopwatch();
        var codeWatch = new Stopwatch();

        int current = 0;
        int counter = 0;
        CaptureScreen(fullSizeImgs[current]);
        ResizeImage(fullSizeImgs[current], resizedImgs[current]);

        globalWatch.Start();
        while (true)
        {
            var next = (current + 1) % 2;
            long totalFrameTime = 0;

            {
                codeWatch.Reset();
                codeWatch.Start();
                CaptureScreen(fullSizeImgs[next]);
                codeWatch.Stop();
                var elapsed = codeWatch.ElapsedMilliseconds;
                Console.WriteLine("Capture : {0} ms", elapsed);
                totalFrameTime += elapsed;
            }

            {
                codeWatch.Reset();
                codeWatch.Start();
                ResizeImage(fullSizeImgs[next], resizedImgs[next]);
                codeWatch.Stop();
                var elapsed = codeWatch.ElapsedMilliseconds;
                Console.WriteLine("Resize : {0} ms", elapsed);
                totalFrameTime += elapsed;
            }

            {
                codeWatch.Reset();
                codeWatch.Start();
                var rects = CodeImage(resizedImgs[current], resizedImgs[next]);
                codeWatch.Stop();
                var elapsed = codeWatch.ElapsedMilliseconds;
                Console.WriteLine("Code : {0} ms", elapsed);
                totalFrameTime += elapsed;
            }
            counter++;
            Console.WriteLine("Total : {0} ms\nFPS : {1}\n", totalFrameTime, counter / ((double)globalWatch.ElapsedMilliseconds / 1000.0));
            current = (current + 1) % 2;
        }
        globalWatch.Stop();
    }

On average I get 20 FPS on my computer, whether I use smaller images or not. Given that the screen capture itself already takes 30-40 ms you have very little wiggle room.

You could evaluate other technologies (DirectX, mirrored-driver etc..). You can look at this post and that one for some pointers into how each technology compares.