Αντιστοίχιση σημείων με γεωμετρικούς περιορισμούς

Abstract

In this thesis we present and analyse the theoretical and experimental steps of a methodology for the evaluation of the geometric consistency of point-pair matches in weakly calibrated scenes. Given interest points that are extracted by a local feature algorithm and putative matches among them according to some local photometric measures, we attempt their verification using purely geometric characteristics in projective spaces. The initial approach is done in a weakly calibrated framework, which means that some information for the camera pair is available, but no assumptions are made for the observed point configurations in 3-dimensional space. During the course we comment on the theoretical and practical problems of the mathematical analysis, the experimental approach as well as the implementation of the proposed algorithms. The central idea of the proposed methodology utilises a virtual geometric construction through which a scalar quantity is calculated, which is subsequently evaluated statistically. The method is based on the cross-ratios which are projective invariants, in the sense that they are preserved by the projective transformations of a projective space. We describe the calculation of the proposed quantities through the virtual geometric construction and analyse their probability distribution under both assumptions of correct and false point correspondences. Main guideline in the whole approach has been to steer away as much as possible from the theoretical barrier that the absence of a metric in projective spaces imposes on calculations performed inside them. This is attempted by reducing the indexing of point matches as inliers and outliers in weekly calibrated scenarios into a problem of indexing probability functions characterising the proposed scalar quantities. The classification is binary and does not rely on the tuning of any thresholding variables. We study theoretically as well as by means of extensive experiments the distinction capability of the distributions as a criterion for the point matching problem and its dependence on the number of samples used for their estimation. This number is shown to be directly linked to the computational complexity of the proposed methodology and the accuracy of the results. At the same time, the indexing performance of the approach in terms of false positives is consistently high. That kind of behaviour is suited for different applications, depending on the available computational power and the required accuracy. Subsequently, we introduce techniques aimed at reducing the computational cost of the proposed methods, as well as for implementing them in parallel computing environments. The scalar values based on the cross-ratios are processed in a statistical framework through the use of weighted sampling. Our approach applies on the problem of geometric point-pair validation a novel modification on the voting based methods, in which the values of the cost function are evaluated according to their distributions instead of their sum. Finally, we also present an application of our approach in uncalibrated cameras using a robust RANSAC framework. Additionally time, this application is a partial extension of the cross-ratio based methodology in uncalibrated scenarios. The performance of the proposed schemes is compared to the commonly used algebraic distances and shown to be more strict by extensive experiments on synthetic and real data.

Στα πλαίσια της διατριβής παρουσιάζονται και αναλύονται τα θεωρητικά και πειραματικά στάδια μιας μεθοδολογίας για την αξιολόγηση της γεωμετρικής συνέπειας αντιστοιχιών σημείων σε ασθενώς βαθμονομημένα σενάρια και άγνωστες σκηνές. Δεδομένων σημείων ενδιαφέροντος που εξάγονται από δύο εικόνες από κάποιον αλγόριθμο τοπικών χαρακτηριστικών και για τα οποία υπάρχει μια αρχική εκτίμηση της μεταξύ τους αντιστοίχισης, επιχειρείται η επιβεβαίωσή τους με χρήση γεωμετρικών χαρακτηριστικών του προβολικού χώρου. Η μελέτη γίνεται αρχικά στα πλαίσια της ασθενούς βαθμονόμησης, το οποίο σημαίνει ότι υπάρχει κάποια περιορισμένη πληροφορία για τη διάταξη των καμερών, αλλά χωρίς καμία πληροφορία για την τριδιάστατη σκηνή. Στην πορεία σχολιάζονται τα θεωρητικά και πρακτικά θέματα της μαθηματικής ανάλυσης, της πειραματικής προσέγγισης καθώς και της υλοποίησης των μεθόδων της διατριβής. Η κεντρική ιδέα της προτεινόμενης μεθοδολογίας χρησιμοποιεί μια εικονική γεωμετρική κατασκευή μέσω της οποίας υπολογίζεται μια βαθμωτή ποσότητα που αξιολογείται στατιστικά. Η μέθοδος βασίζεται στους αναρμονικούς λόγους (cross ratio), που είναι ποσότητα αμετάβλητη μεταξύ προοπτικών καταγραφών. Η διατριβή εισάγει τον ορισμό των ποσοτήτων αυτών μέσω της εικονικής γεωμετρικής κατασκευής και αναλύει διεξοδικά τη στατιστική τους κατανομή τόσο υπό την υπόθεση ότι η μελετούμενη ποσότητα αντιστοιχεί σε ζεύγος ορθής αντιστοίχισης όσο και υπό την αντίθετη. Βασική κατευθυντήρια γραμμή της όλης προσέγγισης είναι να παρακαμφθεί όσο το δυνατόν το φράγμα της έλλειψης μετρικής στους προβολικούς χώρους, το οποίο εμφανίζεται στους αριθμητικούς υπολογισμούς που διεξάγονται εντός τους. Αυτό επιχειρείται ανάγοντας το πρόβλημα της απόφασης για την ορθή (inliers) ή μη ορθή (outliers) αντιστοίχιση ζευγών σημείων σε συνθήκες ασθενούς βαθμονόμησης σε ένα πρόβλημα κατηγοριοποίησης της κατανομής της βαθμωτής ποσότητας ως τυχαία μεταβλητή. Η κατηγοριοποίηση αυτή είναι δυαδική και επιτυγχάνεται χωρίς την εκ των προτέρων γνώση κατωφλιών (thresholds). Μελετήθηκε τόσο θεωρητικά όσο και μέσω εκτενών πειραμάτων η διαχωριστική ικανότητα των στατιστικών κατανομών ως κριτήριο ορθής/εσφαλμένης αντιστοίχισης σημείων και η εξάρτηση της από το πλήθος μαρτύρων που συλλέγονται για κάθε αντιστοίχιση. Το πλήθος αυτό δείχνεται ότι αντιστοιχεί ευθέως στην υπολογιστική πολυπλοκότητα της προτεινόμενης μεθόδου και στην ακρίβεια των εξαγόμενων αποτελεσμάτων. Την ίδια στιγμή, η απόδοση της κατηγοριοποίησης ως προς τον αριθμό των λανθασμένα έγκυρων αντιστοιχιών (false positives) είναι συστηματικά υψηλή. Η συμπεριφορά αυτή ενδείκνυται για διαφορετικές εφαρμογές, ανάλογα με τη διαθέσιμη υπολογιστική ισχύ και την ζητούμενη ακρίβεια. Στη συνέχεια εισάγονται τεχνικές μείωσης του υπολογιστικού κόστους της προτεινόμενης μεθοδολογίας καθώς και παραλληλοποίησης της διαδικασίας. Οι βαθμωτές μεταβλητές με βάση τους αναρμονικούς λόγους αξιολογούνται σε ένα στατιστικό πλαίσιο με χρήση δειγματοληψίας με βάρη. Η προσέγγιση εφαρμόζει στο πρόβλημα της αξιολόγησης γεωμετρικής συμβατότητας μια καινούρια παραλλαγή των μεθόδων ψηφίσματος (voting), όπου οι τιμές μιας συνάρτησης κόστους αξιολογούνται ως προς την κατανομή τους αντί ως προς το άθροισμά τους. Τέλος, προτείνεται μια εφαρμογή της μεθόδου σε σενάρια μη βαθμονομημένων καμερών με εύρωστες τεχνικές τύπου RANSAC. Επιπλέον, η εφαρμογή είναι μια μερική επέκταση της μεθοδολογίας των αναρμονικών λόγων σε μη βαθμονομημένα σενάρια. Η απόδοση της προσέγγισης συγκρίνεται με τις αλγεβρικές αποστάσεις που συνήθως χρησιμοποιούνται για την αξιολόγηση της γεωμετρικής συμβατότητας και δείχνεται μέσω εκτενών πειραμάτων σε συνθετικά και πραγματικά δεδομένα ότι είναι πιο αυστηρή.