RootSIFT（SIFT 記述子の改良）

ここで行うこと

SIFT の準備：　画像から局所特徴量（キーポイントと記述子）を取り出す。
RootSIFT への変換：　 SIFT 記述子に L1 正規化と平方根の２つの後処理を施し、記述子を改良する。
考察：　なぜ RootSIFT が SIFT より画像検索・画像照合の精度を上げるのかを、距離の観点から確かめる。

SIFT について（特許は 2020 年に失効）

SIFT（Scale-Invariant Feature Transform, スケール不変特徴変換）は、 D. Lowe による画像の局所特徴量で、拡大・縮小・回転に対して安定なキーポイントを検出し、各キーポイントの周囲を 128 次元のベクトル（記述子）で表す。

SIFT には特許（US 6,711,293, University of British Columbia）があり、長い間、商用利用に注意が必要だった。 この特許は 2020 年 3 月 7 日に失効し、現在は法的な制限なく自由に利用できる。 OpenCV でも、以前は追加モジュール（opencv-contrib の nonfree）が必要だったが、 OpenCV 4.4.0 / 3.4.11 以降は本体（features2d）に統合され、 cv2.SIFT_create() だけで使える。

RootSIFT とは

RootSIFT は、Arandjelović と Zisserman が 2012 年に提案した、 SIFT 記述子をわずかな後処理だけで改良する手法。追加の学習やパラメータ調整は不要で、既存の SIFT 記述子にそのまま適用できる。

see Three things everyone should know to improve object retrieval (Arandjelović and Zisserman, CVPR 2012)

RootSIFT の計算手順

SIFT 記述子（各成分は 0 以上）に対して、次の２ステップを行う。

L1 正規化：　記述子ベクトルを、その要素の総和で割る。
各要素の平方根：　正規化後の各要素の平方根をとる。

この２ステップだけで、 ユークリッド距離での比較が、ヒストグラム間の類似度でよく使われるヘリンジャー距離（Bhattacharyya 係数）に基づく比較と等価になる。その結果、画像検索や画像照合の精度が上がる。

手順（Python, OpenCV を使用）

準備（インストール）

Python と OpenCV, NumPy を入れる。OpenCV 4.4.0 以降であれば SIFT がそのまま使える。

python -m pip install --upgrade pip
python -m pip install opencv-python numpy

SIFT 記述子を取り出し、RootSIFT に変換する

import cv2
import numpy as np

def root_sift(descs, eps=1e-7):
    """SIFT 記述子 (N, 128) を RootSIFT に変換する。"""
    if descs is None or len(descs) == 0:
        return descs
    # 1. L1 正規化（各記述子を要素の総和で割る）
    descs = descs / (descs.sum(axis=1, keepdims=True) + eps)
    # 2. 各要素の平方根
    descs = np.sqrt(descs)
    return descs

# 画像をグレースケールで読み込む
img = cv2.imread('image.jpg', cv2.IMREAD_GRAYSCALE)

# SIFT（OpenCV 4.4.0 以降は本体に含まれる）
sift = cv2.SIFT_create()
keypoints, descriptors = sift.detectAndCompute(img, None)

# RootSIFT へ変換
root_descriptors = root_sift(descriptors)

print(descriptors.shape)       # 例: (N, 128)
print(root_descriptors.shape)  # 同じ形状 (N, 128)

動かしてみる

上のコードを rootsift.py という名前で保存する。
同じフォルダに image.jpg を置く。
ターミナルで python rootsift.py を実行する。
記述子の形状が SIFT と RootSIFT で同じ（列数 128）であることを確認する。形状は変わらず、中身（値の分布）だけが変わる点がポイント。

別実装例（Java）

考え方は同じ。記述子 desc の総和で割り（L1 正規化）、各要素の平方根をとる。下は符号にも対応させた例（標準の SIFT 記述子は 0 以上なので、通常は負にはならない）。

float sum = 0.0f;
for (float f : desc)
    sum += f;
if (sum != 0) {
    for (int i = 0; i < desc.length; i++) {
        if (desc[i] < 0) desc[i] = (float) -Math.sqrt(-desc[i] / sum);
        else             desc[i] = (float)  Math.sqrt( desc[i] / sum);
    }
}

考察ポイント

RootSIFT どうしのユークリッド距離を計算すると、もとの SIFT のヒストグラムどうしのヘリンジャー距離に一致する。なぜそうなるかを、平方根をとる操作と内積の関係から確かめてみる。
画像検索（クエリ画像に近い画像を探す）で、SIFT と RootSIFT の検索結果を並べて比べる。どのような画像で差が出やすいかを観察する。
L1 正規化のかわりに L2 正規化を使うと、結果はどう変わるか試してみる。