影像壓縮問題
問題描述
給定一張灰度圖，其像素為長度為\(n\)的灰度值序列：{\(p_1,p_2,\cdots,p_n\)}，其中\(p_i \in [0:1:255]\)可表示為8位二進位數。現使用一種變位壓縮方式對影像進行壓縮，具體壓縮過程如下：
將{\(p_1,p_2,\cdots,p_n\)}分割成為\(m\)段：\(S_1,S_2,\cdots,S_m\)；
\(l[i]\)為\(S_i\)段的像素數，要求\(l[i]\leq 256\)；
\(h_i\)為\(S_i\)段中最大像素灰度值對應的二進位位數，則有$$h_i=\left \lceil\log\left(\max\limits_{p_k \in s_i}{p_k}+1\right)\right\rceil$$
\(b[i]\)為\(S_i\)段中所有像素的灰度值二進位表示的最小位數，則有$$h_i \leq b[i] \leq 8$$
每個分段\(S_i\)的段頭都有11位
\(b[i]\leq 8\)的二進位表示：3位
\(l[i]\leq 256\)的二進位表示：8位
\(S_i\)段的二進位總位數（佔用空間）：\(11+b[i]\times l[i]\)；
可以看出，不同的分段方案\(T=\{S_1,S_2,\cdots,S_j\}\)導致不同的變位壓縮結果，即佔用不同大小的總空間。現需要確定空間佔用最小的分段方案，即$$\min\limits_{T}\left{\sum_{i=1}^{j}(b[i]\times l[i]+11)\right}$$
約束條件
影像壓縮問題中約束條件是：\(l[i]\leq 256\)，即每個段中的像素數不超過256個。也就是說只要不違背這個約束條件的所有解均是可行解。
目標函數
影像壓縮問題是最小化問題，其目標函數是：各個分段佔用空間之和，即
\]
演算法設計
子問題邊界參數化
在該問題中，我們將問題的左側邊界固定，右側邊界進行參數化，所有子問題可建模為：像素序列\(P_i=\{p_1,p_2,\cdots,p_i\}, i=1,2,\cdots,n\)。
遞推方程設計
設\(s[i]\)是像素序列\(P_i=\{p_1,p_2,\cdots,p_i\}，i=1,2,\cdots,n\)的最優分段所需存儲的位數，則遞推關係設計如下：
s[i]=\min\limits_{1\leq j \leq \min\{i,256\}}\left\{s[i-j]+j\times b_{max}(i-j+1,i)+11\right\} \\
s[0] = 0
\end{cases}
\]
其中，\(b_{max}(i-j+1,i)=\left\lceil \log \left ( \max\limits_{p_k \in S_m}p_k + 1 \right )\right\rceil \leq 8\)。
演算法的偽程式碼描述
function Compress(n, p, l, s, b)
lmax ← 256;header ← 11;s[0] ← 0
for i = 1 → n do
b[i] ← length(p[i])
bmax ← b[i]
s[i] ← s[i − 1] + bmax
l[i] ← 1
for j = 2 → min i, lmax do
if bmax < b[i − j + 1] then
bmax ← b[i − j + 1]
if s[i] > s[i − j] + j ∗ bmax then
s[i] ← s[i − j] + j ∗ bmax
l[i] ← j
s[i] ← s[i] + header
return s, b, l
end function
function Traceback(n, i, s, l)
i ← 0
if n == 0 then
return
Traceback(n − l[n], i, s, l)
s[i + +] ← n − l[n]
end function
演算法時空效率估計
(1）估計演算法Compress的時間複雜度，試給出詳細過程。
Compress只需\(O(n)\),由於在演算法中j的次數不超過256次，故對每一個確定的i可在\(O(1)\)時間內完成，因此時間複雜度為\(O(n)\).
（2）估計演算法Traceback的時間複雜度，試給出詳細過程。
由於數組\(l[i],b[i]\)記錄了最優分段所需的資訊，最優分段的最後一段的段長度和像素位數分別存在\(l[n],b[n]\)中，其前一段的段長度和像素位數存儲於\(l[n-l[n]]\)和\(b[n-l[n]]\)中，依次類推，在\(O(n)\)時間內構造最優解。
編碼實現
#include<iostream>
#include<vector>
using namespace std;
//灰度值二進位位數
int Length(int i){
int k = 1;
i = i/2;
while(i > 0){
k ++;
i = i/2;
}
return k;
}
//迭代備忘錄實現動態規劃
void Compress(int n,vector<int> &p,vector<int> &s,vector<int> &l,vector<int> &b){
int lmax = 256;
int header = 11;//分段首部
s[0] = 0;
int bmax;
for(int i = 1;i <= n;i ++){
b[i] = Length(p[i]);
bmax = b[i];
s[i] = s[i-1] + bmax;
l[i] = 1;
int k = 0;
if(i > lmax){
k = lmax;
}else{
k = i;
}//k取lmax和 i的較小值
for(int j = 2;j <= k;j ++){
if(bmax < b[i-j+1]){
bmax = b[i-j+1];
}
if(s[i] > s[i-j]+j*bmax){
s[i] = s[i-j]+j*bmax;
l[i] = j;//記錄分段
}
}
s[i] = s[i] + header;//加上首部
}
}
//遞歸追蹤解
void Traceback(int n,int& i,vector<int> &s,vector<int> &l){
if(n == 0){
return;
}
Traceback(n-l[n],i,s,l);
s[i++] = n-l[n];//用s表記錄分段位置
}
int main(){
int n;
cin >> n;
vector<int> s,b,l,p;
for(int i = 0;i <= n;i ++){
s.push_back(0);
b.push_back(0);
l.push_back(0);
p.push_back(0);
}
for(int i = 1;i <= n;i ++){
int p1;
cin >> p1;
p[i] = p1;
}
Compress(n,p,s,l,b);
cout << "最小存儲位數：" << s[n] << endl;
int m = 0;
Traceback(n,m,s,l);
s[m] = n;
cout << "共分段數:" << m << endl;
for(int j = 1;j <= m;j ++){
l[j] = l[s[j]];
b[j] = b[s[j]];
}
for(int j = 1;j <= m;j ++){
cout << "此段個數：" << l[j] << "所需儲存位數：" << b[j] << endl;
}
return 0;
}
結果展示
結束語
若結局非你所願，請在塵埃定前奮力一搏
作者：花城
