Perceptual hashing for images

A user uploads a photo. Another user uploads the same photo, resized, recompressed as a 70% JPEG, with a slight contrast tweak. To a human being they are the same image. To md5_file() they are two files with nothing in common.

A perceptual hash solves exactly this problem: it produces a fingerprint that describes how an image looks, not how it is encoded. In this article we will cover the theory and the three main families of algorithms, and we will implement aHash, dHash and pHash from scratch in PHP, using nothing but the GD extension.

The near-duplicate problem

Cryptographic hashes — MD5, SHA-1, SHA-256 — are designed around one specific property: the avalanche effect. Flipping a single bit of the input must flip, on average, half of the output bits. That is exactly what we want to verify a file's integrity or sign a token. It is exactly what we do not want when comparing images.

Saving the same JPEG twice is enough to get different bytes. Resizing an image from 4000 to 1200 pixels changes every single value. Stripping the EXIF metadata changes the hash without touching a single pixel.

original_photo.jpg  → sha1: 3f2a9c1e5b7d4e8a9c217d4e5f6a8b90c1d2e3f4
resized_photo.jpg   → sha1: a81c04d7e29b5f63c0d8e1a7b4f92c6d3e5a1b08
photo_no_exif.jpg   → sha1: 7e4b1a9d2c8f6e3a5b0d9c7e1f4a2b6c8d3e5f90

Three completely different hashes for three files containing the same photograph. If our goal is to find duplicates in a gallery, block re-uploads of content a moderator already removed, or group similar shots together, a cryptographic hash is useless.

We need a function with the opposite property: similar inputs must produce similar outputs.

What is a perceptual hash

A perceptual hash is a function that reduces an image to a sequence of bits, typically 64, so that two visually similar images produce nearly identical sequences.

The idea is to throw away everything the human eye ignores — resolution, color, compression noise, small details — and keep only the structure: where the bright areas are, where the dark ones are, how light changes from one point to the next. What remains is a sort of semantic thumbnail of the image.

All the algorithms we will look at follow the same three-step pattern:

1. Reduce. The image is drastically shrunk (8×8, 9×8 or 32×32 pixels) and converted to grayscale. Format, dimensions and almost all the noise are already gone at this point.
2. Extract. A feature is computed from the few remaining pixels: average brightness, gradients, frequencies.
3. Binarize. Each value is compared against a threshold and becomes 0 or 1. The resulting 64 bits are the hash.

Hamming distance

A cryptographic hash is compared with ===: it is either equal or different. A perceptual hash is compared with the Hamming distance, the number of bits that differ between two hashes.

hash A:   1100 1100 0100 1101 1111 0010 0011 0010
hash B:   1100 1100 0100 1001 1111 0010 0011 0110
                         ^                     ^
XOR:      0000 0000 0000 0100 0000 0000 0000 0100

Hamming distance = 2

The computation is trivial: XOR the two hashes bit by bit and count the ones. On 64 bits, a distance of 0 means practically identical images, while a distance around 32 means images with no relation at all (which is what you would expect from two random sequences: half the bits match by pure chance).

Three families

In 2011 Neal Krawetz published an article titled Looks Like It on his blog Hacker Factor, which popularized two very simple algorithms, followed two years later by a third. They are still the starting point for anyone approaching the subject.

aHash is the simplest: a bit is 1 if the pixel is brighter than the mean. It is extremely fast but fragile: a non-linear change in brightness or contrast is enough to shift the mean and flip many bits.

dHash does not look at absolute values but at differences: a bit is 1 if a pixel is brighter than its right-hand neighbor. It describes gradients, the direction in which light changes, and for this reason it holds up very well against exposure changes.

pHash is the most sophisticated: instead of pixels it analyzes the image's frequencies through the Discrete Cosine Transform, the same transform behind JPEG. It deserves a section of its own.

How pHash works

DCT-based pHash was analyzed in depth by Christoph Zauner in his 2010 thesis, Implementation and Benchmarking of Perceptual Image Hash Functions, and it is the foundation of the open source pHash library. The intuition is this: an image is not just a grid of pixels, it is also a sum of waves.

The frequencies of an image

Think of a single row of pixels. We can see it as a sequence of brightness values, or as the overlap of cosine waves of increasing frequency: a very slow wave describing the general trend (brighter on the left, darker on the right), then progressively faster waves adding detail, up to the very fast ones that encode sharp edges, texture and noise.

The Discrete Cosine Transform (DCT) performs exactly this decomposition: it takes N values and returns N coefficients, each telling us how much of a given frequency is present in the signal. For a sequence of N values, the k-th coefficient is:

$X_k = \alpha_k \sum_{i=0}^{N-1} x_i \cos\left[\frac{\pi (2i+1) k}{2N}\right]$

with $\alpha_0 = \sqrt{1/N}$ and $\alpha_k = \sqrt{2/N}$ for $k > 0$.

The coefficient X₀ is the constant component (the mean value, called DC). X₁ is the slowest wave, X₂ slightly faster, and so on. In two dimensions the same transform is applied first to every row and then to every column: the DCT is separable.

The result is a matrix where the top-left corner holds the low frequencies (the overall structure of the image) and the bottom-right corner holds the high frequencies (the fine details).

          horizontal frequencies →
        ┌──────────┬───────────────────────┐
   v    │ DC   low │                       │
   e    │ ▓▓▓▓▓▓▓▓ │                       │
   r    │ ▓ 8×8  ▓ │   mid frequencies     │
   t    │ ▓▓▓▓▓▓▓▓ │                       │
   .    ├──────────┘                       │
        │                                  │
   f    │                     high         │
   r    │                  frequencies     │
   e    │                  (details,       │
   q    │                    noise)        │
   ↓    └──────────────────────────────────┘
                      32 × 32

It is the same principle JPEG relies on: the human eye is not very sensitive to high frequencies, so the compressor quantizes them aggressively. pHash goes further: it throws them away entirely.

The algorithm

1. Resize to 32×32 in grayscale. Larger than aHash's 8×8, because the DCT needs a minimum amount of information to extract frequencies from.
2. Compute the 2D DCT of the 32×32 matrix, obtaining 1,024 coefficients.
3. Keep the top-left 8×8 block: the 64 lowest-frequency coefficients. Everything else — including JPEG compression noise — is discarded.
4. Compute the median of the 64 coefficients. We use the median rather than the mean because the DC coefficient is vastly larger than the others and would drag the mean upwards.
5. Binarize: every coefficient above the median becomes 1, the others 0.

Using the median has an elegant side effect: by definition half the bits will be 1 and half 0. The hash is always balanced, which makes the Hamming distance more informative.

The bit corresponding to DC, being the largest coefficient, will practically always be 1. Some implementations exclude it and settle for 63 useful bits; we will keep it, for simplicity and to stay aligned with what the most popular libraries do.

The PHP implementation

We collect everything in a PerceptualHash class with static methods and no external dependencies other than the GD extension, available in practically every PHP installation. The code requires PHP 8.0 or later, because GD returns GdImage objects instead of the old resources.

One design choice to clarify right away: we represent the hash as a 16-character hexadecimal string, not as an integer. PHP integers are 64-bit and signed: a hash with the most significant bit set would become negative, and some arithmetic operations would overflow, silently turning into a float. A hex string is portable, readable in logs, and stores without surprises in any database.

load() and grayscaleMatrix()

load() accepts any format supported by GD (JPEG, PNG, GIF, WebP) thanks to imagecreatefromstring(). grayscaleMatrix() is the reduce step shared by all three algorithms: it resizes with imagecopyresampled(), which unlike imagecopyresized() averages pixels instead of sampling them, and converts each pixel to luminance.

final class PerceptualHash
{
    /** Popcount for the 16 possible values of a nibble (0x0 - 0xF). */
    private const POPCOUNT4 = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];

    public static function load(string $path): GdImage
    {
        $image = imagecreatefromstring(file_get_contents($path));
        if ($image === false) {
            throw new RuntimeException("Unsupported format: $path");
        }
        return $image;
    }

    /**
     * Resizes the image to $w x $h and converts it into a luminance
     * matrix [row][column] with values 0-255.
     */
    public static function grayscaleMatrix(GdImage $src, int $w, int $h): array
    {
        $small = imagecreatetruecolor($w, $h);
        imagecopyresampled($small, $src, 0, 0, 0, 0, $w, $h, imagesx($src), imagesy($src));

        $matrix = [];
        for ($y = 0; $y < $h; $y++) {
            for ($x = 0; $x < $w; $x++) {
                $rgb = imagecolorat($small, $x, $y);
                $r = ($rgb >> 16) & 0xFF;
                $g = ($rgb >> 8) & 0xFF;
                $b = $rgb & 0xFF;
                // Luminance according to ITU-R BT.601
                $matrix[$y][$x] = 0.299 * $r + 0.587 * $g + 0.114 * $b;
            }
        }

        imagedestroy($small);
        return $matrix;
    }

The weights 0.299, 0.587 and 0.114 are not arbitrary: they reflect the human eye's different sensitivity to the three channels. We see green much better than blue, and a plain arithmetic mean would produce perceptually wrong grays.

aHash()

Reduce to 8×8, average, compare. With array_merge(...) and the spread operator we flatten the matrix into an array of 64 values.

    public static function aHash(GdImage $image): string
    {
        $pixels = array_merge(...self::grayscaleMatrix($image, 8, 8));
        $mean   = array_sum($pixels) / count($pixels);

        $bits = array_map(fn($p) => $p > $mean ? 1 : 0, $pixels);
        return self::bitsToHex($bits);
    }

dHash()

We reduce to 9 columns by 8 rows: 9 pixels per row give exactly 8 neighbor comparisons, and 8 rows × 8 comparisons make 64 bits.

    public static function dHash(GdImage $image): string
    {
        // 9 columns to get 8 comparisons per row
        $matrix = self::grayscaleMatrix($image, 9, 8);
        $bits   = [];

        for ($y = 0; $y < 8; $y++) {
            for ($x = 0; $x < 8; $x++) {
                $bits[] = $matrix[$y][$x] > $matrix[$y][$x + 1] ? 1 : 0;
            }
        }

        return self::bitsToHex($bits);
    }

pHash()

The five steps of the algorithm, one per logical line. The $size and $keep parameters let you experiment with different dimensions, but 32 and 8 are the standard values.

    public static function pHash(GdImage $image, int $size = 32, int $keep = 8): string
    {
        $matrix = self::grayscaleMatrix($image, $size, $size);
        $dct    = self::dct2d($matrix);

        // Only the top-left block: the low frequencies
        $low = [];
        for ($y = 0; $y < $keep; $y++) {
            for ($x = 0; $x < $keep; $x++) {
                $low[] = $dct[$y][$x];
            }
        }

        $median = self::median($low);
        $bits   = array_map(fn($c) => $c > $median ? 1 : 0, $low);

        return self::bitsToHex($bits);
    }

dct2d(), dct1d() and cosineTable()

The mathematical core. We exploit separability: instead of a direct 2D DCT, which on a 32×32 matrix would cost 32⁴ ≈ 1 million multiplications, we run 32 DCTs on the rows and 32 on the columns, for a total of 2 × 32³ ≈ 65,000 multiplications.

The cosines depend only on k, i and N, not on the image. We compute them once and keep them in a static cache: with a worker processing thousands of images, cos() is called 1,024 times in total.

    /** Two-dimensional DCT-II, separable: rows first, then columns. */
    private static function dct2d(array $matrix): array
    {
        $n   = count($matrix);
        $cos = self::cosineTable($n);

        $rows = array_map(fn($row) => self::dct1d($row, $cos), $matrix);

        $out = [];
        for ($x = 0; $x < $n; $x++) {
            $column = self::dct1d(array_column($rows, $x), $cos);
            foreach ($column as $y => $value) {
                $out[$y][$x] = $value;
            }
        }

        return $out;
    }

    private static function dct1d(array $v, array $cos): array
    {
        $n   = count($v);
        $out = [];

        for ($k = 0; $k < $n; $k++) {
            $sum = 0.0;
            for ($i = 0; $i < $n; $i++) {
                $sum += $v[$i] * $cos[$k][$i];
            }
            $scale   = $k === 0 ? sqrt(1 / $n) : sqrt(2 / $n);
            $out[$k] = $scale * $sum;
        }

        return $out;
    }

    private static function cosineTable(int $n): array
    {
        static $cache = [];

        if (!isset($cache[$n])) {
            for ($k = 0; $k < $n; $k++) {
                for ($i = 0; $i < $n; $i++) {
                    $cache[$n][$k][$i] = cos(M_PI * (2 * $i + 1) * $k / (2 * $n));
                }
            }
        }

        return $cache[$n];
    }

median() and bitsToHex()

Two utilities. bitsToHex() groups the 64 bits into blocks of 4 (a nibble) and converts each one into a hexadecimal digit.

    private static function median(array $values): float
    {
        sort($values);
        $count = count($values);
        $mid   = intdiv($count, 2);

        return $count % 2
            ? $values[$mid]
            : ($values[$mid - 1] + $values[$mid]) / 2;
    }

    /** 64 bits → 16 hexadecimal characters. */
    private static function bitsToHex(array $bits): string
    {
        $hex = '';
        foreach (array_chunk($bits, 4) as $nibble) {
            $hex .= dechex(bindec(implode('', $nibble)));
        }
        return $hex;
    }

distance()

PHP has no native popcount function (counting the bits set to 1) without the GMP extension. Working on hex strings the solution is simple: we XOR digit by digit and look the result up in a precomputed 16-element table.

    public static function distance(string $a, string $b): int
    {
        if (strlen($a) !== strlen($b)) {
            throw new InvalidArgumentException('Hashes must have the same length');
        }

        $distance = 0;
        for ($i = 0, $len = strlen($a); $i < $len; $i++) {
            $distance += self::POPCOUNT4[hexdec($a[$i]) ^ hexdec($b[$i])];
        }

        return $distance;
    }
}

A complete example

To put it to the test I generated a synthetic 1600×1200 image with GD (a gradient with twelve colored ellipses) and seven variants: resized, recompressed, retouched, watermarked, cropped, mirrored, plus a completely different image.

<?php

require 'PerceptualHash.php';

$original = PerceptualHash::load('original.png');
$ref = [
    'a' => PerceptualHash::aHash($original),
    'd' => PerceptualHash::dHash($original),
    'p' => PerceptualHash::pHash($original),
];

printf("original.png  aHash %s  dHash %s  pHash %s\n\n", $ref['a'], $ref['d'], $ref['p']);

$variants = [
    'resized.jpg', 'jpeg_q30.jpg', 'brightness.png', 'watermark.png',
    'cropped.png', 'mirrored.png', 'different.png',
];

foreach ($variants as $file) {
    $image = PerceptualHash::load($file);
    printf(
        "%-16s aHash %2d  dHash %2d  pHash %2d\n",
        $file,
        PerceptualHash::distance($ref['a'], PerceptualHash::aHash($image)),
        PerceptualHash::distance($ref['d'], PerceptualHash::dHash($image)),
        PerceptualHash::distance($ref['p'], PerceptualHash::pHash($image)),
    );
}

Output:

original.png  aHash f098b838118fc7ff  dHash 98cc8c9cdad0e0d8  pHash cc4df232c6c7c332

resized.jpg      aHash  0  dHash  0  pHash  0
jpeg_q30.jpg     aHash  0  dHash  1  pHash  0
brightness.png   aHash 16  dHash  0  pHash  4
watermark.png    aHash  1  dHash  0  pHash  4
cropped.png      aHash 13  dHash  9  pHash 14
mirrored.png     aHash 28  dHash 23  pHash 32
different.png    aHash 26  dHash 39  pHash 32

The numbers tell the strengths and weaknesses of each algorithm quite clearly.

Resizing and recompression — going from 1600×1200 to 400×300, or saving as a quality-30 JPEG — leave practically no trace: a distance of 0 or 1 for all three. This is the main use case, and it is solved.

Brightness and contrast put aHash in trouble: 16 bits out of 64 changed. Raising the brightness saturates the lightest areas at 255, the gray distribution gets distorted, and the mean no longer separates the same regions. dHash, which only looks at differences between neighbors, does not even notice: distance 0.

Cropping 10% from each side is already at the limit for all of them: the hash describes the global composition, and moving the edges moves the composition.

Mirroring is the structural limit: to a perceptual hash a mirrored image is a different image, with distances in the same range as a completely unrelated one (around 32). If you need to recognize them, compute the hash of the mirrored version with imageflip() as well and compare both.

In production

Computing a hash is the easy part. The real problem is another: given a new upload, how do we find every image within distance ≤ 10 in an archive of millions?

Storing the hash

In the PHP code we used hex strings for portability, but in the database a 64-bit integer is the better fit, because databases can do XOR and popcount natively. In MySQL and MariaDB the right column type is BIGINT UNSIGNED, and the conversion can be done directly in SQL with CONV():

ALTER TABLE images ADD COLUMN phash BIGINT UNSIGNED NULL;

UPDATE images SET phash = CONV('cc4df232c6c7c332', 16, 10) WHERE id = 42;

Searching for near-duplicates becomes a single query, thanks to BIT_COUNT():

SELECT id, BIT_COUNT(phash ^ CONV(:hash, 16, 10)) AS distance
FROM images
WHERE BIT_COUNT(phash ^ CONV(:hash, 16, 10)) <= 10
ORDER BY distance
LIMIT 20;

In PostgreSQL the natural type is bit(64), and bit_count() has been available since version 14. In a Laravel application, the computation belongs in a queued job dispatched at upload time, so the HTTP request does not pay the cost of resizing.

The full-scan problem

That query has a flaw: no B-tree index can help it. The condition on BIT_COUNT() forces the database to compute the XOR on every single row. Up to a few hundred thousand images this is perfectly acceptable, since these are very fast 64-bit operations. Beyond that, you need a dedicated data structure.

The most common solution relies on the pigeonhole principle. We split the 64 bits into 4 blocks of 16. If two hashes are at most 3 bits apart, at least one of the 4 blocks must be identical, because 3 differences are not enough to dirty all of them. We store the 4 blocks in 4 indexed columns, look for candidates with a WHERE b1 = ? OR b2 = ? OR b3 = ? OR b4 = ? that uses the indexes, and compute the exact distance only on those. For higher thresholds you use more, smaller blocks, or structures like BK-trees, trees designed specifically for searching metric spaces such as the one defined by Hamming distance.

Choosing the threshold

There is no universal value. As a rule of thumb, with a 64-bit pHash:

The threshold must be calibrated on your own data. On a product photo platform, where many images share the same white background and composition, a threshold of 10 will generate false positives. On an archive of heterogeneous photographs, the same threshold will be overly cautious. The right method is to collect a few hundred hand-labeled pairs and look at where the distributions separate.

Performance

In my test, computing a pHash on a 1600×1200 image takes about 30 milliseconds, in line with dHash and aHash. This is no coincidence: the time is dominated by imagecopyresampled(), which has to read almost two million pixels. The DCT on 32×32 is negligible by comparison.

For very large images it is therefore worth leaving the heavy lifting to GD, or better to Imagick: if the application already generates thumbnails, computing the hash on the thumbnail instead of the original does not change the result and cuts the time dramatically.

The limits

A perceptual hash is a statistical tool, not proof. We have seen that it is blind to rotations and mirroring and fragile against heavy cropping. Above all, it is not designed to withstand an adversary: in 2021, a few weeks after Apple announced NeuralHash, researchers generated completely different images with the same hash. For content moderation the industry uses more robust algorithms, such as Microsoft's PhotoDNA or PDQ, released as open source by Meta in 2019, but the underlying principle is the same one we implemented here.

Conclusion

Perceptual hashing turns the logic of cryptographic hashing upside down: instead of amplifying every tiny difference, it absorbs it. The trick is not a particularly sophisticated formula, but a choice of what to ignore: resolution, color, noise, high frequencies. What remains, 64 bits in total, is surprisingly enough to recognize one image among millions.

In under 200 lines of PHP, with no external libraries, we have three working algorithms and a distance measure. dHash, thanks to its resistance to brightness changes and its simplicity, is often the best place to start. pHash is the most balanced choice when recognition quality matters more than a few milliseconds.

The fascinating thing is that the DCT we used is the same one JPEG has relied on for thirty years to decide what to throw away. The format that makes two copies of the same photo different is also the one that teaches us to recognize them.