陳鍾誠 | 教材 | 程式 | 文章 | 網站 | 留言版


微積分在影像處理中的用途 - 快速傅立葉轉換簡介

微積分在影像處理中的用途 - 快速傅立葉轉換簡介


摘要


許多學電腦的同學都不清楚數學在電腦中的用途，本文是『電腦與數學』系列中的一篇， 說明微積分中的泰勒級數、與其所衍生出來的各種級數 (尤其是傅立葉級數)、在影像處理中的 用途與價值，我們儘可能以最簡單而直接的方式，說明其中的數學概念，並在後續的 『Java 與影像處理』中以實際的電腦程式進行解析。

相關程式

  1. FFT.java in Dept. Computer Science, Princeton -- http://www.cs.princeton.edu/introcs/97data/FFT.java.html
  2. Complex.java in Dept. Computer Science, Princeton -- http://www.cs.princeton.edu/introcs/97data/Complex.java.html

簡介

微積分概念中的微分，具有許多神奇的應用，其中基於多項式不斷微分概念的泰勒級數， 更成為函數逼近論的基礎，函數逼近方法中最重要的傅立葉轉換，更成為影像處理的神奇工具， 本文將說明微積分、泰勒級數、函數逼近、傅立葉轉換在影像處理中的地位與用途。

微分與泰勒級數

一般的連續函數通常可以不斷的進行微分，因此、就可以用多項式來逼近該函數，其背後的想法是：

『如果我想用一個多項式來逼近函數，應該如何做呢？』

關於這個問題、如果我們直接將函數表示成多項式，可改寫如下：


f(x) = c0 + c1 x + c2 x2 + ...+ ck xk+...=∑
∞
k=0
 ck*xk --- (1)

然而、這些 c0, c1, ... 等係數，到底應該是多少呢？關於這個問題，必需使用函數逼近法，所謂的函數逼近法， 就是利用微分的概念，對於一個指定函數 f(x)，在某特定點附近不斷取微分的方法。

根據算式 (1) 不斷進行微分，可以導出下列算式：
f'(x) =
d f(x)
dx
 = c1+c2*2*x+c3*3*x2+c4*4*x3+...
f''(x) =
d f'(x)
dx
 = c2*2*1+c3*3*2*x+c4*4*3*x2+...
f'''(x) =
d f''(x)
dx
 = c3*3*2*1+c4*4*3*2*x+...
...
fk(x) =
d fk-1(x)
dx
 = ck k!+ck+1 (k+1)! x+...

於是、根據上述最後一個通用算式，若在 x 趨近於 0 時，可捨棄具有 x 的項目 (因為 x 非常接近0，x, x2, ... 都很小、捨棄一點點無所謂啦)， 於是我們就發現下列關係：

ck =
fk(0)
k!

於是、我們就可以將這些係數 ck 套回算式 (1)，而得到下列算式 (2)：

f(x) = f(0) +
f'(0)
1!
 x +...+
fk(0)
k!
 xk+...=∑
∞
k=0
fk(0)
k!
 xk --- (2)

這就是所謂的泰勒級數，又稱泰勒展開式。

上述的論述是針對函數 f(x) 在接近 0 的地方進行逼近的結果，對於在接近 a 的地方，泰勒級數將修改如下：

f(x) = f(a) +
f'(a)
1!
 x +...+
fk(a)
k!
 xk+...=∑
∞
k=0
fk(a)
k!
 xk --- (3)

eix 的泰勒級數

傅立葉轉換其實就是一種泰勒級數，是自然對數 e (或稱尤拉數) 的虛數次方 eix 的泰勒級數，天啊! 又自然對數又虛數，怎麼這麼抽象 ! 這就是數學厲害的地方，實數成立後就想辦法證明看看虛數可不可以用， 深入探討後就發現微分函數中的自然對數的虛數次方更好用，以下我們就將來探討這個神奇的函數。

若我們將泰勒級數公式 (2) 中的 f(x) 代換成 eix，則將會得到下列函數：
eix = 1 + i
x
1!
 -
x2
2!
 - i
x3
3!
 + ... --- (4)

天啊、所有的 fk 通通都不見了，只剩奇數次方中的負號與 i 還存在，好簡潔的公式。

更神奇的是、若我們將 sin(x) 與 cos(x) 的泰勒級數寫出來，就會發現下列泰勒展開式：

cos(x) = 1 -
x2
2!
 +
x4
4!
 + ... --- (5)
sin(x) =
x
1!
 -
x3
3!
 +
x5
5!
 + ... --- (6)

根據這 (4) (5) (6) 三個算式仔細比較，我們可以發現下列驚人的事實：

eix = cos(x) + i*sin(x) --- (7)

這樣的結果令人驚訝的原因是，原本不相關的東西竟然透過泰勒級數連結起來了，數學果真厲害。

以三角函數逼近一般函數 f(x)

假設我們希望用三角函數 sin(nx) 與 cos(nx) 逼近一個函數 f(x)，我們可以將這個式子寫成如下算式：

f(x) =
a0
2
 + ∑
∞
n=-∞
 (an cos(nx)+ bn sin(nx)) --- (8)

由於 (7) 我們可將三角函數轉為自然指數如下：
cos(nx) + i sin(nx) = einx

因此、若我們允許系數 b 包含虛數，則我們可將算式 (8) 寫成如下的自然指數。
f(x) = ∑
∞
n=-∞
 Fn einx --- (9)

算式 (9) 就成為傅立葉級數，也就是利用 sin(nx) 與 cos(nx) 逼近函數的一種方法。

再根據類似推導算式 (2) 泰勒展開式的方法，我們可以導出傅立葉級數的係數如下：

Ft =
1
2π
 ∫
π
-π
 f(x) ei t x dx --- (10)

若是在不連續的狀況之下，上述公式要改寫成總和式如下：

Fn =
1
N
 ∑
N-1
k=0
 f(k) e-ik 2π n/N -- (11)

這個係數 Fn 的計算方法，就稱為傅立葉轉換，其中 Fn 與 an, bn 的關係如下：
F0 =
1
2
 a0Fn=
1
2
 (an-ibn)F-n =
1
2
 (an+ibn)
a0 = 2 c0an=Fn+F-nbn = i(Fn-F-n)

到目前為止，我們已經將傅立葉轉換之所以可以用來逼近函數的數學公式說明清楚了，傅立葉轉換就是用來逼近 f(x) 函數的 sin(nx), cos(nx) 項的係數，因此、只要算出這些係數，就可以重新組合出 f(x)。
以下圖形代表以傅立葉級數進行逼近時頻率為 0, 1, 2, ...,n, 之情況 ：



以下圖形代表利用 sin(nx) 的波形去組合出函數 f(x) 的一個情況，其中：


上圖中：
紅色線代表 c1 sin(1x)
黃色線代表 c1 sin(1x)+c2 sin(2x)
綠色線代表 c1 sin(1x)+c2 sin(2x)+c3 sin(3x)
藍色線代表 c1 sin(1x)+c2 sin(2x)+c3 sin(3x)+c4 sin(4x)
紫色線代表 c1 sin(1x)+c2 sin(2x)+c3 sin(3x)+c4 sin(4x)+c5 sin(5x)


根據這種方法、前面的項數加得越多，逼近的程度就越高、越精確。

而 sin(nx) , cos(nx) 的特性，就是在 n 愈小時越平滑，這些平滑的函數可以用來表示圖形中變化較小的部份，當 n 越大時， 變化越快且頻率越高，因此、 n 大的部分代表了影像快速的細微變化，這些細微變化常是人眼的視覺所自動忽略的，因此、 可以將高頻的部分省掉，留下低頻的部份，影像看起來仍然會非常接近原來的影像，這就是電腦進行影像壓縮所用的方法。

另外、若要從以轉換後的係數 Fn 再轉回原來的 an, bn, 則可進行下列反向計算：

連續的狀況：
f(t) = ∫
∞
-∞
 F(x) ei 2πxt dt --- (12)

不連續 (離散) 的狀況：
f(n) = ∑
N-1
k=0
 F(k) ei 2πk
n
N
 --- (13)

結語

本文中我們介紹了如何利用多項式的不斷微分法導出泰勒級數，接著列出 ei x 函數 的微分，並與 cos(x) + i*sin(x) 比較以導出傅立葉級數，然後利用傅立葉級數對影像進行轉換， 而得到一個基於 cos 與 sin 的係數組，這個係數組所代表的乃是利用 sin, cos 的波形對影像 進行逼近的結果，因而、當我們從中取出低頻率係數而捨棄高頻率係數時，就得到了一個非常近似 於原始影像，但節省許多儲存空間的表示法，這幾乎就是所有影像壓縮技術的基礎。



作者：陳鍾誠 E-mail:ccc@kmit.edu.tw。
Creative Commons License

本著作係採用創用 CC 「姓名標示─相同方式分享 2.5 台灣版」授權條款釋出。

大學課程網 | 手機入口網