Abstract

Browsers of personal digital photographs all essentially fol-low the slide show paradigm, sequencing through the pho-tos in the order they are taken. A more engaging way tobrowse personal photographs, especially of a large space likea popular monument, should involve the geometric contextof the space. In this paper, we present ageometry directedphoto browserthat enables users to browse their personalpictures with the underlying geometry of the space to guidethe process. The browser uses a pre-computed package ofgeometric information about the monument for this task.The package is used to register a set of photographs takenby the user with the common geometric space of the monu-ment. This involves localizing the images to the monumentspace by computing the camera matrix corresponding to it.We use a state-of-the-art method for fast localization. Reg-istered photographs can be browsed using a visualizationmodule that shows them in the proper geometric contextwith respect to a point-based 3D model of the monument.We present the design of the geometry-directed browser anddemonstrate its utility for a few sequences of personal im-ages of well-known monuments. We believe personal photobrowsers can provide an enhanced sense of one’s own ex-perience with a monument using the underlying geometriccontext of the monument.

Abstract

Graphics processing units (GPUs) provide large computational power at a very low price, which position GPUs well as an ubiquitous accelerator. However, GPUs are space constrained, and hence applications developed for GPUs are space sensitive. Space-constrained computational devices such as GPUs can greatly benefit from representations that reduce space consumption drastically. One such representation is the succinct representation of trees. Succinct representation of trees generally allows for operations such as parent queries, least common ancestor queries, and so on. Mapping such a robust representation to the GPU for targeted applications can lead to substantial improvement in problem sizes that are processed at a given point of time. Space-saving methods such as succinct data structures remain largely unexplored on the GPU. In this work, a succinct representation of ordered trees on the GPU is explored, with application to discrete range searching (DRS). Based on the succinct representations found applicable, a space--saving solution for DRS is presented here. In our method, DRS is mapped to a least common ancestor query on a Cartesian tree. For space-efficient DRS queries, we store the succinct representation of the Cartesian tree of an array. Our method uses a maximum of 7.5 bits of additional space per element. Furthermore, the speed-up achieved by our method is in the range of 20--25 for preprocessing and 25--35 for batch querying over a sequential implementation. Compared to an 8-threaded implementation, our preprocessing and querying methods obtain a speed-up of 6--8. We also study the applications of the DRS on the GPU. Efficient primitives expand the range of applications performed on the GPU. DRS is one such primitive with direct applications to string processing, document and text retrieval systems, and least common ancestor queries. We suggest that graph algorithms that use the least common ancestor, can be enabled on the GPU based on DRS primitive. We also show some applications of DRS in tree queries and string querying.

Abstract

Advances in cameras and web technology have madeit easy to capture and share large amounts of video data over toa large number of people. A large number of cameras overseepublic and semi-public spaces today. These raise concerns on theunintentional and unwarranted invasion of the privacy of individ-uals caught in the videos. To address these concerns, automatedmethods tode-identifyindividuals in these videos are necessary.De-identification does not aim at destroying all informationinvolving the individuals. Its ideal goals are to obscure the identityof the actor without obscuring the action. This paper outlinesthe scenarios in which de-identification is required and the issuesbrought out by those. We also present an approach to de-identifyindividuals from videos. Our approach involves tracking andsegmenting individuals in a conservative voxel space involvingx, y,and time. A de-identification transformation is applied perframe using these voxels to obscure the identity. Face, silhouette,gait, and other characteristics need to be obscured, ideally. Weshow results of our scheme on a number of videos and forseveral variations of the transformations. We present the resultsof applying algorithmic identification on the transformed videos.We also present the results of a user-study to evaluate how wellhumans can identify individuals from the transformed videos

Abstract

Raytracing dynamic scenes at interactive rates have received a lot of attention recently. We present a few strategies forhigh performance raytracing on a commodity GPU. The construction of grids needs sorting, which is fast on today’s GPUs. The grid isthus the acceleration structure of choice for dynamic scenes as per-frame rebuilding is required. We advocate the use of appropriatedata structures for each stage of raytracing, resulting in multiple structure building per frame. A perspective grid built for the cameraachieves perfect coherence for primary rays. A perspective grid built with respect to each light source provides the best performancefor shadow rays. Spherical grids handle lights positioned inside the model space and handle spotlights. Uniform grids are best forreflection and refraction rays with little coherence. We propose an Enforced Coherence method to bring coherence to them byrearranging the ray to voxel mapping using sorting. This gives the best performance on GPUs with only user-managed caches. Wealso propose a simple, Independent Voxel Walk method, which performs best by taking advantage of the L1 and L2 caches on recentGPUs. We achieve over 10 fps of total rendering on the Conference model with one light source and one reflection bounce, whilerebuilding the data structure for each stage. Ideas presented here are likely to give high performance on the future GPUs as well asother manycore architectures

Abstract

We propose an object centric representation for easy and in-tuitive navigation and manipulation of videos. Object centricrepresentation allows a user to directly access and process ob-jects as basic video components. We demonstrate a trajectorybased interface and example operations, which allow users toretime, reorder, remove or clone video objects in a ‘click anddrag’ fashion. This interface is created by extracting objectmotion information from the video. We use object detectionand tracking to obtain spatiotemporal video object tube. Thecorresponding object motion trajectories are represented in a3D(x,y,t)grid. Users can navigate and manipulate videoobjects by scrubbing or manipulating corresponding trajecto-ries. We show some example applications of proposed inter-face like object synchronization, saliency magnification, vi-sual effects and composite video creation.

Abstract

Video data is increasing rapidly along with the capacity of storage devices owned by a lay user. Users have mod­erate to large personal collections of videos and would like to keep them in an organized manner based on its content. Video organizing tools for personal users are way behind even the primitive image organizing tools. We present a mechanism in this paper to help ordinary users organize their personal collection of videos based on categories they choose. We cluster the PHOG features extracted from se­lected key frames to form a representation for each user­selected category during the learning phase. During the organization phase, labels from a K -NN classifier on these cluster centres for each key frame are aggregated to give a label to the video while categorizing. Video processing is computationally intensive. To peiform the computationally intensive steps involved, we exploit the CPU as well as the GPU that is common even on personal systems. Effective use of the parallel hardware on the system is the only way to make the tool scale reasonably to large collections that will be available soon. Our tool is able to organize a set of 100 sport videos of total duration of 1375 minutes in about 9.5 minutes. The process of learning the categories from 12 annotated videos of duration 165 minutes took 75 seconds on a GTX 580 card. These were on a standard desktop with an off-the-shelfGPU. The labeling accuracy is about 96% on all video

Abstract

s the complexity of 3D models used in computergraphics applications grows, there arises a need to visualize theoverall distribution of detail on them. Detail is a function ofthe amount of information present on a surface. In this paper,we present a method to quantify detail using a combination oflocal measures of curvature and density. We show that detailcan be used for applications like ordering for mesh decimation,visualizing abnormalities in a mesh and so on

Abstract

Visual surveillance is increasingly prevalent todaybut the privacy issues of individuals involved in surveillancevideos have not been dealt with adequately so far. In mostcases, if not all, the chief purpose of placing a camera can beserved without knowing the identity of the individuals involvedunless the activity is of some predetermined kind. One needsto transform these videos to protect identity of individualsinvolved possibly at the source camera itself. In this paperwe present the De-Identification Camera, which is a scalable,low cost and real-time solution to the privacy protection issues.Our main contribution lies in proposing a privacy protectionarchitecture which transforms the video at the camera level itself,We also present and implement a de-identification pipeline whichis suitable for real-time implementation. We implemented thesystem on a Texas Instrument OMAP4 based embedded platformand was able to de-identify videos in real time, transformingthe video on the camera itself ensures protection from variousattacks. We also address issues like data utility of surveillancevideos by making this solution customizable. We propose thatsuch systems can replace the traditional surveillance cameras inthe future by providing all the surveillance and privacy protectionsolutions on hardware, probably with few performance upgrades.

Abstract

Many image filtering operations provide ample par-allelism, but progressive non-linear processing of im-ages is among the hardest to parallelize due to long,sequential, and non-linear data dependency. A typicalexample of such an operation is error diffusion dither-ing, exemplified by the Floyd-Steinberg algorithm. Inthis paper, we present its parallelization on multicoreCPUs using a block-based approach and on the GPUusing a pixel based approach. We also present a hybridapproach in which the CPU and the GPU operatein parallel during the computation. High PerformanceComputing has traditionally been associated with highend CPUs and GPUs. Our focus is on everyday com-puters such as laptops and desktops, where significantcompute power is available on the GPU as on theCPU. Our implementation can dither an8K8Kimage on an off-the-shelf laptop with an Nvidia 8600MGPU in about 400 milliseconds when the sequentialimplementation on its CPU took about 4 seconds.

Abstract

K-Means is a popular clustering algorithm with wideapplications in Computer Vision, Data mining, Data Visu-alization, etc. Clustering is an important step for indexingand searching of documents, images, video, etc. Clusteringlarge numbers of high-dimensional vectors is very compu-tation intensive. In this paper, we present the design andimplementation of theK-Means clustering algorithm on themodern GPU. All steps are performed entirely on the GPUefficiently in our approach. We also present a load balancedmulti-node, multi-GPU implementation which can handleup to 6 million, 128-dimensional vectors. We use efficientmemory layout for all steps to get high performance. TheGPU accelerators are now present on high-end workstationsand low-end laptops. Scalability in the number and dimen-sionality of the vectors, the number of clusters, as well as inthe number of cores available for processing are importantfor usability to different users. Our implementation scaleslinearly or near-linearly with different problem parameters.We achieve up to 2 times increase in speed compared to thebest GPU implementation forK-Means on a single GPU.We obtain a speed up of over 170 on a single Nvidia FermiGPU compared to a standard sequential implementation.We are able to execute one iteration ofK-Means in 136seconds on off-the-shelf GPUs to cluster 6 million vectorsof 128 dimensions into 4K clusters and in 2.5 seconds tocluster 125K vectors of 128 dimensions into 2K clusters.