Γεωδαιτικές Ενεργές Καμπύλες Και Μέθοδος Πεπερασμένων Στοιχείων Για Κατάτμηση Σε Γράφους

Abstract

Τα προβλήματα κατάτμησης δεδομένων πάνω σε γράφους είναι πολύ χρήσιμα σε μία μεγάλη κατηγορία επιστημονικών κλάδων. Υπάρχει μια πληθώρα δεδομένων τα οποία μπορούν να μοντελοποιηθούν με χρήση γράφων, από εικόνες και γεωγραφικά δεδομένα μέχρι και τα κοινωνικά δίκτυα. Πολλές φορές λοιπόν είναι αναγκαίο να μπορέσει να γίνει κατηγοριοποίηση των δεδομένων σε ένα γράφο σε ομάδες, με βάση κάποιο ή κάποια χαρακτηριστικά τους. Ανά καιρούς έχουν αναπτυχθεί διάφορες μέθοδοι που χειρίζονται το θέμα αυτό στη βιβλιογραφία, η καθεμία με τα πλεονεκτήματα και τους περιορισμούς της.Στην παρούσα εργασία προσεγγίζονται το πρόβλημα της κατάτμησης χρησιμοποιώντας ιδέες από τον τομέα της Όρασης Υπολογιστών και συγκεκριμένα από τις Γεωδαιτικές Ενεργές Καμπύλες. Το πρόβλημα της κατάτμησης μετασχηματίζεται στο πρόβλημα της γεωμετρικής εξέλιξης καμπυλών και η δυσκολία έγκειται στην αποτελεσματική μετατροπή του χωρικά συνεχούς αυτού μοντέλου σε μια διακριτοποιημένη εκδοχή η οποία μπορεί να εφαρμοστεί σε γράφους. Έχουν προταθεί διάφορες μέθοδοι για το σκοπό αυτό με ικανοποιητικά αποτελέσματα. Στην παρούσα εργασία εξετάζεται μια εναλλακτική προσέγγιση χρησιμοποιώντας τη μέθοδο των Πεπερασμένων Στοιχείων.Αρχικά γίνεται θεωρητική παρουσίαση της μεθόδου και ακολούθως εξετάζεται η απόδοσή της στην ανίχνευση γνωστών γεωμετρικών σχημάτων και συνδυασμού αυτών. Στη συνέχεια γίνεται σύγκριση με προηγούμενες μεθόδους και αναλύονται τα πλεονεκτήματα και μειονεκτήματα της καθώς και πιθανούς περιορισμούς για τη χρήση της. Έπειτα παρουσιάζονται μερικές ενδεικτικές εφαρμογές στις οποίες μπορεί η μέθοδος αυτή να χρησιμοποιηθεί, ενώ στο τέλος γίνεται εξαγωγή γενικών συμπερασμάτων και καταδεικνύονται μερικοί από τους πιθανούς μελλοντικούς προσανατολισμούς της έρευνας.