臺灣博碩士論文加值系統

(Motion Estimation) 動態估測乃是視訊壓縮處理上重要的一環，尤其當視訊將透過網路來傳輸，且視訊是具有即時性的需求時, 則視訊資料壓縮處理的速度及被還原後的影像品質是否良好，是必須考慮的要素。動態估測的運算量佔整個壓縮過程的大部份，因此若是能夠在動態估測處理的過程中，有效的將影像品質保持住，且大大的降低整個的運算量，如此將可達到即時性的需求。我們以快速三步搜尋法(FTSS)[2]為基礎，並以視訊會議類的影像為基礎, 發展出更快速的搜尋法，並提出經由移動物體邊界之預估來設定較佳之起始搜尋點(boundary condition for initial searching points )，以使得搜尋點減少且增加影像品質。
本論文以實現改良快速三步搜尋法(FTSS)[1]為主, 我們引用了新三步搜尋法(NTSS)[3](center biased)的觀念及有效四步搜尋法(E4SS)[4]之參考前一個區塊的移動向量當作起始點的做法, 運用在快速三步法(FTSS)[2]上, 逐步判斷可能方向去搜尋的做法,並增加更多的條件來判斷,使其搜尋過程更加準確且減少搜尋點數, 以此實作出baseline, history baseline (HBA)及history fast three step search (HFTSS).另外引用由鄰近區塊的移動向量中值來決定起始點的做法[10], 以及在可能區域搜尋時利用門檻值來降低搜尋點數來實作出High-speed four-step search (HSFSS)。最後提出經由移動物體邊界之預估來設定較佳之起始搜尋點(boundary condition for initial searching points )的方法,在將此方法運用於 (HFTSS)及 (HSFSS),經實驗證明運用於(HFTSS)可獲得相當好的影像品質。

Motion Estimation is a key process on video compression. This thesis is starting from the Fast Three Step Search (FTSS)[2] algorithm, and develops faster searching algorithms to apply on videoconference. A newly developed of error screen method is called a boundary algorithm to get more accuracy decision of initial searching points, and it can hold a better quality and to reduce redundant searching points.
This research is mainly to improve the Fast Three Step Search (FTSS)[2] algorithm, by taking a series of algorithms, such as the center-biased concept of New Three Step Search (NTSS)[3] algorithm, the Efficient Four Step Search (E4SS)[4] algorithm for setting initial searching point, and use of two techniques application on our fast search algorithms. The new algorithm is firstly to use the median value of motion vectors [10] as set the initial searching point, in a possible searching area. This method decreases the searching points, and performs the high-speed four-step search (HSFSS) algorithm. Finally we propose the algorithm for boundary condition for initial searching points, and then apply on history fast three-step search (HFTSS) and high-speed four-step search (HSFSS), Finally according to experiment result we prove the history fast three step search (HFTSS) algorithm can obtain good performance.

List of CONTENTS
ACKNOWLEDGEMENTS I
摘 要 II
ABSTRACT IV
LIST OF CONTENTS VI
FIGURE LIST VIII
TABLE LIST X
CHAPTER 1 INTRODUCTION 1
1.1 THE MOTIVATION 1
1.2 THE PROPOSED METHODS 2
1.3 ORGANIZATION OF THIS THESIS 3
CHAPTER 2 THE MOTION ESTIMATION IN VIDEO 4
2.1 THE H.261 IMAGE COMPRESS AND MOTION ESTIMATION 4
2.2 THE MOTION ESTIMATION BETWEEN FRAMES 9
2.3 THE MAJOR FACTORS IN SEARCH 13
CHAPTER 3 14
THE BLOCK MATCHING SEARCH ALGORITHMS 14
3.1 THREE STEP SEARCH ALGORITHM 14
3.2 NEW THREE STEP SEARCH ALGORITHM 16
3.3 EFFICIENT FOUR STEP SEARCH ALGORITHM 19
3.4 FAST THREE STEP SEARCH ALGORITHM 21
CHAPTER 4 THE PROPOSED FAST SEARCH ALGORITHMS 25
4.1 THE BASELINE OF PROPOSED 26
4.2 HISTORY BASELINE APPROACH (HBA) 37
4.3 HIGH SPEED FOUR STEP SEARCH ALGORITHM (HSFSS) 41
4.4 HISTORY FAST THREE STEP SEARCH ALGORITHM (HFTSS) 45
4.5 BOUNDARY CONDITION FOR INITIAL SEARCHING POINT 49
CHAPTER 5 EXPERIMENT RESULT AND ANALYSIS 52
CHAPTER 6 CONCLUSION AND FUTURE WORK 60
6.1 CONCLUSION 60
6.2 FUTURE WORK 62
REFERENCE 63
APPENDIX 66
COMPUTING SAD USING DIFFERENT NUMBER OF BITS 66
RESULT ANALYSIS 71

[1] Her-Ming Jong, Liang-Gee, Tzi-Dar Chiueh, “Parallel architectures for 3-step hierarchical search block-matching algorithm”, Circuits and Systems for Video Technology, IEEE Transactions on, Volume: 4 Issue: 4, Aug. 1994 Page(s): 407 —416
[2] Jong-Nam Kim, Tae-Sun Choi, “A fast three-step search algorithm with minimum checking points using unimodal error surface assumption”, Consumer Electronics, IEEE Transactions on, Volume: 44 Issue: 3, Aug. 1998 Page(s): 638 —648
[3] Reoxiang Li, Bing Zeng, Liou, M.L, “A new three-step search algorithm for block motion estimation”, Circuits and Systems for Video Technology, IEEE Transactions on, Volume: 4 Issue: 4, Aug. 1994 Page(s): 438 —442
[4] Kuan-Tsang Wang, Oscal T.-C. Chen, “Motion estimation using an efficient four-step search method”, Circuits and Systems, 1998. ISCAS '98. Proceedings of the 1998 IEEE International Symposium on, Volume: 4, 1998 Page(s): 217 -220 vol.4
[5] Jianhua Lu, Ming L. Liou, “A simple and efficient search algorithm for block-matching motion estimation”, Circuits and Systems for Video Technology, IEEE Transactions on, Volume: 7 Issue: 2, April 1997 Page(s): 429 —433
[6] Mon-Chau Shie, Wen-Hsien Fang, Kuo-Jui Hung, Feipei Lai, “Fast block motion estimation using adaptive simulated annealing”, Circuits and Systems, 1998. IEEE APCCAS 1998. The 1998 IEEE Asia-Pacific Conference on, 1998 Page(s): 607 —610
[7] Jae-Yeal Nam, Jae-Soo Seo, Jin-Suk Kwak, Myoung-Ho Lee, Yeong Ho Ha, “New fast-search algorithm for block matching motion estimation using temporal and spatial correlation of motion vector”, Consumer Electronics, IEEE Transactions on, Volume: 46 Issue: 4, Nov. 2000 Page(s): 934 —942
[8] Shen Li, Wei-Pu Xu, Hui Wang, Nan-Ning Zheng, “A novel fast motion estimation method based on genetic algorithm”, Image Processing, 1999. ICIP 99. Proceedings. 1999 International Conference on, Volume: 1, 1999 Page(s): 66 -69 vol.1
[9] Leng wehasarit, K. Ortega, “Probabilistic partial-distance fast matching algorithms for motion estimation”, A. Circuits and Systems for Video Technology, IEEE Transactions on, Volume: 11 Issue: 2, Feb 2001 Page(s): 139 —152
[10] Jae-Yong Kim and Sung-Bong Yang, “An Efficient Hybed Search Algorithm for Fast Block Matching in Video Coding”, Dept. of computer Science, Yonsei University, Seoul 120-749, Korea
[11] Hsien-Hsi Hsieh and Yeong Kang Lai, “A Novel Fast Motion Estimation Algorithm Using Fixed Subsampling Pattern and Multiple Local Winners Search”, Department of Computer Science and Information Engineering National Dong-Hua University, Taiwan, R.O.C
[12] Shan Zhu and Kai-KUang Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation”,
[13] Vasily G Moshnyaga and Keikichi Tamaru, “A Memory Efficient Array Architecture for FULL-Search Block Matching Algorithm”, Department of Electronics, Kyoto University Sakyo-ku, Yoshida-Honmachi, Kyoto 606-01, JAPAN
[14] Vasily G.Moshnyaga, “A New Computationally Adaptive Formulation of Block-Matching Motion Estimation”,
[15] THOMAS KOMAREK and PETER PIRSH, SENIOR MEMBER, IEEE “Array architectures for Block matching Algorithms”.
[16] Seung Hyun Nam and Moon Key Lee, “High-Throughput Block-Matching VLSI Architecture with Low Memory Band width”.
[17] Aur-Heh Hsieh, Member IEEE, and Ting-Pang Lin, “VLSI Architecture for Block-Matching Motion Estimation Algorithm”.
[18] Phillip A. Laplante (senior Member, IEEE) BCC/NJIT Technology and Engineering Center, Alexander D.Stoyenko, New Jersey Institude of Technology, “Real-Time Image Theory, Techniques, and Applications”,