(57)【要約】      （修正有）【課題】統計情報の更新処理を行い、Ｍ個のブロック内のデータの並べ替え処理を並列に実行する。【解決手段】第１のスキャン変換部１０１は、入力した２次元配列の変換係数を、スキャン順序更新部１０３に保持されたスキャン順序情報ScanOrder[]に従って読出し、並べ替え後の１次元配列のデータを出力する。統計情報更新部１０４は、並べ替え後のデータが有意係数であることの通知を受けると、該当する位置の統計情報ScanTotals[x]を更新する。そして、スキャン順序更新判定部１１３は、ScanTotals[x]が降順関係にないと判定したとき、ScanOrder[x-1]とScanOrder[x]、及び、ScanTotals[x-1]とScanTotals[x]とをそれぞれ交換させる。第２のスキャン変換部１０２は、第１のスキャン変換部１０１から、少なくとも２つ分だけ遅れて変換係数のスキャン変換を開始する。【選択図】図１
2010268243.tif 000002
【特許請求の範囲】
【請求項１】
２次元配列のＮ個のデータで構成されるブロック内をスキャンし、有意データを前方、非有意データを後方に偏るように１次元配列データに並べ替えるスキャン変換装置であって、
前記ブロック内の各データの位置を示す位置情報と、当該各データの位置における有意データとなる出現頻度を示す統計情報とをペアにして、前記統計情報について降順に並べられた並び替え情報を設定する設定手段と、
それぞれが、与えられたブロックを構成するＮ個のデータを、前記並べ替え情報における前記位置情報に従って該当するデータを順番に読出し、１次元配列データとして出力すると共に、読出したデータが有意データであるか否かを示す情報を出力する、互いに並列に実行が可能なＭ個（２≦Ｍ≦Ｎ／２）のスキャン変換手段と、
前記Ｍ個のスキャン変換手段のいずれかから、第ｉ番目のデータが有意データであることを示す情報が出力されたとき、前記第ｉ番目の位置に対応する統計情報を更新する統計情報更新手段と、
該統計情報更新手段による更新結果、更新対象となった統計情報と順位が１つ前の統計情報との関係が非降順関係となった場合、非降順関係になった統計情報を持つ２つの並び替え情報を交換する交換手段と、
前記Ｍ個のスキャン変換手段のそれぞれは、第１乃至第Ｍのスキャン変換手段として優先順位が割り当てられ、それぞれのスキャン変換手段を、それぞれより１つ順位が高いスキャン変換手段よりも、少なくとも２つのデータ分だけ遅いタイミングで、データのスキャンを開始させる制御手段と
を備えることを特徴とするスキャン変換装置。
【請求項２】
画像データを符号化する画像符号化装置であって、
画像をｎ行ｍ列より構成されるブロックの単位に分割する画像分割手段と、
前記画像分割手段より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換手段と、
前記直交変換手段により出力されるＭ個のブロックの変換係数を、並列に並び替える請求項１に記載のスキャン変換装置と、
前記スキャン変換装置より出力されるＭ個のブロックの変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化手段と
を有することを特徴とする画像符号化装置。
【請求項３】
２次元配列のＮ個のデータで構成されるブロック内をスキャンし、有意データを前方、非有意データを後方に偏るように１次元配列データに並べ替えるスキャン変換装置であって、
前記ブロック内の各データの位置を示す位置情報と、当該各データの位置における有意データとなる出現頻度を示す統計情報とをペアにして、前記統計情報について降順に並べられた並び替え情報を設定する設定手段と、
それぞれが、与えられたブロックを構成するＮ個のデータを、前記並べ替え情報における前記位置情報に従って該当するデータを順番に読出し、１次元配列データとして出力すると共に、読出したデータが有意データであるか否かを示す情報を出力する、互いに並列に実行が可能なＭ個（２≦Ｍ）のスキャン変換手段と、
前記Ｍ個のスキャン変換手段が並列に第ｉ番目のデータを並べ替えした際に、当該第ｉ番目のデータが有意データであることを示す情報を出力したスキャン変換手段の個数に対応して、前記第ｉ番目の位置に対応する統計情報を更新する統計情報更新手段と、
該統計情報更新手段による更新結果、更新対象となった統計情報と順位が１つ前の統計情報との関係が非降順関係となった場合、非降順関係になった統計情報を持つ２つの並び替え情報を交換する交換手段とを備え、
前記Ｍ個のスキャン変換手段のそれぞれは、第１乃至第Ｍのスキャン変換手段として優先順位が割り当てられ、それぞれのスキャン変換手段は、
第ｉ番目のデータを並べ替え行う際の直前のタイミングで並べ替えを行ったデータを保持する保持手段と、
第ｉ番目のデータが有意データであることを示す情報を出力した、自身より高い優先順位にあるスキャン変換手段の個数をＬ、第ｉ番目の統計情報をScanTotals[i]としたとき、『ScanTotals[i-1]≧ScanTotals[i]＋L』の関係を満たすか否かを判定する判定手段と、
該判定手段の判定結果が、『ScanTotals[i-1]≧ScanTotals[i]＋L』の関係を満たすことを示す場合、前記保持手段に保持されたデータを出力した後に、今回並べ替えられたデータを前記保持手段に保持させ、
前記判定手段の判定結果が、『ScanTotals[i-1]＜ScanTotals[i]＋L』であることを示す場合、今回並べ替えられたデータを出力する選択手段と
を備えることを特徴とするスキャン変換装置。
【請求項４】
画像データを符号化する画像符号化装置であって、
画像をｎ行ｍ列より構成されるブロックの単位に分割する画像分割手段と、
前記画像分割手段より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換手段と、
前記直交変換より出力されるＭ個のブロックの変換係数を、並列に並び替える請求項３に記載のスキャン変換装置と、
前記スキャン変換装置より出力されるＭ個のブロックの変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化手段と
を有することを特徴とする画像符号化装置。
【請求項５】
与えられたブロックを構成するＮ個のデータを、前記並べ替え情報における前記位置情報に従って該当するデータを順番に読出し、１次元配列データとして出力すると共に、読出したデータが有意データであるか否かを示す情報を出力する、互いに並列に実行が可能なＭ個（２≦Ｍ≦Ｎ／２）のスキャン変換手段を有し、２次元配列のＮ個のデータで構成されるＭ個のブロック内を並列に、有意データを前方、非有意データを後方に偏るように１次元配列データに並列に並べ替えるスキャン変換装置の制御方法であって、
設定手段が、前記ブロック内の各データの位置を示す位置情報と、当該各データの位置における有意データとなる出現頻度を示す統計情報とをペアにして、前記統計情報について降順に並べられた並び替え情報を設定する設定工程と、
統計情報更新手段が、前記Ｍ個のスキャン変換手段のいずれかから、第ｉ番目のデータが有意データであることを示す情報が出力されたとき、前記第ｉ番目の位置に対応する統計情報を更新する統計情報更新工程と、
交換手段が、該統計情報更新工程による更新結果、更新対象となった統計情報と順位が１つ前の統計情報との関係が非降順関係となった場合、非降順関係になった統計情報を持つ２つの並び替え情報を交換する交換工程と、
制御手段が、前記Ｍ個のスキャン変換手段のそれぞれは、第１乃至第Ｍのスキャン変換手段として優先順位が割り当てられ、それぞれのスキャン変換手段を、それぞれより１つ順位が高いスキャン変換手段よりも、少なくとも２つのデータ分だけ遅いタイミングで、データのスキャンを開始させる制御工程と
を備えることを特徴とするスキャン変換装置の制御方法。
【請求項６】
画像データを符号化する画像符号化装置の制御方法であって、
画像分割手段が、画像をｎ行ｍ列より構成されるブロックの単位に分割する画像分割工程と、
直交変換手段が、前記画像分割工程より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換工程と、
処理手段が、前記直交変換工程より出力されるＭ個のブロックの変換係数を、並列に並び替える請求項１に記載のスキャン変換装置に供給する処理工程と、
エントロピー符号化手段が、前記スキャン変換装置より出力されるＭ個のブロックの変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化工程と
を有することを特徴とする画像符号化装置の制御方法。
【請求項７】
与えられたブロックを構成するＮ個のデータを、前記並べ替え情報における前記位置情報に従って該当するデータを順番に読出し、１次元配列データとして出力すると共に、読出したデータが有意データであるか否かを示す情報を出力する、互いに並列に実行が可能なＭ個（２≦Ｍ）のスキャン変換手段を有し、２次元配列のＮ個のデータで構成されるＭ個のブロック内を並列に、有意データを前方、非有意データを後方に偏るように１次元配列データに並列に並べ替えるスキャン変換装置の制御方法であって、
設定手段が、前記ブロック内の各データの位置を示す位置情報と、当該各データの位置における有意データとなる出現頻度を示す統計情報とをペアにして、前記統計情報について降順に並べられた並び替え情報を設定する設定工程と、
統計情報更新手段が、前記Ｍ個のスキャン変換手段が並列に第ｉ番目のデータを並べ替えした際に、当該第ｉ番目のデータが有意データであることを示す情報を出力したスキャン変換手段の個数に対応して、前記第ｉ番目の位置に対応する統計情報を更新する統計情報更新工程と、
交換手段が、該統計情報更新工程による更新結果、更新対象となった統計情報と順位が１つ前の統計情報との関係が非降順関係となった場合、非降順関係になった統計情報を持つ２つの並び替え情報を交換する交換工程とを備え、
前記Ｍ個のスキャン変換手段のそれぞれは、第１乃至第Ｍのスキャン変換手段として優先順位が割り当てられ、それぞれのスキャン変換手段は、
第ｉ番目のデータを並べ替え行う際の直前のタイミングで並べ替えを行ったデータを保持する保持手段と、
第ｉ番目のデータが有意データであることを示す情報を出力した、自身より高い優先順位にあるスキャン変換手段の個数をＬ、第ｉ番目の統計情報をScanTotals[i]としたとき、『ScanTotals[i-1]≧ScanTotals[i]＋L』の関係を満たすか否かを判定する判定手段と、
該判定手段の判定結果が、『ScanTotals[i-1]≧ScanTotals[i]＋L』の関係を満たすことを示す場合、前記保持手段に保持されたデータを出力した後に、今回並べ替えられたデータを前記保持手段に保持させ、
前記判定手段の判定結果が、『ScanTotals[i-1]＜ScanTotals[i]＋L』であることを示す場合、今回並べ替えられたデータを出力する選択手段と
を備えることを特徴とするスキャン変換装置の制御方法。
【請求項８】
画像データを符号化する画像符号化装置の制御方法であって、
画像分割手段が、画像をｎ行ｍ列より構成されるブロックの単位に分割する画像分割工程と、
直交変換手段が、前記画像分割工程より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換工程と、
処理手段が、前記直交変換工程より出力されるＭ個のブロックの変換係数を、並列に並び替える請求項３に記載のスキャン変換装置に供給する処理工程と、
エントロピー符号化手段が、前記スキャン変換装置より出力されるＭ個のブロックの変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化工程と
を有することを特徴とする画像符号化装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スキャン変換装置及び画像符号化装置、並びにそれらの制御方法に関するものである。
【背景技術】
【０００２】
一般に、画像データは、多数の画素で構成される。そして、１つの画素が複数の色成分を持ち、尚且つ、１つの色成分は多ビットで表わされるものであるから、画像データのデータ量は非常に大きいものとなる。従って、そのデータを保存するため、或いは、短時間で転送するため、圧縮符号化技術は欠かせない。ここで、撮像素子などで撮影されたデジタル画像データの符号化手順を説明する。先ず、画像データは、所望の矩形サイズのタイルに分割される。そして、各タイルは、予め定められた２次元配列の複数のＭＢ（マクロブロック）に分割される。このＭＢが符号化処理の処理単位となる（図５参照）。
【０００３】
ＭＢデータは、直交変換が施され、色空間データから周波数空間の変換係数に変換される。非可逆符号化の場合には、更に圧縮率を高めるため、変換係数を量子化する。さらに、画像のデータパターンが複数ブロックにまたいでいる場合は、量子化された変換係数を各周波数帯に応じてフレーム内予測することで、更に変換係数の強度を削減する。ただし、量子化値がブロック内の係数位置によって異なっている場合やブロック間で異なっている場合は、画像のデータパターンが複数ブロックにまたいでいても、変換係数の周波数帯応じた相関が保たれているわけではない。そのため、フレーム内予測を施すことで必ずしも変換係数の強度を抑制することができるわけではない。このような場合は、フレーム内予測の処理を省いてもかまわない。そして、量子化、および、フレーム内予測が施された変換係数は２次元データとしてスキャンし、有意係数（有意データ）を前方に、非有意係数（非有意データ）、すなわち、ラン（零）を後方に連続するように１次元データとして並びかえる。このようにして並びかえた１次元データをエントロピー符号化することで符号化ストリームが生成される。また、このように生成された符号化ストリームに対して復号処理を施すことで、画像を再構成することも可能になる。
【０００４】
ＪＰＥＧ、ＭＰＥＧ２、ＭＰＥＧ４、ＪＰＥＧ−ＸＲなどに代表される画素ブロックを単位に符号化する一般的な画像符号化装置では、エントロピー符号化としてランレングス符号化を用いている。ランレングス符号化は、ランの連続する長さを符号化するものである。画像の符号化を行う場合、周波数変換後、或いは、その後の量子化後の２次元配列の変換係数を１次元の配列に変換し、その一次元配列に対してランレングス符号化を行う。従って、２次元配列から１次元配列に変換（スキャン変換）が適正であればあるほど符号化効率が高くなると言える。周波数変換の代表的なものとしてＤＣＴが知られている。このＤＣＴ変換による２次元配列である８×８個の変換係数のうち、左上隅の位置に１つのＤＣ成分値が得られる。そして、それ以外の６３個は交流成分であり、左上から右下に向かう順番に周波数が高い成分値が配置される。このような２次元配列の変換係数を１次元配列にするために有効とされているスキャン順が図３（ａ）に示すジグザグスキャンと呼ばれるものである（図示のマス目の番号が、そのスキャン順序を示しており、数字の順番の軌跡がジグザグであることからこのように呼ばれる）。
【０００５】
しかし、以下の３つの理由で「ジグザグ」パターンのような一定の走査パターンでは、符号化効率に必ずしも寄与するとは言えない。
【０００６】
第１の理由は、ブロック歪を抑制するため、ブロック間をまたいで変換を施す場合は、エッジが強調され、変換係数の分散が大きくなり、変換係数の強度も大きくなる点である。この場合、２次元配列の右下の変換係数の強度が必ずしも小さくなるとは限らない。そのため、ブロックの左上から右下へ変換係数をスキャンするスキャン順序が最適とは言えない。第２の理由は、ブロック内の画素に水平方向や垂直方向に依存関係がある場合は、依存関係に応じて変換係数の周波数帯が偏る傾向になる点である。このような場合においては、図３（ｂ）や図３（ｃ）に示されるような水平方向と垂直方向にそれぞれ異なるスキャン順序が適している。そして、第３の理由は、ブロックをまたいでテクスチャーが存在する場合、ブロック間で変換係数の偏りが同じ傾向になる点である。その場合は、量子化された変換係数に対して、係数予測を行うことで係数の強度を抑制できる。この場合は予測方法に応じて変換係数の周波数帯の偏りが変わる。そのため、予測方法に応じた走査パターンが必要となる。以上の理由から、入力画像と符号化方式に合った最適なスキャン順序を適応的に選択することが望ましいと言える(例えば、特許文献３参照)。
【０００７】
さらに、ＪＰＥＧ−ＸＲに代表されるように、ＭＢをさらにブロックに分割し、ブロック毎に量子化値やフレーム内予測方法が変更できる符号化方式においては、ブロック毎にスキャン順序を変更する方法が適している（例えば、特許文献１および特許文献２参照）。例えば、特許文献１に記載のスキャン順序決定方法によると、図４に示すように１６×１６画素で構成されたＭＢを４×４画素のブロックに分割する。そして、スキャン変換処理は、Ａ〜Ｐの順番で各ブロックの変換係数を読み込み、スキャン変換を行うものである。例えば、ブロックＡの変換係数全てが入力された後、予め定められたスキャン順序で並び替えて変換係数を出力する。一方、ブロックＡのスキャン変換結果を分析し、すなわち、並び替えた後のスキャン順序で変換係数を分析して、次のブロックＢのスキャン順序が決定される。このようにして、スキャン変換対象となるブロック以前に、スキャン変換が施されたブロックによって、当該ブロックのスキャン順序が因果的に決定される。
【０００８】
ここで、上記スキャン順序の詳細な決定方法の例を、図６のフローチャートに従って説明する。ここでは、配列変換対象の２次元配列が４×４個の変換係数であるものとする。
【０００９】
先ず、４×４個の変換係数のどの位置に有意係数が発生しやすいのかを統計的に求めた統計情報ScanTotals（例えば、図７（ａ））を用意する。なお、統計情報ScanTotalsの初期値として、{t*N, t*(N-1), t*(N-2),……,t}として設定されているものとする。一般にtは小さい整数(2 or 4)であるように選択される。また、tの値は、量子化で用いられる量子化パラメータによって決定されてもよい。そして、統計情報は、ある一定期間を置いてリセットすれば、統計情報の各要素の最大ビット長を固定することができる。ここで、この統計的に有意係数の発生しやすい順番を示すスキャンオーダ情報ScanOrder[]も用意する（図７（ｂ））。図７（ｂ）における小文字のアルファベットは、図４における小文字のアルファベットの位置である。図７（ａ），（ｂ）の場合、変換係数の位置“ｄ”が統計上、有意係数となる確率が高いことを示している。すなわち、同図（ａ），（ｂ）の場合、１次元配列に変換された最初の変換係数は位置“ｄ”の位置にある変換係数となる。
【００１０】
なお、図７（ａ），（ｂ）は、画像符号化側と画像復号側で共通になっていれば良いので、図示の数値はあくまでその例である。例えば、水平方向の係数予測がなされることを前提にする符号化装置に適用する場合には、水平方向を優先的に走査するスキャン順序となるスキャンオーダテーブルを用意すればよい（図３（ｂ）参照）。また、垂直方向の係数予測がなさることを前提にする符号化装置に適用する場合には、垂直方向を優先的に走査するスキャンオーダテーブルを用意すればよい（図３（ｃ））。
【００１１】
さて、S801において、スキャン変換を施されたブロック内の変換係数C[x](0≦x≦15)を１次元の順序で１つ取得する（初期の状態ではn=0）。次に、S802において、S801で取得した変換係数C[x]がラン（零）であるか否かを判定する。変換係数C[x]がランである場合は、S806の判定に進む。一方、変換係数C[n]が有意係数（非零）であった場合は、S803の処理を施す。処理がS803に処理が進んだ場合、有意係数であると判断された変換係数C[x]の統計情報ScanTotals[x]をインクリメントする。さらに、S804において、統計情報ScanTotals[x]とScanTotals[x-1]の大小関係を判定する。ScanTotals[x]がScanTotals[x-1]より大きい場合は、変換係数C[x]の位置では、変換係数C[x-1]の位置より有意係数の発生回数が多くなったことを意味する。そのため、S805において、スキャン順序に対応する係数の位置ScanOrderとそれに対応するScanTotalsに対して交換処理を施す。また、S803において、統計情報ScanTotals[x]がScanTotals[x-1]より小さい場合は、スキャン順序の変更処理は施さない。
【００１２】
ここで、S805の具体的な交換処理について説明する。交換処理では、係数位置ScanOrder[x]とScanOrder[x-1]を入れ替えるため、例えば下記のような演算を行う。
Temp = ScanOrder[x-1]
ScanOrder[x-1] = ScanOrder[x]
ScanOrder[x] = Temp
一方、統計情報ScanTotals[x]とScanTotals[x-1]とを入れ替えるため、例えば下記のような演算を行う。
Temp = ScanTotals[x-1]
ScanTotals[x-1] = ScanTotals[x]
ScanTotals[x] = Temp
【００１３】
S806で、次のブロックのスキャン順序を決定するために、ブロック内の変換係数の取得が完了していない場合は、S807へ進み、次の係数の取得に備える。一方、ブロック内の全係数の取得が完了していれば、スキャン順序決定フローを終了する。
【００１４】
以上で説明したように、スキャン順序ScanOrder[x-1]に対応する係数位置ScanOrder[x-1]を、スキャン順序xとx-1に対応する統計情報ScanTotals[x]とScanTotals[x-1]を用いて、因果的に決定している。これにより、スキャン変換を繰り返すと、段階的に最適なスキャン順序に近くづけることができる。また、因果的にスキャン順序を決定できることにより、スキャン順序を復号化処理装置に明示的に知らせる情報を符号化ストリームに付加する必要がなくなる。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００６−１９１６２８号公報
【特許文献２】特開平０７−０５０８３６号公報
【特許文献３】特開２００４−０３２７８８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、従来のスキャン順序決定方法では、スキャン変換を施すブロックを逐次的に処理せざるを得ず、１サイクル辺りに決定できるスキャン順序は１係数分のみだった。また、従来のスキャン順序決定方法では、１つのブロックのスキャン変換が完了しない限り、次のブロックのスキャン変換を開始できない。すなわち、同時に、複数のブロックのスキャン変換を行うことができない。
【００１７】
本発明はかかる点に鑑みなされたものであり、スキャン変換をより効率良く実行することを可能ならしめる技術を提供する。
【課題を解決するための手段】
【００１８】
この課題を解決するため、例えば本発明のスキャン変換装置は以下の構成を備える。すなわち、
２次元配列のＮ個のデータで構成されるブロック内をスキャンし、有意データを前方、非有意データを後方に偏るように１次元配列データに並べ替えるスキャン変換装置であって、
前記ブロック内の各データの位置を示す位置情報と、当該各データの位置における有意データとなる出現頻度を示す統計情報とをペアにして、前記統計情報について降順に並べられた並び替え情報を設定する設定手段と、
それぞれが、与えられたブロックを構成するＮ個のデータを、前記並べ替え情報における前記位置情報に従って該当するデータを順番に読出し、１次元配列データとして出力すると共に、読出したデータが有意データであるか否かを示す情報を出力する、互いに並列に実行が可能なＭ個（２≦Ｍ≦Ｎ／２）のスキャン変換手段と、
前記Ｍ個のスキャン変換手段のいずれかから、第ｉ番目のデータが有意データであることを示す情報が出力されたとき、前記第ｉ番目の位置に対応する統計情報を更新する統計情報更新手段と、
該統計情報更新手段による更新結果、更新対象となった統計情報と順位が１つ前の統計情報との関係が非降順関係となった場合、非降順関係になった統計情報を持つ２つの並び替え情報を交換する交換手段と、
前記Ｍ個のスキャン変換手段のそれぞれは、第１乃至第Ｍのスキャン変換手段として優先順位が割り当てられ、それぞれのスキャン変換手段を、それぞれより１つ順位が高いスキャン変換手段よりも、少なくとも２つのデータ分だけ遅いタイミングで、データのスキャンを開始させる制御手段とを備える。
【発明の効果】
【００１９】
本発明によれば、統計情報の更新処理を行うものの、実質的にＭ個のブロック内のデータの並べ替え処理を並列に実行することが可能になる。従って、ブロック単位にランレングスする画像符号化技術に適用した場合には、符号化処理を高速化させることが可能になる。
【図面の簡単な説明】
【００２０】
【図１】第１の実施形態におけるスキャン変換部のブロック構成図。
【図２】画像符号化部及び復号部のブロック構成図。
【図３】２次元配列データのスキャン順を表わすパターンを示す図。
【図４】ブロック内のデータの配列とマクロブロックとの関係を示す図。
【図５】画像、タイル、マクロブロックの関係を示す図。
【図６】ブロック内のスキャン順を決定するための処理のフローチャート。
【図７】統計情報とスキャン順序情報の例を示す図。
【図８】デジタルカメラのブロック構成図。
【図９】第２の実施形態におけるスキャン変換部のブロック構成図。
【図１０】図１のスキャン順序更新部と統計情報更新部のブロック図。
【図１１】図１の第１，第２の変換部のブロック図。
【図１２】第３の実施形態におけるスキャン変換部のブロック構成図。
【図１３】第３の実施形態のスキャン順序更新部のブロック構成図。
【図１４】第３の実施形態の統計情報更新部のブロック構成図。
【図１５】図１３における判定部の判定テーブルを示す図である。
【図１６】第１の実施形態における逆スキャン変換部のブロック構成図。
【発明を実施するための形態】
【００２１】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。
【００２２】
［第１の実施形態］
まず、本実施形態が産業上利用され得る形態として、画像を符号化する機能、符号化された画像を復号する機能を有する画像処理装置について説明する。画像を符号化する機能は、デジタルカメラやデジタルカムコーダが有する撮像素子から読み出された画像や、ネットワークを介して受信した画像を、符号化対象とする。
【００２３】
ここでは、図８の構成を有するデジタルカメラを例に説明する。撮像対象の像は、レンズ１２０１を介して、ＣＣＤやＣＭＯＳセンサなどの撮像素子１２０２上に結像される。撮像素子１２０２は、この結像された像をアナログ信号に変換し、このアナログ信号を後段のＡ／Ｄ変換器１２０３に送出する。
【００２４】
Ａ／Ｄ変換器１２０３は、撮像素子１２０２から受けたアナログ信号をデジタル信号に変換する。メモリ制御回路１２０７は、この変換されたデジタル信号をデータ（画像データ）としてＡ／Ｄ変換器１２０３から取得すると、この画像データを画像処理部１２０４に送出する。画像処理部１２０４は、この画像データに対して周知の画像補間処理や色変換処理などを施す。
【００２５】
メモリ制御回路１２０７は、画像処理部１２０４による処理後の画像データをこの画像処理部１２０４から取得すると、この取得した画像データをメモリ１２０５に格納する。メモリ１２０５は、撮像された静止画像や動画像のデータを一時的に格納するためのメモリであって、所定枚数の静止画像（所定フレーム数分の静止画像）を格納するための領域を有する。このメモリ１２０５は読み書き可能なメモリであるので、メモリ制御回路１２０７は、メモリ１２０５に対するデータ書込み専用の複数のメモリ制御部と、メモリ１２０５に対するデータ読出し専用の複数のメモリ制御部と、を有する。
【００２６】
メモリ１２０５に格納された画像データはメモリ制御回路１２０７によって再度読み出され、Ｄ／Ａ変換器１２０８と符号化部１２１１に送出される。Ｄ／Ａ変換器１２０８は、この画像データをアナログ信号に変換し、この変換したアナログ信号を画像表示部１２０９に送出する。これにより、画像表示部１２０９の表示画面上には、このアナログ信号が示す画像（撮像された画像）が表示される（再生される）ことになる。
【００２７】
一方で、符号化部１２１１は、メモリ制御回路１２０７から受けた画像データ（入力画像）から符号化ストリームを生成する。メモリ制御回路１２０７は、符号化部１２１１が生成した符号化ストリームを記憶媒体１２０６に記録する。記憶媒体１２０６には、ＳＤカード等の、画像処理装置に着脱可能なリムーバブルな媒体が利用される。
【００２８】
ここで、このデジタルカメラには、ユーザが操作する為のモードダイアル１２２１が備わっている。モードダイアル１２２１は、撮像モード、再生モードの何れかを選択するためのものである。ユーザがモードダイアル１２２１を操作して撮像モードを選択すると、システム制御部１２２０は画像処理装置を構成する各部の動作制御を行い、撮影処理が開始可能な状態になる。即ち、レンズ１２０１を介して得た像の画像データに基づく画像を画像表示部１２０９に表示させる。さらに、モードダイアル１２２１は撮影モードが選択された状態で、撮影記録スイッチ１２２２が投入されると、撮影処理が開始される。即ち、レンズ１２０１を介して得た像の画像データを符号化し、符号化ストリームとして記憶媒体１２０６に記録する処理を実現する。
【００２９】
一方、ユーザがモードダイアル１２２１を操作して再生モードを選択すると、システム制御部１２２０は画像処理装置を構成する各部の動作制御を行い、以下に説明する各処理を実現する。
【００３０】
メモリ制御回路１２０７は、記憶媒体１２０６に記録されている符号化ストリームを順次読み出し、読み出した符号化ストリームを復号部１２１３に送出する。復号部１２１３は、メモリ制御回路１２０７から受けた符号化ストリームを復号する。復号部１２１３には、復号された画像を１枚、ＲＯＭ１２２３には、画像処理装置の設定データや、システム制御部１２２０による実行対象のコンピュータプログラムが格納されている。更に、ＲＯＭ１２２３には、以下に説明する処理において既知のデータとして説明するものについても格納されている。即ち、システム制御部１２２０は、このＲＯＭ１２２３に格納されているコンピュータプログラムやデータを用いて処理を実行することで、デジタルカメラを構成する各部の動作制御を行う。これにより、本実施形態に係るデジタルカメラは、以下に説明する各処理を実現することになる。
【００３１】
［符号化部１２１１］
図２（ａ）は、符号化部１２１１の詳細な機能構成例を示すブロック図である。図２（ａ）に示した各部はハードウェアでもって構成されているものとするが、その一部、若しくは全部をコンピュータプログラムで実現しても良い。
【００３２】
符号化部１２１１に１枚の画像データが入力されると、タイル分割部２０１は入力した画像データを１以上のタイルに分割し、個々のタイルをＭＢ分割部２０２に出力する。ＭＢ分割部２０２は、入力した１つのタイルデータを、符号化処理単位となるマクロブロック（ＭＢ）に分割し、個々のマクロブロックＭＢを直交変換部２０３に出力する。この結果、直交変換部２０３以降の処理は、ＭＢ単位で処理が施される。以下では、１つのＭＢを符号化する為の符号化の動作について説明するが、同様の動作は、他のＭＢに対しても行われることになる点に注意されたい。
【００３３】
直行変換部２０３は入力したＭＢデータに対して直行変換を施し、色空間データから周波数空間の変換係数を出力する。さらに、色空間データへの非可逆符号化で良いのであれ、量子化部２０４において、変換係数を量子化処理して、変換係数のダイナミックレンジを小さくする。さらに、画像のデータパターンが複数ブロックにまたいでいる場合は、フレーム内予測部２０５において、量子化された変換係数を各周波数帯に応じてフレーム内予測することで、さらに変換係数の強度を削減する。ただし、量子化値がブロック内の係数位置によって異なっている場合やブロック間で異なっている場合は、画像のデータパターンが複数ブロックにまたいでいても、フレーム内予測の処理を省いてもかまわない。そして、量子化、および、フレーム内予測が施された変換係数は２次元データとしてスキャン変換部２０６に入力される。スキャン変換部２０６は、２次元の変換係数をスキャンして、その変換係数を符号化効率が高い１次元データに並べ替え、出力する。このときの理想的な並べ替えは、有意係数（有意データ）を前方に、非有意係数（ラン（零）＝非有意データ）を後方に連続するようにすることである。このようにして並びかえた１次元データをエントロピー符号化部２０７において、エントロピー符号化（ランレングス符号化）することで符号化ストリームが生成される。ここで、ブロック毎に量子化値やフレーム内予測方法が変更できる符号化方式においては、ブロック毎にスキャン順序を変更する方法が適している。従来技術にも記載したようなブロック毎にスキャン順序を決定して、スキャン返還を施す符号化部１２１１において、２つ以上のブロックを並列にスキャン変換を施すように半導体上に回路を構成する。この並列処理を可能にするスキャン変換に係る構成は後述することとする。
【００３４】
［復号部１２１３］
次に、復号部１２１３を図２（ｂ）を参照して説明する。なお、同図に示した各部はハードウェアでもって構成されているものとするが、その一部若しくは全部をコンピュータプログラムで実現しても良い。復号部１２１３には、画像毎の符号化ストリームが入力される。エントロピー復号部１１０７は、入力した符号化ストリームの符号語を復号し、予測変換係数誤差データを得る。復号された予測変換係数誤差データデータは、逆スキャン変換部１１０６において、逆スキャン変換を施し、１次元スキャン順序から２次元スキャン順序を変換する。次に、予測復号部１１０５において、予測変換係数誤差データに予測誤差を加算する、量子化変換係数を得る。その後、逆量子化部１１０４において、逆量子化を施し、逆直交変換部１１０３において、逆直交変換を施して、色空間データに復元する。以上の処理によってＭＢデータが復元できる。ＭＢ結合部１１０２は、各ＭＢデータを結合して１つのタイルを復元する。タイル結合部１１０１は、各タイルを結合し、画像に復元する。
【００３５】
以上の手順により、復号部１２１３は、符号化ストリームから画像を再構成し、再構成画像をメモリ制御回路１２０７へ送出する。なお、各復号部の処理については周知であるので、これ以上の説明は省略する。また、以下説明する実施形態は、上述した符号化部１２１１および復号部１２１３にあって、スキャン変換を並列処理する本発明を具体的に実施した場合の一例を示すものである。
【００３６】
［スキャン変換部の説明］
本第１の実施形態のスキャン変換部２０６は、複数（実施形態では２つ）のブロックの変換係数を同時に実行する。スキャン変換の対象となるデータは、先に説明したとおり、量子化されたブロック変換係数や予測符号化されたブロック（１ブロック＝４×４個の変換係数）である。そして、ブロック毎にスキャン順序が更新され、スキャン順序やスキャン順序の更新に伴う付加情報は因果的に決定される。
【００３７】
本第１の実施形態に係るスキャン変換部２０６は、図１に示すハードウェア構成図の如く、第１のスキャン変換部１０１、第２のスキャン変換部１０２、スキャン順序更新部１０３、統計情報更新記憶保持部１０４、及び、制御部１０５により構成される。また、第１のスキャン変換部１０１、第１変換部１１０、有意係数検出部１１２、スキャン順序更新判定部１１３を有する。そして、第２のスキャン変換部１０２は、第２変換部１２０、有意係数検出部１２２、スキャン順序更新判定部１２３を有する。
【００３８】
第１のスキャン変換部１０１は、入力されたブロックの変換係数に対してスキャン変換を施し、且つ、その変換したスキャン順序に基づいて次回のスキャン順序を更新する。第２のスキャン変換部１０２は、入力されたブロックの変換係数に対して、第１のスキャン変換部１０１が更新したスキャン順序に従ってスキャン変換を施し、且つ、その変換したスキャン順序に基づいて次回のスキャン変換を更新する。スキャン順序更新部１０３は、第１のスキャン変換部１０１および第２のスキャン変換部１０２から入力される判定結果を用いて、スキャン順序を更新して保持する。
【００３９】
統計情報更新部１０４は、第１のスキャン変換部１０１および第２のスキャン変換部１０２から入力される有意係数の検出結果を用いて、入力された変換係数のブロック内の各位置に対する有意係数の検出回数を集計して保持する。制御部１０５は、第２のスキャン変換部１０２における第２の変換部１２０の変換開始タイミングを制御する。第１の変換部１１０は、スキャン順序更新部１０３からのスキャン情報を用いて、入力ブロックデータに対してスキャン変換を施す。第２の変換部１２０は、制御部１０５から入力される制御信号にしたがい、スキャン順序更新部１０３からのスキャン情報を用いて、入力されたブロックの変換係数に対してスキャン変換を施す。有意係数検出部１２２は、有意係数（非零）を検出する。スキャン順序更新判定部１２３は、統計情報更新部１０４の統計結果を用いてスキャン順序を更新するか否かを判定する。
【００４０】
以下、図１におけるスキャン変換部２０６の更に詳しい処理内容を説明する。図４に示すように、予測符号化されたＭＢ内の変換係数は、ＭＢを４×４個のブロック、すなわち１６個のブロックに分割される。各ブロックは、Ａ〜Ｐに示す順序にスキャン変換を施される。本第１の実施形態では、２個のブロックに対して並列にスキャン変換を施すため、ＭＢを構成する１６個のブロックは、下記のような１組のセット（Ｘ、Ｙ）で順番に処理が施されるものとする。
（Ａ、Ｂ）→（Ｃ、Ｄ）→（Ｅ、Ｆ）→（Ｇ，Ｈ）→（Ｉ、Ｊ）→（Ｋ、Ｌ）→（Ｍ、Ｌ）→（Ｏ、Ｐ）
【００４１】
以降、上記セット（Ｘ、Ｙ）のうち、Ｘに相当するブロックを「ブロックＸ」、Ｙに相当するブロックを「ブロックＹ」と呼ぶこととする。本実施形態は、ブロックＸの変換係数と、ブロックＸのスキャン変換に用いられたスキャン順序から、ブロックＹのスキャン変換に用いるスキャン順序が決定される。ブロックＸの変換係数は、第１のスキャン変換部１０１に入力され、１次元データに並び替えられる。そこで、このブロックＸの２次元の変換係数を１次元に並び替える処理を図１１（ａ）を用いて説明する。
【００４２】
先ず、第１アドレス生成部１６０１は、変換係数記憶保持部１６０２に、予め設定された順番にアドレスと書き込み信号を出力することで、入力される２次元変換係数（実施形態では１５個であり、図４の英小文字ａ乃至ｏに対応する）を変換係数記憶保持部１６０２に記憶保持させる。その後、第１のアドレス生成部１６０１は、スキャン順序更新部１０３に保持されたスキャン順（図７（ｂ）参照）の１つScanOrder[1]を読出しては、その読出したScanOrder[1]に従い、変換係数記憶保持部１６０２に記憶された変換係数の１つを読出すためのリードアドレスを生成する。言い換えると、各ScanOrder[]は、変換係数記憶保持部１６０２の先頭アドレスに対するオフセットアドレスである。すなわち、第１アドレス生成部１６０１は、第１アドレス生成部１６０１の先頭アドレスに、読出したScanOrder[]で示されるオフセットアドレスを加算することで、リードアドレスを算出する。そして、第１のアドレス生成部１６０１は、この算出したリードアドレスを、変換係数記憶保持部１６０２に出力すると共に、リード信号をも出力する。この結果、変換係数記憶保持部１６０２は、記憶した変換係数の１つを１次元に変換された変換係数として出力することになる。次に、第１のアドレス生成部１６０１は、スキャン順序更新部１０３に保持された次のスキャン順（図７（ｂ）参照）であるScanOrder[2]を読出し、同様の処理を行う。以下、ScanOrder[15]に至るまで、第１のアドレス生成部１６０１はこの処理を繰り返す。以上の結果、例えば、スキャン順序更新部１０３に記憶されたスキャン順序が、図７（ｂ）のような状態であった場合、入力した２次元配列の変換係数をその順番に１次元配列の変換係数にして出力することになる。従って、ブロックＸの変換係数を効率的なエントロピー符号化が可能となる順序に並び替えることができる。
【００４３】
変換係数記憶保持部１６０２から送出された変換係数は、先に説明した通り、エントロピー符号化部２０７に供給されるが、ブロックＹのスキャン順序を決定するために、有意係数検出部１１２にも供給される。有意係数検出部１１２は、入力された変換係数の強度を分析する。そして、変換係数の強度が０(零)でない場合、即ち、着目変換係数が非ゼロの場合、その着目変換係数は有意係数と判断し、その判断結果（１ビットで良い）を統計情報更新部１０４に供給する。統計情報更新部１０４は、有意係数検出部１１２の検出結果を用いて、着目スキャン順位について、有意係数の発生頻度（出現頻度）の更新処理を行う。例えば、着目現在のスキャン順序をｘとすると、当該変換係数が有意係数であった場合は、図７（ａ）に示す統計情報ScanTotals[x]の値を“１”だけインクリメント（増加）する。また、着目変換係数が有意係数ではない（非有意係数＝ゼロ）であった場合、統計情報更新部１０４は、着目スキャン順位の統計情報テーブルScanTotals[x]の値を変更しない。着目変換係数が有意係数の場合は、統計情報更新部１０４は、更新対象となった着目スキャン順位の統計情報ScanTotals[x]と、その１つ前のスキャン順位の統計情報ScanTotals[x-1]をスキャン順序更新判定部１１３に供給する。着目変換係数が非有意係数の場合は、スキャン順序更新判定部１１３がスキャン順序の更新判定を行わないように、供給する統計情報ScanTotals[x]およびScanTotals[x-1]が無効であることをスキャン順序更新判定部１１３に通知する。あるいは、スキャン順序更新判定部１１３において、スキャン順序の更新判定を行わない場合と同じ結果が得られる統計情報ScanTotals[x]およびScanTotals[x-1]を供給する。
【００４４】
スキャン順序更新判定部１１３は、入力した統計情報ScanTotals[x]とScanTotals[x-1]とを比較する。そして、その比較結果が降順関係、すなわち、『ScanTotals[x-1]≧ScanTotals[x]』である場合、ブロックＸに適用される着目スキャン順位は、最適であると判断する。従って、スキャン順序更新判定部１１３はその時点でのスキャン順序ScanOrder[x-1]とScanOrder[x]の関係を維持する信号をスキャン順序更新部１０３に出力する。一方、『ScanTotals[x-1]＜ScanTotals[x]』であると判断した場合、統計情報ScanTotals[]がそこだけ非降順関係になっていることになる。それ故、スキャン順序更新判定部１１３は、ScanTotals[x-1]とScanTotals[x]の保持している値を交換する指示を統計情報更新部１０４に出力すると共に、スキャンオーダ情報ScanOrder[x-1]とScanOrder[x]とを交換する指示を、スキャン順序更新部１０３に出力する。この指示を受けた統計情報更新部１０４は、内部に保持するScanTotals[x-1]とScanTotals[x]の値を交換する。また、スキャン順序更新部１０３も、内部に保持するスキャンオーダ情報ScanOrder[x-1]とScanOrder[x]とを交換する処理を行う。以上説明した処理を、繰り返し処理することで、ブロックＸのスキャン変換が行われ、同時に、ブロックＹのスキャン順序を決定することができる。
【００４５】
ここで、ブロックＸにおける着目スキャン順位をxとした場合を考察する。この場合、着目スキャン順位ｘで示される変換係数が有意係数である場合のみ、ScanOrder[x]とその１つ前のスキャンオーダScanOrder[x-1]の交換処理が行われる可能性があると言える。換言すれば、着目スキャン順位をxとしたとき、ScanOrder[1]、ScanOrder[2]、…ScanOrder[x-2]は、ブロックＹのスキャン変換用として確定していると見なして構わない。そこで、本実施形態の制御部１０５は、第１スキャン部１０１によるブロックＸのスキャン変換を開始してから、ｘ番目の変換係数のスキャン変換を行うタイミングで、第２スキャン変換部１０２に対してｘ−２番目の変換係数のスキャンを行うように制御する。「ｘ−２」は１以上の値であるから、第１スキャン変換部１０１がブロックＸの３番目の変換係数のスキャン変換を行うタイミングで、制御部１０５は第２のスキャン変換部１０２にブロックＹの１番目の変換係数のスキャン変換を行なわせる。
【００４６】
以下、第２のスキャン変換部１０２の処理を説明する。第２のスキャン変換部１０２の第２の変換部１２０は、制御部１０５の制御の下で、入力したブロックＹの変換係数を、スキャン順序更新部１０３からのスキャンオーダ情報に従ってスキャン変換を施し、エントロピー符号化２０７に出力する。また、第２のスキャン変換部１０２内の有意係数位置検出部１２２、スキャン順序更新判定部１２３は、先に説明した有意係数検出部１１２及びスキャン順序更新判定部１１３と同様に、統計情報ScanTotals[]とスキャンオーダ情報を更新する。
【００４７】
第２の変換部１２０の構成と処理を図１１（ｂ）に従って説明する。変換係数記憶保持部１７０２は、２次元のブロックＹの変換係数（図４の英小文字ａ乃至ｏに対応する）を記憶保持する。そして、第２のアドレス生成部１７０１は、制御部１０５からの実行開始指示信号に応じて、スキャン順序更新部１０３に保持されたスキャン順（図７（ｂ）参照）の１つScanOrder[1]を読出しては、変換係数記憶保持部１７０２に記憶された変換係数の１つを読出すためのアドレスを生成する。そして、第２のアドレス生成部１７０１は、この発生したアドレスを、変換係数記憶保持部１７０２に出力すると共に、リード信号をも出力する。この結果、変換係数記憶保持部１７０２は、記憶した変換係数の１つを１次元に変換された変換係数として出力することになる。次に、第２のアドレス生成部１７０１は、スキャン順序更新部１０３に保持されたスキャン順（図７（ｂ）参照）の１つScanOrder[2]を読出し、同様の処理を行う。以下、ScanOrder[15]に至るまで、第２のアドレス生成部１７０１はこの処理を繰り返す。従って、ブロックＹの変換係数を効率的なエントロピー符号化が可能となる順序に並び替えることができる。こうして、第２のスキャン変換部１０２は、ブロックＹのスキャン変換を施すと同時に、次のタイミングにおけるブロックＸで用いるスキャン順序を決定することができる。また、スキャン順序更新部１０３、統計情報更新部１０４は、第１のスキャン変換部１０１によるスキャン変換結果を受けた処理と実質的に同じ処理を、第２のスキャン変換部１０２によって得られたスキャン変換に対しても実行する。従って、例えば、本実施形態のスキャン変換部２０６が、現在、ブロックのセット（Ａ，Ｂ）を処理している場合、第２のスキャン変換部１０２は、次のブロックのセット（Ｃ、Ｄ）のブロックＣが用いるスキャン順序を決定していることに他ならない。この場合、第１のスキャン変換部１０１がブロックＣに対する処理を開始するタイミングは、先に説明したように、第２のスキャン変換部１０２がスキャン変換中の変換係数の順位をｘとしたとき、それより２つ前のｘ−２を処理すればよい。
【００４８】
実施形態では、１ブロック分のScanTotalsとScanOrderを、２つのスキャン変換部１０１、１０２で共有している。より厳密には、２つのスキャン変換部１０１、１０２は、常に異なるスキャン順序を更新することで、１ブロックずつ逐次的にスキャン順序を更新した場合と等価のスキャン順序を得られるようにしている。そこで、以下では、統計情報更新部１０４とスキャン順序更新部１０３について説明する。
【００４９】
図１０（ａ）に、図１のスキャン順序更新部１０３の構成図の一例を示す。図１０（ａ）に示すように、スキャンオーダ情報ScanOrder[]はリングバッファ内に記憶保持している。まず、リングバッファを構成するラッチＤS１乃至ＤS１４には、初期値として図７（ｂ）に示したような初期のスキャン順序で初期化する。初期化時は、ScanOrder[0]がラッチＤS４に記憶保持され、ScanOrder[1]がラッチＤS５に記憶保持される。このようにして、各ScanOrderの要素が各ラッチに対応している。ちなみに、初期化時は、ScanOrder[14]がＤS０に対応し、ScanOrder[15]がＤS１に対応することになる。その後、サイクル毎に保持しているスキャン順序を前段のラッチに送出し、後段のラッチから入力されたスキャン順序を記憶保持する。このようにスキャン順序をバケツリレーすることで、第１，第２のスキャン変換部１０１、１０２は、常に固定ラッチから、１番目から順番にスキャン順序ScanOrderを得ることができる。
【００５０】
例えば、スキャン順序更新部１０３が、ラッチＤS４から第１のスキャン変換部１０１へスキャン順序ScanOrder[x+2]を送出しているときは、その２つ前段のラッチＤS2から第２のスキャン変換部１０２へスキャン順序ScanOrder[x]を送出する。
【００５１】
さらに、ラッチＤS４は、ブロックＸのスキャン順序を第１のスキャン変換部１０１へ送出しなければならない。同様に、ラッチＤS２は、ブロックＹのスキャン順序を第２のスキャン変換部１０２へ送出しなければならい。そこで、ラッチＤS４がブロックＸのScanOrder[x]を保持し、送出している際に、ScanOrder[x]とScanOrder[x-1]のスキャン順序の交換処理を行って、ブロックＹのScanOrder[x-1]を決定する。例えば、第１のスキャン変換部１０１のスキャン順序更新部１１３から入力される更新情報SwapXにしたがい、選択部１４０１、１４０２を用いて、ScanOrder[x]とScanOrder[x-1]のスキャン順序の交換処理を行う。これにより、ブロックＹのScanOrder[x-1]は、ラッチＤS２に記憶保持される。同様に、ラッチＤS2がブロックＹのScanOrder[x]を保持し、送出している際に、ScanOrder[x]とScanOrder[x-1]のスキャン順序の交換処理を行って、次のブロックＸのScanOrder[x-1]を決定する。例えば、第２のスキャン変換部１０２のスキャン順序更新判定部１２３から入力される更新情報SwapXにしたがい、選択部１４０３、１４０４を用いて、ScanOrder[x]とScanOrder[x-1]のスキャン順序の交換処理を行う。これにより、ブロックＹのScanOrder[x-1]は、ラッチＤS０に記憶保持される。以上の説明したように、スキャン順序更新部１０３が、ブロックＹのスキャン順序ScanOrder[x]を第２のスキャン変換部102へ送出しているときに、ブロックＸのスキャン順序ScanOrder[x+2] を第１のスキャン変換部101へ送出することが可能となる。
【００５２】
次に、統計情報更新部１０４の構成とその処理を図１０（ｂ）に従って説明する。この統計情報更新部１０４も、先に説明したスキャン順序更新部１０３と同様にリングバッファで構成され、ラッチＤT０乃至ＤT14に、統計情報ScanTotals[]が記憶保持される。ここでは、図１０（ａ）との差異についてのみ説明する。図１０（ｂ）のリングバッファを構成するラッチＤT０からＤT１４には、図７（ａ）に示したような値が初期値として設定される。統計情報ScanTotalsの各要素は、有意係数検出部１１２の検出結果によって、値がインクリメントされる。そのため、ラッチＤT４とＤT３の間には、ＤT４から送出されたブロックＸの統計情報ScanTotals[x]の値をインクリメントする加算器が備わっている。加算値が０であるか、あるいは、１であるかは、有意係数検出部１１２の検出結果によって決定されている。同様の理由で、ラッチＤT２とＤT１の間には、ラッチＤT２から送出されたブロックＹの統計情報ScanTotals[x]の値をインクリメントする加算器が備わっている。
【００５３】
以上の説明により、複数のブロックを並列にスキャン変換を施すスキャン変換装置において、第２のスキャン変換部１０２における並び替えたデータの出力タイミングを直接制御することで、因果的なスキャン順序更新方法を用いたスキャン変換の実施的に並列処理が可能である。
【００５４】
なお、従来技術で説明した図６に示すスキャン順序決定フローの各ステップと図１の構成要件の対応を下記に示す。有意係数検出部112は、S801およびS802に対応する。統計情報更新記憶保持部104は、S803に対応する。スキャン順序更新判断部113は、S804に対応する。スキャン順序更新記憶保持部103は、S805に対応する。また、本実施形態におけるスキャン変換部を複数のプロセッサに割り当て、タスクの開始タイミングを制御しても構わない。
【００５５】
以上、実施形態１におけるスキャン変換部２０６の構成とその動作を説明した。上記実施形態では、１つのブロック内のスキャン変換対象の２次元の変換係数の個数を４×４−１＝１５個とする例を説明した。そして、第１のスキャン変換部１０１がブロックＸ内の３つ目以降の変換係数のスキャン変換を行うときに、第２のスキャン変換部１０２がブロックＹの変換係数の１つ目の変換係数のスキャン変換を開始する。このような因果的なスキャン順序更新法を採用しながらも、常に２つのブロックのスキャン変換処理を並列に実行した。しかしながら、並列処理数が“２”に限定されるものではなく、３つ以上に拡張できる。今、並列数がｍの場合について説明する。この場合、第ｎ−１のスキャン変換部（１≦ｎ＜ｍ）が或るブロックの変換係数のスキャン変換を行って２つのデータ分だけ遅れたタイミングで第ｎのスキャン変換部が別のブロックの変換係数の１つ目の変換係数のスキャン変換を開始するようにすればよい。但し、第ｍ（最後）のスキャン変換部が或るブロックの変換係数のスキャン変換を行って３つ目以降の変換係数のスキャン変換を行うときに、第１のスキャン変換部が別のブロックの変換係数の１つ目の変換係数のスキャン変換を開始するようにする必要がある。すなわち、２次元の変換係数の個数がＭ個とした場合、スキャン変換の最大並列処理できる数は「Ｍ／２」となる。
【００５６】
［逆スキャン変換部の説明］
以下、復号装置における逆スキャン変換部１１０６について説明する。すなわち、実施形態における逆スキャン変換部１１０６は、１ブロック分の１次元配列データの２次元配列に戻す逆スキャン変換を、複数ブロックに対して並列に処理する。ここで、逆スキャン変換対象となるデータは、符号化されたビットスリームのエントロピー復号して得られたブロック変換係数である（図２（ｂ）参照）。そして、ブロック毎にスキャン順序が更新され、スキャン順序やスキャン順序の更新に伴う付加情報は因果的に決定される。
【００５７】
本実施形態に係る逆スキャン変換部１１０６の構成と処理内容を図１６に従って説明する。ここでは、説明を簡単にするため、２つのブロックの同時に逆スキャン変換を施す構成となっている。
【００５８】
逆スキャン変換部１１０６に入力される２つのブロックのセットは、スキャン変換部２０６と同じであり、図４におけるブロック（Ａ、Ｂ）→（Ｃ、Ｄ）→（Ｅ、Ｆ）→（Ｇ，Ｈ）→（Ｉ、Ｊ）→（Ｋ、Ｌ）→（Ｍ、Ｌ）→（Ｏ、Ｐ）の順である。ここでも、セット（Ｘ、Ｙ）のうち、Ｘに相当するブロックを「ブロックＸ」、Ｙに相当するブロックを「ブロックＹ」と呼ぶこととする。
【００５９】
本実施形態における逆スキャン変換部１１０６は、２つのブロックの２次元配列への変換を並列処理するものであるので、図１６の通り、第１の逆スキャン変換部２４０１、第２の逆スキャン変換部２４０２を有する。また、これら２つの逆変換部が共有するスキャン順序更新部１７３、統計情報更新部１７４と、第２の逆スキャン変換部２４０２の処理開始タイミングを制御する制御部１７６を有する。また、第１の逆スキャン変換部２４０１は、第１の変換部１５０、有意係数検出部１５２、スキャン順序更新判定部１５３を有する。そして、第２の逆スキャン変換部２４０２は、第２の変換部１６１、有意係数検出部１６２、スキャン順序更新判定部１６３を有する。
【００６０】
図示の通り、逆スキャン変換部１１０６の構成は、スキャン変換部２０６と実質的に同じ構成である。ただし、スキャン順序更新部１７３が記憶保持するScanOrder[]の意味がスキャン順序更新部１０３のそれとは逆になる。例えば、入力される１次元配列の先頭の変換係数を、ブロックＸの２次元配列の画素位置“ｄ”（図４参照）に配置させるための情報をScanOrder[1]として記憶保持する。ScanOrder[2]以降も同様である。
【００６１】
なお、統計情報更新部１７４に記憶するデータは、スキャン変換部２０６における統計情報更新部１０４と同じで良い。本実施形態の逆スキャン変換部１１０６の処理は、符号化装置側のスキャン変換部２０６のそれと実質的に同じである。すなわち、第１の逆スキャン変換部２４０１が入力した３つ目の変換係数を、２次元配列であるブロックＸ内に配置するとき、第２の逆スキャン変換部２４０２は入力した最初の変換係数の２次元配列であるブロックＹ内に配置する処理を開始する。以降、第２の逆スキャン変換部２４０２は、第１の逆スキャン変換部２４０１で確定したスキャン順に追従して処理を進めていく。なお、第１の変換部１５０、第２の変換部１６１は、内部に１５個の変換係数を格納するメモリを有し、１ブロック分の変換係数が格納された（逆スキャン）が完了したとき、予め設定された順、例えば、図３（ｄ）や図３（ｅ）の順に変換係数を出力する。
【００６２】
なお、上記は逆スキャン変換の並列処理数を“２”とする例であったが、符号化側のスキャン変換部２０６と同様の理由で、更に多くの並列数とすることもできる。２次元配列に変換させる対象の変換係数がＮ個とした場合、逆スキャン変換の最大並列処理数は「Ｎ／２」となる。
【００６３】
また、実施形態では、スキャン位置を示す位置情報ScanOrderと、統計情報ScanTotalsを別々に記憶管理するものとしたが、ScanOrder[i]と統計情報ScanTotals[i]は常にペアとして扱われるので、１つのメモリに記憶管理するようにしても構わない。すなわち、これらのペアを並び替え情報Inf[i]と定義したとき、Inf[i]={ScanOrder[i],ScanTotals[i]}(i=1,2,,,N)として記憶管理し、交換が必要になった場合には、Inf[j-1]とInf[j]が保持するデータを交換するようにしても、上記と等価のものと言える。
【００６４】
［第２の実施形態］
第２の実施形態に係るスキャン変換部２０６の構成と処理を図９に従って説明する。本第２の実施形態でも、スキャン変換処理の並列数は“２”の例である。図１と異なるのは、制御部１０５の無くなり、代わりに制御部１３０５、及び、スイッチ１３０１が追加された点である。それ以外は同じであり、その且つ同様の機能を有するものとして同符号を付し、その説明は省略する。
【００６５】
本第２の実施形態では、制御部１３０５がスイッチ１３０１を制御することで、第２のスキャン変換部１０２に供給される変換係数の入力タイミングを、第１のスキャン変換部１０１のそれより２つの変換係数分だけ遅らせるようにした。この結果、他の構成の処理は、第１の実施形態におけるスキャン変換部２０６と同じになる。なお、逆スキャン変換部１１０６も、図９と実質的に同様の構成になるのは、第１の実施形態の説明から容易に理解できよう。
【００６６】
［第３の実施形態］
上記の第１，第２の実施形態では、２つのスキャン変換部の一方が、他方のそれより２個の変換係数分だけ遅れてスキャン変換を行うものであった。本第３の実施形態では、２つのスキャン変換部の置換処理に時間差を無くし、その代わりに一方のスキャン変換部の出力タイミングを制御する例を図１２を用いて説明する。
【００６７】
本第３の実施形態のスキャン変換部２０６は、第１のスキャン変換部４０１、第２のスキャン変換部４０２、統計情報更新部４０３、スキャン順序更新部４０４を有する。統計情報更新部４０３は、各第１の変換部４０１の出力データから、スキャン順序に対応した有意係数の発生頻度を統計し、記憶保持する。さらに、スキャン順序更新部４０４は、第１のスキャン変換部４０１、第２のスキャン変換部４０２それぞれの有意係数検出部からの出力データと、統計情報更新部４０３の統計情報から、スキャン順序を更新して記憶保持する。また、スキャン順序の更新信号を統計情報更新部４０３に送出する。
【００６８】
第１のスキャン変換部４０１が有する第１の変換部１１０、有意係数検出部１１２、並びに、第２のスキャン変換部４０２が有する第２の変換部１２０、有意係数検出部１２２は、第１の実施形態と同じ機能を有数ものであるので、その説明は省略する。第２のスキャン変化部４０２は、更に保持部４１１と選択部４１２で構成される変換部４２１と、第１の判定部４２０を有する。
【００６９】
第１のスキャン変換部４０１における第１の変換部１１０は、スキャン順序更新部４０４から入力されたスキャン順序情報ScanOrder[]にしたがい、入力したブロックＸの変換係数を１次元配列に並べ替えて出力する。このとき、有意係数検出部１１２がスキャン変換された変換係数が有意係数であるか否かを検出し、検出結果を信号Ｓ１として出力する。
【００７０】
一方、第２のスキャン変換部４０２における第２の変換部１２０も、スキャン順序更新部４０４から入力されたスキャン順序情報ScanOrder[]にしたがい、入力したブロックＹの変換係数を１次元配列に並べ替えて出力する。但し、第２の変換部１２０から出力される変換係数の順序がただしくないことも起こり得る。そこで、第２のスキャン変換部４０２の第１の判定部４２０、交換部４２１により、第２の変換部１２０から出力された変換係数C[x]と１つ前に出力された変換係数C[x-1]を出力順のまま出力するのかを決定する。すなわち、C[x-1]を先に出力するのか、その逆にC[x]を先に出力するのかを決定する。
【００７１】
以下、図１２におけるスキャン変換部２０６の処理について説明する。なお、本第３の実施形態でも、並列処理する対象の２つのブロックのセットをブロック（Ｘ，Ｙ）とし、その入力順は第１の実施形態と同じであるものとして説明する。以下、ｎ番目の変換係数をスキャンするタイミングを＃ｎ（ｎ＝１、２、…１５）として表わすこととする。
【００７２】
第１のスキャン変換部４０１はブロックＸを入力し、第２のスキャン変換部４０２はブロックＹを入力し、それぞれがスキャン変換更新部４０４からのスキャン順序情報ScanOrder[]に従って、並べ替えを行なう。例えば、スキャン変換更新部４０４が保持するスキャン順序情報ScanOrder[]が図７（ｂ）の状態であったとする。このとき、第１のスキャン変換部４０１の第１変換部１１０はタイミング＃１にて、ブロックＸ内のScanOrder[1]で示される変換係数“ｄ”を読み込み、出力する。また、第２のスキャン変換部４０１の第２変換部１２０もタイミング＃１にて、ブロックＹ内のScanOrder[1]で示される変換係数“ｄ”を読み込み、出力するが、この段階では選択した変換係数“ｄ”は第２スキャン変換部４０２の外部には出力されず、保持部４１１に保持される。
【００７３】
次にタイミング＃２にて、第１のスキャン変換部４０１の第１変換部１１０はブロックＸ内のScanOrder[2]で示される変換係数“ａ”を読み込み、出力することになる。また、第２のスキャン変換部４０１の第２変換部１２０もタイミング＃２でブロックＹ内の変換係数“ａ”を読み込み、出力する。
【００７４】
ここで、仮に、タイミング＃２にて第１のスキャン変換部４０１から出力された変換係数“ａ”が非有意係数であったとする。この場合、信号Ｓ１は“０”となる。第１判定部４２０は、タイミング＃１で読み込んだScanTotals[1]を既に読み込んでいる。なお、タイミング＃１以前には変換係数が存在しないので、保持部４１１には何も記憶保持されていないと見なされる。そして、タイミング#2では、ScanTotals[2]を読み込んでいるが、信号Ｓ１が“０”であるので、統計情報更新部４０３にてScanTotals[2]が更新されない（インクリメントされない）ことがわかる。従って、第１の判定部４２０は、第１のスキャン変換部４０１によるブロックＸのタイミング＃２にけるスキャン処理を終えた時点で、少なくとも、『ScanTotals[1]≧ScanTotals[2]』の関係が維持されることを判定できる。従って、第１の判定部４２０は、交換不要（並べ替え不要）を示す信号を選択部４１２に出力する。選択部４１２はこの信号を受信すると、保持部４１１に保持された変換係数“ｄ”を選択して出力する。なお、変換係数“ｄ”を出力したとき、記憶保持部４１１には変換係数“ａ”が格納されることになる。
【００７５】
一方、タイミング＃２にて第１のスキャン変換部４０１から出力された変換係数“ａ”が有意係数であったとする。すなわち、信号Ｓ１が“１”であった場合である。このとき、第１判定部は、『ScanTotals[1]≧ScanTotals[2]＋１』を満たすか否かを判定する。そして、この関係を満たす場合、第１の判定部４２０は、交換不要（並べ替え不要）を示す信号を選択部４１２に出力する。選択部４１２はこの信号を受信すると、保持部４１１に保持された変換係数“ｄ”を選択して出力する。そして、記憶保持部４１１には新たに変換係数“ａ”が格納されることになる。
【００７６】
もし、タイミング＃２にて、信号Ｓ１が“１”となり、その結果、『ScanTotals[1]＜ScanTotals[2]＋１』となると判定した場合、第１の判定部４２０は、交換要（並べ替え要）を示す信号を選択部４１２に出力する。選択部４１２はこの信号を受信すると、タイミング＃２にて第２交換部１２０から出力された変換係数“ａ”を出力する。このとき、次のタイミング＃３に備えて、保持部４１１は変換係数”ｄ”が保持されている。
【００７７】
以上のように、同一タイミングにて、２つのスキャン変化部がブロックＸ、Ｙそれぞれの同じスキャン順序情報ScanOrser[]に従って並べ替えを行いながらも、第２のスキャン変換部４０２は、第１のスキャン変換部４０１の統計情報ScanTotals[]の更新結果に従った並べ替えを行うことが可能になる。
【００７８】
ここで、第３の実施形態における統計情報更新部４０３について説明する。統計情報更新部４０３は、変換係数のＩＤに対応して有意係数が発生するたびに更新する。２つのブロック、ブロックＸとブロックＹの両方のブロックの同じＩＤに有意係数が発生した場合は、ＩＤに対応する統計情報値ScanTotals[]に“２”を加算する。また、当該IDにおいて、ブロックＸ、または、ブロックＹのいずれか一方のブロックに有意係数が発生した場合は、当該IDに対応する統計情報ScanTotals[]に“１”を加算する。さらに、当該IDにおいて、ブロックＸ、および、ブロックＹのいずれにおいても有意係数が発生しなかった場合（ランであった場合）は、統計情報は更新されない。なお、当該IDを更新するために、図１４に示すようなリングバッファを用いると、計算リソースを少なくでき、逐次統計情報を第１の判定部へ出力することができる。その際、統計情報の加算値は、有意係数検出部のブロックＸの当該ＩＤに対応する検出結果Ｓ１と、有意係数検出部のブロックＹの当該ＩＤに対応する検出結果Ｓ２から決定される。
【００７９】
次に、スキャン順序更新部４０４について説明する。スキャン順序更新部４０４は、統計情報更新４０３の３つの統計情報値と、有意係数検出部１１２、１２２の検出結果Ｓ１、Ｓ２からスキャン順序ScanOrder[]を更新する。スキャン順序更新部４０４の構成例を図１３に示す。２つの比較部５０１、５０２、判定部５０３、スキャン順序記憶用バッファ、および、スキャン順序更新のための選択部５０４，５０５、５０６から構成される。スキャン順序記憶バッファは、図１３に示すようなリングバッファを用いると、回路構成リソースを少なくできる。また、固定ラッチの出力をスキャン変換時の出力データアドレスとして出力することができる。比較部５０１は、統計情報更新部４０３から入力された２つの統計情報を比較し、比較結果を出力する。この比較結果をCMP1とする。比較部５０１は、当該ＩＤに対応する統計情報ScanTotals[x]と、その１つ前の統計情報ScanTotals[x-1]を比較し、比較結果を出力する。例えば、ScanTotals[x]とScanTotals[x-1]が一致している場合は「１」を出力する。また、ScanTotals[x]がScanTotals[x-1]より小さい場合は「０」を出力する。さらに、ScanTotals[x]がScanTotals[x-1]より小さい場合は「２」を出力する。このようにして出力データをできるだけ少ないビットで表現することが望ましい。しかし、比較結果のビット表現は、本発明のかかるところではない。同様に、当該ＩＤの１つ前の統計情報値ScanTotals[x-1]と同２つ前の統計情報値SanTotals[x-2]についても、別の比較部５０２で比較する。この比較結果CMP2とする。図１５に示すように、有意係数検出信号Ｓ１、Ｓ２、および、比較結果CMP1、CMP2から、スキャン順序の交換操作は一意に決定される。例えば、S1=1,S2=1,CMP1=1 CMP2=1or2の場合は、ブロックXとブロックYの当該IDの係数がいずれも有意係数であり、統計情報値の状態の降順が崩れている状態（ScanTotals[x]==ScanTotals[x-1]、ScanTotals[x-1]≧ScanTotals[x-2]）である。そのため、有意係数の発生により、スキャン順序が更新され、当該IDのスキャン順序は２つ前になる。このようにして、有意係数検出信号S1、S2、および、比較結果CMP1、CMP2から、スキャン順序の交換操作は一意に決定される。なお。図１５において「！０」とあるのは、「０以外」という意味である。
【００８０】
上記を、より分かりやすく言えば、x番目のスキャン処理を行ってScanTotals[x]を更新した場合、先ず、ScanTotals[x-1]とScanTotals[x]に着目し、『ScanTotals[x-1]≧ScanTotals[x]』の関係にあるときは、交換処理は終了する。しかし、『ScanTotals[x-1]＜ScanTotals[x]』の関係にあるときは、ScanTotals[x-1]とScanTotals[x]、及び、ScanOrder[x-1]とScanOrder[x]の交換を行う。ついで、今度は、ScanTotals[x-2]とScanTotals[x-1]に着目して同様に処理して行けばよい。
【００８１】
従って、本第３の実施形態における並列数を一般形式のＭ個とするなら、次のようにすれば良いことがわかる。
【００８２】
先ず、Ｍ個のスキャン変換部には、第１乃至第Ｍのスキャン変換部というように優先順位を設定する。そして、各スキャン変換部は、
第ｉ番目のデータを並べ替え行う際の直前のタイミングで並べ替えを行ったデータを保持する保持部（保持部４１１に相当）と、
自身より高い優先順位にあるスキャン変換部中の、第ｉ番目のデータが有意データであることを示す情報を出力したスキャン変換部の個数Ｌをカウントする計数部（第３の実施形態では、並列数が２であり、第２のスキャン変換部よりも高い優先順位にあるのは第１のスキャン変換部の１つだけであるので、単純にＳ１が“０”か“１”かで良かった）と、
『ScanTotals[i-1]≧ScanTotals[i]＋L』の関係を満たすか否かを判定する判定部（第１の判定部４２０に相当）と、
この判定部の判定結果が、『ScanTotals[i-1]≧ScanTotals[i]＋L』の関係を満たすことを示す場合、前記保持部に保持されたデータを出力した後に、今回並べ替えられたデータを前記保持部に保持させ、判定部の判定結果が、『ScanTotals[i-1]＜ScanTotals[i]＋L』であることを示す場合には、今回並べ替えられたデータを出力した後に、保持部に保持されたデータを出力する選択部（選択部４１２に相当）を備えればよい。
【００８３】
このようにすると、本第３の実施形態はＭ個（２≦Ｍ）のスキャン変換部を並列に処理させることができる。
【００８４】
なお、先に説明した統計情報更新部４０３とスキャン順序更新部４０４の構成は、一例であり、本発明に限定されるものではない。また本実施形態ではスキャン変換を想定して説明した。逆スキャン変換の場合は、第２の実施形態と同様に、有意係数検出部の入力データは、変換部の入力データとなる。その他の処理部は、スキャン変換と同様の処理であるため、説明を省略する。
【００８５】
以上説明したように、本第３の実施形態により、入力タイミングに関係なく、出力タイミングを制御することで、スキャン順序が異なる複数のブロックを同時にスキャン変換を施すことが可能となる。
【００８６】
また、実施形態では、デジタルカメラに適用する例を説明したが、デジタルカメラに限定されないことは明らかであり、符号化部１２１１を単体の画像符号化装置としても構わないことも勿論である。
【００８７】
また、実施形態では１ブロックのサイズを４×４のサイズとしたが、これは一例であり、一般的にｎ行ｍ列にも適用できる。
【図１】
2010268243.tif 000003
【図２】
2010268243.tif 000004
【図３】
2010268243.tif 000005
【図４】
2010268243.tif 000006
【図５】
2010268243.tif 000007
【図６】
2010268243.tif 000008
【図７】
2010268243.tif 000009
【図８】
2010268243.tif 000010
【図９】
2010268243.tif 000011
【図１０】
2010268243.tif 000012
【図１１】
2010268243.tif 000013
【図１２】
2010268243.tif 000014
【図１３】
2010268243.tif 000015
【図１４】
2010268243.tif 000016
【図１５】
2010268243.tif 000017
【図１６】
2010268243.tif 000018