Abstract
dc:description.abstractThis thesis addresses problems in computer vision and pattern recognition using graphs. The particular focus is on graph matching and characterization using edge-based operators. The thesis commences with a brief introduction in Chapter 1, followed by a review of the relevant literature in Chapter 2. The remainder of the thesis is organized as follows. Chapter 3 discusses the structure of the Ihara coefficients and presents efficient methods to compute these coefficients. One of our contributions in this chapter is to propose a O(k|V|^3) worst-case running time algorithm to compute the set of first k Ihara coefficients.Chapter 4 proposes efficient methods for characterizing labelled as well as unlabelled graphs. One of our contributions in this chapter is to propose a graph kernel based on backtrackless walks for labelled graphs, whose worst-case running time is the same as that of the kernel defined using random walks. The next part of the thesis discusses the edge-based Laplacian and its applications. Chapter 5 introduces the concept of a metric graph and the eigensystem of the edge-based Laplacian. Our novel contribution in this chapter is to fully explore the eigenfunctions of the edge-based Laplacian and develop a method for explicitly calculating the edge-interior eigenfunctions. In Chapter 6, we define a wave equation on a graph and give a complete solution. The solution is used to define a signature to classify weighted as well as unweighted graphs. Chapter 7 presents another application of the edge-based Laplacian, where the edge-based heat diffusion process is used to define a signature for points on the surface of a three-dimensional shape. It is called the edge-based heat kernel signature (EHKS) and it can be used for shape segmentation, correspondence matching and shape classification. Finally, in Chapter 8 we provide concluding remarks and discuss directions for future research.
Degree
thesis:*- Name dc:type.qualificationname
- Ph.D
- Level dc:type.qualificationlevel
- doctoral
- Grantor dc:publisher.institution
- University of York
- Year dc:date.issued
- 2014
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Aziz, Furqan
- Advisors dc:contributor.advisor
-
- Hancock, Edwin
- Wilson, Richard
Rights
- Language dc:language.dcterms_iso639_2
- eng
Identifiers
dc:identifier.*- Identifier
- uk.bl.ethos.605486