Now, how do you solve the "Random Walker" problem? Well, one way of doing so is by using an electrical circuit analogy. Given a region S, ground all seeded pixels that are not associated with S and put a voltage of unity to all seeded pixels associated with S, and solve for the unknown voltages using Kirchoff's Current Law and Ohm's Law. It's a linear system of equations which can be solved rather easily. In all cases, the obtained voltages are the probabilities we were discussing just above. The following pictures kinda explain the main points of the method. A great deal comes from Richard's Rzeszutek Masters Thesis entitled "Image Segmentation through the Scale Space Random Walker".
Using Kirchoff's Current Law and Ohm's Law to obtain the equation each graph node (pixel) must satisfy.
Well, we can use the exact same methodology to do semi-automatic depth map generation for 2D to 3D image conversion. Again, the user is asked to work a little, but this time, he/she has to put down some depth values (shades of gray) using brush strokes, creating a sparse depth map. The depth values which vary from 0 to 255 (the grayscale range) are converted into voltages which vary from 0 to 1. Just like with image segmentation, using Kirchoff's Current Law and Ohm's Law, we obtain a system of linear equations, which, when solved, give the unknown voltages at the pixels that were not painted. Multiply the voltage by the grayscale range and you get a grayscale intensity or depth.
Random Walks, as is, is quite sensitive to noise, not unlike like many computer vision methodologies. To alleviate this problem, the Ryerson team uses a scale space approach which they call SSRW (Scale Space Random Walks) as opposed to plain RW (Random Walks). In the scale space approach, the original image is smoothed (convolved by an isometric Gaussian kernel) as many times as desired. By stacking the images on top of each other, the graph is given an extra dimension to make it a 6-connected three-dimensional graph. This apparently improves the quality of the depth maps produced but it comes at a price: the number of equations to solve is multiplied by the number of (smoothing) levels. See "Image Segmentation using Scale-Space Random Walks" by Richard Rzeszutek, Thomas El-Maraghi, and Dimitrios Androutsos for more info on SSRW.
The following pictures were taken from "Semi-Automatic 2D to 3D Image Conversion Using Scale-Space Random Walks and a Graph Cuts Based Depth Prior" by R. Phan, R. Rzeszutek and D. Androutsos to illustrate the SSRW process: