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.