(57)【要約】【課題】ＭＲ方式やＭＭＲ方式により、２値画像データを高速に圧縮・伸張する。【解決手段】処理対象ラインである符号化ラインＬｃｏｄｅの変化点と、符号化ラインＬｃｏｄｅの直前に処理したラインである参照ラインＬｒｅｆの変化点とから白黒画像の圧縮および／または伸張を行ない、変化点メモリ１２により、個数がライン幅画素数よりも少ない変化点を保持しておく。【選択図】　　　　図１
2004072155.tif 000002
【特許請求の範囲】
【請求項１】
処理対象ラインで符号化ラインの変化点と、前記符号化ラインの直前に処理したラインである参照ラインの変化点とからモノクロ画像の圧縮および／または伸張を行なう二次元符号化装置において、
保持できる変化点の個数がライン幅画素数よりも少ないメモリを備えたことを特徴とする二次元符号化装置。
【請求項２】
前記メモリに保持できる変化点の個数を指定できることを特徴とする請求項１に記載の二次元符号化装置。
【請求項３】
参照ラインの変化点の個数が、前記メモリに保持された変化点の個数を超えるときは、前記メモリに保持されていない参照ラインの変化点を、当該参照ライン上の画素を走査することで求めることを特徴とする請求項２に記載の二次元符号化装置。
【請求項４】
あるラインの符号化処理における、処理起点となる画素以降に表われる符号化ラインの変化点を、当該符号化ラインの変化点として保持するメモリを備えたことを特徴とする１から３の何れかに記載の二次元符号化装置。
【請求項５】
復号に際して、参照ラインが全ビット白であることを示すフラグを備えたことを特徴とする請求項１から４の何れかに記載の二次元符号化装置。
【請求項６】
復号に際して、前記フラグを参照して符号化ラインが全ビット白色であるか否かを判断することことを特徴とする請求項１から５の何れかに記載の二次元符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＭＲ方式やＭＭＲ方式により、２値画像データを高速に圧縮・伸張することができる二次元符号化装置に関する。
【０００２】
【従来の技術】
ファクシミリ装置では、静止画像データの伝送・記録を、極力少ない情報量で処理するために、各種の符号化・復号技術が提案されている。その符号化・復号技術の一つに、二次元符号化方式である変更読取り（ＭＲ：Ｍｏｄｉｆｉｅｄ　ＲＥＡＤ）符号化方式や、その変形である重複変更読取り（ＭＭＲ）符号化方式がＣＣＩＴＴの勧告として知られている。
【０００３】
モノクロファクシミリ装置における２値画像情報は、振幅方向（白黒）と時間軸方向に量子化されており、時間軸方向の黒の連続個数は、ランレングス（ＲＬ）として、２進符号によって表現される。
【０００４】
ＭＲ方式あるいはＭＭＲ方式は、現在処理対象となっているラインと、すぐ直前に処理したライン上の信号の値（「０」または「１」）との関係を逐次利用しながら符号化するもので、ライン方向の信号の値（「０」または「１」）のみに基づいて符号化する１次元符号化方式に比べて高い圧縮率が得られる。
ＭＲ符号化方式では、符号化処理の対象となるライン（符号化ライン）上の変化点の位置と、直前に符号化処理を行なったライン（参照ライン）上の所定化点の位置を参照して圧縮／伸張するものである。
【０００５】
符号化が完了したラインを、次のラインの符号化に際しての参照ラインとするこの方式では、符号化誤りの波及を防止するため１次元符号化方式を併用するのが一般的であり、所定おきのライン毎に１次元符号化を行い、残りのラインはＭＲ符号化を行うものもある。
【０００６】
この方式をソフトウェアで実現する場合には、図６（Ａ）に示すように、変化点を求め（Ｓ５０１）、符号化・復号化（圧縮・伸張）を行い（Ｓ５０２）、符号化・復号化データを出力している（Ｓ５０３）。図６（Ｂ）に、符号化ライン、参照ライン、および符号化ライン上の起点ａ０、変化点ａ１，ａ２、参照ライン上の変化点ｂ１，ｂ２を例示しておく。ａ１は、ａ０より右の符号化ライン上の変化点であり、ａ２はａ１より右の符号化ライン上の変化点である。また、ｂ１は、ａ０より右の参照ライン上の変化点であり、ｂ２はａ１より右の符号化ライン上の変化点である。
【０００７】
しかし、この符号化の実現方法では、処理時間が長くなる欠点があり、従来からソフトウェア処理での高速化が一つの課題となっている。たとえば、特開平０６−２４５０８４号では、画像データの符号化・復号化処理に際し、処理量を大幅に削減することによって処理の高速化を図っている。この技術では、ＭＲ方式やＭＭＲ方式のような、符号化ラインの白黒画素の変化点の位置情報、および参照ライン（直前に処理したライン）の白黒画素の変化点の位置情報に従って符号化・復号を行なう符号化方式において、符号化の対象となるラインの白黒画素の変化点の位置情報を順次記憶するための変化点メモリを備え、次のラインの符号化・復号化に際し前記記憶した変化点位置情報を参照ラインとして使用するように構成している。
【０００８】
【発明が解決しようとする課題】
しかし、この符号化技術では、想定される最大の変化点数（主走査幅の画素数とほぼ同数の変化点の数）を保持するためのメモリが必要となる。
また、符号化ラインの処理において、当該符号化ラインでの変化点ａ１（起点画素ａ０を基準にして初めて「色」が変る変化点ａ１）が、複数回の符号化が行なわれる場合に、その都度変化点を求めなければならず、処理の高速化が十分に達成されない。
【０００９】
また、復号における全ビット白画像の場合の処理において、参照画素の変化点を求める処理が必要となるため、処理の高速化が十分に達成されない。
【００１０】
【課題を解決するための手段】
本発明の二次元符号化装置は、処理対象ラインで符号化ラインの変化点と、前記符号化ラインの直前に処理したラインである参照ラインの変化点とからモノクロ画像の圧縮および／または伸張を行なうもので、保持できる変化点の個数がライン幅画素数よりも少ないメモリを備えたことを特徴とする。
【００１１】
従来では、各ラインの符号化，復号を行なうごとに、各変化点ａ１，ａ２，ｂ１，ｂ２をそれぞれ求めて符号化，復号を行っていたが、上記の例では、求める変化点の数を最低限にすることで、ソフトウェアによる符号化，復号における処理の高速化を行なうことができる。
【００１２】
本発明の二次元符号化装置では、前記メモリに保持できる変化点の個数を指定できる。また、符号化ラインの変化点を常に保持しようとする場合には、主走査幅分だけのデータを保持するメモリが必要になるが、本発明では、変化点メモリ１２に保持できる変化点ａ１，ａ２の個数を、主走査方向の画素数（ライン幅画素数）よりも少なくしてあるので、メモリ資源の有効利用を図ることができる。変化点メモリ１２に保持できる変化点ａ１，ａ２の個数は、適宜のユーザインタフェースを用いてユーザが適宜変更するようにしてもよい。
【００１３】
本発明の二次元符号化装置では、参照ラインの変化点の個数が、前記メモリに保持された変化点の個数を超えるときは、前記メモリに保持されていない参照ラインの変化点を、当該参照ライン上の画素を走査することで求めることができる。
【００１４】
また、あるラインの符号化処理における、処理起点となる画素以降に表われる符号化ラインの変化点を、当該符号化ラインの変化点として保持するメモリを備えることができる。すなわち、符号化において、符号化ラインは次のラインで参照ラインに変化する。したがって、符号化ラインで変化点を保持しておくと次のラインで参照ラインの変化点を求める必要が無くなる。そのため，符号化ラインで各変化点を保持しておき，次のラインでは参照ラインの変化点ｂ１，ｂ２を求める必要が無くなる。これにより、変化点を求める時間を短縮でき、高速化につながる。
【００１５】
本発明の二次元符号化装置では、復号に際して、参照ラインが全ビット白であることを示すフラグを備えることができる。これにより、復号において、参照ラインが全ビット白であるときに、ｂ１，ｂ２を求める時間の短縮を行なうことができる。復号化においては、前記フラグを参照して、符号化ラインが全ビット白である事を判断することができる。
【００１６】
【発明の実施の形態】
二次元符号化方式は，ＭＭＲ符号化方式および，ＭＲ符号化方式に用いられるもので，ＴＴＣ標準ＪＴ−Ｔ４（旧ＣＣＩＴＴ　Ｔ．４）及びＪＴ−Ｔ．６にて勧告されている。二次元符号化では、変化点ａ０，ａ１，ａ２，ｂ１，ｂ２をパラメータ（変化点）として用いて、３種の符号化モードでの圧縮，伸張を行う。図１は、本発明の二次元符号化装置の回路構成を示すブロック構成図である。図１においては、二次元符号化装置１は符号ＲＯＭ１１と、変化点メモリ１２と、復号部１３、画像データ生成部１４と、変化点検出部１５と、符号化部１６と、レジスタ１７とを含む。
【００１７】
符号ＲＯＭ１１は、ＭＲ，ＭＭＲの符号化表データ等を記憶する読み出し専用に使用される。具体的には、ランレングス（ラン長）と符号とのテーブルであり、符号長は、ラン長により最適化されている。
変化点メモリ１２は、参照ライン、符号化ライン（本発明では復号されるラインを含む）の変化点位置情報を記憶するための読み出し・書込み可能なＲＡＭである。
【００１８】
復号部１３は、符号データ（圧縮）を符号ＲＯＭ１１に従って復号し、変化点メモリの参照ライン情報に基づいて符号化ラインの変化点情報を生成すると共に、符号化ラインの変化点を変化点メモリ１２に記憶する機能を持つ。
画像データ生成部１４は、変化点メモリ１２の符号化ライン情報から復号化ラインの画像データを生成し、外部（所定の記憶部）に出力する。
【００１９】
変化点検出部１５は、外部（所定の記憶部）より入力された画像データから白黒画素変化点を検出し変化点メモリ１２に記憶させる。
符号化部１６は変化点メモリ１２の情報を元に、符号ＲＯＭ１１に従って符号化を行い外部に符号データを出力する符号化部である。レジスタ１７には符号化ラインＬｃｏｄｅの全画素が白色のときにフラグが立てられる。
【００２０】
図２のフローチャートにより、図１の回路の概略動作を説明する。図２では、まず二次元符号化に必要な変化点の設定に際して、必要な変化点が変化点メモリ１２に記憶されているか否かをチェックする。変化点は符号化ラインＬｃｏｄｅにおけるものと、参照ラインＬｒｅｆにおけるものがある。符号化ラインＬｃｏｄｅにおいて求められた変化点は、次の行の処理では参照ラインＬｒｅｆの変化点として使用される。すなわち、参照ラインＬｒｅｆで使用される変化点は、すでに符号化ラインにおいて使用された変化点である。本発明では、変化点メモリ１２に保持できる変化点の個数は、ライン幅画素数よりも少ない。したがって、符号化ラインの変化点数が、メモリに設定されら変化点の記憶個数よりも多い場合がある。このため、まず変化点メモリ１２に変化点が保持されているか否かをチェックし（Ｓ１０１）、変化点メモリ１２に変化点が保持されていない場合には、各変化点を求める（Ｓ１０４）。変化点メモリ１２に変化点が保持されている場合には、保持している変化点を参照ラインの変化点に設定し（Ｓ１０２）、残りの変化点を求める（Ｓ１０３）。この後、符号化または復号を行ない（Ｓ１０５）、符号化ラインの変化点を保持し（Ｓ１０６）、処理後データを出力する。
【００２１】
図３（Ａ）〜（Ｃ），図４および図５により、圧縮処理、伸張処理を説明する。図３（Ａ）〜（Ｃ）において、参照ラインＬｒｅｆは、既に圧縮，伸張されたラインであり、圧縮・伸張するときに参照される。符号化ラインＬｃｏｄｅは、二次元符号化を現に行っているラインである。
【００２２】
符号化ラインの変化点ａ０は、起点の変化点であり、初めはラインの最初の画素に配置され、ラインの最初の画素が黒の場合は、仮想的に白画素を配置し、その位置に配置する。変化点ａ０は、後述するように、順次、ラインの一次元座標を移動する。移動位置の定義は、パスモード、垂直モード、水平モードの３種の符号化モードのうち、どの符号化モードかにより異なる。
【００２３】
変化点ａ１は、ａ０より右側の、符号化ライン上の、最初に「色」が直前の画素と異なったときの当該画素として定義される。変化点ａ２は、ａ１より右側の、符号化ライン上の、最初に「色」が直前の画素と異なったときの当該画素として定義される。
【００２４】
変化点ｂ１は、ａ０より右側の、参照ライン上の、最初に「色」が直前の画素と異なったときの当該画素として定義される。変化点ｂ２は、ｂ１より右側の、参照ライン上の、最初に「色」が直前の画素と異なったときの当該画素として定義される。
【００２５】
パスモードによる符号化，復号が行なわれる条件は、ａ１の左側にｂ２が存在することである。この場合には、パスモードであるという符号語０００１を送り、終了時に、ａ０をｂ２の真下の位置に変更する。この後、新たにａ０より右側の符号化，復号が行なわれる。
垂直モードによる符号化，復号が行なわれる条件は、ａ１とｂ１の相対距離が、
｜ａ１−ｂ１｜≦３
であることである。
【００２６】
この場合、ｂ１を基準にａ１が右のときは、所定データ領域に、ＶＲ，左のときはＶＬ，直下のときはＶ０をセットする。終了時に、ａ０をａ１の位置に変更する。すなわち、ａ１がｂ１の直下から、左右３画素以内にあるときは、参照ラインとの相関を利用すべく、ａ１のｂ１に対する位置（相対的な位置）を送り、ａ０を、ａ１の位置に変更し、新たな処理を行なう。すなわち、直下にあれば、符号語１を送る。ａ１がｂ１の直下の右１画素の位置にあれば０１１を、右２画素の位置にあれば００００１１を、右３画素の位置にあれば０００００１を送る。また、ａ１がｂ１の直下の左１画素の位置にあれば０１０を、左２画素の位置にあれば００００１０を、左３画素の位置にあれば０００００１０を送る。この後、新たにａ０より右側の符号化，復号が行なわれる。
【００２７】
水平モードによる符号化，復号が行なわれる条件は、パスモード、垂直モードの何れでもないとき、すなわちａ１がｂ１の直下から、左右４画素以遠にある場合であり、この場合には、水平モードであるという記号００１＋Ｍ（ａ０ａ１）＋Ｍ（ａ１ａ２）を送る。ただし、ただし、Ｍ（ｘｙ）はｘからｙまでのランレングスを一次元符号化したものである。すなわち、この場合には、参照ラインとの相関が薄いので、モード符号語として００１を送った後、ａ０からａ１までと、ａ１からａ２までの各ラン長をＨｕｆｆｍａｎ符号化して送り、ａ０を、ａ２の位置に変更し、新たな処理を行なう。この後、新たにａ０より右側の符号化，復号が行なわれる。
【００２８】
図４はファクシミリ装置での圧縮における処理を示すフローチャートである。まず、１ライン分の処理が開始されると（ステップＳ２０１）、前ラインａ１＞ａ０となるａ１が保持されているか否かをチェックする（ステップＳ２０２）。
【００２９】
ａ０は、符号化ライン上の参照または起点変化点である。初めは図３（Ａ）に示すように、ラインの先頭の画素に配置される。なお、ラインの最初の画素が黒の場合は、仮想的に白画素を、先頭が画素の位置に配置する。
【００３０】
ａ０が、符号化ラインＬｃｏｄｅの１つ前の処理におけるａ１′（「′」は１つ前の処理を示す）よりも大きいとき（ａ０＞ａ１′）は、今回においてもａ１は変化しないので、ａ１を求めることなく、変化点メモリ１２に、参照ラインＬｒｅｆの変化点ｂ１，ｂ２が保存されているか否かを参照する（Ｓ２０４）。なお、変化点ｂ１，ｂ２はメモリに保存された序列で順次参照される。符号化ラインＬｃｏｄｅの１つ前の処理におけるａ１′（「′」は１つ前の処理を示す）よりも小さいとき（ａ０≦ａ１′）は、今回処理の変化点は、１つ前の処理における変化点（ａ１′）と異なるので、新たにａ１を求める（Ｓ２０３）。
【００３１】
Ｓ２０４において、新たな変化点が保持されているときは、参照ラインの変化点ｂ１，ｂ２に、保持されている直前ラインの符号化処理における変化点ａ１，ａ２を設定する（Ｓ２０５）。変化点メモリからの変化点の読み出しは、メモリに格納されている順に順次行なわれる。
【００３２】
Ｓ２０４において、新たな変化点が保持されていないとき（変化点メモリ１２から参照すべき変化点がなくなってしまったとき）は、ｂ１，ｂ２を求める（Ｓ２０６）
【００３３】
つぎに、上記のようにして求めたａ１，ｂ１，ｂ２を用いてどの符号化モードに移行するかを決定する（Ｓ２０７）。
すなわち、ｂ２＜ａ１のときはパスモードに移行し（Ｓ２０８）、｜ａ１−ｂ１｜≦３のときは水平モードに移行し（Ｓ２０９）、｜ａ１−ｂ１｜＞３のときは垂直モードに移行する（Ｓ２１０）。この後、符号化ラインａ１，ａ２の値を変化点メモリ１２に保持する（Ｓ２１１）。この場合には、すでに参照された変化点ａ１，ａ２（ｂ１，ｂ２に設定されたａ１，ａ２）は消去される。
【００３４】
つぎに、Ｓ２０８〜Ｓ２０９での処理において、処理が正常に終了したか否かを判断し（Ｓ２１２）、正常のときには、次のラインの処理に移行するが（Ｓ２１４）、ビット抜け等の異常が生じたときは「異常終了」とする（Ｓ２１３）。
二次元符号化方式の符号化モードがパスモードの場合やＶＬ，Ｖ０の場合などは保持しているａ１に変化が起きない為，ａ１を新たに求める必要が無い。そのため，ａ１を保持しておき，新たにａ１を求める必要が無い場合は保持しているａ１を用いる事により時間が短縮される。次に復号について説明を行う。図４に詳細な処理フローを示す。
【００３５】
図５はファクシミリ装置での伸張における処理を示すフローチャートである。まず、１ライン分の処理の開始される前に符号化ラインの変化点を参照ラインの変化点にコピーしておき（ステップＳ３０１）、１ライン分の処理を開始する（Ｓ３０２）。
【００３６】
ここで、まず参照ラインＬｒｅｆは全ビット白色か否かをレジスタ１７のフラグを参照してチェックする（Ｓ３０３）。全ビット白のときは、「符号化ラインの先頭で、かつ符号化モードはＶ０」であるか否かをチェックする（Ｓ３０４）。Ｖ０である場合は、ｂ１，ｂ２は参照ラインの行末にあるので、ａ１も行末であることがわかる。したがって、符号化ラインＬｃｏｄｅは全ビット白色であることがわかるので、符号化ラインＬｃｏｄｅに全ビット白色をセットする（Ｓ３０５）。つぎに、符号化ラインＬｃｏｄｅの変化点に主走査幅をセットし（Ｓ３０６）、処理を終了する。
【００３７】
Ｓ３０４で、「符号化ラインの先頭で、かつ符号化モードはＶ０」でないことがチェックされたときは、参照ラインＬｒｅｆの変化点ｂ１，ｂ２に主走査幅をセットする（Ｓ３０７）。この場合には前述した３つの符号化モードにしたがって復号を行なう（Ｓ３１２）。
【００３８】
Ｓ３０３において、参照ラインＬｒｅｆは全ビット白色でないことがチェックされたときは、参照ラインＬｒｅｆの変化点ｂ１，ｂ２に対応する変化点が変化点メモリ１２に存在するか否かをチェックする（Ｓ３０８）。変化点ｂ１，ｂ２に対応する変化点が変化点メモリ１２に保持されているときは、ｂ１，ｂ２に保持している参照ラインＬｒｅｆの変化点をセットするが（Ｓ３０９）、保持されていないときは変化点ｂ１，ｂ２を求める（Ｓ３１０）。
【００３９】
Ｓ３０９で、保持している参照ラインＬｒｅｆの変化点をｂ１，ｂ２にセットし、Ｓ３１０で変化点ｂ１，ｂ２を求めたときは、符号化モードにしたがった復号を行い（Ｓ３１１）、符号化ラインの変化点を変化点メモリ１２保持しておく（Ｓ３１２）。ここで、ループ処理は終了するが（Ｓ３１３）、次の符号化ラインに処理に移行する前に、符号化ラインは全ビット白色であるか否かの判断を行い（Ｓ３１４）、符号化ラインＬｃｏｄｅが全ビット白色のときは、それを示すフラグをレジスタ１７に立てる（Ｓ３１５）。
【００４０】
【発明の効果】
本発明によれば、二次元符号化方式の符号化および復号を高速に実現することができる。また、符号化ラインを符号化している時に求めた変化点を，次のラインの先頭、またはそのラインの終了時にコピーを行い、参照ラインで保持している変化点を用いることで、ｂ１，ｂ２を求める時間を短縮することができる。
【００４１】
また、メモリの容量によって保持する変化点の数を変えることにより、メモリ資源の有効利用を図ることができる。
符号化ラインの変化点ａ１を保持し，次の変化モードがパスモードのときには、保持しているａ１を用いることができるので、新たにａ１を求める時間を短縮することができる。
【００４２】
さらに、伸張処理において、参照ラインが全ビット白であることを示すフラグを用いることで，ｂ１およびｂ２を求める時間を短縮することもできる。具体的には、参照ラインが全ビット白色であることを示すフラグが立っており、かつ次の符号化モードがＶ０モードであるときには、その符号化ラインは全ビット白であることが判定できるので、処理の高速化を図ることができる。
【図面の簡単な説明】
【図１】本発明の二次元符号化装置の回路構成を示すブロック構成図である。
【図２】図１の回路の概略動作を説明するためのフローチャートである。
【図３】（Ａ）〜（Ｃ）は、圧縮処理、伸張処理を説明するための説明図である。
【図４】ファクシミリ装置での圧縮における処理を示すフローチャートである。
【図５】ファクシミリ装置での伸張における処理を示すフローチャートである。
【図６】（Ａ）は従来の符号化方式の処理を示すフローチャートであり、（Ｂ）は符号化ライン、参照ライン、および各ライン上の各変化点を例示する図である。
【符号の説明】
１　二次元符号化装置
１１　符号ＲＯＭ
１２　変化点メモリ
１３　復号部
１４　画像データ生成部
１５　変化点検出部
１６　符号化部
１７　レジスタ
【図１】
2004072155.tif 000003
【図２】
2004072155.tif 000004
【図３】
2004072155.tif 000005
【図４】
2004072155.tif 000006
【図５】
2004072155.tif 000007
【図６】
2004072155.tif 000008