アレクサンダー・クライノフは、 演説の中で、 Yandex.Picturesがどのように複製画像をクラスター化したかを語った。 言い換えれば、重複した画像が分離され、フィルタリングされました。 主なアイデアは、 DoGフィルターを使用して画像の輪郭を強調し、キーポイントを見つけてその記述子を取得することでした。
重複のクラスタリングは、一致する記述子の一致になります。 これは、「 画像検索での重複のクラスタリング 」のキーポイントの「デジタル形式」です。
しかし、これらの記述子が何であるか、そしてそれらをどのように検索するかについてもう少し学びたいです。
記述子
キーポイントとは、画像を変更または修正する際に変更しないことが理想的なポイントです。
記述子は、一般的な用語では、特性の畳み込みであり、一致をチェックするためにアクセス可能な形式でのキーポイントの表示です。
キーポイント、それらの記述子、および一致をチェックする方法の効果的な割り当ての検索は、まだ議題にあります。
しかし、どこかから始めなければならないので、 OpenCVライブラリに助けを求めましょう。
最初に目を引くのは、 SURF記述子です。
これは並外れた精度を約束します。 これはテスト後に確認されます。
しかし、いくつかのニュアンスがあります。
SURF記述子は、キーポイントごとに128（または64）の数値のベクトルです。 マッチングは、最も近いポイント（または2つ）を検索することで実行されます。 そして、ポイントが近いほど良い。
キーポイントが1,000の画像の場合、128,000の浮動小数点数が必要であることがわかります。
さらに、ポイントの検出はかなり複雑な操作であり、かなりの時間を必要とします。 小型のデバイスでこのアルゴリズムを効果的に使用できないもの。 さらに、アルゴリズム自体は閉じられており、特許を取得しています（米国）。
SIFTとSURFに慣れた後、小さなサーバーまたはデバイスで使用できる機能を備えた簡単な実装を望んでいました。
知覚ハッシュ
そして、知覚的または知覚的ハッシュが見つかりました。
画像に少し変更を加えると、ハッシュもわずかに変わります。
一致チェックは、2つのハッシュ間の異なる位置の数をカウントすることにより実行されます。 つまり ハミング距離の計算。 そして、それが小さいほど、異なる要素が少ないほど、一致が大きくなります。
この方法は、完全または部分的な重複画像を検索するように設計されています。 つまり ハッシュが著しく異なるため、画像形式の大幅な変更、またはコンテンツへの干渉により、一致のチェックができなくなります。
言い換えれば、知覚的ハッシュは半分の重複を見つけるのには適していません。
これに基づいて、ファジー半重複を検索する問題を解決するために、SURF記述子と知覚的ハッシュを結合する試みが行われました。
この方法は 、キーポイントのクラスタリングに基づいているため、クラスターの中心は元の画像とトリミングされた画像上で一致します。 そして、キーポイント周辺の画像の断片が抽出され、知覚的ハッシュを受け取りました。 その結果、1つのイメージで約200のスライスとそのハッシュが生成されました。
この方法には、2つ半の重大な欠点があります。
1.ハッシュの大きなセットでの一致のチェックの低速。 100万回のハッシュの検索には20秒かかりました
2.キーポイントを取得する速度が遅い
3.低精度、多くの誤検知、ターゲットベースに対する高い要件、すべての画像に適していない、事前調整が必要など
特定の数の指紋が画像から割り当てられるというまさにアイデアであり、それは単純に互いに比較することができ、魅力的でした。
したがって、これらの問題の解決策を見つけようとすることが決定されました。
遅いサンプリングレート
大きなデータセットでハミング距離を見つけて計算する複雑さは独立した問題であり、独立したアプローチが必要です。
この問題に関するいくつかの調査の後、この問題には多くの解決策があることが判明しました。
HEngineと呼ばれる最も効率的な利用可能なアルゴリズムが選択および実装され、データベースからの選択を約60倍高速化することができました。
サーフとキーポイント
すでにバイナリハッシュまたはフィンガープリントで作業しており、偶然の一致はハミングの距離であると考えているため、SURFのような巨像を使用するのは奇妙であり、キーポイントと記述子を取得する他の方法を検討する価値があります。
一般に、OpenCVは2種類の記述子を提供します。
-浮動小数点記述子
-バイナリ記述子
ハミング距離を使用して一致をチェックするため、タスクに適した他のバイナリ記述子とは異なります。
ORB：SIFTまたはSURFの効率的な代替手段
OpenCVにはすでにSURFの優れた代替品があります。これはオープンであり、ライセンスの制限がないだけでなく、さらに簡単で高速です[1]。
ORBはOriented FAST and Rotated Brief-改良されたバージョンで、FASTキューポイント検出器とBriefバイナリ記述子の組み合わせです。
ORBには重要なニュアンスが1つあります。記述子のサイズは1ポイントあたり32バイトです。
一致チェックは、記述子の各バイトのハミング距離の合計です（最初のバイトは最初のバイトと比較され、2番目のバイトは2番目のバイトと比較されます）。
このタスクでは、1つのポイントが1つの値を与えると想定されており、ターゲットデータベースのインデックス（最初は1番目、2番目は2番目など）によって対応するものと合計する必要があります。
ハッシュは64ビットの数値であるため、8バイトに圧縮するのに32バイトの記述子が必要であり、同時に精度が大幅に低下することはありません。
いくつかのテストの後、これらの32バイトを16x16ビットマトリックスとして提示することが決定されました。 そして、このマトリックスをPHash知覚ハッシュに渡します。 結果は64ビットの数になっているはずです。
次に、コンセプトの完全な説明に進みます。
インデックス作成の仕組み
1.キーポイントとORB記述子を取得し、画像内の必要なポイントの数を選択します。
2.結果として得られる32バイトの記述子は、16x16ビットマトリックスの形式で表示されます。
3. PHashを使用して、マトリックスを64ビット数に変換します。
4. MySQLに64ビットフィンガープリントを保存します。
5.必要なハミング距離を選択し、検索を実行するHEngineデーモンを実行します。
検索の仕組み
インデックス作成から同じ手順1〜3を実行しますが、要求された画像に対してのみ実行します。
4. HEngineデーモンにリクエストを行い、デーモンは指定された制限内のすべてのハッシュを返します。
5.必要に応じて、無関係な結果を除外します。
図1.ハミング距離の制限7.灰色の点が重要なポイントです。 緑-マッチングポイント。 赤-標準ORBの完全検索に一致します。
結果は何ですか？
その結果、いくつかの問題を解決できました。
-大規模なデータセットでハミング距離をすばやく計算する方法を見つける
-大きくて不快なサーフィンを取り除きます
-キーポイントと指紋の強調表示の速度を上げます
-また、精度が大幅に低下することもありません。
これにより、フラグメントによって画像を見つけることができました。また、大きな計算リソースなしで、あいまいな半二重画像を見つけることができました。
図2.金曜日までの甘い
設定に応じて、バイナリ記述子ORBを使用して記述されたアルゴリズムは、画像ごとに約1,000のハッシュを与えることを考慮してください。
1,000個のイメージに基づいて、データベースで1,000,000個のハッシュが取得されます。 すべての重複を見つけてクラスタリングするには、1分半かかります。 徹底的な検索と一致するハッシュが含まれます。
参照資料
[1] Ethan Rublee、Vincent Rabaud、Kurt Konolige、Gary R. Bradski：ORB：SIFTまたはSURFに代わる効率的な手段。 ICCV 2011：2564-2571。
[2] en.wikipedia.org/wiki/SURF
[3] en.wikipedia.org/wiki/Hamming_Distance
[4] phash.org
[5] habrahabr.ru/post/143667 Yandex.Picturesでの重複のクラスタリング
[6] habrahabr.ru/post/211264 HEngine-大量のデータセットで特定のハミング距離内のハッシュを検索するアルゴリズム
[7] github.com/valbok/img.chkフラグメント検索プロトタイプ