2

I am trying to compare a source image against thousands of images in a set to get a similarity score of the most likely matches (0 - 1). Each image is small (64x64 or smaller). Each image is 1 bit, meaning that each pixel is either off (fully transparent) or on (fully white). I am trying to create a very fast similarity algorithm to compare these images. I have found many similarity algorithms via Google search but they all involve comparing large, full color images, which I don't need to do.

I realize I can just compare pixels that match / don't match, but this can be potentially slow, given that the compare set can be very large. The compare set images will all be the same exact size as the lookup image.

Is it possible to create hashes or other fast lookups for these kinds of images where a hash or binary search lookup could be performed and similarity score created with the most likely matches?

jjxtra
  • 20,415
  • 16
  • 100
  • 140
  • Do you have to compare many images for unique ones or are you comparing just 2 images? – Haris Mar 21 '16 at 16:45
  • @Haris There will be many images in the compare set – jjxtra Mar 21 '16 at 16:46
  • Specify what "compare" means: checking if two images are exactly the same (so you get a boolean result), or checking how similar two images are (so you get an score). Also, if you are considering rotations. – ChronoTrigger Mar 21 '16 at 17:03
  • @ChronoTrigger Question updated, I am trying to calculate a similarity score – jjxtra Mar 21 '16 at 17:03
  • "thousands" of 32x32 images with 1-bit pixels really isn't much data. How "slow" is it to do a pixel-by-pixel calculation? And what level of performance do you need? Do you keep comparing the same set against new ones or is this a one-off, i.e. would pre-computing something help? – Ian Mercer Mar 21 '16 at 17:08
  • @IanMercer the closer to real-time performance, the better. Ideally, the lookup will take less than 50 milliseconds. – jjxtra Mar 21 '16 at 17:56
  • What is "similarity"? The top answer suggests Hamming distance, which is a good score for some things, but can be very bad if you want something that correlates with what humans consider similar: e.g. if you have two images with alternating black and white rows, in one of which the white rows are at even-numbered rows, and the other of which they are at odd-numbered rows, the Hamming distance will be maximum possible. – j_random_hacker Mar 22 '16 at 11:37
  • @j_random_hacker similarity will be the hamming distance – jjxtra Mar 22 '16 at 22:32

6 Answers6

4

To get a comparison score for binary images, I'd suggest you calculate the Hamming distance with xor operations and then count the number of ones. This can be sped up a lot using the fast popcount operation of SSSE3 instructions.

The Hamming distance tells you the number of bits that are different between two binary strings (so it's actually a dissimilarity value). To get a score in the range, say, [0, 1], you can divide by the size of the images (this way you get a score invariant to the image size).

With regard to the comparison with thousands of images, make sure it's a bottleneck, because if the data are not that large, it might be faster than you think. If you still need to make it faster, you can consider any or both these ideas:

1) Parallelization: the function is probably very easy to parallelize with OpenMP or tbb, for example. 2) A hash table: use the first (or some subset) bits of each image to index them in a vector. Then, compare those images that belong to the same hash bin only. Of course, this is an approximate approach and you will not get a comparison score for any pair of images, only for those that are similar enough.

Keep in mind that if you want to compare against all the images, you have to run the full comparison against all your database, so there are little chances other than parallelization to speed it up.

ChronoTrigger
  • 8,459
  • 1
  • 36
  • 57
  • This seems like the fastest way, but would still require iteration against the entire lookup set for every source image. I will try it though and see what the performance is. – jjxtra Mar 21 '16 at 18:03
  • I added a couple of ideas to make it faster. – ChronoTrigger Mar 22 '16 at 10:16
  • this seems to be working well enough. Combined with the optimizations from @m69 this is running much faster than I thought it would. I'm using this for real-time image matching in a game. The user draws a picture of an entity and the game creates what they drew. Sort of like Scribblenauts but with pictures instead of words :) – jjxtra Mar 22 '16 at 22:40
1

One way to do this would be a binary tree. Each image's pixel could be converted to a string of 1's and 0's. Then that string could be used to construct a binary tree.

While checking for a new string, you just start following where the path takes you, if you reach a leaf node, then it was present, if you don't then its new.

The image above shows a tree constructed using 3 strings of length 4

1010
0110
0001

So, if 0001 comes again, just follow the path, if you end up in a leaf (filled circle) then the string (image) is duplicate and has occurred again. If not, then you can add it also, while knowing it is new and unique.

It will take 0(n) time for each comparison and addition where n is the length of the string. In your case n == 32*32.

Haris
  • 12,120
  • 6
  • 43
  • 70
  • Thanks for the answer. I am hoping to compute similarity scores, meaning the near duplicate images should also be considered. Would this approach be able to handle that? – jjxtra Mar 21 '16 at 17:06
  • @jjxtra You can use a the length of the string which was correctly matching the path and then compute the percentage. That would work as a similarity score. – Haris Mar 21 '16 at 17:07
  • @Haris Unfortunately that would only do a comparison up to the point where the first pixel mismatched, which means two images that are identical except for the first pixel would be said to be less similar than two images where they are nothing alike except for the two first pixels, which isn't a very good comparison algorithm – Kevin Mar 21 '16 at 19:26
1

If your image stores pixel data in bitmap-like format, then every line is just 32-bit integer value, and you can simply compare image lines

for iy = 0 to ImageHeight - 1 do
  if   CastToInt32(Image1.Scanline[0]) <> CastToInt32(Image2.Scanline[0]) then 
     break due to inequality
//32 comparisons or less

For the case of approximate similarity you can calculate the overall number of discrepancies counting set bits in xor-ed values for all lines.

NumberOf1Bits(Value1 xor Value2)

P.S. Straightforward implementation in Delphi takes 300 nanoseconds per one image/image comparison (0.3 sec for 1 million images). Single thread, i5 processor, mismatching limit 450. Time will be significantly less for low mismatching limit (47 ns for limit 45). The main time eater - NumberOf1Bits/popcount function.

Community
  • 1
  • 1
MBo
  • 77,366
  • 5
  • 53
  • 86
  • This works for exact compare, but I need a similarity score, so near-exact images must also be calculated with some sort of threshold. Also I am hoping for a fast way to do this with a compare set of hundreds, maybe thousands of images. – jjxtra Mar 21 '16 at 17:03
  • @jjxtra Added xor-based approach – MBo Mar 21 '16 at 17:13
  • The xor-based approach is probably the best answer here as long as jjxtra doesn't want to compare images that could be translated or rotated – Kevin Mar 21 '16 at 19:28
  • @KevinWells That's right. I will be pre-processing the source image and lookup set to get them to be all the same size. – jjxtra Mar 21 '16 at 20:38
  • Feel free to implement my suggestions to reduce the number of image line comparisons, and check whether they provide any improvement :-) I fear the overhead of the additional code will prove too costly. – m69's been on strike for years Mar 22 '16 at 04:51
  • 1
    @m69 Yes, I used throwing images when number of mismatched bits exceeds the limit. The gain depends on limit value (upto 20 times) – MBo Mar 22 '16 at 05:00
1

You could implement a quadtree structure https://en.wikipedia.org/wiki/Quadtree

Segment your images recursively. At each level, store the number of 1 and/or 0 pixels (one can be computed from the other)

Ex : for this image :

0 1 1 0

0 1 0 1

0 0 0 0

0 0 1 0

You compute the following tree :

(5)

(2) - (2) - (0) - (1)

(0) - (1) - (0) - (1) - - - (1) - (0) - (0) - (1) - - - (0) - (0) - (0) - (0) - - - (0) - (0) - (1) - (0)

The higher levels of the tree are coarser versions of the image :

First level :

5/16

Second level :

2/4 2/4

0/4 1/4

Then, your similarity score could be computing whether the number of 0s and 1s is different, at different levels of recursion, with a weight at each level. And you could get an approximation of it (to quickly dismiss very different images) by not going down the whole tree.

A.N.
  • 320
  • 1
  • 8
1

If you find that comparing all images completely (using e.g. ChronoTrigger's answer) still takes too much time, consider these two strategies to reduce the number of necessary comparisons.

I will assume that the images are compared line-by-line. You start by comparing the first image completely, store its score as the maximum, then move on to the next, each time updating the maximum as necessary. While comparing each image line-by-line, you do the following after each line (or after each n lines):

  1. Check if the number of mismatched bits so far exceeds the number of mismatches in the image with the maximum score so far. If it does, this image can never reach the maximum score, and it can be discarded.
  2. If the average score per line so far is lower than the average score per line of the image with the maximum score, leave the comparison to be continued during the next run, and skip to the next image.

Repeat this until all images have been completely checked, or discarded.

Trying this strategy on 100 random 32x32-pixel images based on an example image, each with a random number of bits altered, gave this promising result:

FIRST RUN (100 images):
images checked completely:             5    (maximum score: 1015, image #52)
postponed after 1 line:               59
discarded after 1 line:               35
discarded after 10 lines:              1

SECOND RUN (59 images):
discarded without additional checks:  31    (because of new maximum score)
discarded after 1 additional line:    12
discarded after 2 additional lines:    9
discarded after 3 additional lines:    1
discarded after 4 additional lines:    3
discarded after 5 additional lines:    1
discarded after 6 additional lines:    2

Total number of lines compared:      326 out of 3200 lines (~ 10.1875 out of 100 images)
m69's been on strike for years
  • 11,835
  • 3
  • 34
  • 57
  • I will try this today. Looks promising. – jjxtra Mar 22 '16 at 17:36
  • @jjxtra The usefulness depends greatly on how close the best picture is to the original; if it has only a handful of incorrect pixels, other pictures can be quickly discarded. You can finetune the algorithm by always checking a minimum of 2, 4, ... lines in the first run, always checking lines in groups of 2, 4, 8, ... , postponing comparisons only if the score per line falls below 90%, 75%, ... of the score per line of the maximum, always checking the whole image once you're past a certain number of lines, stop postponing once you've found a very high maximum, ... – m69's been on strike for years Mar 22 '16 at 21:35
  • So far the performance for this method is very good. Discarding early without iterating all those extra lines is a big speed boost. – jjxtra Mar 22 '16 at 22:37
0

I made an image hashing class for the Skia4Delphi library unit tests. It generates a hash that makes it possible to compare the similarity percentage between 2 images using only the hash. The focus was on accuracy and not performance, but the performance is not bad. To use it, you must have Skia4Delphi installed. Check the source: https://github.com/skia4delphi/skia4delphi/blob/main/Tests/Source/Skia.Tests.Foundation.ImageHash.pas

vfbb
  • 611
  • 7
  • 15