JP3871995B2

JP3871995B2 - 符号化装置および復号化装置

Info

Publication number: JP3871995B2
Application number: JP2002311145A
Authority: JP
Inventors: 徳明土屋
Original assignee: Fuji Xerox Co Ltd; Fujifilm Business Innovation Corp
Current assignee: Fujifilm Business Innovation Corp
Priority date: 2002-10-25
Filing date: 2002-10-25
Publication date: 2007-01-24
Anticipated expiration: 2017-06-23
Also published as: JP2003198858A

Description

【０００１】
【発明の属する技術分野】
本発明は、予測符号化方式を用いた画像データの符号化装置およびその符号データの復号化装置に関するものである。
【０００２】
【従来の技術】
２値画像の符号化技術の１つとして、周辺の画素から注目画素の状態を予測し、予測した結果を符号化する予測符号化方式がある。予測符号化においては、注目画素と相関関係があると思われる周囲画素をマルコフ情報源として予測に用いる。
【０００３】
予測方式には、予測値を直接決定する方法と、間接的に決定する方法が知られている。予測値を直接決定する方法としては、例えば特開平５−３１６３７０号公報で示されるように、複数の予測器の中から的中率の高い予測器を適応的に切り替え、最終的に１つの予測器を選択し、原画像の予測に使用する方法がある。また、予測値を間接的に決定する方法としては、例えば、予測値等の情報をメモリに格納し、周辺の画素値からメモリの情報を読み出して予測に使用する方法がある。
【０００４】
特公平６−９５６４５号公報に開示されている予測方式は、後者のメモリを用いた間接的に予測値を決定する予測方式であり、周辺の複数画素の値をアドレスとして、テーブルルックアップ方式で出力される予測値を用い、予測誤差データを生成している。しかし、予測画素の位置を全て固定とはせず、１画素のみ位置を可変にし、予測的中率によって予測位置を変更させている方式をとっている。ＩＴＵ−ＴＴ．８２、Ｔ−８５で定められたＪＢＩＧ（ＪｏｉｎｔＢｉ−ｌｅｖｅｌＩｍａｇｅｃｏｄｉｎｇｅｘｐｅｒｔＧｒｏｕｐ）で用いられる予測方式は、上述の特公平６−９５６４５号公報に示されている予測方式であり、符号化状態によって予測テーブルの情報を更新していく学習型の方式が採用されている。符号化には、注目画素を上述の予測方式で予測した結果である予測誤差データが使用される。
【０００５】
ＪＢＩＧにおいては、予測誤差データを符号化する符号化部に、算術符号化が採用された。算術符号化は、例えば特公平１−１７２９５号公報に示されているように、数直線上の領域を入力されたシンボルの１，０の発生確率に合わせて分割し、入力シンボルの値によって領域を選択する。このとき、予測と一致したシンボル（優勢シンボル）をＭＰＳ（ＭｏｒｅＰｒｏｂａｂｌｅＳｙｍｂｏｌ）、一致しないシンボル（劣性シンボル）をＬＰＳ（ＬｅｓｓＰｒｏｂａｂｌｅＳｙｍｂｏｌ）と呼ぶ。このＭＰＳ、ＬＰＳの発生確率推定値は、予測的中率などによって変化させる。ＪＢＩＧでは、シンボルの出現確率の推定部にＬＰＳ発生時の確率値（＝領域幅ＬＳＺ）を持たせるとともに、その確率推定値をシンボルの出現過程に応じて更新する学習機能を持たせている。確率推定の学習機能は上述の予測値の学習機能と連動する。この分割選択処理を情報源の出力系列の分だけ行ない、最終段の分割で得られた領域内の１点の２進小数表示で出力系列を表わす。
【０００６】
図１０は、算術符号化の概念図である。斜線で示した領域が、それぞれシンボルの符号化終了後の有効領域である。初期状態では、有効領域は［０，１）区間であり、ＬＰＳ発生時の領域幅ＬＳＺ（０）が設定されている。１−ＬＳＺ（０）がＭＰＳ発生時の領域幅である。ここではシンボルが「０」のときをＭＰＳ、「１」のときをＬＰＳとする。図１０において確率値は２進数で示している。
【０００７】
図１０では、最初に入力されたシンボルが「０」であるので、ＭＰＳの発生により有効領域は図１０（Ａ）においてハッチングを施した領域となる。そしてこの有効領域内をＬＰＳ発生時とＭＰＳ発生時の領域に分割する新たな領域幅ＬＳＺ（１）を設定する。次のシンボルが「１」のときは、ＬＰＳの発生により図１０（Ｂ）においてハッチングを施した領域が有効領域となる。同様にして、３番目のシンボルが「０」のとき、図１０（Ｃ）においてハッチングを施した領域が有効領域となり、さらに４番目のシンボルが「１」のとき、図１０（Ｄ）においてハッチングを施した領域が有効領域となる。
【０００８】
出力される符号はＣで表わされる。入力されたシンボル列「０１０１」に対する符号は、図１０（Ｄ）における有効領域内の１点とすればよい。ここでは、有効領域の基底、すなわち有効領域の最も小さい値Ｃ（３）を符号として表わし、出力する。
【０００９】
算術符号化においては、符号化の過程で、有効領域の１点を符号とするため、領域を大きくとれば、有効桁が減り符号量が減る。つまり、ＭＰＳ発生時にはなるべくＬＳＺの値を小さくし、ＬＰＳ発生時にはなるべくＬＳＺの値を大きくすることによって、有効領域を多く確保でき、符号量を減らすことができる。
【００１０】
図１１は、ＪＢＩＧで採用されている予測符号化方式の概略図である。図中、１は画像データ、２はコンテキスト生成部、３はコンテキスト、４は予測部、５はステート、６は確率推定テーブル、７はＬＳＺおよびＳＷ、８は予測値、９は算術符号化部、１０は符号データ、１１は書き換えデータ、１２は書き換え信号である。
【００１１】
画像データ１は、符号化のために算術符号化部９に入力されるとともに、コンテキスト生成部２に入力される。コンテキスト生成部２においては、注目画素の予測を行なうために、周辺画素を使用して予測のモデルテンプレートを作成する。図１２は、ＪＢＩＧで使用されるテンプレートの一例の説明図である。Ｐを注目画素とすると、図１２に示す参照画素Ｘ₉〜Ｘ₀を使用するテンプレートが生成される。この参照画素Ｘ₉〜Ｘ₀の値が２¹⁰状態（コンテキスト）の１０重マルコフ情報源となり、そのまま予測部４にコンテキスト３として入力され、予測に使用される。
【００１２】
予測部４には、参照画素Ｘ₉〜Ｘ₀の値に対応した予測値８と、確率推定テーブル６を参照するためのステート５とを対にした予測テーブルが記憶されている。参照画素Ｘ₉〜Ｘ₀の値であるコンテキスト３がそのまま予測テーブルにアドレスとして入力され、予測テーブルの１０２４個のエントリのいずれかが選択される。コンテキスト３により選択された予測テーブルのエントリから予測値８およびステート５を取り出し、予測値８を算術符号化部９へ入力し、また、ステート５を確率推定テーブル６に入力する。図１３は、予測部４に記憶されている予測テーブルの一例の説明図である。図１３に示した予測テーブルは、アドレスに対応して、予測値とステートが対になって格納されている。なお、アドレスは２進数で示しているが、これはコンテキストコンテキスト３として入力される参照画素Ｘ₉〜Ｘ₀のそれぞれの画素値に対応するものである。例えば、参照画素Ｘ₀の値のみが「１」で他の参照画素は「０」であれば、アドレス「０００００００００１」が参照され、予測値「１」とステート「２」が得られる。
【００１３】
確率推定テーブル６は、ステート５に対応して、ＬＰＳ発生時の領域幅ＬＳＺと、ＬＰＳ発生時の次のステート値であるＮＬＰＳおよびＭＰＳ発生時の次のステート値であるＮＭＰＳ、さらに正規化発生時に予測値を書き換えるか否かを示すフラグであるＳＷが格納されている。入力されたステート５に対応するＬＳＺおよびＳＷ７を算術符号化部９に出力するとともに、ＮＭＰＳ，ＮＬＰＳを書き換えデータ１１の一部として予測部４へ送る。図１４は、確率推定テーブル６の一例の説明図である。図１４では、ステート５の番号に対応して、ＬＳＺ、ＮＭＰＳ、ＮＬＰＳ、ＳＷを対にして格納している。例えばステートが「２」のとき、ＬＳＺとして「０ｘ１１１４」、ＮＬＰＳとして「１６」、ＮＭＰＳとして「３」、ＳＷとして「０」が得られる。ここで、「０ｘ」で始まる数値は１６進数である。
【００１４】
算術符号化部９では、予測部４から入力される予測値８と画像データ１とを比較し、一致していれば符号化するシンボルを「０」、すなわちＭＰＳが発生したものとし、不一致であれば符号化するシンボルを「１」、すなわちＬＰＳが発生したものとする。そして確率推定テーブル６から入力されるＬＳＺを用い、図１０で概略説明したように算術符号化を行なって符号データ１０を出力する。ＬＰＳが発生した場合には、確率推定テーブル６から入力されるＳＷが予測値の書き換えを可能としている場合（例えばＳＷが「１」の場合）に限り、予測値を反転した新予測値を書き換えデータ１１の一部として予測部４に送るとともに書き換え信号１２を送り、予測部４に記憶されている予測テーブルの予測値を書き換える。
【００１５】
ＪＢＩＧにおいては、算術符号化部９において、有効領域の有効桁を増やさないよう、有効領域はつねに０．５以上１未満となるように調整されている。この処理を正規化と呼ぶ。またＬＳＺの値は必ず０．５未満の値となるように確率推定テーブルを構成しておく。これにより、ＬＰＳ発生時には有効領域は０．５未満となり、必ず正規化が発生する。さらに、ＭＰＳ発生時においても、新有効領域は、現有効領域から、ＬＳＺを減算して求めるため０．５未満となる可能性があり、正規化が発生するケースがある。この正規化が発生した場合に、予測部４に対して書き換え信号１２を送る。予測部４では、ＭＰＳ発生時には確率推定テーブル６から与えられるＮＭＰＳを、コンテキスト生成部２から与えられているコンテキスト３のステートとして予測テーブルに書き込む。また、ＬＰＳ発生時には、確率推定テーブル６から与えられるＮＬＰＳをコンテキスト３のステートとして予測テーブルに書き込む。このようにして予測テーブルが更新された後、次の画像データ１についての処理を開始する。
【００１６】
上述の予測部４と確率推定テーブル６を順次書き換えてゆく学習型の予測／確率推定方式について、具体例を用いながらさらに説明する。図１５は、入力される画像データの一具体例の説明図である。図１５では、図１２に示すテンプレートの部分の画像データ１のみを示している。図１５に示すように、コンテキストＸ₉〜Ｘ₀が「００００００００１１」のとき、注目画素Ｐが１であった場合を考える。予測部４の予測テーブルおよび確率推定テーブル６は、それぞれ図１３、図１４に示す内容が設定されているものとする。
【００１７】
まず、コンテキスト「００００００００１１」がコンテキスト３として予測部４に入力される。この時、予測部４の予測テーブルのアドレス「００００００００１１」には、図１３に示すように、予測値「０」とステート値「８０」が格納されている。予測テーブルから読み出されたステート値「８０」は、確率推定テーブル６に入力される。次に確率推定テーブル６のステート番号「８０」が参照される。確率推定テーブル６には図１４に示す内容が設定されているので、そのステート番号「８０」に対応するＬＳＺ値「０ｘ５８３２」が読み出され、算術符号化部９に出力される。
【００１８】
このとき、注目画素Ｐの値は「１」であるが、予測部４の予測テーブルから読み出された予測値は「０」であるため、ＬＰＳが発生した、ということになる。ＬＰＳが発生した場合、確率推定テーブル６から読み出されたＬＳＺ値に対応する領域が基本的に次の有効領域となる。ＬＳＺは、０．５未満であるから、０．５以上１未満になるように正規化が行なわれ、ステート番号「８０」のＮＬＰＳの値「８０」が予測部４の予測テーブルのアドレス「００００００００１１」のステート値として上書きされる。また、確率推定テーブル６のステート番号「８０」のＳＷが「１」であるから、予測値は反転されて「１」となり、予測部４の予測テーブルのアドレス「００００００００１１」の予測値として上書きされる。図１６は、書き換え後の予測部テーブルの一具体例の説明図である。このようにして図１６に示すように、予測部のアドレス「００００００００１１」の予測値およびステート値が書き換えられる。この書き換えられた後の予測部を用いて次の画像データ１についての予測を行なうことになる。次に同じコンテキストが入力された場合は、予測値が１となっている。
【００１９】
この例ではＬＰＳが発生したが、ＭＰＳが発生した場合には、正規化を行なったときには予測部４の予測テーブルのステート値をＮＭＰＳ「８１」に書き換える。書き換え後、次に同じコンテキスト３が入力された場合、ステート値が「８１」であり、このときのＬＳＺは図１４から「０ｘ４ｄ１ｃ」となる。この値は、ステート値「８０」のときのＬＳＺ「０ｘ５８３２」よりも小さく、つまりＬＰＳが発生する確率が小さいことを意味する。これは、前回の同じコンテキストの時の予測が当たったため、次に同じコンテキストが入力された場合、ＭＰＳが発生時の領域幅を広げておき、再度予測が当たった場合に有効領域を広くとれるようにしたものであり、最終的な有効領域を増大させ、符号量を減少させることができる。
【００２０】
以上のようにして、確率推定テーブルにしたがって予測部を順次書き換え、予測的中率を向上させ、ＭＰＳ発生数を増やすとともに、ＭＰＳ／ＬＰＳ発生時の領域幅を制御して、符号化効率を向上させている。
【００２１】
また、復号時の処理も符号化時と同様、領域分割を行ないながら実施される。符号化時と異なるのは、符号化時は予測値と注目画素の比較を行ない、ＬＰＳ／ＭＰＳの領域を演算しながら求めるのに対し、復号化時には、符号が、ＬＰＳ／ＭＰＳのどちらの領域に入っているかを演算で求め、次に周辺の復号済みの参照画素から注目画素を逆予測しながら求める。
【００２２】
図１７は、ＪＢＩＧで採用されている予測復号化方式の概略図である。図中、図１１と同様の部分には同じ符号を付して説明を省略する。２１は算術復号化部、２２は逆予測部、２３は逆予測値、２４は書き換えデータである。コンテキスト生成部２および逆予測部２２は、符号化時のコンテキスト生成部２および予測部４とまったく同一に動作する。逆予測部２２は符号化時の予測部４と同一である。当然、確率推定テーブル６も符号化時と同一のものが使用されなければならない。
【００２３】
まず符号化時と同様に、復号化された画像データ１の注目画素の周辺の参照画素の値によりコンテキストが生成され、逆予測部２２、確率推定テーブル６から、ＬＳＺと逆予測値２３が算術復号化部２１に出力される。
【００２４】
次に、符号データ１０は算術復号化部２１において、有効領域の比較が行なわれた後、逆予測値２３を用いて画像データ１を出力する。図１８は、算術復号化部の基本動作の説明図である。まず、現有効領域から確率推定テーブルより入力されたＬＳＺ幅を減算し、
（有効領域−ＬＳＺ）
を得る。この値を境にＭＰＳ領域とＬＰＳ領域が分割される。次に入力された符号Ｃが、先に求めた（有効領域−ＬＳＺ）の値より大きいか否かを比較する。すなわち、
Ｃ＞有効領域−ＬＳＺ
の判定を行なう。この比較判定によって、注目画素がＬＰＳであるかＭＰＳであるかが判定できるので、入力された逆予測値から、注目画素のレベルを求める。すなわち、ＭＰＳであれば注目画素の値は逆予測値であり、ＬＰＳであれば逆予測値を反転して注目画素の値とすればよい。以上の処理により、基本的に注目画素を復号できる。
【００２５】
ただし、次の画素の復号のために、ここからさらに、新有効領域の決定、符号−有効領域の減算等の処理が必要となる。例えば図１８に示した例では、符号データＣがＬＰＳ領域に存在するので、新たな有効領域としてＬＰＳ領域を設定し、新たなＬＳＺを設定して上述の処理を繰り返し行なう。また、符号化時と同様にして、予測部４に記憶されている予測テーブルの予測値およびステート値の書き換えも行なわれる。
【００２６】
以上のように、ＪＢＩＧにおいては、確率推定テーブルとして書き換え可能なメモリを用いて更新してゆく学習型の予測方式を用い、またエントロピー符号化部に算術符号化方式を用いることによって、従来のランレングス符号化等に比べて高能率な２値画像の符号化および符号データの復号が達成される。
【００２７】
しかし、ＪＢＩＧ方式では、高能率な符号化が達成される反面、処理が低速になるという問題がある。ＪＢＩＧで採用されている予測テーブルを使用する学習型の予測方式は、予測値、ステートを書き換えて最適な状態に近づけるため、予測的中率が向上する利点もある反面、メモリのアクセスに時間がかかり、また、予測テーブルの書き換えが発生した場合には書き換えが終了した後でなければ予測値を読み出すことができず、高速化が難しい。
【００２８】
特願平８−３０１８８９号および特願平８−２８８７３１号などにおいては、符号化時あるいは復号時に予測テーブルあるいは逆予測テーブルから複数のデータをあらかじめ読み出しておいて、現画像の符号化結果あるいは復号結果によってデータを選択して高速化する方式が提案されている。また、例えば特開平８−１５４０５９号公報に示されるように、算術符号化自体を高速化する方式も提案されている。しかしいずれにせよ、１画素ごとに予測テーブルの書換えが発生する可能性があるため、隣接する複数の画素を同時に処理するなどの高速化の手段がとれないのが現状である。
【００２９】
符号化の処理を高速化するために、符号器を複数用いて並列に処理する方法が一般に考えられる。すなわち、入力画像を複数の領域に分割して、それぞれに対応する符号器で符号化するものである。しかし、この方式では、スキャナ等から入力画像がページの先頭から１画素ずつ転送される場合には対応できない。例えば入力画像を２分割して２つの符号器で符号化する場合、一方の領域の画素が連続して転送され、その間はその一方の領域に対応する符号器のみが動作し、その後に他方の領域の画素の転送が開始されるまで、他方の領域に対応する符号器は動作できない。そのため、複数の符号器を備えているにもかかわらず、並列に処理することができない。並列に処理するため、画像をメモリに一旦格納してから転送することが考えられるが、メモリ量が増えるという問題がある。また伸長時に出力装置などへリアルタイム出力する場合も、メモリに一旦格納する必要がある。
【００３０】
また別の方式として、例えば米国特許第４，９８２，２９２号明細書などに記載されているように、入力画像を１画素おきに符号化する方式なども提案されている。しかしこの方式では、ＪＢＩＧにおいて高能率符号化を実現するコンテキストを１画素おきに生成することとなって予測効率が落ちてしまい、符号化効率に影響するという問題がある。
【００３１】
また、上述したいずれの高速化のための方式においても、並列的に処理された符号が別々に出力されるため、符号を保持するメモリ管理が複雑になるという問題がある。
【００３２】
別々に生成された符号データを１つに合成する方法としては、例えば特開平６−３８０４８号公報などに記載されているように、それぞれの符号データの先頭に識別コードを挿入する方法がある。この方法によれば、符号としては１つになるが、それぞれの符号データ長を長くするとそれだけ余分なメモリを必要とするし、切り替えを細かくすると識別コード量が増大してしてしまうという問題があった。
【００３３】
【発明が解決しようとする課題】
本発明は、上述した事情に鑑みてなされたもので、高速に高効率の符号化あるいは復号化を行なうことができるとともに、符号データ量を抑えて１つの符号データとして管理可能な符号データを生成する符号化装置およびその符号データを復号する復号化装置を提供することを目的とするものである。
【００３４】
【課題を解決するための手段】
上記課題を解決するために、第１の発明（請求項１に記載）の符号化装置は、複数の符号化手段で符号化した符号データを合成手段で合成する際に、各符号化手段から出力される符号データを単位符号データごとに順に出力する。符号化手段から符号データが出力されない場合には符号データの順次出力ができなくなるので、その場合に限って識別コードを付して他の符号化手段からの符号データの出力を行なう。これによって合成手段から出力される合成符号データには、通常の状態では識別コードが出力されず、符号化手段から符号データが出力されないという特別な場合のみに識別コードが出力されるだけであるので、合成符号データ全体のデータ量を抑えることができる。
【００３６】
【発明の実施の形態】
図１は、本発明の符号化装置の実施の一形態を示すブロック構成図である。図中、図１１と同様の部分には同じ符号を付して説明を省略する。３１は符号化部、３２はＦＩＦＯメモリ、３３はメモリ状態信号、３４はリード信号、３５は単位符号データ、３６は合成部、３７は合成符号データである。なお、図１では符号化部３１を２ブロック設けた例を示しており、一方をＡブロック、他方をＢブロックとして、各ブロックに関係する構成には‘−’の後にＡまたはＢを記して区別している。
【００３７】
各符号化部３１−Ａ，Ｂは、予測部４、確率推定テーブル６、算術符号化部９から構成されており、コンテキスト生成部２を各符号化部３１−Ａ，Ｂに共通した構成として設けている。画像データ１は、共通して設けられているコンテキスト生成部２に入力されるとともに、それぞれの符号化部３１−Ａ，Ｂの算術符号化部９に入力される。コンテキスト生成部２で生成されたコンテキスト３−Ａ，Ｂは、それぞれの符号化部３１−Ａ，Ｂの予測部４に入力される。
【００３８】
また、各符号化部３１−Ａ，Ｂに対応して、各符号化部３１−Ａ，Ｂから出力される符号データ１０−Ａ，Ｂを一時的に格納するＦＩＦＯメモリ３２−Ａ，Ｂを設けている。このＦＩＦＯメモリ３２−Ａ，Ｂは、合成部３６からのリード信号３４−Ａ，Ｂに従って、先に格納した符号データから順に、基本的には所定データ量を単位として読み出し、単位符号データ３５−Ａ，Ｂとして合成部３６へ渡す。ＦＩＦＯメモリ３２−Ａ，Ｂは、それぞれ複数単位の符号データを格納可能であり、空状態か満杯状態かを示すメモリ状態信号３３−Ａ，Ｂを出力する。
【００３９】
合成部３６は、各ＦＩＦＯメモリ３２−Ａ，Ｂからのメモリ状態信号３３−Ａ，Ｂに基づき、基本的にはＦＩＦＯメモリ３２−ＡとＦＩＦＯメモリ３２−Ｂに対して交互にリード信号３４−Ａまたはリード信号３４−Ｂを送出して符号データを読み出し、単位符号データ３５−Ａまたは単位符号データ３５−Ｂを得て、合成符号データ３７として出力する。ＦＩＦＯメモリ３２−ＡまたはＦＩＦＯメモリ３２−Ｂの一方が空の状態で他方が満杯状態となった場合には、満杯状態となった側の識別符号を挿入して満杯となったＦＩＦＯメモリから連続して単位符号データを読み出し、合成符号データ３７として出力する。また、符号データの終了時には、ＦＩＦＯメモリ３２−ＡまたはＦＩＦＯメモリ３２−Ｂに残っている符号データの読み出しおよび出力を行なう。
【００４０】
次に、本発明の符号化装置の実施の一形態における動作の一例について説明する。図２は、画像データの一例の説明図である。図２（Ａ）には（ｎ＋１）×（ｎ＋１）画素からなる原画像を示しており、図中の上から下方向に各ラインの左端から順に右端までの各画素のデータが入力されるものとする。すなわち、Ｐ₀₀，Ｐ₀₁，・・・，Ｐ_0n，Ｐ₁₀，Ｐ₁₁，・・・，Ｐ_1n，Ｐ₂₀，・・・，Ｐ_mnの順で各画素の画像データ１が入力される。図１に示した構成では、符号化部を２ブロック設けているが、各符号化部３１−Ａ，Ｂはそれぞれ交互に、入力される画像データ１の符号化を行なう。すなわち、符号化部３１−Ａは図２（Ｂ）に示すように、Ｐ₀₀，Ｐ₀₂，・・・，Ｐ₁₀，Ｐ₁₂，・・・の画素（２番目の添字が偶数の画素）についての符号化処理を行なう。また、符号化部３１−Ｂは図２（Ｃ）に示すように、Ｐ₀₁，Ｐ₀₃，・・・，Ｐ₁₁，Ｐ₁₃，・・・の画素（２番目の添字が奇数の画素）についての符号化処理を行なうように制御される。
【００４１】
コンテキスト生成部２は、入力された画像データ１から、例えば図１２に示したようなテンプレートに従ってコンテキスト３を生成する。例えばＰ₂₂の画像データ１が入力されたとき、図２（Ｄ）に示すＰ₂₂を除く１０画素によってコンテキストを生成する。次のＰ₂₃の画像データ１が入力されたときには、図２（Ｅ）に示すＰ₂₃を除く１０画素によってコンテキストを生成する。これらのコンテキストは、いずれの符号化部によって使用されるかに関係なく、一律に生成される。このように符号化部に関係なくコンテキスト３を生成することによって、予測の的中率を向上させ、効率よく符号化できるようにしている。
【００４２】
符号化部３１−Ａでは、２番目の添字が偶数の画素が入力されると、コンテキスト生成部２から出力されるコンテキスト３−Ａおよび画像データ１−Ａを取り込む。例えば、Ｐ₂₂の画像データが入力されたとき、これを画像データ１−Ａとして取り込むとともに、Ｐ₂₂に対応する図２（Ｄ）に示すテンプレートによって生成されたコンテキスト３−Ａを取り込む。同様に、符号化部３１−Ｂでは、２番目の添字が奇数の画素が入力されると、コンテキスト生成部２から出力されるコンテキスト３−Ｂおよび画像データ１−Ｂを取り込む。例えば、Ｐ₂₃の画像データが入力されたとき、これを画像データ１−Ｂとして取り込むとともに、Ｐ₂₃に対応する図２（Ｅ）に示すテンプレートによって生成されたコンテキスト３−Ｂを取り込む。
【００４３】
各符号化部３１−Ａ，Ｂでは、上述の図１１と同様の動作によって、コンテキスト３−Ａ，Ｂに従って画像データ１−Ａ，Ｂを適応的に予測符号化し、符号データ１０−Ａ，Ｂを出力する。
【００４４】
図３は、本発明の符号化装置の実施の一形態における画像の入力と各符号化部の動作の一例を示すタイミングチャートである。入力画像クロックとともに１画素分の画像データ１が入力される。符号化部３１−Ａおよび符号化部３１−Ｂには、入力画像クロックを２分周した、それぞれ位相の異なるクロックが入力される。符号化部３１−Ａ，Ｂにおいてはそれぞれのクロックの立ち上がりで画像データ１をラッチするため、結果的にラッチされた画像データＡ，Ｂは１画素おきにそれぞれの符号化部に入力されることになる。図３の例では、まず画素Ｐ₂₀が入力されている間に符号化部３１−Ａのクロックが立ち上がり、Ｐ₂₀が符号化部３１−Ａに取り込まれて符号化される。次に画素Ｐ₂₁が入力されている間に符号化部３１−Ｂのクロックが立ち上がり、Ｐ₂₁が符号化部３１−Ｂに取り込まれて符号化される。Ｐ₂₁が入力されている間は符号化部３１−Ａのクロックは立ち上がらないため、Ｐ₂₁は符号化部３１−Ａには取り込まれない。このようにして、符号化部３１−Ａと符号化部３１−Ｂに交互に画像データ１が取り込まれて符号化される。
【００４５】
図３に示したように、符号化部３１−Ａ，Ｂは、入力画像クロックの２周期分だけの間、符号化処理を行なうことができる。逆に、符号化部３１−Ａ，Ｂは並列的に動作するので、処理速度の倍の速度で画像データ１を入力して符号化することができ、全体の符号化速度は符号化部が１個の場合に比べて倍になる。このとき、コンテキスト生成部２を共用しているので、符号化部３１−Ａと符号化部３１−Ｂはそれぞれ独立して符号化処理を行なっているにもかかわらず、的中率の高い予測を行なうことができ、圧縮効率を向上させている。
【００４６】
各符号化部３１−Ａ，Ｂで符号化されて出力された符号データ１０−Ａ，Ｂは、それぞれ、ＦＩＦＯメモリ３２−Ａ，Ｂに格納される。このときＦＩＦＯメモリ３２−Ａ，Ｂには、所定のデータ量を単位として複数単位の符号データが格納される。ここでは一例としてワード単位で符号データが格納されるものとする。
【００４７】
図４は、本発明の符号化装置の実施の一形態における合成部の動作の一例を示すフローチャートである。このフローチャートでは、ＦＩＦＯメモリ３２−Ａを‘Ａ’として示し、ＦＩＦＯメモリ３２−Ｂを‘Ｂ’として示している。合成部３６は、基本的にはＳ７１〜Ｓ７４の動作を繰り返す。すなわち、Ｓ７１においてメモリ状態信号３３−Ａを参照し、ＦＩＦＯメモリ３２−Ａが空か否かを判定し、空でなければＳ７２においてＦＩＦＯメモリ３２−Ａから１ワード分の符号データ（単位符号データ３５−Ａ）を読み出して合成符号データ３７として出力する。次にＳ７３においてメモリ状態信号３３−Ｂを参照し、ＦＩＦＯメモリ３２−Ｂが空か否かを判定し、空でなければＳ７４においてＦＩＦＯメモリ３２−Ｂから１ワード分の符号データ（単位符号データ３５−Ｂ）を読み出して合成符号データ３７として出力する。これを繰り返すことによって、符号化部３１−Ａと符号化部３１−Ｂで符号化した符号データが１ワードごとに交互に出力されることになり、符号化部３１−Ａ，Ｂで生成した符号データが合成されたことになる。このような合成を行なうことによって、符号化部３１−Ａ，Ｂでそれぞれ生成した符号データを別々に管理することなく、１つの符号データとして管理することができるようになる。また、それぞれの符号データを識別する識別コードをなるべく排除することができ、合成時のデータ量の増大を抑制している。
【００４８】
算術符号化方式では、１つの画像データの入力に対して１つの符号が出力されるとは限らず、例えば非常に効率よく符号化できる場合、多数の画像データが入力されないと符号は出力されない。また、図１０を用いて説明したように、有効領域の基底の小数部分を符号とするため、場合によっては有効領域の変化によって桁上がりが発生する場合がある。例えば有効領域の基底が２進数で０．０１１１のとき、有効領域の分割によって例えば０．１０００１等に変更される場合がある。このような場合には、この桁上がりが発生する可能性を考慮して、符号を出力することはできない。
【００４９】
このように符号データが出力されない状態が一方の符号化部で発生し、他方の符号化部からの符号データの出力がＦＩＦＯメモリに蓄積されてゆく場合がある。例えば符号化部３１−Ａから符号データが出力されない状態が続き、符号化部３１−Ｂからの符号データがＦＩＦＯメモリ３２−Ｂに蓄積されいている場合には、Ｓ７５で符号化が終了したか否かを判断した後、Ｓ７６においてＦＩＦＯメモリ３２−Ｂが満杯か否かを判定する。満杯でない場合には、そのままＳ７１へ戻る。これは、なるべく１ワードごとに交互に符号データを出力するフォーマットを崩さないためであり、符号化部３１−Ａから符号データが出力された時点で再び交互に１ワードずつ読み出し、出力する処理を開始する。
【００５０】
さらに符号化部３１−Ａから符号データが出力されず、ＦＩＦＯメモリ３２−Ｂが満杯になると、符号化部３１−Ｂは符号データを出力できないため符号化処理を停止しなければならなくなる。このような事態を回避するため、メモリ状態信号３３−Ａが空を示し、メモリ状態信号３３−Ｂが満杯を示している場合には、Ｓ７７において、直前に出力した符号データと同じブロックからの符号データを連続して出力する旨を示す識別コードを出力するとともに、ＦＩＦＯメモリ３２−Ｂからすべてのワードを読み出して出力する。そしてＳ７１へ戻り、再びＦＩＦＯメモリ３２−Ａに符号データが格納されるのを待つ。
【００５１】
符号化部３１−Ｂから符号データが出力されない状態が続き、符号化部３１−Ａからの符号データがＦＩＦＯメモリ３２−Ａに蓄積されている場合も同様である。Ｓ７２でＦＩＦＯメモリ３２−Ａから１ワード分の単位符号データ３５−Ａを読み出して出力した後、Ｓ７３でＦＩＦＯメモリ３２−Ｂが空であると判定される。Ｓ７８で符号化処理が終了したか否かを判定した後、Ｓ７９でＦＩＦＯメモリ３２−Ａが満杯か否かを判定する。ＦＩＦＯメモリ３２−Ａが満杯でなければＳ７３へ戻り、ＦＩＦＯメモリ３２−Ｂに符号データが格納されるのを待つ。ＦＩＦＯメモリ３２−Ｂが空のままＦＩＦＯメモリ３２−Ａが満杯となると、Ｓ８０において、識別コードを出力するとともに、ＦＩＦＯメモリ３２−Ａからすべてのワードを読み出して出力する。そしてＳ７３へ戻り、再びＦＩＦＯメモリ３２−Ｂに符号データが格納されるのを待つ。
【００５２】
このように、ＦＩＦＯメモリが満杯の場合には識別コードとともに符号データを出力することによって、合成符号データのデータ量が多少増加するものの、符号化部を停止させることなく、高速な符号化処理を行なうことができる。
【００５３】
符号化すべき画像データ１の入力が無くなり、符号化処理が終了した場合にも、いずれかのＦＩＦＯメモリに符号データが格納されたまま、他のＦＩＦＯメモリに符号データが格納されるのを待つことになる。これを回避するため、Ｓ７５およびＳ７８で符号化処理の終了を判定する。Ｓ７５で符号化処理の終了を判定した場合には、Ｓ７１でＦＩＦＯメモリ３２−Ａが空であると判定されているので、ＦＩＦＯメモリ３２−Ｂにデータが残っていることになる。Ｓ８１において、識別コードを出力した後、ＦＩＦＯメモリ３２−Ｂ内の符号データをすべて読み出し、出力する。また、Ｓ７８で符号化処理の終了を判定した場合は、Ｓ７３でＦＩＦＯメモリ３２−Ｂが空であると判定されているので、Ｓ８２において、識別コードを出力後、ＦＩＦＯメモリ３２−Ａ内の符号データをすべて読み出し、出力する。このようにして、すべての符号データを出力することができる。
【００５４】
図５は、合成符号データの一例の説明図である。上述のようにして合成部３６から出力された合成符号データ３７の一例を図５に示している。ここで、‘Ａ’はＦＩＦＯメモリ３２−Ａから読み出した単位符号データ３５−Ａであり、‘Ｂ’はＦＩＦＯメモリ３２−Ｂから読み出した単位符号データ３５−Ｂである。基本的にＦＩＦＯメモリ３２−ＡとＦＩＦＯメモリ３２−Ｂから交互に１ワードずつ単位符号データ３５−Ａ，Ｂを読み出して出力するので、ＦＩＦＯメモリ３２−Ａから読み出した単位符号データ３５−Ａと、ＦＩＦＯメモリ３２−Ｂから読み出した単位符号データ３５−Ｂが、１ワードずつ交互に並んでいる。すなわち、ＦＩＦＯメモリ３２−Ａから読み出される単位符号データ３５−Ａが順にＡ₀，Ａ₁，・・・であり、ＦＩＦＯメモリ３２−Ｂから読み出される単位符号データ３５−Ｂが順にＢ₀，Ｂ₁・・・であったとすると、まず、Ａ₀，Ｂ₀，Ａ₀，Ｂ₁・・・とそれぞれのブロックの符号が交互に出力される。
【００５５】
Ａ_nを出力した後、符号化部３１−Ａから符号データ１０−Ａが出力されない期間が続き、その間に符号化部３１−Ｂから符号データ１０−Ｂが出力されているとする。Ｂ_nを出力した後は、ＦＩＦＯメモリ３２−Ｂが満杯となるまで符号データの読み出しは行なわれず、そのままＦＩＦＯメモリ３２−Ｂへ格納されるだけである。この状態がさらに続き、ＦＩＦＯメモリ３２−Ｂが満杯となると、識別コードを出力し、ＦＩＦＯメモリ３２−Ｂ内の符号データをすべて読み出して出力する。なお、ここではＦＩＦＯメモリ３２の容量を１６ワードとしている。図５に示すように、識別コードに続き、Ｂ_n+1からＢ_n+16が出力されている。
【００５６】
この例ではその後、符号化部３１−Ａから符号データの出力があり、Ａ_n+1，Ｂ_n+17，・・・と再び交互に読み出しおよび出力がなされている。もちろん、その後も符号化部３１−Ａから符号データの出力がなく、再びＦＩＦＯメモリ３２−Ｂが満杯となれば、識別コードとともにＦＩＦＯメモリ３２−Ｂ内のすべての符号データを出力する。符号化部３１−Ｂから符号データの出力が無く、ＦＩＦＯメモリ３２−Ａに符号データが蓄積されてゆく場合も同様である。このようにして、符号化部３１−Ａと符号化部３１−Ｂで別々に符号化した符号データを１つにまとめることができ、しかもデータ量の増加を抑えた合成符号データ３７を出力することができる。
【００５７】
上述の識別コードは、通常の符号と異なるものであれば何でもよい。例えば、ＪＢＩＧの規格で定められるＦＦ０４（１６進）などのコメントマーカを使用してもよい。
【００５８】
図６は、本発明の復号化装置の実施の一形態を示すブロック構成図である。図中、図１７と同様の部分には同じ符号を付して説明を省略する。４１は復号化部、４２はＦＩＦＯメモリ、４３はメモリ状態信号、４４はライト信号、４５は単位符号データ、４６は分割部、４７は合成符号データである。なお、図６では復号化部４１を２ブロック設けた例を示しており、一方をＡブロック、他方をＢブロックとして、各ブロックに関係する構成には‘−’の後にＡまたはＢを記して区別している。
【００５９】
分割部４６は、合成符号データ４７を分割して、単位符号データ４５−Ａ，Ｂとするとともに、メモリ状態信号４３−Ａ，Ｂを参照しながらＦＩＦＯメモリ４２−Ａ，Ｂを制御して、単位符号データ４５−Ａ，ＢをそれぞれＦＩＦＯメモリ４２−Ａ，Ｂに書き込む。分割部４６は、上述の符号化装置における合成部３６と全く逆の動作を行なう。すなわち、基本的には合成符号データ４７を所定のデータ量ごとに分割し、ＦＩＦＯメモリ４２−ＡまたはＦＩＦＯメモリ４２−Ｂに交互に書き込む。また、識別コードを検出した場合は、所定のデータ量の単位符号データを連続して一方のＦＩＦＯメモリに書き込む。
【００６０】
ＦＩＦＯメモリ４２−Ａ，Ｂは、復号化部４１−Ａ，Ｂにそれぞれ対応してその前段に設けられ、ライト信号４４−Ａ，Ｂに応じて所定のデータ量の単位符号データ４５−Ａ，Ｂを格納する。復号化部４１−Ａ，Ｂは、対応するＦＩＦＯメモリ４２−Ａ，Ｂから符号データ１０−Ａ，Ｂを読み出して復号する。
【００６１】
復号化部４１−Ａ，Ｂは、図１７に示した構成のうちコンテキスト生成部２を除く算術復号化部２１、確率推定テーブル６、逆予測部２２からなる。コンテキスト生成部２は、２つの復号化部４１−Ａ，Ｂに共通して設けられている。復号化部４１−Ａ，Ｂから交互に画像データ１が出力される。出力された画像データ１はコンテキスト生成部２に入力され、例えば図１２に示すようなテンプレートに従ってコンテキスト３を生成する。コンテキスト生成部２で生成されたコンテキスト３は、交互に復号化部４１−Ａまたは復号化部４１−Ｂに入力される。
【００６２】
次に、本発明の復号化装置の実施の一形態における動作の一例について説明する。例えば図５に示したような合成符号データ４７が分割部４６に入力される。分割部４６は、基本的には合成符号データ４７を所定のデータ量の単位、例えば１ワード単位に分割し、分割した単位符号データ４５−Ａ，Ｂをライト信号４４−Ａ，ＢとともにＦＩＦＯメモリ４２−Ａ，Ｂに交互に書き込む。書き込みに際しては、メモリ状態信号４３−Ａ，Ｂを参照し、書き込む側のＦＩＦＯメモリが満杯でないことを確認して行なう。
【００６３】
例えば図５に示す合成符号データ４７では、最初の１ワードの単位符号データＡ₀をＦＩＦＯメモリ４２−Ａに書き込み、次の１ワードの単位符号データＢ₀をＦＩＦＯメモリ４２−Ｂに書き込む。同様にしてＡ₁，・・・，Ａ_nをＦＩＦＯメモリ４２−Ａに、Ｂ₁，・・・，Ｂ_nをＦＩＦＯメモリ４２−Ｂにそれぞれ順次書き込んでゆく。メモリ状態信号４３−Ａ，Ｂを参照し、ＦＩＦＯメモリ４２−Ａ，Ｂのいずれかが満杯の状態の場合には、その時点で書き込みを一時停止する。
【００６４】
識別コードを検出すると、それに続く所定数の単位符号データは一方のＦＩＦＯメモリに書き込む。図５に示す合成符号データ４７の場合には、識別コードの前にＦＩＦＯメモリ４２−Ｂに書き込みを行なっているので、識別コードに続く１６ワードの単位符号データをＦＩＦＯメモリ４２−Ｂに順次書き込んでゆく。この場合もメモリ状態信号４３−Ｂを参照し、ＦＩＦＯメモリ４２−Ｂが満杯の状態の場合には書き込みを一時停止する制御を行なう。
【００６５】
各復号化部４１−Ａ，Ｂにおける動作は上述の図１７と同様であり、コンテキスト生成部２で生成されたコンテキスト３−Ａ，Ｂを用いて、ＦＩＦＯメモリ４２−Ａ，Ｂから読み出した符号データ１０−Ａ，Ｂを復号し、画像データ１−Ａ，Ｂとして出力する。このとき、復号化部４１−Ａ，Ｂは、コンテキスト生成部２から出力されるコンテキストを、復号する画素位置に応じて交互に取り込み、復号する。例えば図２（Ａ）に示す画像を復元する場合、図２（Ｂ）に示す画素を符号化した符号データを復号する復号化部４１−Ａは、２番目の添字が偶数となる画素の画像データを復号する際のコンテキスト３−Ａを取り込む。同様に、図２（Ｃ）に示す画素を符号化した符号データを復号する復号化部４１−Ｂは、２番目の添字が奇数となる画素の画像データを復号する際のコンテキスト３−Ｂを取り込む。
【００６６】
図７は、本発明の復号化装置の実施の一形態における復号化部の動作と画像データの出力の関係の一例を示すタイミングチャートである。復号化部４１−Ａ，Ｂには、それぞれ位相が異なるクロックが与えられており、このクロックに従って復号を行なう。復号処理によって、ある時点で復号結果である画像データが確定する。このとき、復号化部４１−Ａと復号化部４１−Ｂはそれぞれ独立に復号処理を行なっており、復号化部が１つの場合に比べて倍の速度で復号することが可能である。
【００６７】
復号化部４１−Ａと復号化部４１−Ｂとは位相の異なるクロックに従って動作しているので、図７に示すように復号結果が確定するタイミングが異なる。これを復号化部４１−Ａ，Ｂに与えられているクロックの１／２の周期の出力画像クロックによって交互に出力させる。これによって、図２（Ｂ）に示した画素を復号した復号化部４１−Ａの復号結果と、図２（Ｃ）に示した画素を復号した復号化部４１−Ｂの復号結果とが交互に選択されて、図２（Ａ）に示す画像のデータが順次出力されることになる。
【００６８】
また、このようにして復号化部４１−Ａ，Ｂの復号結果を交互に選択した画像データはコンテキスト生成部２にも入力される。これによってコンテキスト生成部２では、符号化時と同様に、図２（Ｄ）や（Ｅ）に示すような連続した画素を参照したコンテキストを生成することができる。
【００６９】
ところが、コンテキスト生成部２において、前画素の復号が終了しないと現画素のコンテキストが生成できないため、現画素の復号を行なうことができないという問題がある。すなわち、一方の復号化部で復号処理が遅れると、他方の復号処理を開始することができず、処理速度が低下してしまう。これを回避するために、例えば上述の特願平８−２８８７３１号に開示したように、復号時に前画素がとりうるすべての値に従って逆予測を行ない、複数の逆予測データを生成しておく。そして、前画素の値が確定した時点でいずれがの逆予測データを選択し、復号処理を高速化する方式が提案されており、本発明でもこの技術を用いることができる。
【００７０】
図６に示した本発明の復号化装置においては、それぞれの復号化部４１−Ａ，Ｂにおいて１画素おきに復号される。そのため、例えば復号化部４１−Ａで現画素を復号する際に、復号化部４１−Ａにおいて直前に復号処理した画素、すなわち原画像上では２画素前の画素と、他方の復号化部４１−Ｂにおいて復号している画素、すなわち原画像上の１画素前の画素をコンテキストに使用する。復号化部４１−Ａで直前に復号した画素については、値は確定しているものの、逆予測部２２内の逆予測テーブルの書き換えが発生している場合、書き換え完了まで逆予測が行なえない。また、復号化部４１−Ｂで復号する画素については、並行して処理を行なっているので値も確定していない場合がある。そのため、現画素の復号を行なう際には、原画像上の１画素前と２画素前の画素について、とりうるすべての値の組み合わせに対応した複数の逆予測値を求めておく。そして、復号化部４１−Ａで直前に復号した画素の値と、復号化部４１−Ｂで現在復号している画素の値が確定した時点で、これらの画素の値から複数の逆予測値の中から正しいものを選択すればよい。
【００７１】
このような動作を実現する構成を以下に示す。図８は、本発明の復号化装置の実施の一形態における復号化部の別の例を示すブロック構成図である。図中、５１〜５４は逆予測テーブル、５５は書き込み制御部、５６は書き込み信号、５７はライトアドレス、５８は選択部、５９は他復号化部からの画像データ、６０は前画像データである。ここでは、１つの復号化部の構成のみを示している。図８に示す構成が図６における復号化部４１−Ａ，Ｂに適用される。
【００７２】
この構成では、例えば図１２に示すテンプレートのＸ₁，Ｘ₀を除いたＸ₉〜Ｘ₂の８個の画像データからなるコンテキストを用いる。逆予測テーブル５１〜５４は、それぞれが例えば図１３に示すような構成のテーブルであり、ＲＡＭ等の記憶装置に格納されている。この逆予測テーブル５１〜５４のアドレスは、図１３に示したものと異なり、８ビットで構成されている。逆予測テーブル５１は、Ｘ₁，Ｘ₀の画素を０，０と仮定した時の逆予測値およびステートを格納している。同様に、逆予測テーブル５２〜５４は、Ｘ₁，Ｘ₀の画素をそれぞれ０，１、１，０、１，１と仮定したときの逆予測値およびステートをそれぞれ格納している。８ビットのコンテキストによって４つの逆予測テーブル５１〜５４からそれぞれ逆予測値およびステートが読み出されて、選択部５８に入力される。
【００７３】
選択部５８は、算術復号化部２１から出力される画像データ１を前画像データ６０として取り込むとともに、他復号化部からの画像データ５９を取り込み、これらに基づいて、逆予測テーブル５１〜５４から出力されている逆予測値およびステートのいずれかを選択し、ステートを確率推定テーブル６へ、逆予測値２３を算術復号化部２１へ出力する。例えば前画像データ６０が０で、他復号化部からの画像データ５９が０の場合には、逆予測テーブル５１の出力を選択する。同様に、前画像データ６０と他復号化部からの画像データ５９が０，１の場合には逆予測テーブル５２の出力を選択し、１，０の場合には逆予測テーブル５３の出力を選択し、１，１の場合には逆予測テーブル５４の出力を選択する。
【００７４】
書き込み制御部５５は、逆予測テーブル５１〜５４で利用するコンテキストＸ₉〜Ｘ₂を書き込みアドレスとして逆予測テーブル５１〜５４に対して出力するとともに、書き換え信号１２の書き換え指示に応じて、算術復号化部２１から出力される画像データ１および他復号化部からの画像データ５９の値から書き込みを行なうべき逆予測テーブル５１〜５４のいずれかを選択して、選択した逆予測テーブルに書き込み信号５６を送る。各逆予測テーブル５１〜５４には、確率推定テーブル６から出力されるＮＭＰＳまたはＮＬＰＳおよび算術復号化部２１から出力される新逆予測値が書き換えデータ２４として与えられているので、書き込み制御部５５から書き込み信号５６が送られた逆予測テーブルでは、同じく書き込み制御部５５から送られてくる書き込みアドレスに書き換えデータ２４が書き込まれる。
【００７５】
図９は、本発明の復号化装置の実施の一形態における復号化部の別の例の動作の一例を説明するためのタイミングチャートである。図９では、図２におけるＰ₂₄の位置の画素の復号を復号化部４１−Ａで行なう例を示している。復号化部４１−Ａでは、Ｐ₂₄の位置の画素を復号する直前に、Ｐ₂₂の位置の画素を復号する。書き込み制御部５５は、Ｐ₂₂の位置の画素を注目画素とするコンテキストＸ’₉〜Ｘ’₂を保持している。
【００７６】
Ｐ₂₂の位置の画素を復号中に、Ｐ₂₄の位置の画素を注目画素とするコンテキストＸ₉〜Ｘ₂が逆予測テーブル５１〜５４にアドレスとして入力される。逆予測テーブル５１〜５４から、それぞれＸ₁，Ｘ₀が００，０１，１０，１１の場合の４種類の逆予測値、ステートが読み出されて選択部５８に入力される。
【００７７】
一方、復号化部４１−ＢにおいてはＰ₂₃の位置の画素の復号が、復号化部４１−ＡにおけるＰ₂₂の位置の画素の復号に半周期遅れて開始される。やがて復号化部４１−ＡにおけるＰ₂₂の位置の画素が復号されて画像データが出力され、これが前画像データ６０として選択部５８に入力される。その後、復号化部４１−ＢにおけるＰ₂₃の位置の画素が復号されて画像データが出力され、他復号化部からの画像データ５９として選択部５８に入力される。この時点でＸ₁，Ｘ₀の値が００，０１，１０，１１のいずれであるかが確定されるので、選択部５８は逆予測テーブル５１〜５４のいずれかの出力（逆予測値、ステート）を選択して、Ｐ₂₄の位置の画素を復号するための逆予測値およびステートとして算術復号化部２１および確率推定テーブル６に渡す。これによって次の周期でＰ₂₄の位置の画素の復号を開始することができる。
【００７８】
また、Ｐ₂₂の復号によって逆予測テーブルの書き換えが発生した場合には、書き込み制御部５５は、保持しているＰ₂₂の位置の画素を注目画素とするコンテキストＸ’₉〜Ｘ’₂を書き込みアドレス５７として予測テーブル５１〜５４に出力する。また、算術復号化部２１から出力されるＰ₂₂の位置の画像データ１と、復号化部４１−Ｂから出力されるＰ₂₃の位置の画像データである他復号化部からの画像データ５９から書き換えるべき逆予測テーブルを特定し、その逆予測テーブルに対して書き込み信号５６を送る。逆予測テーブル５１〜５４には、確率推定テーブル６および算術復号化部２１から、Ｐ₂₂の位置の画像データに関する書き換えデータ２４が入力されているので、書き込み制御部５５から書き込み信号５６が与えられた逆予測テーブルは、書き込みアドレス５７のデータを書き換えデータ２４に書き換える。次のＰ₂₆の位置の画素の復号では、書き換えられた逆予測テーブルを用いて４種類の逆予測値およびステートが出力されることになる。
【００７９】
もちろん、復号化部４１−Ａから出力されるＰ₂₂，Ｐ₂₄の位置の画像データ１は、復号化部４１−Ｂに送られて他復号化部からの画像データ５９として用いられ、同様な処理で復号が実施される。
【００８０】
このようにして、逆予測テーブルの書き換え前でも逆予測テーブルの読み出しが可能であるので、算術復号化部２１の処理と逆予測テーブル５１〜５４の読み出しを並列的に実行することができ、復号処理を高速化することができる。
【００８１】
なお、逆予測テーブル５１〜５４は、他復号化部からの画像データ５９に対する１画素前の値のみによる２つの逆予測テーブルとして構成し、算術復号化部２１から画像データ１が出力された後にコンテキストＸ₉〜Ｘ₁を用いるようにしてもよい。また、３ポートメモリを用いて、２つあるいは１つのメモリで構成してもよい。
【００８２】
ここでは復号化装置について図８に示すような逆予測テーブルの先読みを行なって高速化する例を示したが、例えば上述の特願平８−３０１８８９号に記載されているように符号化装置について予測テーブルの先読みを行なうように構成すれば、符号化装置においても予測テーブルの書き込みよる遅延を発生させずに符号化処理を行なうことができ、符号化を高速に行なうことができる。
【００８３】
以上、本発明による符号化部あるいは復号化部を複数配置して並列処理を行なう符号化装置および復号化装置について、一例を示した。本発明は、これらの例に限られるものではない。例えば、符号化部、復号化部を２ブロックではなく、もっと多数の構成にしてさらに並列化することも可能である。また、合成部３６において合成する際の符号データのデータ量の単位も１ワード以外でよく、任意のデータ量を単位として、順次合成してゆくことができる。また、識別コード以後に続ける特定の符号化部からの符号データの単位数も任意に設定することができる。これらは復号化装置との間で設定可能であればよく、分割部４６は符号化時と同じ規則で合成符号データを分割すればよい。
【００８４】
また、ＦＩＦＯメモリ３２およびＦＩＦＯメモリ４２の容量も１６ワードに限るものではなく、任意の容量でよい。もちろん、ＦＩＦＯメモリ３２とＦＩＦＯメモリ４２の容量が異なっていてもよく、合成符号データの形式に合わせて合成部３６と分割部４６がＦＩＦＯメモリ３２、ＦＩＦＯメモリ４２を制御すればよい。
【００８５】
またさらに、本発明は予測符号化方式の符号データを合成符号データに合成するものに限られるものではなく、異なる符号化方式の符号データをも合成するように構成することも可能である。
【００８６】
以上のように本発明では、ＪＢＩＧなどの高速化が困難な符号化方式においても高速化することができるため、高速リアルタイム処理が必要となるプリンタ、複写機などのシステムにも、ＪＢＩＧ等の高能率の符号化方式を応用し、データを圧縮することが可能となる。
【００８７】
【発明の効果】
以上の説明から明らかなように、第１の発明の符号化装置によれば、並列処理した符号データを効率よく１つの符号に合成することができるため、合成された符号データのデータ量の増大を抑えるとともに、符号データの管理を簡易にすることができる。
【００８８】
また、第２の発明の復号化装置によれば、効率よく合成された符号データを入力として分割手段で複数の復号化手段に分配入力し、複数の復号化手段で並列処理が可能な復号化装置を得ることができるという効果がある。
【００８９】
このほか、予測符号化を複数の符号化手段で並列処理を行なうことができるので、高速に符号化を行なうことができる。このとき、前段に大きな画像メモリを必要とせず、またコンテキストを単体の符号化手段を用いる場合と同じように生成できるため、符号化効率を損なうこともなく符号化することができる。また、この符号化装置と同様に、前段に大きな画像メモリを必要とせず、複数の復号化手段で並列して復号処理を行なうことができるので、高速にリアルタイムで復号することができる。
【図面の簡単な説明】
【図１】本発明の符号化装置の実施の一形態を示すブロック構成図である。
【図２】画像データの一例の説明図である。
【図３】本発明の符号化装置の実施の一形態における画像の入力と各符号化部の動作の一例を示すタイミングチャートである。
【図４】本発明の符号化装置の実施の一形態における合成部の動作の一例を示すフローチャートである。
【図５】合成符号データの一例の説明図である。
【図６】本発明の復号化装置の実施の一形態を示すブロック構成図である。
【図７】本発明の復号化装置の実施の一形態における復号化部の動作と画像データの出力の関係の一例を示すタイミングチャートである。
【図８】本発明の復号化装置の実施の一形態における復号化部の別の例を示すブロック構成図である。
【図９】本発明の復号化装置の実施の一形態における復号化部の別の例の動作の一例を説明するためのタイミングチャートである。
【図１０】算術符号化の概念図である。
【図１１】ＪＢＩＧで採用されている予測符号化方式の概略図である。
【図１２】ＪＢＩＧで使用されるテンプレートの一例の説明図である。
【図１３】予測部４に記憶されている予測テーブルの一例の説明図である。
【図１４】確率推定テーブル６の一例の説明図である。
【図１５】入力される画像データの一具体例の説明図である。
【図１６】書き換え後の予測部テーブルの一具体例の説明図である。
【図１７】ＪＢＩＧで採用されている予測復号化方式の概略図である。
【図１８】算術復号化部の基本動作の説明図である。
【符号の説明】
１…画像データ、２…コンテキスト生成部、３…コンテキスト、４…予測部、５…ステート、６…確率推定テーブル、７…ＬＳＺおよびＳＷ、８…予測値、９…算術符号化部、１０…符号データ、１１…書き換えデータ、１２…書き換え信号、２１…算術復号化部、２２…逆予測部、２３…逆予測値、２４…書き換えデータ、３１…符号化部、３２…ＦＩＦＯメモリ、３３…メモリ状態信号、３４…リード信号、３５…単位符号データ、３６…合成部、３７…合成符号データ、４１…復号化部、４２…ＦＩＦＯメモリ、４３…メモリ状態信号、４４…ライト信号、４５…単位符号データ、４６…分割部、４７…合成符号データ、５１〜５４…逆予測テーブル、５５…書き込み制御部、５６…書き込み信号、５７…ライトアドレス、５８…選択部、５９…他復号化部からの画像データ、６０…前画像データ。

Claims

画素ごとに順次振り分けられて入力されたデータを符号化する複数の符号化手段と、該複数の符号化手段で生成された符号データをそれぞれ格納する複数のメモリと、前記複数のメモリから前記符号データを読み出して単位符号データごとに所定の順序で１つの合成符号データに合成する合成手段を有し、該合成手段は、ある符号化手段において出力すべき符号データを格納する前記メモリが空で、かつ、他の符号化手段に対応する前記メモリが満杯の場合には識別子とともに他の符号化手段の出力する前記符号データを当該他の符号化手段に対応する前記メモリからすべて読み出して出力することを特徴とする符号化装置。