Από τον Ευκλείδη στον Riemann: Ένα άλμα στην υπολογιστική όραση σε γεωμετρικούς χώρους

Βασιλάκης, Νικόλαος

A leap of faith from Euclidean to Riemannian manifolds for computer vision applications

Διπλωματική εργασία

Author

Βασιλάκης, Νικόλαος

Date

2024-10-08

Advisor

Zois, Elias
Venetis, Ioannis

Vasilakis_diploma_theseis_vfinal_signedCCIVEZ.pdf (7.494Mb)

ΔΗΛΩΣΗ-ΣΥΓΓΡΑΦΕΑ-ΠΤΥΧΙΑΚΗΣ-ΔΙΠΛΩΜΑΤΙΚΗΣ-ΕΡΓΑΣΙΑΣ.pdf (101.2Kb)

Keywords

Computer vision ; Digital image processing ; SPD ; Symmetric positive definite manifold ; MATLAB ; Biometrics ; Riemannian geometry ; Υπολογιστική όραση ; Ψηφιακή επεξεργασία εικόνας ; Ευκλείδειοι χώροι ; Συμμετρική και θετικά ορισμένη πολλαπλότητα ; Παράλληλη επεξεργασία ; Κάρτες γραφικών ; Διανυσματική αναπαράσταση εικόνων

Abstract

Η παγκόσμια επιστημονική κοινότητα, μέχρι πρότινος, παραμένοντας πιστή στις κοινότυπες προσεγγίσεις των μεθόδων που χρησιμοποιούνται στην Μηχανική Μάθηση στηρίζεται στην υπόθεση ότι η δόμηση και κατά συνέπεια η επεξεργασία των δεδομένων θα πρέπει να υπόκειται σε πράξεις οι οποίες ορίζονται σε διανυσματικούς χώρους με πρωταρχική βάση την Ευκλείδεια γεωμετρία. Πορίσματα από πληθώρα ερευνών έχουν δείξει ότι ο επιστημονικός τομέας της Υπολογιστική Όραση επωφελείται από αναπαραστάσεις δεδομένων που είναι συμπαγείς, διακριτές, και εύρωστες. Εδώ λοιπόν εγείρεται το ακόλουθο ερώτημα: Μπορούμε να υποστηρίζουμε με απόλυτη βεβαιότητα ότι τα δεδομένα, όπως αυτά συλλέγονται και επεξεργάζονται, ακολουθούν πιστά την Ευκλείδεια Γεωμετρία; Αν όχι, υπάρχει κάποιου είδους υποκείμενης γεωμετρικής δομής η οποία δρα συμπληρωματικά στην ήδη απλοϊκή φύση του Ευκλείδειου Γεωμετρικού χώρου ενισχύοντας τα μοντέλα Μηχανικής Μάθησης με επιπρόσθετη περιγραφικότητα οδηγώντας έτσι σε υψηλότερα επίπεδα ακρίβειας προβλέψεων; Μια πιθανή απάντηση είναι η χρήση Συμμετρικών Θετικά Ορισμένων πινάκων οι οποίοι αντιμετωπίζονται πιο φυσικά μέσω των εννοιών της διαφορικής γεωμετρίας που εμφανίζεται σε μη-Ευκλείδειους χώρους, όπως αυτός του Riemann. Στόχος της παρούσας διπλωματικής είναι να γίνει μια μελέτη σε αλγορίθμους μη επιβλεπόμενης μάθησης τόσο σε Ευκλείδειους όσο και σε Riemannian χώρους με την χρήση προγραμματιστικών εργαλείων όπως το MATLAB για εφαρμογές Υπολογιστικής Όρασης. Συγκεκριμένα, στον Ευκλείδειο χώρο μελετώνται οι αλγόριθμοι: α) Bag of Features, β) Spatial Pyramid Matching, γ) Fisher Kernels και δ) Vectors of Locally Aggregated Descriptors ενώ στον Riemannian χώρο μελετώνται τεχνικές αλγορίθμων που εκμεταλλεύονται την εγγενώς μη γραμμική φύση των πολλαπλοτήτων στις οποίες απαντώνται οι πίνακες συνδιακύμανσης. Οι τέσσερις αριθμημένοι αλγόριθμοι του Ευκλείδειου Χώρου δοκιμάζονται σε μια βάση εικόνων που περιέχουν σκηνές για την μελέτη της προοδευτικής αύξησης της ακρίβειας της τεχνικής της διανυσματικής αναπαράστασης των εικόνων ενώ οι αλγόριθμοι στον Riemannian Χώρο επεξεργάζονται εικόνες χειρόγραφων υπογραφών από μια δημοφιλή βάση με σκοπό την βιομετρική ταυτοποίησή τους. Όπου κατέστη δυνατό, εφαρμόζεται επιτάχυνση του λογισμικού για την μείωση του χρόνου λήψης αποτελεσμάτων στην υλοποίηση των αλγορίθμων χρησιμοποιώντας παράλληλη επεξεργασία και χρήση καρτών γραφικών.

Abstract

The global scientific community, until recently, remaining faithful to the common approaches of the methods used in Machine Learning, has assumed that the construction and consequently the processing of data should be subject to operations defined in vector spaces with Euclidean geometry as the primary basis. Findings from a plethora of research have shown that the scientific field of Computational Vision benefits from data representations that are compact, discrete, and robust, the following question therefore arises here: Can we assert with absolute certainty that the data, as collected and processed, faithfully follow Euclidean geometry? If not, is there some kind of underlying geometric structure that acts in a complementary way to the already simplistic nature of the Euclidean Geometry space by enhancing Machine Learning models with additional descriptiveness leading to higher levels of prediction accuracy? One possible answer is the use of Symmetric Positively Defined matrices which are treated more naturally through the concepts of differential geometry occurring in non-Euclidean spaces such as Riemannian spaces. The objective of this diploma thesis is to provide a thorough review on unsupervised learning algorithms in both Euclidean as well as Riemannian spaces with the use of programming tools such as the MATLAB for computer vision applications. In the Euclidean space the following algorithms are under examination: a) Bag of Visual Words (BoVW), b) Spatial Pyramid Matching (SPM), c) Fisher Kernels (FK) or Fisher Vectors (FV), and d) Vectors of Locally Aggregated Descriptors (VLAD) whereas in Riemannian space techniques for algorithms that exploit the intrinsic non-linear nature of the manifolds that comprise the covariance matrices are studied. The four numbered algorithms in Euclidean Space are tested on an image database containing scenes to study the progressive increase in the accuracy of the vector image representation technique, while the algorithms in Riemannian Space process images of handwritten manuscripts from a popular signature database for biometric identification. Wherever feasible, software acceleration is applied to reduce the time to obtain results in the implementation of the algorithms using parallel processing and GPU computing.