フーリエ変換
( 2017 年 12 月 4 日)
浅井紀久夫
1
本日のポイント
• 空間周波数
• 周波数フィルタ
2
教科書
フーリエ変換
周波数フィルタリング
2 次元正弦波信号
• 2次元正弦波信号は、連続変数(x,y)を用いる と、次式で与えられる
Aを大きさ(振幅)、Ω1=2πF1、Ω2=2πF2をそれぞ れ水平角周波数、垂直角周波数という。
F1、F2は水平周波数、垂直周波数である。
• との違い
– 時間の関数ではない
– 場所(長さ)の関数であること、周波数が2種類存
(
x y)
A y
x
ga( , ) = cos Ω1 + Ω2
( )
tA t
ga( ) = cos Ω
3
2 次元正弦波の周波数
• 単位長さあたりの周期の個数(サイクル数)と して定義される
– 単位時間(1秒)ではない
• 変数x,yによって表現される2次元信号の周 波数を、空間周波数という
0 ,
2 2
1 = F =
F F1 = F0, 2 =1 F1 = F2, 2 =1 4
スペクトル表現
• 周波数を変数とする周波数領域表現
– 信号を、正弦波に分解して周波数成分に着目
• オイラーの公式
から
( )
θ( )
θθ cos j sin
e j = +
( ) ( )
cos 2
θ
θ = e jθ + e− j
( ) ( )
j e e j j sin 2
θ
θ = θ − −
( )
( x y) j( x y)
j a
A e A e
y x
A y
x g
2 1
2 1
2 2
cos )
,
( 1 2
Ω + Ω
− Ω
+
Ω +
=
Ω + Ω
=
重みA/2を持つ2つの複素正弦波の合成として与えられる
5
スペクトル表現
0 ,
2 2
1 = F =
F F1 = F0, 2 =1 F1 = F2, 2 = 1
スペクトルと信号の関係 F1
F2
(1/2) (1/2)
-2 -1 1 2 1
F F2
(1/2) (1/2)
-1 1
F1 F1
F2
(1/2)
(1/2) -2 -1
1 2 1
-1
F1
F2
6
位相
• π/2だけ位相が異なる場合
オイラーの公式から
( x y)
y x
A y
x ga
2 1
2 1
sin
cos 2 )
, (
Ω + Ω
=
Ω + Ω −
= π
( ) ( )
( x y) j j( x y)
j j
y x
j y
x j a
e A e
e A e
j e e A
j y A
x g
2 1
2 1
2 1
2 1
2 2
2 2
2 ) 2
, (
Ω + Ω
− Ω
+
− Ω
Ω + Ω
− Ω
+ Ω
+
=
+ −
=
π π
複素正弦波に対する重みが複素数になる 7
振幅と位相
• 極座標表現に直す
– |C|を振幅スペクトル – θを位相スペクトル
θ
e j
C C =
振幅スペクトル 位相スペクトル 2, 1
2
1 = F =
F
F1 F1
F2
(1/2)
(1/2) -2 -1
1 2 1
-1
F1 F1
F2
(π/2)
(-π/2) -2 -1
1 2 1
-1
離散正弦波信号
• 変数の離散化
ただし、
– 変数f1,f2をそれぞれ正規化水平周波数、正規化 垂直周波数
– サンプリング周波数を基準に、値を相対化
( )
( 11 11 2 22) 2
2 1
2 1
cos cos
, )
, ( )
, (
2 1
2 1
n n
A
T n T
n A
T n y
T n x
y x g n
n g
s s
s s
a a
ω ω +
=
Ω + Ω
=
=
=
=
1 1
1 1
1
1 2 2
s
s F
T F
f π
π
ω = = Ω =
2 2
2 2
2
2 2 2
s
s F
T F
f π
π
ω = = Ω =
9
離散正弦波信号のスペクトル
• サンプリング周波数が決まると、連続信号から離散信号を 一意に決定できる
• 離散信号から元の連続信号を一意に特定することは、一般 に困難
– 同じ離散信号を与える連続信号が無数に存在する – >スペクトルの周期性
F1
F2
0
s2
F
s2
− F
s1 1 F
Fs
− ω1
ω2
0
π 2
π
− 2
π π 2
−2
非正規化 正規化
10
信号の合成
• 3つの信号を、各時刻で足し合わせる
– 周波数の異なる正弦波を合成すると、非正弦波 – 非正弦波を、複数の正弦波に分解できる場合が
ある
) ( )
( )
( )
(t g1 t g2 t g3 t
g = + +
11
フーリエ解析
• 信号を、正弦波に分解したり(g(t)から
g1(t),g2(t),g3(t)を求める)、合成したり(逆に g(t)を求める)する方法
• 非正弦波の処理を、複数個の正弦波の処理 に帰着できる
信号
周期的
非周期的
離散 連続 離散
連続空間フーリエ級数 離散空間フーリエ級数
離散空間フーリエ変換 連続空間フーリエ変換 連続
CSFS
DSFS
DSFT CSFT
12
離散信号のフーリエ変換
• 非周期的な離散信号g(n1,n2)に対するフーリエ 変換
離散空間フーリエ変換(DSFT)
• 表現の簡略化
( ) ∑ ∑
∞( )
−∞
=
∞
−∞
=
−
= −
1 2
2 2 1
1 2
1
2 1,
,
n n
n j n
j j
j e g n n e e
e
G ω ω ω ω
( )
ω G( )
e jωG =
(
ω1,ω2)
G(
e jω1 ,e jω2)
G =
13
振幅スペクトルと位相スペクトル
• g(n1,n2)が実数の場合でも、一般にG(n
1,n2)
は複素数
GR とGI は、Gの実数部と虚数部
• 極座標表示 ただし、
(
ω1,ω2)
GR(
ω1,ω2)
jGI(
ω1,ω2)
G = +
(
ω1,ω2) (
A ω1,ω2)
e jθ(ω1,ω2)G =
(
ω1,ω2) {
GR(
ω1,ω2) }
2{
GI(
ω1,ω2) }
2A = +
( )
= − ( ( ) )
2 1
2 1 1
2
1 ,
tan ,
,ω ωω ωω
ω θ
R I
G G
振幅スペクトル 位相スペクトル
14
振幅スペクトルと位相スペクトル
• DSFT
• 振幅スペクトル
• 位相スペクトル
(
ω1,ω2) (
A ω1,ω2)
e jθ(ω1,ω2)G =
(
ω1,ω2)
A
) , (ω1 ω2 θ
e j
振幅スペクトル 位相スペクトル
15
振幅限定画像と位相限定画像
• 逆DSFT
• 振幅限定画像
• 位相限定画像
( )
[
1 2]
1 2
1, ) ,
(n n F A ω ω
gA = −
[
( , )]
1 2
1
2
) 1
,
( θ ω ω
θ n n F e j
g = −
位相情報が、画像の重要
な情報の多くを持っている 16
原画像
振幅スペクトル 位相スペクトル
振幅限定画像 位相限定画像
離散空間フーリエ変換の性質
• スペクトルの周期性(周期2π)
信号とそのDSFT のとき
• スペクトルの対称性
(
1 2)
2
1, ) ,
(n n G ω ω
g ↔
(
ω1,ω2) (
= G ω1 + 2π ,ω2) (
= G ω1,ω2 + 2π)
G
( )
(
1 2)
2 1
2 1
2 1
,
) ,
(
) ,
( ,
1 2
2 2 1
1
1 2
2 2 1
1
ω ω
ω ω
ω ω
ω ω
G
e e
n n g
e e
n n g G
n n
n j n
j
n n
n j n j
=
=
=
−
−
∑ ∑
∑ ∑
∞
−∞
=
∞
−∞
=
−
−
∞
−∞
=
∞
−∞
=
G は、Gの複素共役を表す
17
離散空間フーリエ変換の性質
から
振幅は偶対称性、位相は奇対称性
• 信号のシフト
整数k
1,k2に対して
ここで、
ゆえに、信号のシフトは振幅スペクトルに影響を与 えない(位相のみに影響する)
(
−ω1,−ω2)
= A(−ω1,−ω2)e− jθ(−ω1,−ω2)G
) ,
( )
,
(ω1 ω2 = A −ω1 −ω2
A θ (ω1,ω2) = −θ (−ω1,−ω2)
(
1 2)
( )2 2
1 1
2 1 1
, 1
) ,
(n k n k G e j k k
g − − ↔ ω ω − ω +ω
(
ω1,ω2)
e (ω1 1 ω1 2) G(
ω1,ω2)
G − j k + k =
18
スペクトル計算例(振幅)
19
有限長信号の DSFT
• N1×N2の領域の2次元信号g(n1,n2)、 n1=0,1,…,N1-1, n2=0,1,…N2-1を考える
( ) ( )
( )
∑ ∑
∑ ∑
−
=
−
=
−
−
∞
−∞
=
∞
−∞
=
−
−
=
=
1
0
1
0
2 1
2 1
2 1
1
1
2
2
2 2 1
1
1 2
2 2 1
1
,
, ,
N
n
N
n
n j n
j
n n
n j n
j
e e
n n g
e e
n n g G
ω ω
ω
ω ω
ω
信号の定義領域(サポート領域)が有限な信号を 有限長(有限領域)信号という
20
周波数の離散化
• N1×N2点の2次元有限長信号g(n1,n2)、 n1=0,1,…,N1-1, n2=0,1,…N2-1
ただし、
( ) ( )
( )
∑ ∑
∑ ∑
−
=
−
=
−
=
−
=
−
−
=
=
1
0
1
0
2 1
1
0
1
0
/ 2
/ 2
2 1
2 1
1
1
2
2
2 2 2 1
1 1 1
1
2
2
2 2 2 1
1 1
,
, ,
N
n
N
n
n k N n
k N N
n
N
n
N n k j N
n k j
W W
n n g
e e
n n g k
k
G π π
2 2
1 1
/ 2 /
2 N , N j N
j
N e W e
W = − π = − π
2次元DFTの値は、スペクトル周期(2π)をN
1、N2
等分するようなDSFTの周波数サンプル値に相当する。21
離散フーリエ変換の分離性
• 2次元離散フーリエ変換は、分離性から
1次元離散フーリエ変換の繰り返しによって 実行可能
( ) ( )
( )
∑
∑ ∑
∑ ∑
−
=
−
=
−
=
−
=
−
=
=
=
=
1
0
2 1
1
0
1
0
2 1
1
0
1
0
2 1
2 1
2
2
2 2 2 2
2
2 2 2 1
1
1 1 1 1
1
2
2
2 2 2 1
1 1
) ,
(
,
, ,
N
n
n k N N
n
n k N N
n
n k N N
n
N
n
n k N n
k N
W n
k G
W W
n n g
W W
n n g k
k G
( )
∑
− ( )= =1 0
2 1 2
1
1
1
1 1
, 1
,
N
n
n k
WN
n n g n
k G
22
FFT (高速フーリエ変換)
• FFTは、DFTを近似なしに少ない計算量で 実行する高速アルゴリズム
• N点の信号g(n)、n=0,1,…,N-1に対して、 DFT
• Nを2のべき乗( N =2l)と仮定 から
( ) ∑
−( )
= =1 0 N
n
nk
WN
n g k
G k=0,1,…,N-1
N j
N e
W = − 2π /
23
FFT アルゴリズム
g(n)を偶数番目と奇数番目に分けて、
2回のN/2点DFT計算によって、N点DFTを実行できる
( ) ( ) ( ) ( )
( ) ( ) ( )
∑ ∑
∑ ∑
−
=
−
=
−
−
−
−
=
−
=
+
−
−
−
−
−
−
−
−
−
−
+ +
=
+ +
=
− +
+ +
+
− +
+ +
=
1 2 /
0
1 2 /
0
)) 2 / /( 2 ( )
/ 2 ( ))
2 / /( 2 ( 1
2 /
0
1 2 /
0
) 1 2 ( ) / 2 ( )
2 ( ) / 2 (
) 1 ( ) / 2 ( 3
) / 2 ( )
/ 2 (
) 2 ( ) / 2 ( 2
) / 2 ( 0
) 1 2
( )
2 (
) 1 2
( )
2 (
1 3
1
2 2
0
N
l
N
l
kl N
j k
N j
kl N
j N
l
N
l
l k N j
l k N j
N k N j
k N j
k N j
N k N j
k N j
j
e l
g e
e l g
e l
g e
l g
e N
g e
g e
g
e N
g e
g e
g k
G
π π
π
π π
π π
π
π π
)] (
[ )
(k DFT g n
G = N と略記して
24
FFT アルゴリズム(つづき)
と、表現される
から、
と計算できる。
FFTでは、この分解を2点DFTの細かさ(l段 の分解)まで繰り返す
)] 1 2
( [ )]
2 ( [ )
(k = DFT /2 g l + e− (2 / ) DFT /2 g l +
G N j π N k N
)] 2 ( [ )
( /2
2
/ k DFT g l
GNeven = N GNodd/2(k) = DFTN/2[g(2l +1)] )
( )
( )
(k G /2 k e (2 / ) G /2 k G = Neven + − j π N k Nodd
25
FFT アルゴリズム(つづき)
) ( )
( )
( /4 (2 /( /2)) /4
2
/ k G k e G k
GNeven = Neven + − j π N k Nodd
FFTアルゴリズムの概念図
N/2点FFT
N/4点FFT
同様にして、
偶数 g(2l)
k
WN /2 N点
g(n)
)
2 (
/ k
GNeven
N/2点FFT
N/4点FFT
N k j k
N k
N W e
W /2 = 2/2 − 4π / )
2(
/ k
GNodd
奇数 g(2l+1)
N j
k
N e
W /2 = − 2π / ) (k G
26
演算量
• 周期 N の離散フーリエ変換(DFT)では、 複素数の乗算を N2 回行う必要がある
• 高速フーリエ変換では、その乗算回数を N・log2N /2 回に減らすことができる
27
DFT の行列表現
• DFT
この変換はN×Nの正方行列を用いた変換とし て記述できる
であることに注意して、N=4を例に すれば、
( ) ∑
−( )
= =1 0 N
n
nk
WN
n g k
G
N j
N e
W = − 2π /
−
−
−
−
−
= −
=
) 3 (
) 2 (
) 1 (
) 0 (
1 1
1 1
1 1
1 1
1 1
1 1
) 3 (
) 2 (
) 1 (
) 0 (
) 3 (
) 2 (
) 1 (
) 0 (
9 4 6
4 3
4 0
4
6 4 4
4 2
4 0
4
3 4 2
4 1
4 0
4
0 4 0
4 0
4 0
4
g g g g
j j
j j
g g g g
W W
W W
W W
W W
W W
W W
W W
W W
G G G G
28
DFT の行列表現
• N点の信号g(n)および変換値G(k)をそれぞれ N次元ベクトルとして、
と表現する。tは転置を意味する。
• N×Nの行列をAとすると
のように、N点信号g(n)からN点の変換値G(k) を、行列とベクトルを用いて表記できる
[
G(0),G(1), ,G(N −1)]
t=
G
Ag G =
29
DFT の行列表現
• 行列Aのk行n列の要素ak,n
としている。基底という。
のとき、直交行列という。
tは転置を、A-1はAの逆行列を表す。
は、直交基底である。
[ ]
A k,n = ak,n = WNnk = e− j2πnk /N−1
= A At
[ ]
A k,n = ak,n = WNnk = e− j2πnk /N30
2 次元 DFT の基底
• M=N=8における2次元DFTの基底( の実部を濃淡で表したもの)
– 画像に、どの程度の大きさで各周波数成分が含 まれているかを調べることができる
31
2 2 2 1
1 1
n k N n
k
N W
W
k=l=0のとき、直流成分に対応 k=l=4のとき、最も高い周波数成分
離散コサイン変換
• 画像符号化では、離散コサイン変換が用いら れることが多い
– 実数行列
– 高速アルゴリズム
32 空間周波数が高くなる
空間周波数が高くなる
DCTの基底
画像中の 1 ブロック
• 1ブロック
– 8x8画素
33
1ブロック
(8x8画素)
画像
基底を、重み付けて足す
34
1ブロック
(8x8画素)
W00 x + W10 x + W20 x
+ W57 x + W67 x + W77 x
Wij (i =0,1, …, 7; j =0,1, …, 7):DCT係数
課題の予定
• 12月18日 課題の提案
– どんな作品、あるいは機能とするのか、概要を 一枚物レポートとして提出
– 必要事項
名前、学籍番号
タイトル
概要(ポイントは何か、面白いところはどこか、どの 手法を使って、どういう手順で進めるのか)
• 1月22日 課題の提出
35
課題例
• 写真と実物との合成
• 立体写真でもOK
– でも、ディスプレイがない
名前:高専太郎 番号:0000
タイトル:た、立った! 概要
ポイント:1つのカメラで撮影した写真に、 画像処理を施す
面白いところ:フィギュア(本物)と実写(パ ソコンに提示)の融合において、照明効果 を考慮する
手法:デジカメを使って素材を取得し、画 像処理ツールで輝度や色を修正する。実 写と実物が違和感なく見えるようにする。 手順:フィギュアを用意、背景画像を設定、 デジカメで撮影、画像処理ツールで編集、 調整
原理図など
SDガンダム