Κατάτμηση εικονοσειρών από τροχιές σημείων

Abstract

This thesis deals with motion-based video segmentation using point trajectories. Throughout the thesis we highlight a series of problems that arise during motion segmentation motivated by experiments and introduce methodologies that can resolve them. A vital component of any motion segmentation algorithm is the metric used to measure whether two trajectories follow the same motion. Especially, in cases of rotations and scalings, metrics that are based on the translation of the trajectories between frames have shown poor results. The approach we propose handles eectively such motions by ranking for each trajectory a set of higher or dermotion models extracted from the trajectories. Trajectories are correlated using their ranking vectors and the distribution of the reprojection error for the models, without resorting to the use of tensors. Hence, higher order motions are not penalized and computational complexity is limited. Another feature of our metric is that it does not use any form of spatial smoothing. This way over segmentation of larger objects is avoided. Another important issue that we deal with in this thesis is that of scalability. As the duration of a video sequence in creases, so does the number of trajectories that soon becomes computationally unmanageable. This problem becomes more in tense in cases of dynamic video sequences where the camera moves and in video shaving higher resolution. In this thesis we introduce an algorithmic design where each video sequence is temporally divided in over lapping subsequences and each subsequence is processed separately. More over, we describe a method to aggregate the individual segmentation results in anal segmentation, while accounting for the over segmentation that arises. Furthermore, as we will explain, the proposed architecture can operate in a streaming environment. A problem that arises during motion segmentation is that of object leakage. Often, as we will demonstrate the cause of this problem is that individual parts of an object are visible for dierent time intervals. The architecture of the subsequences and the merging technique we propose allow us to detect and resolve such cases. Under this perspective we will see that motion segmentation can be modeled as a graph coloring problem. Although graph coloring is an NP-complete problem, in our case it can be eectively solved by exploiting the structure of the graphs that arise. The experimental evaluation of the nal segmentation algorithm attests to its robustness and ecacy compared to the state of the art.

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