University of Washington
Computer Science & Engineering

Abstracts of Research in the Human Interface to Computing

3D Scanning, Reconstruction, and Rendering
(Curless, Duchamp (Mathematics),Stuetzle (Statistics))
3D scanning is a powerful tool for acquiring the shape and appearance of unique physical objects, and for bringing the creative design process from the sculptor into the computer. Capturing the properties of existing objects has driving applications in reverse engineering, inspection, virtual dissemination of museum artifacts, and anatomical modeling for medicine. In addition, when desiging new objects such as automobiles or synthetic movie characters, clay is frequently a superior "interface" than most computer-aided geometric design systems; 3D scanning provides the means of bringing the resulting shape into the computer. In our research, we are concerned with all phases of 3D scanning. We are developing new methods for acquiring high resolution shape and color data. We are exploring ways of reconstructing useful computer models from this data. And we are devising algorithms that enable real-time interaction with these models by taking advantage of current trends in 3D graphics hardware development.

Multiresolution Methods in Computer Graphics
(Salesin)
We are exploring the application of multiresolution methods, such as "wavelets," to problems in computer graphics. These graphics applications include image editing and compression, automatic level-of-detail control for editing and rendering curves and surfaces, surface reconstruction from contours, and fast methods for solving simulation problems in global illumination and animation. Our results to date are described in the research monograph, Wavelets for Computer Graphics: Theory and Applications, and in the following papers:

Non-Photorealistic Rendering for Computer Graphics
(Salesin)
In many applications, such as automotive, industrial, architectural, and graphic design, and whenever effective communication is the goal, illustrations have certain advantages over photorealism. They convey information better by omitting extraneous detail, by focusing attention on relevant features, by clarifying, simplifying, and disambiguating shapes, and by showing parts that are hidden. Illustrations also provide a more natural vehicle for conveying information at different levels of detail. In many respects, illustrations are also more attractive: they add a sense of vitality difficult to capture with photorealism. We are exploring a variety of algorithms for creating non-photorealistic illustrations automatically, starting from continuous tone images, three-dimensional computer graphics models, or communications from an on-line "chat room" as input. Our results to date include, among other things, support for resolution-dependent pen-and-ink rendering, in which the choice of strokes used to convey both texture and tone is appropriately tied to the resolution of the target medium; the automatic "watercolorization" of source images; a system for representing on-line communications in the form of comics; and an approach for simulating apparent camera motion through a 3D environment using a moving window over a single 2D background image. These are described in the following papers: Model-Based Vision for Industrial Applications
(Shapiro)
Model-based vision is the analysis of digital images, guided by stored models of the expected objects. In industrial applications, a small number of object models will be required for a particular task, making this an attractive approach. Our research involves using CAD models of real industrial parts in real environments. We are working on systems that use knowledge of the task and the environment in which it is to be performed to predict image features that can be used to identify and locate objects in images. We have developed a technique called relational indexing that provides access to a large database of object models and can rapidly select those that have a high likelihood of appearing in a given scene. The models with the highest likelihoods are candidates for a verification procedure that computes pose from both point-to-point and ellipse-to-circle correspondences, projects the model onto the image, and uses a modified Hausdorff distance measure to decide if the selected object actually appears in the image.

Reconstruction and Recognition of 3D Objects from Range/Color Data
(Shapiro, Brinkley (Biological Structure))
Modern scanning systems allow us to sense both 3D coordinates and color data from sample 3D objects. We have developed new, robust techniques for automatically constructing models of 3D objects from the sensed data and for rendering images of these objects from arbitrary viewpoints through intelligent use of both the 3D and color data at a small set of sample views. We are currently involved in a collaborative project with a group in Biological Structure to develop symbolic spatial models of their 3D objects, which are organs of the human body. These symbolic models will describe a class of 3D object, such as the lungs, rather than an individual instance. Once the object has been symbolically modeled, the symbolic representation can be used both for reasoning and answering queries about the structure of the object and for matching to real data instances of the object, such as a set of lungs obtained from an MRI scan of a real patient. We are working on making these symbolic models general enough that they are useful in many different applications, including the domain of augmented reality environments.

Efficient Content-Based Image Retrieval
(Shapiro)
The goal of this research project is to design and implement a system for content-based image retrieval that can 1) provide a large variety of image-distance measures that can be used singly or in combination to satisfy a wide range of user needs and 2) provide rapid access to images, even in an extremely large database. The focus of the work is the development of a general, scalable architecture to support fast querying of very large image databases with user-specified distance measures. The work includes the development of distance-measure-independent algorithms and data structures for efficient image retrieval from large databases. Methods for merging the general, distance-measure-independent algorithms with other useful techniques that may be distance measure specific, such as keyword retrieval and relational indexing, are being pursued. The problem of providing users with multiple distance measures of many different varieties is being studied. New methods for combining distance measures and a language in which users can specify their queries without detailed knowledge of the underlying metrics are being designed.

Learning Patterns for Computer-Aided Diagnosis
(Shapiro)
This collaborative work with Neopath, Inc. is concerned with tools for the automation of pattern learning in the field of medical diagnosis. We have developed a pattern representation and related recognition algorithm called probabilistic relational indexing that uses small sets of features and their relationships to recognize complex patterns. We are investigating the use of this representation for describing the patterns that are associated with diagnostic classes. An integral part of this work is to use techniques of machine learning to develop suitable pattern structures and to produce optimal classifiers for medical diagnosis tasks.

The Transcript Project
(Tanimoto)
Computer technology has the potential to improve the educational process by aiding in the management of education at a personal level. The Transcript project encompasses a number of experiments to provide computer support for alternative assessment (e.g., assessing an individual student's learning in a group project), course selection, advising, digital portfolios, and the evaluation of educational materials and curricula. The prospect of using the Internet in educational assessment and advising raises a variety of interesting issues that the project is addressing.

A Networked Cooperative Multimedia Learning Environment
(Tanimoto)
In order to make multimedia materials more effective for education, authors should design into them active computational experiences for students, and the materials should support cooperative use by two or more students at a time (where the students may be co-located or working at a distance through the information superhighway). This project is working to create tools that enable such richness in multimedia learning ware.

Mathematics Experiences Through Image Processing
(Tanimoto , King (Mathematics))
The exciting possibilities for transformations of scanned images on personal computers has the potential to attract middle school and high school students to mathematics. The METIP project is producing software and print materials for mathematics education that work with Intel-family PCs running Microsoft Windows. In recent years the project focused on the design and implementation of an image enhancement and learning tool, called the "Pixel Calculator", as well as explorations with geometric warping of images. More recently, an integrated interactive learning environment was prototyped for working simultaneously with images and mathematical ideas. Currently, the project's materials are being refined and distributed to teachers via the World-Wide Web.

Visual Languages for Web-Based Communication
(Tanimoto, Bernardelli (Univ of Rome))
Interpersonal, international communication is taking new forms as web pages, email, chat, and electronic conferencing evolve. Vedo-Vedi is an experimental visual language that is intended to help reduce one remaining obstacle to international communication (the need to write a common natural language), at least in a particular domain (writing about travel) and population segment (children). Key issues addressed by this research include language ontology and visual representation.