| Περίληψη |
Είναι γνωστό ότι πολλά προβλήματα από τον τομέα της υπολογιστικής όρασης μπορούν να μοντελοποιηθούν με τη βοήθεια διακριτών πεδίων Markov. Η εύρεση του πιθανότερου πεδίου Markov από δεδομένες παρατηρήσεις οδηγεί σε ένα πρόβλημα βελτιστοποίησης, που επομένως αποτελεί ζήτημα εξαιρετικής σημασίας το οποίο συγκεντρώνει έντονο ερευνητικό ενδιαφέρον την τελευταία εικοσαετία. Σε αυτή τη διατριβή προτείνουμε δύο νέους αλγόριθμους βελτιστοποίησης που επεκτείνουν και γενικεύουν ήδη υπάρχουσες μεθοδολογίες. Έτσι, από τη μια, παρουσιάζουμε ένα καινούριο πλαίσιο ανάπτυξης τέτοιων αλγορίθμων το οποίο έχει τις ρίζες του στη θεωρία δυϊσμού του γραμμικού προγραμματισμού. Το πλαίσιο αυτό προσφέρει μια εναλλακτική, αλλά και πιο γενική θεώρηση των τεχνικών βελτιστοποίησης, που βασίζονται στις τομές γράφων, όπως λόγου χάρη ο αλγόριθμος /α-//expansion//,/ που περιλαμβάνεται ως μία απλώς υποπερίπτωση στο γενικότερο πλαίσιο που προτείνουμε. Επιπροσθέτως, οι αλγόριθμοι που προκύπτουν μέσα από το πλαίσιο μας μπορούν αποδεδειγμένα να υπολογίσουν σχεδόν βέλτιστες λύσεις για μια πολύ μεγαλύτερη κατηγορία πεδίων Markov, κάτι το οποίο επίσης αποτελεί σημαντική συνεισφορά. Από την άλλη, προτείνουμε μια νέα μεθοδολογία βελτιστοποίησης που ονομάζεται /Priority//-//BP/, η οποία εμπεριέχει δύο σημαντικές επεκτάσεις σε σχέση με τον κλασσικό αλγόριθμο Διάδοσης Γνώμης /(//Belief// //Propagation//)/: τη/ «δυναμική μείωση καταστάσεων»/ καθώς και το «/χρονοπρογραμματισμό μηνυμάτων βάσει προτεραιοτήτων»/. Για πρώτη φορά, χάρη στις δύο αυτές επεκτάσεις, επιλύεται με γενικό τρόπο ένα από τα σημαντικότερα μειονεκτήματα του αλγορίθμου Διάδοσης Γνώμης: η αδυναμία του δηλαδή να χειριστεί αποτελεσματικά τη βελτιστοποίηση διακριτών πεδίων Markov με πολύ μεγάλο πλήθος πιθανών καταστάσεων ανά κόμβο. Προς επίδειξη της αποτελεσματικότητας του /Priority//-//BP// /αλγορίθμου, αυτός εφαρμόζεται στο δύσκολο πρόβλημα της αυτόματης συμπλήρωσης ημιτελών εικόνων, όπου και προτείνεται μια νέα μεθοδολογία για την επίλυσή του. Σύμφωνα με αυτή, το πρόβλημα μοντελοποιείται ως ένα διακριτό πρόβλημα βελτιστοποίησης με μια καλά ορισμένη ολική συνάρτηση ενέργειας. Κατ’ αυτό τον τρόπο αποφεύγονται λάθη κατά τη συμπλήρωση τα οποία οφείλονται σε άπληστες αποφάσεις, ενώ επιπλέον η μέθοδος μας είναι αρκετά γενική, ώστε να μπορεί να εφαρμοστεί και σε άλλα (παρόμοιας φύσεως) προβλήματα, όπως π.χ. αυτό της σύνθεσης υφής. Αποτελέσματα από ένα ευρύ φάσμα εικόνων αποδεικνύουν την αποτελεσματικότητα της μεθόδου μας. Τέλος, ως μια άλλη εφαρμογή των πεδίων Markov, ασχοληθήκαμε με μια νέα μεθοδολογία για την ψηφιακή ανακατασκευή φυσικών τρισδιάστατων σκηνών, βασιζόμενοι μονάχα σε ένα μικρό σύνολο στερεοσκοπικών λήψεων. Η μέθοδος μας μπορεί και παρέχει σε πραγματικό χρόνο φωτορεαλιστική απεικόνιση των σκηνών αυτών, ενώ σε σχέση με τις υπάρχουσες τεχνικές ένα σημαντικό πλεονέκτημα της είναι ότι μπορεί να χειριστεί σκηνές πολύ μεγάλου φυσικού μεγέθους. Αποτελέσματα από μια εικονική ανακατασκευή του γνωστού φαραγγιού της Σαμαριάς αποδεικνύουν την αποτελεσματικότητά της.
|
Optimization Algorithms for Discrete Markov Random Fields with Applications to Computer Vision
