15-451 Algorithms: recitation notes 10/24/12
* Go over midterm
* An interesting problem you can use max flow to solve
=========================================================================
- Hand back midterm. Some stats: median=78, middle half=68--88
- Discuss midterm - go through the problems.
An interesting problem you can use network flow to solve
========================================================
Here is an application to 3-D image processing. The way you get a 3-D
image is you take a stereo camera that produces two pictures, and then
you match the pictures together to produce a single image, where each
pixel is labeled with its depth in the image. The problem is that
this process can produce a lot of noise because of mistakes in
matching things up. So you need a way to fix those mistakes. One
approach is to use the fact that in general, most objects have smooth
boundaries, which means that most pairs of neighboring pixels should be
at the same depth.
Can formalize the problem like this: Given a pixel image I, where each
pixel is 0 or 1 (indicating close or far --- in actual applications,
usually have many depth levels, but we will just consider 2 levels, so
I is a 0/1 matrix), we want to find the best modification I' of I
using the following criteria: let's say we have to pay $a for each bit
of I that we flip, and we have to pay $b for each pair of neighboring
pixels in I' that are at different depths. For instance, if we decide
to not change I at all (I' = I) then we pay b*(# neighboring pixels in
I that are at different levels). If we decide to just make all depths
equal to 0, we pay a*(# of ones in I).
How can we solve for the best I'? Claim: can set this up as a min-cut
problem, and solve using our max-flow algorithms.
Here's how we do it: set up 0-source and 1-sink. Connect source to
all 0s, and sink to all 1's by edges of capacity a. Connect
neighboring pixels by edge of capacity b. Claim: any solution
corresponds to a cut, with cost = value of cut, and vice-versa. More
specifically, cutting an edge from s corresponds to flipping a 0 to a
1, cutting edge into t corresponds to flipping a 1 to a 0, and cutting
an edge between two neighboring pixels corresponds to paying $b for
having the pixels at different depths. So, given a cut, we can
associate the solution in which everything s can reach is labeled 0
and everything else is labeled 1. So, we just want the min S-T cut.
IF TIME PERMITS
===============
If time permits, you could talk about the game I posted to piazza.