Project:
Spectral Image Segmentation
INSTRUCTOR:
Prof. Andrew Knyazev
Office: CU (Dravo) 644. Phone: 556-8102.
Office hours: by appointment
WWW: http://www-math.cudenver.edu/~aknyazev/
Email: aknyazev@math.cudenver.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: Feb 1.
- 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: Feb 8.
- For your favorite large-scale picture, save the
spectral segmentation and Ncuts matrices for different
scaling factors (and for two different stencils, or topology of the lattice:
0: 4-connect
1: 8-connect
Tentative Due Date: Feb 15.
- Each matrix is singular in such a collection, thus,
a simple factorization is impossible. We know that each matrix
is nonnegative definite (check it by computing all eigenvalues for
smaller size matrices!), so we can make it positive definite
by shifting. To be precise, let us replace each matrix A
in the collection by A + shift I, where shift = 1e-7,
and I is the identity matrix, prior to factorizing it.
For every such shifted matrix, call MATLAB's LU and Cholesky factorizations.
Test LU with a default pivoting and without pivoting.
For each run, check the accuracy of the factors.
Report timing and memory use for each run. Start with small matrices!
Factorizations can be very expensive for large matrices!
Tentative Due Date: March 12.
-
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: April 12.
-
Follow the
instructions by Ilya to install
PETSc and UMFPACK on pogo01 in your account.
Figure out how to use a MATLAB matrix in PETSc.
Tentative Due Date: May 1.
-
Test UMFPACK in PETSc with and without BLAS vs. MATLAB
for large matrices.
Tentative Due Date: May 10.
Sample project reports by students:
To learn more on Spectral Image Segmentation: