Στη διπλωματική αυτή εργασία αναλύεται η εκτίμηση του βάθους μίας άκαμπτης σκηνής από κάμερα τοποθετημένη σε αυτοκίνητο που κινείται. Στο κεφάλαιο 1 γίνεται μία εισαγωγή στον τομέα της Υπολογιστικής Όρασης και δίνονται μερικά παραδείγματα εφαρμογών της. Στο κεφάλαιο 2 περιγράφονται βασικές αρχές της προβολικής γεωμετρίας που χρησιμοποιείται ως μαθηματικό υπόβαθρο για τα επόμενα κεφάλαια. Στο κεφάλαιο 3 γίνεται λόγος για το θεωρητικό μοντέλο της κάμερας, των παραμέτρων της και των παραμορφώσεων που υπεισέρχονται στο μοντέλο αυτό. Στο κεφάλαιο 4 αναφέρεται η διαδικασία βαθμονόμησης της κάμερας, μαζί με την υλοποίησή της. Στο κεφάλαιο 5 παρουσιάζονται γενικές κατηγορίες των στερεοσκοπικών αλγορίθμων που χρησιμοποιούνται, καθώς και τα κατάλληλα μέτρα ομοιότητάς τους. Στο κεφάλαιο 6 γίνεται αναφορά στον ανιχνευτή γωνιών Harris και γίνεται η εφαρμογή του τόσο ως προς την ανίχνευση των γωνιών, όσο και ως προς την αντιστοίχιση των 2 εικόνων. Στο κεφάλαιο 7 αναλύεται η θεωρία του αλγόριθμου SIFT και δίνεται ένα παράδειγμα ανίχνευσης και αντιστοίχισης χαρακτηριστικών. Στο κεφάλαιο 8 επισημαίνονται οι βασικές αρχές της επιπολικής γεωμετρίας, καθώς η σημασία της διόρθωσης των εικόνων. Στο κεφάλαιο 9 αναφέρεται η συνολική διαδικασία που ακολουθήθηκε, μαζί με την περιγραφή και την υλοποίηση των μεθόδων εκτίμησης βάθους που χρησιμοποιήθηκαν. / The current master’s thesis analyzes the depth estimation of a rigid scene from a camera attached to a moving vehicle. The first chapter gives an introduction to the field of Computer Vision and provides some examples of its applications. The second chapter describes basic principles of projective geometry that are being used as mathematical background for the next chapters. The third chapter refers to the theoretical modeling of a camera, along with its parameters and the distortions that appear in this model. The forth chapter deals with the camera calibration procedure, along with its implementation. Chapter five presents general categories of stereoscopic algorithms, along with their similarity measures. Chapter six talks about Harris corner detector and its implementation in detecting corners and in the matching process as well. Chapter 7 analyzes the SIFT algorithm theory and gives an example of detecting and matching features. Chapter 8 highlights basic principles of epipolar geometry and stresses out the importance of image rectification. Chapter nine presents the procedure that has been followed, along with the description and implementation of the depth estimation methods that have been used.

- / -

H συγκεκριμένη διπλωματική εργασία αποτελεί συνέχεια μιας σειράς διπλωματικών εργασιών οι οποίες είχαν ως πηγή έμπνευσης το ρομποτικό όχημα (robot rover) Sojourner το οποίο είχε σταλθεί στον πλανήτη Άρη από τη NASA το 1997. Συγκεκριμένα είχε υλοποιηθεί παλαιότερα μια διπλωματική εργασία στην οποία σκοπός ήταν η κατασκευή ενός ενσωματωμένου συστήματος και του αντίστοιχου οχήματος που θα ελέγχεται στα πρότυπα του ρομποτικού οχήματος Sojourner, όσο αυτό είναι εφικτό. Πιο συγκεκριμένα είχε κατασκευαστεί ένα όχημα και είχε γίνει ο σχεδιασμός και η υλοποίηση ενός ενσωματωμένου συστήματος βασισμένο στον επεξεργαστή της Intel 8086. Σκοπός στη συγκεκριμένη διπλωματική εργασία, είναι ο σχεδιασμός και η υλοποίηση ενός ενσωματωμένου συστήματος, το οποίο θα στηρίζεται σε ένα πιο σύγχρονο υπολογιστικό σύστημα και ταυτόχρονα η υλοποίηση ενός μηχανισμού, με τον οποίο το όχημα θα μπορεί να ανιχνεύει στοιχειωδώς την ύπαρξη κάποιου πιθανού εμποδίου. Αρχικά επιλέχθηκε να υλοποιηθεί μηχανισμός στερεοσκοπικής όρασης προκειμένου να πραγματοποιείται η αναγνώριση πιθανού εμποδίου. Η επιλογή αυτή αποτέλεσε σημαντικό παράγοντα για τον μετέπειτα προγραμματισμό του συστήματος. Στη συνέχεια έγινε ο σχεδιασμός του ενσωματωμένου συστήματος και η επιλογή του hardware που το απαρτίζει. Οι επιλογές που έγιναν προσπάθησαν να αντισταθμίσουν τους παράγοντες κόστους και ταχύτητας. Το επόμενο βήμα αποτέλεσε η software υλοποίηση, δηλαδή ο προγραμματισμός του ενσωματωμένου συστήματος. Αρχικά υλοποιήθηκαν οι ρουτίνες για την κίνηση. Κατόπιν αναπτύχθηκε το πρόγραμμα που αφορά την στερεοσκοπική όραση και στο τέλος έγινε ο προγραμματισμός του radio module. Στη συνέχεια συνδυάστηκαν όλα τα παραπάνω μαζί ώστε να αποτελέσουν την τελική εφαρμογή. Στο τέλος πραγματοποιήθηκε η αξιολόγηση της επιλογής του υπολογιστικού συστήματος που χρησιμοποιήθηκε, καθώς και εξήχθησαν συμπεράσματα για πιθανές μελλοντικές προσθήκες και δυνατότητες. / This diploma thesis belongs to a series of diploma theses, which were inspired by NASA’s robot rover Sojourner which had been sent on Mars in 1997. Specifically, in an older diploma thesis, an embedded system was designed and implemented in order to move and control a vehicle, like it had been done with Sojourner, in a feasible degree. More specifically, a vehicle was constructed and an embedded system which was based on Intel 8086 processor was designed and implemented. The goal of this diploma thesis is the design and implementation of an embedded system which is based on a modern computer system. Moreover a mechanism for elementary locating a possible obstacle was implemented. In the first stage, stereo vision was chosen to be the process in which the vehicle would recognize a possible obstacle. That choice was a significant factor for the later system programming. Afterwards, the hardware that is used on the vehicle was chosen. Those choices tried to have a trade-off between cost and performance. The next step was the programming of the embedded system. This step consisted of three more steps. In the first step, movement functions which were responsible for moving the vehicle were programmed. Secondly, the program responsible for stereo vision was also written and the third step was the programming of the radio module which was used. Finally, all those three programs were combined in order to produce the final application. In the end, we assessed the choice of the computer system we used as well as the whole system and we reached on some conclusions. Also, some suggestions for future additions were introduced.

Η παρούσα διπλωματική εργασία αναπτύχθηκε στα πλαίσια των προπτυχιακών σπουδών του τμήματος Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών του Πανεπιστημίου Πατρών. Θέμα της είναι η τρισδιάστατη ανακατασκευή του χώρου από τουλάχιστον δύο φωτογραφίες του και αποτελεί μέρος του τομέα της Υπολογιστικής Όρασης. Συγκεκριμένα αναλύεται διεξοδικά η περίπτωση της στερεοσκοπικής όρασης, στην οποία η κάμερα μεταξύ δύο διαδοχικών λήψεων της ίδιας σκηνής, έχει μηδενική σχετική περιστροφή ως προς την αρχική της θέση και μικρή μετατόπιση, περίπου 5 εκατοστά. Με τον τρόπο αυτό, προσπαθούμε να προσομοιώσουμε τη λειτουργία της ανθρώπινης όρασης καθώς πολλές εφαρμογές της Τεχνητής Νοημοσύνης το κρίνουν απαραίτητο. Είναι λογικό ότι ο κάθε άνθρωπος θεωρεί τη στερεοσκοπική όραση αυτονόητη γιατί κινείται στον τρισδιάστατο κόσμο. Όταν αυτός όμως καταγράφεται από μία κάμερα, αυτόματα περνάει στο δισδιάστατο επίπεδο. Και πάλι είναι δυνατόν να εξάγουμε πληροφορίες βάθους από μία μόνο εικόνα, όμως γίνεται καθαρά εμπειρικά και βασίζεται στη σύγκριση διάφορων υφών, σχημάτων και μεγεθών. Ο ηλεκτρονικός υπολογιστής αναγνωρίζει την εικόνα σαν ένα οποιοδήποτε αρχείο. Δεν μπορεί να εξάγει κανένα συμπέρασμα για το τι απεικονίζει στον πραγματικό κόσμο. Χρειάζεται το συνδυασμό τουλάχιστον δύο εικόνων της ίδιας σκηνής από διαφορετικές θέσεις για να μπορέσει να αναγνωρίσει για παράδειγμα το βάθος της σκηνής που απεικονίζεται. Αυτή τη διαδικασία περιγράφει αναλυτικά η εργασία. Στο πρώτο κεφάλαιο εισάγουμε την έννοια και τη χρησιμότητα της στερεοσκοπικής όρασης. Στο δεύτερο κεφάλαιο παρουσιάζονται οι βασικές αρχές της προβολικής γεωμετρίας. Στο τρίτο κεφάλαιο αναφερόμαστε στη μοντελοποίηση της κάμερας και τις παραμέτρους που τη χαρακτηρίζουν. Στο τέταρτο κεφάλαιο αναλύεται η διαδικασία της βαθμονόμησης της κάμερας. Στο πέμπτο κεφάλαιο εξηγείται η διαδικασία αντιστοίχησης των σημείων ενδιαφέροντος στις δύο εικόνες. Στο έκτο κεφάλαιο αναλύονται οι βασικές αρχές της επιπολικής γεωμετρίας. Στο έβδομο κεφάλαιο παρουσιάζεται η πειραματική διαδικασία για την εύρεση του βάθους της σκηνής. Στο όγδοο κεφάλαιο παρουσιάζεται συνοπτικά η τρισδιάστατη ανακατασκευή του χώρου και παρουσιάζονται τα αντίστοιχα πειραματικά αποτελέσματα. Στο ένατο κεφάλαιο διατυπώνουμε τα συμπεράσματα της όλης διαδικασίας. Τόσο το θεωρητικό όσο και το πειραματικό μέρος αυτής της εργασίας καλύπτουν σε ένα μεγάλο ποσοστό τα βασικά στάδια ανακατασκευής του τρισδιάστατου χώρου. Τα αποτελέσματα της πειραματικής διαδικασίας αποδεικνύουν ότι οι υπάρχουσες μέθοδοι λειτουργούν ικανοποιητικά αλλά υπάρχουν πολλά περιθώρια βελτίωσης στο θέμα της Υπολογιστικής Όρασης. Στο σημείο αυτό να ευχαριστήσουμε τον επιβλέποντα καθηγητή μας κ. Δερματά για τη συνεργασία του και την κατανόησή του. / The current thesis has been written as part of the undergraduate studies for the department of Electrical and Computer Engineering of Patras University. Its objective is the three-dimensional (3D) reconstruction from two, at least, photographs, which is part of computer vision. More specifically, this thesis analyzes in detail the case of stereo vision when the camera, among two successive shots of the same image, has zero relative rotation compared to its initial position and an average translation of about 5 cm. In this way, it attempts to simulate human vision since this is essential for many Artificial Intelligence applications. Humans take stereo vision for granted since they live in a three-dimensional world. However, this world becomes two-dimensional when recorded by a camera. We can still get information about the image depth but this is empirically done based on comparing various heights, shapes and sizes. Images are identified by the computer as any other file. Computers cannot draw conclusions about what is depicted in the real world. They need to combine at least two images of the same scene and of different positions to identify the image’s depth. This process is described in the current thesis. The first chapter describes stereo vision and why it is so useful. The second chapter provides the basic principles of projective geometry, the mathematical background for passing from the two-dimensional level to the three-dimensional. The third chapter refers to camera modeling and its parameters (instrisic and extrinsic). Chapter four analyzes the camera calibration process. Chapter five explains the matching process of points of interest in both pictures. The sixth chapter provides the basic principles of epipolar geometry. The seventh chapter shows the experimental procedure that we followed in order to estimate the depth of the scene. Chapter eight shows how the 3D reconstruction is finally done. Chapter nine talks about our conclusions and how the results could improve. Both theoretical and experimental parts of this project cover the key points of 3d reconstruction. The results of the experiments show that the existing methods are satisfying but could improve more. We want to thank our supervisor professor Mr. Dermatas for his collaboration and his understanding.

Μια από τις συνεχώς εξελισσόμενες περιοχές της επιστήμης των υπολογιστών είναι η Υπολογιστική Όραση, σκοπός της οποίας είναι η δημιουργία έξυπνων συστημάτων για την ανάκτηση πληροφοριών από πραγματικές εικόνες. Πολλές σύγχρονες εφαρμογές της υπολογιστικής όρασης βασίζονται στην αντιστοίχιση εικόνων. Την πλειοψηφία των αλγορίθμων αντιστοίχισης συνθέτουν παραμετρικές τεχνικές, σύμφωνα με τις οποίες υιοθετείται ένα παραμετρικό μοντέλο, το οποίο εφαρμοζόμενο στη μια εικόνα δύναται να παρέχει μια προσέγγιση της άλλης. Στο πλαίσιο της διατριβής μελετάται εκτενώς το πρόβλημα της Στερεοσκοπικής Αντιστοίχισης και το γενικό πρόβλημα της Ευθυγράμμισης Εικόνων. Για την αντιμετώπιση του πρώτου προβλήματος προτείνεται ένας τοπικός αλγόριθμος διαφορικής αντιστοίχισης που κάνει χρήση μιας νέας συνάρτησης κόστους, του Τροποποιημένου Συντελεστή Συσχέτισης (ECC), η οποία ενσωματώνει το παραμετρικό μοντέλο μετατόπισης στον κλασικό συντελεστή συσχέτισης. Η ενσωμάτωση αυτή καθιστά τη νέα συνάρτηση κατάλληλη για εκτιμήσεις ανομοιότητας με ακρίβεια μικρότερη από αυτήν του εικονοστοιχείου. Αν και η συνάρτηση αυτή είναι μη γραμμική ως προς την παράμετρο μετατόπισης, το πρόβλημα μεγιστοποίησης έχει κλειστού τύπου λύση με αποτέλεσμα τη μειωμένη πολυπλοκότητα της διαδικασίας της αντιστοίχισης με ακρίβεια υπο-εικονοστοιχείου. Ο προτεινόμενος αλγόριθμος παρέχει ακριβή αποτελέσματα ακόμα και κάτω από μη γραμμικές φωτομετρικές παραμορφώσεις, ενώ η απόδοσή του υπερτερεί έναντι γνωστών στη διεθνή βιβλιογραφία τεχνικών αντιστοίχισης ενώ φαίνεται να είναι απαλλαγμένος από το φαινόμενο pixel locking. Στην περίπτωση του προβλήματος της ευθυγράμμισης εικόνων, η προτεινόμενη συνάρτηση γενικεύεται με αποτέλεσμα τη δυνατότητα χρήσης οποιουδήποτε δισδιάστατου μετασχηματισμού. Η μεγιστοποίησή της, η οποία αποτελεί ένα μη γραμμικό πρόβλημα, επιτυγχάνεται μέσω της επίλυσης μιας ακολουθίας υπο-προβλημάτων βελτιστοποίησης. Σε κάθε επανάληψη επιβάλλεται η μεγιστοποίηση μιας μη γραμμικής συνάρτησης του διανύσματος διορθώσεων των παραμέτρων, η οποία αποδεικνύεται ότι καταλήγει στη λύση ενός γραμμικού συστήματος. Δύο εκδόσεις του σχήματος αυτού προτείνονται: ο αλγόριθμος Forwards Additive ECC (FA-ECC) και o αποδοτικός υπολογιστικά αλγόριθμος Inverse Compositional ECC (IC-ECC). Τα προτεινόμενα σχήματα συγκρίνονται με τα αντίστοιχα (FA-LK και SIC) του αλγόριθμου Lucas-Kanade, ο οποίος αποτελεί σημείο αναφοράς στη σχετική βιβλιογραφία, μέσα από μια σειρά πειραμάτων. Ο αλγόριθμος FA-ECC παρουσιάζει όμοια πολυπλοκότητα με τον ευρέως χρησιμοποιούμενο αλγόριθμο FA-LΚ και παρέχει πιο ακριβή αποτελέσματα ενώ συγκλίνει με αισθητά μεγαλύτερη πιθανότητα και ταχύτητα. Παράλληλα, παρουσιάζεται πιο εύρωστος σε περιπτώσεις παρουσίας προσθετικού θορύβου, φωτομετρικών παραμορφώσεων και υπερ-μοντελοποίησης της γεωμετρικής παραμόρφωσης των εικόνων. Ο αλγόριθμος IC-ECC κάνει χρήση της αντίστροφης λογικής, η οποία στηρίζεται στην αλλαγή των ρόλων των εικόνων αντιστοίχισης και συνδυάζει τον κανόνα ενημέρωσης των παραμέτρων μέσω της σύνθεσης των μετασχηματισμών. Τα δύο αυτά χαρακτηριστικά έχουν ως αποτέλεσμα τη δραστική μείωση του υπολογιστικού κόστους, ακόμα και σε σχέση με τον SIC αλγόριθμο, με τον οποίο βέβαια παρουσιάζει παρόμοια συμπεριφορά. Αν και ο αλγόριθμος FA-ECC γενικά υπερτερεί έναντι των τριών άλλων αλγορίθμων, η επιλογή μεταξύ των δύο προτεινόμενων σχημάτων εξαρτάται από το λόγο μεταξύ ακρίβειας αντιστοίχισης και υπολογιστικού κόστους. / Computer Vision has been recently one of the most active research areas in computer society. Many modern computer vision applications require the solution of the well known image registration problem which consist in finding correspondences between projections of the same scene. The majority of registration algorithms adopt a specific parametric transformation model, which is applied to one image, thus providing an approach of the other one. Towards the solution of the Stereo Correspondence problem, where the goal is the construction of the disparity map, a local differential algorithm is proposed which involves a new similarity criterion, the Enhanced Correlation Coefficient (ECC). This criterion is invariant to linear photometric distortions and results from the incorporation of a single parameter model into the classical correlation coefficient, defining thus a continuous objective function. Although the objective function is non-linear in translation parameter, its maximization results in a closed form solution, saving thus much computational burden. The proposed algorithm provides accurate results even under non-linear photometric distortions and its performance is superior to well known conventional stereo correspondence techniques. In addition, the proposed technique seems not to suffer from pixel locking effect and outperforms even stereo techniques, dedicated to the cancellation of this effect. For the image alignment problem, the maximization of a generalized version of ECC function that incorporates any 2D warp transformation is proposed. Although this function is a highly non-linear function of the warp parameters, an efficient iterative scheme for its maximization is developed. In each iteration of the new scheme, an efficient approximation of the nonlinear objective function is used leading to a closed form solution of low computational complexity. Two different iterative schemes are proposed; the Forwards Additive ECC (FA-ECC) and the Inverse Compositional ECC (IC-ECC) algorithm. Τhe proposed iterative schemes are compared with the corresponding schemes (FA-LK and SIC) of the leading Lucas-Kanade algorithm, through a series of experiments. FA-ECC algorithm makes use of the known additive parameter update rule and its computational cost is similar to the one required by the most widely used FA-LK algorithm. The proposed iterative scheme exhibits increased learning ability, since it converges faster with higher probability. This superiority is retained even in presence of additive noise and photometric distortion, as well as in cases of over-modelling the geometric distortion of the images. On the other hand, IC-ECC algorithm makes use of inverse logic by swapping the role of images and adopts the transformation composition update rule. As a consequence of these two options, the complexity per iteration is drastically reduced and the resulting algorithm constitutes the most computationally efficient scheme than three other above mentioned algorithms. However, empirical learning curves and probability of convergence scores indicate that the proposed algorithm has a similar performance to the one exhibited by SIC. Though FA-ECC seems to be clearly more robust in real situation conditions among all the above mentioned alignment algorithms, the choice between two proposed schemes necessitates a trade-off between accuracy and speed.