(57)【特許請求の範囲】
【請求項１】
動き補償予測を行う映像符号化で用いられ、水平成分および垂直成分がともに不一致である元動きベクトルと予測ベクトルとの２つのベクトルの終点を結ぶ直線と水平軸が成す角度と等しく探索領域形状を回転させて探索領域を決定する動きベクトル探索方法であって、
符号化対象ブロックに関し、予め探索した動きベクトルを入力し元動きベクトルとする過程と、
前記符号化対象ブロックの動きベクトルの発生符号量が最小となるオーバーヘッドコスト最小の動きベクトルを算出し予測ベクトルとする過程と、
前記元動きベクトルと前記予測ベクトルとに基づき、両ベクトル間の距離が大きいほど探索領域が広く、該距離が小さいほど探索領域が狭くなり、かつ、前記元動きベクトルと  前記予測ベクトルとの２つのベクトルの終点を結ぶ直線と水平軸が成す角度と等しく探索領域形状を回転させて前記元動きベクトルと前記予測ベクトルとに挟まれた領域を特定して、その特定した領域を探索領域として限定する過程と、
前記限定した探索領域のみを探索することで動きベクトルを探索する過程と、
を備えることを特徴とする動きベクトル探索方法。
【請求項２】
請求項１に記載の動きベクトル探索方法において、
前記探索領域を限定する過程では、前記入力した動きベクトルと前記算出したオーバヘッドコスト最小の動きベクトルとを結ぶ直線上の領域を特定して、その特定した領域を探索領域として限定することを、
特徴とする動きベクトル探索方法。
【請求項３】
請求項１に記載の動きベクトル探索方法において、
前記探索領域を限定する過程では、前記入力した動きベクトルと前記算出したオーバヘッドコスト最小の動きベクトルとを結ぶ直線を長方形の一辺とし、予め設定した長さを持ち、かつその直線に中点位置で交差直交する直線を長方形の他辺とする長方形内の領域を特定して、その特定した領域を探索領域として限定することを、
特徴とする動きベクトル探索方法。
【請求項４】
請求項１に記載の動きベクトル探索方法において、
前記探索領域を限定する過程では、前記入力した動きベクトルと前記算出したオーバヘッドコスト最小の動きベクトルとを焦点として、各焦点からの距離の和が予め設定した一定値となる楕円内の領域を特定して、その特定した領域を探索領域として限定することを、
特徴とする動きベクトル探索方法。
【請求項５】
請求項１に記載の動きベクトル探索方法において、
前記動きベクトルを探索する過程では、前記限定した探索領域から探索点を抽出して、その抽出した探索点のみを探索することを、
特徴とする動きベクトル探索方法。
【請求項６】
動き補償予測を行う映像符号化で用いられ、水平成分および垂直成分がともに不一致である元動きベクトルと予測ベクトルとの２つのベクトルの終点を結ぶ直線と水平軸が成す角度と等しく探索領域形状を回転させて探索領域を決定する動きベクトル探索装置であって、
符号化対象ブロックに関し、予め探索した動きベクトルを入力し元動きベクトルとする手段と、
前記符号化対象ブロックの動きベクトルの発生符号量が最小となるオーバーヘッドコスト最小の動きベクトルを算出し予測ベクトルとする手段と、
前記元動きベクトルと前記予測ベクトルとに基づき、両ベクトル間の距離が大きいほど探索領域が広く、該距離が小さいほど探索領域が狭くなり、かつ、前記元動きベクトルと  前記予測ベクトルとの２つのベクトルの終点を結ぶ直線と水平軸が成す角度と等しく探索領域形状を回転させて前記元動きベクトルと前記予測ベクトルとに挟まれた領域を特定して、その特定した領域を探索領域として限定する手段と、
前記限定した探索領域のみを探索することで動きベクトルを探索する手段と、
を備えることを特徴とする動きベクトル探索装置。
【請求項７】
請求項６に記載の動きベクトル探索装置において、
前記探索領域を限定する手段では、前記入力した動きベクトルと前記算出したオーバヘッドコスト最小の動きベクトルとを結ぶ直線上の領域を特定して、その特定した領域を探索領域として限定することを、
特徴とする動きベクトル探索装置。
【請求項８】
請求項６に記載の動きベクトル探索装置において、
前記探索領域を限定する手段では、前記入力した動きベクトルと前記算出したオーバヘッドコスト最小の動きベクトルとを結ぶ直線を長方形の一辺とし、予め設定した長さを持ち、かつその直線に中点位置で交差直交する直線を長方形の他辺とする長方形内の領域を特定して、その特定した領域を探索領域として限定することを、
特徴とする動きベクトル探索装置。
【請求項９】
請求項６に記載の動きベクトル探索装置において、
前記探索領域を限定する手段では、前記入力した動きベクトルと前記算出したオーバヘッドコスト最小の動きベクトルとを焦点として、各焦点からの距離の和が予め設定した一定値となる楕円内の領域を特定して、その特定した領域を探索領域として限定することを、
特徴とする動きベクトル探索装置。
【請求項１０】
請求項６に記載の動きベクトル探索装置において、
前記動きベクトルを探索する手段では、前記限定した探索領域から探索点を抽出して、その抽出した探索点のみを探索することを、
特徴とする動きベクトル探索装置。
【請求項１１】
請求項１に記載の動きベクトル探索方法の実現に用いられる処理をコンピュータに実行させるための動きベクトル探索プログラム。
【請求項１２】
請求項１に記載の動きベクトル探索方法の実現に用いられる処理をコンピュータに実行させるための動きベクトル探索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き補償予測を行う映像符号化で用いられる動きベクトル探索方法およびその装置と、その動きベクトル探索方法の実現に用いられる動きベクトル探索プログラムおよびそのプログラムを記録したコンピュータ読み取り可能な記録媒体とに関する。
本願は、２００７年３月１４日に出願された特願２００７−０６４２８６号に基づき優先権を主張し、その内容をここに援用する。
【背景技術】
【０００２】
動き補償予測を行う映像符号化方式では、動きベクトルを探索する必要がある。動きベクトルの探索では、必ずしも予測誤差電力が最小となる位置が符号化効率最大とはならない。これは、実際の符号化情報は、予測誤差信号のほかに動きベクトルなどの情報を伝送しているからである。
【０００３】
そこで、動きベクトルの発生符号量をオーバヘッドコストとして考慮した動きベクトル探索が行われている。Ｈ.264の参照ソフトウェアでは、予測モード選択時に、
Ｃost ＝Ｄ＋λ・Ｒ
というコスト関数を用いている（例えば、非特許文献１参照）。
【０００４】
ここで、Ｄは予測誤差電力、Ｒは直交変換係数以外の発生符号量、λは量子化ステップサイズによって決まる定数である。
【０００５】
このような方法により、動きベクトルの発生符号量を考慮した最小コストの動きベクトルを探索できる。
【０００６】
動きベクトルの発生符号量は、映像符号化方式により異なる。
例えば、ＭＰＥＧ−２では、原則左隣のブロックの動きベクトルを予測ベクトルとして差分を符号化する。（例えば、非特許文献２参照）。
また、Ｈ.264では、近傍３ブロックの動きベクトルのメディアンを予測ベクトルとして符号化する（例えば、非特許文献３参照）。
【０００７】
このように、動きベクトルのコストが異なる映像符号化方式間で動きベクトルを流用する場合、前段の映像符号化方式で探索した動きベクトルが、後段の映像符号化方式でコスト最小となるとは限らない。
【０００８】
前段の動きベクトル（以下、元動きベクトルと称する）を後段で利用する例として、図８Ａ及び８Ｂに示すように、「他の動き探索方法を流用した映像符号化処理」や、図９Ａ及び９Ｂに示すように、「再符号化処理」を行うことが考えられる。
【０００９】
前者は、他の映像符号化方式の動き探索部分などを流用して符号化装置を構成する場合であり、後者は、既に符号化済みビットストリームについて、映像符号化方式やビットレート等を変更するために、再符号化する場合である。
特に、再符号化時に、元のビットストリームに含まれる動きベクトルを再利用して、再符号化時の動き探索にかかる演算コストを削減することができる。例えば、下記の特許文献１に記載された発明では、元動きベクトルを探索開始点として、再探索を行っている。
【００１０】
どちらの例でも、元動きベクトルをそのまま利用するだけでは、後段の符号化部で最小コストになる保証がないため、広範囲で再探索した場合に比べて符号化効率は低下する。
特に、再符号化時は、元動きベクトルを探索した映像信号が原信号であるのに対し、後段では元のビットストリームの復号信号を入力するので、映像信号が異なる。このため、符号化効率が低下する可能性が高い。
【００１１】
そこで、一般的に、後段側の演算コストの許す範囲で元動きベクトルの周辺だけを再探索する方法が行われている。この方法では、探索範囲を限定して部分的に再探索を行うため、符号化効率の低下を抑制できる。
【００１２】
図１０に、この再探索のフローチャートを図示する。
ここでは、動きベクトルの発生符号量をオーバヘッドコストとして考慮するため、再探索前に予測ベクトルを算出しているが、動きベクトルの再探索については、予測ベクトルに関係なく、元動きベクトルの周辺だけを再探索するようにしている。
【００１３】
このような方法により、後段での再探索の演算コストを抑えつつ、符号化効率の低下を抑制できる。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】インターネット＜ＵＲＬ：http://iphome.hhi.de/suehring/tml/download/ ＞
【非特許文献２】ISO/IEC-13818-2, "Information technology - Generic coding of moving pictures and associated audio information: Video", pp. 77-85, May, 1996
【非特許文献３】ITU-T H.264 ITU-T Rec. H.264, "Advanced video coding for generic audiovisual services", pp. 146-149, March, 2005
【特許文献】
【００１５】
【特許文献１】特開２０００−２４４９２１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、元動きベクトルを探索する際に用いたコスト関数と、後段の映像符号化方式のコスト関数とが異なる場合、必ずしも、元動きベクトル近傍に最適な動きベクトルが存在するとは限らない。
【００１７】
図１１に、その一例を示す。この例では、後段の再探索範囲内（元動きベクトル近傍の再探索範囲内）で最小コストとなった動きベクトルよりも、その再探索範囲外に更にコスト最小となる動きベクトルが存在することを示している。
これは、前段での動き探索の際、後段での予測ベクトルを考慮していないことに起因する。また、再符号化時は、入力映像も異なるため、このズレが拡大する可能性がある。
【００１８】
このように、元動きベクトルを探索する前段と動きベクトルを再探索する後段とで、探索する際のコスト関数や映像信号が異なる場合には、符号化効率が低下する可能性がある。この問題を解決するには、再探索範囲を拡大する必要があるが、その場合には、後段での演算コストの増加が問題となる。
【００１９】
本発明はかかる事情に鑑みてなされたものであって、前段の映像符号化方式で求められた元動きベクトルを利用して後段の映像符号化方式で動きベクトルを探索する場合に、符号化効率の低下を抑制できるようにするとともに、演算コストを削減できるようにする新たな動きベクトル探索技術の提供を目的とする。
【課題を解決するための手段】
【００２０】
この目的を達成するために、水平成分および垂直成分がともに不一致である元動きベクトルと予測ベクトルとの２つのベクトルの終点を結ぶ直線と水平軸が成す角度と等しく探索領域形状を回転させて探索領域を決定する本発明の動きベクトル探索装置は、動き補償予測を行う映像符号化で用いられるときに、（１）符号化対象ブロックに関し、予め探索した動きベクトルを入力する入力手段と、（２）符号化対象ブロックの動きベクトルの発生符号量が最小となるオーバヘッドコスト最小の動きベクトルを算出する算出手段と、（３）前記元動きベクトルと前記予測ベクトルとに基づき、両ベクトル間の距離が大きいほど探索領域が広く、該距離が小さいほど探索領域が狭くなり、かつ、前記元動きベクトルと前記予測ベクトルとの２つのベクトルの終点を結ぶ直線と水平軸が成す角度と等しく探索領域形状を回転させて前記元動きベクトルと前記予測ベクトルとに挟まれた領域を特定して、その特定した領域を探索領域として限定する手段と、（４）限定手段の限定した探索領域のみを探索することで動きベクトルを探索する探索手段とを備えるように構成する。
以上の各処理手段が動作することで実現される本発明の動きベクトル探索方法はコンピュータプログラムでも実現できるものであり、このコンピュータプログラムは、適当なコンピュータ読み取り可能な記録媒体に記録して提供されたり、ネットワークを介して提供され、本発明を実施する際にインストールされてＣＰＵなどの制御手段上で動作することにより本発明を実現することになる。
このように構成される本発明の動きベクトル探索装置では、動きベクトルを探索する際に、前段の映像符号化方式で探索された動きベクトル（前述した元動きベクトル）を入力する。
【００２１】
続いて、符号化対象ブロックの動きベクトルの発生符号量が最小となるオーバヘッドコスト最小の動きベクトルを算出する。
【００２２】
例えば、符号化済みの近傍ブロックの動きベクトルから符号化対象ブロックの予測ベクトルを算出して、その算出した予測ベクトルをオーバヘッドコスト最小の動きベクトルとする。
【００２３】
続いて、入力した動きベクトルと算出したオーバヘッドコスト最小の動きベクトルとに挟まれた領域を特定して、その特定した領域を探索領域として限定する。
【００２４】
例えば、入力した動きベクトルと算出したオーバヘッドコスト最小の動きベクトルとを結ぶ直線を直径とする円内の領域を特定して、その特定した領域を探索領域として限定する。
【００２５】
あるいは、入力した動きベクトルと算出したオーバヘッドコスト最小の動きベクトルとを結ぶ直線上の領域を特定して、その特定した領域を探索領域として限定する。
あるいは、入力した動きベクトルと算出したオーバヘッドコスト最小の動きベクトルとを結ぶ直線を長方形の一辺とし、予め設定した長さを持ち、かつその直線に中点位置で交差直交する直線を長方形の他辺とする長方形内の領域を特定して、その特定した領域を探索領域として限定する。
あるいは、入力した動きベクトルと算出したオーバヘッドコスト最小の動きベクトルとを焦点として、各焦点からの距離の和が予め設定した一定値となる楕円内の領域を特定して、その特定した領域を探索領域として限定する。
【００２６】
続いて、典型的には、限定した探索領域から探索点を抽出して、その抽出した探索点のみを再探索することで動きベクトルを探索する。
【発明の効果】
【００２７】
このように、本発明では、前段の映像符号化方式で求められた元動きベクトルを利用して後段の映像符号化方式で動きベクトルを探索する場合に、探索する際のコスト関数や映像信号が異なる場合があることで、元動きベクトル近傍に最適な動きベクトルが存在するとは限らないことを考慮して、元動きベクトルの周辺だけを再探索するのではなくて、元動きベクトルと後段でのオーバヘッドコスト最小点とを含む形で探索領域を限定するようにする。
【００２８】
従って、本発明によれば、符号化効率の低下を抑制できるようになるとともに、探索点数についても抑えることができるようなることから、演算コストを削減できるようになる。
【図面の簡単な説明】
【００２９】
【図１】本発明に従った動作のフローチャートである。
【図２Ａ】本発明の限定する再探索範囲の説明図である。
【図２Ｂ】同様に、本発明の限定する再探索範囲の説明図である。
【図２Ｃ】同様に、本発明の限定する再探索範囲の説明図である。
【図２Ｄ】同様に、本発明の限定する再探索範囲の説明図である。
【図３】本発明による映像符号化装置の装置構成例である。
【図４】同映像符号化装置の内部構成例である。
【図５】図形パラメータ記憶部のデータ構造の説明図である。
【図６】同映像符号化装置の実行するフローチャートの一例である。
【図７】同様に、同映像符号化装置の実行するフローチャートの一例である。
【図８Ａ】前段の動きベクトルを後段で利用する映像符号化処理の一例の説明図である。
【図８Ｂ】同様に、上記一例の説明図である。
【図９Ａ】前段の動きベクトルを後段で利用する映像符号化処理の別の一例の説明図である。
【図９Ｂ】同様に、上記別の一例の説明図である。
【図１０】従来技術のフローチャートである。
【図１１】従来技術の問題の説明図である。
【発明を実施するための形態】
【００３０】
次に、実施の形態に従って本発明を説明する。
【００３１】
前段の映像符号化方式で求められた元動きベクトルを利用して後段の映像符号化方式で動きベクトルを探索する場合の従来技術の問題は、元動きベクトルの近傍でしか動きベクトルを探索していないことに起因する。
【００３２】
一方、動きベクトル情報については、近傍の符号化済みブロックの動きベクトルから符号化対象ブロックの予測ベクトルを算出して、当該動きベクトルとこの予測ベクトルとの差分を符号化することから、差分が０のときに動きベクトルの符号量が最小となる。つまり、この場合の予測ベクトルがオーバヘッドコストを最小とする動きベクトルとなる。
【００３３】
これから、限られた探索点数で、元動きベクトル近傍と予測ベクトル近傍とを探索できるようにすれば、従来技術の問題を解決できるようになることで、符号化効率の低下を抑制できるようになるとともに、演算コストを削減できるようになる。
【００３４】
そこで、本発明では、元動きベクトルと、後段の映像符号化方式での動きベクトルの発生符号量（オーバヘッドコスト）を最小とする点である予測ベクトルという２点を用いて、後段の映像符号化方式での再探索範囲（再探索領域）を限定するという構成を採る。
【００３５】
図１に本発明による動作の１例であるフローチャートを示す。
【００３６】
このフローチャートに示すように、先ず最初に、ステップＳ１０１で、元動きベクトルを入力する。すなわち、前段の映像符号化方式で求められた元動きベクトルを入力するのである。
【００３７】
続いて、ステップＳ１０２で、近傍の符号化済みブロックの動きベクトルから符号化対象ブロックの予測ベクトルを算出する。
【００３８】
ここで、予測ベクトルの算出方法は、映像符号化方式によって異なる。また、符号化済みブロックがフレーム内符号化モードなど動きベクトルを持たない場合の処理も、各映像符号化方式の予測ベクトルの生成方法に従う。
【００３９】
続いて、ステップＳ１０３で、元動きベクトルと予測ベクトルとに基づいて、再探索範囲を限定する。
【００４０】
続いて、ステップＳ１０４で、限定した再探索範囲から、その探索範囲を示す図形に含まれる探索点を抽出する。
【００４１】
例えば、再探索範囲が円形であれば、その円に含まれる探索点を全て抽出し、再探索範囲とする。この再探索範囲に含まれる探索点数と、従来方法の再探索点数とを一致させれば、後段の動き探索部の演算コストは同等になる。探索点数を従来方法よりも削減すれば、演算コストの削減につながる。
【００４２】
続いて、ステップＳ１０５で、抽出した再探索点について再探索を行うことで動きベクトルを決定する。
【００４３】
次に、元動きベクトルと予測ベクトルとに基づいて行う再探索範囲の限定方法について説明する。
【００４４】
再探索範囲を限定（設定）する際、オーバヘッドコストを最小とする動きベクトルである予測ベクトルが含まれるように設定することが望ましい。
【００４５】
図２Ａ〜２Ｄに、再探索範囲の設定例を示す。この例では、円形、楕円形、長方形、線分を再探索範囲としている。以下に、再探索範囲の限定方法について説明する。
【００４６】
〔１〕円形
例えば、図２Ａに示すように、元動きベクトルと予測ベクトルとを結ぶ線分を直径とする円を描く。この円の内側に含まれる探索点を再探索範囲とする。
【００４７】
〔２〕楕円形
例えば、図２Ｂに示すように、元動きベクトルと予測ベクトルとを焦点とする楕円を描く。各焦点からの距離の和は定数として予め与えておく。この楕円の内側に含まれる探索点を再探索範囲とする。
【００４８】
〔３〕長方形
例えば、図２Ｃに示すように、元動きベクトルと予測ベクトルとの距離を長辺とする長方形を描く。短辺の長さは定数として予め与えておく。この長方形の内側に含まれる探索点を再探索範囲とする。
【００４９】
〔４〕線分
例えば、図２Ｄに示すように、元動きベクトルと予測ベクトルとを結ぶ線分を描く。この線分上の探索点を再探索範囲とする。
【００５０】
これらの再探索範囲の限定方法は一例である。このように、再探索範囲は、主に元動きベクトルと予測ベクトルとに基づいて限定することになる。
【００５１】
なお、複数の動き補償ブロックサイズを有する映像符号化方式では、ブロックサイズによって、動きベクトルの本数が変わるため、常に最大ブロックサイズが最小オーバヘッドコストになる可能性がある。その場合は、各ブロックサイズごとにオーバヘッドコスト最小の動きベクトルを算出すれば良い。
例えば、１６×１６サイズと８×８サイズの２種類のブロックサイズがある場合、それぞれのサイズでオーバーヘッドコスト最小の動きベクトルを求め、再探索範囲を限定する。
【００５２】
このような方法により、本発明によれば、前段の映像符号化方式で求められた元動きベクトルを利用して後段の映像符号化方式で動きベクトルを探索する場合に、再探索点数を増加させることなく、予測ベクトル近傍も探索することができるようになり、これにより、符号化効率の低下を抑制できるようになるとともに、演算コストを削減できるようになる。
【実施例】
【００５３】
以下、具体的な実施例に従って本発明を説明する。
【００５４】
図３に、本発明の適用される映像符号化装置の装置構成例を図示する。
【００５５】
この図に示すように、本映像符号化装置１は、映像信号の予測信号を生成して、映像信号とその予測信号との差分値を求め、それを量子化し符号化することで符号化ビットストリームを生成して出力するという処理を行うものであり、近傍の符号化済みブロックの動きベクトルから符号化対象ブロックの予測ベクトルを算出する機能を有して、動きベクトルの探索を行う動き探索部１０を備え、さらに、前段の映像符号化方式で求められた元動きベクトルと動き探索部１０の算出した予測ベクトルとを入力として、動き探索部１０に対して、動きベクトルの再探索範囲（再探索領域）を指示する再探索範囲限定部２０を備える。
【００５６】
図４に、本実施例の動きベクトル探索処理を実現するために、映像符号化装置１の備える再探索範囲限定部２０の採る構成の一例を図示する。
【００５７】
この図に示すように、再探索範囲限定部２０は、予測ベクトル入力部２００と、元動きベクトル入力部２０１と、図形種別情報入力部２０２と、再探索範囲設定部２０３と、図形パラメータ記憶部２０４とを備える。
【００５８】
予測ベクトル入力部２００は、動き探索部１０の算出した予測ベクトルを入力する。
元動きベクトル入力部２０１は、前段の映像符号化方式で求められた元動きベクトルを入力する。
図形種別情報入力部２０２は、予め設定される円形であるとか楕円形であるとか長方形であるとか線分であるというような再探索範囲の図形種別の情報を入力する。
【００５９】
再探索範囲設定部２０３は、予測ベクトル入力部２００の入力した予測ベクトルと、元動きベクトル入力部２０１の入力した元動きベクトルと、図形種別情報入力部２０２の入力した図形種別情報とに基づいて、動きベクトルの再探索範囲を設定して、動き探索部１０に通知する。
【００６０】
図形パラメータ記憶部２０４は、図５に示すようなデータ構造を有して、再探索範囲設定部２０３が再探索範囲の設定の際に必要とする図形パラメータの情報を記憶する。
例えば、図２Ｂで説明したように、楕円という図形種別については、再探索範囲を設定するのに２つの焦点からの距離の和についての設定値が必要となるので、その設定値の情報を記憶する。
また、図２Ｃで説明したように、長方形という図形種別については、再探索範囲を設定するのにもう一辺の長さについての設定値が必要となるので、その設定値の情報を記憶する。
【００６１】
本実施例では、他の映像符号化方式で符号化されたビットストリームの再符号化を前提とし、入力される元動きベクトルは、元のビットストリームから取り出した動きベクトルを利用する。
また、予測ベクトルは、近傍３ブロックの動きベクトルから算出する。
なお、元のビットストリームは、後段での符号化処理以前に復号済みで、動きベクトルも保存されているものとする。
【００６２】
図６に、図４のように構成される映像符号化装置１の実行するフローチャートの一例を図示する。
【００６３】
次に、このフローチャートに従って、映像符号化装置１の実行する動きベクトル探索処理について詳細に説明する。
【００６４】
映像符号化装置１では、図６のフローチャートに示すように、まず最初に、ステップＳ２０１で、予め設定された再探索範囲の図形種別情報を入力する。
【００６５】
続いて、ステップＳ２０２で、図形パラメータ記憶部２０４に、入力した図形種別情報の指すパラメータが記憶されている場合には、それを読み出す。
【００６６】
なお、図形種別情報が映像シーケンス全体に対して設定されている場合には、ステップＳ２０１，２０２の処理については、その映像シーケンスに対して一度だけ実行すれば良い。
【００６７】
続いて、ステップＳ２０３で、元のビットストリームから動きベクトルを取り出すことで、符号化対象ブロックについて求められた元動きベクトルを入力する。
【００６８】
続いて、ステップＳ２０４で、近傍の符号化済みブロックの動きベクトルから符号化対象ブロックの予測ベクトルを算出する。
【００６９】
例えば、符号化対象ブロックの近傍３ブロック（Ａ，Ｂ，Ｃ）の動きベクトル（＜ＭＶＡ＞，＜ＭＶＢ＞，＜ＭＶＣ＞）の中央値を予測ベクトルとして算出する場合には、
ＰＭＶx ＝Ｍedian （ＭＶＡx ，ＭＶＢx ，ＭＶＣx ）
ＰＭＶy ＝Ｍedian （ＭＶＡy ，ＭＶＢy ，ＭＶＣy ）
という式に従って、予測ベクトル＜ＰＭＶ＞を算出する。ここで、“＜...＞”はベクトルを示す記号である。
【００７０】
続いて、ステップＳ２０５で、入力した図形種別情報と、入力した元動きベクトルと、算出した予測ベクトルと、図形パラメータ記憶部２０４から読み出したパラメータとに基づいて、図２Ａ〜２Ｄに示すような形で動きベクトルの再探索範囲を限定し、その限定した再探索範囲から探索点を抽出して、動きベクトルを探索をする。
【００７１】
次に、図７に示すフローチャートに従って、再探索範囲の図形種別として線分が指定された場合を具体例にして、図６のフローチャートのステップＳ２０５で実行する処理について詳細に説明する。
【００７２】
ここで、このフローチャートでは、探索点は整数画素精度とし、元動きベクトルから水平または垂直方向に１画素ずつ線分上を探索して、予測ベクトルの位置を終点とすることを想定している。
【００７３】
すなわち、再探索範囲の図形種別として線分が指定された場合には、ステップＳ２０５の処理に入ると、図７のフローチャートに示すように、まず最初に、ステップＳ３０１で、元動きベクトルで初期化する処理を行って、初期動きベクトルとして、入力した元動きベクトル＜ＭＶＯ＞を設定するとともに、最小コストとして、元動きベクトル＜ＭＶＯ＞のコストを代入する。
【００７４】
続いて、ステップＳ３０２で、元動きベクトル＜ＭＶＯ＞と予測ベクトル＜ＰＭＶ＞とを結ぶ線分ｙ＝αｘ＋βを算出する。
【００７５】
すなわち、線分の傾きαと切片βを、
α＝（ＰＭＶy −ＭＶＯy ）／（ＰＭＶx −ＭＶＯx ）
β＝ＭＶＯy −α・ＭＶＯx 
という式に従って算出する。ただし、ＰＭＶx ＝ＭＶＯx の場合を除く。
【００７６】
続いて、ステップＳ３０３で、算出した傾きの絶対値｜α｜が１以上であれば、垂直成分を１ずつ変化させ、１未満であれば、水平成分を１ずつ変化させる。そして、変化後の水平もしくは垂直成分から、線分の式を使い他方の成分を算出することで、線分ｙ＝αｘ＋β上に設定される探索位置を算出する。ただし、ＰＭＶx ＝ＭＶＯx の場合は、垂直成分のみを変化させる。
【００７７】
続いて、ステップＳ３０４で、探索位置でのコストを算出し、続くステップＳ３０５で、現時点での最小コストと比較を行う。
【００７８】
この比較処理に従って、算出したコストが現時点での最小コスト未満であることを判断するときには、ステップＳ３０６に進んで、今回のコストおよび動きベクトルに従って、最小コストおよび動きベクトルを入れ替える。
【００７９】
続いて、ステップＳ３０７で、探索位置が予測ベクトルと一致しているのか否かを確認して、一致していないことを確認する場合には、ステップＳ３０３の処理に戻り、一致したことを確認する場合には、処理を終了する。
【００８０】
ここで、図７のフローチャートでは、元動きベクトルを始点、予測ベクトルを終点としたが、探索の順番は任意である。例えば、探索範囲の両端と中央位置の３点でコストの比較を行い、探索点数を削減することも可能である。
【００８１】
この方法を用いる場合には、例えば、まず、元動きベクトルと予測ベクトルと両ベクトルの中点との３箇所を比較し、コストが低い２点を抽出する。但し、両端が低コスト点となった場合は、最低コスト点と中点の２点を抽出する。続いて、その２点間の中点を求め、同様に３点での比較を行う。中点が算出できなくなるまで、この処理を繰り返し行う。
このほか、コストが小さい位置から探索を開始することも可能である。
【００８２】
図７のフローチャートでは、再探索範囲の図形種別として線分が指定された場合を想定して図６のフローチャートのステップＳ２０５で実行する処理について説明したが、再探索範囲の図形種別として線分以外のものが指定される場合にも、同様の処理を実行することになる。
【００８３】
すなわち、図２Ａ〜２Ｃに示すような形で限定される再探索範囲の中から順次探索位置を選択し、そのコストを算出して、現時点での最小コスト未満であることを判断するときには、今回のコストおよび動きベクトルに従って、最小コストおよび動きベクトルを入れ替えることを繰り返していくことで、コスト最小となる動きベクトルを探索するのである。
【００８４】
このようにして、本発明では、再符号化時に、元のビットストリームの動きベクトルと予測ベクトルとに基づいて、後段での動き探索の探索範囲を限定することができるようになる。
【００８５】
図示実施例に従って本発明を説明したが、本発明はこれに限定されるものではない。例えば、実施例では、図形種別情報入力部２０２を備えることで、外部から再探索範囲の図形種別を指定できるようにするという構成について開示したが、図形種別情報入力部２０２を備えずに、再探索範囲の図形種別を予め規定のものに決めておくようにするという構成を採ってもよい。
【００８６】
また、実施例では、元のビットストリームは復号済みとしたが、逐次復号処理を行うことも可能である。また、実施例では、再符号化処理としたが、元動きベクトルと映像信号とを入力できれば、後段での符号化処理が可能なため、前段を動き探索部としての映像信号からの符号化処理も可能となる。
【産業上の利用可能性】
【００８７】
本発明によれば、符号化効率の低下を抑制できるようになるとともに、探索点数についても抑えることができるようなることから、演算コストを削減できるようになる。
【符号の説明】
【００８８】
１      映像符号化装置
１０    動き探索部
２０    再探索範囲限定部
２００  予測ベクトル入力部
２０１  元動きベクトル入力部
２０２  図形種別情報入力部
２０３  再探索範囲設定部
２０４  図形パラメータ記憶部
【図１】
0005467701.tif 000002
【図２Ａ】
0005467701.tif 000003
【図２Ｂ】
0005467701.tif 000004
【図２Ｃ】
0005467701.tif 000005
【図２Ｄ】
0005467701.tif 000006
【図３】
0005467701.tif 000007
【図４】
0005467701.tif 000008
【図５】
0005467701.tif 000009
【図６】
0005467701.tif 000010
【図７】
0005467701.tif 000011
【図８Ａ】
0005467701.tif 000012
【図８Ｂ】
0005467701.tif 000013
【図９Ａ】
0005467701.tif 000014
【図９Ｂ】
0005467701.tif 000015
【図１０】
0005467701.tif 000016
【図１１】
0005467701.tif 000017