Abstract

The MapReduce paradigm has become a popular way of expressing distributed data processing problems that need to deal with large amount of data. MapReduce is used by a number of organizations worldwide for diverse tasks such as application log processing, user behavior analysis, processing scientific data, web crawling and indexing etc. Many organizations utilize cloud computing services to acquire resources needed to process MapReduce jobs on demand. As a result of the popularity of using MapReduce in the cloud, cloud services such as the Amazon Elastic MapReduce have also become available. The Apache Hadoop framework is the leading open source implementation of the MapReduce model. It also provides a distributed file system (HDFS or the Hadoop Distributed File System). Hadoop is also the most popular MapReduce framework, and is being used by more than 75 organizations worldwide. It is designed to be scalable and robust, and runs on small single node clusters, to very large clusters containing several thousand compute and storage nodes. Despite the popularity and stability of Hadoop, it presents many opportunities for researching new resource management algorithms. Admission Control, Task Assignment and Scheduling, Data Local Execution, Speculative Execution and Replica placement are some of the key challenges involved in resource management in Hadoop. Resource management in Hadoop is complicated by the fact that the resources available are dynamic in nature because of frequent node failures. In this thesis, we approach two of the above problems: Admission Control and Task Assignment. Admission Control is the problem of deciding if a new job submission should be accepted for execution on a MapReduce cluster. An admission controller, or the module that handles admission control should make sure that jobs accepted into the cluster do not overload resources. Another important requirement is that the accepted jobs should try to maximize the utility of the service provider, which in this case is the Hadoop cluster owner. We propose an admission control algorithm that selects incoming jobs based on the principle of expected utility hypothesis. Based on this principle, the admission controller always chooses jobs that are expected to provide maximum utility after their successful completion. To predict whether or not the job will be successful, we observe the effects of past decisions made under similar situations and use this knowledge to predict outcome of incoming jobs. For this purpose we use a Nave Bayes classifier that labels incoming jobs as potentially successful or potentially unsuccessful. Out of the jobs that are labeled potentially successful, we chose the job that has the maximum value of utility function at the time of job submission. If none of the incoming jobs are labeled as potentially successful, we do not admit any job into the cluster. Utility functions are supplied by users and express the value earned by users after successful completion of jobs as a function of time taken to complete their requests. We consider a job submission to be successful if it does not overload resources on the cluster. Once the effects of the admission are observed, we update the classifier so that this experience is used while performing next decision. The next problem that we approach is that of Task Assignment. Each MapReduce job is subdivided into a number of map and reduce tasks. The tasks of a job are executed concurrently. Task assignment is the problem of deciding which task should be allocated to a node in the MapReduce cluster. The task assignment algorithm should consider the current state of resources at the concerned node as well as the resources requirements of tasks in the schedulers queue. Given this information, the task assignment algorithm should choose a task that maximizes resource utilization on the concerned node while still making sure that the node is not overloaded. We used a similar approach as that used in the admission controller for task assignment as well. While choosing a task, we first classify the queued tasks into two categories, good and bad. Good tasks do not overload resources at a node during their execution. From the tasks that are labeled good, we choose the task that has the maximum utility, which in this case is the priority of a task. Again, if none of the tasks are classified as good, we do not assign any task to the concerned node. Task priority is set by the cluster administrator, and can be used for policy enforcement. We thus decouple task assignment from policy enforcement. Once a task is assigned, we observe its effects, and if it results in overloading of resources at the concerned node, we conclude that the task assignment decision was incorrect and update the classifier accordingly. This makes sure that chances of assignments that result into overloading are reduced over time. Overload rules are specified by system administrator.

Abstract

Analog to Digital Converter (ADC) is a fundamental component in digital signal processing systems. For high-speed applications, a flash ADC is often used. Resolution, speed, and power consumption are the three key parameters for an analog-to-digital converter (ADC), which cannot be changed once an ADC is designed. While one can use only 8-bit precision from a 10-bit ADC. Such an application is non-optimal, resulting in slower speed and extra power consumption due to full 10-bit internal operation. Flash ADCs architectures commonly use high speed conversion that requires many analog comparators, which in turn cause higher complexity and power dissipation. Moreover, the accuracy of dividing resistors requires high value for reference voltage if the converting resolution is high. In this thesis, a novel architecture for flash ADC is proposed. In this architecture comparators of conventional flash ADC are replaced with CMOS inverters whose threshold can be varied dynamically. A novel peak-detector circuit is employed to achieve variable resolution for the ADC as well as to switch the unused parallel inverters to standby mode. The ADC is capable of operating at 4-bit, 6-bit, and 8-bit precision at a supply voltage of 2.5V, it consumes 21.5mW at 8-bit, 9mW at 6-bit and 3.5mW at 4-bit resolution. The sampling frequency ranges from 0.8 to 1.6 GSPS, and the ADC has a DNL<±0.4LSB, INL<±0.36LSB, SNR of 47dB and SNDR of 46.3dB for 8-bit operation. The proposed ‘inverter-based’ flash ADC operating at 8-bit precision and conventional 8-bit comparator-based flash ADC have been designed, compared and verified for post layout simulations in standard 65nm CMOS technology using thick gate process. It is observed that linear reduction in resolution leads to exponential reduction in power.

Abstract

Pattern discovery is one of the fundamental problems in bioinformatics and algorithms from computer science have been widely used for identifying biological patterns. The assumption behind pattern discovery approaches is that a pattern that occurs often enough in biological sequences/structures or conserved across organisms is expected to play a role in defining the respective sequence’s or structure’s functional behavior and/or evolutionary relationships. Typical examples of pattern recognition at the sequence level involves identifying repeats, conserved regulatory sequences, protein-coding regions, horizontally transferred regions, motifs, profiles, etc. Similarly at the structure level pattern recognition involves identifying domains, structural motifs and repeats, etc. In this thesis we have addressed to problems Algorithms from computer science have been widely used for identifying biological patterns. In this thesis we have addressed two problems of pattern identification: the first one is at the structure level and involves identifying structural tandem repeats using graph theoretic approaches. The other pattern recognition problem addressed here is at the genomic level and involves identifying horizontally transferred regions. A web-based tool, IGIPT, incorporating a number of measures based on anomalies in nucleotide compositions has been developed.
1. Graph Theoretic Analysis of Protein Structures
Recently much attention is being focused on the analysis of the three dimensional structure of proteins using graph theory. Here, the protein structure is defined as a graph with nodes defined as the amino acids on the polypeptide backbone chain and edges between amino acids which attempt to capture not only covalent but also non-covalent interactions. A wide variety of problems dealing with protein structure such as protein fold recognition, active site identification, detection of functionally and structurally important amino acids, domain identification, etc. have been addressed using graph theory. Here, in this study we propose to use graph properties and their spectral analysis for identifying tandemly repeated patterns in protein structures. Specifically, we focus on identifying structural repeats in proteins which are not easily detectable at the sequence level because of low conservation and high divergence between independent repeated units. Thus, analysis at the structure level would be more reliable. Also, structural analysis of the repeat regions may give some insight to the possible function of the repeat assembly. This has been carried out by constructing protein contact graphs from its 3-dimensional structure and using tools from graph theory to investigate the topology of the 3-dimensional structure of the protein. The proposed approach when implemented on a number of proteins belonging to different repeat families in Pfam database, viz., Armidallo, Spectrin, HEAT, Ankyrin, and Leucine-rich repeats and on a number of proteins from structural repeats in PROPEAT database show promising results. Compared to the self structure-comparison approach of PROPEAT database, the graph theory provides a very elegant and efficient method of identifying repeats in protein structures. Since this approach can be easily automated, one can easily carry out a comparison of multiple copies of repeats between homologues. This would help in gaining insight into the mechanisms of evolution of these proteins by observing the conservation of the copy number or gain/loss of repeating units.
2. Integrated Genomic Island Prediction Tool
Numerous biological events are responsible for the evolution to occur such as gene conversions, rearrangements (e.g., inversion or translocation), deletions, and insertions of foreign DNA (e.g., plasmid integration, transposition). Horizontal Gene Transfer (HGT) is one of the major events responsible for causing significant alterations in the genome composition. This event is more strongly supported in case of prokaryotes and archaea as compared to eukaryotes. Horizontally transferred regions generally display abnormal nucleotide compositions and measures that capture these anomalies are used for their identification. We have developed a web-based tool for identifying genomic islands in prokaryotic genomes (IGIPT) in which various measures aimed at capturing anomalous nucleotide compositions have been incorporated, viz., GC content (at the genome level and at individual codon positions), dinucleotide biases, biases in codon and amino acid usage and k-mer distribution (k=2 to 6). The objective of developing such a tool was to provide all nucleotide based measures on a single platform since it has been observed that no single measure is sufficient in identifying GIs. Also, when more than one measure predicts the same region in the genome, it increases the confidence in the prediction. IGIPT has been tested on a set of prokaryotic geno

Abstract

Human visual system is a pattern seeker of enormous power and subtlety. We not only can see things clearly, but are also capable of describing them with precision and remembering them for a long time. Having these capabilities had a major impact on our sustenance, survival and perpetuation as species. Although computers can perform a variety of tasks that are beyond human capability because of speed, complexity, or dangerous environments, attempts to replicate human perceptual abilities have been strikingly inferior, even for the visual tasks that people consider extremely simple. In this thesis, we advance the research in the field of human computation by leveraging human perceptual abilities to solve problems that computers alone cannot effectively solve. In particular, we address two important problems: user authentication, and image annotation. User authentication has issues in both security and usability. For example, passwords are either ‘secure but difficult to remember’ or ‘memorable but not secure’, when by definition, they needs be both secure and memorable. Graphical passwords are viable alternative to text passwords since they are based on proven human ability to recognize and remember images, coupled with the larger password space offered by images. In this thesis, we propose and evaluate, Marasim, a novel Jigsaw based graphical authentication scheme, using Tagging. Marasim is aimed at achieving the security of system chosen images with the memorability of self chosen images. Empirical studies of Marasim provide evidence of increased memorability, usability and security. Additionally, we examine the manual image annotation problem. Recently there have been a number of attempts to lure humans into annotation process. Notable examples are interactive games like ESP, and social tagging like Flickr. However, we found that extant methods in their present form are inadequate to result in annotations of high quality. We therefore, introduce two intelligent system designs for semantic annotation of images in the form of a game and a CAPTCHA. First one is GoFish, a web variant of standard Go-Fish, a popular playing card game. While the other one is image recognition CAPTCHA, named iCAPTCHA. Behind both these designs is a strong emergent semantic theory that ensures superior annotations. Keywords: Human Computation, Perceptive Intelligence, Human in the loop system, Usable security, User Authentication, Graphical passwords, Tagging, Games with a Purpose, CAPTCHA.

Abstract

Need for better research robot platform and software development framework: The type of robots, sensor payload, etc varies with research problems and applications. A robot system with open and modular architecture enables addition of sensors, modification of overall system much easier, aid in speeding up the research work and customizing the robotic system as per requirements of the applications. Most of the commercial research robot platforms like Amigobot, Pioneer, Khepera offer limited options to modify the robot system. While this is good, in a way, in that it leads to research work in a common stream, there is a tendency for the research area to grow around the capabilities of robots. Cost of the robotic system, upgrading etc, also plays crucial role when there is limited funding. An affordable and open architecture robotic system will enable more researchers to work on actual robots instead of simulators. The complexity of the robot algorithms can be reduced by using sensor fusion of multiple sensors, to extract more accurate data. Computationally different algorithms can be developed by streamlining various modules to work in parallel. Unlike computers, robots work in highly dynamic environment; actuators and sensors are not accurate. This makes software development for robot far more complicated than developing software for computers. The features, capabilities and performance of different robot platforms are different, making it difficult to port software between different types of robots. Majority of the robotics software development is happening in universities and research labs, whose primary goal is to make scientific contributions in various areas of robotics. There is a need to integrate the existing work, in order to progress to higher level research problems. In order to handle large volume of data from multiple sensors, streamlined data management solutions are required. Features and advantages of our research robot platform: With the above goals in mind we have developed a new indoor research robotic system, which we describe in this thesis. It comprises of a differential drive wheel base, and an array of multiple ranging sensors which enable better data accuracy through sensor fusion. A digital compass provides additional robot heading information in addition to pose(x, y, θ), of the robot, from wheel encoder. The embedded controller is modularized into two distinct parts, a motion controller and a sensor controller. The motion controller is designed such that, the robot base comprising motors, encoders and wheels can be changed with very little modification in the embedded controller software. The robot is controlled by computer via ZigBee wireless communication link. Overall data exchange between computer and robot is structured such that frequency and volume of communication is reduced, due to less communication over head. This will enable more number of robots to simultaneously communicate in limited bandwidth. The design and architecture of this robotic system has been done keeping the requirements of robotics researchers and single and multi robot research platforms in mind. This robot at its current stage has most of the features required to be commercialized. It costs a fraction of similar commercial research robots, and provides better sensors and communication features. Features and advantages of robot software development framework This framework enables the algorithm to be divided into independent modules which can be run as separate threads or processes. Database tables are used to implement inter process communication (IPC). The output result of a module is written into a table and this data is used as input to some other modules. As database can be accessed over the network, processes can run on single or multiple computers. The processes are programming language and OS independent. Structured Query Language (SQL) provides various ways of accessing the data, which can enable us to design algorithms with computationally different approaches and reduce the burden of data management. As this framework supports robot software to run as separate processes, it is possible to run different robot control programs as separate processes and integrate those using tables as IPC.

Abstract

Scene interpretation is a fundamental task in both computer vision and robotic systems. We deal with two important aspects of scene interpretation, they are scene reconstruction and scene recognition. Scene reconstruction is determining 3D positions of world points and retrieving camera poses from images. It has several applications such as virtual building editing in computer aided architecture, video augmentation in film industry and planning and navigation in mobile robotics. Among several approaches to modeling the scene, we deal with piecewise planar modeling due to several advantages: Man-made environments are often piece-wise-planar, planar modeling has compact representation and this can be easily modified. We propose a convex optimization based, approach for piecewise planar reconstruction. We show that the task of reconstructing a piece-wise planar environment can be set in an L∞ based Homographic framework that iteratively computes scene plane and camera pose parameters. Instead of image points, the algorithm optimizes over inter-image homographies. The resultant objective function is minimized using Second Order Cone Programming algorithms. Apart from showing the convergence of the algorithm, we also empirically verify its robustness to error in initialization through various experiments on synthetic and real data. We intend this algorithm to be in between initialization approaches like decomposition methods and iterative non-linear minimization methods like Bundle Adjustment. Scene recognition in robotics, specifically terrain scene recognition is one of the fundamental tasks of autonomous navigation. Navigable terrains are examples of planar scenes. The goal of terrain recognition is to recognize various terrains that occur in urban and rural environments in an automated fashion. It has applications in various domains such as advanced driver assistance systems, remote sensing, etc. Various sensing modalities such as ladars, lasers, accelerometers, stereo cameras, omni-directional cameras or combination of them are used in literature. This thesis attacks the problem of scene interpretation using a single camera. This investigation is especially crucial since cameras are relatively low in cost, consume low power, light weight and have the potential to provide very rich information about the environment. Recent advances in computer vision, machine learning and improvements in hardware capabilities have greatly increased the scope of monocular camera, even in unstructured and real world environments. In this thesis, we start with empirical study of promising color, texture and their combination with classifiers such as Support Vector Machines (SVM) and Random Forests. We present comparison across features and classifiers. Then we present a monocular camera based terrain recognition scheme called Partition based classifier. The uniqueness of the proposed scheme is that it inherently incorporates spatial smoothness while segmenting an image, without the requirement of any additional post-processing. The algorithm is fast because it is build on top of a Random Forest classifier. The efficacy of the proposed solution can be seen as we reach low error rates on both our dataset and other publicly available datasets. Further partition classifier is extended to be online and adaptive. The new scheme consists of two underlying classifiers. One of which is learnt over bootstrapped or offline dataset, the second is another classifier that adapts to changes on the fly. Posterior probabilities of both the static and online classifiers are fused to assign the eventual label for the online image data. The online classifier learns at frequent intervals of time through a sparse and stable set of tracked patches, which makes it lightweight and real-time friendly. The learning which is acuted at frequent intervals during the sojourn significantly improves the performance of the classifier vis-a-vis a scheme that only uses the classifier learnt offline. The method finds immediate applications for outdoor autonomous driving where the classifier needs to be updated frequently based on what shows up recently on the terrain and without largely deviating from those learnt offline.

Abstract

Nearest neighbor retrieval can be defined as the task of finding the objects that are most similar to a query from a given a database of objects. It find its application in areas ranging from medical domain, financial sector, computer vision, computational sciences, computational geometry, information retrieval, etc. With the expansion of internet, the amount of digitized data is increasing by leaps and bounds. Retrieval of nearest nearest neighbors accurately and efficiently becomes challenging in such a scenario as the database contain a large number of objects. The problem gets worsen when the underlying distance measure used to compute [dis]similarity is computationally expensive. In such a scenario, sequential scan of data would take a lot of time which is the biggest problem for any online retrieval system. For example in biometric authentication systems, a particular person’s biometric template is compared against all the registered samples in a database to identify the person. This process can be extremely time consuming in large databases even if the matching algorithm is extremely fast. For example, to do background check of a person who is crossing the border using the complete IAFIS,(a biometric person identification system at the U.S. border crossings), requires around 55 million comparisons. Even with the state of the art matching algorithms and computing facilities, this would take close to 10 minutes, which is not practical considering the millions of people who cross the border every month. Even for criminal investigations, it is desirable to get a quick and approximate search done immediately rather than the typical turn-around time of a few days for a search. This thesis proposes a novel method for improving the efficiency and accuracy of nearest neighbor retrieval and classification in spaces with computationally expensive distance measures. The proposed technique is domain-independent, and can be applied in arbitrary spaces, including non- Euclidean and non-metric spaces. The main contributions of our work are : • A representation scheme for objects in a dataset that allows for fast retrieval of approximate nearest neighbors in non-euclidean space. The approach named Hierarchical LocalMaps (HLM),make use of manifold learning techniques to compute linear approximation of local neighborhoods. • Search mechanism combined with filter and refine approach is proposed that minimizes the number of exact distance computations for computationally expensive distance measure. • Study performance of our scheme on biometric data and study the parameters affecting its performance. vi vii Results of k-nearest neighbor retrieval as well as classification results on UNIPEN dataset shows the advantages of using HLM over state-of-the-art approximate nearest neighbor retrieval algorithms. Classification result on CASIA iris dataset by using average gabor response for a block as the feature vector along with Euclidean distance as the soft biometric measure in conjugation with Daugman’s feature vector and hamming distance as the hard biometric shows the advantage of using a softer metric over a hard metric for indexing.

Abstract

Many problems in computer vision are mapped to minimization of an energy or a cost function defined over a discrete Markov Random Field (MRF) or Conditional Random Field (CRF). The primary reason for the popularity has been the successes of the graph cuts based methods in solving various labeling problems, especially, image segmentation, stereo correspondence and image denoising. Subsequently, computer vision researchers focused on improving the computational efficiency of graph cuts based methods. In this dissertation, we present two methods to speed up the graph cuts to solve different MRF optimization problems optimally. In the first half of the dissertation, we present efficient methods to speed up MRF optimization using graph cuts on the GPU. In particular, we present our optimal implementation of the push-relabel methods to solve various labeling problems and show how we have efficiently used different facilities available on the GPU. We also present the incremental α-expansion algorithm to solve multilabel MRFs on the GPU and show how shifting the energy function computation and graph construction to the GPU speeds up the overall computation. We compare the efficiency of our approaches on the problems of image segmentation, image restoration, photomontage and disparity computation on the GPU. The second half of the dissertation deals with the minimization of energy functions defined over large images involving millions of pixels and large number of labels. The computation and memory costs of the current vision algorithms increase at a very fast rate with the increase in the number of the variables in the MRF. This makes them inapplicable to be used for problems involving large images. We present Pyramid Reparameterization scheme to improve the computation efficiency without sacrificing global optimality for bilabel segmentation. We also formulate the multilabel problems like stereo correspondence and image denoising on a multiresolution framework using Pyramid Reparameterization. This formulation reduces both the computation and memory costs. We model the optimization problem on the pyramidal framework to dynamically update and initialize the solution at the current level with the solution from the previous level. The results of this method are compared with those obtained using conventional methods which solve graph cuts on the largest image.

Abstract

Points-based models have gained popularity in recent years. The most attractive feature of the pointbased primitives is its simplicity. No information about connectivity or topology of the surface is stored explicitly. Adaptive modication and dynamic sampling of the surface do not suffer from complexity and robustness like triangle mesh. The level of detail is simple, fast and almost continuous. However, points based methods suffer from surface normal discontinuities in representation. Shading is also not independent from sampling rate. Point based models can be visualized by rendering the points directly. Each sample in the representation has certain attributes (normal, color, material properties) for rendering and shading them as a continuous surface. Typically, a point sample also has a radius to dene an area around it. Such samples are called surfels and approximate the shape of the surface linearly in their neighborhood. Since linear splats can only be at shaded, such representations require a large number of samples for a good shading quality. This slows the rendering due to increase in rendering computation and related memory bus activity. Point-based rendering suffer from the limited resolution of the xed number of samples representing the model. At some distance, the screen space resolution is high relative to the point samples, which causes under-sampling. A better way of rendering a model is to re-sample the surface during the rendering at the desired resolution in object space, guaranteeing a sampling density sufcient for image resolution. Output sensitive sampling samples objects at a resolution that matches the expected resolution of the output image. This is crucial for hole-free point-based rendering. Many technical issues related to point-based graphics boil down to reconstruction and re-sampling. A point based representation should be as small as possible while conveying the shape well. In the rst part of this thesis, we present a compact representation for point based models using non-linear surface elements. In the second part, we present a method for fast ray casting of a dynamic surface dened by large number of attributed points called Metaballs. Algebraic Splats: Higher-order approximations of the local neighborhood have the potential to represent the shape using fewer primitives, simultaneously achieving higher rendering speeds and quality. In this thesis, we present algebraic splats, which are low-order polynomials that approximate the local neighborhood of a pointset. We adapt the Moving Least Squares (MLS) approximation to generate algebraic splat representations for a given point set. Quadratic and cubic splats as basic rendering primitive are able to approximate point-based models using 10% or fewer points than linear splats, for equivalent viii ix visual quality. Though rendering a non-linear patch is slower compared to a linear splat, the overall speed of rendering of an object could be faster. The approximation error can also be less using a small number of higher order primitives. We represent a given point set with a user-specied small number of algebraic splats with optimal rendering quality. This is done by decimating the point set and jointly approximating each using a local algebraic surface based on the Moving Least Squares (MLS) approximation. Our rendering provides smooth surfaces with normals everywhere. We can render polynomials directly on today's GPUs using ray-tracing because of the semi-implicit nature of the splats in the local reference domain. The major contributions of this work are: (i) A compact and lightweight representation for point geometry using nonlinear surface elements, called algebraic splats; (ii) A multi-resolution representation which provides continuous Level of Detail; and (iii) A ray-tracing approach to render the algebraic splats on the GPU. The method includes an adaptive anti-aliasing step to obtain smooth silhouettes. The David 2mm model can be represented using about 30K (or 0.8% of original) algebraic splats with little or low reduction in visual quality. We can raycast the David model with adaptive antialiasing (33 grid) at 130-150 fps and 80-90 fps with shadowing. Our method is faster by a factor of 10 on most models and require about 90% less diskspace in comparision to linear splats. Metaballs: Since the available computational power is steadily growing, more and more science areas rely on simulations of ever-growing problem sizes producing huge amount of data to be analyzed. Simulation and experimental measurement in life sciences, physics, chemistry, materials, and thermodynamics yield large and often also time-dependent datasets. Interactive visualization is the key service that facilitates the analysis of such datasets and thus enables the researchers in those elds to quickly assess and compare the results of a simulation or measurement, verify and improve their mod

Abstract

Advances in cameras and web technology have made it easy to capture and share large amounts of video data over to a large number of people. Also, an increasing number of video cameras observe public spaces like airports, train stations, shopping malls, streets, and other public places today. Video surveillance is an important tool to prevent, detect and reduce crime and disorder. It is also widely used to monitor people’s conduct, detect their presence in an area and/or possibly study their actions too. However, many civil rights and privacy groups have expressed their concern that by allowing continual increases in surveillance of citizens, we will end up in a mass surveillance society, with extremely limited, or non-existent political and/or personal freedoms. With the widespread use of surveillance today, we are becoming used to “being watched”. As time goes on, the more accustomed we become to video surveillance, we are not as likely to fight to maintain our right to privacy. Critics believe that in addition to its obvious function of identifying and capturing individuals who are committing undesirable acts, surveillance also functions to create in everyone a feeling of always being watched, so that they become self-policing. At the same time prices of hardware have fallen, and the capabilities of systems have grown dramatically. The day is not far when it would be easy to convert even the lowcost video surveillance units into “intelligent” human recognition systems. These raise concerns on the unintentional and unwarranted invasion of the privacy of individuals caught in the videos. The data collected during video surveillance consist mainly of images and sounds which allow identification of people captured, whether directly or indirectly, in addition to monitoring their conduct. While there may be a possible security need to identify the individuals in these videos, identifying the action suffices in most cases. The actor needs to be identified only rarely and only to authorized personnel. The privacy concerns related to the processing and distribution of the collected videos are genuine and will grow with wider adaptation of video technology. To address these concerns, automated methods to de-identify individuals in these videos are necessary. De-identification does not aim at destroying all information involving the individuals. Its ideal goals are to obscure the identity of the actor without obscuring the action. There is a natural trade-off between protecting privacy and providing sufficient detail. The goal is to protect the privacy of the individuals while providing sufficient feel for the human activities in the space being imaged. The policies on the privacy issues are still unclear and are fast evolving. The need of the hour is to be cautious as digital data has the potential to be replicated with little control, especially when placed on the cloud. This thesis outlines the scenarios in which de-identification is required and the issues vi vii brought out by those. We also present an approach to de-identify individuals from videos. Our approach involves tracking and segmenting individuals in a conservative voxel space involving x, y and time. A de-identification transformation is applied per frame using these voxels to obscure the identity. A robust de-identification scheme with a randomization module was designed in order to make reconstruction and comparison based identification attacks impossible. Face, silhouette, gait, and other characteristics need to be obscured, ideally. We show results of our scheme on a number of videos and for several variations of the transformations. We present the results of applying algorithmic identification on the transformed videos. We also present the results of a user-study to evaluate how well humans can identify individuals from the transformed videos. The results showed that as the parameter controlling the amount of deidentification increased, the actors became less identifiable (more privacy), while the video started losing the context and detail. The studies also suggest that an action can be recognized with more accuracy than the actor in a de-identified video, which is the guiding principle of de-identification. We also created a suitable dataset for the purpose of user studies, as the standard datasets available online are not challenging enough for such an evaluation.