Abstract

Displays have seen much improvements over the years, withenhancements in spatial resolution and vertical refresh, etc.,to provide better and smoother visual experiences. Color in-tensity resolution, however, has not changed much over thepast few decades. Most displays are still limited to 8-bitsper channel. Simultaneously, much work has gone into cap-turing high dynamic range images. Mapping these directlyto current displays loses information that may be critical tomany applications. We present a way to enhance intensityresolution of a given display by mixing intensities over spa-tial or temporal domains. Our system sacrifices high verticalrefresh and spatial resolution in order to gain intensity res-olution. We present three ways to mix intensities: spatially,temporally and spatio-temporally. The systems produce in-between-intensities not present on the base display, whichare clearly distinguishable by the naked eye. We evaluateour systems using both a camera and human subjects, eval-uating whether they scale the intensity resolution and alsoensuring that the newly generated intensities follow the dis-play model

Abstract

The Graphics Processing Units (GPUs) provide highcomputation power at a low cost and is an important computeaccelerator with a massively multithreaded architecture. Inthis paper, we present fast implementations of common graphoperations like breadth-first search, st-connectivity, single-sourceshortest path, all-pairs shortest path, minimum spanning tree,and maximum flow for undirected graphs on the GPU using theCUDA programming model. Our implementations exhibit highperformance, especially on large graphs. We use two data-parallelprogramming methodologies for these algorithms. One is aniterative, mask-based approach that processes valid data elementslike vertices and edges using independent threads for each.The other is a divide-and-conquer approach that reduces theproblem into smaller problems that are handled later using thesame approach. Parallel algorithms for such problems have beenreported in the literature before, especially on supercomputers.The massively multithreaded model of the GPU makes it possibleto adopt the data-parallel approach even to irregular algorithmslike graph algorithms, usingO(V)orO(E)simultaneous threads.The algorithms and the underlying techniques presented in thispaper are likely to be applicable to many irregular algorithms.We show the impact of our implementations on random, scale-free, and real-life graphs of up to millions of vertices on high-end and low-end GPUs. The availability and spread of GPUs todesktops and laptops make them ideal candidates to accelerategraph operations over the CPU-only implementations. Practicalimplementations of basic operations go a long way in realizingtheir potential.

Abstract

Graphics Processor Units are used for many general purpose pro-cessing due to high compute power available on them. Regular,data-parallel algorithms map well to the SIMD architecture of cur-rent GPU. Irregular algorithms on discrete structures like graphs areharder to map to them. Efficient data-mapping primitives can playcrucial role in mapping such algorithms onto the GPU. In this paper,we present a minimum spanning tree algorithm on Nvidia GPUsunder CUDA, as a recursive formulation of Bor ̊uvka’s approach forundirected graphs. We implement it using scalable primitives suchas scan, segmented scan and split. The irregular steps of superver-tex formation and recursive graph construction are mapped to prim-itives like split to categories involving vertex ids and edge weights.We obtain30to50times speedup over the CPU implementationon most graphs and3to10times speedup over our previous GPUimplementation. We construct the minimum spanning tree on a5million node and30million edge graph in under1second on onequarter of the Tesla S1070GPU.

Abstract

In this paper, we present the design and construction of a simple andinexpensive 3D display made up of polygonal elements. We use aper-pixel transformation of image and depth to produce accuratepicture and depth map on an arbitrary planar display facet fromany viewpoint. Though the facets are rendered independently, theimage and depth for rays from the eye-point through the facet pixelsis produced by our method. Thus, there are no artifacts on a facet orat facet boundaries. Our method can be extended to any polygonaldisplay surface as demonstrated using synthetic setups. We alsoshow a real display constructed using off-the-shelf LCD panels andcomputers. The display uses a simple calibration procedure and canbe setup in minutes. Frame-sequential and anaglyphic stereo modescan be supported for any eye-orientation and at high resolutions.

Abstract

Cluster-based tiled display walls can provide cost-effective and scalable displays with high resolution and a large displayarea. The software to drive them needs to scale too if arbitrarily large displays are to be built. Chromium is a popular software API usedto construct such displays. Chromium transparently renders any OpenGL application to a tiled display by partitioning and sendingindividual OpenGL primitives to each client per frame. Visualization applications often deal with massive geometric data with millions ofprimitives. Transmitting them every frame results in huge network requirements that adversely affect the scalability of the system. Inthis paper, we present Garuda, a client-server-based display wall framework that uses off-the-shelf hardware and a standard network.Garuda is scalable to large tile configurations and massive environments. It can transparently render any application built using theOpen Scene Graph (OSG) API to a tiled display without any modification by the user. The Garuda server uses an object-based scenestructure represented using a scene graph. The server determines the objects visible to each display tile using a novel adaptivealgorithm that culls the scene graph to a hierarchy of frustums. Required parts of the scene graph are transmitted to the clients, whichcache them to exploit the interframe redundancy. A multicast-based protocol is used to transmit the geometry to exploit the spatialredundancy present in tiled display systems. A geometry push philosophy from the server helps keep the clients in sync with oneanother. Neither the server nor a client needs to render the entire scene, making the system suitable for interactive rendering ofmassive models. Transparent rendering is achieved by intercepting the cull, draw, and swap functions of OSG and replacing them withour own. We demonstrate the performance and scalability of the Garuda system for different configurations of display wall. We alsoshow that the server and network loads grow sublinearly with the increase in the number of tiles, which makes our scheme suitable toconstruct very large displays

Abstract

Large graphs involving millions of vertices are common in many prac-tical applications and are challenging to process. Practical-time implementationsusing high-end computers are reported but are accessible only to a few. GraphicsProcessing Units (GPUs) of today have high computation power and low price.They have a restrictive programming model and are tricky to use. The G80 lineof Nvidia GPUs can be treated as a SIMD processor array using the CUDA pro-gramming model. We present a few fundamental algorithms – including breadthfirst search, single source shortest path, and all-pairs shortest path – using CUDAon large graphs. We can compute the single source shortest path on a 10 millionvertex graph in1.5seconds using the Nvidia 8800GTX GPU costing $600. Insome cases optimal sequential algorithm is not the fastest on the GPU architec-ture. GPUs have great potential as high-performance co-processors.

Abstract

Visibility culling of a scene is a crucial stage for interactive graphics applications, particularly for scenes with thousands of objects. The culling time must be small for it to be effective. A hierarchical representation of the scene is used for efficient culling tests. However, when there are multiple view frustums (as in a tiled display wall), visibility culling time becomes substantial and cannot be hidden by pipelining it with other stages of rendering. In this paper, we address the problem of culling an object to a hierarchically organized set of frustums, such as those found in tiled displays and shadow volume computation. We present an adaptive algorithm to unfold the twin hierarchies at every stage in the culling procedure. Our algorithm computes from-point visibility and is conservative. The precomputation required is minimal, allowing our approach to be applied for dynamic scenes as well. We show performance of our technique over different variants of culling a scene to multiple frustums. We also show results for dynamic scenes.

Abstract

We address a few problems in navigation of automated vehicles using images captured by a mounted camera. Specifically, we look at the recognition of sign boards, rectification of planar objects imaged by the camera, and estimation of the position of a vehicle with respect to a fixed sign board. Our solutions are based on contour correspondence between a reference view and the current view. A mapping between corresponding points of a planar object in two different views is a
matrix called the homography. A novel two-step linear algorithm for homography calculation from contour correspondence is developed first. Our algorithm requires the identification of an image contour as the projections of a known planar world contour and the selection of a known starting point. The homography between the reference view and the target view is applied to several reallife navigation applications, results of which are presented in this paper

Abstract

This paper presents several results on images of various configurations of conics. We extract information about the plane from single and multiple views of known and unknown conics, based on planar homography and conic correspondences. We show that a single conic section cannot provide sufficient information. Metric rectification of the plane can be performed from a single view if two conics can be identified to be images of circles without knowing their centers or radii. The homography between two views of a planar scene can be computed if two arbitrary conics are identified in them without knowing anything specific about them. The scene can be reconstructed from a single view if images of a pair of circles can be identified in two planes. Our results are simpler and require less information from the images than previously known results. The results presented here involve univariate polynomial equations of degree 4 or 8 and always have solutions. Applications to metric rectification, homography calculation, 3D reconstruction, and projective OCR are presented to demonstrate the usefulness of our scheme

Abstract

Recognition of discrete planar contours under similarity transformations has received a lot of attention but little work has been reported on recognizing them under more general transformations. Planar object boundaries undergo projective or affine transformations across multiple views. We present two methods to recognize discrete curves in this paper. The first method computes a piecewise parametric approximation of the discrete curve that is projectively invariant. A polygon approximation scheme and a piecewise conic approximation scheme are presented here. The second method computes an invariant sequence directly from the sequence of discrete points on the curve in a Fourier transform space. The sequence is shown to be identical up to a scale factor in all affine related views of the curve. We present the theory and demonstrate its applications to several problems including numeral recognition, aircraft recognition, and homography computation. q 2004 Elsevier B.V. All rights reserved