データ圧縮方法およびプログラム、画像形成装置
【課題】入力データに対して、出現頻度が高い順に短い符号を与えて符号化するデータ圧縮方法において、略最適な符号化を維持しつつ、テーブルのサイズを縮小することができるデータ圧縮方法を提供することにある。
【解決手段】入力データに対して出現頻度が高い順に短い符号を与えて符号化するデータ圧縮方法である。出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成し、入力データについてテーブルを参照して一致するものを検索する。検索ステップの結果、入力データに一致するものがある場合、テーブルに従ってその入力データを変換して出力データとし、入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする。
【解決手段】入力データに対して出現頻度が高い順に短い符号を与えて符号化するデータ圧縮方法である。出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成し、入力データについてテーブルを参照して一致するものを検索する。検索ステップの結果、入力データに一致するものがある場合、テーブルに従ってその入力データを変換して出力データとし、入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力データを符号化してデータ量を少なくするデータ圧縮方法に関する。
【背景技術】
【０００２】
近年、ディジタル信号を圧縮する技術の進歩は著しいものがある。ディジタル化された静止画像や動画信号に関する圧縮技術としては、ＪＰＥＧやＭＰＥＧなどにより提案された圧縮方式が世界的な標準として定着している。これらの圧縮方式は、離散コサイン変換（ＤＣＴ）を用いて画像信号を直交変換した後、視覚的に目立たない部分の信号成分を取り除くことで情報量を減らし、さらに情報量を圧縮するためにハフマン符号化などを行っている。
【０００３】
ハフマン符号は、符号の発生頻度に応じて可変長の符号を割当てるもので、発生頻度の高い符号ほどビット長の短い符号を割当てて符号化することにより、情報量を減らすものである。
【０００４】
ハフマン符号で符号化されたデータを通常の固定長符号に復号化する場合、一般にルックアップテーブルを用いた符号変換方法がとられる。この場合、可変長符号中の最大符号長に満たない符号は全て最大符号長と同じ長さの固定長符号として扱われる。
【０００５】
例えば、ハフマン符号を６ビットに固定長符号化するには、６ビット未満のハフマン符号（ハフマン符号長２〜５）の下位に不足分のビットを補えばよい。しかし、そのため復号化用のルックアップテーブルには、エントリ数が２の６乗必要となり、著しく冗長になる。つまり、ルックアップテーブルの構成が冗長になり、テーブルを格納するために大きなメモリスペースが必要になるという問題があった。
【０００６】
このような問題に対して、入力符号を他の符号系の出力符号に変換するために用いるルックアップテーブルのサイズを削減できる符号変換方法が提案されている（例えば、特許文献１参照。）。
【０００７】
この特許文献１に記載の方法では、有効符号値が疎に分布する第１の符号系の入力符号を他の第２の符号系の符号に変換するためのルックアップテーブルを２つ用いている。空間圧縮用の第１ルックアップテーブルにおいて、入力符号の上位ビットの値の列が、より密な識別符号の列に置換される。第２のルックアップテーブルにおいて、第１のルックアップテーブルから得られる識別符号と入力符号の下位ビットの値との組み合わせの値が、第２の符号系の対応する符号に変換される。このようにして、ルックアップテーブルの全体のサイズの圧縮を図ることが記載されている。
【０００８】
しかし、特許文献１に記載の方法は、可変長符号を復号化する場合において用いられる復号化テーブルに関するものであり、符号化についてはハフマン符号化が前提となっている。つまり、復号化処理ではテーブルのサイズが削減されているものの、符号化処理では従来と同じである。また、圧縮効率を上げるために第１のルックアップテーブルを用いて２段階で変換を行っているので、第１のルックアップテーブルの分だけテーブルサイズは大きくなる。
【０００９】
このように、符号化の際に用いるテーブルを格納するのに必要な記憶容量を削減することは追求すべき課題である。
【特許文献１】特開平０５−１８３４４３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は従来技術の課題に鑑みてなされたものであり、本発明の目的は、入力データに対して、出現頻度が高い順に短い符号を与えて符号化するデータ圧縮方法において、略最適な符号化を維持しつつ、テーブルのサイズを縮小することができるデータ圧縮方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の上記目的は、下記の手段によって達成される。
【００１２】
（１）入力データに対して、出現頻度が高い順に符号を与えて符号化するデータ圧縮方法であって、１）出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成するステップと、２）入力データについて前記テーブルを参照して一致するものを検索するステップと、３）前記ステップ２）の結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとするステップと、４）前記ステップ２）の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとするステップとを有することを特徴とするデータ圧縮方法。
【００１３】
（２）前記ステップ１）において、入力データの出現頻度を高い順に合算して全体に占める出現率を求めるステップを有し、全体に占める出現率が所定値以上である場合、その出現頻度をステップ１）における所定値以上であると判断してテーブルを作成する上記（１）に記載のデータ圧縮方法。
【００１４】
（３）前記ステップ１）の前に、画像データについて離散コサイン変換をするステップを更に有する上記（１）または（２）に記載のデータ圧縮方法。
【００１５】
（４）前記ステップ１）の前に、一次圧縮として固定長におけるデータ圧縮を行うステップを更に有する上記（１）または（２）に記載のデータ圧縮方法。
【００１６】
（５）上記（１）から（４）に記載のデータ圧縮方法によって符号化された出力データを復号化する復号方法であって、１）出力データについて前記テーブルを参照して一致するものを検索するステップと、２）前記ステップ１）の結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換するステップと、３）前記ステップ１）の結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除するステップとを有することを特徴とする復号方法。
【００１７】
（６）入力データに対して、出現頻度が高い順に符号を与えて符合化するためのデータ圧縮プログラムであって、１）出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成する手順と、２）入力データについて前記テーブルを参照して一致するものを検索する手順と、３）前記手順２）の結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとする手順と、４）前記手順２）の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする手順とをデータ処理装置に実行させることを特徴とするデータ圧縮プログラム。
【００１８】
（７）上記（６）に記載のデータ圧縮プログラムによって符号化された出力データを復号化するための復号プログラムであって、１）出力データについて前記テーブルを参照して一致するものを検索する手順と、２）前記手順１）の結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換する手順と、３）前記手順１）の結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除する手順とをデータ処理装置に実行させることを特徴とする復号プログラム。
【００１９】
（８）入力データに対して、出現頻度が高い順に符号を与えて符号化する画像処理装置であって、出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成する手段と、入力データについて前記テーブルを参照して一致するものを検索する手段と、検索した結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとする手段と、検索の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする手段とを有することを特徴とする画像処理装置。
【００２０】
（９）上記（８）に記載の画像処理装置によって符号化された出力データを復号化する画像処理装置であって、出力データについて前記テーブルを参照して一致するものを検索する手段と、検索した結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換する手段と、検索した結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除する手段とを有することを特徴とする画像処理装置。
【発明の効果】
【００２１】
本発明では、入力データに対して出現頻度が高い順に短い符号を与えるため略最適な符号化が行え、出現頻度が所定の値以上である入力データについてテーブルを作成するためテーブルのサイズを縮小し、データ蓄積に必要な記憶容量を削減することができる。また、本発明は集積回路を用いてハードウェアにより実現された場合、チップ面積を抑え、コストの低減や資源の節約を図ることができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態を、図面を参照して詳細に説明する。
【００２３】
図１は、本発明のデータ圧縮装置を装備する印刷装置の概略構成を示す構成図である。
【００２４】
印刷装置１は、ＣＰＵ１１と、ＲＡＭ１２と、ＲＯＭ１３と、入力インタフェース１４と、印刷部１６と、制御部１５とを備え、これらは信号をやり取りするためのバス２７を介して相互に接続されている。
【００２５】
印刷装置１は、文書の印刷の指示を行う印刷指示装置としての外部入力装置２に入力インタフェース１４を介して接続されており、外部入力装置２からの印刷指示に基づいて印刷を行う。なお、印刷装置１と外部入力装置２とは、ネットワークを介することなく直接機器間で接続（ローカル接続）されていてもよい。
【００２６】
ＣＰＵ１１は、プログラムにしたがって、各部の制御や各種の演算処理を行う。
【００２７】
ＲＯＭ１３には、外部入力装置２から受信したＰＤＬファイルを翻訳しビットマップ形式の画像データであるビットマップデータに展開するためのラスタライズ処理のプログラム、ＰＤＬファイルの処理方法を解析するための画像データ処理のプログラム、およびビットマップデータを含む印刷データに基づいて行われる印刷処理のプログラムなど、各種プログラムやデータが格納されている。
【００２８】
ＲＡＭ１２には、作業領域として一時的にプログラムやビットマップデータなどが記憶される。
【００２９】
入力インタフェース１４は、ネットワークを介して他の機器と通信するためのインタフェースであり、イーサネット（登録商標）、トークンリング、ＦＤＤＩ等の規格が用いられる。
【００３０】
制御部１５は、画像処理部１５２と符号化・復号化部１５１とを有している。画像処理部１５２は、外部入力装置２から受信したＰＤＬファイルを翻訳しビットマップ形式の画像データであるビットマップデータに展開したり、印刷装置１の色空間に対応させるためＣＭＹＫに色変換したり、補正処理を施したりする。符号化・復号化部１５１は、印刷データを符号化しデータ容量を縮小して一時的にＲＡＭ１２に格納したり、ＲＡＭ１２から符号化された印刷データを読み出し復号化し印刷部１６に転送したりする。
【００３１】
印刷部１６は、電子写真式プロセス等の周知の作像プロセスを用いて、ＲＡＭ１２から読み出したビットマップデータが示す画像を用紙等の記録媒体に印刷する。つまり、印刷部１６は、印刷時に印刷データをＲＡＭ１２から読み出すと、感光ドラムの表面を帯電ローラにより均一に帯電してから、印刷データに基づいてプリントヘッドにより露光することによって、感光ドラムの表面上に静電潜像部を形成する。その後、トナーカートリッジから供給されたトナーを現像ローラにより静電潜像部に付着させる。次いで、印刷部１６は、給紙トレイから搬送されてきた用紙上に、感光ドラムに付着されたトナーを転写ローラにより転写し、定着装置により用紙上のトナーを定着する。こうして印刷された用紙は、排紙トレイに排出される。
【００３２】
次に、入力データを取得した場合における印刷装置１の動作について説明する。
【００３３】
図２は、図１に示す制御部１５における処理の手順を示すフローチャートである。図２のフローチャートにより示されるアルゴリズムは、印刷装置１のＲＯＭ１３にプログラムとして記憶されており、印刷装置１のＣＰＵ１１によって実行される。
【００３４】
外部入力装置２から画像データ（ＰＤＬファイル）が取得されることにより、処理は開始する。ＰＤＬファイルは、ページプリンタを制御するコマンドがページ記述言語で記述されているファイルである。
【００３５】
取得したＰＤＬファイルがラスタライズされる（Ｓ１０１）。画像処理部１５２は、ＰＤＬファイルを翻訳し、ビットマップ形式の印刷データ（ラスタデータ）に展開する。
【００３６】
ラスタデータがＣＭＹＫに色変換される（Ｓ１０２）。画像処理部１５２は、ラスタデータにおける色空間を印刷装置１の色空間に対応させるためＣＭＹＫに色変換する。
【００３７】
ラスタデータがエッジ処理され（Ｓ１０３）、スクリーン処理される（Ｓ１０４）。例えば、文字については、輪郭部や文字内部などの領域に分類される。輪郭部は高解像度のビットマップ処理を施され、エッジ部分が強調され、文字内部はスクリーン処理によってムラをなくすように補正される。
【００３８】
印刷データが符号化処理される（Ｓ１０５）。符号化・復号化部１５１は、印刷データを符号化して圧縮し、データ量を縮小する。なお、符号化の処理については後で詳しく説明する。圧縮された印刷データはＲＡＭ１２に一時的に格納され、処理は終了する。
【００３９】
図３、４、５を参照して符号化の処理について説明する。
【００４０】
図３は、図２に示す符号化の処理の手順を示すフローチャートである。図３のフローチャートにより示されるアルゴリズムは、印刷装置１のＲＯＭ１３にプログラムとして記憶されており、印刷装置１のＣＰＵ１１によって実行される。
【００４１】
図４は変換テーブルの一例を示す図である。変換テーブルは、入力データに対して、出現確率が高い順に短い符号を割り振って作成されるものであり、符号化・復号化部１５１において、予め全ての入力データを取得した後に作成される。あるいは、変換テーブルは、予め一般的な入力データを使用して得られた統計情報から作成される。例えば、入力データ「００００００００」が最も多く出現した場合、その入力データに対して最も短い符号「０」が割り振られる。また、変換テーブルは、全ての入力データに対して符号を割り振ることはしない。例えば、３３番目と決めた場合、出現頻度が１番目から３３番目までの入力データについて変換テーブルが作成される。
【００４２】
図５は入力データが変換テーブルにない場合を説明するための図である。
【００４３】
入力データについて変換テーブルに一致するものがあるか否が判断される。符号化・復号化部１５１は、変換テーブルを参照して入力データに一致する項目を検索する（Ｓ２０１）。
【００４４】
入力データについて変換テーブルに一致するものがある場合（Ｓ２０１：Ｙｅｓ）、入力データは変換テーブルに従って変換される（Ｓ２０２）。入力データは対応する符号に変換されて出力データとなるため、基本的には出力データは入力データに比較してデータ量は小さいものとなる。
【００４５】
一方、入力データについて変換テーブルに一致するものがない場合（Ｓ２０１：Ｎｏ）、入力データにはヘッダが付加される（Ｓ２０３）。入力データ「０１１１０１０」の出現頻度が低くて、変換テーブルにない場合、図５に示すように、冗長符号「１１１０」をヘッダとして付加して、出力データ「１１１００１１１０１０」とする。このヘッダは出力データが変換テーブルにないことを示しており、復号化する際に用いられる。
【００４６】
次に、印刷時における印刷装置１の動作について説明する。
【００４７】
図６は、図１に示す制御部１５における処理の手順を示すフローチャートである。
【００４８】
図６のフローチャートにより示されるアルゴリズムは、印刷装置１のＲＯＭ１３にプログラムとして記憶されており、印刷装置１のＣＰＵ１１によって実行される。
【００４９】
圧縮された印刷データが読み出される（Ｓ３０１）。符号化・復号化部１５１は、圧縮された印刷データをＲＡＭ１２から読み出す。
【００５０】
読み出した印刷データについて復号化処理が実行される（Ｓ３０２）。符号化・復号化部１５１は、圧縮された印刷データを復号化し、印刷部１６に転送する。なお、符号化の処理については後で詳しく説明する。
【００５１】
印刷データに基づいて印刷が実行される（Ｓ３０３）。印刷部１６は、取得した印刷データが示す画像を用紙等の記録媒体に印刷する。
【００５２】
図７は、図６に示す復号化の処理の手順を示すフローチャートである。図７のフローチャートにより示されるアルゴリズムは、印刷装置１のＲＯＭ１３にプログラムとして記憶されており、印刷装置１のＣＰＵ１１によって実行される。
【００５３】
圧縮された印刷データについて変換テーブルに一致するものがあるか否が判断される（Ｓ４０１）。符号化・復号化部１５１は、圧縮された印刷データが変換テーブルに出力データとして登録されている否かを判断する。つまり、変換テーブルを参照して圧縮された印刷データを検索する。
【００５４】
圧縮された印刷データについて変換テーブルに一致するものがある場合（Ｓ４０１：Ｙｅｓ）、圧縮された印刷データは変換テーブルに従って変換される（Ｓ３０２）。圧縮された印刷データは、対応する入力データに変換されることで、符号化される前の印刷データに復元される。
【００５５】
一方、圧縮された印刷データについて変換テーブルに一致するものがない場合（Ｓ４０１：Ｎｏ）、圧縮された印刷データからヘッダが削除される（Ｓ３０３）。圧縮された印刷データは、ヘッダを削除したデータを用いることで、符号化される前の印刷データに復元される。
【００５６】
本実施形態によれば、出現確率が高い順に短い符号を与えるため、画像データは略最適な状態で符号化される。
【００５７】
また、変換テーブルに全ての入力データを登録しないため、必要なテーブルのサイズを縮小することができる。変換テーブルに登録しない入力データに関してはヘッダを付加して出力データとすることで復元が可能となる。
【００５８】
出現確率が高い順に短い符号を与えて符号化を実行する場合、可逆変換するために、出現頻度が低いものも含め、全ての入力データについて変換テーブルに登録しておく必要がある。本発明では、全ての入力データを登録することはしないため、全ての入力データを登録する変換テーブルを用いる場合に比べてテーブルのサイズを縮小することができる。
【００５９】
さらに、固定値（３３）を調整することで変換テーブルのサイズを調整することができる。
【００６０】
図８は、変形例における制御部１５での処理の手順を示すフローチャートである。本発明の圧縮方式は複数の圧縮方式と組み合わせて適用することもできる。この変形例では、制御部１５は、複数の圧縮方式（圧縮方式Ａ、Ｂおよび本発明の圧縮方式）と圧縮方式選択部とを有している（図示せず）。
【００６１】
図８を参照して復号化の処理の手順を説明する。
【００６２】
圧縮方式Ａによって入力データを符号化し、符号化した入力データを圧縮方式選択部に転送する。圧縮方式Ｂによって入力データを符号化し、圧縮方式選択部に転送する。本発明の圧縮方式によって入力データを符号化し、圧縮方式選択部に転送する。
【００６３】
圧縮方式選択部は、各圧縮方式で符号化された情報の中からデータ量が最小のものを選択する。このようにして選択された情報が出力データとなる。
【００６４】
この変形例では、複数の圧縮方式によって入力データを符号化し、その中からデータ量が最小のものを選択し、出力データとする。このように本発明の圧縮方式は複数の圧縮方式と組み合わせて適用することができる。
【００６５】
図９は、変形例における制御部１５での処理の手順を示すフローチャートである。上述した変形例では、複数の圧縮方式で圧縮したものの中からデータ量が最小のものを選択したが、一旦別の圧縮方式で圧縮したものに対して本発明の圧縮方式を適用して圧縮することもできる。この変形例では、圧縮方式Ａとして量子化を採用し、量子化の前に離散コサイン変換を行う。
【００６６】
図９を参照して復号化の処理の手順を説明する。
【００６７】
画像は固定サイズ（８×８画素）の要素ブロックに分割され、そのブロック単位で空間領域から周波数領域へ離散コサイン変換（ＤＣＴ）され、量子化テーブルを用いて量子化される（Ｓ６０１）。
【００６８】
離散コサイン変換後のデータの周波数成分は低周波数領域に集中するため、本発明の圧縮方式における圧縮率を高くすることができる。また、量子化することによってデータを省略しデータ量を削減することができる。
【００６９】
本発明の圧縮方式によって符号化される（Ｓ６０２）。量子化後のデータについて、上述した変換テーブルが作成され、符号化が行われる。
【００７０】
図１０は、変換テーブルを作成する処理の手順を示すフローチャートである。図４に示す実施形態では、出現頻度が１番目から３３番目までの入力データについて変換テーブルが作成されている。つまり、登録する入力データについては固定値（３３）を採用しているが、本発明はこれに限定されるものではない。変換テーブルに登録する入力データについては出現率に応じて決定することができる。
【００７１】
変換テーブルを作成する処理について説明する。なお、各入力データの出現頻度は予め算出されており、また所定値ｎもユーザにより予め設定されている。
【００７２】
入力データの出現頻度が取得される（Ｓ７０１）。ここで取得される入力データは出現頻度の高い順番ａに取得される。つまり、最初に取得される入力データは最も出現頻度が高く（ａ＝１）、次に取得される入力データは２番目に出現頻度が高く（ａ＝２）、以下、ｍ番目に取得される入力データはｍ番目に出現頻度が高いもの（ａ＝ｍ）となる。
【００７３】
ａ番目に出現頻度が高い入力データの出現頻度が加算され、出現頻度の合算値（ｓｕｍ）が算出される（Ｓ７０２）。つまり、出現頻度の合算値（ｓｕｍ）は、最初は最も出現頻度が高い入力データ（ａ＝１）についての出現頻度（ｓｕｍ＝ｂ１）であり、次は２番目に出現頻度が高い入力データ（ａ＝２）の出現頻度を加算した値であり（ｓｕｍ＋ｂ２）、以下、ｍ番目に出現頻度が高い入力データ（ａ＝ｍ）の出現頻度が加算された値である（ｓｕｍ＋ｂｍ）。
【００７４】
出現頻度の合算値を全ての入力データの出現頻度で除算し、全ての入力データの出現頻度（ｔｏｔａｌ）に占める出現頻度の合算値（ｓｕｍ）の割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)が算出される。算出された割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)は、ユーザにより設定される所定値ｎと比較される（Ｓ７０３）。算出された割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)は、入力データの出現頻度を高い順に合算して全体に占める出現率を表している。
【００７５】
算出された割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)が所定値ｎ以下である場合（Ｓ７０３：Ｎｏ）、処理はステップＳ７０１に戻る。次に出現頻度が高い入力データ（ａ＋１）についてステップＳ７０１からＳ７０２が実行される。つまり、出現頻度の順番ａに１を加えた入力データについて、ステップＳ７０１からＳ７０２が繰り返される。
【００７６】
算出された割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)が所定値ｎ以上である場合（Ｓ７０３：Ｎｏ）、変換テーブルが作成される（Ｓ７０４）。ここで変換テーブルに登録される入力データは、出現頻度の順番が１からａ番目までのものである。
【００７７】
このように入力データの出現率に応じて登録する入力データを決定することで、変換テーブルのサイズを調節することができる。つまり、ユーザが所定値ｎとして小さい値を選択すれば変換テーブルのサイズは小さくなり、大きな値を選択すれば変換テーブルのサイズは大きくなる。ただし、テーブルのサイズが大きい場合であっても、所定値ｎを１００に設定しない限り、全ての入力データを登録する変換テーブルを用いる場合のテーブルサイズより小さくなる。
【００７８】
本発明は、上記した実施形態のみに限定されるものではなく、特許請求の範囲内において、種々改変することができる。
【００７９】
上記実施形態では、本発明のデータ圧縮装置は印刷装置に装備されているが、本発明はこれに限定されるものではない。本発明は、例えばＭＦＰ（Ｍｕｌｔｉ−Ｆｕｎｃｔｉｏｎ Ｐｅｒｉｐｈｅｒａｌ）、複写機等の画像形成装置にも適用可能である。
【００８０】
本実施形態のデータ圧縮処理および復号処理における各種処理を行う手段および方法は、専用のハードウェア回路、またはプログラムされたコンピュータのいずれによっても実現することが可能である。上記プログラムは、たとえばフレキシブルディスクやＣＤ−ＲＯＭなどのコンピュータ読み取り可能な記録媒体によって提供されてもよいし、インターネット等のネットワークを介してオンラインで提供されてもよい。この場合、コンピュータ読み取り可能な記録媒体に記録されたプログラムは、通常、ハードディスク等の記憶部に転送されて記憶される。また、上記プログラムは、単独のアプリケーションソフトとして提供されてもよいし、装置の一機能としてその装置のソフトウェアに組み込まれてもよい。
【図面の簡単な説明】
【００８１】
【図１】本発明のデータ圧縮装置を装備する印刷装置の概略構成を示す構成図である。
【図２】制御部における処理の手順を示すフローチャートである。
【図３】制御部における処理の手順を示すフローチャートである。
【図４】符号化の処理の手順を示すフローチャートである。
【図５】復号化の処理の手順を示すフローチャートである。
【図６】変換テーブルの一例を示す図である。
【図７】入力データが変換テーブルにない場合を説明するための図である。
【図８】変形例における制御部での処理の手順を示すフローチャートである。
【図９】変形例における制御部での処理の手順を示すフローチャートである。
【図１０】変換テーブルを作成する処理の手順を示すフローチャートである。
【符号の説明】
【００８２】
１ 印刷装置、
２ 外部入力装置、
１１ ＣＰＵ
１２ ＲＡＭ、
１３ ＲＯＭ
１４ 入力インタフェース、
１５ 制御部、
１６ 印刷部
１５１ 符号化・復号化部、
１５２ 画像処理部。
【技術分野】
【０００１】
本発明は、入力データを符号化してデータ量を少なくするデータ圧縮方法に関する。
【背景技術】
【０００２】
近年、ディジタル信号を圧縮する技術の進歩は著しいものがある。ディジタル化された静止画像や動画信号に関する圧縮技術としては、ＪＰＥＧやＭＰＥＧなどにより提案された圧縮方式が世界的な標準として定着している。これらの圧縮方式は、離散コサイン変換（ＤＣＴ）を用いて画像信号を直交変換した後、視覚的に目立たない部分の信号成分を取り除くことで情報量を減らし、さらに情報量を圧縮するためにハフマン符号化などを行っている。
【０００３】
ハフマン符号は、符号の発生頻度に応じて可変長の符号を割当てるもので、発生頻度の高い符号ほどビット長の短い符号を割当てて符号化することにより、情報量を減らすものである。
【０００４】
ハフマン符号で符号化されたデータを通常の固定長符号に復号化する場合、一般にルックアップテーブルを用いた符号変換方法がとられる。この場合、可変長符号中の最大符号長に満たない符号は全て最大符号長と同じ長さの固定長符号として扱われる。
【０００５】
例えば、ハフマン符号を６ビットに固定長符号化するには、６ビット未満のハフマン符号（ハフマン符号長２〜５）の下位に不足分のビットを補えばよい。しかし、そのため復号化用のルックアップテーブルには、エントリ数が２の６乗必要となり、著しく冗長になる。つまり、ルックアップテーブルの構成が冗長になり、テーブルを格納するために大きなメモリスペースが必要になるという問題があった。
【０００６】
このような問題に対して、入力符号を他の符号系の出力符号に変換するために用いるルックアップテーブルのサイズを削減できる符号変換方法が提案されている（例えば、特許文献１参照。）。
【０００７】
この特許文献１に記載の方法では、有効符号値が疎に分布する第１の符号系の入力符号を他の第２の符号系の符号に変換するためのルックアップテーブルを２つ用いている。空間圧縮用の第１ルックアップテーブルにおいて、入力符号の上位ビットの値の列が、より密な識別符号の列に置換される。第２のルックアップテーブルにおいて、第１のルックアップテーブルから得られる識別符号と入力符号の下位ビットの値との組み合わせの値が、第２の符号系の対応する符号に変換される。このようにして、ルックアップテーブルの全体のサイズの圧縮を図ることが記載されている。
【０００８】
しかし、特許文献１に記載の方法は、可変長符号を復号化する場合において用いられる復号化テーブルに関するものであり、符号化についてはハフマン符号化が前提となっている。つまり、復号化処理ではテーブルのサイズが削減されているものの、符号化処理では従来と同じである。また、圧縮効率を上げるために第１のルックアップテーブルを用いて２段階で変換を行っているので、第１のルックアップテーブルの分だけテーブルサイズは大きくなる。
【０００９】
このように、符号化の際に用いるテーブルを格納するのに必要な記憶容量を削減することは追求すべき課題である。
【特許文献１】特開平０５−１８３４４３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は従来技術の課題に鑑みてなされたものであり、本発明の目的は、入力データに対して、出現頻度が高い順に短い符号を与えて符号化するデータ圧縮方法において、略最適な符号化を維持しつつ、テーブルのサイズを縮小することができるデータ圧縮方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の上記目的は、下記の手段によって達成される。
【００１２】
（１）入力データに対して、出現頻度が高い順に符号を与えて符号化するデータ圧縮方法であって、１）出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成するステップと、２）入力データについて前記テーブルを参照して一致するものを検索するステップと、３）前記ステップ２）の結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとするステップと、４）前記ステップ２）の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとするステップとを有することを特徴とするデータ圧縮方法。
【００１３】
（２）前記ステップ１）において、入力データの出現頻度を高い順に合算して全体に占める出現率を求めるステップを有し、全体に占める出現率が所定値以上である場合、その出現頻度をステップ１）における所定値以上であると判断してテーブルを作成する上記（１）に記載のデータ圧縮方法。
【００１４】
（３）前記ステップ１）の前に、画像データについて離散コサイン変換をするステップを更に有する上記（１）または（２）に記載のデータ圧縮方法。
【００１５】
（４）前記ステップ１）の前に、一次圧縮として固定長におけるデータ圧縮を行うステップを更に有する上記（１）または（２）に記載のデータ圧縮方法。
【００１６】
（５）上記（１）から（４）に記載のデータ圧縮方法によって符号化された出力データを復号化する復号方法であって、１）出力データについて前記テーブルを参照して一致するものを検索するステップと、２）前記ステップ１）の結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換するステップと、３）前記ステップ１）の結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除するステップとを有することを特徴とする復号方法。
【００１７】
（６）入力データに対して、出現頻度が高い順に符号を与えて符合化するためのデータ圧縮プログラムであって、１）出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成する手順と、２）入力データについて前記テーブルを参照して一致するものを検索する手順と、３）前記手順２）の結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとする手順と、４）前記手順２）の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする手順とをデータ処理装置に実行させることを特徴とするデータ圧縮プログラム。
【００１８】
（７）上記（６）に記載のデータ圧縮プログラムによって符号化された出力データを復号化するための復号プログラムであって、１）出力データについて前記テーブルを参照して一致するものを検索する手順と、２）前記手順１）の結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換する手順と、３）前記手順１）の結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除する手順とをデータ処理装置に実行させることを特徴とする復号プログラム。
【００１９】
（８）入力データに対して、出現頻度が高い順に符号を与えて符号化する画像処理装置であって、出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成する手段と、入力データについて前記テーブルを参照して一致するものを検索する手段と、検索した結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとする手段と、検索の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする手段とを有することを特徴とする画像処理装置。
【００２０】
（９）上記（８）に記載の画像処理装置によって符号化された出力データを復号化する画像処理装置であって、出力データについて前記テーブルを参照して一致するものを検索する手段と、検索した結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換する手段と、検索した結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除する手段とを有することを特徴とする画像処理装置。
【発明の効果】
【００２１】
本発明では、入力データに対して出現頻度が高い順に短い符号を与えるため略最適な符号化が行え、出現頻度が所定の値以上である入力データについてテーブルを作成するためテーブルのサイズを縮小し、データ蓄積に必要な記憶容量を削減することができる。また、本発明は集積回路を用いてハードウェアにより実現された場合、チップ面積を抑え、コストの低減や資源の節約を図ることができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態を、図面を参照して詳細に説明する。
【００２３】
図１は、本発明のデータ圧縮装置を装備する印刷装置の概略構成を示す構成図である。
【００２４】
印刷装置１は、ＣＰＵ１１と、ＲＡＭ１２と、ＲＯＭ１３と、入力インタフェース１４と、印刷部１６と、制御部１５とを備え、これらは信号をやり取りするためのバス２７を介して相互に接続されている。
【００２５】
印刷装置１は、文書の印刷の指示を行う印刷指示装置としての外部入力装置２に入力インタフェース１４を介して接続されており、外部入力装置２からの印刷指示に基づいて印刷を行う。なお、印刷装置１と外部入力装置２とは、ネットワークを介することなく直接機器間で接続（ローカル接続）されていてもよい。
【００２６】
ＣＰＵ１１は、プログラムにしたがって、各部の制御や各種の演算処理を行う。
【００２７】
ＲＯＭ１３には、外部入力装置２から受信したＰＤＬファイルを翻訳しビットマップ形式の画像データであるビットマップデータに展開するためのラスタライズ処理のプログラム、ＰＤＬファイルの処理方法を解析するための画像データ処理のプログラム、およびビットマップデータを含む印刷データに基づいて行われる印刷処理のプログラムなど、各種プログラムやデータが格納されている。
【００２８】
ＲＡＭ１２には、作業領域として一時的にプログラムやビットマップデータなどが記憶される。
【００２９】
入力インタフェース１４は、ネットワークを介して他の機器と通信するためのインタフェースであり、イーサネット（登録商標）、トークンリング、ＦＤＤＩ等の規格が用いられる。
【００３０】
制御部１５は、画像処理部１５２と符号化・復号化部１５１とを有している。画像処理部１５２は、外部入力装置２から受信したＰＤＬファイルを翻訳しビットマップ形式の画像データであるビットマップデータに展開したり、印刷装置１の色空間に対応させるためＣＭＹＫに色変換したり、補正処理を施したりする。符号化・復号化部１５１は、印刷データを符号化しデータ容量を縮小して一時的にＲＡＭ１２に格納したり、ＲＡＭ１２から符号化された印刷データを読み出し復号化し印刷部１６に転送したりする。
【００３１】
印刷部１６は、電子写真式プロセス等の周知の作像プロセスを用いて、ＲＡＭ１２から読み出したビットマップデータが示す画像を用紙等の記録媒体に印刷する。つまり、印刷部１６は、印刷時に印刷データをＲＡＭ１２から読み出すと、感光ドラムの表面を帯電ローラにより均一に帯電してから、印刷データに基づいてプリントヘッドにより露光することによって、感光ドラムの表面上に静電潜像部を形成する。その後、トナーカートリッジから供給されたトナーを現像ローラにより静電潜像部に付着させる。次いで、印刷部１６は、給紙トレイから搬送されてきた用紙上に、感光ドラムに付着されたトナーを転写ローラにより転写し、定着装置により用紙上のトナーを定着する。こうして印刷された用紙は、排紙トレイに排出される。
【００３２】
次に、入力データを取得した場合における印刷装置１の動作について説明する。
【００３３】
図２は、図１に示す制御部１５における処理の手順を示すフローチャートである。図２のフローチャートにより示されるアルゴリズムは、印刷装置１のＲＯＭ１３にプログラムとして記憶されており、印刷装置１のＣＰＵ１１によって実行される。
【００３４】
外部入力装置２から画像データ（ＰＤＬファイル）が取得されることにより、処理は開始する。ＰＤＬファイルは、ページプリンタを制御するコマンドがページ記述言語で記述されているファイルである。
【００３５】
取得したＰＤＬファイルがラスタライズされる（Ｓ１０１）。画像処理部１５２は、ＰＤＬファイルを翻訳し、ビットマップ形式の印刷データ（ラスタデータ）に展開する。
【００３６】
ラスタデータがＣＭＹＫに色変換される（Ｓ１０２）。画像処理部１５２は、ラスタデータにおける色空間を印刷装置１の色空間に対応させるためＣＭＹＫに色変換する。
【００３７】
ラスタデータがエッジ処理され（Ｓ１０３）、スクリーン処理される（Ｓ１０４）。例えば、文字については、輪郭部や文字内部などの領域に分類される。輪郭部は高解像度のビットマップ処理を施され、エッジ部分が強調され、文字内部はスクリーン処理によってムラをなくすように補正される。
【００３８】
印刷データが符号化処理される（Ｓ１０５）。符号化・復号化部１５１は、印刷データを符号化して圧縮し、データ量を縮小する。なお、符号化の処理については後で詳しく説明する。圧縮された印刷データはＲＡＭ１２に一時的に格納され、処理は終了する。
【００３９】
図３、４、５を参照して符号化の処理について説明する。
【００４０】
図３は、図２に示す符号化の処理の手順を示すフローチャートである。図３のフローチャートにより示されるアルゴリズムは、印刷装置１のＲＯＭ１３にプログラムとして記憶されており、印刷装置１のＣＰＵ１１によって実行される。
【００４１】
図４は変換テーブルの一例を示す図である。変換テーブルは、入力データに対して、出現確率が高い順に短い符号を割り振って作成されるものであり、符号化・復号化部１５１において、予め全ての入力データを取得した後に作成される。あるいは、変換テーブルは、予め一般的な入力データを使用して得られた統計情報から作成される。例えば、入力データ「００００００００」が最も多く出現した場合、その入力データに対して最も短い符号「０」が割り振られる。また、変換テーブルは、全ての入力データに対して符号を割り振ることはしない。例えば、３３番目と決めた場合、出現頻度が１番目から３３番目までの入力データについて変換テーブルが作成される。
【００４２】
図５は入力データが変換テーブルにない場合を説明するための図である。
【００４３】
入力データについて変換テーブルに一致するものがあるか否が判断される。符号化・復号化部１５１は、変換テーブルを参照して入力データに一致する項目を検索する（Ｓ２０１）。
【００４４】
入力データについて変換テーブルに一致するものがある場合（Ｓ２０１：Ｙｅｓ）、入力データは変換テーブルに従って変換される（Ｓ２０２）。入力データは対応する符号に変換されて出力データとなるため、基本的には出力データは入力データに比較してデータ量は小さいものとなる。
【００４５】
一方、入力データについて変換テーブルに一致するものがない場合（Ｓ２０１：Ｎｏ）、入力データにはヘッダが付加される（Ｓ２０３）。入力データ「０１１１０１０」の出現頻度が低くて、変換テーブルにない場合、図５に示すように、冗長符号「１１１０」をヘッダとして付加して、出力データ「１１１００１１１０１０」とする。このヘッダは出力データが変換テーブルにないことを示しており、復号化する際に用いられる。
【００４６】
次に、印刷時における印刷装置１の動作について説明する。
【００４７】
図６は、図１に示す制御部１５における処理の手順を示すフローチャートである。
【００４８】
図６のフローチャートにより示されるアルゴリズムは、印刷装置１のＲＯＭ１３にプログラムとして記憶されており、印刷装置１のＣＰＵ１１によって実行される。
【００４９】
圧縮された印刷データが読み出される（Ｓ３０１）。符号化・復号化部１５１は、圧縮された印刷データをＲＡＭ１２から読み出す。
【００５０】
読み出した印刷データについて復号化処理が実行される（Ｓ３０２）。符号化・復号化部１５１は、圧縮された印刷データを復号化し、印刷部１６に転送する。なお、符号化の処理については後で詳しく説明する。
【００５１】
印刷データに基づいて印刷が実行される（Ｓ３０３）。印刷部１６は、取得した印刷データが示す画像を用紙等の記録媒体に印刷する。
【００５２】
図７は、図６に示す復号化の処理の手順を示すフローチャートである。図７のフローチャートにより示されるアルゴリズムは、印刷装置１のＲＯＭ１３にプログラムとして記憶されており、印刷装置１のＣＰＵ１１によって実行される。
【００５３】
圧縮された印刷データについて変換テーブルに一致するものがあるか否が判断される（Ｓ４０１）。符号化・復号化部１５１は、圧縮された印刷データが変換テーブルに出力データとして登録されている否かを判断する。つまり、変換テーブルを参照して圧縮された印刷データを検索する。
【００５４】
圧縮された印刷データについて変換テーブルに一致するものがある場合（Ｓ４０１：Ｙｅｓ）、圧縮された印刷データは変換テーブルに従って変換される（Ｓ３０２）。圧縮された印刷データは、対応する入力データに変換されることで、符号化される前の印刷データに復元される。
【００５５】
一方、圧縮された印刷データについて変換テーブルに一致するものがない場合（Ｓ４０１：Ｎｏ）、圧縮された印刷データからヘッダが削除される（Ｓ３０３）。圧縮された印刷データは、ヘッダを削除したデータを用いることで、符号化される前の印刷データに復元される。
【００５６】
本実施形態によれば、出現確率が高い順に短い符号を与えるため、画像データは略最適な状態で符号化される。
【００５７】
また、変換テーブルに全ての入力データを登録しないため、必要なテーブルのサイズを縮小することができる。変換テーブルに登録しない入力データに関してはヘッダを付加して出力データとすることで復元が可能となる。
【００５８】
出現確率が高い順に短い符号を与えて符号化を実行する場合、可逆変換するために、出現頻度が低いものも含め、全ての入力データについて変換テーブルに登録しておく必要がある。本発明では、全ての入力データを登録することはしないため、全ての入力データを登録する変換テーブルを用いる場合に比べてテーブルのサイズを縮小することができる。
【００５９】
さらに、固定値（３３）を調整することで変換テーブルのサイズを調整することができる。
【００６０】
図８は、変形例における制御部１５での処理の手順を示すフローチャートである。本発明の圧縮方式は複数の圧縮方式と組み合わせて適用することもできる。この変形例では、制御部１５は、複数の圧縮方式（圧縮方式Ａ、Ｂおよび本発明の圧縮方式）と圧縮方式選択部とを有している（図示せず）。
【００６１】
図８を参照して復号化の処理の手順を説明する。
【００６２】
圧縮方式Ａによって入力データを符号化し、符号化した入力データを圧縮方式選択部に転送する。圧縮方式Ｂによって入力データを符号化し、圧縮方式選択部に転送する。本発明の圧縮方式によって入力データを符号化し、圧縮方式選択部に転送する。
【００６３】
圧縮方式選択部は、各圧縮方式で符号化された情報の中からデータ量が最小のものを選択する。このようにして選択された情報が出力データとなる。
【００６４】
この変形例では、複数の圧縮方式によって入力データを符号化し、その中からデータ量が最小のものを選択し、出力データとする。このように本発明の圧縮方式は複数の圧縮方式と組み合わせて適用することができる。
【００６５】
図９は、変形例における制御部１５での処理の手順を示すフローチャートである。上述した変形例では、複数の圧縮方式で圧縮したものの中からデータ量が最小のものを選択したが、一旦別の圧縮方式で圧縮したものに対して本発明の圧縮方式を適用して圧縮することもできる。この変形例では、圧縮方式Ａとして量子化を採用し、量子化の前に離散コサイン変換を行う。
【００６６】
図９を参照して復号化の処理の手順を説明する。
【００６７】
画像は固定サイズ（８×８画素）の要素ブロックに分割され、そのブロック単位で空間領域から周波数領域へ離散コサイン変換（ＤＣＴ）され、量子化テーブルを用いて量子化される（Ｓ６０１）。
【００６８】
離散コサイン変換後のデータの周波数成分は低周波数領域に集中するため、本発明の圧縮方式における圧縮率を高くすることができる。また、量子化することによってデータを省略しデータ量を削減することができる。
【００６９】
本発明の圧縮方式によって符号化される（Ｓ６０２）。量子化後のデータについて、上述した変換テーブルが作成され、符号化が行われる。
【００７０】
図１０は、変換テーブルを作成する処理の手順を示すフローチャートである。図４に示す実施形態では、出現頻度が１番目から３３番目までの入力データについて変換テーブルが作成されている。つまり、登録する入力データについては固定値（３３）を採用しているが、本発明はこれに限定されるものではない。変換テーブルに登録する入力データについては出現率に応じて決定することができる。
【００７１】
変換テーブルを作成する処理について説明する。なお、各入力データの出現頻度は予め算出されており、また所定値ｎもユーザにより予め設定されている。
【００７２】
入力データの出現頻度が取得される（Ｓ７０１）。ここで取得される入力データは出現頻度の高い順番ａに取得される。つまり、最初に取得される入力データは最も出現頻度が高く（ａ＝１）、次に取得される入力データは２番目に出現頻度が高く（ａ＝２）、以下、ｍ番目に取得される入力データはｍ番目に出現頻度が高いもの（ａ＝ｍ）となる。
【００７３】
ａ番目に出現頻度が高い入力データの出現頻度が加算され、出現頻度の合算値（ｓｕｍ）が算出される（Ｓ７０２）。つまり、出現頻度の合算値（ｓｕｍ）は、最初は最も出現頻度が高い入力データ（ａ＝１）についての出現頻度（ｓｕｍ＝ｂ１）であり、次は２番目に出現頻度が高い入力データ（ａ＝２）の出現頻度を加算した値であり（ｓｕｍ＋ｂ２）、以下、ｍ番目に出現頻度が高い入力データ（ａ＝ｍ）の出現頻度が加算された値である（ｓｕｍ＋ｂｍ）。
【００７４】
出現頻度の合算値を全ての入力データの出現頻度で除算し、全ての入力データの出現頻度（ｔｏｔａｌ）に占める出現頻度の合算値（ｓｕｍ）の割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)が算出される。算出された割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)は、ユーザにより設定される所定値ｎと比較される（Ｓ７０３）。算出された割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)は、入力データの出現頻度を高い順に合算して全体に占める出現率を表している。
【００７５】
算出された割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)が所定値ｎ以下である場合（Ｓ７０３：Ｎｏ）、処理はステップＳ７０１に戻る。次に出現頻度が高い入力データ（ａ＋１）についてステップＳ７０１からＳ７０２が実行される。つまり、出現頻度の順番ａに１を加えた入力データについて、ステップＳ７０１からＳ７０２が繰り返される。
【００７６】
算出された割合（（ｓｕｍ／ｔｏｔａｌ）＊１００)が所定値ｎ以上である場合（Ｓ７０３：Ｎｏ）、変換テーブルが作成される（Ｓ７０４）。ここで変換テーブルに登録される入力データは、出現頻度の順番が１からａ番目までのものである。
【００７７】
このように入力データの出現率に応じて登録する入力データを決定することで、変換テーブルのサイズを調節することができる。つまり、ユーザが所定値ｎとして小さい値を選択すれば変換テーブルのサイズは小さくなり、大きな値を選択すれば変換テーブルのサイズは大きくなる。ただし、テーブルのサイズが大きい場合であっても、所定値ｎを１００に設定しない限り、全ての入力データを登録する変換テーブルを用いる場合のテーブルサイズより小さくなる。
【００７８】
本発明は、上記した実施形態のみに限定されるものではなく、特許請求の範囲内において、種々改変することができる。
【００７９】
上記実施形態では、本発明のデータ圧縮装置は印刷装置に装備されているが、本発明はこれに限定されるものではない。本発明は、例えばＭＦＰ（Ｍｕｌｔｉ−Ｆｕｎｃｔｉｏｎ Ｐｅｒｉｐｈｅｒａｌ）、複写機等の画像形成装置にも適用可能である。
【００８０】
本実施形態のデータ圧縮処理および復号処理における各種処理を行う手段および方法は、専用のハードウェア回路、またはプログラムされたコンピュータのいずれによっても実現することが可能である。上記プログラムは、たとえばフレキシブルディスクやＣＤ−ＲＯＭなどのコンピュータ読み取り可能な記録媒体によって提供されてもよいし、インターネット等のネットワークを介してオンラインで提供されてもよい。この場合、コンピュータ読み取り可能な記録媒体に記録されたプログラムは、通常、ハードディスク等の記憶部に転送されて記憶される。また、上記プログラムは、単独のアプリケーションソフトとして提供されてもよいし、装置の一機能としてその装置のソフトウェアに組み込まれてもよい。
【図面の簡単な説明】
【００８１】
【図１】本発明のデータ圧縮装置を装備する印刷装置の概略構成を示す構成図である。
【図２】制御部における処理の手順を示すフローチャートである。
【図３】制御部における処理の手順を示すフローチャートである。
【図４】符号化の処理の手順を示すフローチャートである。
【図５】復号化の処理の手順を示すフローチャートである。
【図６】変換テーブルの一例を示す図である。
【図７】入力データが変換テーブルにない場合を説明するための図である。
【図８】変形例における制御部での処理の手順を示すフローチャートである。
【図９】変形例における制御部での処理の手順を示すフローチャートである。
【図１０】変換テーブルを作成する処理の手順を示すフローチャートである。
【符号の説明】
【００８２】
１ 印刷装置、
２ 外部入力装置、
１１ ＣＰＵ
１２ ＲＡＭ、
１３ ＲＯＭ
１４ 入力インタフェース、
１５ 制御部、
１６ 印刷部
１５１ 符号化・復号化部、
１５２ 画像処理部。
【特許請求の範囲】
【請求項１】
入力データに対して、出現頻度が高い順に符号を与えて符号化するデータ圧縮方法であって、
１）出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成するステップと、
２）入力データについて前記テーブルを参照して一致するものを検索するステップと、
３）前記ステップ２）の結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとするステップと、
４）前記ステップ２）の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとするステップと
を有することを特徴とするデータ圧縮方法。
【請求項２】
前記ステップ１）において、入力データの出現頻度を高い順に合算して全体に占める出現率を求めるステップを有し、
全体に占める出現率が所定値以上である場合、その出現頻度をステップ１）における所定値以上であると判断してテーブルを作成する請求項１に記載のデータ圧縮方法。
【請求項３】
５）前記ステップ１）の前に、画像データについて離散コサイン変換をするステップを更に有する請求項１または２に記載のデータ圧縮方法。
【請求項４】
６）前記ステップ１）の前に、一次圧縮として固定長におけるデータ圧縮を行うステップを更に有する請求項１または２に記載のデータ圧縮方法。
【請求項５】
請求項１から４に記載のデータ圧縮方法によって符号化された出力データを復号化する復号方法であって、
１）出力データについて前記テーブルを参照して一致するものを検索するステップと、
２）前記ステップ１）の結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換するステップと、
３）前記ステップ１）の結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除するステップと
を有することを特徴とする復号方法。
【請求項６】
入力データに対して、出現頻度が高い順に符号を与えて符合化するためのデータ圧縮プログラムであって、
１）出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成する手順と、
２）入力データについて前記テーブルを参照して一致するものを検索する手順と、
３）前記手順２）の結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとする手順と、
４）前記手順２）の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする手順と
をデータ処理装置に実行させることを特徴とするデータ圧縮プログラム。
【請求項７】
請求項６に記載のデータ圧縮プログラムによって符号化された出力データを復号化するための復号プログラムであって、
１）出力データについて前記テーブルを参照して一致するものを検索する手順と、
２）前記手順１）の結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換する手順と、
３）前記手順１）の結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除する手順と
をデータ処理装置に実行させることを特徴とする復号プログラム。
【請求項８】
入力データに対して、出現頻度が高い順に符号を与えて符号化する画像処理装置であって、
出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成する手段と、
入力データについて前記テーブルを参照して一致するものを検索する手段と、
検索した結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとする手段と、
検索の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする手段と
を有することを特徴とする画像処理装置。
【請求項９】
請求項８に記載の画像処理装置によって符号化された出力データを復号化する画像処理装置であって、
出力データについて前記テーブルを参照して一致するものを検索する手段と、
検索した結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換する手段と、
検索した結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除する手段と
を有することを特徴とする画像処理装置。
【請求項１】
入力データに対して、出現頻度が高い順に符号を与えて符号化するデータ圧縮方法であって、
１）出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成するステップと、
２）入力データについて前記テーブルを参照して一致するものを検索するステップと、
３）前記ステップ２）の結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとするステップと、
４）前記ステップ２）の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとするステップと
を有することを特徴とするデータ圧縮方法。
【請求項２】
前記ステップ１）において、入力データの出現頻度を高い順に合算して全体に占める出現率を求めるステップを有し、
全体に占める出現率が所定値以上である場合、その出現頻度をステップ１）における所定値以上であると判断してテーブルを作成する請求項１に記載のデータ圧縮方法。
【請求項３】
５）前記ステップ１）の前に、画像データについて離散コサイン変換をするステップを更に有する請求項１または２に記載のデータ圧縮方法。
【請求項４】
６）前記ステップ１）の前に、一次圧縮として固定長におけるデータ圧縮を行うステップを更に有する請求項１または２に記載のデータ圧縮方法。
【請求項５】
請求項１から４に記載のデータ圧縮方法によって符号化された出力データを復号化する復号方法であって、
１）出力データについて前記テーブルを参照して一致するものを検索するステップと、
２）前記ステップ１）の結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換するステップと、
３）前記ステップ１）の結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除するステップと
を有することを特徴とする復号方法。
【請求項６】
入力データに対して、出現頻度が高い順に符号を与えて符合化するためのデータ圧縮プログラムであって、
１）出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成する手順と、
２）入力データについて前記テーブルを参照して一致するものを検索する手順と、
３）前記手順２）の結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとする手順と、
４）前記手順２）の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする手順と
をデータ処理装置に実行させることを特徴とするデータ圧縮プログラム。
【請求項７】
請求項６に記載のデータ圧縮プログラムによって符号化された出力データを復号化するための復号プログラムであって、
１）出力データについて前記テーブルを参照して一致するものを検索する手順と、
２）前記手順１）の結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換する手順と、
３）前記手順１）の結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除する手順と
をデータ処理装置に実行させることを特徴とする復号プログラム。
【請求項８】
入力データに対して、出現頻度が高い順に符号を与えて符号化する画像処理装置であって、
出現頻度が所定値以上である入力データについて、各入力データと各入力データに対応する符号とを関連付けるテーブルを作成する手段と、
入力データについて前記テーブルを参照して一致するものを検索する手段と、
検索した結果、前記入力データに一致するものがある場合、前記テーブルに従ってその入力データを変換して出力データとする手段と、
検索の結果、前記入力データに一致するものがない場合、その入力データに冗長符号を加えて出力データとする手段と
を有することを特徴とする画像処理装置。
【請求項９】
請求項８に記載の画像処理装置によって符号化された出力データを復号化する画像処理装置であって、
出力データについて前記テーブルを参照して一致するものを検索する手段と、
検索した結果、前記出力データに一致するものがある場合、前記テーブルに従ってその出力データを変換する手段と、
検索した結果、前記出力データに一致するものがない場合、その出力データから前記冗長符号を削除する手段と
を有することを特徴とする画像処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００９−２９６３６８（Ｐ２００９−２９６３６８Ａ）
【公開日】平成２１年１２月１７日（２００９．１２．１７）
【国際特許分類】
【出願番号】特願２００８−１４８３７０（Ｐ２００８−１４８３７０）
【出願日】平成２０年６月５日（２００８．６．５）
【出願人】（３０３０００３７２）コニカミノルタビジネステクノロジーズ株式会社 (12,802)
【Ｆターム（参考）】
【公開日】平成２１年１２月１７日（２００９．１２．１７）
【国際特許分類】
【出願日】平成２０年６月５日（２００８．６．５）
【出願人】（３０３０００３７２）コニカミノルタビジネステクノロジーズ株式会社 (12,802)
【Ｆターム（参考）】
[ Back to top ]