(57)【要約】  本発明の動画像符号化装置は、画像の各ブロックの符号化にそれぞれ必要な符号化情報を記憶するバッファメモリと、前記バッファメモリに記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行うデータソート部および可変長符号化部からなる符号化部とを備えている。これにより、広範囲での空間的な相関を活かした符号化を行うことができる動画像符号化装置を提供する。
2007063612.tif 000002
【特許請求の範囲】
【請求項１】
画像を複数のブロックに分割し符号化する動画像符号化装置において、
前記各ブロックの符号化にそれぞれ必要な符号化情報を記憶する一時記憶手段と、
前記一時記憶手段に記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行う符号化手段とを備えていることを特徴とする動画像符号化装置。
【請求項２】
前記符号化手段は、
前記一時記憶手段に記憶されたＭ×Ｎブロックの符号化情報を、所定の走査手順で走査して１次元データ列に変換するデータ列変換手段と、
変換後の１次元データ列から所定の規則で複数の１次元データ列を生成するデータ列生成手段と、
生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替え手段と、
並べ替えられた１次元データ列に対して可変長符号化を行う可変長符号化手段とを備えていることを特徴とする請求項１に記載の動画像符号化装置。
【請求項３】
前記データ列変換手段は、
前記符号化情報の種類毎に、異なる走査順序で１次元データ列への変換を行うことを特徴とする請求項２に記載の動画像符号化装置。
【請求項４】
前記データ並べ替え手段は、
BWT(Burrows-Wheeler Transform)を用いて、１次元データ列の並べ替えを行うことを特徴とする請求項２に記載の動画像符号化装置。
【請求項５】
前記データ並べ替え手段は、
符号化対象の空間解像度が所定の閾値未満の場合、Ｍ１×Ｎ１ブロック毎に前記１次元データ列の並べ替えを行い、
符号化対象の空間解像度が所定の閾値以上の場合、Ｍ２×Ｎ２ブロック毎に前記１次元データ列の並べ替えを行うとき、
ブロックサイズの関係がＭ１×Ｎ１＜Ｍ２×Ｎ２を満たすことを特徴とする請求項２に記載の動画像符号化装置。
【請求項６】
前記符号化情報は、符号化対象となる動画像に適用する予測方式を示すデータ、および当該予測方式と共に用いる予測パラメータ、および符号化対象となる動画像に当該予測方式を適用して求められる予測残差データのすくなくとも一つであることを特徴とする請求項１〜５の何れか１項に記載の動画像符号化装置。
【請求項７】
請求項１に記載の動画像符号化装置によって符号化された動画像データを復号する動画像復号装置において、
Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号する復号手段を備えていることを特徴とする動画像復号装置。
【請求項８】
請求項２〜６の何れか１項に記載の動画像符号化装置によって符号化された動画像データを復号する動画像復号装置において、
Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号する復号手段を備え、
前記復号手段は、
符号化された符号化情報を可変長復号する可変長復号手段と、
可変長復号された符号化情報から複数の１次元データ列を生成するデータ列生成手段と、
生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替え手段と、
並べ替えられた１次元データ列を、Ｍ×Ｎブロックの符号化情報を走査して得られる１次元データ列に変換するデータ列変換手段と有することを特徴とする動画像復号装置。
【請求項９】
前記データ列変換手段は、前記符号化情報の種類毎に、異なる逆走査順序で１次元データ列に変換することを特徴とする請求項８に記載の動画像復号装置。
【請求項１０】
前記データ並べ替え手段は、逆BWT(Burrows-Wheeler Transform)を用いて１次元データ列の並べ替えを行うことを特徴とする請求項８に記載の動画像復号装置。
【請求項１１】
前記データ並べ替え手段は、
符号化対象の空間解像度が所定の閾値未満の場合、Ｍ１×Ｎ１ブロック毎に前記１次元データ列の並べ替えを行い、
符号化対象の空間解像度が所定の閾値以上の場合、Ｍ２×Ｎ２ブロック毎に前記１次元データ列の並べ替えを行うとき、
ブロックサイズの関係がＭ１×Ｎ１＜Ｍ２×Ｎ２を満たすことを特徴とする請求項８に記載の動画像復号装置。
【請求項１２】
前記符号化情報は、前記符号化情報は、符号化対象となる動画像に適用する予測方式を示すデータ、および当該予測方式と共に用いる予測パラメータ、および符号化対象となる動画像に当該予測方式を適用して求められる予測残差データのすくなくとも一つであることを特徴とする請求項７〜１１の何れか１項に記載の動画像復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像デ−タの高能率符号化技術を実現するための動画像符号化装置および動画像復号装置に関する。
【背景技術】
【０００２】
動画像データの高能率符号化を実現する従来技術としては、非特許文献１に記載のH.264/AVC動画像符号化技術が挙げられる。【０００３】
上記H.264/AVC動画符号化技術を適用した動画像符号化装置について、図面を参照しながら説明する。【０００４】
図１３は、従来技術の動画像符号化装置のブロック図である。【０００５】
図１３において、符号１は、符号化済みの画像を蓄積するフレームメモリ、符号２は、符号化対象の画像に用いる予測方式および予測パラメータを決定する予測方式制御部、符号３は、フレームメモリ１に蓄積された符号化済み画像から予測画像を生成する予測画像生成部、符号４は、符号化対象の画像と予測画像の差分画像を生成する差分画像生成部、符号５は、差分画像を直交変換する直交変換部、符号６は、直交変換部５の出力データを量子化し予測残差データを出力する量子化部、符号７は、量子化部６と逆の操作によって入力データを逆量子化する逆量子化部、符号８は、直交変換部５と逆の操作によって入力データを逆直交変換する逆変換部、符号９は、逆変換部８の出力データと予測画像を合成する画像合成部、符号１０は、量子化部６の出力する２次元データをジグザグスキャンすることで１次元データ列に並べ替えるデータスキャン部、符号１１は、予測方式、予測パラメータ、及び、予測残差データを個々の要素別に可変長符号化する可変長符号化部である。【０００６】
上記構成の動画像符号化装置の動作について、図１３に加え、図１４の動作フロー図を参照しながら説明する。なお、本動画像符号化装置は、画像を１６ｘ１６画素の矩形領域からなるマクロブロック毎に以下の処理を行うものとする。【０００７】
STEP1)  予測方式制御部２は、符号化対象マクロブロックに用いる予測方式および予測パラメータを決定する（Ｓ１０１）。【０００８】
ここで、予測方式は、画面内予測、画面間予測（前方予測、後方予測、双方向予測）のいずれか１つを選択する。【０００９】
また、予測パラメータとして、予測を行う単位（マクロブロック分割パターン）、画面内予測の場合は、複数ある画面内予測方法のいずれを適用するか、画面間予測の場合は、動きベクトル、予測に用いる参照画像の組み合わせが決定される。なお、予測方式および予測パラメータの決定方法は、全ての予測方式および予測パラメータの組み合わせで予測画像を予測画像生成部３にて生成し、符号化対象となる画像との相関が最も高いものを用いることが望ましいが、処理量が膨大となるため、予め選択候補となる予測方式および予測パラメータを限定し、その候補内で最も相関の高い予測画像が得られた予測方式および予測パラメータを選択する方法であっても構わない。【００１０】
STEP2)  可変長符号化部１１は、予測方式制御部２で決定した予測方式及び予測パラメータを要素別に可変長符号化する（Ｓ１０２）。【００１１】
STEP3)  予測画像生成部３は、予測方式制御部２が決定した予測方式および予測パラメータに基づき当該マクロブロックの予測画像を生成する（Ｓ１０３）。【００１２】
STEP4)  差分画像生成部４は、当該マクロブロックの画像と予測画像の差分画像を生成する（Ｓ１０４）。【００１３】
STEP5)  直交変換部５は、当該マクロブロックの差分画像に対し、４ｘ４画素ブロック毎に直交変換を行う（Ｓ１０５）。【００１４】
STEP6)  量子化部６は、直交変換部５の出力する４ｘ４ブロックデータに対し量子化を行う（Ｓ１０６）。【００１５】
STEP7)  逆量子化部７は、量子化部６の出力する予測残差データに対し、逆量子化を行う（Ｓ１０７）。【００１６】
STEP8)  逆変換部８は、逆量子化部７の出力する４ｘ４ブロックデータに対し逆直交変換を行う（Ｓ１０８）。【００１７】
STEP9)  データスキャン部１０は、量子化部６が出力した予測残差データをジグザグスキャンし、１次元データ列へ並べ替える（Ｓ１０９）。【００１８】
STEP10)  可変長符号化部１１は、１次元化された予測残差データの各要素を可変長符号化する（Ｓ１１０）。【００１９】
STEP11)  マクロブロックを構成する全ての４ｘ４画素ブロックについてSTEP5〜10を繰り返す（Ｓ１１１）。【００２０】
STEP12)  画像合成部９は、逆変換部８の出力データと予測画像生成部３で生成された予測画像を合成し、合成した画像を符号化し、符号化済の画像として以降の符号化に利用するためフレームメモリ１に蓄積する（Ｓ１１２）。【００２１】
STEP13)  符号化対象の画像を構成する全てのマクロブロックについて、STEP1〜12を繰り返す（Ｓ１１３）。
【非特許文献１】ITU-T Recommendation H.264:"Advanced Video Coding for generic audiovisual services" (2003)
【発明の開示】
【００２２】
以上説明したように、従来の動画像符号化装置においては、１６ｘ１６画素の矩形領域からなるマクロブロックを処理単位として、符号化情報（予測方式、予測パラメータ、予測残差データ等）の符号化が行われる。マクロブロックサイズは、空間解像度の低い画像を符号化する場合も、空間解像度の高い画像を符号化する場合でも一定である。しかしながら、一般に空間解像度が高くなるほど、符号化対象となる画像の空間的な相関は高くなるため、符号化情報についても隣接マクロブロック間で高い相関を示す傾向がある。
【００２３】
したがって、従来の動画像符号化装置では、マクロブロックサイズよりも広い範囲で高い相関の現れるような高解像度の画像を符号化する場合では、広範囲での空間的な相関を活かした符号化を行うことができないといった問題が生じる。
【００２４】
本発明は、上記の問題点に鑑みなされたものであり、その目的は、マクロブロックサイズよりも広い範囲で高い相関の現れるような高解像度の画像を符号化する場合であっても、広範囲での空間的な相関を活かした符号化を行うことができる動画像符号化装置を提供することにある。
【００２５】
本発明に係る動画像符号化装置は、上記課題を解決するために、画像を複数のブロックに分割し符号化する動画像符号化装置において、前記各ブロックの符号化にそれぞれ必要な符号化情報を記憶する一時記憶手段と、前記一時記憶手段に記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行う符号化手段とを備えていることを特徴としている。
【００２６】
前記符号化手段は、具体的には、前記一時記憶手段に記憶されたＭ×Ｎブロックの符号化情報を、所定の走査手順で走査して１次元データ列に変換するデータ列変換手段と、変換後の１次元データ列から所定の規則で複数の１次元データ列を生成するデータ列生成手段と、生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替え手段と、並べ替えられた１次元データ列に対して可変長符号化を行う可変長符号化手段とを備えているのが好ましい。
【００２７】
また、前記データ列変換手段は、前記符号化情報の種類毎に、異なる走査順序で１次元データ列への変換を行ってもよい。
【００２８】
また、前記データ並べ替え手段は、BWT(Burrows-Wheeler Transform)を用いて、１次元データ列の並べ替えを行ってもよい。
【００２９】
前記データ並べ替え手段は、符号化対象の空間解像度が所定の閾値未満の場合、Ｍ１×Ｎ１ブロック毎に前記１次元データ列の並べ替えを行い、符号化対象の空間解像度が所定の閾値以上の場合、Ｍ２×Ｎ２ブロック毎に前記１次元データ列の並べ替えを行うとき、ブロックサイズの関係がＭ１×Ｎ１＜Ｍ２×Ｎ２を満たすようにしてもよい。
【００３０】
前記符号化情報は、符号化対象となる動画像に適用する予測方式を示すデータ、および当該予測方式と共に用いる予測パラメータ、および符号化対象となる動画像に当該予測方式を適用して求められる予測残差データのすくなくとも一つであることが望ましい。
【００３１】
本発明の動画像復号装置は、上記の課題を解決するために、前記動画像符号化装置によって符号化された動画像データを復号する動画像復号装置において、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号する復号手段を備えていることを特徴としている。
【００３２】
また、前記復号手段は、符号化された符号化情報を可変長復号する可変長復号手段と、可変長復号された符号化情報から複数の１次元データ列を生成するデータ列生成手段と、生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替え手段と、並べ替えられた１次元データ列を、Ｍ×Ｎブロックの符号化情報を走査して得られる１次元データ列に変換するデータ列変換手段とを有してもよい。
【００３３】
前記データ列変換手段は、前記符号化情報の種類毎に、異なる逆走査順序で１次元データ列に変換してもよい。
【００３４】
前記データ並べ替え手段は、逆BWT(Burrows-Wheeler Transform)を用いて１次元データ列の並べ替えを行ってもよい。
【００３５】
前記データ並べ替え手段は、符号化対象の空間解像度が所定の閾値未満の場合、Ｍ１×Ｎ１ブロック毎に前記１次元データ列の並べ替えを行い、符号化対象の空間解像度が所定の閾値以上の場合、Ｍ２×Ｎ２ブロック毎に前記１次元データ列の並べ替えを行うとき、ブロックサイズの関係がＭ１×Ｎ１＜Ｍ２×Ｎ２を満たすのが望ましい。
【００３６】
前記符号化情報は、符号化対象となる動画像に適用する予測方式を示すデータ、および当該予測方式と共に用いる予測パラメータ、および符号化対象となる動画像に当該予測方式を適用して求められる予測残差データのすくなくとも一つであることが望ましい。
【００３７】
本発明に係る動画像符号化装置は、以上のように、画像を複数のブロックに分割し符号化する動画像符号化装置において、前記各ブロックの符号化にそれぞれ必要な符号化情報を記憶する一時記憶手段と、前記一時記憶手段に記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行う符号化手段とを備えていることで、空間解像度の違いによる隣接ブロック間の相関の高さを考慮した符号化が可能となり、この結果、低解像度の画像から高解像度の画像まで幅広く符号化を行うことができるという効果を奏する。
【００３８】
また、本発明に係る動画像復号装置は、本発明に係る動画像符号化装置によって符号化された高効率の動画像符号化データを復号・再生することが可能である。
【図面の簡単な説明】
【００３９】
【図１】本発明の実施形態を示すものであり、動画像符号化装置の要部構成を示すブロック図である。
【図２】図１に示す動画像符号化装置による符号化処理の流れを示すフローチャートである。
【図３（ａ）】４×４のマクロブロックの一例を示す図である。
【図３（ｂ）】図３（ａ）で示したマクロブロックの走査パターンを示す図である。
【図３（ｃ）】図３（ａ）で示したマクロブロックの走査パターンを示す図である。
【図３（ｄ）】図３（ａ）で示したマクロブロックの走査パターンを示す図である。
【図３（ｅ）】図３（ａ）で示したマクロブロックの走査パターンを示す図である。
【図３（ｆ）】図３（ａ）で示したマクロブロックの走査パターンを示す図である。
【図３（ｇ）】図３（ａ）で示したマクロブロックの走査パターンを示す図である。
【図４（ａ）】８×８のマクロブロックの走査パターンを示す図である。
【図４（ｂ）】８×８のマクロブロックの走査パターンを示す図である。
【図４（ｃ）】８×８のマクロブロックの走査パターンを示す図である。
【図４（ｄ）】８×８のマクロブロックの走査パターンを示す図である。
【図４（ｅ）】８×８のマクロブロックの走査パターンを示す図である。
【図４（ｆ）】８×８のマクロブロックの走査パターンを示す図である。
【図５】（ａ）〜（ｅ）は図１に示す動画像符号化装置に備えられたデータソート部によるデータソート処理の流れを示すフローチャートである。
【図６（ａ）】４×４の固定サイズのマクロブロックの一例を示す図である。
【図６（ｂ）】図６（ａ）で示したマクロブロックの走査パターンを示す図である。
【図６（ｃ）】図６（ａ）で示したマクロブロックの走査パターンを示す図である。
【図６（ｄ）】図６（ａ）で示したマクロブロックの走査パターンを示す図である。
【図６（ｅ）】図６（ａ）で示したマクロブロックの走査パターンを示す図である。
【図６（ｆ）】図６（ａ）で示したマクロブロックの走査パターンを示す図である。
【図６（ｇ）】図６（ａ）で示したマクロブロックの走査パターンを示す図である。
【図７（ａ）】可変サイズのマクロブロックの一例を示す図である。
【図７（ｂ）】図７（ａ）で示したマクロブロックの走査パターンを示す図である。
【図７（ｃ）】図７（ａ）で示したマクロブロックの走査パターンを示す図である。
【図７（ｄ）】図７（ａ）で示したマクロブロックの走査パターンを示す図である。
【図７（ｅ）】図７（ａ）で示したマクロブロックの走査パターンを示す図である。
【図７（ｆ）】図７（ａ）で示したマクロブロックの走査パターンを示す図である。
【図７（ｇ）】図７（ａ）で示したマクロブロックの走査パターンを示す図である。
【図８】予想残差データの走査パターンの例を示す図である。
【図９】図１に示す動画像符号化装置に備えられた可変長符号化部による可変長符号化方法の一例を示す図である。
【図１０】本発明の他の実施形態を示すものであり、動画像復号装置の要部構成を示すブロック図である。
【図１１】図１０に示す動画像復号装置の復号処理の流れを示すフローチャートである。
【図１２】（ａ）〜（ｇ）は図１０に示す動画像復号装置に備えられたデータ逆ソート部によるデータ逆ソート処理の流れを示す図である。
【図１３】従来の動画像符号化装置の要部構成を示すブロック図である。
【図１４】図１３に示す動画像符号化装置の符号化処理の流れを示すフローチャートである。
【発明を実施するための最良の形態】
【００４０】
〔実施形態１〕
本発明の第１の実施形態の動画像符号化装置について図面を参照しながら説明する。図１は本実施形態における動画像符号化装置のブロック図である。【００４１】
図１において、符号１２は、複数マクロブロックの符号化情報（予測方式、予測パラメータ、予測残差データ）を一時保存するためのバッファメモリ、符号１３は、バッファメモリに記録された符号化情報(予測方式、予測パラメータ、予測残差データ)を所定の方法で並べ替えるデータソート部、符号１４は、データソート部１３の出力結果を可変長符号化する可変長符号化部である。上記データソート部１３および可変長符号化部１４によって、バッファメモリ１２に記憶された複数の符号化情報（予測方式、予測パラメータ、予測残差データ）に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行う符号化部（符号化手段）１００を構成している。【００４２】
なお、従来技術の動画像符号化装置（図１３）と同一機能を有するブロックについては、名称および符号を同一とし説明を省略する。【００４３】
上記構成の動画像符号化装置の動作の概要について図１に加え、図２の動作フロー図を参照して説明する。【００４４】
STEP1)  予測方式制御部２は、符号化対象マクロブロックに用いる予測方式および予測パラメータを決定する（Ｓ１）。【００４５】
予測方式および予測パラメータの決定方法については、従来技術の動画像符号化装置と同様であり、説明を省略する。なお、決定した予測方式および予測パラメータはバッファメモリ１２に記録される。【００４６】
STEP2)  予測画像生成部３は、予測方式制御部２が決定した予測方式および予測パラメータに基づき当該マクロブロックの予測画像を生成する（Ｓ２）。【００４７】
STEP3)  差分画像生成部４は、当該マクロブロックの画像と予測画像の差分画像を生成する（Ｓ３）。【００４８】
STEP4)  直交変換部５は、当該マクロブロックの差分画像に対し、４ｘ４画素ブロック毎に直交変換を行う（Ｓ４）。【００４９】
STEP5)  量子化部６は、直交変換部５の出力する４ｘ４ブロックデータに対し量子化を行う。出力される予測残差データは、バッファメモリ１２に記録される（Ｓ５）。【００５０】
STEP6)  逆量子化部７は、量子化部６の出力する予測残差データに対し、逆量子化を行う（Ｓ６）。【００５１】
STEP7)  逆変換部８は、逆量子化部７の出力する４ｘ４ブロックデータに対し逆直交変換を行う（Ｓ７）。【００５２】
STEP8)  マクロブロックを構成する全ての４×４画素ブロックについて、STEP４〜７を繰り返す（Ｓ８）。【００５３】
STEP9)  画像合成部９は、逆変換部８の出力データと予測画像生成部３で生成された予測画像を合成し、生成された画像を以降の符号化に利用するためフレームメモリ１に蓄積する（Ｓ９）。【００５４】
STEP10)  符号化対象の画像を構成する全てのマクロブロックについて、STEP１〜9を繰り返す（Ｓ１０）。【００５５】
STEP11)  データソート部１３は、Ｍ×Ｎマクロブロック（Ｍ，Ｎは所定の整数）からなるマクロブロック群を単位としてバッファメモリ１２に記録された予測方式、予測パラメータ、および予測残差データのそれぞれを所定の手順で並べ替える（Ｓ１１）。なお、データソート部１３の詳細については後述する。【００５６】
STEP12)  可変長符号化部１４は、データソート部１３が出力する予測方式、予測パラメータおよび予測残差データのそれぞれをマクロブロック群単位で可変長符号化する（Ｓ１２）。なお、可変長符号化部１４の詳細についても後述する。【００５７】
STEP13)  符号化対象の画像を構成する全てのマクロブロック群の符号化が終わるまで、STEP1〜12を繰り返す（Ｓ１３）。【００５８】
以上の手順により、本実施形態の動画像符号化装置では動画像データの符号化が行われる。なお、上述の説明では、STEP１１、１２において、予測方式、予測パラメータ、及び予測残差データをマクロブロック群単位で並べ替え、それぞれ可変長符号化するとして説明したが、符号化情報の一部（例えば予測残差データ）は、データソート部１３を介さず、各マクロブロック毎にバッファメモリ１２から可変長符号化部１４へ入力し、従来技術と同様に、マクロブロック単位の符号化を行う構成であっても構わない。【００５９】
次に、上記データソート部１３の詳細について説明する。【００６０】
データソート部１３は、所定のマクロブロック群の入力データに対してBWT（Burrows-Wheeler Transform)を用いて、効率的な可変長符号化が可能なデータ列へ変換する。【００６１】
BWTは、１次元データ列を対象とした変換であって、例えば、“0,1,0,1,0,1,…”というように繰り返し同じパターンが現れるデータ列を入力した場合、出力データ列では入力データ列に比べ、同一値を持つ要素が連続しやすいといった性質を備えた変換である。したがって、一連の同一値を持つ要素に対して一括して符号割り当て（例えばランレングス符号）を行うことで、効率的な可変長符号化を行うことが可能である。【００６２】
予測方式のように１マクロブロックに対し１要素からなるデータを扱う場合、マクロブロック群を例えば図３（ａ）に示すような４×４マクロブロック（ＭＢ０〜ＭＢ１５）として処理するならば、図３（ｂ）〜図３（ｇ）に示すような走査パターンのいずれか１つを用いて、入力データを１次元データ列へ変換すれば、隣接マクロブロック間の相関によって繰り返し同じパターンが現れ易くなるため、BWTの適用によって出力データ列で同一値を持つ要素が連続し易くなり、効率の良い符号化が可能となる。【００６３】
同様に、マクロブロック群を８×８マクロブロックとして処理するならば、図４（ａ）〜図４（ｆ）に示すような走査パターンのいずれか１つを用いれば、BWT後の出力データ列で、同一値を持つ要素が連続し易くなることが期待できる。【００６４】
なお、隣接マクロブロック間での符号化情報の相関の強さは、符号化対象となる画像の空間解像度に応じて異なるため、データソート部１３の処理単位であるマクロブロック群のサイズおよび走査パターンは、予め複数の画像の符号化シミュレーションを行い、最も性能の良い組み合わせを用いることが望ましく、例えば、低解像度の画像を符号化する場合は、４ｘ４マクロブロックを処理するマクロブロック群とし、高解像度の画像を符号化する場合には、８ｘ８マクロブロックを処理するマクロブロック群とすれば、空間解像度の違いによる隣接マクロブロック間の相関の高さを考慮した効率的な符号化が可能である。また符号化情報の相関の高さは、符号化対象の画像毎でも異なるため、予め複数の組み合わせを用意し、画像に応じて符号化に使用する組み合わせを適応的に選択可能な構成としても構わない。また、符号化情報の要素（予測方式、予測パラメータ、予測残差データ）毎でも相関の強さが異なるため、符号化情報の要素毎にマクロブロック群のサイズ、走査パターンを用いる構成であっても構わない。【００６５】
図５に具体的なデータソート部の動作例を示す。なお、図５（ａ）は、データソート部１３への入力データの例を示し、ここでは、４ｘ４マクロブロックのそれぞれに、要素値０〜２を持つデータが存在している例を示している。例えば、各要素値が予測方式を表し、０：前方予測、１：後方予測、２：画面内予測を示すものとする。【００６６】
STEP1)  図５（ａ）に対し、前述の図３（ｂ）に示す走査パターンを適用すると、図５（ｂ）の１次元データ列S0が得られる。【００６７】
STEP2)  S0の要素を１要素ごと左にシフトし、先頭要素を最後尾へ巡回させて、１次元データ列S1を生成する。同様の操作を繰り返して、S1〜S15を生成する（図５（ｃ））。【００６８】
STEP3)  S0〜S15を下記の条件で昇順にソートする（図５（ｄ））。【００６９】
２つの１次元データ列Sa:=Ea0、Ea1、Ea2、・・・、Ea15、Sb:=Eb0、Eb1、・・・、Eb15に対し、
条件１：Ea0 ＜ Eb0 ならばSa < Sb
条件２：Eai = Ebi （０≦ｉ＜ｉ＜ｊを満たす任意のｉ）、かつ、Eaj＜EbjならばSa＜Sb
STEP4)  ソートされたS0〜S15の最後尾の要素を順に出力データ列とし、復号に必要な付加情報としてソート結果におけるS0の順位を出力する（図５（e））。【００７０】
以上の説明では、１マクロブロックに１要素からなるデータをデータソート部１３で扱う場合について説明したが、１マクロブロックに複数の要素が存在するデータについても同様に取り扱うことができる。【００７１】
例えば、画面内予測における予測パラメータである予測方法は、１つのマクロブロックを図６（ａ）に示す例のように、４×４サブマクロブロック（B0〜B15）に分割したサブマクロブロック毎にデータが存在するが、マクロブロック単位での走査パターンと同様、隣接サブマクロブロック間の相関を考慮して、図６（ｂ）〜図６（ｇ）に示すようなパターンを用いればよい。【００７２】
また、フレーム間予測の予測パラメータである動きベクトルや参照画像の指定のように、可変サイズのサブマクロブロック毎にパラメータが存在する場合も同様である。例えば、図７（ａ）に示すような可変サイズのサブマクロブロックB0〜B4が存在する場合、走査パターン自体は、固定サイズのサブブロックでの例（図６）と同様に定め、重複したサブマクロブロックを走査した場合、２度目以降の走査を無視すればよい。例えば、図７（ｂ）の走査パターンの場合であれば、B0、B1、B2、B3、B4を出力、図７（ｃ）の場合、B0、B4、B1、B2、B3を出力、図７（ｄ）の場合、B0、B1、B4、B3、B2を出力するといった具合である。【００７３】
また、予測残差データの場合も、同様に隣接ブロック間の同一周波数成分に高い相関があると考えられることから、図８に示す例のように、４つの隣接ブロック（B0、B1、B4、B5)に存在する１６ｘ４要素の予測残差データの操作順序を図中の数値の順で示す通り、低周波成分から高周波成分に向かって走査し、同様の走査を残りのブロックにも適用すれば良い。【００７４】
次に、可変長符号化部１４の詳細について説明する。本実施形態の可変長符号化部１４は、前述の通り、データソート部１３が出力するデータ列が同一値を持つ要素が連続し易い性質を利用して、ランレングス符号化により効率的な可変長符号化を行う。なお、ランレングス符号化するにあたり、各要素の符号化には、下記の表１のゴラム符号や、ハフマン符号、算術符号等いずれの可変長符号化を用いても構わない。【００７５】
【表１】
2007063612.tif 000003
具体的な可変長符号化部１４の動作例として、データソート部１３の説明で使用した図５の出力結果を可変長符号化する場合について説明する。また、説明のため、各要素の符号化には、表１のゴラム符号を用いる。なお、表１のゴラム符号を用いて符号化する場合、予め各要素値の出現確率が、要素値０の場合が最も高く、要素値が大きくなるにつれて出現確率が低くなるよう定めることで効率的な符号化が可能となる。【００７６】
データ列"2、2、2、2、0、0、0、0、0、0、0、2、1、1、1、1"を要素値、ラン長の繰り返しで表すと、"2、4、0、7、2、1、1、4"となる。これに対し表１の符号語を割り当てる。ただし、ラン長０は存在しないので、ラン長−１を要素値として符号語の割り当てを行うと、
"011、00100、1、00111、011、1、010、00100"となる。さらに、S0のソート結果の順位である０を表1に当てはめて符号化して、
"011、00100、1、00111、011、1、010、00100、１"の計２７ビットが可変長符号化部１４の出力となる。【００７７】
参考までに、従来技術と同様、図５における入力データ列S0＝"0、0、1、2、0、0、1、2、0、0、1、2、0、0、2、2"の各要素を個別に表１を用いて可変長符号化した場合、"1、1、010、011、1、1、010、011、1、1、010、011、1、1、011、011"の計３２ビットが必要であり、本実施形態の動画像符号化装置による可変長符号化の方が、５ビット符号化効率が良いことがわかる。【００７８】
また、出現する要素値を予測することで、さらなる符号化効率の改善が期待できる。【００７９】
例えば、予測を用いた符号化の手順は下記の通りである。【００８０】
STEP1)  予測値の候補列を、要素値の大きい順で初期化する。予測値の候補列は、先頭に近いほど出現確率が高く、最後尾に近いほど出現確率が低いことを示す。【００８１】
STEP2)  入力データ列の先頭要素値が、予測値の候補列の何番目に現れるかを検索する。【００８２】
STEP3)  検索して得られた予測値のインデックスとラン長-1を出力し、それぞれを可変長符号化する。【００８３】
STEP4)  予測値の候補列の先頭から、STEP2でえられた予測値のインデックスまでの予測候補を予測候補列の最後尾に移動する。【００８４】
STEP5)  入力データ列の全てのデータ列が符号化されるまでSTEP２〜４を繰り返す。【００８５】
図９は、上述の手順に従って、前述のデータ列"2、2、2、2、0、0、0、0、0、0、0、2、1、1、1、１"を符号化した場合の例であり、出力結果として、"1、00100、010、00111、1、1、1、00100"が得られている。これにS0のソート結果の順位である０の符号化結果を加えると、"1、00100、010、00111、1、1、1、00100、1"の計２３ビットとなり、前述の単純なランレングス符号化に比べても効率的な符号化が行われることがわかる。【００８６】
以上説明したように、本実施形態の動画像符号化装置では、マクロブロックあるいはサブマクロブロック間の相関を利用して、可変長符号化を行うことで、従来の動画像符号化装置に比べ符号化効率を高めることができる。【００８７】
〔実施形態２〕
次に、本発明の他の実施形態として、前記実施形態１の動画像符号化装置で符号化された符号化データを復号する動画像復号装置について説明する。【００８８】
図１０は、本実施形態の動画像復号装置を示すブロック図である。【００８９】
図１０において、符号１５は、符号化データを可変長復号する可変長符号復号部、符号１６は、可変長復号で得られた１次元データ列を所定の操作で並べ替え、マクロブロック毎のデータへ復元するデータ逆ソート部である。
なお、実施形態１の動画像符号化装置と同一機能を有するブロックについては、名称および符号を同一とし説明を省略する。【００９０】
次に、本実施形態の動画像復号装置の動作について、図１０に加え図１１の動作フローを参照しながら以下説明する。【００９１】
STEP1)  可変長符号復号部１５は、符号化データを可変長復号し、図１に示す動画像符号化装置においてデータソート部１３の出力状態の予測方式、予測パラメータ、予測残差データを復元する。可変長符号復号部１５の詳細については後述する(Ｓ１)。【００９２】
STEP2) データ逆ソート部１６は、可変長復号部１５から入力される１次元データ列(符号化情報)を所定の手順で２次元データ列に並べ替え、バッファメモリ１２に記録する（Ｓ２）。なお、バッファメモリ内記録されるデータ格納形式は、実施形態１の動画像符号化装置におけるバッファメモリ内のデータ格納形式と同一であり、データ逆ソート部１６の動作の詳細についても後述する。【００９３】
STEP3)   画面を構成する全てのマクロブロック群のデータが復元されるまでSTEP１〜2を繰り返す（Ｓ３）。【００９４】
STEP4)  逆量子化部７は、バッファメモリ１２から予測残差データを入力し、逆量子化を行う（Ｓ４）。【００９５】
STEP5)  逆変換部８は、逆量子化部７の出力する４ｘ４ブロックデータに対し逆直交変換を行う（Ｓ５）。【００９６】
STEP6)  マクロブロックを構成する全ての４ｘ４画素ブロックについて、STEP4〜5を繰り返す（Ｓ６）。
STEP7)  予測画像生成部３は、バッファメモリ１２から予測方式、予測パラメータを読み出し、フレームメモリ１に蓄積された復号済み画像を元に予測画像を生成する（Ｓ７）。
STEP8)  画像合成部９は、逆変換部８の出力データと予測画像生成部３で生成された予測画像を合成し、生成された画像を以降の復号に利用するためフレームメモリ１に蓄積すると共に、外部へ出力する（Ｓ８）。
STEP9)  画像を構成する全てのマクロブロックに対しSTEP４〜８を繰り返す（Ｓ９）。【００９７】
次に、上記可変長符号復号部１５について、詳細を説明する。【００９８】
可変長符号復号部１５の動作は、前述の実施形態１における可変長符号化部１４の逆の操作を行う。【００９９】
前述の単純ランレングスによる符号化が行われた符号化データを復号する場合は、入力符号化データ列"011、00100、1、00111、011、1、010、00100、１"を前述の表１に当てはめて、"2、3、0、6、2、0、1、3、0"が得られ、ランの復元、及び、S0の順位を分離して、データ列"2、2、2、2、0、0、0、0、0、0、0、2、1、1、1、1"、S0の順位：０を復号完了する。【０１００】
また、予測値を利用した符号化を行った場合は、次の手順で復号する。【０１０１】
STEP1)  予測値の候補列を符号化と同じく要素値の大きい順で初期化する。【０１０２】
STEP2)  予測値のインデックスおよびラン長を表１の符号割り当てに基づき復号する。【０１０３】
STEP3)  予測の候補列におけるSTEP2で得られた予測値のインデックスが指す値を要素値として復号する。【０１０４】
STEP4)  符号化と同様に予測値のインデックスに基づき予測の候補列を更新する。【０１０５】
STEP5)  全ての要素が復号されるまでSTEP1〜4を繰り返し。【０１０６】
STEP6)  S0の順位を表１の符号割り当てに基づき復号して復号を完了する。【０１０７】
次に、データ逆ソート部１６の動作について、前述のデータソート部の動作説明で用いた例（図５）を復元する場合について、図１２を参照しながら説明する。なお、データ逆ソート部１６には、図１２（a）に示すデータ列とＳ０の順位が入力されるものとして以下説明する。なお、この入力データは、前述のデータソート部の出力結果図５（e）と同一である。
STEP1)  図５（ｄ）におけるS0〜S15の最後尾の要素値は入力データ列を順位０〜１５の順に割り当てることで復元される（図１２（ｂ））。【０１０８】
また、図５（ｄ）におけるS0〜S15の先頭要素は、入力データ列を昇順に並べ替えることで得られる。なお、S0以外のS1〜S15がどの順位であるかはこの時点では不明である。【０１０９】
STEP2)  図１２（ｃ）におけるS0〜S15の最後尾の要素を上位の要素から（図の上から順に）e0、e1、…、e15とする。e0からe15まで順に同一要素値を持つS0〜S15の先頭要素を検索し、同一記号を割り当てる。なお、同一の要素値が複数存在する場合は、上位の要素に同一記号を割り当てる。【０１１０】
STEP3) S0〜S15の最後尾以外の要素を全て１つ後ろへシフトし、先頭に最後尾の要素を先頭に移動する（図１２（ｄ））。この操作によって、e0、e1、....、e15のそれぞれの要素に、どの要素が続くのかが判明する。【０１１１】
STEP4)  図１２（ｄ）で得た情報を基にS0の３番目〜１４番目の要素を決定する（図１２（ｅ））。【０１１２】
STEP5)  S0の各要素に割り当てた記号を対応する要素値に置き換える（図１２(f)）。【０１１３】
STEP6)  前記実施の形態１の動画像符号化装置で用いた走査パターンを用いて１次元データを逆に２次元データへ変換し、ＭｘＮマクロブロックにおける符号化情報の各要素値を復元し、バッファメモリ１２へ出力する（図１２（ｇ））。【０１１４】
以上説明した動作によって実施形態１の動画像符号化装置で生成した符号化データを復号することが可能である。【０１１５】
なお、上述の説明では、マクロブロックサイズおよびサブマクロブロックサイズとして、従来技術と同じサイズを用いたが、異なるサイズを用いた構成であってもかまわない。また、符号化情報の要素（予測方式、予測パラメータ、予測残差データ）毎にマクロブロック群のサイズが異なる構成であっても構わない。【０１１６】
また、本発明の動画像符号化方法は、画像を複数のブロックに分割し符号化する動画像符号化方法において、前記各ブロックの符号化にそれぞれ必要な符号化情報を一時的に記憶するステップと、前記ステップにおいて記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行うステップとを含むことを特徴としている。【０１１７】
前記符号化を行うステップは、前記一時的に記憶されたＭ×Ｎブロックの符号化情報を、所定の走査手順で走査して１次元データ列に変換するデータ列変換ステップと、変換後の１次元データ列から所定の規則で複数の１次元データ列を生成するデータ列生ステップと、生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替えステップと、並べ替えられた１次元データ列に対して可変長符号化を行う可変長符号化ステップとを有することを備えていることを特徴としている。【０１１８】
本発明の動画像復号方法は、前記動画像符号化方法によって符号化された動画像データを復号する動画像復号方法において、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号するステップを含んでいることを特徴としている。【０１１９】
本発明の動画像復号方法は、前記動画像符号化方法によって符号化された動画像データを復号する動画像復号方法において、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号する復号ステップを含み、前記復号ステップは、符号化された符号化情報を可変長復号する可変長復号ステップと、可変長復号された符号化情報から複数の１次元データ列を生成するデータ列生成ステップと、生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替えステップと、並べ替えられた１次元データ列を、Ｍ×Ｎブロックの符号化情報を走査して得られる１次元データ列に変換するデータ列変換ステップとを有することを特徴としている。【０１２０】
本発明は上述した各実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。【０１２１】
最後に、動画像符号化装置の各ブロック、特にデータソート部１３および可変長符号化部１４は、ハードウェアロジックによって構成してもよいし、次のようにＣＰＵを用いてソフトウェアによって実現してもよい。【０１２２】
すなわち、動画像符号化装置は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアである動画像符号化装置の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、上記動画像符号化装置に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによっても、達成可能である。【０１２３】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。【０１２４】
また、動画像符号化装置を通信ネットワークと接続可能に構成し、上記プログラムコードを通信ネットワークを介して供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【産業上の利用の可能性】
【０１２５】
高精細動画像データの高能率符号化が必要とされる装置、例えばＨＤＴＶ等の録画再生装置にも適用できる。
【図１】
2007063612.tif 000004
【図２】
2007063612.tif 000005
【図３（ａ）】
2007063612.tif 000006
【図３（ｂ）】
2007063612.tif 000007
【図３（ｃ）】
2007063612.tif 000008
【図３（ｄ）】
2007063612.tif 000009
【図３（ｅ）】
2007063612.tif 000010
【図３（ｆ）】
2007063612.tif 000011
【図３（ｇ）】
2007063612.tif 000012
【図４（ａ）】
2007063612.tif 000013
【図４（ｂ）】
2007063612.tif 000014
【図４（ｃ）】
2007063612.tif 000015
【図４（ｄ）】
2007063612.tif 000016
【図４（ｅ）】
2007063612.tif 000017
【図４（ｆ）】
2007063612.tif 000018
【図５】
2007063612.tif 000019
【図６（ａ）】
2007063612.tif 000020
【図６（ｂ）】
2007063612.tif 000021
【図６（ｃ）】
2007063612.tif 000022
【図６（ｄ）】
2007063612.tif 000023
【図６（ｅ）】
2007063612.tif 000024
【図６（ｆ）】
2007063612.tif 000025
【図６（ｇ）】
2007063612.tif 000026
【図７（ａ）】
2007063612.tif 000027
【図７（ｂ）】
2007063612.tif 000028
【図７（ｃ）】
2007063612.tif 000029
【図７（ｄ）】
2007063612.tif 000030
【図７（ｅ）】
2007063612.tif 000031
【図７（ｆ）】
2007063612.tif 000032
【図７（ｇ）】
2007063612.tif 000033
【図８】
2007063612.tif 000034
【図９】
2007063612.tif 000035
【図１０】
2007063612.tif 000036
【図１１】
2007063612.tif 000037
【図１２】
2007063612.tif 000038
【図１３】
2007063612.tif 000039
【図１４】
2007063612.tif 000040
【手続補正書】
【提出日】平成19年1月22日(2007.1.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（削除）
【請求項２】
画像を複数のブロックに分割し符号化する動画像符号化装置において、
前記各ブロックの符号化にそれぞれ必要な符号化情報を記憶する一時記憶手段と、
前記一時記憶手段に記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行う符号化手段とを備え、
前記符号化手段は、
前記一時記憶手段に記憶されたＭ×Ｎブロックの符号化情報を、所定の走査手順で走査して１次元データ列に変換するデータ列変換手段と、
変換後の１次元データ列から所定の規則で複数の１次元データ列を生成するデータ列生成手段と、
生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替え手段と、
並べ替えられた１次元データ列に対して可変長符号化を行う可変長符号化手段とを備えていることを特徴とする動画像符号化装置。
【請求項３】
前記データ列変換手段は、
前記符号化情報の種類毎に、異なる走査順序で１次元データ列への変換を行うことを特徴とする請求項２に記載の動画像符号化装置。
【請求項４】
前記データ並べ替え手段は、
ＢＷＴ（Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ  Ｔｒａｎｓｆｏｒｍ）を用いて、１次元データ列の並べ替えを行うことを特徴とする請求項２に記載の動画像符号化装置。
【請求項５】
前記データ並べ替え手段は、
符号化対象の空間解像度が所定の閾値未満の場合、Ｍ１×Ｎ１ブロック毎に前記１次元データ列の並べ替えを行い、
符号化対象の空間解像度が所定の閾値以上の場合、Ｍ２×Ｎ２ブロック毎に前記１次元データ列の並べ替えを行うとき、
ブロックサイズの関係がＭ１×Ｎ１＜Ｍ２×Ｎ２を満たすことを特徴とする請求項２に記載の動画像符号化装置。
【請求項６】
前記符号化情報は、符号化対象となる動画像に適用する予測方式を示すデータ、および当該予測方式と共に用いる予測パラメータ、および符号化対象となる動画像に当該予測方式を適用して求められる予測残差データのすくなくとも一つであることを特徴とする請求項２〜５の何れか１項に記載の動画像符号化装置。
【請求項７】
（削除）
【請求項８】
請求項２〜６の何れか１項に記載の動画像符号化装置によって符号化された動画像データを復号する動画像復号装置において、
Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号する復号手段を備え、
前記復号手段は、
符号化された符号化情報を可変長復号する可変長復号手段と、
可変長復号された符号化情報から複数の１次元データ列を生成するデータ列生成手段と、
生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替え手段と、
並べ替えられた１次元データ列を、Ｍ×Ｎブロックの符号化情報を走査して得られる１次元データ列に変換するデータ列変換手段と有することを特徴とする動画像復号装置。
【請求項９】
前記データ列変換手段は、前記符号化情報の種類毎に、異なる逆走査順序で１次元データ列に変換することを特徴とする請求項８に記載の動画像復号装置。
【請求項１０】
前記データ並べ替え手段は、逆ＢＷＴ（Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ  Ｔｒａｎｓｆｏｒｍ）を用いて１次元データ列の並べ替えを行うことを特徴とする請求項８に記載の動画像復号装置。
【請求項１１】
前記データ並べ替え手段は、
符号化対象の空間解像度が所定の閾値未満の場合、Ｍ１×Ｎ１ブロック毎に前記１次元データ列の並べ替えを行い、
符号化対象の空間解像度が所定の閾値以上の場合、Ｍ２×Ｎ２ブロック毎に前記１次元データ列の並べ替えを行うとき、
ブロックサイズの関係がＭ１×Ｎ１＜Ｍ２×Ｎ２を満たすことを特徴とする請求項８に記載の動画像復号装置。
【請求項１２】
前記符号化情報は、前記符号化情報は、符号化対象となる動画像に適用する予測方式を示すデータ、および当該予測方式と共に用いる予測パラメータ、および符号化対象となる動画像に当該予測方式を適用して求められる予測残差データのすくなくとも一つであることを特徴とする請求項８〜１１の何れか１項に記載の動画像復号装置。
【手続補正書】
【提出日】平成20年5月20日(2008.5.20)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像デ−タの高能率符号化技術を実現するための動画像符号化装置および動画像復号装置に関するものである。
【背景技術】
【０００２】
動画像データの高能率符号化を実現する従来技術としては、非特許文献１に記載のH.264/AVC動画像符号化技術が挙げられる。
【０００３】
上記H.264/AVC動画符号化技術を適用した動画像符号化装置について、図面を参照しながら説明する。
【０００４】
図１３は、従来技術の動画像符号化装置のブロック図である。
【０００５】
図１３において、符号１は、符号化済みの画像を蓄積するフレームメモリ、符号２は、符号化対象の画像に用いる予測方式および予測パラメータを決定する予測方式制御部、符号３は、フレームメモリ１に蓄積された符号化済み画像から予測画像を生成する予測画像生成部、符号４は、符号化対象の画像と予測画像の差分画像を生成する差分画像生成部、符号５は、差分画像を直交変換する直交変換部、符号６は、直交変換部５の出力データを量子化し予測残差データを出力する量子化部、符号７は、量子化部６と逆の操作によって入力データを逆量子化する逆量子化部、符号８は、直交変換部５と逆の操作によって入力データを逆直交変換する逆変換部、符号９は、逆変換部８の出力データと予測画像を合成する画像合成部、符号１０は、量子化部６の出力する２次元データをジグザグスキャンすることで１次元データ列に並べ替えるデータスキャン部、符号１１は、予測方式、予測パラメータ、及び、予測残差データを個々の要素別に可変長符号化する可変長符号化部である。
【０００６】
上記構成の動画像符号化装置の動作について、図１３に加え、図１４の動作フロー図を参照しながら説明する。なお、本動画像符号化装置は、画像を１６ｘ１６画素の矩形領域からなるマクロブロック毎に以下の処理を行うものとする。
【０００７】
STEP1)  予測方式制御部２は、符号化対象マクロブロックに用いる予測方式および予測パラメータを決定する（Ｓ１０１）。
【０００８】
ここで、予測方式は、画面内予測、画面間予測（前方予測、後方予測、双方向予測）のいずれか１つを選択する。
【０００９】
また、予測パラメータとして、予測を行う単位（マクロブロック分割パターン）、画面内予測の場合は、複数ある画面内予測方法のいずれを適用するか、画面間予測の場合は、動きベクトル、予測に用いる参照画像の組み合わせが決定される。なお、予測方式および予測パラメータの決定方法は、全ての予測方式および予測パラメータの組み合わせで予測画像を予測画像生成部３にて生成し、符号化対象となる画像との相関が最も高いものを用いることが望ましいが、処理量が膨大となるため、予め選択候補となる予測方式および予測パラメータを限定し、その候補内で最も相関の高い予測画像が得られた予測方式および予測パラメータを選択する方法であっても構わない。
【００１０】
STEP2)  可変長符号化部１１は、予測方式制御部２で決定した予測方式及び予測パラメータを要素別に可変長符号化する（Ｓ１０２）。
【００１１】
STEP3)  予測画像生成部３は、予測方式制御部２が決定した予測方式および予測パラメータに基づき当該マクロブロックの予測画像を生成する（Ｓ１０３）。
【００１２】
STEP4)  差分画像生成部４は、当該マクロブロックの画像と予測画像の差分画像を生成する（Ｓ１０４）。
【００１３】
STEP5)  直交変換部５は、当該マクロブロックの差分画像に対し、４ｘ４画素ブロック毎に直交変換を行う（Ｓ１０５）。
【００１４】
STEP6)  量子化部６は、直交変換部５の出力する４ｘ４ブロックデータに対し量子化を行う（Ｓ１０６）。
【００１５】
STEP7)  逆量子化部７は、量子化部６の出力する予測残差データに対し、逆量子化を行う（Ｓ１０７）。
【００１６】
STEP8)  逆変換部８は、逆量子化部７の出力する４ｘ４ブロックデータに対し逆直交変換を行う（Ｓ１０８）。
【００１７】
STEP9)  データスキャン部１０は、量子化部６が出力した予測残差データをジグザグスキャンし、１次元データ列へ並べ替える（Ｓ１０９）。
【００１８】
STEP10)  可変長符号化部１１は、１次元化された予測残差データの各要素を可変長符号化する（Ｓ１１０）。
【００１９】
STEP11)  マクロブロックを構成する全ての４ｘ４画素ブロックについてSTEP5〜10を繰り返す（Ｓ１１１）。
【００２０】
STEP12)  画像合成部９は、逆変換部８の出力データと予測画像生成部３で生成された予測画像を合成し、合成した画像を符号化し、符号化済の画像として以降の符号化に利用するためフレームメモリ１に蓄積する（Ｓ１１２）。
【００２１】
STEP13)  符号化対象の画像を構成する全てのマクロブロックについて、STEP1〜12を繰り返す（Ｓ１１３）。
【非特許文献１】ITU-T Recommendation H.264:"Advanced Video Coding for generic audiovisual services" (2003)
【発明の開示】
【発明が解決しようとする課題】
【００２２】
以上説明したように、従来の動画像符号化装置においては、１６ｘ１６画素の矩形領域からなるマクロブロックを処理単位として、符号化情報（予測方式、予測パラメータ、予測残差データ等）の符号化が行われる。マクロブロックサイズは、空間解像度の低い画像を符号化する場合も、空間解像度の高い画像を符号化する場合でも一定である。しかしながら、一般に空間解像度が高くなるほど、符号化対象となる画像の空間的な相関は高くなるため、符号化情報についても隣接マクロブロック間で高い相関を示す傾向がある。
【００２３】
したがって、従来の動画像符号化装置では、マクロブロックサイズよりも広い範囲で高い相関の現れるような高解像度の画像を符号化する場合では、広範囲での空間的な相関を活かした符号化を行うことができないといった問題が生じる。
【００２４】
本発明は、上記の問題点に鑑みなされたものであり、その目的は、マクロブロックサイズよりも広い範囲で高い相関の現れるような高解像度の画像を符号化する場合であっても、広範囲での空間的な相関を活かした符号化を行うことができる動画像符号化装置を提供することにある。
【課題を解決するための手段】
【００２５】
本発明に係る動画像符号化装置は、上記課題を解決するために、画像を複数のブロックに分割し符号化する動画像符号化装置において、前記各ブロックの符号化にそれぞれ必要な符号化情報を記憶する一時記憶手段と、前記一時記憶手段に記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行う符号化手段とを備えていることを特徴としている。
【００２６】
前記符号化手段は、具体的には、前記一時記憶手段に記憶されたＭ×Ｎブロックの符号化情報を、所定の走査手順で走査して１次元データ列に変換するデータ列変換手段と、変換後の１次元データ列から所定の規則で複数の１次元データ列を生成するデータ列生成手段と、生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替え手段と、並べ替えられた１次元データ列に対して可変長符号化を行う可変長符号化手段とを備えているのが好ましい。
【００２７】
また、前記データ列変換手段は、前記符号化情報の種類毎に、異なる走査順序で１次元データ列への変換を行ってもよい。
【００２８】
また、前記データ並べ替え手段は、BWT(Burrows-Wheeler Transform)を用いて、１次元データ列の並べ替えを行ってもよい。
【００２９】
前記データ並べ替え手段は、符号化対象の空間解像度が所定の閾値未満の場合、Ｍ１×Ｎ１ブロック毎に前記１次元データ列の並べ替えを行い、符号化対象の空間解像度が所定の閾値以上の場合、Ｍ２×Ｎ２ブロック毎に前記１次元データ列の並べ替えを行うとき、ブロックサイズの関係がＭ１×Ｎ１＜Ｍ２×Ｎ２を満たすようにしてもよい。
【００３０】
前記符号化情報は、符号化対象となる動画像に適用する予測方式を示すデータ、および当該予測方式と共に用いる予測パラメータ、および符号化対象となる動画像に当該予測方式を適用して求められる予測残差データのすくなくとも一つであることが望ましい。
【００３１】
本発明の動画像復号装置は、上記の課題を解決するために、前記動画像符号化装置によって符号化された動画像データを復号する動画像復号装置において、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号する復号手段を備えていることを特徴としている。
【００３２】
また、前記復号手段は、符号化された符号化情報を可変長復号する可変長復号手段と、可変長復号された符号化情報から複数の１次元データ列を生成するデータ列生成手段と、生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替え手段と、並べ替えられた１次元データ列を、Ｍ×Ｎブロックの符号化情報を走査して得られる１次元データ列に変換するデータ列変換手段とを有してもよい。
【００３３】
前記データ列変換手段は、前記符号化情報の種類毎に、異なる逆走査順序で１次元データ列に変換してもよい。
【００３４】
前記データ並べ替え手段は、逆BWT(Burrows-Wheeler Transform)を用いて１次元データ列の並べ替えを行ってもよい。
【００３５】
前記データ並べ替え手段は、符号化対象の空間解像度が所定の閾値未満の場合、Ｍ１×Ｎ１ブロック毎に前記１次元データ列の並べ替えを行い、符号化対象の空間解像度が所定の閾値以上の場合、Ｍ２×Ｎ２ブロック毎に前記１次元データ列の並べ替えを行うとき、ブロックサイズの関係がＭ１×Ｎ１＜Ｍ２×Ｎ２を満たすのが望ましい。
【００３６】
前記符号化情報は、符号化対象となる動画像に適用する予測方式を示すデータ、および当該予測方式と共に用いる予測パラメータ、および符号化対象となる動画像に当該予測方式を適用して求められる予測残差データのすくなくとも一つであることが望ましい。
【００３７】
本発明に係る動画像符号化装置は、以上のように、画像を複数のブロックに分割し符号化する動画像符号化装置において、前記各ブロックの符号化にそれぞれ必要な符号化情報を記憶する一時記憶手段と、前記一時記憶手段に記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行う符号化手段とを備えていることで、空間解像度の違いによる隣接ブロック間の相関の高さを考慮した符号化が可能となり、この結果、低解像度の画像から高解像度の画像まで幅広く符号化を行うことができるという効果を奏する。
【００３８】
また、本発明に係る動画像復号装置は、本発明に係る動画像符号化装置によって符号化された高効率の動画像符号化データを復号・再生することが可能である。
【発明を実施するための最良の形態】
【００３９】
〔実施形態１〕
本発明の第１の実施形態の動画像符号化装置について図面を参照しながら説明する。図１は本実施形態における動画像符号化装置のブロック図である。
【００４０】
図１において、符号１２は、複数マクロブロックの符号化情報（予測方式、予測パラメータ、予測残差データ）を一時保存するためのバッファメモリ、符号１３は、バッファメモリに記録された符号化情報(予測方式、予測パラメータ、予測残差データ)を所定の方法で並べ替えるデータソート部、符号１４は、データソート部１３の出力結果を可変長符号化する可変長符号化部である。上記データソート部１３および可変長符号化部１４によって、バッファメモリ１２に記憶された複数の符号化情報（予測方式、予測パラメータ、予測残差データ）に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行う符号化部（符号化手段）１００を構成している。
【００４１】
なお、従来技術の動画像符号化装置（図１３）と同一機能を有するブロックについては、名称および符号を同一とし説明を省略する。
【００４２】
上記構成の動画像符号化装置の動作の概要について図１に加え、図２の動作フロー図を参照して説明する。
【００４３】
STEP1)  予測方式制御部２は、符号化対象マクロブロックに用いる予測方式および予測パラメータを決定する（Ｓ１）。
【００４４】
予測方式および予測パラメータの決定方法については、従来技術の動画像符号化装置と同様であり、説明を省略する。なお、決定した予測方式および予測パラメータはバッファメモリ１２に記録される。
【００４５】
STEP2)  予測画像生成部３は、予測方式制御部２が決定した予測方式および予測パラメータに基づき当該マクロブロックの予測画像を生成する（Ｓ２）。
【００４６】
STEP3)  差分画像生成部４は、当該マクロブロックの画像と予測画像の差分画像を生成する（Ｓ３）。
【００４７】
STEP4)  直交変換部５は、当該マクロブロックの差分画像に対し、４ｘ４画素ブロック毎に直交変換を行う（Ｓ４）。
【００４８】
STEP5)  量子化部６は、直交変換部５の出力する４ｘ４ブロックデータに対し量子化を行う。出力される予測残差データは、バッファメモリ１２に記録される（Ｓ５）。
【００４９】
STEP6)  逆量子化部７は、量子化部６の出力する予測残差データに対し、逆量子化を行う（Ｓ６）。
【００５０】
STEP7)  逆変換部８は、逆量子化部７の出力する４ｘ４ブロックデータに対し逆直交変換を行う（Ｓ７）。
【００５１】
STEP8)  マクロブロックを構成する全ての４×４画素ブロックについて、STEP４〜７を繰り返す（Ｓ８）。
【００５２】
STEP9)  画像合成部９は、逆変換部８の出力データと予測画像生成部３で生成された予測画像を合成し、生成された画像を以降の符号化に利用するためフレームメモリ１に蓄積する（Ｓ９）。
【００５３】
STEP10)  符号化対象の画像を構成する全てのマクロブロックについて、STEP１〜9を繰り返す（Ｓ１０）。
【００５４】
STEP11)  データソート部１３は、Ｍ×Ｎマクロブロック（Ｍ，Ｎは所定の整数）からなるマクロブロック群を単位としてバッファメモリ１２に記録された予測方式、予測パラメータ、および予測残差データのそれぞれを所定の手順で並べ替える（Ｓ１１）。なお、データソート部１３の詳細については後述する。
【００５５】
STEP12)  可変長符号化部１４は、データソート部１３が出力する予測方式、予測パラメータおよび予測残差データのそれぞれをマクロブロック群単位で可変長符号化する（Ｓ１２）。なお、可変長符号化部１４の詳細についても後述する。
【００５６】
STEP13)  符号化対象の画像を構成する全てのマクロブロック群の符号化が終わるまで、STEP1〜12を繰り返す（Ｓ１３）。
【００５７】
以上の手順により、本実施形態の動画像符号化装置では動画像データの符号化が行われる。なお、上述の説明では、STEP１１、１２において、予測方式、予測パラメータ、及び予測残差データをマクロブロック群単位で並べ替え、それぞれ可変長符号化するとして説明したが、符号化情報の一部（例えば予測残差データ）は、データソート部１３を介さず、各マクロブロック毎にバッファメモリ１２から可変長符号化部１４へ入力し、従来技術と同様に、マクロブロック単位の符号化を行う構成であっても構わない。
【００５８】
次に、上記データソート部１３の詳細について説明する。
【００５９】
データソート部１３は、所定のマクロブロック群の入力データに対してBWT（Burrows-Wheeler Transform)を用いて、効率的な可変長符号化が可能なデータ列へ変換する。
【００６０】
BWTは、１次元データ列を対象とした変換であって、例えば、“0,1,0,1,0,1,…”というように繰り返し同じパターンが現れるデータ列を入力した場合、出力データ列では入力データ列に比べ、同一値を持つ要素が連続しやすいといった性質を備えた変換である。したがって、一連の同一値を持つ要素に対して一括して符号割り当て（例えばランレングス符号）を行うことで、効率的な可変長符号化を行うことが可能である。
【００６１】
予測方式のように１マクロブロックに対し１要素からなるデータを扱う場合、マクロブロック群を例えば図３（ａ）に示すような４×４マクロブロック（ＭＢ０〜ＭＢ１５）として処理するならば、図３（ｂ）〜図３（ｇ）に示すような走査パターンのいずれか１つを用いて、入力データを１次元データ列へ変換すれば、隣接マクロブロック間の相関によって繰り返し同じパターンが現れ易くなるため、BWTの適用によって出力データ列で同一値を持つ要素が連続し易くなり、効率の良い符号化が可能となる。
【００６２】
同様に、マクロブロック群を８×８マクロブロックとして処理するならば、図４（ａ）〜図４（ｆ）に示すような走査パターンのいずれか１つを用いれば、BWT後の出力データ列で、同一値を持つ要素が連続し易くなることが期待できる。
【００６３】
なお、隣接マクロブロック間での符号化情報の相関の強さは、符号化対象となる画像の空間解像度に応じて異なるため、データソート部１３の処理単位であるマクロブロック群のサイズおよび走査パターンは、予め複数の画像の符号化シミュレーションを行い、最も性能の良い組み合わせを用いることが望ましく、例えば、低解像度の画像を符号化する場合は、４ｘ４マクロブロックを処理するマクロブロック群とし、高解像度の画像を符号化する場合には、８ｘ８マクロブロックを処理するマクロブロック群とすれば、空間解像度の違いによる隣接マクロブロック間の相関の高さを考慮した効率的な符号化が可能である。また符号化情報の相関の高さは、符号化対象の画像毎でも異なるため、予め複数の組み合わせを用意し、画像に応じて符号化に使用する組み合わせを適応的に選択可能な構成としても構わない。また、符号化情報の要素（予測方式、予測パラメータ、予測残差データ）毎でも相関の強さが異なるため、符号化情報の要素毎にマクロブロック群のサイズ、走査パターンを用いる構成であっても構わない。
【００６４】
図５に具体的なデータソート部の動作例を示す。なお、図５（ａ）は、データソート部１３への入力データの例を示し、ここでは、４ｘ４マクロブロックのそれぞれに、要素値０〜２を持つデータが存在している例を示している。例えば、各要素値が予測方式を表し、０：前方予測、１：後方予測、２：画面内予測を示すものとする。
【００６５】
STEP1)  図５（ａ）に対し、前述の図３（ｂ）に示す走査パターンを適用すると、図５（ｂ）の１次元データ列S0が得られる。
【００６６】
STEP2)  S0の要素を１要素ごと左にシフトし、先頭要素を最後尾へ巡回させて、１次元データ列S1を生成する。同様の操作を繰り返して、S1〜S15を生成する（図５（ｃ））。
【００６７】
STEP3)  S0〜S15を下記の条件で昇順にソートする（図５（ｄ））。
【００６８】
２つの１次元データ列Sa:=Ea0、Ea1、Ea2、・・・、Ea15、Sb:=Eb0、Eb1、・・・、Eb15に対し、
条件１：Ea0 ＜ Eb0 ならばSa < Sb
条件２：Eai = Ebi （０≦ｉ＜ｉ＜ｊを満たす任意のｉ）、かつ、Eaj＜EbjならばSa＜Sb
STEP4)  ソートされたS0〜S15の最後尾の要素を順に出力データ列とし、復号に必要な付加情報としてソート結果におけるS0の順位を出力する（図５（e））。
【００６９】
以上の説明では、１マクロブロックに１要素からなるデータをデータソート部１３で扱う場合について説明したが、１マクロブロックに複数の要素が存在するデータについても同様に取り扱うことができる。
【００７０】
例えば、画面内予測における予測パラメータである予測方法は、１つのマクロブロックを図６（ａ）に示す例のように、４×４サブマクロブロック（B0〜B15）に分割したサブマクロブロック毎にデータが存在するが、マクロブロック単位での走査パターンと同様、隣接サブマクロブロック間の相関を考慮して、図６（ｂ）〜図６（ｇ）に示すようなパターンを用いればよい。
【００７１】
また、フレーム間予測の予測パラメータである動きベクトルや参照画像の指定のように、可変サイズのサブマクロブロック毎にパラメータが存在する場合も同様である。例えば、図７（ａ）に示すような可変サイズのサブマクロブロックB0〜B4が存在する場合、走査パターン自体は、固定サイズのサブブロックでの例（図６）と同様に定め、重複したサブマクロブロックを走査した場合、２度目以降の走査を無視すればよい。例えば、図７（ｂ）の走査パターンの場合であれば、B0、B1、B2、B3、B4を出力、図７（ｃ）の場合、B0、B4、B1、B2、B3を出力、図７（ｄ）の場合、B0、B1、B4、B3、B2を出力するといった具合である。
【００７２】
また、予測残差データの場合も、同様に隣接ブロック間の同一周波数成分に高い相関があると考えられることから、図８に示す例のように、４つの隣接ブロック（B0、B1、B4、B5)に存在する１６ｘ４要素の予測残差データの操作順序を図中の数値の順で示す通り、低周波成分から高周波成分に向かって走査し、同様の走査を残りのブロックにも適用すれば良い。
【００７３】
次に、可変長符号化部１４の詳細について説明する。本実施形態の可変長符号化部１４は、前述の通り、データソート部１３が出力するデータ列が同一値を持つ要素が連続し易い性質を利用して、ランレングス符号化により効率的な可変長符号化を行う。なお、ランレングス符号化するにあたり、各要素の符号化には、下記の表１のゴラム符号や、ハフマン符号、算術符号等いずれの可変長符号化を用いても構わない。
【００７４】
【表１】
2007063612.tif 000041
【００７５】
具体的な可変長符号化部１４の動作例として、データソート部１３の説明で使用した図５の出力結果を可変長符号化する場合について説明する。また、説明のため、各要素の符号化には、表１のゴラム符号を用いる。なお、表１のゴラム符号を用いて符号化する場合、予め各要素値の出現確率が、要素値０の場合が最も高く、要素値が大きくなるにつれて出現確率が低くなるよう定めることで効率的な符号化が可能となる。
【００７６】
データ列"2、2、2、2、0、0、0、0、0、0、0、2、1、1、1、0"を要素値、ラン長の繰り返しで表すと、"2、4、0、7、2、1、1、3、0、1"となる。これに対し表１の符号語を割り当てる。ただし、ラン長０は存在しないので、ラン長−１を要素値として符号語の割り当てを行うと、
"011、00100、1、00111、011、1、010、011、1、1"となる。さらに、S0のソート結果の順位である０を表1に当てはめて符号化して、
"011、00100、1、00111、011、1、010、011、1、1、１"の計２７ビットが可変長符号化部１４の出力となる。
【００７７】
参考までに、従来技術と同様、図５における入力データ列S0＝"0、0、1、2、0、0、1、2、0、0、1、2、0、0、2、2"の各要素を個別に表１を用いて可変長符号化した場合、"1、1、010、011、1、1、010、011、1、1、010、011、1、1、011、011"の計３２ビットが必要であり、本実施形態の動画像符号化装置による可変長符号化の方が、５ビット符号化効率が良いことがわかる。
【００７８】
また、出現する要素値を予測することで、さらなる符号化効率の改善が期待できる。
【００７９】
例えば、予測を用いた符号化の手順は下記の通りである。
【００８０】
STEP1)  予測値の候補列を、要素値の大きい順で初期化する。予測値の候補列は、先頭に近いほど出現確率が高く、最後尾に近いほど出現確率が低いことを示す。
【００８１】
STEP2)  入力データ列の先頭要素値が、予測値の候補列の何番目に現れるかを検索する。
【００８２】
STEP3)  検索して得られた予測値のインデックスとラン長-1を出力し、それぞれを可変長符号化する。
【００８３】
STEP4)  予測値の候補列の先頭から、STEP2でえられた予測値のインデックスまでの予測候補を予測候補列の最後尾に移動する。
【００８４】
STEP5)  入力データ列の全てのデータ列が符号化されるまでSTEP２〜４を繰り返す。
【００８５】
図９は、上述の手順に従って、前述のデータ列"2、2、2、2、0、0、0、0、0、0、0、2、1、1、1、0"を符号化した場合の例であり、出力結果として、"1、00100、010、00111、1、1、1、011、1、1"が得られている。これにS0のソート結果の順位である０の符号化結果を加えると、"1、00100、010、00111、1、1、1、011、1、1、1"の計２３ビットとなり、前述の単純なランレングス符号化に比べても効率的な符号化が行われることがわかる。
【００８６】
以上説明したように、本実施形態の動画像符号化装置では、マクロブロックあるいはサブマクロブロック間の相関を利用して、可変長符号化を行うことで、従来の動画像符号化装置に比べ符号化効率を高めることができる。
【００８７】
〔実施形態２〕
次に、本発明の他の実施形態として、前記実施形態１の動画像符号化装置で符号化された符号化データを復号する動画像復号装置について説明する。
【００８８】
図１０は、本実施形態の動画像復号装置を示すブロック図である。
【００８９】
図１０において、符号１５は、符号化データを可変長復号する可変長符号復号部、符号１６は、可変長復号で得られた１次元データ列を所定の操作で並べ替え、マクロブロック毎のデータへ復元するデータ逆ソート部である。
なお、実施形態１の動画像符号化装置と同一機能を有するブロックについては、名称および符号を同一とし説明を省略する。
【００９０】
次に、本実施形態の動画像復号装置の動作について、図１０に加え図１１の動作フローを参照しながら以下説明する。
【００９１】
STEP1)  可変長符号復号部１５は、符号化データを可変長復号し、図１に示す動画像符号化装置においてデータソート部１３の出力状態の予測方式、予測パラメータ、予測残差データを復元する。可変長符号復号部１５の詳細については後述する(Ｓ１)。
【００９２】
STEP2) データ逆ソート部１６は、可変長復号部１５から入力される１次元データ列(符号化情報)を所定の手順で２次元データ列に並べ替え、バッファメモリ１２に記録する（Ｓ２）。なお、バッファメモリ内記録されるデータ格納形式は、実施形態１の動画像符号化装置におけるバッファメモリ内のデータ格納形式と同一であり、データ逆ソート部１６の動作の詳細についても後述する。
【００９３】
STEP3)   画面を構成する全てのマクロブロック群のデータが復元されるまでSTEP１〜2を繰り返す（Ｓ３）。
【００９４】
STEP4)  逆量子化部７は、バッファメモリ１２から予測残差データを入力し、逆量子化を行う（Ｓ４）。
【００９５】
STEP5)  逆変換部８は、逆量子化部７の出力する４ｘ４ブロックデータに対し逆直交変換を行う（Ｓ５）。
【００９６】
STEP6)  マクロブロックを構成する全ての４ｘ４画素ブロックについて、STEP4〜5を繰り返す（Ｓ６）。
STEP7)  予測画像生成部３は、バッファメモリ１２から予測方式、予測パラメータを読み出し、フレームメモリ１に蓄積された復号済み画像を元に予測画像を生成する（Ｓ７）。
STEP8)  画像合成部９は、逆変換部８の出力データと予測画像生成部３で生成された予測画像を合成し、生成された画像を以降の復号に利用するためフレームメモリ１に蓄積すると共に、外部へ出力する（Ｓ８）。
STEP9)  画像を構成する全てのマクロブロックに対しSTEP４〜８を繰り返す（Ｓ９）。
【００９７】
次に、上記可変長符号復号部１５について、詳細を説明する。
【００９８】
可変長符号復号部１５の動作は、前述の実施形態１における可変長符号化部１４の逆の操作を行う。
【００９９】
前述の単純ランレングスによる符号化が行われた符号化データを復号する場合は、入力符号化データ列"011、00100、1、00111、011、1、010、011、1、1、１"を前述の表１に当てはめて、"2、3、0、6、2、0、1、3、0"が得られ、ランの復元、及び、S0の順位を分離して、データ列"2、2、2、2、0、0、0、0、0、0、0、2、1、1、1、0"、S0の順位：０を復号完了する。
【０１００】
また、予測値を利用した符号化を行った場合は、次の手順で復号する。
【０１０１】
STEP1)  予測値の候補列を符号化と同じく要素値の大きい順で初期化する。
【０１０２】
STEP2)  予測値のインデックスおよびラン長を表１の符号割り当てに基づき復号する。
【０１０３】
STEP3)  予測の候補列におけるSTEP2で得られた予測値のインデックスが指す値を要素値として復号する。
【０１０４】
STEP4)  符号化と同様に予測値のインデックスに基づき予測の候補列を更新する。
【０１０５】
STEP5)  全ての要素が復号されるまでSTEP1〜4を繰り返し。
【０１０６】
STEP6)  S0の順位を表１の符号割り当てに基づき復号して復号を完了する。
【０１０７】
次に、データ逆ソート部１６の動作について、前述のデータソート部の動作説明で用いた例（図５）を復元する場合について、図１２を参照しながら説明する。なお、データ逆ソート部１６には、図１２（a）に示すデータ列とＳ０の順位が入力されるものとして以下説明する。なお、この入力データは、前述のデータソート部の出力結果図５（e）と同一である。
STEP1)  図５（ｄ）におけるS0〜S15の最後尾の要素値は入力データ列を順位０〜１５の順に割り当てることで復元される（図１２（ｂ））。
【０１０８】
また、図５（ｄ）におけるS0〜S15の先頭要素は、入力データ列を昇順に並べ替えることで得られる。なお、S0以外のS1〜S15がどの順位であるかはこの時点では不明である。
【０１０９】
STEP2)  図１２（ｃ）におけるS0〜S15の最後尾の要素を上位の要素から（図の上から順に）e0、e1、…、e15とする。e0からe15まで順に同一要素値を持つS0〜S15の先頭要素を検索し、同一記号を割り当てる。なお、同一の要素値が複数存在する場合は、上位の要素に同一記号を割り当てる。
【０１１０】
STEP3) S0〜S15の最後尾以外の要素を全て１つ後ろへシフトし、先頭に最後尾の要素を先頭に移動する（図１２（ｄ））。この操作によって、e0、e1、....、e15のそれぞれの要素に、どの要素が続くのかが判明する。
【０１１１】
STEP4)  図１２（ｄ）で得た情報を基にS0の３番目〜１４番目の要素を決定する（図１２（ｅ））。
【０１１２】
STEP5)  S0の各要素に割り当てた記号を対応する要素値に置き換える（図１２(f)）。
【０１１３】
STEP6)  前記実施の形態１の動画像符号化装置で用いた走査パターンを用いて１次元データを逆に２次元データへ変換し、ＭｘＮマクロブロックにおける符号化情報の各要素値を復元し、バッファメモリ１２へ出力する（図１２（ｇ））。
【０１１４】
以上説明した動作によって実施形態１の動画像符号化装置で生成した符号化データを復号することが可能である。
【０１１５】
なお、上述の説明では、マクロブロックサイズおよびサブマクロブロックサイズとして、従来技術と同じサイズを用いたが、異なるサイズを用いた構成であってもかまわない。また、符号化情報の要素（予測方式、予測パラメータ、予測残差データ）毎にマクロブロック群のサイズが異なる構成であっても構わない。
【０１１６】
また、本発明の動画像符号化方法は、画像を複数のブロックに分割し符号化する動画像符号化方法において、前記各ブロックの符号化にそれぞれ必要な符号化情報を一時的に記憶するステップと、前記ステップにおいて記憶された複数の符号化情報に対して、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化を行うステップとを含むことを特徴としている。
【０１１７】
前記符号化を行うステップは、前記一時的に記憶されたＭ×Ｎブロックの符号化情報を、所定の走査手順で走査して１次元データ列に変換するデータ列変換ステップと、変換後の１次元データ列から所定の規則で複数の１次元データ列を生成するデータ列生ステップと、生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替えステップと、並べ替えられた１次元データ列に対して可変長符号化を行う可変長符号化ステップとを有することを備えていることを特徴としている。
【０１１８】
本発明の動画像復号方法は、前記動画像符号化方法によって符号化された動画像データを復号する動画像復号方法において、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号するステップを含んでいることを特徴としている。
【０１１９】
本発明の動画像復号方法は、前記動画像符号化方法によって符号化された動画像データを復号する動画像復号方法において、Ｍ×Ｎブロック（Ｍ，Ｎは任意の整数）を一単位として符号化された符号化情報を復号する復号ステップを含み、前記復号ステップは、符号化された符号化情報を可変長復号する可変長復号ステップと、可変長復号された符号化情報から複数の１次元データ列を生成するデータ列生成ステップと、生成した複数の１次元データ列を所定の並べ替え規則で並べ替えるデータ並べ替えステップと、並べ替えられた１次元データ列を、Ｍ×Ｎブロックの符号化情報を走査して得られる１次元データ列に変換するデータ列変換ステップとを有することを特徴としている。
【０１２０】
本発明は上述した各実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【０１２１】
最後に、動画像符号化装置の各ブロック、特にデータソート部１３および可変長符号化部１４は、ハードウェアロジックによって構成してもよいし、次のようにＣＰＵを用いてソフトウェアによって実現してもよい。
【０１２２】
すなわち、動画像符号化装置は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアである動画像符号化装置の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、上記動画像符号化装置に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによっても、達成可能である。
【０１２３】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【０１２４】
また、動画像符号化装置を通信ネットワークと接続可能に構成し、上記プログラムコードを通信ネットワークを介して供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【産業上の利用可能性】
【０１２５】
高精細動画像データの高能率符号化が必要とされる装置、例えばＨＤＴＶ等の録画再生装置にも適用できる。
【図面の簡単な説明】
【０１２６】
【図１】本発明の実施形態を示すものであり、動画像符号化装置の要部構成を示すブロック図である。
【図２】図１に示す動画像符号化装置による符号化処理の流れを示すフローチャートである。
【図３】（ａ）は４×４のマクロブロックの一例を示す図であり、（ｂ）〜（ｇ）は（ａ）で示したマクロブロックの走査パターンを示す図である。
【図４】（ａ）〜（ｆ）は８×８のマクロブロックの走査パターンを示す図である。
【図５】（ａ）〜（ｄ）は図１に示す動画像符号化装置に備えられたデータソート部によるデータソート処理の流れを示すフローチャートである。
【図６】（ａ）は４×４の固定サイズのマクロブロックの一例を示す図であり、（ｂ）〜（ｇ）は（ａ）で示したマクロブロックの走査パターンを示す図である。
【図７】（ａ）は可変サイズのマクロブロックの一例を示す図であり、（ｂ）〜（ｇ）は（ａ）で示したマクロブロックの走査パターンを示す図である。
【図８】予想残差データの走査パターンの例を示す図である。
【図９】図１に示す動画像符号化装置に備えられた可変長符号化部による可変長符号化方法の一例を示す図である。
【図１０】本発明の他の実施形態を示すものであり、動画像復号装置の要部構成を示すブロック図である。
【図１１】図１０に示す動画像復号装置の復号処理の流れを示すフローチャートである。
【図１２】（ａ）〜（ｇ）は図１０に示す動画像復号装置に備えられたデータ逆ソート部によるデータ逆ソート処理の流れを示す図である。
【図１３】従来の動画像符号化装置の要部構成を示すブロック図である。
【図１４】図１３に示す動画像符号化装置の符号化処理の流れを示すフローチャートである。
【符号の説明】
【０１２７】
１  フレームメモリ
２  予測方式制御部
３  予測画像生成部
４  差分画像生成部
５  直交変換部
６  量子化部
７  逆量子化部
８  逆変換部
９  画像合成部
１２  バッファメモリ（一時記憶手段）
１３  データソート部（データ並べ替え手段）
１４  可変長符号化部
１５  可変長符号復号部
１６  データ逆ソート部（データ並べ替え手段）
１００  符号化部（符号化手段）
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図５
【補正方法】変更
【補正の内容】
【図５】
2007063612.tif 000042
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図９
【補正方法】変更
【補正の内容】
【図９】
2007063612.tif 000043
【手続補正４】
【補正対象書類名】図面
【補正対象項目名】図１２
【補正方法】変更
【補正の内容】
【図１２】
2007063612.tif 000044
【国際調査報告】
2007063612.tif 000045
2007063612.tif 000046
2007063612.tif 000047
2007063612.tif 000048