在本文利用群組(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.

[1] J. R. Jain and A. K. Jain,“ Displacement measurement and its application in interframe image coding,” IEEE Transactions on Communication, vol. COM-29, no. 12, pp. 1799-1808, Dec. 1981.
[2] J. Lu and M. L. Liou, “A simple and efficient search algorithm for block-matching motion estimation,” IEEE Trans. Circuits and Systems for Video Technology, vol. 7, pp. 429-433, Apr. 1997.
[3] Lai-Man Po and Wing-chung Ma, “A novel Four-step search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video technol., vol. 6. NO. 3, JUNE 1996.
[4] R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, pp. 438-442, Aug., 1994.
[5] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Trans. Image Processing, vol. 9, pp. 287-290, Feb. 2000.
[6] J. Y. Tham, S. Ranganath, M. Ranganath and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation,” IEEE Trans. Circuits and Systems for Video Technology, vol. 8, pp.369-377, Aug. 1998.
[7] Chun Ho Cheun and Lai-Man po, “A novel cross-diamond search algorithm for fast block motion estimation”, IEEE Trans. Circuits and Systems, vol. 12, pp 1168 – 1177, Dec. 2002.
[8] Chi- Wai , Lai-Man po and Chun Ho Cheun, “A new cross-diamond search algorithm for fast block matching motion estimation” IEEE Int. Conf. Neural Networks & Signal Processing Nanjing, China, December 14-17,2003.
[9] Chun Ho Cheun and Lai-Man po, “Novel cross-diamond-hexagonal search algorithms for fast block motion estimation”, IEEE Trans. on Multimedia, vol. 7, pp 16 – 22, Feb. 2005.
[10] Lap-Pui Chau and Ce Zhu “Afast octgon-based search algoritm for motion estimation” signal processing 83 (2003) 671-675.
[11] C. Zhu, X. Lin and L. P. Chau, “Hexagon-based search algorithm for fast block motion estimation,” IEEE Trans. Circuits and Systems for Video Technology, vol. 12, pp. 349–355, May 2002.
[12] Ce Zhu, Xiao Lin, Lap-Pui Chau, Hock-Ann Ang, Choo-Yin Ong, “An optimized diamond search algorithm for block motion estimation ”, IEEE Int. Symp. Circuits and Systems (ISCAS), vol 2, pp.26-29, May 2002.
[13] Ce Zhu, Xiao Lin, Lap-Pui Chau, Hock-Ann Ang, Choo-Yin Ong, “ Efficient inner search for faster diamond search ”, Signal Processing 84 (2004) 527 – 533.
[14] C. Zhu, X. Lin, L.-P. Chau and L.-M. Po, “An enhanced hexagonal search algorithm for block motion estimation”, IEEE Int. Symp. Circuits and Systems (ISCAS), Bangkok, Thailand, vol. 2, pp.392-395, May 2003.
[15] C. Zhu, X. Lin, L. P. Chau, “Enhanced hexagon search for fast block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 14, no. 10, pp. 1210–1214, Oct. 2002.
[16] 許益賓「數位相機之快速動態估測演算法設計」國立台灣師範大學機電科技研究所碩士論文，2004。
[17] Chorng-Yann Su, Yi-Pin Hsu, Cheng-Tao Chang, “Efficient hexagonal inner search for fast motion estimation,” IEEE International Conference on Image Processing, ICIP2005, 11-14 Sep. 2005, Genoa, Italy.
[18] Chorng-Yann Su and Cheng-Tao Chang, “One-point hexagonal inner search for fast motion estimation”, International Symposium on Visual Computing, Dec. 5-7, 2005, Lake Tahoe, Nevada, USA.
[19] http://www.xvid.org