画像圧縮アルゴリズム (4)ハフマン符号化 - 動的ハフマン圧縮
上の例では、赤で塗られた同レベルの節を入れ替えて、木の右側ほどレベルが深くなるようにしてから、黄色で塗られた同レベルの葉を入れ替えて、データ番号が昇順に並ぶようにしています。 正規化によって得られたハフマン符号には強い規則性が見られます。最も符号長が短く、且つパレットコードの一番若い葉は、全てのビットが0になり、逆に符号長が最も長く、且つパレットコードが最大の葉は全てのビットが1になります。符号長の等しい葉の符号は、パレットコードの若いものから順に1ずつ増えていき、符号長が1ビット長くなると、符号に1を加えた後で、末尾に0を付加した形になっていることが、上の例からもわかると思います。 この規則性を利用して、次のような手順で符号長からハフマン符号を再現させることができます。 各節の中で、葉の部分のみを符号長でソートする。符号長が等しい場合は、パレットコード順に並べる。 ソート後の葉の配列から
画像圧縮アルゴリズム (3)ハフマン符号化 - 静的ハフマン圧縮
#define PALET_MAX 256 /* パレットコードの最大数 */ #define HUFFMAN_TREE_MAX ( PALET_MAX * 2 - 1 ) /* ハフマン木の節の最大数 */ #define RED( color ) ( ( ( color ) >> 16 ) & 0xFF ) #define GREEN( color ) ( ( ( color ) >> 8 ) & 0xFF ) #define BLUE( color ) ( ( color ) & 0xFF ) /* ハフマン木構造体 */ typedef struct Huffman_Tree { unsigned char rgb; unsigned int count; struct Huffman_Tree *left; struct Huffman_Tree *right; } Huffma
画像圧縮アルゴリズム (5) LZ法
この章では、現在のデータ圧縮・画像圧縮などで広く用いられているLZ法について説明します。 前章までで説明したハフマン圧縮では、個々のデータをハフマン符号に変換して圧縮を試みるというものでしたが、LZ法では、あるデータ列に着目して、それが以前に出現したことがあるかをチェックし、すでに出現したことがあるのならば、そのデータ列を示す何らかの符号(当然、データ列より短くなければなりません)に置き換える処理を行うことにより、圧縮を行っています。 LZ法には、いくつかの種類があり、その種類によってさらに名称が変わります。しかし、その違いは符号化の方法だけで、処理の内容については全て同じです。 LZ法は、Abraham LempelとJacob Zivの二人による共同開発によって、1977年に誕生しました。正式名称はZiv-Lempel codingですが、間違ってLZ法として紹介したことから、現在の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
String Matching Algorithm に基づく有歪み圧縮について | CiNii Research
untitled
招待論文 Lempel-Ziv 符号と情報理論 植松 友彦†a) ユニバーサル符号とデータ圧縮論文小特集 Lempel-Ziv Coding as a Tool for Information Theory Tomohiko UYEMATSU†a) あらまし 情報源の統計的性質をあらかじめ
ひずみを許すユニバーサル符号化 | CiNii Research
サービス終了のお知らせ
