El viaje hacia la optimización de la búsqueda de imágenes a escala de miles de millones (1/2)
Yupoo Picture Manager presta servicio a decenas de millones de usuarios y gestiona decenas de miles de millones de imágenes. A medida que su galería de usuarios crece, Yupoo tiene una necesidad empresarial urgente de una solución que pueda localizar rápidamente la imagen. En otras palabras, cuando un usuario introduce una imagen, el sistema debe encontrar su imagen original e imágenes similares en la galería. El desarrollo del servicio de búsqueda por imagen proporciona un enfoque eficaz para este problema.
El servicio de búsqueda por imagen ha pasado por dos evoluciones:
- Comenzó la primera investigación técnica a principios de 2019 y lanzó el sistema de primera generación en marzo y abril de 2019;
- Comenzó la investigación del plan de actualización a principios de 2020 e inició la actualización general al sistema de segunda generación en abril de 2020.
Este artículo describe la selección de tecnología y los principios básicos detrás de las dos generaciones del sistema de búsqueda por imagen basándose en mi propia experiencia en este proyecto.
Descripción general
¿Qué es una imagen?
Debemos saber qué es una imagen antes de trabajar con imágenes.
La respuesta es que una imagen es una colección de píxeles.
Por ejemplo, la parte en el recuadro rojo de esta imagen es, en la práctica, una serie de píxeles.
Figura 1.
Supongamos que la parte en el recuadro rojo es una imagen; entonces, cada pequeño cuadrado independiente de la imagen es un píxel, la unidad básica de información. Entonces, el tamaño de la imagen es de 11 x 11 px.
Figura 2.
Representación matemática de las imágenes
Cada imagen puede representarse mediante una matriz. Cada píxel de la imagen corresponde a un elemento de la matriz.
Imágenes binarias
Los píxeles de una imagen binaria son negros o blancos, por lo que cada píxel puede representarse mediante 0 o 1. Por ejemplo, la representación matricial de una imagen binaria de 4 * 4 es:
0 1 0 1
1 0 0 0
1 1 1 0
0 0 1 0
Imágenes RGB
Los tres colores primarios (rojo, verde y azul) pueden mezclarse para producir cualquier color. Para las imágenes RGB, cada píxel tiene la información básica de tres canales RGB. Del mismo modo, si cada canal utiliza un número de 8 bits (en 256 niveles) para representar su escala de grises, entonces la representación matemática de un píxel es:
([0 .. 255], [0 .. 255], [0 .. 255])
Tomando como ejemplo una imagen RGB de 4 * 4:
Figura 3.
La esencia del procesamiento de imágenes es procesar estas matrices de píxeles.
El problema técnico de la búsqueda por imagen
Si estás buscando la imagen original, es decir, una imagen con exactamente los mismos píxeles, entonces puedes comparar directamente sus valores MD5. Sin embargo, las imágenes subidas a Internet suelen estar comprimidas o tener marcas de agua. Incluso un pequeño cambio en una imagen puede crear un resultado MD5 diferente. Siempre que haya incoherencia en los píxeles, es imposible encontrar la imagen original.
Para un sistema de búsqueda por imagen, queremos buscar imágenes con contenido similar. Entonces, necesitamos resolver dos problemas básicos:
- Representar o abstraer una imagen como un formato de datos que pueda ser procesado por una computadora.
- Los datos deben ser comparables para el cálculo.
Más específicamente, necesitamos las siguientes características:
- Extracción de características de la imagen.
- Cálculo de características (cálculo de similitud).
El sistema de búsqueda por imagen de primera generación
Extracción de características — abstracción de la imagen
El sistema de búsqueda por imagen de primera generación utiliza el algoritmo Perceptual hash o pHash para la extracción de características. ¿Cuáles son los fundamentos de este algoritmo?
Búsqueda de imágenes de primera generación.
Como se muestra en la figura anterior, el algoritmo pHash realiza una serie de transformaciones en la imagen para obtener el valor hash. Durante el proceso de transformación, el algoritmo abstrae continuamente las imágenes, acercando así los resultados de imágenes similares entre sí.
Cálculo de características — cálculo de similitud
¿Cómo calcular la similitud entre los valores pHash de dos imágenes? La respuesta es usar la distancia de Hamming. Cuanto menor sea la distancia de Hamming, más similar será el contenido de las imágenes.
¿Qué es la distancia de Hamming? Es el número de bits diferentes.
Por ejemplo,
Valor 1： 0 1 0 1 0
Valor 2： 0 0 0 1 1
Hay dos bits diferentes en los dos valores anteriores, por lo que la distancia de Hamming entre ellos es 2.
Ahora conocemos el principio del cálculo de similitud. La siguiente pregunta es: ¿cómo calcular las distancias de Hamming de datos a escala de 100 millones a partir de 100 millones de imágenes? En resumen, ¿cómo buscar imágenes similares?
En la etapa inicial del proyecto, no encontré una herramienta satisfactoria (o un motor de cómputo) que pudiera calcular rápidamente la distancia de Hamming. Así que cambié mi plan.
Mi idea es que si la distancia de Hamming de dos valores pHash es pequeña, entonces puedo cortar los valores pHash y es probable que las partes pequeñas correspondientes sean iguales.
Por ejemplo:
Valor 1： 8 a 0 3 0 3 f 6
Valor 2： 8 a 0 3 0 3 d 8
Dividimos los dos valores anteriores en ocho segmentos y los valores de seis segmentos son exactamente iguales. Se puede inferir que su distancia de Hamming es cercana y, por lo tanto, estas dos imágenes son similares.
Después de la transformación, puedes ver que el problema de calcular la distancia de Hamming se ha convertido en un problema de coincidencia de equivalencia. Si divido cada valor pHash en ocho segmentos, siempre que haya más de cinco segmentos que tengan exactamente los mismos valores, entonces los dos valores pHash son similares.
Por lo tanto, es muy sencillo resolver la coincidencia de equivalencia. Podemos usar el filtrado clásico de un sistema de base de datos tradicional.
Por supuesto, uso la coincidencia de múltiples términos y especifico el grado de coincidencia usando minimum_should_match en ElasticSearch (este artículo no introduce el principio de ES, puedes aprenderlo por tu cuenta).
¿Por qué elegimos ElasticSearch? Primero, proporciona la función de búsqueda mencionada anteriormente. Segundo, el proyecto de gestión de imágenes en sí está usando ES para proporcionar una función de búsqueda de texto completo y es muy económico usar los recursos existentes.
Resumen del sistema de primera generación
El sistema de búsqueda por imagen de primera generación elige la solución pHash + ElasticSearch, que tiene las siguientes características:
- El algoritmo pHash es fácil de usar y puede resistir cierto grado de compresión, marca de agua y ruido.
- ElasticSearch usa los recursos existentes del proyecto sin añadir costes adicionales a la búsqueda.
Pero la limitación de este sistema es evidente: el algoritmo pHash es una representación abstracta de toda la imagen. Una vez que destruimos la integridad de la imagen, como añadir un borde negro a la imagen original, es casi imposible juzgar la similitud entre la original y las demás.
Para superar tales limitaciones, surgió el sistema de búsqueda de imágenes de segunda generación con una tecnología subyacente completamente diferente.
Este artículo está escrito por rifewang, usuario de Milvus e ingeniero de software de UPYUN. Si te gusta este artículo, ¡te invitamos a venir a saludar! https://github.com/rifewang
Sigue leyendo
A Developer's Guide to Exploring Milvus 2.6 Features on Zilliz Cloud
Milvus 2.6 marks a shift from “vector search + glue code” to a more advanced retrieval engine, and it is now Generally Available (GA) on Zilliz Cloud (a managed Milvus service).
The Real Bottlenecks in Autonomous Driving — And How AI Infrastructure Can Solve Them
Autonomous driving faces a data bottleneck. Learn how AI-native vector databases like Zilliz solve scale, cost, and insight challenges across AV pipelines.
Why Not All VectorDBs Are Agent-Ready
Explore why choosing the right vector database is critical for scaling AI agents, and why traditional solutions fall short in production.