私は約 150.000 枚の写真を持っていますが、これらのいくつかは重複しています。SSIM アルゴリズムは、2 つの画像を比較して重複しているかどうかを確認するのに適していると考えました。ただし、そのように重複を見つけたい場合は、150.000 * 149.999 の写真を比較する必要があり、永遠にかかります。
したがって、私が今探しているのは、各画像の平均値を作成し、平均値に近い画像のみを比較するための高速で効果的なアルゴリズムです。
要するに、写真を分類する効果的な方法を探しています!
高速なため、このタスクには C++ CImg ライブラリを使用する予定です。
ありがとう！
高さが異なる写真もありますが、基本的に同じ写真で、下部に無関係なボックスがあり、高さが変わります。
画像の上部が 2 つの複製で常に同じである場合、かなり安全であるはずの画像内の N 行のピクセルに基づいてハッシュ値を計算することを試みることができます (つまり、下部のボックスは表示されません)。それらの行）。
すべてのファイルをハッシュしたら、ハッシュ値を並べ替えて、同じハッシュ値を持つ画像のみをより正確に比較できます。
ハッシュ/指紋のようなアプローチを試してみます：
各画像のフィンガープリントの生成。メタファイルまたはデータベースのコンポーネントのサイズや数など、関連する画像属性も含まれます。フィンガープリントは、一般的なサブイメージから計算できます。これは、不可逆圧縮スペクトログラム、FFTの周波数ビンを含む単純なベクトル、ヒストグラム、または別の手法である可能性があります（私には、何がより適切であるかについての本当の手がかりがありません。これが最もおそらくコンテンツに大きく依存します）。
littlestewieが述べたように、サイズや色成分の数などの画像属性を使用して事前にグループ化すると(n*(n-1))/2、各グループの（バイナリ）比較の数が大幅に減少します。
さらなるサブグループ化のための適切な許容度を持つ指紋の比較（1つの画像が複数のグループで一致する場合をカバーするように注意してください）。
OpenCVは最終的な試合を行うことができます：
OpenCVを使用した画像比較に関する関連質問：
ほぼ同一の画像でも非常に異なるハッシュ値が得られるため、ここでは、任意の形式のハッシュを使用しても意味がありません。コメントで指摘されているように、2 つの「重複」画像はわずかに異なる可能性があるため (たとえば、JPEG 圧縮によって引き起こされる効果を考えてください)、ほぼ重複した画像を検出することに関心があります。また、コメントで指摘されているように、同じ幅の画像のみを考慮することは、比較の二次数を減らすための最初のステップです。すべての画像が同じ幅の場合、改善はありません。
最初に解決しなければならない問題は、高さが異なるほぼ同一の画像の一番下のボックスを破棄することです。なぜこの箱があるのですか？均一な背景色ですか？画像を前処理して、そのようなボトム ボックスを削除します。問題がある場合は、その理由を説明してください。これらのボックスは今後削除されたと見なします。
SSIM (Structural SIMilarity) はほぼ重複を検出するための優れたアプローチかもしれませんが、 Comparing image in url to image in filesystem in python で説明されている NRMSE などの単純なアルゴリズムよりも高速になる可能性はありません。したがって、プロセスを高速化する方法 (本質的には 2 次のままですが) は、最初に特定の画像をグレースケールに変換し、50x50 などの小さな中央ウィンドウのみを考慮することです。この中央のウィンドウにガウス フィルターを適用すると、マイナーな構造 (ノイズなど) がほとんど抑制されます。比較する画像がかなりあるので、この平滑化された中央のウィンドウに次の形式で大まかな 2 値化を適用します。v可能な最大値の半分より大きい場合は白に、それ以外の場合は黒にします。これで、各画像に 2500 ビットが割り当てられました。次のステップは次のようになります。これらの 2500 ビットから共通のビット パターンまでのハミング距離を計算します。ここでは 2500 ビット 1 が機能します。すべての画像に対してこのプロセスを繰り返します。画像ごとにハミング距離があります。
次に、ほぼ同一の画像を見つけてみましょう。最初に、見つかったハミング距離をk個別のスロットにビニングすることを検討してください。そのため、同じビンに含まれるすべての画像が比較のためにさらに考慮されます。このように、画像aが bink_iにあり、画像bが bink_jにある場合、に類似しているものとしてi != j破棄します。同じビンに画像が多すぎる場合は、上記のプロセスを調整するか、各ビンの間隔を縮小する必要があります。プロセスをさらに高速化するには、最初に同じビン内のすべての画像間で NRMSE を適用することを検討してください。最終的に、高い値を示す画像のみが SSIM によって比較されます。ab
MarvinLabs は、最初の N 行をハッシュ化するというアイデアを既に指摘しています。
最初の N 行 (たとえば 20 行) で適切なハッシュ (MD5 など) を使用すると、ハッシュの衝突が同一の画像を識別することを確信できます。ハッシュを他の一意の画像識別子 (ファイル名?) と一緒に std::multimap に入れます。このマルチマップは、パスの長さに応じて約 10MB から 100MB のコストがかかり、簡単にメモリに保持できます。ハッシュ後にレポートを作成できます。あなたが妄想的であれば、衝突のために別の画像比較を行います。すべての画像が同じ CCTV カメラからのものでない限り、誤検知の可能性はディスクからの読み取りエラーよりも小さくなります。