本文是基于9月29日的算法設計與分析課程上所討論的內容總結而成的。因為受到ppt版面所限，原題目中并無“數字”兩字，考慮到準確性這里重新補上。由于時間比較倉促且能力所限，意識到有些問題在課堂上可能沒有闡述清楚，因此在這里把已經提到的和未能提到的問題匯總成篇，以備參考。
我本人的參考書是福州大學王曉東的《計算機算法設計與分析(第3版)》(下稱“王書”)，本課對應于原書第三章第七節的部分內容，當然課堂上我們曾提出王書中有部分不妥之處，并提出了初步的改進建議，這里仍將保留該部分內容。
問題提出 眾所周知，數字圖像壓縮問題是隨著網絡通信技術的不斷發展而提出的。通常把圖像數據壓縮方案分為兩類：有損圖像壓縮和無損圖像壓縮。有損圖像壓縮通常能夠達到很高的壓縮率，但是其在采樣和頻域變換過程中損失了部分像素真值，從而導致圖像質量有一定下降。當前常見的數字圖像壓縮技術有JPEG、MPEG（主要應用于運動圖像壓縮）等。無損圖像壓縮從字面意思上理解就是不會降低圖像質量，但壓縮率會變得不太穩定：典型的無損圖像壓縮實現有兩個步驟：去相關性和編碼。去相關性的目的就是為了減少圖像冗余，這包含字、字節甚至是二進制位的冗余消除，當然消除冗余后的圖像數據需要重新編碼并給出相應的索引表，從而實現壓縮和解壓縮。
這里給出一種數字圖像無損壓縮方案。假設數字圖像像素點灰度值序列為{p1,p2,…,pn}，其中整數pi(1≤i≤n)表示像素點i的灰度值，其范圍通常為0~255。將像素點序列{p1,p2,…,pn}分割成m個連續段S1,S2,…,Sm。第i個像素段Si中(1≤i≤m)，有l個像素，且該段中的所有像素灰度值只用b位表示。確定像素序列{p1,p2,…,pn}的最優分段，使得依次分段所需的存儲空間最小。
初步分析 設t=∑l[k]，1≤k≤i-1，1≤i≤m，則第i個像素段Si為Si={Pt+1,…,Pt+l}，1≤i≤m。另設hi=上界(log(max(Pk+1)))，其中t+1≤k≤t+l，則有hi≤b≤8。故b(1≤i≤m)可用3個二進制位表示。另設1≤l≤255，則需用8位表示l，其中1≤i≤m。因此第i個像素段所需的存儲空間為l×b +11位。故對于全部像素序列{p1, p2,…, pn}，需要∑l×b+11m，1≤i≤m。
確定最優子結構 設l，b，1≤i≤m是{p1,p2,…,pn}的一個最優分段。顯然，l[1],b[1]是{p1,…,pl[1]}的一個最優分段，且l,b，2≤i≤m是{pl[1]+1,…,pn}的一個最優分段。
這部分的證明應用反證法，大體思路如下：已知{p1,p2,…,pn}有最優分段l,b(1≤i≤ m) ，最優總存儲空間為Θ。假設上述結論中的l[1],b[1]和l,b，2≤i≤m不全是相應序列的最優分段，由上部分最后一個公式可得該分段存儲空間Θ’>Θ，這與已知l,b(1≤i≤ m) 為最優分段相矛盾，故假設不成立。
重疊子問題和狀態轉移方程設s，1≤i≤n是像素序列{p1,p2,…,pn}的最優分段所需的存儲位數。由最優子結構性質知：
s=min{s[i-k]+k*bmax(i-k+1,i)}+11，其中bmax(i,j)=上界(log(max{Pk}+1))，1≤k≤min(i,256)。
動態規劃算法設計01
02
03
04
05
06
07
08
09
10
11
12
13
| Compress(n,p,s,l,b)
for i <- 1 to n
b <- length(p); //length:log(p)
bmax <- b;
s <- s[i-1] + bmax;
l <- 1;
for j <- 2 to i and Lmax //Lmax=256
if bmax < b[i-j+1]
then bmax <- b[i-j+1];
if s > s[i-j] + j * bmax
then s <- s[i-j] +j*bmax;
l <- j;
s <- s + header; //header=11
|
計算復雜度 空間復雜度O(n)。
時間復雜度分析：
1
2
3
4
| for i <- 1 to n
...
for j <- 2 to i and Lmax //Lmax=256
...
|
因此亦為O(n)。
構造最優解 在構造出最優解之前我們先舉例給出上述動態規劃算法的結果。例如：
輸入像素序列:196,120,48,5,2,1。 那么計算后得出：s={19,27,35,43,51,55}，l={1,2,3,4,5,3}，b={8,7,6,3,2,1}。由王書P71第二句知：“最優分段的最后一段的段長度和像素位數分別存儲于l[n]和b[n]中”。簡單驗證可知，l的定義是正確的，但是b無法滿足無損壓縮的要求。這是因為，由王書算法計算后得出，{5,2,1}為最優分段的第二段，同時該段像素位數為1位，顯然，1位空間僅能保留像素1的信息，而前面的5、2均會丟失。這就是我們指出的王書中可能存在的錯誤。如果沿用書中的動態規劃算法，那么正確的描述應為：最優分段的最后一段的段長度存儲于l[n]中，其相應的像素位數應是max{b[n-l[n]+1],…,b[n]}。其前一段的段長度應為l[n-l[n]]，而對應的像素位數如下：max{b[n-l[n-l[n]]+1],…b[n-l[n]]}。
鑒于上述描述比較繁瑣，又考慮到保證原算法的正確性，我們給出如下改進的動態規劃算法：
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
| declaration B[n] // global
Compress(n,p,s,l,b)
for i <- 1 to n
b <- length(p); //length:log(p)
bmax <- b;
B <- b;
s <- s[i-1] + bmax;
l <- 1;
for j <- 2 to i and Lmax //Lmax=256
if bmax < b[i-j+1]
then bmax <- b[i-j+1];
if s > s[i-j] + j * bmax
then s <- s[i-j] +j*bmax;
l <- j;
for k<- i-j+1 to i
B<-bmax;
s <- s + header; //header=11
|
其中數組B是一個全局量，我們用于存儲最優分段中的像素位信息，同時在構造最優解的過程中用B替換b作為輸入參數，經驗證，該程序可以實現題目預設的目標。
結論 我們應用動態規劃方法解決了一個較為普通的最優化問題。事實上這種思想可以應用于許多具有類似特征的問題求解中。當然，我們學習動態規劃的目的并非是為了求解類似算法競賽難度的各類習題，而是將這種思想結合進平時對實際問題的解決中，這樣的話，我想，DP的魅力將是無窮的。
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
