Unsupervised 3D mesh segmentation

Abstract

In this thesis we deal with the problem of unsupervised 3D mesh segmentation. Undoubtedly, 3D mesh segmentation is a difficult and important problem. Semantic analysis of 3D content is strongly related to the parts each object consists of. Due to this reason there is a clear trend in literature towards part-based algorithms. However, current mesh segmentation algorithms are often restricted in a limited range of types of objects, use prior knowledge of the object's class, or human interaction. We review previous approaches and discuss the various existing evaluation frameworks. A novel mesh segmentation algorithm is proposed, which is based on a spectral framework. We introduce a new graph Laplacian based on an heterogeneous graph, which comprises two types of nodes, namely faces and patches. Furthermore, we deal with the problem of partitioning the 3D mesh from the eigenvectors of the aforementioned Laplacian. The proposed approach is motivated by the observation that individual eigenvectors highlight different segments. The nodal sets and nodal domains are used to extract segments from each eigenvector separately, while multiple eigenvectors are combined in a hierarchical manner to produce the final segmentation. Experimental results indicate that the proposed methodology achieves improved performance compared to current unsupervised approaches, while it generates results with error equivalent to the ground truth of the very popular Princeton segmentation benchmark. In addition, we use the segmentation produced by the proposed approach, and show how a part-based representation can be used to retrieve similar objects under the premise that objects of the same class will consist of the same parts. This study further supports the experimental results of the segmentation algorithm. The parts produced for each object are used to construct a graph, where nodes represent parts and adjacency between parts is represented by edges in the graph. A novel matching scheme is proposed, which uses a graph cut algorithm to find a correspondence between parts of one object to the other. The matching scheme penalizes parts (nodes) as well as pairs of parts (edges) without a counterpart. We perform experiments in diverse datasets, which show superior performance of the part-based approach in the case of articulated objects, while being competitive with respect to the state-of-the-art in other datasets.

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