Efficient Retrieval of Web Content with Distinctive Visual Vocabularies:
Creators: name: Καστρινάκης, Δημήτριος Επαμεινώνδα
Publisher: name: Aristotle University of Thessaloniki
Year: 2012
Subjects: Εικόνες
Κβάντιση
Ευρετηρίαση
Images
Quantization
Indexing

description: Η ανάκτηση εικόνων αποτελεί ένα διαρκώς αναπτυσσόμενο πεδίο έρευνας, προτείνοντας νέες λύσεις και βελτιώνοντας τις ήδη υπάρχουσες καθώς οι χρήστες αποκτούν πρόσβαση σε μεγάλο όγκο δεδομένων και μετα-δεδομένων στον Παγκόσμιο Ιστό. Τεχνολογίες για το Web 2.0 επιτρέπουν τη δημιουργία, δημοσίευση και διαμοιρασμό πληροφορίας μεταξύ συνδεδεμένων φίλων, αντί για την παθητική κατανάλωση πληροφορίας που ίσχυε μέχρι τις αρχές της προηγούμενης δεκαετίας. Για παράδειγμα, το Flickr φιλοξενεί δισεκατομμύρια φωτογραφίες χρηστών, διαθέσιμες για αναζήτηση, επισκόπηση, προσάρτηση μετα-δεδομένων (tagging) και διαμοιρασμό. Ο ευρετηριασμός μιας συλλογής εικόνων τέτοιου μεγέθους είναι συνήθως ένα δύσκολο και μη τετριμμένο εγχείρημα. Η κατασκευή ενός ευρετηρίου προς μελλοντική ανάκτηση βάσει του μοντέλου bag-of-visual-words υλοποιείται σε τρία βασικά βήματα: (α) Την εξαγωγή τοπικών χαρακτηριστικών (local features) από μια συλλογή εικόνων και αποθήκευσή τους στο σύστημα αρχείων ή σε βάση δεδομένων. Κάθε εικόνα δίδεται ως είσοδος σε έναν κατάλληλο αλγόριθμο και εξάγεται ένα σύνολο από περιγραφείς (descriptors). Ένας τοπικός περιγραφέας είναι ένα πολυδιάστατο διάνυσμα που περιγράφει με χαρακτηριστικό τρόπο το σημείο ενδιαφέροντος όπου ανήκει. Ένα σημείο ενδιαφέροντος είναι μια μικρή περιοχή που περικλείει κάποια άκρη ή γωνία στην εικόνα. Στην περίπτωση των καθολικών χαρακτηριστικών (global features), για κάθε εικόνα εξάγεται ένας περιγραφέας που μπορεί να περιγράφει χρώμα, υφή και σχήμα. (β) Την κβάντιση (quantization) του χώρου των χαρακτηριστικών για την παραγωγή «οπτικών λέξεων» (visual words) και τελικά την κατασκευή του «οπτικού λεξιλογίου» (visual vocabulary). Συχνά, αυτό επιτυγχάνεται με την εφαρμογή κάποιας μεθόδου ομαδοποίησης στο σύνολο των δεδομένων των χαρακτηριστικών, όπως ο k-means, η οποία είναι μια ακριβή διαδικασία, καθώς τα διανύσματα χαρακτηριστικών μπορεί εύκολα να ανέλθουν σε εκατομμύρια. (γ) Την ευρετηρίαση (indexing) κάθε εικόνας στη συλλογή ως ένα έγγραφο οπτικών λέξεων, ανάγοντας το εν λόγω πρόβλημα σε ανάκτηση κειμένου. Για κάθε χαρακτηριστικό στην εικόνα, επιλέγεται η εγγύτερη οπτική λέξη, εν τέλει διαμορφώνοντας ένα σάκο από οπτικές λέξεις για κάθε εικόνα. Βεβαίως, το (γ) δεν υιοθετείται πάντοτε: υπάρχουν άλλες προσεγγίσεις που βασίζονται σε παραγόμενα ιστογράμματα για κάθε εικόνα, χρησιμοποιώντας την Ευκλείδεια απόσταση μεταξύ διανυσμάτων εικόνων. Σε αυτήν την εργασία, προτείνουμε μια νέα μέθοδο που μειώνει σημαντικά τον απαιτούμενο χρόνο κβάντισης. Αντί για την παραγωγή εκατοντάδων χιλιάδων οπτικών λέξεων κατά το βήμα της κβάντισης, η παραγωγή μερικών μόνο οπτικών λέξεων αρκεί: περισσότερες από μία οπτικές λέξεις μπορούν να ανατεθούν σε ένα χαρακτηριστικό, ταξινομημένες κατα αύξουσα σειρά απόστασης, εφόσον ικανοποιούν ένα κατάλληλο κριτήριο απόστασης. Με αυτόν τον τρόπο, ένας εξυπηρετητής μπορεί να φιλοξενήσει ακόμη μεγαλύτερες συλλογές, ικανοποιώντας ερωτήματα σε λιγότερο χρόνο, διατηρώντας μια ικανοποιητική ακρίβεια ανάκτησης. Η αξιολόγηση του συστήματός μας πραγματοποιείται με συλλογές κοινωνικού περιεχομένου, υπολογίζοντας τη mean average precision της προτεινόμενης προσέγγισης και συγκρίνοντάς τη με την τυπική προσέγγιση. Επιπλέον, σχολιάζονται τα αποτελέσματα συγκεκριμένων ερωτημάτων και μετριέται ο χρόνος ευρετηριασμού και αναζήτησης.
description: Image retrieval is a constantly evolving field of research, proposing new solutions and improving existing ones as users have access to massive volumes of both data and meta-data on the Web. Technologies for the Web 2.0 allow users to create and publish their own information and share it with online friends, instead of just consuming information, which had been true for the previous decade. For example, Flickr hosts billions of user uploaded pictures, available for searching, browsing, tagging and sharing; indexing such a massive collection of images is usually an arduous and non-trivial task. Building an index for future retrieval based on the bag of words model consists of three major tasks: (a) local feature extraction from a collection of images and storage to the file system or a database. Each image is provided as input to an appropriate algorithm which extracts a set of descriptors. A local descriptor is a multidimensional vector which describes in a distinctive manner the point of interest (keypoint) it belongs to. The keypoint is a small area of the image which surrounds an edge or a corner. In the case of global features, a single descriptor is extracted from each image and it may describe color, texture or shape. (b) Quantization of the feature space to produce visual words, thus building the visual vocabulary. Often, this can be achieved by applying a clustering method to the feature set such as k-means, which is an expensive process, since the feature vectors can amount to millions. (c) Indexing each image in the collection as a document of visual words, reducing image retrieval to a text retrieval problem. For each feature vector in an image, the nearest visual word is kept, resulting in a bag of visual words for each image. However, (c) is not always adopted; there are other approaches that rely on a histogram representation of images and use the Euclidean distance between vectors of images. In this thesis, we propose a novel method that significantly decreases the time required for the quantization process. Instead of generating hundreds of thousands of visual words during the quantization step, only a few visual words suffice: multiple visual words can be assigned to a feature vector in ascending order of distance, as long as they pass an appropriately selected distance threshold. In this way, a server can host even larger collections and respond to queries in less time, while preserving an adequate retrieval quality. We evaluate our system using reference collections of social content by calculating the mean average precision of the proposed method and comparing it to the baseline. Moreover, ranked results for specific queries are discussed and the time consumed for indexing and querying is measured.