Μελέτη κατάτμησης 3D σχημάτων με τεχνικές διάχυσης σε γραφήματα
Πολλές σύγχρονες εφαρμογές, σε τομείς όπως Computer Vision και Γραφικά, Μοντελοποίηση Σχήματος και άλλους, βασίζονται στην Ανάλυση Σχήματος, δηλαδή στην επεξεργασία ενός σχήματος βάσει της γεωμετρίας του. Προβλήματα που αντιμετωπίζει η Ανάλυση Σχήματος είναι η Αντιστοίχιση (Μatching), η Ανάκτηση (Re...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2017
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/10394 |
| id |
nemertes-10889-10394 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Τμηματοποίηση Σχήματα Γράφοι 006.693 Segmentation Shapes Graphs 3D |
| spellingShingle |
Τμηματοποίηση Σχήματα Γράφοι 006.693 Segmentation Shapes Graphs 3D Παπαγιαννοπούλου, Μαριάννα Μελέτη κατάτμησης 3D σχημάτων με τεχνικές διάχυσης σε γραφήματα |
| description |
Πολλές σύγχρονες εφαρμογές, σε τομείς όπως Computer Vision και Γραφικά, Μοντελοποίηση Σχήματος και άλλους, βασίζονται στην Ανάλυση Σχήματος, δηλαδή στην επεξεργασία ενός σχήματος βάσει της γεωμετρίας του. Προβλήματα που αντιμετωπίζει η Ανάλυση Σχήματος είναι η Αντιστοίχιση (Μatching), η Ανάκτηση (Retrieval) και η Τμηματοποίηση / Κατάτμηση (Segmentation) μη-άκαμπτων (non-rigid), παραμορφώσιμων (deformable) σχημάτων.
Η συγκεκριμένη εργασία εστιάζει στην μελέτη Κατάτμησης 3D Σχημάτων με Τεχνικές Διάχυσης σε Γράφους. Γίνεται μελέτη των περιγραφέων χαρακτηριστικών (feature descriptors) οι οποίοι παραμένουν αμετάβλητοι σε μη-άκαμπτες παραμορφώσεις καθώς και η χρήση αυτών σε μεθόδους τμηματοποίησης μη-άκαμπτων, παραμορφώσιμων, 3D σχημάτων.
Οι περιγραφείς σχήματος που χρησιμοποιήθηκαν είναι ο Global Point Signature (GPS) και ο Heat Kernel Signature (HKS) [1, 2, 3]. Ονομάζονται εγγενείς (intrinsic) περιγραφείς σχήματος και είναι αναλλοίωτοι ως προς την ισομετρία (isometry invariant). Βασίζονται στο φάσμα του τελεστή Laplace - Beltrami της επιφάνειας και δεν αλλάζουν με διαφορετικές ισομετρικές ενσωματώσεις του σχήματος. Το πλεονέκτημά τους είναι ότι μπορούν να εφαρμοστούν εύκολα σε παραμορφώσιμα αντικείμενα (π.χ., ένα άτομο σε διάφορες στάσεις του σώματος), διότι αυτές οι παραμορφώσεις στην πραγματικότητα είναι σχεδόν ισομετρικές.
Η βασική μέθοδος τμηματοποίησης που μελετήθηκε βασίζεται σε μία μέθοδο συναινετικής ομαδοποίησης (Consensus Clustering) από ένα ετερογενές σύνολο θεωρούμενων τμηματοποιήσεων του σχήματος, οι οποίες προκύπτουν από μια διαδικασία ομαδοποίησης πάνω σε μια εγγενή ενσωμάτωση του σχήματος [4, 5, 6]. Για την βελτίωση της παραπάνω μεθόδου εφαρμόστηκαν διάφορες διαδικασίες ομαδοποίησης [8] καθώς και μία μέθοδος εξαγωγής πρωτοτύπων προσεγγίζοντας την κατασκευή του πίνακα ομοιότητας από μία άλλη πλευρά [7]. |
| author2 |
Φωτόπουλος, Σπυρίδων |
| author_facet |
Φωτόπουλος, Σπυρίδων Παπαγιαννοπούλου, Μαριάννα |
| format |
Thesis |
| author |
Παπαγιαννοπούλου, Μαριάννα |
| author_sort |
Παπαγιαννοπούλου, Μαριάννα |
| title |
Μελέτη κατάτμησης 3D σχημάτων με τεχνικές διάχυσης σε γραφήματα |
| title_short |
Μελέτη κατάτμησης 3D σχημάτων με τεχνικές διάχυσης σε γραφήματα |
| title_full |
Μελέτη κατάτμησης 3D σχημάτων με τεχνικές διάχυσης σε γραφήματα |
| title_fullStr |
Μελέτη κατάτμησης 3D σχημάτων με τεχνικές διάχυσης σε γραφήματα |
| title_full_unstemmed |
Μελέτη κατάτμησης 3D σχημάτων με τεχνικές διάχυσης σε γραφήματα |
| title_sort |
μελέτη κατάτμησης 3d σχημάτων με τεχνικές διάχυσης σε γραφήματα |
| publishDate |
2017 |
| url |
http://hdl.handle.net/10889/10394 |
| work_keys_str_mv |
AT papagiannopouloumarianna meletēkatatmēsēs3dschēmatōnmetechnikesdiachysēssegraphēmata AT papagiannopouloumarianna 3dshapesegmentationmethodsusingdiffusiontechniquesongraphs |
| _version_ |
1799945008947658752 |
| spelling |
nemertes-10889-103942022-09-06T05:13:49Z Μελέτη κατάτμησης 3D σχημάτων με τεχνικές διάχυσης σε γραφήματα 3D shape segmentation methods using diffusion techniques on graphs Παπαγιαννοπούλου, Μαριάννα Φωτόπουλος, Σπυρίδων Papagiannopoulou, Marianna Οικονόμου, Γεώργιος Μπακάλης, Δημήτριος Τμηματοποίηση Σχήματα Γράφοι 006.693 Segmentation Shapes Graphs 3D Πολλές σύγχρονες εφαρμογές, σε τομείς όπως Computer Vision και Γραφικά, Μοντελοποίηση Σχήματος και άλλους, βασίζονται στην Ανάλυση Σχήματος, δηλαδή στην επεξεργασία ενός σχήματος βάσει της γεωμετρίας του. Προβλήματα που αντιμετωπίζει η Ανάλυση Σχήματος είναι η Αντιστοίχιση (Μatching), η Ανάκτηση (Retrieval) και η Τμηματοποίηση / Κατάτμηση (Segmentation) μη-άκαμπτων (non-rigid), παραμορφώσιμων (deformable) σχημάτων. Η συγκεκριμένη εργασία εστιάζει στην μελέτη Κατάτμησης 3D Σχημάτων με Τεχνικές Διάχυσης σε Γράφους. Γίνεται μελέτη των περιγραφέων χαρακτηριστικών (feature descriptors) οι οποίοι παραμένουν αμετάβλητοι σε μη-άκαμπτες παραμορφώσεις καθώς και η χρήση αυτών σε μεθόδους τμηματοποίησης μη-άκαμπτων, παραμορφώσιμων, 3D σχημάτων. Οι περιγραφείς σχήματος που χρησιμοποιήθηκαν είναι ο Global Point Signature (GPS) και ο Heat Kernel Signature (HKS) [1, 2, 3]. Ονομάζονται εγγενείς (intrinsic) περιγραφείς σχήματος και είναι αναλλοίωτοι ως προς την ισομετρία (isometry invariant). Βασίζονται στο φάσμα του τελεστή Laplace - Beltrami της επιφάνειας και δεν αλλάζουν με διαφορετικές ισομετρικές ενσωματώσεις του σχήματος. Το πλεονέκτημά τους είναι ότι μπορούν να εφαρμοστούν εύκολα σε παραμορφώσιμα αντικείμενα (π.χ., ένα άτομο σε διάφορες στάσεις του σώματος), διότι αυτές οι παραμορφώσεις στην πραγματικότητα είναι σχεδόν ισομετρικές. Η βασική μέθοδος τμηματοποίησης που μελετήθηκε βασίζεται σε μία μέθοδο συναινετικής ομαδοποίησης (Consensus Clustering) από ένα ετερογενές σύνολο θεωρούμενων τμηματοποιήσεων του σχήματος, οι οποίες προκύπτουν από μια διαδικασία ομαδοποίησης πάνω σε μια εγγενή ενσωμάτωση του σχήματος [4, 5, 6]. Για την βελτίωση της παραπάνω μεθόδου εφαρμόστηκαν διάφορες διαδικασίες ομαδοποίησης [8] καθώς και μία μέθοδος εξαγωγής πρωτοτύπων προσεγγίζοντας την κατασκευή του πίνακα ομοιότητας από μία άλλη πλευρά [7]. Of great importance in the fields of Computer Vision and Graphics, Shape Modeling, 3D Face and Object recognition etc. are the issues of shape Matching, Retrieval and Segmentation. Shape analysis is the process of geometric shapes and is focused on resolving those issues. This work is focused on the study of non-rigid, deformable 3D shape segmentation methods based on Diffusion techniques. Two main issues arise from the above: the acquisition of an appropriate shape descriptor and a stable clustering algorithm. Firstly, an intrinsic embedding of the shape must be acquired. For that, a class of shape descriptors called Intrinsic Shape Descriptors where studied. These descriptors are invariant with respect to isometry, meaning they do not change with the different isometric embeddings of the shape. For each point in the shape, they define its feature vector representing the point's local and global geometric properties. They are based on the spectrum of the Laplace – Beltrami operator of the surface, from which they inherit their isometric invariant characteristics. The descriptors used in this work are the Global Point Signature (GPS) and Heat Kernel Signature (HKS) [1, 2, 3]. Heat Kernel Signature is based on heat kernel, which is a fundamental solution to the heat equation. The other issue is the clustering algorithm to be used. Clustering techniques require the definition of a similarity measure, which is not easy to determine in the absence of any prior knowledge about the formations of the clusters. There is a large number of clustering algorithms but there is not a single algorithm that can adequately handle all kinds of shapes and structures of the clusters. Each algorithm has its own approach on handling the validity of the clusters, the number of the clusters and the structure imposed on the data. The first method implemented in this work is based on [7] and it is an attempt to create a connectivity matrix from a down-sampled version of the dataset, called, Prototypes. The algorithm through an over-partitioning mode of the classical FCM algorithm builds the connectivity graph of prototypes (centroids), exploiting the membership values produced during the clustering procedure. The method is composed of three main stages. In the first stage, similarly to the previous methods, the intrinsic embedding of the shape is created. In the second stage, an over-partitioning mode of the FCM algorithm takes place. The cluster centers and the fuzzy partition matrix, which includes the membership values, are produced by the clustering algorithm. The partition matrix is used to compute the connectivity matrix, which describes the pairwise relationships of the prototypes. In the final stage, the algorithm follows the same steps as in the previous methods for clustering of prototypes i.e the MST or the Dominant Sets methods. With the use of the fuzzy partition matrix and having clustered the prototypes each node is assigned to the closer prototype, forming the natural clusters of the shape. With the use of the fuzzy partition matrix each vertex is assigned in a cluster, forming the natural clusters of the shape. This method, although it is able to detect some basic shape parts, doesn’t have very satisfying results. The second method is a point-based segmentation technique based on the idea of Consensus Clustering [4, 5, 6]. A segmentation based on Consensus Clustering is obtained from a number of different segmentations of the shape and it is desired to find a single (consensus) segmentation of the shape which is a better fit in some sense than the existing ones. At fisrt, an intrinsic embedding of the shape is acquired using GPS or HSK. An iterative procedure takes place in which the intrinsic embedding of the shape in separated in clusters by K-Means clustering algorithm. From the ensemble of different segmentations a similarity measure is derived in the form of a similarity matrix, using a voting mechanism. This similarity matrix, called Consensus matrix, describes the similarity between pairs of vertices of the graph. Consensus matrix provides rich information about the connectivity of shape parts and is inserted to the final stage of shape clustering. Graph clustering is accomplished in this work by using either MST or Dominant sets clustering. In the MST case the weakest k΄ links are removed separating the MST in a minimum spanning forest. Connected components of the graph represent the natural clusters of the shape. In the case of HKS, this method was able to characterize different regions of the shape but it wasn’t appropriate for segmentation. On the case of GPS, the results were more promising. Basic shape parts were recognized but this method wasn’t robust to noise and missing parts. The second approach is based on the Dominant Sets clustering algorithm which is a pairwise data clustering algorithm, more robust to noise [8]. Dominant Sets clustering algorithm is based on the fact that a cluster should satisfy two fundamental conditions: 1) it should have high internal homogeneity and 2) there should be high inhomogeneity between the entities in the cluster and those outside. In the case of an edge-weighted graph, the two conditions above mean that the weights on the edges within a cluster should be large and those on the edges connecting the cluster nodes to the external ones should be small. This approach was able to detect the most important shape parts in the case of humans, four legged animals, ant, armadillo, teddy bear and octopus [37, 38, 39]. Also, it gave more robust and stable segmentations in case of shapes with additive noise or missing parts. In an effort to optimize the segmentation results of the last method, an alternative to Laplace Beltrami operator was invoked. This is the Visibility Matrix (Visibility Graph) which serves as a descriptor of the 3D shape interior [9]. A Visibility graph is a similarity graph based on the Visibility Rule. Visibility Rule states: Nodes i, j are visible if the line segment ℓ connecting them is totally located inside the plane curve or the mesh for 2D and 3D case, respectively. A Visibility graph =( , , ), where V, E are the vertex and edge sets, respectively, while W is an N×N binary, connectivity matrix named Visibility matrix. At that point, Consensus matrix was replaced by the pointwise product, the square matrix and the sum of the Consensus and the Visibility matrix, separately in order to better describe the shape parts connectivity. The sum of the two matrices managed to eliminate redundant segments for the shapes mentioned by combining clusters, separated by Consensus matrix, that were visible with each other. Even though this combinatorial method gave positive results regarding the over-segmented shapes, it didn’t perform well for every shape in the database. In conclusion, the GPS embedding in combination with the segmentation method based on Consensus Clustering and Dominant Sets Clustering lead to the most promising, stable and robust to noise results. Also, to interesting results lead the combined use of Consensus and Visibility matrices. 2017-06-28T09:53:43Z 2017-06-28T09:53:43Z 2017-03-17 Thesis http://hdl.handle.net/10889/10394 gr 0 application/pdf |
