臺灣博碩士論文加值系統

在目前有限的頻寬與儲存空間下，視訊影像壓縮是勢在必行的，因此我們針對視訊壓縮標準，如H.26x和MPEGx標準，內部運算複雜度最高的移動估測(Motion Estimation)提出運算量少而且不會造影像品質嚴重失真的演算法。由於計算複雜度越高的演算法會需要越大量的運算時間，這樣所造成的結果並不符合現代視訊壓縮在時間上的即時需求，因此許多快速的區塊匹配演算法(Block Matching Algorithm)已經被提出，其目的是為了減少傳統全區域搜尋演算法(Full Search Block-Matching Algorithm)所產生的大量計算，但是大部分的快速運算的區塊匹配演算法都會造成較嚴重的影像失真，為了解決上述的問題，我們提出利用動態選擇代表性像素的部分失真搜尋演算法(Partial Distortion Search Algorithm by Dynamically Selecting the Representative Pixels，簡稱PDS-DS)。利用動態選擇代表性像素來提前排除不合適的候選區塊(Candidate Block)，加上利用部份失真演算法(Partial Distortion Search Algorithm，PDS)除了可以減少運算量之外還可以解決影像嚴重失真的問題，因此本論文提出的 PDS-DS 演算法符合現代視訊壓縮標準所強調的失真少、計算時間短的需求。

Motion estimation and Motion compensation are used in the compression standard such as MGEG x and H.26x in order to eliminate the temporal redundancy of the video sequences. But the techniques of the motion estimation need a large amount of computation to complete and waste a lot of time. The long time of the compression is not suitable in the present day. So, many fast block matching algorithms have been proposed in order to solve this problem. But most of the fast block matching algorithms degrade the image quality.
In this thesis, we proposed the improved method for partial distortion algorithm to increase the speed of the motion estimation and avoid to make the quality of the image decrease. In our algorithm, the scan way of dynamically selecting is proposed. Using the scan way of dynamically selecting can find efficiently the more representative pixels. In our method, the unsuitable candidate blocks will be eliminated early. And using the scan way to find the center of the search windows, the computation complexity of the block matching will be reduced. Moreover, we have modified two skills in HGPDS. The skills are the early termination skill and spiral scan in search window respectively. The modifications make the algorithm faster. Experiments have showed that our method has better performance than previous algorithms.

第一章 緒論 - 1 -
1.1 簡介 - 1 -
1.2 研究動機與目的 - 5 -
1.3 論文架構 - 5 -
第二章 視訊編碼介紹 - 7 -
2.1 視訊壓縮原理簡介 - 7 -
2.1.1 移動估測與移動補償原理 - 8 -
2.1.2 離散餘弦轉換(Discrete Cosine Transform) - 10 -
2.1.3 量化(Quantization) - 11 -
2.1.4 可變長度編碼(Variable Length Coding，VLC) - 12 -
2.2 色彩空間轉換 - 12 -
2.3 視訊編碼標準常用的視訊格式 - 13 -
2.4 移動向量預測技巧 - 14 -
第三章 常見的移動估測技術討論 - 16 -
3.1 移動估測演算法的條件設定分析 - 17 -
3.2 快速搜尋區塊比對演算法 - 18 -
3.2.1 三步驟搜尋演算法 - 20 -
3.2.2 鑽石搜尋演算法 - 22 -
3.3快速全區域搜尋區塊比對演算法 - 25 -
3.3.1 連續性消去演算法 - 26 -
3.3.2 部分失真搜尋演算法 - 30 -
第四章 動態選擇代表性像素的部分失真搜尋演算法 - 38 -
4.1 動態選擇掃描法的分析 - 40 -
4.2 減少計算複雜度的機制 - 41 -
4.2.1 延伸螺旋狀搜尋的機制 - 42 -
4.2.2 延伸提前終止的機制 - 44 -
4.3 PDS-DS 演算法的說明 - 45 -
第五章 實驗結果與分析 - 48 -
第六章 結論 - 82 -
參考文獻 - 84 -

[1] Tae Gyoung Ahn, Yong Ho Moon and Jae Ho Kim, “An improved multilevel successive elimination algorithm for fast full-search motion estimation,” in Proceedings of 2003 International Conference on Image Processing, Vol. 2, pp. 14-17, 2003.
[2] Junavit Chalidabhongse, C. C. Jay Kuo, and Senior Member, “Fast motion vector estimation using multiresolution-spatio-temporal correlations,” IEEE Trans. on Circuits and Systems for Video Technology, Vol. 7, no. 3, pp. 477-488, June.1997.
[3] M.-J. Chen, L –G. Chen and T.-D. Chiueh, “One-dimensional full search motion estimation algorithm for video coding,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 4, No. 5, pp. 504-509,1994.
[4] C.-K. Cheung and L.-M Po, “Normalized partial distortion search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 10, No. 3, pp. 417-422, 2000.
[5] C.-H. Cheung and L. M. Po, “Adjustable partial distortion search algorithm for fast block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 13, No. 1, pp. 100-110, 2003.
[6] Y. L. Chan and W. C. Siu, “An adaptive partial distortion search for block motion estimation,” in Proceedings of 2003 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’03), Vol. 3, pp. 153-156, 2003.
[7] Y. L. Chan and W. C. Siu, “New adaptive pixel decimation for block motion vector estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 6, No.1, pp. 113-118, 1996.
[8] Y. L. Chan, K. C. Hui, and W. C. Siu, “Fast search algorithm for edge-oriented block matching algorithm,” in Proceedings of 2001 International Symposium on Intelligent Multimedia, Video and Speech, pp. 225-228, 2001.
[9] X. Q. Gao, C. J. Duanmu and C. R. Zou, “A multilevel successive elimination algorithm for block matching motion estimation,” IEEE Trans. Image Processing, Vol. 9, issue 3, pp. 501-504, 2000.
[10] W. G. Hong and T. M. Oh, “Enhanced partial distortion search algorithm for block motion estimation,” Electronics Letters, Vol. 39, No. 15, pp. 1112-1113, 2003.
[11] W. G. Hong, T. M. Oh, and S. J. Ko, “Fast motion-estimation algorithm based on progressive partial norm matching,” Electronics Letters, Vol. 37, No. 14, pp. 890-892, 2001.
[12] W.-G. Hong and T. M. Oh, “Sorting-based partial distortion search algorithm for motion estimation,” Electronics Letters, Vol. 40, No. 2, pp. 113-115, 2004.
[13] J. R. Jain and A. K. Jain, “Displacement measurement and its application in interframe image coding,” IEEE Transactions on Communications, Vol. 29, No. 12, pp. 1799-1808, 1981.
[14] Faouzi Kossentini, Yuen-Wen Lee, Mark J. T. Smith, and Rabab K. Ward, “Predictive RD optimized motion estimation for very low bit-rat video coding,” IEEE journal on Selected Areas in Communications, Vol. 15, issue 9, pp. 1752-1763, 1997.
[15] T. Koga, K. Iinuma, A. Hirano, Y. Iijima and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” in Proceedings of National Telecommunications Conference, pp. 961-965, 1981.
[16] L.-K. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 6, No. 4, pp. 419–422, 1996.
[17] W. Li and E. Salari, “Successive elimination algorithm for motion estimation,” IEEE Transactions on Image Processing, Vol. 4, No. 1, pp. 105-107, 1995.
[18] R. Li, B. Zeng and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 4, No. 4, pp. 438-442, 1994.
[19] J. H. Lee and J. B. Ra, “Efficient motion estimation using edge-based binary block-matching and refinement based on motion vector correlation,” in Proceedings of 2001 International Conference on Image Processing, Vol. 2, pp. 957-960, 2001.
[20] Y. K. Wang, Y. Q. Wang, and H. Kuroda, “A globally adaptive pixel-decimation algorithm for block-motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 10, No. 6, pp. 1006-1011, 2000.
[21] Y. K. Wang, Y. Q. Wang, and H. Kuroda, “A novel adaptive pixel decimation for block motion vector estimation,” IEICE Transactions on Communications, Vol. E82-B, No. 1, pp. 188-191, 1999.
[22] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Transactions on Image Processing, Vol. 9, No. 2, pp. 287-290, 2000.