Der Weg zur Optimierung der Bildsuche im Milliardenmaßstab (1/2)
Yupoo Picture Manager bedient zig Millionen Nutzer und verwaltet zig Milliarden Bilder. Da die Nutzergalerie immer größer wird, hat Yupoo einen dringenden geschäftlichen Bedarf an einer Lösung, die das Bild schnell lokalisieren kann. Mit anderen Worten: Wenn ein Nutzer ein Bild eingibt, sollte das System dessen Originalbild und ähnliche Bilder in der Galerie finden. Die Entwicklung des Search-by-Image-Dienstes bietet einen effektiven Ansatz für dieses Problem.
Der Search-by-Image-Dienst hat zwei Entwicklungen durchlaufen:
- Beginn der ersten technischen Untersuchung Anfang 2019 und Einführung des Systems der ersten Generation im März und April 2019;
- Beginn der Untersuchung des Upgrade-Plans Anfang 2020 und Start des gesamten Upgrades auf das System der zweiten Generation im April 2020.
Dieser Artikel beschreibt die Technologieauswahl und die grundlegenden Prinzipien hinter den beiden Generationen des Search-by-Image-Systems basierend auf meiner eigenen Erfahrung in diesem Projekt.
Überblick
Was ist ein Bild?
Wir müssen wissen, was ein Bild ist, bevor wir mit Bildern umgehen.
Die Antwort lautet, dass ein Bild eine Sammlung von Pixeln ist.
Zum Beispiel ist der Teil im roten Kasten auf diesem Bild praktisch eine Reihe von Pixeln.
Abbildung 1.
Angenommen, der Teil im roten Kasten ist ein Bild, dann ist jedes unabhängige kleine Quadrat im Bild ein Pixel, die grundlegende Informationseinheit. Dann beträgt die Größe des Bildes 11 x 11 px.
Abbildung 2.
Mathematische Darstellung von Bildern
Jedes Bild kann durch eine Matrix dargestellt werden. Jedes Pixel im Bild entspricht einem Element in der Matrix.
Binärbilder
Die Pixel eines Binärbildes sind entweder schwarz oder weiß, sodass jedes Pixel durch 0 oder 1 dargestellt werden kann. Zum Beispiel lautet die Matrixdarstellung eines 4 * 4-Binärbildes:
0 1 0 1
1 0 0 0
1 1 1 0
0 0 1 0
RGB-Bilder
Die drei Primärfarben (Rot, Grün und Blau) können gemischt werden, um jede beliebige Farbe zu erzeugen. Bei RGB-Bildern hat jedes Pixel die grundlegenden Informationen von drei RGB-Kanälen. Wenn jeder Kanal ähnlich dazu eine 8-Bit-Zahl (in 256 Stufen) verwendet, um seine Grauskala darzustellen, dann lautet die mathematische Darstellung eines Pixels:
([0 .. 255], [0 .. 255], [0 .. 255])
Nehmen wir ein 4 * 4-RGB-Bild als Beispiel:
Abbildung 3.
Das Wesen der Bildverarbeitung besteht darin, diese Pixelmatrizen zu verarbeiten.
Das technische Problem von Search by Image
Wenn Sie nach dem Originalbild suchen, also nach einem Bild mit exakt denselben Pixeln, können Sie deren MD5-Werte direkt vergleichen. Bilder, die ins Internet hochgeladen werden, werden jedoch häufig komprimiert oder mit Wasserzeichen versehen. Schon eine kleine Änderung an einem Bild kann ein anderes MD5-Ergebnis erzeugen. Sobald es eine Abweichung bei den Pixeln gibt, ist es unmöglich, das Originalbild zu finden.
Für ein Search-by-Image-System möchten wir nach Bildern mit ähnlichem Inhalt suchen. Dann müssen wir zwei grundlegende Probleme lösen:
- Ein Bild als ein Datenformat darstellen oder abstrahieren, das von einem Computer verarbeitet werden kann.
- Die Daten müssen für Berechnungen vergleichbar sein.
Genauer gesagt benötigen wir die folgenden Funktionen:
- Bildmerkmalsextraktion.
- Merkmalsberechnung (Ähnlichkeitsberechnung).
Das Search-by-Image-System der ersten Generation
Merkmalsextraktion — Bildabstraktion
Das Search-by-Image-System der ersten Generation verwendet den Perceptual-Hash- oder pHash-Algorithmus zur Merkmalsextraktion. Was sind die Grundlagen dieses Algorithmus?
Bildsuche der ersten Generation.
Wie in der obigen Abbildung gezeigt, führt der pHash-Algorithmus eine Reihe von Transformationen am Bild durch, um den Hash-Wert zu erhalten. Während des Transformationsprozesses abstrahiert der Algorithmus die Bilder kontinuierlich und bringt dadurch die Ergebnisse ähnlicher Bilder näher zusammen.
Merkmalsberechnung — Ähnlichkeitsberechnung
Wie berechnet man die Ähnlichkeit zwischen den pHash-Werten zweier Bilder? Die Antwort ist die Verwendung der Hamming-Distanz. Je kleiner die Hamming-Distanz, desto ähnlicher ist der Inhalt der Bilder.
Was ist die Hamming-Distanz? Sie ist die Anzahl der unterschiedlichen Bits.
Zum Beispiel,
Wert 1： 0 1 0 1 0
Wert 2： 0 0 0 1 1
In den beiden obigen Werten gibt es zwei unterschiedliche Bits, daher beträgt die Hamming-Distanz zwischen ihnen 2.
Jetzt kennen wir das Prinzip der Ähnlichkeitsberechnung. Die nächste Frage ist: Wie berechnet man die Hamming-Distanzen von Daten im 100-Millionen-Maßstab aus Bildern im 100-Millionen-Maßstab? Kurz gesagt: Wie sucht man nach ähnlichen Bildern?
In der frühen Phase des Projekts fand ich kein zufriedenstellendes Tool (oder eine Computing-Engine), das die Hamming-Distanz schnell berechnen kann. Also änderte ich meinen Plan.
Meine Idee ist: Wenn die Hamming-Distanz zweier pHash-Werte klein ist, kann ich die pHash-Werte aufteilen, und die entsprechenden kleinen Teile sind wahrscheinlich gleich.
Zum Beispiel:
Wert 1： 8 a 0 3 0 3 f 6
Wert 2： 8 a 0 3 0 3 d 8
Wir teilen die obigen beiden Werte in acht Segmente auf, und die Werte von sechs Segmenten sind genau gleich. Daraus lässt sich ableiten, dass ihre Hamming-Distanz nahe beieinander liegt und diese beiden Bilder somit ähnlich sind.
Nach der Transformation können Sie feststellen, dass das Problem der Berechnung der Hamming-Distanz zu einem Problem des Gleichheitsabgleichs geworden ist. Wenn ich jeden pHash-Wert in acht Segmente aufteile, sind die beiden pHash-Werte ähnlich, solange es mehr als fünf Segmente gibt, die exakt dieselben Werte haben.
Daher ist es sehr einfach, den Gleichheitsabgleich zu lösen. Wir können die klassische Filterung eines traditionellen Datenbanksystems verwenden.
Natürlich verwende ich das Multi-Term-Matching und gebe den Übereinstimmungsgrad mit minimum_should_match in ElasticSearch an (dieser Artikel stellt das Prinzip von ES nicht vor, Sie können es selbst lernen).
Warum wählen wir ElasticSearch? Erstens bietet es die oben erwähnte Suchfunktion. Zweitens verwendet das Image-Manager-Projekt selbst ES, um eine Volltextsuchfunktion bereitzustellen, und es ist sehr wirtschaftlich, die vorhandenen Ressourcen zu nutzen.
Zusammenfassung des Systems der ersten Generation
Das Search-by-Image-System der ersten Generation wählt die Lösung pHash + ElasticSearch, die folgende Merkmale aufweist:
- Der pHash-Algorithmus ist einfach zu verwenden und kann einem gewissen Grad an Kompression, Wasserzeichen und Rauschen widerstehen.
- ElasticSearch nutzt die vorhandenen Ressourcen des Projekts, ohne zusätzliche Kosten für die Suche zu verursachen.
Die Einschränkung dieses Systems ist jedoch offensichtlich: Der pHash-Algorithmus ist eine abstrakte Darstellung des gesamten Bildes. Sobald wir die Integrität des Bildes zerstören, zum Beispiel indem wir dem Originalbild einen schwarzen Rand hinzufügen, ist es fast unmöglich, die Ähnlichkeit zwischen dem Original und den anderen zu beurteilen.
Um solche Einschränkungen zu überwinden, entstand das Bildsuchsystem der zweiten Generation mit einer völlig anderen zugrunde liegenden Technologie.
Dieser Artikel wurde von rifewang, Milvus-Nutzer und Softwareingenieur bei UPYUN, verfasst. Wenn Ihnen dieser Artikel gefällt, kommen Sie gern vorbei und sagen Sie hallo! https://github.com/rifewang
Weiterlesen
From Vector Database to Vector Lakebase
Zilliz offers a fully managed Vector Lakebase powered by Milvus, unifying real-time vector search, lake-scale discovery, and Al data operations.
Zilliz Skills Breakdown: How AI Agents Master Vector Databases
Zilliz's Milvus Skill (pymilvus, 7 files) and Zilliz Cloud Skill (zilliz-cli, 14 modules) bring vector-DB dev and ops into one Claude Code session.
Proactive Monitoring for Vector Database: Zilliz Cloud Integrates with Datadog
we're excited to announce Zilliz Cloud's integration with Datadog, enabling comprehensive monitoring and observability for your vectorDB deployments.