一：圖像編碼基本理論

圖像編碼：一種將數(shù)字圖像轉(zhuǎn)換為壓縮表示形式的過程。它的目標是減少圖像數(shù)據(jù)的存儲空間，并在傳輸或存儲時減少帶寬和存儲需求、主要分為兩類

• 無損壓縮：盡可能地保留原始圖像的所有信息，以實現(xiàn)無失真的壓縮。其中最常見的算法之一是無損JPEG（JPEG-LS）編碼，它使用類似于有損JPEG的離散余弦變換，但保留了所有細節(jié)
• 有損壓縮：通過犧牲一些細節(jié)和圖像質(zhì)量來實現(xiàn)更高的壓縮比。最常見的有損壓縮算法之一是JPEG（Joint Photographic Experts Group）編碼。JPEG使用離散余弦變換（DCT）將圖像分成不同頻率的頻譜，并根據(jù)人眼對顏色和亮度的感知特性來降低高頻細節(jié)。這樣可以大幅減少圖像的體積，但會引入一定程度的失真

（1）圖像壓縮的必要性

圖像壓縮的必要性：

• 存儲空間的節(jié)省：原始數(shù)字圖像通常占據(jù)大量的存儲空間。通過壓縮圖像，可以有效地減少其所占用的存儲空間。例如，一個高分辨率的彩色圖像可能需要幾百兆字節(jié)的存儲空間，而通過壓縮可以將其縮小到幾十兆字節(jié)或更少
• 傳輸效率的提高：對于需要通過網(wǎng)絡進行傳輸?shù)膱D像，較大的圖像文件會占用更多的帶寬和傳輸時間。通過壓縮圖像，可以顯著降低傳輸所需的帶寬和時間成本。這對于在線圖片分享、視頻流媒體等應用非常重要
• 資源的優(yōu)化利用：在諸如移動設備、無人機、監(jiān)控攝像頭等資源受限的環(huán)境中，壓縮圖像可以減少處理和傳輸所需的計算資源和能源消耗。這有助于延長設備的電池壽命、提高處理速度，并降低硬件成本

例如，一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512′512像素，每像素的R、G、B三分量分別占8b，則總比特數(shù)為

$$90\times 60\times 24\times 3\times 512\times 512\times 8bit=97,200MB$$

因此，傳輸帶寬、速度、存儲器容量的限制使得對圖象數(shù)據(jù)進行壓縮顯得非常必要

（2）圖像壓縮的可能性

A：編碼冗余

編碼冗余：稱為信息熵冗余。如果一個圖像的灰度級編碼，使用了多于實際需要的編碼符號，就稱該圖像包含了編碼冗余\

例如下圖，如果用8bit表示該圖像的像素，那么則認為該圖像存在編碼冗余。因為該圖像的像素只有兩個灰度級，用1bit即可表示

在大多數(shù)圖像中，圖像像素的灰度值分布是不均勻的，因此若對圖像的灰度值直接進行自然二進制編碼（等長編碼），則會對有最大和最小概率可能性的值分配相同比特數(shù)，而產(chǎn)生了編碼冗余

用自然二進制編碼時沒有考慮像素灰度值出現(xiàn)的概率。只有按概率分配編碼長度，才是最精減的編碼方法。也即，灰度級出現(xiàn)概率大的用短碼表示，出現(xiàn)概率小的灰度級用長碼表示，則有可能使編碼總長度下降

B：像素間冗余

像素間冗余：對應圖像目標的像素之間一般具有相關性。因此，圖像中一般存在與像素間相關性直接聯(lián)系著的數(shù)據(jù)冗余——像素相關冗余。主要有

• 空間冗余：鄰近像素灰度分布的相關性很強
• 頻間冗余：多譜段圖像中各譜段圖像對應像素之間灰度相關性很強
• 時間冗余：序列圖像幀間畫面對應像素灰度的相關性很強
• 結(jié)構冗余：有些圖像存在較強的紋理結(jié)構或自相似性，如墻紙、草席等圖像
• 知識冗余：有些圖像中包含與某些先驗知識相關的信息

C：心理視覺冗余

心理視覺冗余：人的眼睛并不是對所有信息都有相同的敏感度，有些信息在通常的視覺感覺過程中與另外一些信息相比來說并不那么重要，這些信息可以認為是心理視覺冗余的

（3）圖像壓縮方法分類

A：基于編碼前后的信息保持程度的分類

• 信息保持編碼（無損編碼）： 在編解碼過程中保證圖像信息不丟失，通常壓縮比一般不超過3:1
• 保真度編碼（有損編碼）： 丟掉一些人眼不敏感的次要信息，在一定保真度準則下，最大限度地壓縮圖像
• 特征提取： 在圖像識別、分析和分類等技術中，只對感興趣部分特征進行編碼壓縮

B：基于編碼方法的分類

• 熵編碼： 基于信息統(tǒng)計特性的編碼技術。如行程編碼、Huffman編碼和算術編碼等
• 預測編碼： 常用的有差分脈沖編碼調(diào)制和運 動估計與補償預測編碼法
• 變換編碼： 將空間域圖像經(jīng)過正交變換映射 到另一變換域上，再采用適當?shù)?strong>量化和熵編碼來有效壓縮圖像。通常采用的變換：離散傅里葉變換（DFT）、離散余弦變換（DCT）和離散小波變換（DWT）等

C：其他方法

• 早起編碼方法：如混合編碼、矢量量化、LZW算法等

• 一些新的編碼方法

  • 人工神經(jīng)元網(wǎng)絡ANN的壓縮編碼
  • 分形編碼
  • 小波編碼
  • 基于模型的壓縮編碼
  • 基于對象的壓縮編碼
  • …

（4）圖像編碼術語

壓縮比：

$$r=\frac{n}{\bar{L}}=\frac{\text{?壓縮前每像素所占平均比特數(shù)目?}}{\text{?壓后每像素所占平均比特數(shù)目?}}$$

圖像熵：

• 令$p(d_i)$為數(shù)字圖像第$i$個灰度級$d_i$的出現(xiàn)概率

$$H=?\sum _{i=1}^{m}p\left(d_i\right){\log }_{2}p\left(d_i\right)\left(p^{pixel}/{}_{bit}\right)$$

平均碼字長度$\bar{L}$：

• 令$L_i$為數(shù)字圖像第$i$個灰度級$d_i$的編碼長度

$$\bar{L}=\sum _{i=1}^m{L}_{i}p\left(d_i\right)(\text{?pixel?}/\text{?bit?})$$

編碼效率：

$$\eta =\frac{H}{\bar{L}}\times 100\%$$

二：圖像的無損壓縮編碼

（1）無損編碼理論

Shannon無失真編碼定理：也稱為香農(nóng)編碼定理（Shannon’s source coding theorem），是信息論中的一個重要定理，由克勞德·香農(nóng)（Claude Shannon）在1948年提出。該定理表明，在一給定離散概率分布下，對于任意平均碼長小于熵的正數(shù)值，存在一種編碼方式可以使得編碼后的數(shù)據(jù)長度趨近于此平均碼長，并且解碼時不會引入任何失真。簡而言之，香農(nóng)無失真編碼定理表明，對于具有確定概率分布的離散信源，我們可以設計一種編碼方案，使得編碼后的數(shù)據(jù)盡可能地緊湊，接近其熵值。在解碼時，我們可以完全恢復原始的消息，沒有任何信息的丟失或失真。這個定理在信息壓縮領域具有重要的應用價值，它提供了一種理論基礎和算法思路，用于有效地壓縮數(shù)據(jù)并在解壓縮時還原原始信息。同時，無失真編碼定理也為其他信息論相關的研究和應用提供了重要參考和指導

如下，假設有一原始符號序列為

$$a_1{a}_4{a}_4{a}_1{a}_2{a}_1{a}_1{a}_4{a}_1{a}_3{a}_2{a}_1{a}_4{a}_1{a}_1$$

若采用等長編碼，等長編碼是將所有符號當作等概率事件處理的

若采用變字長編碼，變字長編碼是每個符號的碼字長度隨字符出現(xiàn)概率而變化

• $a_1$：8次
• $a_2$：2次
• $a_3$：1次
• $a_4$：4次

（2）霍夫曼編碼

A：概述

此部分內(nèi)容不在詳細介紹，請移步(王道408考研數(shù)據(jù)結(jié)構)第五章樹-第四節(jié)3：哈夫曼樹基本概念、構造和哈夫曼編碼

B：程序

實現(xiàn)圖像的霍夫曼編碼

---

matlab：

clc;clear;
%load image
Image=[7 2 5 1 4 7 5 0; 5 7 7 7 7 6 7 7; 2 7 7 5 7 7 5 4; 5 2 4 7 3 2 7 5;1 7 6 5 7 6 7 2; 3 3 7 3 5 7 4 1; 7 2 1 7 3 3 7 5; 0 3 7 5 7 2 7 4];
[h w]=size(Image);   totalpixelnum=h*w;
len=max(Image(:))+1;
for graynum=1:lengray(graynum,1)=graynum-1;%將圖像的灰度級統(tǒng)計在數(shù)組gray第一列
end
%將各個灰度出現(xiàn)的頻數(shù)統(tǒng)計在數(shù)組histgram中
for graynum=1:lenhistgram(graynum)=0;    gray(graynum,2)=0;for i=1:wfor j=1:hif gray(graynum,1)==Image(j,i)histgram(graynum)=histgram(graynum)+1;endendendhistgram(graynum)=histgram(graynum)/totalpixelnum;
end
histbackup=histgram;
%找到概率序列中最小的兩個，相加，依次增加數(shù)組hist的維數(shù)，存放每一次的概率和，同時將原概率屏蔽（置為1.1）；
%最小概率的序號存放在tree第一列中，次小的放在第二列
sum=0;     treeindex=1;
while(1)if sum>=1.0break;else[sum1,p1]=min(histgram(1:len));   histgram(p1)=1.1;[sum2,p2]=min(histgram(1:len));   histgram(p2)=1.1;sum=sum1+sum2;                len=len+1;          histgram(len)=sum;tree(treeindex,1)=p1;         tree(treeindex,2)=p2;treeindex=treeindex+1;        end
end
%數(shù)組gray第一列表示灰度值，第二列表示編碼碼值，第三列表示編碼的位數(shù)
for k=1:treeindex-1i=k;    codevalue=1;if or(tree(k,1)<=graynum,tree(k,2)<=graynum)if tree(k,1)<=graynumgray(tree(k,1),2)=gray(tree(k,1),2)+codevalue;codelength=1;while(i<treeindex-1)codevalue=codevalue*2;for j=i:treeindex-1if tree(j,1)==i+graynumgray(tree(k,1),2)=gray(tree(k,1),2)+codevalue;codelength=codelength+1;i=j;      break;elseif tree(j,2)==i+graynumcodelength=codelength+1;i=j;      break;endendendgray(tree(k,1),3)=codelength;endi=k;    codevalue=1;if tree(k,2)<=graynumcodelength=1;while(i<treeindex-1)codevalue=codevalue*2;for j=i:treeindex-1if tree(j,1)==i+graynumgray(tree(k,2),2)=gray(tree(k,2),2)+codevalue;codelength=codelength+1;i=j;      break;elseif tree(j,2)==i+graynumcodelength=codelength+1;i=j;   break;endendendgray(tree(k,2),3)=codelength;endend
end
%把gray數(shù)組的第二三列，即灰度的編碼值及編碼位數(shù)輸出
for k=1:graynumA{k}=dec2bin(gray(k,2),gray(k,3));
end
disp('編碼');
disp(A);

python：

import numpy as np
import matplotlib.pyplot as plt# Load image
Image = np.array([[7, 2, 5, 1, 4, 7, 5, 0],[5, 7, 7, 7, 7, 6, 7, 7],[2, 7, 7, 5, 7, 7, 5, 4],[5, 2, 4, 7, 3, 2, 7, 5],[1, 7, 6, 5, 7, 6, 7, 2],[3, 3, 7, 3, 5, 7, 4, 1],[7, 2, 1, 7, 3, 3, 7, 5],[0, 3, 7, 5, 7, 2, 7, 4]])h, w = Image.shape
totalpixelnum = h * w
len = np.max(Image) + 1gray = np.zeros((len, 3))
gray[:, 0] = np.arange(len)histgram = np.zeros(len)
for graynum in range(len):histgram[graynum] = np.sum(Image == graynum) / totalpixelnumhistbackup = histgram.copy()sum_val = 0
treeindex = 0
tree = np.zeros((len, 2))
while True:if sum_val >= 1.0:breakelse:p1 = np.argmin(histgram)histgram[p1] = 1.1p2 = np.argmin(histgram)histgram[p2] = 1.1sum_val = histbackup[p1] + histbackup[p2]len += 1histgram[len-1] = sum_valtree[treeindex, 0] = p1tree[treeindex, 1] = p2treeindex += 1gray[:, 1] = np.arange(len)for k in range(treeindex):i = kcodevalue = 1if tree[k, 0] <= graynum or tree[k, 1] <= graynum:if tree[k, 0] <= graynum:gray[int(tree[k, 0]), 1] += codevaluecodelength = 1while i < treeindex - 1:codevalue *= 2for j in range(i, treeindex - 1):if tree[j, 0] == i + graynum:gray[int(tree[k, 0]), 1] += codevaluecodelength += 1i = jbreakelif tree[j, 1] == i + graynum:codelength += 1i = jbreakgray[int(tree[k, 0]), 2] = codelengthi = kcodevalue = 1if tree[k, 1] <= graynum:codelength = 1while i < treeindex - 1:codevalue *= 2for j in range(i, treeindex - 1):if tree[j, 0] == i + graynum:gray[int(tree[k, 1]), 1] += codevaluecodelength += 1i = jbreakelif tree[j, 1] == i + graynum:codelength += 1i = jbreakgray[int(tree[k, 1]), 2] = codelength# Convert gray code to binary strings
A = [bin(int(x[1]))[2:].zfill(int(x[2])) for x in gray[:len]]# Display the encoding
print("編碼:")
for i, code in enumerate(A):print(f"{i}: {code}")# Plotting the image
plt.imshow(Image, cmap='gray')
plt.axis('off')
plt.show()

（3）算數(shù)編碼

A：概述

算數(shù)編碼：是一種無失真的數(shù)據(jù)壓縮技術，用于將源數(shù)據(jù)序列轉(zhuǎn)換為更緊湊的編碼序列。與傳統(tǒng)的固定長度編碼方法（如霍夫曼編碼）不同，算術編碼使用一個區(qū)間來表示整個源數(shù)據(jù)序列，而不是將每個符號映射到固定長度的編碼字。算術編碼的基本思想是利用符號出現(xiàn)的概率分布來為每個符號分配一個對應的區(qū)間，并根據(jù)輸入的符號序列逐步縮小區(qū)間范圍。最終，所生成的區(qū)間內(nèi)的任意一個數(shù)值都可以表示原始數(shù)據(jù)序列的唯一編碼?；静襟E如下

• 初始化：給定待編碼的符號序列和對應的概率分布。
• 創(chuàng)建初始區(qū)間：根據(jù)符號的概率分布，為每個符號分配一個區(qū)間。
• 編碼：根據(jù)每個輸入符號，按照其在當前區(qū)間的長度比例，更新區(qū)間的上界和下界。
• 重標定：根據(jù)區(qū)間的更新，進行重標定以保證精度和避免溢出。
• 輸出：當所有符號編碼完成后，輸出最終區(qū)間中的任意一個編碼值作為壓縮結(jié)果

算術編碼的優(yōu)勢在于可以實現(xiàn)接近熵編碼效率的壓縮比，尤其適用于符號概率分布不均勻、頻率較高的數(shù)據(jù)。然而，算術編碼的實現(xiàn)相對復雜且計算量大，同時對解碼過程中的精度要求較高。需要注意的是，由于算術編碼涉及到浮點數(shù)運算和精度處理，因此在實際應用中可能存在一定的誤差累積和舍入誤差問題。這些問題可以通過使用更高精度的數(shù)值表示或采用其他技巧來緩解?？傊?#xff0c;算術編碼是一種強大的數(shù)據(jù)壓縮技術，能夠提供較高的壓縮比，尤其適用于無損壓縮和對壓縮比要求較高的場景

B：程序

matlab：

%算術編碼
clc;clear;
%load image
%Image=[7 2 5 1 4 7 5 0;5 7 7 7 7 6 7 7;2 7 7 5 7 7 5 4;5 2 4 7 3 2 7 5;
%       1 7 6 5 7 6 7 2;3 3 7 3 5 7 4 1;7 2 1 7 3 3 7 5;0 3 7 5 7 2 7 4];
Image=[4 1 3 1 2];   
[h w col]=size(Image);   pixelnum=h*w;
graynum=max(Image(:))+1;
for i=1:graynumgray(i)=i-1;
end
histgram=zeros(1,graynum);
for i=1:wfor j=1:hpixel=uint8(Image(j,i)+1);histgram(pixel)=histgram(pixel)+1;          end    
end
histgram=histgram/pixelnum;%將各個灰度出現(xiàn)的頻數(shù)統(tǒng)計在數(shù)組histgram中
disp('灰度級');disp(num2str(gray));
disp('概率');disp(num2str(histgram))
disp('每一行字符串及其左右編碼：')
for j=1:hstr=num2str(Image(j,:));    left=0;    right=0;intervallen=1;              len=length(str);for i=1:lenif str(i)==' 'continue;endm=str2num(str(i))+1;      pl=0;        pr=0;for j=1:m-1pl=pl+histgram(j);endfor j=1:mpr=pr+histgram(j);endright=left+intervallen*pr; left=left+intervallen*pl;%間隔區(qū)間起始和終止端點           intervallen=right-left; %  間隔區(qū)間寬度     end%輸入圖像信息數(shù)據(jù)disp(str);  %編碼輸出間隔區(qū)間disp(num2str(left));  disp(num2str(right))    temp=0;  a=1;while(1)left=2*left;right=2*right;if floor(left)~=floor(right)break;endtemp=temp+floor(left)*2^(-a);a=a+1;left=left-floor(left);right=right-floor(right);endtemp=temp+2^(-a);ll=a;%尋找最后區(qū)間內(nèi)的最短二進制小數(shù)和所需的比特位數(shù)disp(num2str(temp));  disp(ll);    %算術編碼的編碼碼字輸出：disp('算術編碼的編碼碼字輸出：'); %yy=DEC2bin(temp,ll);%簡單的將10進制轉(zhuǎn)化為N為2進制小數(shù)for ii= 1: lltemp1=temp*2;yy(ii)=floor(temp1);temp=temp1-floor(temp1);enddisp(num2str(yy));    
end

python：

import numpy as np# 算術編碼
# load image
Image = np.array([[4, 1, 3, 1, 2]])
[h, w] = Image.shape
pixelnum = h * w
graynum = np.max(Image) + 1gray = np.arange(graynum)histgram = np.zeros(graynum)
for i in range(w):for j in range(h):pixel = Image[j, i]histgram[pixel] += 1histgram /= pixelnum
print('灰度級:', gray)
print('概率:', histgram)print('每一行字符串及其左右編碼：')
for j in range(h):str_ = [str(x) for x in Image[j]]left = 0right = 0intervallen = 1len_ = len(str_)for i in range(len_):if str_[i] == ' ':continuem = int(str_[i]) + 1pl = np.sum(histgram[:m-1])pr = np.sum(histgram[:m])right = left + intervallen * prleft = left + intervallen * plintervallen = right - leftprint(''.join(str_))print(left, right)temp = 0a = 1while True:left *= 2right *= 2if int(left) != int(right):breaktemp += int(left) * pow(2, -a)a += 1left -= int(left)right -= int(right)temp += pow(2, -a)ll = aprint(temp, ll)print('算術編碼的編碼碼字輸出：')yy = []for ii in range(ll):temp1 = temp * 2yy.append(int(temp1))temp = temp1 - int(temp1)print(yy)

（4）LZW編碼

A：概述

**LZW編碼：是一種用于數(shù)據(jù)壓縮的無損壓縮算法，它可以將輸入數(shù)據(jù)中的重復模式編碼為更短的代碼，從而減小數(shù)據(jù)的存儲空間。LZW編碼最初由Terry Welch在1984年提出，廣泛應用于圖像、音頻和文本等領域。LZW編碼的基本思想是利用字典來對輸入數(shù)據(jù)進行編碼。初始時，字典中包含所有可能的單個字符作為鍵，以及相應的編號作為值。然后，從輸入數(shù)據(jù)的開頭開始，逐步掃描輸入數(shù)據(jù)，并檢查當前掃描的序列是否已經(jīng)在字典中存在。如果已存在，則繼續(xù)向后掃描并將當前序列與下一個字符拼接，直到找到一個新的序列。此時，將該新序列的編號輸出，并將這個新序列添加到字典中，以供后續(xù)的編碼使用。整個過程持續(xù)進行，直到掃描完整個輸入數(shù)據(jù)。LZW編碼的關鍵是維護一個動態(tài)更新的字典。在編碼過程中，字典不斷增長，并根據(jù)輸入數(shù)據(jù)中的模式進行更新。因此，相同的輸入數(shù)據(jù)可以使用不同長度的編碼表示，具有較高的壓縮比

B：程序

matlab：

clc;clear;
Image=[30 30 30 30;110 110 110 110;30 30 30 30;110 110 110 110];
[h w col]=size(Image);
pixelnum=h*w;     graynum=256;
%graynum=max(Image(:))+1;
if col==1    graystring=reshape(Image',1,pixelnum);%灰度圖像從二維變?yōu)橐痪S信號for tablenum=1:graynumtable{tablenum}=num2str(tablenum-1);endlen=length(graystring);   lzwstring(1)=graynum;R='';         stringnum=1;for i=1:lenS=num2str(graystring(i));RS=[R,S];      flag=ismember(RS,table);if flagR=RS;elselzwstring(stringnum)=find(cellfun(@(x)strcmp(x,R),table))-1;stringnum=stringnum+1;     tablenum=tablenum+1;table{tablenum}=RS;        R=S;endendlzwstring(stringnum)=find(cellfun(@(x)strcmp(x,R),table))-1;disp('LZW碼串： ')disp(lzwstring)
end

python：

import numpy as npImage = np.array([[30, 30, 30, 30],[110, 110, 110, 110],[30, 30, 30, 30],[110, 110, 110, 110]])[h, w] = Image.shape
pixelnum = h * w
graynum = 256if Image.ndim == 2:graystring = Image.T.flatten()table = {str(i): i for i in range(graynum)}lzwstring = [graynum]R = ''stringnum = 1for i in range(len(graystring)):S = str(graystring[i])RS = R + Sif RS in table:R = RSelse:lzwstring.append(table[R])stringnum += 1tablenum = len(table)table[RS] = tablenumR = Slzwstring.append(table[R])print('LZW碼串：')print(lzwstring)