Как найти прямоугольник разницы между двумя изображениями

У меня есть два изображения одинакового размера. Как лучше всего найти прямоугольник, которым они отличаются. Очевидно, я мог пройти изображение 4 раза в разных направлениях, но мне интересно, есть ли более легкий путь.

Пример:

http://i44.tinypic.com/2cg0u2h.png

http://i43.tinypic.com/14l0y13.png

http://i40.tinypic.com/5agshd.png

6 ответов

Решение

Я не думаю, что есть более простой способ.

Фактически, это будет всего лишь (очень) несколько строк кода, поэтому, если вы не найдете библиотеку, которая сделает это непосредственно для вас, вы не найдете более короткого пути.

Если вам нужен один прямоугольник, используйте int.MaxValue для порога.

var diff = new ImageDiffUtil(filename1, filename2);
var diffRectangles = diff.GetDiffRectangles(int.MaxValue);

https://stackru.com/images/19236067afdf672c39a43c8cf7b6b6ea77fafdf3.png

Если вам нужно несколько прямоугольников, используйте меньший порог.

var diff = new ImageDiffUtil(filename1, filename2);
var diffRectangles = diff.GetDiffRectangles(8);

https://stackru.com/images/44f9aec615028fb5f2d21a5cd0758671f6419d8d.png

ImageDiffUtil.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace diff_images
{
    public class ImageDiffUtil
    {
        Bitmap image1;
        Bitmap image2;

        public ImageDiffUtil(string filename1, string filename2)
        {
            image1 = Image.FromFile(filename1) as Bitmap;
            image2 = Image.FromFile(filename2) as Bitmap;
        }

        public IList<Point> GetDiffPixels()
        {
            var widthRange = Enumerable.Range(0, image1.Width);
            var heightRange = Enumerable.Range(0, image1.Height);

            var result = widthRange
                            .SelectMany(x => heightRange, (x, y) => new Point(x, y))
                            .Select(point => new
                            {
                                Point = point,
                                Pixel1 = image1.GetPixel(point.X, point.Y),
                                Pixel2 = image2.GetPixel(point.X, point.Y)
                            })
                            .Where(pair => pair.Pixel1 != pair.Pixel2)
                            .Select(pair => pair.Point)
                            .ToList();

            return result;
        }

        public IEnumerable<Rectangle> GetDiffRectangles(double distanceThreshold)
        {
            var result = new List<Rectangle>();

            var differentPixels = GetDiffPixels();

            while (differentPixels.Count > 0)
            {
                var cluster = new List<Point>()
                {
                    differentPixels[0]
                };
                differentPixels.RemoveAt(0);

                while (true)
                {
                    var left = cluster.Min(p => p.X);
                    var right = cluster.Max(p => p.X);
                    var top = cluster.Min(p => p.Y);
                    var bottom = cluster.Max(p => p.Y);
                    var width = Math.Max(right - left, 1);
                    var height = Math.Max(bottom - top, 1);
                    var clusterBox = new Rectangle(left, top, width, height);

                    var proximal = differentPixels
                                        .Where(point => GetDistance(clusterBox, point) <= distanceThreshold)
                                        .ToList();
                    proximal.ForEach(point => differentPixels.Remove(point));

                    if (proximal.Count == 0)
                    {
                        result.Add(clusterBox);
                        break;
                    }
                    else
                    {
                        cluster.AddRange(proximal);
                    }
                };
            }

            return result;
        }

        static double GetDistance(Rectangle rect, Point p)
        {
            var dx = Math.Max(rect.Left - p.X, 0);
            dx = Math.Max(dx, p.X - rect.Right);

            var dy = Math.Max(rect.Top - p.Y, 0);
            dy = Math.Max(dy, p.Y - rect.Bottom);
            return Math.Sqrt(dx * dx + dy * dy);
        }
    }
}

Form1.cs

using System.Drawing;
using System.Linq;
using System.Windows.Forms;

namespace diff_images
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();

            var filename1 = @"Gelatin1.PNG";
            var filename2 = @"Gelatin2.PNG";

            var diff = new ImageDiffUtil(filename1, filename2);
            var diffRectangles = diff.GetDiffRectangles(8);

            var img3 = Image.FromFile(filename2);
            Pen redPen = new Pen(Color.Red, 1);
            var padding = 3;
            using (var graphics = Graphics.FromImage(img3))
            {
                diffRectangles
                    .ToList()
                    .ForEach(rect =>
                    {
                        var largerRect = new Rectangle(rect.X - padding, rect.Y - padding, rect.Width + padding * 2, rect.Height + padding * 2);
                        graphics.DrawRectangle(redPen, largerRect);
                    });
            }

            var pb1 = new PictureBox()
            {
                Image = Image.FromFile(filename1),
                Left = 8,
                Top = 8,
                SizeMode = PictureBoxSizeMode.AutoSize
            };

            var pb2 = new PictureBox()
            {
                Image = Image.FromFile(filename2),
                Left = pb1.Left + pb1.Width + 16,
                Top = 8,
                SizeMode = PictureBoxSizeMode.AutoSize
            };

            var pb3 = new PictureBox()
            {
                Image = img3,
                Left = pb2.Left + pb2.Width + 16,
                Top = 8,
                SizeMode = PictureBoxSizeMode.AutoSize
            };

            Controls.Add(pb1);
            Controls.Add(pb2);
            Controls.Add(pb3);
        }
    }
}

Наивным подходом было бы начинать с начала и работать построчно, колонка за колонкой. Сравните каждый пиксель, отметив самые верхние, самые левые, самые правые и самые нижние точки, из которых вы можете вычислить прямоугольник. Будут случаи, когда этот однопроходный подход будет более быстрым (то есть, когда будет очень маленькая отличающаяся область)

Обработка изображений, как это дорого, есть много бит, чтобы посмотреть. В реальных приложениях вам почти всегда нужно фильтровать изображение, чтобы избавиться от артефактов, вызванных несовершенным захватом изображения.

Распространенной библиотекой, используемой для этого вида разбивки битов, является OpenCV, для ускорения которой используются специальные инструкции процессора. Для него доступно несколько оболочек.NET, один из них - Emgu.

Идея:

Рассмотрим изображение как двухмерный массив, каждый элемент массива которого является пикселем изображения. Следовательно, я бы сказал, что дифференцирование изображений - это не что иное, как дифференцирование двухмерных массивов.

Идея состоит в том, чтобы просто просмотреть элементы массива по ширине и найти место, где есть разница в значениях пикселей. Если примерные [x, y] координаты обоих 2D-массивов отличаются, тогда начинается наша логика поиска прямоугольника. Позже прямоугольники будут использоваться для исправления последнего обновленного кадрового буфера.

Нам нужно сканировать границы прямоугольников на предмет различий, и если на границе прямоугольника будет обнаружено какое-либо различие, то граница будет увеличена по ширине или по высоте в зависимости от типа сделанного сканирования.

Считайте, что я сканировал по ширине 2D-массива и нашел место, где существует координата, которая отличается в обоих 2D-массивах. Я создам прямоугольник с начальной позицией как [x-1, y-1] и с шириной и высотой как 2 и 2 соответственно. Обратите внимание, что ширина и высота относится к числу пикселей.

Например: Rect Info: X = 20 Y = 35 W = 26 H = 23

То есть ширина прямоугольника начинается с координаты [20, 35] -> [20, 35 + 26 - 1]. Возможно, когда вы найдете код, вы сможете лучше понять его.

Также есть вероятность, что внутри меньшего прямоугольника, который вы нашли, есть меньшие прямоугольники, поэтому нам нужно удалить меньшие прямоугольники из нашей ссылки, потому что они ничего не значат для нас, за исключением того, что они занимают мое драгоценное пространство!!

Вышеприведенная логика будет полезна в случае реализации VNC-сервера, где могут потребоваться прямоугольники, обозначающие различия в изображении, которое в настоящее время делается. Эти прямоугольники могут быть отправлены в сети клиенту VNC, который может исправлять прямоугольники в локальной копии буфера кадров, которым он обладает, и отображать его на плате дисплея клиента VNC.

PS:

Я буду прикреплять код, в котором я реализовал свой собственный алгоритм. Я бы попросил зрителей прокомментировать любые ошибки или настройки производительности. Я также попросил бы зрителей прокомментировать любой лучший алгоритм, который сделал бы жизнь проще.

Код:

Класс Rect:

public class Rect {
    public int x; // Array Index
    public int y; // Array Index
    public int w; // Number of hops along the Horizontal
    public int h; // Number of hops along the Vertical

    @Override
    public boolean equals(Object obj) {
        Rect rect = (Rect) obj;
        if(rect.x == this.x && rect.y == this.y && rect.w == this.w && rect.h == this.h) {
            return true;
        }
        return false;
    }
}

Разница в классе изображения:

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.LinkedList;

import javax.imageio.ImageIO;

public class ImageDifference {
 long start = 0, end = 0;

 public LinkedList<Rect> differenceImage(int[][] baseFrame, int[][] screenShot, int xOffset, int yOffset, int width, int height) {
  // Code starts here
  int xRover = 0;
  int yRover = 0;
  int index = 0;
  int limit = 0;
  int rover = 0;

  boolean isRectChanged = false;
  boolean shouldSkip = false;

  LinkedList<Rect> rectangles = new LinkedList<Rect>();
  Rect rect = null;

  start = System.nanoTime();

  // xRover - Rovers over the height of 2D Array
  // yRover - Rovers over the width of 2D Array
  int verticalLimit = xOffset + height;
  int horizontalLimit = yOffset + width;

  for(xRover = xOffset; xRover < verticalLimit; xRover += 1) {
   for(yRover = yOffset; yRover < horizontalLimit; yRover += 1) {

    if(baseFrame[xRover][yRover] != screenShot[xRover][yRover]) {
     // Skip over the already processed Rectangles
     for(Rect itrRect : rectangles) {
      if(( (xRover < itrRect.x + itrRect.h) && (xRover >= itrRect.x) ) && ( (yRover < itrRect.y + itrRect.w) && (yRover >= itrRect.y) )) {
       shouldSkip = true;
       yRover = itrRect.y + itrRect.w - 1;
       break;
      } // End if(( (xRover < itrRect.x + itrRect.h) && (xRover >= itrRect.x) ) && ( (yRover < itrRect.y + itrRect.w) && (yRover >= itrRect.y) ))
     } // End for(Rect itrRect : rectangles)

     if(shouldSkip) {
      shouldSkip = false;
      // Need to come out of the if condition as below that is why "continue" has been provided
      // if(( (xRover <= (itrRect.x + itrRect.h)) && (xRover >= itrRect.x) ) && ( (yRover <= (itrRect.y + itrRect.w)) && (yRover >= itrRect.y) ))
      continue;
     } // End if(shouldSkip)

     rect = new Rect();

     rect.x = ((xRover - 1) < xOffset) ? xOffset : (xRover - 1);
     rect.y = ((yRover - 1) < yOffset) ? yOffset : (yRover - 1);
     rect.w = 2;
     rect.h = 2;

     /* Boolean variable used to re-scan the currently found rectangle
      for any change due to previous scanning of boundaries */
     isRectChanged = true;

     while(isRectChanged) {
      isRectChanged = false;
      index = 0;


      /*      I      */
      /* Scanning of left-side boundary of rectangle */
      index = rect.x;
      limit = rect.x + rect.h;
      while(index < limit && rect.y != yOffset) {
       if(baseFrame[index][rect.y] != screenShot[index][rect.y]) {        
        isRectChanged = true;
        rect.y = rect.y - 1;
        rect.w = rect.w + 1;
        index = rect.x;
        continue;
       } // End if(baseFrame[index][rect.y] != screenShot[index][rect.y])

       index = index + 1;;
      } // End while(index < limit && rect.y != yOffset)


      /*      II      */
      /* Scanning of bottom boundary of rectangle */
      index = rect.y;
      limit = rect.y + rect.w;
      while( (index < limit) && (rect.x + rect.h != verticalLimit) ) {
       rover = rect.x + rect.h - 1;
       if(baseFrame[rover][index] != screenShot[rover][index]) {
        isRectChanged = true;
        rect.h = rect.h + 1;        
        index = rect.y;
        continue;
       } // End if(baseFrame[rover][index] != screenShot[rover][index])

       index = index + 1;
      } // End while( (index < limit) && (rect.x + rect.h != verticalLimit) )


      /*      III      */
      /* Scanning of right-side boundary of rectangle */
      index = rect.x;
      limit = rect.x + rect.h;
      while( (index < limit) && (rect.y + rect.w != horizontalLimit) ) {
       rover = rect.y + rect.w - 1;
       if(baseFrame[index][rover] != screenShot[index][rover]) {
        isRectChanged = true;
        rect.w = rect.w + 1;
        index = rect.x;
        continue;
       } // End if(baseFrame[index][rover] != screenShot[index][rover])

       index = index + 1;
      } // End while( (index < limit) && (rect.y + rect.w != horizontalLimit) )

     } // while(isRectChanged)


     // Remove those rectangles that come inside "rect" rectangle.
     int idx = 0;
     while(idx < rectangles.size()) {
      Rect r = rectangles.get(idx);
      if( ( (rect.x <= r.x) && (rect.x + rect.h >= r.x + r.h) ) && ( (rect.y <= r.y) && (rect.y + rect.w >= r.y + r.w) ) ) {
       rectangles.remove(r);
      } else {
       idx += 1;
      }  // End if( ( (rect.x <= r.x) && (rect.x + rect.h >= r.x + r.h) ) && ( (rect.y <= r.y) && (rect.y + rect.w >= r.y + r.w) ) ) 
     } // End while(idx < rectangles.size())

     // Giving a head start to the yRover when a rectangle is found
     rectangles.addFirst(rect);

     yRover = rect.y + rect.w - 1;
     rect = null;

    } // End if(baseFrame[xRover][yRover] != screenShot[xRover][yRover])
   } // End for(yRover = yOffset; yRover < horizontalLimit; yRover += 1)
  } // End for(xRover = xOffset; xRover < verticalLimit; xRover += 1)

  end = System.nanoTime();    
  return rectangles;
 }

 public static void main(String[] args) throws IOException { 
  LinkedList<Rect> rectangles = null;

  // Buffering the Base image and Screen Shot Image
  BufferedImage screenShotImg = ImageIO.read(new File("screenShotImg.png"));
  BufferedImage baseImg   = ImageIO.read(new File("baseImg.png"));

  int width  = baseImg.getWidth();
  int height = baseImg.getHeight();
  int xOffset = 0;
  int yOffset = 0;
  int length = baseImg.getWidth() * baseImg.getHeight();

  // Creating 2 Two Dimensional Arrays for Image Processing
  int[][] baseFrame = new int[height][width];
  int[][] screenShot = new int[height][width];

  // Creating 2 Single Dimensional Arrays to retrieve the Pixel Values  
  int[] baseImgPix   = new int[length];
  int[] screenShotImgPix  = new int[length];

  // Reading the Pixels from the Buffered Image
  baseImg.getRGB(0, 0, baseImg.getWidth(), baseImg.getHeight(), baseImgPix, 0, baseImg.getWidth());
  screenShotImg.getRGB(0, 0, screenShotImg.getWidth(), screenShotImg.getHeight(), screenShotImgPix, 0, screenShotImg.getWidth());

  // Transporting the Single Dimensional Arrays to Two Dimensional Array
  long start = System.nanoTime();

  for(int row = 0; row < height; row++) {
   System.arraycopy(baseImgPix, (row * width), baseFrame[row], 0, width);
   System.arraycopy(screenShotImgPix, (row * width), screenShot[row], 0, width);
  }

  long end = System.nanoTime();
  System.out.println("Array Copy : " + ((double)(end - start) / 1000000));

  // Finding Differences between the Base Image and ScreenShot Image
  ImageDifference imDiff = new ImageDifference();
  rectangles = imDiff.differenceImage(baseFrame, screenShot, xOffset, yOffset, width, height);

  // Displaying the rectangles found
  int index = 0;
  for(Rect rect : rectangles) {
   System.out.println("\nRect info : " + (++index));
   System.out.println("X : " + rect.x);
   System.out.println("Y : " + rect.y);
   System.out.println("W : " + rect.w);
   System.out.println("H : " + rect.h);

   // Creating Bounding Box
   for(int i = rect.y; i < rect.y + rect.w; i++) {    
    screenShotImgPix[ ( rect.x               * width) + i ] = 0xFFFF0000;
    screenShotImgPix[ ((rect.x + rect.h - 1) * width) + i ] = 0xFFFF0000;
   }

   for(int j = rect.x; j < rect.x + rect.h; j++) {
    screenShotImgPix[ (j * width) + rect.y                ] = 0xFFFF0000;
    screenShotImgPix[ (j * width) + (rect.y + rect.w - 1) ] = 0xFFFF0000;
   }

  }

  // Creating the Resultant Image
  screenShotImg.setRGB(0, 0, width, height, screenShotImgPix, 0, width);
  ImageIO.write(screenShotImg, "PNG", new File("result.png"));

  double d = ((double)(imDiff.end - imDiff.start) / 1000000);
  System.out.println("\nTotal Time : " + d + " ms" + "  Array Copy : " + ((double)(end - start) / 1000000) + " ms");

 }
}

Описание:

Там будет функция с именем

public LinkedList<Rect> differenceImage(int[][] baseFrame, int[][] screenShot, int width, int height)

который выполняет работу по поиску различий в изображениях и возвращает связанный список объектов. Объекты - это не что иное, как прямоугольники.

Существует основная функция, которая выполняет работу по тестированию алгоритма.

В основной функции передано 2 примера изображений, которые представляют собой не что иное, как "baseFrame" и "screenShot", тем самым создавая результирующее изображение с именем "result".

У меня нет желаемой репутации, чтобы опубликовать получившееся изображение, которое было бы очень интересно.

Есть блог, который бы обеспечил вывод разницы в изображениях

Я не думаю, что может быть что-то лучше, чем исчерпывающий поиск с каждой стороны по очереди первой точки различия в этом направлении. Если, конечно, вы не знаете факт, который каким-то образом ограничивает множество точек различия.

Так что вот простой способ, если вы знаете, как использовать Lockbit:)

        Bitmap originalBMP = new Bitmap(pictureBox1.ImageLocation);
        Bitmap changedBMP = new Bitmap(pictureBox2.ImageLocation);

        int width = Math.Min(originalBMP.Width, changedBMP.Width),
            height = Math.Min(originalBMP.Height, changedBMP.Height),

            xMin = int.MaxValue,
            xMax = int.MinValue,

            yMin = int.MaxValue,
            yMax = int.MinValue;

        var originalLock = originalBMP.LockBits(new Rectangle(0, 0, width, height), ImageLockMode.ReadWrite, originalBMP.PixelFormat);
        var changedLock = changedBMP.LockBits(new Rectangle(0, 0, width, height), ImageLockMode.ReadWrite, changedBMP.PixelFormat);

        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                //generate the address of the colour pixel
                int pixelIdxOrg = y * originalLock.Stride + (x * 4);
                int pixelIdxCh = y * changedLock.Stride + (x * 4);


                if (( Marshal.ReadByte(originalLock.Scan0, pixelIdxOrg + 2)!= Marshal.ReadByte(changedLock.Scan0, pixelIdxCh + 2))
                    || (Marshal.ReadByte(originalLock.Scan0, pixelIdxOrg + 1) != Marshal.ReadByte(changedLock.Scan0, pixelIdxCh + 1))
                    || (Marshal.ReadByte(originalLock.Scan0, pixelIdxOrg) != Marshal.ReadByte(changedLock.Scan0, pixelIdxCh))
                    )
                {
                    xMin = Math.Min(xMin, x);
                    xMax = Math.Max(xMax, x);

                    yMin = Math.Min(yMin, y);
                    yMax = Math.Max(yMax, y);
                }
            }
        }

        originalBMP.UnlockBits(originalLock);
        changedBMP.UnlockBits(changedLock);

        var result = changedBMP.Clone(new Rectangle(xMin, yMin, xMax - xMin, yMax - yMin), changedBMP.PixelFormat);

        pictureBox3.Image = result;

отрицаем, похоже, что ваши 2 изображения содержат больше различий, чем мы видим невооруженным глазом, поэтому результат будет шире, чем вы ожидаете, но вы можете добавить допуск, чтобы он подходил, даже если остальные не идентичны на 100%

ускорить процесс вы, возможно, сможете нам Parallel.For, но сделайте это только для внешнего цикла

Другие вопросы по тегам