「Yandex Internet Mathematics-2011」という問題の解決策。 画像の視覚的類似性の判定

2011年4月から5月にかけて、YandexはYandex Internet Mathコンテストの別のラウンドを開催しました。 ツアーのテーマ：「画像の視覚的類似性の判定」。

受賞者の発表に関するニュースを公開し、チームによるタスクの解決策であるLookLikeItをすぐに説明することを約束しました。LookLikeItは最終評価で12位になりました。



そして今、その時はまったく正しくありません！

はじめに

Yandex Internet Mathは、2011年に5回開催されたYandexが主催する一連のコンテストです。 競争の主な内容は、実際のデータに基づいて実際の問題を解決するための競争です。 2011年の競争の課題として、一連のパノラマの余分なフレームを決定するために、画像の視覚的類似性の分析が選択されました。 この記事では、問題のステートメント、その解決策の方法論、アプローチについて説明します。これらは、競争の枠組みで私たちが適用したものであり、結果の分析でもあります。

コンテストのデータは、Yandex.Mapsサービスのパノラマ画像から取得した画像でした。 コンテストは2つのステージに分かれていました-トレーニングステージには5つの画像がそれぞれ6,000エピソード（各画像の寸法は300x300ピクセル）が含まれ、最終ステージには6,000エピソードが5つの画像からなる別のセットが含まれていました。 各シリーズの基礎は、部分的に重複したパノラマの連続したフラグメントです（間違った順序で）。 一部のシリーズには、他のパノラマシリーズの1つまたは2つの追加ショットがあります。 参加者のタスクは、自動メソッドを使用してシリーズの余分なフレームを決定することでした。 トレーニングセットの6000シリーズの中で、1000はトレーニングセットであり、どの写真が不要であるかが示されました。

シリーズの例：







競争の方法論は次のとおりでした。 チームは質問への回答を作成しました：トレーニング段階での5000シリーズの5枚の写真の各シリーズで余分な写真は何ですか（最初の1000シリーズは教育的であり、答えがわかっていたため、1001から6000まで）。 この回答は、各シリーズの追加の写真を示すテキストファイルの形式で作成されました。 このファイルに基づいて、Yandexサーバーは分析結果の公開評価を計算しました。 最終段階では、これまでに知られていなかった6,000のシリーズが提案されました。 予備段階は2か月続き、最終段階はちょうど1日続きました（2011年5月16日から17日まで）。

結果を評価するための主要な指標は、正しく分類された写真の割合です（パノラマを構成する写真と不要な写真の2つのクラスが考慮されます）。 評価は、式に従って実行されました。

（Tp + Tn）/（P + N）、ここでPはパノラマに関連する画像の数、Nは余分な画像の数、Tpはシステムがパノラマに正しく割り当てた画像の数、Tnはシステムが正しく割り当てた画像の数余分なクラス。 したがって、システムがすべての写真をパノラマクラスと不要なものに完全に正しく分割した場合、評価は1になります。

メトリックを分析した後、一連のエラーがさまざまな方法で結果の全体的な評価に影響を与える可能性があることが明らかになります。 図1に示すシリーズを考えてみましょう。2,3,4,5枚の写真が同じパノラマにあり、1枚目が不要であるとシステムが言っている場合、推定値は（3 + 1）/（3 + 2）= 4/5になります。 2番目、3番目、4番目の写真が同じパノラマにあり、1と5が不要であるという結果がシステムから得られた場合、推定値は（1 + 0）/（3 + 2）= 1/5になります。 これからわか​​るように、システムの設計時に考慮する必要があるエラーの種類によっては、他のエラーよりも全体的なスコアが著しく悪化する可能性があります。

問題を解決するためのシステム開発の主なタスクは、2つの画像が同じパノラマの一部であるかどうかを判断し、これらのメトリックに基づいて各シリーズの結果の回答を作成する決定サブシステムを作成することを可能にするメトリックを決定することでした

指標

2つの画像が同じパノラマに属しているかどうかを判断するために、さまざまな状況で使用されるいくつかのタイプのメトリックを開発しました。 1つのシリーズの画像はペアで比較されます。 これらのメトリックをさらに詳しく検討してみましょう。

1.オーバーレイメトリック

問題の声明は、1つのパノラマからの画像が部分的にオーバーラップするという条件を述べました。 これは常に当てはまるわけではありませんが、ほとんどの場合、実際、重複が発生しています。

部分的に重複した画像を特定するために、我々はその本質が以下の通りである方法を開発しました。 2つの画像は、50ピクセルのオーバーレイウィンドウ幅で互いに重なり合っています。

結果のウィンドウでは、各ピクセルについて、RGBコンポーネントを法として差が計算されます。その後、R、G、Bの値の差が各コンポーネントで20より小さいピクセルの相対数が計算されます。これらのピクセルを「黒」と呼びます。 この数値は、互いに重ね合わされたピクセルが色にどれだけ近いかを示し、したがって、1番目と2番目の画像の重ねられた部分の近接度を決定します。

その後、ウィンドウは6ピクセルシフトされ、オーバーレイウィンドウの幅が150ピクセル（イメージの半分）に増加するまで手順が繰り返されます。 同じ手順を同じ画像に対して、反対側が重なり合って繰り返します（最初に、最初の画像の右側が2番目の画像の左側に、次に反対に、2番目の画像の右側が最初の画像の左側に）。

たとえば、画像について考えてみましょう。



これらの画像の反復オーバーレイプロセスと、オーバーレイウィンドウでのピクセル差の計算を示します。



オーバーレイの繰り返しに応じた暗いピクセルの相対的な数の変化のグラフ：



ご覧のとおり、13回目の反復で重要なピークが得られました。これは、オーバーラップにできるだけ正確に到達したことを意味し、これも図で確認できます。

この手順の後、一連の画像の各ペアに対して、「黒」ピクセルの相対数の値を持つ2つのベクトルがあり、それらの最大値を探します。 これは、部分的なオーバーラップによる2つの画像の近接度のメトリックです。 つまり、2つの画像が重なったときにどれだけ一致するかを判断します。

このメトリックの明らかな問題は、最初は暗い画像（夜景など）です。これは、暗い領域を暗い領域に適用すると、画像に実際のオーバーラップがないにもかかわらず、R、G、Bの値の差が小さくなるためです。 。 この問題を解決するには、手順を開始する前に、各画像の暗いピクセルの総数をチェックし、十分な大きさ（画像の70％以上）である場合、そのような系列はこのメトリックを使用して分析されません。 そのようなシリーズの例：



このようなメトリックを適用するときの2番目の問題は、画像のオーバーラップが正確ではないが、特定の歪みがある画像です。

-有望な：



-オーバーラップでのオブジェクト（車）の外観：



-重複部分に非常に詳細なオブジェクト（木、建物の複雑なテクスチャ、グレア）が存在します。これらのオブジェクトは、理想的には互いに「重複」できず、上記の手順を適用したときに相対的な「黒」ピクセルが多くなります。



さらに、同じパノラマの写真の前提条件として問題の説明で部分的な重複が言及されているという事実にもかかわらず、写真に重複がないかなり多くのエピソードがありました。



この場合、詳細化メトリックが使用されました。これについては、後で説明します。

オーバーレイメトリックに関連する3番目の問題は、2つの画像に部分的な重なりがあるかどうかを判断できるメトリックしきい値（2辺からオーバーレイを渡すときの「黒」ピクセルの最大数）の決定でした。

この問題の最初の解決策は、静的しきい値の選択でした。その値は、トレーニングサンプルの特定のステップで特定の範囲の値を経験的に選択することによって選択されました。 したがって、トレーニングサンプルの公開評価の結果が最大になる静的しきい値の特定の値を取得しました。 ただし、このアプローチは十分に効果的ではないことは明らかです。同じしきい値は異なるシリーズの写真にうまく適合しないためです（たとえば、シリーズAでは、2つの写真が重なり合っており、メトリックの結果は95％です。非常に詳細なオブジェクトがあり、メトリックの結果は70％でした。これはシリーズAの95％に比べて非常に小さいですが、シリーズB内の他の写真と比較するとはるかに大きくなる可能性があります。 さらに、しきい値を選択したトレーニングサンプルはかなり小さく、十分な代表値ではありませんでした。

これらの問題に関連して、オーバーレイメトリックによって近接性を判断するためのしきい値は、シリーズごとに個別に計算する必要があることが決定されました。 まず、一連のすべての写真のメトリック値がペアで計算され、その後、これらの推定値の平均二乗が決定されます。 二乗平均値は、高すぎるまたは低すぎる値が表現力があり、2つの写真が同じパノラマに属し、またはその逆であり、それらの差が大きすぎるため、これらのピークがシリーズの平均スコアに強い影響を与えることを考慮して選択されました平均スコアを計算するときは正方形。 その後、各評価が平均評価と比較され、それよりも大きい場合（ある程度のマージンはある）、写真は同じパノラマに属していると見なされます。 そのような予備がない場合、これは、シリーズのすべての写真がほぼ同じ値を持つことを意味します。これは、このシリーズに余分な写真がないか、メトリックが機能しなかったため、結果をさらに明確にする必要があることを意味します

各シリーズの動的なしきい値決定アプローチを使用して、公開評価の結果は10分の2以上改善されました。

2.スペクトル相関メトリック

このメトリックは、1つのパノラマからの画像のオーバーラップが明示的でなく、オーバーレイメトリックを使用して不十分に決定されたシリーズに使用されました。 十分な数のエピソードシリーズで、パノラマの画像と過剰な画像は完全に異なる条件（季節、時刻、ビュー構造（建物や森林など）など）で撮影されたため、色の分布と画像の明るさ。



したがって、色の分布の類似性/差を評価するために、シリーズの各画像を10値のスペクトル（ヒストグラム）にレイアウトしました：虹色（赤、オレンジ、黄色、緑、青、青、紫）と中立色：白、グレーそして黒。 虹色の場合、HSV色空間は色相成分とともに使用され、0〜360の範囲にあり、ピクセルのトーンを反映します。 ただし、このアプローチでは、色の範囲の下にあるそれぞれの輝度成分を考慮せずに、図に示すように、白、灰色、黒の色を含めます。



したがって、白、グレー、黒を除外するには、RGBスペースの各ピクセルのコンポーネントがまずこれらの色の範囲に属しているかどうかを確認します（白の場合、すべてのコンポーネントは225-255、グレーの場合：125-225、黒の場合：0- 30）。

スペクトルの各成分は、画像内の1つまたは別のサブ範囲の相対的な色数を意味します。つまり、画像内の色の分布を示します。 次のようになります。



各スペクトルは10個の値のベクトルであるため、ピアソン相関係数を使用して、一連の画像のペアのスペクトル間の関係の存在を判断しました。



このアプローチは非常によく証明されており、色の分布が類似した画像の相関の値は急速に成長しました。



このメトリックの重要な問題は、オーバーレイメトリックと同様に、2つの画像が同じパノラマに属していることを示すために、2つの画像の相関係数の値を超えるしきい値の定義です。 この問題を解決するために、シリーズの平均二乗相関値によって各シリーズのしきい値を動的に決定する方法も使用しました。

2番目の問題は、パノラマ写真と不要な写真の色の分布が非常に近い（たとえば、空と緑の色）ため、誤検出が発生することです。



3番目の問題は、1つのパノラマからの画像であり、その上に大きなオブジェクト（通過車など）が表示され、画像の半分に達することがあります。 この場合、そのような画像のスペクトル分布は劇的に変化し（たとえば、パノラマの他の画像にはなかった多くの青が現れます）、相関はそのスペクトルと他のパノラマ画像のスペクトルとの依存関係を示すことができません。

3. SURF記述子メトリック

SURF（Speeded Up Robust Features）メソッドは、画像を認識し、その類似性を判断するための最も効率的で最速の最新のアルゴリズムの1つです。

この方法の主なポイントは、画像上でいくつかのキーポイントとそれらの周りの小さな領域を強調表示することです。 キーポイントは、ポイントの大部分からそれを大幅に区別する特定の兆候があるようなポイントと見なされます。 たとえば、線の端、小さな円、照明の鋭い変化、角度などです。 画像の小さな領域は遠近法や大規模な歪みの影響をほとんど受けないため、ポイントの周りの小さな領域が選択されますが、小さすぎる領域は情報が少なすぎるため適切ではありません。

SURFメソッドは、ヘッセ行列を使用して特異点を検索します。ヘッセ行列の行列式は、輝度勾配の最大変化点で極値に達し、線のスポット、角度、およびエッジを適切に検出します。 キーポイントの例：



この方法はスケール不変であり、画像平面内で回転し、ノイズを発生させ、他のオブジェクトと重なり、明るさとコントラストを変更します。 つまり、最初の2つのメトリックで問題があったシリーズに最適です。

2つの画像を比較するときのメトリック値は、共通のキーポイントの数です。 ポイント数が10を超えると、ほとんどの場合2つの画像に共通のオブジェクトがあるため、このメトリックには静的なしきい値が使用され、実際には誤検出はありませんでした。

このメトリックにより、視野角の変化が大きく、遠近法や幾何学的な歪みが大きい360度パノラマでスケーリングされた写真を特定できましたが、同時にオブジェクトが残り、キーポイントが残ります。 たとえば、そのようなシリーズでは：





この方法の主な欠点は、計算負荷が高く、その結果、動作時間が長くなることです。 しかし、我々はそれをクラリファイアとして使用し、最も問題があり論争の的になる状況で計算したため、計算の数を最小限に減らすことが判明しました。

このメソッドの実装として、OpenSURF 2.0ライブラリが使用されました。

SURFメソッドの詳細については、注目に値する記事「 永続的画像の特徴の検出：SURFメソッド 」を参照してください。ここから、 メソッドの図と説明をうっかり借りました:)

決定ロジック

特定のシリーズ内の画像をペアワイズで比較し、その長所と短所を分析するためのメトリックを開発し、トレーニングサンプルで一連のテストを実施して、これらのメトリックに基づいて答えを形成する意思決定サブシステムを作成しました：このシリーズではどの写真が不要ですか？

まず、シリーズの可能なオプションを検討します。

1）パノラマの3枚の写真と2枚の写真は不要です。

a）1つのパノラマの追加写真。

b）異なるパノラマからの追加の写真。

2）パノラマの4枚の写真のシリーズで、1枚の写真は不要です。

3）余分なものはありません。

一連の写真を考慮すると、システムは写真付きの2つのセットを作成します：pl。1およびpl。2。 最初に、アルゴリズムはこれらのセットに画像を配信します。これらのセットは、オーバーレイメトリックによって動的しきい値を超えます。 その後、これらのセットにイメージを配布するための次の論理オプションが可能です。 これらのオプションのアクションについて説明します。

1）（0）（0）-このオプションは使用できません。動的しきい値を使用する場合、常にオーバーレイメトリックがこのシリーズ内の2次平均よりも大きい画像があります（オーバーレイメトリックで「マージン」が克服されない場合、シリーズは「マージン」が提供されないスペクトル相関メトリックを使用して設定します）

2）（2）（2）-このオプションは、アルゴリズムが2つの写真が1つのパノラマにあり、2つが別のパノラマにあると判断したが、5番目については何も言えなかったことを意味します。 この場合、次のオプションが可能です。

A）5番目は複数1になり、複数2は不要になります。

B）5番目は複数2になり、複数1は不要になります。

C）5番目は両方のセットに入りますが、余分なものはありません。

E）5番目のピクチャがどのセットに属するかを決定するメトリックはないため、このピクチャの相関係数の最大値が最初のセット、2番目のセットのピクチャと決定され、セット1およびセット2のピクチャの相関係数も分析されます。スペクトル相関：

-複数の1と複数の2が結合し、5番目の画像が不要になります。

-pl。1と5番目の写真が結合され、pl。2は不要になります。

-複数の2番目と5番目の画像は結合し、複数の1つは不要です。

すべての改良は、スペクトル相関係数のメトリックとSURFメソッドに従って行われます



3）（3）（2）-大多数のケースのトレーニングサンプルでは、​​このオプションはすぐに正しく、明確化する必要がないことが経験的に観察されました（pl。2-不要）。 そうでない場合、エラーはあまりにもひどくなく、結果の全体的な評価に大きな影響を与えません。

4）（2）（3）-前の段落と同様（pl。1-不要）。

5）（3）（0）-この場合、次のオプションが可能です。

A）両方の写真が不要です（オプション（3）（2））。

B）2枚の写真のうち1枚がパノラマに含まれており、5枚目は不要です（オプション（4）（1））。

C）両方の写真がパノラマに含まれていますが、余分なものはありません（オプション（5）（0））。

すべての改良は、スペクトル相関係数のメトリックとSURFメソッドに従って行われます



6）（4）（0）-この場合、オプションが可能です：

A）5番目の写真はパノラマに含まれていません。つまり、5番目の写真は不要です。

B）5枚目の写真がパノラマに含まれています。余分なものはありません。

すべての改良は、スペクトル相関係数のメトリックとSURFメソッドに従って行われます



7）（5）（0）-オプションなし。 答えは余分ではありません。

結果の評価

この問題は反復的に解決され、ますます複雑なアプローチを適用しながら、公共の評価の価値を徐々に高めていきました。

最も高い結果は、上記の決定によって得られ、予備的な公開評価で0.945に達しました。 最終結果は0.967に増加しました。 最終サンプルの勝者の結果は0.994でした。

1つのシリーズの分析時間は平均で約20秒でした。

最終サンプルの結果がこのように急激に増加する主な理由は、私たちの意見では、シリーズの最終セットがより慎重にチェックされ、コンパイラーに事実上エラーがなかったことであり、コンパイラーは予備段階のシリーズでしばしば発見されました。

このメトリクスはあまり明確ではなく、その意味はあまり明確ではないため、実際の認識結果はトレーニングサンプルで得られた統計です（そのような統計は、回答が既知であるため、それについてのみ取得できます）。

絶対正解：85.3％; さまざまな種類のエラーを含む不正解：14.7％。

この結果は非常に高いです。 エラーになったシリーズを分析するとき、私たちはしばしば正しい答えを決定できないという事実に遭遇しました（または、正しい答えは、Yandexのそれと一致しませんでした）。

たとえば、シリーズでは：



余分なのは1と4です（ただし、画像2、3、5の間には共通点はほとんどありません）。

そして、このシリーズでは：



最初の写真のみが不要と見なされます。 私たちの意見では、4番目の写真は2、3および5の1つのパノラマに入ることができ、そこには入らず、これが非現実的であると判断できます。



説明した決定の主な欠点である結果を分析した後、メトリックの数が不十分であり、意思決定の厳格な論理構造を考慮します。 実際、トレーニングサンプルは、特定の方法の迅速な評価を取得し、統計を収集するためにのみ使用され、システムでは機械学習は提供されませんでした。 しかし、予備段階で最初の5 KEで行われたいくつかの主要なチームは、システムが予備データセットで再訓練されすぎたため、最終サンプリングで結果を大幅に削減しました（0.975から0.941）。



あなたが興味を持っていて、この記事の終わりに到達したことを願っています:)。 他のソリューションの説明（受賞者の決定を含む）は、 Yandex Clubにあります。