(57)【要約】      （修正有）【課題】コンピュータ実装方法がカーネルフィルタを用いて入力データをフィルタリングする。【解決手段】カーネルフィルタを定義され、カーネルフィルタに対して一組の一意のフィルタ係数が求められる。リンクセットが、各一意のフィルタ係数に対し、リンクセットが、同一のフィルタ係数を有するカーネルフィルタにおける位置に対する相対リンクを含み、各相対リンクが一意のフィルタ係数の位置の逆数であるように構成される。各入力データポイントが、カーネルフィルタが中心を置く値を一意のフィルタ係数の各々で乗算によって処理され、乗算の結果を、相対リンクが参照するように対応する出力データポイントに加算する。【選択図】図４
2008226233.tif 000002
【特許請求の範囲】
【請求項１】
カーネルフィルタを用いて入力データをフィルタリングするコンピュータ実装方法であって、
ｄ次元実数値デカルト空間ＲｄにおいてカーネルフィルタＳを定義するステップであって、前記カーネルフィルタは、前記空間における入力データポイントｐ＝［ｘ１，・・・，ｘｄ］に中心を置く前記カーネルフィルタ内の入力データＩを、対応するｍ次元出力データポイントにマップし、
Ｉ（ｐ；Ｓ）→ｙ（ｐ）＝［ｙ１，・・・，ｙｍ］
フィルタは、実数値係数ｆ（ｐ）を前記カーネルフィルタにおける前記入力データポイントｐの各々に割り当てる、ステップと、
前記カーネルフィルタに対して一組の一意のフィルタ係数ｗｉ（ｉ＝１，・・・，Ｕ）を求めるステップと、
各一意のフィルタ係数ｗｉに対しリンクセットＬｉを、前記リンクセットが、同一のフィルタ係数を有する前記カーネルフィルタにおける位置に対する相対リンクを含みＬｉ＝｛ｌｉｏ，・・・，ｌｉＬｉ｝、各相対リンクｌｉｊが前記一意のフィルタ係数の前記位置の逆数であるように構成するステップと、
前記カーネルフィルタが中心を置く値を前記一意のフィルタ係数の各々で乗算によって各入力データポイントを処理し、前記乗算の結果を、前記相対リンクが参照するように前記対応する出力データポイントに加算するステップと
【数１】
2008226233.tif 000015
を含む、カーネルフィルタを用いて入力データをフィルタリングするコンピュータ実装方法。
【請求項２】
前記入力データは、０≦ｘ１＜Ｎｉである場合、範囲Ｎ１，・・・，Ｎｄ内に制限される、請求項１に記載の方法。
【請求項３】
単一チャネル画像カーネルフィルタは２次元で定義され、カラーカーネルフィルタ及びビデオカーネルフィルタは３次元で定義される、請求項２に記載の方法。
【請求項４】
前記カーネルフィルタの応答は、
【数２】
2008226233.tif 000016
である、請求項１に記載の方法。
【請求項５】
ｍ＝１であり、前記カーネルフィルタはスカラーにマップし、ｙ（ｐ）＝ｙ１である、請求項１に記載の方法。
【請求項６】
前記カーネルフィルタにおける前記位置は（ｘ１，ｘ２）であり、前記相対リンクは、前記カーネルフィルタのインデックス付けに関して（−ｘ２，−ｘ２）である、請求項１に記載の方法。
【請求項７】
前記一意のフィルタ係数及び前記相対リンクは、処理段階において前記カーネルフィルタに対して一度事前に求められる、請求項１に記載の方法。
【請求項８】
各入力データポイントに対しｐｉｊ＝（ｘ１（ｉ，ｊ），ｘ２（ｉ，ｊ））及びｌｉｊ＝（−ｘ１（ｉ，ｊ），−ｘ２（ｉ，ｊ））を求めるステップ
をさらに含む、請求項１に記載の方法。
【請求項９】
前記入力データは画像における画素であり、前記カーネルフィルタは、選択された順序で前記画像にわたって掃引され、
前記対応する相対リンクを使用して各入力データポイントＩ（ｘ１，ｘ２）を重み付けするステップをさらに含む、請求項１に記載の方法。
【請求項１０】
各入力データポイントは、各一意のフィルタ係数によって一度だけ乗算され、一方で、前記乗算の結果を、前記対応する相対リンクを使用して前記対応する出力データポイントに加算する、請求項１に記載の方法。
【請求項１１】
合計
【数３】
2008226233.tif 000017
を求めるステップをさらに含む、請求項１に記載の方法。
【請求項１２】
前記カーネルフィルタは、４象限対称フィルタ、ガボールフィルタ、移動平均フィルタ、グレーレベルモルフォロジカル演算子フィルタ、ボリューム平滑化関数、ガウスフィルタ、シンクフィルタ及びローパスフィルタを含むグループから選択される、請求項１に記載の方法。
【請求項１３】
前記カーネルフィルタは任意の形状及びサイズを有する、請求項１に記載の方法。
【請求項１４】
前記カーネルフィルタは線形フィルタである、請求項１に記載の方法。
【請求項１５】
前記入力データポイントは、前記結果を前記対応する出力データポイントに累算することによって並列に同時に処理される、請求項１に記載の方法。
【請求項１６】
カーネルフィルタを用いて入力データをフィルタリングするコンピュータ実装方法であって、
カーネルフィルタＳを定義するステップと、
前記カーネルフィルタに対して一組の一意のフィルタ係数を求めるステップと、
各一意のフィルタ係数に対しリンクセットを、該リンクセットが、同一のフィルタ係数を有する前記カーネルフィルタにおける位置に対する相対リンクを含み、各相対リンクが前記一意のフィルタ係数の前記位置の逆数であるように構成するステップと、
前記カーネルフィルタが中心を置く値を前記一意のフィルタ係数の各々で乗算によって各入力データポイントを処理し、該乗算の結果を、前記相対リンクが参照するように前記対応する出力データポイントに加算するステップと
を含む、カーネルフィルタを用いて入力データをフィルタリングするコンピュータ実装方法。
【請求項１７】
前記入力データは、所定の範囲内に制限される、請求項１６に記載の方法。
【請求項１８】
単一チャネル画像カーネルフィルタは２次元で定義され、カラーカーネルフィルタ及びビデオカーネルフィルタは３次元で定義される、請求項１７に記載の方法。
【請求項１９】
前記カーネルフィルタは任意の形状及びサイズを有する、請求項１６に記載の方法。
【請求項２０】
カーネルフィルタを用いて入力データをフィルタリングする装置であって、
カーネルフィルタを定義する手段と、
前記カーネルフィルタに対して一組の一意のフィルタ係数を求める手段と、
各一意のフィルタ係数に対しリンクセットを、該リンクセットが、同一のフィルタ係数を有する前記カーネルフィルタにおける位置に対する相対リンクを含み、各相対リンクが前記一意のフィルタ係数の前記位置の逆数であるように構成する手段と、
前記カーネルフィルタが中心を置く値を前記一意のフィルタ係数の各々で乗算によって各入力データポイントを処理し、該乗算の結果を、前記相対リンクが参照するように前記対応する出力データポイントに加算する手段と
を含む、カーネルフィルタを用いて入力データをフィルタリングする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはデータをフィルタリングすることに関し、特に任意のカーネルフィルタを用いてデータをフィルタリングすることに関する。
【背景技術】
【０００２】
信号及びデータ処理において、特に画像処理において、質の向上した出力データを生成するために入力データにカーネルフィルタを適用することが多い。カーネルフィルタは、データのセットのすべてのポイントに関数を適用することによって作用する。通常、カーネルフィルタは、カーネルと、カーネルに対して定義される関数とを含む。２Ｄ画像における画素の矩形エリアであることが多いカーネルは、関数に対するサポートの領域を指定する。関数は、通常、フィルタ係数の行列の形態である。行列の係数は、フィルタの応答を生成するようにカーネル内の各ポイントの寄与を求める乗算係数である。基礎となる入力データのすべてがフィルタ係数によって乗算された後、現ポイントにおける応答は、その積の和をとることによって求められる。異なるカーネル関数を選択することにより、異なるタイプのフィルタリングを実行することができる。
【０００３】
フィルタリングは、必要な演算量が多い可能性がある。したがって、従来の手法は、たとえばスケールスペース表現を使用して元のカーネルをより小さいカーネルの畳み込みに分解しようとする。これについては、P. Burt著、「Fast filter transforms for image processing」（Computer Vision, Graphics and Image Processing, vol.16, 20-51, 1981）を参照されたい。所与の画像に対し、線形スケール空間表現は、信号を同時に平滑化し且つサブサンプリングすることにより信号のガウスカーネルとの畳み込みによって定義される導出信号のファミリである。このように、計算効率の高い方法を得ることができる。
【０００４】
しかしながら、大量のカーネルのセットとの畳み込みのすべてを実施するためには大量の乗算が必要である。したがって、２Ｄフィルタカーネルを設計し、その後フィルタを分離可能な１次元フィルタ又はカスケード式表現の和に分解することも可能である。これについては、J. Crowley、R. Stern著、「Fast computation of the difference of low-pass transform」（IEEE Trans. Pattern Anal. Machine Intell., vol. 6, 212-222, 1984）、P. Heckbert著、「Filtering by repeated integration」（ACM SIGGRAPH Computer Graphics, vol. 20:4, 315-321, 1986）及びW. Wells著、「Efficient synthesis of Gaussian filters by cascaded uniform filters」（IEEE Trans. Pattern Anal. Machine Intell., vol. 8:2, 234-239, 1986）を参照されたい。これを、２Ｄカーネルの固有値拡張か又は特異値分解（ＳＶＤ）の適用を使用することによって行うことができる。これについては、参照により本明細書に援用される、W. S. Lu、H. P. Wang、A. Antoniou著、「Design of 2D FIR digital filters by using the singular value decomposition」（IEEE Trans. Circuits System, vol. 37, 35-36, 1990）を参照されたい。
【０００５】
２Ｄガウス関数の分離可能性を利用することにより、非等方性すなわち方向に依存するガウスカーネルを、１次元ガウスフィルタとそれに続く非直交方向にある別のフィルタとに分解することが可能である。これについては、J. M. Geusebroek、A. Smeulders、J. Weijer著、「Fast anisotropic Gauss filtering」（IEEE Transaction on Image Processing, vol. 12:8, 2003)を参照されたい。その方法は、畳み込み方式及び再帰的方式を使用するエッジマップ及びリッジマップの高速計算を可能にする。
【０００６】
サムボックス（sum-box）フィルタ技法は、サムボックスフィルタの変換出力の和により或る係数に対する大きいカーネル線形フィルタに近似する。これについては、J. Shen、W. Shen、S. Castan、T. Zhang著、「Sum-box technique for fast linear filtering」（Signal Process., vol. 82:8, 1109-1126, 2002）を参照されたい。その方法は、乗算が不要である。その方法は、スケーリングされたスプライン関数に対する分析を使用する。彼らの方法により、加算のみで大きいフィルタカーネルとの畳み込みを達成することが可能になる。ボックス技法は、乗算を用いてガウスフィルタを実装することができるが、ガウスフィルタ以外の線形フィルタで使用することができない。
【０００７】
別の方法は、ファジィ領域強調方法及び再帰的且つ分離可能ローパスフィルタに基づく。これについては、H. Tang、T. Zhaung、E. X. Wu著、「Realizations of fast 2-D/3-D image filtering and enhancement」（IEEE Trans Medical Imaging, vol. 20:2, 32-40, 2001）を参照されたい。それらは、各画素を独立して処理し、動的範囲と局所変動とを共に変更する。その方法もまた、ガウス関数にしか適用できない。
【０００８】
一方法は、非局所適用ポイントを指定する適応的に求められるベクトルフィールドに基づいて非線形偏微分方程式を解く。これについては、B. Fischl、E. L. Schwartz著、「Adaptive non-local filtering: A fast alternative to anisotropic diffusion for image enhancement」（IEEE Trans. Pattern Anal. Machine Intell., vol. 21:1, 42-48, 1999）を参照されたい。彼らの方法は、画質向上を高速化するが、線形フィルタには適用できない。
【０００９】
多くのフィルタリング方法は、局所空間テクスチャの適応に対し方向推定を使用する。それは、非等方性フィルタリングによる方向のサンプリングを意味することが多い。線形方向スケール空間の場合、非等方性ガウス関数が最適な因果的フィルタである。方向分析は、一組の可操舵非等方性フィルタによって取り組まれている。
【００１０】
Freeman他は、基底フィルタの線形組合せを作成することによってフィルタを特定の方向に調整することができる条件について述べている。これについては、W. T. Freeman、E. H. Adelson著、「The design and use of steerable filters」（IEEE Trans. Pattern Anal. Machine Intell., vol. 13, 891-906, 1991）を参照されたい。彼らの枠組みによれば、非等方性ガウスを回転させるために正確な基底はない。
【００１１】
非等方性ガウス関数に近似する有限基底を生成する方法が、P. Peronaにより、「Steerable-scalable kernels for edge detection and junction analysis」（Image Vis. Comput., vol. 10, 663-672, 1992）において述べられている。しかしながら、基底フィルタの数が多く、基底フィルタは分離不可能であり、高い計算性能が必要である。
【００１２】
フィルタリングプロセスを加速するために再構成可能ハードウェア又はプロセッサ適合ソフトウェアを使用する他の方法がある。特にピラミッド表現を使用する面積和の計算に対し、画像フィルタリング方法のグラフィック処理ユニット（ＧＰＵ）インプリメンテーションもまた利用可能である。これについては、J. Kruger、R. Westermann著、「Linear algebra operators for GPU implementation of numerical algorithms」（ACM Transactions on Graphics, vol. 22:3, 908-916, 2003）を参照されたい。
【００１３】
双線形テクスチャ補間を利用する３次Ｂスプラインを用いる画像の別のＧＰＵベースフィルタリングについては、C. Sigg、M. Hadwigerにより、「Fast third-order texture filtering」（Matt Pharr編、GPU Gems 2: Programming Techniques for High-Performance Graphics, 313-329, 2005）において述べられている。その技法はテクスチャ画像に対するランダムアクセスを可能にするが、画素毎に著しい数のテクスチャルックアップを必要とする。
【００１４】
Strengert他は、ＧＰＵが双線形テクスチャ補間に基づくピラミッド方法を実装することができることを示し、３つの例、すなわち双２次Ｂスプラインフィルタリングを用いるズーミング、任意のぼかし幅の効率的な画像ぼかし、及び分散画素データの滑らか補間について述べている。これについては、M. Strengert、M. Kraus、T. Ertl著、「Pyramid Methods in GPU-Based Image Processing」（In Proc. 11th International Fall Workshop Vision, Modeling, and Visualization, 2006）を参照されたい。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
要約すれば、最も高速なフィルタリング方法は、厳密にフィルタ関数の形状によって決まるか、又は微小な計算上の改善しか提供しない。
【課題を解決するための手段】
【００１６】
本発明は、複数の同一フィルタ係数を有するカーネルフィルタを用いて入力データをフィルタリングする方法を提供する。このようなフィルタ、たとえばガボール（Gabor）フィルタ、移動平均、グレーレベルモルフォロジカル演算子、ボリューム平滑化関数、４象限対称（quad-symmetric）フィルタ等は、多くのコンピュータイメージングタスク及びコンピュータビジョンタスクにおいて広く使用される。利点として、本発明による方法は、特定のフィルタ形状に限定されない。
【００１７】
本発明は、フィルタリングされた出力データが生成される時の冗長な乗算を回避するために、フィルタ係数及び隣接するデータポイントのカーネル間のオーバラップの空間配置を利用する。
【００１８】
本発明は、一組の一意のフィルタ係数を求め、フィルタ係数に対応する一組の相対リンクを構成する。そして、各ポイントにおける応答を累積する一方で、フィルタ係数をそれらの相対リンクを使用して適用することにより入力データを処理して、出力データを生成する。
【００１９】
本発明は、従来のフィルタ処理と比較した場合、平均して４０％の性能向上を達成する、２重解決法、すなわち単一入力アクセス及び単一出力アクセスを提供する。計算上の利点に加えて、本方法は最小量のメモリを使用し、それにより、本方法はハードウェアインプリメンテーションに対して理想的になる。
【発明の効果】
【００２０】
本発明は、複数の同一係数を有するカーネルフィルタの適用を促進する新規な最小主義（minimalist）フィルタリング方法を提供する。本発明による方法は、冗長な乗算を低減するためにカーネル間のオーバラップを利用する。
【００２１】
本発明による最小主義フィルタリングにより、いかなるカーネルフィルタの計算負荷も平均して４０％低減する。従来の方法とは対照的に、本方法は、特定のフィルタ関数に限定されない。本方法を、計算コストを増大させることなく任意の形状のカーネルで使用することができ、それは、コンピュータビジョンアプリケーションにおける形状マッチング等、テンプレート検出タスクに対する必須の特性である。
【００２２】
本方法を、３Ｄボリュメトリック平滑化及びマルチスペクトルフィルタリング等の任意の次元のデータに対して使用することができる。必要なメモリの量は非常に少なく、それにより本方法はハードウェアインプリメンテーションに対する候補になる。さらに、本方法を、並列に、又はＧＰＵ等の特定のハードウェアに実装することができる。また、本方法をピラミッド表現で使用することができる、ということも留意されるべきである。また、より低次元の分離可能基底は、最小主義フィルタリングから利益を得ることができる。
【発明を実施するための最良の形態】
【００２３】
本発明の実施の形態は、図１に示すようにカーネルフィルタを用いて入力データをフィルタリングすることにより、フィルタ応答として出力データを生成する方法を提供する。カーネルフィルタは、画質が向上した出力画像を生成するために入力画像に適用されることが多い。このようなアプリケーションでは、カーネルの中心における画素の値（強度又は色）は、カーネルによってサポートされる近傍画素値によって求められる値に置き換えられる。本発明を、データが２次元であるアプリケーション例を使用して説明するが、本発明を、他の次元を有するデータで動作させることができる、ということが理解されるべきである。
【００２４】
図１は、本発明が使用することができるいくつかのカーネルフィルタ例を示す。通常、カーネルフィルタは、上段に示すようなフィルタ関数１０１と、下段に示す対応するカーネル１０２とを含む。フィルタ関数ｆ（ｋ）１０１は、通常フィルタ係数の行列の形態であり、カーネル１０２の形状Ｓは、ディスク、正方形又は任意であってもよい。示すカーネルフィルタ例には、ガウスフィルタ１１１、ガウスフィルタの上位集合でもある４象限対称フィルタ１１２、ガボールフィルタ１１３、シンク（sinc）フィルタ又はローパスフィルタ１１４及び任意のフィルタ１１５がある。対称フィルタ関数は、通常、ディスク形状カーネル内で定義される。しかしながら、実装を簡略化するために、実際には正方形カーネル又は矩形カーネルが使用されることが多い。任意の形状のカーネルの一例は、テンプレート拡張グレーレベルモルフォロジカルフィルタである。ここで、これらフィルタのうちのいくつかについて、より詳細に説明する。
【００２５】
ガボールフィルタ
ガボールフィルタは、ガウス関数によって乗算される調和関数によって定義されるインパルス応答を有する線形フィルタである。乗算・畳み込み特性のために、ガボールフィルタのインパルス応答のフーリエ変換は、調和関数のフーリエ変換とガウス関数のフーリエ変換との畳み込みである。
【００２６】
したがって、ガボールフィルタは、空間領域と周波数領域との両方において最適な局所化特性を有する。したがって、ガボールフィルタは、テクスチャセグメンテーション、ターゲット検出、虹彩認識、画像符号化及び画像表現等の多くのアプリケーションに適している。
【００２７】
ガボールフィルタを、ｓ（ｘ１，ｘ２）がキャリアとして知られる調和関数であり、ｇがエンベロープとして知られる２Ｄガウス関数である場合、ｆ（ｘ１，ｘ２）＝ｓ（ｘ１，ｘ２）ｇ（ｘ１，ｘ２）として表すことができる。キャリアは、一般に、ｘ’＝ｘ１ｃｏｓθ＋ｘ２ｓｉｎθである場合、実関数
【００２８】
【数１】
2008226233.tif 000003
【００２９】
として割り当てられ、エンベロープは以下の通りである。
【００３０】
【数２】
2008226233.tif 000004
【００３１】
上記式では、λは波長を表し、θは空間中心周波数を表し、ψは位相オフセットを表し、σｘ１、σｘ２は楕円ガウスエンベロープの標準偏差である。一般に、さまざまなスケール及び回転を有するガボールフィルタを含むフィルタバンクを使用して、すべての周波数空間がカバーされる。
【００３２】
４象限対称フィルタ
４象限対称フィルタは、画像雑音除去、照明補正、動き推定及びビデオ処理等のアプリケーションに対して有用な線形カーネルフィルタである。４象限対称フィルタは、カーネルの中心における画素を、近傍画素の重み付き平均によって置き換える。４象限対称フィルタを、ｇが任意の形状の関数であり、（ｘｃ，ｙｃ）がカーネルの中心である場合、
ｆ（ｘ１，ｘ２）＝ｇ（｜ｘ１−ｘｃ１，ｘ２−ｘｃ２｜）
として表すことができる。４象限対称フィルタは、２つの画素値間の距離を求めることができる限り、所与の状況に容易に適応することができる。４象限対称フィルタはまた非反復的であり、それにより、単一パスのみで十分な結果が得られる。このフィルタは非常に有用であるが、比較的低速である。妥当なサイズの画像に対する力任せな（brute-force）計算は、数十分台になる可能性がある。それでもなお、４象限対称フィルタの評価を高速化する解決法が知られており、たとえば正確な計算を実行するが特定のシナリオに制限される専用フィルタ、及び正確な結果をもたらさないか又はダウンサンプリング及びより高次元空間におけるローパスフィルタリングに依存する近似フィルタである。
【００３３】
最小主義フィルタリング
本発明によるカーネルフィルタは、ｄ次元実数値デカルト空間Ｒｄにおいて定義される。フィルタは、その空間におけるデータポイントｐ＝［ｘ１，・・・，ｘｄ］を中心とするカーネルフィルタＳ内の入力データＩを、以下のようにｍ次元応答ベクトル又は出力データにマップする。
Ｉ（ｐ；Ｓ）→ｙ（ｐ）＝［ｙ１，・・・，ｙｍ］
【００３４】
ここで、一般性を失うことなく、スカラーにマップする、すなわちｍ＝１である線形フィルタ、したがってｙ（ｐ）＝ｙ１を考慮する。フィルタは、実数値係数ｆ（ｐ）を、カーネルＳのデータポイントｐの各々に割り当てる。フィルタリングされるデータは、範囲Ｎ１，・・・，Ｎｄ内に制限され、すなわち０≦ｘ１＜Ｎｉである。なお、時間成分が３次元を構成するため、単一チャネル画像フィルタはｄ＝２で定義され、カラーフィルタ及びビデオフィルタはｄ＝３で定義されることに留意されたい。
【００３５】
この表記法から、カーネルフィルタの応答を以下のように表すことができ、
【００３６】
【数３】
2008226233.tif 000005
【００３７】
これは、相関と同じである。応答を、単一パスにおけるフィルタ係数の有界集合によって求めることができるため、カーネルフィルタはまた、有限インパルス応答（ＦＩＲ）フィルタでもある。正方形カーネルが［−Ｋ１／２，Ｋ１／２］、［−Ｋ２／２，Ｋ２／２］内に制限される従来の２Ｄ画像フィルタリングの場合、応答は以下のようになる。
【００３８】
【数４】
2008226233.tif 000006
【００３９】
応答を、符号を変えることによって畳み込みに対して変更することができる。
【００４０】
図２は、従来のカーネルフィルタリング方法の場合の擬似コードである。
【００４１】
上記式を変更なしに実装しがちであるが、本発明者は、それはまた、カーネルが同じ係数を含む場合、カーネル内のそれらの位置に関わらず、同じ係数による画素値の乗算を何回ももたらすという事実を強調する。これは、時間及び資源を消耗する。
【００４２】
したがって、本発明の一実施の形態による最小主義フィルタリング方法は、まず、図３Ａ〜図３Ｃに示すように、一組の一意のフィルタ係数ｗｉ（ｉ＝１，・・・，Ｕ）３１０を求める。次に、本方法は、ポイント３２０に基づいて、各一意のフィルタ係数ｗｉに対してリンクセットＬｉ３３０を、リンクセットが同一のフィルタ係数を有するフィルタにおける位置に対する相対リンクを含むように、すなわちＬｉ＝｛ｌｉｏ，・・・，ｌｉＬｉ｝であるように構成する。
【００４３】
各相対リンクｌｉｊは、フィルタ係数の位置の逆数であり、すなわち、フィルタ位置が（ｘ１，ｘ２）である場合、相対リンクは、カーネルのインデックス付けに関して（−ｘ２，−ｘ２）である。一意のフィルタ係数及び相対リンクは、オフラインで又は前処理段階でカーネルフィルタに対して一度事前に求められる。
【００４４】
一意のフィルタ係数３１０及び相対リンク３３０を求めた後、一度に１つの入力ポイントでデータを処理する。カーネルの中心が置かれる値を一意のフィルタ係数の各々によって乗算し、その結果を相対リンクによって参照されるように複数の出力ポイントの応答に加算する。すなわち、以下の通りである。
【００４５】
【数５】
2008226233.tif 000007
【００４６】
図３Ａに示すように、最小主義フィルタリング方法は、まず、何らかの任意の形状のカーネル３０１における各位置に対し、一度、オフライン段階で一意のフィルタ係数ｗｉ（ｉ＝１，・・・，Ｕ）３１０を求める。そして、本方法は、同じ係数を有するポイント３２０と対応する相対リンク３３０とを求める。すなわち、本方法は、ｐｉｊ＝（ｘ１（ｉ，ｊ），ｘ２（ｉ，ｊ））及びｌｉｊ＝（−ｘ１（ｉ，ｊ），−ｘ２（ｉ，ｊ））を求める。
【００４７】
図３Ｂは、カーネル３０１が、たとえば線状に又は「ラスタ」スキャン順に画像３４２にわたって「掃引される（swept）」（３４０）本発明による方法のオンライン段階を示す。データポイント（画素）Ｉ（ｘ１，ｘ２）（３５０）に対し、ポイントは、対応する相対リンク３７０を使用して重み付けされる（３６０）。
【００４８】
フィルタ行列に基礎となるデータを直接乗算する代りに、最小主義フィルタリング方法は、一意のフィルタ係数を選択し、その後、各一意のフィルタ係数に対し一度だけ入力画素値を乗算する一方で、結果を、対応する相対リンクを使用して対応する出力画素に加算する。
【００４９】
この方法は、キャッシュのサイズが制限されるストリームプロセッサに適している。このため、アクセスされる必要のあるデータの量が最小限になる。単一入力アクセスでは、フィルタ応答は累進的に求められ、図３Ｃの擬似コードに示すようにカーネルにおけるポイントのすべてが処理されると、出力が生成される。
【００５０】
図４に示すように、ここではまた、フィルタカーネル４０２を用いて画像４０１をフィルタリングすることによりフィルタリングされた画像４０３を生成する二重方法について説明する。入力のカーネルサイズブロック４１０を、各反復で処理する。上述したように、本発明者は、一意の係数ｗｉ及び相対リンクセットを見つける。二重方法は、現カーネル内の入力を取得し、各相対リンクに対するポイントの合計４２０を見つける。そして、本方法は、これら合計を対応する一意の係数と乗算することにより出力ポイントの値を割り当て、それら和を合計する（４３０）。すなわち、以下のようになる。
【００５１】
【数６】
2008226233.tif 000008
【００５２】
図５は、単一出力アクセスでの単一出力ポイントに対する応答を求める二重方法に対する擬似コードを示す。
【００５３】
このように、単一出力ポイントに対するフィルタ応答を求める。画像は各一意の係数に対して一度乗算されるため、この方法は、フィルタリングをさらに加速させるためにＧＰＵを利用することができる。
【００５４】
上述した方法を、デジタルプロセッサ又は特定用途向け集積回路（ＡＳＩＣ）で実装することができる、ということが理解されるべきである。
【００５５】
計算上の改良
表Ａに、通常、整数加算演算のコストに対して測定される、プロセッサ演算の相対コストに関する詳細な計算複雑性分析を示す。
【００５６】
【表１】
2008226233.tif 000009
【００５７】
表Ａには、本発明の結果と共に従来の方法の基本演算の相対コストを提示する。高次元のデータになるほど配列インデックス付けのコストがそれに匹敵するようになるため、配列インデックス付けのコストも考慮する。データポイントのｄ次元配列の場合、データにアクセスするためには、ｄ回の整数加算、ｄ−１回の整数乗算が必要である。本発明者は、プロセッサ上での乗算累算ユニット（ＭＡＣ）のハードウェア統合使用により、加算及び乗算のコストは同じデータタイプに対して等しいままであることに気づいた。
【００５８】
表Ａにおいて、演算子列はさまざまな演算を示す。列Ａは、S. Ouallineにより、「Practical C++ programming」（O'Reilly & Associates, ISBN: 1-56592-139-9, 1995）において述べられているような基本プロセッサ演算子の相対コストである。列Ｂは、ストリーミングＳＩＭＤ及びＰｒｅｓｃｏｔｔ算術演算を使用するＰ４プロセッサで実行される演算子のコストである。これについては、R. Bryant、D. O'Hallaron著、「Computer systems: a programmer's perspective」（Prentice Hall, ISBN 0-13-034074-1, 2003）を参照されたい。列Ｃは、Ｃ＋＋コンパイラを実行するＰ４における相対コストである。これについては、J. Mathew、P. Coddington、K. Hawick著、「Analysis and development of java grande benchmarks」（Proceedings of ACM, 1999）を参照されたい。列Ｄは、ＭＳＶＣ＋＋コンパイラを実行するＩｎｔｅｌ  Ｐ４プロセッサの場合であり、これについては、F. Porikli著、「Integral histogram: a fast way to extract histograms in Cartesian spaces」（Proc. Computer Vision and Pattern Recognition Conference, vol. 1, 829-836, 2005）を参照されたい。最後の列は本発明による方法に対するコストである。
【００５９】
入力データが浮動小数点値であり、カーネルにおけるポイントの総数がＡである、すなわち矩形カーネルＡ＝ΠｄｉＫｉの場合を想定する。従来のカーネルフィルタリング方法では、フィルタ応答を計算するために以下のタスクが必要である。
現ポイントのインデックスを見つける：Ａ回のｄ次元配列インデックス付け及び２Ａ回の加算、
現ポイントがカーネルにあるか否かを検査する：ｄ次元配列インデックス付け及び比較、
フィルタ係数により乗算する：Ａ回の乗算、
乗算の和を割り当てる：Ａ−１回の加算及びｄ次元配列インデックス付け。
【００６０】
単一データポイントの場合、従来のフィルタリングでは、データ空間におけるカーネル内の寄与ポイントのインデックスを計算しそれらの値にそれぞれアクセスするために２Ａ＋（２ｄ−１）Ａ回の演算が必要である。非矩形カーネルを使用する場合、ポイントがカーネルに属するか否かを求めるために２つの制御条件があり得る。すなわち、より大きい適切な矩形配列とカーネルメンバシップを表すバイナリマスクとを使用することか、又はインデックス値から距離ベースの基準を計算することである。本発明者は、本発明による結果から、マスクを使用することにより計算負荷が低減することが分った。検査段階には、（２ｄ−１）Ａ＋Ａ＝２ｄＡ回の演算が必要である。
【００６１】
カーネル内の各データポイントの浮動小数点値を、対応するフィルタ係数によって乗算することにより、１５Ａ回の演算となる。乗算の浮動小数点和の計算には１５（Ａ−１）回の演算が必要であり、一方で和をフィルタ応答として割り当てるためには２ｄ−１回の演算のみが必要である。なお、先の計算が、データ内のＮ１×・・・×Ｎｄポイントの各々に対して繰り返されることに留意されたい。そして、すべての候補に対して必要な演算の総数は以下のようになる。
【００６２】
【数７】
2008226233.tif 000010
【００６３】
一方、最小主義フィルタリングは、同じ係数による乗算を繰り返さず、任意の形状のカーネルに対して条件付きの検査を必要としない。カーネルフィルタの適用前に、フィルタは一意の係数を求めるために前処理され、各一意の係数に対する相対リンクのセットを構成する。なお、これはオフライン段階においてそのフィルタに対し一度だけ行われることに留意されたい。すなわち、それは、実際のオンラインフィルタリングプロセス中に繰り返されない。このオフライン段階後、最小主義フィルタリングはこれらステップを必要とする。
１）現ポイント値を取得する：ｄ次元配列インデックス付け、
２）一意の係数によって乗算する：Ｕ回の乗算、
３）ポイントのインデックスを見つける：Σｌｉ回のｄ次元配列インデックス付け及び２ΣＬｉ回の加算、
４）ポイント値を増分する：ΣＬｉ回の加算。
【００６４】
各データポイントにおいて、最小主義フィルタリングは、現データポイントの値を取得するために２ｄ−１回の演算を採用する。そして、浮動小数点値を一意の係数の各々によって乗算し、それには１５Ｕ回の演算が必要である。相対リンクの総数がカーネルにおけるポイントの総数に等しいため（ΣＵｉＬｉ＝Ａ）、カーネル内のポイントのインデックスを見つけるために、相対リンクをデータポイントインデックスに変換するための２Ａ回の整数加算と、Ａ回の配列インデックス付けとが必要であり、それにより（２ｄ＋１）Ａ回の演算となる。その結果、この段階の計算負荷は（２ｄ＋１）Ａ回の演算である。
【００６５】
対応する乗算結果を、出力配列データポイントのフィルタ応答に加算する。これには、浮動小数点加算に対して１５Ａ回の演算が必要であり、出力配列にアクセスするために（２ｄ−１）Ａ回の演算が必要である。そして、演算の総数は以下のようになる。
【００６６】
【数８】
2008226233.tif 000011
【００６７】
最小主義フィルタリングによって達成される計算上の節約のパーセンテージに対応する低減率を以下のように定義する。
【００６８】
【数９】
2008226233.tif 000012
【００６９】
この数は、最小主義フィルタリングを使用することにより何パーセントの計算が回避されるかを表す。また、一意の係数のすべての係数に対する割当てを表すために冗長性スコアを以下のように提供する。
【００７０】
【数１０】
2008226233.tif 000013
【００７１】
量子化、対称性及び分離可能性の効果
最小主義フィルタリングの成功は、一意の係数の数がより少ないことからもたらされる。この数が大きい、すなわちカーネルにおけるポイントの総数に等しい場合、Ｕ＝Ａである。
【００７２】
このため、最小主義フィルタリングは従来のフィルタリングまで後退する。しかしながら、カーネルフィルタのほとんどすべてが有する一意の係数は非常にわずかである。量子化は、より少ない数の一意の係数を取得する適当な方法である。カーネル原点の周囲で対称な２Ｄカーネルフィルタの場合、最小冗長性スコアは７５％である。言い換えれば、量子化が全くなくても、本発明による最小主義フィルタリング方法は、依然として、必要な計算を元の負荷の１／４まで大幅に低減する。
【００７３】
全体を通しての分析を提供するために、本発明者は、広く使用されるフィルタ、すなわちガウスフィルタ、４象限対称フィルタ、ガボールフィルタ、シンクフィルタ及びエッジフィルタをテストした。表Ｂは、２１×２１カーネルにおけるさまざまな２Ｄフィルタに対する５０ｄＢでの平均計算節約を示す。
【００７４】
【表２】
2008226233.tif 000014
【００７５】
本発明者はまた、種々の次元のデータにおける性能変化を分析した。図６に示すように、部分的には配列アクセスコストが低減する結果として、次元が低減するに従い節約が増大する。なお、節約は次元データが低いほどはるかに高くなることに留意されたい。言い換えれば、最小主義フィルタリングは、低次元の分離可能なカーネルを使用する場合にさらに高い利得を提供する。さらに、次元が高いほど、節約はフィルタサイズに左右されなくなる。図６はまた、分離可能フィルタの場合、改善がさらに高くなることも示す。示すように、冗長係数の数が増大するに従い、計算節約が増大する。ドット６０１〜６０３は、出力にいかなる顕著な変化もない平均利得４３％、４０．５％及び３７％を示す。
【００７６】
図７は、負荷及びフィルタサイズの関数として従来のフィルタリング７０１を本発明による最小主義２Ｄフィルタリング７０２と比較する。カーネルサイズが増大するに従い、最小主義方法はより有利になる。たとえば、フィルタサイズ３０に対する負荷は約４０％未満である。
【００７７】
図８Ａ及び図８Ｂは、１３×１３  ４象限対称カーネルを使用する５０ｄＢフィルタリングでの従来のフィルタリングと最小主義フィルタリングとの間に目に見える差がないことを示す。図８Ａは、冗長性のない従来の４象限対称フィルタリングを示し、図８Ｂは９８％冗長性を有する最小主義フィルタリングを示す。
【００７８】
本発明を、好ましい実施の形態の例を用いて説明したが、本発明の精神及び範囲内で他のさまざまな適応及び変更を行うことができる、ということが理解されなければならない。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内にあるこのような変形及び変更のすべてを包含することである。
【図面の簡単な説明】
【００７９】
【図１】本発明の実施の形態によって使用されるカーネルフィルタの図である。
【図２】従来技術によるフィルタリング方法の擬似コードのブロック図である。
【図３Ａ】本発明の一実施の形態によるフィルタリング方法のオフライン段階のブロック図である。
【図３Ｂ】本発明の一実施の形態によるフィルタリング方法のオンライン段階のブロック図である。
【図３Ｃ】本発明の一実施の形態によるフィルタリング方法の擬似コードのブロック図である。
【図４】本発明の一実施の形態による二重フィルタリング方法のブロック図である。
【図５】図４の二重方法の擬似コードのブロック図である。
【図６】多次元データに対するフィルタ係数における冗長性の関数として計算低減率（Ｒ）を比較するグラフである。
【図７】従来のフィルタリングと本発明の一実施の形態によるフィルタリングとに対するフィルタサイズの関数として計算負荷を比較するグラフである。
【図８Ａ】従来のフィルタリングを用いた画像である。
【図８Ｂ】本発明の一実施の形態によるフィルタリングを用いた画像である。
【図１】
2008226233.tif 000018
【図２】
2008226233.tif 000019
【図３Ａ】
2008226233.tif 000020
【図３Ｂ】
2008226233.tif 000021
【図３Ｃ】
2008226233.tif 000022
【図４】
2008226233.tif 000023
【図５】
2008226233.tif 000024
【図６】
2008226233.tif 000025
【図７】
2008226233.tif 000026
【図８Ａ】
2008226233.tif 000027
【図８Ｂ】
2008226233.tif 000028
【外国語明細書】
2008226233.tif 000029
2008226233.tif 000030
2008226233.tif 000031
2008226233.tif 000032
2008226233.tif 000033
2008226233.tif 000034
2008226233.tif 000035
2008226233.tif 000036
2008226233.tif 000037
2008226233.tif 000038
2008226233.tif 000039
2008226233.tif 000040
2008226233.tif 000041
2008226233.tif 000042
2008226233.tif 000043
2008226233.tif 000044
2008226233.tif 000045
2008226233.tif 000046
2008226233.tif 000047
2008226233.tif 000048
2008226233.tif 000049
2008226233.tif 000050
2008226233.tif 000051
2008226233.tif 000052
2008226233.tif 000053
2008226233.tif 000054
2008226233.tif 000055
2008226233.tif 000056
2008226233.tif 000057
2008226233.tif 000058
2008226233.tif 000059
2008226233.tif 000060
2008226233.tif 000061
2008226233.tif 000062
2008226233.tif 000063
2008226233.tif 000064
2008226233.tif 000065
2008226233.tif 000066