The task of 3D reconstruction is usually associated with binocular vision. Alternatively, you may move a single camera around the object. Meanwhile, if the shape of the object is known, the task may be solved from a single photo. That is you have only one camera and it doesn't move. Let's look how to do it step by step. We will use Rubik's Cube because it is well standardized and has a rich set of features. It may be regarded as a very simple object and simultaneously a complicated construct. So machine vision must surpass substantial obstacles so as to complete the task.

Step 1: Evaluate Complexity of the Task

At first glance, the task is simple. Find the central knot where 3 edges of the cube come together and draw these edges. From their coordinates, it is possible to calculate the distance from the camera and angles of rotation. The problem is that these lines don't exist. From the left image you see that each edge is represented by 2 parallel lines. Furthermore, the upper right picture shows that each of them is broken into 3 segments. Moreover, if we apply a variant of the popular Hough transform which can detect line segments, it performs the task with some errors which make detection of the central knot impossible. If the ends don't reach each other, there is no single point. If the detection overshoots the end, it will look like the knot in the middle of the edge as you see on the 2 remaining images.

Step 2: Find the Proper Approach

When too many details make deterministic algorithms unworkable, it's time to consider probabilistic approach. If we calculate averaged parameters of the image, their errors will be substantially diminished and paradoxically the method will turn out more reliable. The standard Hough transform doesn't output line segments. Only its slope theta and the distance rho from the coordinate origin. They form the Hough space part of which is shown above. Here theta corresponds to the horizontal axis. Bright spots mark possible lines on the image. Note that several such spots are located one above another. No wonder, on our image there are many parallel lines. They have the same theta and different rho.

Step 3: Calculate Theta Histogram

Let's detect such clusters. For this purpose we will summarize readings for all dots in the Hough space with the same theta. You see the corresponding histogram on the illustration. A few notes about measurements. When you work with images in pixel coordinates, X axis goes as usual, but Y points downwards so the coordinate origin is the upper left corner and theta should be measured from X axis clockwise. Keeping in mind that the whole sweep of theta on the picture is 180 degrees, you can approximately check that 3 major peaks represent 3 predominant slopes on the image.

Step 4: Calculate Rho Histogram

Now that we know 3 main clusters of parallel lines, let's separate lines within each of them. We can repeat the same approach. Let's take a column from the Hough space that corresponds to one peak on theta histogram. Next, we will calculate another histogram where X axis represents rho value and Y - summarized readings for this rho. Obviously, the sum will be less so this chart is not so smooth. Nevertheless, peaks are clearly visible and the number of them (7) exactly corresponds to the number of parallel lines on the source image. Unfortunately, not all the charts are so perfect, but the principle is clear.

Step 5: Find the Central Knot

If we take the central peak on rho histogram for each theta, we will get 3 lines which are red on the picture. Their intersection marks the necessary point.

Step 6: Choose From 2 Alternatives

You see that each line goes from the central point in both directions. How to determine the correct half? Let's take theta3. Suppose we take the lower part of this line. Let's calculate yet another Hough space only for the part of the picture from 2 green lines to the upper right corner of the image. Then create theta histogram for it. You see that the third peak completely disappeared so we have made the correct choice.

Step 7: Determine the External Corners

Now we can use the first and the last peak on rho histograms so as to draw blue lines which cut the red edges and mark the rest corners. The task is solved.

Step 8: Try It in Practice

The illustrations for this Instructable were created using Perception 1.0. This is free software which uses OpenCV - a powerful library for computer vision. Also it may be linked to WinNB which was used in my another Instructable thus providing vision capability for robotics. You can download both programs from nbsite. For installation, just run the downloaded exe file. Later, you can remove it using the standard tool of Windows. The site also contains resources about computer vision and related topics. In Perception you will find the described method of 3D reconstruction as well as many others. The advantage of this program is that it outputs the final result along with intermediate data. You are able to research how computer vision works without being a programmer. As to input, each method has specially selected typical samples. Of course, you can use your own too. It is possible to input images from a file or from the computer's camera. Feel free to contact me with any questions or suggestions.