Τεχνικές Ομαδοποίησης Και Κοντινότερου Γείτονα Για Οπτική Αναζήτηση Εικόνων

Abstract

Στην παρούσα εργασία προτείνονται βελτιώσεις στην οπτική αναζήτηση εικόνων, με τεχνικές που βασίζονται κυρίως σε ομαδοποίηση. Η ομαδοποίηση εκτελείται είτε στο χώρο των χαρακτηριστικών είτε στο χώρο των εικόνων, σε πολυδιάστατους διανυσματικούς ή μετρικούς χώρους, αντίστοιχα.Αρχικά προτείνουμε μια νέα, γενικότερη μέθοδο ομαδοποίησης, η οποία συνδυάζει την περιγραφική δύναμη των μοντέλων μείγματος κανονικών κατανομών με τις ιδιότητες που απαιτούνται κατά την κατασκευή μεγάλης κλίμακας οπτικών λεξικών για αναζήτηση εικόνων. Είναι μια παραλλαγή του αλγορίθμου expectation-maximization που μπορεί να συγκλίνει γρήγορα, ενώ παράλληλα μπορεί να εκτιμήσει δυναμικά τον τελικό αριθμό των συνιστωσών. Επιστρατεύουμε τεχνικές προσεγγιστικών κοντινότερων γειτόνων για την επιτάχυνση του E-step του αλγορίθμου EM και εκμεταλλευόμαστε την επαναληπτική του φύση για να κάνουμε την αναζήτηση αυξητική, βελτιώνοντας την ταχύτητα αλλά και την ακρίβεια. Καταλήγουμε να έχουμε απόδοση υψηλότερη από το state of the art της αναζήτησης σε μεγάλες βάσεις εικόνων, ενώ είμαστε ταυτόχρονα το ίδιο γρήγοροι με τις πλέον γρήγορες γνωστές τεχνικές κατασκευής οπτικών λεξικών.Έπειτα, παρουσιάζουμε μια νέα μέθοδο για αναζήτηση κοντινότερου γείτονα, μια μέθοδο που βελτιστοποιεί παραγοντικούς κβαντιστές τοπικά και έτσι μειώνει σημαντικά την παραμόρφωση κατά τον κβαντισμό. Αν συνδυαστεί με τη μέθοδο δεικτοδότησης multi-index, καταφέρνει να ξεπεράσει τα μέχρι τώρα καλύτερα δημοσιευμένα αποτελέσματα στην αναζήτηση κοντινότερου γείτονα σε ένα σύνολο με ένα δισεκατομμύριο πολυδιάστατα σημεία. Παράλληλα απολαμβάνει ταχύτητες αναζήτησης της τάξεως των λίγων millisecond, γεγονός που την καθιστά ανταγωνιστική ως προς το χρόνο ακόμα και σε σχέση με μεθόδους κατακερματισμού(hashing).Προτείνουμε επίσης τους χάρτες σκηνών και θα δείξουμε ότι μια εκ των προτέρων ομαδοποίηση των εικόνων της συλλογής μπορεί να βελτιώσει την απόδοση της οπτικής αναζήτησης, ενώ παράλληλα ένα κριτήριο παραμόρφωσης μπορεί να εγγυηθεί την ανάκτηση ακόμα και απομονωμένων εικόνων από μη δημοφιλής τοποθεσίες όπως σε ένα γενικό σύστημα αναζήτησης εικόνων. Προτείνουμε μια λύση που παρότι μπορεί να δουλέψει σε συλλογές εκατομμυρίων εικόνων, μπορεί να ανακτήσει ακόμα και τις μη δημοφιλής εικόνες απαιτώντας μονάχα ένα ποσοστό της αρχικής μνήμης.Παρουσιάσουμε τέλος ένα ολοκληρωμένο σύστημα αναζήτησης εικόνων, το οποίο μπορεί να χρησιμοποιηθεί για αυτόματο γεωγραφικό εντοπισμό καθώς και για αναγνώριση οροσήμων ή σημείων ενδιαφέροντος, όπου αυτό είναι εφικτό. Το VIRaL (Visual Image Retrieval and Localization) παρέχει δημόσια πρόσβαση στις προαναφερθείσες τεχνολογίες μέσω ενός ενοποιημένου γραφικού διαδικτυακού περιβάλλοντος. Η διατριβή καταλήγει με τη συνοπτική περιγραφή μερικών ακόμα δημοσιεύσεων που εστιάζουν σε εφαρμογές της οπτικής αναζήτησης καθώς και τα συμπεράσματα της έρευνας.