如何找到两个图像之间的差异矩形

I have two images the same size. What is the best way to find the rectangle in which they differ. Obviously I could go through the image 4 times in different directions, but i'm wondering if there's an easier way.

我有两个同样大小的图像。找到它们不同的矩形的最好方法是什么?显然，我可以在不同的方向上对图像进行4次遍历，但是我想知道有没有更简单的方法。

Example:

例子:

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

第一个图像http://i44.tinypic.com/2cg0u2h.png

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

第二个图像http://i43.tinypic.com/14l0y13.png

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

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

6 个解决方案

#1

I don't think there is an easier way.

我认为没有更简单的方法。

In fact doing this will just be a (very) few lines of code, so unless you find a library that does that for you directly you won't find a shorter way.

实际上，这样做只需要(非常)几行代码，所以除非您找到一个直接为您实现这一点的库，否则您将找不到更短的方法。

#2

A naive approach would be to start at the origin, and work line by line, column by column. Compare each pixel, keeping note of the topmost, leftmost, rightmost, and bottommost, from which you can calculate your rectangle. There will be cases where this single pass approach would be faster (i.e. where there is a very small differing area)

一种幼稚的方法是从原点开始，逐行逐列地工作。比较每个像素，记录最上面、最左边、最右边和最下面的像素，从中您可以计算矩形。在某些情况下，这种单通道方法会更快(例如，有一个非常小的不同区域)

#3

Image processing like this is expensive, there are a lot of bits to look at. In real applications, you almost always need to filter the image to get rid of artifacts induced by imperfect image captures.

像这样的图像处理是昂贵的，有很多位要看。在实际应用程序中，您几乎总是需要对图像进行过滤，以消除不完整的图像捕获所引起的伪影。

A common library used for this kind of bit whacking is OpenCV, it takes advantage of dedicated CPU instructions available to make this fast. There are several .NET wrappers available for it, Emgu is one of them.

OpenCV是一种普通的用于这种比特攻击的库，它利用了可用的CPU指令来实现这种快速攻击。有几个。net包装器可用，Emgu就是其中之一。

#4

I don't think there can be anything better than exhaustively searching from each side in turn for the first point of difference in that direction. Unless, that is, you know a fact that in some way constrains the set of points of difference.

我认为没有什么比从每一方依次寻找那个方向的第一个不同点更好的了。除非，你知道一个事实在某种程度上限制了不同点的集合。

#5

So here comes the easy way if you know how to use Lockbit :)

所以，如果你知道如何使用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;

disclaim it looks like your 2 pictures contains more differences than we can see with the naked eye so the result will be wider than you expect but you can add a tolerance so it wil fit even if the rest isn't 100% identical

否认你的两张照片看起来比我们用肉眼看到的有更多的差异，所以结果会比你预期的要宽，但是你可以增加一个容忍度，这样即使其他的不是100%相同的也可以

to speed things up you will maybe able to us Parallel.For but do it only for the outer loop

为了加快速度，你也许可以让我们平行。但只适用于外部循环。

#6

Idea:

的想法:

Consider an image as a 2D Array with each Array element as a pixel of the image. Hence, I would say Image Differencing is nothing but 2D Array Differencing.

将一个图像作为一个二维数组，每个数组元素作为图像的一个像素。因此，我认为图像差分就是二维数组差分。

Idea is to just scan through the array elements width-wise and find the place where there is a difference in pixel values. If example [x, y] co-ordinates of both 2D Array are different then our rectangle finding logic starts. Later on the rectangles would be used to patch the last updated Frame Buffer.

想法是通过数组元素横向扫描，找到像素值不同的地方。如果两个二维数组的坐标都不同，那么我们的矩形查找逻辑就开始了。稍后，这些矩形将被用来修补最近更新的帧缓冲区。

We need to scan through the boundaries of the rectangles for differences and if any difference is found in the boundary of rectangle, then the boundary will be increased width-wise or height-wise depending upon the type of scan made.

我们需要在矩形的边界上进行扫描，如果在矩形的边界上发现了差异，那么根据所做的扫描的类型，边界将会增加宽度或高度。

Consider I scanned width-wise of 2D Array and I found a location where there exist a co-ordinate which is different in both the 2D Arrays, I will create a rectangle with the starting position as [x-1, y-1] and with the width and height as 2 and 2 respectively. Please note that width and height refers to the number of pixels.

考虑到我扫描了二维数组的宽度，我找到了一个位置，在二维数组中存在一个不同的坐标，我将创建一个矩形，起始位置为[x-1, y-1]，宽度和高度分别为2和2。请注意宽度和高度是指像素的数量。

eg: Rect Info: X = 20 Y = 35 W = 26 H = 23

Rect Info: X = 20 Y = 35 W = 26 H = 23。

i.e width of the rectangle starts from co-ordinate [20, 35] -> [20, 35 + 26 - 1]. Maybe when you find the code you may be able to understand it better.

我。矩形的e宽度开始于坐标[20,35]->[20,35 + 26 - 1]。也许当你找到代码的时候，你能更好地理解它。

Also there are possibilities that there are smaller rectangles inside a bigger rectangle you have found, thus we need to remove the smaller rectangles from our reference because they mean nothing to us except that they occupu my precious space !!

还有一种可能性是，在一个较大的矩形中有更小的矩形，因此我们需要从我们的引用中删除较小的矩形，因为它们对我们来说毫无意义，除了占据我宝贵的空间!!

The above logic would be helpful in the case of VNC Server Implementation where there would be a need of rectangles that denotes differences in the image that is currently taken. Those rectangles could be sent in the network to the VNC Client which can patch the rectangles in the local copy of Frame Buffer it possesses thereby displaying it on the VNC Client Display Board.

在VNC服务器实现的情况下，上面的逻辑将很有帮助，因为需要使用矩形来表示当前所使用的图像的不同。这些矩形可以在网络中发送到VNC客户端，VNC客户端可以对它所拥有的框架缓冲区的本地副本中的矩形进行补丁，从而将其显示在VNC客户端显示板上。

P.S.:

注:

I will be attaching the code in which I implemented my own algorithm. I would request viewers to comment for any mistakes or performance tuning. I would also request viewers to comment about any better algorithm that would make life simpler.

我将附加我实现自己算法的代码。如果有任何错误或性能调优，请查看器进行评论。我也会要求观众评论任何能让生活更简单的更好的算法。

Code:

代码:

Class 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;
    }
}

Class Image Difference:

类图像的区别:

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");

 }
}

Description:

描述:

There would be a function named

会有一个函数命名

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

which does the job of finding differences in the images and return a linkedlist of objects. The objects are nothing but the rectangles.

它可以找到图像中的差异并返回一个对象链表。对象只是矩形。

There is main function which does the job of testing the algorithm.

有一个主要的函数来测试算法。

There are 2 sample images passed into the code in main function, they are nothing but the "baseFrame" and "screenShot" thereby creating the resultant image named "result".

在main函数中，有2个示例图像被传递到代码中，它们只是“baseFrame”和“screenShot”，从而创建名为“result”的合成图像。

I don't possess the desired reputation to post the resultant image which would be very interesting.

我并没有想要的名声去发布合成图像，这将是非常有趣的。

There is a blog which would provide the output Image Difference

有一个博客可以提供输出图像的差异