Re: Comparing images

Replies are listed 'Best First'.
Re^2: Comparing images by pengvado (Acolyte) on Nov 27, 2006 at 17:12 UTC
That's true for any sort of compressed image. But if some of the files are raw bitmap, then filesize is just a function of resolution, and I don't think it's unlikely to find two files with a black or white pixel in the same place.	[reply]
Re^3: Comparing images by BrowserUk (Patriarch) on Nov 27, 2006 at 17:34 UTC
This is a statistical tactic so the file format is not a factor. Assuming binary files where all 256 values are possible. If you pick a random offset within two files being compared, and compare the byte values at that offset, then the odds that they will have the same value is: `256! / (256-2)! / 256^2 = 0.00390625 or 0.4%` [download] And if you pick two random offsets and compare the bytes drawn from both files at those offsets, then the odds against them both being the same (if the files are different) is the above value squared: `0.00390625^2 = 0.0000152587890625 or 0.0015%` [download] Now, seeking to a random offset is much more expensive than reading 2 bytes instead of one once you are there. So, what are the odds of a word (2 sequential bytes), read at the same (random) offset from two files being the same? `65536! / 65534! / 65536^2 = 0.0000152587890625 or 0.0015%` [download] Ie. The same as the two random offset case above. And by extension, selecting two words at 2 offsets gives us a probability of: `0.0000000002328 or 0.000000023%` [download] Again, if the 2 words are read as a single dword at a single offset, then the odds remain the same. In other words, the odds of two non-identical files containing the same 32-bit value at the same offset are statistically vanishingly small. So, when comparing files, if the sizes are the same, there is still no need to read the whole file and perform a checksum or hashing algorithm on them quite yet. By storing a random offset/32-bit value pairing, along with a file's size and checksum/hash, the occasions on which it will be necessary to actually compute the checksum/hash are reduced almost to nil. The choice of random offset deserves some thought. Many filetypes have headers which contain control information which is either static (as in the 'MZ' in the first two bytes of a dos/win executable; the 'GIF8' bytes in .gif files; the 'JFIF' at offset 6 of jpeg files; etc.). or frequently the same in files of the same type containing different data. For example, the 32-bit fields at offset 16 & 20 (width & height respectively) of a .png (and similar fields in other image formats) will contain the same values for images of the same width/height regardless of the content of the images. There are many other similarly non-diagnostic fields which should be avoided. A simple strategy for avoiding these (in most cases), is to use an offset derived from the filesize (which also reduces the volume of data that needs to be accumulated/stored). Eg. Reading the 32-bit value stored at the halfway point (suitably rounded down to the nearest 4-byte boundary) will avoid most headers in most file formats. Although this simple (and fast) tactic is not guaranteed to weed out duplicates, the final sanctions are still the calculation of a full checksum or hash from the entire file, or even a full byte-wise comparison, so the risk is negligible. But the tactic serves to eliminate those final, relatively expensive strategies in all but a minuscule number of cases. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l] [select]
Re^4: Comparing images by kaif (Friar) on Nov 28, 2006 at 01:00 UTC
Your use of statistics is somewhat misguided. The images that people look at are not remotely random, and one cannot assume that they are. pengvado is correct in saying that in raw bitmaps (particularly of few-colored things), there is a high probability of getting identical bytes. If you want to suggest "simple" methods to check if two files are identical before doing full MD5s, go ahead. (Filesize, first few bytes, random byte, and CRCs are all good suggestions.) Considering the OP hinted at a hashing method, please keep in mind the birthday paradox: remember that collisions among many objects are much likelier than those among just two. (Incidentally, your equations are missing a `1-` on the LHS and may be more simply written as `1/256` and `1/256^2`) To summarize: Equally sized and colored Canadian and Chinese flags would have about a 50% chance of differing at a random byte (they are mostly the same shade of red). Similarly with United States and Japanese flags (they share a lot of white). ++pengvado.	[reply] [d/l] [select]
Re^5: Comparing images by BrowserUk (Patriarch) on Nov 28, 2006 at 01:48 UTC
Re^6: Comparing images by kaif (Friar) on Nov 28, 2006 at 11:17 UTC
Some notes below your chosen depth have not been shown here
Re^2: Comparing images by brig (Scribe) on Nov 27, 2006 at 22:11 UTC
Read one pixel out of an arbitrarily large file? Nine Nines and two sevens? that's 33 out of a hundred billion!	[reply]
Re^3: Comparing images by BrowserUk (Patriarch) on Nov 27, 2006 at 23:16 UTC
Yup. Did you read this? Remember, if the two values are the same, you then go on and run a full md5, so there is no risk. But if they are different you saved yourself the bother/expense of doing it. And statistically, that should be the case in a very large percentage of cases. The reality of any given set of data probably won't reach that theoretical maximum. For a start, many if not most images don't use the alpha byte, so the range of values is reduced to `( ( 2*24 (224 - 2) ) / 248 ) == 0.999_999_887_92` [download] but that's still pretty good odds for the effort of reading 4 bytes and comparing two integers. Of course, if the two pictures being compared are A 640x480x24-bit color image of a black cat in a coal celler inside the Artic Circle in winter, with no flash. A 640x480x24-bit color image closeup of a black hole. Then this quick and simple test may not discriminate between them. But then, will the viewers? :) More seriously, it's possible that the camera that took the images has a bad cell in the CCD that means that one pixel in the same place on every image is always black (or white or red), and this test would fail to distinquish them if it happens to check that exact pixel. But if the dword compared is (semi-)randomly chosen, that would be pretty unlucky. Even if you mount the camera on a tripod and use a remote trigger to avoid micro-seismic disturbances, and take two frames one after the other, with 16 mlllion colors to choose from for each pixel, even the slightest variation in the light, or focus, or even the battery charge is likely to cause variations in the pixel colors at identical positions in identical shots by the same camera. In 8-bit color/grey scale images, the variation will be less, but then you are comparing 4 pixels not one. In a strictly B&W image, you would be comparing 32 adjacent pixels. But when the statistically improbable happens and you get a false positive, that false positive would be caught by the full md5 anyway. The point is to save time by avoiding that full md5 (or similar) where possible--not ditch it all together. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]