Video surveillance systems are widely deployed to keep private and public spaces safe and secure. There are over 30 million cameras in United States only, shooting 4 billion hours of video footage a week. Currently, it requires significant human supervision to analyze the videos captured by surveillance cameras. Since it is not possible to analyze all the video data with eye inspection, most of it is stored and not processed. One approach to tackle this problem is to simplify the algorithms, but this would inevitably increase the false alarm and miss rates. Another approach would be to use more computing power. Programmable Graphics Processor Units (GPUs) have evolved into multi-threaded, many-core, highly parallel processors. However, to be able to take full advantage of the GPUs, the algorithms must be highly parallel. The objective of the proposed project is to design and implement parallel video analysis algorithms optimized for the GPU. The state-of-the-art computer vision algorithms used for video analysis will be parallelized or new algorithms optimized for GPUs will be designed if needed, without compromising the performance. Theoretical work on global optimization using message passing will be done so that the convergence is fast and resulting local minimum is satisfactory. The message passing algorithm will be used in optimization stages required by most of the analytics algorithms. A metadata will be created, shared and used by the algorithms to reduce the overall running time. An analytics engine will be designed and implemented to efficiently use the results of this project, while achieving a (close to) real-time execution. Finally, this engine will be tested on video footage obtained from Istanbul Police Department’s Information and Security System, which is a video surveillance system that monitors Istanbul’s streets, highways, and important districts with high crime rates, accidents, and congestions.