(57)【要約】【課題】本発明は、画像を並列処理にて符号化するに際し符号化効率や画質の低下を防止可能な画像符号化装置を提供する。【解決手段】入力される画像を符号化してビットストリームを生成する符号化手段１０ｂ、画像内の符号化順序を制御するために符号化手段を制御する符号化制御手段１０ａを備える。符号化制御手段１０ａは、画像をブロックを含む各領域に分割して前記各領域の形状を設定し各領域に領域処理順位を各々設定し、各領域処理順位に従って各領域を符号化する際に領域の制御条件として、同一の領域処理順位の各領域間では互いに符号化情報の利用を不可とし、一領域処理順位の領域は、一の領域処理順位より優先度の高い他領域処理順位の領域への符号化情報の利用を可とするように制御する。【選択図】図１
2010029850.tif 000002
【特許請求の範囲】
【請求項１】
入力される画像を符号化してビットストリームを生成する符号化手段と、
前記画像内の符号化順序を制御するために前記符号化手段を制御する符号化制御手段と、を備え、
前記符号化制御手段が、
前記画像をブロックを含む各領域に分割して前記各領域の形状を設定するとともに前記各領域に領域処理順位を各々設定し、
前記各領域処理順位に従って前記各領域を符号化する際に、前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たす符号化をするように制御することを特徴とする画像符号化装置。
【請求項２】
請求項１に記載の画像符号化装置において、
前記符号化制御手段は、前記領域内をブロック単位で符号化する際に前記各領域に応じてブロックの符号化の順序を変更する制御することを特徴とする画像符号化装置。
【請求項３】
請求項２に記載の画像符号化装置において、
前記符号化制御手段は、一の前記領域の前記ブロック符号化順序を他の前記領域に隣接するブロック部分から符号化を開始し、前記他の領域における前記一の領域隣接部分の符号化情報を利用するように制御することを特徴とする画像符号化装置。
【請求項４】
請求項３に記載の画像符号化装置において、
前記符号化制御手段は、前記ブロック符号化順序を前記領域の形状情報と前記領域処理順位に応じて決定するように制御することを特徴とする画像符号化装置。
【請求項５】
請求項３に記載の画像符号化装置において、
前記符号化制御手段は、前記領域の形状情報と前記領域処理順位と前記ブロック符号化順序とに関する情報をも符号化してビットストリーム中に出力するように制御することを特徴とする画像符号化装置。
【請求項６】
請求項５に記載の画像符号化装置において、
前記符号化制御手段は、前記同一の領域処理順位が割り当てられた前記各領域を並列に符号化するように制御することを特徴とする画像符号化装置。
【請求項７】
入力されるビットストリームを復号化して復号化画像を生成する復号化手段と、前記ビットストリームの復号化順序を制御するために前記復号化手段の動作を制御する復号化制御手段と、を備え、
前記復号化制御手段が、
前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含む前記ビットストリームを解析し、この領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する前記ビットストリームを復号化するように制御し、
前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をするように制御することを特徴とする画像復号化装置。
【請求項８】
請求項７に記載の画像復号化装置において、
前記復号化制御手段は、
前記領域に対応するビットストリームをブロック単位で復号化する際に、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に応じてブロック復号化順序を変更するように制御することを特徴とする画像復号化装置。
【請求項９】
画像符号化装置を用いた画像符号化方法であって、
入力される画像をブロックを含む各領域に分割して各領域の形状を設定し、
前記各領域に領域処理順位を各々設定し、
この領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化してビットストリームを生成する符号化の制御を行い、
前記符号化制御の際に、前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域では、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たす符号化をするように制御することを特徴とする画像符号化方法。
【請求項１０】
請求項９に記載の画像符号化方法において、
前記符号化制御に際しては、
前記領域内をブロック単位で符号化するためのブロック符号化順序を、前記各領域毎に変更するように制御することを特徴とする画像符号化方法。
【請求項１１】
請求項１０に記載の画像符号化方法において、
前記符号化制御に際しては、
前記ブロック符号化順序を、前記領域の形状情報と前記領域処理順位とに応じて決定するように制御することを特徴とする画像符号化方法。  
【請求項１２】
請求項１１に記載の画像符号化方法において、
前記符号化制御に際しては、
一の前記領域の前記ブロック符号化順序を他の前記領域に隣接するブロック部分から符号化を開始し、前記他の領域における前記一の領域隣接部分の符号化情報を利用するように制御することを特徴とする画像符号化方法。
【請求項１３】
請求項１２に記載の画像符号化方法において、
前記符号化制御に際しては、
前記領域の形状情報と前記領域処理順位と前記ブロック符号化順序とに関する情報をも符号化し、これらをビットストリーム中に出力するように制御することを特徴とする画像符号化方法。
【請求項１４】
請求項１３に記載の画像符号化方法において、
前記符号化制御に際しては、
前記同一の領域処理順位が割り当てられた前記各領域を並列に符号化するように制御することを特徴とする画像符号化方法。
【請求項１５】
画像復号化装置を用いた画像復号化方法であって、
前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含むビットストリームを入力し、入力したビットストリームの前記領域処理順位と前記領域の形状情報とを取得してこれを解析し、
前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する各ビットストリームを復号化して復号化画像を生成するように復号化制御を行い、前記復号化制御に際しては、前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をするように制御することを特徴とする画像復号化方法。
【請求項１６】
請求項１５に記載の画像復号化方法において、
前記復号化制御に際しては、
前記領域に対応するビットストリームをブロック単位として復号化するように制御し、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に応じてブロック復号化順序を変更するように制御することを特徴とする画像復号化方法。
【請求項１７】
請求項１６に記載の画像復号化方法において、
前記復号化制御に際しては、
同一の前記領域処理順位を割り当てられた異なる位置の各領域の各々の復号化処理を並列に実行するように制御することを特徴とする画像復号化方法。
【請求項１８】
請求項１７に記載の画像復号化方法において、
前記解析をする際に、
前記領域内での前記ブロック復号化順序をも前記入力ビットストリームから取得してこれを解析することを特徴とする画像復号化方法。
【請求項１９】
画像の符号化を制御する画像符号化処理プログラムであって、
コンピュータに、
入力される画像をブロックを含む各領域に分割して各領域の形状を設定するとともに、前記各領域に領域処理順位を設定する機能と、
前記領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化してビットストリームを生成するように符号化の制御を行い、かつ前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域では、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件を満たす符号化制御をする機能とを実行させることを特徴とする画像符号化処理プログラム。
【請求項２０】
符号化された画像を復号化する制御を行う画像復号化処理プログラムであって、
コンピュータに、
前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含むビットストリームから前記領域処理順位と前記領域の形状情報とを取得してその内容を解析する機能と、
前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する各ビットストリームを復号化して復号化画像を生成するように復号化における制御を行い、前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をするように制御する機能とを実行させることを特徴とする画像復号化処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像符号化装置、画像復号化装置、画像符号化方法、画像復号化方法、画像符号化処理プログラム、及び画像復号化処理プログラムに関し、特に画像を並列処理にて符号化するのに際し符号化効率や画質の低下を防止可能な画像符号化装置などに関する。
【背景技術】
【０００２】
動画像信号を低ビットレート、高圧縮率かつ高画質で符号化して符号化データを生成したり、符号化された動画像を復号化したりする技術として、ＩＴＵ（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｕｎｉｏｎ）が標準化したＨ．２６１、Ｈ．２６３や、ＩＳＯ（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ  ｆｏｒ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ）のＭＰＥＧ−１、ＭＰＥＧ−２、ＭＰＥＧ−４などが国際標準規格として広く用いられている。
さらに、近年、前記ＩＴＵとＩＳＯが共同で行った規格としてＨ．２６４がある（非特許文献１）。このＨ．２６４では、これまでの動画像符号化技術に比べ、さらなる圧縮効率向上及び画質向上を実現できることが知られている。【０００３】
これらの動画像符号化方式では、高い符号化効率を実現するために、符号化対象画素ブロックと画面内で近傍に位置するブロックとの間には絵柄の傾向や動きに相関があることを利用して情報圧縮を行うことが行なわれている。
ＭＰＥＧ−１／２等では、近傍の動きベクトル情報からのベクトル予測が用いられ、Ｈ．２６３、ＭＰＥＧ−４ではさらに動き補償残差画像のＤＣＴ係数の空間予測(ＡＣ／ＤＣ予測)が導入されている。
さらに、Ｈ．２６４では画素値レベルでの空間予測(イントラ予測)が採用されており、符号化効率の向上に寄与している。【０００４】
上で挙げたベクトル予測、ＡＣ／ＤＣ予測、イントラ予測のような空間的な符号化情報の予測を効率よく実現するため、画面内での画素ブロックの符号化順は規格で定められている。
基本的には画面の左上から符号化処理を開始して右方向に符号化処理が進行し、画面の右端に達すると1ブロック分下に移動して再び右方向に進む、ラスタースキャン順で処理するように規定されている。
また、符号化処理する画素ブロックの単位としてはマクロブロック（以下、ＭＢという）と呼ばれる１６×１６画素のサイズのブロックが用いられ、ＭＢ単位で上記のようにラスタースキャン順に符号化処理が行なわれる。【０００５】
関連技術の符号化方法の動作の一例を図１６に示す。これは１画面がＮ個×Ｍ個のＭＢで構成される動画像を符号化処理する場合の例である。図１６に示すように、画面内の各ＭＢはラスタースキャン順で符号化処理される。このような順番で符号化処理することにより、ある符号化対象ＭＢの左上、上、右上、左に隣接するＭＢは既に符号化処理済みであることになり、これらの隣接ＭＢの符号化情報を用いた空間予測が可能になる。【０００６】
Ｈ．２６４方式での動きベクトルの空間予測処理の一例を図１７に示す。あるＭＢを符号化する時点で、符号化対象ＭＢの左上、上、右上、左に隣接するＭＢは符号済みであり、それらのＭＢの動きベクトル４０１〜４０４は確定している。そこで、隣接ＭＢの動きベクトル４０２、４０３、４０４のメディアン値（中間値）を算出することによって符号化対象ＭＢの予測動きベクトル４０５を得る。【０００７】
符号化対象ＭＢの動きベクトル符号化では、符号化する動きベクトルと予測動きベクトル４０５との差分値を符号化する。通常の動画像においては動きベクトルに強い空間的相関がある場合が多いため、空間予測で算出した予測動きベクトルとの差分値を符号化することで符号化する情報量を削減することができる。
ただし、画面の最上部や最左部に位置するＭＢ（マクロブロック）については、左上、上、右上、左に隣接するＭＢのうち存在しないものがあり、予測動きベクトルの算出にはゼロベクトルなどの代替値を用いる。
このため、画面の最上部や最左部に位置するＭＢの予測動きベクトルは通常よりも空間予測の精度が低下し、情報量削減効果が低下する場合が多い。【０００８】
次に、Ｈ．２６４方式でのイントラ予測処理の一例を図１８に示す。
図１８は、ＭＢ予測モードがＩｎｔｒａ＿１６ｘ１６で、予測モードがＩｎｔｒａ＿１６ｘ１６＿Ｖｅｒｔｉｃａｌ（縦方向予測）モードである場合の輝度成分のイントラ予測の例を示している。
あるＭＢを符号化する時点で、符号化対象ＭＢの左上、上、右上、左に隣接するＭＢは符号済みであり、それらのＭＢの画素値は確定している。
そこで、縦方向予測の場合は上隣接ＭＢの下端列の画素値を、符号化対象ＭＢの横方向位置が同じ画素の予測画素値とする。
符号化対象ＭＢの動きベクトル符号化では、符号化する画素値と予測画素値との差分値を符号化する。通常の動画像においては近傍位置の画素値に強い空間的相関がある場合が多いため、イントラ予測で算出した予測画素値との差分値を符号化することで符号化する情報量を削減することができる。【０００９】
ただし、画面の最上部や最左部に位置するＭＢについては、左上、上、右上、左に隣接するＭＢのうち存在しないものがあり、予測画素値には１２８などの代替値を用いる。このため、画面の最上部や最左部に位置するＭＢの予測画素値は通常よりも空間予測の精度が低下し、情報量削減効果が低下する場合が多い。
このため、図１６の例ではＮ×Ｍ個のＭＢのうち、画面の最上部、最左部に位置するＭ＋（Ｎ−１）個のＭＢは空間予測効率が悪く、情報量削減効果が低下する場合が多い。【００１０】
ところで、大画面テレビの普及等により、より高精細な動画像の符号化の必要性が高まっている。ハイビジョン（１９２０×１０８０画素）や４Ｋ×２Ｋ（４０９６×２０４８画素）、８Ｋ×４Ｋ（８１９２×４０９６画素）などが代表的なフォーマットである。
このような高精細の動画像の符号化、復号化処理に要する演算量は非常に大きいため、複数のプロセッサを用いて並列処理したいという要望が強い。
動画像の符号化、復号化を並列処理するためには、画面を複数のスライスと呼ばれる部分領域に分割し、各スライスを独立に並列処理することが行なわれている。【００１１】
図１９に、スライス分割による関連技術の並列処理の動作の例を示す。これは画面を横に４つのスライスに分割して処理する場合の例である。
画面をスライスに分割する場合、各スライスはそれぞれ独立した符号化処理を行い、他のスライスの符号化結果などへの依存関係がないため、各スライスの符号化処理を完全に並列実行することができる。各スライス内の符号化処理は通常と同様にＭＢ単位でラスタースキャン順に進行する。【００１２】
しかし、この方式では、各スライスを独立に符号化処理するため、あるスライスの符号化時には隣接スライスに属するＭＢ（マクロブロック）の符号化情報を用いた空間予測は行えず、各スライスの最上部のＭＢは空間予測効率が低下するという課題があった。
図１６に示した４分割の例では、画面の最上部、最左部のＭＢに各スライスの最上部のＭＢを加えた合計Ｍ＋４×（Ｍ−１）個のＭＢで空間予測効率が低下し、この結果画像全体の符号化効率が劣化してしまう。【００１３】
また、スライス境界の上下では完全に独立した符号化が行なわれるため、この箇所でイントラ予測や動きベクトルの向きなどの性質が大きく変化し、不自然なノイズパターンが発生してしまう、という課題もあった。
この課題は、圧縮率が高い場合に特に顕著になり、画面内に横線が見えるなどの現象が発生して主観画質を大きく劣化させる。【００１４】
これに対し特許文献１や特許文献２では、スライス境界の近傍は他の領域に比べて量子化パラメータを小さめに制御する（特許文献１の段落番号００９１）などの方法によって、圧縮率を抑えて比較的高い画質で符号化し、不自然な符号化ノイズの発生を軽減する手法が開示されている。【００１５】
この内、特許文献１では、符号化装置のレート制御回路が、スライス境界に位置するマクロブロックについては、量子化パラメータＱＰに重み付け係数Ｑを乗じることで、より小さい量子化パラメータＱＰ１を割り当て、これにより、当該マクロブロックにより多くの符号量を割り当て、細かく量子化を行う。そのため、可逆符号化回路において、当該マクロブロックとそれに隣接するマクロブロックとが異なるスライスに属し、当該マクロブロックの符号化をそれに隣接するマクロブロックのデータの代替データを用いて行っても、当該マクロブロックの符号化による画質劣化を抑制できる。【００１６】
又、特許文献２では、フレームメモリが、各領域の画像データを夫々符号化回路に出力する。
符号化領域検出回路は、動き補償範囲が領域外に設定される端領域を検出し、端領域のタイミングの直前のタイミングに発生する領域フラグを出力する。
符号量制御回路は、領域フラグの発生時には符号化回路に設定する量子化幅を大きくする。また、符号量制御回路が、使用量又は加算使用量が大きい場合には大きい量子化幅を設定するための量子化幅データを出力し、使用量又は加算使用量が小さい場合には小さい量子化幅を設定するための量子化幅データを出力する。これにより、領域フラグの発生期間である加算期間には割り当て符号量が低減され、端領域に割り当て可能な符号量が増加する。こうして、端領域の画質が劣化することを防止して、境界部分が目立つことを防止する。
【特許文献１】特開２００４−２３５６８３号公報
【特許文献２】特開平９−２７５５６４号公報
【非特許文献１】ＩＴＵ−Ｔ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  Ｈ．２６４「Ａｄｖａｎｃｅd  ｖｉｄｅｏ  ｃｏｄｉｎｇ  ｆｏｒ  ｇｅｎｅｒｉｃ  ａｕｄｉｏｖｉｓｕａｌ  ｓｅｒｖｉｃｅｓ」、２００５年３月
【発明の開示】
【発明が解決しようとする課題】
【００１７】
ところで、上記特許文献１や特許文献２で開示されている技術によれば、上述したようにスライス分割による符号化、復号化並列処理で発生するスライス境界での不自然な符号化ノイズを、軽減するための手法が開示されている。【００１８】
しかしながら、これらの技術は、問題の符号化ノイズの発生原因を根本的に解消するものではなく、ノイズを軽減して主観画質の劣化を目立ちにくくする技術であるため、動画像の絵柄や動きの性質、圧縮率などの符号化条件によっては、主観画質劣化が発生する、という課題があった。【００１９】
また、スライス境界での空間予測効率（空間予測精度）低下を解決する技術ではないため、画像全体の符号化効率の劣化は抑えられない、という課題があった。【００２０】
本発明の目的は、上述の関連技術の課題を解決することにあり、画像を並列処理にて符号化するに際し符号化効率や画質の低下を有効に防止することが可能な画像符号化装置、画像復号化装置、画像符号化方法、画像復号化方法、画像符号化処理プログラム、及び画像復号化処理プログラムを提供することにある。
【課題を解決するための手段】
【００２１】
上記目的を達成するため、本発明の画像符号化装置は、入力される画像を符号化してビットストリームを生成する符号化手段と、前記画像内の符号化順序を制御するために前記符号化手段を制御する符号化制御手段と、を備え、前記符号化制御手段が、前記画像をブロックを含む各領域に分割して前記各領域の形状を設定するとともに前記各領域に領域処理順位を各々設定し、前記各領域処理順位に従って前記各領域を符号化する際に、前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たす符号化をするように制御することを特徴とする。【００２２】
本発明の画像復号化装置は、入力されるビットストリームを復号化して復号化画像を生成する復号化手段と、前記ビットストリームの復号化順序を制御するために前記復号化手段の動作を制御する復号化制御手段と、を備え、前記復号化制御手段が、前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含む前記ビットストリームを解析し、この領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する前記ビットストリームを復号化するように制御し、前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をするように制御することを特徴とする。【００２３】
本発明の画像符号化方法は、画像符号化装置を用いた画像符号化方法であって、入力される画像をブロックを含む各領域に分割して各領域の形状を設定し、前記各領域に領域処理順位を各々設定し、この領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化してビットストリームを生成する符号化制御をし、この符号化制御の際に、前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域では、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たす符号化をするように制御することを特徴とする。【００２４】
本発明の画像復号化方法は、画像復号化装置を用いた画像復号化方法であって、前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含むビットストリームを入力し、入力ビットストリームの前記領域処理順位と前記領域の形状情報とを取得してこれを解析し、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する各ビットストリームを復号化して復号化画像を生成するように復号化制御を行い、前記復号化制御に際しては、前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をするように制御することを特徴とする。【００２５】
本発明の画像符号化処理プログラムは、画像の符号化を制御する画像符号化処理プログラムであって、
コンピュータに、
入力される画像をブロックを含む各領域に分割して各領域の形状を設定するとともに、前記各領域に領域処理順位を設定する機能と、
前記領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化してビットストリームを生成するように符号化の制御を行い、かつ前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域では、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件を満たす符号化制御をする機能とを実行させることを特徴とする。【００２６】
本発明の画像復号化処理プログラムは、符号化された画像を復号化する制御を行う画像復号化処理プログラムであって、
コンピュータに、
前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含むビットストリームから前記領域処理順位と前記領域の形状情報とを取得してその内容を解析する機能と、
前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する各ビットストリームを復号化して復号化画像を生成するように復号化における制御を行い、前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をするように制御する機能とを実行させることを特徴とする。
【発明の効果】
【００２７】
本発明によれば、画像を並列処理にて符号化を行う際に、スライス境界での不自然な符号化ノイズの発生や符号化効率の低下を有効に且つ確実に排除することができ、これにより画像の符号化処理を効率よく、高精度に実現できる。
【発明を実施するための最良の形態】
【００２８】
〔画像符号化装置の基本的構成〕
先ず、画像符号化装置の基本的構成について説明する。図１に示すように、本発明の画像符号化装置１は、入力される画像を符号化してビットストリームを生成する処理を行う符号化手段としての符号化モジュール１０ｂと、前記入力される画像内の符号化順序を制御するために前記符号化手段を制御する符号化制御手段としての符号化制御モジュール１０ａとを備える構成としている。【００２９】
ここで、符号化制御モジュール１０ａは、前記画像をブロックを含む各領域に分割して前記各領域の形状を設定するとともに前記各領域に領域処理順位を各々設定し、前記各領域処理順位に従って前記各領域を符号化する際に、前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たす符号化をするように制御する機能を備える。【００３０】
符号化制御モジュール１０ａが例えば図１４に示すように、領域の形状（ＡＲ６１、ＡＲ６２―１〜ＡＲ６２―６）及び領域処理順位（レベル０、レベル１）を設定した場合、符号化モジュール１０ｂがレベル０の領域ＡＲ６１、レベル１の領域（ＡＲ６２―１〜ＡＲ６２―６）の順に符号化を行う。
この際、符号化制御モジュール１０ａは、同一の領域処理順位（レベル１）の例えば領域ＡＲ６２―１と領域ＡＲ６２―２と間では、符号化の際に互いに符号化情報を参照し利用するのを不可として、符号化をするように制御する。この場合、各領域では、空間予測をする際の符号化情報の依存関係がない。
符号化制御モジュール１０ａは、一の領域処理順位（レベル１）の例えば領域ＡＲ６２―１について、符号化の際に優先度の高い他の領域処理順位（レベル０）の領域ＡＲ６１の符号化情報を参照し利用して、符号化をするように制御する。この場合、各領域では、空間予測をする際の符号化情報の依存関係を有する。
符号化制御モジュール１０ａは上述した領域符号化における制御条件によって符号化制御を行うことにより、依存関係の有無を含めた領域を任意に設定して制御する。換言すれば、符号化制御モジュール１０ａは依存関係を有する領域境界、依存関係を有しない領域境界を設定して制御する。依存関係を有する領域境界に臨む各領域では、空間予測効率の低い部分がなくなるため、領域境界での符号化ノイズがなくなる。【００３１】
ここで、領域は、前記「ブロック」を含むものであればよい。この「ブロック」の単位は、マクロブロックであっても、画素ブロックであってもよい。また、「ブロック」が画素ブロック群となる場合でもよく、この画素ブロック群は、いわゆるマクロブロックと同等のものであっても、そうでないものであってもよい。
例えば、領域は、図１５に示すように、１個のマクロブロック（＝画素ブロック群）として設定することもできる。
さらに、この領域は、いわゆるマクロブロックとは異なる概念で任意に設定できる。【００３２】
このため、このような符号化制御手法を、並列処理用に画像を分割して各々符号化を行う場合などに応用することで、関連技術の並列処理における符号化ノイズの課題も解消される。
具体的には、符号化制御モジュール１０ａは、少なくとも並列処理用画像分割境界を含む第１領域（例えば図６に示す領域ＡＲ１１）とその他の第２領域（例えば図６に示す領域ＡＲ２１及びＡＲ２２）とに前記画像を分割し、前記各領域に割り当てられる領域処理順位（例えばレベル０、レベル１）に従って少なくとも前記第１領域を前記第２領域より先に符号化するように制御するとともに、前記第２領域を符号化する際に前記第１領域の符号化情報を利用するように制御する機能を備えている。【００３３】
このような画像符号化装置では、画像を並列処理にて符号化を行う際に、スライス境界での不自然な符号化ノイズの発生や符号化効率の低下と言った副作用を削減しつつ画像の符号化処理を効率よく、高精度に実現できる。
その理由は、関連技術のスライス分割では、スライス境界で符号化情報の空間的予測が不連続になっていたために上記課題を避けられなかった。
これに対し本画像符号化装置では、少なくとも並列処理用画像分割境界を含む第１領域をまず先に符号化する。そして、第２領域は、第１領域からの空間予測における符号化情報を用いて符号化するため、イントラ予測や動きベクトルの性質には空間的な連続性がある。これにより、関連技術のスライス分割の課題である、スライス境界での不連続性に起因する符号化ノイズは発生しない。【００３４】
以下、このような本発明の「画像符号化装置」のさらに具体的構成の一例について、図面を参照して説明する。【００３５】
〔第１の実施の形態〕
（画像符号化装置の全体構成）
先ず、本実施の形態の画像符号化装置の具体的構成について、全体構成から説明し、続いて各部の詳細構成について説明することとする。図１は、本発明における第１実施の形態の画像符号化装置の全体の概略構成の一例を示すブロック図である。【００３６】
図１に示すように、本実施の形態の画像符号化装置１は、１フレームの画像が入力可能な入力ユニット１１と、入力ユニット１１から入力された画像を格納する入力画像メモリ１２と、上述した符号化制御モジュール１０ａ及び符号化モジュール１０ｂとを有している。前記符号化制御モジュール１０ａは、一画面分の画像を部分領域に分割するとともに符号化処理順位（領域処理順位）をレベル値（Ｌｅｖｅｌ）として割り当てる制御を行う分割レベル割り当てユニット１３（設定制御手段）と、レベル値に基づいて各領域の符号化処理順を制御する符号化順制御ユニット１４（第１の符号化順序制御手段）とを含んでいる。【００３７】
さらに、画像符号化装置１の符号化モジュール１０ｂは、各領域に各領域の各分割画像を画素ブロック単位で符号化可能な１又は複数の符号化ユニット１５を有しており、前記符号化制御モジュール１０ａは、各領域の画素ブロック符号化順序を（例えばラスタースキャン順序などで）制御する走査ユニット１６（第２の符号化順序制御手段）を有している。また、画像符号化装置１は、前記符号化ユニット１５にて符号化されたマクロブロック単位の画像であって符号化の際に参照される（符号化済みの）符号化画像を格納する符号化画像メモリ１７と、符号化ユニット１５にて符号化されたビットストリームを出力する出力ユニット１８とを有している。【００３８】
分割レベル割り当てユニット１３は、入力画像メモリ１２から供給される入力画像を複数の部分領域に分割するとともに、領域間の空間予測依存性に基づいて各領域の符号化処理順位をレベル値として割り当てる。前記レベル値は０が最も高く、最初に符号化処理を行うことを意味する。分割レベル割り当てユニット１３は、例えばレベル値が１（レベル  １）の領域に属するＭＢ（マクロブロック）について、レベル値が０（レベル  ０）の領域に属するＭＢの符号化情報を空間予測に利用してもよいようにレベル値を割り当てる。このため、レベル１の領域は、レベル０の領域の符号化処理が全て完了した後でないと符号化処理を開始できない。【００３９】
更にいえば、分割レベル割り当てユニット１３は、レベル値を０、１、・・・、Ｎ−１、Ｎ（Ｎは自然数）とした場合に、レベル値がＮ（レベル  Ｎ）の領域に属するＭＢ（マクロブロック）について、レベル値がＮ−１（レベル  Ｎ−１）以下の領域に属するＭＢの符号化情報を空間予測に利用してもよいようにレベル値を割り当てる。このため、レベル  Ｎの領域は、レベル  Ｎ−１以下の領域の符号化処理が全て完了した後でないと符号化処理を開始できない。【００４０】
また、分割レベル割り当てユニット１３は、同じレベルを持つ異なる領域間では依存性が無いように、レベル値を割り当てる。このため、レベルが等しい異なる領域は独立に符号化処理が可能である。
ここで、「依存性を有する」とは、一の領域を符号化する際に、他の領域を参照し該他の領域の情報（符号化情報）を利用することをいう。また、「依存性がない」とは、一の領域を符号化する際に、他の領域を参照せず該他の領域の情報（符号化情報）を利用しないことをいう。【００４１】
より詳細には、一のＭＢ（マクロブロック）を符号化する際に、他のＭＢ（マクロブロック）を参照し該他のＭＢ（マクロブロック）の情報（符号化情報）を利用する場合、一のＭＢ（マクロブロック）と他のＭＢ（マクロブロック）との関係は、空間予測する際の依存性を有する関係にある、ということができる。一方、一のＭＢ（マクロブロック）を符号化する際に、他のＭＢ（マクロブロック）を参照せず該他のＭＢ（マクロブロック）の情報（符号化情報）を利用しない場合、一のＭＢ（マクロブロック）と他のＭＢ（マクロブロック）との関係は、空間予測する際の依存性の無い関係にある、ということができる。【００４２】
また、一のＭＢ（マクロブロック）を符号化する際に他のＭＢ（マクロブロック）を参照し該他のＭＢ（マクロブロック）の情報（符号化情報）を利用する場合であって、特に符号化対象ＭＢ（マクロブロック）に対する他の参照可能ＭＢ（マクロブロック）の数が通常より少ない場合は、空間予測依存性が低い（空間予測効率が悪い、空間予測精度が低い）ということができる。
さらに、符号化対象ＭＢ（マクロブロック）に対する他の参照可能ＭＢ（マクロブロック）の数が前述の少ない場合より多い場合は、空間予測依存性が高い（空間予測効率が高い、空間予測精度が高い）ということができる。【００４３】
また、分割レベル割り当てユニット１３は、少なくとも並列処理用画像分割境界領域を含むブロックラインの第１領域（例えば図３に示す符号ＡＲ１）とその他の第２領域（例えば図３に示す符号ＡＲ２（ＡＲ２―１〜ＡＲ２―４））とに前記画像を分割して前記各領域の形状を設定する領域形状設定機能１３ａと、少なくとも前記第１領域を前記第２領域よりも先に符号化するように前記各領域に対して領域処理順位としてのレベル値をそれぞれ設定する領域処理順位設定機能１３ｂとを備えることができる。【００４４】
符号化順制御ユニット１４は、前記分割レベル割り当てユニット１３が割り当てた領域毎の符号化処理順番に基づき、各領域の符号化処理実行順序を制御する。すなわち、符号化順制御ユニット１４は、前記各領域処理順位に従って前記各領域を符号化し前記第２領域について前記第１領域の符号化情報を利用して符号化するように制御する。【００４５】
符号化ユニット１５は、分割レベル割り当てユニット１３から供給される入力画像と、符号化画像メモリ１７から供給される過去に符号化済みの画像を用いて１つのＭＢ（マクロブロック）の符号化処理を行ない、生成したビットストリームを出力ユニット１８に供給するとともに、符号化結果の画像を符号化画像メモリ１７に供給する。【００４６】
さらに、符号化ユニット１５は、１ＭＢに対する動きベクトル探索、イントラ予測モード決定、ＭＢ符号化モード決定、動き補償またはイントラ予測、予測残差信号の整数変換、量子化、逆量子化、逆整数変換、エントロピー符号化、局所復号画像の生成とデブロッキングフィルタ処理といった一連の符号化処理を実行する。すなわち、符号化ユニット１５は、近傍の動きベクトル情報からのベクトル予測、動き補償残差画像のＤＣＴ係数の空間予測(ＡＣ／ＤＣ予測)、画素値レベルでの空間予測(イントラ予測)などの空間的な符号化情報の予測を行う。【００４７】
ここで、本実施の形態の分割レベル割り当てユニット１３と符号化順制御ユニット１４と走査ユニット１６とにより符号化制御モジュール１０ａを構成する。また、一又は複数の符号化ユニット１５により符号化モジュール１０ｂを構成する。この符号化制御モジュール１０ａは、「符号化制御手段」の一例又は一部ということもできる。また、符号化モジュール１０ｂは、「符号化手段」の一例又は一部ということもできる。【００４８】
この場合、符号化モジュール１０ｂは、入力される画像を符号化してビットストリームを生成する処理を行う。符号化制御モジュール１０ａは、前記入力される画像内の符号化順序を制御するために前記符号化手段を制御する。【００４９】
又、符号化制御モジュール１０ａは、前記画像をブロックを含む各領域に分割して前記各領域の形状を設定するとともに前記各領域に領域処理順位を各々設定し、前記各領域処理順位に従って前記各領域を符号化する際に、前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たす符号化をするように制御する機能を備えている。【００５０】
更に、符号化制御モジュール１０ａは、前記領域の形状情報と前記領域処理順位と前記ブロック符号化順序とに関する情報をも符号化してビットストリーム中に出力するように制御する機能を備えている。又、符号化制御モジュール１０ａは、前記同一の領域処理順位が割り当てられた前記各領域を並列に符号化するように制御する機能を備えている。【００５１】
更に、並列処理に応用する場合、符号化制御モジュール１０ａは、少なくとも並列処理用画像分割境界を含む第１領域とその他の第２領域とに前記画像を分割し、前記各領域に割り当てられる領域処理順位に従って少なくとも前記第１領域を前記第２領域より先に符号化するように制御するとともに、前記第２領域を符号化する際に前記第１領域の符号化情報を利用するように制御する機能を備えてよい。【００５２】
又更に、符号化制御モジュール１０ａは、前記第２領域（例えば図３のＡＲ２）の内、前記第１領域によって分割される２以上の各サブ領域（例えば図３のＡＲ２―１、ＡＲ２―２、ＡＲ２―３、ＡＲ２―４）に同一の前記領域処理順位を割り当てるとともに前記各サブ領域を並列に符号化するように制御する機能を備えている。【００５３】
更に、符号化制御モジュール１０ａは、前記第１領域の符号化に際しては、前記画像の周縁部のうち符号化スキャンの開始に関わる少なくとも２辺の前記周縁部を符号化するように制御するとともに、前記第２領域内をブロック単位で符号化するに際しては、前記各サブ領域を同一の前記ブロック符号化順序で符号化するように制御する機能を備えている。【００５４】
更に、符号化制御モジュール１０ａは、画像をブロック間における空間予測依存性に応じて前記ブロック群からなる２以上の（並列処理用スライス分割とは異なる）各領域に分割して前記各領域の形状を設定するとともに前記各領域での空間予測依存性に応じて前記各領域に領域処理順位を設定する処理をし、この領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化するように制御し、一領域処理順位の一領域では該一領域処理順位より優先度の低い他領域処理順位の他領域を空間予測の際に参照せずに前記他領域より先に符号化するように制御する機能を備えている。【００５５】
また、符号化制御モジュール１０ａは、同一の前記領域処理順位を割り当てられた異なる各領域の各々の符号化処理を並列に実行するように制御する機能を備えている。さらに、符号化制御モジュール１０ａは、前記領域の形状情報と前記領域処理順位と前記ブロック符号化順序とに関する情報をも符号化しビットストリーム中に出力するように制御する機能を備えている。【００５６】
（動作処理手順について）
（全体の概略動作）
次に、上述のような構成を有する画像符号化装置における全体の動作処理手順について、図２乃至図４を参照しつつ説明する。図２は、図１の画像符号化装置における処理手順の一例を示すフローチャートである。【００５７】
本実施の形態に係る画像符号化における全体の動作処理手順は、基本的手順として、符号化制御モジュ−ル１０ａに入力画像メモリ１２から画像が入力すると、前記符号化制御モジュール１０ａが、入力される画像をブロックを含む各領域に分割して各領域の形状を設定し（図２に示すステップＳ１０２）、前記各領域に領域処理順位を各々設定し（図２に示すステップＳ１０２）、この領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化してビットストリームを生成する符号化制御を行う（図２に示すステップＳ１０３〜ステップＳ１０９からなるステップ）。【００５８】
この符号化制御の際に、前記符号化制御モジュール１０ａは、前記領域の制御条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域では、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たす符号化をするように制御する。【００５９】
また、並列処理に応用する場合、前記符号化制御モジュール１０ａは、一例として、領域の形状を、入力される画像を少なくとも並列処理用画像分割境界を含む第１領域とその他の第２領域とに分割して設定してもよい。また、前記符号化制御モジュール１０ａは、領域処理順位を、少なくとも前記第１領域を前記第２領域より先に符号化するように前記各領域に設定してよい。
この場合、符号化制御では、前記第２領域の符号化では前記第１領域の符号化情報を利用するように制御することができる。
また、前記符号化制御に際しては、前記第２領域が前記第１領域によって分割された各サブ領域では、同一の前記領域処理順位を割り当てられた異なる位置の前記各サブ領域の各々の符号化処理を並列に実行するように制御することができる。また、前記符号化における制御をする際に、前記領域の形状情報と前記領域処理順位と前記ブロック符号化順序とに関する情報をも符号化し、これらをビットストリーム中に出力するように制御することができる。【００６０】
さらに、この符号化における制御では、前記符号化制御モジュール１０ａは、一領域処理順位の一領域では該一領域処理順位より優先度の低い他領域処理順位の他領域を空間予測の際に参照せずに前記他領域より先に符号化するように制御する。また、この符号化における制御では、前記符号化制御モジュール１０ａは、他領域での空間予測の際に、先に符号化された一領域の符号化情報を参照し利用するように制御する。さらに、この符号化における制御では、前記符号化制御モジュール１０ａは、同一の前記領域処理順位を割り当てられた異なる各領域の各々の符号化処理を並列に実行するように制御する。【００６１】
（詳細動作）
以下、これを詳述する。
先ず、図２に示すように、１フレームの符号化処理が開始すると、入力ユニット１１は、１フレームの画像を入力し、入力画像メモリ１２に格納する（ステップＳ１０１）。【００６２】
続いて、符号化制御モジュール１０ａの分割レベル割り当てユニット１３は、入力画像メモリ１２から供給される一画面分の入力画像を２以上の各領域に分割する処理を行う（領域形状設定処理）。さらに、分割レベル割り当てユニット１３は、上記の規則に基づいて前記分割した各分割領域にレベル値を割り当てる処理（領域処理順位設定処理）を行う（ステップＳ１０２：設定制御ステップないしは設定制御機能）。【００６３】
具体的には分割レベル割り当てユニット１３は図３に示すように、レベル０領域ＡＲ１と、レベル１領域ＡＲ２（ＡＲ２―１〜ＡＲ２―４）とに画像を分割する。図３の例では、レベル０領域ＡＲ１は、画像の周縁部のうちブロックスキャンを開始する側のニ辺と、並列処理用画像分割境界を含む領域とを有する。
レベル１領域ＡＲ２は、レベル０領域ＡＲ１のその他の領域であって、レベル０領域ＡＲ１によって分割される複数のサブ領域ＡＲ２―１、ＡＲ２―２、ＡＲ２―３、ＡＲ２―４を含む。
分割レベル割り当てユニット１３は、レベル０領域ＡＲ１にレベル値として「０」を割り当て、レベル１領域ＡＲ２（ＡＲ２―１〜ＡＲ２―４）にレベル値として「１」を割り当てる。
このように、図３の例は、分割レベル割り当てユニット１３が、画面左端と画面を４分割する４本のＭＢ（マクロブロック）行で構成されるレベル（Ｌｅｖｅｌ）０領域ＡＲ１と、レベル０領域ＡＲ１によって区切られる４つのレベル１領域ＡＲ２（ＡＲ２―１、ＡＲ２―２、ＡＲ２―３、ＡＲ２―４）に画面を分割し、前記分割したそれぞれの領域にレベル割り当てをする場合を示している。【００６４】
次に、符号化制御モジュール１０ａの符号化順制御ユニット１４が各分割領域のレベル値に基づいて、各領域毎の符号化順を制御する。具体的に説明すると、符号化順制御ユニット１４が、処理対象レベル値であるＬに０を設定する処理を行う（図２のステップＳ１０３）。すなわち、符号化順制御ユニット１４は、前記分割された領域を符号化する順序として、処理対象レベル値Ｌが０である領域を最初に符号化するための制御を行う。ここにおける「Ｌ」は変数であり、符号化順制御ユニット１４は、図３の例によれば、Ｌ＝０を設定することにより最初に符号化する領域を処理対象レベル値Ｌが０である領域に設定し、前記処理対象レベル値Ｌが０である領域の符号化が実行された際に、次に処理対象レベル値Ｌが１である領域を符号化処理の対象となるように各領域の符号化順を制御する。また、本実施形態では、Ｌ＝０、Ｌ＝１の各領域を処理する場合について例示しているが、符号化順制御ユニット１４による領域の符号化順の制御は、図３に示す様な処理対象レベル値Ｌが０或いは１の２種類の領域の符号化順を制御する場合に限られるものではなく、処理レベル値が３種類以上の領域を符号化する順序を制御する場合であってもよいものである。【００６５】
続いて、符号化順制御ユニット１４は、レベル値がＬ＝０である未処理領域が存在するかどうかを判定する（図２のステップＳ１０４）。このステップＳ１０４において、前記レベル値Ｌ＝０の未処理領域が存在すると符号化順制御ユニット１４が判定した場合に、符号化順制御ユニット１４による前記判定結果に基づいて前記未処理領域について走査ユニット１６及び符号化ユニット１５による図２に示すステップＳ１０５〜Ｓ１０７の処理が実行される。【００６６】
具体的には、符号化順制御ユニット１４は、最初に符号化処理を行うべき領域であるレベル値がＬ＝０の未処理領域、図３の例ではレベル値０の領域ＡＲ１（未処理領域）が存在するか否かの判定処理を行う（第１レベル領域有無判定処理ステップないしは第１レベル領域有無判定処理機能）。この判定処理において、レベル値０の領域ＡＲ１は未だ符号化処理されていないため、符号化順制御ユニット１４は、レベル値Ｌが０である領域ＡＲ１（未処理領域）が存在していると判定し、その判定結果を走査ユニット１６及び符号化ユニット１５に出力する。走査ユニット１６及び符号化ユニット１５は、符号化順制御ユニット１４からの前記判定結果を受け取ると、図２のステップＳ１０５〜ステップＳ１０７の処理を実行する。【００６７】
次に、走査ユニット１６及び符号化ユニット１５によってＬ＝０となるレベル値Ｌ＝０の領域ＡＲ１の符号化が処理された場合、符号化順制御ユニット１４は、前記第１レベル領域有無判定処理ステップにおいてレベル値Ｌ＝０の領域ＡＲ１の符号化処理がなされて未処理領域が存在しないと判定し、た場合、後述するステップＳ１０８に処理を進める。【００６８】
さらに、符号化順制御ユニット１４は、最初に符号化すべきレベル値Ｌ＝０の領域ＡＲ１の符号化処理がなされた後に、符号化順を示すＬの値を「１」増やしてＬ＝Ｌ＋１に設定する（図２のステップＳ１０９）。図３の例では、分割した領域に割り当てるレベル値が「０」又は「１」であるから、前記ステップＳ１０９におけるＬは「１」となる。したがって、符号化制御ユニット１４は、Ｌ＝１となるレベル値Ｌ＝１の領域ＡＲ２が未処理領域であるか否かの判定処理を行う（図２のステップＳ１０４；第２レベル領域有無判定処理ステップないしは第２レベル領域有無判定処理機能）。この判定処理において、レベル１の領域ＡＲ２（ＡＲ２―１〜ＡＲ２―４）は、未だ符号化処理されていないため、符号化順制御ユニット１４は、レベル値Ｌが１である領域ＡＲ２（未処理領域）が存在していると判定し、その判定結果を走査ユニット１６及び符号化ユニット１５に出力する。走査ユニット１６及び符号化ユニット１５は、符号化順制御ユニット１４からの前記判定結果を受け取ると、図２のステップＳ１０５〜ステップＳ１０７の処理を実行する。【００６９】
ここで、ステップＳ１０５〜Ｓ１０７の処理過程において、走査ユニット１６及び符号化ユニット１５は、各領域内のＭＢの符号化処理を順次行う。具体的には、走査ユニット１６は、処理対象の領域内に未処理ＭＢが存在するかを判定する処理を行う（ステップＳ１０５）。
走査ユニット１６が、処理対象の領域内に未処理ＭＢが存在しないと判定した場合には、その領域の処理を完了してステップＳ１０５に戻る。
一方、ステップＳ１０５において走査ユニット１６が、処理対象の領域内に未処理ＭＢが存在すると判定した場合には、走査ユニット１６がラスタースキャン順に従って処理対象ＭＢを決定し、符号化ユニット１５に通知する（ステップＳ１０６）。【００７０】
次に、符号化ユニット１５は、符号化ユニット１５からの通知を受け取ると、分割レベル割り当てユニット１３から供給される入力画像と、符号化画像メモリ１７から供給される過去に符号化済みの画像を用いて１ＭＢの符号化処理を行い、前記符号化処理を行った領域の形状情報とレベル値とをビットストリームとして出力ユニット１８に供給するとともに、符号化結果の画像を符号化画像メモリ１７に供給して画像メモリ１７に記憶させる（ステップＳ１０７：符号化ステップないしは符号化機能）。
このようにして一領域内についての画素ブロック（ＭＢ：マクロブロック）単位での符号化が順次実行される。【００７１】
すなわち、これらのステップＳ１０５〜Ｓ１０７において最初のループでは、Ｌ＝０となるレベル０の領域（図３に示すＡＲ１）内について未処理ＭＢが存在するか否かの判定処理を行い（第１レベル領域ＭＢ有無判定処理ステップないしは第１レベル領域ＭＢ有無判定処理機能）、Ｌ＝０となるレベル０の領域内についての各ＭＢについて順次符号化処理を行ってゆく。【００７２】
また、これらのステップＳ１０５〜Ｓ１０７において２回目のループでは、Ｌ＝１となるレベル１の領域（図３に示すＡＲ２（ＡＲ２―１〜ＡＲ２―４））内について未処理ＭＢが存在するか否かの判定処理を行い（第２レベル領域ＭＢ有無判定処理ステップないしは第２レベル領域ＭＢ有無判定処理機能）、Ｌ＝１となるレベル１の領域内についての各ＭＢについて順次符号化処理を行ってゆく。【００７３】
ここで、ステップＳ１０５〜Ｓ１０７では、並列処理が可能となっているため、Ｌ＝１となるレベル１の領域（図３に示すＡＲ２（ＡＲ２―１〜ＡＲ２―４））のうち複数のサブ領域ＡＲ２―１、ＡＲ２―２、ＡＲ２―３、ＡＲ２―４内のＭＢ符号化処理を並列して行うことができる。【００７４】
一方、上述のステップＳ１０４において、符号化順制御ユニット１４が、レベル値がＬである未処理領域が存在しないと判定した場合は、ステップＳ１０８に進む。
ステップＳ１０８では、符号化順制御ユニット１４が、レベル値がＬである未処理の領域が存在するかを判定し、存在する場合にはステップＳ１０９でＬの値を１増やしてステップＳ１０４に戻る。
一方、ステップＳ１０８にて符号化順制御ユニット１４が未処理の領域が存在しないと判定した場合は、１フレームの符号化処理は完了する。【００７５】
すなわち、ステップＳ１０８において最初のループでは、Ｌ＝０となるレベル０の領域（図３に示すＡＲ１）の他に領域ＡＲ２（ＡＲ２―１〜ＡＲ２―４）が未処理であるから、Ｌ＝Ｌ＋１によってＬ＝１となり、Ｌ＝１の設定でステップＳ１０４からの処理を繰り返す。【００７６】
また、ステップＳ１０８において２回目のループでは、Ｌ＝１となるレベル１の領域（図３に示すＡＲ２（ＡＲ２―１〜ＡＲ２―４）の他に未処理領域が存在しないため、処理を終了する。【００７７】
ここで、分割レベル割り当てユニット１３は、分割領域の形状や各領域のレベル値の情報を符号化ユニット１５に供給し、ビットストリーム中に符号化して出力する制御を行う。【００７８】
また、図１の構成では、１または複数の符号化ユニット１５を備える。複数の符号化ユニット１５を備える場合、異なる領域に対する図２のフローチャートのステップＳ１０５〜ステップＳ１０７の処理は異なる符号化ユニット１５を用いて並列に処理することが可能である。【００７９】
ここで、以上のステップＳ１０５〜ステップＳ１０６からなるステップは、第２の符号化順序制御処理ステップの一例ということもできる。また、以上のステップＳ１０３、Ｓ１０４、Ｓ１０８、Ｓ１０９からなるステップは、第１の符号化順序制御処理ステップの一例ということもできる。【００８０】
このように、図４の例では、最初にレベル  ０領域の符号化処理を実行し、これが完了すると４つのレベル  １領域の符号化処理を、最大で４並列で処理することができる。
図１０に示す関連技術の並列処理の例とは異なり、レベル  ０の領域に属する画面左端のＭＢ列は分割されていないため、縦方向の空間予測を利用することができ、関連技術よりも符号化効率の低下を抑えることができる。【００８１】
以上のように本実施の形態によれば、符号化効率の低下を軽減しながら符号化処理を効率良く並列実行できる。【００８２】
すなわち、前述した関連技術でのスライス分割による並列処理では、符号化効率の低下やスライス境界での不自然な符号化ノイズの発生等の不都合があったが、本第１実施形態では、かかる不都合をレベル０の領域を設けることによってこれらを確実に排除し得るので動画像データの符号化および復号化処理を効率よく並列処理できる。
即ち、関連技術のスライス分割では、スライス境界で符号化情報の空間的予測が不連続になっていたために上記の問題を避けられなかったが、本実施の形態では、画面を複数の領域に分割し、領域間の空間予測依存性に応じて符号化および復号化順序を示すレベル（Ｌｅｖｅｌ）を割り当て、同一または下位レベルの領域の符号化情報には依存しないように符号化し、先に符号化された上位レベルの領域の符号化情報を複数の下位レベルの領域から空間予測に利用することで、イントラ予測や動きベクトルの性質には空間的な連続性を保ちつつ、同一レベルの領域は独立に並列処理することが可能としためである。【００８３】
ここで、図１に示すブロック図における一部の各ブロックは、記録媒体に記録されたプログラムをコンピュータに実行することにより、ソフトウェア上で実現するようにしてもよいものである。【００８４】
すなわち、物理的構成は例えば一又は複数のＣＰＵ（或いは一又は複数のＣＰＵと一又は複数のメモリ）等ではあるが、各部（回路・手段）によるソフトウェア構成は、プログラムの制御によってＣＰＵが発揮する複数の機能を、それぞれ複数の部（手段）による構成要素として表現したものである。【００８５】
ＣＰＵがプログラムによって実行されている動的状態（プログラムを構成する各手順を実行している状態）を機能表現した場合、ＣＰＵ内に各部（手段）が構成されることになる。プログラムが実行されていない静的状態にあっては、各手段の構成を実現するプログラム全体（或いは各手段の構成に含まれるプログラム各部）は、メモリなどの記憶領域に記憶されている。【００８６】
以上に示した各ユニット、モジュール（手段）は、プログラムにより機能化されたコンピュータをプログラムの機能と共に実現し得るように構成しても、また、固有のハードウェアにより恒久的に機能化された複数の電子回路ブロックからなる装置で構成してもよい。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せによっていろいろな形で実現でき、いずれかに限定されるものではない。【００８７】
［第２の実施の形態］
次に、本発明にかかる第２の実施の形態について、図５に基づいて説明する。以下には、前記第１の実施の形態の実質的に同様の構成に関しては説明を省略し、異なる部分についてのみ述べる。図５は、本発明の第２の実施形態に係る画像符号化装置の全体構成の一例を示すブロック図である。【００８８】
本第２の実施の形態では、符号化ユニット毎に対応する走査ユニットを備え、符号化処理を行う領域毎に異なる走査を行うことが可能な点が第１の実施の形態と異なる。【００８９】
具体的には、画像符号化装置１００では、図５に示す入力ユニット１１、入力画像メモリ１２、分割レベル割り当てユニット１１３、符号化順制御ユニット１１３、符号化ユニット１５、符号化画像メモリ１７、出力ユニット１８を備え、これらは、図１に示す第１の実施形態の構成と同一である。
本第２の実施形態の画像符号化装置１００は、各符号化ユニット１５に対応して各々走査ユニット１１６を備える。【００９０】
走査ユニット１１６は、分割レベル割り当てユニット１３から供給される画像とその分割状況及びレベル割り当て状況の情報に基づき、符号化対象の領域毎に適したＭＢの走査順で走査を行う。【００９１】
走査ユニット１１６が走査する走査順は、符号化対象領域のレベル値より小さいレベル値の領域に属するＭＢの符号化情報を利用した空間予測を活用できるよう、符号化対象領域のレベル値より小さいレベル値の領域に属するＭＢに隣接したＭＢから符号化処理を開始するように設定する。
例えば、左右方向に関しては符号化対象領域の左側には隣接せず右側には隣接していた場合は右から左への走査、それ以外の場合には左から右への走査とし、上下方向に関しては符号化対象領域の上側には隣接せず下側には隣接していた場合は下から上への走査、それ以外の場合には上から下への走査とする。【００９２】
ここで、本実施の形態の分割レベル割り当てユニット１１３と符号化順制御ユニット１１４と複数の走査ユニット１１６とにより符号化制御モジュール１１０ａを構成する。この符号化制御モジュール１１０ａは、「符号化制御手段」の一例ということもできる。【００９３】
この場合、符号化制御モジュール１１０ａは、前記領域内をブロック単位で符号化する際に、前記各領域に応じて画素ブロック符号化順序（ブロック符号化順序）を変更するように制御する機能を備えている。また、符号化制御モジュール１１０ａは、画素ブロック符号化順序（ブロック符号化順序）を前記領域の形状情報と前記領域処理順位とに応じて決定するように制御する機能を備える。
又更に、符号化制御モジュール１１０ａは、一の前記領域の前記ブロック符号化順序を他の前記領域に隣接するブロック部分から符号化を開始し、前記他の領域における前記一の領域隣接部分の符号化情報を利用するように制御する機能を備える。すなわち、符号化制御モジュール１１０ａは、一の前記領域内でのブロック符号化順序を前記一の領域に隣接し先に符号化される他の前記領域内の符号化情報を利用した空間予測処理をするように決定する機能を備える。【００９４】
また、並列処理に応用する場合、符号化制御モジュール１１０ａは、前記第２領域内をブロック単位で符号化する際に前記各サブ領域に応じてブロック符号化順序を変更するように制御する機能を備える。
又、符号化制御モジュール１１０ａは、前記第２領域の前記ブロック符号化順序を前記第１領域に隣接するブロック部分から符号化を開始するように制御する機能を備える。  【００９５】
本第２の実施形態の処理の流れは図２の第１の実施の形態のフローチャートと同じであるが、ステップＳ１０６で処理対象ＭＢを決定する際に、各符号化ユニット１５に対応する各々の走査ユニット１１６で、上記の各符号化領域に適した走査順に基づいて決定する点が第１の実施の形態とは異なる。【００９６】
（動作例１）
図６及び図７を参照して本第２の実施の形態の動作例を説明する。
図６では、分割レベル割り当てユニット１３が、画面中央のＭＢ行をレベル０領域ＡＲ１１に、その上下の領域をそれぞれレベル１領域ＡＲ２１、ＡＲ２２に割り当てる場合の例である。
この例では、符号化制御モジュール１１０ａが符号化ユニット１１０ｂを制御することによって、最初にレベル０領域ＡＲ１１の符号化処理を実行し、これが完了すると、２つのレベル１領域ＡＲ２１、ＡＲ２２の符号化処理を並列で処理することができる。
この際、下側のレベル１領域ＡＲ２２では、領域の上側にレベル０領域ＡＲ１１が隣接しているため、通常のラスタースキャン順で走査することでレベル０領域ＡＲ１１からの空間予測を利用した符号化処理が出来る。【００９７】
一方、上側のレベル１領域ＡＲ２１では、領域の下側にレベル０領域ＡＲ１１が隣接しているため、通常のラスタースキャン順走査ではレベル０領域ＡＲ１１からの空間予測を利用できない。【００９８】
そこで、この上側のレベル１領域ＡＲ２１では、図７に示すように、レベル１領域ＡＲ２１の左下から符号化処理を開始して右方向に符号化処理が進行し、画面の右端に達すると1ブロック分上に移動して再び右方向に進む走査（逆ラスタースキャン順走査）を符号化制御モジュール１１０ａの対応する走査ユニット１１６が行う。
この際、下側のＭＢ（マクロブロック）から符号化処理が進行するため、符号化情報の空間的な予測は左下、下、右下、左に隣接するＭＢの情報を用いて行う。【００９９】
図８に動きベクトルの予測の場合の例を示す。図１７に示す関連技術の動きベクトル予測では上、右上、左に隣接するＭＢの動きベクトル４０２、４０３、４０４のメディアン値を用いていた。
これに対して本実施の形態では、下側から予測する場合は図８に示すように下、右下、左に隣接するＭＢの動きベクトル３０２、３０３、３０４のメディアン値を用いる。
イントラ予測やＡＣ／ＤＣ予測など、他の空間予測も同様に下側のＭＢから予測を行うことができる。【０１００】
このように処理対象領域毎に適した走査順で符号化処理を行う。これにより、図６の例では、空間予測効率が悪いＭＢ（マクロブロック）の数は、図７に示すように、画面の左端部のＭＢのＭ個と、レベル０領域に属するＭＢの（Ｎ―１）個とを合わせて合計Ｍ＋（Ｎ−１）個となる。
これは図１３の関連技術の画面分割を行わない場合の例と同じ個数である。このため、図７の例では画面分割を行わない場合と同程度の符号化効率を維持しながら、２つのレベル１領域の符号化処理の並列実行によって効率よい並列化を実現できる。
また、２つのレベル１領域は、それぞれレベル０領域からの空間予測を用いて符号化するため、イントラ予測や動きベクトルの性質には空間的な連続性がある。これにより、関連技術のスライス分割の課題である、スライス境界での不連続性に起因する符号化ノイズは発生しない。【０１０１】
（動作例２）
次に、図９及び図１０を参照して本発明の第２の実施の形態の別の動作例を説明する。
図９では、分割レベル割り当てユニット１３が、画面中央の略十字状の領域をレベル０領域ＡＲ２１とし、レベル０領域ＡＲ２１で区切られる４つの領域をそれぞれレベル１領域ＡＲ４１、ＡＲ４２、ＡＲ４３、ＡＲ４４として領域を分割する。
この例では、符号化制御モジュール１１０ａの４つの走査ユニット１１６、１１６、１１６、１１６は、４つの領域ＡＲ４１、ＡＲ４２、ＡＲ４３、ＡＲ４４でそれぞれ異なる順序でＭＢ（マクロブロック）を走査する。【０１０２】
例えば、左下のレベル１領域ＡＲ４３の場合、レベル１領域ＡＲ４３の上側と右側とにそれぞれレベル０領域ＡＲ３１が隣接している。
１つの走査ユニット１１６は、レベル０領域ＡＲ３１からの空間予測における符号化情報を活用するために、図１０に示すように、レベル１領域ＡＲ４３の右上から符号化処理を開始して、左方向に符号化処理を進行させ、画面の左端部に達すると１ＭＢ（マクロブロック）分下に移動し、再び左方向に進む第１走査順で符号化処理を実行する。【０１０３】
他のレベル１領域ＡＲ４１、ＡＲ４２、ＡＲ４４についても同様に、それぞれに対応する走査ユニット１１６、１１６、１１６は、レベル０領域ＡＲ３１からの空間予測を利用できるように、レベル０領域ＡＲ３１と隣接しているＭＢ（マクロブロック）から符号化処理を開始する。
すなわち、２つめの走査ユニット１１６は、レベル０領域ＡＲ３１からの空間予測における符号化情報を活用するために、図１０に示すように、レベル１領域ＡＲ４１の右下から符号化処理を開始して、左方向に符号化処理を進行させ、画面の左端部に達すると１ＭＢ（マクロブロック）分上に移動し、再び左方向に進む第２走査順で符号化処理を実行する。【０１０４】
３つめの走査ユニット１１６は、レベル０領域ＡＲ３１からの空間予測における符号化情報を活用するために、図１０に示すように、レベル１領域ＡＲ４４の左上から符号化処理を開始して、右方向に符号化処理を進行させ、画面の右端部に達すると１ＭＢ（マクロブロック）分下に移動し、再び右方向に進む第３走査順で符号化処理を実行する。【０１０５】
４つめの走査ユニット１１６は、レベル０領域ＡＲ３１からの空間予測における符号化情報を活用するために、図１０に示すように、レベル１領域ＡＲ４２の左下から符号化処理を開始して、右方向に符号化処理を進行させ、画面の右端部に達すると１ＭＢ（マクロブロック）分上に移動し、再び右方向に進む第４走査順で符号化処理を実行する。【０１０６】
これにより、図９の例では、空間予測効率が悪いＭＢ（マクロブロック）の数は、図１０に示すように、レベル０領域に属するＭ＋（Ｎ−１）個となる。これは、図１３の関連技術の画面分割を行わない場合の例と同じ個数である。【０１０７】
このように、図９の例では、４つのレベル１領域ＡＲ４１、ＡＲ４２、ＡＲ４３、ＡＲ４４は、最大４並列で並列処理可能である。しかも、画面分割を行わない場合と同程度の符号化効率を維持しながら、高い並列度で効率よい符号化処理の並列化を実現できる。
また、図６の例と同様に、すべてのレベル１領域ＡＲ４１、ＡＲ４２、ＡＲ４３、ＡＲ４４は、レベル０領域ＡＲ３１からの空間予測における符号化情報を用いて符号化するため、イントラ予測や動きベクトルの性質には空間的な連続性がある。このため、関連技術の課題であったスライス境界での不自然な符号化ノイズは発生しない。【０１０８】
このように、本実施の形態に係る画像符号化における動作処理手順は、前記符号化制御に際しては、前記領域内をブロック単位で符号化するためのブロック符号化順序を、前記各領域毎に変更するように制御することができる。また、前記符号化制御に際しては、前記ブロック符号化順序を、前記領域の形状情報と前記領域処理順位とに応じて決定するように制御することができる。
さらに、前記符号化制御に際しては、一の前記領域の前記ブロック符号化順序を他の前記領域に隣接するブロック部分から符号化を開始し、前記他の領域における前記一の領域隣接部分の符号化情報を利用するように制御することができる。また、前記符号化制御に際しては、前記同一の領域処理順位が割り当てられた前記各領域を並列に符号化するように制御することができる。【０１０９】
更に、並列処理に応用する場合、前記符号化における制御をする際に、前記第２領域（レベル１の領域）内をブロック単位で符号化するためのブロック符号化順序を前記第２領域が前記第１領域によって分割された各サブ領域（図９の例ではＡＲ４１、ＡＲ４２、ＡＲ４３、ＡＲ４４）に応じて変更（又は各サブ領域毎に変更）するように制御することができる。又、前記符号化における制御をする際に、前記ブロック符号化順序を前記領域の形状情報と前記領域処理順位とに基づいて変更するように制御することができる。さらに、前記符号化における制御をする際に、前記第２領域内での前記ブロック符号化順序を前記第１領域に隣接するブロック部分から開始するように制御することができる。【０１１０】
例えば、図９に示す例では、第２領域（レベル１領域）を構成する各サブ領域ＡＲ４１、ＡＲ４２、ＡＲ４３、ＡＲ４４は全て異なるブロック符号化順序にて符号化する場合を示したが、ＡＲ４３とＡＲ４４とを同一順序、ＡＲ４１とＡＲ４２とを同一順序とする場合であってもよい。この場合、ブロック符号化順序を各サブ領域に応じて変更することができるといえる。
また、各サブ領域におけるブロック符号化スキャン順序は、図１０に示す例に限られるものではない。少なくとも第１領域に隣接するブロック部分から開始するようにすれば、如何なる順序でも構わない。必要に応じてＡＲ４１では、右下から右上を最初にスキャンするようにしてもよいし、種々のスキャン手法を採用することができる。【０１１１】
また、前記符号化における制御をする際に、一の前記領域内でのブロック符号化順序を前記一の領域に隣接し先に符号化される他の前記領域内の符号化情報を利用した空間予測処理をするように決定することができる。【０１１２】
以上で説明したように、本第２の実施の形態によると、関連技術の並列処理で課題であった符号化効率低下と不自然な符号化ノイズの発生を解消しながら符号化処理を効率良く並列実行できる。【０１１３】
その他の構成およびその他のステップないしは機能並びにその作用効果については、前述した実施の形態の場合と同一となっている。また、上記の説明において、上述した各ステップの動作内容及び各部の構成要素並びにそれらによる各機能をプログラム化（ソフトウエアプログラム）し、コンピュータに実行させてもよい。【０１１４】
［第３の実施の形態］
次に、本発明にかかる第３の実施の形態について、図１１に基づいて説明する。以下には、前記第１の実施の形態の実質的に同様の構成に関しては説明を省略し、異なる部分についてのみ述べる。図１１は、本発明の画像復号化装置の第３の実施の形態における全体構成の一例を示すブロック図である。【０１１５】
本実施の形態では、上述の各実施形態の画像符号化装置にて符号化されたビットストリームを復号化するための画像復号化装置の構成を開示している。【０１１６】
具体的には、本実施の形態の画像復号化装置２００は、図１１に示すように、入力ユニット２１１、ビットストリームメモリ２１２、分割レベル情報解析ユニット２１３、復号化順制御ユニット２１４、複数の各復号化ユニット２１５、各復号化ユニット２１５に対応して各々設けされる走査ユニット２１６、復号化画像メモリ２１７、出力ユニット２１８とを含んで構成される。【０１１７】
入力ユニット２１１は、上述の実施の形態の各領域の形状情報と領域処理順位とを含むビットストリームを入力することができる。【０１１８】
ビットストリームメモリ２１２は、入力ユニット２１１から入力される入力ビットストリームを格納する。【０１１９】
分割レベル情報解析ユニット２１３（解析手段）は、ビットストリームメモリ２１２に格納されているビットストリーム中の各領域の形状情報と領域処理順位とを取得し、これを解析する。【０１２０】
復号化順制御ユニット２１４（第１の復号化順序制御手段）は、各領域の形状情報と領域処理順位とに基づいて前記各領域に対応する前記ビットストリームを復号化するように前記復号化ユニット２１５を制御する。【０１２１】
各走査ユニット２１６（第２の復号化順序制御手段）のうち一の走査ユニット２１６は、一の領域について画素ブロック復号化順序に従って画素ブロックに対応するビットストリームを順次復号化するように対応する一の復号化ユニット２１５を制御する。
同様に、他の走査ユニット２１６は、他の領域について画素ブロック復号化順序に従って画素ブロックに対応するビットストリームを順次復号化するように対応する他の復号化ユニット２１５を制御する。
この際、一の領域についての画素ブロック復号化順序と他の領域についての画素ブロック復号化順序は適宜変更することができる。【０１２２】
一つの復号化ユニット２１５は、画素ブロック単位でビットストリームを復号化し、復号化画像を生成する処理を行う。各々の復号化ユニット２１５は、それぞれの並列処理可能な各領域に対応して設けられ、各領域に対応する各々のビットストリームの各々の復号化処理を並列処理可能な構成としている。【０１２３】
復号化画像メモリ２１７は、復号化ユニット２１５にて復号化された復号化画像を格納する。【０１２４】
出力ユニット２１８は、復号化画像メモリ２１７の復号化画像を出力する。【０１２５】
ここで、本実施の形態の分割レベル情報解析ユニット２１３と復号化順制御ユニット２１４と複数の走査ユニット２１６とにより復号化制御モジュール２１０ａを構成することもできる。また、一又は複数の復号化ユニット２１５により復号化モジュール２１０ｂを構成することもできる。この復号化制御モジュール２１０ａは、「復号化制御手段」の一例又は一部ということもできる。また、復号化モジュール２１０ｂは、「復号化手段」の一例又は一部ということもできる。【０１２６】
この場合、復号化モジュール２１０ｂは、入力されるビットストリームを復号化して復号化画像を生成する処理を行う。復号化制御モジュール２１０ａは、前記入力されるビットストリームの復号化順序を制御するために前記復号化手段の動作を制御する機能を備える。【０１２７】
復号化制御モジュール２１０ａは、前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含む前記ビットストリームを解析し、この領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する前記ビットストリームを復号化するように制御する機能を備える。
この場合、復号化制御モジュール２１０ａは、前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をするように制御する機能を備える。
ここにおいて、前記ビットストリームは、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たすように符号化制御された符号化情報であることを前提とするものである。【０１２８】
又、並列処理に応用する場合、復号化制御モジュール２１０ａは、少なくとも並列処理用画像分割境界を含む第１領域とその他の第２領域とに前記画像を分割して設定された前記各領域の形状情報と、少なくとも前記第１領域を前記第２領域より先に符号化するように前記各領域に設定された領域処理順位と、を含む前記ビットストリームを解析し、この領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する前記ビットストリームを復号化するように制御する機能を備える。【０１２９】
復号化制御モジュール２１０ａは、前記領域に対応するビットストリームをブロック単位で復号化する際に、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に応じてブロック復号化順序を変更するように制御する機能を備える。【０１３０】
復号化制御モジュール２１０ａは、画像をブロック間における空間予測依存性に応じて前記ブロック群からなる２以上の（並列処理用スライス分割とは異なる）各領域に分割して設定された前記各領域の形状情報と前記各領域での空間予測依存性に応じて前記各領域に設定された領域処理順位とを含む前記ビットストリームを解析し、この領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する前記ビットストリームを復号化するように制御する機能を備える。【０１３１】
また、復号化制御モジュール２１０ａは、前記領域に対応するビットストリームを画素ブロック単位で復号化する際に、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に応じてブロック復号化順序を変更するように制御する機能を備える。さらに、復号化制御モジュール２１０ａは、同一の前記領域処理順位を割り当てられた異なる各領域の各々の復号化処理を並列に実行するように制御する機能を備える。【０１３２】
（動作処理手順について）
（全体の概略動作）
次に、上述のような構成を有する画像復号化装置における全体の動作について、図１２を参照しつつ説明する。図１２は、図１１の画像復号化装置における処理手順の一例を示すフローチャートである。【０１３３】
本実施の形態に係る画像復号化における全体の動作処理手順は、基本的手順として、画像復号化装置が、前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含むビットストリームを入力し（図１２に示すステップＳ２０１）、入力ビットストリームの前記領域処理順位と前記領域の形状情報とを取得してこれを解析し（図１２に示すステップＳ２０２）、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する各ビットストリームを復号化して復号化画像を生成するように復号化制御を行う（図１２に示すステップＳ２０３〜ステップＳ２０９までのステップ）ことができる。
ここで、前記復号化制御に際しては、前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をするように制御することができる。【０１３４】
ここにおいて、前記ビットストリームは、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件、を満たすように符号化制御された符号化情報であることを前提とするものである。【０１３５】
また、並列処理に応用する場合、画像復号化装置が、少なくとも並列処理用画像分割境界を含む第１領域とその他の第２領域とに前記画像を分割して設定された前記各領域の形状情報と、少なくとも前記第１領域を前記第２領域より先に符号化するように前記各領域に設定された領域処理順位と、を含むビットストリームを入力することができ、入力ビットストリームの前記領域処理順位と前記領域の形状情報とを取得してその内容を解析し、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する各ビットストリームを復号化して復号化画像を生成するように復号化における制御を行うことができる。【０１３６】
また、この復号化制御をするに際しては、前記領域に対応するビットストリームをブロック単位として復号化するように制御し、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に応じて画素ブロック復号化順序を変更するように制御することができる。【０１３７】
さらに、復号化制御をするに際しては、同一の前記領域処理順位を割り当てられた異なる位置の各領域の各々の復号化処理を並列に実行するように制御することができる。また、前記解析をする際に、前記領域内での前記ブロック復号化順序をも前記入力ビットストリームから取得してこれを解析することができる。【０１３８】
（詳細動作）
以下、これを詳述する。
図１２に示すように、１フレームの復号化処理が開始すると、入力ユニット２１１は、ビットストリームを入力しビットストリームメモリ２１２に記憶する（ステップＳ２０１：ビットストリーム入力処理ステップないしはビットストリーム入力処理機能）。【０１３９】
続いて、分割レベル情報解析ユニット２１３が、ビットストリームに記録されている画面分割形状と各分割領域のレベル値を解析する（ステップＳ２０２：解析ステップないしは解析機能）。【０１４０】
次に、復号化順制御ユニット２１４が処理対象レベル値であるＬに０を設定し（ステップＳ２０３）、レベル値がＬである未処理領域が存在するかどうかを判定する（ステップＳ２０４）。【０１４１】
復号化順制御ユニット２１４がレベル値がＬである未処理領域が存在すると判定した場合には、その未処理領域についてステップＳ２０５〜Ｓ２０７の領域ＭＢ復号化処理に進む。【０１４２】
ここでは、一つの領域に対応するビットストリームについて画素ブロック単位に対応するビットストリームの復号化処理を行う。
ステップＳ２０５では、走査ユニット２１６が処理対象領域内に未処理ＭＢが存在するかを判定し、存在すると判定した場合にはステップＳ２０６に進む。【０１４３】
走査ユニット２１６が、未処理ＭＢが存在しないと判定した場合には、その領域の復号化処理を完了する。
ステップＳ２０６では、走査ユニット２１６が、分割レベル情報解析ユニット２１３から供給される画面分割形状と各分割領域のレベル値を基に処理対象領域でのＭＢ走査順を決定し、処理対象ＭＢを決定する。
ＭＢ走査順の決定手法は、前記第２の実施の形態と同様とする。【０１４４】
復号化ユニット２１５は、ビットストリームメモリ２１２から供給されるビットストリームと復号化画像メモリ２１７から供給される過去に符号化済みの画像を用いて１ＭＢに対するエントロピー符号復号化、逆量子化、逆整数変換、動き補償またはイントラ予測、デブロッキングフィルタ処理、局所復号画像の生成といった一連の復号化処理を実行し、復号結果を復号化画像メモリ２１７に格納する（ステップＳ２０７：復号化処理ステップないしは復号化処理機能）。
復号化画像メモリ２１７に格納された復号結果の画像は、出力ユニット２１８から出力される。【０１４５】
一方、上述のステップＳ２０４で復号化順制御ユニット２１４がレベル値がＬである未処理領域が存在しないと判定した場合はステップＳ２０８に進む。【０１４６】
ステップＳ２０８では、復号化順制御ユニット２１４が未処理の領域が存在するかを判定し、存在すると判定した場合には、ステップＳ２０９でＬの値を１増やしてステップＳ２０４に戻る。
一方、ステップＳ２０８で、復号化順制御ユニット２１４が未処理の領域が存在しないと判定した場合は、１フレームの復号化処理は完了する。【０１４７】
ここで、図１１の構成では、１または複数の復号化ユニット２１５を備える。複数の復号化ユニット２１５を備える場合、異なる領域に対する図９のフローチャートのステップＳ２０５〜ステップＳ２０７の処理は異なる復号化ユニット２１５を用いて並列に処理することが可能である。【０１４８】
また、以上のステップＳ２０５〜ステップＳ２０６からなるステップは、第２の復号化順序制御処理ステップの一例ということもできる。また、以上のステップＳ２０３、Ｓ２０４、Ｓ２０８、Ｓ２０９からなるステップは、第１の復号化順序制御処理ステップの一例ということもできる。  【０１４９】
以上のように本第３の実施の形態によれば、第２の実施の形態で挙げた符号化処理の場合の例と同様に、関連技術の並列処理で課題であった符号化効率低下と不自然な符号化ノイズの発生を解消しながら復号化処理を効率良く並列実行できる。【０１５０】
その他の構成およびその他のステップないしは機能並びにその作用効果については、前述した実施の形態の場合と同一となっている。また、上記の説明において、上述した各ステップの動作内容及び各部の構成要素並びにそれらによる各機能をプログラム化（ソフトウエアプログラム）し、コンピュータに実行させてもよい。【０１５１】
[その他の各種変形例]
また、本発明にかかる装置及び方法は、そのいくつかの特定の実施の形態に従って説明してきたが、本発明の主旨および範囲から逸脱することなく本発明の本文に記述した実施の形態に対して種々の変形が可能である。【０１５２】
例えば、画像の分割パターンの例（領域の形状の設定及び領域処理順位の設定例）としては、図１３、図１４、図１５に示すような例が挙げられる。
（変形例１）
図１３では、レベル数が２以上の場合を示している。
すなわち、図１３の例の画像では、領域数が１個のレベル０領域ＡＲ５１と、領域数が２個のレベル１領域ＡＲ５２―１、ＡＲ５２―２と、領域数が４個のレベル２領域ＡＲ５３―１、ＡＲ５３―２、ＡＲ５３―３、ＡＲ５３―４と、領域数が８個のレベル３領域ＡＲ５４―１、ＡＲ５４―２、ＡＲ５４―３、ＡＲ５４―４、ＡＲ５４―５、ＡＲ５４―６、ＡＲ５４―７、ＡＲ５４―８とを含む。
このように、階層的に領域を分割することで、並列処理可能な領域数を１→２→４→８と増やすことができる。【０１５３】
（変形例２）
図１４では、上位レベルの領域が分割境界とはならない場合を示している。
図１４の例の画像では、１つのレベル０領域ＡＲ６１と、６つのレベル１領域ＡＲ６２―１、ＡＲ６２―２、ＡＲ６２―３、ＡＲ６２―４、ＡＲ６２―５、ＡＲ６２―６とを含む。
ここで、６つのレベル１領域ＡＲ６２―１、ＡＲ６２―２、ＡＲ６２―３、ＡＲ６２―４、ＡＲ６２―５、ＡＲ６２―６間は、論理的な区切りＢＬによって区分されている。
このような場合には、各領域間では依存関係がないように符号化制御を行う。すなわち、同一レベルの各領域間で符号化情報の参照は不可となっている。【０１５４】
（変形例３）
図１５は、上位レベルのＭＢが分散している場合の例を示している。
図１５の例の画像では、９つのレベル０領域ＡＲ７１―１と、９つのレベル１領域ＡＲ７２―１とを含む。
ここで、レベル１領域ＡＲ７２―１は、レベル０領域ＡＲ７１―１の周囲に形成される。レベル１領域ＡＲ７２―１は、レベル０領域ＡＲ７１―１の符号化情報が利用できる。
ただし、各レベル１領域ＡＲ７２―１は、論理的な区切りＢＬによって区分されている。このような場合には、各レベル１領域間では依存関係がないように符号化制御を行う。すなわち、同一レベルの各領域間で符号化情報の参照は不可となっている。【０１５５】
また、同一のレベル値の各領域をブロック単位で符号化する際のブロック符号化順序は、ラスター走査に限らず、ジグザグ走査であってもよい。さらに、符号化制御手段が、一の領域でラスター走査を行い、他の領域でジグザグ走査を行ってもよい。
またさらに、各領域のラスター走査は、横方向のラスター走査に限らず、縦方向のラスター走査であってもよいし、それらを組み合わせてもよい。この際の走査開始位置及び走査終了位置は、空間予測効率の悪いMＢを低減するやり方であれば、領域内のいずれの箇所であってもよい。【０１５６】
さらに、上記の実施の形態ではＨ．２６４に則った応用について述べたが、本発明はこの応用のみに限定されるものではない。
また、画像分割の形に関しては限られた例についてのみ説明したが、本発明は例示した画像分割に限定されるものではなく、例示した以外の種々の画像分割の形にも適用可能である。【０１５７】
さらに、画像分割の形は固定的である必要はなく、画像毎に異なる形の画像分割を行うことや、動的に分割形状を変化させることも可能である。【０１５８】
また、領域内での走査順は領域の形状と隣接領域との関係から決定する例について説明したが、操作順の決定方法はこれに限定されるものではなく、符号化時に選択した走査順情報をビットストリームに符号化して伝送することも考えられる。
さらにまた、２または４並列で並列処理する例について説明したが、本発明はこの並列度に限定されるものではない。【０１５９】
また、動画像の符号化、復号化処理への適用例について説明したが、本発明は必ずしも動画像符号化、復号化に限定されるものではない。例えば、静止画の符号化、復号化など２次元のブロックベース処理で空間予測を利用する方式などにも適用可能である。【０１６０】
以上説明した方法は、コンピュータがプログラムを記録媒体から読み込んで実行することによっても実現することが出来る。すなわち、すなわち、上述のプログラムを、情報記録媒体に記録した構成であってもよい。【０１６１】
また、前述した実施形態の機能を実現する本発明のプログラムは、前述した各実施の形態における各種ブロック図などに示された処理部（処理手段）、機能などに対応したプログラムや、フローチャートなどに示された処理手順、処理手段、機能などに対応したプログラムや、各種データ構造を利用するプログラムなどにおいて各々処理される各処理プログラム、本明細書で全般的に記述される方法（ステップ）、説明された処理、データの全体もしくは各部を含む。【０１６２】
具体的には、本発明の一実施形態における画像符号化装置をソフトウェア上で実現するプログラムは、コンピュータに、入力される画像をブロックを含む各領域に分割して各領域の形状を設定するとともに、前記各領域に領域処理順位を設定する機能と、この領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化してビットストリームを生成するように符号化制御をする機能とを実行させる構成として構築する。
この場合、前記領域処理順位を制御する条件として、同一の前記領域処理順位の各領域間では、互いに符号化情報の利用を不可とする第一条件、少なくとも一の前記領域処理順位の領域では、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域への符号化情報の利用を可とする第二条件を満たす条件を設定する。【０１６３】
また、並列処理に応用する場合、コンピュータに、入力される画像を少なくとも並列処理用画像分割境界を含む第１領域とその他の第２領域とに分割して各領域の形状を設定するとともに少なくとも前記第１領域を前記第２領域より先に符号化するように前記各領域に領域処理順位を設定する機能と、この領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化してビットストリームを生成するように符号化制御をする機能とを実行させる構成として構築する。
前記第２領域の符号化をする際に前記第１領域の符号化情報を利用する。【０１６４】
また、本発明の一実施形態における画像復号化装置をソフトウェア上で実現するプログラムは、コンピュータに、前記画像をブロックを含む各領域に分割して設定された前記各領域の形状情報と、前記各領域に設定された領域処理順位と、を含むビットストリームから前記領域処理順位と前記領域の形状情報とを取得してその内容を解析する機能と、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する各ビットストリームを復号化して復号化画像を生成するように復号化における制御を行う機能とを実行させる構成として構築する。
この場合、前記各領域処理順位に従って前記各領域を復号化する際に、少なくとも一の前記領域処理順位の領域は、前記一の領域処理順位より優先度の高い他の前記領域処理順位の領域より後に復号化をする。【０１６５】
また、並列処理に応用する場合、コンピュータに少なくとも並列処理用画像分割境界を含む第１領域とその他の第２領域とに前記画像を分割して設定された前記各領域の形状情報と、少なくとも前記第１領域を前記第２領域より先に符号化するように前記各領域に設定された領域処理順位と、を含むビットストリームから前記領域処理順位と前記領域の形状情報とを取得してその内容を解析する機能と、前記領域処理順位と前記領域の形状情報とに基づいて前記各領域に対応する各ビットストリームを復号化して復号化画像を生成するように復号化における制御を行う機能とを実行させる構成として構築する。【０１６６】
また、本発明の一実施形態に係る符号化装置の符号化制御手段は、少なくとも並列処理用画像分割境界を含む第１領域とその他の第２領域とに前記画像を分割して前記第１、第２の各領域の形状を設定し、少なくとも前記第１領域を前記第２領域よりも先に符号化するように前記各領域に対して領域処理順位をそれぞれ設定し、前記各領域処理順位に従って前記各領域を符号化しこの際に前記第２領域は前記第１領域の符号化情報を利用して符号化するように制御する構成として構築する。【０１６７】
また、前記第１領域には、前記境界に沿った第１の方向と交差する第２の方向に延びて前記画像の第１の方向一端部側に形成される空間予測精度が通常より低い第１の一端部領域と、前記第１の方向に延びて前記画像の第２の方向一端部側に形成される空間予測精度が通常より低い第２の一端部領域とを含ませる。
この場合、前記符号化制御手段は、前記第１領域を符号化する際に前記第１、第２の各一端部領域を符号化するように制御する。【０１６８】
ここで、前記符号化制御手段は、前記画像をブロック間における空間予測依存性に応じて前記ブロック群からなる２以上の各領域に分割して前記各領域の形状を設定するとともに前記各領域での空間予測依存性に応じて前記各領域に領域処理順位を設定する。
また、前記符号化制御手段は、この領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化するように制御する。
この際、前記符号化制御手段は、一の領域処理順位の一領域では該一領域処理順位より優先度の低い他の領域処理順位の他領域を空間予測の際に参照せずに前記他領域より先に符号化するように制御する。また、前記符号化制御手段は、他領域での空間予測の際には、先に符号化された一領域の符号化情報を参照し利用する。【０１６９】
このような画像符号化装置では、画像をブロック間における空間予測依存性に応じて前記ブロック群からなる２以上の各領域に分割して前記各領域の形状を設定するとともに前記各領域での空間予測依存性に応じて前記各領域に符号化順序を示す領域処理順位を設定する。
そして、この領域処理順位と前記領域の形状情報とに基づいて前記各領域を符号化するように制御する。その際、一領域処理順位の一領域では該一領域処理順位より優先度の低い他領域処理順位の他領域を空間予測の際に参照せずに前記他領域より先に符号化するように制御する。さらに、以降の順位の他の領域での空間予測の際には、先に符号化された一領域の符号化情報を参照し利用する。
これにより、イントラ予測や動きベクトルの性質には空間的な連続性を保つことができ、加えて、同一領域処理順位の各領域は独立に並列処理することも可能になるためである。  【０１７０】
一実施の形態に係る画像符号化における全体の動作処理手順では、画像符号化装置の符号化制御モジュ−ル１０ａが、入力される画像をブロック間における空間予測依存性に応じて前記ブロック群からなる２以上の（関連技術における並列処理用スライス分割とは異なる）各領域に分割して前記各領域の形状を設定することができる。【０１７１】
また、一実施の形態に係る画像復号化における全体の動作処理手順は、画像復号化装置が備えたコンピュータが、画像をブロック間における空間予測依存性に応じて前記ブロック群からなる２以上の各領域に分割して設定された前記各領域の形状情報と前記各領域での空間予測依存性に応じて前記各領域に設定された領域処理順位とを含むビットストリームを入力することができる。【０１７２】
さらに、上述のプログラム（画像符号化処理プログラム、画像復号化処理プログラムを含む）を、情報記録媒体に記録した構成であってもよい。【０１７３】
また、前記実施の形態において、各構成のユニットが同一筐体中にあるか否かは問わない。このため、複数の機器から構成されるものに適用しても良いし、また、一つの機器からなる装置に適用しても良い。【０１７４】
さらに、このような各画像符号化装置、画像復号化装置は、単独で存在する場合もあるし、ある機器（例えば電子機器など）に組み込まれた状態で利用されることもあるなど、発明の思想としてはこれに限らず、各種の態様を含むものである。
さらにまた、一部がソフトウェアであって、一部がハードウェアで実現されている場合であってもよく、一部を記憶媒体上に記憶しておいて必要に応じて適宜読み込まれるような形態のものとしてあってもよい。【０１７５】
また、発明の範囲は、図示例に限定されないものとする。さらに、上記各実施の形態には種々の段階が含まれており、開示される複数の構成要件における適宜な組合せにより種々の発明が抽出され得る。つまり、上述の各実施の形態同士、あるいはそれらのいずれかと各変形例のいずれかとの組合せによる例をも含む。【０１７６】
この出願は２００８年９月９日に出願された日本出願特願２００８−２３１３５９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１７７】
本発明は、画像符号化装置、画像復号化装置全般に適用可能である。
【図面の簡単な説明】
【０１７８】
【図１】本発明の第１の実施の形態による画像符号化装置の全体構成の一例を示すブロック図である。
【図２】本発明の第１の実施の形態による画像符号化装置における処理手順の一例を示すフローチャートである。
【図３】図１の画像符号化装置における符号化順序制御のレベル割り当て例を模式的に示す説明図である。
【図４】図１の画像符号化装置における符号化順序制御の具体例を模式的に示す説明図である。
【図５】本発明の第２の実施の形態による画像符号化装置の全体構成の一例を示すブロック図である。
【図６】図５の画像符号化装置における符号化順序制御のレベル割り当て例を模式的に示す説明図である。
【図７】図５の画像符号化装置における符号化順序制御の具体例を模式的に示す説明図である。
【図８】下方向からの動きベクトル予測の動作の具体例を説明するための説明図である。
【図９】図５の画像符号化装置における符号化順序制御のレベル割り当ての他の例を模式的に示す説明図である。
【図１０】図５の画像符号化装置における符号化順序制御の他の具体例を模式的に示す説明図である。
【図１１】本発明の第３の実施の形態による画像復号化装置の全体構成の一例を示すブロック図である。
【図１２】本発明の第３の実施の形態による画像復号化装置における処理手順の一例を示すフローチャートである。
【図１３】本発明のその他の実施の形態による画像符号化装置における符号化順序制御のレベル割り当て例を模式的に示す説明図である。
【図１４】本発明のその他の実施の形態による画像符号化装置における符号化順序制御のレベル割り当て例を模式的に示す説明図である。
【図１５】本発明のその他の実施の形態による画像符号化装置における符号化順序制御のレベル割り当て例を模式的に示す説明図である。
【図１６】関連技術の符号化処理手法の動作の具体例を示す図である。
【図１７】動きベクトル予測の動作の具体例を示す図である。
【図１８】イントラ予測の動作の具体例を示す図である。
【図１９】関連技術の符号化並列処理手法の動作の具体例を示す図である。
【符号の説明】
【０１７９】
１、１００  画像符号化装置
１０a、１１０ａ  符号化制御モジュール（符号化制御手段）
１０ｂ、１１０ｂ  符号化モジュール（符号化手段）
１１    入力ユニット
１２    入力画像メモリ
１３、１１３    分割レベル割り当てユニット
１４、１１４    符号化順制御ユニット
１５    符号化ユニット
１６、１１６    走査ユニット
１７    符号化画像メモリ
１８    出力ユニット
２００  画像復号化装置
２１０ａ  復号化制御モジュール（復号化制御手段）
２１０ｂ  復号化モジュール（復号化手段）
２１１    入力ユニット
２１２    ビットストリームメモリ
２１３    分割レベル情報解析ユニット
２１４    復号化順制御ユニット
２１５    復号化ユニット
２１６    走査ユニット
２１７    復号化画像メモリ
２１８    出力ユニット  
【図１】
2010029850.tif 000003
【図２】
2010029850.tif 000004
【図３】
2010029850.tif 000005
【図４】
2010029850.tif 000006
【図５】
2010029850.tif 000007
【図６】
2010029850.tif 000008
【図７】
2010029850.tif 000009
【図８】
2010029850.tif 000010
【図９】
2010029850.tif 000011
【図１０】
2010029850.tif 000012
【図１１】
2010029850.tif 000013
【図１２】
2010029850.tif 000014
【図１３】
2010029850.tif 000015
【図１４】
2010029850.tif 000016
【図１５】
2010029850.tif 000017
【図１６】
2010029850.tif 000018
【図１７】
2010029850.tif 000019
【図１８】
2010029850.tif 000020
【図１９】
2010029850.tif 000021
【国際調査報告】
2010029850.tif 000022
2010029850.tif 000023
2010029850.tif 000024
2010029850.tif 000025