(57)【要約】【課題】  ランレングス符号化を迅速に行う。【解決手段】  ランレングス符号化装置１００は、２値画像データのビット列を符号化する。ランレングス取得部１０６は、検出対象の先頭ビットと同値のデータの連続数を所定単位時間毎に取得する。【選択図】      図１
2005252408.tif 000002
【特許請求の範囲】
【請求項１】
２値画像データのビット列を符号化する符号化装置であって、
検出対象の先頭ビットと同値のデータの連続数を所定単位時間毎に取得するランレングス取得手段と、
前記ランレングス取得手段により取得された連続数に基づき、前記ビット列を符号化する符号化手段と、
を含むことを特徴とする符号化装置。
【請求項２】
請求項１に記載の符号化装置において、
前記ランレングス取得手段は、前記先頭ビットと異なるビットが出現する桁が所定位置になるように前記ビット列をシフトし、シフトした桁数に基づいて前記連続数を取得することを特徴とする符号化装置。
【請求項３】
請求項１または２に記載の符号化装置において、
前記ランレングス取得手段は、所定ビット数を検出対象のビット列として前記連続数を取得し、一の前記所定ビット数のビット列の最後のビットと次の前記所定ビット数のビット列の最初のビットの値が同じである場合、前記一のビット列の最後の部分の連続数と前記次のビット列の最初の部分の和を連続数として算出する処理を行うことを特徴とする符号化装置。
【請求項４】
コンピュータに、２値画像データのビット列を符号化させるためのプログラムであって、
コンピュータを、
検出対象の先頭ビットと同値のデータの連続数を所定単位時間毎に取得するランレングス取得手段、
前記ランレングス取得手段により取得された連続数に基づき、前記ビット列を符号化する符号化手段、
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置に関する。
【背景技術】
【０００２】
ファクシミリ装置における送信原稿の符号化やＭＦＰにおけるＰＣプリント受信データの圧縮方法として、ランレングス符号化が知られている。多くのシステムでは、画像データの１ドットをメモリの１ビットとして処理を行う。ランレングス符号化とは、たとえば２値画像データのビット列を「０」が連続する個数、と「１」が連続する個数に変換し、その連続個数を符号化することによりデータ量を少なくするものである（特許文献１）。
【０００３】
従来、ランレングス符号化では１ビットずつ読み出して各ビットの値を評価するという処理が行われていた。そのため、ランレングスを求めるのに時間がかかるという問題があった。とくに、このような符号化をプログラムコード上でソフト的に行う場合、ランレングスを求める処理に時間がかかるため、全体の処理速度を短縮することができなかった。
【特許文献１】特開平６−１６９４０６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明はこうした点に鑑みてなされたもので、その目的は、ランレングス符号化を迅速に行う技術の提供にある。
【課題を解決するための手段】
【０００５】
本発明の符号化装置は、２値画像データのビット列を符号化する。符号化装置は、検出対象の先頭ビットと同値のデータの連続数を所定単位時間毎に取得するランレングス取得手段と、ランレングス取得手段により取得された連続数に基づき、ビット列を符号化する符号化手段と、を含む。ここで、所定単位時間毎とは、たとえば１クロック毎とすることができる。
【０００６】
本発明の符号化装置において、ランレングス取得手段は、先頭ビットと異なるビットが出現する桁が所定位置になるようにビット列をシフトし、シフトした桁数に基づいて連続数を取得することができる。
【０００７】
本発明の符号化装置によれば、同値のデータの連続数をたとえば１クロック毎の所定単位時間毎に取得するので、ランレングス符号化を迅速に行うことができる。このような処理は、たとえば、ＤＳＰの機能である規格化補助命令ＮＯＲＭやＬＭＢＤ（Ｌｅｆｔ  Ｍｏｓｔ  Ｂｉｔ  Ｄｅｔｅｃｔｉｏｎ）を用いて行うことができる。
【０００８】
本発明の符号化装置において、ランレングス取得手段は、所定ビット数を検出対象のビット列として連続数を取得することができ、一の所定ビット数のビット列の最後のビットと次の所定ビット数のビット列の最初のビットの値が同じである場合、一のビット列の最後の部分の連続数と次のビット列の最初の部分の和を連続数として算出する処理を行うことができる。
【０００９】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラム等の間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１０】
本発明によれば、ランレングス符号化を迅速に行うことができる。
【発明を実施するための最良の形態】
【００１１】
（第一の実施の形態）
図１は、本実施の形態における符号化装置の構成を示すブロック図である。本実施の形態において、ランレングス符号化装置１００は、たとえばインターネットファクシミリ装置やＭＦＰ（Multi Functional Peripheral）等のファクシミリ装置に設けられる。
【００１２】
ランレングス符号化装置１００の各構成要素は、ハードウエアコンポーネントでいえば、任意のコンピュータのＣＰＵ、メモリ、メモリにロードされた本図の構成要素を実現するプログラム、そのプログラムを格納するハードディスク等の記憶ユニット、ネットワーク接続用インターフェース、ファクシミリ通信用モデム等を中心に実現されるが、その実現方法、装置にはいろいろな変形例があることは、当業者には理解されるところである。これから説明する各図は、ハードウエア単位の構成ではなく、機能単位のブロックを示している。
【００１３】
ランレングス符号化装置１００は、データ取得部１０２と、初期化処理部１０４と、ランレングス取得部１０６と、ランレングスデータ記憶部１０８と、符号化処理部１１０と、データ出力部１１２とを含む。ランレングス符号化装置１００は、図示しない原稿読み取り部が読み取った原稿の画像データを１ライン毎に処理する。以下、１ラインの画像データを処理する例を説明する。
【００１４】
データ取得部１０２は、画像データを１ライン毎に取得する。初期化処理部１０４は、データ取得部１０２が取得した画像データのランレングスを検出するための初期化を行う。ランレングス取得部１０６は、検出対象の先頭ビットと同値のデータの連続数を所定単位時間毎に取得する。具体的には、ランレングス取得部１０６は、先頭ビットと異なる値を持つビットを探し、そのビットまでの桁数を検出する。その桁数までの数に基づき、ランレングスを取得する。
【００１５】
本実施の形態において、ランレングス取得部１０６は、ＤＳＰ（デジタルシグナルプロセッサ）の機能である規格化補助命令ＮＯＲＭを用いてランレングスを取得する。このような方法を用いることにより、ソフトウェア的にビット毎に順次比較をする方式に比べて高速にランレングスを取得することができる。図２は、ビット列のパターンとそのときにＮＯＲＭにより得られる返数Ｎ（ｘ）を示す図である。たとえば、先頭ビットが「０」で、次のビットが「１」の場合、返数Ｎ（ｘ）は「０」となる。また、先頭ビットが「０」で次のビットが「０」、その次のビットが「１」の場合、返数Ｎ（ｘ）は「１」となる。同様に、先頭ビットが「１」で、次のビットが「０」の場合、返数Ｎ（ｘ）は「０」となる。また、先頭ビットが「１」で次のビットが「１」、その次のビットが「０」の場合、返数Ｎ（ｘ）は「１」となる。ランレングス取得部１０６は、ＮＯＲＭにより得られた返数Ｎ（ｘ）に１を足した値をランレングスとして取得する。
【００１６】
次に、本実施の形態におけるランレングス符号化装置１００の処理手順を図３を参照して説明する。ここでは、ランレングス取得部１０６が３２ビット毎のビット列を対象にしてランレングスを取得する場合を例として説明する。
【００１７】
まず、初期化処理部１０４が初期化を行う（Ｓ１０）。ここでは、ラン値Ｒを初期化してゼロとするとともに、比較用ビット値Ｆを初期化して、たとえば「１（黒）」とする。つづいて、データ取得部１０２が処理対象の３２ビットのデータをロードして「Ａ」とする（Ｓ１２）。また、このとき、先頭ビットの位置「Ｘ」をゼロとしておく。
【００１８】
つづいて、データ取得部１０２は、先頭ビットが「Ｆ」と一致するか否かを判断する（Ｓ１４）。ファクシミリ装置で読み取る原稿では、ラインの最初のビットは「０（白）」であることが多い。そのため、本実施の形態において、上述したように、比較用ビット値Ｆを「１（黒）」と設定しておき、ステップＳ１４において、先頭ビットがＦと一致するか否かを判断する。ステップＳ１４において、先頭ビットがＦの場合（Ｓ１４のＹ）、ランレングス取得部１０６は、このときのＲ（＝０）をランレングスとして決定する（Ｓ１６）。これにより、ラインの最初のビットが「０」でない場合、最初のランレングスとしてＲ＝０が得られる。その後、初期化処理部１０４は、ラン値Ｒをリセットしてゼロとする（Ｓ１８）。
【００１９】
ステップＳ１８の後、およびステップＳ１４において先頭ビットが「Ｆ」でない場合（Ｓ１４のＮ）、ランレングス取得部１０６は、ＮＯＲＭを用いて返数Ｎ（ｘ）を取得する（Ｓ２０）。このＮＯＲＭを用いて返数Ｎ（ｘ）を取得する処理は、たとえば１クロック毎等の所定単位時間毎に行われる。これにより、ソフトウェア的にビット毎に順次比較をする方式に比べて高速にランレングスを取得することができる。つづいて、ランレングス取得部１０６は、もとのＲに「Ｎ（ｘ）＋１」を加えて新たなＲとする（Ｓ２２）。
【００２０】
その後、ランレングス取得部１０６は、もとの先頭ビットの位置Ｘに「Ｎ（ｘ）＋１」を加えて新たなＸとする（Ｓ２４）。つづいて、ランレングス取得部１０６は、Ｘが３２以上であるか否かを判断する（Ｓ２６）。
【００２１】
Ｘが３２未満の場合（Ｓ２６のＮ）、Ａを「Ｎ（ｘ）＋１」だけシフトする（Ｓ３０）。その後、Ｓ１６に戻り、同様の処理を繰り返す。
【００２２】
一方、Ｓ２６でＸが３２以上である場合（Ｓ２６のＹ）、暫定Ｒを補正する（Ｓ３４）。ステップＳ２２で求めたＲから（Ｘ−３２）を減じ、新たなＲとする。つづいて、ライン終端に達しているか否かを判断する（Ｓ３６）。ライン終端に達していない場合（Ｓ３６のＮ）、最終ビット値とは逆の値をＦとする（Ｓ３８）。その後、ステップＳ１２に戻り、データ取得部１０２は、新たな３２ビットのデータをロードする。このとき、新たな３２ビットのデータの最初の部分のランと前の３２ビットのデータの最後の部分のランとが連続しているか否かを判断する必要がある。そこで、データ取得部１０２は、先頭ビットが「Ｆ」と一致するか否かを判断する（Ｓ１４）。先頭ビットがＦと一致する場合（Ｓ１４のＹ）、前のビット列の最後の部分と今回のビット列の最初の部分のビット値が連続していないので、ステップＳ３４で補正した暫定Ｒをランレングスとして決定する（Ｓ１６）。一方、ステップＳ１４において、先頭ビットがＦと一致しない場合、前のビット列の最後の部分と今回のビット列の最初の部分のビット値が連続しているので、ランレングス取得部１０６は、今回のビット列のラン値と前回のラン値とを足して新たなラン値を算出する（Ｓ２２）。
【００２３】
一方、ステップＳ３６において、ライン終端に達していた場合（Ｓ３６のＹ）、ライン最後のＲをランレングスとして決定する（Ｓ４０）。ここで、Ｒがゼロの場合は省略することができる。以上で、１ラインの処理を終了する。
【００２４】
次に、具体的な数値を用いて以上の処理を説明する。図４は、３２ビットのビット列とその次のビット列の先頭部分を示す図である。以下、図３をも参照して説明する。
まず、初期化処理部１０４は、Ｆ＝１、Ｒ＝０、Ｘ＝０としておく。図４（ａ）に示すように、先頭ビットは「０」なので、ステップＳ１４でＮとなり、ランレングス取得部１０６は、Ｎ（ｘ）＝３を取得する（Ｓ２０）。つづいて、ランレングス取得部１０６は、新たなラン値Ｒ＝０＋（３＋１）＝４を取得する（Ｓ２２）。次に、ランレングス取得部１０６は、図４（ｂ）に示すように、Ｘ＝４とする（Ｓ２４）。ここで、Ｘは３２未満なので、Ｓ２６でＮとなる。図４（ｃ）に示すように、初期化処理部１０４は、ＡをＮ（ｘ）＋１だけシフトし（Ｓ３０）、ランレングスとして「４」が決定される（Ｓ１６）。つづいて、ラン値Ｒをリセットする（Ｓ１８）。その後、ランレングス取得部１０６は、新しく定められたＡにより、再びランＮ（ｘ）＝２を取得する（Ｓ２０）。次に、ランレングス取得部１０６は、新たなラン値３を取得する（Ｓ２２）。以下、同様の処理を行うと、図４に示したビット列のランレングスは、「４３６３３２５２４」を得る。ここで、このビット列の最後のランレングス「４」は暫定のランレングスである。
【００２５】
図４（ｄ）に示すように、Ｘ＝２８のとき、ステップＳ２４で新たなＸ＝２８＋７＝３５≧３２となる。そこで、ステップＳ２６でＹとなり、ステップＳ３４で暫定Ｒとして、Ｒ＝７−（３５−３２）＝４が算出される。その後、ステップＳ３８において、Ｆ＝１がセットされる。ステップＳ１２において、新たな３２ビットのデータがロードされ、ステップＳ１４で先頭ビットがＦと一致するか否かが判断される。ここで、先頭ビットは「０」でＦと一致しないので、ステップＳ２０に進み、Ｎ（ｘ）＝２が取得される。つづいて、ステップＳ２２において、暫定Ｒ＝４に上記返数Ｎ（ｘ）＝２と１を加えた値Ｒ＝７が新たなＲとして取得される。以下、同様の処理を繰り返す。
【００２６】
以上のようにして、本実施の形態におけるランレングス符号化装置１００によれば、所定単位時間毎にＮＯＲＭにより返数Ｎ（ｘ）が得られ、この返数に基づいて画像データのランレングスが検出されるので、ランレングス符号化を迅速に行うことができる。
【００２７】
（第二の実施の形態）
本実施の形態においても、ランレングス符号化装置１００は、第一の実施の形態と同様の構成要素を有する。
本実施の形態において、ランレングス取得部１０６は、検索すべきビットを指定して、そのランを求める命令ＬＭＢＤ（Ｌｅｆｔ  Ｍｏｓｔ  Ｂｉｔ  Ｄｅｔｅｃｔｉｏｎ）を用いてランレングスを取得する。図５は、ビット列のパターンとそのときにＬＭＢＤにより得られるＬＭＢＤの演算結果を示す図である。たとえば、引数ビット配列が「０１・・」のとき、ＬＭＢＤ（ｘ，Ｆ（Ｆ＝１））＝１となる。また、たとえば、引数ビット配列が「１０・・」のとき、ＬＭＢＤ（ｘ，Ｆ（Ｆ＝０））＝１となる。
【００２８】
次に、本実施の形態におけるランレングス符号化装置１００の処理手順を図６を参照して説明する。ここでは、ランレングス取得部１０６が３２ビット毎のビット列を対象にしてランレングスを取得する場合を例として説明する。
【００２９】
まず、初期化処理部１０４が初期化を行う（Ｓ５０）。ここでは、フラグＦを初期化して、たとえば「１（黒）」とするとともに、ラン値Ｒを初期化してゼロとする。つづいて、データ取得部１０２が処理対象の３２ビットのデータをロードして「Ａ」とする（Ｓ５２）。また、このとき、先頭ビットの位置「Ｘ」をゼロとしておく。
【００３０】
その後、ランレングス取得部１０６は、ＬＭＢＤ（Ａ，Ｆ）を取得し、ｒに格納する（Ｓ５４）。つづいて、ランレングス取得部１０６は、もとのＲに「ＬＭＢＤ（Ａ，Ｆ）」を加えて新たなＲとする（Ｓ５６）。
【００３１】
その後、ランレングス取得部１０６は、もとの先頭ビットの位置ＸにステップＳ５６で算出したｒを加えて新たなＸとする（Ｓ５８）。つづいて、ランレングス取得部１０６は、Ｘが３２以上であるか否かを判断する（Ｓ６０）。Ｘが３２未満の場合（Ｓ２６のＮ）、このときのＲをランレングスとして決定する（Ｓ６２）。
【００３２】
次いで、初期化処理部１０４は、Ａをｒだけシフトし（Ｓ６４）、フラグＦを反転させるとともにラン値Ｒをリセットしてゼロとする（Ｓ６６）。その後、Ｓ５４に戻り、同様の処理を繰り返す。
【００３３】
一方、Ｓ６０でＸが３２以上である場合（Ｓ６０のＹ）、暫定Ｒを補正する（Ｓ６８）。ステップＳ２２で求めたＲから（Ｘ−３２）を減じ、新たなＲとする。つづいて、ライン終端に達しているか否かを判断する（Ｓ７０）。ライン終端に達していない場合（Ｓ７０のＮ）、ステップＳ５２に戻り、同様の処理を行う。
【００３４】
一方、ステップＳ７０において、ライン終端に達していた場合（Ｓ７０のＹ）、ライン最後のＲをランレングスとして決定する（Ｓ７２）。ここで、Ｒがゼロの場合は省略することができる。以上で、１ラインの処理を終了する。
【００３５】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【産業上の利用可能性】
【００３６】
本発明にかかる符号化装置は、所定単位時間毎にランレングスを取得し、迅速にランレングス符号化を行うことができるという効果を有し、符号化装置として有用である。
【図面の簡単な説明】
【００３７】
【図１】本発明の実施の形態における符号化装置の構成を示すブロック図である。
【図２】ビット列のパターンとそのときにＮＯＲＭにより得られる返数Ｎ（ｘ）を示す図である。
【図３】本発明の実施の形態におけるランレングス符号化装置の処理手順を示すフローチャートである。
【図４】３２ビットのビット列とその次のビット列の先頭部分を示す図である。
【図５】ビット列のパターンとそのときにＬＭＢＤにより得られるＬＭＢＤの演算結果を示す図である。
【図６】本発明の実施の形態におけるランレングス符号化装置の処理手順を示すフローチャートである。
【符号の説明】
【００３８】
１００  ランレングス符号化装置
１０２  データ取得部
１０４  初期化処理部
１０６  ランレングス取得部
１０８  ランレングスデータ記憶部
１１０  符号化処理部
【図１】
2005252408.tif 000003
【図２】
2005252408.tif 000004
【図３】
2005252408.tif 000005
【図４】
2005252408.tif 000006
【図５】
2005252408.tif 000007
【図６】
2005252408.tif 000008