Search

Efficiently identifying polygons that are visible from a changing 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 rates while viewing such models.

We propose a simple modification to the classical polygon rasterization pipeline that enables exact, efficient raycasting of bounded implicit surfaces without the use of a global spatial data structure bounding hierarchy. Our algorithm requires two descr

This paper describes novel algorithms that use absolute camera pose information to identify correspondence among point features in hundreds or thousands of images. Our incidence counting algorithm is a geometric approach to matching: it makes features by extruding them into an absolute 3-D coordinate system, then searching 3-D space for regions into which many features project.

Extracting 3-dimensional structure from real-world imagery and rendering it from unrestricted viewpoints is an important problem in computer vision, and increasingly, computer graphics. Despite many years of research, a system that automatically recovers

Many sensor network applications require that each node's sensor stream be annotated with its physical location in some common coordinate system. Manual measurement and configuration methods for obtaining location don't scale and are error-prone, and equipping sensors with GPS is often expensive and does not work in indoor and urban deployments. Sensor networks can therefore benefit from a self-configuring method where nodes cooperate with each other, estimate local distances to their neighbors, and converge to a consistent coordinate assignment. This paper describes a fully decentralized algorithm called AFL (Anchor-Free Localization) where nodes start from a random initial coordinate assignment and converge to a consistent solution using only local node interactions. The key idea in AFL is fold-freedom, where nodes first configure into a topology that resembles a scaled and unfolded version of the true configuration, and then run a force-based relaxation procedure. We show using extensive simulations under a variety of network sizes, node densities, and distance estimation errors that our algorithm is superior to previously proposed methods that incrementally compute the coordinate of nodes in the network, in terms of its ability to computer correct coordinates under a wider variety of conditions and its robuestness to measurement errors.

Efficient visible surface determination algorithms have long been a fundamental goal of computer graphics. We discuss the well-known ray casting problem: given a geometric scene description, a synthetic camera, and a viewport which discretizes the camer

Accurate camera calibration is crucial to the reconstruction of three-dimensional geometry and the recovery of photometric scene properties. Calibration involves the determination of intrinsic parameters (e.g. focal length, principal point, and radial lens distortion) and extrinsic parameters (orientation and position). In urban scenes and other environments containing sufficient geometric structure, it is possible to decouple extrinsic calibration into rotational and translational components that can be treated separately, simplifying the registration problem. Here we present such a decoupled formulation and describe methods for automatically recovering the positions of a large set of cameras given intrinsic calibration, relative rotations, and approximate positions. Our algorithm first estimates the directions of translation (up to an unknown scale factor) between adjacent camera pairs using point features but without requiring explicit correspondence between them. This technique combines the robustness and simplicity of a Hough transform with the accuracy of Monte Carlo expectation maximization. We then find a set of distances between the pairs that produces globally-consistent camera positions. Novel uncertainty formulations and match plausibility criteria improve reliability and accuracy. We assess our system's performance using both synthetic data and a large set of real panoramic imagery. The system produces camera positions accurate to within 5 centimeters in image networks extending over hundreds of meters.

Classical ray-tracing algorithms compute radiance returning to the eye along one or more sample rays through each pixel of an image. The output of a ray-tracing algorithm, although potentially photorealistic, is a two-dimensional quality an image array of radiance values and is not directly useful from any viewpoint other than the one for which it was computed.

Efficiently identifying polygons that are visible from a changing synthetic viewpoint is an important problem in computer graphics. In many complex geometric models, most parts of the model are invisible from the instantaneous viewpoint. Despite this, hidden-surface algorithms like the z-buffer or BSP tree often expend significant computation processing invisible portions of the model.

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 surverying 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.

We describe the design considerations underlying a system for scalable, automated capture of precisely controlled imagery in urban scenes. The system operates for architectural scenes in which, from every camera position, some two vanishing points are visible. It has been used to capture thousands of controlled images in outdoor environments spanning hundreds of meters. The proposed system architecture forms the foundation for a future, fully robotic outdoor mapping capability for urban areas, analogous to existing, satellite-based robotic mapping systems which acquire images and models of natural terrain. Four key ideas distinguish our approach from other methods. First, our sensor acquires georeferencing metadata with every image, enabling related images to be efficiently identified and registered. Second, the sensor acquires omni-directional images; we show strong experimental evidence that such images are fundamentally more powerful observations than conventional (narrow-FOV) images. Third, the system uses a probabilistic, projective error formulation to account for uncertainty. By treating measurement error in an appropriate depth-free framework, and by deferring decisions about camera calibration and scene structure until many noisy observations can be fused, the system achieves superior robustness and accuracy. Fourth, the system's computational requirements scale linearly in the input size, the area of the acquisition region, and the size of the output model. This is in contrast to most previous methods, which either assume constant-size inputs or exhibit quadratic running time (or worse) asymptotically. These attributes enable the system to operate in a regime of scale and physical extent which is unachievable by any other method, whether manual or automated. Consequently, it can acquire the most complex calibrated terrestrial image sets in existence, while operating faster thanany existing manual or algorithmic method.

Natural language provides a flexible, intuitive way for people to command robots, which is becoming increasingly important as robots transition to working alongside people in our homes and workplaces. To follow instructions in unknown environments, robots will be expected to reason about parts of the environments that were described in the instruction, but that the robot has no direct knowledge about. However, most existing approaches to natural language understanding require that the robot’s environment be known a priori. This paper proposes a probabilistic framework that enables robots to follow commands given in natural language, without any prior knowledge of the environment. The novelty lies in exploiting environment information implicit in the instruction, thereby treating language as a type of sensor that is used to formulate a prior distribution over the unknown parts of the environment. The algorithm then uses this learned distribution to infer a sequence of actions that are most consistent with the command, updating our belief as we gather Keywords Natural Language; Mobile Robot; Parse Tree; World Model; Behavior Inference

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., Andrea Bocelli Foundation, East Japan Railway Company, United States. Office of Naval Research (N00014-10-1-0936, N00014-11-1-0688, N00014-13-1-0588), National Science Foundation (U.S.) (IIS-1318392)