再投稿または知覚的ハッシュに関するいくつかの言葉に対処する方法

この出版物では、知覚的イメージハッシュを構築するアプローチと、その使用の可能性（重複検索など）について説明します。

知覚ハッシュアルゴリズムは、同等のハッシュを生成するための関数のクラスを記述します。 さまざまな画像プロパティを使用して、個々の「インプリント」を構築します。 将来、これらの「プリント」は相互に比較できます。

ハッシュが異なる場合、データは異なります。 ハッシュが一致する場合、データはおそらく同じです（衝突の可能性があるため、同じハッシュはデータが一致することを保証しません）。 この記事では、知覚的なイメージハッシュを構築するためのいくつかの一般的な方法と、衝突に対処する簡単な方法について説明します。 猫の下で、興味のある方はどうぞ。

復習

知覚的イメージハッシュを作成するには、さまざまなアプローチがあります。 それらはすべて、3つの主要な段階で統合されています。

• 前処理。 この段階で、画像はハッシュを作成するために処理しやすい形式に縮小されます。 これには、さまざまなフィルター（ガウスなど）、変色、画像の縮小などを使用できます。
• 基本的な計算。 ステージ1で取得した画像から、マトリックス（またはベクトル）が構築されます。 行列（ベクトル）は、周波数の行列（たとえば、フーリエ変換後）、輝度のヒストグラム、またはより単純化された画像にすることができます。
• ハッシュを作成します。 ステージ2で取得した行列（ベクトル）から、いくつかの（おそらくすべての）係数が取得され、ハッシュに変換されます。 通常、ハッシュは8〜100バイトのサイズで取得されます。 計算されたハッシュ値は、2つのハッシュ間の「距離」を計算する関数を使用して比較されます。

本書では、上記のアルゴリズムの実装については考慮しません。 これは概要であり、ハッシュを構築するためのさまざまなアプローチについて説明しています。

知覚的ハッシュアルゴリズム

4つの異なるハッシュアルゴリズムを見ていきます。単純なハッシュ[4]、DCTベースのハッシュ[1]、[11]、放射状分散ベースのハッシュ[1]、[5]、およびMarr-Hildreth Operator Based Hash [1]、[6] 。

シンプルハッシュ（別名平均ハッシュ）

このアルゴリズムの本質は、低周波数の平均値を表示することです。 画像では、高周波数は詳細を提供し、低周波数は構造を示します。 したがって、類似の画像に対して近いハッシュを生成するようなハッシュ関数を作成するには、高周波を取り除く必要があります。 動作原理：

• サイズを小さくします。 高周波を取り除く最も速い方法は、画像を縮小することです。 画像は32x32〜8x8の範囲のサイズに縮小されます。
• 色を削除します。 小さな画像はグレースケールで変換されるため、ハッシュは3分の1に削減されます。
• すべてのピクセルの平均色値を計算します。
• ビットチェーンを構築します。 各ピクセルの色は、平均よりも大きいか小さいかに応じて、1または0に置き換えられます。
• ハッシュを作成します。 1024ビットの1つの値への変換。 順序は重要ではありませんが、通常、ビットは左から右、上から下に書き込まれます。

結果として得られるハッシュは、画像のスケーリング、圧縮、ストレッチ、明るさ、コントラスト、色の変更に対する耐性があります。 しかし、アルゴリズムの主な利点はその速度です。 このタイプのハッシュを比較するために、正規化されたハミング距離関数が使用されます。


ソース画像


「指紋」を受け取った

離散コサイン変換ベースのハッシュ（別名pHash）

離散コサイン変換（DCT）[7]は、離散フーリエ変換（DFT）と密接に関連する直交変換の1つであり、そのベクトル空間の準同型です。 DCTは、フーリエ指向の変換と同様に、関数または信号（有限数のデータポイントのシーケンス）を、異なる周波数と振幅を持つ正弦波の合計として表現します。 DCTは、コサイン関数とサイン関数の両方を使用するDFTとは異なり、コサイン関数のみを使用します。 DCTには8種類あります[7]。 最も一般的なのは2番目のタイプです。 これを使用してハッシュ関数を作成します。
2番目のタイプのDCTを見てみましょう。

x [m]で、m = 0、...、N-1は長さNの信号のシーケンスです。DCTの2番目のタイプを次のように定義します。



この式は次のように書き換えることができます。



ここで、c [n、m]は、番号nの行と番号mの列の交点にあるDCT行列の要素です。
DCTマトリックスは次のように定義されます。



このマトリックスは、DCTの計算に非常に便利です。 DCTは、必要な長さについて事前に計算できます。 したがって、DCTは次のように表すことができます。
DCT = M×I×M '
ここで、MはDCT行列、Iは平方サイズの画像、M 'は逆行列です。

低周波DCT係数は、画像操作に対して最も安定しています。 これは、ほとんどの信号情報が通常、いくつかの低周波係数に集中しているためです。 マトリックスIとしては、通常、画像が取得され、32x32のサイズに圧縮され、たとえば漂白などのさまざまなフィルターを使用して単純化されます。 結果はDCTマトリックス（I）で、左上隅に低周波係数があります。 ハッシュを作成するには、左上の8x8の周波数ブロックが使用されます。 次に、このブロックから中間​​を見つけてビットのチェーンを構築することにより、8バイトのハッシュが構築されます（Simple Based Hashと同様）。
このアルゴリズムを使用してハッシュを構築する手順をリストします。

• 色を削除します。 不要な高周波を抑制するため。
• ノイズレベルを低減するには、メディアンフィルター[8]を適用します。 同時に、画像はいわゆる「ウィンドウ」に分割され、各ウィンドウは隣接するウィンドウの中央値[9]に置き換えられます。
• 画像を32x32に縮小します。
• 画像にDCTを適用します。
• ハッシュを作成します。

このようなハッシュの主な利点は、小さな回転に対する耐性、画像のぼやけと圧縮、およびサイズが小さいためにハッシュを比較する速度です。 このタイプのハッシュを比較するには、ハミング距離関数が使用されます。

動径分散ベースのハッシュ

Radial Variance Based Hashアルゴリズムの考え方は、ラドン変換に基づいて光線分散ベクトル（LDP）を構築することです[5]。 次に、DCTがDVDに適用され、ハッシュが計算されます。 ラドン変換は、直線に沿った多くの変数の関数の積分変換です。 さまざまな操作（圧縮など）および幾何学的変換（回転など）を使用した画像処理に耐性があります。 2次元の場合、関数f（x、y）のラドン変換は次のようになります。



ラドン変換には単純な幾何学的な意味があります-ベクトルn =（cos a、sin a）に垂直な直線に沿った関数の積分であり、原点から距離s（ベクトルnに沿って測定）で通過します。



離散画像のラドン変換を拡張するには、直線d = x∙cosα+ y∙sinαに沿った線形積分を、幅1ピクセルの行にあるすべてのピクセルの値を合計することで近似できます。



後に、投影線に沿ったピクセル値の合計の代わりに分散を使用するほうが良いことが発見されました[6]。 分散は、投影線に沿った輝度ギャップをより適切に処理します。 このような輝度ギャップは、投影線に直交するエッジが原因で発生します。
次に、分散の光線ベクトルを定義します。 Γ（α）を、与えられた角度に対応する投影線上のピクセルのセットとします。 （x '、y'）を画像の中心ピクセルの座標とします。 x、yがΓ（α）に属するのは、次の場合のみ



次に、動径分散ベクトルを定義します。
I（x、y）がピクセルの輝度（x、y）、＃（α）が集合のパワー、次に光線分散ベクトルR [α]（α= 0,1、...、179）を定義します。



ラドン変換は対称であるため、角度の180個の値からベクトルを作成するだけで十分です。 結果のベクトルを使用してハッシュを構築できますが、このアルゴリズムはさらに改善を提案します-DCTを結果のベクトルに適用します。 結果は、DCTのすべての重要なプロパティを継承するベクトルです。 結果のベクトルの最初の40個の係数は、低周波数に対応し、ハッシュとして取得されます。 したがって、受信したハッシュのサイズは40バイトです。
したがって、このアルゴリズムを使用してハッシュを構築する手順をリストします。

• 色を削除して、不要な高周波を抑制します。
• ガウスぼかしを使用した画像のぼかし （ぼかし）[10]。 画像は、ノイズを抑制するためにガウス関数を使用して変換されます。
• ガンマ補正を適用して、画像の退色を解消します。
• 分散の光線ベクトルを作成します。
• DCTを分散ベクトルに適用します。
• ハッシュを作成します。

このタイプのハッシュを比較するために、相互相関関数のピーク検索が使用されます。

Marr-Hildreth演算子ベースのハッシュ

Marr-Hildreth演算子[16]を使用すると、画像のエッジを定義できます。 一般的に、画像の境界は、特定の特徴に従って比較的優れた特性を持つ画像の隣接部分を分離するエッジまたは輪郭として定義できます。 これらの機能には色またはテクスチャを使用できますが、ほとんどの場合、画像の色のグレーグラデーション（明るさ）が使用されます。 境界を決定した結果が境界マップです。 境界マップは、画像の各ピクセルの境界の分類を表します。 境界が明るさの急激な変化として定義されている場合、微分または勾配を使用してそれらを見つけることができます。
機能させて ラインの輝度レベル（ピクセルの1次元配列）を示します。 境界を決定する最初のアプローチは、関数の局所的な極値、つまり一次導関数を見つけることです。 2番目のアプローチ（ラプラスの方法）は、2次導関数を見つけることです。 [1]。
両方のアプローチは、2次元の離散画像の場合に適合できますが、いくつかの問題があります。 離散的なケースで導関数を見つけるには、近似が必要です。 さらに、画像のノイズは境界を見つけるプロセスを著しく低下させる可能性があります。 したがって、画像の境界を決定する前に、ノイズを抑制する何らかのフィルターを適用する必要があります。 ハッシュを作成するには、ラプラス演算子（アプローチ2）とガウスフィルターを使用するアルゴリズムを選択できます。
連続ラプラスを定義します（ラプラス演算子）：
させる 画像の明るさを決定します。 次に、連続ラプラシアンは次のように定義されます。



ゼロゼロ そして、関数の境界に対応する点があります 、これらは2次導関数が消滅するポイントであるためです。 連続ラプラシアンからさまざまなフィルター（離散ラプラス演算子）を取得できます。 そのようなフィルター 、畳み込み関数を使用して離散画像に適用できます。 画像のラプラス演算子 次のように書き換えることができます。



ここで、*は関数の畳み込みを示します。 境界のマップを作成するには、離散演算子のゼロを見つける必要があります 。
次に、Marra-Hildreth演算子について考えます。 ガウスフィルター（LoG）からのラプラスとも呼ばれます-これは、特殊なタイプの離散ラプラス演算子です。 LoGは、ラプラス演算子をガウスフィルター（関数）に適用することによって構築されます。 この演算子の特徴は、一定のスケールで境界線を強調表示できることです。 境界をより適切に識別するために、スケール変数を変更できます。
ガウスフィルターは次のように定義されます。



微分と畳み込みは線形演算子であるため、ラプラス演算と畳み込みを交換できます。



このプロパティを使用すると、演算子を事前計算できます 、画像に依存しないため（ ）
（Marra-Hildreth演算子、Gaussフィルターからのラプラシアン、LoG）。 LoG hc（x、y）は次のように定義されます：



LoGを離散形式で使用するには、目的のスケール変数を代入してこの方程式を離散化します。 デフォルトでは、その値は1.0になります。 次に、離散畳み込みを使用してフィルターを画像に適用できます。
離散畳み込みを定義する：
x、y、zを画像Iのピクセル幅、長さ、深さとします。
画像IとマスクMの畳み込みの結果Rは、次のように定義されます。



次に、Marra-Hildreth演算子を使用してハッシュを構築するアルゴリズムのステップをリストします。

• 色を削除して、不要な高周波を抑制します。
• サイズ128x128の画像を変換します。
• 画像をぼかす（ぼかし）。 画像はガウス関数を使用して変換され、ノイズが抑制されます[10]。
• Marra-Hildrethオペレーターを作成します。
• LoGと画像に離散畳み込みを適用します。 判明します
  明るさのジャンプがはっきりと見える画像。
• 画像を棒グラフに変換します。 画像は小さなブロック（5x5）に分割され、輝度値が合計されます。
• ヒストグラムからハッシュを作成します。 ヒストグラムは3x3ブロックに分割されます。 これらのブロックでは、平均輝度値が考慮され、ビットのチェーンを構築する方法が使用されます。 サイズが64バイトのバイナリハッシュが判明します。

受信したハッシュのサイズは小さくありませんが、正規化されたハミング距離関数が使用されるため、2つのハッシュの比較にはラジアルアルゴリズムと比較してかなり時間がかかります。 また、このようなアルゴリズムは画像の回転に敏感ですが、スケーリング、暗化、および圧縮には耐性があります。

知覚的ハッシュ値比較関数

ハミング距離

ハミング距離は、2つのバイナリシーケンス間の異なる位置の数を決定します。
定義：
Aを有限長のアルファベットとします。 -バイナリシーケンス（ベクトル）。 xとyの間のハミング距離Δは次のように定義されます。



ハッシュ値を比較するこの方法は、DCTベースのハッシュ方法で使用されます。 ハッシュのサイズは8バイトなので、ハミング距離は間隔[0、64]にあります。 Δ値が小さいほど、画像の類似性が高くなります。
比較を容易にするために、ベクトルの長さを使用してハミング距離を正規化できます。



ハミングの正規化された距離は、単純ハッシュおよびMarr-Hildreth演算子ベースのハッシュアルゴリズムで使用されます。 ハミング距離は間隔[0.1]にあり、Δが0に近いほど、画像は類似しています。

ピーク相互相関関数

2つの信号間の相関は次のように定義されます。



ここで、x（t）とy（t）は実数の2つの連続関数です。 関数rxy（t）は、時間Tに対するこれら2つの信号のシフトを表します。変数Tは、信号が左にどれだけシフトするかを決定します。 信号x（t）とy（t）が異なる場合、関数rxy Tは相互相関と呼ばれます。
正規化相互相関関数を定義します。
xiとyiの場合、i = 0、... N-1は実数の2つのシーケンスであり、Nは両方のシーケンスの長さです。 遅延dを持つIAFは次のように定義されます。



ここで、mxおよびmyは、対応するシーケンスの平均値を示します。
相互相関関数（PCC）のピークは、間隔d = 0、Nで達成できる関数rdの最大値です。
PCCは、放射状分散ベースのハッシュアルゴリズムのハッシュ値を比較するために使用されます。 PCC∈[0,1]、その値が大きいほど、画像はより類似しています。

練習について一言

ハッシュアルゴリズムの実装における4つの異なるアプローチを検討しました。 知覚的ハッシュの範囲は、類似した画像の検索から写真内のスパムの検出まで幅広くあります。

このプロジェクトでは、知覚ハッシュを使用して、重複する画像を特定します。 さらに、ウォーターマーク 'i（異なるソースから取得）を含む画像またはエッジがトリミングされた画像同士を正常に比較することができます。
重複を見つけるための最適なアルゴリズムは放射状分散ベースのハッシュと考えることができますが、ハッシュの比較に非常に時間がかかるため、大量のデータに適用することは非常に困難です。

私たちは、DCTベースのハッシュを選択しました。 64ビットハッシュを使用します。これは重複を見つけるのに十分ですが、このような小さなハッシュサイズは必然的に衝突を引き起こします。 画像のヒストグラム（スペクトル）を作成することで、衝突に苦労しています。
スペクトルの各成分は、画像内の1つまたは別の部分範囲の相対的な色数を意味します。つまり、画像内の色の分布を示します。 次のようになります。



したがって、まずハッシュを比較して画像を探し、次にヒストグラムを比較します。ヒストグラムが大きく異なる場合、そのような画像は類似しているとは見なされません。 ピアソン相互相関を使用して、相互相関を考慮し、放射状分散ベースのハッシュを比較することで、ヒストグラム自体を比較できます。


このトピックがコミュニティにとって興味深いものである場合、次の記事では、DCTハッシュの実装と、ハミング距離を見つける方法について具体的に説明します。