人気ブログランキング |
- 北の空からみなみへ -
exblog staff

<< 制 夜が8時になったなら >>
おべんきょう うえいぶれっと(復習)
2008年 09月 11日
データ圧縮というのは、通常の完全に元データを再現できる圧縮の場合は、1/2~1/3程度を限界とすることが多い。
 このような完全に復元できる圧縮を 可逆圧縮と呼ぶ。
 それ以上の圧縮を行う場合、音声や画像データのように劣化を容認し不完全な復元を容認する。
 これを 不可逆圧縮と呼ぶ。

 圧縮はサイズの縮小が目的になされるが、サイズが多少の増加をしても解読が困難になることを狙う場合、それは暗号化と呼ばれる。
(ライフログにひとつだけ暗号化の関連図書がある
  
日経BP企画
暗号解読 ロゼッタストーンから量子暗号まで
暗号技術は解読技術とのせめぎ合いを通じて高度に発展してきた。その歴史的経緯と未来の動向をひも解く読み物。カエサル暗号,ヴィジュネル暗号,暗号機械エニグマ,公開カギ暗号,量子暗号などを追う。


(日経インターネットテクノロジー 2001/09/01 Copyright©2001 日経BP企画..All rights reserved.)


内容(「BOOK」データベースより)
最先端領域に宿る天才たちの壮絶なドラマ。歴史の背後に秘められた、暗号作成者と解読者の攻防―加速する情報戦争の勝者はいったい誰か?『フェルマーの最終定理』に続く世界的ベストセラー、待望の完全翻訳版。

内容(「MARC」データベースより)
ネット・セキュリティ、Uボート、英女王暗殺計画…。歴史の裏面を彩る、暗号をめぐる壮絶なドラマの数々。加速する情報戦争の勝者はいったい誰か? 最先端領域に宿る、天才たちの壮絶なドラマ。


出版社 新潮社担当編集者
わからないものがわかるようになる『フェルマーの最終定理』でもそう思わされましたが、このサイモン・シンという書き手、ただものではありません。最終的には現在の暗号の最先端領域にまで踏み込んでいくのですが(量子コンピュータだとか量子暗号だとか)、青木薫さんの名訳のおかげもあって(ほんとに読みやすく訳してくださってます)、本来かなり難しい内容のはずなのに、読む側にはまったくストレスを感じさせません。それどころか、読み終わるとなんだか頭が良くなったような気にさえさせるのです。こんな才能を持ったサイエンス・ライターは、ほんとにまれだと思います。ワクワクさせてくれて、しかも科学の最先端に触れさせてくれる――僕などは、一ファンとして、次作が待ち遠しくてなりません。是非ご一読を!

From the Back Cover
Praise for Fermat's Enigma by Simon Singh:
"Vividly recounted...I strongly recommend this book to anyone wishing
to catch a glimpse of what is one of the most important and
ill-understood, but oldest, cultural activities of humanity...an
excellent and very worthwhile account of one of the most dramatic and
moving events of the century."
--Roger Penrose, The New York Times Book Review

"How great a riddle was Fermat's 'last theorem'? The exploration of
space, the splitting of the atom, the discovery of DNA--unthinkable in
Fermat's time--all were achieved while his Pythagorean proof still
remained elusive...Though [Singh] may not ask us to bring too much
algebra to the table, he does expect us to appreciate a good detective
story."
--The Boston Sunday Globe

"It is hard to imagine a more informative or gripping account
of...this centuries-long drama of ingenious failures, crushed hopes,
fatal duels, and suicides." --The Wall Street Journal

"[Singh] writes with graceful knowledgeability of the esoteric and
esthetic appeal of mathematics through the ages, and especially of the
mystifying behavior of numbers." --The New York Times

"[Singh] has done an admirable job with an extremely difficult
subject. He has also done mathematics a great service by conveying the
passion and drama that have carried Fermat's Last Theorem aloft as the
most celebrated mathematics problem of the last four centuries."
--American Mathematical Society

"The amazing achievement of Singh's book is that it actually makes the
logic of the modern proof understandable to the nonspecialist...More
important, Singh shows why it is significant that this problem should
have been solved." --The Christian Science Monitor
--このテキストは、絶版本またはこのタイトルには設定されていない版型に関連付けられています。

About the Author
Simon Singh received his Ph.D. in physics from the
University of Cambridge. A former BBC producer, he directed an
award-winning documentary film on Fermat's Last Theorem that aired on
PBS's "Nova" series, and wrote the bestselling book Fermat's
Enigma. He lives in London, England.
--このテキストは、絶版本またはこのタイトルには設定されていない版型に関連付けられています。

著者略歴 (「BOOK著者紹介情報」より)
シン,サイモン
1967年、イングランド南西部サマーセット州生まれ。祖父母はインドからの移民。ケンブリッジ大学大学院で素粒子物理学の博士号を取得。ジュネーブの研究センターに勤務後、テレビ局BBCに転職。96年、ドキュメンタリー『フェルマーの最終定理―ホライズン・シリーズ』で国内外の賞を数多く受賞

青木 薫
1956年、山形県生まれ。京都大学理学部卒業、同大学院修了。理学博士。翻訳家(本データはこの書籍が刊行された当時に掲載されていたものです)
暗号解読―ロゼッタストーンから量子暗号まで | 商品情報(書籍)


可逆圧縮でなされる手法は、双方向関数の手法。 厳密な解が相互にひとつだけ存在するような方法でなされる。

二進数(Binary number)で表されたデータを、バイナリと呼ぶ。 コンピュータが扱うデータは全て二進数だから、バイナリ・データと呼ぶことができる。
(これは本来の意味でのバイナリという語の扱い方。 慣用的にはもっと狭義に、実行可能ファイルや 可読文字コード列以外が主となるデータに限ってバイナリ・データと呼ぶことも多い)

十進数(decimal number)は、人間の指の数が両手で十本であることから世界中で使用されている。 その働きを模した算盤(そろばん)の場合は、「1の珠が4個 + 5の珠が1個」でひとつの桁を示す。 まれに商家では1の珠が5個のものも使う。
ところが二進数の場合、計算機が扱う珠の種類は、「オンかオフ(入りか切)」「信号が高いか低い(High/Low)」のようなひとつ玉である。 ゼロ・いち・に という数え方を、入が1で切が0とする二進数8桁(0~255まで数えられる)で示すと、

  1. 00000000
  2. 00000001
  3. 00000010
   ・・・
  1. 00001111
  2. 00010000
   ・・・
  1. 11111111
となる。
このように、もの(上の例では数)となまえ(上の例では十進数で"2" 二進数で"00000010")の関係を定めたり、ある系から別の体系へ変換(割り当て)することを 符号化 と呼ぶ。

そして、この符号化の手法は もの⇒なまえ の割り当て方のほかに、なまえ(ひらがな)⇒ナマエ(カタカナ) のようにも、名前(日本語)⇒name(英語)のような割り当て方にも共通する部分がある。

二進数で "00100000" というのは、十進数では32に相当する。 割り当てられている文字コードは「 」(半角の空白)である。 試しにURLの文字の中に「%20」というのを入れてみるとどうなるか試すこともできる。 次の検索のURL文字列を、ロケーション(アドレス)欄に入れて試すこともできる。
http://www.google.co.jp/search?q=%20&lr=lang_ja
これって、自分でいろいろ試してみるとよく分かるかもしれません。

二進数を十進表記するほかに、よく使われるのが16進数(hexadecimal numbers)表記。
 0, 1, 2, 3,,,, 9, A, B, C, D, E, F という具合に、10~15にA~Fを割り当てます。
 多く書かれる形式では、00h のように二桁で書いて末尾にhexadecimalの略を書く。

二進数の8桁を、前4桁(上位ビット)後ろ4桁(下位ビット)にして表記したものに相当するのが16進数ということになります。
 10進数を上段 2進数を中段 16進数を下段 という具合に並べてみましょう。

0
9
10
15
16
255
00000000
00001001
00001010
00001111
00010000
11111111
00h
09h
0Ah
0Fh
20h
FFh



情報を箱の中に入れる(例えばデータベース)場合に、固定長の箱を用意する方法(dbfなどの形式)と可変長の箱(ポインタ管理)で管理する方法があります。
 二進数の場合、この箱は8桁(8bit つまり 1byte)とか、16桁(2byte文字=全角文字)とか、24~48桁(3~4byte=Unicodeなど)があるのですが、この箱が大きければ大きいほど当然ながら箱全体を収納するファイル容量は増加します。
 そして、このファイル容量をより小さくする方法を考えることが圧縮方法を考えることになるわけです。

ごく単純なものから記す。


RanLength method(ランレングス法)
 同じデータが続く場合、たとえば空白文字 「 」(20h)が100個とか続く場合には、8bit箱(1byte長)で扱っても、100バイトが必要になります。
 ところが、[100個の半角空白] というわずか15バイトの文字列でも同じ情報を伝えることができます。
 このように、同じ文字列が連続する場合に威力を発揮するのがランレングス法で、ファックスのような二値画像(白か黒かで表現)を圧縮送信するのに使われています。
 解説サイトの例 画像圧縮アルゴリズム (1)ランレングス法
 Wikipedia記事 連長圧縮 - Wikipedia


エントロピー符号化(theory of output statistics)
 同じデータが続く場合、ランレングス法で圧縮が効く例からも分かるように、データが容易に圧縮できるには そのデータが均一である方が都合がよい(容易という意味)。 例えば、完全な空白(それはデータと呼べるのか?)や、一様な真っ黒(これは濃いデータと呼んでいいのか?)のようなデータ列は高い圧縮効率が期待できます。
 異なるデータに偏りがある場合、そして「完全におんなじ」な少数の種類しかデータが分類されない場合 ── たとえば真っ白な白紙に一点だけ黒がある あるいは 日の丸のようなデータ ── に、有効な圧縮手法が先のランレングス法であり、ここで述べるエントロピー符号化になります。両者の差は、隣接しているデータが同じか近い場合に圧縮可能なランレングス法、出現頻度に偏りがある場合にエントロピー符号化圧縮が効果的。

こういうのは画像で直感的に理解するのが一番! なので、画像中の画素の明るさを一覧表示した、ヒストグラムとかパワースペクトルとか呼ばれる図で記す。
 元になった画像は、http://pds.exblog.jp/pds/1/200809/10/95/c0062295_2057593.jpg
 こちらの写真を白黒のグレースケール画像として解析した図になります。
c0062295_22275689.jpg
peak index 140(3.5%)

赤丸で示した高頻度に出現するデータには、短い符号(ビット数)を与えます。
緑丸で示した低頻度にしか出現しないデータには、短い符号(ビット数)で済ませます。
 そうやって、箱の大きさ(ビット長)を可変にすることで、圧縮効率を得るのがエントロピー符号化ということになります。
 上の図では、全諧調(256階調)のうち30%ほどの輝度index値に 全体画素(480x270=129600px)の95%以上が集中しているのが元になった写真の画像です。
 各画素に、256階調を与えるとそれだけで(白黒なのに)129Kbyteになります。
 赤丸印に囲まれた画素が存在するindexに(仮に)3ビットだけ与え、緑丸印の部分で無強度(画素数ゼロ)のindexにはビットを与えない、ほんの少し(5%未満)しかない画素には6ビットを与えるとします。
 すると、赤丸内画素は123120個以上あるのですが、370Kbit(ビットをバイトになおすと)= 47Kbyte 程度に圧縮されます。
 青丸内画素(5%あるとして6480px)は、強度ゼロの分を省略できたので6bitの符号化で間に合うため、長目の符号を与えたにも関わらすわずか39Kbit = 5Kbyte のデータ量で済みます。
 合計で、52Kbyte。
 ※ 実際にはファイル内容定義部分や、解読用辞書=デコード・コーデック(CODECとは Coder+Decoder または Compresser Decompressor の意)参照用データを、ファイル内に格納するためこれよりは大きくなる。

エントロピー符号化の一種に、LHAで有名になった圧縮手順で使われている ハフマン符号化がある。

 2.1.5. エントロピー符号化 - 規格/H.264|AVC - Fraternity7 を調べていて、偶然の寄り道が面白かった(停止済みブログ)牛乳有害説

ハフマン符号化は、LZ77 / LZ78 そして LZSS のアルゴリズム中にも存在し、さらに GIF や PNG そして Tiff や Jpeg(jpg)画像にも使用されている。
ハフマン符号化による圧縮は可逆圧縮であり、データの損失(画像であれば劣化)がない。 2000年を迎える頃に、GIFフォーマット内LZ系アルゴリズムで二箇所使用されていた特許部分を所有する UNISYS社によるライセンス料請求問題によって、一時期画像ソフトからGIF画像サポートが打ち切られる現象があった。


さて・・・やっと画像圧縮の標準ともいえる、Jpegにまでたどり着いたのだが。。。参照リンク頼りでなるべく省略しよう ^^;





Jpeg のキモは、8x8のブロックに分割して、そのブロック毎に完結する形で DCT(離散コサイン変換)によって高周波成分を丸める手法にある。
Jpeg開発の中心となったグループ ISO/IEC JTC 1/SC 29/WG 1、Joint Photographic Experts Group のメンバーが検討作業を開始した1982年当時のコンピュータ性能の制限から、8x8画素程度のブロックに分割することが望ましいとされた。
 しかしながら、この手法によって、特に高圧縮になるほど、
 ・なだらかなグラデーション部分でブロックノイズが目立つ
 ・色調の急激に変わる辺縁部分でモスキートノイズが生じやすい
 という欠点が目立つことにもなった。

ブロック内の画素値を読み込む順番は、左の上から右の下へと行われる。

1
2
6
7
15
16
28
29
3
5
8
14
17
27
30
43
4
9
13
18
26
31
42
44
10
12
19
25
32
41
45
54
11
20
24
33
40
46
53
55
21
23
34
39
47
52
56
61
22
35
38
48
51
57
60
62
36
37
49
50
58
59
63
64
c0062295_18421998.gif
このような順番で取得する理由
 自然画(写真)においては画素値が急速に変化することは少ない。
 なだらかな画素値の変化は、次のステップで行う離散コサイン変換(DCT)によって情報の圧縮がしやすいようにスペクトル(頻度順)化できるので、連続的な値であるほうが望ましい。 ⇒ したがって、左から右への順次走査(テレビでの水平スキャン)をすると、右端から左端に飛んだ時点で画素の値が不連続になる。 それを避けるためにこのような 「左上から右下へのジグザグ走査でブロック内スキャンを完結させる」という手法を採っている。

次のステップとして、得られたデータ列は次式で離散コサイン変換(DCT)される。
 データ数 64個の場合は次の式で計算され、結果のスペクトルを得る。
 このスペクトル分布は、DCT係数と呼ばれ低周波数のデータに偏る。 よってエントロピー圧縮に向いたデータになった。(高周波成分を粗く量子化したり切捨てると、ハフマン符号化することによる圧縮率はより高くなる)
c0062295_1927751.gif下になる
c0062295_1955460.jpg
 右図はWikipediaより改変引用した


このDCT係数を量子化テーブルの値で除す(割り算する)。
この段階で(量子化テーブルの内容次第で)、粗く切り捨てる範囲が決まる。
 ⇒ 得た係数データ列は、量子化係数と呼ばれる。

この量子化係数は、低周波成分だけを守り高周波成分を丸めたもの。
高周波成分はほとんどゼロに等しい値なので、最終ステップとして行う ハフマン符号化による圧縮が 効果を示すことになる。

全体の流れは
下になる



[原画像] → [ブロック化] → [DCT] → [量子化] → [符号化] → [圧縮データ]
 圧縮【符号器】↑

解凍(復元)【復号器】↓

量子化テーブル 符号化テーブル

[復元画像] ← [逆DCT] ← [逆量子化] ← [復号化] ← [圧縮データ]
 量子化・逆量子化では量子化テーブルが、
 符号化・復号化では符号化テーブルが使用される。

参考になる(私の記事よりずっと)分かりやすい説明
 貧乏人のためのCG講座
 → 離散的コサイン変換と量子化の具体例 量子化テーブルの実際例



画像解析を少しでも学ぶと、必ずといっていいほどフーリエ変換にお目にかかる。
コンピュータ上でこれを実装する場合、離散フーリエ変換として 完全な周期関数とはみなさない工夫がされるのだが、基本的に局所完結型の解析は苦手である。 (周波数の制度を高めると、追従性が悪くなる。 追従性を求めて時間微分するサンプリングウィンドウを狭めると → 周波数解析の信頼性は非常に悪化する)

そこで、例えば地震波の解析など、石油探査の場で「一度限りで急激に変化する波の解析に使う」という目的で使われだしたのが Wavelet解析 / Wavelet変換 ということになる。
 浅学の私には、フーリエ変換と本質的に同じ ── Fourierの sin / cos では 奇関数 / 偶関数(そして平行位相 1/4)という特徴に対して、Waveletのほうは 奇/偶(積分が1/差分がゼロ)の対となる関数を局所反転と位相シフトを施し使用法に合わせ最適化した関数 ── という雑把さで理解している ^^

さて うえーぶれっと圧縮の実際的手順。

基礎の説明: 高周波成分と低周波周波数とに分解する。
 縦方向に高周波成分・低周波成分
 横方向にも高周波成分・低周波成分
 そうすると、4分割された LLLH・HL・HH の成分分布を得る。
(縦横どちらも低周波・横方向低周波・横方向高周波・縦横どちらも高周波)

具体的手順(わかりやすい harrウエーブレット関数にて)
 


。。。のこりは後日に追記を・・・・するかも 笑(投稿記事の日付も変更するかも)
by bucmacoto | 2008-09-11 21:15 | particle
<< 制 夜が8時になったなら >>
<< 制 夜が8時になったなら >>