資料壓縮 向量量化 方法解說與實作

向量量化原理解析(未訓練)

首先我們回需要三分檔案分別是

1. 原圖：source.raw
2. 編碼簿：origin.raw
3. 索引值：idx.raw

原圖

原圖是256x256的大小，並且在實做中最小單位是一個區塊，一個區塊由4x4組合，原圖可以看成是是一個64x64大小的圖。

編碼簿

編碼簿也是以區塊為單位，其中第一次是從原圖隨機抽取256個區塊。

索引值

索引值大小是區塊化的原圖大小也就是64x64，它的獲取需要輸入sou與ori獲得，獲取的過程是以原圖為主，原圖的第一個區塊 sou.bolock[0] 去比較 ori.bolock[0~255] 跟哪一個最像獲得。

假如 sou.bolock[i] 與 ori.bolock[2] 最像，那麼就在 idx[i] 填入 2，依序填完全部

最像的定義是這樣的兩個區塊內16個像素，個別的差值平方的總和 而根據這個數據，越低代表越像。

void block_diff(unsigned char a[16], unsigned char b[16]){
    size_t sum=0;
    for(unsigned i = 0; i < 16; ++i) {
        sum += pow(abs(a[i]-b[i]), 2);
    }
}

合併回原圖

我們有了編碼簿與索引值之後就可以拼回原圖了，依照索引值內的編號將編碼簿一個區塊一個區塊慢慢補回去即可。

for(unsigned i = 0; i < 4096; ++i) {
    img.block[i] = ori.block[idx[i]];
}

訓練編碼簿

隨機抽取的編碼簿還原之後的圖與原圖的差距是很大的，為了降低這種誤差，要盡可能的讓編碼簿的碼優化。優化步驟如下。

1. 計算新的編碼簿區塊
2. 計算新的索引值
3. 疊代至收斂

計算新的編碼簿區塊

看一下圖中的 sou.raw 上面的編號是從 idx.raw 抄上來的，在這上面可以發現有兩個3號，分別是 sou.block[0] 與 sou.block[2] 他們之所以獲得相同的編號是因為，他們各自與編碼簿中的256個比較後，與 ori.block[3] 很像。

理解這個原理就可以發現 ori.block[3] 存在著優化空間，它可以取 sou.block[0] 與 sou.block[2] 的平均獲得更精準的還原；平均指的是16個點個別相加/2，獲得全新的16個點。

void tra_block(int idxNum){
    long long unsigned int s[16]{};
    size_t cnt=0;
    // 找出相同索引並累加
    for(unsigned i = 0; i < 4096; ++i) {
        if(idx[i]==idxNum) {
            for(unsigned k = 0; k < 16; ++k, ++cnt) {
                s[k] += sou.block[i][k];
            }
        }
    }
    // 根據找出的數，算出平均數並填入tra
    if (cnt != 0){
        // 算出平均
        for (int i = 0; i < 16; ++i)
            s[i] = s[i]/cnt;
        // 回填
        for (unsigned k = 0; k < 16; ++k)
            ori.block[idxNum][k] = s[k];
    }
}

ori 裡面總共有 256 個區塊，把這 256 個都做過一次優化就可以了

for(unsigned j = 0; j < 256; ++j) {
    tra_block(j);
}

計算新的索引值

有了優化過的編碼簿之後就可以重新計算新的索引值，與前面所敘述的算法是一樣的，只不過在過程中要多存一個數據。

比對的過程中每個區塊所算出來的差平方和，一共是4096個要把取平均值存下來。

疊代至收斂

根據索引值計算時所產出的 avg 做計算，依據公式需要用到本次與上次的avg

計算 avg差值/當前avg 不小於 0.01 則回到[1]

可以看到優化過後的圖片，與原本的沒有優化好了很多。

實作程式碼

GitHub連結：向量量化

​