特徴点マッチングの基礎 - SIFT、ORB、AKAZE の原理と実装比較
特徴点マッチングとは - 画像間の対応関係を見つける技術
特徴点マッチング (Feature Matching) は、2 枚以上の画像間で同一の物理的な点に対応するピクセル位置を特定する技術です。パノラマ合成、3D 復元、物体認識、画像位置合わせ (レジストレーション)、AR/VR のトラッキングなど、コンピュータビジョンの幅広い応用の基盤となっています。
処理の 3 ステップ:
- 検出 (Detection): 画像中の特徴的な点 (コーナー、ブロブ) を見つける
- 記述 (Description): 各特徴点の周辺情報をベクトル (記述子) として数値化する
- マッチング (Matching): 2 枚の画像の記述子を比較し、類似度の高いペアを対応点とする
良い特徴点の条件: 再現性 (同じ点が異なる画像でも検出される)、識別性 (他の点と区別できる)、不変性 (回転・スケール・照明変化に対して安定) が求められます。平坦な領域やエッジ上の点は識別性が低く、コーナーやブロブ (局所的な明暗の塊) が良い特徴点になります。
歴史的発展: Harris コーナー検出 (1988) → SIFT (1999/2004) → SURF (2006) → ORB (2011) → AKAZE (2013) と発展してきました。SIFT は長年特許で保護されていましたが、2020 年に特許が失効し、OpenCV で自由に使用可能になりました。現在は用途に応じて SIFT、ORB、AKAZE を使い分けるのが一般的です。
SIFT - スケール不変特徴変換の原理と実装
SIFT (Scale-Invariant Feature Transform) は David Lowe が 2004 年に発表した特徴量で、スケール変化と回転に対して不変な記述子を生成します。精度の高さから特徴点マッチングのゴールドスタンダードとされ、20 年以上経った現在でも多くの場面で最高精度を達成します。
スケール空間の構築: 画像を異なるスケール (σ) のガウシアンでぼかし、隣接スケール間の差分 (DoG: Difference of Gaussians) を計算します。DoG はラプラシアン (LoG) の近似で、ブロブ検出に最適です。通常 4 オクターブ × 5 スケールの計 20 枚の DoG 画像を生成します。
キーポイント検出: DoG 画像の各ピクセルを 3x3x3 の 26 近傍と比較し、極値 (局所最大/最小) をキーポイント候補とします。サブピクセル精度の位置補正、低コントラスト点の除去、エッジ上の点の除去を経て、安定なキーポイントのみを残します。
方向の割り当て: キーポイント周辺の勾配方向ヒストグラム (36 ビン) から主方向を決定します。これにより回転不変性が実現されます。
記述子の生成: キーポイント周辺 16x16 領域を 4x4 のサブ領域に分割し、各サブ領域で 8 方向の勾配ヒストグラムを計算します。4x4x8 = 128 次元の記述子ベクトルが得られます。
OpenCV での実装:
sift = cv2.SIFT_create(nfeatures=500)
kp, des = sift.detectAndCompute(gray, None)
性能: 1,920 × 1,080画像で約 300-500ms (CPU)。検出点数は通常 1000-5000 点。精度は最高だが速度は遅い。
ORB - 高速かつ無料の特徴量
ORB (Oriented FAST and Rotated BRIEF) は 2011 年に OpenCV の開発者らが発表した特徴量で、SIFT の代替として設計されました。バイナリ記述子を使用するため計算が高速で、リアルタイムアプリケーションに適しています。
キーポイント検出 (Oriented FAST): FAST (Features from Accelerated Segment Test) コーナー検出器をベースに、Harris コーナー応答でフィルタリングし、画像ピラミッドでマルチスケール検出を実現します。各キーポイントに Intensity Centroid 法で方向を割り当て、回転不変性を確保します。
記述子 (Rotated BRIEF): BRIEF (Binary Robust Independent Elementary Features) はキーポイント周辺のピクセルペアの大小比較で 256 ビットのバイナリ記述子を生成します。ORB ではキーポイントの方向に応じてペアの位置を回転させ (rBRIEF)、回転不変性を実現しています。
バイナリ記述子の利点:
- 記述子間の距離計算がハミング距離 (XOR + popcount) で超高速
- メモリ使用量が SIFT の 1/16 (256 ビット = 32 バイト vs SIFT の 128×4 = 512 バイト)
- SIMD 命令で並列計算が容易
OpenCV での実装:
orb = cv2.ORB_create(nfeatures=1000)
kp, des = orb.detectAndCompute(gray, None)
性能: 1,920 × 1,080画像で約 15-30ms (CPU)。SIFT の 10-20 倍高速。ただし、大きなスケール変化 (2 倍以上) や大きな視点変化に対する頑健性は SIFT に劣ります。モバイルデバイスやリアルタイム AR で広く使用されています。
パラメータ調整: nfeatures (検出点数上限)、scaleFactor (ピラミッドのスケール比、デフォルト 1.2)、nlevels (ピラミッド段数、デフォルト 8) が主要パラメータです。
AKAZE - 非線形スケール空間による高精度特徴量
AKAZE (Accelerated-KAZE) は 2013 年に発表された特徴量で、非線形拡散フィルタリングによるスケール空間を使用します。ガウシアンぼかし (線形拡散) ではエッジがぼけてしまう問題を解決し、エッジを保持したままスケール空間を構築するため、テクスチャの少ない画像でも高精度なマッチングが可能です。
非線形スケール空間: AKAZE は Perona-Malik 拡散方程式に基づく非線形フィルタリングを使用します。エッジ付近では拡散を抑制し、平坦な領域では拡散を促進するため、エッジ構造を保持したスケール空間が得られます。FED (Fast Explicit Diffusion) ソルバーにより高速に計算されます。
キーポイント検出: 非線形スケール空間上で Hessian 行列の行列式の極値を検出します。ガウシアンスケール空間よりもエッジ付近のキーポイントが安定し、テクスチャの少ない人工物 (建物、看板) での検出性能が向上します。
記述子: AKAZE はバイナリ記述子 (M-LDB: Modified Local Difference Binary) を使用します。486 ビットのバイナリベクトルで、ORB の BRIEF より識別性が高く、SIFT より高速です。浮動小数点記述子 (KAZE 互換) も選択可能です。
OpenCV での実装:
akaze = cv2.AKAZE_create()
kp, des = akaze.detectAndCompute(gray, None)
性能比較: 1,920 × 1,080画像で約 80-150ms (CPU)。SIFT より高速、ORB より低速ですが、精度は SIFT に匹敵し、特にテクスチャの少ない画像で SIFT を上回ることがあります。
使い分けの指針: 建築物、室内環境、工業製品など人工的な構造物の画像では AKAZE が最適です。自然風景や高テクスチャ画像では SIFT が依然として最高精度を示します。
マッチング手法 - BFMatcher と FLANN
特徴点の記述子が得られたら、2 枚の画像間で対応する記述子ペアを見つけるマッチング処理を行います。マッチングの品質がアプリケーション全体の精度を左右します。
Brute-Force Matcher (BFMatcher): 全ての記述子ペアの距離を計算し、最も距離が近いペアをマッチとする総当たり方式です。確実に最近傍を見つけますが、記述子数 N に対して O(N²) の計算量です。
bf = cv2.BFMatcher(cv2.NORM_L2, crossCheck=True) # SIFT 用
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True) # ORB/AKAZE 用
FLANN (Fast Library for Approximate Nearest Neighbors): KD-Tree や LSH (Locality Sensitive Hashing) を使用した近似最近傍探索です。大量の特徴点 (1000 点以上) では BFMatcher より大幅に高速ですが、近似のため最適なマッチを見逃す可能性があります。
Lowe's Ratio Test: 最も重要なフィルタリング手法です。各特徴点に対して最近傍と 2 番目の最近傍の距離比 (d1/d2) を計算し、比が閾値 (通常 0.7-0.8) 以下のマッチのみを採用します。曖昧なマッチ (複数の候補が似た距離にある) を除去し、誤マッチ率を大幅に削減します。
matches = bf.knnMatch(des1, des2, k=2)
good = [m for m, n in matches if m.distance < 0.75 * n.distance]
Cross-Check: 画像 A→B のマッチと B→A のマッチの両方で対応する場合のみ採用する双方向検証です。Ratio Test と組み合わせることで、誤マッチ率を 5% 以下に抑えられます。
性能目安: 1000 点同士の BFMatcher (L2) で約 10ms、FLANN で約 3ms。5000 点同士では BFMatcher が約 250ms に対し FLANN は約 15ms と差が顕著になります。
外れ値除去と幾何学的検証 - RANSAC によるロバスト推定
Ratio Test を通過したマッチにも誤対応 (外れ値) が含まれます。幾何学的な整合性を検証し、外れ値を除去する RANSAC (Random Sample Consensus) が最終的な精度を決定します。
ホモグラフィ推定と RANSAC: 2 枚の画像間の射影変換 (ホモグラフィ) を推定し、その変換に整合するマッチ (インライア) のみを採用します。ホモグラフィは 4 組の対応点から計算でき、RANSAC は以下の手順を繰り返します。
- ランダムに 4 組のマッチを選択
- 4 組からホモグラフィ行列 H を計算
- 全マッチに H を適用し、再投影誤差が閾値以下のマッチ数 (インライア数) を計数
- 最もインライア数が多い H を最終結果とする
H, mask = cv2.findHomography(pts1, pts2, cv2.RANSAC, 5.0)
閾値 5.0 は再投影誤差のピクセル数で、小さいほど厳密ですがインライア数が減少します。通常 3.0-5.0 が適切です。
RANSAC の反復回数: インライア率 p、必要サンプル数 s=4 のとき、成功確率 P=0.99 を達成するための反復回数は k = log(1-P) / log(1-p^s) です。インライア率 50% で約 72 回、30% で約 588 回必要です。OpenCV のデフォルトは 2000 回で、ほとんどの場合十分です。
USAC (Universal RANSAC): OpenCV 4.5 以降で利用可能な改良版 RANSAC です。DEGENSAC、MAGSAC、LO-RANSAC などの改良を統合し、従来の RANSAC より高精度かつ高速です。cv2.USAC_MAGSAC を指定すると、閾値の自動調整が行われます。
マッチング品質の評価: 最終的なインライア数が 10 未満の場合、マッチングは失敗と判断すべきです。安定したホモグラフィ推定には最低 20-30 のインライアが必要です。インライア率 (インライア数/全マッチ数) が 30% 以下の場合は、特徴量の選択やパラメータの見直しを検討します。