(57)【特許請求の範囲】
【請求項１】
現在画像内のブロックについて、基準画像内の複数の検索位置に対応する複数のエラーメトリック下限値を決定する段階と、
前記現在画像内の前記ブロックについて決定された複数のエラーメトリック下限値の最小値を下限値として有する制限された検索範囲を使用して分離しきい値を決定する段階と、
前記分離しきい値に基づいて、前記複数の検索位置から複数の候補位置を選択する段階と、
前記現在画像内の前記ブロックについて、前記複数の候補位置のうち１つを一致位置として特定する段階と、
前記現在画像内の前記ブロックおよび前記一致位置に基づき、動きベクトルを決定する段階と
を備える方法。
【請求項２】
前記分離しきい値を前記決定する段階において、前記複数の候補位置の数が、前記複数の検索位置よりも少ない予め定められた個数に近くなるように、前記分離しきい値を決定する、請求項１に記載の方法。
【請求項３】
前記分離しきい値を前記決定する段階において、二分探索アルゴリズムに基づいて前記分離しきい値を決定する、請求項１または請求項２に記載の方法。
【請求項４】
前記複数のエラーメトリック下限値はそれぞれ、サブサンプリングされた絶対差の総和（ＳＳＡＤ）値である請求項１から請求項３のいずれか１つに記載の方法。
【請求項５】
前記特定する段階は、
前記複数の候補位置について複数のエラーメトリックを算出する段階と、
前記複数のエラーメトリックのうち最小値を選択する段階と
を有する請求項１から請求項４のいずれか１つに記載の方法。
【請求項６】
前記複数の候補位置は、ずれがゼロの位置を含む請求項５に記載の方法。
【請求項７】
前記複数のエラーメトリックはそれぞれ、絶対差の総和（ＳＡＤ）値である請求項５または請求項６に記載の方法。
【請求項８】
前記動きベクトルに少なくとも基づいて前記現在画像をエンコードする段階をさらに備える請求項１から請求項７のいずれか１つに記載の方法。
【請求項９】
現在画像および基準画像の画素データを格納する格納媒体と、
前記現在画像内でブロックを選択するブロック選択モジュールと、
ベクトル算出モジュールと
を備え、
前記ベクトル算出モジュールは、
選択された前記ブロックについて、前記基準画像内の複数の検索位置に対応する複数のエラーメトリック下限値を決定し、
前記現在画像内の前記ブロックについて決定された複数のエラーメトリック下限値の最小値を下限値として有する制限された検索範囲を使用して分離しきい値を決定し、
前記分離しきい値に基づいて、前記複数の検索位置から複数の候補位置を選択し、
前記現在画像内の前記ブロックについて、前記複数の候補位置のうち１つを一致位置として特定し、
前記現在画像内の前記ブロックおよび前記一致位置に基づき、動きベクトルを決定する装置。
【請求項１０】
前記ベクトル算出モジュールは、前記複数の候補位置の数が、前記複数の検索位置よりも少ない予め定められた個数に近くなるように、前記分離しきい値を決定する、請求項９に記載の装置。
【請求項１１】
前記ベクトル算出モジュールは、二分探索アルゴリズムに基づいて前記分離しきい値を決定する、請求項９または請求項１０に記載の装置。
【請求項１２】
前記複数のエラーメトリック下限値はそれぞれ、サブサンプリングされた絶対差の総和（ＳＳＡＤ）値である請求項９から請求項１１のいずれか１つに記載の装置。
【請求項１３】
前記複数のエラーメトリックはそれぞれ、絶対差の総和（ＳＡＤ）値である請求項９から請求項１２のいずれか１つに記載の装置。
【請求項１４】
現在画像および基準画像の画素データを格納する格納媒体と、
前記現在画像をエンコードし、前記画像内のブロックについて動きベクトルを生成する動き推定モジュールを有するエンコーダと
を備え、
前記動き推定モジュールはベクトル算出モジュールを含み、
前記ベクトル算出モジュールは、
選択された前記ブロックについて、前記基準画像内の複数の検索位置に対応する複数のエラーメトリック下限値を決定し、
前記現在画像内の前記ブロックについて決定された複数のエラーメトリック下限値の最小値を下限値として有する制限された検索範囲を使用して分離しきい値を決定し、
前記分離しきい値に基づいて、前記複数の検索位置から複数の候補位置を選択し、
前記現在画像内の前記ブロックについて、前記複数の候補位置のうち１つを一致位置として特定し、
前記現在画像内の前記ブロックおよび前記一致位置に基づき、前記動きベクトルを決定する装置。
【請求項１５】
前記ベクトル算出モジュールは、前記複数の候補位置の数が、前記複数の検索位置よりも少ない予め定められた個数に近くなるように、前記分離しきい値を決定する、請求項１４に記載の装置。
【請求項１６】
前記ベクトル算出モジュールは、二分探索アルゴリズムに基づいて前記分離しきい値を決定する、請求項１４または請求項１５に記載の装置。
【請求項１７】
前記複数のエラーメトリック下限値はそれぞれ、サブサンプリングされた絶対差の総和（ＳＳＡＤ）値である請求項１４から請求項１６のいずれか１つに記載の装置。
【請求項１８】
前記複数のエラーメトリックはそれぞれ、絶対差の総和（ＳＡＤ）値である請求項１４から請求項１７のいずれか１つに記載の装置。
【請求項１９】
機械に、
現在画像内のブロックについて、基準画像内の複数の検索位置に対応する複数のエラーメトリック下限値を決定させ、
前記現在画像内の前記ブロックについて決定された複数のエラーメトリック下限値の最小値を下限値として有する制限された検索範囲を使用して分離しきい値を決定させ、
分離しきい値に基づいて、前記複数の検索位置から複数の候補位置を選択させ、
前記現在画像内の前記ブロックについて、前記複数の候補位置のうち１つを一致位置として特定させ、
前記現在画像内の前記ブロックおよび前記一致位置に基づき、動きベクトルを決定させるためのプログラム。
【請求項２０】
前記機械に、前記複数の候補位置の数が、前記複数の検索位置よりも少ない予め定められた個数に近くなるように、前記分離しきい値を決定させる、請求項１９に記載のプログラム。
【請求項２１】
前記機械に、二分探索アルゴリズムに基づいて前記分離しきい値を決定させる、請求項１９または請求項２０に記載のプログラム。
【請求項２２】
前記複数のエラーメトリック下限値はそれぞれ、サブサンプリングされた絶対差の総和（ＳＳＡＤ）値である請求項１９から請求項２１のいずれか１つに記載のプログラム。
【請求項２３】
前記複数のエラーメトリックはそれぞれ、絶対差の総和（ＳＡＤ）値である請求項１９から請求項２２のいずれか１つに記載のプログラム。
【請求項２４】
前記複数の候補位置は、ずれがゼロの位置を含む請求項１９から請求項２３のいずれか１つに記載のプログラム。
【発明の詳細な説明】
【背景技術】
【０００１】
ビデオ処理機能および画像処理機能を持つデバイスが多くなっている。例えば、多くの携帯可能デバイスおよび固定デバイスでは今日、ビデオ用の画像を撮像、表示、エンコード、および／または圧縮することが可能である。こういった機能は、デバイスのリソース、例えば、処理部およびメモリ部に大きな負荷をかけることが多い。
【０００２】
このため、デバイスは、ビデオエンコーディング等の処理を行なうと、他のタスクを実行できなくなったり、および／または、デバイスの電池寿命が短くなってしまったりする場合がある。したがって、上述したような処理を効率化する方法が必要とされている。
【図面の簡単な説明】
【０００３】
図面では、同様の参照番号は通常、同一の、同様の機能を持つ、および／または、同様の構造の構成要素を指す。ある構成要素が最初に図示される図面は、参照番号の最大桁を見ることで分かる。本発明は、添付図面を参照して説明する。添付図面は以下の通りである。
【図１】装置の一例を示す図である。
【図２】フレームの一例を示す図である。
【図３】処理の一例を示すフローチャートである。
【図４】実施例を示す図である。
【図５】処理の一例を示すフローチャートである。
【図６】画像エンコードモジュールに含められる実施例を示す図である。
【発明を実施するための形態】
【０００４】
実施形態によれば、動き推定方法が提供される。例えば、実施形態では、現在画像内のブロックについて複数のエラーメトリック下限値を決定するとしてよい。尚、エラーメトリック下限値はそれぞれ、基準画像における検索位置に対応する。分離しきい値に基づき、検索位置から複数の候補位置を特定するとしてよい。そして、候補位置から一致位置を特定する。一致位置に基づき、動きベクトルを決定する。
【０００５】
このような方法を用いることによって、演算効率を改善するとしてよい。
【０００６】
本明細書において「一実施形態」または「実施形態」と言う場合、当該実施形態に関連付けて説明した特定の特徴、構造、または、特性が少なくとも１つの実施形態に含まれていることを意味する。このため、「一実施形態において」または「実施形態において」という表現が本明細書において繰り返し用いられているとしても、全てが必ずしも同じ実施形態を指しているとは限らない。また、特定の特徴、構造、または、特性は、１以上の実施形態において適宜組み合わせるとしてよい。
【０００７】
図１は、本明細書に開示する方法を利用する装置１００の一例を示す図である。当該装置は、さまざまな構成要素を備えるとしてよい。例えば、図１は、画像ソース１０２および画像エンコードモジュール１０４を備える装置１００を示す図である。これらの構成要素は、ハードウェア、ソフトウェア、または、これらの任意の組み合わせで実現されるとしてよい。
【０００８】
画像ソース１０２は、画像エンコードモジュール１０４に画素値を供給する。具体的に説明すると、図１では、画素値が、１以上の画像を表す信号ストリーム１２２になっている様子を示している。このため、信号ストリーム１２２は、複数の画素値を含むフレームシーケンスまたはフィールドシーケンスを構成しているとしてよい。フレーム／フィールド（「画像」とも呼ぶ）はそれぞれ、特定の時点または期間に対応するとしてよい。実施形態によると、信号ストリーム１２２はデジタルストリームである。これに代えて、信号ストリーム１２２は、アナログストリームであってもよい。
【０００９】
実施形態によると、画像ソース１０２は、例えば、ビデオコンテンツおよび／または画像を格納する格納媒体（例えば、メモリ）を有するとしてよい。これに代えて、画像ソース１０４は、画像エンコードモジュール１０４に信号ストリーム１２２を供給する通信媒体を有するとしてもよい。このような通信媒体は、有線通信媒体または無線通信媒体であってよい。
【００１０】
別の代替例として、画像ソース１０２は、画像を撮像して対応する信号を生成する構成要素群を有するとしてよい。例えば、実施形態によると、画像ソース１０２は、光学系および画像センサを有するとしてよい。
【００１１】
光学系は、視野内の画像を画像センサ内の複数のセンサ素子に投影する１以上の光学デバイス（例えば、レンズ、ミラー等）を含むとしてよい。さらに、光学系は、光学デバイスの配置を制御する機構を含むとしてよい。例えば、このような機構は、集束動作、開口設定、ズーム動作、シャッター速度、実効焦点距離等を制御するとしてよい。しかし、実施形態は上記の例に限定されない。
【００１２】
画像センサは、センサ素子アレイ（例えば、相補型金属酸化膜半導体（ＣＭＯＳ）センサ、電荷結合素子（ＣＣＤ）センサ等）を含むとしてよい。センサ素子は、センサに入射した光に対応するアナログ強度信号（例えば、電圧）を生成するとしてよい。また、画像センサはさらに、アナログ強度信号をデジタル的にエンコードされた強度値に変換するアナログデジタルコンバータ（ＡＤＣ）を含むとしてよい。画像センサは、このようにして得られた値を信号ストリーム１２２で搬送するとしてよい。
【００１３】
画像エンコードモジュール１０４は、信号ストリーム１２２で搬送されてきた画像信号をエンコード（例えば、圧縮）して、エンコード信号１２４を生成する。このエンコードは、１以上の方法に応じて行なわれるとしてよい。例えば、画像エンコードモジュール１０４は、信号ストリーム１２２に本質的に存在する冗長性（例えば、空間的冗長性および／または時間的冗長性）を利用するさまざまな圧縮方法を用いるとしてよい。このような方法には、ブロック一致アルゴリズムが含まれるとしてよい。
【００１４】
ブロック一致アルゴリズム（ＢＭＡ）では、動きベクトル（本明細書では、「ずれベクトル」とも呼ぶ）を決定する。動きベクトルは、基準画像と現在画像との間での、あるブロックの水平方向および垂直方向のずれを推定するベクトルである。このような動きベクトルを決定する処理は、「動き推定」とも呼ばれる。したがって、図１には、動き推定モジュール１０６を含む画像エンコードモジュール１０４を図示している。
【００１５】
動き推定モジュール１０６は、画像またはフレーム内のブロック（例えば、マクロブロック）の動きベクトルを決定する。画像エンコードモジュール１０４は、決定された動きベクトルをエンコード信号１２４に含めるとしてよい。
【００１６】
実施形態によると、画像エンコードモジュール１０４は、例えば、１以上のＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅｓ  Ｅｘｐｅｒｔ  Ｇｒｏｕｐ）規格、例えば、ＭＰＥＧ２および／またはＭＰＥＧ４に準拠しているとしてよい。また、画像エンコードモジュール１０４は、国際電気通信連合（ＩＴＵ）の電気通信標準化部門（ＩＴＵ−Ｔ）が策定した１以上の規格に準拠しているとしてもよい。このような規格の例としては、Ｈ．２６１、Ｈ．２６３、および、Ｈ．２６４が挙げられる。しかし、実施形態は上述した例に限定されない。
【００１７】
上述したように、画像エンコードモジュール１０４は、信号ストリーム１２２からエンコード信号１２４を生成する。装置１００は、格納媒体（例えば、メモリ）にエンコード信号１２２を格納するとしてよい。装置１００はまた、エンコード信号１２４をデコードして出力（例えば、表示）するとしてよい。さらに、装置１００は、１以上のネットワーク（不図示）を介してリモートデバイスにエンコード信号１２４を送信するとしてよい。リモートデバイスは、受信すると、対応する画像を格納、デコード、および／または、出力（例えば、表示）するとしてよい。
【００１８】
装置１００は、ハンドヘルド装置または組み込みシステム等、さまざまなデバイスで実現されるとしてよい。デバイスの例を挙げると、無線携帯電話、ボイス・オーバー・インターネット・プロトコル（ＶｏＩＰ）電話、パーソナルコンピュータ（ＰＣ）、携帯情報端末（ＰＤＡ）、および、デジタルカメラがある。また、本システムはさらに、標準的な公衆電話交換回線網（ＰＳＴＮ）の電話線、デジタル総合サービス網（ＩＳＤＮ）の電話線、および／または、パケットネットワーク（例えば、ローカルエリアネットワーク（ＬＡＮ）インターネット等）を利用する固定電話ベースのビデオ電話でも実現され得る。しかし、実施形態は上述した例に限定されない。
【００１９】
さまざまな実施形態の処理を、以下の図面および例を参照しつつさらに説明する。図面の中には、ロジックフローを図示しているものもあるとしてよい。本明細書に含まれるロジックフロー図は特定のロジックフローを図示しているが、それは本明細書に記載する一般的な機能をどのように実現するかの一例を説明するためのものに過ぎないと考えられたい。また、所与のロジックフローは、明示していない限り、必ずしも図示した順序で実行する必要はない。また、所与のロジックフローは、ハードウェア素子、プロセッサで実行されるソフトウェア素子、または、これらの任意の組み合わせで実現されるとしてよい。実施形態はこれに限定されるものではない。
【００２０】
上述したように、実施形態では、エンコードされていない状態の画素データから、エンコードされた画像信号を生成するとしてよい。例えば、図１の画像エンコードモジュール１０４は、連続する画像間での時間的冗長性を利用するエンコード方法を採用するとしてよい。このため、現在画像の特徴は、先行する基準画像に対して相対的に表されるとしてよい。
【００２１】
例えば、現在画像または現在フレーム内のブロック（例えば、マクロブロック）に対応付けて動きベクトルを決定するエンコード方法を採用するとしてよい。具体的に説明すると、各動きベクトルは、先行する基準画像と現在画像との間での、対応するブロックのずれを表す。
【００２２】
絶対差の総和（Ｓｕｍ  ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅｓ：ＳＡＤ）は、動きベクトルを決定する基準（またはメトリック）として広く利用されている。このように広く利用されているのは、利用が簡単で単純なためである。ＳＡＤは、下記の数１にしたがって算出され得る。
【数１】
0005328936.tif 000002
【００２３】
数１において、ｍおよびｎはそれぞれ、現在ブロックと先行する基準ブロックとの間のｘ方向およびｙ方向のずれを表す。現在（ｉ，ｊ）は、現在画像の位置（ｉ，ｊ）での値を表す。基準（ｉ＋ｍ，ｊ＋ｎ）は、先行画像の位置ｉ＋ｍ，ｊ＋ｎでの値を表す。
【００２４】
したがって、数１で表されるＳＡＤは、特定のブロックについて一連の値を持つ。具体的には、数１は、ＳＡＤがずれベクトルに応じて決まる（ずれベクトルは、ｍおよびｎという成分を含む）ことを示している。
【００２５】
全検索ブロック一致アルゴリズム（ＦＳＢＭＡ）と呼ばれるアルゴリズムは、動き推定の実行を簡単にする。本アルゴリズムでは、検索領域（「検索ウィンドウ」とも呼ばれる）内のそれぞれのｍ、ｎについてＳＡＤを算出して、「最良」動きベクトルとしてＳＡＤが最小となるｍ、ｎの値を選択する。ＦＳＢＭＡは、演算コストが高いという問題がある。
【００２６】
しかし、演算コストがそこまで高くない方法もある。例えば、高速動き推定アルゴリズム（例えば、ひし形検索、ツリーステップ検索、および、４段階検索）では、基準フレームの検索領域内の一部のポイントのみを考慮するので、演算効率が高くなる。しかし、このような高速検索アルゴリズムでは、「極小値問題」と呼ばれる欠陥がある。この欠陥のために、「最良の最小」動きベクトルを得ることが出来ない可能性がある。
【００２７】
逐次消去（ｓｕｃｃｅｓｓｉｖｅ  ｅｌｉｍｉｎａｔｉｏｎ）アルゴリズムと呼ばれるアルゴリズムを用いることで、極小値問題は解決される。また、このアルゴリズムはソフトウェアでの実施が容易である。逐次消去アルゴリズムは、ＦＳＢＭＡよりも演算コストが低く、「最小限のエラー」で最良の最小動きベクトルを発見する。逐次消去アルゴリズムは、下記の数２に示す不等式に基づいている。
【数２】
0005328936.tif 000003
【００２８】
数２に示すように、ＳＳＡＤ（ｍ，ｎ）（サブサンプリングされたＳＡＤ関数）は、ＳＡＤ（ｍ，ｎ）の下限値を示す。また、所与のポイントについて、ＳＳＡＤ（ｍ，ｎ）が必要とする演算は、ＳＡＤ（ｍ，ｎ）よりも少ない。このため、逐次消去アルゴリズムは最初に、所与のポイントについてＳＳＡＤ（ｍ，ｎ）を算出する。算出したＳＳＡＤ（ｍ，ｎ）値が対応するＳＡＤ（ｍ，ｎ）値について所望の下限値を表していない場合（つまり、算出したＳＳＡＤ（ｍ，ｎ）値が現在知られている最小ＳＡＤ値以上である場合）、このポイントについてはより演算コストの高いＳＡＤ（ｍ，ｎ）の算出は省略する。
【００２９】
グローバル消去アルゴリズムと呼ばれるアルゴリズムは、ＳＡＤ（ｍ，ｎ）の低減値としてＳＳＡＤ（ｍ，ｎ）を採用するので、逐次消去アルゴリズムと同様である。例えば、グローバル消去アルゴリズムは、複数の検索位置（整数Ｐで指定）についてＳＳＡＤ（ｍ，ｎ）を算出して、下記の数３に示す方法でソートする。
【数３】
0005328936.tif 000004
【００３０】
この後、グローバル消去アルゴリズムは、ＳＳＡＤ値が最小となる最良のＭ個（ＭはＰよりも非常に少ない）の検索位置を見つける。これらの検索位置は、下記の数４では（ｍｉ，ｎｉ）と示される。
【数４】
0005328936.tif 000005
【００３１】
これらＭ個の検索位置が特定された後、グローバル消去アルゴリズムは、Ｍ個の検索位置のそれぞれについてＳＡＤ（ｍ，ｎ）を算出する。そして、Ｍ個の候補のうちでＳＡＤが最小値を取る位置を特定する。この位置によって、下記の数５に示す動きベクトルＭＶが明らかとなる。
【数５】
0005328936.tif 000006
【００３２】
グローバル消去アルゴリズムの大きな問題点は、検索領域内のＰ個の検索ポイント全てのＳＳＡＤ（ｍ，ｎ）値をソートする必要がある点である。このため、このアルゴリズムは演算コストが高くなり得る。
【００３３】
実施形態では、本明細書において二層整数アルゴリズムと呼ぶアルゴリズムを採用する。二層整数アルゴリズムでは、グローバル消去アルゴリズムと同様に、ＳＳＡＤ値とＳＡＤ値との間の相関関係を利用する。しかし、二層整数アルゴリズムでは、グローバル消去アルゴリズムとは違って、Ｐ個のポイントの全てについて求められたＳＳＡＤ値をソートする必要はない。この結果、演算効率が改善され得る。
【００３４】
二層整数アルゴリズムでは、複数のＳＳＡＤ値を第１群および第２群に分割するしきい値Ｔを特定する。第１群は、Ｔ以下のＳＳＡＤ（ｍ，ｎ）値を全て含む。第２群は、Ｔよりも大きいＳＳＡＤ（ｍ，ｎ）値を全て含む。
【００３５】
しきい値Ｔは、第１群に含まれる要素の数が所望の値Ｍに近くなるように設定されるとしてよい。このため、実施形態では、ＴはＭとして選択された値に応じて決まる。
【００３６】
二層整数アルゴリズムは、「最良の」動きベクトルを見つける成功率が高い。下記の数６は、第１の群（ｍｉ，ｎｉ）に含まれるポイントの基準を示す。また、数７は、第１の群に含まれるポイントの数とＭとの差がΔであることを示している。
【数６】
0005328936.tif 000007
【数７】
0005328936.tif 000008
【００３７】
Ｔを特定する方法の１つに、検索範囲を制限する方法がある。数８は、この制限された検索範囲は、下限値がＴｍｉｍで上限値がＴｍａｘであることを示している。
【数８】
0005328936.tif 000009
【００３８】
実施形態では、Ｔｍｉｎは全てのＳＳＡＤ値の最小値を選択し、Ｔｍａｘは全てのＳＳＡＤ値の平均値を選択するとしてよい。この選択は、下記の数９および数１０に表す。
【数９】
0005328936.tif 000010
【数１０】
0005328936.tif 000011
【００３９】
Ｔｍａｘの選択は、例えば、数１１に示すマルコフの不等式に基づいて行なわれるとしてよい。
【数１１】
0005328936.tif 000012
【００４０】
例えば、Ｍは全てのＰ個のポイントの１０％に等しくなるように選択されるとしてよい。全てのＰ個のＳＳＡＤ値を、離散一様分布を持つ正の確率変数Ｘとしてモデル化すると、マルコフの不等式を適用することによって（ａをＴで置換）、数１２および数１３で表す分析が行なわれる。この分析によって、全てのＰ個のポイントのＳＳＡＤ値の平均値がＴの上限値（つまり、Ｔｍａｘ）として適切であることが分かる。
【数１２】
0005328936.tif 000013
【数１３】
0005328936.tif 000014
【００４１】
実施形態では、ＴｍｉｎおよびＴｍａｘが特定されると、しきい値Ｔの最良値を決定するとしてよい。しきい値Ｔの最良値の決定では、二分探索アルゴリズムを利用するとしてよい。
【００４２】
実施形態では、ＳＡＤ値およびＳＳＡＤ値は、各画素値に基づいて決まるとしてよい。しかし、別の実施形態によると、ＳＡＤ値およびＳＳＡＤ値は、画素ブロックに対応する合計に基づいて決まるとしてよい。この方法の一例を図２に示す。
【００４３】
具体的に説明すると、図２は、現在フレーム２０２、基準フレーム２０４、処理後の基準フレーム２０６を示す図である。現在フレーム２０２は、マクロブロック２０８を含む。このマクロブロックは、現在フレーム２０２内に画定されている、横に１６個の画素、縦に１６個の画素（１６×１６）の領域を表している。
【００４４】
ＳＡＤ値およびＳＳＡＤ値を算出することを目的として、マクロブロック内の画素値を合成して、演算効率を高めるとしてよい。例えば、マクロブロック２０８内には４×４のサブブロックが複数ある。各サブブロックの画素値を合計して、マクロブロック２０８に対応する値を生成する。このため、マクロブロック２０８は、４×４でアレイ状に配置された値（つまり、各サブブロックの値）として表されるとしてよい。
【００４５】
この様子は、図２において、マクロブロック２０６を拡大した２２０で図示している。これによると、マクロブロック２０８は４×４のアレイ状に並べられた合計値として図示されている。各合計値（下記の数１４に示す）は、対応する４×４のサブブロックの総画素値である。
【数１４】
0005328936.tif 000015
【００４６】
このように、当該方法によれば、マクロブロック２０８のＳＳＡＤ値は下記の数１５に示すように算出するとしてよい。
【数１５】
0005328936.tif 000016
【００４７】
実施形態ではさらに、基準フレーム全体についてサブブロックの画素値を算出することによって、演算効率を改善するとしてよい。サブブロックの画素値の計算によって、基準フレームのサイズよりも、利用したサブブロックのサイズだけ大きくなる。例えば、図２は、高さがＨ＋４で幅がＷ＋４の拡大基準フレーム２０６を図示している。この拡大基準フレーム内では、動きベクトルを求める検索ウィンドウ２１０が画定されている。
【００４８】
図３は、ロジックフローの実施形態を示す図である。具体的には、図３には、本明細書に記載する１以上の実施形態で実行される処理を表すロジックフロー３００を示す。図３では特定の順序を図示しているが、順序は変更するとしてもよい。また、図示した処理は、並行に実行するとしてもよいし、および／または、順次実行するとしてもよく、さまざまに組み合わせるとしてよい。
【００４９】
図３に示すロジックフローでは、現在画像（フレーム）内のマクロブロックについて動きベクトルを推定する。動きベクトルは、基準画像（フレーム）に基づいて決まる。図３に示すように、ブロック３０２では、基準画像の全てのサブブロック（例えば、４×４のサブブロック）の合計値を算出する。
【００５０】
ブロック３０４では、現在画像においてマクロブロックを選択する。この選択に基づき、ブロック３０６では、ずれがゼロのＳＡＤ値を決定する。このＳＡＤ値を最小ＳＡＤ値に指定する。ブロック３０８で示すように、このＳＡＤ値が所定の終了しきい値未満の場合には、ブロック３１６の処理に進む。このＳＡＤ値が所定の終了しきい値以上の場合には、ブロック３１０に進む。
【００５１】
ブロック３１０では、複数のＳＳＡＤ値を算出する。例えば、採用した検索ウィンドウ内の全てのＳＳＡＤ値を算出することを含むとしてよい。
【００５２】
ブロック３１２において、分離しきい値を決定する。上述したように数６から数１３に基づきしきい値Ｔを決定することを含むとしてよい。
【００５３】
決定した分離しきい値に基づき、Ｍ個の検索位置を特定する。したがって、ブロック３１４では、これらの検索位置のそれぞれについてＳＡＤ値を算出する。ブロック３１６では、これらのＳＡＤ値（および、ブロック３０６で決定されたずれがゼロのＳＡＤ値）に基づき、最小ＳＡＤ値を更新する。
【００５４】
したがって、ブロック３１８において、選択されたマクロブロックについて動きベクトルを決定する。この動きベクトルは、最小ＳＡＤ値に対応する。
【００５５】
ブロック３２０において、現在画像内の全てのマクロブロックが選択されたか否かを判断する。選択されていない場合、ブロック３０４に戻って、別のマクロブロックを選択する。選択されている場合、ブロック３２２に進む。ブロック３２２において、次の画像（例えば、フレーム）を現在フレームとして選択する。そして、本明細書に記載する処理を再度実行するとしてよい。
【００５６】
図４は、実施例４００を示す図である。この実施例では、図３に示した方法のような動き推定方法を実行するとしてよい。したがって、実施例４００は、図１に示す画像エンコードモジュール１０４に含まれるとしてよい。
【００５７】
実施例４００は、さまざまな構成要素を含むとしてよい。例えば、図４では、格納媒体４０２、ブロック選択モジュール４０４、および、ベクトル算出モジュール４０６を含む実施例を図示している。これらの構成要素は、ハードウェア、ソフトウェア、または、これらの任意の組み合わせで実現されるとしてよい。
【００５８】
格納媒体４０２は、複数の画像またはフレームのデータを格納しているとしてよい。例えば、格納媒体４０２は、現在フレームの画素データおよび基準フレームの画素データを格納している。格納媒体４０２は、例えば、メモリおよび／またはその他の種類の有形格納デバイスを含むとしてよい。メモリおよびこのような格納デバイスの例は後述する。
【００５９】
ブロック選択モジュール４０４は、現在画像においてブロック（例えば、マクロブロック）を選択する。図４に示すように、この選択が行われた結果、選択指標４２０が格納媒体４０２に送信される。この選択指標に基づき、格納媒体４０２は、ベクトル算出モジュール４０６にデータを供給する。具体的には、図４には、格納媒体４０２が基準画像データ４２２、現在画像データ４２４、および現在画像データ４２６を供給している様子を示している。
【００６０】
ベクトル算出モジュール４０６は、ブロック選択モジュール４０２が選択したブロックについて、動きベクトル４３８を算出する。この算出は、本明細書に記載した技術に基づいて行なわれるとしてよい。図４に示すように、ベクトル算出モジュール４０４は、サブブロック合計モジュール４０８、ＳＳＡＤ算出モジュール４１０、ＳＡＤ算出モジュール４１２、しきい値決定モジュール４１４、最小値選択モジュール４１６、動きベクトル決定モジュール４１８を有する。上述したように、これらの構成要素は、ハードウェア、ソフトウェア、または、これらの任意の組み合わせで実現するとしてよい。
【００６１】
図４は、サブブロック合計モジュール４０８が格納媒体４０２から基準画像データ４２２を受信している様子を図示している。サブブロック合計モジュール４０８は、このデータに基づき、サブブロック合計値４２７を算出する。サブブロック合計値４２７は、ＳＳＡＤ算出モジュール４１０およびＳＡＤ算出モジュール４１２に送信される。
【００６２】
ＳＳＡＤ算出モジュール４１０は、サブブロック合計値４２７および現在画像データ４２４を受信する。ＳＳＡＤ算出モジュール４１０は、この情報に基づき、本明細書に記載した方法でＳＳＡＤ値４２８を算出する。算出されたＳＳＡＤ値は、検索ウィンドウ内のずれに対応するとしてよい。図４に示すように、ＳＳＡＤ算出モジュール４１０は、しきい値決定モジュール４１４にＳＳＡＤ値４２８を送信する。
【００６３】
しきい値決定モジュール４１４は、この情報を受信すると、ＳＳＡＤ値について分離しきい値を決定する。例えば、しきい値決定モジュール４１４は、数６から数１３に基づき上述したようにＴを決定するとしてよい。この決定結果に基づき、しきい値決定モジュール４１４は、ＳＳＡＤ算出モジュール４１０にしきい値４３０を返す。
【００６４】
ＳＳＡＤ算出モジュール４１０は、このしきい値に応じて、ＳＡＤ算出モジュール４３０にずれ指標４３２を送信する。この指標は、しきい値４３０を満たすＳＳＡＤ値に対応する。このため、ＳＳＡＤ算出モジュール４１０は、ＳＡＤ算出モジュール４１２に（Ｍ±Δ）個の指標を送信するとしてよい。
【００６５】
図４は、ＳＡＤ算出モジュール４１２が基準画像データ４２２および現在画像データ４２６を受信するものと図示している。この情報に基づき、ＳＡＤ算出モジュール４１２は、ずれ指標４３２のそれぞれについて、ＳＡＤ値を算出する。また、図３を参照して上述したように、ＳＡＤ算出モジュール４１２は、ずれがゼロのＳＡＤ値を算出するとしてよい。この算出結果は、ＳＡＤ値４３４として最小値選択モジュール４１６に送信される。
【００６６】
最小値選択モジュール４１６は、ＳＡＤ値４３４をソートして、最小ＳＡＤ値を特定する。これに基づき、最小値選択モジュール４１６は、最小ＳＡＤ値に対応するずれの指標４３６を生成する。図４に示すように、この指標は動きベクトル決定モジュール４１８に送信される。動きベクトル決定モジュール４１８は、指標４３６に基づき、動きベクトル４３８を決定する。
【００６７】
動き推定を実行する方法を上述した。図５は、上記の方法の特徴を示す別のフローチャートである。具体的には、図５には、本明細書に記載する１以上の実施形態で実行される処理を表すロジックフロー５００を示す。図５では特定の順序を図示しているが、順序は変更するとしてもよい。また、図示した処理は、並行に実行するとしてもよいし、および／または、順次実行するとしてもよく、さまざまに組み合わせるとしてよい。
【００６８】
ブロック５０２において、現在画像内のブロックについて、複数のエラーメトリック下限値（例えば、ＳＳＡＤ値）を算出する。各エラーメトリック下限値は、基準画像内の検索位置に対応する。
【００６９】
ブロック５０４において、複数の検索位置から複数の候補位置を選択する。この選択は、数６から数１３を参照して上述した分離しきい値、例えばＴに基づいて行われるとしてよい。したがって、実施形態では、ブロック５０２で算出されたエラーメトリック下限値に基づき分離しきい値を決定するとしてよい。また、候補位置は、（例えば、図３のブロック３０６を参照して説明したように）ずれがゼロの位置を含むとしてよい。
【００７０】
候補位置の中から、ブロック５０６において、一致位置を特定する。一致位置の特定では、各候補位置についてエラーメトリック値（例えば、ＳＡＤ値）を決定して、最も小さいエラーメトリック値を特定するとしてよい。
【００７１】
ブロック５０８において、現在画像内のブロックおよび一致ブロックに基づき、動きベクトルを決定する。
【００７２】
上記の処理は、現在画像内の複数のブロックについて実行されるとしてよい。さらに、１以上のブロックについて動きベクトル（上述の方法で生成されたもの）を持つエンコード画像が生成されるとしてよい。
【００７３】
上述したように、本明細書で説明する方法は、画像エンコーディング／ビデオエンコーディングの分野で利用されるとしてよい。一例として、図１は画像エンコードモジュール１０４を図示している。
【００７４】
図６は、画像エンコードモジュール１０４内に含まれる実施例６００を示す図である。この実施例は、エンコーダ６０２、フレーム格納モジュール６０４およびパラメータ設定モジュール６０７等、さまざまな構成要素を備えるとしてよい。しかし、実施形態はこれらの構成要素に限定されない。
【００７５】
エンコーダ６０２は、ハイブリッド変換を利用する動き補償エンコーディング方式を利用するとしてよい。しかし、実施形態はこの例に限定されない。このエンコーディング方式では、空間的冗長性および時間的冗長性を利用して、画像を表現するのに必要なデータ量を小さくするとしてよい。例えば、エンコーダ６０２は、１以上のＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅｓ  Ｅｘｐｅｒｔ  Ｇｒｏｕｐ）規格、例えば、ＭＰＥＧ−２およびＭＰＥＧ−４に準拠しているエンコーダであってよい。また、エンコーダ６０２は、国際電気通信連合（ＩＴＵ）の電気通信標準化部門（ＩＴＵ−Ｔ）が策定した１以上の規格に準拠しているエンコーダであってもよい。この規格の例には、Ｈ．２６１、Ｈ２６３、およびＨ．２６４が含まれる。
【００７６】
図６によると、エンコーダ６０２は転送部６０５および再構成部６０６を有する。転送部６０５は、圧縮されていない状態の画像情報を受信して、この情報をエンコード（例えば、圧縮）された状態で出力する。しかし、転送部６０５は、エンコーディングに利用される予測情報の供給については、再構成部６０６に依存している。
【００７７】
フレーム格納モジュール６０４は、フレーム等の画像信号を格納する。フレームは、例えば、画像センサ１０４等の画像センサから受信するとしてよい。また、図４を参照しつつ説明すると、フレーム格納モジュール２０４は、格納媒体４０２の特徴を提供するとしてよい。さらに、フレーム格納モジュール６０４は、エンコーダ６０２から受信する再構成フレームを格納する。したがって、フレーム格納モジュール６０４は、メモリ等の格納媒体を含むとしてよい。格納媒体の例は後述する。
【００７８】
エンコーダ６０２の説明に戻ると、図６は、転送部６０５が図１に示した動き推定モジュール１０６を含むことを示している。また、転送部２０５は、合成（例えば、減算）ノード６１０、転送変換モジュール６１２、量子化モジュール６１４、エンコードモジュール６１６、および、フレーム内予測選択モジュール６１８を有するとしてよい。また、図６によると、再構成部６０６は、動き補償モジュール６２０、フレーム内予測モジュール６２２、ルーティングモジュール６２４、逆量子化モジュール６２６、逆変換モジュール６２８、合成（例えば、加算）ノード６３０、および、ループ内ブロック解除フィルタ６３２を有するとしてよい。
【００７９】
図６によると、フレーム格納モジュール６０４は転送部６０５に対して現在フレーム６５０（Ｆｎと図示）を提示している。フレーム格納モジュール６０４はさらに、転送部６０５に基準フレーム６５２（図６にはＦ'ｎ−１と図示）も提示している。しかし、これに代えて、複数の基準フレームを提示するとしてもよい。エンコーダ６０２は、これらのフレームをマクロブロック単位、例えば、１６×１６の画像画素領域の単位で処理する（しかし、フレーム間予測エンコーディングの場合、基準フレームの処理領域はサイズが可変であるとしてよい）。例えば、図６は現在フレームＦｎに対応するマクロブロックＢｎを図示している。
【００８０】
エンコーダ６０２は、各ブロックをフレーム内予測モードまたはフレーム間予測モードでエンコードするとしてよい。各予測モードでは、図６においてＰとして図示している予測ブロックを利用する。また、各予測モードにおいて、予測ブロックＰは、基準として用いられる再構成フレームに基づいて生成される。
【００８１】
フレーム内予測モードにおいて、モジュール６２２は、既にエンコード、デコード、および、再構成が実行された現在フレームｎ内の複数のサンプルから予測ブロックＰｉｎｔｒａを形成する。このサンプルは、図６において、ｕＦ'ｎとして図示されている。フレーム内予測は、さまざまなモードにしたがって実行され得る。このため、モジュール６１８は、Ｆｎ内のブロック毎に１つのモードを選択する。この選択結果に基づいて、フレーム内予測モジュール６２２は、予測ブロックＰｉｎｔｒａを生成する。
【００８２】
フレーム間予測モードでは、モジュール６２０が、１以上の基準フレームに基づき動き補償予測技術を適用して予測ブロックＰｉｎｔｅｒを形成する。例えば、図６は、既にエンコードおよび再構成が実行されているフレームＦ'ｎ−１である基準フレーム６５２を図示している。しかし、エンコードおよび再構成が実行されたフレームを２つ以上、基準フレームとして利用するとしてもよい。
【００８３】
フレーム間予測モードでは、動き推定モジュール６０８および動き補償モジュール６２０を利用する。動き推定モジュール６０８は、現在フレームＦｎ内の１以上のブロックについて動きベクトルを推定する。動きベクトルは、基準フレームＦ'ｎ−１内の対応するブロックに基づいて推定される。実施形態によると、動き推定モジュール１０６は、図４を参照しつつ上述した方法で実現されるとしてよい。しかし、上述したように、フレーム格納モジュール２０４は、これに代えて、格納媒体４０２の特徴を提供するとしてもよい。
【００８４】
フレームＦｎ内のブロック毎に、動き補償モジュール６２０は、基準フレーム内の対応するブロックに基づいて予測ブロックＰｉｎｔｅｒを生成する。この対応するブロックは、動き推定モジュール６０８によって推定された動きベクトルに基づき決定される。
【００８５】
図６に示すように、ルーティングモジュール６２４は、予測ブロックＰとしてＰｉｎｔｅｒまたはＰｉｎｔｒａのいずれか一方を選択する。この選択は、フレームＦｎおよび１以上のその他のフレームの特徴に基づいて行なわれるとしてよい。そして、合成ノード６１０は、現在マクロブロックＢｎ（現在フレームＦｎ内のブロック）と予測マクロブロックＰとの間の差分を算出する。この結果、残余マクロブロックまたは差分マクロブロックＤｎが生成される。転送変換モジュール６１２は、Ｄｎを（例えば、４×４のブロック変換を利用して）一連の変換係数に変換する。そして、変換係数は、量子化モジュール６１４によって、量子化された係数Ｘに量子化される。量子化された係数はエンコードモジュール６１６に送信される。エンコードモジュール６１６は、量子化された係数を並び替えてエントロピーエンコードを実行するとしてよい。
【００８６】
この結果、エンコードモジュール６１６は、マクロブロックＢｎについて圧縮情報ストリーム６５８を出力する。図１の場合、圧縮情報ストリーム６５８は、エンコード信号１２４に含められているとしてよい。圧縮情報ストリーム６５８は、エンコードされた係数およびマクロブロックをデコードするためのサイド情報を含むとしてよい。サイド情報の例を挙げると、マクロブロック予測モード、量子化ステップサイズ（ｑｕａｎｔｉｚｅｒ  ｓｔｅｐ  ｓｉｚｅ）、マクロブロックに対してどのように動き補償が行なわれたかを説明する動きベクトル情報等が含まれるとしてよい。ストリーム６５８は、さまざまな方法で処理するとしてよい。例えば、情報ストリーム６５８は、遠隔デバイスに送信されるか、および／または、格納媒体に格納されるとしてよい。
【００８７】
上述するように、再構成部６０６は、動き補償モジュール６２０、フレーム内予測モジュール６２２、ルーティングモジュール６２４、逆量子化モジュール６２６、逆変換モジュール６２８、合成ノード６３０、および、ブロック解除フィルタ６３２を有するとしてよい。
【００８８】
逆量子化モジュール６２６は、量子化されたマクロブロック係数Ｘを量子化モジュール６１４から受信して、再スケーリングする。再スケーリングされた係数は、逆変換モジュール６２８に送信される。逆変換モジュール６２８は、受信した係数に逆変換（例えば、４×４のブロック逆変換）を実行して、差分マクロブロックＤｎ'を取得する。Ｄｎ'は、元々の差分マクロブロックＤｎとは同一でない場合がある。これは、量子化モジュール６１４での処理によって歪みが入ってしまうためである。
【００８９】
図６によると、差分マクロブロックＤｎ'と予測マクロブロックＰとを合成（例えば、加算）して、再構成マクロブロックｕＢ'ｎを生成する。この再構成マクロブロックは、元のマクロブロックに歪みが発生したものである。この歪みを小さくするべく、ブロック解除フィルタ６３２を元のマクロブロックに適用する。また、ブロック解除フィルタ６３２は、複数のマクロブロックから１つの再構成フレーム６５４（Ｆ'ｎと図示する）を再構成する。
【００９０】
本明細書で説明したように、さまざまな実施形態は、ハードウェア素子、ソフトウェア素子、または、これらの任意の組み合わせで実現するとしてよい。ハードウェア素子の例を挙げると、プロセッサ、マイクロプロセッサ、回路、回路素子（例えば、トランジスタ、抵抗器、コンデンサ、インダクタ等）、集積回路、特定用途向け集積回路（ＡＳＩＣ）、プログラマブルロジックデバイス（ＰＬＤ）、デジタルシグナルプロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ロジックゲート、レジスタ、半導体デバイス、チップ、マイクロチップ、チップセット等が含まれるとしてよい。
【００９１】
ソフトウェアの例を挙げると、ソフトウェアコンポーネント、プログラム、アプリケーション、コンピュータプログラム、アプリケーションプログラム、システムプログラム、マシンプログラム、オペレーティングシステムソフトウェア、ミドルウェア、ファームウェア、ソフトウェアモジュール、ルーチン、サブルーチン、関数、方法、プロシージャ、ソフトウェアインターフェース、アプリケーションプログラムインターフェース（ＡＰＩ）、命令群、コンピューティングコード、コンピュータコード、コードセグメント、コンピュータコードセグメント、ワード、値、シンボル、または、これらの任意の組み合わせが含まれるとしてよい。
【００９２】
一部の実施形態は、例えば、命令または命令群を格納している機械可読媒体または機械可読物品を用いて実現されるとしてよい。命令または命令群を機械で実行すると、機械は、実施形態に係る方法および／または処理を実行するとしてよい。機械としては、例えば、任意の適切な処理プラットフォーム、コンピューティングプラットフォーム、コンピューティングデバイス、処理デバイス、コンピューティングシステム、処理システム、コンピュータ、プロセッサ等が含まれるとしてよく、ハードウェアおよび／またはソフトウェアを適宜組み合わせることで実現するとしてよい。
【００９３】
機械可読媒体または機械可読物品は、例えば、任意の適切な種類のメモリユニット、メモリデバイス、メモリ物品、メモリ媒体、格納デバイス、格納物品、格納媒体、および／または、格納ユニット、例えば、メモリ、取り外し可能または取り外し不可能な媒体、消去可能または消去不可能な媒体、書き込み可能または書き換え可能な媒体、デジタル媒体またはアナログ媒体、ハードディスク、フロッピー（登録商標）ディスク、コンパクトディスクリードオンリーメモリ（ＣＤ−ＲＯＭ）、コンパクトディスクリコーダブル（ＣＤ−Ｒ）、コンパクトディスクリライタブル（ＣＤ−ＲＷ）、光ディスク、磁気媒体、光磁気媒体、取り外し可能なメモリカードまたはメモリディスク、さまざまな種類のデジタルバーサティルディスク（ＤＶＤ）、テープ、カセット等を含むとしてよい。命令は、任意の適切な種類のコードを含むとしてよく、例えば、ソースコード、コンパイラ型コード、インタプリタ型コード、実行コード、静的コード、動的コード、暗号化コード等であり、任意の適切な高級プログラミング言語、低級プログラミング言語、オブジェクト指向型プログラミング言語、ビジュアルプログラミング言語、コンパイラ型プログラミング言語、および／または、インタプリタ型プログラミング言語を用いて実現するとしてよい。
【００９４】
本発明のさまざまな実施形態を上述したが、限定ではなく例示を目的として記載されてものであると理解されたい。
【００９５】
例えば、本明細書に記載した方法は、ＳＳＡＤ値およびＳＡＤ値を利用することに限定されない。例えば、他のエラーメトリック下限値およびエラーメトリックを利用するとしてよい。また、実施形態は、１６×１６のマクロブロックまたは４×４のサブブロックを利用することに限定されない。さらに、実施形態は、分離しきい値を決定する際に（マルコフの不等式に基づく方法以外の）さまざまな方法を利用するとしてよい。
【００９６】
したがって、本明細書の意図および範囲から逸脱することなく、実施形態の形式および詳細をさまざまな点で変更し得ることは当業者には明らかである。このように、本発明の範囲は、上述した実施形態例のいずれにも限定されるべきではなく、請求項およびその均等物によってのみ定義されるべきである。
【図１】
0005328936.tif 000017
【図２】
0005328936.tif 000018
【図３】
0005328936.tif 000019
【図４】
0005328936.tif 000020
【図５】
0005328936.tif 000021
【図６】
0005328936.tif 000022