欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標題: 數(shù)字圖像壓縮問題 [打印本頁]
作者: 51黑tt    時間: 2016-3-5 18:18
標題: 數(shù)字圖像壓縮問題
本文是基于9月29日的算法設計與分析課程上所討論的內(nèi)容總結(jié)而成的。因為受到ppt版面所限，原題目中并無“數(shù)字”兩字，考慮到準確性這里重新補上。由于時間比較倉促且能力所限，意識到有些問題在課堂上可能沒有闡述清楚，因此在這里把已經(jīng)提到的和未能提到的問題匯總成篇，以備參考。
我本人的參考書是福州大學王曉東的《計算機算法設計與分析(第3版)》(下稱“王書”)，本課對應于原書第三章第七節(jié)的部分內(nèi)容，當然課堂上我們曾提出王書中有部分不妥之處，并提出了初步的改進建議，這里仍將保留該部分內(nèi)容。
問題提出 眾所周知，數(shù)字圖像壓縮問題是隨著網(wǎng)絡通信技術(shù)的不斷發(fā)展而提出的。通常把圖像數(shù)據(jù)壓縮方案分為兩類：有損圖像壓縮和無損圖像壓縮。有損圖像壓縮通常能夠達到很高的壓縮率，但是其在采樣和頻域變換過程中損失了部分像素真值，從而導致圖像質(zhì)量有一定下降。當前常見的數(shù)字圖像壓縮技術(shù)有JPEG、MPEG（主要應用于運動圖像壓縮）等。無損圖像壓縮從字面意思上理解就是不會降低圖像質(zhì)量，但壓縮率會變得不太穩(wěn)定：典型的無損圖像壓縮實現(xiàn)有兩個步驟：去相關(guān)性和編碼。去相關(guān)性的目的就是為了減少圖像冗余，這包含字、字節(jié)甚至是二進制位的冗余消除，當然消除冗余后的圖像數(shù)據(jù)需要重新編碼并給出相應的索引表，從而實現(xiàn)壓縮和解壓縮。
這里給出一種數(shù)字圖像無損壓縮方案。假設數(shù)字圖像像素點灰度值序列為{p1,p2,…,pn}，其中整數(shù)pi(1≤i≤n)表示像素點i的灰度值，其范圍通常為0~255。將像素點序列{p1,p2,…,pn}分割成m個連續(xù)段S1,S2,…,Sm。第i個像素段Si中(1≤i≤m)，有l(wèi)個像素，且該段中的所有像素灰度值只用b位表示。確定像素序列{p1,p2,…,pn}的最優(yōu)分段，使得依次分段所需的存儲空間最小。
初步分析 設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。
確定最優(yōu)子結(jié)構(gòu) 設l，b，1≤i≤m是{p1,p2,…,pn}的一個最優(yōu)分段。顯然，l[1],b[1]是{p1,…,pl[1]}的一個最優(yōu)分段，且l,b，2≤i≤m是{pl[1]+1,…,pn}的一個最優(yōu)分段。
這部分的證明應用反證法，大體思路如下：已知{p1,p2,…,pn}有最優(yōu)分段l,b(1≤i≤ m) ，最優(yōu)總存儲空間為Θ。假設上述結(jié)論中的l[1],b[1]和l,b，2≤i≤m不全是相應序列的最優(yōu)分段，由上部分最后一個公式可得該分段存儲空間Θ’>Θ，這與已知l,b(1≤i≤ m) 為最優(yōu)分段相矛盾，故假設不成立。
重疊子問題和狀態(tài)轉(zhuǎn)移方程設s，1≤i≤n是像素序列{p1,p2,…,pn}的最優(yōu)分段所需的存儲位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)知：
s=min{s[i-k]+k*bmax(i-k+1,i)}+11，其中bmax(i,j)=上界(log(max{Pk}+1))，1≤k≤min(i,256)。
動態(tài)規(guī)劃算法設計
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)。
構(gòu)造最優(yōu)解 在構(gòu)造出最優(yōu)解之前我們先舉例給出上述動態(tài)規(guī)劃算法的結(jié)果。例如：
輸入像素序列: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第二句知：“最優(yōu)分段的最后一段的段長度和像素位數(shù)分別存儲于l[n]和b[n]中”。簡單驗證可知，l的定義是正確的，但是b無法滿足無損壓縮的要求。這是因為，由王書算法計算后得出，{5,2,1}為最優(yōu)分段的第二段，同時該段像素位數(shù)為1位，顯然，1位空間僅能保留像素1的信息，而前面的5、2均會丟失。這就是我們指出的王書中可能存在的錯誤。如果沿用書中的動態(tài)規(guī)劃算法，那么正確的描述應為：最優(yōu)分段的最后一段的段長度存儲于l[n]中，其相應的像素位數(shù)應是max{b[n-l[n]+1],…,b[n]}。其前一段的段長度應為l[n-l[n]]，而對應的像素位數(shù)如下：max{b[n-l[n-l[n]]+1],…b[n-l[n]]}。
鑒于上述描述比較繁瑣，又考慮到保證原算法的正確性，我們給出如下改進的動態(tài)規(guī)劃算法：
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



其中數(shù)組B是一個全局量，我們用于存儲最優(yōu)分段中的像素位信息，同時在構(gòu)造最優(yōu)解的過程中用B替換b作為輸入?yún)?shù)，經(jīng)驗證，該程序可以實現(xiàn)題目預設的目標。
結(jié)論 我們應用動態(tài)規(guī)劃方法解決了一個較為普通的最優(yōu)化問題。事實上這種思想可以應用于許多具有類似特征的問題求解中。當然，我們學習動態(tài)規(guī)劃的目的并非是為了求解類似算法競賽難度的各類習題，而是將這種思想結(jié)合進平時對實際問題的解決中，這樣的話，我想，DP的魅力將是無窮的。





歡迎光臨 (http://www.raoushi.com/bbs/) Powered by Discuz! X3.1