(57)【要約】【課題】探索窓の伸縮に関して処理を高速化でき、原理的に探索漏れを生じない信号探索装置を提供する。【解決手段】入力信号上の領域に任意の大きさの第１の探索窓と第２の探索窓をそれぞれ配置し、前記各探索窓の特徴量をそれぞれ抽出し、前記各特徴量を用いて、前記探索窓間の類似度を算出し、前記類似度が予め定めた閾値より小さくなる場合には、前記探索窓の大きさと前記領域の位置を出力し、前記類似度が前記閾値を下回り得ないように、前記探索窓の大きさを伸縮する伸縮率を算出し、前記伸縮率によって前記各探索窓の大きさを伸縮し、前記伸縮した探索窓の大きさが予め定められた大きさになれば終了し、前記伸縮した探索窓の大きさが前記予め定められた大きさにならなければ、前記処理をそれぞれ繰り返すように制御する。【選択図】      図１
2010218022.tif 000002
【特許請求の範囲】
【請求項１】
入力信号上の領域に任意の大きさの第１の探索窓と第２の探索窓をそれぞれ配置する注目領域抽出部と、
前記各探索窓の特徴量をそれぞれ抽出する特徴抽出部と、
前記各特徴量を用いて、前記探索窓間の前記両特徴量が類似する程に値が大きくなる類似度を算出する類似度算出部と、
前記類似度が予め定めた閾値より小さくなる場合には、前記探索窓の大きさと前記領域の位置を出力する結果出力部と、
前記類似度が前記閾値を下回り得ないように、前記探索窓の大きさを伸縮する伸縮率を算出する伸縮率算出部と、
前記伸縮率によって前記各探索窓の大きさを伸縮し、（１）前記伸縮した探索窓の大きさが予め定められた大きさになれば信号探索処理を終了し、（２）前記伸縮した探索窓の大きさが前記予め定められた大きさにならなければ、前記特徴抽出部へ前記伸縮した前記探索窓の大きさを出力し、前記特徴抽出部の前記抽出処理、前記類似度算出部の前記算出処理、前記結果出力部の前記出力処理、前記伸縮率の前記算出処理を前記信号探索処理が終了するまでそれぞれ繰り返す繰り返し制御部と、
を有することを特徴とする信号探索装置。
【請求項２】
前記類似度算出部が前記入力信号の前記領域中の位置毎に算出したそれぞれの前記類似度から最大類似度を選択する類似度選択部をさらに有し、
前記伸縮率算出部は、前記最大類似度を用いて、前記伸縮率を算出する、
ことを特徴とする請求項１に記載の信号探索装置。
【請求項３】
前記入力信号を複数の領域に分割し、前記分割された領域毎に前記探索窓の大きさを伸縮させる、
ことを特徴とする請求項２に記載の信号探索装置。
【請求項４】
前記伸縮率算出部は、前記伸縮部で伸縮した前記両探索窓の現在の大きさを用いて、次に伸縮したい前記両探索窓の大きさを予測し、
前記類似度算出部は、前記予測した大きさの前記両探索窓を用いて前記類似度を求め、
前記繰り返し制御部は、前記予測した大きさから求めた前記類似度から計算される前記伸縮率が、前記両探索窓の伸縮可能な範囲外の場合には、前記予測した両探索窓の大きさを、前記両探索窓の現在の大きさに近づけるバックトラックを行う、
ことを特徴とする請求項１に記載の信号探索装置。
【請求項５】
前記第１の探索窓と前記第２の探索窓が隣接し、かつ、同じ形状であるか、前記第１の探索窓と前記第２の探索窓のそれぞれが複数の領域を有するか、又は、前記第１の探索窓の面積と前記第２の探索窓の面積が異なる、
ことを特徴とする請求項１に記載の信号探索装置。
【請求項６】
前記特徴抽出部が算出する前記特徴量は、前記入力信号の信号値のヒストグラム、又は、信号値の平均である、
ことを特徴とする請求項１に記載の信号探索装置。
【請求項７】
前記類似度算出部が算出する前記類似度は、前記入力信号の信号値の平均値の差、又は、前記信号値のヒストグラム重なり率である、
ことを特徴とする請求項１に記載の信号探索装置。
【請求項８】
前記類似度算出部が算出する前記類似度は、前記探索窓の大きさが前記伸縮率によって変化するときの前記類似度の上限を求める式で表されている、
ことを特徴とする請求項１に記載の信号探索装置。
【請求項９】
前記入力信号は、映像信号、画像信号、時空間画像信号、音声信号、文字列、又は、３次元ボリューム信号である、
ことを特徴とする請求項１に記載の信号探索装置。
【請求項１０】
前記類似度として、前記探索窓間の前記両特徴量が類似する程に値が小さくなる距離の逆数を用いる、
ことを特徴とする請求項１に記載の信号探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力信号の信号探索装置、信号探索方法及びプログラムに関する。
【背景技術】
【０００２】
特許文献１では、テンプレート画像照合に関して、テンプレート画像を移動しても類似度が急激に変化しない性質を利用して、テンプレート画像周囲の類似度の上限を求め、類似度が予め与えられた閾値θを下回る領域の照合を省略することによって照合を高速化した。この手法はアクティブ探索法と呼ばれる．
また、特許文献２では、２つの窓間の類似度を用いた特徴抽出処理に関して、窓を移動しても類似度が急激に変化しない性質を利用して、その類似度を算出した窓の位置の周辺において、類似度が予め与えられた閾値θを明らかに下回らない位置での照合処理を省略することによって特徴抽出処理を高速化した。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第３４７４１３１号公報
【特許文献２】特開２００８−６５２６５公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
２つの窓を伸縮させながらその間の類似度を算出する処理において、例えば１．２５倍などの経験的な倍率で窓の大きさを変化させた。そのため、原理的に探索もれが生じるという問題点があった。
【０００５】
そして、データの性質に応じて倍率を変更する必要がある。例えば、画像エッジ検出で複数の角度の線を検出したり、顔検出で複数の角度の顔を検出したりする場合には、複数の識別器を並列動作させる必要があるため、処理の高速化が求められていた。
【０００６】
そこで本発明は、上記問題点に鑑みて、探索窓の伸縮に関して処理を高速化でき、探索漏れを生じない信号探索装置、信号探索方法及びプログラムを提供する。
【課題を解決するための手段】
【０００７】
本発明は、入力信号上の領域に任意の大きさの第１の探索窓と第２の探索窓をそれぞれ配置する注目領域抽出部と、前記各探索窓の前記両特徴量が類似する程に値が大きくなる特徴量をそれぞれ抽出する特徴抽出部と、前記各特徴量を用いて、前記探索窓間の類似度を算出する類似度算出部と、前記類似度が予め定めた閾値より小さくなる場合には、前記探索窓の大きさと前記領域の位置を出力する結果出力部と、前記類似度が前記閾値を下回り得ないように、前記探索窓の大きさを伸縮する伸縮率を算出する伸縮率算出部と、前記伸縮率によって前記各探索窓の大きさを伸縮し、（１）前記伸縮した探索窓の大きさが予め定められた大きさになれば信号探索処理を終了し、（２）前記伸縮した探索窓の大きさが前記予め定められた大きさにならなければ、前記特徴抽出部へ前記伸縮した前記探索窓の大きさを出力し、前記特徴抽出部の前記抽出処理、前記類似度算出部の前記算出処理、前記結果出力部の前記出力処理、及び、前記伸縮率算出部の前記算出処理をそれぞれ繰り返すように制御する繰り返し制御部と、を有することを特徴とする信号探索装置である。
【発明の効果】
【０００８】
本発明によれば、探索窓の伸縮に関して処理を高速化でき、探索漏れが生じない。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施例１による画像エッジ検出で用いる探索窓の説明図である。
【図２】本発明の実施例１による画像エッジ検出で行う動作の説明図である。
【図３】本発明の実施例１に係わる信号探索装置の構成を示すブロック図である。
【図４】本発明の実施例１の動作を示すフローチャートである。
【図５】探索窓を拡大しても右側が暗いエッジを検出しないことが明らかな例を説明するための図である。
【図６】探索窓縮小時の伸縮率下限の算出方法を説明するための図である。
【図７】探索窓拡大時の伸縮率上限の算出方法を説明するための図である。
【図８】従来方法によって伸縮率を変化させながら照合する様子を説明するための図である。
【図９】本発明の実施例１によって伸縮率を変化させながら照合する様子を説明するための図である。
【図１０】実施例１と同様に類似度を算出できる探索窓の例を説明するための図である。
【図１１】面積比率の異なる探索窓の例を説明するための図である。
【図１２】複雑な形状の探索窓の例を説明するための図である。
【図１３】ショット境界検出での探索窓縮小時の伸縮率上限の算出方法を説明するための図である。
【図１４】ショット境界検出での探索窓拡大時の伸縮率上限の算出方法を説明するための図である。
【図１５】Ｖｉｏｌａ−Ｊｏｎｅｓらの顔検出方法で用いるＨａａｒ−ｂａｓｅｄ特徴を説明するための図である。
【図１６】Ｖｉｏｌａ−Ｊｏｎｅｓらの顔検出方法の動作を説明するための図である。
【図１７】探索枠と探索窓の位置関係の例を説明するための図である。
【図１８】探索枠内での探索窓の位置の違いを説明するための図である。
【図１９】探索枠内での探索窓の位置の違いによって入力画像上の探索範囲領域を変化させることを説明するための図である。
【図２０】本発明の実施例に係る信号探索装置のハードウエアの構成を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施例の信号探索装置について図面に基づいて説明する。本発明の実施例の信号探索装置は、音声信号の話者交代検出、動画の映像信号のショット境界検出、文字列信号のテキスト話題分割、画像信号の画像エッジ検出、画像信号の顔検出、時空間画像信号の部分画像境界検出、３次元ボリュームデータの３次元境界検出、などに適用できる。
【００１１】
また、実施例１、実施例１の変更例１，２，４、実施例２及び実施例３において用いる類似度は、比較する対象が近いほど値が小さくなる距離で表し、一方、実施例１の変更例３及び変更例５にヒストグラム重なり率の説明で用いた類似度は、比較する対象が近いほど値が大きくなる値で表している。そのため、実施例１、実施例１の変更例１，２，４、実施例２及び実施例３において用いる類似度は、最小になったときに比較対象が最も類似している状態となる。また、実施例１の変更例３及び変更例５にヒストグラム重なり率の説明において用いる類似度は、最大になったときに比較対象が最も類似している状態となる。
【実施例１】
【００１２】
本発明の実施例１に係る信号探索装置を図１〜図１２に基づいて説明する。
【００１３】
本実施例では、信号探索装置が入力画像に含まれる縦方向のエッジ検出を信号探索処理するものであるが、図５に示すように、入力画像全体について左側がだんだん暗くなるグラデーションであるにも関わらず、左側の探索窓よりも右側の探索窓の方が暗いエッジを探索する場合を想定して説明する。
【００１４】
（１）信号探索装置の構成
本実施例の信号探索装置について図３に基づいて説明する。図３は本実施例に係る信号探索装置の構成図である。
【００１５】
信号探索装置は、信号入力部１０１、検出器１０２、伸縮率算出部１０３、類似度選択部１０４を有する。
【００１６】
信号入力部１０１は、画像信号を入力して記憶する。
【００１７】
検出器１０２は、画像上の全ての位置について探索窓を走査して、類似度が予め与えられた閾値θ（０≦θ≦１）を下回る場合に探索窓の位置、大きさ及び類似度を出力する。
【００１８】
類似度選択部１０３は、同じ大きさの探索窓について検出器１０２から出力される類似度を入力し、その中の最小の類似度を出力する。
【００１９】
伸縮率算出部１０４は、類似度選択部１０３で求めた最小の類似度に基づいて、探索窓を縮小する伸縮率を算出する。また、この伸縮率算出部１０４は、以上の処理をまず最大の探索窓の大きさβｍａｘで行い、求めた伸縮率で探索窓を縮小しながら処理を繰り返し、最大の探索窓の大きさβｍｉｎ以下になるまで行うように制御する繰り返し制御部の機能も兼ねている。
【００２０】
検出器１０２は、注目領域抽出部１０５、特徴抽出部１０６、類似度算出部１０７、部分結果出力部１０８を有する。
【００２１】
注目領域抽出部１０５は、信号入力部１０１に記憶された画像上のある位置に、２種類の探索窓、すなわち、第１の探索窓内と第２の探索窓内を設定して、それらの中に含まれる画素を出力する。探索窓は伸縮率算出部１０３で指定された大きさとする。
【００２２】
特徴抽出部１０６は、第１の探索窓内と第２の探索窓内のそれぞれの画像の平均輝度を算出して特徴量をそれぞれ抽出する。
【００２３】
類似度算出部１０７は、第１の探索窓と第２の探索窓の間の類似度を算出する。
【００２４】
結果出力部１０８は、類似度算出部１０７で求めた類似度が予め与えられた閾値θ（０≦θ≦１）を下回る場合に探索窓の位置、大きさ及び類似度を出力する。
【００２５】
信号探索装置は、図２０に示すように装置全体を制御するＣＰＵ（Central Processing Unit）等の制御部１１と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）１４やＲＡＭ１５（Random Access Memory）等の記憶部と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶部１６と、これらを接続するバス１７とを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、信号探索装置には、情報を表示する表示部１３と、ユーザの指示入力を受け付けるキーボードやマウス等の操作部１２と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）１８とが有線又は無線により各々接続される。
【００２６】
なお、この信号探索装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。すなわち、信号入力部１０１、検出器１０２、類似度選択部１０３、伸縮率算出部１０４、注目領域抽出部１０５、特徴抽出部１０６、類似度算出部１０７、結果出力部１０８は、上記のコンピュータに搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、信号探索装置は、上記のプログラムをコンピュータに予めインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、又はネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータに適宜インストールすることで実現してもよい。また、信号探索装置に設けた記憶部は、上記のコンピュータに内蔵又は外付けされたメモリ、ハードディスクもしくはＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒなどの記憶媒体などを適宜利用して実現することができる。
【００２７】
（２）探索窓の説明
図１ａ〜ｈは、本実施例に係る信号探索装置において、画像のエッジ検出で用いる第１の探索窓と第２の探索窓である。
【００２８】
図１ａは、注目領域抽出部１０５が有する第１の探索窓ｗ１と第２の探索窓ｗ２を、画像上に左右に隣接して配置して横方向のエッジを検出する。図１ｂから図１ｈは、図１ａを時計回り方向に少しずつ回転させたエッジを検出するための各探索窓を表す。
【００２９】
入力画像をグレースケール画像とし、探索窓ｗ１、ｗ２の平均輝度値をＬ１、Ｌ２、探索窓ｗ１、ｗ２の平均輝度値の差分値である輝度差分値をＤをとすると、Ｄ＝Ｌ１−Ｌ２となる。但し、０≦Ｌ１≦１、０≦Ｌ２≦１、０≦Ｄ≦１である。輝度は０〜１の値をとり、０が最も明るく、１が最も暗いとする。Ｄ＞θの場合にその位置をエッジとして検出する。但し、０≦θ≦１とする。
【００３０】
検出器１０２は、入力画像内を走査して、図１ａの探索窓の組を用いて、縦方向のエッジを検出する。なお、輝度差分値Ｄは、輝度差分値Ｄとは距離を意味している。すなわち、距離差分値Ｄは類似度の逆数であり、輝度差分値が大きくなると、類似度は小さくなる。
【００３１】
図２に示すように、信号探索装置は、上記処理を最初に最大の大きさを有する探索窓βｍａｘで行い、探索窓を縮小しながら処理を繰り返し、最小の大きさの探索窓βｍｉｎ以下になるまで行う。
【００３２】
（３）画像中に明らかにエッジがない場合に照合を省略して高速化する例
図５は、探索窓を多少縮小してもエッジを検出しないことが明らかな例を説明するための図である。
【００３３】
左側の第１の探索窓ｗ１の方が右側の第２の探索窓ｗ２より明るいエッジを検出するためのものとする。入力画像はこれとは逆に、左側より右側が明るいグラデーション画像である。このような場合では、各探索窓を多少縮小しても輝度差分値は大きく変化せず、エッジを検出しないという問題点がある。
【００３４】
（４）探索窓の縮小率を算出する方法
図６は、本実施例において、探索窓の縮小率の算出方法を説明する図である。
【００３５】
検出器１０２は、上記したように第１の探索窓ｗ１の方が第２の探索窓ｗ２より明るいエッジを検出するためのものである。縮小前の左右の探索窓の輝度値をＬ１、Ｌ２とすると、輝度差分値はＤ＝Ｌ１−Ｌ２となる。但し、Ｄ＞０とする。
【００３６】
各探索窓ｗ１、ｗ２を縮小した各探索窓ｗ１’、ｗ２’として、それらの輝度値をＬ１’、Ｌ２’とすると、輝度差分値はＤ’＝Ｌ１’−Ｌ２’となる。
【００３７】
縮小によって輝度差分値Ｄ’が最も減少する場合を考える。第１の探索窓ｗ１’に関して縮小によって第１の探索窓の範囲外となった全ての領域の輝度が１で、第２の探索窓ｗ２’に関して縮小によって第２の探索窓の範囲外となった全ての領域の輝度が０の場合に、輝度差分値Ｄ’が最も減少する。この場合の縮小率をαとすると、Ｌ１’、Ｌ２’、Ｄ’は以下の式で表せる。
【００３８】
Ｌ１’＝（Ｌ１／２−（１−α２）／２）／（α２／２）
＝（Ｌ１−１＋α２）／α２
Ｌ２’＝Ｌ２／α２
Ｄ’＝Ｌ１’−Ｌ２’
＝（Ｌ１−Ｌ２−１＋α２）／α２
＝（Ｄ−１＋α２）／α２
Ｄ’＞θを解くと以下の関係を導ける。
【００３９】
α２＞（１−Ｄ）／（１−θ）    ・・・（１）
縮小率αが、式１の範囲内であれば、エッジを検出し得ない。
【００４０】
縮小率αが１に近い場合には、探索窓の大きさがほとんど変化しないから、これを避けるために縮小率の下限Ａｆｉｘを定め、α＜Ａｆｉｘの場合にはα＝Ａｆｉｘとする。但し、Ａｆｉｘは固定値とし、０≦Ａｆｉｘ≦１とする。
【００４１】
現在の探索窓の大きさをβ（ｉ）とする。但し、ｉは繰り返し処理の回数を表し、ｉ≧１である。
【００４２】
β（１）はβｍａｘに初期化しておく。画像上の全ての位置において輝度差分値Ｄを求めて、Ｄ≧θとなる全ての位置（ｘ、ｙ）について、位置（ｘ，ｙ）、輝度差分値Ｄ、探索窓の大きさβ（ｉ）を出力する。但し、画像の大きさはｘ×ｙとする。それらの中でも最小の輝度差分値Ｄｍｉｎを求める。
【００４３】
次の探索窓の大きさをβ（ｉ＋１）とすると、β（ｉ＋１）は以下の式２で表せる。
【００４４】
β（ｉ＋１）＝β（ｉ）×α
＝β（ｉ）×√（（１−Ｄｍｉｎ）／（１−θ））・・・（２）
以上の処理を繰り返して探索窓の大きさがβ（ｉ）≦βｍｉｎになるまで繰り返す。
【００４５】
（５）従来方法
図８は、探索窓の伸縮率を固定幅ずつ変化させながら探索する従来方法を示す。
【００４６】
従来方法では、図５に示す探索窓の大きさを多少変化させても明らかに輝度値が閾値を下回らない場合でも探索する必要があり、無駄が多かった。また、信号の種類や性質によって変化幅を経験的に変更する必要もあった。
【００４７】
（６）本実施例の方法
図９に本実施例によって伸縮率を可変に変化させながら探索する様子を示す。
【００４８】
本実施例では、式２より求めた明らかに輝度差分値が予め与えられた閾値θを下回らない大きさの探索窓での照合を省略して、探索窓の大きさをスキップしながら探索を進める。
【００４９】
図４に以上の処理手順を説明するフローチャートを示す。
【００５０】
まず、ステップ４００において、伸縮率算出部１０４は、ｉを１に、探索窓の大きさβ（ｉ）をβｍａｘに、伸縮率αを１に、最小差分値Ｄｍｉｎを０に初期化する。
【００５１】
ステップ４０１において、伸縮率算出部１０４は、探索窓をα倍に縮小する。
【００５２】
ステップ４０２において、注目領域抽出部１０５は、入力画像上の位置（ｘ，ｙ）が第１の探索窓ｗ１と第２の探索窓ｗ１の重心になる位置に各探索窓ｗ１、ｗ２を配置する。特徴抽出部１０６は各探索窓ｗ１、ｗ２の平均輝度値Ｌ１、Ｌ２をそれぞれ算出する。類似度算出部１０７は両探索窓ｗ１、ｗ２の輝度差分値Ｄを、Ｄ＝Ｌ１−Ｌ２から算出する。但し、０≦Ｌ１≦１、０≦Ｌ２≦１、０≦Ｄ≦１である。
【００５３】
ステップ４０３において、結果出力部１０８は、Ｄ＞θの場合はその入力画像上の位置（ｘ，ｙ）をエッジとして検出し、両探索窓ｗ１、ｗ２の重心の位置（ｘ，ｙ）、輝度差分値Ｄ、探索窓の大きさβ（ｉ）を出力する。但し、０≦θ≦１である。
【００５４】
ステップ４０４において、類似度選択部１０３は、Ｄ＜Ｄｍｉｎの場合は最小輝度差分値Ｄｍｉｎ＝Ｄとして更新する。
【００５５】
ステップ４０５において、注目領域抽出部１０５、特徴抽出部１０６、類似度算出部１０７、結果出力部１０８、類似度選択部１０３は、以上の処理を入力画像上の全ての位置についてステップ４０２に戻って繰り返し行い、全て処理した場合はステップ４０６に進む。
【００５６】
ステップ４０６において、伸縮率算出部１０４は、閾値θと最小輝度差分値Ｄｍｉｎに基づいて式１によって伸縮率αを算出する。但し、αの下限値をＡｆｉｘとすると、α＜Ａｆｉｘの場合はα＝Ａｆｉｘとする。
【００５７】
ステップ４０７において、伸縮率算出部１０４が兼ねている繰り返し制御部は、各探索窓ｗ１、ｗ２の大きさをβ（ｉ＋１）＝β（ｉ）×αとして求めて更新し、ｉ＝ｉ＋１とインクリメントする。
【００５８】
ステップ４０８において、伸縮率算出部１０４が兼ねている繰り返し制御部は、各探索窓の大きさβ（ｉ）＜βｍｉｎの場合は処理を終了し、そうでない場合はステップ２０１に戻って検出処理を繰り返すように制御する。
【００５９】
（７）変更例１
また、本発明は上記実施例そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施例に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施例に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施例にわたる構成要素を適宜組み合わせてもよい。
【００６０】
変更例１について説明する。
【００６１】
実施例１では両探索窓ｗ１、ｗ２を縮小したが、両探索窓ｗ１、ｗ２を拡大しても拡大幅の伸縮率を導ける。拡大前の左右の探索窓をｗ１、ｗ２、輝度値をＬ１、Ｌ２とし、輝度差分値をＤとする。拡大後の左右の探索窓をｗ１”、ｗ２”、輝度値をＬ１”、Ｌ２”とし、輝度差分値をＤ”＝Ｌ１”−Ｌ２”とする。
【００６２】
拡大によって輝度差分値Ｄ”が最も減少する場合を考える。第１の探索窓ｗ１”に関して拡大によってはみ出した全ての領域の輝度が０で、第２の探索窓ｗ２”に関して拡大によってはみ出した全ての領域の輝度が１の場合に、輝度差分値Ｄ”が最も減少する。拡大率をαとすると、Ｌ１”、Ｌ２”、Ｄ”は以下の式で表せる。
【００６３】
Ｌ１”＝Ｌ１／α２
Ｌ２”＝（Ｌ２／２＋（α２−１）／２）／（α２／２）
＝（Ｌ２＋α２−１）／α２
Ｄ”＝Ｌ１”−Ｌ２”
＝（Ｌ１−Ｌ２−α２＋１）／α２
＝（Ｄ−α２＋１）／α２
Ｄ”＞θを解くと以下の関係を導ける。
【００６４】
α２＜（１＋Ｄ）／（１＋θ）    ・・・（３）
拡大率αが、式３の範囲内であれば、エッジを検出し得ない。
【００６５】
式１と式３をまとめると以下の式を導ける。
【００６６】
（１−Ｄ）／（１−θ）＜α２＜（１＋Ｄ）／（１＋θ）    ・・・（４）
縮小及び拡大を含めて、伸縮率αがこの範囲内であれば、エッジを検出し得ない。
【００６７】
なお、本明細書では、「伸縮」とは、拡大、又は、縮小を意味する。
【００６８】
（８）変更例２
変更例２について説明する。
【００６９】
実施例１では、最小輝度差分値Ｄｍｉｎを画像全体から求めたが、画像を複数に分割して、それぞれの領域毎に独立して探索してもよい。また、全ての位置を一つの領域とみなしてもよい。
【００７０】
すなわち、実施例１では、一点でも輝度差分値Ｄが閾値θを下回るとスキップすることができない。画像全体について最小輝度差分値Ｄｍｉｎを求めると、その可能性が高くなり、スキップできない場合が増える。画像は微小な領域では均一な変化をすることが多く、その場合は輝度差分値Ｄも似た値をとることが多い。そこで、画像を微小な領域に分割して、その最小輝度差分値Ｄｍｉｎを求めると、スキップできる可能性が高くなる。
【００７１】
また、前記分割した領域が、一つの点（例えば、一画素）でもよい。この場合には、実施例１のように、領域の中の最小輝度差分値Ｄｍｉｎを求めるのでなく、その位置における輝度差分値自身を用いて式２から伸縮率を算出する。
【００７２】
（９）変更例３
変更例３について説明する。
【００７３】
実施例１では、各探索窓ｗ１、ｗ２内の輝度の平均値を特徴量とし、探索窓間の輝度差分値を求めた。しかし、探索窓の大きさの伸縮量から類似度の変化の上限を算出できるものであれば、特徴量の算出方法と、類似度の算出方法は何でもよい。
【００７４】
例えば、各探索窓内の輝度値のヒストグラムを特徴量とし、各探索窓間のヒストグラム重なり率を類似度として求めても良い。
【００７５】
各探索窓ｗ１、ｗ２に含まれる画素の輝度値に関するヒストグラムをそれぞれＨ１＝（ｈ１１，ｈ１２，・・・，ｈ１ｎ）、Ｈ２＝（ｈ２１，ｈ２２，・・・，ｈ２ｎ）とする。但し、ｎは探索窓に含まれる画素数、すなわちヒストグラムの総度数を表す。縮小前後の左右の探索窓間の類似度をＳ、Ｓ’とする。類似度は以下の式で表されるヒストグラム重なり率で求める。
【数１】
2010218022.tif 000003
【００７６】
縮小によってＳが最も減少した場合を考える。縮小された各探索窓ｗ１’、ｗ２’から探索窓の範囲外となった全ての領域が類似度増加に寄与する場合にＳが最も減少する。縮小率をαとすると、類似度Ｓ’は以下の式で表せる。
【００７７】
Ｓ’＝（Ｓ−（１−α２）／２）／α２
＝（Ｓ−１＋α２）／α２
Ｓ’＜θを解くと以下の式５を導ける。
【００７８】
α２＞（１−２Ｓ）／（１−２θ）    ・・・（５）
一方、各探索窓ｗ１、ｗ２を拡大する場合は、拡大した各探索窓ｗ１”、ｗ２”によってはみ出した全ての領域が類似度増加に寄与しない場合にＳが最も減少する。拡大率をαとすると、拡大後の類似度Ｓ”は以下の式で表せる。
【００７９】
Ｓ”＝（Ｓ−（α２−１）／２）／α２
Ｓ”＜θを解くと以下の式６を導ける。
【００８０】
α２＜（１＋２Ｓ）／（１＋２θ）    ・・・（６）
式５と式６をまとめると以下の式７のようになる。
【００８１】
（１−２Ｓ）／（１−２θ）＜α２＜（１＋２Ｓ）／（１＋２θ）
・・・（７）
両探索窓の伸縮率αが式７を満たす範囲内であればエッジを検出し得ない。
【００８２】
また、類似度の変更例としては、上記輝度差分値と上記ヒストグラム重なり率を用いるに代えて、探索窓の大きさの伸縮量から類似度の変化の上限を算出できる式そのものを用いてもよい。具体的には、ａ＊の式を用いても良い。
【００８３】
（１０）変更例４
実施例１では、縮小時には伸縮率の下限、拡大時には伸縮率の上限のみを用いて信号探索処理を高速化した。この変更例４では、その両方を用いて信号探索処理を高速化する。実施例１と同様に、探索窓Ｗ（ｉ）をα倍して探索窓Ｗ（ｉ＋１）に縮小する場合を説明する。但し、探索窓Ｗ（ｉ）は探索窓ｗ１と探索窓ｗ２の組を表し、α＜１とする。
【００８４】
探索窓Ｗ（ｉ）の大きさがβ（ｉ）、輝度差分値がＤのときに、探索窓Ｗ（ｉ）より小さい探索窓Ｗ（ｉ＋１）’を設定した場合に、探索窓Ｗ（ｉ）’における伸縮率αｐの上限をどのように表せるかを考える。
【００８５】
探索窓Ｗ（ｉ）での輝度差分値はＤであるので、式１より以下の式７−１で表せる。
【００８６】
α２＞（１−Ｄ）／（１−θ）    ・・・（７−１）
一方、探索窓Ｗ（ｉ＋１）’の輝度差分値を仮に予測輝度差分値Ｄ’とすると、探索窓Ｗ（ｉ＋１）’から見た伸縮率の上限は式３より以下の式７−２のように表せる。
【００８７】
αｐ２＜（１＋Ｄ’）／（１＋θ）    ・・・（７−２）
探索窓Ｗ（ｉ）から見た探索窓の最小の大きさをβ（ｉ）’とすると、β（ｉ）’＝β（ｉ）×αと表せる。探索窓Ｗ（ｉ＋１）から見た探索窓の最大の大きさをβ”（ｉ）とすると、β（ｉ）”＝β（ｉ＋１）／αｐと表せる。β（ｉ）＜β（ｉ）”ならば探索を省略できる伸縮の区間が連続する。この式を解くと以下の式７−３を導ける。
【００８８】
β（ｉ＋１）’＜β（ｉ）×α／αｐ
＝β（ｉ）×√（（１−Ｄ）（１＋θ）／（１＋Ｄ’）（１−θ））
・・・（７−３）
式７−１は伸縮率の下限を利用した範囲であり、式７−２は伸縮率の上限を利用した範囲である。式７−３はこれらの両方を利用できるため、実施例１のように伸縮率の下限のみ利用したり、実施例１の変更例１のように伸縮率の上限のみ利用したりするのと比較すると、スキップできる伸縮率の範囲が広い。但し、探索窓Ｗ（ｉ＋１）’の大きさβ（ｉ＋１）’は式７−３を満たすものを選ぶ必要がある。
【００８９】
そこで、まず、予測輝度差分値Ｄ’を予測して、式７−３を満たす範囲内の値に探索窓Ｗ（ｉ＋１）の大きさβ（ｉ＋１）を設定する。なお、できるだけスキップ可能な伸縮幅を広げるために、β（ｉ＋１）は式７−３を満たす最小値付近に設定する。
【００９０】
例えば、伸縮率算出部１０４は、探索窓Ｗ（ｉ）から探索窓Ｗ（ｉ＋１）まで輝度差分値がＤのまま変わらないと仮定すると、β（ｉ＋１）は以下のように設定する。但し、Ｃｐは例えば１．１などの１に近い定数とする。
【００９１】
β（ｉ＋１）＝Ｃｐ×β（ｉ＋１）’
＝Ｃｐ×β（ｉ）×√（（１−Ｄ）（１＋θ）／（１＋Ｄ’）（１−θ））    ・・・（７−４）
次に、検出器１０２が、探索窓Ｗ（ｉ）を実際にβ（ｉ＋１）に縮小した探索窓Ｗ（ｉ＋１）を用いてエッジを探索し、類似度選択部１０３に実際の最小輝度差分値Ｄａを記憶する。この際に結果出力部１０８が出力する結果には未決定のマークを付けておく。
【００９２】
次に、類似度選択部１０３に記憶された実際の輝度差分値Ｄａを予測輝度差分値Ｄ’式７−３に代入してβ（ｉ＋１）’を算出し、以下の式７−５を満たすかどうかを、伸縮率算出部１０４は調べる。
【００９３】
β（ｉ＋１）＞β（ｉ＋１）’    ・・・（７−５）
式７−５を満たす場合は、結果出力部１０８が出力した未決定のマークを付けられた出力結果に決定のマークを付けて有効な結果とし、探索を進める。
【００９４】
式７−５を満たさない場合は、β（ｉ）’に１以上β（ｉ）／β（ｉ）’以下の固定値Ｃｂを乗じてβ（ｉ）に近づけて、式７−２を再び満たすか調べる処理を行う。この処理が「バックトラック」である。このバックトラックは、式７−２を満たすまで繰り返し行う。
【００９５】
以上の処理を繰り返すことによって、伸縮率の下限又は上限だけでなく、両方を同時に利用してさらに信号探索処理を高速化できる。
【００９６】
なお、拡大も同様に信号探索処理を行うことができる。すなわち、
β（ｉ＋１）’＞β（ｉ）×√（（１＋Ｄ’）（１−θ）／（１−Ｄ）（１＋θ））
・・・（７−６）
を満たすまでバックトラックを繰り返す。
【００９７】
また、類似度としては、輝度差分値に代えてヒストグラム重なり率を用いてもよい。
【００９８】
（１１）変更例５
変更例５について説明する。
【００９９】
変更例５では、複雑な形状の探索窓を用いた場合を説明する。
【０１００】
実施例１では、図６、図７に示したように、同じ大きさの長方形を左右に隣接させた第１の探索窓と第２の探索窓を用いて、正方形の中心について両探索窓を伸縮した。しかし、両探索窓は、図１０、図１１、図１２に示すように、各探索窓が２以上の領域を有していても良い。以下、順番に変形例について説明する。
【０１０１】
（１１−１）探索窓の第１の変形例
複雑な場合の探索窓の第１の変形例について図１０に基づいて説明する。
【０１０２】
図１０に示す両探索窓１６００〜１６０４は、中心点から放射状に伸びた線分によって両探索窓の領域が区切られ、かつ、中心点について点対象な場合である。
【０１０３】
両探索窓１６００〜１６０４は、中心点について両探索窓の大きさを伸縮しても、互いに重なることはない場合であり、実施例１と同じ式を用いて伸縮率を算出できる。
【０１０４】
（１１−２）探索窓の第２の変形例
複雑な場合の探索窓の第２の変形例について図１１に基づいて説明する。
【０１０５】
図１１に示す両探索窓１７００〜１７０４は、中心点から放射状に伸びた線分によって両探索窓の領域が区切られるが、中心点について点対称ではない場合である。
【０１０６】
両探索窓１７００〜１７０４は、中心点について両探索窓を伸縮しても、互いに重なることはない場合だが、各探索窓の領域の面積が異なる。
【０１０７】
（１１−２−１）平均輝度の場合
そのため、特徴量に平均輝度を用いる場合は、輝度の平均値を算出する段階で単位面積当たりの値に換算する。これにより、両探索窓の面積が異なっても実施例１と同じ式を用いて伸縮率を算出できる。
【０１０８】
（１１−２−２）ヒストグラム重なり率の場合
一方、特徴量にヒストグラム重なり率を用いる場合は、実施例１と式が異なる。両探索窓ｗ１、ｗ２の面積の比率がγとする。両探索窓ｗ１、ｗ２を縮小する場合に、縮小前後の類似度をＳ、Ｓ’とする。縮小された両探索窓ｗ１’、ｗ２’から探索窓の範囲外となった全ての領域が類似度増加に寄与する場合にＳが最も減少する。縮小率をα、ε＝ｍｉｎ（γ，１−γ）／ｍａｘ（γ，１−γ）、ｍｉｎ（・）は最小値を出力する関数、ｍａｘ（・）は最大値を出力する関数とすると、Ｓ’は以下の式で表せる。
【０１０９】
Ｓ’＝（Ｓ−（１−α２）／ε）／α２
＝（εＳ−１＋α２）／εα２
但し、両探索窓ｗ１、ｗ２の領域間の面積が異なるため、類似度は最大でもεであり、０≦Ｓ≦ε、０≦Ｓ’≦εである。
【０１１０】
Ｓ’＜θを解くと以下の式８を導ける。
【０１１１】
Ｓ’＞（１−εＳ）／（１−εθ）    ・・・（８）
但し、０≦θ≦εである。
【０１１２】
両探索窓ｗ１、ｗ２を拡大する場合は、拡大した両探索窓ｗ１”、ｗ”によってはみ出した全ての領域が類似度増加に寄与しない場合にＳが最も減少する。拡大率をα、拡大後の類似度をＳ”とすると、Ｓ”は以下の式で表せる。
【０１１３】
Ｓ”＝Ｓ／α２
Ｓ”＜θを解くと以下の式９を導ける。
【０１１４】
α２＜Ｓ／θ    ・・・（９）
式８と式９をまとめると以下のようになる。
【０１１５】
（１−εＳ）／（１−εθ）＜α２＜Ｓ／θ    ・・・（１０）
（１１−３）探索窓の第３の変形例
複雑な場合の探索窓の第３の変形例について図１２に基づいて説明する。
【０１１６】
図１２に示す両探索窓ｗ１、ｗ２は、中心点から放射状に伸びた線分によって領域が区切られておらず、かつ、中心点について点対称ではない場合である。
【０１１７】
両探索窓ｗ１、ｗ２は、中心点について両探索窓の大きさを伸縮すると、互いに重なり、両探索窓ｗ１、ｗ２の領域の面積が必ずしも同じではない場合である。
【０１１８】
このような探索窓ｗ１、ｗ２の場合は、探索窓の大きさを伸縮した際の類似度の上限を算出するときに、互いの重なり部分を増減させる必要がある。
【０１１９】
増減の方法は、探索窓の形状によって異なり、単調増加とは限らないが、探索窓の伸縮率と重なりの面積の関係は明白なので、類似度の上限を算出することは可能であり、式は異なるが実施例１を適用することが可能である。
【０１２０】
（１２）変更例６
上記実施例では、伸縮率算出部１０４が、繰り返し制御部を兼ねていたが、これに限らず、別体で設けてもよい。
【実施例２】
【０１２１】
本発明の実施例２の信号探索装置について図１３〜図１５に基づいて説明する。
【０１２２】
実施例１では画像のエッジ検出を例にとって説明した。画像は２次元の信号であるが、本発明はこれに限らず１次元の信号も処理できる。本実施例では、１次元の信号について説明する。本実施例では映像のショット境界検出を例にとって説明する。
【０１２３】
図１３は、映像のショット境界検出で用いる探索窓を示す。
【０１２４】
本実施例に係る信号探索装置の構成は、図３に示した実施例１に係る信号探索装置の構成と同一である。すなわち、信号入力部１０１、検出器１０２、類似度選択部１０３、伸縮率算出部１０４を有する。
【０１２５】
信号入力部１０１は映像信号（画像部分のみ）を入力して記憶する。
【０１２６】
検出器１０２は時系列は、映像の中の一つのフレーム画像から抽出した特徴量を並べた時系列信号上において、同じ長さの第１の探索窓ｗ１と第２の探索窓ｗ２を隣接して配置し、これを信号列上で走査して、類似度が予め与えられた閾値θ（０≦θ≦１）を下回る場合に探索窓の位置、大きさ及び類似度を出力する。
【０１２７】
類似度選択部１０３は、同じ大きさの探索窓について検出器１０２から出力される類似度を入力し、その中の最小の類似度を出力する。
【０１２８】
伸縮率算出部１０４は、探索窓の大きさの伸縮率を算出する。また、この伸縮率算出部１０４は、以上の処理をまず最大の探索窓の大きさβｍａｘで行い、続いて求めた伸縮率で探索窓を縮小しながら処理を繰り返し、最小の探索窓の大きさβｍｉｎ以下になるまで繰り返し行う繰り返し制御部の機能も兼ねている。
【０１２９】
検出器１０２は、注目領域抽出部１０５、特徴抽出部１０６、類似度算出部１０７、結果出力部１０８を有する。
【０１３０】
注目領域抽出部１０５は、時系列信号上のある位置に、同じ長さの第１の探索窓ｗ１と第２の探索窓ｗ２を隣接して配置し、それらの探索窓に含まれるフレーム画像を出力する。この際に伸縮率算出部１０３で指定された大きさの探索窓を用いる。
【０１３１】
特徴抽出部１０６は、第１の探索窓ｗ１内と第２の探索窓ｗ２内のそれぞれに含まれるフレーム画像上の全ての画素について平均輝度を算出して特徴量をそれぞれ抽出する。
【０１３２】
類似度算出部１０７は、第１の探索窓ｗ１と第２の探索窓ｗ２の間の類似度を算出する。
【０１３３】
結果出力部１０８は、類似度算出部１０７で求めた類似度が予め与えられた閾値θ（０≦θ≦１）を下回る場合に、輝度差分値が極小となる位置をショット境界として検出し、探索窓の位置、大きさ及び類似度を出力する。
【０１３４】
（１）縮小の処理
まず、信号入力部１０１には、映像としてグレースケール画像列が入力される。
【０１３５】
次に、特徴抽出部１０６は、両探索窓ｗ１、ｗ２に含まれるフレーム画像の画素の輝度値を全て平均した平均輝度値を特徴量として抽出する。
【０１３６】
次に、類似度算出部１０７は、両探索窓ｗ１、ｗ２間の輝度差分値を距離として求める。距離は類似度の逆数である。
【０１３７】
伸縮率算出部１０４の動作の概念について説明する。
【０１３８】
縮小前の両探索窓ｗ１、ｗ２の平均輝度値をＬ１、Ｌ２とし、縮小後をＬ１’、Ｌ２’とすると、縮小前後の探索窓ｗ１、ｗ２間の距離はＤ＝Ｌ１−Ｌ２、Ｌｄ’＝Ｌ１’−Ｌ２’となる。
【０１３９】
ここで、縮小によって距離Ｄが最も増加する場合の距離の上限値を考える。縮小された探索窓ｗ１’から探索窓の範囲外となった全ての領域の輝度が０で、探索窓ｗ２’から探索窓の範囲外となった全ての領域の輝度が１の場合にＤが最も増加する。縮小率をαとすると、Ｄ’は以下のように表せる。
【０１４０】
Ｌ１’＝（Ｌ１−１＋α）／α
Ｌ２’＝Ｌ２／α
Ｄ’＝Ｌ１’−Ｌ２’のため、Ｄ’は以下の式で表せる。
【０１４１】
Ｄ’＝（Ｌ１−Ｌ２−１＋α）／α
Ｄ’＞θを解くと以下の式１１の関係を導ける。
【０１４２】
α＞（１−Ｌ１＋Ｌ２）／（１−θ）    ・・・（１１）
（２）拡大の処理
以上では、両探索窓ｗ１、ｗ２を縮小したが、各探索窓ｗ１、ｗ２を拡大しても拡大幅の伸縮率を導ける。
【０１４３】
距離Ｄ＞θ、０≦θ≦１のときに、各探索窓ｗ１、ｗ２の拡大によって距離Ｄが最も増加する場合を考える。Ｌ１”に関して拡大によってはみ出した全ての領域の輝度が０で、Ｌ４’に関して拡大によってはみ出した全ての領域の輝度が１の場合に、距離Ｄが最も増加する。拡大率をαとすると、Ｌ１”Ｌ２”、Ｄ”は以下のように表せる。
【０１４４】
Ｌ１”＝Ｌ１／α
Ｌ２”＝（Ｌ２＋α−１）／α
Ｄ”＝Ｌ１”−Ｌ２”
＝（Ｌ１−Ｌ２−α＋１）／α
＝（Ｄ＋１）／α
Ｌｄ’＞θをαについて解くと以下の式１２の関係を導ける。
【０１４５】
α＜（１＋Ｄ）／（１−θ）    ・・・（１２）
（３）まとめ
式１１と式１２をまとめると以下のようになる。
【０１４６】
（１−Ｄ）／（１＋θ）＜α＜（１＋Ｄ）／（１−θ）
本実施例に係る信号探索装置の処理手順は、実施例１に係る信号探索装置の処理手順と同一であり、説明を省略する。
【０１４７】
（４）変更例１
実施例２の変更例１について説明する。
【０１４８】
実施例２では、輝度差分値と距離としたが、探索窓の大きさの変化量から類似度の変化の上限を算出できるものであれば、特徴量の算出方法と類似度の算出方法は何でも良い。
【０１４９】
例えば、探索窓に含まれるフレーム画像の平均輝度を求め、その平均輝度値のヒストグラムを特徴量とし、それらの間のヒストグラム重なり率を類似度としても良い。
【０１５０】
図１３に基づいて、このヒストグラム重なり率を用いて、探索窓ｗ１、ｗ２の縮小率を算出する方法を説明する。
【０１５１】
両探索窓ｗ１、ｗ２に含まれる特徴量のヒストグラムをＨ１＝（ｈ１１，ｈ１２，・・・，ｈ１ｎ）、Ｈ２＝（ｈ２１，ｈ２２，・・・，ｈ２ｎ）とする。但し、ｎは探索窓に含まれる特徴量の個数、すなわち、ヒストグラムの総度数を表す。両探索窓ｗ１、ｗ２の間の類似度Ｓをヒストグラム重なり率で算出する。
【０１５２】
縮小前後の類似度をＳ、Ｓ’とする。類似度が最も減少する場合を考える。縮小によってはみ出した全ての領域のヒストグラムが合致する場合にＳが最も減少する。この場合の縮小率をαとすると、Ｓ、Ｓ’の関係は以下のように表せる。
【０１５３】
Ｓ’＝（Ｓ−（１−α））／α
＝（Ｓ−１＋α）／α
Ｓ’＞θを解くと以下の式１３を導ける
α＞（１−Ｓ）／（１−θ）    ・・・（１３）
探索窓を拡大する場合は、拡大後の探索窓をｗ１”、ｗ２”、類似度輝度差分をＳ”とすると、拡大によってはみ出した全ての領域のヒストグラムが合致しない場合にＳが最も減少する。よってＳ”は以下のように表せる。
【０１５４】
Ｓ”＝Ｓ／α
Ｓ’＞θを解くと以下の式１４の関係を導ける。
【０１５５】
α＜Ｓ／θ    ・・・（１４）
式１３と式１４をまとめると以下の式１５のようになる。
【０１５６】
（１−Ｓ）／（１−θ）＜α＜Ｓ／θ    ・・・（１５）
（５）変更例２
実施例２の変更例２について説明する。
【０１５７】
実施例１では２次元の信号である画像に、実施例２では１次元の信号である画像列について説明したが、本発明はこれに限らずｎ次元の信号を処理できる。例えば、ＭＲＩなどで取得した３次元ボリューム信号や、画像列を時間方向に連結した時空間画像は３次元のデータである。
【０１５８】
距離（すなわち、類似度の逆数）を輝度差分値で算出する場合は、以下の式１６の関係を導ける。
【０１５９】
（１−Ｄ）／（１＋θ）＜αｎ＜（１−Ｄ）／（１−θ）    ・・・（１６）
類似度をヒストグラム重なり率で算出する場合は、以下の式１７の関係を導ける。
【０１６０】
（１−Ｓ）／（１−θ）＜αｎ＜Ｓ／θ    ・・・（１７）
【実施例３】
【０１６１】
本発明の実施例３の信号探索装置について図１５〜図１９に基づいて説明する。本実施例では、信号探索装置を顔検出装置に用いた場合を説明する。
【０１６２】
本実施例の顔検出装置は、Ｖｉｏｌａ−Ｊｏｎｅｓらの顔検出方法を用いる（Paul Viola, Michael J. Jones, 「Robust Real−Time Face Detection」 International Journal of Computer Vision, Vol.57, No.2, pp.137-154, 2004.参照）。すなわち、図１５に示すようなＨａｒｒ−ｂａｓｅｄ特徴を用いた弱識別器を検出器１０２として用い、この弱識別器を図１６に示すようなｍ段（但し、ｍ≧１である）に直列に接続し、識別器を構成する。
【０１６３】
Ｈａｒｒ−ｂａｓｅｄ特徴は、両探索窓ｗ１、ｗ２間の輝度値の差の符号を検出する。両探索窓ｗ１、ｗ２間の輝度差分値が正なら１、負なら０とする。図１５ａを例に取ると、第１の探索窓ｗ１の輝度が１５、第２の探索窓ｗ２の輝度が３の場合、特徴量は１５−３＞０だから１となる。この処理は図１６ａの第１段の弱識別器で行われ、輝度差分値が１の場合は、図１６ｂの第２段の弱識別器の判定に進む。
【０１６４】
２段目の弱識別器では、１段目の弱識別器とは異なるＨａｒｒ−ｂａｓｅｄ特徴を用いる。
【０１６５】
この処理を画像上の全ての位置について繰り返して、全ての弱識別器で１と判定された位置を顔として検出する。この処理は、まず大きさβｍａｘの両探索窓ｗ１、ｗ２で行い、少しずつ両探索窓ｗ１、ｗ２の大きさをα倍に縮小しながら、両探索窓ｗ１、ｗ２が大きさβｍｉｎになるまで検出を繰り返す。
【０１６６】
この検出器１０２では両探索窓ｗ１、ｗ２間の輝度差分値Ｄの符号のみを用いる。式４にθ＝０を代入すると以下の式１８を導ける。
【０１６７】
１−Ｄ＜α２＜１＋Ｄ    ・・・（１８）
（１）顔検出方法
以下に実施例１を適用して顔検出方法を説明する。
【０１６８】
顔検出装置は、図１７に示すように、探索したい探索領域を設定し、この探索領域の中で第１の探索窓ｗ１、第２の探索窓ｗ２を用いて顔を探索する。また、顔検出装置は探索枠を有している。この探索枠は、各段の両探索窓ｗ１、ｗ２と、各段の探索窓ｗ１、ｗ２をどのように配置するかという位置情報も有している。
【０１６９】
最初に、入力画像を均等に１６分割する。そして、それぞれの分割領域毎に、次の処理を行う。
【０１７０】
例えば、第１の分割領域において、図１６ａに示した第１段の両探索窓ｗ１、ｗ２を用いて輝度差分値Ｄ（１）を算出し、伸縮率α（１）を求める。この両探索窓は図１ａに示したエッジ検出のための第１の探索窓ｗ１と第２の探索窓ｗ２と同じ形状である。例えば、図１６に示すように、この第１段の両探索窓ｗ１、ｗ２が、両目を探索する検出器１０２とする。なお、この第１段の両探索窓ｗ１、ｗ２の中心Ｐ１は、図１８に示すように、第１の分割領域の左上を原点Ｐ０とすると、斜め下にずれている。
【０１７１】
式１８よりα（１）の取り得る範囲は以下の式１９のように表せる。
【０１７２】
１−Ｄ（１）＜α（１）２＜１＋Ｄ（１）    ・・・（１９）
α（１）＞Ａｆｉｘの場合は、エッジが検出されないとして、第１段の両探索窓ｗ１、ｗ２の伸縮率αを式１９の下限値に設定して、α＝√（１−Ｄ（１））とし、第１段の両探索窓ｗ１、ｗ２を縮小して、第１の分割領域において探索を継続する。なお、ここでは伸縮率を最大にするためにαを式１９の下限値に設定したが、αに設定する値は式１９を満たす範囲ならばどの値でも良い。
【０１７３】
α（１）≦Ａｆｉｘの場合は、図１６ｂに示した第２段の両探索窓ｗ１、ｗ２を用いて輝度差分値Ｄ（２）を算出し、伸縮率を求める。
【０１７４】
図１７に示すように、この検出器１０２では両探索窓ｗ１、ｗ２をそのまま用いるのではなく、探索枠は、第２段の両探索窓ｗ１、ｗ２をどの位置に配置するかという情報も持つ。そこで、第１段の両探索窓ｗ１、ｗ２の位置と第２段の両探索窓ｗ１、ｗ２の位置の相対的な差分だけ、第１段の探索領域をずらした範囲で類似度を算出する必要がある。第２段の両探索窓ｗ１、ｗは、例えば、図１６に示すように左頬を探索するものとすると、両目を探索する第１段の両探索窓ｗ１、ｗ２との位置関係は明確である。すなわち、第１段の両探索窓ｗ１、ｗ２の探索領域より斜め下の位置を探索領域にすると、効率よく左頬の領域を探索できる。
【０１７５】
図１８に、第１〜３段の両探索窓ｗ１、ｗ２の位置を示す。Ｐ１、Ｐ２、Ｐ３は第１段、第２段、第３段の両探索窓ｗ１、ｗ２の中心を表す。第２段の両探索窓ｗ１、ｗ２を用いた探索では図１９に示すようにずらした探索領域で輝度差分値Ｄ（２）を算出し、伸縮率α（２）を求める。
【０１７６】
この検出器１０２では、第１段の輝度差分値Ｄ（１）は探索領域内で全て求めるが、第２段の輝度差分値Ｄ（２）は第１段でＤ＜０となった位置についてしか求めない。また、第２段による探索領域のうち、第１段による探索領域に含まれない位置についても第２段の輝度差分値Ｄ（２）は求まっていない。そこで、第２段の両探索窓ｗ１、ｗ２による伸縮率を算出する際には、これらの輝度差分値が求まっていない位置でも新たに輝度差分値を求める必要がある。
【０１７７】
α（２）＞Ａｆｉｘの場合は、α＝√（１−Ｄ（２））に設定し、第２段の両探索窓ｗ１、ｗ２を縮小して、第１の分割領域の探索を継続する。
【０１７８】
α（２）≦Ａｆｉｘの場合は、図１６ｃに示した第３段の両探索窓ｗ１、ｗ２を用いて輝度差分値Ｄ（３）を算出し、伸縮率α（３）を求める。この第３段の両探索窓ｗ１、ｗ２が、鼻を探索する検出器１０２とする。
【０１７９】
以上の処理を繰り返してｍ段全てについて処理を繰り返し、最終的にα（ｍ）≦Ａｆｉｘとなった場合は、α＝Ａｆｉｘに設定し、両探索窓ｗ１、ｗ２を縮小して探索を継続する。
【０１８０】
このように、本実施例では、Ｖｉｏｌａ−Ｊｏｎｅｓらの顔検出方法を適用すると、探索窓の伸縮方向についてもれなく探索でき、顔らしくない領域については探索をスキップできるので信号探索処理を高速化が期待できる。
【符号の説明】
【０１８１】
１０１    信号入力部
１０２    検出器
１０３    類似度選択部
１０４    伸縮率算出部
１０５    注目領域抽出部
１０６    特徴抽出部
１０７    類似度算出部
１０８    結果出力部
【図１】
2010218022.tif 000004
【図２】
2010218022.tif 000005
【図３】
2010218022.tif 000006
【図４】
2010218022.tif 000007
【図５】
2010218022.tif 000008
【図６】
2010218022.tif 000009
【図７】
2010218022.tif 000010
【図８】
2010218022.tif 000011
【図９】
2010218022.tif 000012
【図１０】
2010218022.tif 000013
【図１１】
2010218022.tif 000014
【図１２】
2010218022.tif 000015
【図１３】
2010218022.tif 000016
【図１４】
2010218022.tif 000017
【図１５】
2010218022.tif 000018
【図１６】
2010218022.tif 000019
【図１７】
2010218022.tif 000020
【図１８】
2010218022.tif 000021
【図１９】
2010218022.tif 000022
【図２０】
2010218022.tif 000023