トップ :: H 電気 :: H04 電気通信技術




【発明の名称】 映像符号化並列処理方法，映像符号化装置，映像符号化プログラムおよびその記録媒体
【発明者】 【氏名】谷田 隆一

【氏名】清水 淳
【要約】 【課題】マクロブロック毎に演算量が異なる場合でも，符号化の並列処理を効率的に行うことができるようにする。

【構成】ブロックの符号化状態保持手段３０は，各ブロックの符号化状態を保持する。並列にブロック単位の符号化処理を行う符号化手段１０，２０は，例えばラスタ順または斜め順の異なる順番で全画面分のブロックについて次に符号化処理を行うブロックを指定するブロック番号指定手段１１，２１を備えると共に，ブロック番号指定手段１１，２１が指定したブロックの符号化状態に従って，少なくともそのブロックの符号化処理を行うか，符号化処理をスキップするか，他の符号化手段による処理終了を待つかを判定するスキップ判定制御手段１２，２２を備える。
【特許請求の範囲】
【請求項１】
各ブロックの符号化状態を保持する符号化状態保持手段と，並列に動作可能な複数の符号化手段とを有し，映像もしくは画像をブロックに分割して前記複数の符号化手段により符号化する映像符号化並列処理方法であって，
前記符号化手段が，
各符号化手段毎に，それぞれ異なる順番で全画面分のブロックについて次に符号化処理を行う符号化対象ブロックを選択し，
前記選択された符号化対象ブロックの符号化状態を，前記符号化状態保持手段から取得し，その符号化状態に従って，少なくともその符号化対象ブロックの符号化処理を行うか，符号化処理をスキップするか，他の符号化手段による処理終了を待つかを判定し，
判定結果に応じた処理を実行する
ことを特徴とする映像符号化並列処理方法。
【請求項２】
請求項１記載の映像符号化並列処理方法において，
前記符号化手段は，
前記符号化対象ブロックの符号化処理の開始時に前記符号化状態保持手段が保持する符号化対象ブロックの符号化状態を符号化前から符号化中の状態に更新し，符号化処理の終了時に符号化状態を符号化中から符号化済みに更新し，
前記選択された符号化対象ブロックが，符号化前の状態である場合に，そのブロックの符号化処理を行い，符号化中の状態である場合に，他の符号化手段によりそのブロックの符号化が終了するまで処理を待ち，符号化済みの状態の場合に，処理対象を次のブロックへとスキップする
ことを特徴とする映像符号化並列処理方法。
【請求項３】
映像もしくは画像をブロックに分割して符号化する映像符号化装置であって，
各ブロックの符号化状態を保持する符号化状態保持手段と，
ブロック単位の符号化処理を行う複数の符号化手段とを備え，
前記符号化手段は，
各符号化手段毎に，それぞれ異なる順番で全画面分のブロックについて次に符号化処理を行うブロックを指定するブロック番号指定手段と，
前記ブロック番号指定手段が指定したブロックの符号化状態を，前記符号化状態保持手段から得て，その符号化状態に従って，少なくともそのブロックの符号化処理を行うか，符号化処理をスキップするか，他の符号化手段による処理終了を待つかを判定する制御手段とを備える
ことを特徴とする映像符号化装置。
【請求項４】
請求項３記載の映像符号化装置において，
前記符号化状態保持手段は，各ブロックの符号化状態として，符号化前，符号化中または符号化済みを示す情報を保持し，
前記制御手段は，前記ブロック番号指定手段により指定されたブロックが，符号化前の状態である場合に，そのブロックの符号化処理を行わせ，符号化中の状態である場合に，他の符号化手段によりそのブロックの符号化が終了するまで処理を待たせ，符号化済みの状態の場合に，処理対象を次のブロックへとスキップさせ，
前記符号化手段は，各ブロックの符号化処理の開始および終了時に，前記符号化状態保持手段が保持する符号化状態を更新するように構成される
ことを特徴とする映像符号化装置。
【請求項５】
請求項１または請求項２記載の映像符号化並列処理方法を，コンピュータに実行させるための映像符号化プログラム。
【請求項６】
請求項１または請求項２記載の映像符号化並列処理方法を，コンピュータに実行させるための映像符号化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】【技術分野】
【０００１】
本発明は，映像あるいは静止画を複数の小領域に分割し，順次符号化処理を行う映像符号化技術に関し，特に，小領域単位で並列に効率よく符号化するための映像符号化並列処理方法，映像符号化装置，映像符号化プログラムおよびその記録媒体に関するものである。
【背景技術】
【０００２】
ＭＰＥＧ−２やＨ．２６４をはじめ，現在広く用いられている映像符号化方式は，フレームを矩形の小領域に分割し，各領域毎に順次符号化する方法が主流となっている（非特許文献１，非特許文献２参照）。
【０００３】
例として，映像符号化方式Ｈ．２６４を取り上げる。図６は，Ｈ．２６４のマクロブロックの符号化順序を示す。Ｈ．２６４では，入力映像を１６×１６画素のマクロブロックと呼ばれる単位に区切り，その単位で符号化処理を行う。符号化の順序は，通常左上のマクロブロック（（ｘ，ｙ）＝（０，０））から開始し，終わったら順次右隣のマクロブロックへと処理を進める。一ライン分のマクロブロックの処理が済むと，１段下の左端のマクロブロックへと移り，また右に向かって順に処理していく。
【０００４】
Ｈ．２６４の符号化処理のフローチャートの一例を図７に示す。最初の符号化対象マクロブロックを左上（（ｘ，ｙ）＝（０，０））のマクロブロックとし（Ｓ３０１），左上のマクロブロックから順に，以下のような処理を行う。まず，符号化対象マクロブロックについてイントラ予測モードを決定し，その予測コストを求める（Ｓ３０２）。次に，動き探索を行ってインター予測モードを決定し，その予測コストを求める（Ｓ３０３）。そして，イントラ予測モードとインター予測モードとの予測コストを比較し，小さい方を予測モードとして決定する（Ｓ３０４）。
【０００５】
その後，選択した予測モードについて，予測画像と原画像の差分である予測残差を求め，ＤＣＴ変換・量子化を施し（Ｓ３０５），予測モード情報と共にエントロピー符号化を施す（Ｓ３０６）。
【０００６】
一方，量子化値を逆量子化・逆変換してイントラ予測用の復号画像を生成した（Ｓ３０７）後に，デブロッキングフィルタを適用し，動き補償用の参照画像を生成する（Ｓ３０８）。そして，最後のマクロブロックかを判定し（Ｓ３０９），そうでないならば符号化対象を次のマクロブロックとし（Ｓ３１０），上記の処理（Ｓ３０２〜Ｓ３１０）を，最後のマクロブロックの符号化が終了するまで繰り返す。このような処理により，Ｈ．２６４の符号化を行うことができる。
【０００７】
Ｈ．２６４符号化装置のブロック図の一例を図８に示す。Ｈ．２６４符号化装置は，ＭＢ番号生成部２０１，ＭＢ切り出し部２０２，減算器２０３，ＤＣＴ部２０４，量子化部２０５，逆量子化部２０６，ＩＤＣＴ部２０７，加算器２０８，インター予測モード決定部２０９，イントラ予測モード決定部２１０，予測モード選択部２１１，スイッチ２１２，復号画像保存バッファ２１３，フィルタ２１４，参照画像保存バッファ２１５，符号化情報保存バッファ２１６，エントロピー符号化部２１７から構成される。
【０００８】
ＭＢ番号生成部２０１は，符号化情報保存バッファ２１６から制御信号を受けると，次に符号化処理するマクロブロックの番号を生成し，ＭＢ切り出し部２０２に送る。ＭＢ切り出し部２０２は，ＭＢ番号生成部２０１からマクロブロック番号を受け取ると，その番号に対応する１６×１６画素を原画像から切り出し，減算器２０３，インター予測モード決定部２０９およびイントラ予測モード決定部２１０に送る。
【０００９】
減算器２０３は１６×１６画素の原画像と予測画像との差分を取り，ＤＣＴ部２０４へ送る。ＤＣＴ部２０４は，予測差分にＤＣＴを施し量子化部２０５へ送る。量子化部２０５は，予め定められた量子化ステップ幅で量子化を行い，その結果を符号化情報保存バッファ２１６と逆量子化部２０６へ送る。
【００１０】
逆量子化部２０６は，入力された量子化値に逆量子化を施し，ＩＤＣＴ部２０７へ送る。ＩＤＣＴ部２０７は，逆量子化部２０６から送られてきた２次元周波数データに逆ＤＣＴを施し，加算器２０８に送る。加算器２０８は，スイッチ２１２から送られる予測信号とＩＤＣＴ部２０７から送られる差分信号を加算し，復号画像を生成して復号画像保存バッファ２１３に送る。
【００１１】
インター予測モード決定部２０９は，符号化情報保存バッファ２１６から送られる隣接ブロックの予測モード情報を使い，入力された原画像と参照画像保存バッファ２１５内の参照画像の間で動き補償を行って，求めた参照画像を予測画像としてスイッチ２１２へ出力する。同時に，動きベクトルなどの予測モード情報と予測コストを予測モード選択部２１１へ送る。
【００１２】
イントラ予測モード決定部２１０は，原画像と復号画像保存バッファ２１３から入力された隣接画素を用いてイントラ予測モードを決定し，予測画像をスイッチ２１２へ出力すると共に，イントラ予測モードと予測コストを予測モード選択部２１１へ送る。
【００１３】
予測モード選択部２１１は，インター予測モード決定部２０９とイントラ予測モード決定部２１０から送られる予測コストを比較し，予測コストが低い方を予測モードとして選択する。そして，選択した方の予測モード情報を符号化情報保存バッファ２１６に送信すると共に，選択した方の予測画像が出力されるように制御信号でスイッチ２１２を切り換える。スイッチ２１２は，予測モード選択部２１１から送られる制御信号に従って，入力の切り換えを行い，選択された予測モードの予測画像を減算器２０３と加算器２０８に送る。
【００１４】
復号画像保存バッファ２１３は加算器２０８から送られる復号画像を保持し，順次，フィルタ２１４に送ると共に，イントラ予測モード決定部２１０に符号化対象マクロブロックの周辺画像を送る。フィルタ２１４は，復号画像にデブロッキングフィルタを施し，参照画像保存バッファ２１５に送る。参照画像保存バッファ２１５は，フィルタ２１４から送られるフィルタ処理後の復号画像を保持し，参照画像としてインター予測モード決定部２０９に送信する。
【００１５】
符号化情報保存バッファ２１６は，量子化部２０５から送られてくる量子化値と，予測モード選択部２１１から送られる予測モード情報を保持し，順次，エントロピー符号化部２１７へ渡す。また，隣接ブロックの予測モード情報をインター予測モード決定部２０９へ送ると共に，次のマクロブロックの処理を促す制御信号をＭＢ番号生成部２０１へ送る。エントロピー符号化部２１７は，符号化情報保存バッファ２１６に保持された符号化情報を，順次エントロピー符号化し，符号化ストリームを出力する。以上のような構成にすることで，図７に示す処理を行うことができる。
【００１６】
このＨ．２６４の符号化処理を，複数の処理部を用いてマクロブロック単位で並列に行うことを考える。Ｈ．２６４では，マクロブロックの符号化に，隣接するマクロブロックの符号化結果を用いることで，符号化効率を高めている。詳しい符号化方法は本発明の本質と直接関係が無いため省略するが，図９に示すマクロブロックＥの符号化の際には，隣接マクロブロックＡ，Ｂ，Ｃ，Ｄの符号化結果を必要とする（非特許文献３参照）。したがって，マクロブロック単位で並列に符号化処理を行う場合，既に周囲のマクロブロックＡ，Ｂ，Ｃ，Ｄの符号化が終わっているような組み合わせで符号化を行う必要がある。
【００１７】
２並列処理の従来法の一例としては，図１０のＰ，Ｑの位置関係にあるマクロブロックを同時に処理する方法がある。このような位置関係のマクロブロックであれば，図９に示す隣接マクロブロックの符号化が終わっていることになるので，マクロブロックＰとＱを同時に処理することができる。このときの各処理部のフローチャートの例を図１１に示す。
【００１８】
一つ目の処理系は処理を開始すると，左上（（ｘ，ｙ）＝（０，０））のマクロブロックをスタートとし（Ｓ４０１），以下の処理を繰り返す。まず，符号化対象マクロブロックの一つ上のマクロブロックＭＢ［ｘ］［ｙ−１］が符号化済みかをチェックし（Ｓ４０２），符号化が終了していなければ終了するまで待つ（Ｓ４０３）。一つ上のマクロブロックの符号化が終了していたなら，次に符号化対象マクロブロックの右上のマクロブロックＭＢ［ｘ＋１］［ｙ−１］が符号化済みかをチェック（Ｓ４０４）し，符号化が終了していなければ終了するまで待つ（Ｓ４０５）。
【００１９】
右上のマクロブロックの符号化も終了していたなら，図７のフローチャートに示す処理（Ｓ３０２〜Ｓ３０８）に従って符号化対象マクロブロックＭＢ［ｘ］［ｙ］の符号化を行う（Ｓ４０６）。その符号化が終了したら，ｘに１を加算し，一つ右のマクロブロックに移動する（Ｓ４０７）。右にマクロブロックがあれば，すなわち，ｘ＝ｘ＿ｍａｘ（ｘ＿ｍａｘは水平方向のマクロブロック数）でなければ（Ｓ４０８），そのマクロブロックについて上記の処理を繰り返す（Ｓ４０２〜Ｓ４０８）。右端だったならば，すなわち，ｘ＝ｘ＿ｍａｘになったならば，ｘを０とし，ｙに２を加算して，２つ下のラインの一番左のマクロブロックに移動する（Ｓ４０９）。そこにマクロブロックがあれば，すなわち，ｙ≧ｙ＿ｍａｘ（ｙ＿ｍａｘは垂直方向のマクロブロック数）でなければ（Ｓ４１０），上記の処理を繰り返す（Ｓ４０２〜Ｓ４１０）。２つ下にマクロブロックが無ければ，すなわち，ｙ≧ｙ＿ｍａｘになったならば，そこで処理を終了する。
【００２０】
２つ目の処理系は，処理を開始すると２ライン下の左端のマクロブロック（（ｘ，ｙ）＝（０，１））からスタートし（Ｓ４０１），一つ目の処理系と同じ処理を行う（Ｓ４０２〜Ｓ４１０）。以上のように処理することで，２並列で符号化処理を行うことができる。
【００２１】
図１２に，上記の処理を実現させるためのブロック図の一例を示す。この装置は，２ラインおきＭＢ番号生成部Ａ３０１，２ラインおきＭＢ番号生成部Ｂ３０２，制御部３０３，３０４，ＭＢ符号化器３０５，３０６，フレームメモリ３０７，ステータス保存メモリ３０８，参照画像保存バッファ３０９，フィルタ３１０，復号画像保存バッファ３１１，符号化情報保存バッファ３１２，エントロピー符号化部３１３から構成される。このうち，ＭＢ符号化器は図８の破線で囲まれた部分と同様の処理を行うものとする。また，フィルタ３１０，エントロピー符号化部３１３は，図８の同名のものと同等の機能を有する。参照画像保存バッファ３０９，復号画像保存バッファ３１１，符号化情報保存バッファ３１２は，図８の同名のものと同等の機能を持つが，入出力を２系統所持する。
【００２２】
フレームメモリ３０７は原画像を保持し，符号化対象マクロブロックの画像を各ＭＢ符号化器３０５，３０６に送る。
【００２３】
２ラインおきＭＢ番号生成部Ａ３０１，２ラインおきＭＢ番号生成部Ｂ３０２は，符号化情報保存バッファ３１２から制御信号として前のマクロブロックの符号化終了信号を受け取ると，ステータス保存メモリ３０８に当該マクロブロックの符号化終了信号を送る。そして，次の符号化対象マクロブロック番号を生成して制御部３０３，３０４に送る。２ラインおきＭＢ番号生成器Ａ３０１，２ラインおきＭＢ番号生成部Ｂ３０２が生成するマクロブロック番号の順序は，図１３に示す通りである。
【００２４】
制御部３０３，３０４は，２ラインおきＭＢ番号生成部Ａ３０１，２ラインおきＭＢ番号生成部Ｂ３０２からＭＢ番号を受けとると，ステータス保存メモリ３０８のステータス情報から，上，右上隣接マクロブロックが符号化済みかどうかを判断し，共に符号化済みであれば，符号化対象マクロブロック番号をＭＢ符号化器３０５，もしくはＭＢ符号化器３０６に送信する。
【００２５】
このような構成にすることで，図１１に示すフローチャートに従った処理を行うことができる。
【００２６】
また，特許文献１には，イントラ予測を用いて符号化する画像符号化装置において，マクロブロックのパイプライン処理を容易化し，また，複数のマクロブロックに対する動きベクトル探索を並列化することを目的として，符号化するマクロブロックを選択するときに，現在マクロブロックと現在マクロブロックがイントラ予測あるいは動きベクトル探索で参照するマクロブロックの順序番号の差が２以上となるように，符号化するマクロブロックの順序を選択するマクロブロック順序選択手段を持つ画像符号化装置が開示されている。
【非特許文献１】ＭＰＥＧ−２：小野定康，鈴木純司，「わかりやすいＪＰＥＧ／ＭＰＥＧ２の技術」，オーム社，PP.133（2001）
【非特許文献２】Ｈ．２６４： Text of ISO/IEC 14496 10 Advanced Video Coding 3rd Edition ，PP.19 （2004）
【非特許文献３】Ｈ．２６４の符号化依存関係：大久保榮，角野眞也，菊池義浩，鈴木輝彦，「Ｈ．２６４／ＡＶＣ教科書」，インプレス，pp.108，111 ，120 （2004）
【特許文献１】特開２００５−２９５５２６号公報
【発明の開示】
【発明が解決しようとする課題】
【００２７】
図１０で示したような並列処理手法は，マクロブロックＰ，Ｑの符号化にかかる処理時間が全く同じである場合には効率よく働く。しかし，処理の高速化のために動きベクトルの探索範囲を可変にする場合など，マクロブロック毎の処理時間が大きく異なるケースも存在する。このような場合，処理待ちが頻繁に入るため，処理効率が大きく低下するという問題がある。例えば探索範囲を限定させることで，マクロブロックＱがＰの１０分の１の処理時間で符号化できたとしても，その右隣のマクロブロックの処理を開始するためにはマクロブロックＰの処理が終わるまで待たなければならず，マクロブロックＱの演算量削減効果が薄れてしまう。
【００２８】
また，特許文献１に記載された方法を用いた場合にも，各マクロブロックの処理時間が全く同じ場合には有効に働くが，マクロブロック毎に処理時間が異なる場合には，「処理待ち」の時間が発生するという問題がある。
【００２９】
本発明は上記問題点の解決を図り，マクロブロック毎に演算量が異なる場合でも，符号化の並列処理を効率的に行うことができるようにすることを目的とする。
【課題を解決するための手段】
【００３０】
前記の課題を解決するために，本発明では，各処理系がそれ単体でも全マクロブロックの符号化ができるような順序でマクロブロック番号を順に指定する手段と，既に符号化済みのマクロブロックをスキップして次のマクロブロックの符号化処理を行う手段と，処理対象マクロブロックが処理開始できない場合には処理ができるまで待つ手段を，並列処理のタスクの数だけ持っていることを特徴とする。なお，各マクロブロック番号を生成する手段は，生成される番号の順序が処理系毎に全て異なっていることを特徴とする。
【００３１】
図１は，本発明の概要を説明する図である。ブロック単位で並列に符号化処理を行う処理系として，符号化手段１０による処理系Ａと，符号化手段２０による処理系Ｂとがある。ブロックの符号化状態保持手段３０は，各ブロックが符号化済みであるか符号化中であるか符号化前（未処理）であるかの情報を保持する。
【００３２】
処理系Ａのブロック番号指定手段１１は，図１の（ａ）に示すように，ラスタ順で符号化対象のブロック番号を指定する。一方，処理系Ｂのブロック番号指定手段２１は，図１の（ｂ）に示すように，斜め順で符号化対象のブロック番号を指定する。
【００３３】
処理系Ａのスキップ判定制御手段１２および処理系Ｂのスキップ判定制御手段２２は，それぞれブロックの符号化状態保持手段３０を参照し，指定された符号化対象のブロック番号に該当するブロックの符号化状態に従ってそのブロックの符号化処理を直ぐに行うか，スキップするか，または一方の処理系による符号化処理の終了を待つかを判定する。
【００３４】
スキップ判定制御手段１２または２２による制御のもとに，符号化手段１０または２０において，一つのブロックの符号化を開始すると，ブロックの符号化状態保持手段３０が保持するブロックの符号化状態は，符号化前から符号化中の状態に更新され，符号化が終了すると，符号化中から符号化済みの状態に更新される。
【００３５】
各スキップ判定制御手段１２，２２は，符号化対象のブロックの符号化状態が符号化前の場合には，符号化手段１０，２０に符号化処理を実施させる。また，符号化対象のブロックの符号化状態が符号化済みの場合には，処理対象を次の符号化対象のブロックへとスキップさせる。また，符号化対象ブロックの符号化状態が符号化中である場合には，他の符号化手段２０，１０によりそのブロックの符号化が終了するまで，符号化処理を待たせる。
【００３６】
ブロック番号指定手段１１，２１が，画面すべてのマクロブロック番号を符号化対象として指示し，スキップ判定制御手段１２，２２が，指示されたマクロブロックが既に符号化済みの場合には，それを飛ばしてさらに次のマクロブロックへと処理対象を移していく点が従来技術と顕著に異なる。このような特徴により，符号化済みマクロブロックを飛ばして処理可能なマクロブロックを探していくため，各マクロブロックがどのプロセスで符号化されるかは，状況によって毎回変わることになり，結果的に処理の待ち時間が少なくなる。
【００３７】
処理系Ａと処理系Ｂの２系列の並列処理の例を示したが，３系列以上であっても同様に本発明を実施することができる。
【００３８】
本発明による並列符号化処理のフローチャートの一例を図２に示す。図中，マクロブロックをＭＢと記している。このフローは，本発明における各処理系の処理手順の例である。処理が始まると，符号化対象マクロブロックの処理開始点（ｘ，ｙ）を設定し（Ｓ１），開始点として設定された符号化対象マクロブロックから順に，以下の処理（Ｓ２〜Ｓ７）を繰り返す。
【００３９】
まず，処理対象マクロブロックが符号化済みかどうかを，ブロックの符号化状態保持手段３０を参照して調べ（Ｓ２），もし符号化済みならば，ステップＳ６へ進み，次のマクロブロックに移動する。符号化済みでないならば，処理対象マクロブロックが符号化中かどうかを調べ（Ｓ３），符号化中ならば，符号化が終了するまで待つ（Ｓ４）。それ以外ならば，処理対象マクロブロックは符号化前の未処理状態であるため，処理対象マクロブロックを図７の手順（Ｓ３０２〜Ｓ３０８）に従って符号化処理し（Ｓ５），次のマクロブロックに移動する（Ｓ６）。全マクロブロックの符号化処理が終了したならば，そこで符号化処理を終了し（Ｓ７），まだ終了していないならば上記ステップＳ２〜Ｓ７の処理を繰り返す。
【００４０】
以上の映像符号化の並列処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【発明の効果】
【００４１】
本発明によれば，各々の符号化手段が並列に異なる順序でマクロブロックの符号化処理を行う。また，各符号化手段がそれ単体でも１画面分の符号化が可能な順序のため，マクロブロック毎に演算量が異なる場合でも，待ちが発生する回数やその影響が少なくなり，効率的な符号化処理を行うことができる。
【発明を実施するための最良の形態】
【００４２】
以下，本発明の実施の形態を図面を用いて説明する。
【００４３】
本実施の形態では，ラスタ順にマクロブロックの符号化を行う処理系Ａと，斜め順にマクロブロックの符号化を行う処理系Ｂの二つを並列に動作させた場合について述べる。それぞれの処理系を単独で動作させた場合のマクロブロックの処理順序は，図１の（ａ），（ｂ）に示す通りである。処理系Ａは，左上の（０，０）マクロブロックから始まり，右に向かって符号化処理を行う。処理系Ｂは，開始位置（ｘ，ｙ）＝（０，０）から，斜め順に符号化処理を行う。処理系Ａはもちろん単体で符号化処理が可能であるが，処理系Ｂも単体で１画面分の符号化処理を行うことができる。また，処理系には優先順位を設け，同じマクロブロックを同時にアクセスした場合には処理系Ａを優先するとする。
【００４４】
まず，処理系Ａのフローチャートの例を図３に示す。符号化が始まると，まず左上のマクロブロック（（ｘ，ｙ）＝（０，０））をスタートとし（Ｓ１０１），以下の処理（Ｓ１０２〜Ｓ１０９）を繰り返す。
【００４５】
まず，処理対象マクロブロックＭＢ［ｘ］［ｙ］が符号化済みかどうかを調べ（Ｓ１０２），もし符号化済みならば，ステップＳ１０６へ進む。処理対象マクロブロックＭＢ［ｘ］［ｙ］が符号化中ならば（Ｓ１０３），符号化が終了するまで待つ（Ｓ１０４）。それ以外ならば，ステップＳ１０５へ進み，処理対象マクロブロックＭＢ［ｘ］［ｙ］を，図７の手順（Ｓ３０２〜Ｓ３０８）に従って符号化処理する。
【００４６】
その後，ｘに１を加算して，一つ右隣のマクロブロックに移動する（Ｓ１０６）。右にマクロブロックがあれば，すなわち，ｘ＝ｘ＿ｍａｘ（ｘ＿ｍａｘは水平方向のマクロブロック数）でなければ（Ｓ１０７），そのマクロブロックについて上記の処理を繰り返す（Ｓ１０２〜Ｓ１０７）。もし右端を外れた場合には，すなわち，ｘ＝ｘ＿ｍａｘになったならば，ｘを０とし，ｙに１を加算して，一段下の左端のマクロブロックに移動する（Ｓ１０８）。最後のマクロブロックまで処理が終了したかどうか，すなわち，ｙ＝ｙ＿ｍａｘ（ｙ＿ｍａｘは垂直方向のマクロブロック数）になったかどうかを判定し（Ｓ１０９），まだ未処理のマクロブロックがあれば，上記の処理（Ｓ１０２〜Ｓ１０９）を繰り返す。最後のマクロブロックまで処理が終了した場合には，そこで処理を終了する。このような手順で処理することで，処理系Ａは，処理系Ｂによって符号化が完了しているマクロブロックを抜かしながら，図１（ａ）に示す順序でマクロブロックの符号化を行うことができる。
【００４７】
次に，処理系Ｂのフローチャートの例を図４に示す。符号化が始まると，まず左上のマクロブロック（（ｘ，ｙ）＝（０，０））をスタートとし（Ｓ２０１），以下の処理（Ｓ２０２〜Ｓ２１２）を繰り返す。
【００４８】
まず，処理対象マクロブロックＭＢ［ｘ］［ｙ］が符号化済みかどうかを調べ（Ｓ２０２），もし符号化済みならば，ステップＳ２０６へ進む。処理対象マクロブロックＭＢ［ｘ］［ｙ］が符号化中ならば（Ｓ２０３），符号化が終了するまで待つ（Ｓ２０４）。それ以外ならば，ステップＳ２０５へ進み，処理対象マクロブロックＭＢ［ｘ］［ｙ］を図７の手順（Ｓ３０２〜Ｓ３０８）に従って符号化処理する。
【００４９】
その後，ｘから１を減算し，ｙに１を加算して，次のマクロブロックへ移動する（Ｓ２０６）。ｘの値が負になり，移動先にマクロブロックが存在しない場合には（Ｓ２０７），ｘにｙの値を代入し，ｙを０にする（Ｓ２０８）。次に，ｙ＝ｙ＿ｍａｘ（ｙ＿ｍａｘは垂直方向のマクロブロック数）になったかどうかを判定し（Ｓ２０９），ｙがｙ＿ｍａｘになった場合には，移動先にマクロブロックが存在しないので，ｘにｘ＋ｙ＋１の値を代入し，ｙを０にし，移動先を右斜め上の最上行のマクロブロックにする（Ｓ２１０）。次に，ｘ≧ｘ＿ｍａｘ（ｘ＿ｍａｘは水平方向のマクロブロック数）かどうかを判定し（Ｓ２１１），ｘ≧ｘ＿ｍａｘであった場合，すなわち，移動先のマクロブロックが右端を越えている場合には，ステップＳ２１２に進む。それ以外の場合には，上記のステップＳ２０２〜Ｓ２１１の処理を繰り返す。
【００５０】
ステップＳ２１２では，全マクロブロックの処理が終了したかどうか，すなわち，ｘがｘ＿ｍａｘ＋ｙ＿ｍａｘ−１になったかどうかを判定し，もし全マクロブロックの処理が終了したならば，そこで処理を終了する。まだ終了していないならば，ステップＳ２０６へ戻り，上記の処理（Ｓ２０２〜Ｓ２１２）を繰り返す。
【００５１】
このような手順で処理することで，処理系Ｂは，処理系Ａによって符号化が完了しているマクロブロックを抜かしながら，図１（ｂ）に示す順序でマクロブロックの符号化を行うことができる。なお，アクセスが競合した場合には，処理系Ａを優先するとしているため，０番目のマクロブロック（０，０）と１番目のマクロブロック（１，０）の符号化は処理系Ａが行い，処理系Ｂは実質的には２番目のマクロブロック（０，１）から符号化処理を行うことになる。
【００５２】
次に，本実施の形態による符号化装置のブロック図の一例を図５に示す。図中の点線で囲まれた２箇所が本発明の適用部分である。この装置はラスタ順ＭＢ番号生成部１０１（図１のブロック番号指定手段１１に相当する），斜め順ＭＢ番号生成部１０２（図１のブロック番号指定手段２１に相当する），スキップ付き制御部１０３（図１のスキップ判定制御手段１２に相当する），スキップ付き制御部１０４（図１のスキップ判定制御手段２２に相当する），ＭＢ符号化器１０５，１０６，フレームメモリ１０７，ステータス保存メモリ１０８（図１のブロックの符号化状態保持手段３０に相当する），参照画像保存バッファ１０９，フィルタ１１０，復号画像保存バッファ１１１，符号化情報保存バッファ１１２，エントロピー符号化部１１３から構成される。
【００５３】
ＭＢ符号化器１０５，１０６，フレームメモリ１０７，ステータス保存メモリ１０８，参照画像保存バッファ１０９，フィルタ１１０，復号画像保存バッファ１１１，符号化情報保存バッファ１１２，エントロピー符号化部１１３は，前述した図８または図１２における同名のものと同等の機能を有する。ただし，ステータス保存メモリ１０８は，処理系Ａと処理系Ｂのアクセスが競合した場合には，処理系Ａの処理を優先するものとする。
【００５４】
ラスタ順ＭＢ番号生成部１０１は，スキップ付き制御部１０３から制御信号を受けると，次の符号化対象マクロブロック番号を生成してスキップ付き制御部１０３に送る。生成されるブロック番号の順序は，図１（ａ）に示す通りである。
【００５５】
斜め順ＭＢ番号生成部１０２は，スキップ付き制御部１０４から制御信号を受けると，次の符号化対象マクロブロック番号を生成してスキップ付き制御部１０４に送る。生成されるブロック番号の順序は，図１（ｂ）に示す通りである。
【００５６】
スキップ付き制御部１０３，１０４は，符号化情報保存バッファ１１２から制御信号として前のマクロブロックの符号化終了信号を受け取ると，ステータス保存メモリ１０８に当該マクロブロックの符号化終了信号を送ると共に，ラスタ順ＭＢ番号生成部１０１もしくは斜め順ＭＢ番号生成部１０２に制御信号を送り，これらから次の符号化対象マクロブロック番号を受け取る。
【００５７】
次に，スキップ付き制御部１０３，１０４は，受け取ったマクロブロックの符号化状態をステータス保存メモリ１０８から送られるステータス情報から判定し，もし符号化されていなければそのマクロブロック番号をＭＢ符号化器１０５もしくは１０６に送ると共に，当該マクロブロックが符号化中であることを示す制御信号をステータス保存メモリ１０８に送る。もし符号化中ならば符号化終了まで待つ。符号化が終了しているならば，ラスタ順ＭＢ番号生成部１０１もしくは斜め順ＭＢ番号生成部１０２に制御信号を送り，これらから次の符号化対象マクロブロック番号を受け取る。以上のような構成を用いることで，図３，図４に示す処理を行うことができる。
【００５８】
以上の実施の形態では，あるマクロブロックＭＢ［ｘ］［ｙ］の処理終了後，次に処理するマクロブロックＭＢは，処理系Ａの場合，すぐ横のマクロブロックＭＢ［ｘ＋１］［ｙ］（図１（ａ））とし，処理系Ｂの場合，左斜め下のマクロブロックＭＢ［ｘ−１］［ｙ＋１］（図１（ｂ））とした。
【００５９】
他にも，ＭＢ［ｘ］［ｙ］の次に処理するマクロブロックＭＢを，
例２：ＭＢ［ｘ−２］［ｙ＋１］
例３：ＭＢ［ｘ−３］［ｙ＋１］
・・ ・・・
例Ｎ：ＭＢ［ｘ−Ｎ］［ｙ＋１］
とする順番で処理することもでき，３以上の処理系によって並列処理する場合に，これらの中から異なるものを選択して，本発明を実施することができる。
【００６０】
本発明の検証実験を次のように行った。ソフトウェアのプロセス（スレッド）により，マクロブロックの符号化順序が異なる二つのスレッドを並列動作させた。まず，４種類のテストシーケンス（７２０×４８０画素，３０ｆｐｓ）について，打ち切り処理がある木探索を用い，ＳＡＤ計算時の絶対値演算回数を各マクロブロック毎に計測した。なお，動き補償ブロックサイズは，８×８固定，探索範囲は±１６×１６とした。
【００６１】
次に，絶対値演算１回を１ステップとして，各マクロブロックの演算回数を演算時間に見立て，２スレッドで１フレームを並列探索する場合の処理待ちステップ数の合計を，従来技術を用いた場合と本発明を用いた場合とで比較した。従来技術としては，図１０で説明した方法を用いた。また，本発明による各スレッドのマクロブロック処理順の概要は，図１（ａ），（ｂ）に示す通りとした。
【００６２】
処理待ちステップ数の比較結果は，４種類のテストシーケンスについて，以下のとおりであった。
============================================================================
シーケンス（７２０×４８０） 従来技術 本発明 削減率
"Yachting" ６３１０ ３６４５ −４２．２％
"Rustling Leaves" １１９１１ ６５３３ −４５．２％
"Soccer" １１８４２ ６４３０ −４５．７％
"Bronze with Credits" １３２７６ ５２４８ −６０．５％
============================================================================
数値は，１フレームの符号化処理の間に「処理待ち」に費やした時間の合計値を示している。数値の単位は，ステップ（１ステップ中に絶対値演算１回を行うことが可能）である。削減率は，本発明を用いた場合に，従来技術と比較して処理待ちステップ数がどの程度削減されたかを割合で示したものである。この結果から，本発明を用いた場合，従来技術より処理待ちのステップ数がほぼ半減していることがわかる。これは，スレッド毎に処理するマクロブロックの順番が大きく異なることで，「待ち」の発生確率が低減されたためと考えられる。
【図面の簡単な説明】
【００６３】
【図１】本発明の概要を説明する図である。
【００６４】

【図２】本発明による並列符号化処理のフローチャートの一例を示す図である。
【図３】本実施の形態による処理系Ａの処理手順を示すフローチャートである。
【図４】本実施の形態による処理系Ｂの処理手順を示すフローチャートである。
【図５】本実施の形態による符号化装置のブロック図である。
【図６】Ｈ．２６４のマクロブロックの符号化順序を示す図である。
【図７】Ｈ．２６４の符号化処理のフローチャートの一例を示す図である。
【図８】Ｈ．２６４符号化装置の一例のブロック図である。
【図９】符号化対象マクロブロックの符号化に必要となる隣接マクロブロックを説明する図である。
【図１０】２並列処理するマクロブロックの位置関係（従来技術）を示す図である。
【図１１】２並列で符号化する場合の符号化処理フローチャート（従来技術）の一例を示す図である。
【図１２】２並列で符号化する場合の符号化装置（従来技術）の一例を示すブロック図である。
【図１３】２並列で符号化する場合のマクロブロックの符号化順序（従来技術）を示す図である。
【符号の説明】
【００６５】
１０，２０ 符号化手段
１１，２１ ブロック番号指定手段
１２，２２ スキップ判定制御手段
３０ ブロックの符号化状態保持手段
１０１ ラスタ順ＭＢ番号生成部
１０２ 斜め順ＭＢ番号生成部
１０３，１０４ スキップ付き制御部
１０５，１０６ ＭＢ符号化器
１０７ フレームメモリ
１０８ ステータス保存メモリ
１０９ 参照画像保存バッファ
１１０ フィルタ
１１１ 復号画像保存バッファ
１１２ 符号化情報保存バッファ
１１３ エントロピー符号化部
【出願人】 【識別番号】０００００４２２６
【氏名又は名称】日本電信電話株式会社
【出願日】 平成１８年７月２７日（２００６．７．２７）
【代理人】 【識別番号】１０００８７８４８
【弁理士】
【氏名又は名称】小笠原 吉義

【識別番号】１０００９５０７２
【弁理士】
【氏名又は名称】岡田 光由

【識別番号】１００１２１５１１
【弁理士】
【氏名又は名称】小田 直
【公開番号】 特開２００８−３５０２９（Ｐ２００８−３５０２９Ａ）
【公開日】 平成２０年２月１４日（２００８．２．１４）
【出願番号】 特願２００６−２０４３２０（Ｐ２００６−２０４３２０）