傳統影像資料例如由照相機取得，在類比轉數位(Analog-to-digital; A/D)的取樣過程(Sampling process)中，其取樣率依據取樣定理(Sampling theory)至少須為訊號頻寬的二倍，所取樣出的離散取樣資料其量非常可觀，然後在傳送過程也須經由資料壓縮並透過多媒體網路來傳送這種取樣與壓縮方式其過程的確浪費了大量的取樣資源。
本篇論文探討一種新的信號處理技術，稱之為壓縮感測(Compressive sensing; CS)，被提出並廣泛應用在視訊與通訊訊號處理領域中，有別於傳統作法，壓縮感測技術的特色在於其取樣技術是針對具稀疏性(Sparsity)或可壓縮(Compressive)的訊號源，即在取樣時直接針對訊號進行壓縮的新興理論，此種作法容許我們所取樣的原始信號頻寬可以低於傳統取樣定理的要求。
基本上傳統壓縮感測(CS)理論是基於假設稀疏值訊號向量(Signal vector)的位置是未知的，這樣會使得在許多實際應用上有許多限制，但是在許多情況中，稀疏值的位置於接收端是可以預知的，因此所謂退化壓縮感測演算法被提出，退化型的演算法[11](Degradation algorithm of CS)被設計用於信號獲取(Acquisition)，並利用被檢測出的大多數稀疏值，經由線性處理來進行訊號之重建(Reconstruction)。相較於傳統其他類似的壓縮感測方法，退化型壓縮感測演算法可以有效減少感測數量及改善操作效率。
最後，我們可以由電腦模擬的結果，驗證我們所提出的方法。

In the conventional image/video compression approach, we need to first capture the image/video signals from for example camera, and take more sampled data via sampling processes. For transmission those sampled data through various communication networks, high efficient compression algorithm is required for compressing data [2-8]. This processes of sampling analog signal and then compressing them for reducing the quantity of sampled data is a kind of wasting. Compressive sensing (CS) is an emerging approach for the acquisition of signals having a sparse or compressible representation in some basis. It has been developed from questions raised about the efficiency of the conventional signal processing pipeline for compression, coding and recovery of natural signals, including audio, still images and video. With the basic principle developed in CS, we might enable dramatically reduced measurement time, reduced sampling rates significantly, or reduced use of Analog-to-Digital converter resources.
Many natural signals have concise representations when expressed in the proper basis. Recently, for data acquisition and signal recovery based on the premise that a signal having a sparse representation in the proper basis, the technique of degradation algorithm of CS [11] was presented for image compression. It showed that the complexity as well as signal reconstruction quality could be improved significantly.
Via computer simulation, we verify that the performance is improved, in terms of the PSNR and the efficiency of the system.

目錄   
第一章  緒論	1
1.1研究背景與動機	1
1.2研究方法	4
1.3論文架構	5
第二章  相關研究與背景知識	6
2.1壓縮感測相關文獻	6
2.1.1 傳統壓縮感測	6
2.1.2 使用奇異值分解的壓縮感測	9
2.2 H.264相關文獻	11
2.2.1 H.264視訊壓縮標準介紹	11
2.2.2 畫面內部預測	15
2.2.3 畫面間預測	20
2.2.4 低複雜度的整數離散餘弦轉換及量化	23
第三章  研究架構與設計	37
3.1 系統架構	37
3.2 以整數DCT為基底之退化型壓縮感測	39
第四章 實驗結果	49
4.1 實驗環境	49
4.2 傳統壓縮感測與退化型壓縮感測之比較	51
4.3 結合量化	71
4.4 將退化型壓縮感測應用於H.264/AVC	78
第五章  結論與未來展望	82
5.1 結論	82
参考文獻	84

圖目錄
圖1.1 傳統編碼端與解碼端的架構圖	3
圖1.2 壓縮感測架構	4
圖2.1 將QCIF畫面分成 巨集區塊[28]	13
圖2.2 H.264編碼端[1]	14
圖2.3 H.264解碼端[1]	14
圖2.4 原始區塊與 預測的亮度區塊	16
圖2.5 九種預測模式與預編碼區塊間的SAE值	18
圖2.6  的預測區塊標記	18
圖2.7 九種 亮度預測模式[1]	18
圖2.8 Intra 四種預測模式示意圖	19
圖2.9 四種預測模式與預編碼區塊間的SAE值	19
圖2.10 區塊分割方式[1]	21
圖2.11 1/2像素點預測圖	22
圖2.12 1/4像素點預測圖	22
圖2.13 非線性純量量化	30
圖3.1設計流程圖	38
圖3.2 降維度轉換矩陣之概念圖	39
圖3.3 大小為 矩陣TA	42
圖3.4大小為 矩陣TC	44
圖3.5 精準控制矩陣	46
圖3.6 擷取信號概念圖	47
圖4.1 測試圖像	50
圖4.2 PSNR值比較(測試圖像Lena)	51
圖4.3 處理完之圖像比較(測試圖像Lena)	52
圖4.4 PSNR值比較(測試圖像Boots)	53
圖4.5 PSNR值比較(測試圖像F16)	53
圖4.6 處理完之圖像比較(測試圖像Boots)	54
圖4.7 處理完之圖像比較(測試圖像F16)	55
圖4.8 PSNR值比較(測試圖像Goldhill)	56
圖4.9 PSNR值比較(測試圖像Pepper)	56
圖4.10 處理完之圖像比較(測試圖像Goldhill)	57
圖4.11 處理完之圖像比較(測試圖像Pepper)	58
圖4.12 PSNR值比較(測試圖像Baboon)	59
圖4.13 處理完之圖像比較(測試圖像Baboon)	60
圖4.14 PSNR值比較(測試圖像Lena)	62
圖4.15 PSNR值比較(測試圖像Boots)	62
圖4.16 處理完之圖像比較(測試圖像Lena)	63
圖4.17 處理完之圖像比較(測試圖像Boots)	64
圖4.18 PSNR值比較(測試圖像F16)	65
圖4.19 PSNR值比較(測試圖像Goldhill)	65
圖4.20 處理完之圖像比較(測試圖像F16)	66
圖4.21 處理完之圖像比較(測試圖像Goldhill)	67
圖4.22 PSNR值比較(測試圖像Pepper)	68
圖4.23 PSNR值比較(測試圖像Baboon)	68
圖4.24 處理完之圖像比較(測試圖像Pepper)	69
圖4.25 處理完之圖像比較(測試圖像Baboon)	70
圖4.26 PSNR值比較(測試圖像Lena)	72
圖4.27 PSNR值比較(測試圖像Boots)	72
圖4.28 PSNR值比較(測試圖像F16)	73
圖4.29 PSNR值比較(測試圖像Goldhill)	73
圖4.30 PSNR值比較(測試圖像Pepper)	74
圖4.31 PSNR值比較(測試圖像Baboon)	74
圖4.32 應用於H.264(測試影像序列為Foreman)	79
圖4.33 應用於H.264(測試影像序列為Carphone)	80
圖4.34 應用於H.264(測試影像序列為Suzie)	80

表目錄	
表2.1 H.264之量化位階表[1]	32
表2.2 縮放矩陣上的元素[1]	32
表2.3 矩陣H上的元素[1]	33
表2.4 矩陣V上的元素[1]	34
表4.1 測試環境相關設定	49
表4.2 時間比較(測試圖像Lena)	75
表4.3時間比較(測試圖像Boots)	76
表4.4 時間比較(測試圖像F16)	76
表4.5時間比較(測試圖像Goldhill)	77
表4.6 時間比較(測試圖像Baboon)	77
表4.7 時間比較(測試圖像Pepper)	78
表4.8 測試影片序列	79

[1] Iain EG Richardson, H.264 and MPEG-4 Video Compression, John Wiley & Sons, 2003.

[2] Y. Wang, J. Ostermann and Y. Zhang, Video Processing and Communications, 1st ed. Englewood Cliffs, NJ: Prentice-Hall, 2002.

[3] T. Wiegand, G. J. Sullivan, G. Bjontegaard and A. Luthra,“ Overview of the H.264/AVC Video Coding Standard,” IEEE Trans. Circuits Syst, Vol. 13, pp.560-576, July 2003.

[4] Information Technology—Coding of Audio-Visual Objects—Part 10: Advanced Video Coding, ISO/IEC Std 14496-10, 2003.

[5] G. Cote, B. Erol, M. Gallant and F. Kossentini,“H.263+: Video Coding at Low Bit Rates,” IEEE Transactions on Circuits and Systems for Video Technology, Vol.8, no.7, pp.849–66, November 1998.

[6] S.-K. Kwon, A. Tamhankarand and K. R. Rao, “Overview of H.264/MPEG-4 part 10,” Journal of Visual Commun. Image, vol. 17, pp.186-216, April 2006.

[7] H. S. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, “Low-Complexity Transform and Quantization in H.264/AVC,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, July 2003.
 
[8] T. Blu, P.-L. Dragotti, M.Vetterli, P. Marziliano, and L. Coulot,“ Sparse Sampling of Signal Innovations,” IEEE Signal Processing Magazine, vol. 25, no.2, pp. 32-40, March 2008.

[9] T. Cai, L. Wang, and G. Xu, “Shifting Inequality and Recovery of Sparse Signals,” IEEE Trans. on Signal Processing, vol.58,:pp. 1300–1308, 2010.

[10] Antti Hallapuro, Marta Karczewicz,” Low Complexity Transform and Quantization – Part I: Basic Implementation”, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG(ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6).
 
[11] Chunhui Zhao and Wei Liu,” Degradation algorithm of compressive sensing,” Journal of Systems Engineering and Electronics, vol. 22, no. 5, pp.832–839.

[12] Justin Romerg, “Imaging Via Compressive Sampling,” IEEE Signal Processing Magazine, vol.52, no.2, pp. 14-20, July 2007.

[13] Candes, E., Romberg, J., Tao, T. “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. on Inform,pp.489–509, February 2006.

[14] R. G. Baraniuk, E. Candes, R. Nowak, and M. Vetterli “Compressive Sensing,” IEEE Signal Processing Magazine, vol. 25, no.2, pp. 12-13, March 2008.

[15] E. J. Candes and M. B. Wakin, “An Introduction to Compressive Sampling,” IEEE Signal Processing Magazine, vol.25, no.2, pp.21-30, March 2008.

[16] D. L. Donoho,” Compressed Sensing,” IEEE Trans. on Information Theory,” vol. 52, no. 4, April 2006.

[17] E. J. Candes, “The restricted isometry property and its implications for compressed sensing,” Comptes Rendus Mathematique, vol. 346, pp. 589-592, 2008.

[18] R. G. Baraniuk, “Compressive sensing,” IEEE Signal Processing Magazine, Vol. 24, pp. 118–121, July 2007.

[19] E. J. Cand`es, M. B. Wakin, “An introduction to compressive sampling: a sensing/sampling paradigm that goes against the common knowledge in data acquisition,” IEEE Signal Processing Magazine, 25 (2). pp. 21-30, ISSN 1053-5888.

[20] D. Donoho. Compressed sensing. IEEE Trans. on Information Theory, 2006, 52(4): 1289–1306.

[21] Lei Xu and Qilian Liang, ” Compressive Sensing Using Singular Value Decomposition,” WASA'10 Proceedings of the 5th international conference on Wireless algorithms, systems, and applications, pp. 338–342, 2010.

[22] “Draft ITU-T recommendation and final draft international standard of joint video specification (ITU-T Rec. H.264/ISO/IEC 14 496-10 AVC),” in Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, March 2003.

[23] ISO/IEC 14496-2: “Information technology-coding of audio visual objects-part 2: visual,” Geneva, 2000.

[24] J. Ostermann, J. Bormans, P. List, D. Marpe, M. Narroschke, F. Pereira, T. Stockhammer and T. Wedi, “Video coding with H.264/AVC：tools, performance, and complexity,” IEEE on Circuits and Systems Magazine, vol. 4, pp. 7-28, 2004.

[25] I Candes, E., Tao, T. “Near-optimal signal recovery from random projections: universal encoding strategies,” IEEE Trans. on Inform. Theory, 5406–5425 (December 2006).

[26] J. Ostermann, J. Bormans, P. List, D. Marpe, M. Narroschke, F. Pereira, T. Stockhammer and T. Wedi, “Video coding with H.264/AVC：tools, performance, and complexity,” IEEE on Circuits and Systems Magazine, vol. 4, pp. 7-28, 2004.

[27] 戴顯權, 多媒體通訊, 紳藍出版社, 5, 2003。

[28] 楊永欽，在H.264 下的快速Intra Mode 演算法，私立中原大學，2007。

[29] T. Wedi, and H.G. Musmann,”Motion- and aliasing-compensated prediction for hybrid video coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, pp. 577-587, July 2003.

[30] H. valvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, ”Low- Complexity Transform and Quantization in H.264/AVC,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, No. 7, July 2003.

[31] Million, Elizabeth. The Hadamard Product . Retrieved 2 January 2012.

[32] Santosa, F., Symes, W.W. “Linear inversion of band-limited reflection seismograms,” SIAM J. Sci. Statist. Comput., 7(4), pp. 1307–1330 (1986).

[33] Golub, G.H., Van Loan, C.F.: Matrix Computations. John Hopkins University Press, Maryland (1996)

[34] Joel A. Tropp, “Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit,” IEEE TRANSACTIONS ON INFORMATION THEORY, Vol. 53, pp. 4655-4666, Dec. 2007.

[35] D. Needell, J. Tropp. “CoSaMP: iterative signal recovery from incomplete and inaccurate samples,” Applied Computational Harmonic Analysis, Vol. 26, pp. 301-321, May 2009.

[36] S. Ji, Y. Xue, L. Carin “Bayesian compressive sensing,” IEEE Trans. on Signal Processing, Vol. 56, pp. 2346–2356, June 2008.

[37] M. Fornasier, H. Rauhut. Iterative thresholding algorithms. Applied and Computational Harmonic Analysis, Vol. 25, pp. 187–208, 2008

[38] T. Blumensath, M. E. Davies. Gradient pursuits. IEEE Trans. on Signal Processing, Vol. 56, pp. 2370–2382, 2008

[39] D. Donoho. For most large underdetermined systems of linear equations, the minimal ell-1 norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 2006, 59(5): 797–829.

[40] D. Donoho. For most large underdetermined systems of linear equations, the minimal ell-1 norm near-solution approximates the sparsest near-solution. Communications on Pure and Applied Mathematics, 2006, 59(7): 907–934.

[41] S. Boyd, L. Vandenberghe. Convex optimization. Cambridge, MA: Cambridge University Press, 2004.

[42] E. J. Cand`es, J. Romberg, T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information” IEEE Trans. on Information Theory, 2006, 52(2): 489–509.

[43] E. J. Cand`es, J. Romberg, “Quantitative robust uncertainty principles and optimally sparse decompositions”, Foundations of Computational Mathematics, 2006, 6(2): 227–254.

[44] Huihui Bai ,AnhongWang and Mengmeng Zhang, “Compressive       Sensing for DCT Image”, 2010 International Conference on Computational Aspects of Social Networks, pp. 378-381, Sep. 2010.

[45] Emmanuel J. Candes and Michael B. Wakin, “An Introduction To Compressive Sampling”, IEEE SIGNAL PROCESS MAG, Vol.25 (2), pp. 21-30, MAR. 2008

[46] JUSTIN ROMBERG, “Compressive sensing by random convolution”, SIAM Journal on Imaging Science, Vol.2,pp.1098-1128, July 2009.