有效的群組式快速內部動態估測搜尋演算法

Abstract

在本文利用群組(group based)的方式改良了傳統的增強型六角搜尋演算法(enhanced hexagon-based search，EHEXBS)最後的內部搜尋這一個部分，本文利用了單調遞減特性，在點和點之間做出群組的分類，透過這些分類過後的群組找到最小的群組並且往最小的群組區域搜尋，在最小的群組區域去搜尋較佳的內部搜尋點。從實驗結果發現不僅可以減少計算量，並且可以得到更好的視訊品質。本研究把這個演算法稱之為有效的六角內部搜尋演算法(efficient hexagonal inner search, EHIS)和單點六角內部搜尋演算法(one-point hexagonal inner search, OPHIS)。從實驗數據發現，在EHIS和EHEXBS相比之下速度平均提升7.32%，減少MSE約3.12%，利用OPHIS和EHEXBS相比在速度上大約提升12.06%，而MSE大約降低2.29%。利用這個觀點並且應用到鑽石搜尋演算法(diamond search)，把群組過後的鑽石搜尋演算法稱之為中心偏向內部搜尋鑽石演算法（center-based inner search – diamond, CBIS-D)和傳統的鑽石搜尋演算法做比較，實驗發現在速度提升方面可以提升大約27.96%，在MSE的計算大約會提高1.31%，在兩者相較之下雖然MSE的計算提高一點，但是在速度的提升上是大幅提昇的。經過這樣的相比之下，雖然損失些微的視迅品質卻換來更快的編碼速度這樣的交換是有價值的。In this thesis，authors use group-based method to reduce the hexagonal search. A recent one, called enhanced hexagon-based search (EHEXBS), focused on reducing the number of search points in a fine-resolution inner search. In this thesis, authors propose a novel fast inner search algorithm, named efficient hexagonal inner search (EHIS), to further reduce the number of search points in the fine-resolution inner search. In EHIS, the distortion information of center point is well exploited. Experimental results show that EHIS performs better than the EHEXBS in terms of the number of search points or the mean squared error. The proposed algorithm, called as one-point hexagonal inner search (OPHIS), is based on the characteristic of monotonically decreasing of distortion on a local area. Compared with the enhanced hexagon-based search algorithm (EHEXBS), the EHIS and OPHIS not only decrease the number of search points, but also get a better video quality. Experimental results show that the speed improvement is about 7.32% and 12.06% on average respectively and the percentage decrease of the mean squared error is near to 3.12% and 2.29% on average respectively. Authors utilize the concept to the diamond search, called the new algorithm be center-based inner search – diamond (CBIS-D). Compared with the diamond search the speed improvement is about 27.96% on average and the percentage decrease of the mean squared error is 1.31% in our experiment.