Detecting moved and dirty areas between two snapshots/images

I'm new to image processing and trying to figure out best way to identify 'moved' and 'dirty' rectangles between two desktop screenshots.Basically, lets say there is a round circle moving on a screen, there is a text that is changing e.g. millisecond counter, and there is a image that is being updated. All this is happening at 60fps. The algorithm should identify the moving circle as 'moved' region (and provide bounding rectangle of the moved object in source/initial and second/final image). Anything that changed in-place e.g. color/image change, text change etc should be identified as a 'dirty' region (with associated bounding rectangle). There could be a multiple of dirty & moved regions so the technique should be very fast on typical computer hardware (i5 processor) and be able to hit 60+ fps. I'm open to using GPU/iGPU for speeding up the process, but at this point not sure about the right image processing algorithm.

• Could you supply 2 sample images? – Royi Feb 9 at 10:06
• – tunafish24 Feb 9 at 10:26
• Grab 2 frames and give us example what you want to happen. – Royi Feb 9 at 10:51
• I've updated my question to provide details, basically I need this algorithm for a screen capture software to efficiently identify areas and its hard to explain it using an image example. – tunafish24 Feb 9 at 21:32
• joonyoung-cv.github.io/assets/paper/12_icip_real_time.pdf Here is a nice paper on motion detection. – starhd Feb 10 at 11:20

I love abstract art. It speaks to something inside of me that is outside the library, it speaks in words but not words. One of my favorite artists is Wassily Kandinsky.

An image of his that could meet the requirements of the problem, both with "text" and translation of a circle, is his "Circle within a circle". The bouncing globe animation is pristine, not textured, and doesn't have the text.

Also, the real world is messy and complex, so outside of explicitly specifying "this must work only on computer-generated content", any viable method has to hand a few real-world curve-balls.

Here is a copy of it:

So using MS Paint, I moved one of the circles and hashed up the lines in a way that should be consistent with local text changes.

Here it is:

So lets open up the files, convert to grayscale, and subtract them.

Here is some code:

import cv2
import numpy as np
from matplotlib import pyplot as plt
from PIL import Image

#name of input file
fname1 = './wassily-kandinsky(A).png'
fname2 = './wassily-kandinsky(B).png'

#read the files, convert to grayscale
img1 = Image.open(fname1).convert("L")
img2 = Image.open(fname2).convert("L")

#convert to numpy array for math
arr1 = np.asarray(img1)
arr2 = np.asarray(img2)

#smooth (to remove some of the manual-editing real-world images artifacts)
kernel_width = 11
arr1b = cv2.bilateralFilter(arr1, kernel_width,75,75)
arr2b = cv2.bilateralFilter(arr2, kernel_width,75,75)

#subtract images
arr_diff = np.abs(arr2b-arr1b)

#show them
plt.imshow(arr1, cmap='gray')
plt.savefig("figure1.png", dpi=300)
plt.show()

plt.imshow(arr2, cmap='gray')
plt.savefig("figure2.png", dpi=300)
plt.show()

plt.imshow(arr_diff, cmap='gray')
plt.savefig("figure_diff.png", dpi=300)
plt.show()


And this gives slightly different initial images, and allows a decent difference image.

New (smoothed, grayscale) "unchanged" image:

New (smoothed, grayscale) "changed" image:

The difference between the two:

Here is a zoom in of the "signal area":

Next steps (to do when I get time):

• clean up circle signal, show how edge histograms clearly give locations
• block location from difference image, show locations of "salt-and-pepper" which would come from alternate text in same location.

You are not giving a lot of details but here's a suggestion based on what you have provided:

• to detect the things that have changed you can subtract image A with image B and then you will have values different from zero only on the pixels whose value has changed.

• then, to detect circles you can apply the Hough transform (https://en.wikipedia.org/wiki/Circle_Hough_Transform). There are plenty of implementations of this algorithm and, as a first approach, you can check Matlab or Python for a quick test.

• the things that have changed and are not circles should be classified as text.

• Please see my updated question, hopefully, its more clear this time. – tunafish24 Feb 9 at 21:32

Ive been doing some research and it looks like the answer is Block Matching Algorithms: https://en.wikipedia.org/wiki/Block-matching_algorithm

These can be used to identify moved regions and the ones that aren't identified as moved can be marked as dirty.

• The drawback to this approach is in the article itself: "A full search of all potential blocks however is a computationally expensive task." Like I said in my answer, looking for movement is more expensive than looking for changes. – Cedron Dawg Feb 13 at 14:05

I did something similar many years ago. I pointed a webcam out my window and wrote a program that displayed the current image next to an image that was the difference of the current image and the previous image divided by two added to mid grey. If nothing moved, the image stayed grey. As soon as something moved is showed up distinctly on the grey image. This was on a 486 or early Pentium and I doubt it was over 15 fps.

Your situation is slightly different. Since you are talking about screen captures, the background that doesn't move should stay exactly the same, rather than just being close. This means you don't have to worry about the right threshold to indicate change.

I did another project where the camera found a pattern of dots that made a calibration plane, sort of like the chessboard calibration approach. When the dots were recognized, the webcam could be located to within a tenth of an inch in a 3D coordinate system defined by the sheet of paper the dots were on.

Finding something that moved is a lot more difficult than finding something that changed. I would concentrate on finding your dirty areas first, then trying to match the dirty areas with a before and after of your circle. Is is a solid colored ball or an actual circle?

You can speed up computation by skipping every other row and every other column. After all, you aren't looking for pixel sized regions. As you scan your rows, build a list of dirty intervals (row, start column, end column). You can then match intervals across rows keeping the mininum of start columns and maximum of end columns. When it doesn't overlap with the next row up and down, you have found your vertical range and the (start row, minimum start column, end row, maximum start columns) will form your bounding rectangle. In the text areas, you may need to do a little interval merging, or be a little loose in defining intervals.

A moving ball can be tricky. It can be a dirty ball where it was and a dirtly ball where it went. The bounding rectangle should be a square so it should be easy to find. However, if it moves just slightly you will have two dirty arc slivers. The good news is that the bounding rectangles should be similar in shape.