(57)【要約】  画像や音声等のパターン認識に用いられるパターン認識装置の高速化及び省メモリ化の方法、及び該方法を実装したパターン認識装置を提供する。本発明に係るパターン認識方法は、ヒストグラムの生成と線形SVMによる判別を組み合わせることにより、演算の高速化と省メモリ化を解決したものである。具体的には、特徴ベクトルFの各要素のヒストグラムに値を1加算する代わりに、この要素に対応する係数ベクトルwの要素を加算していく（ステップＢ５）ことにより、w・Fの内積計算を加算演算のみで行っている。これにより、ハードウェア実装の際に、回路規模を大きくすることなく並列処理による高速化が可能になると共に、特徴ベクトルFの各要素を保持するためのメモリが不要になる。
2011037097.tif 000002
【特許請求の範囲】
【請求項１】
L種類のヒストグラム特徴量から成る特徴ベクトルFに対し、パターン認識を行うための判別関数g(F)=w・F+b（ただし、w及びbはそれぞれL次元係数ベクトル及びスカラー値を表す。）のw及びbが、線形SVMにより前もって導出されているパターン認識方法において、
前記特徴ベクトルFの各要素のヒストグラムに値を1加算する際、その代わりに該特徴ベクトルFの要素に対応する係数ベクトルwの要素を加算することにより、前記判別関数におけるw・Fの内積演算を加算演算のみで行うことを特徴とするパターン認識方法。
【請求項２】
前記加算演算を、並列処理により行っていることを特徴とする請求項１に記載のパターン認識方法。
【請求項３】
前記ヒストグラム特徴量がCoHOG特徴量であることを特徴とする請求項１に記載のパターン認識方法。
【請求項４】
前記加算演算を、1次元又は2次元に並べたM個のブロック領域と、各ブロックにおけるN個のオフセットとの、計M×N個の並列処理により行っていることを特徴とする請求項３に記載のパターン認識方法。
【請求項５】
L種類のヒストグラム特徴量から成る特徴ベクトルFに対し、パターン認識を行うための判別関数g(F)=w・F+b（ただし、w及びbはそれぞれL次元係数ベクトル及びスカラー値を表す。）のw及びbが、線形SVMにより前もって導出されているパターン認識装置において、
前記特徴ベクトルFの各要素のヒストグラムに値を1加算する際、その代わりに該特徴ベクトルFの要素に対応する係数ベクトルwの要素を加算することにより、前記判別関数におけるw・Fの内積演算を加算演算のみで行う係数ベクトル加算手段を有していることを特徴とするパターン認識装置。
【請求項６】
前記加算演算を、並列処理により行っていることを特徴とする請求項５に記載のパターン認識装置。
【請求項７】
前記ヒストグラム特徴量がCoHOG特徴量であることを特徴とする請求項５に記載のパターン認識装置。
【請求項８】
前記加算演算を、1次元又は2次元に並べたM個のブロック領域と、各ブロックにおけるN個のオフセットとの、計M×N個の並列処理により行っていることを特徴とする請求項７に記載のパターン認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像や音声等のパターン認識に用いられるパターン認識装置の高速化と省メモリ化の方法、及び該方法を実装したパターン認識装置に関する。
【背景技術】
【０００２】
コンピュータによるパターン認識は、認証、監視、検索、ロボット、自動車の運転補助等における重要な技術として盛んに研究されるようになっている。これらのパターン認識では、画像や音声等の各種データから、目的とするパターンの識別に適した複数種類の特徴量を抽出し、この抽出された特徴量に目的のパターンが含まれているかを学習・判別する、ということが行われる。【０００３】
抽出する特徴量としては識別すべきパターンに応じて様々なものが用いられるが、近年、特徴量をヒストグラムで表す手法が多く用いられるようになってきている。例えば非特許文献１には、生体認識や犯罪捜査等に用いられる顔検出において、光の周波数スペクトルのヒストグラムを特徴量とする手法が提案されている。また、非特許文献２には、音の周波数スペクトルのヒストグラムを特徴量とする音楽の分類方法が記載されている。非特許文献３には、監視や車載用途で用いられる歩行者検出において、輝度勾配ヒストグラム（Histograms of Oriented Gradients：HOG）を特徴量とする手法が記載されている。非特許文献４には、HOGをより発展させた輝度勾配共起ヒストグラム（Co-occurrence Histograms of Oriented Gradients：CoHOG）を特徴量として用いる手法が提案されている。【０００４】
一方、抽出された特徴量に対する学習・判別には、サポートベクタマシン（Support Vector Machine：SVM）が用いられることが多い。SVMとは、各特徴量パラメータを座標軸とする特徴空間において、学習データを正解集合と不正解集合に分類する超平面（判別平面）を、マージン（超平面と該超平面に最近接するデータ点との距離）を最大化させるように最適化計算により導出するという方法である。ここで、特徴量の数（特徴空間の次元数）をL、特徴空間上の任意の点をx（L次元の位置ベクトル）とすると、前記の判別平面は次式により表される。
【数１】
2011037097.tif 000003
ここで、wとbはそれぞれL次元係数ベクトルとスカラー定数であり、学習データから導出された値である。従って、データから抽出された特徴量が正解集合に含まれるか否かは、抽出された特徴量に対応する特徴ベクトルxに対して、
【数２】
2011037097.tif 000004
で表される判別関数g(x)の正負を判定することにより判別できる。【０００５】
また、特徴空間において判別平面を導出できない場合、該特徴空間を別の写像空間に変換し、この写像空間上で判別平面を導出することも行われる。特徴空間上で判別平面を導出するものは線形SVM、写像空間上で判別平面を導出するものは非線形SVMと呼ばれる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】C. Shan, S. Gong, and P.W. McOwan, "Robust facial expression recognition using local binary pattern", IEEE International Conference on Image Processing, vol.2, pp.370-373, 2005.
【非特許文献２】T. Li, M. Ogihara, and Q. Li, "A comparative study on content-based music genre classification", the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pp.282-289, 2003.
【非特許文献３】N. Dalai, B. Triggs, I. Rhone-Alps, and F. Montbonnot, "Histograms of oriented gradients for human detection", IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol.1, pp.886-893, 2005.
【非特許文献４】T. Watanabe, S. Ito, and K. Yokoi, "Co-occurrence histograms of oriented gradients for pedestrian detection", the 3rd IEEE Pacific-Rim Symposium Image and Video Technology, pp. 37-47, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
コンピュータによるパターン認識では、大量のデータから識別すべきパターンを検出することになるため、高速化が要求されることが多い。例えば、上記の歩行者検出では、毎秒数十フレームという短い時間間隔で、リアルタイムで歩行者を識別することが要求される。【０００８】
しかしながら、高精度に目的のパターンを検出し、かつ誤検出を避けるためには、膨大な数の特徴量を扱う必要がある。歩行者検出のCoHOG特徴量を例に説明すると、扱う特徴量の次元数は数万から十数万という規模になる。このような規模の特徴量を短い時間間隔で、かつリアルタイムで処理することは、ソフトウェアによる実装のみではたとえ最新のプロセッサを用いても困難である。【０００９】
また、監視カメラやロボット、自動車の運転補助システム等の用途では、パターン認識装置はそれぞれの機器の内部に組み込んで使用することになる。このように装置を組み込んで使用する場合、物理的なサイズや消費電力等の制約が厳しく、動作周波数の高い最新のプロセッサや大規模なマルチプロセッサ等を利用することが難しい。
以上の理由から、パターン認識装置の高速化のためには、専用のハードウェア（回路）による実装が必要となる。【００１０】
しかしながら、従来の方法では、特徴量をデータから抽出した後、パターンの判別を行うため、抽出した特徴量を一旦メモリに格納する必要がある。上記のように特徴量の数が膨大である場合、これを保持するためのメモリも大量に用意する必要がある。そのため回路規模が大きくなり、ハードウェアに実装する際の障害となってしまう。【００１１】
また、パターン判別のための計算も高速化の障害となる。例えば、式(2)に示すような線形SVMによる判別では、係数ベクトルwと特徴ベクトルxの内積演算のために、特徴ベクトルの次元数に応じた多数の乗算演算が必要となる。ハードウェア実装においてこの内積演算を高速に行うには、回路に乗算器を多数並列に並べる必要がある。しかしながら、これはやはり回路規模の増大を招いてしまう。一方、回路規模の増大を抑えようとすると、乗算演算の並列化が十分に行えなくなり、判別計算を高速に行うことができなくなる。【００１２】
本発明が解決しようとする課題は、画像や音声等のパターン認識に用いられるパターン認識装置の高速化及び省メモリ化の方法、及び該方法を実装したパターン認識装置を提供することである。
【課題を解決するための手段】
【００１３】
本願発明者は、ヒストグラムに基づく特徴量（以下、「ヒストグラム特徴量」と呼ぶ）と線形SVMによる判別とを組み合わせたパターン認識方法に着目した。ヒストグラム特徴量は、データ内に対応する特徴量が1つ見つかる毎に、該特徴量のヒストグラムに値を1ずつ加算していくことで計算される。このヒストグラムに値を1ずつ加算していく演算と、式(2)の判別関数における内積演算とを統合することにより、メモリの削減と乗算演算の削減とを同時に解決する方法を見出した。【００１４】
すなわち、上記課題を解決するために成された本発明に係るパターン認識方法は、
L種類のヒストグラム特徴量から成る特徴ベクトルFに対し、パターン認識を行うための判別関数g(F)=w・F+b（ただし、w及びbはそれぞれL次元係数ベクトル及びスカラー値を表す。）のw及びbが、線形SVMにより前もって導出されているパターン認識方法において、
前記特徴ベクトルFの各要素のヒストグラムに値を1加算する際、その代わりに該特徴ベクトルFの要素に対応する係数ベクトルwの要素を加算することにより、前記判別関数におけるw・Fの内積演算を加算演算のみで行うことを特徴とする。【００１５】
また、上記課題を解決するために成された本発明に係るパターン認識装置は、
L種類のヒストグラム特徴量から成る特徴ベクトルFに対し、パターン認識を行うための判別関数g(F)=w・F+b（ただし、w及びbはそれぞれL次元係数ベクトル及びスカラー値を表す。）のw及びbが、線形SVMにより前もって導出されているパターン認識装置において、
前記特徴ベクトルFの各要素のヒストグラムに値を1加算する際、その代わりに該特徴ベクトルFの要素に対応する係数ベクトルwの要素を加算することにより、前記判別関数におけるw・Fの内積演算を加算演算のみで行う係数ベクトル加算手段を有していることを特徴とする。
【発明の効果】
【００１６】
本発明に係るパターン認識方法及びパターン認識装置は、ヒストグラム生成と内積演算の2つの処理を統合したものである。これらの処理を統合したことにより、ヒストグラム特徴量を保持するためのメモリが不要になり、ハードウェアに実装する際に大幅なメモリ削減を行うことが可能となる。また、内積演算を全て加算演算で行うことができるため、並列化の際に乗算器を多数並べる必要がなくなる。以上から、ハードウェアの回路規模を大幅に削減することができ、これによって製造コストを削減することもできる。また、並列化が容易になることから、計算時間を削減することもできる。
【図面の簡単な説明】
【００１７】
【図１】輝度勾配のラベリングの一例を示す図。
【図２】輝度勾配の共起ヒストグラムの生成の一例を示す図。
【図３】共起行列の計算に用いられるオフセットの一例を示す図。
【図４】CoHOG特徴量の計算の手順を示す図。
【図５】CoHOG特徴量に対する従来のパターン認識方法の実行手順を示すフローチャート。
【図６】本発明に係るパターン認識方法をCoHOG特徴量に対して適用した場合の実行手順を示すフローチャート。
【図７】本発明に係るパターン認識装置の一実施例を示すブロック図。
【図８】本発明に係るパターン認識装置をハードウェア実装した際の構成を示す構成図。
【図９】ブロック内での画素の走査の順序を示す図。
【図１０】オフセット毎の並列化を示す図。
【図１１】水平方向のブロック毎の並列化を示す図。
【発明を実施するための形態】
【００１８】
本発明に係るパターン認識方法は、ヒストグラム特徴量と線形SVMとを組み合わせた方法であれば、どのようなパターン認識方法に対しても適用可能であるが、以下では、CoHOG特徴量を用いた歩行者検出を例に説明することにする。
【００１９】
まず、CoHOG特徴量について簡単に説明を行う。CoHOG特徴量は、歩行者検出に有効な特徴量としてよく利用されている輝度勾配ヒストグラム（HOG）を拡張した特徴量であり、輝度勾配方向のペアの共起（Co-occurrence）ヒストグラムを用いることにより、HOG特徴量より複雑な形状を表現することができるものである。
【００２０】
まず、入力された可視画像に対する各画素の輝度勾配方向θは、以下のように求められる。
【数３】
2011037097.tif 000005
ここでv, hはそれぞれ垂直及び水平方向の輝度勾配であり、入力画像に適切なフィルタをかけることにより求めることができる。上式より求められたθは、所定の角度毎に複数のクラスに分類され、それぞれのクラスにラベリングが施される。以下では簡単のため、θを45度おきに8つのクラスに分類し、図１に示すように、各クラスに1〜8のラベルを与えることにする。また、画素の位置を2次元ベクトル(p,q)で表し、位置(p,q)の輝度勾配方向のラベル（以下、これを「輝度勾配方向画像」と呼ぶ）をI(p,q)で表すことにする。なお、pは水平方向の画素の位置を、qは垂直方向の画素の位置を表しており、それぞれ整数で与えられる。
【００２１】
次に、輝度勾配方向のペアに対する共起行列（Co-occurrence matrix）のヒストグラムを、図２に示すように生成する。図２の共起行列は、次式で表されるCi,jを要素とする行列Cとして求められる。
【数４】
2011037097.tif 000006
ここで、n及びmはそれぞれ水平方向及び垂直方向の画素数であり、(x,y)は(p,q)に対する画素ペアの位置を示すオフセットである。また、i及びjはそれぞれ位置(p,q)及び(p+x,q+y)の輝度勾配方向のラベルを表している。上述のように、輝度勾配方向のラベルは8個あるため、この共起行列Cの次元数は8×8=64となる。
【００２２】
また、オフセット(x,y)としては、図３に示す31種類（(x,y)=(0,0)も含む）を用いることにする。なお、オフセットとして図３に示したもの以外のものも用いることができるが、対称性の観点から、位置(p,q)から一定半径内に含まれる円の下半分のみで良い。
【００２３】
上記の共起行列のヒストグラム（共起ヒストグラム）は、入力画像中の候補領域を分割した小領域と上記のオフセットとの全ての組み合わせに対して計算される（図４）。以下、候補領域全体をサブウィンドウ、小領域をブロックと呼ぶことにする。ここで、ブロックのインデックスをkとすると、ブロックk、オフセット(x,y)に対する共起行列Cは、64次元のベクトルfk,x,yで表すことができる。従って、全てのブロック、全てのオフセットに対してベクトルfk,x,yを算出し、さらに算出されたベクトルfk,x,yを全て連結することで、最終的なCoHOG特徴量の特徴ベクトルFを得ることができる。なお、この特徴ベクトルFの次元数Lは、ブロックの総数をKとすると、L=K×31×64である。
【００２４】
CoHOG特徴量は強力な特徴量であるため、線形SVMを用いても高精度な歩行者検出が実現できる。式(2)で示したように、線形SVMでは特徴ベクトルFに対して、
【数５】
2011037097.tif 000007
で表される判別関数gの正負を判定することにより、特徴量ベクトルFが正解集合に含まれるか否かを判別することができる。
以下、用語の簡単化のため、線形SVMによる判別のことを「SVM予測」と呼ぶことにする。また、式(5)の係数ベクトルw及びスカラー定数bは、予め学習により算出されているものとする。
【００２５】
上記の例では、CoHOG特徴量の次元数はL=K×31×64となっている。従って、サブウィンドウ内の水平方向のブロック数を6、垂直方向のブロック数を12とすると、ブロックの総数はK=6×12となり、CoHOG特徴量の次元数は約14万という非常に膨大な数になってしまう。しかしながら、従来の方法ではヒストグラム生成後にSVM予測を行うため、一時的にこのL次元の長大なベクトルFを保持する必要があった。そのため、ハードウェア実装の際に、メモリの量、すなわち回路の規模が増大してしまっていた。また、SVM予測では、式(5)に示したようにベクトルの内積を計算しなければならないため、ベクトルの次元数に応じた多数の乗算が必要となる。ハードウェア実装においてSVM予測を高速に行うためには、多数の乗算器を並列に並べる必要があり、これも回路規模の増大を招いてしまっていた。
【００２６】
これに対し、本願研究者は、ヒストグラム生成とSVM予測のそれぞれの性質に着目し、これらの処理を統合することにより上記の問題点を解決する方法を見出した。以下、ヒストグラム生成とSVM予測の両処理を統合した、本発明に係るパターン認識方法について説明を行う。
【実施例１】
【００２７】
上述したCoHOG特徴量の特徴ベクトルFの各要素をfk,x,y(i,j)で表し、この要素に対応する式(5)の係数ベクトルwの要素をwk,x,y,i,jとすると、式(5)の右辺の内積は以下の式で表すことができる。
【数６】
2011037097.tif 000008
ここで、特徴ベクトルFの要素fk,x,y(i,j)は、式(4)から
【数７】
2011037097.tif 000009
で表される。従って、
【数８】
2011037097.tif 000010
とすると、次式が成立する。
【数９】
2011037097.tif 000011
式(9)は、従来、(i,j)の値に対応するヒストグラムに1を加算していた処理の代わりに、wk,x,y,i,jの値を加算していけば良いことを意味している。【００２８】
以上を、図５及び図６に示す従来例及び本実施例のフローチャートを比較することにより説明する。
従来の方法は、予め線形SVMによって学習・算出された判別関数の係数ベクトルw及びスカラー定数bを入力設定するパラメータ設定ステップ（ステップＡ１）と、検出対象となる画像を入力する画像入力ステップ（ステップＡ２）と、入力された画像から輝度勾配画像を生成する輝度勾配画像生成ステップ（ステップＡ３）と、生成された輝度勾配画像から共起ヒストグラムの生成を行うヒストグラム生成ステップ（ステップＡ４〜Ａ６）と、共起ヒストグラムを連結することにより特徴ベクトルFを生成するベクトル生成ステップ（ステップＡ７）と、特徴ベクトルFと係数ベクトルwとの内積演算を行う内積演算ステップ（ステップＡ８）と、内積演算ステップで得られたw・Fの値と-bとの大小を比較することにより、特徴ベクトルFが正解集合に含まれるか否かを判別する判別ステップ（ステップＡ９）と、に分かれている。【００２９】
この従来例の方法では、ステップＡ４〜Ａ６において、計算途中のfk,x,y(i,j)をメモリ内に格納しておく必要がある。そのため、k, x, y, i, jの組み合わせの数（次元数L）だけメモリが必要となってしまう。また、ステップＡ８の内積演算を行うために多数の乗算演算が必要になってしまうという問題もある。【００３０】
これに対し、本実施例では、従来例のヒストグラム生成ステップと内積演算ステップを統合した。具体的には、fk,x,y(i,j)に値を1加算する代わりに、fk,x,y(i,j)に対応する係数ベクトルwの要素wk,x,y,i,jをSVM評価値αに加算する構成とした（ステップＢ５）。全てのk, p, q, x, yに対してそれぞれ(i,j)の組を決定してSVM評価値αに加算することにより、最終的な加算値がw・Fに一致することは、式(9)より明らかである。これにより、従来の方法におけるステップＡ４〜Ａ８を、本実施例ではステップＢ４〜Ｂ６に削減できる。また、本実施例の方法ではfk,x,y(i,j)を計算しないため、これを保持するメモリを削減できる。さらに、w・Fの計算に乗算演算を用いていないため、乗算器を多数並べる必要がなくなる。以上から、ハードウェア実装の際に回路規模を大幅に削減できると共に、並列処理による高速化が可能となる。
【実施例２】
【００３１】
第１実施例に示したパターン識別方法を実装したパターン識別装置の一実施例を図７のブロック図を用いて説明する。なお、本実施例においても、第１実施例と同様、CoHOG特徴量を対象に説明を行う。【００３２】
本実施例のCoHOG特徴量に対するパターン識別装置は、図７に示す画像入力部１０、輝度勾配画像生成部１１、サブウィンドウ決定部１２、ヒストグラム生成・SVM予測統合部１３、判定部１４、を有している。また、ヒストグラム生成・SVM予測統合部１３は輝度勾配方向ペア決定部１５、係数ベクトル読み出し部１６、パラメータ記憶部１７、係数ベクトル加算部１８を有している。【００３３】
本実施例のパターン識別装置の各部の動作を以下に説明する。
画像入力部１０から入力された画像は、輝度勾配画像生成部１１において輝度勾配画像に変換される。輝度勾配画像生成部１１で得られた輝度勾配画像に対し、サブウィンドウ決定部１２においてサブウィンドウ（候補領域）が決定され、該サブウィンドウ内の輝度勾配画像のデータがヒストグラム生成・SVM予測統合部１３に送られる。一方、前記のサブウィンドウは複数のブロックに分けられ、ブロックk内の画素(p,q)とそのオフセット(x,y)に対する輝度勾配方向の組(i,j)が、輝度勾配方向ペア決定部１５で決定される。この輝度勾配方向ペア決定部１５で決定された輝度勾配方向の組(i,j)に対し、前もってパラメータ記憶部１７に設定・記憶された係数ベクトルwの対応する要素wk,x,y,i,jが係数ベクトル読み出し部１６で読み出され、画素(p,q)の走査と共に係数ベクトル加算部１８で加算されていく。この加算処理が全てのブロックk、オフセット(x,y)に対して行われた後、サブウィンドウ内に目的とするパターンが含まれているか否かが、係数ベクトル加算部１８で得られた加算値とパラメータ記憶部から読み出された-bとの大小を判定する判定部１４により判定される。【００３４】
なお、ヒストグラム生成・SVM予測統合部１３における輝度勾配方向ペア決定部１５、係数ベクトル読み出し部１６、パラメータ記憶部１７、係数ベクトル加算部１８の各動作は、並列処理により高速化できる。以下、実際に集積回路等のチップにハードウェア実装し、さらに並列処理を施したCoHOG特徴量に対するパターン識別装置について説明を行う。【００３５】
図７の装置に対して実際にハードウェア実装を行い、並列処理による高速化を施したパターン識別装置の構成の一例を図８に示す。図８のパターン識別装置では、図示しない画像入力部からW×Hの大きさの画像が入力され、長さWのラインバッファに3ライン分格納される。その後、輝度勾配画像生成部１１において、3ライン分の入力画像にSobelフィルタを作用させ、水平、垂直方向の輝度勾配を計算し、これに基づき輝度勾配の方向を8方向に分類する。なお、上記の輝度勾配算出を行っている間も入力画像を休み無く受け取るために、ラインバッファは4ライン分用意している。【００３６】
各画素に対して算出された8種類の輝度勾配方向は輝度勾配画像用のフレームバッファに格納される。フレームバッファのサイズは入力画像と同じW×Hである。輝度勾配画像を生成した後、候補領域としてサブウィンドウが決定され、サブウィンドウ内のデータがヒストグラム生成・SVM予測統合部１３に転送される。このヒストグラム生成・SVM予測統合部１３では31種類のオフセット及びサブウィンドウ内のブロック横一行分を並列に処理する。最終的に、SVM予測により得られた評価値（SVM評価値α）とサブウィンドウの座標が出力され、図示しない判定部により該サブウィンドウ内に目的とするパターンが含まれているか否かが判定される。【００３７】
以下、図８の輝度勾配画像生成部１１、ヒストグラム生成・SVM予測統合部１３の詳細について述べる。【００３８】
［輝度勾配画像生成部］
本実施例の輝度勾配画像生成部１１では、水平、垂直方向の輝度勾配を求めるためにSobelフィルタを使用している。Sobelフィルタとは、対象画素の周囲3×3画素に対して以下の行列をそれぞれ作用させることにより、水平、垂直方向の輝度勾配h, vを得るものである。
【数１０】
2011037097.tif 000012
【００３９】
輝度勾配h, vが得られた後、式(3)に従って勾配方向を求め、それを45度おきの8つのクラスに分類する。この際、θを求めるために逆正接演算を行う必要があるが、ここでは8つのクラスに分類することが目的であるので、これらを全て比較演算に置換する。例えば、対象とする輝度勾配画像がπ/8<θ<3π/8のクラスに属するかどうかを判定するには、
【数１１】
2011037097.tif 000013
【数１２】
2011037097.tif 000014
の比較を行えばよい。さらに、式(12)のtan(π/8)やtan(3π/8)は定数であるため、これらの値を前もって計算しておけば、正接演算も不要となる。
この輝度勾配画像生成部１１では上記のような比較演算により勾配方向を8つのクラスに分類し、次段のフレームバッファへと出力する。【００４０】
［ヒストグラム生成・SVM予測統合部］
一方、図８に示したヒストグラム生成・SVM予測統合部１３では、並列化により、輝度勾配方向ペアの決定、係数ベクトルを記憶するROMからの係数ベクトルの読み出し、係数ベクトルの各要素の加算の動作の高速化を行う。なお、今回の実装ではサブウィンドウのサイズを60×120、ブロックサイズを10×10とし、サブウィンドウ内に6×12個のブロックが並んでいるものとした。【００４１】
まず、単一のブロックに注目した際の処理内容及びハードウェア構成について述べる。ブロックk内の各画素を図９に示すようにラスタ順に走査し、各画素に対して図３に示した各々のオフセットの画素を参照して、それらの画素のペアの勾配方向の組(i,j)を決定する。(i,j)が求まると、予め学習済みの係数ベクトルwを格納したROM（係数ベクトル用ROM）から対応するwk,x,y,i,jが読み出され、加算器によりこの読み出されたwk,x,y,i,jがSVM評価値αに加算され、累算器にαのデータが保持される。この際、対象の画素と該画素を中心とする下半円状の領域内のデータさえあれば、31種類全てのオフセットに対する画素ペアの勾配方向の組(i,j)の決定と、SVM評価値の加算を並列に行うことができる。各オフセットに対する係数ベクトルwの要素を同時に（並列に）読み出せるようにするため、係数ベクトル用ROMをオフセット毎に分割し、それぞれのオフセット(x,y)に対する係数ベクトル用ROMに、ブロックk、オフセット(x,y)における64種の係数ベクトルの要素wk,x,y,i,jを保持することで、図１０のように31並列で輝度勾配方向ペアの決定と係数ベクトルの各要素の加算を実行できるようにした。【００４２】
ここで、図３の領域の形状からも分かるように、各ブロックに対して上記の処理を行う場合、自身のブロック内の画素だけでなく隣接するブロックに含まれる画素のデータも必要となる。従って、隣接するブロックをまとめてレジスタアレイ上に読み出し、同時に処理することによってフレームバッファからのデータ読み出しを減らすことができる。本実施例では、図１１のように横方向に並んだ6ブロックを同時に処理する構成とした。この場合、5ライン分のデータを読み出した時点で処理を開始できる。1サイクルに各ブロック内の1画素に対して処理を行うとすると、1ラインを処理するのに要するサイクル数は6並列なので10サイクルとなる。この10サイクルの間にフレームバッファから次の1ライン分60画素のデータを転送することにより、無駄なデータ転送を行うこと無く連続処理を実現する。ラインバッファは走査に適するよう、シフトレジスタにより実装し、次ラインのバッファを含め60画素分を6本搭載した。【００４３】
上記の処理をサブウィンドウの高さである120ライン分繰り返し、31オフセット及び6ブロックの全て出力結果の総和を加算することにより、最終的なSVM評価値を得ることができる。【００４４】
なお、上記の例では、ブロックに対する並列処理を水平方向に対して行ったが、垂直方向に並列処理を行っても良い。また、水平方向と垂直方向の両方向に対して同時に並列処理を行うこともできる。【００４５】
本実施例のパターン認識装置において1サブウィンドウを処理するのに必要なサイクル数を計算する。上述の通り、オフセットに対し31並列、横方向のブロックに対し6並列で実行するため、1ライン処理するのに10サイクル要する。サブウィンドウの高さは120であるため、総サイクル数は10×120=1200となる。【００４６】
なお、輝度勾配画像の生成に画像サイズW×H分のサイクル数を要するが、1フレーム当たりのサブウィンドウ数が十分大きいため、これらは無視できる値となる。また、上記の他にSVM評価値の加算等に若干のサイクル数を要するが、これらの処理は全てパイプライン化されているため、定常的には前述の通り1サブウィンドウ当たり1200サイクルで処理を継続することができる。【００４７】
次に、図８に示したパターン識別装置の回路規模及び動作速度を評価するため、FPGA上に実装を行った。評価に用いたFPGAはXilinx社Virtex-5 XC5VLX330T-2である。論理合成及び配置配線にはXilinx社のISE 11.1を利用した。実装結果は表１の通りである。
【表１】
2011037097.tif 000015
なお、最大遅延は5.977ns、最大動作周波数は167MHzとなった。【００４８】
表１に示すように、図８に示したパターン識別装置の回路規模は、ロジック、メモリ共に単一のFPGAデバイスに十分収まっている。また、最大利用率が18%であるため同FPGAを用いれば提案ハードウェアを4, 5個搭載することも可能である。なお、本実施例のパターン識別装置における入力ラインバッファ及びフレームバッファはブロックRAMで、サブウィンドウのラインバッファはレジスタで、それぞれ実装している。【００４９】
さらに、図８に示したパターン識別装置と汎用CPUの処理速度の比較を行った。ここでは比較対象のCPUとしてIntel Core i7 CPU3.2GHzを使用する。非特許文献４のCoHOGの原論文の手法をそのままソフトウェアにより実装しCPU上で実行させた結果、処理速度は毎秒約1100サブウィンドウであった。一方、本実施例のパターン識別装置は1サブウィンドウあたり1200サイクルで処理可能であり、最大動作周波数が167MHzであるため、毎秒139166サブウィンドウを処理可能である。これはCPUによる実行の100倍以上高速である。【００５０】
ここで、実際の歩行者検出に即した条件を用いて処理速度を評価する。入力画像から実際に歩行者検出を行うためには、まず画像からサブウィンドウを抽出し、それに対してCoHOG特徴を求め、SVMによる識別を行う必要がある。サブウィンドウは全画面をラスタスキャン順に走査することにより得られるが、画像サイズをW×H、サブウィンドウのサイズをw×h、サブウィンドウのスキャン間隔をpとすると、サブウィンドウの総数Sは、
【数１３】
2011037097.tif 000016
となる。より大きなサイズの歩行者にも対応するため、入力画像をs倍に縮小して同様にスキャンを行うため、1フレームあたりの総数はこれの全縮尺についての和となり、
【数１４】
2011037097.tif 000017
となる。例として、320×240の入力画像から60×120の大きさのサブウィンドウを抽出する場合を考えると、ステップ間隔を4ピクセル、縮尺を1.2倍ずつ変更した時、Sframe=3615となる。従って、CPUによる実行では上記の条件では1フレーム当たり約3秒要することになるが、本実施例のパターン識別装置は同条件で毎秒38フレームの実時間処理を達成可能である。また、さらに高解像度の640×480を8ピクセル間隔でスキャンした場合は毎秒17フレームで、4ピクセル間隔でスキャンした場合でも毎秒4.2フレームで処理可能である。
【符号の説明】
【００５１】
１０…画像入力部
１１…輝度勾配画像生成部
１２…サブウィンドウ決定部
１３…ヒストグラム生成・SVM予測統合部
１４…判定部
１５…輝度勾配方向ペア決定部
１６…係数ベクトル読み出し部
１７…パラメータ記憶部
１８…係数ベクトル加算部
【図１】
2011037097.tif 000018
【図２】
2011037097.tif 000019
【図３】
2011037097.tif 000020
【図４】
2011037097.tif 000021
【図５】
2011037097.tif 000022
【図６】
2011037097.tif 000023
【図７】
2011037097.tif 000024
【図８】
2011037097.tif 000025
【図９】
2011037097.tif 000026
【図１０】
2011037097.tif 000027
【図１１】
2011037097.tif 000028
【国際調査報告】
2011037097.tif 000029
2011037097.tif 000030