動き解析への用途を有するスパース積分画像記述子
画像を表現する方法は、軸上に画像を投影することによって画像の少なくとも1つの1次元表現を導き出すことを含み、投影は、前記軸に垂直な画像のそれぞれのライン内での、選択されたピクセルの値の総和であり、選択されるピクセルの数は、ライン内のピクセルの数よりも少ないことを特徴とする。
【発明の詳細な説明】
【技術分野】
【0001】
画像投影は、動きおよび変化解析などの多くの用途に有用な、積分画像特性を記述する。画像処理アルゴリズムは、2次元問題を、1次元問題の集合に縮小するために、画像投影の計算を使用する。そのような縮小の主な理由としては、以下が挙げられる。
・1D問題の計算複雑度(computational complexity)ははるかに低い。W×Hピクセルのサイズの画像の場合、単純なピクセルごとの走査でさえ、O(WH)回の演算を必要とし、そして、アルゴリズムは、通常、複数回の走査からなる。投影に基づくアルゴリズムは、画像投影を計算するための1回の画像走査と、O(W)およびO(H)の複雑度を有する数回の投影走査とを必要とする。
・いくつかの場合、2D画像関数におけるよりも、1D投影関数における方が、物体またはその他の画像特徴を検出するのは容易である。
【0002】
水平(または垂直)投影の各値は、対応する列(または行)内のすべてのピクセルを総和することによって得られる。したがって、両方の投影に必要とされる加算の回数は、次のようになる。
N標準=2WH (1)
【0003】
3つのカラーチャネルについて計算された、画像投影の例が、図1に示されている。この例は、複雑な構造(橋の垂直部分)が、水平投影において、それらの極小を調べることによって検出可能であることを示している。投影計算の図解的方法は、図2に示されており、各行(または列)内のピクセルの総和が、投影関数の対応する値(矢印によって示す)を決定する。走査されるピクセルは、ドットによってマークされている。
【0004】
リアルタイムシステム、特に、低コストのDSPボード内で実施されるリアルタイムシステムにおいては、投影計算のO(WH)の複雑度でさえ、リアルタイム性能としては依然として高すぎる場合がある。本発明は、特定のアルゴリズムの精度への重大な影響なしに、この複雑度を、2分の1、3分の1、4分の1、・・・に、さらに減少させるための方法を開示する。発明者らは、投影のための近似法を取得し、そのような近似法が、標準の投影と同じ方法で、画像処理アルゴリズム内で使用されてもよいということを示す。
【0005】
本発明の実施形態は、ブロックベースの投影、または単純にBn,m投影と呼ばれる、特殊な画像投影を使用し、ここで、n×mは基本ブロックのサイズである。n×mピクセルからなる重ならないブロックが画像全体を分割し、各ブロックからの正確にn個のピクセルが、水平Bn,m投影のn個の値を更新するために使用され、そして、各ブロックからの正確にm個のピクセルが、垂直Bn,m投影のm個の値を更新するために使用される。
【0006】
ブロックサイズが等しい場合(n=m)、そのようなBn,n投影を、Bn投影と呼ぶ。Bn投影の計算のためのアルゴリズムはより単純であり、一般的なBn,m投影の場合のような追加の計算オーバヘッドを必要としない。
【0007】
Bn,m投影の定義によれば、標準の投影(standard projection)(図1、図2)はB1投影とも呼ばれてもよく、これは、基本ブロックが1つのピクセルからなるということを示している。さらに、定義から、Bn,m投影は標準の投影と同じ長さを有し、したがって、元の画像解像度が維持される。これは、標準の投影が使用される、任意の画像処理アルゴリズムにおいて、Bn,m投影を使用することを可能にする。さらに、画像の前処理を追加せずには標準の投影を適用できない状況において、Bn,m投影のいくつかの特定のケースが使用されてもよい。そのような状況の1つの例は、ベイヤーパターン(Bayer pattern)によって表される画像の処理である。
【0008】
本発明の態様は、添付の特許請求の範囲に記載される。
【0009】
第1の態様では、本発明は、軸上に画像を投影することによって、画像の少なくとも1つの1次元表現を導き出すことを含む、画像を表現する方法を提供する。投影は、前記軸に垂直な画像のそれぞれのライン内で、選択されたピクセルの値を総和することを含む。本方法は、選択されるピクセルの数が、ライン内のピクセルの数よりも少ないことを特徴とする。
【0010】
好ましくは、投影は、複数のそれぞれのライン内で、選択されたピクセルの値を総和することを含み、ここで、少なくとも1つのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少ない。
【0011】
それぞれの軸に垂直な複数のそれぞれのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少なくてもよい。それぞれの軸に垂直なすべてのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少なくてもよい。
【0012】
2つ以上の投影であって、2つ以上のそれぞれの軸上への、投影が存在してもよい。好ましくは、画像は2次元画像であり、そして、2つの各軸のそれぞれの上への投影が存在し、投影は上述したとおりのものである。好ましくは、2つ以上の軸は、水平軸と垂直軸のように、垂直である。
【0013】
一実施形態では、選択されるピクセルは、垂直投影において、i番目ごとの行からのピクセルを除外することによって、そして、水平投影において、j番目ごとの列からのピクセルを除外することによって得られる。例えば、2番目ごとの行、または2番目ごとおよび3番目ごとの行内のピクセルが除外されてもよく、そして、3番目ごとの列、または2番目ごとおよび3番目ごとの列内のピクセルが除外されてもよい。
【0014】
本明細書において、「選択される(選択された)ピクセル(selected pixel)」という用語は、選択されるピクセルの値が、投影についての総和に含まれるということを意味する。「除外される(除外された)ピクセル(omitted pixel)」は、対応するピクセル値が選択されない、すなわち、投影についての総和に含まれないということを意味する。ある投影(たとえば水平投影)について選択されるピクセルは、別の投影(たとえば垂直投影)については除外されてもよく、逆もまた同様である。一般に、ブロックの文脈における「選択される(選択された)ピクセル」とは、そのピクセルが少なくとも1つの投影についての総和に含まれることを意味し、ラインの文脈における「選択される(選択された)ピクセル」とは、そのピクセルが、そのラインに沿った投影における総和に含まれることを意味する。
【0015】
大まかに述べると、提案される方法の実施形態は、以下のように働く。
1)画像走査を、いくつかのピクセルのスキッピングとともに実行する。次の節で説明する、以下の方法のうちの1つ、またはそれらの組み合わせが、走査のために使用されてもよい。
・行/列スキッピング(Row/column skipping)
・対角スキッピング(Diagonal skipping)
・ブロック置換(Block permutation)
2)アクセスされたピクセルのみを使用して、画像行または列を総和することによって、垂直および水平のBn,m投影を計算し、そして、それらを、メモリバッファ内に記憶する。
【0016】
提案される方法の、定性的および数値的比較により、以下の結論がもたらされる。
・次の節で説明する3つの方法は、投影を計算するために、等しい数の基本演算(加算)を必要とする。
・対角スキッピング方法によって必要とされる合計時間は、その他の方法によって必要とされる時間よりも少ない。
・3つの方法は、すべて、n、m=2、3、4について、似た結果を与える。そのようなブロックサイズを使用して得られる投影は、n=m=1を使用して得られる標準の投影から大幅には逸脱しない。
・発明者らは、アルゴリズム速度の、n倍という大幅な増加を得たが、取得される投影は、ノイズおよびアーチファクトによって、標準の投影とは異なる可能性がある。ただし、n、m=2、3、4の場合は、ノイズおよびアーチファクトは非常に小さい。信号処理方法は、通常、そのような小さな因数に対して堅牢であり、したがって、発明者らのBn,m投影は、標準の投影の代わりに使用可能である。
【0017】
本発明の実施形態を、添付の図面を参照して説明する。
【図面の簡単な説明】
【0018】
【図1】従来技術による、画像とその垂直および水平の投影とを示す。
【図2】従来技術による、垂直および水平の投影を示す図である。
【図3】本発明の第1の実施形態による投影を示す図である。
【図4】本発明の第1の実施形態による投影を示す代替の図である。
【図5】本発明の第2の実施形態による投影を示す図である。
【図6】本発明の第3の実施形態による、選択されたピクセルを有するブロックの図である。
【図7】本発明の第4の実施形態による投影を示す図である。
【図8】本発明の第5の実施形態による、画像内の選択されたピクチャを示す図である。
【図9】本発明の第6の実施形態による投影を示す図である。
【図10】投影を使用した水平の動き推定を示す図である。
【図11】動き推定の一形態を示すブロック図である。
【図12】ベイヤーパターンの例である。
【図13】動き推定の別の形態を示すブロック図である。
【図14】動き推定の別の形態を示すブロック図である。
【図15】ベイヤーパターンを使用した動き推定を示す画像である。
【図16】動き検知(motion sensing)の一形態のブロック図である。
【0019】
本発明の実施形態は、参照により本明細書に援用される、本出願人による同時係属出願である英国特許出願第0425430.6号明細書(GB0425430.6)を含む、画像を表現するための画像投影の計算に関する従来技術の発展である。
【0020】
本発明の第1の実施形態による、Bn投影を計算するための手法が、図3に示されている。Bn投影は、行/列スキッピングによって計算される。図3に示す、印を付けられたピクセルのみが、対応する投影を計算するために使用される。
【0021】
2回の画像走査が使用され、それぞれの走査で、対応する投影が計算される。X投影を計算するためには、n番目ごとの行がスキップされる。同様に、Y投影を計算するためには、n番目ごとの列がスキップされる。
【0022】
この方法(行/列スキッピング)は、ブロックベースの表現によって説明することも可能である。図4は、2×2ブロックを使用する例を示す。図4(a)は、ブロックサイズn=2およびn=3についての、実際の画像領域(図1の画像の小さな領域など)の例を示す。スキップされるピクセルは、白で示されている。図4(b)は、ブロックサイズn=2およびn=3についての、計算方法の概略図を示す。印を付けられたピクセルのみが、対応する投影を計算するために使用される。黒のピクセルは、両方の投影のために使用される。灰色のピクセルは、X投影のために使用される。白のピクセルは、Y投影のために使用される。
【0023】
この例は、各ブロックのうちの3つのピクセルのみが使用されるため、アルゴリズムの計算複雑度は3WH/4に比例するということを示す。一般的なn×nブロックの場合については、計算複雑度C行/列は、(2n−1)WH/n2に比例する:
C行/列(n)=k1(2n−1)WH/n2 (2)
上式で、定数k1は、画像走査の追加のオーバヘッドに相当する。この方法によって必要とされる加算の回数は、1つのブロックからの2(n−1)個のピクセルが投影に1回加算され、そのブロックからの1つのピクセルのみが2回使用されるという事実に基づいて取得される。したがって、加算の回数は次のようになる。
N行/列(n)=2WH/n≦N標準 (3)
【0024】
第2の実施形態では、Bn投影は、対角スキッピングによって計算される。
【0025】
対角スキッピングの方法は、図5に示されている。図5(a)は、n=2およびn=3についての、実際の画像(図1の画像の小さな領域など)の例を示す。スキップされるピクセルは、白で示されている。図5(b)は、計算方法の概略図である。各基本ブロックの中の、(ドットによって印を付けられた)主対角線からのピクセルのみが使用される。
【0026】
Bn投影を計算するために、いくつかの画像対角線がスキップされ、そして、等式(4)を満足するピクセル(x,y)のみが使用される。
(x+y) mod n=0 (4)
【0027】
これは、各基本ブロックの中で、主対角線(the main diagonal)からのピクセルのみが使用されるということを意味している。したがって、この方法の計算複雑度C対角は、n(各ブロックの主対角線内のピクセルの数)にブロックの数WH/n2を乗算した値に比例する:
C対角=k2WH/n (5)
【0028】
定数k2もまた、(4)の計算と画像走査のその他のオーバヘッドとを考慮に入れる。実験的なテストから、C対角<C行/列ということになる。ブロックの対角線に属する各ピクセルは2回使用され、したがって、加算の回数は次のようになる:
N対角(n)=2WH/n=N行/列(n) (6)
【0029】
第3の実施形態では、Bn投影は、ブロック置換によって計算される。図6は、行(または、同等に、列)置換によって生成された、投影において使用される選択されるピクセルを示す3×3ブロックの例を示す。
【0030】
第3の実施形態のBn投影計算の方法は、第2の実施形態の対角スキッピング方法の変更形態と考えることができる。この方法では、各基本ブロックは、行(または、同等に、列)置換によって予備的に変換される(図6)。ランダムな、またはランダムではない、置換の組が使用されてもよい。
【0031】
図7は、ランダムな置換を用いてこの方法を使用する例を示す。n=2およびn=3についての、基本ブロックのランダムな置換が示されている。図7(a)は、実際の画像(図1の画像の小さな領域など)の例を示す。スキップされるピクセルは、白で示されている。図7(b)は、計算方法の概略図である。印を付けられたピクセルのみが、投影計算のために使用される。
【0032】
計算複雑度C置換は、(5)に類似している:
C置換=k3WH/n (7)
ただし、ピクセルを走査するために、より複雑なアルゴリズムが使用される。走査アルゴリズムの効率的な実施のためには、(図6内で印を付けられた)ピクセル位置が、事前に計算され、そしてメモリテーブル内に記憶されるべきである。(7)における定数k3は、走査アルゴリズムの複雑度を考慮に入れ、そして、一般に、C対角<C置換である。この方法では、各ブロックからのn個のピクセルが(水平および垂直の両方の投影に寄与するために)2回使用され、したがって、加算の回数は次のようになる。
N置換(n)=2WH/n=N対角(n) (8)
【0033】
上記の実施形態の変更形態は、複数の異なるブロックサイズの組み合わせを含む。
【0034】
いくつかの画像処理方法では、いくつかの画像部分が、その他の画像部分よりも重要な場合がある。例えば、移動しているビデオカメラの場合、カメラの移動方向とは反対側の画像境界の付近のピクセルは、フレームごとに消失する。そのようなピクセルは、通常、解析から除外されるか、または、窓掛け処理(windowing)などの、複数の異なる技術によって、それらの影響が減少させられる。この場合、より概算的かつより高速な、画像投影計算の方法が使用されてもよい。例えば、画像の中央部では、B2投影が使用されてもよく、そして、境界の付近ではBn投影(n>2)が使用されてもよい(図8を参照)。図8では、ブロック置換方法が、説明の目的のためにのみ使用されている。複数の異なる方法が、画像の複数の異なる領域内で使用されてもよい。この方法の追加のオーバヘッドは、各ピクセルが、投影内で総和される前に、そのブロックのサイズ(nに等しい)によって重み付けされなければならないということである。
【0035】
一般的なBn,m投影の場合が、1:1とは異なるアスペクト比を有する画像に対して使用されてもよい。例えば、640×480ピクセルの標準VGA画像の場合、等しい数のピクセルが、垂直および水平の両方の投影に寄与することを確実にするために、アスペクト比4:3を有するブロックB4,3が使用されてもよい。そのような計算は、例えば、図9に示すような、対角スキッピング方法と列スキッピング方法との組み合わせによって達成されてもよい。図9において、黒のピクセルは両方の投影に寄与し、灰色のピクセルは水平投影のみに寄与する。
【0036】
上述のように、異なるブロックサイズが画像の異なる領域のために使用されてもよい。同様に、投影計算(ピクセル選択)の異なる方法が、画像の異なる領域について、または、1つのブロック内で組み合わせて、使用されてもよい。複数の異なる方法が組み合わされてもよい。
【0037】
投影計算の結果は、画像の表現、すなわち画像記述子と見なされてもよい。より具体的には、結果は、スパース積分画像記述子(sparse integral image descriptors)と見なされてもよい。
【0038】
上述の、画像を表現する方法は、画像を解析するために画像投影を計算する、任意の画像処理システムにおいて適用可能である。本提案の画像投影の高速計算から利益を得るであろう3つの既知の画像処理方法への、本発明の実施形態の適用例について、以下に概説する。さらに、新規な適用例、特に、ベイヤーパターンからの動き推定と、それから得られる、自己動きセンサ(ego-motion sensor)とが、提案される。
【0039】
第1の既知の技術は、画像のシフトはシフトされた投影をもたらすという事実に基づいた、主要な平行移動の動き推定(dominant translational motion estimation)である。図10は、複数の水平投影の間における1Dシフトを推定することによる、3つの連続したビデオフレーム間の、水平の動き推定を示す。この話題に関する最先の研究のうちの1つは、S.Alliney、C.Morandi著、Digital image registration using projections、IEEE TPAMI−8、No.2、1986年3月、222〜223頁において報告された。これは、本出願人による同時係属出願である英国特許出願第0425430.6号明細書(GB 0425430.6)においてさらに改良された。この方法について、本発明者らは、標準の投影の代わりにBn投影を使用することを提案する。
【0040】
連続する複数の画像から計算される、2つ以上の画像投影が、主要な動き(dominant motion)の対応する成分を推定するために使用される(図10)。図10は、3つの連続したフレーム(フレームK−2、フレームK−1、およびフレームK)と、それらの対応する水平投影とを示す。正規化相互相関(normalized cross-correlation)(NCC)、差分絶対値和(sum of absolute difference)(SAD)または差分二乗和(sum of squared difference)(SSD)、あるいは位相相関(phase correlation)(PC)などの、信号シフト推定の任意の従来技術による方法が、投影を比較してフレーム間のシフトを決定するために使用されてもよい。
【0041】
第2の既知の技術は、画像記述子の抽出と、記述子のマッチングとの、2つの主なステップからなる、主要な動き推定方法である(図11を参照)。図11(そしてさらに、図13、図14、および図16)は、動き推定または動き検知方法のステップを示す。図に示されている方法のステップは、装置の対応する構成要素またはモジュールによって実施されてもよい。
【0042】
図11に示すように、1つの画像記述子は、水平(X記述子)および垂直(Y記述子)の、2つの独立した部分からなる。記述子抽出の主な着想は、処理の初期段階において、2D画像情報を1D信号に変換することである。本発明の実施形態を使用して、記述子は、Bn投影から導き出される。どのような種類のマッチング方法が使用されるかに応じて、記述子は以下であってもよい。
・Bn投影そのもの(信号領域内でのマッチング用)
・Bn投影のフーリエ変換(周波数領域内でのマッチング用)
【0043】
記述子マッチングブロックは、現在のフレームの記述子と、直前のフレームについて計算された記述子とを使用する。提案される方法の一実施形態では、1Dシフトの推定のために、位相相関が使用される。この方法は、フーリエ変換とシフト定理(Shift Theorem)とに基づく。2つの信号(提案される方法ではいずれもBn投影。例えば、s1(x)およびs2(x))が、次のように平行移動aだけ異なると仮定する。
s(x)=s’(x+a)
【0044】
その場合、位相相関方法を次のように適用する。
【0045】
【数1】
【0046】
上式で、F(s)は、記述子抽出段階で事前に計算される、信号sのフーリエ変換であり、F*(s)は、F(s)の複素共役である。これにより、相対変位値におけるパルスが得られる。
C(x)=δ(x−a)
【0047】
変位aは、結果として得られる信号C(x)内の最も高いピークを見つけることによって決定される。
【0048】
主要な動きを検出する、別の既知の方法は、ベイヤーパターンを使用する。シングルチップビデオカメラの大多数、およびほとんどすべてのデジタルスチルカメラは、いわゆるベイヤーパターンセンサを使用する。これらのセンサは、CMOSまたはCCDデバイスのいずれかである場合があるが、原理は同じである。米国特許第3971065号明細書のベイヤーパターンアプローチでは、カラーフィルタアレイの多くの可能な実施のうちの1つとしての、特殊なパターンを使用する。ベイヤーパターンの例を、図12に示す。その他の実施は、ほとんどが、輝度チャネル(luminance channel)(緑)は色チャネル(chromatic channel)(赤および青)よりも高いレートでサンプリングされる必要があるという原理を使用する。輝度を表すものとしての緑の選択は、人間の目の輝度応答曲線が、緑の光の周波数(約550nm)に近いという事実によって説明することができる。
【0049】
ベイヤーパターンからの画像を処理するためには、多くの方法が存在する。デジタルカメラ内の一般的な画像処理パイプラインは、主として、以下のステップに分けられる。空間デモザイキング(spatial demosaicing)と、それに続く、色およびガンマ補正(図13−ビデオカメラまたはDSCからの出力画像を使用した動き推定)。各ピクセルにおける色値を補間するために、ベイヤーは、単純な双一次補間を提案した。デジタルスチルカメラの開発の初期において、米国特許第4642678号明細書では、一定の色相に基づいた補間(constant hue-based interpolation)を使用することが提案されたが、その理由は、デモザイキングプロセスにおけるピクセルのアーチファクトは、色相の突然のジャンプの中で発生するからである。次に、米国特許4774565号明細書では、色フリンジ(colour fringes)を回避するために、色チャネルのメジアンに基づいた補間(median-based interpolation)を使用することが提案された。米国特許第5382976号明細書では、エッジベースの技術(edge-based technique)を使用することによる、フルカラー画像の適応的な補間が提案された。米国特許5373322号明細書では、米国特許第5,382,976号明細書のアプローチの拡張と見ることができる、承認されたエッジベースの方法が提案された。米国特許5629734号明細書では、両方のエッジベースの方法の概念が使用され、それらのアプローチの組み合わせおよび拡張が作成された。ベイヤーパターンデモザイキングの問題は、コンピュータビジョンコミュニティにおいて依然として盛んに話題となっている。例えば、Henrique Malvar,Li−wei He,およびRoss Cutler著,High−quality linear interpolation for demosaicing of Bayer−patterned color images,IEEE International Conference on Speech, Acoustics, and Signal Processing、2004年を参照されたい。
【0050】
動き推定方法を含む、画像処理方法のほとんどは、最終的なカラー画像(ベイヤーパターン処理の結果)がピクセル補間によって得られることを要求する。直接的な方法(direct method)の設計は、(動きなどの)高レベルの情報を、画像センサデータから直接(すなわち、コストのかかるデモザイキングなしに)推定するのを可能にする。
【0051】
主要な動き推定方法における垂直および水平の投影は、以下のうちの1つを使用して計算される。
・任意のRGB画像チャネル(好ましくは、最も大きいダイナミックレンジを有する、緑)
・(すべてのカラーチャネルから導き出される)画像輝度
・通常はカメラバッファから得られる、YCrCbカラースペースのYチャネル
・元の、または処理されたカラーチャネルの、任意のその他の組み合わせ
【0052】
したがって、投影に基づく方法を使用するためには、ベイヤーパターンを処理し、そして、それを標準のカラー画像に変換する必要がある。この処理の速度は、埋め込まれた動き推定アルゴリズムのために好適ではない場合がある。したがって、ベイヤーパターンの中間処理を回避するために、この方法のさらなる変更が必要とされる。
【0053】
垂直および水平の投影は、画像ピクセルを総和することによって計算される。そして、この計算は、上記で示したように、正確に2WH回の加算を必要とする。画像の、m分の1へのダウンサンプリングは、加算の回数をWH/m2に減少させるが、推定される動きベクトルの精度を比例して減少させ、そして、ダウンサンプリング処理自体のために、WHに比例した回数の追加の演算を必要とする場合がある。
【0054】
本発明のさらなる実施形態は、図14および図15に示すような、ベイヤーパターン(またはベイヤー様のパターン)に直接働きかける、高速動き推定アルゴリズムを提供する。
【0055】
図14は、初期段階における動き推定を有する、処理パイプラインのブロック図である。図15は、ベイヤーパターン表現を使用した、画像の動き推定を示す。
【0056】
本実施形態によれば、Bn投影が、対角スキッピングまたはブロック置換方法によって計算される。n=2を考慮する場合(図5、左列)、このパターンは、ベイヤーパターンの緑チャネル(図12)、またはCMYベイヤーパターンの黄チャネルに、正確に対応する。ブロック置換方法における置換の組を調節することによって、複数の異なるベイヤー様パターンと、疑似ランダムベイヤーパターンとが、モデル化されてもよい。提案される方法の有用な特性としては、以下が挙げられる。
・CCDまたはCMOSセンサからの、ベイヤーパターン(RGBおよびCMYの両方)の直接使用、および、ピクセルの数に比例した複雑度を有する高価な色補間および補正アルゴリズムの回避。
・センサから画像を受信した直後の、最初期段階における動き推定。検出された動きに関する情報は、処理の他の段階において、例えば、デモザイキングの前の、ベイヤーパターンのノイズ除去のために、または、動きぼやけ(motion blur)の低減のために使用されてもよい。
対角スキッピング方法により計算されるBn投影を使用することによって、ピクセル数の1/nに比例した複雑度を有する、より高速な変更が可能である。
・動きベクトルの元の解像度が維持される(および、サブピクセル補間を使用してさらに向上させられる)。
・ブロック置換方法により計算されるBn投影を使用することによって、ベイヤーパターンの、複数の異なる構成への拡張が可能である。
【0057】
セキュリティまたはその他のシステム用の、低コストの、自己動きビデオセンサを作成するために、前節で提示した方法が使用されてもよい。例えば、このセンサは、動きを開始した場合、信号を生成する。そのようなセンサは、(好ましくは、低コストの)ビデオカメラと、小さなCCDまたはCMOSマトリクスとからなる。この場合、ベイヤーパターン処理のために通常使用される(図16)、すべての色補正/補間手順は不要であり、そして、Bn投影を介した動き推定は、そのようなセンサを実施するための非常に効果的な方法である。図17は、そのようなセンサの働きの抽象ブロック手法(abstract block-scheme)を示す。
【0058】
画像投影は、全体照明の変化を含む、突然の照明の変化を検出するために使用されてもよい。画像投影の挙動は、照明の変化を反映する。例えば、連続したフレームからの投影の、負の差は、照明レベルの低下を知らせる。そのような特徴は、画像処理システムに、そのパラメータを新しい照明レベルのために適合させるように通知するために使用されてもよい。プロセス全体の速度を低下させないために、この補助的特徴は、高速で実行されることが重要である。Bn投影を使用することにより、この特徴の性能はn倍向上する。
【0059】
比較的単純なシーン(暗い背景の中の明るい物体、またはその逆など)では、物体追跡の2D問題を、画像投影を使用して、1D追跡問題に縮小することが可能である。そのような場合、物体の位置は、投影の極大(または極小)によって決定される。そのような方法の、可能な適用領域は、航空機追跡、顕微鏡画像、およびレーダ画像である。物体が多数の場合、または時間が制限される場合、性能を向上させるために、標準の投影の代わりにBn投影が使用されてもよい。
【0060】
上記の各実施形態においては、一般に、2つの投影(水平および垂直)が計算および使用される。しかし、1つのみの投影が計算および/または使用されてもよい(例えば、水平の平行移動の動き推定の例におけるように)。
【0061】
本明細書においては、「画像」および「フレーム」という用語は、画像単位(フィルタリング後のものを含む)を記述するために使用されるが、この用語は、画像、フィールド、ピクチャ、あるいは、画像やフレームなどのサブ単位または領域といった、その他の類似した用語にも適用される。ピクセル、およびピクセルのブロックまたはグループという用語は、適切な場合、区別なく使用されることがある。本明細書において、画像という用語は、文脈から明らかである場合を除き、画像全体、または画像の領域を意味する。同様に、画像の領域は、画像全体を意味する場合がある。画像は、フレームまたはフィールドを含み、そして、静止画像に、あるいは、フィルムまたはビデオなどの画像シーケンスの中の画像に、あるいは、関連する画像グループの中の画像に、関連する。
【0062】
画像は、グレースケールであってもカラー画像であってもよく、あるいは別のタイプのマルチスペクトル画像(例えば、IR、UV、またはその他の電磁画像(electromagnetic image))であってもよく、あるいは音響画像(acoustic image)であってもよい。画像は、好ましくは2次元画像であるが、n次元画像であってもよく、ここで、nは2よりも大きい。
【0063】
本発明は、例えば、画像に対応する信号を処理する装置を使用して実施されてもよい。装置は、例えば、適切なソフトウェアおよび/またはハードウェアの変更が行われた、コンピュータシステムであってもよい。例えば、本発明は、プロセッサまたは制御装置などの、制御または処理手段と、メモリ、磁気記憶装置、CD、DVDなどの画像記憶手段を含む、データ記憶手段と、ディスプレイまたはモニタまたはプリンタなどの、データ出力手段と、キーボードなどのデータ入力手段と、スキャナなどの画像入力手段とを有するか、あるいは、そのような構成要素の任意の組み合わせを、追加の構成要素とともに有する、コンピュータまたは類似物を使用して実施されてもよい。本発明の態様は、ソフトウェアおよび/またはハードウェアの形態で、または特定用途向け装置の中で提供されてもよく、あるいは、チップなどの、特定用途向けモジュールが提供されてもよい。本発明の実施形態による装置内のシステムの構成要素は、例えばインターネットを介して、他の構成要素から離れた場所で提供されてもよい。
【技術分野】
【0001】
画像投影は、動きおよび変化解析などの多くの用途に有用な、積分画像特性を記述する。画像処理アルゴリズムは、2次元問題を、1次元問題の集合に縮小するために、画像投影の計算を使用する。そのような縮小の主な理由としては、以下が挙げられる。
・1D問題の計算複雑度(computational complexity)ははるかに低い。W×Hピクセルのサイズの画像の場合、単純なピクセルごとの走査でさえ、O(WH)回の演算を必要とし、そして、アルゴリズムは、通常、複数回の走査からなる。投影に基づくアルゴリズムは、画像投影を計算するための1回の画像走査と、O(W)およびO(H)の複雑度を有する数回の投影走査とを必要とする。
・いくつかの場合、2D画像関数におけるよりも、1D投影関数における方が、物体またはその他の画像特徴を検出するのは容易である。
【0002】
水平(または垂直)投影の各値は、対応する列(または行)内のすべてのピクセルを総和することによって得られる。したがって、両方の投影に必要とされる加算の回数は、次のようになる。
N標準=2WH (1)
【0003】
3つのカラーチャネルについて計算された、画像投影の例が、図1に示されている。この例は、複雑な構造(橋の垂直部分)が、水平投影において、それらの極小を調べることによって検出可能であることを示している。投影計算の図解的方法は、図2に示されており、各行(または列)内のピクセルの総和が、投影関数の対応する値(矢印によって示す)を決定する。走査されるピクセルは、ドットによってマークされている。
【0004】
リアルタイムシステム、特に、低コストのDSPボード内で実施されるリアルタイムシステムにおいては、投影計算のO(WH)の複雑度でさえ、リアルタイム性能としては依然として高すぎる場合がある。本発明は、特定のアルゴリズムの精度への重大な影響なしに、この複雑度を、2分の1、3分の1、4分の1、・・・に、さらに減少させるための方法を開示する。発明者らは、投影のための近似法を取得し、そのような近似法が、標準の投影と同じ方法で、画像処理アルゴリズム内で使用されてもよいということを示す。
【0005】
本発明の実施形態は、ブロックベースの投影、または単純にBn,m投影と呼ばれる、特殊な画像投影を使用し、ここで、n×mは基本ブロックのサイズである。n×mピクセルからなる重ならないブロックが画像全体を分割し、各ブロックからの正確にn個のピクセルが、水平Bn,m投影のn個の値を更新するために使用され、そして、各ブロックからの正確にm個のピクセルが、垂直Bn,m投影のm個の値を更新するために使用される。
【0006】
ブロックサイズが等しい場合(n=m)、そのようなBn,n投影を、Bn投影と呼ぶ。Bn投影の計算のためのアルゴリズムはより単純であり、一般的なBn,m投影の場合のような追加の計算オーバヘッドを必要としない。
【0007】
Bn,m投影の定義によれば、標準の投影(standard projection)(図1、図2)はB1投影とも呼ばれてもよく、これは、基本ブロックが1つのピクセルからなるということを示している。さらに、定義から、Bn,m投影は標準の投影と同じ長さを有し、したがって、元の画像解像度が維持される。これは、標準の投影が使用される、任意の画像処理アルゴリズムにおいて、Bn,m投影を使用することを可能にする。さらに、画像の前処理を追加せずには標準の投影を適用できない状況において、Bn,m投影のいくつかの特定のケースが使用されてもよい。そのような状況の1つの例は、ベイヤーパターン(Bayer pattern)によって表される画像の処理である。
【0008】
本発明の態様は、添付の特許請求の範囲に記載される。
【0009】
第1の態様では、本発明は、軸上に画像を投影することによって、画像の少なくとも1つの1次元表現を導き出すことを含む、画像を表現する方法を提供する。投影は、前記軸に垂直な画像のそれぞれのライン内で、選択されたピクセルの値を総和することを含む。本方法は、選択されるピクセルの数が、ライン内のピクセルの数よりも少ないことを特徴とする。
【0010】
好ましくは、投影は、複数のそれぞれのライン内で、選択されたピクセルの値を総和することを含み、ここで、少なくとも1つのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少ない。
【0011】
それぞれの軸に垂直な複数のそれぞれのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少なくてもよい。それぞれの軸に垂直なすべてのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少なくてもよい。
【0012】
2つ以上の投影であって、2つ以上のそれぞれの軸上への、投影が存在してもよい。好ましくは、画像は2次元画像であり、そして、2つの各軸のそれぞれの上への投影が存在し、投影は上述したとおりのものである。好ましくは、2つ以上の軸は、水平軸と垂直軸のように、垂直である。
【0013】
一実施形態では、選択されるピクセルは、垂直投影において、i番目ごとの行からのピクセルを除外することによって、そして、水平投影において、j番目ごとの列からのピクセルを除外することによって得られる。例えば、2番目ごとの行、または2番目ごとおよび3番目ごとの行内のピクセルが除外されてもよく、そして、3番目ごとの列、または2番目ごとおよび3番目ごとの列内のピクセルが除外されてもよい。
【0014】
本明細書において、「選択される(選択された)ピクセル(selected pixel)」という用語は、選択されるピクセルの値が、投影についての総和に含まれるということを意味する。「除外される(除外された)ピクセル(omitted pixel)」は、対応するピクセル値が選択されない、すなわち、投影についての総和に含まれないということを意味する。ある投影(たとえば水平投影)について選択されるピクセルは、別の投影(たとえば垂直投影)については除外されてもよく、逆もまた同様である。一般に、ブロックの文脈における「選択される(選択された)ピクセル」とは、そのピクセルが少なくとも1つの投影についての総和に含まれることを意味し、ラインの文脈における「選択される(選択された)ピクセル」とは、そのピクセルが、そのラインに沿った投影における総和に含まれることを意味する。
【0015】
大まかに述べると、提案される方法の実施形態は、以下のように働く。
1)画像走査を、いくつかのピクセルのスキッピングとともに実行する。次の節で説明する、以下の方法のうちの1つ、またはそれらの組み合わせが、走査のために使用されてもよい。
・行/列スキッピング(Row/column skipping)
・対角スキッピング(Diagonal skipping)
・ブロック置換(Block permutation)
2)アクセスされたピクセルのみを使用して、画像行または列を総和することによって、垂直および水平のBn,m投影を計算し、そして、それらを、メモリバッファ内に記憶する。
【0016】
提案される方法の、定性的および数値的比較により、以下の結論がもたらされる。
・次の節で説明する3つの方法は、投影を計算するために、等しい数の基本演算(加算)を必要とする。
・対角スキッピング方法によって必要とされる合計時間は、その他の方法によって必要とされる時間よりも少ない。
・3つの方法は、すべて、n、m=2、3、4について、似た結果を与える。そのようなブロックサイズを使用して得られる投影は、n=m=1を使用して得られる標準の投影から大幅には逸脱しない。
・発明者らは、アルゴリズム速度の、n倍という大幅な増加を得たが、取得される投影は、ノイズおよびアーチファクトによって、標準の投影とは異なる可能性がある。ただし、n、m=2、3、4の場合は、ノイズおよびアーチファクトは非常に小さい。信号処理方法は、通常、そのような小さな因数に対して堅牢であり、したがって、発明者らのBn,m投影は、標準の投影の代わりに使用可能である。
【0017】
本発明の実施形態を、添付の図面を参照して説明する。
【図面の簡単な説明】
【0018】
【図1】従来技術による、画像とその垂直および水平の投影とを示す。
【図2】従来技術による、垂直および水平の投影を示す図である。
【図3】本発明の第1の実施形態による投影を示す図である。
【図4】本発明の第1の実施形態による投影を示す代替の図である。
【図5】本発明の第2の実施形態による投影を示す図である。
【図6】本発明の第3の実施形態による、選択されたピクセルを有するブロックの図である。
【図7】本発明の第4の実施形態による投影を示す図である。
【図8】本発明の第5の実施形態による、画像内の選択されたピクチャを示す図である。
【図9】本発明の第6の実施形態による投影を示す図である。
【図10】投影を使用した水平の動き推定を示す図である。
【図11】動き推定の一形態を示すブロック図である。
【図12】ベイヤーパターンの例である。
【図13】動き推定の別の形態を示すブロック図である。
【図14】動き推定の別の形態を示すブロック図である。
【図15】ベイヤーパターンを使用した動き推定を示す画像である。
【図16】動き検知(motion sensing)の一形態のブロック図である。
【0019】
本発明の実施形態は、参照により本明細書に援用される、本出願人による同時係属出願である英国特許出願第0425430.6号明細書(GB0425430.6)を含む、画像を表現するための画像投影の計算に関する従来技術の発展である。
【0020】
本発明の第1の実施形態による、Bn投影を計算するための手法が、図3に示されている。Bn投影は、行/列スキッピングによって計算される。図3に示す、印を付けられたピクセルのみが、対応する投影を計算するために使用される。
【0021】
2回の画像走査が使用され、それぞれの走査で、対応する投影が計算される。X投影を計算するためには、n番目ごとの行がスキップされる。同様に、Y投影を計算するためには、n番目ごとの列がスキップされる。
【0022】
この方法(行/列スキッピング)は、ブロックベースの表現によって説明することも可能である。図4は、2×2ブロックを使用する例を示す。図4(a)は、ブロックサイズn=2およびn=3についての、実際の画像領域(図1の画像の小さな領域など)の例を示す。スキップされるピクセルは、白で示されている。図4(b)は、ブロックサイズn=2およびn=3についての、計算方法の概略図を示す。印を付けられたピクセルのみが、対応する投影を計算するために使用される。黒のピクセルは、両方の投影のために使用される。灰色のピクセルは、X投影のために使用される。白のピクセルは、Y投影のために使用される。
【0023】
この例は、各ブロックのうちの3つのピクセルのみが使用されるため、アルゴリズムの計算複雑度は3WH/4に比例するということを示す。一般的なn×nブロックの場合については、計算複雑度C行/列は、(2n−1)WH/n2に比例する:
C行/列(n)=k1(2n−1)WH/n2 (2)
上式で、定数k1は、画像走査の追加のオーバヘッドに相当する。この方法によって必要とされる加算の回数は、1つのブロックからの2(n−1)個のピクセルが投影に1回加算され、そのブロックからの1つのピクセルのみが2回使用されるという事実に基づいて取得される。したがって、加算の回数は次のようになる。
N行/列(n)=2WH/n≦N標準 (3)
【0024】
第2の実施形態では、Bn投影は、対角スキッピングによって計算される。
【0025】
対角スキッピングの方法は、図5に示されている。図5(a)は、n=2およびn=3についての、実際の画像(図1の画像の小さな領域など)の例を示す。スキップされるピクセルは、白で示されている。図5(b)は、計算方法の概略図である。各基本ブロックの中の、(ドットによって印を付けられた)主対角線からのピクセルのみが使用される。
【0026】
Bn投影を計算するために、いくつかの画像対角線がスキップされ、そして、等式(4)を満足するピクセル(x,y)のみが使用される。
(x+y) mod n=0 (4)
【0027】
これは、各基本ブロックの中で、主対角線(the main diagonal)からのピクセルのみが使用されるということを意味している。したがって、この方法の計算複雑度C対角は、n(各ブロックの主対角線内のピクセルの数)にブロックの数WH/n2を乗算した値に比例する:
C対角=k2WH/n (5)
【0028】
定数k2もまた、(4)の計算と画像走査のその他のオーバヘッドとを考慮に入れる。実験的なテストから、C対角<C行/列ということになる。ブロックの対角線に属する各ピクセルは2回使用され、したがって、加算の回数は次のようになる:
N対角(n)=2WH/n=N行/列(n) (6)
【0029】
第3の実施形態では、Bn投影は、ブロック置換によって計算される。図6は、行(または、同等に、列)置換によって生成された、投影において使用される選択されるピクセルを示す3×3ブロックの例を示す。
【0030】
第3の実施形態のBn投影計算の方法は、第2の実施形態の対角スキッピング方法の変更形態と考えることができる。この方法では、各基本ブロックは、行(または、同等に、列)置換によって予備的に変換される(図6)。ランダムな、またはランダムではない、置換の組が使用されてもよい。
【0031】
図7は、ランダムな置換を用いてこの方法を使用する例を示す。n=2およびn=3についての、基本ブロックのランダムな置換が示されている。図7(a)は、実際の画像(図1の画像の小さな領域など)の例を示す。スキップされるピクセルは、白で示されている。図7(b)は、計算方法の概略図である。印を付けられたピクセルのみが、投影計算のために使用される。
【0032】
計算複雑度C置換は、(5)に類似している:
C置換=k3WH/n (7)
ただし、ピクセルを走査するために、より複雑なアルゴリズムが使用される。走査アルゴリズムの効率的な実施のためには、(図6内で印を付けられた)ピクセル位置が、事前に計算され、そしてメモリテーブル内に記憶されるべきである。(7)における定数k3は、走査アルゴリズムの複雑度を考慮に入れ、そして、一般に、C対角<C置換である。この方法では、各ブロックからのn個のピクセルが(水平および垂直の両方の投影に寄与するために)2回使用され、したがって、加算の回数は次のようになる。
N置換(n)=2WH/n=N対角(n) (8)
【0033】
上記の実施形態の変更形態は、複数の異なるブロックサイズの組み合わせを含む。
【0034】
いくつかの画像処理方法では、いくつかの画像部分が、その他の画像部分よりも重要な場合がある。例えば、移動しているビデオカメラの場合、カメラの移動方向とは反対側の画像境界の付近のピクセルは、フレームごとに消失する。そのようなピクセルは、通常、解析から除外されるか、または、窓掛け処理(windowing)などの、複数の異なる技術によって、それらの影響が減少させられる。この場合、より概算的かつより高速な、画像投影計算の方法が使用されてもよい。例えば、画像の中央部では、B2投影が使用されてもよく、そして、境界の付近ではBn投影(n>2)が使用されてもよい(図8を参照)。図8では、ブロック置換方法が、説明の目的のためにのみ使用されている。複数の異なる方法が、画像の複数の異なる領域内で使用されてもよい。この方法の追加のオーバヘッドは、各ピクセルが、投影内で総和される前に、そのブロックのサイズ(nに等しい)によって重み付けされなければならないということである。
【0035】
一般的なBn,m投影の場合が、1:1とは異なるアスペクト比を有する画像に対して使用されてもよい。例えば、640×480ピクセルの標準VGA画像の場合、等しい数のピクセルが、垂直および水平の両方の投影に寄与することを確実にするために、アスペクト比4:3を有するブロックB4,3が使用されてもよい。そのような計算は、例えば、図9に示すような、対角スキッピング方法と列スキッピング方法との組み合わせによって達成されてもよい。図9において、黒のピクセルは両方の投影に寄与し、灰色のピクセルは水平投影のみに寄与する。
【0036】
上述のように、異なるブロックサイズが画像の異なる領域のために使用されてもよい。同様に、投影計算(ピクセル選択)の異なる方法が、画像の異なる領域について、または、1つのブロック内で組み合わせて、使用されてもよい。複数の異なる方法が組み合わされてもよい。
【0037】
投影計算の結果は、画像の表現、すなわち画像記述子と見なされてもよい。より具体的には、結果は、スパース積分画像記述子(sparse integral image descriptors)と見なされてもよい。
【0038】
上述の、画像を表現する方法は、画像を解析するために画像投影を計算する、任意の画像処理システムにおいて適用可能である。本提案の画像投影の高速計算から利益を得るであろう3つの既知の画像処理方法への、本発明の実施形態の適用例について、以下に概説する。さらに、新規な適用例、特に、ベイヤーパターンからの動き推定と、それから得られる、自己動きセンサ(ego-motion sensor)とが、提案される。
【0039】
第1の既知の技術は、画像のシフトはシフトされた投影をもたらすという事実に基づいた、主要な平行移動の動き推定(dominant translational motion estimation)である。図10は、複数の水平投影の間における1Dシフトを推定することによる、3つの連続したビデオフレーム間の、水平の動き推定を示す。この話題に関する最先の研究のうちの1つは、S.Alliney、C.Morandi著、Digital image registration using projections、IEEE TPAMI−8、No.2、1986年3月、222〜223頁において報告された。これは、本出願人による同時係属出願である英国特許出願第0425430.6号明細書(GB 0425430.6)においてさらに改良された。この方法について、本発明者らは、標準の投影の代わりにBn投影を使用することを提案する。
【0040】
連続する複数の画像から計算される、2つ以上の画像投影が、主要な動き(dominant motion)の対応する成分を推定するために使用される(図10)。図10は、3つの連続したフレーム(フレームK−2、フレームK−1、およびフレームK)と、それらの対応する水平投影とを示す。正規化相互相関(normalized cross-correlation)(NCC)、差分絶対値和(sum of absolute difference)(SAD)または差分二乗和(sum of squared difference)(SSD)、あるいは位相相関(phase correlation)(PC)などの、信号シフト推定の任意の従来技術による方法が、投影を比較してフレーム間のシフトを決定するために使用されてもよい。
【0041】
第2の既知の技術は、画像記述子の抽出と、記述子のマッチングとの、2つの主なステップからなる、主要な動き推定方法である(図11を参照)。図11(そしてさらに、図13、図14、および図16)は、動き推定または動き検知方法のステップを示す。図に示されている方法のステップは、装置の対応する構成要素またはモジュールによって実施されてもよい。
【0042】
図11に示すように、1つの画像記述子は、水平(X記述子)および垂直(Y記述子)の、2つの独立した部分からなる。記述子抽出の主な着想は、処理の初期段階において、2D画像情報を1D信号に変換することである。本発明の実施形態を使用して、記述子は、Bn投影から導き出される。どのような種類のマッチング方法が使用されるかに応じて、記述子は以下であってもよい。
・Bn投影そのもの(信号領域内でのマッチング用)
・Bn投影のフーリエ変換(周波数領域内でのマッチング用)
【0043】
記述子マッチングブロックは、現在のフレームの記述子と、直前のフレームについて計算された記述子とを使用する。提案される方法の一実施形態では、1Dシフトの推定のために、位相相関が使用される。この方法は、フーリエ変換とシフト定理(Shift Theorem)とに基づく。2つの信号(提案される方法ではいずれもBn投影。例えば、s1(x)およびs2(x))が、次のように平行移動aだけ異なると仮定する。
s(x)=s’(x+a)
【0044】
その場合、位相相関方法を次のように適用する。
【0045】
【数1】
【0046】
上式で、F(s)は、記述子抽出段階で事前に計算される、信号sのフーリエ変換であり、F*(s)は、F(s)の複素共役である。これにより、相対変位値におけるパルスが得られる。
C(x)=δ(x−a)
【0047】
変位aは、結果として得られる信号C(x)内の最も高いピークを見つけることによって決定される。
【0048】
主要な動きを検出する、別の既知の方法は、ベイヤーパターンを使用する。シングルチップビデオカメラの大多数、およびほとんどすべてのデジタルスチルカメラは、いわゆるベイヤーパターンセンサを使用する。これらのセンサは、CMOSまたはCCDデバイスのいずれかである場合があるが、原理は同じである。米国特許第3971065号明細書のベイヤーパターンアプローチでは、カラーフィルタアレイの多くの可能な実施のうちの1つとしての、特殊なパターンを使用する。ベイヤーパターンの例を、図12に示す。その他の実施は、ほとんどが、輝度チャネル(luminance channel)(緑)は色チャネル(chromatic channel)(赤および青)よりも高いレートでサンプリングされる必要があるという原理を使用する。輝度を表すものとしての緑の選択は、人間の目の輝度応答曲線が、緑の光の周波数(約550nm)に近いという事実によって説明することができる。
【0049】
ベイヤーパターンからの画像を処理するためには、多くの方法が存在する。デジタルカメラ内の一般的な画像処理パイプラインは、主として、以下のステップに分けられる。空間デモザイキング(spatial demosaicing)と、それに続く、色およびガンマ補正(図13−ビデオカメラまたはDSCからの出力画像を使用した動き推定)。各ピクセルにおける色値を補間するために、ベイヤーは、単純な双一次補間を提案した。デジタルスチルカメラの開発の初期において、米国特許第4642678号明細書では、一定の色相に基づいた補間(constant hue-based interpolation)を使用することが提案されたが、その理由は、デモザイキングプロセスにおけるピクセルのアーチファクトは、色相の突然のジャンプの中で発生するからである。次に、米国特許4774565号明細書では、色フリンジ(colour fringes)を回避するために、色チャネルのメジアンに基づいた補間(median-based interpolation)を使用することが提案された。米国特許第5382976号明細書では、エッジベースの技術(edge-based technique)を使用することによる、フルカラー画像の適応的な補間が提案された。米国特許5373322号明細書では、米国特許第5,382,976号明細書のアプローチの拡張と見ることができる、承認されたエッジベースの方法が提案された。米国特許5629734号明細書では、両方のエッジベースの方法の概念が使用され、それらのアプローチの組み合わせおよび拡張が作成された。ベイヤーパターンデモザイキングの問題は、コンピュータビジョンコミュニティにおいて依然として盛んに話題となっている。例えば、Henrique Malvar,Li−wei He,およびRoss Cutler著,High−quality linear interpolation for demosaicing of Bayer−patterned color images,IEEE International Conference on Speech, Acoustics, and Signal Processing、2004年を参照されたい。
【0050】
動き推定方法を含む、画像処理方法のほとんどは、最終的なカラー画像(ベイヤーパターン処理の結果)がピクセル補間によって得られることを要求する。直接的な方法(direct method)の設計は、(動きなどの)高レベルの情報を、画像センサデータから直接(すなわち、コストのかかるデモザイキングなしに)推定するのを可能にする。
【0051】
主要な動き推定方法における垂直および水平の投影は、以下のうちの1つを使用して計算される。
・任意のRGB画像チャネル(好ましくは、最も大きいダイナミックレンジを有する、緑)
・(すべてのカラーチャネルから導き出される)画像輝度
・通常はカメラバッファから得られる、YCrCbカラースペースのYチャネル
・元の、または処理されたカラーチャネルの、任意のその他の組み合わせ
【0052】
したがって、投影に基づく方法を使用するためには、ベイヤーパターンを処理し、そして、それを標準のカラー画像に変換する必要がある。この処理の速度は、埋め込まれた動き推定アルゴリズムのために好適ではない場合がある。したがって、ベイヤーパターンの中間処理を回避するために、この方法のさらなる変更が必要とされる。
【0053】
垂直および水平の投影は、画像ピクセルを総和することによって計算される。そして、この計算は、上記で示したように、正確に2WH回の加算を必要とする。画像の、m分の1へのダウンサンプリングは、加算の回数をWH/m2に減少させるが、推定される動きベクトルの精度を比例して減少させ、そして、ダウンサンプリング処理自体のために、WHに比例した回数の追加の演算を必要とする場合がある。
【0054】
本発明のさらなる実施形態は、図14および図15に示すような、ベイヤーパターン(またはベイヤー様のパターン)に直接働きかける、高速動き推定アルゴリズムを提供する。
【0055】
図14は、初期段階における動き推定を有する、処理パイプラインのブロック図である。図15は、ベイヤーパターン表現を使用した、画像の動き推定を示す。
【0056】
本実施形態によれば、Bn投影が、対角スキッピングまたはブロック置換方法によって計算される。n=2を考慮する場合(図5、左列)、このパターンは、ベイヤーパターンの緑チャネル(図12)、またはCMYベイヤーパターンの黄チャネルに、正確に対応する。ブロック置換方法における置換の組を調節することによって、複数の異なるベイヤー様パターンと、疑似ランダムベイヤーパターンとが、モデル化されてもよい。提案される方法の有用な特性としては、以下が挙げられる。
・CCDまたはCMOSセンサからの、ベイヤーパターン(RGBおよびCMYの両方)の直接使用、および、ピクセルの数に比例した複雑度を有する高価な色補間および補正アルゴリズムの回避。
・センサから画像を受信した直後の、最初期段階における動き推定。検出された動きに関する情報は、処理の他の段階において、例えば、デモザイキングの前の、ベイヤーパターンのノイズ除去のために、または、動きぼやけ(motion blur)の低減のために使用されてもよい。
対角スキッピング方法により計算されるBn投影を使用することによって、ピクセル数の1/nに比例した複雑度を有する、より高速な変更が可能である。
・動きベクトルの元の解像度が維持される(および、サブピクセル補間を使用してさらに向上させられる)。
・ブロック置換方法により計算されるBn投影を使用することによって、ベイヤーパターンの、複数の異なる構成への拡張が可能である。
【0057】
セキュリティまたはその他のシステム用の、低コストの、自己動きビデオセンサを作成するために、前節で提示した方法が使用されてもよい。例えば、このセンサは、動きを開始した場合、信号を生成する。そのようなセンサは、(好ましくは、低コストの)ビデオカメラと、小さなCCDまたはCMOSマトリクスとからなる。この場合、ベイヤーパターン処理のために通常使用される(図16)、すべての色補正/補間手順は不要であり、そして、Bn投影を介した動き推定は、そのようなセンサを実施するための非常に効果的な方法である。図17は、そのようなセンサの働きの抽象ブロック手法(abstract block-scheme)を示す。
【0058】
画像投影は、全体照明の変化を含む、突然の照明の変化を検出するために使用されてもよい。画像投影の挙動は、照明の変化を反映する。例えば、連続したフレームからの投影の、負の差は、照明レベルの低下を知らせる。そのような特徴は、画像処理システムに、そのパラメータを新しい照明レベルのために適合させるように通知するために使用されてもよい。プロセス全体の速度を低下させないために、この補助的特徴は、高速で実行されることが重要である。Bn投影を使用することにより、この特徴の性能はn倍向上する。
【0059】
比較的単純なシーン(暗い背景の中の明るい物体、またはその逆など)では、物体追跡の2D問題を、画像投影を使用して、1D追跡問題に縮小することが可能である。そのような場合、物体の位置は、投影の極大(または極小)によって決定される。そのような方法の、可能な適用領域は、航空機追跡、顕微鏡画像、およびレーダ画像である。物体が多数の場合、または時間が制限される場合、性能を向上させるために、標準の投影の代わりにBn投影が使用されてもよい。
【0060】
上記の各実施形態においては、一般に、2つの投影(水平および垂直)が計算および使用される。しかし、1つのみの投影が計算および/または使用されてもよい(例えば、水平の平行移動の動き推定の例におけるように)。
【0061】
本明細書においては、「画像」および「フレーム」という用語は、画像単位(フィルタリング後のものを含む)を記述するために使用されるが、この用語は、画像、フィールド、ピクチャ、あるいは、画像やフレームなどのサブ単位または領域といった、その他の類似した用語にも適用される。ピクセル、およびピクセルのブロックまたはグループという用語は、適切な場合、区別なく使用されることがある。本明細書において、画像という用語は、文脈から明らかである場合を除き、画像全体、または画像の領域を意味する。同様に、画像の領域は、画像全体を意味する場合がある。画像は、フレームまたはフィールドを含み、そして、静止画像に、あるいは、フィルムまたはビデオなどの画像シーケンスの中の画像に、あるいは、関連する画像グループの中の画像に、関連する。
【0062】
画像は、グレースケールであってもカラー画像であってもよく、あるいは別のタイプのマルチスペクトル画像(例えば、IR、UV、またはその他の電磁画像(electromagnetic image))であってもよく、あるいは音響画像(acoustic image)であってもよい。画像は、好ましくは2次元画像であるが、n次元画像であってもよく、ここで、nは2よりも大きい。
【0063】
本発明は、例えば、画像に対応する信号を処理する装置を使用して実施されてもよい。装置は、例えば、適切なソフトウェアおよび/またはハードウェアの変更が行われた、コンピュータシステムであってもよい。例えば、本発明は、プロセッサまたは制御装置などの、制御または処理手段と、メモリ、磁気記憶装置、CD、DVDなどの画像記憶手段を含む、データ記憶手段と、ディスプレイまたはモニタまたはプリンタなどの、データ出力手段と、キーボードなどのデータ入力手段と、スキャナなどの画像入力手段とを有するか、あるいは、そのような構成要素の任意の組み合わせを、追加の構成要素とともに有する、コンピュータまたは類似物を使用して実施されてもよい。本発明の態様は、ソフトウェアおよび/またはハードウェアの形態で、または特定用途向け装置の中で提供されてもよく、あるいは、チップなどの、特定用途向けモジュールが提供されてもよい。本発明の実施形態による装置内のシステムの構成要素は、例えばインターネットを介して、他の構成要素から離れた場所で提供されてもよい。
【特許請求の範囲】
【請求項1】
画像を表現する方法であって、
前記方法は、軸上に前記画像を投影することによって前記画像の少なくとも1つの1次元表現を導き出すことを含み、
前記投影は、前記軸に垂直な前記画像のそれぞれのライン内での、選択されたピクセルの値の総和である
方法において、
選択されるピクセルの数は前記ライン内のピクセルの数よりも少ないことを特徴とする、方法。
【請求項2】
前記投影は、複数のそれぞれのライン内での、選択されたピクセルの値の総和であり、
少なくとも1つのライン内の、選択されるピクセルの数は、前記それぞれのライン内のピクセルの数よりも少ない、請求項1に記載の方法。
【請求項3】
2次元画像を含む画像を表現するための、請求項1または2に記載の方法であって、
前記方法は、水平投影および垂直投影のうちの少なくとも1つを、水平および垂直軸にそれぞれ垂直な、列または行内の、ピクセル値を総和することによって導き出すことを含む、方法。
【請求項4】
水平投影において、1つ以上の行からのすべてのピクセルを除外すること、および/または、
垂直投影において、1つ以上の列からのすべてのピクセルを、除外すること
を含む、請求項3に記載の方法。
【請求項5】
水平投影において、i番目ごとの行からのピクセルを除外すること、および/または、
垂直投影において、j番目ごとの列からのピクセルを除外すること
を含み、
iおよびjは1よりも大きい整数である、請求項1〜4のいずれか一項に記載の方法。
【請求項6】
サイズm×nのブロックに分割された画像について、少なくとも1つのブロック内で、m×nよりも少ないピクセルが選択される、請求項1〜5のいずれか一項に記載の方法。
【請求項7】
画像をブロックに分割することを含む、請求項6に記載の方法。
【請求項8】
mはn以上であるサイズm×nのブロックについて、サイズn×nの前記ブロックの対角線のピクセルまたはサイズn×nのサブブロックの対角線のピクセルが選択される、請求項6または7に記載の方法。
【請求項9】
前記n×nのブロックまたはサブブロックの、前記対角線上の前記ピクセル以外のピクセルは除外される、請求項8に記載の方法。
【請求項10】
少なくとも1つのブロックについて、前記総和のためのピクセルはランダムに選択される、請求項6または7に記載の方法。
【請求項11】
少なくとも1つのブロック内の、前記選択されたピクセルを、行および/または列ごとに置換することをさらに含む、請求項8に記載の方法。
【請求項12】
異なるブロック内では選択されるピクセルのパターンが異なる、請求項6〜11のいずれか一項に記載の方法。
【請求項13】
前記画像の異なる領域内では異なるブロックサイズを使用する、請求項6〜12のいずれか一項に記載の方法。
【請求項14】
画像または画像のシーケンスを処理する方法であって、
前記方法は、前記画像の少なくとも1つの1次元表現を使用し、
前記1次元表現は、請求項1〜13のいずれか一項に記載の方法を使用して導き出される、方法。
【請求項15】
請求項1〜13のいずれか一項に記載の方法を使用して導き出された、複数の画像のそれぞれの1次元表現を比較することによって、複数の画像を比較することを含む、請求項14に記載の方法。
【請求項16】
動きを検出するための、かつ/または、物体追跡のための、請求項14または15に記載の方法。
【請求項17】
画像のシーケンス内の、例えば主要な平行移動の動きなどの、主要な動きを推定するための、請求項15に記載の方法。
【請求項18】
前記画像の少なくとも1つの1次元表現を、ベイヤーパターンセンサの出力から導き出すことを含む、請求項14〜17のいずれか一項に記載の方法。
【請求項19】
前記選択されたピクセルの配置は、前記ベイヤーパターン内の1つ以上のチャネルのパターンに関連する、請求項18に記載の方法。
【請求項20】
前記ベイヤーパターンセンサの前記出力の前記処理、例えば、動き推定または検出のための前記ベイヤーパターンセンサの前記出力の前記処理は、前記ベイヤーパターンセンサの前記出力の処理と並列に実行されて画像を作成する、請求項18または19に記載の方法。
【請求項21】
前記ベイヤーパターンセンサの前記出力の前記処理、例えば、動き推定または検出のための、前記ベイヤーパターンセンサの前記出力の前記処理は、前記ベイヤーパターンセンサの前記出力の処理の前に実行されて画像を作成し、
任意選択で、そのような推定される動きは、画像のノイズ除去またはぼやけ除去のために使用される、請求項18または19に記載の方法。
【請求項22】
請求項1〜13のいずれか一項に記載の方法を使用して導き出された、画像の表現の使用であって、記憶、送信、受信などである使用。
【請求項23】
請求項1〜21のいずれか一項に記載の方法を実行するようにプログラムされた、制御装置。
【請求項24】
請求項1〜21のいずれか一項に記載の方法を実行するための装置。
【請求項25】
記述子抽出器モジュール(descriptor extractor module)を含む画像処理装置を具備する、請求項24に記載の装置。
【請求項26】
記述子マッチングモジュール(descriptor matching module)をさらに具備する、請求項24または25に記載の装置。
【請求項27】
請求項1〜21のいずれか一項に記載の方法を実行するための、コンピュータプログラム、システム、またはコンピュータ読み取り可能記憶媒体。
【請求項1】
画像を表現する方法であって、
前記方法は、軸上に前記画像を投影することによって前記画像の少なくとも1つの1次元表現を導き出すことを含み、
前記投影は、前記軸に垂直な前記画像のそれぞれのライン内での、選択されたピクセルの値の総和である
方法において、
選択されるピクセルの数は前記ライン内のピクセルの数よりも少ないことを特徴とする、方法。
【請求項2】
前記投影は、複数のそれぞれのライン内での、選択されたピクセルの値の総和であり、
少なくとも1つのライン内の、選択されるピクセルの数は、前記それぞれのライン内のピクセルの数よりも少ない、請求項1に記載の方法。
【請求項3】
2次元画像を含む画像を表現するための、請求項1または2に記載の方法であって、
前記方法は、水平投影および垂直投影のうちの少なくとも1つを、水平および垂直軸にそれぞれ垂直な、列または行内の、ピクセル値を総和することによって導き出すことを含む、方法。
【請求項4】
水平投影において、1つ以上の行からのすべてのピクセルを除外すること、および/または、
垂直投影において、1つ以上の列からのすべてのピクセルを、除外すること
を含む、請求項3に記載の方法。
【請求項5】
水平投影において、i番目ごとの行からのピクセルを除外すること、および/または、
垂直投影において、j番目ごとの列からのピクセルを除外すること
を含み、
iおよびjは1よりも大きい整数である、請求項1〜4のいずれか一項に記載の方法。
【請求項6】
サイズm×nのブロックに分割された画像について、少なくとも1つのブロック内で、m×nよりも少ないピクセルが選択される、請求項1〜5のいずれか一項に記載の方法。
【請求項7】
画像をブロックに分割することを含む、請求項6に記載の方法。
【請求項8】
mはn以上であるサイズm×nのブロックについて、サイズn×nの前記ブロックの対角線のピクセルまたはサイズn×nのサブブロックの対角線のピクセルが選択される、請求項6または7に記載の方法。
【請求項9】
前記n×nのブロックまたはサブブロックの、前記対角線上の前記ピクセル以外のピクセルは除外される、請求項8に記載の方法。
【請求項10】
少なくとも1つのブロックについて、前記総和のためのピクセルはランダムに選択される、請求項6または7に記載の方法。
【請求項11】
少なくとも1つのブロック内の、前記選択されたピクセルを、行および/または列ごとに置換することをさらに含む、請求項8に記載の方法。
【請求項12】
異なるブロック内では選択されるピクセルのパターンが異なる、請求項6〜11のいずれか一項に記載の方法。
【請求項13】
前記画像の異なる領域内では異なるブロックサイズを使用する、請求項6〜12のいずれか一項に記載の方法。
【請求項14】
画像または画像のシーケンスを処理する方法であって、
前記方法は、前記画像の少なくとも1つの1次元表現を使用し、
前記1次元表現は、請求項1〜13のいずれか一項に記載の方法を使用して導き出される、方法。
【請求項15】
請求項1〜13のいずれか一項に記載の方法を使用して導き出された、複数の画像のそれぞれの1次元表現を比較することによって、複数の画像を比較することを含む、請求項14に記載の方法。
【請求項16】
動きを検出するための、かつ/または、物体追跡のための、請求項14または15に記載の方法。
【請求項17】
画像のシーケンス内の、例えば主要な平行移動の動きなどの、主要な動きを推定するための、請求項15に記載の方法。
【請求項18】
前記画像の少なくとも1つの1次元表現を、ベイヤーパターンセンサの出力から導き出すことを含む、請求項14〜17のいずれか一項に記載の方法。
【請求項19】
前記選択されたピクセルの配置は、前記ベイヤーパターン内の1つ以上のチャネルのパターンに関連する、請求項18に記載の方法。
【請求項20】
前記ベイヤーパターンセンサの前記出力の前記処理、例えば、動き推定または検出のための前記ベイヤーパターンセンサの前記出力の前記処理は、前記ベイヤーパターンセンサの前記出力の処理と並列に実行されて画像を作成する、請求項18または19に記載の方法。
【請求項21】
前記ベイヤーパターンセンサの前記出力の前記処理、例えば、動き推定または検出のための、前記ベイヤーパターンセンサの前記出力の前記処理は、前記ベイヤーパターンセンサの前記出力の処理の前に実行されて画像を作成し、
任意選択で、そのような推定される動きは、画像のノイズ除去またはぼやけ除去のために使用される、請求項18または19に記載の方法。
【請求項22】
請求項1〜13のいずれか一項に記載の方法を使用して導き出された、画像の表現の使用であって、記憶、送信、受信などである使用。
【請求項23】
請求項1〜21のいずれか一項に記載の方法を実行するようにプログラムされた、制御装置。
【請求項24】
請求項1〜21のいずれか一項に記載の方法を実行するための装置。
【請求項25】
記述子抽出器モジュール(descriptor extractor module)を含む画像処理装置を具備する、請求項24に記載の装置。
【請求項26】
記述子マッチングモジュール(descriptor matching module)をさらに具備する、請求項24または25に記載の装置。
【請求項27】
請求項1〜21のいずれか一項に記載の方法を実行するための、コンピュータプログラム、システム、またはコンピュータ読み取り可能記憶媒体。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【公表番号】特表2009−545794(P2009−545794A)
【公表日】平成21年12月24日(2009.12.24)
【国際特許分類】
【出願番号】特願2009−522338(P2009−522338)
【出願日】平成19年8月2日(2007.8.2)
【国際出願番号】PCT/GB2007/002948
【国際公開番号】WO2008/015446
【国際公開日】平成20年2月7日(2008.2.7)
【出願人】(501253316)ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC R&D CENTRE EUROPE B.V.
【住所又は居所原語表記】20 Frederick Sanger Road, The Surrey Research Park, Guildford, Surrey GU2 5YD, Great Britain
【Fターム(参考)】
【公表日】平成21年12月24日(2009.12.24)
【国際特許分類】
【出願日】平成19年8月2日(2007.8.2)
【国際出願番号】PCT/GB2007/002948
【国際公開番号】WO2008/015446
【国際公開日】平成20年2月7日(2008.2.7)
【出願人】(501253316)ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC R&D CENTRE EUROPE B.V.
【住所又は居所原語表記】20 Frederick Sanger Road, The Surrey Research Park, Guildford, Surrey GU2 5YD, Great Britain
【Fターム(参考)】
[ Back to top ]