Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/7619
標題: 基於像素取樣快速演算法之平行移動估測器電路架構設計與實現
Design and Implementation of Parallel Motion Estimation Archi-tecture Based on Fast Pel-Subsampling Algorithm
作者: 謝天恩
Hsieh, Tian-En
關鍵字: Motion Estimation;移動估測;VLSI;pel-subsampling algorithm;超大型積體電路;像素取樣
出版社: 電機工程學系所
引用: [1]. Information Technology - Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbit/s-Part 2: Video, ISO/IEC 11172-2, 1993. [2]. Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Video, ISO/IEC 13818-2 and ITU-T Recommendation H.262, 1996. [3]. Information Technology-Coding of Audio-Visual Objects-Part 2: Visual, ISO/IEC 14496-2,1999. [4]. Video Codec for Audiovisual Services at p64Kbit/s, ITU-T Recommenda-tion H.261, Mar. 1993. [5]. Video Coding for Low Bit Rate Communication, ITU-T Recommendation H.263, Feb. 1998. [6]. Joint Video Team, Draft ITU-T Recommendation and Final Draft Interna-tional Standard of Joint Video Specification, ITU-T Recommendation H.264 and ISO/IEC 14496-10 AVC, May 2003. [7]. K. R. Rao and J. J. Hwang, Techniques and Standards for Image, Video, and Audio Coding, Prentice Hall PTR, July 1998 [8]. T. Koga et al., “Motion compensated interframe coding for video conferenc-ing,” NTC '81, Notional Telecommun. Conf., pp. G5.3.1-G5.3.5, NEW Orleans, LA, Nov.-Dec. 1981. [9]. J. Y. Them, S. Ranganath, M.Ranganath, and A. A. Kassim, “A novel unre-stricted center-biased diamond search algorithm for block motion estima-tion.” IEEE Transactions on Circuits and Systems for Video Technology, vol.8, no. 4, pp. 369-37, Aug. 1998. [10]. 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. [11]. M.-J. Chen, W.-T. Chen, Y.-S. Jehng, and T.-D. Chiueh, “One-dimensional full search motion estimation algorithm for video coding,” IEEE Transac-tions on Circuits and Systems for Video Technology, vol. 4, no. 5, pp. 504-509, June 1994. [12]. L.-M. Po and W.-C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 3, pp. 313-317, June 1996. [13]. J. Jain and A. Jain, “Displacement measurement and its application in inter-nal image coding,” IEEE Transactions on Communications, vol. com-29, no. 12, pp. 1799-1808, Dec. 1981. [14]. M. Granbari, “The cross search algorithm for motion estimation,” IEEE Transactions on Communications, vol. 38, no. 9, pp. 950-953, July 1990. [15]. S. Kappagantula and K. R. Rao, “Motion compensated interframe image prediction,” IEEE Transactions on Communications, vol. COM-33, no. 9, pp. 1011-1015, Sept. 1985. [16]. R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Transactions on Circuits and System for Video Technology, vol. 4, no. 4, pp. 438-442, Aug. 1994. [17]. 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 System for Video Technology, vol. 6, no. 4, pp. 419-422, Aug. 1996. [18]. A. M. Tourapis, O. C. Au, M. L. Liou, G. Shen, and I. Ahmad, “Optimizing the MPEG-4 encoder - advanced diamond zonal search,” in Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS'00), 2000, PP. 674-677. [19]. A. M. Tourapis, O. C. Au, and M. L. Liu, “Highly efficient predictive zonal algorithms for fast block-matching motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 10, pp. 934-947, Oct. 2002. [20]. A. Zaccarin and B. Liu, “Fast algorithms for block motion estimation,” in Proceedings of IEEE International Conference on Acoustics, Speed, and Signal Processing (ICASSP'92), 1992, pp. 449-452. [21]. H. Gharavi and M. Mills, “Block matching motion estimation algorithms - new results,” IEEE Transactions on Circuits and Systems, vol. 37, no. 5, pp. 649-651, May 1990. [22]. M.-J. Chen, L.-G. Chen, T.-D. Chiueh, and Y.-P. Lee, “A new block-matching criterion for motion estimation and its implementation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 5, no. 3, pp. 231-236, June 1995. [23]. B. Natarajan and V. Bhaskaran, “Low-complexity block-based motion esti-mation via one-bit transforms,” IEEE Transactions on Circuits and Systems for Video Technology, 7, no. 4, pp. 702-706, Aug. 1997 [24]. J.-H. Luo, C.-N. Wang, and T. Chiang, “A novel all-binary motion estima-tion (ABME) with optimized hardware architectures,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 8, pp. 700-712, Aug. 2002. [25]. Z.-L. He, C.-Y. Tsui, K.-K. Chan, and M. L. Liou, “Low-power VLSI design for motion estimation using adaptive pixel truncation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, no. 5, pp. 669-678, Aug. 2000 [26]. C.-H. Hsieh, P.-C. Lu, J.-S. Shyn, and E.-H.Lu, “Motion estimation algo-rithm using interblock correlation,” IEE Electronic Letters, vol. 26, no. 5, pp. 276-277, Mar. 1990. [27]. S. Zafar, Y.-Q. Zhang, and J. S. Baras, “Predictive block-matching motion estimation for TV coding - part I: inter-block prediction,” IEEE Transac-tions on Broadcasting, vol. 37, no. 3, pp. 97-101, Sept. 1991. [28]. Y.-Q. Zhang and S. Zafar, “Predictive block-matching motion estimation for TV coding - Part II: inter-frame prediction,” IEEE Transactions on Broad-casting, vol. 37, no. 3, pp. 102-105, Sept. 1991. [29]. M.-C. Chen and A. N. Willson J., “A logarithmic-time adaptive block matching algorithm in estimating large displacement motion vectors,” in Proceedings pf IEEE Multimedia Communication and Video Coding Sym-posium, 1995. [30]. J. Chalidabhongse and C.-C. J. Kuo, “Fast motion vector estimation using multiresolution-spatio-temporal correlations,” IEEE Transactions on Cir-cuits and System for Video Technology, vol. 7, no. 3, pp. 477-488, June 1997. [31]. D. Tzovaras, M. G. Strintizis, and H. Sahinolou, “Evaluation of multiresolu-tio block matching techniques for motion and disparity estimation,” Signal Processing: Image Communication, vol. 6, no. 1, pp. 56-67, Mar. 1994. [32]. J. H. Lee, K. W. Lin, B. C. Song, and J. B. Ra, “A fast multi-resolution block matching algorithm and its VLSI architecture for low bit-rate video coding,” IEEE Transactions on Circuits and System for Video Technology, vol. 11, no.12, pp. 1289-1301, Dec. 2001. [33]. J. H. Lee and N. S. Lee, “Variable block size motion estimation algorithm and its hardware architecture for H.264,” In proceedings of IEEE Interna-tional Symposium on Circuits and Systems(ISCAS'04), 2004, pp. 740-743. [34]. W. Li and E. Salari, “Succerrive elimination algorithm for motion estima-tion,” IEEE Transations on Image Processing, vol. 4, no. 1, pp. 105-107, Jan. 1995. [35]. X. Q. Gao, C. J. Duanmu, and C. R. Zou, “A multilevel successive elimation algorithm for block matching motion estimation,” IEEE Transations on Im-age Processing, vol. 9, no. 3, pp. 501-504, Mar. 2000. [36]. M. Bruning and W. Niehsen, “Fast full-search block matching,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 11, no. 2, pp. 241-247, Feb. 2001. [37]. Digital Video Coding Group, ITU-T recommendation H.263 software im-plementation, Telenor R&D, 1995. [38]. 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, Apr. 2000. [39]. K. M. Yang, M. T. Sun, and L. Wu, “A family of VLSI designs for the mo-tion compensation block-matching algorithm,” IEEE Transactions on Cir-cuits and Systems., vol. 36, no. 10, pp. 1317-1325, Oct. 1999. [40]. T. Komarek and P. Pirsch, “Arrary architectures for block matching algo-rithms,” IEEE Transactions on Circuits and Systems., vol. 36, no. 10, pp. 1301-1308, Oct. 1989. [41]. H. Yeo and Y. H. Hu, “A novel modular systolic array architecture for full-search block matching motion estimation,” IEEE Transactions on Cir-cuits and Systems for Video Technology., vol. 5, no. 5, pp. 407-416, Oct. 1995. [42]. Y. K. Lai and L. G. Chen, “A data-interlacing architecture with two-dimensional data-reuse for full-search block-matching algorithm,” IEEE Transactions on Circuits and Systems for Video Technology., vol. 8, no. 2, pp. 124-127, April 1998. [43]. L. De Vos and M. Stegherr, “Parameterizable VLSI architectures for the full-search block-matching algorithm,” IEEE Transactions on Circuits and Systems., vol. 36, no. 10, pp. 1309-1316, Oct. 1989. [44]. C. H. Hsieh and T. P. Lin, “VLSI architecture for block-matching motion es-timation algorithm,” IEEE Transactions on Circuits and Systems for Video Technology., vol. 2, no. 2, pp. 169-175, June 1992. [45]. J. F. Shen, T. C. Wang, and L. G. Chen, “A novel low-power full search block-matching motion estimation design for H.263+,” IEEE Transactions on Circuits and Systems for Video Technology., vol. 11, no. 7, pp. 890-897, July 2001. [46]. V. L. Do and K. Y. Yun, “A low-power VLSI architectur for full-search block-matching motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology., vol. 8, no. 4, pp. 393-398, Aug. 1998. [47]. X. Q. Gao, C. J. Duanmu, and C. R. Zou, “A multilevel successive elimina-tion algorithm for block matching motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology., vol. 9, no. 3, pp. 501-504, March 2000. [48]. M. Brunig and W. Niehsen, “Fast full-search block matching,“IEEE Trans-actions on Circuits and Systems for Video Technology., vol. 11, no. 2, pp. 241-247, Feb. 2001 [49]. H.-M. Jong, L.-G. Chen and T.-D. Chiueh, “Parallel architecture for 3-step hierarchical search block-matching algorithm,” IEEE Transactions on Cir-cuits and Systems for Video Technology, vol. 4, no 4, pp. 407-416, Aug. 1994. [50]. S. Dutta and W. Wolf, “A flexible parallel architecture adopted to block-matching motion estimation algorithms,” IEEE Transactions on Cir-cuits and Systems for Video Technology, vol. 6, no. 1, pp. 74-86, Feb. 1996. [51]. S.-C. Cheng and H.-M. Hang, “A comparison of block-matching algorithms mapped to systolic-array implementation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 7, no. 5, pp. 741-757, Aug. 1997. [52]. V. G. Moshnyaga, “A new computationally adaptive formulation of block-matching motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 11, no. 1, pp. 118-124, Jan. 2001. [53]. W.-M. Chao, C.-W. Hsu, Y.-C. Cheng, and L.-G Chen, “A noval motion es-timatior supporting diamond search and fast full search,” in Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS'02) pp. 492-495, 2002. [54]. Y.-W. Huang, S.-Y. Chien, B.-Y. Hsieh, and L.-G. Chen, “Global elimination algorithm and architecture design for fast block matching motion estima-tion,” IEEE Trans. Circuits Syst. Video Technol., vol. 14, pp. 898-907, June 2004. [55]. H.-K. Jung C.-P. Hong, J.-S. Choi, and Y.-H. Ha, “A VLSI architecture for the alternative sub-sampling block-matching algorithm,” IEEE Trans. Con-sumer Electron., vol. 41, pp. 231-238, May 1995. [56]. K.-B. Lee, H.-Y. Chin, H.-C. Hsu, and C.-W. Jen, “QME: An efficient sub-sampling-based block matching algorithm for motion estimation,” in proc. IEEE Int. Symp. Circuits Syst. Video Technol., vol. 2, pp. II-305-8, May 2004. [57]. S.-S. Lin, P.-C. Tseng, C.-P. Lin, and L.-G. Chen, ”Multi-mode content-ware motion estimation algorithm for power-aware video coding system,” IEEE Work Shop on Signal Processing Systems, pp. 239-244, 2004. [58]. S.-S. Lin, P.-C. Tseng, and L.-G. Chen, “Low-power parallel tree architecture for full search block-matching motion estimation,” in Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS'04), pp. II-313-316, 2004. [59]. J.-C. Tuan, T.-S. Chang, and C.-W. Jen, “On the data reuse and memory bandwidth analysis for full-search block-matching VLSI architecture,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 1, pp. 61-72, Jan. 2002.
摘要: 
在本論文中,我們提出了一個基於像素取樣快速演算法之平行移動估計器電路架構。首先我們使用了像素取樣快速演算法來降低絕對值累加之合(SAD)的計算量。此外,我們也利用四平行化螺旋掃描方法(four-parallel spiral scanning:4PSP)以及部分失真忽略法(partial distortion elimination:PDE)來提早終止不必要之絕對值累加運算。因此,我們提出之快速演算法可以避免陷入區域性最小值之困境,並順利的找出整體最小值,並且以很小的畫質品質下降達到節省運算功率之目的;根據我們的演算法,我們利用了一個4x4的處理單元(PE)陣列以及一個雙模態絕對值累加樹以有效的完成像素取樣之絕對值累加(SSAD)以及一般區塊比對之絕對值(SAD)累加,為了降低系統記憶體頻寬,我們也利用了記憶體插補組織以及內嵌記憶體組態此二技術有效率的將像素資料安排於記憶體中並達到C層次(Level C)的資料重複使用機制。本電路利用TSMC 0.18 um工藝設計;實作結果顯示,本架構可工作於100 MHz且功率消耗僅只需71.6 mW,而晶片的面積為1.9x1.9 mm2。根據實驗結果顯示本架構於100 MHz的工作頻率之下可處理每秒25張1024x768(XGA)之畫面;若應用於352x288 CIF@30fps之視訊編碼,則工作頻率僅僅需25 MHz,因此可以將此電路架構應用於多種影像相關電子產品之上。

In this paper, a parallel motion estimation architecture based on fast pel-subsampling algorithm is proposed. We proposed a fast pel-subsampling algorithm to reduce the computational amount of the sum absolute difference (SAD). Moreover, the four-parallel spiral scanning (4PSP) with partial distortion elimination (PDE) mecha-nism is also utilized to early terminate the unnecessary SAD. Therefore, the proposed fast algorithm can avoid trapping into the local minimum and save the computational power with a little performance degradation. In the light of our algorithm, the 4x4 processing element (PE) array and the dual mode SAD tree are proposed to perform SAD and SAD of the pel-subsampling (SSAD) efficiently. For the sake of reducing the system memory bandwidth, the memory interleaving organization and local memory con-figuration are proposed to easily arrange the current data and reference pixels, and to achieve the Level C data-reuse scheme. The proposed architecture has been imple-mented using standard cell methodology for TSMC 0.18 um 1P6M technology. The chip implementation results show that proposed architecture can work at 100 MHz and its power consumption is about 71.6 mW. The chip size is 1.9x1.9 mm2. According to the experimental results, the proposed architecture can process1024x768 XGA resolu-tion pictures in 25 frames per second at 100 MHz. For the CIF specification, it can per-form 352x288@30fps in real time at 25 MHz working frequency. Therefore, the pro-posed architecture can be utilized in many mobile video applications.
URI: http://hdl.handle.net/11455/7619
其他識別: U0005-2208200716453200
Appears in Collections:電機工程學系所

Show full item record
 

Google ScholarTM

Check


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