Kaggle Image Matching Challenge 2022 まとめ

- 今回 [Image Matching Challenge 2022 \| Kaggle](https://www.kaggle.com/competitions/image-matching-challenge-2022) に参加しました
    - 約1ヶ月ほど参加しました
    - 一緒に参加してくださったチームメンバーに圧倒的感謝 :pray:
        - [arutema47（@arutema47）さん](https://twitter.com/arutema47)
        - [yu4u（@yu4u）さん](https://twitter.com/yu4u)
        - [かまろ/Camaro（@mlaass1）さん](https://twitter.com/mlaass1)
        - [s\_shohey（@s\_shohey）さん](https://twitter.com/s_shohey)
    - 結果は 41 / 653 teams で Silver でした（ぐやじいでず）
- 悔しいですが学んだことも色々あったので記事に残します
    - あとやってない人からするとこのコンペが何をしてるのか分かりづらい

# 1. About Competition

[Image Matching Challenge 2022 \| Kaggle](https://www.kaggle.com/competitions/image-matching-challenge-2022/leaderboard)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/33573/b57d3bed-11f3-6bce-ef47-f9d0805ed655.png)


## 1.1 Task

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

### 1.1.1 Target Value(input & output)

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

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

[^1]: [コンピュータビジョン ―広がる要素技術と応用― \(未来へつなぐ デジタルシリーズ 37\) \| Amazon](https://www.amazon.co.jp/dp/4320123573)

<img width="500" alt="入出力の図" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/33573/1a0abea7-98d3-9b87-825c-66832719bde8.png">

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

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

### 1.1.2 カメラ幾何

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

[^3]: [Image Matching Challenge 2022 - overview \| Kaggle](https://www.kaggle.com/competitions/image-matching-challenge-2022/overview/problem-definition)

ピンホールカメラモデルを仮定した場合の各座標系（ワールド・カメラ・画像）は以下の図[^4]のようになる。
[^4]: [Pinhole Camera \- Kornia](https://kornia.readthedocs.io/en/latest/geometry.camera.pinhole.html)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/33573/d245181a-7eee-2730-d10e-dc7e7f4e0129.png)

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

- $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[^5]でも使われている）
                - この記事[^6]がわかりやすかったです
- 画像座標系(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$: スキュー（せん断）係数[^1]
        - 画像座標系の $u$ 軸に対する $v$ 軸の傾き
        - 直行する場合は $0$
        - 最近のデジタルカメラでは $\gamma = 0$ と近似できるものが多いため、OpenCVの関数では $\gamma = 0$ として扱っている

```math
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}}$ への投影は以下の式で表せる。


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

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

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

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

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

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

```math
\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}
```

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



```math
\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}
```


[^5]: [imc2022\-training\-data \| Kaggle](https://www.kaggle.com/code/eduardtrulls/imc2022-training-data)
[^6]: [クォータニオン \(Quaternion\) を総整理！ ～ 三次元物体の回転と姿勢を鮮やかに扱う ～ \- Qiita](https://qiita.com/drken/items/0639cf34cce14e8d58a5)

### 1.1.3 エピポーラ幾何

<img width="700" alt="Epipolar Geometry" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/33573/a3875331-2669-c8b9-ccbe-b72abe7ceb1e.png">

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

```math
\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$ を求める方法[^1]
    - 基礎行列 $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}}]$ を含む

```math
E = K'^TFK
```

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

[^2]: [エピポーラ幾何 \- Qiita](https://qiita.com/Thought_Nibbler/items/9cb7c2637000eecc1a30)
[^7]: [OpenCV: Epipolar Geometry](https://docs.opencv.org/4.x/da/de9/tutorial_py_epipolar_geometry.html)

## 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
    - 公式のデータ定義[^8]に記載されている内容
        - 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

[^8]: [Image Matching Challenge 2022 - Data \| Kaggle](https://www.kaggle.com/competitions/image-matching-challenge-2022/data)

## 1.3 Metrics

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

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

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

- 各パラメータ定義
    - $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 いわく「本意ではないが違反ではない」[^9]
    - 入出力例
        - 入力: 複数ペア画像
        - 出力: 複数基礎行列
- このようにいくつかのアプローチが考えられるので、ここでは関連するAI（もしくは画像処理）タスクをいくつか紹介しようと思います

[^9]: [Image Matching Challenge 2022 - Discussion - Competition Rules: Use images other than pair? \| Kaggle](https://www.kaggle.com/competitions/image-matching-challenge-2022/discussion/323364)

ここでは関連タスクとして以下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[^10] 見ると LoFTR（Detector-Free Local Feature Matching with Transformers)[^11]が強い
        - あとコードとかも整理されてて使いやすいようになっている
- `Local Feature Matching` を使った基礎行列の推論ステップ
    - Step1. 2枚の画像に対し Local Feature Matching を適用して画像間で8個以上の座標の対応を取得
    - Step2. `cv2.findFundamentalMat()` 適用
        - 対応が8個未満の場合は 0 にしているが、今回のデータではほとんど 8個以上あった

[^10]: [IMC PhotoTourism Benchmark \(Image Matching\) \| Papers With Code](https://paperswithcode.com/sota/image-matching-on-imc-phototourism)
[^11]: [zju3dv/LoFTR: Code for "LoFTR: Detector\-Free Local Feature Matching with Transformers", CVPR 2021](https://github.com/zju3dv/LoFTR)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/33573/3b1ed9c1-f862-d536-2f8b-e931e4a1541c.png)

## 2.2 SfM(Structure from motion)

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

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

[^14]: [colmap/colmap: COLMAP \- Structure\-from\-Motion and Multi\-View Stereo](https://github.com/colmap/colmap)
[^15]: [cvg/Hierarchical\-Localization: Visual localization made easy with hloc](https://github.com/cvg/Hierarchical-Localization)
[^16]: [bmild/nerf: Code release for NeRF \(Neural Radiance Fields\)](https://github.com/bmild/nerf)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/33573/417e64e7-3223-4c69-483d-c8cd32536689.png)

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

[^17]: [GLRet21: EfficientNetB0 Baseline Inference \| Kaggle](https://www.kaggle.com/code/hidehisaarai1213/glret21-efficientnetb0-baseline-inference)

## 2.3 MVS(Multi view stereo)

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

![スクリーンショット 2022-06-04 10.18.07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/33573/54d684b0-8229-0bfb-ccfa-c6f24e77752f.png)
![スクリーンショット 2022-06-04 10.18.36.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/33573/09be843c-f9b2-8a22-bf81-2071aa873c66.png)


[^13]: [cdcseacave/openMVS: open Multi\-View Stereo reconstruction library](https://github.com/cdcseacave/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)[^18]
    - An End to End Network Architecture for Fundamental Matrix Estimation(2020)[^19]
    - Estimating the fundamental matrix based on the end-to-end convolutional network(2022)[^20]

[^18]: [\[1810\.01575\] Deep Fundamental Matrix Estimation without Correspondences](https://arxiv.org/abs/1810.01575)
[^19]: [\[2010\.15528\] An End to End Network Architecture for Fundamental Matrix Estimation](https://arxiv.org/abs/2010.15528)
[^20]: [Estimating the fundamental matrix based on the end\-to\-end convolutional network](https://www.researchgate.net/publication/359273247_Estimating_the_fundamental_matrix_based_on_the_end-to-end_convolutional_network)

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

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

[^12]: [🥇 IMC 2022\-kornia : Score 0\.725 🥇 \| Kaggle](https://www.kaggle.com/code/cbeaud/imc-2022-kornia-score-0-725)

```python: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[^21] という巨大データセットで学習した 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 が効くようにしていた

[^21]:[MegaDepth: Learning Single\-View Depth Prediction from Internet Photos](https://www.cs.cornell.edu/projects/megadepth/)

## 4.1 全体外観

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

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

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

# 参加した所感
- 色々試せて楽しかったです（小並感）