最近、新しい製品ラインの開発に関連して、当社はデータベース内で同一の画像を見つけるタスクを持っています。
実装のアウトソーシングは費用がかかりすぎるため、最適なソリューションを保証するものではありません。 フリーランサーを手放す方が安くなりますが、ソリューションはおそらく同じくらい安く、OpenCVのような既存のライブラリに基づいています。 しかし、タスクが非常に簡単に解決された場合、競合他社はかなり前にこれを利用してきちんとした製品を作ったでしょうが、市場にはありません。 一般的に、固有の完璧主義、野心、そして最高になりたいという願望は、製品を「他の皆と同じように」市場に持ち込むことを可能にせず、より良く、より速く、より強くする必要があります。 私たちは、問題を独自に理解し、解決策を考え出し、詳細な参照条件を書き、既に実装のためにフリーランサーに提供することにしました。 競合他社が単に気付かなかった既製のソリューションがあるという希望がありました。 しかし、この質問（およびアルゴリズムORB、Brief、FAST、SIFT、SURF、BRISK、A-KAZE、Viola-Jonesなど）を検討すると、これらのアルゴリズムにはすべて欠点があることが明らかになりました。 上記のアルゴリズムのいくつかは私たちの問題を解決するのに適していましたが、どういうわけか私は突然、ソリューションをユニークでシンプルにしたかったのです。 そして今、私は自分の作曲のアルゴリズムであるコミュニティを裁判にかけます。
批判のファン（建設的に）私は猫の下でお願いします。
1.アルゴリズムの原理
当初は、これは基本的に、いわゆる検索と比較に基づいて画像を比較する方法です。 キーポイント。
この種類の（またはほぼすべての）アルゴリズムと同様に、私のアルゴリズムは次の手順で構成されます。
手順1.画像内のキーポイントを検索します。
ステップ2.記述子の形成。
ステップ3.バイナリ文字列（ハッシュ）の形成。
手順4.処理された画像のハッシュとデータベースに保存されている画像のハッシュの比較。
ステップ5.必要な形式で結果を取得します。
2.アルゴリズムの説明
2.1。 画像内のキーポイントを検索します。
キー（特異点、または特徴）は、多くのプロパティを満たす画像点です。
- 明確さ-フィーチャは、隣接するポイントの中で際立っている必要があります。
- 再現性—明るさ、コントラスト、色域の変化は、オブジェクトまたはシーンの特定のポイントの位置に影響を与えません。
- 特定のしきい値を超えない画像の安定性（ノイズ）は、検出器の動作に影響を与えません。
- 解釈可能性-特異点は、今後の作業に適した形式で提示する必要があります。
- 数量-検出された特殊ポイントの数は、オブジェクトの検出に必要なポイント数を提供する必要があります。
特定のポイントを検索するには、最高の速度対品質比としてFAST Detectorを使用しますが、他のタスクには他の検出器を使用できます。
次に、Harris Angle Detectorを使用して、少数（50個）の最も重要なキーポイントを選択します。
* FASTおよびHarris検出器の動作原理は、興味深い光源の記事「 角度 検出器 」に記載されています。2.2。 記述子の形成
記述子（緯度記述子-説明から）-周囲の特徴を定義する特異点の説明は、特定のパラメーターの数値またはバイナリベクトルです。 ベクトルの長さとパラメーターのタイプは、適用されるアルゴリズムによって決まります。 記述子を使用すると、画像内のそれらのセット全体から特異点を選択できます。これは、異なる画像を比較するときに1つのオブジェクトに属する特徴のキーペアをコンパイルするために必要です。
このステップでは、同様のアルゴリズムで一般的に使用されているキーポイント記述方法から離れて、より単純な方法に切り替えることをお勧めします。
環境を通じて各キーポイントを記述する代わりに、そのような各ポイントから残りのポイントまでの距離を測定することをお勧めします。 つまり 見つかった点の間にすべての可能なセグメントを置き、それらの長さを測定します。
そのため、測定の結果として得られたそのような数（セグメントの長さ）を、記述子と呼ぶことを提案します。
2.3。 ハッシュ生成
ハッシュまたはハッシュは、特定のアルゴリズムによって実行される、任意の長さの入力データの配列を固定長の（出力）ビット文字列に変換することです。 アルゴリズムを実装し、変換を実行する関数は、「ハッシュ関数」または「畳み込み関数」と呼ばれます。 ソースデータは、入力配列、「キー」または「メッセージ」と呼ばれます。 変換の結果（出力）は、「ハッシュ」、「ハッシュコード」、「ハッシュサム」、「メッセージサマリー」と呼ばれます。
ご存じのとおり、
Xポイントを使用して、
X *（X-1）/ 2セグメント、つまり 50ポイントから50 * 49/2 = 1225セグメントを作成できます。 つまり 行は1225個の整数で構成されます。 さらに、これらの数字は同じ文字数でなければなりません。 必要な文字数は、画像の解像度に基づいて選択されます（たとえば、500 * 500の画像の場合、最大カット長は707（対角線）です。つまり、3文字が必要です）。
平面内の回転に対する不変性を達成するために、計算されたようにではなく、大きいものから小さいものへとセグメントの長さを線で書きます。
次の行を取得します：
A1、A2、...、A1225 、ここで
A1> A2> ...> A12252.4。 ハッシュとデータベースを比較する
データベースでそのような画像を検索するには
、受け取ったハッシュ
A1、A2、...、A1225とデータベースに保存されているハッシュを比較する必要があります。
たとえば、ハッシュ
A1、A2、...、A1225を、
A1> A2> ...> A1225と
B1、B2、...、B1225と
比較し、記述子
Aを 3値、記述子
Bを 4とします。 これは、画像が異なる場合、または同じ画像が異なる縮尺である場合の2つの場合があります。
スケールに対する不変性を達成するために、各記述子を単一のスケールにします。 これを行うために、より大きな記述子の容量と同じ容量の最大数
M （この例では、最大4桁の数
M = 9999 ）を決定し、係数を見つけます。 式に従って
Kをスケーリング：
Ka = M / A1 （ライン
A1、A2、...、A1225の場合 ）および
Kv = M / B1 （ライン
B1、B2、...、B1225の場合 ）。 次に、ハッシュを単一のスケールにします。このため、各ハッシュ記述子
Aに
Kaを乗算し、各ハッシュ記述子
Bに
Qを乗算します
。 結果を行
A'1、A'2、...、A'1225および
B'1、B'2、...、B'1225に書き込み 、値を整数に丸めます。 その結果、同じスケールの2つのハッシュと1つのディメンションを取得します。
行
A'1、A'2、...、A'1225と
B'1、B'2、...、B'1225を比較できます。 このために、修正されたハミング距離の式を使用します。
実際、ハミング距離は、エラーの数を行の不均等な値の数として考慮します。 しかし、前の手順では、整数に丸めを適用しました。これにより、誤った結果が生じる可能性があります。 したがって、行
Aと
Bの対応する記述子の値が
Eだけ異なる場合、エラーとは見なしません（つまり、行の値が等しくないことを考慮するために、モジュロでとられた
iと
iの差は
Eより大きくなければなりません）。
Eを係数と呼びます。 忠誠心」であり、一般的なケースでは
E = 1を取ります。
次に、エラーの数を単純な合計と見なします。 距離
Pを取得します
。2.5。 結果を取得する
異なるタスクの場合、アルゴリズムの結果の異なる表示が必要になる場合があります。
2.5.1。 類似度2x画像
結果は、ステップ2.4に示す計算になります。
Rの2つのハッシュの距離 またはそれらの推定値。 たとえば、
P <10では 、画像が同一であると仮定できます。
10 <P <100-画像は類似しています。 など
2.5.2。 調査したものと可能な限り類似したデータベース内の画像検索
結果は、最小の距離値
Pを持つ画像の出力になります
。 または、すべての距離
Pが特定のしきい値よりも大きい場合、求められている画像に類似した画像は見つからなかったというメッセージの結論。
3.アルゴリズムの長所と短所
3.1。 上記のアルゴリズムの利点は次のとおりです。
- シンプルさ
- 高速
- 柔軟性（タスク、画像の特性、必要な精度に応じて、キーポイントを見つけるためのさまざまな方法を適用できます）。
- 係数のおかげで、異なる品質の画像に適用する機能。 忠誠心E.
- 画像の回転とスケーリングに対する不変性。
3.2。 私が含むだろう欠点：
- 遠近法の歪みに対する不変性の欠如。 ある程度までは、これは元の画像を小さな断片に分割し、係数を増やすことで実現できます。 E.
- 大きな画像で画像を検索する機能ではありません。
*アルゴリズムを完成させるために、アルゴリズムの欠陥を示すコメントに注意してください。3.3。 不確実性
プログラマーではないので、作業中のアルゴリズムを独立してチェックする機会はありません。 Habrコミュニティのメンバーの1人がこのアルゴリズムをプログラムで実装し、実際にテストできるとうれしいです。
このようなチェックの後、最も重要なパラメーター「精度」を私のアルゴリズムの長所または短所に帰することができます。
参照：
1.「
角度 検出器 」-
光源2.「
Androidオペレーティングシステムでのアルゴリズムの導入による特定の画像ポイントの記述子の比較分析 -MV Patin
3.「
キャッシング 」、wikipedia.org
PSアルゴリズムの2番目の（改良された）バージョン：
habrahabr.ru/post/320994