New Dimensions of Knowledge

The hub of the lab is a small circle of computers, where graduate students, in typical fashion, guzzle coffee and spend most of their waking hours glued to the monitor. Faculty members come and go, consulting with the students and going about their own work. Artists sit next to engineers. Anthropologists knock elbows with biologists. And everyone works with the computer scientists.

According to information technologist Jeremy Rowe, the centralized lab is one of the strengths of ASU’s Partnership for Research in Stereo Modeling, or PRISM.

“The projects and resources entice students from multiple disciplines to work together. This draws their faculty advisors to the lab where they interact with students and other faculty. The model has worked very well. There’s sort of a magnetic pull into the lab.”

The real pull is the allure of finding answers—answers that were once impossible to obtain. PRISM’s 3D Knowledge (3DK) project is bringing those answers within reach.

The 3DK program allows researchers to acquire, analyze, and share three-dimensional data. The first step is digitizing information about the object—its size and shape. The PRISM lab houses four 3D scanners to do that job.

The scanners record the X, Y, and Z coordinates of thousands of points on a target object. The result is the creation of a “point cloud.” The computer then plays connect-the-dot with the points, creating a surface made up of thousands of tiny triangles.

The triangulated surface is rough, so researchers might apply a smoothing algorithm for rounded objects. After being smoothed, the computerized object looks just like the real thing.

“This is much more understandable to the viewer but doesn’t really provide any usable information,” says Anshuman Razdan, director of PRISM. That’s where the analysis part comes in.

PRISM researchers have developed software to analyze 3D data in a variety of ways. They work closely with faculty and students to develop tools specific to their needs.

For example, they developed methods for analyzing the curvature of an object. This process lets them segment an object into a collection of features. The software color codes each separate feature. Users then select one or more features for further analysis.

How does the computer separate one feature from the next? Razdan says that objects tend to have natural geometric boundaries, perhaps marked by a change in the direction or depth of a curve. For example, the handle of a coffee cup is obviously separate from the rest of the cup’s outer surface.

“We exploit these phenomena in geometry to find naturally occurring regions,” explains Razdan. “However, these regions turn out to be small and too many in number to be useful. To get answers we use the concept of ‘watersheds.’ Smaller regions are merged together based on a threshold to form bigger, more meaningful, features.”

“Think of two lakes side-by-side,” explains anthropology doctoral student Matt Tocheri. “They are delineated by a land bridge in between them. That’s what separates one lake from another.”

The software allows the user to extract a wide range of information about the features, such as area, direction, and depth. There are hundreds of potential uses for this kind of data. For example, anthropologists are comparing the curves on pots to find out how symmetrical they are.

One of PRISM’s strengths is that the underlying algorithms can be tweaked and reapplied to completely different projects.

“We developed all this stuff to extract shape data for pots,” says Gerald Farin, a computer science professor and advisor to PRISM. “Then a guy comes in from Denmark and wants to digitize a model Viking ship. We used the same program.”

Future applications might include 3D face recognition or analysis of surface features on Mars.

Another advantage to digitizing 3D data is that it can be shared and searched. “When we can describe, we can archive intelligently. When you can archive intelligently, the second half of what we are developing, you can search on 3D shapes,” says Razdan.

He compares the process to existing Internet search engines such as Google or Yahoo, only far more complicated. Users could search for size, shape, or curvature, among other variables, setting a tolerance for how accurate a match is needed.

For example, an anthropologist might find a fossil finger joint. The scientists could then search a 3D library from multiple institutions to find the best match from the other hand.

All of the analysis and cataloguing software is developed at ASU.

“This is not software we take off the shelves and use,” notes Farin. “First you have to come up with the right algorithms. There’s a lot of mathematics involved. Only after the research does the programming come in.”

The Mellon Foundation recently produced a report saying that visual querying is a key research focus over the next couple of years.

“We’re at the front end of having tangible, practical data on how this works,” says Rowe.

Razdan believes the technology will really take off in the next five years. “Our ASU students [in the PRISM lab] will go out and integrate these tools into their programs at other institutions when they become forces in their fields.”—Diane Boudreau