1. はじめに
類似画像検索アルゴリズムの一種に dHash というものがあります。アルゴリズムの中身は「Perceptual Hashを使って画像の類似度を計算してみる」を見ていただくのが分かり易いのですが、ざっくり以下のような特徴のある類似画像検索アルゴリズムだと私は理解しています。
- ハッシュ値計算が非常に高速
- 検索精度が比較的高く、特にfalse-positiveが少ない
- 対象画像に対してグレースケール変換した上でハッシュ値計算を行うため、多少の色彩のブレに強い
- 対象画像に対して9x8サイズの画像に縮小したうえでハッシュ値計算を行うため、多少の位置ズレに強い
そこで、この dHash を使って、レースゲーム Assetto Corsa のプレイのワンシーン（オンボード映像）からそのシーンがコース上のどの位置の画像なのかを特定することができるかを試してみました。
具体的には、以下のような流れになります。
①
まず、コースを1周するあるプレイ動画（オンボード映像）から全フレームを PNG 画像として抽出・保存します。
②
保存した全フレームの画像に対して dHash のハッシュ値を計算します。また、プレイ動画撮影時に取得したテレメトリーデータからある時刻に車両がどの位置にあったか特定できるので、その位置情報と組み合わせて計算したハッシュ値を検索用CSVファイルに保存します。
③
一方、別のプレイ動画からコース上の位置を特定したいワンシーンを選択します。
④
選択したワンシーンの画像に対して dHash のハッシュ値を計算します。
⑤
計算した dHash のハッシュ値に一番近いハッシュ値を持つ画像を検索用CSVファイルから検索します。検索でヒットした画像には②で位置情報を紐付けているので、その位置を選択したワンシーンのコース上の位置と見做します。
レースゲームのワンシーンは、コース上近い位置にいても、プレイごとに若干通るラインに差が出るなどの理由で若干位置ズレが発生します。そういった差を吸収して、類似画像検索ができるかというのが今回のポイントになるかと思います。
2. 実装コード
今回は Python で上述の処理を実装します。
2-1. プレイ動画からのフレーム画像抽出
プレイ動画ファイル（mp4ファイル）から全フレームの画像を抽出するには今回は OpenCV を使いました。以下のページを参考にしています。
フレーム画像が「（フレーム番号）.png」というファイル名で保存されます。
import cv2
import sys
def extract_frame(video_file, save_dir):
capture = cv2.VideoCapture(video_file)
frame_no = 0
while True:
retval, frame = capture.read()
if retval:
cv2.imwrite(r'{}\{:06d}.png'.format(save_dir, frame_no), frame)
frame_no = frame_no + 1
else:
break
if __name__ == '__main__':
video_file = sys.argv[1]
save_dir = sys.argv[2]
extract_frame(video_file, save_dir)
このスクリプトは③でも利用します。
2-2. dHashの計算と位置情報の紐付け
抽出したフレーム画像のうち、ある期間（特定の周回の部分）に該当する画像について、ImageHash パッケージの dhash 関数を用いて dHash のハッシュ値を計算します。加えて、以下のin-game Appスクリプトで取得したテレメトリーデータ（事前に該当部分だけを抽出）と紐付けを行い、検索用CSVファイルに出力します。
from PIL import Image, ImageFilter
import imagehash
import csv
import sys
frame_width = 1280
frame_hight = 720
trim_lr = 140
trim_tb = 100
dhash_size = 8
def calc_dhash(frame_dir, frame_no_from, frame_no_to, telemetry_file, output_file):
# テレメトリーデータファイルを読み込む
position_data = [row for row in csv.reader(open(telemetry_file), delimiter = '\t')]
writer = csv.writer(open(output_file, mode = 'w', newline=''))
for i in range(frame_no_from, frame_no_to + 1):
# 抽出したフレーム画像を読み込み、トリミングする（タイムなどが画像端に表示されているのを消すため）
frame = Image.open(r'{}\{:06d}.png'.format(frame_dir, i))
trimed_frame = frame.crop((
trim_lr,
trim_tb,
frame_width - trim_lr,
frame_hight - trim_tb))
# dHash 値の計算
dhash_value = str(imagehash.dhash(trimed_frame, hash_size = dhash_size))
# テレメトリーデータとの紐付け
# 画像もテレメトリーも一定周期で出力されているため、単純に行数比例で紐付ける
position_no = round((len(position_data) - 1) * (i - frame_no_from) / (frame_no_to - frame_no_from))
writer.writerow([
i,
dhash_value,
position_data[position_no][9],
position_data[position_no][10]
])
if __name__ == '__main__':
frame_dir = sys.argv[1]
frame_no_from = int(sys.argv[2])
frame_no_to = int(sys.argv[3])
telemetry_file = sys.argv[4]
output_file = sys.argv[5]
calc_dhash(frame_dir, frame_no_from, frame_no_to, telemetry_file, output_file)
このスクリプトの結果、以下のような（フレーム番号）、（ハッシュ値）、（メートル単位の2D座標位置）の情報がCSVファイルに出力されます。
731,070b126ee741c080,-520.11,139.89
732,070b126ee7c1c080,-520.47,139.90
733,070b126ee7c1c480,-520.84,139.92
このスクリプトは④でも利用します。
2-3. 一番近いハッシュ値の探索
指定したハッシュ値に一番近いハッシュ値を持つ画像を2-2.で出力した検索用CSVファイルから検索します。
ハッシュ値同士の近さはハミング距離を用います。ハミング距離の算出には gmpy2 パッケージの popcount を利用しています（とても高速らしいので）。
import csv
import gmpy2
import sys
def match_frame(base_file, search_hash):
base_data = [row for row in csv.reader(open(base_file))]
min_distance = 64
min_line = None
results = []
for base_line in base_data:
distance = gmpy2.popcount(
int(base_line[1], 16) ^
int(search_hash, 16)
)
if distance < min_distance:
min_distance = distance
results = [base_line]
elif distance == min_distance:
results.append(base_line)
print("Distance = {}".format(min_distance))
for min_line in results:
print(min_line)
if __name__ == '__main__':
base_file = sys.argv[1]
search_hash = sys.argv[2]
match_frame(base_file, search_hash)
以下のように、ハッシュ値が一番近い画像の情報と紐付いた位置情報を出力します。
（同じ距離の画像が複数ある場合は、全ての画像情報を表示します）
> python.exe 03_match_frame.py dhash_TOYOTA_86.csv cdc9cebc688f3f47
Distance = 8
['13330', 'c9cb4cb8688f3f7f', '-1415.73', '-58.39']
['13331', 'c9eb4cbc688f3f7f', '-1415.39', '-58.44']
3. 検索結果
今回は、ニュルブルクリンク北コース（全長20.81km）を TOYOTA 86 GT で走行したプレイ動画を全フレーム抽出⇒ハッシュ値計算を行い、BMW Z4 で走行した別のプレイ動画の幾つかのシーンの画像に近い画像を探してみます。
まずは有名どころの3つのコーナーの画像がちゃんと検索できるか確認してみます。
- Schwedenkreuz
| 検索に用いた画像 | ヒットした画像 | |
|---|---|---|
| 画像 |  |
 |
| ハッシュ値 | ced06061edcf9f2d | 0c90e064ed8f1f3d |
| 位置情報 | (-2388.29, 69.74) | (-2416.50, 66.67) |
ハッシュ値の距離 = 10, 位置情報のズレ = 28.4m
dHash ではハッシュ値の距離が10以下だと同じ画像と見做すと言われているそうですが、ギリギリですね。画像の上でも、コーナーの形状は似ていますが、周りの木の位置は若干違っており、似ている or 似ていないを判断し辛いですね。
- Bergwerk
| 検索に用いた画像 | ヒットした画像 | |
|---|---|---|
| 画像 |  |
 |
| ハッシュ値 | 7c5450640c73198c | 7c7c50642d361b0a |
| 位置情報 | (317.58, -121.52) | (316.18, -121.45) |
ハッシュ値の距離 = 11, 位置情報のズレ = 1.4m
これは画像的にはかなり近いですね。ただ、ハッシュ値の距離は 11 と先ほどより大きくなっています。
- Karussell
| 検索に用いた画像 | ヒットした画像 | |
|---|---|---|
| 画像 |  |
 |
| ハッシュ値 | 665d1d056078cde6 | 665c1d856050da8d |
| 位置情報 | (2071.48, 77.01) | (2071.23, 77.12) |
ハッシュ値の距離 = 13, 位置情報のズレ = 0.27m
車両の位置的にも非常に近く、画像もかなり似ているように見えますが、よく見ると若干向きが違いますね。ハッシュ値の距離は 13 と結構大きいです。
以上、有名どころの3か所のコーナーで試してみましたが、大体近い位置は特定できるようです。
その他、ランダムに選択した10か所のシーンで試してみましたが、以下のようになりました。
- 正しい位置のみがヒット：6件
- 正しい位置と誤った位置の両方がヒット：1件
- 誤った位置のみヒット：3件
誤った位置のみヒットしたケースを1件だけ以下に示します。
| 検索に用いた画像 | ヒットした画像 | |
|---|---|---|
| 画像 |  |
 |
| ハッシュ値 | b7b630b24c1e1f1e | b7b43839481e3f1f |
| 位置情報 | (1439.61, -18.69) | (2059.41, 37.44) |
ハッシュ値の距離 = 9, 位置情報のズレ = 622.34m
左右の木の生い茂り方やコースの先が左カーブ or ストレートと結構違いがあるように見えるのですが、ハッシュ値の距離は 9 と比較的近いです。
ちなみに、本来ヒットしてほしい画像は以下です。
| 検索に用いた画像 | ヒットした画像 |
|---|---|
|
 |
ハッシュ値の差 = 13
ぱっと見は似た画像ですが、よく見るとずれており、その結果比較的大きい差になっているのかなと思います。
4. さいごに
本記事では、レースゲームのシーンをdHashで類似画像検索してみました。
有名どころのコーナーなど特徴的なシーンに関しては比較的精度は良いのですが、ランダムにシーンを選んでみると勝率7割といったところでした（確かめた件数が10件と少ない点は許してください）。
しっかりとした解釈ではなく、個人的な感想としては以下の感じです。
- dHashはハッシュ値の距離が10以下だと同じ画像と見做すそうですが、今回ではかなり似た画像でも8-15程度の距離が出ており、判断のしきい値は検討が必要かな。
- 人が見ると違う画像でも、8-10ぐらいの距離になっていることもあり、false-positive が少ないとは言い切れないような。（これは「人が見て違う」が人によって異なりそうな気もするので何とも言えないですが）
精度を向上させたいなら、以下のような方策も考えらるのではないかと思います。
- 一番近い画像だけではなく、ある程度近い範囲の画像を確認する。
- 検索する際に1シーンだけではなく前後のシーンも含めて検索する