(57)【特許請求の範囲】
【請求項１】
第１の複数の差分画像および多数ｎの後続する複数の差分画像を取得するための並列計算のための方法であって、
ａ．複数の画素によって画成された原画像から第１の複数の差分画像を取得する工程であって、前記第１の複数の差分画像が、
ｉ．複数のボケ畳み込み関数を提供する工程であって、前記ボケ畳み込み関数の各々は、前記原画像の畳み込み時に前記原画像の増大するボケの程度を提供する工程と、
ｉｉ．２つの前記ボケ畳み込み関数間の差を算出することにより複数の差分畳み込み関数Ｄｉｆを確立する工程であって、前記２つのボケ畳み込み関数の各々は、前記原画像の畳み込み時に前記原画像のボケの異なる程度を提供する工程と、
ｉｉｉ．差分画像を取得するために、前記差分畳み込み関数Ｄｉｆの各々を前記原画像と畳み込むことによって、前記原画像から複数の差分画像を算出する工程と、
によって取得される工程と、
ｂ．前記複数のボケ畳み込み関数をダウンサンプリング関数およびアンチエイリアシング関数で畳み込むことによって、第１のダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ(1)を取得する工程と、
ｃ．ｎが１よりも大きい場合、以前のダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｔ−１）を、前記複数のボケ畳み込み関数、ダウンサンプリング関数、およびアンチエイリアシング関数と畳み込むことで、付加的なダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｔ）を取得する工程であって、ｔ＝２でこの工程ｃを始め、単一増分でｔを増加させながらｔがｎに達するまでこの工程を繰り返す工程と、
ｄ．ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｘ）の各々について画像（ｘ）を取得すべく、前記ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎの全てを前記原画像と畳み込む工程と、
ｅ．後続するｎ個の複数の差分画像を取得して、各々の画像（ｘ）から各複数（ｘ）を取得する工程と、を備え、
前記ボケ畳み込み関数が、ガウシアンである、方法。
【請求項２】
前記原画像におけるスケール不変特徴を識別する方法に使用される、請求項１記載の方法。
【請求項３】
前記複数の差分畳み込み関数は、一旦確定され、前記差分画像の後続計算に繰り返し使用される、請求項１記載の方法。
【請求項４】
前記差分畳み込み関数Ｄｉｆが多項式によって近似される、請求項１記載の方法。
【請求項５】
前記原画像におけるスケール不変特徴を識別する方法であって、識別された画像特徴は、複数の画素によって画成される画像内で種々のスケールにわたって安定しており、多重フィルタリング工程およびリサンプリング工程が並行して実施され得る、方法において、
ａ．多重差分画像を取得する工程と、
ｂ．前記多重差分画像における画素振幅極値を検索する工程と、
ｃ．各差分画像内の各画素について画素勾配ベクトルを生成する工程と、
ｄ．ベクトルの向きを、各差分画像に関連するそれぞれの実際の最大および最小振幅画素と関連付ける工程と、
を備えた、請求項２記載の方法。
【請求項６】
複数の画素によって画成された原画像から複数の差分画像を取得するための並列計算のための画像処理装置であって、前記装置は、前記原画像に関するデータを受信するための手段、前記差分画像を送信または記憶するための手段、およびプロセッサ回路を備え、前記プロセッサ回路は、
ａ．前記原画像から第１の複数の差分画像を取得し、前記第１の複数の差分画像が、
ｉ．複数のボケ畳み込み関数を提供し、前記ボケ畳み込み関数の各々は、前記原画像の畳み込み時に前記原画像の増大するボケの程度を提供し、
ｉｉ．２つの前記ボケ畳み込み関数間の差を算出することにより複数の差分畳み込み関数Ｄｉｆを確立し、前記２つのボケ畳み込み関数の各々は、前記原画像の畳み込み時に前記原画像のボケの異なる程度を提供し、
ｉｉｉ．差分画像を取得するために、前記差分畳み込み関数Ｄｉｆの各々を前記原画像と畳み込むことによって、前記原画像から複数の差分画像を算出し、
ｂ．前記複数のボケ畳み込み関数をダウンサンプリング関数およびアンチエイリアシング関数で畳み込むことによって、第１のダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ(1)を取得し、
ｃ．ｎが１よりも大きい場合、以前のダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｔ−１）を、前記複数のボケ畳み込み関数、ダウンサンプリング関数、およびアンチエイリアシング関数と畳み込むことで、付加的なダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｔ）を取得し、ｔ＝２でこの工程ｃを始め、単一増分でｔを増加させながらｔがｎに達するまでこの工程を繰り返し、
ｄ．ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｘ）の各々について画像（ｘ）を取得すべく、前記ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎの全てを前記原画像と畳み込み、
ｅ．後続するｎ個の複数の差分画像を取得して、各々の画像（ｘ）から各複数（ｘ）を取得し、前記ボケ畳み込み関数が、ガウシアンである、画像処理装置。
【請求項７】
前記プロセッサ回路は、チップを含む、請求項６記載の画像処理装置。
【請求項８】
画像処理装置は複数のチップを備え、各チップは少なくとも一つの差分画像を計算するように構成される、請求項６記載の画像処理装置。
【請求項９】
前記画像処理装置は双線形補間器を備え、前記双線形補間器は、乗加算器（ＭＡＣ）、遅延線加算器、および制御論理ブロックを含んでなる、請求項６記載の画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、畳み込んだデータの並列計算に関するものである。特に、本発明は、ＳＩＦＴアルゴリズムで使用するための繰り返し畳み込んだデータの並列演算などのような、画像データの並列処理に適したガウシアンピラミッド構築の効率的な計算に関するものである。
【背景技術】
【０００２】
とりわけ、米国特許第６７１１２９３号に開示された従来のＳＩＦＴアルゴリズムは、画像中のスケール不変特徴を識別するための方法および装置と、画像内のオブジェクトを検索するための、これら特徴の使用を開示している。
【０００３】
米国特許出願公開２０１０／０１６９５７６には、スケール不変特徴変換アルゴリズムを実装するための方法が開示されているが、ここでは、ガウシアン画像の差分は、入力画像をガウシアンフィルタの差で畳み込むことで得られる。この出願では、プロセスが並行して行われてもよいことになっているが、実際の並列実装については触れていない。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来のＳＩＦＴアルゴリズムは、逐次型プロセッサを使用する実装に適した直列アルゴリズムとして設計された。従来のＳＩＦＴアルゴリズムの速度を増大させるためには、並列プロセスとしてアルゴリズムを実行するように企図されてもよい。しかしながら、従来のＳＩＦＴアルゴリズムは、多数のステップからなっており、ステップの結果は後続を計算するための必須条件である。したがって、従来のＳＩＦＴアルゴリズムは、それ自体が容易に並列処理に適したものとはならない。
【０００５】
本発明の発明者は、驚くべきことに、従来のＳＩＦＴアルゴリズムにおける特定のステップは、並列処理を可能にするために改変され得ることを発見した。さらに、発明者は、このような改変により、手法をハードウェアに組み込むことができることを見出したため、これによって、アルゴリズムを実装した既知のソフトウェアと比較して、計算速度の驚異的な増大が可能となった。
【課題を解決するための手段】
【０００６】
一態様によれば、本発明は、複数の画素によって画成される画像においてスケール不変特徴を識別する方法で使用する差分画像を取得するための方法に関し、この方法は、２つの異なるボケ畳み込み関数間の差を算出することにより差分畳み込み関数値Ｄｉｆを計算し、前記２つの異なるボケ畳み込み関数の各々は、原画像を畳み込むことで原画像の異なるボケの程度を提供し、差分画像を取得するために前記差分畳み込み関数値Ｄｉｆを原画像と畳み込むことからなるものである。差分畳み込み関数は、好ましくは一度だけ計算され、その後、異なる画像に対して繰り返し使用してもよい。
【０００７】
一態様によれば、本発明は、複数の画素によって画成される画像におけるスケール不変特徴を識別する方法において使用する複数の差分画像を取得するための方法に関し、この方法は、複数のボケ畳み込み関数を提供し、前記畳み込み関数の各々は前記原画像の畳み込み時に原画像の増大するボケの程度を提供し、原画像から複数の差分画像を算出するものである。ボケ畳み込み関数は、好ましくは一度だけ計算され、その後、異なる画像に対して繰り返し使用することができる。ガウシアンボケ関数を用いると、その関数を畳み込むことによって得られる関数の幅を取得するためには、関数の幅を追加すれば足りる。
【０００８】
一態様によれば、本発明は、複数の画素によって画成される原画像から複数の差分画像を取得するための方法に関し、前記方法は、
ａ．複数のボケ畳み込み関数を提供する工程であって、前記畳み込み関数の各々は前記原画像の畳み込み時に原画像の増大するボケの程度を提供する工程と、
ｂ．２つの前記ボケ畳み込み関数間の差を算出することにより複数の差分畳み込み関数値Ｄｉｆを確立する工程であって、前記２つのボケ畳み込み関数の各々は、前記原画像の畳み込み時に原画像のボケの異なる程度を提供する工程と、
ｃ．差分画像を取得するために、前記差分畳み込み関数値Ｄｉｆの各々を前記原画像と畳み込むことによって、前記原画像から複数の差分画像を算出する工程と、を備える。
【０００９】
一態様によれば、本発明は、第１の複数の差分画像および少なくとも１つの後続する複数の差分画像を取得するための方法に関し、前記方法は、
ａ．複数のボケ畳み込み関数を用いて、本発明により原画像から前記第１の複数の差分画像を取得する工程と、
ｂ．ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎを取得するために、前記複数のボケ関数をダウンサンプリング関数およびアンチエイリアシング関数で畳み込む工程と、
ｃ．後続画像を取得するために、前記ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎを前記原画像と畳み込む工程と、
ｄ．本発明により後続画像から後続する複数の差分画像を取得する工程と、
ｅ．任意に、前記原画像として前記後続画像を用い、付加的な後続する複数の差分画像を取得するために、上記ｃおよびｄの工程を繰り返す工程と、
を備える。
【００１０】
一態様によれば、本発明は、第１の複数の差分画像および少なくとも１つの後続する複数の差分画像を取得するための方法であって、前記方法は、
ａ．複数のボケ畳み込み関数を用いて、請求項１乃至８のいずれか一項に記載の方法により原画像から前記第１の複数の差分画像を取得する工程と、
ｂ．第１の画像を取得するために、ボケた原画像をダウンサンプリングする工程と、
ｃ．ダウンサンプリング・アンチエイリアシング畳み込み関数Ａｃｏｎを取得するために、前記複数のボケ関数をアンチエイリアシング関数と畳み込む工程と、
ｄ．後続画像を取得するために、取得されたアンチエイリアシング畳み込み関数Ａｃｏｎを第１の画像と畳み込む工程と、
ｅ．請求項１乃至８のいずれか一項に記載の方法により前記後続画像から後続する複数の差分画像を取得する工程、
ｆ．任意に、前記後続画像前記原画像を表示し、付加的な後続する複数の差分画像を取得するために、上記ｂ、ｃおよびｄの工程を繰り返す工程と、
を備える。
【００１１】
一態様によれば、本発明は、第１の複数の差分画像および多数ｎの後続する複数の差分画像を取得するための方法であって、前記方法は、
ａ．複数のボケ畳み込み関数を用いて、本発明により原画像から前記第１の複数の差分画像を取得する工程と、
ｂ．ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎを取得するために、前記複数のボケ関数をダウンサンプリング関数およびアンチエイリアシング関数で畳み込む工程と、
ｃ．後続画像を取得するために、前記ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎを前記原画像と畳み込む工程と、
ｄ．本発明により後続画像から後続する複数の差分画像を取得する工程と、
ｅ．任意に、前記原画像として前記後続画像を用い、付加的な後続する複数の差分画像を取得するために、上記ｃおよびｄの工程を繰り返す工程と、
を備える。
【００１２】
一態様によれば、本発明は、複数の画素によって画成される画像内で種々のスケールにわたって安定した画像特徴を識別するための方法であって、多重フィルタリング工程およびリサンプリング工程が並行して実施され得る方法において、前記方法は、
ａ．本発明の方法により多重差分画像を取得する工程と、
ｂ．前記多重差分画像における画素振幅極値を検索する工程と、
ｃ．各差分画像内の各画素について画素勾配ベクトルを生成する工程と、
ｄ．ベクトルの向きを、各差分画像に関連するそれぞれの実際の最大および最小振幅画素と関連付ける工程と、
を備える。
【００１３】
一態様によれば、本発明は、複数の画素によって画成される原画像から複数の差分画像を取得するための画像処理装置であって、前記装置は、前記第１の画像に関するデータを受信するための手段と、前記差分画像を送信または記憶するための手段、および処理手段を備え、差分画像を取得するために、複数の差分ボケ関数Ｄｉｆの各々を前記原画像に畳み込むことによって原画像から複数の差分画像を算出し、前記複数の差分畳み込み関数Ｄｉｆは、２つのボケ畳み込み関数間の差を計算することによって確立され、前記２つのボケ畳み込み関数の各々は、前記原画を畳み込むと前記原画像の異なるボケの程度を提供する。
【００１４】
一態様によれば、本発明は、複数の画素によって画成される画像におけるスケール不変特徴を識別するための画像処理装置であって、前記画像処理装置は、本発明の方法を実装するように構成されたプロセッサ回路を備える。
【００１５】
一態様によれば、本発明は、複数の画素によって画成される原画像から差分画像を複数取得するためのソフトウェアプログラムであって、前記ソフトウェアプログラムは、複数のプロセッサに以下の動作をもたらす：前記複数のプロセッサが並行して異なる差分画像を算出するように、複数の差分ボケ関数Ｄｉｆの各々を前記原画像に畳み込むことによって原画像から複数の差分画像を算出し、前記差分畳み込み関数値Ｄｉｆは、２つのボケ畳み込み関数の差を計算することによって確立され、前記２つのボケ畳み込み関数の各々は、前記原画を畳み込むと前記原画像の異なるボケの程度を提供する。
【００１６】
一態様によれば、本発明は、複数の画素によって画成された画像においてスケール不変特徴を識別するためのソフトウェアプログラムであって、前記ソフトウェアプログラムが請求項１〜１２のいずれか一項に記載の方法を実装するように構成される。
［詳細な開示］
追加の態様および実施形態を以下に記載する。
【００１７】
実施形態によれば、本発明は、複数の画素によって画成される原画像から複数の差分画像を取得するための方法であって、
ａ．複数のボケ畳み込み関数を提供する工程であって、前記畳み込み関数の各々は前記原画像の畳み込み時に原画像の増大するボケの程度を提供する工程と、
ｂ．２つの前記ボケ畳み込み関数間の差を算出することにより複数の差分畳み込み関数値Ｄｉｆを確立する工程であって、前記２つのボケ畳み込み関数の各々は、前記原画像の畳み込み時に原画像のボケの異なる程度を提供する工程と、
ｃ．差分画像を取得するために、前記差分畳み込み関数値Ｄｉｆの各々を前記原画像と畳み込むことによって、前記原画像から複数の差分画像を算出する工程と、
を備える。
【００１８】
この方法の特有な利点は、並列処理に容易に適応できることである。
【００１９】
実施形態によれば、本発明は、複数の前記差分画像が並列に計算される方法に関する。
【００２０】
実施形態によれば、本発明は、前記原画像におけるスケール不変特徴を識別する方法で使用するために、本発明による方法に関する。
【００２１】
実施形態によれば、本発明は、本発明に係る方法であって、前記複数の差分ボケ畳み込み関数は、一旦確定され、前記差分画像の後続計算に繰り返し使用される。ボケ畳み込み関数および／または差分畳み込み関数は、好ましくは一度だけ計算され、その後、異なる画像に対して繰り返し使用することができる。畳み込み関数は、単一チップのようなハードウェアに実装してもよい。
【００２２】
実施形態によれば、本発明は、前記ボケ畳み込み関数がガウシアン関数である、本発明よる方法に関する。ガウシアンボケ畳み込み関数を使用すると、その関数を畳み込むことによって得られる関数の幅を取得するためには、その関数の幅を追加すれば足りる。
【００２３】
実施形態によれば、本発明は、前記差分畳み込み関数値Ｄｉｆが多項式によって近似される、本発明による方法に関する。
【００２４】
実施形態によれば、本発明は、第１の複数の差分画像および少なくとも１つの後続する複数の差分画像を取得するための方法であって、
ａ．複数のボケ畳み込み関数を用いて、請求項１乃至６のいずれか一項に記載の方法により原画像から前記第１の複数の差分画像を取得する工程と、
ｂ．ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎを取得するために、前記複数のボケ関数をダウンサンプリング関数およびアンチエイリアシング関数で畳み込む工程と、
ｃ．後続画像を取得するために、前記ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎを前記原画像と畳み込む工程と、
ｄ．請求項１乃至６のいずれか一項に記載の方法により後続画像から後続する複数の差分画像を取得する工程と、
ｅ．任意に、前記原画像として前記後続画像を用い、付加的な後続する複数の差分画像を取得するために、上記ｃおよびｄの工程を繰り返す工程と、
を備える。
【００２５】
工程ｂは一度行うことができ、ハードウェア実装の一部であってもよい。工程ｅの代わりに、更なるボケとダウンサンプリングおよびアンチエイリアシング畳み込み関数を組み合わせることにより、より多くの後続する複数の差分画像を原画像から直接計算することができる。
【００２６】
実施形態によれば、本発明は、後続する複数の差分画像は、原画像から、付加的なボケ、ダウンサンプリングおよびアンチエイリアシング畳み込み関数と畳み込むことによって、直接計算される本発明の方法に関する。
【００２７】
実施形態によれば、本発明は、第１の複数の差分画像および少なくとも１つの後続する複数の差分画像を取得するための方法であって、
ａ．複数のボケ畳み込み関数を用いて、請求項１乃至８のいずれか一項に記載の方法により原画像から前記第１の複数の差分画像を取得する工程と、
ｂ．第１の画像を取得するために、ボケた原画像をダウンサンプリングする工程と、
ｃ．ダウンサンプリング・アンチエイリアシング畳み込み関数Ａｃｏｎを取得するために、前記複数のボケ関数をアンチエイリアシング関数と畳み込む工程と、
ｄ．後続画像を取得するために、取得されたアンチエイリアシング畳み込み関数Ａｃｏｎを第１の画像と畳み込む工程と、
ｅ．請求項１乃至８のいずれか一項に記載の方法により前記後続画像から後続する複数の差分画像を取得する工程、
ｆ．任意に、前記後続画像前記原画像を表示し、付加的な後続する複数の差分画像を取得するために、上記ｂ、ｃおよびｄの工程を繰り返す工程と、
を備える。
【００２８】
実施形態によれば、本発明は、第１の複数の差分画像と、多数ｎの後続する複数の差分画像を取得するための方法であって、前記方法は、
ａ．複数のボケ畳み込み関数を用いて、請求項１乃至９のいずれか一項に記載の方法により原画像から前記第１の複数の差分画像を取得する工程と、
ｂ．前記複数のボケ関数をダウンサンプリング関数およびアンチエイリアシング関数と畳み込むことで第１のダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（１）を取得する工程と、
ｃ．ｎが１よりも大きい場合、以前のダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｔ−１）を、前記複数のボケ関数、ダウンサンプリング関数、およびアンチエイリアシング関数と畳み込むことで、付加的なダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｔ）を取得する工程であって、ｔ＝２でこの工程ｃを始め、単一増分でｔを増加させながらｔがｎに達するまでこの工程を繰り返す工程と、
ｄ．ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎ（ｘ）の各々について画像（ｘ）を取得すべく、前記ダウンサンプリング・アンチエイリアシング畳み込み関数ＤＡｃｏｎの全てを前記原画像と畳み込む工程と、
ｅ．請求項１乃至９のいずれか一項に記載の方法により後続するｎ個の複数の差分画像を取得して、画像（ｘ）の各々から複数（ｘ）の各々を取得する工程と、
を備える。
【００２９】
ここでは、パラメーｔおよびｘは、関数と複数と画像を区別するために導入されたダミーのパラメータである。更なる実施形態によれば、工程ｂ及びｃは一度だけ行われる必要があり、ハードウェアに実装することができる。
【００３０】
実施形態によれば、本発明は、複数の画素によって画成される画像内で種々のスケールにわたって安定した画像特徴を識別するための方法であって、多重フィルタリング工程およびリサンプリング工程が並行して実施され得る方法において、
ａ．請求項１乃至１０のいずれか一項に記載の方法により多重差分画像を取得する工程と、
ｂ．前記多重差分画像における画素振幅極値を検索する工程と、
ｃ．各差分画像内の各画素について画素勾配ベクトルを生成する工程と、
ｄ．ベクトルの向きを、各差分画像に関連するそれぞれの実際の最大および最小振幅画素と関連付ける工程と、
を備える。
【００３１】
実施形態によれば、本発明は、複数のフィルタリング工程がガウシアンフィルタリング工程である。
【００３２】
実施形態によれば、本発明は、複数の画素によって画成される原画像から複数の差分画像を取得するための画像処理装置であって、前記第１の画像に関するデータを受信するための手段と、前記差分画像を送信または記憶するための手段、および処理手段を備え、差分画像を取得するために、複数の差分ボケ関数Ｄｉｆの各々を前記原画像に畳み込むことによって原画像から複数の差分画像を算出し、前記複数の差分畳み込み関数Ｄｉｆは、２つのボケ畳み込み関数間の差を計算することによって確立され、前記２つのボケ畳み込み関数の各々は、前記原画を畳み込むと前記原画像の異なるボケの程度を提供する、装置。
【００３３】
実施形態によれば、本発明は、複数の画素によって画成される画像におけるスケール不変特徴を識別するための画像処理装置に関し、前記画像処理装置は、本発明の方法を実装するように構成されたプロセッサ回路を備える。
【００３４】
実施形態によれば、本発明は、画像処理装置に関するものであって、前記プロセッサ回路は、例えばＣＰＵなどのチップを含む。
【００３５】
実施形態によれば、本発明は、画像処理装置に関するものであって、前記画像処理装置は複数のチップを備え、各チップは少なくとも一つの差分画像を計算するように構成される。これにより、差分画像の並列計算を可能にする。
【００３６】
実施形態によれば、本発明は、画像処理装置に関し、前記画像処理装置は双線形補間器を備え、前記双線形補間器は、乗加算器（ＭＡＣ）、遅延線加算器、および制御論理ブロックを含んでいる。
【００３７】
実施形態によれば、本発明は、複数の画素によって画成される原画像から差分画像を複数取得するためのソフトウェアプログラムであって、前記ソフトウェアプログラムは、複数のプロセッサに以下の動作をもたらす：前記複数のプロセッサが並行して異なる差分画像を算出するように、複数の差分ボケ関数Ｄｉｆの各々を前記原画像に畳み込むことによって原画像から複数の差分画像を算出し、前記差分畳み込み関数値Ｄｉｆは、２つのボケ畳み込み関数の差を計算することによって確立され、前記２つのボケ畳み込み関数の各々は、前記原画を畳み込むと前記原画像の異なるボケの程度を提供する。
【００３８】
実施形態によれば、本発明は、複数の画素によって画成された画像においてスケール不変特徴を識別するためのソフトウェアプログラムに関し、前記ソフトウェアプログラムは、本発明の方法を実装するように構成される。
【００３９】
ＳＩＦＴアルゴリズムの一部として、多重スケールで生じるガウシアン差分（ＤｏＧ）が計算される。原理上、他の関数も適用することができるが、ここでは説明のためにガウシアン関数が用いられる。
【００４０】
ＳＩＦＴアルゴリズムでは、入力画像は一定回数繰り返しボケさせられ、連続するボケの反復の間の差が計算される。得られた画像の一つは、その後、ダウンサンプリングされ、ボケ／差分演算が繰り返される。結果は、「ガウシアンの差」画像の収集であり、いくつかは各スケールのためのものである。収集は、ガウシアンピラミッドの差と呼ばれ、本明細書ではＤｏＧピラミッドと呼ぶ。
【００４１】
本発明の一態様によれば、ガウシアンピラミッドにおけるオクターブ全域のスケーリングされた画像が生成され、スケール／ダウンサンプリング画像を単一ＤｏＧカーネルの各々により畳み込むことで、ピラミッド内の全てのスケールで全てのＤｏＧ画像が並列に計算されるが、ここでは、各ＤｏＧカーネルはその分散と偏角において一意的なものである。得られた畳み込みプロセスは、必要とされるＤｏＧ画像の数に対応する多数の２次元ＦＩＲフィルタによって、全体のスケールでスケーリングされた画像を並列フィルタリングすることに相当する。ＦＩＲフィルタの係数は、予め計算されていてもよい。
【００４２】
画素数の線形時間複雑度を取り入れたピラミッド方法は、例えば、ビデオ圧縮、画像改善や画像再構成、並びに画像分割や特徴抽出などのアプリケーションを含むリアルタイム画像処理と解析に適している。
【００４３】
これらのアプリケーションに使用される例示的関数のいくつかは、以下のとおりである。
【００４４】
・双二次Ｂ−スプラインフィルタリングとのズーミング
・任意ボケ幅の効率的な画像ブレ
・散乱ピクセルデータとの滑らかな補間
・ミップマップテクスチャ
・勾配両極端を検出するためのスケールスペース構築
ここで、ガウシアンフィルタリングおよびリサンプリングカーネルの組み合わせからなる解析フィルタの並列インスタンス化を使用して、例えば、ガウシアンピラミッドを構築するための方法とシステムが提示される。本発明を説明するため、ＳＩＦＴアルゴリズムによって示唆されるように、勾配両極端を検出するためのスケールスペース構造を構築するための方法およびシステムの実施形態を提示する。 
ＳＩＦＴの計算における主要なフェーズは、スケールスペース構造である。このフェーズでは、興味深い画像の特徴あるいはキーポイントは、画像の候補位置を識別するカスケードフィルタリングアプローチを用いて検出される。これらの画像位置は、種々の手法を用いながら、更なる段階で評価され、検証される。
【００４５】
最初の工程は、興味のある対象に変化をもたらすことで繰り返し割り当てることができる画像位置座標とスケールを識別することである。
【００４６】
スケールについて不変である位置を見つけることは、様々なスケールにわたって安定した特徴を検索するスケール関数によって行われる。最適なスケールスペース畳み込みカーネルは、入力画像のスケールスペース関数を決定するために使用されるガウシアン関数である。
【００４７】
スケールスペースで安定したキーポイントの位置を検出するために、画像で畳み込まれたガウシアン（ＤｏＧ）関数の差Ｄ（ｘ；ｙ；σ）は、定数乗算係数ｋで区切られた二つの隣接するスケールの差から計算される。
【００４８】
ＤｏＧ画像Ｄ（ｘ；ｙ；σ）は、以下の式により与えられる：
Ｄ（ｘ，ｙ，σ）＝Ｌ（ｘ，ｙ，ｋｉσ）−Ｌ（ｘ，ｙ，ｋｊσ）
ここで、Ｌ（ｘ；ｙ；ｋσ）は、スケールｋσにおけるガウシアンボケまたはカーネルＧ（ｘ；ｙ；ｋσ）と原画像Ｌ（ｘ，ｙ）との畳み込み（コンボリューション）であり、すなわち、
Ｌ（ｘ，ｙ，ｋσ）＝Ｇ（ｘ，ｙ，ｋσ）＊Ｉ（ｘ，ｙ）
である。
【００４９】
記号"＊"
は、ｘとｙでの畳み込み演算を示すために使用される。このように、従来のＳＩＦＴアルゴリズムは、２つの畳み込みを計算し、その後、これら２つの畳み込み間の差を算出する。
【００５０】
本発明の一態様によれば、画像の２つの畳み込み間の差は、次のように２つの畳み込み関数間の差として、関数ＤｉＦで画像を畳み込むことによって計算することができる：
【００５１】
【数１】
0005976665.tif 000002
ここで、
【００５２】
【数２】
0005976665.tif 000003
である。
【００５３】
この置換を用いることによって、２つの畳み込み処理と差分の後続計算は、単一の畳み込み演算によって置き換えられるため、速度の顕著な増大が達成される。
【００５４】
ガウシアンカーネルを用いると、
【００５５】
【数３】
0005976665.tif 000004
２つのガウシアンカーネルの畳み込みが、第３のガウシアンカーネルを生成することが示されるが、ガウシアン構成要素の分散の和である分散を伴う。
【００５６】
【数４】
0005976665.tif 000005
繰り返し行われる畳み込みは、畳み込み関数を畳み込んで得られた単一の畳み込みにより置換してもよい。
【００５７】
同様に、一方の幅が他方の幅の２倍である２つのガウシアンカーネルのためのＤｉＦが、下記の通り計算できることが示される。
【００５８】
【数５】
0005976665.tif 000006
一般的には、一定の係数ｋで区切られた２つのガウシアンカーネルのためのＤｉＦは、次のように計算できることを示すことが可能である。
【００５９】
【数６】
0005976665.tif 000007
引用した文献はすべて、参照により本明細書に組み込まれる。
【００６０】
添付の図面と注釈は、本発明を限定するためではなく提供される。態様、実施形態および本発明の特許請求の範囲を組み合わせることができることは当業者にとって明らかであろう。
【００６１】
図面を以下に取り入れ、引き続いて、いくつかの図面についてさらに説明する。
【図面の簡単な説明】
【００６２】
【図１】図１はカスケードアプローチを用いてガウシアンピラミッドを構築する従来の方法を表現した概略図である。
【図２】図２は、並列ハードウェア実装に適した２つの実施形態による２つの異なるＤｏＧピラミッド方法を表現した模式的概略図である。
【図３】図３は、実施形態による双線形ダウンサンプリン補間器のブロック図を示す模式的概略図である。
【図４】図４は、実施形態による双線形ダウンサンプリング補間器のハードウェアの効果的な実装のブロック図を示す模式的概略図である。
【図５】図５は、実施形態によるダウンサンプリング補間器を示す模式的フローチャートである。
【図６】図６は、本発明の実施形態により、効率的なハードウェア性能のためにガウシアンピラミッドの基本的な構築ブロックがいかに組み合わせることができるかを示す模式図である。
【図７】図７は、実施形態によるガウシアンピラミッドの構築のための効果的な双線形補間器を説明する概略図である。これは、双線形テクスチャ補間に基づくピラミッドスキームである。
【図８Ａ】図８Ａは、幅の異なる２つのガウシアン関数間の差を算出して得られたガウシアンカーネル（ＤｉＦ）の差を示すもので、これらの１つは図８Ｂに示されている。
【図８Ｂ】図８Ａは、幅の異なる２つのガウシアン関数間の差を算出して得られたガウシアンカーネル（ＤｉＦ）の差を示すもので、これらの１つは図８Ｂに示されている。
【図９】図９は、実施形態よるＤｏＧ関数を計算するための模式的ブロック図である。
【図１０】図１０は、実施形態によるハードウェア実装の一部を示す模式図である。
【図１１】図１１は、実施形態によるハードウェア実装の一部を示す模式図である。
【図１２】図１２は、実施形態によるハードウェア実装の一部を示す模式図である。
【発明を実施するための形態】
【００６３】
［注釈］
図１は、ＤｏＧ関数を構築する従来の方法を、例を挙げて示すものである。
【００６４】
ガウシアンカーネルのカスケード特性に従って、２つのガウシアンカーネルの畳み込みが第３のガウシアンカーネルを生成する。上述したように、２つのガウシアンカーネルを畳み込むと、構成するガウシアンの分散の和である分散σ２を持つ新規なより広い幅のガウシアンを取得する。下記記号は、畳み込み演算を表すために使用される。
【００６５】
【数７】
0005976665.tif 000008
図１の各レベルでの減算器出力におけるガウシアンの画像の差は、次のように表すことができる。
【００６６】
【数８】
0005976665.tif 000009
ここで、ｎ＝１からｓ、ｍは１からピラミッドレベルの数まで達する。
【００６７】
同様に、各レベルの入力画像は、下記の式で表すことができる。
【００６８】
【数９】
0005976665.tif 000010
式において、ｍ=>１である。従って、ＤｏＧピラミッドの完全な並列計算を可能にし、図１は図２として表し直せる。
【００６９】
図２を参照すると、リサンプリングカーネルとｈｐｍで示されるパスガウシアンカーネルの組み合わせは、分析フィルタとみなすことができるが、ここでは画像が先ず補間カーネルｋ（ｘ、ｙ）により畳み込まれ、次いでアンチエイリアスフィルタリングを含む畳み込みカーネルＧ（ｘ、ｙ、２σ＋σＡ）により畳み込まれる。
【００７０】
次に、組み合わされた補間カーネルとＧ（ｘ、ｙ、２σ＋σＡ）の解析フィルタは、単一の畳み込みカーネルにより次式で表すことができる。
【００７１】
【数１０】
0005976665.tif 000011
それ故、式（２）は次のように書き直すことができる（別表Ａの論証を参照のこと）：
【００７２】
【数１１】
0005976665.tif 000012
または
【００７３】
【数１２】
0005976665.tif 000013
または
【００７４】
【数１３】
0005976665.tif 000014
一般的には、Ｋ（ｘ、ｙ）で表されるリサンプリング関数は、デルタディラック関数δ（ｘ）と見做すことができる。これは、内側のスケールがゼロになるにつれて限界をとるとき、ガウシアン関数で表すことができる一般化数学関数の一つである。それ故：
【００７５】
【数１４】
0005976665.tif 000015
となる。
【００７６】
従って、任意のサンプリング関数をガウシアンカーネルとして扱うことができ、カスケード特性を適用することができることとなる。
【００７７】
リサンプリング関数が畳み込みによる補間（畳み込み補間は任意のグリッド間でデータをリサンプリングするために使用される一般的な方法である）である特定のケースでは、解析フィルタは、１つのガウシアンカーネルによって以下の式で表すことができる。
【００７８】
【数１５】
0005976665.tif 000016
リサンプリングがダウンサンプリング関数を含む別の特定のケースでは、各次元における２ｎの係数による換算を伴い、分析フィルタの組み合わせのために、便宜上、特定の表記を導入することができる。
【００７９】
【数１６】
0005976665.tif 000017
ここで、ｇは入力画像を意味し、ｆは下記の成分を伴って結果として生ずる画像である。
【００８０】
【数１７】
0005976665.tif 000018
フィルタマスクｈがｎｉ×ｎｊマトリクスで表され、画像ｇがｎｒ×ｎｃの寸法である場合、マトリクス成分ｆｒ，ｃは行インデックスｒおよび列インデックスｃのためのものである。
【００８１】
ダウンサンプリングカーネルが双線補間である特定のケースでは、解析双線補間は、次式に従って、粗いスケールで単一の画素を生成するために、１つのスケール（ｓ）において２×２カーネル内で４つの隣接する画素の重み付け平均化よって機能する。
【００８２】
【数１８】
0005976665.tif 000019
ここで、隣接する画素はｐ（ｘ、ｙ）によって表せられる。
【００８３】
【数１９】
0005976665.tif 000020
このような補間器のブロック図を図３に示す。図に示すように、線形時不変離散時間システムは、以下の式で表すことができる。
【００８４】
【数２０】
0005976665.tif 000021
ここで、ｋは入力画像のライン幅であり、ｔは整数であり、Ｎはサンプリング周期である。かくして、
【００８５】
【数２１】
0005976665.tif 000022
となる。
【００８６】
図４は、効果的な双線補間器のハードウェア実装のブロック図を示している。補間器は、乗加算器（ＭＡＣ）、遅延線加算器、および制御論理ブロックで構成される。補間器は、実際のピラミッドレベルの画像における、線あたりの画素数および線の数に関して、画像サイズに対して設定可能である。ダウンサンプリング補間関数は、図５のフローチャートに概説されているが、ここではダウンサンプル補間器における制御ロジックを示している。
【００８７】
付録Ａ：単一処理における補間と畳み込み
補間カーネル（ｘ、ｙ）によって画像ｆ（ｘ、ｙ）をリサンプリングし、その後、これを畳み込みカーネルｐ（ｘ、ｙ）により畳み込むことを所望するならば、ｋ（ｘ、ｙ）によるｐ（ｘ、ｙ）の畳み込みであるカーネルｑ（ｘ、ｙ）によって畳み込むことによって工程を節約することができる。
【００８８】
【数２２】
0005976665.tif 000023
ｆｑ（ｘ、ｙ）を取得するにはカーネルｑ（ｘ、ｙ）を使用して補間する。
【００８９】
【数２３】
0005976665.tif 000024
ｑ（ｘ、ｙ）の定義に当てはめる：
【００９０】
【数２４】
0005976665.tif 000025
合計を再グループ化すると、最終的な合計に到達する：
【００９１】
【数２５】
0005976665.tif 000026
これを証明するため、補間後に且つ畳み込み前に、ｆｉ（ｘ、ｙ）を画像として定義する：
【００９２】
【数２６】
0005976665.tif 000027
そして、最終結果ｆｐ（ｘ、ｙ）を取得するために、ｐ（ｘ、ｙ）によってこれを畳み込む：
【００９３】
【数２７】
0005976665.tif 000028
ｆｉ（ｘ、ｙ）のため値に当てはめる：
【００９４】
【数２８】
0005976665.tif 000029
合計を再グループ化することで、ｑ（ｘ、ｙ）で補間することによって得たものと同じものを取得する：
【００９５】
【数２９】
0005976665.tif 000030
補間カーネルが、畳み込みカーネルよりも広い周波数範囲をサンプリングする正弦関数である場合、為さなければならないことは、畳み込みカーネルを用いて補間することのみであることに留意されたい。
【００９６】
【数３０】
0005976665.tif 000031
正弦関数のフーリエ変換は正方形であるから：
【００９７】
【数３１】
0005976665.tif 000032
ここで、もし｜ｓ｜１／２の場合には、Π（ｓ）＝１であり、そうでなければ０である。
【００９８】
【数３２】
0005976665.tif 000033
これは、Ｋ（ｕ，ｖ）がいずれであっても、Ｐ（ｕ、ｖ）が０であるようなスケールを、Ｋ（ｕ，ｖ）が持つ場合である。換言すれば、Ｐ（ｕ、ｖ）が補間正弦関数Ｋ（ｕ，ｖ）の帯域制限よりも狭い帯域で制限される帯域であればいつでも、Ｑ（ｕ，ｖ）＝Ｐ（ｕ，ｖ）となる。
【図１】
0005976665.tif 000034
【図２】
0005976665.tif 000035
【図３】
0005976665.tif 000036
【図４】
0005976665.tif 000037
【図５】
0005976665.tif 000038
【図６】
0005976665.tif 000039
【図７】
0005976665.tif 000040
【図８Ａ】
0005976665.tif 000041
【図８Ｂ】
0005976665.tif 000042
【図９】
0005976665.tif 000043
【図１０】
0005976665.tif 000044
【図１１】
0005976665.tif 000045
【図１２】
0005976665.tif 000046