はじめに
最近、Habrahabrに投稿された、 「見た目が似ている」画像の比較に関する記事に出会いました。 知覚ハッシュはどのように機能しますか？ 私自身がこのトピックに長い間取り組んでいるので（私はAntiDuplプログラムの著者です）、この問題に関する私の経験をここで共有したかったのです。 記事では、類似画像を比較するためのアルゴリズムの2つのバージョン-基本および改良版を提供します。 これらはすべて、上記のプロジェクトのフレームワーク内で実際に作者によってテストされました。 私のプレゼンテーションは、厳密な証拠、複雑な公式、特別な数学用語なしで実施されます。 読者がこれを許してくれることを願っています。
基本的なアルゴリズム
画像の類似性測定
類似の画像を比較する場合、最初の質問が発生します：画像の類似性の尺度とは何ですか？ 明らかに、この値は画像の互いの違いと反対の値を持っています。 したがって、相互の画像の違いを特徴付ける特定のメトリックを選択する必要があります。 次に、類似した画像は、それらの差が特定のしきい値よりも小さい画像と見なされます。 同じ寸法の画像の場合、通常、標準偏差は、ある画像のピクセルと別の画像のピクセルの標準偏差です。 もちろん、たとえば画像ピクセルの平均絶対差など、別のメトリックを選択することを妨げるものはありません。
さまざまなサイズの写真
異なるサイズの画像を比較する必要がある場合、質問はやや複雑です。 ただし、この問題のかなり明白な解決策は、すべての画像を同じサイズにすることです。 このサイズを選択する必要があります-選択するサイズが小さすぎると、画像間の差異が平準化され、多くの誤検知が発生することは明らかです。 サイズが大きすぎると、比較アルゴリズムのリソース消費が不当に増加します。 経験から、最も最適なのは16x16から64x64の画像のサイズであることがわかります。 また、経験から、画像の色特性は、明るさと比較して画像の類似性の視覚的感覚に与える影響がはるかに少ないため、破棄できます。
主な手順
したがって、類似画像を比較するためのアルゴリズムの最も単純なバージョンには、次の手順が含まれます。
- すべての画像を同じサイズにします（明確にするために、32x32にします）。
- カラー情報の破棄（グレー画像への変換）。
- 縮小グレー画像の各ペアのrms差を見つけます。
- 得られたrms差と特定のしきい値の比較。
ここで、しきい値は画像の類似性の尺度を決定します。 したがって、0％のしきい値を選択すると、アルゴリズムは完全に同一の画像のみを検出します。 5％のしきい値では、アルゴリズムは、解像度、圧縮品質、小さなラベルの存在、トリミングなどが異なる視覚的に類似した画像を見つけることもできます。 少数の誤検知があります。 原則として、10％を超えるしきい値では、誤検出の数が正の検出の数を超える可能性があります。 間違いなく、このアルゴリズムは何らかの形で、同様の画像を検索するプログラムに実装する必要があります。 バリエーションは通常、縮小画像を取得する方法、縮小画像のサイズ、およびカラーパレットに従って量子化する方法、画像の相違の程度を決定するメトリックの選択に関連します。
基本的なアルゴリズムの欠点
このアルゴリズムの欠点には、コントラストの弱い画像と大規模な特徴のない画像（輪郭描画、テキスト画像）を比較するときの感度が低いことが含まれます。 弱い感度は、元の画像が32x32のサイズに縮小されると、原則として、そのようなすべての画像が互いに区別できなくなるという事実によって説明されます。 また、画像の合計数に依存するアルゴリズムの実行時間の二次依存性は、画像の各ペアに対して比較を行う必要があるため、このアプローチの欠点と見なすことができます。 そのため、正規化された画像のペアを互いに比較するには、アルゴリズムは約10 ^ 3の算術演算を実行する必要があり、1000の画像では約10 ^ 9の演算であり、100万の画像では10 ^ 15の演算です。 もちろん、すべてのユーザーが100万枚の写真を集めた画像のコレクションを持っているわけではありませんが、10万枚の画像（これはアマチュア写真家にとってそれほど珍しいことではありません）を比較するために、約10 ^ 13の操作を完了する必要があり、これは最新のハードウェアでもかなりの時間がかかる可能性があります。
高速アルゴリズム
すでに述べたように、このアルゴリズムの基本的な実装には2つの問題があります。大規模な特徴のない画像の精度が低いことと、画像の総数に対する実行時間の2次依存性です。 最初の問題は、かなり狭い画像の円に対して非常に具体的かつ特徴的であるため、2番目の問題の解決にさらに焦点を当てます。 明らかに、このアルゴリズムは十分に並列化およびベクトル化されています。 ただし、この記事のフレームワークでは、ソフトウェアではなく、このアルゴリズムのアルゴリズム最適化について説明します。
アスペクト比
視覚的に同一の画像は、原則として、幅と高さの比率が近いです。 したがって、論理的な結論は、アスペクト比が近い画像のみを比較することです。 実際には、同じコレクション内のほとんどの画像は、原則として同じ縦横比（3：4など）を持ちますが、向きは異なります（垂直または水平）。 したがって、互いに比較する必要のない2つの分離されたクラスの画像を取得します。 この事実からのアルゴリズムのおおよその加速は約2倍です。
予備比較
最初の最も明白なステップ：一度画像を縮小した場合、再度それをしないのはなぜですか？ 32x32画像から4x4画像を作成します。縮小画像の各ポイントは、元の画像の対応する8x4サイズの部分の平均輝度を表します。 この縮小された画像のrms差は、元の画像のrms差以下であることが数学的に厳密に証明されます。 したがって、縮小された4x4画像を予備的に比較することにより、完全な比較のためにほとんどの候補を除外する種類のフィルターを作成できます（サンプル内の画像のほとんどが比較的一意である場合）。 このような単純な手法は、計算が容易であるため、ほぼ50倍の加速度を達成できます。 ただし、画像を比較するしきい値が高いほど、このフィルターの効率が低いことは明らかです。
一次元画像のインデックス付け
ご存じのように、O（N）を必要とする順序付けられていない配列とは対照的に、順序付けられたデータ配列での検索は、O（ln（N））の順序で実行できます。 したがって、なんとか画像を配置することができれば、理論的にはO（N ^ 2）の検索の2次の複雑さを準線形の複雑さ-O（N * ln（N））に減らすことができます。 そして、画像をソートするためのインデックスを作成しようとします。 これを行うには、4x4のサムネイルを使用して、さらに2回縮小して2x4にします。 この図から最初のインデックスを作成するのは簡単です。
i [0] =（p [0] [0] + p [0] [1] + p [1] [0] + p [1] [1]）/ 4
これは、画像の平均輝度を表します。 実際、この画像は1x1のサイズに縮小されます。 元の画像の二乗平均平方根の差は、強度の差以上になります。 したがって、画像を比較するためのしきい値がtである場合、比較のすべての可能な候補は、i [0]-tからi [0] + tの範囲の平均輝度を持つ必要があります。 実際、すべての画像をインデックスi [0]でソートすると、非常に少ない数の画像（2 * t / 255）と比較できます。 5％の典型的なしきい値に対して、10倍の理論的なゲインがあることを計算することは難しくありません。 実際には、平均輝度による画像の統計分布は[0 ... 255]の範囲で均一ではなく、127の近くでベル型の最大値を持ち、範囲の端で低下するため、ゲインは小さくなります。 その実際の幅、したがって、理論的に可能なアルゴリズムの実際のゲインは約70〜80％です。
多次元画像のインデックス付け
平均輝度i [0]に加えて、2x2画像からさらに3つの追加インデックスを作成できます。
i [1] = 128 +（p [0] [0]-p [0] [1] + p [1] [0]-p [1] [1]）/ 4、
i [2] = 128 +（p [0] [0] + p [0] [1]-p [1] [0]-p [1] [1]）/ 4、
i [3] = 128 +（p [0] [0]-p [0] [1]-p [1] [0] + p [1] [1]）/ 4
単純な物理的意味を持ちます：インデックスi [1]は画像の左部分が右よりどれだけ明るくなるかを示します。i[2]-上部は底よりも明るくなります。i[3]-画像の対角線はどれだけ異なります。 これらのすべてのインデックスについて、最初の画像だけでなく画像も並べ替えることができます。比較可能なすべての候補は、i [j]-tからi [j] + tの範囲にあります。 つまり これらのインデックスによって形成された4次元空間では、検索領域は2 * t辺と中心をもつ4次元立方体を表し、座標は目的の画像のインデックスによって形成されます。 理論的な加速度は、この4次元立方体の体積とインデックススペースの総体積の比に等しく、（2 * t / 255）^ 4 = 1/10000に等しくなります。 インデックスi [1]およびi [2]による画像の分布の有効幅は約40〜50％であり、i [3]は可能な最大の20〜30％であるため、実際の加速ははるかに控えめです。 実際の範囲が狭いため、実際には、後者のインデックスの使用はまったくお勧めできません。したがって、最初の3つのインデックスに制限することができます。 それにもかかわらず、実際に達成可能な加速度は2桁に達します（しきい値の差が5％の場合）。
改良されたアルゴリズムの主な段階
したがって、推論を要約し、迅速な画像比較のためにアルゴリズムのフレームワークで実行する必要がある基本的な手順を示すことができます。
- すべての画像を1つのサイズ（32x32）に縮小し、色情報を破棄します。
- 予備の4x4比較のサムネイルを見つける。
- 予備的な比較のために、画像に基づいて画像のn次元インデックスを構築します。
- n次元のインデックススペースで検索領域の境界を定義する。
- このフィールドの候補者のアスペクト比を確認します。
- 前の段落に合格した候補者と画像の予備比較を行う。
- 前の段落を過ぎた画像と候補者との完全な比較の実施。
高速アルゴリズムの欠点
一般に、インデックス付けの効率は画像の類似性のしきい値に強く依存します-ゼロのしきい値では、類似の画像の検索の複雑さは線形O（N）に近づき、大きなしきい値では2次O（N ^ 2）に近づきます それでも、アルゴリズムの基本バージョンでは、検索の複雑さは常に2次O（N ^ 2）であるため、これは大きな進歩です。 また、実際には、n次元のインデックススペースによる並べ替えを実装するには、インデックスの特定の範囲にある画像のリストでn次元の配列を整理する必要があります。 これにより、追加のオーバーヘッドが発生し、大きなディメンションのインデックス作成を使用することは不当になります。また、小さな画像コレクションに対するこのようなインデックス作成の非効率性もあります。
おわりに
一般に、改善されたバージョンのアルゴリズムに適用されるすべての改善点を要約すると、基本実装と比較して3〜4桁のゲインが得られます。 画像の大規模なコレクションのテストは、これが真実であることを示しています。 そのため、画像を相互に直接比較するには、シングルコアプロセッサで10万枚の画像を収集するのに約30秒かかります。 実際には、比較の速度は画像を検索する一般的なプロセスでは重要な要素になりません-結局、それらを見つけてディスクから読み取ってサムネイルを作成する必要があります（もちろん、最後の2つのポイントは1回だけ実行できますが、再利用のためにバイトを保存することをお勧めします）。
読者が私のプレゼンテーションに興味を持つことを願っています。 おそらく誰かがそれを有用だと思ったのでしょう。 フィードバックを待っています。
PSソフトウェアの実装
この記事の執筆から多くの時間が経過しました。 私はそれに少し追加することにしました。 Simdプロジェクトのフレームワーク内で、この記事で説明するアルゴリズムを実装するC ++ ImageMatcherでクラスが作成されました。 素敵な使い方をしてください！