圖像壓縮算法

1、算法設(shè)計與分析課程報告姓名:文亮學(xué)號:201322220254學(xué)院:信息與軟件工程學(xué)院老師:屈老師;王老師算法實現(xiàn)與應(yīng)用算法設(shè)計與分析課程報告一. 基本要求 1. 題目 : 圖像壓縮 2. 問題描述掌握基于 DCT 變換的圖像壓縮的基本原理及其實現(xiàn)步驟;對同一幅原 始圖像進(jìn)行壓縮,進(jìn)一步掌握 DCT 和圖像壓縮。3. 算法基本思想圖像數(shù)據(jù)壓縮的目的是在滿足一定圖像質(zhì)量的條件下,用盡可能少的比特數(shù) 來表示原始圖像, 以提高圖像傳輸?shù)男屎蜏p少圖像存儲的容量, 在信息論中稱 為信源編碼。 圖像壓縮是通過刪除圖像數(shù)據(jù)中冗余的或者不必要的部分來減小圖 像數(shù)據(jù)量的技術(shù), 壓縮過程就是編碼過程, 解壓縮過

2、程就是解碼過程。 壓縮技術(shù) 分為無損壓縮和有損壓縮兩大類, 前者在解碼時可以精確地恢復(fù)原圖像, 沒有任 何損失;后者在解碼時只能近似原圖像,不能無失真地恢復(fù)原圖像。假設(shè)有一個無記憶的信源 , 它產(chǎn)生的消息為 Ni a i 1, 其出現(xiàn)的概率是已 知的 , 記為 (i a p 。則其信息量定義為 :(i i a p a log -=I由此可見一個消息出現(xiàn)的可能性越小, 其信息量就越多, 其出現(xiàn)對信息的貢 獻(xiàn)量越大,反之亦然。信源的平均信息量稱為“熵” (entropy ,可以表示為:(=-=HNi i i Ni i i a p a p a p I a p 11log對上式取以 2為底的對數(shù)時,單

3、位為比特(bits :(=-=HNi i i a p a p 1log根據(jù)香農(nóng)(Shannon 無噪聲編碼定理,對于熵為 H 的信號源,對其進(jìn)行無失真編碼所可能達(dá)到的最低比特數(shù)為, 這里為一任意小的正數(shù), 因此可能達(dá)到的 最大壓縮比為:H+H=BB C max 其中 B 是原始圖像的平均比特率。在圖像壓縮中,壓縮比是一個重要的衡量指標(biāo)?？梢远x壓縮比為:H=B C 其中 B :原始數(shù)據(jù)的平均壓縮比; H :壓縮數(shù)據(jù)的平均比特率 圖像壓縮的基本模型圖像編碼包括兩個階段, 前一個階段就是利用預(yù)測模型或正交模型對圖 像信號進(jìn)行變換;后一個階段是利用已變換信號的統(tǒng)計特性,對其分配適當(dāng) 的代碼來進(jìn)行編碼

4、傳輸。編碼器與解碼器的結(jié)構(gòu)分別如圖 (a、 (b。 圖(a 編碼器結(jié)構(gòu) 圖(b 解碼器結(jié)構(gòu)在發(fā)送端, 輸入的原始圖像首先經(jīng)過 DCT 變換后, 其低頻分量都集中在左上 角,高頻分量分布在右下角(DCT 變換實際上是空間域的低通濾波器 。由于該 低頻分量包含了圖像的主要信息, 而高頻分量與之相比就不那么重要了, 所以可 以忽略高頻分量, 從而達(dá)到壓縮的目的。 將高頻分量去掉就要用到量化, 這是產(chǎn) 生信息損失的根源?！傲炕钡闹饕蝿?wù)是用有限個離散電平來近似表達(dá)已抽取出的信息。在此 采用均勻量化,通過改變程序中的量化因子 Q 的值以得到不同壓縮比的圖像。Huffman 編碼時,首先對經(jīng) DCT 變

5、換及量化后的圖像收據(jù)掃描一遍,計算出各種 像素出現(xiàn)的概率;然后按概率的大小指定不同長度的唯一碼字,由此得到一張 Huffman 表。編碼后的圖像記錄的是每個像素的碼字,而碼字與量化后像素值的 對應(yīng)關(guān)系記錄在碼表中。 生成的一維字符矩陣即為實際中要傳輸?shù)男蛄? 壓縮后 的圖像數(shù)據(jù)在信道中進(jìn)行傳輸。在接收端,接收到的壓縮圖像數(shù)據(jù)首先經(jīng)過 Huffman 譯碼,通過搜索已生成 的 Huffman 表, 根據(jù)碼字與量化后像素值的對應(yīng)關(guān)系, 搜索出與碼字對應(yīng)的像素 值, 并轉(zhuǎn)換為二維矩陣。 反量化時將以上二維矩陣中的每一個像素值乘以量化因 子 Q 。最后通過 DCT 反變換得到重建圖像。離散余弦變換 (

6、DCT當(dāng)前處于信息高速流通時代,要求在保證質(zhì)量的前提下,以較小的空間存儲 圖像和較小的比特率傳輸圖像, 這就需要采用各種圖像壓縮編碼技術(shù)來實現(xiàn)。 DCT 變換是最小均方誤差條件得出的次最佳正交變換, 且已經(jīng)獲得廣泛的應(yīng)用, 并已 經(jīng)成為許多圖像編碼國際標(biāo)準(zhǔn)的核心。 離散余弦變換的變換核是余弦函數(shù), 計算 速度較快,有利于圖像壓縮和其他處理。在大多數(shù)情況下, DCT 用于圖像的壓縮 操作中。 JPEG 圖像格式的壓縮算法采用的是 DCT 。二.算法實現(xiàn)程序源代碼function b = blkproc(varargina, block, border, fun, params, padval =

7、 parse_inputs(varargin:; ma,na = size(a;mpad = rem(ma,block(1; if mpad>0, mpad = block(1-mpad; endnpad = rem(na,block(2; if npad>0, npad = block(2-npad; endif (isa(a, 'uint8' if (padval = 1aa = repmat(uint8(1, ma+mpad+2*border(1,na+npad+2*border(2;elseaa = repmat(uint8(0, ma+mpad+2*bor

8、der(1,na+npad+2*border(2;endelseif isa(a, 'uint16' if (padval = 1aa = repmat(uint16(1, ma+mpad+2*border(1,na+npad+2*border(2;elseaa = repmat(uint16(0, ma+mpad+2*border(1,na+npad+2*border(2;endelseif (padval = 1aa = ones(ma+mpad+2*border(1,na+npad+2*border(2;elseaa = zeros(ma+mpad+2*border(1,

9、na+npad+2*border(2;endendaa(border(1+(1:ma,border(2+(1:na = a;m = block(1 + 2*border(1;n = block(2 + 2*border(2;mblocks = (ma+mpad/block(1;nblocks = (na+npad/block(2;arows = 1:m; acols = 1:n;x = aa(arows, acols;firstBlock = feval(fun,x,params:;if (isempty(firstBlockstyle = 'e' ;b = ;elseif (

10、all(size(firstBlock = size(xstyle = 's' ; % sameif (isa(firstBlock, 'uint8' b = repmat(uint8(0, ma+mpad, na+npad;elseif (isa(firstBlock, 'uint16' b = repmat(uint16(0, ma+mpad, na+npad;elseb = zeros(ma+mpad, na+npad;endbrows = 1:block(1;bcols = 1:block(2;mb = block(1;nb = bloc

11、k(2;xrows = brows + border(1;xcols = bcols + border(2;b(brows, bcols = firstBlock(xrows, xcols;elseif (all(size(firstBlock = (size(x-2*borderstyle = 'b' ; % borderif (isa(firstBlock, 'uint8' b = repmat(uint8(0, ma+mpad, na+npad;elseif (isa(firstBlock, 'uint16' b = repmat(uint

12、16(0, ma+mpad, na+npad;elseb = zeros(ma+mpad, na+npad;endbrows = 1:block(1;bcols = 1:block(2;b(brows, bcols = firstBlock;mb = block(1;nb = block(2;elsestyle = 'd' ; % differentP,Q = size(firstBlock;brows = 1:P;bcols = 1:Q;mb = P;nb = Q;if (isa(firstBlock, 'uint8' b = repmat(uint8(0,

13、mblocks*P, nblocks*Q;elseif (isa(firstBlock, 'uint16' b = repmat(uint16(0, mblocks*P, nblocks*Q;elseb = zeros(mblocks*P, nblocks*Q;endb(brows, bcols = firstBlock;endrr,cc = meshgrid(0:(mblocks-1, 0:(nblocks-1;rr = rr(:;cc = cc(:;mma = block(1;nna = block(2;for k = 2:length(rrx = aa(rr(k*mma+

14、arows,cc(k*nna+acols;c = feval(fun,x,params:;if (style = 's' b(rr(k*mb+brows,cc(k*nb+bcols = c(xrows,xcols; elseif (style = 'b' b(rr(k*mb+brows,cc(k*nb+bcols = c;elseif (style = 'd' b(rr(k*mb+brows,cc(k*nb+bcols = c;endendif (style = 's' | (style = 'b' b = b(1

15、:ma,1:na;endfunction a, block, border, fun, params, padval = parse_inputs(varargin iptchecknargin(2,Inf,nargin,mfilename;switch nargincase 3% BLKPROC(A, m n, 'fun'a = varargin1;block = varargin2;border = 0 0;fun = fcnchk(varargin3;params = cell(0,0;padval = 0;case 4if (strcmp(varargin2, '

16、;indexed' % BLKPROC(X, 'indexed', m n, 'fun'a = varargin1;block = varargin3;border = 0 0;fun = fcnchk(varargin4;params = cell(0,0;padval = 1;elseparams = varargin(4;fun,msg = fcnchk(varargin3, length(params;if isempty(msg% BLKPROC(A, m n, 'fun', P1a = varargin1;block = va

17、rargin2;border = 0 0;padval = 0;else% BLKPROC(A, m n, mb nb, 'fun'a = varargin1;block = varargin2;border = varargin3;fun = fcnchk(varargin4;params = cell(0,0;padval = 0;endendotherwiseif (strcmp(varargin2, 'indexed' params = varargin(5:end;fun,msg = fcnchk(varargin4,length(params;if

18、isempty(msg% BLKPROC(A, 'indexed', m n, 'fun', P1, .a = varargin1;block = varargin3;border = 0 0;padval = 1;else% BLKPROC(A, 'indexed', m n, mb nb, 'fun', P1, .a = varargin1;block = varargin3;border = varargin4;params = varargin(6:end;fun = fcnchk(varargin5,length(par

19、ams;padval = 1;endelseparams = varargin(4:end;fun,msg = fcnchk(varargin3,length(params;if isempty(msg% BLKPROC(A, m n, 'fun', P1, .a = varargin1;block = varargin2;border = 0 0;padval = 0;else% BLKPROC(A, m n, mb nb, 'fun', P1, .a = varargin1;block = varargin2;border = varargin3;param

20、s = varargin(5:end;fun = fcnchk(varargin4, length(params;padval = 0;endendendif (islogical(a | isa(a,'uint8' | isa(a, 'uint16' padval = 0;endclearclcI=imread('C:Userslenovo.lenovo-PCDesktop²âÊÔͼ.jpg' I=rgb2gray(I;I=im2double(I;T=dctmtx(8;B=blkproc(I,8 8,'P1*x*P2',T,T'mask = 1 1 1 1 0 0 0 01 1 1 0 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00