Project:
Spectral Image Segmentation
INSTRUCTOR:
Prof. Andrew Knyazev
Office: CU (Dravo) 644. Phone: 556-8102.
Office hours: by appointment
WWW: http://math.ucdenver.edu/~aknyazev/
Email: aknyazev@math.ucdenver.edu
The Background:
Graph partitioning has many practical applications such as
image segmentation,
efficient load balancing for parallel processing, and data clustering.
Spectral methods make use of the eigenvectors of graph matrices (e.g., the Laplacian or the adjacency matrix of a graph) to construct a quality partitioning.
Spectral image segmentation uses graph assosiated with images and leads
to large scale problems, ideal for testing different numerical linear
algebra methods.
The Ultimate Goals:
To learn numerical linear and eigenvalue solvers
and to test them on "real life" problems from
image segmentation.
The Project Stages:
- Download the
Graph Analysis Toolbox
including the
DEMOS package by
Leo Grady. Unpack it and run the
image segmentation demos provided. Learn how to use the
segmentation code with your own images. Study the
structure of the functions involved in image segmentation.
Tentative Due Date: September 16.
- Figure out how to limit the number of segmentation
recursion levels and set it to one.
Use my version of
recursivepartition.m
with a recursion bug fixed. Locate the place in the code
where the eigensolver
eigs.m is called. Learn how to dump the matrices,
being used as input for eigs, to a file.
Tentative Due Date: September 26.
- For your favorite large-scale picture, save the
spectral segmentation and Ncuts matrices for different
scaling factors. For each matrix, call eigs to compute the smallest
and the largest eigenvalues. Report timing and memory use for each run.
Analyze the growth of the condition numbers as a function of
the matrix size. Provide the actual segmented images
for every image resolution tests. Perform the tests for two
different stencils, or topology of the lattice:
0: 4-connect (Default)
1: 8-connect
Compile a report with all results and provide an electronic
version of the report together with all the codes and pictures used,
so that the results could be completely reproducible.
Tentative Due Date: December 10.
These are the final reports by two groups of students:
To learn more on Spectral Image Segmentation: