Please use this identifier to cite or link to this item:
標題: 用於影像壓縮的一個混合式快速全區域搜尋移動估測演算法
A Hybrid Fast Full Search Motion Estimation Algorithm for Video Compression
作者: 黃柏森
Huang, Po-Sen
關鍵字: Fast Full Search Algorithm;快速全區域搜尋演算法;Motion Estimation;移動評估
出版社: 電機工程學系所
引用: [1] CCITT SGXV, “Description of reference model 8 (RM8),” Document 525, Work-ing Party XV/4, Specialists Group on Coding for Visual Telephony, June 1989. [2] ISO/IEC 11172-2(MPEG-1 Video), “Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at Up to About 1.5 Mbit/s: Video,” 1993. [3] ISO/IEC 13818-2 | ITU-T H.262(MPEG-2 Video), “Information Technol-ogy-Generic Coding of Moving Pictures and Associated Audio Information: Video,” 1995. [4] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion Compensated Inter-frame Coding for Video Conferencing,” in Proc. NTC81, New Orleans, LA, pp. C9.6.1-9.6.5, Nov. 1981. [5] J. R. Jain and A. K. Jain, “Displacement Measurement and Its Application in In-ter-frame Image Coding,” IEEE Transactions Communication, vol. COM-29, pp. 1799-1808, Dec. 1981. [6] R. Srinivasan and K. R. Rao, “Predictive coding based on efficient motion estima-tion,” IEEE Transactions Communication, vol. COM-33, pp. 888-896, Aug. 1985. [7] S. Kappagantula and K. R. Rao, “Motion Compensated Inter-frame Image Predic-tion,” IEEE Transactions Communication, vol. COM-33, pp. 101 1-1015, Sept. 1985. [8] “ITU-T Recommendation H.263 Software Implementation,” Digital Video Coding Group, Telenor R&D, 1995. [9] W. Li and E. Salari, “Successive Elimination Algorithm for Motion Estimation,” IEEE Transactions Image Processing, vol. 4, no. 1, pp. 105-107, Jan.1995. [10] X. Q. Gao, C. J. Duanmu, and C. R. Zou, “A Multilevel Successive Elimination Algorithm for Block Matching Motion Estimation,” IEEE Transactions Image Processing, vol. 9, no. 3, pp. 501-504, Mar. 2000. [11] S. M. Akramullah, I. Ahmad, and M. L. Liou, “Optimization of H.263 Video En-coding Using a Single Processor Computer: Performance tradeoffs and bench-marking,” IEEE Transactions Circuits System Video Technology., vol. 11, no. 8, pp. 901-915, Aug. 2001. [12] Lai-Man Po and Wing-Chung Ma, “A Novel Four-Step Search Algorithm for Fast Block Motion Estimation,” IEEE Transactions Circuits System Video Technology, vol. 6, no. 3, Aug. 1996. [13] 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, Feb. 2000. [14] Ce Zhu, Xiao Lin; L.; Lai-Man Po; “Enhance hexagonal search for fast block mo-tion estimation” IEEE Transactions on Circuits and Systems for video Technology, vol. 14, Issue 10, pp. 1210-1214 ,Oct. 2004. [15] Jong-Nam Kim, and Tae-Sun, “Adaptive Matching Scan Algorithm Based on Gra-dient Magnitude for Fast Full Search in Motion Estimation,” IEEE Transactions Consumer Electronics, vol. 45, no. 3, Aug. 1999. [16] Jong-Nam Kim, and Tae-Sun, “A Fast Full-Search Motion-Estimation Algorithm Using Representative Pixels and Adaptive Matching Scan,” IEEE Transactions Circuits System Video Technology, vol. 10, no. 7, Oct. 2000. [17] Hanan A. Mahmoud, and Magdy Bayoumi, “A New Block-Matching Motion Es-timation Algorithm Based on Successive Elimination” IEEE Transactions Circuits System Video Technology, vol. 10, no. 7, Oct. 2000. [18] Bartolomeo Montrucchio, and Davide Quaglia, “New Sorting-Based Lossless Mo-tion Estimation Algorithms and a Partial Distortion Elimination Performance Analysis,” IEEE Transactions Circuits System Video Technology, vol. 15, no. 2, Feb. 2005. [19] S. Eckart and C. Fogg, “ISO/IEC MPEG-2 Software Video Codec,” Proc, SPIE, vol. 2419, 1995, pp. 100-118.
這個混合式的快速FSBMA,主要有兩個階段所組成。第一階段是內部螺旋形搜尋並結合部分失真刪除演算法(Spiral PDE)來實現,而第二階段是由,部分區塊失真刪除,架構在多階連續消除移動預估演算法(MSEA PDE)來組成。Spiral PDE演算法將會幫助MSEA PDE來得到一個小的絕對值差之和(SAD)當作初始值,如此將會提高無用候選區塊被略過不計算的機率。
一個全新的觀念MSEA PDE被導入此混合式移動區塊估計演算法,在MSEA小區塊上實現PDE的精神,並配合Spiral PDE在參數circle的設定,使得在適當的範圍內螺旋狀的搜尋起始SAD,將可獲得一個極佳的初始SAD,有助於在後段的MSEA PDE部份來大幅提升了整體演算法的速度,並將原始MSEA演算法,在小區塊2x2以下的高運算量缺陷,藉由小區塊PDE的方法往下推了一層到1x1的區塊大小才會產生高運算量的負荷。
當MSEA PDE演算法有著最小的起始SAD時,可以提高忽略無用的候選區塊之比率(Skip Ratio),當此Skip Ratio越高時,代表著我們忽略不計算的區塊越多,因此程式執行時間會較快,但卻不是最高的Skip Ratio,會有著最快的程式執行時間,因為高的Skip Ratio必定伴隨著大量比較器的使用,因而兩者之間不會呈現正比的關係。
實驗的結果在Linux Fedora Core 4系統下,利用AMD 3700+的中央處理器以及2GByte的記憶體,利用g++編譯器來編譯程式,在程式執行時間上面,對於一些典型的影像SIF(352x240)格式的測試圖片,大約有FSBMA的7倍多之快,並且能得到與FSBMA相同的MSE以及PSNR。

Along with technology progress, people require the video quality also higher than the past. In order to achieve the high resolution and high quality, the real time lossless algorithms become more and more important. Traditionally, we will use the full search block matching algorithm (FSBMA) to search the best matching image block. As this algorithm has large computational overhead, it is not suitable for real time propose. Hence, many fast FSBMAs are developed. Our thesis also proposed a new hybrid FSBMA method to solve the needs of real-time computation.
The hybrid fast FSBMA primarily has two stages. One is the spiral search com-bining partial distortion elimination algorithm (Spiral PDE), and the other is partial dis-tortion multilevel blocks on multilevel successive elimination algorithm (MSEA PDE). The Spiral PDE algorithm will help the MSEA PDE to obtain the minimum sum of ab-solute difference (SAD) for the initial value, and it will increase the skip ratio on invalid candidate blocks.
Beside, a novel concept, MSEA PDE, is introduced in a hybrid motion estimation block matching algorithm. Based on multilevel blocks to realize the PDE conception, and appropriate setting the circle parameter, it will help to obtain a good initial SAD in an appropriate circle range. Spiral PDE will help the MSEA PDE algorithm stage to in-crease the speed of the overall algorithm. It also will improve the computation complex-ity of original MSEA on the block sizes below 2x2 overhead, and by using MSEA PDE, the computational overhead level drops to the 1x1 block size.
When MSEA PDE algorithm has the initial minimum SAD, we can increase the skip of invalid candidate blocks ratio (Skip Ratio). When the skip ratio is high, it means the more invalid blocks we skip, and the run time of the program is faster. But it does not mean the highest skip ratio has the shortest run time, the high skip ratio must come with amount of comparators. They are present in the direct proportion.
The experiment is made under the Linux Fedora core 4 system with the AMD 3700+ processor and 2Gbyte RAM. By using the g++ compiler, in the run time aspect on some typical SIF (352x240) format video sequences it is seven times faster than FSBMA, and has the same MSE and PSNR as FSBMA.
其他識別: U0005-1408200613350000
Appears in Collections:電機工程學系所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.