Mythbusters：Google Recaptchaの自動ソリューション

こんにちは 私はpythonで興味深いアイデアを具体化し、その結果について話します。 前回、不動産価格マップで異常を見つけようとしました。 そのように。 今回のアイデアは、いくつかのアルゴリズムとトレーニング例の大規模なデータベースに基づいて、非常に人気のあるGoogle Recaptcha 2.0自体を解決できるシステムを構築することでした。
Google Recaptcha 2.0は一連の画像（1つの命令で9個または16個の正方形の画像）であり、その中でユーザーは、妥当性を確認するために同じカテゴリのすべての画像を選択する必要があります。 これは機械学習システムを構築することではありません -キャプチャを認識します！

読者が技術計画の詳細や研究のロマンスに触れたくない場合、記事全体の結論は最終的にBCGの近くに集中します。
この研究のためのキャプチャのトレーニングサンプルは、アンチキャプチャサービスRuCaptcha.comによって親切に提供されました。RuCaptcha.comは、私の研究のために解決済みのキャプチャのサンプルにアクセスするためのAPIを開発しました。
Googleには、世界のすべての主要言語でキャプチャに関する非常に大きな一連の指示（例：レクリエーション用車両ですべての画像を選択）がなく、一部の指示は他の指示よりもはるかに一般的であることに注意してください。 さらに記事では、タイプはキャプチャの正確な指示を意味します。

数千の画像

画像のテストバッチをアップロードして並べ替えた後、さまざまな種類のキャプチャを手動で解析し始めました。 まず、一致を見つけることを期待して、同じタイプのすべてのキャプチャからmd5サムを作成しました。 最も簡単な方法は機能しませんでした-単に一致するものがありませんでした。 そして何？ -私には権利があります！
画像アイコンの目を歩いてみると、何か面白いものが見つかりました。 ここで、たとえば、4つの同一のリムジン：

同じですが、完全ではありません-左下隅のホイールのサイズが顕著です。 比較のためにリムジンが選ばれたのはなぜですか？ それらを目で見るのが最も簡単でした-道路標識や通りの名前の写真が1つに統合され、同様のリムジンやピックアップの検索は簡単でした。 さまざまな種類の画像を自分の目で評価したところ、多くの場合、さまざまな変形（伸縮、圧縮、または変位）のキャプチャを繰り返し見ました。 適切な画像類似度関数を見つけ、十分な基礎を集めたので、ある程度の成功を期待できます。

知覚的ハッシュ

ほとんどすべての検索が彼につながります。 Habréには、知覚ハッシュに関する多くの記事があります（ 1、2、3、4 ）。 NumPyおよびSciPyパッケージを使用して、python ImageHashライブラリもすぐに見つかりました。

知覚的ハッシュはどのように機能しますか？ 要するに：

dct = scipy.fftpack.dct(scipy.fftpack.dct(pixels, axis=0), axis=1) dctlowfreq = dct[:hash_size, :hash_size] med = numpy.median(dctlowfreq) diff = dctlowfreq > med 

1. 画像はhash_sizeサイズに圧縮されます。
2. 離散フーリエ変換は、結果のピクセルの値から取得されます。
3. フーリエ変換から、中央値が考慮されます。
4. フーリエ変換行列は中央値と比較され、結果としてゼロと1の行列が得られます。

したがって、不変式と画像を区別することができますが、元の画像を少し変更しても変化しません。 標準のhash_sizeは8で、試行比較で良好に機能しました。 このハッシュの大きな特徴の1つは、それらを比較でき、その差が自然数のように見えることです。
今から説明します。 イメージハッシュは、ゼロまたは1の行列です（ゼロは中央値より低く、1つは上にあります）。 差を見つけるために、マトリックスは要素ごとに比較され、差の値は同じ位置にある異なる要素の数に等しくなります。 マトリックス上の一種のXOR。

数万枚の画像

知覚的ハッシュは、同じリムジンの間の類似性を明確に定義しましたが、変形が異なり、完全に異なる画像間の違いを定義しました。 ただし、ハッシュは写真に示されているフォームを記述するのに適しています：キャプチャの数が増えると、オブジェクトの形状の一致は避けられませんが、写真のコンテンツではありません（もちろん、特定のしきい値があります）。
そしてそれが起こった。 キャプチャベースの増加に伴い、画像に別の比較値を追加する必要性が高まりました。
画像の客観的な色特性は、色強度のヒストグラムで説明できます。 2つのヒストグラムの距離関数（差関数でもあります）は、ヒストグラム要素の標準偏差の合計です。 かなり良い束が得られます。


一方で、非常に類似した形状の画像間の位相差がゼロになるという事実と、偽陽性の割合が非常に低くなると想像すると、2つのハッシュを使用するよりも知覚的ハッシュのみを使用する方が速いと考えるかもしれません。 しかし、練習は何と言っていますか？

比較のために、異なるタイプの4000画像のキャプチャの2つのサンプルを使用しました。 1つのタイプには「類似性」があり、もう1つのタイプには他の方法があります。 類似性（別名圧縮率）とは、特定の応答しきい値を持つ同じタイプの2つのランダムイメージがハッシュに関して同じになる確率を意味します。 評価結果は次のとおりです。

 instructions : phash only : both hashes   (  !) : 0.001% : 0.002%  : 52.97% : 60.12% 

リムジンの画像の半分以上が互いに似ている、すごい！ 両方のハッシュを使用すると、結果はさらに良くなりますが、パフォーマンスはどうですか？

 instructions : phash only : both hashes   (  !) : 31.37s : 31.06s  : 17.85s : 17.23s 

驚いたことに、両方のハッシュを使用すると、最大偏差がゼロの知覚的ハッシュのみを使用するよりも高速でした。 もちろん、これは画像比較操作の数の違いが原因であり、300値のヒストグラムの比較はサイズが8バイトの知覚ハッシュの比較よりも28.7％遅いという事実にもかかわらず！

数十万枚の画像

大量のサンプルでパフォーマンスの問題が感じられました。 最も人気のあるタイプでは、ラップトップでの類似画像の検索時間はすでに数秒でした。 精度の損失を最小限に抑えながら、検索の最適化が必要でした。
位相精度を変更することは、私にとって良い考えのように思えませんでした。 したがって、いくつかのキャプチャの色の強度のヒストグラムを注意深く見てみましょう。



このヒストグラムを簡単に説明するように求められた場合、「横座標値55で鋭いピーク、次にグラフが緩やかに減少し、値170および220で2つの局所的な低値」と言います。 同様のキャプチャからより多くのヒストグラムプロットを取得すると、これらのプロットの形状が互いに類似しており、高低の位置（極値）にわずかな誤差があることに気付くでしょう。 では、これらの値を使用して、異なる値を意図的に遮断しないのはなぜですか？
OK Google、Pythonチャートで極値を見つける方法は？

 import numpy as np from scipy.signal import argrelextrema mins = argrelextrema(histogram, np.less)[0] maxs = argrelextrema(histogram, np.greater)[0] 

argrelextrema関数の説明は、データの相対的な極値を計算します。
ただし、ヒストグラムはギザギザになりすぎており、必要以上に局所的な極値があります。 関数を平滑化する必要があります。

 s = numpy.r_[x[window_len-1:0:-1],x,x[-1:-window_len:-1]] 

スライディングウィンドウアルゴリズムでグラフを平均化します。 ウィンドウサイズは、最小または最大の数が平均2になるように経験的に選択され、100ピクセルの値で停止しました。 このアルゴリズムの結果は、美しく、スムーズで...スケジュールが長くなります。 ウィンドウのサイズを正確に引き伸ばした。


同様に、極値シフトの位置

 mins = array([ 50, 214, 305]) maxs = array([116, 246]) 

同様のキャプチャの多くのグラフを比較すると、3〜4ピクセルが局所的な極値の位置からの許容可能な偏差であることがわかりました。 この値をより小さな方向に調整することにより、圧縮率の低下により、アルゴリズムのより大きなフィルタリングと高速化を実現できます。

もちろん、RuCaptchaのキャプチャには認識エラーがあった可能性があります。 それらに対抗するために、キャプチャ評価システムが導入されました。 新しいcaptchaのmd5が既にデータベースにあるが、命令のタイプが異なる場合、古いcaptchaには失敗カウンターがあり、古いcaptchaのタイプが新しいcaptchaのタイプと同じである場合、 人気カウンターが増加します。 したがって、間違った決定の自然な調整が導入されます-同様の決定を検索する場合、 人気>失敗のキャプチャのみが考慮されます。

私の最初の百万

調査作業のすべての時間で、100万以上の解決されたキャプチャが収集されました。 データの保存には、PostgreSQLデータベースが使用されました。このデータベースでは、ハッシュとヒストグラム値の配列を保存すると便利でした。 ヒストグラムの保存といえば、 255 + window_sizeの値をすべて保存して、2つのヒストグラム間の距離を計算する必要はありません。 配列値の半分または3分の1を使用する場合、距離の精度はわずかに低下しますが、ディスク容量は節約されます。

このようなサンプルの場合、キャプチャ統計は非常に正確です。
以下は、最も「圧縮性」が高く人気のあるキャプチャ（各3行）に関するデータです。

        (%)  15274 5508 64   2453 928 62  5261 2067 61   (  !) 201872 189473 6    137893 134695 2    94569 92824 2 

最も純粋な形式のパレートの法則 ：指示の11％がすべてのキャプチャの〜80％を与えます（および指示の20％がすべてのキャプチャの91％を与えます）。 そして、統計は、最も圧縮可能なタイプを支持するものではありません。

Google自身はこう言っています：
reCAPTCHAは、高度なリスク分析エンジンと適応型CAPTCHAを使用して、自動化されたソフトウェアがサイトでの不正行為を行わないようにします。
CAPTCHAが解決されるたびに、その人間の努力がテキストのデジタル化、画像の注釈付け、機械学習データセットの構築に役立ちます。 これにより、書籍の保存、地図の改善、ハードAIの問題の解決に役立ちます。

人々によるキャプチャの解決を通して、それが彼らの自動回転を保証することを示唆します。 Googleは、交通標識や通りの名前など、画像の回転が適切なレベルの小さな一連の指示に依存していました。

タスクには実際のGoogle reCaptchaのチェックに関する項目が含まれていなかったため、代わりに、すべての新しいトレーニング画像に次のアルゴリズムを使用します。

1. 入力キャプチャは3x3または4x4をキャプチャし、それぞれ9または16個の画像に分割されます
2. 上記のアルゴリズムによると、9個または16個の画像すべてに対して、データベース内のすべてのタイプの類似データが選択されます。
3. 見つかった解の画像インデックスは、参照解のインデックスと比較されます
4. ソリューション間の差異（異なるインデックスの数）が50％以上の場合、キャプチャは未解決と見なされます

左側の例では、データベース（自動ソリューション）のデータが正しいインデックスが0、1、3であり、参照ソリューションが0、1、4である場合、インデックス3と4は異なるインデックスになります。異なるインデックス、すなわち キャプチャは解決されません。

ほとんどの3x3 captchas 3（+ -1）インデックスは正しいため、このようなアルゴリズムは、自然なreCaptchaと同様の結果をもたらします。
パラグラフ2では、ソリューションはさまざまな方法で選択できます。

• 各画像について、データベース内のすべての種類の画像を検索してから、命令の種類に対応する画像のみを選択します。 このようなアプローチにより、対象外の画像からも解の統計を見つけることができ、決定の正確性に対する誤検知の影響も確認できます。
• 画像ごとに、1種類の指示のみを検索します。 このような検索ははるかに高速であり、原則として最初の方法からの誤検出を与えません。

以下は、数日間の解答結果のダイナミクスです。


平均して、組み立てられたシステムはGoogleのキャプチャを12.5％の確率で解決しました。これにより、Googleのソリューションを支持する強い議論ができました。

驚いたことに、ソリューションの数の点でリーダーは最も圧縮されていないキャプチャ（複数のサンプルの統計）の1つでした。

    (%)  (%)    142 14.03 2   (  !) 80 7.91 6  68 6.72 40  (   ) 58 5.73 43   (  ) 58 5.73 43   57 5.63 43 

また、非ターゲットキャプチャ（55％）はターゲットキャプチャ（45％）よりわずかに多くありました。 ターゲットキャプチャは、データベース全体を検索するときに（1つのタイプの命令だけでなく）イメージが正常に検出され、そのタイプがキャプチャ命令のタイプに対応するものです。 言い換えれば、リムジンに関する平均的な3x3のキャプチャには、リムジンを含む3つの画像と、その他のタイプを含む別の3.66画像があります。

この研究は、知覚的なハッシュと色のヒストグラムに基づいて、巨大なトレーニングサンプルを使用してもキャプチャソリューションシステムを構築することは不可能であることを示しました。 reCapthcaのこの結果は、最も人気のあるタイプのキャプチャが適切にローテーションされるために達成されます。

RuCaptchaの快適なコミュニケーションに感謝し、彼らの許可を得て、Yandexディスクにオープンアクセスでトレーニングサンプルを投稿します（ダウンロードは急ぎ、ディスクは1か月分支払われます）。

1. yadi.sk/d/CNJQ5uOwqfykL
2. yadi.sk/d/gnTU-qwnqfykM
3. yadi.sk/d/6vTTjhJaqfykV

Yandexドライブは10ギガバイトを超えるファイルをアップロードできないため、研究者は3部構成のtarアーカイブを接着する作業を待っています。

同じサンプルでの機械学習についての考えは私を去りません:)それまでは、システムのソースコードを Python で共有しています 。