此篇論文實現一全搜索塊匹配脈動陣列演算法。為簡化複雜的運算及大量的記憶體，本文對全搜索塊匹配演算法進行範圍限制以及預處理，最後將之實現於開發板上，本系統先將攝影機捕捉到的原始影像進行追蹤的預處理，透過縱向以及橫向的線追蹤其位置，並將結果轉換為灰階圖後分別寫入前幀(Previous Frame)以及後幀(Current Frame)，接著藉由脈動陣列對兩者進行全搜索塊匹配求出運動向量，整個系統使用的設備包括三個螢幕、一個開發板、一個攝影機，其中一個螢幕用來編譯及撰寫程式，一個用來控制RS232介面，最後一個用VGA與開發板連接並用來輸出結果。
我們實現兩種脈動陣列架構於全搜索塊匹配演算法，在同樣的規格下，兩種架構分別加快了大約五倍及十倍的速度，使整個系統達到及時的影音序列處理，並以640×480 的解析度、每秒60幀的影格率透過VGA輸出到螢幕上，此外，在進行預處理時透過避免使用消耗過多記憶體的演算法，本系統僅使用了板子上10%的內存，最後透過自行設計的簡易介面於PC端控制操作，因此，我們的系統為一高速、廉價且易於使用的影音序列處理系統。

This thesis implemented a full search block matching systolic array. In order to simplify complex operations and a large amount of memory, we limit the search range and preprocesses the input video to find the ROI, finally implements it on the DE2 development board. The system first performs the tracking preprocessing on the original image captured by the camera, traces its position through vertical and horizontal lines, converts the result to grayscale, and register the Previous Frame and the Current Frame respectively. Then, the systolic array is used to perform full search block matching on the two frames to obtain the motion vector. The equipment used in the system consists of three screens, a development board, and a camera. One screen is used to compile and write programs, another is used to control the RS232 interface, and the last one is connected to the development board with VGA and used to output the results.
We implemented two systolic architectures of full search block matching algorithm. Under the same specifications, the two architectures are accelerated by about five times and ten times, respectively. The system can output the motion vectors to the screen through VGA at 60 per second frame rate for 640x480 video sequences. In addition, by avoiding consuming too much memory during preprocessing, the system uses only 10% of the memory on the board. Finally, the operation of the system is controlled by a GUI on the PC side. Therefore, our system is a real-time, inexpensive and easy-to-use processing system for video sequences.

[1] Sahabuddin and E. Firmanto, "Estimasi motion vector menggunakan algoritma block-matching pada video animasi untuk memotivasi siswa di pendidikan tinggi", Progress, vol. 12, no. 1, pp. 13-20, Apr. 2020.

[2] K. Y. Kok and P. Rajendran, "A constraints based approach using ranking-gradient-similarity multi-block matching algorithm for computer vision", Apr. 2022.

[3] C. H. Hsieh and T. P. Lin, "VLSI architecture for block-matching motion estimation algorithm", pp. 169-175, Jun. 1992.

[4] C. Rajabai and S. Sivanantham, "Review on architectures of motion estimation for video coding standards", International Journal of Engineering and Technology 7(4.10): 928-934, 2018.

[5] F. Farahi and H. S. Yazdi. "Probabilistic Kalman filter for moving object tracking", Signal Processing: Image Communication 82, 115751, 2020.

[6] T. Mahalingam and M. Subramoniam, "A robust single and multiple moving object detection, tracking and classification", Applied Computing and Informatics, 2020.

[7] J. Shim, S. Lee and K. Cho, "Hybrid architecture of full-search block-matching motion estimation circuit for MPEG-4 encoder",2008 International SoC Design Conference, pp. I-226-I-229, 2008.

[8] C. A. Rahman and W. Badawy, "A quarter pel full search block motion estimation architecture for H.264/AVC",2005 IEEE International Conference on Multimedia and Expo, pp. 4, 2005.

[9] J. J. Lee and G.Y. Song, "Implementation of the super-systolic array for convolution", Proceedings of the ASP-DAC Asia and South Pacific Design Automation Conference, pp. 491-494, 2003.

[10] A. Yahi, K. Messaoudi, S. Toumi and E. B. Bourennane, "An optimized systolic array architecture for motion estimation based FSBMA used in H.264/AVC standard", 2013.

[11] G. Hegde “Implementation of systolic array architecture for full search block matching algorithm on FPGA”, 2009.

[12] M. Mohammadzadeh, M. Eshghi and M. M. Azadfar, "An optimized systolic array architecture for full search block matching algorithm and its implementation on FPGA chips", The 3rd International IEEE-NEWCAS Conference, pp.327-330, 2005.

[13] S. B. Pan, S. S. Chae and R. H. Park, "VLSI architectures for block matching algorithms using systolic arrays", in IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 1, pp. 67-73, Feb. 1996.

[14] G. Saldana and M. Arias-Estrada, "Compact FPGA-based systolic array architecture for motion estimation using full search block matching", 2007 3rd Southern Conference on Programmable Logic, pp. 231-234, 2007.

[15] N. Müller, Y. S. Wong, N. J. Mitra, A. Dai and M. Nießner. "Seeing behind objects for 3D multi-object tracking in RGB-D sequences", Proceedings of the IEEE/CVF Conference on Computer Vison and Pattern Recognition 2021.

[16] J. W. Tang, N. S. Husin, U. U. Sheikh and M. N. Marsono "FPGA-based real-time moving target detection system for unmanned aerial vehicle application", International Journal of Reconfigurable Computing. 1-16. 10.1155/2016/8457908, 2016.

[17] Terasic Technology Inc., "DE2-115 user manual" Terasic Technology Inc, 2012.

[18] Terasic Technology Inc., "TRDB-D5M hardware specification" Terasic Technology Inc, 2009.

[19] Terasic Technology Inc, "TRDB-D5M user manual," Terasic Technology Inc, 2017.