(57)【要約】コンピュータ実行方法は、時系列データ、画像及びボリュームデータ等のサンプルされたデータから統合ヒストグラムを抽出する。まず、現実の信号からサンプルのセットを獲得する。このサンプルのセットを所定順序でスキャンする。それぞれの現サンプルに対し、当該現サンプルのヒストグラムと先にスキャンされたサンプルの統合ヒストグラムとを統合する統合ヒストグラムを構成する。
2008530627.tif 000002
【特許請求の範囲】
【請求項１】
現実の信号からサンプルのセットを獲得すること、
所定の順序で前記サンプルのセットをスキャンすること、
及び
現サンプル各々に対し、前記現サンプルのヒストグラムと先にスキャンされたサンプルの統合ヒストグラムとを統合した統合ヒストグラムを構成すること
を含む、サンプルされたデータから統合ヒストグラムを抽出するコンピュータ実行方法。
【請求項２】
前記スキャンは、左から右、その後上部から下部の順序で行われる
請求項１記載の方法。
【請求項３】
前記サンプルのセットは、ｄ次元アレイであり、各次元の値の範囲は、関連するｋ次元テンソルでＮｄである
請求項１記載の方法。
【請求項４】
前記統合ヒストグラムは、複数のビンを含み、各ビンのサイズは整数である
請求項１記載の方法。
【請求項５】
前記サイズは、２のべき乗である
請求項４記載の方法。
【請求項６】
前記サンプルのセットは、１次元時系列である
請求項１記載の方法。
【請求項７】
前記サンプルのセットは、２次元グレーレベル画像である
請求項１記載の方法。
【請求項８】
前記サンプルのセットは、カラー画像である
請求項１記載の方法。
【請求項９】
前記サンプルのセットは、ボリュームデータである
請求項１記載の方法。
【請求項１０】
前記サンプルのセットは、ビデオであり、
前記統合ヒストグラムから類似度マップを構成することをさらに含む
請求項１記載の方法。
【請求項１１】
前記類似度マップを使用して前記画像のオブジェクトが検出される
請求項１０記載の方法。
【請求項１２】
前記類似度マップを使用して前記画像のテクスチャが検出される
請求項１０記載の方法。
【請求項１３】
前記統合ヒストグラムを空間的に結合することをさらに含む
請求項１記載の方法。
【請求項１４】
前記統合ヒストグラムを階層的に結合することをさらに含む
請求項１記載の方法。
【請求項１５】
前記統合ヒストグラムをモデルに従って結合することをさらに含む
請求項１記載の方法。
【請求項１６】
前記サンプルのセットは、画像であり、
デカルト空間におけるコーナ点に従って前記画像の目標領域を指定すること、
前記目標領域に対する前記統合ヒストグラムを確定すること、
及び
前記画像の前記目標領域のサイズに対して前記統合ヒストグラムを正規化して正規化ヒストグラムを取得することをさらに含む
請求項１記載の方法。
【請求項１７】
前記画像における最大目標領域に対応する右下コーナ点の前記統合ヒストグラムのビン値を、最小目標領域に対応する前記画像の左上コーナ点の前記統合ヒストグラムのビン値に加算すること、
及び
右上コーナ点及び左下コーナ点の統合ヒストグラムの前記ビン値を減算することをさらに含む
請求項１６記載の方法。
【請求項１８】
前記正規化ヒストグラムと前記目標領域の前記統合ヒストグラムとの距離を確定することをさらに含む
請求項１７記載の方法。
【請求項１９】
前記サンプルのセットは、画像であり、
前記画像の強度、色、テクスチャ、勾配、動き、向き、テンプレートマッチング及び画像フィルタ応答の前記統合ヒストグラムを結合することによってより高レベルの特徴を構成することをさらに含む
請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、現実の信号（real-world signals）のデータサンプルを表すとともに探索することに関し、特に、データサンプルから抽出されたヒストグラムを用いて表すとともに探索し、それによってオブジェクトを検出することに関する。
【背景技術】
【０００２】
図１に示すように、ヒストグラム１００は「ビン」１０１のアレイである。各ビンは、サンプルされたデータセットの値の範囲１０２に対応する。ビンは、特定の範囲におけるサンプル値の発生の頻度１０３を「カウント」する。言い換えれば、ヒストグラムは、データセットにおけるサンプルの頻度分布を表す。
【０００３】
たとえば、サンプルされたカラー画像のヒストグラムは、各ビンにおける同じ色値を有する画素の数を「カウントする」。したがって、そのヒストグラムは、サンプルされたデータセットから非負実数＋Ｒのセットへのマッピングである。
【０００４】
確率的観点から見ると、ヒストグラムの正規化により、データセットの確率密度関数に似た離散関数がもたらされる。ヒストグラムを使用して、分布、拡散及び異常値等、データセットの統計的特性を確定することができる。
【０００５】
ヒストグラムは、オブジェクトベースのインデキシング及び探索（C.Carson、M.Thomas、S.Belongie、J.M.Hellerstein及びJ.Malik著、「Blobworld: A system for region-based image indexing and retrieval」（Proceedings of ICVS, 1999）及びJ.Huang、S.Kumar、M.Mitra、W.J.Zhu及びR.Zabih著、「Image indexing using color correlograms」（Proceedings of CVPR, 1997））、画像セグメント化（D.A.Forsyth及びJ.Ponce著、「Computer Vision: A Modern Approach」(Prentice Hall, 2002）及びS.Ruiz-Correa、L.G.Shapiro及びM.Meila著、「A new paradigm for recognizing 3-D object shapes from range data」（Proceedings of CVPR, 2003））、オブジェクト検出（C.Papageorgiou、M.Oren及びT.Poggio著、「A general framework for object detection」（Proceedings of ICCV, 1998）及びオブジェクト追跡（D.Comaniciu、V.Ramesh及びP.Meer著、「Real-time tracking of nonrigid objects using mean shift」（Proceedings of CVPR, 2000））等、多くのコンピュータビジョンアプリケーションにおいて使用されている。
【０００６】
顔検出器について、P.Viola及びM.Jonesにより、「Robust real-time face detection」（Proceedings of ICCV, page II: 747, 2001）において述べられている。Viola他によって述べられているように、画像にわたってスキャンされる矩形窓内で、あり得る窓の各々に対して加法演算子を繰り返すことなく線形時間で強度値の合計を求めることが可能である。各矩形合計に対し、別個の矩形にわたって複数回合計を求めるために一定の数の演算が必要である。これにより、累積強度画像又は積分強度画像が画定され、そこでは、各画素は、その画素自体の値を含む画素の左方の且つ上方のすべての値の合計を保持する。積分強度画像を、画像全体に対し、一画素につき４回のみの算術演算によって求めることができる。スキャンは、画像の左上隅の画素における窓で開始し、まず右へ進み次に下方に進む。関数により、積分画像における現画素の値が、現画素の上方の且つ左方のすべての画素の強度の合計から左上の画素値を減算したものとして求められる。矩形における画像関数の合計を、別の４つの算術演算を、境界において適当に変更して用いることによって確定することができる。このように、線形量の演算により、任意の矩形にわたる画像関数の合計を、線形時間で求め、それによって積分画像を構成することができる。
【０００７】
不都合なことに、従来のヒストグラムを抽出するとともに探索することは時間がかかる。全数探索のみが、大域的最適解を提供することができる。勾配降下及びアプリケーション特有の制約等、次善最適な探索により、探索の時間を短くすることができる。しかしながら、オブジェクト検出及びオブジェクト追跡等の最適な解決法に依存するコンピュータビジョンアプリケーションは、ヒストグラム抽出において理論的ブレークスルーを必要とする。
【０００８】
従来、全数探索では、特定のヒストグラムとすべてのあり得る目標領域のヒストグラムとの間のすべての距離を測定することが必要である。このプロセスには、すべてのあり得る点、たとえば画素に中心を置く領域に対してヒストグラムを生成する必要がある。異なるスケール、すなわち異なる目標領域スケール（サイズ）で探索が実行される場合、プロセスは、スケールの数と同程度の回数繰り返される。
【０００９】
図２は、従来のヒストグラム探索の擬似コード２００を示す。
【００１０】
今のところ、この従来の手法が、ヒストグラムベースの探索に対する大域的最適解を見つけることを保証する唯一の既知の解決法である。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ヒストグラム抽出及びヒストグラムの探索の速度を桁違いに向上させることが望まれる。
【００１２】
本発明は、デカルトサンプルされたデータ空間におけるあり得る目標領域から統合ヒストグラム（integral histogram）を抽出し、且つ抽出されたヒストグラムを探索する方法を提供する。
【課題を解決するための手段】
【００１３】
本発明は、データ点の空間的配置を利用し、原点から開始して所定のスキャンラインに沿って残りの点を通ってスキャンすることにより、統合されたヒストグラムを再帰的に伝播する。４つのコーナ点において統合ヒストグラムに対しインタセクションを行うことにより、矩形領域のヒストグラムが確定される。各ステップにおいて、先に処理された隣接する点における統合ヒストグラムの値を使用することにより、単一のビンが更新される。統合ヒストグラムが伝播された後、任意の目標領域のヒストグラムを、わずかな回数の単純な算術演算を使用して構成することができる。
【発明の効果】
【００１４】
本発明による方法は３つの明確な利点を有する。本方法は、従来の手法と比較すると極めて高速である。本方法は、大部分の複雑なビジョンアプリケーションに対して今まで実際的でなかった、リアルタイムでの全数探索プロセスを採用することができる。本方法を、その利点を犠牲にすることなく、より高いデータ次元、一様及び非一様のビット形成、並びに複数の目標スケールに拡張することができる。また、本方法によって、ヒストグラム内の空間情報の統合を可能にするより高レベルのヒストグラム特徴を記述することも可能になる。
【００１５】
異なる数のビン、データ次元及びデータ構造での多数の分析により、本発明による統合ヒストグラム法が、必要な演算の回数を大幅に減少させることが分かった。
【００１６】
本方法を使用して、ビデオのオブジェクトをリアルタイムに検出することができる。
【発明を実施するための最良の形態】
【００１７】
統合ヒストグラム
本発明による統合ヒストグラムは、再帰的伝播法によってサンプルされたデータから抽出される。本方法は、デカルト空間で作用する。本方法を、任意の次元のデータ空間及び任意のテンソル表現に拡張することができる。
【００１８】
ｘ→ｆ（ｘ）等の関数ｆは、ｄ次元実数値デカルト空間
【００１９】
【数１】
2008530627.tif 000003
【００２０】
において定義される。ここで、ｘ＝［ｘ１，…，ｘｄ］は、空間におけるサンプル点である。関数ｆは、ｋ次元テンソルにマップし、すなわちｆ（ｘ）＝［ｇ１，…，ｇｋ］である。ｄ次元データ空間は、範囲Ｎ１，…，Ｎｄ内に制限され、すなわち０≦ｘｉ≦Ｎｉである。
【００２１】
統合ヒストグラムＨ（ｘ，ｂ）は、点ｘ０，ｘ１，…のスキャンラインに沿って
【００２２】
【数２】
2008530627.tif 000004
【００２３】
であるように定義される。ここで、
【００２４】
【数３】
2008530627.tif 000005
【００２５】
は現在点の対応するビンを与え、∪は、以下のように定義される和集合演算子である。
【００２６】
ヒストグラムＨ（ｘ，ｂ）のビンｂの値は、ヒストグラムの先にスキャンされた点のビン値の合計、すなわちｐ＜ｘである間のすべての
【００２７】
【数４】
2008530627.tif 000006
【００２８】
の合計に等しい。言い換えれば、Ｈ（ｘ，ｂ）は、原点と現在点との「間の」より広いデカルト領域のヒストグラムであり、０≦ｐ１≦ｘ１、０≦ｐ２≦ｘ２、…等である。
【００２９】
なお、Ｎ＝［Ｎ１，…，Ｎｄ］が空間の境界であるため、Ｈ（Ｎ，ｂ）は、空間におけるすべてのデータ点のヒストグラムに等しい、ということに留意されたい。
【００３０】
したがって、統合ヒストグラムを、初期条件Ｈ（０）＝０、すなわち、ヒストグラムのビンのすべてが最初は空である、という条件を使用して
【００３１】
【数５】
2008530627.tif 000007
【００３２】
として再帰的に取得することができる。
【００３３】
そして、目標領域Ｔ＝［ｐ−，ｐ＋］（ただしｐ−＜ｐ＋）のヒストグラムは、
【００３４】
【数６】
2008530627.tif 000008
【００３５】
として領域の境界点における伝播された統合ヒストグラム値を求め、これは、２−Ｄデータセットの場合
【００３６】
【数７】
2008530627.tif 000009
【００３７】
となる。なお、領域は、
【００３８】
【数８】
2008530627.tif 000010
【００３９】
によって境界が決められることに留意されたい。
【００４０】
従来のヒストグラム構成とは対照的に、本発明による統合ヒストグラム法は、あり得る領域の各々に対してヒストグラム抽出を繰り返さない。
【００４１】
図３は、本発明によるサンプルされたデータから統合ヒストグラムを抽出する方法の擬似コード３００を示す。
【００４２】
あり得る点各々に対し、且つ目標点の各々に対し、現在値を取得し、ビンを見つけ、ビン値を増大させる。そして、あり得るスケールの各々に対し、あり得る点の各々に対し、且つビンの各々に対し、先のビンとのインタセクションを計算し、正規化し、ヒストグラム間の距離を計算する。
【００４３】
２−Ｄデータ、たとえばＮ１×Ｎ２グレーレベル画像の場合、パラメータはｄ＝２、ｋ＝１であり、データ空間は、垂直画像サイズＮ１及び水平画像サイズＮ２内に制限される。
【００４４】
図４に示すように、画像４０２のスキャンライン４０１を画素４０３に、左から右、且つ上部から下部の順序で割り当てることができる。
【００４５】
図５及び図６に示すように、再帰を、すべてのｂ＝１，…，Ｂに対し
【００４６】
【数９】
2008530627.tif 000011
【００４７】
として表すことができる。
【００４８】
この伝播は、３つの先のヒストグラム５０１〜５０３のビンのインタセクションを使用することにより、現データ点（画素）Ｉ（ｘ，ｙ）５０４に属するビンの値を増分させて、現在点のヒストグラムビンを左、上部及び左上それぞれに割り当てる。
【００４９】
以下の節は、従来のヒストグラムと比較した場合の統合ヒストグラムを抽出する計算コストを分析する。この分析は、統合ヒストグラム法が従来のヒストグラム抽出方法より著しく優れていることを劇的に示すため含まれる。
【００５０】
整数データ
この場合、サンプルされた入力データはｄ次元アレイであり、各次元の値の範囲は、関連するｋ次元テンソルでＮｄである。ヒストグラムは、各次元に対してＢ個の同一のビンを含むｋ次元である。ビンサイズは整数である。さらに、ヒストグラムの目標窓は、目標オブジェクトＭ１×…×Ｍｄのサイズに対応する。
【００５１】
従来のヒストグラムマッチングアルゴリズムでは、ｄ次元入力テンソルにおいて現在値を求めるために７ｄ−３＋ｋ回の演算が必要であり、対応するビンインデックスを確定するために７５ｋ回の演算が必要であり、ビン値を増大させるために１回の演算が必要である。ビンインデックスを、浮動小数点乗算により、その後、浮動・整数変換によって求めることができる。このオプションのコスト（１０９ｋ）は、除算自体（７５ｋ）より高い。目標窓におけるＭ１×…×Ｍｄ点がすべてが処理された後、ヒストグラムビンは、点の数によって正規化され、これにはＢｋ回の浮動小数点乗算、したがって相対コストに関して４Ｂｋ回の演算が必要である。これらの演算は、Ｎ１×…×Ｎｄ回のヒストグラムマッチングの各々に対して繰り返される。
【００５２】
【数１０】
2008530627.tif 000012
【００５３】
なお、異なる窓サイズの組合せＭｓ＝１，…，Ｓｓ（ただし、Ｓｓは次元ｓに対する範囲の最大サイズを表す）の場合、上記プロセスが繰り返され、従来の方法の場合の演算の総数は
【００５４】
【数１１】
2008530627.tif 000013
【００５５】
となる。
【００５６】
統合ヒストグラムで伝播のために必要な演算の回数は、テンソル値の現在値を取得するコスト（７ｄ−３＋ｋ）、対応するビンのインデックスを見つけるコスト（７５ｋ）、及び取得されたビン値を累積するコストに加えて（これがデータ空間のすべての点に対して繰り返される）、３（７ｋ−３）＋２ｋ＝２３ｋ−９回である。
【００５７】
そして、ヒストグラムを抽出するために必要な演算の数は、
【００５８】
【数１２】
2008530627.tif 000014
【００５９】
である。
【００６０】
ヒストグラムインタセクションは、４（７ｋ−３）＋３ｋ＝３１ｋ−１２回の演算を使用する。結果を正規化するには、各ヒストグラムに対してＢｋ回の浮動小数点除算、すなわち４Ｂｋ回の演算を使用する。そして、Ｎ１×…×Ｎｄヒストグラムのすべて及びあり得る探索窓次元マッチングのすべてのコストは、
【００６１】
【数１３】
2008530627.tif 000015
【００６２】
のみである。
【００６３】
従来の手法の計算負荷対統合ヒストグラム法の計算負荷の比は、
【００６４】
【数１４】
2008530627.tif 000016
【００６５】
である。
【００６６】
浮動小数点データ
浮動小数点データでは、７５ｋ〜１００ｋの各点についての各除算に対する演算の数が増大する。ビン値増分コストは、先には１であったが４となる。従来の手法の総コストは、
【００６７】
【数１５】
2008530627.tif 000017
【００６８】
となる。
【００６９】
統合ヒストグラム法の場合、ビンインデックスを見つけるステップの複雑性は１００ｋまで増大する。伝播段階では、加算のコストは２ｋから８ｋまで増大する。インタセクション計算では、コストは
【００７０】
【数１６】
2008530627.tif 000018
【００７１】
となる。
【００７２】
２のべき乗のビンサイズ
なお、２のべき乗であるビンサイズを使用することにより最適化が可能であることに留意されたい。ビット単位のシフト演算子を使用することにより、コストの一部で除算演算子を達成することができる。たとえば、６４で除算する代りに、数を６ビット右方へシフトさせることができる。ビンインデックスの計算は、平均して、且つビットがシフトする数に応じて７５ｋから２ｋまで下がる。そして、従来の手法を使用する整数データの演算の総数は
【００７３】
【数１７】
2008530627.tif 000019
【００７４】
となる。
【００７５】
ビンサイズが２のべき乗である統合ヒストグラムの場合、総数は
【００７６】
【数１８】
2008530627.tif 000020
【００７７】
まで下がる。
【００７８】
正規化なしのマッチング
アプリケーションによっては、目標オブジェクトは、スケーリングなしにそのオリジナルサイズで、又は２のべき乗によるダウンサンプリングに対応する１／２サイズのスケーリングファクタ、すなわち１／２サイズ、１／４サイズ等で、探索される。こうした場合、同じサイズのマッチングに対してヒストグラム正規化は必要でないため、さらなる計算の低減が可能であり、また、ビット単位右シフト演算子を使用して除算を行うことができるため、より小さい１／２サイズに対して大幅な低減が達成される。２−ｓのスケーリングファクタ（ただし、ｓ＝０はスケーリングのないことを表し、ｓ≦１はダウンサイジングを表す）の場合、整数データを用いる従来の手法の必要な計算は、
【００７９】
【数１９】
2008530627.tif 000021
【００８０】
となる。
【００８１】
統合ヒストグラムのコストは、
【００８２】
【数２０】
2008530627.tif 000022
【００８３】
となる。
【００８４】
なお、上記コストに加えて、従来の手法は別の重要な欠点を有することに留意されたい。各計算後、ヒストグラムアレイ値は新たに初期化される。これによってさらなるオーバヘッドがもたらされる。
【００８５】
アプリケーション
時系列データ
長さＭ及び総ビン数Ｂを有するヒストグラムの音声信号の時系列等の１Ｄ−サンプルされたデータ、及び最大Ｓデータ点の目標サイズ範囲の場合、上記分析のパラメータはｄ＝１及びｋ＝１となる。
【００８６】
この比は
【００８７】
【数２１】
2008530627.tif 000023
【００８８】
となる。
【００８９】
驚くべきことに、統合ヒストグラムは、従来の方法に比べて、最大３．５×１０４倍、時系列サンプルされたデータの処理時間を向上させる。たとえば、３２ビンヒストグラムで１０４点を含む時系列データを探索するために必要な一般的なタスクは、従来の方法より３，３４７倍高速である。
【００９０】
グレーレベル画像
Ｍ１×Ｍ２グレーレベル画像及び探索窓サイズ範囲Ｓ１、Ｓ２である場合、上記分析のパラメータはｄ＝２及びｋ＝１となり、比は
【００９１】
【数２２】
2008530627.tif 000024
【００９２】
となる。
【００９３】
グレーレベル監視ビデオ及びモノクロ航空画像を使用するビジョンアプリケーションでは、２次元データが非常に一般的である。たとえば、問題は、１６ビンのヒストグラムを使用して、３つの異なる階層的解像度、たとえば６４×６４、３２×３２及び１６×１６で６４×６４目標パターンを見つけることである。本発明による方法は、２，４３５倍高速に目標パターンを見つける。上述したような他の最適化では、プロセス全体は、従来の方法に比べて６×１０４倍速度を上げることができる。
【００９４】
カラー画像
各点がテンソル形式で３つの色値を有する３Ｄヒストグラムを用いるカラー画像の場合、パラメータはｄ＝２及びｋ＝３になる。探索が、画像次元においてＳ１、Ｓ２のテンプレート窓サイズで行われる場合、比は
【００９５】
【数２３】
2008530627.tif 000025
【００９６】
である。
【００９７】
４ビットで符号化される各カラーチャネルに対する、すなわち１６ビンのヒストグラムを使用して２０スケールで１００×１００オブジェクトモデルを探索する標準モデルマッチングタスクの場合であっても、プロセスは１４６倍加速される。ビンの数及び目標サイズに応じて、最大７×１０５まで節約することができる。
【００９８】
ボリュームデータ
ボリュームデータの場合、パラメータはｄ＝３及びｋ＝１である。特徴選択の問題及び分類の問題において、より高次元の空間における探索が必須である。対応する比は
【００９９】
【数２４】
2008530627.tif 000026
【０１００】
である。
【０１０１】
統合ヒストグラム法は、より高い次元でははるかに有利となる。最大１５×１０７まで節約することができる。１００ビンのヒストグラムを使用してそのオリジナルサイズ（Ｓ＝１）で探索された１０３×１０３×１０３目標ボリュームを探索するために、本発明は、驚くべきことに１．６×１０８倍の向上を達成することができる。
【０１０２】
オブジェクト検出
図７に示すように、オブジェクト検出アプリケーションは、入力として画像７０１を取得する。目標は、交通標識７０２である。目標オブジェクトの探索には、各チャネルに対して１５ビンのカラーヒストグラムを使用する。統合ヒストグラムを使用して、同様の類似度マップ７０３を構成する。これは、従来の類似度マップに類似する。しかしながら、従来の方法では、従来の３．２Ｇｈｚプロセッサで２分間必要であるのに対し、統合ヒストグラム法は６３ミリ秒で実行し、およそ２０００倍向上する。
【０１０３】
テクスチャ検出
図８に示すように、テクスチャ検出アプリケーションに対して統合ヒストグラム法を使用することも可能である。このアプリケーションは、入力としてテクスチャ８０１の画像を取得する。タスクは、テクスチャ８０２及び８０３を検出することである。検出されたテクスチャは、対応する類似度マップ８０４及び８０５に示される。統合ヒストグラムは、勾配の向きの２４ビンのヒストグラムを有する。統合ヒストグラム法では８８ミリ秒かかり、従来の方法では、５分を越える処理時間が必要であり、３４００倍の増大である。なお、こうした単純なヒストグラムでさえもテクスチャセグメント化に対して十分な情報を提供する、ということに留意されたい。また、ハール（Ｈａａｒ）ウェーブレット等のより高レベルの特徴を定義するためにヒストグラムを結合することも可能である。
【０１０４】
ここでは、画素単位のテクスチャ特徴を確定するとともに、画像データに対してテンソルを構成する。各テンソルは、勾配の大きさ、向き、色及びエッジ等の対応するテクスチャコンポーネントを、ガボール（Ｇａｂｏｒ）フィルタ、離散フーリエ及びコサイン変換係数等の他の画像フィルタ応答とともに含むベクトルである。
【０１０５】
本発明では、テンソルを使用してテクスチャのヒストグラムを確定する。たとえば、ｋ個の異なるテクスチャコンポーネントを有する場合、本発明のテンソルは［１×ｋ］テンソルである。テンソルの各要素は、現画素の対応するテクスチャ特徴の値を示す。本発明ではまた、第１、第２、…第ｄ（ただし、ｄは大きい正の整数であり得る）の特徴に対するＫ１、Ｋ２、…、Ｋｄ等のセンサの各要素に対して量子化ステップも指定する。そして、統合ヒストグラムは、Ｋ１×Ｋ２×…×Ｋｄである。従来の方法を使用する各目標領域／データ範囲に対するこうしたより高次元のヒストグラムの構成には、指数関数的な時間が必要であり、それは、大部分のテクスチャ検出アプリケーションにはかかりすぎる（prohibitive）。しかしながら、統合ヒストグラム法では、特にデータの次元が増大するに従い、計算負荷のより大きい低減が可能である。
【０１０６】
より高レベルの特徴
図１０乃至図１２に示すように、本発明による統合ヒストグラムの空間的、階層的及びモデルベースの結合を使用してより高レベルの特徴を容易に確定することができる。
【０１０７】
図１０は、中心点ｐ１０１０の周囲のヒストグラムｈ１、ｈ２、ｈ３及びｈ４の空間的結合を示す。結合されたヒストグラムｈ（ｐ）１０２０は、（ｈ１−ｈ２＋ｈ３−ｈ４）によって与えられる。より高レベルの特徴は、画像の領域の対応するヒストグラムを加算し又は減算することによって構成される。
【０１０８】
図１１は、点ｐ１１０５を中心とするヒストグラムｈ１、ｈ２及びｈ３の階層的結合を示す。単一スケールでヒストグラムを構成する代りに、より高レベルの特徴は、異なる同心円領域内の複数のヒストグラムから構成される。ヒストグラムは、結合されることにより、基礎にあるデータ分布のマルチスケール特性を取り込むために、ｈ１∪ｈ２∪ｈ３であるｈ（ｐ）１１１０に従って統合されたヒストグラムを形成する。
【０１０９】
図１２は、髪の色１２０１、目の色１２０２、顔のテクスチャ１２０３、肌の色１２０４及び唇の色１２０５を含む顔に対するヒストグラムのモデルベースの結合を示す。結合されたヒストグラムｈ（ｐ）１２１０は∪ｉｈｉである。
【０１１０】
これらの結合は、データ値の分布と同様に空間情報の統合も可能にする。
【０１１１】
追跡例
図９は、入力ビデオのオブジェクト、たとえば通りの風景における歩行者を追跡する従来のヒストグラム法と本統合ヒストグラム法を比較する。入力は、フレーム９０１のシーケンスである。シーケンス９０２は、従来の平均値シフト追跡の結果を示す。従来の方法は歩行者を追跡することができず、代りに静止した影を追跡することに留意されたい。シーケンス９０３は、統合ヒストグラム法を使用してシーケンス９０４において正しく追跡されるような、追跡されるオブジェクトを示す。
【０１１２】
オブジェクトの初期化後、元のヒストグラムとすべての画素を中心としたオブジェクト窓のヒストグラムとの間のカラーヒストグラム類似度スコアが求められる。なお、こうした類似度の確定は、従来の方法を使用すると非常に低速であることに留意されたい。統合ヒストグラム法は、平均値シフトとして既知である勾配降下ベースの方法と比較される。これについては、上記のComaniciu他を参照されたい。
【０１１３】
平均値シフト方法では、オブジェクトの窓であるその元のカーネル内でのみ、多くの場合Ｂｈａｔｔａｃｈａｒｙａ距離を使用して、ヒストグラム類似度を評価する。平均値シフトの繰返しにより、各カラーチャネルに対して１６ビンのヒストグラムを使用する。しかしながら、平均値シフトは、限られた探索領域内における類似度しか評価しない。その結果、フレーム間でオブジェクト再配置が大きく、且つ連続したフレームにおけるオブジェクト窓間にオーバラップがない場合、シーケンス９０２に示すように必ず失敗する。
【０１１４】
統合ヒストグラムによって、比較的一定の短時間、たとえば５５ミリ秒で、画像平面全体にわたり類似度を確定することができる。このため、統合ヒストグラム法により、オブジェクトを高フレームレートで正確に追跡することが今や可能である。
【０１１５】
発明の効果
本発明は、デカルト空間においてあり得るすべての領域のヒストグラムを抽出するとともに探索する計算効率の高い方法を提供する。統合ヒストグラムは、ヒストグラムベースのアプリケーションに対して最適且つ完全な解決法を提供する。
【０１１６】
統合ヒストグラム法は、従来の方法に比較して何千倍を上回る速度で探索プロセスを行うことができる。
【０１１７】
本方法を、任意の次元のデータ空間に且つ任意のテンソル表現に拡張することができる。
【０１１８】
さらに、本方法により、さらなる特徴選択及び分類目的のために高度なヒストグラム特徴を構成することができる。
【０１１９】
今までリアルタイム要件がネックであった、ビデオオブジェクト検出及びビデオオブジェクト追跡等の多くのコンピュータビジョンアプリケーションは、本統合ヒストグラム法から利益を得ることができる。
【０１２０】
本発明を好ましい実施形態の例によって説明したが、本発明の精神及び範囲内で他のさまざまな適合及び変更を行ってもよい、ということが理解されるべきである。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内にあるこうしたすべての変形及び変更を包含することである。
【図面の簡単な説明】
【０１２１】
【図１】従来技術によるヒストグラムである。
【図２】従来技術によるヒストグラム抽出方法の擬似コードである。
【図３】本発明によるヒストグラム抽出方法の擬似コードである。
【図４】画像の画素を通してのスキャンラインのブロック図である。
【図５】再帰的統合ヒストグラム構成のブロック図である。
【図６】再帰的統合ヒストグラム構成のブロック図である。
【図７】入力画像における目標交通標識を同様の類似度マップにマッピングする図である。
【図８】入力画像におけるテクスチャを類似度マップにマップする図である。
【図９】従来の平均値シフトオブジェクト追跡を使用するビデオにおけるオブジェクト追跡と、本発明による統合ヒストグラム法での追跡とを比較する図である。
【図１０】本発明による統合ヒストグラムの空間的結合のブロック図である。
【図１１】本発明による統合ヒストグラムの階層的結合のブロック図である。
【図１２】本発明による統合ヒストグラムのモデルベースの結合のブロック図である。
【図１】
2008530627.tif 000027
【図２】
2008530627.tif 000028
【図３】
2008530627.tif 000029
【図４】
2008530627.tif 000030
【図５】
2008530627.tif 000031
【図６】
2008530627.tif 000032
【図７】
2008530627.tif 000033
【図８】
2008530627.tif 000034
【図９】
2008530627.tif 000035
【図１０】
2008530627.tif 000036
【図１１】
2008530627.tif 000037
【図１２】
2008530627.tif 000038
【国際調査報告】
2008530627.tif 000039
2008530627.tif 000040
2008530627.tif 000041