JP3580251B2 - データ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体 - Google Patents
データ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体 Download PDFInfo
- Publication number
- JP3580251B2 JP3580251B2 JP2000396450A JP2000396450A JP3580251B2 JP 3580251 B2 JP3580251 B2 JP 3580251B2 JP 2000396450 A JP2000396450 A JP 2000396450A JP 2000396450 A JP2000396450 A JP 2000396450A JP 3580251 B2 JP3580251 B2 JP 3580251B2
- Authority
- JP
- Japan
- Prior art keywords
- code
- encoding
- identification
- identification value
- run
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 143
- 238000013144 data compression Methods 0.000 title claims description 45
- 238000007906 compression Methods 0.000 title description 10
- 230000006835 compression Effects 0.000 title description 10
- 238000010187 selection method Methods 0.000 claims description 9
- 230000000694 effects Effects 0.000 description 11
- 238000010586 diagram Methods 0.000 description 8
- 238000007796 conventional method Methods 0.000 description 2
- 230000006866 deterioration Effects 0.000 description 1
- 238000004519 manufacturing process Methods 0.000 description 1
- 230000005236 sound signal Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- H04N19/91—Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Compression Of Band Width Or Redundancy In Fax (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明はデータ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体に関し、特に高い圧縮率を実現できるデータ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
従来のデータ圧縮装置の一例が、特開平６−３１１３６９号公報（以下、先行技術文献という）に記載されている。この先行技術文献記載の技術は量子化された画像信号を入力データとしてデータ圧縮処理を行う画像符号化装置におけるデータ圧縮装置についてのものである。このデータ圧縮装置の構成図を図７に、その動作を示すフローチャートを図８に夫々示す。このデータ圧縮装置は、それぞれ異なるハフマン符号化テーブルを用いてデータ圧縮を行う第１ハフマン符号化部３０１〜第３ハフマン符号化部３０３と、これらのハフマン符号化部３０１〜３０３の中から最小の符号量を出力するハフマン符号化部を選択し、選択されたハフマン符号化部を示す識別符号と、選択されたハフマン符号化部によって圧縮されたハフマン符号を出力する符号選択部３０４とから構成されている。
【０００３】
このような構成を有する従来のデータ圧縮装置（図７参照）は次のようにデータ圧縮を行う。まず、入力データを第１ハフマン符号化部３０１〜第３ハフマン符号化部３０３によって符号化する。これらのハフマン符号化部３０１〜３０３ではそれぞれ異なるハフマン符号化表を用いて入力データをハフマン符号化し、ハフマン符号を符号選択部３０４に出力する。符号選択部３０４では入力された複数のハフマン符号から最も符号量が少ないものを選択し、最も符号量の少ないハフマン符号と、そのハフマン符号の生成に用いられたハフマン符号化部を示す識別符号を出力する。
【０００４】
次に、このデータ圧縮装置の動作について説明する。ここでは複数のデータを圧縮する手法を説明する。図８を参照すると、手順４０１ではｎの値を０に初期化する。ｎの値は現在何番目のデータを処理しているかを示す変数である。
【０００５】
手順４０２、４０３、４０４ではそれぞれ異なるハフマン符号化表を用いてｎ番目のデータをハフマン符号化しハフマン符号を得る。
【０００６】
手順４０５では、手順４０２、４０３、４０４で得られたハフマン符号の中で最小の符号量となるものを選択する。そして最小の符号量を生成するハフマン符号化手順（４０２、４０３、４０４のいずれか）を示す識別値（一例として、手順４０２なら０、手順４０３なら１、手順４０４なら２）をＣ（ｎ）とする。
【０００７】
手順４０６では、手順４０５で選択された最小の符号量となるハフマン符号をＨ（ｎ）とし、これを処理結果として出力する。
【０００８】
手順４０７では、圧縮すべきデータが残っていれば（手順４０７にて「イエス」の場合）手順４０８へ、そうでなければ（手順４０７にて「ノ−」の場合）手順４０９へ処理を分岐する。
【０００９】
手順４０８では、ｎを１増加し、手順４０２へ戻る。手順４０９では、識別値Ｃ（０〜ｎ）を符号化して識別符号ＣＣとし、これを処理結果として出力する。従って、処理全体としては、ハフマン符号Ｈ（０〜ｎ）と識別符号ＣＣが処理結果として出力される。
【００１０】
このようなデータ圧縮処理を複数回繰り返した場合、識別符号ＣＣの符号量が増大し、符号化効率劣化の要因と成り得る。そのため、オーディオ信号の国際標準圧縮方式であるＭＰＥＧ−２ ＡＡＣでは、識別符号の生成にランレングス符号化を用いることで識別符号の符号量削減を図っている。ＭＰＥＧ−２ ＡＡＣ規格の詳細については、「１９９７年、インフォメーション テクノロジー −ジェネリック コーディング オブ ムービング ピクチャーズ アンド アソシエイティッド オーディオ、パート７：アドバンスド オーディオ コーディング、エーエーシー”「Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ−Ｇｅｎｅｒｉｃ ｃｏｄｉｎｇ ｏｆ ｍｏｖｉｎｇ ｐｉｃｔｕｒｅｓ ａｎｄａｓｓｏｃｉａｔｅｄ ａｕｄｉｏ， Ｐａｒｔ７：Ａｄｖａｎｃｅｄ Ａｕｄｉｏ Ｃｏｄｉｎｇ，ＡＡＣ」に詳しく記載されている。ＭＰＥＧ−２ ＡＡＣでの識別符号の生成方法を以下で説明する。
【００１１】
ＭＰＥＧ−２ ＡＡＣでは０から１５までの数値を用いて、選択されたハフマン符号化部を表す。例えば、図７において、第１のハフマン符号化部３０１が選択されれば「０」、第２のハフマン符号化部３０２が選択されれば「１」、第３のハフマン符号化部３０３が選択されれば「２」といった具合に識別値が符号選択部３０４から出力される。識別値は複数まとめられてランレングス符号化され識別符号となる。
【００１２】
例えば、識別値が「０，０，０，２，２，１，１，１，１」であった場合、「０」が「３」連続、「２」が「２」連続、「１」が「４」連続という意味で「０，３，２，２，１，４」という識別符号となる。このようにランレングス符号化では、「ある値」が「いくつ連続するか」を符号化する。ＭＰＥＧ−２ ＡＡＣ規格では一般に「ある値」を４ビット、「いくつ連続するか」を５ビットで符号化する。先ほどの例（「０，０，０，２，２，１，１，１，１」）の各数値を４ビットで符号化すると４ビット×９＝３６ビット必要となるが、ランレングス符号化することにより「０，３，２，２，１，４」は（４ビット＋５ビット）×３＝２７ビットで符号化でき、符号量を削減することができる。
【００１３】
【発明が解決しようとする課題】
しかしながら、この符号量削減効果は、同じ識別値が多く連続する場合にのみ得られる。例えば、識別値が「０，１，０，２，１，２，０，１，２」という場合、各値を４ビットで符号化すれば４ビット×９＝３６ビットであるのに対し、ランレングス符号化を用いると（４ビット＋５ビット）×９＝８１ビット必要となってしまう。
【００１４】
即ち、符号量が多く圧縮率が悪いという欠点がある。その理由は、選択されたハフマン符号化手段を示す識別符号の符号化効率が悪いためである。
【００１５】
そこで本発明の目的は、符号量を低減させ高い圧縮率が得られるデータ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体を提供することにある。
【００１６】
【課題を解決するための手段】
前記課題を解決するために本発明によるデータ圧縮装置は、順次入力されるデータを夫々異なる手法で符号化する複数のデータ符号化手段と、前記各データ符号化手段で得られた符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った前記データ符号化手段の識別値の履歴を符号化した識別符号を出力する符号選択手段とを含むデータ圧縮装置であって、その装置は前記符号選択手段から出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記データ符号化手段を再選択し再符号化を行う再符号化手段を含むことを特徴とする。
【００１７】
又、本発明によるデータ圧縮方法は、順次入力されるデータを夫々異なる手法で符号化するデータ符号化手順と、前記異なる手法で符号化された符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った手法の識別値の履歴を符号化した識別符号を出力する符号選択手順とを含むデータ圧縮方法であって、その方法は前記符号選択手順によって出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記手法を再選択し再符号化を行う再符号化手順を含むことを特徴とする。
【００１８】
又、本発明による記録媒体は、順次入力されるデータを夫々異なる手法で符号化するデータ符号化手順と、前記異なる手法で符号化された符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った手法の識別値の履歴を符号化した識別符号を出力する符号選択手順とをコンピュータに実行させるための制御プログラムを記録した記録媒体であって、その記録媒体は前記制御プログラムは前記符号選択手順によって出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記手法を再選択し再符号化を行う再符号化手順を含むことを特徴とする。
【００１９】
本発明によれば、再符号化部（図１の１０５）が識別符号とハフマン符号の合計符号量が従来よりも小さくなるよう再符号化する。
【００２０】
【発明の実施の形態】
以下、本発明の実施の形態について添付図面を参照しながら説明する。図１は本発明に係るデータ圧縮装置の第１の実施の形態の構成図である。同図を参照すると、データ圧縮装置は第１ハフマン符号化部１０１〜第３ハフマン符号化部１０３と、符号選択部１０４と、再符号化部１０５と、これら構成部分１０１〜１０５を制御する制御部１０６とから構成されている。
【００２１】
第１ハフマン符号化部１０１〜第３ハフマン符号化部１０３は従来手法における第１ハフマン符号化部３０１〜第３ハフマン符号化部３０３と同様に入力データをそれぞれ異なるハフマン符号表を用いてハフマン符号化し、ハフマン符号を符号選択部１０４に出力する。なお、本発明ではハフマン符号化部が３つ（１０１，１０２，１０３）存在する場合を例に説明するが、この数に制限はない。
【００２２】
符号選択部１０４は従来手法における符号選択部３０４と同様に、入力された複数のハフマン符号から最も符号量が少ないものを選択し、最も符号量の少ないハフマン符号と、そのハフマン符号の生成に用いられたハフマン符号化部を示す識別値を符号化した識別符号とを再符号化部１０５に出力する。
【００２３】
次に、再符号化部１０５の構成について説明する。図２は再符号化部１０５の構成図である。なお、図１と同様の構成部分には同一番号を付し、その説明を省略する。図２を参照すると、再符号化部１０５は符号選択部１０４から入力された識別符号を変更する識別符号変更部１０７と、識別符号変更部１０７にて変更された識別符号に基づき再選択される第１ハフマン符号化部１０１〜第３ハフマン符号化部１０３と、これらハフマン符号化部１０１〜１０３で符号化されたデ−タから最短符号を選択する最短符号選択部１０８とから構成されている。
【００２４】
再符号化部１０５は、識別符号とハフマン符号の合計符号量がより小さくなるように識別符号を変更してハフマン符号化部（１０１，１０２，１０３のいずれか）を再選択し、再選択されたハフマン符号化部を示す識別値を符号化した識別符号と、再選択されたハフマン符号化部を用いて符号化されたハフマン符号を出力する。
【００２５】
次に、図３及び図４を参照して第１の実施の形態の全体の動作について詳細に説明する。図３及び図４は本発明に係るデータ圧縮装置の第１の実施の形態の動作を示すフロ−チャートである。
【００２６】
図３を参照すると、手順２０１ではｎの値を０に初期化する。ｎの値は現在何番目のデータを処理しているかを示す変数である（図８に示す従来技術における手順４０１と同じである）。
【００２７】
手順２０２、２０３、２０４では夫々異なるハフマン符号化表を用いて第１ハフマン符号化部３０１〜第３ハフマン符号化部３０３にてｎ番目のデータをハフマン符号化しハフマン符号を得る（図８に示す従来技術における手順４０２、４０３、４０４と同じである）
手順２０５では、符号選択部１０４にて手順２０２、２０３、２０４で得られたハフマン符号の中で最小の符号量となるハフマン符号化部を選択する。そして最小の符号量を生成するハフマン符号化手順（２０２、２０３、２０４のいずれか）を示す識別値（一例として、手順２０１なら０、手順２０２なら１、手順２０３なら２）をＣ（ｎ）とする（図８に示す従来技術における手順４０５と同じである）。
【００２８】
手順２０６では、手順２０５で選択された最小の符号量となるハフマン符号をＨ（ｎ）とする（図８に示す従来技術における手順４０６とはＨ（ｎ）を処理結果として出力しない点で異なる）。
【００２９】
手順２０７では、圧縮すべきデータが残っていれば（手順２０７にて「イエス」の場合）手順２０８へ、そうでなければ（手順２０７にて「ノ−」の場合）手順２０９へ処理を分岐する（図８に示す従来技術における手順４０７と同じである）。
【００３０】
手順２０８では、ｎを１増加し、手順２０２へ戻る（図８に示す従来技術における手順４０８と同じである）。
【００３１】
手順２０９では、識別値Ｃ（０〜ｎ）を符号化して識別符号ＣＣを生成する。その符号化手法にはランレングス符号化等を用いることができる（図８に示す従来技術における手順４０９とは識別符号ＣＣを処理結果として出力しない点で異なる）。
【００３２】
次に、図４を参照すると、手順２１０では識別符号変更部１０７にて識別値Ｃ（０〜ｎ）に変更を加え、これを識別値Ｃ’（０〜ｎ）とする。変更の加え方については後述するが、一般にはＣ’（０〜ｎ）を符号化した識別符号の符号量が少なくなるような変更を行う。例えば、識別符号の生成がランレングス符号化によって行われる場合は、識別値Ｃ’（０〜ｎ）のラン長が長くなるように（同じ識別値が多く連続するように）変更を行う。
【００３３】
手順２１１では識別値Ｃ’（０〜ｎ）が示すハフマン符号化部（１０１，１０２，１０３のいずれか）を用いて０番目からｎ番目までのデータをハフマン符号化し、生成されたハフマン符号をＨ’（０〜ｎ）とする。
【００３４】
手順２１２では、識別値Ｃ’（０〜ｎ）を手順２０９と同様な手法で符号化して識別符号ＣＣ’を生成する。
【００３５】
手順２１３では、最短符号選択部１０８にて識別符号ＣＣ’とＨ’（０〜ｎ）の合計符号量が識別符号ＣＣとＨ（０〜ｎ）の合計符号量よりも小さい場合に（手順２１３にて「イエス」の場合）手順２１４へ、そうでなければ（手順２１３にて「ノ−」の場合）手順２１５へ分岐する。手順２１３では、手順２１０での識別値の変更によって符号量削減効果が得られたかどうかを判定している。
【００３６】
手順２１４では、現時点での最小符号量を実現する識別値として、識別値Ｃ’（０〜ｎ）を識別値Ｃ（０〜ｎ）に、識別符号ＣＣ’を識別符号ＣＣに、ハフマン符号Ｈ’（０〜ｎ）をハフマン符号Ｈ（０〜ｎ）に夫々値をコピーする。
【００３７】
手順２１５では、手順２１０で行う識別値Ｃ（０〜ｎ）の変更において、他の変更候補が残っていれば（手順２１５にて「イエス」の場合）手順２１０へ戻り処理を繰り返し、他の変更候補が残っていなければ（手順２１５にて「ノ−」の場合）手順２１６へ進む。このように識別値の変更とハフマン符号化を繰り返し、最小符号量を実現する識別値を探索する。
【００３８】
手順２１６では、処理結果として識別符号ＣＣとハフマン符号Ｈ（０〜ｎ）を出力する。
【００３９】
次に、手順２１０と手順２１５について一例を挙げて説明する。例えば、データの数が５（即ち、ｎ＝４）であり、手順２０５で得られた識別値Ｃ（０〜４）が”０，１，０，１，１”であったとする。また、手順２０９と手順２１２において識別符号の生成に従来技術の説明で用いたランレングス符号化を用いるとする。すると、手順２０９が終了した時点で識別符号ＣＣの符号量は、３６ビットとなる。
【００４０】
即ち、識別値Ｃ（０〜４）が”０，１，０，１，１”だから、「０」が「１」連続、「１」が「１」連続、「０」が「１」連続、「１」が「２」連続であり、ランの数は４となる。従って、識別符号ＣＣの符号量は、９ビット×４＝３６ビットとなるのである。
【００４１】
手順２１０では上述のように識別符号ＣＣの符号量が少なくなるように識別値Ｃを変更する。ランレングス符号化においては、ランの長さを長くすることが符号量削減となる。現在の識別値Ｃ（０〜４）＝”０，１，０，１，１”は上述したように４つのランに分けられ、各々のランを長くすることで識別符号の符号長を少なくできる。
【００４２】
たとえば、最初の”０”の１連続ランを長くすると識別値Ｃ’（０〜４）は”０，０，０，１，１”となり、２つのランとなる。従って、９ビット×２＝１８ビットで符号化できる。又、２つ目のランを左方向に長くした場合は、Ｃ’（０〜４）＝”１，１，０，１，１”、右方向に長くした場合は、Ｃ’（０〜４）＝”０，１，１，１，１”、左右方向に長くした場合はＣ’（０〜４）＝”１，１，１，１，１”となる。同様に、３つ目のランを左方向に長くした場合は、Ｃ’（０〜４）＝”０，０，０，１，１”、右方向に長くした場合は、Ｃ’（０〜４）＝”０，１，０，０，１”、左右方向に長くした場合はＣ’（０〜４）＝”０，０，０，０，１”となり、４つ目のランを左方向に長くした場合は、Ｃ’（０〜４）＝”０，１，１，１，１”となる。
【００４３】
このように各ランを、左方向、右方向、左右方向に長くした場合の各々が識別値Ｃの変更候補となる。識別値Ｃを変更することで、一般にハフマン符号の符号量は増大する。しかしながら、識別符号ＣＣにおける符号量削減効果がハフマン符号量増大よりも大きい場合にデータ圧縮処理全体としての圧縮率向上が実現できる。
【００４４】
手順２１５では全てのランについて左方向、右方向、左右方向に長くした場合が既に実行されたかを判定し、変更候補が残っていれば（手順２１５にて「イエス」の場合）処理２１０へ戻る。実装方法の一例としては、各ランを最も左側のランから順に、ランを長くしたものを変更候補としていき、そして、最も右側のランを長くしたものを最後の変更候補とするという方法が考えられる。又、この手順法によって符号量削減効果が得られた場合は、さらにもう一度、最も左側のランから順に、ランを長くしたものを変更したものを変更候補とし、これを最も右側のランまで繰り返す上記手順を符号量削減効果が得られなくなるまで、もしくは予め定められた規定回数まで繰り返しても良い。
【００４５】
なお、手順２０２、２０３、２０４、２１１におけるハフマン符号化においては、実際にハフマン符号化を行わず、ハフマン符号量を求めるだけでもよい。これによって演算量削減効果が得られることがある。その場合、処理２１６で、識別値Ｃ（０〜ｎ）を用いて０番目からｎ番目までのデータをハフマン符号化してハフマン符号Ｈ（０〜ｎ）を生成する。
【００４６】
なお、手順２１０、２１５の説明では識別値Ｃの変更候補として、ランを左方向、右方向、左右方向に長くする場合の３通り全てを候補としたが、これら３つの中のいずれか１つもしくは２つのみを用いても良い。
【００４７】
次に、第２の実施の形態について説明する。第２の実施の形態は上述した手順２１５の具体例を示したものである。図４を参照すると、手順２１５では全てのランについて左方向、右方向、左右方向に長くした場合が既に実行されたか否かが判定され、変更候補が残っていれば手順２１０へ戻る。
【００４８】
実装方法の一例としては、考えられ得るランの結合の候補を全て変更候補とするというものがあるが、この方法では必要演算量が膨大となる場合がある。そこで、必要演算量が少なくて済む実装方法の一例として、各ランを最も左側のランから順に、ランを長くしたものを変更候補としていき、そして、最も右側のランを長くしたものを最後の変更候補とするという方法が考えられる。又、逆に最も右側のランから順に、ランを長くしたものを変更候補とし、最も左側のランを長くしたものを最後の変更候補とする方法も考えられる。
【００４９】
又、この手順によって符号量削減効果が得られた場合は、さらにもう一度、最も左側のランから順に、ランを長くしたものを変更候補とし、これを最も右側のランまで繰り返す上記手順を符号量削減効果が得られなくなるまで、もしくは予め定められた規定回数まで繰り返してよい。
【００５０】
この方法に沿うように図４のフローチャートを書き換えたものが図５の第２の実施の形態の動作を示すフローチャートである。なお、手順２０１〜２０９については図３のフローチャートと同様であるため説明を省略する。
【００５１】
図５を参照すると、手順２０９ａでは、現在処理の対象となっているランを表す変数をラン位置Ｒとし、その値をＣ（０）を含むラン、即ち、最も左側のランとする。
【００５２】
次に、手順２１０では、識別値Ｃ（０〜ｎ）に３種類の変更を加え、ラン位置Ｒのランを左方向に長くした識別値を識別値ＣＬ´（０〜ｎ）、右方向に長くした識別値を識別値ＣＲ´（０〜ｎ）、左右方向に長くした識別値を識別値ＣＬＲ´（０〜ｎ）とする。
【００５３】
次に、手順２１１では、識別値ＣＬ´（０〜ｎ）、ＣＲ´（０〜ｎ）、ＣＬＲ´（０〜ｎ）が示すハフマン符号化部を用いて０番目からｎ番目までのデータをハフマン符号化し、生成されたハフマン符号を各々ＨＬ´（０〜ｎ）、ＨＲ´（０〜ｎ）、ＨＬＲ´（０〜ｎ）とする。
【００５４】
次に、手順２１２では、識別値ＣＬ´（０〜ｎ）、ＣＲ´（０〜ｎ）、ＣＬＲ´（０〜ｎ）を手順２０９と同様な手法で各々符号化して識別符号ＣＣＬ´，ＣＣＲ´，ＣＣＬＲ´を生成する。又、識別符号ＣＣＬ´とハフマン符号ＨＬ´（０〜ｎ）との合計符号量と、識別符号ＣＣＲ´とハフマン符号ＨＲ´（０〜ｎ）との合計符号量と、識別符号ＣＣＬＲ´とハフマン符号ＨＬＲ´（０〜ｎ）との合計符号量とを比較し、最も少ない符号量を実現する識別符号をＣＣ´、ハフマン符号をＨ´（０〜ｎ）、識別値をＣ´（０〜ｎ）とする。例えば、識別符号ＣＣＬ´とハフマン符号ＨＬ´（０〜ｎ）との合計符号量が最小であれば、ＣＣ´＝ＣＣＬ´、Ｈ´（０〜ｎ）＝ＨＬ´（０〜ｎ）、Ｃ´（０〜ｎ）＝ＣＬ´（０〜ｎ）とする。
【００５５】
次に、手順２１３では、識別符号ＣＣ´とハフマン符号Ｈ´（０〜ｎ）との合計符号量が識別符号ＣＣとハフマン符号Ｈ（０〜ｎ）の合計符号量よりも小さい場合（手順２１３にて「イエス」の場合）に手順２１４へ進み、そうでなければ（手順２１３にて「ノ−」の場合）手順２１５へ分岐する。この手順２１３では、手順２１０での識別値の変更によって符号量削減効果が得られたか否かを判定している。
【００５６】
次に、手順２１４では、現時点での最小符号量を実現する識別値として、識別値Ｃ´（０〜ｎ）を識別値Ｃ（０〜ｎ）に、識別符号ＣＣ´を識別符号ＣＣに、ハフマン符号Ｈ´（０〜ｎ）をハフマン符号Ｈ（０〜ｎ）に夫々コピーする。
【００５７】
次に、手順２１５では、ラン位置Ｒが示すランがＣ（ｎ）を含むラン、即ち、最も右側のランであれば（手順２１５にて「イエス」の場合）手順２１６へ進み、そうでなければ（手順２１５にて「ノ−」の場合）、手順２１５ａでラン位置Ｒを一つ右隣のランへ移動して手順２１０へ戻る。
【００５８】
次に、手順２１６では、処理結果として識別符号ＣＣとハフマン符号Ｈ（０〜ｎ）とを出力する。
【００５９】
ここで、上述した手順２０９ａ以降の処理について具体的な数値を用いて説明する。一例として、手順２０９にて識別値Ｃ（０〜４）＝”０，１，０，１，１”が得られた場合について説明する。この場合、最も左側のラン（Ｒ１とする）が“０”、その右隣のラン（Ｒ２とする）が“１”、その右隣のラン（Ｒ３とする）が“０”、その右隣のラン（Ｒ４とする）が“１，１”である。
【００６０】
まず、手順２０９ａではラン位置をＲ１とする。次に、手順２１０では、ラン位置Ｒ１のランを右方向に長くする。従って、識別値ＣＲ´（０〜４）＝”０，０，０，１，１”となる。なお、ラン位置Ｒ１は左端であるためランを左方向及び左右方向に長くすることはできない。同様に、ラン位置Ｒ４は右端であるためランを右方向及び左右方向に長くすることはできない。
【００６１】
次に、手順２１１では識別値ＣＲ´（０〜４）が示すハフマン符号化部で各々入力データをハフマン符号化する。即ち、まず識別値ＣＲ´（０）＝”０”だから最初の入力データＤ１を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＲ´（０）を得る。同様に、識別値ＣＲ´（１）＝”０”だから第２の入力データＤ２を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＲ´（１）を、識別値ＣＲ´（２）＝”０”だから第３の入力データＤ３を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＲ´（２）を、識別値ＣＲ´（３）＝”１”だから第４の入力データＤ４を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（３）を、識別値ＣＲ´（４）＝”１”だから第５の入力データＤ５を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（４）を夫々得る。
【００６２】
次に、手順２１２では識別値ＣＲ´（０〜４）＝”０，０，０，１，１”から識別符号ＣＣＲ´（０〜４）を生成する。すると、識別符号ＣＣＲ´（０〜４）＝“０，３，１，２”となる。なお、ラン位置Ｒ１が左端であるため識別値ＣＬ´（０〜４）及びＣＬＲ´（０〜４）は存在しない。従って、この場合、合計符号量の比較は行わない。即ち、識別符号ＣＣＲ´（０〜４）＝“０，３，１，２”をＣＣ´とし、ハフマン符号ＨＲ´（０〜４）をＨ´（０〜４）とし、識別値ＣＲ´（０〜４）＝”０，０，０，１，１”をＣ´（０〜４）とする。
【００６３】
次に、手順２１３では識別符号ＣＣ´とハフマン符号Ｈ´との合計符号量が識別符号ＣＣとハフマン符号Ｈとの合計符号量よりも小さいか否かを判定する。この場合、識別符号ＣＣ´とハフマン符号Ｈ´との合計符号量が識別符号ＣＣとハフマン符号Ｈとの合計符号量よりも小さいものとする。そこで、手順２１４に進み、識別値Ｃ´（０〜４）を識別値Ｃ（０〜４）に、識別符号ＣＣ´（０〜４）をＣＣ（０〜４）に、ハフマン符号Ｈ´（０〜４）をハフマン符号Ｈ（０〜４）にコピーする。
【００６４】
次に、手順２１５ではラン位置Ｒ１は最も右側のランではないので、手順２１５ａへ進み、ラン位置を右隣のＲ２へ移動する。そして、手順２１０に戻る。これから先は上述の手順２１０以降の繰り返しとなる。いま、ラン位置Ｒ２の場合についてのみ説明するが、ラン位置Ｒ３，Ｒ４の場合も同様に説明できる。
【００６５】
手順２１０ではラン位置Ｒ２のランを左方向に長くする。元の識別値Ｃ（０〜４）＝”０，１，０，１，１”だから、、識別値ＣＬ´（０〜４）＝”１，１，０，１，１”となる。次に、ラン位置Ｒ２のランを右方向に長くする。すると、識別値ＣＲ´（０〜４）＝”０，１，１，１，１”となる。次に、ラン位置Ｒ２のランを左右方向に長くする。すると、識別値ＣＬＲ´（０〜４）＝”１，１，１，１，１”となる。
【００６６】
次に、手順２１１では識別値ＣＬ´（０〜４）が示すハフマン符号化部で各々入力データをハフマン符号化する。即ち、まず識別値ＣＬ´（０）＝”１”だから最初の入力データＤ１を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬ´（０）を得る。同様に、識別値ＣＬ´（１）＝”１”だから第２の入力データＤ２を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬ´（１）を、識別値ＣＬ´（２）＝”０”だから第３の入力データＤ３を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＬ´（２）を、識別値ＣＬ´（３）＝”１”だから第４の入力データＤ４を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬ´（３）を、識別値ＣＬ´（４）＝”１”だから第５の入力データＤ５を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬ´（４）を夫々得る。
【００６７】
同様に、識別値ＣＲ´（０〜４）が示すハフマン符号化部で各々入力データをハフマン符号化する。即ち、まず識別値ＣＲ´（０）＝”０”だから最初の入力データＤ１を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＲ´（０）を得る。同様に、識別値ＣＲ´（１）＝”１”だから第２の入力データＤ２を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（１）を、識別値ＣＲ´（２）＝”１”だから第３の入力データＤ３を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（２）を、識別値ＣＲ´（３）＝”１”だから第４の入力データＤ４を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（３）を、識別値ＣＲ´（４）＝”１”だから第５の入力データＤ５を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（４）を夫々得る。
【００６８】
同様に、識別値ＣＬＲ´（０〜４）が示すハフマン符号化部で各々入力データをハフマン符号化する。即ち、まず識別値ＣＬＲ´（０）＝”１”だから最初の入力データＤ１を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（０）を得る。同様に、識別値ＣＬＲ´（１）＝”１”だから第２の入力データＤ２を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（１）を、識別値ＣＬＲ´（２）＝”１”だから第３の入力データＤ３を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（２）を、識別値ＣＬＲ´（３）＝”１”だから第４の入力データＤ４を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（３）を、識別値ＣＬＲ´（４）＝”１”だから第５の入力データＤ５を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（４）を夫々得る。
【００６９】
次に、手順２１２では識別値ＣＬ´（０〜４），ＣＲ´（０〜４），ＣＬＲ´（０〜４）から識別符号ＣＣＬ´，ＣＣＲ´，ＣＣＬＲ´を生成する。すると、識別符号ＣＣＬ´＝“１，２，０，１，１，２”、識別符号ＣＣＲ´＝“０，１，１，４”、識別符号ＣＣＬＲ´＝“１，５”となる。
【００７０】
次に、識別符号ＣＣＬ´とハフマン符号ＨＲ´（０〜４）との合計符号量と、識別符号ＣＣＲ´とハフマン符号ＨＲ´（０〜４）との合計符号量と、識別符号ＣＬＲ´とハフマン符号ＨＬＲ´（０〜４）との合計符号量とを比較し、最も少ない符号量を実現する識別符号をＣＣ´、ハフマン符号をＨ´（０〜４）、識別値をＣ´（０〜４）とする。
【００７１】
そして、上述したのと同様の手順で手順２１３，２１４を実行し，手順２１５でラン位置Ｒ２は最も右側のランではないので、手順２１５ａへ進み、ラン位置を右隣のＲ３へ移動する。そして、手順２１０に戻る。以下、ラン位置Ｒ２について行ったのと同様の手順をラン位置Ｒ２及びＲ３について実行する。
【００７２】
次に、第３の実施の形態について説明する。第３の実施の形態はデータ圧縮方法の制御プログラムを記録した記録媒体に関するものである。図６は記録媒体及び記録媒体駆動装置の一例の構成図である。同図を参照すると、記録媒体駆動装置は、前述した制御部（図１参照）１０６と、入力部１１０と、記憶部１１１とから構成され、制御部１０６が前述したハフマン符号化部１０１，１０２，１０３と、符号選択部１０４と、再符号化部１０５と（図１参照）を制御する。一方、記録媒体１１２には図３〜図５にフローチャートで示した制御プログラムが記録されている。
【００７３】
次に、記録媒体駆動装置の動作について説明する。まず、入力部１１０から制御部１０６に対し記録媒体１１２の制御プログラムの入力命令が出されると、制御部１０６は記録媒体１１２から制御プログラムを読み込み、記憶部１１に格納する。次に、入力部１１０から制御部１０６に対し制御プログラムの実行命令が出されると、制御部１０６は記憶部１１から制御プログラムを読出し、その制御プログラムに従ってハフマン符号化部１０１，１０２，１０３と、符号選択部１０４と、再符号化部１０５とを制御する。その制御内容については既に述べたので説明を省略する。
【００７４】
【発明の効果】
本発明による第１の発明によれば、順次入力されるデータを夫々異なる手法で符号化する複数のデータ符号化手段と、前記各データ符号化手段で得られた符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った前記データ符号化手段の識別値の履歴を符号化した識別符号を出力する符号選択手段とを含むデータ圧縮装置であって、その装置は前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記データ符号化手段を再選択し再符号化を行う再符号化手段を含むため、符号量を従来技術よりも低減することが可能となる。
【００７５】
即ち、識別符号の符号量が少なくなるような変更とその時の符号量計算を繰り返し行い、識別符号とハフマン符号の合計符号量がより小さくなるように構成されているため、より高い圧縮率でデータ圧縮することができる。又、第２及び第３の発明も第１の発明と同様の効果を奏する。
【図面の簡単な説明】
【図１】本発明に係るデータ圧縮装置の第１の実施の形態の構成図である。
【図２】同データ圧縮装置の再符号化部１０５の構成図である。
【図３】本発明に係るデータ圧縮装置の第１の実施の形態の動作を示すフロ−チャートである。
【図４】本発明に係るデータ圧縮装置の第１の実施の形態の動作を示すフロ−チャートである。
【図５】第２の実施の形態の動作を示すフローチャートである。
【図６】記録媒体及び記録媒体駆動装置の一例の構成図である。
【図７】従来のデータ圧縮装置の一例の構成図である。
【図８】従来のデータ圧縮装置の動作を示すフローチャートである。
【符号の説明】
１０１〜１０３ 第１〜第３ハフマン符号化部
１０４ 符号選択部
１０５ 再符号化部
１０６ 制御部
１０７ 識別符号変更部
１０８ 最短符号選択部
１１２ 記録媒体
【発明の属する技術分野】
本発明はデータ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体に関し、特に高い圧縮率を実現できるデータ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
従来のデータ圧縮装置の一例が、特開平６−３１１３６９号公報（以下、先行技術文献という）に記載されている。この先行技術文献記載の技術は量子化された画像信号を入力データとしてデータ圧縮処理を行う画像符号化装置におけるデータ圧縮装置についてのものである。このデータ圧縮装置の構成図を図７に、その動作を示すフローチャートを図８に夫々示す。このデータ圧縮装置は、それぞれ異なるハフマン符号化テーブルを用いてデータ圧縮を行う第１ハフマン符号化部３０１〜第３ハフマン符号化部３０３と、これらのハフマン符号化部３０１〜３０３の中から最小の符号量を出力するハフマン符号化部を選択し、選択されたハフマン符号化部を示す識別符号と、選択されたハフマン符号化部によって圧縮されたハフマン符号を出力する符号選択部３０４とから構成されている。
【０００３】
このような構成を有する従来のデータ圧縮装置（図７参照）は次のようにデータ圧縮を行う。まず、入力データを第１ハフマン符号化部３０１〜第３ハフマン符号化部３０３によって符号化する。これらのハフマン符号化部３０１〜３０３ではそれぞれ異なるハフマン符号化表を用いて入力データをハフマン符号化し、ハフマン符号を符号選択部３０４に出力する。符号選択部３０４では入力された複数のハフマン符号から最も符号量が少ないものを選択し、最も符号量の少ないハフマン符号と、そのハフマン符号の生成に用いられたハフマン符号化部を示す識別符号を出力する。
【０００４】
次に、このデータ圧縮装置の動作について説明する。ここでは複数のデータを圧縮する手法を説明する。図８を参照すると、手順４０１ではｎの値を０に初期化する。ｎの値は現在何番目のデータを処理しているかを示す変数である。
【０００５】
手順４０２、４０３、４０４ではそれぞれ異なるハフマン符号化表を用いてｎ番目のデータをハフマン符号化しハフマン符号を得る。
【０００６】
手順４０５では、手順４０２、４０３、４０４で得られたハフマン符号の中で最小の符号量となるものを選択する。そして最小の符号量を生成するハフマン符号化手順（４０２、４０３、４０４のいずれか）を示す識別値（一例として、手順４０２なら０、手順４０３なら１、手順４０４なら２）をＣ（ｎ）とする。
【０００７】
手順４０６では、手順４０５で選択された最小の符号量となるハフマン符号をＨ（ｎ）とし、これを処理結果として出力する。
【０００８】
手順４０７では、圧縮すべきデータが残っていれば（手順４０７にて「イエス」の場合）手順４０８へ、そうでなければ（手順４０７にて「ノ−」の場合）手順４０９へ処理を分岐する。
【０００９】
手順４０８では、ｎを１増加し、手順４０２へ戻る。手順４０９では、識別値Ｃ（０〜ｎ）を符号化して識別符号ＣＣとし、これを処理結果として出力する。従って、処理全体としては、ハフマン符号Ｈ（０〜ｎ）と識別符号ＣＣが処理結果として出力される。
【００１０】
このようなデータ圧縮処理を複数回繰り返した場合、識別符号ＣＣの符号量が増大し、符号化効率劣化の要因と成り得る。そのため、オーディオ信号の国際標準圧縮方式であるＭＰＥＧ−２ ＡＡＣでは、識別符号の生成にランレングス符号化を用いることで識別符号の符号量削減を図っている。ＭＰＥＧ−２ ＡＡＣ規格の詳細については、「１９９７年、インフォメーション テクノロジー −ジェネリック コーディング オブ ムービング ピクチャーズ アンド アソシエイティッド オーディオ、パート７：アドバンスド オーディオ コーディング、エーエーシー”「Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ−Ｇｅｎｅｒｉｃ ｃｏｄｉｎｇ ｏｆ ｍｏｖｉｎｇ ｐｉｃｔｕｒｅｓ ａｎｄａｓｓｏｃｉａｔｅｄ ａｕｄｉｏ， Ｐａｒｔ７：Ａｄｖａｎｃｅｄ Ａｕｄｉｏ Ｃｏｄｉｎｇ，ＡＡＣ」に詳しく記載されている。ＭＰＥＧ−２ ＡＡＣでの識別符号の生成方法を以下で説明する。
【００１１】
ＭＰＥＧ−２ ＡＡＣでは０から１５までの数値を用いて、選択されたハフマン符号化部を表す。例えば、図７において、第１のハフマン符号化部３０１が選択されれば「０」、第２のハフマン符号化部３０２が選択されれば「１」、第３のハフマン符号化部３０３が選択されれば「２」といった具合に識別値が符号選択部３０４から出力される。識別値は複数まとめられてランレングス符号化され識別符号となる。
【００１２】
例えば、識別値が「０，０，０，２，２，１，１，１，１」であった場合、「０」が「３」連続、「２」が「２」連続、「１」が「４」連続という意味で「０，３，２，２，１，４」という識別符号となる。このようにランレングス符号化では、「ある値」が「いくつ連続するか」を符号化する。ＭＰＥＧ−２ ＡＡＣ規格では一般に「ある値」を４ビット、「いくつ連続するか」を５ビットで符号化する。先ほどの例（「０，０，０，２，２，１，１，１，１」）の各数値を４ビットで符号化すると４ビット×９＝３６ビット必要となるが、ランレングス符号化することにより「０，３，２，２，１，４」は（４ビット＋５ビット）×３＝２７ビットで符号化でき、符号量を削減することができる。
【００１３】
【発明が解決しようとする課題】
しかしながら、この符号量削減効果は、同じ識別値が多く連続する場合にのみ得られる。例えば、識別値が「０，１，０，２，１，２，０，１，２」という場合、各値を４ビットで符号化すれば４ビット×９＝３６ビットであるのに対し、ランレングス符号化を用いると（４ビット＋５ビット）×９＝８１ビット必要となってしまう。
【００１４】
即ち、符号量が多く圧縮率が悪いという欠点がある。その理由は、選択されたハフマン符号化手段を示す識別符号の符号化効率が悪いためである。
【００１５】
そこで本発明の目的は、符号量を低減させ高い圧縮率が得られるデータ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体を提供することにある。
【００１６】
【課題を解決するための手段】
前記課題を解決するために本発明によるデータ圧縮装置は、順次入力されるデータを夫々異なる手法で符号化する複数のデータ符号化手段と、前記各データ符号化手段で得られた符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った前記データ符号化手段の識別値の履歴を符号化した識別符号を出力する符号選択手段とを含むデータ圧縮装置であって、その装置は前記符号選択手段から出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記データ符号化手段を再選択し再符号化を行う再符号化手段を含むことを特徴とする。
【００１７】
又、本発明によるデータ圧縮方法は、順次入力されるデータを夫々異なる手法で符号化するデータ符号化手順と、前記異なる手法で符号化された符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った手法の識別値の履歴を符号化した識別符号を出力する符号選択手順とを含むデータ圧縮方法であって、その方法は前記符号選択手順によって出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記手法を再選択し再符号化を行う再符号化手順を含むことを特徴とする。
【００１８】
又、本発明による記録媒体は、順次入力されるデータを夫々異なる手法で符号化するデータ符号化手順と、前記異なる手法で符号化された符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った手法の識別値の履歴を符号化した識別符号を出力する符号選択手順とをコンピュータに実行させるための制御プログラムを記録した記録媒体であって、その記録媒体は前記制御プログラムは前記符号選択手順によって出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記手法を再選択し再符号化を行う再符号化手順を含むことを特徴とする。
【００１９】
本発明によれば、再符号化部（図１の１０５）が識別符号とハフマン符号の合計符号量が従来よりも小さくなるよう再符号化する。
【００２０】
【発明の実施の形態】
以下、本発明の実施の形態について添付図面を参照しながら説明する。図１は本発明に係るデータ圧縮装置の第１の実施の形態の構成図である。同図を参照すると、データ圧縮装置は第１ハフマン符号化部１０１〜第３ハフマン符号化部１０３と、符号選択部１０４と、再符号化部１０５と、これら構成部分１０１〜１０５を制御する制御部１０６とから構成されている。
【００２１】
第１ハフマン符号化部１０１〜第３ハフマン符号化部１０３は従来手法における第１ハフマン符号化部３０１〜第３ハフマン符号化部３０３と同様に入力データをそれぞれ異なるハフマン符号表を用いてハフマン符号化し、ハフマン符号を符号選択部１０４に出力する。なお、本発明ではハフマン符号化部が３つ（１０１，１０２，１０３）存在する場合を例に説明するが、この数に制限はない。
【００２２】
符号選択部１０４は従来手法における符号選択部３０４と同様に、入力された複数のハフマン符号から最も符号量が少ないものを選択し、最も符号量の少ないハフマン符号と、そのハフマン符号の生成に用いられたハフマン符号化部を示す識別値を符号化した識別符号とを再符号化部１０５に出力する。
【００２３】
次に、再符号化部１０５の構成について説明する。図２は再符号化部１０５の構成図である。なお、図１と同様の構成部分には同一番号を付し、その説明を省略する。図２を参照すると、再符号化部１０５は符号選択部１０４から入力された識別符号を変更する識別符号変更部１０７と、識別符号変更部１０７にて変更された識別符号に基づき再選択される第１ハフマン符号化部１０１〜第３ハフマン符号化部１０３と、これらハフマン符号化部１０１〜１０３で符号化されたデ−タから最短符号を選択する最短符号選択部１０８とから構成されている。
【００２４】
再符号化部１０５は、識別符号とハフマン符号の合計符号量がより小さくなるように識別符号を変更してハフマン符号化部（１０１，１０２，１０３のいずれか）を再選択し、再選択されたハフマン符号化部を示す識別値を符号化した識別符号と、再選択されたハフマン符号化部を用いて符号化されたハフマン符号を出力する。
【００２５】
次に、図３及び図４を参照して第１の実施の形態の全体の動作について詳細に説明する。図３及び図４は本発明に係るデータ圧縮装置の第１の実施の形態の動作を示すフロ−チャートである。
【００２６】
図３を参照すると、手順２０１ではｎの値を０に初期化する。ｎの値は現在何番目のデータを処理しているかを示す変数である（図８に示す従来技術における手順４０１と同じである）。
【００２７】
手順２０２、２０３、２０４では夫々異なるハフマン符号化表を用いて第１ハフマン符号化部３０１〜第３ハフマン符号化部３０３にてｎ番目のデータをハフマン符号化しハフマン符号を得る（図８に示す従来技術における手順４０２、４０３、４０４と同じである）
手順２０５では、符号選択部１０４にて手順２０２、２０３、２０４で得られたハフマン符号の中で最小の符号量となるハフマン符号化部を選択する。そして最小の符号量を生成するハフマン符号化手順（２０２、２０３、２０４のいずれか）を示す識別値（一例として、手順２０１なら０、手順２０２なら１、手順２０３なら２）をＣ（ｎ）とする（図８に示す従来技術における手順４０５と同じである）。
【００２８】
手順２０６では、手順２０５で選択された最小の符号量となるハフマン符号をＨ（ｎ）とする（図８に示す従来技術における手順４０６とはＨ（ｎ）を処理結果として出力しない点で異なる）。
【００２９】
手順２０７では、圧縮すべきデータが残っていれば（手順２０７にて「イエス」の場合）手順２０８へ、そうでなければ（手順２０７にて「ノ−」の場合）手順２０９へ処理を分岐する（図８に示す従来技術における手順４０７と同じである）。
【００３０】
手順２０８では、ｎを１増加し、手順２０２へ戻る（図８に示す従来技術における手順４０８と同じである）。
【００３１】
手順２０９では、識別値Ｃ（０〜ｎ）を符号化して識別符号ＣＣを生成する。その符号化手法にはランレングス符号化等を用いることができる（図８に示す従来技術における手順４０９とは識別符号ＣＣを処理結果として出力しない点で異なる）。
【００３２】
次に、図４を参照すると、手順２１０では識別符号変更部１０７にて識別値Ｃ（０〜ｎ）に変更を加え、これを識別値Ｃ’（０〜ｎ）とする。変更の加え方については後述するが、一般にはＣ’（０〜ｎ）を符号化した識別符号の符号量が少なくなるような変更を行う。例えば、識別符号の生成がランレングス符号化によって行われる場合は、識別値Ｃ’（０〜ｎ）のラン長が長くなるように（同じ識別値が多く連続するように）変更を行う。
【００３３】
手順２１１では識別値Ｃ’（０〜ｎ）が示すハフマン符号化部（１０１，１０２，１０３のいずれか）を用いて０番目からｎ番目までのデータをハフマン符号化し、生成されたハフマン符号をＨ’（０〜ｎ）とする。
【００３４】
手順２１２では、識別値Ｃ’（０〜ｎ）を手順２０９と同様な手法で符号化して識別符号ＣＣ’を生成する。
【００３５】
手順２１３では、最短符号選択部１０８にて識別符号ＣＣ’とＨ’（０〜ｎ）の合計符号量が識別符号ＣＣとＨ（０〜ｎ）の合計符号量よりも小さい場合に（手順２１３にて「イエス」の場合）手順２１４へ、そうでなければ（手順２１３にて「ノ−」の場合）手順２１５へ分岐する。手順２１３では、手順２１０での識別値の変更によって符号量削減効果が得られたかどうかを判定している。
【００３６】
手順２１４では、現時点での最小符号量を実現する識別値として、識別値Ｃ’（０〜ｎ）を識別値Ｃ（０〜ｎ）に、識別符号ＣＣ’を識別符号ＣＣに、ハフマン符号Ｈ’（０〜ｎ）をハフマン符号Ｈ（０〜ｎ）に夫々値をコピーする。
【００３７】
手順２１５では、手順２１０で行う識別値Ｃ（０〜ｎ）の変更において、他の変更候補が残っていれば（手順２１５にて「イエス」の場合）手順２１０へ戻り処理を繰り返し、他の変更候補が残っていなければ（手順２１５にて「ノ−」の場合）手順２１６へ進む。このように識別値の変更とハフマン符号化を繰り返し、最小符号量を実現する識別値を探索する。
【００３８】
手順２１６では、処理結果として識別符号ＣＣとハフマン符号Ｈ（０〜ｎ）を出力する。
【００３９】
次に、手順２１０と手順２１５について一例を挙げて説明する。例えば、データの数が５（即ち、ｎ＝４）であり、手順２０５で得られた識別値Ｃ（０〜４）が”０，１，０，１，１”であったとする。また、手順２０９と手順２１２において識別符号の生成に従来技術の説明で用いたランレングス符号化を用いるとする。すると、手順２０９が終了した時点で識別符号ＣＣの符号量は、３６ビットとなる。
【００４０】
即ち、識別値Ｃ（０〜４）が”０，１，０，１，１”だから、「０」が「１」連続、「１」が「１」連続、「０」が「１」連続、「１」が「２」連続であり、ランの数は４となる。従って、識別符号ＣＣの符号量は、９ビット×４＝３６ビットとなるのである。
【００４１】
手順２１０では上述のように識別符号ＣＣの符号量が少なくなるように識別値Ｃを変更する。ランレングス符号化においては、ランの長さを長くすることが符号量削減となる。現在の識別値Ｃ（０〜４）＝”０，１，０，１，１”は上述したように４つのランに分けられ、各々のランを長くすることで識別符号の符号長を少なくできる。
【００４２】
たとえば、最初の”０”の１連続ランを長くすると識別値Ｃ’（０〜４）は”０，０，０，１，１”となり、２つのランとなる。従って、９ビット×２＝１８ビットで符号化できる。又、２つ目のランを左方向に長くした場合は、Ｃ’（０〜４）＝”１，１，０，１，１”、右方向に長くした場合は、Ｃ’（０〜４）＝”０，１，１，１，１”、左右方向に長くした場合はＣ’（０〜４）＝”１，１，１，１，１”となる。同様に、３つ目のランを左方向に長くした場合は、Ｃ’（０〜４）＝”０，０，０，１，１”、右方向に長くした場合は、Ｃ’（０〜４）＝”０，１，０，０，１”、左右方向に長くした場合はＣ’（０〜４）＝”０，０，０，０，１”となり、４つ目のランを左方向に長くした場合は、Ｃ’（０〜４）＝”０，１，１，１，１”となる。
【００４３】
このように各ランを、左方向、右方向、左右方向に長くした場合の各々が識別値Ｃの変更候補となる。識別値Ｃを変更することで、一般にハフマン符号の符号量は増大する。しかしながら、識別符号ＣＣにおける符号量削減効果がハフマン符号量増大よりも大きい場合にデータ圧縮処理全体としての圧縮率向上が実現できる。
【００４４】
手順２１５では全てのランについて左方向、右方向、左右方向に長くした場合が既に実行されたかを判定し、変更候補が残っていれば（手順２１５にて「イエス」の場合）処理２１０へ戻る。実装方法の一例としては、各ランを最も左側のランから順に、ランを長くしたものを変更候補としていき、そして、最も右側のランを長くしたものを最後の変更候補とするという方法が考えられる。又、この手順法によって符号量削減効果が得られた場合は、さらにもう一度、最も左側のランから順に、ランを長くしたものを変更したものを変更候補とし、これを最も右側のランまで繰り返す上記手順を符号量削減効果が得られなくなるまで、もしくは予め定められた規定回数まで繰り返しても良い。
【００４５】
なお、手順２０２、２０３、２０４、２１１におけるハフマン符号化においては、実際にハフマン符号化を行わず、ハフマン符号量を求めるだけでもよい。これによって演算量削減効果が得られることがある。その場合、処理２１６で、識別値Ｃ（０〜ｎ）を用いて０番目からｎ番目までのデータをハフマン符号化してハフマン符号Ｈ（０〜ｎ）を生成する。
【００４６】
なお、手順２１０、２１５の説明では識別値Ｃの変更候補として、ランを左方向、右方向、左右方向に長くする場合の３通り全てを候補としたが、これら３つの中のいずれか１つもしくは２つのみを用いても良い。
【００４７】
次に、第２の実施の形態について説明する。第２の実施の形態は上述した手順２１５の具体例を示したものである。図４を参照すると、手順２１５では全てのランについて左方向、右方向、左右方向に長くした場合が既に実行されたか否かが判定され、変更候補が残っていれば手順２１０へ戻る。
【００４８】
実装方法の一例としては、考えられ得るランの結合の候補を全て変更候補とするというものがあるが、この方法では必要演算量が膨大となる場合がある。そこで、必要演算量が少なくて済む実装方法の一例として、各ランを最も左側のランから順に、ランを長くしたものを変更候補としていき、そして、最も右側のランを長くしたものを最後の変更候補とするという方法が考えられる。又、逆に最も右側のランから順に、ランを長くしたものを変更候補とし、最も左側のランを長くしたものを最後の変更候補とする方法も考えられる。
【００４９】
又、この手順によって符号量削減効果が得られた場合は、さらにもう一度、最も左側のランから順に、ランを長くしたものを変更候補とし、これを最も右側のランまで繰り返す上記手順を符号量削減効果が得られなくなるまで、もしくは予め定められた規定回数まで繰り返してよい。
【００５０】
この方法に沿うように図４のフローチャートを書き換えたものが図５の第２の実施の形態の動作を示すフローチャートである。なお、手順２０１〜２０９については図３のフローチャートと同様であるため説明を省略する。
【００５１】
図５を参照すると、手順２０９ａでは、現在処理の対象となっているランを表す変数をラン位置Ｒとし、その値をＣ（０）を含むラン、即ち、最も左側のランとする。
【００５２】
次に、手順２１０では、識別値Ｃ（０〜ｎ）に３種類の変更を加え、ラン位置Ｒのランを左方向に長くした識別値を識別値ＣＬ´（０〜ｎ）、右方向に長くした識別値を識別値ＣＲ´（０〜ｎ）、左右方向に長くした識別値を識別値ＣＬＲ´（０〜ｎ）とする。
【００５３】
次に、手順２１１では、識別値ＣＬ´（０〜ｎ）、ＣＲ´（０〜ｎ）、ＣＬＲ´（０〜ｎ）が示すハフマン符号化部を用いて０番目からｎ番目までのデータをハフマン符号化し、生成されたハフマン符号を各々ＨＬ´（０〜ｎ）、ＨＲ´（０〜ｎ）、ＨＬＲ´（０〜ｎ）とする。
【００５４】
次に、手順２１２では、識別値ＣＬ´（０〜ｎ）、ＣＲ´（０〜ｎ）、ＣＬＲ´（０〜ｎ）を手順２０９と同様な手法で各々符号化して識別符号ＣＣＬ´，ＣＣＲ´，ＣＣＬＲ´を生成する。又、識別符号ＣＣＬ´とハフマン符号ＨＬ´（０〜ｎ）との合計符号量と、識別符号ＣＣＲ´とハフマン符号ＨＲ´（０〜ｎ）との合計符号量と、識別符号ＣＣＬＲ´とハフマン符号ＨＬＲ´（０〜ｎ）との合計符号量とを比較し、最も少ない符号量を実現する識別符号をＣＣ´、ハフマン符号をＨ´（０〜ｎ）、識別値をＣ´（０〜ｎ）とする。例えば、識別符号ＣＣＬ´とハフマン符号ＨＬ´（０〜ｎ）との合計符号量が最小であれば、ＣＣ´＝ＣＣＬ´、Ｈ´（０〜ｎ）＝ＨＬ´（０〜ｎ）、Ｃ´（０〜ｎ）＝ＣＬ´（０〜ｎ）とする。
【００５５】
次に、手順２１３では、識別符号ＣＣ´とハフマン符号Ｈ´（０〜ｎ）との合計符号量が識別符号ＣＣとハフマン符号Ｈ（０〜ｎ）の合計符号量よりも小さい場合（手順２１３にて「イエス」の場合）に手順２１４へ進み、そうでなければ（手順２１３にて「ノ−」の場合）手順２１５へ分岐する。この手順２１３では、手順２１０での識別値の変更によって符号量削減効果が得られたか否かを判定している。
【００５６】
次に、手順２１４では、現時点での最小符号量を実現する識別値として、識別値Ｃ´（０〜ｎ）を識別値Ｃ（０〜ｎ）に、識別符号ＣＣ´を識別符号ＣＣに、ハフマン符号Ｈ´（０〜ｎ）をハフマン符号Ｈ（０〜ｎ）に夫々コピーする。
【００５７】
次に、手順２１５では、ラン位置Ｒが示すランがＣ（ｎ）を含むラン、即ち、最も右側のランであれば（手順２１５にて「イエス」の場合）手順２１６へ進み、そうでなければ（手順２１５にて「ノ−」の場合）、手順２１５ａでラン位置Ｒを一つ右隣のランへ移動して手順２１０へ戻る。
【００５８】
次に、手順２１６では、処理結果として識別符号ＣＣとハフマン符号Ｈ（０〜ｎ）とを出力する。
【００５９】
ここで、上述した手順２０９ａ以降の処理について具体的な数値を用いて説明する。一例として、手順２０９にて識別値Ｃ（０〜４）＝”０，１，０，１，１”が得られた場合について説明する。この場合、最も左側のラン（Ｒ１とする）が“０”、その右隣のラン（Ｒ２とする）が“１”、その右隣のラン（Ｒ３とする）が“０”、その右隣のラン（Ｒ４とする）が“１，１”である。
【００６０】
まず、手順２０９ａではラン位置をＲ１とする。次に、手順２１０では、ラン位置Ｒ１のランを右方向に長くする。従って、識別値ＣＲ´（０〜４）＝”０，０，０，１，１”となる。なお、ラン位置Ｒ１は左端であるためランを左方向及び左右方向に長くすることはできない。同様に、ラン位置Ｒ４は右端であるためランを右方向及び左右方向に長くすることはできない。
【００６１】
次に、手順２１１では識別値ＣＲ´（０〜４）が示すハフマン符号化部で各々入力データをハフマン符号化する。即ち、まず識別値ＣＲ´（０）＝”０”だから最初の入力データＤ１を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＲ´（０）を得る。同様に、識別値ＣＲ´（１）＝”０”だから第２の入力データＤ２を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＲ´（１）を、識別値ＣＲ´（２）＝”０”だから第３の入力データＤ３を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＲ´（２）を、識別値ＣＲ´（３）＝”１”だから第４の入力データＤ４を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（３）を、識別値ＣＲ´（４）＝”１”だから第５の入力データＤ５を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（４）を夫々得る。
【００６２】
次に、手順２１２では識別値ＣＲ´（０〜４）＝”０，０，０，１，１”から識別符号ＣＣＲ´（０〜４）を生成する。すると、識別符号ＣＣＲ´（０〜４）＝“０，３，１，２”となる。なお、ラン位置Ｒ１が左端であるため識別値ＣＬ´（０〜４）及びＣＬＲ´（０〜４）は存在しない。従って、この場合、合計符号量の比較は行わない。即ち、識別符号ＣＣＲ´（０〜４）＝“０，３，１，２”をＣＣ´とし、ハフマン符号ＨＲ´（０〜４）をＨ´（０〜４）とし、識別値ＣＲ´（０〜４）＝”０，０，０，１，１”をＣ´（０〜４）とする。
【００６３】
次に、手順２１３では識別符号ＣＣ´とハフマン符号Ｈ´との合計符号量が識別符号ＣＣとハフマン符号Ｈとの合計符号量よりも小さいか否かを判定する。この場合、識別符号ＣＣ´とハフマン符号Ｈ´との合計符号量が識別符号ＣＣとハフマン符号Ｈとの合計符号量よりも小さいものとする。そこで、手順２１４に進み、識別値Ｃ´（０〜４）を識別値Ｃ（０〜４）に、識別符号ＣＣ´（０〜４）をＣＣ（０〜４）に、ハフマン符号Ｈ´（０〜４）をハフマン符号Ｈ（０〜４）にコピーする。
【００６４】
次に、手順２１５ではラン位置Ｒ１は最も右側のランではないので、手順２１５ａへ進み、ラン位置を右隣のＲ２へ移動する。そして、手順２１０に戻る。これから先は上述の手順２１０以降の繰り返しとなる。いま、ラン位置Ｒ２の場合についてのみ説明するが、ラン位置Ｒ３，Ｒ４の場合も同様に説明できる。
【００６５】
手順２１０ではラン位置Ｒ２のランを左方向に長くする。元の識別値Ｃ（０〜４）＝”０，１，０，１，１”だから、、識別値ＣＬ´（０〜４）＝”１，１，０，１，１”となる。次に、ラン位置Ｒ２のランを右方向に長くする。すると、識別値ＣＲ´（０〜４）＝”０，１，１，１，１”となる。次に、ラン位置Ｒ２のランを左右方向に長くする。すると、識別値ＣＬＲ´（０〜４）＝”１，１，１，１，１”となる。
【００６６】
次に、手順２１１では識別値ＣＬ´（０〜４）が示すハフマン符号化部で各々入力データをハフマン符号化する。即ち、まず識別値ＣＬ´（０）＝”１”だから最初の入力データＤ１を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬ´（０）を得る。同様に、識別値ＣＬ´（１）＝”１”だから第２の入力データＤ２を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬ´（１）を、識別値ＣＬ´（２）＝”０”だから第３の入力データＤ３を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＬ´（２）を、識別値ＣＬ´（３）＝”１”だから第４の入力データＤ４を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬ´（３）を、識別値ＣＬ´（４）＝”１”だから第５の入力データＤ５を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬ´（４）を夫々得る。
【００６７】
同様に、識別値ＣＲ´（０〜４）が示すハフマン符号化部で各々入力データをハフマン符号化する。即ち、まず識別値ＣＲ´（０）＝”０”だから最初の入力データＤ１を第１のハフマン符号化部１０１で符号化しハフマン符号ＨＲ´（０）を得る。同様に、識別値ＣＲ´（１）＝”１”だから第２の入力データＤ２を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（１）を、識別値ＣＲ´（２）＝”１”だから第３の入力データＤ３を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（２）を、識別値ＣＲ´（３）＝”１”だから第４の入力データＤ４を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（３）を、識別値ＣＲ´（４）＝”１”だから第５の入力データＤ５を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＲ´（４）を夫々得る。
【００６８】
同様に、識別値ＣＬＲ´（０〜４）が示すハフマン符号化部で各々入力データをハフマン符号化する。即ち、まず識別値ＣＬＲ´（０）＝”１”だから最初の入力データＤ１を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（０）を得る。同様に、識別値ＣＬＲ´（１）＝”１”だから第２の入力データＤ２を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（１）を、識別値ＣＬＲ´（２）＝”１”だから第３の入力データＤ３を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（２）を、識別値ＣＬＲ´（３）＝”１”だから第４の入力データＤ４を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（３）を、識別値ＣＬＲ´（４）＝”１”だから第５の入力データＤ５を第２のハフマン符号化部１０２で符号化しハフマン符号ＨＬＲ´（４）を夫々得る。
【００６９】
次に、手順２１２では識別値ＣＬ´（０〜４），ＣＲ´（０〜４），ＣＬＲ´（０〜４）から識別符号ＣＣＬ´，ＣＣＲ´，ＣＣＬＲ´を生成する。すると、識別符号ＣＣＬ´＝“１，２，０，１，１，２”、識別符号ＣＣＲ´＝“０，１，１，４”、識別符号ＣＣＬＲ´＝“１，５”となる。
【００７０】
次に、識別符号ＣＣＬ´とハフマン符号ＨＲ´（０〜４）との合計符号量と、識別符号ＣＣＲ´とハフマン符号ＨＲ´（０〜４）との合計符号量と、識別符号ＣＬＲ´とハフマン符号ＨＬＲ´（０〜４）との合計符号量とを比較し、最も少ない符号量を実現する識別符号をＣＣ´、ハフマン符号をＨ´（０〜４）、識別値をＣ´（０〜４）とする。
【００７１】
そして、上述したのと同様の手順で手順２１３，２１４を実行し，手順２１５でラン位置Ｒ２は最も右側のランではないので、手順２１５ａへ進み、ラン位置を右隣のＲ３へ移動する。そして、手順２１０に戻る。以下、ラン位置Ｒ２について行ったのと同様の手順をラン位置Ｒ２及びＲ３について実行する。
【００７２】
次に、第３の実施の形態について説明する。第３の実施の形態はデータ圧縮方法の制御プログラムを記録した記録媒体に関するものである。図６は記録媒体及び記録媒体駆動装置の一例の構成図である。同図を参照すると、記録媒体駆動装置は、前述した制御部（図１参照）１０６と、入力部１１０と、記憶部１１１とから構成され、制御部１０６が前述したハフマン符号化部１０１，１０２，１０３と、符号選択部１０４と、再符号化部１０５と（図１参照）を制御する。一方、記録媒体１１２には図３〜図５にフローチャートで示した制御プログラムが記録されている。
【００７３】
次に、記録媒体駆動装置の動作について説明する。まず、入力部１１０から制御部１０６に対し記録媒体１１２の制御プログラムの入力命令が出されると、制御部１０６は記録媒体１１２から制御プログラムを読み込み、記憶部１１に格納する。次に、入力部１１０から制御部１０６に対し制御プログラムの実行命令が出されると、制御部１０６は記憶部１１から制御プログラムを読出し、その制御プログラムに従ってハフマン符号化部１０１，１０２，１０３と、符号選択部１０４と、再符号化部１０５とを制御する。その制御内容については既に述べたので説明を省略する。
【００７４】
【発明の効果】
本発明による第１の発明によれば、順次入力されるデータを夫々異なる手法で符号化する複数のデータ符号化手段と、前記各データ符号化手段で得られた符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った前記データ符号化手段の識別値の履歴を符号化した識別符号を出力する符号選択手段とを含むデータ圧縮装置であって、その装置は前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記データ符号化手段を再選択し再符号化を行う再符号化手段を含むため、符号量を従来技術よりも低減することが可能となる。
【００７５】
即ち、識別符号の符号量が少なくなるような変更とその時の符号量計算を繰り返し行い、識別符号とハフマン符号の合計符号量がより小さくなるように構成されているため、より高い圧縮率でデータ圧縮することができる。又、第２及び第３の発明も第１の発明と同様の効果を奏する。
【図面の簡単な説明】
【図１】本発明に係るデータ圧縮装置の第１の実施の形態の構成図である。
【図２】同データ圧縮装置の再符号化部１０５の構成図である。
【図３】本発明に係るデータ圧縮装置の第１の実施の形態の動作を示すフロ−チャートである。
【図４】本発明に係るデータ圧縮装置の第１の実施の形態の動作を示すフロ−チャートである。
【図５】第２の実施の形態の動作を示すフローチャートである。
【図６】記録媒体及び記録媒体駆動装置の一例の構成図である。
【図７】従来のデータ圧縮装置の一例の構成図である。
【図８】従来のデータ圧縮装置の動作を示すフローチャートである。
【符号の説明】
１０１〜１０３ 第１〜第３ハフマン符号化部
１０４ 符号選択部
１０５ 再符号化部
１０６ 制御部
１０７ 識別符号変更部
１０８ 最短符号選択部
１１２ 記録媒体
Claims (28)
- 順次入力されるデータを夫々異なる手法で符号化する複数のデータ符号化手段と、前記各データ符号化手段で得られた符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った前記データ符号化手段の識別値の履歴を符号化した識別符号を出力する符号選択手段とを含むデータ圧縮装置であって、
前記符号選択手段から出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記データ符号化手段を再選択し再符号化を行う再符号化手段を含むことを特徴とするデータ圧縮装置。 - 前記再符号化手段は前記識別符号の符号量がより小さくなるように前記識別値の履歴を変更することを特徴とする請求項１記載のデータ圧縮装置。
- 前記識別符号は前記識別値の履歴をランレングス符号化することにより得られることを特徴とする請求項１又は２記載のデータ圧縮装置。
- 前記再符号化手段は前記変更後の識別値に対応する符号化部で再符号化した符号と前記変更後の識別値の履歴を符号化した識別符号の合計符号量と、識別値変更前の合計符号量とを比較し、前記変更後の合計符号量が前記変更前の合計符号量よりも小さい場合に前記変更後の識別符号及び符号を出力することを特徴とする請求項１から３いずれかに記載のデータ圧縮装置。
- 前記再符号化手段を複数用いることにより、前記合計符号量をさらに削減することを特徴とする請求項４記載のデータ圧縮装置。
- 前記識別符号の符号量は前記識別値のラン長が長くなるように制御されることを特徴とする請求項３から５いずれかに記載のデータ圧縮装置。
- 前記再符号化手段は前記識別値の履歴から得られる複数のランの各々についてラン長が長くなるように前記識別値を変更し、その変更後の前記識別値で選択された前記データ符号化手段にて再符号化を行うことを特徴とする請求項３から６いずれかに記載のデータ圧縮装置。
- 順次入力されるデータを夫々異なる手法で符号化するデータ符号化手順と、前記異なる手法で符号化された符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った手法の識別値の履歴を符号化した識別符号を出力する符号選択手順とを含むデータ圧縮方法であって、
前記符号選択手順によって出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記手法を再選択し再符号化を行う再符号化手順を含むことを特徴とするデータ圧縮方法。 - 前記再符号化手順は前記識別符号の符号量がより小さくなるように前記識別値の履歴を変更することを特徴とする請求項８記載のデータ圧縮方法。
- 前記識別符号は前記識別値の履歴をランレングス符号化することにより得られることを特徴とする請求項８又は９記載のデータ圧縮方法。
- 前記再符号化手順は前記変更後の識別値に対応する手法で再符号化した符号と前記変更後の識別値の履歴を符号化した識別符号の合計符号量と、識別値変更前の合計符号量とを比較し、前記変更後の合計符号量が前記変更前の合計符号量よりも小さい場合に前記変更後の識別符号及び符号を出力することを特徴とする請求項８から１０いずれかに記載のデータ圧縮方法。
- 前記再符号化手順を複数用いることにより、前記合計符号量をさらに削減することを特徴とする請求項１１記載のデータ圧縮方法。
- 前記識別符号の符号量は前記識別値のラン長が長くなるように制御されることを特徴とする請求項１０から１２いずれかに記載のデータ圧縮方法。
- 前記再符号化手順は前記識別値の履歴から得られる複数のランの各々についてラン長が長くなるように前記識別値を変更し、その変更後の前記識別値で選択された手法にて再符号化を行うことを特徴とする請求項１０から１３いずれかに記載のデータ圧縮方法。
- 順次入力されるデータを夫々異なる手法で符号化するデータ符号化手順と、前記異なる手法で符号化された符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った手法の識別値の履歴を符号化した識別符号を出力する符号選択手順とをコンピュータに実行させるための制御プログラムを記録した記録媒体であって、
前記制御プログラムは前記符号選択手順によって出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記手法を再選択し再符号化を行う再符号化手順を含むことを特徴とする記録媒体。 - 前記再符号化手順は前記識別符号の符号量がより小さくなるように前記識別値の履歴を変更することを特徴とする請求項１５記載の記録媒体。
- 前記識別符号は前記識別値の履歴をランレングス符号化することにより得られることを特徴とする請求項１５又は１６記載の記録媒体。
- 前記再符号化手順は前記変更後の識別値に対応する手法で再符号化した符号と前記変更後の識別値の履歴を符号化した識別符号の合計符号量と、識別値変更前の合計符号量とを比較し、前記変更後の合計符号量が前記変更前の合計符号量よりも小さい場合に前記変更後の識別符号及び符号を出力することを特徴とする請求項１５から１７いずれかに記載の記録媒体。
- 前記再符号化手順を複数用いることにより、前記合計符号量をさらに削減することを特徴とする請求項１８記載の記録媒体。
- 前記識別符号の符号量は前記識別値のラン長が長くなるように制御されることを特徴とする請求項１７から１９いずれかに記載の記録媒体。
- 前記再符号化手順は前記識別値の履歴から得られる複数のランの各々についてラン長が長くなるように前記識別値を変更し、その変更後の前記識別値で選択された手法にて再符号化を行うことを特徴とする請求項１７から２０いずれかに記載の記録媒体。
- 順次入力されるデータを夫々異なる手法で符号化する複数のデータ符号化手段と、前記各データ符号化手段で得られた符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った前記データ符号化手段の識別値の履歴を符号化した識別符号を出力する符号選択手段とを含むデータ圧縮装置であって、
前記符号選択手段から出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記データ符号化手段を再選択し再符号化を行う再符号化手段を含んでおり、
前記識別符号は前記識別値の履歴をランレングス符号化することにより得られ、かつ前記再符号化手段は複数のランの各々についてラン長が長くなるように前記識別値を変更し、その変更後の前記識別値で選択された前記データ符号化手段にて再符号化を行うことを特徴とするデータ圧縮装置。 - 前記再符号化手段は、各ランを最も左側のランから順に、ランを長くしたものを変更候補としていき、最も右側のランを長くしたものを最後の変更候補とすることを特徴とする請求項２２記載のデータ圧縮装置。
- 順次入力されるデータを夫々異なる手法で符号化するデータ符号化手順と、前記異なる手法で符号化された符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った手法の識別値の履歴を符号化した識別符号を出力する符号選択手順とを含むデータ圧縮方法であって、
前記符号選択手順によって出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記手法を再選択し再符号化を行う再符号化手順を含んでおり、
前記識別符号は前記識別値の履歴をランレングス符号化することにより得られ、かつ前記再符号化手順は複数のランの各々についてラン長が長くなるように前記識別値を変更し、その変更後の前記識別値で選択された手法にて再符号化を行うことを特徴とするデータ圧縮方法。 - 前記再符号化手順は、各ランを最も左側のランから順に、ランを長くしたものを変更候補としていき、最も右側のランを長くしたものを最後の変更候補とすることを特徴とする請求項２４記載のデータ圧縮方法。
- 順次入力されるデータを夫々異なる手法で符号化するデータ符号化手順と、前記異なる手法で符号化された符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った手法の識別値の履歴を符号化した識別符号を出力する符号選択手順とをコンピュータに実行させるための制御プログラムを記録した記録媒体であって、
前記制御プログラムは前記符号選択手順によって出力された前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記手法を再選択し再符号化を行う再符号化手順を含んでおり、
前記識別符号は前記識別値の履歴をランレングス符号化することにより得られ、かつ前記再符号化手順は複数のランの各々についてラン長が長くなるように前記識別値を変更し、その変更後の前記識別値で選択された手法にて再符号化を行うことを特徴とする記録媒体。 - 前記再符号化手順は、各ランを最も左側のランから順に、ランを長くしたものを変更候補としていき、最も右側のランを長くしたものを最後の変更候補とすることを特徴とする請求項２６記載の記録媒体。
- 順次入力されるデータを夫々異なる手法で符号化する複数のデータ符号化手順と、前記各データ符号化手順で得られた符号のうち最短符号を選択し、その最短符号及びその最短符号化を行った前記データ符号化手順の識別値の履歴を符号化した識別符号を出力する符号選択手順と、前記識別符号と前記最短符号の合計符号量がより小さくなるように前記識別値を変更して前記データ符号化手順を再選択し再符号化を行う再符号化手順とをコンピュータに実行させるための制御プログラムを記録した記録媒体。
Priority Applications (7)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000396450A JP3580251B2 (ja) | 2000-12-27 | 2000-12-27 | データ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体 |
| KR10-2001-0085136A KR100472040B1 (ko) | 2000-12-27 | 2001-12-26 | 데이터압축방법 및 장치, 데이터압축을 제어하기 위한제어프로그램을 저장한 컴퓨터로 읽을 수 있는 기록매체 |
| US10/033,088 US6940900B2 (en) | 2000-12-27 | 2001-12-27 | Data compression, control program for controlling the data compression |
| DE2001631359 DE60131359T2 (de) | 2000-12-27 | 2001-12-27 | Datenkomprimierung und dazugehöriges Kontrollverfahren |
| SG200108096A SG102024A1 (en) | 2000-12-27 | 2001-12-27 | Data compression, control program for controlling the data compression |
| EP20010130919 EP1223677B1 (en) | 2000-12-27 | 2001-12-27 | Data compression and related control method |
| CA 2366349 CA2366349C (en) | 2000-12-27 | 2001-12-27 | Data compression, control program for controlling the data compression |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000396450A JP3580251B2 (ja) | 2000-12-27 | 2000-12-27 | データ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2002198822A JP2002198822A (ja) | 2002-07-12 |
| JP3580251B2 true JP3580251B2 (ja) | 2004-10-20 |
Family
ID=18861735
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000396450A Expired - Fee Related JP3580251B2 (ja) | 2000-12-27 | 2000-12-27 | データ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体 |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US6940900B2 (ja) |
| EP (1) | EP1223677B1 (ja) |
| JP (1) | JP3580251B2 (ja) |
| KR (1) | KR100472040B1 (ja) |
| CA (1) | CA2366349C (ja) |
| DE (1) | DE60131359T2 (ja) |
| SG (1) | SG102024A1 (ja) |
Families Citing this family (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DK1400954T3 (da) | 2002-09-04 | 2008-03-31 | Microsoft Corp | Entropi-kodning ved tilpasning af kodning mellem niveau- og runlængde/niveau-moduser |
| JP4728568B2 (ja) * | 2002-09-04 | 2011-07-20 | マイクロソフト コーポレーション | レベル・モードとラン・レングス／レベル・モードの間での符号化を適応させるエントロピー符号化 |
| US20060126718A1 (en) * | 2002-10-01 | 2006-06-15 | Avocent Corporation | Video compression encoder |
| US7321623B2 (en) * | 2002-10-01 | 2008-01-22 | Avocent Corporation | Video compression system |
| US9560371B2 (en) | 2003-07-30 | 2017-01-31 | Avocent Corporation | Video compression system |
| KR100513061B1 (ko) * | 2003-10-01 | 2005-09-05 | 주식회사 팬택 | 카메라 영상 압축 방법 |
| CN1954611A (zh) * | 2004-04-09 | 2007-04-25 | 诺基亚公司 | 压缩图像数据文件的生成方法，图像数据压缩装置及摄影装置 |
| US7006700B2 (en) * | 2004-06-25 | 2006-02-28 | Avocent Corporation | Digital video compression command priority |
| US7457461B2 (en) * | 2004-06-25 | 2008-11-25 | Avocent Corporation | Video compression noise immunity |
| KR100731640B1 (ko) * | 2005-12-23 | 2007-06-22 | 주식회사 텔레칩스 | 비트스트림 처리기 |
| US7555570B2 (en) | 2006-02-17 | 2009-06-30 | Avocent Huntsville Corporation | Device and method for configuring a target device |
| US8718147B2 (en) * | 2006-02-17 | 2014-05-06 | Avocent Huntsville Corporation | Video compression algorithm |
| BRPI0708267A2 (pt) | 2006-02-24 | 2011-05-24 | France Telecom | método de codificação binária de ìndices de quantificação de um envelope de sinal, método de decodificação de um envelope de sinal, e módulos de codificação e decodificação correspondentes |
| US7782961B2 (en) * | 2006-04-28 | 2010-08-24 | Avocent Corporation | DVC delta commands |
| EP2014026B1 (fr) * | 2006-04-28 | 2011-07-27 | France Telecom | Procede de transmission d'une pluralite de champs identificateurs dans un reseau a commutation de paquets |
| KR100847077B1 (ko) | 2006-08-02 | 2008-07-17 | 엠텍비젼 주식회사 | 허프만 부호화 방법 및 이를 구현하기 위한 프로그램이기록된 기록 매체 |
| JP4781198B2 (ja) * | 2006-08-08 | 2011-09-28 | キヤノン株式会社 | 画像処理装置及び方法、並びに、コンピュータプログラム及びコンピュータ可読記憶媒体 |
| US8179974B2 (en) | 2008-05-02 | 2012-05-15 | Microsoft Corporation | Multi-level representation of reordered transform coefficients |
| US8321326B2 (en) | 2009-09-15 | 2012-11-27 | Auerbach Group Llc | Method and system for enhancing the efficiency of a digitally communicated data exchange |
| DE102009046096A1 (de) | 2009-10-28 | 2011-05-05 | Robert Bosch Gmbh | Alarmeinrichtung zur Erkennung und Mitteilung von umgebungs- und anlagenspezifischen Zuständen |
| US9673836B1 (en) * | 2016-09-23 | 2017-06-06 | International Business Machines Corporation | System level testing of entropy encoding |
| CN116170027B (zh) * | 2023-04-26 | 2023-07-25 | 北京索斯克科技开发有限公司 | 一种毒检设备数据管理系统及处理方法 |
Family Cites Families (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63117564A (ja) * | 1986-11-05 | 1988-05-21 | Mitsubishi Electric Corp | ハフマン符号化装置 |
| JPH0773249B2 (ja) * | 1989-06-29 | 1995-08-02 | 富士通株式会社 | 音声符号化・復号化伝送方式 |
| US5255090A (en) * | 1991-11-19 | 1993-10-19 | Scientific-Atlanta, Inc. | Progressive transmission of vector quantized data |
| JPH05199421A (ja) * | 1992-01-20 | 1993-08-06 | Fujitsu General Ltd | 画像伝送方法 |
| GB2274038B (en) * | 1992-12-22 | 1996-10-02 | Sony Broadcast & Communication | Data compression |
| GB2274956B (en) | 1993-02-05 | 1997-04-02 | Sony Broadcast & Communication | Image data compression |
| JPH06311369A (ja) * | 1993-04-21 | 1994-11-04 | Tokyo Electric Co Ltd | 画像符号化装置 |
| US5566001A (en) * | 1994-07-27 | 1996-10-15 | Motorola, Inc. | Method and apparatus for fax messaging in a selective call receiver system using multiple code-book data compression |
| KR100209877B1 (ko) * | 1994-11-26 | 1999-07-15 | 윤종용 | 복수개의 허프만부호테이블을 이용한 가변장부호화장치 및 복호화장치 |
| JP2951861B2 (ja) | 1994-12-28 | 1999-09-20 | シャープ株式会社 | 画像符号化装置及び画像復号装置 |
| US5825830A (en) * | 1995-08-17 | 1998-10-20 | Kopf; David A. | Method and apparatus for the compression of audio, video or other data |
| JPH10105372A (ja) | 1996-10-02 | 1998-04-24 | Oki Data:Kk | データ列の圧縮装置及び圧縮方法 |
| GB2321577B (en) | 1997-01-27 | 2001-08-01 | British Broadcasting Corp | Audio compression |
| KR100295802B1 (ko) * | 1998-07-25 | 2001-10-26 | 구자홍 | 복수의가변장부호화테이블을이용한영상데이터압축장치 |
| JP3323175B2 (ja) * | 1999-04-20 | 2002-09-09 | 松下電器産業株式会社 | 符号化装置 |
-
2000
- 2000-12-27 JP JP2000396450A patent/JP3580251B2/ja not_active Expired - Fee Related
-
2001
- 2001-12-26 KR KR10-2001-0085136A patent/KR100472040B1/ko not_active Expired - Fee Related
- 2001-12-27 SG SG200108096A patent/SG102024A1/en unknown
- 2001-12-27 EP EP20010130919 patent/EP1223677B1/en not_active Expired - Lifetime
- 2001-12-27 US US10/033,088 patent/US6940900B2/en not_active Expired - Fee Related
- 2001-12-27 DE DE2001631359 patent/DE60131359T2/de not_active Expired - Lifetime
- 2001-12-27 CA CA 2366349 patent/CA2366349C/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| EP1223677B1 (en) | 2007-11-14 |
| US20020080872A1 (en) | 2002-06-27 |
| EP1223677A2 (en) | 2002-07-17 |
| JP2002198822A (ja) | 2002-07-12 |
| KR20020053754A (ko) | 2002-07-05 |
| CA2366349A1 (en) | 2002-06-27 |
| DE60131359T2 (de) | 2008-09-11 |
| SG102024A1 (en) | 2004-02-27 |
| KR100472040B1 (ko) | 2005-03-08 |
| DE60131359D1 (de) | 2007-12-27 |
| EP1223677A3 (en) | 2003-12-10 |
| CA2366349C (en) | 2005-09-20 |
| US6940900B2 (en) | 2005-09-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2002198822A (ja) | データ圧縮装置及び圧縮方法並びにその制御プログラムを記録した記録媒体 | |
| JP5221047B2 (ja) | 圧縮率の向上のために改善されたコンテキストモデル選択を使用するｃａｂａｃ符号化方法及び装置、並びにｃａｂａｃ復号化方法及び装置 | |
| JP2007531460A (ja) | 縮小サイズまたはフルサイズでの再生を動的に選択的に行うための複数の独立した符号化チェーンを備えるビデオ符号化システム | |
| JP4442891B2 (ja) | 可変長符号化装置及び可変長符号化方法 | |
| KR20260019670A (ko) | 범위 비대칭 숫자 시스템 인코딩 및 디코딩의 피쳐 | |
| JP5570409B2 (ja) | データ圧縮装置及びデータ圧縮方法及びデータ圧縮プログラム | |
| CN101009837B (zh) | 将位置内插器编码到比特流中的方法 | |
| JP4785706B2 (ja) | 復号装置及び復号方法 | |
| JP5095033B2 (ja) | データ圧縮装置及びデータ圧縮方法及びプログラム | |
| JP2006197610A (ja) | 内容適応可変長符号化装置及び方法 | |
| JP7361838B2 (ja) | 映像符号化装置、映像復号装置、及びこれらのプログラム | |
| JP2001326935A (ja) | 画像符号／復号方法及びその装置並びにそのプログラムを記録した記録媒体 | |
| JP4524501B2 (ja) | 符号化システム、符号化方法、符号化プログラム、復号化システム、復号化方法および復号化プログラム | |
| JP4079965B2 (ja) | 復号化システム | |
| WO2018135520A1 (ja) | 量子化装置、量子化方法および記録媒体 | |
| JP4575344B2 (ja) | 縮小サイズまたはフルサイズでの再生を動的に選択的に行うための複数の独立した符号化チェーンを備えるビデオ符号化システム | |
| JP2005123913A (ja) | 解像度変換用フィルタ係数決定方法，画像解像度変換方法，画像解像度変換装置，映像再符号化方法，映像再符号化装置，解像度変換用フィルタ係数決定プログラム，画像解像度変換プログラム，映像再符号化プログラムおよびそれらのプログラムを記録した記録媒体 | |
| CN100414996C (zh) | 用于编码和解码关键字数据的装置和方法 | |
| JP5244479B2 (ja) | 画像符号化装置及び画像符号化方法 | |
| JP4319895B2 (ja) | 時系列信号の符号化装置 | |
| JP4775026B2 (ja) | 符号本選択方法及び符号本選択装置 | |
| JP4053949B2 (ja) | 画像符号化方法，画像復号方法，画像符号化装置，画像復号装置，それらのプログラムおよびそれらのプログラム記録媒体 | |
| TWI260611B (en) | Encoding method of recording media | |
| JP2024152413A (ja) | メッシュ復号装置、メッシュ復号方法及びプログラム | |
| JP5553533B2 (ja) | 画像編集装置およびその制御方法およびプログラム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040413 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040614 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040629 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040712 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070730 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080730 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090730 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100730 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110730 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110730 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120730 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120730 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130730 Year of fee payment: 9 |
|
| LAPS | Cancellation because of no payment of annual fees |