Kaggle Image Matching Challenge 2023を振り返る

2023年4ー6月に開催された[Image Matching Challenge 2023](https://www.kaggle.com/competitions/image-matching-challenge-2023 "Image Matching Challenge 2023")(IMC2023)に参加し、４位（順位確定後は３位）を獲得することができました。
![スクリーンショット 2023-07-01 13.03.57.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325964/5dc74245-aa6f-e3e1-89fc-4754c72e397a.png)
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">お疲れ様でした！！<br>笑顔で泣いてる <a href="https://t.co/XyJHAnZLSO">pic.twitter.com/XyJHAnZLSO</a></p>&mdash; HeKa (@warm_start) <a href="https://twitter.com/warm_start/status/1668457467544752128?ref_src=twsrc%5Etfw">June 13, 2023</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
※画像は順位確定前のもの。

また、CVPR2023のワークショップの１つ[Image Matching: Local Features and Beyond](https://image-matching-workshop.github.io/ "Image Matching: Local Features and Beyond")に招待され、解法を話す機会をいただきました。
まさか自分がこのような貴重な場に参加できるとは思ってもみなかったです。大変刺激を受けました。

# どんなコンペ？
いわゆるSfM（Structure from Motion）と呼ばれるテーマにあたります。
オブジェクトを色々な角度から撮影して得た画像セットを使い、それぞれの画像の撮影位置と向きを推定し、その精度を競います。
尚、本コンペは、昨年に開催された[Image Matching Challenge 2022](https://www.kaggle.com/competitions/image-matching-challenge-2022 "Image Matching Challenge 2022")(IMC2022)の続編です。
IMC2022では、カメラの内部パラメータ（焦点距離や光学中心）が与えられていました。そのため、２枚の画像で特徴点マッチング（DNN等を使い、画像間の同一箇所をマッチングする）を行えば、三角測量の原理で両カメラの位置関係を算出可能でした。
一方、IMC2023では、完全な内部パラメータは与えられません。そのため、特徴点マッチングを行った上で、COLMAPというツールキットを使いカメラパラメータ推定と位置推定、および３D点群構築を同時最適化する、という手法（バンドル法）が最も合理的となります。
（私はSfMを扱ったりCOLMAPに触ったりするのは初めてでしたが、ホストが一連の処理のベースラインを提供してくれたので、スタートラインに立つのは簡単でした）

特徴点マッチングやカメラ位置の計算については、 fam_taroさんによる前回コンペのまとめが大変分かりやすいです。
今回のコンペ参加のための事前勉強においても、大変参考になりました。深く感謝申し上げます。
[　Kaggle Image Matching Challenge 2022 まとめ](https://qiita.com/fam_taro/items/bdc47e944d4612a0eac1 "Kaggle Image Matching Challenge 2022 まとめ")

# 精度を上げるために何が重要だった？
前述の通り、特徴点の一致ペアを得た上で、カメラ位置推定を行います。そのため、
①いかに正確な一致ペアを得るか。
②制限時間内でいかに多くの画像ペアでマッチングを行うか。
という点が基本的なポイントとなっています。

以下に、私自身のパイプラインで実装した処理とその効果を列挙します。（概ね[Discussionに投稿した解法](https://www.kaggle.com/competitions/image-matching-challenge-2023/discussion/416918 "Discussionに投稿した解法")の内容をなぞっています）
![inbox_9249230_1036693590b6655d8d48d588bfd69e9c_IMC-solution.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325964/fbf57e97-6b58-7823-69c3-0b52b8aaebb6.png)

## 画像の回転
デジカメで撮った写真は、９０°横向きになって保存されがちですが、今回のコンペで与えられたデータセットは、そのような横向きになった写真が含まれていました。
横向きになった場合、正しく特徴量を抽出することは困難です。
そこで、しきい値以上の数の特徴点ペアを得られるまで片方の画像を90°回転し続ける、という処理が必要です。
上位チームはだいたい全員がこれを行っていたようです。
（ただし、6位のKeyNetAffNetHardNet + Adalamでは補正せずともマッチングできるとのこと）

![20230620_4th_forkaggle.pptx.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325964/82e14a4e-d244-3baa-254f-19ac6d3bb5f6.png)
左：与えられた画像同士をそのままマッチング処理した場合。黄色い領域は互いに対応しているのだが、ペアを抽出できていない。
右：右側の画像を９０°回転させた場合。期待通りに抽出できるようになった。

回転させてもペアがほとんど得られないということは、その画像同士は一致する対象物がほとんど写り込んでいない、と判断し、あきらめて次のペアに進みます。

話は前後しますが、画像ペアの作成には、ベースラインで提供された、EfficientNetを使った類似度による選定プロセスをそのまま使いました。

## TTA・アンサンブル
IMC２０２２と同様、抽出モデルに入れる画像のサイズを様々に変えるマルチスケールTTAや、異なるモデルとのアンサンブルが、特徴点を漏れなく得るために有効でした。
また、IMC2022の1位解法で使われた、画像のCropを導入したチームも多かったです。
自分の場合、次項で説明する画像分割処理のほうが有効だったのと、処理時間に余裕がなかったため、マルチスケールTTAは行わず、DKMというモデルとのアンサンブルだけを採用しました。

![inbox_9249230_4a040a43881adc0532ccc0e5b4878c17_DKM_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325964/1116d42c-061f-b507-f9c9-3b36ea43f143.png)
DKMとの比較。SuperPoint/SuperGlue(SP/SG)では階段の部分（黄色い領域）を正しく認識できていないが、DKMではできている。
一方で、アーチなど他の領域はSP/SGが広い範囲でマッチできている。この２つを足し合わせることで精度向上に繋がったとみられる。

## 画像分割
画像を4分割してSuperPointで特徴点抽出を行い、SuperGlueで4×4=16通りの組み合わせで特徴点マッチングを行う、という処理が有効であると見出しました。
16通りも計算すると非常に時間がかかりそうですが、律速なのはSuperPoint側の処理なので、処理時間の増加はだいたい４倍で済んでいます。
下の例では、４分割したことで、一組の画像ペアから得られる特徴点ペアが約３倍になったことを示しています。

![inbox_9249230_59ee7b75b96f413775ba3f8f7e6fc6c0_split_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325964/d71aba73-0154-fdd1-c9c5-b0e5f7a8b152.png)

「TTAでマッチ数を増やすよりも、分割することで細かく念入りに特徴点ペアを探させた方が良いのではないか」、という気持ちで試してみました。
また、厳密に検証はしていませんが、マルチスケールTTAでは、各処理で得られたペア同士がしばしば重複すると思われます。
一方、分割する場合は、各ペアは重複しません。この点も有利に働いたのではないかと考えています。

## 並列処理
（１）特徴点の抽出とマッチングと、（２）COLMAPによる点群構築は、それぞれGPU、CPUを主に使います。
queueライブラリを使って両処理を並列化しました。
これにより処理時間が短縮され、処理する画像ペアの数やTTA処理を増やすことができました。
（GPU処理とCPU処理を並列化するアイデアは、IMC2022の6位解法を参考にしました。）

# 試せなかったこと（試すべきだったこと）
* EXIF情報の利用 
画像処理では基本的な情報となりますが、すっかり検討から漏れていました。
一部の画像で焦点距離の情報が得られます。3位と６位のチームはこれをCOLMAPに渡して活用していました。

* SuperPointのキャッシュ
各画像は繰り返し登場するのですから、SuperPointで得られる特徴点はキャッシュしておけば再利用できます。
2位と5位のチームで採用されていました。
これを使えばさらに時間短縮できていたと思います。

「試したけどうまくいかなかったこと」は書ききれないので割愛いたします。
Discussionの投稿でいくつか説明しているので、興味のある方はそちらをご覧ください。



# 上位解法まとめ
記事作成時点で解法が公開されたもののみ掲載しています。

| Place |Pair creation | Rotation | Models | Others |
|:-----------|:-----------|:-----------|:-----------|:-----------|
| [1st](https://www.kaggle.com/competitions/image-matching-challenge-2023/discussion/417407)  | NetVLAD        | True        | SP/SG, DKMv3         | Crop, Coarse-to-fine SfM         |
| [2nd](https://www.kaggle.com/competitions/image-matching-challenge-2023/discussion/416873)     | All pair      | True       | SP/SG         | Multi-run reconstruction |
| [3rd](https://www.kaggle.com/competitions/image-matching-challenge-2023/discussion/417191)*       | DINOv2        | True         | SP/SG    | GeoVertification, Setting Camera Params |
| [4th](https://www.kaggle.com/competitions/image-matching-challenge-2023/discussion/416918)*        | EfficientNet          | True           | SP/SG, DKMv3 |Image split       |
| [5th](https://www.kaggle.com/competitions/image-matching-challenge-2023/discussion/416816)*       | SP/SG+kNN | True  | SP/SG, MatchFormer |Crop         |
| [6th](https://www.kaggle.com/competitions/image-matching-challenge-2023/discussion/417045)*    | KeyNetAffNetHardNet+AdaLAM（matching distance）     | False      | KeyNetAffNetHardNet+AdaLAM         |
| [9th](https://www.kaggle.com/competitions/image-matching-challenge-2023/discussion/416842)*    | NetVlad     | True      |SP+GlueStick     | Matching with binary search |

※３位チームに何らかの規約違反があったのか、確定されたLBでは4位以降が繰り上がっています。
※Rotation: マッチング時の画像の回転処理の有無

Discussionには公開されていませんでしたが、８位のチームはLightGlueという独自のモデルを用いたそうです。
コンペ終了後に公開されました。
[https://github.com/cvg/LightGlue](https://github.com/cvg/LightGlue)

# （7/14追記）ホストによる振り返り
本コンペのホストが、タスク概要と主な解法について要約記事を公開したので紹介します。
[Image Matching Challenge 2023: The Unbearable Weight of the Bundle Adjustment](https://ducha-aiki.github.io/wide-baseline-stereo-blog/2023/07/05/IMC2023-Recap.html)
スコア向上につながった手法に加え、上手くいかなかった手法とその考察についても丁寧にまとめられています。
ちょっぴり辛口のユーモラスな文体で、楽しく読めました。

# 総括
画像処理コンペは計算資源での殴り合いになりがちなのですが、本コンペは「各画像をどうペアリング・前処理してモデルに渡すか」「公開済のモデルをどのように使いこなすか」という、アイデア勝負の性質が特に強かったです。
手元のGPU一枚を使い、ひたすら推論パイプラインの構築実験に集中すればよかったので、個人でも互角（？）に戦うことができました。

また、ChatGPTには大いに助けられました。
アイデアの実装やバグ修正、ペーパーの要約など、非常に強力なサポーターとなってくれました。
経験が浅い私でも上位に入れたのは、ChatGPTで実装力をブーストできたからと言っても過言ではないです。

次回のコンペも楽しみです。
特徴点マッチング、カメラ位置推定、と来たので、次回はいよいよ本格的な３Dモデル構築、あるいはNeRFタスクになるのでしょうか。
LightGlueも是非試してみたいです。