(57)【要約】      （修正有）【課題】探索効率を向上させるための改良式ダイアモンドサーチ動き推定方法を提供する。【解決手段】第一画面に含まれる予定ブロックに基づいて、該第一画面と時間的に近い第二画面に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定する改良式ダイアモンドサーチ動き推定方法において、前記第二画面にある原則一つのブロックを選択して探索基点とし、該探索基点を中心とするソリット菱形の領域を最初の探索領域とし、前記探索基点から順次遠い位置に前記予定ブロックとのマッチングブロックを探索して前記動きベクトルを推定し、さらに、中空菱形の探索パターンを利用して、最初の探索領域以外での最適動きベクトルを迅速サーチすることを特徴とする改良式ダイアモンドサーチ動き推定方法。動きベクトルは一般的に放射状に分配されるので、この存在確率が距離の増加によって迅速に下降する。【選択図】図５
2006270958.tif 000002
【特許請求の範囲】
【請求項１】
第一画面に含まれる予定ブロックに基づいて、該第一画面と時間的に近い第二画面に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定する改良式ダイアモンドサーチ動き推定方法において、
前記第二画面に一つのブロックを選択して探索基点とし、該探索基点を中心とするソリッド菱形（ｓｏｌｉｄ  ｒｈｏｍｂｕｓ）の領域を最初の探索領域とし、該探索基点から順次遠い位置にマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定することを特徴とする改良式ダイアモンドサーチ動き推定方法。
【請求項２】
前記ソリット菱形の領域が、前記探索基点及び該探索基点の周り四点から成る小菱形領域を含むことを特徴とする請求項１記載の動き推定方法。
【請求項３】
前記ソリット菱形の領域が、更に前記小菱形領域の周り八点を含むことを特徴とする請求項２記載の動き推定方法。
【請求項４】
前記第一画面と時間的に近い第二画面の位置が、該第一画面と時間的に前或いは後の複数画面の一つであることを特徴とする請求項１記載の動き推定方法。
【請求項５】
前記探索基点から順次遠い位置にマッチングブロックを探索する方向が、時計回りの螺旋方向であることを特徴とする請求項１記載の動き推定方法。
【請求項６】
前記探索基点から順次遠い位置にマッチングブロックを探索する方向が、反時計回りの螺旋方向であることを特徴とする請求項１記載の動き推定方法。
【請求項７】
探索されたマッチングブロックが前記ソリット菱形の領域の枠にある場合、探索領域を該マッチングブロックがある辺と平行している外縁三点まで拡大することを特徴とする請求項３記載の動き推定方法。
【請求項８】
探索されたマッチングブロックが前記ソリット菱形の領域の頂点にある場合、探索領域を該頂点の外縁の三角形の枠にある五点まで拡大することを特徴とする請求項３記載の動き推定方法。
【請求項９】
探索されたマッチングブロックが探索領域の中心点にある場合、該マッチングブロックを中心として、探索領域が該マッチングブロックの周り四点になることを特徴とする請求項７又は８記載の動き推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ画像処理（Ｖｉｄｅｏ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ）技術に関する動き推定方法（Ｍｏｔｉｏｎ  Ｅｓｔｉｍａｔｉｏｎ）に関し、特に、改良式ダイアモンドサーチ動き推定方法に関する。
【０００２】
本願発明は、ここに引用して本明細書に組み込む出願日２００５年３月２１日の台湾出願第０９４１０８５９９号における全開示内容に係り優先権主張するものである。
【背景技術】
【０００３】
図１に示すように、従来のＭＰＥＧ画像のデータストリーム（Ｄａｔａ  Ｓｔｒｅａｍ）は、一つ或いは複数のシーケンス（Ｓｅｑｕｅｎｃｅ）から構成されている。この各シーケンスは複数の画像グループ（Ｇｒｏｕｐ  ｏｆ  Ｐｉｃｔｕｒｅｓ，ＧＯＰ）を含み、該画像グループは多くのフレーム（Ｆｒａｍｅ）或いはピクチャ（Ｐｉｃｔｕｒｅ）から成る。フレームの属性により、イントラ符号化画像（Ｉフレーム）、フレ−ム間順方向予測符号画像（Ｐフレーム）及び双方向予測符号化画像（Ｂフレーム）の三つのフレームタイプに分かれている。
【０００４】
前記毎のフレームは全て符号化することができる。画像圧縮作業を行うため、一般的にＩフレームをカットインポイント（Ｃｕｔ―ｉｎ  Ｐｏｉｎｔ）として、動きベクトル（Ｍｏｖｉｎｇ  Ｖｅｃｔｏｒ）の推定に従って、Ｐフレーム及びＢフレームの予測ができる。すなわち、Ｉフレーム或いはＰフレームを参照フレームとして、Ｐフレームを予測することができ、Ｉフレーム及びＰフレーム或いは二つのＰフレームを参照フレームとして生じた動きベクトルから、Ｂフレームを予測することができる。したがって、これらのフレームを連続的に出力して、ＭＰＥＧ動画像をユーザに表示する。
【０００５】
ＭＰＥＧの映像圧縮標準規格により、各映像画面を複数のスライス（Ｓｌｉｃｅ）に分割して、該スライスを更に複数のマクロブロック（Ｍｉｃｒｏ  Ｂｌｏｃｋ）に分割できる。このマクロブロックは四つの輝度（Ｌｕｍｉｎａｎｃｅ）ブロック及び複数のクロミナンス（Ｃｈｒｏｍｉｎａｎｃｅ）ブロックから成っており、最終的にこの各ブロック（Ｂｌｏｃｋ）はＭＰＥＧデータの最小符号化ユニットとして定義される。動きベクトルの推定（Ｍｏｔｉｏｎ  Ｅｓｔｉｍａｔｉｏｎ）に対応して、動き補償（Ｍｏｔｉｏｎ  Ｃｏｍｐｅｎｓａｔｉｏｎ）という技術がある。一般的に、前記マクロブロック或いはブロック毎のピクセル（Ｐｉｘｅｌ）の輝度を記録して、フルサーチ（Ｆｕｌｌ  Ｓｅａｒｃｈ）の方式により二つベクトルの変化を記録して、直接動きベクトルを推算できる。しかし、この方式は膨大な計算機資源を浪費するという問題がある。
【０００６】
動きベクトルの推定によって、現画面に含まれた各ブロック及び前の画面を基準に最適マッチングブロックを求める。計算された動きベクトル及び誤差データに基づいて、前の画面のブロックを調整して現画面が得られる。この動きベクトルに基づいて、ブロックが適当な位置に転移される。重複するデータの大部分は記憶する必要がないため、記憶空間を削減し、データ圧縮の目的も達成できる。従来の動き推定方法ではフルサーチ（Ｆｕｌｌ  Ｓｅａｒｃｈ，ＦＳ）、３段探索（Ｔｈｒｅｅ  Ｓｔｅｐ  Ｓｅａｒｃｈ，ＴＳＳ)、４段探索(ｆｏｕｒ  Ｓｔｅｐ  Ｓｅａｒｃｈ，ＦＳＳ)、及びダイアモンドサーチ（Ｄｉａｍｏｎｄ  Ｓｈａｐｅ  Ｓｅａｒｃｈ,  ＤＳＳ）などがある。
【０００７】
ここで、菱形（Ｒｈｏｍｂｕｓ）のような枠を探索領域とする従来のダイアモンドサーチ動き推定方法の動作手順を以下説明する。
【０００８】
ステップ１：探索基点及び該探索基点を中心とする中空菱形の枠全ての九点から探索作業を行い、仮に最も類似度の高い点が菱形の中心にある場合、ステップ４を行い、仮に最も類似度の高い点が菱形の枠にある場合、ステップ２を行う。
【０００９】
ステップ２：該最も類似度の高い点を中心点として、もう一度菱形の枠を探索領域とする。
【００１０】
ステップ３：仮に最も類似度の高い点が中心点にある場合、ステップ４を行い、仮に最も類似度の高い点が菱形の枠にある場合、再度ステップ２を行う。
【００１１】
ステップ４：探索領域を小ソリット菱形（ｉｎｎｅｒ  ｓｏｌｉｄ  ｒｈｏｍｂｕｓ，内側の五点）へと小さくし、最後に、最も類似度の高い点が求められると、探索作業を止める。
【００１２】
図２Ａに示すように、ステップ１において最も類似度の高い点が中心１ａにあるため、ステップ４を行い、探索領域を小ソリット菱形（２、２ａ及び１ａと表示している点）へと小さくして探索作業を行い、最後に、最も類似度の高い点２ａが得られて、探索作業を止めることが説明されている。
【００１３】
図２Ｂに示すように、ステップ１において最も類似度の高い点が菱形の枠１ｂにあるので、ステップ２を行い、該最も類似度の高い点１ｂを中心点として、もう一度菱形の枠を探索領域とする。次にステップ３を行い、最も類似度の高い点が菱形の枠２ｂにあるので、再度ステップ２を行い、もう一度菱形の枠を探索領域とする。次に最も類似度の高い点が中心２ｂにあるため、ステップ４を行い、探索領域を小ソリット菱形（４、４ｂ及び２ｂと表示している点）へと小さくして、最後に、最も類似度の高い点４ｂが求められて、探索作業を止めることが説明されている。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、探索基点を中心とする中空菱形の枠を探索領域とする従来のダイアモンドサーチ動き推定方法は、大領域から探索を行った後、再度探索領域を縮小して探索を行うものである。しかし、最も類似度の高い点が一般に探索基点と近い位置になければ、探索確率が低くなる場合が多い。
【００１５】
このため、本発明の目的は、探索効率を向上させるための改良式ダイアモンドサーチ動き推定方法を提供するものである。
【課題を解決するための手段】
【００１６】
したがって、本発明は、第一画面に含まれる予定ブロックに基づいて、該第一画面と時間的に近い第二画面に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定する改良式ダイアモンドサーチ動き推定方法において、前記第二画面にある原則で一つのブロックを選択して探索基点とし、該探索基点を中心とするソリット菱形（ｓｏｌｉｄ  ｒｈｏｍｂｕｓ）の領域を最初の探索領域とし、前記探索基点から順次遠い位置に前記予定ブロックとのマッチングブロックを探索して前記動きベクトルを推定し、中空菱形の探索パターンを利用して、最初の探索領域以外での最適動きベクトルを迅速サーチすることを特徴とする改良式ダイアモンドサーチ動き推定方法である。
【００１７】
しかしながら、探索基点を中心とする中空菱形の枠を探索領域として、次に探索領域を小さくする従来のダイアモンドサーチ動き推定方法は、ある状況で、たとえば最も類似度の高い点が前記 中空菱形の内側にあっても（存在確率が高い範囲）、探索作業は依然として前記中空菱形の枠にある点から行う。このため、探索効率は低下するという問題がある。
【発明を実施するための最良の形態】
【００１８】
添付の図面を参照して理解すれば、本発明の他の目的、長所、及び新規な特徴は，以下の詳細な記述でより明らかになるだろう。
【００１９】
本発明の実施の形態において、以下の段落に類似の構成要素には同一参照符号が付けられていることに留意すべきである。
【００２０】
図３に示すように、本発明に係る方法を使用するシステムはＭＰＥＧ画像データを圧縮するための画像エンコーダ1で行われるが、本発明は他の類似な画像圧縮を行うための画像処理システムにも応用できる。
【００２１】
画像エンコーダ１ は前処理部（Ｐｒｅｐｒｏｃｅｓｓｏｒ  Ｕｎｉｔ）１０ 、動き推算部（Ｍｏｔｉｏｎ  Ｅｓｔｉｍａｔｉｏｎ  Ｕｎｉｔ）１１ 、動き補償部１２ 、動きベクトル符号化部（Ｍｏｔｉｏｎ  Ｖｅｃｔｏｒ  Ｅｎｃｏｄｉｎｇ  Ｕｎｉｔ）１３、テクスチャー符号化部（Ｔｅｘｔｕｒｅ  Ｅｎｃｏｄｉｎｇ  Ｕｎｉｔ）１４ 、ビットストリーム合成部（Ｂｉｔ―Ｓｔｒｅａｍ  Ｃｏｍｐｏｓｅｒ  Ｕｎｉｔ）１５ 、及び、記憶部１６を備える。
【００２２】
入力画像１００が前記画像エンコーダ１に入力させると、定められた画面毎のマクロブロックデータが前記画像エンコーダ１の前処理部１０で定義され、記憶部１６に記憶される。次に、前記入力画像１００に含まれるマクロブロックデータを前記動き推算部１１で計算し、例えば、前及び後の画面とのマッチングブロックデータが計算されたら、全画面で各ブロックデータの動きベクトルデータ１０２が求められ、前記動き補償部１２に入力させる。該動き補償部１２は前記動きベクトルを利用して、時間的に前或いは後の画面のマクロブロックデータを読み取って、参照データ１０４を求める。その後、前記前処理部１０からの入力画像１００に含まれるマクロブロックデータ及び動き補償部１２からの参照データ１０４との差を求めて、誤差データ１０３が得られる。該誤差データ１０３がテクスチャー符号化部１４で計算され、圧縮のテクスチャー及び復号の参照データが求められる。
【００２３】
ここで、前記テクスチャー符号化部１４の離散コサイン変換部１４１は、各ブロックのピクセルデータの離散コサイン変換（ＤＣＴ）係数を求める。そして、該ピクセルデータは周波数領域転換部１４２で時間領域から周波数領域に変換される。次に、量子化部１４３で量子化（Ｑｕａｎｔｉｚｅ）されて、多くの離散コサイン変換係数をゼロにして、更に高周波数成分を抽出する。そして、逆量子化部１４４で逆量子化されて、逆離散コサイン変換部１４５で逆離散コサイン変換係数を求めて、前記動き推算部１１に返送させる。各動きベクトルは前記動きベクトル符号化部１３で符号化されると、前記ビットストリーム合成部１５の可変長エンコーダ１５１に入力させる。
【００２４】
その同時に、同一画面の各ブロック（Ｂｌｏｃｋ）に含まれる余分な重複情報は前記交流／直流予測部１４６（ＡＣ／ＤＣ  Ｐｒｅｄｉｃｔｉｏｎ）で抽出され、前記ジグザグスキャン部１４７でジグザグスキャン（Ｚｉｇ―ｚａｇ  ｓｃａｎ）が行われ、量子化された離散コサイン変換係数を再配列する。すなわち、低周波係数を高周波係数の前に配列し、ジグザグスキャンされた離散コサイン変換係数をランレングス符号化（Ｒｕｎ  Ｌｅｎｇｔｈ  Ｅｎｃｏｄｉｎｇ、ＲＬＥ)されて、最後に、ビットストリーム合成部１５のもう一つ可変長エンコーダ１５２で可変長符号化（ｖａｒｉａｂｌｅ  ｌｅｎｇｔｈ  ｃｏｄｉｎｇ、ＶＬＣ）され、その後ビットストリーム合成部１５で組み合われて、ＭＰＥＧ圧縮データを出力できる。
【００２５】
図３及び４に示すように、本発明に係る改良式ダイアモンドサーチ動き推定方法の各好ましい実施形態は、画像エンコーダ１の動き推算部１１で行われる。本発明は第一画面５０１（又は現画面（Ｃｕｒｒｅｎｔ  Ｆｒａｍｅ）と呼ばれる）に含まれる予定ブロック５１から、時間的に近い第二画面５０２（又は参照画面（Ｒｅｆｅｒｅｎｃｅ  Ｆｒａｍｅ）と呼ばれる）に前記予定ブロック５１とのマッチングピクセルを探索して、前記予定ブロック５１の動きベクトル５３を推定する。本発明では前記第二画面５０２に含まれる予定探索点５２０を探索基点として、該探索基点を中心とするソリット菱形（図示せず）の探索領域を形成する、該探索基点から順次遠い位置にマッチングブロックを探索して、動きベクトル５３を推定する。
【００２６】
本発明の実施形態により、前記時間的に近い第二画面５０２の位置は、前記第一画面５０１と時間的に前或いは後の複数画面の一つである。また、本発明により探索基点から順次遠い位置に探索する方向は、時計回りの螺旋方向 、或いは反時計回りの螺旋方向のいずれの一つである。
【００２７】
図５に示すように、本発明に係る改良式ダイアモンドサーチ動き推定方法は、先ず最初に、探索基点と一番近いソリッド菱形（Ｓｏｌｉｄ Ｒｈｏｍｂｕｓ）を形成する十三点を探索する（ステップ６０１)。次に最も類似度の高い点を判定する(ステップ６０２)。仮に最も類似度の高い点が該ソリット菱形の内側五点の一つ（ステップ６０３）である場合、探索を止める（ステップ６１０）。仮に最も類似度の高い点が該ソリット菱形の外側八点の一つ（ステップ６０４）である場合、該最も類似度の高い点を新探索基点として、菱形の枠にあるまだ探索していなかった三点或いは五点を探索領域とする（ステップ６０５）。
【００２８】
その後、再度最も類似度の高い点を判定する（ステップ６０６）。仮に最も類似度の高い点が菱形の枠にある（ステップ６０７）場合、該最も類似度の高い点を新探索基点として、菱形の枠にあるまだ探索していなかった三点或いは五点を探索領域とする（ステップ６０５）。仮に最も類似度の高い点が菱形の中心点にある（ステップ６０８）場合、中心点と一番近い小ソリッド菱形（ｉｎｎｅｒ  ｓｏｌｉｄ  ｒｈｏｍｂｕｓ）を形成する四点を探索する（ステップ６０９）。最も類似度の高い点が得られると、探索を止め、該最も類似度の高い点の動きベクトルを返送する（ステップ６１０）。
【００２９】
図５及び６Ａ〜６Ｂにしたがって、本発明に係る改良式ダイアモンドサーチ動き推定方法の好ましい実施形態における各種探索状況を説明する。
【００３０】
図６Ａに示すように、第一回探索を行うとき、探索基点と一番近いソリッド菱形を形成する十三点を探索する（ステップ６０１）。次に最も類似度の高い点を判定する（ステップ６０２）。該最も類似度の高い点１ｖが該ソリット菱形の内側五点の一つ（ステップ６０３）にあるので、第一回探索を終了したら探索を止める（ステップ６１０） 。
【００３１】
図６Ｂに示すように、第一回探索を行うとき、探索基点と一番近いソリッド菱形を形成する十三点を探索する（ステップ６０１）。そして最も類似度の高い点を判定する（ステップ６０２）。最も類似度の高い点１ｖが該ソリット菱形の外側八点の一つ（ステップ６０４）にあるため、次に第二回探索を行い、 該最も類似度の高い点１ｖを新探索基点として、菱形の枠にあるまだ探索していなかった三点或いは五点（図６Ｂの２，２ｖ，４と表示している点）を探索領域とする（ステップ６０５）。
【００３２】
その後、再度最も類似度の高い点を判定する（ステップ６０６）。仮に最も類似度の高い点２ｖが菱形の枠にある（ステップ６０７）場合、第三回探索を行い、 該最も類似度の高い点２ｖを新探索基点として、菱形の枠にあるまだ探索していなかった三点（図６Ｂの３と表示している点）を探索領域とする（ステップ６０５）。仮に該最も類似度の高い点が菱形の中心点２ｖにある（ステップ６０８）場合、第四回探索を行い、 中心点と一番近い小ソリッド菱形を形成する四点（図６Ｂの４と表示している点）を探索する（ステップ６０９）。最も類似度の高い点４ｖが得られると、探索を止め、該最も類似度の高い点の動きベクトルを返送する（ステップ６１０）。
【００３３】
図７〜９に示すように、本発明に係る改良式ダイアモンドサーチ動き推定方法の好ましい実施形態の変形例を示す。該探索方法では、いずれも探索基点から順次遠い位置へ探索領域を移して行き、かつ、該探索方法における探索領域を前記のソリット菱形の一部分として行うものである。
【００３４】
図７に示すように、先ず最初に、内側の小ソリット菱形を形成する五点（１及び１ｖと表示している点）から探索作業を行う。仮に最も類似度の高い点１ｖが小ソリット菱形の枠にある場合、まだ探索していなかった該ソリット菱形の枠８１を形成する八点をサーチする。次にステップ６０２〜６１０にしたがって、探索基点から順次遠い位置に探索して、最も類似度の高い点が得られるまで探索作業を行う 。
【００３５】
図８に示すように、 先ず最初に、内側の小ソリット菱形を形成する五点（１及び１ｖと表示している点）から探索作業を行う。仮に最も類似度の高い点１ｖが小ソリット菱形の枠にある場合、該最も類似度の高い点１ｖを探索基点の中心として、該最も類似度の高い点１ｖ外側のソリット菱形の半枠８２にある五点（２と表示している点）を探索領域として、ステップ６０２〜６１０にしたがって、探索基点から順次遠い位置に探索して、最も類似度の高い点が得られるまで探索作業を行う。
【００３６】
図９は図８の半枠 探索パターンと類似し、先ず内側の小ソリット菱形を形成する五点（１及び１ｖと表示している点）から探索作業を行う。仮に最も類似度の高い点１ｖが小ソリット菱形の枠にある場合、該最も類似度の高い点１ｖを探索基点の中心として、該最も類似度の高い点１ｖ外側のソリット菱形の半枠８３にある三点（２と表示している点）を探索領域として、ステップ６０２〜６１０にしたがって、探索基点から順次遠い位置に探索して、最も類似度の高い点が得られるまで探索作業を行う。
【００３７】
なお、本発明は上記実施の形態に限定されるものではなく、本発明の趣旨に基づいて種々変形させることが可能であり、それらを本発明の範囲から排除するものではない。
【００３８】
（発明の効果）
上述したように、動きベクトルが一般に放射状に分配されるので、ソリット菱形を最初の探索領域とし、次に最も類似度の高い点を中心とする中空菱形の枠の探索領域に拡大し、最後に四点の探索領域へと小さくする本発明に係る改良式ダイアモンドサーチ動き推定方法は、最も類似度の高い点の存在確率が高い領域から探索し始めるので、無駄な探索時間を削減でき、探索効率も向上できる。
【図面の簡単な説明】
【００３９】
【図１】従来のＭＰＥＧ画像データの構造を示す説明図である。
【図２Ａ−２Ｂ】従来のダイアモンドサーチ動き推定方法を示す説明図である。
【図３】本発明に係るＭＰＥＧ画像データを圧縮するための画像エンコーダを示すブロック図である。
【図４】本発明に係る改良式ダイアモンドサーチ動き推定方法による動きベクトルの推定を示す説明図である。
【図５】本発明に係る改良式ダイアモンドサーチ動き推定方法を示すフローチャートである。
【図６Ａ−６Ｂ】本発明に係る改良式ダイアモンドサーチ動き推定方法の好ましい実施形態を示す説明図である。
【図７】本発明に係る改良式ダイアモンドサーチ動き推定方法の好ましい実施形態の第一の変形例を示す説明図である。
【図８】本発明に係る改良式ダイアモンドサーチ動き推定方法の好ましい実施形態の第二の変形例を示す説明図である。
【図９】本発明に係る改良式ダイアモンドサーチ動き推定方法の好ましい実施形態の第三の変形例を示す説明図である。
【符号の説明】
【００４０】
１        画像エンコーダ
１０      前処理部
１００    入力画像
１０１    現画像マクロブロックデータ
１０２    動きベクトルデータ
１０３    誤差データ
１０４    参照データ
１１      動き推算部
１２      動き補償部
１３      動きベクトル符号化部
１４      テクスチャー符号化部
１４１    離散コサイン変換部
１４２    周波数領域転換部
１４３    量子化部
１４４    逆量子化部
１４５    逆離散コサイン変換部
１４６    交流／直流予測部
１４７    ジグザグスキャン部
１５      ビットストリーム合成部
１５１，１５２      可変長エンコーダ
１６      記憶部
５０１    第一画面
５０２    第二画面
５２      ブロック
５２０    予定探所点
５３      動きベクトル
６０１〜６１０      ステップ
【図１】
2006270958.tif 000003
【図２Ａ−２Ｂ】
2006270958.tif 000004
【図３】
2006270958.tif 000005
【図４】
2006270958.tif 000006
【図５】
2006270958.tif 000007
【図６Ａ−６Ｂ】
2006270958.tif 000008
【図７】
2006270958.tif 000009
【図８】
2006270958.tif 000010
【図９】
2006270958.tif 000011