Good way to identify similar images? [closed]

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 3 years ago.

Improve this question

I've developed a simple and fast algorithm in PHP to compare images for similarity.

Its fast (~40 per second for 800x600 images) to hash and a unoptimised search algorithm can go through 3,000 images in 22 mins comparing each one against the others (3/sec).

The basic overview is you get a image, rescale it to 8x8 and then convert those pixels for HSV. The Hue, Saturation and Value are then truncated to 4 bits and it becomes one big hex string.

Comparing images basically walks along two strings, and then adds the differences it f开发者_开发问答inds. If the total number is below 64 then its the same image. Different images are usually around 600 - 800. Below 20 and extremely similar.

Are there any improvements upon this model I can use? I havent looked at how relevant the different components (hue, saturation and value) are to the comparison. Hue is probably quite important but the others?

To speed up searches I could probably split the 4 bits from each part in half, and put the most significant bits first so if they fail the check then the lsb doesnt need to be checked at all. I dont know a efficient way to store bits like that yet still allow them to be searched and compared easily.

I've been using a dataset of 3,000 photos (mostly unique) and there havent been any false positives. Its completely immune to resizes and fairly resistant to brightness and contrast changes.

---

What you want to use is:

1. Feature extraction
2. Hashing
3. Locally aware bloom hashing.

---

1. Most people use SIFT features, although I've had better experiences with not scale-invariant ones. Basically you use an edge detector to find interesting points and then center your image patches around those points. That way you can also detect sub-images.

2. What you implemented is a hash method. There's tons to try from, but yours should work fine :)

3. The crucial step to making it fast is to hash your hashes. You convert your values into unary representation and then take a random subset of the bits as the new hash. Do that with 20-50 random samples and you get 20-50 hash tables. If any feature matches 2 or more out of those 50 hash tables, the feature will be very similar to one you already stored. This allows you to convert the abs(x-y)

Hope it helps, if you'd like to try out my self-developed image similarity search, drop me a mail at hajo at spratpix