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.

Abstract

General purpose programming on the graphics processing units(GPGPU) has received a lot of attention in the parallel computing community as it promises to offer a large computational power at a very low price. GPGPU is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as convex hull, list ranking etc. In this paper, we present a GPU-optimized implementation for finding the convex hull of a two dimensional point set. Our implementation tries to minimize the impact of irregular data access patterns. Our implementation can find the convex hull of 10 million random points in less than 0.2 seconds and achieves a speedup of up to 14 over the standard sequential CPU implementation. We also discuss some of the practical issues relating to the implementation of convex hull algorithms on massively multi-threaded architectures like that of the GPU.

Abstract

ndexing image data for content-based image search is an important area in Computer Vision. The state of theart uses the 128-dimensional SIFT as low level descriptors. Indexing even a moderate collection involves severalmillions of such vectors. The search performance depends on the quality of indexing and there is often a need tointeractively tune the process for better accuracy. In this paper, we propose a a visualization-based tool to tunethe indexing process for images and videos. We use a feature selection approach to improve the clustering of SIFTvectors. Users can visualize the quality of clusters and interactively control the importance of individual or groupsof feature dimensions easily. The results of the process can be visualized quickly and the process can be repeated.The user can use a filter or a wrapper model in our tool. We use input sampling, GPU-based processing, and visualtools to analyze correlations to provide interactivity. We present results of tuning the indexing for a few standarddatasets. A few tuning iterations result in an improvement of over 4% in the final classification performance, whichis significant.

Abstract

Graphics processing units provide a large compu-tational power at a very low price which position them as anubiquitous accelerator. General purpose programming on thegraphics processing units (GPGPU) is best suited for regulardata parallel algorithms. They are not directly amenable foralgorithms which have irregular data access patterns suchas list ranking, and finding the connected components of agraph, and the like. In this work, we present a GPU-optimizedimplementation for finding the connected components of agiven graph. Our implementation tries to minimize the impactof irregularity, both at the data level and functional level.Our implementation achieves a speed up of 9 to 12 timesover the best sequential CPU implementation. For instance, ourimplementation finds connected components of a graph of 10million nodes and 60 million edges in about 500 millisecondson a GPU, given a random edge list. We also draw interestingobservations on why PRAM algorithms, such as the Shiloach-Vishkin algorithm may not be a good fit for the GPU and howthey should be modified.

Abstract

Genetic algorithms are effective in solving many optimiza-tion tasks. However, the long execution time associated withit prevents its use in many domains. In this paper, we pro-pose a new approach for parallel implementation of geneticalgorithm on graphics processing units (GPUs) using CUDAprogramming model. We exploit the parallelism within achromosome in addition to the parallelism across multiplechromosomes. The use of one thread per chromosome byprevious efforts does not utilize the GPU resources effec-tively. Our approach uses multiple threads per chromosome,thereby exploiting the massively multithreaded GPU moreeffectively. This results in good utilization of GPU resourceseven at small population sizes while maintaining impressivespeed up for large population sizes. Our approach is mod-eled after the GAlib library and is adaptable to a varietyof problems. We obtain a speedup of over 1500 over theCPU on problems involving a million chromosomes. Prob-lems of such magnitude are not ordinarily attempted due tothe prohibitive computation times.

Abstract

Large-scale 3D reconstruction has received a lot of attentionrecently. Bundle adjustment is a key component of the reconstructionpipeline and often its slowest and most computational resource intensive.It hasn’t been parallelized effectively so far. In this paper, we present ahybrid implementation of sparse bundle adjustment on the GPU usingCUDA, with the CPU working in parallel. The algorithm is decomposedinto smaller steps, each of which is scheduled on the GPU or the CPU. Wedevelop efficient kernels for the steps and make use of existing libraries forseveral steps. Our implementation outperforms the CPU implementationsignificantly, achieving a speedup of 30-40 times over the standard CPUimplementation for datasets with upto 500 images on an Nvidia TeslaC2050 GPU.

Abstract

Graphics processing units provide a large compu-tational power at a very low price which position them as an ubiquitous accelerator. General purpose programming on the graphics processing units (GPGPU) is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as list ranking, and finding the connected components of a graph, and the like. In this work, we present a GPU-optimized implementation for finding the connected components of a given graph. Our implementation tries to minimize the impact of irregularity, both at the data level and functional level. Our implementation achieves a speed up of 9 to 12 times over the best sequential CPU implementation. For instance, our implementation finds connected components of a graph of 10 million nodes and 60 million edges in about 500 milliseconds on a GPU, given a random edge list. We also draw interesting observations on why PRAM algorithms, such as the Shiloach-Vishkin algorithm may not be a good fit for the GPU and how they should be modified.

Abstract

Graphics Processing Units (GPU) are application specific accelerators which provide high performance to cost ratio and are widely available and used, hence places them as a ubiquitous accelerator. A computing paradigm based on the same is the general purpose computing on the GPU (GPGPU) model. The GPU due to its graphics lineage is better suited for the data-parallel, data-regular algorithms. The hardware architecture of the GPU is not suitable for the data parallel but data irregular algorithms such as graph connected components and list ranking. In this paper, we present results that show how to use GPUs efficiently for graph algorithms which are known to have irregular data access patterns. We consider two fundamental graph problems: finding the connected components and finding a spanning tree. These two problems find applications in several graph theoretical problems. In this paper we arrive at efficient GPU implementations for the above two problems. The algorithms focus on minimising irregularity at both algorithmic and implementation level. Our implementation achieves a speedup of 11-16 times over a corresponding best sequential implementation.