「Fingerprinting Images for Near-Duplicate Detection」な Python

「Python」を冠しているのは単にやりやすさだけの理由よ。

「加工やらなんやらで同じような画像を大量に持っててやぁねぇ」状態に対する整理のソリューション、な。自分の作業起因ではなくてな、親族の PC・スマホからほじくりだした画像をかき集めてみたらこんなことになってて、どうしたもんかと。ファイル名と EXIF タグで情報を拾えるものはまだ良いのだが、何やらそのデバイスの機能だの何かしらアプリの機能だので何かしらの加工をしたような「いろんなバリエーション」(サイズと RGB/ARGB、とか)が、ファイル名での何の主張もなくごちゃごちゃと。デバイスやアプリによる連番のようで、ほんとに何者なのか、開いてみないとわからんのね。

こういうニーズに対する解を「フィンガープリント」という呼び方で考えるというのは今回調べて初めて知ったけれど、調べる前に自力でやるとしたらどうだろうなぁと想像してた通りのものたちだった。どこいっても「セキュリティ目的のハッシュと違って、違っても似たものなら似たダイジェストるんだぜぃ」みたいな説明なのだが、いやぁ、そういう難しいこというよりはさ、要は「ざっくりいえば概ね黒」みたいな要約が出来ればそれでいい、てことだぞ、考え方自体が難しいはずはないわな、と思ってたが、その通りだった。

要求精度等々でバリエーション個々のアルゴリズムが多少難しいことになるのはそうだが、基本的な発想が至極簡単なものであることは、以下サイトを(読まずとも)眺めれば多分わかるハズ:

考え方のポイントは、「要約も結局は画像のように考えればよい(2D配列)」てことで、ゆえに、「凄まじく似た画像は同じダイジェストになる」の一歩先の、「凄まじいというほどでもない似た画像は似たダイジェストになる」は、なんのことはない、「似てる度=2D配列の差」てこと。

Python で弄ぶつもりならば imagehash がそのまま目的のもの:

imagehash パッケージそのものはかなり簡単な作りになってるので、読めばすぐに理解出来るはず。ウェーブレット変換を利用するとことかは scipy とか使ってるんで、実際の中身は見かけよりは結構複雑だけれど。

とりあえず、今日のオレ、のためにサクっと:

imgfp2dot.py
 1 # -*- coding: utf-8 -*-
 2 import os
 3 from PIL import Image
 4 import imagehash
 5 from glob import iglob
 6 from collections import defaultdict
 7 import numpy as np
 8 from itertools import combinations
 9 
10 
11 #def _binary_array_to_hex(arr):
12 #    """
13 #    internal function to make a hex string out of a binary array.
14 #    """
15 #    bit_string = ''.join(str(b) for b in 1 * arr.flatten())
16 #    width = int(numpy.ceil(len(bit_string) / 4))
17 #    return '{:0>{width}x}'.format(int(bit_string, 2), width=width)
18 
19 
20 #def _harrreduce(h):
21 #    return np.array([sum((b * (2**k) for k, b in enumerate(row))) for row in (1 * h.hash)])
22 
23 
24 if __name__ == '__main__':
25     hm = defaultdict(list)
26     pat = "*.jpg"
27     for fn in iglob(pat):
28         im = Image.open(fn)
29         h = imagehash.phash(im)
30         hm[h].append(fn)
31         #hm[h].append((im.size[0] * im.size[1], h2, fn))
32         #print(_binary_array_to_hex(h.hash))
33         #print(_harrreduce(h))
34         #print(np.array([sum((b * (2**k) for k, b in enumerate(row))) for row in (1 * h.hash)]))
35     print("graph g {")
36     print("    node [shape=plaintext];")
37     for h, files in hm.items():
38         print('    "{}" [label=<<TABLE BORDER="1" CELLBORDER="0">{}</TABLE>>];'.format(
39             h, "".join(
40                 ['<TR><TD BGCOLOR="#eeeeee">{}</TD></TR>'.format(h)] + \
41                 ['<TR><TD FIXEDSIZE="TRUE" WIDTH="180" HEIGHT="180"><IMG SRC="{}"/></TD></TR>'.format(f) for f in files])))
42     print("")
43     for h1, h2 in combinations(hm.keys(), 2):
44         w = h1 - h2
45         if w:
46             w = 1.0 / w
47         #if w > 1./10:
48         #    c = "color=black"
49         #elif w > 1./15:
50         #    c = 'color="#333333"'
51         #elif w > 1./20:
52         #    c = 'color="#777777"'
53         #elif w > 1./30:
54         #    c = 'color="#aaaaaa"'
55         #else:
56         #    c = 'color="#eeeeee"'
57         c = 'color="none"'
58         print('    "{}" -- "{}" [weight={}, {}]'.format(h1, h2, w, c))
59     #    #print(h1, h2, h1 - h2, np.sum(np.abs(1 * h1.hash - 1 * h2.hash)))
60     #    print(h1, h2, h1 - h2, hm[h1] + hm[h2])
61     print("}")

色々コメントアウトして残してある部分は、これは試行錯誤というよりは、「こういうことだよね?」を確証していった形跡。最終的に、二つの「hash」の差が目的のものであることを確認するために「np.sum(np.abs(1 * h1.hash - 1 * h2.hash))」を計算してダンプしてみたりしてる。

このスクリプトは Graphviz で画像化するための dot を吐き出すので…:

いつものとおり、「py」は Windows 専用の python ランチャね。
1 [me@host: ~]$ py -3 imgfp2dot.py > fp.dot
2 [me@host: ~]$ dot fp.dot -Kosage -Tsvg > fp.svg

レンダリングエンジンは osage しか使い物にならない、ある程度のファイル数があると。

処理結果を見せたいところなんだけれど、今やってみたのは非常にプライベートな写真なので、見せない。でもサイズだけ違うみたいなのは同じハッシュになり、微妙に違うが似てるものは近い位置に配置されて、まぁかなり目的のものにはなってくれた。興味があるなら、ご自身で是非お試してみ。