概要
AprilTagはAR、ロボット、カメラのキャリブレーションなどの様々なタスクで使われています。こんなやつ。
カメラに対するタグの3D位置、方向、タグに振り分けられている一意なIDなどを取得できます。
結構使う機会が多いのですが、ちゃんと内部のアルゴリズムを理解しようと思い、AprilTagの論文を読んでみました。ただ、OSSで日々コードやアルゴリズムが進化しているので、最新のものは反映していません。
検出アルゴリズム
入力画像から、最終的な検出結果が出力されるまでの流れをまとめていきたいと思います。もっと詳細を知りたい方は、参考資料に載せている論文を読んでください。
1. Decimation
画像サイズを下げて、処理全体の速度を上げています。若干精度は下がるので、精度を突き詰めたい場合は、この処理に関する引数を変更する必要があります。
下画像は入力画像の例で、
下画像がDecimation後の画像です。少し粗くなっているのがわかります。
2. Threshold
2値化を行っています。4×4の領域でAdaptive Thresholdingを使っているそうです。タグの模様がはっきり映っていますね。
3. Union find
連続した塊かどうかを区別しています。横または縦に同じ画素値のピクセルがあれば、連続している塊と判断していきます。
4. Contours
手順3で塊は検出できているので、黒と白の境界を引いていきます。
5. Fitting Quadrilaterals
輪郭が検出されているので、輪郭ごとに四角形を当てはめていきます。正確には、4つの線を輪郭内で当てはめていき、四角形を作成できるかを判別しています。
6. Tag Decoding
この状態では、色々な四角形があるので、検出された四角形内のピクセル情報を元に、その四角形がAprilTagなのか、AprilTagの場合はID番号は何なのかを判断していきます。
まずは、元のタグ(正方形)と、画像に映っている四角形とのホモグラフィ行列を計算します。映っているタグが綺麗に正方形で映っているとは限らないからです。
\begin{bmatrix}\omega_i x_i^1 \\
\omega_i y_i^1 \\
\omega_i \end{bmatrix}=H\begin{bmatrix}x_i^0 \\
y_i^0 \\
1 \end{bmatrix}
タグはいつも同じ方向で映っているとは限らないので、90度ずつ回転させた4種類の模様と、検出した四角形のピクセルごとでXORをとります。そのハミング距離が閾値より小さく、最小のものをAprilTagとして出力します。
7. Edge refinement
2値化された画像には、影などの影響でノイズがのっていることがあります。これはコーナーの検出精度に影響してしまいます。そこで、最初にコーナーとして検出されたポイントの周辺をサンプリングし、勾配が最も大きいポイントを新しいタグのコーナーとして出力します。黒から白、またはその逆の場合のピクセル間の勾配が最も大きいはずだからです。
ただ、タグのIDだけ使いたいなどのコーナーの検出精度が重要ではない場合は、この処理はいらないので、引数などで調整すれば処理速度を上げられると思います。
まとめ
AprilTagには様々な工夫が組み込まれていて、参考になりました。あと、ドローン用にこんなタグもあって面白かったです。これだと着陸する際にもタグ(中央の小さいタグ)がちゃんと見えるそうです。
