適合硬體實作之演算法以及硬體架構設計應用於影片近似最近鄰居搜尋

Hardware Friendly Algorithm and Hardware Architecture Design for Approximate Nearest Neighbor Search in Videos

洪嘉鴻(Jia-Hong Hong)

指導教授 ： 簡韶逸

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202003901

摘要

小方圖影像處理應用於影片領域相較於單純圖片領域，仍未發展成熟。其瓶頸在於快速的找到小方圖在資料庫裡的最近鄰居對應小方圖，來符合影片即時播放 的需求。近似最近鄰居搜尋法是一個該瓶頸的解決方法，其以搜尋品質換取處理 速度。這項技術運用小方圖在影片中的某種一致性和資料庫內小方圖彼此間的關係，來減少需要的搜尋對象數量。
我們提出一個近似最近鄰居搜尋演算法，相較於當前最先進的方法RIANN，在搜尋速度、時間和記憶體使用量都有進步。我們使用記錄局部資訊的查詢表來存取若干個鄰居，幫助進行快速搜尋，相較而言只有4%以下的記憶體使用量，而且有較小的頻寬利於增進處理速度。搜尋時間在一樣的搜尋品質下提升了六倍。
我們也提出了一個硬體架構設計基於上述演算法來進一步速，該系統藉由多格快取來增進讀取頻寬。該快取有與行暫存器差不多大小的合理記憶體成本。該硬體設計通過了台積電45奈米技術的驗證，達成了至少七倍的加速相較於實作在電腦上的演算法，證明了適宜於硬體實作的特性。
我們於數個應用當中展現出近似最近鄰居搜尋的用途，包括影片追蹤、影片時間調和，影片去雜訊。有著低記憶體使用量特性，透過我們的系統來實作這些應用在輕量裝置上是較為可行的。

關鍵字

近似最近鄰居搜尋 ； 小方圖類別影片應用 ； 適合硬體實作之演算法

並列摘要

Patched-based applications in video domain is a new research realm to be developed contrary to image domain. The bottleneck problem is to find the nearest neighbor among large amount of reference patches with fast online playing requirement. The approximate nearest neighbor search is a solution to achieve fast processing time with trade-off of lower searching quality. The technique utilize the coherency in video and the relationship between reference patches to reduce number of possible candidate patches for acceleration of searching process.
We proposed an approximate nearest neighbor search algorithm with improvements in terms of searching time, quality and memory consumption over state-ofthe-art method RIANN [1]. We use local hashing table to record k neighbors for each reference point to perform fast querying with only lower than 4% memory footprint and lower processing time benefit from low bandwidth. The querying time is 6 times faster in same searching quality.
We also proposed a hardware architecture based on our algorithm to accelerate the approximate nearest neighbor search further. The system is equipped with a multiple bins cache as on-chip memory to increase the bandwidth of loading reference patches. We design the system with reasonable cost for cache memory size about to the size of line buffer. The proposed hardware design is verified with TSMC 45nm iiitechnology in FHD specification and achieves over 7x acceleration for CPU version of the proposed algorithm, which proves the hardware friendliness feature of our method.
We show the effectiveness of the approximate nearest neighbor search in a few video applications, including video tracking, video temporal consistency, video denoising. With low memory footprint feature of our approximate nearest neighbor search approach, it is feasible to extend these applications on edge devices via our system.

並列關鍵字

Approximate Nearest Neighbor Search ； Patch-based Video Application ； Hardware Friendly Algorithm

參考文獻

N. Ben-Zrihem and L. Zelnik-Manor, “Approximate nearest neighbor fields in video,” in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 5233–5242.

C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman, “PatchMatch: A randomized correspondence algorithm for structural image editing,” ACM Transactions on Graphics (Proc. SIGGRAPH), vol. 28, no. 3, Aug. 2009.

I. Olonetsky and S. Avidan, “Treecann - k-d tree coherence approximate nearest neighbor algorithm.” in ECCV (4), ser. Lecture Notes in Computer Science, A. W. Fitzgibbon, S. Lazebnik, P. Perona, Y. Sato, and C. Schmid, Eds., vol. 7575. Springer, 2012, pp. 602–615. [Online]. Available:

http://dblp.uni-trier.de/db/conf/eccv/eccv2012-4.html#OlonetskyA12

S. Korman and S. Avidan, “Coherency sensitive hashing,” IEEE Trans. Pattern Anal. Mach. Intell., pp. 1607–1614, 2016.