How to find the rectangle of the difference between two images

Question

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

Example:

Answer 1

I do not think there is an easier way.

In fact, it will be just a (very) few lines of code, so if you do not find a library that does this for you directly, you will not find a shorter path.

Answer 2

The naive approach should be to start at the origin and work in turn, along the column. Compare each pixel, observing the top, left, right and bottom, from which you can calculate your rectangle. There will be cases when this one-pass approach will be faster (i.e., where there is a very small different area)

Answer 3

Image processing is expensive, there are many bits to look at. In real applications, you almost always have to filter the image to get rid of artifacts caused by imperfect image captures.

The common library used for this kind of beat is OpenCV, which takes advantage of the dedicated CPU instructions available for quick execution. Several .NET shells are available to him, Emgu is one of them .

Answer 4

I do not think that there can be anything better than an exhaustive search on each side, in turn, for the first point of difference in this direction. If, that is, you know a fact that somehow limits the set of difference points.

Answer 5

So here comes the easy way if you know how to use 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; 

Refuse, it looks like your 2 photos contain 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 to match even if the rest is not 100% identical

to speed things up, you might be able to Parallel.For us, but do it only for the outer loop

Answer 6

Idea:

Consider the image as a 2D array with each Array element as the image pixel. Therefore, I would say that Image Differencing is nothing more than a two-dimensional difference in an array.

The idea is to simply scan the elements of the array in width and find the place where there is a difference in pixel values. If the examples of [x, y] coordinates of both 2D arrays are different, then the rectangle search logic begins. Rectangles will later be used to fix the last updated frame buffer.

We need to scan the borders of the rectangles for differences, and if any difference is found on the border of the rectangle, then the border will be increased in width or height, depending on the type of scan.

Consider that I scanned the width of a 2D array, and I found a place where there is a coordinate that is different in both 2D arrays, I will create a rectangle with the original position as [x-1, y-1], and the width and height are 2 and 2 respectively. Please note that width and height are related to the number of pixels.

e.g. Rect Info: X = 20 Y = 35 W = 26 H = 23

ie the width of the rectangle begins with the coordinate [20, 35] → [20, 35 + 26 - 1]. Perhaps when you find the code, you can better understand it.

There is also the possibility that there are smaller rectangles in the large rectangle, so we need to remove the smaller rectangles from our link because they mean nothing to us, except that they occupy my precious space !!

The above logic would be useful in the case of a VNC server implementation, where there is a need for rectangles that indicate the differences in the image that is currently running. These rectangles can be sent on the network to the VNC client, which can correct the rectangles in the local copy of the frame buffer it possesses by displaying it on the VNC client card.

PS :.

I will attach the code in which I implemented my own algorithm. I would ask viewers to comment on any bugs or performance tuning. I would also ask viewers to comment on any best algorithm that makes life easier.

The code:

Rect Class:

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

Differences in class image:

 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 <= rx) && (rect.x + rect.h >= rx + rh) ) && ( (rect.y <= ry) && (rect.y + rect.w >= ry + rw) ) ) { rectangles.remove(r); } else { idx += 1; } // End if( ( (rect.x <= rx) && (rect.x + rect.h >= rx + rh) ) && ( (rect.y <= ry) && (rect.y + rect.w >= ry + rw) ) ) } // 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 will be a function named

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

which searches for differences in images and returns a linked list of objects. Objects are just rectangles.

There is a basic function that performs the task of testing an algorithm.

In the main function, two image samples are transferred, they are nothing more than "baseFrame" and "screenShot", thereby creating a resulting image called "result".

I do not have the desired reputation to publish the resulting image, which will be very interesting.

There is a blog that will provide image difference output