Η παρούσα εργασία ασχολείται με την ανάκτηση (retrieval) σχήματος από μια βάση δεδομένων στην οποία περιλαμβάνονται ομοειδή αλλά και ανόμοια σχήματα. Τα σχήματα αυτά είναι τρισδιάστατα και παρουσιάζονται σε διάφορες μορφές. Αυτό σημαίνει ότι το ίδιο αντικείμενο μπορεί να παρουσιάζεται στην βάση δεδομένων είτε ελαφρώς παραμορφωμένο, είτε από διαφορετική γωνία είτε να έχουν μετατοπιστεί οι κινούμενοι σύνδεσμοι που μπορεί να έχει. Πρόκληση και στόχος αυτής της διπλωματικής εργασίας είναι ο αλγόριθμος που θα υλοποιήσουμε, να μπορεί να ταυτοποιεί το προς εξέταση αντικείμενο με τα σχήματα που αντιπροσωπεύουν το αυτό αντικείμενο. Ο αλγόριθμος που θα χρησιμοποιήσουμε κάνει χρήση των αποστάσεων διάχυσης (Diffusion distances), οι οποίες αποτελούν αντικείμενο έρευνας με πολλές εφαρμογές για την ανεύρεση σχήματος. / This paper deals with the retrieval of shapes from a database that includes similar and dissimilar shapes. These shapes are three-dimensional and are presented in various forms. This means that the same object can be presented in the database or slightly distorted, either from a different angle or with the driven links shifted. Challenge and aim of this thesis is the algorithm that we will implement , it can identify the subject being studied with shapes that represent the same object. The algorithm makes use of the diffusion distances, which are the subject of investigation of many applications for finding shape.

Η παρούσα εργασία ασχολείται με την ανάκτηση σχήματος. Πιο συγκεκριμένα επικεντρώνεται σε επίπεδα (δισδιάστατα) σχήματα τα οποία είναι μη άκαμπτα και έχουν υποστεί κάμψη ή μεταβάλλονται εξαιτίας της παρουσίας κάποιας άρθρωσης. Τέτοια εύκαμπτα σχήματα συναντάμε καθημερινά στη φύση όπως για παράδειγμα τους μικροοργανισμούς μέχρι και τον ίδιο τον άνθρωπο. Τα κριτήρια ομοιότητας μεταξύ των σχημάτων που χρησιμοποιούνται εδώ είναι Intrinsic. Τέτοια κριτήρια μπορεί κανείς να εξάγει δημιουργώντας ένα τελεστή διάχυσης. Οι τελεστές διάχυσης μπορούν να διατυπωθούν με πολλούς τρόπους. Στην παρούσα εργασία βασιζόμαστε στην πιθανολογική προσέγγιση δημιουργώντας ένα τελεστή (Μητρώο Markov) ενώ ταυτόχρονα λαμβάνουμε ένα τυχαίο περίπατο στα δεδομένα. Ο τελεστής αυτός επιπλέον έχει το πλεονέκτημα ότι μπορεί να προσεγγίσει τον τελεστή Laplace-Beltrami ασχέτως της πυκνότητας δειγματοληψίας των δεδομένων. Ορίζεται λοιπόν ως Απόσταση Διάχυσης η απόσταση δύο σημείων. Η απόσταση αυτή είναι μικρότερη όσο περισσότερα μονοπάτια συνδέουν τα δύο σημεία. Η φασματική ανάλυση του μητρώου αυτού μας επιτρέπει να αναπαραστήσουμε τα δεδομένα μας σε ένα νέο χώρο με σαφή μετρική απόσταση την Ευκλείδεια χρησιμοποιώντας τις ιδιοτιμές και τα ιδιοδιανύσματα που προκύπτουν. Επιπλέον η Ευκλείδεια απόσταση στο νέο χώρο ισούται με την απόσταση Διάχυσης στον αρχικό χώρο. Ο συνδυασμός των φασματικών ιδιοτήτων του μητρώου Διάχυσης με τις Markov διεργασίες οδηγεί σε μία ανάλυση των δεδομένων σε πολλές κλίμακες. Αυτό ισοδυναμεί με το να προχωρήσουμε τον τυχαίο περίπατο μπροστά. Από τις απεικονίσεις αυτές μπορούμε να εξάγουμε ιστογράμματα κατανομής αποστάσεων. Έτσι για κάθε σχήμα και για κάθε κλίμακα λαμβάνουμε ένα ιστόγραμμα κατανομής αποστάσεων. Συνεπώς δύο σχήματα μπορεί να βρίσκονται πολύ κοντά σε μία κλίμακα χρόνου ενώ να βρίσκονται πολύ μακριά σε μία άλλη κλίμακα. Συγκεκριμένα εδώ παραθέτουμε την άποψη η απόσταση των σχημάτων συνδέεται άμεσα με την κλίμακα- χρόνο. Μελετώνται οι ιδιότητες των μικρών, μεσαίων και μεγάλων κλιμάκων κυρίως ως προς τα γεωμετρικά χαρακτηριστικά που μπορούν να περιγράψουν και κατά συνέπεια την ικανότητα να εξάγουν αποδοτικούς περιγραφείς των σχημάτων. Η συνεισφορά της παρούσας Διπλωματικής Εργασίας είναι διπλή: A. Προτείνεται για πρώτη φορά μία νέα μέθοδος κατά την οποία αξιοποιούνται οι ιδιότητες των διαφορετικών κλιμάκων της διεργασίας Διάχυσης που αναφέραμε. Ονομάζουμε τη μέθοδο αυτή Weighted Multiscale Diffusion Distance -WMDD. B. Τα αποτελέσματα που παρουσιάζονται φέρνουν την μέθοδο αυτή στην κορυφή για τις συγκεκριμένες βάσεις σχημάτων (MPEG-7 και KIMIA 99). / This thesis focuses explicitly at shape retrieval applications. More precisely concentrates in planar shapes that are non-rigid, meaning that they might have been articulated or bended. These non-rigid shapes appear in humans’ life like for example bacteria and also the same the human body. The shape pair wise similarity criteria are intrinsic. Such similarity criteria one can take through a Diffusion Operator. Diffusion Operators can be defined in many ways. In this thesis we concern only in the probabilistic interpretation of Diffusion Operators. Thus by constructing a Diffusion Operator we also construct a random Walk on data. This operator converges to the Laplace-Beltrami even if the sampling density of the data is not uniform. Through this framework the Diffusion Distance between two points is defined. This distance gets smaller as much more paths are connecting two points. Spectral decomposition if this diffusion kernel allows us to map, re-represent our data using the eigenvectors and the eigenvalues in a new space with the property of embedding with an explicit metric. These maps are called Diffusion Maps and have the property that diffusion distance in the initial space equals the Euclidean distance in the embedding space. A combination of spectral properties of a Markov matrix with Markov Processes leads to a multiscale analysis. This corresponds to running the random walk forward. From these embeddings we can extract histograms of distributions of distances. Thus for every shape and every scale we have one histogram. Therefore two shapes may be close in one scale but not in another one. The contribution of this Thesis is twofold: A. For first time a new method where the properties of different scales as studied in order to take the advantage of the most discriminative times/ steps of the diffusion process that we described above. We called this method Weighted Multiscale Diffusion Distance- WMDD. B. The results presented here bring our method to the state of the art for the MPEG- and KIMIA 99 databases.