A local stereo matching algorithm for dense 3D scene reconstruction

Abstract

This thesis investigates problems and algorithms on stereo-matching for the purposes of 3D reconstruction in a variety of applications. Stereo-matching can be part, for instance, of multi-view algorithms used to produce 3D models and orthomaps from aerial images, either from digital aerial cameras or UAV cameras, or architectural reconstructions. Nevertheless, it is also often applied to single stereo-pairs since many modern applications rely on stereo-matching to obtain the shape of the surrounding world, including robotics, autonomous navigation, augmented reality. Considering such applications, stereo-algorithms need, among other characteristics, to adapt well to new domains, offer accurate results, be computationally efficient and run on low-powered devices. The main scope here has been to thoroughly study existing methods and approaches for the core components of matching algorithms, namely cost computation, aggregation and optimization, as well as confidence measures and disparity map refinements, understand their limits and limitations, and propose in each step possible novelties and improvements concerning the quality of the final 3D reconstructed scene. First, the variety of active and passive (image-based) methods for 3D reconstruction are briefly reviewed to correctly place stereo-matching in the broader area of surface reconstruction approaches; also, fundamental concepts for calibrating and creating a rectified stereo-pair as a standard prerequisite for stereo-matching algorithms are given. Several stereo-algorithms have been studied and evaluated in an in-depth review to acquire a firm understanding of concepts and methods in the overall area of stereo-matching. Different cost functions have been implemented or adapted, as well as image filters, confidence measures and matching constraints. Also, aggregation methods, both simple and more elaborate, have been implemented and experimented with to better comprehend and evaluate their performance, also with respect to global methods. Based on this, an end-to-end stereo-algorithm was developed, including certain novelties in each of its individual components. A combination of cost measures is used to define the overall cost based on census transformation on gradients which produced improved results, especially in sub-pixel disparity estimation and under radiometric differences in the stereo-pair, under different aggregation and optimization schemes. As an aggregation scheme, an improved version of cross-based matching, which defines the geometric and radiometric proximity based on a linear threshold, has been proposed; this yielded better results than the original definition and reduced the heuristic thresholds needed to define it. It is noticed that local methods, despite advantages in speed, computational complexity, and disparity edge retrieval, perform poorly on strongly slanted surfaces. To this end, the computed cost volume is filtered via a geometrically constrained smoothing kernel, based on a 3D Gaussian kernel but modified to serve the ordering and uniqueness constraints. This approach significantly improved the disparities in slanted surfaces at the low cost of a convolutional operation. This technique is generic and can be used in conjunction with any stereo algorithm. The above methods have been integrated within a hierarchical matching scheme to tackle issues related to high-resolution images, namely computational efficiency and accuracy via reducing the disparity search space. The cross-based support regions have been intuitively exploited for this. Some extra investigations have been conducted on semi-global matching and the different approaches to define the penalties on disparity changes and on global optimization (via MRFs) combined with local aggregation. Different disparity map refinement steps have also been implemented to evaluate the improvement on the final results, and a robust scheme of consecutive refinement steps is proposed mixing existing approaches and new techniques, some of which exploit the cross-based regions.The proposed techniques were assembled in an algorithm that performs reasonably well, with quantitative evaluation criteria, to various scenes. The evaluation and the comparison to other methods were based on typical datasets available in standard publicly available evaluation platforms, and on datasets that can better fit the purposes of typical photogrammetric applications.

Η παρούσα διατριβή μελέτησε προβλήματα και αλγορίθμους που αφορούν την αυτόματη πυκνή συνταύτιση σε στερεοζεύγη εικόνων (stereo-matching) για την 3D ανακατασκευή (3D reconstruction) σε πλήθος πεδίων εφαρμογής. Η “διεικονική συνταύτιση” μπορεί, για παράδειγμα, να αποτελεί μέρος αλγορίθμων πολυεικονικής συνταύτισης (multi-view matching) για την δημιουργία 3D μοντέλων και ορθοφωτοχαρτών από αεροφωτογραφίες (προερχόμενες από αεροφωτομηχανές ή από μηχανές φερόμενες σε UAV) ή για την δημιουργία μοντέλων αρχιτεκτονικού ή αρχαιολογικού ενδιαφέροντος. Ωστόσο, συχνά επίσης εφαρμόζεται απλώς σε μεμονωμένα στερεοζεύγη, δεδομένου ότι πολλές σύγχρονες εφαρμογές βασίζονται σε τεχνικές διεικονικής συνταύτισης για την ανάπλαση του σχήματος του περιβάλλοντος κόσμου, συμπεριλαμβανομένων της ρομποτικής, της αυτόνομης πλοήγησης και την επαυξημένης πραγματικότητας (augmented reality). Στο πλαίσιο τέτοιων εφαρμογών, οι αλγόριθμοι διεικονικής συνταύτισης (stereo-algorithms) χρειάζεται, μεταξύ άλλων χαρακτηριστικών τους, να προσαρμόζονται καλά σε νέα πεδία, να παρέχουν ακριβή αποτελέσματα, να είναι υπολογιστικά ρεαλιστικοί και να ανταποκρίνονται σε εξοπλισμούς χαμηλής ισχύος. Βασικό πλαίσιο της διατριβής ήταν η κατά το δυνατόν πληρέστερη μελέτη υπαρχουσών τεχνικών και μεθόδων για τις βασικές συνιστώσες των αλγορίθμων συνταύτισης – και ειδικότερα τον υπολογισμό κόστους συνταύτισης (cost computation), την συσσωμάτωση (aggregation) και βελτιστοποίηση (optimization) του κόστους καθώς και τα μέτρα εμπιστοσύνης όσο και την τελική επεξεργασία των χαρτών παράλλαξης (disparity map refinements) – και η διερεύνηση των ορίων και των περιορισμών τους. Τελικός στόχος ήταν να προταθούν, κατά το δυνατόν σε κάθε βήμα της όλης διαδικασίας συνταύτισης, καινοτομίες και βελτιώσεις σχετικά με την ποιότητα της τελικής ανακατασκευασμένης 3D επιφάνειας. Αρχικά, πραγματοποιείται σύντομη επισκόπηση του πλήθους των υπαρχουσών ενεργητικών και παθητικών (δηλαδή βάσει εικόνων) μεθόδων για την 3D ανακατασκευή προκειμένου να ενταχθεί η διεικονική συνταύτιση στο ευρύτερο πλαίσιο των μεθόδων ανακατασκευής. Ακόμα, αναφέρονται ορισμένες θεμελιώδεις έννοιες σχετικά με τον προσανατολισμό και την επιπολική επανασύσταση στερεοζευγών, που αντιπροσωπεύουν συνήθεις προϋποθέσεις για την εφαρμογή αλγορίθμων διεικονικής συνταύτισης. Μελετήθηκαν και αξιολογήθηκαν αρκετοί διεικονικοί αλγόριθμοι συνταύτισης σε μια αναλυτική επισκόπηση. Υλοποιήθηκαν και προσαρμόστηκαν διαφορετικές συναρτήσεις κόστους συνταύτισης, καθώς και φίλτρα εικόνων, μέτρα εμπιστοσύνης και δυνατές δεσμεύσεις κατά την συνταύτιση. Υπήρξε ακόμα πειραματισμός με μεθόδους συσσωμάτωσης κόστους, προκειμένου να αποσαφηνιστεί και αξιολογηθεί η απόδοσή τους σε τοπικές (local) αλλά και σε σύνολες (global) προσεγγίσεις συνταύτισης. Βάσει αυτών, αναπτύχθηκε ένας πλήρης (end-to-end) αλγόριθμος τοπικής διεικονικής συνταύτισης, ο οποίος περιλαμβάνει ορισμένες νέες ιδέες σε κάθε μία από τις συνιστώσες του. Προκειμένου να οριστεί το τελικό κόστος, χρησιμοποιήθηκε ένας συνδυασμός μέτρων κόστους συνταύτισης βασιζόμενος κυρίως σε μετασχηματισμό census στις εικόνες κλίσεων (gradients), από όπου προέκυψαν βελτιωμένα αποτελέσματα, ιδιαίτερα στην υποψηφιδική (sub-pixel) εκτίμηση της παράλλαξης, στο πλαίσιο διαφορετικών παραλλαγών συσσωμάτωσης και βελτιστοποίησης κόστους. Ως σχήμα συσσωμάτωσης προτάθηκε εδώ μια βελτιωμένη παραλλαγή της “σταυροειδούς” (cross-based) συνταύτισης, όπου η γεωμετρική και ραδιομετρική εγγύτητα ορίζονται μέσω γραμμικού κατωφλίου. Αυτό απέδωσε καλύτερα από την αρχική εκδοχή, αποφεύγοντας και τα ευρετικά (heuristic) κατώφλια που εκείνη απαιτούσε. Ακόμα, έχει παρατηρηθεί ότι οι τοπικές μέθοδοι – παρά τα πλεονεκτήματά τους πχ. σε ταχύτητα και υπολογιστική απλότητα – δεν αποδίδουν ικανοποιητικά σε έντονα κεκλιμένες επιφάνειες. Για τον λόγο αυτό ο υπολογιζόμενος όγκος κόστους (cost volume) εξομαλύνεται εδώ με γεωμετρικά δεσμευμένο φίλτρο, βασιζόμενο σε 3D φίλτρο Gauss αλλά τροποποιημένο προκειμένου να ικανοποιεί τις δεσμεύσεις της διαδοχής και της μοναδικότητας (ordering and uniqueness constraints). Η προσέγγιση αυτή, που είναι γενική και μπορεί να αξιοποιηθεί σε κάθε διεικονικό αλγόριθμο, βελτίωσε σημαντικά τις τιμές παραλλάξεων σε κεκλιμένες επιφάνειες με την μικρή επιβάρυνση μιας πράξης συνέλιξης. Οι προαναφερθείσες μέθοδοι ενσωματώθηκαν σε ένα σχήμα ιεραρχικής συνταύτισης, προκειμένου να αντιμετωπίζονται προβλήματα σχετιζόμενα με εικόνες υψηλής ανάλυσης, από άποψη δηλαδή υπολογιστικού φόρτου και ακρίβειας, με την μείωση του εύρους αναζήτησης των παραλλάξεων. Οι σταυροειδείς περιοχές υποστήριξης (cross-based support regions) χρησιμοποιήθηκαν και σε αυτή την περίπτωση. Ακόμα, πραγματοποιήθηκαν ορισμένες πρόσθετες διερευνήσεις σχετικά με την “υπο-σύνολη” συνταύτιση (semi-global matching) και τις διαφορετικές εκδοχές ορισμού των ποινών στις μεταβολές παράλλαξης, καθώς και σχετικά με τον συνδυασμό σύνολης βελτιστοποίησης (μέσω MRF) με τοπική συσσωμάτωση. Τέλος, υλοποιήθηκαν και αξιολογήθηκαν ως προς την απόδοσή τους διαφορετικά βήματα επεξεργασίας του χάρτη παράλλαξης, με αποτέλεσμα να προταθεί ένα εύρωστο σχήμα διαδοχικών βημάτων τελικής επεξεργασίας (refinement steps) με την συνέργεια υπαρχουσών προσεγγίσεων και νέων τεχνικών, ορισμένες από τις οποίες αξιοποιούν τις “σταυροειδείς” περιοχές. Η αξιολόγηση και η σύγκριση με άλλες μεθόδους βασίστηκαν σε αντιπροσωπευτικά δεδομένα εικόνων, προσβάσιμα σε έγκυρες, δημόσια διατιθέμενες πλατφόρμες για την αξιολόγηση αλγορίθμων συνταύτισης, καθώς και σε περαιτέρω δεδομένα που αντιπροσωπεύουν τυπικότερες φωτογραμμετρικές εφαρμογές (εικόνες από την Ακρόπολη την Αθηνών και εικόνες από ψηφιακή αεροφωτομηχανή). Οι προτεινόμενες τεχνικές συγκροτήθηκαν σε έναν αλγόριθμο που αποδίδει ικανοποιητικά, με βάση κριτήρια ακρίβειας, για διαφορετικά είδη απεικονιζόμενων σκηνών.