SfMについて #3.6:AOS(KAZEの非線形拡散フィルタの計算)
はじめに
前回記事ではKAZEの論文を確認し、どのように特徴量抽出を行っているのかを確認しました。 ただし、KAZEで利用している非線形拡散フィルタである偏微分方程式を解く方法AOS(Additive Operator Splitting)について、 引用されている文献を確認しないとよくわからなかったので、本記事はその補足を行うことを目的とします。
導入
KAZEの論文ではAOSに対してJ. Weickertらの論文1を引用しています。 1998年の論文であり、少し古いですが読み込んでKAZEを理解したいと思います。 実はKAZEの改良版であるA-KAZEではAOSは使われていませんが、A-KAZEでも非線形拡散フィルタを解くことに変わりはありませんので、 理解も進むかと思います。J. Weickertらの論文でも順を追ってAOSが必要になった理由が書かれていますので、 本記事もその流れに沿って概説していきます。
偏微分方程式を離散化する
画像をベクトル として、このベクトルはという次元空間から写像されたものだと考えます。 カラー画像はの平面空間をのベクトルに変換していると考えるようです。
非線形拡散フィルタは時間に対して偏微分方程式によって表現されます。 これはCLMCフィルタと呼ばれるようで次式の形です。
これはという画像の時間的変化を表現した式であり、は勾配を計算するオペレータです。 この段階では細かいことは気にしないでください。 重要なことはあくまでも時間で表現される連続値であることです。 コンピュータで扱うため、かつ時間である空間を、画像処理で扱うスケール空間に対応させていく必要があるのです。
連続値で表された微分方程式を離散化して解くにあたって、 時刻のときの初期値は、と定めます。 画像の端(論文ではと書いてありましたが)に対しては境界条件としてとします。 これはいわゆるノイマン問題としての仮定だと思います。
拡散という現象は時間が経過するほど詳細な情報が薄れていき、均一に、つまり単純な情報を示すようになります。 画像処理に対して拡散フィルタを施すということは、時間を大きくするほど高周波数が減っていき単純な画像になっていくことになります。 一般的な物理現象としての拡散については以下の記事がわかりやすいです。
さて、非線形拡散フィルタを施すことで画像をボヤけさせていきますが、エッジは特徴的であると考えられるため、 エッジは他よりもボヤけさせたくありません。 なので、エッジの強さを表すが大きいほど、拡散の強さが低減するような形にしてあげます。
として、はガウシアンカーネルです。 そして、拡散の強さを次のようにしてあげればいいわけです。
KAZEの記事に書いたものと若干異っていますが、論文に従って記載しています。 これらの連続値である計算をexplicitな計算で離散化していきます。
整理すると、連続値バージョンでは、
であった計算を離散化すると、
となるのです。 更に行列を駆使して整理してあげると、
と書けて、KAZE論文で出てきた式になります。 ただし、KAZE論文では謎であったものが、
であることが判明します。
結局のところexplicitになることが次式のように整理できるのでわかります。 explicitとは、陽的にかける、つまりの状態をのみで直接表現できて、他に方程式を解く必要がないことを意味します。
しかし、このexplicitな方程式を安定的に解くためには、いくつかの条件を満たす必要があり、 特に時間幅を次のように設定しなくてはなりません。
これは文献によると画像処理においては、拡散率の上限を1にするために、となり、 これはとなってしまいます。 このステップ幅はかなり厳しい制約条件と言えるため、離散化したときの正確さvs安定性という議論につながります。 そして、これを解決するためにsemi-explicitな解法としてAOSが求められた理由になります。
AOS
1次元の拡散フィルタ
まず1次元拡散フィルタの連続値バージョンである、
という式を少し複雑に離散化する別の方法を次のように考えるようです。
これをいじると、
となりますが、この式ではに対して陽的な表現にはなっていません。 なぜならば、これを解くためには左辺に存在する線形システムを解く必要があるためで、 このような表現をsemi-explicitといいます。
左辺の行列を
と考えます。 実はこの行列は優対角行列というものになります。 優対角行列とは、行列の要素をとすると、
となる特性をもつ行列を言います。 そして優対角行列は正則であるという特性も持ちます。 なので、
とできてしまい、semi-explicitにするとどのような時間幅を選んでも収束性を脅かすことなく、所望の正確さをもった離散化が行えてしまうのだ、そうです。
今、という線形システムを考えて、が三重対角行列であるとします。 つまり次の形をしている行列であり、これはThomas algorithmというガウスの消去法の一種で解くことができます。
Thomas algorithmは3ステップの処理を行う方法で、
- 行列をLR分解する
- という、下二重対角行列と上二重対角行列にします
- すると、という形になる
- 前進代入
- をに関して解く
- この時点におけるフィルタをcausal filterという、らしい
- 後退代入
- をに関して解く
- この時点におけるフィルタをanticausal filterという、らしい
と解きます。 この処理は計算量がかなり低く、で抑えることができるのです。 この辺りの計算は書き下してみると簡単にわかります。
m次元の拡散フィルタ
論文に沿って1次元の拡散フィルタをexpicitに解く場合と、semi-explicitに解く場合を見てきました。 m次元の場合も偏微分方程式のことを考えるとそのまま拡張すればOKです。
explicitなときは、
semi-explicitなときは、
となります。 m次元のexplicitなときは解の安定性条件が、
となります。 m次元の場合は次元が大きくなるほどに時間幅がとても小さくする必要出てきてしまうわけです。
AOSではsemi-explicitなアプローチの利点をフル活用するために、
と細工を施す。 このように細工を施しても、元々の微分方程式を1次のテイラー展開してみると、implicitなもの、semi-implicitなものと一貫性を保っているらしい。
Splitting Operator(またはMethod)とは、微分方程式を解きやすくするテクニックで、1つの変数を複数の変数に分けていく手法を指すようです。 乗法(Multiplicative)ではなく加法(Additive)なアプローチであるため、 すべての次元方向に対しても同じ方法で分割(Split)することが可能です。 Multiplicative Splittingは可換性を保てれるとは限らないようです。
普通のガウシアンフィルタを使って拡散させていく方法は、とした線形フィルタリングと等価です。 このとき時間とスケールの関係となりますので、 AOSでも同じ関係を使うことにするらしいです。
AOSは偏微分方程式を解くための工夫であり、数式を追っていくことに疲れて全体の流れを忘れてしまいそうになります。 これまでの処理フローは文献のV.ALGORITHMIC STRUCTUREに記載がありますので、 これを見たほうが全体を通したフローがわかりやすいと思います。
まとめ
今回はKAZEで使われているAOSに関して論文を確認しました。 熱力学や流体力学など機械系でも見覚えのある拡散フィルタでしたが、すっかり忘れてしまっていました。。 AOSと検索してもなかなか出てきませんが、拡散フィルタの離散化は画像処理とは別分野での資料が見つかる可能性が高そうなので、そちらで検索しつつ勉強すると、雰囲気がつかめると思います。
なお、上記の記事は間違いや誤認識が含まれる可能性もありますので、A-KAZEの論文も確認したら、適宜修正したいと思います。
文献
SfMについて #3.5:KAZE
はじめに
前回の記事の続きです。が、一部追加執筆中となっていますのでご了承ください。
mlengineer.hatenablog.com mlengineer.hatenablog.com
引き続きOpenSfMの精度向上方法を考えていく上で、特徴量抽出手法のうちKAZE、AKAZEという手法についても知る必要があると感じましたので、まずはKAZEの論文1を読んでまとめることにしました。 SfMから若干脱線するので3.5回目ということにします。 (AKAZEは4.5回目になるかも?)
特徴量抽出とはなんぞや?
ある物体aが写っている画像Aと、同一の物体aを異なる位置から撮影した画像A'があったとします。 この物体aは画像Aであろうが画像A'であろうが同じ物体aが写っていることには変わりはありません。 しかし、どうやればコンピュータにこれを教えることができるのでしょうか?
それは物体aの特徴を的確に教えてあげることで実現できそうです。 つまり物体aの特徴とは何なのか?という哲学にも通じそうな問題設定になります。
画像上で物体の特徴を決める上では、従来から2段階の方法をとることが多いです。 これは前回記事でも紹介したとおり以下のような流れで、1段階目を特徴点抽出(Detector)、2段階目(Descriptor)を特徴量記述といいます。 この2段階をまとめて特徴量抽出(Feature Extraction)と呼びます。
なぜ2段階も必要になるのかというと、それぞれの役割を考えると簡単です。 人の視覚・認知能力と違い、コンピュータが画像上から物体aを認識するためには以下のことができるといい感じになりそうです。
- 画像に写っている中から物体を見つける(Detectorの役割)
- ここでいう物体は様々で、物体aだけではなく物体b、物体cなどたくさんあるイメージ
- 何もしない状態では、コンピュータは背景と物体の区別すらつきません
- 画像が異なっていても、その物体を同一視できる/区別できる特徴を把握する(Descriptorの役割)
- 画像Aには物体a、物体b、物体cが写っているとして、画像A'には物体a、物体d、物体eが写っているとします。 それぞれの画像に写る物体aが同じものであると認識したいですが、その一方で物体aは物体b、c、d、eとも異なるということも認識する必要があります
従来用いられる画像の特徴量抽出という技術は、この2段階をそれぞれ実現するための手法であると言えます。 さて、人は背景が白色で、その手前に黒色の物体が置いてあるとき容易に物体と背景を区別できます。 これは色や輝度の違いがあれば、画像に写る背景と物体を区別できるということになります。 色や輝度の違いとは、ある注目領域に比べてその周辺領域での変化が急激であるということです。 色や輝度の変化が急激な箇所は、画像中では線(エッジ)や角(コーナー)として発生し、この情報を使えば背景と物体の区別がつくということです。 Detectorでも同様にして画像中からエッジやコーナーという特徴点を検出するわけです。
ただし闇雲に特徴点を検出しまくると、今度は安定性に欠けることにも繋がります。 ごま塩ノイズなどが画像に発生しているとき、輝度が急激に変化しているピクセルをありったけ特徴点として認めてしまうと、 物体とは関係のない特徴点だらけになってしまうでしょう。 つまり、Detectorには撮影状況に対するロバスト性が求められます。
一方でDescriptorは特徴点の周辺領域の画像(ピクセル)を用いて、特徴量というベクトル化を行う処理になります。 ベクトル化することで、画像Aの物体は画像A'の物体と同じか?という類似性を数値的に算出することが可能になります。 しかし異なる画像AとA'のそれぞれに同じ物体aが写っていたとしても、その大きさや角度、明るさといった状態が変わってきてしまいます。 このような状況でも画像検索としては、同じ物体aだよ!という結果が望ましいので、 Descriptorに対しても撮影状況が変わっても同一視できる普遍性が重要になってきます。
正確には、物体として認識するためには特徴量を複数個集めてコンピュータに教えてあげることが必要で、 簡単な方法ですが良く用いられる方法がBag-of-Words(BoW)という方法です。 事前にある物体aの画像をたくさん集めて、これらの画像から特徴量をいっぱい取得してあげることで、物体aを構成する特徴量の集合を取得します。この特徴量の集合から新たなベクトルを作ってあげて、それを物体aとして覚えておく方法です(辞書;Dictionaryをつくる、と言います)。 このように多くの物体を辞書に登録しておくことで、物体の認識を行います。
KAZE
KAZEという手法は、P. F. AlcantarillaらによってEur. Conf. on Computer Vision (ECCV) 2012にて発表されたもので、 ECCV 2012はイタリアのフィレンツェで開催されたようです。 本家のサイトはこちら2です。 KAZE=風という手法名であり、そのまま発音してOKです。 OpenSfMでKAZEを改良したAKAZEが利用できるため、そのベースとなっている本手法についても論文を確認したいと思います。
さて、KAZEはDetectorおよびDescriptorの両方をまとめた呼び名です。 この手法の特徴は以下の点です。
- 風のように非線形なシステムに従ってその流れを表現するように、画像分野のマルチスケール画像の生成を扱いたい
- 非線形拡散フィルタ(nonlinear diffusion filter)を使ってマルチスケール画像から特徴量を抽出する
- KAZEよりも従来の手法では1枚の画像からガウシアンピラミッドやそれを近似した画像ピラミッドをつかう
- ガウシアンピラミッドなどは画像全体をぼやけさせるため、ノイズをボヤけさせてくれるが、背景と物体といった境界線までボヤけさせる
- そのため、特徴点の位置精度の低下を招き、識別性能も低下させてしまう
- 非線形拡散フィルタを使ってこの問題を解決する
- Additive Operator Splitting (AOS)というテクニックを使って非線形拡散フィルタによるマルチスケール画像を作る
このようにしてKAZEでは画像からスケール不変(物体の大きさに依存しにくい)で変形に強い特徴量抽出を行います。 実験結果ではSURFやCenSurEと比べて若干の計算量増加で抑えています。
以下は論文に沿って見ていきます。
非線形拡散フィルタ
非線形拡散フィルタとはなんぞや?というと次式で表現された、 輝度が時間/スケールに対してどのように発展していくのかを意味する偏微分方程式です。
ここで、は発散していく何かしらの関数であり、は勾配を算出するオペレータです。 は伝導率を表す関数で画像中の位置(空間)と時間/スケールに依存したものとします。 と輝度勾配との内積をとることで時間/スケール、そして空間的な拡散の仕方を示します。 ただし簡単にするためにはスカラーでもテンソルでもOKです。 は時間を意味しますがスケールパラメータとして扱われます。 流体のように時間が経過するにつれ発散するように進展していき、 が大きくなるに従い複雑な形状ではなく単純な形状を表現するようになります。
画像分野に非線形拡散フィルタが用いられ始めたのは1990年のPerona, P.とMalik, Jらの論文からということでかなり歴史があります。 彼らの論文では伝導率を輝度勾配の強さ(magnitude)で表現することで画像中にあるエッジでの拡散の強さを低減していたようで、KAZEの文献では次式で表現されています。
オリジナルの画像に対してはのガウシアンフィルタをかけてから勾配をとったものです。 このような関数の形はいくつか提案されていて、Perona, P.とMalik, Jらは次の、を使っています。
はパラメータで拡散の強さを調整します。 は高コントラストを助長させる効果があり、 を逆に低コントラストで広い領域を助長させる効果があります。
さらに2001年にWeickert, J.は、エッジの両側で拡散の強さは早く、一方でエッジ自体の拡散は弱くなるような次の形状を提案しています。 これによってエッジは非線形拡散を行っても残りやすくなります。
このは画像中の物体と物体を跨ぎながら影響するブラーよりも、各物体内や境界線内という限られた領域内に影響するブラーのほうが強くなります。 文献中では、
That selective smoothing prefers intraregional smoothing to in- terregional blurring.
と言及されています。
KAZEの文献では、パラメータをオリジナル画像に対して平滑化をかけたあとの画像から勾配ヒストグラムを作成し、 70パーセンタイルの値を使っています。 前回記事でOpenSfMのconfigについて触れていますが、AKAZEでもakaze_kcontrast_percentileという同様のパラメータがあり、 70%(=0.7)でとして設定されていることが確認できます。
... # Params for AKAZE (See details in lib/src/third_party/akaze/AKAZEConfig.h) akaze_omax: 4 # Maximum octave evolution of the image 2^sigma (coarsest scale sigma units) akaze_dthreshold: 0.001 # Detector response threshold to accept point akaze_descriptor: MSURF # Feature type akaze_descriptor_size: 0 # Size of the descriptor in bits. 0->Full size akaze_descriptor_channels: 3 # Number of feature channels (1,2,3) akaze_kcontrast_percentile: 0.7 akaze_use_isotropic_diffusion: no ...
より強いコントラストであるエッジを使いたければ、このパラメータを高く設定し、 逆に低いコントラストであるエッジも使いたいときは低めに設定する必要があります。 の場合で、がどの様な影響を与えているのかは、KAZEの論文Fig.1.[^1]にわかりやすい図があります。 AKAZEを使ってダンテのデスマスクを3次元復元する際に調整する必要がでてくるかもしれません。
AOS
論文の流れに沿ってみていくと、次はAOSについて言及されています。 ご存知の通り、非線形な偏微分方程式を解析的に解くことは難しいです。 解析的に解くとは、方程式が与えられている場合に、ごにょごにょ手計算を行いという形式で解を求めることです。 解析的に解くことが難しいため、機械学習の界隈では損失関数を決めて最小にするような最適化を行います。
そのため、非線形拡散フィルタに対しては偏微分を離散化する上で、AOSというテクニックを使います。 一般的に非線形な偏微分方程式は線形化して近似するような方法をとります。 先に示したに関する偏微分方程式は半陰的(semi-implicit)に解くと、次のように書けます。
ここでは誘導率を行列化したものです。 半陰的に解くことでステップサイズに依らず安定的に算出ができる特性を持ちます。 画像分野でのスケール空間で計算を行おうとすると大きな時間幅を扱いたいので、このときに便利になります。 上記の式形状は線形システムとなるので、三重対角行列をもつ線形システムをトーマスのアルゴリズムを使い効率的に解くことが可能となるようです。
KAZEの特徴点検出および特徴量記述
さて、ようやく非線形拡散フィルタによって、オリジナル画像からスケール空間に非線形にぼやけさせた画像たちを生成することができます。 そしてこのぼやけさせた画像たちから特徴点を検出し、その特徴点をベクトル化する特徴量記述を行います。
特徴点の検出は、SIFTと似た方法を取ります。 まずは非線形拡散フィルタの適用方法を述べていきます。
SIFTでは最初のOctaveの中ではオリジナル画像と同じ画像サイズでフィルタをかけていき、 次のOctaveに進むときにダウンサンプリングすることで画像サイズを小さくしていきます。 しかし、KAZEではダウンサンプリングを行わないようです。 またSIFTではガウシアンフィルタの標準偏差がピクセル単位となりますが、 非線形拡散フィルタでは時間単位に合わせておきたいため、と間のマッピングを決めておきます。
octaveが、sub-levelがであり、次のように初期スケールレベルに対して定めます。 当然ながら、はフィルタをかけた画像を総計何枚作成するのかを示すパラメータで、 とはそれぞれいくつのoctaveをつくるか、いくつのsub-levelをつくるのかを示すパラメータですね。 オリジナル画像に対してで一度ガウシアンフィルタをかけて、ノイズやアーチファクトの影響を少し低減しておき、 その後は非線形拡散フィルタを使います。 ガウシアンフィルタをかけた画像を基底画像(base image)として扱い、この画像からパラメータを定めるわけです。
論文[^1]にあるFig.2.を貼り付けますが、明らかにガウシアンフィルタでは全体がぼやけてしまっていますが、 非線形拡散フィルタではエッジ部分をきれいに残しつつも、細かな構造をぼやけさせることに成功しています。
あとはHessianを使って特徴点を定めるのですが、スケールで正規化したHessianをKAZEでは使います。 これは、ぼやけさせていくことで各スケールにおける画像の勾配強度が低下していく傾向があるからです。 [tex:Li]の非線形拡散フィルタをかけた画像に対応するスケールの画像と、その前後のスケールの画像たちから極大値を取るような位置を探し出して完了です。
特徴量記述は、ほぼほぼSURFと同じ方法で算出しますので省略します。 論文中では文章のみの記述となっていますので、時間ができたときに図示して追記したいと思います。
結局、KAZEでは64次元でベクトル化した特徴量を得ることができます。
まとめ
最後のほうはSURFやSIFTとかなり類似していたので、説明が荒くなってしまいましたが、 KAZEの特性は論文の図を見るだけでかなりわかったかと思います。 時間ができたときに考察についても追記していきます。
文献
SfMについて #3:OpenSfMの中身をみる(detect_features)
はじめに
前回の記事の続きです。 mlengineer.hatenablog.com mlengineer.hatenablog.com
初回記事では、OpenSfMを使ってイタリアで撮影したダンテのデスマスクを3次元復元するサンプルスクリプトを実行し、 2回目以降の記事ではこのサンプルスクリプトが何をやっているのかを確認していき、 最終的には精度向上や手法改善をめざしています。 今回は3回目の記事で、ようやくSfMの中身に近づいていくことができそうです。
OpenSfMの流れをおさらい
OpenSfM 1のサンプルで紹介されている以下のコマンドを実行すると、主に次のような処理が行われるのでした。
bin/opensfm_run_all data/berlin
- extract_metadata
- 対象データのメタデータを取得する処理
- detect_features(●本記事の対象)
- 対象データの各画像から特徴量を取得する処理
- match_features
- 取得した特徴量を画像間でマッチングする処理
- create_tracks
- マッチング結果からカメラ位置推定を行う処理
- reconstruct
- カメラ位置推定の結果から3次元点群を生成する処理
- mesh
- 3次元点群から可視化を行うためにメッシュを生成する処理
- undistort
- カメラパラメータを利用して歪みを軽減する処理
- compute_depthmaps
- カメラパラメータから対象データの各画像の深度マップを生成する処理
本記事では、2. detect_featuresについて見ていきたいと思います。
detect_features
本家の記事では1行しか言及されていなく、非常に心もとないです。
detect_features
This command detects feature points in the images and stores them in the feature folder.
一応、翻訳すると、「このコマンドは画像列から特徴点を見つけて、featureフォルダに格納する」ということです。 特徴点を見つけると言われても、特徴点検出方法はたくさんあるわけで、更には特徴量記述はどうなっているのか?と疑問を持ちます。
そこで以下のファイルを見てみるとpythonスクリプトは3つの重要そうなモジュールをimportしていることがわかります。
from opensfm import bow from opensfm import dataset from opensfm import features
- /OpenSfM/opensfm/bow.py
- Bag-of-wordsを行うモジュールでしょう
- /OpenSfM/opensfm/dataset.py
- データセットや設定ファイルを扱うための関数が入っている
- OpenSfM/opensfm/config.pyという重要なモジュールをインポートしている
- /OpenSfM/opensfm/features.py
- 各画像から特徴点抽出および特徴量記述を行う
- 結果を保存/読込を行う関数をもつ
実は2番目にあげたdataset.pyがimportしているconfig.pyの中には、default_config_yamlという変数に重要な手がかりが散りばめられていました。 以下にyamlの一部を貼り付けます。
... # Params for features feature_type: HAHOG # Feature type (AKAZE, SURF, SIFT, HAHOG, ORB) feature_root: 1 # If 1, apply square root mapping to features feature_min_frames: 4000 # If fewer frames are detected, sift_peak_threshold/surf_hessian_threshold is reduced. feature_process_size: 2048 # Resize the image if its size is larger than specified. Set to -1 for original size feature_use_adaptive_suppression: no # Params for SIFT sift_peak_threshold: 0.1 # Smaller value -> more features sift_edge_threshold: 10 # See OpenCV doc # Params for SURF surf_hessian_threshold: 3000 # Smaller value -> more features surf_n_octaves: 4 # See OpenCV doc surf_n_octavelayers: 2 # See OpenCV doc surf_upright: 0 # See OpenCV doc # Params for AKAZE (See details in lib/src/third_party/akaze/AKAZEConfig.h) akaze_omax: 4 # Maximum octave evolution of the image 2^sigma (coarsest scale sigma units) akaze_dthreshold: 0.001 # Detector response threshold to accept point akaze_descriptor: MSURF # Feature type akaze_descriptor_size: 0 # Size of the descriptor in bits. 0->Full size akaze_descriptor_channels: 3 # Number of feature channels (1,2,3) akaze_kcontrast_percentile: 0.7 akaze_use_isotropic_diffusion: no # Params for HAHOG hahog_peak_threshold: 0.00001 hahog_edge_threshold: 10 hahog_normalize_to_uchar: yes # Params for general matching lowes_ratio: 0.8 # Ratio test for matches matcher_type: FLANN # FLANN(symmetric) or BRUTEFORCE(symmetric), WORDS(one-way), WORDS_SYMMETRIC(symmetric) # Params for FLANN matching flann_branching: 8 # See OpenCV doc flann_iterations: 10 # See OpenCV doc flann_checks: 20 # Smaller -> Faster (but might lose good matches) # Params for BoW matching bow_file: bow_hahog_root_uchar_10000.npz bow_words_to_match: 50 # Number of words to explore per feature. bow_num_checks: 20 # Number of matching features to check. bow_matcher_type: FLANN # Matcher type to assign words to features # Params for VLAD matching vlad_file: bow_hahog_root_uchar_64.npz # Params for matching ...
yamlにはmatchingについての記載もありましたが、次回考えるために省略しました。 このyamlから次の手法が使えそうです。 ちなみに、特徴点検出(Key points Extraction)と特徴量記述(Descriptor)の処理をまとめて特徴量抽出(Feature Extraction)とよぶことが多いかなと思います。
OepnSfMで選択できる特徴量抽出手法を並べました。
- AKAZE(Accelerated-KAZE)
- SURF(Speeded Up Robust Features)
- SIFT(Scale-Invariant Feature Transform)
- HAHOG(Hessian Affine feature point detector + HOG)
- ORB(Oriented FAST and Rotated BRIEF)
このうち、変数default_config_yamlにあるfeature_typeを使うようにできています。 サンプルではHAHOGが使われるということです。 HAHOGは聞いたことがなかったので調べてみると、公式フォーラム2で回答されていて、 実態はHessian Affine特徴点をHOG(Histogram of Oriented Gradients)で記述する実装となっています。 HAHOGの実装は、/OpenSfM/opensfm/src/hahog.ccというpythonバインドするためにC++で書かれています。
HAHOGの性能について考えてみます。 まず特徴点検出であるHessian Affineの効果は、ある物体Aから抽出した特徴点aと、 その物体Aに対してアフィン変換を施した物体A'から抽出した特徴点a'とすると、 aとa'が一致するという利点があります。 これをアフィン不変であるといいます。 正確にはHessian AffineはMSERのようにアフィン不変な領域を抽出する方法です。
HOGは非常に簡単で、SIFTでも使われている特徴点の記述方法です。 特徴点の周りに適当なサイズの領域セルを考えてあげ、このセルの輝度勾配を求めます。 特徴の方向とはのうち、どっちを向いてますか?という話になるので、 を適当な数のビンで分割してあげて輝度勾配によるヒストグラムを作ります。 このようにつくったヒストグラムを更に大きな領域であるブロックで束ねてあげて新たなヒストグラムをつくり、 ベクトルとして扱う、という流れです。 文献3は図がたくさんあってわかりやすいです。 HOGだけを画像に適用する場合は、画像全体をセルに分割して、そのセルを複数個束ねてブロックにして、最終的には画像全体からブロックごとに特徴量を記述することができます。
HAHOGでは安定的な特徴点の周りだけにHOGを適用することで、軽量化しつつも特徴量として扱えるようベクトル化にしたものであると思います。 SURF/SIFTに関しては特許が取られているので、mapillaryとしては簡便な手法方法としてHAHOGを実装したのでは、と感じました。 これがデフォルト設定になっていることが微妙だと思いますが、 1~5の選択肢を考えるとまずAKAZEに変更することで3次元復元したときの精度向上が期待できそうです。 オリジナルはこちら4ですが、AKAZEの性能についてはこちら5がわかりやすいです。 AKAZEの詳細についてはまた今度論文を読んで解説したいと思います。
Params for features
AKAZEが良さそうだと思いますが、configで設定されたパラメータで他の特徴量にも影響しているものは、 yamlの上部にかかれているParams for featuresです。
- feature_root
- 特徴量によって若干動作が異なるが、特徴量記述した結果に対して平方根をとる処理を行いその結果を使う
- feature_min_frames
- 特徴点の検出数がこの数より小さい場合は、ハイパーパラメータを少し調整してくれる
- feature_process_size
- オリジナル画像のサイズを使う場合は-1にする必要がある
- feature_use_adaptive_suppression
- OpenSfM/opensfm/src/csfm.cc内を見る限り、AKAZEのみに影響があるパラメータのようです
feature_rootを実行することで極端な特徴量ベクトルの影響を抑えることができるのかな?と思います。 あまりいい処理だと思いませんが、デフォルトでは使うことになっていました。
feature_min_framesは各画像から取得した特徴点数を評価して、思ったよりも少ない場合は各手法のハイパーパラメータを調整して、 特徴点数を増やしてあげる処理を行います。
feature_process_size はデフォルト設定では画像の幅/高さのうち大きいほうを2048ピクセルにしてしまいます。 常に入力した画像と同じ大きさを使いたい場合は-1にセットすべきで、 ダンテのデスマスクは4K画像を入力しましたが、いつの間にか小さくされていたようです。 画像サイズは大きいほうが特徴点が取りやすくなるのでここは直す必要があります。
feature_use_adaptive_suppressionは、HAHOGの場合は強制的にFALSEになり、 AKAZEを使ったときのみ利用されるようです。 論文を読まないと詳しい処理のイメージがつきませんが、OpenSfM/opensfm/src/third_party/akaze/lib/AKAZE.cppに処理が書かれています。 今回はAKAZEについては詳しく触れるつもりはありませんので、また今度の宿題にしたいと思います。
まとめ
本家サイトでは1行でさらっと書かれており、どのような手法を適用することができるのかわかりにくいですが、 config.pyをみるだけでほぼほぼ十分でした。
特徴量抽出のデフォルト設定がHAHOGであり、初回投稿時のダンテのデスマスクの復元にはこれを利用しています。 単純にAKAZEに変更するだけでも性能が上がりそうです。
更に、てっきり4K画像を入力すればそのまま利用されると思っていましたが、デフォルトconfigはリサイズしてしまうことが判明しました。
AKAZEを利用する上では、更にハイパーパラメータを知る必要がありますが、また今度の宿題とします。
特徴量抽出はそのあとのマッチングをどのように行うかということにも依存します。 次回はmatch_featuresの処理について確認することで、3次元点群を復元する上で改良できる点を探っていきます。
文献
SfMについて #2:OpenSfMの中身をみる(extract_metadata)
はじめに
前回の記事mlengineer.hatenablog.comの続きで、
今回はOpenSfMの中身を少しずつ噛み砕き、解説していこうと思います。
目的は前回の記事でダンテのデスマスクを再構成して思い出をより堪能できる3次元点群の取得を行いましたが、
この3次元点群の精度をどうすれば高めることができるのか考え、
その後に処理の改善・修正やパラメータ調整を行いたいと考えているからです。
そのためには、まずOpenSfMが何をやっているのかを知る必要があります。
OpenSfM1は何をやっているのか?
サンプルコマンド bin/opensfm_run_all とはなんぞや?
OpenSfMのサンプルコードでは以下のコマンドを入力することで、対象データの3次元点群を取得することができます。
bin/opensfm_run_all data/berlin
このコマンドが何を実行してるのか中身を覗いていきます。 bin/opensfm_run_allをvimで見てみると次のようなコードとなっています。
#!/usr/bin/env bash set -e DIR=$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd ) PYTHON=${2:-python} echo "Running using Python command: $PYTHON" $PYTHON $DIR/opensfm extract_metadata $1 $PYTHON $DIR/opensfm detect_features $1 $PYTHON $DIR/opensfm match_features $1 $PYTHON $DIR/opensfm create_tracks $1 $PYTHON $DIR/opensfm reconstruct $1 $PYTHON $DIR/opensfm mesh $1 $PYTHON $DIR/opensfm undistort $1 $PYTHON $DIR/opensfm compute_depthmaps $1
これは見てわかるとおり、bashによってpythonスクリプトを順番に実行しているだけで、
ワンクッションおいて$DIR/opensfmに対して、行いたい処理と対象データを引数として渡しています。
$DIRは/OpenSfM/binのことですので、/OpenSfM/bin/opensfmというスクリプトを使っています。
$PYTHONは人によって若干違うと思いますが、自分の環境で利用しているpythonコマンドです。
/OpenSfM/bin/opensfmは中身を見れば一行目でわかりますが、pythonスクリプトです。
そして、/OpenSfM/bin/opensfmに対して渡している引数と、おおよそ実施している処理は次の通りです。
- extract_metadata(●本記事の対象)
- 対象データのメタデータを取得する処理
- detect_features
- 対象データの各画像から特徴量を取得する処理
- match_features
- 取得した特徴量を画像間でマッチングする処理
- create_tracks
- マッチング結果からカメラ位置推定を行う処理
- reconstruct
- カメラ位置推定の結果から3次元点群を生成する処理
- mesh
- 3次元点群から可視化を行うためにメッシュを生成する処理
- undistort
- カメラパラメータを利用して歪みを軽減する処理
- compute_depthmaps
- カメラパラメータから対象データの各画像の深度マップを生成する処理
これらの処理をスクリプトを覗きながら順番に軽く見ていきます。 各スクリプトは/OpenSfM/opensfm/commands/にあります。 思いの外長くなってしまったので、今回はextract_metadataの話のみにしました。
extract_metadata
extract_metadata.pyは対象データの画像から、EXIFを使うことでメタデータを取得しています。 ダンテのデスマスクに関する取得されたメタデータは、/OpenSfM/data/italy_dante/にcamera_models.jsonというファイルで保存されます。
またメタデータとはなんぞや?というと、/OpenSfM/opensfm/commands/exif.pyおよび公式ページ[^1]を見る限り、
次の情報を意味しているようです。
※公式ページとの対応がわかるように英語表記も残します
- 画像サイズ(幅、高さ) 【width and height】
- GPS情報(緯度、経度、高さ、DOP) 【gps latitude, longitude, altitude and dop】
- 撮影時刻【capture_time】
- matching_time_neighborsのオプションを付けて実行することで、撮影時刻の情報を使うようです
- 前回記事で復元したときは、このオプションを付けた覚えはありません。
- カメラ方向【camera orientation】
- 投影方法【projection_type】
- iPhone Xの場合はperspectiveでした。他にはfisheyeや360度カメラをつかった場合のequirectangularなどがあります。
- 焦点距離【focal_ratio】
- イメージセンサの大きさを利用して算出された値であり、iPhone Xの場合は約0.78のようです。
- この値はカメラパラメータを推定するときの初期値として利用するようです。
- メーカ名およびモデル【make and model】
- カメラIDを示す文字列【camera】
公式サイトをみると、EXIFによるメタ情報の取得とカメラパラメータの取得について記載がありますが、
スクリプトに書いてある順番と少し異なる(というかわかりにくい)ので、メモを残します。
スクリプトを見ていく限りは次の段階を踏んでいました。
※公式サイトの"Providing additional metadata"を読むと書いてあったりもします
[EXIFの取得]
1. exif_overrides.jsonが最も優先される
* extract_metadata.pyからdataset.pyのload_exif_overridesメソッドを見る限り
2. その次に、対象画像と同一の名前で拡張子が.exifであるファイルが存在すればこの情報が使われる
* 画像が01.jpgであれば、EXIFファイルは01.jpg.exifである必要がある
* 例えば、01.jpg.exifには上述の画像サイズ〜カメラIDの情報が含まれている
3. 最終的に上記の2つがなければ各画像に付随するEXIF情報を利用する
[カメラパラメータの取得] ここは投影方法によって処理順番が異なるので注意が必要ですが以下はperspectiveの場合で確認をしています。
- hard_coded_calibration, focal_ratio_calibration, default_calibrationのいずれかを用いる。
- 次にcamera_models_overrides.jsonが使われる
結構、設定の優先順位やファイル名が分かりにくいですね。。 ※間違いを含む可能性がありますので、適宜見直して上記は修正するつもりです
まとめ
OpenSfMの中のサンプルスクリプトの解説を試み、 まずは画像情報からEXIFを取得するextract_metadataに関して見ました。 公式サイトにも記載がありこれがわかりにくいので、スクリプトを見ながら処理を軽くまとめてみましたが、 それでもまだわかりにくくなってしまいました。 適宜見直しを行い、わかりやすくなるように更新していきたいと思います。
本記事から、ダンテのデスマスクを高精度に3次元復元するためには、
- 画像のEXIFのみではなく、自分で撮影したiPhone Xのカメラパラメータを算出して入力してあげる
- ただし、まだ未確認ですがOpenSfMの処理にカメラパラメータの推定処理が含まれる場合はこの限りではない可能性も出てきます
- 現段階では注意が必要
- 画像取得時刻をオプション指定をしてあげる
- この情報を利用することでどのような違いが生じるのか調査できてません
- これも現段階では注意が必要
次回は対象データの各画像から特徴量を取得する処理である、detect_features に関して見てみます。 対象データによっては相性のいい特徴点検出を選んでみたり、 深層学習を利用したデコーダを挟むことができるかもしれません。
文献
SfMについて #1:OpenSfMを実行する
はじめに
今回は機械学習とは少し異なる話題ですが、SfM(Structure from Motion)についての記事となります。 Google先生に聞けばたくさん記事が出てくる話題ですが、 まずはOpenSfMを利用する方法をメモしておきます。 SfMの詳細については時間ができたときに話題にしたいと思います。 最近では深層学習を利用して、単眼画像から深度(デプス)を推定する手法も多く提案されており、 車の自動運転からVR/ARに至るまで応用先が広く、魅力的な技術といえます。
SfMとは?
詳細はまたの機会にしますが、SfMとは被写体に対して視差をもたせたたくさんの画像を撮影しまくり、 各画像 の撮影した位置を推定しつつ、被写体の3次元点群を生成する手法を指します。 1つの手法名ではなく一連の処理方法をまとめたもの・概念の名前です。 カメラパラメータを利用できれば実際に撮影した物体の実寸を推定することもできたりと、活用先が多岐に渡ります。 自動運転や自律移動ロボットの分野では自己位置推定と地図構築に関わるVisual SLAMのような技術分野でも活用される技術となります。
Docker環境でOpenSfMを利用する準備
OpenSfM1はpython2系でもpython3系でも動かすことが可能なライブラリです。 私はDockerで構築したUbuntu 18.04.1でpython3系を利用しているので、 こちらのDockerfile2を参考にして既に立ち上げているコンテナに必要なモジュールを追加していきました。 独立した環境をDockerで構築したい場合は、このDockerfileをそのまま利用しdocker buildによるイメージを作成、 コンテナを作成していけばOKだと思います3。
私の既存コンテナの環境では、anacondaが入っていて、どのpythonを利用しているかというと、
which python
/opt/conda/bin/python
python -V
Python 3.7.3
となり、 /opt/conda/lib/python3.7/site-packages/にconda installを行ったモジュールたちがいます。 anacondaを利用せずに、最近はpipで十分なのでこの場合は公式サイトの手順に従えばOKだと思います。
さて、anacondaを利用している場合はDockerfile内の以下のコマンドにおける DPYBIND11_PYTHON_VERSIONオプションとDPYTHON_INSTALL_DIRオプションを変えてあげます。
# opengv RUN \ mkdir -p /source && cd /source && \ git clone https://github.com/paulinus/opengv.git && \ cd /source/opengv && \ git submodule update --init --recursive && \ mkdir -p build && cd build && \ cmake .. -DBUILD_TESTS=OFF \ -DBUILD_PYTHON=ON \ -DPYBIND11_PYTHON_VERSION=3.6 \ -DPYTHON_INSTALL_DIR=/usr/local/lib/python3.6/dist-packages/ \ && \ make install && \ cd / && rm -rf /source/opengv
まず、DPYBIND11_PYTHON_VERSION=3.7として、DPYTHON_INSTALL_DIR=/opt/conda/lib/python3.7/site-packages/と変更してあげることで、無事opengvが使えました。
OpenSfMを使う
無事、OpenSfMと依存環境がインストールできれば、公式サイトに書いてある次のコマンドを実行できます。
bin/opensfm_run_all data/berlin
このopensfm_run_allの中身をcatで覗いてみると、OpenSfM/bin/opensfmに対してオプションを渡して順番に実行してくれるだけだとわかります。 下の$1はdata/berlinを渡しています。
#!/usr/bin/env bash set -e DIR=$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd ) PYTHON=${2:-python} echo "Running using Python command: $PYTHON" $PYTHON $DIR/opensfm extract_metadata $1 $PYTHON $DIR/opensfm detect_features $1 $PYTHON $DIR/opensfm match_features $1 $PYTHON $DIR/opensfm create_tracks $1 $PYTHON $DIR/opensfm reconstruct $1 $PYTHON $DIR/opensfm mesh $1 $PYTHON $DIR/opensfm undistort $1 $PYTHON $DIR/opensfm compute_depthmaps $1
OpenSfM/bin/opensfmの中身は結局引数を渡して、OpenSfM/opensfm/commands以下にあるpythonスクリプトたちを実行しています。
SfMというと建築物の画像を題材にしたものをよく見ますので、少し異なる画像に対して適用して遊んでみます。 夏休みにイタリアを旅行し、フィレンツェにあるヴェッキオ宮殿に行き、 ここぞとばかりにダンテのデスマスクを大量に撮影してきました。 この画像に対してOpenSfMのサンプルスクリプト(bin/opensfm_run_all)を適用し、3次元点群を復元することで、 思い出をより深く楽しんでみます。
まず、私が撮影してきたダンテのデスマスクの画像は以下のようなもので、 角度を変えてiPhone Xで撮影しまくり、全19枚の画像からなります。 再構成した3次元点群と画像を重畳した結果も載せてしまいますが、結構きれいに復元できました。
蘇る、ダンテ
念の為に記載しておきますが、bin/opensfm_run_allにわたすターゲットとする自身のデータセット(複数の画像)は、 data/italy_dante/images/xx.jpgのようにimagesというフォルダにまとめておく必要があります。 一部省略しましたが、treeコマンドでみると次のような階層構造でデータが生成されます。 自分で用意したものはdata/italy_dante/imaegs/xx.jpgのみで、その他のフォルダやファイルはすべて自動で生成されます。
tree data/italy_date
data/italy_dante/
├── camera_models.json
├── depthmaps
│ ├── 01.jpg.clean.npz
│ ├── 01.jpg.pruned.npz
│ ├── 01.jpg.raw.npz
│ ├── ...
│ ├── 19.jpg.clean.npz
│ ├── 19.jpg.pruned.npz
│ ├── 19.jpg.raw.npz
│ └── merged.ply
├── exif
│ ├── 01.jpg.exif
│ ├── ...
│ └── 19.jpg.exif
├── features
│ ├── 01.jpg.features.npz
│ ├── ...
│ └── 19.jpg.features.npz
├── images
│ ├── 01.jpg
│ ├── ...
│ └── 19.jpg
├── matches
│ ├── 01.jpg_matches.pkl.gz
│ ├── ...
│ └── 19.jpg_matches.pkl.gz
├── profile.log
├── reconstruction.json
├── reconstruction.meshed.json
├── reference_lla.json
├── reports
│ ├── features
│ │ ├── 01.jpg.json
│ │ ├── ...
│ │ └── 19.jpg.json
│ ├── features.json
│ ├── matches.json
│ ├── reconstruction.json
│ └── tracks.json
├── tracks.csv
├── undistorted
│ ├── 01.jpg.jpg
│ ├── ...
│ └── 19.jpg.jpg
├── undistorted_reconstruction.json
└── undistorted_tracks.csv
あとは、次のコマンドで簡易的なhttpサーバ(ポート指定しなければポートは8000)をローカルに立ててウェブブラウザでSfMの結果ファイル(http://localhost:8000/viewer/reconstruction.html#file=/data/italy_dante/reconstruction.meshed.json)にアクセスしてあげれば、viewerによって描画することが可能です。
python -m http.server [port number]
おでこのあたりの点群が少し欠けている結果となりますが、比較的うまく再構成されています。 おでこ付近は凹凸がすくないため特徴点がうまく抽出されなかった可能性がありますね。 よくあるサンプルとして被写体が建物のように大きな物体である場合、視差を発生させるためには多くの位置から撮影する必要があり、色々な場所に人が移動して撮影するために撮影に手間がかかります。 特に上斜め上空といった位置から大きな建物を撮影することは難しいと思いますので、SfMで遊んでみると思ったよりも綺麗に点群が得られなかったりします。 一方で今回のダンテのデスマスクの場合は、被写体に対してあらゆる角度から簡単に写真撮影ができたため、 いい具合の再構成ができたのだと考えられます。
まとめ
今回はSfMを適用して、かの有名なダンテのデスマスクの3次元復元を行いました。 被写体が小さいために、あらゆる角度から視差を生じさせた画像を容易に撮影でき、 再構成結果もいい感じとなりました。 しかし、おでこ付近においては特徴点不足が原因と疑われる欠損が発生しました。 身近な画像によってかんたんに3次元復元を行うことができ、旅の思い出がより鮮明に蘇ります! 次回以降は、SfMの原理や、精度向上を目指していこうかと考えています。