請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8140
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 簡韶逸(Shao-Yi Chien) | |
dc.contributor.author | Jia-Hong Hong | en |
dc.contributor.author | 洪嘉鴻 | zh_TW |
dc.date.accessioned | 2021-05-20T00:49:12Z | - |
dc.date.available | 2020-08-21 | |
dc.date.available | 2021-05-20T00:49:12Z | - |
dc.date.copyright | 2020-08-21 | |
dc.date.issued | 2020 | |
dc.date.submitted | 2020-08-18 | |
dc.identifier.citation | 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. S. Gu, L. Zhang, W. Zuo, and X. Feng, “Weighted nuclear norm minimization with application to image denoising,” in 2014 IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp. 2862–2869. R. Timofte, V. DeSmet, and L. VanGool, “A+: Adjusted anchored neighbor-hood regression for fast super-resolution,” in Computer Vision – ACCV 2014, D. Cremers, I. Reid, H. Saito, and M.-H. Yang, Eds. Cham: Springer Inter- national Publishing, 2015, pp. 111–126. R. Timofte, V. De Smet, and L. Van Gool, “Anchored neighborhood regression for fast example-based super-resolution,” in Proceedings of the IEEE International Conference on Computer Vision (ICCV), December 2013. C. Yang and M. Yang, “Fast direct super-resolution by simple functions,” in 2013 IEEE International Conference on Computer Vision, 2013, pp. 561–568.A. Buades, B. Coll, and J. . Morel, “A non-local algorithm for image denoising,” in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), vol. 2, 2005, pp. 60–65 vol. 2. J. Bentley, “Multidimensional binary search trees used for associative searching,” Commun. ACM, vol. 18, pp. 509–517, 1975. C. Silpa-Anan and R. Hartley, “Optimised kd-trees for fast image descriptor matching,” in 2008 IEEE Conference on Computer Vision and Pattern Recognition, 2008, pp. 1–8. L. Paulev, H. Jgou, and L. Amsaleg, “Locality sensitive hashing: A comparison123 of hash function types and querying mechanisms,” Pattern Recognition Letters, vol. 31, pp. 1348–1358, 08 2010. K. He and J. Sun, “Computing nearest-neighbor fields via propagation-assisted kd-trees,” in 2012 IEEE Conference on Computer Vision and Pattern Recognition, 2012, pp. 111–118. P. Geurts, D. Ernst, and L. Wehenkel, “Extremely randomized trees,” Machine Learning, vol. 63, pp. 3–42, 04 2006. E. O’neil, P. O’Neil, G. Weikum, and E. Zurich, “The lru–k page replacement algorithm for database disk buffering,” SIGMOD Record (ACM Special Interest Group on Management of Data), vol. 22, 10 1996. K. Kdzierski, M. Moreto, F. J. Cazorla, and M. Valero, “Adapting cache partitioning algorithms to pseudo-lru replacement policies,” in 2010 IEEE International Symposium on Parallel Distributed Processing (IPDPS), 2010, pp. 1–12. I. Talmi, R. Mechrez, and L. Zelnik-Manor, “Template matching with deformable diversity similarity,” in 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 1311–1319. N. Bonneel, J. Tompkin, K. Sunkavalli, D. Sun, S. Paris, and H. Pfister, “Blind video temporal consistency,” ACM Transactions on Graphics (SIGGRAPH Asia), 2015. [Online]. Available: http://liris.cnrs.fr/~nbonneel/temporalconsistency.htm | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8140 | - |
dc.description.abstract | 小方圖影像處理應用於影片領域相較於單純圖片領域,仍未發展成熟。其瓶頸在於快速的找到小方圖在資料庫裡的最近鄰居對應小方圖,來符合影片即時播放 的需求。近似最近鄰居搜尋法是一個該瓶頸的解決方法,其以搜尋品質換取處理 速度。這項技術運用小方圖在影片中的某種一致性和資料庫內小方圖彼此間的關係,來減少需要的搜尋對象數量。 我們提出一個近似最近鄰居搜尋演算法,相較於當前最先進的方法RIANN,在搜尋速度、時間和記憶體使用量都有進步。我們使用記錄局部資訊的查詢表來存取若干個鄰居,幫助進行快速搜尋,相較而言只有4%以下的記憶體使用量,而且有較小的頻寬利於增進處理速度。搜尋時間在一樣的搜尋品質下提升了六倍。 我們也提出了一個硬體架構設計基於上述演算法來進一步速,該系統藉由多格快取來增進讀取頻寬。該快取有與行暫存器差不多大小的合理記憶體成本。該硬體設計通過了台積電45奈米技術的驗證,達成了至少七倍的加速相較於實作在電腦上的演算法,證明了適宜於硬體實作的特性。 我們於數個應用當中展現出近似最近鄰居搜尋的用途,包括影片追蹤、影片時間調和,影片去雜訊。有著低記憶體使用量特性,透過我們的系統來實作這些應用在輕量裝置上是較為可行的。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-05-20T00:49:12Z (GMT). No. of bitstreams: 1 U0001-1808202001260100.pdf: 33120136 bytes, checksum: 8a95fda0b2a4c34deafa61c25d4e897c (MD5) Previous issue date: 2020 | en |
dc.description.tableofcontents | Acknowledgments (P. i) Abstract (P. iii) List of Figures (P. x) List of Tables (P. xix) Chapter 1 Introduction (P.1) 1.1 Patch-based Applications (P.1) 1.2 Contribution (P.5) 1.3 Thesis Organization (P.6) 2 Related Works (P.7) 2.1 Image-based Approximate Nearest Neighbor Search (P.7) 2.2 Video-based Approximate Nearest Neighbor Search (P.10) 2.3 Reference Set Construction (P.14) 3 Proposed Algorithm (P.16) 3.1 Introduction (P.16) 3.2 Video Nearest Neighbor Search (P.17) 3.3 Proposed Method (P.17) 3.3.1 Introduction (P.17) 3.3.2 Coherence in Video (P.18) 3.3.3 Chain Hashing (P.20) 3.3.4 Dual Mode Decision (P.25) 3.3.5 Summary (P.27) 4 Proposed Hardware Architecture (P.29) 4.1 Design Motivation and Challenge (P.29) 4.2 Proposed Architecture (P.34) 4.2.1 Line Buffer (P.35) 4.2.2 FIFO (P.37) 4.2.3 Processing Element (P.38) 4.2.4 Process Control (P.39) 4.2.5 Cache Update Policy (P.40) 4.2.6 Address Queue (P.44) 5 Experimental Results (P.50) 5.1 Experiment Configuration (P.50) 5.2 Comparison with Other Works (P.52) 5.3 Ablation Study and Parameter Setting (P.56) 5.4 Visualization and Comparison with RIANN (P.62) 5.5 Hardware Implementation Result (P.64) 5.6 Video Applications for Approximate Nearest Neighbor Search (P.69) 6 Conclusion (P.91) Bibliography (P.93) | |
dc.language.iso | en | |
dc.title | 適合硬體實作之演算法以及硬體架構設計應用於影片近似最近鄰居搜尋 | zh_TW |
dc.title | Hardware Friendly Algorithm and Hardware Architecture Design for Approximate Nearest Neighbor Search in Videos | en |
dc.type | Thesis | |
dc.date.schoolyear | 108-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 楊家驤(Chia-Hsiang Yang),丁建均(Jian-Jiun Ding),盧奕璋(Yi-Chang Lu),莊永裕(Yung-Yu Chuang) | |
dc.subject.keyword | 近似最近鄰居搜尋,小方圖類別影片應用,適合硬體實作之演算法, | zh_TW |
dc.subject.keyword | Approximate Nearest Neighbor Search,Patch-based Video Application,Hardware Friendly Algorithm, | en |
dc.relation.page | 99 | |
dc.identifier.doi | 10.6342/NTU202003901 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2020-08-19 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1808202001260100.pdf | 32.34 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。