2023年度秋学期　画像情報処理　第5回　離散フーリエ変換，フーリエ変換の実例 (2023. 10. 20)

2023年度秋学期　画像情報処理
浅野　晃
関西大学総合情報学部
離散フーリエ変換，フーリエ変換の実例
第5回

View Slide

26
2
離散フーリエ変換🤔🤔

View Slide

26
2023年度秋学期　画像情報処理／　関西大学総合情報学部　浅野　晃
サンプリングされた関数のフーリエ変換
3
サンプリング fT (x) = f(x)combT (x)
輝度f(x)
位置x
fT
(x)
x
x
...
...
T
δ(x)
...
δ(x–T)
δ(x–nT)
× ＝
FT[fT (x)](ν) = FT[f(x)combT (x)](ν)
=
∞
−∞
f(x)combT (x) exp(−i2πνx)dx

View Slide

26
4
x
x
f(x)
fT
(x)
サンプリング
フーリエ変換
ν
T
フーリエ変換
ν
1 / T
... ...
νc
–νc
FT[f(x)](ν)
FT[fT
(x)](ν)

View Slide

26
4
x
x
f(x)
fT
(x)
サンプリング
フーリエ変換
ν
T
フーリエ変換
ν
1 / T
... ...
νc
–νc
FT[f(x)](ν)
FT[fT
(x)](ν)
こちらは離散的だが

View Slide

26
4
x
x
f(x)
fT
(x)
サンプリング
フーリエ変換
ν
T
フーリエ変換
ν
1 / T
... ...
νc
–νc
FT[f(x)](ν)
FT[fT
(x)](ν)
こちらは離散的だがこちらは離散的でない→コンピュータで扱えない

View Slide

26
周波数空間でもサンプリング
5
周波数空間で，１周期あたり
N 点のサンプリングをする
x
f
T
(x)
間隔T [mm]
ν [1/mm]
FT[f
T
(x)](ν)
間隔1 / T [1/mm]
フーリエ変換
［実空間］［周波数空間］
FT[fT(x)](n)
間隔 1 / NT [1/mm]
ν [1/mm]

View Slide

26
実空間ではどうなる？
6
実空間でサンプリング→周波数空間で周期的に現れる
周波数空間でサンプリング→実空間で周期的に現れる
x
f
T
(x)とみると
T [mm]
ν [1/mm]
FT[f
T
(x)](ν) と見ると
1 / T [1/mm]
フーリエ変換
u(n)とみると
1[刻み] = 1[T(mm)]
n
k[刻み]
U(k) とみると
1[刻み]
x[mm]
n[刻み]
N[刻み] = N[T(mm)]
　　　 = NT[(mm)]周期の
周期関数とみなしている
離散フーリエ変換
FT[fT(x)](n) とみると
1 / NT [1/mm]
ν [1/mm]

View Slide

26
「周波数空間でサンプリング」とは
7
周波数空間でサンプリング→実空間で周期的に現れる　🤔🤔
周波数空間でサンプリング，つまり「周波数がとびとび」
それはつまり
波長 L 波長 L/3
f(x) = +
波長 L/2
+ + … + + …
波長 L/n
フーリエ級数
ということは，周期関数を三角関数の足し合わせで表している

View Slide

26
8
離散フーリエ変換は
ここの計算になっている
x
f
T
(x)とみると
T [mm]
ν [1/mm]
FT[f
T
1 / T [1/mm]
フーリエ変換
u(n)とみると
1[刻み] = 1[T(mm)]
n
k[刻み]
U(k) とみると
1[刻み]
x[mm]
n[刻み]
1 / NT [1/mm]
ν [1/mm]

View Slide

26
8
元のフーリエ変換とはだいぶ違う
x
f
T
(x)とみると
T [mm]
ν [1/mm]
FT[f
T
1 / T [1/mm]
フーリエ変換
u(n)とみると
1[刻み] = 1[T(mm)]
n
k[刻み]
U(k) とみると
1[刻み]
x[mm]
n[刻み]
1 / NT [1/mm]
ν [1/mm]

View Slide

26
8
これが元のフーリエ変換
x
f
T
(x)とみると
T [mm]
ν [1/mm]
FT[f
T
1 / T [1/mm]
フーリエ変換
u(n)とみると
1[刻み] = 1[T(mm)]
n
k[刻み]
U(k) とみると
1[刻み]
x[mm]
n[刻み]
1 / NT [1/mm]
ν [1/mm]

View Slide

26
8
こっちが
x
f
T
(x)とみると
T [mm]
ν [1/mm]
FT[f
T
1 / T [1/mm]
フーリエ変換
u(n)とみると
1[刻み] = 1[T(mm)]
n
k[刻み]
U(k) とみると
1[刻み]
x[mm]
n[刻み]
1 / NT [1/mm]
ν [1/mm]

View Slide

26
数列の計算にする
9
元の関数は忘れて，サンプリングされたものを数列とみなす
デルタ関数の並びの積分だったのが
→数列の場合は，そこの値を合計するだけ
U(k) =
N−1
n=0
u(n) exp −i2π
k
N
n (k = 0, 1, . . . , N − 1)
離散フーリエ変換(DFT)
x[s]
デルタ関数の並びではなく，単に間隔でとびとびに取り出された関数の値を
数列とする
T
u(n)

View Slide

26
10
の離散フーリエ変換は
実際には
…
…
…
…
という
周期関数と
みなしている
x
f
T
(x)とみると
T [mm]
ν [1/mm]
FT[f
T
1 / T [1/mm]
フーリエ変換
u(n)とみると
1[刻み] = 1[T(mm)]
n
k[刻み]
U(k) とみると
1[刻み]
x[mm]
n[刻み]
　　　 = NT[mm]周期の
1 / NT [1/mm]
ν [1/mm]

View Slide

26
11
フーリエ変換の実例💡💡
(MATLABを使って示します）

View Slide

26
12
テキスト付録1：
周波数空間でのサンプリングと，実空間で
の周期関数の関係🤔🤔

View Slide

26
「周波数空間でサンプリング」とは
13
周波数空間でサンプリング→実空間で周期的に現れる　🤔🤔
周波数空間でサンプリング，つまり「周波数がとびとび」
それはつまり
波長 L 波長 L/3
f(x) = +
波長 L/2
+ + … + + …
波長 L/n
フーリエ級数
ということは，周期関数を三角関数の足し合わせで表している

View Slide

26
「実空間の周期関数」のほうから考えてみる
14
x
f
T
(x)
間隔T
x
1
幅NT
×
x
=
実空間でサンプリングされた関数 fT
(x)
幅だけ切り出す矩形関数
NT rect(
x
NT
)
rect(x) =
0 (|x| > 1
2
)
1 (|x| < 1
2
)
fT (x) × rect(
x
NT
)
切り出した

View Slide

26
サンプリングして，さらに周期関数にする
15
fT (x) × rect(
x
NT
)
　　
切り出された
x
＊
x
間隔NT
x
=
…
…
…
…
コンヴォリューション
間隔のくし形関数
NT combNT
(x)
周期の周期関数にした
NT
fT (x) × rect(
x
NT
) ∗ combNT (x)

View Slide

26
そのフーリエ変換は
16
周期の周期関数になった
NT
fT (x) × rect(
x
NT
) ∗ combNT (x)
x
…
…
そのフーリエ変換は
FT[f(x)combT (x) × rect(
x
NT
) ∗ combNT (x)]
= FT[f(x)combT (x)] ∗ FT[rect(
x
NT
)] × FT[combNT (x)]
フーリエ変換すると
　× → ＊
　＊ → ×
かけ算はコンヴォリューションに
コンヴォリューションはかけ算に

View Slide

26
矩形関数のフーリエ変換は
17
幅 a の矩形関数の
フーリエ変換は
rect(
x
a
)
sinc関数といい，で表す
sinc(aν)
x
1
幅NT
FT[rect(
x
a
)] =
∞
−∞
rect(
x
a
) exp(−i2πνx)dx
=
a
2
− a
2
exp(−i2πνx)dx
=
1
−i2πν
[exp(−i2πνx)]
a
2
− a
2
=
1
i2πν
(exp(iπaν) − exp(−iπaν))
=
sin(aπν)
πν
0
1
a

View Slide

26
サンプリング／周期化してフーリエ変換すると
18
NT
fT (x) × rect(
x
NT
) ∗ combNT (x)
x
…
…
これのフーリエ変換は FT[fT (x)] × comb 1
NT
(xν) ∗ sinc(
ν
1/(NT)
)
実空間でサンプリングされたのフーリエ変換を
間隔でサンプリング
fT
(x)
NT
ν
FT[f
T
(x)](ν)
間隔1 / T
間隔 1 / NT
ν

View Slide

26
サンプリング／周期化してフーリエ変換すると
18
NT
fT (x) × rect(
x
NT
) ∗ combNT (x)
x
…
…
これのフーリエ変換は FT[fT (x)] × comb 1
NT
(xν) ∗ sinc(
ν
1/(NT)
)
fT
(x)
NT
ν
FT[f
T
(x)](ν)
間隔1 / T
間隔 1 / NT
ν
こっちは？

View Slide

26
sinc関数はどうなるのか？
19
FT[fT (x)] × comb 1
NT
(xν) ∗ sinc(
ν
1/(NT)
)
　　
fT
(x)
NT
ν
FT[f
T
(x)](ν)
間隔1 / T
間隔 1 / NT
ν
デルタ関数の間隔の並びと
sinc関数のコンヴォリューション
1/(NT)
sinc関数が
間隔で並ぶ
sinc(
ν
1/(NT)
)
1/(NT)

View Slide

26
sinc関数はどうなるのか？
19
FT[fT (x)] × comb 1
NT
(xν) ∗ sinc(
ν
1/(NT)
)
　　
fT
(x)
NT
ν
FT[f
T
(x)](ν)
間隔1 / T
間隔 1 / NT
ν
デルタ関数の間隔の並びと
sinc関数のコンヴォリューション
1/(NT)
sinc関数が
間隔で並ぶ
sinc(
ν
1/(NT)
)
1/(NT)
は間隔ごとにゼロになるから，
間隔で並んだsinc関数の影響はない
sinc(
ν
1/(NT)
) 1/(NT)
1/(NT)
0
1
NT

View Slide

26
20
テキスト付録2：
離散フーリエ変換すると
データサイズが2倍に増えているのか？🤔🤔

View Slide

26
離散フーリエ変換の結果は複素数
21
N個の実数値は，N個の複素数値に変換される
複素数はの形で，2つの実数の組になっている
a + bi
離散フーリエ変換によって，
データの大きさが2倍になっているのか？🤔🤔
そんなことはないはずです。

View Slide

26
離散フーリエ変換と対称性
22
数列を離散フーリエ変換したものが　数列であるとき
u(n) U(k)
U∗(N − k) = U(k) という対称性がある
*は複素共役
のとき,
U = a + bi U* = a − bi
なぜならば，👉👉

View Slide

26
23
数列を離散フーリエ変換したものが　数列であるとき
u(n) U(k)
U∗(N − k) = U(k)
が実数ならば，なので
u(n) u*(n) = u(n)
U∗(N − k) =
N−1
n=0
u∗(n) exp(i2π
N − k
N
n)
=
N−1
n=0
u(n) exp(i2πn) exp(i2π
−k
N
n)
なぜならば，👉👉

View Slide

26
24
U∗(N − k) =
N−1
n=0
u∗(n) exp(i2π
N − k
N
n)
=
N−1
n=0
u(n) exp(i2πn) exp(i2π
−k
N
n)
が整数のとき指数関数と三角関数の関係から
，よって
n
exp(i2πn) = cos(2πn) + i sin(2πn) = 1 + 0 = 1
U∗(N − k) =
N−1
n=0
u(n) exp(i2π
−k
N
n) = U(k)

View Slide

26
やっぱりデータサイズは2倍にはなってない
25
が整数のとき指数関数と三角関数の関係から
，よって
n
exp(i2πn) = cos(2πn) + i sin(2πn) = 1 + 0 = 1
こっちが
ν [1/s]
ν [1/s]
が実数ならば，なので
離散フーリエ変換で表されている
最大の周波数は
u(n) U*(k) = U(N − k)
N/2
U(0) U(
N
2
)
は対称「指数関数2つの組でひとつの波」だから，
当然といえば当然ですね💬💬

View Slide

26
第２部へ
26
第２部は画像データ圧縮
画像の細かいところを，見た目にはわからないようにごまかして，データ量
を減らす
「細かいところ」はどのように表現されるか？
　　→周波数で表現される

View Slide

26
第２部へ
26
を減らす
そういうわけで，もう少しフーリエ変換とおつきあいください。

View Slide

26
第２部へ
26
を減らす
そういうわけで，もう少しフーリエ変換とおつきあいください。
もっと一般的な原理から説明します。まずは数学の「行列」から。

View Slide

2023年度秋学期　画像情報処理　第5回　離散フーリエ変換，フーリエ変換の実例 (2023. 10. 20)

2023年度秋学期　画像情報処理　第5回　離散フーリエ変換，フーリエ変換の実例 (2023. 10. 20)

Akira Asano

More Decks by Akira Asano

Other Decks in Education

Featured

Transcript

2023年度秋学期 画像情報処理 第5回 離散フーリエ変換，フーリエ変換の実例 (2023. 10. 20)

2023年度秋学期 画像情報処理 第5回 離散フーリエ変換，フーリエ変換の実例 (2023. 10. 20)

Akira Asano

More Decks by Akira Asano

Other Decks in Education

Featured

Transcript

2023年度秋学期　画像情報処理　第5回　離散フーリエ変換，フーリエ変換の実例 (2023. 10. 20)

2023年度秋学期　画像情報処理　第5回　離散フーリエ変換，フーリエ変換の実例 (2023. 10. 20)