Too many collisions?

[doughboyks]

Maybe I am doing it wrong but I ran through about 1,250 images (out of more than 350,000) and hashed (Perceptual) them. I then stored the hash in the database and I am using the SQL Bit_COUNT to get the hamming distance.

I took a random hash and ran the query and ended up with 2 at a distance of 0 (different hashes) and maybe 50 or more at a distance of 1. The farthest away is a distance of 27.

These are the two images that had different hashes but yet were still 0 away.

Hash: 12d2552c66ddc94b (image: https://10deb7fbfece20ff53da-95da5b03499e7e5b086c55c243f676a1.ssl.cf1.rackcdn.com/a1afc58c6ca9540d057299ec3016d726_l.jpg)

Hash: 12e627593dbc2307 (image: https://10deb7fbfece20ff53da-95da5b03499e7e5b086c55c243f676a1.ssl.cf1.rackcdn.com/3b8a614226a953a8cd9526fca6fe9ba5_l.jpg)

As you can see these are not anywhere close to the same.

SELECT c.*, BIT_COUNT('12e627593dbc2307' ^ i.hash) as hamming_distance
FROM images i
where hash is not null
ORDER BY hamming_distance ASC

Will this not work on "created" images? Maybe the sample size is too small for an accurate comparison. I think I am reading it is converted to an 8x8 image...maybe in my case it should be MUCH larger but I am not sure where to start.

[jenssegers]

That's weird. Can you make sure you are comparing integers, and not strings?

[doughboyks]

I am not following. I have both of those hashes stored in the database just like that. I could not find out how to get and store the 01010101011 representation.

So the query actually would look like

SELECT c.*, BIT_COUNT('12e627593dbc2307' ^ '12d2552c66ddc94b') as hamming_distance
FROM images i
where hash is not null
ORDER BY hamming_distance ASC

[doughboyks]

Following up on this. What am I doing wrong or does it not work for what I want it to?

[doughboyks]

Any help on this would be greatly appreciated. Either I am not following how to get the binary value of the hash or what I am doing is correct and it has limitations.

[Opekunov]

Sorry for my Eng.
First -
_MySQL BIT_COUNT() syntax:
BIT_COUNT(N)
Where N is an integer. (Not string)
Not sure, but it seems to me that the 01010101011 is also not a string

Why you can't loaded all md5 hashes from DB to script, and use
$yourVar->distance($hash1,$hash2)?
My test function (return 10 closest hashes) with 50000 hashes - result 0.8 sec (load from db -> foreach -> asort -> array_spice)

with your test pics:
$yourVar->distance('12d2552c66ddc94b','12e627593dbc2307') //return 28

[doughboyks]

Because by the time I get done hashing all of the images there will be 7 times as many as yours. All things being equal that would be more than 5 seconds.

So I need the MySQL query to work, I am just seeing no documentation on how to store and ultimately compare the binary version of a hash. For instance is there a "$hash->get_binary"? I could then store that and pass it into the query.

[doughboyks]

Let me ask this. Is the 0101011100 just an example and not the actual format? Following through the code for distance and when I call it passing the hash I get:

hash: 7e426e403d1e71f | hexdec: 568622213714011935

Should I be storing and using this hexdec value (even though it isn't 0's and 1's)?

[Opekunov]

Ok, try with hexdec
$hash1 = hexdec ("12e627593dbc2307"); $hash2 = hexdec ("12d2552c66ddc94b");
SELECT *, BIT_COUNT(1361819201567466247 ^ hashBig) as hd from photoHash ORDER BY hd ASC;
Result 28, like $->distance($hash1,$hash2);
screenshot

But maybe need test with more images
One more faster solution https://stackoverflow.com/questions/4777070/hamming-distance-on-binary-strings-in-sql/4783415

[Opekunov]

ALTER TABLE photoHash ADD hashBit BIT(YOURCOUNT)

for storing 01010101011 representation, but this not INT for BIT_COUNT

[doughboyks]

From the readme it has:

Image 1 hash: 3c3e0e1a3a1e1e1e (0011110000111110000011100001101000111010000111100001111000011110)
Image 2 hash: 3c3e0e3e3e1e1e1e (0011110000111110000011100011111000111110000111100001111000011110)

How do I generate the information in the parenthesis? I have the hash, just need to know how to get it as all 0's and 1's.

[jdreesen]

In PHP you could do decbin(hexdec($hash)) or base_convert($hash, 16, 2) to convert the hex value into a binary value.

[doughboyks]

Thanks jdreesen. So now I am attempting to store that data, but what format? The only thing that appears to keep it like this is varchar. But when I do the query like this:

SELECT i.*, BIT_COUNT(101001010110000000110011011011010010101111101100011010100001101 ^ i.hash) as hamming_distance
FROM images ci
where hash is not null
ORDER BY hamming_distance ASC

After processing only 10 images and grabbing one of the hashes all 10 are being returned as 1. Obviously I am not storing it correctly or I am not comparing correctly, or something. I apologize that I am having this much difficulty with this, but other than getting a hash none of this is really defined.

[doughboyks]

I think I have this figured out. I made the MySQL field BigINT Unsigned, I installed bcmath(so I don't get E+19 values) and I am storing and comparing against the hexdec value of the hash. I did a limited test and it got an exact match against one image (the others were in the 20's). I did another test where there were two similar images (one color and one black and white) and it matched perfect on the color and was like 10 on the B&W).

Looks like it will take 80+ hours before it will have hashed everything. I will do some more testing and see if it all is working and if so we can consider this "issue" closed (just might want to take the learnings and apply to the readme.

[Lucassifoni]

Hi @doughboyks, could you elaborate on your use of bcmath to solve this ? My hashes int representation get truncated to 9223372036854775807 aka PHP_INT_MAX when I try to store them.

I'm considering splitting the hash in two parts for now, like

8ececed9d8d8d0f4 => 8ececed9, d8d8d0f4
to decimal => 2395918041, 3638087924

And then querying potential duplicates this way, assuming hash_1 and hash_2 being BIGINT columns, and supplied parameters being [int image.hash_1, int image.hash_2, int treshold].
(note, MySQL dialect)

select ID, BIT_COUNT(hash_1 XOR ?) + BIT_COUNT(hash2 XOR ?) AS distance FROM pictures HAVING distance < ?

But this really feels dirty, I'd like to avoid this approach.
Still, it works for now as a POC for my project, and I'm getting the same distances with @jenssegers compare() function :

• phash is the whole hex string,
• hash_1 an int representation of the first 8 digits of this hex string,
• hash_2 an int representation of the last 8 digits of the hex string.

    /* Picture.php, Laravel5.5 Eloquent Model */

    /**
     * @param int $level
     * Returns potential duplicates of this picture.
     */
    public function findPotentialDuplicates(int $level = 5) {
        $hash_1 = $this->hash_1;
        $hash_2 = $this->hash_2;
        return DB::table('pictures')
            ->selectRaw('id, BIT_COUNT(hash_1 ^ ?) + BIT_COUNT(hash_2 ^ ?)  AS distance', [$h1, $h2])
            ->havingRaw('distance < ?', [$level])
            ->get();
    }

   /**
     * @param Picture $a
     * @param Picture $b
     * @return int
     */
    public static function compare(Picture $a, Picture $b) {
        $hasher = self::getHasher();
        return $hasher->distance($a->phash, $b->phash);
    }

But hey, it works for now, I'm getting similar and "opposite" images with similarity cursors, couldn't get fancier ! Thanks for documenting your issue, it allowed me to resolve this.

[scratcher28]

@Lucassifoni, any progress on this issue?