ハッシュ値で画像の類似度を判定する

# 概要
2つの画像のハッシュ値をそれぞれ求め、ハッシュ値間の類似度を求めます。
完全に一致しているかどうか、ではなく類似度が分かるので、しきい値を適切に設定するとあいまいな画像一致判定ができます。
本稿はC#を前提として記述していますが、使用しているアルゴリズムは他の言語でも実装があるようなので、一定の参考になると思います。

# 前提
前述のとおり本稿はC#を前提として記述しています。
このアルゴリズムを使うには、CoenM.ImageSharp.ImageHashをNuGetでインストールし、以下のnamespaceを追加してください。

```
using CoenM.ImageHash;
using CoenM.ImageHash.HashAlgorithms;
using SixLabors.ImageSharp;
using SixLabors.ImageSharp.PixelFormats;
```

# ライブラリ
- CoenM.ImageSharp.ImageHash [GitHub](https://github.com/coenm/ImageHash) [NuGet](https://www.nuget.org/packages/CoenM.ImageSharp.ImageHash)

# ハッシュ値を求めるアルゴリズム
CoenM.ImageSharp.ImageHashでは、pHash(Perceptual Hash)、aHash(Average Hash)、dHash(Difference Hash)の3つのアルゴリズムを使用できます。

pHashとaHashは以下の記事に詳しいです。
[同一画像を判定するためのハッシュ化アルゴリズム](https://qiita.com/mamo3gr/items/b93545a0346d8731f03c)

以下は、pHashとaHashの開発者である[Dr.Neal Krawetz氏のブログのエントリ](http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html)から各アルゴリズムの評価を意訳したものです。

- pHashは遅いが、正確性では最高のパフォーマンスを発揮する。
- aHashは高速だが、正確性に欠ける。一致すべき画像の取りこぼしは少ないが、一致すべきでない画像と一致するケースが多い。
- dHashはaHashと同等の速度で、正確性もかなり高い。

※ブログのコメントに「pHash別に遅くないじゃん。二次元のDCTをO(n^4)でやってるから遅い。O(n^3)でやればpHashも全然速いじゃん。」みたいな指摘がありますが、CoenM.ImageSharp.ImageHashがどっちなのかは分かりません…。

# 画像のハッシュ値を求める
この画像のハッシュ値を求めます。(©いらすとや)
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)

### コード
```
    // 画像の読み込み
    Image<Rgba32> image = Image.Load<Rgba32>(@"neko_kaburu_man.png");
    // ハッシュアルゴリズムのインスタンス化(この例ではpHash)
    IImageHash pHashArgorithm = new PerceptualHash();
    // ハッシュ値を求める
    ulong pHash = pHashArgorithm.Hash(image);
    // 出力
    Console.WriteLine($"pHash = {pHash}");
```

### 実行結果
```
pHash = 10402329587663758416
```

pHashがPerceptual Hashでのハッシュ値です。
CoenM.ImageSharp.ImageHashではulongですが、アルゴリズム本来の意味では64bitのハッシュが求まります。

# 画像間の類似度を求める
この2つの画像のハッシュ値それぞれを求め、類似度を求めます。
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)![neko_kaburu_woman.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/b8cbd04a-1af6-6bf1-cac8-efca8b2a04ca.png)

### コード
```
    // 画像の読み込み
    Image<Rgba32> image1 = Image.Load<Rgba32>(@"neko_kaburu_man.png");
    Image<Rgba32> image2 = Image.Load<Rgba32>(@"neko_kaburu_woman.png");

    // ハッシュアルゴリズムのインスタンス化(この例ではpHash)
    IImageHash pHashArgorithm　= new PerceptualHash();

    // ハッシュを求める
    ulong pHash1 = pHashArgorithm.Hash(image1);
    ulong pHash2 = pHashArgorithm.Hash(image2);

    // ハッシュ値間の類似度を求める
    double pHashSimilarity = CompareHash.Similarity(pHash1 , pHash2);

    // 出力
    Console.WriteLine($"pHash1 = {pHash1}");
    Console.WriteLine($"pHash2 = {pHash2}");
    Console.WriteLine($"pHashSimilarity = {pHashSimilarity}");
```

### 実行結果
```
pHash1 = 10402329587663758416
pHash2 = 10401203732853990480
pHashSimilarity = 90.625
```

pHash1が左の画像のハッシュ値、pHash2が右の画像のハッシュ値です。
pHashSimilarityが類似度です。
類似度について詳しくは後述します。

# いろんなアルゴリズムでハッシュ値を求める

### コード
```
    // 画像の読み込み
    Image<Rgba32> image = Image.Load<Rgba32>(@"neko_kaburu_man.png");
    // ハッシュアルゴリズムのインスタンス化
    IImageHash pHashArgorithm = new PerceptualHash();
    IImageHash aHashArgorithm = new AverageHash();
    IImageHash dHashArgorithm = new DifferenceHash();
    // ハッシュ値を求める
    ulong pHash = pHashArgorithm.Hash(image);
    ulong aHash = aHashArgorithm.Hash(image);
    ulong dHash = dHashArgorithm.Hash(image);
    // 出力
    Console.WriteLine($"pHash = {pHash}");
    Console.WriteLine($"aHash = {aHash}");
    Console.WriteLine($"dHash = {dHash}");
```

### 実行結果

```
pHash = 10402329587663758416
aHash = 11590717229577021695
dHash = 5958916077812472516
```

pHash、aHash、dHashともに使い方は同じです。
ハッシュアルゴリズムをインスタンス化する際に使いたいアルゴリズムを選んでください。

# アルゴリズムごとの類似度サンプル(以下コード省略)
いろんなケースでアルゴリズムごとに類似度を求めてみます。
類似度は100で完全一致です。
一致と判断するのはおおむね90台後半にしたほうがいいです。

## 一部だけ異なる画像の比較
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)![neko_kaburu_woman.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/b8cbd04a-1af6-6bf1-cac8-efca8b2a04ca.png)

### 実行結果
```
pHashSimilarity = 90.625
aHashSimilarity = 67.1875
dHashSimilarity = 92.1875
```
異なる部分が小さければある程度類似画像とみなしてくれます。
が、しきい値を下げすぎることはお勧めしません。
この例で一致と判断したいのであれば、異なっていない箇所だけ切り出して比較したほうがいいです。
(異なっている箇所が分かる場合だけですが)

## 異なる画像の比較
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)![pose_dance_ukareru_woman.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/8bdec8eb-de44-1e23-8069-853a888e1814.png)

### 実行結果
```
pHashSimilarity = 50
aHashSimilarity = 59.375
dHashSimilarity = 54.6875
```
全然違う画像と比較した場合の類似度は50前後です。
類似度0は全く逆の画像(aHashならネガポジ反転とか)なので、ある意味元の画像と近いです。

## リサイズされた画像の比較
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)![neko_kaburu_man_resized.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/2d22d8a0-6475-a1b9-3f10-8812b5c4b11f.png)

### 実行結果
```
pHashSimilarity = 100
aHashSimilarity = 100
dHashSimilarity = 100
```
これらのアルゴリズムは、同じサイズに縮小してからハッシュ値を求めるというものなので、リサイズされた画像やアスペクト比が異なる画像との比較もできます。

## ウォーターマークありなしの比較
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)![neko_kaburu_man_watermarked.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/2f62939d-6fa6-5869-66c4-1120ca2e76aa.png)

### 実行結果
```
pHashSimilarity = 96.875
aHashSimilarity = 62.5
dHashSimilarity = 90.625
```
ウォーターマークありなしもある程度類似画像とみなしてくれます。
aHashは類似度が低いですね。

## 圧縮ノイズで劣化した画像との比較
![neko_kaburu_man_good.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/15c47344-6428-ccbc-a96e-9106babee6d6.jpeg)![neko_kaburu_man_bad.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/df8a74a3-3d0b-50ad-d430-ac9adad835d4.jpeg)

### 実行結果
```
pHashSimilarity = 96.875
aHashSimilarity = 100
dHashSimilarity = 100
```
圧縮ノイズがあっても類似画像とみなしてくれます。

## 一部切り出した画像との比較
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)![neko_kaburu_man_cropped.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/1d5aeffd-5781-7bc0-5415-6095182ac9e8.png)

### 実行結果
```
pHashSimilarity = 53.125
aHashSimilarity = 70.3125
dHashSimilarity = 59.375
```
一部切り出した画像は基本的に異なる画像とみなされます。
アルゴリズムによって多少異なりますが、ハッシュ値は縦横8x8といった、ごく画像にリサイズしてから計算します。
一部切り出されていると縮小した際に全く異なった結果になるため、類似度が低くなります。
余白が広くなっていたり狭くなっていたりしても同様です。

## 色味が補正された画像の比較
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)![neko_kaburu_man_retoned.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/422a7549-2c2f-1789-05a5-dcaaa77fe5e3.png)

### 実行結果
```
pHashSimilarity = 96.875
aHashSimilarity = 82.8125
dHashSimilarity = 93.75
```

程度によりますが、色味が補正されていても類似画像とみなしてくれます。
これもaHashは類似度が低いですね。

## 人間の目にはよく似ているように見える画像の比較
![pose_dance_ukareru_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/667a8f89-d497-bedb-9ff6-4060d9ad4254.png)![pose_dance_ukareru_woman.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/8bdec8eb-de44-1e23-8069-853a888e1814.png)

### 実行結果
```
pHashSimilarity = 78.125
aHashSimilarity = 87.5
dHashSimilarity = 75
```

aHashは比較的高いように見えますが、類似度90未満は信用しないほうがいいです。
こういう画像の比較は機械学習等の手段を検討すべきです。

## 一見同じに見えるが、背景の透過率が異なっている画像の比較
![neko_kaburu_man.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/da520ae1-138a-48fb-31f7-75c05de613e6.png)![neko_kaburu_man_good.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/582560/f7cdcafe-9da3-5693-7744-fd2c7ff7fe26.jpeg)

### 実行結果
```
pHashSimilarity = 43.75
aHashSimilarity = 51.5625
dHashSimilarity = 46.875
```

左の画像はPNGで右の画像はJPEGです。
フォーマットの違いは重要ではありません。
左の画像は背景が透明で、右の画像は白色になっています。
CoenM.ImageHash.HashAlgorithmsでは透過度も含めてハッシュ値を求めているため、異なる画像とみなされます。
透過度を無視したければ、ハッシュ値を求める前に透過情報をなくしておく必要があります。

# 雑感
- サンプルのように、用途によって最適なアルゴリズムは異なります。正確性を重視したい場合はpHashがよさそうです。
- 今回は余白の多いイラストで試しましたが、写真などの余白がない(情報量が多い)画像であればもっと顕著な結果が出ます。
- どの類似度以上なら一致と判断するかどうかは実際に比較してチューニングが必要です。情報量が多く、ノイズが少ない画像であれば類似度98あたりをしきい値にするといいと思います。