Computed Tomography is used to create models of lung dynamics because it provides high contrast images of lung tissue. Creating 4D CT models which capture dynamics is complicated because clinical CT scanners capture data in slabs that comprise only a small part of the tissue. Commonly, creating 4D reconstruction requires stitching together different lung segments based on an external measure of lung volume. This paper presents a novel method for assembling 4D CT datasets using only the CT data. We use a manifold learning algorithm to parameterize each slab data with respect to the breathing cycle, and an alignment method to coordinate these parameterizations for different sections of the lung. Comparing this data driven parameterization with physiological measurements captured by a belt around the abdomen, we are able to generate slightly smoother reconstructions.

Modeling the dynamics of heart and lung tissue is challenging because the tissue deforms between data acquisitions. To reconstruct complete volumes, sample data captured at different times and locations must be combined. This paper presents a novel end-to-end, data driven framework for the complete reconstruction of deforming tissue volumes. This framework is a joint optimization over an undeformed tissue volume, a deformation map that describes tissue motion for given pose parameters (\ie breathing and heartbeat), and an estimate of those parameters for each data acquisition. Tissue motion is modeled by deforming a reference volume with a cubic B-spline free form deformation, and we use Isomap to derive initial estimates of the pose of sample data. An iterative method is used to simultaneously solve for the reference volume and deformation map while updating the pose estimates. This same process is demonstrated on 4D CT lung data and heart/lung MR data.

In this paper, we describe a novel, shape-modeling approach to recovering 3D protein structures from volumetric images. The input to our method is a sequence of a-helices that make up a protein, and a low-resolution volumetric image of the protein where possible locations of a-helices have been detected. Our task is to identify the correspondence between the two sets of helices, which will shed light on how the protein folds in space. The central theme of our approach is to cast the correspondence problem as that of shape matching between the 3D volume and the 1D sequence. We model both the shapes as attributed relational graphs, and formulate a constrained inexact graph matching problem. To compute the matching, we developed an optimal algorithm based on the A*-search with several choices of heuristic functions. As demonstrated in a suite of real protein data, the shape-modeling approach is capable of correctly identifying helix correspondences in noise-abundant volumes with minimal or no user intervention.

In this paper, we propose a new approach to wireless sensor network assisted navigation while avoiding moving dangers. Our approach relies on an embedded roadmap in the sensor network that always contains safe paths. The roadmap is adaptive, i.e., it adapts its topology to changing dangers. Mobile robots in the environment use the roadmap to reach their destinations. We evaluated the performance of embedded roadmap both in simulations using realistic conditions and with real hardware. Our results show that the proposed navigation algorithm is better suited for sensor networks than traditional navigation eld based algorithms. Our observations suggest that there are two drawbacks of traditional navigation eld based algorithms, (i) increased power consumption, (ii) mes- sage congestion that can prevent important danger avoidance messages to be received by the robots. In contrast, our approach signicantly reduces the number of messages on the network (up to 160 times in some scenarios) while increasing the navigation performance.

Multi-robot systems require efficient and accurate planning in order to perform mission-critical tasks. However, algorithms that find the optimal solution are usually computationally expensive and may require a large number of messages between the robots as the robots need to be aware of the global spatiotemporal information. In this project, we introduce an emergent task allocation approach for mobile robots. Each robot uses only the information obtained from its immediate neighbors in its decision. Our technique is general enough to be applicable to any task allocation scheme as long as a utilization criteria is given. We demonstrate that our approach performs similar to the integer linear programming technique which finds the global optimal solution at the fraction of its cost. The tasks we are interested in are detecting and controlling multiple regions of interest in an unknown environment in the presence of obstacles and intrinsic constraints.

An increasing number of structural studies of large macromolecular complexes, both in X-ray crystallography and electron cryomicroscopy, have resulted in intermediate resolution (5-10 A) structures. Despite being limited in resolution, significant structural and functional information may be extractable from these maps. To aid in the analysis and annotation of these complexes, we have developed SSEhunter, a tool for the quantitative detection of alpha-helices and beta-sheets. Based on density skeletonization, local geometry calculations and a template-based search, SSEhunter has been tested and validated on a variety of simulated and authentic subnanometer resolution density maps. The result is a robust, user-friendly approach that allows users to quickly visualize, assess and annotate intermediate resolution density maps. Beyond secondary structure element identification, the skeletonization algorithm in SSEhunter provides secondary structure topology, potentially useful in leading to structural models of individual molecular components directly from the density.

Associating specific gene activity with functional locations in the brain results in a greater understanding of the role of the gene. To perform such an association for the over 20,000 genes in the mammalian genome, reliable automated methods that characterize the distribution of gene expression in relation to a standard anatomical model are required. In this paper, we propose a new automatic method that results in the segmentation of gene expression images into distinct anatomical regions in which the expression can be quantified and compared with other images. Our contribution is a novel hybrid atlas that utilizes a statistical shape model based on a subdivision mesh, texture differentiation at region boundaries, and features of anatomical landmarks to delineate boundaries of anatomical regions in gene expression images. This atlas, which provides a common coordinate system for internal brain data, is being used to create a searchable database of gene expression patterns in the adult mouse brain. Our framework annotates the images about four times faster and has achieved a median spatial overlap of up to 0.92 compared with expert segmentation in 64 images tested. This tool is intended to help scientists interpret large-scale gene expression patterns more efficiently.

This paper presents an algorithm for adapting periodic behavior to gradual shifts in task parameters. We circumvent the curse of dimensionality by parametrizing the policy only along the limit cycle traversed by the gait, and thus focus the computational effort on a closed one-dimensional manifold, embedded in the high-dimensional state space. We demonstrate our approach on two simulations of bipedal robots walking on rough terrain - the compass gait walker, which is a four-dimensional system, and RABBIT, which is ten-dimensional.

Detecting, isolating, and tracking moving objects in an outdoor scene is a fundamental problem of visual surveillance. A key component of most approaches to this problem is the construction of a background model of intensity values. We propose extending background modeling to include learning a model of the expected shape of foreground objects. This paper describes our approach to shape description, shape space density estimation, and unsupervised model training. A key contribution is a description of properties of the joint distribution of object shape and image location. We show object segmentation and anomalous shape detection results on video captured from road intersections. Our results demonstrate the usefulness of building scene-specific and spatially-localized shape background models.

This paper details an empirical study of large image sets taken by static cameras. These images have consistent correlations over the entire image and over time scales of days to months. Simple second-order statistics of such image sets show vastly more structure than exists in generic natural images or video from moving cameras. Using a slight variant to PCA, we can decompose all cameras into comparable components and annotate images with respect to surface orientation, weather, and seasonal change. Experiments are based on a data set from 538 cameras across the United States which have collected more than 17 million images over the the last 6 months.

A key problem in widely distributed camera networks is geolocating the cameras. This paper considers three scenarios for camera localization: localizing a camera in an unknown environment, adding a new camera in a region with many other cameras, and localizing a camera by finding correlations with satellite imagery. We find that simple summary statistics (the time course of principal component coefficients) are sufficient to geolocate cameras without determining correspondences between cameras or explicitly reasoning about weather in the scene. We present results from a database of images from 538 cameras collected over the course of a year. We find that for cameras that remain stationary and for which we have accurate image timestamps, we can localize most cameras to within 50 miles of the known location. In addition, we demonstrate the use of a distributed camera network in the construction a map of weather conditions.

We present a method for modifying the topology of a 3D model with user control. The heart of our method is a guided topology editing algorithm. Given a source model and a user-provided target shape, the algorithm modifies the source so that the resulting model is topologically consistent with the target. Our algorithm permits removing or adding various topological features (e.g., handles, cavities and islands) in a common framework and ensures that each topological change is made by minimal modification to the source model. To create the target shape, we have also designed a convenient 2D sketching interface for drawing 3D line skeletons. As demonstrated in a suite of examples, the use of sketching allows more accurate removal of topological artifacts than previous methods, and enables creative designs with specific topological goals.

Skeletons are important shape descriptors in object representation and recognition. Typically, skeletons of volumetric models are computed using iterative thinning. However, traditional thinning methods often generate skeletons with complex structures that are unsuitable for shape description, and appropriate pruning methods are lacking. In this paper, we present a new method for computing skeletons of volumetric models by alternating thinning and a novel skeleton pruning routine. Our method creates a family of skeletons parameterized by two user-specified numbers that determine respectively the size of curve and surface features on the skeleton. As demonstrated on both real-world models and protein images in bio-medical research, our method generates skeletons with simple and meaningful structures that are particularly suitable for describing cylindrical and plate-like shapes.

Barycentric coordinates are a fundamental concept in computer graphics and geometric modeling. We extend the geometric construction of Floater's mean value coordinates to a general form that is capable of constructing a family of coordinates in a convex 2D polygon, 3D triangular polyhedron, or a higher-dimensional simplicial polytope. This family unifies previously known coordinates, including Wachspress coordinates, mean value coordinates and discrete harmonic coordinates, in a simple geometric framework. Using the construction, we are able to create a new set of coordinates in 3D and higher dimensions and study its relation with known coordinates. We show that our general construction is complete, that is, the resulting family includes all possible coordinates in any convex simplicial polytope.

Using the Storytelling Alice programming environment to create computer-animated movies inspires middle school girls' interest in learning to program computers.

We describe Storytelling Alice, a programming environment that introduces middle school girls to computer programming as a means to the end of creating 3D animated stories. Storytelling Alice supports story creation by providing 1) a set of high-level animations, that support the use of social characters who can interact with one another, 2) a collection of 3D characters and scenery designed to spark story ideas, and 3) a tutorial that introduces users to writing Alice programs using story-based examples. In a study comparing girls' experiences learning to program using Storytelling Alice and a version of Alice without storytelling support (Generic Alice), we found that users of Storytelling Alice and Generic Alice were equally successful at learning basic programming constructs. Participants found Storytelling Alice and Generic Alice equally easy to use and entertaining. Users of Storytelling Alice were more motivated to program; they spent 42% more time programming, were more than 3 times as likely to sneak extra time to work on their programs, and expressed stronger interest in future use of Alice than users of Generic Alice.

Dual Contouring is a feature-preserving iso-surfacing method that extracts crack-free surfaces from both uniform and adaptive octree grids. We present an extension of Dual Contouring that further guarantees that the mesh generated is a manifold even under adaptive simplification. Our main contribution is an octree-based, topology-preserving vertex clustering algorithm for adaptive contouring. The contoured surface generated by our method contains only manifold vertices and edges, preserves sharp features, and possesses much better adaptivity than those generated by other iso-surfacing methods under topologically safe simplification.

This paper specializes general manifold learning by considering a small set of image distance measures that correspond to key transformation groups observed in natural images. This results in more meaningful embeddings for a variety of applications.

This paper proposes the minimum power configuration (MPC) approach to energy conservation in wireless sensor networks. In sharp contrast to earlier research that treats topology control, power-aware routing, and sleep management in isolation, MPC integrates them as a joint optimization problem in which the power configuration of a network consists of a set of active nodes and the transmission powers of the nodes.

We present a method for repairing topological errors on solid models in the form of small surface handles, which often arise from surface reconstruction algorithms. We utilize a skeleton representation that offers a new mechanism for identifying and measuring handles. Our method presents two unique advantages over previous approaches. First, handle removal is guaranteed not to introduce invalid geometry or additional handles. Second, by using an adaptive grid structure, our method is capable of processing huge models efficiently at high resolutions.

Motion planning algorithms enable us to find feasible paths for moving objects. These algorithms utilize feasibility checks to differentiate valid paths from invalid ones. Unfortunately, the computationally expensive nature of such checks reduces the effectiveness of motion planning algorithms. However, by using hardware acceleration to speed up the feasibility checks, we can greatly enhance the performance of the motion planning algorithms. Of course, such acceleration is not limited to feasibility checks; other components of motion planning algorithms can also be accelerated using specially designed hardware. A Field Programmable Gate Array (FPGA) is a great platform to support such an acceleration. An FPGA is a collection of digital gates which can be reprogrammed at run time, i.e., it can be used as a CPU that reconfigures itself for a given task. In this paper, we study the feasibility of an FPGA based motion planning processor and evaluate its performance. In order to leverage its highly parallel nature and its modular structure, our processor utilizes the probabilistic roadmap method at its core. The modularity enables us to replace the feasibility criteria with other ones. The reconfigurability lets us run our processor in different roles, such as a motion planning co-processor, an autonomous motion planning processor or dedicated collision detection chip. Our experiments show that such a processor is not only feasible but also can greatly increase the performance of current algorithms.

Colors that appear closer to the red end of the visible spectrum are said to be warm while the colors that appear closer to the blue end are said to be cool. The phenomenon of warmer colors appearing nearer in depth to viewers than cooler colors has been studied extensively by psychologists and other vision researchers. The vast majority of these studies have asked human observers to view physically equidistant, colored stimuli and compare them for relative depth. However, in most cases, the stimuli presented were rather simple: straight colored lines, uniform color patches, point light sources, or symmetrical objects with uniform shading. Additionally, the colors used were typically highly saturated. Although such stimuli are useful in isolating and studying depth cues in certain contexts, they leave open the question of whether the human visual system operates similarly for realistic objects. This paper presents the results of an experiment designed to explore the color-depth relationship for realistic, colored objects with varying shading and contours.

Mobile entity navigation in dynamic environments is an essential part of many mission critical applications like search and rescue and fire fighting. The dynamism of the environment necessitates the mobile entity to constantly maintain a high degree of awareness of the changing environment. This criteria makes it difficult to achieve good navigation performance by using just on-board sensors and existing navigation methods and motivates the use of wireless sensor networks (WSNs) to aid navigation. In this paper, we present a novel approach that integrates a roadmap based navigation algorithm with a novel WSN query protocol called Roadmap Query (RQ). RQ enables collection of frequent, up-to-date information about the surrounding environment, thus allowing the mobile entity to make good navigation decisions. Simulation results under realistic fire scenarios show that in highly dynamic environments RQ outperforms existing approaches in both navigation performance and communication cost. We also present a mobile agent based implementation of RQ along with preliminary experimental results, on Mica2 motes.

Manifold learning has become an important tool to characterize high-dimensional data that vary nonlinearly due to a few parameters. Applications to the analysis of medical imagery and human motion patterns have been successful despite the lack of effective tools to parameterize cyclic data sets. This paper offers an initial approach to this problem, and provides for a minimal parameterization of points that are drawn from cylindrical manifolds -- data whose (unknown) generative model includes a cyclic and a non-cyclic parameter. Solving for this special case is important for a number of current, practical applications and provides a start toward a general approach to cyclic manifolds. We offer results on synthetic and real data sets and illustrate an application to de-noising cardiac ultrasound images.

Synthesized or pre-recorded speech is often used for communication from robots to humans. In many situations, it may be unnecessary to use speech since much of the information which robots must communicate is often very simple and context-sensitive. In this paper we hypothesize that nonspeech aural communication may be more effective in many situations, and we present an experiment to test the effectiveness of non-verbal communication.

We have developed highly modular middleware for robotics programming and an interface for multi-robot teleoperation. WURDE provides abstractions for the communications, applications, and systems levels of robotic system development, which helps to isolate the developer from details not essential to the immediate task. RIDE is a control interface inspired by real time strategy games for tasking multiple robots at the same time, which increases the situational awareness of the operator and allows a single person to control many more robots than with single-robot interfaces. In this paper, we describe WURDE and RIDE and discuss how they were used in the 2006 AAAI Mobile Robot Competition and Exhibition.

In surveillance applications there may be multiple time scales at which it is important to monitor a scene. This work develops on-line, real-time algorithms that maintain background models simultaneously at many time scales. This creates a novel temporal de-composition of video sequence which can be used as a visualization tool for a human operator or an adaptive background model for classical anomaly detection and tracking algorithms. This paper solves the design problem for choosing appropriate time scales for the decomposition and derives the equations to approximately reconstruct the original video given only the temporal decompo-sition. We present two applications that highlight the potential of video processing; first a visualization tool that summarizes recent video behavior for a human operator in a single image, and second a pre-processing tool to detect "left bags" in the challenging PETS 2006 dataset which includes many occlusions of the left bag by pedestrians.

A method for extracting intersection-free iso-surfaces from volumetric data with an octree structure is presented. Unlike contouring techniques designed for uniform grids (such as Marching Cubes), adaptive contouring methods (such as Dual Contouring) can and do often generate intersecting polygons. Our main contribution is a polygon generation algorithm that produces triangles enclosed in nonoverlapping volumes, which guarantees an intersection-free mesh. Like other adaptive contouring methods, this new method generates crack-free and feature-preserving surfaces on both uniform and octree grids. We demonstrate the method on both scanned objects and industrial models.

Skeletons are important shape descriptors in object representation and recognition. Typically, skeletons of volumetric models are computed via an iterative thinning process. However, traditional thinning methods often generate skeletons with complex structures that are unsuitable for shape description, and appropriate pruning methods are lacking. In this paper, we present a new method for computing skeletons on volumes by alternating thinning and a novel skeleton pruning routine. Our method creates a family of skeletons parameterized by two user-specified numbers that determine respectively the size of curve and surface features on the skeleton. As demonstrated on both real-world models and medical images, our method generates skeletons with simple and meaningful structures that are particularly suitable for describing cylindrical and plate-like shapes.

Sectioning tissues for optical microscopy often introduces upon the resulting sections distortions that make 3d reconstruction diffcult. Here we present an automatic method for producing a smooth 3D volume from distorted 2D sections in the absence of any undistorted references. The method is based on pairwise elastic image warps between successive tissue sections, which can be computed by 2D image registration. Using a Gaussian filter, an average warp is computed for each section from the pairwise warps in a group of its neighboring sections. The average warps deform each section to match its neighboring sections, thus creating a smooth volume where corresponding features on successive sections lie close to each other. The proposed method can be used with any existing 2D image registration method for 3D reconstruction. In particular, we present a novel image warping algorithm based on dynamic programming that extends Dynamic Time Warping in 1D speech recognition to compute pairwise warps between high-resolution 2D images. The warping algorithm efficiently computes a restricted class of 2D local deformations that are characteristic between successive tissue sections. Finally, a validation framework is proposed and applied to evaluate the quality of reconstruction using both real sections and a synthetic volume.

Traditional approaches to teaching computer science are often unsuccessful in attracting girls into the discipline. Our hypothesis is that presenting computer programming as a means to the end of storytelling will help motivate girls to learn to program, a traditional gateway to computer science. In this paper, we present a case study in designing a version of the Alice programming system to support storytelling. We present lessons we learned about what supports are necessary to enable girls to program animated movies and describe the kinds of programming tasks that arise in girls

Reaction-Diffusion (RD) was first introduced as a model of morphogenesis, a biological pattern-formation process in which two or more morphogens diffuse over a surface and react with each other to create certain animal coat patterns, such as spots and stripes [Tur52]. Used as the basis for texture synthesis, RD allows an unlimited amount of non-repeating texture and offers great flexibility for mapping textures to arbitrary surfaces. However, it can be difficult to find starting values of parameters that will produce interesting patterns. In this work, we present an interactive interface for sketching RD textures. We use machine learning to resolve the difficulty of determining appropriate initial values of the RD system. The system described here allows a user to sketch a pattern of spots or stripes with arbitrary orientations, and then automatically generates a pattern with the same attributes as the sketch. It also allows the user to interactively create more complex textures by adding another layer of pattern, as well as manipulate the color of the resulting texture. We also show that this procedure can be applied to realistic 3D surfaces.

We propose a simple generalization of Shephard's interpolation to piecewise smooth, convex closed curves that yields a family of boundary interpolants with linear precision. Two instances of this family reduce to previously known interpolants: one based on a generalization of Wachspress coordinates to smooth curves and the other an integral version of mean value coordinates for smooth curves. A third instance of this family yields a previously unknown generalization of discrete harmonic coordinates to smooth curves. For closed, piecewise linear curves, we prove that our interpolant reproduces a general family of barycentric coordinates considered by Floater, Hormann and Kos that includes Wachspress coordinates, mean value coordinates and discrete harmonic coordinates.

When there are only a few underlying causes of the deformation, these images have a natural lowdimensional structure which can be parameterized using manifold learning. This paper presents a method to solve for the deformation field as a function of the manifold coordinates ? implicitly optimizing the deformation between all pairs of images simultaneously. Additionally, we provide a mechanism to create images for arbitrary coordinates of the manifold.

The equilibrium binding of E. coli RecBC and RecBCD helicases to duplex DNA ends containing varying lengths of polyethylene glycol (PEG) spacers within pre-formed 3'-single-stranded (ss) DNA ((dT)n) tails were studied. These studies were designed to test a previous proposal that the 3'-(dT)n tail can be looped out upon binding RecBC and RecBCD for 3'-ssDNA tails with n>=6 nucleotides. Equilibrium binding of protein to unlabeled DNA substrates with ends containing PEG-substituted 3'-ssDNA tails was examined by competition with a Cy3-labeled reference DNA which undergoes a Cy3 fluorescence enhancement upon protein binding. We find that the binding affinities of both RecBC and RecBCD for a DNA end are unaffected upon substituting PEG for the ssDNA between the sixth and the final two nucleotides of the 3'-(dT)n tail. However, placing PEG at the end of the 3'-(dT)n tail increases the binding affinities to their maximum values (i.e. the same as binding constants for RecBC or RecBCD to a DNA end with only a 3'-(dT)6 tail). Equilibrium binding studies of a RecBC mutant containing a nuclease domain deletion, RecBC suggest that looping of the 3'-tail (when n>=6 nucleotides) occurs even in the absence of the RecB nuclease domain, the nuclease domain stabilizes such loop formation. Computer modeling of the RecBCD-DNA complexes suggests that the loop in the 3'-ssDNA tail may form at the RecB/RecC interface. Based on these results we suggest a model for how a loop in the 3'-ssDNA tail might form upon encounter of a "Chi" recognition sequence during unwinding of DNA by the RecBCD helicase.

We develop theory and algorithms to incorporate image manifold constraints in a level set segmentation algorithm. This provides a framework to simultaneously segment every image of data sets that vary due to two degrees of freedom - such as cardiopulmonary MR images which deform due to patient breathing and heartbeats.

We address the problem of segmenting multiple similar objects by optimizing a Chan-Vese-like functional with respect to a mixture of level set functions. We solve the variational formulation under this model allowing for similarity transforms. This allows shape priors to be enforced even in the presence of mutual occlusion. We show numerical results on example images to demonstrate the promise of our approach.

We present a technique to automatically synthesize dancing motions for arbitrary songs with dance beats. Our technique is based on analyzing a musical tune and synthesizing a motion for the virtual character where the character's movement synchronizes to the musical beats. Our motion synthesis algorithm analyses library of stock motions and generates new sequences of synchronized movements that were not described in the library.

Autonomous mobile agent navigation is crucial to many mission-critical applications (e.g., search and rescue missions in a disaster area). In this paper, we present how sensor networks may assist probabilistic roadmap methods (PRMs), a class of ef^Bcient navigation algorithms particularly suitable for dynamic environments. A key challenge of applying PRM algorithms in dynamic environment is that they require the spatiotemporal sensing of the environment to solve a given navigation problem. To facilitate navigation, we propose a set of query strategies that allow a mobile agent to periodically collect real-time information (e.g., fire conditions) about the environment through a sensor network. Such strategies include local spatiotemporal query (query of spatial neighborhood), global spatiotemporal query (query of all sensors), and border query (query of the border of danger fields). We investigate the impact of different query strategies through simulations under a set of realistic fire conditions. We also evaluate the feasibility of our approach using a real robot and real motes. Our results demonstrate that (1) spatiotemporal queries from a sensor network result in significantly better navigation performance than traditional approaches based on on-board sensors of a robot, (2) the area of local queries represent a tradeoff between communication cost and navigation performance, (3) through in-network processing our border query strategy achieves the best navigation performance at a small fraction of communication cost compared to global spatiotemporal queries.

In this paper, we present an FPGA (Field Programmable Gate Array) based collision detection chip. The chip can be used as a co-processor for a traditional computer or several of them can be utilized to work in parallel to create a very fast collision detection server for real time environments. In our experiments we have seen speeds-up of 36 with respect to a fast Pentium 4 chip. Further improvements are possible by using more advanced collision detection techniques.

We present a method, the Curvature Map, that uses surface curvature properties in a region around a point to create a unique signature for that point. These signatures, which are based on either rings (which use the local topology of the mesh) or Geodesic Fans (which trace geodesics along the mesh from the point), can then be compared to determine the similarity of one point to another. Point similarities are important for applications such as medical diagnosis, object registration and alignment, and shape retrieval.

We present methods to better leverage observed experience by reusing experience across parts of the problem state space that are known to be similar. We present experimental results in a navigational, goal-based domain, and develop an approach to identifying portions of the world that appear similar based on observed transition samples.

We apply simplified image-based lighting methods to reduce the equipment, cost, time, and specialized skills required for high-quality photographic lighting of desktop-sized static objects such as museum artifacts. We place the object and a computer-steered moving-head spotlight inside a simple foam-core enclosure, and use a camera to quickly record low-resolution photos as the light scans the box interior. Optimization guided by interactive user sketching selects a small set of frames whose weighted sum best matches the target image. The system then repeats the lighting used in each of these frames, and constructs a high resolution result from re-photographed basis images. Unlike previous image-based relighting efforts, our method requires only one light source, yet can achieve high resolution light positioning to avoid multiple sharp shadows. A reduced version uses only a hand-held light, and may be suitable for battery-powered, field photography equipment that fits in a backpack.

This paper experimentally compares the performance of a collection of models of dynamic backgrounds, that allow object/anomaly detection in scenes with waving trees, water motion, etc.

Manifold learning has become a vital tool in data driven methods for interpretation of video, motion capture, and handwritten character data. This work extends manifold learning to classify and parameterize unlabeled data which lie on multiple, intersecting manifolds. This approach introduces several technical contributions which may be of broader interest, including node-weighted multidimensional scaling and a fast algorithm for weighted low-rank approximation for rank-one weight matrices.

For the case of image sets of an unknown object undergoing an unknown deformation, we show that Isomap, using domain-specific distance metrics, gives a valuable pre-processing step to finding an ordering of the images in terms of their deformation.

We describe methods for spatio-temporal background modeling, anomaly detection, shape description, and object localization on data sets containing low-quality video, unpredictable camera motion, and dropped frames.

The concept of "curved perspective" been used by artists such as M.C. Escher in order effectively convey a sense of three dimensional space while being restricted to a two dimensional canvas. We present an interactive system to create and manipulate projections with a curvilinear perspective. Our system presents the user with a set of intuitive screen-space perspective primitives that control the vanishing points of the scene. This allows the user to generate diverse projections having curved perspective.

Provides a geometric analysis of the relationship between coverage and connectivity. This yields key insights for treating coverage and connectivity within a unified framework, in contrast to approaches that address the two problems in isolation. One algorithm provides both coverage and connectivity guarantees, and we propose a probabilistic coverage model and extend CCP to provide probabilistic coverage guarantees.

Cardiopulmonary imaging is a key tool in modern diagnostic and interventional medicine. Automated analysis of MRI or ultrasound video is complicated by limitations on the image quality and complicated deformations of the chest cavity created by patient breathing and heart beating. When these are the primary causes of image variation, the video sequence samples a two-dimensional, nonlinear manifold of images. Nonparametric representations of this image manifold provide strong new cues on the shape and deformation of particular regions of interest. This paper develops the theory and algorithms to incorporate these manifold constraints within a level set based segmentation algorithm. We apply our algorithm, based on manifold constraints to the problem of segmenting the left ventricle, and show the improvement that arises from using the manifold constraints.

In many biomedical imaging applications, video sequences are captured with low resolution and low contrast challenging conditions in which to detect, segment, or track features. When image deformations have just a few underlying causes, such as continuously captured cardiac MRI without breath-holds or gating, the captured images lie on a low-dimensional, nonlinear manifold. The manifold structure of these images offers new constraints for tracking and segmentation of relevant image regions. We illustrate how to incorporate these new constraints within a snake-based energy minimization approach, and demonstrate improvements in using snakes to segment a set of cardiac MRI images in challenging conditions.

This thesis explores techniques for shading 3D computer generated models using scanned images of actual paint samples.

This paper presents a direct interface, where an artist manipulates in 2D the desired projection of a few features of the 3D scene to specify a nonlinear projection. The features represent a rich set of constraints which define the overall projection of the 3D scene. Desirable properties of local linear perspective and global scene coherence drive a heuristic algorithm that attempts to interactively satisfy the sketched constraints as a weight-averaged projection of a minimal set of linear perspective cameras.

This paper presents a method for constructing a topologically-aware value-function approximator for solving Reinforcement Learning problems with continuous, multi-dimensional state spaces. We use a manifold representation to combine approximator predictions in small, well-behaved neighborhoods to construct a global approximation of the value function.

This is a more complete version of the Shape Modeling International Conference paper. It has improved methods for mapping a mesh to the appropriate topology. It also includes a summary of the n-holed work from the Mathematics of Surfaces paper.

Empirically measures the prior distribution of color differences between matching pixels using an augmented calibration set-up, in order to support true Bayesian Stereo Matching for Robot Navigation.

This paper presents a method for modeling contact areas and ligament lengths in articulations between joints. The approach Is a combination of signed distance volume techniques and smooth surface modeling.

This paper introduces algorithms for detecting roads based on statistics of image derivative measurements captured in real time from extended aerial video.

The paper specializes Isomap for the analysis of non-rigid heart deformation using image distance measures that measure along the tangent space of the deformation groups.

Describes the generalized epi-polar constraint for generalized cameras in the sense introduced by Greenburg and Nayar.

The IBar provides a compelling interface for controlling scene perspective based on the artistic concept of vanishing points. Various handles on the widget manipulate multiple camera parameters simultaneously to create a single perceived projection change.

We present an image-space camera manipulation widget that supports visualization of the relationship of the camera with respect to the scene.Visual aids such as ghosting of the scene and preview animations are used to acquaint novice users with the functions of different parts of the widget. Finally, we provide a novel method for visualizing camera bookmarks.

In sensor networks that provide coverage gauruntees, not only is the communication graphs connected, greedy geographic forwarding has very good, provable bounds on hop count and overall distance relative to the optimal path and Euclidean shortest path.

A distributed heuristic for finding good sets of active nodes in a sensor network, maintaining both communications connectivity, and "sufficient" coverage, for a sensing model with noise that requires multiple sensors to be sufficiently close to an event location for robust detection.

This work describes theoretical and experimental results for the extrinsic calibration of sensor platform consisting of a camera and a 2D laser range finder.Additionally the constraint introduced for the extrinsic calibration can reduce the variance in estimating intrinsic camera parameters

This paper describes a framework for calibrating motion sensitive sensors attached to an autonomous vehicle.For the case of a camera and laser range finder, we present an auto-calibration algorithm for discrete motions.

This work considers the geometric constraints to combine structure from motion with a sparse set of depth measurements. The goal is to improve the motion estimation for autonomous navigation, and to increase the fidelity of reconstructed 3D scene models

We describe a complete, end-to-end system for taking well-composed photographs using a mobile robot. The general scenario is a reception, or other event, where people are roaming around talking to each other. The robot serves as an "event photographer", roaming around the same space as the participants, periodically taking photographs. These images are then sent to a workstation where participants can print the photographs out, or email them.

We have developed an autonomous robot system that takes well-composed photographs of people at social events, such as weddings and conference receptions. The robot, Lewis, navigates through the environment, opportunistically taking photographs of people. In this paper, we outline the overall architecture of the system and describe how the various components inter-relate. We also describe our experiences of deploying the robot photographer at a number of real-world events.

This paper focuses on the types of interaction we saw at various events, and suggests that the robot needs two interaction modes. The first is "stealth" mode, where the robot is just wandering around, ignored. In the second mode, the robot responds to a specific human request, such as waving a hand to get the robot's attention.

This paper presents three techniques for producing rendered, shaded images of 3D meshes using scanned images of paint samples. All three techniques use texture synthesis to generate additional paint samples. The techniques emphasise artisitc control of brush stroke texture and color.

Parameterizing n-holed tori using hyperbolic geometry. In this paper we use the hyperbolic polygon , modeled as a manifold, as the domain for n-holed tori. This approach was first used by Alyn Rockwood , who creates a multi-periodic function over the hyperbolic polygon.

The magnitude of flow through each edge of a network can be infered from sensors at each source and sink, and sensors on every node of a co-tree. We give efficient approximation algorithms for finding co-trees with few nodes.

Proceedings of the 2003 Omnivis workshop

An exploration of dimensionality reduction (Isomap) for video. The temporal sequence of images creates an implicit manifold and a trajectory through that manifold, that is highly informative about the behaviors in the sequence.

Images captured by a collection of cameras can be viewed as a single image captured by a non-central projection camera. A consistent framework for motion estimation from networks of cameras is presented, using Plucker vectors to represent arbitrary imaging geometries. The Fisher information matrix is analytically computed for each camera network, and allows quantitative design of camera networks optimized to estimate particular ego-motion distributions.

Using spatio-temporal image derivatives gives a method for characterizing background behavior. The distribution of derivatives , at each pixel, can be represented as the best fitting optic flow, a Gaussian, or a mixture model. These representations are compared in varied data sets using ROC response curves.

We build an inexpensive 3D input device using a camera, a piece of cardboard, and a laser pointer. The cardboard has a calibration pattern printed on the back which the camera tracks. The inside of the cardboard is clear plastic, and is our drawing surface. The laser pen shines through the plastic and is also tracked by the camera.

Calculating dense estimates of strain fields using tagged MRI imagery via local fourier transforms.

We have developed a calibration pattern suitable for object capture. The pattern is visible from the full upper hemisphere and is robust to different lighting conditions.

In a sensor network, a subset of nodes must be active to ensure both communications connectivity and sensing coverage. Choosing small subsets of nodes is easy in the case when the communications range is at least twice the sensing range.

Fitting mesh surfaces to a simple manifold of the same topology. Describes a simple manifold for a plane, sphere, and torus, and how to fit a mesh to that manifold. We define a bijection between the mesh and the manifold. We then show how to create an embedding of the manifold that approximates the mesh.

his paper shows how to fit a manifold surface to CT data in three steps, starting with a coarse mesh and working down to the control points of the surface.

Extensions of the epi-polar constraint for arbibtrary, non-central projection cameras, including unusual imaging geometries formed by cameras looking through curved optical interfaces.

A modificatin of Isomap to provide a parameterization of data that lives on a manifold isometric to a sphere, cylinder, torus, or their higher dimensional correlates.

Simple post-processing of Isomap embedding of images of an object from different poses gives tools for pose estimation without an explicit object model.

We have smooth models of bones and can easily measure the closest distance between two bone surfaces. We use the distances to color the bone, or draw contours. This can be used as a diagnostic tool to determine if the bones are correctly spaced.

Use a ray tracer (or other 3D rendering engine) to create accurate images of objects, possibly from different viewpoints. Now take those images and alter them by moving them around, changing their size, and their color.

A technique for making "fat worms" using an axis curve and one or more profile curves which describe how far the surface is from the axis. Also extends to two axes (a ruled surface). Also describes a user interface.

A system for the accurate capture of faces. You, too, can have dots glued all over your face.

A framework for combining multiple curve representations under one umbrella.

This paper discusses the difficulties in creating a coherent user interface for interactive modeling. To this end we present four principles for designing visual operators, using several freeform visual operators as concrete examples.

A surface modeling paradigm that is an extension of B-splines to surfaces of arbitrary topology. It models everything from roses to striped dinosaurs.

Converting an implicit surface to a parametric representation using a cute trick with edge cycles created by the marching cubes algorithm.