距離空間とベクトル量子化
デジタル画像
ピクセル
R
G
色の三原色
B
0~255
画像圧縮について
289Kbyte
・・・
エンコーダ
(順変換)
ブロック/画素単位の走査
蓄積
両者が異なる場合,
歪み圧縮という.
0100101000
1000001111
0001111000
0001・ ・ ・ ・
伝送
圧縮ファイル
289Kbyte
・・・
80Kbyte
デコーダ
(逆変換)
距離空間
【距離と距離空間】
集合X上の2つの元x,y∈Xを実数値に対応づける写像d(x,y)が,以下の条件を
満足するとき,dを距離といい,集合Xを距離空間という.
1.d(x,y)≧0 (非負性)
3.d(x,y) = 0
集合X
⇔
x=y
2.d(x,y) = d(y,x)
4.d(x,y) ≦ d(x,z) + d(z,y)
元y
(三角不等式)
-2 -1 0 1 2 3 4
d
元x
(可換)
R1
距離空間におけるベクトル量子化
符号化器
…
…
…
…
[Code Book] 64x3[B] → 1[B]
[Data File] 8x8, 64x64
123,222,034,254,001,102,211,246,
123,222,034,254,001,102,211,246,
123,222,034,253,001,102,211,246,
:
123,222,034,254,001,006,211,246,
…
…
…
復号器
000:■, 001 :■, 002 :■, 003 :■,
004:■, 005 :■, 006 :■, 007 :■,
008:■, 009 :■, 010 :■, 011:■,
012:■, 013 :■, 014 :■, 015 :■,
:
252:■, 253 :■, 254 :■, 255 :■,
【コードブック;code book】
類似したブロック群を代表する
ブロックを記録したテーブル.
…
クラスタリングによるコードブック生成
【画像空間;image space】
n画素からなる画像ブロックは,n次元実空間Rn上の元となる.
【距離で類似度を計る】
画像空間上で,位置の近い画像ブロック
同士は,類似している.したがって,
画像空間には類似度を測るための適当な
距離を定義する必要がある.
【群化;clustering】
元を幾つかの代表点で近似するとき,
できるだけ誤差を小さくする代表点
を選択する処理をクラスタリングと
いう.コードブックとは,群番号と
代表点を記録したファイルである.
【LBG法】
全ての元を最寄の代表点で近似した場合の
距離の総量 (誤差関数,目的関数)が極小と
なるように代表点を移動させる最適化法
NN法
+
初期配置
+
ラベリング
重心計算
+
+
ラベリング
重心計算
収束
ダウンロード

距離と距離空間