(57)【要約】【課題】符号化対象部分の周辺部分のデータに基づいて符号化対象部分の符号化を行う符号化装置において、符号化処理の高速化を図る。【解決手段】入力画像データを分割し、各分割部分を異なるメモリに分散して記憶させる。また、ｎ番目の分割部分を記憶させる際、ｎ−１番目の分割部分に含まれるデータのうち、ｎ番目の分割部分における符号化対象部分を符号化処理する際に参照する周辺部分を含む部分のデータを、ｎ番目の分割部分に付加して記憶させる。【選択図】図１
2008153779.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上の記憶部を備えたデータ記憶部と、入力データを複数の分割部分に分割し、上記複数の分割部分を上記１つ以上の記憶部に分割させた状態で記憶させる記憶制御手段と、上記データ記憶部から読み出した入力データの符号化処理を行う符号化手段とを備え、上記符号化手段が上記符号化処理時に入力データにおける符号化対象部分の周辺部分のデータを参照し、この周辺部分のデータに応じて上記符号化対象部分の符号を決定する符号化装置であって、
上記記憶制御手段は、
上記入力データを第１〜第ｍ分割部分（ｍは２以上の整数）に分割し、
第ｎ分割部分（ｎは２以上ｍ以下の整数）を上記記憶部に記憶させる際、第ｎ分割部分とは異なる第ｎ−１分割部分に含まれるデータのうち、上記第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、上記第ｎ分割部分に付加して上記記憶部に記憶させることを特徴とする符号化装置。
【請求項２】
上記ｎは入力データの先頭側の分割部分から順に付される整数であり、
上記記憶制御部は、
上記第ｎ分割部分を上記記憶部に記憶させる際、上記第ｎ−１分割部分に含まれるデータの末尾部分を、上記第ｎ分割部分の先頭に付加して上記記憶部に記憶させることを特徴とする請求項１に記載の符号化装置。
【請求項３】
上記記憶制御部は、
上記第ｎ分割部分に付加するデータを、上記符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分の範囲を示すコンテクストに応じて設定することを特徴とする請求項１に記載の符号化装置。
【請求項４】
上記入力データは、行方向および列方向にマトリックス状に配された複数の画素のデータを含む画像データであり、
上記コンテクストは、上記符号化対象部分を含む行である第１ラインの一部と上記第１ラインに隣接する行である第２ラインの一部とを上記周辺部分の範囲とする２ラインテンプレート、または、上記第１ラインの一部と上記第２ラインの一部と上記第２ラインに対して上記第１ラインとは反対側に隣接する行である第３ラインの一部とを上記周辺部分の範囲とする３ラインテンプレートであり、
上記ｎは入力データの先頭側の分割部分から順に付される整数であり、
上記記憶制御部は、上記コンテクストが２ラインテンプレートである場合には上記第ｎ分割部分に付加するデータを上記第ｎ−１分割部分における末尾１ラインとし、上記コンテクストが３ラインテンプレートである場合には上記第ｎ分割部分に付加するデータを上記第ｎ−１分割部分における末尾２ラインとすることを特徴とする請求項３に記載の符号化装置。
【請求項５】
上記コンテクストは、上記入力データを一定のビット数毎に折り返すことで上記入力データを仮想的に複数のラインからなる２次元データとみなしたときに、上記符号化対象部分を含むラインである第１ラインの一部と上記第１ラインに隣接するラインである第２ラインの一部とを上記周辺部分の範囲とする２ラインテンプレート、または、上記第１ラインの一部と上記第２ラインの一部と上記第２ラインに対して上記第１ラインとは反対側に隣接するラインである第３ラインの一部とを上記周辺部分の範囲とする３ラインテンプレートであり、
上記ｎは入力データの先頭側の分割部分から順に付される整数であり、
上記記憶制御部は、上記コンテクストが２ラインテンプレートである場合には上記第ｎ分割部分に付加するデータを上記第ｎ−１分割部分における末尾１ラインとし、上記コンテクストが３ラインテンプレートである場合には上記第ｎ分割部分に付加するデータを上記第ｎ−１分割部分における末尾２ラインとすることを特徴とする請求項３に記載の符号化装置。
【請求項６】
上記符号化手段は、上記第ｎ分割部分の符号化処理を行う際、この第ｎ分割部分に付加された上記データを除くデータに対して符号化処理を行うことを特徴とする請求項１に記載の符号化装置。
【請求項７】
上記符号化手段は、算術符号化処理を行うことを特徴とする請求項１に記載の符号化装置。
【請求項８】
上記符号化手段は、ＪＢＩＧ、ＪＢＩＧ２、ＪＰＥＧ、ＪＰＥＧ  ２０００のいずれかで規定されている符号化方法を用いて上記算術符号化処理を行うことを特徴とする請求項７に記載の符号化装置。
【請求項９】
入力データを複数の分割部分に分割する分割工程と、上記複数の分割部分をデータ記憶部に備えられる１つ以上の記憶部に分割させた状態で記憶させる記憶工程と、上記記憶部から読み出した入力データの符号化処理を行う符号化工程とを含み、上記符号化処理時に入力データにおける符号化対象部分の周辺部分のデータを参照し、この周辺部分のデータに応じて上記符号化対象部分の符号を決定する符号化方法であって、
上記分割工程では、上記入力データを第１〜第ｍ分割部分（ｍは２以上の整数）に分割し、
上記記憶工程では、第ｎ分割部分（ｎは２以上ｍ以下の整数）を上記記憶部に記憶させる際、第ｎ分割部分とは異なる第ｎ−１分割部分に含まれるデータのうち、上記第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、上記第ｎ分割部分に付加して上記記憶部に記憶させることを特徴とする符号化方法。
【請求項１０】
請求項１〜８のいずれか１項に記載の符号化装置を動作させるプログラムであって、コンピュータを上記各手段として機能させるためのプログラム。
【請求項１１】
請求項１０に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力データにおける符号化対象部分の周辺部分のデータを参照し、この周辺部分のデータに応じて符号化対象部分の符号を決定する符号化装置および符号化方法に関するものである。
【背景技術】
【０００２】
データを高圧縮率で圧縮（符号化）する方法として、例えばＪＢＩＧ，ＪＢＩＧ２，ＪＰＥＧ，ＪＰＥＧ２０００等のように、圧縮対象セル（圧縮対象画素；符号化対象部分）の近傍セル（周辺画素；周辺部分）のデータに基づいて圧縮対象セルの値を予測し、その出現確率を用いて圧縮を行う方法（算術圧縮方法；算術符号化方法）が知られている。
【０００３】
これらの方法においては、対象セルの近傍セルを参照して、その近傍セルから対象セルを予測したときの予測値と実際の値とのずれを保存することによって対象セルの圧縮を行う。なお、この他にも符号化の際に符号化対象部分の周辺部分のデータを参照して符号化を行う数多くのアルゴリズムが知られている。
【０００４】
これらのアルゴリズムでは、データを２次元的に表現し、２ライン以上の形状を持つコンテクスト（近傍セルのパターン；近傍形あるいはテンプレートとも言う）を使用することが多い。元々２次元的なデータ（例えば画像データ）であれば、そのデータに対して２ライン以上の形状を持つコンテクストを適用できる。また、元々は２次元的なデータではない場合（例えば画像データ以外のデータ）であっても、そのデータを一定のビット数ごとに折り返すなどして仮想的に２次元データとして捉えれば２ライン以上のコンテクストを適用できる。
【０００５】
図８は、ＪＢＩＧで採用されている算術符号化方式であるＱＭ−Ｃｏｄｅｒを実装した従来の符号化装置２１の概略構成を示すブロック図である。また、図９は、符号化装置２１における符号化処理の流れを示すフローチャートである。
【０００６】
図８に示すように、符号化装置２１は、概略的に、コンテクスト生成部２２、取得部２３、算術符号化部２４、記録部２５、レジスタ２６、入力制御部４１、入力画像記憶部４２を備えている。
【０００７】
符号化装置２１に入力された画像データは、入力制御部４１によって入力画像記憶部４２に格納される。このとき、入力画像記憶部４２が複数のメモリからなり、連続した十分なメモリを確保できない場合、入力画像データは複数に分割され、別々のメモリに格納される。例えば、入力画像データの半分は入力画像記憶部４２の第１メモリ４３に格納され、入力画像データの残りの半分は入力画像記憶部４２の第２メモリ４４に格納される。その後、入力制御部４１は、入力画像記憶部４２に格納した入力画像データを順次読み出してコンテクスト生成部２２に送る。
【０００８】
コンテクスト生成部２２は、入力画像データを少なくとも１つ以上のストライプに分ける（Ｓ１５０）。ストライプとは、符号化処理を行う単位であり、画像中の１ライン以上の横ラインからなる。Ｓ１５０〜Ｓ１６０におけるストライプについてのループ（ＬＯＯＰ＿Ａ）によって、全てのストライプに対して処理が完了すると、画像全体の符号化が完了する。
【０００９】
コンテクスト生成部２２は、符号化対象となるセルを選択する（Ｓ１５１）。この対象セルの選択は、ストライプの左上から右下に向けて順次行う。Ｓ１５１〜Ｓ１６２のループにて対象セルについての符号化を行い、ストライプにおける全ての画素の処理が完了すると当該ストライプの処理が完了したことになる。
【００１０】
また、コンテクスト生成部２２は、入力画像データから、対象セルおよび対象セルの近傍セル（周辺画素）であるコンテクストのデータを抽出し（読み取り）、取得部２３に送信する（Ｓ１５２）。この際、対象セルと近傍セルとが別々のメモリに格納されている場合には、それぞれのメモリにアクセスすることになる。つまり、入力画像データが第１メモリ４３と第２メモリ４４とに分割して格納されている場合であって、対象セルと対象セルの一部とが第２メモリ４４の１ライン目である場合には、第２メモリ４４から対象セルと対象セルの一部とが抽出され、第１メモリ４３から残りの対象セルが抽出される。なお、コンテクストの読み取りの際、コンテクスト生成部２２は、２ラインテンプレートまたは３ラインテンプレートに基づいて読み取りを行う。ただし、図１０（ａ）に示すように対象セルが画像の上端近傍（この図の例では上端）であった場合、図１０（ｂ）に示すように左端近傍（この図の例では左端から４セル以内）であった場合、図１０（ｃ）に示すように右端近傍（この図の例では右端から２セル以内）であった場合等には、コンテクストが画像データの外側にはみ出してしまう。このため、コンテクストが画像データの外側部分にはみ出さないように特別な処理（例えば、コンテクストが画像データの外側にはみ出す部分については参照しないようにするとともに、画像データの外側にはみ出す部分には０を代入するといった処理）を行う必要がある。
【００１１】
次に、取得部２３が、コンテクスト生成部２２から送信された対象セルおよびコンテクストのデータに応じて、記録部２５の確率推定テーブル２７にアクセスして、コンテクストについての優勢確率シンボル（ＭＰＳ）および劣勢確率シンボル（ＬＰＳ）の確率推定値のインデックスＳＴを取得する（Ｓ１５３）。
【００１２】
次に、算術符号化部２４の前処理部３０に備えられる選択部３０ａが、入力される対象セルの値とＭＰＳとに応じて、対象セルがＭＰＳであるか否かを判別する（Ｓ１５４）。Ｓ１５４において対象セルがＭＰＳであると判別された場合には、算術符号化部２４の符号処理部２９において、ＭＰＳ処理部２９ａがＭＰＳ処理（ＣＯＤＥＭＰＳ：Ｓ１５５〜Ｓ１５８）を行う。一方、Ｓ１５４において対象セルがＬＰＳであると判別された場合には、算術符号化部２４の符号処理部２９において、ＬＰＳ処理部２９ｂがＬＰＳ処理（ＣＯＤＥＬＰＳ：Ｓ１５９〜Ｓ１６１）を行う。
【００１３】
次に、ＭＰＳ処理部２９ａが、記録部２５の確率推定表２８にアクセスして、劣勢確率シンボルの確率推定値のインデックスＳＴを用いて、劣勢確率シンボルの確率推定値を取得し、これに応じてレジスタ２６のＡｒｅｇ２６ａ、Ｃｒｅｇ２６ｂを書き換える（Ｓ１５５）。また、ＭＰＳ処理部２９ａは、Ａｒｅｇ２６ａの値が０．５未満であるか否かを判別して（Ｓ１５６）、０．５未満である場合にはＳ１５７に進み、０．５以上の場合にはＳ１６２に進む。Ｓ１５７ではＭＰＳ処理部２９ａがＲＥＮＯＲＭ処理部２９ｃに指示して、ＲＥＮＯＲＭ処理部２９ｃがレジスタ２６のＡｒｅｇ２６ａ、Ｃｒｅｇ２６ｂに対して正規化処理をし、得られた符号化データを必要に応じて出力する。ＭＰＳ処理部２９ａは、記録部２５の確率推定表２８を更新し（Ｓ１５８）、Ｓ１６２に進む。
【００１４】
一方、Ｓ１５４において対象セルがＬＰＳであると判別された場合には、ＬＰＳ処理部２９ｂが、記録部２５の確率推定表２８にアクセスして、劣勢確率シンボルの確率推定値のインデックスＳＴを用いて、劣勢確率シンボルの確率推定値を取得し、これに応じてレジスタ２６のＡｒｅｇ２６ａ、Ｃｒｅｇ２６ｂを書き換える（Ｓ１５９）。また、ＬＰＳ処理部２９ｂは、レジスタ２６のＡｒｅｇ２６ａ、Ｃｒｅｇ２６ｂに対して、確率推定表のＳＷＩＴＣＨの値に応じて、ＬＰＳとＭＰＳの入れ替えと符号出力を行う（Ｓ１６０）。すなわち、ＬＰＳ処理部２９ｂは、ＬＳＺのインデックスに対応する確率推定表のＳＷＩＴＣＨの値が１か否かによって、入れ替えを行うかどうかを判断する。さらに、ＬＰＳ処理部２９ｂは、記録部２５の確率推定表２８を更新し（Ｓ１６１）、Ｓ１６２に進む。
【００１５】
Ｓ１６２では、符号処理部２９がコンテクスト生成部２２に対してセルインクリメントの指示を行い、セルについてのループを終了する。このような手順をストライプの全てのセルに対して行うことで、ストライプの符号化を行う。Ｓ１６３では、コンテクスト生成部２２が、ストライプについての処理が終了したか否かを判別し、終了していた場合にはレジスタ２６から符号化データを出力する（フラッシュ処理：Ｓ１６３）。このように、次のストライプの符号化に進む前に、ここまでの符号化結果のうちで、まだ出力されていない部分を出力する。Ｓ１６４では、コンテクスト生成部２２が新たなストライプを選択する。全てのストライプの符号化が完了すれば画像全体の符号化が完了したことになり、入力画像データの全てを符号化した場合には、処理を終了する。
【００１６】
なお、特許文献１には、２値画像の圧縮を行う２値画像圧縮システムにおいて、画像データのサイズが非常に大きい場合であっても、大容量のメモリを必要とすることなく効率的な符号化を行うために、与えられる２値画像データに対して圧縮処理を行ってコードデータを生成する２値画像圧縮処理手段と、前記２値画像圧縮処理手段に対して、圧縮対象とする２値画像を所定のライン毎に分割して得られる複数のブロック単位で２値画像データを与える２値画像データ設定手段と、前記２値画像データ設定手段によって与えられた２値画像データに対する前記２値画像圧縮処理手段による圧縮処理が１ブロックに対して完了した際に、最終コードが生成された状態を読出して保持する状態保持手段と、前記２値画像データ設定手段により次ブロックの２値画像データが前記２値画像圧縮処理手段に与えられる前に、前記状態保持手段によって保持された状態を、前記２値画像圧縮処理手段に設定する状態設定手段とを備える技術が開示されている。
【特許文献１】特開平７−１８４０６３号公報（公開日：１９９５年７月２１日）
【非特許文献１】ＩＴＵ−Ｔ(International Telecommunication Union Telecommunication standardization sector) ＷＨＩＴＥ  ＢＯＯＫ  ディジタル静止画像圧縮符号化関連勧告書（財団法人  新日本ＩＴＵ協会）  勧告Ｔ．８２
【発明の開示】
【発明が解決しようとする課題】
【００１７】
しかしながら、上記従来の符号化装置２１では、入力画像データが複数のメモリに分割されて格納されている場合、符号化対象部分を含む分割部分を符号化する際に、符号化対象部分を含む分割部分を格納したメモリだけでなく、その周辺部分を含む分割部分を格納したメモリにもアクセスする必要がある。
【００１８】
つまり、入力画像データが複数のメモリに分割されて格納されている場合、ある分割部分の符号化が完了すると、次の分割部分の符号化を開始する。この際、２つ目以降の分割部分の最上部を符号化するためには、符号化に使用するコンテクスト（テンプレート）の形状に応じて、既に符号化した分割部分の一部をコンテクストとして参照する必要がある。したがって、２つ目以降の分割部分における最上部の符号化の際には、符号化対象部分を含む分割部分とその直前の分割部分とを参照しながら（２つの分割部分を参照しながら）符号化を行う必要がある。
【００１９】
このため、これら２つの分割部分を格納したそれぞれのメモリに対して交互にアクセスする必要があるので、アルゴリズムが複雑になるとともに、符号化処理の処理速度が低下するという問題があった。また、符号化処理が完了した分割部分の入力画像データを、次の分割部分（あるいは次の分割部分の一部）の符号化が終わるまで記憶しておく必要があるので、符号化処理が完了した分割部分のメモリをすぐには解放できず、多数のメモリ（あるいは大容量のメモリ）を備える必要があった。
【００２０】
また、上記特許文献１の技術では、圧縮処理が１ブロックに対して完了した際に、最終コードが生成された状態が状態保持手段に保持され、次ブロックの２値画像データが２値画像圧縮処理手段に与えられる前に、状態保持手段によって保持された状態を２値画像圧縮処理手段に設定するようになっている。
【００２１】
この構成では、次ブロックの２値画像データの圧縮処理を行う前に、前ブロックの最終コードが生成された状態を状態保持手段に保持する処理、状態保持手段によって保持された状態を読み出す処理、および状態保持手段によって保持された状態を２値画像圧縮処理手段に設定する処理を行う必要があるので、上記従来の符号化装置２１と同様、アルゴリズムが複雑になるとともに、圧縮処理の処理速度が低下するという問題があった。また、入力画像データを格納する入力画像記憶部に加えて、前ブロックの最終コードが生成された状態を保持する状態保持手段をさらに設ける必要があるので、上記従来の符号化装置２１と同様、多数のメモリ（あるいは大容量のメモリ）を備える必要があった。
【００２２】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、符号化対象部分の周辺部分のデータを用いて符号化対象部分の符号を決定する符号化装置において、符号化処理のアルゴリズムの簡略化、および符号化処理の高速化を図ることにある。
【課題を解決するための手段】
【００２３】
本発明の符号化装置は、上記の課題を解決するために、１つ以上の記憶部を備えたデータ記憶部と、入力データを複数の分割部分に分割し、上記複数の分割部分を上記１つ以上の記憶部に分割させた状態で記憶させる記憶制御手段と、上記データ記憶部から読み出した入力データの符号化処理を行う符号化手段とを備え、上記符号化手段が上記符号化処理時に入力データにおける符号化対象部分の周辺部分のデータを参照し、この周辺部分のデータに応じて上記符号化対象部分の符号を決定する符号化装置であって、上記記憶制御手段は、上記入力データを第１〜第ｍ分割部分（ｍは２以上の整数）に分割し、第ｎ分割部分（ｎは２以上ｍ以下の整数）を上記記憶部に記憶させる際、第ｎ分割部分とは異なる第ｎ−１分割部分に含まれるデータのうち、上記第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、上記第ｎ分割部分に付加して上記記憶部に記憶させることを特徴としている。なお、データ記憶部が上記記憶部を複数備える場合、これら複数の記憶部は、互いに異なる記録媒体（互いに物理的に分離した記録媒体）であってもよく、共通の記録媒体内における互いに異なる記憶領域であってもよい。
【００２４】
上記の構成によれば、上記データ記憶部は１つ以上の記憶部を備えている。そして、記憶制御手段は、上記入力データを第１〜第ｍ分割部分（ｍは２以上の整数）に分割し、第ｎ分割部分（ｎは２以上ｍ以下の整数）を上記記憶部に記憶させる際、第ｎ分割部分とは異なる第ｎ−１分割部分に含まれるデータのうち、上記第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、上記第ｎ分割部分に付加して上記記憶部に記憶させる。つまり、記憶制御手段は、第ｎ−１分割部分の一部（第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分）を、第ｎ−１分割部分を記憶する記憶領域と第ｎ分割部分を記憶する記憶領域とに重複して記憶させる。
【００２５】
これにより、第ｎ分割部分の符号化処理を行う際、第ｎ−１分割部分を記憶した記憶領域にアクセスして第ｎ−１分割部分の一部を読み出す処理を行う必要がなくなるので、符号化処理の処理速度を速くすることができ、また、符号化処理に関するアルゴリズムを簡略化できる。さらに、第ｎ−１分割部分の符号化処理が完了した後にこの第ｎ−１分割部分のデータを参照する必要がなくなるので、第ｎ−１分割部分の符号化処理が完了すればこの第ｎ−１分割部分を記憶部から削除できる。したがって、第ｎ−１分割部分の符号化処理が完了すれば、第ｎ−１分割部分を記憶した記憶領域から第ｎ−１分割部分を削除してこの記憶領域を解放できるので、この記憶領域に他のデータ（例えば他の分割部分のデータ）を記憶させることができる。したがって、記憶部を有効利用することができ、データ記憶部に要求される記憶部の数、あるいは記憶部の容量を低減できる。
【００２６】
また、上記ｎは入力データの先頭側の分割部分から順に付される整数であり、上記記憶制御部は、上記第ｎ分割部分を上記記憶部に記憶させる際、上記第ｎ−１分割部分に含まれるデータの末尾部分を、上記第ｎ分割部分の先頭に付加して上記記憶部に記憶させる構成としてもよい。
【００２７】
上記の構成によれば、上記ｎは入力データの先頭側の分割部分から順に付される整数なので、第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分は、第ｎ−１分割部分の末尾に存在する。したがって、第ｎ分割部分を記憶部に記憶させる際、第ｎ−１分割部分に含まれるデータの末尾部分を第ｎ分割部分の先頭に付加して記憶させることにより、第ｎ分割部分の符号化処理を行う際に第ｎ−１分割部分を記憶した記憶部にアクセスする必要がなくなる。
【００２８】
また、上記記憶制御部は、上記第ｎ分割部分に付加するデータを、上記符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分の範囲を示すコンテクストに応じて設定する構成としてもよい。
【００２９】
例えば、上記入力データは、行方向および列方向にマトリックス状に配された複数の画素のデータを含む画像データであり、上記コンテクストは、上記符号化対象部分を含む行である第１ラインの一部と上記第１ラインに隣接する行である第２ラインの一部とを上記周辺部分の範囲とする２ラインテンプレート、または、上記第１ラインの一部と上記第２ラインの一部と上記第２ラインに対して上記第１ラインとは反対側に隣接する行である第３ラインの一部とを上記周辺部分の範囲とする３ラインテンプレートであり、上記ｎは入力データの先頭側の分割部分から順に付される整数であり、上記記憶制御部は、上記コンテクストが２ラインテンプレートである場合には上記第ｎ分割部分に付加するデータを上記第ｎ−１分割部分における末尾１ラインとし、上記コンテクストが３ラインテンプレートである場合には上記第ｎ分割部分に付加するデータを上記第ｎ−１分割部分における末尾２ラインとする構成としてもよい。
【００３０】
また、上記コンテクストは、上記入力データを一定のビット数毎に折り返すことで上記入力データを仮想的に複数のラインからなる２次元データとみなしたときに、上記符号化対象部分を含むラインである第１ラインの一部と上記第１ラインに隣接するラインである第２ラインの一部とを上記周辺部分の範囲とする２ラインテンプレート、または、上記第１ラインの一部と上記第２ラインの一部と上記第２ラインに対して上記第１ラインとは反対側に隣接するラインである第３ラインの一部とを上記周辺部分の範囲とする３ラインテンプレートであり、上記ｎは入力データの先頭側の分割部分から順に付される整数であり、上記記憶制御部は、上記コンテクストが２ラインテンプレートである場合には上記第ｎ分割部分に付加するデータを上記第ｎ−１分割部分における末尾１ラインとし、上記コンテクストが３ラインテンプレートである場合には上記第ｎ分割部分に付加するデータを上記第ｎ−１分割部分における末尾２ラインとする構成としてもよい。
【００３１】
上記の構成によれば、第ｎ分割部分に付加するデータが、コンテクストに応じて設定される。すなわち、第ｎ−１分割部分を記憶する記憶部と、第ｎ分割部分を記憶する記憶部とに重複して記憶されるデータが、コンテクストに応じて設定される。これにより、重複して記憶されるデータの量を、第ｎ分割部分の符号化処理を行う際に、第ｎ−１分割部分を記憶した記憶部にアクセスする必要がないようにするための最小限の量にすることができる。したがって、記憶部に要求される容量を低減することができる。
【００３２】
また、上記符号化手段は、上記第ｎ分割部分の符号化処理を行う際、この第ｎ分割部分に付加された上記データを除くデータに対して符号化処理を行う構成としてもよい。
【００３３】
第ｎ分割部分に付加して記憶部に記憶したデータ、すなわち、第ｎ−１分割部分を記憶する記憶部と第ｎ分割部分を記憶する記憶部とに重複して記憶されるデータについては、第ｎ−１分割部分の符号化処理時に符号化される。このため、上記の構成によれば、異なる記憶部に重複して記憶される上記データについて、重複して符号化処理が行われることを防止し、符号化処理を効率的に行うことができる。
【００３４】
また、上記符号化手段は、算術符号化処理を行う構成であってもよい。例えば、上記符号化手段は、ＪＢＩＧ、ＪＢＩＧ２、ＪＰＥＧ、ＪＰＥＧ  ２０００のいずれかで規定されている符号化方法を用いて上記符号化処理を行う構成であってもよい。
【００３５】
ここで、算術符号化とは、対象シンボル系列の出現確率に応じて数直線上の部分領域を割り当ててゆき、該当範囲を判定するのに必要な座標情報をその符号語とする符号化方法である。この方法では、符号化対象部分における対象シンボル系列の出現確率を算出するために、符号化対象部分の周辺部分のデータが参照される。したがって、上記の構成によれば、上記した本発明の効果を得ることができる。
【００３６】
本発明の符号化方法は、上記の課題を解決するために、入力データを複数の分割部分に分割する分割工程と、上記複数の分割部分をデータ記憶部に備えられる１つ以上の記憶部に分割させた状態で記憶させる記憶工程と、上記記憶部から読み出した入力データの符号化処理を行う符号化工程とを含み、上記符号化処理時に入力データにおける符号化対象部分の周辺部分のデータを参照し、この周辺部分のデータに応じて上記符号化対象部分の符号を決定する符号化方法であって、上記分割工程では、上記入力データを第１〜第ｍ分割部分（ｍは２以上の整数）に分割し、上記記憶工程では、第ｎ分割部分（ｎは２以上ｍ以下の整数）を上記記憶部に記憶させる際、第ｎ分割部分とは異なる第ｎ−１分割部分に含まれるデータのうち、上記第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、上記第ｎ分割部分に付加して上記記憶部に記憶させることを特徴としている。
【００３７】
上記の方法によれば、上記分割工程では、上記入力データを第１〜第ｍ分割部分（ｍは２以上の整数）に分割し、上記記憶工程では、第ｎ分割部分（ｎは２以上ｍ以下の整数）を上記記憶部に記憶させる際、第ｎ分割部分とは異なる第ｎ−１分割部分に含まれるデータのうち、上記第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、上記第ｎ分割部分に付加して上記記憶部に記憶させる。つまり、第ｎ−１分割部分の一部（第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分）を、第ｎ−１分割部分を記憶する記憶領域と第ｎ分割部分を記憶する記憶領域とに重複して記憶させる。
【００３８】
これにより、第ｎ分割部分の符号化処理を行う際、第ｎ−１分割部分を記憶した記憶領域にアクセスして第ｎ−１分割部分の一部を読み出す処理を行う必要がなくなるので、符号化処理の処理速度を速くすることができ、また、符号化処理に関するアルゴリズムを簡略化できる。さらに、第ｎ−１分割部分の符号化処理が完了した後にこの第ｎ−１分割部分のデータを参照する必要がなくなるので、第ｎ−１分割部分の符号化処理が完了すればこの第ｎ−１分割部分を記憶部から削除できる。したがって、第ｎ−１分割部分の符号化処理が完了すれば、第ｎ−１分割部分を記憶した記憶領域から第ｎ−１分割部分を削除してこの記憶領域を解放できるので、この記憶領域に他のデータ（例えば他の分割部分のデータ）を記憶させることができる。したがって、記憶部を有効利用することができ、データ記憶部に要求される記憶部の数、あるいは記憶部の容量を低減できる。
【００３９】
なお、上記符号化装置は、コンピュータによって実現してもよく、この場合には、コンピュータを上記各手段として動作させることにより、上記符号化装置をコンピュータにて実現させるプログラム、およびそれを記録したコンピュータ読み取り可能な記録媒体も、本発明の範疇に含まれる。
【発明の効果】
【００４０】
本発明の符号化装置は、上記記憶制御手段が、上記入力データを第１〜第ｍ分割部分（ｍは２以上の整数）に分割し、第ｎ分割部分（ｎは２以上ｍ以下の整数）を上記記憶部に記憶させる際、第ｎ分割部分とは異なる第ｎ−１分割部分に含まれるデータのうち、上記第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、上記第ｎ分割部分に付加して上記記憶部に記憶させる。
【００４１】
また、本発明の符号化方法は、上記分割工程では、上記入力データを第１〜第ｍ分割部分（ｍは２以上の整数）に分割し、上記記憶工程では、第ｎ分割部分（ｎは２以上ｍ以下の整数）を上記記憶部に記憶させる際、第ｎ分割部分とは異なる第ｎ−１分割部分に含まれるデータのうち、上記第ｎ分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、上記第ｎ分割部分に付加して上記記憶部に記憶させる。
【００４２】
それゆえ、符号化処理に関するアルゴリズムを簡略化でき、また、符号化処理の処理速度を速くすることができる。また、データ記憶部に要求される記憶部の数、あるいは記憶部の容量を低減できる。
【発明を実施するための最良の形態】
【００４３】
本発明の一実施形態について説明する。本実施形態では、本発明を、２値の画像データを算術符号化により圧縮（符号化）し、それによって得られた圧縮画像データ（符号化データ）を出力する符号化装置１に適用する場合の例ついて説明する。
【００４４】
なお、本実施形態では、符号化装置１を構成する各部が、ＣＰＵなどの演算手段がＲＯＭやＲＡＭなどの記録媒体に格納されたプログラムコードを実行することで実現される機能ブロックである場合を例にして説明する。また、本実施形態では、算術符号化の実装形態が、ＪＢＩＧのＱＭ−ｃｏｄｅｒ（２値画像データをマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果に応じて算術符号化する方式）である場合について説明する。また、ＪＢＩＧ圧縮はプログレッシブ方式を取っているが、ここでは、説明を簡単にするために最低解像度レイヤのみを持つＪＢＩＧ圧縮について扱う。また、説明を簡単にするため、コンテクストの形状を変化させるＡＴ(Adaptive Template)移動などＪＢＩＧの仕様に含まれる付加的な機能に関しては説明を省略する。
【００４５】
また、本実施形態に係る符号化装置１は、図示しないパーソナルコンピュータのプリンタドライバにおける符号化圧縮部として機能するものである。このプリンタドライバは、パーソナルコンピュータの図示しない記憶部（記録媒体）に蓄積されたプログラムをパーソナルコンピュータのＣＰＵ(Central Processing Unit)が読み込んで実行することによって実現される。パーソナルコンピュータに対するユーザの指示に応じて、プリンタドライバは、印刷ドキュメントを画像に変換したデータを符号化装置１によってＪＢＩＧ圧縮し、プリンタ本体に送信する。プリンタ本体では、受信したＪＢＩＧ画像を復号して印刷を行う。これによって、プリンタドライバにおける圧縮を高速化することができるようになっている。
【００４６】
（１．１  符号化装置１の全体構成）
図２は、符号化装置１の概略構成を示すブロック図である。この図に示すように、符号化装置１は、概略的に、入力制御部３１、入力画像記憶部３２、コンテクスト生成部２、取得部３、算術符号化部４、記録部５、およびレジスタ（メモリ）６を備えている。この符号化装置１においては、符号化処理を計算機上で実装するために、固定精度の整数演算で近似をしている。
【００４７】
入力画像記憶部３２は、第１メモリ（第１記憶領域）３６および第２メモリ（第２記憶領域）３７を備えている。第１メモリ３６および第２メモリ３７は、互いに連続しない記憶領域である。例えば、第１メモリ３６と第２メモリ３７とは、互いに異なる記録媒体（互いに物理的に分離した記録媒体）であってもよく、共通の記録媒体における互いに連続しない記憶領域であってもよい。なお、本実施形態では、説明を簡単にするために、入力画像記憶部３２が２つのメモリを備えているものとするが、これに限らず、さらに多数のメモリを備えていてもよい。
【００４８】
入力制御部３１は、画像入力部３３、画像分割部３４、および画像読出部３５を備えている。画像入力部３３は、パーソナルコンピュータで実行される各種アプリケーションから画像データの入力を受け付ける。そして、入力画像データを、入力画像記憶部３２に一端記憶させる。なお、入力画像データのサイズが第１メモリ３６または第２メモリ３７の容量よりも大きい場合、画像入力部３３は入力画像データを画像分割部３４に送る。画像分割部３４は、入力画像データを分割して第１メモリ３６と第２メモリとに格納する。分割方法の詳細については後述する。画像読出部３５は、入力画像記憶部３２に格納されている入力画像データを順次読出し、コンテクスト生成部２に送る。
【００４９】
コンテクスト生成部２は、入力画像データから、符号化対象部分（符号化処理の対象となる画素（セル））およびその周辺部分（符号化対象部分の周辺（近傍）の複数画素の配列であるコンテクスト）を抽出するものである。符号化対象部分とコンテクストとの関係を、図３（ａ）に基づいて説明する。ＱＭ−ｃｏｄｅｒを用いる符号化装置１においては、符号化対象部分とする入力ビットをその直前の入力ビットまでの入力ビット列、より詳細には周辺画素（コンテクスト）の状態（周辺画素に対応する複数の入力ビットの値の組み合わせ）から予測する。すなわち、符号化装置１は、予測の際に、周辺の複数画素が取りうる状態の組み合わせそれぞれに対して、優勢確率シンボルおよび劣勢シンボルの出現確率を推定する機能を持つ。
【００５０】
ここで、今回の入力ビット（入力シンボル）である対象画素（符号化対象部分）を選択した場合に、この対象画素の周辺の複数画素（コンテクスト）として、図３（ａ）に示すように、対象画素より前に処理された画像データのうちで、対象画素と同じラインおよびそれに隣接するライン（図３（ａ）では１つ上のライン）における符号化画素の周辺に存在する複数画素を選択する。図３（ａ）において、斜線部分が符号化対象部分となる対象画素であり、その周辺の１０個の四角がコンテクスト（周辺部分）の各画素を表している。なお、この場合、コンテクストの画素数は１０個であり、各画素の値（シンボル）は０または１の値を持つので、コンテクストの各画素が取りうる値の組み合わせの数は１０２４通りとなる。また、ＪＢＩＧ圧縮では、最低解像度レイヤのコンテクストとして、図３（ａ）に示すような２ラインテンプレートの他に、図３（ｂ）に示すような３ラインテンプレートも用意されており、こちらを用いることもできる。以下の説明では、２ラインテンプレートを用いるものとする。
【００５１】
コンテクスト生成部２は、抽出した画素およびコンテクストのデータを取得部３に出力する。また、コンテクスト生成部２は、算術符号化部４の符号処理部９からの画素インクリメント指示を受信すると、入力画像データから、次の対象画素およびコンテクストを抽出する。
【００５２】
次に、取得部３について説明する。取得部３は、予測値としての優勢確率シンボル（ＭＰＳ）を、周辺画素の配列（コンテクスト）に対する優勢確率シンボルを記録した記録部５の確率推定テーブル７から取得する。
【００５３】
ここで、確率推定テーブル７は、図４に示すように、コンテクストと、そのコンテクストから予想されるＭＰＳの値との関係を含んでいる。また、確率推定テーブル７は、コンテクストと、このコンテクストに応じたＬＰＳインターバルの推定値（ＬＳＺ）のインデックスＳＴとの関係も含んでいる。ＬＳＺについては後述する。取得部３は、記録部５の確率推定テーブル７にアクセスし、入力されるコンテクストを用いてインデックスＳＴを得る。取得部３は、ＭＰＳとインデックスＳＴとを得ると、画素の値（入力ビットの値；入力シンボル）、ＭＰＳ、インデックスＳＴを算術符号化部４に出力する。以上のように、符号化対象画素（符号化対象のビットに対応する画素）の近傍画素（周辺画像；コンテクスト）の値から符号化対象のビット（シンボル）のＬＰＳインターバル（この場合にはＬＰＳインターバルの推定値）を推定する推定ステップが、取得部３と確率推定テーブル７とによって実行される。すなわち、取得部３および確率推定テーブル７は、上記推定ステップを実行する推定部として機能する。
【００５４】
算術符号化部４は、入力される画素の値、ＭＰＳ、インデックスＳＴから、符号化データである実数ｘを生成する。この算術符号化部４は、符号処理部９および前処理部１０を含んでいる。
【００５５】
符号処理部９は、優勢確率シンボルの符号化を行うＭＰＳ処理部９ａ、劣勢確率シンボルの符号化を行うＬＰＳ処理部９ｂ、正規化処理を実行するＲＥＮＯＲＭ処理部９ｃを含んでいる。符号処理部９は、前処理部１０から入力される選択信号に応じて、各処理部９ａ〜９ｃのうちから適切な処理部を選択する。また、入力された画素の値、ＭＰＳ、ＳＴを用いて、選択した処理部によって符号化データを生成する。なお、各処理部９ａ〜９ｃにおける処理の詳細については後述する。
【００５６】
前処理部１０は、取得部３から入力される画素の値、ＭＰＳ、ＳＴに応じて、選択信号を生成して、符号処理部９に出力するものである。具体的には、前処理部１０は、選択部１０ａを含んでいる。この選択部１０ａは、選択信号を生成するために、入力される画素の値（符号化対象のシンボル）と、そのコンテクストから予想されるＭＰＳとを比較し、符号化対象のシンボルが優勢確率シンボルか劣勢確率シンボルかを判断する。そして、選択部１０ａは、判断結果に応じて選択信号を生成し、符号処理部９に出力する。選択部１０ａの詳細な動作については後述する。
【００５７】
記録部５には、確率推定テーブル７と確率推定表８とが記録されている。なお、確率推定テーブル７と確率推定表８とは、全く別のものである。テーブルは表とも訳し得るが、ＩＴＵ−Ｔ  Ｔ．８２の日本語訳（非特許文献１）でこのようになっているため、その語句をそのまま用いることとする。
【００５８】
確率推定テーブル７は、コンテクストごとの優勢確率シンボルＭＰＳと、ＬＳＺのインデックスＳＴとを保存するテーブルである。本実施形態においては、コンテクストごとのＭＰＳ（１ビット）とＬＳＺのインデックスＳＴ（７ビット）とを保存している。このため、各コンテクストに対して１バイト（８ビット）の情報を有している。本実施形態のように、コンテクストが１０画素分の大きさを持つ場合には、２の１０乗個のコンテクストそれぞれに対して１バイトの大きさを有することになり、確率推定テーブル７全体は１０２４バイトとなる。この確率推定テーブル７は、符号化処理の間、書き換えが行なわれる。
【００５９】
より詳細には、確率推定テーブル７は、インデックスＳＴと優勢確率シンボルＭＰＳとを更新しながら符号化される。なお、一括符号化中には、インデックスＳＴの値、および優勢確率シンボルＭＰＳのどちらも変化しないので、確率推定テーブル７の書き換えは発生しない。一方、通常の符号化（逐次の符号化）中には、優勢確率シンボルまたは劣勢確率シンボルを符号化するたびにインデックスＳＴの値が変化するため、確率推定テーブル７の書き換えが生じる。また、ＬＰＳインターバルの大きさがＭＰＳインターバルの大きさを超えれば優勢確率シンボルと劣勢確率シンボルとが入れ替わるため、このときも確率推定テーブル７を書き換える。
【００６０】
なお、優勢確率シンボルは、０または１の値を取る。ＬＳＺのインデックスＳＴは、ＪＢＩＧにおいては、０から１１２までのどれかの値を取る。また、コンテクストが１０ビットである一方で、インデックスは７ビットであるので、同じインデックスを有する、互いに異なるコンテクストが存在することになる。例えばコンテクスト“００００００００００”のＬＳＺのインデックスＳＴと、“０００００００００１”のＬＳＺのインデックスＳＴとが共に１３というようなことも起こり得る。このＬＳＺのインデックスＳＴは、後述するＪＢＩＧの確率推定表８において、近傍１０画素に出現した０または１の値（シンボル）の組み合わせ状況（コンテクスト）ごとに、これまで注目画素の位置に出現した値（シンボル）の履歴から注目画素に出現するであろう値（シンボル）の出現確率の予測を表すために用いられる。
【００６１】
一方、確率推定表８は、図５（ａ）および図５（ｂ）に示すＩＴＵ−Ｔ  Ｔ．８２の表２４のように、ＬＳＺのインデックスＳＴから、ＬＳＺや次のＳＴなどを求めるための表である。確率推定表８からＬＳＺを求めるために、確率推定テーブル７から得たＬＳＺのインデックスＳＴが使用される。この確率推定表８は、符号化処理の際にも書き換えられることはない。すなわち、確率推定表８は、参照されるだけで、書き換えられることはない。
【００６２】
ＬＳＺのインデックスＳＴは、確率推定テーブル７に関して説明したように、７ビットの情報である。本実施形態のようにＪＢＩＧ圧縮の場合には、インデックスＳＴの取り得る値は０から１１２までとなる。また、ＬＳＺは、上述のように、ＬＳＺのインデックスＳＴに応じた、劣勢確率シンボルのインターバル（の近似値）を意味する。また、ＮＬＰＳは、劣勢確率シンボルを符号化したとき（このときには必ず正規化が発生する）の次のインデックスＳＴの値を意味する。また、ＮＭＰＳは、優勢確率シンボルを符号化して正規化が発生したときの、次のインデックスＳＴの値を意味する。したがって、正規化が発生したときには、インデックスＳＴの値がＮＬＰＳの値（劣勢確率シンボルを符号化した優勢確率シンボルを符号化した場合）またはＮＭＰＳの値（優勢確率シンボルを符号化した場合）に更新される。なお、正規化が発生しないときには、インデックスＳＴの値は更新されない。また、ＳＷＩＴＣＨは、優勢確率シンボルと劣勢確率シンボルとの入れ替えを行うかどうかのフラグを意味する。
【００６３】
また、符号化装置１は、作業用メモリとしてのレジスタ６を備えている。このレジスタ６は、高速アクセス可能なメモリである。レジスタ６は、Ａｒｅｇ６ａ、Ｃｒｅｇ６ｂを含んでいる。
【００６４】
Ａｒｅｇ６ａは、インターバルの大きさの値Ａｒｅｇを保持（蓄積）するための記憶領域である。また、Ｃｒｅｇ６ｂは、インターバルの低数の値Ｃｒｅｇを保持する記憶領域である。Ａｒｅｇ６ａおよびＣｒｅｇ６ｂは、整数で固定精度である。
【００６５】
（１．２  算術符号化方法の概略）
符号化装置１における符号化方法の概略について、図６に基づいて概略を説明する。符号化装置１は、外部から入力された２値の画像データである入力ビット列（入力シンボル列）を算術符号化して０以上１未満の実数ｘに変換する。より詳細には、０以上１未満の半開区間を、入力ビット（入力シンボル）に応じて分割することにより、実数ｘに対応する半開区間（ｘ以上ｙ未満の区間）を求め、半開空間の下限値を符号結果とする。符号化結果である符号化データは、桁数の多い一つの小数となる。なお、符号化結果である実数ｘに対応する半開区間（実数ｘの存在し得る範囲）を、以下ではインターバルと呼ぶ。
【００６６】
図６に示すように、まだ１ビット（１シンボル）も入力が行なわれていない時点では、明らかにインターバルは０以上１未満の領域となる。
【００６７】
このインターバルを、入力ビットに応じて、予め定めた手順で変化させる。全ての入力ビットに応じてインターバルを変化させた後におけるインターバルの下限値（最小値）である低数を符号化結果とする。符号化装置１において、インターバルは、インターバルの下限値である低数と、インターバルの大きさ（下限値と上限値との差）との組み合わせとして記憶されている。
【００６８】
より詳細には、符号化装置１は、次の（今回の）入力ビットを前回の入力ビットまでの入力ビット列、より詳細には周辺の画素（コンテクスト）の状態（周辺の画素に対応する複数の入力ビットの値の組み合わせ）から予測する。また、この予測に応じて、インターバルを２つの領域に分割する。符号化装置１は、予測の際に、周辺の画素が取りうる複数の状態のそれぞれから優勢確率シンボルおよび劣勢確率シンボルの出現確率を推定する機能を持つ。これにより、周辺の画素の状態から０または１のどちらのシンボルが出現しやすいかを判断する。
【００６９】
ここで、入力ビットに出現すると予想された入力値（入力シンボル）を優勢確率シンボル（ＭＰＳ）と呼ぶ。予想されなかった方の入力値（入力シンボル）を劣勢確率シンボル（ＬＰＳ）とする。また、予想とともに、優勢確率シンボルの出現確率と劣勢確率シンボルの出現確率との比に応じて、インターバルを２つの領域に分割し、一方の領域をＭＰＳインターバル、他方の領域をＬＰＳインターバルとする。優勢確率シンボルの出現確率に応じたＭＰＳインターバルは、０により近い方の領域とする。また、０から遠い方の領域は、ＬＰＳの出現確率に応じたＬＰＳインターバルとする。
【００７０】
入力ビット列（入力シンボル列）の符号化時には、各ビット（シンボル）の入力に応じて、入力ビット（入力シンボル）と優勢確率シンボル（ＭＰＳ）との比較を行う。入力ビットと優勢確率シンボル（ＭＰＳ）とが一致する場合には、現在のインターバルからＬＰＳインターバルを取り除くように、インターバルを変化させる。一方、入力ビットとＭＰＳとが一致しない場合には、現在のインターバルからＭＰＳインターバルを取り除くように、インターバルを変化させる。
【００７１】
一例として、入力ビット列（入力シンボル列）「０００１」であり、そのときの優勢確率シンボル（ＭＰＳ）が「０１０１」である場合の符号化処理を図６に基づいて説明する。２ビット目の入力（前から２つ目の入力シンボル）は劣勢確率シンボルであるから、その入力の符号化時には、ＬＰＳインターバルが符号化後の新たなインターバルとして選択される。すなわち、現在のインターバルからＭＰＳインターバルを取り除くようにインターバルを変化させることで、符号化が行われる。一方、２ビット目以外の入力（前から１つ目、３つ目、４つ目のシンボル）は優勢確率シンボルであるから、その入力の符号化時には、ＭＰＳインターバルが符号化後のインターバルとして選択される。すなわち、現在のインターバルからＬＰＳインターバルを取り除くようにインターバルを変化させることで、符号化が行われる。
【００７２】
ここで、全ての入力ビット列に対する処理が完了したときのインターバルの低数を実数ｘとし、この実数ｘを符号化結果とする。上述の処理手順によって、入力ビットが予想される入力ビット（優勢確率シンボル）と一致する場合には、インターバルの低数に変化を生じない。このため、出力（符号化結果）にも変化を生ずることがなく、新たなビットを出力する必要もないので、これを利用して符号化を行うことができる。なお、全ての入力ビットが優勢確率シンボルであれば符号化結果ｘは０となる。
【００７３】
上述のような手順を行うにあたって、ＱＭ−Ｃｏｄｅｒを用いている符号化装置１においては、以下の手順をさらに行う。すなわち、上述の算術符号化処理を実施していくと、インターバルの大きさが次第に小さくなる。このため、やがて計算機の固定精度では表現できなくなってしまう。そこで、インターバルの大きさが０．５以上となるまで繰り返しインターバルの大きさを２倍にしていく、正規化処理と呼ばれる処理を行う。
【００７４】
符号化装置１においては、インターバルの大きさを後述するレジスタ６内のレジスタＡ（以下、「Ａｒｅｇ」と記す）６ａに保持（記憶）し、インターバルの低数を後述するレジスタ６内のレジスタＣ（以下、「Ｃｒｅｇ」と記す）６ｂに保持（記憶）している。ここで、本実施形態では、インターバルを、実際の値を２１６倍した値、すなわち０ｘ０〜０ｘ１００００の範囲の値で表現する。以下では、１６進表示の数字（“０ｘ”を前に付けた数字）は、この表現による値である。したがって、１６進表示の数字を２１６で割った値が実際の値である。この場合、Ａｒｅｇ６ａには、０．５（“０ｘ８０００”で表される）以上かつ１（“０ｘ１００００”で表される）以下となるように正規化されたインターバルの大きさが格納される。
【００７５】
また、Ａｒｅｇ６ａに記憶される値Ａｒｅｇ（インターバルの大きさ）が、正規化処理によって２倍にされる度に、Ｃｒｅｇ６ｂに記憶される値Ｃｒｅｇ（インターバルの低数）も２倍とする。このため、Ａｒｅｇ６ａに記憶される値Ａｒｅｇを２倍化していることによる出力への影響は、相殺（キャンセル）される。また、Ｃｒｅｇ６ｂの値Ｃｒｅｇは、オーバーフローしないように、上位バイトが適時取り出され、符号化結果として出力されるようになっている。なお、この際に発生するキャリーオーバーを解決する方法がＩＴＵ−Ｔ  Ｔ．８２に記載されているが、本発明の内容を理解する上で必須ではないため、ここでは説明を省略する。
【００７６】
また、符号化装置１においては、以下のような近似を行うようになっている。ＬＰＳインターバルを計算するには、本来は、（インターバルの大きさ）×（ＬＰＳ出現確率）という演算が必要である。符号化装置１においては、このＬＰＳインターバルの値を、統計的に求められた推定値（推定ＬＰＳインターバル；以下、適宜、「ＬＳＺ」と略記する）によって近似する。この近似では、その時点でのインターバルの大きさが１（“０ｘ１００００”）とは限らないということを考慮せずにインターバルの大きさが１であるものとみなし、ＬＰＳインターバルの値を、統計的な推定によって求められたＬＰＳの出現確率の推定値（ＬＳＺ）で近似する。そのため、インターバル全体のうち、推定ＬＰＳインターバルの占める割合は、インターバルの大きさに応じて変化してしまう。しかしながら、インターバルは大きさが０．５以上かつ１以下となるように正規化されているため、誤差はそれほど大きくはならない。
【００７７】
すなわち、上記の近似は、インターバル全体の大きさが０の出現確率と１の出現確率との合計であるものとみなして行うものであるから、本来はインターバル全体の大きさは１であるべきである。しかしながら、演算を行う都合上、インターバル全体の大きさを１にする処理は行わず、インターバル全体の大きさが０．５から１．０までの範囲におさまっていればよいこととしている。このため、インターバルの大きさが小さければ、インターバルからＬＰＳインターバルを引いてＭＰＳインターバルを求めたときに、ＬＰＳインターバルの大きさがＭＰＳインターバルの大きさより大きくなる可能性がある。
【００７８】
以上をまとめると、符号化装置１において、入力ビット（入力シンボル）としてＭＰＳが与えられた際にはインターバルからＬＳＺを引き、その結果得られた値を新たなインターバルとする。また、符号化装置１は、入力ビットとしてＬＰＳが与えられたときには、インターバルをＬＳＺに変更する。この操作によって、入力ビットが符号化される。符号化装置１は、この操作の結果としてインターバルが０．５以下となったときには正規化を行う。正規化が行われたときにはＬＳＺの値を更新する。また、上述の符号化によって、ＭＰＳインターバルよりもＬＰＳインターバルの方が大きくなってしまう場合がある。このときは、ＭＰＳインターバルとＬＰＳインターバルとの入れ替えを行う。
【００７９】
ここで、上述のような算術符号化の手順を、計算機や電子回路などに実装する場合には、有限の計算精度でも符号化を行うことができるように、劣勢確率シンボルの推定出現確率（ＬＳＺ）には最小値を持たせるのが一般的である。算術符号化においては、符号化中に正規化が発生すると、劣勢確率シンボルの推定出現確率（ＬＳＺ）を減少させる。ただし、上述のような実装形態においては、既に劣勢確率シンボルの推定出現確率（ＬＳＺ）が最小になっていれば、それ以上劣勢確率シンボルの推定出現確率（ＬＳＺ）は減少しない。
【００８０】
（１．３  符号化装置１の動作）
図７は、符号化装置１における処理の流れを示すフローチャートである。この図を参照しながら、符号化装置１における符号化処理について説明する。
【００８１】
まず、パーソナルコンピュータで実行される各種アプリケーションから符号化装置１の入力制御部３１に画像データが入力されると、画像入力部３３は、入力画像データのサイズが入力画像記憶部３２に備えられる第１メモリ３６の容量以下であるか判断する（Ｓ１）。そして、入力画像データのサイズが第１メモリ３６の容量以下である場合には、入力画像データを第１メモリ３６に格納し（Ｓ２）、Ｓ６に進む。
【００８２】
一方、入力画像データのサイズが第１メモリ３６の容量より大きい場合、画像入力部３３は入力画像データを画像分割部３４に送る。画像分割部３４は、入力画像記憶部３２に備えられるメモリの数および各メモリのサイズに応じて入力画像データを分割する（Ｓ３）。
【００８３】
また、画像分割部３４は、２番目以降（ｎ番目（ｎは２以上の整数））の分割部分の先頭に、その直前（ｎ−１番目）の分割部分の末尾を付加する（Ｓ４）。上記付加する部分は、ｎ番目の分割部分の符号化処理時にｎ−１番目の分割部分を読み出す必要がないように、コンテクストの形に応じて設定される。本実施形態では、２ラインテンプレートを用いるので、ｎ番目の分割部分の先頭ラインにｎ−１番目の分割部分の最終ラインを付加する。したがって、ｎ番目の分割部分の先頭ラインと、ｎ−１番目の分割部分の最終ラインとには、共通のデータが重複して格納されることになる。なお、本実施形態では、３ラインテンプレートを用いる場合には、ｎ番目の分割部分の先頭２ラインと、ｎ−１番目の分割部分の末尾２ラインとを重複させるようにすればよい。また、図３（ａ）に示した２ラインテンプレートまたは図３（ｂ）に示した３ラインテンプレートを用いる場合、ｎ番目の分割部分に付加された重複部分（重複ライン）のうち先頭の１セルは実際には参照されることはない。このため、上記重複部分の先頭の１セルについては付加しないようにしてもよい。
【００８４】
次に、画像分割部３４は、上記の各分割部分（ｎ番目の分割部分における先頭ラインにはｎ−１番目の分割部分における末尾ラインのデータが付加されている）を、入力画像記憶部３２の第１メモリ〜第ｎメモリ（本実施形態では第１メモリ３６および第２メモリ３７）に格納する（Ｓ５）。なお、入力画像記憶部４２の各メモリに格納された入力画像データは、以降の符号化処理時に画像読出部３５によって適宜読み出され、コンテクスト生成部２に送られる。
【００８５】
コンテクスト生成部２２は、入力画像データを少なくとも１つ以上のストライプに分ける（Ｓ６）。このストライプとは、符号化処理を行う単位であり、画像中の１ライン以上の横ラインからなる。また、このストライプは、幅が画像の幅と同じであり、高さは１ライン以上で画像の高さ以下の領域である。
【００８６】
符号化装置１は、符号化処理をストライプ単位で行う。Ｓ６〜Ｓ２０のストライプについてのループ（ＬＯＯＰ＿Ａ）の内部では個々のストライプの処理を行う。Ｓ６から一つのストライプについての処理を開始し、Ｓ６〜Ｓ２０のストライプのループ（ＬＯＯＰ＿Ａ）においてそのストライプの処理（画素の符号化を繰り返す処理）が完了すると、Ｓ６〜Ｓ２０のストライプのループ（ＬＯＯＰ＿Ａ）の先頭のＳ６に戻って、次のストライプの処理をＳ７から開始する。Ｓ６〜Ｓ２０までのループによって全てのストライプに対して処理が完了すると、画像データ全体の符号化が完了する。
【００８７】
ストライプのループ（ＬＯＯＰ＿Ａ）の内部にはセル（画素）のループ（ＬＯＯＰ＿Ｂ）がある。セルのループ（ＬＯＯＰ＿Ｂ）の内部では、Ｓ７〜Ｓ１８において各セルの処理が行われる。１つのセルの処理が完了すると、セルのループ（ＬＯＯＰ＿Ｂ）の先頭Ｓ７に戻って次のセルの符号化が行われる。セルのループ（ＬＯＯＰ＿Ｂ）の先頭Ｓ７において、コンテクスト生成部２は、選択したストライプのうちから、符号化対象となる一つのセルを選択する。このとき、次のセルは、例えばストライプの左上から右下に向けて移動させるように順次一つずつ選択する。例えば、横方向に１ライン分の画素とコンテクストの読み取りを完了すると、その下のラインの読み取りへと進む。全てのセルの処理が完了すると１つのストライプの処理が完了したことになる。なお、ｎ番目の分割部分に付加された、ｎ−１番目の分割部分の末尾との重複部分に含まれるセルについては、ｎ−１番目の分割部分の符号化処理時に既に符号化処理がなされているため、対象セルとはしない（符号化処理を重複して行わない）。
【００８８】
また、コンテクスト生成部２は、入力画像データから、対象セルおよび対象セルの近傍セル（周辺画素）であるコンテクストを抽出し（読み取り）、取得部２３に送信する（Ｓ８）。ここで、本実施形態では、上記したようにｎ番目の分割部分の先頭に、ｎ−１番目の分割部分における末尾のデータが付加されているので、ｎ番目の分割部分の符号化処理を行う際にｎ−１番目の分割部分のデータを格納したメモリにアクセスする必要がない。この点について、図１（ａ）および図１（ｂ）を参照しながらより詳細に説明する。
【００８９】
図１（ａ）は上記した従来の符号化装置２１における入力画像データ（６×７画素の画像データ）の分割方法を模式的に示した説明図であり、図１（ｂ）は本実施形態にかかる符号化装置１における入力画像データ（図１（ａ）と同じ入力画像データ）の分割方法を模式的に示した説明図である。
【００９０】
図１（ａ）に示したように、従来の分割方法では、各分割部分に重複部分はなかった。このため、ｎ番目の分割部分の符号化処理時には、近傍セルのデータを読み出すために、対象セルを含む分割部分（ｎ番目の分割部分）のデータを格納したメモリだけでなく、近傍セルを含む他の分割部分（ｎ−１番目の分割部分）のデータを格納したメモリにもアクセルする必要があった。
【００９１】
これに対して、本実施形態では、図１（ｂ）に示したように、ｎ番目の分割部分の先頭にｎ−１番目の分割部分の最終ラインを付加する。このため、ｎ番目の分割部分における２番目のライン（上記最終ラインが付加される前の先頭ライン）の対象セルを符号化処理する場合に、当該分割部分の先頭に付加されたｎ−１番目の分割部分の最終ラインを参照して処理できる。したがって、対象セルの符号化処理時にアクセスするメモリは、対象セルを含む分割部分（ｎ番目の分割部分）のデータが格納されたメモリだけでよくなる。
【００９２】
取得部３は、コンテクスト生成部２から送信された対象セルおよびコンテクストに応じて、記録部５の確率推定テーブル７から、当該コンテクストについての優勢確率シンボルおよび劣勢確率シンボルの確率推定値のインデックスＳＴを取得する（Ｓ９）。また、取得部３は、セルの値、ＭＰＳ、インデックスＳＴを算術符号化部４へと出力する。
【００９３】
次に、算術符号化部４の前処理部１０に備えられる選択部１０ａは、入力される対象セルの値とＭＰＳとに応じて、対象セルがＭＰＳであるか否かを判別する（Ｓ１０）。Ｓ１０において対象セルがＭＰＳであると判別された場合には、算術符号化部４の符号処理部９において、ＭＰＳ処理部９ａがＭＰＳ処理（ＣＯＤＥ  ＭＰＳ：Ｓ１１〜Ｓ１４）を行う。一方、Ｓ１０において対象セルがＬＰＳであると判別された場合には、算術符号化部４の符号処理部９において、ＬＰＳ処理部９ｂがＬＰＳ処理（ＣＯＤＥ  ＬＰＳ：Ｓ１５〜Ｓ１７）を行う。
【００９４】
Ｓ１０において対象セルがＭＰＳであると判別された場合、ＭＰＳ処理部９ａは、記録部５の確率推定表８にアクセスし、劣勢確率シンボルの確率推定値のインデックスＳＴを用いて、劣勢確率シンボルの確率推定値を取得し、これに応じてレジスタ６のＡｒｅｇ６ａ、Ｃｒｅｇ６ｂを書き換える（Ｓ１１）。また、ＭＰＳ処理部９ａは、Ａｒｅｇ６ａの値が０．５未満であるか否かを判別して（Ｓ１２）、０．５未満である場合にはＳ１３に進み、０．５以上の場合にはＳ１８に進む。Ｓ１３ではＭＰＳ処理部９ａがＲＥＮＯＲＭ処理部９ｃに指示して、ＲＥＮＯＲＭ処理部９ｃに、レジスタ６のＡｒｅｇ６ａ、Ｃｒｅｇ６ｂに対する正規化処理を行わせ、この正規化処理によって得られた符号化データを必要に応じて符号化装置１の後段に備えられる装置に出力（符号出力）させる。また、ＭＰＳ処理部９ａは、記録部５の確率推定表８を更新し（Ｓ１４）、Ｓ１８に進む。
【００９５】
一方、Ｓ１０において対象セルがＬＰＳであると判別された場合、ＬＰＳ処理部９ｂは、記録部５の確率推定表８にアクセスして、劣勢確率シンボルの確率推定値のインデックスＳＴを用いて、劣勢確率シンボルの確率推定値を取得し、これに応じてレジスタ６のＡｒｅｇ６ａ、Ｃｒｅｇ６ｂを書き換える（Ｓ１５）。また、ＬＰＳ処理部９ｂは、レジスタ６のＡｒｅｇ６ａ、Ｃｒｅｇ６ｂに対して、確率推定表のＳＷＩＴＣＨの値に応じて、ＬＰＳとＭＰＳの入れ替えと符号出力を行う（Ｓ１６）。すなわち、ＬＰＳ処理部９ｂは、ＬＳＺのインデックスに対応する確率推定表のＳＷＩＴＣＨの値が１か否かによって、入れ替えを行うかどうかを判断する。さらに、ＬＰＳ処理部９ｂは、記録部５の確率推定表８を更新し（Ｓ１７）、Ｓ１８に進む。
【００９６】
Ｓ１８では、符号処理部９がコンテクスト生成部２に対してセルインクリメントの指示を行い、セルについてのループを終了する。このような手順をストライプの全てのセルに対して行うことで、ストライプの符号化を行う。
【００９７】
次に、コンテクスト生成部２は、ストライプについての処理が終了したか否かを判別し、終了していた場合にはレジスタ６から符号化データを出力する（フラッシュ処理：Ｓ１９）。このように、次のストライプの符号化に進む前に、ここまでの符号化結果のうちで、まだ出力されていない部分を出力する。
【００９８】
その後、Ｓ２０では、コンテクスト生成部２が新たなストライプを選択する。全てのストライプの符号化が完了すれば画像全体の符号化が完了したことになり、入力画像データの全てを符号化した場合には、処理を終了する。
【００９９】
以上のように、本実施形態にかかる符号化装置１が、第１メモリ３６および第２メモリ３７を有する入力画像記憶部３２を備えている。そして、入力制御部３１は、入力画像データを分割し、各分割部分を第１メモリ３６と第２メモリ３７とに分散して記憶させる。また、入力制御部３１は、２番目の分割部分を記憶させる際、１番目の分割部分に含まれるデータのうち、２番目の分割部分における符号化対象セルを符号化処理する際に参照する周辺セルを含むラインのデータを、２番目の分割部分に付加して第２メモリ３７に記憶させる。つまり、１番目の分割部分の一部（２番目の分割部分における符号化対象セルを符号化処理する際に参照する周辺セルを含むライン）を、第１メモリ３６と第２メモリ３７とに重複して記憶させる。
【０１００】
これにより、２番目の分割部分の符号化処理を行う際にアクセルする必要のあるメモリは、第２メモリ３７だけでよくなり、第１メモリ３６にはアクセスする必要がないので、符号化処理の処理速度を速くすることができる。また、符号化処理に関するアルゴリズムを簡略化できる。さらに、１番目の分割部分の符号化処理が完了した後は、この１番目の分割部分のデータを参照する必要がなくなるので、第１メモリ３６から１番目の分割部分のデータを削除できる。したがって、第１メモリ３６を迅速に解放し、第１メモリ３６に他のデータを記憶させるなどしてこの第１メモリ３６を効率的に利用できる。
【０１０１】
なお、本実施形態では、入力画像記憶部３２が２つのメモリ（第１メモリ３６および第２メモリ３７）を備えているものとしたが、さらに多数のメモリを備えていてもよい。また、本実施形態では、主に、入力画像データを２つの分割部分に分割する例について説明したが、これに限るものではなく、３つ以上の分割部分に分割してもよい。この場合、ｎ番目（ｎは２以上の整数）の分割部分を入力画像記憶部３２のメモリに記憶させる際、ｎ−１番目の分割部分に含まれるデータのうち、ｎ番目の分割部分における符号化対象部分を符号化処理する際に参照する当該符号化対象部分の周辺部分を含む部分のデータを、ｎ番目の分割部分に付加して上記メモリに記憶させればよい。これにより、上記の効果を得ることができる。
【０１０２】
また、本実施形態では、２次元形状を有する画像データ（行方向および列方向にマトリックス状に配された複数の画素のデータを含む画像データ）の符号化処理を行う構成について説明したが、これに限るものではない。画像データでなくても、２次元的なデータであれば、本発明を適用できる。また、入力データが２次元的なデータでない場合であっても、例えば入力データを一定のビット数毎に折り返すことによって上記入力データを仮想的に複数のラインからなる２次元データとして取り扱うことで、本実施形態の構成を適用できる。
【０１０３】
また、本実施形態では、簡単のために、最低解像度レイヤのみを持つＪＢＩＧ圧縮について説明したが、これに限るものではなく、本発明は複数の解像度レイヤを持つプログレッシブなＪＢＩＧ圧縮に対しても応用できる。
【０１０４】
また、本実施形態では、本発明をＪＢＩＧやＪＰＥＧに使用されているＱＭ−ｃｏｄｅｒに適用する場合の例について説明したが、これに限るものではない。例えば、ＪＢＩＧ２やＪＰＥＧ  ２０００に使用されているＭＱ−ｃｏｄｅｒにもそのまま適用できる。ただし、ＭＱ−ｃｏｄｅｒに使用されている確率推定表は、ＱＭ−ｃｏｄｅｒに使用されている確率推定表とは異なっているため、劣勢確率シンボルのインターバルが最低となるインデックスＳＴの値は、１３ではなく４５となる。
【０１０５】
また、ＱＭ−ｃｏｄｅｒやＭＱ−ｃｏｄｅｒに適用する構成に限らず、入力データにおける符号化対象部分の周辺部分のデータを参照して上記符号化対象部分の符号化処理を行う構成であれば適用できる。例えば、上記した以外の算術符号化方式を用いる符号化装置に適用してもよい。
【０１０６】
また、本実施形態では、本発明を２値画像データの符号化に適用した場合について説明したが、これに限らず、多値画像データの符号化にも適用できる。多値画像の場合であっても、画像データが０と１のビット列で表されていることに変わりはなく、たとえば１画素を８ビットで表す画像データであれば幅が８倍になった２値画像データと考えることができる。この場合、必要に応じて近傍形の参照パターンを変更すればよい。また、必要に応じて確率推定表の内容を変更すればよい。その場合、劣勢確率シンボルのインターバルが最低となるインデックスＳＴの値が変化する可能性はあるが、それ以外の点では２値画像データの場合と変化はない。そのため、２値画像データの場合と略同様の処理を行うことができる。さらに、文字データ等のような画像データ以外のデータであっても、統計的な予測に基づく算術符号化によってデータを符号化することができるものであれば、本発明を適用できる。
【０１０７】
また、本実施形態では、説明を簡単にするため、コンテクストの形状を変化させるＡＴ移動などＪＢＩＧの仕様に含まれる付加的な機能に関しても説明を省略したが、本発明は、ＡＴ移動を伴うＪＢＩＧ圧縮に対しても応用可能である。ここで、ＡＴ（Adaptive Template）移動とは、ＪＢＩＧ圧縮の仕様に含まれている特殊な操作である。ＡＴ移動は符号化において必須のものではなく、ＡＴ移動を行わないようにすることもできる。通常、コンテクストの形（テンプレート）は一定で符号化中に変化することはないが、ＡＴ移動を使用する場合にはコンテクストの形そのものが変化する。ＡＴ移動するかどうか、いつＡＴ移動するかは符号化する側で決めることができるため、本発明はＡＴ移動の有無に関わらず適用することができる。ＡＴ移動を行う場合であっても、想定されるコンテクストの形に応じて、対象セルの符号化に用いられる近傍セルのデータを対象セルのデータと共通のメモリ領域に格納すればよい。
【０１０８】
また、本実施形態では、入力データを符号化処理することによってこの入力データの圧縮を行うものとしたが、これに限るものではなく、入力データにおける符号化対象部分の周辺部分のデータを参照して上記符号化対象部分の符号化処理を行う構成であれば適用できる。例えば、符号化によって入力データを暗号化する構成であってもよく、符号化によって入力データの暗号化および圧縮を行う構成であってもよい。
【０１０９】
また、符号化装置１を構成する各部（各ブロック）は、ＣＰＵ等のプロセッサを用いてソフトウェアによって実現される。すなわち、符号化装置１は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアである符号化装置１の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、符号化装置１に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによって達成される。
【０１１０】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【０１１１】
また、符号化装置１を通信ネットワークと接続可能に構成し、通信ネットワークを介して上記プログラムコードを供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波ディジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【０１１２】
また、符号化装置１の各ブロックは、ソフトウェアを用いて実現されるものに限らず、ハードウェアロジックによって構成されるものであってもよく、処理の一部を行うハードウェアと当該ハードウェアの制御や残余の処理を行うソフトウェアを実行する演算手段とを組み合わせたものであってもよい。
【０１１３】
また、本実施形態では、符号化装置１がパーソナルコンピュータのプリンタドライバにおける符号化圧縮部として機能するものとしたが、これに限るものではない。符号化装置１は、例えば、ファクシミリ装置（ＦＡＸ）やプリンタ等の画像形成装置、デジタルカメラやイメージスキャナ等の撮像装置、各種通信装置などに備えられ、各種データを符号化処理する符号化部として機能するものであってもよい。
【０１１４】
本発明は上述した実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能である。すなわち、請求項に示した範囲で適宜変更した技術的手段を組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【産業上の利用可能性】
【０１１５】
本発明は、符号化対象部分の周辺部分のデータに基づいて符号化対象部分のデータを符号化する符号化装置（例えば、ＪＢＩＧ，ＪＢＩＧ２，ＪＰＥＧ，ＪＰＥＧ２０００などの符号化方式を用いる符号化装置）に適用できる。また、本発明は、ファクシミリ装置（ＦＡＸ）やプリンタ、パーソナルコンピュータのプリンタドライバ等における画像データの圧縮（符号化）に特に有効であり、特に印刷ドキュメントを画像に変換したものをプリンタに送信する際の画像データ圧縮を高速化するのに有効である。
【図面の簡単な説明】
【０１１６】
【図１】（ａ）は従来の符号化装置における入力画像データの分割方法を示す説明図である。（ｂ）は本発明の一実施形態にかかる符号化装置における入力画像データの分割方法を示す説明図である。
【図２】本発明の一実施形態にかかる符号化装置の概略構成を示すブロック図である。
【図３】（ａ）は２ラインテンプレートを用いる場合の、符号化を行う対象画素と、その画素についてのコンテクストの一例を示す説明図である。（ｂ）はラインテンプレートを用いる場合の、符号化を行う対象画素と、その画素についてのコンテクストの一例を示す説明図である。
【図４】上記符号化装置にて用いる確率推定テーブルの一例を示す図である。
【図５】（ａ）は上記符号化装置にて用いる確率推定表の一例の一部を示す図であり、（ｂ）は上記確率推定表の他の一部を示す図である。
【図６】上記符号化装置にて行う算術符号化を説明するための概念図である。
【図７】上記符号化装置にて行う符号化処理の概略を示すフローチャートである。
【図８】従来の符号化装置の概略構成を示すブロック図である。
【図９】従来の符号化装置における符号化処理の流れを示すフローチャートである。
【図１０】（ａ）〜（ｃ）は、コンテクストが画像データの外側にはみ出してしまう場合の例を示す説明図である。
【符号の説明】
【０１１７】
１  符号化装置
２  コンテクスト生成部（符号化手段）
３  取得部（符号化手段）
４  算術符号化部（符号化手段）
５  記録部（符号化手段）
６  レジスタ（符号化手段）
７  確率推定テーブル（符号化手段）
８  確率推定表（符号化手段）
９  符号処理部（符号化手段）
９ａ  ＭＰＳ処理部（符号化手段）
９ｂ  ＬＰＳ処理部（符号化手段）
９ｃ  ＲＥＮＯＲＭ処理部（符号化手段）
１０  前処理部（符号化手段）
１０ａ  選択部（符号化手段）
３１  入力制御部（記憶制御手段）
３２  入力画像記憶部（データ記憶部）
３３  画像入力部（記憶制御手段）
３４  画像分割部（記憶制御手段）
３５  画像読出部（記憶制御手段）
３６  第１メモリ（記憶部）
３７  第２メモリ（記憶部）
【図１】
2008153779.tif 000003
【図２】
2008153779.tif 000004
【図３】
2008153779.tif 000005
【図４】
2008153779.tif 000006
【図５】
2008153779.tif 000007
【図６】
2008153779.tif 000008
【図７】
2008153779.tif 000009
【図８】
2008153779.tif 000010
【図９】
2008153779.tif 000011
【図１０】
2008153779.tif 000012