臺灣博碩士論文加值系統

在本論文中，我們提出自己的六種影像動態估測法(方法A、方法B群、和方法C群)，我們的方法是根據全域搜尋演算法的概念從低位元解析度影像中，使用簡單的影像區塊比對法則，初步估測出一些候選的動態向量。之後我們將這一群候選的動態向量，依累計影像圖素強度差之絕對值的影像區塊比對法則，決定出最後的動態向量。此外，我們依據峰值訊號雜音比(PSNR)、平均資訊量(entropy)、和運算複雜度(Computational complexity)三種客觀的效能和效率量測法，將論文中我們所提出的六種影像動態估測法與傳統的全域搜尋演算法(Full search algorithm)、五種節省搜尋點數量之演算法(三步搜尋法、新三步搜尋法、四步搜尋法、交叉方向搜尋法、和區塊梯度遞降搜尋法)和運用適應性量化的低位元解析度影像動態估測法作一些效能的比較。傳統的全域搜尋演算法總是可以達到最佳化的估測結果，我們提出的六種影像動態估測法可以保有不錯之估測影像峰值訊號雜音比值及較低的差值影像之平均資訊量，方法B群和方法C群可以接近傳統的全域搜尋演算法的效能，方法A尚可接近運用適應性量化的低位元解析度影像動態估測法。另外在運算複雜度的比較上，傳統的全域搜尋演算法有最大的運算複雜度，我們的方法C-1之運算複雜度比運用適應性量化的低位元解析度影像動態估測法高，但其他五種方法可以有較低的運算複雜度。在運算複雜度的比較，五種節省搜尋點數量之演算法有過人的表現。依我們模擬的結果，我們發現了多重位元解析度的影像動態估測法，雖然有比節省搜尋點數量之演算法高的運算複雜度，但仍可以獲得比全域搜尋演算法運算複雜度降低約30%。重要的是多重位元解析度的影像動態估測法，在不同影像特性的估測可以比節省搜尋點數量之演算法有較佳並且穩定的峰值訊號雜音比值和平均資訊量的效能表現。

In this thesis, we describe some multi-bit-resolution motion estimation algorithms. Our proposed multi-bit-resolution motion estimation algorithms first reduce the bit resolution of the pixel values and then exhaustively match all possible block in the search window of low bit-resolution image to obtain a candidate motion vector (CMV) set by using a simple block-matching criterion to reduce the computational complexity and hardware cost. Secondly, the motion vector is refined on the positions of the CMV set by using the sum of absolute difference (SAD) block-matching criterion in the full-bit-resolution image. In our simulation, three measurement criteria, which are the peak-signal-to-noise ratio (PSNR) in the predicted image fidelity criterion, the entropy of prediction residue image, and the computational complexity of algorithm, are used to appraise the performance and the efficiency of the block estimation algorithms. The conventional full search algorithm always approach optimal performance in the PSNR and the entropy measurement. We could observe that our motion estimation methods, except our method A, obtain better performance in average PSNR and entropy measurement over the LRQME method proposed by Lee, Kim, and Chae in 1998. Their performance is close to that of the full search algorithm. We also observe that the motion estimation methods using multi-bit-resolution search schemes outperform the spare search algorithms (three-step search, new three-step search, four-step search, cross-search, and block-based gradient descent search algorithms) in average PSNR and entropy performance. In the comparison of algorithm’s efficiency, we could observe that the computational complexity of the full search algorithm is so large compared to the most other motion estimation algorithms. The computational complexity of our motion estimation C-1 is higher than that of the LRQME algorithm. Our method A has less the computational complexity than that of the LRQME algorithm. The computational complexities of our method group B and method C-2 are close to that of the LRQME algorithm. Moreover, the spare search algorithms have concise schemes from the viewpoint of the computational complexity.

Abstract (in Chinese)……………………………………………………i
Abstract (in English)…………………………………………………iii
Contents……………………………………………………………………v
List of Abbreviations………………………………………………viii
List of Figures…………………………………………………………ix
List of Tables…………………………………………………………xxx
Chapter 1 Introduction………………………………………………1
1.1 Motivation …………………………………………………1
1.2 Pixel-recursive algorithm ……………………………3
1.3 Block-matching algorithm ………………………………4
1.4 Block-matching criteria ………………………………6
1.4.1 Complex block-matching criteria ………………………6
1.4.2 Simple block-matching criteria ………………………9
1.5 Performance of block-matching algorithms ………11
1.6 Thesis organization ……………………………………16
Chapter 2 Multi-bit-resolution Motion Estimation …………17
2.1 Introduction ……………………………………………17
2.2 Low-resolution quantization motion estimation …18
2.2.1 Adaptive quantization into 2-bit resolution ……20
2.2.2 Computational complexity of LRQME method …………21
2.3 Our motion estimation method A ……………………24
2.3.1 2-bit absolute moment block truncation coding (AMBTC)
………………………………………………………………25
2.3.2 Motion estimation method A ……………………………27
2.3.3 Computational complexity of our method A …………29
2.4 Our motion estimation method group B ……………31
2.4.1 Adaptive quantization and supposed background……32
2.4.2 Motion estimation method group B ……………………32
2.4.2.1 Method B-1 …………………………………………………34
2.4.2.2 Method B-2 …………………………………………………35
2.4.2.3 Method B-3 …………………………………………………37
2.4.3 Computational complexity of our method group B …38
2.5 Our motion estimation method group C ……………40
2.5.1 LSB-truncated quantization ……………………………41
2.5.2 Motion estimation method group C ……………………42
2.5.2.1 Method C-1 …………………………………………………44
2.5.2.2 Method C-2 …………………………………………………45
2.5.3 Computational complexity of our method group C …45
Chapter 3 Simulation Results and Performance Comparison…49
3.1 Introduction ……………………………………………………49
3.2 Simulation results ……………………………………………49
3.2.1 Qualities of predicted video for various methods…50
3.2.2 Computational complexities for various methods …134
Chapter 4 Conclusions and Future Studies ……………………138
4.1 Conclusions ………………………………………………138
4.2 Future studies …………………………………………140
References ……………………………………………………………141
Vita ……………………………………………………………………144

[1] F. Dufaux and F. Moschemi, “Motion esimation techniques for digital TV: A review and a new contribution,” Proc. IEEE, vol. 83, pp. 858-876, June 1995.
[2] L. De Vos, M. Stegherr, and T. G. Noll, “VLSI architectures for the full-search blockmatching algorithm” ICASSP-89. International Conference on Acoustics, Speech, and Signal Processing, vol.3, pp. 1687 —1690, 1989.
[3] P. Lakamsani, B. Zeng, and M. Liou, “An enhanced three step search motion estimation method and its VLSI architecture” IEEE International Symposium on Circuits and Systems, vol.2, pp. 754 —757, 1996.
[4] M. Ghanbari, “The cross-search algorithm for motion estimation (image coding)”, IEEE Trans. on Communications, vol. 38, pp. 950 —953, July 1990.
[5] 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. on Circuits and Systems, vol. 8, pp. 369 —377, Aug. 1998.
[6] L. K. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding” IEEE Trans. on Circuits and Systems, vol. 6, pp. 419 -422, Aug. 1996.
[7] S. Lee, J. M. Kim, and S. I. Chae, “New motion estimation algorithm using adaptively quantized low bit-resolution image and its VLSI architecture for MPEG2 video encoding” IEEE Trans. on Circuits and Systems, vol. 8, pp. 734 -744, Oct. 1998.
[8] X. Song, T. Chiang, X. Lee, and Y. Q. Zhang, “Fast binary pyramid motion estimation” WCCC-ICSP 2000. 5th International Conference on Signal Processing Proceedings, vol. 2, pp. 1127 —1132, 2000.
[9] V. Fotopoulos and A. N. Skodras, “sMAE: an improved block matching criterion” IEEE International Conference on Electronics, Circuits and Systems, vol. 3, pp. 519 —522, 1998.
[10] M. D. Shieh, M. H. Sheu, and Y. C. Hsu, “MAPS: a new and efficient block-matching criterion for motion estimation” IEEE 39th Midwest symposium on Circuits and Systems, vol. 3, pp. 1393 —1396, 1996.
[11] M. J. Chen, L. G. Chen, T. D. Chiueh, and Y. P. Lee, “A new block-matching criterion for motion estimation and its implementation” IEEE Trans. on Circuits and Systems, vol. 5, pp. 231 —236, June 1995.
[12] H. Yeo and Y. H. Hu, “A novel matching criterion and low power architecture for real-time block based motion estimation” ASAP 96. Proceedings of International Conference on Application Specific Systems, Architectures and Processors, pp. 122 —130, 1996.
[13] Y. Baek, H. S. Oh, and H. K. Lee, “An efficient block-matching criterion for motion estimation and its VLSI implementation” IEEE Trans. on Consumer Electronics, vol. 42, pp. 885 —892, Nov. 1996.
[14] Y. Chan and S. Y. Kung, “Multi-level pixel difference classification methods” International Conference on Image Processing, vol. 3, pp. 252-255, 1995.
[15] H. Yeo and Y. H. Hu, “A novel architecture and processor-level design based on a new matching criterion for video compression” Workshop on VLSI Signal Processing IX, pp. 448 -457, 1996.
[16] R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation” IEEE Trans. on Circuits and Systems, vol. 4, pp.438-442, August 1994.
[17] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation” IEEE Trans. on Circuits and Systems, vol. 6, pp. 313 —317, June 1996.
[18] M. D. Lema and O. R. Mitchell, “Absolute moment block truncation coding and its application to color images” IEEE Trans. Communications, vol. 32, no. 10, Oct 1984, pp. 1148~1157.
[19] E. J. Delp and O.R. Mitchell, “Image compression using BTC” IEEE Trans. Communications, vol. 27, no.9, Sept. 1979, pp. 1335~1342.
[20] V. R. Udpikar and J. P. Raina, “Modified algorithm for block truncation coding of monochrone images” Electronics Letters, vol. 21, Sept. 1985, pp. 900~902