最近鄰居的快速找尋法及其應用

Abstract

摘 要本論文針對數種最近鄰居找尋的應用提出了不同的演算法。所提出 的第一種方法是以參考點為基礎的快速找尋法，這個方法在記憶體上的需 求是N*(k/2 + 1), 這裡的N是指編碼簿的大小, k則是編碼簿的向量維度 。我們將其用來加速向量量化中LBG編碼簿的產生。第二種方法是用投影 的技巧來縮短影像壓縮裡的BTC/VQ 編碼簿的產生時間。這個方法在記憶 體上的需求上僅有2N。第三種方法是基於歌西不等式而導出來的判斷條件 。經由此單一的判斷條件，我們可踢除許多不需要計算距離的向量點，從 而大量節省了最近鄰居找尋的時間。利用這個方法所需要的記憶體也只 有1N。第四種方法則是由本人及一位碩士生，利用階層式使用"明可斯基 不等式"，發展出的一套加速 "動量估計"的糸統。由實驗結果可看出，所 提出的方法比一些廣為人知的方法(如PDE,SEA and TSS)，能省下更多的 計算時間。 ABSTRACTIn this dissertation, we propose several kinds of fast searching algorithmfor various applications of Nearest Neighbour (NN) search. The first one is a reference-point-based fast searching method with N*(k/2 + 1) memory overhead. Here, N is the number of codewords and k is the dimensionality of each codeword. This method is used to accelerate the LBG codebook generation process for Vector Quantization (VQ) design. As for the second one, when the high/low means generated by the Block Truncation Coding (BTC) image compression technique are to be quantized using VQ, the computation time to search for the nearesthigh/low mean sample can be reduced significantly by the second approach. Thememory overhead for this approach is 2N only. The third approach is a new approach that kicks out many impossible candidates by a single kick-out conditionderived from Schwarz Inequality. Due to the efficiency and simplicity of theproposed condition, a considerable saving of the CPU time needed to encode a data set (using a given codebook) can be achieved. The memory overhead is as low as 1N (which is quite competitive). The performance are demonstrated using the example of encoding images by vector quantization (without BTC) when a code-book is given. Finally, we introduce a fast motion estimation method based onthe Hierarchical Use of Minkowski's Inequality. Experimental results and complexity analysis are both given to show that the method outperforms many well-known methods such as PDE, SEA and TSS.