跳到主要內容

臺灣博碩士論文加值系統

(3.238.135.174) 您好!臺灣時間:2021/08/05 07:16
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:許意函
研究生(外文):Yi-Han Hsu
論文名稱:壓縮感知及其於影片與音訊處理之應用
論文名稱(外文):Compressive Sensing and its Applications in Video and Audio Processing
指導教授:貝蘇章
指導教授(外文):Soo-Chang Pei
口試委員:鍾國亮黃文良林康平祁忠勇
口試日期:2015-06-06
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電信工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:100
中文關鍵詞:壓縮感知低階近似除雨除霧降噪移動物體偵測
外文關鍵詞:Compressive SensingLow-Rank ApproximationRain RemovalHaze RemovalDenoisingMoving Object Detection
相關次數:
  • 被引用被引用:0
  • 點閱點閱:261
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
傳統的取樣定理 (Sampling Theorem) 指出,若信號為帶寬限制的, 且取樣頻率大於等於信號最高頻率的兩倍時,則取樣後的信號完整保 留了原始信號的訊息,可完整的重建原來的信號。若取樣頻率不足, 會導致頻譜的重疊進而造成失真,稱為混疊 (Aliasing Effect)。由於人 說話的頻率大約介於 300Hz 到 3400Hz 之間,通常電話的取樣頻率約 為 8000Hz。而人耳能聽見的頻率範圍在 20Hz 到 20000Hz 之間,所以 通常音樂檔案的取樣頻率為 44100Hz。至於影片檔的樣頻率都非常的 大,常常是 MHz 的等級。如此導致資料量非常龐大,常常需要另外進 行壓縮以便儲存或者傳輸。
壓縮感知 (Compressive Sensing) 為近年來發展出的一種全新的信號 取樣與重建理論。此理論係由 Emmanuel Candes, David Donoho, 以及 Terence Tao 等人共同提出。此理論的核心概念為:若某信號在特定正 交空間具有稀疏性 (sparsity),則即可以一遠低於 Nyquist 取樣頻率之頻 率來進行取樣,且仍能精確的重建此信號。若用傳統的取樣方式,若 信號包含五百個數據,則得至少進行五百次測量才能精確的復原此信 號。也就是說要用五百條方程式來解出五百個未知數。而壓縮感知則 是假定信號具有稀疏性,也就是只有少數地方有值,因為這個稀疏性, 可以讓我們只藉由一百次測量就完整的復原此信號。也就是說用一百 條方程式來解出五百個未知數。如此一來,需要被記錄的資料量就比 原本少了許多,進而達到壓縮的效果。
目前已有許多壓縮感知相關的應用,例如降噪 (denoising) 、影像 修補 (inpainting) 、影像恢復、物體偵測、臉部辨識、雷達脈衝取樣... 等。近年也有手機的相機晶片採用此方法來降低記錄照片所需之能量。 而目前的核磁共振 (Magnetic Resonance Imaging) 之掃描取樣也有用到 此方法。
而基於壓縮感知理論,發展出另一個快速低階近似之演算法 GoDec。以往都用奇異值分解 (Singular Value Decomposition) ,其時 間複雜度較高,而此快速低階近似方式大大降低了所需耗時,效果也 不比奇異值分解差。本篇論文先介紹了壓縮感知以及一些現存應用,也討論了高維度資料之恢復。之後研究了低階近似對於時間序列的資 料(例如影片)之意義,也探討了此演算法於影片以及音訊上的應用。 把快速低階近似結合了一些周邊技術,得到一個影片除雨演算法。此 演算法不但能有效除去影片裡的雨,更改善了整體的亮度及色相表現。 不只是雨,此方法也能應用於除霧、除雪。且由於並非如傳統的演算 法那般進行偵測雨、移除、填補空隙的步驟,所需時間遠小於其他現 存方法。所求演算法複雜度低、也不需太大的記憶體,除雨、雪、霧 的效果上以及色彩上的恢復都優於目前已知的其他方式。若再進行優 化,在硬體上進行即時處理可達到更多應用。


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.

Contents
致謝 iii
中文摘要 iv
Abstract vi
Contents ix
List of Figures xii
List of Tables xx
Chapter 1 Introduction 1
1.1 CompressiveSensingTheorem....................... 1
1.2 Reconstruction Algorithms of Compressive Sensing . . . . . . . . . . . . 4

Chapter 2 Selection of Sensing Matrix and Sparsifying Basis 7
2.1 SomeCommonlyUsedSparsifyingBasis ................. 7
2.2 SomeCommenlyUsedSensingMatrices.................. 13
2.2.1 RandomCirculantSensingMatrices ................ 13
2.2.2 LearnedCirculantSensingMatrices ................ 14
2.2.3 ZACbasedCirculantSensingMatrices . . . . . . . . . . . . . . 16
2.2.4 RecoveryPerformanceComparison ................ 16

Chapter 3 One Dimensional and Multidimensional Data Recovery 22
3.1 1DCompressiveSensingon1Dand2DData . . . . . . . . . . . . . . . 22
3.2 2DCompressiveSensing .......................... 25
3.3 Multidimensional Compressive Sensing Using Tensor Representation . . 27
3.3.1 Kronecker Product, Tucker Decomposition, and Block Sparsity . . 27
3.3.2 MultidimensionalCompressiveSensing . . . . . . . . . . . . . . 29
3.3.3 Multidimensional CS Performance Comparison . . . . . . . . . . 31
3.4 Conclusions................................. 33

Chapter 4 Fast Low-Rank Approximation 37
4.1 BilateralRandomProjections........................ 38
4.1.1 OriginalAlgorithm ......................... 38
4.1.2 ModifiedAlgorithm......................... 39
4.1.3 PerformanceComparison...................... 41
4.2 GoDecomposition ............................. 45
4.2.1 GoDecAlgorithm.......................... 45
4.2.2 ConvergenceofGoDec....................... 46
4.2.3 ApplicationsofGoDec ....................... 48

Chapter 5 GoDec for Video Processing 52
5.1 RelatedWorkofVideoRainRemoval ................... 52
5.1.1 Rain Removal via Considering Temporal and Chromatic Properties 52
5.1.2 Rain Removal via Considering the Dynamics of Rain and the Pho-
tometryoftheEnvironment..................... 55
5.2 ProposedMethodforRainRemoval .................... 61
5.2.1 RainRemovalofVideoswithStaticScene. . . . . . . . . . . . . 61
5.2.2 Rain Removal of Videos with Static Scene and Moving Object . . 67
5.2.3 RainRemovalofVideoswithDynamicScene . . . . . . . . . . . 72
5.3 ProposedMethodforHazeRemoval .................... 77
5.4 ProposedMethodforMovingObjectDetection . . . . . . . . . . . . . . 78

Chapter 6 GoDec in Audio Processing
81
6.1 AudioClippingRecoveryviaGoDec.................... 81
6.2 AudioInpainting .............................. 86
6.3 AudioDenoising .............................. 86

Chapter 7 Conclusion and Future Work 93
References 95

Bibliography
[1] Cesar F Caiafa and Andrzej Cichocki. Computing sparse representations of mul- tidimensional signals using kronecker bases. Neural computation, 25(1):186–220, 2013.
[2] Tianyi Zhou and Dacheng Tao. Bilateral random projections. In Information The- ory Proceedings (ISIT), 2012 IEEE International Symposium on, pages 1286–1290. IEEE, 2012.
[3] Kostadin Dabov, Alessandro Foi, and Karen Egiazarian. Video denoising by sparse 3d transform-domain collaborative filtering. In Proc. 15th European Signal Process- ing Conference, volume 1, page 7, 2007.
[4] Xiaopeng Zhang, Hao Li, Yingyi Qi, Wee Kheng Leow, and Teck Khim Ng. Rain removal in video by combining temporal and chromatic properties. In Multimedia and Expo, 2006 IEEE International Conference on, pages 461–464. IEEE, 2006.
[5] Kshitiz Garg and Shree K Nayar. Detection and removal of rain from videos. In
Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, volume 1, pages I–528. IEEE, 2004.
[6] AbhishekKumarTripathiandSudiptaMukhopadhyay.Removalofrainfromvideos: a review. Signal, Image and Video Processing, 8(8):1421–1430, 2014.
[7] HJ Landau. Sampling, data transmission, and the nyquist rate. Proceedings of the IEEE, 55(10):1701–1706, 1967.
[8] Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and ap- plied mathematics, 59(8):1207–1223, 2006.
[9] Ronald A DeVore, Björn Jawerth, and Bradley J Lucier. Image compression through wavelet transform coding. Information Theory, IEEE Transactions on, 38(2):719– 746, 1992.
[10] Emmanuel J Candès and Michael B Wakin. An introduction to compressive sam- pling. Signal Processing Magazine, IEEE, 25(2):21–30, 2008.
[11] Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal on computing, 24(2):227–234, 1995.
[12] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge univer- sity press, 2004.
[13] Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decom- position by basis pursuit. SIAM journal on scientific computing, 20(1):33–61, 1998.
[14] Joel A Tropp. Greed is good: Algorithmic results for sparse approximation. Infor- mation Theory, IEEE Transactions on, 50(10):2231–2242, 2004.
[15] Irina F Gorodnitsky and Bhaskar D Rao. Sparse signal reconstruction from limited data using focuss: A re-weighted minimum norm algorithm. Signal Processing, IEEE Transactions on, 45(3):600–616, 1997.
[16] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty prin- ciples: Exact signal reconstruction from highly incomplete frequency information. Information Theory, IEEE Transactions on, 52(2):489–509, 2006.
[17] Po-Shen Loh. Image reconstruction with ridgelets. 2003.
[18] Y Zhang, J Yang, and Wotao Yin. Yall1: Your algorithms for l1. MATLAB software,
http://www. caam. rice. edu/ ̃ optimization L, 1, 2010.
[19] Youngjune Gwon, HT Kung, and Dario Vlah. Compressive sensing with optimal sparsifying basis and applications in spectrum sensing. In Global Communications Conference (GLOBECOM), 2012 IEEE, pages 5386–5391. IEEE, 2012.
[20] Wotao Yin, Simon Morgan, Junfeng Yang, and Yin Zhang. Practical compressive sensing with toeplitz and circulant matrices. In Visual Communications and Image Processing 2010, pages 77440K–77440K. International Society for Optics and Pho- tonics, 2010.
[21] Joel A Tropp, Michael B Wakin, Marco F Duarte, Dror Baron, and Richard G Bara- niuk. Random filters for compressive sampling and reconstruction. In Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE Inter- national Conference on, volume 3, pages III–III. IEEE, 2006.
[22] Richard Baraniuk and Philippe Steeghs. Compressive radar imaging. In Radar Con- ference, 2007 IEEE, pages 128–133. IEEE, 2007.
[23] Roummel F Marcia and Rebecca M Willett. Compressive coded aperture superres- olution image reconstruction. In Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on, pages 833–836. IEEE, 2008.
[24] Dong Liang, Guangwu Xu, Haifeng Wang, Kevin F King, Dan Xu, and Leslie Ying. Toeplitz random encoding mr imaging using compressed sensing. In Biomedical Imaging: From Nano to Macro, 2009. ISBI’09. IEEE International Symposium on, pages 270–273. IEEE, 2009.
[25] MassimoFornasierandHolgerRauhut.Compressivesensing.InHandbookofmath- ematical methods in imaging, pages 187–228. Springer, 2011.
[26] Michael Elad. Optimized projections for compressed sensing. Signal Processing, IEEE Transactions on, 55(12):5695–5702, 2007.
[27] Julio Martin Duarte-Carvajalino and Guillermo Sapiro. Learning to sense sparse signals: Simultaneous sensing matrix and sparsifying dictionary optimization. Image Processing, IEEE Transactions on, 18(7):1395–1408, 2009.
[28] Yangyang Xu, Wotao Yin, and Stanley Osher. Learning circulant sensing kernels. Technical report, DTIC Document, 2014.
[29] Justin Romberg. Compressive sensing by random convolution. SIAM Journal on Imaging Sciences, 2(4):1098–1128, 2009.
[30] Inc. Gurobi Optimization. Gurobi optimizer reference manual, 2015.
[31] JohnJBenedettoandSomantikaDatta.Constructionsandageneralizationofperfect autocorrelation sequences on ?. In Multiscale Signal Analysis and Modeling, pages 183–207. Springer, 2013.
[32] Wotao Yin. Gurobi mex: A matlab interface for gurobi. Online at http://convexop- timization.com/wikimization/index.php/gurobi_mex, 2009–2011.
[33] Haifeng Wang, Dong Liang, and Leslie Ying. Pseudo 2d random sampling for com- pressed sensing mri. In Engineering in Medicine and Biology Society, 2009. EMBC 2009. Annual International Conference of the IEEE, pages 2672–2675. IEEE, 2009.
[34] Srdjan Stankovic and Irena Orovic. Compressive sensing reconstruction for sparse 2d data. arXiv preprint arXiv:1502.05980, 2014.
[35] Hao Fang, Sergiy A Vorobyov, Hai Jiang, and Omid Taheri. 2d signal compression via parallel compressed sensing with permutations. In Signals, Systems and Comput- ers (ASILOMAR), 2012 Conference Record of the Forty Sixth Asilomar Conference on, pages 1925–1929. IEEE, 2012.
[36] Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3):455–500, 2009.
[37] Andrzej Cichocki, Rafal Zdunek, Anh Huy Phan, and Shun-ichi Amari. Nonneg- ative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation. John Wiley & Sons, 2009.
[38] Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Comput- ing, 33(5):2295–2317, 2011.
[39] Yair Rivenson and Adrian Stern. Compressed imaging with a separable sensing operator. Signal Processing Letters, IEEE, 16(6):449–452, 2009.
[40] James G Nagy and Misha Elena Kilmer. Kronecker product approximation for pre- conditioning in three-dimensional imaging applications. Image Processing, IEEE Transactions on, 15(3):604–613, 2006.
[41] Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. On the best rank-1 and rank-(r 1, r 2,..., rn) approximation of higher-order tensors. SIAM Journal on Matrix Analysis and Applications, 21(4):1324–1342, 2000.
[42] Marco F Duarte and Richard G Baraniuk. Kronecker compressive sensing. Image Processing, IEEE Transactions on, 21(2):494–504, 2012.
[43] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decom- positions. SIAM review, 53(2):217–288, 2011.
[44] M Fazel, E Candes, B Recht, and P Parrilo. Compressed sensing and robust recov- ery of low rank matrices. In Signals, Systems and Computers, 2008 42nd Asilomar Conference on, pages 1043–1047. IEEE, 2008.
[45] Sam Roweis. Em algorithms for pca and spca. Advances in neural information processing systems, pages 626–632, 1998.
[46] Tianyi Zhou and Dacheng Tao. Godec: Randomized low-rank & sparse matrix de- composition in noisy case. In in International Conference on Machine Learning. Citeseer, 2011.
[47] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal com- ponent analysis? Journal of the ACM (JACM), 58(3):11, 2011.
[48] Kristian Bredies and Dirk A Lorenz. Iterated hard shrinkage for minimization prob- lems with sparsity constraints. SIAM Journal on Scientific Computing, 30(2):657– 683, 2008.
[49] A.S. Georghiades, P.N. Belhumeur, and D.J. Kriegman. From few to many: Illu- mination cone models for face recognition under variable lighting and pose. IEEE Trans. Pattern Anal. Mach. Intelligence, 23(6):643–660, 2001.
[50] Li Cheng, Minglun Gong, Dale Schuurmans, and Terry Caelli. Real-time discrim- inative background subtraction. Image Processing, IEEE Transactions on, 20(5): 1401–1414, 2011.
[51] JohnSMarshallandWMcKPalmer.Thedistributionofraindropswithsize.Journal of meteorology, 5(4):165–166, 1948.
[52] Robert Michael Manning. Stochastic Electromagnetic Image Propagation: An Adaptive Compensation. McGraw-Hill Companies, 1993.
[53] G. Evangelidis. Iat: A matlab toolbox for image alignment. http://www. iatool.net, 2013.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top