臺灣博碩士論文加值系統

本研究提出一個高效率且低功耗的動態估測方法，並結合卡爾曼濾波器用於穩定估測干擾同時提供自適應搜尋方針。本方法主要基於方塊比對動態估測演算法並結合一位元轉換前處理。連續影像首先處理成一位元深度，做為高效率方塊比對的基礎，搜尋結果將交由卡爾曼濾波器或擴展行卡爾曼濾波器做進一步估測，一方面提供本文所提出的自適應搜尋方針所需的資訊，另一方面則同時用於穩定觀測干擾。本方法亦可結合至傳統的方塊比對動態估測法。各種改良型的一位元轉換也將在此介紹。在文章最後，即展示一個設計用於一位元轉換的影像前處理單元，一個使用 field-programmable gate array (FPGA) 開發板實作的system on a chip (SOC) 原型在本研究呈現。

This thesis presents a fast and low power consumption motion estimation method that combines with a Kalman filter based adaptive search scheme and movement stabilization algorithm. The main estimation technique we used is block-based motion estimation and an adoption of a one-bit transform (1BT) image pre-processing method. In order to achieve high effective block-matching processing, the image sequences are transformed into one-bit formats, and then we used Kalman filter in the proposed adaptive search strategies. Kalman filter can stabilize a noisy observation at the same time. The adaptive search strategies can be applied to the conventional block-based motion estimation. Several modifications proposed to improve 1BT are described. In the final, we present a hardware design of image 1BT pre-processing element, which implements on a system on a chip (SOC) prototype using a field-programmable gate array (FPGA) development board are also presented.

ABSTRACT i
摘 要 ii
誌 謝 iii
CONTENTS iv
LIST OF FIGURES vi
LIST OF ABBREVIATIONS viii
CHAPTER 1. INTRODUCTION 1
CHAPTER 2. BLOCK-BASED MOTION ESTIMATION AND ONE-BIT TRANSFORM 4
2.1 Block-Based Motion Estimation 4
2.2 Matching Criteria 5
2.3 Searching Procedures 6
2.3.1 Exhaustive Search 6
2.3.2 Three-Step Search 7
2.3.3 New Three-Step Search 8
2.4 Block Matching via One-Bit Transform 9
2.5 Operation of One-Bit Transform Based Motion Estimation 12
CHAPTER 3. OPTIMAL ESTIMATION 14
3.1 Dynamical System Representation 14
3.2 Elements of Bayesian Inference 15
3.3 Kalman Filter 16
3.4 Extended Kalman Filter 23
CHAPTER 4. MOTION ESTIMATION WITH OPTIMAL ESTIMATION 28
4.1 Adaptive Search Range 28
4.2 Target Dynamic Model 28
4.2.1 Linear Model 28
4.2.2 Non-Linear Model 29
4.3 Trajectory Stabilization 30
CHAPTER 5. FPGA IMPLEMENTATION OF ONE-BIT TRANSFORM 31
5.1 SOPC Configuration 32
5.2 Image Pre-Processing Elements 33
CHAPTER 6. EXPERIMENTAL AND SIMULATION RESULTS 38
6.1 Brightness Test Result 38
6.2 Adaptive Search Results 40
6.3 Stabilization Using Kalman Filter 42
6.3.1 Linear Dynamic Condition 43
6.3.2 Non-Linear Dynamic Condition 60
CHAPTER 7. CONCLUSION 65
REFERENCES 66
APPENDIX 70

[Altera Crop., 2010]
Altera Crop., "RAM-Based Shift Register (ALTSHIFT_TAPS) Megafunction User Guide," November 2010.
[Altera Crop., 2012]
Altera Crop., "Integer Arithmetic Megafunctions User Guide," February 2012.
[Arulampalam et al., 2002]
M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, "A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking," IEEE Transactions on Signal Processing, vol. 50, no. 2, pp. 174-188, February 2002.
[Bhaskaran and Konstantinides, 1997]
V. Bhaskaran and K. Konstantinides, Image and Video Compression Standars: Algorithms and Architectures: Kluwer, 1997.
[Ertürk and Ertürk, 2005]
A. Ertürk and S. Ertürk, "Two-Bit Transform for Binary Block Motion Estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 15, no. 7, pp. 938-946, July 2005.
[Ertürk, 2007]
S. Ertürk, "Multiplication-Free One-Bit Transform for Low-Complexity Block-Based Motion Estimation," IEEE Signal Processing Letters, vol. 14, no. 2, pp. 109-112, February 2007.
[Feng et al., 1995]
J. Feng, T. K. Lo, H. Mehrpour, and A. E. Karbowiak, "Adaptive Block Matching Motion Estimation Algorithm Using Bit-Plane Matching," In Proceedings of the 1995 International Conference on Image Processing, vol. 3, no. 23, pp. 496-499, October 1995.
[Gonzalez and Woods, 2008]
R. C. Gonzalez and R. E. Woods, Digital Image Processing, Third Edition: Prentice Hall, 2008.
[Jain and Jain, 1981]
J. Jain and A. Jain, "Displacement Measurement and Its Application in Interframe Image Coding," IEEE Transactions on Communications, vol. 29, no. 12, pp. 1799-1808, December 1981.
[Kalman, 1960]
R. E. Kalman, "A New Approach to Linear Filtering and Prediction Problems," Journal of Basic Engineering, vol. 82, pp. 35-45, March 1960.
[Koga et al., 1981]
T. Koga, K. Linuma, A. Hirano, Y. Iijima, and T. Ishiguro, "Motion-Compensated Interframe Coding for Video Conferencing," In Proceedings of the 1981 National Telecommunications Conference, pp. G5.3.1-G5.3.5., November/ December 1981.
[Musmann et al.,1985]
H. G. Musmann, P. Pirsch, and H. J. Grallert, "Advances in Picture Coding," In Proceedings of the IEEE, vol. 73, no. 4, pp. 523-548, April 1985.
[Natarajan et al., 1997]
B. Natarajan, V. Bhaskaran, and K. Konstantinides, "Low-Complexity Block-Based Motion Estimation via One-Bit Transforms," IEEE Transactions on Circuits and Systems for Video Technology, vol. 7, no. 4, pp. 702-706, August 1997.
[Po and Ma, 1996]
L. M. Po and W. C. Ma, "A Novel Four-Step Search Algorithm for Fast Block Motion Estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 3, pp. 313-317, June 1996.
[Reoxiang et al.,1994]
L. Reoxiang, Z. Bing, 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, no. 4, pp. 438-442, August 1994.
[Shi and Sun, 2008]
Y. Q. Shi and H. Sun, Image And Video Compression for Multimedia Engineering: Fundamentals, Algorithms, And Standards: Taylor & Francis Group, 2008.
[Srinivasan and Rao, 1985]
R. Srinivasan and K. Rao, "Predictive Coding Based on Efficient Motion Estimation," IEEE Transactions on Communications, vol. 33, no. 8, pp. 888-896, August 1985.
[Urhan and Ertürk, 2007]
O. Urhan and S. Ertürk, "Constrained One-Bit Transform for Low Complexity Block Motion Estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 17, no. 4, pp. 478-482, April 2007.
[Wong and Au, 1999]
P. H. W. Wong and O. C. Au, "Modified One-Bit Transform for Motion Estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, no. 7, pp. 1020-1024, October 1999.