Share
Embed
Learning to Solve Hard Minimal Problems
2022/08/07に開催された第11回全日本コンピュータビジョン勉強会「CVPR2022読み会」(前編)で発表した資料です。
https://kantocv.connpass.com/event/253622/
Takuya MINAGAWA
August 07, 2022
Transcript
36 slides
-
自己紹介 2 株式会社ビジョン&ITラボ 代表取締役 皆川 卓也(みながわ たくや) 博士(工学) 「コンピュータビジョン勉強会@関東」主催 株式会社フューチャースタンダード
技術顧問 略歴: 1999-2003年 日本HP(後にアジレント・テクノロジーへ分社)にて、ITエンジニアとしてシステム構築、プリ セールス、プロジェクトマネジメント、サポート等の業務に従事 2004-2009年 コンピュータビジョンを用いたシステム/アプリ/サービス開発等に従事 2007-2010年 慶應義塾大学大学院 後期博士課程にて、コンピュータビジョンを専攻 単位取得退学後、博士号取得(2014年) 2009年-現在 フリーランスとして、コンピュータビジョンのコンサル/研究/開発等に従事(2018年法人化) http://visitlab.jp -
紹介する論文 3 Learning to Solve Hard Minimal Problems
Petr Hruby (ETH Zurich), Timothy Duff (University of Washington), Anton Leykin (Georgia Institude of Technology), Tomas Pajdla (Czech Technical University in Prague) Best Paper 選んだ理由: -
概要 4 5点アルゴリズムやScrantonアルゴリズムなどでカメラの 姿勢推定を行うには、複数の偽の解をもつ連立方程式 を解かなければならない。 RANSACの場合、1回のサンプリングごとに問題を解く 本手法では、以下の方法によって偽の解を避けて、高速
に(1つの問題を70μs以下で)解くことが出来る 1. 問題/解のペアを学習 2. 入力となる問題から、近い問題と解のペアを識別問題として 解く 3. 上記の問題/解のペアを始点として、問題/解空間を入力問 題まで追跡 -
カメラポーズ推定(=各点の奥行推定) 9 𝑣𝑘,𝑖 = 𝑥𝑘,𝑖 𝑦𝑘,𝑖 1 x y z
𝑋𝑘 = 𝜆𝑘,𝑖 𝑣𝑘,𝑖 = 𝜆𝑘,𝑖 𝑥𝑘,𝑖 𝑦𝑘,𝑖 1 𝐶𝑖 𝐶𝑖 : 𝑖番目のカメラ 𝑣𝑖,𝑘 : 𝑘番目の点の𝑖番目のカメラ画像上の座標(既知) 𝜆𝑘,𝑖 :𝑘番目の点の𝑖番目のカメラから見た奥行(未知) 𝑋𝑘 : 𝑘番目の点の三次元座標 -
5点アルゴリズム 10 5点中任意の2点𝑘、𝑚を選択 𝜆𝑘,1 𝑣𝑘,1 − 𝜆𝑚,1 𝑣𝑚,1
2 = 𝜆𝑘,2 𝑣𝑘,2 − 𝜆𝑚,2 𝑣𝑚,2 2 5 2 = 10個の連立方程式を解き奥行𝜆𝑘,𝑖 を求める 𝑘、𝑚間のカメラ1から見た距離 𝑘、𝑚間のカメラ2から見た距離 10個程度の幾何学的にも整合性の取れた似の解が現れる -
Scrantonアルゴリズム 11 4点中任意の2点𝑘、𝑚を選択し、距離を比較 𝜆1,1 = 1の制約をパラメータ𝑙で緩和 𝜆𝑘,1
𝑣𝑘,1 − 𝜆𝑚,1 𝑣𝑚,1 2 = 𝜆𝑘,2 𝑣𝑘,2 − 𝜆𝑚,2 𝑣𝑚,2 2 𝑣1,1 + 𝑙[0; 1; 0] − 𝜆𝑚,1 𝑣𝑚,1 2 = 𝜆1,2 𝑣1,2 − 𝜆𝑚,2 𝑣𝑚,2 2 272個程度の幾何学的にも整合性の取れた似の解が現れる -
RANSAC 12 対応点をランダムに サンプリング サンプリングされた点 からカメラポーズ推定 推定されたポーズを元に対 応点を他のカメラへ投影 誤差が閾値以内の点 (inlier)の数をカウント
最もinlierが多かった ポーズを採用 5点アルゴリズムなら5組 Scrantonなら4組 本手法の適用範囲 →偽の解を避ける -
Pick&Solveアプローチ(本手法) 15 従来手法 本手法 画像中の対 応点をサンプ リング 近い問題aを 識別 aを始点にカメラ
ポーズsを追跡 最も良い解 を更新 -
問題-解 多様体𝑀 17 問題𝑝と解sのペア が作る多様体𝑀 問題𝑝が所属する ベクトル空間𝑃 𝑀を𝑃へ投影 𝜋: 𝑀
→ 𝑃 例: 𝑥3 + 𝑎𝑥 + 𝑏 = 0 𝑝 = (𝑎, 𝑏) 𝑠 = 𝑥 問題𝑝によって1-3 個の解sを持つ -
5点アルゴリズムの問題𝑝と解𝑠の定義 18 𝑣𝑘,𝑖 = 𝑥𝑘,𝑖 𝑦𝑘,𝑖 1 x y z
𝑋𝑘 = 𝜆𝑘,𝑖 𝑣𝑘,𝑖 = 𝜆𝑘,𝑖 𝑥𝑘,𝑖 𝑦𝑘,𝑖 1 𝐶𝑖 𝐶𝑖 : 𝑖番目のカメラ 𝑣𝑖,𝑘 : 𝑘番目の点の𝑖番目のカメラ画像上の座標(既知) 𝜆𝑘,𝑖 :𝑘番目の点の𝑖番目のカメラから見た奥行(未知) 𝑋𝑘 : 𝑘番目の点の三次元座標 𝑝 = (𝑥1,1 , 𝑥2,1 , 𝑥3,1 , 𝑥4,1 , 𝑥5,1 , 𝑦1,1 , 𝑦2,1 , 𝑦3,1 , 𝑦4,1 , 𝑦5,1 , 𝑥1,2 , 𝑥2,2 , 𝑥3,2 , 𝑥4,2 , 𝑥5,2 , 𝑦1,2 , 𝑦2,2 , 𝑦3,2 , 𝑦4,2 , 𝑦5,2 ) 𝑠 = (𝜆1,1 , 𝜆2,1 , 𝜆3,1 , 𝜆4,1 , 𝜆5,1 , 𝜆1,2 , 𝜆2,2 , 𝜆3,2 , 𝜆4,2 , 𝜆5,2 ) 5点の座標x2カメラ→20パラメータ 5点の奥行x2カメラ –1 →9パラメータ ただし𝝀𝟏,𝟏 = 𝟏 -
Scrantonアルゴリズムの問題𝑝と解𝑠の定義 19 𝑣𝑘,𝑖 = 𝑥𝑘,𝑖 𝑦𝑘,𝑖 1 x y z
𝑋𝑘 = 𝜆𝑘,𝑖 𝑣𝑘,𝑖 = 𝜆𝑘,𝑖 𝑥𝑘,𝑖 𝑦𝑘,𝑖 1 𝐶𝑖 𝐶𝑖 : 𝑖番目のカメラ 𝑣𝑖,𝑘 : 𝑘番目の点の𝑖番目のカメラ画像上の座標(既知) 𝜆𝑘,𝑖 :𝑘番目の点の𝑖番目のカメラから見た奥行(未知) 𝑋𝑘 : 𝑘番目の点の三次元座標 𝑝 = (𝑥1,1 , 𝑥2,1 , 𝑥3,1 , 𝑥4,1 , 𝑦1,1 , 𝑦2,1 , 𝑦3,1 , 𝑦4,1 , 𝑥1,2 , 𝑥2,2 , 𝑥3,2 , 𝑥4,2 , 𝑦1,2 , 𝑦2,2 , 𝑦3,2 , 𝑦4,2 , 𝑥1,3 , 𝑥2,3 , 𝑥3,3 , 𝑥4,3 , 𝑦1,3 , 𝑦2,3 , 𝑦3,3 , 𝑦4,3 ) 𝑠 = (𝜆1,1 , 𝜆2,1 , 𝜆3,1 , 𝜆4,1 , 𝜆1,2 , 𝜆2,2 , 𝜆3,2 , 𝜆4,2 , 𝜆1,3 , 𝜆2,3 , 𝜆3,3 , 𝜆4,3 ) 4点の座標x3カメラ→24パラメータ 4点の奥行x3カメラ –1 →11パラメータ ただし 𝝀𝟏,𝟏 = 𝟏 -
ホモトピー継続 (Homotopy Continuation) 20 1. 問題𝑝から、始点となる問題/解のペア(𝑝0 , 𝑠0 ) ∈
𝑀を選 択 2. 問題空間𝑃上で𝑝0 から𝑝へのパスを算出 3. 多様体𝑀上で上記パスを追跡することで解𝑠を算出 問題のパス 解のパス 𝑠0 𝑝0 -
Solve&Pick VS Pick&Solve 22 問題𝑝を解いて解集合𝑆を計算 解集合𝑆から最適な𝑠を選択 問題𝑝からアンカーとなる問 題/解のペア(𝑝0 , 𝑠0
)を選択 (𝑝0 , 𝑠0 )から𝑝の解𝑠をホモト ピー継続を用いて解く Solve&Pick (従来法) Pick&Solve (本手法) -
Solve&Pick VS Pick&Solve 23 問題𝑝を解いて解集合𝑆を計算 解集合𝑆から最適な𝑠を選択 問題𝑝からアンカーとなる問 題/解のペア(𝑝0 , 𝑠0
)を選択 (𝑝0 , 𝑠0 )から𝑝の解𝑠をホモト ピー継続を用いて解く Solve&Pick (従来法) Pick&Solve (本手法) 識別器𝜎を学習 -
Solverの構築 24 問題𝑝からアンカーとなる問題/解のペア(𝑝0 , 𝑠0 ) を算出する識別器𝜎を学習 1. 3Dモデルからデータセット𝐷をサンプリング 2.
データセット𝐷からアンカー𝐴を抽出 3. 問題𝑝を与えたとき、始点𝑝(𝑝0 , 𝑠0 ) ∈ 𝐴を出 力する識別器𝜎を学習 -
Solverの構築 25 問題𝑝からアンカーとなる問題/解のペア(𝑝0 , 𝑠0 ) を算出する識別器𝜎を学習 1. 3Dモデルからデータセット𝐷をサンプリング 2.
データセット𝐷からアンカー𝐴を抽出 3. 問題𝑝を与えたとき、始点𝑝(𝑝0 , 𝑠0 ) ∈ 𝐴を出 力する識別器𝜎を学習 -
学習データの作成 26 カメラと3D Model上の点のサン プリング • 5pt Algorithm: • Camera
x2, Point x5 • Scranton: • Camera x3, Point x4 ETH 3D Dataset サンプリングした点を各 カメラへ投影し、問題と 解のペア(𝑝, 𝑠)を生成 サンプリングした 𝑝𝑖 ,𝑠𝑖 から他のペア(𝑝𝑗 , 𝑠𝑗 )へ 追跡可能か調査 追跡可能な場合、 𝑝𝑖 , 𝑠𝑖 と(𝑝𝑗 , 𝑠𝑗 )間に エッジを生成 (𝑝, 𝑠)を頂点、追跡 可能性をエッジとし たグラフ生成 グラフ全体をカ バーする頂点 をアンカー𝐴と する -
アンカーの選択 27 ETH 3D DatasetのOfficeおよびTerrainsから1K, 4K, 10K, 40Kの問題/解をサンプリングして学習データセット𝐷を作 成
何個のアンカーでデータセット𝐷のどれだけの割合をカ バーできるか -
Solverの構築 30 問題𝑝からアンカーとなる問題/解のペア(𝑝0 , 𝑠0 ) を算出する識別器𝜎を学習 1. 3Dモデルからデータセット𝐷をサンプリング 2.
データセット𝐷からアンカー𝐴を抽出 3. 問題𝑝を与えたとき、始点𝑝(𝑝0 , 𝑠0 ) ∈ 𝐴を出 力する識別器𝜎を学習 -
始点識別器σ(𝑝)の学習 31 カメラと3D Model上の点のサン プリング • 5pt Algorithm: • Camera
x2, Point x5 • Scranton: • Camera x3, Point x4 ETH 3D Dataset サンプリングした点を各 カメラへ投影し、問題と 解のペア(𝑝, 𝑠)を生成 アンカー𝐴の各問題/解 𝑝0 , 𝑠0 から、サンプリ ングした 𝑝𝑖 , 𝑠𝑖 へ追跡 可能か調査 𝑝𝑖 へ追跡可能なすべて のアンカーを𝑝𝑖 のラベ ルとする。追跡可能な アンカーが無い場合 TRASHラベルをつける 入力が𝑝𝑖 、出力が 𝐴 + 1クラスのMLPを学習 -
始点識別器σ(𝑝)の学習 32 識別器の評価 評価データ: delivery_area facade
学習データ 上記以外の23シーケンス 始点 𝑝0 , 𝑠0 の選択 B1:すべてのアンカー (𝑚 = 𝐴 ) B2: ユークリッド距離が最 も近いアンカー (𝑚 = 1 ) B3: マハラノビス距離が最 も近いアンカー (𝑚 = 1 ) MLP: MLPの出力上位m個 MLPT: MLPの出力上位1 個 Recall アンカーの学習 データカバー率 -
Solverの実行 33 問題𝑝を解く 1. 問題𝑝に対し正規化や対応点順序入れ 替え等の前処理 2. 識別器𝜎を用い、アンカー𝐴から始点 𝜎 𝑝
= (𝑝0 , 𝑠0 )を選択 3. (𝑝0 , 𝑠0 )を始点としてホモトピー継続で 問題𝑝の解𝑠を算出 -
ホモトピー継続 34 問題のパスが 𝑝 𝑡 = 1 − 𝑡
𝑝0 + 𝑡𝑝 で与えられた ときの解𝑠 𝑡 を𝑠0 からステップΔ𝑡毎に求めていく(追跡) 問題のパス 解のパス 𝑠0 𝑝0 ルンゲ=クッタ法で予測 (predictor) ニュートン法で修正 (corrector) 𝑠 𝑝 -
実験 35 CVPR2020 RANSAC Tutorial Dataset 4950 Camera
Pairs 画像間の対応点は与えられている(ノイズおよび誤対応含む) Rotationの誤差が10度以内の割合 -
まとめ 36 機械学習とホモトピー継続を用いて偽の解を 避けて幾何学的な最適化問題を高速に解く 手法を提案 問題と解のペアの多様体𝑀を生成 問題𝑝を与えたとき、始点となる𝑀上の点(𝑝0
, 𝑠0 ) を出力する識別器𝜎を学習 ホモトピー継続によって(𝑝0 , 𝑠0 )から問題𝑝に対す る解𝑠を算出