TwitterのTLから二次元画像だけ収集しよう! (4)収集画像が被らないようにする

さて、このシリーズも後半に入ってきました。
ところで、ブログのテーマを変えてみたので記事が読みやすくなったと思うのですが、どうでしょうか?

で、ここで1つ訂正があります。
前回、次回はデータベースに情報を書き込んでいくと言っていましたが、間違えてました。
今回は画像の重複を無くす処理を書きます。予定を完全に間違えてました。
前回の記事はあのまま置いておきます。書き換えても良かったんですけどねw

ということで、いつものスクリプト配布ー

GitHub Gist – TL_capture_lbp_overlap.py

今回もGistには2つのファイルが入っています。どちらもダウンロードしてください。

で、image_hash.pyは前回のlbpcascade.py同様に名前を変更しないようにしてください。
TL_capture_lbp_overlap.pyに関しては変えても大丈夫です。というかファイル名が長すぎるので、前回のTL_capture_lbp.pyの中身に丸ごと置き換えてもらったほうがいいかもしれません。

では、動かしてみましょう。
いつものようにダウンロードしたファイルを配置して、start.batを起動して、python TL_capture_lbp_over.pyと叩きます。
ちなみにスクショで毎回フォルダーまで写しているのは配置しているファイルを確認してもらうためだったりします。ここまできちんとファイルを全て残していると同じような感じになっているはずです。

はい、見た目は何も変わりません。

 

ということで、動作確認が出来たので本体の変更点を見てみましょう。

クリックで元サイズの画像が表示されます。左が今回のTL_capture_lbp_overlap.py、右が前回のTL_capture_lbp.pyです。(前回の表示と入れ替わってしまいました、ごめんなさい)

まず、またimport文が増えています(10行目)。
今回追加してもらったimage_hash内にある関数を呼び出してます。

次にメソッド mkdirの変更点を先に見ます。

ここでは収集した画像のハッシュ値とURLを保存するリストが追加で定義されるようになりました(117~118行目)。
ここに書いてあることからも分かる通り、このリストは日付が変わるたびに初期化されます。

一番変更が多いon_statusの変更点を見ます。

まず、URLによる画像の重複確認を行うようになっています(74~76行目)。
先ほど定義した収集済み画像URLのリストにダウンロードしようとしている画像のURLが含まれているかどうかを確認しています。
このチェックは同一のツイートが流れてきた時のために行っています。重複確認では結構分かりやすい方法ですね。
ちなみにTPTS組んだときは何も考えていなかったため、画像ダウンロード後にMD5値を取って判定しています。画像のダウンロードは結構遅い処理なので、こっちの方が高速です。

次に画像のハッシュ値による重複確認を行っています(84~95行目)。
今回の一番の重要ポイントがここです。
ハッシュ値と言うとMD5やCRC32などが有名ですが、今回は全く異なるハッシュを使用しています。これに関する説明は後ほど行います。
まず、重複判定用のフラグを定義しています(84行目)。これは後ろでfor文を使っているのですが、画像をスキップするためにcontinueがそのままだと使えないので定義しています。
次に画像のハッシュ値をimage_hashの関数を呼び出して取得しています(85行目)。
次に取得したハッシュ値と取得済み画像のハッシュ値のリストを照らし合わせていきます(86~92行目)。ここの説明は後ほど行います。
最後にフラグをチェックして、重複していたらスキップします(93~95行目)。

最後に重複していない画像だった場合は画像のURLとハッシュ値をそれぞれのリストに追加しておきます(103~104行目)。

変更点は以上になります。

 

では、一番重要なハッシュ値による重複確認の説明に移ります。
正直、TPTSの中で一番力を入れた場所です。顔検出なんてモデル作って関数に投げておけばいいだけですが、このハッシュ計算はほぼ手書きですw

まず、利用するハッシュについてです。
先ほどMD5やCRC32とは異なるハッシュを利用すると言いました。
今上げたハッシュの計算方法だと全く同じ場合でないと同じ値になりません。逆に言えばちょっと変えた(サイズ変更とか)だけで大きく値が変化します。(CRC32は衝突しやすいけど…)
なので、今回はPerceptual Hashというものを使用します。

Perceptual Hashを使って画像の類似度を計算してみる – ユニファ開発者ブログ
最近、引越しをしたWebエンジニアの本間です。 引越しの作業は大変面倒でしたが、新しい街に来た時のワクワク感がやっぱりいいなーと感じております。 さて、弊社のサービスである「写真サービス るくみー」では、毎日たくさんの写真をアップロードしていただいているのですが、中には内容がほとんど同じ写真が入ってしまうことがあります。 これらの写真がそのまま販売されてしまうと、写真を選ぶ際に邪魔になったり、間違って複数枚購入してしまうことがあるため、可能な限り避けたい事象です。 「同じ内容」の写真を自動で判別する方法がないか調査していたところ「Perceptual Hash」という手法を見つけました。 Py…

はい、参考サイトが出てきました。
簡単に言えば、画像等のメディアファイルにおいて似ていると認識されるデータでは似たハッシュ値が作られるアルゴリズム群のことです。

今回はこのアルゴリズム群の中からpHash(Perceptive Hash)を使用しています。
ちなみにimage_hashにはdHash(Difference Hash)も実装してあります。
というのも、TPTSの初期に使用していたのがdHashでその後pHashに移行したため、どちらのコードも残っていたので入れておきました。

まず、初期に使っていたdHashです。これを実装する時に参考にしたサイトを載せておきます。

Detecting duplicate images using Python
One of the features that came out of our little hackaton and will be rolling out in the next couple of weeks is the ability to detect duplicate icons upon submission. So, for example if a user…

英語ですね。日本語のサイトもあったのですが、そちらは502エラーを吐いているので元の記事にしておきました。実際に書いたときは見れていたので、僕もそっちを読んでいました。

dHashの説明は最初の参考サイトにも載っているので、そちらを読むといいです。

では、image_hash内のdHashのコードを見てみましょう。

# dhash(different hash)による実装例
def dhash_calc(raw_file, hash_size=7):
    image = cv2.imdecode(np.asarray(bytearray(raw_file), dtype=np.uint8), 1)
    check_image = cv2.resize(image,(hash_size,hash_size+1))
    check_image = cv2.cvtColor(check_image, cv2.COLOR_RGB2GRAY)
    difference = []
    for row in range(hash_size):
        for col in range(hash_size):
            pixel_left = check_image[col, row]
            pixel_right = check_image[col + 1, row]
            difference.append(pixel_left > pixel_right)
    decimal_value = 0
    hex_string = []
    for index, value in enumerate(difference):
        if value:
            decimal_value += 2**(index % 8)
        if (index % 8) == 7:
            hex_string.append(hex(decimal_value)[2:].rjust(2, '0'))
            decimal_value = 0
    return ''.join(hex_string)

今回は使用していませんが、入っているのでTL_capture_lbp_overlap.py内のphashと書かれた部分を全てdhashに置き換えて、87行目のコメントに合わせてスクリプトを少し変えてもらえば使う事ができます。

では、関数の説明です。行番号はimage_hash.pyの行番号になっています。

まず、画像を8×7の非常に小さな画像にし、グレースケールにします(23~25行目)。
このサイズなのですが、サンプルと同じサイズにしてあるだけで変更は一応出来ます。ただ、ハッシュサイズが大きくなって計算に時間がかかるようになるのでおすすめはしません。結果もさほど変化しないので、あまり意味がないかと…

次に1ピクセルずつ左右の輝度を比較していきます(27~31行目)。
右隣のほうが明るければ1、暗ければ0といったビットに変換していきます。変換したビット群はリストに入れていきます。

最後にそのリストを元に16進数でハッシュ値を生成します(34~40行目)。
なんかやばい計算をしていますが、この部分はサンプルから持ってきたものなのでよく分かってません(おい
正直リストを連結して2進数表記でもいい気がします。てか、pHashのほうは2進数表記なので合わせればよかったですね。

ちなみにdHashなのですが、一時期有名になったごちうサーチでも使用されているようです。
つまり、これを使えば自分でごちうサーチを作ることが出来るのだ!

次は現在実際に使っているpHashです。これも参考サイトを載せておきます。

Perceptual Hash – stMind
Perceptual Hashは、画像などのメディアデータのハッシュを計算するアルゴリズム群です。 SHA-1やMD5とは異なり、画像サイズの違いや回転などの変換で画像が全く同一でない場合でも、元画像と同じハッシュ値を計算してくれます。 どんなことに使われているのか? アプリケーションとしては次のようなものがあります。 コンテンツの重複検出 Iconfinderでは、アイコン画像のアップロード時にdHashを用いて登録済みアイコンとの重複を検出する機能を開発中(Detecting duplicate images using Python – The Iconfinder Blog) Yout…

で、まあこのブログを見てもらえば分かるのですが、ImageHashっていうライブラリが存在するんですよね。なんで自分で書いたんだろう…

まあ、実装出来てちゃんと動いてるのでいいとしましょう。
image_hash内のpHashのコードを見てみましょう。

# phash(perceptual hash)による実装例
def phash_calc(raw_file, hash_size=32):
    image = cv2.imdecode(np.asarray(bytearray(raw_file), dtype=np.uint8), 1)
    check_image = cv2.resize(image, (hash_size, hash_size))
    check_image = cv2.cvtColor(check_image, cv2.COLOR_RGB2GRAY)
    dct = scipy.fftpack.dct(check_image)
    dctlowfreq = dct[:8, 1:9]
    avg = dctlowfreq.mean()
    diff = dctlowfreq > avg
    value_str = ""
    for value in [flatten for inner in diff for flatten in inner]:
        value_str += '1' if value else '0'
    return value_str

では、説明していきます。

まず、画像を32×32のサイズにリサイズして、グレースケールにします(9~11行目)。
先ほどより画像のサイズが大きくなりました。実はこれを狙って、pHashに移行したのです。
というのも、dHashは8×7というアホほど小さい画像に変換していました。そのため、細部がどうしても潰れてしまいます。
細部が潰れるとどうなるかというと、例えばエロゲのスクショなどがあった場合にテキストが変わっているにも関わらず、立ち絵が変わっていないため同じ画像として判定されてしまうことがしばしばありました。
ならばとハッシュサイズを大きくしたのですが、計算に時間がかかるようになってしまい実用的ではありませんでした。
そのため、32×32というある程度大きなサイズで計算が出来るpHashを使用することにしました。

次に画像の輝度情報(グレースケールのため画像自体が輝度だけのものになっています)に対してDCT(離散コサイン変換)をかけます(12行目)。
離散コサイン変換ってなんですかね。知識が無いので全然分からないです…
一応分かりやすい感じで書いてあるサイトのリンクを貼りましたが、皆さんググってください。圧縮などに使用される信号変換みたいです。

次に離散コサイン変換を行った後のデータから低周波成分を取り出します(13行目)。
これもさっぱり分かりません。低周波成分ってなんですか。
ただ、スライスを見れば分かる通り64ビット分だけ取り出しているようです。

次に取り出した低周波成分の平均値を取得して、各成分と比較していきます(14~15行目)。
平均より大きければ1、小さければ0といった感じのビット群を生成しています。

最後にこのビット群を文字列に変換していきます(17~18行目)。
内包表記と三項演算子による書き方をしていますが、まあ分かるでしょ。
てか、僕は普通こんな書き方をしません。つまり、どこからか引っ張ってきたものです。
ただ、探しても見つからないんですよね。どこから持ってきたんだ…

とりあえず、これでハッシュは生成出来ました。

次は出来たハッシュとすでに持っているハッシュの比較です。

for hash_key in self.file_hash:
    # dhashの場合は下の2を16に変更(2進数と16進数)
    check = int(hash_key, 2) ^ int(image_hash, 2)
    count = bin(check).count('1')
    if count < 4:
        is_overlap = True
        break

TL_capture_lbp_overlap.pyの比較部分を引っ張ってきました。
説明の行番号はTL_capture_lbp_overlap.pyの行番号となっています。

まず、ハッシュをint型に変換し、XOR演算を行っています(88行目)。
値同士をXOR演算すると、値のビット列において値が違うところが1、同じところが0となったビット列を得ることができます。

次にXOR演算後の値をビット列に変換し、1の数を数えています(89行目)。

さて、この2つの作業でハミング距離を求めています。
ハミング距離とは、 2つの値の異なるものの個数です。そのまま過ぎます。
ちなみにハミング距離は大学で習ったばかりのものです。やっと大学の内容が活かされるようになってきたぞ。

最後にハミング距離が4未満だった場合は重複しているものとしてスキップするようにします(90~92行目)。
コメントで書き忘れたのですが、この4という値はpHashの時に有効なものでdHashの場合は7ぐらいにするとちょうどいいです。
この値を調整することによって、重複判定の強弱を調整できます。小さくするとほぼ同一の画像でない限り収集されるようになり、大きくすると若干変わっただけでもスキップされるようになります。

ところで、dHashよりpHashのほうが遅いというのを見かけたのですが本当でしょうか?
今回はちょっとだけ計測してみました。
計測条件は以下のようにしました。

  • 100枚の重複無しJPEG画像を対象とする
  • 画像サイズはバラバラである
  • TPTS同様にハッシュを持っていない状態から始め、最後が一番処理に時間がかかる状態する。(TPTSにおいて常時回収をする判定の状態)
  • 10回計測し、平均時間を求める

こんな感じでやったところ、両方共6.0secという驚きの結果になりました。
全く同じ値が出るので、何回かやりましたがそこまで大きな変化はありませんでした。
今回は遅いHDDでやったため、時間がかかっています。ただ、それでも目に見えて変化することは無いと思うので、どちらを使っても大丈夫でしょう。

ちなみにごちうサーチが高速なのは、すでに100万枚のハッシュを持っている状態で投げられた1枚の画像だけハッシュを求め、比較していけばいいだけだからだと思います。正解の位置が判明すればそこで処理が終了となりますし…

 

重複判定はこんなものですかね。結構役に立つ部分だと思います。
次こそは本当にデータベースに情報を蓄えていきます。残すところ、あと2回です!

投稿者: 赤西 真論

人生に疲れたどこかにいるオタク。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください