データ圧縮
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/26 14:59 UTC 版)
アナログ帯域圧縮
代表的なものとして、TV放送に用いられるNTSC、PALなどのコンポジット映像信号がある。コンポジット映像信号では、映像信号を輝度成分と色成分に分離した後、輝度成分に対しては十分な帯域幅を与えているのに対し、色成分についてはそれと比べ帯域幅を狭くしている。結果として元の画質と比較すると、色彩の細かい変化が失われた、例を上げるなら黒白写真に着色したものに近いような画質になっているはずだが、人間の視覚の特性上、通常のいわゆる「自然画」や、いわゆるアニメ絵でも縁の黒い線の輝度成分に助けられ、あまり気にならない（また画質が気になるような、静止している映像に対しては三次元Y/C分離によって高画質な再生が可能である）。しかしゲーム画面やCGのような、隣接する場所の色彩が極端に変化する動画ではいわゆる「色滲み」が避けられない。
中波～短波のAMラジオ放送では、占有帯域をあまり広くしないように、4kHz程度から上を切っている。電話においても効率よく多重化するため、電話は300 Hz - 3600 Hz程度が伝われば良いので、その範囲以外を切っている。
他に、以前は電話の交換機と交換機の間をPAM（パルス振幅変調）方式を使い0.125μsに分割することで、信号を多重化して送っていた。後にPAM方式からPCM（パルス符号変調）方式へ変わり、事実上デジタル方式に変わっている。
デジタル圧縮
デジタル圧縮の歴史
デジタル符号化されたデータの圧縮の歴史は意外と古く、1830年代に発明されたモールス信号に用いられるモールス符号も圧縮符号の一種である。これは、文字通信の中で比較的出現頻度の高いアルファベットに短い符号を割り当て、出現頻度の低いものには長い符号を割り当てることで、通信に要する手間を省いている。（しかし日本語のモールス符号はそうなっていない。モールス信号の項目を参照）
1967年、音響心理学的マスキング効果が発表されている[13]。
その後、コンピュータの発達とともに、デジタル通信やファイルの保存でデータ圧縮の重要性が高まったことで研究が進み、1970年代後半頃からはデータ圧縮の要素技術に関する重要な特許も出願されるようになった。特許については、近年でも、オーディオ圧縮で用いられるMP3のライセンスの問題や、ウェブサイトの画像で広く用いられている GIF画像のライセンス問題など多くの紛争を発生させており、それだけデジタル時代の重要な基幹技術であることを示している。
1980年代に入ると音声通信分野のデジタル化の動きが始まり、音声圧縮の分野ではADPCMなど初期の比較的単純な圧縮方式が実用化された[14]。また、パーソナルコンピュータやパソコン通信（ただし、日本では通信自由化以降）が普及するようになり、オンラインソフトウェアの分野からもZIPやLHAといった現在も幅広く使用されているファイル圧縮方式も誕生した。1988年、ブエノスアイレス大学の Oscar Bonello が IBM PC を使ったラジオ放送局用自動音声圧縮システムを開発した[15]。
1990年代前半に入ると、音声圧縮や画像圧縮の分野で2005年現在でも広く知られている多くのデータ圧縮方式が発表された。音声（オーディオ）の分野では、1992年に登場したミニディスク (MD) に搭載されているATRACなどがある。また、画像の分野ではJPEG圧縮方式が国際標準規格として勧告され、広く普及した。これらの背景には、集積回路 (IC) の生産技術や設計技術の発達で大規模で高度な処理が行えるICが比較的安価な製品でも搭載可能になった点や、パーソナルコンピュータの急速な性能向上でソフトウェア的な画像処理が容易に行えるようになった点も大きい。
また、動画圧縮の分野でも、この頃、TV会議システム用の動画圧縮方式 (H.261) やビデオCDの圧縮方式 (MPEG-1) も標準化されている。また、パーソナルコンピュータ向けに企業独自の圧縮方式を採用したコーデックも登場するようになった。しかし、動画圧縮の分野では音声圧縮や画像圧縮に比べてさらに高度な技術が要求されるため、まだしばらくの間、業務用や限定的な用途に限られていた。これとは別に、デジタル時代の重要な基幹技術である動画圧縮技術には特許の権益に絡む思惑もあり、この方面でも標準化までに長い時間を要した。
1990年代後半になると、動画圧縮の分野でも国際的な標準規格であるMPEG-2が標準化され、業務用分野から幅広く利用されるようになり、1996年に登場したDVDプレーヤーや、2000年に開始されたBSデジタル放送など、家電製品にも採用されるようになった。
ファイル圧縮
静止画像圧縮
代表的なものとしては、インターネットのウェブサイトで広く用いられるJPEG、GIFがある。非可逆圧縮による高能率圧縮を行うものと、劣化を生じさせない可逆圧縮を用いるものがある。
例えば、非可逆圧縮形式のJPEGの場合、一定の画素数のブロックに分割したデータを離散コサイン変換 (Discrete Cosine Transform, DCT) と呼ばれる演算で処理して符号化を行う。
画像圧縮アルゴリズムの評価には、レナなどの画像サンプルが広く使われている。
音声圧縮
音声圧縮では、人の聴覚の特性を利用して高能率の非可逆圧縮を行うものが広く用いられている。非可逆圧縮の代表的な方式としてMP3がある。CDの音声データ (1411.2kbps: 44.1kHz, 16bit, 2ch) を128kbpsのMP3形式に圧縮した場合、圧縮率は約1/11となる。最近では高音質の320kbpsの圧縮率が一般的になりつつある。
一方で、まったく劣化を生じさせない可逆圧縮方式を用いたものも増えてきている。 ALAC、FLAC、Monkey's Audio(APE)などがその代表である。
動画圧縮
動画圧縮では、各フレームの静止画の圧縮と時系列の圧縮技法（動きベクトル、フレーム間予測、動き補償など）を組み合わせて行う[16]。通常動画データには同期した音声も付属しているため、動画圧縮のコーデックは音声圧縮用コーデックを統合してパッケージ化されていることが多い[17]。
動画圧縮アルゴリズムのほとんどが非可逆圧縮である。圧縮前の動画はあまりにも多大なデータとなり、ストリーミングに際しても巨大な帯域幅を必要とする。可逆な動画用コーデックの圧縮性能は平均で3倍程度だが、非可逆なMPEG-4の圧縮性能は20倍から200倍である[18]。非可逆圧縮では、画質、圧縮・伸長のコスト、要求されるシステム性能といったトレードオフが考慮される。圧縮率が高すぎるとブロックノイズなどの圧縮アーティファクトが生じることがある。
動画圧縮では一般に四角い範囲の隣接するピクセル群をグループとして扱い、これをマクロブロックと呼ぶ。このブロックを次のフレームの同じ位置のブロックと比較し、差分のみをデータとして送る。そのため、動きが激しい動画では差分が大きくなり、より多くのデータを符号化しなければならなくなる。したがって固定ビットレートでは、爆発シーン、炎のシーン、動物の群れ、視点（カメラ）の平行移動などで画質が低下することがあり、可変ビットレートではデータ転送量が増加する。
符号化理論
動画データは、一連の静止画フレームからなっている。このフレーム列には空間的にも時間的にも冗長性があり、動画圧縮アルゴリズムはそれを除去することで全体のサイズを小さくしようとする。隣接するフレームは相互によく似ていることが多く、フレーム間の差分だけを格納することでこれを利用する。また、ヒトの目は色の変化には鈍感で輝度の変化には敏感である。そこで、静止画圧縮のJPEGのようにフレーム内の似たような色が並んでいる領域を平均化するような圧縮を行う[19]。これらの技法には本質的に非可逆なものと原本の情報を保持する可逆なものがある。
フレーム間圧縮では、フレーム列を前後で比較したとき、全く変化しない領域があれば、前のフレームの同じ領域をそのままコピーせよというコマンドを生成する。領域が単純に変化している場合、シフト、回転、明るくする、暗くするなどのコマンドを生成する。このようにコマンド列を生成した方が各フレームを静止画として圧縮するよりサイズが小さくなる。このようなフレームをまたいだ圧縮は単純に再生する用途では問題ないが、圧縮された動画を編集したい場合には問題となることがある[20]。
フレーム間圧縮を行うと、フレームからフレームにデータをコピーしていくことになるため、大本となるフレームが消されると（転送に失敗すると）その後のフレーム列を正しく再生できなくなる。DVのようなデジタルビデオ規格では、フレーム毎の圧縮しか行わない。その場合は編集で一部をカットするのが容易である。フレーム毎の圧縮しか行わない場合、各フレームのデータ量はほぼ同じになる。フレーム間圧縮システムでは、あるフレーム（MPEG-2では「Iフレーム」と呼ぶ）は他のフレームからデータをコピーせずに再現できるフレームでフレーム間圧縮の起点となっているため、前後の他のフレームより多くのデータを含んでいる[21]。
フレーム間圧縮を施した動画データの編集はフレーム毎の圧縮のみの場合よりはるかにコンピュータの性能を要求するが、例えばHDVなどの規格ではMPEG-2データのノンリニア編集が可能である。
2013年現在、主に使われている動画圧縮技法（例えば、ITU-TまたはISOが規格として承認したもの）は、空間的冗長性の削減に離散コサイン変換 (DCT) を採用しているものが多い。この技法は1974年、N. Ahmed、T. Natarajan、K. R. Rao が導入した[22]。他の技法としてはフラクタル圧縮や matching pursuit がある。研究段階では離散ウェーブレット変換 (DWT) も使われているが、製品としては実用化されていない（静止画圧縮では使用している例がある）。フラクタル圧縮は最近の研究の進展で比較的有効性が低いとされ、人気が衰えている[16]。
動画圧縮規格の年表
| 年 | 規格 | 策定者 | 主な実装・用途 |
|---|---|---|---|
| 1984 | H.120 | ITU-T | |
| 1990 | H.261 | ITU-T | テレビ会議、テレビ電話 |
| 1993 | MPEG-1 Part 2 | ISO、IEC | ビデオCD |
| 1995 | MPEG-2 Part 2 | ISO、IEC、ITU-T | DVD-Video、Blu-ray、DVB、SVCD |
| 1996 | H.263 | ITU-T | テレビ会議、テレビ電話、携帯電話での動画再生 (3GP) |
| 1999 | MPEG-4 Part 2 | ISO、IEC | 第3世代携帯電話、インターネット上の動画 (DivX, Xvid ...) |
| 2003 | H.264/MPEG-4 AVC | ソニー、パナソニック、サムスン、ISO、IEC、ITU-T | Blu-ray、HD DVD DVB、iPod Video、Apple TV、ワンセグ |
| 2008 | VC-2 (Dirac) | ISO | インターネット上の動画、HDTV放送、UHDTV |
| 2013 | H.265/HEVC | ISO、IEC、ITU-T | UHD（スーパーハイビジョン） |
遺伝学
塩基配列データの圧縮は可逆圧縮の新たな用途であり、データの特性に適応させた一般的な圧縮アルゴリズムと遺伝学的なアルゴリズムが使われている。2012年、ジョンズ・ホプキンス大学のチームは特定の外部の配列データベースに依存しない世界初の遺伝子圧縮アルゴリズムを発表した。HAPZIPPERは HapMap 向けに作られており、20分の1に圧縮（ファイルサイズを95%削減）できる。これは、一般的圧縮ユーティリティの2倍から4倍の圧縮率であり、しかも高速である。彼らはSNP（一塩基多型）をマイナー対立遺伝子でソートすることでデータセットを均質化するMAF（マイナー対立遺伝子頻度）ベースの符号化 (MAFE) を導入した[23]。
- ^ Tank, Minaldevi K. (2011), Pise, S. J., ed., “Implementation of Lempel-ZIV algorithm for lossless compression using VHDL”, Thinkquest-2010 (Springer India): 275-278, doi:10.1007/978-81-8489-989-4_51, ISBN 978-81-8489-989-4
- ^ Pujar, J.H.; Kadlaskar, L.M. (May 2010). “A New Lossless Method of Image Compression and Decompression Using Huffman Coding Techniques”. Journal of Theoretical and Applied Information Technology 15 (1): 18-23.
- ^ Mahdi, O.A.; Mohammed, M.A.; Mohamed, A.J. (November 2012). “Implementing a Novel Approach an Convert Audio Compression to Text Coding via Hybrid Technique”. International Journal of Computer Science Issues 9 (6, No. 3): 53-59 2013年3月6日閲覧。.
- ^ Navqi, Saud; Naqvi, R.; Riaz, R.A.; Siddiqui, F. (April 2011). “Optimized RTL design and implementation of LZW algorithm for high bandwidth applications”. Electrical Review 2011 (4): 279-285.
- ^ Mahmud, Salauddin (March 2012). “An Improved Data Compression Method for General Data”. International Journal of Scientific & Engineering Research 3 (3): 2 2013年3月6日閲覧。.
- ^ Mahmud, Salauddin (March 2012). “An Improved Data Compression Method for General Data”. International Journal of Scientific & Engineering Research 3 (3): 2 6 March 2013-03-06閲覧。.
- ^ Arcangel, Cory. “On Compression”. 2013年3月6日閲覧。
- ^ Mahmud, Salauddin (March 2012). “An Improved Data Compression Method for General Data”. International Journal of Scientific & Engineering Research 3 (3): 2 2013年3月6日閲覧。.
- ^ Marak, Laszlo. “On image compression”. University of Marne la Vallee. 2013年3月6日閲覧。
- ^ Mahoney, Matt. “Rationale for a Large Text Compression Benchmark”. http://cs.fit.edu/~mmahoney/. Florida Institute of Technology. 2013年3月5日閲覧。
- ^ Korn, et. al., D.. “RFC 3284: The VCDIFF Generic Differencing and Compression Data Format”. Internet Engineering Task Force. 2013年3月5日閲覧。
- ^ Korn, D.G.; Vo, K.P. (1995), B. Krishnamurthy, ed., Vdelta: Differencing and Compression, Practical Reusable Unix Software, New York: John Wiley & Sons, Inc.
- ^ Zwicker, et. al., Eberhard (Originally published in 1967; Translation published in 1999). The Ear As A Communication Receiver. Melville, NY: Acoustical Society of America
- ^ IEEE Journal on Selected Areas in Communications. Voice Coding For Communications 6 (2). (February 1988). http://www.jsac.ucsd.edu/TOC/1988/feb88.html+2013年3月6日閲覧。.
- ^ “Summary of some of Solidyne's contributions to Broadcast Engineering”. Brief History of Solidyne. Buenos Aires: Solidyne. 2013年3月6日閲覧。
- ^ a b Faxin Yu, Hao Luo, Zheming Lu (2010). Three-Dimensional Model Analysis and Processing. Berlin: Springer. p. 47. ISBN 9783642126512
- ^ “Video Coding”. Center for Signal and Information Processing Research. Georgia Institute of Technology. 2013年3月6日閲覧。
- ^ Graphics & Media Lab Video Group (2007). Lossless Video Codecs Comparison. Moscow State University
- ^ Lane, Tom. “JPEG Image Compression FAQ, Part 1”. Internet FAQ Archives. Independent JPEG Group. 2023年10月11日閲覧。
- ^ Bhojani, D.R.. “4.1 Video Compression”. Hypothesis. 2013年3月6日閲覧。[リンク切れ]
- ^ Jaiswal, R.C. (2009). Audio-Video Engineering. Pune, Maharashtra: Nirali Prakashan. p. 3.55. ISBN 9788190639675
- ^ Ahmed, N.U.; Natarajan, T.; Rao, K.R. (January 1974). “Discrete Cosine Transform”. IEEE Transactions on Computers C-23 (1): 90-93. doi:10.1109/T-C.1974.223784 2013年3月6日閲覧。.
- ^ “HapZipper: sharing HapMap populations just got easier”. Nucleic Acids Research 40 (20): e159. (2012年7月27日). doi:10.1093/nar/gks709.
- 1 データ圧縮とは
- 2 データ圧縮の概要
- 3 理論
- 4 アナログ帯域圧縮
- 5 関連項目
データ圧縮と同じ種類の言葉
- データ圧縮のページへのリンク
