7

TL;DR:what the title says

I am developing some sort of image board in PHP. I was thinking of changing each image's filename to it's checksum prior to saving it. This way, I might be able to prevent duplicates.
I know this wouldn't work for two images that are the same but differ in size or level of compression or whatnot, but this method would allow for an early check.
What bugs me is that I never saw this method implemented anywhere, so I was wondering if there is a catch to it. Maybe it is just more efficient to keep the original filename and store the hash in DB? Maybe the whole method is just not useful and my question is moot?
What do you think?

On a side note, I don't really get how hashes are calculated so I was wondering, if my first question checks out, if it would be possible to calculate the likeness that two images are similar by comparing hashes (levenshtein or something of the sort).

Improve this question

4 Answers 4

Reset to default
6

A hash seeded with something static (like a file name or the actual file) will tell you whether there's an exact match, but it won't help you with similarity, as hashes will diverge significantly even with minor changes. So you have two options:

1. Ignore the problem...

...and just ensure files don't collide with each other, even if they're duplicates (Fastest).

This is where hashes come in handy: seeding a hash with something relatively unique virtually ensures the ability to uniquely reference a file, even if its file name is the same or the image is similar. The value of this, especially in an image board, is for CDNs: most CDNs generally determine duplicates based off of file name (because it's fast). So if someone makes a modification to an image but uses the same file name, the CDN will ignore the new version.

So, if your file name is foo.jpg, you could create a hash using something like

list(basename, extension) = split(filename, '.')
hash = md5(filename . ':' . time())
filename = basename . '_' . hash . extension

And arrive at something like foo_a23aed3a298ae.jpg. Since the base name and the extension doesn't change, it'd be trivial to generate the original file name.

Plus, as the hash was seeded with the time, you should have a mostly unique hash, even when the two files are mostly the same.

2. Compute the image similarity criteria once...

...and store the results in the image's metadata or a separate database (Slower, but higher chance of saving storage).

This would go hand-in-hand with the first option.

Any good image library will provide a wealth of data about an image that you could use to create a comparison formula between two images. You'd then store those data either in the image itself (accessible via metadata like EXIF or IPTC) or in a database referenced by the image's unique hash.

Of course, in this scenario, you're doing searches throughout your database for matches. You might save some time by adding the important metadata to the file name:

foo_200x200_300dpi_cats_a23aed3a298ae.jpg

But depending on the amount of images you have to sort through, this can be really expensive, and would likely outweigh the cost of additional storage.

Improve this answer
6
  • 1
    Great answer (upvoted)! One small thing to note is that direct photo comparison could become quite computationally expensive depending on the language & library used and the dimensions of the photo uploaded by the user; image comparison, in my experience also has a large probability of false negatives caused by changes in color spacing, compression, size, and a variety of other factors.
    – dirk
    Commented Jun 25, 2011 at 2:51
  • 1
    @Dirk That's definitely something to watch out for; but depending on the image format and the type of information one's looking for, a lot of useful information can be accessed relatively easily through metadata formats like IPTC and EXIF. At worst, the data should only need to be computed once and then added to the image's metadata or the filename.
    – user8
    Commented Jun 25, 2011 at 3:25
  • Hadn't though of metadata, great idea!
    – dirk
    Commented Jun 26, 2011 at 2:13
  • I don't deny the usefulness or smartness of the answer, but it does not answer my point (unless I fail to see how, which is very possible - I am stupid sometimes). I am not wanting to generate a unique name; I am looking into the option of using the hash to check if an image already exists before saving it, and the drawbacks of it.
    – Xananax
    Commented Jun 26, 2011 at 20:23
  • @Xananax Ah, I was thinking about preventing duplication from a different angle. I've edited my question to hopefully address what you're asking for. In short, the amount of time you'd waste trying to compare images is likely more expensive than just storing everything.
    – user8
    Commented Jun 26, 2011 at 21:21
4

Git stores files (and other things as well) indexed by their SHA-1 hashes, which are quite a bit longer and more collision-proof than simple checksum. With a cryptographic hash, you should also be able to truncate the hash value, and what's left should still work as a hash of reduced bit length.

Improve this answer
2
  • A SHA-1 hash can be a checksum too. Your "simple checksum" possibly refers to MD5.
    – Lekensteyn
    Commented Jun 25, 2011 at 9:15
  • +1 As a general purpose content addressable file system, it has many applications beyond just version control.
    – Mark Booth
    Commented Jun 27, 2011 at 17:25
1

Important to know is that hashes and checksums are calculated in a way that small differences in input result in a completely unrelated hash. It has great value in evaluating exact duplicates, but it cannot be used to compute similarity. (For that, compression and explicit similarity algorithms are probably of more use, but I can't help you much with that.)

Other than that, using hashes as file names is definitely a possibility, and I have it seen implemented. The reason it is not seen more often is probably because many systems (especially web apps) resort to data storage through the database, which is also a very real possibility, especially if there is other information you need to store in a database anyway. (You can store the binary in a blob, and have other columns to indicate name and other properties.) Since databases have good unique key management, the hash is not needed for that (although it can still be used to find exact duplicates, just store the hash with the binary.)

If you are using the file system, there are two additional upsides to using hashes:

  1. it assures images that are not the same have different filenames (with the caveat of hash collisions of course), so you won't have image1.png's all over the place.
  2. it assures there is no chance of upsetting the filesystem with unusual chars or overflowing filename length or whatever
Improve this answer
0

For the sort of application you describe, it's worth it. But you want to present the files to users with the original name, not the checksum or hash of the file name, if you're going to present the file names to users.

Improve this answer
1
  • presenting the filenames should be completely separated from storing them, indeed. I was thinking of presenting all downloads through a script and generate a filename according to size/tags/other characteristics, close to what Mark Trapp was proposing, but on output, not input.
    – Xananax
    Commented Jun 26, 2011 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.