Navigating in a previously unknown environment and recognizing naturally occurring text in a scene are two important autonomous capabilities that are typically treated as distinct. However, these two tasks are potentially complementary, (i) scene and pose priors can benefit text spotting, and (ii) the ability to identify and associate text features can benefit navigation accuracy through loop closures. Previous approaches to autonomous text spotting typically require significant training data and are too slow for real-time implementation. In this work, we propose a novel high-level feature descriptor, the “junction”, which is particularly well-suited to text representation and is also fast to compute. We show that we are able to improve SLAM through text spotting on datasets collected with a Google Tango, illustrating how location priors enable improved loop closure with text features.

We describe a semantic mapping algorithm that learns human-centric environment models by interpreting natural language utterances. Underlying the approach is a coupled metric, topological, and semantic representation of the environment that enables the method to fuse information from natural language descriptions with low-level metric and appearance data. We extend earlier work with a novel formulation that incorporates spatial layout into a topological representation of the environment. We also describe a factor graph formulation of the semantic properties that encodes human-centric concepts such as type and colloquial name for each mapped region. The algorithm infers these properties by combining the user's natural language descriptions with image- and laser-based scene classification. We also propose a mechanism to more effectively ground natural language descriptions of distant regions using semantic cues from other modalities. We describe how the algorithm employs this learned semantic information to propose valid topological hypotheses, leading to more accurate topological and metric maps. We demonstrate that integrating language with other sensor data increases the accuracy of the achieved spatial-semantic representation of the environment.

The paper describes the system developed by researchers from MIT for the Defense Advanced Research Projects Agency's (DARPA) Virtual Robotics Challenge (VRC), held in June 2013. The VRC was the first competition in the DARPA Robotics Challenge (DRC), a program that aims to “develop ground robotic capabilities to execute complex tasks in dangerous, degraded, human-engineered environments”. The VRC required teams to guide a model of Boston Dynamics' humanoid robot, Atlas, through driving, walking, and manipulation tasks in simulation. Team MIT's user interface, the Viewer, provided the operator with a unified representation of all available information. A 3D rendering of the robot depicted its most recently estimated body state with respect to the surrounding environment, represented by point clouds and texture-mapped meshes as sensed by on-board LIDAR and fused over time.

We describe and evaluate two methods for device pose classification and walking speed estimation that generalize well to new users, compared to previous work. These machine learning based methods are designed for the general case of a person holding a mobile device in an unknown location and require only a single low-cost, low-power sensor: a triaxial accelerometer. We evaluate our methods in straight-path indoor walking experiments as well as in natural indoor walking settings. Experiments with 14 human participants to test user generalization show that our pose classifier correctly selects among four device poses with 94% accuracy compared to 82% for previous work, and our walking speed estimates are within 12-15% (straight/indoor walk) of ground truth compared to 17-22% for previous work. Implementation on a mobile phone demonstrates that both methods can run efficiently online.

This paper describes a system enabling rapid multi-floor indoor map building using a body-worn sensor system fusing information from RGB-D cameras, LIDAR, inertial, and barometric sensors. Our work is motivated by rapid response missions by emergency personnel, in which the capability for one or more people to rapidly map a complex indoor environment is essential for public safety. Human-portable mapping raises a number of challenges not encountered in typical robotic mapping applications including complex 6-DOF motion and the traversal of challenging trajectories including stairs or elevators. Our system achieves robust performance in these situations by exploiting state-of-the-art techniques for robust pose graph optimization and loop closure detection. It achieves real-time performance in indoor environments of moderate scale. Experimental results are demonstrated for human-portable mapping of several floors of a university building, demonstrating the system's ability to handle motion up and down stairs and to organize initially disconnected sets of submaps in a complex environment.

This paper describes a new model for understanding natural language commands given to autonomous systems that perform navigation and mobile manipulation in semi-structured environments. Previous approaches have used models with fixed structure to infer the likelihood of a sequence of actions given the environment and the command. In contrast, our framework, called Generalized Grounding Graphs, dynamically instantiates a probabilistic graphical model for a particular natural language command according to the command's hierarchical and compositional semantic structure. Our system performs inference in the model to successfully find and execute plans corresponding to natural language commands such as "Put the tire pallet on the truck." The model is trained using a corpus of commands collected using crowdsourcing. We pair each command with robot actions and use the corpus to learn the parameters of the model. We evaluate the robot's performance by inferring plans from natural language commands, executing each plan in a realistic robot simulator, and asking users to evaluate the system's performance. We demonstrate that our system can successfully follow many natural language commands from the corpus.

We describe a robotic tour-taking capability enabling a robot to acquire local knowledge of a human-occupied environment. A tour-taking robot autonomously follows a human guide through an environment, interpreting the guide's spoken utterances and the shared spatiotemporal context in order to acquire a spatially segmented and semantically labeled metrical-topological representation of the environment. The described tour-taking capability enables scalable deployment of mobile robots into human-occupied environments, and natural human-robot interaction for commanded mobility. Our primary contributions are an efficient, socially acceptable autonomous tour-following behavior and a tour interpretation algorithm that partitions a map into spaces labeled according to the guide's utterances. The tour-taking behavior is demonstrated in a multi-floor office building and evaluated by assessing the comfort of the tour guides, and by comparing the robot's map partitions to those produced by humans.

The Rapidly-exploring Random Tree (RRT) algorithm, based on incremental sampling, efficiently computes motion plans. Although the RRT algorithm quickly produces candidate feasible solutions, it tends to converge to a solution that is far from optimal. Practical applications favor "anytime" algorithms that quickly identify an initial feasible plan, then, given more computation time available during plan execution, improve the plan toward an optimal solution. This paper describes an anytime algorithm based on the RRT* which (like the RRT) finds an initial feasible solution quickly, but (unlike the RRT) almost surely converges to an optimal solution. We present two key extensions to the RRT% committed trajectories and branch-and-bound tree adaptation, that together enable the algorithm to make more efficient use of computation time online, resulting in an anytime algorithm for real-time implementation. We evaluate the method using a series of Monte Carlo runs in a high-fidelity simulation environment, and compare the operation of the RRT and RRT* methods. We also demonstrate experimental results for an outdoor wheeled robotic vehicle.

Many indoor localization methods are based on the association of 802.11 wireless RF signals from wireless access points (WAPs) with location labels. An “organic” RF positioning system relies on regular users, not dedicated surveyors, to build the map of RF fingerprints to location labels. However, signal variation due to device heterogeneity may degrade localization performance. We analyze the diversity of those signal characteristics pertinent to indoor localization - signal strength and AP detection - as measured by a variety of 802.11 devices. We first analyze signal strength diversity, and show that pairwise linear transformation alone does not solve the problem. We propose kernel estimation with a wide kernel width to reduce the difference in probability estimates. We also investigate diversity in access point detection. We demonstrate that localization performance may degrade significantly when AP detection rate is used as a feature for localization, and correlate the loss of performance to a device dissimilarity measure captured by Kullback-Leibler divergence. Based on this analysis, we show that using only signal strength, without incorporating negative evidence, achieves good localization performance when devices are heterogeneous.

A desirable property of path planning for robotic manipulation is the ability to identify solutions in a sufficiently short amount of time to be usable. This is particularly challenging for the manipulation problem due to the need to plan over high-dimensional configuration spaces and to perform computationally expensive collision checking procedures. Consequently, existing planners take steps to achieve desired solution times at the cost of low quality solutions. This paper presents a planning algorithm that overcomes these difficulties by augmenting the asymptotically-optimal RRT* with a sparse sampling procedure. With the addition of a collision checking procedure that leverages memoization, this approach has the benefit that it quickly identifies low-cost feasible trajectories and takes advantage of subsequent computation time to refine the solution towards an optimal one. We evaluate the algorithm through a series of Monte Carlo simulations of seven, twelve, and fourteen degree of freedom manipulation planning problems in a realistic simulation environment. The results indicate that the proposed approach provides significant improvements in the quality of both the initial solution and the final path, while incurring almost no computational overhead compared to the RRT algorithm. We conclude with a demonstration of our algorithm for single-arm and dual-arm planning on Willow Garage's PR2 robot.

We demonstrate a method for collaborative ranking of future events. Previous work on recommender systems typically relies on feedback on a particular item, such as a movie, and generalizes this to other items or other people. In contrast, we examine a setting where no feedback exists on the particular item. Because direct feedback does not exist for events that have not taken place, we recommend them based on individuals' preferences for past events, combined collaboratively with other peoples' likes and dislikes. We examine the topic of unseen item recommendation through a user study of academic (scientific) talk recommendation, where we aim to correctly estimate a ranking function for each user, predicting which talks would be of most interest to them. Then by decomposing user parameters into shared and individual dimensions, we induce a similarity metric between users based on the degree to which they share these dimensions. We show that the collaborative ranking predictions of future events are more effective than pure content-based recommendation. Finally, to further reduce the need for explicit user feedback, we suggest an active learning approach for eliciting feedback and a method for incorporating available implicit user cues.

We describe a multimodal framework for interacting with an autonomous robotic forklift. A key element enabling effective interaction is a wireless, handheld tablet with which a human supervisor can command the forklift using speech and sketch. Most current sketch interfaces treat the canvas as a blank slate. In contrast, our interface uses live and synthesized camera images from the forklift as a canvas, and augments them with object and obstacle information from the world. This connection enables users to "draw on the world," enabling a simpler set of sketched gestures. Our interface supports commands that include summoning the forklift and directing it to lift, transport, and place loads of palletized cargo. We describe an exploratory evaluation of the system designed to identify areas for detailed study.

This paper describes a new algorithm for cooperative and persistent simultaneous localization and mapping (SLAM) using multiple robots. Recent pose graph representations have proven very successful for single robot mapping and localization. Among these methods, incremental smoothing and mapping (iSAM) gives an exact incremental solution to the SLAM problem by solving a full nonlinear optimization problem in real-time. In this paper, we present a novel extension to iSAM to facilitate online multi-robot mapping based on multiple pose graphs. Our main contribution is a relative formulation of the relationship between multiple pose graphs that avoids the initialization problem and leads to an efficient solution when compared to a completely global formulation. The relative pose graphs are optimized together to provide a globally consistent multi-robot solution. Efficient access to covariances at any time for relative parameters is provided through iSAM, facilitating data association and loop closing. The performance of the technique is illustrated on various data sets including a publicly available multi-robot data set. Further evaluation is performed in a collaborative helicopter and ground robot experiment.

Precise calibration of camera intrinsic and extrinsic parameters, while often useful, is difficult to obtain during field operation and presents scaling issues for multi-robot systems. We demonstrate a vision-based approach to navigation that does not depend on traditional camera calibration, and present an algorithm for guiding a robot through a previously traversed environment using a set of uncalibrated cameras mounted on the robot. On the first excursion through an environment, the system builds a topological representation of the robot's exploration path, encoded as a place graph. On subsequent navigation missions, the method localizes the robot within the graph and provides robust guidance to a specified destination. We combine this method with reactive collision avoidance to obtain a system able to navigate the robot safely and reliably through the environment. We validate our approach with ground-truth experiments and demonstrate the method on a small ground rover navigating through several dynamic environments.

One long-standing challenge in robotics is the realization of mobile autonomous robots able to operate safely in existing human workplaces in a way that their presence is accepted by the human occupants. We describe the development of a multi-ton robotic forklift intended to operate alongside human personnel, handling palletized materials within existing, busy, semi-structured outdoor storage facilities. The system has three principal novel characteristics. The first is a multimodal tablet that enables human supervisors to use speech and pen-based gestures to assign tasks to the forklift, including manipulation, transport, and placement of palletized cargo. Second, the robot operates in minimally-prepared, semi-structured environments, in which the forklift handles variable palletized cargo using only local sensing (and no reliance on GPS), and transports it while interacting with other moving vehicles. Third, the robot operates in close proximity to people, including its human supervisor, other pedestrians who may cross or block its path, and forklift operators who may climb inside the robot and operate it manually. This is made possible by novel interaction mechanisms that facilitate safe, effective operation around people. We describe the architecture and implementation of the system, indicating how real-world operational requirements motivated the development of the key subsystems, and provide qualitative and quantitative descriptions of the robot operating in real settings.

This paper addresses the problem of autonomous manipulation of a priori unknown palletized cargo with a robotic lift truck (forklift). Specifically, we describe coupled perception and control algorithms that enable the vehicle to engage and place loaded pallets relative to locations on the ground or truck beds. Having little prior knowledge of the objects with which the vehicle is to interact, we present an estimation framework that utilizes a series of classifiers to infer the objects' structure and pose from individual LIDAR scans. The classifiers share a low-level shape estimation algorithm that uses linear programming to robustly segment input data into sets of weak candidate features. We present and analyze the performance of the segmentation method, and subsequently describe its role in our estimation algorithm. We then evaluate the performance of a motion controller that, given an estimate of a pallet's pose, is employed to safely engage each pallet. We conclude with a validation of our algorithms for a set of real-world pallet and truck interactions.

Most current methods for 802.11-based indoor localization depend on surveys conducted by experts or skilled technicians. Some recent systems have incorporated surveying by users. Structuring localization systems "organically," however, introduces its own set of challenges: conveying uncertainty, determining when user input is actually required, and discounting erroneous and stale data. Through deployment of an organic location system in our nine-story building, which contains nearly 1,400 distinct spaces, we evaluate new algorithms for addressing these challenges. We describe the use of Voronoi regions for conveying uncertainty and reasoning about gaps in coverage, and a clustering method for identifying potentially erroneous user data. Our algorithms facilitate rapid coverage while maintaining positioning accuracy comparable to that achievable with survey-driven indoor deployments.

We describe a speech system for commanding robots in human-occupied outdoor military supply depots. To operate in such environments, the robots must be as easy to interact with as are humans, i.e. they must reliably understand ordinary spoken instructions, such as orders to move supplies, as well as commands and warnings, spoken or shouted from distances of tens of meters. These design goals preclude close-talking microphones and “push-to-talk” buttons that are typically used to isolate commands from the sounds of vehicles, machinery and non-relevant speech. We used multiple microphones to provide omnidirectional coverage. A novel voice activity detector was developed to detect speech and select the appropriate microphone to listen to. Finally, we developed a recognizer model that could successfully recognize commands when heard amidst other speech within a noisy environment. When evaluated on speech data in the field, this system performed significantly better than a more computationally intensive baseline system, reducing the effective false alarm rate by a factor of 40, while maintaining the same level of precision.

We present a vision-based method that assists human navigation within unfamiliar environments. Our main contribution is a novel algorithm that learns the correlation between user egomotion and feature matches on a wearable set of uncalibrated cameras. The primary advantage of this method is that it provides robust guidance cues in the user's body frame, and is tolerant to small changes in the camera configuration. We couple this method with a topological mapping algorithm that provides global localization within the traversed environment. We validate our approach with ground-truth experiments and demonstrate the method on several real-world datasets spanning two kilometers of indoor and outdoor walking excursions.

Recent applications of robotics often demand two types of spatial awareness: 1) A fine-grained description of the robot's immediate surroundings for obstacle avoidance and planning, and 2) Knowledge of the robot's position in a large-scale global coordinate frame such as that provided by GPS. Although managing information at both of these scales is often essential to the robot's purpose, each scale has different requirements in terms of state representation and handling of uncertainty. In such a scenario, it can be tempting to pick either a body-centric coordinate frame or a globally fixed coordinate frame for all state representation. Although both choices have advantages, we show that neither is ideal for a system that must handle both global and local data. This paper describes an alternative design: a third coordinate frame that stays fixed to the local environment over short time-scales, but can vary with respect to the global frame. Careful management of uncertainty in this local coordinate frame makes it well-suited for simultaneously representing both locally and globally derived data, greatly simplifying system design and improving robustness. We describe the implementation of this coordinate frame and its properties when measuring uncertainty, and show the results of applying this approach to our 2007 DARPA Urban Challenge vehicle.

This paper describes an algorithm for estimating lane boundaries and curbs from a moving vehicle using noisy observations and a probabilistic model of curvature. The primary contribution of this paper is a curve model we call lateral uncertainty, which describes the uncertainty of a curve estimate along the lateral direction at various points on the curve, and does not attempt to capture uncertainty along the longitudinal direction of the curve. Additionally, our method incorporates expected road curvature information derived from an empirical study of a real road network. Our method is notable in that it accurately captures the geometry of arbitrarily complex lane boundary curves that are not well approximated by straight lines or low-order polynomial curves. Our method operates independently of the direction of travel of the vehicle, and incorporates sensor uncertainty associated with individual observations. We analyze the benefits and drawbacks of the approach, and show results of our algorithm applied to real world data sets.

The moving-baseline localization (MBL) problem arises when a group of nodes moves through an environment in which no external coordinate reference is available. When group members cannot see or hear one another directly, each node must employ local sensing and inter-device communication to infer the spatial relationship and motion of all other nodes with respect to itself. We consider a setting in which nodes move with piecewise-linear velocities in the plane, and any node can exchange noisy range estimates with certain sufficiently nearby nodes. We develop a distributed solution to the MBL problem in the plane, in which each node performs robust hyperbola fitting, trilateration with velocity constraints, and subgraph alignment to arrive at a globally consistent view of the network expressed in its own "rest frame." Changes in any node's motion cause deviations between observed and predicted ranges at nearby nodes, triggering revision of the trajectory estimates computed by all nodes. We implement and analyze our algorithm in a simulation informed by the characteristics of a commercially available ultra-wideband (UWB) radio, and show that recovering node trajectories, rather than just locations, requires substantially less computation at each node. Finally, we quantify the minimum ranging rate and local network density required for the method's successful operation.

Robust egomotion recovery for extended camera excursions has long been a challenge for machine vision researchers. Existing algorithms handle spatially limited environments and tend to consume prohibitive computational resources with increasing excursion time and distance. We describe an egomotion estimation algorithm that takes as input a coarse 3D model of an environment, and an omnidirectional video sequence captured within the environment, and produces as output a reconstruction of the camera's 6-DOF egomotion expressed in the coordinates of the input model. The principal novelty of our method is a robust matching algorithm that associates 2D edges from the video with 3D line segments from the input model. Our system handles 3-DOF and 6-DOF camera excursions of hundreds of meters within real, cluttered environments. It uses a novel prior visibility analysis to speed initialization and dramatically accelerate image-to-model matching. We demonstrate the method's operation, and qualitatively and quantitatively evaluate its performance, on both synthetic and real image sequences.

This paper describes a new approach to motion estimation in video. We represent video motion using a set of particles. Each particle is an image point sample with a longduration trajectory and other properties. To optimize these particles, we measure point-based matching along the particle trajectories and distortion between the particles. The resulting motion representation is useful for a variety of applications and cannot be directly obtained using existing methods such as optical flow or feature tracking. We demonstrate the algorithm on challenging real-world videos that include complex scene geometry, multiple types of occlusion, regions with low texture, and non-rigid deformations.

A robot exploring an environment can estimate its own motion and the relative positions of features in the environment. Simultaneous localization and mapping (SLAM) algorithms attempt to fuse these estimates to produce a map and a robot trajectory. The constraints are generally non-linear, thus SLAM can be viewed as a non-linear optimization problem. The optimization can be difficult, due to poor initial estimates arising from odometry data, and due to the size of the state space. We present a fast non-linear optimization algorithm that rapidly recovers the robot trajectory, even when given a poor initial estimate. Our approach uses a variant of stochastic gradient descent on an alternative state-space representation that has good stability and computational properties. We compare our algorithm to several others, using both real and synthetic data sets

The localization problem is to determine an assignment of coordinates to nodes in a wireless ad-hoc or sensor network that is consistent with measured pairwise node distances. Most previously proposed solutions to this problem assume that the nodes can obtain pairwise distances to other nearby nodes using some ranging technology. However, for a variety of reasons that include obstructions and lack of reliable omnidirectional ranging, this distance information is hard to obtain in practice. Even when pairwise distances between nearby nodes are known, there may not be enough information to solve the problem uniquely. This paper describes MAL, a mobile-assisted localization method which employs a mobile user to assist in measuring distances between node pairs until these distance constraints form a "globally rigid'* structure that guarantees a unique localization. We derive the required constraints on the mobile's movement and the minimum number of measurements it must collect; these constraints depend on the number of nodes visible to the mobile in a given region. We show how to guide the mobile's movement to gather a sufficient number of distance samples for node localization. We use simulations and measurements from an indoor deployment using the Cricket location system to investigate the performance of MAL, finding in real-world experiments that MAL's median pairwise distance error is less than 1.5% of the true node distance.

This paper describes a distributed, linear-time algorithm for localizing sensor network nodes in the presence of range measurement noise and demonstrates the algorithm on a physical network. We introduce the probabilistic notion of robust quadrilaterals as a way to avoid flip ambiguities that otherwise corrupt localization computations. We formulate the localization problem as a two-dimensional graph realization problem: given a planar graph with approximately known edge lengths, recover the Euclidean position of each vertex up to a global rotation and translation. This formulation is applicable to the localization of sensor networks in which each node can estimate the distance to each of its neighbors, but no absolute position reference such as GPS or fixed anchor nodes is available.

This paper describes a method for bringing two videos (recorded at different times) into spatiotemporal alignment, then comparing and combining corresponding pixels for applications such as background subtraction, compositing, and increasing dynamic range. We align a pair of videos by searching for frames that best match according to a robust image registration process. This process uses locally weighted regression to interpolate and extrapolate high-likelihood image correspondences, allowing new correspondences to be discovered and refined. Image regions that cannot be matched are detected and ignored, providing robustness to changes in scene content and lighting, which allows a variety of new applications.

This paper describes Atlas, a hybrid metrical/topological approach to SLAM that achieves efficient mapping of large-scale environments. The representation is a graph of coordinate frames, with each vertex in the graph representing a local frame, and each edge representing the transformation between adjacent frames. In each frame, we build a map that captures the local environment and the current robot pose along with the uncertainties of each. Each map's uncertainties are modeled with respect to its own frame. Probabilities of entities with respect to arbitrary frames are generated by following a path formed by the edges between adjacent frames, computed via Dijkstra's shortest path algorithm. Loop closing is achieved via an efficient map matching algorithm. We demonstrate the technique running in real-time in a large indoor structured environment (2.2 km path length) with multiple nested loops using laser or ultrasonic ranging sensors.

Physical location is an important attribute of a sensor’s data stream in a large number of sensor network applications. In addition, geographic information, for instance in the form of node coordinates in some common coordinate system, is a useful primitive in routing protocols such as geographic routing, information dissemination protocols such as directed diffusion using location attributes, and sensor query processing systems. We present a method to facilitate large-scale deployment of location-aware sensor networks. We show that large networks of location-aware sensors can be made cooperatively self-configuring, that is, that each sensor can run an algorithm locally, interacting only with neighboring nodes, such that after a number of iterations all sensors will have reached a consensus about their coordinates in some coordinate system. By doing this in an automated manner, large-scale sensor networks can eliminate the cumbersome and unscalable process of manually configuring sensor nodes with their location. In non-urban outdoor settings, nodes may obtain location information using an existing infrastructure such as GPS. However, GPS receivers may be too expensive, too large, too power-intensive for the desired application, or simply unavailable. One solution to this problem is an alternative location infrastructure such as Cricket that works in places that GPS does not. Another solution to these problems is to equip sensors with hardware capable of estimating distances to nearby nodes, and to have the sensors themselves selfconfigure into a consistent coordinate system.

The paper describes a system for structure-from-motion using vanishing points and three-dimensional lines extracted from omnidirectional video sequences. Two novel aspects of this work are its deferred initialization of features using noisy observations from multiple, uncertain vantage points, and its use of dynamic programming for efficient 3D line tracking. We show preliminary results from the system for both indoor and outdoor sequences.

We describe a linear-time algorithm that recovers absolute camera positions for networks of thousands of terrestrial images spanning hundreds of meters in outdoor urban scenes, under uncontrolled lighting. The algorithm requires no human input or interaction. For real data, it recovers camera pose globally consistent on average to roughly five centimeters, or about four pixels of epipolar alignment. The paper's principal contributions include an extension of Markov chain Monte Carlo estimation techniques to the case of unknown numbers of feature points, unknown occlusion and deocclusion, large scale (thousands of images, and hundreds of thousands of point features), and large dimensional extent (tens of meters of inter-camera baseline, and hundreds of meters of baseline overall). Also, a principled method is given to manage uncertainty on the sphere; a new use of the Hough transform is proposed; and a method for aggregating local baseline constraints into a globally consistent pose set is described.

We describe a dataset of several thousand calibrated, geo-referenced, high dynamic range color images, acquired under uncontrolled, variable illumination in an outdoor region spanning hundreds of meters. All image, feature, calibration, and geo-referencing data are available at http://city.lcs.mit.edu/data. Calibrated imagery is of fundamental interest in a wide variety of applications. We have made this data available in the belief that researchers in computer graphics, computer vision, photogrammetry and digital cartography will find it useful in several ways: as a test set for their own algorithms; as a calibrated image set for applications such as image-based rendering, metric 3D reconstruction, and appearance recovery; and as controlled imagery for integration into existing GIS systems and applications. The Web-based interface to the data provides interactive viewing of high-dynamic-range images and mosaics; extracted edge and point features; intrinsic and extrinsic calibration, along with maps of the ground context in which the images were acquired; the spatial adjacency relationships among images; the epipolar geometry relating adjacent images; compass and absolute scale overlays; and quantitative consistency measures for the calibration data.

The ability to determine the orientation of a device is of fundamental importance in context aware and location-dependent mobile computing. By analogy to a traditional compass, knowledge of orientation through the Cricket compass attached to a mobile device enhances various applications, including efficient way-finding and navigation, directional service discovery, and “augmented-reality” displays. Our compass infrastructure enhances the spatial inference capability of the Cric ketindoor location system [20], and enables new pervasive computing applications.

In this paper we describe a formulation of extrinsic camera calibration that decouples rotation from translation by exploiting properties inherent in urban scenes. We then present an algorithm which uses edge features to robustly and accurately estimate relative rotations among multiple cameras given intrinsic calibration and approximate initial pose. The algorithm is linear both in the number of images and the number of features. We estimate the number and directions of vanishing points (VPs) with respect to each camera using a hybrid approach that combines the robustness of the Hough transform with the accuracy of expectation maximization. Matching and labeling methods identify unique VPs and correspond them across all cameras. Finally, a technique akin to bundle adjustment produces globally optimal estimates of relative camera rotations by bringing all VPs into optimal alignment. Uncertainty is modeled and used at every stage to improve accuracy. We assess the algorithm's performance on both synthetic and real data, and compare our results to those of semi-automated photogrammetric methods for a large set of real hemispherical images, using several consistency and error metrics.

We are developing a system to extract geodetic, textured CAD models from thousands of initially uncontrolled, close-range ground and aerial images of urban scenes. Here we describe one component of the system, which operates after the imagery has been controlled or geo-referenced. This fully automatic component detects significant vertical facades in the scene, then extrudes them to meet an inferred, triangulated terrain and procedurally generated roof polygons. The algorithm then estimates for each surface a computer graphics texture, or diffuse reflectance map, from the many available observations of that surface. We present the results of the algorithm on a complex dataset: nearly 4,000 high-resolution digital images of a small (200 meter square) office park, acquired from close range under highly varying lighting conditions, amidst significant occlusion due both to multiple inter-occluding structures, and dense foliage. While the results are of less fidelity than that would be achievable by an interactive system, our algorithm is the first to be demonstrated on such a large, real-world dataset.

Ray tracers, which sample radiance, are usually regarded as offline rendering algorithms that are too slow for interactive use. In this article we present a system that exploits object-space, ray-space, image-space, and temporal coherence to accelerate ray tracing. Our system uses per-surface interpolants to approximate radiance both interactive and batch ray tracers. Our approach explicity decouples the two primary operations of a ray tracer—shading and visibility determination—and accelerates each of them independently. Shading is accelerated by quadrilinearily interpolating lazily acquired radiance samples. Interpolation error does not exceed a user-specified bound, allowing the user to control performance/quality tradeoffs. Error is bounded by adaptive sampling at discontinuities and radiance nonlinearities. Visibility determination at pixels is accelerated by reprojecting interpolants as the user's viewpoint changes. A fast scan-line alogoithm then achieves high performance without sacrificing image quality. For a smoothly varying viewpoint, the combination of lazy interpolants and projection substantially accelerates the ray tracer. Additionally, an efficient cache management algorithm keeps the memory footprint of the system small with negilgible overhead.

We describe the generation of a large pose-mosaic dataset: a collection of several thousand digital images, grouped by spatial position into spherical mosaics, each annotated with estimates of the acquiring camera's 6 DOF pose (3 DOF position and 3 DOF orientation) in an absolute coordinate system. The pose-mosaic dataset was generated by acquiring images, grouped by spatial position into nodes (essentially, spherical mosaics). A prototype mechanical pan-tilt head was manually deployed to acquire the data. Manual surveying provided initial position estimates for each node. A back-projecting scheme provided initial rotational estimates. Relative rotations within each node, along with internal camera parameters, were refined automatically by an optimization-correlation scheme. Relative translations and rotations among nodes were refined according to point correspondences, generated automatically and by a human operator. The resulting pose-imagery is self-consistent under a variety of evaluation metrics. Pose-mosaics are useful "first-class" data objects, for example in automatic reconstruction of textured 3D CAD models which represent urban exteriors.

High fidelity textured geometric models are a fundamental starting point for computer graphics, simulation, visualization, design, and analysis. Existing tools for acquiring 3D models of large scale (e.g., urban) geometry, from imagery, require significant manual input and suffer other algorithmic scaling limitations. We are pursuing a research and engineering effort to develop a novel sensor and associated geometric algorithms, to achieve fully automated reconstruction from close range color images of textured geometric models representing built urban structures. The sensor is a geo-located camera, which annotates each acquired digital image with metadata recording the date and time of image acquisition, and estimating the position and orientation of the acquiring camera in a global (geodetic) coordinate system. This metadata enables the formulation of reconstruction algorithms which scale well both with the number and spatial density of input images, and the complexity of the reconstructed model. We describe our initial dataset of about four thousand geo-located images acquired through a prototype sensor, manual surveying, and semi automated refinement of navigation information. We demonstrate, for a small of office park on the MIT campus, the operation of fully automated algorithms for generating hemispherical image mosaics, for reconstructing vertical building facades, and for estimating high resolution texture information for each facade. Finally, we describe the status of our efforts, and discuss several significant research and engineering challenges facing the project.

Efficiently identifying polygons that are visible from a dynamic synthetic viewpoint is an important problem in computer graphics. Typically, visibility determination is performed using the z-buffer algorithm. As this algorithm must examine every triangle in the input scene, z-buffering can consume a significant fraction of graphics processing, especially on architectures that have a low performance or software z-buffer. One way to avoid needlessly processing invisible portions of the scene is to use an occlusion culling algorithm to discard invisible polygons early in the graphics pipeline. In this paper, we exploit the presence of large occluders in urban and architectural models to design a real-time occlusion culling algorithm. Our algorithm has the following features: it is conservative, i.e., it overestimates the set of visible polygons; it exploits spatial coherence by using a hierarchical data structure; and it exploits temporal coherence by reusing visibility information computed for previous viewpoints. The new algorithm significantly accelerates rendering of several complex test models.

Efficiently identifying polygons that are visible from a chang- ing synthetic viewpoint is an important problem in computer graphics.Even with hardware support, simple algorithms like depth-buffering cannot achieve interactive frame rates when applied to geometric models with many polygons.However, a visibility algorithm that exploits the occlusion properties of the scene to identify a superset of visible polygons, without touching most invisible polygons, could achieve fast frame rates while viewing such models.In this paper, we present a new approach to the visibility problem.The novel aspects of our algorithm are that it is temporally coherent and conservative for all viewpoints the algorithm overestimates the set of visible polygons.As the synthetic viewpoint moves, the algorithm reuses visibility information computed for previous viewpoints.It does so by computing visual events at which visibility changes occur, and efficiently identifying and discarding these events as the viewpoint changes.In essence, the algorithm implicitly constructs and maintains a linearized portion of an aspect graph, a data structure for representing visual events.

We describe a system that computes radiosity solutions for polygonal environments much larger than can be stored in main memory. The solution is stored in and retrieved from a database as the computation proceeds. Our system is based on two ideas: the use of visibility oracles to find source and blocker surfaces potentially visible to a receiving surface; and the use of hierarchical techniques to represent interactions between large surfaces efficiently, and to represent the computed radiosity solution compactly. Visibility information allows the environment to be partitioned into subsets, each containing all the information necessary to transfer light to a cluster of receiving polygons. Since the largest subset needed for any particular cluster is much smaller than the total size of the environment, these subset computations can be performed in much less memory than can classical or hierarchical radiosity. The computation is then ordered for further efficiency. Careful ordering of energy transfers minimizes the number of database reads and writes. We report results from large solutions of unfurnished and furnished buildings, and show that our implementation's observed running time scales nearly linearly with both local and global model complexity.

No abstract available.

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by

We describe techniques for managing large amounts of data during an interactive walkthrough of an architectural model.These techniques are based on a spatial subdivision, visibility analysis, and a display database containing objects described at multiple levels of detail.In each frame of the walkthrough, we compute a set of objects to render, i.e. those potentially visible from the observer's viewpoint, and a set of objects to swap into memory, i.e. those that might become visible in the near future.We choose an appropriate level of detail at which to store and to render each object, possibly using very simple representations for objects that appear small to the observer, thereby saving space and time.Using these techniques, we cull away large portions of the model that are irrelevant from the observer's viewpoint, and thereby achieve interactive frame rates.

We define the antiumbra and the antipenumbra of a convex area light source shining through a sequence of convex area] holes in three dimensions.The antiumbra is the volume from which all points on the light source can be seen.The antipenumbra is the volume from which some, but not all, of the light source can be seen.We show that the antipenumbra is, in general, a disconnected set bounded by portions of quadric surfaces, and describe an implemented 0(n2) time algorithm that computes this boundary, where n is the total number of edges comprising the light source and holes.The antipenumbra computation is motivated by a visibility scheme in which we wish to determine the volume visible to an observer looking through a sequence of transparent convex holes, or portals, connecting adjacent cells in a spatial subdivision.Knowledge of the antipenumbra should also prove useful for rendering shadowed objects.Finally, we have extended the algorithm to compute the planar and quadratic surfaces along which the rate of areal variation in the visible portion of the light source changes discontinuously due to occlusion.These surfaces are relevant in polygon meshing schemes for global illumination and shadow computations.

The number of polygons comprising interesting architectural models is many more than can be rendered at interactive frame rates. However, due to occlusion by opaque surfaces (e.g., walls), only a small fraction of a typical model is visible from most viewpoints.We describe a method of visibility preprocessing that is efficient and effective for axis-aligned or axial architectural models. A model is subdivided into rectangular cells whose boundaries coincide with major opaque surfaces. Non-opaque portals are identified on cell boundaries, and used to form an adjacency graph connecting the cells of the subdivision. Next, the cell-to-cell visibility is computed for each cell of the subdivision, by linking pairs of cells between which unobstructed sightlines exist.During an interactive walkthrough phase, an observer with a known position and view cone moves through the model. At each frame, the cell containing the observer is identified, and the contents of potentially visible cells are retrieved from storage. The set of potentially visible cells is further reduced by culling it against the observer's view cone, producing the eye-to-cell visibility. The contents of the remaining visible cells are then sent to a graphics pipeline for hidden-surface removal and rendering.Tests on moderately complex 2-D and 3-D axial models reveal substantially reduced rendering loads.