Ταχείς Αλγόριθμοι Για Την Εξέλιξη Γεωδαιτικών Ενεργών Περιγραμμάτων Με Εφαρμογές Στην Όραση Υπολογιστών

Abstract

Στο επίκεντρο αυτής της διπλωματικής εργασίας είναι η ταχεία επίλυση μερικών διαφορικών εξισώσεων που βρίσκουν εφαρμογή στην Όραση Υπολογιστών, με έμφαση στην εξίσωση εξέλιξης των γεωδαιτικών ενεργών περιγραμμάτων και στην εξίσωση ανισοτροπικής διάχυσης θερμότητας. Μετά από μια σύντομη ανασκόπηση των μοντέλων των γεωδαιτικών ενεργών περιγραμμάτων και χώρων κλίμακας από ανισοτροπική διάχυση θερμότητας, εξετάζουμε βασικές μεθόδους αριθμητικής ανάλυσης για μερικές διαφορικές εξισώσεις, με έμφαση στην ανάλυση ευστάθειας με τη μέθοδο του πίνακα και στα αριθμητικά σχήματα που χρησιμοποιούνται ευρέως για την εξέλιξη επιπεδοσυνόλων. Το προκαταρτικό μέρος της εργασίας συμπληρώνεται με την παρουσίαση της μεθόδου πολλαπλών πλεγμάτων για την αποδοτική επίλυση αραιών γραμμικών συστημάτων. Οι ιδέες αυτές μας οδηγούν σε νέους ταχείς αλγορίθμους για την εξίσωση εξέλιξης των γεωδαιτικών ενεργών περιγραμμάτων. Οι αλγόριθμοι αυτοί προκύπτουν με χρήση implicit αριθμητικών σχημάτων, είναι ευσταθείς δίχως περιορισμούς στο χρονικό βήμα και έχουν πρακτικά O(N) πολυπλοκότητα, χάρη στη χρήση μεθόδων πολλαπλών πλεγμάτων για την επίλυση των γραμμικών συστημάτων που προκύπτουν. Η θεωρητική ανάλυση των προτεινόμενων αλγορίθμων οδηγεί στην ανακάλυψη μιας σημαντικής συσχέτισης του μοντέλου των γεωδαιτικών ενεργών περιγραμμάτων με μεθόδους τομής γράφων που χρησιμοποιούνται τα τελευταία χρόνια στην Όραση Υπολογιστών για κατάτμηση εικόνων.