Επιτάχυνση εκτέλεσης προηγμένων αλγορίθμων επεξεργασίας εικόνας και βίντεο σε επαναδιαμορφούμενο υλικό (FPGA), για εφαρμογές ρομποτικής όρασης

Abstract

A fundamental problem in computer vision is finding correspondences between similar images. Image features extraction and their use to establish correspondences improve the matching process. In the literature, several feature extraction algorithms have been proposed. One of the most reliable and robust algorithms is SIFT (Scale Invariant Feature Transform). However, SIFT is computationally demanding and it is rarely used in real-time applications. In this PHD thesis, an FPGA-based architecture for real-time SIFT extraction and matching is presented. The SIFT detector and descriptor modules are fully pipelined in pixel basis. The proposed SIFT matcher was implemented with the same pipelined design concept. In order to remove the false matches, RANSAC (random sample consensus) algorithm is applied in the last step. RANSAC is an iterative and computationally demanding algorithm. Although its execution is time consuming, it is parallelized in a significant degree and its completion requires only a few clock cycles. In conclusion, the architecture includes all the necessary steps from the image capture, up to the establishment of the correct correspondences. The architecture includes various customized controllers, which have been designed to minimize the required resources from the FPGA device. The main controller is the frame grabber which captures the incoming frames from the CMOS image sensor. It consists of the I2C controller, the Bayer decoder as well as the VGA controller which is used for visual verification. The I2C controller configures the CMOS image sensor, while the Bayer decoder extracts pixel intensities from Bayer encoding. Furthermore, controllers such as SPI master and FIFO-to-USB have been developed in order to communicate with external devices. The last but not the least controller is the SDR SDRAM controller, which has been designed in order to store image results to external RAM. Regarding the SIFT detector, two main originalities have been presented. Firstly, an improved method for the Gaussian scale space construction is proposed. In the literature, the cascade scheme is usually met, in which every Gaussian image is produced from the previous one by applying convolution with a kernel of fixed standard deviation. In the proposed architecture, convolutions are applied to the initial image with progressively increased standard deviation. In this way, the memory resources required from the FPGA are reduced. Moreover, when more than four scales are demanded, the reuse of previously calculated Gaussians is feasible so that more efficient resource management can be achieved. The proposed convolution scheme also saves hardware multipliers in comparison with the widely used separable Gaussian scheme. Those improvements in resource usage do not degrade SIFT performance. A significant contribution of this PHD thesis to the state of the art constitutes the fully pipelined architecture of the SIFT extraction. The proposed scheme is capable to extract one descriptor vector per clock cycle. As pixel data from CMOS sensor is read in a streaming manner, the architecture extracts descriptors in a streaming manner too. The same principle is followed in the matcher scheme. The descriptor of each detected feature in the current frame is compared with feature descriptors of the previous frame and the match, if exists, is identified in one clock cycle. It should be also noticed that RANSAC algorithm has been parallelized in a significant degree. RANSAC is usually executed iteratively and considerable time is required for its completion. In the literature, we meet papers in which only a few random samples are selected to compute the transformation matrix, in order to reduce the processing time. However, this leads to accuracy reduction in false correspondences removal process. In the proposed RANSAC implementation, real-time requirements are met even if all random samples are used to calculate the transformation matrix. When all random samples are used, then the best accuracy in transformation matrix computation can be derived. The proposed architecture achieves significant acceleration in the execution of the SIFT algorithm. The descriptor processing time was estimated 40ns, considering use of Cyclone IV FPGA technology. That is 50 times faster than the current state of the art papers. In order to produce one correspondence, the matcher scheme requires processing time 80ns. As a result, the processing rate of the complete SIFT detector/descriptor/matcher is 40 fps, when it is applied to images with resolution of 640 x 480 pixels. The aforementioned processing rate meets real-time requirements.

Το πρόβλημα της εύρεσης αντιστοιχιών ανάμεσα σε παρόμοιες εικόνες αποτελεί ένα από τα πιο πολυσύνθετα και δύσκολα προβλήματα στην επεξεργασία εικόνας. Η εξαγωγή χαρακτηριστικών σημείων εικόνων και η χρήση τους για την εύρεση των αντιστοιχιών αποτελεί μία μεθοδολογία που βελτιώνει την αξιοπιστία της διαδικασίας αντιστοίχησης. Στη βιβλιογραφία μπορούν να εντοπιστούν αρκετοί αλγόριθμοι για την εξαγωγή χαρακτηριστικών σημείων. Ένας από τους πιο αξιόπιστους και ακριβείς αλγορίθμους είναι ο αλγόριθμος SIFT (Scale Invariant Feature Transform). Ωστόσο, η εκτέλεσή του προϋποθέτει ιδιαίτερα απαιτητικούς υπολογισμούς και η χρήση του σε εφαρμογές πραγματικού χρόνου θα μπορούσε να χαρακτηριστεί ως αναποτελεσματική. Στα πλαίσια της παρούσας διδακτορικής διατριβής περιγράφεται η υλοποίηση σε FPGA ενός επιταχυντή για την εύρεση αντιστοιχιών ανάμεσα σε διαδοχικά πλαίσια βίντεο, χρησιμοποιώντας τα χαρακτηριστικά σημεία SIFT. Ο προτεινόμενος επιταχυντής σε FPGA πραγματοποιεί ανίχνευση και εξαγωγή των χαρακτηριστικών SIFT μέσα από μια πλήρως παραλληλισμένη (pipelined) αρχιτεκτονική. Επίσης, περιλαμβάνει τη διαδικασία αντιστοίχησης (matching) των χαρακτηριστικών σημείων ανάμεσα σε δύο πλαίσια βίντεο, η οποία σχεδιάστηκε με την αρχή να ακολουθεί την παραλληλισμένη αρχιτεκτονική των προηγούμενων βαθμίδων. Στην τελευταία βαθμίδα του επιταχυντή, εφαρμόζεται ο αλγόριθμος RANSAC (random sample consensus) για την απομάκρυνση των εσφαλμένων αντιστοιχιών. Ο RANSAC, αν και αποτελεί έναν επαναληπτικό αλγόριθμο ιδιαίτερα απαιτητικό, είναι επίσης παραλληλισμένος σε μεγάλο βαθμό και η ολοκλήρωση της εκτέλεσής του απαιτεί μερικούς κύκλους ρολογιού. Συνοψίζοντας, η αρχιτεκτονική του επιταχυντή περιλαμβάνει όλα τα στάδια που απαιτούνται από τη σύλληψη της εικόνας μέχρι και την εξαγωγή των σωστών αντιστοιχιών. Ο επιταχυντής περιλαμβάνει μία σειρά από ελεγκτές που αναπτύχθηκαν με στόχο την ελαχιστοποίηση των πόρων που απαιτούνται στο FPGA. Ο κυριότερος ελεγκτής είναι ο ελεγκτής σύλληψης των εισερχόμενων πλαισίων βίντεο (frame grabber) από την κάμερα (CMOS αισθητήρας εικόνας). Περιλαμβάνει τον ελεγκτή (I2C controller) για τη ρύθμιση της κάμερας, τον ελεγκτή για την εξαγωγή της φωτεινότητας των εικονοστοιχείων από την κωδικοποίηση Bayer, καθώς επίσης και έναν ελεγκτή VGA για οπτική επαλήθευση. Επιπλέον, για χρήση σε διάφορες λειτουργίες του επιταχυντή υλοποιήθηκαν οι ελεγκτές SPI master, ελεγκτής επικοινωνίας με συσκευή USB και ο ελεγκτής μνήμης SDR SDRAM. Στην παρούσα διατριβή προτείνονται δύο βασικές πρωτοτυπίες ως προς τον τρόπο που υλοποιείται ο ανιχνευτής SIFT (SIFT detector). Αρχικά προτείνεται μια διαφορετική τεχνική για τη δημιουργία του χώρου κλιμάκωσης (scale space). Στη βιβλιογραφία, συνήθως, συναντάται το σχήμα καταρράκτη (cascade scheme) όπου κάθε επόμενη γκαουσιανή προκύπτει από την γκαουσιανή της προηγούμενης κλίμακας. Ο προτεινόμενος επιταχυντής χρησιμοποιεί μια μέθοδο εφαρμόζοντας γκαουσιανά φίλτρα στην ίδια αρχική εικόνα με προσεκτικά επιλεγμένη την τυπική απόκλιση. Με τον τρόπο αυτό επιτυγχάνεται μείωση της απαιτούμενης μνήμης στο FPGA. Επιπλέον, με το σχήμα αυτό είναι δυνατή η επαναχρησιμοποίηση των γκαουσιανών όταν ζητούνται περισσότερες κλίμακες. Η δεύτερη πρωτοτυπία βασίζεται στον τρόπο που υλοποιείται η συνέλιξη. Συνήθως στη βιβλιογραφία συναντάται το σχήμα της διαχωρίσιμης συνέλιξης. Με το σχήμα που υλοποιείται στον επιταχυντή γίνεται εξοικονόμηση πολλαπλασιαστών, χωρίς απώλεια της ακρίβειας στον αλγόριθμο SIFT. Μια σημαντική συνεισφορά της διατριβής αποτελεί ο πλήρης παραλληλισμός του αλγορίθμου εξαγωγής χαρακτηριστικών σημείων SIFT. Η προτεινόμενη αρχιτεκτονική έχει τη δυνατότητα να εξάγει έναν περιγραφέα ανά παλμό ρολογιού. Καθώς διαβάζονται τα εικονοστοιχεία από την κάμερα με τη μορφή streaming, με τον ίδιο ρυθμό γίνεται και η εξαγωγή χαρακτηριστικών σημείων (SIFT detector/descriptor), αναφερόμενοι σε άλλα εικονοστοιχεία που διαβάστηκαν σε προηγούμενο χρόνο. Με την ίδια αρχή είναι σχεδιασμένο στον επιταχυντή και τo κύκλωμα εύρεσης αντιστοιχιών. Κάθε νέο χαρακτηριστικό, που λαμβάνεται από το τρέχον πλαίσιο βίντεο, συγκρίνεται με αποθηκευμένα χαρακτηριστικά του προηγούμενου πλαισίου και η αντιστοίχηση, αν υπάρχει, εξάγεται σε 1 παλμό ρολογιού. Θα πρέπει να αναφερθεί ότι πολύ σημαντικός είναι και ο βαθμός στον οποίο έχει παραλληλιστεί ο RANSAC. Ο RANSAC συνήθως εκτελείται επαναληπτικά και απαιτείται υπολογίσιμος χρόνος για την ολοκλήρωσή του. Για την ελάττωση του χρόνου εκτέλεσης του RANSAC, πολλές φορές χρησιμοποιούνται λιγότερα τυχαία δείγματα για τον υπολογισμό του πίνακα μετασχηματισμού. Αυτό όμως μπορεί να οδηγήσει σε μείωση της ακρίβειας στην απομάκρυνση των εσφαλμένων αντιστοιχιών, καθώς μπορεί να απορριφθούν και πραγματικές αντιστοιχήσεις. Με την προτεινόμενη υλοποίηση του RANSAC είναι δυνατή η εκτέλεση του αλγορίθμου χρησιμοποιώντας όλους τους δυνατούς συνδυασμούς των αντιστοιχιών ως τυχαία δείγματα, κάτι που προσδίδει τη μέγιστη δυνατή ακρίβεια στον πίνακα μετασχηματισμού. Η επιτάχυνση που επιτυγχάνεται στην εκτέλεση του αλγορίθμου SIFT είναι ιδιαίτερα σημαντική. Να σημειωθεί ότι ο χρόνος εξαγωγής ενός περιγραφέα SIFT υπολογίστηκε στα 40ns, περίπου 50 φορές μικρότερος σε σύγκριση με εργασίες οι οποίες υλοποιούν τον αλγόριθμο χρησιμοποιώντας μηχανές καταστάσεων (state machines). Επιπλέον, παρουσιάζεται για πρώτη φορά στη βιβλιογραφία κύκλωμα εύρεσης αντιστοιχιών, το οποίο έχει τη δυνατότητα να υπολογίζει μια αντιστοιχία σε χρόνο 80ns. Η συνολική αρχιτεκτονική ανιχνευτή/περιγραφέα/κυκλώματος εύρεσης αντιστοιχιών μπορεί να φιλοξενηθεί σε FPGA μεσαίας κλίμακας, όπως της οικογένειας Cyclone IV της Altera. Περισσότερα για την υλοποίηση των παραπάνω δίνονται στα κεφάλαια που ακολουθούν. Στο πρώτο κεφάλαιο γίνεται μια εισαγωγή στους αλγορίθμους εξαγωγής χαρακτηριστικών σημείων σε εικόνες. Στο δεύτερο κεφάλαιο παρουσιάζεται η δομή του επιταχυντή και οι ελεγκτές που υλοποιούν τις βασικές λειτουργίες. Στο τρίτο κεφάλαιο αναλύεται ο ανιχνευτής και ο περιγραφέας των χαρακτηριστικών σημείων SIFT. Στο τέταρτο κεφάλαιο παρουσιάζεται το κύκλωμα εύρεσης αντιστοιχιών των χαρακτηριστικών σημείων (SIFT matcher). Στο πέμπτο κεφάλαιο δίνονται οι λεπτομέρειες υλοποίησης για τις αρχιτεκτονικές του RANSAC. Στο έκτο κεφάλαιο παρουσιάζονται τα συμπεράσματα και αναλύονται προοπτικές μελλοντικής έρευνας.