Τεχνικές ομαδοποίησης και ταξινόμησης με εφαρμογές στην ανθρωποκεντρική ανάλυση εικόνων και εικονοσειρών

Abstract

In this doctoral thesis, we present the results of the research conducted in the fields of data clustering and classification with applications in anthropocentric analysis of images and video. Our main contribution to the field of classification consists of the introduction of an image searching data structure based on binary search trees for quick shape matching. According to the properties of a balanced binary search tree, we can insert, search and delete shapes in logarithmic time. In each node of the tree, a weak classifier decides which path it should direct the search. In its initial form, the tree is constructed incrementally. Starting from an empty tree, the data structure is filled in by inserting the shapes into the tree. The classifiers in each node are trained using a simple and quick training algorithm. The evolution of these tree takes advantage of the entire training set, aiming to improve the speed and performance of the proposed data structure. The construction of the tree and the training of the nodes are implemented with more sophisticated algorithms. The training algorithm of the classifiers maximizes the a posteriori probability that an input shape is directed to the correct subtree based on the shape templates that are contained in each subtree. The tree construction algorithm organizes the shape templates in such a way, that the training of each classifier is as easy as possible, while maintaining the balance of the tree. Consequently, we present our contributions to the field of similarity matrix based data clustering. Our first and most important contribution in this field concerns the trimming of the kernel matrix used by the kernel k-means algorithm. The proposed trimming algorithm attempts to estimate the cardinality of the cluster that each sample belongs to and trims the corresponding matrix row based on this estimation. This results in the reduction of the kernel matrix size and the improvement of the performance of the kernel k-means algorithm. Also described is the distributed implementation of the proposed algorithm. Furthermore, we show how the computation of the kernel matrix can be performed very fast on modern CPUs using specialized software. Finally, we present a stochastic graph clustering method based on the discreet cosine transform.

Σε αυτή τη διδακτορική διατριβή, θα παρουσιάσουμε τα αποτελέσματα της έρευνας που διεξήχθει στις περιοχές της ομαδοποίησης και της ταξινόμησης δεδομένων με εφαρμογές στην ανθρωποκεντρική ανάλυση εικόνων και εικονοσειρών. Η κύρια συνεισφορά μας στο πεδίο της ταξινόμησης σχετίζεται με την εισαγωγή μιας δομής δεδομένων αναζήτησης σχημάτων βασισμένη στα δυαδικά δένδρα για τη γρήγορη ταυτοποίηση σχημάτων. Σύμφωνα τις ιδιότητες ενός ισορροπημένου δυαδικού δένδρου, μπορούμε να εισάγουμε, να αναζητούμε και να διαγράφουμε σχήματα σε λογαριθμικό χρόνο. Σε κάθε κόμβο του δένδρου ένας ασθενής ταξινομητής αποφασίζει σε ποιο μονοπάτι θα κατευθύνει την αναζήτηση. Στην αρχική του μορφή, το δένδρο κατασκευάζεται αυξητικά. Ξεκινώντας από ένα άδειο δένδρο, η δομή συμπληρώνεται εισάγοντας τα σχήματα στο δένδρο. Οι ταξινομητές σε κάθε κόμβο εκπαιδεύονται με έναν απλό και γρήγορο αλγόριθμο εκπαίδευσης. Η μετεξέλιξη αυτών των δένδρων εκμεταλλεύεται ολόκληρο το σύνολο εκπαίδευσης, σκοπεύοντας στη βελτίωση της ταχύτητας και της επίδοσης της προτεινόμενης δομής. Η κατασκευή του δένδρου και η εκπαίδευση των ταξινομητών των κόμβων πραγματοποιείται με πιο εκλεπτισμένους αλγόριθμους. Ο αλγόριθμος εκπαίδευσης των ταξινομητών μεγιστοποιεί την εκ των υστέρων πιθανότητα ένα σχήμα εισόδου να κατευθυνθεί στο σωστό υποδένδρο με βάση τα σχήματα που βρίσκονται στο κάθε υποδένδρο. Ο αλγόριθμος κατασκευής του δένδρου οργανώνει τα σχήματα με τέτοιον τρόπο, ώστε η εκπαίδευση κάθε ταξινομητή να είναι όσο πιο εύκολη γίνεται, ενώ παράλληλα το δένδρο να παραμένει ισορροπημένο. Στη συνέχεια θα παρουσιάσουμε τις συνεισφορές μας στο πεδίο της ομαδοποίησης δεδομένων με χρήση πινάκων ομοιότητας. Η πρώτη και σημαντικότερη συνεισφορά μας σε αυτόν τον τομέα αφορά την περικοπή του πίνακα πυρήνων του αλγόριθμου των κ-μέσων με χρήση πυρήνα. Ο προτεινόμενος αλγόριθμος περικοπής προσπαθεί να εκτιμήσει τον πληθάριθμο της ομάδας στην οποία ανήκει κάθε δείγμα και περικόπτει την αντίστοιχη γραμμή με βάση αυτήν την εκτίμηση. Αυτό έχει ως αποτέλεσμα τη συρρίκνωση του πίνακα πυρήνων και τη βελτίωση των επιδόσεων του αλγόριθμου των κ-μέσων με χρήση πυρήνα. Περιγράφεται, επίσης, μια κατανεμημένη υλοποίηση του προτεινόμενου αλγόριθμου. Ακόμα, δείχνουμε πως ο υπολογισμός του πίνακα πυρήνων μπορεί να πραγματοποιηθεί πολύ γρήγορα σε σύγχρονους επεξεργαστές και χρησιμοποιώντας κατάλληλο λογισμικό. Τέλος, παρουσιάζουμε μια στοχαστική μέθοδο ομαδοποίησης γραφημάτων βασισμένη στον Διακριτό Μετασχηματισμό Συνημιτόνου.