(57)【要約】【課題】この発明は、バイラテラルフィルタを用いて入力画像をフィルタリングする方法を記載する。【解決手段】バイラテラルフィルタは空間フィルタおよびレンジフィルタを含む。この発明の実施の形態による方法は、強度をそれぞれ有する複数の画素を含む入力画像からパワー画像の集合を構築する。次に、本方法は、各パワー画像に空間フィルタを適用して、空間フィルタの応答および対応するパワー画像を求め、これらの応答およびパワー画像の集合を結合して、バイラテラルフィルタの応答を生成する。【選択図】図１
2010003297.tif 000002
【特許請求の範囲】
【請求項１】
バイラテラルフィルタを用いて入力画像をフィルタリングする方法であって、該バイラテラルフィルタは空間フィルタおよびレンジフィルタを含み、該方法は、
強度をそれぞれ有する複数の画素を含む入力画像からパワー画像の集合を構築するステップと、
各パワー画像に前記空間フィルタを適用するステップであって、該空間フィルタの応答および対応するパワー画像を求める、適用するステップと、
前記応答および前記パワー画像の集合を結合するステップであって、前記バイラテラルフィルタの応答を生成する、結合するステップと、
を含む、方法。
【請求項２】
前記フィルタリングの処理時間は、所与の画像サイズに対して一定であり、前記バイラテラルフィルタの半径に依存しない、請求項１に記載の方法。
【請求項３】
時間的に実行されて出力画像列を生成する、請求項１に記載の方法。
【請求項４】
前記空間フィルタはｆ（ｋ）＝ｃであり、ここで、ｃは任意の定数であり、前記レンジフィルタはｇ（ｐ，ｋ）であり、ここで、ｐは前記バイラテラルフィルタの中心画素であり、ｋは応答である、請求項１に記載の方法。
【請求項５】
前記パワー画像の集合は、
Ｉ１＝Ｉ（ｐ），Ｉ２＝Ｉ（ｐ）Ｉ（ｐ），．．．，（Ｉ（ｐ））ｎ
として示され、対応するフィルタ応答は、
ｙ１Σｆ（ｋ）Ｉ１（ｐ＋ｋ），ｙ２Σｆ（ｋ）Ｉ２（ｐ＋ｋ），．．．，ｙｎΣｆ（ｋ）Ｉｎ（ｐ＋ｋ）
であり、ここで、Ｉは前記入力画像であり、ｎは前記集合のパワー画像の数である、請求項４に記載の方法。
【請求項６】
前記レンジフィルタは２次多項式関数であり、前記応答は、
【数１】
2010003297.tif 000022
であり、ここで、
【数２】
2010003297.tif 000023
である、請求項５に記載の方法。
【請求項７】
前記レンジフィルタは、
ｅｘｐ（−αＩ２（ｐ））ｅｘｐ（−α［Ｉ２（ｐ）−２Ｉ（ｐ）Ｉ（ｐ＋ｋ）］）
であり、ここで、αは定数である、請求項５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には画像のフィルタリングに関し、特に、一定のＯ（１）時間でのバイラテラルフィルタを用いる画像のフィルタリングに関する。
【背景技術】
【０００２】
バイラテラルフィルタは、空間領域および強度領域において画像に適用される非線形フィルタである。高速バイラテラルフィルタは、多くのコンピュータビジョン用途に重要である。非線形フィルタを分離可能な１次元フィルタまたはカスケード表現に分解して処理時間を短縮するいくつかの方法が知られている。これは、２Ｄフィルタカーネルの固有値展開、または特異値分解（ＳＶＤ）の適用を用いることによって行うことができる。いくつかの方法は、並列処理および再構成可能ハードウェアを役立てようとする。
【０００３】
バイラテラルフィルタは、エッジの細部を保ちながら画像を平滑化する非反復的な手段である。フィルタリングは加重重畳を含み、各画素の重みは、中心画素からの距離だけでなく強度にも依存する。ベイズ手法もまたバイラテラルフィルタの中核にあり、バイラテラルフィルタリングを、対角正規化された（ｄｉａｇｏｎａｌ  ｎｏｒｍａｌｉｚｅｄ）最急降下法の一回の反復として記述する。
【０００４】
バイラテラルフィルタの基本的な特性は、（空間）フィルタ半径ｒに対する画素当たりの処理時間である。これは、フィルタ半径（または、カーネルサイズ）の変化に伴う方法の性能に対応する。この性能は、バイラテラルフィルタリング方法の中の主な差別化特徴である。
【０００５】
空間・レンジ統合フィルタリングにより、バイラテラルフィルタは計算量が多くなる。参考のために、総当たり実行は、指数関数的なＯ（ｒ２）時間で各出力画素を計算する可能性があり、中程度のフィルタ半径でも非現実的となる。よく知られたＰｈｏｔｏｓｈｏｐ（著作権）ＣＳ２の表面ぼかしの実行は、バイラテラルフィルタであり、メディアンフィルタに用いられる行列ヒストグラムと同様の線形のＯ（ｒ）時間特性を有する。
【０００６】
バイラテラルフィルタは、離散的強度カーネルを用いて画像のサブサンプリングされたコピーをフィルタリングし、線形補間を用いてフィルタ応答を結合することによって近似することができる。言い換えれば、この方法は、強度画像を３Ｄ表面として扱い、二値の強度変調された画像にガウシアン平滑化を適用し、強度を除算して、元の表面位置におけるフィルタリングされた強度値を求める。この方法は、半径が大きいほど表面のサブサンプリング比率が高くなるため高速になる。正確な出力は、サブサンプリンググリッドの位相に依存する。しかし、打ち切りを行うと、特に高ダイナミックレンジ（ＨＤＲ）画像で精度が失われることになる。
【０００７】
最も高速な従来技術のバイラテラルフィルタの実行の中の１つは、対数Ｏ（ｌｏｇ  ｒ）時間に収束する（参照により本明細書中に援用される非特許文献１を参照）。その方法は、層に基づく手法において部分分布ヒストグラムの階層を用いる。複雑度は低下しているが、比較的小さなフィルタサイズおよびヒストグラムカウントに特有の実行要件により単純性は失われている。その方法は、矩形の空間カーネルおよびボックスフィルタに限定される。別の懸念は、その空間ボックスフィルタの不完全な周波数応答である。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ｗｅｉｓｓ著「Ｆａｓｔ  ｍｅｄｉａｎ  ａｎｄ  ｂｉｌａｔｅｒａｌ  ｆｉｌｔｅｒｉｎｇ」（Ｐｒｏｃ．  ＳＩＧＧＲＡＰＨ，  ｐａｇｅｓ  ５１９−５２６  ２００６）
【発明の概要】
【発明が解決しようとする課題】
【０００９】
この発明の実施の形態は、サンプリングなしで一定のＯ（１）時間でのバイラテラルフィルタリングを可能にする。本明細書中で定義するように、一定時間は、フィルタ半径が変化しても、フィルタリングの処理時間は同じであり続けることを意味する。
【課題を解決するための手段】
【００１０】
この発明の実施の形態は、積分ヒストグラムを利用して、空間カーネルおよびレンジカーネルを用いるバイラテラルフィルタの冗長演算を避ける。
【００１１】
多項式型空間カーネルおよびレンジカーネルによって構築されるバイラテラルフィルタの場合、別の実施の形態が、線形フィルタを画像パワーに適用することによって直接定式化を行う。
【００１２】
別の実施の形態によれば、フィルタ応答の顕著な低下なく任意の空間フィルタおよびガウシアン型レンジ関数がテイラー級数により線形フィルタ分解として表される。
【００１３】
これらの実施の形態はすべて、処理時間を一定時間、たとえば１ＭＢの画像につき０．３秒に大幅に削減する一方で、４５ｄＢを超す非常に高いピーク信号対雑音比（ＰＳＮＲ）を達成する。計算上の利点に加え、この発明の方法は実行が簡単である。
【００１４】
この発明のフィルタリング方法は、これまでに開発されてきた中で最も効率的なバイラテラルフィルタであると考えられる。これは、本方法は、カーネル半径が大きくなるにつれて複雑度が増すものよりも性能が高いことを意味する。画像がより高解像度になり、それに対応してより大きなカーネル半径が必要となる傾向を考えると、大きなカーネルを用いて小さなカーネルと同じくらい高速にフィルタリングを行う点で本方法は有利となる。
【００１５】
積分ヒストグラムは入力画像から構築され、この積分ヒストグラムは、任意のレンジ関数により強度差に重み付けすることができる均一領域のカーネルを有する矩形ボックスフィルタのバイラテラル重畳応答を求めるために用いられる。積分ヒストグラムは、所与の画像におけるすべての考え得るカーネルのヒストグラムの構築を可能にする。本方法は、デカルト座標系における画素の空間的位置付けを利用し、原点画素から開始し残りの画素を走査線に沿ってジグザグ順に横断して集約関数を伝播する。
【００１６】
画像ウインドウのヒストグラムは、一つ一つの画素に対して別個のヒストグラムを再構築することなく、それらのウインドウの角の画素における積分ヒストグラム値を用いることによって構築することができる。
【００１７】
任意領域のカーネルに対するより一般的なガウシアン型レンジ関数および多項式型レンジ関数に関しては、対応するノルムのテイラー級数展開が用いられる。これは、複雑度を増すことなくバイラテラルフィルタリングに「あらゆる」空間カーネルを使用できるようにする。このようなバイラテラルフィルタは、パワー画像に適用される空間線形フィルタで表すことができる。
【発明の効果】
【００１８】
この発明の実施の形態は、フィルタの半径に関係なく一定時間でのバイラテラルフィルタリングを可能にする方法を提供する。
【００１９】
任意のレンジボックス空間フィルタを有するバイラテラルフィルタのための積分ヒストグラムに基づくバイラテラルフィルタリング方法が提供される。
【００２０】
本方法は、重複カーネルを利用して冗長演算を避ける。本方法は正確であり（ＰＳＮＲ＞４５ｄＢ）、非常に高速である。本方法はまた、各画素における空間フィルタサイズの適応的な設定を可能にする。
【００２１】
タイプＩＩの正確なバイラテラルフィルタの定式は、多項式型レンジフィルタと、線形フィルタによる任意の空間フィルタとを有する。これらのフィルタは、正確なものとして同一の応答を与える。上記と同様に、これらのフィルタも非常に高速である。処理時間は、フィルタの半径に関係なく、１ＭＢの画像に対して０．３秒未満である。
【００２２】
ガウシアン型レンジフィルタおよび任意の空間フィルタを有するタイプＩＩＩのバイラテラルフィルタ（σｒ＝０．１まで）は、テイラー級数によって表すことができ、非線形バイラテラルフィルタリングを画像パワーの線形フィルタリングおよび線形フィルタタップの適応的な設定に変換する。この展開は、正確なフィルタ（ＰＳＮＲ＞５０ｄＢ）と略同じである。
【００２３】
画像がより高解像度になり、それに対応してより大きなカーネル半径が必要となる一般的な傾向を考えると、大きなカーネルを用いて小さなカーネルと同じくらい高速にフィルタリングを行う点で、説明する方法は有利となる。
【図面の簡単な説明】
【００２４】
【図１】この発明の実施の形態１によるバイラテラルフィルタの概略図である。
【図２】この発明の実施の形態１による積分ヒストグラムの構築の概略図である。
【図３】この発明の実施の形態１による、タイプＩのバイラテラルフィルタを用いて入力画像をフィルタリングし、出力画像を作成する方法の流れ図である。
【図４】この発明の実施の形態１による、タイプＩＩのフィルタを用いて入力画像をフィルタリングし、出力画像を作成する方法の流れ図である。
【図５】この発明の実施の形態１による、タイプＩＩＩのフィルタを用いて入力画像をフィルタリングし、出力画像を作成する方法の流れ図である。
【発明を実施するための形態】
【００２５】
バイラテラルフィルタリング
フィルタｆは、ｄ次元のデカルト空間
【００２６】
【数１】
2010003297.tif 000003
【００２７】
において定義される写像である。このフィルタは、Ｎ１，．．．，Ｎｄ、および、０≦ｘｉ＜Ｎｉ内を境界とする入力画像Ｉの各画素ｐ＝［ｘ１，．．．，ｘｄ］にｍ次元の応答ベクトル（応答）ｙ（ｐ）＝［ｙ１，．．．，ｙｍ］を割り当てる。
【００２８】
通常、台Ｓの領域内の小さな画素集合のみを用いてフィルタ応答が求められる。画素ｐを中心とする台の領域は、フィルタのフットプリントまたはカーネルと呼ばれる。一般性を失うことなく、画素集合はスカラー値に対応する。すなわち、ｍ＝１であり、ｙ（ｐ）＝ｙ１である。例示的な実施の形態は、単一のチャネル画像フィルタリング（ｄ＝２，ｍ＝１）を用いる。しかし、本方法は、より高い次元、カラー画像および時間的なビデオのフィルタリングに拡張することができる。
【００２９】
画像画素ｐを中心とする２Ｄ画像フィルタが、係数ｆ（ｋ）をその下にある、カーネルｋ＝［ｋｘ，ｋｙ］∈Ｓ内の画像画素ｋ＋ｐの値に適用する。
【００３０】
矩形カーネルの場合、中心画素の座標は、原点として割り当てることができる。すなわち、Ｓ：−ｒ／２≦ｋｘ，ｋｙ≦ｒ／２であり、ここで、ｒはフィルタの半径である。係数の値が空間的な位置のみに依存する場合、フィルタは空間フィルタに該当する。
【００３１】
フィルタが線形演算子により、たとえばカーネルに対する行列の乗算として表される場合、そのフィルタは線形である。たとえば、２Ｄのガウシアン平滑化演算子は、中心画素からの空間的距離に応じて係数の値が変化する線形フィルタである。上記の表記が与えられると、空間フィルタの応答は、次式のように表される。
【００３２】
【数２】
2010003297.tif 000004
【００３３】
ここで、κ＝Σｆ（ｋ）は、バイアスを防ぐためのスカラー項である。なお、上記の式は、ｆおよびＩの重畳と同じである。簡潔にするために、フィルタは正規化されることが多い。すなわち、Σｆ（ｋ）＝１となる。
【００３４】
図１に示すように、この発明の実施の形態１によるバイラテラルフィルタ１０１は、空間フィルタ１０２およびレンジフィルタ１０３を結合する。空間フィルタのベクトル係数は、中心画素１１１への距離に応じて変化し、レンジフィルタｇ（ｐ，ｋ）のベクトル係数は、中心への空間的距離ではなく、カーネル１１２内の中心画素と残りの画素との間の強度差１０３に応じて変化する。レンジフィルタは、強度差の関数、すなわち、ｇ（Ｉ（ｐ）−Ｉ（ｐ＋ｋ））である。
【００３５】
言い換えれば、バイラテラルフィルタは、カーネルＳ内の画像画素の強度値に、対応する空間フィルタ係数ｆ（ｋ）およびレンジフィルタ係数ｇ（ｐ，ｋ）を乗算する。したがって、バイラテラルフィルタの応答は、
【００３６】
【数３】
2010003297.tif 000005
【００３７】
となり、ここで、正規化項
【００３８】
【数４】
2010003297.tif 000006
【００３９】
は強度差のスカラー関数である。レンジフィルタは、入力画像の各画素において異なる値を持ち得る。空間フィルタとは異なり、正規化項κｂは一定でない。
【００４０】
上記のレンジフィルタリングの特性により、バイラテラルフィルタは非線形フィルタである。このフィルタの応答は、単純な行列の乗算では得ることができない。これが、従来のバイラテラルフィルタの計算量が多い主な理由である。
【００４１】
この発明の目的は、バイラテラルフィルタリングをフィルタの半径（サイズ）とは関係なく一定のＯ（１）時間で行うことである。
【００４２】
空間フィルタを用いるバイラテラルフィルタリング
式（２）は、一定の空間フィルタｆ（ｋ）＝ｃ（ボックスフィルタ）および任意のレンジフィルタｇ（ｐ，ｋ）を有するバイラテラルフィルタ（タイプＩのバイラテラルフィルタと呼ぶことがある）用に
【００４３】
【数５】
2010003297.tif 000007
【００４４】
および
【００４５】
【数６】
2010003297.tif 000008
【００４６】
のように書き換えることができる。
【００４７】
この応答は、対応するカーネルの積分ヒストグラムｈから、
【００４８】
【数７】
2010003297.tif 000009
【００４９】
および
【００５０】
【数８】
2010003297.tif 000010
【００５１】
のように直接求めることができ、ここで、レンジ関数は、直接の強度差ではなく、ヒストグラムのビン値にわたって蓄積される。
【００５２】
本明細書中で説明するように、この定式はカーネル半径ｒに依存しない。１つの利点として、すべてのスカラー項を積分ヒストグラムから一定時間で並列処理することができる。さらに、ガウシアンフィルタ関数およびより複雑なフィルタ関数を含む任意のレンジフィルタｇを用いることができる。
【００５３】
Ｗｅｉｓｓ（上記を参照）は、タイプＩのバイラテラルフィルタ（空間ボックス、任意レンジ）の処理時間をＯ（ｌｏｇ  ｒ）として与える。Ｗｅｉｓｓのフィルタは、妥当な性能を得るために半径ｒが１２８未満に略限定されている。この発明の方法は、これを画像サイズまでのあらゆる半径ｒに関して一定時間Ｏ（１）に削減する。
【００５４】
この一定時間フィルタは、最も高速な既知のバイラテラルフィルタと考えられる。
【００５５】
任意の空間フィルタを用いるバイラテラルフィルタリング
積分ヒストグラムの定式は、変化する空間フィルタを有するバイラテラルフィルタには適用することができない。多項式型レンジフィルタは、
ｇ（ｐ＋ｋ）＝［１−（Ｉ（ｐ）−Ｉ（ｐ＋ｋ））２］ｎ  ・・・（６）
であり、ここで、ｎは多項式の次数である。ｎ＝１の場合、対応するバイラテラルフィルタ（タイプＩＩのフィルタと呼ばれる）を式（２）から次のように得ることができる。
【００５６】
【数９】
2010003297.tif 000011
【００５７】
ｎ個の画像の集合は、Ｉ１＝Ｉ（ｐ），Ｉ２＝Ｉ（ｐ）Ｉ（ｐ），，．．．，（Ｉ（ｐ））ｎとして示され、対応するフィルタ応答は、次のようになる。
ｙ１Σｆ（ｋ）Ｉ１（ｐ＋ｋ），ｙ２Σｆ（ｋ）Ｉ２（ｐ＋ｋ），．．．，ｙｎΣｆ（ｋ）Ｉｎ（ｐ＋ｋ）
ｙ１＝Σｆ（ｋ）Ｉ（ｐ＋ｋ），ｙ２＝Σｆ（ｋ）Ｉ２（ｐ＋ｋ），．．．，
【００５８】
式（７）は、次のように書き換えることができる。
【００５９】
【数１０】
2010003297.tif 000012
【００６０】
ここで、インデックスｐは、簡潔にするために式の右辺から省かれる。
【００６１】
同様に、正規化項は、次のようになる。
κｂ＝１−Ｉ２＋２Ｉｙ１−ｙ２
【００６２】
なお、空間フィルタｆに制約はなく、任意の所望のフィルタ関数を選択することができる。
【００６３】
２次多項式関数（ｎ＝２）の場合（図４を参照）、式（２）のタイプＩＩのバイラテラルフィルタの応答は、
【００６４】
【数１１】
2010003297.tif 000013
【００６５】
となり、ここで、
【００６６】
【数１２】
2010003297.tif 000014
【００６７】
である。
【００６８】
式（８）および式（９）は、多項式型レンジフィルタを用いる対応するバイラテラルフィルタのパラメータを、空間フィルタに関して近似を用いることなく与える。
【００６９】
別の一般的なタイプのバイラテラルフィルタであるタイプＩＩＩは、さらなる平滑性のためにガウシアン型レンジフィルタパラメータ５１１を用いる（図５を参照）。この実施の形態において、ガウシアン関数のテイラー級数展開がこのようなバイラテラルフィルタを近似する。この方法もやはり、空間フィルタｆに対する制約はない。ガウシアンフィルタは微分可能であり、１次変換で表すことができる。
【００７０】
ガウシアンレンジフィルタは、
ｅｘｐ（−α［Ｉ（ｋ＋ｐ）−Ｉ（ｐ）］２）  ・・・（１０）
であり、ここで、αは定数である。
【００７１】
式（１０）は、次のように書くことができる。
ｅｘｐ（−αＩ２（ｐ））ｅｘｐ（−α［Ｉ２（ｐ）−２Ｉ（ｐ）Ｉ（ｐ＋ｋ）］）  ・・・（１１）
ここで、第１項
ｅｘｐ（−αＩ２（ｐ））
はカーネル内で変化しない。この項は正規化項にも現れるため、別個に求める必要はない。
【００７２】
テイラー展開を式（１１）に適用することによって、バイラテラルフィルタの展開を次式のように２次導関数まで得ることができ、
【００７３】
【数１３】
2010003297.tif 000015
【００７４】
また、次式のように３次導関数まで得ることができる。
【００７５】
【数１４】
2010003297.tif 000016
【００７６】
ここで、正規化項は、同一項を含む同様の形を有する。
【００７７】
したがって、バイラテラルフィルタは、原画像のパワーの空間フィルタリングされた応答の加重和として解釈することができる。
【００７８】
一定Ｏ（１）時間バイラテラルフィルタ
２Ｄの線形空間フィルタ応答を求める方法には様々なものがある（図３〜図５を参照）。「移動平均」としても知られる空間ボックスフィルタ３３０は、すべてのカーネル係数が等しい矩形カーネルを有する単純な線形フィルタである。このフィルタは、積分ヒストグラム３１０を用いることによって一定のＯ（１）時間でも求めることができる。
【００７９】
積分画像
積分画像ＩΣは入力画像における画素強度の累積和である。任意の画像領域ΣＩ（ｐ）の和は、画像領域の角の画素ｐ＋＋、ｐ−＋、ｐ＋−、ｐ−−における積分画像の画素強度値を含む３回の算術演算、たとえば、
ΣＩ（ｐ）＝ＩΣ（ｐ＋＋）−ＩΣ（ｐ＋−）−ＩΣ（ｐ−＋）＋ＩΣ（ｐ−−）
によって求められる。
【００８０】
三角フィルタ、たとえば、ランプフィルタ、バートレットフィルタまたは多項式フィルタを、同一半径を有する２つのボックスフィルタの重ね合わせとして構築することができる。ランプフィルタの計算量はボックスフィルタの計算量の２倍である。したがって、ランプフィルタもまた一定のＯ（１）時間で適用することができ、結果はガウシアンフィルタに視覚的に非常に似ている。
【００８１】
多項式フィルタｆ（ｋ）＝１−ｋｎの応答もまた、積分画像の集合を用いて一定のＯ（１）時間で求めることができる。距離二乗ノルムは次式のようになる。
【００８２】
【数１５】
2010003297.tif 000017
【００８３】
ここで、Ｓｚは画素ｚ−ｐを中心とする新たなカーネルである。和ΣＩ（ｚ）、ΣｚＩ（ｚ）、Σｚ２Ｉ（ｚ）は、対応する積分画像から直接求めることができる。これらの和は、積分画像における矩形領域の角の画素における一定数の演算しか必要としないため、全処理時間は領域サイズに関係ない。計算量は、ここでも一定のＯ（１）時間である。これは、双１次補間フィルタにも有効である。
【００８４】
他の線形空間フィルタは、高速フーリエ変換（ＦＦＴ）によって一定時間で求めることができる。基礎となるＦＦＴの画素毎の計算量は画像のサイズのみに依存する。入力画像毎に、所定の重畳カーネルサイズから開始して、ＦＦＴに基づく重畳は単純な実行よりも有利である。正方形カーネル上のガウシアンフィルタは分離可能である、すなわち、２Ｄフィルタは１Ｄフィルタの集合に分解することができる。
【００８５】
フィルタ半径ｒが比較的小さく、たとえば５０画素未満である場合、フィルタ応答を求める最も速い方法は、直接的な１Ｄ重畳によるものである。フィルタの対称性を利用して、乗算の回数を２分の１に削減することができる。フィルタ半径が比較的大きい場合、直接重畳は時間がかかるため、ＦＦＴに基づく重畳が最良の選択である。
【００８６】
一定の時間処理を保証するために、分離可能な１Ｄの線形空間フィルタが、十分に正確な１５個の非対称タップ（すなわち、中心ほどタップが多い）でサブサンプリングされる。
【００８７】
積分ヒストグラム
積分画像を用いて、可変の矩形画像領域にわたって局所ヒストグラムを求めることができる（Ｆ．  Ｐｏｒｉｋｌｉ著「Ｉｎｔｅｇｒａｌ  ｈｉｓｔｏｇｒａｍ：  Ａ  ｆａｓｔ  ｗａｙ  ｔｏ  ｅｘｔｒａｃｔ  ｈｉｓｔｏｇｒａｍｓ  ｉｎ  Ｃａｒｔｅｓｉａｎ  ｓｐａｃｅｓ」（Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ  （ＣＶＰＲ），  ２００５）、およびＰｏｒｉｋｌｉによって２００５年２月７日に出願された米国特許出願第１１／０５２，５９８号明細書「Ｍｅｔｈｏｄ  ｆｏｒ  Ｅｘｔｒａｃｔｉｎｇ  ａｎｄ  Ｓｅａｒｃｈｉｎｇ  Ｉｎｔｅｇｒａｌ  Ｈｉｓｔｏｇｒａｍｓ  ｏｆ  Ｄａｔａ  Ｓａｍｐｌｅｓ」、いずれも参照により本明細書中に援用される）。
【００８８】
図２および図３に示すように、積分ヒストグラムは、画像画素列における画素毎のヒストグラムの伝播およびそれに続くヒストグラムインタセクションにより任意の（矩形）領域の局所ヒストグラムを求めることを含む。
【００８９】
画素列に沿ったｍ番目の位置における現画像画素２０１における積分ヒストグラムＨ（ｐｍ，ｂ）（ここで、ｂ＝１．．．Ｂ）は次のように定義される。
【００９０】
【数１６】
2010003297.tif 000018
【００９１】
ここで、Ｑ（．）２０５は現画素２０１の対応するビンである。各ビンは、特定の強度範囲にある画素数を示す係数と、この係数に対するインデックスとを格納する。式（１４）の和集合演算子は次のように定義される。Ｈ（ｐｍ，ｂ）の係数値は、ジグザグ順２２０で以前に処理された画素２１０のヒストグラムビンの係数値の和、すなわち、ｊ＜ｍである間のすべてのＱ（Ｉ（ｐｊ））の和に等しい。言い換えれば、Ｈ（ｐｍ，ｂ）は原点２５０と現画素２０１
【００９２】
【数１７】
2010003297.tif 000019
【００９３】
との間の領域のヒストグラムである。
【００９４】
積分ヒストグラムＨ（ｐＮ，ｂ）は、ｐＮ＝［Ｎ１，Ｎ２］が入力画像中の最後（左下）の画素であるため、すべての画素のヒストグラムに等しい。したがって、積分ヒストグラムは、原点（左上）の画素２５０に関してすべてのビンが空であることを意味する初期条件Ｈ（０，０，ｂ）＝０を用いて再帰的に次のように表すことができる。
Ｈ（ｐｘ，ｐｙ，ｂ）＝Ｈ（ｐｘ−１，ｐｙ，ｂ）＋Ｈ（ｐｘ，ｐｙ−１，ｂ）−Ｈ（ｐｘ−１，ｐｙ−１，ｂ）＋Ｑ（Ｉ（ｐｘ，ｐｙ））  ・・・（１５）
【００９５】
ジグザグ走査２２０は、左、上、および左上の近傍が走査された画素に関して積分ヒストグラムの更新を必要とする。現画素における積分ヒストグラム２１４は、各ビンにつき３回の算術演算によって、図２に示すように３近傍の積分ヒストグラム値２１１〜２１３を用いて得られる。前画素の積分ヒストグラム値は伝播前に現画素にコピーされる。
【００９６】
領域Ｔのヒストグラムは、その領域の境界画素
【００９７】
【数１８】
2010003297.tif 000020
【００９８】
における伝播した積分ヒストグラム値を用いて次のように求めることができる。
【００９９】
【数１９】
2010003297.tif 000021
【０１００】
従来のヒストグラム計算とは対照的に、積分ヒストグラム方法は、考え得る領域毎にヒストグラムの抽出を繰り返さないため、ヒストグラムの抽出はフィルタカーネルのサイズｒに依存しない。したがって、処理時間はあらゆるフィルタサイズに対して一定である。
【０１０１】
なお、積分ヒストグラムは、バイラテラルフィルタを各画像画素に適用する際に空間フィルタ半径ｒのサイズを制約しない。言い換えれば、入力画像を走査（２２０）しつつフィルタ半径ｒを各画素において適応的に変更することが可能である。
【０１０２】
分布ヒストグラム
Ｗｅｉｓｓは、重複カーネルを用いるため、複数の列に対して一度に作用する。複数列動作の枠組みが与えられると、Ｗｅｉｓｓは画素の正の値を列ｉのヒストグラムには格納せず、その画素の負の値を、列ｉ＋１のヒストグラムには現れるべきでない列ｉのヒストグラムに格納する。この結果、正の一列および負の一列のみを記録する基底に隣接するヒストグラム、並びに正のｒ列および負のｒ列を記録する距離ｒだけ離れたヒストグラムが得られる。最も外側のヒストグラムが非常に少数の列を基底と共有しても役に立たず、部分ヒストグラム群の維持には、特にｒが大きく、たとえば１２８よりも大きい場合にオーバーヘッドがあるため、上記の処理時間はＯ（ｌｏｇ  ｒ）である。
【０１０３】
Ｗｅｉｓｓの方法を拡張して基底ヒストグラムの複数の層を含めると、第１層の大きな共通基底ヒストグラム、第２層の７画素間隔のいくつかの中型のサイズの部分ヒストグラム、および第３層の１画素刻みの多くの小さな部分ヒストグラムに対応する。大きな半径のフィルタリングの完全に理論的な分析では、７つの層に数十万の部分ヒストグラムを保つことによって、Ｗｅｉｓｓの処理時間はＯ（ｌｏｇ  ｒ）に収束する。Ｗｅｉｓｓは、走査の中心列に大きな辞書を維持して、所与の近傍画素が中心画素からｒ列に入らないかどうかを判定する。しかし、これらの辞書の維持は、ヒストグラムよりも格段に遅い。辞書の維持に加え、近傍が与えられるとバイラテラルフィルタの計算には遥かに長い時間がかかる。
【０１０４】
図３は、タイプＩのバイラテラルフィルタのための方法を示す。この方法は、バイラテラルフィルタ３００を用いて入力画像３０１をフィルタリングし、出力画像３０９を作成する。入力画像は複数の画素を含み、各画素は強度を有する。入力画像がカラー（ＲＧＢ）である場合、３つの強度が各色に１つずつある。バイラテラルフィルタ２００は、空間フィルタ３３０およびレンジフィルタ３４２を含む。積分ヒストグラム３１０が入力画像から構築される。
【０１０５】
積分ヒストグラムは１度に１画素ずつ、たとえば順番２２０で処理される（３２０）。画素毎に、空間フィルタが積分ヒストグラムに適用されて局所ヒストグラムが作成される（３０３）。各局所ヒストグラムは画素の特定の強度範囲に対してビンを有する。たとえば、強度が８ビット値（０〜２５５）であり、３２個のビンがある場合、各範囲は８レベルの強度にまたがる。各ビンには、特定範囲の画素数を示す係数３２１と、この係数に対するインデックス３２２とが関連付けられている。
【０１０６】
各局所ヒストグラムのビン毎に、画素の強度３０２が各インデックスから減算されて（３４０）差分値３０４が生成される。ビン毎に、レンジフィルタが各差分値に適用されて（３５０）ビン応答３０５が生成される。各応答は、対応する係数によってスケーリングされて（３６０）スケーリングされた応答３６１が生成される。
【０１０７】
局所ヒストグラム毎に、スケーリングされた応答が総和されて（３７０）、局所ヒストグラムの局所応答３７１が生成され、それらの係数が総和されて（３８０）係数３８１の和を生成する。次に、画素毎に、局所応答を係数の和で除算して（３９０）バイラテラルフィルタ応答３０６を生成し、これが出力画像となる。
【０１０８】
図４は、タイプＩＩのバイラテラルフィルタのための方法を示す。パワー画像４２０が入力画像４０１から、多項式型レンジフィルタパラメータ４１１を用いて構築される（４１０）。任意のカーネル空間フィルタ関数４２１がパワー画像に適用されてフィルタ応答４３０が生成される。これらのフィルタ応答およびパワー画像が結合されて（４４０）出力画像４０３が生成される。タイプＩＩのバイラテラルフィルタ応答は式（８）または式（９）に従って求めることができる。
【０１０９】
図５は、タイプＩＩＩのバイラテラルフィルタのための方法を示す。パワー画像４２０が入力画像４０１から、ガウシアン型レンジフィルタパラメータ５１１を用いて構築される（４１０）。任意のカーネル空間フィルタ関数４２１がパワー画像に適用されてフィルタ応答４３０が生成される。これらのフィルタ応答およびパワー画像が結合されて出力画像４０３が生成される。タイプＩＩＩのバイラテラルフィルタ応答は式（１２）または式（１３）に従って求めることができる。
【０１１０】
この発明を好適な実施の形態の例として説明してきたが、この発明の精神および範囲内で様々な他の適応および変更を行うことができることが理解される。したがって、添付の特許請求の範囲の目的は、この発明の真の精神および範囲に入る変形および変更をすべて網羅することである。
【図１】
2010003297.tif 000024
【図２】
2010003297.tif 000025
【図３】
2010003297.tif 000026
【図４】
2010003297.tif 000027
【図５】
2010003297.tif 000028
【外国語明細書】
2010003297.tif 000029
2010003297.tif 000030
2010003297.tif 000031
2010003297.tif 000032
2010003297.tif 000033
2010003297.tif 000034
2010003297.tif 000035
2010003297.tif 000036
2010003297.tif 000037
2010003297.tif 000038
2010003297.tif 000039
2010003297.tif 000040
2010003297.tif 000041
2010003297.tif 000042
2010003297.tif 000043
2010003297.tif 000044
2010003297.tif 000045
2010003297.tif 000046
2010003297.tif 000047
2010003297.tif 000048
2010003297.tif 000049
2010003297.tif 000050
2010003297.tif 000051
2010003297.tif 000052
2010003297.tif 000053
2010003297.tif 000054
2010003297.tif 000055
2010003297.tif 000056
2010003297.tif 000057