Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/7749
標題: 基於機率分析的一種次取樣的移動估計演算法
A subsampling motion estimation algorithm based on probability analysis
作者: 王紹文
Wang, Shao-Wen
關鍵字: motion estimation;移動估計;subsampling;probability;移動估算;機率
出版社: 電機工程學系所
引用: [1] Hsien-Hsi Hsieh and Yeong-Kang Lai, ” A Novel fast motion estimation algorithm using fixed subsampling pattern and multiple local winners search”, Circuits and Systems, 2001. ISCAS 2001. The 2001 IEEE International Symposium on Volume 2, 6-9 May 2001 Page(s):241 - 244 vol. 2 [2] L. M. Po and W. C. Ma, ” A novel four-step search algorithm for block motion estimation ”, IEEE Trans. Circuits Sys. Video Technol., vol. 6. pp. 331-317, June 1996. [3] Shan Zhu and Kai-Kuang Ma, ” A New Diamond Search AIgorithm for Fast Bock-Matching Motion Estimation ”, IEEE Trans. Iinage Process., vol. 9, no. 2. Feb. 2000. [4] So. M.F.; Wu, A. ” Four-step genetic search for block motion estimation ”, Int. Conf Signal Process. Proceed., Vol. 3,pp.1393 -1396, 1998. [5] Jae-Yong Kiam; Sung-Bong Yang ” An efficient hybrid search algorithm for fast block matching in video coding ”,TENCON 99. Proceedings of the IEEE Region IO ConferenceVolume, vol. 1 , pp. 112 -1 15, 1999. [6] B.Liu; A.Zaccarin ” New fast algorithms for the estimation of block matching vectors ”, IEEE Trans. Circuits Sys. VideoTechnol., vol. 3, no. 2, pp. 148-158, April 1993. [7] C. H. Cheung and L. M. Po, "A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation," IEEE Trans. on Circuits and Systems for Video Technology, Vol.12, No. 12, pp. 1168-1177, Dec. 2002. [8] C. H. Cheung and L. M. Po, "Novel Cross-diamond-hexagonal Search Algorithms for Fast Block Motion Estimation," IEEE Trans. on Multimedia, vol. 7, No. 1, pp. 16 - 22, Feb 2005. [9] Demir, B.; Erturk, S.; “Block motion estimation using adaptive modified two-bit transform”,Image Processing, IET,Volume 1, Issue 2, June 2007 Page(s):215 - 222 [10] Yang, S.; Wolf, W.; Vijaykrishnan, N.; “Power and performance analysis of motion estimation based on hardware and software realizations”, Computers, IEEE Transactions on Volume 54, Issue 6, Jun 2005 Page(s):714 - 726 [11] Veeravalli, A.G.; Pan, W.D.; Nalasani, M.; Mohan, M.K.S.; “Covariance analysis of non-translational motion-compensated frame differences”,System Theory, 2005. SSST ''05. Proceedings of the Thirty-Seventh Southeastern Symposium on 20-22 March 2005 Page(s):462 - 465 [12] Mietens, S.; de With, P.H.N.; Hentschel, C.; “Computational-complexity scalable motion estimation for mobile MPEG encoding”,Consumer Electronics, IEEE Transactions on Volume 50, Issue 1, Feb 2004 Page(s):281 - 291 [13] Namuduri, K.R.; Aiyuan Ji; “Computation and performance trade-offs in motion estimation algorithms”,Information Technology: Coding and Computing, 2001. Proceedings. International Conference on 2-4 April 2001 Page(s):263 - 267 [14] Dufaux, F.; Moscheni, F.; “Motion estimation techniques for digital TV: a review and a new contribution”,Proceedings of the IEEE Volume 83, Issue 6, June 1995 Page(s):858 - 876 [15] Namuduri, K.R.; “Motion estimation using spatio-temporal contextual information”,Circuits and Systems for Video Technology, IEEE Transactions on Volume 14, Issue 8, Aug. 2004 Page(s):1111 - 1115 [16] Erturk, A.; Erturk, S.;” Two-bit transform for binary block motion estimation”,Circuits and Systems for Video Technology, IEEE Transactions on Volume 15, Issue 7, July 2005 Page(s):938 - 946 [17] Cai, Z.Q.; “LPF-based motion estimation”, ISCE ''97 - Proceedings of 1997 IEEE International Symposium on Consumer Electronics 2-4 Dec. 1997 Page(s):222 - 225 [18] Rabiner, W.B.; Chandrakasan, A.P.;” Network-driven motion estimation for wireless video terminals”,Circuits and Systems for Video Technology, IEEE Transactions on Volume 7, Issue 4, Aug. 1997 Page(s):644 - 653 [19] Malo, J.; Gutierrez, J.; Epifanio, I.; Ferri, F.J.; Artigas, J.M.; “Perceptual feedback in multigrid motion estimation using an improved DCT quantization”,Image Processing, IEEE Transactions on Volume 10, Issue 10, Oct. 2001 Page(s):1411 - 1427 Digital Object Identifier 10.1109/83.951528 [20] Hoi-Ming Wong; Au, O.C.; Chang, A.; Shu-Kei Yip; Chi-Wang Ho; “Fast mode decision and motion estimation for H.264 (FMDME)”, Circuits and Systems, 2006. ISCAS 2006. Proceedings. 2006 IEEE International Symposium on 21-24 May 2006 Page(s):4 pp. [21] Subramanya, S.R.; Patel, H.; Ersoy, I.; “Performance evaluation of block-based motion estimation algorithms and distortion measures”, Information Technology: Coding and Computing, 2004. Proceedings. ITCC 2004. International Conference on Volume 2, 2004 Page(s):2 - 7 Vol.2 [22] Narang, S.; Narang, N.K.; “Network oriented motion estimation for video-on-demand over wireless networks”, Vehicular Technology Conference, 1999 IEEE 49th Volume 2, 16-20 May 1999 Page(s):1535 - 1539 vol.2 [23] Chung-Ming Kuo; Shu-Chiang Chung; Po-Yi Shih; “Kalman filtering based rate-constrained motion estimation for very low bit rate video coding”, Circuits and Systems for Video Technology, IEEE Transactions on Volume 16, Issue 1, Jan. 2006 Page(s):3 - 18 [24] Rabiner, W.B.; Chandrakasan, A.P.; “Network driven motion estimation for portable video terminals”,Acoustics, Speech, and Signal Processing, 1997. ICASSP-97., 1997 IEEE International Conference on Volume 4, 21-24 April 1997 Page(s):2865 - 2868 vol.4 [25] Hill, P. R.; Chiew, T. K.; Bull, D. R.; Canagarajah, C. N.; “Interpolation Free Subpixel Accuracy Motion Estimation”, Circuits and Systems for Video Technology, IEEE Transactions on Volume 16, Issue 12, Dec. 2006 Page(s):1519 - 1526 [26] Jen-Yu Shieh; Hanqi Zhuang; Sudhakar, R.; “Motion estimation from a sequence of stereo images: a direct method”, Systems, Man and Cybernetics, IEEE Transactions on Volume 24, Issue 7, July 1994 Page(s):1044 - 1053 [27] Panusopone, K.; Baylon, D.M.;” An analysis and efficient implementation of half-pel motion estimation”, Circuits and Systems for Video Technology, IEEE Transactions on Volume 12, Issue 8, Aug. 2002 Page(s):724 - 729 [28] WeiJian Yang; “An efficient motion estimation method for MPEG-4 video encoder”,Consumer Electronics, IEEE Transactions on Volume 49, Issue 2, May 2003 Page(s):441 - 446 [29] Manikandan, M.; Vijayakumar, P.; Ramadass, N.; “Motion estimation method for video compression - an overview”,Wireless and Optical Communications Networks, 2006 IFIP International Conference on 11-13 April 2006 Page(s):5 pp. [30] Sorwar, G.; “Adaptive-centre candidate decimation distance-dependent thresholding search for motion estimation”, Information Technology and Applications, 2005. ICITA 2005. Third International Conference on Volume 1, 4-7 July 2005 Page(s):674 - 679 vol.1 [31] Wei-Feng He; Zhi-Gang Mao; Zhi-Qiang Gao; Yi-Zheng Ye; “VLSI implementation of full pixel motion estimation processor for MPEG-4 AS profile”,Solid-State and Integrated Circuits Technology, 2004. Proceedings. 7th International Conference on Volume 3, 18-21 Oct. 2004 Page(s):1633 - 1636 vol.3 [32] Nalasani, M.; Pan, W.D.; “On the complexity and accuracy of motion estimation using Lie operators”,System Theory, 2004. Proceedings of the Thirty-Sixth Southeastern Symposium on 2004 Page(s):16 - 20 [33] Duanmu, C.; Ahmad, M.O.; Swamy, M.N.S.; “A continuous tracking algorithm for long-term memory motion estimation [video coding]”, Circuits and Systems, 2003. ISCAS ''03. Proceedings of the 2003 International Symposium on Volume 2, 25-28 May 2003 Page(s):II-356 - II-359 vol.2 [34] Sorwar, G.; Murshed, M.; Dooley, L.; “Distance dependent thresholding search for fast motion estimation in real world video coding application”, Circuits and Systems, 2002. APCCAS ''02. 2002 Asia-Pacific Conference on Volume 2, 28-31 Oct. 2002 Page(s):519 - 524 vol.2 [35] Wei Guan Yau; Li-Chen Fu; Liu, D.; “Robust real-time 3D trajectory tracking algorithms for visual tracking using weak perspective projection”, American Control Conference, 2001. Proceedings of the 2001 Volume 6, 25-27 June 2001 Page(s):4632 - 4637 vol.6 [36] Cohen, B.; Dinstein, I.; “Motion estimation in noisy ultrasound images by maximum likelihood”, Pattern Recognition, 2000. Proceedings. 15th International Conference on Volume 3, 3-7 Sept. 2000 Page(s):182 - 185 vol.3 [37] Lopes, F.; Ghanbari, M.; “Hierarchical motion estimation with spatial transforms”,Image Processing, 2000. Proceedings. 2000 International Conference on Volume 2, 10-13 Sept. 2000 Page(s):558 - 561 vol.2 [38] Ismaeil, I.R.; Docef, A.; Kossentini, F.; Ward, R.; “Motion estimation using long-term motion vector prediction”,Data Compression Conference, 1999. Proceedings. DCC ''99 29-31 March 1999 Page(s):531 [39] Ertuk, S.; “A New Perspective to Block Motion Estimation for Video Compression: High-Frequency Component Matching”,Signal Processing Letters, IEEE Volume 14, Issue 2, Feb. 2007 Page(s):113 - 116 [40] Sung-Eun Kim; Jong-Ki Han; Jae-Gon Kim; “An efficient scheme for motion estimation using multireference frames in H.264/AVC”, Multimedia, IEEE Transactions on Volume 8, Issue 3, June 2006 Page(s):457 - 466 [41] Chimienti, A.; Ferraris, C.; Pau, D.; “A complexity-bounded motion estimation algorithm”,Image Processing, IEEE Transactions on Volume 11, Issue 4, April 2002 Page(s):387 - 392 [42] Munoz-Jimenez, V.; Zergainoh, A.; Astruc, J.-P.; “Motion estimation method through adaptive deformable variable-sized rectangular meshes using warping function”,Signal Processing and Information Technology, 2006 IEEE International Symposium on Aug. 2006 Page(s):884 - 889 [43] Nguyen Van Dan; Michitaka Kameyama; “Bayesian-Networks-Based Motion Estimation for a Highly-Safe Intelligent Vehicle”,SICE-ICASE, 2006. International Joint Conference Oct. 2006 Page(s):6023 - 6026 [44] Meng-chou Chang; Jung-shan Chien; “An adaptive search algorithm based on block classification for fast block motion estimation”, Circuits and Systems, 2006. ISCAS 2006. Proceedings. 2006 IEEE International Symposium on 21-24 May 2006 Page(s):4 pp. [45] Tak-Song Chong; Au, O.C.; Tai-Wai Chan; Wing-San Chau; “A spatial-temporal de-interlacing algorithm”,Multimedia and Expo, 2005. ICME 2005. IEEE International Conference on 6-8 July 2005 Page(s):4 pp. [46] Guang-Yu Du; Tian-Shu Huang; Li-Xin Song; Bing-Jie Zhao; “A novel fast motion estimation method based on particle swarm optimization”, Machine Learning and Cybernetics, 2005. Proceedings of 2005 International Conference on Volume 8, 18-21 Aug. 2005 Page(s):5038 - 5042 Vol. 8 [47] Chung, H.; Romacho, D.; Ortega, A.; “Fast long-term motion estimation for H.264 using multiresolution search”, Image Processing, 2003. ICIP 2003. Proceedings. 2003 International Conference on Volume 1, 14-17 Sept. 2003 Page(s):I - 905-8 vol.1 [48] Chang, A.; Wong, P.H.W.; Yeung, Y.M.; Au, O.C.; “Fast integer motion estimation for H.264 video coding standard”,Multimedia and Expo, 2004. ICME ''04. 2004 IEEE International Conference on Volume 1, 27-30 June 2004 Page(s):289 - 292 Vol.1
摘要: 
移動估算的目的就是要估算出目前巨集方塊(MB)在參考畫面中出現的位置,因此我們在參考畫面中以目前畫面中的MB位置為中心點定義出一個搜尋視窗,在視窗中的候選方塊裡找到一個符合我們所定義的相似條件的MB,依據找到的候選方塊與目前畫面中的方塊的座標相減後為最佳的移動向量,如何降低搜尋的複雜度及運算量變成非常重要的課題。本論文提出一種基於機率分析的一種次取樣(sub-sampling)的移動估計演算法,其中依據特定的式樣(pattern) ,逐次取出後計算SSAD(Sub-sampling SAD)值,另外配合區域最小值及由中心點為搜尋路徑起點的方式結合,再利用早先就統計好的每一階層中SSAD值出現的機率,進行SAD值的預測,這樣可以非常有效的在第一階取樣後立即預測該候選方塊的最終SAD值的大小,剩下的候選方塊再進入下一階的取樣並重複類似的步驟,這其中將會發現在候選方塊中原本需要計算256個點才能得知的最終SAD值,有時候只需要取樣其中的8~16個點便能準確判斷出其最終的SAD值的出現範圍,也就是只需要以出現機率預測的方式便能提前結束計算,最後我們將會針對其他搜尋演算法進行性能的比較,本論文所提供的演算法對於降低複雜度及運算量有令人滿意的效果。

The goal of motion estimation needs to estimate the best position of current micro block (MB) which appears in the reference picture, therefore we define a search window in the reference picture and take the position of current MB as the central point. Searching candidate blocks for matched with the condition which conforms to us to define. To subtract the coordinates of matched candidate block from the coordinates of current block coordinates then we got the motion vector. How to reduce the search complexity and the operand turns is the extremely important topic. The present paper proposed a subsampling motion estimation algorithm based on probability analysis to calculate SSAD (Sub-sampling SAD) value using two fixed pattern. Moreover unifies the localwinner and the central point of searching path and probability of the SSAD value. It can predict the SAD value of this candidate blocks effectively after the first step sample. The left over candidate blocks enter the next step of subsampling again. Originally it needs 256 spots to calculate the value of SAD ;In our algorithm, it takes only 8~16 spots to judge its range of final SAD value accurately. In other words, we can meet prediction target ahead of time using the probability of SSAD. Finally we compare the average PNSR and the average search points with many other algorithms. The present paper will reduce the order of complexity and the operand effectively.
URI: http://hdl.handle.net/11455/7749
其他識別: U0005-2708200714322400
Appears in Collections:電機工程學系所

Show full item record
 

Google ScholarTM

Check


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