(57)【要約】【課題】各種データの内容に対応させて高精度な分類を行う。【解決手段】入力データを予め設定された複数の異なる分類のうち何れか１つに分類分けするデータ分類装置において、前記入力データに関連する学習データを入力して復元抽出でランダムサンプルすることにより１又は複数のクラスに分類し、分類されたクラスに対して予め設定された数のデータ集合を生成するデータ集合生成手段と、前記データ集合を生成するデータ集合生成手段により得られる前記データ集合に対して決定木により学習し、前記複数の分類を設定する決定木学習手段と、前記入力データの入力に対して前記決定木学習手段により得られた学習結果を用いて、前記複数の異なる分類のうち何れか１つに分類分けするデータ分類手段とを有することにより、上記課題を解決する。【選択図】図３
2010044674.tif 000002
【特許請求の範囲】
【請求項１】
入力データを予め設定された複数の異なる分類のうち何れか１つに分類分けするデータ分類装置において、
前記入力データに関連する学習データを入力して復元抽出でランダムサンプルすることにより１又は複数のクラスに分類し、分類されたクラスに対して予め設定された数のデータ集合を生成するデータ集合生成手段と、
前記データ集合を生成するデータ集合生成手段により得られる前記データ集合に対して決定木により学習し、前記複数の分類を設定する決定木学習手段と、
前記入力データの入力に対して前記決定木学習手段により得られた学習結果を用いて、前記複数の異なる分類のうち何れか１つに分類分けするデータ分類手段とを有することを特徴とするデータ分類装置。
【請求項２】
前記データ集合生成手段は、
前記分類されたクラス対して等確率でランダムにデータを抽出し、データを抽出する数が予め設定された数を超えた場合に、抽出されたデータを用いてデータ集合を生成することを特徴とする請求項１に記載のデータ分類装置。
【請求項３】
前記データ集合生成手段は、
前記分類されたクラスの中から１つのクラスをランダムに選択し、選択したクラスに対してランダムにデータを抽出し、データを抽出する数が予め設定された数を超えた場合に、抽出されたデータを用いてデータ集合を生成することを特徴とする請求項２に記載のデータ分類装置。
【請求項４】
前記データ集合生成手段は、
前記分類されたクラスの中から１つのクラスをランダムに選択する処理を所定回数行うことを特徴とする請求項３に記載のデータ分類装置。
【請求項５】
前記データ集合生成手段は、
前記分類されたクラスの全てに対してランダムにデータを抽出し、データを抽出する数が予め設定された数を超えた場合に、抽出されたデータを用いてデータ集合を生成することを特徴とする請求項１に記載のデータ分類装置。
【請求項６】
入力データが映像である場合、入力される映像信号からショット境界を検出し、各ショットの中間位置にあるフレームをキーフレームとして抽出するキーフレーム抽出手段と、
前記キーフレーム抽出手段により抽出されたキーフレームを１又は複数のブロック領域に分割するデータブロック領域分類手段と、
前記データブロック領域分類手段により分割されたブロック領域毎に各領域に対して予め設定された各種画像特徴量を算出する特徴量抽出手段と、
前記特徴量抽出手段により得られるデータに基づいて被写体フレーム判定を行う被写体フレーム判定手段とを有することを特徴とする請求項１乃至５の何れか１項に記載のデータ分類装置。
【請求項７】
入力データを予め設定された複数の異なる分類のうち何れか１つに分類分けするデータ分類処理をコンピュータに実行させるためのデータ分類プログラムにおいて、
コンピュータを、
前記入力データに関連する学習データを入力して復元抽出でランダムサンプルすることにより１又は複数のクラスに分類し、分類されたクラスに対して予め設定された数のデータ集合を生成するデータ集合生成手段、
前記データ集合を生成するデータ集合生成手段により得られる前記データ集合に対して決定木により学習し、前記複数の分類を設定する決定木学習手段、及び、
前記入力データの入力に対して前記決定木学習手段により得られた学習結果を用いて、前記複数の異なる分類のうち何れか１つに分類分けするデータ分類手段として機能させるためのデータ分類プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分類装置及びデータ分類プログラムに係り、特に各種データの内容に対応させて高精度な分類を行うためのデータ分類装置及びデータ分類プログラムに関する。
【背景技術】
【０００２】
従来、大量の映像や音楽等のコンテンツを効率的に検索するためには、意味内容に基づいた有効なインデクスが必要不可欠である。例えば、番組のような映像に対する索引付けにおいて、どの区間にどのような被写体が映っているかということは、最も重要な情報の１つである。
【０００３】
ここで、大量の映像から所望の番組を効率的に探索するための有効な技術の１つとして映像の要約がある。従来では、電子番組表（ＥＰＧ）に記載される番組紹介テキストとクローズドキャプション（ＣＣ）との対応付けによりフレーム等のデータの内容を分類し、その分類した情報から自動に要約部分を抽出する手法が提案されている（例えば、特許文献１参照。）。
【特許文献１】特許２００８−１４１６２１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述した手法に用いられるデータ分類手法は、テキスト処理に基づいた手法であり、上述したＥＰＧやＣＣが存在しない番組には適用できないという問題があった。また、映像中にナレーションが存在しないシーン等、テキストの解析のみでは判別できない重要シーンを検出できず、データの内容によっては高精度な分類ができないという問題があった。
【０００５】
本発明は、上述した問題点に鑑みなされたものであり、各種データの内容に対応させて高精度な分類を行うためのデータ分類装置及びデータ分類プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本件発明は、以下の特徴を有する課題を解決するための手段を採用している。
【０００７】
請求項１に記載された発明は、入力データを予め設定された複数の異なる分類のうち何れか１つに分類分けするデータ分類装置において、前記入力データに関連する学習データを入力して復元抽出でランダムサンプルすることにより１又は複数のクラスに分類し、分類されたクラスに対して予め設定された数のデータ集合を生成するデータ集合生成手段と、前記データ集合を生成するデータ集合生成手段により得られる前記データ集合に対して決定木により学習し、前記複数の分類を設定する決定木学習手段と、前記入力データの入力に対して前記決定木学習手段により得られた学習結果を用いて、前記複数の異なる分類のうち何れか１つに分類分けするデータ分類手段とを有することを特徴とする。
【０００８】
請求項１記載の発明によれば、各種データの内容に対応させて高精度な分類を行うことができる。
【０００９】
請求項２に記載された発明は、前記データ集合生成手段は、前記分類されたクラス対して等確率でランダムにデータを抽出し、データを抽出する数が予め設定された数を超えた場合に、抽出されたデータを用いてデータ集合を生成することを特徴とする。
【００１０】
請求項２記載の発明によれば、分類されたクラスに対して等確率で学習結果を抽出できるため、各種データの内容に対応させて高精度な分類を行うことができる。
【００１１】
請求項３に記載された発明は、前記データ集合生成手段は、前記分類されたクラスの中から１つのクラスをランダムに選択し、選択したクラスに対してランダムにデータを抽出し、データを抽出する数が予め設定された数を超えた場合に、抽出されたデータを用いてデータ集合を生成することを特徴とする。
【００１２】
請求項３記載の発明によれば、分類されたクラスに対して等確率で学習結果を抽出できるため、各種データの内容に対応させて高精度な分類を行うことができる。
【００１３】
請求項４に記載された発明は、前記データ集合生成手段は、前記分類されたクラスの中から１つのクラスをランダムに選択する処理を所定回数行うことを特徴とする。
【００１４】
請求項４記載の発明によれば、例えば３つのクラスが存在する場合に、そのうちの２つのクラスのみが選択される場合もあるため、より汎用的なブートストラップを生成することができる。
【００１５】
請求項５に記載された発明は、前記データ集合生成手段は、前記分類されたクラスの全てに対してランダムにデータを抽出し、データを抽出する数が予め設定された数を超えた場合に、抽出されたデータを用いてデータ集合を生成することを特徴とする。
【００１６】
請求項５記載の発明によれば、分類された全クラスに対して同一回数の学習結果を抽出できるため、各種データの内容に対応させて高精度な分類を行うことができる。
【００１７】
請求項６に記載された発明は、入力データが映像である場合、入力される映像信号からショット境界を検出し、各ショットの中間位置にあるフレームをキーフレームとして抽出するキーフレーム抽出手段と、前記キーフレーム抽出手段により抽出されたキーフレームを１又は複数のブロック領域に分割するデータブロック領域分類手段と、前記データブロック領域分類手段により分割されたブロック領域毎に各領域に対して予め設定された各種画像特徴量を算出する特徴量抽出手段と、前記特徴量抽出手段により得られるデータに基づいて被写体フレーム判定を行う被写体フレーム判定手段とを有することを特徴とする。
【００１８】
請求項６記載の発明によれば、映像情報に合ったデータの分類を高精度に行うことができる。
【００１９】
請求項７に記載された発明は、入力データを予め設定された複数の異なる分類のうち何れか１つに分類分けするデータ分類処理をコンピュータに実行させるためのデータ分類プログラムにおいて、コンピュータを、前記入力データに関連する学習データを入力して復元抽出でランダムサンプルすることにより１又は複数のクラスに分類し、分類されたクラスに対して予め設定された数のデータ集合を生成するデータ集合生成手段、前記データ集合を生成するデータ集合生成手段により得られる前記データ集合に対して決定木により学習し、前記複数の分類を設定する決定木学習手段、及び、前記入力データの入力に対して前記決定木学習手段により得られた学習結果を用いて、前記複数の異なる分類のうち何れか１つに分類分けするデータ分類手段として機能させる。
【００２０】
請求項７記載の発明によれば、データの内容に基づいてクラス分けして等確率で学習結果を抽出できるため、各種データの内容に対応させて高精度な分類を行うことができる。また、プログラムをインストールすることにより、容易にデータ分類処理を実現することができる。
【発明の効果】
【００２１】
本発明によれば、各種データの内容に対応させて高精度な分類を行うことができる。
【発明を実施するための最良の形態】
【００２２】
＜本発明の概要＞
本発明は、映像や音楽、テキスト情報等の各種データに対して分類分けを行う。具体的には、例えば、映像解析による重要シーンの抽出を目的とした場合、被写体が出現する映像区間とフレーム内での被写体領域の検出を行う際には様々な被写体を検出するために、被写体とそれ以外の背景を区別するための画像特徴量と、その特徴量に基づいた有効な識別手法の検討が必要となる。そこで、本発明では、例えば、各キーフレームにおけるブロック領域に対して様々なテクスチャ特徴を取得し、その情報からランダムフォレスト法によって被写体とそれ以外の背景領域とに分類する。
【００２３】
＜ランダムフォレスト法について＞
ここで、本実施形態で適用されるランダムフォレスト法について説明する。ランダムフォレスト学習アルゴリズムは、集団学習の一種であり、多数の決定木を組み合わせることによって高い分類精度を実現する手法である（ランダムフォレスト学習アルゴリズムについては、例えば非特許文献１（Ｌ．Ｂｒｅｉｍａｎ，“Ｒａｎｄｏｍ  Ｆｏｒｅｓｔｓ，”Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ，ｖｏｌ．４５，ｐｐ．５−３２，２００１．）等参照。）。
【００２４】
また、ランダムフォレスト法は、バギングやブースティング、サポートベクターマシーン等の分類アルゴリズムと比較しても、非常に高い精度を得ることができるとされており、多クラスの分類に使用することができる。ここで、ランダムフォレストのアルゴリズムについて説明する。
（１）まず、学習データの中から、生成する決定木の数だけのデータ集合であるブートストラップサンプルを生成する。ここで、ブートストラップサンプルとは、学習データから復元抽出でランダムサンプルすることによって生成したデータ集合を示す。
（２）次に、生成したブートストラップサンプルを用いて決定木を学習する。決定木としては、ＣＡＲＴ（例えば、非特許文献２（Ｌ．Ｂｒｅｉｍａｎ，Ｊ．Ｈ．Ｆｒｉｅｄｍａｎ，Ｒ．Ａ．Ｏｌｓｈｅｎ  ａｎｄ  Ｃ．Ｊ．Ｓｔｏｎｅ，“Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ａｎｄ  Ｒｅｇｒｅｓｓｉｏｎ  Ｔｒｅｅｓ，”Ｗａｄｓｗｏｒｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｇｒｏｕｐ，Ｂｅｌｍｏｎｔ，１９８４．）等参照。）を用いる。
【００２５】
また、決定木の各ノードの分岐の方法については、例えば、Ｍ個の全特徴の中からｍ個（ｍ＜Ｍ）をランダムに選択し、その中から最良の分岐を選択する。また、分岐の良否の判定には、Ｇｉｎｉ係数又は情報利得を利用する。なお、木は最大まで成長させ、枝刈りは行わない。
（３）識別器の出力結果は、全ての決定木の出力の多数決によって決定する。ランダムフォレスト法では、学習データにおいて各クラスに属するデータが均等である場合は、良好な識別器を学習することができる。しかしながら、一部のクラスに含まれるデータ数が極端に多い等、データ数に偏りがある場合には、殆ど全ての入力データを、学習データの多数を占めるクラスとして分類するような識別器が学習されてしまう。例えば、表１に示すような偏りのある学習データに対して、全てをクラスＢと分類しても８０％のデータは正しく分類できることになる。そこで、上述した非特許文献１に示すような技術では、各学習データに対して、各クラスに含まれるデータ数に反比例した重みを設定することによって、問題の解決を図っている。
【００２６】
ここで、表１に重み付けの例を示す。
【００２７】
【表１】
2010044674.tif 000003
上述の表１に示すように、データ数の少ないクラスＡに属するデータには大きな重み（例えば、クラスＢの重みが０．２に対して０．８等）を与えている。この重みを考慮して、ノードの分岐におけるＧｉｎｉ係数又は情報利得を算出することによって、データ数の多いクラスに偏った分岐が選択されることがないようにする。
【００２８】
ここで、上述の手法を用いた場合には、以下に示す２点の問題点が存在する。まず１つは、データの偏りを重みによって補正するため、少数クラスにおけるデータの多様性が損なわれ、汎化能力の低い、つまり検出再現率の低い識別器が学習されてしまうという点である。重みによる補正は、少数クラスのデータについて、全く同一のデータを幾つも含めているのと同じ意味となっており、使用される特徴量にも偏りが起きてしまう恐れがある。
【００２９】
ここで、図１は、検出再現率の低くなる例を模式的に表した図である。例えば、図１に示すようなクラスＡとクラスＢの２つのクラスのデータ分布があった場合、予測されるクラスの境界は、図１（ａ）の点線のようになる。それに対して、上述した表１に示した重み付けによってブートストラップサンプルを生成した場合は、図１（ｂ）に示すようになる。つまり、元の分布と比較して点線で表される境界が変形し、領域が狭くなっている（汎化性が低下している）ことが分かる。
【００３０】
また、もう１つの問題は、ブートストラップサンプルを生成する際に、少数クラスに属するデータが確実に選択されることが保証されていない点が挙げられる。特に、データ数の偏りが大きい場合には、データ数の少ないクラスに属する学習データが殆ど選択されない可能性もある。
【００３１】
そこで、本発明では、ブートストラップサンプルを生成する際に、各クラスから等確率でデータが選択されるようにすることにより、上述の問題を解決する。つまり、各データに対する重み付けは実施しないようにする。
【００３２】
次に、本発明におけるデータ分類装置及びデータ分類プログラムを好適に実施した形態について、図面を用いて説明する。
【００３３】
＜データ分類装置１０：ハードウェア構成＞
まず、本実施形態におけるデータ分類装置１０における装置構成例について説明する。データ分類装置１０は、例えば、汎用のパーソナルコンピュータ、サーバ等を用いることができ、本発明に係る各処理をコンピュータに実行させることができる実行プログラム（データ分類プログラム）をインストールすることにより、本発明におけるデータ分類処理を実現することができる。
【００３４】
図２は、本発明におけるデータ分類が実現可能な装置構成の一例を示す図である。なお、図２は、データ分類装置１０の各構成のそれぞれに適用される。図２は、入力装置１１と、出力装置１２と、ドライブ装置１３と、補助記憶装置１４と、メモリ装置１５と、各種制御を行うＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１６と、ネットワーク接続装置１７とを有するよう構成されており、これらはシステムバスＢで相互に接続されている。
【００３５】
入力装置１１は、ユーザが操作するキーボード及びマウス等のポインティングデバイスを有しており、ユーザからのプログラムの実行等、本実施形態におけるデータ分類処理を実行するための各種操作信号を入力する。
【００３６】
出力装置１２は、本発明における処理を行うためのコンピュータ本体を操作するのに必要な各種ウィンドウやデータ等を表示するディスプレイを有し、ＣＰＵ１６が有する制御プログラムによりプログラムの実行経過や結果等を表示することができる。また、出力装置１２は、プリンタ等の機能を有していてもよく、その場合には、学習結果や分類結果等の取得可能な各種情報を紙等の印刷媒体に印刷して、ユーザ等に提供することもできる。
【００３７】
ここで、本発明において、コンピュータ本体にインストールされる実行プログラムは、例えばＣＤ−ＲＯＭ等の記録媒体１８等により提供される。プログラムを記録した記録媒体１８は、ドライブ装置１３にセット可能であり、記録媒体１８に含まれる実行プログラムが、記録媒体１８からドライブ装置１３を介して補助記憶装置１４にインストールされる。なお、記録媒体１８としては、ＣＤ−ＲＯＭ以外でも、例えばフレキシブルディスク、光磁気ディスク等のように情報を光学的、電気的或いは磁気的に記録する記録媒体、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ等のように情報を電気的に記録する半導体メモリ等、様々なタイプの記録媒体を用いることができる。
【００３８】
また、補助記憶装置１４は、ハードディスク等のストレージ手段であり、本発明における実行プログラムや、コンピュータに設けられた制御プログラム、学習データ、分類結果等を蓄積し必要に応じて入出力を行うことができる。
【００３９】
メモリ装置１５は、ＣＰＵ１６により補助記憶装置１４から読み出された実行プログラム等を格納する。なお、メモリ装置１５は、ＲＯＭやＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等からなる。
【００４０】
ＣＰＵ１６は、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）等の制御プログラム、及びメモリ装置１５により読み出され格納されている実行プログラムに基づいて、各種演算や各ハードウェア構成部とのデータの入出力等、コンピュータ全体の処理を制御して、データ分類等における後述する各処理を実現することができる。なお、ＣＰＵ１６は、プログラムの実行中に必要な制御パラメータや入力される設定情報等の各種情報等を、補助記憶装置１４から取得することができ、またプログラムにより実行された結果や上述の各種情報等を補助記憶装置１４に蓄積することができる。
【００４１】
ネットワーク接続装置１７は、通信ネットワーク等と接続することにより、実行プログラムを通信ネットワークに接続されている他の端末等から取得したり、プログラムを実行することで得られた実行結果又は本発明における実行プログラム自体を他の端末等に提供することができる。また、ネットワーク接続装置１７によりデータ分類装置１０等の外部装置から学習データ等を取得することができる。
【００４２】
上述したような装置構成により、本発明におけるデータ分類処理を実行することができる。また、プログラムをインストールすることにより、汎用のパーソナルコンピュータ等で本発明におけるデータ分類処理を容易に実現することができる。
【００４３】
＜データ分類装置１０：機能構成例＞
次に、図３は、本実施形態におけるデータ分類装置の機能構成の一例を示す図である。図３に示すデータ分類装置１０は、データ集合生成手段としてのブートストラップサンプル生成手段２１と、決定木学習手段２２と、データ分類手段２３とを有するよう構成されている。
【００４４】
ブートストラップサンプル生成手段２１は、予め用意された学習データを入力し、その学習データから復元抽出でランダムサンプルすることによって生成したデータ集合を生成する。なお、学習データは、後述するデータ分類手段２３で分分類対象となる入力データに関連した学習データを用いるのが好ましいが、様々な入力データに対応できるように、一般的な広い分野での辞書的な学習が可能なデータであってもよい。
【００４５】
次に、決定木学習手段２２は、ブートストラップサンプル生成手段２１により生成されたデータ集合に基づいて決定木を学習する。具体的には、例えば元となる集合を属性情報等に基づいて部分集合に分割し、全ての部分集合に対して再帰的に繰り返される。この繰り返しは、分割が実行不可能となった場合、又は、部分集合の個々の要素が各々1つずつの分類となってしまう段階で終了することで、決定木を学習する。なお、決定木としては、例えば、上述したＣＡＲＴ等の従来手法を用いることができ、本発明においては特に限定されるものではない。また、決定木学習手段２２は、学習したデータを学習結果データベース２４に蓄積しておく。なお、ここまでの処理は、データ分類処理を実際に行う前段階として行うことができる。
【００４６】
次に、データ分類装置１０に入力されるデータに対して学習結果データベース２４を参照し、該当する分類条件に基づいて、分類結果を出力する。
【００４７】
＜ブートストラップサンプル生成手段２１：生成処理＞
次に、データ集合生成手段としてのブートストラップサンプル生成手段２１における生成処理について具体的に説明する。上述したデータ分類装置１０では、まず学習データからブートストラップサンプルを生成する。
【００４８】
ここで、図４は、ブートストラップサンプル生成処理手順の一例を示すフローチャートである。以下の説明では、学習データの集合Ｔを、以下に示す式（１）で表し、ｊ番目のクラスに属するデータの学習データの集合Ｃｊを式（２）で表す。
【００４９】
【数１】
2010044674.tif 000004
ここで、Ｄは学習データの総数を表し、Ｃは学習データに含まれるクラス数を表す。また、上述した式（２）における「ｃｌａｓｓ＿ｎｏ（ｄｉ）」は、データｄｉが属するクラス番号を表している。
【００５０】
まず始めに、入力される全ての学習データを走査して異なる分類からなるクラス数Ｃを求める（Ｓ０１）。ここで、クラスとは、例えば映像であれば、対象となる被写体（特定人物、動物、建造物等）を含むものと含まないもの等を意味し、また音声であれば、特定人物の声とＢＧＭ等の音楽等を意味する。なお、これらのクラスは、入力される学習データに対して従来の画像解析手法や音声解析手法等を用いて得られる特徴毎にクラス数が設定される。また、予め学習データの内容がわかっている場合には、ユーザがデータの内容に応じて任意にクラス数を設定してもよい。
【００５１】
次に、Ｓ０１の処理により得られたＣ個のクラスの中からランダムに１つを選択する（Ｓ０２）。ここで、何れのクラスも等確率で選択されるものとする。なお、ランダムに選択する場合には、例えば３つのクラスが存在する場合に、そのうちの２つのクラスのみが選択される場合もあるため、より汎用的なブートストラップを生成することができる。
【００５２】
次に、選択されたクラスに属するデータの中からランダムにデータを１つ選択する（Ｓ０３）。なお、Ｓ０３の処理において、選択されたデータは、選択データ３１として、蓄積手段等に蓄積される。
【００５３】
ここで、ブートストラップサンプルのデータ数が予め設定された任意の数Ｎを超えているか否かを判断する（Ｓ０４）、ここで、任意の数Ｎを超えていない場合（Ｓ０４において、ＮＯ）、Ｓ０２に戻りＳ０４の条件を満たすまで、後述の処理を繰り返し行う。また、Ｓ０４の処理において、任意の数Ｎを超えている場合（Ｓ０４において、ＹＥＳ）、ブートストラップサンプルを生成する（Ｓ０５）。また、Ｓ０５の処理で生成されたブートストラップサンプル３２は、蓄積手段等に蓄積される。
【００５４】
なお、Ｓ０５の処理では、以下に示す式（３）の処理をＮ回繰り返すことによって、１つのブートストラップサンプル３２を生成する。
【００５５】
【数２】
2010044674.tif 000005
なお、上述した式（３）は、ｋ番目のブートストラップサンプルを示している。
【００５６】
ここで、上述した式（３）において、「ｒａｎｄ（Ｃ）」は“０”から“Ｃ−１”までの数字を等確率でランダムに返す関数を表している。つまり、これを生成する決定木の本数Ｔだけ繰り返し、Ｔ個のブートストラップサンプルを生成する。
【００５７】
つまり、生成されたブートストラップサンプルが予め設定された任意の数Ｔを超えているか否かを判断し（Ｓ０６）、任意の数Ｔを超えていない場合（Ｓ０６において、ＮＯ）、Ｓ０２に戻り、任意の数Ｔを超えるまで繰り返し処理を行う。また、Ｓ０６の処理において、任意の数Ｔを超える場合（Ｓ０６において、ＹＥＳ）、処理を終了する。
【００５８】
このようにして生成したブートストラップサンプルを用いて、上述した決定木学習手段２２により決定木の学習を行う。したがって、入力データは、学習された全ての決定木の出力の多数決によって、クラスタリングされる。
【００５９】
ここで、上述の処理では、Ｓ０２の処理において、Ｎ回分データが選択されるまでランダムにクラスを選択していたが、本発明においてはこれに限定されるものではなく、例えば分類されたクラスの全てに対してランダムにデータを抽出し、データを抽出する数が予め設定された数を超えた場合に、Ｓ０５の処理に示すように抽出されたデータを用いてブートストラップサンプルを生成してもよい。これにより、分類された全クラスに対して同一回数の学習結果を抽出できるため、各種データの内容に対応させて高精度な分類を行うことができる。
【００６０】
上述したように、本実施形態におけるデータ分類装置１０では、各データに対して重み付けをしないため、各クラスに属するデータの総数を事前に求める必要がなく、クラスの種類数のみ判別すればよいため、学習データの解析に要する計算時間を軽減することができる。また、データの重み情報を保持しておくためのメモリも削減することができる。
【００６１】
＜データ分類装置１０の具体的な実施形態＞
次に、上述したデータ分類装置を用いた具体的な実施形態について図を用いて説明する。なお、以下の説明では、実際の放送番組として動物番組を対象に、映像中に出現する動物被写体を画像処理によって検出する処理について説明する。つまり、本実施形態では、各キーフレームにおけるブロック領域に対して様々なテクスチャ特徴を算出し、ランダムフォレスト法によって被写体とそれ以外の背景領域とに分類する処理内容について説明する。また、放送番組に対して上述した本発明手法を適用し、被写体領域及び被写体出現フレームの検出精度を評価する。
【００６２】
図５は、本実施形態におけるデータ分類システムの機能構成の一例を示す図である。図５に示すデータ分類システム４０は、キーフレーム抽出手段４１と、ブロック領域分割手段４２と、特徴量抽出手段４３と、データ分類装置１０と、被写体フレーム判定手段４４とを有するよう構成されている。
【００６３】
図５において、キーフレーム抽出手段４１は、入力される放送番組の映像信号の前後のフレームの画素情報の差分値の大きさ等からショット境界を検出し、各ショットの中間位置にあるフレームをキーフレームとして抽出する。
【００６４】
データブロック領域分類手段４２は、キーフレーム抽出手段４１により抽出されたキーフレームを予め設定される画素数等により１又は複数のブロック領域に分割する。つまり、データブロック領域分類手段４２において、１つのブロック領域に分割するとは、１フレームをそのまま分割せずに用いることを意味する。
【００６５】
特徴量抽出手段４３は、データブロック領域分類手段４２により分割されたブロック領域毎に各領域に対して予め設定された各種画像特徴量を算出する。なお、特徴量抽出手段４３は、具体的な画像特徴量であるテクスチャ特徴として、例えばカラーモーメント特徴、エッジ方向ヒストグラム、ガボール特徴、ローカルバイナリパターン、ブロック位置等がある。なお、各種画像特徴量の具体的な算出手法については後述する。
【００６６】
また、図５におけるデータ分類装置１０は、ランダムフォレスト識別器として上述した処理を行う。具体的には、データ分類装置１０は、特徴量抽出手段４３により算出された特徴量を含むブロック領域の画像情報を入力し、各領域が被写体領域であるかどうかを判定する。
【００６７】
また、被写体フレーム判定手段４４は、データ分類装置１０において得られるブロック領域の分類結果を統合し、映像を構成するフレームに被写体が映っているかを判定する。
【００６８】
なお、上述したデータ分類システム４０に示す各構成は、データ分類装置１０内に設けてもよい。上述した構成により、映像情報に関するデータの分類を高精度に行うことができる。
【００６９】
なお、上述したデータ分類システム４０は、映像に限らず例えば音声からある特定人物の音声とＢＧＭとを分類することもできる。その場合には、例えば音声データを無声部と有声部とで分割し、有声部から特徴量抽出手段４３によりＭＦＣＣ（Ｍｅｌ−Ｆｒｅｑｕｅｎｃｙ  Ｃｅｐｓｔｒｕｍ  Ｃｏｅｆｆｉｃｉｅｎｔｓ）等のような声道の形状を数値化した特徴量や、韻律（ピッチ、抑揚等）等の特徴量、またそれらの特徴量の平均値や分散等の統計的情報からなる音響特徴量を抽出し、抽出した音響特徴量に対応させてデータ分類を判定手段等により行うことができる。
【００７０】
＜各種画像特徴量の具体的な算出手法＞
次に、上述した図５に示す特徴量抽出手段４３における各種画像特徴量の具体的な算出手法について、具体的に説明する。
＜テクスチャ特徴＞
特徴量抽出手段４３により求められるテクスチャ特徴としては、例えば上述したカラーモーメント特徴，エッジ方向ヒストグラム，ガボール（Ｇａｂｏｒ）特徴，ローカルバイナリパターン（ＬＢＰ：Ｌｏｃａｌ  Ｂｉｎａｒｙ  Ｐａｔｔｅｒｎ）の４種類を用い、更に本実施形態では元のフレームにおけるブロック位置も特徴量として利用している。以下に、それぞれのテクスチャ特徴について簡単に説明する。
【００７１】
＜１．カラーモーメント特徴＞
カラーモーメント特徴では、入力画像をＨＳＶ色空間，Ｌａｂ色空間のそれぞれに変換し、各コンポーネントに対して，画素値の平均μ，標準偏差σ，歪度の立方根ｓを算出する。
【００７２】
＜２．エッジ方向ヒストグラム＞
エッジ方向ヒストグラムでは、−９０度から＋９０度の範囲を５度毎に区切った３６方向と、非エッジ点について頻度ヒストグラムを求め、特徴量とする。また、検出には、例えば画像の持つ２次元的な特徴を対象物体の輪郭（エッジ）として抽出し認識する手法であるＳｏｂｅｌフィルタ等を用いる。
【００７３】
＜３．ガボール特徴＞
ガボール特徴におけるガボールフィルタは、濃淡特徴の方向と周期を特徴量として抽出できるフィルタである。解像度ｍ，方向ｎのガボールフィルタを式（４）に示す。
【００７４】
【数３】
2010044674.tif 000006
ここで、上述した式（４）において、ｋｍ＝ａｍ（０≦ｍ≦Ｓ−１），θｎ＝ｎπ／Ｋ（０≦ｎ≦Ｋ−１）である。また、本実施形態では、一例としてσ＝２．５、ａ＝√２、Ｓ＝４、Ｋ＝６とする。上述した式（４）のフィルタを入力画像に畳み込み、その結果における平均と標準偏差を特徴量として利用する。
【００７５】
＜４．ローカルバイナリパターン（ＬＢＰ）＞
ローカルバイナリパターンは、注目画素に対する周辺画素の濃度の大小パターンを表した特徴量である（ＬＢＰについては、例えば、Ｔ．Ｏｊａｌａ  Ｍ．Ｐｉｅｔｉｋａｎｉｎｅｎ  ａｎｄ  Ｔ．Ｍａｅｎｐａａ，“Ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ  ｇｒａｙｓｃａｌｅ  ａｎｄ  ｒｏｔａｔｉｏｎ  ｉｎｖａｒｉａｎｔ  ｔｅｘｔｕｒｅ  ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ｗｉｔｈ  ｌｏｃａｌ  ｂｉｎａｒｙ  ｐａｔｔｅｒｎｓ，”ＩＥＥＥ  Ｔｒａｎｓ．Ｐａｔｔｅｒｎ  ａｎａｌｙｓｉｓ  ａｎｄ  ｍａｃｈｉｎｅ  ｉｎｔｅｌｌｉｇｅｎｃｅ，ｖｏｌ．２４，ｎｏ．７，ｐｐ．９７１−９８７，２００２．等参照。）。ここで、例えば、半径Ｒの位置にあるＰ個の画素のＬＢＰは式（５）で算出できる。
【００７６】
【数４】
2010044674.tif 000007
ここで、ｇｃは注目画素の画素値を表し、ｇｐは座標（Ｒｓｉｎ（２πｐ／Ｐ），Ｒｃｏｓ（２πｐ／Ｐ））の画素値を表す。また、Ｕは０と１が変化する箇所の数を表し、以下に示す式（６）で算出される。
【００７７】
【数５】
2010044674.tif 000008
ここで、解像度変化に耐性を持たせるため、本実施形態では、（Ｐ，Ｒ）＝（８，１），（１６，２），（２４，３）の三種類の組み合わせを使用する。また、上述の処理により、各ＬＢＰの頻度ヒストグラムを求め特徴量とする。
【００７８】
＜５．ブロック位置＞
ブロック位置では、入力データとして入力される映像中に含まれるフレーム内でのブロック位置をｘ，ｙ座標で表す。
【００７９】
＜被写体フレーム判定手段４４におけるフレーム判定手法＞
次に、上述した被写体フレーム判定手段４４におけるフレーム判定手法について、説明する。
【００８０】
ランダムフォレスト法によって被写体領域と判定されたブロック領域について、ブロック位置等により近接する被写体領域を再帰的に統合していく。最終的に、フレーム内に閾値以上の面積を持つ領域が存在すれば、被写体フレームと判定する。
【００８１】
＜評価実験＞
次に、上述した図５に示す実施形態を適用して実際に放送の動物番組に対して動物被写体の抽出を試みた。なお、実験には、番組名“ふしぎ大自然「大絶壁をヒヒが登る」”を利用した。なお、番組長は４３分である。
【００８２】
ここで、図６は、識別に用いられる画像の例を示す図である。なお、図６（ａ）は、検出された被写体のフレームの例を示し、図６（ｂ）は、誤検出の例を示す図である。
【００８３】
つまり、今回の実験では、図６に示すような“ヒヒ”を検出対象の被写体に設定した。番組映像に含まれるキーフレームの総数は２３９フレームであり、そのうち番組前半の１２０フレームを学習データとして使用し、残りの１１９フレームを検出精度の評価に使用した。ここで、学習データについては、キーフレームの各ブロック領域に対して人手で正解を付与した。なお、キーフレームの解像度は７２０×４８０画素であり、各フレームを６４×６４画素のブロック領域に分割した（合計７７ブロック）。また、ランダムフォレスト法における木の総数は、５００本に設定した。評価には以下に示す式で表される再現率及び適合率を用いた。
再現率＝Ｎｂ／Ｎｇ，適合率＝Ｎｂ／Ｎｏ
なお、Ｎｇは正解数、Ｎｏは提案手法による検出数、Ｎｂは正解のうち本発明手法でも検出できた数を表す。
【００８４】
ここで、図７は、本実施形態を適用した検出精度の一例を示す図である。なお、図７（ａ）はブロック領域単位での検出精度を示し、図７（ｂ）はフレーム単位での検出精度を示している。また、図７に示す括弧内の数値は、上述の再現率、適合率を抽出するためのブロック数（図７（ａ））、又はフレーム数（図７（ｂ））を示している。
【００８５】
図７（ａ）に示すブロック領域単位での検出結果において、被写体以外については、再現率，適合率とも９０％以上の非常に高い結果となった。また、図７（ｂ）に示すフレーム単位での評価結果において、実験では、被写体が一定の大きさ以上に映されているフレームを正解とした。実験の結果、被写体検出の再現率が９７％，適合率が８５％と，ブロック単位の結果と比較して精度が向上した。また、被写体の出現フレームでは、ブロック単位で未検出があっても、その他の領域が正しく検出されていれば未検出とならなかったため再現率が向上したと考えられる。また、誤検出される被写体領域は、フレーム内に散らばって存在し、大きな領域を形成することが少なかったため、フレーム単位での誤検出が軽減された。
【００８６】
本実施形態では、テクスチャ特徴に基づいた画像解析による動物被写体の検出手法を示したが、本発明の適用範囲はこれに限定されるものではなく、例えば画像や音声の分類等にも適用することができる。また、上述の実験結果から、例えば本実施形態におけるデータ分類手段２３において、入力されるデータをブロック単位で分類するか、又はフレーム単位で分類するかを分類対象となる被写体の内容等に応じて、組み合わせて処理することもできる。
【００８７】
また、上述した本実施形態においては、映像信号のフレームを予め設定された被写体が存在するフレームと、存在しないフレームの２種類に分類する例を示したが、本発明においてはこれに限定されるものではなく、本発明を適用して３種類以上の分類分けも可能である。
【００８８】
以上に説明したように本発明によれば、各種データの内容に対応させて高精度な分類を行うことができる。具体的には、学習過程における学習データのランダムサンプルの際に、各クラスからデータを等確率で選択することによって、識別性能のよい識別器を生成し、データを精度よく分類することができる。
【００８９】
なお、ランダムフォレスト法は、アンサンブル学習の一種であり、多数の決定木を組み合わせることによって高い分類精度を実現する手法であるが、本発明を適用して例えば、バギングやブースティング等の分類手法を使用することもできる。
【００９０】
また、本発明によれば、学習データ数に偏りがある場合に汎化性能が低下するという従来手法の問題を、ブートストラップサンプルの生成時におけるデータのサンプリングにおいて、各クラスから等確率でデータが選択されるようにすることで解決を図ることができる。つまり、本発明によれば、ランダムフォレストアルゴリズムを利用して画像や音声等のデータをその特徴ベクトルに基づいて分類し、識別器の学習においては、学習データをランダムサンプルする際、各クラスに属する学習データを等確率で選択するようにすることによって、学習用データにおけるクラス毎のデータ数に偏りがある場合においても精度のよい識別器を学習し、入力データを精度よく分類することができる。
【００９１】
以上本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形、変更が可能である。
【図面の簡単な説明】
【００９２】
【図１】検出再現率の低くなる例を模式的に表した図である。
【図２】本発明におけるデータ分類が実現可能な装置構成の一例を示す図である。
【図３】本実施形態におけるデータ分類装置の機能構成の一例を示す図である。
【図４】ブートストラップサンプル生成処理手順の一例を示すフローチャートである。
【図５】本実施形態におけるデータ分類システムの機能構成の一例を示す図である。
【図６】識別に用いられる画像の例を示す図である。
【図７】本実施形態を適用した検出精度の一例を示す図である。
【符号の説明】
【００９３】
１０  データ分類装置
１１  入力装置
１２  出力装置
１３  ドライブ装置
１４  補助記憶装置
１５  メモリ装置
１６  ＣＰＵ
１７  ネットワーク接続装置
１８  記録媒体
２１  ブートストラップサンプル生成手段
２２  決定木学習手段
２３  データ分類手段
２４  学習結果データベース
３１  選択データ
３２  ブートストラップサンプル
４１  データ分類システム
４１  キーフレーム抽出手段
４２  ブロック領域分割手段
４３  特徴量抽出手段
４４  被写体フレーム判定手段
【図１】
2010044674.tif 000009
【図２】
2010044674.tif 000010
【図３】
2010044674.tif 000011
【図４】
2010044674.tif 000012
【図５】
2010044674.tif 000013
【図７】
2010044674.tif 000014
【図６】
2010044674.tif 000015