CUDAによる局所特徴量計算の高速化とソースコード公開

はじめに

こんにちは、エンジニアの高木です。

私は現在、adaskitという社内の自動運転関連のオープンソースプロジェクトに携わっており、プロジェクトの成果としてこれまでlibSGMやcuda-bundle-adjustmentなどを公開しています。

今回はVisual SLAMやSfM(Structure from Motion)で行われる局所特徴量計算について、CUDAによる高速化に取り組んだ話を紹介します。また、そのソースコードをcuda-efficient-featuresという名前でGitHubに公開しました。
fixstars/cuda-efficient-features

背景

局所特徴量計算

Visual SLAMやSfMでは、2つの視点間の相対的なカメラ姿勢を推定する処理(relative pose estimation)がよく行われます。この際、2つの視点で対応する特徴点のペアを収集し、対応点の間に成り立つ幾何学的な条件(エピポーラ拘束など)を元にカメラ姿勢を推定するのが一般的です。同じ3次元上の点でも、視点の位置姿勢によって画像上での見え方は変化します。そのため、対応点を正しく求めるには、(1)マッチングに適した特徴点検出(keypoint detection)と、(2)特徴点周辺の輝度パターンを適切な表現に変換する特徴量抽出(feature extraction)※が必要です。ここでは、(1)と(2)を合わせて局所特徴量計算と呼ぶことにします。

※特徴量の事を特徴記述子(descriptor)と呼び、descriptor extractionと呼ぶこともあります。

BADとHashSIFTの登場

局所特徴量計算はこれまで様々なものが提案されています。代表的な手法であるSIFTは視点のスケール変動や回転に対してロバストに設計されており、精度面では今でもベースラインとされている印象です。計算効率の面で工夫された手法も多く存在します。AKAZEやORBに代表されるバイナリ特徴量は特徴ベクトルをビット列で記述したもので、省メモリかつ類似度計算を高速に行えるメリットがあります。

近年、SuárezらによりBAD(Box Average Difference)とHashSIFTという、2つのバイナリ特徴量が提案されました[1]。下図の赤青緑の色分けは、特徴量抽出手法のカテゴリを示しています。BADはORB同様に、特徴点周辺からサンプリングした輝度値の差をビット列にエンコードする手法です。HashSIFTはSIFTと同じく輝度勾配を利用した手法で、SIFT特徴量を計算した後、線形変換と2値化を適用してバイナリ化したものです。下図の各点は様々な局所特徴量の精度と計算コストをプロットしたもので、ピンク色の線が示す通り、BADとHashSIFTは優れたトレードオフを示しています。著者によりソースコードが公開されており、OpenCV APIを通じて利用できます。

図1：特徴量計算の精度と計算コストのトレードオフ ([1]より引用)

CUDA実装による高速化

SLAMではリアルタイム性が求められること、SfMでは大量の画像を処理することから、局所特徴量計算を出来るだけ高速化したいモチベーションが生まれました。特徴点検出は画素毎に、特徴量抽出は特徴点毎に並列に計算できるため、GPUによる高速化が期待できます。今回、上で述べたBADとHashSIFTをCUDA実装でさらに高速化しようと考えました。また、BADとHashSIFTそれ自体は特徴点検出を含んでいませんが、実用的には特徴点検出と特徴量抽出はセットで行うことが多いため、特徴点検出についてもCUDA実装することにしました。

特徴点検出の実装

実装概要

特徴点検出は、OpenCVのORBで採用されている、マルチスケールのFAST特徴点検出をベースとしています。OpenCV実装の特徴点の分布に課題を感じたため、若干の機能拡張を追加しています。

下図は特徴点の最大検出数を2万点とした場合の、OpenCV実装(左)と本プロジェクト実装(右)の比較です。

OpenCV実装では、2万点程度の特徴点が検出されていますが、そのほとんどがコーナー性(≒コントラスト)の強い、木の葉の領域に集中しています。このような特徴点の偏りがあると、カメラ姿勢の推定が不安定になる恐れがあります。特徴点の偏りを防ぐため、Non-Maximum Suppression(NMS)という、特徴点同士を一定距離より近づけない処理を行うことがあります。OpenCVにもNMSが実装されているものの、その適用範囲が極めて狭く(隣接する周囲8ピクセル)、調節もできないため、あまり機能していません。

本プロジェクトでは、指定された半径(特徴点間で許容される最小距離)で、NMSを実行できるよう機能拡張を行いました。下図右のNMS半径15のバージョンでは、建物を含め、満遍なく特徴点が検出されていることが分かります。

処理時間

特徴点検出のアルゴリズムはNMSを除いて違いはありませんが、主に以下の2つの最適化を行いました。

• デバイスバッファを使いまわし、メモリ再確保/解放を回避
• NMSのアルゴリズムの変更に伴い、FASTベースのコーナースコア計算を除去

FAST特徴点検出は元から処理時間が小さいため、相対的にデバイスメモリ確保・解放などの、CUDA APIの処理時間が無視できなくなってきます。本プロジェクトでは特徴点検出が繰り返し呼び出されることを想定し、1度確保したデバイスバッファを使いまわすことで、極力CUDA API呼び出しを回避しています。

以下は実装のベースであるOpenCVのcv::cuda::ORB::detectとの処理時間比較です。高速化の効果は、あまり想定していませんでしたが、画像サイズが大きくなるにつれて顕著になることが分かりました。

計測環境

特徴点検出の処理時間比較 (単位は[millisecond])

特徴量抽出の実装

実装概要

著者実装のBADとHashSIFTをコード整理した後、CUDA実装と高速化を行いました。BADとHashSIFTそれぞれ、最適なスレッド割り当てやWarp Shuffleによる並列リダクション、CUDA API呼び出し削減などを適用しています。HashSIFTについては、高速化の詳細を後日別記事で紹介する予定です。

処理時間

下記はリファレンスCPU実装とCUDA実装で処理時間を比較したものです。GPUでは1万点の特徴点について1[msec]程度で特徴量抽出を実行できています。CPUのマルチスレッドと比較しても、BADでは9~10倍程度、HashSIFTでは200～300倍程度高速化することが出来ました。

計測環境

特徴量抽出の処理時間比較 (単位は[millisecond])

おわりに

局所特徴量計算の高速化についてご紹介させていただきました。冒頭で紹介した通り、今回のソースコードはcuda-efficient-featuresという名前でGitHubに公開しました。SfMやSLAMを高速化したい方は、是非使ってみて下さい。
fixstars/cuda-efficient-features

今後は本プロジェクトの成果を活用しつつ、SfM全体を高速化することも考えています。

最後に、高速化にご協力いただいた、アルバイトの藤本悠太さん、堀井大輔さんの多大な貢献に感謝いたします。

参考文献

[1] Iago Suárez, José M. Buenaposada, and Luis Baumela. Revisiting binary local image description for resource limited devices. IEEE Robotics and Automation Letters, 6(4):8317–8324, 2021.

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。