webdevqa.jp.net

多くの画像の類似性を比較するための画像指紋

すべての画像を他のすべての画像と非常に高速に比較するために、多くの画像の指紋を作成する必要があります(既存の約100.000、1日あたり新規1000、RGB、JPEG、最大サイズ800x800)。バイナリ比較メソッドを使用することはできません。ほとんど類似した画像も認識されるはずだからです。

最善の方法は既存のライブラリですが、既存のアルゴリズムへのヒントも役立ちます。

91
Philip Dreyer

通常のハッシュまたはCRC計算アルゴリズムは、画像データではうまく機能しません。情報の次元的な性質を考慮する必要があります。

アフィン変換(スケーリング、回転、変換、反転)が考慮されるなど、非常に堅牢なフィンガープリントが必要な場合は、 画像ソースのラドン変換 を使用して、画像データの規範的なマッピングを生成できます-各画像にこれを保存し、指紋のみを比較します。これは複雑なアルゴリズムであり、弱い人向けではありません。

いくつかの簡単な解決策が可能です。

  1. 画像の輝度ヒストグラムを指紋として作成します
  2. 各画像の縮小版を指紋として作成します
  3. 比較品質を改善するために、手法(1)と(2)をハイブリッドアプローチに組み合わせます。

輝度ヒストグラム(特にRGBコンポーネントに分離されたヒストグラム)は、画像の妥当な指紋であり、非常に効率的に実装できます。あるヒストグラムから別のヒストグラムを引くと、新しいヒストリグラムが生成されます。これを処理して、2つの画像の類似性を判断できます。ヒストグラム。輝度/色情報の分布と出現を評価するのは、アフィン変換を非常にうまく処理するからです。各色成分の輝度情報を8ビット値まで量子化すると、ほぼすべての妥当なサイズの画像の指紋を保存するのに768バイトのストレージで十分です。画像の色情報を操作すると、輝度ヒストグラムは偽陰性を生成します。コントラスト/輝度、ポスタリゼーション、カラーシフトなどの変換を適用すると、輝度情報が変化します。また、特定の種類の画像では、誤検知が発生する可能性があります。たとえば、風景や単一の色が他の色を支配している画像などです。

画像の情報密度を比較しやすいレベルに下げるもう1つの方法は、スケーリングされた画像を使用することです。通常、元の画像サイズの10%未満の縮小では、使用する情報があまりにも多く失われるため、800x800ピクセルの画像を80x80に縮小しても、適切なフィンガープリンティングを実行するのに十分な情報を提供できます。ヒストグラムデータとは異なり、ソース解像度のアスペクト比が異なる場合、画像データの異方性スケーリングを実行する必要があります。つまり、300x800の画像を80x80のサムネイルに縮小すると、画像が変形し、300x500の画像(非常によく似ています)と比較すると、偽陰性が発生します。アフィン変換が関係する場合、サムネールフィンガープリントもしばしば偽陰性を生成します。画像を反転または回転させると、そのサムネイルは元の画像とはかなり異なり、誤検知が発生する可能性があります。

両方の手法を組み合わせることは、賭けをヘッジし、偽陽性と偽陰性の両方の発生を減らす合理的な方法です。

55
LBushkin

一般的なフレーバーを保持する、ここで提案されている縮小されたイメージバリアントよりもはるかに少ないアドホックアプローチがありますが、これは何が起こっているかについてはるかに厳密な数学的基礎を提供します。

画像の Haarウェーブレット を取得します。基本的に、Haarウェーブレットは、低解像度画像から各高解像度画像への一連の違いですが、ミップマップの「ツリー」の深さによって重み付けされます。計算は簡単です。次に、Haarウェーブレットに適切な重みを付けたら、k個の最大係数(絶対値で)を除くすべてを破棄し、ベクトルを正規化して保存します。

これらの正規化されたベクトルの2つのドット積を取得すると、1がほぼ同一の類似性の尺度が得られます。 here で詳細を投稿しました。

33
Edward KMETT

phash を必ず見てください。

画像比較のために、これがありますphpプロジェクト: https://github.com/kennethrapp/phasher

そして、私の小さなjavascriptクローン: https://redaktorcms.com/dev/phasher/demo_js/index.html

残念ながら、これは「ビットカウント」ベースですが、回転した画像を認識します。 javascriptのもう1つのアプローチは、canvasを使用して画像から輝度ヒストグラムを作成することでした。キャンバス上でポリゴンヒストグラムを視覚化し、データベース内のそのポリゴンを比較できます(例:mySQL spatial ...)

これは、ビデオヒストグラムのデモです。 https://redaktorcms.com/dev/globetrottr/testHashVideo.php

19
sebilasse

ずいぶん前に、いくつかの類似した特性を持つシステムに取り組みました。これは、私たちが従ったアルゴリズムの近似です:

  1. 画像をゾーンに分割します。この場合、4:3解像度のビデオを扱っていたため、12ゾーンを使用しました。これを行うと、ソース画像の解像度が写真から取り除かれます。
  2. 各ゾーンについて、全体の色-ゾーン内のすべてのピクセルの平均を計算します
  3. 画像全体について、全体の色-すべてのゾーンの平均を計算します

したがって、各画像に対して、n + 1整数値。nは追跡しているゾーンの数です。

比較のために、各カラーチャンネルを個別に確認する必要もあります。

  1. 画像全体について、全体の色のカラーチャネルを比較して、特定のしきい値(たとえば10%)内にあるかどうかを確認します。
  2. 画像がしきい値内にある場合、次に各ゾーンを比較します。すべてのゾーンもしきい値内にある場合、イメージは十分に一致しているため、少なくとも比較のためにフラグを立てることができます。

これにより、一致しない画像をすばやく破棄できます。より多くのゾーンを使用したり、アルゴリズムを再帰的に適用して、一致の信頼性を高めることもできます。

11
GalacticCowboy

Icの答えに似ています-複数の解像度で画像を比較してみてください。したがって、各画像は1x1、2x2、4x4 .. 800x800として保存されます。最低の解像度が一致しない場合(しきい値の対象)、すぐに拒否できます。一致する場合は、次に高い解像度でそれらを比較できます。

また、画像が医療画像などの類似の構造を共有している場合、その構造を抽出して比較しやすい/より速い記述にできる場合があります。

6
allclaws

ですから、「画像照合」とはかなり異なる「指紋照合」を行いたいのです。指紋の分析は過去20年間に深く研究されており、適切な検出率([〜#〜] far [〜#〜]に関して) および[〜#〜] frr [〜#〜]メジャー-誤受入率および偽拒否率)。

LFA(Local Feature Analysis)クラスの検出技術の方が優れていることをお勧めします。特徴点は指紋の特定の特性であり、いくつかのクラスに分類されています。ラスターイメージを詳細マップにマッピングすることは、実際にはほとんどの公的機関が犯罪者やテロリストを登録するために行うことです。

詳細なリファレンスについては、 here をご覧ください

3
ZZambia

IPhoneの画像比較と画像の類似性の開発のチェックアウト: http://sites.google.com/site/imagecomparison/

動作を確認するには、iTunes AppStoreでeyeBuy Visual Searchをチェックしてください。

3
Brett

2015年の時点(未来に戻って...現在Googleで上位にランクされているこの2009年の質問について)画像の類似性は、ディープラーニング技術を使用して計算できます。 Auto Encodersとして知られるアルゴリズムのファミリは、類似性を検索可能なベクトル表現を作成できます。デモがあります こちら

2
Alex R

これを行う1つの方法は、イメージのサイズを変更し、解像度を大幅に(おそらく200x200に)落として、比較のために小さい(ピクセル平均)バージョンを保存することです。次に、許容しきい値を定義し、各ピクセルを比較します。すべてのピクセルのRGBが許容範囲内にある場合、一致しています。

最初の実行はO(n ^ 2)ですが、すべての一致をカタログ化する場合、新しいイメージはそれぞれO(n)アルゴリズムと比較するだけです(以前と比較する必要があるだけです)ただし、比較する画像のリストが大きくなると、最終的には故障しますが、しばらくは安全だと思います。

400日間実行すると、500,000個の画像が得られます。つまり、(画像のサイズを変更する時間を割り引く)200(H)*200(W)*500,000(images)*3(RGB) = 60,000,000,000回の比較になります。すべての画像が完全に一致する場合、遅れることになりますが、おそらくそうではないでしょうか?単一の比較がしきい値を超えたらすぐに、一致する画像を割り引くことができます。

2
lc.

文字通りすべての画像を他の画像と比較したいですか?アプリケーションは何ですか?特定の記述子に基づいて、ある種のインデックス付けと画像の取得が必要な場合がありますか?次に、たとえば、マルチメディアコンテンツ記述インターフェイスのMPEG-7標準を見ることができます。その後、さまざまな画像記述子を比較できますが、これはそれほど正確ではありませんが、はるかに高速です。

2
Anonymous

特殊な画像ハッシュアルゴリズムは活発に研究されている領域のようですが、おそらく画像バイトの通常のハッシュ計算がトリックを行うでしょう。

同じソースから派生しているが、フォーマットや解像度が異なる可能性がある画像を探すのではなく、バイトが同一の画像を探していますか(かなり難しい問題だと思います)。

0
Ian Hopkinson