In this post, I’ll present an unsupervised algorithm that can, in polynomial time, extract three-dimensional features from a two-dimensional image. The results are quite good, especially given the run time. This algorithm could have applications in computer vision, in particular medical imaging, and perhaps other fields, but even as a novelty, it’s a fun algorithm that can be run on an ordinary consumer device.
Several months ago, I presented an algorithm that can quickly identify features in an image with no prior information, which I explained in some detail in the post below this one entitled, “Fast Unsupervised Image Categorization Algorithm”. In short, the feature identification algorithm works by partitioning an image into maximally distinct regions by making use of methods rooted in information theory.
By changing the equation that governs the stopping condition in the feature identification algorithm, we can allow the algorithm to run longer, and identify fine-grain features in an image, similar to an edge detection algorithm. The fine-grain feature identification algorithm also has a polynomial run-time, but it is much slower, and as a result, I generally do not use it, though it was the original version of the algorithm.
However, I realized that the fine-grained algorithm is useful for making detailed distinctions between foreground and background. This is because the feature identification algorithm assigns a probability to each feature that gives the likelihood that the feature in question is part of the background of an image. It turns out that this probability is reliable, and so the background of an image generally has a probability of approximately 0, and the foreground generally has a probability of approximately 1. By turning this probability into a depth parameter, we can map a two-dimensional image into a three-dimensional space, where a background feature has a depth of 1, and a foreground feature has a depth of 0 (i.e., one minus the foreground probability), in turn producing a three-dimensional rendering of the two-dimensional image, where the background features are recessed at a greater depth than the foreground features. If we use the fine-grain feature identification algorithm, the features will be smaller in scale, allowing for tighter depth information.
The examples I’ve posted were generated using very low-resolution photos, of around around 250 pixels x 250 pixels. Higher resolution photos produce very fine features, and correspondingly rich depth information, but of course take much longer to render.
This is of course not the algorithm of choice if you’re looking for a mathematically exact rendering. But, it could be useful whenever a fast approximation of depth is required, and the only tool available is information generated by an ordinary two-dimensional camera. In any case, it is certainly a useful heuristic for depth given two-dimensional information, and at a minimum, it is a fun algorithm to experiment with that produces visually meaningful results.
I’ve attached four scripts that you’ll need to run the algorithm, and the rest of the scripts you’ll need are available in the post just below this one.