(57)【要約】【課題】分類精度だけでなく計算コストも考慮した決定木を生成し、データ分類のための処理時間を短くする。【解決手段】特徴量算出部２は、学習データから特徴量を計算し、その特徴量の計算に要した平均コスト（計算コスト）を算出する。決定木学習部３は、学習データに対する分類精度の低さを示す不純度と、特徴量の計算コストの逆数とに基づいて評価値を算出し、評価値が最大となる内部ノード及び特徴量を探索することにより、決定木を生成する。これにより、分類精度だけでなく計算コストも考慮した決定木を生成することができる。データ分類部５は、分類対象のデータを入力し、決定木学習部３により生成された決定木を用いて、根ノード及び内部ノード毎に特徴量を計算して分岐を行い、到達した葉ノードが示すカテゴリを分類結果として出力する。これにより、計算コストも考慮した決定木を用いるから、処理時間が短くなる。【選択図】図１
2011028519.tif 000002
【特許請求の範囲】
【請求項１】
複数の特徴量を属性に持つデータを、決定木に基づいて複数のカテゴリに分類する際に、前記特徴量及び分岐条件が割り当てられた根ノード及び内部ノード、並びに分類結果のカテゴリが割り当てられた葉ノードからなる決定木であって、前記根ノードから複数の内部ノードまたは葉ノードへ分岐し、前記内部ノードから他の内部ノードまたは葉ノードへと分岐する木構造の決定木を用いたデータ分類装置において、
前記決定木を生成するための学習用のデータから、前記複数の特徴量をそれぞれ計算し、前記特徴量の計算コストを算出する特徴量算出部と、
前記特徴量算出部により計算された特徴量及び前記分岐条件により、葉ノードへ分岐したときの、前記学習用のデータに対する分類精度の低さを示す不純度と、前記特徴量の計算コストの逆数とに基づいて、前記特徴量毎に評価値を算出し、前記評価値が最大となる特徴量を探索し、前記探索した特徴量を根ノードまたは内部ノードに割り当て、前記決定木を生成する決定木学習部と、を備えたことを特徴とするデータ分類装置。
【請求項２】
請求項１に記載のデータ分類装置において、
前記決定木学習部は、前記葉ノードを新たな内部ノードに置き替え、前記新たな内部ノードに分岐して複数の新たな葉ノードを設定し、前記特徴量算出部により計算された特徴量を前記新たな内部ノードに割り当てた場合の前記評価値を、前記新たな内部ノード毎及び前記特徴量毎に算出し、前記評価値が最大となる新たな内部ノード及び特徴量を探索し、前記探索した特徴量を前記探索した新たな内部ノードに割り当てることにより、前記決定木を生成する、ことを特徴とするデータ分類装置。
【請求項３】
請求項１または２に記載のデータ分類装置において、
前記決定木学習部は、さらに、前記生成した決定木を構成する内部ノードのうち、下位側に内部ノード及び葉ノードが配置された内部ノードを選定し、
前記選定した内部ノード並びに下位側に配置された内部ノード及び葉ノードからなる子孫ノードについて、前記子孫ノードによる計算コストの増加量を第１の計算コスト増加量として算出し、
前記子孫ノードによる前記不純度の減少量を第１の不純度減少量として算出し、
前記子孫ノードを新たな内部ノードに置き替え、前記新たな内部ノードに分岐して複数の新たな葉ノードを設定し、前記特徴量算出部により計算された特徴量を前記新たな内部ノードに割り当てた場合の前記計算コストの増加量及び前記不純度の減少量を、前記新たな内部ノード毎及び前記特徴量毎に、第２の計算コスト増加量及び第２の不純度減少量として算出し、
前記第１の計算コスト増加量から第２の計算コスト増加量を減算した結果が所定の閾値よりも大きく、かつ、前記第２の不純度減少量から第１の不純度減少量を減算した結果が所定の閾値よりも大きいときの前記新たな内部ノード及び特徴量を探索し、前記子孫ノードを前記探索した新たな内部ノード及び複数の新たな葉ノードに置き替え、前記探索した特徴量を前記探索した新たな内部ノードに割り当てることにより、新たな決定木を生成する、ことを特徴とするデータ分類装置。
【請求項４】
請求項１から３までのいずれか一項に記載のデータ分類装置において、
映像を構成する複数のフレーム画像のうち、ショット境界のフレーム画像を検出する際に、
前記特徴量算出部は、前記決定木を生成するための学習映像に基づいて、前記学習映像を構成する複数のフレーム画像の特徴量をそれぞれ計算し、前記特徴量の計算コストを算出し、
前記決定木学習部は、
前記特徴量算出部により計算されたフレーム画像の特徴量及び前記分岐条件により、葉ノードへ分岐したときの、前記フレーム画像が真のショット境界であるか否かの分類精度の低さを示す不純度と、前記特徴量の計算コストの逆数とに基づいて、前記特徴量毎に評価値を算出し、前記評価値が最大となる特徴量を探索し、前記探索した特徴量を根ノードまたは内部ノードに割り当て、前記決定木を生成する、ことを特徴とするデータ分類装置。
【請求項５】
コンピュータを、請求項１から４までのいずれか一項に記載のデータ分類装置として機能させるためのデータ分類プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の特徴量を属性に持つデータを、決定木を用いてカテゴリに分類するための装置及びプログラムに関する。
【背景技術】
【０００２】
図８は、複数の特徴量を属性に持つデータを、カテゴリに分類するための手法を説明する図である。図８に示すように、データをカテゴリに分類する手法は、（１）及び（２）に分けることができる。第１の手法は、（１）に示すように、全特徴量を事前に計算する。このデータ分類装置は、入力したデータに対して全ての特徴量を計算した後、これらの特徴量に基づいて、複数のクラスのカテゴリに分類する。例えば、サポートベクターマシンが用いられる。第２の手法は、（２）に示すように、特徴量を逐次的に計算する。このデータ分類装置は、入力したデータに対して逐次的に特徴量を計算し、この計算した特徴量に基づいて、複数のクラスのカテゴリに分類する。例えば、決定木が用いられる。
【０００３】
第１の手法は、多数の特徴量を全て用いることによりデータを分類するから、分類精度が高くなるという利点があるが、入力した全てのデータに対して全ての特徴量を計算する必要があるから、計算コストが高くなるという問題がある。これに対し、第２の手法は、全ての特徴量を計算することなく、必要な場合にのみ必要な特徴量を計算すればよいから、計算コストを抑えることができるという利点がある。以下に示す本発明は、決定木を用いた第２の手法を対象とする。
【０００４】
〔決定木〕
図９は、決定木の構成例を説明する図である。この決定木は、複数のノードからなるツリーを逆にした構造になっており、ノードには、最上位に位置する根ノード、下位のノードが存在しないノードであって最下位に位置する葉ノード、及び、根ノードと葉ノードとの間に位置する内部ノードの３種類がある。根ノード及び内部ノードには、データの属性を示す複数の特徴量のうちの１つの特徴量がそれぞれ割り当てられており、さらに、特徴量と閾値とを比較することにより、葉ノードまたは内部ノードへ分岐するための分岐条件がそれぞれ割り当てられている。葉ノードには、データが分類されるカテゴリのクラスが割り当てられている。図９の例では、根ノードには、特徴量ｑ０及び図示しない分岐条件、内部ノード０には、特徴量ｑ１及び図示しない分岐条件、内部ノード１には、特徴量ｑ２及び図示しない分岐条件が割り当てられている。また、葉ノード０，１，２には、クラスｌ０のカテゴリが割り当てられ、葉ノード３にはクラスｌ１のカテゴリが割り当てられている。このような決定木は、後述する決定木学習処理により生成される。
【０００５】
このような決定木を用いたデータ分類装置は、入力したデータを、図９に示したクラスｌ０またはクラスｌ１のカテゴリに分類する。具体的には、データ分類装置は、入力したデータに対し、まず根ノードの処理として、データから特徴量ｑ０を計算し、特徴量ｑ０と閾値とを比較して根ノードの分岐条件を判定する。根ノードの分岐条件により、内部ノード０に分岐すると判定した場合、内部ノード０の処理を行う。一方、根ノードの分岐条件により、葉ノード０に分岐すると判定した場合、入力したデータがクラスｌ０のカテゴリに属するとして処理を終了する。
【０００６】
データ分類装置は、根ノードの分岐条件により、内部ノード０に分岐すると判定した場合、内部ノード０の処理として、データから特徴量ｑ１を計算し、特徴量ｑ１と閾値とを比較して内部ノード０の分岐条件を判定する。内部ノード０の分岐条件により、内部ノード１に分岐すると判定した場合、内部ノード１の処理を行う。一方、内部ノード０の分岐条件により、葉ノード１に分岐すると判定した場合、入力したデータがクラスｌ０のカテゴリに属するとして処理を終了する。
【０００７】
データ分類装置は、内部ノード０の分岐条件により、内部ノード１に分岐すると判定した場合、内部ノード１の処理として、データから特徴量ｑ２を計算し、特徴量ｑ２と閾値とを比較して内部ノード１の分岐条件を判定する。内部ノード１の分岐条件により、葉ノード３に分岐すると判定した場合、入力したデータがクラスｌ１のカテゴリに属するとして処理を終了する。一方、内部ノード１の分岐条件により、葉ノード２に分岐すると判定した場合、入力したデータがクラスｌ０のカテゴリに属するとして処理を終了する。
【０００８】
〔決定木学習処理〕
決定木を用いたデータ分類装置における決定木を学習する処理として、例えばＩＤ３（非特許文献１を参照）、Ｃ４．５（非特許文献２を参照）、ＣＡＲＴ（非特許文献３を参照）等のアルゴリズムが知られている。これらの学習処理のアルゴリズムは、特徴量をノードに割り当てるために用いる不純度を、独自の計算式により算出する点で異なる。これに対し、いずれの学習処理のアルゴリズムも、基本的に、不純度が最も減少する特徴量をノードに割り当て、そのノードから分岐させたノードに対して順番に特徴量を割り当て、特徴量をノードに割り当てることができない、またはノードに割り当てた特徴量によって減少する不純度が閾値以下となるまで分岐を繰り返す点で同一である。学習処理によっては、その後、不必要に成長した枝を剪定するための作業（以下、決定木枝刈りという。）を実施する。
【０００９】
以下、不純度としてエントロピーを用いた場合を例にして、従来の決定木学習処理について説明する。ここで、不純度とは、データが分類された場合の分類精度の低さをいう。学習データの集合をＤ、葉ノードの集合をＬとすると、決定木全体の条件付エントロピーは、以下の式により表される。
【数１】
2011028519.tif 000003
【００１０】
また、決定木におけるそれぞれの葉ノードｌｉの条件付きエントロピーは、以下の式により表される。
【数２】
2011028519.tif 000004
【００１１】
ここで、
【数３】
2011028519.tif 000005
であり、Ｎは学習データの総数、Ｃ（ｌｉ）は葉ノードｌｉに属する学習データの総数、Ｃ（ｄｊ｜ｌｉ）は、葉ノードｌｉに属する学習データのうち、真のクラスがｄｊである学習データの総数を示す。
【００１２】
いま、葉ノードｌｉの代わりに、新しい特徴量ｑｋが割り当てられた新しい内部ノードを設定し（葉ノードｌｉを、新しい特徴量ｑｋが割り当てられた新しい内部ノードに置き替え）、さらに、その内部ノードの下に、新しい２つの葉ノードｌｉ，ｓ（ｓ＝０，１）を追加したとする。この場合、新しい葉ノードｌｉ，ｓ（ｓ＝０，１）の条件付エントロピーは、以下の式で表される。
【数４】
2011028519.tif 000006
【００１３】
したがって、葉ノードｌｉを、新しい特徴量ｑｋが割り当てられた新しい内部ノードに置き替え、その内部ノードの下に、新しい葉ノードｌｉ，ｓ（ｓ＝０，１）を追加したことによる決定木全体の条件付エントロピーの減少量は、以下の式で表される。
【数５】
2011028519.tif 000007
【００１４】
図１０は、従来の決定木学習処理を説明するフローチャートである。データ分類装置は、決定木を学習するにあたり、まず、根ノードのみの決定木を作成する（ステップＳ１００１）。ここで、根ノードのみの決定木は、特徴量、分岐条件及びクラスが存在しないノードのみからなる初期状態の決定木である。
【００１５】
データ分類装置は、式（５）に示した、新しい内部ノードの置き替え及び新しい葉ノードの追加による決定木全体の条件付エントロピーの減少量ΔＨ（Ｄ｜ｌｉ，ｑｋ）を算出し、その減少量が最大となる葉ノード（元の葉ノード、新しい内部ノード）
2011028519.tif 000008
、及び、特徴量（新しい特徴量）
2011028519.tif 000009
を探索する（ステップＳ１００２）。ステップＳ１００１から移行した場合、データ分類装置は、根ノードを探索し、学習データの属性を構成する全ての特徴量のうち、式（５）の減少量が最大となる特徴量を探索する。
【００１６】
データ分類装置は、ステップＳ１００２にて選定した葉ノード及び特徴量における、式（５）に示した決定木全体の条件付エントロピーの減少量
2011028519.tif 000010
と、予め設定された閾値εとを比較する（ステップＳ１００３）。決定木全体の条件付エントロピーの減少量が閾値εよりも小さくないと判定した場合（ステップＳ１００３：Ｎ）、探索した葉ノード
2011028519.tif 000011
を、特徴量
2011028519.tif 000012
が割り当てられた新しい内部ノードに置き替え、その内部ノードを分岐して新しい葉ノードを追加する。そして、ステップＳ１００２へ移行する。
【００１７】
一方、ステップＳ１００３において、データ分類装置は、決定木全体の条件付エントロピーの減少量が閾値εよりも小さいと判定した場合（ステップＳ１００３：Ｙ）、処理を終了する。
【００１８】
このように、不純度としてエントロピーを用いて、決定木全体の条件付エントロピーの減少値が最大となる葉ノード及び特徴量を探索し、その特徴量が割り当てられた新しい内部ノード及び新しい葉ノードを設定する学習処理により、根ノード、内部ノード及び葉ノードからなる図９に示すような決定木が生成される。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】J.R.Quinlan, “Induction of Decision Trees”, Machine Learning, vol.1, pp.81-106 (1986)
【非特許文献２】J.R.Quinlan, “C4.5:Programs for Machine Learning”, Morgan Kaufmann (1993)
【非特許文献３】L.Breiman, J.Friedman, R.A.Olshen and C.J.Stone, “Classification and regression trees”, Wadsworth, 1984.
【発明の概要】
【発明が解決しようとする課題】
【００２０】
従来の決定木学習処理では、内部ノードに割り当てる特徴量を選定する際に、分類のための不純度に基づいた分類精度を考慮しているが、特徴量の計算に要する時間、演算数等の計算コストを全く考慮していない。このため、従来の決定木学習処理により生成された決定木を用いるデータ分類装置では、入力したデータを分類する処理のために多大な時間を要する場合があるという問題があった。例えば、従来の決定木学習処理では、他よりも１００倍の計算コストを要する特徴量であったとしても、不純度の減少量が僅かでも大きい場合には、その特徴量が探索され内部ノードに割り当てられてしまう。特に、計算コストを要する特徴量が根ノード、または根ノードに近い内部ノードに割り当てられた場合には、入力されたデータの処理が計算コストを要する根ノードまたは内部ノードを通過する可能性が高くなるから、分類のための処理時間が一層多大になる。
【００２１】
そこで、本発明は前記課題を解決するためになされたものであり、その目的は、決定木を用いてデータをカテゴリに分類する際に、分類精度だけでなく計算コストも考慮した決定木を生成し、データ分類のための処理時間を短くすることが可能なデータ分類装置及びプログラムを提供することにある。
【課題を解決するための手段】
【００２２】
本発明者らは、上記目的を達成すべく鋭意研究開発を行った。その結果、決定木を構成する根ノード及び内部ノードに割り当てる特徴量を選定する際に、データに対する分類精度の低さを示す不純度と、データから特徴量が計算されるときの計算コストとを考慮した評価値を算出し、この評価値が最大となる特徴量を探索することを見出した。このような学習処理を行うことにより、分類精度だけでなく計算コストも考慮した効果的な決定木を生成することができる。したがって、このような決定木を用いるデータ分類装置により、精度の高いデータ分類を実現することに加え、データ分類の処理時間を短くすることが可能となる。
【００２３】
本発明によるデータ分類装置は、複数の特徴量を属性に持つデータを、決定木に基づいて複数のカテゴリに分類する際に、前記特徴量及び分岐条件が割り当てられた根ノード及び内部ノード、並びに分類結果のカテゴリが割り当てられた葉ノードからなる決定木であって、前記根ノードから複数の内部ノードまたは葉ノードへ分岐し、前記内部ノードから他の内部ノードまたは葉ノードへと分岐する木構造の決定木を用いたデータ分類装置において、前記決定木を生成するための学習用のデータから、前記複数の特徴量をそれぞれ計算し、前記特徴量の計算コストを算出する特徴量算出部と、前記特徴量算出部により計算された特徴量及び前記分岐条件により、葉ノードへ分岐したときの、前記学習用のデータに対する分類精度の低さを示す不純度と、前記特徴量の計算コストの逆数とに基づいて、前記特徴量毎に評価値を算出し、前記評価値が最大となる特徴量を探索し、前記探索した特徴量を根ノードまたは内部ノードに割り当て、前記決定木を生成する決定木学習部と、を備えたことを特徴とする。
【００２４】
また、本発明によるデータ分類装置は、前記決定木学習部が、前記葉ノードを新たな内部ノードに置き替え、前記新たな内部ノードに分岐して複数の新たな葉ノードを設定し、前記特徴量算出部により計算された特徴量を前記新たな内部ノードに割り当てた場合の前記評価値を、前記新たな内部ノード毎及び前記特徴量毎に算出し、前記評価値が最大となる新たな内部ノード及び特徴量を探索し、前記探索した特徴量を前記探索した新たな内部ノードに割り当てることにより、前記決定木を生成することを特徴とする。
【００２５】
また、本発明によるデータ分類装置は、前記決定木学習部が、さらに、前記生成した決定木を構成する内部ノードのうち、下位側に内部ノード及び葉ノードが配置された内部ノードを選定し、前記選定した内部ノード並びに下位側に配置された内部ノード及び葉ノードからなる子孫ノードについて、前記子孫ノードによる計算コストの増加量を第１の計算コスト増加量として算出し、前記子孫ノードによる前記不純度の減少量を第１の不純度減少量として算出し、前記子孫ノードを新たな内部ノードに置き替え、前記新たな内部ノードに分岐して複数の新たな葉ノードを設定し、前記特徴量算出部により計算された特徴量を前記新たな内部ノードに割り当てた場合の前記計算コストの増加量及び前記不純度の減少量を、前記新たな内部ノード毎及び前記特徴量毎に、第２の計算コスト増加量及び第２の不純度減少量として算出し、前記第１の計算コスト増加量から第２の計算コスト増加量を減算した結果が所定の閾値よりも大きく、かつ、前記第２の不純度減少量から第１の不純度減少量を減算した結果が所定の閾値よりも大きいときの前記新たな内部ノード及び特徴量を探索し、前記子孫ノードを前記探索した新たな内部ノード及び複数の新たな葉ノードに置き替え、前記探索した特徴量を前記探索した新たな内部ノードに割り当てることにより、新たな決定木を生成することを特徴とする。
【００２６】
また、本発明によるデータ分類装置は、映像を構成する複数のフレーム画像のうち、ショット境界のフレーム画像を検出する際に、前記特徴量算出部が、前記決定木を生成するための学習映像に基づいて、前記学習映像を構成する複数のフレーム画像の特徴量をそれぞれ計算し、前記特徴量の計算コストを算出し、前記決定木学習部が、前記特徴量算出部により計算されたフレーム画像の特徴量及び前記分岐条件により、葉ノードへ分岐したときの、前記フレーム画像が真のショット境界であるか否かの分類精度の低さを示す不純度と、前記特徴量の計算コストの逆数とに基づいて、前記特徴量毎に評価値を算出し、前記評価値が最大となる特徴量を探索し、前記探索した特徴量を根ノードまたは内部ノードに割り当て、前記決定木を生成することを特徴とする。
【００２７】
さらに、本発明によるデータ分類プログラムは、コンピュータを、前記データ分類装置として機能させることを特徴とする。
【発明の効果】
【００２８】
このように、本発明によれば、学習用のデータから特徴量及び計算コストを求め、学習用のデータの分類精度の低さを示す不純度及び計算コストに基づいて評価値を算出し、この評価値に基づいて、ノードに割り当てる特徴量を選定するようにした。このような学習処理を行うことにより、分類精度だけでなく計算コストも考慮した効果的な決定木を生成することができる。したがって、精度の高いデータ分類を実現することに加え、データ分類の処理時間を短くすることが可能となる。
【図面の簡単な説明】
【００２９】
【図１】本発明の実施形態によるデータ分類装置の構成を示すブロック図である。
【図２】決定木学習部における決定木学習処理を説明するフローチャートである。
【図３】決定木学習部における決定木枝刈り処理を説明する図である。
【図４】決定木学習部における決定木枝刈り処理を説明するフローチャートである。
【図５】本発明の実施形態によるデータ分類装置をショット境界検出装置に適用した場合における実施例の構成を示すブロック図である。
【図６】ショット境界検出用決定木の構成を説明する図である。
【図７】実験結果を説明する比較表である。
【図８】（１）は全特徴量を事前に計算する例を説明する図である。（２）は特徴量を逐次的に計算する例を説明する図である。
【図９】決定木の構成例を説明する図である。
【図１０】従来の決定木学習処理を説明するフローチャートである。
【発明を実施するための形態】
【００３０】
以下、本発明を実施するための形態について図面を用いて詳細に説明する。
〔データ分類装置の構成〕
まず、本発明の実施形態によるデータ分類装置の構成について説明する。図１は、データ分類装置の構成を示すブロック図である。このデータ分類装置１は、特徴量算出部２、決定木学習部３、結果格納部４及びデータ分類部５を備えている。
【００３１】
特徴量算出部２は、外部から学習データを入力し、学習データから特徴量を計算すると共に、その特徴量の計算に要した平均コスト（計算コスト）を算出する。具体的には、特徴量算出部２は、一つの学習データから複数の特徴量を計算し、全ての学習データについて学習データ毎に全ての特徴量を計算し、全ての特徴量の計算コストを算出する。ここで、特徴量の計算コストは、全ての学習データにおける特徴量の計算コストを、同種の特徴量毎に平均した値である。
【００３２】
例えば、学習データＤ１から３つの特徴量が計算され、それぞれの計算コストがＴ１−Ｄ１，Ｔ２−Ｄ１，Ｔ３−Ｄ１であり、学習データＤ２から同種の３つの特徴量が計算され、それぞれの計算コストがＴ１−Ｄ２，Ｔ２−Ｄ２，Ｔ３−Ｄ２であり、学習データＤ３から同種の３つの特徴量が計算され、それぞれの計算コストがＴ１−Ｄ３，Ｔ２−Ｄ３，Ｔ３−Ｄ３であったとする。この場合、特徴量算出部２は、第１の特徴量について、それぞれの計算コストＴ１−Ｄ１，Ｔ１−Ｄ２，Ｔ１−Ｄ３を平均し、その平均コストを第１の特徴量の計算コストに設定する。同様に、第２の特徴量について、それぞれの計算コストＴ２−Ｄ１，Ｔ２−Ｄ２，Ｔ２−Ｄ３を平均し、その平均コストを第２の特徴量の計算コストに設定し、第３の特徴量について、それぞれの計算コストＴ３−Ｄ１，Ｔ３−Ｄ２，Ｔ３−Ｄ３を平均し、その平均コストを第３の特徴量の計算コストに設定する。そして、特徴量算出部２は、学習データ、特徴量及び計算コストを決定木学習部３に出力する。
【００３３】
尚、特徴量算出部２は、計算コストとして、実測に基づく計算時間を算出するようにしてもよいし、実装されたプログラムに基づく演算数等を算出するようにしてもよい。
【００３４】
決定木学習部３は、特徴量算出部２から学習データ、特徴量及び計算コストを入力し、決定木学習処理及び決定木枝刈り処理を行って決定木を生成し、結果格納部４に格納する。決定木学習処理及び決定木枝刈り処理については後述する。
【００３５】
結果格納部４は、決定木学習部３により格納された決定木を記憶する。結果格納部４に格納された決定木は、データ分類部５によりデータ分類のために読み出される。
【００３６】
データ分類部５は、外部から分類対象のデータを入力すると共に、結果格納部４から決定木を読み出し、決定木に基づいてデータを分類し、分類結果を外部へ出力する。具体的には、データ分類部５は、例えば図９に示した決定木を結果格納部４から読み出し、根ノードにおいて、分類対象のデータから特徴量ｑ０を計算し、根ノードの分岐条件に従って分岐処理を行う。内部ノード０に分岐した場合、内部ノード０において、分類対象のデータから特徴量ｑ１を計算し、内部ノード０の分岐条件に従って分岐処理を行う。このように、特徴量は、各分岐点である根ノード及び内部ノードにおいて、分岐条件に従って到達したときに計算され、最終的に分岐条件に従って葉ノードに到達する。そして、到達した葉ノードのクラスｌ０またはクラスｌ１が分類結果となり、外部へ出力される。
【００３７】
〔決定木学習処理〕
次に、図１に示したデータ分類装置１の決定木学習部３における決定木学習処理について説明する。図２は、決定木学習処理を説明するフローチャートである。このフローチャートには、学習データ、特徴量及び計算コストに基づいて、図９に示したような決定木を生成する学習処理が示されている。
【００３８】
決定木学習部３は、まず、根ノードのみの決定木を作成する（ステップＳ２０１）。ここで、根ノードのみの決定木は、特徴量、分岐条件及びクラスが存在しないノードのみからなる初期状態の決定木である。
【００３９】
決定木学習部３は、分岐可能な葉ノードがあるか否か（後述するステップＳ２０６により分岐できないノードに設定された葉ノード以外の葉ノードが存在するか否か）を判定する（ステップＳ２０２）。分岐可能な葉ノードがないと判定した場合（ステップＳ２０２：Ｎ）、学習処理を終了する。一方、分岐可能な葉ノードがあると判定した場合（ステップＳ２０２：Ｙ）、分岐可能な全ての葉ノードに対して、特徴量算出部２において計算された全ての特徴量を用いて、以下に示す評価値δを算出し、この評価値δが最大となる葉ノード及び特徴量を探索する（ステップＳ２０３）。尚、ステップＳ２０１から移行した場合、決定木学習部３は、根ノードを、分岐可能な葉ノードとして処理を行う。
【００４０】
図１０に示した従来の決定木学習処理では、評価値として、式（５）で示した条件付エントロピーの減少量を用いたが、図２に示す決定木学習処理では、これに加えて、葉ノードｌｉにおける特徴量ｑｋの計算に要した計算コストの増加量を考慮する。具体的には、決定木学習部３は、評価値δの算出に際し、葉ノードｌｉの代わりに、新しい特徴量ｑｋが割り当てられた新しい内部ノードを設定し（葉ノードｌｉを、新しい特徴量ｑｋが割り当てられた新しい内部ノードに置き替え）、その下に新しい葉ノードを追加した場合に、計算コストの増加量を次の式により計算する。
【数６】
2011028519.tif 000013
【００４１】
ここで、Ｔは、葉ノードｌｉが置き替えられた新しい内部ノードにおいて、特徴量ｑｋの計算に要した計算コストを示し、０．０から１．０までの範囲で正規化されているものとする。各特徴量に対する計算コストは、図１に示した特徴量算出部２において、実測に基づく処理時間または実装されたプログラムに基づく演算数等により算出された値である。また、Ｐ（ｌｉ）は、式（３）と同様の値であり、葉ノードｌｉに属する学習データの数Ｃ（ｌｉ）を学習データの総数Ｎで除算した値である。
【００４２】
このように、式（６）に示した計算コストの増加量は、計算コストＴ（ｌｉ，ｑｋ）と、この葉ノード（新しい内部ノード）に学習データが到達する確率Ｐ（ｌｉ）とを乗算することにより算出される。したがって、式（６）は、葉ノード（新しい内部ノード）で処理される学習データ数も考慮しているから、通過する学習データが多い根ノードに近い内部ノードには、より計算コストの低い特徴量が選定されることが期待できる。
【００４３】
また、決定木学習部３は、葉ノードｌｉを、新しい特徴量ｑｋが割り当てられた新しい内部ノードに置き替え、その下に新しい葉ノードを追加したことにより、決定木全体の条件付エントロピーの減少量を、式（５）により算出する。そして、決定木学習部３は、式（６）により算出した計算コストの増加量、及び、式（５）により算出したエントロピーの減少量を用いて、以下の式により評価値を算出する。
【数７】
2011028519.tif 000014
【００４４】
式（７）におけるΔＨは、式（５）により算出されたノード分岐による不純度の減少量を示す。また、式（７）は、計算コストあたりの効果を反映した評価値となっている。式（７）中のΦは、計算コストをどの程度考慮するかを表す変換関数である。ｗは、その調整パラメータであり、計算コストまたは分類精度のうちのどちらを重視するかを調整するために用いられる。変換関数Φの例としては、以下のとおりである。
【数８】
2011028519.tif 000015
常にΦ＝１とした場合は、計算コストを全く考慮しない従来のデータ分類装置と同様になる。逆に、微小な計算コストの増加に対して、評価値が大きく増加するような関数を用いた場合は、より計算コストが重視された決定木が構成されることとなる。
【００４５】
そして、決定木学習部３は、算出した評価値δ（ｌｉ，ｑｋ）が最大となる葉ノード（元の葉ノード、新しい内部ノード）
2011028519.tif 000016
、及び、特徴量（新しい特徴量）
2011028519.tif 000017
を探索する。
【００４６】
決定木学習部３は、評価値δと所定の閾値εとを比較し（ステップＳ２０４）、評価値δが閾値εよりも大きいと判定した場合（ステップＳ２０４：Ｙ）、
探索した葉ノード
2011028519.tif 000018
を、特徴量
2011028519.tif 000019
が割り当てられた新しい内部ノードに置き替え、その内部ノードを分岐して新しい葉ノードを追加し（ステップＳ２０５）、ステップＳ２０２へ移行する。一方、評価値δが閾値εよりも大きくないと判定した場合（ステップＳ２０４：Ｎ）、葉ノード
2011028519.tif 000020
をこれ以上分岐できないノードに設定し（ステップＳ２０６）、ステップＳ２０２へ移行する。ステップＳ２０２〜ステップＳ２０６の処理は、分岐可能な葉ノードが存在する限り繰り返して行われる。このようにして、根ノード、内部ノード及び葉ノードからなる図９に示すような決定木が生成される。
【００４７】
このように、データ分類装置１の決定木学習部３によれば、決定木学習処理により、分類精度だけでなく計算コストも考慮した評価値を用いて、内部ノードに置き替える葉ノード、及び、内部ノードに割り当てる特徴量を探索し、決定木を生成するようにした。これにより、データ分類部５は、決定木学習部３により生成された決定木を用いて、精度の高いデータ分類を行うことができ、データ分類の処理時間を短くすることができる。
【００４８】
尚、データ分類装置１の決定木学習部３は、条件付エントロピーにより不純度を算出するようにしたが、前述した非特許文献２のＣ４．５等で利用される情報利得率、または、前述した非特許文献３のＣＡＲＴにおけるＧＩＮＩ係数等により不純度を算出するようにしてもよい。後述する決定木枝刈り処理においても同様である。
【００４９】
また、決定木学習部３は、ステップＳ２０２において、分岐可能な葉ノードがあるか否かを判定するようにしたが、分岐可能な葉ノードが、所定の深さのノード位置に存在するか否か、ステップＳ２０２からステップＳ２０６までの処理を所定数行ったか否か、または、探索対象の特徴量があるか否かを判定するようにしてもよい。この場合、分岐可能な葉ノードが所定の深さのノード位置に存在するとき、前記処理を所定数行ったとき、または、探索対象の特徴量がないときに、処理を終了する。
【００５０】
〔決定木枝刈り処理〕
次に、図１に示したデータ分類装置１の決定木学習部３における決定木枝刈り処理について説明する。図３は、決定木枝刈り処理を説明する図であり、図４は、決定木枝刈り処理を説明するフローチャートである。このフローチャートには、学習データ、特徴量及び計算コストに基づいて生成した決定木に対し、さらに計算コストを考慮した決定木を生成するための枝刈り処理が示されている。
【００５１】
図３に示すように、決定木枝刈り処理は、ある内部ノードｌｉについて、その子孫ノード（内部ノードｌｉ、内部ノードｌｉに分岐した下位の内部ノード及び葉ノード）の全てにおける計算コストの和及び分類精度を基準にして、それと同程度の性能が得られる別の特徴量が存在する場合、その特徴量を内部ノードｌｉに割り当て、子孫ノードを、その特徴量が割り当てられた内部ノードｌｉ及び新しい葉ノードに置き替えるものである。決定木枝刈り処理は、根ノードに近い内部ノードから順に、葉ノードへ向かって内部ノード毎に行われる。
【００５２】
図４を参照して、決定木学習部３は、まず、深さ０のノード（根ノード）を開始ノードにするため、深さＤ＝０を設定する（ステップＳ４０１）。そして、決定木学習部３は、深さＤにおいて未処理の内部ノードがあるか否か（着目した内部ノードとして処理していない内部ノードがあるか否か）を判定する（ステップＳ４０２）。未処理の内部ノードがあると判定した場合（ステップＳ４０２：Ｙ）、ステップＳ４０３へ移行し、未処理の内部ノードがないと判定した場合（ステップＳ４０２：Ｎ）、ステップＳ４０７へ移行する。
【００５３】
決定木学習部３は、ステップＳ４０２から移行して、未処理の内部ノードのうちの一つの内部ノードに着目し、その着目した内部ノードを最上位の内部ノードとした子孫ノードにおける計算コストの増加量ΔＴを算出し、条件付きエントロピーの減少量ΔＨを算出する（ステップＳ４０３）。
【００５４】
具体的には、決定木学習部３は、子孫ノードｌｎによる計算コストの増加量を次の式により算出する。
【数９】
2011028519.tif 000021
ここで、子孫ノードｌｎは、最上位の内部ノード（着目した内部モード）ｌｉを含むノード群を示す。
【００５５】
また、決定木学習部３は、子孫ノードｌｎの条件付きエントロピーを、以下の式により算出する。
【数１０】
2011028519.tif 000022
ここで、ｌｔは、着目した内部ノードｌｉのうちの葉ノードを示す。
【００５６】
そして、決定木学習部３は、子孫ノードｌｎに基づく決定木全体の条件付エントロピーの減少量を、以下の式により算出する。
【数１１】
2011028519.tif 000023
【００５７】
決定木学習部３は、以下の式を満たす特徴量ｑｋを複数の特徴量の中から探索する（ステップＳ４０４）。
【数１２】
2011028519.tif 000024
ここで、ΔＴ（Ｌｉ）は、子孫ノードｌｎによる計算コストの増加量であり、ΔＴ（ｌｉ，ｑｋ）は、着目した内部ノードｌｉ（子孫ノードｌｎにおける最上位の内部モードｌｉ）を、新しい特徴量ｑｋが割り当てられた内部ノードに置き替え、その新しい内部ノードに分岐した新しい葉ノードを設定した場合における、計算コストの増加量（子孫ノードｌｎを新しい内部ノード及び新しい葉ノードに置き替えた場合における、計算コストの増加量）である。また、ΔＨ（Ｄ｜ｌｉ，ｑｋ）は、着目した内部ノードｌｉ（子孫ノードｌｎにおける最上位の内部モードｌｉ）を、新しい特徴量ｑｋが割り当てられた内部ノードに置き替え、その新しい内部ノードに分岐した新しい葉ノードを設定した場合における、決定木全体の条件付エントロピーの減少量（子孫ノードｌｎを新しい内部ノード及び新しい葉ノードに置き替えた場合における、条件付エントロピーの減少量）であり、ΔＨ（Ｄ｜Ｌｉ）は、子孫ノードｌｎに基づく決定木全体の条件付エントロピーの減少量である。
【００５８】
また、Ｔｈｒ１は計算コストの閾値であり、Ｔｈｒ２は条件付エントロピーの閾値である。すなわち、子孫ノードｌｎを、特徴量ｑｋが割り当てられた新しい内部ノード及び新しい葉ノードに置き替えた場合に、子孫ノードｌｎによる計算コストの増加量から、特徴量ｑｋが割り当てられた新しい内部ノード等における計算コストの増加量を減算した値が、閾値Ｔｈｒ１よりも大きく、かつ、特徴量ｑｋが割り当てられた新しい内部ノード等に基づく決定木全体の条件付エントロピーの減少量から、子孫ノードｌｎに基づく決定木全体の条件付エントロピーの減少量を減算した値が、閾値Ｔｈｒ２よりも大きい条件を満たす特徴量ｑｋを探索する。
【００５９】
決定木学習部３は、式（１２）を満たす特徴量ｑｋがあるか否か判定し（ステップＳ４０５）、特徴量ｑｋがあると判定した場合（ステップＳ４０５：Ｙ）、ステップＳ４０６へ移行し、その特徴量ｑｋがないと判定した場合（ステップＳ４０５：Ｎ）、ステップＳ４０２へ移行する。
【００６０】
決定木学習部３は、ステップＳ４０５から移行して、子孫ノードを削除し、探索した特徴量ｑｋが割り当てられた内部ノードに置き替え、その内部ノードに分岐する葉ノードを追加し（ステップＳ４０６）、ステップＳ４０２へ移行する。
【００６１】
ステップＳ４０２からステップＳ４０６までの処理を、同じ深さＤにある内部ノードについて行う。そして、決定木学習部３は、ステップＳ４０２において、同じ深さＤにある全ての内部ノードについての処理が完了した場合（ステップＳ４０２：Ｎ）、深さＤをインクリメントし（ステップＳ４０７）、深さＤと決定木の深さとを比較し（ステップＳ４０８）、深さＤが決定木の深さよりも大きいと判定した場合（ステップＳ４０８：Ｙ）、処理を終了する。一方、深さＤが決定木の深さよりも大きくないと判定した場合（ステップＳ４０８：Ｎ）、ステップＳ４０２へ移行する。
【００６２】
このように、データ分類装置１の決定木学習部３によれば、分類精度だけでなく計算コストも考慮した決定木を生成した後に、決定木枝刈り処理によって、分類精度及び計算コストの条件式を用いて、置き替えるべき内部ノード、及び、その内部ノードに割り当てる特徴量を探索し、子孫ノードを削除して新たな決定木を生成するようにした。これにより、データ分類部５は、決定木学習部３により生成された新たな決定木を用いて、精度の高いデータ分類を行うことができ、データ分類の処理時間を一層短くすることができる。
【００６３】
また、前述した決定木学習処理により、各内部ノードにおける局所的な最適値に基づいて内部ノードを分岐させ決定木を生成することができるが、その後の決定木枝刈り処理により、一層大局的な視点で特徴量を選択した決定木を生成することができる。例えば、その内部ノードにおける計算コストが小さくても、それ以降に多数の処理が続く場合には、全体としてはデータ分類の処理時間が増大することとなる。決定木枝刈り処理によってこのような内部ノードを差し替えることが可能となり、データ分類の処理時間を削減することができる。また、決定木の構成が単純になるため、様々なデータに対して一層高い分類精度を実現でき、汎化能力の高い決定木を構築することが可能となる。
【００６４】
尚、本発明の実施形態によるデータ分類装置１のハード構成としては、通常のコンピュータを使用することができる。データ分類装置１は、ＣＰＵ、ＲＡＭ等の揮発性の記憶媒体、ＲＯＭ等の不揮発性の記憶媒体、及びインターフェース等を備えたコンピュータによって構成される。データ分類装置１に備えた特徴量算出部２、決定木学習部３、結果格納部４及びデータ分類部５の各機能は、これらの機能を記述したプログラムをＲＡＭ等から読み出してＣＰＵに実行させることによりそれぞれ実現される。また、これらのプログラムは、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ等）、半導体メモリ等の記憶媒体に格納して頒布することもできる。後述するショット境界検出装置１０においても同様である。
【実施例】
【００６５】
次に、図１のデータ分類装置１を利用したアプリケーションの例として、ショット境界検出装置について説明する。ショットとは、１台のカメラで連続して撮影された映像の区間をいい、ショット境界とは、ショットの切り替え点をいう。ショットは映像の基本単位であり、要約した映像及び検索した映像等を扱う際には、まず、元映像をショットに分割する作業が必要不可欠となる。ショット境界検出は、映像解析における最も基本的な処理の一つであり、高速かつ高精度な処理が求められる。そこで、図１のデータ分類装置１を用いることにより、少ない計算コストで正確にショット境界を検出できるようにする。
【００６６】
〔ショット境界検出装置の構成〕
まず、ショット境界検出装置の構成について説明する。図５は、ショット境界検出装置の構成を示すブロック図である。このショット境界検出装置１０は、フレーム画像取得部１１、画像特徴量算出部１２、決定木学習部１３、結果格納部１４、フレーム画像取得部１５及びショット境界検出部１６を備えている。
【００６７】
フレーム画像取得部１１は、外部から学習のために用いる映像（学習映像）を入力し、学習映像をデコードしてフレーム画像を取得し、画像特徴量算出部１２に出力する。画像特徴量算出部１２は、フレーム画像取得部１１からフレーム画像を入力し、フレーム画像から画像特徴量を計算すると共に、その画像特徴量の計算に要した平均コスト（計算コスト）を算出する。計算コストは、例えば、計算時間または計算のための演算数等である。
【００６８】
ここで、画像特徴量について説明する。通常、ショット境界は、フレーム画像間の類似性に基づいて検出することができる。フレーム画像間の類似性は、ショット境界を含まない場合に高くなり、ショット境界を含む場合に低くなるという特性を有しており、この特性によってショット境界が検出される。フレーム画像間の類似性を図る尺度（画像特徴量）としては、様々なものが存在するが、一般的に次のような傾向がある。単純な画像特徴量を用いた場合には、高速な計算が可能であるが、カメラ、被写体等が動くときにフレーム画像間の類似性が低く計算されてしまうから、誤検出が多く発生する可能性がある。これに対し、カメラ、被写体等の動きも考慮した画像特徴量は、計算コストが高く低速な計算になってしまう。本実施例では、これらを考慮して、様々な画像特徴量を利用した決定木を生成する。また、決定木の生成に際し、隣接したフレーム画像間の類似性のみならず、離れたフレーム画像間の類似性も考慮することにより、ショット境界検出精度の向上を図る。具体的には、以下に示す画像特徴量を用いる。
【００６９】
（１）画素値の絶対差分和Ｄsad（ｆi，ｆi-k）
【数１３】
2011028519.tif 000025
ここで、ｆiは、入力した学習映像におけるｉ番目のフレーム画像を示し、Ｆは、フレーム画像における全画素を示す。ｆ（ｖ）は、座標ｖにおける画素値を示す。画像特徴量算出部１２は、式（１３）により、所定のフレーム画像ｆi，ｆi-kについて、画素値の絶対値差分和による画像特徴量Ｄsad（ｆi，ｆi-k）を計算し、この画像特徴量の計算コストを算出する。
【００７０】
（２）ヒストグラム差分和Ｄhist（ｆi，ｆi-k）
画像特徴量算出部１２は、所定のフレーム画像ｆi，ｆi-kについて、画素値の頻度ヒストグラムを作成し、各ビンの頻度の絶対差分和をヒストグラム差分和による画像特徴量Ｄhist（ｆi，ｆi-k）として計算し、その画像特徴量の計算コストを算出する。
【００７１】
（３）エッジ方向ヒストグラム差分和Ｄedge（ｆi，ｆi-k）
画像特徴量算出部１２は、所定のフレーム画像ｆi，ｆi-kについて、エッジ方向ヒストグラムを作成し、各ビンの頻度の絶対差分和をエッジ方向ヒストグラム差分和による画像特徴量Ｄedge（ｆi，ｆi-k）として計算し、その画像特徴量の計算コストを算出する。エッジ方向ヒストグラムは、各画素について、エッジの方向arctan（dy／dx）及びエッジの強さ（dy2＋dx2）1/2を算出することにより、エッジの方向毎にエッジの強さを表した分布図である。エッジの検出には、Ｓｏｂｅｌフィルタ等が用いられる。
【００７２】
（４）余弦Ｄcos（ｆi，ｆi-k）
【数１４】
2011028519.tif 000026
画像特徴量算出部１２は、式（１４）により、所定のフレーム画像ｆi，ｆi-kについて、画素値の余弦による画像特徴量Ｄcos（ｆi，ｆi-k）を計算し、この画像特徴量の計算コストを算出する。
【００７３】
（５）ブロックマッチング差分ＤBM（ｆi，ｆi-k）
画像特徴量算出部１２は、まず、フレーム画像ｆiをブロック領域に分割する。そして、各ブロック領域について、フレーム画像ｆi-kとの間の類似度が閾値以上となる位置を探索する。最後に、類似度が閾値以上となる位置が見つからなかったブロック領域の総数をフレーム画像間の非類似度（画像特徴量ＤBM（ｆi，ｆi-k））として計算し、この画像特徴量の計算コストを算出する。ブロック領域の比較にはヒストグラム差分和、画素値の絶対差分和等が用いられる。
【００７４】
画像特徴量算出部１２は、画像特徴量の計算及び計算コストの算出にあたり、前述の（１）〜（５）におけるｋを例えば１〜５に設定する。すなわち、画像特徴量算出部１２は、ｋ＝１に設定した場合のフレーム画像ｆi，ｆi-1について、（１）〜（５）の画像特徴量の計算及び計算コストの算出を行い、同様に、ｋ＝２〜５に設定した場合のフレーム画像ｆi，ｆi-2〜5について、（１）〜（５）の画像特徴量の計算及び計算コストの算出をそれぞれ行う。これにより、一つのフレーム画像から２５個の画像特徴量及び計算コストが得られる。
【００７５】
具体的には、画像特徴量算出部１２は、一つのフレーム画像から２５個の画像特徴量を計算し、画像特徴量毎に計算コストを算出する。同様にして、全てのフレーム画像について２５個の画像特徴量をそれぞれ計算し、画像特徴量毎に計算コストを算出し、全ての学習映像における画像特徴量の計算コストを、同種の画像特徴量毎に平均し、その平均値を、画像特徴量の計算コストに設定する。これにより、２５個の画像特徴量に対し、それぞれの計算コストが算出される。
【００７６】
決定木学習部１３は、画像特徴量算出部１２からフレーム画像、画像特徴量及び計算コストを入力すると共に、ショット境界の位置であるフレーム画像の番号を示す情報を入力し、図２に示した決定木学習処理及び図４に示した決定木枝刈り処理を行ってショット境界検出用決定木を生成し、結果格納部１４に格納する。ここで、ショット境界検出用決定木を生成する際に用いる不純度は、フレーム画像が真のショット境界であるか否かの分類精度の低さの程度を示す。
【００７７】
結果格納部１４は、決定木学習部１３により格納されたショット境界検出用決定木を記憶する。結果格納部１４に格納されたショット境界検出用決定木は、ショット境界検出部１６によりショット境界検出のために読み出される。
【００７８】
フレーム画像取得部１５は、外部からショット境界検出対象の映像を入力し、映像をデコードしてフレーム画像を取得し、ショット境界検出部１６に出力する。ショット境界検出部１６は、フレーム画像取得部１５からフレーム画像を入力すると共に、結果格納部１４からショット境界検出用決定木を読み出す。そして、ショット境界検出部１６は、ショット境界検出用決定木に基づいて、ショット境界となるフレーム画像ｆiを検出し、検出したフレーム画像ｆiの情報を検出結果として外部へ出力する。
【００７９】
〔ショット境界検出用決定木〕
次に、図５に示した決定木学習部１３により生成され、結果格納部１４に格納されるショット境界検出用決定木の構成について説明する。図６は、ショット境界検出用決定木の構成を説明する図である。決定木学習部１３は、画像特徴量算出部１２から、例えば、前述の（１）〜（５）におけるｋ＝１〜５とした場合における画像特徴量及び計算コストを入力し、図２に示した決定木学習処理により、２５個の画像特徴量を１個の根ノード及び２４個の内部ノード０〜２３に割り当ててショット境界検出用決定木を生成する。そして、図４に示した決定木枝刈り処理により、子孫ノードを内部ノードに置き替えることにより、計算コストを一層考慮したショット境界検出用決定木を生成する。図６の例では、根ノードには、（１）におけるｋ＝１とした場合の画像特徴量Ｄsad（ｆi，ｆi-1）が割り当てられ、内部ノード０には、（２）におけるｋ＝１とした場合の画像特徴量Ｄhist（ｆi，ｆi-1）が割り当てられ、内部ノード１には、（１）におけるｋ＝２とした場合の画像特徴量Ｄsad（ｆi，ｆi-2）が割り当てられ、内部ノード２が分岐した葉ノード０には、クラスｌ０のカテゴリ：フレーム画像ｆiはショット境界である、が割り当てられ、葉ノード１にはクラスｌ１のカテゴリ：フレーム画像ｆiはショット境界でない、が割り当てられている。また、根ノード及び内部ノードには、分岐条件がそれぞれ割り当てられる。
【００８０】
ショット境界検出部１６は、フレーム画像取得部１５から入力したフレーム画像のうちのフレーム画像ｆiを注目フレーム画像として、このフレーム画像ｆiがショット境界であるか否かを、図６に示したショット境界検出用決定木を用いて判定し、ショット境界となるフレーム画像ｆiを検出する。具体的には、ショット境界検出部１６は、ショット境界検出用決定木の根ノードにおいて、フレーム画像ｆi，ｆi-1から（１）の画像特徴量Ｄsad（ｆi，ｆi-1）を計算し、根ノードの分岐条件に従って分岐処理を行う。内部ノード０に分岐した場合、内部ノード０において、フレーム画像ｆi，ｆi-1から（２）の画像特徴量Ｄhist（ｆi，ｆi-1）を計算し、内部ノード０の分岐条件に従って分岐処理を行う。内部ノード２に分岐した場合、当該内部ノード２に割り当てられた画像特徴量を計算し、内部ノード２の分岐条件に従って分岐処理を行う。そして、葉ノード０に分岐した場合、ショット境界検出部１６は、フレーム画像ｆiがショット境界であると判定する。一方、葉ノード１に分岐した場合、ショット境界検出部１６は、フレーム画像ｆiがショット境界でないと判定する。このように、ショット境界検出部１６は、注目したフレーム画像ｆiがショット境界であるか否かを、図６に示したショット境界検出用決定木を用いて判定する。この判定にあたり、根ノード及び内部ノードにおいて、必要な画像特徴量を逐次算出する。
【００８１】
尚、前述の（１）〜（５）に示した画像特徴量は、ショットを瞬時に切り替えるカットを検出するためのものである。複数のフレーム画像に渡るディゾルブ、ワイプ等を検出する場合には、単純なフレーム画像間の類似度だけでなく、他の画像特徴量も追加する必要がある。例えば、動きベクトル等の情報や単調増加または単調減少している画素の割合、エッジの変化量等の画像特徴量を追加することにより、決定木学習部１３において決定木を生成する。
【００８２】
〔実験結果〕
次に、図５に示したショット境界検出装置１０による実験結果について説明する。図７は、実験結果を説明する比較表である。この実験結果は、ドラマ、スポーツ、ドキュメンタリー等の合計約１８０分のテレビ番組の映像のうち、半分の映像を、ショット境界検出用決定木を生成するための学習映像として使用し、半分の映像をショット境界検出対象として使用したときの結果である。また、この実験結果は、図１０の決定木学習処理による決定木を用いた従来のデータ分類装置における結果と、図２の決定木学習処理による決定木を用いた実施例のショット境界検出装置１０における結果とを比較するものである。決定木枝刈り処理は行っていない。図７において、再現率は、ショット境界の検出に対する再現性の観点から検出精度を示したものであり、適合率は、ショット境界の検出に対する適合性の観点からの検出精度を示したものである。また、処理時間は、デコードの時間を除いたショット境界検出のための時間を示している。
【００８３】
図７の実験結果によれば、分類精度だけでなく計算コストを考慮した実施例のショット境界検出装置１０では、分類精度のみを考慮した従来のデータ分類装置と比較して、同程度の検出精度を維持したまま、処理時間を約半分に削減できることがわかる。
【００８４】
以上のように、実施例によるショット境界検出装置１０によれば、ショット境界検出精度だけでなく計算コストも考慮した効果的なショット境界検出用決定木を用いて、映像を構成するフレーム画像のショット境界を検出するようにした。これにより、精度の高いショット境界を検出することができることに加え、検出処理時間を短くすることが可能となる。
【符号の説明】
【００８５】
１  データ分類装置
２  特徴量算出部
３，１３  決定木学習部
４，１４  結果格納部
５  データ分類部
１０  ショット境界検出装置
１１，１５  フレーム画像取得部
１２  画像特徴量算出部
１６  ショット境界検出部
【図１】
2011028519.tif 000027
【図２】
2011028519.tif 000028
【図３】
2011028519.tif 000029
【図４】
2011028519.tif 000030
【図５】
2011028519.tif 000031
【図６】
2011028519.tif 000032
【図７】
2011028519.tif 000033
【図８】
2011028519.tif 000034
【図９】
2011028519.tif 000035
【図１０】
2011028519.tif 000036