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.
Well, we can use the exact same methodology to do semi-automatic depth map generation for 2D to 3D image conversion. A great deal comes from Richard's Rzeszutek Masters Thesis entitled "Image Segmentation through the Scale Space Random Walker". The following pictures kinda explain the main points of the method. In all cases, the obtained voltages are the probabilities we were discussing just above. It's a linear system of equations which can be solved rather easily. 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. Now, how do you solve the "Random Walker" problem? Well, one way of doing so is by using an electrical circuit analogy. Do this for every unseeded pixel and you've got your segmentation. It is then a matter of picking the highest probability for a given unseeded pixel to obtain the region it would reach first and associate the pixel with that region. For now, let's assume this problem can be solved. If one considers an image to be a graph (by connecting a pixel to its neighboring pixels with a weighted edge), the question that is to be asked for each unseeded pixel is as follows: Given a random walker starting at that pixel, what is the probability that he will first reach a seed associated with region S (S goes from 1 to K)? The edges are weighted (say, from 0 to 1) knowing that a random walker is much more likely to go along an edge whose weight is high (connected pixels are similar in color) than an edge whose weight is low. A semi-automatic image segmentation approach relies on having the user indicate the number of regions (say, K) and paint a brush stroke (or less) within each region. The goal of image segmentation is to split an image into a set of homogeneous regions, say, in terms of color. The "Random Walks" methodology used for semi-automatic 2D to 3D conversion is quite similar to the one used in semi-automatic image segmentation (see "Random Walks for Image Segmentation" by Leo Grady).