スライド 1

Ikeuchi Laboratory
The University of Tokyo
Japan
変分法と有限要素法
宮崎大輔
光学勉強会
光学勉強会って？




不定期だが，月に一回開催を目指している
宮崎♂が主催
CVLセミナーと違ってofficialなイベントではない
CVLセミナーと違って





もっとアットホームな雰囲気で
基礎的な内容をやりたい
光学グループが中心メンバーだが，他のグループも多数参
加してほしい
昔，ITS勉強会やロボ勉強会やレベルセット勉強会などが開
催されていた時期があったが，現在生き残っているのはたぶ
ん光学勉強会だけ
光学勉強会を作るのはあなたたちです！！
光学勉強会
今日の話

戸川隼人
変分法と有限要素法
日本評論社1994
光学勉強会
Shape-from-shadingにおけるエネルギー最小化問
題
H
傾き＝
x
H
x
勾配
H
p  Hx 
x
コスト関数
  H
H
q  Hy 
y
x

 p    H y  q  dxdy
2
これを最小化したい
光学勉強会
2
Shape-from-shadingにおけるエネルギー最小化問
題
2
2
  H
x

 p    H y  q  dxdy
これをpについて解くためには中身をpで偏微分して=0とする
解は
離散化すると
H
p  Hx 
x
1
p   H ( x  1, y )  H ( x  1, y ) 
2
qについても解ける
でもHについてはどうやって解く？
変分法
光学勉強会
最短時間で降りる非常用滑り台の問題
光学勉強会
変分問題



1 2
mgy  mv
2
運動エネルギー=位置エネルギー
よって，速度 v  2gy
この曲線y=u(x)にそった微小長さ ds  1  u( x) 2 dx
を通過するのに要する時間
ds
1  u( x) 2
dt 

v

2 gy
P点からQ点に達するまでの全体の所要時間
T [u ( x)]  
a
0
1  u( x) 2
dx
2 gu( x)
このTが最小になるu(x)を求めたい
x
u(x)
ds
き
u'(x)dx
dx
光学勉強会
はじ
汎関数と変関数


汎関数：関数→変数
変関数：汎関数の引数
u( )
汎関数
2.317・・・


1 1
J [u ]   u ( x) 2  u ( x) 2 dx
2 0
2
 du 
J [u ]   1    dx
a
 dx 
2
2



1  u 
u 

J [u ]        dxdy
2 D  x   y  


b
光学勉強会
変分


J [u  v]  J [u ] 

J  lim

 0



変分
例 J [u]   u( x)
1
0
2
dx


J [u  v]   u( x)  v( x) dx   u( x) 2  2u( x)v( x)   2v( x) 2 dx
1
1
2
0
J [u  v]  J [u ]



ε→0
u( x)  v( x) と置く
0
1
1
0
0
 2 u( x)v( x)dx    v( x) 2 dx
任意の u に対して J  0
光学勉強会
解く
部分積分の公式
  fg   fg dx
 f gdx
u(1)u(1)  u(0)u(0)  0
1
J [u ]   u( x) 2 dx
0
u(0)u (0)  0
1
J  2 uudx
u(1)u(1)  0
0
1
 uudx  0
1
1
uu 0  0 uudx
u(0)  0 または u(0)  0
0
かつ
u(1)  0 または u (1)  0
u  0
u  c1 x  c2
任意の u に対して J  0
光学勉強会
u(0)  0
u (1)  0
u (0)  
u(1)  
変分学の基本補題

区間[a,b]においてf(x)が連続で，下記の積分の可
能な任意の関数g(x)について

b
a
f ( x) g ( x)dx  0
であれば
f ( x)  0
である
光学勉強会
a xb
オイラー方程式

このように
汎関数の
停留条件
部分積分
変分学の基本
補題の適用
という変形により，変分問題を微分方程式に帰着さ
せることができる．この微分方程式をオイラー方程
式という．
光学勉強会
ラグランジュ乗数法

懸垂線：糸の各部分の位置エネルギーの総和を最
b
小化
 u( x)ds
最小
a

糸の長さが一定(l)

b
a

ds  l
ラグランジュ乗数法： J [u ]  b u ( x)ds    b ds  l 
 a

a


uとλについて最小化
光学勉強会
計算

汎関数
b
J [u]   F ( x, u, u)dx
a

すなわち

F d  F 
 
0
u dx  u 
F   F    F 
  F 
 
 
u 

u  0
u x  u  u  u 
u  u 
オイラー方程式
境界条件
u (a)  
u (b)  
または
自然境界条件  F 
 F 

 0

 0
 u  x a
 u  x b
光学勉強会
滑り台の問題
2 gT [u ]  
a
0
F
1 
  u 2 1  u2
u
2
3
1  u( x) 2
dx
u ( x)
1

F
 u 2 1  u2
u

1

1  u 2
F ( x, u, u) 
 u 2 1  u2
u



1
2
3

1 2
 u 1  u2
2


1
2
1
2
u

  F 
1 
2

   u 2 1  u
u  u 
2
3
1
2
1
2
1
u  u
2

1
2
1  u 
3
2 2


  F 
2

  u 2 1  u
u  u 
オイラー方程式は
3



  F 

0
x  u 
これを最小化すると
1 2
 u 1  u2
2






1
2
u
3
2
u  0
整理すると 1  u2  2uu  0
x  c1   sin    c2
これはサイクロイド．一般解は u  c 1  cos 
1
境界条件 u (0)  0
u (a)  h を代入してc1とc2を求めればOK
光学勉強会
計算

Fがxを陽に含まない場合

b
J [u]   F (u, u)dx
滑り台の問題
F u
a

1
2
1  u 
1
2
1  u 
1
2 2
オイラー方程式
d 
F 
 F  u    0
dx 
u 
F
u
u
積分

1

2 2
u
より
F
F  u
c
u 
u
光学勉強会

1
2
1

2
2
1  u 
c
計算
b
J [u]   F ( x, u, u, u)dx
a
オイラー方程式
F d F d 2 F

 2
0
u dx u dx u
自然境界条件
 F d F 
0
 

 u dx u  x a
 F 
    0
 u  x a
 F d F 
0
 

 u dx u  x b
 F 
    0
 u  x b
光学勉強会
２次元の場合
2
2

1
 u   u  

J [u ]         dxdy
2 D
 x   y  

  2u  2u 
u
J 
 uds    2  2   udxdy
 n
D x
y 


ds はDの境界Γ上の反時計まわりの線積分


は法線方向の微分
n
 2u  2u
オイラー方程式
 2  0 （ラプラス方程式）
2
x y
u
0
自然境界条件
n
光学勉強会
計算
J [u ]   F ( x, y, u, p, q)dxdy
D
ただし
u
p
x
u
q
y
オイラー方程式
 2 F u  2 F  2u  2 F  2u  2 F  2 F

 2


2
px x pu x p
xy pq qy
u  2 F  2u  2 F  2u  2 F F

 2


0
2
y qu y q
xy qp u
F
F
自然境界条件
dy 
dx  0
p
q
光学勉強会
計算
J [u ]   F ( x, y, p, q, r , s, t )dxdy
D
ただし
u
r 2
x
2
u
p
x
u
q
y
 2u
s
xy
 2u
t 2
y
オイラー方程式
F  F  F  2 F
 2 F  2 F


 2
2
 2
0
u x p y q x y
xy s y t
光学勉強会
変分問題の直接解法

近似解で解く方法（パラメータai，基底φi）
u( x)  a11 ( x)  a22 ( x) 

J[u]に代入→各aiで偏微分して=0→連立方程式
J (a1 , a2 ,
ai

 ann ( x)
, an )
0
レイレイーリッツ(Rayleigh-Ritz)法
定式化
変分問題
光学勉強会
直接解法
ラプラス方程式，ポアソン方程式
2
2

1
 u   u  

J [u ]         dxdy   u  fdxdy
D
2 D

x

y







 2u  2u
オイラー方程式 2  2  f ポアソン方程式（ラプラス方程式）
x y
u  a11 ( x, y)  a22 ( x, y) 
 c11 c12
c
 21 c22


 cn1 cn 2
J (a1 , a2 ,
ai
 ann ( x, y)
c1n   a1   b1 
c2 n   a2  b2 

   
   
cnn   an  bn 
, an )
 i  j i  j
cij   

D
y y
 x x
bi   f ( x, y )i ( x, y )dxdy
光学勉強会
D
0

 dxdy

境界条件


ディリクレ条件：境界におけるuの値を指定
u
ノイマン条件：境界における n を指定
ディリクレ条件
基底φiに境界上での値が0の関数を使う
0以外の境界値の場合，関数φ0を加える
u  0  a11  a22 
光学勉強会
 ann
自然境界条件

物理の問題を変分法で解く場合
変分法における自然境界条件
物理的意味で「自然な」境界条件
（何も拘束を加えない）

物理問題→変分問題で定式化→直接解法で解く
「自然な」境界条件が自動的に満たされる

例：ラプラス方程式


自然境界条件＝法線方向の微分が0
熱伝導の問題でいえば「特に指定しない限り，壁における
熱の出入りはない」
光学勉強会
有限要素法
u  a11  a22 
 ann
基底関数φiとして区分多項式
（特に区分１次式つまり折れ線関数）
基底関数φi(x)
折れ線関数u(x)
三重対角行列になるのでコンピュータで簡単に解ける
光学勉強会
三角形１次要素

２次元→三角形分割→各三角形内部で１次式
基底関数φi(x,y)としてこの関数（形状関数）を使う
光学勉強会
Shape-from-shadingの例
  H
x

 p    H y  q  dxdy をHについて解く
2
2
 F (u, u , u
x
オイラー方程式
自然境界条件
y
)dxdy


Fu  Fux  Fu y  0
x
y
dy
dx
Fux
 Fu y
0
ds
ds
オイラー方程式を整理するとポアソン方程式になる
→緩和法でコンピュータで計算可能
光学勉強会
コンピュータビジョンへの応用

変分法は何の役に立つの？


Shape-from-shadingはもちろん，ステレオ，optical flow，
SNAKES，など様々なエネルギー最小化問題を解くこと
ができる
有限要素法は何の役に立つの？

レベルセットなどのdeformable surfaceの計算
光学勉強会
次回


予定：１１月
発表者



宮崎大輔「テンソル積展開」
？？
？？
光学勉強会
Ikeuchi Laboratory
The University of Tokyo
Japan
© Daisuke Miyazaki 2005
All rights reserved.
http://www.cvl.iis.u-tokyo.ac.jp/
光学勉強会

Download Report