Kaggleで注目を集める画像特徴量抽出新手法、DELGの概要紹介

# はじめに
この記事はGoogle Landmark Recognitionで注目されている、画像特徴量抽出のアルゴリズムDELGを紹介します。
- [Unifying Deep Local and Global Features for Image Search](https://arxiv.org/abs/2001.05027)

このアルゴリズムは2020年1月に発表されたもので、日本語の文献はほとんどないと思われます。

# 概要
画像の特徴量抽出は画像全体の情報を反映したGlobal featureと、局所的な特徴を集めたLocal featureに大分されます。
これまで、この二つの特徴量抽出には、それぞれ別のアルゴリズムが採用されてきました。
本論文ではこれらを一つのアルゴリズムにまとめ、効率的に特徴量抽出を目的としています。
具体的には、Global featureには平均プーリング層を、Local featureにはattentive selectionを用いてこれを実現しています。
さらに、auto encoderをベースとしたlocal featureの次元削減も紹介しています。

結果として、このモデルは（Googleの公開しているLandmarkのデータセットを含め、）数々のデータセットでState of the artの成績となっています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/ad793213-b497-6da3-1652-e79fedd6c056.png)

- [Unifying Deep Local and Global Features for Image Search](https://arxiv.org/pdf/2001.05027.pdf)

# Global feature / Local featureとは

Global featureは画像全体から抽出される特徴量です。
また、Local featureは画像の一部分から抽出される特徴量の集まりです。

| |Global feature<br>(global descriptor, embedding) | Local feature|
|--- |--- |--- |
|抽出対象の範囲|- 全体|- 局所|
|次元|- 画像につき1次元|- 画像につき複数次元になりうる|
|抽出手順|- 全体を一斉に計算|1. 抽出する局所を選定(detector) <br>2.特徴量を抽出(descriptor)|
|特徴|- 1ステップなので軽量な計算 <br>- 出力は画像につき1次元なのでデータ量が抑えられる <br>- recallに優れる|- 画像の一部が隠れていても比較的ロバスト<br>- precisionに優れる|
|代表的手法|- カラーヒストグラム<br> - GeM pooling<br>- ArcFace loss|- SIFT<br>- SURF<br>- RANSAC<br>- DELF|

参考

- [Combining Local and Global Image Features for Object Class Recognition](http://vis-www.cs.umass.edu/papers/local_global_workshop.pdf)
- [局所特徴量のハッシングに基づく大規模画像](http://www.m.cs.osakafu-u.ac.jp/publication_data/1054/paper.pdf)


Global featureとLocal featureでは得意不得意が異なることがわかります。
類似画像の選択アルゴリズム(Retrival)では、一般的にGlobal featureによる選択の後、local featureによる順位の修正(geometric verification)が行われる二段構えがとられています。

# Autoencoderとは

ニューラルネットワークを用いた次元削減方法で、入力層よりもノード数の小さい中間層を挟むことで次元を削減します。

Local feature は一般的に大きな次元(100~1,000)になることから、PCAなどの次元削減を別途行うことが通例です。
しかし本論文ではこの次元削減もワンストップに行うことを目指しているため、ニューラルネットワークに組み込めるAutoencoderで次元の削減まで一気通貫して行っています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/864ab9d9-4aa1-8384-9469-fbb46b338cb0.png)
[Autoencoder](https://en.wikipedia.org/wiki/Autoencoder)

# 提案モデル

提案モデルの特徴は以下のようになっています。
- ResNetがベース
- Global feature extraction
    - 出力をGeneralized mean average(GeM)と全結合層の白色化により調整
    - ArcFace lossで学習
- Local feature
    - 特徴的な局所を判別するアルゴリズムが重要。Attention moduleを採用
    - autoencoderで次元削減
    - attention lossとreconstruction loss の二つで学習

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/0c87e2af-5f92-1764-152b-50feec720dbf.png)

- [Unifying Deep Local and Global Features for Image Search](https://arxiv.org/pdf/2001.05027.pdf)

# 実装

以下の画像のglobal featureとlocal featureの抽出を行います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/672b6d65-8ebe-daa9-d07b-d9e337ca97fd.png)

## Global feature

```py
import tensorflow as tf

# 学習済みDELGモデルを読み込みます
SAVED_MODEL_DIR = '../input/delg-saved-models/local_and_global'
DELG_MODEL = tf.saved_model.load(SAVED_MODEL_DIR)

# パラメータを設定します

## 抽出するGlobal featureの次元
NUM_EMBEDDING_DIMENSIONS = 2048
## 画像の解像度を設定します(Image Pyramids)
DELG_IMAGE_SCALES_TENSOR = tf.convert_to_tensor([0.70710677, 1.0, 1.4142135])
## DELGモデルのうち、global feature extractionに用いる部分のみ切り出します
DELG_INPUT_TENSOR_NAMES = ['input_image:0', 'input_scales:0']
GLOBAL_FEATURE_EXTRACTION_FN = DELG_MODEL.prune(DELG_INPUT_TENSOR_NAMES,
                                                ['global_descriptors:0'])


# 画像のパスから画像データをテンソルとして読み込みます
# image_pathは適宜設定してください
image_tensor = load_image_tensor(image_path)

# DELFでGlobal featureを抽出します
embedding_tensor_1 = GLOBAL_FEATURE_EXTRACTION_FN(image_tensor, DELG_IMAGE_SCALES_TENSOR)[0]

# 標準化します
embedding_tensor_2 = tf.nn.l2_normalize(
    embedding_tensor_1,
    axis=1,
    name='l2_normalization')

# 異なる解像度の結果を合体します
embedding_tensor_3 = tf.reduce_sum(
    embedding_tensor_2, axis=0, name='sum_pooling')

# さらにこれを標準化します
embedding_res = tf.nn.l2_normalize(
    embedding_tensor_3, axis=0, name='final_l2_normalization').numpy()
```

| |操作|サイズ|
|--- |--- |--- |
|image_tensor |画像データ|450, 800, 3||
|embedding_tensor_1 |3つの解像度に対して2048次元のGlobal feature抽出|3, 2048
|embedding_tensor_2 |標準化|3, 2048
|embedding_tensor_3 |解像度の軸をつぶす方向に合計|2048,
|embedding_res |標準化|2048,

## Local feature


```py

# パラメータを設定します
## 抽出する特徴量数の最大値
LOCAL_FEATURE_NUM_TENSOR = tf.constant(1000)

# モデルを切り出します
LOCAL_FEATURE_EXTRACTION_FN = DELG_MODEL.prune(
    DELG_INPUT_TENSOR_NAMES + ['input_max_feature_num:0', 'input_abs_thres:0'],
    ['boxes:0', 'features:0'])

# 画像をテンソルで読み込みます
image_tensor = load_image_tensor(image_path)

# DELFによるlocal featureの抽出
# 特徴量の位置と値を出力
features = LOCAL_FEATURE_EXTRACTION_FN(image_tensor, DELG_IMAGE_SCALES_TENSOR,
                                       LOCAL_FEATURE_NUM_TENSOR,
                                       DELG_SCORE_THRESHOLD_TENSOR,
                                      )

# 特徴量として抽出した画像の位置
# 出力の0列目と2列目、1列目と3列目を足して2で割る
keypoints = tf.divide(
  tf.add(
      tf.gather(features[0], [0, 1], axis=1),
      tf.gather(features[0], [2, 3], axis=1)), 2.0).numpy()


# 特徴量
# 標準化する
descriptors = tf.nn.l2_normalize(
  features[1], axis=1, name='l2_normalization').numpy()

```


```py

train_keypoints = keypoints
train_descriptors = descriptors
test_keypoints = keypoints_2 #比較対象
test_descriptors = descriptors_2 #比較対象

# descriptorsを木構造に変換し、距離が近い点を取得。
# 参考：https://myenigma.hatenablog.com/entry/2020/06/14/205753#kdtree%E3%81%A8%E3%81%AF
train_descriptor_tree = spatial.cKDTree(train_descriptors)
_, matches = train_descriptor_tree.query(
  test_descriptors, distance_upper_bound=max_distance)

test_kp_count = test_keypoints.shape[0]
train_kp_count = train_keypoints.shape[0]

test_matching_keypoints = np.array([
test_keypoints[i,]
  for i in range(test_kp_count)
　#最近傍の点がmax_distanceを超える場合は最大インデックス＋１が返ってくる
  if matches[i] != train_kp_count 
])
train_matching_keypoints = np.array([
  train_keypoints[matches[i],]
  for i in range(test_kp_count)
  if matches[i] != train_kp_count
])

```

比較する2枚の画像についてlocal featuresを求め、対応するdescriptorsを元に一致する部分を可視化した結果を以下に示します。
位置がピタリと合っていないのは残念ですが、特徴的な部分をおおよそ対応づけられていることがわかります。

|元画像|データオーグメンテーション|
|--- |--- |
|![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/86e5bcbe-3610-1893-4ece-c12cba03c038.png)　 |![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/ae22ea6a-ef20-b9a1-9858-681281dbe1ed.png) |
| ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/f18fb504-8215-23cf-7c41-47a12ddc1134.png)|![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/d4d75aa8-3ff1-192e-21eb-41d69d9c2a15.png)|

# 発展分野

これで局所特徴量とその対応は一応求まりましたが、より発展的には、以下の課題があります。
1. 対応点の精度を上げたい
2. 空間的関係を理解したい（どれくらい異なる角度から撮影された画像なのかの理解など）

こうした問題には、一般的にはRANSACアルゴリズムが用いられています。
また、RANSACよりも高速なアルゴリズムとしてpydegensacがkaggleでも紹介されています。
これらの内容は以下の記事がわかりやすいので、ぜひご覧になってください。

参考：
- [各画像の「移動量」と「変形量」の算出による特徴点の対応づけ](https://news.mynavi.jp/article/computer_vision-30/)
- [RANSAC: Pydegensac vs Scikit](https://www.kaggle.com/camaskew/ransac-pydegensac-vs-scikit)




# 終わりに

より詳しくは以下をご覧ください。
- [元の論文](https://arxiv.org/pdf/2001.05027.pdf)
- [元の実装](https://github.com/tensorflow/models/tree/master/research/delf)
- [実装の参考にしたKernel](https://www.kaggle.com/camaskew/host-baseline-example)