🚀 Essayez Zilliz Cloud, la version entièrement gérée de Milvus, gratuitement—découvrez des performances 10x plus rapides ! Essayez maintenant>>

milvus-logo
LFAI

Vue d'ensemble

  • Scenarios
August 04, 2020
Rife Wang

Yupoo Picture Manager sert des dizaines de millions d'utilisateurs et gère des dizaines de milliards d'images. Comme sa galerie d'utilisateurs s'agrandit, Yupoo a un besoin urgent d'une solution capable de localiser rapidement l'image. En d'autres termes, lorsqu'un utilisateur saisit une image, le système doit trouver l'image originale et les images similaires dans la galerie. Le développement du service de recherche par image fournit une approche efficace de ce problème.

Le service de recherche par image a connu deux évolutions :

  1. Début de la première enquête technique au début de 2019 et lancement du système de première génération en mars et avril 2019 ;
  2. Début de l'étude du plan de mise à niveau au début de 2020 et lancement de la mise à niveau globale vers le système de deuxième génération en avril 2020.

Cet article décrit la sélection de la technologie et les principes de base des deux générations de système de recherche par image en se basant sur ma propre expérience de ce projet.

Vue d'ensemble

Qu'est-ce qu'une image ?

Nous devons savoir ce qu'est une image avant de traiter des images.

La réponse est qu'une image est un ensemble de pixels.

Par exemple, la partie dans la boîte rouge sur cette image est virtuellement une série de pixels.

1-what-is-an-image.png 1-qu'est-ce-qu'une-image.png

Supposons que la partie dans l'encadré rouge soit une image, alors chaque petit carré indépendant dans l'image est un pixel, l'unité d'information de base. La taille de l'image est donc de 11 x 11 px.

2-what-is-an-image.png 2-qu'est-ce-qu'une-image.png

Représentation mathématique des images

Chaque image peut être représentée par une matrice. Chaque pixel de l'image correspond à un élément de la matrice.

Images binaires

Les pixels d'une image binaire sont soit noirs, soit blancs, de sorte que chaque pixel peut être représenté par 0 ou 1. Par exemple, la représentation matricielle d'une image binaire 4 * 4 est la suivante :

0 1 0 1
1 0 0 0
1 1 1 0
0 0 1 0

Images RVB

Les trois couleurs primaires (rouge, vert et bleu) peuvent être mélangées pour produire n'importe quelle couleur. Pour les images RVB, chaque pixel possède les informations de base de trois canaux RVB. De même, si chaque canal utilise un nombre de 8 bits (en 256 niveaux) pour représenter son échelle de gris, la représentation mathématique d'un pixel est la suivante :

([0 .. 255], [0 .. 255], [0 .. 255])

Prenons l'exemple d'une image RVB 4 * 4 :

3-4-x-4-rgb-image.png 3-4-x-4-rgb-image.png

L'essence du traitement d'images consiste à traiter ces matrices de pixels.

Le problème technique de la recherche par image

Si vous recherchez l'image originale, c'est-à-dire une image comportant exactement les mêmes pixels, vous pouvez comparer directement leurs valeurs MD5. Toutefois, les images téléchargées sur l'internet sont souvent compressées ou marquées d'un filigrane. Même un petit changement dans une image peut créer un résultat MD5 différent. Tant qu'il y a des incohérences entre les pixels, il est impossible de retrouver l'image originale.

Pour un système de recherche par image, nous voulons rechercher des images dont le contenu est similaire. Nous devons donc résoudre deux problèmes fondamentaux :

  • Représenter ou abstraire une image dans un format de données qui peut être traité par un ordinateur.
  • Les données doivent être comparables pour le calcul.

Plus précisément, nous avons besoin des caractéristiques suivantes :

  • Extraction des caractéristiques de l'image.
  • Calcul des caractéristiques (calcul de similarité).

Le système de recherche par image de première génération

Extraction des caractéristiques - abstraction de l'image

Le système de recherche par image de première génération utilise l'algorithme de hachage perceptuel ou pHash pour l'extraction des caractéristiques. Quels sont les principes de base de cet algorithme ?

4-first-generation-image-search.png 4-recherche-d'images-de-première-generation.png

Comme le montre la figure ci-dessus, l'algorithme pHash effectue une série de transformations sur l'image pour obtenir la valeur de hachage. Au cours du processus de transformation, l'algorithme fait continuellement abstraction des images, ce qui rapproche les résultats des images similaires.

Calcul des caractéristiques - calcul de la similarité

Comment calculer la similarité entre les valeurs de pHash de deux images ? La réponse est l'utilisation de la distance de Hamming. Plus la distance de Hamming est petite, plus le contenu des images est similaire.

Qu'est-ce que la distance de Hamming ? C'est le nombre de bits différents.

Par exemple, il y a deux bits différents dans l'image ci-dessus,

Value 1: 0 1 0 1 0
Value 2: 0 0 0 1 1

Il y a deux bits différents dans les deux valeurs ci-dessus, la distance de Hamming entre elles est donc de 2.

Nous connaissons maintenant le principe du calcul de la similarité. La question suivante est de savoir comment calculer les distances de Hamming entre des données à 100 millions d'échelles et des images à 100 millions d'échelles. En bref, comment rechercher des images similaires ?

Au début du projet, je n'ai pas trouvé d'outil satisfaisant (ou de moteur de calcul) capable de calculer rapidement la distance de Hamming. J'ai donc modifié mon plan.

Mon idée est que si la distance de Hamming entre deux valeurs de pHash est faible, alors je peux couper les valeurs de pHash et les petites parties correspondantes seront probablement égales.

Par exemple :

Value 1: 8 a 0 3 0 3 f 6
Value 2: 8 a 0 3 0 3 d 8

Nous divisons les deux valeurs ci-dessus en huit segments et les valeurs de six segments sont exactement les mêmes. On peut en déduire que leur distance de Hamming est proche et que ces deux images sont donc similaires.

Après la transformation, vous pouvez constater que le problème du calcul de la distance de Hamming est devenu un problème d'équivalence de correspondance. Si je divise chaque valeur de pHash en huit segments, tant qu'il y a plus de cinq segments qui ont exactement les mêmes valeurs, alors les deux valeurs de pHash sont similaires.

Il est donc très simple de résoudre la question de l'équivalence. Nous pouvons utiliser le filtrage classique d'un système de base de données traditionnel.

Bien sûr, j'utilise la correspondance multiterme et je spécifie le degré de correspondance en utilisant minimum_should_match dans ElasticSearch (cet article ne présente pas le principe d'ES, vous pouvez l'apprendre par vous-même).

Pourquoi choisir ElasticSearch ? Tout d'abord, il fournit la fonction de recherche mentionnée ci-dessus. Deuxièmement, le projet de gestionnaire d'images utilise lui-même ES pour fournir une fonction de recherche plein texte et il est très économique d'utiliser les ressources existantes.

Résumé du système de première génération

Le système de recherche par image de première génération choisit la solution pHash + ElasticSearch, qui présente les caractéristiques suivantes :

  • L'algorithme pHash est simple à utiliser et peut résister à un certain degré de compression, de filigrane et de bruit.
  • ElasticSearch utilise les ressources existantes du projet sans ajouter de coûts supplémentaires à la recherche.
  • Mais la limite de ce système est évidente : l'algorithme pHash est une représentation abstraite de l'image entière. Dès que nous détruisons l'intégrité de l'image, par exemple en ajoutant une bordure noire à l'image originale, il est presque impossible de juger de la similitude entre l'original et les autres.

C'est pour dépasser ces limites qu'est apparu le système de recherche d'images de deuxième génération, qui repose sur une technologie sous-jacente totalement différente.

Cet article a été rédigé par rifewang, utilisateur de Milvus et ingénieur logiciel d'UPYUN. Si vous aimez cet article, n'hésitez pas à venir lui dire bonjour ! https://github.com/rifewang

Like the article? Spread the word

Continuer à Lire