スキャン変換装置及び画像符号化装置、並びにそれらの制御方法
【課題】 ブロック毎にスキャン順序が変更されるスキャン変換処理を利用しながらも、スキャン変換処理を並列に実行できる場合には並列実行することで、単位時間当たりのスキャン変換するブロック数をこれまで以上にする。
【解決手段】 スキャン状態保持部１０３は、ブロック内の係数の出現頻度値に基づく統計情報を保持する。スキャンオーダ保持部１０２は、ブロック内の各係数位置をスキャン順序に並べた係数位置情報を保持する。並列処理判定部１０４は、スキャン状態保持部１０３に保持された統計情報に基づき、並列処理できるブロック数を決定し、その決定結果を制御信号としてスキャン変換部１０１に供給する。スキャン変換部１０１は、並列処理判定部１０４からの制御信号が並列処理を示す場合には、入力した２つのブロックのスキャン変換を並列に処理する。
【解決手段】 スキャン状態保持部１０３は、ブロック内の係数の出現頻度値に基づく統計情報を保持する。スキャンオーダ保持部１０２は、ブロック内の各係数位置をスキャン順序に並べた係数位置情報を保持する。並列処理判定部１０４は、スキャン状態保持部１０３に保持された統計情報に基づき、並列処理できるブロック数を決定し、その決定結果を制御信号としてスキャン変換部１０１に供給する。スキャン変換部１０１は、並列処理判定部１０４からの制御信号が並列処理を示す場合には、入力した２つのブロックのスキャン変換を並列に処理する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スキャン変換装置及び画像符号化装置、並びにそれらの制御方法に関するものである。
【背景技術】
【０００２】
画像データがデータ量が多く、そのままでは保存、送信に適さない。そこで、一般には、画像データを圧縮符号化することで、データ量を少なくすることが行われている。そこで、先ず、一般的な画像符号化装置について説明する。
【０００３】
撮像素子などで撮影されたデジタル入力画像は、所望の矩形サイズのタイルに分割される。さらに、各タイルは、予め定められた２次元のMB(マクロブロック)へとさらに分割される(図５参照)。MBのデータは直交変換が施され、色空間データから周波数空間の変換係数に変換される。
【０００４】
さらに必要に応じて、変換係数に対して量子化処理が施される。さらに、画像のデータパターンが複数ブロックにまたいでいる場合は、量子化された変換係数を各周波数帯に応じてフレーム内予測することで、更に変換係数の強度を削減する。ただし、量子化値がブロック内の係数位置によって異なっている場合やブロック間で異なっている場合は、画像のデータパターンが複数ブロックにまたいでいても、変換係数の周波数帯応じた相関が保たれているわけではない。そのため、フレーム内予測を施すことで必ずしも変換係数の強度を抑制することができるわけではない。このような場合は、フレーム内予測の処理を省いてもかまわない。
【０００５】
そして、量子化、および、フレーム内予測が施された２次元の変換係数は、有意係数を前方に、ラン(零)を後方に連続するように１次元データとして並びかえられる。このようにして並びかえた１次元データをエントロピー符号化することで符号化ストリームが生成される。
【０００６】
一方、上記のようにして生成された符号化ストリームは、その逆の手順で処理を施すことによって、画像に再構成される。
【０００７】
JPEG、MPEG2、MPEG4、JPEG-XRなどに代表される多くのブロック変換ベースの画像符号化装置では、エントロピー符号化にランレングス符号化を用いている。ランレングス符号化は、あるパターンに従って２次元の変換係数を１次元スキャンし、ランの連続する長さを符号化するものである。図３（ａ）はこのスキャンパターンの一例である。図示の番号順にスキャンするものであり、この番号順で示されるルートがジグザグであるので「ジグザグ」パターンと呼ばれる。しかし、以下３つの理由で「ジグザグ」パターンのような一定の走査パターンでは、符号化効率に寄与するとは必ずしも言えない。
【０００８】
第１の理由は、ブロック歪を抑制するため、ブロック間をまたいで変換を施す場合は、エッジが強調されるため、変換係数の分散が大きくなり、変換係数の強度も大きくなることである。この場合、低周波の変換係数(ブロックの右下の変換係数)の強度が必ずしも小さくなるとは限らない。そのため、ブロックの左上から右下へ変換係数をスキャンするスキャン順序が最適とは言えない。
【０００９】
第２の理由は、ブロック内の画素に水平方向や垂直方向に依存関係がある場合は、依存関係に応じて変換係数の周波数帯が偏る傾向にあることである。このような場合においては、図３（ｂ）や図３（ｃ）に示されるような水平方向と垂直方向にそれぞれ異なるスキャン順序が適している。
【００１０】
そして、第３の理由は、ブロックをまたいでテクスチャーが存在する場合、ブロック間で変換係数の偏りが同じ傾向にあることである。その場合は、量子化された変換係数に対して、係数予測を行うことで係数の強度を抑制できる。この場合は予測方法に応じて変換係数の周波数帯の偏りが変わる。そのため、予測方法に応じた走査パターンが必要となる。
【００１１】
以上の理由から、入力画像と符号化方式に合った最適なスキャン順序が選択することが望ましい（例えば、特許文献３）。
【００１２】
JPEG-XRに代表されるように、MBをさらにブロックに分割し、ブロック毎に量子化値やフレーム内予測方法が変更できる符号化方式においては、ブロック毎にスキャン順序を変更する方法が適している（例えば特許文献１、および、特許文献２）。
【００１３】
例えば、特許文献１に記載のスキャン順序決定方法によると、図４に示すように１６×１６画素で構成されたMBを、４×４画素のブロックに分割し、図示のＡ〜Ｐの順番で各ブロックのスキャン変換を行う。これによると、ブロックＡのスキャン変換結果を分析し、すなわち、並び替えた後の順序で係数を分析して、次のブロックＢのスキャン順序を決定する。同様に、ブロックＢのスキャン変換結果を分析し、すなわち、並び替えた後の順序で係数を分析して、次のブロックＣのスキャン順序を決定する。以下同様に、現在処理対象のブロックのスキャン変換結果に依存して、次のブロックのスキャン順序を決定する。ここで、上記のスキャン順序の決定方法について図６を用いて更に説明する。
【００１４】
先ず、S801において、スキャン変換を施されたブロック内の変換係数C[n](n≧0)を1次元の順序で1つ取得する。次に、S802において、S801で取得した係数C[n]がラン(零)であるか否かを判定する。変換係数C[n]がランである場合は、S804の判定に進む。一方、変換係数C[n]が有意係数(非零)であった場合は、S803の処理を施す。
【００１５】
そして、４×４ブロック内のどの位置に有意係数が発生したのかを統計した統計情報テーブルScanTotals(例えば、図７（ａ）参照)がある。図７（ａ）は、説明の都合上、スキャン順序に対応した４×４画素ブロック内の位置(例えば、図７（ｂ）に対応した統計情報テーブル値を示している。
【００１６】
尚、統計情報ScanTotalsの初期値として、以下のように設定される場合がある。
{t*N, t*(N-1), t*(N-2),……,t}
【００１７】
一般に、tは小さい整数(2 or 4)であるように選択される。tの値は、量子化で用いられる量子化パラメータによって決定されてもよい。そして、統計情報は、ある一定期間を置いてリセットすれば、統計情報の各要素の最大ビット長を固定することができる。
【００１８】
さらに、４×４画素ブロック内の係数の位置とスキャン順序の対応を示すテーブルScanOrderがある。スキャン順序に対応する係数の位置ScanOrderの初期順序は、画像符号化処理装置と画像復号化処理装置とで、因果的に決定されることが望ましい。例えば、水平方向の係数予測がなされた場合は、水平方向を優先的に走査するスキャン順序で初期化する(図３（ｂ）参照)。一方、垂直方向の係数予測がなされた場合は、垂直方向を優先的に走査するスキャン順序で初期化する(図３（ｃ）参照)。尚、水平方向性のスキャン順序は、特定の方向性を示さないブロックについても初期走査順序として使用してもよい。図４のa〜oは、４×４画素ブロック内の各係数の位置との対応を示している。図９（ｂ）は、図３（ｂ）に示す初期化された状態のスキャン順序テーブルScanOrderを図４のa〜oで示している。
【００１９】
さて、S803では、有意係数の場合は、この統計情報テーブルScanTotalsの当該要素の出現頻度値をインクリメント（増加）する。
【００２０】
さらに、S804において、統計情報ScanTotals[n]とScanTotals[n-1]の大小関係を判定する。ScanTotals[n]がScanTotals[n-1]より大きい場合は、変換係数C[n]の位置では、変換係数C[n-1]の位置より有意係数の発生回数が多いことを意味する。そのため、S805において、図10に示すようなスキャン順序に対応する係数の位置ScanOrderとそれに対応するScanTotalsに対して交換処理を施す。また、S802において、統計情報ScanTotals[n]がScanTotals[n-1]より小さい場合は、スキャン順序の変更処理は施さない。
【００２１】
ここで、S805の具体的な交換処理について説明する。交換処理では、係数位置ScanOrder[n]をScanOrder[n-1]に、ScanOrder[n-1]をScanOrder[n]に入れ替えるため、例えば下記のような演算を行う。
Temp = ScanOrder[n-1]
ScanOrder[n-1] = ScanOrder[n]
ScanOrder[n] = Temp
一方、統計情報ScanTotals[n]とScanTotals[n-1]とに、ScanTotals[n-1]をScanTotals[n]に入れ替えるため、例えば下記のような演算を行う。
Temp = ScanTotals[n-1]
ScanTotals[n-1] = ScanTotals[n]
ScanTotals[n] = Temp
【００２２】
S806で、スキャン順序決定のためにブロック内の変換係数の取得が完了していない場合は、S807へ進み、次の係数の取得に備える。一方、ブロック内の全係数の取得が完了していれば、スキャン順序決定フローを終了する。
【００２３】
以上で説明したように、スキャン順序n-1に対応する係数位置ScanOrder[n-1]を、スキャン順序nとn-1に対応する統計情報ScanTotals[n]とScanTotals[n-1]を用いて、因果的に決定している。これにより、段階的に最適なスキャン順序に近くづくことができる。さらに、因果的にスキャン順序を決定できるため、符号化装置から復号化装置にスキャン順序を明示的に知らせる情報を符号化ストリームに付加する必要がないというメリットがある。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】特開2006-191628号公報
【特許文献２】特開平07-050836号公報
【特許文献３】特開2004-032788号公報
【発明の概要】
【発明が解決しようとする課題】
【００２５】
上記のように、或るブロックの状態に応じて、後続するブロックのスキャン順序が決定するスキャン順序決定方法においては、ブロック毎にスキャン順序が変更され得る。このようなスキャン変換処理においては、複数のブロックのスキャン変換処理を同時に実行することが困難であるため、処理の高速化が十分に図れないという問題が残る。
【００２６】
本発明は、かかる問題を解決する技術を提供しようとするものであり、ブロック毎にスキャン順序が変更されるスキャン変換処理を利用しながらも、スキャン変換処理を並列に実行できる場合には並列実行することで、単位時間当たりのスキャン変換するブロック数をこれまで以上にする技術を提供しようとするものである。
【課題を解決するための手段】
【００２７】
かかる課題を解決するため、例えば本発明は以下の構成を備える。すなわち、
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える装置であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記スキャン状態保持手段に保持されたスキャン状態に応じて、N(Nは2以上の整数)個の前記ブロックのスキャン変換処理をM (Mは1以上N以下の整数) 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、スキャン変換装置。
【発明の効果】
【００２８】
本発明によれば、ブロック毎にスキャン順序が変更されるスキャン変換処理を利用しながらも、スキャン変換処理を並列に実行できる場合には並列実行することで、単位時間当たりのスキャン変換するブロック数をこれまで以上にすることができる。
【図面の簡単な説明】
【００２９】
【図１】第１の実施形態における並列スキャン変換部の構成図である。
【図２】本発明の画像符号化部のブロック構成図である。
【図３】スキャン順序の例を示す図である。
【図４】マクロブロックとブロックとの関係、及び、ブロック内の各データとその位置に割り当てた文字との対応関係を示す図である。
【図５】画像分割の説明するための図である。
【図６】スキャン順序決定処理のフローチャートである。
【図７】統計情報テーブルと係数位置テーブルを示す図である。
【図８】画像復号部の構成図を示す図である。
【図９】実施形態で適用するデジタルカメラの構成図である。
【図１０】第１の実施形態におけるスキャン変換部の構成図である。
【図１１】第１の実施形態におけるスキャンオーダ保持部の構成図である。
【図１２】第１の実施形態におけるスキャン状態保持部の構成図である。
【図１３】図１２のカウンタ1033の構成図である。
【図１４】第１の実施形態における並列処理判定部の構成図である。
【図１５】第１の実施形態における並列処理判定部の並列数判定処理のフローチャートである。
【図１６】第１の実施形態の動作タイミングチャートを示す図である。
【図１７】第１の実施形態の処理過程におけるスキャン順（係数位置）と統計情報の推移を示す図である。
【図１８】第２の実施形態における並列スキャン変換部の構成図である。
【図１９】第２の実施形態における並列処理判定部の構成図である。
【図２０】第２の実施形態における並列処理判定部の並列数判定処理のフローチャートである。
【図２１】第２の実施形態における有意データ位置情報生成部の構成図である。
【図２２】第２の実施形態の動作タイミングチャート
【図２３】第２の実施形態の処理過程におけるスキャン順（係数位置）と統計情報の推移を示す図である。
【発明を実施するための形態】
【００３０】
以下、添付図面に従って本発明に係る実施形態を説明する。なお、実施形態では、或るブロックの状態に応じて、後続するブロックのスキャン順序が決定するスキャン変換処理を行うスキャン変換装置を利用して、符号化を行う例として説明する。また、当該符号化にかかる構成が、デジタルカメラやデジタルカムコーダに搭載する圧縮システムの中で利用する例として説明する。しかしながら、スキャン変換装置や画像符号化装置がデジタルカメラやカムコーダに搭載されることに限定されるものではない。
【００３１】
図９は、本実施形態に係る画像処理装置としてのデジタルカメラのハードウェア構成例を示す図である。撮像対象の像は、レンズ1201を介して、CCDやCMOSセンサなどの撮像素子1202上に結像される。撮像素子1202は、この結像された像をアナログ信号に変換し、このアナログ信号を後段のA/D変換器1203に送出する。
【００３２】
A/D変換器1203は、撮像素子1202から受けたアナログ信号をデジタル信号に変換する。メモリ制御回路1207は、この変換されたデジタル信号をデータ(画像データ)としてA/D変換器1203から取得すると、この画像データを画像処理部1204に送出する。画像処理部1204は、この画像データに対して周知の画像補間処理や色変換処理などを施す。
【００３３】
メモリ制御回路1207は、画像処理部1204から、画像処理後の画像データを取得すると、この取得した画像データをメモリ1205に格納する。メモリ1205は、撮像された静止画像や動画像のデータを一時的に格納するためのメモリであって、所定枚数の静止画像(所定フレーム数分の静止画像)を格納するための領域を有する。このメモリ1205は読み書き可能なメモリであるので、メモリ制御回路1207は、メモリ1205に対するデータ書込み専用の複数のメモリ制御部と、メモリ1205に対するデータ読出し専用の複数のメモリ制御部と、を有する。
【００３４】
メモリ1205に格納された画像データはメモリ制御回路1207によって再度読み出され、D/A変換器1208と符号化部1211とに送出される。D/A変換器1208は、この画像データをアナログ信号に変換し、この変換したアナログ信号を画像表示部1209に送出する。これにより、画像表示部1209の表示画面上には、このアナログ信号が示す画像(撮像された画像)が表示される(再生される)ことになる。
【００３５】
一方で、符号化部1211は、メモリ制御回路1207から受けた画像データ(入力画像)から符号化ストリーム（符号化データ）を生成する。そして、メモリ制御回路1207は、符号化部1211が生成した符号化ストリームを記憶媒体1206にファイルとして記録する。記憶媒体1206には、SDカード等の、画像処理装置に着脱可能なリムーバブルな媒体が利用される。
【００３６】
ここで、このデジタルカメラには、各種スイッチやボタンが搭載されている。その中に、モードダイヤル1221が設けられている。モードダイヤル1221は、撮像モード、再生モードの何れかを選択するためのものである。ユーザがモードダイヤル1221を操作して撮像モードを選択すると、システム制御部1220はROM1223に格納されたプログラムに従い、本装置を構成する各処理部の動作制御を行い、上述した処理を実現する。即ち、レンズ1201を介して得た像の画像データに基づく画像を画像表示部1209に表示させると共に、この画像データを符号化し、符号化ストリームとして記憶媒体1206に記録する処理を実現する。
【００３７】
一方、ユーザがモードダイヤル1221を操作して再生モードを選択すると、システム制御部1220は画像処理装置を構成する各部の動作制御を行い、以下に説明する各処理を実現する。
【００３８】
メモリ制御回路1207は、記憶媒体1206に記録されている符号化データファイルから符号化ストリームを読み出し、読み出した符号化ストリームを復号化1213に送出する。復号部1213は、メモリ制御回路1207から受けた符号化ストリームを復号する。メモリ制御回路1207は、復号して得られた画像データを、D/A変換器1208に送出する。D/A変換器1208は、この画像データをアナログ信号に変換し、この変換したアナログ信号を画像表示部1209に送出する。これにより、画像表示部1209の表示画面上には、記憶媒体1206に格納された符号化画像データファイルが再生（表示）されることになる。
【００３９】
なお、ROM1223には、画像処理装置の設定データや、システム制御部1220による実行対象のコンピュータプログラムが格納されている。更に、ROM1223には、以下に説明する処理において既知のデータとして説明するものについても格納されている。即ち、システム制御部1220は、このROM1223に格納されているコンピュータプログラムやデータを用いて処理を実行することで、本装置を構成する各部の動作制御を行う。これにより、本実施形態に係る装置は、以下に説明する各処理を実現することになる。
【００４０】
次に、図２を用いて符号化部1211について説明する。図２は、符号化部1211の詳細な機能構成例を示すブロック図である。図２に示した各部はハードウェアで構成されているものとするが、その一部若しくは全部をコンピュータプログラムで実現しても良い。
【００４１】
図２において、タイル分割部201は、入力した１枚の画像データを分割する画像分割部として機能する。具体的には、タイル分割部201は入力した画像データを１以上のタイルに分割し、各タイルを順にMB分割部202に出力する。MB分割部202は入力した１つのタイルから、符号化処理単位である複数のMBに分割し、その分割したMBを直交変換部203に送出する。そのため、直交変換部203以降の処理は、MB単位で処理が施される。
【００４２】
以下では、１つのMBを符号化する為の符号化の動作について説明するが、同様の動作は、他のMBに対しても行われることになるし、１つのタイル内の全MBの処理が終わると、他のタイルについても同様の処理が行われる。
【００４３】
MBのデータは、直交変換部203で直交変換が施され、色空間データから周波数空間の変換係数に変換される。さらに、非可逆を許容するのであれば、量子化部204において、変換係数を量子化処理して解像度を落とし、データ量を削減する。さらに、画像のデータパターンが複数ブロックにまたいでいる場合は、フレーム内予測部205において、量子化された量子化変換係数（以下、単に変換係数）を各周波数帯に応じてフレーム内予測することで、さらに変換係数の強度を削減する。ただし、量子化値がブロック内の係数位置によって異なっている場合やブロック間で異なっている場合は、画像のデータパターンが複数ブロックにまたいでいても、フレーム内予測の処理を省いてもかまわない。
【００４４】
そして、量子化、および、フレーム内予測が施された変換係数は２次元データとして並列スキャン変換部206に入力される。並列スキャン変換部206は、２次元の変換係数をスキャンし、有意係数を前方に、ラン(零)を後方に連続するように１次元配列データとして並びかえる。このようにして並びかえた１次元データをエントロピー符号化部207において、エントロピー符号化（ランレングス符号化）することで符号化ストリームが生成される。
【００４５】
一方、図８は復号部1213のブロック構成図を示している。復号部1213は図示の如く、エントロピー復号部1107、並列逆スキャン変換部1106、係数予測部1105、逆量子化部1104、逆直交変換部1103、ＭＢ結合部1102、及び、タイル結合部1101を有する。ただし、これら処理部の処理内容は、図２に示した符号化部1211のそれの逆であるので、詳細に関しては説明を省略する。
【００４６】
ここで、ブロック毎に量子化値やフレーム内予測方法が変更できる符号化方式においては、ブロック毎にスキャン順序を変更する方法が適している。以下、高速化を図るために２つ以上のブロックを並列にスキャン変換を施すように、並列スキャン変換部206を実現するための２つの実施形態について、詳細に説明する。
【００４７】
［第１の実施形態］
図１に並列スキャン変換部206の構成を示す。この並列スキャン変換部206は、スキャン変換部101、スキャンオーダー保持部102、スキャン状態保持部103、及び、並列処理判定部104を有する。ここでは、説明を簡単なものとするため、スキャン変換部101は、２つのスキャン変換を並列して実行するものとしているが、それ以上であっても構わないのは以下の説明から明らかであろう。以下、図１を用いて並列スキャン変換部206について詳細に説明する。
【００４８】
スキャン変換部101は連続する２個のブロックデータ入力#1及び#2を受け取り、スキャン変換（並べ替え処理）を行なって、その変換データ出力#1及び#2として出力する。このスキャン変換部101は、入力したブロックデータ入力#1及び#2を、スキャンオーダ保持部102より受け取るスキャンオーダー情報に従ってスキャン変換を行う。そして並列処理判定部104より受け取る並列処理制御信号に従って変換データ出力#1のみを出力するか、または変換データ出力#1及び#2両方を出力する。
【００４９】
スキャンオーダー保持部102は、スキャン状態保持部103の出力する情報をもとに、必要に応じて先に説明した交換処理を行ない、スキャン順序を表すスキャンオーダー情報を生成して保持する。そして、スキャンオーダー保持部102は、生成したスキャンオーダ情報をスキャン変換部101と並列処理判定部104に出力する。スキャン状態保持部103は、ブロックデータ入力#1及び#2を受け取り、次のスキャン状態及びスキャン状態を生成して保持し、次のスキャン状態をスキャンオーダ保持部102へ、スキャン状態を並列処理判定部104へと出力する。
【００５０】
並列処理判定部104は、スキャン変換部101の動作を制御するスキャン制御部として機能する。具体的には、並列処理判定部104は、スキャンオーダ保持部102が出力するスキャンオーダー情報、及びスキャン状態保持部103が出力するスキャン状態を受け取る。そして、並列処理判定部104は、これらの情報を解析して並列処理制御信号を生成し、スキャン変換部101及びスキャン状態保持部103に制御信号を出力する。
【００５１】
次に、本実施形態における並列スキャン変換部206の処理内容を、図１６のタイミングチャート、図１７の状態説明図、及び、図１を用いて説明する。
【００５２】
図１６では、Term1〜5の各期間におけるブロックデータ入力から変換データ出力までの各部の状態の変化を示している。Term1において、ブロックデータ#1としてBlock Aが、ブロックデータ#2としてBlock Bが、スキャン変換部101及びスキャン状態保持部103に供給される。またTerm1では、スキャンオーダ保持部102の内部で保持されているスキャンオーダー情報、及び、スキャン状態保持部103の内部で保持されているスキャン状態は初期状態となっている。
【００５３】
本実施形態においては、スキャンオーダ保持部102内部で保持する初期のスキャンオーダー情報は図７（ｂ）に示される係数位置を表すものとするが、スキャンオーダー情報はスキャンの順序を特定できる表現であればよく、これに限定されるものではない。また同様に本実施形態ではスキャン状態保持部103内部で保持する初期のスキャン状態（初期の各係数の出現頻度値）は、図７（ａ）に示される統計的に求めた情報を表すものとするが、スキャン状態はスキャンの順序を決定するための情報であればよく、これに限定されるものではない。なお、図７（ａ）に示すように、統計情報は出現頻度値の順（降順）に並べられれている。また本実施形態では、当該スキャン順序及び統計情報は、図６に示される係数位置(ScanOrder)及び統計情報(ScanTotals)の決定方法に準じて決定されるものとするが、当該決定方法もこれに限定されるものではない。
【００５４】
図１７は、図１６のTerm1〜5の各期間における、スキャンオーダ保持部102内部で保持する係数位置データ、及び、スキャン状態保持部103内部で保持する統計情報、及び、ブロック入力#1及び#2の状態を表している。Term1において、係数位置及び統計情報は、図１７に示されるごとく初期化されている。ここへBlock A及びBが図１７に示される値で入力されたとする。図１７ではまた、入力されたブロック内の係数値のうち、有意係数(0以外の値を持つ係数)が現れたブロック内の位置に対応するところに、黒丸及び白丸でマーキングされているので、参考にされたい。黒丸はブロック入力#1の有意係数の位置に対応し、白丸はブロック入力#2の有意係数の位置に対応する。
【００５５】
Term1における統計情報の状態においては、ブロック内の何れの位置に有意係数が発生した場合でも、どのスキャン順序に対応する統計情報もそれより前の順序に対応する統計情報の値より大きくなることはない。そのため、Block A及びBはいずれも同一のスキャン順序でスキャン変換可能である。並列処理判定部104は、スキャンオーダ保持部102より出力される係数位置情報、及びスキャン状態保持部103より出力される統計情報より並列処理可能と判定し、並列処理指示を示す信号をスキャン変換部101へ出力する。
【００５６】
ここで並列処理判定部104の並列処理判定処理を図１５のフローに従って説明する。
【００５７】
処理が開始されると、処理S1041において変数nに2が代入される。次に処理S1042において、並列処理数を決定するためのPに最大並列処理数（実施形態では'2'）を設定する。この後、処理S1043にて、連続する２つの統計情報の差Dを算出する。
D=ScanToltls(n-1)-ScanToltls(n)+1
【００５８】
次に、判定処理S1044にて、値ＰとＤとを比較判定する。ここでＰ≦Ｄであると判定した場合には、２つのブロックのスキャン処理を行なったとしても、統計情報中のScanToltls(n-1)よりも、ScanToltls(n)が大きくなることは有り得ない。
【００５９】
一方、Ｐ＞Ｄの場合、２つのブロックのスキャン処理を行なった場合、その結果、統計情報内に、昇順となるデータが存在することことになるので、それを降順とする必要がある。すなわち、スキャン順を変更して、最大並列数を少なくする必要があるので、処理S1405にて、変数Pに変数Dの値を代入する。
【００６０】
この後、判定処理S1046にて、変数nが、ブロック内の係数の個数になったか否かを判定する。否の場合には、処理S1047にて、変数nの値をインクリメント（増加）し、処理S1043に戻る。なお、実施形態では、1ブロックが4x4画素のサイズであり、スキャン対象（並べ替え対象）はその中の1個のＤＣ成分を除く15個のＡＣ成分であるので、ブロック内のスキャン変換対象の係数の個数は'15'である。
【００６１】
さて、判定処理S1046にて、yesと判定されると、統計情報の全てについての検査を終えたことになるので、処理S1048に進む。処理S1048では、値Pは、交換処理が行われるまでの最も少ないブロック数、より具体的には、ブロック数Ｐのブロックのデータを並列してスキャン変換しても構わないことを意味する。従って、並列実行数をＰ個として決定できることになる。
【００６２】
なお、統計情報が図７(a)の初期状態の場合、連続する２つのScanToltls(n-1)とScanToltls(n)の差は'2'であるので、理論的に３つのスキャン変換処理を並列処理が可能である。しかし、実施形態では、図１に示すように、スキャン変換部101が実行可能な並列処理数が２つであるので、処理S1048ではP=2と判定されることになる。また、上記の説明からわかるように、図１５のフローチャートは、要するに、n=2,3,…,15について、ScanToltls(n-1)とScanToltls(n)の最小となる箇所とその差を求め、それによって並列処理数を求めている。
【００６３】
Term1の説明へと戻る。Term1において、スキャン変換部101は入力されたBlock A及びBを、スキャンオーダ保持部102より出力された係数位置情報及び並列処理判定部104より出力された並列制御信号に従って、スキャン順序の並び替えを行う。Term1では並列処理判定部104より出力された並列制御信号は並列処理を示しているので、Block A及びBはスキャンオーダ保持部102より出力された係数位置情報に従って、並列に、並び替え処理が行われる。
【００６４】
次に、Term2において、ブロックデータ#1としてBlock Cが、ブロックデータ#2としてBlock Dが、スキャン変換部101及びスキャン状態保持部103へと入力される。Term1において並列処理がなされ、かつ図１７で黒丸及び白丸で示された位置の係数が有意係数であったため、スキャン状態保持部103の位置の統計情報は図１７のTerm2に示されたような値に更新される。またスキャンオーダ保持部102では、Block A及びBの入力による係数位置の入れ替えは起きないため、Term2においても変更されない。並列処理判定部104は、スキャンオーダ保持部102より出力される係数位置情報及びスキャン状態保持部103より出力される統計情報に基づいて図15に示されたフローに従って並列処理すを決定し、それを制御信号としてスキャン変換部101及びスキャン状態保持部103へと出力する。Term2においては、図１７のTerm2に示されるようにスキャン順序が入れ替わる可能性のある個所が存在するため、並列処理判定部104は逐次処理を示す並列制御信号を出力する。また同じくTerm2においてスキャン状態保持部103では、並列制御信号が逐次処理を示しているので、次の統計情報として、現在保持中の統計情報に対しBlock C入力の有意係数に対応する情報のみ更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock C入力の有意係数に対応する位置は、図１７のTerm2の黒丸で示されている。スキャンオーダ保持部102では、スキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term2においてスキャン変換部101では、Term1において行ったBlock A及びBのスキャン変換処理の結果を、変換データ出力#1及び#2として出力する。また並列処理判定部104より出力された並列制御信号は逐次処理を示しているので、スキャン変換部101はBlock Cのみを、スキャンオーダ保持部102より出力された係数位置情報に従って並び替える。
【００６５】
次にTerm3において、ブロックデータ#1としてBlock Dが、ブロックデータ#2としてBlock Eが、スキャン変換部101及びスキャン状態保持部103へと入力される。スキャン状態保持部103では、Term2において逐次処理がなされ、かつ図１７の中で黒丸で示された位置の係数がBlock Cの有意係数であったため、対応する位置の統計情報が図１７のTerm3に示されたような値に更新される。またスキャンオーダ保持部102では、Block Cの入力による係数位置の入れ替えが発生したため、図１７のTerm3に示されるごとく係数位置の情報が更新される。並列処理判定部104はTerm3において、次の状態でスキャン順序が入れ替わる可能性のある個所が存在しないため、図１５に示されたフローに従って並列処理（P=2）を示す並列制御信号をスキャン変化部101及びスキャン状態保持部103へと出力する。またTerm3においてスキャン状態保持部103では、並列制御信号が並列処理を示しているので、次の統計情報として現在保持中の統計情報に対しBlock D及びE入力の有意係数に対応する情報を更新してスキャンオーダ保持部102へと出力する。当該更新されるBlock D及びE入力の有意係数に対応する位置は、図１７のTerm3の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term3においてスキャン変換部101は、Term2において行ったBlock Cのスキャン変換処理結果を、変換データ出力#1出力する。またスキャン変換部101は、Block Bのスキャン変換処理結果を保持して変換データ出力#2へと出力する。また並列処理判定部104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101は、Block D及びEをスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。
【００６６】
次に、Term4において、ブロックデータ#1としてBlock Fが、ブロックデータ#2としてBlock Gが、スキャン変換部101及びスキャン状態保持部103へと入力される。スキャン状態保持部103では、Term3において並列処理がなされ、かつ図１７で黒丸及び白丸で示された位置の係数が有意係数であったため、対応する位置の統計情報を図１７のTerm4に示されたような値に更新する。またスキャンオーダ保持部102では、Block D及びEの入力による係数位置の入れ替えは起きないため、Term4においても変更されない。並列処理判定部104においては、スキャンオーダ保持部102より出力される係数位置情報及びスキャン状態保持部103より出力される統計情報に基いて、図１５に示されたフローに従って並列制御信号を101及び103へと出力する。Term4においては、図１７のTerm4に示されるようにスキャン順序が入れ替わる可能性のある個所が存在する。このため、並列処理判定部104は逐次処理を示す並列制御信号を出力する。またTerm4においてスキャン状態保持部103では、並列制御信号が逐次処理を示しているので、次の統計情報として、現在保持中の統計情報に対しBlock F入力の有意係数に対応する情報のみ更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock F入力の有意係数に対応する位置は、図１７のTerm4の黒丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term4においてスキャン変換部101は、Term3において行ったBlock D及びEのスキャン変換処理結果を、変換データ出力#1及び#2として出力する。また並列処理判定部104より出力された並列制御信号は逐次処理を示しているので、スキャン変換部101はBlock Fのみをスキャンオーダ保持部102より出力された係数位置情報に従って並び替える。
【００６７】
次に、Term5において、ブロックデータ#1としてBlock Gが、ブロックデータ#2としてBlock Hが、スキャン変換部101及びスキャン状態保持部103へと入力される。スキャン状態保持部103では、Term4において逐次処理がなされ、かつ図１７で黒丸で示された位置の係数がBlock Fの有意係数であったため、対応する位置の統計情報が図１７のTerm5に示されたような値に更新される。またスキャンオーダ保持部102では、Block Fの入力による係数位置の入れ替えは起きないため、Term5においても変更されない。並列処理判定部104はTerm5において、次の状態でスキャン順序が入れ替わる可能性のある個所が存在しないため、図１５に示されたフローに従って並列処理を示す並列制御信号をスキャン変換部101及びスキャン状態保持部103へと出力する。また同じくTerm5においてスキャン状態保持部103では、並列制御信号が並列処理を示しているため、次の統計情報として、現在保持中の統計情報に対しBlock G及びH入力の有意係数に対応する情報を更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock G及びH入力の有意係数に対応する位置は、図１７のTerm5の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term5においてスキャン変換部101は、Term4において行ったBlock Fのスキャン変換処理結果を、変換データ出力#1として出力する。またスキャン変化部101は、Block Eのスキャン変換処理結果を保持して変換データ出力#2へと出力する。また並列処理判定部104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101はBlock G及びHを、スキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。
【００６８】
以下、同様にスキャン変換処理を繰り返す。
【００６９】
次に、本実施形態の実施形態を構成する各部の構成及び動作について、それぞれ説明する。まず、スキャン変換部101内部の構成及び動作を、図１０を用いて説明する。
【００７０】
図１０は、スキャン変換部101の内部の構成例を示した図である。ブロックスキャン変換器#1(1011)は、ブロックデータ入力#1として入力した着目ブロック内のデータを、係数位置情報に従って並び替えを施し、変換データ出力#1として次のサイクルに出力する。ブロックスキャン変換器#2(1012)も同様で、ブロックデータ入力#2を係数位置情報に従って並び替えを施し、並列制御信号が並列処理指示を示す場合には変換データ出力#2として次のサイクルに出力する。また、並列制御信号が逐次処理指示を示す場合には、前サイクルの値を保持して変換データ出力#2として出力する。
【００７１】
次に、スキャンオーダ保持部102内部の構成及び動作を図１１を用いて説明する。
【００７２】
ソータ1021aは、係数a〜oの次の統計情報を表すnScanTotalsを、係数位置情報に応じてスキャン順に1〜15まで並べ替えて出力する。ソータ1021bは、係数b〜oの非ゼロ情報を、係数位置情報に応じてスキャン順に2〜15まで並べ替えて出力する。論理ORアレイ1022は、係数b〜oの有意係数情報#1及び係数b〜oの有意係数情報#2を、それぞれ互いに論理ORをとって係数b〜oの非ゼロ情報として出力する。マルチプレクサ1023は、図中'1'で示された入力と'0'で示された入力とのいずれかを、セレクト信号に従って選択して出力する。本実施形態ではセレクト信号が'1'であれば入力'1'を、'0'であれば入力'0'を選択して出力するものとしている。比較部1024はソータ1021aより出力されたnScanTotalsのうち、1021bより出力された非ゼロ情報が非ゼロを示している場合は、スキャン順で隣り合う2つ入力として値を比較し、小さい方を出力する。また比較部1024は、ソータ1021bより出力された非ゼロ情報が非ゼロを示していない場合は、スキャン順で前のnScanTotalsを出力する。また比較部1024は、ソータ1021bより出力された非ゼロ情報が非ゼロを示しており、かつスキャン順で前のnScanTotalsが小さい場合、マルチプレクサ1023へのセレクト信号として'1'を出力し、そうでなければ'0'を出力する。フリップフロップ1025は、マルチプレクサ1023からの出力を入力し、保持してスキャン順序1〜15の係数位置情報として出力する。
【００７３】
次に、スキャン状態保持部103内部の構成及び動作を、図１２を用いて説明する。
【００７４】
ブロック入力データ#1及び#2は、それぞれ係数a#1〜o#1及び係数a#2〜o#2へとスフ゜リットされて非ゼロ検出部1031a1〜1031o1及び1031a2〜1031o2へとそれぞれ入力される。非ゼロ検出部1031a1〜1031o1は、係数a#1〜o#1が0であるか否かをそれぞれ判別し、判別結果を係数a#1非ゼロ信号〜o#1非ゼロ信号として出力する。当該非ゼロ信号は、本実施形態においては非ゼロであった場合は'1'を、そうでない場合は'0'として出力されるものとする。非ゼロ検出部1031a2〜1031o2は、係数a#2〜o#2が0であるか否かをそれぞれ判別し、非ゼロであった場合には'1'を、そうでない場合は'0'として出力する。論理ANDゲート1032a〜1032oは、非ゼロ検出部1031a2〜1031o2の出力と並列制御信号入力との論理ANDをそれぞれとり、係数a#2非ゼロ信号〜o#2非ゼロ信号として出力する。本実施形態においては、並列制御信号は並列処理指示を'1'、逐次処理指示を'0’として示されるものとする。すなわち、当該並列制御信号が逐次処理指示を示している場合には、係数a#2非ゼロ信号〜o#2非ゼロ信号はいずれも'0'にマスクされる。また、当該係数a#1非ゼロ信号〜o#1非ゼロ信号及び係数a#2非ゼロ信号〜o#2非ゼロ信号はそれぞれ、有意係数情報#1及び#2として外部へ出力される。カウンタ1033a〜1033oは、それぞれ係数a〜oに対応するScanTotalsを保持する。カウンタ1033aは、係数a#1非ゼロ信号及び係数a#2非ゼロ信号を入力し、それぞれの状態に応じて内部状態をカウントアップして出力する。
【００７５】
図１３は、カウンタ1033a〜1033oに共通な内部構成例を図示したものである。フリップフロップ10331は、対応する係数のScanTotalsを保持して出力する。加算器10332は、フリップフロップ10331の出力に対して'1'を加算し、その加算結果をマルチプレクサ10334へと出力する。加算器10333はフリップフロップ10331の出力に対して'2'を加算し、その加算結果をマルチプレクサ10334へと出力する。マルチプレクサ10334は、#1非ゼロ入力及び#2非ゼロ入力の状態に応じて、フリップフロップ10331の出力、または、加算器10332の出力、または、加算器10333の出力のいずれかを選択してフリップフロップ10331へと出力する。また、マルチプレクサ10334の出力はScanTotalsの次の状態”nScanTotals”として、外部へと出力される。また、マルチプレクサ10334は#1非ゼロ入力が'1'かつ#2非ゼロ入力が'0'の場合は加算器10332の出力を、いずれも'1'の場合は加算器10333の出力を、その他の場合はフリップフロップ10331の出力をそれぞれ選択して出力する。カウンタ1033a同様、他のカウンタ1033b〜1033oも係数b〜o#1非ゼロ信号及び係数b〜o#2非ゼロ信号をそれぞれ入力し、それぞれの状態に応じて内部状態をカウントアップして出力する。カウンタ1033a〜1033oの出力である係数a〜oのScanTotalsは、次の統計情報として外部へと出力される。またカウンタ1033a〜1033oの出力である係数a〜oのScanTotalsは、統計情報として外部へと出力される。
【００７６】
次に、並列処理判定部104の内部の構成及び動作を、図１４を用いて説明する。
【００７７】
統計情報は係数a〜o ScanTotalsへとスプリットされてソータ1041へと入力される。ソータ1041は、係数a〜oのScanTotalsを、係数位置情報に応じてスキャン順に1〜15まで並べ替えて比較器1042へ出力する。比較器1042はスキャン順序1〜15のScanTotalsをそれぞれ比較し、比較結果を1043へと出力する。比較器1042は、複数の比較器10421が、図示されたごとく接続されてなる。比較器10421は、同図で上方からの入力値から1を引いた値が、下方からの入力値より小さい場合に'0'を、そうでない場合には'1'を比較結果として論理ＡＮＤゲート1043へと出力する。論理ANDゲート1043は、比較器1042より出力される全ての比較器10421の比較結果の論理ANDをとり、並列制御信号として外部へと出力する。この場合、並列制御信号は、並列処理指示を示す場合は'1'、逐次処理指示を示す場合は'0'となる。
【００７８】
［第２の実施形態］
次に、並列スキャン変換部206の第2の実施形態の構成について、図１８のブロック図を参照して説明する。
【００７９】
同図において、図１と実質的に同機能を有するものについては、同符を付した。従って、スキャン変換部101は、連続する2個のブロックデータ入力#1及び#2を受け取り、スキャン変換を行なって変換データ出力#1及び#2として出力する。またスキャン変換部101は、スキャンオーダー保持部102及び並列処理判定部2104に接続されている。スキャン変換部101はブロックデータ入力#1及び#2を、スキャンオーダ保持部102より受け取るスキャンオーダー情報に従ってスキャン変換を行う。そしてスキャン変換部101は、並列処理判定部2104より受け取る並列処理制御信号に従って変換データ出力#1のみを出力するか、または変換データ出力#1及び#2の両方を出力する。スキャンオーダー保持部102は、スキャン状態保持部103の出力する情報をもとに、スキャン順序を表すスキャンオーダー情報を生成して保持し、スキャン変換部101及び並列処理判定部2104及び有意データ位置情報生成部2105へ出力する。スキャン状態保持部103は、ブロックデータ入力#1及び#2を受け取り、次のスキャン状態及びスキャン状態を生成して保持し、次のスキャン状態をスキャンオーダ保持部102へ、スキャン状態を並列処理判定部2104へと出力する。並列処理判定部2104は、スキャンオーダ保持部102の出力するスキャンオーダー情報、及び、スキャン状態保持部103の出力するスキャン状態、及び、有意データ位置情報生成部2105の出力する有意データ位置情報を受け取る。そして並列処理判定部2104はこれらの情報に基いて、並列処理制御信号を生成し、スキャン変換部101及びスキャン状態保持部103へと出力する。有意データ位置情報生成部2105は、ブロックデータ入力#1及びスキャンオーダ保持部102の出力するスキャンオーダー情報を受け取り、各係数が有意係数であるか否かの情報をスキャン順に並べて有意データ位置情報として並列処理判定部2104へ出力する。
【００８０】
次に、本第２の実施形態の並列スキャン変換部206の動作について、図２２のタイミングチャート、及び、図２３の状態説明図、及び図１８を用いて説明する。
【００８１】
図２２では、Term1〜5の各期間におけるブロックデータ入力から変換データ出力までの各部の状態の変化を示している。Term1において、ブロックデータ#1としてBlock Aが、ブロックデータ#2としてBlock Bが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm1において、Block Aは有意データ位置情報生成部2105へも入力される。またTerm1では、スキャンオーダ保持部102内部で保持されているスキャンオーダー情報、及び、スキャン状態保持部103内部で保持されているスキャン状態は初期状態となっている。本第２の実施形態においては、スキャンオーダ保持部102及びスキャン状態保持部103における動作及びそれぞれの内部で扱う情報の意味は、第１の実施形態におけるスキャンオーダ保持部102及びスキャン状態保持部103のそれと同様であるので、説明は省略する。
【００８２】
図２３は、図２２のTerm1〜5の各期間における、スキャンオーダ保持部102内部で保持する係数位置、及び、スキャン状態保持部103内部で保持する統計情報、及び、ブロック入力#1及び#2の状態を表している。Term1において、係数位置及び統計情報は、図２３に示されるごとく初期化されている。ここへBlock A及びBが図２３に示される値で入力されたとする。図２３では図１７同様、入力されたブロック内の係数値のうち、有意係数が現れたブロック内の位置に対応するところに、黒丸及び白丸でマーキングされているので、参考にされたい。黒丸及び白丸の示す意味もまた、図１７と同様である。
【００８３】
Term1における統計情報の状態においては、ブロック内の何れの位置に有意係数が発生した場合でも、どのスキャン順序に対応する統計情報もそれより前の順序に対応する統計情報の値より大きくなることはない。そのため、Block A及びBはいずれも同一のスキャン順序でスキャン変換可能である。またTerm1において有意データ位置情報生成部2105は、Block Aの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104においては、スキャンオーダ保持部102より出力される係数位置情報及びスキャン状態保持部103より出力される統計情報及び有意データ位置情報生成部2105より出力される有意係数位置情報より並列処理可能と判定し、並列処理指示を示す信号をスキャン変換部101へと出力する。
【００８４】
ここで図２０は並列処理判定部2104の並列処理判定フローを示した図である。以下、図２０を用いて並列処理判定部2104の並列処理判定フローについて説明する。処理が開始されると、処理S21041において変数nに2が代入される。次に処理S21042において、変数tempに1番目のスキャン順序における統計情報ScanTotals(1)が代入される。次にS21043において、n番目のスキャン順序の係数が有意係数かつ、temp-N+1の値がn番目のスキャン順序の統計情報ScanTotals(n)の値より小さいか否かを判定する。当該条件に合致する場合、処理S21044へ、そうでない場合は処理S21045へと進む。ここでNは並列に入力されるブロックの数を表す。本実施形態においてはN=2となる。処理S21044において、逐次処理で行うよう判定される。処理S21044がなされると判定処理の終了となる。処理S21045において、変数tempにn番目のスキャン順序における統計情報ScanTotals(n)が代入されると、処理S21046が実行される。処理S21046において、ブロック内にまだ係数があるかどうかの確認がなされ、ある場合は処理S21047へ、そうでない場合は処理S21048へと進む。処理S21047において、変数nの値がインクリメントされ、処理S21043へと移行する。処理S21048においては、N並列で処理されるよう判定される。本第２の実施形態においてはN=2であるので、２並列で処理を行うよう判定される。処理S21048がなされると判定処理の終了となる。このように並列処理判定部2104では、統計情報ScanTotals及び有意係数であるか否かの情報をもとに、並列処理制御情報を生成する。
【００８５】
Term1の説明へと戻る。Term1において、スキャン変換部101は入力されたBlock A及びBを、スキャンオーダ保持部102より出力された係数位置情報及び並列処理判定部2104より出力された並列制御信号に従って、スキャン順序の並び替えを行う。Term1では並列処理判定部2104より出力された並列制御信号は並列処理を示しているので、Block A及びBはスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理が行われる。
【００８６】
次に、Term2において、ブロックデータ#1としてBlock Cが、ブロックデータ#2としてBlock Dが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm2において、Block Cは有意データ位置情報生成部2105へも入力される。スキャン状態保持部103では、Term1において並列処理がなされ、かつ図２３で黒丸及び白丸で示された位置の係数が有意係数であったため、対応する位置の統計情報が図２３のTerm2に示されたような値に更新される。またスキャンオーダ保持部102では、Block A及びBの入力による係数位置の入れ替えは起きないため、Term2においても変更されない。またTerm2において有意データ位置情報生成部2105は、Block Cの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104においては、スキャンオーダ保持部102より出力される係数位置情報、及び、スキャン状態保持部103より出力される統計情報、及び、有意データ位置情報生成部2105より出力される有意係数位置情報に基いて図２０に示されたフローに従って並列制御信号をスキャン変換部101、及び、スキャン状態保持部103へと出力する。Term2においては、図２３のTerm2に示されるようにスキャン順序が入れ替わる個所が存在するため、並列処理判定部2104は逐次処理を示す並列制御信号を出力する。また同じくTerm2においてスキャン状態保持部103では、並列制御信号が逐次処理を示しているので、次の統計情報として、現在保持中の統計情報に対しBlock C入力の有意係数に対応する情報のみ更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock C入力の有意係数に対応する位置は、図２３のTerm2の黒丸で示されている。スキャンオーダ保持部102では、スキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term2においてスキャン変換部101では、Term1において行ったBlock A及びBのスキャン変換処理の結果を、変換データ出力#1及び#2として出力する。また並列処理判定部2104より出力された並列制御信号は逐次処理を示しているので、スキャン変換部101はBlock Cのみをスキャンオーダ保持部102より出力された係数位置情報に従って並び替える。
【００８７】
次にTerm3において、ブロックデータ#1としてBlock Dが、ブロックデータ#2としてBlock Eが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm3において、Block Dは有意データ位置情報生成部2105へも入力される。スキャン状態保持部103では、Term2において逐次処理がなされ、かつ図２３の中で黒丸で示された位置の係数がBlock Cの有意係数であったため、対応する位置の統計情報が図２３のTerm3に示されたような値に更新される。またスキャンオーダ保持部102では、Block Cの入力による係数位置の入れ替えが発生したため、図２３のTerm3に示されるごとく係数位置の情報が更新される。またTerm3において有意データ位置情報生成部2105は、Block Dの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104はTerm3において、次の状態でスキャン順序が入れ替わる個所が存在しないため、図２０に示されたフローに従って並列処理を示す並列制御信号をスキャン変換部101及びスキャン状態保持部103へと出力する。またTerm3においてスキャン状態保持部103では、並列制御信号が並列処理を示しているので、次の統計情報として現在保持中の統計情報に対しBlock D及びE入力の有意係数に対応する情報を更新してスキャンオーダ保持部102へと出力する。当該更新されるBlock D及びE入力の有意係数に対応する位置は、図２３のTerm3の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term3においてスキャン変換部101は、Term2において行ったBlock Cのスキャン変換処理結果を、変換データ出力#1出力する。またスキャン変換部101は、Block Bのスキャン変換処理結果を保持して変換データ出力#2へと出力する。また並列処理判定部2104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101はBlock D及びEをスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。
【００８８】
次に、Term4において、ブロックデータ#1としてBlock Fが、ブロックデータ#2としてBlock Gが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm4において、Block Fは有意データ位置情報生成部2105へも入力される。スキャン状態保持部103では、Term3において並列処理がなされ、かつ図２３で黒丸及び白丸で示された位置の係数が有意係数であったため、対応する位置の統計情報が図２３のTerm4に示されたような値に更新される。またスキャンオーダ保持部102では、Block D及びEの入力による係数位置の入れ替えは起きないため、Term4においても変更されない。またTerm4において有意データ位置情報生成部2105は、Block Fの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104においては、スキャンオーダ保持部102より出力される係数位置情報及びスキャン状態保持部103より出力される統計情報に基いて、図２０に示されたフローに従って並列制御信号をスキャン変換部101及びスキャン状態保持部103へと出力する。Term4においては、図２３のTerm4に示されるように統計情報は同じ個所があるが有意係数でないため、係数位置の入れ替わりは発生しないと判定され、並列処理判定部2104は逐次処理を示す並列制御信号を出力する。またTerm4においてスキャン状態保持部103では、並列制御信号が並列処理を示しているので、次の統計情報として現在保持中の統計情報に対しBlock F及びG入力の有意係数に対応する情報を更新してスキャンオーダ保持部102へと出力する。当該更新されるBlock F及びG入力の有意係数に対応する位置は、図２３のTerm4の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term4においてスキャン変換部101は、Term3において行ったBlock D及びEのスキャン変換処理結果を、変換データ出力#1及び#2として出力する。また並列処理判定部2104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101はBlock F及びGをスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。
【００８９】
次に、Term5において、ブロックデータ#1としてBlock Hが、ブロックデータ#2としてBlock Iが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm5において、Block Hは有意データ位置情報生成部2105へも入力される。スキャン状態保持部103では、Term4において並列処理がなされ、かつ図２３で黒丸及び白丸で示された位置の係数が有意係数であったため、対応する位置の統計情報が図２３のTerm5に示されたような値に更新される。またスキャンオーダ保持部102では、Block F及びGの入力による係数位置の入れ替えは起きないため、Term5においても変更されない。またTerm5において有意データ位置情報生成部2105は、Block Hの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104はTerm5において、次の状態でスキャン順序が入れ替わる個所が存在しないため、図２０に示されたフローに従って並列処理を示す並列制御信号をスキャン変換部101及びスキャン状態保持部103へと出力する。また同じくTerm5においてスキャン状態保持部103では、並列制御信号が並列処理を示しているため、次の統計情報として、現在保持中の統計情報に対しBlock H及びI入力の有意係数に対応する情報を更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock H及びI入力の有意係数に対応する位置は、図２３のTerm5の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term5においてスキャン変換部101は、Term3において行ったBlock F及びGのスキャン変換処理結果を、変換データ出力#1及び#2として出力する。また並列処理判定部2104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101はBlock H及びIをスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。以下、同様にスキャン変換処理を繰り返す。
【００９０】
次に、本第２の実施形態の実施形態を構成する各部の構成及び動作について、それぞれ説明する。スキャン変換部101、スキャンオーダ保持部102、及びスキャン状態保持部103については、第１の実施形態と同じであるので、その説明を省略する。
【００９１】
並列処理判定部2104内部の構成及び動作を、図１９を用いて説明する。
【００９２】
同図において、統計情報入力は係数a〜oのScanTotalsへとスプリットされて、ソータ1041へと入力される。ソータ1041は、係数a〜oのScanTotalsを、係数位置情報に応じてスキャン順に1〜15まで並べ替えて比較器1042へと出力する。比較器1042はスキャン順序1〜15のScanTotalsをそれぞれ比較し、比較結果を並列処理判定部21045へと出力する。比較器1042に関する説明は第１の実施形態のそれと同じであるので、説明を省略する。有意係数情報入力はスキャン順序2〜15の非ゼロ情報へとスプリットされて、並列処理判定部21044へと入力される。並列処理判定部21044は複数の論理反転ゲートであり、スキャン順序2〜15の非ゼロ情報をそれぞれ論理反転して、並列処理判定部21045へと出力する。並列処理判定部21045は複数の論理ORゲートで構成され、比較器1042内の全ての比較器10421の比較結果と並列処理判定部21044より出力されるスキャン順序2〜15の非ゼロ情報の論理反転結果との論理ORをとり、出力する。論理AND1043であり、並列処理判定部21045より出力される全ての出力の論理ANDをとり、並列制御信号として外部へと出力する。この場合、並列制御信号は、並列処理指示を示す場合は'1'、逐次処理指示を示す場合は'0'となる。
【００９３】
次に、第２の実施形態における、有意データ位置情報生成部2105内部の構成及び動作を図２１を用いて説明する。
【００９４】
ブロックデータ入力#1は係数a#1〜o#1へとスプリットされて、それぞれスキャン状態保持部1031a〜スキャン状態保持部1031oへと入力される。スキャン状態保持部1031a1〜スキャン状態保持部1031o1は、係数a#1〜o#1が0であるか否かをそれぞれ判別し、判別結果を係数a#1非ゼロ信号〜o#1非ゼロ信号として出力する。当該非ゼロ信号は、本第２の実施形態においては非ゼロであった場合に'1'を、そうでない場合は'0'として出力されるものとする。有意データ位置情報生成部21052はソータであり、係数a#1〜o#1を、係数位置情報に応じてスキャン順に1〜15まで並べ替えて、スキャン順序1〜15の非ゼロ情報として出力する。スキャン順序1〜15の非ゼロ情報は有意係数情報として、外部へと出力される。
【００９５】
以上本発明に係る実施形態を説明した。なお、本実施形態では、スキャン変換対しようの２次元配列のブロックのサイズを４×４画素サイズとし、その内の１５のＡＣ成分を例にして説明したが、これに限定されるものではない。ブロックサイズは一般にn行m列、もしくはｍ×ｎ個のデータで表わせ、その中のＮ個（Ｎは2以上）のブロックのスキャン変換処理をＭ（Mは1以上N以下の整数） 並列で行うよう指示できれば良い。
【００９６】
また、実施形態では、図７(ａ),(b)に示すように、統計情報ScanTotals()と、係数位置ScanOrder()とを別々にテーブルとして管理する例を説明したが、統計情報と係数位置とをペアとして扱われるので、これらを１つのテーブルで管理するようにしても良い。
【００９７】
また、実施形態では、本発明の装置がカメラの内部の符号化部に収容されるものとして説明したが、これによっても本願発明が限定されるものではない。
【技術分野】
【０００１】
本発明は、スキャン変換装置及び画像符号化装置、並びにそれらの制御方法に関するものである。
【背景技術】
【０００２】
画像データがデータ量が多く、そのままでは保存、送信に適さない。そこで、一般には、画像データを圧縮符号化することで、データ量を少なくすることが行われている。そこで、先ず、一般的な画像符号化装置について説明する。
【０００３】
撮像素子などで撮影されたデジタル入力画像は、所望の矩形サイズのタイルに分割される。さらに、各タイルは、予め定められた２次元のMB(マクロブロック)へとさらに分割される(図５参照)。MBのデータは直交変換が施され、色空間データから周波数空間の変換係数に変換される。
【０００４】
さらに必要に応じて、変換係数に対して量子化処理が施される。さらに、画像のデータパターンが複数ブロックにまたいでいる場合は、量子化された変換係数を各周波数帯に応じてフレーム内予測することで、更に変換係数の強度を削減する。ただし、量子化値がブロック内の係数位置によって異なっている場合やブロック間で異なっている場合は、画像のデータパターンが複数ブロックにまたいでいても、変換係数の周波数帯応じた相関が保たれているわけではない。そのため、フレーム内予測を施すことで必ずしも変換係数の強度を抑制することができるわけではない。このような場合は、フレーム内予測の処理を省いてもかまわない。
【０００５】
そして、量子化、および、フレーム内予測が施された２次元の変換係数は、有意係数を前方に、ラン(零)を後方に連続するように１次元データとして並びかえられる。このようにして並びかえた１次元データをエントロピー符号化することで符号化ストリームが生成される。
【０００６】
一方、上記のようにして生成された符号化ストリームは、その逆の手順で処理を施すことによって、画像に再構成される。
【０００７】
JPEG、MPEG2、MPEG4、JPEG-XRなどに代表される多くのブロック変換ベースの画像符号化装置では、エントロピー符号化にランレングス符号化を用いている。ランレングス符号化は、あるパターンに従って２次元の変換係数を１次元スキャンし、ランの連続する長さを符号化するものである。図３（ａ）はこのスキャンパターンの一例である。図示の番号順にスキャンするものであり、この番号順で示されるルートがジグザグであるので「ジグザグ」パターンと呼ばれる。しかし、以下３つの理由で「ジグザグ」パターンのような一定の走査パターンでは、符号化効率に寄与するとは必ずしも言えない。
【０００８】
第１の理由は、ブロック歪を抑制するため、ブロック間をまたいで変換を施す場合は、エッジが強調されるため、変換係数の分散が大きくなり、変換係数の強度も大きくなることである。この場合、低周波の変換係数(ブロックの右下の変換係数)の強度が必ずしも小さくなるとは限らない。そのため、ブロックの左上から右下へ変換係数をスキャンするスキャン順序が最適とは言えない。
【０００９】
第２の理由は、ブロック内の画素に水平方向や垂直方向に依存関係がある場合は、依存関係に応じて変換係数の周波数帯が偏る傾向にあることである。このような場合においては、図３（ｂ）や図３（ｃ）に示されるような水平方向と垂直方向にそれぞれ異なるスキャン順序が適している。
【００１０】
そして、第３の理由は、ブロックをまたいでテクスチャーが存在する場合、ブロック間で変換係数の偏りが同じ傾向にあることである。その場合は、量子化された変換係数に対して、係数予測を行うことで係数の強度を抑制できる。この場合は予測方法に応じて変換係数の周波数帯の偏りが変わる。そのため、予測方法に応じた走査パターンが必要となる。
【００１１】
以上の理由から、入力画像と符号化方式に合った最適なスキャン順序が選択することが望ましい（例えば、特許文献３）。
【００１２】
JPEG-XRに代表されるように、MBをさらにブロックに分割し、ブロック毎に量子化値やフレーム内予測方法が変更できる符号化方式においては、ブロック毎にスキャン順序を変更する方法が適している（例えば特許文献１、および、特許文献２）。
【００１３】
例えば、特許文献１に記載のスキャン順序決定方法によると、図４に示すように１６×１６画素で構成されたMBを、４×４画素のブロックに分割し、図示のＡ〜Ｐの順番で各ブロックのスキャン変換を行う。これによると、ブロックＡのスキャン変換結果を分析し、すなわち、並び替えた後の順序で係数を分析して、次のブロックＢのスキャン順序を決定する。同様に、ブロックＢのスキャン変換結果を分析し、すなわち、並び替えた後の順序で係数を分析して、次のブロックＣのスキャン順序を決定する。以下同様に、現在処理対象のブロックのスキャン変換結果に依存して、次のブロックのスキャン順序を決定する。ここで、上記のスキャン順序の決定方法について図６を用いて更に説明する。
【００１４】
先ず、S801において、スキャン変換を施されたブロック内の変換係数C[n](n≧0)を1次元の順序で1つ取得する。次に、S802において、S801で取得した係数C[n]がラン(零)であるか否かを判定する。変換係数C[n]がランである場合は、S804の判定に進む。一方、変換係数C[n]が有意係数(非零)であった場合は、S803の処理を施す。
【００１５】
そして、４×４ブロック内のどの位置に有意係数が発生したのかを統計した統計情報テーブルScanTotals(例えば、図７（ａ）参照)がある。図７（ａ）は、説明の都合上、スキャン順序に対応した４×４画素ブロック内の位置(例えば、図７（ｂ）に対応した統計情報テーブル値を示している。
【００１６】
尚、統計情報ScanTotalsの初期値として、以下のように設定される場合がある。
{t*N, t*(N-1), t*(N-2),……,t}
【００１７】
一般に、tは小さい整数(2 or 4)であるように選択される。tの値は、量子化で用いられる量子化パラメータによって決定されてもよい。そして、統計情報は、ある一定期間を置いてリセットすれば、統計情報の各要素の最大ビット長を固定することができる。
【００１８】
さらに、４×４画素ブロック内の係数の位置とスキャン順序の対応を示すテーブルScanOrderがある。スキャン順序に対応する係数の位置ScanOrderの初期順序は、画像符号化処理装置と画像復号化処理装置とで、因果的に決定されることが望ましい。例えば、水平方向の係数予測がなされた場合は、水平方向を優先的に走査するスキャン順序で初期化する(図３（ｂ）参照)。一方、垂直方向の係数予測がなされた場合は、垂直方向を優先的に走査するスキャン順序で初期化する(図３（ｃ）参照)。尚、水平方向性のスキャン順序は、特定の方向性を示さないブロックについても初期走査順序として使用してもよい。図４のa〜oは、４×４画素ブロック内の各係数の位置との対応を示している。図９（ｂ）は、図３（ｂ）に示す初期化された状態のスキャン順序テーブルScanOrderを図４のa〜oで示している。
【００１９】
さて、S803では、有意係数の場合は、この統計情報テーブルScanTotalsの当該要素の出現頻度値をインクリメント（増加）する。
【００２０】
さらに、S804において、統計情報ScanTotals[n]とScanTotals[n-1]の大小関係を判定する。ScanTotals[n]がScanTotals[n-1]より大きい場合は、変換係数C[n]の位置では、変換係数C[n-1]の位置より有意係数の発生回数が多いことを意味する。そのため、S805において、図10に示すようなスキャン順序に対応する係数の位置ScanOrderとそれに対応するScanTotalsに対して交換処理を施す。また、S802において、統計情報ScanTotals[n]がScanTotals[n-1]より小さい場合は、スキャン順序の変更処理は施さない。
【００２１】
ここで、S805の具体的な交換処理について説明する。交換処理では、係数位置ScanOrder[n]をScanOrder[n-1]に、ScanOrder[n-1]をScanOrder[n]に入れ替えるため、例えば下記のような演算を行う。
Temp = ScanOrder[n-1]
ScanOrder[n-1] = ScanOrder[n]
ScanOrder[n] = Temp
一方、統計情報ScanTotals[n]とScanTotals[n-1]とに、ScanTotals[n-1]をScanTotals[n]に入れ替えるため、例えば下記のような演算を行う。
Temp = ScanTotals[n-1]
ScanTotals[n-1] = ScanTotals[n]
ScanTotals[n] = Temp
【００２２】
S806で、スキャン順序決定のためにブロック内の変換係数の取得が完了していない場合は、S807へ進み、次の係数の取得に備える。一方、ブロック内の全係数の取得が完了していれば、スキャン順序決定フローを終了する。
【００２３】
以上で説明したように、スキャン順序n-1に対応する係数位置ScanOrder[n-1]を、スキャン順序nとn-1に対応する統計情報ScanTotals[n]とScanTotals[n-1]を用いて、因果的に決定している。これにより、段階的に最適なスキャン順序に近くづくことができる。さらに、因果的にスキャン順序を決定できるため、符号化装置から復号化装置にスキャン順序を明示的に知らせる情報を符号化ストリームに付加する必要がないというメリットがある。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】特開2006-191628号公報
【特許文献２】特開平07-050836号公報
【特許文献３】特開2004-032788号公報
【発明の概要】
【発明が解決しようとする課題】
【００２５】
上記のように、或るブロックの状態に応じて、後続するブロックのスキャン順序が決定するスキャン順序決定方法においては、ブロック毎にスキャン順序が変更され得る。このようなスキャン変換処理においては、複数のブロックのスキャン変換処理を同時に実行することが困難であるため、処理の高速化が十分に図れないという問題が残る。
【００２６】
本発明は、かかる問題を解決する技術を提供しようとするものであり、ブロック毎にスキャン順序が変更されるスキャン変換処理を利用しながらも、スキャン変換処理を並列に実行できる場合には並列実行することで、単位時間当たりのスキャン変換するブロック数をこれまで以上にする技術を提供しようとするものである。
【課題を解決するための手段】
【００２７】
かかる課題を解決するため、例えば本発明は以下の構成を備える。すなわち、
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える装置であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記スキャン状態保持手段に保持されたスキャン状態に応じて、N(Nは2以上の整数)個の前記ブロックのスキャン変換処理をM (Mは1以上N以下の整数) 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、スキャン変換装置。
【発明の効果】
【００２８】
本発明によれば、ブロック毎にスキャン順序が変更されるスキャン変換処理を利用しながらも、スキャン変換処理を並列に実行できる場合には並列実行することで、単位時間当たりのスキャン変換するブロック数をこれまで以上にすることができる。
【図面の簡単な説明】
【００２９】
【図１】第１の実施形態における並列スキャン変換部の構成図である。
【図２】本発明の画像符号化部のブロック構成図である。
【図３】スキャン順序の例を示す図である。
【図４】マクロブロックとブロックとの関係、及び、ブロック内の各データとその位置に割り当てた文字との対応関係を示す図である。
【図５】画像分割の説明するための図である。
【図６】スキャン順序決定処理のフローチャートである。
【図７】統計情報テーブルと係数位置テーブルを示す図である。
【図８】画像復号部の構成図を示す図である。
【図９】実施形態で適用するデジタルカメラの構成図である。
【図１０】第１の実施形態におけるスキャン変換部の構成図である。
【図１１】第１の実施形態におけるスキャンオーダ保持部の構成図である。
【図１２】第１の実施形態におけるスキャン状態保持部の構成図である。
【図１３】図１２のカウンタ1033の構成図である。
【図１４】第１の実施形態における並列処理判定部の構成図である。
【図１５】第１の実施形態における並列処理判定部の並列数判定処理のフローチャートである。
【図１６】第１の実施形態の動作タイミングチャートを示す図である。
【図１７】第１の実施形態の処理過程におけるスキャン順（係数位置）と統計情報の推移を示す図である。
【図１８】第２の実施形態における並列スキャン変換部の構成図である。
【図１９】第２の実施形態における並列処理判定部の構成図である。
【図２０】第２の実施形態における並列処理判定部の並列数判定処理のフローチャートである。
【図２１】第２の実施形態における有意データ位置情報生成部の構成図である。
【図２２】第２の実施形態の動作タイミングチャート
【図２３】第２の実施形態の処理過程におけるスキャン順（係数位置）と統計情報の推移を示す図である。
【発明を実施するための形態】
【００３０】
以下、添付図面に従って本発明に係る実施形態を説明する。なお、実施形態では、或るブロックの状態に応じて、後続するブロックのスキャン順序が決定するスキャン変換処理を行うスキャン変換装置を利用して、符号化を行う例として説明する。また、当該符号化にかかる構成が、デジタルカメラやデジタルカムコーダに搭載する圧縮システムの中で利用する例として説明する。しかしながら、スキャン変換装置や画像符号化装置がデジタルカメラやカムコーダに搭載されることに限定されるものではない。
【００３１】
図９は、本実施形態に係る画像処理装置としてのデジタルカメラのハードウェア構成例を示す図である。撮像対象の像は、レンズ1201を介して、CCDやCMOSセンサなどの撮像素子1202上に結像される。撮像素子1202は、この結像された像をアナログ信号に変換し、このアナログ信号を後段のA/D変換器1203に送出する。
【００３２】
A/D変換器1203は、撮像素子1202から受けたアナログ信号をデジタル信号に変換する。メモリ制御回路1207は、この変換されたデジタル信号をデータ(画像データ)としてA/D変換器1203から取得すると、この画像データを画像処理部1204に送出する。画像処理部1204は、この画像データに対して周知の画像補間処理や色変換処理などを施す。
【００３３】
メモリ制御回路1207は、画像処理部1204から、画像処理後の画像データを取得すると、この取得した画像データをメモリ1205に格納する。メモリ1205は、撮像された静止画像や動画像のデータを一時的に格納するためのメモリであって、所定枚数の静止画像(所定フレーム数分の静止画像)を格納するための領域を有する。このメモリ1205は読み書き可能なメモリであるので、メモリ制御回路1207は、メモリ1205に対するデータ書込み専用の複数のメモリ制御部と、メモリ1205に対するデータ読出し専用の複数のメモリ制御部と、を有する。
【００３４】
メモリ1205に格納された画像データはメモリ制御回路1207によって再度読み出され、D/A変換器1208と符号化部1211とに送出される。D/A変換器1208は、この画像データをアナログ信号に変換し、この変換したアナログ信号を画像表示部1209に送出する。これにより、画像表示部1209の表示画面上には、このアナログ信号が示す画像(撮像された画像)が表示される(再生される)ことになる。
【００３５】
一方で、符号化部1211は、メモリ制御回路1207から受けた画像データ(入力画像)から符号化ストリーム（符号化データ）を生成する。そして、メモリ制御回路1207は、符号化部1211が生成した符号化ストリームを記憶媒体1206にファイルとして記録する。記憶媒体1206には、SDカード等の、画像処理装置に着脱可能なリムーバブルな媒体が利用される。
【００３６】
ここで、このデジタルカメラには、各種スイッチやボタンが搭載されている。その中に、モードダイヤル1221が設けられている。モードダイヤル1221は、撮像モード、再生モードの何れかを選択するためのものである。ユーザがモードダイヤル1221を操作して撮像モードを選択すると、システム制御部1220はROM1223に格納されたプログラムに従い、本装置を構成する各処理部の動作制御を行い、上述した処理を実現する。即ち、レンズ1201を介して得た像の画像データに基づく画像を画像表示部1209に表示させると共に、この画像データを符号化し、符号化ストリームとして記憶媒体1206に記録する処理を実現する。
【００３７】
一方、ユーザがモードダイヤル1221を操作して再生モードを選択すると、システム制御部1220は画像処理装置を構成する各部の動作制御を行い、以下に説明する各処理を実現する。
【００３８】
メモリ制御回路1207は、記憶媒体1206に記録されている符号化データファイルから符号化ストリームを読み出し、読み出した符号化ストリームを復号化1213に送出する。復号部1213は、メモリ制御回路1207から受けた符号化ストリームを復号する。メモリ制御回路1207は、復号して得られた画像データを、D/A変換器1208に送出する。D/A変換器1208は、この画像データをアナログ信号に変換し、この変換したアナログ信号を画像表示部1209に送出する。これにより、画像表示部1209の表示画面上には、記憶媒体1206に格納された符号化画像データファイルが再生（表示）されることになる。
【００３９】
なお、ROM1223には、画像処理装置の設定データや、システム制御部1220による実行対象のコンピュータプログラムが格納されている。更に、ROM1223には、以下に説明する処理において既知のデータとして説明するものについても格納されている。即ち、システム制御部1220は、このROM1223に格納されているコンピュータプログラムやデータを用いて処理を実行することで、本装置を構成する各部の動作制御を行う。これにより、本実施形態に係る装置は、以下に説明する各処理を実現することになる。
【００４０】
次に、図２を用いて符号化部1211について説明する。図２は、符号化部1211の詳細な機能構成例を示すブロック図である。図２に示した各部はハードウェアで構成されているものとするが、その一部若しくは全部をコンピュータプログラムで実現しても良い。
【００４１】
図２において、タイル分割部201は、入力した１枚の画像データを分割する画像分割部として機能する。具体的には、タイル分割部201は入力した画像データを１以上のタイルに分割し、各タイルを順にMB分割部202に出力する。MB分割部202は入力した１つのタイルから、符号化処理単位である複数のMBに分割し、その分割したMBを直交変換部203に送出する。そのため、直交変換部203以降の処理は、MB単位で処理が施される。
【００４２】
以下では、１つのMBを符号化する為の符号化の動作について説明するが、同様の動作は、他のMBに対しても行われることになるし、１つのタイル内の全MBの処理が終わると、他のタイルについても同様の処理が行われる。
【００４３】
MBのデータは、直交変換部203で直交変換が施され、色空間データから周波数空間の変換係数に変換される。さらに、非可逆を許容するのであれば、量子化部204において、変換係数を量子化処理して解像度を落とし、データ量を削減する。さらに、画像のデータパターンが複数ブロックにまたいでいる場合は、フレーム内予測部205において、量子化された量子化変換係数（以下、単に変換係数）を各周波数帯に応じてフレーム内予測することで、さらに変換係数の強度を削減する。ただし、量子化値がブロック内の係数位置によって異なっている場合やブロック間で異なっている場合は、画像のデータパターンが複数ブロックにまたいでいても、フレーム内予測の処理を省いてもかまわない。
【００４４】
そして、量子化、および、フレーム内予測が施された変換係数は２次元データとして並列スキャン変換部206に入力される。並列スキャン変換部206は、２次元の変換係数をスキャンし、有意係数を前方に、ラン(零)を後方に連続するように１次元配列データとして並びかえる。このようにして並びかえた１次元データをエントロピー符号化部207において、エントロピー符号化（ランレングス符号化）することで符号化ストリームが生成される。
【００４５】
一方、図８は復号部1213のブロック構成図を示している。復号部1213は図示の如く、エントロピー復号部1107、並列逆スキャン変換部1106、係数予測部1105、逆量子化部1104、逆直交変換部1103、ＭＢ結合部1102、及び、タイル結合部1101を有する。ただし、これら処理部の処理内容は、図２に示した符号化部1211のそれの逆であるので、詳細に関しては説明を省略する。
【００４６】
ここで、ブロック毎に量子化値やフレーム内予測方法が変更できる符号化方式においては、ブロック毎にスキャン順序を変更する方法が適している。以下、高速化を図るために２つ以上のブロックを並列にスキャン変換を施すように、並列スキャン変換部206を実現するための２つの実施形態について、詳細に説明する。
【００４７】
［第１の実施形態］
図１に並列スキャン変換部206の構成を示す。この並列スキャン変換部206は、スキャン変換部101、スキャンオーダー保持部102、スキャン状態保持部103、及び、並列処理判定部104を有する。ここでは、説明を簡単なものとするため、スキャン変換部101は、２つのスキャン変換を並列して実行するものとしているが、それ以上であっても構わないのは以下の説明から明らかであろう。以下、図１を用いて並列スキャン変換部206について詳細に説明する。
【００４８】
スキャン変換部101は連続する２個のブロックデータ入力#1及び#2を受け取り、スキャン変換（並べ替え処理）を行なって、その変換データ出力#1及び#2として出力する。このスキャン変換部101は、入力したブロックデータ入力#1及び#2を、スキャンオーダ保持部102より受け取るスキャンオーダー情報に従ってスキャン変換を行う。そして並列処理判定部104より受け取る並列処理制御信号に従って変換データ出力#1のみを出力するか、または変換データ出力#1及び#2両方を出力する。
【００４９】
スキャンオーダー保持部102は、スキャン状態保持部103の出力する情報をもとに、必要に応じて先に説明した交換処理を行ない、スキャン順序を表すスキャンオーダー情報を生成して保持する。そして、スキャンオーダー保持部102は、生成したスキャンオーダ情報をスキャン変換部101と並列処理判定部104に出力する。スキャン状態保持部103は、ブロックデータ入力#1及び#2を受け取り、次のスキャン状態及びスキャン状態を生成して保持し、次のスキャン状態をスキャンオーダ保持部102へ、スキャン状態を並列処理判定部104へと出力する。
【００５０】
並列処理判定部104は、スキャン変換部101の動作を制御するスキャン制御部として機能する。具体的には、並列処理判定部104は、スキャンオーダ保持部102が出力するスキャンオーダー情報、及びスキャン状態保持部103が出力するスキャン状態を受け取る。そして、並列処理判定部104は、これらの情報を解析して並列処理制御信号を生成し、スキャン変換部101及びスキャン状態保持部103に制御信号を出力する。
【００５１】
次に、本実施形態における並列スキャン変換部206の処理内容を、図１６のタイミングチャート、図１７の状態説明図、及び、図１を用いて説明する。
【００５２】
図１６では、Term1〜5の各期間におけるブロックデータ入力から変換データ出力までの各部の状態の変化を示している。Term1において、ブロックデータ#1としてBlock Aが、ブロックデータ#2としてBlock Bが、スキャン変換部101及びスキャン状態保持部103に供給される。またTerm1では、スキャンオーダ保持部102の内部で保持されているスキャンオーダー情報、及び、スキャン状態保持部103の内部で保持されているスキャン状態は初期状態となっている。
【００５３】
本実施形態においては、スキャンオーダ保持部102内部で保持する初期のスキャンオーダー情報は図７（ｂ）に示される係数位置を表すものとするが、スキャンオーダー情報はスキャンの順序を特定できる表現であればよく、これに限定されるものではない。また同様に本実施形態ではスキャン状態保持部103内部で保持する初期のスキャン状態（初期の各係数の出現頻度値）は、図７（ａ）に示される統計的に求めた情報を表すものとするが、スキャン状態はスキャンの順序を決定するための情報であればよく、これに限定されるものではない。なお、図７（ａ）に示すように、統計情報は出現頻度値の順（降順）に並べられれている。また本実施形態では、当該スキャン順序及び統計情報は、図６に示される係数位置(ScanOrder)及び統計情報(ScanTotals)の決定方法に準じて決定されるものとするが、当該決定方法もこれに限定されるものではない。
【００５４】
図１７は、図１６のTerm1〜5の各期間における、スキャンオーダ保持部102内部で保持する係数位置データ、及び、スキャン状態保持部103内部で保持する統計情報、及び、ブロック入力#1及び#2の状態を表している。Term1において、係数位置及び統計情報は、図１７に示されるごとく初期化されている。ここへBlock A及びBが図１７に示される値で入力されたとする。図１７ではまた、入力されたブロック内の係数値のうち、有意係数(0以外の値を持つ係数)が現れたブロック内の位置に対応するところに、黒丸及び白丸でマーキングされているので、参考にされたい。黒丸はブロック入力#1の有意係数の位置に対応し、白丸はブロック入力#2の有意係数の位置に対応する。
【００５５】
Term1における統計情報の状態においては、ブロック内の何れの位置に有意係数が発生した場合でも、どのスキャン順序に対応する統計情報もそれより前の順序に対応する統計情報の値より大きくなることはない。そのため、Block A及びBはいずれも同一のスキャン順序でスキャン変換可能である。並列処理判定部104は、スキャンオーダ保持部102より出力される係数位置情報、及びスキャン状態保持部103より出力される統計情報より並列処理可能と判定し、並列処理指示を示す信号をスキャン変換部101へ出力する。
【００５６】
ここで並列処理判定部104の並列処理判定処理を図１５のフローに従って説明する。
【００５７】
処理が開始されると、処理S1041において変数nに2が代入される。次に処理S1042において、並列処理数を決定するためのPに最大並列処理数（実施形態では'2'）を設定する。この後、処理S1043にて、連続する２つの統計情報の差Dを算出する。
D=ScanToltls(n-1)-ScanToltls(n)+1
【００５８】
次に、判定処理S1044にて、値ＰとＤとを比較判定する。ここでＰ≦Ｄであると判定した場合には、２つのブロックのスキャン処理を行なったとしても、統計情報中のScanToltls(n-1)よりも、ScanToltls(n)が大きくなることは有り得ない。
【００５９】
一方、Ｐ＞Ｄの場合、２つのブロックのスキャン処理を行なった場合、その結果、統計情報内に、昇順となるデータが存在することことになるので、それを降順とする必要がある。すなわち、スキャン順を変更して、最大並列数を少なくする必要があるので、処理S1405にて、変数Pに変数Dの値を代入する。
【００６０】
この後、判定処理S1046にて、変数nが、ブロック内の係数の個数になったか否かを判定する。否の場合には、処理S1047にて、変数nの値をインクリメント（増加）し、処理S1043に戻る。なお、実施形態では、1ブロックが4x4画素のサイズであり、スキャン対象（並べ替え対象）はその中の1個のＤＣ成分を除く15個のＡＣ成分であるので、ブロック内のスキャン変換対象の係数の個数は'15'である。
【００６１】
さて、判定処理S1046にて、yesと判定されると、統計情報の全てについての検査を終えたことになるので、処理S1048に進む。処理S1048では、値Pは、交換処理が行われるまでの最も少ないブロック数、より具体的には、ブロック数Ｐのブロックのデータを並列してスキャン変換しても構わないことを意味する。従って、並列実行数をＰ個として決定できることになる。
【００６２】
なお、統計情報が図７(a)の初期状態の場合、連続する２つのScanToltls(n-1)とScanToltls(n)の差は'2'であるので、理論的に３つのスキャン変換処理を並列処理が可能である。しかし、実施形態では、図１に示すように、スキャン変換部101が実行可能な並列処理数が２つであるので、処理S1048ではP=2と判定されることになる。また、上記の説明からわかるように、図１５のフローチャートは、要するに、n=2,3,…,15について、ScanToltls(n-1)とScanToltls(n)の最小となる箇所とその差を求め、それによって並列処理数を求めている。
【００６３】
Term1の説明へと戻る。Term1において、スキャン変換部101は入力されたBlock A及びBを、スキャンオーダ保持部102より出力された係数位置情報及び並列処理判定部104より出力された並列制御信号に従って、スキャン順序の並び替えを行う。Term1では並列処理判定部104より出力された並列制御信号は並列処理を示しているので、Block A及びBはスキャンオーダ保持部102より出力された係数位置情報に従って、並列に、並び替え処理が行われる。
【００６４】
次に、Term2において、ブロックデータ#1としてBlock Cが、ブロックデータ#2としてBlock Dが、スキャン変換部101及びスキャン状態保持部103へと入力される。Term1において並列処理がなされ、かつ図１７で黒丸及び白丸で示された位置の係数が有意係数であったため、スキャン状態保持部103の位置の統計情報は図１７のTerm2に示されたような値に更新される。またスキャンオーダ保持部102では、Block A及びBの入力による係数位置の入れ替えは起きないため、Term2においても変更されない。並列処理判定部104は、スキャンオーダ保持部102より出力される係数位置情報及びスキャン状態保持部103より出力される統計情報に基づいて図15に示されたフローに従って並列処理すを決定し、それを制御信号としてスキャン変換部101及びスキャン状態保持部103へと出力する。Term2においては、図１７のTerm2に示されるようにスキャン順序が入れ替わる可能性のある個所が存在するため、並列処理判定部104は逐次処理を示す並列制御信号を出力する。また同じくTerm2においてスキャン状態保持部103では、並列制御信号が逐次処理を示しているので、次の統計情報として、現在保持中の統計情報に対しBlock C入力の有意係数に対応する情報のみ更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock C入力の有意係数に対応する位置は、図１７のTerm2の黒丸で示されている。スキャンオーダ保持部102では、スキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term2においてスキャン変換部101では、Term1において行ったBlock A及びBのスキャン変換処理の結果を、変換データ出力#1及び#2として出力する。また並列処理判定部104より出力された並列制御信号は逐次処理を示しているので、スキャン変換部101はBlock Cのみを、スキャンオーダ保持部102より出力された係数位置情報に従って並び替える。
【００６５】
次にTerm3において、ブロックデータ#1としてBlock Dが、ブロックデータ#2としてBlock Eが、スキャン変換部101及びスキャン状態保持部103へと入力される。スキャン状態保持部103では、Term2において逐次処理がなされ、かつ図１７の中で黒丸で示された位置の係数がBlock Cの有意係数であったため、対応する位置の統計情報が図１７のTerm3に示されたような値に更新される。またスキャンオーダ保持部102では、Block Cの入力による係数位置の入れ替えが発生したため、図１７のTerm3に示されるごとく係数位置の情報が更新される。並列処理判定部104はTerm3において、次の状態でスキャン順序が入れ替わる可能性のある個所が存在しないため、図１５に示されたフローに従って並列処理（P=2）を示す並列制御信号をスキャン変化部101及びスキャン状態保持部103へと出力する。またTerm3においてスキャン状態保持部103では、並列制御信号が並列処理を示しているので、次の統計情報として現在保持中の統計情報に対しBlock D及びE入力の有意係数に対応する情報を更新してスキャンオーダ保持部102へと出力する。当該更新されるBlock D及びE入力の有意係数に対応する位置は、図１７のTerm3の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term3においてスキャン変換部101は、Term2において行ったBlock Cのスキャン変換処理結果を、変換データ出力#1出力する。またスキャン変換部101は、Block Bのスキャン変換処理結果を保持して変換データ出力#2へと出力する。また並列処理判定部104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101は、Block D及びEをスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。
【００６６】
次に、Term4において、ブロックデータ#1としてBlock Fが、ブロックデータ#2としてBlock Gが、スキャン変換部101及びスキャン状態保持部103へと入力される。スキャン状態保持部103では、Term3において並列処理がなされ、かつ図１７で黒丸及び白丸で示された位置の係数が有意係数であったため、対応する位置の統計情報を図１７のTerm4に示されたような値に更新する。またスキャンオーダ保持部102では、Block D及びEの入力による係数位置の入れ替えは起きないため、Term4においても変更されない。並列処理判定部104においては、スキャンオーダ保持部102より出力される係数位置情報及びスキャン状態保持部103より出力される統計情報に基いて、図１５に示されたフローに従って並列制御信号を101及び103へと出力する。Term4においては、図１７のTerm4に示されるようにスキャン順序が入れ替わる可能性のある個所が存在する。このため、並列処理判定部104は逐次処理を示す並列制御信号を出力する。またTerm4においてスキャン状態保持部103では、並列制御信号が逐次処理を示しているので、次の統計情報として、現在保持中の統計情報に対しBlock F入力の有意係数に対応する情報のみ更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock F入力の有意係数に対応する位置は、図１７のTerm4の黒丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term4においてスキャン変換部101は、Term3において行ったBlock D及びEのスキャン変換処理結果を、変換データ出力#1及び#2として出力する。また並列処理判定部104より出力された並列制御信号は逐次処理を示しているので、スキャン変換部101はBlock Fのみをスキャンオーダ保持部102より出力された係数位置情報に従って並び替える。
【００６７】
次に、Term5において、ブロックデータ#1としてBlock Gが、ブロックデータ#2としてBlock Hが、スキャン変換部101及びスキャン状態保持部103へと入力される。スキャン状態保持部103では、Term4において逐次処理がなされ、かつ図１７で黒丸で示された位置の係数がBlock Fの有意係数であったため、対応する位置の統計情報が図１７のTerm5に示されたような値に更新される。またスキャンオーダ保持部102では、Block Fの入力による係数位置の入れ替えは起きないため、Term5においても変更されない。並列処理判定部104はTerm5において、次の状態でスキャン順序が入れ替わる可能性のある個所が存在しないため、図１５に示されたフローに従って並列処理を示す並列制御信号をスキャン変換部101及びスキャン状態保持部103へと出力する。また同じくTerm5においてスキャン状態保持部103では、並列制御信号が並列処理を示しているため、次の統計情報として、現在保持中の統計情報に対しBlock G及びH入力の有意係数に対応する情報を更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock G及びH入力の有意係数に対応する位置は、図１７のTerm5の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term5においてスキャン変換部101は、Term4において行ったBlock Fのスキャン変換処理結果を、変換データ出力#1として出力する。またスキャン変化部101は、Block Eのスキャン変換処理結果を保持して変換データ出力#2へと出力する。また並列処理判定部104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101はBlock G及びHを、スキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。
【００６８】
以下、同様にスキャン変換処理を繰り返す。
【００６９】
次に、本実施形態の実施形態を構成する各部の構成及び動作について、それぞれ説明する。まず、スキャン変換部101内部の構成及び動作を、図１０を用いて説明する。
【００７０】
図１０は、スキャン変換部101の内部の構成例を示した図である。ブロックスキャン変換器#1(1011)は、ブロックデータ入力#1として入力した着目ブロック内のデータを、係数位置情報に従って並び替えを施し、変換データ出力#1として次のサイクルに出力する。ブロックスキャン変換器#2(1012)も同様で、ブロックデータ入力#2を係数位置情報に従って並び替えを施し、並列制御信号が並列処理指示を示す場合には変換データ出力#2として次のサイクルに出力する。また、並列制御信号が逐次処理指示を示す場合には、前サイクルの値を保持して変換データ出力#2として出力する。
【００７１】
次に、スキャンオーダ保持部102内部の構成及び動作を図１１を用いて説明する。
【００７２】
ソータ1021aは、係数a〜oの次の統計情報を表すnScanTotalsを、係数位置情報に応じてスキャン順に1〜15まで並べ替えて出力する。ソータ1021bは、係数b〜oの非ゼロ情報を、係数位置情報に応じてスキャン順に2〜15まで並べ替えて出力する。論理ORアレイ1022は、係数b〜oの有意係数情報#1及び係数b〜oの有意係数情報#2を、それぞれ互いに論理ORをとって係数b〜oの非ゼロ情報として出力する。マルチプレクサ1023は、図中'1'で示された入力と'0'で示された入力とのいずれかを、セレクト信号に従って選択して出力する。本実施形態ではセレクト信号が'1'であれば入力'1'を、'0'であれば入力'0'を選択して出力するものとしている。比較部1024はソータ1021aより出力されたnScanTotalsのうち、1021bより出力された非ゼロ情報が非ゼロを示している場合は、スキャン順で隣り合う2つ入力として値を比較し、小さい方を出力する。また比較部1024は、ソータ1021bより出力された非ゼロ情報が非ゼロを示していない場合は、スキャン順で前のnScanTotalsを出力する。また比較部1024は、ソータ1021bより出力された非ゼロ情報が非ゼロを示しており、かつスキャン順で前のnScanTotalsが小さい場合、マルチプレクサ1023へのセレクト信号として'1'を出力し、そうでなければ'0'を出力する。フリップフロップ1025は、マルチプレクサ1023からの出力を入力し、保持してスキャン順序1〜15の係数位置情報として出力する。
【００７３】
次に、スキャン状態保持部103内部の構成及び動作を、図１２を用いて説明する。
【００７４】
ブロック入力データ#1及び#2は、それぞれ係数a#1〜o#1及び係数a#2〜o#2へとスフ゜リットされて非ゼロ検出部1031a1〜1031o1及び1031a2〜1031o2へとそれぞれ入力される。非ゼロ検出部1031a1〜1031o1は、係数a#1〜o#1が0であるか否かをそれぞれ判別し、判別結果を係数a#1非ゼロ信号〜o#1非ゼロ信号として出力する。当該非ゼロ信号は、本実施形態においては非ゼロであった場合は'1'を、そうでない場合は'0'として出力されるものとする。非ゼロ検出部1031a2〜1031o2は、係数a#2〜o#2が0であるか否かをそれぞれ判別し、非ゼロであった場合には'1'を、そうでない場合は'0'として出力する。論理ANDゲート1032a〜1032oは、非ゼロ検出部1031a2〜1031o2の出力と並列制御信号入力との論理ANDをそれぞれとり、係数a#2非ゼロ信号〜o#2非ゼロ信号として出力する。本実施形態においては、並列制御信号は並列処理指示を'1'、逐次処理指示を'0’として示されるものとする。すなわち、当該並列制御信号が逐次処理指示を示している場合には、係数a#2非ゼロ信号〜o#2非ゼロ信号はいずれも'0'にマスクされる。また、当該係数a#1非ゼロ信号〜o#1非ゼロ信号及び係数a#2非ゼロ信号〜o#2非ゼロ信号はそれぞれ、有意係数情報#1及び#2として外部へ出力される。カウンタ1033a〜1033oは、それぞれ係数a〜oに対応するScanTotalsを保持する。カウンタ1033aは、係数a#1非ゼロ信号及び係数a#2非ゼロ信号を入力し、それぞれの状態に応じて内部状態をカウントアップして出力する。
【００７５】
図１３は、カウンタ1033a〜1033oに共通な内部構成例を図示したものである。フリップフロップ10331は、対応する係数のScanTotalsを保持して出力する。加算器10332は、フリップフロップ10331の出力に対して'1'を加算し、その加算結果をマルチプレクサ10334へと出力する。加算器10333はフリップフロップ10331の出力に対して'2'を加算し、その加算結果をマルチプレクサ10334へと出力する。マルチプレクサ10334は、#1非ゼロ入力及び#2非ゼロ入力の状態に応じて、フリップフロップ10331の出力、または、加算器10332の出力、または、加算器10333の出力のいずれかを選択してフリップフロップ10331へと出力する。また、マルチプレクサ10334の出力はScanTotalsの次の状態”nScanTotals”として、外部へと出力される。また、マルチプレクサ10334は#1非ゼロ入力が'1'かつ#2非ゼロ入力が'0'の場合は加算器10332の出力を、いずれも'1'の場合は加算器10333の出力を、その他の場合はフリップフロップ10331の出力をそれぞれ選択して出力する。カウンタ1033a同様、他のカウンタ1033b〜1033oも係数b〜o#1非ゼロ信号及び係数b〜o#2非ゼロ信号をそれぞれ入力し、それぞれの状態に応じて内部状態をカウントアップして出力する。カウンタ1033a〜1033oの出力である係数a〜oのScanTotalsは、次の統計情報として外部へと出力される。またカウンタ1033a〜1033oの出力である係数a〜oのScanTotalsは、統計情報として外部へと出力される。
【００７６】
次に、並列処理判定部104の内部の構成及び動作を、図１４を用いて説明する。
【００７７】
統計情報は係数a〜o ScanTotalsへとスプリットされてソータ1041へと入力される。ソータ1041は、係数a〜oのScanTotalsを、係数位置情報に応じてスキャン順に1〜15まで並べ替えて比較器1042へ出力する。比較器1042はスキャン順序1〜15のScanTotalsをそれぞれ比較し、比較結果を1043へと出力する。比較器1042は、複数の比較器10421が、図示されたごとく接続されてなる。比較器10421は、同図で上方からの入力値から1を引いた値が、下方からの入力値より小さい場合に'0'を、そうでない場合には'1'を比較結果として論理ＡＮＤゲート1043へと出力する。論理ANDゲート1043は、比較器1042より出力される全ての比較器10421の比較結果の論理ANDをとり、並列制御信号として外部へと出力する。この場合、並列制御信号は、並列処理指示を示す場合は'1'、逐次処理指示を示す場合は'0'となる。
【００７８】
［第２の実施形態］
次に、並列スキャン変換部206の第2の実施形態の構成について、図１８のブロック図を参照して説明する。
【００７９】
同図において、図１と実質的に同機能を有するものについては、同符を付した。従って、スキャン変換部101は、連続する2個のブロックデータ入力#1及び#2を受け取り、スキャン変換を行なって変換データ出力#1及び#2として出力する。またスキャン変換部101は、スキャンオーダー保持部102及び並列処理判定部2104に接続されている。スキャン変換部101はブロックデータ入力#1及び#2を、スキャンオーダ保持部102より受け取るスキャンオーダー情報に従ってスキャン変換を行う。そしてスキャン変換部101は、並列処理判定部2104より受け取る並列処理制御信号に従って変換データ出力#1のみを出力するか、または変換データ出力#1及び#2の両方を出力する。スキャンオーダー保持部102は、スキャン状態保持部103の出力する情報をもとに、スキャン順序を表すスキャンオーダー情報を生成して保持し、スキャン変換部101及び並列処理判定部2104及び有意データ位置情報生成部2105へ出力する。スキャン状態保持部103は、ブロックデータ入力#1及び#2を受け取り、次のスキャン状態及びスキャン状態を生成して保持し、次のスキャン状態をスキャンオーダ保持部102へ、スキャン状態を並列処理判定部2104へと出力する。並列処理判定部2104は、スキャンオーダ保持部102の出力するスキャンオーダー情報、及び、スキャン状態保持部103の出力するスキャン状態、及び、有意データ位置情報生成部2105の出力する有意データ位置情報を受け取る。そして並列処理判定部2104はこれらの情報に基いて、並列処理制御信号を生成し、スキャン変換部101及びスキャン状態保持部103へと出力する。有意データ位置情報生成部2105は、ブロックデータ入力#1及びスキャンオーダ保持部102の出力するスキャンオーダー情報を受け取り、各係数が有意係数であるか否かの情報をスキャン順に並べて有意データ位置情報として並列処理判定部2104へ出力する。
【００８０】
次に、本第２の実施形態の並列スキャン変換部206の動作について、図２２のタイミングチャート、及び、図２３の状態説明図、及び図１８を用いて説明する。
【００８１】
図２２では、Term1〜5の各期間におけるブロックデータ入力から変換データ出力までの各部の状態の変化を示している。Term1において、ブロックデータ#1としてBlock Aが、ブロックデータ#2としてBlock Bが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm1において、Block Aは有意データ位置情報生成部2105へも入力される。またTerm1では、スキャンオーダ保持部102内部で保持されているスキャンオーダー情報、及び、スキャン状態保持部103内部で保持されているスキャン状態は初期状態となっている。本第２の実施形態においては、スキャンオーダ保持部102及びスキャン状態保持部103における動作及びそれぞれの内部で扱う情報の意味は、第１の実施形態におけるスキャンオーダ保持部102及びスキャン状態保持部103のそれと同様であるので、説明は省略する。
【００８２】
図２３は、図２２のTerm1〜5の各期間における、スキャンオーダ保持部102内部で保持する係数位置、及び、スキャン状態保持部103内部で保持する統計情報、及び、ブロック入力#1及び#2の状態を表している。Term1において、係数位置及び統計情報は、図２３に示されるごとく初期化されている。ここへBlock A及びBが図２３に示される値で入力されたとする。図２３では図１７同様、入力されたブロック内の係数値のうち、有意係数が現れたブロック内の位置に対応するところに、黒丸及び白丸でマーキングされているので、参考にされたい。黒丸及び白丸の示す意味もまた、図１７と同様である。
【００８３】
Term1における統計情報の状態においては、ブロック内の何れの位置に有意係数が発生した場合でも、どのスキャン順序に対応する統計情報もそれより前の順序に対応する統計情報の値より大きくなることはない。そのため、Block A及びBはいずれも同一のスキャン順序でスキャン変換可能である。またTerm1において有意データ位置情報生成部2105は、Block Aの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104においては、スキャンオーダ保持部102より出力される係数位置情報及びスキャン状態保持部103より出力される統計情報及び有意データ位置情報生成部2105より出力される有意係数位置情報より並列処理可能と判定し、並列処理指示を示す信号をスキャン変換部101へと出力する。
【００８４】
ここで図２０は並列処理判定部2104の並列処理判定フローを示した図である。以下、図２０を用いて並列処理判定部2104の並列処理判定フローについて説明する。処理が開始されると、処理S21041において変数nに2が代入される。次に処理S21042において、変数tempに1番目のスキャン順序における統計情報ScanTotals(1)が代入される。次にS21043において、n番目のスキャン順序の係数が有意係数かつ、temp-N+1の値がn番目のスキャン順序の統計情報ScanTotals(n)の値より小さいか否かを判定する。当該条件に合致する場合、処理S21044へ、そうでない場合は処理S21045へと進む。ここでNは並列に入力されるブロックの数を表す。本実施形態においてはN=2となる。処理S21044において、逐次処理で行うよう判定される。処理S21044がなされると判定処理の終了となる。処理S21045において、変数tempにn番目のスキャン順序における統計情報ScanTotals(n)が代入されると、処理S21046が実行される。処理S21046において、ブロック内にまだ係数があるかどうかの確認がなされ、ある場合は処理S21047へ、そうでない場合は処理S21048へと進む。処理S21047において、変数nの値がインクリメントされ、処理S21043へと移行する。処理S21048においては、N並列で処理されるよう判定される。本第２の実施形態においてはN=2であるので、２並列で処理を行うよう判定される。処理S21048がなされると判定処理の終了となる。このように並列処理判定部2104では、統計情報ScanTotals及び有意係数であるか否かの情報をもとに、並列処理制御情報を生成する。
【００８５】
Term1の説明へと戻る。Term1において、スキャン変換部101は入力されたBlock A及びBを、スキャンオーダ保持部102より出力された係数位置情報及び並列処理判定部2104より出力された並列制御信号に従って、スキャン順序の並び替えを行う。Term1では並列処理判定部2104より出力された並列制御信号は並列処理を示しているので、Block A及びBはスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理が行われる。
【００８６】
次に、Term2において、ブロックデータ#1としてBlock Cが、ブロックデータ#2としてBlock Dが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm2において、Block Cは有意データ位置情報生成部2105へも入力される。スキャン状態保持部103では、Term1において並列処理がなされ、かつ図２３で黒丸及び白丸で示された位置の係数が有意係数であったため、対応する位置の統計情報が図２３のTerm2に示されたような値に更新される。またスキャンオーダ保持部102では、Block A及びBの入力による係数位置の入れ替えは起きないため、Term2においても変更されない。またTerm2において有意データ位置情報生成部2105は、Block Cの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104においては、スキャンオーダ保持部102より出力される係数位置情報、及び、スキャン状態保持部103より出力される統計情報、及び、有意データ位置情報生成部2105より出力される有意係数位置情報に基いて図２０に示されたフローに従って並列制御信号をスキャン変換部101、及び、スキャン状態保持部103へと出力する。Term2においては、図２３のTerm2に示されるようにスキャン順序が入れ替わる個所が存在するため、並列処理判定部2104は逐次処理を示す並列制御信号を出力する。また同じくTerm2においてスキャン状態保持部103では、並列制御信号が逐次処理を示しているので、次の統計情報として、現在保持中の統計情報に対しBlock C入力の有意係数に対応する情報のみ更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock C入力の有意係数に対応する位置は、図２３のTerm2の黒丸で示されている。スキャンオーダ保持部102では、スキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term2においてスキャン変換部101では、Term1において行ったBlock A及びBのスキャン変換処理の結果を、変換データ出力#1及び#2として出力する。また並列処理判定部2104より出力された並列制御信号は逐次処理を示しているので、スキャン変換部101はBlock Cのみをスキャンオーダ保持部102より出力された係数位置情報に従って並び替える。
【００８７】
次にTerm3において、ブロックデータ#1としてBlock Dが、ブロックデータ#2としてBlock Eが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm3において、Block Dは有意データ位置情報生成部2105へも入力される。スキャン状態保持部103では、Term2において逐次処理がなされ、かつ図２３の中で黒丸で示された位置の係数がBlock Cの有意係数であったため、対応する位置の統計情報が図２３のTerm3に示されたような値に更新される。またスキャンオーダ保持部102では、Block Cの入力による係数位置の入れ替えが発生したため、図２３のTerm3に示されるごとく係数位置の情報が更新される。またTerm3において有意データ位置情報生成部2105は、Block Dの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104はTerm3において、次の状態でスキャン順序が入れ替わる個所が存在しないため、図２０に示されたフローに従って並列処理を示す並列制御信号をスキャン変換部101及びスキャン状態保持部103へと出力する。またTerm3においてスキャン状態保持部103では、並列制御信号が並列処理を示しているので、次の統計情報として現在保持中の統計情報に対しBlock D及びE入力の有意係数に対応する情報を更新してスキャンオーダ保持部102へと出力する。当該更新されるBlock D及びE入力の有意係数に対応する位置は、図２３のTerm3の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term3においてスキャン変換部101は、Term2において行ったBlock Cのスキャン変換処理結果を、変換データ出力#1出力する。またスキャン変換部101は、Block Bのスキャン変換処理結果を保持して変換データ出力#2へと出力する。また並列処理判定部2104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101はBlock D及びEをスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。
【００８８】
次に、Term4において、ブロックデータ#1としてBlock Fが、ブロックデータ#2としてBlock Gが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm4において、Block Fは有意データ位置情報生成部2105へも入力される。スキャン状態保持部103では、Term3において並列処理がなされ、かつ図２３で黒丸及び白丸で示された位置の係数が有意係数であったため、対応する位置の統計情報が図２３のTerm4に示されたような値に更新される。またスキャンオーダ保持部102では、Block D及びEの入力による係数位置の入れ替えは起きないため、Term4においても変更されない。またTerm4において有意データ位置情報生成部2105は、Block Fの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104においては、スキャンオーダ保持部102より出力される係数位置情報及びスキャン状態保持部103より出力される統計情報に基いて、図２０に示されたフローに従って並列制御信号をスキャン変換部101及びスキャン状態保持部103へと出力する。Term4においては、図２３のTerm4に示されるように統計情報は同じ個所があるが有意係数でないため、係数位置の入れ替わりは発生しないと判定され、並列処理判定部2104は逐次処理を示す並列制御信号を出力する。またTerm4においてスキャン状態保持部103では、並列制御信号が並列処理を示しているので、次の統計情報として現在保持中の統計情報に対しBlock F及びG入力の有意係数に対応する情報を更新してスキャンオーダ保持部102へと出力する。当該更新されるBlock F及びG入力の有意係数に対応する位置は、図２３のTerm4の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term4においてスキャン変換部101は、Term3において行ったBlock D及びEのスキャン変換処理結果を、変換データ出力#1及び#2として出力する。また並列処理判定部2104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101はBlock F及びGをスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。
【００８９】
次に、Term5において、ブロックデータ#1としてBlock Hが、ブロックデータ#2としてBlock Iが、スキャン変換部101及びスキャン状態保持部103へと入力される。またTerm5において、Block Hは有意データ位置情報生成部2105へも入力される。スキャン状態保持部103では、Term4において並列処理がなされ、かつ図２３で黒丸及び白丸で示された位置の係数が有意係数であったため、対応する位置の統計情報が図２３のTerm5に示されたような値に更新される。またスキャンオーダ保持部102では、Block F及びGの入力による係数位置の入れ替えは起きないため、Term5においても変更されない。またTerm5において有意データ位置情報生成部2105は、Block Hの各係数が有意係数であるか否かの情報を生成し、スキャンオーダ保持部102の出力する係数位置情報に基いてスキャン順に並べて有意係数位置情報として並列処理判定部2104へと出力する。並列処理判定部2104はTerm5において、次の状態でスキャン順序が入れ替わる個所が存在しないため、図２０に示されたフローに従って並列処理を示す並列制御信号をスキャン変換部101及びスキャン状態保持部103へと出力する。また同じくTerm5においてスキャン状態保持部103では、並列制御信号が並列処理を示しているため、次の統計情報として、現在保持中の統計情報に対しBlock H及びI入力の有意係数に対応する情報を更新して、スキャンオーダ保持部102へと出力する。当該更新されるBlock H及びI入力の有意係数に対応する位置は、図２３のTerm5の黒丸及び白丸で示されている。スキャンオーダ保持部102ではスキャン状態保持部103より出力された次の状態の統計情報を用いて、係数位置情報を決定する。Term5においてスキャン変換部101は、Term3において行ったBlock F及びGのスキャン変換処理結果を、変換データ出力#1及び#2として出力する。また並列処理判定部2104より出力された並列制御信号は並列処理を示しているので、スキャン変換部101はBlock H及びIをスキャンオーダ保持部102より出力された係数位置情報に従って並列に並び替え処理を行う。以下、同様にスキャン変換処理を繰り返す。
【００９０】
次に、本第２の実施形態の実施形態を構成する各部の構成及び動作について、それぞれ説明する。スキャン変換部101、スキャンオーダ保持部102、及びスキャン状態保持部103については、第１の実施形態と同じであるので、その説明を省略する。
【００９１】
並列処理判定部2104内部の構成及び動作を、図１９を用いて説明する。
【００９２】
同図において、統計情報入力は係数a〜oのScanTotalsへとスプリットされて、ソータ1041へと入力される。ソータ1041は、係数a〜oのScanTotalsを、係数位置情報に応じてスキャン順に1〜15まで並べ替えて比較器1042へと出力する。比較器1042はスキャン順序1〜15のScanTotalsをそれぞれ比較し、比較結果を並列処理判定部21045へと出力する。比較器1042に関する説明は第１の実施形態のそれと同じであるので、説明を省略する。有意係数情報入力はスキャン順序2〜15の非ゼロ情報へとスプリットされて、並列処理判定部21044へと入力される。並列処理判定部21044は複数の論理反転ゲートであり、スキャン順序2〜15の非ゼロ情報をそれぞれ論理反転して、並列処理判定部21045へと出力する。並列処理判定部21045は複数の論理ORゲートで構成され、比較器1042内の全ての比較器10421の比較結果と並列処理判定部21044より出力されるスキャン順序2〜15の非ゼロ情報の論理反転結果との論理ORをとり、出力する。論理AND1043であり、並列処理判定部21045より出力される全ての出力の論理ANDをとり、並列制御信号として外部へと出力する。この場合、並列制御信号は、並列処理指示を示す場合は'1'、逐次処理指示を示す場合は'0'となる。
【００９３】
次に、第２の実施形態における、有意データ位置情報生成部2105内部の構成及び動作を図２１を用いて説明する。
【００９４】
ブロックデータ入力#1は係数a#1〜o#1へとスプリットされて、それぞれスキャン状態保持部1031a〜スキャン状態保持部1031oへと入力される。スキャン状態保持部1031a1〜スキャン状態保持部1031o1は、係数a#1〜o#1が0であるか否かをそれぞれ判別し、判別結果を係数a#1非ゼロ信号〜o#1非ゼロ信号として出力する。当該非ゼロ信号は、本第２の実施形態においては非ゼロであった場合に'1'を、そうでない場合は'0'として出力されるものとする。有意データ位置情報生成部21052はソータであり、係数a#1〜o#1を、係数位置情報に応じてスキャン順に1〜15まで並べ替えて、スキャン順序1〜15の非ゼロ情報として出力する。スキャン順序1〜15の非ゼロ情報は有意係数情報として、外部へと出力される。
【００９５】
以上本発明に係る実施形態を説明した。なお、本実施形態では、スキャン変換対しようの２次元配列のブロックのサイズを４×４画素サイズとし、その内の１５のＡＣ成分を例にして説明したが、これに限定されるものではない。ブロックサイズは一般にn行m列、もしくはｍ×ｎ個のデータで表わせ、その中のＮ個（Ｎは2以上）のブロックのスキャン変換処理をＭ（Mは1以上N以下の整数） 並列で行うよう指示できれば良い。
【００９６】
また、実施形態では、図７(ａ),(b)に示すように、統計情報ScanTotals()と、係数位置ScanOrder()とを別々にテーブルとして管理する例を説明したが、統計情報と係数位置とをペアとして扱われるので、これらを１つのテーブルで管理するようにしても良い。
【００９７】
また、実施形態では、本発明の装置がカメラの内部の符号化部に収容されるものとして説明したが、これによっても本願発明が限定されるものではない。
【特許請求の範囲】
【請求項１】
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える装置であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記スキャン状態保持手段に保持されたスキャン状態に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、スキャン変換装置。
【請求項２】
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える装置であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記ブロック内に存在する有意データの位置情報を生成する有意データ位置情報生成手段と、
前記スキャン状態保持手段に保持されたスキャン状態及び有意データ位置情報生成手段より出力された位置情報に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、スキャン変換装置。
【請求項３】
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える方法であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持工程と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持工程と、
前記スキャン状態保持工程で保持されたスキャン状態に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定工程と、
前記並列処理判定工程の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持工程に保持されたスキャン順序に従って並べ替えを行うスキャン変換工程と、
を有することを特徴とする、スキャン変換方法。
【請求項４】
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える工程であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持工程と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持工程と、
前記ブロック内に存在する有意データの位置情報を生成する有意データ位置情報生成工程と、
前記スキャン状態保持工程に保持されたスキャン状態及び有意データ位置情報生成工程より出力された位置情報に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定工程と、
前記並列処理判定工程の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持工程に保持されたスキャン順序に従って並べ替えを行うスキャン変換工程と、
を有することを特徴とする、スキャン変換方法。
【請求項５】
画像をn行m列より構成されるブロックの単位に分割する画像分割手段と、
前記画像分割手段より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換手段と、
前記直交変換手段より出力される変換係数に対し、量子化処理を施し量子化変換係数を出力する量子化手段と、
前記量子化手段より出力される量子化変換係数を、前記ブロックの単位で並べ替えて出力するスキャン変換手段と、
前記スキャン変換手段より出力される量子化変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化手段と、
を有し、前記スキャン変換手段は、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記スキャン状態保持手段に保持されたスキャン状態に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、画像符号化装置。
【請求項６】
画像をn行m列より構成されるブロックの単位に分割する画像分割手段と、
前記画像分割手段より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換手段と、
前記直交変換手段より出力される変換係数に対し、量子化処理を施し量子化変換係数を出力する量子化手段と、
前記量子化手段より出力される量子化変換係数を、前記ブロックの単位で並べ替えて出力するスキャン変換手段と、
前記スキャン変換手段より出力される量子化変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化手段と、
を有し、前記スキャン変換手段は、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記ブロック内に存在する有意データの位置情報を生成する有意データ位置情報生成手段と、
前記スキャン状態保持手段に保持されたスキャン状態及び有意データ位置情報生成手段より出力された位置情報に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、画像符号化装置。
【請求項７】
画像をn行m列より構成されるブロックの単位に分割する画像分割工程と、
前記画像分割工程より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換工程と、
前記直交変換工程より出力される変換係数に対し、量子化処理を施し量子化変換係数を出力する量子化工程と、
前記量子化工程より出力される量子化変換係数を、前記ブロックの単位で並べ替えて出力するスキャン変換工程と、
前記スキャン変換工程より出力される量子化変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化工程と、
を有し、前記スキャン変換工程は、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持工程と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持工程と、
前記スキャン状態保持工程に保持されたスキャン状態に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定工程と、
前記並列処理判定工程の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持工程に保持されたスキャン順序に従って並べ替えを行うスキャン変換工程と、
を有することを特徴とする、画像符号化方法。
【請求項８】
画像をn行m列より構成されるブロックの単位に分割する画像分割工程と、
前記画像分割工程より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換工程と、
前記直交変換工程より出力される変換係数に対し、量子化処理を施し量子化変換係数を出力する量子化工程と、
前記量子化工程より出力される量子化変換係数を、前記ブロックの単位で並べ替えて出力するスキャン変換工程と、
前記スキャン変換工程より出力される量子化変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化工程と、
を有し、前記スキャン変換工程は、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持工程と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持工程と、
前記ブロック内に存在する有意データの位置情報を生成する有意データ位置情報生成工程と、
前記スキャン状態保持工程に保持されたスキャン状態及び有意データ位置情報生成工程より出力された位置情報に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM（Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定工程と、
前記並列処理判定工程の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持工程に保持されたスキャン順序に従って並べ替えを行うスキャン変換工程と、
を有することを特徴とする、画像符号化方法。
【請求項９】
ランレングス符号化するため、ｍ×ｎ個のデータで構成される２次元配列のブロックにおけるＮ個のデータをスキャンし、１次元配列のデータに変換し、出力することを繰り返し実行するスキャン変換装置であって、
前記ｍ×ｎ個のデータにおけるスキャン対象のデータの位置と、当該位置における非ゼロとなる統計的な出現頻度値をペアにして、前記スキャン対象のデータの前記出現頻度値について降順に並べられた初期の並び替え情報を設定する設定手段と、
互いに並列に実行可能な複数のスキャン変換手段と、
ここで、各スキャン変換手段は、前記並び替え情報に従ったデータ位置の順に、着目ブロック内のデータを順に読出して出力すると共に、前記読出したデータが非ゼロであった場合には当該データの位置における出現頻度値を増加させる；
前記並び替え情報において、出現頻度値が昇順となる箇所があった場合、当該昇順となると判定された２つのペアを交換することで、前記並び替え情報を降順になるよう更新する更新手段と、
前記並び替え情報を解析し、前記更新手段による交換処理が行われるまでの最も少ないブロック数Ｐ（Ｐ≧１）を判定する判定手段と、
前記複数のスキャン変換手段におけるＰ個に対し、連続するＰ個のブロックデータについて並列に１次元配列への変換を実行させるスキャン制御手段と
を備えることを特徴とするスキャン変換装置。
【請求項１０】
並び替え情報に従ったデータ位置の順に、着目ブロック内のデータを順に読出して出力すると共に、前記読出したデータが非ゼロであった場合には当該データの位置における出現頻度値を増加させる、互いに並列に実行可能な複数のスキャン変換手段を有し、ランレングス符号化するため、ｍ×ｎ個のデータで構成される２次元配列のブロックを、少なくとも１つのスキャン変換手段を用いてスキャンし、１次元配列のデータに変換し、出力することを繰り返し実行するスキャン変換装置の制御方法であって、
前記ｍ×ｎ個のデータにおけるスキャン対象のデータの位置と、当該位置における非ゼロとなる統計的な出現頻度値をペアにして、前記スキャン対象のデータの前記出現頻度値について降順に並べられた初期の並び替え情報を設定する設定工程と、
前記並び替え情報において、出現頻度値が昇順となる箇所があった場合、当該昇順となると判定された２つのペアを交換することで、前記並び替え情報を降順になるよう更新する更新工程と、
前記並び替え情報を解析し、前記更新工程による交換処理が行われるまでの最も少ないブロック数Ｐ（Ｐ≧１）を判定する判定工程と、
前記複数のスキャン変換手段におけるＰ個に対し、連続するＰ個のブロックデータについて並列に１次元配列への変換を実行させるスキャン制御工程と
を備えることを特徴とするスキャン変換装置の制御方法。
【請求項１】
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える装置であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記スキャン状態保持手段に保持されたスキャン状態に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、スキャン変換装置。
【請求項２】
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える装置であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記ブロック内に存在する有意データの位置情報を生成する有意データ位置情報生成手段と、
前記スキャン状態保持手段に保持されたスキャン状態及び有意データ位置情報生成手段より出力された位置情報に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、スキャン変換装置。
【請求項３】
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える方法であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持工程と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持工程と、
前記スキャン状態保持工程で保持されたスキャン状態に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定工程と、
前記並列処理判定工程の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持工程に保持されたスキャン順序に従って並べ替えを行うスキャン変換工程と、
を有することを特徴とする、スキャン変換方法。
【請求項４】
n行m列より構成されるブロック内のデータを所定のスキャン順序で並べ替える工程であって、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持工程と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持工程と、
前記ブロック内に存在する有意データの位置情報を生成する有意データ位置情報生成工程と、
前記スキャン状態保持工程に保持されたスキャン状態及び有意データ位置情報生成工程より出力された位置情報に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定工程と、
前記並列処理判定工程の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持工程に保持されたスキャン順序に従って並べ替えを行うスキャン変換工程と、
を有することを特徴とする、スキャン変換方法。
【請求項５】
画像をn行m列より構成されるブロックの単位に分割する画像分割手段と、
前記画像分割手段より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換手段と、
前記直交変換手段より出力される変換係数に対し、量子化処理を施し量子化変換係数を出力する量子化手段と、
前記量子化手段より出力される量子化変換係数を、前記ブロックの単位で並べ替えて出力するスキャン変換手段と、
前記スキャン変換手段より出力される量子化変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化手段と、
を有し、前記スキャン変換手段は、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記スキャン状態保持手段に保持されたスキャン状態に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、画像符号化装置。
【請求項６】
画像をn行m列より構成されるブロックの単位に分割する画像分割手段と、
前記画像分割手段より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換手段と、
前記直交変換手段より出力される変換係数に対し、量子化処理を施し量子化変換係数を出力する量子化手段と、
前記量子化手段より出力される量子化変換係数を、前記ブロックの単位で並べ替えて出力するスキャン変換手段と、
前記スキャン変換手段より出力される量子化変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化手段と、
を有し、前記スキャン変換手段は、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持手段と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持手段と、
前記ブロック内に存在する有意データの位置情報を生成する有意データ位置情報生成手段と、
前記スキャン状態保持手段に保持されたスキャン状態及び有意データ位置情報生成手段より出力された位置情報に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定手段と、
前記並列処理判定手段の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持手段に保持されたスキャン順序に従って並べ替えを行うスキャン変換手段と、
を有することを特徴とする、画像符号化装置。
【請求項７】
画像をn行m列より構成されるブロックの単位に分割する画像分割工程と、
前記画像分割工程より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換工程と、
前記直交変換工程より出力される変換係数に対し、量子化処理を施し量子化変換係数を出力する量子化工程と、
前記量子化工程より出力される量子化変換係数を、前記ブロックの単位で並べ替えて出力するスキャン変換工程と、
前記スキャン変換工程より出力される量子化変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化工程と、
を有し、前記スキャン変換工程は、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持工程と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持工程と、
前記スキャン状態保持工程に保持されたスキャン状態に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM （Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定工程と、
前記並列処理判定工程の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持工程に保持されたスキャン順序に従って並べ替えを行うスキャン変換工程と、
を有することを特徴とする、画像符号化方法。
【請求項８】
画像をn行m列より構成されるブロックの単位に分割する画像分割工程と、
前記画像分割工程より出力されるブロックの単位で直交変換を施し、変換係数を出力する直交変換工程と、
前記直交変換工程より出力される変換係数に対し、量子化処理を施し量子化変換係数を出力する量子化工程と、
前記量子化工程より出力される量子化変換係数を、前記ブロックの単位で並べ替えて出力するスキャン変換工程と、
前記スキャン変換工程より出力される量子化変換係数に対して、エントロピー符号化を施し符号化ストリームを出力するエントロピー符号化工程と、
を有し、前記スキャン変換工程は、
前記ブロック内のデータの状態に応じて、現在のスキャンの状態を更新して保持しておくスキャン状態保持工程と、
前記スキャンの状態に応じて、スキャン順序を更新して保持しておくスキャンオーダ保持工程と、
前記ブロック内に存在する有意データの位置情報を生成する有意データ位置情報生成工程と、
前記スキャン状態保持工程に保持されたスキャン状態及び有意データ位置情報生成工程より出力された位置情報に応じて、N（Nは2以上の整数）個の前記ブロックのスキャン変換処理をM（Mは1以上N以下の整数） 並列で行うよう指示する並列処理判定工程と、
前記並列処理判定工程の指示に従って、前記ブロック内のデータを前記スキャンオーダ保持工程に保持されたスキャン順序に従って並べ替えを行うスキャン変換工程と、
を有することを特徴とする、画像符号化方法。
【請求項９】
ランレングス符号化するため、ｍ×ｎ個のデータで構成される２次元配列のブロックにおけるＮ個のデータをスキャンし、１次元配列のデータに変換し、出力することを繰り返し実行するスキャン変換装置であって、
前記ｍ×ｎ個のデータにおけるスキャン対象のデータの位置と、当該位置における非ゼロとなる統計的な出現頻度値をペアにして、前記スキャン対象のデータの前記出現頻度値について降順に並べられた初期の並び替え情報を設定する設定手段と、
互いに並列に実行可能な複数のスキャン変換手段と、
ここで、各スキャン変換手段は、前記並び替え情報に従ったデータ位置の順に、着目ブロック内のデータを順に読出して出力すると共に、前記読出したデータが非ゼロであった場合には当該データの位置における出現頻度値を増加させる；
前記並び替え情報において、出現頻度値が昇順となる箇所があった場合、当該昇順となると判定された２つのペアを交換することで、前記並び替え情報を降順になるよう更新する更新手段と、
前記並び替え情報を解析し、前記更新手段による交換処理が行われるまでの最も少ないブロック数Ｐ（Ｐ≧１）を判定する判定手段と、
前記複数のスキャン変換手段におけるＰ個に対し、連続するＰ個のブロックデータについて並列に１次元配列への変換を実行させるスキャン制御手段と
を備えることを特徴とするスキャン変換装置。
【請求項１０】
並び替え情報に従ったデータ位置の順に、着目ブロック内のデータを順に読出して出力すると共に、前記読出したデータが非ゼロであった場合には当該データの位置における出現頻度値を増加させる、互いに並列に実行可能な複数のスキャン変換手段を有し、ランレングス符号化するため、ｍ×ｎ個のデータで構成される２次元配列のブロックを、少なくとも１つのスキャン変換手段を用いてスキャンし、１次元配列のデータに変換し、出力することを繰り返し実行するスキャン変換装置の制御方法であって、
前記ｍ×ｎ個のデータにおけるスキャン対象のデータの位置と、当該位置における非ゼロとなる統計的な出現頻度値をペアにして、前記スキャン対象のデータの前記出現頻度値について降順に並べられた初期の並び替え情報を設定する設定工程と、
前記並び替え情報において、出現頻度値が昇順となる箇所があった場合、当該昇順となると判定された２つのペアを交換することで、前記並び替え情報を降順になるよう更新する更新工程と、
前記並び替え情報を解析し、前記更新工程による交換処理が行われるまでの最も少ないブロック数Ｐ（Ｐ≧１）を判定する判定工程と、
前記複数のスキャン変換手段におけるＰ個に対し、連続するＰ個のブロックデータについて並列に１次元配列への変換を実行させるスキャン制御工程と
を備えることを特徴とするスキャン変換装置の制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２０１０−１９３０９７（Ｐ２０１０−１９３０９７Ａ）
【公開日】平成２２年９月２日（２０１０．９．２）
【国際特許分類】
【出願番号】特願２００９−３４３９０（Ｐ２００９−３４３９０）
【出願日】平成２１年２月１７日（２００９．２．１７）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２２年９月２日（２０１０．９．２）
【国際特許分類】
【出願日】平成２１年２月１７日（２００９．２．１７）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]