Marl

I have a website with about 15 000 images, and get about 20-30 new every day. However - duplicates are becomming a problem, and right now i'm looking for a method to find alert the user who are uploading that his/her image may already be in the database. First - i have a SHA-checksum on all the images, so it's not a problem to find a exact duplicate, but the problem arise when it has been scaled, saved an extra time (jpg) or someting like that. After searching for a solution i found out that ImageMagick has a "compare"-function, but running compare on 15000+ images every time a user is uploading a new image is not an option :/ Another method i was thinking about was taking 20-30 "testpixels" from each image, and save the color, and try to match them on every new image. However - this would only work if the images has the same size. The last solution I have been thinking about is calculating some sort of "average color" of a picture, but i fear that it wouldn't be very reliable and either return far to many, or only exact copies. How would you solve this problem? Isn't there some kind of standart solution?