臺灣博碩士論文加值系統

本論文主要的目的是研究多維度的內插法，探討其效能、以及以矽智財實現時之可行性，已將內插法應用在多種領域。目前大多數的內插演算法，其運算公式複雜度高、運算耗費多時，因此硬體電路實現困難。我們提出一種基於模糊理論的新內插法，首先將取樣點之間的梯度進行內插，得到內插點的梯度估測值，再將此估測值換算為該內插點之高度。由於梯度代表了兩個取樣點函數值之關係，比起單純兩個取樣點函數值包含更多資訊，這種方法可加速運算速度，其運算公式複雜度低，因此特別適合用來進行多維度內插。本文以FPGA來實現影像內插法的硬體，並以浮點數四則運算來合成整個系統，整體架構則以管線化的方式運行。文中所探討效能指標將以使用四則運算所使用的個數、浮點數所使用的位元數、精確度及運算複雜度來做探討和比較，經過整體的比較後，發現我們的內插法其不論在效能、速度、硬體電路成本都優於其他內插法，這些都可顯示出此多維度內插法具有非常好的實用性。

This thesis mainly addresses High Performance Multi-dimensional Interpolation (HPMI) and its Silicon Intellectual Property (SIP) realization. Applications with efficiency and feasibility studies show that HMPI possesses better accuracy and lower complexity advantages compared to state-of-the-art interpolation algorithms. Therefore, hardware implementation of HPMI is much easier. Based on fuzzy set theory, we estimate gradient between each pair of sample points then calculate the height of the interpolating point. A gradient is a relation between each pair of sample points and contains more information than merely the function values of the two sample points. Based on this concept, we accelerate the HPMI interpolation process such that the whole multidimensional interpolation algorithm complexity is reduced. We implement image interpolation hardware with FPGA where floating-point arithmetic operations construct a pipeline data path architecture. The performance evaluation includes number of arithmetic operations, bit width of floating point operations, accuracy in image PSNR, and time complexity for comparison with state-of-the-art interpolation algorithms. We find that the HPMI outperforms all the other algorithms in efficiency, accuracy, and hardware costs and thus HPMI is much practical way in modern applications.

中文摘要 i
ABSTRACT iii
誌 謝 v
目 錄 vi
表目錄 viii
圖目錄 ix
一、緒論 1
1.1 研究動機與目的 1
1.2 模糊理論[3] [4] [5] 2
(A) 模糊集合與歸屬函數 2
(B) L-R 型歸屬函數(Membership Function) 3
(C) Takagi-Sugeno 的模糊推論法 4
(D) 解模糊化(Defuzzification) 4
1.3 論文架構 5
二、高效能內插演算法 6
2.1 非等距取樣與取樣演算法 6
2.2 1D-HPMI演算 6
2.3 2D-HPMI演算 9
三、高效能多維度內插法矽智財設計 20
3.1系統架構 20
3.2 系統撰寫規劃 20
(A) 影像讀取 20
(B) 16-bit浮點運算設計 21
(C) 2D-HPMI程式規劃 24
3.3 高階合成與RTL模型 25
(A) 四則浮點運算 25
(B) Pipeline架構 32
(C) 硬體效能 36
四、效能比較與分析 38
4.1 1D-HPMI效能分析 38
(A) 精確度比較 38
(B) 計算複雜度 41
4.2 2D-HPMI效能分析 42
(A) 精確度比較 42
(B) 計算複雜度 47
4.3 HPMI演算法化簡及效能 47
五、結論以及未來工作 50
參考文獻 51
附錄A 53
附錄B 58
作者簡歷 61

[1] Dong-U Lee, Ray C.C. Cheung, Wayne Luk, and John D. Villasenor, “Hardware Implementation Trade-Offs of Polynomial Approximations and Interpolations” IEEE Transactions on Computers, vol. 57, no. 5, pp 686-701, May. 2008.
[2] Dong-U Lee, John D. Villasenor, “A Bit-Width Optimization Methodology for Polynomial-Based Function Evaluation” IEEE Transactions on Computers, vol. 56, NO. 4, pp 567-671, April. 2007.
[3] 孫宗瀛，楊英魁，Fuzzy 控制理論、實作與應用(初版)，台北：全華科技圖書股份有限公司。
[4] 王文俊，認識Fuzzy(二版)，台北：全華科技圖書股份有限公司。
[5] 王進德，蕭大全，類神經網路與模糊控制理論入門，全華科技圖書股份有限公司。
[6] Lung-Jen Wang, Wen-Shyong Hsieh, and Trieu-Kien Truong, “A Fast Computation of 2-D Cubic-Spline Interpolation” IEEE Signal Processing Letter, vol. 11, no. 9, pp. 768-771, Sept. 2004.
[7] Weiss, Mark Allen, Data Structures and Algorithm Analysis in C++ (2nd Edition), Addison-Wesley, Nov. 1998.
[8] Shi-hau Liao, Interpolation and American options pricing, Master Thesis, Department of Finance, National Taiwan University, June. 2003.
[9] Alasdair McAndrew, An Introduction to Digital Image Processing with MATLAB.
[10] Chung-chi Lin, Ming-hwa Sheu, and Huann-keng Chiang, et al, “The Efficient VLSI Design of BI-CUBIC Convolution Interpolation for Digital Image Processing,” Circuits and Systems, 2008. ISCAS 2008. IEEE International Symposium on, pp. 480 - 483, May. 2008.
[11] M.A. Nuno-Maganda, M.O. Arias-Estrada, “Real-time FPGA-based architecture for bicubic interpolation: an application for digital image scaling,” International Conference on Reconfigurable Computing and FPGAs, Sept. 2005.
[12] 吳曾傳，陳思穎，林正基，…等，“高效能 Bi-cubic之影像解析度縮放硬體實現” 2007年系統雛型與電路設計創新應用研討會，Sept.2007.