Αναζήτηση Εικόνων Με Γεωμετρικά Κριτήρια

Abstract

Ένα μεγάλο εύρος από ιδιότητες και υποθέσεις καθορίζουν το πιο κατάλληλο μοντέλο γεωμετρικού ταιριάσματος για εφαρμογές όπως η αναγνώριση κι ο εντοπισμός αντικειμένων, η ευθυγράμμιση εικόνων, ή η ανάκτηση από μεγάλες βάσεις εικόνων. Πιο σημαντικές από αυτές είναι το γεωμετρικά αναλλοίωτο, οι περιορισμοί ακαμψίας, οι περιορισμοί στις αντιστοιχίες, οι υποθέσεις σχετικά με τα χρησιμοποιούμενα τοπικά χαρακτηριστικά ή περιγραφείς, η διακριτική τους ικανότητα και φυσικά το υπολογιστικό κόστος. Στην παρούσα διατριβή θα ασχοληθούμε με το πρόβλημα της ανάκτησης από μεγάλη βάση εικόνων με χρήση εικόνας ερωτήματος. Σκοπός είναι η εύρεση εικόνων οι οποίες απεικονίζουν το ίδιο αντικείμενο από διαφορετικές οπτικές γωνίες ακόμα κι αν αυτό δεν είναι πλήρως ορατό. Για τον σκοπό αυτό προτείνουμε δύο μεθόδους ανάκτησης με χρήση γεωμετρικής πληροφορίας είτε στην δομή δεικτοδότησης είτε σε ένα δεύτερο στάδιο ανακατάταξης των εικόνων με γεωμετρικά κριτήρια. Επίσης προτείνουμε τρόπους με τους οποίους το γεωμετρικό ταίριασμα μπορεί να χρησιμοποιηθεί για επιλογή χαρακτηριστικών. Τέλος αναπτύσσουμε μία μέθοδο για επέκταση ερωτήματος η οποία εμπλουτίζει την τοπική αναπαράσταση της εικόνας, επιτυγχάνοντας υψηλή απόδοση και σε χαμηλούς χρόνους. Παρουσιάζουμε μία νέα μέθοδο για δεικτοδότηση και ανάκτηση εικόνων, η οποία ενσωματώνει την εμφάνιση των τοπικών χαρακτηριστικών μαζί με πληροφορία καθολικής γεωμετρίας στην διαδικασία δεικτοδότησης. Χρησιμοποιούμε τις παραμέτρους σχήματος των τοπικών χαρακτηριστικών για να πάρουμε μία εκτίμηση της ευθυγράμμισης των εικόνων από μονές αντιστοιχίες χαρακτηριστικών. Για κάθε χαρακτηριστικό κατασκευάζουμε έναν αραιό χωρικό χάρτη ο οποίος κωδικοποιεί την κανονικοποιημένη θέση όλων των υπολοίπων χαρακτηριστικών. Μία εικόνα αναπαρίσταται τελικά από ένα σύνολο τέτοιων χαρτών χαρακτηριστικών και τελικά ένα ταίριασμα εικόνων παρόμοιο με εκείνο του αλγόριθμου RANSAC ανάγεται σε έναν αριθμό από εσωτερικά γινόμενα ή τομές συνόλων. Χρησιμοποιούμε την μέθοδο των ανεξάρτητων αντιμεταθέσεων και προτείνουμε ένα μέτρο ομοιότητας για συλλογές χαρτών χαρακτηριστικών.Εκτός από την τυχαία επιλογή χαρακτηριστικών προχωράμε και σε επιλογή τους με βάση το γεωμετρικό ταίριασμα ανάμεσα σε διαφορετικές όψεις του ίδιου αντικειμένου. Αυτή η τεχνική μας επιτρέπει να κατορθώσουμε δεικτοδότηση γεωμετρίας για 1Μ εικόνες. Εκμεταλλευόμενοι την αραιότητα της αναπαράστασής μαςχρησιμοποιούμε ανάστροφο αρχείο ως δομή δεικτοδότησης μετατρέποντας την αναζήτηση σε διαδικασία υπο-γραμμική ως προςτο μέγεθος της βάσης εικόνων.Επιπλέον προτείνουμε ένα πολύ απλό μοντέλο γεωμετρικού ταιριάσματος (ταίριασμα πυραμίδων Hough) με έμπνευση από τον μετασχηματισμό Hough στον χώρο των γεωμετρικών μετασχηματισμών. Οι ψήφοι Hough, προκύπτουν και πάλι από μονές αντιστοιχίες χαρακτηριστικών. Ο αλγόριθμός μας χρησιμοποιεί χαλαρό γεωμετρικό ταίριασμα το οποίο επιτρέπει το ταίριασμα πολλαπλών αντικειμένων ή επιφανειών, επιβάλλοντας παράλληλααντιστοίχιση ένα προς ένα με πολυπλοκότητα γραμμική ως προς το πλήθος των αρχικών αντιστοιχιών. Τον εφαρμόζουμε σε ανάκτηση από βάση 2 εκατομμυρίων εικόνων επιδεικνύοντας υψηλότερη απόδοση αλλά και ταχύτερη εκτέλεση από σύγχρονες μεθόδους.Επεκτείνουμε και χρησιμοποιούμε την μέθοδο ταιριάσματος πυραμίδων Hough για τον εντοπισμό συμμετρικών κι επαναλαμβανόμενων δομών μέσα στην ίδια εικόνα. Υποστηρίζουμε πως τοπικά χαρακτηριστικά τα οποία συμμετέχουν σε τέτοιες δομές έχουν μεγαλύτερη πιθανότητα να ταιριάξουν και μεταξύ διαφορετικών εικόνων. Το αποτέλεσμα του γεωμετρικού ταιριάσματος της εικόνας με τον εαυτό της και το αντικατοπτρισμένο είδωλο της μας δίνει την πληροφορία για την επιλογή χαρακτηριστικών από μοναδικές εικόνες.Σε αντίθεση με όλες τις προηγούμενες μεθόδους με τις οποίες ασχοληθήκαμε και προτείναμε, οι οποίες χρησιμοποιούν μόνο τις οπτικές λέξεις για ταίριασμα μεταξύ τοπικών χαρακτηριστικών, ασχολούμαστε και με την μέθοδο Hamming Embedding (HE) η οποία κάνει επιπλέον χρήση πληροφορίας του τοπικού περιγραφέα. Κάθε τοπικό χαρακτηριστικό περιγράφεται από μία οπτική λέξη αλλά και μία δυαδική υπογραφή. Προτείνουμε μία μέθοδο για επέκταση ερωτήματος η οποία χρησιμοποιεί την βασική αναπαράσταση της μεθόδου HE και είναι εναρμονισμένη με αυτή. Καταφέρνουμε να βελτιώσουμε την απόδοση ακόμα και χωρίς την χρήση γεωμετρικής πληροφορίας και να πετύχουμε έτσι πολύ χαμηλούς χρόνους εκτέλεσης. Τελικά δείχνουμε πως με επιπλέον γεωμετρικό ταίριασμα η απόδοση βελτιώνεται ακόμα περισσότερο.