コンペティション「インターネット数学：Yandex.Maps」-参加の経験と受賞アルゴリズムの説明

コンテスト「 インターネット数学：Yandex.Maps 」の終了から1年以上が経過しましたが、このコンテストで勝利をもたらしたアルゴリズムについてはまだ質問されています。 Yandexは最近、次の「 インターネット数学 」の発表を発表したことを知り、昨年の参加の経験を共有し、アプローチについて説明することにしました。 開発されたアルゴリズムは、たとえば次のように、一連のパノラマ画像内の余分な画像を99.44％の精度で正しく識別することができました。







この記事では、アルゴリズムの主なアイデアを説明し、興味のある人にその詳細を提供し、学んだ教訓とそれがどのように起こったかについて話します。



ソリューションのソースコードはgithub （ OpenCVを使用したC ++）で入手できます。

競合タスクの説明

2011年、Yandexはコンテスト参加者にコンピュータービジョンの興味深いタスクを提供したため、この分野に特化した当社が参加しないことは罪です。 タスクは、Yandex.Mapsの一連のパノラマ画像から余分な画像を検索することでした。 各シリーズでは、5つの画像が与えられ、そのうちのいくつか（3、4、または5つすべて）は1つの場所でほぼ同時に作成され、残りは冗長でした。 たとえば、上のシリーズの画像1、3、および5はパノラマを構成し、画像2および4は不要です。 合計で6000のエピソードが提供され、それぞれのエピソードで追加の写真を見つける必要がありました。

最初から最後まで

企業ニュースレターからコンテストについて学ぶと、私たちはそれぞれデータをダウンロードし、数日かけて写真を見つめました（何かすることがありました-合計 6000 x 5 = 30,000枚）、一人で勝つことを望みました。 すぐに、タスクが一見したほど単純ではないことが明らかになりました。 したがって、私たちは集まり、アイデアを話し合い、可能な共同の努力を交渉することにしました。 結局のところ、問題を解決するために非常に異なるアプローチがあり、同じチームで互いに補完することは素晴らしいことです。 そのため、すべてを標準スキームに従って実行しました。共通のコードリポジトリを作成し、アルゴリズムの精度をテストするためのインフラストラクチャを作成し、それぞれが彼のアイデアに取り組み始めました。 適切な記事を検討し、定期的にブレーンストーミングセッションを開催し、新しいアイデアを試し、アイドルアイデアを破棄しました。



そして、最終日が来ました-競争の条件によると、最終日にYandexはアルゴリズムを実行して1日で答えを得る必要がある新しいデータセットを発行しました。 私たちのチームは仕事で眠れない夜を過ごしていたので、優先順位はまだチップと生産的なプログラミングに必要なすべてを購入することでした。 最終的なデータセットにアクセスした後、アルゴリズムの最適なバージョンを起動し、30,000個の画像の新しいバッチの調査を開始し、最後までデータの新しいプロパティを考慮するための新しいアイデアを生成しました（ただし、午前5時までにいくつかのナンセンスが判明しましたが、それ以来、ジョークの理由があります）。 すべてが無駄ではありませんでした。数日後、私たちのチーム「Mythical Nizhny Novgorod」がコンペティションの勝者になったことを知りました！



次に、どのアルゴリズムになったのかについて説明します。

アルゴリズムの重要なアイデア

そのため、タスクは一連の画像をグループに分割することです：目的のパノラマと追加の画像。 そのようなパーティションを見つけるには、それらが任意の画像ペアで同じパノラマに属しているという事実の妥当性を評価できる必要があります。 これを行うために、補完的なアプローチに基づいて、画像のペアに対して2つの類似性尺度を導入しました。画像の色ヒストグラムの比較と、画像内の共通部分の検索です。 これら2つの測定値を1つに組み合わせ、結果の測定値を使用して画像をグループに分割しました（クラスタリング）。 それぞれのアプローチの測定値を別々に使用することもできますが、この組み合わせにより、それぞれの長所を組み合わせることができます。



ヒストグラムを使用すると、ある画像の色の頻度を別の画像の頻度と比較できます。 タスクの説明によると、同じパノラマ内の写真はカメラの近接位置から一度に1つのシーンを描写するため、それらの色特性は通常互いに類似しており、追加の画像については通常異なります。 したがって、ヒストグラム間の距離は、画像の近接度の適切な推定値を提供します。 たとえば、記事の冒頭に示したシリーズの余分な画像はパノラマ画像よりもはるかに暗いため、過剰な画像のヒストグラムでは暗い色が優勢になり、これらのヒストグラムはパノラマ画像のヒストグラムからは遠くなります。



2番目のアプローチである画像内の共通部分の検索では、2つの写真が十分に交差している場合、たとえば同じオブジェクトがそれらに出会った場合に、2つの写真が同じパノラマに属していると判断できます。 これは、コンピュータービジョンで一般的なアプローチを使用することで実現されます。特徴的なキーポイントは、2つの比較画像で検出され、その後、たとえばこれらのポイントの近傍を比較することで、それらの対応を検索します 多くの類似した近隣を見つけることができた場合、それらは同じオブジェクトに関連している可能性が高く、これらは同じシーンの2つの画像です。 このアプローチでは、近接性の尺度は、類似した近隣の数です。 たとえば、このアプローチの動作を図に示します。 1および2。





図 1.写真には同じ建物の部品が含まれているため、共通部品の検索で正しい分類が得られるシリーズの例。 この場合、画像1と4のカラーヒストグラムは他と非常に異なるため、ヒストグラムアプローチではこれら2つの画像は不要であると見なされますが、これは実際には正しくありません。





図 2.アルゴリズムによって検出された対応するキーポイント。



これらの2つのアプローチは相互に補強しています。 ヒストグラムアプローチは、同じパノラマの画像間に共通部分や共通部分がない場合でも機能します（図3の例を参照）。 ただし、場合によっては画像間に交差点がありますが、残りの部分の色は非常に異なります（たとえば、太陽が雲の後ろに沈んでいる）。 この場合、ヒストグラムは互いに離れており、共通部分を検索すると、これらの画像がわずかに重複しても同じパノラマに属していると判断される場合があります（図1および2の例を参照）。





図 3.同じパノラマ（3、4、5）の写真の間に共通のキーポイントがある領域はないが、色ヒストグラムのために正しい分類が得られるシリーズの例（画像1と2は不要です ）。



実験で示されているように、ほとんどの正解はヒストグラムアプローチのみを提供できます。2番目のアプローチを追加するのはごく一部のケースのみで、分類が改善されます。



コンピュータビジョンとこれらの2つのアプローチの詳細に興味がある人のために、次の2つのセクションを作成し、他のすべての人が2つのアプローチと結果の 組み合わせに進むように招待されています。

ヒストグラムアプローチの詳細

実装中に、 YCrCb色空間が使用されました。これは、輝度成分が明確に強調表示されているためです。 これにより、このコンポーネントのビン（グループ化間隔）の数を減らして、照明と影の変化に対するアルゴリズムの安定性を高めることができます。



また、ヒストグラムを作成するためのこれら3つのコンポーネント（Y、Cr、Cb）に、色の空間的配置を考慮に入れるために画像のピクセルの縦座標をもう1つ追加しました。 このアイデアにより、通常同じ高さにあるオブジェクトの色をより正確に比較できます。道路は道路と、草は草と、空は空と比較する必要があります。 このような画像の横縞への分割は、競技データでは同じパノラマ内の画像が互いに主に水平方向にずれているという事実のために導入されました。



したがって、4次元のヒストグラムは、明るさの12ビン、2つの色成分のそれぞれの256ビン、ピクセル縦座標の4ビンで構成されました。



ヒストグラム間の距離を計算するために、それらの交差点（ ヒストグラム交差距離 ）が使用されました。 同じ解像度の画像の場合、この距離は実際には2つの画像間の類似したピクセルの数を反映します。

ローカル機能に基づいたアプローチの詳細

コンピュータビジョンで最も成功した方法の1つは、画像内の一意のローカルフィーチャ、たとえば、角の塊や塊（小さな均一な領域）を使用することです。 このアプローチは、シーンが十分なテクスチャである場合、つまり、そのようなローカルフィーチャが多数含まれている場合に適用できます。 Yandex.Mapsの画像はテクスチャのストリートシーンを表しているため、このアプローチの適用は合理的です。 ただし、競合するデータセットにはいくつかの困難があります。画像の解像度は低く（300x300ピクセル）、多くの場合、テクスチャ以外の大きな領域（アスファルト、空など）があります。 このような低解像度では、局所特徴の検出器の再現性が低くなります：画像の1つで見つかったキーポイントは、同じパノラマの別の画像では検出されないことが多く、画像間に対応があると判断することはできません。 これらの問題を解決するために、ローカルフィーチャディテクターのこのようなパラメーターを設定して、画像内の多数のキーポイント（〜10k）を検出します。 ただし、これにより、比較対象の画像の特徴の一意性が低くなり、一致する特徴を検索するときに、誤った一致が見つかることがよくあります。 したがって、正しい一致を選択するために、いくつかの追加のフィルター処理を適用しました。 詳細に移りましょう。

1. ローカルフィーチャの検出器としてFASTを使用しました。これにより、画像内の角度をすばやく見つけることができます。 アルゴリズムがさまざまなカメラ位置でキャプチャされたオブジェクトまでの距離の変化に耐えられるようにするには、異なるスケールのローカルフィーチャを検出する必要があります。 これを行うには、4レベルのガウス画像ピラミッドを使用して画像をスケーリングし、各レベルでFASTを実行し、見つかったキーポイントのセットを結合します。
2. 各画像の重要なポイントについて、周囲の記述子（記述子）を計算します。 SURF記述子を使用しました。これは、よく知られているSIFTよりも高速ですが、同等の品質を持っています。
3. 次に、計算された記述子（実数の64次元ベクトル）を使用して、2つの画像で互いに対応するキーポイントを見つけます。 このため、1つの画像の各記述子について、記述子ベクトル間の距離でL1に沿って別の画像の最も近い記述子が見つかります。 この距離は、標準のユークリッド距離よりもノイズに強くなっています。 膨大な数のローカルフィーチャがあるため、徹底的な検索で最も近い記述子を検索するには時間がかかりすぎます。 したがって、OpenCVに統合されたFLANNライブラリを使用して、最も近い記述子の近似検索を使用しました。
4. 検出されたローカルフィーチャ間の対応は、 クロスチェック信頼性基準によってフィルター処理されます。信頼性基準は、すべての対応のうち1対1のみになります。
5. 残りの対応をy座標でフィルター処理します。一致によって接続されたポイントのy座標が100ピクセル以上異なる場合（パラメーター値は実験的に選択されます）、この対応はfalseと見なされます。 このフィルターは、競合する画像では水平方向のパノラマのみが見つかったという事実によって正当化されます。
6. ローカルフィーチャ間の1対1対応のセットに従って、 RANSACスキームに従ってホモグラフィマトリックスを計算します。 理論によれば、3Dワールドの反転画像が同じ平面上にある場合、（カメラの位置を任意に変更して）画像ポイント間にホモグラフィ変換があります。 非平面オブジェクトの場合、平面からのオブジェクトのポイントの偏差がカメラからオブジェクトまでの距離よりもはるかに小さい場合、ホモグラフィ変換を探すこともできます。 パノラマの競合画像のホモグラフィの検索は、次の事実によって正当化されます。1）平面の存在は、都市のシーンのオブジェクトの特性です。 2）多くの場合、オブジェクトはフラットであると見なすのに十分です。 3）ホモグラフィの計算に必要なRANSAC反復回数は、 基本行列を見つけるのに必要な回数よりも少なくなります。
   
   
   
   RANSACスキームを使用したホモグラフィの検索では、次のホモグラフィ仮説の品質を評価するためにいくつかのヒューリスティックが使用されました。 。 その結果、ホモグラフィが選択され、最大数の内輪が与えられました。
7. 画像間の近接性の尺度として、見つかったホモグラフィマトリックスのインレイの数が取得されます。

多くの写真では、このアルゴリズムが対応する重要なポイントを十分に見つけるには、画像間の小さな交差点でも十分でした。 したがって、説明したアルゴリズムの動作の興味深く、予想外の例を図に示します。 4。





図 4.空に同じ雲が存在することで、写真を1つのパノラマにまとめることができる面白い状況。 このスナップショットのペアでは、大きな影のためにヒストグラムが不安定に感じられますが、ローカルの機能と曇りの天候が状況を保存します。

2つのアプローチを組み合わせる

説明したアプローチにより、画像間の2種類の距離を計算できます。 両方のアプローチを考慮するために、これらの距離を次のように組み合わせます。



d _comb = min（ c * d _hist 、 d _feat ）、



どこで

d _comb-結合距離、

d _histとd _featは、それぞれヒストグラムとローカルフィーチャのアプローチを使用して計算された、間隔[0、1]に正規化された距離です。

c -1未満の係数。ヒストグラムを使用したアルゴリズムの結果により高い優先順位を与えることができます。



2つの距離の少なくとも1つが小さい場合、画像は実際に近いため、2つのアプローチを組み合わせるために選択されたのは、まさに最小関数でした。



同じシリーズの画像間のペアワイズ結合距離を計算した後、これらの画像の単一結合を使用して凝集型階層クラスタリングを実行します。 要素の最大数を持つクラスターは、目的のパノラマとして認識され、残りの画像は冗長です。 このような階層的クラスタリングは、このタスクに非常に自然に適しています.1つのパノラマ内には、互いに近い他のパノラマ画像のチェーンで接続された離れたバラバラの画像が存在する可能性があるためです。この方法では、そのような画像を1つのパノラマに結合できます。

結果

そのため、私たちのアルゴリズムに一生懸命取り組んだ後、彼は最終データセットで非常に良い結果を示しました。99.44％の画像が正しく分類され、競争で1位になりました。 また、勝利を祝うために賞金100,000ドルを獲得します:-)

競争のレッスン

結論として、コンテストに参加することで学んだ、または統合したいくつかの教訓を共有したいと思います。 彼らは私たちにとって間違いなく便利です。

• 友達なしで、私は少しですが、友達とたくさん。 単一のチームに参加することが、コンテスト全体での最良の決定でした。 私たちは誰一人として競争に勝つことはできませんでした。 一緒にアイデアを生成し、多くの異なるアプローチを同時にテストし、それぞれの知識と経験を使用し、お互いをサポートし、インスピレーションを与え、締め切り前の最後の夜に誰も眠らないようにし、午前5時にクレイジーなアイデアを生成し続けました。 そして、一緒に勝利を祝う方が楽しいです。
• 心からの災い（または過剰適合）。 コンテストの開始時に、Yandexはアルゴリズムの予備テスト用のタグ付きデータを提供しました。 しかし、多くのシリーズでは、人にとっても余分な画像を見つけることはほとんど不可能でした（図5の例を参照）。
  
  
  
  
  
  図 5.非常に難しいシリーズの例。 ここで余分な画像は何だと思いますか？
  
  
  答え

  1と3-追加の画像、2、4と5は1つのパノラマを形成します。 よく見ると、余分な写真は今年の別の時期に撮影されました。
  
  
  不溶性シリーズの問題は、コンテストフォーラムの参加者によって提起され、主催者は最終データセットでこれを許可しないことを約束しました。 つまり、最終的なデータセットには、予備的なデータセット以外のプロパティがあります。 したがって、トレーニングおよびテストサンプルは単一の確率分布によって生成されるべきであるという機械学習アルゴリズムの基本的な前提は満たされていませんでした。 したがって、再トレーニングのリスクが非常に高いため、少数の構成可能なパラメーターを持つ最も単純なアルゴリズムを使用することにしました。 実践が示しているように、これは非常に価値のある観察でした。高度な機械学習アルゴリズムを使用する他の参加者が実際に再訓練され、最終データで予備的な結果ほど良い結果を示さなかったからです
• ルートを参照してください。 アイデアをテストし、アルゴリズムの動作と問題を理解し、デバッグするためには、正しい視覚化（最終結果と中間ステップの両方）が必要です。 これにより、タスクとデータの詳細を感じることができ、より明確かつ迅速に適切なソリューションに移行できました。
• 小さい、はい。 問題の解決策は、シンプルなアプローチから始める必要があります。非常に簡単かつ迅速に実装できますが、すぐに比較結果を取得できます（ベースライン）。 さらに、原始的なアプローチでも驚くほど良い結果が得られる可能性があり、タスクの仕様の下でわずかに改善されれば、無敵になる可能性があります。 これは、ヒストグラムで発生しました。主な結果をもたらした非常に単純なアイデアです（ローカルフィーチャにより、分類精度が1％未満向上しました）。 同時に、ヒストグラムを使用したすべての最終データの計算には数分しかかからず、ローカルフィーチャに対するアプローチの結果を数時間待ちました。
• 右側のフック、左側のフック。 さまざまな角度からタスクを攻撃する方が優れています。問題を解決するためのフォールバック戦略を開発し、タスクの発見されたすべてのプロパティに対処できるツールを用意すると便利です。 たとえば、色、勾配とその向き、空間位置、画像間の重なりの有無を考慮したアプローチを試みました。 その結果、分類の精度を向上させるために、見つかったソリューションを組み合わせました。
• 心配しないで、幸せになってください。 プロセスを楽しむことを忘れず、新しいことを学び、お互いにチャットする機会を高く評価しました。 とても楽しく、やりがいのある経験でした。 もちろん、 コンペティションに勝つことは素晴らしいことですが、結果が発表された瞬間ではなく、 コンペティションへの参加中の他の多くの面白い瞬間を覚えています-これは人生のためです:-)

次のコンピュータービジョンコンペティションでお会いしましょう！

Habréの有用な資料

• 別のチームのアルゴリズム： 問題「Yandex Internet Mathematics-2011」の解決。 画像の視覚的類似性の判定
• SURF検出器および記述子の説明： 永続的画像特徴の検出：SURFメソッド
• SIFT検出器と記述子の説明： SIFT記述子の構築と画像マッチングのタスク
• マッチフィルタリングの代替アプローチの説明： ダイナミックマッチグラフを使用した画像間の偽マッチのフィルタリング
• ローカル機能を適用するための標準スキームに関するチュートリアル（検出器+記述子+対応検索+ホモグラフィ）： OpenCV 2.4フラットオブジェクトの認識

記事の著者：

マリア・ディマショヴァ（イッツェーズ、研究エンジニア）、 mdim

イリヤ・リセンコフ（イッツェーズ、研究エンジニア）、 ビリー