臺灣博碩士論文加值系統

在本篇論文中，我們提出一個以物件導向的影像壓縮標準MPEG-4為基礎的數位監控系統，並使用軟體程式實現。

由於MPEG-4系統的高計算複雜度，為達到即時壓縮，我們提出一些快速MPEG-4演算法來取代原始的演算法，這些快速演算法包含形狀編碼（Shape coding）、物件追蹤（Object tracking）及離散餘弦轉換（discrete cosine transform）。形狀編碼使用entropy及差值的方式來編碼。物件追蹤則是利用形狀與物件內容的相關性來降低移動估測的運算量及花費時間。而離散餘弦轉換運算在MPEG-4編碼中佔了相當大的比重，我們提出一個使用行列的快速演算法來近似。

藉著結合這些快速演算法，在使用Intel Pentium-4, 3.2GHz的硬體下，此架構在非即時的情況下，處理速度可以達到每秒15~25張畫面，當使用攝影機即時取樣及編碼下，速度可以達到每秒2~5張畫面。

In this thesis, we present the content-based video coding, MPEG-4 for video surveillance system using software programming. Due to high computational complexity in MPEG-4 system, we proposed some fast MPEG-4 algorithms for MPEG-4 encoding in order to real-time implementation. The fast algorithms include shape coding, object tracking and DCT (discrete cosine transform) computations. The shape coding employs the differential code consisting of entropy code. The object tracking uses the relativity of shape and content information to reduce computational requirements and time of motion estimation. The DCT computation also occupies heavy work in MPEG-4 encoder. We proposed a simple fast algorithm using row/column approach. By combination of these fast algorithms, under the CPU using Intel Pentium-4, 3.2GHz, the encoder can realize 15~25 frames per second in off-line. As for real-time camera sampling and encoding, the frame rate can achieve about 2~5 frames.

目錄
項　　　目 頁次
中文摘要 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -i
英文摘要 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ii
誌謝 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -iii
目錄 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - iv
表目錄 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - vi
圖目錄 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -vii
第一章、 緒論- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -1
1.1 前言- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -1
1.2 研究動機 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1
1.3 論文組織 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2
第二章、 MPEG-4標準- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -3
2.1 MPEG-4簡介- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -3
2.2 MPEG-4系統- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -5
2.3 MPEG-4影像壓縮技術- - - - - - - - - - - - - - - - - - - - - - - - - -6
2.3.1 動態影像切割技術- - - - - - - - - - - - - - - - - - - - - - -10
2.3.2 形狀編碼- - - - - - - - - - - - - - - - - - - - - - - - - - -12
2.3.3 動態估測- - - - - - - - - - - - - - - - - - - - - - - - - - -16
2.3.4 離散餘弦轉換- - - - - - - - - - - - - - - - - - - - - - - - -25
第三章、 快速MPEG-4演算法- - - - - - - - - - - - - - - - - - - - - - - - - - 26
3.1 物件切割演算法- - - - - - - - - - - - - - - - - - - - - - - - - - - 26
3.2 形狀編碼- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 26
3.2.1 差值鏈結編碼- - - - - - - - - - - - - - - - - - - - - - - - -26
3.2.2 模擬- - - - - - - - - - - - - - - - - - - - - - - - - - - - -28
3.3 動態估測 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -30
3.3.1 二進位輪廓外型移動追蹤- - - - - - - - - - - - - - - - - - - -30
3.3.2 模擬- - - - - - - - - - - - - - - - - - - - - - - - - - - - -36
3.3.3 灰階內容移動尋找- - - - - - - - - - - - - - - - - - - - - - -47
3.3.4 模擬- - - - - - - - - - - - - - - - - - - - - - - - - - - - -49
3.4 離散餘弦轉換- - - - - - - - - - - - - - - - - - - - - - - - - - - - 54
3.4.1 快速離散餘弦轉換- - - - - - - - - - - - - - - - - - - - - - -54
3.4.2 模擬- - - - - - - - - - - - - - - - - - - - - - - - - - - - -58
第四章、 MPEG-4整合與模擬- - - - - - - - - - - - - - - - - - - - - - - - - - 59
4.1 取樣系統 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -59
4.2 系統整合 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -61
4.3 模擬系統架構- - - - - - - - - - - - - - - - - - - - - - - - - - - - 63
4.4 模擬- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 65
第五章、 結論- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 74
參考文獻 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 75

表目錄
表 3.1 差值鏈結編碼的霍夫曼編碼表- - - - - - - - - - - - - - - - - - - - - 27
表 3.2 各種形狀編碼演算法位元數比較圖（byte/frame）- - - - - - - - - - - - 29
表 3.3 二進位外型輪廓追蹤模擬效率表（weather） - - - - - - - - - - - - - - 41
表 3.4 二進位外型輪廓追蹤模擬效率表（irene） - - - - - - - - - - - - - - - 41
表 3.5 二進位外型輪廓追蹤模擬效率表（TV） - - - - - - - - - - - - - - - - -41
表 3.6 灰階內容移動尋找模擬效率表（weather）- - - - - - - - - - - - - - - -49
表 3.7 灰階內容移動尋找模擬效率表（Irene）- - - - - - - - - - - - - - - - -49
表 3.8 灰階內容移動尋找模擬效率表（TV）- - - - - - - - - - - - - - - - - - 50
表 3.9 DCT的餘弦係數- - - - - - - - - - - - - - - - - - - - - - - - - - - -56
表 3.10 IDCT的餘弦係數表- - - - - - - - - - - - - - - - - - - - - - - - - - 57
表 3.11 快速離散餘弦轉換模擬的時間與MSE（CIF 352×288）- - - - - - - - - - - 58
表 4.1 PANASONIC WV-CP470攝影機規格表- - - - - - - - - - - - - - - - - - - 60
表 4.2 IEI IVC-200G影像擷取卡規格表 - - - - - - - - - - - - - - - - - - - -61
表 4.3 off-line模擬結果- - - - - - - - - - - - - - - - - - - - - - - - - - 66
表 4.4 real-time模擬結果- - - - - - - - - - - - - - - - - - - - - - - - - -70


圖目錄
圖 2.1 MPEG-4在物件上的運用- - - - - - - - - - - - - - - - - - - - - - - - -4
圖 2.2 MPEG-4基本編碼流程- - - - - - - - - - - - - - - - - - - - - - - - - -7
圖 2.3 一般視訊物件平面的編碼架構- - - - - - - - - - - - - - - - - - - - - -7
圖 2.4 視訊物件與各種性質的巨區塊- - - - - - - - - - - - - - - - - - - - - -8
圖 2.5 AC/DC估測（AC/DC Prediction） - - - - - - - - - - - - - - - - - - - -9
圖 2.6 Zig-Zag Scan- - - - - - - - - - - - - - - - - - - - - - - - - - - - 10
圖 2.7 Grandma的原始影像與二元α平面- - - - - - - - - - - - - - - - - - - - 13
圖 2.8 CAE演算法- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -14
圖 2.9 Grandma 之輪廓- - - - - - - - - - - - - - - - - - - - - - - - - - - 15
圖 2.10 移動向量預報- - - - - - - - - - - - - - - - - - - - - - - - - - - - 16
圖 2.11 區塊比對法的程序- - - - - - - - - - - - - - - - - - - - - - - - - - 18
圖 2.12 Block、Search Area 與Frame示意圖- - - - - - - - - - - - - - - - - - 18
圖 2.13 全域搜尋演算法示意圖- - - - - - - - - - - - - - - - - - - - - - - - 19
圖 2.14 三步搜索演算法示意圖- - - - - - - - - - - - - - - - - - - - - - - - 21
圖 3.1 鏈結編碼的變數定義- - - - - - - - - - - - - - - - - - - - - - - - - 27
圖 3.2 形狀編碼模擬輸入圖- - - - - - - - - - - - - - - - - - - - - - - - - 28
圖 3.3 當物件邊緣為垂直方向且左右移動時- - - - - - - - - - - - - - - - - - 30
圖 3.4 當物件邊緣為水平方向且上下移動時- - - - - - - - - - - - - - - - - - 31
圖 3.5 當物件為斜度移動時（mvx=6，mvy=-3）- - - - - - - - - - - - - - - - -31
圖 3.6 當物件為斜度移動時（mvx=-3，mvy=-4）- - - - - - - - - - - - - - - - 32
圖 3.7 當物件為斜度移動時（mvx=3，mvy=5）- - - - - - - - - - - - - - - - - 32
圖 3.8 當物件移動過大時，物件斜率為正- - - - - - - - - - - - - - - - - - - 32
圖 3.9 當物件移動過大時，物件斜率為負- - - - - - - - - - - - - - - - - - - 33
圖 3.10 搜索程序圖- - - - - - - - - - - - - - - - - - - - -- - - - - - - - -34
圖 3.11 搜索程序舉例說明圖- - - - - - - - - - - - - - - - - - - - - - - - - 35
圖 3.12 二進位輪廓外型移動追蹤模擬輸入圖（weather）- - - - - - - - - - - - -36
圖 3.13 二進位輪廓外型移動追蹤模擬輸入圖（irene）- - - - - - - - - - - - - -36
圖 3.14 二進位輪廓外型移動追蹤模擬輸入圖（TV）- - - - - - - - - - - - - - - 37
圖 3.15 全域搜索法輸出圖（weather）- - - - - - - - - - - - - - - - - - - - -37
圖 3.16 全域搜索法輸出圖（irene）- - - - - - - - - - - - - - - - - - - - - -37
圖 3.17 全域搜索法輸出圖（TV）- - - - - - - - - - - - - - - - - - - - - - - 38
圖 3.18 三步搜索法輸出圖（weather）- - - - - - - - - - - - - - - - - - - - -38
圖 3.19 三步搜索法輸出圖（irene）- - - - - - - - - - - - - - - - - - - - - -38
圖 3.20 三步搜索法輸出圖（TV）- - - - - - - - - - - - - - - - - - - - - - - 39
圖 3.21 二進位輪廓外型移動追蹤法輸出圖（weather）- - - - - - - - - - - - - -39
圖 3.22 二進位輪廓外型移動追蹤法輸出圖（irene）- - - - - - - - - - - - - - -39
圖 3.23 二進位輪廓外型移動追蹤法輸出圖（TV）- - - - - - - - - - - - - - - - 40
圖 3.24 錯誤點數曲線圖（weather）- - - - - - - - - - - - - - - - - - - - - -42
圖 3.25 錯誤點數曲線圖（irene）- - - - - - - - - - - - - - - - - - - - - - -42
圖 3.26 錯誤點數曲線圖（TV）- - - - - - - - - - - - - - - - - - - - - - - - 43
圖 3.27 比較次數圖（weather）- - - - - - - - - - - - - - - - - - - - - - - -43
圖 3.28 比較次數圖（irene）- - - - - - - - - - - - - - - - - - - - - - - - -44
圖 3.29 比較次數圖（TV）- - - - - - - - - - - - - - - - - - - - - - - - - - 44
圖 3.30 MSE曲線圖（weather）- - - - - - - - - - - - - - - - - - - - - - - - 45
圖 3.31 MSE曲線圖（irene）- - - - - - - - - - - - - - - - - - - - - - - - - 45
圖 3.32 MSE曲線圖（TV）- - - - - - - - - - - - - - - - - - - - - - - - - - -46
圖 3.33 物件內容移動估測情況參考區塊- - - - - - - - - - - - - - - - - - - - 47
圖 3.34 灰階內容動態估測流程圖- - - - - - - - - - - - - - - - - - - - - - - 48
圖 3.35 PSNR曲線圖（weather）- - - - - - - - - - - - - - - - - - - - - - - -50
圖 3.36 PSNR曲線圖（irene）- - - - - - - - - - - - - - - - - - - - - - - - -51
圖 3.37 PSNR曲線圖（TV）- - - - - - - - - - - - - - - - - - - - - - - - - - 51
圖 3.38 加減法次數曲線圖（weather）- - - - - - - - - - - - - - - - - - - - -52
圖 3.39 加減法次數曲線圖（irene）- - - - - - - - - - - - - - - - - - - - - -52
圖 3.40 加減法次數曲線圖（TV）- - - - - - - - - - - - - - - - - - - - - - - 53
圖 3.41 利用兩個1D-DCT實現2D-DCT - - - - - - - - - - - - - - - - - - - - - -55
圖 4.1 PANASONIC WV-CP470攝影機- - - - - - - - - - - - - - - - - - - - - - 59
圖 4.2 IEI IVC-200G影像擷取卡- - - - - - - - - - - - - - - - - - - - - - - 60
圖 4.3 MPEG-4整合架構圖- - - - - - - - - - - - - - - - - - - - - - - - - - 62
圖 4.4 模擬系統架構圖- - - - - - - - - - - - - - - - - - - - - - - - - - - 63
圖 4.5 實際模擬系統攝影圖- - - - - - - - - - - - - - - - - - - - - - - - - 64
圖 4.6 程式介面- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 64
圖 4.7 off-line模擬10秒的PNSR曲線圖- - - - - - - - - - - - - -- - - - - - -66
圖 4.8 off-line模擬100秒的PNSR曲線圖- - - - - - - - - - - - - - - - - - - -67
圖 4.9 off-line模擬100秒的PNSR曲線圖- - - - - - - - - - - - - - - - - - - -67
圖 4.10 off-line模擬之原始影像- - - - - - - - - - - - - -- - - - - - - - - -68
圖 4.11 off-line模擬之重建影像- - - - - - - - - - - - - -- - - - - - - - - -68
圖 4.12 off-line模擬之物件輪廓- - - - - - - - - - - - - -- - - - - - - - - -69
圖 4.13 off-line模擬之物件內容- - - - - - - - - - - - - -- - - - - - - - - -69
圖 4.14 real-time模擬10秒的PNSR曲線圖- - - - - - - - - - - - - - - - - - - -71
圖 4.15 real-time模擬100秒的PNSR曲線圖- - - - - - - - - - - - - - - - - - - 71
圖 4.16 real-time模擬之原始影像- - - - - - - - - - - - - -- - - - - - - - - 72
圖 4.17 real-time模擬之重建影像- - - - - - - - - - - - - -- - - - - - - - - 72
圖 4.18 real-time模擬之重建物件輪廓- - - - - - - - - - - - - -- - - - - - - 73
圖 4.19 real-time模擬之重建物件內容- - - - - - - - - - - - - - - - - - - - -73

參 考 文 獻
[1] ISO/IEC JTC1 IS 11172, Coding of Moving Picture and Coding of Continuous Audio for Digital Storage Media up to 1.5Mbps, 1992.
[2]ISO/IEC JTC1/SC29/WG11 Draft CD 13818-2, General Coding of Moving Pictures and Associated, ITU-T Recommendation H.262 Committee Draft, 1994.
[3]MPEG-4 Video Group. “Generic Coding of Audio-Visual Object: Part 2 – Visual 14496-2,” ISO/IEC JTC1/SC29/WG11 N2502a, FDIS, Atlantic City, Oct. 1998.
[4] ITU-T Recommendation H.261: “Video Codec for Audiovisual Services at p×64 kbits,” Mar. 1993.
[5] ITU-T Recommendation H.263（1996）: “Video coding for low bitrate communication”.
[6]ISO/IEC JTC1/SC29/WG11 N3312, “MPEG-4 Video Verification Model version 16.0,” Mar. 2000.
[7]T. Meier and K. N. Ngan, “Video Segmentation for Content-Based Coding” IEEE Trans. Circuits Systems. Video Technology, VOL. 9, No 8, pp. 1190-1203, Dec. 1999.
[8]L. Vincent and P. Soille,“Watershed in digital space: An efficient algorithm based on immersion simulations” IEEE Trans. Pattern Analysis Machine Intel., Vol. 13,pp 583-598, June 1991.
[9]D. Wang,“Unsupervised Video Segmentation Based on Watersheds and Temporal Tracking,”IEEE Trans. Circuits Systems for Video Technology, Vol. 8, On. 5, pp 539-546, Sept. 1998.
[10]M.J. Chen, Y.P. Hsieh, and Y.P. Wang, “Multi-resolution shape coding algorithm for MPEG-4,” IEEE Trans. Consumer Electronics, Vol. 46 3, pp. 505-13, Aug. 2000.
[11] N. Brady, F. Bossen, and N. Murphy, “Context-based arithmetic encoding of 2D shape sequences.” in Proc. of IEEE International Conference On Image Processing, Vol. 1, pp. 29-32, 1997.
[12]J.W. Stroming, Y. Kang, T.S. Huang, and S.M. Kang, “New architectures for modified MMR shape coding,” ISCAS ’97, Vol. 2, pp. 1205-8, 1997.
[13]W.M. Yio, A.H. Sadka, and A.M. Kondoz, “Multi-rate variable-Quality VOP shape coder,” IEEE International Conference on Multimedia Computing and System, pp. 46-50, 1999.
[14]K.J. O’Connell, “Object-adaptive vertex-based shape coding method,” IEEE Trans. On Circuits and System for Video Technology, Vol. 7, NO.1, pp. 251-255, 1997.
[15]R.J. Qian, and M.I. Sezan, “Content-Scalable Shape Representation and coding,” Vol. 2, NO. 641, pp. 819-823, ICIP 1997.
[16] J. Kim and B.L. Evans, “Predictive shape coding using generic polygon approximation,” in Proc. ISCAS ’98. Monterrey, CA, to be published.
[17]T. Koga, K. Iinuma, A. Hirano, and T. Ishiguro, “Motion-compensated interframe coding for video conferencing,” in Nat. Telecommun. Conf., pp. G5.3.1-G5.3.5, 1981.
[18]X. Lee, Y.Q. Zhang, “A fast hierarchical motion-compensation scheme for video coding using block feature matching,” IEEE Trans. Circuits and System for Video Technology On, pp. 627-635, Vol. 6 Issue 6, Dec. 1996.
[19]B. Natarajan, V. Bhaskaran, and K. Konstantinids, “Low-Complexity Block-based Motion Estimation via One-Bit Transforms,” IEEE Trans. On Circuits and System for Video Technology, Vol. 7, NO. 4, pp. 702-706, Aug. 1997.
[20]X. Song, T. Chiang, X. Lee, and Y.Q. Zhang, “New fast binary pyramid motion estimation for MPEG-2 and HDTV encoding,” IEEE Trans. On Circuits and System for Video Technology, Vol. 10, NO. 7, pp. 1015-1028, Oct. 2000.
[21]J.H. Luo, C.N. Wang, and T. Chiang, “A novel all binary motion estimation（ABME）,” IEEE Circuits and System, ISCAS 2002, IEEE Int. Symposium on, Vol. 2, pp. 26-29, May 2002.
[22] G. K. Wallace, “ The JPEG still picture compression standard,” Commun. ACM, Vol. 34, No. 4, pp. 59-63, April 1991.
[23] 蕭政弘, “固定式攝影頭之影像物件切割演算法與晶片設計,” 2002高雄第一科技大學電腦與通訊工程研究所碩士論文.
[24]Y.T. Hwang, Y.C. Wang; and S.S. Wang, “An efficient shape coding scheme and its codec design,” IEEE Workshop on Signal Processing Systems, pp. 225-232, Sept. 2001.
[25] 呂長霖, “H.261視訊編解碼器中INTRA模式之系統設計,”2002高雄第一科技大學電腦與通訊工程研究所碩士論文.
[26] B.G Lee, “A new algorithm to compute the discrete cosine transform,” IEEE Trans. Acoust., Speech Signal Process., ASSP-32, (6) pp. 1243-1245, 1984.
[27] Y. Jeong, I. Lee, H.S. Kim, and K.T. Park, “Fast DCT algorithm with fewer multiplication stages,” IEE Electronics Letters, Vol. 34, Issue 8, pp. 723-724, Apr. 16, 1998.