ぷろぐ((>ω<))

ぷろぐらみんぐ関係のメモ

cv::cornerSubPix (サブピクセル推定) アルゴリズムの詳細

OpenCVにはcv::cornerSubPixという関数があるが、これの原理に関する説明が非常に簡素でわかりづらい。

特徴検出 — opencv 2.2 documentation


上記ページに書いてある3つの式の意味についてまとめる。

  1. \displaystyle{\epsilon_{i}=DI^{T}_{p_{i}}\cdot(q-p_{i})}
  2. \displaystyle{\sum_{i} (DI_{p_{i}}\cdot DI^{T}_{p_{i}})-\sum_{i} (DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i})}
  3. \displaystyle{q=G^{-1}\cdot b}

式1について

上記OpenCVの説明ページで「各点pに向かう画像勾配と直交する」にあたる部分。これについては下記記事がわかりやすかった。

Fundamentals of Features and Corners: Subpixel Corners: Increasing accuracy - AI Shack

式2について

式1から式2の間がちょっとぶっ飛びすぎているし、いろいろと間違っていると思う。

  • \epsilon_{i}を0とすることで」(英語版では"A system of equations may be set up with \epsilon_{i} set to zero")は違うと思う
  • 突然qが式2から消えてなくなっているが間違いだと思う

式1~式2の間には次の論理が省略されていると思う。一言で言えば「二乗誤差の最小化」である。

詳細

探索窓内のすべての点について式1で定義される\epsilon_{i}の二乗の総和をEとする。

\displaystyle{
E=\sum_{i} \epsilon_{i}^{2}
}

これに式1を代入すると、

\displaystyle{
E=\sum_{i} \left(DI^{T}_{p_{i}}\cdot(q-p_{i})\right)^{2}
}

この総和Eが最小値をとるようなqを求めればよい。それはつまり、qについての微分dE/dqがゼロになるときである。よって、

\displaystyle{
\frac{dE}{dq}=2\sum_{i} \left(DI^{T}_{p_{i}}\cdot(q-p_{i})\right)DI^{T}_{p_{i}}=0
}

(a\cdot b)a=(aa^T)bと書き換えられるので、

\displaystyle{
\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot(q-p_{i})=0
}

これを展開すると

\displaystyle{
\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot q - \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i}=0
} (★)

この左辺が式2である。繰り返しになるが、qが書かれてしかるべきだと思う。

式3について

突然1次勾配G、2次勾配bという言葉が出てくるが、次の論理が省略されている。

詳細

上述の式(★)より

\displaystyle{
\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot q = \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i}
}

q\displaystyle{\sum_{i}}には依存しないので、

\displaystyle{
\left(\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\right) \cdot q = \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i}
}

ここで、

\displaystyle{
G=\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}
}
\displaystyle{
b=\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i}
}

と置くと、上述の式は次のように書き換えらえる。

\displaystyle{
G\cdot q=b
}

ゆえに、今求めたいq

\displaystyle{
q=G^{-1}\cdot b
}

となり、式3となる。

おまけ

ところで、G=\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}は計算すると近似的に次のようになるが、これを structure tensor matrix と呼ぶ。

DI_{p_{i}}=(I_{x_{p_{i}}}, I_{y_{p_{i}}})^{T}とすると、

\displaystyle{
G=\sum_{i} \begin{pmatrix}
I_{x_{p_{i}}}I_{x_{p_{i}}} & I_{x_{p_{i}}}I_{y_{p_{i}}} \\
I_{x_{p_{i}}}I_{y_{p_{i}}} & I_{y_{p_{i}}}I_{y_{p_{i}}} \\
\end{pmatrix} \approx 
\sum_{i} \begin{pmatrix}
I_{xx_{p_{i}}} & I_{x_{p_{i}}}I_{y_{p_{i}}} \\
I_{x_{p_{i}}}I_{y_{p_{i}}} & I_{yy_{p_{i}}} \\
\end{pmatrix} 
}

C, V, H キーが打てない問題の解消法 (When C, V, H keys don't work...)

TL;DR (English)

  • It might depend on each environment, but in my case, "Right Windows" key is regarded as pressed down.
    • Of course my keyboard doesn't have such a key... So I can't press it.
  • To solve this problem, simulate "R Win" key (VK_RWIN) with some tool.
    • You can create it by yourself using Win32API keybd_event()
  • My guess is that this problem might occur due to the malfunction of keyboards.

TL;DR (Japanese)

  • この問題の発生原因は人それぞれかもしれないが、私の場合は「右Windowsキー」が押しっぱなし状態と判定されていることが原因だった。
    • ちなみに使っているキーボードには「左Windowsキー」しかなく、当然「右Windowsキー」を押した覚えはない。
      • たぶん今時「右Windowsキー」のついたキーボードの方が珍しいはず
    • なおWindowsに標準でインストールされているソフトウェアキーボードも「左Windowsキー」しかないので、解消できない。
  • キーボード入力をシミュレートするツールで「右Windowsキー」を話したことにして対処。
  • (恐らくだが)原因はキーボードの誤動作。無線キーボードを使っているのだが、伝送する信号を間違えたのかな…あくまで想像。

詳細

結構長い間、下記の問題に悩んでいた:

  • テキスト入力欄にC, V, Hキーが打てない
  • C, V, H, Aキーを押すと変な動作をする
  • etc

ネットで調べても同様の症状の人は世界中でいるようである。
検索欄に「c v h」と入力したら他の人も検索しているみたい。

f:id:presan:20190622222311p:plain
c v h suggestion

実際いくつかの質問サイトでQ&Aがあるが、人それぞれ原因は違うようでいろんな対策が載っている。

ちなみに私は検索して出てくるやつでは一向に改善しなかった。
これまでは、しばらく我慢してたらどういうわけか直ったりしていた。
(いつか直るまでどうにも我慢できないときは、一度ログオフしたり再起動したりしていた)

ちょっと真面目に原因を探ろうと思い、何か特殊キーが押された状態になっているのではないかと仮説を立ててキー入力状態を見てみたら、当たりだった。

Direct Sparse Odometry (DSO) の要点まとめ

過去のエントリではWindowsへのインストール方法をまとめたが、今回は論文から理解したことをまとめる。
数学的な細かな話は最小限に抑え、私なりに要点だけまとめる。
# 間違ってるところがあるかもしれないので随時修正していくつもり。

従来手法

従来のSFM/SLAMはざっくり次の3ステップ:

  1. 複数画像から対応する特徴点を抽出
  2. 各対応特徴点に対して三角測量を行い3D再構成
  3. 3D再構成した点やカメラ位置姿勢に対してバンドル調整 (Bundle Adjustment : BA)
    • 3D点の画像上への再投影点と元の2D特徴点のx,yのズレ(再投影誤差)という空間的誤差 (geometric error) が最小化されるように、カメラ位置姿勢や3D点座標の微小修正を繰り返す

DSOの手法

これに対して、DSOは入力画像群に対して最初から直接バンドル調整(BA)を実施しているイメージ。特徴点は求めない。ざっくり次の3ステップ:

  1. 一方の画像の(勾配がある程度大きい)とある座標の画素値(A)はもう一方の画像のとある座標の画素値(B)に対応するはずという計算式を立てる
  2. その計算式から、画素値(A)と(B)の差の計算式を立てる
  3. その画素値誤差 (photometric error) が最小化されるようにカメラ位置姿勢や3D点(*1)の微小修正を繰り返す

ちなみに、処理対象とする画像:キーフレーム(KF)や3D点群を随時不要になったら削除するなど上手に管理するところにもテクニックがありそうだ。

※画像/画質処理屋さんのセンスのままで考えると理解できないかも。DSOは数学の塊で成立しているイメージ。
前回エントリを例にとると、私のイメージでは(あくまで個人の感想):

  • マッチング方式 … 画像処理屋さん的センス
  • オプティカルフロー方式 … 数学屋さん的センス

前提条件

Webカメラスマホカメラのような「人の目に美しく映るような画像」ではなく、「マシンビジョンにとって最適な画像(やカメラ)」であること。具体的には:

  • グローバルシャッター
    • 論文では一言、ローリングシャッターの影響をいくらか緩和する手法もあるようなことも書かれてはいるが…
  • キャリブレーションその1 (geometric calibration) (※言わゆる内部パラメタ)
  • キャリブレーションその2 (photometric calibration)
    • 露光時間
    • レンズ減衰・口径食
    • 放射照度の逆関数

DSOの嬉しいところ

  • 従来の特徴点方式SFM/SLAMは所謂「コーナー」を3D化するに留まるが、DSOは処理方式の違いから「エッジ」も再構成しやすい
  • つまり従来方式より多くの3D点を生成しやすい


今後より技術的に詳しく見ていこうと思う。

画像間の特徴点対応付け~マッチング方式とオプティカルフロー方式~

最終出力として2画像間の特徴点の対応関係を求めたいという場合、その方式には大きく2種類がある。
この観点からまとめられている記事をあまり見た事がないので投稿。

マッチング方式

「特徴点 対応付け」や「特徴点 マッチング」と検索すると引っかかるのは大体この方式のこと。
特徴点は英語では feature (point) と言ったり keypoint と言ったりする。
ブロック図にすると下記のようになる:

マッチング方式のブロック図
BlockDiagram

つまり、処理手順としては

  1. 双方の画像で「特徴点」を見つける
  2. 双方の画像で見つけた特徴点について「特徴量(特徴記述子と言ったりもする)」を求める
  3. 双方の特徴量を比較して一番近しい(似ている)ペアを見つける

という流れ。

特徴点抽出手法や特徴量記述手法にはいろんなものが提案されている。

  • 2つセットで提案されているものとして、例えばSIFT, SURF, ORB, KAZE, AKAZE, etc...
  • 特徴点抽出(検出)手法単体として提案されているものとして、例えばHarrisコーナー, Shi-Tomasiコーナー(=GFTT), FAST, etc...
  • 大抵の特徴点抽出手法や特徴量記述手法はグレースケール画像に対して実施するが、RGB画像をそのまま使用するものもあるようだ。例えば、SIFTに色情報を追加する論文がいくつか見つかる。

処理が理解しやすいように、ブロック図にイメージ図も付け足すとこんな感じ:

マッチング方式のイメージ図
BlockDiagram

ちなみに近しい特徴量が複数ある場合はマッチングに失敗することもある。例えばこんな感じ:

マッチング失敗の例
マッチング失敗の例

このような誤マッチングの回避策として、例えばOpenMVGでは下記のようなチェックがなされている:

誤マッチング回避方法のコンセプト
誤マッチングの回避策

つまり特徴が突出しているわけではなければ、マッチング不成立としよう、という考え方。
他にも、双方向にマッチングしてみて、結果が1対1対応しなければ、棄却する、などという手法もある。
ただ、どんどん計算量が増えていってしまうところが悩みどころ。

オプティカルフロー方式(疎)

ここではLucas-kanade法を扱うこととする。
また、説明の簡単化のためにPyramidの件は省略する。
ブロック図にすると下記のようになる:

疎なオプティカルフロー方式のブロック図
疎なオプティカルフロー方式のブロック図

つまり、処理手順としては

  1. 片方の画像で「特徴点」を見つける
  2. 片方の画像について微分画像」を求める
  3. 片方の画像の特徴点と微分画像ともう片方の画像から、特徴点の移動先を推定する(追跡する)

という流れ。

特徴点を追跡するので英語ではtrackingと言ったりする。matchingしているわけではない。
どうして「こんな処理でもう一方の画像上で対応点が見つかるのか?」という疑問に対する雑な回答としては、
「数学的に計算するとこれでできる」となる。下記でわかりやすく解説されている:
OpenCVでとらえる画像の躍動、Optical Flow - Qiita
オプティカルフロー推定の原理・特徴・計算式 | アルゴリズム雑記


処理が理解しやすいように、ブロック図にイメージ図も付け足すとこんな感じ:

疎なオプティカルフロー方式のイメージ図
疎なオプティカルフロー方式のイメージ図

オプティカルフロー方式でも誤った点対応(誤トラッキング)が発生する可能性がある。
具体的には「同じような模様の繰り返し」である。

Direct Sparse Odometry (DSO) を Win10, VS2017 でビルド

環境

スタート地点

本家Gitは下記だがLinux/Mac前提。
GitHub - JakobEngel/dso: Direct Sparse Odometry
これをWindows向けに移植したforkがあったので、これを使う。
GitHub - AndreV2890/dso: Direct Sparse Odometry

しかし手元の環境ではすんなりビルドができなかった。
どうも、上記Win版DSOは下記の環境でのビルドを想定しているようである。

thirdpartyの準備

まず、thirdpartyはx86を前提として準備されている。自分で全部やりなおすのが面倒だったので、同じくx86で行くことにする。

READMEによると、cmakeしたときに依存ライブラリのパスをそれぞれ設定すればOKと書いてあるが、一部はそのままではうまくいかなかった。

  • READMEの通りやれば、うまくいったもの
    • Eigen
    • SuiteSparse
    • CHOLMOD
    • OpenCV

以下ではうまくいかなかったものについて記す

Boost, Pangolin, OpenCVへのlink (CMakeLists.txt)

cmakeのfind_packageではうまく見つからないので、

set (Boost_FOUND ON)
set (Pangolin_FOUND ON)
set (OpenCV_FOUND ON)

ということにして、includeやlibのパスをinclude_directories,() link_directories()で手動設定。

ちなみにこの3つがないと、dsoのコアライブラリまではビルドできるが、それを使ったアプリ(dso_dataset)がビルドされない。

更にちなみに、BoostはVisualStudio 2015 (vc14, v140)でビルドされているが、v140からそれ以降と互換性があるらしく今回VisualtStudio2017 (vc15, v141)だが再ビルド不要らしい。
VisualStudio2017でDSOをビルドするなら、v141のライブラリじゃないとダメだった。そのため、Boost1.66を別途x86でビルドしてリンク。

Pangolinのビルド

Releaseモード

普通にビルド。ただし、私はOpenNI2を入れていた関係でそれ関係のビルドもONになってしまい、それがリンクエラーを誘発してしばらく詰まっていた。今回OpenNI2は使わないので、CMakeの段階でOFFにする(自動的に設定されたパスを削除してConfigureする)ことで対処。

Debugモード(DSOをDebugモードで動かしたい場合は必須)

DSO.slnとライブラリの種類を合わせないと、最後のDSOビルドでpangolin.lib関連で大量のリンクエラーが発生する。

/MDとか/MTとかmsvcrt.libとかlibc.libとかlibcmt.libとか - snipsnipsnip

Pangolinプロジェクトを右クリックして[構成プロパティ]→[C/C++]→[コード生成]→[ランタイムライブラリ]を /MTd から /MDd に変更。

OpenCVのDebugモードビルド(DSOをDebugモードで動かしたい場合は必須)

thirdparty/opencvにはRelease版しか入っていない。OpenCVはDebug時はDebug用、Release時はRelease用をちゃんとリンクしないとエラーになるので、x86のDebugを自分で別途ビルド。
(配布されているPrebuiltなOpenCVはx64でしかビルドされていないので自分でビルドするしかない)

libzipのビルド

TUMのデータセットは入力画像をzipで固めているのだが、そのzipのまま画像を読み取れるようにするためにはlibzipが必要。そしてlibzipのビルドにはzlibが必要。

ということで何も考えずにWindowsでビルドできるよう環境がそろった下記を持ってきた。

GitHub - kiyolee/zlib-win-build: zlib Windows build with Visual Studio.
GitHub - kiyolee/libzip-win-build: libzip Windows build with Visual Studio.

> cd {somewhere}\
> git clone https://github.com/kiyolee/zlib-win-build.git
> git clone https://github.com/kiyolee/libzip-win-build.git

上記gitのREADMEにも書いてあるが、zlib→libzipの順序でビルドする必要がある。その際、libzipのVSソリューション内のzlibへのincludeやlibのパスは自分の環境に合わせなおす必要があることに注意。

後から気づいたが、Pangolinをビルドするとthirdparty/Pangolin/build/external/にzlibがビルドされているので、これを使ってthirdparty/libzip-1.1.1.tar.gzを解凍&ビルドすればよかったかも。

DSOビルド

ようやくメインのビルド。これもそのままではビルドできない。

zipオフライン映像を入力するよう改造1

Win版forkではWebカメラで動かすように改造されているようなので、本家のmain_dso_pangolin.cppから該当箇所を逆移植。

実際の改造コードの掲載はここでは省略する。やることは次の通り:

  • main関数内のcv::VideoCapture関係の記述を削除
  • main関数冒頭でparseArgumentするようにし、sourceなどのハードコード指定を削除
  • 画像読み込みのwhile文を削除し、本家からfor文を移植

zipオフライン映像を入力するよう改造2

src\util\DatasetReader.hの中のgetdir関数がPOSIX仕様なので、下記を参考に書き換え。
ディレクトリ内のファイルリストを得る

#ifdef _MSC_VER
#include <io.h>
#else
#include <dirent.h>
#endif

inline int getdir(std::string dir, std::vector<std::string> &files)
{
#ifdef _MSC_VER
	struct _finddata_t fdata;
	intptr_t fh = _findfirst(dir.c_str(), &fdata);
	if (-1 == fh)
	{
		return -1;
	}

	do {
		std::string name = std::string(fdata.name);
		if (name != "." && name != "..")
			files.push_back(name);
	} while (0 == _findnext(fh, &fdata));

	_findclose(fh);
#else
    // (省略)
#endif
    std::sort(files.begin(), files.end());

    if(dir.at( dir.length() - 1 ) != '/') dir = dir+"/";
	for(unsigned int i=0;i<files.size();i++)
	{
		if(files[i].at(0) != '/')
			files[i] = dir + files[i];
	}

    return files.size();
}

usleep削除

main_dso_pangolin.cpp内にusleep()が使われているがWindowsでは使えない。
WinAPIのQueryPerformanceCounter()に代替するのが正しいのだろうが、面倒なのでひとまず単純にコメントアウト。問題が生じたら後で上の修正をすることとする…

リンクするライブラリを追加

リンクするライブラリはmain_dso_pangolin.cppの冒頭で #pragma comment で指定されている。下記のように編集。

//#include <GL/freeglut.h>

#pragma comment(lib, "glew.lib")
#pragma comment(lib, "libpng16.lib")
#pragma comment(lib, "jpeg.lib")
#pragma comment(lib, "libzip.lib")
#pragma comment(lib, "glu32.lib")
#pragma comment(lib, "opengl32.lib")

// Boost
#ifdef _DEBUG
#pragma comment(lib, "libboost_thread-vc141-mt-gd-x32-1_66.lib")
#pragma comment(lib, "libboost_system-vc141-mt-gd-x32-1_66.lib")
#pragma comment(lib, "libboost_date_time-vc141-mt-gd-x32-1_66.lib")
#pragma comment(lib, "libboost_chrono-vc141-mt-gd-x32-1_66.lib")
#else
#pragma comment(lib, "libboost_thread-vc141-mt-s-x32-1_66.lib")
#pragma comment(lib, "libboost_system-vc141-mt-s-x32-1_66.lib")
#pragma comment(lib, "libboost_date_time-vc141-mt-s-x32-1_66.lib")
#pragma comment(lib, "libboost_chrono-vc141-mt-s-x32-1_66.lib")
#endif

// OpenCV
#ifdef _DEBUG
#pragma comment(lib,"opencv_core341d.lib")
#pragma comment(lib,"opencv_highgui341d.lib")
#pragma comment(lib,"opencv_imgproc341d.lib")
#pragma comment(lib,"opencv_imgcodecs341d.lib")
#pragma comment(lib,"opencv_videoio341d.lib")
#else
#pragma comment(lib,"opencv_core341.lib")
#pragma comment(lib,"opencv_highgui341.lib")
#pragma comment(lib,"opencv_imgproc341.lib")
#pragma comment(lib,"opencv_imgcodecs341.lib")
#pragma comment(lib,"opencv_videoio341.lib")
#endif

thirdparty/Pangolin/glewがあったので、要らんやろと思いfreeglutのincludeも消したが、thirdparty/freeglutがあったことに後から気づいた。

いざビルド&実行

ビルドできた。
その後、libpng16.dll, libzip.dll, opencv_*.dllが見つかるようにパスを通すと実行できた。

f:id:presan:20190428213238p:plain
Direct Sparse Odometry on Windows10

Android Studio でデバッグ実行してもブレークポイントで止まらない場合の対処

タイトルの件でちょっとハマったのでメモ。
Android Studioデバッグ実行してもブレークポイントで止まらない場合、考えられる理由は私の知っている範囲では次の3つ。まだまだ事例は他にもあるかもしれないですが。
私がハマったのは3番目の奴です。

1. AsyncTask等で別スレッドで動いている場合

そのスレッドでデバッグできるようにするために追加すべきコードがあります。
「AsyncTask ブレークポイント」等で検索すればたくさん出てきます。

www.ecoop.net

2. Gradle の設定で debuggable が false になっている

android studio ブレークポイント 止まらない」で検索すると下記サイトがヒットします。
d.hatena.ne.jp

3. Gradle の設定で minifyEnabledが true になっている

私はこれでした。debuggableが true でも minifyEnabled が false じゃないとブレークポイントでは止まらないのですね…

以上!

OpenCVを使いたいときのcmakeの書き方

次のように書けばよい。かなりシンプル。link_directoriesの指定は不要。
なぜならば、${OpenCV_LIBS}でライブラリへの絶対パスが指定されるため

OpenCVが見つかった場合のみプロジェクトを作成したければif(DEFINED ${OpenCV_VERSION})でadd_executableやtarget_link_librariesを囲めばよい

cmake_minimum_required(VERSION 2.8 FATAL_ERROR)

project(opencv_project)

find_package(OpenCV 2.4 REQUIRED)

include_directories(${OpenCV_INCLUDE_DIRS})

add_executable (project1 hoge.cpp)
target_link_libraries (project1 ${OpenCV_LIBS})