Μελέτη ανάκτησης σχημάτων με χρήση διεργασιών διάχυσης

• Κύριος συγγραφέας: Καστανιώτης, Δημήτρης
• Άλλοι συγγραφείς: Φωτόπουλος, Σπύρος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2012
• Θέματα: Ανάκτηση σχημάτων; Διεργασίες διάχυσης; Αποστάσεις διάχυσης; Απεικονίσεις διάχυσης; Φασματικές ιδιότητες γράφων; Markov διεργασίες; Shape retrieval; Diffusion processes; Diffusion distance; Diffusion maps; Graph spectra properties; Markov processes; MPEG-7; KIMIA; 516.15

Η παρούσα εργασία ασχολείται με την ανάκτηση σχήματος. Πιο συγκεκριμένα επικεντρώνεται σε επίπεδα (δισδιάστατα) σχήματα τα οποία είναι μη άκαμπτα και έχουν υποστεί κάμψη ή μεταβάλλονται εξαιτίας της παρουσίας κάποιας άρθρωσης. Τέτοια εύκαμπτα σχήματα συναντάμε καθημερινά στη φύση όπως για παράδειγμα τους μικροοργανισμούς μέχρι και τον ίδιο τον άνθρωπο. Τα κριτήρια ομοιότητας μεταξύ των σχημάτων που χρησιμοποιούνται εδώ είναι Intrinsic. Τέτοια κριτήρια μπορεί κανείς να εξάγει δημιουργώντας ένα τελεστή διάχυσης. Οι τελεστές διάχυσης μπορούν να διατυπωθούν με πολλούς τρόπους. Στην παρούσα εργασία βασιζόμαστε στην πιθανολογική προσέγγιση δημιουργώντας ένα τελεστή (Μητρώο Markov) ενώ ταυτόχρονα λαμβάνουμε ένα τυχαίο περίπατο στα δεδομένα. Ο τελεστής αυτός επιπλέον έχει το πλεονέκτημα ότι μπορεί να προσεγγίσει τον τελεστή Laplace-Beltrami ασχέτως της πυκνότητας δειγματοληψίας των δεδομένων. Ορίζεται λοιπόν ως Απόσταση Διάχυσης η απόσταση δύο σημείων. Η απόσταση αυτή είναι μικρότερη όσο περισσότερα μονοπάτια συνδέουν τα δύο σημεία. Η φασματική ανάλυση του μητρώου αυτού μας επιτρέπει να αναπαραστήσουμε τα δεδομένα μας σε ένα νέο χώρο με σαφή μετρική απόσταση την Ευκλείδεια χρησιμοποιώντας τις ιδιοτιμές και τα ιδιοδιανύσματα που προκύπτουν. Επιπλέον η Ευκλείδεια απόσταση στο νέο χώρο ισούται με την απόσταση Διάχυσης στον αρχικό χώρο. Ο συνδυασμός των φασματικών ιδιοτήτων του μητρώου Διάχυσης με τις Markov διεργασίες οδηγεί σε μία ανάλυση των δεδομένων σε πολλές κλίμακες. Αυτό ισοδυναμεί με το να προχωρήσουμε τον τυχαίο περίπατο μπροστά. Από τις απεικονίσεις αυτές μπορούμε να εξάγουμε ιστογράμματα κατανομής αποστάσεων. Έτσι για κάθε σχήμα και για κάθε κλίμακα λαμβάνουμε ένα ιστόγραμμα κατανομής αποστάσεων. Συνεπώς δύο σχήματα μπορεί να βρίσκονται πολύ κοντά σε μία κλίμακα χρόνου ενώ να βρίσκονται πολύ μακριά σε μία άλλη κλίμακα. Συγκεκριμένα εδώ παραθέτουμε την άποψη η απόσταση των σχημάτων συνδέεται άμεσα με την κλίμακα- χρόνο. Μελετώνται οι ιδιότητες των μικρών, μεσαίων και μεγάλων κλιμάκων κυρίως ως προς τα γεωμετρικά χαρακτηριστικά που μπορούν να περιγράψουν και κατά συνέπεια την ικανότητα να εξάγουν αποδοτικούς περιγραφείς των σχημάτων. Η συνεισφορά της παρούσας Διπλωματικής Εργασίας είναι διπλή: A. Προτείνεται για πρώτη φορά μία νέα μέθοδος κατά την οποία αξιοποιούνται οι ιδιότητες των διαφορετικών κλιμάκων της διεργασίας Διάχυσης που αναφέραμε. Ονομάζουμε τη μέθοδο αυτή Weighted Multiscale Diffusion Distance -WMDD. B. Τα αποτελέσματα που παρουσιάζονται φέρνουν την μέθοδο αυτή στην κορυφή για τις συγκεκριμένες βάσεις σχημάτων (MPEG-7 και KIMIA 99).