Welchen Algorithmus verwendet Google für seine Website "Suche nach Bild"?

45

Wie funktioniert die Google Bildsuche am besten? Ich kann ein Foto hochladen und nach ähnlichen Bildern suchen. Mit welchem ​​Algorithmus werden ähnliche Bilder identifiziert?

Cory
quelle
Sie können das Histogramm des Bildes speichern. Dies funktioniert für verschiedene Maßstäbe desselben Bildes und kleine Unterschiede aufgrund von Kompressionsartefakten oder was auch immer.
Helium
1
Histogramme erfassen keine räumlichen Informationen. Sie würden falsche Übereinstimmungen erhalten.
Emre
Neuronale Netze: research.googleblog.com/2015/06/…
endolith

Antworten:

29

Ich weiß nicht, welchen Algorithmus Google verwendet. Aber lassen Sie mich einige Ideen geben, wie ein ähnliches System aufgebaut werden könnte , da Sie eine bestmögliche Vermutung haben wollten .

Das gesamte Feld, das sich mit der Suche nach Bildern auf Basis von Bildern befasst, wird als Content Based Image Retrieval (CBIR) bezeichnet . Die Idee ist, irgendwie eine (für Menschen nicht unbedingt verständliche) Bilddarstellung zu konstruieren, die die Informationen über den Bildinhalt enthält .

Es gibt zwei grundlegende Ansätze:

  • Abrufen unter Verwendung von (lokalen) Merkmalen auf niedriger Ebene: Farbe, Textur, Form an bestimmten Teilen von Bildern (ein Bild ist eine Sammlung von Deskriptoren lokaler Merkmale)
  • semantische Ansätze, bei denen ein Bild in gewisser Weise als Sammlung von Objekten und ihren Beziehungen dargestellt wird

Der lokale Ansatz auf niedriger Ebene ist sehr gut erforscht. Der derzeit beste Ansatz extrahiert lokale Merkmale (es gibt eine Auswahl an Algorithmen zur Merkmalsextraktion) und verwendet ihre lokalen Deskriptoren (wiederum eine Auswahl an Deskriptoren), um die Bilder zu vergleichen.

In neueren Werken werden die lokalen Deskriptoren zuerst in Clustern zusammengefasst und dann als visuelle Wörter behandelt - die Technik ist dann der Google-Dokumentsuche sehr ähnlich, verwendet jedoch visuelle Wörter anstelle von Buchstabenwörtern.

Sie können sich visuelle Wörter als Äquivalente zu Wortwurzeln in der Sprache vorstellen: Zum Beispiel gehören die Wörter: arbeiten, arbeiten, gearbeitet alle zur selben Wortwurzel.

Einer der Nachteile dieser Arten von Verfahren ist, dass sie bei Bildern mit geringer Textur normalerweise nicht ausreichend funktionieren.

Ich habe bereits viele Antworten gegeben und gesehen, in denen diese Ansätze detailliert beschrieben sind, daher werde ich nur Links zu diesen Antworten bereitstellen:

  • CBIR: 1 , 2
  • Merkmalsextraktion / Beschreibung: 1 , 2 , 3 , 4

Semantische Ansätze basieren typischerweise auf hierarchischen Darstellungen des gesamten Bildes. Diese Ansätze wurden insbesondere für die allgemeinen Bildtypen noch nicht perfektioniert. Es ist ein gewisser Erfolg, diese Art von Techniken auf bestimmte Bilddomänen anzuwenden.

Da ich mich gerade in der Erforschung dieser Ansätze befinde, kann ich keine Schlussfolgerungen ziehen. Nun, das heißt, ich erklärte eine allgemeine Idee hinter diesen Techniken in dieser Antwort .

Noch einmal kurz: Die allgemeine Idee ist es, ein Bild mit einer baumförmigen Struktur darzustellen, wobei Blätter die Bilddetails enthalten und Objekte in den Knoten näher an der Wurzel solcher Bäume zu finden sind. Dann vergleichen Sie irgendwie die Teilbäume, um die in verschiedenen Bildern enthaltenen Objekte zu identifizieren.

Hier finden Sie einige Referenzen für verschiedene Baumdarstellungen. Ich habe nicht alle von ihnen gelesen, und einige von ihnen verwenden diese Art von Darstellungen zur Segmentierung anstelle von CBIR, aber dennoch sind sie hier:

Penelope
quelle
22

Neben der Antwort von penelope gibt es zwei Ansätze, Wahrnehmungs-Hashing und das Wortsack-Modell, dessen grundlegende Funktionalität leicht zu implementieren ist und mit denen man gut spielen oder daraus lernen kann, bevor man sich in ein fortgeschritteneres Gebiet wagt.

Wahrnehmungs-Hashing

Perzeptive Hashing-Algorithmen zielen darauf ab, einen Hash zu konstruieren, der im Gegensatz zu einem kryptografischen Hash ähnliche oder nahezu ähnliche Hash-Werte für identische Bilder liefert, die beispielsweise durch Skalierung oder JPEG-Komprimierung leicht verzerrt wurden. Sie erfüllen einen nützlichen Zweck bei der Erkennung in der Nähe von Duplikaten in einer Bildersammlung.

In der einfachsten Form können Sie dies folgendermaßen implementieren:

  1. Bild in Graustufen konvertieren

  2. Machen Sie aus Ihrem Bild einen Mittelwert von Null

  3. Zerkleinern Sie Ihr Bild auf die Miniaturbildgröße, sagen wir [32x32].
  4. Führen Sie die zweidimensionale diskrete Cosinustransformation aus
  5. Behalten Sie die oberen linken [8 x 8], wichtigsten Niederfrequenzkomponenten
  6. Binarisieren Sie den Block anhand des Vorzeichens der Komponenten

Das Ergebnis ist ein stabiler 64-Bit-Hash, da er auf den niederfrequenten Bildkomponenten basiert. Eine Variante zu diesem Thema wäre, jedes Bild in 64 Unterblöcke zu unterteilen und den globalen Bildmittelwert mit dem lokalen Unterblockmittelwert zu vergleichen und dementsprechend eine 1 oder 0 zu schreiben.

Perceptual Hashing wird zum Beispiel durch Phash implementiert

Bag-of-Words-Modell

Das Bag-of-Word-Modell zielt darauf ab, ein Bild semantisch zu identifizieren, z. B. alle Bilder mit Hunden darin. Dies geschieht durch die Verwendung bestimmter Bildausschnitte in dem Sinne, dass ein Textdokument anhand des Vorkommens bestimmter Wörter klassifiziert wird. Man könnte die Wörter kategorisieren, "Hund" und "Hunde" sagen und sie als Kennung in einer invertierten Datei speichern, wobei die Kategorie "Hund" nun auf alle Dokumente verweist, die entweder "Hund" oder "Hunde" enthalten.

In seiner einfachsten Form kann man dies mit Bildern wie folgt tun:

  1. Stellen Sie die sogenannten SIFT-Funktionen bereit , beispielsweise mithilfe der hervorragenden vlfeat- Bibliothek, die die SIFT-Funktionspunkte und einen SIFT-Deskriptor pro Punkt erkennt . Dieser Deskriptor ist im Grunde eine intelligent aufgebaute Schablone des diesen Merkmalspunkt umgebenden Bildfelds. Diese Deskriptoren sind Ihre rohen Wörter.
  2. Sammeln Sie SIFT-Deskriptoren für alle relevanten Bilder

Sie haben jetzt eine riesige Sammlung von SIFT-Deskriptoren. Das Problem ist, dass selbst bei nahezu identischen Bildern einige Deskriptoren nicht übereinstimmen. Sie möchten die identischen Wörter mehr oder weniger so gruppieren, als würden Sie einige Wörter als "Hund" und "Hunde" als identisch behandeln, und Sie müssen Fehler ausgleichen. Hier kommt das Clustering ins Spiel.

  1. Nehmen Sie alle SIFT-Deskriptoren und gruppieren Sie sie, zum Beispiel mit einem Algorithmus wie k-means. Dies findet eine vorher festgelegte Anzahl von Clustern mit Schwerpunkten in Ihren Deskriptordaten. Diese Schwerpunkte sind Ihre neuen visuellen Wörter.
  2. Jetzt können Sie pro Bild und den ursprünglich gefundenen Deskriptoren die Cluster anzeigen, denen diese Deskriptoren zugewiesen wurden. Daraus wissen Sie, welche Schwerpunkte oder visuellen Wörter zu Ihrem Bild gehören. Diese Schwerpunkte oder visuellen Wörter werden zum neuen semantischen Deskriptor Ihres Bildes, der in einer invertierten Datei gespeichert werden kann.

Eine Bildabfrage, zB finde ich ähnliche Bilder zum Query-Image, wird dann wie folgt gelöst:

  1. Suchen Sie die SIFT-Punkte und ihre Deskriptoren im Abfragebild
  2. Weisen Sie die Abfragedeskriptoren den Schwerpunkten zu, die Sie zuvor in der Registrierungsphase gefunden haben. Sie haben jetzt eine Reihe von Schwerpunkten oder visuellen Wörtern, die sich auf Ihr Abfragebild beziehen
  3. Ordnen Sie die visuellen Wörter der Abfrage visuellen Wörtern in Ihrer invertierten Datei zu und geben Sie die passenden Bilder zurück
Maurits
quelle
1
Ihr Bag-of-Word-Ansatz ist im Grunde das, wozu meine Links für den "lokalen Ansatz" führen :) Obwohl er nicht wirklich semantisch ist: Sie würden niemals einen einzelnen Hund mit einem Merkmal darstellen, und es wäre auch nicht so einfach, ihn zu identifizieren verschiedene Hundegewürze wie Hunde. Aber Wahrnehmungs-Hashing ist nett, wusste nichts darüber. Erklärungen sind nett. Was hat mich zum Nachdenken gebracht? Haben Sie Vorschläge, wie Sie diese Technik auf einen nicht rechteckigen Bereich anwenden können? Oder vielleicht einige Verweise auf Artikel, ich könnte ein wenig nachlesen und wenn die Frage Sinn macht, es als separate Frage öffnen.
Penelope
1
@penelope Ich habe vor Jahren tatsächlich in einem Artikel gelesen, in dem die Autoren ein Bild in willkürliche Dreiecke aufteilen. Und da ist die Trace-Transformation, die auch als Grundlage für einen Wahrnehmungs-Hash verwendet wurde. Ich melde mich bei dir.
Maurits
Alles, was ich Sie dazu fragen möchte, geht weit über den Rahmen dieser Frage hinaus, daher habe ich eine neue eröffnet. Weitere Informationen / Referenzen zur Basistechnik wären auch in dieser oder jener Antwort noch großartig. Ich freue mich :)
penelope
2

Der andere interessante Ansatz, der in den obigen Antworten vernachlässigt zu werden scheint, ist Deep Convolutional Neural Networks. Es scheint, dass Google es derzeit für seine Bildsuchmaschine und seinen Übersetzungsdienst verwendet . CNNs sind äußerst leistungsfähig bei kognitiven Aufgaben wie dem Auffinden von Ähnlichkeiten. Es scheint, dass CNN ein ähnliches Verfahren von Bag-of-Worlds durchführt, das durch seine Netzwerkschichten eingebettet ist. Der Nachteil dieser Techniken ist die Unfähigkeit, riesige Datenmengen für das Training zu verlernen und zu benötigen, und natürlich die hohen Rechenkosten auf der Trainingsstufe.

Vorgeschlagenes Papier zu diesem Thema:

und Open-Source-Implementierung zum Abrufen von Deep-Learning-Bildern (das spätere Dokument): https://github.com/paucarre/tiefvision

MimSaad
quelle