• 検索結果がありません。

06フーリエ変換pdf 映像メディア工学2017 ヒューマンコンピュータインタラクション研究室 06フーリエ変換

N/A
N/A
Protected

Academic year: 2018

シェア "06フーリエ変換pdf 映像メディア工学2017 ヒューマンコンピュータインタラクション研究室 06フーリエ変換"

Copied!
43
0
0

読み込み中.... (全文を見る)

全文

(1)

フーリエ変換

2017124 日)

浅井紀久夫

1

(2)

本日のポイント

空間周波数

周波数フィルタ

2

教科書

フーリエ変換

周波数フィルタリング

(3)

2 次元正弦波信号

• 2次元正弦波信号は、連続変数(x,y)を用いる と、次式で与えられる

Aを大きさ(振幅)、Ω1=2πF1Ω2=2πF2をそれぞ れ水平角周波数、垂直角周波数という。

F1F2は水平周波数、垂直周波数である。

との違い

時間の関数ではない

場所(長さ)の関数であること、周波数が2種類存

(

x y

)

A y

x

ga( , ) = cos 1 + 2

( )

t

A t

ga( ) = cos

3

(4)

2 次元正弦波の周波数

• 単位長さあたりの周期の個数(サイクル数)と して定義される

単位時間(1秒)ではない

変数x,yによって表現される2次元信号の周 波数を、空間周波数という

0 ,

2 2

1 = F =

F F1 = F0, 2 =1 F1 = F2, 2 =1 4

(5)

スペクトル表現

• 周波数を変数とする周波数領域表現

信号を、正弦波に分解して周波数成分に着目

オイラーの公式

から

( )

θ

( )

θ

θ 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

(6)

スペクトル表現

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

(7)

位相

π/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

(8)

振幅と位相

極座標表現に直す

– |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

(9)

離散正弦波信号

変数の離散化

ただし、

変数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

(10)

離散正弦波信号のスペクトル

サンプリング周波数が決まると、連続信号から離散信号を 一意に決定できる

離散信号から元の連続信号を一意に特定することは、一般 に困難

同じ離散信号を与える連続信号が無数に存在する >スペクトルの周期性

F1

F2

0

s2

F

s2

F

s1 1 F

Fs

ω1

ω2

0

π 2

π

2

π π 2

2

非正規化 正規化

10

(11)

信号の合成

• 3つの信号を、各時刻で足し合わせる

周波数の異なる正弦波を合成すると、非正弦波 非正弦波を、複数の正弦波に分解できる場合が

ある

) ( )

( )

( )

(t g1 t g2 t g3 t

g = + +

11

(12)

フーリエ解析

• 信号を、正弦波に分解したり(g(t)から

g1(t),g2(t),g3(t)を求める)、合成したり(逆に g(t)を求める)する方法

• 非正弦波の処理を、複数個の正弦波の処理 に帰着できる

信号

周期的

非周期的

離散 連続 離散

連続空間フーリエ級数 離散空間フーリエ級数

離散空間フーリエ変換 連続空間フーリエ変換 連続

CSFS

DSFS

DSFT CSFT

12

(13)

離散信号のフーリエ変換

非周期的な離散信号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

(14)

振幅スペクトルと位相スペクトル

• 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

) }

2

A = +

( )

= 

( ( ) )



2 1

2 1 1

2

1 ,

tan ,

,ω ωω ωω

ω θ

R I

G G

振幅スペクトル 位相スペクトル

14

(15)

振幅スペクトルと位相スペクトル

• DSFT

振幅スペクトル

位相スペクトル

(

ω1,ω2

) (

A ω1,ω2

)

e jθ(ω1,ω2)

G =

(

ω1,ω2

)

A

) , (ω1 ω2 θ

e j

振幅スペクトル 位相スペクトル

15

(16)

振幅限定画像と位相限定画像

DSFT

振幅限定画像

位相限定画像

( )

[

1 2

]

1 2

1, ) ,

(n n F A ω ω

gA =

[

( , )

]

1 2

1

2

) 1

,

( θ ω ω

θ n n F e j

g =

位相情報が、画像の重要

な情報の多くを持っている 16

原画像

振幅スペクトル 位相スペクトル

振幅限定画像 位相限定画像

(17)

離散空間フーリエ変換の性質

• スペクトルの周期性(周期

信号とその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

(18)

離散空間フーリエ変換の性質

から

振幅は偶対称性、位相は奇対称性

信号のシフト

整数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)

スペクトル計算例(振幅)

19

(20)

有限長信号の 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

(21)

周波数の離散化

• 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の値は、スペクトル周期()をN

1N2

等分するようなDSFTの周波数サンプル値に相当する。21

(22)

離散フーリエ変換の分離性

• 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

(23)

FFT (高速フーリエ変換)

• FFTは、DFTを近似なしに少ない計算量で 実行する高速アルゴリズム

• N点の信号g(n)n=0,1,…,N-1に対して、 DFT

• N2のべき乗( N =2l)と仮定 から

( )

( )

= =1 0 N

n

nk

WN

n g k

G k=0,1,…,N-1

N j

N e

W = 2π /

23

(24)

FFT アルゴリズム

g(n)を偶数番目と奇数番目に分けて、

2回のN/2DFT計算によって、NDFTを実行できる

( ) ( ) ( ) ( )

( ) ( ) ( )

∑ ∑

∑ ∑

=

=

=

=

+

+ +

=

+ +

=

+

+ +

+

+

+ +

=

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

(25)

FFT アルゴリズム(つづき)

と、表現される

から、

と計算できる。

FFTでは、この分解を2DFTの細かさ(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

(26)

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

(27)

演算量

周期 N の離散フーリエ変換(DFT)では、 複素数の乗算を N2 回行う必要がある

• 高速フーリエ変換では、その乗算回数を Nlog2N /2 回に減らすことができる

27

(28)

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

(29)

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

(30)

DFT の行列表現

行列Akn列の要素ak,n

としている。基底という。

のとき、直交行列という。

tは転置を、A-1Aの逆行列を表す。

は、直交基底である。

[ ]

A k,n = ak,n = WNnk = e j2πnk /N

1

= A At

[ ]

A k,n = ak,n = WNnk = e j2πnk /N

30

(31)

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)

離散コサイン変換

• 画像符号化では、離散コサイン変換が用いら れることが多い

実数行列

高速アルゴリズム

32 空間周波数が高くなる

DCTの基底

(33)

画像中の 1 ブロック

• 1ブロック

– 8x8画素

33

1ブロック

8x8画素)

画像

(34)

基底を、重み付けて足す

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係数

(35)

課題の予定

• 1218 課題の提案

どんな作品、あるいは機能とするのか、概要を 一枚物レポートとして提出

必要事項

名前、学籍番号

タイトル

概要(ポイントは何か、面白いところはどこか、どの 手法を使って、どういう手順で進めるのか)

• 122 課題の提出

35

(36)

課題例

写真と実物との合成

立体写真でもOK

でも、ディスプレイがない

名前:高専太郎 番号:0000

タイトル:た、立った! 概要

ポイント:1つのカメラで撮影した写真に、 画像処理を施す

面白いところ:フィギュア(本物)と実写(パ ソコンに提示)の融合において、照明効果 を考慮する

手法:デジカメを使って素材を取得し、画 像処理ツールで輝度や色を修正する。実 写と実物が違和感なく見えるようにする。 手順:フィギュアを用意、背景画像を設定、 デジカメで撮影、画像処理ツールで編集、 調整

原理図など

SDガンダム

(37)
(38)
(39)
(40)
(41)

何が違う?

(42)

ライトフィールドカメラ

(43)

マイクロレンズアレイ

参照

関連したドキュメント

Mapping Satoshi KITAYAMA and Hiroshi YAMAKAWA Waseda University,Dept.of Mech.Eng.,59‑314,3‑4‑1,Ohkubo,Shinjuku‑ku Tokyo,169‑8555 Japan This paper presents a method to determine

Power spectrum of sound showed a feature near the upper dead point of shedding motion when healds collided the heald bar.. Superposing sound pressure signals during several periods

The goods and/or their replicas, the technology and/or software found in this catalog are subject to complementary export regulations by Foreign Exchange and Foreign Trade Law

LLVM から Haskell への変換は、各 LLVM 命令をそれと 同等な処理を行う Haskell のプログラムに変換することに より、実現される。

張力を適正にする アライメントを再調整する 正規のプーリに取り替える 正規のプーリに取り替える

(5) 本プロジェクト実施中に撮影した写真や映像を JPSA、JSC 及び「5.協力」に示す協力団体によ る報道発表や JPSA 又は

 ところが、転換証券を使った伝統的ではない資金調達手法には、転換によって発行され

そこで本解説では,X線CT画像から患者別に骨の有限 要素モデルを作成することが可能な,画像処理と力学解析 の統合ソフトウェアである