本研究針對數位相機中所預設的動態估測演算法(三步搜尋演算法)進行改良。三步搜尋演算法雖然在實作上相當容易，但是在計算方面仍然佔據過多的計算量。為了減低計算量，鑽石形搜尋演算法被提出。雖然鑽石形搜尋演算法在PSNR與計算量上比三步搜尋演算法還好，但是其不規律的搜尋樣式卻是一個缺點。近年來，六角形搜尋演算法被提出來。原因為其搜尋樣式較趨向圓形，形成一個較規律的搜尋樣式，並且在計算量與畫面品質方面有更好的效果。在另ㄧ方面，此數位相機中含有一個硬體加速器，稱之為IMX。IMX在使用上有一個嚴格的限制，就是搜尋的樣式必須是規律的。因此利用六角形的特點並配合相機硬體的限制而提出一個適用於此相機平台的快速搜尋演算法，稱為預測式線性類六角形搜尋演算法。由實驗結果顯示，在計算量方面比原本的三步搜尋演算法平均減少42.07%的計算量，而在PSNR方面卻僅僅損失8.05%，於人類視覺上是可以被接收的。

This research aims to improve the three-step search algorithm (TSS) used in a digital still camera (DSC). Although the TSS is very convenient for programming, its computation is still too much. In order to reduce computation, diamond search (DS) is proposed. Even if the DS has a fine results in PSNR and the number of search points over the TSS, its search pattern is more complicated than the TSS. In recent years, hexagonal-based search algorithm (HEXBS) is proposed. Because its geometry shape tends to a circle and its search pattern is more regular than the DS, it performs better than the other algorithms in term of the PSNR value and the number of search points. On the other hand, the DSC includes a hardware accelerator called as IMX. The IMX has a strictly restriction in which the search pattern must be regular. Based on this restriction of DSC, we design a new algorithm called as predictive linear hexagon-like search algorithm (PLHLS). By experimental results, the PLHLS can efficiently reduce the amount of computation about 42.07% and only loses 8.05% in PSNR value compared with the TSS. In the view points of human vision, this result is acceptable.

[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]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.
[3]X. Jing and L. P. Chau, “An efficient three-step search algorithm for block motion estimation,” IEEE Transactions on Multimedia, vol. 6, no. 3, pp. 435-438, June 2004.
[4]J. Y. Tham, S. Ranganath, M. Ranganath and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, pp.369-377, Aug. 1998.
[5]C. Zhu, X. Lin, L. P. Chan, H. A. Ang, C. Y. Ong, “Efficient inner search for faster diamond search,” Signal Processing, pp.527-533, 2004.
[6]C. Zhu, X. Lin, L. P. Chau, ”Hexagon-based search pattern for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 15, pp. 349–355, May 2002.
[7]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.
[8]J. Lu and M. L. Liou, “A simple and efficient search algorithm for Block-Matching motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 7, no.2, pp. 429–433, Apr. 1997.
[9]L. P. Chau and C. Zhu, “A fast octagon-based search algorithm for motion estimation,” Signal Processing, pp.671-675, 2003.
[10]F. H. Cheng and S. N. Sun, “New fast and efficient two-step search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, no. 7, pp.977-983, Oct. 1999.
[11]H. J. and L. Zhang, ” A new cross diamond search algorithm for block motion estimation,” Proceeding of IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 3, pp. 357-360, May 2004.
[12]C. W. Lam, L. M. Po, C. H. Cheun, ” A novel kite-cross-diamond search algorithm for fast block matching motion estimation,” Proceeding of IEEE International Symposium on Circuits and Systems, vol. 3, pp. 729-732, May 2004.
[13]S. R. Subramanya, H. Patel, I. Ersoy,” Performance evaluation of block-based motion estimation algorithms and distortion measures,” Proceeding of International Conference on Information Technology: Coding and Computing, vol. 2, pp. 2-7, Apr. 2004.
[14]K. L. Chung and L. C. Chang, “A new predictive search area approach for fast block motion estimation,” IEEE transactions on Image Processing, vol. 12, no. 6, pp. 648-652, June 2003.
[15]L. Louro, P. Santos, N. Rodrigues, V. Silva, S. Faria,“ DSP performance evaluation for motion estimation,” Proceeding of IEEE Symposium on Signal Processing and Its Applications, vol.2, pp. 137-140, July 2003.
[16]Y. W. Huang, S. Y. Ma, C. F. Shen, L. G. Chen, ” Predictive line search: an efficient motion estimation algorithm for MPEG-4 encoding systems on multimedia processors,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, issue: 1, pp. 111–117, Jan. 2003.
[17]TMS320DM310 Digital Media DSP — CPUs and Peripherals, Texas Instruments, version 2.0, 2003.
[18]I. Richardson, H.264 and MPEG-4 video compression. Wiley, 2003.
[19]Naim Dahnoum, Digital signal processing implementation using the TMS320C6000TM DSP platform. Prentice Hall, 2002.
[20]Information Technology — Coding of Audio-Visual Objects — part 2：Visual, ISO/IEC Standard 14496-2, 2004.
[21]R. Kamal, Embedded systems, architecture, programming and designed. McGraw-Hill, 2003.
[22]http://www.xvid.org
[23]http://www.ti.com