Εύρωστη εκτίμηση από μετρήσεις γραμμικών αισθητήρων

Abstract

Ως εύρωστη εκτίμηση (robust estimation) χαρακτηρίζεται το πρόβλημα του προσδιορισμού ενός μοντέλου βασιζόμενο σε ένα σύνολο μετρήσεων. Ένας διαδεδομένος αλγόριθμος που χρησιμοποιείται για την εύρωστη εκτίμηση είναι ο αλγόριθμος RANSAC. Αποτελεί έναν επαναληπτικό αλγόριθμο κατά τον οποίο όλα τα στοιχεία του συνόλου ελέγχονται αν επαληθεύουν κάποιο μοντέλο, το οποίο έχει προσδιοριστεί από ένα τυχαίο δείγμα. Χρησιμοποιώντας έναν αριθμό από διαφορετικά τυχαία δείγματα προσδιορίζονται διαφορετικά μοντέλα από τα οποία θεωρείται ως πιο εύρωστο αυτό που επαληθεύει τον μεγαλύτερο αριθμό δειγμάτων του συνόλου. Η κλασικότερη εφαρμογή του RANSAC είναι η εκτίμηση μιας ευθείας από ένα σύνολο σημείων. Ωστόσο, ο αλγόριθμος βρίσκει εφαρμογή σε αλγόριθμους επεξεργασίας εικόνας όπως στην απομάκρυνση εσφαλμένων αντιστοιχιών παρόμοιων εικόνων, στην ευθυγράμμιση εικόνων, στην ιχνηλάτιση οφθαλμού κ.λπ. Στα πλαίσια της παρούσας εργασίας πραγματοποιήθηκε ο σχεδιασμός ελεγκτή σε VHDL που υλοποιεί τον αλγόριθμο RANSAC για την περίπτωση εκτίμησης ευθείας από σύνολο σημείων. Ο ελεγκτής σχεδιάστηκε με τέτοιο τρόπο ώστε να μπορεί να χρησιμοποιηθεί ως component από άλλες εφαρμογές ρομποτικής όρασης. Το σχεδιαζόμενο μοντέλο λαμβάνει ως είσοδο τα σημεία από τα οποία ζητείται να υπολογιστεί η ευθεία και παράγει ως έξοδο τις παραμέτρους a, b και c της βέλτιστης ευθείας. Επίσης, ήταν επιθυμητό να συγκριθούν δύο υλοποιήσεις. Ασύγχρονος υπολογισμός των παραμέτρων σε παλμό 1 ρολογιού, και συγχρονισμένος διαβάζοντας τις μετρήσεις μία προς μία. Η σύγκριση περιλάμβανε το χρόνο και τους δεσμευμένους πόρους που απαιτούνται στις δύο υλοποιήσεις. Τέλος, αναπτύχθηκε αρχείο δοκιμών (test bench) για τον έλεγχο της σωστής λειτουργίας του component.

Robust estimation is the problem of defining a model based on a set of measurements. A common algorithm used for robust estimation is the RANSAC algorithm. It is an iterative algorithm in which all the elements of the set are checked to verify a model that has been identified from a random sample. Using a number of different random samples, different models are identified, of which the one that verifies the largest number of samples in the set is considered the most robust. The most common use of RANSAC is to estimate a line from a set of points. However, the algorithm is met in image processing algorithms such as the removal of erroneous matches of similar images, image alignment, eye tracking, etc. The controller was designed in such a way that it can be used as a component by other robotic vision applications. A testbench was also developed to verify the functional operation of the component. In the context of this work, the design of a controller in VHDL that implement the RANSAC algorithm for the case of line estimation from a set of points was realized. The design receive as input the coordinates of the points and extracts the a, b, and c parameters of the best line fit. We compare two implementations. In the first one, we include asynchronous calculation of parameters and inliers check in one pulse clock. In the second one, random samples and verification for inliers are performed using sequential structures. The comparison will essentially include the proportion of time required for the reserved resources. Finally, a test bench was developed to chek the proper operation of the component.