狠狠撸

コンピュータビジョンのための
グレブナー基底??1
美間亮太
東京?学?学部計数?学科3年
2019/12/15(3D勉強会)

??紹介
かわいい
Twitter(@mamii0718) Facebook
好きな定理

1.Introduction 3
Gr?bner basisとは

1.Introduction 4
[Cox,Using…]
Gr?bner basisの参考?献
.
[Cox,Ideals…] [グレbo徒] [??,統計]

1.Introduction 5
(例)多変数?線形連??程式

1.Introduction 6
(例)多変数?線形連??程式

1.Introduction 7
例題(Gr?bner basis解答例1/3 ①)

1.Introduction 8
例題(Gr?bner basis解答例1/3 ②)

1.Introduction 9
例題(Gr?bner basis解答例1/3 ③)

1.Introduction 10
例題(Gr?bner basis解答例1/3 ④)

1.Introduction 11
例題(Gr?bner basis解答例2/3 )

1.Introduction 12

1.Introduction 13
→3章へ

2. SLAMにおける
Gr?bner basis
SLAMにおける5点アルゴリズム
5点アルゴリズムの問題設定
エピポーラー拘束
5点アルゴリズムの先?研究
CVでの最?問題

2.SLAMにおける
Gr?bner basis (15)(例)SLAMにおける5点アルゴリズム
Mur-Artal, Raul, Jose Maria Martinez Montiel, and Juan D. Tardos. "ORB-SLAM: a versatile and accurate monocular SLAM system." IEEE transactions on robotics 31.5 (2015): 1147-1163.
特徴点ベースのSLAMでの初期化(パラメータの初期値を求め
る)
→5点アルゴリズム、8点アルゴリズム、DLT…

2.SLAMにおける
Gr?bner basis (16)(例)5点アルゴリズム(問題設定)

2.SLAMにおける
Gr?bner basis (17)補?(内部パラメーターとは)
3次元点の世界座標値
正規画像座標値
3次元点のカメラ座標値
画像座標値
1
内部パラ
メーター
K

2.SLAMにおける
Gr?bner basis (18)(例)5点アルゴリズム(エピポーラ拘束）
Rc1→c2 &tc1→c2
これらが同?平?上
→スカラー3重積が0
カメラ座標

2.SLAMにおける
Gr?bner basis (19)(例)5点アルゴリズム(基本?列の拘束)
Rc1→c2 &tc1→c2
SVD

2.SLAMにおける
Gr?bner basis (20)
? [Kruppa, 1913] : ?々11個の解
? Maybank, Faugerasによって改善。?々10個の解
? [Philip,1996]：13次?程式を解く?法（Maybankよりefficientで
practical)
? [Nister,2004]：10次?程式を解く?法→ OpenCVのfive-point.cppで
引?
? [Stewenius,2006]：Gr?bner basisを?いて10次?程式に帰着
→Open GVのfivept_steweniusで引?
※[Nister,2007]：代数的に厳密解を得るには少なくとも10次の?程式
を解く必要があることをガロア理論によって証明
(例)5点アルゴリズム(先?研究)
[Kruppa,1913]“Zur Ermittlung eines Objektes aus zwei Perspektiven mit innerer Orientierung.” [Philip,1996]” A non-iterative algorithm for determining all essential matrices corresponding to five point
pairs. ” “Motion from point matches: Multiplicity of solutions.” Using galois theory to prove structure from ? motion algorithms are optimal.

2.SLAMにおける
Gr?bner basis (21)(例)5点アルゴリズム(連??程式へ）
10個の?線形3変数連??程式
代?
5対応

2.SLAMにおける
Gr?bner basis (22)
6pt, calibrated
radial distortion,
CVでの最?問題
http://cmp.felk.cvut.cz/old_pages/mini/

2. SLAMにおける
Gr?bner basis
SLAMにおける5点アルゴリズム…Trackingの初期化
5点アルゴリズムの問題設定…2視点,歪みなし,内部パラメータ既知,5対応
エピポーラー拘束…対応のカメラ座標による制約
5点アルゴリズムの先?研究…openGVでのfivept_stewenius
CVでの最?問題… http://cmp.felk.cvut.cz/old_pages/mini/
まとめ

3. Gr?bner basis ??
イデアルと?成
連??程式とイデアル
単項式順序
余りの?意性
Gr?bner basis導出アルゴリズム

3.Grobner Basis
?? (25)イデアルと?成

3.Grobner Basis
?? (26)連??程式とイデアル

3.Grobner Basis
?? (27)連??程式とイデアル

3.Grobner Basis
?? (28)連??程式とイデアル(疑問点1)

3.Grobner Basis
?? (29)単項式順序

3.Grobner Basis
?? (30)(例)単項式順序
OK

3.Grobner Basis
OK

3.Grobner Basis
“Ideals,Varieties ,and Algorithm”
他にも無限に…

3.Grobner Basis
?? (33)連??程式とイデアル(懸念点2)

3.Grobner Basis
?? (34)余りの?意性

3.Grobner Basis
?? (35)Gr?bner 产补蝉颈蝉を求めるアルゴリズム
最初は与えられた多項式からスタート！

3.Grobner Basis
多項式2つを取る

3.Grobner Basis
S多項式を既にある多項式達で割った余りを追加

3.Grobner Basis

3.Grobner Basis
Gr?bner basisを求めるBuchbergerのアルゴリズムは
例題で多項式を追加していた流れととほとんど同じ！

3.Grobner Basis
?? (40)連??程式とイデアル(懸念点その他)

3. Gr?bner basis ??
まとめ
イデアルと?成…和と多項式倍を組み合わせてイデアル?成！
連??程式とイデアル…同じイデアルの中で変数を減らす！
単項式順序…割り算に向いた順序、無限にある！
余りの?意性…余りが割り算の順序によらない
Gr?bner basis導出アルゴリズム…例題の解法！

4. 固有値問題に帰着
させる?法
消失定理による解法の問題点
商環
action matrixの固有値問題
具体例

4.固有値問題に帰
着させる?法 (43)消失定理による解法の問題点

着させる?法 (44)この章での?法

着させる?法 (45)商環
後のスライドで具体例を通して説明します

着させる?法 (46)action matrix

着させる?法 (47)(例題)action matrix
多項式f1,…,fs
Gr?bner basis
g1,…,gt
基底B
写像[g]→[fg]の
基底Bの表現?
列mf
Mfの固有値f(p)
Gr?bner basisは3章のBuchbergerのアルゴリズムで求めた

着させる?法 (48)action matrixによる解答例1/3(標準基底)
多項式f1,…,fs
Gr?bner basis
g1,…,gt
基底B
写像[g]→[fg]の
基底Bの表現?
列mf
Mfの固有値f(p)

着させる?法 (49)action matrixによる解答例2/3(表現?列)
多項式f1,…,fs
Gr?bner basis
g1,…,gt
基底B
写像[g]→[fg]の
基底Bの表現?
列mf
Mfの固有値f(p)

着させる?法 (50)action matrixによる解答例3/3(固有値問題)
多項式f1,…,fs
Gr?bner basis
g1,…,gt
基底B
写像[g]→[fg]の基底
Bの表現?列mf
Mfの固有値がf(p)

着させる?法 (51)action matrixによる解答例3/3(固有値問題)
多項式f1,…,fs
Gr?bner basis
g1,…,gt
基底B
写像[g]→[fg]の基底
Bの表現?列mf
Mfの固有値がf(p)

4. 固有値問題に帰着
させる?法
消失定理による解法の問題点…単項式順序依存、累積誤差
商環…多項式全体をイデアルの同値類で割ったもの
action matrixの固有値問題…[g]→[xg]の表現?列の固有値がxの解
まとめ

1.Introduction 53
? Gr?bner basis導出の?速化
? Traceアルゴリズム
? F4
? FGLM(順序変換)
? Gr?bner basis導出の?動化
? Syzygyを使った?法
? Beyond Gr?bner bases: Basis Selection
for Minimal Solvers
…
次回予告？
技術書典8に計数?学科、物理?学
科で出展します！僕もGr?bner
basisに関して記事を書く予定！

狠狠撸

コンピュータービジョンのためのグレブナー基底入门1

More Related Content

コンピュータービジョンのためのグレブナー基底入门1