圖像信息處理的技術(shù)

1、關(guān)于圖像信息處理技術(shù)第1頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四4.1 圖像信號(hào)概述 圖像是一種可視化的信息， 圖像信號(hào)是圖像信息的理論描述方法， 圖像信號(hào)按其內(nèi)容變化與時(shí)間的關(guān)系來(lái)分， 主要包括靜態(tài)圖像和動(dòng)態(tài)圖像兩種。 靜態(tài)圖像其信息密度隨空間分布， 且相對(duì)時(shí)間為常量； 動(dòng)態(tài)圖像也稱(chēng)時(shí)變圖像， 其空間密度特性是隨時(shí)間而變化的。 人們經(jīng)常用靜態(tài)圖像的一個(gè)時(shí)間序列來(lái)表示一個(gè)動(dòng)態(tài)圖像。 第2頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 圖像分類(lèi)還可以按其他方式進(jìn)行： 如按其亮度等級(jí)的不同可分為二值圖像和灰度圖像； 按其色調(diào)的不同可分為黑白圖像和彩色圖像； 按其所占空

2、間的維數(shù)不同可分為平面的二維圖像和立體的三維圖像等等。 圖像信號(hào)的記錄、 存儲(chǔ)和傳輸可以采用模擬方式或數(shù)字方式。 傳統(tǒng)的方式為模擬方式， 例如， 目前我們?cè)陔娨暽纤?jiàn)到的圖像就是以一種模擬電信號(hào)的形式來(lái)記錄， 并依靠模擬調(diào)幅的手段在空間傳播的。 將模擬圖像信號(hào)經(jīng)A/D變換后就得到數(shù)字圖像信號(hào)， 數(shù)字圖像信號(hào)便于進(jìn)行各種處理， 例如最常見(jiàn)的壓縮編碼處理就是在此基礎(chǔ)上完成的。 本書(shū)介紹的圖像信息處理技術(shù)就是針對(duì)數(shù)字圖像信號(hào)的。 第3頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 1 彩色圖像信號(hào)的分量表示 對(duì)于黑白圖像信號(hào)， 每個(gè)像素點(diǎn)用灰度級(jí)來(lái)表示， 若用數(shù)字表示一個(gè)像素點(diǎn)的灰度，

3、有8比特就夠了， 因?yàn)槿搜蹖?duì)灰度的最大分辨力為26。 對(duì)于彩色視頻信號(hào)（例如常見(jiàn)的彩色電視信號(hào)）均基于三基色原理， 每個(gè)像素點(diǎn)由紅（R）、 綠（G）、 藍(lán)（B）三基色混合而成。 若三個(gè)基色均用8比特來(lái)表示， 則每個(gè)像素點(diǎn)就需要24比特， 由于構(gòu)成一幅彩色圖像需要大量的像素點(diǎn)， 因此， 圖像信號(hào)采樣、 量化后的數(shù)據(jù)量就相當(dāng)大， 不便于傳輸和存儲(chǔ)。 第4頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 為了解決此問(wèn)題， 人們找到了相應(yīng)的解決方法： 利用人的視覺(jué)特性降低彩色圖像的數(shù)據(jù)量， 這種方法往往把RGB空間表示的彩色圖像變換到其他彩色空間， 每一種彩色空間都產(chǎn)生一種亮度分量和兩種色度

4、分量信號(hào)。 常用的彩色空間表示法有YUV、 YIQ和YCbCr等。 第5頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 （1） YUV彩色空間。 通常我們用彩色攝像機(jī)來(lái)獲取圖像信息， 攝像機(jī)把彩色圖像信號(hào)經(jīng)過(guò)分色棱鏡分成R0、 G0、 B0三個(gè)分量信號(hào)， 分別經(jīng)過(guò)放大和r校正得到RGB， 再經(jīng)過(guò)矩陣變換電路得到亮度信號(hào)Y和色差信號(hào)U、 V， 其中亮度信號(hào)表示了單位面積上反射光線(xiàn)的強(qiáng)度， 而色差信號(hào)（所謂色差信號(hào)， 就是指基色信號(hào)中的三個(gè)分量信號(hào)R、 G、 B與亮度信號(hào)之差）決定了彩色圖像信號(hào)的色調(diào)。 最后發(fā)送端將Y、 U、 V三個(gè)信號(hào)進(jìn)行編碼， 用同一信道發(fā)送出去， 這就是在PAL

5、彩色電視制式中使用的YUV彩色空間。 YUV與RGB彩色空間變換的對(duì)應(yīng)關(guān)系如式（4.1-1）所示。 第6頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 YUV彩色空間的一個(gè)優(yōu)點(diǎn)是， 它的亮度信號(hào)Y和色差信號(hào)U、 V是相互獨(dú)立的， 即Y信號(hào)分量構(gòu)成的黑白灰度圖與用U、 V兩個(gè)色彩分量信號(hào)構(gòu)成的兩幅單色圖是相互獨(dú)立的。 因?yàn)閅UV是獨(dú)立的， 所以可以對(duì)這些單色圖分別進(jìn)行編碼。 此外， 利用YUV之間的獨(dú)立性解決了彩色電視機(jī)與黑白電視機(jī)的兼容問(wèn)題。 （4.1-1） 第7頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 YUV表示法的另一個(gè)優(yōu)點(diǎn)是， 可以利用人眼的視覺(jué)特性來(lái)降低數(shù)

6、字彩色圖像的數(shù)據(jù)量。 人眼對(duì)彩色圖像細(xì)節(jié)的分辨能力比對(duì)黑白圖像細(xì)節(jié)的分辨能力低得多， 因此就可以降低彩色分量的分辨率而不會(huì)明顯影響圖像質(zhì)量， 即可以把幾個(gè)相同像素不同的色彩值當(dāng)做相同的色彩值來(lái)處理（即大面積著色原理）， 從而減少了所需的數(shù)據(jù)量。 在PAL彩色電視制式中， 亮度信號(hào)的帶寬為4.43 MHz， 用以保證足夠的清晰度， 而把色差信號(hào)的帶寬壓縮為1.3 MHz， 達(dá)到了減少帶寬的目的。 第8頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 在數(shù)字圖像處理的實(shí)際操作中， 就是對(duì)亮度信號(hào)Y和色差信號(hào)U、 V分別采用不同的采樣頻率。 目前常用的Y、 U、 V采樣頻率的比例有422和

7、411， 當(dāng)然， 根據(jù)要求的不同， 還可以采用其他比例。 例如要存儲(chǔ)RGB888的彩色圖像， 即R、 G、 B分量都用8比特表示， 圖像的大小為640480像素， 那么所需要的存儲(chǔ)容量為64048038/8921 600字節(jié)； 如果用YUV411來(lái)表示同一幅彩色圖像， 對(duì)于亮度信號(hào)Y， 每個(gè)像素仍用8比特表示， 而對(duì)于色差信號(hào)U、 V， 每4個(gè)像素用8比特表示， 則存儲(chǔ)量變?yōu)?40480(8+4)/8460 800字節(jié)。 盡管數(shù)據(jù)量減少了一半， 但人眼察覺(jué)不出有明顯變化。 第9頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 （2） YIQ彩色空間。 在NTSC彩色電視制式中選用YI

8、Q彩色空間， 其中Y表示亮度， I、 Q是兩個(gè)彩色分量。 I、 Q與U、 V是不相同的。 人眼的彩色視覺(jué)特性表明， 人眼對(duì)紅、 黃之間顏色變化的分辨能力最強(qiáng)； 而對(duì)藍(lán)、 紫之間顏色變化的分辨能力最弱。 在YIQ彩色空間中， 色彩信號(hào)I表示人眼最敏感的色軸， Q表示人眼最不敏感的色軸。 在NTSC制式中， 傳送人眼分辨能力較強(qiáng)的I信號(hào)時(shí)， 用較寬的頻帶（1.31.5 MHz）； 而傳送人眼分辨能力較弱的Q信號(hào)時(shí)， 用較窄的頻帶（0.5 MHz）。 YIQ與RGB彩色空間變換的對(duì)應(yīng)關(guān)系如式(4.1-2)所示。 第10頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四（4.1-2） 第11頁(yè)

9、，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 （3） YCbCr彩色空間。 YCbCr彩色空間是由ITU-R（國(guó)際電聯(lián)無(wú)線(xiàn)標(biāo)準(zhǔn)部， 原國(guó)際無(wú)線(xiàn)電咨詢(xún)委員會(huì)CCIR）制定的彩色空間。 按照CCIR601-2標(biāo)準(zhǔn)， 將非線(xiàn)性的RGB信號(hào)編碼成YCbCr， 編碼過(guò)程開(kāi)始是先采用符合SMPTE-CRGB（它定義了三種熒光粉， 即一種參考白光， 應(yīng)用于演播室監(jiān)視器及電視接收機(jī)標(biāo)準(zhǔn)的RGB）的基色作為r校正信號(hào)。 第12頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 非線(xiàn)性RGB信號(hào)很容易與一個(gè)常量矩陣相乘而得到亮度信號(hào)Y和兩個(gè)色差信號(hào)Cb、 Cr。 YCbCr通常在圖像壓縮時(shí)作為

10、彩色空間， 而在通信中是一種非正式標(biāo)準(zhǔn)。 YCbCr與RGB彩色空間變換的對(duì)應(yīng)關(guān)系如式（4.1-3）所示， 可以看到： 數(shù)字域中的彩色空間變換與模擬域中的彩色空間變換是不同的。 （4.1-3） 第13頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 2 彩色圖像信號(hào)的分量編碼 通過(guò)圖像信號(hào)的表示方法的討論可以看到： 對(duì)于彩色圖像信號(hào)數(shù)字壓縮編碼， 可以采用兩種不同的編解碼方案。 一種是復(fù)合編碼， 它直接對(duì)復(fù)合圖像信號(hào)進(jìn)行采樣、 編碼和傳輸； 另一種是分量編碼， 它首先把復(fù)合圖像中的亮度和色度信號(hào)分離出來(lái)， 然后分別進(jìn)行取樣、 編碼和傳輸。 目前分量編碼已經(jīng)成為圖像信號(hào)壓縮的主流， 在

11、20世紀(jì)90年代以來(lái)頒布的一系列圖像壓縮國(guó)際標(biāo)準(zhǔn)中均采用分量編碼方案。 以YUV彩色空間為例， 分量編碼系統(tǒng)的基本框圖如圖4.1-1所示， 其中對(duì)亮度信號(hào)Y使用較高的采樣頻率， 對(duì)色差信號(hào)U、 V則使用較低的采樣頻率。 第14頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四圖4.1-1 彩色圖像信號(hào)分量編碼系統(tǒng)的基本框圖 第15頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四4.2 圖像信號(hào)數(shù)字化 圖像信號(hào)數(shù)字化與音頻數(shù)字化一樣主要包括兩方面的內(nèi)容： 取樣和量化。 圖像在空間上的離散化稱(chēng)為取樣， 即使空間上連續(xù)變化的圖像離散化， 也就是用空間上部分點(diǎn)的灰度值來(lái)表示圖像， 這

12、些點(diǎn)稱(chēng)為樣點(diǎn)（或像素， 像元， 樣本）。 一幅圖像應(yīng)取多少樣點(diǎn)呢？其約束條件是： 由這些樣點(diǎn)采用某種方法能夠正確重建原圖像。 第16頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 取樣的方法有兩類(lèi)： 一類(lèi)是直接對(duì)表示圖像的二維函數(shù)值進(jìn)行取樣， 即讀取各離散點(diǎn)上的信號(hào)值， 所得結(jié)果就是一個(gè)樣點(diǎn)值陣列， 所以也稱(chēng)為點(diǎn)陣取樣； 另一類(lèi)是先將圖像函數(shù)進(jìn)行正交變換， 用其變換系數(shù)作為取樣值， 故稱(chēng)為正交系數(shù)取樣。 對(duì)樣點(diǎn)灰度級(jí)值的離散化過(guò)程稱(chēng)為量化， 也就是對(duì)每個(gè)樣點(diǎn)值數(shù)字化， 使其和有限個(gè)可能電平數(shù)中的一個(gè)對(duì)應(yīng)， 即使圖像的灰度級(jí)值離散化。 量化也可分為兩種： 一種是將樣點(diǎn)灰度級(jí)值等間隔分

13、檔取整， 稱(chēng)為均勻量化； 另一種是將樣點(diǎn)灰度級(jí)值不等間隔分檔取整， 稱(chēng)為非均勻量化。 第17頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 4.2.1 取樣點(diǎn)數(shù)和量化級(jí)數(shù)的選取 假定一幅圖像取MN個(gè)樣點(diǎn)， 對(duì)樣點(diǎn)值進(jìn)行Q級(jí)分檔取整。 那么對(duì)M， N和Q如何取值呢？ 首先， M， N， Q一般總是取2的整數(shù)次冪， 如Q = 2b ， b為正整數(shù)， 通常稱(chēng)為對(duì)圖像進(jìn)行b比特量化， M、 N可以相等， 也可以不相等。 若取相等， 則圖像距陣為方陣， 分析運(yùn)算方便一些。 其次， 關(guān)于M、 N和b(或Q)數(shù)值大小的確定。 對(duì)b來(lái)講， 取值越大， 重建圖像失真越小。 若要完全不失真地重建原圖像

14、， 則b必須取無(wú)窮大， 否則一定存在失真， 即所謂的量化誤差。 第18頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 一般供人眼觀察的圖像， 由于人眼對(duì)灰度分辨能力有限， 用58比特量化即可。 對(duì)MN的取值主要依據(jù)取樣的約束條件。 也就是在MN大到滿(mǎn)足取樣定理的情況下， 重建圖像就不會(huì)產(chǎn)生失真， 否則就會(huì)因取樣點(diǎn)數(shù)不夠而產(chǎn)生所謂混淆失真。 為了減少表示圖像的比特?cái)?shù)， 應(yīng)取MN點(diǎn)數(shù)剛好滿(mǎn)足取樣定理。 這種狀態(tài)的取樣即為奈奎斯特取樣。 MN常用的尺寸有512512， 256256， 6464， 3232等。 第19頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 再次， 在實(shí)

15、際應(yīng)用中， 如果允許表示圖像的總比特?cái)?shù)MNb給定， 對(duì)MN和b的分配往往是根據(jù)圖像的內(nèi)容和應(yīng)用要求以及系統(tǒng)本身的技術(shù)指標(biāo)來(lái)選定的。 例如， 若圖像中有大面積灰度變化緩慢的平滑區(qū)域如人圖像的特寫(xiě)照片等， 則MN取樣點(diǎn)可以少些， 而量化比特?cái)?shù)b多些， 這樣可使重建圖像灰度層次多些。 若b太少， 在圖像平滑區(qū)往往會(huì)出現(xiàn)“假輪廓”。第20頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 反之， 對(duì)于復(fù)雜景物圖像， 如群眾場(chǎng)面的照片等， 量化比特?cái)?shù)b可以少些， 而取樣點(diǎn)數(shù)MN要多些， 這樣就不會(huì)丟失圖像的細(xì)節(jié)。 究竟MN和b如何組合才能獲得滿(mǎn)意的結(jié)果很難講出一個(gè)統(tǒng)一的方案， 但是有一點(diǎn)是可以肯

16、定的： 不同的取樣點(diǎn)數(shù)和量化比特?cái)?shù)組合可以獲得相同的主觀質(zhì)量評(píng)價(jià)。 第21頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 *4.2.2 點(diǎn)陣取樣 在分析取樣和重建圖像時(shí)， 往往認(rèn)為取樣系統(tǒng)的輸入圖像是一個(gè)確定的圖像場(chǎng)， 即為確知函數(shù)， 如一幅照片或膠片。 但是在某些情況下， 如電視圖像由于噪聲影響和取樣方式變化， 把這種取樣看成是二維隨機(jī)過(guò)程的取樣更為有益， 當(dāng)然實(shí)際取樣還有一些問(wèn)題要注意。 第22頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 1. 確定圖像場(chǎng)的點(diǎn)陣取樣原理 對(duì)理想取樣而言， 其取樣函數(shù)為空間抽樣函數(shù) S（x,y）， 離散形式可表示為（4.2-1） 函

17、數(shù)的取樣陣列如圖4.2-1所示。 第23頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四圖4.2-1 函數(shù)的取樣陣列 第24頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 令fI(x,y)代表一理想的無(wú)限大連續(xù)圖像場(chǎng)， 其點(diǎn)陣取樣方法就是用空間抽樣函數(shù)S(x,y)和連續(xù)圖像函數(shù)fI(x,y)相乘。 設(shè)fS(x,y)表示取樣后的圖像， 理想取樣數(shù)學(xué)模型如圖4.2-2所示。 圖4.2-2 理想取樣數(shù)學(xué)模型 第25頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四由此可以得到 （4.2-2） 第26頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 式中, 連續(xù)

18、函數(shù)fI(x,y)移入求和式內(nèi)變?yōu)殡x散形式fI(ix, jy)， 表明只是在取樣點(diǎn)(ix, jy)上計(jì)值。 根據(jù)二維傅立葉變換卷積定理， 可以得到頻域關(guān)系式為 （4.2-3） 式中 第27頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 假定理想圖像的頻譜是有限的， 截止頻率為uc和vc， 根據(jù)函數(shù)的篩選性質(zhì)對(duì)式(4.2-3)進(jìn)一步運(yùn)算可以得式(4.2-4)和如圖4.2-3所示的取樣圖像頻譜示意圖。 （4.2-4） 第28頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四圖4.2-3 取樣圖像頻譜示意圖 第29頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 由式（

19、4.2-4）和圖4.2-3可以看出， 取樣圖像頻譜是原圖像頻譜在頻域中的無(wú)窮多個(gè)重復(fù)。 重復(fù)頻譜之間間隔u和v取決于取樣間隔x和y的大小， 只要選取合適的x、 y， 就能保證u、 v等于或大于原圖像截止頻率2uc、 2vc， 那么各個(gè)重復(fù)頻譜之間就不會(huì)重疊。 在這種情況下， 選用合適的二維重建濾波器， 就可以取出一個(gè)完整的原圖像頻譜（即除所有i, j0的頻譜成分）， 再由二維傅立葉反變換獲得和原圖像一樣的重建圖像 。 第30頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 取樣正確與否的原則是能否由取樣圖像不失真地重建原圖像， 而正確取樣的關(guān)鍵是取樣間隔x、 y的選擇， 因此保證正確

20、取樣的條件是因?yàn)?（4.2-5）第31頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四所以 則 （4.2-6）第32頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 滿(mǎn)足式(4.2-5)和式(4.2-6)中“等于”條件的取樣稱(chēng)為奈奎斯特取樣。 滿(mǎn)足兩式中大于條件的取樣稱(chēng)為過(guò)取樣， 而不滿(mǎn)足上述兩條件的取樣稱(chēng)為欠取樣。 在欠取樣情況下， 會(huì)產(chǎn)生混淆失真。 混淆失真是取樣中應(yīng)注意的一個(gè)重要問(wèn)題。 防止出現(xiàn)混淆失真的辦法， 從理論上講， 若已知原圖像頻譜的最高頻率成分， 則使用過(guò)取樣或奈奎斯特取樣， 而不要使用欠取樣； 第33頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星

21、期四 但若不知道原圖像頻譜的最高頻率成分， 則應(yīng)先采用已知截止頻率的低通濾波器預(yù)先過(guò)濾圖像， 限制其高頻率成分， 再針對(duì)低通濾波器截止頻率進(jìn)行過(guò)取樣或奈奎斯特取樣。 在實(shí)際取樣系統(tǒng)中， 取樣脈沖寬帶效應(yīng)相當(dāng)于一個(gè)低通濾波器， 另外光學(xué)系統(tǒng)的透鏡散焦， 孔闌衍射也都可以等效為低通濾波器的作用， 盡管會(huì)引起圖像模糊降質(zhì)， 但對(duì)防止混淆失真卻是有好處的。第34頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 2. 隨機(jī)圖像場(chǎng)取樣 實(shí)際圖像往往有噪聲， 這種附加有噪聲的確定圖像場(chǎng)可以認(rèn)為是隨機(jī)圖像場(chǎng)， 因此這里簡(jiǎn)單介紹一下隨機(jī)圖像場(chǎng)的取樣。 式中, x=x1-x2; y=y1-y2。第35頁(yè)

22、，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 用狄拉克取樣函數(shù)S（x,y）對(duì)這個(gè)隨機(jī)過(guò)程進(jìn)行取樣所獲得的取樣場(chǎng)為（4.2-8） 因而取樣場(chǎng)的自相關(guān)函數(shù)為 （4.2-9） 第36頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 根據(jù)狄拉克函數(shù)性質(zhì)： 兩個(gè)狄拉克函數(shù)相乘還是一個(gè)狄拉克函數(shù)， 即 S(x1,y1)S(x2,y2)=S(x1-x2,y1-y2)=S(x,y) （4.2-10）將式（4.2-7）和式（4.2-10）代入式（4.2-9）即可得第37頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四對(duì)上式兩邊取二維傅立葉變換， 根據(jù)傅氏變換定理得（4.2-11）

23、 （4.2-12） 第38頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四圖4.2-4 有噪聲圖像的取樣（一維示意圖） 第39頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 4.2.3 圖像信號(hào)量化 經(jīng)過(guò)取樣的圖像只是在空間上被離散為像素（樣本）的陣列， 而每一個(gè)樣本灰度值還是一個(gè)有無(wú)窮多個(gè)取值的連續(xù)變化量， 必須將其轉(zhuǎn)化為有限個(gè)離散值， 賦予不同碼字才能真正成為數(shù)字圖像， 再由計(jì)算機(jī)或其他數(shù)字設(shè)備進(jìn)行處理運(yùn)算， 這樣的轉(zhuǎn)化過(guò)程稱(chēng)為量化。 將樣本連續(xù)灰度等間隔分層量化方式稱(chēng)為均勻量化， 不等間隔分層量化方式稱(chēng)為非均勻量化。 量化既然以有限個(gè)離散值來(lái)近似表示無(wú)限多個(gè)連續(xù)量，

24、 就一定會(huì)產(chǎn)生誤差， 這就是所謂的量化誤差。 第40頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 由此產(chǎn)生的失真叫量化失真或量化噪聲， 對(duì)均勻量化來(lái)講， 量化分層越多， 量化誤差越小， 但編碼時(shí)占用比特?cái)?shù)就越多。 在一定比特?cái)?shù)下， 為了減少量化誤差， 往往要用非均勻量化， 如按圖像灰度值出現(xiàn)的概率大小不同進(jìn)行非均勻量化， 即對(duì)灰度值經(jīng)常出現(xiàn)的區(qū)域進(jìn)行細(xì)量化， 反之進(jìn)行粗量化。 在實(shí)際圖像系統(tǒng)中， 由于存在著成像系統(tǒng)引入的噪聲及圖像本身的噪聲， 因此量化等級(jí)取得太多（量化間隔太?。┦菦](méi)有必要的， 因?yàn)槿绻肼暦戎荡笥诹炕g隔， 量化器輸出的量化值就會(huì)產(chǎn)生錯(cuò)誤， 得到不正確的量化。

25、 第41頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 在應(yīng)用屏幕顯示其輸出圖像時(shí)， 灰度鄰近區(qū)域邊界會(huì)出現(xiàn)“忙動(dòng)”現(xiàn)象。 假設(shè)噪聲是高斯分布， 均值為0， 方差為2， 在有噪聲情況下， 最佳量化層選取有兩種方法， 一是令正確量化的概率大于某一個(gè)值， 二是使量化誤差的方差等于噪聲方差。 針對(duì)輸出圖像是專(zhuān)供人觀察評(píng)價(jià)的應(yīng)用， 研究出了一些按人的視覺(jué)特性進(jìn)行非均勻量化方式， 如圖像灰度變化緩慢部分細(xì)量化， 而圖像灰度變化快的細(xì)節(jié)部分粗量化， 這是由于視覺(jué)掩蓋效應(yīng)被發(fā)現(xiàn)而產(chǎn)生的。 再如按人的視覺(jué)靈敏度特征進(jìn)行對(duì)數(shù)形式量化分層等。 第42頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，

26、星期四4.3 數(shù)字圖像壓縮方法的分類(lèi) 圖像壓縮的基本目標(biāo)就是減小數(shù)據(jù)量， 但最好不要引起圖像質(zhì)量的明顯下降， 在大多數(shù)實(shí)際應(yīng)用中， 為了取得較低的比特率， 輕微的質(zhì)量下降是允許的。 至于圖像壓縮到什么程度而沒(méi)有明顯的失真， 則取決于圖像數(shù)據(jù)的冗余度。 較高的冗余度形成較大的壓縮， 而典型的圖像信號(hào)都具有很高的冗余度， 正是這些冗余度的存在允許我們對(duì)圖像進(jìn)行壓縮。 第43頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 例如， 我們?cè)诘?章介紹的空間冗余和時(shí)間冗余是圖像信號(hào)最常見(jiàn)的冗余， 所有的這些冗余度都可以被除去而不會(huì)引起顯著的信息損失， 但壓縮編碼無(wú)法減少冗余度。 不同的出發(fā)點(diǎn)有

27、不同的分類(lèi)， 按照信息論的角度， 數(shù)字圖像壓縮方法一般可分為： （1） 可逆編碼（Reversible Coding 或Information Preserving Coding）， 也稱(chēng)為無(wú)損壓縮。 這種方法的解碼圖像與原始圖像嚴(yán)格相同， 壓縮是完全可恢復(fù)的或無(wú)偏差的， 無(wú)損壓縮不能提供較高的壓縮比。 第44頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 （2） 不可逆編碼（Non-Reversible Coding）， 也稱(chēng)為有損壓縮。 用這種方法恢復(fù)的圖像較原始圖像存在一定的誤差， 但視覺(jué)效果一般是可接受的， 它可提供較高的壓縮比。 第45頁(yè)，共438頁(yè)，2022年，5月20

28、日，5點(diǎn)12分，星期四 按照壓縮方法的原理， 數(shù)字圖像壓縮方法可分為： （1） 預(yù)測(cè)編碼（Predictive Coding）。 預(yù)測(cè)編碼是一種針對(duì)統(tǒng)計(jì)冗余進(jìn)行壓縮的方法， 它主要是減少數(shù)據(jù)在空間和時(shí)間上的相關(guān)性， 達(dá)到對(duì)數(shù)據(jù)的壓縮， 是一種有失真的壓縮方法。 預(yù)測(cè)編碼中典型的壓縮方法有DPCM和ADPCM等， 它們比較適合于圖像數(shù)據(jù)的壓縮。 第46頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 （2） 變換編碼（Transform Coding）。 變換編碼也是一種針對(duì)統(tǒng)計(jì)冗余進(jìn)行壓縮的方法。 這種方法將圖像光強(qiáng)矩陣（時(shí)域信號(hào)）變換到系數(shù)空間（頻域）上進(jìn)行處理。 常用的正交變換有

29、DFT（離散傅氏變換）、 DCT（離散余弦變換）、 DST（離散正弦變換）、 哈達(dá)碼變換和Karhunen-Loeve變換。 第47頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 （3） 量化和矢量量化編碼（Vector Quantization）。 量化和矢量量化編碼本質(zhì)上也還是一種針對(duì)統(tǒng)計(jì)冗余進(jìn)行壓縮的方法。 當(dāng)我們對(duì)模擬量進(jìn)行數(shù)字化時(shí)， 必然要經(jīng)歷一個(gè)量化的過(guò)程。 在這里量化器的設(shè)計(jì)是一個(gè)很關(guān)鍵的步驟， 量化器設(shè)計(jì)的好壞對(duì)于量化誤差的大小有直接的影響。 矢量量化是相對(duì)于標(biāo)量量化而提出的， 如果我們一次量化多個(gè)點(diǎn)， 則稱(chēng)為矢量量化。 第48頁(yè)，共438頁(yè)，2022年，5月20日

30、，5點(diǎn)12分，星期四 （4） 信息熵編碼（Entropy Coding）。 根據(jù)信息熵原理， 用短的碼字表示出現(xiàn)概率大的信息， 用長(zhǎng)的碼字表示出現(xiàn)概率小的信息。 常見(jiàn)的方法有哈夫曼編碼、 游程編碼以及算術(shù)編碼。 （5） 子帶編碼（Sub-band Coding）。 子帶編碼將圖像數(shù)據(jù)變換到頻域后， 按頻率分帶， 然后用不同的量化器進(jìn)行量化， 從而達(dá)到最優(yōu)的組合。 或者是分步漸近編碼， 在初始時(shí)對(duì)某一頻帶的信號(hào)進(jìn)行解碼， 然后逐漸擴(kuò)展到所有頻帶， 隨著解碼數(shù)據(jù)的增加， 解碼圖像也逐漸地清晰起來(lái)。 此方法對(duì)于遠(yuǎn)程圖像模糊查詢(xún)與檢索的應(yīng)用比較有效。 第49頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)

31、12分，星期四 （6） 結(jié)構(gòu)編碼（Structure Coding）， 也稱(chēng)為第二代編碼（Second Generation Coding）。 編碼時(shí)首先求出圖像中的邊界、 輪廓、 紋理等結(jié)構(gòu)特征參數(shù)， 然后保存這些參數(shù)信息。 解碼時(shí)根據(jù)結(jié)構(gòu)和參數(shù)信息進(jìn)行合成， 從而恢復(fù)出原圖像。 （7） 基于知識(shí)的編碼（Knowledge-Based Coding）。 對(duì)于人臉等可用規(guī)則描述圖像， 利用人們對(duì)其的知識(shí)形成一個(gè)規(guī)則庫(kù)， 據(jù)此將人臉的變化等特征用一些參數(shù)進(jìn)行描述， 從而用參數(shù)加上模型就可以實(shí)現(xiàn)人臉的圖像編碼與解碼。圖像壓縮算法的總體框圖如圖4.3-1所示。 第50頁(yè)，共438頁(yè)，2022年，5月

32、20日，5點(diǎn)12分，星期四圖4.3-1 圖像壓縮算法的總體框圖 第51頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 下面幾節(jié)主要介紹幾種常見(jiàn)的壓縮編碼方法： 信息熵編碼方法（如哈夫曼編碼、 游程編碼和算術(shù)編碼）、 預(yù)測(cè)編碼和變換編碼， 并介紹新一代編碼方法（如知識(shí)基編碼和分形編碼）等以及相關(guān)知識(shí)。 由于矢量量化編碼和子帶編碼方法在上一章中結(jié)合音頻編碼已經(jīng)介紹， 它們?cè)趹?yīng)用于圖像時(shí)原理基本相同， 這里不再贅述。 第52頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四4.4 典型的熵編碼方法 4.4.1 基本概念 1 圖像熵和平均碼字長(zhǎng)度 1） 圖像熵（Entropy） 設(shè)

33、數(shù)字圖像像素灰度級(jí)集合為 （W1, W2,Wk，,WM）， 其對(duì)應(yīng)的概率分別為P1， P2， ， Pk， ， PM。 按信息論中信源信息熵定義， 數(shù)字圖像的熵H為第53頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 由此可見(jiàn)， 一幅圖像的熵就是這幅圖像的平均信息量度， 也是表示圖像中各個(gè)灰度級(jí)比特?cái)?shù)的統(tǒng)計(jì)平均值。 式(4.4-1)所表示的熵值是在假定圖像信源無(wú)記憶（即圖像的各個(gè)灰度級(jí)不相關(guān)）的前提下獲得的， 這樣的熵值常稱(chēng)為無(wú)記憶信源熵值， 記為H0()。 對(duì)于有記憶信源， 假如某一像素灰度級(jí)與前一像素灰度級(jí)相關(guān)， 那么公式(4.4-1)中的概率要換成條件概率P(Wi/Wi-1)和

34、聯(lián)合概率P(Wi, Wi-1)， 則圖像信息熵公式變?yōu)椋?.4-1） 第54頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 式中， P(Wi, Wi-1)=P(Wi)P(Wi/Wi-1), 則稱(chēng)H(Wi/Wi-1)為條件熵。 因?yàn)橹慌c前面一個(gè)符號(hào)相關(guān)， 故稱(chēng)為一階熵H1()。 如果與前面兩個(gè)符號(hào)相關(guān)， 求得的熵值就稱(chēng)為二階熵H2()。 依此類(lèi)推可以得到三階和四階等高階熵， 并且可以證明 H0（）H1（）H2（）H3（）(4.4-2) 第55頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 香農(nóng)信息論已證明： 信源熵是進(jìn)行無(wú)失真編碼的理論極限。 低于此極限的無(wú)失真編碼方法是

35、不存在的， 這是熵編碼的理論基礎(chǔ)。 而且可以證明， 如果考慮像素間的相關(guān)性， 使用高階熵一定可以獲得更高的壓縮比。 第56頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 2） 平均碼字長(zhǎng)度 設(shè)k為數(shù)字圖像第k個(gè)碼字Ck的長(zhǎng)度(二進(jìn)制代數(shù)的位數(shù))， 其相應(yīng)出現(xiàn)的概率為Pk， 則該數(shù)字圖像所賦予的碼字平均長(zhǎng)度R為（4.4-3） 第57頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四3） 編碼效率在一般情況下， 編碼效率往往用下列簡(jiǎn)單公式表示（4.4-4） 式中， H為信源熵， R為平均碼字長(zhǎng)度。 第58頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 根據(jù)信息論中信

36、源編碼理論， 可以證明在RH條件下總可以設(shè)計(jì)出某種無(wú)失真編碼方法。 若編碼結(jié)果使R遠(yuǎn)大于H， 表明這種編碼方法效率很低， 占用比特?cái)?shù)太多。 例如對(duì)圖像樣本量化值直接采用PCM編碼， 其結(jié)果平均碼字長(zhǎng)度R就遠(yuǎn)比圖像熵H大。 若編碼結(jié)果使R等于或很接近于H， 這種狀態(tài)的編碼方法稱(chēng)為最佳編碼。 它既不丟失信息而引起圖像失真， 又占用最少的比特?cái)?shù)， 例如下面要介紹的哈夫曼編碼即屬于最佳編碼方法。 第59頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 若要求編碼結(jié)果RH， 則必然丟失信息而引起圖像失真。 這就是在允許失真條件下的一些失真編碼方法。 熵編碼的目的就是要使編碼后的圖像平均比特?cái)?shù)R

37、盡可能接近圖像熵H。 一般是根據(jù)圖像灰度級(jí)數(shù)出現(xiàn)的概率大小賦予不同長(zhǎng)度的碼字， 概率大的灰度級(jí)用短碼字， 反之， 用長(zhǎng)碼字。 可以證明， 這樣的編碼結(jié)果所獲得的平均碼字長(zhǎng)度最短。 這就是下面要介紹的變長(zhǎng)最佳編碼定理。 第60頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 2. 變長(zhǎng)最佳編碼定理 【定理】 在變長(zhǎng)編碼中， 對(duì)出現(xiàn)概率大的信息符號(hào)賦予短碼字， 而對(duì)于出現(xiàn)概率小的信息符號(hào)賦予長(zhǎng)碼字。 如果碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)出現(xiàn)概率大小逆序排列， 則編碼結(jié)果平均碼字長(zhǎng)度一定小于任何其他排列方式。 這個(gè)定理就是下面要介紹的哈夫曼編碼方法的理論基礎(chǔ)。 設(shè)圖像灰度級(jí)為W1, W2, ,

38、Wi, WN； 各灰度級(jí)出現(xiàn)的概率分別為P1， P2， ， Pi， ， PN； 第61頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 編碼所賦予的碼字長(zhǎng)度分別為t1， t2， ， ti， ， tN； 則編碼后圖像平均碼字長(zhǎng)度R應(yīng)為第62頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 再令嚴(yán)格按照定理規(guī)則進(jìn)行編碼， 其結(jié)果平均碼字長(zhǎng)度為R1； R2為將其中任兩個(gè)灰度級(jí)不按定理規(guī)則編碼（即概率大的灰度級(jí)賦予長(zhǎng)碼字。 反之， 用短碼字）， 而其他所有灰度級(jí)仍按定理規(guī)則編碼所得的圖像平均碼字長(zhǎng)度， 那么R2應(yīng)等于R1加上“不按定理規(guī)則編碼所增加的平均碼字長(zhǎng)度”R。 只要證明R大

39、于0， 即可以證明上述定理。 第63頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 3. 可變長(zhǎng)最佳編碼的平均碼字長(zhǎng)度 設(shè)可變長(zhǎng)編碼所用碼元進(jìn)制為D， 被編碼的信息符號(hào)總數(shù)為N， 第i個(gè)符號(hào)出現(xiàn)的概率為Pi， 與其對(duì)應(yīng)的碼字長(zhǎng)度為ti， 則可以證明這種編碼結(jié)果平均碼字長(zhǎng)度R落在下列區(qū)間內(nèi)第64頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 式中, , 由此可以引導(dǎo)出對(duì)某一信息符號(hào)存在下式（4.4-5） 對(duì)二進(jìn)制碼進(jìn)一步簡(jiǎn)化為 -lbPiti-lbPi+1 （4.4-6） 第65頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 4. 惟一可譯編碼 有些情況下，

40、為了減少表示圖像的平均碼字長(zhǎng)度， 往往對(duì)碼字之間不加同步碼。 但是， 這樣就要求所編碼字序列能被惟一地譯出來(lái)。 滿(mǎn)足這個(gè)條件的編碼稱(chēng)為惟一可譯編碼， 也常稱(chēng)為單義可譯碼。 單義可譯碼往往是采用非續(xù)長(zhǎng)代碼。 第66頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 1） 續(xù)長(zhǎng)代碼和非續(xù)長(zhǎng)代碼 若代碼中任何一個(gè)碼字都不是另一個(gè)碼字的續(xù)長(zhǎng)， 也就是不能在某一碼字后面添加一些碼元而構(gòu)成另一個(gè)碼字， 稱(chēng)其為非續(xù)長(zhǎng)代碼。 反之， 稱(chēng)其為續(xù)長(zhǎng)代碼。 如二進(jìn)制代碼0， 10， 11即為非續(xù)長(zhǎng)代碼， 而0， 01， 11則為續(xù)長(zhǎng)代碼。 因?yàn)榇a字01可由碼字“0”后加上一個(gè)碼元“1”構(gòu)成。 第67頁(yè)，共4

41、38頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 2） 單義代碼 在介紹單義代碼前， 先簡(jiǎn)單介紹一下克勞夫特(Kraft)不等式： 若信源符號(hào)有m種取值， 其碼字長(zhǎng)度分別為li(i=1， 2， , m)； 又設(shè)最長(zhǎng)的碼字長(zhǎng)度為L(zhǎng)， 碼元種類(lèi)（即多少進(jìn)制碼）為D， 長(zhǎng)度為li的碼字占用了 個(gè)長(zhǎng)度為L(zhǎng)的碼字， 也就是必須有 對(duì)于二進(jìn)制, 則有 。 第68頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 任意有限長(zhǎng)的碼字序列， 只能被惟一地分割成一個(gè)個(gè)碼字， 則這樣的碼字序列稱(chēng)為單義代碼。 單義代碼的充要條件是滿(mǎn)足克勞夫特(Kraft)不等式（4.4-7） 式中, D為代碼中碼元種類(lèi)，

42、對(duì)于二進(jìn)制D2； n為代碼中碼字個(gè)數(shù)； ti為代碼中第i個(gè)碼字的長(zhǎng)度（即碼元個(gè)數(shù)）。 第69頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 如代碼C00， 10， 001， 101， 因?yàn)槭嵌M(jìn)制碼， 則D2， 共有4個(gè)碼字C100、 C210、 C3001、 C4101， 其相應(yīng)的長(zhǎng)度為t1=2、 t2=2、 t3=3、 t4=3， 代入式（4.4-7）可得第70頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 4.4.2 哈夫曼（Huffman）編碼方法 哈夫曼編碼是根據(jù)可變長(zhǎng)度最佳編碼定理， 應(yīng)用哈夫曼算法而產(chǎn)生的一種編碼方法。 在具有相同輸入概率集合的前提下， 它

43、的平均碼字長(zhǎng)度比其他任何一種惟一可譯碼都小， 因此， 也常稱(chēng)其為緊湊碼。 下面以一個(gè)具體的例子來(lái)說(shuō)明其編碼方法， 如圖4.4-1所示。第71頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四圖4.4-1 哈夫曼（Huffman）編碼的示例 第72頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 1. 編碼步驟 (1) 先將輸入灰度級(jí)按出現(xiàn)的概率由大到小順序排列（對(duì)概率相同的灰度級(jí)可以任意顛倒排列位置）。 （2） 將最小兩個(gè)概率相加， 形成一個(gè)新的概率集合。 再按第(1)步方法重排（此時(shí)概率集合中概率個(gè)數(shù)已減少一個(gè)）。 如此重復(fù)進(jìn)行， 直到只有兩個(gè)概率為止。第73頁(yè)，共438頁(yè)

44、，2022年，5月20日，5點(diǎn)12分，星期四 （3） 分配碼字。 碼字分配從最后一步開(kāi)始反向進(jìn)行， 對(duì)最后兩個(gè)概率一個(gè)賦予“1”碼， 一個(gè)賦予“0”碼。 如概率0.60賦予“0”碼， 0.40賦予“1”碼（也可以將0.60賦予“1”碼， 0.40賦予“0”碼）。 如此反向進(jìn)行到開(kāi)始的概率排列。 在此過(guò)程中， 若概率不變， 則仍用原碼字。 如圖4.4-1中第六步中概率0.40到第五步中仍用“1”碼。 若概率分裂為兩個(gè)， 其碼字前幾位碼元仍用原來(lái)的。 碼字的最后一位碼元一個(gè)賦予“0”碼元， 另一個(gè)賦予“1”碼元。 如圖中第六步中概率0.60到第五步中分裂為0.37和0.23， 則所得碼字分別為“0

45、0”和“01”。 第74頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 2. 前例哈夫曼編碼的編碼效率計(jì)算 根據(jù)式(4.4-1)求出前例信源熵為根據(jù)式(4.4-3)求出平均碼字長(zhǎng)度為第75頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四根據(jù)式（4.4-4）求出編碼效率為 可見(jiàn)哈夫曼編碼效率很高。 第76頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 *4.4.3 游程編碼 在圖像中， 尤其是一些不太復(fù)雜的圖像和計(jì)算機(jī)生成的圖像中， 往往存在著灰度或顏色相同的圖像塊， 對(duì)這樣的圖像進(jìn)行掃描時(shí)， 對(duì)應(yīng)這些相同灰度和顏色的圖像塊就會(huì)有連續(xù)多行掃描行數(shù)據(jù)具有相同的數(shù)值

46、， 而且在同一行上會(huì)有許多連續(xù)的像素點(diǎn)具有同樣的數(shù)值。 只保留連續(xù)相同像素值中的一個(gè)值及具有相同數(shù)值的像素點(diǎn)數(shù)目， 這種方法就是人們常說(shuō)的行程編碼或游程編碼（RLC， Run Length Coding）， 而且這種方法可以用少的數(shù)據(jù)量來(lái)表示圖像信息。 第77頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 在二元序列中， 只有兩種符號(hào)， 即“0”和“1”； 這些符號(hào)可連續(xù)出現(xiàn)， 連“0”這一段稱(chēng)為“0”游程， 連“1”這一段稱(chēng)為“1”游程。 它們的長(zhǎng)度分別為L(zhǎng)(0)和L(1)。 “0”游程和“1”游程總是交替出現(xiàn)的。 倘若規(guī)定二元序列是以“0”開(kāi)始， 第一個(gè)游程是“0”游程， 第二

47、個(gè)必為“1”游程， 第三個(gè)又是“0”游程等等。 對(duì)于隨機(jī)的二元序列， 各游程長(zhǎng)度將是隨機(jī)變量； 其取值可為1， 2， 3， ， 直到無(wú)限。 第78頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 定義了游程和游程長(zhǎng)度， 就可把任何二元序列變換成游程長(zhǎng)度的序列， 或簡(jiǎn)稱(chēng)游程序列。 這種變換是一一對(duì)應(yīng)的， 也就是可逆的。 例如有一二元序列 000101110010001 可變換成下列游程序列 3113213第79頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 *4.4.4 算術(shù)編碼 哈夫曼編碼、 游程編碼等無(wú)損編碼都是建立在符號(hào)和碼字相對(duì)應(yīng)的基礎(chǔ)上的， 這種編碼通常叫做塊碼或

48、分組碼。 此時(shí)， 信源符號(hào)應(yīng)是多元的， 而且不考慮符號(hào)相關(guān)性。 要用于最常見(jiàn)的二元序列， 須采用游程編碼、 分幀編碼或合并符號(hào)等方法， 轉(zhuǎn)換成多值符號(hào)， 而這些符號(hào)間的相關(guān)性也不予考慮。 這就使信源編碼的匹配原則不能充分滿(mǎn)足， 編碼效率就有所損失。 倘若要較好的解除相關(guān)性， 常需在序列中取很長(zhǎng)一段， 而這將遇到采用等長(zhǎng)碼時(shí)的那種困難。 第80頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 為了克服這種局限性， 就需跳出塊碼的范疇， 研究非塊碼的編碼方法。 這就是從全序列出發(fā)， 采用遞推形式的連續(xù)編碼。 其實(shí)香農(nóng)早就提出信源序列的積累概率的概念， 把這個(gè)概率映射到0，1）區(qū)間上， 使

49、每個(gè)序列對(duì)應(yīng)區(qū)間內(nèi)的一點(diǎn)， 這就是一個(gè)二進(jìn)位的小數(shù)。 這些點(diǎn)把0，1）區(qū)間分成許多小段， 每段的長(zhǎng)度等于某一序列的概率。 再在段內(nèi)取一個(gè)二進(jìn)位小數(shù)， 其長(zhǎng)度可與該序列的概率匹配， 達(dá)到高效編碼的目的。 這也就是算術(shù)編碼的基本概念。 在這里將著重討論積累概率的意義以及遞推計(jì)算等， 以說(shuō)明算術(shù)編碼的基本原理。 再通過(guò)實(shí)例介紹獨(dú)立二元序列的編碼過(guò)程。 第81頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 1. 積累概率的遞推計(jì)算 我們先從信源符號(hào)的積累概率開(kāi)始， 再討論序列的積累概率。 設(shè)信源符號(hào)集為 A=a0, a1, a2, , am-1 相應(yīng)的概率為Pr， r=0， 1， 2， ，

50、 m-1。 定義各符號(hào)的積累概率為（4.4-8） 第82頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 顯然， 由上式可得 P0=0, P1=p0, P2=p0+p1， 而且 pr=Pr+1-Pr 由于Pr和Pr+1都是小于1的正數(shù)， 可用0,1)區(qū)間內(nèi)的兩個(gè)點(diǎn)來(lái)表示， 則pr就是這兩點(diǎn)間的小區(qū)間的長(zhǎng)度。 不同的符號(hào)有不同的小區(qū)間， 它們互不重疊， 這種小區(qū)間內(nèi)任一個(gè)點(diǎn)可作為該符號(hào)的代碼。 第83頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 現(xiàn)在來(lái)計(jì)算序列的積累概率。 為了簡(jiǎn)單起見(jiàn)， 先以獨(dú)立二元序列為例來(lái)計(jì)算， 所得的結(jié)果很容易推廣到一般情況。 設(shè)有一序列S=011

51、， 這種三個(gè)二元符號(hào)的序列可按自然二進(jìn)數(shù)排列， 000， 001， 010， ， 則S的積累概率為 P(S)=p(000)+p(001)+p(010) （4.4-9） 倘若S后面接一個(gè)“0”， 積累概率就成為P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S) 第84頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 因?yàn)閮蓚€(gè)四元符號(hào)的最后一位是“0”和“1”時(shí)， 根據(jù)歸一律， 它們的概率和應(yīng)等于前三位的概率， 即p(0000)+p(0001)=p(000)等。 第85頁(yè)，共438

52、頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 倘若S后面接一個(gè)“1”， 則其積累概率是 P(S1)=p(0000)+p(0001)+p(0010)+p(0011) +p(0100)+p(0101)+p(0110) =P(S)+p(0110)=P(S)+p(S)p0 由于二元集的積累概率為P0=0， P1=p0， 所以上面兩式可統(tǒng)一寫(xiě)成 P(Sr)=P(S)+p(S)Pr r=0， 1 (4.4-10) 第86頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 這樣寫(xiě)的式子很容易推廣到多元序列， 即可得到一般的積累概率遞推公式 P(Sar)=P(S)+p(S)Pr (4.4-11) 以

53、及序列的概率公式 p(Sar)=p(S)pr (4.4-12) 對(duì)于有相關(guān)性的序列， 上面的兩個(gè)遞推公式也是適用的， 只是上式中的單符號(hào)概率應(yīng)換成條件概率。 第87頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 用遞推公式可逐位計(jì)算序列的積累概率， 而不用像式（4.4-9）那樣列舉所有排在前面的那些序列概率。 實(shí)際上， 可用兩個(gè)存儲(chǔ)器把p(S)和P(S)存下來(lái)， 然后根據(jù)輸入符號(hào)和式(4.4-11)、 式(4.4-12)， 更新兩個(gè)存儲(chǔ)器中的值。 在起始時(shí)可令 P（）=0, p()=1其中代表空集， 只有一個(gè)符號(hào)ar的序列就是ar。 第88頁(yè)，共438頁(yè)，2022年，5月20日，5

54、點(diǎn)12分，星期四 2. 代碼長(zhǎng)度 從以上關(guān)于積累概率P(S)的計(jì)算中可看出， P(S)把區(qū)間0,1）分割成許多小區(qū)間， 每個(gè)小區(qū)間的長(zhǎng)度等于各序列的概率p(S)， 而這些小區(qū)間內(nèi)的任一點(diǎn)可用來(lái)代表這些序列， 現(xiàn)在來(lái)討論如何選擇這個(gè)點(diǎn)。 令 （4.4-13）第89頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 其中X代表大于或等于X的最小整數(shù)， 把積累概率P(S)寫(xiě)成二進(jìn)位的小數(shù)， 取其前L位， 若有尾數(shù)， 就進(jìn)位到第L位， 這樣得到一個(gè)數(shù)C。 例如, P(S)=0.10110001， p(S)=1/7, 則L=3, 得C0.110。 這個(gè)C就可以作為S的碼字。 可以證明這C點(diǎn)必然在

55、長(zhǎng)度為p(S)的小區(qū)間內(nèi)， 因而是可以惟一解碼的。 第90頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 這樣構(gòu)成的碼字， 編碼效率是很高的， 因?yàn)橐呀?jīng)達(dá)到概率匹配， 尤其是當(dāng)序列很長(zhǎng)時(shí)。 由式（4.4-13）可見(jiàn)， 對(duì)于長(zhǎng)序列， p(S)必然很小， L與概率倒數(shù)的對(duì)數(shù)已幾乎相等。 也就是取整數(shù)所造成的差別很小， 平均代碼長(zhǎng)度將接近S的熵值。 第91頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 實(shí)際編碼過(guò)程是這樣的。 可先設(shè)定兩個(gè)存儲(chǔ)器， 起始時(shí)一個(gè)為“0”， 另一個(gè)為“1”， 分別代表空集的積累概率和概率。 每輸入一個(gè)信源符號(hào), 更新一次， 得到P(S)值后， 按前

56、述方法得到碼字C， 暫存起來(lái), C值也隨輸入符號(hào)而更新。 直至序列結(jié)束， 就可作為該序列的碼字輸出。 由于P(S)是遞增的， 而增量隨著序列的增長(zhǎng)而減小。 因?yàn)樵隽渴切蛄械母怕逝c信源符號(hào)的積累概率的乘積， 所以C的前幾位一般已固定， 在以后的計(jì)算中不會(huì)被更新， 因而可以輸出。第92頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 解碼也逐位進(jìn)行。 由于P（S）的遞增性， 第一個(gè)符號(hào)的積累概率不會(huì)小于以后的C值， 所以從C值就可譯出第一個(gè)信源符號(hào)。 由該符號(hào)按編碼方法算得的P（S）與C比較就可判斷下一個(gè)信源符號(hào)， 依次下去就可譯出全序列。 其實(shí)， 在算術(shù)編碼中， 解碼過(guò)程與編碼過(guò)程是相

57、似的。 第93頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 3. 實(shí)現(xiàn)算術(shù)編碼的一些問(wèn)題 以上從理論上簡(jiǎn)單討論了算術(shù)編碼的編譯方法以及它的編碼效率， 可以看出它有許多優(yōu)點(diǎn)， 尤其它的漸近最佳性， 亦即當(dāng)序列無(wú)限增長(zhǎng)時(shí)， 平均碼長(zhǎng)將漸近地等于序列的熵值。 但在實(shí)際實(shí)現(xiàn)時(shí)， 尚有一些必須解決的問(wèn)題。第94頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 （1） 復(fù)雜性問(wèn)題。 每次遞推運(yùn)算中都有乘法， 當(dāng)序列概率和符號(hào)的積累概率展開(kāi)成二進(jìn)位小數(shù)后的位數(shù)較多且要求精度較高時(shí)， 就有一定的運(yùn)算量。 這種運(yùn)算必須在輸入一個(gè)信源符號(hào)的時(shí)間內(nèi)完成， 以保證實(shí)時(shí)編解碼， 有時(shí)會(huì)造成困難。

58、 要消除乘法， 只有一種情況， 這就是編碼序列是二元序列， 而且其符號(hào)概率較小的一個(gè)是2-k的形式， 其中k是正整數(shù)。 此時(shí)乘以2-k等于移位， 乘以1-2-k等于移位和相減。 這樣就完全沒(méi)有乘法運(yùn)算， 可加快運(yùn)算速度。 這就是為什么算術(shù)編碼一般只用于二元序列的編碼， 而且符號(hào)概率常用2-k去近似。 第95頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 (2) 計(jì)算精度問(wèn)題。 即使在二元序列的情況下， 精度問(wèn)題仍存在。 隨著遞推運(yùn)算的延續(xù)， P(S)和p(S)（即積累概率和序列的概率）的小數(shù)位數(shù)也將逐步增加， 若不能隨時(shí)輸出和加以截?cái)啵?運(yùn)算器將難于容納， 但有所截?cái)啾厝唤档途取?/p>

59、 而精度不夠會(huì)影響編解碼的正確性。 這是因?yàn)殡S著序列長(zhǎng)度增大， 小區(qū)間數(shù)目越來(lái)越多， 長(zhǎng)度越來(lái)越短。 計(jì)算精度不夠會(huì)使有些小區(qū)間互相重疊或消失（即長(zhǎng)度為零）， 前者使惟一性喪失， 后者使無(wú)碼字可編。 這些會(huì)造成差錯(cuò)， 就不是無(wú)損編碼， 而且這些差錯(cuò)還會(huì)擴(kuò)散。 所以最初提出的算術(shù)編碼要求無(wú)限精度， 這是不現(xiàn)實(shí)的。 有限精度是可能的， 只是編碼效率會(huì)有所下降。 第96頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四 （3） 存儲(chǔ)量問(wèn)題。 碼字C的長(zhǎng)度也隨序列S長(zhǎng)度的增加而不斷增長(zhǎng)。 若不及時(shí)輸出， 存儲(chǔ)量將非常大。 但若輸出過(guò)早， 運(yùn)算過(guò)程中可能還需調(diào)整已輸出的部分， 就會(huì)影響結(jié)果。 當(dāng)

60、未輸出部分的前面各位都是“1”時(shí)， 后面在計(jì)算時(shí)略有增加， 就可能進(jìn)位到已輸出部分， 尤其是連“1”很長(zhǎng)時(shí)， 原以為保留許多位已經(jīng)夠了， 但仍會(huì)影響已輸出部分。 從理論上說(shuō)， 這種連“1”的長(zhǎng)度可以達(dá)到無(wú)限， 當(dāng)然出現(xiàn)這種情況的概率也將接近于零。 這類(lèi)問(wèn)題常稱(chēng)為進(jìn)位問(wèn)題， 在實(shí)際應(yīng)用時(shí)也必須設(shè)法解決。 第97頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四4. 二元獨(dú)立序列的算術(shù)編碼示例設(shè)有二元獨(dú)立序列： S=11111100已知其符號(hào)概率 p0=1/4， p1=3/4, 則第98頁(yè)，共438頁(yè)，2022年，5月20日，5點(diǎn)12分，星期四用前面的公式和編碼規(guī)則， 可得P(S) =p(