@cley_faye/shash-2d

Perceptual hash function to find similar-looking images. The idea is basically the stuff described at https://www.npmjs.com/package/@stabilityprotocol.com/phash . I just wanted to play a bit with it and see if some amount of pre-processing would help.

Main difference is pre-processing, and trying to accomodate heavily distorted source image. And slightly higher resolution, because why not.

Basic idea

1. Convert image to 8 bit greyscale

2. Determine the scale-down dimension

   • The main target is 128x128
   • If the input image ratio is extremely distorted (>4 or <0.25) divide the largest dimension by 2 and keep that ratio of full squares.

3. Scale down to the computed dimension from the previous step using bilinear interpolation.

4. Measure the average value for each quarters of the image

   • if the two right quarters are higher than the two left quarters, flip image horizontally (so that brightest is on the left)
   • if the two bottom quarters are higher than the two top quarters, flip image vertically (so that brightest in at the top)

5. For each input square (128x128):

   • Compute a 2D DCT (first DCT on each rows, then DCT on resulting columns)
   • Extract the most significant part of the computed DCT (8x8 top-left corner)

6. Compute Mean DCT (if more than one)

   • create a merged 8x8 DCT value where all output coefficient are the mean of all input DCT at that coefficient's position

7. Create the shash output:

   • Compute the median value of all coefficients in the final/single DCT grid, excluding the top-left most coefficient (it seems to represent an average value for the input, but have no relation to the actual signal variations)
   • create a bitfield by processing each rows, outputing 1 when over the threshold, 0 otherwise. The first bit is set to 1 if the original image was heavily skewed in the third step, 0 otherwise.

Initial scaling

The original idea strictly kept the same ratio for ALL images, shrinking them down to 64x64. While this does account for distortion of images in both axis, it would significantly lower the level of details for very large/small ratio on source images, which are a thing. Since we will then shrink the image down to a set of most important coefficients anyway, it might be a good idea to keep some level of details for the most skewed sources.

This is completely done on intuition of course; I'm not a signal processing expert. Not even a novice.

First hash bit

With the initial computation, we would take the top-left coefficient and output something depending on its relation to the computed median. According to my very cursory glance of the output of a DCT, keeping this information in the hash is not really useful, since we want to not distinguish too much between general brightness changes. So, I'll take this as an opportunity to have a bit indicate if the image have a large aspect ratio.

Hash size

A 8x8 coefficient list is 64 coefficients. Each coefficient is compared to the median of all coefficients, and one bit it output for each. We skip the first one, but replace it with a ratio-inbalance bit.

The output is still a 64 bits value.

Checking for similarities

Registering an image consists of running the algorithm described above, then storing the fingerprint somewhere.

Comparing two images for similarity would begin with computing the hash of the candidate image, then comparing the hamming distance between available hashes. Let's say that <15% difference (10 bits) is likely to be similar images. Less than 5% is very likely to be similar images.

A 64 bits hash is 8 bytes. To try to improve comparison speed, we could implement bit difference lookup tables working on bytes. An array of array of numbers could be used to very quickly retrieve the number of bit of difference between two bytes. And since we have a maximum threshold, we can bail out once that threshold is reached.

Lookup optimization

When storing the hash with each image, a pre-optimization could be to store the number of set bits alongside the hash. Any value with a difference larger than the threshold is obviously not a match.

Usage

CLI

Install globally (npm install -g @cley_faye/shash-2d), then run the following command to compute image hashes:

shash-compute <image>

You can run the script with --help to get more options.

Library

Install the library (npm install @cley_faye/shash-2d).

It basically provides two exports:

import {prepare, distance} from "@cley_faye/shash-2d";

const context = prepare();
const img1Hash = await context.fromPath("img1.jpg");
const img2Hash = await context.fromPath("img2.jpg");

console.log("Distance between img1 and img2:", distance(img1Hash, img2Hash));

The prepare() function can take arguments to customize the size and resolution of the shash. The context can compute image shash from local FS (NodeJs only), from Uint8Array instances, or from Blob/File. The distance() function accept a maximum distance parameters to quickly bailout if too much differences are detected.

Comparison

To improve performance on large dataset, the following lower level function to compare bit distance byte by byte are provided:

• bitDiff() compare two bytes and return the number of different bits between them
• byteRanges() return an object with all byte values closer than X bit difference for each byte value