Perceptual hash per le immagini
Un utente carica una foto. Un altro utente carica la stessa foto, ridimensionata, ricompressa in JPEG al 70% e con un leggero ritocco al contrasto. Per un essere umano sono la stessa immagine. Per md5_file() sono due file che non hanno nulla in comune.
Il perceptual hash risolve esattamente questo problema: produce un'impronta che descrive come appare un'immagine, non come è codificata. In questo articolo vedremo la teoria, le tre famiglie principali di algoritmi, e implementeremo da zero aHash, dHash e pHash in PHP, usando solo l'estensione GD.
Il problema dei quasi-duplicati
Gli hash crittografici — MD5, SHA-1, SHA-256 — sono progettati per una proprietà precisa: l'effetto valanga. Cambiare un singolo bit dell'input deve cambiare, in media, metà dei bit dell'output. È esattamente ciò che vogliamo per verificare l'integrità di un file o firmare un token. È esattamente ciò che non vogliamo per confrontare immagini.
Basta salvare due volte lo stesso JPEG per ottenere byte diversi. Ridimensionare un'immagine da 4000 a 1200 pixel cambia ogni singolo valore. Rimuovere i metadati EXIF cambia l'hash senza toccare un solo pixel.
foto_originale.jpg → sha1: 3f2a9c1e5b7d4e8a9c217d4e5f6a8b90c1d2e3f4
foto_ridimensionata.jpg → sha1: a81c04d7e29b5f63c0d8e1a7b4f92c6d3e5a1b08
foto_senza_exif.jpg → sha1: 7e4b1a9d2c8f6e3a5b0d9c7e1f4a2b6c8d3e5f90
Tre hash completamente diversi per tre file che contengono la stessa fotografia. Se il nostro obiettivo è trovare duplicati in una galleria, bloccare il ricaricamento di contenuti già rimossi da un moderatore o raggruppare scatti simili, l'hash crittografico non serve a niente.
Serve una funzione con la proprietà opposta: input simili devono produrre output simili.
Cos'è un perceptual hash
Un perceptual hash è una funzione che riduce un'immagine a una sequenza di bit, tipicamente 64, in modo che due immagini visivamente simili producano sequenze quasi identiche.
L'idea è buttare via tutto ciò che l'occhio umano ignora — risoluzione, colore, rumore di compressione, piccoli dettagli — e tenere solo la struttura: dove sono le zone chiare, dove sono quelle scure, come varia la luce da un punto all'altro. Quello che resta è una specie di miniatura semantica dell'immagine.
Tutti gli algoritmi che vedremo seguono lo stesso schema in tre passi:
- Ridurre. L'immagine viene rimpicciolita drasticamente (8×8, 9×8 o 32×32 pixel) e convertita in scala di grigi. Già qui spariscono formato, dimensioni e quasi tutto il rumore.
- Estrarre. Dai pochi pixel rimasti si calcola una caratteristica: la luminosità media, i gradienti, le frequenze.
- Binarizzare. Ogni valore viene confrontato con una soglia e diventa 0 o 1. I 64 bit risultanti sono l'hash.
La distanza di Hamming
Un hash crittografico si confronta con ===: o è uguale o è diverso. Un perceptual hash si confronta con la distanza di Hamming, cioè il numero di bit che differiscono tra due hash.
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
distanza di Hamming = 2
Il calcolo è banale: si fa lo XOR bit a bit e si contano gli 1. Su 64 bit, una distanza 0 indica immagini praticamente identiche, una distanza intorno a 32 indica immagini senza alcuna relazione (è quello che ci si aspetta da due sequenze casuali: metà dei bit coincide per puro caso).
Tre famiglie
Nel 2011 Neal Krawetz pubblicò sul suo blog Hacker Factor un articolo intitolato Looks Like It, che rese popolari due algoritmi molto semplici, seguito due anni dopo da un terzo. Sono ancora oggi i tre punti di partenza di chiunque si avvicini all'argomento.
| Algoritmo | Riduzione | Caratteristica estratta | Soglia |
|---|---|---|---|
| aHash (Average Hash) | 8×8 | luminosità di ogni pixel | media dei 64 pixel |
| dHash (Difference Hash) | 9×8 | differenza tra pixel adiacenti | il pixel a destra |
| pHash (Perceptual Hash, DCT) | 32×32 | 64 coefficienti di bassa frequenza della DCT | mediana dei coefficienti |
L'aHash è il più semplice: un bit vale 1 se il pixel è più chiaro della media. È velocissimo ma fragile: basta una variazione non lineare di luminosità o contrasto per spostare la media e ribaltare molti bit.
Il dHash non guarda i valori assoluti ma le differenze: un bit vale 1 se un pixel è più chiaro del suo vicino di destra. Descrive i gradienti, cioè la direzione in cui varia la luce, e per questo resiste molto bene ai cambi di esposizione.
Il pHash è il più sofisticato: invece dei pixel analizza le frequenze dell'immagine tramite la Discrete Cosine Transform, la stessa trasformata alla base del JPEG. Merita una sezione a parte.
Come funziona il pHash
Il pHash basato su DCT è stato analizzato a fondo da Christoph Zauner nella sua tesi del 2010, Implementation and Benchmarking of Perceptual Image Hash Functions, ed è alla base della libreria open source pHash. L'intuizione è questa: un'immagine non è solo una griglia di pixel, è anche una somma di onde.
Le frequenze di un'immagine
Pensiamo a una singola riga di pixel. Possiamo vederla come una sequenza di valori di luminosità, oppure come la sovrapposizione di onde coseno di frequenza crescente: un'onda lentissima che descrive l'andamento generale (più chiaro a sinistra, più scuro a destra), poi onde via via più rapide che aggiungono i dettagli, fino a quelle velocissime che codificano bordi netti, texture e rumore.
La Discrete Cosine Transform (DCT) fa esattamente questa scomposizione: prende N valori e restituisce N coefficienti, ognuno dei quali dice quanto di una certa frequenza è presente nel segnale. Per una sequenza di N valori, il coefficiente k-esimo vale:
$X_k = \alpha_k \sum_{i=0}^{N-1} x_i \cos\left[\frac{\pi (2i+1) k}{2N}\right]$
con $\alpha_0 = \sqrt{1/N}$ e $\alpha_k = \sqrt{2/N}$ per $k > 0$.
Il coefficiente X₀ è la componente continua (il valore medio, detto DC). X₁ è l'onda più lenta, X₂ un po' più rapida, e così via. In due dimensioni si applica la stessa trasformata prima a ogni riga e poi a ogni colonna: la DCT è separabile.
Il risultato è una matrice in cui l'angolo in alto a sinistra contiene le basse frequenze (la struttura generale dell'immagine) e l'angolo in basso a destra le alte frequenze (i dettagli fini).
frequenze orizzontali →
┌──────────┬───────────────────────┐
f │ DC bassa│ │
r │ ▓▓▓▓▓▓▓▓ │ │
e │ ▓ 8×8 ▓ │ medie frequenze │
q │ ▓▓▓▓▓▓▓▓ │ │
. ├──────────┘ │
│ │
v │ alte │
e │ frequenze │
r │ (dettagli, │
t │ rumore) │
↓ └──────────────────────────────────┘
32 × 32
È lo stesso principio su cui si basa il JPEG: l'occhio umano è poco sensibile alle alte frequenze, quindi il compressore le quantizza aggressivamente. Il pHash va oltre: le butta via del tutto.
L'algoritmo
- Ridimensionare a 32×32 in scala di grigi. Più grande dell'8×8 dell'aHash, perché la DCT ha bisogno di un minimo di informazione da cui estrarre le frequenze.
- Calcolare la DCT 2D della matrice 32×32, ottenendo 1.024 coefficienti.
- Tenere il blocco 8×8 in alto a sinistra: i 64 coefficienti di frequenza più bassa. Tutto il resto — compreso il rumore della compressione JPEG — viene scartato.
- Calcolare la mediana dei 64 coefficienti. Si usa la mediana e non la media perché il coefficiente DC è enormemente più grande degli altri e sposterebbe la media verso l'alto.
- Binarizzare: ogni coefficiente sopra la mediana diventa 1, gli altri 0.
Usare la mediana ha un effetto collaterale elegante: per definizione metà dei bit sarà 1 e metà 0. L'hash è sempre bilanciato, e questo rende la distanza di Hamming più informativa.
Il bit corrispondente al DC, essendo il coefficiente più grande, sarà praticamente sempre 1. Alcune implementazioni lo escludono e ripiegano su 63 bit utili; noi lo terremo, per semplicità e per allinearci a quanto fanno le librerie più diffuse.
L'implementazione in PHP
Raccogliamo tutto in una classe PerceptualHash con metodi statici, senza dipendenze esterne oltre all'estensione GD, presente in praticamente ogni installazione PHP. Il codice richiede PHP 8.0 o superiore, perché GD restituisce oggetti GdImage invece delle vecchie resource.
Una scelta di design da chiarire subito: rappresentiamo l'hash come stringa esadecimale di 16 caratteri e non come intero. Gli interi di PHP sono a 64 bit con segno: un hash con il bit più significativo a 1 diventerebbe negativo, e alcune operazioni aritmetiche andrebbero in overflow trasformandosi silenziosamente in float. Una stringa hex è portabile, leggibile nei log e si salva senza sorprese in qualsiasi database.
load() e grayscaleMatrix()
load() accetta qualsiasi formato supportato da GD (JPEG, PNG, GIF, WebP) grazie a imagecreatefromstring(). grayscaleMatrix() è il passo di riduzione comune a tutti e tre gli algoritmi: ridimensiona con imagecopyresampled(), che a differenza di imagecopyresized() fa una media dei pixel invece di campionarli, e converte ogni pixel in luminanza.
final class PerceptualHash
{
/** Popcount per i 16 valori possibili di un 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("Formato non supportato: $path");
}
return $image;
}
/**
* Ridimensiona l'immagine a $w x $h e la converte in una matrice
* di luminanza [riga][colonna] con valori 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;
// Luminanza secondo ITU-R BT.601
$matrix[$y][$x] = 0.299 * $r + 0.587 * $g + 0.114 * $b;
}
}
imagedestroy($small);
return $matrix;
}
I pesi 0.299, 0.587 e 0.114 non sono casuali: riflettono la diversa sensibilità dell'occhio umano ai tre canali. Vediamo il verde molto meglio del blu, e una media aritmetica semplice produrrebbe grigi percettivamente sbagliati.
aHash()
Riduzione a 8×8, media, confronto. Con array_merge(...) e lo spread operator appiattiamo la matrice in un array di 64 valori.
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()
Riduciamo a 9 colonne per 8 righe: 9 pixel per riga danno esattamente 8 confronti tra vicini, e 8 righe × 8 confronti fanno 64 bit.
public static function dHash(GdImage $image): string
{
// 9 colonne per ottenere 8 confronti per riga
$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()
I cinque passi dell'algoritmo, uno per riga logica. I parametri $size e $keep permettono di sperimentare con dimensioni diverse, ma 32 e 8 sono i valori standard.
public static function pHash(GdImage $image, int $size = 32, int $keep = 8): string
{
$matrix = self::grayscaleMatrix($image, $size, $size);
$dct = self::dct2d($matrix);
// Solo il blocco in alto a sinistra: le basse frequenze
$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() e cosineTable()
Il cuore matematico. Sfruttiamo la separabilità: invece di una DCT 2D diretta, che su una matrice 32×32 costerebbe 32⁴ ≈ 1 milione di moltiplicazioni, facciamo 32 DCT sulle righe e 32 sulle colonne, per un totale di 2 × 32³ ≈ 65.000 moltiplicazioni.
I coseni dipendono solo da k, i e N, non dall'immagine. Li calcoliamo una volta sola e li teniamo in una cache static: con un worker che processa migliaia di immagini, cos() viene chiamata 1.024 volte in tutto.
/** DCT-II bidimensionale, separabile: prima le righe, poi le colonne. */
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() e bitsToHex()
Due utility. bitsToHex() raggruppa i 64 bit in blocchi da 4 (un nibble) e converte ognuno in una cifra esadecimale.
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 bit → 16 caratteri esadecimali. */
private static function bitsToHex(array $bits): string
{
$hex = '';
foreach (array_chunk($bits, 4) as $nibble) {
$hex .= dechex(bindec(implode('', $nibble)));
}
return $hex;
}
distance()
PHP non ha una funzione nativa di popcount (il conteggio dei bit a 1) senza l'estensione GMP. Lavorando su stringhe hex la soluzione è semplice: facciamo lo XOR cifra per cifra e cerchiamo il risultato in una tabella di 16 elementi precalcolata.
public static function distance(string $a, string $b): int
{
if (strlen($a) !== strlen($b)) {
throw new InvalidArgumentException('Gli hash devono avere la stessa lunghezza');
}
$distance = 0;
for ($i = 0, $len = strlen($a); $i < $len; $i++) {
$distance += self::POPCOUNT4[hexdec($a[$i]) ^ hexdec($b[$i])];
}
return $distance;
}
}
Un esempio completo
Per metterlo alla prova ho generato con GD un'immagine sintetica da 1600×1200 pixel (un gradiente con dodici ellissi colorate) e sette varianti: ridimensionata, ricompressa, ritoccata, con watermark, ritagliata, specchiata, più un'immagine completamente diversa.
<?php
require 'PerceptualHash.php';
$original = PerceptualHash::load('originale.png');
$ref = [
'a' => PerceptualHash::aHash($original),
'd' => PerceptualHash::dHash($original),
'p' => PerceptualHash::pHash($original),
];
printf("originale.png aHash %s dHash %s pHash %s\n\n", $ref['a'], $ref['d'], $ref['p']);
$variants = [
'ridimensionata.jpg', 'jpeg_q30.jpg', 'luminosita.png', 'watermark.png',
'ritagliata.png', 'specchiata.png', 'diversa.png',
];
foreach ($variants as $file) {
$image = PerceptualHash::load($file);
printf(
"%-20s 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:
originale.png aHash f098b838118fc7ff dHash 98cc8c9cdad0e0d8 pHash cc4df232c6c7c332
ridimensionata.jpg aHash 0 dHash 0 pHash 0
jpeg_q30.jpg aHash 0 dHash 1 pHash 0
luminosita.png aHash 16 dHash 0 pHash 4
watermark.png aHash 1 dHash 0 pHash 4
ritagliata.png aHash 13 dHash 9 pHash 14
specchiata.png aHash 28 dHash 23 pHash 32
diversa.png aHash 26 dHash 39 pHash 32
I numeri raccontano bene i punti di forza e di debolezza di ciascun algoritmo.
Ridimensionamento e ricompressione — passata da 1600×1200 a 400×300, o salvata in JPEG a qualità 30 — non lasciano praticamente traccia: distanza 0 o 1 per tutti e tre. È il caso d'uso principale, ed è risolto.
Luminosità e contrasto mettono in crisi l'aHash: 16 bit su 64 cambiati. Aumentando la luminosità le zone più chiare saturano a 255, la distribuzione dei grigi si deforma e la media non separa più le stesse aree. Il dHash, che guarda solo le differenze tra vicini, non se ne accorge nemmeno: distanza 0.
Il ritaglio del 10% per lato è già al limite per tutti: l'hash descrive la composizione globale, e spostare i bordi sposta la composizione.
La specchiatura è il limite strutturale: per un perceptual hash un'immagine riflessa è un'immagine diversa, con distanze nella stessa zona di un'immagine completamente estranea (intorno a 32). Se serve riconoscerle, bisogna calcolare anche l'hash della versione specchiata con imageflip() e confrontare entrambi.
In produzione
Calcolare un hash è la parte facile. Il problema reale è un altro: dato un nuovo upload, come troviamo in un archivio di milioni di immagini tutte quelle a distanza ≤ 10?
Salvare l'hash
Nel codice PHP abbiamo usato stringhe hex per portabilità, ma nel database conviene un intero a 64 bit, perché i database sanno fare XOR e popcount in modo nativo. In MySQL e MariaDB la colonna giusta è BIGINT UNSIGNED, e la conversione si fa direttamente in SQL con CONV():
ALTER TABLE images ADD COLUMN phash BIGINT UNSIGNED NULL;
UPDATE images SET phash = CONV('cc4df232c6c7c332', 16, 10) WHERE id = 42;
La ricerca dei quasi-duplicati diventa una sola query, grazie a 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 il tipo naturale è bit(64), e dalla versione 14 è disponibile bit_count(). In un'applicazione Laravel, il calcolo trova posto in un job accodato al momento dell'upload, così la richiesta HTTP non paga il costo del ridimensionamento.
Il problema della scansione completa
Quella query ha un difetto: nessun indice B-tree può aiutarla. La condizione su BIT_COUNT() obbliga il database a calcolare lo XOR su ogni singola riga. Fino a qualche centinaio di migliaia di immagini è perfettamente accettabile, perché si tratta di operazioni sui 64 bit velocissime. Oltre, serve una struttura dati dedicata.
La soluzione più usata sfrutta il principio dei cassetti. Dividiamo i 64 bit in 4 blocchi da 16. Se due hash distano al massimo 3 bit, almeno uno dei 4 blocchi deve essere identico, perché 3 differenze non bastano a sporcarli tutti. Salviamo i 4 blocchi in 4 colonne indicizzate, cerchiamo i candidati con un WHERE b1 = ? OR b2 = ? OR b3 = ? OR b4 = ? che usa gli indici, e calcoliamo la distanza esatta solo su quelli. Per soglie più alte si usano più blocchi più piccoli, oppure strutture come i BK-tree, alberi pensati apposta per le ricerche in spazi metrici come quello definito dalla distanza di Hamming.
Scegliere la soglia
Non esiste un valore universale. Come regola empirica, con un pHash a 64 bit:
| Distanza | Interpretazione tipica |
|---|---|
| 0–5 | stessa immagine: resize, ricompressione, piccoli ritocchi |
| 6–10 | molto probabilmente la stessa, con modifiche più evidenti |
| 11–20 | zona grigia: scatti simili, stessa scena, crop importanti |
| > 20 | immagini diverse |
La soglia va calibrata sui propri dati. Su una piattaforma di foto prodotto, dove molte immagini hanno lo stesso sfondo bianco e la stessa composizione, una soglia di 10 genererà falsi positivi. Su un archivio di fotografie eterogenee, la stessa soglia sarà fin troppo prudente. Il metodo corretto è raccogliere qualche centinaio di coppie etichettate a mano e guardare dove si separano le distribuzioni.
Performance
Sul mio test l'intero calcolo di un pHash su un'immagine da 1600×1200 richiede circa 30 millisecondi, in linea con dHash e aHash. Non è un caso: il tempo è dominato da imagecopyresampled(), che deve leggere quasi due milioni di pixel. La DCT su 32×32 è trascurabile in confronto.
Per immagini molto grandi conviene quindi lasciare a GD, o meglio a Imagick, il lavoro pesante: se l'applicazione genera già le miniature, calcolare l'hash sulla miniatura invece che sull'originale non cambia il risultato e abbatte i tempi.
I limiti
Un perceptual hash è uno strumento statistico, non una prova. Abbiamo visto che è cieco alle rotazioni e alle specchiature e fragile davanti ai ritagli importanti. E soprattutto non è progettato per resistere a un avversario: nel 2021, poche settimane dopo l'annuncio di NeuralHash da parte di Apple, alcuni ricercatori hanno generato immagini completamente diverse con lo stesso hash. Per la moderazione dei contenuti l'industria usa algoritmi più robusti, come PhotoDNA di Microsoft o PDQ, rilasciato open source da Meta nel 2019, ma il principio di fondo resta lo stesso che abbiamo implementato qui.
Conclusione
Il perceptual hash ribalta la logica dell'hash crittografico: invece di amplificare ogni minima differenza, la assorbe. Il trucco non sta in una formula particolarmente sofisticata, ma in una scelta di cosa ignorare: la risoluzione, il colore, il rumore, le alte frequenze. Quello che resta, 64 bit in tutto, è sorprendentemente sufficiente a riconoscere un'immagine tra milioni.
In meno di 200 righe di PHP, senza librerie esterne, abbiamo tre algoritmi funzionanti e una misura di distanza. Il dHash, per la sua resistenza ai cambi di luminosità e la sua semplicità, è spesso il miglior punto di partenza. Il pHash è la scelta più equilibrata quando la qualità del riconoscimento conta più di qualche millisecondo.
La cosa affascinante è che la DCT che abbiamo usato è la stessa che da trent'anni il JPEG usa per decidere cosa buttare. Il formato che rende diverse due copie della stessa foto è anche quello che ci insegna a riconoscerle.