Efficient retrieval of near-duplicate images

Abstract

Aufgrund der kontinuierlich steigenden Menge an digitalen Bildern und dem ständigen Wachstum an verfügbarer Speicherkapazität, sind umfangreiche Bilddatenbanken weit verbreitet. Die Verwaltung einer großen Menge an digitalen Bildern ist jedoch nicht trivial und mit diversen Problemen verbunden. Eine spezielle Herausforderung ist eine Bilddatenbank auf nahezu identische Bilder zu durchsuchen. Als nahezu identisches Bild bezeichnet man jede veränderte Version, bei der das ursprüngliche Bild bestimmten Transformationen unterworfen wurde. Dies bedeutet, dass ein dafür konzipiertes System Bilder als Suchanfragen akzeptiert und gegebenenfalls entsprechende Originale zurückliefert. Die Schwierigkeit dabei ist eine Bildrepräsentation zu finden die robust in Bezug auf diese Transformationen ist. Gleichzeitig soll die Ähnlichkeit zweier Repräsentationen effizient zu berechnen sein oder die Repräsentationen sollten indizierbar sein. Im ersten Fall kann die Datenbank linear durchsucht werden, während im zweiten Fall eine effiziente Suchstruktur aufgebaut werden kann. Die Bags of Visual Words Methode, in Analogie zu der Bags of Words Methode für die Textdokument-Suche, hat sich als geeignet herausgestellt. Dabei wird ein Bild duch die Häufigkeiten seiner enthaltenen visuellen Worte beschrieben. Diese visuellen Worte werden von lokalen Bildmerkmalen abgeleitet. Methoden auf dem aktuellen Stand derWissenschaft verwenden SIFT Merkmale, welche den Nachteil einer aufwendigen Berechnung haben. Um dem entgegenzuwirken werden in dieser Arbeit SIFT Merkmale durch binäre Merkmale ersetzt. Binäre Merkmale bestehen aus einer einfachen Liste an Bits und ermöglichen bestimmte Schritte der Bags of Visual Words Methode effizienter durchzuführen. Das Erzeugen der visuellen Worte ist einer dieser Schritte und äußerst zeitaufwändig. Ein alternativer Clustering-Algorithmus, kShifts, wird untersucht, um diesen Schritt effizienter durchzuführen. Weiters wird der kMeans Algorithmus für binäre Merkmale angepasst und mit kShifts verglichen. Für die Evaluierung des vorgestellten Systems werden frei verfügbare Bilddatenbanken verwendet. Ein Vergleich mit aktuellen Methoden wird gezogen. Zusätzlich wird eine Bilddatenbank mit circa 1,000,000 Pressebildern als praxisorientierter Anwendungsfall untersucht.

Due to the increasing flood of digital images and the overall increase of storage capacity, large scale image databases are common these days. Managing such a vast number of digital images is not trivial and certain problems arise. A specific problem is the task of finding near-duplicate images in such image databases. A near-duplicate image is not only a bit exact copy of a given original image, but also a modified version of the image after specific image manipulations. Practically this means a near-duplicate image retrieval system can be seen as a database that can be queried with images and retrieves corresponding originals. The challenge is to develop image descriptions that are robust to said image manipulations. Furthermore a similarity measure for image descriptions is needed. This similarity should either be calculable very fast or image descriptions should be indexable. In the first case linear database scans are applicable, while in the second case an efficient search structure can be built. The Bags of Visual Words method, in analogy to the Bags of Words method in text document retrieval, has proven to be particularly suited. It represents every image as a set of visual word frequencies, which correspond to keyword frequencies. A visual word is derived from a local visual feature. State of the art methods often rely on SIFT features which have the drawback of relatively high computational costs. To overcome this drawback recently introduced binary features are considered as replacement in this thesis. Binary features are simply bit strings and allow to process several steps of the Bags of Visual Words method more efficiently. Generating visual words with sufficient precision is very time consuming and an alternative clustering algorithm, called kShifts, is examined in this thesis. Furthermore the established kMeans algorithm is adapted to cluster binary features and compared with the kShifts algorithm. For evaluation the implemented algorithm is tested with commonly available image sets and compared with state of the art methods. Additionally a specific use-case in the form of a press image set consisting of approximately 1,000,000 high quality press images is studied. The most common image transform occurring in this context is cropping and therefore a specialized similarity measure is introduced.