search

e4exp / paper_manager_abstract

0 stars 0 forks source link

Large-Scale Unsupervised Object Discovery #525

Open e4exp opened 3 years ago

e4exp commented 3 years ago

既存の教師なし物体探索（UOD）のアプローチは、大規模なデータセットに対応するためには、性能を低下させる近似を行わなければなりません。 本研究では、UODをランキング問題として新たに定式化し、固有値問題やリンク分析に用いられる分散型の手法を利用することを提案します。 COCOとOpenImagesを用いた大規模な実験により、各画像の中から1つの目立つ物体を探すという単一物体探索の場合、提案したLOD（Large-scale Object Discovery）アプローチは、中規模データセット（最大12万画像）では最新の技術と同等かそれ以上の性能を発揮し、170万画像まで拡張できる唯一のアルゴリズムよりも37%以上優れていることが分かりました。 また，各画像に複数の物体が存在する場合には，2万枚から1.7万枚のデータセットにおいて，提案LODは他の手法と比較して平均精度（AP）を14％以上向上させました．

e4exp commented 3 years ago

image

1 はじめに

本論文では，大規模な画像コレクションの中から，人手によらずに著名なオブジェクトを特定するという問題に取り組んでいます． このプロセスは，教師なしオブジェクト探索（UOD）として知られています． UODの初期のアプローチは，同じカテゴリのオブジェクトを含む画像のクラスタを見つけることに主眼を置いていた[22, 58, 61, 62, 64, 69]． いくつかのアプローチ[58, 61, 62]では，画像中のオブジェクトの位置を出力することもできるが，その評価は，オブジェクトのクラスが特徴的な小さなデータセットに限られている． 最近の技術[8, 66, 67]では、より多様な画像コレクションの中から、画像のリンクや個々のオブジェクトの位置を発見することに焦点を当てている。 これらの技術は、組み合わせ最適化に依存しており、異なる画像に関連付けられた提案のペアについて計算された類似性スコアが与えられると、何千もの領域提案候補[46, 65, 67, 83]の中からオブジェクト、あるいはオブジェクトのバウンディングボックスを選択します。 これらの技術は有望な結果を得ることができるが，その計算コストと本質的に逐次的な性質のため，適用できるデータセットのサイズが制限される． 探索空間のサイズを小さくすることで、最先端のアプローチ[67]を拡張しようとした場合、各画像内の複数のオブジェクトを発見する能力が損なわれることが明らかになった。 UODに対する他のアプローチは、画像をオブジェクトに分解することで画像表現を学習することに焦点を当てている[5, 12, 23, 43, 47]。 これらの手法は、大規模な自然画像コレクションには対応しておらず、主に制約のある環境下での単純な形状を含む小規模なデータセットに焦点を当てている。

我々は、大規模な自然画像コレクションに取り組むために、UODの新しいアルゴリズムを提案する。 8, 32, 66, 67]と同様に、我々はオブジェクトの位置をバウンディングボックスの形で見つける。 これらのアプローチとは対照的に、UODは、提案が他の画像の領域との類似性に基づいて順序付けられ、上位の領域が発見されたオブジェクトとして返される、ランキング手順として鋳造されます。 その結果、固有値問題やリンク分析[48]で利用可能な多くの手法を適用して、従来よりもはるかに大きなデータセットでUODを解くことができる（図1）。 1つ目はUODの目的[66, 67]を地域提案グラフ上の固有値問題として再定義したもの、2つ目はUODに対するPageRank[4, 48]の適用性を検討したもの、そして最後のバリエーションは他の2つを組み合わせて、固有値問題の解を用いてPageRankをパーソナライズするLOD（for large-scale object discovery）と呼ばれるハイブリッド・アルゴリズムにしたものです。 LODは、非常に大きなデータセット上でのオブジェクト発見に、高速で分散型のソリューションを提供します。 4.1節と表1に示すように、LODの性能は、1つのオブジェクトを発見する場合、120,000枚の画像を扱うデータセットでは最新のアルゴリズムと同等かそれ以上であり、1.7M枚の画像を扱うことができる唯一のアルゴリズムよりも37%以上優れています。 また、マルチオブジェクト探索では、2万枚から1.7M枚のデータセットにおいて、LODは既存のすべての技術を大幅に上回りました。 LODは、画像間の関係性の発見（画像をクラスに分類するなど）を明示的に扱っていませんが、後処理としてカテゴリを発見できることを実証しています（項4.2参照）。 これまでのところ、UODの最も優れたアプローチは、教師ありの領域提案や特徴を使用しています。 また、4.1節では、自己教師付きの特徴量がUODの性能を向上させることを初めて示しました。 我々の主な貢献は以下のようにまとめられる。

e4exp commented 3 years ago

2 問題提起と関連研究

2.1 問題提起

それぞれがr個の領域提案[66, 67]を持つn個の画像のコレクションを考える。我々は，提案のペアがどれだけ似ているかということ以外の情報がなくても，これらの提案のうちどれがオブジェクトに対応するかを見つけ，似たオブジェクトを含む画像をリンクさせたいと思う． この問題は，教師なしオブジェクト探索（UOD）として知られており，画像をノードとして表現したグラフ上の最適化問題[67]として定式化できる． p, q = 1, 2, ... ...nに対してe_pq∈{0, 1}とする。 ここで，e_pq∈{0.1} for p, q = 1, 2, ... , n は，2つの画像がグラフ内で接続されているかどうかを示す2値変数の集合であり，画像pとqが類似した視覚的コンテンツを共有している場合，epq = 1とする． 同様に，p = 1, 2, ... ... , n および k = 1, 2, ... ... に対して x^k_p∈{0, 1} とする． rを指標変数とし、画像pの領域提案kが近傍と共有するビジュアルコンテンツに対応する場合にx^k_p = 1とし、x_p = (x^1_p , ... , x^r_p ) T とする。ここで，物体発見問題は，組合せ最大化問題として定式化することができる．

image

ここで，Spq∈R^r×rは行列であり，そのエントリS ^kl pq ≥ 0は，画像pの領域kと画像qの領域lとの間の類似性と，それぞれの領域の顕著性を測定し，N (p)は画像pの潜在的な高類似度の近傍集合であり，νとτは，それぞれ，画像内のオブジェクトの最大数とその近傍の最大数に対応する事前定義された定数である． UODに対する以前のアプローチ[8, 66, 67]では，(C)の凸型緩和を双対領域で解くか，あるいはそのバイナリ変数xpとepqに対してブロック座標上昇法を用いる． 類似性スコアS kl pqは、通常、[8]のProbabilistic Hough Matching (PHM)アルゴリズムを用いて計算されます。 このアルゴリズムは、より良い性能を得るために、局所的な外観とグローバルな幾何学的整合性の制約を組み合わせて、領域のペアを比較します。 我々はこの伝統に従い，PHMスコアも使用している(Sec. 4)．

C）で定式化されたUODの目的は、オブジェクト（変数x^k_p）と、それを含む画像を結ぶエッジ（変数e_pq）の両方を見つけることです。 67]は、(C)に対して、変数xpとepqを順次更新して目的を最適化するブロック座標上昇アルゴリズムを提案している。 このアルゴリズムは、データセット全体で実行する前に、画像コレクションの一部で実行してrをわずか50に減らすという、思い切った近似で(C)のスケールアップを試みています。 しかし、大幅に削減された領域提案のセットを使用すると、複数のオブジェクトを発見する能力が妨げられます（表1）。 さらに、このアルゴリズムは、本質的に逐次的な性質を持っているため、数百万枚の画像を持つデータセットに拡張することができない。

そこで、UODの2つ目の目的をやめて、完全に連結されたプロポーザルの重み付きグラフのみに頼ることにしました。 これにより、UODをランキング問題[4, 30, 34, 36, 51]として再定式化することができ、固有値問題やリンク分析に利用できる大規模な分散ツールを利用することができます。 ここでは、2つの異なるランキング定式化を検討します。 1つ目（Q）は二次最適化問題に取り組み、2つ目（P）はよく知られたPageRankアルゴリズムに基づいています[4, 48]。 これらの2つのアプローチを組み合わせて、大規模データセットで最良の結果が得られる共同形式(LOD)を提案する。 詳細は第3節と第4節をご覧ください。

e4exp commented 3 years ago

3 提案されたアプローチ

3.1 二次定式化

リージョンプロポーザルを，N = nr個のノードを持つグラフGで表現することにしましょう（ここで，nは画像の数，rは各画像のプロポーザルの数）． 各ノードはプロポーザルに対応し，画像pとqのプロポーザルkとlにそれぞれ対応する任意の2つのノード(p, k)と(q, l)は，重みS kl pqのエッジで結ばれています． G は，p, q = 1, ... n の r × r ブロック Spq からなる N × N 対称隣接行列 W で表されます． Spq は，Sec. 2.1 で定義され，p neq q の場合は PHM アルゴリズム [8] で計算されますが，本設定では画像間領域の類似性のみが問題となるため，対角線ブロックはゼロとされます． yi ≥ 0をノードiに対して推定したい重要性の尺度とし、y = (y1, ... , yN ) Tと設定する。 yが与えられたノードiのサポートをzy(i) = P j Wijyjと定義し、zy = (zy(1), ... ... , zy(N))Tを取るようにする。 直感的には、yが与えられたとき、zy(i)は、iとjの間の類似性Wijとそのノードの重要性yjを考慮して、iがグラフ内の残りのノードjにどれだけ接続されているか（または「サポートされている」か）を定量化する。 我々は，ノードの重要度を可能な限りランク付けする重要度スコアを見つけたい． 次のレンマで示すように，この「鶏と卵」の問題は，簡単な解決策があることがわかる．

Lemma 1. Wが既約である（すなわち、強結合グラフGを表している）とする。 二次最適化問題の解y∗は

image

は、その最大の固有値に関連するWの唯一の単位、非負の固有ベクトルである。

これは古典的な結果で、Perron-Frobeniusの定理[15, 50]を用いて証明することができる。 完全な証明は付録にあります。 我々の文脈では、いくつかの提案類似性がゼロである可能性があるため、Wは一般的に既約ではない（すなわち、すべてのペア（i, j）について、W m(i, j) > 0となるようなm ≥ 1が存在する）。 PageRank [48]を彷彿とさせるように、Wに小さな項γeeT /Nを追加します。 eはR Nのすべてのエントリが1に等しいベクトル、γ = 10-4で、追加された項が類似性スコアにあまり影響を与えないように意図的に小さく選択し、Wを既約化します。 この項は、結果として得られるランキングが一意であることを保証するもので、PageRankの類似項と同じ目的を持っています。 なお、y ∗ は W の最大の固有値 λ ∗ と関連しており、この固有値は Perron-Frobenius の定理により正であることから、λ ∗y ∗ =W y∗ =zy∗ となります。 したがって，各ノードの重要度スコアy∗ iは，正の定数まではその支持率に等しいので，これを使ってノードを任意にランク付けすることができる。 (C)の画像のグラフが完全であると仮定した場合，(C)と(Q)は密接に関連する問題であることに注意してほしい． この場合、(C)はmaxx∈{0,1}N x T W x, s.t., for all p from 1 to n, Pr k=1 xr(p-1)+k ≤ νと書くことができる。 ここでは、xi（i = 1, ... , n）を積み重ねてベクトルxにしています。 したがって、(Q)は、(C)の連続的な緩和と見ることができます。 この緩和では、二値変数が連続的なものに置き換えられ、プロポーザルと元画像を結びつける線形制約が取り除かれます。 Gのノード上のWの支配的な固有ベクトルy∗によって引き起こされる順序は、リンク分析のPageRankアプローチ[4, 48]を思い起こさせます。 この発言は、次に述べるランキングによるUODへの第2のアプローチにつながります。

3.2 PageRankの定式化

PageRankを定義する際、[48]は(Q)のような最適化問題から始めるのではなく、ランキングを直接固有値問題として定式化している。 37] に従って、A はマルコフ連鎖に関連したグラフの遷移行列を表し、aij ≥ 0 がノード j からノード i に移動する確率となります。 定義[4, 48]により、行列 A の PageRank ベクトル v は、行列 P の最大（単位）固有値に関連する唯一の非負の固有ベクトル v であり、P は次のように定義されます。

image

ここでβはダンピングファクターである。 ここで、いわゆるパーソナライズド・ベクトルであるuは、e T u = 1となるようなR Nの要素である。 先に述べたように、第2項は、Pが既約であることを保証し、PerronFrobeniusの定理により、固有ベクトルv ≥ 0が一意となるようにしている[38]。 ベクトルuは，通常，e/Nに等しいとされるが，特定のノードをより重要視することでランキングを「パーソナライズ」するためにも使用できる． これにより、次節で提案するハイブリッドな定式化が可能となる。 (Q)と(P)は密接に関連しており、vベクトルは二次最適化問題の解と見なすこともできます[45]。 この形式的な類似性に加えて，2つの定式化の目的も似ています． 48]を引用すると、「バックリンクのランクの合計が高ければ、ページは（PageRankによると）高いランクを持っている」ということになります。 (Q)と(P)の両方の解は、最大の固有値に関連する固有ベクトルとして、サポート関数に基づくランキングを提供し、power iterationアルゴリズムで見つけることができます[68]。 このアルゴリズムは、行列とベクトルの乗算しか行わないため、分散型の方法で効率的に実装することができます。

3.3 (Q)を使ってPageRankをパーソナライズする

上記の議論は、2つのアプローチを組み合わせることを提案しています。 そこで、(P)のパーソナライズされたベクトルを生成するために、(Q)の最大化を使用することを提案します。 (Q)と(P)は地域をランク付けするための2つの異なる最適化問題であり、これらを組み合わせることで最終的なパフォーマンスを向上させることができます。 直感的には、(Q)で与えられた高得点のリージョン提案は信頼性が高く、これらの上位得点の提案の「フィードバック」に基づいて、他のリージョンの「オブジェクト性」をより正確にランク付けできるはずである。 (Q)の解からパーソナライズド・ベクトルを以下のように計算する。 係数αが与えられると、各画像の上位の領域が候補として選ばれ、次にこれらの候補の中で上位α％の領域が選ばれます。 正しい確率の高いリージョンだけが有益であるため、αを十分に小さく選び（Sec.4参照）、最も正しい可能性の高いリージョンだけを選択する。 選択された地域のセットが与えられたとき、パーソナライズされたベクトルuは、ui = 1/K（Kは提案iが選択された場合の選択された地域の総数、それ以外はui = 0）のL1正規化された指標ベクトルです。 パワー反復アルゴリズムの初期化v0をuに設定して、(P)を(Q)が見つけた信頼できる地域にさらに偏らせる。 以下では、このハイブリッド・アルゴリズムをLarge-Scale Object Discovery (LOD)と呼ぶことにする。