Part based 3D representation for the retrieval of 3D graphical models

Abstract

3D object representations have become an integral part of modern computer graphics applications, such as computer-aided design, game development and film production. At the same time, 3D data have become very common in domains such as computer vision, computational geometry, molecular biology and medicine. The rapid evolution in graphics hardware and software development, in particular the availability of low cost 3D scanners, has greatly facilitated 3D model acquisition, creation and manipulation, giving the opportunity to experience applications using 3D models to a large user community. As the number of 3D models is continuously growing the problem of creating new 3D models has shifted to the problem of searching for existing 3D models. Thereupon, the development of efficient search mechanisms is required for the effective retrieval of 3D objects from large repositories, both of a single class and across classes. In this dissertation, a graph-based representation of a 3D object is introduced using a novel segmentation algorithm and the attributed relational graph concept. The proposed graph-based representation sets the base for an effective 3D object retrieval methodology of articulated objects. The contribution of this dissertation is two-fold. The first contribution is a 3D mesh segmentation algorithm based on the premise that a 3D object consists of its main body part and its constituent protrusible parts. The proposed segmentation algorithm aims to segment the object into these parts. To achieve this goal, first the salient points of the object are detected. These points are prominent features of the 3D object that guide the rest of the segmentation. Afterwards, the salient points are gathered into groups representing the main protrusible parts of the object. In the sequel, the main body (core) of the object is approximated using the minimum cost paths between the salient points of the object. The key idea of the proposed core approximation is to expand a set of vertices in ascending order of protrusion function value until the expanded set touches a certain percentage of all elements of the minimum cost paths. The core approximation either covers portions of the protrusible part areas or is very close to the neighboring areas where the real boundary between the core component and the protrusible part is situated. Afterwards, the partitioning boundary is detected, that is the boundary between a protrusible part and the main body of the mesh. It is considered that in the area enclosed by the desired boundary between the protrusible part and the main body, an abrupt change in the volume of the 3D object should occur, thus, the goal is to detect this change. To accomplish this, closed boundaries are constructed which are defined by a distance function associated to a representative of the group which represents the protrusible part. The abrupt change of volume is detected by examining the closed boundaries perimeter and setting the closed boundary where the largest change of perimeter occurs as the partitioning boundary approximation. The proposed partitioning boundary approximation is very effective since it is shown in the experimental results that it is very close to the real partitioning boundary. Lastly, the partitioning boundary is refined so that it passes through the concavities of the object using a minimum cut algorithm. The second contribution of this dissertation is a 3D object retrieval methodology that relies upon a graph-based representation of an articulated 3D object produced by the proposed segmentation scheme. In particular, the parts extracted by the segmentation algorithm are set as the nodes of the graph structure while its edges connect all the protrusible parts with the part representing the main body of the articulated object. The nodes and the edges of the graph structure relate to unary and binary attributes which represent the geometrical characteristics of the parts as well as the relationships with each other. This graph-based representation can be viewed as an Attributed Relational Graph (ARG). The ARG of the object is later used for effective 3D articulated object retrieval. Specifically, the query’s object ARG is matched with the ARGs of the objects in a database containing 3D articulated objects. The outcome of the retrieval process is a sequence of objects from the database similar to the query object based upon a similarity criterion that relies upon the Earth Mover’s Distance similarity measure. The improved performance of the proposed 3D mesh segmentation scheme as well as the proposed object retrieval methodology for 3D articulated objects has been demonstrated by an extensive evaluation in standard 3D object databases against the major state-of-the-art methodologies.

Η αναπαράσταση 3∆ αντικειµένων έχει γίνει αναπόσπαστο µέρος των σύγχρονων εφαρµογών των Γραφικών σε Υπολογιστή, όπως εφαρµογές CAD, ανάπτυξη 3∆ παιχνιδιών σε υπολογιστή και δηµιουργία ταινιών. Επίσης τα 3∆ δεδοµένα έχουν γίνει πολύ κοινά στο πεδίο της Υπολογιστικής Όρασης, Υπολογιστικής Γεωµετρίας, Μοριακής Βιολογίας και Ιατρικής. Η ραγδαία εξέλιξη στην ανάπτυξη υλικού και λογισµικού στον τοµέα των γραφικών, ιδιαίτερα στη διαθεσιµότητα χαµηλού κόστους 3∆ σαρωτών, έχει βοηθήσει ιδιαίτερα στην ανάκτηση, δηµιουργία και διαχείριση 3∆ µοντέλων δίνοντας την ευκαιρία σε µία µεγάλη κοινωνία χρηστών να βιώσουν εφαρµογές που σχετίζονται µε 3∆ µοντέλα. Όσο ο αριθµός των 3∆ µοντέλων συνεχίζει να αυξάνεται το πρόβληµα της δηµιουργίας 3∆ µοντέλων µετατοπίζεται στο πρόβληµα αναζήτησης ήδη υπαρχόντων 3∆ µοντέλων. Συνεπώς, η ανάπτυξη αποδοτικών µεθόδων αναζήτησης είναι αναγκαία για την αποδοτική ανάκτηση 3∆ αντικειµένων από µεγάλες βάσεις δεδοµένων. Σε αυτήν την ∆ιδακτορική ∆ιατριβή παρουσιάζεται µια αναπαράσταση βασισµένη σε γράφηµα του 3∆ αντικειµένου µε χρήση ενός καινοτόµου αλγορίθµου κατάτµησης και της ιδέας του Γραφήµατος Σχεσιακών Χαρακτηριστικών (Attributed Relational Graph). Η προτεινόµενη αναπαράσταση βασισµένη σε γράφηµα θέτει τη βάση για µία αποτελεσµατική µεθοδολογία ανάκτησης 3∆ αρθρωτών αντικειµένων (3D articulated objects). Η συνεισφορά αυτού του ∆ιδακτορικού είναι δίπτυχη: H πρώτη συνεισφορά είναι η κατασκευή ενός αλγορίθµου κατάτµησης του 3∆ αντικειµένου βασισµένη στην προϋπόθεση ότι το 3∆ αντικείµενο αποτελείται από ένα κυρίως σώµα (main body) και τα επιµέρους προεξέχοντα τµήµατα (protrusible parts). Ο προτεινόµενος αλγόριθµος κατάτµησης στοχεύει στην κατάτµηση του αντικειµένου σε αυτά τα τµήµατα. Για να επιτευχθεί αυτός ο στόχος, πρώτα ανιχνεύονται τα προεξέχοντα σηµεία (salient points) του αντικειµένου. Αυτά τα σηµεία είναι προεξέχοντα χαρακτηριστικά του 3∆ αντικειµένου που οδηγούν τον αλγόριθµο κατάτµησης. Στην συνέχεια, τα προεξέχοντα αυτά σηµεία συγκεντρώνονται σε οµάδες που αναπαριστούν τα κύρια προεξέχοντα τµήµατα του αντικειµένου. Στη συνέχεια, το κυρίως σώµα του αντικειµένου προσεγγίζεται χρησιµοποιώντας µονοπάτια ελαχίστου κόστους (minimum cost paths) µεταξύ των προεξεχόντων σηµείων του αντικειµένου. Η κύρια ιδέα του προτεινόµενου αλγορίθµου προσέγγισης του κυρίως σώµατος είναι η επέκταση ενός συνόλου σηµείων µε αύξουσα διάταξη ως προς τη συνάρτηση προεξοχής (protrusion function) µέχρι η επέκταση να καλύψει ένα συγκεκριµένο ποσοστό των σηµείων των ελαχίστων µονοπατιών. Η προσέγγιση του κυρίως σώµατος είτε καλύπτει µέρος των προεξεχόντων τµηµάτων είτε είναι πολύ κοντά στην περιοχή του συνόρου µεταξύ των προεξεχόντων τµηµάτων και του κυρίως σώµατος. Στη συνέχεια ανιχνεύεται το σύνορο κατάτµησης (partitioning boundary), το οποίο είναι το σύνορο µεταξύ του προεξέχοντος τµήµατος και του κυρίως σώµατος του αντικειµένου. Θεωρείται ότι στην περιοχή που εσωκλείεται από το επιθυµητό σύνορο µεταξύ του προεξέχοντος τµήµατος και του κυρίως σώµατος. Συµβαίνει µία απότοµη µεταβολή στον όγκο του 3∆ αντικειµένου, συνεπώς στόχος είναι η ανίχνευση αυτής της µεταβολής. Για να επιτευχθεί αυτό, κατασκευάζονται κλειστές οριακές καµπύλες (closed boundaries) που ορίζονται από µία συνάρτηση απόστασης (distance function) η οποία σχετίζεται µε τον αντιπρόσωπο της οµάδας που αναπαριστά το προεξέχον τµήµα. Η απότοµη µεταβολή του όγκου ανιχνεύεται εξετάζοντας τις κλειστές οριακές καµπύλες και τίθεται σαν προσέγγιση του συνόρου κατάτµησης η κλειστή οριακή καµπύλη όπου παρατηρείται η µέγιστη µεταβολή περιµέτρου. Η προτεινόµενη προσέγγιση συνόρου κατάτµησης είναι πολύ αποτελεσµατική διότι τα πειραµατικά αποτελέσµατα δείχνουν ότι είναι πολύ κοντά στο πραγµατικό σύνορο κατάτµησης. Τέλος, η προσέγγιση του συνόρου κατάτµησης γίνεται ακριβέστερη έτσι ώστε να περνάει από τις καµπυλότητες του αντικειµένου µε χρήση ενός αλγορίθµου ελάχιστης περικοπής. Η δεύτερη συνεισφορά του ∆ιδακτορικού είναι µία µεθοδολογία ανάκτησης 3∆ αντικειµένων που βασίζεται στην αναπαράσταση βασισµένη σε γράφηµα ενός αρθρωτού 3∆ αντικειµένου το οποίο δηµιουργείται από τον προτεινόµενο αλγόριθµο κατάτµησης. Συγκεκριµένα, τα τµήµατα που εξάγονται από τον αλγόριθµο κατάτµησης τίθενται σαν κορυφές του γραφήµατος και οι ακµές του συνδέουν όλα τα προεξέχοντα τµήµατα µε το κυρίως σώµα του αρθρωτού αντικειµένου. Οι κορυφές και οι ακµές του γραφήµατος σχετίζονται µε µοναδιαία (unary) και δυαδικά (binary) χαρακτηριστικά που αναπαριστούν τα γεωµετρικά χαρακτηριστικά των τµηµάτων όπως επίσης και τη σχέση που έχουν µεταξύ τους. Η αναπαράσταση βασισµένη σε γράφηµα µπορεί να θεωρηθεί σαν ένα Σχεσιακό Γράφηµα Χαρακτηριστικών (Αttributed Relational Graph). Το σχεσιακό γράφηµα χαρακτηριστικών του αντικειµένου χρησιµοποιείται στη συνέχεια για αποτελεσµατική ανάκτηση 3∆ αρθρωτών αντικειµένων. Συγκεκριµένα, το Σχεσιακό Γράφηµα Χαρακτηριστικών του εξεταζόµενου αντικειµένου (query object) ταιριάζεται µε τα Σχεσιακά Γραφήµατα Χαρακτηριστικών των αντικειµένων σε µια βάση που περιέχει 3∆ αρθρωτά αντικείµενα. Το αποτέλεσµα της διαδικασίας ανάκτησης είναι µία ακολουθία από αντικείµενα από τη βάση παρόµοια µε το εξεταζόµενο αντικείµενο. Το χρησιµοποιούµενο κριτήριο οµοιότητας βασίζεται σε µία µετρική οµοιότητας που ονοµάζεται Earth Mover’s Distance. H βελτιωµένη απόδοση του προτεινόµενου 3∆ σχήµατος κατάτµησης καθώς επίσης και η προτεινόµενη µεθοδολογία ανάκτησης 3∆ αρθρωτών αντικειµένων έχει επιδειχθεί µέσω εκτενούς αξιολόγησης σε καθιερωµένη βάση 3∆ αντικειµένων σε αντιπαράθεση µε άλλες σηµαντικές σύγχρονες µεθοδολογίες.