(57)【要約】      （修正有）【課題】対象物を分類し、その位置を特定する。【解決手段】学習ステージで確率ブースティングツリー（ＰＢＴ）によりツリーが自動生成される。このツリーでは各ノードにより多数の弱い分類器が強い分類器または条件付き事後確率に組み合わされる。ＰＢＴは、分割統治法を介するデータオーグメンテーションによって目標の事後分布にアプローチする。テストステージでは上記条件付き確率が、学習された分類器に基づいて各ツリーノードで計算され、確率がサブツリーに伝搬される。ツリーの最上部のノードはサブツリーから集めた確率をまとめることにより全体的な事後確率を出力する。トレーニングステージでは、各ツリーノードが強い分類器であるツリーが再帰的に構成される。入力されるトレーニング集合は、学習した分類器にしたがって新たな左および右側の集合に分けられる。各集合は左および右側のサブツリーを再帰的にトレーニングするために使用される。【選択図】図２
2006252559.tif 000002
【特許請求の範囲】
【請求項１】
画像にて対象物の位置を特定する方法において、
該方法は、
ａ）  確率ブースティングツリーを構成して、当該確率ブースティングツリーにて各ノードにより、多数の弱い分類器が組み合わされて強い分類器または条件付き事後確率になるようにするステップと、
ｂ）  位置を特定すべき前記対象物を含む少なくとも１つの入力画像を受け取るステップと、
ｃ）  前記の条件付き事後確率に基づいて、前記の対象物が存在するはずである、前記入力画像のバウンディングボックスを識別するステップと、
ｄ）  前記の対象物が実際に前記の位置にある尤度に基づいて前記バウンディングボックスに対する確率値を計算するステップと、
ｅ）  前記入力画像にて相異なる位置で前記ステップｃ）〜ｄ）を繰り返すステップと、
ｆ）  計算され最も高い確率を有するバウンディングボックスを、前記対象物が存在する位置として選択するステップとを有することを特徴とする、
画像における対象物の位置を特定する方法。
【請求項２】
前記ステップｅ）はさらに、
前記画像にてさまざまに回転させて少なくとも１つの入力画像をサーチするステップと、
前記画像にてさまざまな縦横比で少なくとも１つの入力画像をサーチするステップとを有する、
請求項１に記載の方法。
【請求項３】
前記の弱い分類器は対象物のフィーチャを表す、
請求項１に記載の方法。
【請求項４】
前記の対象物は解剖学的構造体である、
請求項１に記載の方法。
【請求項５】
前記の解剖学的構造体は左心室である、
請求項４に記載の方法。
【請求項６】
前記の解剖学的構造体は胎児の頭部である、
請求項４に記載の方法。
【請求項７】
前記の解剖学的構造体は胎児の腹部である、
請求項４に記載の方法。
【請求項８】
前記の解剖学的構造体は胎児の大腿部である、
請求項４に記載の方法。
【請求項９】
前記の解剖学的構造体は顔である、
請求項４に記載の方法。
【請求項１０】
前記の解剖学的構造体は直腸管である、
請求項４に記載の方法。
【請求項１１】
画像にて対象物を検出する方法において、
該方法は、
ａ）  確率ブースティングツリーを構成して、各ノードにより、多数の弱い分類器が強い分類器または条件付き事後確率に組み合わされてようにするステップと、
ｂ）  少なくとも１つの入力画像を受け取るステップと、
ｃ）  前記の条件付き事後確率に基づき、対象物が存在し得る、少なくとも１つの入力画像のバウンディングボックスを識別するステップと、
ｄ）  前記の対象物が画像にある尤度に基づいて前記バウンディングボックスに対する確率値を計算するステップと、
ｅ）  当該の確率と、あらかじめ定めた閾値とを比較するステップと、
ｆ）  前記の確率があらかじめ定めた閾値を上回る場合、当該バウンディングボックスを保持するステップと、
ｇ）  前記の画像の相異なる位置で前記ステップｃ）〜ｆ）を繰り返すステップと、
ｈ）  少なくとも１つのバウンディングボックスに対する確率が前記のあらかじめ定めた閾値を上回る場合に前記対象物が当該画像内にあることを決定することを特徴とする、
画像にて対象物を検出する方法。
【請求項１２】
前記のステップｇ）はさらに、
前記画像にてさまざまに回転させて少なくとも１つの入力画像をサーチするステップと、
前記画像にてさまざまな縦横比で少なくとも１つの入力画像をサーチするステップとを有する、
請求項１１に記載の方法。
【請求項１３】
前記のサーチをコートツーグレイン（coarse-to-grain）方式で行う、
請求項１２に記載の方法。
【請求項１４】
前記の弱い分類器は対象物のフィーチャを表す、
請求項１１に記載の方法。
【請求項１５】
前記の対象物は解剖学的構造体である、
請求項１１に記載の方法。
【請求項１６】
前記の解剖学的構造体は左心室である、
請求項１５に記載の方法。
【請求項１７】
前記の解剖学的構造体は胎児の頭部である、
請求項１５に記載の方法。
【請求項１８】
前記の解剖学的構造体は胎児の腹部である、
請求項１５に記載の方法。
【請求項１９】
前記の解剖学的構造体は胎児の大腿部である、
請求項１５に記載の方法。
【請求項２０】
前記の解剖学的構造体は顔である、
請求項１５に記載の方法。
【請求項２１】
前記の解剖学的構造体は直腸管である、
請求項１５に記載の方法。
【請求項２２】
対象物の画像を異なる画像カテゴリに分類する方法において、
該方法は、
各ツリーノードが強い分類器である確率ブースティングツリーを再帰的に構成し、ここで識別モデルが当該ツリーの最上部に得られ、当該ツリーの各レベルにはオーグメントされた変数が含まれるようにし、
学習した分類器にしたがって、入力トレーニング集合を新たな２つの集合に分け、
当該の新たな２つの集合を使用して、左側および右側のサブツリーを再帰的にトレーニングし、クラスタリングが階層的に自動的に形成されるようにし、
形成されたクラスタの数に基づいて、適切な数の分類を出力することを特徴とする、
対象物の画像を異なる画像カテゴリに分類する方法。
【請求項２３】
前記の確率ツリーによって２クラス問題を解く、
請求項２２に記載の方法。
【請求項２４】
前記の適切な数の分類を出力するステップは、ポジティブクラスおよびネガティブクラスを含む、
請求項２２に記載の方法。
【請求項２５】
前記の確率ツリーによってマルチクラス問題を解く、
請求項２２に記載の方法。
【請求項２６】
前記の適切な数の分類を出力するステップは、複数のカテゴリを含む、
請求項２２に記載の方法。
【請求項２７】
前記の対象物は解剖学的構造体である、
請求項２２に記載の方法。
【請求項２８】
前記の解剖学的構造体は左心室である、
請求項２７に記載の方法。
【請求項２９】
前記の解剖学的構造体は胎児の頭部である、
請求項２７に記載の方法。
【請求項３０】
前記の解剖学的構造体は胎児の腹部である、
請求項２７に記載の方法。
【請求項３１】
前記の解剖学的構造体は胎児の大腿部である、
請求項２７に記載の方法。
【請求項３２】
前記の解剖学的構造体は顔である、
請求項２７に記載の方法。
【請求項３３】
前記の解剖学的構造体は直腸管である、
請求項２７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連する明細書への相互参照
本明細書は、２００５年３月９日に提出した米国暫定明細書第６０／６６０，１３６号に優先権を主張するものであり、ここではその全体を本明細書に組み込むものとする。
【０００２】
発明の分野
本発明は、識別モデルを学習するための確率ブースティングツリーフレームワーク（probabilistic boosting tree framework）に関し、さらに具体的には２クラスおよびマルチクラス識別モデルを計算するための確率ブースティングツリーフレームワークに関する。
【０００３】
発明の背景
自然のシーンにおいて一般的な対象物を分類／認識、検出およびクラスタリングするという作業は、極めて取り組みがいのある課題である。その困難さは、多くの理由に起因する。すなわち、極めて大きなクラス内での変化およびクラス間での類似性、明瞭度（articulation）および動き、ライティング条件の違い、向き／見る方向、および異なる対象物の複合した構成などに起因するのである。図１には数多くの画像が示されている。図１の第１行１０２ではいくつかの顔の画像が表示されている。残りの行１０４〜１１０には、カリフォルニア工科大学の対象物の１０１カテゴリ（Caltech 101 categories of objects）からいくつかの典型的な画像が示されている。いくつかの対象物は、極めて非剛性（non-rigid）であり、また同じカテゴリに含まれる対象物には互いにほとんど類似性を有しないものもある。分類作業に対して、１クラスに属する別個のインスタンスを同じカテゴリに入れるために極めて高いレベルの知識が必要である。
【０００４】
一般的なシーンを理解するという課題は、２つの側面、すなわちモデリングおよび計算という側面で観察することができる。モデリングが扱うのは、一般的なパターン／対象物の統計をどのように学習／定義するかという課題である。計算が取り込むのは推論の課題である。ｘを画像サンプルとし、またその解釈をｙとする。理論的には生成モデルp(x｜y)が、１パターンに対して得られて任意のサンプルｘについての統計が測定される。残念なことに、このような生成モデルには到達できないことが多いだけでなく、このような生成モデルは、計算ステージにおいて大きな計算負担を形成してしまうのである。例えば顔は、研究が比較的容易なクラスと考えられる。それでもなお、多視点、影、表情、隠れ（occlusion）および髪型などの顔に対するすべての変化形態を捉える生成モデルは存在していないのである。いくつかの顔のサンプルは、図１の第１行１０２に見ることができる。択一的には識別モデルp(y｜x)がじかに学習される。ここでｙは単に「イエス」または「ノー」を示す単純な変数またはクラスラベルである。
【０００５】
AdaBoostと称される公知の手法およびその変形手法は、視覚および機械学習における数多くの課題に適用されて成功を収めてきた。AdaBoostは、弱い分類器の集合を選択して組み合わせて強い分類器にすることによって事後分布（posterior）p(x｜y)に到達しようとする。しかしながら、現在のAdaBoost法にはいくつか問題がある。第１にこれは目標の分布に漸近的に収束するのであるが、数百もの弱い分類器を選択しなければならないことになり得る。これにより、極めて大きな計算負荷が課される。第２に、トレーニングステージにおいてフィーチャが選択された順序は保存されないのである。フィーチャの集合の順序は、高レベルのセマンティックスに相応することがあり、したがって対象物／パターンの理解に極めて重要なのである。第３に、AdaBoostの再重み付け方式は、前に正しく分類したサンプルを再度誤って分類しまうことがあるのである。第４に２クラスからマルチクラスへの拡張が提案されているが、出力されたコーディングを使用し、マルチクラスにおいて弱い分類器を学習することはさらに困難であり、また計算コストもかかってしまうのである。
【０００６】
通例AdaTreeと称される別の公知の手法では、AdaBoostと決定木（decision tree）とが組み合わされる。このAdaTree法の主たる目標は、プルーニング（pruning）によってAdaBoost法を高速化することである。AdaTree法は、弱い分類器の集合をツリー構造に組み合わせることによって強い分類器を学習するが、これはマルチクラス分類を扱っていない。
【０００７】
対象物の分類および検出を扱うためには数多くのアプローチがある。AdaBoostと一緒に使用されるカスケードアプローチは、例外事象検出（rare event detection）において有効であることが示されている。このカスケード法は、本発明の方法の特別なケースと見ることができる。このカスケードでは、すべてのポジティブサンプルがツリーの右側に押しやられるように閾値が選択される。しかしながらポジティブサンプルを右側に押しやることにより、殊にポジティブサンプルとネガティブサンプルとを分けるのが困難である場合には大きく誤ったポジティブレートが発生してしまうことがある。本発明の方法ではトレーニング集合が自然に２つの部分に分けられる。ポジティブサンプルよりもネガティブサンプルが多い場合、ほとんどのネガティブサンプルは、最上部に近いリーフノードに移される。ツリーの深いところにあるリーフは、分けることが困難なポジティブサンプルおよびネガティブサンプルの分類に専念する。
【０００８】
決定木は視覚および人工知能において広く使用されている。伝統的な決定木において、各ノードは弱い意思決定器（decision maker）であり、したがって各ノードにおける結果は一層ランダムである。これとは異なり、本発明では各ノードは強い意思決定器であり、分布q(y｜x)を学習する。別のアプローチにはＡ*、生成モデル、ＥＭならびに文法およびセマンティックスが含まれる。必要とされるのは、マルチクラス分類に使用され、識別モデルを学習することのでき、高い計算負荷を要しないフレームワークである。
【０００９】
発明の要約
本発明は、画像において対象物の位置を特定する方法に関する。ここでは確率ブースティングツリーが構成され、この確率ブースティングツリーでは各ノードによって、多数の弱い分類器が強い分類器または条件付き事後確率に組み合わされる。位置を特定すべき対象物を含む少なくとも１つの入力画像が受け取られる。上記の条件付き事後確率に基づいて、上記の対象物が存在するはずである、この入力画像のバウンディングボックスが識別される。このバウンディングボックスに対する確率値は、上記の対象物がこの位置に実際にある尤度に基づいて計算される。バウンディングボックスおよび確率値は、上記の入力画像におけるさまざまな位置に対して決定される。計算され最も高い確率を有するバウンディングボックスが、対象物が存在する場所として選択される。
【００１０】
本発明はまた画像において対象物を検出する方法に関する。ここでは確率ブースティングツリーが構成され、この確率ブースティングツリーでは各ノードによって、多数の弱い分類器が強い分類器または条件付き事後確率に組み合わされる。少なくとも１つの入力画像が受け取られる。上記の対象物が存在し得る、少なくとも１つの入力画像のバウンディングボックスが上記の条件付き事後確率に基づいて識別される。バウンディングボックスに対する確率値は、対象物がこの画像に実際にある尤度に基づいて計算される。この確率は、あらかじめ定めた閾値と比較される。この確率があらかじめ定めた閾値を上回る場合、上記のバウンディングボックスは保持される。バウンディングボックスおよび確率値は、上記の入力画像におけるさまざまな位置に対して決定される。少なくとも１つのバウンディングボックスに対する確率が上記のあらかじめ定めた閾値よりも大きい場合、この対象物がこの画像に存在することについての決定が行われる。
【００１１】
本発明はまた対象物の画像を異なる画像カテゴリに分類する方法に関する。確率ブースティングツリーは再帰的に構成され、このツリーにおいて各ツリーノードは強い分類器である。識別モデルは、ツリーの最上部において得られ、ツリーの各レベルは、オーグメントされた変数を含む。入力トレーニング集合は、学習された分類器にしたがって、新たな２つの集合に分けられる。これらの新たな２つの集合は、左側および右側のサブツリーをトレーニングするために再帰的に使用されて、クラスタリングが階層的に自動的に形成される。形成されるクラスタの数に基づいて、適切な数の分類が出力される。
【００１２】
本発明の有利な実施形態を以下、添付の図面に関連してさらに詳しく説明する。ここでは同様の参照符号は、同様の要素を示す。
【００１３】
本発明は、２クラスおよびマルチクラス識別モデルを計算するための確率ブースティングツリーフレームワークに関する。学習ステージにおいて確率ブースティングツリー（ＰＢＴ  probabilistic boosting tree）によって自動的にツリーが構成され、このツリーでは各ノードにより、多数の弱い分類器（例えば、証拠（evidence）、知識）が強い分類器または条件付き事後確率に組み合わされる。このＰＢＴは、分割統治法（divide-and-conquer strategy）を介し、データオーグメンテーション（data augmentation，例えば、ツリー拡張）によって目標の事後分布にアプローチする。
【００１４】
テストステージにおいて上記の条件付き確率は、学習した分類器に基づいて各ツリーノードで計算される。これによってそのサブツリーに確率が伝搬されることになる。したがってこのツリーの最上部のノードは、そのサブツリーから集めた確率をまとめることによって全体的な事後確率を出力する。またクラスタリングは学習フェーズに自然に埋め込まれ、各サブツリーは特定のレベルのクラスタを表すのである。
【００１５】
トレーニングステージではツリーは再帰的に構成され、ここで各ツリーノードは強い分類器である。入力トレーニング集合は、学習された分類器にしたがって、新たな２つの集合、左側の集合と右側の集合とに分割される。つぎに各集合が使用されて左側および右側のサブツリーが再帰的にトレーニングされる。ツリーの最上部で得られた識別モデルは、データオーグメンテーションによって目的の事前分布にアプローチする。このツリーの各レベルは、オーグメントされた変数である。クラスタリングは学習ステージに本質的に埋め込まれ、クラスタは自動的に発見され、階層的に形成される。
【００１６】
マルチクラス問題に対して、目標は、階層的なツリー構造を保ちながら識別モデルを学習することである。これはマルチクラス分類問題を特殊な２クラス分類問題として扱うことによって行われる。各ノードでは、ポジティブラベルまたはネガティブラベルいずれかが各クラスに割り当てられて全体的なエントロピーが最小化される。この手順により、マルチクラス学習手順および２クラス学習手順が統合される。マルチクラスのクラスタはここでもじかに形成される。
【００１７】
一般的なAdaBoost法およびその変形形態は、強い分類器を弱い分類器の集合を組み合わせることによって強い分類器を学習する。すなわち、
【００１８】
【数１】
2006252559.tif 000003
であり、ここでｈｔ(ｘ)は弱い分類器である。全体的なエラーレートε ＝ Σｉｗｉ[sign[Ｈ(ｘｉ)]≠ｙｉ]は、
【００１９】
【数２】
2006252559.tif 000004
によって制限されることが示されており、ここでｗｉは、サンプルｘｉの確率である。
【００２０】
複合的な分布から得られるｘｉを扱う場合、εｔはすぐさま０．５に近づき、つぎのこの収束は遅くなる。考えられる１つの対処法は、ポジティブなものとネガティブなものとをより良好に分けることができるより効果的な弱い分類器を設計することである。残念なことに良好な弱い分類器を得ることは困難なことが多く、これらの分類器およびフィーチャを計算する際の計算上の複雑さはさらに別の制限になってしまう。AdaBoostのキーとなるアイデアの１つは、誤って分類されたサンプルが、つぎの機会により多く重み付けづけされることである。Ｄｔに対する正規化および更新ルールに起因して、以前に正しく分類されたサンプルは再び誤って分類され、したがってペナルティを受けることがある。このため、いくつかのステップの後、弱い分類器は無効になってしまうのである。すべての弱い分類器を一緒にして単一の強い分類器にする代わりに、分割統治法のアプローチを使用する。
【００２１】
図２には本発明にしたがって、確率ブースティングツリーフレームワークをインプリメントするための一般的なシステムのブロック図が示されている。１つ以上の画像が、カメラのような入力デバイス２０２を使用して得られる。これらの画像は、ＰＢＴフレームワークを画像に適用するプロセッサ２０４によって受け取られる。このＰＢＴフレームワークは、以下に一層詳しく説明する多くの作業を遂行するために使用可能である。例えば、このＰＢＴフレームワークは、対象物の分類または対象物の検出に使用することができる。データベース２０６に格納されているトレーニングサンプルは、識別モデルを学習して計算するために使用可能である。このシステムは入力画像を受け取って、分類結果を出力する。２クラス問題の場合、この出力はポジティブまたはネガティブのいずれかである。マルチクラス問題では、この画像の所属するクラスが出力である。この分類結果はつぎにディスプレイ２０８に表示される。
【００２２】
図３には本発明にしたがってブースティングツリーをトレーニングする方法の概略が示されている。表記を簡単にするため、学習した各AdaBoost法によって計算された確率をつぎのように書き表す。すなわち
【００２３】
【数３】
2006252559.tif 000005
である。
【００２４】
このアルゴリズムは直感にわかりやすい。これは再帰的にツリーを学習する。各ノードでは強い分類器が、標準のブースティングアルゴリズムを使用して学習される。つぎにトレーニングサンプルは、学習した分類器を使用して、左側の集合および右側の集合の新たな２つの集合に分けられる。これらの集合はつぎに左側のサブツリーおよび右側のサブツリーをトレーニングするためにそれぞれ使用される。変数εは、過学習（overfitting）の問題をある程度制御するために使用される。［１／２−ε，１／２＋ε］の範囲に入るサンプルは、曖昧なサンプルであり、左側および右側のサブツリーの両方においてトレーニングに使用されることになる。ε＝１／２の場合、すべてのトレーニングサンプルは、強い分類器に基づいて再計算された重み付けで両方のサブツリーにわたされる。この場合、ＰＢＴはブースティングと同様になる。ε＝０の場合、各サンプルは右側または左側のツリーのいずれかにわたされる。したがって同じものがなければ、ポジティブサンプルと、ネガティブサンプルとはほぼ確実に分けられれる。しかしながらこれらはデータを過学習することがある。
【００２５】
１つのトレーニングセットが２つの部分に分けられる場合、新たなエラーレートは、
εｓｐｌｉｔ ＝Σｉｗｉ(l)[Ｈｌ(ｘｉ)≠ｙｉ]＋Σｉｗｉ(r) [Ｈｒ (ｘｉ)≠ｙｉ] ≦ε    （３）
ただし、ε ＝ Σｉｗｉ[Ｈ(ｘｉ)≠ｙｉ]
である。
【００２６】
Ｈｌ＝ＨおよびＨｒ=Ｈの場合に等号が成り立つこと確かめるのは容易である。一般的には入力サンプル数を低減することによって問題の複雑さが低減され、決定の境界もより良好になる。
【００２７】
このモデルでは、ポジティブサンプルおよびネガティブサンプルは自然に複数のサブグループに分けられる。図４には、どのようにツリーが学習され、またトレーニングサンプルが分けられるかの例が示されている。分類が困難なサンプルはさらに下にわたされて、このツリーは拡張されることになる。ポジティブなものおよびネガティブなもののクラスタリングは自然に行われる。１つのグループは、他のグループに対する補助変数として使用される。各ツリーのノードは強い分類器であるため、複合した分布を有するサンプルを扱うことができる。またクラスタの数をあらかじめ指定する必要もない。このツリーの階層構造によって、識別の相異なるレベルにしたがってクラスタを記録することができる。
【００２８】
図４に示したようにＰＢＴは、２０００個の点からなる合成データセット４０２から形成される。弱い分類器は、２Ｄラインとの距離およびポジションのようなフィーチャについての尤度分類器である。ツリー４０４，４０６の第１レベルより、全体集合が２つの部分４０８，４１０に分けられる。一方の集合４０８は、主として暗い点を有している。それはこれらは残りの雲状の部分から離れているからである。ポジティブサンプルおよびネガティブサンプルが絡み合っている部分においてこのツリーが拡張される。さらなるレベル４１２〜４１８は集合４１０から拡張されて、これらによってこの集合から暗い点と明るい点とが良好に分けられる。
【００２９】
テストステージは上記のトレーニングステージと整合している。図５には、近似された事後確率
【００３０】
【数４】
2006252559.tif 000006
を計算するための詳細が示されている。ツリーの根には、子孫からの情報が集められ、全体的な近似された事後分布が記録される。このアプローチは、困難な決定を行う分類器に転換させることもできる。q(＋1｜x)およびq(−1｜x)を計算した後、q(＋1｜x)とq(−1｜x)とを比較することよって決定を行い、右または左のサブツリーに進むことができる。このツリーのリーフノードに含まれている実験的な分布
【００３１】
【数５】
2006252559.tif 000007
はつぎにこのツリーのルートノードに戻される。しかしながら確率を使用することの利点は明らかである。ＰＢＴを一旦トレーニングしてしまえば、
【００３２】
【数６】
2006252559.tif 000008
は、精度とリコールとの間をバランスさせるための閾値として使用可能である。
【００３３】
図６には本発明によるツリーの確率モデルの例が示されている。各ツリーノード６０〜６１２は強い分類器である。暗いノード６２０〜６３２はリーフノードである。ここでは複雑なパターンｘが、隠された変数の集合を有する生成処理によって生成されている。ＰＢＴは、暗黙的なデータオーグメンテーションを行うことによって類似の様相を有すると見なすことができる。この学習法の目標は、事後分布ｐ(ｙ｜ｘ)を学習することである。各ツリーレベルｌｉは、オーグメントされた変数である。
【００３４】
【数７】
2006252559.tif 000009
【００３５】
ツリーノードにおいて、正確なモデルを学習できる場合、
【００３６】
【数８】
2006252559.tif 000010
であり、これはモデルｑ(ｌｉ＋１｜ｌｉ,…,ｌ１,ｘ)がｙを完全に予想し、したがってツリーの拡張が停止することを意味する。オーグメントされた変数ｌｉは徐々にｘからｙをデカップリングし、より良好な予想が行われる。
【００３７】
ここまで２クラスブースティングツリーアプローチを説明した。マルチクラス分類に対する慣用のブースティングアプローチにはマルチクラスの弱い分類器が必要であり、一般的にはマルチクラスの弱い分類器を学習および計算するために２クラスの弱い分類器よりもはるかに計算コストがかかる。これはクラスの数が大きくなる場合に殊に問題である。おもしろいことに、相異なるパターンのクラスはしばしばある側面では互いに類似している。例えば、ロバは離れたところから見ると馬のように見える。
【００３８】
図７には本発明にしたがってマルチクラスブースティングツリーをトレーニングする手順が概略が示されている。この手順では最初に、マルチクラスパターンを２クラスに分ける最適なフィーチャがサーチされ、つぎに前の２クラスブースティングツリー法を使用して分類器が学習される。多くの場合、マルチクラスを２クラスに変換した後、ブースティング法よって選択されるフィーチャは、このマルチクラスを分けるために選択されるフィーチャであることが多い。直感的には選択された弱い分類器／フィーチャの残りは、最初のフィーチャをサポートしており、これによって強い決定が行われる。したがって２クラス分類問題は、マルチクラス問題の特殊ケースなのである。これらのフィーチャによれば、相異なるクラスに属する類似の対象物は、別のものに照らして分類される。ツリーの拡張が継続されるにつれて、これらは次第にクラスタリングされて分離される。この拡張は、各クラスの分離が成功するか、またはトレーニングサンプルが少なすり過ぎた場合に停止される。
【００３９】
マルチクラスＰＢＴに対するテスト手順は、２クラス問題とほぼ同じである。ここでもツリーの最上部のノードにより、そのサブツリーからのすべての確率がまとめられて全体的な事後確率が出力される。この問題のスケールは、クラスの数ｎについてＯ(log(n))である。このマルチクラスＰＢＴは、階層構造に起因して確率の計算が極めて効率的である。これは、数百または数千もの対象物のクラスを認識したい場合には重要であり、これはヒューマンビジョンシステムが日々取り組んでいる問題である。最悪のケースでは各ツリーノードを横断的に移動しなければならない。しかしながらこれは実用上は希なケースである。
【００４０】
本発明により、上記のマルチクラス確率ブースティングツリーは、対象物の分類に使用可能である。ここでは１つの実施例を説明する。図８には４つの対象物の画像のヒストグラムが、輝度および３つのガボールフィルタリング結果について示されている。ここに示した画像は４つのカテゴリを表す。すなわち、盆栽８０２，８０４，ピューマの身体８０６，８０８，ドル紙幣８１０，８１２およびケッチ８１４，８１６である。ヒストグラムは平行移動および回転に対してロバストであり、良好な識別能力を有することが示されている。１画像の相異なるフィルタ応答についてヒストグラムは、相異なる手掛かり（cue）として有効であり、これらはシーン分析および対象物認識を実行するために使用して組み合わせることができる。識別モデルを学習するために、ヒストグラムｈ(ｓ)毎に３次のモーメントまでが計算されて、高速な計算のためにインテグラールイメージ（integral image）が使用される。
【００４１】
目標は識別モデルを学習して、この識別モデルにより、入力画像パッチ毎に分類ラベルについての事後分布が出力されるようにすることである。各対象物画像は、８０×８０のパッチにサイズ変更される。画像パッチ毎に３つのスケールにおけるキャニー（Canny）エッジ検出器、エッジの向きおよび１０個のガボールフィルタによるフィルタリング結果が使用されてエッジマップが計算される。これらは画像パッチに対する手掛かりの画像（cue image）である。さまざま位置でセンタリングされ相異なるサイズおよび縦横比を有する１０００個の矩形が８０×８０の画像パッチにされる。フィーチャは、各手掛かり画像における矩形毎のヒストグラムのモーメントである。つぎにマルチクラスＰＢＴは、これらのフィーチャを選択し組み合わせて階層的な分類器を形成する。
【００４２】
説明のため、画像データセットにおいて全体で８０個のカテゴリから２９個を選択する。カテゴリ毎に４１個のカテゴリがあり、これらのうちのいくつかが図９に示されている。これらの画像は、複数の対象物に対してさまざまな視覚方向および照明で採取されている。つぎにトレーニングのために各カテゴリからランダムに２５個の画像が選択される。図９にはサンプル画像９０２と、学習の後、ブースティングツリーにおいて形成されたクラスタ９０４とが示されている。本発明のアプローチによって可能になるのは、クラス内の類似性ならびにクラス間の類似性および非類似性を自動的に発見することである。トレーニングに選択されなかった画像に対して認識／分類率をテストする。最も高い確率を有するものが、正しい認識と考えられる。以下の表１にはカテゴリ毎に残りの１６画像についての認識率が示されている。平均認識率は７６％である。
【００４３】
【表１】
2006252559.tif 000011
【００４４】
つぎの例では、Caltech１０１画像カテゴリとして知られているさらに複雑な画像集合を使用する。典型的な画像のうちのいくつかが図１に示されている。
【００４５】
原画像で作業する代わりにすべての画像はトリミングされて８０×８０にサイズ変更される。学習およびテストはこれらのトリミングされた画像に基づいて行われる。つぎにトレーニングのため、２５個の画像が各カテゴリからランダムに選択される。図１０にはトレーニングの後、形成されるクラスタのうちのいくつかが示されている。しかしながら対象物のカテゴリが複雑であることに起因して、上に説明した別の画像集合のクラスタよりもまばらである。カテゴリｙｊ毎にヒストグラムが計算され、
ｈ(Ｎ) ＝ Σｉδ(Ｎ−Ｎ(ｘｉ))                          （６）
であり、ここでＮはリーフノードであり、またＮ(ｘｉ)はトレーニングサンプルｘｉが最終的に位置するリーフノードである。ｈ(Ｎ)のエントロピーは、ツリーにおいて各カテゴリのサンプルがどの程度密（tight）であるかを示す。カテゴリにおいて互いに類似している対象物に対しては、密なクラスタを形成すべきである。大きな変化を有する対象物は、ツリー中により一層散らばっている。以下に示した表２ではカテゴリ名の後の第３の列には、カテゴリ毎のエントロピー測度（entropy measure）が示されている。
【００４６】
【表２】
2006252559.tif 000012
【００４７】
「陰陽（ying yang）」のような対象物カテゴリは極めて小さなエントロピーを有しており、また背景のカテゴリが最大の変動性および最も大きなエントロピーを有することは意外ではない。エントロピー測度がルーズに示すのは、各カテゴリを認識するのがどの程度困難になり得るかである。分類／認識結果は表２に示されている。カテゴリ名の後の第１の列ｒ１は、識別モデルがそのカテゴリｉｄを、最も高い確率を有するカテゴリｉｄとして出力する場合の認識率である。ｒ１に対する平均認識率は２０％である。ランダムなあてずっぽうの推測は、約１％になる。第２の列ｒ２は、カテゴリｉｄがトップテンの選択肢中にある場合の分類率である。ｒ２に対する平均的なレートは４０％である。
【００４８】
本発明は、対象物の検出および分類の両方に使用可能である。ＰＢＴが有効であり得るアプリケーションのいくつかの例に含まれるのは、マルチビューの顔検出、左心室の位置特定、胎児の測定（例えば胎児の頭部、腹部および大腿部）などである。この場合、本発明はさらに、検出した対象物の分類に使用可能である。例えば左心室の場合、左心室を長い左心室と、丸い左心室とに分類することができる。胎児測定の場合、頭部測定値と腹部測定値とを分けることができるのである。
【００４９】
ＰＢＴは、すべての同じサイズの整列された約2000個のポジティブサンプルと、90000個のネガティブサンプルとについてトレーニングされる。ネガティブサンプルにはポジティブサンプルをシフトしたコピーも含まれている。これはより良好に位置特定を行うためである。図１１には心臓の入力ビデオを表す一連の静止画１１０２と、本発明にしたがって左心室が検出された結果画像１１０４とが示されている。検出のため、入力画像１１０２においてさまざまな位置、回転角、スケールおよび縦横比で、コースツーファイン（coarse-to-fine）法を使用して左心室がサーチされる。各サーチ位置、回転、スケールおよび縦横比は、左心室が存在すべきである必ずしも水平でないバウンディングボックスに相応する。バウンディングボックスの例には１１０６〜１１１０が含まれている。トレーニングされたＰＢＴにより、このようなボックス毎に確率が得られ、最も確率の高いボックスが、左心室の位置、サイズおよびボックスとして選択される。左心室１２０２の位置特定の例は図１２に示されている。「＋ｓ」は、心内膜壁１２０４を示している。バウンディングボックス１２０６は、左心室の位置を表す。
【００５０】
同じ手法は、超音波データから胎児の頭部、腹部および大腿部の位置を特定するためにも使用される。図１３〜１５には本発明にしたがって胎児の頭部１３０２、胎児の腹部１４０２および大腿部１５０２を位置特定する例が示されている。左心室と同じように胎児の頭部、腹部または大腿部が、入力画像においてさまざまな位置、回転角、スケールおよび縦横比で、コースツーファイン法を使用してサーチされる。各サーチ位置、回転、スケールおよび縦横比は、頭部、腹部または大腿部が存在すべきであるバウンディングボックスに相応する。トレーニングされたＰＢＴにより、このようなボックス毎に確率が得られ、最も確率の高いボックスが、頭部、腹部または大腿部の位置、サイズおよび向きとして選択される。
【００５１】
ＰＢＴは３次元ＣＴデータから直腸（Rectal Tube）を検出するためにも使用可能である。１実施例を図１６および１７に基づいて説明する。軸回転に対して不変であり、グラディエントおよび曲率に基づく7000個のフィーチャからなる集合をトレーニングに使用した。このトレーニング集合は、約20000個の管セグメントをポジティブな例として含んでおり、また250000個のネガティブな例を含んでいる。
【００５２】
通例、３Ｄデータにおける管のサーチには、計算の上で法外ともいえる管の多くの位置、３Ｄ方向およびサイズが必要である。ここではその代わりにテンソルボーティング（tensor voting）法が使用されて、管の候補の３Ｄ位置、方向および半径が提示される。トレーニングされたＰＢＴ分類器は、管の候補毎に計算され、閾値よりも高い確率を有する候補が、図１６および１７の管１６０２および１７０２によって示したように、検出された管として選択されるのである。
【００５３】
上に示したように本発明はマルチビューの顔検出にも使用可能である。トレーニングされたＰＢＴによって、顔のビューのさまざまな例が得られる。図１８には、正面および側面の画像集合でテストした顔検出結果のいくつかの例が示されている。
【００５４】
ここでは確率ブースティングツリーフレームワークを使用してマルチクラス識別モデルを計算する方法についての実施形態を説明したが、ここに説明したことを考え合わせれば、当業者により、さまざまな修正および変更が行われ得ることに注意されたい。したがって開示した本発明の特定の実施形態は変更でき、これらの変更は添付の請求項に定められた本発明の範囲および精神内にあることを理解されたい。本発明を特許法によって必要とされる詳細で説明したが、請求され特許法によって保護されることを望む事項は添付の請求項に記載されている。
【図面の簡単な説明】
【００５５】
【図１】共通な対象物および自然なシーンの画像の例を示す図である。
【図２】本発明にしたがって確率ブースティングツリーをインプリメントするシステムのブロック図である。
【図３】本発明にしたがってブースティングツリーをトレーニングする方法の概略を示す図である。
【図４】本発明にしたがって、どのように確率ブースティングツリーが学習され、またトレーニングサンプルが分けられるかの例を示す図である。
【図５】本発明にしたがってブースティングツリーをテストする方法の概略を示す図である。
【図６】本発明によるツリーの確率モデルの例を示す図である。
【図７】本発明にしたがってマルチクラス確率ブースティングツリーをトレーニングする方法の概略を示す図である。
【図８】本発明による４つの対象物の画像のヒストグラムを輝度および３つのガボールフィルタリング結果について示す図である。
【図９】画像集合のうちのいくつかのサンプル画像および本発明にしたがって学習されたクラスタを示す図である。
【図１０】本発明にしたがって形成された、いくつかのサンプル画像クラスタを示す図である。
【図１１】心臓の入力ビデオから得られる静止画像と、本発明にしたがって得られた左心室検出結果とを示す図である。
【図１２】本発明にしたがい、超音波画像において左心室の位置を特定する例を示す図である。
【図１３】本発明にしたがい、超音波画像において胎児の頭部位置を特定する例を示す図である。
【図１４】本発明にしたがい、超音波画像において胎児の腹部位置を特定する例を示す図である。
【図１５】本発明にしたがい、超音波画像において胎児の大腿部位置を特定する例を示す図である。
【図１６】本発明にしたがい、コンピュータトモグラフ画像において直腸管を検出する例を示す図である。
【図１７】本発明にしたがって図１６の直腸管を拡大したビューを示す図である。
【図１８】本発明にしたがって顔検出を行う例を示す図である。
【図２】
2006252559.tif 000013
【図３】
2006252559.tif 000014
【図５】
2006252559.tif 000015
【図７】
2006252559.tif 000016
【図１】
2006252559.tif 000017
【図４】
2006252559.tif 000018
【図６】
2006252559.tif 000019
【図８】
2006252559.tif 000020
【図９】
2006252559.tif 000021
【図１０】
2006252559.tif 000022
【図１１】
2006252559.tif 000023
【図１２】
2006252559.tif 000024
【図１３】
2006252559.tif 000025
【図１４】
2006252559.tif 000026
【図１５】
2006252559.tif 000027
【図１６】
2006252559.tif 000028
【図１７】
2006252559.tif 000029
【図１８】
2006252559.tif 000030
【外国語明細書】
2006252559.tif 000031
2006252559.tif 000032
2006252559.tif 000033
2006252559.tif 000034
2006252559.tif 000035
2006252559.tif 000036
2006252559.tif 000037
2006252559.tif 000038
2006252559.tif 000039
2006252559.tif 000040
2006252559.tif 000041
2006252559.tif 000042
2006252559.tif 000043
2006252559.tif 000044
2006252559.tif 000045
2006252559.tif 000046
2006252559.tif 000047
2006252559.tif 000048
2006252559.tif 000049
2006252559.tif 000050
2006252559.tif 000051
2006252559.tif 000052
2006252559.tif 000053
2006252559.tif 000054
2006252559.tif 000055
2006252559.tif 000056
2006252559.tif 000057
2006252559.tif 000058
2006252559.tif 000059
2006252559.tif 000060
2006252559.tif 000061
2006252559.tif 000062
2006252559.tif 000063
2006252559.tif 000064
2006252559.tif 000065
2006252559.tif 000066
2006252559.tif 000067