Hi.

OK, here's one for the more mathematically oriented programmers.

Given a pair of stereo photographs of the same scene, how would you process them to extract depth information?

I know it's possible, but the mathematics is beyond me. I don't know if there is any software available to do this, or at least any open-source software. I've looked, but all I can find are a few packages to deal with satellite images, which isn't quite what I want.

I'd like to be able to take stereo pairs of the ground from one of my model planes, and generate reasonably good digital elevation data from the images. This is a technique that's used commercially, but the resulting data is extremely expensive.

I don't want to map the entire country, just specific ares where I fly. Is this something that's possible with a sensible amount of effort, or am I going to have to design that subminiature lidar scanner after all?

pca

The trigonometry ought to be reasonably simple. I guess you're asking how to identify the same point automatically?

Then again, in the scales you're looking at, while the trig may be simple, I bet a very slight difference between real and nominal camera angles will cause a huge output error.

I've got a friend who's working on AI programming at University of British Columbia, and your question is PRECISELY his field. In fact, he just successfully did this exact thing recently.

He's a geek of the highest order, much like you, with an equal number of interesting stories to tell. If you two ever met, the universe would implode because of the geek singularty that would be created.

I'm not sure which is cooler: Your stereoscopic R/C aircraft, or his trips on the NASA vomit comet to test his autonomous robot designed to navigate in zero G by sight alone.

Anyway. I'm sayin'... Talk to him. We call him Fishy. PM me with your desired email address contact and I'll give you his (and give him yours).

Okay, Fishy says:

This is the basic, high speed system still used:
http://www.cs.ubc.ca/~lowe/525/fua.pdf

And this is the repository for all of the most modern, mathematically complex systems, often with source code:
http://vision.middlebury.edu/stereo/

I'll PM you with his email address, he says he's happy to lay it out for you in more detail.

Oh, and by the way:



For proper resolution of the resulting data set, would you need the photos to be farther apart than your typical stereo pair meant for human eyes? i.e., a very big airplane with a camera on each wingtip, or two photos taken sequentially as the aircraft moves?

(For instance, to get a proper 3D effect from this geographical feature, the two photos had to be miles apart, taken a few seconds apart from the window of an airliner.)

I would think that the wider the baseline between the cameras, the better.

The cameras would need to have a known configuration, and some calibration/characterization of the resulting images would be needed.

After that, pick a pixel in the first picture, and some set of pixels around it, then look at the same group of pixels in the other pic, run a comparison to determine the shift. Scan the image in this manner and you get an array of values.

Those values should be related to the distance from the camera. edit: Those values would be relative, not absolute.

How to match up the info across many stereo pairs... maybe some kind of image tagging with gps coordinates and measured altitude above ground could help.

I'm guessing, at geographic-feature altitudes, the baseline needs to be larger than the aircraft by such a significant factor that time, speed, and direction need to be part of the equations. In other words, one camera, two photos, with a precise known time and speed between the two photos.

Of course, it will be possible to get the baselines too far apart, at which point your image detection algorithm starts to return nothing but noise. I think that's your noise floor: The more dissimilar the two camera photos, the more random the resulting 3D data set. Your optimum baseline will be, I'll bet, a function of the camera's resolution, the size of the geographic features being captured, and the camera's distance from those features.

Heh. The little cloud hovering just over the peak in the left-hand picture and to the right of the peak in the right-hand picture is freaking my stereoscopic vision out.

There are two approaches I could use. One is to mount two identical cameras on the aircraft, either across the width or along the length. On my biggest plane, I could get them about 3 meters apart on the wingtips. It's a pretty big model

The other one is, as suggested, to simply use images taken at the desired separation in time, from the one camera. With a 5 Hz update GPS, and typical flying speeds of around 60MPH or less, I can get accurate spacings down to less than a meter, essentially the error on the gps.

The problem with both methods, although arising from slightly different reasons, is with rotation between the images. In the second case, the aircraft has to fly in a dead straight line relative to the ground, or the images fit along either a curve (if it's turning) or a slanted line (in the case of crosswinds). Of course both simultaneously are possible.

In the first case, if the aircraft is yawing about it's center axis, the two images will be rotated relative to each other.

It also needs to maintain constant altitude above sea level. All this really ultimately needs to be automated, which is simple enough. An autopilot can fly a raster scan pattern ensuring the images overlap by any necessary amount, using gps coordinates to trigger the camera at points equally spaced in distance rather than time. Doing it manually, from the ground, is fairly difficult.

The end result would be pictures with exact x,y,z coordinates known, as well as field of view, roll, pitch and yaw data, and lens data allowing the images to be corrected geometrically. One desired outcome is the ability to tile these images together to form a much larger one at very high resolution, as is done with a pan-tilt mount to make spherical or cylindrical panoramas. Although in this case is is a flat projection, since the camera position is moving in a plane rather than just rotating.

The other outcome is to process the data to build a decent-resolution digital elevation map of the ground. This data could be used to improve the autopilot, so it knows how far away the ground based simply on position and absolute altitude.

It could also be used to drape the mosaic image over, giving a nice 3d image of the area that it's flying over. From there it's a short step to have it make Battlefield 2 maps

pca

Possibly because, if it's the bit I think you're referring to, it's not cloud, it's a smudge on the airplane window. Since I had to rotate the camera slightly to keep the mountain centered in the frame as the plane flew past, the smudge isn't falling into a proper alignment for anything.

I really like that particular stereo image because it captures the cragginess of the peaks so clearly that they feel sharp enough to cut your hands on.

A-HA! The real reason for the project is revealed!!!!!!!

Follow up. Fishy's final thesis on the topic:

Using the structure and motion of stereo point clouds for the semantic segmentation of images

Output from a small gyro compass could be used to correct for both of these phenomena. If you can get the rotational position at the time the frame is captured (you need to integrate because the gyro provides rates [dr/dt]) then you can rotate the images by that amount prior to stitching them together. Cameras attached to yaw-axis gyro-stabilized gibals could also correct for small instability, but it would probably affect the flight dynamics.

There is a technology called a "MEMS" gyro (Microelectromechanical Systems) that is basically a gyro in a chip. They are fairly inexpensive. A friend of mine is using them for navigation system design where we used to use ring-laser gyros (many years ago when I worked on these systems as an engineer). Much easier and less expensive -- probably in the range of a crazy rocket-scientist hobbyist...

Using MEMS, it's possible to make a full-blown IMU (internal measurement unit) fairly inexpensively. The IMU has 3 gyros and 3 accelerometers on orthogonal axes. By integrating the outputs, you can know the position of the device over time. For short flights, using cheap components, you could know the position and orientation of the vehicle much, much more precisely than GPS (and in all 6 axes).