(57)【要約】  画像を表現する方法は、軸上に画像を投影することによって画像の少なくとも１つの１次元表現を導き出すことを含み、投影は、前記軸に垂直な画像のそれぞれのライン内での、選択されたピクセルの値の総和であり、選択されるピクセルの数は、ライン内のピクセルの数よりも少ないことを特徴とする。
2009545794.tif 000002
【特許請求の範囲】
【請求項１】
画像を表現する方法であって、
前記方法は、軸上に前記画像を投影することによって前記画像の少なくとも１つの１次元表現を導き出すことを含み、
前記投影は、前記軸に垂直な前記画像のそれぞれのライン内での、選択されたピクセルの値の総和である
方法において、
選択されるピクセルの数は前記ライン内のピクセルの数よりも少ないことを特徴とする、方法。
【請求項２】
前記投影は、複数のそれぞれのライン内での、選択されたピクセルの値の総和であり、
少なくとも１つのライン内の、選択されるピクセルの数は、前記それぞれのライン内のピクセルの数よりも少ない、請求項１に記載の方法。
【請求項３】
２次元画像を含む画像を表現するための、請求項１または２に記載の方法であって、
前記方法は、水平投影および垂直投影のうちの少なくとも１つを、水平および垂直軸にそれぞれ垂直な、列または行内の、ピクセル値を総和することによって導き出すことを含む、方法。
【請求項４】
水平投影において、１つ以上の行からのすべてのピクセルを除外すること、および／または、
垂直投影において、１つ以上の列からのすべてのピクセルを、除外すること
を含む、請求項３に記載の方法。
【請求項５】
水平投影において、ｉ番目ごとの行からのピクセルを除外すること、および／または、
垂直投影において、ｊ番目ごとの列からのピクセルを除外すること
を含み、
ｉおよびｊは１よりも大きい整数である、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
サイズｍ×ｎのブロックに分割された画像について、少なくとも１つのブロック内で、ｍ×ｎよりも少ないピクセルが選択される、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
画像をブロックに分割することを含む、請求項６に記載の方法。
【請求項８】
ｍはｎ以上であるサイズｍ×ｎのブロックについて、サイズｎ×ｎの前記ブロックの対角線のピクセルまたはサイズｎ×ｎのサブブロックの対角線のピクセルが選択される、請求項６または７に記載の方法。
【請求項９】
前記ｎ×ｎのブロックまたはサブブロックの、前記対角線上の前記ピクセル以外のピクセルは除外される、請求項８に記載の方法。
【請求項１０】
少なくとも１つのブロックについて、前記総和のためのピクセルはランダムに選択される、請求項６または７に記載の方法。
【請求項１１】
少なくとも１つのブロック内の、前記選択されたピクセルを、行および／または列ごとに置換することをさらに含む、請求項８に記載の方法。
【請求項１２】
異なるブロック内では選択されるピクセルのパターンが異なる、請求項６〜１１のいずれか一項に記載の方法。
【請求項１３】
前記画像の異なる領域内では異なるブロックサイズを使用する、請求項６〜１２のいずれか一項に記載の方法。
【請求項１４】
画像または画像のシーケンスを処理する方法であって、
前記方法は、前記画像の少なくとも１つの１次元表現を使用し、
前記１次元表現は、請求項１〜１３のいずれか一項に記載の方法を使用して導き出される、方法。
【請求項１５】
請求項１〜１３のいずれか一項に記載の方法を使用して導き出された、複数の画像のそれぞれの１次元表現を比較することによって、複数の画像を比較することを含む、請求項１４に記載の方法。
【請求項１６】
動きを検出するための、かつ／または、物体追跡のための、請求項１４または１５に記載の方法。
【請求項１７】
画像のシーケンス内の、例えば主要な平行移動の動きなどの、主要な動きを推定するための、請求項１５に記載の方法。
【請求項１８】
前記画像の少なくとも１つの１次元表現を、ベイヤーパターンセンサの出力から導き出すことを含む、請求項１４〜１７のいずれか一項に記載の方法。
【請求項１９】
前記選択されたピクセルの配置は、前記ベイヤーパターン内の１つ以上のチャネルのパターンに関連する、請求項１８に記載の方法。
【請求項２０】
前記ベイヤーパターンセンサの前記出力の前記処理、例えば、動き推定または検出のための前記ベイヤーパターンセンサの前記出力の前記処理は、前記ベイヤーパターンセンサの前記出力の処理と並列に実行されて画像を作成する、請求項１８または１９に記載の方法。
【請求項２１】
前記ベイヤーパターンセンサの前記出力の前記処理、例えば、動き推定または検出のための、前記ベイヤーパターンセンサの前記出力の前記処理は、前記ベイヤーパターンセンサの前記出力の処理の前に実行されて画像を作成し、
任意選択で、そのような推定される動きは、画像のノイズ除去またはぼやけ除去のために使用される、請求項１８または１９に記載の方法。
【請求項２２】
請求項１〜１３のいずれか一項に記載の方法を使用して導き出された、画像の表現の使用であって、記憶、送信、受信などである使用。
【請求項２３】
請求項１〜２１のいずれか一項に記載の方法を実行するようにプログラムされた、制御装置。
【請求項２４】
請求項１〜２１のいずれか一項に記載の方法を実行するための装置。
【請求項２５】
記述子抽出器モジュール（descriptor extractor module）を含む画像処理装置を具備する、請求項２４に記載の装置。
【請求項２６】
記述子マッチングモジュール（descriptor matching module）をさらに具備する、請求項２４または２５に記載の装置。
【請求項２７】
請求項１〜２１のいずれか一項に記載の方法を実行するための、コンピュータプログラム、システム、またはコンピュータ読み取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
画像投影は、動きおよび変化解析などの多くの用途に有用な、積分画像特性を記述する。画像処理アルゴリズムは、２次元問題を、１次元問題の集合に縮小するために、画像投影の計算を使用する。そのような縮小の主な理由としては、以下が挙げられる。
・１Ｄ問題の計算複雑度（computational complexity）ははるかに低い。Ｗ×Ｈピクセルのサイズの画像の場合、単純なピクセルごとの走査でさえ、Ｏ（ＷＨ）回の演算を必要とし、そして、アルゴリズムは、通常、複数回の走査からなる。投影に基づくアルゴリズムは、画像投影を計算するための１回の画像走査と、Ｏ（Ｗ）およびＯ（Ｈ）の複雑度を有する数回の投影走査とを必要とする。
・いくつかの場合、２Ｄ画像関数におけるよりも、１Ｄ投影関数における方が、物体またはその他の画像特徴を検出するのは容易である。
【０００２】
水平（または垂直）投影の各値は、対応する列（または行）内のすべてのピクセルを総和することによって得られる。したがって、両方の投影に必要とされる加算の回数は、次のようになる。
Ｎ標準＝２ＷＨ      （１）
【０００３】
３つのカラーチャネルについて計算された、画像投影の例が、図１に示されている。この例は、複雑な構造（橋の垂直部分）が、水平投影において、それらの極小を調べることによって検出可能であることを示している。投影計算の図解的方法は、図２に示されており、各行（または列）内のピクセルの総和が、投影関数の対応する値（矢印によって示す）を決定する。走査されるピクセルは、ドットによってマークされている。
【０００４】
リアルタイムシステム、特に、低コストのＤＳＰボード内で実施されるリアルタイムシステムにおいては、投影計算のＯ（ＷＨ）の複雑度でさえ、リアルタイム性能としては依然として高すぎる場合がある。本発明は、特定のアルゴリズムの精度への重大な影響なしに、この複雑度を、２分の１、３分の１、４分の１、・・・に、さらに減少させるための方法を開示する。発明者らは、投影のための近似法を取得し、そのような近似法が、標準の投影と同じ方法で、画像処理アルゴリズム内で使用されてもよいということを示す。
【０００５】
本発明の実施形態は、ブロックベースの投影、または単純にＢn,m投影と呼ばれる、特殊な画像投影を使用し、ここで、ｎ×ｍは基本ブロックのサイズである。ｎ×ｍピクセルからなる重ならないブロックが画像全体を分割し、各ブロックからの正確にｎ個のピクセルが、水平Ｂn,m投影のｎ個の値を更新するために使用され、そして、各ブロックからの正確にｍ個のピクセルが、垂直Ｂn,m投影のｍ個の値を更新するために使用される。
【０００６】
ブロックサイズが等しい場合（ｎ＝ｍ）、そのようなＢn,n投影を、Ｂn投影と呼ぶ。Ｂn投影の計算のためのアルゴリズムはより単純であり、一般的なＢn,m投影の場合のような追加の計算オーバヘッドを必要としない。
【０００７】
Ｂn,m投影の定義によれば、標準の投影(standard projection)（図１、図２）はＢ1投影とも呼ばれてもよく、これは、基本ブロックが１つのピクセルからなるということを示している。さらに、定義から、Ｂn,m投影は標準の投影と同じ長さを有し、したがって、元の画像解像度が維持される。これは、標準の投影が使用される、任意の画像処理アルゴリズムにおいて、Ｂn,m投影を使用することを可能にする。さらに、画像の前処理を追加せずには標準の投影を適用できない状況において、Ｂn,m投影のいくつかの特定のケースが使用されてもよい。そのような状況の１つの例は、ベイヤーパターン(Bayer pattern)によって表される画像の処理である。
【０００８】
本発明の態様は、添付の特許請求の範囲に記載される。
【０００９】
第１の態様では、本発明は、軸上に画像を投影することによって、画像の少なくとも１つの１次元表現を導き出すことを含む、画像を表現する方法を提供する。投影は、前記軸に垂直な画像のそれぞれのライン内で、選択されたピクセルの値を総和することを含む。本方法は、選択されるピクセルの数が、ライン内のピクセルの数よりも少ないことを特徴とする。
【００１０】
好ましくは、投影は、複数のそれぞれのライン内で、選択されたピクセルの値を総和することを含み、ここで、少なくとも１つのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少ない。
【００１１】
それぞれの軸に垂直な複数のそれぞれのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少なくてもよい。それぞれの軸に垂直なすべてのライン内の、選択されるピクセルの数は、それぞれのライン内のピクセルの数よりも少なくてもよい。
【００１２】
２つ以上の投影であって、２つ以上のそれぞれの軸上への、投影が存在してもよい。好ましくは、画像は２次元画像であり、そして、２つの各軸のそれぞれの上への投影が存在し、投影は上述したとおりのものである。好ましくは、２つ以上の軸は、水平軸と垂直軸のように、垂直である。
【００１３】
一実施形態では、選択されるピクセルは、垂直投影において、ｉ番目ごとの行からのピクセルを除外することによって、そして、水平投影において、ｊ番目ごとの列からのピクセルを除外することによって得られる。例えば、２番目ごとの行、または２番目ごとおよび３番目ごとの行内のピクセルが除外されてもよく、そして、３番目ごとの列、または２番目ごとおよび３番目ごとの列内のピクセルが除外されてもよい。
【００１４】
本明細書において、「選択される（選択された）ピクセル（selected pixel）」という用語は、選択されるピクセルの値が、投影についての総和に含まれるということを意味する。「除外される（除外された）ピクセル（omitted pixel）」は、対応するピクセル値が選択されない、すなわち、投影についての総和に含まれないということを意味する。ある投影（たとえば水平投影）について選択されるピクセルは、別の投影（たとえば垂直投影）については除外されてもよく、逆もまた同様である。一般に、ブロックの文脈における「選択される（選択された）ピクセル」とは、そのピクセルが少なくとも１つの投影についての総和に含まれることを意味し、ラインの文脈における「選択される（選択された）ピクセル」とは、そのピクセルが、そのラインに沿った投影における総和に含まれることを意味する。
【００１５】
大まかに述べると、提案される方法の実施形態は、以下のように働く。
１）画像走査を、いくつかのピクセルのスキッピングとともに実行する。次の節で説明する、以下の方法のうちの１つ、またはそれらの組み合わせが、走査のために使用されてもよい。
・行／列スキッピング（Row/column skipping）
・対角スキッピング（Diagonal skipping）
・ブロック置換（Block permutation）
２）アクセスされたピクセルのみを使用して、画像行または列を総和することによって、垂直および水平のＢn,m投影を計算し、そして、それらを、メモリバッファ内に記憶する。
【００１６】
提案される方法の、定性的および数値的比較により、以下の結論がもたらされる。
・次の節で説明する３つの方法は、投影を計算するために、等しい数の基本演算（加算）を必要とする。
・対角スキッピング方法によって必要とされる合計時間は、その他の方法によって必要とされる時間よりも少ない。
・３つの方法は、すべて、ｎ、ｍ＝２、３、４について、似た結果を与える。そのようなブロックサイズを使用して得られる投影は、ｎ＝ｍ＝１を使用して得られる標準の投影から大幅には逸脱しない。
・発明者らは、アルゴリズム速度の、ｎ倍という大幅な増加を得たが、取得される投影は、ノイズおよびアーチファクトによって、標準の投影とは異なる可能性がある。ただし、ｎ、ｍ＝２、３、４の場合は、ノイズおよびアーチファクトは非常に小さい。信号処理方法は、通常、そのような小さな因数に対して堅牢であり、したがって、発明者らのＢn,m投影は、標準の投影の代わりに使用可能である。
【００１７】
本発明の実施形態を、添付の図面を参照して説明する。
【図面の簡単な説明】
【００１８】
【図１】従来技術による、画像とその垂直および水平の投影とを示す。
【図２】従来技術による、垂直および水平の投影を示す図である。
【図３】本発明の第１の実施形態による投影を示す図である。
【図４】本発明の第１の実施形態による投影を示す代替の図である。
【図５】本発明の第２の実施形態による投影を示す図である。
【図６】本発明の第３の実施形態による、選択されたピクセルを有するブロックの図である。
【図７】本発明の第４の実施形態による投影を示す図である。
【図８】本発明の第５の実施形態による、画像内の選択されたピクチャを示す図である。
【図９】本発明の第６の実施形態による投影を示す図である。
【図１０】投影を使用した水平の動き推定を示す図である。
【図１１】動き推定の一形態を示すブロック図である。
【図１２】ベイヤーパターンの例である。
【図１３】動き推定の別の形態を示すブロック図である。
【図１４】動き推定の別の形態を示すブロック図である。
【図１５】ベイヤーパターンを使用した動き推定を示す画像である。
【図１６】動き検知（motion sensing）の一形態のブロック図である。
【００１９】
本発明の実施形態は、参照により本明細書に援用される、本出願人による同時係属出願である英国特許出願第０４２５４３０．６号明細書（ＧＢ０４２５４３０．６）を含む、画像を表現するための画像投影の計算に関する従来技術の発展である。
【００２０】
本発明の第１の実施形態による、Ｂn投影を計算するための手法が、図３に示されている。Ｂn投影は、行／列スキッピングによって計算される。図３に示す、印を付けられたピクセルのみが、対応する投影を計算するために使用される。
【００２１】
２回の画像走査が使用され、それぞれの走査で、対応する投影が計算される。Ｘ投影を計算するためには、ｎ番目ごとの行がスキップされる。同様に、Ｙ投影を計算するためには、ｎ番目ごとの列がスキップされる。
【００２２】
この方法（行／列スキッピング）は、ブロックベースの表現によって説明することも可能である。図４は、２×２ブロックを使用する例を示す。図４（ａ）は、ブロックサイズｎ＝２およびｎ＝３についての、実際の画像領域（図１の画像の小さな領域など）の例を示す。スキップされるピクセルは、白で示されている。図４（ｂ）は、ブロックサイズｎ＝２およびｎ＝３についての、計算方法の概略図を示す。印を付けられたピクセルのみが、対応する投影を計算するために使用される。黒のピクセルは、両方の投影のために使用される。灰色のピクセルは、Ｘ投影のために使用される。白のピクセルは、Ｙ投影のために使用される。
【００２３】
この例は、各ブロックのうちの３つのピクセルのみが使用されるため、アルゴリズムの計算複雑度は３ＷＨ／４に比例するということを示す。一般的なｎ×ｎブロックの場合については、計算複雑度Ｃ行/列は、（２ｎ−１）ＷＨ／ｎ2に比例する：
Ｃ行/列（ｎ）＝ｋ1（２ｎ−１）ＷＨ／ｎ2      （２）
上式で、定数ｋ1は、画像走査の追加のオーバヘッドに相当する。この方法によって必要とされる加算の回数は、１つのブロックからの２（ｎ−１）個のピクセルが投影に１回加算され、そのブロックからの１つのピクセルのみが２回使用されるという事実に基づいて取得される。したがって、加算の回数は次のようになる。
Ｎ行/列（ｎ）＝２ＷＨ／ｎ≦Ｎ標準      （３）
【００２４】
第２の実施形態では、Ｂn投影は、対角スキッピングによって計算される。
【００２５】
対角スキッピングの方法は、図５に示されている。図５（ａ）は、ｎ＝２およびｎ＝３についての、実際の画像（図１の画像の小さな領域など）の例を示す。スキップされるピクセルは、白で示されている。図５（ｂ）は、計算方法の概略図である。各基本ブロックの中の、（ドットによって印を付けられた）主対角線からのピクセルのみが使用される。
【００２６】
Ｂn投影を計算するために、いくつかの画像対角線がスキップされ、そして、等式（４）を満足するピクセル（ｘ，ｙ）のみが使用される。
（ｘ＋ｙ）  ｍｏｄ  ｎ＝０      （４）
【００２７】
これは、各基本ブロックの中で、主対角線(the main diagonal)からのピクセルのみが使用されるということを意味している。したがって、この方法の計算複雑度Ｃ対角は、ｎ（各ブロックの主対角線内のピクセルの数）にブロックの数ＷＨ／ｎ2を乗算した値に比例する：
Ｃ対角＝ｋ2ＷＨ／ｎ      （５）
【００２８】
定数ｋ2もまた、（４）の計算と画像走査のその他のオーバヘッドとを考慮に入れる。実験的なテストから、Ｃ対角＜Ｃ行/列ということになる。ブロックの対角線に属する各ピクセルは２回使用され、したがって、加算の回数は次のようになる：
Ｎ対角（ｎ）＝２ＷＨ／ｎ＝Ｎ行/列（ｎ）      （６）
【００２９】
第３の実施形態では、Ｂn投影は、ブロック置換によって計算される。図６は、行（または、同等に、列）置換によって生成された、投影において使用される選択されるピクセルを示す３×３ブロックの例を示す。
【００３０】
第３の実施形態のＢn投影計算の方法は、第２の実施形態の対角スキッピング方法の変更形態と考えることができる。この方法では、各基本ブロックは、行（または、同等に、列）置換によって予備的に変換される（図６）。ランダムな、またはランダムではない、置換の組が使用されてもよい。
【００３１】
図７は、ランダムな置換を用いてこの方法を使用する例を示す。ｎ＝２およびｎ＝３についての、基本ブロックのランダムな置換が示されている。図７（ａ）は、実際の画像（図１の画像の小さな領域など）の例を示す。スキップされるピクセルは、白で示されている。図７（ｂ）は、計算方法の概略図である。印を付けられたピクセルのみが、投影計算のために使用される。
【００３２】
計算複雑度Ｃ置換は、（５）に類似している：
Ｃ置換＝ｋ3ＷＨ／ｎ      （７）
ただし、ピクセルを走査するために、より複雑なアルゴリズムが使用される。走査アルゴリズムの効率的な実施のためには、（図６内で印を付けられた）ピクセル位置が、事前に計算され、そしてメモリテーブル内に記憶されるべきである。（７）における定数ｋ3は、走査アルゴリズムの複雑度を考慮に入れ、そして、一般に、Ｃ対角＜Ｃ置換である。この方法では、各ブロックからのｎ個のピクセルが（水平および垂直の両方の投影に寄与するために）２回使用され、したがって、加算の回数は次のようになる。
Ｎ置換（ｎ）＝２ＷＨ／ｎ＝Ｎ対角（ｎ）      （８）
【００３３】
上記の実施形態の変更形態は、複数の異なるブロックサイズの組み合わせを含む。
【００３４】
いくつかの画像処理方法では、いくつかの画像部分が、その他の画像部分よりも重要な場合がある。例えば、移動しているビデオカメラの場合、カメラの移動方向とは反対側の画像境界の付近のピクセルは、フレームごとに消失する。そのようなピクセルは、通常、解析から除外されるか、または、窓掛け処理（windowing）などの、複数の異なる技術によって、それらの影響が減少させられる。この場合、より概算的かつより高速な、画像投影計算の方法が使用されてもよい。例えば、画像の中央部では、Ｂ2投影が使用されてもよく、そして、境界の付近ではＢn投影（ｎ＞２）が使用されてもよい（図８を参照）。図８では、ブロック置換方法が、説明の目的のためにのみ使用されている。複数の異なる方法が、画像の複数の異なる領域内で使用されてもよい。この方法の追加のオーバヘッドは、各ピクセルが、投影内で総和される前に、そのブロックのサイズ（ｎに等しい）によって重み付けされなければならないということである。
【００３５】
一般的なＢn,m投影の場合が、１：１とは異なるアスペクト比を有する画像に対して使用されてもよい。例えば、６４０×４８０ピクセルの標準ＶＧＡ画像の場合、等しい数のピクセルが、垂直および水平の両方の投影に寄与することを確実にするために、アスペクト比４：３を有するブロックＢ4,3が使用されてもよい。そのような計算は、例えば、図９に示すような、対角スキッピング方法と列スキッピング方法との組み合わせによって達成されてもよい。図９において、黒のピクセルは両方の投影に寄与し、灰色のピクセルは水平投影のみに寄与する。
【００３６】
上述のように、異なるブロックサイズが画像の異なる領域のために使用されてもよい。同様に、投影計算（ピクセル選択）の異なる方法が、画像の異なる領域について、または、１つのブロック内で組み合わせて、使用されてもよい。複数の異なる方法が組み合わされてもよい。
【００３７】
投影計算の結果は、画像の表現、すなわち画像記述子と見なされてもよい。より具体的には、結果は、スパース積分画像記述子（sparse integral image descriptors）と見なされてもよい。
【００３８】
上述の、画像を表現する方法は、画像を解析するために画像投影を計算する、任意の画像処理システムにおいて適用可能である。本提案の画像投影の高速計算から利益を得るであろう３つの既知の画像処理方法への、本発明の実施形態の適用例について、以下に概説する。さらに、新規な適用例、特に、ベイヤーパターンからの動き推定と、それから得られる、自己動きセンサ（ego-motion sensor）とが、提案される。
【００３９】
第１の既知の技術は、画像のシフトはシフトされた投影をもたらすという事実に基づいた、主要な平行移動の動き推定（dominant translational motion estimation）である。図１０は、複数の水平投影の間における１Ｄシフトを推定することによる、３つの連続したビデオフレーム間の、水平の動き推定を示す。この話題に関する最先の研究のうちの１つは、Ｓ．Ａｌｌｉｎｅｙ、Ｃ．Ｍｏｒａｎｄｉ著、Ｄｉｇｉｔａｌ  ｉｍａｇｅ  ｒｅｇｉｓｔｒａｔｉｏｎ  ｕｓｉｎｇ  ｐｒｏｊｅｃｔｉｏｎｓ、ＩＥＥＥ  ＴＰＡＭＩ−８、Ｎｏ．２、１９８６年３月、２２２〜２２３頁において報告された。これは、本出願人による同時係属出願である英国特許出願第０４２５４３０．６号明細書（ＧＢ  ０４２５４３０．６）においてさらに改良された。この方法について、本発明者らは、標準の投影の代わりにＢn投影を使用することを提案する。
【００４０】
連続する複数の画像から計算される、２つ以上の画像投影が、主要な動き(dominant motion)の対応する成分を推定するために使用される（図１０）。図１０は、３つの連続したフレーム（フレームＫ−２、フレームＫ−１、およびフレームＫ）と、それらの対応する水平投影とを示す。正規化相互相関（normalized cross-correlation）（ＮＣＣ）、差分絶対値和（sum of absolute difference）（ＳＡＤ）または差分二乗和（sum of squared difference）（ＳＳＤ）、あるいは位相相関（phase correlation）（ＰＣ)などの、信号シフト推定の任意の従来技術による方法が、投影を比較してフレーム間のシフトを決定するために使用されてもよい。
【００４１】
第２の既知の技術は、画像記述子の抽出と、記述子のマッチングとの、２つの主なステップからなる、主要な動き推定方法である（図１１を参照）。図１１（そしてさらに、図１３、図１４、および図１６）は、動き推定または動き検知方法のステップを示す。図に示されている方法のステップは、装置の対応する構成要素またはモジュールによって実施されてもよい。
【００４２】
図１１に示すように、１つの画像記述子は、水平（Ｘ記述子）および垂直（Ｙ記述子）の、２つの独立した部分からなる。記述子抽出の主な着想は、処理の初期段階において、２Ｄ画像情報を１Ｄ信号に変換することである。本発明の実施形態を使用して、記述子は、Ｂn投影から導き出される。どのような種類のマッチング方法が使用されるかに応じて、記述子は以下であってもよい。
・Ｂn投影そのもの（信号領域内でのマッチング用）
・Ｂn投影のフーリエ変換（周波数領域内でのマッチング用）
【００４３】
記述子マッチングブロックは、現在のフレームの記述子と、直前のフレームについて計算された記述子とを使用する。提案される方法の一実施形態では、１Ｄシフトの推定のために、位相相関が使用される。この方法は、フーリエ変換とシフト定理（Shift Theorem）とに基づく。２つの信号（提案される方法ではいずれもＢn投影。例えば、ｓ1（ｘ）およびｓ2（ｘ））が、次のように平行移動ａだけ異なると仮定する。
ｓ（ｘ）＝ｓ’（ｘ＋ａ）
【００４４】
その場合、位相相関方法を次のように適用する。
【００４５】
【数１】
2009545794.tif 000003
【００４６】
上式で、Ｆ（ｓ）は、記述子抽出段階で事前に計算される、信号ｓのフーリエ変換であり、Ｆ*（ｓ）は、Ｆ（ｓ）の複素共役である。これにより、相対変位値におけるパルスが得られる。
Ｃ（ｘ）＝δ（ｘ−ａ）
【００４７】
変位ａは、結果として得られる信号Ｃ（ｘ）内の最も高いピークを見つけることによって決定される。
【００４８】
主要な動きを検出する、別の既知の方法は、ベイヤーパターンを使用する。シングルチップビデオカメラの大多数、およびほとんどすべてのデジタルスチルカメラは、いわゆるベイヤーパターンセンサを使用する。これらのセンサは、ＣＭＯＳまたはＣＣＤデバイスのいずれかである場合があるが、原理は同じである。米国特許第３９７１０６５号明細書のベイヤーパターンアプローチでは、カラーフィルタアレイの多くの可能な実施のうちの１つとしての、特殊なパターンを使用する。ベイヤーパターンの例を、図１２に示す。その他の実施は、ほとんどが、輝度チャネル（luminance channel）（緑）は色チャネル（chromatic channel）（赤および青）よりも高いレートでサンプリングされる必要があるという原理を使用する。輝度を表すものとしての緑の選択は、人間の目の輝度応答曲線が、緑の光の周波数（約５５０ｎｍ）に近いという事実によって説明することができる。
【００４９】
ベイヤーパターンからの画像を処理するためには、多くの方法が存在する。デジタルカメラ内の一般的な画像処理パイプラインは、主として、以下のステップに分けられる。空間デモザイキング（spatial demosaicing）と、それに続く、色およびガンマ補正（図１３−ビデオカメラまたはＤＳＣからの出力画像を使用した動き推定）。各ピクセルにおける色値を補間するために、ベイヤーは、単純な双一次補間を提案した。デジタルスチルカメラの開発の初期において、米国特許第４６４２６７８号明細書では、一定の色相に基づいた補間（constant hue-based interpolation）を使用することが提案されたが、その理由は、デモザイキングプロセスにおけるピクセルのアーチファクトは、色相の突然のジャンプの中で発生するからである。次に、米国特許４７７４５６５号明細書では、色フリンジ（colour fringes）を回避するために、色チャネルのメジアンに基づいた補間（median-based interpolation）を使用することが提案された。米国特許第５３８２９７６号明細書では、エッジベースの技術（edge-based technique）を使用することによる、フルカラー画像の適応的な補間が提案された。米国特許５３７３３２２号明細書では、米国特許第５，３８２，９７６号明細書のアプローチの拡張と見ることができる、承認されたエッジベースの方法が提案された。米国特許５６２９７３４号明細書では、両方のエッジベースの方法の概念が使用され、それらのアプローチの組み合わせおよび拡張が作成された。ベイヤーパターンデモザイキングの問題は、コンピュータビジョンコミュニティにおいて依然として盛んに話題となっている。例えば、Ｈｅｎｒｉｑｕｅ  Ｍａｌｖａｒ，Ｌｉ−ｗｅｉ  Ｈｅ，およびＲｏｓｓ  Ｃｕｔｌｅｒ著，Ｈｉｇｈ−ｑｕａｌｉｔｙ  ｌｉｎｅａｒ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｆｏｒ  ｄｅｍｏｓａｉｃｉｎｇ  ｏｆ  Ｂａｙｅｒ−ｐａｔｔｅｒｎｅｄ  ｃｏｌｏｒ  ｉｍａｇｅｓ，ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｓｐｅｅｃｈ，  Ａｃｏｕｓｔｉｃｓ，  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ、２００４年を参照されたい。
【００５０】
動き推定方法を含む、画像処理方法のほとんどは、最終的なカラー画像（ベイヤーパターン処理の結果）がピクセル補間によって得られることを要求する。直接的な方法（direct method）の設計は、（動きなどの）高レベルの情報を、画像センサデータから直接（すなわち、コストのかかるデモザイキングなしに）推定するのを可能にする。
【００５１】
主要な動き推定方法における垂直および水平の投影は、以下のうちの１つを使用して計算される。
・任意のＲＧＢ画像チャネル（好ましくは、最も大きいダイナミックレンジを有する、緑）
・（すべてのカラーチャネルから導き出される）画像輝度
・通常はカメラバッファから得られる、ＹＣｒＣｂカラースペースのＹチャネル
・元の、または処理されたカラーチャネルの、任意のその他の組み合わせ
【００５２】
したがって、投影に基づく方法を使用するためには、ベイヤーパターンを処理し、そして、それを標準のカラー画像に変換する必要がある。この処理の速度は、埋め込まれた動き推定アルゴリズムのために好適ではない場合がある。したがって、ベイヤーパターンの中間処理を回避するために、この方法のさらなる変更が必要とされる。
【００５３】
垂直および水平の投影は、画像ピクセルを総和することによって計算される。そして、この計算は、上記で示したように、正確に２ＷＨ回の加算を必要とする。画像の、ｍ分の１へのダウンサンプリングは、加算の回数をＷＨ／ｍ2に減少させるが、推定される動きベクトルの精度を比例して減少させ、そして、ダウンサンプリング処理自体のために、ＷＨに比例した回数の追加の演算を必要とする場合がある。
【００５４】
本発明のさらなる実施形態は、図１４および図１５に示すような、ベイヤーパターン（またはベイヤー様のパターン）に直接働きかける、高速動き推定アルゴリズムを提供する。
【００５５】
図１４は、初期段階における動き推定を有する、処理パイプラインのブロック図である。図１５は、ベイヤーパターン表現を使用した、画像の動き推定を示す。
【００５６】
本実施形態によれば、Ｂn投影が、対角スキッピングまたはブロック置換方法によって計算される。ｎ＝２を考慮する場合（図５、左列）、このパターンは、ベイヤーパターンの緑チャネル（図１２）、またはＣＭＹベイヤーパターンの黄チャネルに、正確に対応する。ブロック置換方法における置換の組を調節することによって、複数の異なるベイヤー様パターンと、疑似ランダムベイヤーパターンとが、モデル化されてもよい。提案される方法の有用な特性としては、以下が挙げられる。
・ＣＣＤまたはＣＭＯＳセンサからの、ベイヤーパターン（ＲＧＢおよびＣＭＹの両方）の直接使用、および、ピクセルの数に比例した複雑度を有する高価な色補間および補正アルゴリズムの回避。
・センサから画像を受信した直後の、最初期段階における動き推定。検出された動きに関する情報は、処理の他の段階において、例えば、デモザイキングの前の、ベイヤーパターンのノイズ除去のために、または、動きぼやけ(motion blur)の低減のために使用されてもよい。
対角スキッピング方法により計算されるＢn投影を使用することによって、ピクセル数の１／ｎに比例した複雑度を有する、より高速な変更が可能である。
・動きベクトルの元の解像度が維持される（および、サブピクセル補間を使用してさらに向上させられる）。
・ブロック置換方法により計算されるＢn投影を使用することによって、ベイヤーパターンの、複数の異なる構成への拡張が可能である。
【００５７】
セキュリティまたはその他のシステム用の、低コストの、自己動きビデオセンサを作成するために、前節で提示した方法が使用されてもよい。例えば、このセンサは、動きを開始した場合、信号を生成する。そのようなセンサは、（好ましくは、低コストの）ビデオカメラと、小さなＣＣＤまたはＣＭＯＳマトリクスとからなる。この場合、ベイヤーパターン処理のために通常使用される（図１６）、すべての色補正／補間手順は不要であり、そして、Ｂn投影を介した動き推定は、そのようなセンサを実施するための非常に効果的な方法である。図１７は、そのようなセンサの働きの抽象ブロック手法（abstract block-scheme）を示す。
【００５８】
画像投影は、全体照明の変化を含む、突然の照明の変化を検出するために使用されてもよい。画像投影の挙動は、照明の変化を反映する。例えば、連続したフレームからの投影の、負の差は、照明レベルの低下を知らせる。そのような特徴は、画像処理システムに、そのパラメータを新しい照明レベルのために適合させるように通知するために使用されてもよい。プロセス全体の速度を低下させないために、この補助的特徴は、高速で実行されることが重要である。Ｂn投影を使用することにより、この特徴の性能はｎ倍向上する。
【００５９】
比較的単純なシーン（暗い背景の中の明るい物体、またはその逆など）では、物体追跡の２Ｄ問題を、画像投影を使用して、１Ｄ追跡問題に縮小することが可能である。そのような場合、物体の位置は、投影の極大（または極小）によって決定される。そのような方法の、可能な適用領域は、航空機追跡、顕微鏡画像、およびレーダ画像である。物体が多数の場合、または時間が制限される場合、性能を向上させるために、標準の投影の代わりにＢn投影が使用されてもよい。
【００６０】
上記の各実施形態においては、一般に、２つの投影（水平および垂直）が計算および使用される。しかし、１つのみの投影が計算および／または使用されてもよい（例えば、水平の平行移動の動き推定の例におけるように）。
【００６１】
本明細書においては、「画像」および「フレーム」という用語は、画像単位（フィルタリング後のものを含む）を記述するために使用されるが、この用語は、画像、フィールド、ピクチャ、あるいは、画像やフレームなどのサブ単位または領域といった、その他の類似した用語にも適用される。ピクセル、およびピクセルのブロックまたはグループという用語は、適切な場合、区別なく使用されることがある。本明細書において、画像という用語は、文脈から明らかである場合を除き、画像全体、または画像の領域を意味する。同様に、画像の領域は、画像全体を意味する場合がある。画像は、フレームまたはフィールドを含み、そして、静止画像に、あるいは、フィルムまたはビデオなどの画像シーケンスの中の画像に、あるいは、関連する画像グループの中の画像に、関連する。
【００６２】
画像は、グレースケールであってもカラー画像であってもよく、あるいは別のタイプのマルチスペクトル画像（例えば、ＩＲ、ＵＶ、またはその他の電磁画像（electromagnetic image））であってもよく、あるいは音響画像（acoustic image）であってもよい。画像は、好ましくは２次元画像であるが、ｎ次元画像であってもよく、ここで、ｎは２よりも大きい。
【００６３】
本発明は、例えば、画像に対応する信号を処理する装置を使用して実施されてもよい。装置は、例えば、適切なソフトウェアおよび／またはハードウェアの変更が行われた、コンピュータシステムであってもよい。例えば、本発明は、プロセッサまたは制御装置などの、制御または処理手段と、メモリ、磁気記憶装置、ＣＤ、ＤＶＤなどの画像記憶手段を含む、データ記憶手段と、ディスプレイまたはモニタまたはプリンタなどの、データ出力手段と、キーボードなどのデータ入力手段と、スキャナなどの画像入力手段とを有するか、あるいは、そのような構成要素の任意の組み合わせを、追加の構成要素とともに有する、コンピュータまたは類似物を使用して実施されてもよい。本発明の態様は、ソフトウェアおよび／またはハードウェアの形態で、または特定用途向け装置の中で提供されてもよく、あるいは、チップなどの、特定用途向けモジュールが提供されてもよい。本発明の実施形態による装置内のシステムの構成要素は、例えばインターネットを介して、他の構成要素から離れた場所で提供されてもよい。
【図１】
2009545794.tif 000004
【図２】
2009545794.tif 000005
【図３】
2009545794.tif 000006
【図４】
2009545794.tif 000007
【図５】
2009545794.tif 000008
【図６】
2009545794.tif 000009
【図７】
2009545794.tif 000010
【図８】
2009545794.tif 000011
【図９】
2009545794.tif 000012
【図１０】
2009545794.tif 000013
【図１１】
2009545794.tif 000014
【図１２】
2009545794.tif 000015
【図１３】
2009545794.tif 000016
【図１４】
2009545794.tif 000017
【図１５】
2009545794.tif 000018
【図１６】
2009545794.tif 000019
【国際調査報告】
2009545794.tif 000020
2009545794.tif 000021
2009545794.tif 000022
2009545794.tif 000023
2009545794.tif 000024