Das INRIA entwickelt einen effizienten Algorithmus zur schnelleren Bildersuche

PQ-Codes kann ein Bild auf eine sehr kleine Anzahl von Merkmalen reduzieren, die nur wenige Bytes in Anspruch nehmen. Ziel ist es, die Rechenzeit zu verkürzen, um so schnell wie möglich relevante Ergebnisse zu erhalten.

Um Fotomontagen aufzuspüren, wurde bislang auf Bildersuchmaschinen (wie z.B. TinEye oder Cydral) zurückgegriffen, die alle Kopien und Veränderungen eines Bildes oder Videos im Web suchen. Ihre Algorithmen basieren auf der Analyse von Bild-Pixeln, um so deren Eigenschaften herauszufiltern. Jedoch nehmen diese Berechnungen viel Zeit in Anspruch und sind eine Herausforderung für den Server. Außerdem sind die Ergebnisse im Verhältnis zum hohen Aufwand an Rechenleistung nicht unbedingt zufriedenstellend.

Hervé Jegou, Forscher am INRIA, hat sich mit seinem Projekt “PQ-Codes” genau diesem Problem des Rechenaufwands gewidmet. Mit PQ-Codes dauert es nur 20 Millisekunden, um eine illegale (oder veränderte) Kopie eines Fotos oder Videos in einer 10 Millionen Dateien umfassenden Datenbank aufzuspüren! Im Gegensatz zu Systemen, die auf der Pixelanalyse basieren, erstellt PQ-Codes eine mathematische Darstellung des Bildes. Das Programm filtert eine bestimmte Menge charakteristischer Merkmale des Bildes heraus.
Diese erzeugen eine Reihe von Vektoren und der daraus resultierende Algorithmus wählt einen charakteristischen “Supervektor” für das Bild aus. Er ist nicht ganz so genau, aber ausreichend, um ein einzigartiges Merkmal des Bildes herauszufiltern. (Diese Technik nennt sich “Vektorquantisierung” und wird auch in der Spracherkennung angewandt).

Mit dieser Methode, die die Pixel und Farben unberücksichtigt lässt, können die Eigenschaften eines Bildes mit nur 20 Bytes definiert werden, was einen deutlichen Zugewinn an Rechenzeit bedeutet. Letztlich werden zwei Bilder nur anhand ihrer beiden Supervektoren verglichen. Veränderte Bilder oder raubkopierte Videos von schlechter Qualität können so unter Millionen anderer identifiziert werden.

In der Praxis könnte diese Technologie in die von uns täglich genutzten Suchmaschinen integriert werden. Bislang hat ein Großunternehmen eine Lizenz erworben und andere haben bereits ihr Interesse bekundet. Mehrere Industrie- und Forschergruppen (ETZH, NTT, Xeroxn,…) haben diese Technik für ihre eigenen Bedürfnisse neu implementiert.

Quelle:
– Artikel aus Futura-science – 13.01.2012 – http://www.futura-sciences.com/fr/news/t/internet/d/pq-codes-le-plus-rapide-pour-retrouver-une-image-parmi-des-millions_35914/#xtor=RSS-8

Redakteur: Charles Collet, charles.collet@diplomatie.gouv.fr