Il percorso verso l'ottimizzazione della ricerca di immagini su scala di miliardi (1/2)
Yupoo Picture Manager serve decine di milioni di utenti e gestisce decine di miliardi di immagini. Man mano che la sua galleria utenti diventa sempre più grande, Yupoo ha un'esigenza aziendale urgente di una soluzione che possa individuare rapidamente l'immagine. In altre parole, quando un utente inserisce un'immagine, il sistema dovrebbe trovare la sua immagine originale e immagini simili nella galleria. Lo sviluppo del servizio di ricerca per immagine fornisce un approccio efficace a questo problema.
Il servizio di ricerca per immagine ha attraversato due evoluzioni:
- Ha iniziato la prima indagine tecnica all'inizio del 2019 e ha lanciato il sistema di prima generazione a marzo e aprile 2019;
- Ha iniziato l'indagine del piano di aggiornamento all'inizio del 2020 e ha avviato l'aggiornamento complessivo al sistema di seconda generazione ad aprile 2020.
Questo articolo descrive la selezione della tecnologia e i principi di base alla base delle due generazioni di sistemi di ricerca per immagine, sulla base della mia esperienza personale in questo progetto.
Panoramica
Che cos'è un'immagine?
Dobbiamo sapere che cos'è un'immagine prima di occuparci delle immagini.
La risposta è che un'immagine è una raccolta di pixel.
Ad esempio, la parte nel riquadro rosso su questa immagine è virtualmente una serie di pixel.
Figura 1.
Supponiamo che la parte nel riquadro rosso sia un'immagine, allora ogni piccolo quadrato indipendente nell'immagine è un pixel, l'unità informativa di base. Quindi, la dimensione dell'immagine è 11 x 11 px.
Figura 2.
Rappresentazione matematica delle immagini
Ogni immagine può essere rappresentata da una matrice. Ogni pixel nell'immagine corrisponde a un elemento nella matrice.
Immagini binarie
I pixel di un'immagine binaria sono neri o bianchi, quindi ogni pixel può essere rappresentato da 0 o 1. Ad esempio, la rappresentazione matriciale di un'immagine binaria 4 * 4 è:
0 1 0 1
1 0 0 0
1 1 1 0
0 0 1 0
Immagini RGB
I tre colori primari (rosso, verde e blu) possono essere mescolati per produrre qualsiasi colore. Per le immagini RGB, ogni pixel contiene le informazioni di base di tre canali RGB. Allo stesso modo, se ogni canale utilizza un numero a 8 bit (in 256 livelli) per rappresentare la sua scala di grigi, allora la rappresentazione matematica di un pixel è:
([0 .. 255], [0 .. 255], [0 .. 255])
Prendendo come esempio un'immagine RGB 4 * 4:
Figura 3.
L'essenza dell'elaborazione delle immagini è elaborare queste matrici di pixel.
Il problema tecnico della ricerca per immagine
Se stai cercando l'immagine originale, cioè un'immagine con esattamente gli stessi pixel, allora puoi confrontare direttamente i loro valori MD5. Tuttavia, le immagini caricate su Internet sono spesso compresse o filigranate. Anche una piccola modifica in un'immagine può creare un risultato MD5 diverso. Finché c'è incoerenza nei pixel, è impossibile trovare l'immagine originale.
Per un sistema di ricerca per immagine, vogliamo cercare immagini con contenuti simili. Quindi, dobbiamo risolvere due problemi di base:
- Rappresentare o astrarre un'immagine come un formato di dati che possa essere elaborato da un computer.
- I dati devono essere confrontabili per il calcolo.
Più specificamente, abbiamo bisogno delle seguenti funzionalità:
- Estrazione delle caratteristiche dell'immagine.
- Calcolo delle caratteristiche (calcolo della similarità).
Il sistema di ricerca per immagine di prima generazione
Estrazione delle caratteristiche — astrazione dell'immagine
Il sistema di ricerca per immagine di prima generazione utilizza l'algoritmo Perceptual hash o pHash per l'estrazione delle caratteristiche. Quali sono le basi di questo algoritmo?
Ricerca di immagini di prima generazione.
Come mostrato nella figura sopra, l'algoritmo pHash esegue una serie di trasformazioni sull'immagine per ottenere il valore hash. Durante il processo di trasformazione, l'algoritmo astrae continuamente le immagini, avvicinando così tra loro i risultati delle immagini simili.
Calcolo delle caratteristiche — calcolo della similarità
Come calcolare la similarità tra i valori pHash di due immagini? La risposta è usare la distanza di Hamming. Più piccola è la distanza di Hamming, più simile è il contenuto delle immagini.
Che cos’è la distanza di Hamming? È il numero di bit diversi.
Per esempio,
Valore 1： 0 1 0 1 0
Valore 2： 0 0 0 1 1
Ci sono due bit diversi nei due valori sopra, quindi la distanza di Hamming tra loro è 2.
Ora conosciamo il principio del calcolo della similarità. La domanda successiva è: come calcolare le distanze di Hamming di dati su scala di 100 milioni provenienti da immagini su scala di 100 milioni? In breve, come cercare immagini simili?
Nella fase iniziale del progetto, non ho trovato uno strumento soddisfacente (o un motore di calcolo) in grado di calcolare rapidamente la distanza di Hamming. Quindi ho cambiato il mio piano.
La mia idea è che, se la distanza di Hamming di due valori pHash è piccola, allora posso tagliare i valori pHash e le piccole parti corrispondenti hanno probabilità di essere uguali.
Per esempio:
Valore 1： 8 a 0 3 0 3 f 6
Valore 2： 8 a 0 3 0 3 d 8
Dividiamo i due valori sopra in otto segmenti e i valori di sei segmenti sono esattamente gli stessi. Si può dedurre che la loro distanza di Hamming è vicina e quindi queste due immagini sono simili.
Dopo la trasformazione, puoi vedere che il problema del calcolo della distanza di Hamming è diventato un problema di corrispondenza di equivalenza. Se divido ogni valore pHash in otto segmenti, finché ci sono più di cinque segmenti che hanno valori esattamente uguali, allora i due valori pHash sono simili.
Quindi è molto semplice risolvere la corrispondenza di equivalenza. Possiamo usare il filtraggio classico di un sistema di database tradizionale.
Naturalmente, io uso la corrispondenza multi-termine e specifico il grado di corrispondenza usando minimum_should_match in ElasticSearch (questo articolo non introduce il principio di ES, puoi approfondirlo autonomamente).
Perché scegliamo ElasticSearch? Primo, fornisce la funzione di ricerca sopra menzionata. Secondo, il progetto image manager stesso sta usando ES per fornire una funzione di ricerca full-text ed è molto conveniente usare le risorse esistenti.
Riepilogo del sistema di prima generazione
Il sistema di ricerca per immagine di prima generazione sceglie la soluzione pHash + ElasticSearch, che ha le seguenti caratteristiche:
- L’algoritmo pHash è semplice da usare e può resistere a un certo grado di compressione, watermark e rumore.
- ElasticSearch usa le risorse esistenti del progetto senza aggiungere costi aggiuntivi alla ricerca.
Ma la limitazione di questo sistema è evidente: l’algoritmo pHash è una rappresentazione astratta dell’intera immagine. Una volta che distruggiamo l’integrità dell’immagine, ad esempio aggiungendo un bordo nero all’immagine originale, è quasi impossibile giudicare la similarità tra l’originale e le altre.
Per superare tali limitazioni, è emerso il sistema di ricerca immagini di seconda generazione con una tecnologia sottostante completamente diversa.
Questo articolo è scritto da rifewang, utente Milvus e software engineer di UPYUN. Se ti piace questo articolo, sei il benvenuto a passare a salutare! https://github.com/rifewang
Continua a leggere
Zilliz Cloud Just Landed in Claude Code
The Zilliz Cloud Plugin brings the full power of Zilliz Cloud directly into your Claude Code terminal as natural-language conversations.
Zilliz Cloud Now Available in Azure North Europe: Bringing AI-Powered Vector Search Closer to European Customers
The addition of the Azure North Europe (Ireland) region further expands our global footprint to better serve our European customers.
Announcing the General Availability of Zilliz Cloud BYOC on Google Cloud Platform
Zilliz Cloud BYOC on GCP offers enterprise vector search with full data sovereignty and seamless integration.