Kaggle Image Matching Challenge 2022 まとめ

Last updated at 2024-03-19Posted at 2022-06-04

今回 Image Matching Challenge 2022 | Kaggle に参加しました
- 約1ヶ月ほど参加しました
- 一緒に参加してくださったチームメンバーに圧倒的感謝
- 結果は 41 / 653 teams で Silver でした（ぐやじいでず）
悔しいですが学んだことも色々あったので記事に残します
- あとやってない人からするとこのコンペが何をしてるのか分かりづらい

1. About Competition

Image Matching Challenge 2022 | Kaggle

1.1 Task

個人的にはタスクの理解が一番大変でした。
以下 カメラ幾何 とか エピポーラ幾何 の説明が多いので、既知の方は飛ばしてください。

1.1.1 Target Value(input & output)

このコンペティションでは以下の入出力が求められていました。

入力: 2枚のペア画像（同じシーン ≒ 建物を撮影したもの）
出力: Fundamental Matrix（基礎行列）（$F$ とする）
- $3 \times 3$ の行列
- ランク 2、自由度 7
- 以下の情報を含む行列¹
  - カメラの 内部パラメータ $K$
  - 2つのカメラ間の相対外部パラメータ（相対姿勢） $[\boldsymbol{\mathrm{R}} \space | \space \boldsymbol{\mathrm{t}}]$

ここで$K$とか$R$とか $\mathrm{t}$ が出てきて混乱すると思うのですが、これらの値の意味を理解するためにはカメラ幾何（幾何学的キャリブレーション）やエピポーラ幾何について触れる必要があります。

幾何学的キャリブレーション¹
- 3次元空間中のある点から発せられた光が画像のどの位置に投影されるか
  - 3次元空間と2次元画像平面の幾何学的変換特性を求める
  - 例: ピンホールカメラモデルにおいて内部パラメータや外部パラメータを求めること
エピポーラ幾何¹
- 3次元のシーンを撮影した2つの画像間の特徴点の対応には拘束条件があり、それを表すのが以下２つ
  - 基礎行列（Fundamental Matrix） $F$: 画像座標系での拘束条件
  - 基本行列（Essential Matrix） $E$: カメラ座標系での拘束条件
- この2つのカメラと3次元点の空間的対応関係はエピポーラ幾何と呼ばれる

1.1.2 カメラ幾何

カメラ幾何の基礎知識¹
- 3次元点を画像平面へ投影する手順
  - ワールド座標系 →カメラ座標系 → 画像座標系
  - 「カメラ → 画像」変換を表すのが 内部パラメータ
  - 「ワールド → カメラ」変換を表すのが 外部パラメータ
上記の投影をするにあたって色んなカメラモデルがある
- このモデルによって持っているパラメータの種類や投影方法が異なる
- 今回のコンペティション²ではピンホールカメラ（pinhole camera）モデルを仮定している
  - （おそらく）一番シンプルで最も使われているカメラモデル

ピンホールカメラモデルを仮定した場合の各座標系（ワールド・カメラ・画像）は以下の図³のようになる。

図の中の各パラメータや説明に用いるパラメータについて説明する。

$w$: 世界座標系（3次元）
$c$: カメラ座標系（3次元）
- 世界座標系でのカメラの位置 $\boldsymbol{\mathrm{t}}$ を原点とする姿勢 $\boldsymbol{\mathrm{R}}$ を考慮した座標系（≒ カメラから見た座標系）
  - $\boldsymbol{\mathrm{t}}$: 位置、3次元座標
  - $\boldsymbol{\mathrm{R}}$: 姿勢、いくつかの表現方法がありこの記事では1つ目を用いるが、どれも意味は同じ
    - 1. 3次元空間上での回転を表す $3 \times 3$ の行列
    - 2. 3次元方向の向きベクトル（3パラメータ）と、その向きを回転軸とした回転角度（1パラメータ）
    - 3. クォータニオン（4パラメータ）
      - 実装上ではこれが用いられることが多い（competition host が用意した notebook⁴でも使われている）
      - この記事⁵がわかりやすかったです
画像座標系(2次元)
- $u$ 軸と $v$ 軸がある
- 基本画像の左上の角を原点とする
$\boldsymbol{\mathrm{M_i}}$: 世界座標系 $w$ における対象の物体の座標（3次元)
- $\boldsymbol{\mathrm{M_i}} = [X, Y, Z, 1]^T$
- $1$ は計算の都合上つけている
$\boldsymbol{\mathrm{M_{Ci}}}$: カメラ座標系 $c$ における対象の物体の座標（3次元）
- $\boldsymbol{\mathrm{M_{Ci}}} = [X_c, Y_c, Z_c]^T$
$\boldsymbol{\mathrm{m_i}}$: 画像座標系 における対象の物体の座標（2次元）
- $\boldsymbol{\mathrm{m_i}} = [u, v, 1]^T$
$K$: カメラの内部パラメータ（camera calibration matrix）であり以下のように表せる
- $f_x, f_y$: 画像座標系の各軸の焦点距離
- $(u_0, v_0)$: 主点（principal point offset）
  - 光軸（光学中心と焦点を通る直線）と画像平面の交点
- $\gamma$: スキュー（せん断）係数¹
  - 画像座標系の $u$ 軸に対する $v$ 軸の傾き
  - 直行する場合は $0$
  - 最近のデジタルカメラでは $\gamma = 0$ と近似できるものが多いため、OpenCVの関数では $\gamma = 0$ として扱っている

K=\left[\begin{array}{ccc}
f_{x} & \gamma & u_{0} \\
0 & f_{y} & v_{0} \\
0 & 0 & 1
\end{array}\right]

このとき カメラ座標系 で表した物体の座標 $\boldsymbol{\mathrm{M_{Ci}}}$ から 画像座標系 の物体の座標 $\boldsymbol{\mathrm{m_i}}$ への投影は以下の式で表せる。

s \boldsymbol{\mathrm{m_i}} = K \boldsymbol{\mathrm{M_{Ci}}}

上記のように画像中の2次元点から3次元空間への投影を考えたとき、1枚の画像だけでは奥行きが求まらないためスケールパラメータ $s$ の不定性を有する。

また 世界座標系 で表した物体の座標 $\boldsymbol{\mathrm{M_i}}$ から カメラ座標系 の物体の座標 $\boldsymbol{\mathrm{M_{Ci}}}$ への変換は以下の式で表せる。

\boldsymbol{\mathrm{M_{Ci}}} =  [\boldsymbol{\mathrm{R}} \space | \space \boldsymbol{\mathrm{t}}] \boldsymbol{\mathrm{M_i}}

よって 世界座標系 で表した物体の座標 $\boldsymbol{\mathrm{M_i}}$ と 画像座標系 の物体の座標 $\boldsymbol{\mathrm{m_i}}$ の関係は以下のように表せる。

\begin{aligned}
\textbf{スケール} \cdot \textbf{画像座標} &= \textbf{内部パラメータ} \times \textbf{カメラ座標} \\
&= \text{内部パラメータ} \times \textbf{外部パラメータ} \times \textbf{世界座標}
\end{aligned}

\begin{aligned}
s \boldsymbol{\mathrm{m_i}} &= K \boldsymbol{\mathrm{M_{Ci}}} \\
&= K [\boldsymbol{\mathrm{R}} \space | \space \boldsymbol{\mathrm{t}}] \boldsymbol{\mathrm{M_i}}
\end{aligned}

上記の式について各パラメータを展開すると以下のようになる。

\begin{aligned}
s \left[\begin{array}{l}
u \\
v \\
1
\end{array}\right] &=\left[\begin{array}{ccc}
f_{x} & \gamma & u_{0} \\
0 & f_{y} & v_{0} \\
0 & 0 & 1
\end{array}\right]\left[\begin{array}{cccc}
r_{11} & r_{12} & r_{13} & t_{1} \\
r_{21} & r_{22} & r_{23} & t_{2} \\
r_{31} & r_{32} & r_{33} & t_{3}
\end{array}\right]\left[\begin{array}{c}
X \\
Y \\
Z \\
1
\end{array}\right]
\end{aligned}

1.1.3 エピポーラ幾何

2つのカメラと3次元点の空間的対応関係は エピポーラ幾何 と呼ばれる
- 上図⁶では同じ物体（シーン）を、 $o$ から撮影した画像と $o'$ から撮影した画像を表している
このとき座標 $\boldsymbol{x}$ に写っている座標は、世界座標系では図内の3つの $\boldsymbol{X}$ のように直線上のどこかの点に対応する
- 1枚の画像からは奥行きが定まらないため
またそれぞれの $\boldsymbol{X}$ を $o'$ から撮影した画像上の座標に対応させると、図内の3つの $\boldsymbol{x}'$ のように直線 $l'$ 上のいずれかの点に対応する
このように座標 $\boldsymbol{x}$ を1つ定めると $\boldsymbol{x}'$ に関する制約を与える
- これを エピポーラ拘束 といい、下記の式で表される
  - ここでの $F$ が 基礎行列（Fundamental matrix）
- エピポーラ拘束の導出はこの記事⁷がわかりやすかったです

\begin{equation}
\boldsymbol{x}'{}^{T} F \boldsymbol{x}=
\left[\begin{array}{lll}
u' & v' & 1
\end{array}\right]\left[\begin{array}{lll}
f_{11} & f_{12} & f_{13} \\
f_{21} & f_{22} & f_{23} \\
f_{31} & f_{32} & f_{33}
\end{array}\right]\left[\begin{array}{c}
u \\
v \\
1
\end{array}\right]=0
\end{equation}

基礎行列 $F$ を求める方法¹
- 基礎行列 $F$ は9つの要素をもつが、スケールは任意なので解を求めるには 8つの方程式が必要となる
  - そのため8個の対応点を用いて上記式を連立1次方程式として解く（ 8点アルゴリズム ）
    - 例えば後述する Local Feature Matching で 8個以上の座標の対応を得ると算出できる
  - 対応点が8つ以上ある場合はすべての対応点を利用して特異値分解(SVD)などを用いた最小二乗法により計算する
  - 特徴点の対応から基礎行列 $F$ を推定する処理は findFundamentalMat() に実装されている
また2つのカメラの内部パラメータである$K$と$K'$が既知の場合、下記のように基本行列（Essential matrix） $E$ が算出できる
- 基礎行列（Fundamental matrix） と 基本行列（Essential matrix） の違い
  - 基礎行列（Fundamental matrix）: 2つのカメラの内部パラメータと相対姿勢 $[\boldsymbol{\mathrm{R}} \space | \space \boldsymbol{\mathrm{t}}]$ を含む
  - 基本行列（Essential matrix）: 2つのカメラの相対姿勢 $[\boldsymbol{\mathrm{R}} \space | \space \boldsymbol{\mathrm{t}}]$ を含む

E = K'^TFK

基本行列 $E$ に含まれるカメラの相対姿勢 $[\boldsymbol{\mathrm{R}} \space | \space \boldsymbol{\mathrm{t}}]$ は3次元点と両カメラの姿勢によって4通りに分解される
- 4通りの中から「3次元点が両カメラ前方に復元される」という条件を加えることで最終的なカメラ姿勢を得ることができる

1.2 Data

Train
- 16シーン（16種類の建物）
- images: 5.6k
  - 各画像のカメラの内部パラメータも与えられていた
  - jpg（test は png）
  - 1 pair はある同シーンを撮影した 2枚の画像（img1, img2）
- fundamental matrix(fm): 1.4M
  - ある同schene の (img1, img2) に対する fm
  - もし (img1, img2) から fm を学習するモデルを作るならこれがデータ数
  - fm(img1, img2) と fm(img2, img1) は通常別の値
- 各写真に対するカメラ情報（位置・姿勢）も配布されている

Trainの内訳

scene	images	fundamental matrixs
st_peters_square	622	193,131
brandenburg_gate	350	61,075
trevi_fountain	706	248,865
lincoln_memorial_statue	214	22,791
pantheon_exterior	321	51,360
piazza_san_marco	68	2,278
buckingham_palace	446	99,235
taj_mahal	399	79,401
temple_nara_japan	217	23,436
sagrada_familia	90	4,005
notre_dame_front_facade	911	414,505
colosseum_exterior	499	124,251
sacre_coeur	281	39,340
st_pauls_cathedral	142	10,011
grand_place_brussels	236	27,730
british_museum	176	15,400
Total	5,678	1,416,814

Test
- 公式のデータ定義⁸に記載されている内容
  - roughly 10,000 pairs of images
  - public:private = 49:51
  - sample_id, batch_id, image_[1/2]_id が入力として与えられる
  - image_path = test_image_dir / batch_id / image_[1/2]_id.png
- probing
  - batch_ids: 85~90
  - total images: 18,000 ~ 18,400

1.3 Metrics

このコンペティションでは mean Average Accuracy (mAA) が採用されていました。（ただこの分野で一般的な指標なのか私はわかりませんでした）

0 から 1 の間の値
高いほどよい

具体的な計算方法は公式notebook⁴に記載されていますので大雑把な計算方法を以下に述べます。

各パラメータ定義
- $F$: 基礎行列（Fundamental matrix)
- $E$: 基本行列（Essential matrix）
- $[\boldsymbol{\mathrm{R}} \space | \space \boldsymbol{\mathrm{t}}]$: 相対姿勢
- $gt$: 正解（Ground truth）
- $pred$: 予測（Predict）
mean Average Accuracy (mAA) の算出方法
- Step1. 基礎行列 $F_{gt}$ と $F_{pred}$ から基本行列 $E_{gt}$ と $E_{pred}$ を計算
  - Host は test images のカメラの内部パラメータ $K$ を持っているので計算可能
- Step2. 基本行列 $E_{gt}$ と $E_{pred}$ から相対姿勢を抽出する
  - $[\mathbf{R_{gt}} \space | \space \mathbf{t_{gt}} ]$
  - $[\mathbf{R_{pred}} \space | \space \mathbf{t_{pred}} ]$
  - コードとしては _, R, T, _ = cv2.recoverPose(E, keypoints1, keypoints2) で抽出できる
- Step3. $\mathbf{R}$ と $\mathbf{t}$ のそれぞれについて、あるしきい値を設定したときに $gt$ と $pred$ の誤差がしきい値未満なら正解として Accuracy を計算する
- Step4. しきい値を以下のように変えて平均をとったものが mean Average Accuracy (mAA)
  - $\mathbf{R}$: thresholds_r = np.linspace(1, 10, 10) # In degrees.
  - $\mathbf{t}$: thresholds_t = np.geomspace(0.2, 5, 10) # In meters.

2. Related (AI) Task

このコンペティションでは 同じシーンを撮影した2枚の画像（ペア画像） を入力として 基礎行列（Fundamental matrix） を出力することを要求されていました
ただし現在 基礎行列（Fundamental matrix） の推定においては、 Image Classification や Object Detection のように End2End Deep Learning（つまり Deepでポン）が主流ではないようです
- 自分が調べた限りでは、 End2end Deep Learning によって基礎行列を推定する研究はかなり少なかったです
- Google Scholarで調べると年1,2paper ぐらい
また今回のコンペティションではあるペア画像の入力時に他の画像を参照可能でしたので、3枚以上の画像から基礎行列を推定することも可能でした
- Host いわく「本意ではないが違反ではない」⁹
- 入出力例
  - 入力: 複数ペア画像
  - 出力: 複数基礎行列
このようにいくつかのアプローチが考えられるので、ここでは関連するAI（もしくは画像処理）タスクをいくつか紹介しようと思います

ここでは関連タスクとして以下4つについて大雑把に紹介します。

Local Feature Matching(+ cv2.findFundamentalMat)
- 上位 Solution 見るとほとんどこのアプローチみたいでした
SfM(Structure from motion)
MVS(Multi view stereo)
Estimate Fundamental matrix with end2end DNN

他には Dense Matching とかも基礎行列推定に使える気がするのですが、調査してないのでここでは触れません…。

2.1 Local Feature Matching(+ `cv2.findFundamentalMat`)

2つの画像間で局所特徴（Local Feature）を紐付けるタスク
- かつては SIFTなどの hand-craft feature が主流だったが最近では Deep による特徴量抽出が増えている
- Paper with code¹⁰ 見ると LoFTR（Detector-Free Local Feature Matching with Transformers)¹¹が強い
  - あとコードとかも整理されてて使いやすいようになっている
Local Feature Matching を使った基礎行列の推論ステップ
- Step1. 2枚の画像に対し Local Feature Matching を適用して画像間で8個以上の座標の対応を取得
- Step2. cv2.findFundamentalMat() 適用
  - 対応が8個未満の場合は 0 にしているが、今回のデータではほとんど 8個以上あった

2.2 SfM(Structure from motion)

弊チームではこの SfM が適用できないかに結構時間をかけたのかなと思います。（COLMAP の notebook 移植が地獄でした😇）
ただ結局 Local Feature Matching の方が LB 高かったので最終的には不採用となりました🥺

複数視点の画像を用いてカメラの位置姿勢と特徴点の3次元位置を推定する手法¹
- 同じシーンを撮影した画像を数十枚から数百枚程度入力とする
- オプションでカメラの内部パラメータも推定できたりする
- やりたいことは3次元の疎な点群を得ることなんですが、その中間生成物としてカメラの位置姿勢とカメラの内部パラメータが得られる
  - これにより指定したペア画像間での基礎行列 $F$ を得ることができる
代表的なモデル（たくさんあるので一部のみピックアップ）
- COLMAP(2016)¹²
  - 今流行の NeRF(2020)¹³でも COLMAP が使用されてる
  - 元祖 NeRF ではカメラの位置姿勢とカメラ内部パラメータを事前に必要とするため COLMAP で算出している
- hloc(2020)¹⁴
以下は COLMAP を使用して復元したときの結果です
- 画像内の赤い点と枠が各カメラの位置姿勢と画像平面を表しています

ただし通常のSfMモデルは 同シーンで撮影した複数画像 を入力とする必要があり、もしこのコンペティションで使用して基礎行列を推定しようとすると以下のように一工夫必要になります
SfM を使った基礎行列の推論ステップ例
- Step1. Test data に対して同シーン判定
  - 例: Google Landmark Retrieval trained feature¹⁵ を使ったクラスタリング
- Step2. SfM 対象の画像に対して SfM 適用、それ以外には Local Feature Matching による基礎行列推論を適用

2.3 MVS(Multi view stereo)

基礎行列の推定では特に活用するイメージがないのですが SfM に関連するタスクなので一応紹介します
カメラの位置姿勢が既知の条件で多視点幾何を利用して被写体の密な3次元形状を復元する手法¹
以下はOpenMVS¹⁶のデモから取得した画像（実際のデモはグリグリ動かせる）
- 思ったより密で感動しました
- ぜひ皆さんにもデモページ見て欲しいです

2.4 Estimate Fundamental matrix with end2end DNN

いわゆるDeepでポンアプローチです
Local Feature Matching では対応点を検出後 cv2.findFundamentalMat で外れ値の除去や基礎行列の計算を行っていますが、この部分を省略してDNNが直接基礎行列を出力するアプローチです
調査前は、基礎行列は $3 \times 3$ であることから最大9個の値を出力するだけなので意外といけるのでは？と思ってました
ただ少し調査したところ以下の理由から本コンペで試してみるのは少し難しそうでした
- 先行研究・実装例が非常に少ない
  - Local Feature Matching + cv2.findFundamentalMat で十分精度が出るから？
    - もしくは外れ値の除去を DNN 内でやるのがめんどくさい？
  - それ以上の精度が必要だったりその後の処理（3次元復元）を考えるなら SfM を頑張ったほうが良いから？
  - もしかしたらカメラの内部パラメータと pose をそれぞれ推論すれば計算できるからかも…？
- 基礎行列の制約をDNNのmoduleやLoss・学習方法に反映させるのが難しい？
  - 基礎行列は $3 \times 3$ の行列（9つの値）ならなんでも良いわけではなく、以下を満たしている必要があります
    - ランク 2
    - 自由度 7
一応見つけた先行研究を記載します
- Deep Fundamental Matrix Estimation without Correspondences(2018)¹⁷
- An End to End Network Architecture for Fundamental Matrix Estimation(2020)¹⁸
- Estimating the fundamental matrix based on the end-to-end convolutional network(2022)¹⁹

3. Basic Approach(LoFTR -> `cv2.findFundamentalMat`)

このnotebook²⁰で扱ってます
LoFTR自体の解説はしません
画像読み込みや前処理、CV計算用の関数を除くとやっているのは下記だけです
- これだけでできるのすごすぎるンゴ…

LoFTR擬似コード

import numpy as np
import cv2
import torch
import kornia.feature as KF

# Load model
device = torch.device('cuda')
matcher = KF.LoFTR(pretrained=None)
matcher.load_state_dict(torch.load("../input/kornia-loftr/loftr_outdoor.ckpt")['state_dict'])
matcher = matcher.to(device).eval()

# Inference
F_dict = {}
for i, sample_id, image0, image1 in enumerate(test_samples):    
    with torch.no_grad():
        correspondences = matcher(image0=image0, image1=image1)
    
    # 対応点
    mkpts0 = correspondences['keypoints0'].cpu().numpy()
    mkpts1 = correspondences['keypoints1'].cpu().numpy()
    
    # Calc fundamental matrix
    if len(mkpts0) > 7:
        F, _ = cv2.findFundamentalMat(mkpts0, mkpts1, cv2.USAC_MAGSAC, 0.25, 0.9999, 100000)
        F_dict[sample_id] = F
    else:
        F_dict[sample_id] = np.zeros((3, 3))

4. Gold solutions（6/6 更新）

大雑把なポイント
- train(random sampling)と public LB は相関しないが、public/private はある程度相関するようだった
  - そのため結果としては CV 作るより sub して LB 確認したほうが良さそうだった
    - うまく LB と相関するような train subset を作ったチームもいたようです(1st, 10th)
- 学習は基本しない（train data とは）
  - LoFTR とかが MegaDepth²¹ という巨大データセットで学習した weight を提供していて、この weight で十分精度が出たことや、自分で再学習するのが難しかったことが要因としてあります（e.g. 32GB x 64GPU hours）
  - 再学習する暇があるなら TTA 探索したり他のモデルの結果をアンサンブルして sub して LB 見ることが重要そうでした
- 基本は Local Feature Matching ベースのアプローチ
  - TTA やアンサンブル頑張る
    - cv2.findFundamentalMat() 前の keypoints を concat する
    - 推論時間の許す限り
- いかに画像サイズやモデル数を増やせるかの戦いでもあった
  - LoFTRなどは画像サイズが非固定でかつ正方形でなくても良い（正方形の方がGPUメモリを必要とする）ので、たくさんsubして限界サイズを確認するのは有効だった
  - 1st solution では LFM -> 密集箇所の crop -> resize によってより resize が効くようにしていた

4.1 全体外観

全体を眺めるため以下のポイントでまとめてみました。

is_LFM_only: Local Feature Matching のみだったか
- SfM 等も採用したか
- 確認できた下記のチームでは全員 False だったので表から割愛
is_solo: solo か team か
train_model: モデルを学習したか
- 確認できた下記のチームでは全員 False だったので表から割愛
models: モデル
points: solution のポイント

	is solo	models	points
1st	F	LoFTR SuperGlue DKM DBSCAN(for clustering)	・2step LFM 　・LFM -> keypoints clustering 　・-> crop dense area -> resize -> LFM ・ensemble multi-resolution matching
2nd	T	`new Model` LoFTR SuperGlue QuadTree	・new Model（公開待ち） Normalized Positional Encoding
4th	F	LoFTR SuperGlue DKM QuadTree	・no TTA ・superglue とかも限界最大サイズまで試してる
6th	F	LoFTR SuperGlue DKM QuadTree	・TTA(rotation) ・confidence filter
7th	F	LoFTR DKM	・mkpts clustering & crop ・Warping (back and forth) matching ・VSAC ・Radius NMS for filtering mkpts
9th	T	LoFTR SuperGlue DKM	・modify DKM confidence ・multi thread for increase RANSAC iter ・TTA(rot, flip)
10th	F	LoFTR LoFTR-SE2 SuperGlue DKM	・Ensemble with DKM-ROI ・SSC(NMS) for filterring mkpts ・Outlier Handling
11th	T	QuadTree SuperGlue	・TTA(scale) ・fp16 ・2-stage MAGSAC++(fewer iter + more iter)

参加した所感

色々試せて楽しかったです（小並感）

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up