More than 5 years have passed since last update.

同一画像を判定するためのハッシュ化アルゴリズム

Last updated at 2020-11-02Posted at 2019-11-18

はじめに

インターネット上から収集した画像をもとに機械学習のデータセットを作成するとき、重複した画像の削除が必要です。訓練データに重複した画像があるならまだ良いですが、訓練データ・テストデータの間で重複した画像があると、いわゆるleakageが起きてしまいます。

画像の重複を検出する方法として最も単純なものは、MD5などのファイルのハッシュ値を利用することです。しかしながら、ファイルのハッシュ値は、あくまでも画像ファイルのバイナリ列をハッシュ化したものであり、同じ画像でも保存形式や圧縮パラメータを変えただけでも変化してしまい、検出漏れにつながります。

そこで本記事では、画像の特徴そのものをハッシュ化するアルゴリズムを紹介するとともに、簡単な実験を通してそれらハッシュ化アルゴリズムの特性を見ていきます。

画像のハッシュ化アルゴリズム

Average Hash (aHash)

画像の特徴（輝度パターン）をもとにしたハッシュ値で、素朴なアルゴリズムで計算できます。具体的な手順は以下の通りです。

画像を8x8 pixels に縮小する。
さらにグレースケールに変換する。
画素値の平均を求める。
8x8 pixels の各画素に対し、平均値よりも高いか低いかで2値化 (0 or 1) する。
2値のシーケンスについて、ラスタスキャン順など何らかの順で一列にし、64bitのハッシュを得る。

aHashには、アルゴリズムが簡単でかつ計算が速いという長所があります。一方で、柔軟性に欠ける欠点もあります。例えば、ガンマ補正した画像のハッシュ値は、元の画像と距離が遠くなってしまいます。

Perseptual Hash (pHash)

aHashは画素値そのものを使いましたが、pHashでは画像の離散コサイン変換 (DCT) を使います。DCTは、画像などの信号を周波数領域に変換する方法のひとつで、例えばJPEGの圧縮に利用されています。JPEG圧縮では、画像をDCTし、人間が知覚しやすい低周波数成分のみを取り出すことで、データ量を削減しています。

JPGE圧縮と同様に、pHashでも画像のDCTにおける低周波数成分に着目し、それらをハッシュ化します。こうすることで、人間が知覚しやすい特徴を優先して抽出することができ、また画像の平行移動や輝度変化に対してロバストなハッシュ化ができると考えられます。

画像を縮小する。8x8よりも大きいサイズにする（例えば32x32など）。
グレースケール化する。
DCTする。
低周波数成分の8x8だけを取り出す。
直流成分を除いた低周波数成分の平均値を算出する。
平均値よりも高いか低いかで2値化する。
ラスタスキャン順など何らかの順で一列にし、64bitのハッシュを得る。

その他のxHash

aHash, pHashの他にも、さまざまなバリエーションがあるようです。ベンチマークをしてくれている人もいます¹。

実験

画像に対してさまざまな処理を加え、元画像とのハッシュ値を比較してみます。ハッシュ値として、aHash, pHashをそれぞれ計算します。

また、ResNet50の最終層の直前の層について、出力をハッシュとみなす、という手法も試してみます。この手法はある論文²で採用されていた方法です³。

コード

aHashおよびpHashの計算にはOpenCVを使っていますが、ImageHashというライブラリもあるそうです。また、aHashおよびpHashでは、ハッシュ値の比較にハミング距離が使えます。値域は [0, 64] です。この値域に合わせるため、ResNet50を利用したハッシュ（もどき）の比較では、コサイン類似度を計算した後に前述の値域へ変換しています。

import copy
import pprint

import cv2.cv2 as cv2
import numpy as np
from keras import models
from keras.applications.resnet50 import ResNet50, preprocess_input
from sklearn.metrics.pairwise import cosine_similarity


class ImagePairGenerator(object):
    """
    実験用の画像ペアを生成するクラス
    """

    def __init__(self, img: np.ndarray):
        self._img = img
        self._processings = self._prepare_processings()

    def _prepare_processings(self):
        h, w, _ = self._img.shape
        # lenna画像の顔のあたりを切り抜くための位置とサイズ
        org = np.array([128, 128])
        size = np.array([256, 256])
        # kind (processing description), img1, img2
        processings = [
            ('同一',
             lambda x: x,
             lambda x: x),
            ('グレースケール化',
             lambda x: x,
             lambda x: cv2.cvtColor(
                 cv2.cvtColor(x, cv2.COLOR_BGR2GRAY), cv2.COLOR_GRAY2BGR)),
            *list(map(lambda s:
                      (f'1/{s:2}に縮小',
                       lambda x: x,
                       lambda x: cv2.resize(x, (w // s, h // s))),
                      np.power(2, range(1, 5)))),
            *list(map(lambda s:
                      (f'平滑化 (kernel size = {s:2}',
                       lambda x: x,
                       lambda x: cv2.blur(x, (s, s))),
                      [3, 5, 7, 9, 11])),
            *list(map(lambda s:
                      (f'テキスト挿入 (fontScale = {s})',
                       lambda x: x,
                       lambda x: cv2.putText(x, 'Text', org=(10, 30*s),
                                             fontFace=cv2.FONT_HERSHEY_SIMPLEX,
                                             fontScale=s,
                                             color=(255, 255, 255),
                                             thickness=3*s,
                                             lineType=cv2.LINE_AA)),
                      range(1, 8))),
            *list(map(lambda q:
                      (f'JPEG圧縮 (quality = {q})',
                       lambda x: x,
                       lambda x: img_encode_decode(x, q)),
                      range(10, 100, 10))),
            *list(map(lambda gamma:
                      (f'ガンマ補正 (gamma = {gamma})',
                       lambda x: x,
                       lambda x: img_gamma(x, gamma)),
                      [0.2, 0.5, 0.8, 1.2, 1.5, 2.0])),
            *list(map(lambda d:
                      (f'平行移動 ({d:2} pixels)',
                       lambda x: img_crop(x, org, size),
                       lambda x: img_crop(x, org + d, size)),
                      np.power(2, range(7)))),
        ]
        return processings

    def __iter__(self):
        for kind, p1, p2 in self._processings:
            yield (kind,
                   p1(copy.deepcopy(self._img)),
                   p2(copy.deepcopy(self._img)))


class ResNet50Hasher(object):
    """
    ResNet50の最終層をハッシュ値として出力するためのクラス
    """
    _input_size = 224

    def __init__(self):
        self._model = self._prepare_model()

    def _prepare_model(self):
        resnet50 = ResNet50(include_top=False, weights='imagenet',
                            input_shape=(self._input_size, self._input_size, 3),
                            pooling='avg')
        model = models.Sequential()
        model.add(resnet50)
        return model

    def compute(self, img: np.ndarray) -> np.ndarray:
        img_arr = np.array([
            cv2.resize(img, (self._input_size, self._input_size))
        ])
        img_arr = preprocess_input(img_arr)
        embeddings = self._model.predict(img_arr)
        return embeddings

    @staticmethod
    def compare(x1: np.ndarray, x2: np.ndarray):
        """
        コサイン類似度を計算する。値域は [0, 1]。
        aHashおよびpHashを比較するハミング距離に合わせて、
        [0, 64] の値域に変換する。
        """
        cs = cosine_similarity(x1, x2)
        distance = 64 + (0 - 64) * ((cs - 0) / (1 - 0))
        return distance.ravel()[0]  # np.array -> float


def img_crop(img: np.ndarray, org: np.ndarray, size: np.ndarray) -> np.ndarray:
    """
    画像から任意の領域を切り抜く。
    """
    y, x = org
    h, w = size
    return img[y:y + h, x:x + w, :]


def img_encode_decode(img: np.ndarray, quality=90) -> np.ndarray:
    """
    Jpeg圧縮の劣化を再現する。
    参考：https://qiita.com/ka10ryu1/items/5fed6b4c8f29163d0d65
    """
    encode_param = [int(cv2.IMWRITE_JPEG_QUALITY), quality]
    _, enc_img = cv2.imencode('.jpg', img, encode_param)
    dec_img = cv2.imdecode(enc_img, cv2.IMREAD_COLOR)
    return dec_img


def img_gamma(img: np.ndarray, gamma=0.5) -> np.ndarray:
    """
    ガンマ補正する。
    参考：https://www.dogrow.net/python/blog99/
    """
    lut = np.empty((1, 256), np.uint8)
    for i in range(256):
        lut[0, i] = np.clip(pow(i / 255.0, gamma) * 255.0, 0, 255)

    return cv2.LUT(img, lut)


def image_hashing_test():
    image_path = 'resources/lena_std.tif'
    img = cv2.imread(image_path, cv2.IMREAD_COLOR)
    h, w, _ = img.shape

    hashers = [
        ('aHash', cv2.img_hash.AverageHash_create()),
        ('pHash', cv2.img_hash.PHash_create()),
        ('ResNet', ResNet50Hasher())
    ]

    pairs = ImagePairGenerator(img)

    result_dict = {}
    for pair_kind, img1, img2 in pairs:
        result_dict[pair_kind] = {}
        for hasher_kind, hasher in hashers:
            hash1 = hasher.compute(img1)
            hash2 = hasher.compute(img2)
            distance = hasher.compare(hash1, hash2)
            result_dict[pair_kind][hasher_kind] = distance
        # 画像を目視で確認（shapeが同じときだけ。揃えるのが面倒なので）
        if img1.shape == img2.shape:
            window_name = pair_kind
            cv2.imshow(window_name, cv2.hconcat((img1, img2)))
            cv2.waitKey()
            cv2.destroyWindow(window_name)

    pprint.pprint(result_dict)


if __name__ == '__main__':
    image_hashing_test()

結果

{'同一': {'ResNet': 0.0, 'aHash': 0.0, 'pHash': 0.0},
 'グレースケール化': {'ResNet': 14.379967, 'aHash': 0.0, 'pHash': 0.0},
 '1/ 2に縮小': {'ResNet': 1.2773285, 'aHash': 3.0,  'pHash': 1.0},
 '1/ 4に縮小': {'ResNet': 6.5748253, 'aHash': 4.0,  'pHash': 1.0},
 '1/ 8に縮小': {'ResNet': 18.959282, 'aHash': 7.0,  'pHash': 3.0},
 '1/16に縮小': {'ResNet': 34.8299,   'aHash': 12.0, 'pHash': 0.0},
 'JPEG圧縮 (quality = 10)': {'ResNet': 6.4169083,  'aHash': 2.0, 'pHash': 0.0},
 'JPEG圧縮 (quality = 20)': {'ResNet': 2.6065674,  'aHash': 1.0, 'pHash': 0.0},
 'JPEG圧縮 (quality = 30)': {'ResNet': 1.8446579,  'aHash': 0.0, 'pHash': 0.0},
 'JPEG圧縮 (quality = 40)': {'ResNet': 1.2492218,  'aHash': 0.0, 'pHash': 1.0},
 'JPEG圧縮 (quality = 50)': {'ResNet': 1.0534592,  'aHash': 0.0, 'pHash': 0.0},
 'JPEG圧縮 (quality = 60)': {'ResNet': 0.99293137, 'aHash': 0.0, 'pHash': 0.0},
 'JPEG圧縮 (quality = 70)': {'ResNet': 0.7313309,  'aHash': 0.0, 'pHash': 0.0},
 'JPEG圧縮 (quality = 80)': {'ResNet': 0.58068085, 'aHash': 0.0, 'pHash': 0.0},
 'JPEG圧縮 (quality = 90)': {'ResNet': 0.354187,   'aHash': 0.0, 'pHash': 0.0},
 'ガンマ補正 (gamma = 0.2)': {'ResNet': 16.319721,  'aHash': 2.0, 'pHash': 1.0},
 'ガンマ補正 (gamma = 0.5)': {'ResNet': 4.2003975,  'aHash': 2.0, 'pHash': 0.0},
 'ガンマ補正 (gamma = 0.8)': {'ResNet': 0.48334503, 'aHash': 0.0, 'pHash': 0.0},
 'ガンマ補正 (gamma = 1.2)': {'ResNet': 0.381176,   'aHash': 0.0, 'pHash': 1.0},
 'ガンマ補正 (gamma = 1.5)': {'ResNet': 1.7187691,  'aHash': 2.0, 'pHash': 1.0},
 'ガンマ補正 (gamma = 2.0)': {'ResNet': 4.074257,   'aHash': 6.0, 'pHash': 2.0},
 'テキスト挿入 (fontScale = 1)': {'ResNet': 0.7838249, 'aHash': 0.0, 'pHash': 0.0},
 'テキスト挿入 (fontScale = 2)': {'ResNet': 1.0911484, 'aHash': 0.0, 'pHash': 1.0},
 'テキスト挿入 (fontScale = 3)': {'ResNet': 2.7721176, 'aHash': 0.0, 'pHash': 2.0},
 'テキスト挿入 (fontScale = 4)': {'ResNet': 4.646305,  'aHash': 0.0, 'pHash': 4.0},
 'テキスト挿入 (fontScale = 5)': {'ResNet': 8.435852,  'aHash': 2.0, 'pHash': 3.0},
 'テキスト挿入 (fontScale = 6)': {'ResNet': 11.267036, 'aHash': 6.0, 'pHash': 3.0},
 'テキスト挿入 (fontScale = 7)': {'ResNet': 15.272251, 'aHash': 2.0, 'pHash': 7.0},
 '平滑化 (kernel size =  3': {'ResNet': 1.3798943, 'aHash': 2.0, 'pHash': 0.0},
 '平滑化 (kernel size =  5': {'ResNet': 3.1528091, 'aHash': 4.0, 'pHash': 1.0},
 '平滑化 (kernel size =  7': {'ResNet': 4.903698,  'aHash': 4.0, 'pHash': 1.0},
 '平滑化 (kernel size =  9': {'ResNet': 6.8400574, 'aHash': 4.0, 'pHash': 1.0},
 '平滑化 (kernel size = 11': {'ResNet': 9.477722,  'aHash': 5.0, 'pHash': 2.0},
 '平行移動 ( 1 pixels)': {'ResNet': 0.47764206, 'aHash': 6.0,  'pHash': 0.0},
 '平行移動 ( 2 pixels)': {'ResNet': 0.98942566, 'aHash': 10.0, 'pHash': 3.0},
 '平行移動 ( 4 pixels)': {'ResNet': 1.475399,   'aHash': 15.0, 'pHash': 5.0},
 '平行移動 ( 8 pixels)': {'ResNet': 2.587471,   'aHash': 20.0, 'pHash': 13.0},
 '平行移動 (16 pixels)': {'ResNet': 3.1883087,  'aHash': 25.0, 'pHash': 21.0},
 '平行移動 (32 pixels)': {'ResNet': 4.8445663,  'aHash': 23.0, 'pHash': 31.0},
 '平行移動 (64 pixels)': {'ResNet': 9.34531,    'aHash': 28.0, 'pHash': 30.0}}

※実際に得られた出力に対し、可視性向上のため順序の入れ替えとインデントの調整をしています。

考察

ResNetはあくまでもImageNetで事前学習されたものをそのまま使っていることに注意してください。すなわち、学習データを用意することによって、以下で述べられているものとは異なる特性を持ったネットワークを獲得することもできると考えられます。

また、画像によっても傾向が変わる可能性もあります。実用するなら、ある程度ちゃんとしたデータセットで評価するのがいいでしょう。

同一：当たり前ですが、どのハッシュ方法でも距離が0になっています。
グレースケール化：aHashやpHashでは処理の最初でグレースケール化するため、元画像との距離が0になっています。
縮小：ResNetやaHashでは、スケールに対応して距離が離れていきますが、pHashは比較的ロバストです。
JPEG圧縮：ResNetでは圧縮率に比例しているように見えるのが興味深いです。対してaHashやpHashは比較的ロバストです。単純なハッシュ化のアルゴリズム（平均値に対する高低でのエンコード）が、圧縮による劣化に対してもロバストなのかもしれません。
ガンマ補正：ResNetと比較すると、aHashやpHashの方が比較的ロバストなようです。
テキスト挿入：aHashが比較的ロバストなようです。挿入されたテキストの色に合わせて、画像内の画素値の平均が変化し、エンコード結果が変わっていないことが考えられます。対してpHashやResNetではテキストの大きさに伴って距離が開いています。
平滑化：pHashが比較的ロバストです。これは、低周波数成分のみに着目しているためでしょう。
平行移動：どのハッシュも、平行移動量に伴って距離が離れていきます。ResNetが比較的ロバストでしょうか。

まとめ

画像をハッシュ化する手法を紹介しました。加えて、いくつかの処理を加えた画像と元画像との距離を測定し、各ハッシュ化手法の特性を観察しました。本記事で比較したアルゴリズムの中では、pHashが、画像のスケーリング、圧縮による劣化、平滑化に対してロバストである傾向が観察できました。

私はxHash系のアルゴリズムを最近知ったのですが、シンプルでかついいアイデアに基づくアルゴリズムであると思います。比較的枯れたアルゴリズムではあると思いますが、適材適所で使いこなせるようになるといいですね。

参考

Looks Like It - The Hacker Factor Blog
http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html
perceptual hash(phash)を利用して画像比較をしてみる
http://hideack.hatenablog.com/entry/2015/03/16/194336
OpenCV: The module brings implementations of different image hashing algorithms.
https://docs.opencv.org/4.5.0/d4/d93/group__img__hash.html
OpenCVに実装されているハッシュ化アルゴリズムについては、パフォーマンスチャートが公開されています。

C. Zauner, "Implementation and Benchmarking of Perceptual Image Hash Functions," Upper Austria University of Applied Sciences, Hagenberg Campus, 2010. ↩
Recipe1M+: A Dataset for Learning Cross-Modal Embeddings for Cooking Recipes and Food Images - MIT ↩
実を言うと、この論文を読んでいたときに「もっと簡単に重複を見分ける方法があるのでは？」と思い立ったのが、本記事を書くきっかけでした ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Why not login to Qiita and try out its useful features?

同一画像を判定するためのハッシュ化アルゴリズム

はじめに

画像のハッシュ化アルゴリズム

Average Hash (aHash)

Perseptual Hash (pHash)

その他のxHash

実験

コード

結果

考察

まとめ

参考

@mamo3gr

Today's trending articles

「Googleでの14年間で学んだ21の教訓」を個人的な解釈でまとめてみた

Obsidian の個人的に便利だと思う使い方

年間500万円以上のコスト削減を実現したのに、どこかむなしいのはなぜか

資格懐疑派がAWS SAP取得を目指したきっかけと学習法

お名前.comの罠にハマった私が、AIを「超絶クレーマー」に改造した話

Comments

Being held Article posting campaign

2026年!初アウトプットをしよう

Login to continue?

Login or Sign up with social account

Login or Sign up with your email address

Why not login to Qiita and try out its useful features?

同一画像を判定するためのハッシュ化アルゴリズム

はじめに

画像のハッシュ化アルゴリズム

Average Hash (aHash)

Perseptual Hash (pHash)

その他のxHash

実験

コード

結果

考察

まとめ

参考

@mamo3gr

Today's trending articles

「Googleでの14年間で学んだ21の教訓」を 個人的な解釈でまとめてみた

Obsidian の個人的に便利だと思う使い方

年間500万円以上のコスト削減を実現したのに、どこかむなしいのはなぜか

資格懐疑派がAWS SAP取得を目指したきっかけと学習法

お名前.comの罠にハマった私が、AIを「超絶クレーマー」に改造した話

Comments

Being held Article posting campaign

2026年!初アウトプットをしよう

「Googleでの14年間で学んだ21の教訓」を個人的な解釈でまとめてみた