# Vector Quantization (VQ)

###### tags: `C/C++` `Data Compression`

> 紀錄向量量化流程

[ToC]
## :memo: Linde-Buzo-Gray(LBG) Algorithm?

### Step 1: Divide the given image into block, so that each block appears as a d-dimensional vector.
> 將輸入圖片切分為數個區塊(block)，每個區塊都為一個向量集合[color=#3b75c6]

:::info
假設我們的圖片大小為512x512，區塊大小為4x4，因此我們需要 (512x512) / (4x4) = **16384** 個區塊，而且每個區塊的向量集合為**16** (4x4)。
:::

### Step 2: Initial codebook is chosen randomly.
> 初始化編碼簿(codebook)，分為隨機法以及最鄰近配對法，在這邊使用**隨機法**取得[color=#3b75c6]

:::info
編碼簿的大小自行設定 (64, 128, 256, 512, 1024)，在這邊選用1024，意即在**16384**個區塊中隨機挑選**1024**個區塊放入編碼簿。
:::

### Step 3: The initial chosen codebook is set as the centroid and the other vectors are grouped according to the nearest distance with the centroid similar to the k-mean clustering.
> 將初始化好的編碼簿與原圖的區塊 (16384) 進行匹配，尋找最接近的區塊，並**記錄對應的索引(index)**[color=#3b75c6]

- 虛擬碼

for (int i = 0; i < 區塊數量(16384); i++) {
    for (int j = 0; j < 編碼簿大小(1024); j++) {
        for (int k = 0; k < 區塊大小(4x4); k++) {
            最小平方誤差 += pow(abs(原圖區塊[i][k] - 編碼簿區塊[j][k]), 2);
        }
        if (最小平方誤差最小){
            更新最小值;
            更新索引值;
        }
    }
    // 累積整張圖(16384 blocks)的最小值，以便後面訓練(迭代收斂)編碼簿使用
    累積最小值;                
    紀錄區塊(i)對應的索引值;
}

:::info
:rocket: 因為隨機抽取的編碼簿還原後的結果與原圖的差距很大，為了降低這種誤差，要盡可能的優化編碼簿。優化的步驟如下:
1. 計算新的編碼簿區塊
2. 計算新的索引值
3. 迭代至收斂
:::

### Step 4: Find the new centroid of every group to get a new codebook iterative. Repeat the steps 3 & 4 till the convergence of the centroid of every group.
> 重複訓練編碼簿(步驟3與步驟4)直到平均失真值收斂[color=#3b75c6]

:::info
:rocket: 因為在步驟3各自與編碼簿的1024個比較後，索引可能會記錄相同的區塊(codebook block)，因此必須==優化重複的索引目標==。

**假設區塊[0]與區塊[2]紀錄的索引都是編碼簿[3]的資料(因為與1024個匹配出最接近的為編碼簿[3])，所以須將原圖的區塊[0]與區塊[2]進行平均來獲得更精準地還原。平均指的是16(4x4)個點個別相加 / 2，以便獲得全新的16個點。**
:::

- 虛擬碼

for (int idxNum = 0; idxNum < 編碼簿大小(1024); ++idxNum) {
		long long unsigned int s[16]{};
		size_t cnt = 0;
		// 找出相同索引並累加
		for (unsigned i = 0; i < 索引大小(同區塊數量 16384); ++i) {
			if (索引值[i] == idxNum) {
				++cnt;
				for (unsigned k = 0; k < BLOCK_SIZE; ++k) {
					s[k] += 原圖區塊[i][k];
				}
			}
		}
		// 根據找出的數，算出平均數並更新編碼簿
		if (cnt != 0) {
			// 算出平均
			for (int i = 0; i < BLOCK_SIZE; ++i)
				s[i] = s[i] / cnt;
			// 更新
			for (unsigned k = 0; k < BLOCK_SIZE; ++k)
				編碼簿[idxNum][k] = s[k];
		}
}
// 迭代所需的平均值(更新前)
double pre_avg = 累積最小值(步驟3) / 索引大小(同區塊數量 16384);
// 清空累積最小值以便步驟3使用
累積最小值 = 0;
// 重新匹配(更新)
匹配原圖與編碼簿(步驟3);
// 迭代所需的平均值(更新後)
double post_avg = 累積最小值(步驟3) / 索引大小(同區塊數量 16384);
// 迭代所需的平均失真值(參考)
return abs(post_avg - pre_avg) / post_avg;

---

## Benchmark Results !
> 查找編碼簿與索引值合併出原圖[color=#3b75c6]

- 原圖
- 無訓練
- 訓練完

## Reference
- GeeksforGeeks ➜ [Linde-Buzo-Gray(LBG) Algorithm](https://www.geeksforgeeks.org/linde-buzo-gray-lbg-algorithm/)
- Blogger(hunandy14) ➜ [CHG:資料壓縮 向量量化 方法解說與實作](https://charlottehong.blogspot.com/2018/01/blog-post_10.html/)