デジタル映像メディア基礎

デジタル画像の 圧縮や符号化入門
デジタル映像メディア基礎
Digital Images : Compression and Encoding
Foundations of Digital Image Media
8回目
圧縮
＝compression
（あっしゅく）
符号化(ふごうか）＝encoding
1
10
データ圧縮とは
宿題/Homework
What is data compression?
Data compression is a way to make a
data file smaller
※データ圧縮とは、ファイルを小さくする方法である
データ
ファイル
pp. 9 - 10
pp. 21 - 31
pp. 177-186
11
8 megabytes
圧縮
同じデータファイル
1 megabytes
12
なぜデータ圧縮するのか？
なぜデータ圧縮するのか？
Why do we need to compress data?
Why do we need to compress data?
(1)Data Transmission/データ通信
不圧縮
Transmitting data can be slow and expensive.
データ通信には、お金と時間がかかる。
￥￥￥
Example: packet charge for your keitai:
例：携帯のパケットの通信料
圧縮されたデータ
Compression reduces the time/cost of sending data
データ圧縮すると、コストと時間を削る事が出来る
13
Compressed data is faster and cheaper to transmit
圧縮されたデータ通信は、より早く安い
データ圧縮と通信
なぜデータ圧縮するのか？
Data compression & transmission
Why do we need to compress data?
￥
14
(2) Data Storage/データ保存
Encode/
符号化
Large data files take up lots of storage space.
大きなファイルは、たくさんの容量（ようりょう）
が必要
通信
Example (a): DVD
- movies are compressed with “mpeg2”
to make the data fit on one disk
Decode/
デコード(復号)
例 (a)：DVD：
映画は、MPEG2等を使って、データを一枚の
15
ディスクに保存出来るように圧縮している
16
なぜデータ圧縮するのか？
なぜデータ圧縮するのか？
Why do we need to compress data?
Why do we need to compress data?
データファイル
(2) Data Storage/データ保存
Example (b): mp3
- music is compressed so many songs
fit on one CD, or iPod
DVD,CD-ROM等
不圧縮
例 (b): mp3
- 音楽ファイルを圧縮すると、一枚のCD
やiPod等に、たくさんの曲を保存出来る
17
圧縮された
ファイル
Can store more data if it is compressed
データを圧縮すると、たくさんのものを保存出来る
18
データ圧縮と符号化
データ圧縮のしくみ
Data Compression and Encoding
How to compress data?
簡単な例： A simple example
To compress data, we write it in a code
データを圧縮するために、コードを使う
Message/メッセージ： aaababbbcdabeeeee (17文字）
Some codes are more efficient than others
あるコードは、非常に効果的である
Code/コード: 3aba3bcdab5e
(12文字）
Message/メッセージ ：aaaaaaaaaaaaaaa (15文
字）
例: 漢字、ひらがな、ローマ字
Code/コード : 15a
(3文字）
※Some messages are easier to compress!
立命館 ＝ りつめいかん ＝ Ritsumeikan
3文字 6文字 11文字
19
※あるメッセージは、圧縮しやすい
※※This is called a ‘Run-length Code’ (RLE)
※※「ランレングス符号化」という
20
画像データ圧縮のしくみ
画像データ圧縮のしくみ
How to compress image data?
Why do we need to compress images?
21
復習：カラー画像も、数字の表
復習：デジタル画像は数字の表
Digital image = table of numbers
colour image = table of numbers
画素の明るさは数字で表現される
252
240
237
242
253
252
124
199
249
(R = 151, G = 116, B = 70)
画素の明るさ
画素の明るさ
白: 255
黒: 0
•グレースケール
２５６段階が普
通
22
（赤、緑、青）
画素の色と明るさは３つの原色で表現される
Usual case: 3 Bytes (= 24 bits) for each pixel
23
24
復習：標本化と量子化と画像データ量（りょう）
総(そう）ピクセル数 実例
Review: Sampling, Quantization, and
Total number of pixels, actual example
Image Data Quantity
Image file size is proportional to
1. Total number of pixels
(N pixels)
h = 480 pixels
2. Number of bits/bytes for each pixel
Image file size
~ 922 KiloBytes
(3 bytes/pixel)
Nxb
例: 1 x 106 pixels x 8 bits = 1 MB (megabyte)
w = 640 pixels
25
26
画像データ圧縮のしくみ
総(そう）ピクセル数 実例
How to compress image data?
Total number of pixels, actual example
Let s think about a 2 level image
階調数=2画像について考えてみよう
※Fax machine
922 kbytes will be expensive to send by mobile phone
And slow
922 kbytesのファイルを携帯で送ると、値段と時間がかか
る
N = w x h = 640 x 480 = 307,200
pixels
27
sends binary
image
※ファクスは、白黒
28
の
画像を送る
画像データ圧縮のしくみ
画像データ圧縮のしくみ
How to compress image data?
How to compress image data?
よく出てくるパターン
３白 ー＞ 「１０」
２黒 ー＞ 「１１」
2 level
Image
白黒の
画像
あまり出ないパターン
２０白 ー＞ 「００００１１０１」
長い信号に符号化する
１５黒 ー＞ 「００００１１００」
白黒黒黒白•黒白白白黒•白白白白黒•••
白 黒ラン
ラ
ン
短い信号に符号化する
白ラン
This idea is the basis of “Huffman Coding”
ハフマン符号化の基礎です
RLE: 白３黒白黒３白黒４白黒•••
29
30
ハフマン符号化
可逆圧縮と不可逆圧縮について
Huffman Coding
Lossless & Lossy Compression
Huffman invented this code in 1951,
when he was a student at MIT
ハフマンが大学院生の時に発明した
Used in digital media:
Fax, digital images, mp3, DVD etc…
ほとんどのディジタルメディアで
使われている
David Huffman
(1925 - 1999)
31
Both run-length code and Huffman code
Are LOSSLESS CODES
ランレングス符号化とハフマン符号化は、
可逆圧縮である
This means that we can recover all of the
signal from the code - no information is lost
圧縮した情報は、完全に元に戻す事が出来る
32
可逆圧縮と不可逆圧縮について
不可逆圧縮について
Lossless & Lossy Compression
Lossy Compression
Deleting some pixels in an image is a simple
example of lossy compression
We can also compress a file by deleting information
また、情報を削る事により、圧縮する事が出来る
This is known as LOSSY COMPRESSION because
information is lost
この場合は、不可逆圧縮といい、情報は削られる
（けずられる）
ピクセルを削ると、簡単に圧縮出来る
33
34
不可逆圧縮について
可逆圧縮と不可逆圧縮について
Lossy Compression
Lossless & Lossy Compression
Nearly all digital media use both LOSSY and
lossless compression
X
ほとんどすべてのディジタルメディアでは、不可逆
と可逆圧縮の両方が使われている
The file size is 30%
BUT: we cannot recover the original image
- mp3
- Digital images/デジタル画像
ファイルサイズは、３０％に圧縮出来たが、
もとの画像に戻す事は出来ない
- speech over mobile phone/携帯での通話
- DVD
35
36
可逆圧縮と不可逆圧縮について
不可逆圧縮について
Lossless & Lossy Compression
Lossy Compression
So, why don’t we notice the missing
Information?
The trick: delete information that we don’t notice
トリック：人間にとって、鈍感（どんかん）な情報
を削る
37
38
不可逆圧縮について
画像データの不可逆圧縮のしくみ
Lossy Compression
Lossy Image Compression
•Colour Information can be reduced without
becoming noticeable
色の変化の成分には、鈍感なので、削ること
Example mp3: throw information above 15 kHz
例；mp３ー15kHz以上の情報を削る
が
出来る
Human hearing is not so sensitive to this range
人間の聴覚（ちょうかく）が気つかないため
•Small image details can be reduced without
becoming noticeable
The missing information doesn’t bother us too much
39
画像の細かい部分にも、鈍感なので、削るこ
とが
JPG フォーマット
出来る
40
JPG 圧縮のしくみ
JPG 圧縮のしくみ I
JPG Compression
JPG Compression: Step I
明るさの
成分
JPG ＝ JPEG
「JPEG」 ＝ Joint Photographic coding Experts Group
元の画像
画像圧縮の方式を決めたグループの名前
色の変化
成分
41
データを
減らす
色の変化
成分
42
JPG 圧縮のしくみ II
DCTの計算方法
JPG Compression: Step II
DCT Calculation
補足（ほそく）：
• Small detail of image is reduced
(画像の細かい部分を削る（けずる）
• Method: Discrete Cosine Transform (DCT)
方式：「離散•コサイン変換」（DCT）
8ピクセル
補足（ほそく）：
• DCT transforms image to frequency space
and cut high frequency data
8ピクセル
こうしゅうは
DCTの計算時間を減らすため、８x８ピクセルのブロック
•画像を周波に変換し、その中の高周波成分を削る
(人間の目は、高周波成分には、鈍感（どんかん）である）
43
ごとに高周波成分を削る
44
具体的に、JPGはどうなるの?
Hmm… so what does a JPG
look like?
45
Lena.png
PNG file: 708 KB
46
「PNG」画像ファイルフォーマット
PNG Image File Format
「PNG」 ＝ 「Portable Network Graphics」
ちょっと、「PNG」ってなに?
PNG???
※ PNG uses LOSSLESS compression
※ PNGでは、可逆圧縮が使われている
PNG was designed to replace GIF image format
PNGは、「GIF」の代替物である
47
48
「GIF」画像ファイルフォーマット
GIF Image File Format
「GIF」 ＝ 「Graphics Interchange Format」
「GIF」？？
ファイルフォーマットが多いな。。。
※ GIF uses LOSSLESS compression
「GIF」では、可逆圧縮が使われている
※ Uses 8 bit colour (only 256 levels)
256 段階しか表現出来ない
49
50
「GIF」と「PNG」画像ファイルフォーマッ
ト
GIF
※ Filesize of GIF and PNG is usually larger than for JPG
※ 通常、GIFとPNGのファイルのサイズは、JPGより大きい
GIF is an old format, but still used for animations
「ANIMATED GIF」 = 「アニメーションGIF」
「GIF」は古いフォーマットだが、今でも、アニメーション
で使われている
GIF and PNG are well suited for images which have
large homogeneous areas
GIFとPNGフォーマットは、同じ色の部分が多い画像
に向いている。
43
51
GIFフォーマット画像の実例
例
１
例
３
とりあえず、JPGの話に戻ろう
例
２
52
53
JPG画像ファイルフォーマット
JPG Image File Format
で、実際、JPGはどうなるの?
※ ALL JPG Images use LOSSY compression
※ すべてのJPG画像では、不可逆圧縮が使われている
SO!!! what does a JPG
look like???
JPG is good for photographs: file size is smaller but
we don’t notice the information loss
JPGは、写真に向いている。ファイルのサイズは、小さく
なるが、情報が減った事に気づかない
54
55
４０分の１
に圧縮！
Lena.jpg
Lena.jpg
JPG file, Quality = 100, 312 KB
56
JPG file, Quality = 1, 16 KB ( > 40x compressed!!)
57
！！！
！！！
４０分の１、に圧縮したのに、
あまり 情報が減った事に気づかない
58
59
JPG画像ファイルフォーマット
JPG Image File Format
However, if we compare the PNG and JPG, there
is a slight difference in colour
しかし、「PNG」と「JPG」を比較して見ると、
色に微妙（びみょう）な違いがある。
60
Lena.png
PNG file: 708 KB
61
JPG画像ファイルフォーマット
JPG Image File Format
Also, if we enlarge the image, we can see errors of the
JPG compression
また、画像を拡大して見ると、画像のエラーが見える
Lena.jpg
JPG file, Quality = 100, 312 KB
62
63
PNG File
704 KB
20X
64
Quality = 80
116 KB
20X
66
Quality =100
312 KB
20X
65
Quality = 50
44 KB
20X
67
Quality = 1
16 KB
20X
Quality = 1
16 KB
20X
8
ピ
ク
セ
ル
68
8ピクセル 69
DCTの計算方法
DCT Calculation
補足（ほそく）：
8ピクセル
8ピクセル
DCTの計算時間を減らすため、８x８ピクセルのブロック
ごとに高周波成分を削る
70
71
Quality =100, 312 KB
Quality = 1, 16 KB
72