Adam Finkelstein - US grants

Three recent advances in technology -- the advent of the Web, the revolution of digital media, and the dramatic performance improvement of PCs -- have opened the door for a host of new 3D computer graphics applications. Access to this technology, as well as broadening interest in graphics among non-technical people, drives a growing demand for new ways to catalogue, view, modify, and protect 3D models. Several challenges to providing these tools lie in the growing size and heterogeneity of both the data available and the groups of people manipulating these data.

This project investigates four application areas pertinent to 3D
surfaces: (1) a content-based query method for 3D surfaces in order to find 3D models in a large database -- this technique will enable people to find 3D models on the Web and will enhance catalogue searching for the digital library of the future; (2) algorithms for surface interpolation in order to visualize either the time-evolution of an isosurface or an animation of the isosurface from low to high threshold values -- this technology will aid understanding of 3D data sets such as those resulting from medical scans or astrophysical simulations; (3) controls for reshaping a 3D model based on hand-drawn gestures and interactions with other models -- these controls permit 3D animators to reshape models in a natural way, and they allow 2D
animators to apply complex textures to hand-drawn figures; and (4) a method for insertion and detection of an invisible digital watermark in a 3D surface -- watermarking technology addresses concerns about copyright protection of proprietary models, and will thereby spur the proliferation of new models on the Web.

A factor that binds these projects together is that they rely on two common underlying technologies. The projects share a common
fundamental technology -- multiresolution analysis -- a tool for
representing and manipulating data at different levels of detail. At a higher level, they share a common problem -- the surface correspondence problem -- which looks at how to map one surface onto another optimally. Solutions to this problem have direct application in the four projects highlighted above.

This research will investigate methods for automatic retrieval and analysis
of 3D models. It will develop computational representations of 3D shape
for which indices can be built, similarity queries can be answered
efficiently, and interesting features can be computed robustly. Next, it will
build user interfaces which permit untrained users to specify shape-based
queries. This will include queries specified with text, 3D models, 2D
sketching, and high-level methods based on constraints and rules. It will
combine elements of computer graphics, computer vision, and computational
geometry.

Applications of shape-based query methods will include Internet search engines,
computer-aided design, molecular biology, medicine, and security. In each
application the researchers will work with domain experts to understand the
critical elements of the 3D databases and the challenging shape queries for
which new methods are required. For example, working with molecular biologists
will help develop query tools for the Protein Data Bank to find macromolecules
matching a given shape. These methods will aid classification of proteins for
which only low-resolution electron density maps are available, and aid searches
for proteins matching a specific binding site.

This project will explore new and potentially powerful technological teaching tools for introducing the concepts of computing and physics to children (and teachers). The goal is to broaden the class of students who are not merely exposed to but rather engaged with technology, by empowering children to express ideas with usable tools for creating stop-action and 3D-animated movies, and by developing methodologies for incorporating such tools into Science, Technology, Engineering, and Mathematics (STEM) education. This effort leverages emerging public fascination for computer animation, as well as recent technological advances that have moved the graphics power of yesterday's million-dollar visualization supercomputers into every desktop PC.

A proof of concept of this approach, based on stop-motion animation, was prototyped by one of the PIs, and initial trials were encouraging. In a high-school physics class for noncollege-bound seniors, students who typically skipped class were now attending, some coming even during free time to complete their movies. Through animations, students were able to critically examine their own understanding of the physics and more effectively convey that understanding to teachers. (The same technique is also being used to teach reading to 7 year olds and biology to 9 year olds, replacing book reports and lab notebooks with animated stories and documentaries.) Informed by that experience, this project will have two arms: one to develop and evaluate teaching methodology based on moviemaking (at Tufts University), the other to create new 3D computer animation tools useable in the classroom (at Princeton University).

Technological teaching tools are often developed in the absence of strong educational research; in this project, the PIs will use accepted metrics (and develop new ones) to quantify the STEM learning improvement in high school physics as a result of using animations, comparing student understanding in conventional "hands-on" physics classes with those that include movie journaling. Results from this work will not only contribute to our understanding of how students learn physics and computing, but will also help bridge the student's experience and intuition with modern scientific theory. Further development of moviemaking tools will allow students to move from the jerky animation of the stop-action world to the smooth animations of modern computer graphics. Unfortunately, existing animation systems are barely usable by professionals, let alone grade-school students. This project will address that research challenge by developing inexpensive and robust 3D scanning hardware, point-and-click animation interfaces, and methods for stylized (e.g. cartoon-like) rendering of 3D animation.

Broader Impacts: Anecdotal evidence from the prototype system (gathered over the last three years in five classrooms) already suggests the potential significant impacts of the work. Science-phobic students and computer-shy teachers enthusiastically argue about the underlying physics to improve their movies. Movie making gives teachers a multi-media portfolio to assess student learning and test student preconceived models. If formal evaluations agree with this experience, the results of this project have the potential to change the way students learn science at all ages, opening up a new channel to students to show their understanding and test their hypotheses. This may lead to innovations in teaching computing, math, biology, chemistry, engineering, and even story telling and literature. (Nonetheless, this study chooses an emphasis on physics education because of established metrics for evaluation in this subject.) Even more broadly, animation represents a new medium of expression - visual rather than written - that is compelling but currently limited to highly skilled professionals. The tools the PI plans to develop in this project will make animation more accessible both to children and, more generally, to everyone outside the animation industry. Making this technology more widely available has the potential to affect the way we all communicate, learn, work, and play, turning us into media developers rather than media consumers.

Finding and labeling semantic patterns in large, spatial data sets is one of the most important problems facing computer scientists today. Massive spatial data sets are being acquired in almost every scientific discipline, such as medicine, geology, biology, astrophysics, and others. Finding meaningful patterns in those data is often the bottleneck to scientific discovery. The proposed research is to develop a transformative machine learning methodology, where the process of discovering semantic patterns in large spatial data sets is interactive and semi-autonomous. With the proposed tools and algorithms, the user is provided with an interactive system that shows the most likely segmentations and labelings given the information provided so far, but allows the user to provide additional information as he/she sees fit. The user might adjust a segmentation, provide a label, or specify an expected pattern. The system will adapt in real time to each of these inputs, thus adjusting its predictions throughout the data.



The broad impact of the proposed plan will be enhanced through an integrated educational and outreach plan. Besides the published results of research results, the field will benefit from free distribution of research and education resources, including web pages, bibliographies, software, and data sets, including augmentations to WordNet. Further broad impacts include focused workshops and courses on shape analysis, machine learning, and visualization at both the university and professional levels. Finally, diversity enhancement programs will promote the opportunities for disadvantaged groups in research.

This project develops a Micro-GPS system that provides centimeter-level accuracy and is reliable both indoors and out, based on specific landmarks in the "random" textures present in the world. The key idea is that all floors, such as the carpet in a building, the grain of a wood floor, the concrete on a sidewalk, and the asphalt on a road, have small imperfections, bumps, or variations in color from location to location. A downward-pointing camera mounted underneath a vehicle can observe specific, unique arrangements of these seemingly random variations, looking them up in an index to find out their precise position in the world. The developed technology can provide capabilities for better in-car navigations, such as accurate parking in a particular spot, pothole avoidance, and lane departure warning. Other applications might include smart wheelchairs that can stay on a sidewalk and avoid rough patches, scooters for the elderly and disabled, assistive technologies for the visually impaired, marker-free smart highways, smart robots in warehouses that can precisely position themselves next to shelves, and even domestic assistants that can handle day-to-day chores inside a home.

This research is based on a key idea that localization is possible based on specific features in the "random" textures present in the world: seemingly-heterogeneous textures that have unique variations everywhere but globally consistent image statistics. The key challenges of this project include developing methods for (1) detecting uncommon locations or "features" in a close-up image of the ground surface; (2) computing a feature descriptor for each detected landmark, in a way that is invariant to changes in orientation and lighting; (3) matching the features against a map: a pre-built database of features, their arrangements, and their locations in the world; and (4) being able to create and update the database to increase coverage and to account for changes. All of these are common components in contemporary systems for tracking, image alignment, and recognition. However, the individual algorithms have been tuned to work best for "natural" images. Instead, the project focuses on developing detectors, descriptors, matching algorithms, and update strategies that are tuned to the statistics of common ground textures. The research team investigates whether accuracy can be improved by combining descriptors based on color with ones based on surface normals or height fields; and the systems issues involved in scaling the system to widespread coverage.

Understanding the complex set of signals that control communication between cells in a multicellular organism is a challenging problem that requires a diverse set of tools to solve. This project will use methods from developmental biology, applied mathematics and computer science to uncover the complex signaling patterns that regulate tissue formation in the developing fruit fly (Drosophila) embryo. The quantitative, computational and visualization tools to be developed in this study will be applicable to a broad range of signaling mechanisms in complex three-dimensional tissues or organisms, thereby providing methods of general applicability in biology. In addition, this project will provide interdisciplinary training for students from chemical and biological engineering, molecular biology, and computer science departments, as well as for postdoctoral fellows with applied mathematics and life sciences backgrounds.

Alterations in the activation of receptor tyrosine kinases (RTKs) have been implicated in multiple developmental abnormalities, motivating quantitative studies of developmental RTK signaling. Signaling systems involved in embryogenesis have been highly conserved in evolution, which implies that studies in model organisms, such as Drosophila, yield broadly applicable insights. The early Drosophila embryo provides unique opportunities for high-throughput quantitative experiments, and this project will focus on signaling by the Epidermal Growth Factor Receptor (EGFR), a key regulator of developing tissues in many species. EGFR signaling in the early embryo is accurately described as a temporal pulse that leads to a stable pattern of gene expression, and this project will examine the molecular mechanisms controlling the quantitative parameters of this pulse and its function, as well as establishing experimentally testable models of EGFR signaling in vivo. This project will also develop methods to combine information from different experimental assays that address different aspects of developmental dynamics in different embryos to generate a stereotypical developmental trajectory.

This award is funded jointly by the Systems and Synthetic Biology Program in the Division of Molecular and Cellular Biosciences and the Biomedical Engineering Program in the Division of Chemical, Bioengineering, Environmental and Transport Systems.