JP4577048B2 - 画像符号化方法、画像符号化装置および画像符号化プログラム - Google Patents

Description

本発明は、ＭＰＥＧ等の技術に基づいて動画像、あるいは静止画像を符号化する装置、方法、およびプログラムに関する。

近年、動画像の符号化が衛星放送、蓄積媒体等に広く応用されている。圧縮方法としてＭＰＥＧ２ Ｖｉｄｅｏが広く用いられており、規格は非特許文献３に述べられている。ＭＰＥＧ２は動き補償とＤＣＴ（離散コサイン変換）を用いた圧縮技術である。

非特許文献１に基づいてＭＰＥＧ２の符号化装置について簡単に説明する。図３はエンコーダの基本構成を示すものであり、非特許文献１のｐ．７１の図を元にしている。図３に基づいて符号化処理について説明する。

ビデオ入力がアナログ入力の場合はＡ／Ｄ変換部５０によりデジタル化される。入力の解像度と符号化の解像度が異なっている場合はフォーマット変換部５１で空間解像度が変換される。

ピクチャタイプにはＩ、Ｐ、Ｂの３種類がある。Ｂピクチャは入力順（表示順）で後のＩ、Ｐピクチャが符号化された後に符号化されるため、画面並び替え部５２で画面の並び替えを行い、符号化順のフレーム順序に変換する。

各画面に対して符号化はマクロブロック（１６画素×１６画素）単位に行われる。マクロブロックの符号化の順序は画面で左から右へ、また上から下への順である。Ｉピクチャでは全てのマクロブロックがイントラ符号化（他のピクチャを参照しない）される。Ｐピクチャ、Ｂピクチャではマクロブロックはイントラ符号化あるいはインター符号化（他のピクチャを参照する）される。インター符号化では動きベクトル検出部６０で検出された動きベクトルを用いて、動き補償モード選択部６１によって他のピクチャから予測し、予測値との差分を符号化する。図３に示したのはインター符号化の場合である（イントラ符号化の場合は動き補償を行わない）。

各マクロブロック（ＭＢ）に対する処理を説明する。イントラの場合は輝度の４個のブロック（８×８）と色差の２個のブロック（８×８）に対してＤＣＴ部５３によりＤＣＴが行われる。インター符号化の場合は動きベクトルに基づいて動き補償予測されて、予測値との差分である４個の輝度のブロックと２個の色差のブロックに対してＤＣＴが行われる。

ＤＣＴの結果、ＤＣＴ係数が出力される。ＤＣＴ係数は量子化部５４で量子化され、可変長符号化部５５で可変長符号化（ＶＬＣ）されて出力される。出力のビットレートに制約がある場合は、レート制御部５７によってレート制御が行われて、量子化ステップに反映される。

量子化後のデータはローカルデコードされる。量子化後のＤＣＴ係数は逆量子化部５８で逆量子化され、逆ＤＣＴ部５９で逆ＤＣＴされ、動き補償されて（インター符号化の場合）、ビデオメモリ６２に一時保存される。ビデオメモリに保存されたローカルデコード画像はＰピクチャ、Ｂピクチャの符号化で参照フレームとして用いられる。

非特許文献１に基づいてＭＰＥＧ２の復号化装置について簡単に説明する。図４はデコーダの基本構成を示すものであり、非特許文献１のｐ．７１の図を元にしている。図４に基づいて復号化処理について説明する。

入力されたデータが可変長復号化部７１によって可変長復号され、量子化ＤＣＴ係数と動きベクトルその他の情報が分離される。量子化ＤＣＴ係数は逆量子化部７２によって逆量子化され、逆ＤＣＴ部７３によって逆ＤＣＴされて画像データとなる。インター符号化されたマクロブロックの場合は、さらに動きベクトルを用いて動き補償部７７によって動き補償された画像データが加算される。

復号化においてもマクロブロックの処理順序は符号化と同じく、左から右へ、また上から下への順である。１フレーム分のデコードが終るとＩピクチャ、Ｐピクチャは他のフレームをデコードするときの参照フレームとして用いるためにビデオメモリ７８に一時保存される。後からデコードされたＢピクチャが表示順で先になることがあり、この場合、メモリに保存されている画像を用いて画面並び替え部７４によってフレームの出力順序を並び替える。

ハードウェアによるエンコード、デコードにおいては、前述のマクロブロックに対する処理をパイプライン方式で行うことがある。マクロブロックに対するパイプライン処理について非特許文献２に基づいて説明する。図５は非特許文献２のｐ．１２６を元にして作成したマクロブロックのパイプライン処理の概念図である。非特許文献２のエンコーダは２個のＤＳＰを用いた構成になっているため、ＤＳＰ間の転送処理（ステージ３）が入っているが、１個のＤＳＰで構成されていれば転送処理は不要である。

図５に基づいてマクロブロックのパイプラン処理について説明する。図５（ａ）はマクロブロックに対して行われる各ステージの処理内容である。ステージは処理のタイミングを示すものであり、１個のステージの処理が必ずしも１個の回路ユニットで行われるわけではない。

１個のマクロブロックに対してステージ０からステージ６までの処理が行われる。ステージ０ではデータ入力が行わる。ステージ１ではフレーム／フィールドＤＣＴの選択と動き補償モード選択が行われる。ステージ２ではＤＣＴが行われる。ステージ３では２つのＤＳＰの間で転送が行われる。ステージ４では量子化と逆量子化が行われる。ステージ５では可変長符号化と逆ＤＣＴが行われる。ステージ６ではフレーム再構成が行われる。

図５（ｂ）を参照してマクロブロックのパイプラン処理を時間の経過に従って説明する。ＭＢ０がステージ０に入る。ＭＢ０がステージ０の処理が終了してステージ１に１に入り、それと同時に新たなＭＢ１がステージ０に入る。ＭＢ０がステージ２に入り、それと同時にＭＢ１がステージ１に入り、新たなＭＢ２がステージ０に入る。このようにしてステージ０からステージ６までの７個のステージが並列に動作する。各マクロブロックに対しては７ステージの処理が必要であるが、７個のステージが並列に動作するため、１ステージの時間ごとに１個のマクロブロックの処理が完了する。マクロブロックの処理をパイプラン化することにより、パイプラン化しなかった場合の最大７倍の速度で処理することができる。ＭＥＰＧのエンコードの高速化においてパイプライン処理の効果は大きい。

図５に基づきエンコーダのパイプライン処理について説明したが、デコードにおいても同様に、マクロブロックの処理を適当なステージに分割し、各ステージを並列に動作させることによりパイプライン処理することが可能である。デコードにおいてもパイプライン処理することにより速度を上げることができる。
テレビジョン学会編「ＭＰＥＧ」オーム社、2001年、p.69-71. 祇園、他６名「リアルタイムＭＰＥＧ２コーデック用ＤＳＰ（ＶＤＳＰ２）」ナショナルテクニカルレポート、1994年、Vol.40、ナンバー６、p.122-128. ISO/IEC 13818-2, Information technology - Generic coding of moving pictures and associated audio information: Video. ITU-T H.264, Advanced video coding for generic audiovisual services. ITU-T T.81, Information technology - Digital compression and coding of continuous-tone still images - Requirements and guidelines. Joint Video Team (JVT) software, http://iphome.hhi.de/suehring/tml/index.htm Yu-Wen Huang, Tu-Chih Wang, Bing-Yu Hsieh and Liang-Gee Chen, "Hardware architecture design for variable block size motion estimation in MPEG-4 AVC/JVT/ITU-T H.264", IEEE Int Symp Circuits Syst, 2003 Vol 2, p.796-799, 2003. Gary J. Sullivan and Thomas Wiegand, "Rate-Distortion Optimization for Video Compression", IEEE Signal Processing Magazine, Nov 1998, p.74-90, 1998.

以上説明したように、前記のＭＰＥＧエンコーダの基本構成をマクロブロックパイプライン処理で実装した従来のエンコーダは、フレーム間の予測を含む符号化を高速で処理することができる。

しかしながら、従来の符号化装置はフレーム内予測を含む符号化においてはパイプラン処理が難しいという課題がある。なぜならば、フレーム間予測の場合は参照フレームのエンコード、ローカルデコードが既に完了しているのに対して、フレーム内予測の場合は、参照する領域の処理がマクロブロックパイプラインの途中にある可能性があるためである。

例えば、マクロブロックの符号化において同じフレーム内の左のマクロブロックをイントラ予測（後述）に用いる場合は、左のマクロブロックのエンコード、ローカルデコードが完了するまで、エンコードしようとしているマクロブロックの予測を行うことができない。そのため、従来例のように各ステージの処理を並行動作することができないので、マクロブロックのパイプライン処理を実装することが困難である。

以下にイントラ予測について詳しく説明する。イントラ予測を用いた符号化方法としてＨ．２６４がある。Ｈ．２６４の規格は非特許文献４に述べられている。Ｈ．２６４はフレーム間予測、イントラ予測、整数変換、エントロピー符号化、デブロッキングフィルタなどの技術を用いているが、本発明と関係があるイントラ予測について非特許文献４に基づいて説明する。Ｈ．２６４の符号化はＭＰＥＧ２と同様にマクロブロック単位で行われる。

Ｈ．２６４のイントラ予測について説明する。イントラ予測は同じフレーム内の既にデコードされた画素を参照して予測し、入力画像と予測値の差分を符号化することにより符号量を減少させる技術である。イントラ予測において参照される領域は、符号化する領域に先だってエンコード、ローカルデコードされていなければならない。

Ｈ．２６４のイントラ予測には１６×１６と４×４の２種類がある。図１０はＨ．２６４のマクロブロック（１６×１６）とブロック（４×４）を示している。４×４のブロックは１６×１６のマクロブロックを１６等分したものである。

図１１を参照してイントラ１６×１６予測を説明する。以下、輝度について説明するが、色差についても同様である。マクロブロックＡが符号化する現在マクロブロックである。●（黒い丸印）で示した３３個の画素がマクロブロックＡのイントラ１６×１６予測に参照画素として用いられる。マクロブロックＡが画面周辺部にあり参照画素が存在しない場合は、参照画素の値として１２８が用いられる（画素値は８ビットである）。

３３個の参照画素を用いてマクロブロックＡの２５６個の画素を予測する。イントラ１６×１６の予測方法は４種類のモードがあり、vertical、horizontal、DC、planeと呼ばれている。予測方法の詳細は本発明の本質と関係ないので省略する。

重要なことは、マクロブロックＡをエンコードするときに、参照する画素が利用可能でなければならないことである。そのためには、マクロブロックＡのエンコードに用いる参照画素を含む左のマクロブロックＢ、上のマクロブロックＣ、左上のマクロブロックＤのエンコードとローカルデコードが完了している必要がある。マクロブロックＢ、Ｃ、Ｄのエンコードが完了した後でなければマクロブロックＡのエンコードを開始することができない。

図９（ａ）は従来のエンコーダによるマクロブロックの符号化順序を示している。従来のエンコーダでは、マクロブロックＡの直前にエンコードするのは左のマクロブロックＢである。エンコーダはマクロブロックＢの処理が完了するまで、マクロブロックＡに対してイントラ１６×１６予測を行うことができない。従って、マクロブロックの処理を順次に行う必要があり、パイプラン処理が困難であるという課題がある。

簡単のためマクロブロックの処理がステージ０、ステージ１の２つのステージで行われる場合について説明する。ここで、ステージ０はイントラ予測のモード選択を含む処理を行い、ステージ１はステージ０の結果を用いてエンコードとローカルデコードを行う。現在マクロブロックのイントラ予測のために左のマクロブロックのエンコード、ローカルデコード結果を用いる。左のマクロブロックのステージ１が完了するまで現在マクロブロックのステージ０を開始することができないので、各ステージを並行動作させることができない。マクロブロックの各ステージの処理を図９（ｂ）に示す。

図１２を参照してイントラ４×４予測を説明する。マクロブロックＡが符号化する現在マクロブロックである。ブロックａが符号化する４×４のブロックである。●（黒丸）で示した１３個の画素がブロックａのイントラ４×４予測で参照画素として用いられる。イントラ４×４の予測方法は９種類のモードがあり、vertical、horizontal、DC、diagonal down left、diagonal down right、vertical right、horizontal down、vertical left、horizontal upと呼ばれる。予測方法の詳細は本発明の本質と関係ないので省略する。

ブロックａのイントラ４×４予測において、マクロブロックＢ、マクロブロックＣ、マクロブロックＤの画素を参照するので、マクロブロックＡのエンコードに先だって、マクロブロックＢ、Ｃ、Ｄの処理が完了している必要がある。さらに、ブロックａがｂの位置にある場合を考えると、ブロックｂはマクロブロックＥの画素を参照するので、マクロブロックＡのエンコードに先立ち、マクロブロックＥの処理が完了している必要がある。結局、マクロブロックＡのエンコードに先だって、マクロブロックＢ、Ｃ、Ｄ、Ｅのエンコードとローカルデコードが完了している必要がある。

イントラ１６×１６予測の場合と同様に、イントラ４×４の予測においても、マクロブロックＢ、Ｃ、Ｄ、Ｅのエンコードが完了した後でなければマクロブロックＡのエンコードを開始することができない。そのため、マクロブロックの処理を順次に行う必要があり、パイプラン処理が困難であるという課題がある。

符号化の規格によっては、マクロブロックの符号化において動きベクトルを符号化しないで、周囲のマクロブロックの動きベクトルから動きベクトルを決めるような符号化方法がある。このようなマクロブロックの符号化方法はＨ．２６４では「スペーシャルダイレクトモード」と呼ばれる。

非特許文献４に基づいてＨ．２６４のスペーシャルダイレクトモードについて説明する。Ｈ．２６４ではＢピクチャの中のブロックをスペーシャルダイレクトモードで符号化することができる。図８はスペーシャルダイレクトモードの説明図である。ブロックＡがスペーシャルダイレクトモードで符号化するブロックである。ブロックＡは１６×１６あるいは８×８である。ブロックＢは、ブロックＡの左上の画素の左に位置する画素を含むブロックである。ブロックＣは、ブロックＡの左上の画素の上に位置する画素を含むブロックである。ブロックＤは、ブロックＡの右上の画素の右上に位置する画素を含むブロックである。ブロックＡ、Ｂ、Ｃ、Ｄは同じフレーム内にある。

スペーシャルダイレクトモードで符号化するブロックＡに対しては、動きベクトルを符号化しない。デコード時にはブロックＢ、Ｃ、Ｄの動きベクトルのメジアン（中央値）によってブロックＡの動きベクトルを決める。ブロックＡの動きベクトルを符号化しないことによって、符号量を減らすことができる。

ブロックをスペーシャルダイレクトモードで符号化する場合は、同じフレーム内の符号化するブロックの左、上、右上のブロックの動きベクトルを用いる。そのため、マクロブロック内にスペーシャルダイレクトモードで符号化するブロックが存在する場合は、現在マクロブロックをエンコードする前に左、上、右上のマクロブロックのエンコードが完了している必要がある。

スペーシャルダイレクトモードを用いる符号化においては、イントラ予測の場合と同様に、現在マクロブロックの左、上、右上のマクロブロックのエンコードが完了した後でなければ現在マクロブロックのエンコードを開始することができない。そのため、マクロブロックの処理を順次に行う必要があり、パイプラン処理が困難であるという課題がある。

本発明は、イントラ予測を行うような符号化方法であっても、マクロブロックのパイプライン処理が可能な画像符号化装置を提供することを目的とする。また、本発明のもう一つの目的は、スペーシャルダイレクトを用いるような符号化方法であっても、マクロブロックのパイプライン処理が可能な画像符号化装置を提供することである。

また、本発明の他の目的は、ＰＭＶ（予測動きベクトル）を用いる符号化方法において動きベクトル探索とエンコードをパイプライン処理することが可能な画像符号化装置を提供することである。また、ＰＭＶを用いる符号化方法において複数のマクロブロックに対する動きベクトル探索を並列に行うことが可能な画像符号化装置を提供することである。

前記従来の課題を解決するために、本発明の画像符号化装置は、背景技術で説明した従来のエンコーダに対してマクロブロックの符号化順序を選択する手段を付加したことを特徴とし、イントラ予測あるいはスペーシャルダイレクトモードを用いる場合であってもマクロブロックのパイプライン処理を行うことができる。

本発明のマクロブロックの符号化順序の選択手段は、横１行分のマクロブロックの符号化が完了する前に次の行のマクロブロックの符号化を開始することを特徴とする。さらに、前記順序を選択する手段は現在マクロブロックのイントラ予測に用いるマクロブロック、あるいは現在マクロブロックのスペーシャルダイレクトモード予測に用いるマクロブロックの符号化の順序番号が現在マクロブロックの順序番号よりも２以上大きい（間に１つ以上のマクロブロックが存在する）ことを特徴とする。

本発明の画像符号化装置によれば、イントラ予測を用いる符号化方法においてマクロブロックのパイプラン処理が可能となり、処理速度を上げることが可能となる。

また、本発明の画像符号化装置によれば、スペーシャルダイレクトを用いる符号化においてマクロブロックのパイプライン処理が可能となり、処理速度を上げることが可能となる。

また、本発明の画像符号化装置によれば、ＰＭＶ（予測動きベクトル）を用いる符号化方法において動きベクトル探索とエンコードをパイプライン処理することが可能となり、処理速度を上げることが可能となる。

また、本発明の画像符号化装置によれば、ＰＭＶを用いる符号化方法において複数のマクロブロックに対する動きベクトル探索を並列に行うことが可能となり、処理速度を上げることが可能となる。

以下本発明の実施の形態について、図面を参照しながら説明する。

（実施の形態１）
図１は本発明による画像符号化装置の基本構成である。従来の装置構成との相違はマクロブロック順序選択部１３が追加されたことである。本実施の形態の目的は、Ｈ．２６４のイントラ１６×１６予測を用いる符号化方法の場合に、マクロブロックのパイプラン処理を容易にすることである。前述のように、イントラ１６×１６予測では現在マクロブロックの左、上、左上の３個のマクロブロックを予測に用いる。説明を簡単にするために、ピクチャ全体が１つのスライスであるとする（Ｈ．２６４の規格では可能）。Ｈ．２６４ではＤＣＴの代わりにＤＣＴを整数演算で近似した整数変換を用いるが、本発明の本質とは関係ないので、以下の説明ではＤＣＴとする。

図１に基づいて動作を説明する。マクロブロック順序選択部１３は次にエンコードするマクロブロックを選択する。動きベクトル検出、イントラ予測部１７は選択されたマクロブロックに対してインター予測モードの動きベクトルの検出とイントラ予測のモードの選択を行う。動き補償モード選択部１８は選択されたマクロブロックに対してイントラ予測、インター予測、スキップ等の符号化モードの選択を行う。ＤＣＴ部１４は選択されたマクロブロックのイントラ予測の残差あるいはインター予測の残差に対してＤＣＴを行う。量子化部１５はＤＣＴ係数を量子化する。エントロピー符号化部２１はＤＣＴ係数をエントロピー符号化する。エントロピー符号化にはＨ．２６４の規格によって可変長符号化と算術符号化がある。逆量子化部１９は量子化されたＤＣＴ係数を逆量子化する。逆ＤＣＴ部２０は逆量子化されたＤＣＴ係数に対して逆ＤＣＴを行う。

図１３は本実施の形態におけるマクロブロック順序選択部１３が次にエンコードするマクロブロック（ＭＢとする）を選択する方法のフローチャートである。図１３を参照してマクロブロック順序選択部の動作を説明する。現在のマクロブロックの座標を（ｉ、ｊ）として、次にエンコードするマクロブロックの座標（ｖ、ｈ）を求める。第１座標は垂直方向の位置を示し、下方向に増加する。第２座標は水平方向の位置を示し、右方向に増加する。ＭＢ（ｉ、ｊ）は座標（ｉ、ｊ）のマクロブロックを表わす。

座標（ｉ＋１、ｊ−１）にマクロブロックが存在するかどうか調べ（ステップＳ１０）、存在する場合、そのマクロブロックを次のマクロブロックとする（ステップＳ１１）。座標（ｉ＋１、ｊ−１）にマクロブロックが存在しない場合、以下の（１）から（３）を行う。

（１）エンコードされていないマクロブロックが存在する最小の第１座標をｖとする（ステップＳ１２）。

（２）第１座標がｖのエンコードされていないマクロブロックの中で最も左のマクロブロックの第２座標をｈとする（ステップＳ１３）。

（３）座標（ｖ、ｈ）のマクロブロックを次のマクロブロックとする（ステップＳ１４）。

上の（１）においてエンコードされていないマクロブロックが存在しない場合、終了とする。

図６（ａ）は図１３の方法によりマクロブロックに順序をつけた例である。四角がマクロブロックを示し、四角の中の数字がマクロブロックの順序を示す。図ではフレームサイズが水平８マクロブロック、垂直４マクロブロックの場合を示しているが、他のフレームサイズでも同様である。

図６（ｂ）は本実施の形態の順序でマクロブロックをエンコードしたときのパイプラン処理の概念図である。簡単のため、マクロブロックの処理をステージ０とステージ１に分割して、２段のパイプライン処理を行う場合について説明する。ステージ０はイントラ１６×１６予測のモード選択を含む処理を行い、ステージ１はステージ０の結果を用いてエンコードとローカルデコードを行うとする。例として、ＭＢ４をエンコードする場合について説明する。ＭＢ４のイントラ１６×１６予測ではＭＢ０、ＭＢ１、ＭＢ２を参照するので、ＭＢ４のエンコードの前にこれら３個のマクロブロックのエンコードとローカルデコードが完了している必要がある。図６（ｂ）に示すように、ＭＢ４の前にＭＢ３がエンコードされるため、ＭＢ４のエンコードの開始時点でＭＢ０、ＭＢ１、ＭＢ２の処理が完了している。そのため、ＭＢ３のステージ０の完了直後に、ＭＢ４のステージ０を開始することができる。このようにしてパイプラン処理が可能となる。

本実施の形態の装置でエンコードされたマクロブロックはエンコード順に出力しても良いし、フレーム全体のエンコードが完了した後にＨ．２６４の規格に合うように通常のラスタ順に並べ替えて出力しても良い。また、出力ストリームの中にエンコード順かラスタ順かの識別情報を持たせて、いずれかを選択するようにすることも可能である。マクロブロックをエンコード順に出力する場合は、符号化装置から出力されるストリームにマクロブロックのフレーム内の位置を示す情報を含むようにする。マクロブロックをラスタ順に出力する場合は、マクロブロックのエンコード順序を示す情報を含むようにする。

マクロブロックの位置を示すことは、マクロブロックに対してフレーム内の座標（ｉ、ｊ）に対応する情報を付加することにより行うことができるが、他の方法、例えば、マクロブロックの位置を導くことができる情報を付加することによっても可能である。他の方法としては、ピクチャヘッダの中にピクチャ全体のマクロブロックの順序付けの方法を示す識別子を付加する方法がある。あるいは、スライスヘッダの中にスライス内のマクロブロックの順序付け方法の識別子を付加する方法であってもよい。あるいは、シーケンスヘッダの中にシーケンス内のピクチャのマクロブロックの順序付け方法の識別子を付加する方法であっても良い。

なお、本実施の形態ではマクロブロックをエンコードする順序を図１３で示す方法で選択したが、現在マクロブロックと、左、上、左上の３個のマクロブロックの順序番号の差が２以上であるような順序付けであれば、他の選択方法であっても同様に実施可能である。

なお、本実施の形態は２段のパイプラン処理について説明したが、３段以上のパイプラン処理を行うことも可能である。例えば、図６（ａ）ではＭＢ６以降は左、上、左上のマクロブロックとの順序番号の差が３以上なので、３段のパイプラン処理が可能である。同様に、ＭＢ１０以降は左、上、左上のマクロブロックとの順序番号の差が４以上なので、４段のパイプラン処理が可能である。ただし、フレームの左上端と右下端ではパイプラン処理が可能な段数は小さくなる。

なお、以上の説明ではピクチャ全体が１つのスライスとしたが、複数のスライスに分かれている場合であっても、スライスごとに本実施の形態によるマクロブロックの順序付けによって符号化を行うことにより同様に実施可能である。

なお、以上の説明ではフレームピクチャについて説明したが、フィールドピクチャについても同様に実施可能である。フィールドピクチャの場合はフィールドに分けた後にマクロブロックに分割し、マクロブロックに対する処理（エンコーダの場合はエンコード、デコーダの場合はデコード）を上記の説明の順序で行う。

なお、本発明は、コンピュータとプログラムで実施されることがあり、そのプログラムは記録媒体に記録されることがある。このことは本発明の他の実施の形態についても同様である。

（実施の形態２）
本実施の形態における画像符号化装置の基本構成は実施の形態１と同じである。実施の形態１と異なるのはマクロブロック順序選択部１３の動作である。本実施の形態はＨ．２６４の４×４のイントラ予測を含む符号化方法であってもマクロブロックのパイプラン処理を可能とすることを目的とする。前述のように、イントラ４×４予測では現在マクロブロックの左、上、左上、右上の４個のマクロブロックを予測に用いる。

図１４は本実施の形態のマクロブロック順序選択部が、次にエンコードするマクロブロックを選択する方法のフローチャートである。図１４を参照して動作を説明する。現在マクロブロックの位置が座標（ｉ、ｊ）とする。第１座標が垂直位置を示し、下方向に増加する。第２座標が水平位置を示し、右方向に増加する。座標（ｉ＋１、ｊ−２）のマクロブロックが存在するかどうか調べ（ステップＳ２０）、存在する場合、そのＭＢ（ｉ＋１、ｊ−２）を次のマクロブロックとする（ステップＳ２１）。座標（ｉ＋１、ｊ−２）のマクロブロックが存在しない場合は以下の（１）から（３）を実行する。

（１）まだ符号化されていないマクロブロックが存在する最小の第１座標をｖとする（ステップＳ２２）。

（２）第１座標がｖの符号化されていないマクロブロックの中で最も左のマクロブロックの第２座標をｈとする（ステップＳ２３）。

（３）座標（ｖ、ｈ）のマクロブロックを次にエンコードするマクロブロックとする（ステップＳ２４）。

上の（１）において符号化されていないマクロブロックが存在しない場合、終了とする。

図７（ａ）は図１４の方法によって選択したマクロブロックの符号化順序である。図７（ｂ）はマクロブロックのパイプラン処理を示す。図では簡単のため、２段のパイプランで処理する場合を示している。ステージ０はイントラ４×４予測のモード選択を含む処理を行い、ステージ１はステージ０の結果を用いてエンコード、ローカルデコードを行うとする。

例として、ＭＢ５をエンコードする場合について説明する。ＭＢ５のイントラ４×４予測ではＭＢ０、ＭＢ１、ＭＢ２、ＭＢ３の４個のマクロブロックを予測に用いる。ＭＢ５のエンコード開始までに予測に用いるこれらの４個のマクロブロックのエンコードとローカルデコードが完了している必要がある。本実施の形態のマクロブロック順序選択によれば、ＭＢ５とこれら４個のマクロブロックの順序の差が２以上となるので、ＭＢ５のエンコードを開始する時点でこれらの４個のマクロブロックの処理が完了している。従って、ＭＢ４のステージ０の完了直後に、ＭＢ５のステージ０を開始することができる。それによって、図７（ｂ）に示すように２段のパイプラン処理が可能となる。

なお、本実施の形態は２段のパイプラン処理について説明したが、３段以上のパイプラン処理を行うことも可能である。例えば、図７（ａ）ではＭＢ９以降は、現在マクロブロックと現在マクロブロックが参照する左、上、左上、右上の４個のマクロブロックとの順序番号の差が３以上なので、３段のパイプラン処理が可能である。同様に、ＭＢ１６以降は現在マクロブロックと左、上、左上、右上のマクロブロックとの順序番号の差が４以上なので、４段のパイプラン処理が可能である。ただし、フレームの左上端と右下端ではパイプラン処理が可能な段数は小さくなる。

なお、本実施の形態ではマクロブロックをエンコードする順序を図１４で示す方法で選択したが、現在マクロブロックと、左、上、左上、右上の４個のマクロブロックの順序番号の差が２以上であるような順序付けであれば、他の選択方法でも同様に実施可能である。

実施の形態１においてイントラ１６×１６予測を含む符号化を２段のパイプラン処理できるための条件は、現在マクロブロックと左、上、左上の３個のマクロブロックの順序番号の差が２以上となることである。実施の形態２においてイントラ４×４予測を含む符号化を２段のパイプラン処理できるための条件は、現在マクロブロックと左、上、左上、右上の４個のマクロブロックの順序番号の差が２以上となることである。実施の形態２の条件を満たせば実施の形態１の条件を満たすので、実施の形態２の符号化装置はイントラ１６×１６予測に対してもマクロブロックのパイプラン処理が可能である。３段以上のパイプライン処理についても実施の形態２の条件を満たせば実施の形態１の条件を満たすので、同様に実施可能である。

本実施の形態の装置でエンコードされたマクロブロックはエンコード順に出力しても良いし、フレーム全体のエンコードが完了した後に通常のラスタ順に並べ替えて出力しても良い。また、出力ストリームの中にエンコード順かラスタ順かの識別情報を持たせて、いずれかを選択するようにすることも可能である。

なお、マクロブロックを横方向の２列単位に区切って、エンコード順序を図１８（ａ）のようにしても同様に実施可能である。このような順序にすることにより、マクロブロックのエンコードが終わった後にラスタ順に並び替えて出力する場合、マクロブロックのエンコードが終わってから出力するまでの中間データのデータ量を小さくすることができる。また、マクロブロックのエンコード順序を図１８（ｂ）のようにしても同様に実施可能である。図１８（ａ）の順序ではＭＢ１４、ＭＢ１５、ＭＢ１７は左のマクロブロックとの順序番号の差が１なので、これらのマクロブロックはパイプライン処理することができない。図１８（ｂ）の順序とすることによりこれらのマクロブロックについてもパイプライン処理を行うことが可能となる。

なお、マクロブロックを横方向の３列単位に区切って、図１９の順序でエンコードしても同様に実施可能である。このような順序とすることにより、マクロブロックを３段のパイプラン処理することを可能とし、かつ、マクロブロックのエンコードが終わった後にラスタ順に並び替えて出力する場合、マクロブロックのエンコードが終わってから出力するまでの中間データのデータ量を小さくすることができる。

なお、ピクチャ構造がフレームであってもフィールドであっても同様に実施することができる。フィールドピクチャの場合はフィールドごとに前述の順序でマクロブロックをエンコードする。

（実施の形態３）
図２は本発明の実施の形態３における復号化装置の基本構成図である。従来の装置構成との差異はマクロブロック順序選択部３９が存在することである。本実施の形態の目的は、イントラ１６×１６予測を含む符号化方法によって符号化されたストリームをマクロブロックのパイプラン処理によって復号することを容易にすることである。

図２に基づいて動作を説明する。マクロブロック順序選択部３９は可変長復号化部３１からマクロブロックの位置情報を受け取る。マクロブロック順序選択部３９は後述のマクロブロック順序選択方法に基づいて、次にデコードするマクロブロックを選択する。動き補償部３７は選択されたマクロブロックに対して動き補償を行い、ビデオメモリ部３８は選択されたマクロブロックをフレーム内の対応する位置に格納する。

前記マクロブロック位置情報はデコードするマクロブロックのフレーム内における位置を示す情報である。具体的には、マクロブロックごとにもつピクチャ内の座標、あるいはピクチャヘッダに含まれるピクチャ内のマクロブロックの順序を示す情報、あるいはスライスヘッダに含まれるスライス内のマクロブロックの順序を示す情報、あるいはシーケンスヘッダに含まれるシーケンス内のピクチャのマクロブロックの順序を示す情報である。ピクチャヘッダ、スライスヘッダ、シーケンスヘッダに含まれるマクロブロックの順序を示す情報とは、マクロブロックの順序を規定する識別子、あるいはピクチャ内のマクロブロックに対する座標と符号化順序の対応表である。ストリーム内のマクロブロックの格納順序が図９（ａ）に示すようなラスタ順でなくても、前記識別子あるいは前記対応表によってマクロブロックのフレーム内の位置を知ることができる。

以下、イントラ予測を含む符号化方法でエンコードされたストリームを復号する場合について説明する。

マクロブロックのストリームの中の格納順序とマクロブロックのデコード順序が一致することもあり、異なることもある。一致する場合の例として、ストリーム中の順序とデコード順序がともに図６（ａ）に示す順序の場合や、ストリーム中の順序とデコード順序がともに図７（ａ）に示す順序の場合がある。異なる場合の例として、ストリーム中の順序が図９（ａ）でデコード順序が図６（ａ）の場合や、ストリーム中の順序が図９（ａ）でデコード順序が図７（ａ）の場合がある。マクロブロックのストリーム中の出現順序とデコード順序が異なる場合は、後述の方法によりマクロブロックのデコード順序を選択する。

符号化ストリームの中にマクロブロックごとの座標が含まれている場合は、マクロブロック順序選択部はその座標からフレーム内の位置を決定する。符号化ストリームのピクチャヘッダ、スライスヘッダあるいはシーケンスヘッダにマクロブロックの順序を示す識別子が含まれている場合は、識別子が示す手順にしたがってマクロブロックのフレーム内の位置を決定する。

例えば、識別子が示すマクロブロックの格納順序が図１３のフローチャートの手順の場合、図１３の手順に基づいてマクロブロックのフレーム内の位置を決定する。この場合、ストリーム中のマクロブロックの格納順序は図６（ａ）のようになる。このようにして、デコードされたマクロブロックをフレーム内の正しい位置に配置することができる。

本実施の形態におけるマクロブロック順序選択部３９はマクロブロックのデコード順序を図１３のフローチャートによって選択する。ストリーム中のマクロブロックの格納順序は図６（ａ）の順序のこともあり、他の順序、例えば、図９（ａ）の順序のこともある。マクロブロックのストリーム中の格納順序とデコード順序が同じ場合は、可変長復号された順にデコードする。マクロブロックのストリーム中の格納順序とデコード順序が異なる場合は、可変長復号後にマクロブロックのデータを一時的に保存しておき、順序選択部がデコードするマクロブロックの順序を選択する。

イントラ１６×１６予測のデコードでは現在マクロブロックの左、上、左上の３個のマクロブロックを参照するので、現在マクロブロックをデコードする前にこれらの３個のマクロブロックのデコードが完了している必要がある。図１３の手順により選択されるマクロブロックのデコード順序は図６（ａ）に示す順序となる。本実施の形態の復号装置は現在マクロブロックと現在マクロブロックの左、上、左上の３個のマクロブロックのデコード順序の差が２以上となる（左上端と右下端を除く）。

本実施の形態の復号装置によるマクロブロックのデコードのパイプラン処理について説明する。簡単のため、パイプラインはステージ０とステージ１の２段とし、各段の処理時間は等しいとする。ステージ０がイントラ１６×１６予測のデコードを含む処理を行い、ステージ１が残りの処理を行うとする。例として、ＭＢ４のデコードについて説明する。ＭＢ４がイントラ１６×１６予測を用いてエンコードされていたとする。ＭＢ４のデコードではＭＢ０、ＭＢ１、ＭＢ２を参照するので、ＭＢ４のデコードの前にこれら３個のマクロブロックのデコードが完了している必要がある。ＭＢ４がパイプラインのステージ０に入る前にＭＢ２のステージ１の処理が完了しているので、ＭＢ３のステージ０の完了直後にＭＢ４のステージ０を開始することができる。

なお、本実施の形態は実施の形態１の符号化装置でエンコードされたストリームのデコードについて説明したが、実施の形態２の符号化装置でエンコードされたストリームを復号する場合についても、マクロブロックのデコード順序を図７（ａ）とすることにより同様にパイプラン処理することが可能である。

なお、本実施の形態はマクロブロック処理のパイプラインが２段の場合について説明したが、パイプラインが３段以上の場合についても同様に実施可能である。ＭＢ６以降は現在マクロブロックの順序番号と、イントラ１６×１６で参照する３個のマクロブロック（現在マクロブロックの左、上、左上のマクロブロック）の順序番号の差が３以上となるので、３段のパイプラン処理が可能である。ＭＢ１０以降は現在マクロブロックと参照する３個のマクロブロックとの順序番号の差が４以上となるので、４段のパイプラン処理が可能である。

なお、本実施の形態はマクロブロックの符号化順序が図６（ａ）で示される場合について説明したが、図７（ａ）で示されるような順序に対しても実施可能である。図７（ａ）の順序は図１４のフローチャートに示す手順により求めることができる。図７（ａ）の順序の場合は、現在マクロブロックと現在マクロブロックの左、上、左上、右上の４個のマクロブロックの順序番号の差が２以上となるので、イントラ１６×１６予測とイントラ４×４予測の両方に対して２段のパイプラン処理によるマクロブロックのデコードが可能である。なお、この場合においても前述と同様に３段以上のパイプラン処理が可能である。

本実施の形態の装置でエンコードされたマクロブロックはエンコード順に出力しても良いし、フレーム全体のエンコードが完了した後に通常のラスタ順に並べ替えて出力しても良い。また、出力ストリームの中にエンコード順かラスタ順かの識別情報を持たせて、いずれかを選択するようにすることも可能である。

（実施の形態４）
本実施の形態はエンコーダにおいてＨ．２６４のスペーシャルダイレクトモードの予測を含む符号化方法であっても、マクロブロックのパイプラン処理を可能とすることを目的とする。スペーシャルダイレクトモードについては非特許文献４に述べられている。本実施の形態における画像符号化装置の基本構成は実施の形態１と同じである。実施の形態１と異なるのはマクロブロック順序選択部１３の動作である。本実施の形態におけるマクロブロックのエンコード順序は実施の形態２と同じである。

本実施の形態におけるマクロブロックのエンコード順序を図７（ａ）に示す。図１４のフローチャートに示す方法により、図７（ａ）に示すマクロブロックの順序付けを得ることができる。

図８に示すように、現在マクロブロックＡをスペーシャルダイレクトモードでエンコードするときには、マクロブロックＢ、Ｃ、Ｄの動きベクトルあるいはそれらのマクロブロックに含まれる小ブロックの動きベクトルを用いる。そのため、現在マクロブロックをエンコードする前に左、上、右上の３個のマクロブロックのエンコードが完了している必要がある。

簡単のため、２段のパイプラインでエンコードする場合について説明する。図７（ａ）のマクロブロック順序によれば、現在マクロブロックと現在マクロブロックの左、上、右上の３個のマクロブロックとのエンコード順序番号の差が２以上となるので、図７（ｂ）に示すように２段のパイプラン処理が可能となる。

（実施の形態５）
図１５は本発明の実施の形態５による静止画符号化装置の基本構成図である。本実施の形態が用いる静止画の符号化方法は非特許文献５のＪＰＥＧのベースラインプロファイルを修正したものである。具体的には、マクロブロック単位に符号化し、８×８サイズのＤＣＴ、量子化、変換係数のジグザグスキャン、可変長符号化により符号化するが、以下の２点がＪＰＥＧと異なる。

（１）マクロブロックの符号化において、Ｈ．２６４のイントラ予測と同様の予測を用いて、周囲のマクロブロックから現在マクロブロックを予測し、予測残差を符号化する。

（２）マクロブロックの符号化順序を図６（ａ）あるいは図７（ａ）に示す順序とする。

図１５に基づいて本実施の形態における静止画符号化装置の動作を説明する。マクロブロック順序選択部８６がエンコードするマクロブロックを選択する。マクロブロックの順序は図１３あるいは図１４に示す方法で選択することができる。予測部８０は選択されたマクロブロックに対して、フレームメモリ８７に保存されている現在マクロブロックの周囲のマクロブロックのローカルデコード画像を用いて予測画像を作成する。残差計算部８１は予測の残差を計算する。ＤＣＴ部８２は残差に対してＤＣＴを行う。量子化部８３はＤＣＴ係数を量子化する。ジグザグスキャン部８４はＤＣＴ係数をジグザグスキャンする。可変長符号化部８５はＤＣＴ係数を可変長符号化し、現在マクロブロックを周囲のマクロブロックからどのように予測したかの情報を追加する。逆量子化部８９は量子化されたＤＣＴ係数を逆量子化する。逆ＤＣＴ部８８は逆量子化されたＤＣＴ係数を逆ＤＣＴする。予測に用いた情報と逆ＤＣＴの結果からマクロブロックを再構成し、フレームメモリ８７に保存する。フレームメモリに保存されたマクロブロックは以降のマクロブロックの予測に用いられる。

周囲のマクロブロックのローカルデコード画像から現在マクロブロックを予測する方法として以下の２つがある。

（１）現在マクロブロックの左、上、左上の３個のマクロブロックを用いる。

（２）現在マクロブロックの左、上、左上、右上の４個のマクロブロックを用いる。

ここで、（１）の場合はマクロブロックの符号化順序を図６（ａ）に示すものとする。（２）の場合はマクロブロックの符号化順序を図７（ａ）に示すものとする。

以上のような方法で符号化することにより、マクロブロックの符号化でイントラ予測を用いることができるので、ＪＰＥＧよりも符号量を小さくすることができるという利点がある。また、図６（ａ）あるいは図７（ａ）の順序でマクロブロックをエンコードするので、図６（ｂ）あるいは図７（ｂ）に示すようにマクロブロックをパイプライン処理することが可能である。

なお、以上の説明では静止画符号化装置について説明したが、本実施の形態の静止画符号化装置で符号化されたデータを復号する静止画復号装置においても、符号化装置と同じ順序でマクロブロックをデコードすることにより、マクロブロック単位のパイプラン処理が可能となる。

なお、図６（ｂ）、図７（ｂ）には２段のパイプライン処理する場合について示したが、エンコード、デコードで参照するマクロブロックと現在マクロブロックの順序番号の差が３以上の場合は、エンコード、デコードにおいて３段以上のパイプラン処理が可能である。

（実施の形態６）
図１６は本発明の実施の形態６による符号化装置のためのマクロブロック順序並び替え装置の基本構成図である。本装置の目的はマクロブロックの符号化順序とマクロブロックのストリームへの出力順序が異なる場合に、マクロブロックを並べ替えることである。符号化されたマクロブロックは本装置により順序を並び替えた後に出力される。

図１６に基づいてマクロブロック並び替え装置の動作を説明する。例として、マクロブロックの符号化順序が図７（ａ）であり、マクロブロックの格納順序が図９（ａ）である場合について説明する。

符号化マクロブロック領域は符号化されたマクロブロック（ＭＢ）が格納される。マクロブロックの符号量は一定とは限らずマクロブロックによって異なることがある。ポインタテーブルはエンコード順に格納されたマクロブロックのアドレスを持っている。順序変換テーブルは２つのエントリがあり、第１のエントリはマクロブロックの伝送順序であり、第２のエントリはマクロブロックの符号化順序である。符号化されたマクロブロックは１ピクチャのマクロブロックの符号化が完了するまで伝送されないで、符号化マクロブロック領域に格納され、そのアドレスがポインタテーブルのエントリに格納される。

１ピクチャのマクロブロックの符号化が完了した後、マクロブロックを伝送順に並び替えて出力する。最初に、順序変換テーブルの第１エントリの値が０の第２エントリの値に対応するポインタが指すマクロブロックを出力する。次に、第１エントリの値が１の第２エントリの値に対応するポインタが指すマクロブロックを出力する。それ以降も同様である。このような手順により、図の例では、ポインタテーブルの０、１、２、４、６、９、１２、１６、３、５、７、１０、１３が指すマクロブロックの順に出力する。

なお、本実施の形態のマクロブロック順序並び替え装置は実施の形態１あるいは実施の形態２の画像符号化装置と組み合わせて用いることができる。実施の形態１あるいは実施の形態２の符号化装置によって符号化されたマクロブロックを、本実施の形態の装置によって順序を並べ替える。マクロブロックの符号化順序が図７（ａ）のようになるので、マクロブロック単位のパイプライン処理が可能となる。また、マクロブロックの伝送順序が図９（ａ）のようになるので、Ｈ．２６４の規格に適合したストリームを生成することが可能となる。すなわち、マクロブロックのパイプラン処理によってＨ．２６４の規格に適合したストリームを生成する画像符号化装置を可能とする。

なお、本実施の形態ではマクロブロックの符号化順序が図７（ａ）であり、出力順序が図９（ａ）である場合について説明したが、マクロブロックのエンコード順序あるいは出力順序が本実施の形態と異なる場合であっても、順序変換テーブルを変更することにより、同様に実施可能である。

なお、符号化マクロブロック領域に格納されるマクロブロックはエントロピー符号化された後のマクロブロックであっても、エントロピー符号化される前のマクロブロックであっても良い。エントロピー符号化される前のマクロブロックが格納される場合は、マクロブロックの順序並び替えが行われた後にエントロピー符号化されて出力される。

（実施の形態７）
図１７は本発明の実施の形態７による復号化装置のためのマクロブロック順序並び替え装置の基本構成図である。本装置の目的は、符号化ストリームの中のマクロブロックの格納順序とマクロブロックの復号順序が異なる場合に、マクロブロックを並べ替えることである。入力されたマクロブロックはエントロピー復号化された後、本装置により復号順序を選択されて復号される。

図１７に基づいて本実施の形態におけるマクロブロック順並び替え装置の動作を説明する。例として、マクロブロックの入力順序が図９（ａ）に示すものであり、マクロブロックの復号化順序が図７（ａ）に示すものである場合について説明する。

復号待ちマクロブロック領域には復号待ちのマクロブロック（ＭＢ）が格納される。マクロブロックの符号量は一定とは限らずマクロブロックによって異なることがある。ポインタテーブルはマクロブロックの入力順にエントロピー復号されたマクロブロックが格納されたアドレスを持っている。順序変換テーブルは２つのエントリがあり、第１のエントリはマクロブロックの復号順序であり、第２のエントリはマクロブロックの入力順序である。

入力されてエントロピー復号されたマクロブロックは復号待ちマクロブロック領域に格納される。ポインタテーブルに入力順の復号待ちマクロブロックのアドレスが格納される。１ピクチャの全てのマクロブロックの入力が完了した後、マクロブロックを復号順序によって選択して復号する。

最初に、順序変換テーブルの第１エントリの値が０の第２エントリの値に対応するポインタが指すマクロブロックを復号する。次に、第１エントリの値が１の第２エントリの値に対応するポインタが指すマクロブロックを復号する。それ以降も同様である。図の場合は、このような手順により、ポインタテーブルの０、１、２、８、３、９、４、１０、１６、５、１１、１７、６が指すマクロブロックの順に復号する。

なお、本実施の形態のマクロブロック順序並び替え装置は実施の形態３の画像復号化装置と組み合わせて用いることができる。本実施の形態の装置によって順序を並べ替えた後に、実施の形態３の復号化装置によって復号化する。このようにすることにより、マクロブロックの入力順序が図９（ａ）のようになり、Ｈ．２６４の規格に適合させることができる。また、マクロブロックの復号化順序が図７（ａ）のようになり、マクロブロックの復号のパイプライン処理を可能とすることができる。すなわち、Ｈ．２６４の規格に適合したストリームをパイプライン処理によって復号する画像復号化装置を可能とする。

なお、本実施の形態ではマクロブロックの入力順序が図９（ａ）、復号化順序が図７（ａ）の場合について説明したが、他の順序の場合であっても、順序変換テーブルを変更することにより、同様に実施可能である。

（実施の形態８）
Ｈ．２６４の規格にはＭＢＡＦＦ（macroblock adaptive frame field）と呼ばれるマクロブロックの符号化方法がある。本実施の形態ではＭＢＡＦＦを用いた符号化方法をパイプライン方式で処理する符号化装置について説明する。ＭＢＡＦＦについては非特許文献４に述べられている。ＭＢＡＦＦでエンコードする場合は、上下の２個のマクロブロックをペアにして、マクロブロックペアごとにフレームかフィールドかを選択することができる。マクロブックペアがフレームの場合は２個のマクロブロックを共にフレームとしてエンコードする。マクロブロックペアがフィールドの場合は２個のマクロブロックを共にフィールドとしてエンコードする。マクロブロックペアは上のマクロブロック、下のマクロブロックの順にエンコードする。

図２１（ａ）は従来方法におけるＭＢＡＦＦの場合のマクロブロックの符号化順序である。ＭＢＡＦＦにおいてもイントラ１６×１６予測、イントラ４×４予測、スペーシャルダイレクトモードを用いることができる。これらのモードにおいては現在マクロブロックを含むマクロブロックペア（現在マクロブロックペアと呼ぶことにする）の左、上、左上、右上のマクロブロックペアをエンコードし、ローカルデコードした結果を用いて現在マクロブロックペアをエンコードする。そのため、現在マクロブロックペアのエンコードを開始する前に左、上、左上、右上のマクロブロックペアのエンコード、ローカルデコードが完了している必要がある。１個のマクロブロックのエンコードが２つのステージで行われる場合を例として説明すると、マクロブロックの各ステージの処理タイミングは図２１（ｂ）のようになり、パイプライン処理を行うことが困難である。

図２０（ａ）は本実施の形態におけるマクロブロックの処理順序である。ＭＢ６、ＭＢ７のマクロブロックペアはＭＢ４、ＭＢ５のマクロブロックペアを参照していないので、ＭＢ６、ＭＢ７のマクロブロックペアはＭＢ４、ＭＢ５のマクロブロックペアのエンコード、ローカルデコードの完了を待たずにエンコードを開始することができる。従って、ＭＢ６、ＭＢ７のマクロブロックペアはＭＢ４，ＭＢ５マクロブロックペアとパイプライン処理でエンコードすることができる。同様に、ＭＢ８，ＭＢ９のマクロブロックペアはＭＢ６，ＭＢ７のマクロブロックペアとパイプライン処理でエンコードすることができる。これ以降のマクロブロックペアに対しても同様である。

パイプライン処理の例として１個のマクロブロックの処理が２つのステージで行われる場合について説明する。２つのステージの処理時間は等しいとする。図２０（ｂ）は本実施の形態におけるパイプライン処理のタイミングを説明する図である。ＭＢ４のステージ０が終わると、ＭＢ４のステージ１を開始し、同時にＭＢ６のステージ０を開始する。ＭＢ６のステージ０が終わると、ＭＢ６のステージ１を開始し、同時にＭＢ５のステージ０を開始する。ＭＢ５のステージ０が終わると、ＭＢ５のステージ１を開始し、同時にＭＢ７のステージ０を開始する。ＭＢ７のステージ０が終わると、ＭＢ７のステージ１を開始し、同時にＭＢ８のステージ０を開始する。これ以降も同様にパイプライン処理を行うことができる。

なお、３段以上のパイプライン処理についても同様に実施可能である。ＭＢ１４，ＭＢ１５のマクロブロックペアはＭＢ１２，ＭＢ１３のマクロブロックペアのローカルデコード結果を用いない。また、ＭＢ１６，ＭＢ１７のマクロブロックペアはＭＢ１２，ＭＢ１３のマクロブロックペアとＭＢ１４，ＭＢ１５のマクロブロックペアのローカルデコード結果を用いない。従って、ＭＢ１２，ＭＢ１３のマクロブロックペア、ＭＢ１４，ＭＢ１５のマクロブロックペア、ＭＢ１６，ＭＢ１７のマクロブロックペアの３つのマクロブロックペアは並行してエンコードすることができる。従って、ＭＢ１２，ＭＢ１３のマクロブロックペア以降は３段のパイプライン処理によってエンコードすることができる。フレームサイズが図２０（ａ）より大きい画像に対しては４段以上のパイプライン処理を行うことが同様に実施可能である。

（実施の形態９）
本実施の形態では動きベクトル探索とエンコードをパイプライン方式で処理する符号化装置について説明する。全体の構成は図１と同じである。

Ｈ．２６４の規格では動き補償を用いてマクロブロックをエンコードすることができる。マクロブロック単位で動き補償を行うことも、マクロブロックを分割したブロックで動き補償を行うこともできる。図２２に動き補償のブロックを示す。動き補償を行うブロックサイズは１６×１６、１６×８、８×１６、８×８から選択することができる。８×８の場合はさらに、８×８、８×４、４×８、４×４に分割することができる。分割したブロックごとに動きベクトルを持つことができる。

Ｈ．２６４の規格では動きベクトルを符号化するときに、動きベクトルの値そのものを符号化するのではなく、動きベクトルと動きベクトルの予測値（ＰＭＶと呼ばれる）との差分を符号化する。水平、垂直の成分ごとに動きベクトルとＰＭＶの差分を符号化する。規格では動きベクトルの予測値（ＰＭＶ）は現在マクロブロックの左、上、右上のマクロブロックの動きベクトルから求められる。図２３（ａ）においてＭＢ９を現在マクロブロックとすると、ＭＢ８（左）、ＭＢ１（上）、ＭＢ２（右上）の３個のマクロブロックの動きベクトルを用いてＭＢ９の動きベクトルの予測値（ＰＭＶ）を求める。周囲のマクロブロックの動きベクトルからＰＭＶを求める手順は複雑であるが、本発明の本質とは関係がないので手順の説明は省く。

Ｈ．２６４の標準化の過程で非特許文献６に述べられるJoint Model（以下ＪＭとする）と呼ばれるエンコーダ、デコーダが作成された。ＪＭでは符号化による歪みを小さくし、かつ符号量を小さくするためにレート・歪み最適化と呼ばれる手法を用いる（レート・歪み最適化の手法は非特許文献８にも述べられている）。非特許文献６に基づいてＪＭのエンコードにおける動きベクトル探索（motion estimation、ＭＥ）の方法を説明する。動きベクトル探索で動きベクトルを求めた後に、その動きベクトルを用いてエンコードする。動きベクトル探索では原画像と予測画像との予測誤差を小さくすると同時に動きベクトルの符号量が小さくなるように動きベクトルを選択する。

ＪＭでは以下の式で計算されるＪを最小にするような動きベクトルを選択する。

Ｊ＝ＳＡＤ＋λＲ
ここで、ＳＡＤ（sum of absolute difference)は予測残差の絶対値の和、λはラグランジュパラメタと呼ばれる定数、Ｒは動きベクトルの符号量である。ＳＡＤの代わりに残差に対してアダマール変換を行った後の絶対値の和であるＳＡＴＤを用いることもある。ＪＭエンコーダでは動きベクトルの符号量を小さくするために、規格の手順に基づいてＰＭＶを求め、画像の予測誤差が小さくなると同時に動きベクトルとＰＭＶの差分が小さくなるような動きベクトルを選択する（動きベクトル探索方法はＨ．２６４の規格には規定されておらず、エンコーダに任されている。ＰＭＶを求める手順はＨ．２６４の規格に規定されている。）。

ＪＭエンコーダはソフトウェアによる実装であるが、ハードウェアで実装する場合はパイプライン処理が課題となる。以下、それについて説明する。ＪＭの動きベクトルサーチをそのままハードウェアで実装しようとすると、規格の手順によってＰＭＶを求める必要がある。ＰＭＶを求めるときに現在マクロブロックの左、上、右上のマクロブロックの動きベクトルを用いるので、現在マクロブロックに対する動きベクトル探索を開始する前にこれらの３個のマクロブロックのエンコードが完了している必要がある。特に影響が大きいのが左のマクロブロックである。左のマクロブロックの動きベクトル探索とエンコードが完了してからでなければ現在マクロブロックに対する動きベクトル探索を開始することができないので、動きベクトル探索とその後のエンコード処理をパイプライン処理することが困難である。

非特許文献７ではこの課題に以下のように対応している。図２３（ｂ）に示すように、現在マクロブロックのＰＭＶの計算において、左のマクロブロックの動きベクトルの代わりに左上のマクロブロックの動きベクトルを用いる。このようにして求めたベクトルをＰＭＶ’とすると、非特許文献７の方法は現在マクロブロックの動きベクトルとＰＭＶ’の差分を小さくするように動きベクトルを選択する。このようにすれば、動きベクトル探索とエンコードをパイプライン処理することは可能であるが、別の課題が生じる。動きベクトル探索では動きベクトルとＰＭＶ’との差分を小さくするように動きベクトルを選択するが、エンコードでは動きベクトルとＰＭＶの差分をエンコードする。ＰＭＶとＰＭＶ’は異なるので、動きベクトルとＰＭＶ’との差分が小さくても、動きベクトルとＰＭＶの差分が大きくなることがあり得る。そのためエンコードした後に動きベクトルの符号量が大きくなるという課題が生じる。

本実施の形態における方法では図２４（ａ）に示す順序でマクロブロックを処理する。このような順序で処理することにより、図２４（ｂ）に示すように動きベクトル探索とその後のエンコードの処理をパイプラン処理することが可能となる。図の例ではマクロブロックの処理を動きベクトル探索とその後のエンコード処理の２段のパイプラインで処理している。例として、図２４（ｂ）を参照して現在マクロブロックがＭＢ５の場合について説明する。ＭＢ５の動きベクトル探索に用いるＰＭＶを求めるためにＭＢ１、ＭＢ２、ＭＢ３の動きベクトルを用いるので、これらの３個のマクロブロックの処理が完了している必要がある。ＭＢ４の動きベクトル探索ステージが終了する時点でＭＢ３のエンコードステージが終了するので、ＭＢ４の動きベクトル探索ステージの終了直後にＭＢ５の動きベクトル探索ステージを開始することができる。

なお、図２４はマクロブロックの処理を動きベクトル探索とその後のエンコードの２段のパイプラン処理で行う場合について示しているが、マクロブロックの処理を細分して３段以上のパイプラインによって処理することも可能である。図２４（ａ）の順序でマクロブロックを処理することにより、ＭＢ６以降は３段のパイプライン処理が可能である。ＭＢ１２以降は４段のパイプライン処理が可能である。フレームサイズが大きい画像に対しては５段以上のパイプライン処理も同様に実施可能である。

なお、図２４（ａ）に示すマクロブロックの処理順序は図１４のフローチャートの手順によって選択することが可能である。あるいは、マクロブロックのアドレスと処理順序の対応表を用いることによって選択することも可能である。

なお、本実施の形態の特徴は現在マクロブロックと左、上、右上のマクロブロックの間に処理順序で１個以上のマクロブロックが入ることである。（別の表現をすれば、現在マクロブロックと左、上、右上のマクロブロックの順序番号の差が２以上となることである。）この条件を満たせば、図２４（ａ）とは異なる処理順序であっても、動きベクトル探索とその後のエンコードをパイプライン処理することが同様に実施可能である。３段以上のパイプライン処理についても同様である。

（実施の形態１０）
本実施の形態では複数のマクロブロックに対する動きベクトル探索を並列に行い、さらに動きベクトル探索とエンコードをパイプライン方式で処理する符号化装置について説明する。全体の構成は図１と同じである。

Ｈ．２６４の規格では動きベクトルそのものを符号化するのではなく、動きベクトルと動きベクトルの予測値の差分を符号化する。実施の形態９に述べたように、動きベクトル探索においては、現在マクロブロックの左、上、右上のマクロブロックの動きベクトルから動きベクトルの予測値であるＰＭＶを求める必要がある。そのため、現在マクロブロックの左、上、右上にマクロブロックが存在した場合、現在マクロブロックの動きベクトル探索を開始する前にそれらのマクロブロックのエンコードが完了している必要がある（現在マクロブロックの左、上、右上にマクロブロックが存在しない場合はそれらのエンコードが完了している必要はない。）。

図２５（ａ）は本実施の形態によるマクロブロックの処理順序である。図２５（ｂ）は動きベクトル探索を行うＭＥユニットを０、１の２個備え、エンコードを行うエンコードユニットを０、１の２個備えた符号化装置の動作を説明する図である。図に基づいて時間の経過に従って動作を説明する。

時間０：ＭＢ０の動きベクトルサーチを開始する。

時間１：ＭＢ０の動きベクトルサーチが完了し、ＭＢ０のエンコードを開始する。

時間２：ＭＢ０のエンコードが完了したので、ＭＢ１の動きベクトルサーチを開始することが可能となる（ＭＢ１に対するＰＭＶを求めるのにＭＢ０のエンコード結果を用いるため）。ＭＢ１の動きベクトルサーチを開始する。

時間３：ＭＢ１の動きベクトルサーチが完了し、ＭＢ１のエンコードを開始する。

時間４：ＭＢ１のエンコードが完了したので、ＭＢ２の動きベクトルサーチを開始することが可能となる。ＭＢ２の動きベクトルサーチを開始する。ＭＢ０、ＭＢ１のエンコードが完了しているので、ＭＢ３の動きベクトルサーチを開始することが可能となる。ＭＢ３の動きベクトルサーチを開始する。

時間５：ＭＢ２の動きベクトルサーチが完了し、ＭＢ２のエンコードを開始する。ＭＢ３の動きベクトルサーチが完了し、ＭＢ３のエンコードを開始する。

時間６：ＭＢ４の動きベクトルサーチを開始する。ＭＢ５の動きベクトルサーチを開始する。

時間７：ＭＢ４のエンコードを開始する。ＭＢ５のエンコードを開始する。

時間８：ＭＢ６の動きベクトルサーチを開始する。ＭＢ７の動きベクトルサーチを開始する。

時間９：ＭＢ３、ＭＢ５のエンコードが完了しているので、ＭＢ８の動きベクトルサーチを開始することが可能となる（ＭＢ８に対するＰＭＶを求めるのにＭＢ３とＭＢ５のエンコード結果を用いるため）。ＭＢ８の動きベクトルサーチを開始する。ＭＢ６のエンコードを開始する。ＭＢ７のエンコードを開始する。

時間１０：ＭＢ４、ＭＢ６、ＭＢ７のエンコードが完了しているので、ＭＢ１０の動きベクトルサーチを開始することが可能となる（ＭＢ１０に対するＰＭＶを求めるのに、ＭＢ４、ＭＢ６、ＭＢ７のエンコード結果を用いるため）。ＭＢ１０の動きベクトルサーチを開始する。ＭＢ６のエンコードが完了しているのでＭＢ９の動きベクトルサーチを開始することが可能となる。ＭＢ９の動きベクトルサーチを開始する。ＭＢ８のエンコードを開始する。

時間１１：ＭＢ５、ＭＢ７、ＭＢ８のエンコードが完了しているのでＭＢ１１の動きベクトルサーチを開始することが可能となる。ＭＢ１１の動きベクトルサーチを開始する。ＭＢ１０のエンコードを開始する。ＭＢ９のエンコードを開始する。

時間１２：ＭＢ９のエンコードが完了したので、ＭＢ１２の動きベクトルサーチを開始することが可能となる。ＭＢ１２の動きベクトルサーチを開始する。ＭＢ６、ＭＢ９、ＭＢ１０のエンコードが完了しているので、ＭＢ１３の動きベクトルサーチを開始することが可能となる。ＭＢ１３の動きベクトルサーチを開始する。ＭＢ１１のエンコードを開始する。

時間１３：ＭＢ７、ＭＢ１０、ＭＢ１１のエンコードが完了しているので、ＭＢ１４の動きベクトルサーチを開始することが可能となる。ＭＢ１４の動きベクトルサーチを開始する。ＭＢ８、ＭＢ１１のエンコードが完了しているので、ＭＢ１５の動きベクトルサーチを開始することが可能となる。ＭＢ１５の動きベクトルサーチを開始する。ＭＢ１２のエンコードを開始する。ＭＢ１３のエンコードを開始する。

時間１４：ＭＢ１２のエンコードが完了しているので、ＭＢ１６の動きベクトルサーチを開始することが可能となる。ＭＢ１６の動きベクトルサーチを開始する。ＭＢ９、ＭＢ１２、ＭＢ１３のエンコードが完了しているので、ＭＢ１７の動きベクトルサーチを開始することが可能となる。ＭＢ１７の動きベクトルサーチを開始する。ＭＢ１４のエンコードを開始する。ＭＢ１５のエンコードを開始する。

以上の説明から分かるように、時間４以降は２個のマクロブロックに対する動きベクトルサーチ、あるいは２個のマクロブロックに対するエンコードを並列に実行することができる。また、時間１３以降は２個のマクロブロックに対する動きベクトルサーチと２個のマクロブロックに対するエンコードの両方を並列に実行することができる。時間１３以降は２つのＭＥユニットと２つのエンコードユニットを空き時間を作らずに連続して動作させることができる。

以上、２個のＭＥユニットと２個のエンコードユニットを備えた装置に対する並列処理について説明したが、３個以上のマクロブロックに対する並列処理についても同様に実施可能である。例として、３個のマクロブロックに対する並列処理について説明する。符号化装置はＭＥユニットとエンコードユニットをともに３個備えるとする。図２５でＭＢ６に対するＰＭＶを求めるときに参照するのはＭＢ４である。ＭＢ７に対するＰＭＶを求めるときに参照するのはＭＢ２、ＭＢ４、ＭＢ５である。ＭＢ８に対するＰＭＶを求めるときに参照するのはＭＢ３、ＭＢ５である。ＭＢ４とＭＢ５のエンコードが完了した時点で、ＭＢ６、ＭＢ７、ＭＢ８に対するＰＭＶを求めるときに参照するマクロブロックのエンコードが完了している。従って、ＭＢ４とＭＢ５のエンコードが完了した時点で、ＭＢ６、ＭＢ７、ＭＢ８に対する動きベクトル探索を同時に開始することができる。このようにしてＭＢ６以降は３個のマクロブロックに対する動きベクトル探索、あるいは３個のマクロブロックに対するエンコードを並列に行うことができる。フレームサイズが大きい場合、処理を進めていくに従って、３個のマクロブロックに対する動きベクトルサーチと３個のマクロブロックに対するエンコードの両方を並列に実行することができる。なお、４個以上のマクロブロックに対する並列処理も同様に実施可能である。

（実施の形態１１）
本実施の形態による画像符号化装置は、動きベクトル探索を行う２個のＭＥユニットと動きベクトル探索以降のエンコード処理を行う１個のエンコードユニットを備える。図２６は本実施の形態の説明図である。動きベクトル探索はエンコードと比較して計算量が大きいので、本実施の形態ではエンコードユニットの数より多くのＭＥユニットを備える。

本実施の形態による画像符号化装置は図２６（ａ）の順序でマクロブロックを処理する。図２６（ｂ）に基づき、本実施の形態の動作を時間の経過に従って説明する。動きベクトル探索はエンコードの２倍の時間がかかるとする。

時間０：ＭＢ０の動きベクトルサーチを開始する。

時間２：ＭＢ０の動きベクトルサーチが完了し、ＭＢ０のエンコードを開始する。

時間３：ＭＢ０のエンコードが完了したので、ＭＢ１の動きベクトルサーチを開始することが可能となる。ＭＢ１の動きベクトルサーチを開始する。

時間５：ＭＢ１の動きベクトルサーチが完了し、ＭＢ１のエンコードを開始する。

時間６：ＭＢ１のエンコードが完了したので、ＭＢ２の動きベクトルサーチを開始することが可能となる。ＭＢ２の動きベクトルサーチを開始する。ＭＢ０、ＭＢ１のエンコードが完了したので、ＭＢ３の動きベクトルサーチを開始することが可能となる。ＭＢ３の動きベクトルサーチを開始する。

時間８：ＭＢ２の動きベクトルサーチが完了し、ＭＢ２のエンコードを開始する。

時間９：ＭＢ２のエンコードが完了したので、ＭＢ４の動きベクトルサーチを開始することが可能となる。ＭＢ４の動きベクトルサーチを開始する。ＭＢ３の動きベクトルサーチが完了しているので、ＭＢ３のエンコードを開始する。

時間１０：ＭＢ１、ＭＢ２、ＭＢ３のエンコードが完了したので、ＭＢ５の動きベクトルサーチを開始することが可能となる。ＭＢ５の動きベクトルサーチを開始する。

時間１１：ＭＢ４の動きベクトルサーチが完了し、ＭＢ４のエンコードを開始する。

時間１２：ＭＢ４のエンコードが完了したので、ＭＢ６の動きベクトルサーチを開始することが可能となる。ＭＢ６の動きベクトルサーチを開始する。ＭＢ５の動きベクトルサーチが完了したので、ＭＢ５のエンコードを開始する。

時間１３：ＭＢ２、ＭＢ４、ＭＢ５のエンコードが完了したので、ＭＢ７の動きベクトルサーチを開始することが可能となる。ＭＢ７の動きベクトルサーチを開始する。

時間１４：ＭＢ３、ＭＢ５のエンコードが完了しているので、ＭＢ８の動きベクトルサーチを開始することが可能となる。ＭＢ８の動きベクトルサーチを開始する。ＭＢ６の動きベクトルサーチが完了したので、ＭＢ６のエンコードを開始する。

時間１５：ＭＢ６のエンコードが完了したので、ＭＢ９の動きベクトルサーチを開始することが可能となる。ＭＢ９の動きベクトルサーチを開始する。ＭＢ７の動きベクトルサーチが完了し、ＭＢ７のエンコードを開始する。

時間１６：ＭＢ４、ＭＢ６、ＭＢ７のエンコードが完了したので、ＭＢ１０の動きベクトルサーチを開始することが可能となる。ＭＢ１０の動きベクトルサーチを開始する。ＭＢ８の動きベクトルサーチが完了し、ＭＢ８のエンコードを開始する。

以上の説明から分かるように、時間１４以降は２個のＭＥユニットと１個のエンコードユニットを空き時間を作らずに連続して動作させることが可能となる。２個のマクロブロックに対する動きベクトル探索を並列に行い、さらに動きベクトル探索とエンコード処理を並列に行うことが可能となる。

なお、動きベクトル探索以外のエンコードの処理をパーソナルコンピュータが実行し、計算量が大きい動きベクトル探索をパーソナルコンピュータの拡張ボードが行うように実装することも可能である。そのように実装した場合、ＭＥユニット０，１がパーソナルコンピュータの拡張ボードに相当し、エンコードユニットがパーソナルコンピュータに相当し、全体の制御をパーソナルコンピュータが実行する。１枚の拡張ボードを１個のＭＥユニットとしてもよいし、１枚の拡張ボードに複数のＭＥユニットの機能を持たせてもよい。ＭＥユニットとエンコードユニットの動作は本実施の形態と同様である。

（実施の形態１２）
本実施の形態による画像符号化装置は、動きベクトル探索を行う３個のＭＥユニットと動きベクトル探索以降のエンコード処理を行う１個のエンコードユニットを備える。図２７は本実施の形態の説明図である。

現在マクロブロックの左、上、右上にマクロブロックが存在する場合は、現在マクロブロックに対するＰＭＶを求めるのに、これらのマクロブロックの動きベクトルを用いるので、現在マクロブロックの動きベクトル探索を開始する前にこれらのマクロブロックのエンコードが完了している必要がある。本実施の形態による画像符号化装置は図２７（ａ）の順序でマクロブロックを処理する。図２７（ｂ）に基づき、本実施の形態の動作を時間の経過に従って説明する。動きベクトル探索はエンコードの３倍の時間がかかるとする。

時間０：ＭＢ０の動きベクトルサーチを開始する。

時間３：ＭＢ０の動きベクトルサーチが完了し、ＭＢ０のエンコードを開始する。

時間４：ＭＢ０のエンコードが完了し、ＭＢ１の動きベクトルサーチを開始することが可能となる。ＭＢ１の動きベクトルサーチを開始する。

時間７：ＭＢ１の動きベクトルサーチが完了し、ＭＢ１のエンコードを開始する。

時間８：ＭＢ１のエンコードが完了したので、ＭＢ２の動きベクトルサーチを開始することが可能となる。ＭＢ２の動きベクトルサーチを開始する。ＭＢ０、ＭＢ１のエンコードが完了したので、ＭＢ３の動きベクトルサーチを開始することが可能となる。ＭＢ３の動きベクトルサーチを開始する。

時間１１：ＭＢ２の動きベクトルサーチが完了し、ＭＢ２のエンコードを開始する。

時間１２：ＭＢ２のエンコードが完了したので、ＭＢ４の動きベクトルサーチを開始することが可能となる。ＭＢ４の動きベクトルサーチを開始する。ＭＢ３の動きベクトルサーチが完了しているので、ＭＢ３のエンコードを開始する。

時間１３：ＭＢ１、ＭＢ２、ＭＢ３のエンコードが完了しているので、ＭＢ５の動きベクトルサーチを開始することが可能となる。ＭＢ５の動きベクトルサーチを開始する。

時間１５：ＭＢ４の動きベクトルサーチが完了し、ＭＢ４のエンコードを開始する。

時間１６：ＭＢ４のエンコードが完了したので、ＭＢ６の動きベクトルサーチを開始することが可能となる。ＭＢ６の動きベクトルサーチを開始する。ＭＢ５の動きベクトルサーチが完了し、ＭＢ５のエンコードを開始する。

時間１７：ＭＢ２、ＭＢ４、ＭＢ５のエンコードが完了したので、ＭＢ７の動きベクトルサーチを開始することが可能となる。ＭＢ７の動きベクトルサーチを開始する。ＭＢ３、ＭＢ５のエンコードが完了したので、ＭＢ８の動きベクトルサーチを開始することが可能となる。ＭＢ８の動きベクトルサーチを開始する。

時間１９：ＭＢ６の動きベクトルサーチが完了し、ＭＢ６のエンコードを開始する。

時間２０：ＭＢ６のエンコードが完了し、ＭＢ９の動きベクトルサーチを開始することが可能となる。ＭＢ９の動きベクトルサーチを開始する。ＭＢ７の動きベクトルサーチが完了し、ＭＢ７のエンコードを開始する。

時間２１：ＭＢ４、ＭＢ６、ＭＢ７のエンコードが完了したので、ＭＢ１０の動きベクトルサーチを開始することが可能となる。ＭＢ１０の動きベクトルサーチを開始する。ＭＢ８の動きベクトルサーチが完了しているので、ＭＢ８のエンコードを開始する。

時間２２：ＭＢ５、ＭＢ７、ＭＢ８のエンコードが完了したので、ＭＢ１１の動きベクトルサーチを開始することが可能となる。ＭＢ１１の動きベクトルサーチを開始する。

時間２３：ＭＢ９の動きベクトルサーチが完了し、ＭＢ９のエンコードを開始する。

時間２４：ＭＢ９のエンコードが完了したので、ＭＢ１２の動きベクトルサーチを開始することが可能となる。ＭＢ１２の動きベクトルサーチを開始する。ＭＢ１０の動きベクトルサーチが完了し、ＭＢ１０のエンコードを開始する。

時間２５：ＭＢ１１の動きベクトルサーチが完了し、ＭＢ１１のエンコードを開始する。

時間２６：ＭＢ７、ＭＢ１０、ＭＢ１１のエンコードが完了したので、ＭＢ１４の動きベクトルサーチを開始することが可能となる。ＭＢ１４の動きベクトルサーチを開始する。

時間２７：ＭＢ８、ＭＢ１１のエンコードが完了しているので、ＭＢ１５の動きベクトルサーチを開始することが可能となる。ＭＢ１５の動きベクトルサーチを開始する。ＭＢ１２の動きベクトルサーチが完了し、ＭＢ１２のエンコードを開始する。

時間２８：ＭＢ１２のエンコードが完了したので、ＭＢ１６の動きベクトルサーチを開始することが可能となる。ＭＢ１６の動きベクトルサーチを開始する。ＭＢ１３の動きベクトルサーチが完了し、ＭＢ１３のエンコードを開始する。

時間２９：ＭＢ９、ＭＢ１２、ＭＢ１３のエンコードが完了したので、ＭＢ１７の動きベクトルサーチを開始することが可能となる。ＭＢ１７の動きベクトルサーチを開始する。ＭＢ１４の動きベクトルサーチが完了し、ＭＢ１４のエンコードを開始する。

時間３０：ＭＢ１０、ＭＢ１３、ＭＢ１４のエンコードが完了したので、ＭＢ１８の動きベクトルサーチを開始することが可能となる。ＭＢ１８の動きベクトルサーチを開始する。ＭＢ１５の動きベクトルサーチが完了し、ＭＢ１５のエンコードを開始する。

時間３１：ＭＢ１１、ＭＢ１４、ＭＢ１５のエンコードが完了したので、ＭＢ１９の動きベクトルサーチを開始することが可能となる。ＭＢ１９の動きベクトルサーチを開始する。ＭＢ１６の動きベクトルサーチが完了し、ＭＢ１６のエンコードを開始する。

時間３２：ＭＢ１６のエンコードが完了したので、ＭＢ２０の動きベクトルサーチを開始することが可能となる。ＭＢ２０の動きベクトルサーチを開始する。ＭＢ１７の動きベクトルサーチが完了し、ＭＢ１７のエンコードを開始する。

以上の説明と図２７（ｂ）から分かるように、時間２７以降は３個のＭＥユニットとエンコードユニットを空き時間を作らずに連続して動作させることが可能となる。３個のマクロブロックに対する動きベクトル探索を並列に実行し、さらに動きベクトル探索とエンコードを並列に実行することが可能となる（フレームの左上と右下の領域では、並列可能な個数は小さくなる）。

なお、本実施例ではＭＥユニットが３個の場合について説明したが、ＭＥユニットが４個以上の場合についても同様に実施可能である。フレームサイズは十分大きいものとする。ＭＥユニットが４個で、１個のマクロブロックに対するＭＥユニットの処理時間がエンコードユニットの処理時間の４倍である場合、４個のＭＥユニットと１個のエンコードユニットを空き時間を作らずに連続して動作させることができる。ＭＥユニットの数がさらに多い場合も同様である。

なお、動きベクトル探索以外のエンコードの処理をパーソナルコンピュータが実行し、計算量が大きい動きベクトル探索をパーソナルコンピュータの拡張ボードが行うように実装することも可能である。そのように実装した場合、ＭＥユニット０，１、２がパーソナルコンピュータの拡張ボードに相当し、エンコードユニットがパーソナルコンピュータに相当し、全体の制御をパーソナルコンピュータが行う。１枚の拡張ボードを１個のＭＥユニットとしてもよいし、１枚の拡張ボードに複数のＭＥユニットの機能を持たせてもよい。４個以上のＭＥユニットを備えたパーソナルコンピュータによる画像符号化装置も同様に実施可能である。

なお、動きベクトル探索機能をパーソナルコンピュータの拡張ボードとして実装した場合、パーソナルコンピュータからの１回の呼び出しで複数個のマクロブロックに対する動きベクトル探索を行うようにしても同様に実装可能である。このようにすることにより、パーソナルコンピュータからの拡張ボードの呼び出し回数が少なくなり、拡張ボードの呼び出しのオーバヘッドを小さくすることができる。

本実施の形態では、現在マクロブロックに対するＰＭＶを求めるために左、上、右上のマクロブロックの動きベクトルを用いるので、現在マクロブロックの処理を開始する前にこれらのマクロブロックの処理が完了している必要があるとした。しかし、理由がＰＭＶを求めるためであることに限定されない。現在マクロブロックの処理が左、上、右上のマクロブロックの処理結果に依存するような場合であれば、本発明の方法を適用することが可能である。本実施の形態では現在マクロブロックが左、上、右上のマクロブロックに依存する理由はＰＭＶを求めるためであったが、ＰＭＶを求めるためと限らず他の理由で依存する場合であっても同様に実施可能である。なお、現在マクロブロックが依存するマクロブロックが左、上、右上のマクロブロックとは限定されず、現在マクロブロックが依存するマクロブロックが他の場合であっても同様に実施可能である。例えば、現在マクロブロックが左、上、左上のマクロブロックに依存する場合であっても同様に実施可能である。現在マクロブロックが左、左上、上、右上のマクロブロックに依存する場合であっても同様に実施可能である。

本発明にかかる画像符号化装置はマクロブロック単位のパイプライ処理が可能であるという特徴を有し、デジタル放送、テレビ会議、蓄積媒体等の用途における画像符号化装置として有用である。

本発明の実施の形態１における符号化装置の基本構成図 本発明の実施の形態３における復号化装置の基本構成図 従来のＭＰＥＧ２符号化装置の基本構成図 従来のＭＰＥＧ２復号化装置の基本構成図 （ａ）マクロブロックのパイプラン処理における各ステージの処理内容を示す図（ｂ）マクロブロックのパイプラン処理を示す図 本発明の実施の形態１におけるマクロブロックの符号化順序を示す図 本発明の実施の形態２におけるマクロブロックの符号化順序を示す図 スペーシャルダイレクトモードの説明図 従来方法におけるマクロブロックの符号化順序を示す図 符号化マクロブロックの分割の説明図 イントラ１６×１６予測の説明図 イントラ４×４予測の説明図 本発明の実施の形態１におけるマクロブロック順序選択方法のフローチャート 本発明の実施の形態２におけるマクロブロック順序選択方法のフローチャート 本発明の実施の形態５における静止画符号化装置の基本構成図 本発明の実施の形態６におけるマクロブロック順序並び替え装置の基本構成図 本発明の実施の形態７におけるマクロブロック順序並び替え装置の基本構成図 マクロブロックの処理順序を示す図 マクロブロックの処理順序を示す図 本発明の実施の形態８におけるＭＢＡＦＦの処理順序を示す図 従来方法におけるＭＢＡＦＦの符号化順序を示す図 動き補償のブロックの説明図 ＰＭＶの導出に用いるマクロブロックを示す図 本発明の実施の形態９におけるマクロブロックの処理順序を示す図 本発明の実施の形態１０におけるマクロブロックの処理順序を示す図 本発明の実施の形態１１におけるマクロブロックの処理順序を示す図 本発明の実施の形態１２におけるマクロブロックの処理順序を示す図

符号の説明

１０ Ａ／Ｄ変換部
１１ フォーマット変換部
１２ 画面並び替え部
１３ マクロブロック順序選択部
１４ ＤＣＴ部
１５ 量子化部
１６ レート制御部
１７ 動きベクトル検出、イントラ予測部
１８ 動き補償モード選択部
１９ 逆量子化部
２０ 逆ＤＣＴ部
２１ エントロピー符号化部
２２ バッファ
２３ ビデオメモリ
３０ バッファ
３１ 可変長復号化部
３２ 逆量子化部
３３ 逆ＤＣＴ部
３４ 画面並び替え部
３５ フォーマット変換部
３６ Ｄ／Ａ変換部
３７ 動き補償部
３８ ビデオメモリ
３９ マクロブロック順序選択部
５０ Ａ／Ｄ変換部
５１ フォーマット変換部
５２ 画面並び替え部
５３ ＤＣＴ部
５４ 量子化部
５５ 可変長符号化部
５６ バッファ
５７ レート制御部
５８ 逆量子化部
５９ 逆ＤＣＴ部
６０ 動きベクトル検出部
６１ 動き補償モード選択部
６２ ビデオメモリ
７０ バッファ
７１ 可変長復号化部
７２ 逆量子化部
７３ 逆ＤＣＴ部
７４ 画面並び替え部
７５ フォーマット変換部
７６ Ｄ／Ａ変換部
７７ 動き補償部
７８ ビデオメモリ
８０ 予測部
８１ 残差計算部
８２ ＤＣＴ部
８３ 量子化部
８４ ジグザグスキャン部
８５ 可変長符号化部
８６ マクロブロック順序選択部
８７ フレームメモリ
８８ 逆ＤＣＴ部
８９ 逆量子化部

Claims (17)

1. 複数のマクロブロックを含む画像を符号化する画像符号化装置であって、
   画像を構成する複数のマクロブロックを取得するマクロブロック取得手段と、
   前記複数のマクロブロックから、符号化対象のマクロブロックである現在マクロブロックを、所定の順序で選択して出力するマクロブロック選択手段と、
   前記現在マクロブロックを、所定の段数のパイプライン処理を用いて符号化する符号化手段と、
   前記符号化手段によって符号化された前記マクロブロックを出力する出力手段と
   を備え、
   前記符号化手段は、前記現在マクロブロックを、前記画像内において当該現在マクロブロックと所定の位置関係を満たすマクロブロックである参照マクロブロックの符号化後の情報を用いて符号化し、前記参照マクロブロックは、前記画像内において、前記現在マクロブロックの左のマクロブロックを含んでおり、
   前記マクロブロック選択手段は、Ｎを１以上の整数として、
   前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に符号化されていないマクロブロックが存在する場合には、当該マクロブロックを次の現在マクロブロックとして選択し、
   前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に符号化されていないマクロブロックが存在しない場合には、前記複数のマクロブロックのうち、符号化されておらず、かつ、最も上の行の最も左に配置されたマクロブロックを次の現在マクロブロックとして選択することを特徴とする画像符号化装置。
2. 前記Ｎは１であることを特徴とする請求項１に記載の画像符号化装置。
3. 前記Ｎは２であることを特徴とする請求項１に記載の画像符号化装置。
4. 前記符号化手段は、前記現在マクロブロックを、前記参照マクロブロックの符号化後の
   情報を参照したイントラ予測を用いて符号化する
   ことを特徴とする請求項１記載の画像符号化装置。
5. 前記画像符号化装置は、さらに、
   複数の画像同士の間で、前記マクロブロックごと若しくは前記マクロブロックの一部分ごとの動きベクトルを検出する動きベクトル検出手段を備え、
   前記符号化手段は、前記現在マクロブロック若しくは前記現在マクロブロックの一部分の動きベクトルを、前記参照マクロブロック若しくは前記参照マクロブロックの一部分の動きベクトルを用いて符号化することにより、前記現在マクロブロックの符号化を行う
   ことを特徴とする請求項１記載の画像符号化装置。
6. 前記マクロブロック選択手段は、上下の２つのマクロブロックを現在マクロブロックの組として選択して出力し、
   前記符号化手段は、前記現在マクロブロックの組ごとの符号化を行う
   ことを特徴とする請求項１に記載の画像符号化装置。
7. 前記出力手段は、さらに、前記マクロブロックそれぞれの前記画像内における位置を示す位置情報を出力する
   ことを特徴とする請求項１に記載の画像符号化装置。
8. 前記出力手段は、前記符号化されたマクロブロックそれぞれを、前記符号化手段によって符号化された符号化順あるいはラスタ順で並べたストリームとして出力し、かつ、いずれの順序で出力したかを示す識別情報を出力する
   ことを特徴とする請求項１に記載の画像符号化装置。
9. 画像を構成する複数のマクロブロックそれぞれを符号化することで生成された複数の符号化マクロブロックを復号化する画像復号化装置であって、
   複数の符号化マクロブロックを取得する符号化マクロブロック取得手段と、
   前記複数の符号化マクロブロックから、復号化対象の符号化マクロブロックである現在マクロブロックを、所定の順序で選択して出力する符号化マクロブロック選択手段と、
   前記現在マクロブロックを、所定の段数のパイプライン処理を用いて復号化する復号化手段と、
   前記復号化手段によって復号化されたマクロブロックから前記画像を再構成する再構成手段と
   を備え、
   前記復号化手段は、前記現在マクロブロックを参照マクロブロックの復号化後の情報を用いて復号化し、
   前記参照マクロブロックは、当該参照マクロブロックを復号化して得られるマクロブロックと、前記現在マクロブロックを復号化して得られるマクロブロックとが、前記画像内で所定の位置関係を満たす符号化マクロブロックであり、前記参照マクロブロックは、前記現在マクロブロックの左のマクロブロックを含んでおり、
   前記符号化マクロブロック選択手段は、Ｎを１以上の整数として、
   前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に復号化されていないマクロブロックが存在する場合には、当該マクロブロックを次の現在マクロブロックとして選択し、
   前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に復号化されていないマクロブロックが存在しない場合には、前記複数のマクロブロックのうち、復号化されておらず、かつ、最も上の行の最も左に配置されたマクロブロックを次の現在マクロブロックとして選択することを特徴とする画像復号化装置。
10. 前記復号化手段は、前記現在マクロブロックを、前記参照マクロブロックの復号化後の情報を参照したイントラ予測を用いて復号化する
    ことを特徴とする請求項９記載の画像復号化装置。
11. 前記複数の符号化マクロブロックのそれぞれは、各マクロブロック若しくは各マクロブロックの一部分の動きベクトルを符号化した情報を含み、
    前記復号化手段は、前記現在マクロブロック若しくは前記現在マクロブロックの一部分の動きベクトルを、前記参照マクロブロック若しくは前記参照マクロブロックの一部分の動きベクトルを用いて復号化することにより、前記現在マクロブロックの復号化を行う
    ことを特徴とする請求項９記載の画像復号化装置。
12. 前記画像復号化装置は、さらに、前記複数の符号化マクロブロックそれぞれの前記画像内における位置を示す位置情報を取得する位置情報取得手段を備え、
    前記再構成手段は、復号化されたマクロブロックのそれぞれを、前記位置情報が示す位置に配置することにより前記画像を復元する
    ことを特徴とする請求項９に記載の画像復号化装置。
13. 前記位置情報取得手段は、前記画像を構成するマクロブロックのストリーム内の順序が、符号化された符号化順あるいはラスタ順のいずれであるかを示す識別情報を取得し、
    前記再構成手段は、復号化したマクロブロックそれぞれの前記画像内の位置を、前記識別情報に基づいて特定することで、前記画像を再構成する
    ことを特徴とする請求項１２に記載の画像復号化装置。
14. 複数のマクロブロックを含む画像を符号化する画像符号化方法であって、
    画像を構成する複数のマクロブロックを取得するマクロブロック取得ステップと、
    前記複数のマクロブロックから、符号化対象のマクロブロックである現在マクロブロックを、所定の順序で選択して出力するマクロブロック選択ステップと、
    前記現在マクロブロックを、所定の段数のパイプライン処理を用いて符号化する符号化ステップと、
    前記符号化ステップによって符号化された前記マクロブロックを出力する出力ステップと
    を含み、
    前記符号化ステップは、前記現在マクロブロックを、前記画像内において当該現在マクロブロックと所定の位置関係を満たすマクロブロックである参照マクロブロックの前記符号化後の情報を用いて符号化し、前記参照マクロブロックは、前記画像内において、前記現在マクロブロックの左のマクロブロックを含んでおり、
    前記マクロブロック選択ステップは、Ｎを１以上の整数として、
    前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に符号化されていないマクロブロックが存在する場合には、当該マクロブロックを次の現在マクロブロックとして選択し、
    前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に符号化されていないマクロブロックが存在しない場合には、前記複数のマクロブロックのうち、符号化されておらず、かつ、最も上の行の最も左に配置されたマクロブロックを次の現在マクロブロックとして選択することを特徴とする画像符号化方法。
15. 画像を構成する複数のマクロブロックそれぞれを符号化することで生成された複数の符号化マクロブロックを復号化する画像復号化方法であって、
    複数の符号化マクロブロックを取得するマクロブロック取得ステップと、
    前記複数の符号化マクロブロックから、復号化対象の符号化マクロブロックである現在マクロブロックを、所定の順序で選択して出力するマクロブロック選択ステップと、
    前記現在マクロブロックを、所定の段数のパイプライン処理を用いて復号化する復号化ステップと、
    前記復号化ステップによって復号化されたマクロブロックから前記画像を再構成する再構成ステップと
    を含み、
    前記復号化ステップは、前記現在マクロブロックを参照マクロブロックの復号化後の情報を用いて復号化し、
    前記参照マクロブロックは、当該参照マクロブロックを復号化して得られるマクロブロックと、前記現在マクロブロックを復号化して得られるマクロブロックとが、前記画像内で所定の位置関係を満たす符号化マクロブロックであり、前記参照マクロブロックは、前記現在マクロブロックの左のマクロブロックを含んでおり、
    前記マクロブロック選択ステップは、Ｎを１以上の整数として、
    前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に復号化されていないマクロブロックが存在する場合には、当該マクロブロックを次の現在マクロブロックとして選択し、
    前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に復号化されていないマクロブロックが存在しない場合には、前記複数のマクロブロックのうち、復号化されておらず、かつ、最も上の行の最も左に配置されたマクロブロックを次の現在マクロブロックとして選択することを特徴とする画像復号化方法。
16. 複数のマクロブロックを含む画像を符号化するコンピュータに実行させる画像符号化プログラムであって、
    画像を構成する複数のマクロブロックを取得するマクロブロック取得ステップと、
    前記複数のマクロブロックから、符号化対象のマクロブロックである現在マクロブロックを、所定の順序で選択して出力するマクロブロック選択ステップと、
    前記現在マクロブロックを、所定の段数のパイプライン処理を用いて符号化する符号化ステップと、
    前記符号化ステップによって符号化された前記マクロブロックを出力する出力ステップと
    をコンピュータに実行させる画像符号化プログラムにおいて、
    前記符号化ステップは、前記現在マクロブロックを、前記画像内において当該現在マクロブロックと所定の位置関係を満たすマクロブロックである参照マクロブロックの前記符号化後の情報を用いて符号化し、前記参照マクロブロックは、前記画像内において、前記現在マクロブロックの左のマクロブロックを含んでおり、
    前記マクロブロック選択ステップは、Ｎを１以上の整数として、
    前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に符号化されていないマクロブロックが存在する場合には、当該マクロブロックを次の現在マクロブロックとして選択し、
    前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に符号化されていないマクロブロックが存在しない場合には、前記複数のマクロブロックのうち、符号化されておらず、かつ、最も上の行の最も左に配置されたマクロブロックを次の現在マクロブロックとして選択することを特徴とするコンピュータに実行させる画像符号化プログラム。
17. 画像を構成する複数のマクロブロックそれぞれを符号化することで生成された複数の符号化マクロブロックを復号化するコンピュータに実行させる画像復号化プログラムであって、
    複数の符号化マクロブロックを取得するマクロブロック取得ステップと、
    前記複数の符号化マクロブロックから、復号化対象の符号化マクロブロックである現在マクロブロックを、所定の順序で選択して出力するマクロブロック選択ステップと、
    前記現在マクロブロックを、所定の段数のパイプライン処理を用いて復号化する復号化ステップと、
    前記復号化ステップによって復号化されたマクロブロックから前記画像を再構成する再構成ステップと
    をコンピュータに実行させる画像復号化プログラムにおいて、
    前記復号化ステップは、前記現在マクロブロックを参照マクロブロックの復号化後の情報を用いて復号化し、
    前記参照マクロブロックは、当該参照マクロブロックを復号化して得られるマクロブロックと、前記現在マクロブロックを復号化して得られるマクロブロックとが、前記画像内で所定の位置関係を満たす符号化マクロブロックであり、前記参照マクロブロックは、前記現在マクロブロックの左のマクロブロックを含んでおり、
    前記マクロブロック選択ステップは、Ｎを１以上の整数として、
    前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に復号化されていないマクロブロックが存在する場合には、当該マクロブロックを次の現在マクロブロックとして選択し、
    前記画像内において、前回選択した現在マクロブロックの１つ下かつＮ個左に復号化されていないマクロブロックが存在しない場合には、前記複数のマクロブロックのうち、復号化されておらず、かつ、最も上の行の最も左に配置されたマクロブロックを次の現在マクロブロックとして選択することを特徴とするコンピュータに実行させる画像復号化プログラム。

Images