A Jornada para Otimizar a Busca de Imagens em Escala de Bilhões (1/2)
O Yupoo Picture Manager atende dezenas de milhões de usuários e gerencia dezenas de bilhões de imagens. À medida que a galeria de usuários cresce, o Yupoo tem uma necessidade comercial urgente de uma solução que possa localizar rapidamente a imagem. Em outras palavras, quando um usuário insere uma imagem, o sistema deve encontrar sua imagem original e imagens semelhantes na galeria. O desenvolvimento do serviço de busca por imagem fornece uma abordagem eficaz para esse problema.
O serviço de busca por imagem passou por duas evoluções:
- Iniciou a primeira investigação técnica no início de 2019 e lançou o sistema de primeira geração em março e abril de 2019;
- Iniciou a investigação do plano de atualização no início de 2020 e começou a atualização geral para o sistema de segunda geração em abril de 2020.
Este artigo descreve a seleção de tecnologia e os princípios básicos por trás das duas gerações do sistema de busca por imagem com base na minha própria experiência neste projeto.
Visão geral
O que é uma imagem?
Devemos saber o que é uma imagem antes de lidar com imagens.
A resposta é que uma imagem é uma coleção de pixels.
Por exemplo, a parte na caixa vermelha nesta imagem é virtualmente uma série de pixels.
Figura 1.
Suponha que a parte na caixa vermelha seja uma imagem, então cada pequeno quadrado independente na imagem é um pixel, a unidade básica de informação. Então, o tamanho da imagem é 11 x 11 px.
Figura 2.
Representação matemática de imagens
Cada imagem pode ser representada por uma matriz. Cada pixel na imagem corresponde a um elemento na matriz.
Imagens binárias
Os pixels de uma imagem binária são pretos ou brancos, então cada pixel pode ser representado por 0 ou 1. Por exemplo, a representação matricial de uma imagem binária 4 * 4 é:
0 1 0 1
1 0 0 0
1 1 1 0
0 0 1 0
Imagens RGB
As três cores primárias (vermelho, verde e azul) podem ser misturadas para produzir qualquer cor. Para imagens RGB, cada pixel tem as informações básicas de três canais RGB. Da mesma forma, se cada canal usa um número de 8 bits (em 256 níveis) para representar sua escala de cinza, então a representação matemática de um pixel é:
([0 .. 255], [0 .. 255], [0 .. 255])
Tomando uma imagem RGB 4 * 4 como exemplo:
Figura 3.
A essência do processamento de imagens é processar essas matrizes de pixels.
O problema técnico da busca por imagem
Se você está procurando a imagem original, ou seja, uma imagem com exatamente os mesmos pixels, então você pode comparar diretamente seus valores MD5. No entanto, imagens enviadas para a Internet são frequentemente comprimidas ou recebem marcas-d’água. Mesmo uma pequena alteração em uma imagem pode criar um resultado MD5 diferente. Enquanto houver inconsistência nos pixels, é impossível encontrar a imagem original.
Para um sistema de busca por imagem, queremos pesquisar imagens com conteúdo semelhante. Então, precisamos resolver dois problemas básicos:
- Representar ou abstrair uma imagem como um formato de dados que possa ser processado por um computador.
- Os dados devem ser comparáveis para cálculo.
Mais especificamente, precisamos dos seguintes recursos:
- Extração de características de imagem.
- Cálculo de características (cálculo de similaridade).
O sistema de busca por imagem de primeira geração
Extração de características — abstração de imagem
O sistema de busca por imagem de primeira geração usa o algoritmo Perceptual hash ou pHash para extração de características. Quais são os fundamentos desse algoritmo?
Busca de imagens de primeira geração.
Como mostrado na figura acima, o algoritmo pHash realiza uma série de transformações na imagem para obter o valor de hash. Durante o processo de transformação, o algoritmo abstrai continuamente imagens, aproximando assim os resultados de imagens semelhantes entre si.
Cálculo de características — cálculo de similaridade
Como calcular a similaridade entre os valores pHash de duas imagens? A resposta é usar a distância de Hamming. Quanto menor a distância de Hamming, mais semelhante é o conteúdo das imagens.
O que é distância de Hamming? É o número de bits diferentes.
Por exemplo,
Valor 1： 0 1 0 1 0
Valor 2： 0 0 0 1 1
Há dois bits diferentes nos dois valores acima, portanto a distância de Hamming entre eles é 2.
Agora conhecemos o princípio do cálculo de similaridade. A próxima pergunta é: como calcular as distâncias de Hamming de dados na escala de 100 milhões a partir de imagens na escala de 100 milhões? Em resumo, como pesquisar imagens semelhantes?
No estágio inicial do projeto, não encontrei uma ferramenta satisfatória (ou um mecanismo de computação) que pudesse calcular rapidamente a distância de Hamming. Então mudei meu plano.
Minha ideia é que, se a distância de Hamming de dois valores pHash for pequena, então posso cortar os valores pHash e as pequenas partes correspondentes provavelmente serão iguais.
Por exemplo:
Valor 1： 8 a 0 3 0 3 f 6
Valor 2： 8 a 0 3 0 3 d 8
Dividimos os dois valores acima em oito segmentos e os valores de seis segmentos são exatamente iguais. Pode-se inferir que sua distância de Hamming é próxima e, portanto, essas duas imagens são semelhantes.
Após a transformação, você pode perceber que o problema de calcular a distância de Hamming se tornou um problema de correspondência por equivalência. Se eu dividir cada valor pHash em oito segmentos, desde que haja mais de cinco segmentos com valores exatamente iguais, então os dois valores pHash são semelhantes.
Assim, é muito simples resolver a correspondência por equivalência. Podemos usar a filtragem clássica de um sistema de banco de dados tradicional.
Claro, uso a correspondência de múltiplos termos e especifico o grau de correspondência usando minimum_should_match no ElasticSearch (este artigo não apresenta o princípio do ES; você pode aprendê-lo por conta própria).
Por que escolhemos ElasticSearch? Primeiro, ele fornece a função de pesquisa mencionada acima. Segundo, o próprio projeto de gerenciador de imagens está usando ES para fornecer uma função de pesquisa de texto completo, e é muito econômico usar os recursos existentes.
Resumo do sistema de primeira geração
O sistema de pesquisa por imagem de primeira geração escolhe a solução pHash + ElasticSearch, que possui as seguintes características:
- O algoritmo pHash é simples de usar e pode resistir a um certo grau de compressão, marca d’água e ruído.
- ElasticSearch usa os recursos existentes do projeto sem adicionar custos adicionais à pesquisa.
Mas a limitação deste sistema é óbvia: o algoritmo pHash é uma representação abstrata da imagem inteira. Uma vez que destruímos a integridade da imagem, como adicionar uma borda preta à imagem original, é quase impossível julgar a similaridade entre a original e as outras.
Para superar tais limitações, surgiu o sistema de pesquisa de imagens de segunda geração com uma tecnologia subjacente completamente diferente.
Este artigo foi escrito por rifewang, usuário do Milvus e engenheiro de software da UPYUN. Se você gostou deste artigo, fique à vontade para vir dizer oi! https://github.com/rifewang
Continue lendo
Zilliz Cloud Update: Smarter Autoscaling for Cost Savings, Stronger Compliance with Audit Logs, and More
What's new in Zilliz Cloud? Smarter autoscaling with scale-down, audit logs GA, enhanced SSO, and Milvus 2.6 in Private Preview.
How to Build RAG with Milvus, QwQ-32B and Ollama
Hands-on tutorial on how to create a streamlined, powerful RAG pipeline that balances efficiency, accuracy, and scalability using the QwQ-32B and Milvus.
Milvus WebUI: A Visual Management Tool for Your Vector Database
Explore Milvus WebUI to monitor, manage, and optimize your vector database with real-time insights, performance tracking, and system health monitoring.