Abstract

The Partnership for Research in Spatial Modeling (PRISM) project at Arizona State University (ASU) developed modeling and analytic tools to respond to the limitations of two-dimensional (2D) data representations perceived by affiliated discipline scientists, and to take advantage of the enhanced capabilities of 3D data that raise the level of abstraction and add semantic value to 3D data. Three-dimensional data is complex, and application of modeling and analytic techniques significantly enhances the capacity for researchers to extract meaning from 3D information. The tool prototypes simplify analysis of surface and volume using curvature and topology to help researchers understand and interact with 3D data. The tools automatically extract information about features and regions of interest to researchers, calculate quantifiable, replicable metric data, and generate metadata about the object being studied. To make this information useful to researchers, the project developed prototype interactive, sketch-based interfaces that permit researchers to remotely search, identify and interact with the detailed, highly accurate 3D models of the objects. The results support comparative analysis of contextual and spatial information, and extend research about asymmetric man-made and natural objects that can significantly extend the interactive capabilities of museums for exhibitions, education, and outreach.

Key Words: modeling, archiving, query, retrieval, three-dimensional (3D) object

Figure 1. 3D model of Hohokam ceramic vessel.

Background

Describing, cataloguing, analyzing and organizing 3-dimensional (3D) objects have been significant and long-standing challenges to the museum community. Sketches and scientific illustrations were augmented by photography in the mid 1840s. Beginning in the 1970s, computers began to provide powerful capabilities to automate and link catalogues, to manage research data, and to combine images and text to create educational materials and programs.

Today digital museum collections and digital libraries include text, graphics, images, and increasingly, video, sound, animation, and sophisticated visual displays. Some now display three-dimensional objects and permit the user to rotate and view an image of the original object in their browser window using QuickTime, plug-ins, or custom applications. Examples range from presentation of objects for research or public access to time-lapse movies of exhibit construction and panoramas of exhibitions.

Multiple photographs and QuickTime have begun to capture representations of 3D objects, providing "rotatable" images of complex objects and environments. These photographic representations of shape can be powerful tools for interaction and education; however, the underlying images are still two-dimensional and provide insufficient information for true 3D analysis.

Though still significantly more complex and expensive than traditional photography, 3D data is becoming less costly to acquire. In addition, the number of sources of 3D data continues to increase. Medical imaging techniques such as CAT scans and MRI yield 3D data, as can Confocal microscopes, stereophotogrammetry, satellite and remote sensors, and laser scanners. Whether extracting information from existing data or creating data for additional analysis, the availability of digital 3D representations is increasing and will continue to increase.

Once in digital form, files can be modeled and analyzed. The Partnership for Research in Spatial Modeling (PRISM) project at Arizona State University (ASU) has worked with discipline scientists in anthropology, forensics, and cellular biology to develop prototype modeling and analytic tools that enhance research by raising the level of abstraction and adding semantic value to 3D data about the natural objects being studied.

As objects become more complex in terms of variety of shape and changes in curvature, it becomes more difficult to quantify and analyze. Developing mathematical techniques to represent shape and curvature allows accurate models of the surface of 3D objects such as ceramic vessels, bones, or lithics to be created. These surface models and sophisticated mathematical tools present the ability to analyze, identify, and compare the objects that they represent. The accuracy of the measurements derived from the 3D models created equal or exceed those possible using traditional 2D tools such as calipers and rulers. In addition, measurements such as height, width, maximum height or width, surface area, or volume can be easily, consistently and accurately calculated, even for asymmetric natural objects.

Figure 2. Examples of spatial analysis of ceramic vessel. 

Use of 3D data also makes possible new measures based on topology and global or local changes in curvature that define the shape of the original object. The project built an interdisciplinary team of discipline and computer scientists and technologists to guide an interactive development processes. Research questions were initially posed by the discipline scientists; then tools and spatial modeling techniques to address them were developed by the computer scientists. With the use of mathematical models and surface and volume information, many new and powerful analytic tools become available to spatially analyze objects. For example, boundaries between surfaces can be objectively identified, small local areas of changes in curvature identified and compared, and accurate, replicable measurements calculated automatically.

Once the domain scientists link meaning to the changes in topology, shape, or curvature, a "feature" is defined. The modeling process provides an objective method to calculate physical measurements, and to consistently identify boundaries and changes that are associated with the feature, defining local areas that are of interest to researchers. Once a feature is identified, it can be described by its size, position, shape or curvature. Examples of features that can be extracted from the model data include the maximum diameter or height of a ceramic vessel.

Figure 3. Components of interest for Ceramic Vessel

Features can also be mathematically abstract components of interest to the researcher, such as the base or neck of a vessel, keel of a ship, boundaries of the joint surfaces on a bone or spindles that form in the nucleus of a cell during meiosis. Often the tools developed to identify features and regions also provide additional capabilities that raise new research questions within the disciplines. Developing the tools needed to address these questions becomes a new design challenge for the computer scientists, fostering a new cycle of development. For example, ceramic analysts have found tools that identify mathematically defined features found on the vertical profile curve of a vessel; such as end points, points of vertical tangency, inflection points and corner points, as features extremely helpful in analyzing vessel shape and style. These same tools have been useful in identifying condyle surfaces of trapezia for anthropologists and forensic scientists. The tools developed to join regions of interest in the trapezia have found application to lithic tool analysis.

In addition to the tangible research benefit the tools and techniques provide, a significant result of this process has been the "cross-pollination" that has occurred as graduate students and faculty from different disciplines gravitate to a given project and explore application of tools and techniques to other discipline research.

A summary of data acquisition and analysis processes begins with laser scanning to acquire the 3D data that represents the object. Mathematical modeling is then applied to identify features and regions of interest to the domain scientists. Software tools developed by the project team generate analytic data about the original object, automatically assign metadata about spatial characteristics, and populate the database.

A visual query interface was developed to permit researchers to interact with the data using both contextual (text and numeric descriptive data) and spatial (shape and topological attribute) data. A sketch-based interface was developed to permit users to input both context and sketches to visually describe the object to initiate the search. Several text and spatial matching algorithms are used to identify and rank order objects within the database that match the search criteria.

Initial development of the digital collections focused on Classic Period (A. D. 1250 – 1450) pre-Columbian Hohokam ceramic vessels from central Arizona housed at the Archeological Research Institute at ASU. These vessels have simple, undecorated surfaces, and their analysis focuses on shape and symmetry. The level of symmetry has been a research focus as it relates to the skill of the potter and may be related to the level of time devoted to craft as a community develops and evolves over time. Since even the best hand-made pots are asymmetric, the traditional measure of symmetry, the profile curve, can vary dramatically depending on the orientation of the vessel. Multiple photographs used to create a QuickTime view of the vessel would assist researchers in visual analysis, but not in more detailed measurement. By scanning and creating a 3D model of the vessel, researchers can perform detailed, objective analysis of the shape and symmetry using tools to compare local and overall curvature, inflection points (changes in curvature from convex to concave), corner points, and calculated measures such as surface area.

Methods

Metadata Schema and Organizational Structure

One of the greatest challenges in an interdisciplinary research effort is coordinating expectations among team members, and developing communication processes that bridge conceptual, strategic, and linguistic differences across the disciplines. An iterative process was developed to share research questions, tools and intellectual approaches across disciplines at project meetings. The results were a gradual bonding of researchers, development of a shared vocabulary, and substantial interaction about potential research issues and approaches. These efforts provided a foundation for the initial modeling and analysis, and for developing the metadata structure needed to organize data for storage, analysis, and query. 

A conceptual goal of the metadata component of the project was to develop an extensible schema structure that could accommodate adding new types of objects as the project continued to evolve. An object class was defined as the master class document type definition (DTD) for each item in the digital library database. For the 3DK digital library project, all of the additional descriptive data about each object was defined and organized as contextual or spatial classes.

Figure 4. Example of metadata structure.

Contextual types define text and metric information about the object. This context class includes subclasses for metadata associated with objects as they are acquired, processed, and archived; such as type, item name, catalogue number, collection, provenance, etc. At this phase of the project, these fields were primarily determined by existing descriptive data elements, though efforts were made to design a schema structure that would accommodate adding new object types as necessary. To date, several iterations to refine the schema model to function effectively across object types have been completed.

Spatial data types define the 3D attributes of the object, including raw data, thumbnails, models, and calculated or derived data about the topology, shape, and composition of the object. Use of common descriptive components and geometric elements as new object types are added will permit shared use of the modeling and analysis tools across classes of objects. The project goal is to develop standards for description and organization that permit automated cataloguing and population of data as objects are scanned and processed for entry into the database.

Due to familiarity and availability of resources, an SQL database was used to store the contextual and spatial data. Fields were assigned to each data element, and large spatial data files were stored as hyperlinks. Generally accepted data formats such as binary, PLY, HTML, and XML have been used to make data accessible and simplify migration and access to the data over time.

Scanning to Acquire 3D Data

The PRISM Digital Library project uses two Cyberware scanners, the M15 and 3030, to scan and capture 3D data describing ceramic vessels, bones, and other objects up to roughly a 30Πmaximum dimension. Each object is scanned by a laser which captures spatial data (x, y, z) values for each point. The scanners capture line-of-site data, so each object must be scanned, then rotated, and scanned again to capture additional data. This process is repeated until sufficient scans are obtained to combine to create a point cloud model to document the surface.

Figure 5. Laser scanning ship model

The Model 15 laser digitizer captures surface data points less than 300 microns (0.3mm) apart, producing high-density triangular meshes with an average resolution of over 1000 points per cm2. The digitized data generated by the scanner is composed of thousands of (x, y, z) coordinates that describe a point cloud that represents the surface of the object scanned. Further analysis requires generating a surface model from the point cloud.

Figure 6. Representation of scanning of ceramic vessel

Figure 7. Point cloud of ceramic vessel combined from multiple scans.

Modeling techniques are used to create an actual measurable surface that represents the original object. In addition to the triangle meshes, PRISM software can represent these surfaces as Non-Uniform Rational B-spline (NURB) or subdivision surfaces (Bernadini et al., 98; Razdan et al., 98; Farin, 01, Farin, 02). NURB representation provides the capability to assess curvature distribution in complex objects; such as identification of the joint surfaces from scanned data of a bone.

The accurate model of the object that results from this process provides the data and conceptual framework needed for objective, replicable analysis of surface and volume attributes of the objects under study. 

Extracting Features and Identifying Regions of Interest

Once the geometric structure has been obtained, the next step is to identify features and regions of interest to the discipline researchers. Ceramicists look for shape, symmetry, and curvature, cellular biologists look for structure of bio-molecular machines inside a cell, forensic anthropologists look at shape, and surface comparisons. A number of 3D modeling and analytic algorithms have been combined, and new techniques developed to segment the geometric structure into regions, and to identify meaningful features 

The nontrivial challenge has been to translate the features of interest to the discipline scientists into mathematically definable terms. For example, the transition between the neck and body of a vessel can be described mathematically as an inflection point and the maximum width of a vessel by its greatest diameter. Crosswalks of definitions to help translate terms and permit mapping mathematical concepts on to features meaningful to the discipline scientists have been developed by the project team. The 3D data permits accurate maximum and minimum measurements to be identified, as well as allowing calculation of complex metric and descriptive data that are extremely difficult to obtain using 2D representations, linear measurements, and traditional measuring tools, particularly for naturally asymmetric or man-made objects such as ceramics.

Figure 8. Region editor applied to trapezium data model.

The second program developed is Region Editor that calculates more complex information about the object and its component features such as total object volume, absolute object symmetry, the area of surfaces identified, and the average angle at which surfaces intersect. Several of these measures are extremely difficult to determine accurately using traditional techniques, such as tape and caliper, particularly for asymmetrical objects. The Region Editor also permits researchers to add contextual information such as technical data about the scan, image processing that has been used, provenance, or collection to the 3D data. The final action of the Region Editor is to create the metadata or XML file associated with the 3D data for archiving.

Figure 9. Diagram of Visual Query Interface and Search Process.

Interacting with the Data: the User Interface

A primary design problem was how to accept input to support searches for both contextual and spatial variables. An interdisciplinary "visual query interface" team guided research into interface design, identified desired capabilities, developed the interface, and coordinates ongoing revision based on evaluation data.

The PRISM team chose to design separate contextual and spatial input areas in the interface screen. Textual data is input or selected from pull-down menus to query existing descriptive catalogues or databases. Search criteria can include metadata such as name, type or number of the item, collection, or other catalogue information about the object. This input area also permits the user to limit search by provenance by limiting the search to a specific collection, or by measurements such as height, width, or maximum or minimum diameter.

Figure 10. Prototype profile-based visual query interface for searching ceramic vessels

The most interesting interface design challenge was to accommodate the input to query spatial data and to identify matching 3D shapes (Sakurai and Gossard, 88; Osada et al 2001, 2002; Razdan et al. 2001). To simplify the initial development of the prototype, and to mirror the 2D shape profiles of the ceramic vessels familiar to anthropologists, the interface model uses an interactive vessel profile graphic representation to define the spatial search component. A gridded area is used to present a sample of a profile curve selected from the menu, or permit the researcher to draw a profile to be searched. Using the mouse and tool palette, the user can interactively create or manipulate the shape until it represents the desired vessel. Initially developed as a Netscape plug-in, the sketch interface has been converted into a Java applet to support multiple browsers and platforms.

After descriptive information about context and shape has been entered, the query is submitted. The descriptive and spatial information are separated, and the multiple database queries are coordinated by project software. The contextual component of the query is handled as a conventional text and numeric database search. The spatial search uses a variety of size, shape, and curve matching algorithms developed by the project team to identify and locate similarities within the databases.

During search and analysis of potential matches, intelligent filtering techniques are used to limit the search pool. Initially simple text, metric, or gross spatial classification criteria are used to identify possible matches from the database and reduce the search domain The search progressively applies increasingly more complex algorithms to the shrinking pool of potential matches. This process minimizes computational load and search time while accurately identifying all objects that match the search criteria.

Figure 11. Ranked search results.

Another algorithm ranks the query results by descriptive and spatial similarity to the query image. Query response information is presented sequentially over several screens, each providing an additional level of information about the selected objects. The first screen displays thumbnail images and brief descriptions of the top search results. Also presented is a large 3D display of the top search result, along with more detailed descriptive and calculated information. The 3D model can be displayed as a point cloud, wire frame, or full shaded surface representation at the discretion of the researcher. Using the mouse, the model can be rotated and viewed from any angle. Selecting a thumbnail of another search result from the queue of search results will replace its model in the 3D display window.

Figure 12. Detailed search results

If more detailed descriptive information is desired, a third window is available to display the 3D model and two additional analytic tools - a profile curve and curvature plot, and additional descriptive data about the object. A fourth window can be selected to provide access to the complete descriptive and calculated data available.

Significant effort has been given to adapting the interface design to accommodate differences in contextual data and analytic tools across different classes of objects. The object type metadata can be used to select the customized search template with fields for the contextual and spatial data appropriate for the object. The visual query interface team developed training materials to guide new users and evaluation instruments to obtain formative guidance from users.

Evaluation

Several techniques were used to evaluate and guide the development of the project. In addition to general meetings and team building activities, process mapping and interviews with project team members provided qualitative and quantitative input to help build communication among researchers in the team.

Initial evaluation input regarding interface components and design were obtained from the roughly 25 project team members. The current version of the interface was used and assessed by the entire group at general and visual query interface team meetings throughout its development. The designs were critiqued, limitations identified, additional desired capabilities described, development challenges identified, and component work delegated to project teams.

Several evaluation sessions were held to obtain input from faculty and student researchers outside of the team. After initial orientation, research problems were posed to the evaluation groups, and users used the interface to locate individual target objects by context, shape or size. Users were encouraged to explore the 150ceramic vessels in the test database and comment on the clarity, scope, and ease of use of the interface. A revision cycle followed each evaluation.

Figure 12. Overview of prototype digital library process.

Discussion

One of the pleasant surprises during this project has been the ease of extending the modeling and analytic tools developed for one specific discipline to other research domains, as well as the growth of the tools for surface and volume modeling and analysis. The improvements that have resulted from the iterative process of identifying a domain research question, developing an application tool, deployment, analysis of potential applications across other research domains, and identification of new research questions have generated significant progress in developing modeling and analytic tools applicable to 3D data.

As 3D data acquisition tools become more affordable and readily available, the amount of 3D data that must be described, stored and displayed will grow dramatically. Accommodating this huge data management challenge will require development of standards and tools to begin to analyze and add meaning to the data.

The spatial and volume modeling and analytic tools developed by the project team permit discipline researchers to quantify and accurately replicate measurements of complex 3D objects. The feature and region recognition capabilities assist in visualizing complex, abstract concepts of interests to discipline researchers.

The ability to generate and analyze accurate representations of 3D objects has many potential uses in the research and museum communities. Scanned and modeled artifacts can permit second-best access to the original objects where access is restricted, such as by country of origin, or by delicacy or condition of the object.

Since the models are scale-independent and can vary in size or magnification, they permit detailed analysis augmenting visual tools such as dissecting scopes or microscopes for small objects, and providing new perspectives for viewing and analyzing large scale objects.

In addition to analysis of individual objects, the tools can be used to compare objects, and one application currently under development is lithic refitting, though the time and effort currently involved limit the practicality of this approach.

These modeling and analytic techniques appear to have many other applications for museums and collection management. The representations are accurate enough to support condition analysis to determine changes over time by comparing sequential scans. For Native American materials, another potential application is documenting repatriated objects to identify artifacts that reappear on the market at some point in the future.

Several efforts are underway or are planned by the PRISM team to further extend the capabilities of the tools developed and their application to domain research. In terms of infrastructure, the move from custom plug-ins to Java will simplify deployment.

We are exploring alternatives to the currently used SQL database, such as object-oriented databases. Another effort to improve searching is a pilot XML search protocol developed by the National Science Foundation Biological Databases and Informatics project at Arizona State University (BDI) research project, in conjunction with the ASU Long Term Ecological Research (LTER) Metadata Committee and the Knowledge Network for Biocomplexity (KNB) Project at the National Center for Environmental Analysis and Synthesis (NCEAS). The "Xanthoria" metadata query system developed by this project team uses SOAP (Simple Object Access Protocol) to send XML query requests and responses, and supports simultaneous Web-based querying of distributed, structurally different metadata repositories.

The spatial analytic tools continue to develop as improvements are made in the feature extraction and region editing applications and more powerful techniques are developed to compare curvature, identify matches and rank search results. Key to these efforts are the expanding partnerships with other research areas with their own unique modeling and visualization needs. Included to date are more complex anatomical data from CAT scanners and MRI, cloud formation pattern recognition, geological erosion, and identification of targets within complex, noisy environmental data.

Interface design continues to evolve. The project is evaluating models developed for 3D query and display by other projects including: