This thesis considers a method for computing skeletal representations based on the average outward flux (AOF) of the gradient of the Euclidean distance function to the boundary of a 2D object through the boundary of a region that is shrunk. It then shows how the original method, developed by Dimitrov et al. [17] can be optimized and made more efficient and proposes an algorithm for computing flux invariants which is a number of times faster. It further exploits a relationship between the AOF and the object angle at endpoints, branch points and regular points of the skeleton to obtain more complete boundary reconstruction results than those demonstrated in prior work. Using this optimized implementation, new measures for skeletal simplification are proposed based on two criteria: the uniqueness of an inscribed disk as a tool for defining salience, and the limiting average outward flux value. The simplified skeleton when abstracted as a directed graph is shown to be far less complex than popular skeletal graphs in the literature, such as the shock graph, by a number of graph complexity measures including: number of nodes, number of edges, depth of the graph, number of skeletal points, and the sum of topological signature vector (TSV) values. We conclude the thesis by applying the simplified graph to a view-based object recognition experiment previously arranged for shock graphs. The results suggest that our new simplified graph yields recognition scores very close to those obtained using shock graphs but with a smaller number of nodes, edges, and skeletal points. / Ce mémoire propose une méthode pour calculer des représentations squelettiques en fonction du flux moyen décrit par le gradient de la fonction de distance Euclidienne aux limites d'un objet 2D qui rétrécit. La méthode originale développée par Dimitrov et al. [17] est ensuite optimisée afin de calculer des invariants de flux plus rapidement. Une relation entre l'AOF et l'angle de l'objet aux extrémités (aux points de branches et des points réguliers du squelette) est exploitée afin d'obtenir une reconstruction plus précises des limites de l'objet par rapport aux travaux précédents. En utilisant cette implémentation optimisée, de nouvelles mesures de simplification de squelettes sont proposées selon deux critères: l'unicité d'un disque inscrit comme un outil permettant de définir la saillance, et la limitation de la moyenne du flux à l'extérieur. Il est démontré que le squelette simplifié, abstrait par un graphe orienté, est beaucoup moins complexe que des graphes squelettiques conventionnels mentionnés dans la littérature, tel que le graphe de choc. Les mesures de complexité de graphe comprennent le nombre de nuds, le nombre de bords, la profondeur du graphe, le nombre de points du squelette et la somme des valeurs du vecteur des signes topologiques (TSV). La thèse se finit en appliquant le graphe simplifié au problème de reconnaissance d'objets basée sur la vue, préalablement adapté pour l'utilisation de graphes de choc. Les résultats suggèrent que notre nouveau graphe simplifié atteint des performances similaires à celles des graphes de choc, mais avec moins de nuds, de bords et de points du squelette plus rapide.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.117144 |
| Date | January 2013 |
| Creators | Rezanejad, Morteza |
| Contributors | Kaleem Siddiqi (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0108 seconds