Perceptual hash: search for similar images

Perceptual Hash: How Algorithms Find Similar Images

Perceptual hashing allows detecting visual similarity between images, even if they differ in size, color, or compression level. Unlike cryptographic hashes like SHA1, perceptual hashes preserve information about the image structure and are robust to minor modifications. This makes them indispensable in systems for finding duplicates, content recognition, and digital forensics.

Basics of Perceptual Hashing

Cryptographic hash functions are designed to verify exact data matches: even the slightest change in the input file results in a completely different hash. Perceptual hashes solve a different problem—they remain similar for visually insignificant changes to the image. This approach is based on the fact that human perception ignores fine details and focuses on the overall structure.

Perceptual hashing algorithms are typically:

• Robust to changes in size and aspect ratio;
• Invariant to brightness and contrast adjustments;
• Preserve similarity under light compression or noise;
• Fast and scalable.

To compare two images, their hashes are computed, and then the Hamming distance is measured—the number of differing bits. The smaller the distance, the greater the visual similarity.

Simplest Method: Average Hash

One of the most accessible perceptual hashing algorithms is based on pixel averaging. It consists of the following steps:

• Resize to 8×8 pixels—this drastically reduces the impact of high-frequency details.
• Convert to grayscale—eliminates dependence on color channels.
• Compute the average brightness of all 64 pixels.
• Binarization: each pixel is replaced with 1 if its brightness is above the average, and 0 if below.
• Form a 64-bit hash by concatenating the bits (usually left to right, top to bottom).

This method is extremely fast and effective for finding exact or near-exact duplicates. However, it is sensitive to nonlinear transformations like gamma correction or histogram changes, as the average shifts and many bits flip.

Improved Approach: pHash Based on DCT

The pHash (perceptual hash) algorithm uses the discrete cosine transform (DCT) to focus on low-frequency components of the image—these define the overall structure. The steps of pHash:

• Resize to 32×32 pixels—sufficient for proper DCT application.
• Convert to grayscale.
• Apply DCT to the entire image (unlike JPEG, where DCT is applied to 8×8 blocks).
• Extract the top-left 8×8 block from the resulting frequency matrix—it contains the lowest frequencies.
• Compute the average of these 64 coefficients, excluding the first (DC component), to avoid dependence on overall brightness.
• Binarize the coefficients relative to this average.
• Form a 64-bit hash.

This approach is significantly more robust to color and brightness distortions. Even after gamma correction or local changes (e.g., adding a watermark to a small part of the image), the hash remains close to the original.

Practical Applications and Limitations

In real-world systems like TinEye or internal digital forensics tools, multiple methods are often combined:

• Precomputed hashes for the entire archive;
• Fast average hash for initial filtering;
• pHash or other advanced algorithms for refinement;
• Additional features: color distribution, object positions, face presence.

For example, with a face recognition system, separate hashes can be computed just for face regions, improving accuracy in portrait collections.

However, no perceptual hash guarantees 100% accuracy. Significant changes—like replacing the background, rotating by a large angle, or swapping key objects—can make images visually different, yet hashes may still be close, or vice versa.

Key Points

• Perceptual hash measures visual, not bitwise, similarity.
• Hamming distance between hashes is the primary way to assess similarity.
• Average hash is fast but vulnerable to nonlinear transformations.
• DCT-based pHash provides better robustness to modifications.
• Industrial systems use method combinations and pre-indexing.

Method Comparison

| Criterion | Average Hash | pHash (DCT) |

|------------------------|--------------|-----------------|

| Speed | Very High | Moderate |

| Noise Robustness | Medium | High |

| Gamma Robustness | Low | High |

| Memory Required | Minimal | Moderate |

| Suitable for Bulk Search | Yes | Yes (with indexing) |

The choice of method depends on the task: average hash for exact copies, pHash for modified images.

— Editorial Team