Αντικείμενο αυτής της διπλωματικής εργασίας είναι η εύρεση της θέσης ενός κινούμενου ρομπότ. Για το σκοπό αυτό, χρησιμοποιείται ένα στερεοσκοπικό σύστημα όμοιων καμερών (web-cameras) υπό γωνία μεταξύ τους. Κάθε μια εκ των 2 καμερών λαμβάνει μια ακολουθία φωτογραφιών σε κοινό χρόνο. Η εύρεση της θέσης γίνεται με τη μέθοδο της τριγωνοποίησης (triangulation), η οποία δίνει τις συντεταγμένες του κινούμενου αντικειμένου μέσω ομοίων τριγώνων που σχηματίζονται από τα 2 επίπεδα των φωτογραφιών (image planes), την ευθεία που ενώνει τα κέντρα των 2 καμερών καθώς και από το ίδιο το κινούμενο αντικείμενο. Ωστόσο, η γεωμετρική αυτή μέθοδος εφαρμόζεται σε φωτογραφίες που έχουν ληφθεί με παράλληλες κάμερες. Για τον λόγο αυτό, εφαρμόζεται η μέθοδος της διόρθωσης εικόνας (image rectification) η οποία μετασχηματίζει τις εικόνες έτσι ώστε να είναι σα να έχουν ληφθεί από παράλληλες κάμερες. Στη συνέχεια εντοπίζεται το κινούμενο αντικείμενο με μορφολογική επεξεργασία εικόνας, υπολογίζεται το κέντρο βάρους του και γίνεται η τριγωνοποίηση γεωμετρικά. Στην προαναφερθείσα διαδικασία, θεωρούνται γνωστά τα εσωτερικά στοιχεία των καμερών και η μεταξύ τους απόσταση. Επιπλέον, θεωρείται ότι όλος ο όγκος του ρομπότ αναπαρίσταται απο ένα σημείο P με συντεταγμένες (X,Y,Z) ως προς σύστημα συντεταγμένων με αρχή το κέντρο προβολής της αριστερής κάμερας. / The objective of this thesis is the position estimation of a moving robot. For this purpose, a stereoscopic system of two identical, non-parallel cameras has been used (web-cameras). Each of the two cameras takes a photo synchronized sequence. The position of the robot has been estimated with the method of triangulation, which computes the coordinates of the moving object via similar triangles formed by the two image planes, the straight line joining the centres of the cameras and by the moving object. However, triangulation is applicable to images acquired by parallel cameras. For this reason, the images have been rectified. Image rectification is a transformation process that is used to project two-or-more images onto a common image. Then, the moving object is detected with morphological image processing techniques, its centroid is calculated and finally triangulation has been applied. The intrinsic parameters of the cameras and the distance between them are known. Furthermore, we consider that the entire volume of the robot is represented by a point P with coordinates (X, Y, Z) with respect to the left camera coordinate system.

Μια γρήγορη επίλυση του Delaunay Τριγωνισμός (DT) πρόβληματος αποτελεί ένα από τα βασικά συστατικά σε πολλές θεωριτικές και πρακτικές εφαρμογές. Οι υπάρχουσες μονάδες επεξεργασίας γραφικών (GPU), με βάση τις εφαρμογές των αλγορίθμων DT πάσχουν από δύο σοβαρά μειονεκτήματα. Το πρώτο σχετίζεται με την εξάρτηση του αλγορίθμου καθοδήγηση της GPU από την CPU για τους υπολογισμούς. Το δεύτερο πιο σοβαρό μειονέκτημα είναι η εξάρτησή τους από τη διανομή του σημειοσύνολου εισόδου. Οι περισσότεροι αλγορίθμοι για GPU έχουν καλή απόδοση μόνο με ομοιόμορφες κατανομές σημειοσύνολον. Προτείνουμε ένα καινούριο αλγόριθμο που δεν πάσχουν από τα παραπάνω προβλήματα. / A Fast solver of Delaunay Triangulation (DT) problem constitutes one of the basic ingredients in many practical and sientific applications. Existing Graphics Processing Units (GPU) based implementations of DT algorithms suffer from two serious drawbacks. The first is related to the dependency of the CPU guidance algorithm on GPU calculations. Albeit the modern GPUs have high computational throughput, if the feedback from CPU is necessary for the algorithmic evolution, the overhead caused by CPU-GPU communication can seriously degrade the performance. The second most serious drawback is their dependency on the distribution of the given point-set. Most of the GPU-based implementations can optimally run only on uniformly distributed point-sets, however, in many practical applications this is not the case.