Ανάπτυξη αποδοτικών ευφυών ταξινομητών και εφαρμογή τους στην όραση μηχανών

Abstract

A crucial part of a modern and intelligent system is the pattern classification procedure. This process is being performed by using special devices called Classifiers, which have specific structure and their main function is to classify the patterns, presented as inputs. In the present dissertation, new methods which ensure a more efficient operation of the intelligent classifiers, by incorporating in different processing stages, are presented. The most significant processing part of a modern pattern classification system, is the feature extraction procedure, since the extracted features enclose useful information about the patterns being classified. Therefore, the used feature extraction method, significantly determines the performance of the classifier in operation. By selecting orthogonal moments as discriminative features, a detailed study of the numerical behaviour of the recursive algorithms, used to compute the orthogonal moments present, is taking place through this dissertation. This study focuses in, the so called finite precision errors. The appropriate conditions under which the finite precision errors being generated and propagated are defined and the need of developing more numerical stable algorithms seems to be of major importance. Two novel algorithms, which do not present finite precision errors and which ensure the accurate and fast computation of Zernike, Pseudo-Zernike and Fourier- Mellin orthogonal moments are being introduced. The first type of algorithms proposed in this dissertation, computes the orthogonal moments, approximately. The computational complexity of the most consumptive terms of these algorithms is of Ο(log2(p)) order, while the corresponding complexity of the conventional methods is O(p). This complexity reduction, in conjunction with the small numerical errors, makes the proposed algorithms appropriate for pattern recognition applications. The second type of algorithms performs better than the first one, since it computes the exact moment values recursively in a short time. The corresponding computational complexity of these algorithms is O(1), which means that the computation of the most consumptive term is constant and independent of the moment order. Moreover, a new feature extraction method based on orthogonal moments, which produces high discriminative features called compressed features, is also introduced in the present dissertation. More precisely, by having as main objective the construction of high discriminative feature vectors having low dimension, wavelet compression is applied to an appropriate one dimensional signal consisting of the magnitudes of the orthogonal moments. The remaining compressed wavelet coefficients constitute the novel features of high discriminative power, since they describe a signal moment that includes moments of high orders. An improved version of the above methodology, where an extra processing step is added, the smoothing of the moment signal, achieves very high compression ratios, up to 75%. Another two factors which determine the performance of an intelligent classifier, apart from the feature extraction procedure, are its learning algorithm and its architecture. As far as the first factor is concerned, the present dissertation proposes the usage of a hybrid learning algorithm for training a neural classifier, which accelerates the learning process. The proposed hybrid algorithm is a combination of the backpropagation algorithm and the genetic algorithms, in such a way that we could take advantage of their properties. According to this algorithm, firstly the genetic algorithm finds a candidate solution, by searching globally in the search space and then the backpropagation algorithm operates locally, in a small region, in order to find the optimal solution. As far as the architecture of the classifier is concerned, the present dissertation proposes new hybrid structures which ensure the high performance of the classifiers, in machine vision applications. ....................

Σημαντικό μέρος ενός σύγχρονου και ευφυούς συστήματος, αποτελεί η διαδικασία ταξινόμησης των προτύπων που στοιχειοθετούν μία εφαρμογή. Η διαδικασία της ταξινόμησης, πραγματοποιείται με τη χρήση ειδικών διατάξεων, που ονομάζονται Ταξινομητές, οι οποίοι έχουν συγκεκριμένη αρχιτεκτονική και κύρια λειτουργία, την κατηγοριοποίηση των προτύπων που εμφανίζονται στην είσοδο τους. Στην παρούσα διατριβή παρουσιάζονται μέθοδοι και διαδικασίες οι οποίες εξασφαλίζουν την αποδοτικότερη λειτουργία των ευφυών ταξινομητών, επεμβαίνοντας καθεμία σε διαφορετικά στάδια επεξεργασίας. Το σημαντικότερο τμήμα επεξεργασίας από το οποίο αποτελείται ένα σύγχρονο σύστημα ταξινόμησης, είναι η διαδικασία εξαγωγής των χαρακτηριστικών διάκρισης και αυτό, γιατί τα χαρακτηριστικά διάκρισης περικλείουν όλη την απαραίτητη πληροφορία για την φύση των προς ταξινόμηση προτύπων. Η διαδικασία εξαγωγής των χαρακτηριστικών καθορίζει σε μεγάλο βαθμό και την απόδοση λειτουργίας του χρησιμοποιούμενου ταξινομητή. Επιλέγοντας ως χρησιμοποιούμενα χαρακτηριστικά διάκρισης τις ορθογώνιες ροπές, στα πλαίσια της παρούσας διατριβής έχει πραγματοποιηθεί μία αναλυτική μελέτη της αριθμητικής συμπεριφοράς των αναδρομικών αλγορίθμων υπολογισμού των ορθογώνιων ροπών. Η μελέτη αυτή ανέδειξε την ύπαρξη σφάλματος λόγω πεπερασμένης ακρίβειας που εμφανίζεται κατά τον υπολογισμό των ορθογώνιων ροπών. Μέσα από αυτή την διερεύνηση, ορίζονται οι κατάλληλες συνθήκες κάτω από τις οποίες δημιουργούνται και διαδίδονται τα σφάλματα πεπερασμένης ακρίβειας, ενώ η ανάγκη ανάπτυξης περισσότερο ευσταθών αλγορίθμων υπολογισμού των ροπών, διαφαίνεται άκρως σημαντική. Ως εναλλακτικές μέθοδοι υπολογισμού των Zernike, Pseudo-Zernike και Fourier- Mellin ορθογώνιων ροπών, οι οποίες δεν παρουσιάζουν την παραπάνω ευπάθεια των αναδρομικών αλγορίθμων, προτείνονται δύο νέες μεθοδολογίες οι οποίες εξασφαλίζουν τον ακριβή και ταχύ υπολογισμό των ροπών αυτών. Η πρώτη προτεινόμενη κατηγορία αλγορίθμων, υπολογίζει κατά προσέγγιση της ορθογώνιες ροπές, όπου ο πιο χρονοβόρος όρος υπολογίζεται με πολυπλοκότητα τάξης Ο(log2(p)), όταν η αντίστοιχη πολυπλοκότητα του συμβατικού αλγορίθμου είναι O(p). Αυτή η μείωση της πολυπλοκότητας, σε συνδυασμό με το γεγονός ότι τα προσεγγιστικά σφάλματα υπολογισμού των ροπών διατηρούνται σε χαμηλά επίπεδα, προσδίδουν στους αλγορίθμους αυτούς σημαντική χρησιμότητα σε εφαρμογές αναγνώρισης προτύπων. Η δεύτερη κατηγορία αλγορίθμων, παρουσιάζει καλύτερη συμπεριφορά από την πρώτη, αφού υπολογίζει τις ακριβείς τιμές των ροπών με αναδρομικό τρόπο σε πολύ μικρό χρόνο. Η αντίστοιχη υπολογιστική πολυπλοκότητα των αλγορίθμων αυτών είναι O(1), πράγμα που σημαίνει ότι ο υπολογισμός του πιο χρονοβόρου όρου γίνεται σε σταθερό χρόνο ανεξάρτητα από την τάξη της ροπής. Επιπλέον, στα πλαίσια αυτής της διατριβής εισάγεται μία καινούρια μέθοδος εξαγωγής χαρακτηριστικών τα οποία βασίζονται στις ροπές και ονομάζονται συμπιεσμένα χαρακτηριστικά διάκρισης. Πιο συγκεκριμένα, με βασικό σκοπό την κατασκευή διανυσμάτων χαρακτηριστικών μεγάλης διακριτικής ικανότητας και μικρής διάστασης, εφαρμόζεται η μέθοδος της συμπίεσης με τη χρήση των κυματιδίων (wavelets) σε ένα κατάλληλα σχηματισμένο σήμα αποτελούμενο από τα πλάτη των ορθογώνιων ροπών. Οι εναπομείναντες συμπιεσμένοι συντελεστές κυματιδίου αποτελούν τα νέα χαρακτηριστικά διάκρισης, τα οποία χαρακτηρίζονται από υψηλή διακριτική ικανότητα αφού περιγράφουν ένα σήμα ροπών που αποτελείται από ροπές υψηλών τάξεων. Μία παραλλαγή της παραπάνω μεθόδου στην οποία εφαρμόζεται ένα επιπλέον στάδιο επεξεργασίας, η ομαλοποίηση του σήματος των ροπών, επιτρέπει την επίτευξη πολύ υψηλών ποσοστών συμπίεσης, της τάξεως του 75%. Δύο ακόμη παράγοντες που καθορίζουν την απόδοση ενός ευφυούς ταξινομητή, εκτός από την εξαγωγή των χαρακτηριστικών, είναι ο αλγόριθμος με τον οποίο εκπαιδεύεται και η αρχιτεκτονική δομή του. .............................