Friday, November 12, 2010

Structure From Motion

Part of our interest in acquiring a UAV is to expand our ability for quickly generating high resolution topographic data. Traditionally, this process is time-consuming and (as a result) expensive. I've spent a number of summers collecting elevation data over archaeological deposits (Easter Island, Panakton, Greece, Harappa..) and even after weeks of tedious point collection (and thousands of points measured across the ground), the resulting topographic map is less-than-desirable. The problem is one of data density -- 1000 points can be collected pretty quickly (esp. with a modern total station) but over any sized area the density of the points is pretty low per unit area. Take a 100x100 meter area -- it would take 10000 points to have a point every meter. 1000 points is only a 10% sample of that. Now one can be "smart" and sample more densely in areas with greater changes in topography but then some of the algorithms for building the iso-contours will produce odd "artifacts" -- many assume even coverage of points. Even with 10000 points, you end up with a fairly crude representation of the surface - which might work at the scale of the entire deposit, but is too crude for examining any specific area. To make matters worse, in order to increase resolution by say 2x (i.e., to get 50 centimeter resolution), you have to quadruple the sample size.

New developments in laser scanning and LiDAR provide a great means for changing the data generation to cost relationship. However, the technology is pretty new and not entirely cheap. Ultimately, LiDAR provides a great solution for mapping landscape scale features (e.g., entire states) and produces information about the bare ground (so can provide topographic data under tree canopies -- often where we know the least about the archaeological record [e.g., bayous]). But for a project specific survey LiDAR can be overly expensive or simply impossible (since getting plane to some places with the right set up for laser scanning is not always possible -- e.g., Easter Island). Here, land-based laser scanners are handy but these cost about $100,000 to start and typically require trained operators. Renting them can be as much as $20K a month.

From a cost perspective, generating topographic information using "structure from motion" based techniques is quite appealing. This approach makes use of basic imagery collected from inexpensive cameras. Surfaces are calculated based on shared points in photos, determining the position of the camera from images and calculating where the points that are shared must be in space in order that they were captured by the camera. It is an ingenious technique - using some cool math. Noah Snavely, a PhD student (now an assistant professor at Cornell) at the University of Washington developed some of the basic software for doing this (originally part of a "photo tourism" project in which photos taken by tourists of locations can be combined to build a 3-D model of the scene - without knowing before hand where the cameras were placed and under a variety of lighting and other conditions). This project has morphed into Photosynth, the free Microsoft project that automates this project and is Silverlight based.

From a topographic perspective, the "structure from motion" approach is pretty slick - using just a bunch of photos made on cheap digital cameras, one can produce detailed representations of surfaces. Actually, the product is a 3D point cloud that has excellent relative accuracy. Increasing resolution simply means more photos - and whole swaths of areas can be covered with just a click of the shutter. Getting absolute position requires georectification - a separate process (which I can detail elsewhere). Commercial products, though, can take geotagged photos and create a georeferenced point cloud. We have a license for Microsoft's Geosynth - a professional version of Photosynth that can take HD video and geotags to produce high density georeferenced point clouds.

One of the problems with Geosynth, however, is that it doesn't produce some basic products such as a simple (georeferenced) photomosaic. Instead, there focus is on creating "synths" -- a cool product but entirely unintegrated with other kinds of spatial tools (e.g., GIS). Last week, we saw a demo of another software package that produces mosaics using the same kinds of algorithms as Geosynth -- 2d3's TacitView. 2d3 is a small software company located in Irvine. TacitView (and TopoMap, their 3D product). The software is slick and well-done - a great interface and the products are well-suited for integrating into GIS software. We are going to do a demo of this software soon to see how it compares to Geosynth.

Post a Comment