×この技術を簡単クリック査定この機能をご利用いただくには、会員登録(無料)が必要です。出願した特許の牽制数、引用された数などを知る事ができます。気になる技術や特許をブックマークしておけば、いつでも後から読むことができます。後で印刷するために、公報をPDFでダウンロードできます。会員登録してastamuseを使えば、もっと簡単に便利にお使いいただけます。会員登録(無料)「astamuse」は世界中の挑戦したい社会課題に挑戦し、未来を創る人のプラットフォームです。※この項目の情報は公開日時点(2016年3月31日)のものです。30は、二値化された特徴ベクトルxを取得する場御なりコード変換部33と、特徴ベクトルを識別するための複数のクラスの辞書としての複数の実数ベクトルq1〜qLからなる実数行列Qを、複数のMiCi(i=1〜N、Nは2以上の自然数)の和に分解するパラメータ行列分解部35と、特徴ベクトルxと複数の実数ベクトルq1〜qLの各々との内積の計算として、特徴ベクトルxと基底行列Miとの積xMiを計算し、さらに当該積xMiと対応する係数行列Ciとの積を計算することで、特徴ベクトルxについて各クラスの識別を行う線形SVM識別部36とを備えている。パターン認識など、多くの分野で特徴量が用いられている。情報を、計算機で扱いやすいように変換したものである。特徴量は、D次元のベクトル(特徴ベクトル)で表される。特徴ベクトルを用いた演算を行うことで、例えば、コンテンツの類似度を判定することができる。画像αの特徴ベクトルと、画像βの特徴ベクトルの距離が小さければ、αとβは似ているとみなすことができる。同様に、音声波形αの特徴ベクトルと、音声波形βの特徴ベクトルとの距離が小さければ、αとβは似ているとみなすことができる。パターン認識等の情報処理では、情報を特徴ベクトルに変換して、特徴ベクトル同士を比較して、その距離を求めることにより情報の類似度を判断する。特徴ベクトル間の距離の尺度としては、L1ノルム、L2ノルム、ベクトル間角度などが用いられる。これらは、特徴ベクトルx,y∈RDについて、次のように計算できる。特徴ベクトルが実数ベクトルである場合には、以下のような問題がある。2つの特徴ベクトルx,y∈RDの間の距離の計算が遅くなるという問題がある。L2ノルムの二乗を距離の尺度として用いる場合、であるから、D回の引き算、D回の乗算、D−1回の加算が必要である。特徴ベクトルが浮動小数で表現される場合には、この計算負荷は非常に高くなる。特徴ベクトルが高次元になれば、この計算負荷はさらに高くなる。大量のメモリを消費する点も問題となる。特徴ベクトルを4バイトの単精度実数で表現する場合、D次元の特徴ベクトルは4Dバイトのメモリを消費する。特徴ベクトルが高次元になれば、このメモリ消費量は大きくなる。大量の特徴ベクトルを扱う場合、扱う特徴ベクトルの数だけメモリを消費することになる。そこで近年、特徴ベクトルを0と1の列から成るバイナリコードに変換することにより、これら2つの問題を解決する手法が提案されている。Hashing、非特許文献3参照)がある。これらの手法では、D次元の特徴ベクトルがdビットのバイナリコードに変換される。この変換は、もともとの空間における距離が、変換後の空間におけるハミング距離と強く相関するように行われる(もともとの空間における距離と、変換後の空間におけるハミング距離と強く相関する根拠については、非特許文献1の1121ページのLemma3.2を参照)。これによって、特徴ベクトル間の距離の計算を、バイナリコード同士のハミング距離計算で代用できるようになる。ハミング距離とは、二つのバイナリコードのうち、異なるビットの数を数えたものである。この計算は、二つのコードのXORをとった後に1が立っているビット数を数えるだけなので、非常に高速に行うことができる。多くの場合、バイナリコード変換によって、数十〜数百倍程度の高速化が可能である。特徴ベクトル間の距離の計算を、バイナリコード同士のハミング距離計算で代用することにより、もともと4Dバイトであったメモリの必要容量を、d/8バイトまで削減できる。これにより、数十〜数百分の一にメモリ容量を節約できる。抽出された特徴量をバイナリコードに変換して、さまざまなアルゴリズムを適用することで、コンテンツの検索や認識などが可能となる。類似コンテンツを検索する場合には、あらかじめデータベースに登録されているコンテンツの特徴量を、すべてバイナリコードに変換しておく。入力クエリとして与えられたコンテンツの特徴量をバイナリコードに変換する。入力クエリのバイナリコードと、データベースに登録されているすべてのバイナリコードとの間のハミング距離を計算することで、入力クエリに類似するコンテンツを検索して出力できる。バイナリコードはdビットの0と1の列からなる。これを、各要素が−1及び1の二値のみを取るd次元のベクトルと考えることもできる。以下の説明における混乱を避けるために、「バイナリコード」と「二値ベクトル」という用語について、以下のように区別をする。「バイナリコード」は、0と1の列からなるデータ表現である。char)型の16要素分の配列を用意すればよい(8bit×16=128bit)。「二値ベクトル」は、各要素が二値のみを取るベクトルである。二値ベクトルを各要素が−1及び1のみをとるベクトルとする場合には、バイナリコード「01101110」に対応する二値ベクトルは、(−1,1,1,−1,1,1,1,−1)Tである。各要素が0及び1の二値のみを取るベクトルも二値ベクトルであるし、さらには、各要素が任意のα及びβ(ここでα≠βである)の二値のみを取るベクトルも二値ベクトルである。「バイナリコード」と「二値ベクトル」の違いは、情報の表現に関するものであり、両者に本質的な違いはない。特徴ベクトルを、各要素が−1及び1の二値のみを取るd次元の二値ベクトルに変換すれば、SVM(サポートベクトルマシン)による識別処理や、k−meansクラスタリングなど、さまざまな処理をバイナリコードに対しても適用できる。これらのケースではハミング距離による高速距離計算の恩恵を受けることができないことがある。アルゴリズムによっては、バイナリコード変換による高速距離計算の恩恵を受けられないことがある。バイナリコード変換による高速距離計算の恩恵を受けられない例として、以下では、識別器(Classifier)による認識処理及びk−meansクラスタリングを説明する。識別器による認識処理については、例えば、二値ベクトルx∈{−1,1}dを2クラスに識別する問題に対して、線形SVM(線形サポートベクトルマシン)等の線形識別器を適用することを考える。線形SVMでは以下の式を評価する。f(x)が正ならばxはクラスAに属し、f(x)が負ならばxはクラスBに属するものとして識別する。wは、重みパラメータであって、w∈Rdである。bは、バイアスパラメータであって、b∈R1である。パラメータw及びbは、学習用に用意した特徴量を用いて、学習処理により自動的に決定される。ここで、学習用に用意した特徴量が二値ベクトルであっても、w∈Rdは二値にならず、実数値になってしまう。f(x)の計算にはwTxが含まれているが、xが二値である一方でwが実数値のベクトルであるため、wTxの計算には、浮動小数点演算が必要になってしまう。このように、SVMを適用する識別器による認識処理では、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。次に、二値ベクトルに対して、k−meansクラスタリングを適用する場合、すなわち、d次元の二値ベクトルがN個与えられたとき、互いに距離が近い二値ベクトルをまとめたk個のクラスタを求める問題を考える。k−meansとは、次の手順によりk個のクラスタと代表ベクトルを算出するアルゴリズムである。ステップ1:N個の特徴量からk個をランダムに選出し、これをクラスタの代表ベクトルとする。ステップ2:入力として与えられたN個の特徴量それぞれについて、最も距離が近い代表ベクトルを求める。ステップ3:各代表ベクトルに所属する特徴量の平均を計算し、これを新しい代表ベクトルとする。ステップ4:ステップ2、ステップ3を収束するまで繰り返す。k−meansクラスタリングにおいて問題となるのは、ステップ3において、新しい代表ベクトルが二値ベクトルの平均で定義される点である。入力として与えられたデータが二値ベクトルであっても、平均の演算により、代表ベクトルは実数のベクトルになる。そのため、ステップ2における距離計算では、二値ベクトルと実数ベクトルとの間の距離を求めなければならなくなる。浮動小数点演算が必要になってしまう。このように、k−meansクラスタリングにおいても、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。上記のように、識別器(Classifier)による認識処理やk−meansクラスタリングでは、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。その理由は、いずれもd次元の二値ベクトルp∈{−1,1}dと、d次元の実数ベクトルq∈Rdとの内積演算が必要であるという点にある。k−meansクラスタリングで必要なのは、dビットの二値ベクトルp∈{−1,1}dと、d次元の実数ベクトルq∈Rdとの間の「距離」であるが、これも結局のところ、pTqという内積の演算に帰着される。pとqとの間のユークリッド距離の二乗は、下式で表現されるからである。よって、識別器による認識処理においてもk−meansクラスタリングにおいても、二値ベクトルとd次元の実数ベクトルとの内積の演算を高速化することこそが、問題の解決につながる。そこで、本出願人は、特徴ベクトルがd次元の二値ベクトルp∈{−1,1}dである場合において、そのような特徴ベクトルとd次元の実数ベクトルq∈Rdとの間の内積(pTqもしくはqTp)の演算を高速に行う関連性判定装置を提案している(特許文献1)。特許文献1の関連性判定装置は、二値化された特徴ベクトルを取得する特徴ベクトル取得部と、実数ベクトルを二値または三値の離散値のみから構成された要素を持つ複数の基底ベクトルの線形和に分解することで得られた前記複数の基底ベクトルを取得する基底ベクトル取得部と、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算を順次行うことで、前記実数ベクトルと前記特徴ベクトルとの関連性を判定するベクトル演算部とを備えている。この構成により、実数ベクトルは複数の二値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。二値化された特徴ベクトルと複数の実数ベクトルとの内積計算を伴う対象の認識を高速に行う認識装置を提供する。物体認識装置30は、二値化された特徴ベクトルxを取得する場御なりコード変換部33と、特徴ベクトルを識別するための複数のクラスの辞書としての複数の実数ベクトルq1〜qLからなる実数行列Qを、複数のMiCi(i=1〜N、Nは2以上の自然数)の和に分解するパラメータ行列分解部35と、特徴ベクトルxと複数の実数ベクトルq1〜qLの各々との内積の計算として、特徴ベクトルxと基底行列Miとの積xMiを計算し、さらに当該積xMiと対応する係数行列Ciとの積を計算することで、特徴ベクトルxについて各クラスの識別を行う線形SVM識別部36とを備えている。請求項1二値化された特徴ベクトルxを取得する特徴ベクトル取得部と、前記特徴ベクトルを識別するための複数のクラスの辞書としての複数の実数ベクトルq1〜qLからなる実数行列Qを、複数のMiCi(i=1〜N、Nは2以上の自然数)の和に分解する実数行列分解部と、ここで、Miは要素として二値又は三値の離散値のみをもつ複数の基底ベクトルからなる基底行列であり、Ciは実数の要素をもつ係数行列であり、MiCiは前記基底行列と前記係数行列との積であり、前記特徴ベクトルxと前記複数の実数ベクトルq1〜qLの各々との内積の計算として、前記特徴ベクトルxと前記基底行列Miとの積xMiを計算し、さらに当該積xMiと対応する前記係数行列Ciとの積を計算することで、前記特徴ベクトルxについて各クラスの識別を行う識別部と、を備えたことを特徴とする認識装置。請求項2前記識別部は、前記積xMiを計算し、さらに当該積xMiと対応する前記係数行列Ciとの積を計算するごとに、所定の閾値と比較して早期棄却を行うことを特徴とする請求項1に記載の認識装置。請求項3前記識別部は、早期棄却された前記クラスについては、前記積xMi及び当該積xMiと対応する前記係数行列Ciとの積を計算しないことを特徴とする請求項2に記載の認識装置。分解後の残差の分解を繰り返すことで、前記複数のMiCiを得ることを特徴とする請求項1ないし3のいずれか一項に記載の認識装置。前記複数の実数ベクトルq1〜qLに対して互いに相関が高いものをまとめるグルーピングを行い、グループごとに前記MiCiを得ることを特徴とする請求項1ないし4いずれか一項に記載の認識装置。分解後の残差の分解を行うごとに、前記グルーピングを行うことを特徴とする請求項5に記載の認識装置。請求項7二値化された特徴ベクトルxを取得する特徴ベクトル取得部と、前記特徴ベクトルを識別するための複数のクラスの辞書としての複数の実数ベクトルq1〜qLからなる実数行列Qを複数のMiCi(i=1〜N、Nは2以上の自然数)の和に分解することで得られた前記複数のMiCiを用いて、i=1から順にiを増加させつつ、前記特徴ベクトルxと前記複数の実数ベクトルq1〜qLの各々との内積の計算として、前記特徴ベクトルxと前記基底行列Miとの積xMiを計算し、さらに当該積xMiと対応する前記係数行列Ciとの積を計算して、近似行列yを求め、前記近似行列yの各要素を所定の閾値行列tiの各要素と比較することで、前記特徴ベクトルxについて各クラスの識別を行う識別部と、を備え、ここで、Miは要素として二値又は三値の離散値のみをもつ複数の基底ベクトルからなる基底行列であり、Ciは実数の要素をもつ係数行列であり、MiCiは前記基底行列と前記係数行列との積であることを特徴とする認識装置。0001本発明は、特徴ベクトルの認識を行う認識装置及び認識方法、並びに実数行列を分解する実数行列分解方法に関するものである。パターン認識など、多くの分野で特徴量が用いられている。情報を、計算機で扱いやすいように変換したものである。特徴量は、D次元のベクトル(特徴ベクトル)で表される。0003特徴ベクトルを用いた演算を行うことで、例えば、コンテンツの類似度を判定することができる。画像αの特徴ベクトルと、画像βの特徴ベクトルの距離が小さければ、αとβは似ているとみなすことができる。同様に、音声波形αの特徴ベクトルと、音声波形βの特徴ベクトルとの距離が小さければ、αとβは似ているとみなすことができる。パターン認識等の情報処理では、情報を特徴ベクトルに変換して、特徴ベクトル同士を比較して、その距離を求めることにより情報の類似度を判断する。0004特徴ベクトル間の距離の尺度としては、L1ノルム、L2ノルム、ベクトル間角度などが用いられる。これらは、特徴ベクトルx,y∈RDについて、次のように計算できる。L1ノルムL2ノルムベクトル間角度0005特徴ベクトルが実数ベクトルである場合には、以下のような問題がある。2つの特徴ベクトルx,y∈RDの間の距離の計算が遅くなるという問題がある。L2ノルムの二乗を距離の尺度として用いる場合、であるから、D回の引き算、D回の乗算、D−1回の加算が必要である。特徴ベクトルが浮動小数で表現される場合には、この計算負荷は非常に高くなる。特徴ベクトルが高次元になれば、この計算負荷はさらに高くなる。0006また、大量のメモリを消費する点も問題となる。特徴ベクトルを4バイトの単精度実数で表現する場合、D次元の特徴ベクトルは4Dバイトのメモリを消費する。特徴ベクトルが高次元になれば、このメモリ消費量は大きくなる。大量の特徴ベクトルを扱う場合、扱う特徴ベクトルの数だけメモリを消費することになる。0007そこで近年、特徴ベクトルを0と1の列から成るバイナリコードに変換することにより、これら2つの問題を解決する手法が提案されている。Hashing、非特許文献3参照)がある。0008これらの手法では、D次元の特徴ベクトルがdビットのバイナリコードに変換される。この変換は、もともとの空間における距離が、変換後の空間におけるハミング距離と強く相関するように行われる(もともとの空間における距離と、変換後の空間におけるハミング距離と強く相関する根拠については、非特許文献1の1121ページのLemma3.2を参照)。これによって、特徴ベクトル間の距離の計算を、バイナリコード同士のハミング距離計算で代用できるようになる。0009ハミング距離とは、二つのバイナリコードのうち、異なるビットの数を数えたものである。この計算は、二つのコードのXORをとった後に1が立っているビット数を数えるだけなので、非常に高速に行うことができる。多くの場合、バイナリコード変換によって、数十〜数百倍程度の高速化が可能である。特徴ベクトル間の距離の計算を、バイナリコード同士のハミング距離計算で代用することにより、もともと4Dバイトであったメモリの必要容量を、d/8バイトまで削減できる。これにより、数十〜数百分の一にメモリ容量を節約できる。0010抽出された特徴量をバイナリコードに変換して、さまざまなアルゴリズムを適用することで、コンテンツの検索や認識などが可能となる。類似コンテンツを検索する場合には、あらかじめデータベースに登録されているコンテンツの特徴量を、すべてバイナリコードに変換しておく。入力クエリとして与えられたコンテンツの特徴量をバイナリコードに変換する。入力クエリのバイナリコードと、データベースに登録されているすべてのバイナリコードとの間のハミング距離を計算することで、入力クエリに類似するコンテンツを検索して出力できる。0011バイナリコードはdビットの0と1の列からなる。これを、各要素が−1及び1の二値のみを取るd次元のベクトルと考えることもできる。以下の説明における混乱を避けるために、「バイナリコード」と「二値ベクトル」という用語について、以下のように区別をする。「バイナリコード」は、0と1の列からなるデータ表現である。char)型の16要素分の配列を用意すればよい(8bit×16=128bit)。0012一方、「二値ベクトル」は、各要素が二値のみを取るベクトルである。二値ベクトルを各要素が−1及び1のみをとるベクトルとする場合には、バイナリコード「01101110」に対応する二値ベクトルは、(−1,1,1,−1,1,1,1,−1)Tである。各要素が0及び1の二値のみを取るベクトルも二値ベクトルであるし、さらには、各要素が任意のα及びβ(ここでα≠βである)の二値のみを取るベクトルも二値ベクトルである。「バイナリコード」と「二値ベクトル」の違いは、情報の表現に関するものであり、両者に本質的な違いはない。0013特徴ベクトルを、各要素が−1及び1の二値のみを取るd次元の二値ベクトルに変換すれば、SVM(サポートベクトルマシン)による識別処理や、k−meansクラスタリングなど、さまざまな処理をバイナリコードに対しても適用できる。これらのケースではハミング距離による高速距離計算の恩恵を受けることができないことがある。アルゴリズムによっては、バイナリコード変換による高速距離計算の恩恵を受けられないことがある。0014バイナリコード変換による高速距離計算の恩恵を受けられない例として、以下では、識別器(Classifier)による認識処理及びk−meansクラスタリングを説明する。識別器による認識処理については、例えば、二値ベクトルx∈{−1,1}dを2クラスに識別する問題に対して、線形SVM(線形サポートベクトルマシン)等の線形識別器を適用することを考える。線形SVMでは以下の式を評価する。f(x)が正ならばxはクラスAに属し、f(x)が負ならばxはクラスBに属するものとして識別する。wは、重みパラメータであって、w∈Rdである。bは、バイアスパラメータであって、b∈R1である。パラメータw及びbは、学習用に用意した特徴量を用いて、学習処理により自動的に決定される。0015ここで、学習用に用意した特徴量が二値ベクトルであっても、w∈Rdは二値にならず、実数値になってしまう。f(x)の計算にはwTxが含まれているが、xが二値である一方でwが実数値のベクトルであるため、wTxの計算には、浮動小数点演算が必要になってしまう。このように、SVMを適用する識別器による認識処理では、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。0016次に、二値ベクトルに対して、k−meansクラスタリングを適用する場合、すなわち、d次元の二値ベクトルがN個与えられたとき、互いに距離が近い二値ベクトルをまとめたk個のクラスタを求める問題を考える。k−meansとは、次の手順によりk個のクラスタと代表ベクトルを算出するアルゴリズムである。0017ステップ1:N個の特徴量からk個をランダムに選出し、これをクラスタの代表ベクトルとする。ステップ2:入力として与えられたN個の特徴量それぞれについて、最も距離が近い代表ベクトルを求める。ステップ3:各代表ベクトルに所属する特徴量の平均を計算し、これを新しい代表ベクトルとする。ステップ4:ステップ2、ステップ3を収束するまで繰り返す。0018k−meansクラスタリングにおいて問題となるのは、ステップ3において、新しい代表ベクトルが二値ベクトルの平均で定義される点である。入力として与えられたデータが二値ベクトルであっても、平均の演算により、代表ベクトルは実数のベクトルになる。そのため、ステップ2における距離計算では、二値ベクトルと実数ベクトルとの間の距離を求めなければならなくなる。浮動小数点演算が必要になってしまう。このように、k−meansクラスタリングにおいても、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。0019上記のように、識別器(Classifier)による認識処理やk−meansクラスタリングでは、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。その理由は、いずれもd次元の二値ベクトルp∈{−1,1}dと、d次元の実数ベクトルq∈Rdとの内積演算が必要であるという点にある。k−meansクラスタリングで必要なのは、dビットの二値ベクトルp∈{−1,1}dと、d次元の実数ベクトルq∈Rdとの間の「距離」であるが、これも結局のところ、pTqという内積の演算に帰着される。pとqとの間のユークリッド距離の二乗は、下式で表現されるからである。0020よって、識別器による認識処理においてもk−meansクラスタリングにおいても、二値ベクトルとd次元の実数ベクトルとの内積の演算を高速化することこそが、問題の解決につながる。0021そこで、本出願人は、特徴ベクトルがd次元の二値ベクトルp∈{−1,1}dである場合において、そのような特徴ベクトルとd次元の実数ベクトルq∈Rdとの間の内積(pTqもしくはqTp)の演算を高速に行う関連性判定装置を提案している(特許文献1)。0022特許文献1の関連性判定装置は、二値化された特徴ベクトルを取得する特徴ベクトル取得部と、実数ベクトルを二値または三値の離散値のみから構成された要素を持つ複数の基底ベクトルの線形和に分解することで得られた前記複数の基底ベクトルを取得する基底ベクトル取得部と、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算を順次行うことで、前記実数ベクトルと前記特徴ベクトルとの関連性を判定するベクトル演算部とを備えている。この構成により、実数ベクトルは複数の二値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。2008.発明が解決しようとする課題0025二値化された特徴ベクトルと複数の実数ベクトルとの内積を計算することで、特徴ベクトルと複数の実数ベクトルの各々との関連性を判定する必要がある場合がある。上述のように、線形SVMでは、特徴ベクトルがクラスAに属するか、クラスBに属するか、即ち、特徴ベクトルがある識別基準に該当するか否かのみを判断するものであるが、このような識別を複数の基準について行いたい場合がある。具体的な例としては、撮影された画像に映っているのが、大人であるか否か、子供であるか否か、車であるか否か、道路標識であるか否かをそれぞれ判断したい場合がある。0026また、上述のk−meansクラスタリングでは、入力として与えられたN個の特徴ベクトルの各々について、k個の代表ベクトルとの間で内積計算を伴う距離の計算を行う。ここで、k個の代表ベクトルの各々は、上述のように、二値ベクトルの平均で定義されるので、実数ベクトルである。よって、k−meansクラスタリングでも、二値化された特徴ベクトルと複数の実数ベクトルとの内積計算が必要となる。0027そこで、本発明は、二値化された特徴ベクトルと複数の実数ベクトルとの内積計算を高速化することを目的とする。課題を解決するための手段0028本発明の一態様は、認識装置であり、この認識装置は、二値化された特徴ベクトルxを取得する特徴ベクトル取得部と、前記特徴ベクトルを識別するための複数のクラスの辞書としての複数の実数ベクトルq1〜qLからなる実数行列Qを、複数のMiCi(i=1〜N、Nは2以上の自然数)の和に分解する実数行列分解部と、前記特徴ベクトルxと前記複数の実数ベクトルq1〜qLの各々との内積の計算として、前記特徴ベクトルxと前記基底行列Miとの積xMiを計算し、さらに当該積xMiと対応する前記係数行列Ciとの積を計算することで、前記特徴ベクトルxについて各クラスの識別を行う識別部とを備えた構成を有している。ここで、Miは要素として二値又は三値の離散値のみをもつ複数の基底ベクトルからなる基底行列であり、Ciは実数の要素をもつ係数行列であり、MiCiは前記基底行列と前記係数行列との積である。0029この構成により、特徴ベクトルと複数の実数ベクトルの各々との内積計算のために、複数の実数ベクトルからなる実数行列を複数の離散値の基底行列と係数行列の積の和に分解した上で、特徴ベクトルと各基底行列との積を計算し、さらにそれらの各積と対応する係数行列との積を計算するので、特徴ベクトルと複数の実数ベクトルの各々との内積演算を高速に行うことができる。実数行列を複数の基底行列と係数行列の積の和に分解するので、実数行列のクラス数が多い場合にも、各基底行列の基底数は比較的小さく抑えることができ、分解の処理負担を軽減できる。0030前記識別部は、前記積xMiを計算し、さらに当該積xMiと対応する前記係数行列Ciとの積を計算するごとに、所定の閾値と比較して早期棄却を行ってよい。0031この構成により、複数の基底行列と係数行列の積を利用して、識別をカスケード化でき、識別の速度を大幅に高速化できる。0032前記識別部は、早期棄却された前記クラスについては、前記積xMi及び当該積xMiと対応する前記係数行列Ciとの積を計算しなくてよい。0033この構成により、早期棄却されたクラスについての計算を省略して、識別処理を高速化できる。分解後の残差の分解を繰り返すことで、前記複数のMiCiを得てよい。0035この構成により、残差を徐々に小さくしていくことで、複数のMiCiの和への分解が行われるので、インデクスiが小さいほどもとの実数行列Qに対する寄与度が大きくなる。前記複数の実数ベクトルq1〜qLに対して互いに相関が高いものをまとめるグルーピングを行い、グループごとに前記MiCiを得てよい。0037この構成により、相関が高い複数の実数ベクトルからなるグループごとに分解を行うので、少ない基底数で分解を行うことができる。分解後の残差の分解を行うごとに、前記グルーピングを行ってよい。0039この構成により、カスケード処理の各段で最適なグループを選択できる。0040本発明の他の態様の認識装置は、二値化された特徴ベクトルxを取得する特徴ベクトル取得部と、前記特徴ベクトルを識別するための複数のクラスの辞書としての複数の実数ベクトルq1〜qLからなる実数行列Qを複数のMiCi(i=1〜N、Nは2以上の自然数)の和に分解することで得られた前記複数のMiCiを用いて、i=1から順にiを増加させつつ、前記特徴ベクトルxと前記複数の実数ベクトルq1〜qLの各々との内積の計算として、前記特徴ベクトルxと前記基底行列Miとの積xMiを計算し、さらに当該積xMiと対応する前記係数行列Ciとの積を計算して、近似行列yを求め、前記近似行列yの各要素を所定の閾値行列tiの各要素と比較することで、前記特徴ベクトルxについて各クラスの識別を行う識別部とを備えた構成を有している。ここで、Miは要素として二値又は三値の離散値のみをもつ複数の基底ベクトルからなる基底行列であり、Ciは実数の要素をもつ係数行列であり、MiCiは前記基底行列と前記係数行列との積である。0041この構成により、複数の基底行列と係数行列の積を利用して、カスケードによる識別を行うことができる。前記第5ステップの後に、前記第3ステップに戻り、直前の前記第4ステップにて得られた前記新たな残差行列Rを、前記第5ステップでインクリメントされた前記iで分解する構成を有している。ここで、Miは要素として二値又は三値の離散値のみをもつ複数の基底ベクトルからなる基底行列であり、Ciは実数の要素をもつ係数行列であり、MiCiは前記基底行列と前記係数行列との積である。0043この構成により、実数行列Qを複数のMiCiの和に分解することができ、かつ、残差を徐々に小さくしていくので、インデクスiが小さいほど、もとの実数行列Qに対する寄与度を大きくできる。0044本発明のさらに他の態様は、認識装置において特徴ベクトルxについて複数のクラスでの識別を行う認識方法であって、この認識方法は、前記認識装置が、iを1として、特徴ベクトルxとMiCiとの積を計算して、近似行列yを得る第1ステップと、前記認識装置が、前記第1ステップの後に、前記近似行列yの各要素と所定の閾値行列tiの各要素とをそれぞれ比較して、前記閾値行列tiの要素よりも小さい前記近似行列yの要素について、negativeであると判定する第2ステップと、前記認識装置が、前記第2ステップの後に、前記iをインクリメントする第3ステップと、前記認識装置が、前記第3ステップの後に、前記第3ステップでインクリメントされた前記iで、前記特徴ベクトルxとMiCiとの積を計算する第4ステップと、前記認識装置が、前記第4ステップの後に、前記近似行列yに、前記第4ステップで計算された前記積を加えて、新たな近似行列yを取得する第5ステップとを含み、前記認識装置は、前記第5ステップの後に、前記第2ステップに戻り、直前の前記第5ステップで得られた新たな近似行列yについて、前記比較及び前記判定を行う構成を有している。ここで、Miは要素として二値又は三値の離散値のみをもつ複数の基底ベクトルからなる基底行列であり、Ciは実数の要素をもつ係数行列であり、MiCiは前記基底行列と前記係数行列との積である。0045この構成により、複数の基底行列と係数行列の積を利用して、カスケードによる識別を行うことができる。発明の効果0046本発明によれば、実数行列を複数の基底行列と係数行列の積の和に分解するので、実数行列のクラス数が多い場合にも、各基底行列の基底数は比較的小さく抑えることができ、分解の処理負担を軽減できる。実施例0048本明細書では、以下の順に本発明の実施の形態を説明する。I.第1の実施の形態1.概要2.実施の形態2−1.二値分解法2−2.二値分解法の拡張2−3.三値分解法2−4.三値分解法の拡張3.応用例3−1.第1の応用例3−2.第2の応用例3−3.第3の応用例II.第2の実施の形態1.概要2.実施の形態3.変形例III.第3の実施の形態1.概要2.実施の形態IV.変形例0049I.第1の実施の形態1.概要まず、特徴ベクトルとの内積を計算すべき実数ベクトルが複数ある場合について説明する。図1は、複数の識別基準で画像中の人を識別する場合の線形SVMの例を示す図である。この例では、入力されたある特徴ベクトルに対して、図1に示すように、単にその特徴ベクトルの画像内に人がいるか否かの識別ではなく、それが「大人(正面)」であるか否か、「大人(横)」であるか否か、「子供(正面)」であるか否かをそれぞれ識別する。特徴ベクトルを識別する基準が複数ある。この場合、図1に示すように、線形SVMの評価式f(x)の重みパラメータ(以下、「辞書」ともいう。)qは、識別基準ごとに複数(q1,q2,q3,...,qL)用意する必要があり、バイアスbも識別基準ごとに複数(b1,b2,b3,...,bL)用意する必要がある。図10050図2は、被写体までの距離に応じた複数の識別基準で画像中の人を識別する場合の線形SVMの例を示す図である。この例では、人の識別が、被写体までの距離、即ち画像内の被写体のスケールの変化に対してロバストとなるように、入力されたある特徴ベクトルに対して、図2に示すように、単にその特徴ベクトルの画像内に大人がいるか否かを識別するだけでなく、それが「大人(遠)」であるか否か、「大人(中距離)」であるか否か、「大人(近)」であるか否かをそれぞれ識別する。この場合も、特徴ベクトルを識別する基準が複数あり、よって、図2に示すように、線形SVMの辞書qは、識別基準ごとに複数(q1,q2,q3,...,qL)用意する必要があり、バイアスbも識別基準ごとに複数(b1,b2,b3,...,bL)用意する必要がある。図20051このように、ある特徴ベクトルに対して複数の基準で識別を行う場合には、それらの複数の基準が互いに似ていることが多い。図1及び図2もそのような例を示しており、即ち、図1の例では、「大人(正面)」と「大人(横)」は、大人という共通点を有し、「大人(正面)」と「子供(正面)」は、人の正面という共通点を有し、また、「大人(正面)」と「大人(横)」と「子供(正面)」は、人という共通点を有する。図2の例でも、「大人(遠)」と「大人(中距離)」と「大人(近)」は、「大人」という共通点を有する。よって、図1及び図2の複数の実数ベクトルである辞書(q1,q2,q3,...,qL)は互いに似ている。k−meansクラスタリングにおいても、k個の実数ベクトルである代表ベクトルが互いに似ていることが多い。本実施の形態の関連性判定装置は、このように複数の実数ベクトルが互いに似ているという性質を生かして、処理を高速化する。図1図20052本実施の形態の関連性判定装置は、二値化された特徴ベクトルを取得する特徴ベクトル取得部と、複数の実数ベクトルからなる実数行列を、係数行列と、要素として二値または三値の離散値のみを持つ複数の基底ベクトルからなる基底行列との積に分解する実数行列分解部と、前記特徴ベクトルと前記複数の実数ベクトルの各々との内積の計算として、前記特徴ベクトルと前記基底行列との積を計算し、さらに当該積と前記係数行列との積を計算して、その結果を用いて、前記複数の実数ベクトルの各々と前記特徴ベクトルとの関連性を判定するベクトル演算部とを備えた構成を有している。この構成により、特徴ベクトルと複数の実数ベクトルの各々との内積を計算のために、複数の実数ベクトルからなる実数行列を離散値の基底行列と係数行列に分解したうえで、特徴ベクトルと基底行列との積を計算し、さらに係数行列との積を計算するので、特徴ベクトルと複数の実数ベクトルの各々との内積演算の結果を高速に取得でき、よって特徴ベクトルと複数の実数ベクトルとの関連性の判定を高速に行うことができる。0053上記の関連性判定装置は、前記複数の実数ベクトルを並べることで前記実数行列を生成する実数行列生成部をさらに備えていてよい。この構成により、容易に複数の実数ベクトルから実数行列を生成できる。前記複数の実数ベクトルが所定のパラメータを有する場合に、当該パラメータの順に従って前記複数の実数ベクトルを並べることにより前記実数行列を生成してよい。この構成により、実数行列において互いに似た実数ベクトルが隣り合うこととなるので、隣り合う係数行列もまた類似するようになる。コスト関数として、前記コスト関数を解くことにより前記実数行列を分解してよい。ここで、Qは前記実数行列、Mは前記基底行列、Cは前記係数行列である。この構成により、実数行列を基底行列と係数行列との積に分解したときの誤差をコストとして評価して、実数行列を分解するので、容易かつ高精度に実数行列を分解できる。具体的には、このコスト関数を最小にする(所定の収束条件を満たす)基底行列及び係数行列で実数行列を分解することができる。前記基底行列の要素を固定して前記係数行列の要素を最小二乗法で最適化する第1の更新と、前記係数行列の要素を固定して前記基底行列の要素を全探索で最適化する第2の更新とを繰り返すことで、前記基底行列及び前記係数行列を求めてよい。この構成により、容易に実数行列を分解できる。係数行列の要素を固定すると、基底行列の各行を求めるときに探索すべき組み合わせ数は、二値分解の場合は2k通り、三値分解の場合は3k通りしかないので、全探索を行っても計算量が多くなりすぎることはない。コスト関数として、前記コスト関数を解くことにより前記実数行列を分解してよい。ここで、Qは前記実数行列、Mは前記基底行列、Cは前記係数行列、λは係数である。この構成によっても、実数行列を基底行列と係数行列との積に分解したときの誤差をコストとして評価して、容易かつ高精度に実数行列を分解できるとともに、係数行列を疎にすることができるので、特徴ベクトルと実数行列との積を高速に計算できる。具体的には、このコスト関数を最小にする(所定の収束条件を満たす)基底行列及び係数行列で実数行列を分解することができる。前記基底行列の要素を固定して前記係数行列の要素を近接勾配法で最適化する第1の更新と、前記係数行列の要素を固定して前記基底行列の要素を全探索で最適化する第2の更新とを繰り返すことで、前記基底行列及び前記係数行列を求めてよい。この構成により、容易に実数行列を分解できる。係数行列の要素を固定すると、基底行列の各行を求めるときに探索すべき組み合わせ数は、二値分解の場合は2k通り、三値分解の場合は3k通りしかないので、全探索を行っても計算量が多くなりすぎることがない。コスト関数として、前記コスト関数を解くことにより前記実数行列を分解してよい。ここで、Qは前記実数行列、Mは前記基底行列、Cは前記係数行列、Pは複数の前記特徴ベクトルの集合である。この構成により、実数行列の分解の誤差ではなく、複数の特徴ベクトルを用いて、特徴ベクトルと実数行列との積の分解による誤差をコストとして評価するので(データ依存分解)、特徴ベクトルと実数行列との積をより高精度に近似できる。具体的には、このコスト関数を最小にする(所定の収束条件を満たす)基底行列及び係数行列で実数行列を分解することができる。前記基底行列の要素を固定して前記係数行列の要素を最小二乗法で最適化する第1の更新と、前記係数行列の要素を固定して組合最適化問題を解くことで前記基底行列の要素を最適化する第2の更新とを繰り返すことで、前記基底行列及び前記係数行列を求めてよい。この構成により、容易に実数行列を分解できる。組合最適化問題は、例えば、グリーディアルゴリズム、タブーサーチ、シミュレイテッドアニーリング等のアルゴリズムを用いて解くことができる。コスト関数として、前記コスト関数を解くことにより前記実数行列を分解してよい。ここで、Qは前記実数行列、Mは前記基底行列、Cは前記係数行列、Pは複数の前記特徴ベクトルの集合、λは係数である。この構成により、実数行列の分解の誤差ではなく、複数の特徴ベクトルを用いて、特徴ベクトルと実数行列との積の分解による誤差をコストとして評価するので(データ依存分解)、特徴ベクトルと実数行列との積をより高精度に近似できるとともに、係数行列を疎にすることで特徴ベクトルと実数行列との積を高速に計算できる。具体的には、このコスト関数を最小にする(所定の収束条件を満たす)基底行列及び係数行列で実数行列を分解することができる。前記基底行列の要素を固定して前記係数行列の要素を近接勾配法で最適化する第1の更新と、前記係数行列の要素を固定して組合最適化問題を解くことで前記基底行列の要素を最適化する第2の更新とを繰り返すことで、前記基底行列及び前記係数行列を求めてよい。この構成により、容易に実数行列を分解できる。組合最適化問題は、例えば、グリーディアルゴリズム、タブーサーチ、シミュレイテッドアニーリング等のアルゴリズムを用いて解くことができる。コスト関数として、前記コスト関数を解くことにより前記実数行列を分解して前記基底行列及び前記係数行列の要素の初期値を求め、又は、をコスト関数として、前記コスト関数を解くことにより前記実数行列を分解して前記基底行列及び前記係数行列の要素の初期値を求めてよい。この構成により、データ非依分解により得られた基底行列及び係数行列を初期値とするので、十分に良好な初期解からデータ依存分解のための更新の繰り返しを開始でき、よって効果的にコストを減少させることができる。前記基底行列及び前記係数行列の要素の初期値を変えて、複数とおりの前記基底行列及び前記係数行列を求め、前記コスト関数が最小となる前記基底行列及び前記係数行列を採用することで前記実数行列を分解してよい。この構成により、初期値によるばらつきを軽減して、分解の誤差をより小さくできる。0065上記の関連性判定装置において、前記特徴ベクトルは、HOG特徴量であってよく、前記複数の実数ベクトルは、複数の線形識別器のパラメータに対応する複数の重みベクトルであってよく、前記ベクトル演算部は、前記関連性の判定として、前記複数の線形識別器の識別関数によって、前記複数の基準の各々に対する前記特徴ベクトルの識別を行なってよい。この構成により、複数の線形識別器による特徴ベクトルの識別を高速化できる。前記特徴ベクトル及び前記複数の実数ベクトルが1又は複数のパラメータを有する場合に、当該パラメータの順に従って前記複数の実数ベクトルを並べることにより前記実数行列を生成し、前記ベクトル演算部は、前記係数行列を構成する複数のベクトルであって前記複数の実数ベクトルが並べられた方向と同方向の複数のベクトルの各々を前記パラメータに関する連続関数で表現し、前記識別関数を最大にする前記パラメータを、前記特徴ベクトルのパラメータ値として求めてよい。この構成により、複数の実数ベクトルをまとめて実数行列を生成する際に、複数の実数ベクトルをそれが滑らかに変化するパラメータの順に並べて実数行列を生成することで、識別関数をそのパラメータに関する連続関数で表現できるので、高い分解能で特徴ベクトルのパラメータ値を求めることができる。0067上記の関連性判定装置において、前記特徴ベクトルは、k−meansクラスタリングによるクラスタリングの対象となるベクトルであってよく、前記実数ベクトルは、k−meansクラスタリングにおける代表ベクトルであってよく、前記ベクトル演算部は、前記関連性の判定として、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なってよい。この構成により、k−meansクラスタリングにおける特徴ベクトルと代表ベクトルとの間の距離の演算を高速化できる。treeによる近似最近傍探索の対象となるベクトルであってよく、前記実数ベクトルは、k−分木のノードに登録されている代表ベクトルであってよく、前記ベクトル演算部は、前記関連性の判定として、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なってよい。treeによる近似最近傍探索における特徴ベクトルとk−分木のノードに登録されている代表ベクトルとの間の距離の演算を高速化できる。0069上記の関連性判定装置において、前記特徴ベクトルは、画像の特徴量を表すベクトルであってよい。この構成により、画像の特徴量の演算における特徴ベクトルと複数の実数ベクトルの内積計算を高速化できる。0070本実施の形態の関連性判定プログラムは、コンピュータを、上記の関連性判定装置として機能させるための関連性判定プログラムである。この構成によっても、特徴ベクトルと複数の実数ベクトルの各々との内積を計算のために、複数の実数ベクトルからなる実数行列を離散値の基底行列と係数行列に分解したうえで、特徴ベクトルと基底行列との積を計算し、さらに係数行列との積を計算するので、特徴ベクトルと複数の実数ベクトルの各々との内積演算の結果を高速に取得でき、よって特徴ベクトルと複数の実数ベクトルとの関連性の判定を高速に行うことができる。0071本実施の形態の関連性判定方法は、二値化された特徴ベクトルを取得する特徴ベクトル取得ステップと、複数の実数ベクトルからなる実数行列を、係数行列と、要素として二値または三値の離散値のみを持つ複数の基底ベクトルからなる基底行列との積に分解する実数行列分解ステップと、前記特徴ベクトルと前記複数の実数ベクトルの各々との内積の計算として、前記特徴ベクトルと前記基底行列との積を計算し、さらに当該積と前記係数行列との積を計算して、その結果を用いて、前記複数の実数ベクトルの各々と前記特徴ベクトルとの関連性を判定するベクトル演算ステップとを含む構成を有している。この構成によっても、特徴ベクトルと複数の実数ベクトルの各々との内積を計算のために、複数の実数ベクトルからなる実数行列を離散値の基底行列と係数行列に分解したうえで、特徴ベクトルと基底行列との積を計算し、さらに係数行列との積を計算するので、特徴ベクトルと複数の実数ベクトルの各々との内積演算の結果を高速に取得でき、よって特徴ベクトルと複数の実数ベクトルとの関連性の判定を高速に行うことができる。0072本実施の形態によれば、二値化された特徴ベクトルと複数の実数ベクトルの各々との内積計算を高速化でき、そのような特徴ベクトルと複数の実数ベクトルの各々との関連性の判定を高速に行うことができる。図3は、本発明の第1の実施の形態の二値分解法を採用する特徴量演算装置100の構成を示すブロック図である。特徴量演算装置100は、コンテンツ取得部101と、特徴ベクトル生成部102と、特徴ベクトル二値化部103と、実数行列取得部104と、実数行列分解部105と、ベクトル演算部106と、データベース107とを備えている。図30074本実施の形態の特徴量演算装置100は、後述するように、特徴ベクトルと辞書データとしてデータベースに保存された複数の実数ベクトルとの内積演算を伴うベクトル演算によって、特徴ベクトルと複数の実数ベクトルとの関連性を判定する関連性判定装置として機能する。特徴演算装置100は、本発明の関連性判定装置に相当する。0075関連性判定装置としての特徴量演算装置100は、コンピュータが本発明の実施の形態の関連性判定プログラムを実行することにより実現される。関連性判定プログラムは、記録媒体に記録されて、記録媒体からコンピュータによって読み出されてもよいし、ネットワークを通じてコンピュータにダウンロードされてもよい。0076コンテンツ取得部101は、画像データ、音声データ、文字データ等のコンテンツデータを取得する。これらのコンテンツデータは、外部機器から与えられるものであってもよく、コンテンツ取得部101で生成されるものであってもよい。コンテンツ取得部101がカメラであり、そこでコンテンツデータとして画像データが生成されてよい。0077特徴ベクトル生成部102は、コンテンツ取得部101にて取得されたコンテンツデータからD次元の特徴ベクトルを生成する。コンテンツが画像である場合には、特徴ベクトル生成部102は、画像の特徴量を抽出する。特徴ベクトル二値化部103は、特徴ベクトル生成部102で生成されたD次元の特徴ベクトルを二値化して、各要素が−1及び1の二値のみをとるd次元の二値ベクトルp∈{−1,1}dを生成する。この特徴ベクトル二値化部103は、本発明の「特徴ベクトル取得部」に相当する。0078なお、コンテンツ取得部101、特徴ベクトル生成部102、及び特徴ベクトル二値化部103からなる構成は、最終的に二値化された特徴ベクトルを取得できる構成であればよく、例えば、コンテンツ取得部101及び特徴ベクトル生成部102を備えずに、特徴ベクトル二値化部103が外部機器から特徴ベクトルを取得して、その取得した特徴ベクトルを二値化する構成であってよいし、また、特徴ベクトル二値化部103外部機器から二値化された特徴ベクトルを直接取得する構成であってもよい。0079実数行列取得部104は、複数のd次元の実数ベクトルqn∈Rd(n=1,2,...,L)を取得する。複数の実数ベクトルqnは、外部機器から与えられるものであってもよく、特徴量演算装置100の図示しない記憶装置から読み出されるものであってもよく、実数行列取得部104で生成されるものであってもよい。各実数ベクトルqnは、その要素に浮動小数を含む実数を持つ。ここで、複数の実数ベクトルqnを並べたものを実数行列Q=(q1,q2,...,qL)∈Rd×Lと表記する。0080このように複数の実数ベクトルqnをまとめた実数行列Qを用いると、図1及び図2の複数の線形SVMは、下式(1)のようにまとめて表現することができる。図1図20081実数行列分解部105は、図4に示すように、d行L列の実数行列Qを、二値の基底行列M∈{−1,1}d×kと係数行列との積に分解する。具体的には、実数行列分解部105は、d行L列の実数行列Qを、下式(2)によって、二値の要素を持つ基底行列Mと実数の要素を持つ係数行列Cに分解する。ここで、図4に示すように、M=(m1,m2,...,mk)∈{−1,1}d×kであり、C=(c1,c2,...,cL)T∈Rk×Lである。図40082すなわち、基底行列Mは、k個の基底ベクトルmiからなり、ここで、基底ベクトルmiは、要素が−1及び1のみをとるd次元の二値ベクトルであり、従って、基底行列Mは、要素が−1及び1のみをとるd行k列の二値行列である。0083また、係数行列Cは、L個(Lはクラス数)の係数ベクトルcnからなり、ここで、係数ベクトルcnは、k個(kは基底数)の基底ベクトルに係る実数の係数を要素として持つk次元の実数ベクトルである。105が実数行列Qを式(2)のように分解する手法を説明する。0084(第1の分解手法)第1の分解手法として、データ非依存型の分解手法を説明する。第1の分解手法では、実数行列分解部105は、分解誤差を表す下式(3)のコスト関数g1を解くことで分解を行う。基底行列Mは二値であり、M∈{−1,1}d×kである。0085実数行列分解部105は、以下の手順で上記のコスト関数g1を解く。(1)基底行列M及び係数行列Cをランダムに初期化する。(2)基底行列Mの要素を固定して、係数行列Cの要素を最小二乗法により最適化することで、コスト関数g1が最小になるように係数行列Cの要素を更新する。(3)係数行列Cの要素を固定して、コスト関数g1が最小になるように全探索で基底行列Mの要素を更新する。この最小化アルゴリズムである全探索については、後に詳しく述べる。(4)収束するまで(2)及び(3)を繰り返す。コスト関数g1が所定の収束条件(例えば、減少量が一定値以下となる)を満たしたときに、収束したと判定する。(5)ステップ(1)〜ステップ(4)により得た解を候補として保持する。(6)ステップ(1)〜ステップ(5)を繰り返し、最もコスト関数g1を小さくできた候補基底行列M及び候補係数行列Cを最終結果として採用する。このステップ(1)〜ステップ(5)の繰り返しはなくてもよいが、複数回繰り返すことで、初期値依存の問題を回避できる。0086次に、ステップ(3)における基底行列Mの更新処理を説明する。図5の破線枠で囲ったように、基底行列Mのj行目の行ベクトルの要素は、実数行列のj行目の要素のみに依存する。よって、基底行列Mの各行ベクトルの値は、他の行とは独立して最適化することができるので、基底行列Mは、行ごとに網羅探索(全探索)を行うことができる。基底行列Mのj行目の行ベクトルは、本実施の形態のように二値分解の場合は2k通りしか存在しない(なお、後述の三値分解の場合にも3k通りしか存在しない)。よって、実数行列分解部105は、これらをすべて網羅的にチェックし、コスト関数g1を最小化する行ベクトルを採用する。これを基底行列Mのすべての行ベクトルに対して適用して、基底行列Mの要素を更新する。図50087(第2の分解手法)第2の分解手法として、係数行列Cを疎にするデータ非依存型の分解手法を説明する。第2の分解手法では、実数行列分解部105は、分解誤差である下式(4)のコスト関数g2を解くことで分解を行う。基底行列Mは二値であり、M∈{−1,1}d×kである。|C|1は、係数行列Cの要素のL1ノルムであり、λはその係数である。0088実数行列分解部105は、以下の手順で上記のコスト関数g2を解く。(1)基底行列M及び係数行列Cをランダムに初期化する。(2)基底行列Mの要素を固定して、係数行列Cの要素を近接勾配法で最適化する。(3)係数行列Cの要素を固定して、コスト関数g2が最小になるように全探索で基底行列Mの要素を更新する。(4)収束するまで(2)及び(3)を繰り返す。コスト関数g2のが所定の収束条件(例えば、減少量が一定値以下となる)を満たしたときに、収束したと判定する。(5)ステップ(1)〜ステップ(4)により得た解を候補として保持する。(6)ステップ(1)〜ステップ(5)を繰り返し、最もコスト関数g2を小さくできた候補基底行列M及び候補係数行列Cを最終結果として採用する。このステップ(1)〜ステップ(5)の繰り返しはなくてもよいが、複数回繰り返すことで、初期値依存の問題を回避できる。0089第2の分解手法によれば、係数行列Cを疎にすることができる。係数行列Cを疎にすることで、積MCの計算において、係数行列Cのゼロ要素にかかわる部分を省略することができ、さらに高速に内積計算を行うことができる。0090(第3の分解手法)次に、第3の分解手法を説明する。第1の分解手法では、コスト関数g1として、分解誤差を定義し、この分解誤差を最小化することを考えた。実数行列を基底行列と係数行列との積に近似した後に実際に近似をしたいのは、特徴ベクトルと実数行列の積QTpである。0091そこで、第3の分解手法では、特徴ベクトルpをあらかじめS個集め、これをまとめたものをP∈Rd×Sとする。分解誤差をと定義して、これを最小化する。第3の分解手法では、実数行列分解部105は、下式(5)のコスト関数g3を解くことで分解を行う。このコスト関数g3によれば、実数行列Qは、実際のデータの分布に従って分解されることになるため、分解の際の近似精度が向上する。0092この近似分解は、基底ベクトルmiを逐次的に求めることで行うことができる。第3の分解手法の手順は以下のとおりである。(1)第1又は第2の分解手法によって、基底行列M及び係数行列Cを求めて、これをそれらの初期値とする。(2)基底行列Mの要素を固定して、係数行列Cの要素を最小二乗法で最適化する。(3)係数行列Cの要素を固定して、基底行列Mの要素を最適化することで、基底行列Mの要素を更新する。この基底行列Mの更新処理については後述する。(4)収束するまで(2)及び(3)を繰り返し、コスト関数g3を最小化した基底行列M及び係数行列Cを候補として保持する。(5)ステップ(1)〜(6)を繰り返し、コスト関数g3を最小化した基底行列M及び係数行列Cを最終結果として採用する。ステップ(1)では再度第1又は第2の分解手法による基底行列M及び係数行列Cの最適化が行われるので、初期値が変更される。ステップ(5)の繰り返しはなくてもよいが、複数回繰り返すことで、初期値依存の問題を軽減できる。0093次に、ステップ(3)における基底行列Mの更新処理を説明する。データ依存分解の場合、基底行列Mの行ベクトルの値は、もはや他の行と独立せず、依存してしまう。基底行列Mの要素は、二値又は三値、即ち離散値であるため、基底行列Mの最適化は、組合最適化問題となる。annealing)等のアルゴリズムを用いることができる。ステップ(1)でよい初期値が得られているので、これらのアルゴリズムでも良好に分解誤差を最小化できる。0094例えばグリーディアルゴリズムを用いる場合は、以下の手順で基底行列Mを最適化する。(3−1)基底行列Mの要素のうち、ランダムにT個を選択する。(3−2)2T通りの組み合わせ(後述の三値分解の場合は3T通り)を試し、最もコスト関数g3を最小化したものを採用する。(3−3)ステップ(3−1)及びステップ(3−2)を収束するまで繰り返す。0095(第4の分解手法)第4の分解手法は、第2の分解手法と第3の分解手法とを組み合わせてものである。具体的には、実数行列分解部105は、下式(6)のコスト関数g4を解くことで分解を行う。このコスト関数g4によれば、実数行列Qは、実際のデータの分布に従って分解されることになるため、分解の際の近似精度が向上するとともに、係数行列Cを疎にすることができる。第2の分解手法のメリットと第3の分解手法のメリットをいずれも得ることができる。具体的な分解の手順は、第3の分解手法と同様である。0096(第1及び第2の分解手法の変形例)上記の第1及び第2のデータ非依存分解の手法は、分解数をkとしたとき、2k通り(三値分解の場合は3k通り)の探索が必要であるため、kが大きいときは、適用が難しい。そのような場合は、あらかじめ実数行列Qに所属する実数ベクトルqnの互いの類似度を調べ、似ている実数ベクトルどうしをクラスタリングし、各クラスタに対して第1又は第2の分解手法を適用すればよい。0097ベクトル演算部106は、特徴ベクトルを用いた演算を行なう。演算の具体的内容については、後述にて、本実施の形態の特徴量演算装置100の応用例とともに具体的に説明する。この特徴ベクトルを用いた演算には、二値化された特徴ベクトルp∈{−1,1}dと実数行列分解部105にて分解された実数行列Qとの積QTpの計算が含まれる。以下では、まず、この積QTpの計算について説明する。0098積QTpは、下式(7)のように式変形できる。ここで、miTpは二値ベクトル同士の内積である。cn,iは、n番目のクラスの係数ベクトルcnのi番目の要素、即ち係数行列Cのi行n列の要素である。この二値ベクトル同士の内積miTpは、極めて高速に計算可能である。その理由は以下のとおりである。0099二値ベクトル同士の内積は、ハミング距離の演算に帰着できる。ハミング距離とは、2つのバイナリコードにおいて、値が異なるビットを数えたものであり、2つの二値ベクトルの間のハミング距離は、すなわち値が異なる要素数を数えたものである。ここで、miとpのハミング距離をDhamming(mi,p)と記述すると、内積miTpは、Dhamming(mi,p)と下式(8)の関係がある。ここで、前述のとおり、dはバイナリコードのビット数である。0100ハミング距離の演算は、2つのバイナリコードにおいて、XORを適用した後に、1が立っているビットを数えることで計算できるので、極めて高速である。二値ベクトルがバイナリコード(0と1のビット列)で表現されているのであれば、ハミング距離は、下式(9)で計算できる。ここで、XOR関数はmiとpをバイナリコード表現で考えたときに排他的論理和を取る操作であり、BITCOUNT関数はバイナリコードの1が立っているビット数を数えあげる処理のことである。0101以上をまとめると、積QTpは下式(10)のように変形できる。dビットのハミング距離計算をk回行い、k個のハミング距離について、係数行列Cに関する重み付け和を計算し、定数項を足したものがQTpになる。よって、kが十分小さければ、QTpを浮動小数点精度で計算するよりも、はるかに高速に計算できるようになる。0102データベース107には、実数行列分解部105にて分解された複数の実数行列Qについて、基底行列Mと係数行列Cの積が辞書データとして記憶されている。ベクトル演算部106は、データベース107から基底行列Mと係数行列Cとの積を読み出して、上記の演算を行う。0103以上のように、本実施の形態の特徴量演算装置100によれば、特徴ベクトルを用いた演算処理に特徴ベクトルと実数行列との積演算が含まれている場合にも、特徴ベクトルを二値化した上で、実数行列についても、二値行列である基底行列と係数行列との積に分解するので、特徴ベクトルと実数行列との積の計算において、特徴ベクトルと基底行列との積を計算した上で、さらに係数行列との積を計算することで、特徴ベクトルと実数行列との積演算を高速化できる。0104また、複数の実数ベクトルを1つの実数行列としてまとめ、その実数行列を二値行列である基底行列と係数行列とに分解するので、特許文献1の技術のように各実数ベクトルをそれぞれ分解する場合と比較して、基底行列を構成する基底ベクトルの個数、即ち基底数を小さくすることができる。原理的には、1クラスあたり1個以下の基底数(即ち、基底数k≦クラス数L)とすることも可能である。上記の二値分解法では、二値ベクトルmi、pを、それぞれ、mi∈{−1,1}d、p∈{−1,1}dと定義して、実数行列を二値の基底行列と実数の係数行列との積に分解することで積演算QTpが高速になることを説明した。́∈{−a,a}dとしても、それらの高速な積演算が可能である。́=a2(miTp)であることから、−1及び1により定義される二値ベクトル同士の内積にa2を掛ければよい。́∈{γ,δ}dとしても、高速な内積演算が可能である。実数であり、α≠β、γ≠δである。́は、−1及び1により定義される二値ベクトルmi及びpの各要素に線形変換を施すことで得られ、下式(11)及び(12)のように展開される。式(11)及び(12)中の太字の「1」は、長さがdですべての要素が1であるベクトルである。式(11)及び(12)中のA、B、C、Dは実数であり、式(11)及び(12)が成立するようにあらかじめ計算しておけばよい。́は、下式(13)のように展開できる。式(13)の括弧内の計算は、−1及び1からなる二値ベクトル同士の内積である。従って、特徴ベクトルが任意の二値の要素をもつ二値ベクトルにされ、かつ、実数行列を二値の基底行列と実数の係数行列との積に展開した場合にも、高速演算が可能である。次に、三値分解法を採用する特徴量演算装置を説明する。特徴量演算装置の構成は、図1に示した二値分解法の場合と同じである。二値分解法では、実数行列分解部105は、実数行列Qを式(1)によって二値の基底行列と実数の係数行列に分解したが、三値分解法を採用する特徴量演算装置100の実数行列分解部105は、実数行列を三値の基底行列と実数の係数行列に分解する。図10109実数行列分解部105は、d行L列の実数行列Q∈Rd×Lを、三値の基底行列と実数の係数行列の積に分解する。具体的には、実数行列分解部105は、d行L列の実数行列Q∈Rd×Lを、下式(14)によって、三値の要素を持つ基底行列Mと実数の要素を持つ係数行列Cに分解する。ここで、M=(m1,m2,...,mk)∈{−1,0,1}d×kであり、C=(c1,c2,...,cL)T∈Rk×Lである。基底行列Mは、k個の基底ベクトルmiからなり、ここで、基底ベクトルmiは、要素が−1、0、及び1のみをとるd次元の三値ベクトルであり、従って、基底行列Mは、要素が−1、0、及び1のみをとるd行k列の三値行列である。0110また、係数行列Cは、L個(Lはクラス数)の係数ベクトルcnからなり、ここで、係数ベクトルcnは、k個の基底ベクトルに係る実数の係数を要素として持つk次元の実数ベクトルである。QとMCはなるべく一致するように分解することが好ましいが、誤差を含んでもよい。実数行列分解部105は、二値分解法の場合と同様にして、第1〜第4の分解手法によって実数行列Qを分解できる。0111ベクトル演算部106は、積QTpを計算する。以下では、積QTpを計算するベクトル演算部106を特に、積演算部106とも呼ぶ。積QTpは、下式(15)のように式変形できる。ここで、miTpは、三値ベクトルmiと二値ベクトルpとの内積である。積演算部106は、ここで、三値ベクトルmiの代わりに、以下に定義する0置換ベクトルmibin、フィルタベクトルmifilter、及び0要素数ziを用いる。0112まず、積演算部106は、miの0の要素を、−1又1に置き換える。miの各要素について、それを−1に置き換えるか、1に置き換えるかは、いずれでもよい。この置き換えによって、0置換ベクトルmibin∈{−1,1}dが生成される。この0置換ベクトルmibin∈{−1,1}dは二値ベクトルである。0113また、積演算部106は、miの0の要素を−1に置き換え、0以外の要素を1に置き換える。この置き換えによって、フィルタベクトルmifilter∈{−1,1}dが生成される。このフィルタベクトルmifilterも二値ベクトルである。0114さらに、積演算部106は、miの0の要素数ziを求める。積演算部106は、これらの二値ベクトルmibin、フィルタベクトルmifilter、及び0要素数ziを用いて、式(15)におけるmiTpを、下の式(16)及び式(17)によって計算する。ここで、式(17)のAND関数は、二値ベクトルをバイナリコード表現で考えたときに、論理積を取る操作である。0115以下、図6の具体例を用いて、式(16)及び(17)の導出を説明する。図6は、本実施の形態の計算例を示す図である。図6の例では、p={−1,1,−1,1,−1,1}であり、mi={−1,0,1,0,1,1}である。この例では、mibin={−1,*,1,*,1,1}となる。ここで、「*」は−1又は1の任意のいずれかを示す。mifilter={1,−1,1,−1,1,1}となり、zi=2となる。図60116式(17)におけるpとmibinとの排他的論理和は、XOR(p,mibin)={−1,*,1,*,1,−1}となり、すなわち、pとmiの要素のうち、非0で異なっている要素すなわち−1と1又は1と−1の組となる要素が1となり、−1と−1又は1と1の組となる要素が−1となる。0117次に、その排他的論理和とmifilterとの論理積は、AND(XOR(p,mibin),mifilter))={−1,−1,1,−1,1,−1}となり、pとmiの要素のうち、非0で異なっている要素に1が立ち、それ以外は−1となる。このビットカウントを取ると、1である要素の個数、すなわち非0で異なっている要素の個数が数え上げられ、Dfiltered_hamming(p,mibin,mifilter)=2となる。0118ここで、pとmiの要素のうち、1と1又は−1と−1の組となる要素の個数は、全要素数d=6から、非0で異なっている要素の個数Dfiltered_hamming=2と0である要素の個数zi=2を引くことで求められる。1と1又は−1と−1の組となる要素の数=d−Dfiltered_hamming−zi=6−2−2=2となる。0119miTpは、1と1又は−1と−1の組となる要素(積が1になる要素の組)の個数から、−1と1又は1と−1との組となる要素(積が−1になる要素の組)の個数を引いた値と等しいため、miTp=(d−Dfiltered_hamming−zi)−Dfiltered_hamming=d−zi−2Dfiltered_hammingとなり、式(16)が得られ、その値は、6−2−2×2=0となる。この結果は、当然ながら、pTmi={−1,1,−1,1,−1,1}×{−1,0,1,0,1,1}=1+0+(−1)+0+(−1)+1=0と一致する。0120式(15)〜(17)をまとめると、積QTpは、下式(18)のように変形できる。積演算部106は、この式(18)によって、積QTpを計算する。0121関数Dfiltered_hamming(p,mibin,mifilter)は、ハミング距離演算と非常に似ており、AND演算が加わっただけである。したがって、Q∈Rd×Lを、三値行列と係数行列との積に分解した場合でも、QTpを浮動小数点精度で計算するよりも、はるかに高速にQTpを計算できるようになる。0122以上のように、d次元の実数行列Q∈Rd×Lを、二値ではなく三値の基底行列と係数行列との積に分解することの利点は、式(10)の近似が、より少ない数の基底数の基底行列でも成立するようになることにある。基底数を小さく抑えられることになるため、さらなる高速化につながる。上記の三値分解法の説明では、二値ベクトルp及び三値ベクトルmiを、それぞれ、p∈{−1,1}d、mi∈{−1,0,1}dと定義して、複数の実数ベクトルからなる実数行列を三値の基底行列と係数行列との積に分解することで内積演算pTmiが高速になることを説明した。́∈{−a,a}d、三値ベクトルmi∈{−a,0,a}dとしても、それらの高速な内積演算が可能である。́=a2(pTmi)であることから、−1及び1により定義される二値ベクトル同士の内積にa2を掛ければよい。0124さらに、二値ベクトルp及び三値ベクトルmiをp∈{α,β}d、mi∈{γ−δ,γ,γ+δ}dと一般化しても、高速な内積演算が可能である。ここで、α、β、γ、δは実数であり、α≠β、δ≠0である。式(19)及び(20)中の太字の「1」は、長さがdですべての要素が1であるベクトルである。式(19)及び(20)中のA、B、C、Dは実数であり、式(19)及び(20)が成立するようにあらかじめ計算しておく。́は、下式(21)のように展開できる。式(21)の括弧内の計算は、−1及び1からなる二値ベクトル同士の内積、又は−1及び1からなる二値ベクトルと−1、0、1からなる三値ベクトルとの内積である。従って、特徴ベクトルが任意の二値ベクトルにされ、かつ、実数行列を上記のとおり一般化した三値行列を用いて展開した場合にも、そのような特徴ベクトルと実数行列との積を高速に演算できる。次に、ベクトル演算部106における演算処理について説明する。上記の二値分解法及び三値分解法の特徴量演算装置100のベクトル演算部106は、二値化された特徴ベクトルpと複数の実数ベクトルqをまとめた実数行列Qとの積の計算を伴うものであるが、そのような演算処理は種々ある。本発明の上記の実施の形態は、特徴ベクトルを用いて演算処理を行なう種々の装置に応用できる。本応用では、本発明がHOG特徴量を用いてSVMにより複数種類の物体を認識する物体認識装置に応用される。図7は、物体認識装置の構成を示すブロック図である。物体認識装置10は、ピラミッド画像生成部11と、HOG特徴量抽出部12と、バイナリコード変換部13と、パラメータ決定部14と、パラメータ行列分解部15と、線形SVM識別部16と、ピーク検出部17とを備えている。図70128ピラミッド画像生成部11は、入力クエリとしての画像を取得して、当該画像を複数段階の倍率でそれぞれ縮小してなるG段のピラミッド画像を生成する。これにより、サイズの異なる物体に対処できる。このピラミッド画像生成部11は、図3に示したコンテンツ取得部101に対応する。HOG特徴量抽出部12は、ピラミッド画像の各段における画像を、16×16ピクセルのサイズのブロックに分割し、各ブロックからHOG特徴量を抽出する。HOG特徴量抽出部12は、各ブロックからD次元の特徴量を抽出する。このHOG特徴量抽出部12は、図3に示した特徴ベクトル抽出部102に対応する。バイナリコード変換部13は、各セルに与えられたD次元の特徴量を、d次元の二値ベクトルに変換する。このバイナリコード変換部13は、図3に示した特徴ベクトル二値化部103に対応する。図30129パラメータ決定部14は、認識したい対象の種類(大人、子供、車、バイクといった種類であって、パラメータで定義される)ごとに、それぞれ線形SVM識別部16における線形SVMにて用いる重みベクトルwn(n=1,2,...,L)及び実数のバイアスbn(n=1,2,...,L)を決定する。パラメータ決定部14は、学習用に用意された特徴量を用いて、学習処理によってL種類の重みベクトルwn及びバイアスbnを決定して、重みベクトルwnをまとめた重み行列Wを生成する。このパラメータ決定部14は、図3に示した実数行列取得部104に対応する。パラメータ行列分解部15は、重み行列Wを上記で説明した式(2)又は式(14)によって離散値の基底行列と係数行列との積に分解する。このパラメータ行列分解部15は、図3に示した実数行列分解部105に対応する。図30130線形SVM識別部16は、線形SVMによって特徴ベクトルの識別を行なう。線形SVM識別部16は、まず、sx×syブロックをひとまとまりとして、検出ウィンドウを構成する。1つの検出ウィンドウから抽出される特徴ベクトルは、sx×sy×d次元のベクトルとなる。線形SVM識別部16は、この特徴ベクトルに対して、下式(22)の線形SVMを適用する。ここで、線形SVMにおける積演算WTxは、上記で説明した実数行列と二値ベクトルの高速な積演算により実現できる。0131検出位置付近では、検出結果が固まることがある。そこで、ピーク検出部17は、周辺でf(x)の値が最大になったところを、代表的な検出位置とする。この線形SVM識別部16及びピーク検出部17は、特徴ベクトルを用いた処理を行なう構成であり、図3のベクトル演算部106に対応する。図30132次に、この物体認識装置10において、HOG特徴量により、回転し得る物体を検出する例を説明する。図8は、回転する道路標識について、それぞれの回転角度で辞書qn及びバイアスbnを作成する場合を示している。図8において左右方向は道路標識の回転角度θを示している。図80133従来のアプローチでは、回転角度ごとに学習処理を行って辞書qn及びバイアスbnを取得する。その後、入力画像からHOG特徴量を抽出して、検出ウィンドウ(スライディングウィンドウ)をL回適用することでこの道路標識の検出を行っている。このような従来の手法では、1検出ウィンドウあたりL回の内積計算が必要となり、計算量が多くなる。検出の角度分解能は2pi/Lであり、荒い。0134そこで、本応用例では、パラメータ決定部14が辞書qnをまとめて行列Qとし、SVM識別部16は、下式(23)により複数の辞書qnと特徴ベクトルpとの内積計算をまとめて行う。このようにk個の整数基底に分解することにより、1検出ウィンドウあたり、k回の二値と二値との内積演算又は二値と三値との内積演算で処理が可能となる。このとき、隣り合う辞書同士が似ているため、整数基底の数kを小さくすることができ、原理的には1クラスあたり1個以下(k≦L)とすることも可能である。0135本応用例では、さらに、ピーク検出部17が、係数行列Cの性質に着目した検出分解能の高精度化を行う。図9は、係数行列Cの性質を示す図である。実数ベクトルqnが回転角度θをパラメータとして、そのパラメータに従って変化するものである場合には、複数の実数ベクトルqnをまとめて実数行列Qを生成する際に、図8に示すように、複数の実数ベクトルqnをパラメータθの順に並べると、図9に示すように、係数行列Cの実数ベクトルqnが並べられた方向と同方向の各ベクトル、即ち係数行列Cの各行ベクトルの要素の行方向の変化が滑らかになる。図8図90136そこで、ピーク検出部17は、係数行列Cの行ベクトルを多項式でフィッティングして、下式(24)のように連続関数で表現する。ここで、αiは、フィッティングの係数である。0137これを用いて識別関数の式を整理すると、回転角度θにおける識別関数は下式(25)のようにパラメータθに関する連続関数の形式で表現できる。ピーク検出部17は、この識別関数を用いてピークの検出を行う。ci(θ)は式(24)に示すように多項式であるから、fθ(p)もまた連続関数(連続の多項式)となる。図10は、fθ(p)の例を示すグラフである。図10において、横軸は回転角度θであり、縦軸はfθ(p)である。ピーク検出部17は、fθ(p)が正の最大をとるときのθを対象の回転角度、即ち特徴ベクトルpのパラメータ値として検出する。図100138以上のように、複数の辞書qnをまとめて行列Qを生成する際に、複数の辞書qnをそれが滑らかに変化するように、パラメータ(図8の例ではθ)の順に並べて行列Qを生成することで、識別関数をそのパラメータに関する多項式の形式で表現できるので、高い分解能でそのパラメータを検出できるようになる。図80139なお、上記ではパラメータを回転角度として説明したが、パラメータは例えばスケールであってもよい。図2のように検出ウィンドウの大きさは固定とし、検出ウィンドウ内における人物のサイズ(スケール)ごとに、別々に識別器を学習しておき、スケールσに関して多項式のフィッティングを行い、スケールσに関して識別器のピークを求めることで、高精度にスケール推定をおこなえるようになる。このように工夫することで、ピラミッド画像自体の生成を不要とできる。パラメータが複数であってもよい。回転角度θとスケールσの両方に関して上記の多項式へのフィッティングを行ってもよい。この場合、係数はci(θ,σ)のように、二次元の多項式となる。図20140また、係数αiは、まず係数行列Cを求めてから各行をフィッティングして求めることができるが、係数行列Cの個々の要素cn,iを求めずに直接係数αiを求めてもよい。フィッティングする関数は多項式でなくてもよく、例えば三角関数(サイン、コサイン)にフィッティングしてもよい。本応用例では、本発明がk−meansクラスタリングに応用される。図11は、k−meansクラスタリング装置の構成を示すブロック図である。k−meansクラスタリング装置20は、コンテンツ取得部21と、特徴ベクトル生成部22と、特徴ベクトル二値化部23と、代表行列更新部24と、収束判定部25と、代表行列分解部26と、最近接代表ベクトル探索部27とを備えている。図110142コンテンツ取得部21は、クラスタリングの対象となるN個のコンテンツを取得する。特徴ベクトル生成部22は、コンテンツ取得部21にて取得した各コンテンツからそれらの特徴量を特徴ベクトルpとして抽出する。特徴ベクトル二値化部23は、特徴ベクトル抽出部22にて抽出された各特徴ベクトルを二値化する。0143代表行列更新部24は、まず、特徴ベクトル二値化部23で二値化されたN個の特徴ベクトルからk(=L)個をランダムに選出してこれを代表ベクトルqn(n=1,2,...,L)とし、これらの代表ベクトルqnをまとめた行列を代表行列Qとする。収束判定部25は、代表行列更新部24が代表行列を更新するごとに収束判定を行なう。収束判定部25にて収束したと判定された場合には、k−meansクラスタリング装置20はクラスタリングの処理を終了する。代表行列分解部26は、代表行列更新部24にて更新された代表行列を離散値(二値又は三値)行列に分解する。0144最近接代表ベクトル探索部27は、特徴ベクトル二値化部23より入力されるN個の二値ベクトルをそれぞれ最も近傍の代表ベクトルqnに所属させる。最近接代表ベクトル探索部27は、この結果を代表行列更新部24に出力する。代表行列更新部24は、各代表ベクトルqnについて、それに所属する特徴ベクトル(二値化されている)の平均ベクトルを算出して、これを新しい代表ベクトルqnとする。このようにして代表行列更新部24で更新される代表ベクトルqnは、二値ベクトルの平均で算出されるので、実数ベクトルとなる。0145従って、仮に代表行列分解部26がなければ、最近接代表ベクトル探索部27は、更新された代表ベクトル(実数ベクトル)と特徴ベクトル(二値ベクトル)との距離を求めるためにそれらの内積を計算しなければならない。そこで、本応用例では、上記のように、この代表ベクトルqn(実数ベクトル)の集合である代表行列Qを代表行列分解部26によって、上記の実施の形態で説明したように、離散値(二値又は三値)行列と実数の係数行列との積に分解する。それによって、最近接代表ベクトル探索部27における、各特徴ベクトルと各代表ベクトルとの距離の計算を高速にでき、よって各特徴ベクトルが最も近接する代表ベクトル(すなわち、所属すべき代表ベクトル)を高速に探索できる。treeによる近似最近傍探索に応用される。.cs.ubc.ca/~mariusm/uploads/FLANN/flann_visapp09.pdf)に提案されている手法を採用する。N個のデータに対してk−meansを再帰的に適用することでk−分木を構築し、上記提案の木探索の原理により近似的に最近傍点を探索する。この手法は、データが実数ベクトルであり、かつノードに登録されている代表ベクトルが二値ベクトルである場合を前提として設計される。データが二値ベクトルであって、ノードに登録されている代表ベクトルが実数ベクトルである場合にも、上記の実施の形態を採用することで、木探索を高速化できる。第1の実施の形態では、二値ベクトルpと複数の実数ベクトルqiの内積を一括して高速に計算できる特徴量演算装置を説明した。この特徴量演算装置を応用した物体認識装置によれば、複数種類の認識をまとめて行うことができた。具体的には、物体認識装置において、複数種類(クラス)の認識に対応する複数の辞書としての実数ベクトルq1,q2,q3,...,qLで識別を行う際に、このL個の実数ベクトルq1,q2,q3,...,qLと二値ベクトルpとの各々の内積を計算するにあたって、L個の実数ベクトルq1,q2,q3,...,qLをまとめた実数行列Qを二値の要素を持つ基底行列Mと実数の要素を持つ係数行列Cに分解して、CTMTpを計算し、これを閾値と比較することで、各クラスの識別を行った。0149このように、第1の実施の形態では、複数の実数ベクトルをまとめて分解することで、複数の実数ベクトルをそれぞれ基底行列と係数ベクトルに分解する場合と比較して、より少ない基底数で分解ができた。物体認識装置において、隣り合う辞書同士が似ている場合には、基底数kを小さくすることができ、原理的には1クラスあたり1個以下(k≦L)とすることも可能であった。0150しかしながら、第1の実施の形態の物体認識装置においても、クラス数Lが増加すると、基底数kを大きくしなければならず、基底数kが増加すれば分解する際に行われるコスト関数最小化に要する演算量は爆発的に増加し、実数ベクトルをまとめた実数行列の分解が困難になる。第1の実施の形態の物体認識装置では、内積計算に基づいて識別を行う場合に、各クラスについて、すべての計算をする前にネガティブの判定を下す早期棄却の手順を採用することができず、特徴ベクトルと基底との内積をすべて計算する必要がある。0151本実施の形態では、上記の点で、第1の実施の形態の物体認識装置に対して有利な物体認識装置を説明する。本実施の形態の物体認識装置30は、図12に示すように、ピラミッド画像生成部31と、HOG特徴量抽出部32と、バイナリコード変換部33と、パラメータ決定部34と、パラメータ行列分解部35と、線形SVM識別部36とを備えている。図120153コンテンツ取得部としてのピラミッド画像生成部31は、入力クエリとしての画像を取得して、当該画像を複数段階の倍率でそれぞれ縮小してなるG段のピラミッド画像を生成する。これにより、サイズの異なる物体に対処できる。特徴ベクトル抽出部としてのHOG特徴量抽出部32は、ピラミッド画像の各段における画像を、16×16ピクセルのサイズのブロックに分割し、各ブロックからHOG特徴量を抽出する。HOG特徴量抽出部32は、各ブロックからD次元の特徴量を抽出する。特徴ベクトル二値化部としてのバイナリコード変換部33は、各セルに与えられたD次元の特徴量を、d次元の二値ベクトルに変換する。0154実数行列取得部としてのパラメータ決定部34は、認識したい対象の種類(大人、子供、車、バイクといった種類であって、パラメータで定義される)ごとに、それぞれ線形SVM識別部36における線形SVMにて用いる重みベクトルwn(n=1,2,...,L)及び実数のバイアスbn(n=1,2,...,L)を決定する。パラメータ決定部34は、学習用に用意された特徴量を用いて、学習処理によってL種類の重みベクトルwn及びバイアスbnを決定して、重みベクトルwnをまとめた重み行列Wを生成する。0155実数行列分解部ないし実数分解装置としてのパラメータ行列分解部35は、離散値の基底行列と係数行列との積に分解する。図13は、パラメータ行列分解部35による複数の実数の重みベクトルの分解を説明する図である。以下の説明では、実数の重みベクトルをqと表記する。パラメータ行列分解部35は、図13に示すように、複数の実数ベクトルqnを並べてなる実数行列Qを複数の基底行列Mと係数行列Cとの積の和に分解する。以下、具体的な手順を説明する。図130156以下の説明において、第1の実施の形態で説明した分解手法で実数行列Qをk個の基底を持つ基底行列Mと係数行列Cとに分解する手順を下式(26)のように表記することとする。0157この分解は第1の実施の形態で説明した二値又は三値の分解手法により行うことができるが、上述のように基底数kが大きくなると分解が困難になる。そこで、本実施の形態では、以下のアルゴリズムで実数行列を逐次的に分解する。図14は、パラメータ行列分解部35が実行するアルゴリズムのフロー図である。パラメータ行列分解部35は、分解すべき実数行列Qを取得する(ステップS141)。次に、パラメータ行列分解部35は、インデクスi(i=1〜N、Nは2以上の自然数)を1とし、残差行列Rに実数行列Qを代入する(ステップS142)。残差行列Rは、逐次的な分解によってそれまでに分解された基底行列Mと係数行列Cとの内積の和と実数行列Qとの差である。図140158次に、パラメータ行列分解部35は、残差行列Rを第1の実施の形態の手法によって、基底行列Mと係数行列Cに分解する(ステップS143)。このとき、基底数はkiとする。基底数ki=k1、k2、・・・、kNは、あらかじめパラメータ行列分解部35に記憶されている。MiCiが得られると、パラメータ行列分解部35は、もとの残差行列RとMiCiとの差分を新たな残差行列Rとし(ステップS144)、インデクスiをインクリメントし(ステップS145)、インデクスiがNより大きいか、即ち、N段階の逐次的な分解が終了したかを判断する(ステップS146)。0159インデクスiがN以下である場合には(ステップS146にてNO)、パラメータ行列分解部35は、ステップS143に戻って、ステップS144で得られた新たな残差行列Rに対して、ステップS145でインクリメントされた新たなiで再度分解を行う。以上の処理を繰り返して、インデクスiがNより大きくなったら(ステップS146でYES)、処理を終了する。上記のように、N段の基底数k1、k2、・・・、kNは、あらかじめ用意されており、それらは同じ数であっても互いに異なる数であってもよい。基底数kは例えば8程度であればよい。0160ベクトル演算部としての線形SVM識別部36は、線形SVMによって特徴ベクトルの識別を行なう。線形SVM識別部36は、まず、sx×syブロックをひとまとまりとして、検出ウィンドウを構成する。1つの検出ウィンドウから抽出される特徴ベクトルxは、sx×sy×d次元のベクトルとなる。線形SVM識別部36は、図15に示す特徴ベクトルxと重みベクトルqnを並べた重み行列Qとの積が、ある閾値を超えるか否かによって識別をする。よって、この内積が閾値を超えるか否かがわかればよく、内積の値を求めること自体は必ずしも必要ない。重み行列Qは、パラメータ行列分解部35においてM1C1+M2C2+・・・+MNCNに分解されており、その分解アルゴリズムは、残差を徐々に小さくしていくものであるので、MiCiのインデクス(添え字)iが小さいほど、もとの重み行列Qに対する寄与度が大きくなっている。このことに着目すると、識別処理の早期棄却(カスケード化)が可能となる。図150161図16は、線形SVM識別部36におけるカスケード識別処理のフロー図である。線形SVM識別部36は、まず、インデクスiを1に初期化して、図17に示すように、入力された特徴ベクトルxとMiCi(=M1C1)との積を計算し、行数1、列数(クラス数)Lの次元をもつ行列yを得る(ステップS161)。このとき第1の実施の形態で説明したように、xとMiとのハミング距離を計算して、係数行列Cに関する重み付け和を計算し、定数項を足すことで、特徴ベクトルxとMiCi(=M1C1)との内積を計算する。図16図170162得られたyは、xTQをよく近似しているため、この近似行列yの要素が十分に小さければ、当該要素に対応するクラスについては、この時点でウィンドウ内の被写体が背景(negative)であると判別することができる。そこで、次に、線形SVM識別部36は、近似行列yのサイズと同じサイズの閾値行列tiをあらかじめ用意しておき、図18に示すように、得られた近似行列yの各要素とこの閾値行列tiの各要素とをそれぞれ比較して、閾値行列tiの要素よりも小さい近似行列yの要素(クラス)については、背景(negative:図17における「N」)であると判定する(ステップS162)。閾値行列tiは、positiveをnegativeと誤判定することの無いような十分小さい値にあらかじめ調整しておけばよい。背景であると判定された要素(クラス)については、この時点で識別を確定させる。図17図180163線形SVM識別部36は、未確定のクラス、即ち早期棄却できなかった要素(図18における「?」)が残っているか否かを判断する(ステップS163)。早期棄却できなかった要素(クラス)が残っている場合には(ステップS163にてYES)、線形SVM識別部36は、インデクスiをインクリメントし(ステップS164)、インデクスiがNより大きいかを確認する(ステップS165)。線形SVM識別部36は、インデクスiがN以下である場合は(ステップS165にてNO)、近似行列yに、次の段のxTMiCiを加えて、近似行列yを更新し(ステップS166)、ステップS162に戻って、近似行列yと閾値行列tiとを比較する。ここでもxTMiCiの計算は、第1の実施の形態と同様に行うことができる。図180164このようにして、近似行列yを更新するごとに閾値tiと比較することで、背景と確定できる要素(クラス)が徐々に増えていき、未確定のクラスがなくなった場合は(ステップS163にてNO)、すべてのクラスについて背景であると確定して(ステップS167)、処理を終了する。背景であると確定できないクラスが残されたままインデクスiがNより大きくなった場合には(ステップS165にてYES)、その未確定のクラスについて、定義された被写体に該当するという判定(positive判定)をして(ステップS168)、処理を終了する。0165以上のように、本実施の形態によれば、二値化された特徴ベクトルとの内積演算が行われる実数ベクトルを複数の二値又は三値の基底行列と係数行列との内積の和に分解するので、基底行列の基底数を小さく抑えることができ、クラス数が多い場合にも実数行列を容易に分解できる。実数ベクトルを二値又は三値の基底行列M係数行列との内積の線形和に分解するので、全体では、k1+k2+・・・+kN個の基底ベクトルが必要となるが、識別の際には、カスケード化による早期棄却が可能となり、かつ、多くの場合にはこれらの基底ベクトルをすべて計算することなく早期棄却されるため、識別処理を高速化できる。上記の実施の形態において、ステップS152にて近似行列yと閾値行列tiとの比較の結果、閾値行列tiの要素より小さいとしてnegative判定された近似行列yの要素については、その後の計算を省略してよい。具体的には、図18の例では、近似行列yと閾値行列t1とを比較した結果、クラス1、3、6、7についてnegative判定ができているので、図20に示すように、近似行列yを更新するためにxTM2C2を計算する際には、係数行列C2における未確定クラスのみについて計算し(図20では係数行列C2における確定したクラスをハッチングして示している)、もとの近似行列yの未確定のクラスのみ(図20では、もとの近似行列yにおける確定したクラスをハッチングして示している)をこれと足し合わせることで、未確定クラスのみが更新された新たな近似行列yを得る(図20では、新たな近似行列yにおける確定したクラスをハッチングして示している)。新たな近似行列yを対応する閾値行列t2と比較する際にも、図21に示すように、すでにnegative判定されている要素(図21において「N」で示している)については、比較を行わず、未確定クラスについてのみ比較を行うようにしてよい。図21の例では、新たにクラス2、5についてnegative判定がされている。このように、確定したクラスについての計算を省略することで、識別のための計算不可を軽減して、識別処理をより高速化できる。図18図20図210167また、上記の実施の形態では、小さい値の閾値行列tiを用意して、近似行列yの要素がこの閾値行列の要素より小さいときに、その要素についてnegative判定をすることで早期棄却を行ったが、これに代えて、又はこれに加えて、大きい値の閾値行列を用意して、近似行列yの要素がその閾値行列の値より大きいときに、その要素についてpositive判定をして、早期確定をしてもよい。0168また、上記の実施の形態では、実数行列Qを複数のMiCiの和に分解したことでカスケード化した識別が可能となり、物体認識装置30はカスケード化した識別を行ったが、分解のみ上記の手法で行い、識別処理はカスケード化しない通常の処理を行ってもよい。この場合にも、分解については、実数行列のクラス数が多い場合にも各基底行列の基底数を比較的小さく抑えることができるという効果を得ることができる。0169なお、上記で個別に説明した内容以外にも、第2の実施の形態において、第1の実施の形態で説明した技術を適宜に組み合わせてよい。第2の実施の形態においても、第1の実施の形態で説明したデータ依存分解及びデータ非依存分解のいずれも採用できる。上記の第2の実施の形態では、複数クラスの実数ベクトルからなる実数行列を全クラスについて共通の二値基底行列に分解するので、相関が低い多クラス識別に対しては有効ではない。そこで、本実施の形態では、相関が高い識別器のグルーピングを行うことで、より効率的な分解を行う。0171より具体的には、本実施の形態では、相関が高い識別器のみをグルーピングし、各グループに対して行列分解を適用させることで、少ない基底数での分解を行う。カスケード構造を構築する際の残差行列Rに対してグルーピングし直すことにより、各段で最適なグループを選択する。本実施の形態の物体認識装置の構成は、図12に示した第2の実施の形態の物体認識装置30と同じであり、ピラミッド画像生成部31と、HOG特徴量抽出部32と、バイナリコード変換部33と、パラメータ決定部34と、パラメータ行列分解部35と、線形SVM識別部36とを備えている。図120173図22は、本実施の形態のパラメータ行列分解部35が実行するアルゴリズムのフロー図である。パラメータ行列分解部35は、分解すべき実数行列Qを取得し(ステップS221)、インデクスi(i=1〜N、Nは2以上の自然数)を1として残差行列Rに実数行列Qを代入する(ステップS222)。パラメータ行列分解部35は、複数の重みベクトルqi(i=1〜N)に対して相関が高いものどうしを同じグループとしてまとめるグルーピングを行って(ステップS223)、残差行列Rを基底行列Mと係数行列Cに分解する(ステップS224)。図220174即ち、Q=MCの分解では、すべてのクラスに対して1つの二値基底行列Mを用いて分解しているので、重みベクトルq間の距離が近いほど、この分解が有効になる。実際に分解する実数行列Qにおいて、必ずしも各クラスにおけるベクトルの距離が近いとは限らない。分解前の重みベクトルqの距離が離れていても分解後に近くなることがある。そこで、パラメータ行列分解部35は、上述のように分解(ステップS224)の前に、まず分解対象のベクトルを相関別にグルーピングする(ステップS223)。0175パラメータ行列分解部35は、グルーピングのために、ベクトルqm(m=1,2,・・・,J)とベクトルqn(n=1,2,・・・,J)との間の距離を下式(27)、(28)によって正規化する。0176ここで、NDは、ベクトルqmとベクトルqnとの間の正規化された距離であり、−1〜1の実数である。ND=1であるときにベクトルqmとベクトルqnとが同じとなり、ND=−1であるときにベクトルqmとベクトルqnとは反対の向きのベクトルとなる。あるベクトルを同じグループとする。0177図23は、グルーピングを用いた行列分解を説明する図である。図23のスケール係数行列Cにおける塗りつぶされた要素は0を表しており、各要素のハッチングはそれぞれのグループを表している。図23に示すように、パラメータ行列分解部35は、各グループについて、基底数kでの分解を行う。図230178ステップS224の分解によってMiCiが得られると、パラメータ行列分解部35は、もとの残差行列RとMiCiとの差分を新たな残差行列Rとし(ステップS225)、インデクスiをインクリメントし(ステップS226)、インデクスiがNより大きいか、即ち、N段階の逐次的な分解が終了したかを判断する(ステップS227)。よってグルーピングをし直し、ステップS226でインクリメントされた新たなiで再度分解を行う。以上の処理を繰り返して、インデクスiがNより大きくなったら(ステップS227でYES)、処理を終了する。0180以上のように、本実施の形態の物体認識装置によれば、相関が高い重みベクトル(識別器)をグルーピングして、各グループに対してそれぞれ基底数kの行列分解を行うので、少ない基底で重み行列(実数行列)を二値の基底行列と係数行列の積に分解できる。本実施の形態の物体認識装置によれば、カスケード処理を行うにあたって、残差行列Rが生成されるごとに新たにグルーピングをし直すので、カスケード処理の各段において最適なグループを選択できる。100において、コンテンツ取得部101、特徴ベクトル生成部102、特徴ベクトル二値化部103、実数行列取得部104、実数行列分解部105、及びベクトル演算部106の一部と他の部分とが別々の装置として構成されていてもよい。コンテンツ取得部101、特徴ベクトル生成部102、特徴ベクトル二値化部103、及びベクトル演算部106が特徴演算装置100に搭載され、実数行列取得部104、及び実数行列分解部105が別の装置に搭載されてよい。この場合には、実数行列分解部105にて分解された複数の実数行列が特徴演算装置100のデータベース107に記憶され、ベクトル演算部106は、データベース107から分解された複数の実数行列を取得する。0182上記の実施の形態では、基底行列Mが二値又は三値であったが、基底行列Mが二値又は三値でなくともよい。基底行列Mのとり得る要素の種類が有限の数であれば上記の分解手法を適用して実数行列を分解することができる。係数行列Cも、基底行列Mと同様にあらかじめ定められた離散的な値でもよい。係数行列Cの要素を2のべき乗に制約してもよく、そうすることで、処理を高速化できる。́を基底行列Mと係数行列Cに分解すると、より少ない基底で式(2)や式(14)の近似分解を行うことができる。0183コンテンツ取得部101にて取得されるコンテンツデータは、車両から得られる計測データであってよい。車両から得られる計測データは、例えば、車両に設置されたカメラで撮影された画像データ、車両に設置されたセンサで計測されたセンシングデータであってよい。この場合に、関連性判定装置としての特徴演算装置100のベクトル演算部106は、計測データと辞書データとの関連性を判定する。計測データとして、車両に設置されたカメラで撮影された画像データが取得される場合には、辞書データとして複数の人物画像のデータがデータベースに保存されており、関連性判定装置としての特徴演算装置100のベクトル演算部106は、上記の応用例のいずれかによって、画像データの画像に人物が含まれるか否かを判定してよい。0184本発明は、実数行列を複数の基底行列と係数行列の積の和に分解するので、実数行列のクラス数が多い場合にも、各基底行列の基底数は比較的小さく抑えることができ、分解の処理負担を軽減できという効果を有し、複数の実数ベクトルと二値ベクトルに変換された特徴ベクトルとの内積の計算を含むベクトル演算によって特徴ベクトルと複数の実数ベクトルの各々との関連性の判定を行う関連性判定装置等として有用である。線形SVM識別部ページトップへこの技術を出願した法人この情報を共有FacebookTwitterGoogle+LinkedInこの技術を発明した人物この情報を共有FacebookTwitterGoogle+LinkedInページトップへ関連する挑戦したい社会課題この情報を共有FacebookTwitterGoogle+LinkedIn高い食料自給率を実現する高い食料自給率を実現すると、国内での食料の安定供給や、他国の問題による食料不足などの問題を防止する可能性が高まります。日本の食料自給率は非常に低く、食料面で海外に大きく依存しているのが現状です...最終更新日:2018/06/18癌(5大疾病)のない社会を実現する癌のない社会を実現すると、全世界の患者約1,750万人を助け、年間約760万人の亡くなる命を救うことができます。イノベーションを導く多くの企業が膨大な労力と費用をかけて新たな市場や事業を生み出そうとしている中「イノベーション」にかかわるデータのニーズはかつてないほどの高まりを見せいます。