画像処理とフーリエ変換のまとめ
(
振り返ってみる
)
桂田 祐史
2015
年
1
月
16
日
1
Fourier
級数
• f : R → C が周期 2π で、ある程度の滑らかさがあるとき、 f (x) = a0 2 + ∞ ∑ n=1 (ancos nx + bnsin nx) , (1) an= 1 π ∫ π −π f (x) cos nx dx, bn = 1 π ∫ π −π f (x) sin nx dx (2)が成り立つ。an, bn を f の Fourier 係数, (3) の右辺を f の Fourier 級数と呼ぶ。— こ
れは「数学とメディア」でやったこと。周期を一般にするとか、奇関数 or 偶関数の場 合とか、練習問題 No. 1 にあることはこの講義では本当は前提としたい…) • 特に、練習問題の問 5, 宿題の問 1 のような、簡単な関数の Fourier 級数を計算で求める ことが出来るように。 • 複素数バージョンがある。 f (x) = ∞ ∑ n=−∞ cneinx (3) cn= 1 2π ∫ π −π f (x)e−inxdx. (4) cn と an, bn との関係 (練習問題 問 9) cn= 1 2(an− ibn) (n > 0) 1 2a0 (n = 0) 1 2(a−n+ ib−n) (n < 0). これから分かるように、f が実数値 ⇔ (∀n ∈ Z) c−n = cn. (後の音声の信号を離散フーリエ変換した時の CN−n = Cn はここから来ている。|Cn| を プロットすると左右対称になるのはそのせい。)
• Fourier 級数の収束のための条件で、(a) 区分的 C1 級, (b) 連続で区分的 C1 級, (c) f が 2乗可積分、というものがあると説明した。(a), (b) はぜひ理解すること。(c) について は努力目標 (L2 は内積を考える場合に都合の良い空間であるが、収束に関しては少し分 かりづらいかもしれない)。 – (a) 区分的 C1 級ならば、任意の連続点 x で収束する: f (x) = a0 2 + ∞ ∑ n=1 (ancos nx + bnsin nx) . これは次のことを意味する。 f (x) = lim N→∞ ( a0 2 + N ∑ n=1 (ancos nx + bnsin nx) ) . 不連続点 x では片側極限の平均値に収束する: f (x + 0) + f (x− 0) 2 = a0 2 + ∞ ∑ n=1 (ancos nx + bnsin nx) . (不連続点の近傍では Gibbs の現象が起こる。) – (b) 連続かつ区分的に C1 級ならば一様収束する: lim N→∞x∈[−π,π]sup f (x)− ( a0 2 + N ∑ n=1 (ancos nx + bnsin nx) ) = 0. – (c) 2乗可積分ならば (この意味は後述)、(2 次) 平均収束する: lim N→∞ f− ( a0 2 + N ∑ n=1 (ancos nx + bnsin nx) ) = 0. (この (c) を今回のテストの問題のネタにはしない。) • ∫ π −π|f(x)| 2 dx <∞ である関数を (−π, π) で 2 乗可積分と呼ぶ。これは緩い条件である (区分的に滑らかでも OK, 単に [−π, π] で連続でも OK)。このとき 2 乗可積分関数の全 体を L2(−π, π) で表す。φ, ψ ∈ L2(−π, π) とするとき、 (φ, ψ) = ∫ π −π φ(x)ψ(x)dx で内積が定義できる。また ∥φ∥ =√(φ, φ) = ∫ π −π|φ(x)| 2 dx. Fourier 級数に現れる関数系 {φn} は、この内積について直交系をなす。すなわち n ̸= m ⇒ (φn, φm) = 0.
• {φn} が直交系であるとき、f = ∑ n cnφn となっていれば、cn= (f, φn) (φn, φn) である。 (非常に重要: これが自分で式変形して導出できること。) (非常に重要: Fourier 級数の an = 1 π ∫ π −π· · · , bn = 1 π ∫ π −π· · · , cn = 1 2π ∫ π −π· · · という式 はこの観点から理解できる。) • 直交系 {φn} が、任意の f に対して f =∑ n cnφn を満たすとき、完全であるという。Fourier 級数に現れる関数系は完全な直交系である。 例えば
(i) {cos nx}n≥0∪ {sin nx}n∈N は完全な直交系である。 (ii) {einx}n∈Z は完全な直交系である。 (この辺は、「数学とメディア」任せで、この講義では深く追求しなかった。証明に手間 取り、他とのバランスが悪くなるので…) • {φn} が正規直交系であるとは、 (φn, φm) = δnm def. = { 1 (n = m) 0 (n̸= m) が成り立つことをいう (もちろん正規直交系は直交系である)。 {φn} が直交系で、どれも 0 でないとき、ψn:= 1 ∥φn∥ φn とおくと、{ψn} は正規直交系 になる。 (a) √1 2π, 1 √ π cos nx, 1 √ πsin nx (n ∈ N) は完全な正規直交系である。 (b) √1 2πe inx (n ∈ Z) は完全な正規直交系である。(∵ φ n(x) = einx (n ∈ Z) とすると き、∥φn∥ = √ 2π) • {φn} が正規直交系であるとき、f = ∑ n cnφn となっていれば、cn = (f, φn)である。 • {φn} が正規直交系であるとき、Bessel の不等式 ∑ n |(f, φn)|2 ≤ ∥f∥2 が成り立つ。{φn} が完全な正規直交系であれば Parseval の等式 ∑ n |(f, φn)|2 =∥f∥2
が成り立つ (ピタゴラスの定理のようなもの)。 (収束に関わる基本的な定理の証明の鍵となる命題であるが、この講義では追求しなか った。) • 微分との関係。cn= bf (n)と書くことにすると、部分積分をすることで b f′(n) = 1 2π ∫ π −π f′(x)e−inxdx =− 1 2π ∫ π −π f (x)· (−in)e−inxdx = in bf (n). (後で見るように、Fourier 変換等でも似たことが成り立つ。関数がたくさんの回数微分 できるほど、Fourier 級数の収束は速く (良く) なるという性質の根拠となる重要な事実。 微分方程式への応用でも重要である。この講義では本来そうあるべきよりは、軽い扱い になっている。)
2
Fourier
変換
• f : R → C の Fourier 変換とは Ff(ξ) = bf (ξ) := √1 2π ∫ ∞ −∞ f (x)e−ixξdx (ξ ∈ R) で定義される関数 Ff = bf のことを言う。 • g : R → C の逆 Fourier 変換 (共役 Fourier 変換) とは F∗g(x) = eg(x) := √1 2π ∫ ∞ −∞ g(ξ)eixξdξ (x∈ R) で定義される関数 F∗g =eg のことを言う。 • (非常に重要) 名前の通り Fourier 変換の逆変換は逆 Fourier 変換である。すなわち F∗Ff = f, FF∗g = g. 最初の式は、Fourier 変換を逆 Fourier 変換すると元に戻る、つまり f (x) = √1 2π ∫ π −π b f (ξ)eixξdξ (反転公式) ということであり、 Ff = g ⇒ F∗g = f ということでもある。 • Ff(ξ) = F∗f (−ξ), F∗f (x) =Ff(−x). • 連続関数でも Fourier 変換が存在するとは限らない (Fourier 変換は広義積分だから)。計 算も難しいが、次の 3 つ (数えようによっては 5 つ) だけは出来るようにしておくこ と (公式の暗記はせず、導き方を覚えよう。授業でも板書したし、講義ノートにも書い たし、宿題 3 の解説にも詳しく書いておいた。)。いずれも a > 0 とする。(i) 簡単な計算で F[e−a|x|](ξ) = √ 2 π a ξ2+ a2. (反転公式から、これはF∗ [√ 2 π a ξ2+a2 ] (x) = e−a|x|ということであるから、Ff(ξ) = F∗f (−ξ) を用いて) F [ 1 x2+ a2 ] (ξ) = 1 a √ π 2e −a|ξ|. (これを直接計算で示すには、複素関数論などを使わないと難しい。) (ii) f (x) = { 1 (|x| < a) 0 (それ以外) とするとき、簡単な計算で Ff(ξ) = √ 2 π sin(aξ) ξ . これも反転させて F [ sin(ax) x ] (ξ) = √ π 2 × 0 (|x| > a) 1 (|x| < a) 1 2 (x =±a) (x =±a の場合は、不連続点では、片側極限の平均に収束する、という性質による。) 授業では上のように説明したが、次のようにするのが良いかも。 f (x) = 1 2a (|x| < a) 0 (それ以外) とするとき Ff(ξ) = √1 2π sin(aξ) aξ = 1 √ 2πsinc(aξ), F [sinc(ax)] (ξ) = √2π× 0 (|x| > a) 1 2a (|x| < a) 1 4a (|x| = a) と書いたほうが良いのかも。
ただし sinc は sinc x = sin x
x で定義される関数である (テキストによる違いがある)。
(iii) Gaussianの Fourier 変換:
F[e−ax2 ] (ξ) = √1 2ae −ξ2 4a. (この公式の導出は講義ノートを見よ。)
• Fourier 変換の基本的な性質 (微積分の良い応用問題なので、「計算して1確かめよ」、と
いう問題を出そうかな。授業でも板書したし、講義ノートにも書いてある。)
F [f1+ f2] =Ff1+Ff2.
F [λf] = λFf.
F [f(x − a)] (ξ) = e−iaξFf(ξ).
F[f (x)eiax](ξ) =Ff(ξ − a).
F [f(ax)] (ξ) = 1 |a|Ff ( ξ a ) . F [f′(x)] (ξ) = (iξ)Ff(ξ). d dξFf(ξ) = −iF [xf(x)] (ξ). (これらの公式は、他の “Fourier 変換” にも拡張されるものが多い。)
3
離散
Fourier
変換
• 周期 T の周期関数 f : R → C に対して、その Fourier 係数 cn = 1 T ∫ T /2 −T/2 f (x)e−2πinx/Tdx = 1 T ∫ T 0 f (x)e−2πinx/Tdx (n∈ Z) を近似的に求めたい。 h := T N, ω := e 2πi/N = eih, x j = jh, fj = f (xj) とおく (要するにサンプリングしたわけだ)。{fj} は周期 N の周期数列で、cn を台形則 で近似計算したもの Cn= 1 N N∑−1 j=0 fjω−nj を f の (N 項) 離散 Fourier 係数と呼ぶ。 • ω の基本的な性質: 1 の原始 N 乗根, i.e. ωN = 1, 1≤ m ≤ N − 1 ⇒ ωm ̸= 1. N∑−1 j=0 ωmj = { N (m≡ 0 (mod N)) 0 (それ以外). 1厳密に証明しようとすると、積分の存在条件などが問題になり難しい。• {Cn} は周期 N の周期数列で、任意の n ∈ Z に対して Cn = ∑ k≡n ck= cn+ ∞ ∑ p=1 (cn+pN + cn−pN) . |n| が (N と比較して) 小さいとき、Cn は cn を近似していると期待できる。例えば、 CN−1 は cN−1 でなく、c−1 の近似とみなすべきである。 • f = f0 f1 .. . fN−1 ∈ CN に対して、Cn= 1 N N∑−1 j=0 ω−njfj で定義される離散 Fourier 係数を並 べた C = C0 C1 .. . CN−1 ∈ CN を、f の離散 Fourier 変換と呼ぶ。 • 写像 CN ∋ f 7→ C ∈ CN も離散 Fourier 変換と呼ぶ。これは W = 1 N ( ω−(n−1)(j−1)) を表現行列とする線形写像である。 • W−1 =(ω(j−1)(n−1)). ゆえに Cn= 1 N N∑−1 j=0 ω−njfj (n = 0, 1,· · · , N − 1) ⇔ fj = N∑−1 n=0 ωjnCn (j = 0, 1,· · · , N − 1). • U :=√N W はユニタリ行列である: U∗U = U U∗ = I. (余談: 普通の Fourier 変換も、適当な設定で、ユニタリ変換となる。そういうところも 良く対応している。) • N が “たくさん素因数分解” 出来るとき、高い効率で離散 Fourier 変換を計算できる高
速 Fourier 変換 (fast Fourier transform, FFT) と呼ばれるアルゴリズムがある。
4
離散時間
Fourier
変換
(以前授業で説明した時とは少し記号を変える。) 数列{fn}n∈Z ∈ CZ は、f : Z → C という関数とみなせる。 Ff(ω) = bf (ω) := ∞ ∑ n=−∞ f (n)e−inω (ω∈ R) で定義される関数 bf : R → C を、f の離散時間 Fourier 変換と呼ぶ。 b f は周期 2π の関数である。反転公式は f (n) = 1 2π ∫ π −π b f (ω)einwdω (n∈ Z).5
サンプリング定理
連続信号をサンプリングして離散信号を取り出すことにより、元の信号 (関数) の情報がどれ くらい失われるのか、どのくらい保存されているのか、これは大事な問題である。離散 Fourier 変換でも考えたが、周期関数でない f : R → C に関する有名な「シャノンのサンプリング定 理」を紹介した。定理 5.1 (サンプリング定理, Nyquist, Shannon, 染谷) 関数 x :R → C の Fourier 変換
X(ω) = ∫ ∞ −∞ x(t)e−iωtdt が ∃W > 0 (∀ω ∈ R : |ω| ≥ W ) X(ω) = 0 を満たすとき、このような W を任意に一つ取って T := π W とおくと、次式が成り立つ。 (∀t ∈ R) x(t) = ∞ ∑ n=−∞ x(nT )sin π(n− t/T ) π(n− t/T ) . つまり、W 2π 以上の周波数成分を含まない信号は、その 2 倍のサンプリング周波数 fs:= 1 T = W π でサンプリングした離散信号から復元できる。 言い換えると、f 以上の周波数成分を含まない信号は、2f 以上のサンプリング周波数でサ ンプリングしたデータから復元できる。 離散 Fourier 変換に関する、宿題の問 4B を想起するところがある。どちらも 復元したい信号の周波数の 2 倍より大きなサンプリング周波数でサンプリングすれば、完全 に復元できる
6
Fourier
変換ファミリー
(
この授業だけの言葉
)
Fourier 変換、Fourier 級数 (Fourier 係数)、離散時間 Fourier 変換、離散 Fourier 変換の一 覧表を作ってみる。
対象 操作の名前 変換の定義式 反転公式 R 上の関数 Fourier変換 f (ξ) =b √1 2π ∫ ∞ −∞ f (x)e−ixξdx (ξ∈ R) f(x) = √1 2π ∫ ∞ −∞ b f (ξ)eixξdξ R 上の周期関数 Fourier係数 cn= 1 2π ∫ T 0 f (x)e−inxdx (n∈ Z) f (x) = ∞ ∑ n=−∞ cneinx Z 上の関数 (離散 信号) 離散時間 Fourier 変換 b f (ω) = ∞ ∑ n=−∞ f (n)e−inω (ω∈ [0, 2π]) f (n) = 1 2π ∫ 2π 0 b f (ω)einωdω Z 上の周期関数 (周期的離散信号) 離散 Fourier 変換 Cn= N∑−1 j=0 fjω−nj (0≤ n ≤ N − 1), fj = 1 N N∑−1 n=0 Cnωnj ω := exp ( 2πi N ) 式が良く似ていることに注目しよう。 (cn を bf (n) と書き変えたり、fj を f (j), Cn を bf (n) と書き変えたり、 1 2π や 1 N を平等に 割り振ったり、少しいじると互いにとても良く似た式になる。) どれもいわゆる「変換」であり、それぞれ (例えば) L2(R) → L2(R), L2(0, 2π) → ℓ2(Z), ℓ2(Z) → L2(0, 2π), CN → CN の同型を与える。
7
畳み込み
• 色々な関数 (連続信号, 離散信号) に対して、畳み込み (合成積, convolution) f ∗ g が定 義できる。一つの場合を除き、広義積分、無限和であるから、収束するかしないかが問 題になるが、それはとりあえず問題にしないでおく。 (i) f, g :R → C に対して、f ∗ g : R → C を (5) f∗ g(x) := ∫ ∞ −∞ f (x− y)g(y) dy (x ∈ R) により定める。 (ii) 周期 2π の周期関数 f, g : R → C に対して、f ∗ g : R → C を (6) f ∗ g(x) := 1 2π ∫ π −π f (x− y)g(y) dy (x ∈ R) により定める。これは周期 2π であることが分かる。 (iii) f, g : Z → C に対して、f ∗ g : Z → C を (7) f∗ g(n) := ∞ ∑ k=−∞ f (n− k)g(k) (n ∈ Z) により定める。(iv) 周期 N の f, g :Z → C に対して、f ∗ g : Z → C を (8) f∗ g(n) := N∑−1 k=0 f (n− k)g(k) (n ∈ Z) により定める。これは周期 N であることが分かる。 • 「積」として「良い」性質を持っている。 f∗ g = g ∗ f, (交換法則) (9) (f ∗ g) ∗ h = f ∗ (g ∗ h), (結合法則) (10) (f1+ f2)∗ g = f1∗ g + f2∗ g, (分配法則あるいは線形性の一部) (11) (cf )∗ g = c(f ∗ g) (線形性の残り) (12) f∗ g = 0 ⇒ f = 0 or g = 0. (零因子の非存在) (13) (零因子の非存在以外の “証明 (ただし収束の議論は除く)” は比較的簡単である。これく らいは出来てほしい。) • 畳み込みの Fourier 変換は、Fourier 変換の積である。 (i) f :R → C の Fourier 変換を Ff(ξ) := √1 2π ∫ ∞ −∞ f (x)e−ixξdx で定めるとき F[f ∗ g](ξ) =√2πFf(ξ)Fg(ξ). (ii) 周期 2π の f : R → C の Fourier 係数を Ff(n) := 1 2π ∫ π −π f (x)e−inxdx で定める とき F[f ∗ g](n) = Ff(n)Fg(n). (iii) 数列 f : Z → C の離散時間 Fourier 変換を Ff(ξ) := ∞ ∑ n=−∞ f (n)e−inξ で定めるとき F[f ∗ g](ξ) = Ff(ξ)Fg(ξ). (iv) 周期 N の数列 f : Z → C の離散 Fourier 変換を Ff(n) := 1 N N∑−1 j=0 f (j)ω−nj で定め るとき F[f ∗ g](n) = NFf(n)Fg(n).
(i), (ii), (iii) は授業でやった。すべて講義ノートには書いてある。これくらいは自力で 出来てほしい。
• 畳み込みには、単位元らしきもの “デルタ” δ, つまり任意の f に対して f ∗ δ = f
が成り立つ δ がある。普通の実変数の関数 (連続信号) の場合は、ディラックのデルタ 関数と呼ばれる超関数であり、きちんと定義するのは難しいが、離散信号の場合は単位 インパルスと呼ばれる数列 δ ={δn}n∈Z :={δn0}n∈Z ={· · · , 0, 0, 1, 0, 0, · · · } (δ0 = 1, n̸= 0 のとき δn = 0). である。Fourier 変換と関係して、以下のような著しい性質を持つ。 Fδ = 定数 × 1, F1 = 定数 × δ. (これは連続信号に対しては「難しいのでお話」だけれど、離散信号に対しては「簡単な ので出来なくてはいけないこと」で、デジタル・フィルターのところで扱うことになる。)
