大量の画像を用いた特定物体認識手法による一般物体認識

秋山瑞樹

2010年 2月 8日

1 はじめに

1.1 背景

実世界シーンの一般的な画像に含まれる物体に対して、椅子、自動車など一般的な物体カテゴリを言い当てる処理を計算機にさせる「一般物体認識」という研究がある。特定の制限下ではない一般的な画像を認識させる場合、「一般物体認識」の実現はまだ難しいのが現状である。

一方で画像に写っている物体とまったく同一のものが写った画像を、膨大なデータベースから発見する処理は、異なる画像でも物体特有の特徴が取れているならば計算機にとって容易である。まったく同じ物体かどうかを言い当てる処理を「特定物体認識」と言われている。

もし一般物体認識として認識したい画像と類似した画像がデータベースとして登録されているならば、類似画像を高速に探し出し、登録された情報を元に認識が可能になるのではないかと考え、特定物体認識の手法を一般物体認識に適応を試みた。

1.2 目的

本研究では一般に撮影された画像に対して写っている対象の物体を認識することを目的とする。

認識手法として、大量の画像をWeb上から収集、それらの画像から特徴を抽出しデータベース化する。実際に認識をしたいクエリ画像に対して最近傍探索の高速マッチングを用いた特定物体認識の手法から一般物体認識の実現を目標とした。

このようにデータ量で認識の問題を解決するアプローチの研究を目指す。

2 提案手法概要

本研究での大まかな流れとしては以下のようになる。図1はシステムのフローチャートである。フローチャート中の番号はシステムの流れの番号と対応する。

Web上からデータベース用の学習画像収集をする。
すべての画像から局所特徴を抽出しテキストファイルに書き出しデータベース化する。またそれらの特徴がどの画像から抽出された特徴かもデータベース化する。 BoF(Bag of Features)による実験の場合はすべての特徴からコードブック作成後、学習画像のBoFをデータベース化する。
データベースを読み込み、最近傍探索のためのデータ構造としてkd-treeを構築する。
認識対象の未知画像から特徴を抽出する。
得られた未知画像の特徴1つ1つに対して近似最近傍探索、 ANN(Approximate Nearest Neighbor)によって kd-treeから最近傍特徴を高速マッチングする。
選ばれた特徴を持っているデータベースの画像に投票を行う。
未知画像のすべての特徴に対してマッチングを行い、最終的に投票が多かったデータベースの画像のクラスを未知画像の認識結果とする。

図: フローチャート
$\includegraphics[width=1.0\hsize]{img/nagare.eps}$

3 提案手法詳細

3.1 画像収集

画像はクエリ語によってWeb画像検索エンジンを利用して収集した。使用した検索エンジンはGoogle、Yahoo!、 Flickrの3つを利用した。

google、yahoo検索エンジンではクエリ語に対して表示される検索結果に約1000 枚までの限界が設けられているので、クエリ語を変えながらランク順に画像を取得し、flickrではAPIを使い relevance(関連度)のランク順に画像を取得した。

変化させるクエリ後は収集したい画像を下位クラスとしたとき、「下位クラス名」と「上位クラス名 + 下位クラス名」をクエリ語として使用した。さらにそれぞれについて日本語、英語について検索を行い計4種類のクエリ語で検索を行った。例えばバラの画像を集める場合、「バラ」、「花　バラ」、「rose」、「flower rose」といった具合で画像検索を行う。

一つの下位クラスの画像収集に対して、3エンジン*4種類の計12種類での画像検索を行った。

重複が無いように12種類の検索結果を各種類上位から順に画像として保存していくことで、検索エンジンのランキングに基づいて画像を取得した。また、今回の実験では手動で25種類の下位クラスを決め実験を行った。

3.2 局所特徴

局所特徴とは、特徴点オペレータにより画像中の濃淡変化が大きい特徴点を検出し、その特徴点周りの領域を画素値や微分値等により特徴ベクトルにしたものである。この特徴は同一対象であれば、視点変化や回転、スケールの異なる画像であっても、同じ特徴点が検出されやすい。本実験で用いる局所特徴として、SIFTとPCA-SIFTを使用し実験を行った。さらに画像の表現方法として局所特徴の頻出頻度表現で表現するBoF(Bag-of-Features)表現を用いた場合の計3方法で実験を行った。

また巨大な画像の場合画像の長辺が640pixelになるように比率を保ち縮小させてから、局所特徴の検出を行った。

SIFT特徴

SIFT(Scale Invariant Feature Transform) は D.Loweによって考案され、特徴点周りの局所画像パターンを128次元特徴ベクトルで表現し、回転・スケール変化・照明変化に対して耐性のある特徴である。特徴点検出にはDifference of Gaussian(DoG)を使用した。

PCA-SIFT特徴

PCA-SIFTはKeらによって考案されSIFTの拡張手法である。

SIFTで検出された特徴点周辺の41x41の正方形領域に対して勾配情報を求め、3042次元の特徴ベクトルを得る。その特徴ベクトルに対してPCAにより得られた射影行列を用いて部分空間に投影し主成分分析を行うことで36 次元へと圧縮した特徴ベクトルである。

次元数の減少によりマッチング処理、メモリー効率の点で利点がある。

Bag-of-Features

Bag-of-Featuresとは画像を局所特徴の集合と捉えた画像の表現方法である。Bag-of-Featuresの基本的な考え方は bag-of-wordsというテキスト検索のモデルであり、bag-of-wordsは文章中に出現する単語のコードブックをもとに、語順に関係なく文章を単語の出現頻度で表現する方法である。 Bag-of-Featuresでは単語の代わりにベクトル量子化された局所特徴を用いることで画像を局所特徴の集合として考える。

Bag-of-Featuresの作成手順としては以下のような流れとなる。

まず学習画像から局所特徴を抽出する。次に、すべての局所特徴をk個にクラスタリングすることでvisual words と呼ばれる似たような特徴が集まった特徴ベクトルがk個作成し、それらの特徴ベクトルをまとめたものをコードブックと呼ぶ。画像を対象とし、画像一枚づつに対して得られた局所特徴をコードブックのk個の特徴ベクトルのうち最も近い特徴ベクトルに投票を行うことで、出現回数のヒストグラムで画像を表現する。その画像の局所特徴の総数でヒストグラムの各binを割ることによって作成された、正規化されたヒストグラムがその画像に対してのBag-of-Features表現となる。

今回の実験ではk=50000として実験を行った。

3.3 データベース

SIFT、PCA-SIFTによる実験の場合、特徴ベクトルが1行1特徴として書かれた特徴データベースと、特徴データベースに書かれた特徴IDと対応する画像名がかれている画像名データベースの２種類のデータベースを作成した。

Bag-of-Featuresの実験の場合、まず作成したコードブックを元に、各行が画像1枚を表す特徴データベースを作成した。こうして作成した特徴データベースからだと類似コードブック特徴を持つ画像に対して投票が困難である。そこでコードブック特徴ベクトルについての各学習画像の評価値を読み込めるような、転置ファイルを作成した。転置ファイルはコードブックサイズの行を持ち、対応する行のコードブック特徴ベクトルをもつ学習画像名を列として持つ。

SIFT、PCA-SIFT実験では、特徴データベースから木構造を作成し、近似特徴探索で得られた特徴IDをもとに、学習画像を画像名データベースから探索することで投票を行う。 BoF実験では、コードブックから木構造を作成し、転置ファイルをから学習画像に対して投票を行う。

3.4 特徴探索

クエリ画像の１つ１つの特徴に対して、データベース化された学習画像の特徴から最近傍特徴を探す際に上から順に探索していくという単純な最近傍探索では、すべての特徴に対して類似計算を行わなくてはならなく、今回の実験のようなデータベースの特徴数が1000万個を超えるような実験では計算コストが肥大し実用可能な範囲での物体認識は困難である。

そこでANN(Approximate Nearest Neighbor) という近似最近傍探索を導入することで最近傍探索の時間を高速化させた。

Approximate Nearest Neighbor

ANN(Approximate Nearest Neighbor)は木探索を用いた近似最近傍探索の手法である。今回の実験ではデータ構造としてkd-treeという木構造を使用し、最近傍探索を行った。 ANNの流れは以下のようになる。

まずデータベースからkd-treeを構築する。再帰的な処理により特徴空間で分割していくことで、セルと呼ばれる同じ分割ルールによって分けられた特徴が集まる領域に分割していく。こうしてできたセルを葉ノード、分割ルールを内部ノードとすることで木構造(kd-tree)を構築する。

次に作成したkd-treeからクエリ画像の特徴に対して最近傍探索を行う。クエリ画像の特徴ベクトル q がどのセルの内部にあるのかを、木構造探索によって求める。発見したセルに対応づけられている特徴ベクトルをとするとき、真の最近傍はを半径とする円の中にある。そしてその円と重なりを持つほかのセルを訪問し、そのセルに含まれている特徴ベクトルとの距離を計算し、最小のユークリッド距離を与える特徴ベクトルを最近傍特徴とする。

さらに探索の時間を短くするために、の距離をそのまま用いるのではなく $1/(1 + \varepsilon )$ を乗じ半径を小さくすることで計算対象の特徴ベクトルが減り、高速化が可能になる。

3.5 認識

クエリ画像から得たすべての特徴それぞれに対してデータベース内の近似最近傍特徴を持こうして得られたランキングからkNN(k-Nearest Neigbor)によってクエリ画像のクラスを認識する。

k-Nearest Neigbor

k-Nearest Neigborとはk個の最近傍のオブジェクトの中で最も一般的なクラスに分類する方法である。上位k位までについてクラスの多数決を行い、もっとも票が多くなったクラスをそのクエリ画像のクラスと認識する。

4 実験

4.1 画像収集

実験には上位クラス5種類に属する計25のクラスで画像収集を行った。 25種類のクエリ語は表1のとおりである。左が上位クラス名、右が実際に画像収集する下位クラスである。また収集した画像例を図2で表す。

表: クエリ語
動物	ネコ	イヌ	ゾウ	ライオン	トラ
車	インプレッサ	レクサス	オデッセイ	パジェロ	プリウス
花	コスモス	タンポポ	ラベンダー	ユリ	バラ
食べ物	ケーキ	ハンバーガー	ピザ	ラーメン	スシ
楽器	ドラム	フルート	ギター	ピアノ	バイオリン

図: 画像例
$\includegraphics[width=0.9\hsize]{img/images.eps}$

4.2 実験手順

まず収集した画像を学習画像とクエリ画像に分割する。クエリ画像は収集した画像に対して検索エンジンの結果として下位となった正しい画像を各クラス50枚づつ選出し、残りの画像を学習画像とした。

実験はSIFT、PCA-SIFT、BoF(Bag-of-Features)の３種類の手法に対して行った。

SIFT、PCA-SIFTの実験では、クラスによってクラス内総特徴数に大きなばらつきがあると総特徴数が多いクラスに対して有利に投票が行われてしまうので、それぞれの実験において最小の特徴数となったクラスと同数になるまで他のクラスについてもランダムに特徴数の削減を行った。

それぞれの実験において使用した学習画像数と、特徴点数は以下の表2となる。

表: データベース内訳
	クラス辺りの画像数	総画像数	クラス辺りの特徴数	総特徴数
SIFT	1,050	26,250	600,000	15,000,000
PCA-SIFT	2,900	72,500	2,140,000	53,500,000
BoF	5,800	145,000	-	-

こうして選出した特徴量をデータベースとして登録する。BoFでの実験では選出したPCA-SIFTの特徴を用いて codebookを作成し、学習画像のBoF表現を作成しデータベースとした。codebookは上位クラス5種類それぞれに対してvisual wordsの数を10000としてcodebookを作成し、 5種類のcodebookを合わせたものを最終的にcodebook(visual words数50000)として使用した。クラスタリングの際もANN(Approximate Nearest Neighbor)のアルゴリズムを用いることで高速に最近傍のvisual wordsを探索できるようにした。

作成した特徴データベースに対してANNを用いて、クエリ画像の特徴点に対し最近傍特徴を持つ画像に投票を行った。実験では、ANNで得られた近傍を上位n位(n=1,5,10,25)までを近傍として許容した場合において得られた

4.3 評価方法

認識精度の尺度として適合率、再現率、分類率によって評価を行った。それぞれの式は以下のように定義される。今回の実験では分類率を中心に見ていった。

$\displaystyle 適合率 = \frac{正しく識別された画像数}{正しいと識別された画像数}$

$\displaystyle 再現率 = \frac{正しく識別された画像数}{正しいクエリ画像総数}$

$\displaystyle 分類率 = \frac{正しく識別された画像総数}{全クエリ画像数}$

5 実験結果

実験を行った。CPUはIntel(R)Xeon(R)CPU 5140 2.33GHz、メモリ32GBの計算機を使用した。特徴から最初にkd-treeを作成するには、SIFTの場合約1時間、PCA-SIFTの場合約2時間ほど時間かかったが、一度作成されたkd-treeを書き出すことで、次の読込の際は10分ほどで行える。 BoFの場合転置ファイルの読み込みに約12時間ほどかかった。

またメモリ使用率はSIFT実験の場合約20GB、PCA-SIFT実験の場合約26GB、BoF実験の場合約6GBのメモリを必要とした。データ量は多いが探索は高速に行うことができる。クエリ画像から得られた特徴点数にも依存するが n=1の場合、SIFTでは約1秒、PCA-SIFTでは3秒、n=25の場合SIFTでは4秒、PCA-SIFTでは6秒、BoFでは1秒ほどで kNNはk位までの投票を行うだけなので、時間はほぼかからない。

また各実験について未知画像のクラス分類が目的なので、認識分類率準として考え、下位クラスにおける分類率がもっとも高くなったn,kの組合わせについて適合率(%)と再現率(%)を表として示した。

まずベースラインとしてBoF(codebook size = 1000)+サポートベクターマシンを使用した実験結果と今回の提案手法との比較結果は図3のようになった。ベースラインには少し及ばなかったが、トラやピアノなど特定のクラス分類においてはベースラインよりも高い精度を得ることができた。

図: 比較結果
$\includegraphics[width=0.9\hsize]{hikaku.eps}$

SIFT,PCA-SIFT手法の場合、kの値は7000ほどまで精度が上がったが、それ以降は横ばいか精度が下がる傾向がわかった。 nの値はどちらの場合でもn=5の時もっとも良い分類率を得ることができた。 BoFではkは大きければ大きいほどよい分類率を得ることができた。

図: 上位クラス分類(5クラス分類)
$\includegraphics[width=0.9\hsize]{5class_2.eps}$

図: 下位クラス分類(25クラス分類)
$\includegraphics[width=0.9\hsize]{25class_2.eps}$

5.1 SIFT実験

分類率がもっとも良かったn=5、k=7000について適合率と再現率を示す。上位クラス分類(5クラス分類)は表3、下位クラス分類(25クラス分類)は表4となった。

表: SIFT,上位クラス分類(適合率、再現率)
表: SIFT,下位クラス分類(適合率、再現率)
$\begin{table}\begin{minipage}{0.45\hsize} \begin{center} \includegraphics... ...dth = 0.9\hsize]{sift,n=5,k=7000.eps} \end{center}\end{minipage} \end{table}$

5.2 PCA-SIFT実験

分類率がもっとも良かったn=5,k=7000について適合率と認分類率示す。上位クラス分類(5クラス分類)は表5、下位クラス分類(25クラス分類)は表6となった。

表: PCA-SIFT,上位クラス(適合率、再現率)
表: PCA-SIFT,下位クラス(適合率、再現率)
$\begin{table}\begin{minipage}{0.45\hsize} \begin{center} \includegraphics... ...ics[width = 0.9\hsize]{pca,kai.eps} \end{center} \end{minipage} \end{table}$

5.3 BoF実験

分類率がもっとも良かったk=10000について適合率と認分類率示す。上位クラス分類(5クラス分類)は表7、下位クラス分類(25クラス分類)は表8となった。

表: BoF,上位クラス(適合率、再現率)
表: BoF,下位クラス(適合率、再現率)
$\begin{table}\begin{minipage}{0.45\hsize} \begin{center} \includegraphics... ...ics[width = 0.9\hsize]{bof_kai.eps} \end{center} \end{minipage} \end{table}$

6 考察

6.1 手法の違いに関して

SIFT、PCA-SIFTの結果の違いに関しては使用した画像データ数が異なるので結果から単純にPCA-SIFTの方が悪いとはいえないが、すべてのn,kの値でSIFTのほうがPCA-SIFTよりも高い結果となった。またn=25の場合のノイズ画像に多く投票されると思われる実験でも、SIFTでは他のnの分類率は低くなったがkの範囲に比例して分類率が向上しているのに対してPCA-SIFTの方は分類率あまり延びてないことから今回の実験ではSIFT特徴の方が有効だったと考えられる。

またBoFの実験結果がSIFT,PCA-SIFTと比較して悪くなってしまった。特にBoFではすべてのクラスにおいて楽器クラスが強く出てしまった。色々な原因が考えられると思うが、楽器クラスでは特徴が他のクラスの画像に比べるとあまり取れないので、特徴の1次元辺りの値が大きくなってしまい、すべてのデータベースの登録に使う画像において取得できる特徴点数が少ない画像は除くと行った処理が必要になると思う。またBoFのコードブックサイズが小さすぎたために他クラス間で同じBoFの各クラスタに投票が片寄ってしまった可能性がある。コードブックサイズをより大きくした実験との比較が重要であると考えられる。より広げる必要がある。

SIFT、PCA-SIFTどちらの場合でもANN(Approximate Nearest Neighbor)の近傍数nの範囲を広げると認識精度が下がってしまうが、を表すのに有効な特徴も有効で無いノイズ特徴というのも同等にn個まで許容してしまうので、画像に対してノイズ特徴が認識精度が下がったのではないかと考えられる。一方kの範囲を7000まであげると認識精度が上がったことに関しては、有効な特徴ではある程度正しく正解クラスの画像に投票が行われ、ノイズ特徴は他のクラス画像に散らばって投票が行われるためだと考える。有効特徴がノイズ特徴よりも少なかったとしても、ノイズ特徴は様々な画像に投票されるが、有効特徴は着実に正解画像に投票がされていくために、k=7000の範囲まで許容した場合、精度が伸び悩んだと考えられる。

6.3 認識精度に関して

全体として結果が最も良かったSIFTのn=5,k=7000に関する結果を見て考察を行う。また後述するピアノ、ゾウの結果である。

下位クラス認識では、ピアノの鍵盤、ギターの弦といった特徴的な特徴を持っている物体に対してはある程度認識ができていた。車クラスに関して車種名までの特定は難しいが、車クラス自体認識という点では認識がある程度できていた。こういった特徴は異なるピアノであっても鍵盤は必ず持っているし、花や食べ物画像にピアノやギターといったものが写っているのは少数であると考えられるため、ノイズ特徴にあまり影響を受けずに認識ができたと考えられる。正解したピアノ画像については図6で表す。不正な画像も集まっているがすべてのkに関して正解クラスが選択された。

図: ピアノ分類成功例
$\includegraphics[width=0.9\hsize]{piano.eps}$

図: ゾウ分類失敗例
$\includegraphics[width=0.9\hsize]{ele.eps}$

一方で動物、食べ物のクラス分類というのは難しく、花クラス内だけ見てもコスモスに引っ張られてしまっていた。動物クラスの認識では多くが花クラスに引っ張られてしまっている。動物画像の多くが背景に草原や木といった情報を含んでいるために花クラスの草に引っ張られている。たしかに草原や木といった特徴は「草木」の特徴に投票はされているということが考えられるが、もし動物クラスだけでの実験の場合そういった「草木」特徴というのが動物クラスの中で散らばるので、もしかしたらあまり結果に関わってこない特徴となりうると考えられるが、今回の実験では花クラスが存在するので結果に大きく関わってくるノイズ特徴となってしまったと考えられる。ゾウ画像で花画像に多数投票されてしまった例を図7で示す。

そういった「草木」に関するような特徴は食べ物クラスの認識でも関わってきていると考えられ、例えばピザが多くコスモスに出てしまうのは、ピザにのっている野菜などの特徴が取れてしまったように思う。こうした多数のクラスにまたがって出てきてしまう特徴の投票を極力減らす努力をする必要がある。

6.4 必要メモリ量に関して

データベースを増やし、特徴点数を増やしていくと必要なメモリ量というのも増大していってしまう。今回の実験ではSIFT実験の場合約20GB、PCA-SIFT実験の場合約26GBのメモリを必要としたが、特徴点数が増えるにつれて、kd-treeを作成する枝情報といったものものも比例して重くなってしまう。 PCA-SIFTとSIFTの比較から、次元を削減するというのはあまり勧まないが、例えばSIFTの各次元に関して bit数の削減というのは試してみる価値があるように思える。またBoF実験では学習画像を増やすこと余裕があるので、できるだけ登録数を増やす必要がある。

7 まとめ

本研究では、特定物体認識の手法をデータ量を増やすことで一般物体認識の実現を目指した。 Web上から集めた画像から特徴を抽出しデータベース化する。クエリ画像に関してデータベースの kNN(k-Nearest Neigbor)による多数決による認識を行った。

実験の結果、最高で上位クラスに対する認識率(60.3%)、下位クラスに対する認識率(32.5%)を得ることができた。下位クラス認識では、トラ78%、ピアノ70%、ギター58%ほどの再現率が得られるなど、トラの縞模様、ピアノの鍵盤やギターの弦といった特定の特徴を必ず持ったような下位クラスに対しては認識ができた。また車クラス上位クラスに関しては適合率(車56%)で見ると良いとはいえないが再現率に関して見ると、車91%と適合率以上に良い結果が得られた。しかし、動物画像に関しては背景特徴である「草木」といった特徴に関して花クラスの特徴に多く引っ張られてしまうなど、複数のクラスに共通して出てくるような特徴に関しての扱いが難しい問題となっていることがわかった。

8 今後の課題

パラメータを色々変化させてBoF実験をやる必要がある。

クラスに関して有益な特徴、例えばトラを認識したい場合背景画像の草原といったものではなくトラ自体の特徴だけを投票できるようにする必要があると思われる。他クラスに共通して出てきてしまう類似特徴を減らすために、作成したデータベースの特徴に関して同じデータベースをクエリとしてすべての特徴に対して探索を行い、ANNの近傍探索範囲n=1以外の投票結果を調べることで特徴を無視することで、有効な特徴に関しての投票ができるのではないかと思う。

また今回の実験では異なるクラスの画像がそのクラスのデータベースに混じっているのも許容して実験を行ったが、データベースに登録する画像を軽い識別機で登録されるクラスと等しいかどうかを確認してからデータベース化することで無駄な画像に対するメモリ消費を押さえることができる可能性がある。しかし一般物体認識に関していえば、見たこともない改造された変な車も車であるし落書きのようなトラでさえもトラといえばトラである。どこに閾値を取るのかもまた難しい問題だと思う。

YANAI Lab.