Efficient way to compare animated images to tell if they are the same

Question

I have a Student license for Mathematica, and felt like I wasn't making full use of the wonderful toolkit that it is; so I looked into things like its image processing capabilities. Now, I made and run a website called Sudomemo, which is essentially a place to post Flipnotes (Flipbook animations) made on the Nintendo DSi.

One of the features of Flipnote Studio (the DSi application which talks with Sudomemo) is the ability to spin-off - download, edit, and reupload - other's Flipnotes, provided that the uploader has not locked their Flipnote.

I've run into a people abusing the Spinoff function in order to essentially steal Flipnotes - reuploading them with no changes or just adding small things to make it slightly different. Sometimes the frame count between two is different, or the color palette has been edited - just enough to make it slightly different. I can trace a child flipnote back to its parent, however.

I've been trying to create a multi-pass process to compare Flipnotes.

One of the planned steps is hashing normalized copies of each frame into an array, then sorting the array and comparing it with the parent.

Advantages - normalizing solves the color palette swap issue;

Disadvantages - I need to be able to find the checksum of the image without any metadata. Also, a single small change will completely change the checksum.

I've been looking at using ImageKeypoints to find the shape of the image, and then compare with the other frames.

Advantages - Can find general shape and may be better and comparing, given that it determines a shape.

Disadvantages = small changes may add values, and I may end up with extra Keypoints; the number of frames in the animation may change and shift things over, and comparing every frame with each other will get harder exponentially (You can have up to 999 frames); and efficiency and speed become a concern.

Any suggestion? I need a numeric result (like a double, 0.00 for no similarity; and 1.00 for exactly the same.) The animations only have simple colors - red, blue, and either black or white, on either a black or white canvas. Please look to http://www.sudomemo.net for reference.

Answer 1

There are many different so called perceptual hash algorithms that can do the job, and fortunately at least some of them are easy to implement using Mathematica. This is my implementation of the algorithms described here.

generateHash[img_, method_: "Average"] /; (method == "Average" || method == "pHash") :=
  Module[
  {resized, grayscale, mean, imgdata, binarized},
  If[method == "pHash",
   resized = ImageResize[img, {32, 32}],
   resized = ImageResize[img, {8, 8}]
   ];
  grayscale = ColorConvert[resized, "Grayscale"];
  imgdata = ImageData[grayscale, "Byte"];
  If[method == "pHash",
   imgdata = FourierDCT[imgdata];
   mean = Mean@Rest@Flatten@imgdata[[;; 8, ;; 8]],
   mean = ImageMeasurements[grayscale, "Mean"]
   ];
  binarized = UnitStep[imgdata - mean];
  IntegerString[FromDigits[Flatten@binarized, 2], 16]
  ]
compare[img1_, img2_, method_: "Average"] /; (method == "Average" || method == "pHash") :=
  Module[
  {hash1, hash2},
  hash1 = generateHash[img1, method];
  hash2 = generateHash[img2, method];
  If[
   StringLength@hash1 == StringLength@hash2,
   HammingDistance[hash1, hash2],
   Infinity
   ]
  ]

compare returns a numeric result. You can test images as described in Daniel Lichtblau's answer, and perhaps even extend the algorithms with the method he proposes to take care of rotated images. You can make it so that if the value compare returns is smaller than a certain threshold, then that frame is marked as suspicious. Using some kind of scoring system you can then determine whether the animation is worth to examine more closely. I have not tried this extensively at all on your images so I can't say how well it works, but I tried it on one frame with some modifications done to it and that worked well:

The value returned by compare in the last example is 1, which is second highest grade of certainty. 0 is the highest grade of certainty that the images being compared are in fact the same. In the above code frames is a list of 448 images, and testing one image against all of these took 2.3 seconds.

This algorithm is very fast, but using compare to test a frame against all other frames in all other animations on your entire site will still take some time. Instead you should go through all of your existing animation and generate the hash for each of their frames, and then save the hashes to a database. When someone uploads a new animation you simply have to generate the hashes of a few frames and see if any of these hashes are similar to the ones already in your database. For example:

hashes = generateHash /@ frames;
sampleHash = generateHash[sample];
Select[hashes,
 If[
    StringLength@sampleHash == StringLength@#,
    HammingDistance[sampleHash, #],
    Infinity
    ] < 3 &]

finds all similar frames from a stored list of hashes using the threshold 3 and takes only 0.001117 seconds. If you store all of your hashes to a database, you might even be able to compare the hashes directly using SQL which should be lightning fast. Searching through your entire library of animations should no longer be a problem.

By the way, Sal Mangano offers a different solution based on eigenvectors (principal component analysis) in his book, Mathematica Cookbook.

Answer 2

It's a good question. I do not have a real answer but this is too long for a comment.

First, I'll assume that you want a probabilistic test to determine if a new submission is likely a slightly modified version of an older one. Let's say you are comparing just two. You probably don't need to test all frames of one against all frames of the other. I would suspect that comparing the first, middle, and last of one against all frames of the other would be more than sufficient. Could do this both ways just for extra assurance. Or throw in a few random comparisons as well. So the cost is O(k*(n+m)) where one has n frames, the other m, and the cost for a single comparison is k. (There is a bigger issue, though, which is that you have a growing collection to compare against. I'll say a bit about that later.)

So how to compare frames? I will assume they all have the same size. If not you will need to find a way to "normalize" to get equal dimensions. If there are color issues it might suffice to convert to gray scale. You then want a measure of discrepancy. An "obvious" one is to subtract one from the other and see if differences are small. This has a few of problems. One is that is much is white space, most differences will be zero without this meaning there is similarity. Another is that the relative darknesses might be different. A third is that one type of modification is to translate the main part of the picture (where the action is, so to speak). Worse I guess is that it could also be rotated. A fourth is that light/dark might get reversed.

For darkness issues, you might try either binarizing, or maybe averaging the nonwhite part and using that to normalize level of darkness for a given frame. To handle the possibility of color reversal you might first decide based on an overall value whether to first reverse via image negation.

For white space and translating/rotating, you might try the following. (1) Find the weighted "centroid" and subtract that from all image values. (2) Take the SingularValueDecomposition. (3) Use the principle axis information to determine rotation angle. Now rotate so that the new principal directions are vertical and horizontal. At this point you might have images that can be compared by subtraction or perhaps division (with special handling needed for those values that are zero, say the background). If doing division what you would be looking for is some level of constancy outside of the background parts.

One possible shortcut above is if the two pairs singular values are "very" different from one another, that might indicate that the images are different. Again though, since there are ways to fool with coloring and brightness, you might want to conside cases where their ratios are roughly constant as being similar even if the actual values are quite different e.g. {2,1} vs. {1,.5} or even {.98,.53} might be regarded as close enough to warrant the harder processing with rotations and all.

--- edit 2 ---

The paragraph above was partly blather. Here is how to salvage the idea. An m x m matrix will have m singular values, not 2. So the idea would be to throw away all but the largest few (five, say), and see if those have, approximately, a common ratio.

There might be a plausible way to extend this to the entire sequence defining the animation. You now have a rank 3 object rather than a matrix, but possibly flattening in one dimension would provide something workable. For this I'd suggest the flattening to be spacial, so each is m^2 x kj where images are m x n and the jth animation has kj images (obviously this does not require that image lengths = widths, that's just to simplify exposition). Now you have very large matrices, e.g. if m=256 then 65536 x 999, say. But you can still extract the several largest singular values. If these have an approximately common ration then the animations might be related, and if not then maybe they are unrelated. I should emphasize that this is speculative, and you'd need to expermient on some cases to decide if the idea actually works.

--- end edit 2 ---

As for the problem of a growing library, this is somewhat ameliorated by the fact that you only have to compare newcomers with existing ones. But as that latter set grows this of course could become tedious. I have to wonder if there might be a quick "these two are obviously different" test though that could speed things. Another thing to consider is the "sociology" of the site. It might become possible to have a whitelist of contributors known not to have abused by copying, and that would mean some percentage of incoming contributions would not require this testing.

I realize this is both somewhat complicated (especially if you are not familiar with SVD-type methods) and also devoid of actual code. Just thought it might provide a few ideas for getting started. I hope you find something workable.

--- edit ---

Here is something else you might consider. You could place a digital watermark in the contributions, a unique one for each. If done steganograpy-style, and sufficiently secure that it cannot readily be detected or erased, then this would give you a very quick test for copying: simply test new submissions for presence of one of the existing signatures.

--- end edit ---