Compressive Sensing and its Applications in Video and Audio Processing
Date Issued
2015
Date
2015
Author(s)
Hsu, Yi-Han
Abstract
The Shannon and Nyquist’s sampling theorem states that: when a signal is bandlimited, and the sampling frequency is at least twice faster than signal bandwidth, then the sampled signal preserve enough information to recon- struct the original signal. If the sampling frequency isn’t high enough, there will be some overlapping of the sampled signals and cause aliasing effect. The frequency range of human speech is between 300Hz to 3400Hz, so the standard sampling frequency of telephone communication is 8000Hz. And the hearing range of human ear is given as 20Hz to 20000Hz, so 44100Hz is a common sampling frequency for most of the digital audio files. As for video file, the sampling frequency is usually several MHz. The data would be quite huge, compression is always needed for the convenience of transmission or storage. Compressive sensing is a newly developed signal sampling and recon- struction theorem. This theorem is proposed by Emmanuel Candes, David Donoho, and Terence Tao. The core concept of this theorem is that, when a signal has sparsity in a specific orthogonal space, we can sample this signal at a frequency which is much lower than Nyquist rate, and still be able to reconstruct it precisely. If we use traditional sampling method, for a signal with length 500, we need at least 500 masurements to reconstruct this signal. Just like we need 500 equations to solve a linear system with 500 unknowns. Compressive sensing assumes that signals have sparsity in specific domain,i.e. only a few positions are nonzero. Due to the sparsity, we are able to recon- struct the whole signal with simply 100 measurements. Just like we can solve a linear system with 500 unknowns with only 100 equations. Compression is therefore achieved since the amount of data is drastically reduced. There are many applications based on compressive sensing, like denois- ing, image inpainting, image restoration, object detection, face recognition, incoherent sampling of radar impulse...etc. Compressive sensing is also brought to a mobile phone camera sensor and MRI imaging. Based on compressive sensing, a fast low-rank approximation algorithm GoDec is developed. In the past, singular valude decomposition (SVD) is used to obtain a low-rank approximation. But the time complexity of SVD is too high, GoDec outperforms SVD when considering time consumption. In this thesis, basic concepts and some existing applications of compressive sens- ing are introduced. Compressive sensing for high dimensional data restora- tion is also discussed. Then I demonstrate the physical meaning of “low-rank approximation” of time series data, and show some applications of this algo- rithm on video and audio file. Combining this fast low-rank approximation with some existing techniques, a new video rain removal algorithm is pro- posed. Not only the rain is removed by this algorithm, the performance of hue and brightness is also improved. It can be further applied to haze or snow removal. Unlike existing rain removal algorithms, which are usually consist of rain detection, rain removal and pixel interpolation procedures, the compu- tational time of my algorithm is much shorter than other algorithms. The time complexity of this proposed method is low, and it doesn’t require huge mem- ory, The ability of rain, snow, haze removal and color restoration are both better than existing methods. Real-time processing on hardware is possible under optimization.
Subjects
Compressive Sensing
Low-Rank Approximation
Rain Removal
Haze Removal
Denoising
Moving Object Detection
Type
thesis