Voxels: Not Your Daddy’s GIS

Can statistics and GIS build a more accurate geospatial picture?

By Art Kalinski, GISP

I’m a little late with this month’s column, but it was for a good reason: I had the responsibility (and honor) of swearing in my daughter at her Navy Officer Candidate School graduation in Newport, Rhode Island. It was a bizarre feeling seeing her stand on the same drill deck where I stood 37 years ago.

Seeing all those fine young men and women at the ceremony reminded me what a privilege it was to serve. I may not have thought so at the time, but now, years later, I know it was. Since you won’t hear it enough, to all of you who are or were on active duty: Thank you for serving your country.

Of course, there are other ways to serve as well, such as creating technologies that can support our first responders and military personnel. A few months ago, I learned about one that was new to me: voxels. With computers growing in power and speed, and richer, more complex datasets being developed, it will surely become more commonplace.

The term “voxel” grew from the words “volumetric” and “pixel”; it describes resolution in volumetric 3D space, not camera or flat-screen resolution. Think of it as the difference between a checkerboard and the construction toy Legos. Voxels are spatial data structures that not only describe 3D space, but can also display statistically fuzzy data.

3D Models: Simulation vs. Reality

For those of you not familiar with voxels, let’s start with GRID or Spatial Analyst, which is a grid cell-based GIS. (If you need a refresher, see my column in the June 2008 edition of GeoIntelligence Insider.) Spatial Analyst is similar to a checkerboard: a 2D space consisting of square cells with values defined in the cells by the checkers. You can even show 3D-like effects by raising or extruding each cell based on elevation data, and then draping an ortho image over the resultant surface.

People call this 3D, but it really isn’t; no matter which way you look at the model, the draped image is still a 2D photo. The other limitation is that, for the most part, all the elevation starts from a theoretical ground plane. There is no easy way to show holes in the space such as overhanging cliffs, caves, bridge underpasses, etc. (Yes, I know there are ways to get around this limitation, but not elegantly.)

There have been efforts to create 3D models of buildings using ortho imagery by extruding the buildings from their footprints, but since the side views of the buildings are limited, the quality is poor and limited to one side, if any. This is where geo-referenced oblique imagery has benefited 3D model creation. Since the geo-referenced oblique images show each side of a building in very high resolution and contain the data needed to automatically generate the 3D wireframes, the resultant models are very easy to create and are not only photo-realistic, but photo-accurate.

Although the application is still in its infancy, 3D models are also where voxels show the greatest potential. Since each volumetric cell is a 3D object in 3D space, complex 3D objects are easy to define. Just like the Legos example, you can build almost any 3D object with voxels. But Legos are solid little cubes, whose presence and location are not ambiguous; they can be there, or not there, period. They are never “maybe there” or fuzzy in their location.

Voxels have another key benefit: they can be statistically defined. By that I mean that each voxel can display the probability that it exists. If you have data that clearly defines a particular area, that region will have a very solid and unambiguous appearance. But if the data is missing, weak, or sparse, the area will appear porous instead. This is where the human observer’s mind can — and does — fill in the voids. The observer automatically understands that there is incomplete data in those places.

Building Body Models

Voxels have been around for a while in the video gaming industry, for the very reason that caves and overhangs can be displayed. Their most serious use, however, has been in building the images created from MRI (magnetic resonance imaging). There they have been a boon to physicians, who can manipulate the 3D images, viewing them from any direction. Additionally, each voxel can have varying degrees of transparency, aiding the physician in comprehending the objects he or she is reviewing.

This is an ideal environment for voxels, since the MRI scan creates very complete datasets to populate the voxel space. Each MRI scan, like the one shown at left, is a 2D “slice” of the 3D object. Assembling all the slices creates an almost perfect 3D model.

Image courtesy of Lockheed Martin.

Voxels and Imagery

There are many more ways of building 3D models that are not as easy as assembling finite, regular slices of a 3D object, and this is where things get complicated and messy. Kirk Smedley and Mark Pritt of Lockheed Martin are leading a team of researchers exploring ways to apply voxel technology to transform the traditional “TCPED” imagery chain. (For more information on this subject, you can contact Smedley at kirk.smedley@lmco.com.) TCPED (short for tasking, collection, processing, exploitation, and dissemination) is shorthand for the well-established life cycle of imagery, from capture all the way to desktop application.

Lockheed’s work is based on the groundbreaking research of Dr. Joseph Mundy at Brown University, who continues to work very closely with Lockheed. The Lockheed/Brown team is performing some very sophisticated investigations into 3D voxel model creation using multiple imagery and data sources. None are as clean as the regular slices of an MRI, but instead are statistical products that generate probability distributions. Think principal component analysis, factor analysis, and Eigen value decomposition.

Yes, it hurts my brain to even think about those long-forgotten statistical methods, but for the brave few who are comfortable in those environments, the voxel is ideal — it can display very complex and imperfect data sets. Not only complex in size, shape, and location, but complex as temporal values and abstract probability distributions.

This ability to display incomplete or imperfect data accurately in a 3D model is important to Lockheed’s clients. There are many video games or training simulators that provide photo-realistic environments; much of the imagery they use is simulated by cloning or modifying textures or images from real life. However, this technique is unacceptable for use by mission planners or first responders in combat or tactical situations. With lives at stake, they need to know exactly what they will face. The 3D model has to show true reality, and display unknown areas as “unknown” or “no data.” For example, in the 3D models that are created by Pictometry and PLW, if there is no satisfactory imagery available for part of a building, that part is shown as a plain, black surface. One can’t add in a fake window or door that has no counterpart in the real world. It’s much better to show the unknown as such.

Voxels are especially well suited to show fuzziness or incomplete data not just as black, no-data representations, but as probability displays that can show fuzzy data as incomplete or semi-transparent voxels.

The varying transparency of voxels can indicate the relative completeness of data. Image courtesy of Lockheed Martin.

Voxels are also ideally suited to create temporal models (which some prefer to call 4D models). Here again, the ability of voxels to display data as probability distributions is even more important for temporal data, which may be fuzzy in some locations and vary in fuzziness over time. Researchers are now looking at the possibility of populating voxel space with multiple images (ground stills, oblique aerial images, video, LIDAR, interior stills, CAD, GIS) in a kind of 3D statistical summary version of Microsoft PhotoSynth.

We may eventually see a seamless environment, inside and out, with accurately represented data that was statistically assembled. This is not your father’s “points, lines, and polygons” GIS. Are you imagining the potential for the GIS community? I see this as yet another example of the CAD, GIS, imagery, and BIM worlds coming together for the benefit of first responders and the military.