dHash という画像検索用のアルゴリズムがある。
画像をグレースケール化して 9x8 のサイズにリサンプルし、隣合わせのピクセル同士を比較して増減に応じて 0 か 1 の値を設定して画像を 64bit 値にするというものだ。画像の検索には Binary Search Tree (２分探索木) を使って、3 bit 程度の誤差なら許容するような形で検索する。
※ グレースケール化やリサンプルのアルゴリズム、増減に応じて 0/1付与の方式によって dHash値の互換性が無くなるので長期の利用の際には互換性の維持については要注意である。
ただし Binary Search Tree を構築するのには時間と手間がかかるし、頻繁に検索するには Binary Search Tree のデータをメモリ上に長期間保持する必要があるので運用が面倒である。
そこで MySQL で Binary Search Tree を用いずに単純検索をしてみるとした場合、どうなるかを確認してみた。
MySQL には BIT(n) 型というのがあって、最大 64bit までの値を格納できる。今回はSIGNED/UNSIGNED関係にまったく気を配りたくないのでdhash値はBIT型にした。
※尚、UPDATE images SET dhash_bits = UNHEX(dhash); 等で16進文字列からBITへの変換は容易にできる。
一言でまとめると、MySQL には BITの立っている数を数える BIT_COUNT() 関数があるので単純に dhash同士でBITWISE XORしたものの立ちBIT数を数えれば良いようだ。
SELECT HEX(dhash_bits), BIT_COUNT(dhash_bits ^ b'1111000111110000111000100100000001100100010011001101001011111001') AS SCORE FROM images WHERE dhash_bits IS NOT NULL AND BIT_COUNT(dhash_bits ^ b'1111000111110000111000100100000001100100010011001101001011111001') <= 3 ORDER BY BIT_COUNT(dhash_bits ^ b'1111000111110000111000100100000001100100010011001101001011111001') ASC
※ 当然だが Binary Search Treeでは無いので大容量検索の場合は効率が悪くなる。
