Back to search

University of York

Edge-based Operators for Graph Characterization

Abstract

dc:description.abstract

This 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

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Aziz, Furqan. Edge-based Operators for Graph Characterization. doctoral thesis, University of York, 2014.