對ㄧ個視訊編碼器而言移動估計是最為重要的一部份。在AVC內，移動估計包含多種模式預測，多個參考畫面及不同大小區塊編碼，利用其間的交叉組合來獲得更準確且更高的壓縮效率。然而移動估計的運算量也因而相對提高。
在本論文裡我們提出一個基於適應性區塊處理的移動估計，以偵測移動的方向來決定投射方向。所提出的投射方法結合了適應性區塊選擇，基於移動向量與預測誤差來決定收尋區塊的大小，有效地加快移動估計處理的時間。我們也提出利用預測的誤差與鄰邊區塊的特性來決定收尋範圍。因為移動估計會影響到視訊編碼的效能、計算量及功率消耗。利用移動向量及預測的誤差來決定最佳的收尋範圍。相同的收尋範圍也因畫面間的關係而應用在不同的畫面。結果顯示所提出的方法有效減少收尋範圍因而降低計算量。此演算法能有效地減少60%的移動估計編碼時間。
此外我們針對移動估計提出平行化可重組計算的方法，提供更彈性的運算方式。我們利用directed acyclic graph (DAG)來呈現視訊編碼演算法，提出一新穎的平行化分割方式，在一個平行化可重組計算的系統上運用dynamic reconfigurable computing (DRC)單元來呈現移動估計DAG。此方法對於高解析度的測試影片能加快視訊編碼運算的速度。

Motion estimation is the most important component in the video encoder which directly affects the encoding speed. In video coding motion estimation invokes multiple prediction modes, multiple reference frames and variable block sizes to achieve more accurate prediction and higher compression efficiency. However, the computation load of motion estimation increases greatly in advance video coding.
In this dissertation a block based motion estimation algorithm based on projection with adaptive window size selection is proposed. Direction of the motion is detected to decide projection direction according to their edge. This projection method is combined with adaptive window size selection in which, appropriate search window for each block is determined on the basis of motion vectors and prediction errors obtained for the previous block, which makes this novel method several times faster than exhaustive search with negligible performance degradation.
We also propose an adaptive search range selection scheme based on prediction error and local statistics of the neighboring blocks. The performance, computation, and power consumption of block matching motion estimation algorithms in video coding standards depends on the motion search range. An optimal search range for each block is determined on the basis of motion vectors and prediction errors obtained for a region of blocks for which those values have already been obtained. Same search range is utilized for different frames subjected to correlation of scalability. The result shows that there is a significant reduction of computational cost of video encoder, since a narrow search range is chosen for area with little motion. Thus, in encoding a video our method results in reduction of computation complexity of block based motion estimation by 60% with negligible PSNR degradation.
Finally, parallel reconfigurable computing architecture for search range selection in motion estimation is proposed which offers more flexibility than graphic processing unit. First, we construct a directed acyclic graph (DAG) to represent video coding algorithms, and a novel parallel partition approach is proposed to map motion estimation DAG onto the multiple dynamic reconfigurable computing (DRC) units in a parallel reconfigurable computing (PRC) system. This partitioning algorithm is capable of design optimization of parallel processing reconfigurable systems for a given number of processing elements in different search range. This speeds up the video processing with minimum sacrifice for HDTV.

[1] K. Peter, “Algorithms,complexity analysis and VLSI architectures for MPEG-4 motion estimation”, Kluwer Academic Publishers, Boston, 1999.

[2] Joint Video Team of ITU-T and ISODEC JTC I, “Draft ITU-T recommendation and final draft international standard of joint video specification.” (ITU-T Kec. H.264 ISO/IEC 14496.10 AVC) JVT of ISO/IEC MPEG and ITU-T VCEG , JVT – GO05 march 2003.

[3] T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra “Overview of the
H.264/AVC video coding standard”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 560-576, 2003.

[4] P. Milanfar, “A model of the effect of image motion in the radon transform domain,” IEEE Transaction on Image Processing Vol 8, Issue 9, pp 1276-1281, Sep 1999.

[5] J. Kim and R. Park, “A fast feature-based block matching algorithm using integral projections,” IEEE Jour. Sel. Areas in Comm., vol. 10, no. 5, pp. 968-971, Jun. 1992.

[6] K. L. Chung and L. C. Chang, “A new predictive search area approach for fast block motion estimation,” IEEE Trans. Image Processing, vol. 12, no. 6, pp 648-652, June 2003.

[7] C. Tu, T. Tran, and P. Topiwala, “A hybrid feature/image block motion estimation approach,” ITU-T/VCEG M.26.doc, Austin Meeting, April 2001.

[8] T Yamada, M Ikekawa, and I Kuroda, “Fast and accurate motion estimation algorithm by adaptive search range and shape selection,” Proceeding of ICASSP , vol. 2, pp. 897-900, 2005.

[9] Joint Video Team of ISO/IEC MPEG and ITU-T VCEG, H.264/AVC. (online) Reference Software JM10.1, JM 16.0 http:/bs.hhi.de/suehring/tml/download/ .

[10] R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation” IEEE Transactions on Circuits and Systems Video Technology,vol. 4, pp. 438–443, Aug. 1994.

[11] C. Zhu et al., “Enhanced hexagonal search for fast block motion estimation”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 14, pp. 1210 - 1214, Oct. 2004.

[12] P. Lai-Man and M. Wing-chung, “A novel four-step search algorithm for fast blockmatching”, IEEE Transactions On Circuits and Systems for Video Technology, vol. 6, pp. 313-317, Jun. 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, pp. 287-290, Feb. 2000.

[14] Y. Chan and W. Siu , “An efficient search strategy for block motion estimation using image features”, IEEE Transactions on Image Processing, vol. 10, pp. 1223-1238, Aug. 2001.

[15] J. Lee et al, “An efficient architecture for motion estimation and compensation in the transform domain”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, pp. 191-201,Feb. 2006.

[16] C. Cheung and L. Po, “A hierarchical block motion estimation algorithm using partial distortion measure”, Proceedings International Conference on Image Processing, vol. 3, pp. 606-609, Oct. 1997

[17] Motion estimation algorithm source code available at Matlab central file exchange ‘ www.mathworks.com/matlabcentral/fileexchange’

[18] “Phase correlation motion estimation” report available at http://visilab.unime.it/~ianni/slides_CV/liang_report-phase-correlation-motion-prediction.pdf

[19] T. Song, K. Ogata, K. Saito, and T. Shimamoto, “Adaptive search range motion estimation algorithm for H.264/AVC,” Proc. ISCAS, pp.3956–1959, May 2007.

[20] X. Xu and Y. He, “Modification of dynamic search range for JVT,”JVT-Q088-L, USA, Oct. 2005.

[21] S. Saponara, et al., “Dynamic control of motion estimation search parameters for low complex H.264 video coding,” IEEE Trans. Consum.Electron., Feb. 2006.

[22] S.W. Lee, et al., “Fast motion estimation with adaptive search range adjustment,” SPIE Optical. Eng., vol.46, no.4, April 2007.

[23] G. Li and M.-J. Chen, “Adaptive search range decision and early termination for multiple reference frame motion estimation for H.264,” IEICE Trans. Commun., vol.E89-B, no.1, pp.250–253, Jan. 2006.

[24] Goel S., Ismail Y., Bayomi M., “Adaptive Search Window Size Algorithm for Fast Motion Estimation in H.264/AVC Standard”, MWSCAS 2005

[25] Choi Y H and Choi T S, “Fast Motion Estimation Technique with Adaptive Variable Search Range.”, IEICE Fundamentals, Vol. E82-A, No.6, p.905-910, 1999.

[26] Kim B G, Reddy K.and Ahn W H, “Dynamic Search-Range Control Algorithm for Interframe Coding in Scalable Video Coding.”, Optical Engineering48(9), 097002, September 2009.

[27] Shen L., Feng G., Zhang Z., and An P., “Macroblock-level Adaptive Search Range Selection for Motion Estimation in Multiview Video Coding.”, Journal of Electronic Imaging 18(3), 033003, July-Sep 2009.

[28] J. Mitcell, W. Pennebaker, C. Fogg, and D. LeGall, MPEG Video Compression Standard, Chapman and Hall, 1997.

[29] Chen Z., Song Y., Ikenaga T., and Goto S., “Adaptive Search Range Selection Algorithm for Variable Block Size Motion Estimation in H.264/AVC”, IEICE Trans. Fundamentals, Vol.E91-A, No.4 April 2008.

[30] M. Motomura, Y. Aimoto, A. Shibayama, Y. Yabe and M. Yamashina, “An embedded DRAM-FPGA chip with instantaneous logic reconfiguration,” in Proc. Symp. VLSI Circuits, 1997, pp. 55-56.
[31] T. Fujii et al, “A dynamically reconfigurable logic engine with a multiconfiguration/ multi-mode unified-cell architecture,” in Proc. IEEE Int. Solid-State Circuits Conf., 1999, pp. 364-365.

[32] W. Stallings, “Computer organization and architecture: designing for performance,” Pearson Education, 2003.

[33] L. F. Chen, Y. K. Lai, “VLSI architecture of the reconfigurable computing engine for digital signal processing applications,” IEEE Circuits and Systems Conference., ISCAS '04. pp. 937-40, May 2004.

[34] Vissers, K.A, “Parallel processing architectures for reconfigurable systems,” Design, Automation and Test in Europe Conference and Exhibition, 2003 pp. 396 – 397

[35] H. Schmit et al, “PipeRench: A virtualized programmable datapath in 0.18 micron technology,” IEEE Custom Integrated Circuits Conference., pp. 63-66, May 2002.

[36] H. Singh, G. Lu, M. Lee, F. J. Kurdahi, N. Bagherzadeh, E. Filho, R. Maestre, “MorphoSys: Case Study of a Reconfigurable Computing System Targeting Multimedia Applications,” Proceedings Design Automation Conference (DAC’00), pp. 573-578, Los Angeles, California, May 2000.

[37] R. Maestre, F. J. Kurdahi, M. Fernández, R. Hermida, N. Bagherzadeh, H. Singh, “Kernel Scheduling Techniques for Efficient Solution Space Exploration in Reconfigurable Computing,” Special Issue on Modern Methods and Tools in Digital System Design, in the Journal on System Architecture, 47, pp. 277-292, 2001.

[38] [Online]. Available: http://www.xilinx.com/

[39] G. M. Wu, J. M. Lin, and Y. W. Chang, “Generic ILP-based approaches for time-multiplexed FPGA partitioning,” IEEE Trans. Computer-Aided Design, vol. 20, no. 10, pp. 1266-1274, Oct. 2001.

[40] Y. K. Lai, L. F. Chen, and J. C. Chen, “A reconfigurable computing processor core for multimedia system-on-chip applications,” Japanese Journal of Applied Physics, vol.45, no.4B, pp.3336-3342, April 2006.

[41] Yagi H., Rosenstiel W., Engblom J., Andrews J., Vissers K., Serughetti M., “The wild west: Conquest of complex hardware-dependent software design” Design Automation Conference, 2009. DAC '09. 46th ACM/IEEE ,26-31 July 2009 Page(s):878- 879

[42] Schmit, Herman, “ Programmable pipeline fabric utilizing partially global configuration buses”, US Patent 7263602, assignee - Carnegie Mellon University.

[43] Eric and et al, “Acceleratiing Video-Mining application Using Many Small General-Purpose Cores”, IEEE Micro, pp.8-21 September-October 2008.

[44] Yen-Kuang Chen, and et al, “High-Performance Physical Simulations on Next-Generation Architecture with Many Cores” Intel Technology Journal, pp. 251-262, Vol.1, Issue 3, August 2007

[45] Y. C. Jiang and J. F. Wang, “Temporal Partitioning Data Flow Graphs for Dynamically Reconfigurable Computing,” IEEE Transactions on VLSI, vol. 15, no. 12, pp. 1351-1361, Dec. 2007.

[46] F. Mehdipour, M. Saheb Zamani, M. Sedighi, “An integrated temporal partitioning and physical design framework for static compilation of reconfigurable computing systems,” The International Journal of Microprocessors and Microsystems, Elsevier, Vol. 30, No. 1, pp. 52-62, Jan. 2006.

[47] T. Wiegand, G. J. Sullivan, G. Bjntegaard, and A. Luthra, “Overview of the scalable video coding extension of the H.264/AVC standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 9, Sep. 2007.

[48] Kiefer Kuah, “Motion Estimation with Intel® Streaming SIMD Extensions 4 (Intel® SSE4)” Intel Software Solutions Group, April 2007.

[49] R. Krishna, S. Mahlke and T. Austin, “Memory system design space exploration for low-power, real time speech recognition,” in Proc. IEEE International Conference on Hardware/Software, codesign and System Synthesis, pp. 140-145, Sept. 2004.

[50] S. Yoshizawa, Y. Miyanaga, and N. Wada, “A low-power VLSI design of a ME based speech recognition system,” Circuits and Systems, 2002. MWSCAS-2002. The 2002 45th Midwest Symposium on, pp. 489-492, Aug. 2002.

[51] Ce zhu, Xiao Lin and Lap-Pui Chau, “Hexagonal-based search pattern for fast block motion estimation”, IEEE Transaction on Circuits and Systems for Video Technology, Vol.12, No.15, pp.349-355, 2002.

[52] Zhenxing Chen, Yang Song, Takeshi Ikenaga, Satoshi Goto, “Adaptive Search Range Algorithm for Variable Block Size Motion Estimation in H.264/AVC”, IEICE Fundamentals, Vol.E91-A, No.4 April 2008.

[53] Bjontegarrd G., “Calculation of Average PSNR Difference between RD-curve”, VCEG-M33.doc, In 13th VCEG Meeting, Austin, TX April 2001.
[54]Y. L. Xi, Ch. Y. Hao, Y. Y. Fan, and H. Q. Hu, ”A fast block-matching algorithm based on adaptive search area and its VLSI architecture for H.264/AVC,” IEEE Image Communication, No.8, pp. 626-646, Sep., 2006.

[55] L. Zhang, and W. Gao, ”Improved FFSBM algorithm and its VLSI architecture for variable block size motion estimaiton of H.264,” in Proc. of International Symposium on Intelligent Signal Processing and Communication Systems, pp. 445-448, 2005.