(57)【特許請求の範囲】
【請求項１】
第１フレームを表わす第１イメージデータを受信する段階と、
前記第１フレームで複数の特徴点を識別する段階と、
第２フレームを表わす第２イメージデータを受信する段階と、
前記特徴点のそれぞれに相応する前記第１、第２フレーム間のモーションベクトルを得る段階と、
現在ベクトルＡとして前記モーションベクトルのうちの第１モーションベクトルを選択し、現在ベクトルＢとして前記モーションベクトルのうちの第２モーションベクトルを選択する段階と、
前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率及びアングル差に基づいて、前記現在ベクトルＡと前記現在ベクトルＢとを比較する段階と、
前記ベクトルサイズ比率のスレショルド値及びアングル差のスレショルド値を設定する段階と、
前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率が前記ベクトルサイズ比率のスレショルド値以内であり、且つ前記現在ベクトルＡと前記現在ベクトルＢとのアングル差が前記アングル差のスレショルド値以内である場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化する段階と、
前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率が前記ベクトルサイズ比率のスレショルド値を外れるか、又は前記現在ベクトルＡと前記現在ベクトルＢとのアングル差が前記アングル差のスレショルド値を外れる場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化しない段階と、
前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化しないと決定した場合、
新たなベクトルＢとして第３モーションベクトルを選択し、前記現在ベクトルＡと前記新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記新たなベクトルＢとのアングル差に基づいて、前記現在ベクトルＡと前記新たなベクトルＢとを比較する段階と、
新たなベクトルＡとして第２モーションベクトルを選択し、さらに新たなベクトルＢとして第４モーションベクトルを選択し、前記現在ベクトルＡと前記さらに新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記さらに新たなベクトルＢとのアングル差に基づいて、前記現在ベクトルＡと前記さらに新たなベクトルＢとを比較する段階を有することを特徴とするビデオデータ処理方法。
【請求項２】
前記ベクトルサイズ比率を比較する段階は、
（｜Ｂ｜／｜Ａ｜）２＝（（ｘｂ２＋ｙｂ２）／（ｘａ２＋ｙａ２））を計算することであり、
正規化されたベクトルａは、ベクトルＡをベクトルＡの絶対値｜Ａ｜によって除算したもの（ａ＝Ａ／｜Ａ｜）であり、正規化されたベクトルｂは、ベクトルＢをベクトルＡの絶対値｜Ａ｜によって除算したもの（ｂ＝Ｂ／｜Ａ｜）であり、ベクトルＡは、Ａ＝（ｘａ，ｙａ）であり、ベクトルＢは、Ｂ＝（ｘｂ，ｙｂ）であることを特徴とする請求項１に記載のビデオデータ処理方法。
【請求項３】
前記ベクトルサイズ比率のスレショルド値は、
（１−ｒ）２＜（｜Ｂ｜／｜Ａ｜）２＜（１＋ｒ）２であるｒｔｈであり、前記ｒは、０より大きく１より小さな所定の実数であることを特徴とする請求項１に記載のビデオデータ処理方法。
【請求項４】
前記ベクトルＡと前記ベクトルＢとの間の前記アングル差を比較する段階は、
正規化されたベクトル差のサイズの二乗｜ａ−ｂ｜２とアングル差のスレショルド値Ｍａｔｈ２とを比較する段階を含み、
前記｜ａ−ｂ｜２＝｛（ｘａ−ｘｂ）２＋（ｙａ−ｙｂ）２｝／（ｘａ２＋ｙａ２）であり、
ここで、正規化されたベクトルａは、ベクトルＡをベクトルＡの絶対値｜Ａ｜によって除算したもの（ａ＝Ａ／｜Ａ｜）であり、正規化されたベクトルｂは、ベクトルＢをベクトルＡの絶対値｜Ａ｜によって除算したもの（ｂ＝Ｂ／｜Ａ｜）であり、ベクトルＡは、Ａ＝（ｘａ，ｙａ）であり、ベクトルＢは、Ｂ＝（ｘｂ，ｙｂ）であることを特徴とする請求項１に記載のビデオデータ処理方法。
【請求項５】
前記アングル差のスレショルド値Ｍａｔｈ２は、所定のアングルスレショルド値θｔｈに基づいて計算され、
Ｍａｔｈ２＝（１＋｜ｂ｜２−２＊｜ｂ｜＊ｃｏｓθｔｈ）であり、前記｜ｂ｜＝ＳＱＲＴ｛（｜Ｂ｜／｜Ａ｜）２｝であり、
前記ベクトルＡと前記ベクトルＢとの比較は、一回のみの二乗根演算を使って行うことを特徴とする請求項４に記載のビデオデータ処理方法。
【請求項６】
前記アングル差のスレショルド値Ｍａｔｈ２＝０．５２であることを特徴とする請求項４に記載のビデオデータ処理方法。
【請求項７】
前記ベクトルＡと前記ベクトルＢとを比較する段階は、二乗根演算を使用せずに行うことを特徴とする請求項１に記載のビデオデータ処理方法。
【請求項８】
第１フレームで複数の特徴点を識別し、各特徴点で前記第１フレームと第２フレームとの間のモーションベクトルを得る特徴点回路と、
現在ベクトルＡ（ｘａ，ｙａ）として前記モーションベクトルのうちの１つを選択し、現在ベクトルＢ（ｘｂ，ｙｂ）として前記モーションベクトルのうちの他の１つを選択するペアリングアルゴリズムコントローラと、
前記ベクトルＡと前記ベクトルＢとのベクトルサイズ比率に基づいて前記ベクトルＡと前記ベクトルＢとを比較するサイズ比率比較器と、
前記ベクトルＡと前記ベクトルＢとのベクトルアングル差に基づいて前記ベクトルＡと前記ベクトルＢとを比較するベクトルアングル比較器とを有し、
前記ペアリングアルゴリズムコントローラは、前記サイズ比率比較器での前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率がベクトルサイズ比率のスレショルド値以内であり、且つ前記ベクトルアングル比較器での前記現在ベクトルＡと前記現在ベクトルＢとのベクトルアングル差がベクトルアングル差のスレショルド値以内である場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化し、
前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率が前記ベクトルサイズ比率のスレショルド値を外れるか、又は前記現在ベクトルＡと前記現在ベクトルＢとのベクトルアングル差が前記ベクトルアングル差のスレショルド値を外れる場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化せず、
前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化しない場合、
前記ペアリングアルゴリズムコントローラは、新たなベクトルＢとして第３モーションベクトルを選択し、
前記現在ベクトルＡと前記新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記新たなベクトルＢとのベクトルアングル差に基づいて、前記サイズ比率比較器及び前記ベクトルアングル比較器にて前記現在ベクトルＡと前記新たなベクトルＢとを比較し、
前記ペアリングアルゴリズムコントローラは、新たなベクトルＡとして第２モーションベクトルを選択し、さらに新たなベクトルＢとして第４モーションベクトルを選択し、
前記現在ベクトルＡと前記さらに新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルアングル差に基づいて、前記サイズ比率比較器及び前記ベクトルアングル比較器にて前記現在ベクトルＡと前記さらに新たなベクトルＢとを比較することを特徴とするビデオ処理回路。
（正規化されたベクトルａは、ベクトルＡをベクトルＡの絶対値｜Ａ｜によって除算したもの（ａ＝Ａ／｜Ａ｜）であり、正規化されたベクトルｂは、ベクトルＢをベクトルＡの絶対値｜Ａ｜によって除算したもの（ｂ＝Ｂ／｜Ａ｜）であり、ベクトルＡは、Ａ＝（ｘａ，ｙａ）であり、ベクトルＢは、Ｂ＝（ｘｂ，ｙｂ）である。）
【請求項９】
前記サイズ比率比較器は、前記ベクトルサイズ比率の二乗値（｜Ｂ｜／｜Ａ｜）２と前記ベクトルサイズ比率のスレショルド値とを比較し、
（｜Ｂ｜／｜Ａ｜）２＝（（ｘｂ２＋ｙｂ２）／（ｘａ２＋ｙａ２））であることを特徴とする請求項８に記載のビデオ処理回路。
【請求項１０】
前記ベクトルサイズ比率のスレショルド値は、（｜Ａ｜／｜Ｂ｜）２であることを特徴とする請求項８に記載のビデオ処理回路。
【請求項１１】
前記ベクトルサイズ比率スレショルド値は、
（１−ｒ）２＜（｜Ｂ｜／｜Ａ｜）２＜（１＋ｒ）２であるｒｔｈであり、前記ｒは、０より大きく１より小さな所定の実数であることを特徴とする請求項８に記載のビデオ処理回路。
【請求項１２】
前記ベクトルアングル比較器は、前記正規化されたベクトル差のサイズの二乗｜ａ−ｂ｜２とベクトルアングル差のスレショルド値Ｍａｔｈ２とを比較し、
｜ａ−ｂ｜２＝｛（ｘａ−ｘｂ）２＋（ｙａ−ｙｂ）２｝／（ｘａ２＋ｙａ２））であることを特徴とする請求項８に記載のビデオ処理回路。
【請求項１３】
前記ベクトルアングル差のスレショルド値Ｍａｔｈ２は、所定のアングルスレショルド値θｔｈに基づいて計算され、
Ｍａｔｈ２＝（１＋｜ｂ｜２−２＊｜ｂ｜＊ｃｏｓ  θｔｈ）であり、
｜ｂ｜＝ＳＱＲＴ｛（｜Ｂ｜／｜Ａ｜）２｝であることを特徴とする請求項１２に記載のビデオ処理回路。
【請求項１４】
前記ベクトルアングル差のスレショルド値Ｍａｔｈ２＝０．５２であることを特徴とする請求項１２に記載のビデオ処理回路。
【請求項１５】
第１モーション特性を有する特徴点の第１グループと第２モーション特性を有する特徴点の第２グループとを保存する特徴点グループメモリを更に含むことを特徴とする請求項８に記載のビデオ処理回路。
【請求項１６】
メモリから取り出したデータをチップの外部回路に伝送するための特徴点グループメモリに連結された入出力ピンを更に含むことを特徴とする請求項８に記載のビデオ処理回路。
【請求項１７】
ビデオデータの第１フレームで複数の特徴点を識別し、各特徴点で前記第１フレームと第２フレームとの間のモーションベクトルを推定する段階と、
ベクトルサイズ比率及びアングル差に基づいてモーションベクトルグループに前記モーションベクトルをグループ化する段階と、
前記第１フレームの場面内の静止した物体の動きを表わすモーションベクトルを含むグループを選択する段階とを有し、
前記モーションベクトルをグループ化する段階は、前記モーションベクトルの内のベクトルＡとベクトルＢとのベクトルサイズ比率及び前記ベクトルＡと前記ベクトルＢとのアングル差に基づいて前記ベクトルＡと前記ベクトルＢとを比較する段階を含み、
前記第１フレーム内の静止した物体を表わすモーションベクトルグループを選択する段階は、前記第１フレームで動く物体のローカルな動きを表わす少なくとも１つのモーションベクトルグループを拒絶する段階を含み、
サブサンプルされた輝度データを使用して、前記第１フレームの一部から分割された複数のタイルのそれぞれのモーションベクトルを推定し、最も小さな絶対差の和（ｌｏｗｅｓｔ  ＳＡＤ）を有するタイルモーションベクトルの候補を選択する段階と、
ベクトルサイズ比率及びアングル差に基づいて前記タイルモーションベクトルを前記モーションベクトルグループにグループ化する段階とをさらに有することを特徴とするビデオデータ処理方法。
【請求項１８】
イメージをキャプチャーし、複数のイメージをイメージデータの第１フレーム及び第２フレームに変換するイメージキャプチャー回路と、
ビデオ処理回路チップと、を備え、
前記ビデオ処理回路チップは、
前記第１フレームで複数の特徴点を識別し、各特徴点で前記第１フレームと第２フレームとの間のモーションベクトルを得る特徴点回路と、
現在ベクトルＡ（ｘａ，ｙａ）として前記モーションベクトルのうちの１つを選択し、現在ベクトルＢ（ｘｂ，ｙｂ）として前記モーションベクトルのうちの他の１つを選択するペアリングアルゴリズムコントローラと、
前記ベクトルＡと前記ベクトルＢとのベクトルサイズ比率に基づいて前記ベクトルＡと前記ベクトルＢとを比較するサイズ比率比較器と、
前記ベクトルＡと前記ベクトルＢとのベクトルアングル差に基づいて前記ベクトルＡと前記ベクトルＢとを比較するベクトルアングル比較器とを有し、
前記ペアリングアルゴリズムコントローラは、前記サイズ比率比較器での前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率がベクトルサイズ比率のスレショルド値以内であり、且つ前記ベクトルアングル比較器での前記現在ベクトルＡと前記現在ベクトルＢとのベクトルアングル差がベクトルアングル差のスレショルド値以内である場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化し、
前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率が前記ベクトルサイズ比率のスレショルド値を外れるか、又は前記現在ベクトルＡと前記現在ベクトルＢとのベクトルアングル差が前記ベクトルアングル差のスレショルド値を外れる場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化せず、
前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化しない場合、
前記ペアリングアルゴリズムコントローラは、新たなベクトルＢとして第３モーションベクトルを選択し、
前記現在ベクトルＡと前記新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記新たなベクトルＢとのベクトルアングル差に基づいて、前記サイズ比率比較器及び前記ベクトルアングル比較器にて前記現在ベクトルＡと前記新たなベクトルＢとを比較し、
前記ペアリングアルゴリズムコントローラは、新たなベクトルＡとして第２モーションベクトルを選択し、さらに新たなベクトルＢとして第４モーションベクトルを選択し、
前記現在ベクトルＡと前記さらに新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルアングル差に基づいて、前記サイズ比率比較器及び前記ベクトルアングル比較器にて前記現在ベクトルＡと前記さらに新たなベクトルＢとを比較することを特徴とするカメラ。
（正規化されたベクトルａは、ベクトルＡをベクトルＡの絶対値｜Ａ｜によって除算したもの（ａ＝Ａ／｜Ａ｜）であり、正規化されたベクトルｂは、ベクトルＢをベクトルＡの絶対値｜Ａ｜によって除算したもの（ｂ＝Ｂ／｜Ａ｜）であり、ベクトルＡは、Ａ＝（ｘａ，ｙａ）であり、ベクトルＢは、Ｂ＝（ｘｂ，ｙｂ）である。）
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルイメージ安定化（Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｓｔａｂｉｌｉｚａｔｉｏｎ：ＤＩＳ）装置及び方法に係り、より詳細には、デジタルイメージ安定化のために特徴点を感知、選択、及びグループ化する装置及方法に関する。
【背景技術】
【０００２】
デジタルカメラ、デジタルビデオカメラ、及びハンドヘルドデバイスは、カメラが、人の手によって作動される間に、写真や映像を撮影するために使われる。従って、ビデオカメラは、写真や映像を撮影する間に、手ぶれや、ジッタ（ｊｉｔｔｅｒ）が発生しうる。ジッタは、水平的要素、垂直的要素、回転的要素を含みうる。回転は、イメージキャプチャー回路の焦点面に対して垂直軸に、イメージキャプチャー回路の焦点面に対して水平軸に、又は水平軸と垂直軸とに対する傾斜軸になされうる。ジッタは、ハンドキャプチャードビデオを見る人の注意力を散漫にし（ｄｉｓｔｒａｃｔｉｎｇ）又は方向感を失わせる（ｄｉｓｏｒｉｅｎｔｉｎｇ）。従って、デジタル的にカメラ軌跡（例えば、連続したフレームで感知されるジッタ）を予測し、同じ場面（ｓｃｅｎｅ）の映像フレームのシーケンスからジッタをフィルタリングするデジタル回路を用いることが要求される。連続したフレーム間のカメラ軌跡を予測し、映像フレームの配列からカメラ軌跡によって引き起こされたジッタをフィルタリングするために使用される回路は、ビデオカメラ自体に含まれ、撮影された映像フレームの保存の前に（ビデオカメラがリアルタイムＭＰＥＧエンコーダを含む場合、ＭＰＥＧエンコーディング以前に）、リアルタイムでジッタを除くように作動する。一方、連続した映像フレーム間でカメラ軌跡を予測し、映像フレームの保存された配列からジッタをフィルタリングするために使用される回路は、デジタルイメージ安定化方法を具現したソフトウェアによって制御される一般的なマイクロコンピュータやデジタルイメージ安定化方法を行うために最適化されたＡＳＩＣに具現されたＭＰＥＧ映像エンコーダのような専用ハードウェアであり得る。
【０００３】
映像は、キャプチャーされた映像内にビデオカメラを安定に固定又は移動させる場合、主に滑らかな動作（並進（平行移動）、回転）が含まれる。しかし、不安定なビデオカメラは、ビデオイメージを通じて非常に頻繁なジッタ（並進的に、及び／又は回転的に）映像を発生させる。
【０００４】
物理的イメージ装置からキャプチャーされたデジタルイメージシーケンスは、度々所望していないに非常に頻繁なジッタ（ｊｉｔｔｅｒｉｎｇ）モーションを表示する。イメージシーケンスに表われたジッタ動作の全体は、キャプチャーされたシーケンスの物体（ｏｂｊｅｃｔ）に対してイメージキャプチャー装置の物理的特性に依存する。場面の深さ（ｄｅｐｔｈ）、及びマウントの重さ、慣性、均衡による映像機のマウントの不安定は、所望しない全体的なジッタを作り出す。
【０００５】
デジタル安定化システムは、先ず所望しない（意図しない）動作（ｍｏｔｉｏｎ）を推定した後、イメージシーケンスに修正を加える。安定化された映像の視覚的効果は、カメラ軌跡推定の品質に大きく依存する。デジタルイメージ安定化アルゴリズムは、２つの連続したフレーム間のジッタを推定するために、適切に追跡された（ｗｅｌｌ−ｔｒａｃｋｅｄ）特徴点を使用する。ＤＩＳは、不安定なビデオカメラによって引き起こされた意図していない急な動き（ｊｅｒｋｙ  ｍｏｔｉｏｎ）を含む他の不安定な映像から、空間的に安定した映像を産出するハードウェア及び／又はソフトウェア的な方法によって具現されうる。一般的なＤＩＳ技術で、カメラの動きは、場面の様々なポイントでモーションベクトルを分析することで感知される。しかし、モーションベクトルは、カメラの動きと同様に物体の動きによって生じる。
【０００６】
このポイントが経時的に（ｔｉｍｅ  ｗｉｓｅ）隣接したフレームで感知可能な特徴点としてどのくらい適するかを表わすフレームの各ピクセルのために数字的なスコア（ｎｕｍｅｒｉｃａｌ  ｓｃｏｒｅ）を提供する関数がある。関数の一例として、ハリスコーナー感知器（Ｈａｒｒｉｓ  Ｃｏｒｎｅｒ  Ｄｅｔｅｃｔｏｒ）がある。しかし、特徴点のサイズは、イメージの他の領域毎に類型的に非常に異なる。ＤＩＳ方法は、各ピクセルの数字的なスコアを比較した全体スレショルド値によるが、必ずしも特徴点の最適分布で発生するものではない。これにより、低いコントラストを有する領域（例えば、雲が殆どない青空又は特徴点のない）は、非常に小さい特徴点を有する。一方、非常に多くの構造物を有する領域は、特徴点が互いに非常に近いことがある。特徴点の誤った分布は、非常に近接した特徴点のモーションベクトルを計算するに当たって、計算上の負担を増加させ、正確なモーションベクトルを算出することができない。
【０００７】
ＤＩＳ方法の具現において、回路の電力消耗及びＤＩＳの遂行に必要な時間消耗を減らして、計算の負担を最小化することが要求される。また、カメラ軌跡を感知及び測定し、ジッタを正確に特性化することが要求される。その結果、ジッタが正確に補償されて保存／表示される映像からジッタが正確に除去されうる。
【０００８】
数学的処理で、アフィン幾何学は、アフィン変換によって変わらずに保持される幾何学的な特性の研究である（例えば、非単数線形変換及び並進（ｎｏｎ−ｓｉｎｇｕｌａｒ  ｌｉｎｅａｒ  ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ  ａｎｄ  ｔｒａｎｓｌａｔｉｏｎｓ））。アフィン行列と呼ばれる数値係数によって定義される方程式の数学システムは、連続した各対のフレーム間又はその一部（例えば、フレーム内の物体の運動）で感知される横（又は上下）方向、回転、及びスケーラー（ｓｃａｌａｒ）（例えば、ズームイン又はズームアウト）の動きで特性化されて発展した。
【０００９】
これにより、ジッタは、場面で主要変形（Ｐｒｉｎｃｉｐａｌ  Ｔｒａｎｓｆｏｒｍ）又は全体変形（Ｇｌｏｂａｌ  Ｔｒａｎｓｆｏｒｍ）と呼ばれるあるアクチュアリーステーショナリー物体（ａｃｔｕａｌｌｙ  ｓｔａｔｉｏｎａｒｙ  ｏｂｊｅｃｔ）（例えば、岩、テーブル、駐車した車、山、及び太陽）と関連して、第１アフィン変形行列によって特性化されうる。一方、フレーム内の動く物体（例えば、鳥、人、球、動く車）は、追加的なアフィンマトリックスによって特性化されうる。
【００１０】
ユーザの手ぶれ（ｈａｎｄ  ｊｉｔｔｅｒ）によって生じるカメラの動きを表わす主要変形（ｐｒｉｎｃｉｐｌｅ  ｉｎｔｅｒ−ｆｒａｍｅ  ｔｒａｎｓｆｏｒｍ）は、時間ｔでキャプチャーされた各フレームでアクチュアリーステーショナリー物体と関連した１つ又はそれ以上の関心のあるポイント（これを特徴点と称する）を感知し、経時的に隣接したフレーム（ｔ＋１）で同じ特徴点を探し、特徴点のそれぞれのモーションベクトルを計算することで計算されうる。特定物体と関連する複数のモーションベクトルは、物体のアフィン変形（即ち、次のアフィン方程式によって動きを感知する）の計算に使用される。
ｘ′＝ｓｘ＊ｘ＋ｒｙ＊ｙ＋ｔｘ
ｙ′＝ｒｘ＊ｘ＋ｓｙ＊ｙ＋ｔｙ
【００１１】
連続したフレーム間の特徴点のモーションベクトルは、映像圧縮分野で採用される多様な検索方法を使用して計算されうる。そのような検索方法は、マクロブロック（ｍａｃｒｏｂｌｏｃｋ）の数学的比較、即ち経時的に近い２つのフレーム間の絶対差の和（ｓｕｍ  ｏｆ  ａｂｓｏｌｕｔｅ  ｄｉｆｆｅｒｅｎｃｅｓ：ＳＡＤ）、絶対差の平均（ｍｅａｎ  ａｂｓｏｌｕｔｅ  ｄｉｆｆｅｒｅｎｃｅ：ＭＡＤ）、又はエラー二乗平均（ｍｅａｎ  ｓｑｕａｒｅ  ｅｒｒｏｒ：ＭＳＥ）による（例えば、現在フレームで特徴点を含む８×８ピクセルマクロブロックと、基準フレーム（ｔ＋１）の検索領域で特徴点位置が略中心となる複数の８×８ピクセルマクロブロックと、を比較することによって、基準フレーム（ｔ＋１）で特徴点の位置を検索する）。経時的に隣接したフレーム間（ｔ及びｔ＋１）の特徴点に対して中心部にあるマクロブロック移動の測定値と方向とを特徴点のモーションベクトルと言う。多様に選択された範囲でブロックマッチングアルゴリズム（Ｂｌｏｃｋ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍｓ：ＢＭＡ）を使用する関連技術のモーションベクトル推定方法は、アメリカ特許ＵＳ  Ｐａｔ．６８９５３６１、Ｙａｎｇ及びアメリカ特許ＵＳ  ７６８０１８６、Ｌｅｅを参照することができる。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明の技術的な課題は、デジタルイメージ安定化を正確にすると同時に、カメラの動き又はグローバルモーションのために起こる動きの特徴点を識別して、その特徴点のモーションベクトルを得る非常に効率的なプロセスを提供することにある。
【課題を解決するための手段】
【００１３】
ＤＩＳアルゴリズムに優れた特徴点は、適切なモーション推定アルゴリズムが適用される場合、曖昧ではないモーションベクトルから算出されるポイントである。イメージで特徴点を識別するために、イメージフレームのピクセルに適用されるハリスコーナー感知器（Ｈａｒｒｉｓ  Ｃｏｒｎｅｒ  Ｄｅｔｅｃｔｏｒ）は、各ピクセルが特徴点としてどのくらい適するかを推定する。イメージの他の領域は、識別された特徴点候補の他の密度を有する。ラスタースキャンオーダー選択（ｒａｓｔｅｒ  ｓｃａｎ  ｏｒｄｅｒ  ｓｅｌｅｃｔｉｏｎ）及び分類（ｓｏｒｔｉｎｇ）の開示された方法は、イメージフレームの小さな領域、即ちタイルに基づいた最終特徴点分布を提供する。最終特徴点分布で、特徴点の最大数は、タイルのイメージデータ輝度の分散σ２によって線形的に増加する。
【００１４】
各イメージフレームは、小さな数（ｊ×ｋ）のタイルに分けられる。タイルの数ｊ×ｋは、ＳＤビデオで４×４からＨＤビデオで６×６、又は更に大きな数の範囲を有しうる。上記範囲内の他の数（４…８）×（４…８）も可能であり有用である。タイルサイズは、少なくとも１タイルで殆どを独立してカバーして動く十分に大きな物体のようなものを選ぶことができる。その結果、物体の動きは、ＤＩＳ目的でキャプチャーされうるが、小さな物体の動きは無視される。
【００１５】
より関心のあるイメージデータを有するタイル及びより多い特徴点のための必要性を有するタイルは、より大きな分散σ２を有すると予想される。特徴点分類アルゴリズムは、特徴点の間のプログラム可能な最小距離を探すが、これは最小限のハードウェアメモリを必要とする。
【００１６】
階層的動き推定アルゴリズムは、フレームからフレームまでの特徴点の動きの推定に使用される。この際、その後の検索レベルのためのプログラム可能な動き範囲は、意図的に小さく、ローカルな動き以上の大きな物体又はグローバルな動きを好む。その結果、動作に要求される数は最小化されるが、一方、その結果値はＤＩＳ応用に非常に適している。
【００１７】
選択された（例えば、分類アルゴリズムによって）特徴点のそれぞれに対して、そのモーションベクトルは、使用される開始ベクトルの小さな範囲内のブロックマッチングによって決定される。開始ベクトルは、現在特徴点を含むタイルとその周辺タイル（例えば、上、下、左、右の）のタイルモーションベクトルである。タイルモーション推定は、特徴点のモーションベクトルを得る最初の段階である。タイルモーション推定は、入力イメージの中心部分をカバーする（例えば、特徴点分類アルゴリズムに使われる同じタイル）重ならないタイルに基づいてなされる。タイルのそれぞれのタイルモーション推定のために、フルブロックマッチング探索（ｆｕｌｌ  ｂｌｏｃｋ  ｍａｔｃｈｉｎｇ  ｓｅａｒｃｈ）がダウンサンプルされたイメージで行われる。
【００１８】
現在フレームは、標準画質ビデオ（ｓｔａｎｄａｒｄ  ｄｅｆｉｎｉｔｉｏｎ  ｖｉｄｅｏ：ＳＤ  ｖｉｄｅｏ）の場合、４から８に、高画質ビデオ（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｖｉｄｅｏ：ＨＤ  ｖｉｄｅｏ）で８から１６に、第２サブサンプリングファクターｆｓ２によってサブサンプリングされる。サブサンプリングされたドメインで、フルサーチブロックマッチングがあらゆるタイルでなされ、タイルベクトルは、その後の使用のために保存される（例えば、特徴点のモーションベクトルを算出するための開始ベクトルとして）。１つのモーションベクトルは、あらゆるタイルで推定され、最も低い解像度でフルサーチができ、第２サブサンプリングファクターによりサブサンプリングされうる。最も小さなＳＡＤで算出されるモーションベクトル候補は、各タイルに割り当てられる。一実施形態によると、ボーダータイル（ｂｏｒｄｅｒ  ｔｉｌｅｓ）のために、可能な検索領域で検索領域の（部分的に）外部として検索を制限することができ、基準ブロックのために、モーションベクトルが全く生成されないこともある。解像度と関連して、タイルモーション検索は、半分−画素（ｈａｌｆ−ｐｅｌ）の正確なベクトルで発生することがある。検索領域は、単純なバイリニア補間（ｓｉｍｐｌｅ  ｂｉｌｉｎｅａｒ  ｉｎｔｅｒｐｏｌａｔｉｏｎ）によってアップサンプル（ｕｐｓａｍｐｌｅｄ）されうる。これは、ＶＬＳＩの具現でロジック領域及びメモリに保存する非常に小さなローカルメモリにのみ使われる。
【００１９】
本発明の技術的な課題は、モーションベクトル間のサイズ比率及びアングル差に基づいて、特徴点のペアをグループ化する特徴点モーションベクトルグループ化プロセスを含むデジタルイメージ安定化方法を提供することにある。本発明の一態様によるビデオデータ処理方法は、第１フレームを表わす第１イメージデータを受信する段階と、前記第１フレームで複数の特徴点を識別する段階と、第２フレームを表わす第２イメージデータを受信する段階と、前記特徴点のそれぞれに相応する前記第１、第２フレーム間のモーションベクトルを得る段階と、現在ベクトルＡとして前記モーションベクトルのうちの第１モーションベクトルを選択し、現在ベクトルＢとして前記モーションベクトルのうちの第２モーションベクトルを選択する段階と、前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率及びアングル差に基づいて、前記現在ベクトルＡと前記現在ベクトルＢとを比較する段階と、前記ベクトルサイズ比率のスレショルド値及びアングル差のスレショルド値を設定する段階と、前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率が前記ベクトルサイズ比率のスレショルド値以内であり、且つ前記現在ベクトルＡと前記現在ベクトルＢとのアングル差が前記アングル差のスレショルド値以内である場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化する段階と、前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率が前記ベクトルサイズ比率のスレショルド値を外れるか、又は前記現在ベクトルＡと前記現在ベクトルＢとのアングル差が前記アングル差のスレショルド値を外れる場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化しない段階と、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化しないと決定した場合、新たなベクトルＢとして第３モーションベクトルを選択し、前記現在ベクトルＡと前記新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記新たなベクトルＢとのアングル差に基づいて、前記現在ベクトルＡと前記新たなベクトルＢとを比較する段階と、新たなベクトルＡとして第２モーションベクトルを選択し、さらに新たなベクトルＢとして第４モーションベクトルを選択し、前記現在ベクトルＡと前記さらに新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記さらに新たなベクトルＢとのアングル差に基づいて、前記現在ベクトルＡと前記さらに新たなベクトルＢとを比較する段階を有することを特徴とする。
【００２１】
本発明の一態様によるビデオ処理回路は、第１フレームで複数の特徴点を識別し、各特徴点で前記第１フレームと第２フレームとの間のモーションベクトルを得る特徴点回路と、現在ベクトルＡ（ｘａ，ｙａ）として前記モーションベクトルのうちの１つを選択し、現在ベクトルＢ（ｘｂ，ｙｂ）として前記モーションベクトルのうちの他の１つを選択するペアリングアルゴリズムコントローラと、前記ベクトルＡと前記ベクトルＢとのベクトルサイズ比率に基づいて前記ベクトルＡと前記ベクトルＢとを比較するサイズ比率比較器と、前記ベクトルＡと前記ベクトルＢとのベクトルアングル差に基づいて前記ベクトルＡと前記ベクトルＢとを比較するベクトルアングル比較器とを有し、前記ペアリングアルゴリズムコントローラは、前記サイズ比率比較器での前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率がベクトルサイズ比率のスレショルド値以内であり、且つ前記ベクトルアングル比較器での前記現在ベクトルＡと前記現在ベクトルＢとのベクトルアングル差がベクトルアングル差のスレショルド値以内である場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化し、前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率が前記ベクトルサイズ比率のスレショルド値を外れるか、又は前記現在ベクトルＡと前記現在ベクトルＢとのベクトルアングル差が前記ベクトルアングル差のスレショルド値を外れる場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化せず、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化しない場合、前記ペアリングアルゴリズムコントローラは、新たなベクトルＢとして第３モーションベクトルを選択し、前記現在ベクトルＡと前記新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記新たなベクトルＢとのベクトルアングル差に基づいて、前記サイズ比率比較器及び前記ベクトルアングル比較器にて前記現在ベクトルＡと前記新たなベクトルＢとを比較し、前記ペアリングアルゴリズムコントローラは、新たなベクトルＡとして第２モーションベクトルを選択し、さらに新たなベクトルＢとして第４モーションベクトルを選択し、前記現在ベクトルＡと前記さらに新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルアングル差に基づいて、前記サイズ比率比較器及び前記ベクトルアングル比較器にて前記現在ベクトルＡと前記さらに新たなベクトルＢとを比較することを特徴とする。
（正規化されたベクトルａは、ベクトルＡをベクトルＡの絶対値｜Ａ｜によって除算したもの（ａ＝Ａ／｜Ａ｜）であり、正規化されたベクトルｂは、ベクトルＢをベクトルＡの絶対値｜Ａ｜によって除算したもの（ｂ＝Ｂ／｜Ａ｜）であり、ベクトルＡは、Ａ＝（ｘａ，ｙａ）であり、ベクトルＢは、Ｂ＝（ｘｂ，ｙｂ）である。）
【００２２】
本発明の他の態様によるビデオデータ処理方法は、ビデオデータの第１フレームで複数の特徴点を識別し、各特徴点で前記第１フレームと第２フレームとの間のモーションベクトルを推定する段階と、ベクトルサイズ比率及びアングル差に基づいてモーションベクトルグループに前記モーションベクトルをグループ化する段階と、前記第１フレームの場面内の静止した物体の動きを表わすモーションベクトルを含むグループを選択する段階とを有し、前記モーションベクトルをグループ化する段階は、前記モーションベクトルの内のベクトルＡとベクトルＢとのベクトルサイズ比率及び前記ベクトルＡと前記ベクトルＢとのアングル差に基づいて前記ベクトルＡと前記ベクトルＢとを比較する段階を含み、前記第１フレーム内の静止した物体を表わすモーションベクトルグループを選択する段階は、前記第１フレームで動く物体のローカルな動きを表わす少なくとも１つのモーションベクトルグループを拒絶する段階を含み、サブサンプルされた輝度データを使用して、前記第１フレームの一部から分割された複数のタイルのそれぞれのモーションベクトルを推定し、最も小さな絶対差の和（ｌｏｗｅｓｔ  ＳＡＤ）を有するタイルモーションベクトルの候補を選択する段階と、ベクトルサイズ比率及びアングル差に基づいて前記タイルモーションベクトルを前記モーションベクトルグループにグループ化する段階とをさらに有することを特徴とする。
【００２３】
本発明の一態様によるカメラは、イメージをキャプチャーし、複数のイメージをイメージデータの第１フレーム及び第２フレームに変換するイメージキャプチャー回路と、ビデオ処理回路チップと、を備え、前記ビデオ処理回路チップは、前記第１フレームで複数の特徴点を識別し、各特徴点で前記第１フレームと第２フレームとの間のモーションベクトルを得る特徴点回路と、現在ベクトルＡ（ｘａ，ｙａ）として前記モーションベクトルのうちの１つを選択し、現在ベクトルＢ（ｘｂ，ｙｂ）として前記モーションベクトルのうちの他の１つを選択するペアリングアルゴリズムコントローラと、前記ベクトルＡと前記ベクトルＢとのベクトルサイズ比率に基づいて前記ベクトルＡと前記ベクトルＢとを比較するサイズ比率比較器と、前記ベクトルＡと前記ベクトルＢとのベクトルアングル差に基づいて前記ベクトルＡと前記ベクトルＢとを比較するベクトルアングル比較器とを有し、前記ペアリングアルゴリズムコントローラは、前記サイズ比率比較器での前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率がベクトルサイズ比率のスレショルド値以内であり、且つ前記ベクトルアングル比較器での前記現在ベクトルＡと前記現在ベクトルＢとのベクトルアングル差がベクトルアングル差のスレショルド値以内である場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化し、前記現在ベクトルＡと前記現在ベクトルＢとのベクトルサイズ比率が前記ベクトルサイズ比率のスレショルド値を外れるか、又は前記現在ベクトルＡと前記現在ベクトルＢとのベクトルアングル差が前記ベクトルアングル差のスレショルド値を外れる場合、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化せず、前記現在ベクトルＡと前記現在ベクトルＢとを一緒のグループにグループ化しない場合、前記ペアリングアルゴリズムコントローラは、新たなベクトルＢとして第３モーションベクトルを選択し、前記現在ベクトルＡと前記新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記新たなベクトルＢとのベクトルアングル差に基づいて、前記サイズ比率比較器及び前記ベクトルアングル比較器にて前記現在ベクトルＡと前記新たなベクトルＢとを比較し、前記ペアリングアルゴリズムコントローラは、新たなベクトルＡとして第２モーションベクトルを選択し、さらに新たなベクトルＢとして第４モーションベクトルを選択し、前記現在ベクトルＡと前記さらに新たなベクトルＢとを一緒のグループにグループ化するか否かを決定するため、前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルサイズ比率及び前記現在ベクトルＡと前記さらに新たなベクトルＢとのベクトルアングル差に基づいて、前記サイズ比率比較器及び前記ベクトルアングル比較器にて前記現在ベクトルＡと前記さらに新たなベクトルＢとを比較することを特徴とする。
（正規化されたベクトルａは、ベクトルＡをベクトルＡの絶対値｜Ａ｜によって除算したもの（ａ＝Ａ／｜Ａ｜）であり、正規化されたベクトルｂは、ベクトルＢをベクトルＡの絶対値｜Ａ｜によって除算したもの（ｂ＝Ｂ／｜Ａ｜）であり、ベクトルＡは、Ａ＝（ｘａ，ｙａ）であり、ベクトルＢは、Ｂ＝（ｘｂ，ｙｂ）である。）
【００２４】
本発明の実施形態は、以下、添付図面を参照して、より詳しく説明する。しかし、上記本発明は、他の形態で具現され、ここで説明した実施形態に限定されるものではない。また、本実施形態は、公開された範囲で徹底的且つ完璧であるだけではなく、従来技術に本発明の概念の範囲を全体的に伝達できるように提供する。数字等は全体要素等を参照する。
添付した図面は、本発明の概念に対する理解を助けるために、以下の詳細な説明と共に提供する。図面は、本発明の実施形態を示し、詳細な説明と共に本発明の概念の原理を説明するためのものである。
【図面の簡単な説明】
【００２５】
【図１Ａ】本発明の一実施形態によるデジタルイメージ安定化（ＤＩＳ）方法を説明するための現在フレーム、基準フレーム、及び選択された特徴点とモーションベクトルとを示す図である。
【図１Ｂ】本発明の一実施形態によるＤＩＳ方法を説明するための現在フレーム、基準フレーム、及び選択された特徴点とモーションベクトルとを示す図である。
【図１Ｃ】本発明の一実施形態によるＤＩＳ方法を説明するための現在フレーム、基準フレーム、及び選択された特徴点とモーションベクトルとを示す図である。
【図１Ｄ】本発明の一実施形態によるＤＩＳ方法を説明するための現在フレーム、基準フレーム、及び選択された特徴点とモーションベクトルとを示す図である。
【図１Ｅ】本発明の一実施形態によるＤＩＳ方法を説明するための現在フレーム、基準フレーム、及び選択された特徴点とモーションベクトルとを示す図である。
【図１Ｆ】本発明の一実施形態によるＤＩＳ方法を説明するための現在フレーム、基準フレーム、及び選択された特徴点とモーションベクトルとを示す図である。
【図２Ａ】図１Ａ〜図１Ｆに示したＤＩＳ方法において、ボーダー（ｂｏｒｄｅｒ）領域とコア（ｃｏｒｅ）領域内の複数のタイル（ｊ×ｋ）とに分けられた図１Ａの現在フレーム（Ｆｔ）を含む図１Ｅのキャプチャーされたフレーム図である。
【図２Ｂ】図１Ａ〜図１Ｆに示したＤＩＳ方法において、選択された特徴点、拒絶された特徴点、及び取り消された特徴点を示す図２Ａのイメージフレームのコア領域内の１つのタイルの図である。
【図３】本発明の一実施形態によるＤＩＳ処理を行う回路ブロック図である。
【図４Ａ】図１Ａ〜図１Ｆに示したＤＩＳ方法を行うため、図１Ａ及び図２Ａのイメージフレームの各タイル内の複数の特徴点を識別して選択する方法を示すフローチャートである。
【図４Ｂ】図１Ａ〜図１Ｆに示したＤＩＳ方法を行うため、図１Ａ及び図２Ａのイメージフレームの各タイル内の複数の特徴点を識別して選択する方法を示すフローチャートである。
【図５】図１Ａ〜図１Ｆに示したＤＩＳ方法におけるモーションベクトル計算段階を示すため、スーパーインポーズされたタイルモーションベクトルを有してダウンサンプルされた図１Ａの現在フレーム（Ｆｔ）を示す図である。
【図６】図１Ａ〜図１Ｆに示したＤＩＳ方法で用いられた１つの選択された特徴点のモーションベクトルを計算するブロックマッチング検索のための開始ベクトルとして図５のタイルモーションベクトルを用いることを示す図５のダウンサンプルされたフレーム内の１つのタイルの部分を示す図である。
【図７】図１Ａ〜図１Ｆに示したＤＩＳ方法を行うため、図１Ａ及び図２Ａのイメージフレーム内の選択された特徴点のモーションベクトルを計算する方法を示すフローチャートである。
【図８Ａ】カメラが並進的な動きのみで回転的な要素を有しない場合、カメラから同じ距離でビデオ場面内の同一の実際に静止した客体の２つの特徴点のモーションベクトルを示す図である。
【図８Ｂ】カメラが回転的な要素を有する場合、カメラから同じ距離で実際に静止した客体の２つの特徴点のモーションベクトルを示す図である。
【図８Ｃ】カメラが並進的な動きのみで回転的な要素を有しない場合、カメラから異なる距離で同一の実際に静止した客体の２つの特徴点のモーションベクトルを示す図である。
【図９Ａ】モーションベクトルの４つの方向及びサイズが全て異なるにも拘わらずベクトル差が同じサイズを有するそれぞれの対を示すため、ビデオ場面内の実際に静止した客体の特徴点の２対のモーションベクトルを示す図である。
【図９Ｂ】モーションベクトルの４つの方向及びサイズが全て異なるにも拘わらずベクトル差が同じサイズを有するそれぞれの対を示すため、ビデオ場面内の実際に静止した客体の特徴点の２対のモーションベクトルを示す図である。
【図１０】図１Ａ〜図１Ｆに示したＤＩＳ方法における特徴点グループ化のために用いられるアングル差の間接的な測定のための正規化されたベクトル差の計算を示す３つのベクトル図である。
【図１１】図１Ａ〜図１Ｆに示したＤＩＳ方法における図１Ｄのベクトルグループ化を行うため、図１Ａ及び図２Ｂのイメージフレーム内の選択された特徴点のモーションベクトル間のアングル差の間接的な測定のために図１０（ａ）〜（ｃ）の正規化されたベクトル差を用いてグループ化するアルゴリズムのフローチャートである。
【図１２】図１１のグループ化アルゴリズムを用いるための近似値の有効性を示し、アングル差θの関数として、正規化されたベクトル差（ａ−ｂ）のサイズ比率｜ｂ｜に対する正規化されたベクトル差（ａ−ｂ）のサイズ｜（ａ−ｂ）｜のグラフである。
【図１３】図１１の特徴点グループ化アルゴリズムを行うグループ化アルゴリズム回路１３１０を含む特徴点グループ化回路のブロック図である。
【発明を実施するための形態】
【００２６】
図１Ａ〜図１Ｆは、本発明の一実施形態によるデジタルイメージ安定化（Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｓｔａｂｉｌｉｚａｔｉｏｎ：以下、ＤＩＳと称する）方法において、各段階を説明するための現在フレーム、基準フレーム、及び選択された特徴点とモーションベクトルとを示す図である。
【００２７】
図１Ａは、２つの連続した映像フレームである、場面（ｓｃｅｎｅ）の現在フレーム（Ｆｔ）及び基準フレーム（Ｆｔ＋１）を示す。場面は、静止している物体（ｏｂｊｅｃｔ）（全景の丘、電柱、山、及び太陽）及び動く物体（左側の鳥）を含む。現在フレーム（Ｆｔ）及び基準フレーム（Ｆｔ＋１）は、図１Ｅに示したように、より広い領域を有するそれぞれの連続するキャプチャーされたフレームの一部である。より広いキャプチャーされたフレームは、ＤＩＳ以前にイメージセンサーによってキャプチャーされた原本（ｒａｗ）イメージである。基準フレーム（Ｆｔ＋１）は、ジッタ動作によって引き起こされたカメラ軌跡のために、現在フレーム（Ｆｔ）と関連して回転及び並進する。キャプチャーされたフレーム（図１Ｅ参照）の面積は、ビデオカメラのイメージセンサー（図示せず）の物理的なハードウェア面積によって一般的に予め決定される。現在フレーム（Ｆｔ）及び基準フレーム（Ｆｔ＋１）の面積は、カメラのジッタ動作のためにキャプチャーされたフレームの境界（ｂｏｕｎｄｓ）を超えた現在フレーム（Ｆｔ）の“オーバーエクスカーション（ｏｖｅｒｅｘｃｕｒｓｉｏｎｓ）”の発生を避けるか、最小化するために動的に選択される。
【００２８】
図１Ｂは、場面内のアクチュアリーステーショナリー物体（ａｃｔｕａｌｌｙ  ｓｔａｔｉｏｎａｒｙ  ｏｂｊｅｃｔｓ）及び動く物体と関連した現在フレーム（Ｆｔ）で選択された複数の特徴点（円）を示す。現在フレーム（Ｆｔ）は、複数の矩形タイルに分けられており、各タイルは、少なくとも１つの選択された特徴点を構成する。図１Ｂに示した選択された特徴点は、図２Ａ、図２Ｂ、図４Ａ及び図４Ｂに示す方法の各段階を行うことによって、及び／又は図３の回路によって、識別されて選択されうる。現在フレーム及び基準フレームは、図１Ｂに示した選択された特徴点が、図２Ａ、図２Ｂ、図４Ａ及び図４Ｂに示す方法の各段階を行うことによって識別されて選択される間に、図３に示す回路のメモリ３５０に保存される。
【００２９】
図１Ｃは、モーションベクトル（矢印）を有する現在フレーム（Ｆｔ）の各選択された特徴点を示す。図１Ｃに示した選択された特徴点のモーションベクトルは、図６及び図７に示す方法の各段階を行うことによって計算されうる。
【００３０】
図１Ｄは、場面内のモーションベクトルが、グループ化（グループＡ、グループＢ、グループＣ）されたものを示す。場面内のアクチュアリーステーショナリー物体のモーションベクトル（グループＢ、グループＣ）は、ジッタのようなカメラの動きによって引き起こされる。図１Ｄに示した選択された特徴点のモーションベクトルのグループ化は、モーションベクトルがサイズ比率及び正規化されたベクトル差を用いるペアリングアルゴリズム（ｐａｉｒｉｎｇ  ａｌｇｏｒｉｔｈｍ）に基づいて組み合わせ／グループ化（含み／除外）される図１０（ａ）、図１０（ｂ）、図１０（ｃ）、及び図１１に示す方法の各段階によって行われる。
【００３１】
図１Ｅは、イメージセンサー（図示せず）によって出力されたより広くキャプチャーされたフレームのより大きな背景内の基準フレーム（Ｆｔ＋１）を示す。基準フレーム（Ｆｔ＋１）の位置は、基準フレーム（Ｆｔ＋１）のアフィン係数を定義するために、図１Ｄに示したアクチュアリーステーショナリー物体のグループＢ及びグループＣのモーションベクトルを用いることによって決定される。基準フレームの境界を超えてキャプチャーされたフレームのイメージデータは、グループＢ及びグループＣのモーションベクトルが計算される図６及び図７に示す方法の各段階を行う回路に使用されるように作られる。
【００３２】
図１Ｆは、図１Ｄに示したアクチュアリーステーショナリー物体のモーションベクトルによって示されるジッタカメラモーションを除去するためのイメージセンサー（図示せず）によって受信される位置における基準フレーム（Ｆｔ＋１）を示す。基準フレーム（Ｆｔ＋１）のアフィン係数は、カメラのジッタモーションを補正するために基準フレーム（Ｆｔ＋１）を回転させ、並進させる補償回路に（図示せず）よって適用される。
【００３３】
＜特徴点識別、分類、及び分布＞
図２Ａは、図１Ａ〜図１Ｆに示したＤＩＳ方法において、特徴点識別段階と一致するように分類することを容易にするために、ボーダー（ｂｏｒｄｅｒ）領域とコア（ｃｏｒｅ）領域内の複数のタイル（ｊ×ｋ）とに分けられた図１Ｅに示したような現在フレーム（Ｆｔ）のキャプチャーされたフレームの図である。ボーダー領域及びコア領域の境界線は、現在フレーム（Ｆｔ）の境界が、例えば、現在フレームのオーバーエクスカーションを阻むか又は減らすために、動的に受信されたイメージデータコンテンツによって示されるジッタカメラモーションの量に基づいて選択されるか又はハードウェアや受信されたイメージデータコンテンツから独立してソフトウェアによって予め決定されうる。従って、コア領域は、図１Ａに示した現在フレーム（Ｆｔ）のサイズ及び位置に対応するか、或いは対応しないこともある。
【００３４】
それぞれのキャプチャーされたビデオフレームは、ＤＩＳに適した優れた特徴点分布を提供する特徴点をアルゴリズム的に選択するために、小さな数の重ならないタイル（例えば、標準画質では４×４タイル、高画質では６×６タイル、もしくはそれ以上のタイル）に分けることができる。イメージの更に他の領域は、適切な特徴点の他の密度を有しうる。極端な一例として、雲ひとつない青空の場合、フレームの領域は、適切な特徴点を有することができない。他の領域で、潜在的な特徴点は、非常に密集しうる。グローバル基盤スレショルド値（ｇｌｏｂａｌ−ｂａｓｅｄ  ｔｈｒｅｓｈｏｌｄ）に基づいてあらゆる特徴点を識別して選択する場合、特徴点は、イメージの小さな領域に密集し、これは、低級なＤＩＳ結果に繋がることがある。潜在的に更に関心のあるモーションがあるために、構造物がより多いイメージの領域に、より多くの特徴点が位置する必要がある。密集領域で他の注目すべき課題は、如何にあらゆる特徴点が一塊に密集しないようにするかである。従って、本発明の技術的な課題は、ＤＩＳに使われる特徴点の間で最小距離（ＭＩＮ＿ＤＩＳＴ）を確保する効果的な方法を提供する。
【００３５】
ＤＩＳアルゴリズムの安定性のために、特徴点の全体数を制限する同じ時間の間の特徴点は、最大限広く分布する。特徴点の‘望ましい分布’は、次のように表現される。それは、広い凸状の外形を有する。特徴点は、互いに対して過度に近くない（ＭＩＮ＿ＤＩＳＴ）。タイルに適した特徴点が殆どない場合、特徴点が最小限に選択される。他のタイルに適した特徴点がより多い場合、特徴点がより多く選択される（ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ＝ｍｉｎ＿ｆｅａｔｕｒｅｓ＋ｍａｘ＿ｐｌｕｓ＿ｆｅａｔｕｒｅｓ＊（ｔｉｌｅ＿ｖａｒｉａｎｃｅ  σ２／ｔｏｔａｌ＿ｖａｒｉａｎｃｅ））。
【００３６】
各タイルでの最大特徴点数（ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ）は、タイルの輝度分散（σ２）によって決定される。
【００３７】
一実施形態において、各タイルでの最大特徴点数（ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ）は、タイル当たりの最小プログラム可能な特徴点数（ｍｉｎ＿ｆｅａｔｕｒｅｓ）と最大プログラム可能な追加特徴点数（ｍａｘ＿ｐｌｕｓ＿ｆｅａｔｕｒｅｓ）とに、特定タイルの分散（ｔｉｌｅ＿ｖａｒｉａｎｃｅ、σ２）をタイルの分散の総和（ｔｏｔａｌ＿ｖａｒｉａｎｃｅ）で割った値を、乗算して加えた値である。タイルが異なるサイズであれば、補正ファクターが適用可能である。従って、タイル当たりの最終的に選択された特徴点数の最大値は、最小特徴点数（ｍｉｎ＿ｆｅａｔｕｒｅｓ）とタイル分散（σ２）に比例した対応するタイルの加重値（ｗｅｉｇｈｔ）によって正規化された分散特徴点数（ｖａｒ＿ｆｅａｔｕｒｅｓ）との和に代替されうる。ボーダータイルは、ボーダー領域を含んでおり、より広いため、より高い加重値が付与される。このような代替例の場合、所定のタイルに対する最大特徴点数は、次の数式１のように計算される。
【数１】
0005933970.tif 000002
【００３８】
従って、最大選択された特徴点数（ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ）は、全てのタイルで一定に保持されないか、現在フレーム（Ｆｔ）及び基準フレーム（Ｆｔ＋１）の間で一定に保持されない。
【００３９】
一実施形態において、各タイル当たりの最大特徴点数（ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ）は、各タイルの輝度分散（σ２）及びフレームの全体分散の計算が前に要求され、この全体輝度分散で割った各タイルの輝度データの分散（σ２）の関数である。当該技術分野で通常の知識を有する者は、他の関数（例えば、タイルの分散（σ２）だけではなく、平均輝度値を含む関数）でも可能であるということを容易に理解することができる。
【００４０】
特徴点を識別するために、ハリスコーナー感知器（Ｈａｒｒｉｓ  Ｃｏｒｎｅｒ  Ｄｅｔｅｃｔｏｒ）又はこれと類似したコーナー感知器（Ｃｏｒｎｅｒ  Ｄｅｔｅｃｔｏｒ）が使用されうる。ハリスコーナー感知器は、イメージのあらゆるピクセルを可能性のある特徴点候補として評価する。先順位の特徴点候補は、フィーチャークオリティー推定関数（ｆｅａｔｕｒｅ  ｑｕａｌｉｔｙ  ｅｓｔｉｍａｔｉｏｎ  ｆｕｎｃｔｉｏｎ）が部分的な最大値を有するポイントである。特徴点選択の開示された方法は（このピクセルが特徴点としてどのくらい適するかを評価する）、各識別された特徴点の結果値をグローバル基盤スレショルド値よりはローカルスレショルド値と比較することによって、ハリスコーナー感知器によって識別された特徴点の選択を最適化する。従って、開示された方法は、各ローカル領域での特徴点密度及びフレームの他の部分との対比における差を考慮する。
【００４１】
得られた特徴点分布は、各タイルの特徴点数がタイルの輝度イメージデータの輝度分散（σ２）に線形的に比例して増加するビデオフレーム（重ならないタイル）の小さな領域に基づく。より関心のあるイメージを有するタイル及びより多くの特徴点に対する要求は、より高い輝度分散（σ２）を有する。
【００４２】
図４Ａ及び図４Ｂは、同じ時間に小さいローカル状態情報が必要であり、ハードウェア構築コストを減らしうる各タイルの特徴点の間の最小距離（ＭＩ  Ｎ＿ＤＩＳＴ）を保持する方法を示すフロー図である。
【００４３】
図２Ｂは、選択された特徴点（黒）、拒絶された特徴点（白）、及び選択されたが取り消された特徴点（×表示された黒）を示す図２Ａのイメージフレームのコア領域内の何れか一つのタイルの図である。図２Ｂで小さな四角形に見える特徴点は、ハリスコーナー感知器アルゴリズムを用いて特徴点候補として識別され、順次に図４Ａ及び図４Ｂに示した方法と関連したラスタースキャン順に選択されるか、拒絶されるか、取り消される。
【００４４】
各タイルに対して識別された特徴点候補のうちから最大特徴点数（ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ）は選択される。本発明の一実施形態によると、各識別された特徴点候補は、例えば、次のようなラスタースキャン順に選択されうる。
【００４５】
ｉ．識別された特徴点候補は、ハリスコーナー推定関数がプログラム可能なスレショルド値を超過し、推定がローカル最大値を有するピクセルである。ローカル最大値になるためには、問題となる位置における値が、スキャンオーダーにおいて、このピクセルの次で、直接的であり対角に隣り合ったピクセルの値より大きいか又は同じでなければならず、スキャンオーダーにおいて、このピクセルの前に全て直接的であり対角に隣り合ったピクセルの値より大きくなければならない。
【００４６】
ｉｉ．特徴点候補が同一である場合、各タイルのための既定の最大特徴点候補数（例えば、３２、４８、６４、又は最終的に選択されたより高い特徴点最大値）を保存することができるデータ保存構造（例えば、他の実施形態として具現されうる分類されたリスト）で保存され、プログラム可能な閉鎖（ｌｏｃｋｏｕｔ）範囲（ＭＩＮ＿ＤＩＳＴ）内にある更に高い推定関数値を有する特徴点候補はないと仮定する。図示する目的で、本実施形態を表わすために３２の最大値が選択される。
【００４７】
ｉｉｉ．後に識別された特徴点候補がデータ構造に保存された場合、閉鎖範囲（ＭＩＮ＿ＤＩＳＴ）よりこのポイントに更に近い、即ちより小さな推定関数値を有する他の特徴点候補は、データ保存構造から除去される。
【００４８】
例えば、タイル（５，４）の特徴点候補の既定の最大値が４（ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ＝４）と仮定する。図２Ａのタイル（５，４）は、図２Ｂのように４つの最終的に選択された特徴点（黒：ラスタースキャン順に、ＳＦＰ３、ＳＦＰ４、ＳＦＰ５、及びＳＦＰ７）、３つの選択された後に取り消された特徴点（×表示された黒：ＳＦＰ１、ＳＦＰ２、及びＳＦＰ６）及び２つの拒絶された（選択されていない）特徴点（白）を含む。選択されてから取り消された特徴点（×表示された黒：ＳＦＰ１、ＳＦＰ２、及びＳＦＰ６）は、図４Ａ及び図４Ｂの方法を行うラスタースキャン順に特徴点として選択されたが、後に特徴点候補として識別されて選択されたより広い特徴点の排他的領域（ｅｘｃｌｕｓｉｏｎａｒｙ  ｚｏｎｅ：ＭＩＮ＿ＤＩＳＴ）内に存在するため、選択された特徴点としては、順次に取り消された特徴点候補であり得る。或いは、選択された特徴点のリストが一杯になって（選択された特徴点候補の数：ＳＦＰ＿ｃｏｕｎｔ＝ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ）、先行して選択された特徴点が、選択された特徴点のリストのうち、最も小さく、後に識別されて選択された特徴点候補より小さいため、選択された特徴点としては、順次に取り消された特徴点候補であり得る。
【００４９】
選択されてから取り消された特徴点ＳＦＰ１は、図４Ａ及び図４Ｂの方法によるラスタースキャン順に識別されて選択された第１特徴点であった。次いで、選択されてから取り消された特徴点ＳＦＰ２は、識別されて選択されたが、ＳＦＰ２が選択された後に、ＳＦＰ２より大きい特徴点ＳＦＰ３が識別された。ＳＦＰ２が、より大きく、選択された特徴点ＳＦＰ３の排他的領域（ＭＩＮ＿ＤＩＳＴ）内にあるため、ＳＦＰ２は、ＳＦＰ３が選択されると直ちに取り消される。ＳＦＰ３が選択された後に、特徴点候補は、ＳＦＰ３の排他的領域（ＭＩＮ＿ＤＩＳＴ）の右下のコーナーで識別され、特徴点候補がＳＦＰ３より小さく、排他的領域内にあるため、それは、直ちに拒絶（選択されずに）される。次に、特徴点候補は、ＳＦＰ３の排他的領域（ＭＩＮ＿ＤＩＳＴ）のすぐ外の下で識別され、ＳＦＰ４が特徴点候補として選択される（後で取り消されない）。そして、特徴点候補は、更にＳＦＰ３の排他的領域（ＭＩＮ＿ＤＩＳＴ）のすぐ右下で識別され、特徴点候補としてＳＦＰ５が選択される（ＳＦＰ７の排他的領域に近いが、内側にないため後で取り消されない）。次いで、特徴点候補は、ＳＦＰ５の排他的領域（ＭＩＮ＿ＤＩＳＴ）のすぐ右下で識別され、特徴点候補としてＳＦＰ６が選択される（更に大きな、後で選択される特徴点ＳＦＰ７の排他的領域内において、後に取り消される）。ＳＦＰ６が選択されると、選択された特徴点のリストは、既に“一杯になり”（タイルに対する最大特徴点数は、４）、ＳＦＰ１は、選択された特徴点ＳＦＰ１、ＳＦＰ３、ＳＦＰ４、及びＳＦＰ５の中で最も小さく、ＳＦＰ６がＳＦＰ１より大きいために、ＳＦＰ１は取り消される。次いで、特徴点候補は、ＳＦＰ６の排他的領域（ＭＩＮ＿ＤＩＳＴ）内の下で識別され、特徴点候補としてＳＦＰ７が選択される（選択された特徴点ＳＦＰ７がＳＦＰ６より大きいためか、又はリストが一杯になるなどの理由でＳＦＰ６が直ちに取り消されたため）。次いで、特徴点候補は、ＳＦＰ７の排他的領域（ＭＩＮ＿ＤＩＳＴ）内の下で識別された特徴点候補は、以前の特徴点候補がＳＦＰ７より小さいために拒絶される（選択されず）。ＳＦＰ３がＳＦＰ７より非常に大きい場合、ＳＦＰ７が実際に取り消されたＳＦＰ２より小さいものが可能であるが、特徴点の優れた分布が得られる。プログラム可能な閉鎖範囲（ＭＩＮ＿ＤＩＳＴ）は、最終的に選択された特徴点が過度に密集されないようにする。
【００５０】
各タイルのピクセル輝度分散（σ２）は、各タイルがダウンサンプルされるダウンスケーリングプロセスの間に決定されうる。各タイルの最大特徴点数は、タイル当たりのプログラム可能な特徴点の一定の最小数と全体の変わりうる特徴点の数とを加えたものに特定タイルのタイル分散（σ２）の比率を乗算し、タイル分散の和で割ったものの総和で決定される。補正ファクターは、特徴点がボーダー領域もあり得るので、縁部とエッジタイル領域のために加えることがあり、各タイルのために、特徴点候補の最大数までは、分類プロセス（ラスタースキャンオーダーによって識別された各特徴点に対して、選択する段階、拒絶する段階、取り消す段階）を用いて集められて保存することができる。各タイルに対して最終的に選択された特徴点候補は、単純に最大値が既定の最も高い推定関数応答を有する特徴点候補である。低いコントラストイメージデータのタイルのような最終的に使用された特徴点の結果数がプログラムされた最小数（ｍｉｎ＿ｆｅａｔｕｒｅｓより小さな）より小さい場合に、所定のタイルで可能な特徴点候補が十分ではない場合があり得る。
【００５１】
従って、ラスタースキャンオーダーによる特徴点候補を処理する方法は、より多くの新たな特徴点候補が追って識別されて選択される間に、最大限過度に密集されないように選択された特徴点の計算された最大の数を殆ど含みうるリストを保持する段階が提供される。特徴点を分類するラスタースキャンオーダー方法は、識別された特徴点候補のうちから優先順位を付けて選択する多様な他の方法に比べて、メモリと計算量とを減らしうる利点がある。例えば、他の実施形態において、タイルの全ての特徴点候補は、識別されてメモリの大きなリストに保存され、次いで、タイルの全ての特徴点候補が識別された直後に数学的分類アルゴリズムは、セットされた他の特徴点候補の排他領域（ＭＩＮ＿ＤＩＳＴ）に属さない最も広い特徴点候補の（既定の最大のサイズの）最適のセットを探すのに適用可能である。しかし、そのような分類アルゴリズムは（タイルの識別された特徴点の全体リストを保存する）、より多くの物理的なメモリを必要とし、図４Ａ及び図４Ｂのラスター順の分類（選択する段階、拒絶する段階、取り消す段階）方法より多くの全体計算を（例えば、図２Ｂに示した結果）潜在的に必要とする。特徴点候補は、後に選択されるが、後に取り消される特徴点候補によってリストから取り消されるため、図４Ａ及び図４Ｂのラスタースキャン順の分類アルゴリズムは、必然的にグローバル最適条件である選択された特徴点のセットを提供しないが、代わりに制限されたローカルストレージを有するハードウェアに具現されうるアルゴリズムを提供する。図４Ａ及び図４Ｂの方法が、ハリスコーナー感知器が行ったピクセルオーダー（左から右に、上から下に）である“ラスタースキャンオーダー”によって識別された特徴点候補を処理するものとして表わされても、特徴点候補の選択のあらゆる順序は、全ての特徴点が識別され、結果的に順次に分類される限り、隣接しない特徴点候補の不連続した順序のような方法で使用される。
【００５２】
図３は、本発明の一実施形態による特徴点回路のブロック図である。特徴点回路３０００は、特徴点セレクター３００、ＳＦＰモーションベクトル計算器７００、及び共有されるＲＡＭメモリ３５０を含む。特徴点セレクター３００は、第１ダウンサンプラー３１０、特徴点候補識別器３３０、及び特徴点候補分類器３４０を含む。
【００５３】
特徴点候補識別器３３０は、ハリスコーナー感知器アルゴリズムを用いて特徴点候補を識別し、識別された特徴点（例えば、同時に１タイルでピクセル位置とハリスコーナー応答、ラスタースキャンオーダーとによって識別された）を特徴点候補分類器３４０に出力する。特徴点候補分類器３４０は、図１Ａ、図２Ｂに示したような各タイルの識別された特徴点を、図４Ａ及び図４Ｂに示す順次的な分類方法によって行うように構成される。第１ダウンサンプラー３１０は、次の数式２によって、イメージフレームの各タイルのタイル分散（σ２）を計算するタイル分散計算器３２０の機能ブロックを含む。
【数２】
0005933970.tif 000003
ｙは、タイル内の輝度分散であり、Ｎは、タイル内のピクセルの数である。
【００５４】
図３に示した回路３０００は、半導体チップ内に具現され、半導体チップは、イメージをキャプチャーするセンサーを有するカメラからイメージデータを受信するＩ／Ｏピン及びキャプチャーされたイメージをイメージデータに変換する回路素子を含む。図３の回路３０００によって処理されたデータは、Ｉ／Ｏピンを通じてカメラの他の構成要素として出力される。後述するように、メモリは、物理的なサイズが小さくなければならず、保存容量は制限される。計算に消耗する電力を減らし、要求される演算数を減らすため、特徴点セレクター３００は、２、４、又は８のセレクタブルファクター（ｓｅｌｅｃｔａｂｌｅ  ｆａｃｔｏｒ：ｆｓ１）による第１ダウンサンプラー３１０で水平及び垂直にサブサンプリングされて、ルーマデータ（ｌｕｍａ  ｄａｔａ）のみで作動することができる。本実施形態では、セレクタブルファクター（ｆｓ１）が選択される。セレクタブルファクター（ｆｓ１）によってダウンサンプルされたルーマデータは、特徴点候補識別器３３０で特徴点識別のために使われ、他の実施形態において、ＳＦＰモーションベクトル計算器７００に含まれる階層的ブロックマッチング検索ユニット７３０による特徴点モーションベクトル推定のために使われる。より小さなダウンサンプルされたイメージが、第１ダウンサンプラー３１０で計算される間に、各タイルの輝度分散（タイルの分散：σ２）が計算され、３×３ハリスコーナー行列のより小さな固有値（ｅｉｇｅｎ−ｖａｌｕｅ）のグローバル最大値が識別される。フレーム上部左側のタイルの上部左側のピクセルと同格（ｃｏｏｒｄｉｎａｔｅ）であるタイルオフセットとタイルピクセルディメンションとの両方とも最も大きなサブサンプリングファクター（ｆｓ２）の積である。イメージコア領域は、全体イメージの中央に位置することが好ましい。従って、左側のボーダー領域の幅は、右側のボーダー領域の幅と同一であり、上のボーダー領域の高さは、下のボーダー領域の高さと同一である（図２Ａ参照）。
【００５５】
入力フレーム輝度データがサブサンプルされ、ＲＡＭメモリ３５０に保存されると、特徴点候補識別器３３０は、タイル順序によって順次に再び読み取り（ｓｅｑｕｅｎｔｉａｌｌｙ  ｆｅｅｄ）、識別された特徴点候補を特徴点候補分類器３４０に伝送する。特徴点候補識別器３３０の特徴点識別プロセスのために、ボーダー領域に隣接するタイル内のポテンシャル特徴点の統計領域（ｓｔａｔｉｓｔｉｃｓ  ａｒｅａ）は、ボーダー領域に拡張され、従って、各ボーダー領域タイルのピクセルは、隣接するタイルのピクセルと共に処理される。ピクセルデータは、ラスタースキャン順（上から下のラインに、各ラインで左側から右側のピクセルに）に各タイルで読み取られる。
【００５６】
各タイルを処理するために、特徴点候補識別器３３０は、ハリスコーナー感知器を用いて特徴点識別のための各内部タイルボーダー上の３つの追加的なピクセルが必要である。従って、このようなピクセルは、一回以上読み取られうる。識別された特徴点候補は、ハリスマトリックスのより低い固有値λ１がローカル最大値を有する各タイル内のピクセルである。ローカル最大値であることを証明するために、問題視されるピクセルのコーナー応答は、左上、上、右上、及び左に隣り合ったピクセルのコーナー応答より大きくなければならず、上、左下、下、及び右下に隣り合ったピクセルのコーナー応答と同じか、大きくなければならない。上記定義で、より大きな領域で同じ一定のコーナー応答を有する少なくとも１つのポイントは、潜在的な特徴点候補として識別される。ローカル最大値のための感知ロジックには、コーナー応答の２本のラインバッファを必要とする。ローカルコーナー応答の最大値を有するポイントは、先ずプログラム可能なコーナー応答スレショルド値と比較される。問題視されるポイントのコーナー応答が、スレショルド値より小さければ、上記ポイントは無視される。そうでない場合、特徴点後補とそのコーナー応答は、特徴点候補分類器３４０に伝送される。
【００５７】
特徴点候補分類器３４０は、各タイルで最も高いコーナー応答を有する特徴点候補を最大特徴点数（ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ）まで記録すると同時に、同時に全ての特徴点が互いに対して最小プログラム可能な距離（排他領域；ＭＩＮ＿Ｄ  ＩＳＴ）を有するかを検証する。２つのポイントの間に上記アルゴリズムに使われる距離は、次の数式３によって決定される。
【数３】
0005933970.tif 000004
【００５８】
図４Ａ及び図４Ｂに示す分類方法は、選択された特徴点と新たに入ってくる特徴点候補の分類リストの現在コンテンツのみを考慮し、直ちに決定を出す動作によって行われる。従って、図４Ａ及び図４Ｂの方法が適用された特徴点候補分類器３４０は、本質的にグローバル最適条件を計算せず、上記出力は、入ってくる特徴点候補が提供される順序による。
【００５９】
特徴点候補分類器３４０は、順に選択された特徴点を出力し、選択された特徴点は、図３に示したメモリ３５０の一部としてＳＦＰリストに保存される。
【００６０】
図４Ａ及び図４Ｂは、図１Ａ〜図１Ｆに示したＤＩＳ方法の各段階を行うために、図１Ａ及び図２Ａのイメージフレームの各タイル内の複数の特徴点を識別して選択する方法を示すフローチャートである。上記方法は、現在フレーム（Ｆｔ）の輝度データが受信されるデータ入力段階（Ｓ４００）から始まり、その後ダウンサンプリング段階（Ｓ４０２）が行われる。初期化段階（Ｓ４０４）は、現在タイルカウンター値（ｃｕｒｒｅｎｔ＿ｔｉｌｅ）及びピクセルカウンター（ｃｕｒｒｅｎｔ＿ｐｉｘｅｌ）をリセットする。
【００６１】
次に、ハリスコーナー感知器は（Ｓ４０６、ＳＤ４０８、及びＳ４１０）、ラスタースキャン順に現在タイル（ｃｕｒｒｅｎｔ＿ｔｉｌｅ）のダウンサンプルされた輝度データの各ピクセルで、現在ピクセル（ｃｕｒｒｅｎｔ＿ｐｉｘｅｌ）をインクリメント（Ｓ４２８）する。現在ピクセルのコーナー応答がローカル最大値や限界値を超過する度に（ＳＤ４０８のＹＥＳ経路）、現在ピクセルは、現在特徴点候補として識別され（Ｓ４１０）、直ちに特徴点分類アルゴリズムに適用される（ＳＤ４１２、ＳＤ４１４、ＳＤ４１６、ＳＤ４１７、ＳＤ４３０、Ｓ４１８、及びＳ４２０）。
【００６２】
リストが一杯にならなければ、特徴点分類アルゴリズムは、選択された特徴点のリストに既に保存された前に選択された最も低い特徴点候補より現在特徴点候補が大きい場合、現在特徴点候補を選択する（Ｓ４２０）。ＳＤ４１２段階でＹＥＳ経路に行かない場合（ＳＤ４１２のＮＯ経路）、現在特徴点候補としては拒絶される（Ｓ４１７）。現在特徴点候補が選択される場合（選択された特徴点カウント（ＳＦＰ＿ｃｏｕｎｔ＝ｍａｘ＿ｎｕｍ＿ｆｅａｔｕｒｅｓ＝ｍｉｎ＿ｆｅａｔｕｒｅｓ＋ｍａｘ＿ｐｌｕｓ＿ｆｅａｔｕｒｅｓ＊（ｔｉｌｅ＿ｖａｒｉａｎｃｅ／ｔｏｔａｌ＿ｖａｒｉａｎｃｅ））によって表わされるように）、選択された特徴点のリストが既に一杯になっていれば、その次に、リストから最も小さな前に選択された特徴点候補を取り消し（ＳＤ４３０）、そうでなければ、選択された特徴点カウント値（ＳＦＰ＿ｃｏｕｎｔ）をインクリメントする（ＳＤ４３０）。
【００６３】
特徴点分類アルゴリズムは、現在特徴点候補を、現在特徴点候補が既にリスト（ＳＤ４１４）にある前に選択された特徴点の排他領域（ＭＩＮ＿ＤＩＳＴ）内になくより大きい（ＳＤ４１６）場合、選択する（Ｓ４２０）。そして、現在特徴点候補が既にリスト（ＳＤ４１４）にある前に選択された特徴点のより大きな排他領域（ＭＩＮ＿ＤＩＳＴ）内にある場合（ＳＤ４１６）、選択されることなしに拒絶される（ＳＤ４１６のＮＯ経路及びＳＤ４１７）。一方、現在特徴点がより小さな（ＳＤ４１６）既にリスト（ＳＤ４１４）にある前に選択された特徴点の排他領域（ＭＩＮ＿ＤＩＳＴ）内にない場合、全ての小さな（ＳＤ４１６）前に選択された特徴点は取り消される（ＳＤ４１６のＹＥＳ経路及びＳ４１８）。この際、現在特徴点候補が選択され（Ｓ４２０）、選択された特徴点カウント（ＳＦＰ＿ｃｏｕｎｔ）は、それによって更新（減少するか、保持）される（Ｓ４１８）。
【００６４】
現在特徴点候補が選択されるか（Ｓ４２０）、拒絶されると（Ｓ４１７）、ハリスコーナー感知器は、現在タイル（ＳＤ４２２）内の現在ピクセル（Ｓ４１０）の次の値を出力する（Ｓ４２８）。次に識別された特徴点候補は、直ちに特徴点分類アルゴリズムに提供される（ＳＤ４１２、ＳＤ４１４、ＳＤ４１６、Ｓ４１７、ＳＤ４３０、Ｓ４１８、及びＳ４２０）。現在タイルの最後のピクセルが処理されると（ＳＤ４２２）、次のタイルが処理される（ＳＤ４２４及びＳ４２６）。最後のタイルが処理されると、次のイメージフレームが処理されて上記処理が完了する。
【００６５】
＜特徴点モーションベクトル計算＞
現在フレーム（Ｆｔ）の各タイルの特徴点が識別されて分類された後、図１Ａ〜図１ＦのＤＩＳ方法の次の段階は、選択された特徴点のそれぞれのためにモーションベクトルを得る。
【００６６】
特徴点のモーションベクトルの計算に使用されるブロックマッチングアルゴリズム（Ｂｌｏｃｋ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍｓ：ＢＭＡ）は、よく知られている。ブロックマッチングでは、エラー関数（例えば、ＳＡＤ、ＭＡＤ、ＭＳＥ）は、基準フレームのターゲット領域内にあるブロックの全ての可能な位置のために計算される。上記関数の最も低い結果を有する位置は、推定されたモーションベクトルの計算に用いられる。ブロックマッチングは、計算上非効率的である。計算上の消耗を減らすためのいくつかの知られた方法がある。段階的又はマルチ解像度ブロックマッチングは、グローバルムーブメントが初めにより低い解像度で計算される方法のうちの１つである。計算されたベクトルは、より高い解像度でより小さな範囲を探すのに使用され、そのために必要な計算動作の総回数を減らしうる。
【００６７】
殆どのアプリケーションやそれぞれのビデオエンコーディングのために、正確なモーションベクトルは、フレームの全てのブロックに対して必要である。従って、後の段階で検索範囲は、一般的に比較的広い。図１Ａ〜図１Ｆに示したＤＩＳ方法で、１フレームから次のフレームまでの特徴点（例えば、アクチュアリーステーショナリー物体の特徴点）の相対的な動きを推定することのみが要求される。イメージ安定化の目的で、背景及び広い物体の動きを表現する正確なモーションベクトルが要求されるが、小さな物体は、それと関連して正確なモーションベクトルを有することが要求されない。小さな物体の不正確なベクトルは、ＤＩＳアルゴリズムの後の段階でフィルタリングされる。
【００６８】
ＤＩＳ方法において重要なより大きな静止物体の特徴点がグローバルな動き又はカメラの動きのために生じる一定の動きを予想することができる。出願人は、独立して動く十分に大きな物体が少なくとも１つのタイルの殆どをカバーすることが分かり、大きな物体のモーションがタイル自体の支配的なモーションとして推定されうるが、小さな物体のモーションは、タイル自体のモーションベクトルに影響を殆ど及ぼさないことが分かった。従って、モーションベクトルを計算するプロセスは、タイルのモーションベクトルを使用しながら階層的モーション推定アルゴリズムを用いてローカルムーブメントよりタイルムーブメントを採択することによって計算を減らすように変更されうる。従って、先ず現在イメージフレームを複数のタイル（ｊ×ｋ個）に分けることである（最初の段階は、図１Ｂ及び図２Ａと関連して示した特徴点選択の目的のために既に行われた）。
【００６９】
ＤＩＳのために十分に正確な特徴点のモーションベクトルを計算する二番目の段階は、最も低い解像度のブロックマッチングを用いてタイル毎に１つのモーションベクトルを得る。上記段階で、所定のタイルの差の絶対値の和（ｓｕｍ  ｏｆ  ａｂｓｏｌｕｔｅ  ｄｉｆｆｅｒｅｎｃｅｓ：ＳＡＤ）が計算される。所定のタイルのモーションベクトルは、ＳＡＤを小さくさせるベクトルである。所定のモーションベクトル候補（ｖ＝（ｖｘ，ｖｙ））のＳＡＤは、次の数式４によって決定される。
【数４】
0005933970.tif 000005
【００７０】
低い解像度のダウンサンプルされたイメージを用いることによって、計算は減って場面にある小さな物体の影響も減る。
【００７１】
三番目の段階で、タイルのモーションベクトルは、ブロックマッチングアルゴリズムに各タイル内の特徴点のモーションベクトルのローカル検索のための開始ベクトルとして用いられる。少なくとも１つのタイルの殆どをカバーすることができる十分に広い物体は、隣接するタイルに拡張され、各タイル内の特徴点は、そのタイル内で発見されるモーションベクトルより隣接するタイルのモーションベクトルに更に強く関連する。従って、所定のタイルの特徴点のモーションベクトルのためのブロックマッチング検索において、隣接する全てのタイルのモーションベクトルを複数の開始ベクトルとして用いることが効果的である。ここで使用されるタイルは、少なくとも最大に支持されるモーションベクトルのサイズのボーダー領域のフレームで中央に位置し、全てのタイルの全ての特徴点のためのモーション検索は、フレーム外部のピクセルを参照せずに行われる。
【００７２】
図５は、図１Ａ〜図１Ｆに示したＤＩＳ方法におけるモーションベクトル計算段階を示すため、スーパーインポーズされたタイルモーションベクトルを有してダウンサンプルされた図１Ａの現在フレーム（Ｆｔ）を示す図である。図５に示した更に小さな（小さいピクセルと小さいデータとを有する）イメージは、水平及び垂直的にサブサンプリングすることによって、前にサブサンプルされたイメージ（図４ＡのＳ４０２）及び元の現在キャプチャーされたフレームから得られる。サブサンプリングファクターｆｓ２（例えば、４）は、グローバル（タイル）モーション推定に使用される。４×４ダウンサンプリングは、入力サイドにオーバーラップなしに（ラウンディングで）、１６ピクセルの平均を求める。次いで、各全体のサブサンプルされたタイルを使用したブロックマッチング検索は、各タイルのモーションベクトルを決定するために行われる。
【００７３】
所定のタイルのモーションベクトルは、ＳＡＤを減らすベクトルである。関連した実施形態で、発見された最初の１つが与えられる。モーションベクトルは、近い特徴点のモーションベクトルのためのローカル検索のための開始ベクトルとして使用される。各開始ベクトルに対するモーション範囲は、プログラム可能である。
【００７４】
タイルモーション推定のために必要な動作の数がローカルモーション推定のために必要な動作の約１２％に過ぎないので、サイクル当たり約８つの絶対差の和を計算することで十分である。従って、シストリックアレイ（ｓｙｓｔｏｌｉｃ  ａｒｒａｙ）が必要なものではない。
【００７５】
図６は、図１Ａ〜図１Ｆに示したＤＩＳ方法で用いられた１つの選択された特徴点のモーションベクトルを計算するブロックマッチング検索のための開始ベクトルとして図５のタイルモーションベクトルを用いることを示す図５のダウンサンプルされたフレーム内の１つのタイルの部分を示す図である。
【００７６】
小さなローカルブロックマッチング検索は、タイル内のあらゆる特徴点のための開始ベクトルのセットのそれぞれの周りにある更に高い解像度ドメイン内で行われる。上記段階は、元のビデオ解像度で行われるか、２又は４のファクター（ｆｓ３）によってサブサンプルされうる。使用された開始ベクトルは、特徴点が属するタイルの開始ベクトルだけではなく、４つの直接隣接するタイル（上のタイル、左のタイル、右のタイル、下のタイル）に属するベクトルであり得る。従って、図６では、ブロックマッチング検索領域１に対応する開始ベクトルは、特徴点（ＦＰ）が属するタイルのモーションベクトル、ブロックマッチング検索領域２に対応する開始ベクトルは、特徴点（ＦＰ）が属するタイルのモーションベクトルの下の下ブロック（ｂｌｏｃｋ  Ｄｏｗｎ）、ブロックマッチング検索領域３に対応する開始ベクトルは、特徴点（ＦＰ）が属するタイルのモーションベクトルの下の右ブロック（ｂｌｏｃｋ  Ｒｉｇｈｔ）、ブロックマッチング検索領域４に対応する開始ベクトルは、特徴点（ＦＰ）が属するタイルのモーションベクトルの下の左ブロック（ｂｌｏｃｋ  Ｌｅｆｔ）、ブロックマッチング検索領域５に対応する開始ベクトルは、特徴点（ＦＰ）が属するタイルのモーションベクトルの下の上ブロック（ｂｌｏｃｋＵｐ）である。他の実施形態によると、４つの対角で隣り合ったタイルの開始ベクトルも使用されうる。特に、タイルベクトルの最初のグループが１つの広い物体を連想させる互いに対して類似したサイズと方向とを有する場合（図８Ａ、図８Ｂ、図９、図１０（ａ）、図１０（ｂ）、図１０（ｃ）と関連するモーションベクトルグループ化参照）、開始ベクトルの中から選択する段階（例えば、ブロックマッチングコンピュテーションの数を減らすこと）のための他の段階が行われる。この代わりに、ブロックマッチングは所定の優先順位を有し、２以上のブロックマッチング検索領域がオーバーラップされる所でのみ、又は互いに最も近いブロックマッチング検索領域間等で行われる。
【００７７】
一般的に、特徴点に対するモーションベクトルの割り当ては、タイルからタイルに進行し、所定のタイルのあらゆる特徴点は、同じ開始ベクトル（例えば、タイルモーションベクトルの同じ選択）を使用できる。しかし、多様な実施形態において、タイルモーションベクトルの感知されたグループ内のタイルに隣接した特徴点は、グループの各メンバーで共通して探すことができる同じ物体上の見えるポイントである可能性が大きくなるという仮定で、所定のタイルの他の部分にある特徴点は、開始ベクトルの他の選択を用いる。従って、ブロックマッチング検索は、初めに各タイルの境界線付近にある特徴点に対して行われ、これは、それらが自分のタイルのモーションベクトル及び／又はタイルモーションベクトルの隣接するグループのタイルモーションベクトルと殆ど又は完全に類似しているかを感知するために行われる。例えば、初めに選択された特徴点（例えば、所定のタイルの境界線付近の全てのポイント又は中央ポイントから最も遠いポイント）のモーションベクトルが、自分のタイルのモーションベクトルと同じか、類似していれば、残った特徴点のための選択された開始ベクトルのセットは減ることになる。
【００７８】
使用された各開始ベクトルのために、ローカル検索のための非常に小さな範囲を使用する。ここで、目標は、各々且つあらゆる特徴点のための正確なベクトルを決定するだけではない。これに関心のある特徴点は、背景や広い物体に属した特徴点である。そのような特徴点のために、タイルモーションベクトルのそれぞれは、良いか関心のある特徴点のモーションベクトルに近くなければならず、従って、各選択されたタイルモーションベクトルに対する小さなローカル検索は十分でなければならない。
【００７９】
図３を再び参照すると、特徴点回路３０００のＳＦＰモーションベクトル計算器７００は、タイルベクトル計算のための第１ダウンサンプラー３１０より更にダウンサンプルされたルーマデータを出力するための第２ダウンサンプラー７１０、各タイルのモーションベクトルを計算するためのタイルベクトル計算器７２０、及び特徴点セレクター３００の特徴点候補分類器３４０から受信された各ＳＦＰのモーションベクトルを決定して出力する階層的ブロックマッチング検索ユニット７３０を含む。第２ダウンサンプラー７１０は、図５に示した深くダウンサンプルされた現在フレーム（Ｆｔ）を出力する。タイルベクトル計算器７２０は、第２ダウンサンプラー７１０によって出力された現在フレーム（Ｆｔ）の深くダウンサンプルされたルーマデータを用いて、各タイルのモーションベクトルを計算する。階層的ブロックマッチング検索ユニット７３０は、２つの連続したフレームのフル解像度のルーマデータ（又は、第１ダウンサンプラー３１０の出力）を用いて、上述した開始ベクトルのようなタイルベクトルを用いて、特徴点セレクター３００の特徴点候補分類器３４０によって出力された各選択された特徴点のモーションベクトルを決定する。
【００８０】
図７は、図１Ａ〜図１Ｆに示したＤＩＳ方法の各段階を行うために、図１Ａ及び図２Ａの現在フレーム（Ｆｔ）内の選択された特徴点（ＳＦＰ）のモーションベクトルを計算する方法を示すフローチャートである。
【００８１】
開始段階で、図３に示した階層的ブロックマッチング検索ユニット７３０は、ビデオの２つの連続したフレーム（現在フレーム及び基準フレーム）のルーマデータを受信し（Ｓ７００ｉ）、選択された特徴点のピクセル位置を受信する（Ｓ７００ｉｉ）。現在フレーム（Ｆｔ）は、図４Ａ及び図４Ｂの特徴点分類方法に既に用いられたタイルのような複数のサブサンプルされたタイルに分けられる（Ｓ７１０）。現在フレーム（Ｆｔ）は、図２Ａに示したようにボーダー領域に加えて複数のｊ×ｋタイルに分けられる（Ｓ７１０−Ａ）。各タイルと関連したルーマデータは、図５に示したようにファクター（ｆｓ２：例えば、ＳＤでは、ｆｓ２＝４、ＨＤでは、ｆｓ２＝８）によってサブサンプルされる（Ｓ７１０−Ｂ）。
【００８２】
次に、各タイルのモーションベクトルは、図５に示したように、深くサブサンプルされたルーマデータと共にフルサーチブロックマッチングを用いて計算され、サブサンプルされた解像度に比べて、ハーフペル（ｈａｌｆ−ｐｅｌ）正確度を有する（Ｓ７２０）。計算されたモーションベクトルに対応して計算された最小ＳＡＤ値は、ＤＩＳの他の特徴（例えば、小さな物体の特徴点をフィルタリングする）における用途のために保存することができる。開始ベクトルは、上述したように、Ｓ７２０段階からの計算されたタイルモーションベクトルに基づいて、現在選択されたＳＦＰのために選択される（Ｓ７３０）。段階的ブロックマッチングアルゴリズムは、フル解像度ルーマデータと共に行われ、現在ＳＦＰのモーションベクトルを決定するために、タイルベクトルに基づいて選択された開始ベクトルを使用する（Ｓ７４０）。Ｓ７３０及びＳ７４０段階は、あらゆるタイル内のあらゆるＳＦＰのモーションベクトルが計算されるまで反復される（ループＳＤ７５０、及びＳ７５２）。
【００８３】
＜モーションベクトルのサイズと方向とによる特徴点グループ化＞
ビデオフレーム間のモーションは、隣接するフレーム内の識別可能な特徴点のモーションベクトルを計算することによって感知される。特徴点のモーションベクトルは、カメラ／場面のグローバルモーションと区別されるように、場面で動く物体を識別することの目的のためにグループ化される。カメラ／場面のグローバルモーションは、意図された（例えば、パンニング、そして、意図していない（ジッタリ）グローバルモーション間を区別するために分析される。
【００８４】
カメラの動き（カメラ軌跡）がない場合、アクチュアリーステーショナリー物体（例えば、岩のエッジ、山頂）の各感知された特徴点は、２以上の連続したフレームのそれぞれで同じ位置に発見されることが予見され、全ての感知された特徴点のモーションベクトルは、無効（ｎｕｌｌ）として測定される。しかし、カメラの動きがあると、所定のアクチュアリーステーショナリー物体の多くの特徴点のベクトルは、異なるサイズと方向とを有する。ＤＩＳ回路は、複数のモーションベクトルが同じアクチュアリーステーショナリー物体によるものであるように、特徴点の複数のモーションベクトルを正しくグループ化するために使用される。
【００８５】
一般的に、カメラの動きは、並進（ｔｒａｎｓｌａｔｉｏｎａｌ）及び回転（ｒｏｔａｔｉｏｎａｌ）の動きの混合であり、カメラから場面内の物体間の距離は可変される。並進カメラ運動は、背景のカメラからの距離に基づいたモーションベクトルのサイズ差に寄与し、回転カメラ運動は、モーションベクトルのサイズ及び方向の両方に寄与する。
【００８６】
図８Ａ及び図８Ｂは、単純な並進ベクトルモーションと比較して回転カメラ運動から得られる他のベクトルを示す。図８Ａ及び図８Ｂで同じ静止した物理的物体の２つの選択された特徴点ＳＦＰ４、ＳＦＰ５が物理的にカメラから同じ距離にあり、単純な並進カメラ運動の場合、ベクトルＡ及びベクトルＢは、それぞれＳＦＰ４及びＳＦＰ５のモーションベクトルであり、回転カメラ運動を含む場合、ベクトルＡ′及びベクトルＢ′は、それぞれＳＦＰ４及びＳＦＰ５のモーションベクトルであると仮定する。
【００８７】
単純な並進カメラ運動でベクトルＡ及びベクトルＢは、完全に同じモーションベクトルを有するが、ベクトルＡ′及びベクトルＢ′は、カメラから同じ距離を有するとしても、回転カメラモーションのために異なるサイズ及び方向を有する。
【００８８】
図８Ｃは、同じ静止した物体の２つの特徴点がカメラから異なる距離を有する場合、単純な並進ベクトルモーションから得られる他のベクトルを示す。同じ静止した物理的物体の２つの選択された特徴点ＳＦＰ４、ＳＦＰ７が物理的にカメラから異なる距離にあり、単純な並進カメラ運動の場合、ベクトルＡ及びベクトルＣ″は、それぞれＳＦＰ４及びＳＦＰ７のモーションベクトルであると仮定する。ＳＦＰ７がＳＦＰ４よりカメラに近いため、ＳＦＰ４及びＳＦＰ７が同じ静止した物体上のポイントであるのに、ＳＦＰ４及びＳＦＰ７のモーションベクトルのサイズは異なる（ベクトルＣ″は、ベクトルＡよりサイズが大きい）。
【００８９】
従って、ベクトル差のマージンは、モーションベクトルをグループ化する間に、同じ静止した物体の全ての特徴点のモーションベクトルを共にグループ化することができるベクトルサイズ及びベクトル方向（アングル）差の各要素に起因することを説明するために必要である。モーションベクトルグループを感知する通常の方法は、エラーマージン及び簡単なモーションベクトル差を使用してエラースレショルド値を定義することである。
【００９０】
モーションベクトル差（ΔＭ）のサイズは、グループ化決定のための基礎として使用される測定値であり、エラーマージン（ＴｈΔＭ）は、ΔＭ＝ＳＱＲＴ（（ｘａ−ｘｂ）２＋（ｙａ−ｙｂ）２）＜ＴｈΔＭによって決定される。ここで、Ａ＝（ｘａ，ｙａ）及びＢ＝（ｘｂ，ｙｂ）であり、エラーマージン（ＴｈΔＭ）は、モーションベクトル差（ΔＭ：正数）のサイズのためのエラースレショルド値である。
【００９１】
モーションベクトル差の方法のサイズは、あらゆる静止した物体の特徴点のモーションベクトルが同じ方向を有して特徴点が同じ並進カメラ運動によって全て定義されるために、カメラモーションが単純に並進（上、下、及び／又は左右）のみする時に適している。図８Ａと図８Ｃとを比べると、他の静止した特徴点のモーションベクトルは、単純な並進カメラ運動の場合にも、物体からカメラの異なる距離のために変わりうる。同じ静止した物体の特徴点のモーションベクトルのサイズ差は、一般的な通常のビデオ場面で相対的に小さく、サイズ差は、ベクトルサイズ差（｜Ａ｜−｜Ｂ｜）の、あるマージンを許容することによって容認され、モーションベクトル差（ΔＭ）の方法のサイズは、この場合に適している。
【００９２】
図９Ａは、モーションベクトル差（ΔＭ）のサイズが、２つの特徴点を共にグループ化するための適した基礎である２つのモーションベクトルＡ、Ｂの場合を示す。
【００９３】
モーションベクトル差（ΔＭ）は、単独で同じ場合のベクトルをグループ化するための適した基礎とならないこともある。
【００９４】
図９Ｂは、モーションベクトル差（ΔＭ′）のサイズが、２つの特徴点を共にグループ化するための適した基礎とならない２つのモーションベクトルＡ′、Ｂ′の場合を示す。
【００９５】
図９Ａ及び９Ｂにおいて、ベクトル対Ａ、Ｂ及びベクトル対Ａ′、Ｂ′は、ベクトル差が正確に同じサイズを有する（ΔＭ＝ΔＭ′）。各ベクトル対Ａ、Ｂ及びベクトル対Ａ′、Ｂ′は、エラーマージン（ＴｈΔＭ）を有するベクトル差（ΔＭ、ΔＭ′）のそれぞれのサイズをも有しうる。ベクトル対Ａ、Ｂは、ベクトル差（ΔＭ）のサイズに基づいて適切に共にグループ化されうる。しかし、ベクトル対Ａ′、Ｂ′は、ベクトル対Ａ′、Ｂ′が同じグループにグループ化されるためには、非常に大きなアングルの（方向の）差（例えば、ベクトル対Ａ、Ｂと比較して）を有する。
【００９６】
ベクトル差（ΔＭ）のサイズ方法自体は、２つの特徴点が非常に大きなアングルの（方向の）差を有するので、場合によって、２つの特徴点がエラーマージン（ＴｈΔＭ）内のベクトル差のサイズを有するモーションベクトルグループ化のために適さないこともある。カメラ曲線の回転成分は、ベクトル差のサイズ方法によって感知されない同じ方向を有し、同じか又は類似したサイズを有する静止した物体の１つ以上の特徴点を作り出す。従って、ベクトル差のサイズ方法は、誤ったジッタ補償及び／又は最適化されたビデオ圧縮、過度な計算に必要な電力や時間消費及び／又は静止しているか、動く物体の誤ったビデオ圧縮によるビデオ構造（ｖｉｄｅｏ  ａｒｔｉｆａｃｔｓ）が引き起こされる。
【００９７】
次いで、特徴点回路３０００の段階的ブロックマッチング検索ユニット７３０によって出力されたＳＦＰのモーションベクトルは、連続したビデオフレーム間の物体の感知される相対的な動きに基づいて、場面にある物体とＳＦＰのモーションベクトルとを連結させるサイズ及び方向によってグループ化される。
【００９８】
カメラの動きが、イメージセンサー／フォトダイオードアレイの面と殆ど垂直である軸に回転成分を有する場合、１つの物体（例えば、背景）のモーションベクトルの方向は同じではないこともある。ベクトルのサイズ及び方向の両方が、実際に静止していてカメラから同じ距離にあるとしても、背景の他の特徴点とは異なりうる。
【００９９】
グループ化決定のために、モーションベクトル差（ΔＭ）のサイズ及びエラーマージン（ＴｈΔＭ）のみを用いる代わりに、回転カメラモーションによって発生するモーションベクトル差の一定の量を感知して容認するため、モーションベクトルのサイズ比率及び正規化されたベクトル差を用いる。
【０１００】
ベクトルＡは、Ａ＝（ｘａ，ｙａ）であり、ベクトルＢは、Ｂ＝（ｘｂ，ｙｂ）である。
【０１０１】
第１グループ化決定基準は、サイズ比率（｜ｂ｜）に基づき、次の関係が成立する。
【０１０２】
｜ｂ｜２＝（｜Ｂ｜／｜Ａ｜）２＝（｜Ｂ｜２）／（｜Ａ｜２）＝（ｘｂ２＋ｙｂ２）／（ｘａ２＋ｙａ２）
第２グループ化決定基準は、アングル差の計算のために使われた正規化されたベクトル差である｜ａ−ｂ｜に基づき、次の関係が成立する。
｜ａ−ｂ｜２＝［｛（ｘａ−ｘｂ）２＋（ｙａ−ｙｂ）２｝／（ｘａ２＋ｙａ２）］
【０１０３】
第１グループ化決定は、絶対差（ａｂｓｏｌｕｔｅ  ｄｉｆｆｅｒｅｎｃｅ）（Ａ−Ｂ）よりはサイズ比率（｜Ｂ｜／｜Ａ｜）に基づくために、絶対エラーマージン（ＴｈΔＭ）の代わりに、サイズ比率スレショルド値（ｒｔｈ）を用いる。グループ化決定のために、サイズ比率スレショルド値の下位境界値（ｌｏｗｅｒ  ｂｏｕｎｄ）（ＭｒＬｔｈ）と上位境界値（ｕｐｐｅｒｂｏｕｎｄ）（ＭｒＵｔｈ）とを定義する。即ち、整理すると次の通りである。
ＭｒＬｔｈ２＜｜ｂ｜２＜ＭｒＵｔｈ２
ここで、ＭｒＬｔｈ＝（１−ｒｔｈ）、ＭｒＵｔｈ＝（１＋ｒｔｈ）、及び０＜ｒｔｈ＜１である。
例えば、サイズ比率スレショルド値が３０％とすれば、サイズ比率スレショルド値（ｒｔｈ）は０．３、下位境界値（ＭｒＬｔｈ）は０．７、上位境界値（ＭｒＵｔｈ）は１．３であるので、０．７２＜｜ｂ｜２＜１．３２の関係が成立する。
【０１０４】
ベクトルＡとベクトルＢとの間のアングル差は、スレショルド値θｔｈを超過せず、第２グループ化決定基準は、｜ａ−ｂ｜２＜Ｍａｔｈ２である。
ここで、Ｍａｔｈ２＝ＳＱＲＴ（１＋｜ｂ｜２−２＊｜ｂ｜＊ｃｏｓθｔｈ）であり、
｜ｂ｜＝ＳＱＲＴ｛（ｘｂ２＋ｙｂ２）／（ｘａ２＋ｙａ２）｝である。
【０１０５】
これら２つのグループ化決定基準に基づいた決定を用いるグループ化方法は、回転するカメラの動きがある場合でも最適化された動きベクトルグループ化を行うことができる。
【０１０６】
図１０は、図１Ａ〜図１Ｆに示したＤＩＳ方法における特徴点グループ化のために用いられるアングル差の間接的な測定のための正規化されたベクトル差の計算を示す３つのベクトル図を示し、図１０（ａ）を参照すると、ベクトルＡとベクトルＢとの間の差ベクトル（Ａ−Ｂ）は、水平にベクトル表示（Ａ−Ｂ）を示した。便宜上、図１０（ｃ）は、図１０（ａ）及び図１０（ｂ）より大きく示した。差ベクトル（Ａ−Ｂ）の絶対値（ΔＭ（Ａ−Ｂ））は、次のように計算される。
△Ｍ（Ａ−Ｂ）＝ＳＱＲＴ（（ｘａ−ｘｂ）２＋（ｙａ−ｙｂ）２）であり、
ここで、Ａ＝（ｘａ，ｙａ）、Ｂ＝（ｘｂ，ｙｂ）である。
【０１０７】
図１０（ｂ）を参照すると、正規化されたベクトルａは、ベクトルの絶対値｜Ａ｜によって除算されたベクトルＡとして定義され、従って、正規化されたベクトルａは、１のサイズ（ｍａｇｎｉｔｕｄｅ）を有する（図１０（ｃ）参照）。正規化されたベクトルｂは、ベクトルの絶対値｜Ａ｜によって除算されたベクトルＢとして定義される。｜Ａ｜及び｜Ｂ｜のサイズは、次の方程式によって定義される。
｜Ａ｜２＝（ｘａ２＋ｙａ２）、｜Ｂ｜２＝（ｘｂ２＋ｙｂ２）
【０１０８】
ｂ＝Ｂ／｜Ａ｜であることに注目し、従って、サイズ比率は、絶対値｜ｂ｜＝｜Ｂ｜／｜Ａ｜＝｜（Ｂ／｜Ａ｜）｜である。従って、｜ｂ｜は正規化されたベクトルｂのサイズであり、ベクトルＡのサイズ｜Ａ｜により除算されたベクトルＢによって正規化された（例えば、ｂ＝Ｂ／｜Ａ｜）。従って、サイズ比率｜ｂ｜＝ＳＱＲＴ｛（ｘｂ２＋ｙｂ２）／（ｘａ２＋ｙａ２）｝である。
【０１０９】
正規化されたベクトルａのサイズ｜ａ｜は１であるため、サイズ｜ｂ｜も、正規化されたベクトルｂのサイズ｜ｂ｜により除算された正規化されたベクトルＡのサイズ｜ａ｜との間のサイズ比率と同じである。従って、サイズ｜ｂ｜は、サイズ比率｜ｂ｜として参照される。サイズ比率｜ｂ｜は、ベクトルＡとベクトルＢとの間のアングル差θの関数ではない。
【０１１０】
最初のグループ化決定基準として、｜ｂ｜（ここで、｜ｂ｜＝｜Ａ｜／｜Ｂ｜）がサイズ比率スレショルド値の下限ＭｒＬｔｈ及び上限ＭｒＵｔｈ内にあるかをチェックする。従って、｜ｂ｜２＜ＭｒＬｔｈ２又は｜ｂ｜２＞ＭｒＵｔｈ２である場合、ベクトルＡ及びベクトルＢは、同じグループにありえない。しかし、ＭｒＬｔｈ２＜｜ｂ｜２＜ＭｒＵｔｈ２である場合、基準として正規化されたベクトル差｜ａ−ｂ｜の使用に基づく第２比較を行う。
【０１１１】
正規化されたベクトル差（ａ−ｂ）の絶対値サイズ｜（ａ−ｂ）｜は、次の方程式によって計算される。
｜ａ−ｂ｜２＝［｛（ｘａ−ｘｂ）２＋（ｙａ−ｙｂ）２｝／（ｘａ２＋ｙａ２）］
【０１１２】
正規化されたベクトル差（ａ−ｂ）は、図１０（ｃ）で示したように、絶対値サイズ｜（ａ−ｂ）｜を有し、その長さ｜ａ｜、｜ｂ｜、及び｜（ａ−ｂ）｜は、｜（ａ−ｂ）｜の反対側にあるベクトルのアングル差θを有する三角形を形成し、これは、｜（ａ−ｂ）｜もθの関数としてコサイン法則を用いることによって得られるということを意味する。コサイン法則は、他の側の長さで、三角形の知られていない側の長さと知られていない側の反対側のアングルとの間の数学的関係を定義する。正規化されたベクトル差（ａ−ｂ）のサイズ｜（ａ−ｂ）｜は、次のようなコサイン法則を用いることで得られる。
｜（ａ−ｂ）｜＝ＳＱＲＴ（１＋｜ｂ｜２−２＊｜ｂ｜＊ｃｏｓθ）
【０１１３】
従って、正規化されたベクトル差（ａ−ｂ）（図１０（ｃ）のアングル差θの対向側の三角形側）のサイズ｜（ａ−ｂ）｜の限界値として表わされたアングル限界値（ａｎｇｌｅ  ｔｈｒｅｓｈｏｌｄ）は、｜ｂ｜及びアングル差θの関数として計算され、アングル差θは、コサイン法則によって示される。従って、アングル差の限界値としてサイズ｜（ａ−ｂ）｜の限界値サイズＭａｔｈを定義することができ、ここで、Ｍａは、選択された限界値アングルθｔｈの関数である。従って、正規化されたベクトル差（ａ−ｂ）の計算されたサイズ｜（ａ−ｂ）｜の二乗とＭａｔｈの二乗とを比較することができる。従って、｜ａ−ｂ｜２は、ベクトルＡとベクトルＢとの間のアングル差が、それらが共にグループ化されるのに十分に小さいか否かを決定するためにＭａｔｈ２と比較される。
【０１１４】
Ｍａｔｈ２＝（１＋｜ｂ｜２−２＊｜ｂ｜＊ｃｏｓθｔｈと定義し、ここで、θｔｈは、グループ化決定の目的のための予め設定されたアングル限界値である（例えば、３０゜）。そして、｜ｂ｜＝｜（Ｂ／｜Ａ｜）｜＝ＳＱＲＴ｛（（ｘｂ２＋ｙｂ２）／（ｘａ２＋ｙａ２））｝である。
【０１１５】
｜ａ−ｂ｜２がＭａｔｈ２より小さい場合、同じグループにあり得るベクトルＡ及びベクトルＢを決定する。従って、｜ａ−ｂ｜２がＭａｔｈ２より小さい場合、適当な最後のグループ化決定は、同じグループにあるベクトルＡ及びベクトルＢである。
これにより、｜ａ−ｂ｜２がＭａｔｈ２より小さく、｜ｂ｜２（ここで、｜ｂ｜２＝（｜Ｂ｜／｜Ａ｜）２）がＭｒＬｔｈ２より大きく且つＭｒＵｔｈ２より小さい場合にのみ、ベクトルＡ及びベクトルＢは、同じグループになる。従って、Ｍａｔｈ２の正確な計算は、１つの二乗根（ｓｑｕａｒｅ  ｒｏｏｔ）演算を必要とし（例えば、｜ｂ｜を計算するために）、二乗根演算は、高価な計算であるか、大規模なハードウェア装置を必要とし、従って、二乗根演算の削除は重要である。出願人は、１±３０％（例えば、０．７≦｜ｂ｜≦１．３）と同じ｜ｂ｜のための優れたグループ化結果を提供し、３０゜のベクトルエラー（ベクトル差）アングル（例えば、−３０°≦θ≦＋３０°）内のＭａｔｈのための近似化を創案（例えば、Ｍａｔｈ＝０．５）した。従って、第２グループ化基準は、｜ａ−ｂ｜２＜０．５２になる。
【０１１６】
アングル差θ、サイズ比率｜ｂ｜、及び正規化された差｜ａ−ｂ｜の間の関係をプロット（ｐｌｏｔ）した場合、図１２のグラフが得られる。
【０１１７】
図１２は、アングル差θ（０〜９０゜の間）の関数として、正規化されたベクトル差（ａ−ｂ）のサイズ｜（ａ−ｂ）｜に対する正規化されたベクトル差（ａ−ｂ）のサイズ比率｜ｂ｜のグラフであり、これは、図１１のグループ化アルゴリズムの決定段階ｄＳ１１４０で使用するための効用のある近似化の効用可能性（ａｖａｉｌａｂｉｌｉｔｙ  ｏｆ  ａｎ  ａｐｐｒｏｘｉｍａｔｉｏｎ）を示す。
【０１１８】
図１２の矩形領域の境界によって示すように、実験によって、一般的な映像（ｖｉｄｅｏ）は、１±３０％より大きなサイズ比率又は３０゜より大きなアングルに至るアングル差θと共に優れたグループ化結果を提供する。この経験に基づいた範囲は、図１２のグラフに示したように、０〜０．５の間の正規化されたベクトル差の近似化のために効率的である。
【０１１９】
近似化（ａｐｐｒｏｘｉｍａｔｉｏｎ）を使用して、ＳＱＲＴ（１＋｜ｂ｜２−２＊｜ｂ｜＊ｃｏｓθ）は、｜ｂ｜に関係なく、０．５として近似化され、計算的な負担を減らしうる。従って、この近似化を使用して、第２グループ化決定基準は、｜ａ−ｂ｜２＜０．５２になる。
【０１２０】
図１１は、本発明の一実施形態によるグループ化過程を示すフローチャートである。グループ化過程１１００は、図１Ａ〜図１Ｆに示したＤＩＳ方法の図１Ｄのベクトルグループ化段階を実行するための選択された特徴点（図１Ａ及び図２Ａのイメージフレーム参照）の動作（ｍｏｔｉｏｎ）ベクトル間のアングル差の間接的な測定のための正規化されたベクトル差を含む２つの基準を使用する。グループ化アルゴリズム１１００は（ＳＤ１１２０段階での）、サイズ比率グループ化決定基準及び（ＳＤ１１４０段階での）ベクトル差グループ化決定基準を含む。外部的にグループ化アルゴリズム１１００で作動するペアリングアルゴリズム（Ｓ１１０４、Ｓ１１０６、Ｓ１１５２、ｄＳ１１５０、及びＳ１１５４）は、既にその対にならずにグループ化アルゴリズム１１００から完全に排除される他のものなどと共に対になったその特徴点（動きベクトル）の経路（ｔｒａｃｋ）を保持する。ペアリングアルゴリズムは、グループ化アルゴリズム１１００への入力として一対のＳＦＰ動きベクトルＡ及びＢを提供する（Ｓ１１０４、Ｓ１１０６）。初期化段階ｉＳ１１０２で、サイズ比率マージン（例えば、ＭｒＬｔｈ２及びＭｒＵｔｈ２）及びアングルマージンは、外部回路から受信されてグループ化アルゴリズム１１００に提供される。
【０１２１】
グループ化アルゴリズム１１００は、少なくとも次の段階Ｓ１１１６、ｄＳ１１２０、及びｄＳ１１４０で、次の段階の計算のためのこれらの計算された値を使用するための受信されたベクトルＢ（Ｓ１１１２及びＳ１１１４段階）に基づいた受信されたベクトルＡ及び｜Ｂ｜２に基づいた｜Ａ｜２を計算する。従って、受信されたベクトルＢが（決定段階ｄＳ１１２０のＹＥＳ分枝、又は決定段階ｄＳ１１４０のＮＯ分枝によって）受信されたベクトルＡと一緒のグループ化から排除された場合、ペアリングアルゴリズムは、新たなベクトルＢ（Ｓ１１５２段階）及び新たなベクトルＢに基づいた｜Ｂ｜２の新たな値を計算する（Ｓ１１１４段階）グループ化アルゴリズムを割当てる（ａｓｓｉｇｎ）。しかし、同じベクトルＡの比較は、新たなベクトルＢと共に続けられるため、現在のベクトルＡの｜Ａ｜２の計算された値は（Ｓ１１１２段階）、同時にアップデートされる必要はない。従って、グループ化アルゴリズム１１００の実行に採択されたハードウェア又はソフトウェアは、ベクトルＡ及びＢの中で１つのみが一回で変わる限り、それらの値の１つを使う複数の比較を効率的に行うために、１つ又はそれ以上の瞬間値（ｉｎｓｔａｎｃｅｓ  ｏｆ  ｖａｌｕｅ）｜Ｂ｜２及び｜Ａ｜２を分離して保存するように構成される。
【０１２２】
グループ化アルゴリズム１１００は、次に（Ｓ１１１２及びＳ１１１４から）｜Ａ｜２及び｜Ｂ｜２を使用するサイズ比率｜ｂ｜２及び｜ａ−ｂ｜２（Ｓ１１１６）を計算する。第１（サイズ比率）グループ化決定基準は、決定段階ｄＳ１１２０に適用される。決定段階ｄＳ１１２０でサイズ比率の二乗｜ｂ｜２は（ｉＳ１１０２段階から）、サイズ比率マージンと比較される。（｜Ａ｜／｜Ｂ｜）２＜ＭｒＵｔｈ２又は（｜Ａ｜／｜Ｂ｜）２＞ＭｒＵｔｈ２の場合（決定段階ｄＳ１１２０のＮＯ分枝）、現在のベクトルＡは、現在のベクトルＢとグループにならず、現在のベクトルＢとの比較は終わらず、新たなベクトルＢが選択される（Ｓ１１５２段階）。（｜Ａ｜／｜Ｂ｜）２がＭｒＬｔｈ及びＭｒＵｔｈの間にある場合（決定段階ｄＳ１１２０のＹＥＳ分枝）、現在のベクトルＡは、現在のベクトルＢと共にグループ化され、第２グループ化決定基準が適用される（決定段階ｄＳ１１４０）。｜ｂ｜が所定の範囲内（例えば、｜ｂ｜２の値に基づいた）にあり、アングル差θが所定の範囲内（決定段階ｄＳ１１３０のＹＥＳ分枝）にある場合、正規化された差ベクトル（ａ−ｂ）のサイズＭａｔｈは近似化される（例えば、Ｍａｔｈ２＝０．５２として）、そうでない場合（決定段階ｄＳ１１３０のＮＯ分枝）、正規化された差ベクトル（ａ−ｂ）のサイズＭａｔｈは計算される（Ｓ１１３２）。
【０１２３】
次に、正規化された差ベクトル（ａ−ｂ）の近似化されたか又は計算されたＭａｔｈは、決定段階ｄＳ１１４０の第２（正規化されたベクトル差）グループ化決定基準で使用される。決定段階ｄＳ１１４０で、Ｍａｔｈの二乗（Ｍａｔｈ２）は、（｜ａ−ｂ｜）２と比較されるか及び／又は（ｉＳ１１０２段階から）アングルマージンと比較される。（｜ａ−ｂ｜）２がＭａｔｈ２より小さい場合（決定段階ｄＳ１１４０のＹＥＳ分枝）、現在のベクトルＡは、現在のベクトルＢと共にグループ化される（Ｓ１１４２）。（｜ａ−ｂ｜）２がＭａｔｈ２より小さくない場合（決定段階ｄＳ１１４０のＮＯ分枝）、現在のベクトルＡは、現在のベクトルＢとグループ化されず、現在のベクトルＢとの比較は終わり、新たなベクトルＢが選択される（Ｓ１１５２段階）。
【０１２４】
一旦、現在のベクトルＡが全ての使用可能なグループ化候補（ｃａｎｄｉｄａｔｅｓ）ベクトルＢｓと比較され（決定段階ｄＳ１１５０のＹＥＳ分枝）、新たなベクトルＡが選択され、比較が残った（グループになっていない）グループ化候補ベクトルＢｓのために継続されるか、又は全てのベクトルがグループにならない場合、グループ化アルゴリズム１１００は、新たなフレームが進行する必要があるまで待つ。
【０１２５】
図１３は、図１１の特徴点グループ化アルゴリズムを行うグループ化アルゴリズム回路１３１０を含む特徴点グループ化回路のブロック図である。特徴点グループ化回路１３００は、サイズ比率限界値（ＭｒＬｔｈ＆ＭｒＵｔｈ）の基準（｜ｂ｜）に基づいた（図１１の決定段階ｄＳ１１２０の）第１グループ化決定を行うサイズ比率（｜ｂ｜）比較器１３２０、及び（アングル差の測定ために使われる）正規化されたベクトル差の基準に基づいた（図１１の決定段階ｄＳ１１４０）第２グループ化決定を行うベクトルアングル比較器１３３０を含む。本実施形態で具現されたベクトルアングル比較器１３３０は、正規化された差のサイズ（Ｍａｔｈ）計算器／推定器１３３２、及び正規化された差のサイズ（Ｍａｔｈ）比較器１３３４を含む。正規化された差のサイズ（Ｍａｔｈ）計算器／推定器１３３２は、図１１のｄＳ１１３０、Ｓ１１３２、及びＳ１１３４段階に関して上述したように生成するか、計算する。
【０１２６】
特徴点グループ化回路１３００は、図３の特徴点回路３０００と共にＲＡＭメモリ３５０を共有する。メモリ３５０のＳＦＰリスト３５２部分は、特徴点候補分類器３４０によって出力された選択された特徴点のリストを含む。特徴点グループ化回路１３００内にあるペアリングアルゴリズムコントローラ１３０２は、図１１のＳ１１５２、Ｓ１１５４、ｄＳ１１５６、及びｄＳ１１５０に関して上述したように、グループ化アルゴリズム回路１３１０における比較のためにＳＦＰリスト３５２にＤＭＡアクセスしてベクトルＡ及びベクトルＢを選択する。比較によって１つ又はそれ以上のベクトルのグループ（選択された特徴点のグループ）が生成された場合、ペアリングアルゴリズムコントローラ１３０２は、メモリ３５０のＦＰグループインベントリ３５４にグループ化されたベクトル又はそれらの技術的な（ｄｅｓｃｒｉｐｔｉｖｅ）リストを記録（ｗｒｉｔｅ）する。一実施形態によると、特徴点グループ化回路１３００とメモリ３５０は、単一集積回路で具現され、メモリ３５０から取り出されたデータは、Ｉ／Ｏピンを通じてチップの外部回路に出力される。他の実施形態によると、特徴点グループ化回路１３００、ＲＡＭメモリ３５０、及び特徴点回路３０００は、単一集積回路で具現されうる。上記実施形態は、当該技術分野に属する当業者が容易に実施可能であり、追加的なメモリ容量が必要な場合、他のＲＡＭメモリを集積回路の外部に付加させうることは自明である。
【０１２７】
特徴点グループ化回路１３００は、｜Ａ｜２計算器１３１２、｜Ｂ｜２計算器１３１４、及び｜ｂ｜２＆｜ａ−ｂ｜２計算器１３１６を更に含み、これは、それぞれ図１１のＳ１１１２、Ｓ１１１４、及びＳ１１１６段階を行う。
【０１２８】
上記開示した発明は、実施形態として考慮されたものであるので、制限されて解釈されてはならず、請求項は、発明の思想によって変形、添加、及び他の実施形態をも含むものと理解しなければならない。従って、請求項及びその均等物の最大限の解釈によって、発明の保護範囲は、法によって許容される最大の内容まで含まれなければならず、上述した詳細な説明によって制限的に解釈してはならない。
【符号の説明】
【０１２９】
３００    特徴点セレクター
３１０    第１ダウンサンプラー
３２０    タイル分散計算器
３３０    特徴点候補識別器
３４０    特徴点候補分類器
３５０    メモリ
３５２    ＳＦＰリスト
３５４    ＦＰグループインベントリ
７００    ＳＦＰモーションベクトル計算器
７１０    第２ダウンサンプラー
７２０    タイルベクトル計算器
７３０    階層的ブロックマッチング検索ユニット
１３００    特徴点グループ化回路
１３０２    ペアリングアルゴリズムコントローラ
１３１０    グループ化アルゴリズム回路
１３１２    ｜Ａ｜２計算器
１３１４    ｜Ｂ｜２計算器
１３１６    ｜ｂ｜２＆｜ａ−ｂ｜２計算器
１３２０    サイズ比率（｜ｂ｜）
１３３０    ベクトルアングル比較器
１３３２    正規化された差（Ｍａｔｈ）計算器／推定器
１３３４    正規化された差のサイズ比較器
３０００    特徴点回路
【図１Ａ】
0005933970.tif 000006
【図１Ｂ】
0005933970.tif 000007
【図１Ｃ】
0005933970.tif 000008
【図１Ｄ】
0005933970.tif 000009
【図１Ｅ】
0005933970.tif 000010
【図１Ｆ】
0005933970.tif 000011
【図２Ａ】
0005933970.tif 000012
【図２Ｂ】
0005933970.tif 000013
【図３】
0005933970.tif 000014
【図４Ａ】
0005933970.tif 000015
【図４Ｂ】
0005933970.tif 000016
【図５】
0005933970.tif 000017
【図６】
0005933970.tif 000018
【図７】
0005933970.tif 000019
【図８Ａ】
0005933970.tif 000020
【図８Ｂ】
0005933970.tif 000021
【図８Ｃ】
0005933970.tif 000022
【図９Ａ】
0005933970.tif 000023
【図９Ｂ】
0005933970.tif 000024
【図１０】
0005933970.tif 000025
【図１１】
0005933970.tif 000026
【図１２】
0005933970.tif 000027
【図１３】
0005933970.tif 000028