@PhdThesis{grady2004space_phd,
author = {Leo Grady},
title = {Space-Variant Computer Vision: A Graph-Theoretic
Approach},
school = {Boston University},
year = 2004,
address = {Boston, MA},
abstract = {Space-variant sampling of visual input is ubiquitous
in the higher vertebrate brain, because a large
input space may be processed with high peak
precision without requiring an unacceptably large
brain mass. Space-variant sampling has been studied
in computer vision for decades. A major obstacle to
exploiting this architecture in machines, and
understanding its role in biology, is the lack of
algorithms that generalize beyond regular samplings.
Most image processing algorithms implicitly assume a
Cartesian grid underlying the sensor. This thesis
generalizes image processing to a sensor
architecture described by an arbitrary graph. This
data structure separates the sensor topology,
expressed by the graph edge structure, from its
geometry, represented by coordinates of the vertex
set. The combinatorial Laplacian of the sensor graph
is a key operator underlying a series of novel image
processing algorithms. First, a new graph
partitioning algorithm for segmentation is presented
that heuristically minimizes the ratio of the
perimeter of the partition border and the area of
the partitions, under a suitable definition of
graph-theoretic area. This approach produces high
quality image segmentations. Interpolation of
missing data on graphs is developed, using a
combinatorial version of the Dirichlet Problem,
i.e., minimizing the average gradients of the
interpolated values while maintaining fixed boundary
conditions. This leads to the solution of the
Laplace Equation, which represents the steady-state
of the diffusion process for stated boundary
conditions. Results compare favorably to both
isotropic and anisotropic diffusion for filling-in
of missing data. A pyramid graph is defined by
connecting vertical and horizontal levels of the
Laplacian pyramid data structure. The isoperimetric
algorithm, run on the graph pyramid, yields an
improved segmentation at little extra computational
cost. Finally, a small-world graph topology is
employed by randomly introducing a few new edges to
the image graph. This results in a large speed-up in
computation time, with identical final results. The
algorithms developed in this thesis do not require
that the data associated with the graph are embedded
in two-dimensions or even have a metric structure.
Therefore, this approach to generalized image
processing may find wider application in other areas
of discrete data processing.},
datestr = {200402},
}