【正文】 會(huì)得到不同的樣本序列 。 采樣分析 采樣樣本： 采樣函數(shù)： ????????nnTttp )()( ?????????nnTttx )()( ? )()(????????nnTtnTx ? )()()( tptxtx p ?采樣分析 已采樣信號(hào)的頻譜： 采樣函數(shù)頻譜： )2(2)( ????????k TkTjP ????? ? ?)()(21)( ???? jPjXjX P ??????????kskjXT )(( ??1原連續(xù)時(shí)間信號(hào)： )()( ?jXtx ?MMs ??? ??MMs ??? ??采樣分析 對(duì)連續(xù)時(shí)間信號(hào)在時(shí)域理想采樣，就相當(dāng)于在頻域以采樣頻率 ?s為周期延拓，幅值減小1/T。 采樣定理 設(shè) 是某一個(gè)帶限信號(hào)，在 |?| ?M時(shí)，X（ j?） =0。 已知這些樣本值，我們能用如下辦法重建：讓采樣后的信號(hào)通過一個(gè)增益為 T, 截止頻率大于 ?M，而小于（ ?s? ? M）的理想濾波器，該濾波器的輸出就是 。 )(tx )(nTx)(tx )(tx數(shù)據(jù)壓縮 2 壓縮的必要性 ?音頻、視頻的數(shù)據(jù)量很大，如果不進(jìn)行處理，計(jì)算機(jī)系統(tǒng)幾乎無法對(duì)它進(jìn)行存取和交換。對(duì)于聲音也是如此， CD音質(zhì)的聲音每秒將有約為 172KB的數(shù)據(jù)量。 ?運(yùn)用通信技術(shù)與概率論、隨機(jī)過程、數(shù)理統(tǒng)計(jì)的方法系統(tǒng)討論了通信的基本問題，得出了幾個(gè)重要而帶有普遍意義的結(jié)論： 信息論科學(xué)體系 香農(nóng)信息論 壓縮理論 有失真信源編碼 無失真信源編碼 率失真理論 壓縮編碼 等長(zhǎng)編碼 定理 變長(zhǎng)編碼 定理 最優(yōu)碼構(gòu)成 Huffman碼 Fano碼 傳輸理論 有噪聲 信道編碼理論 碼構(gòu)成 糾錯(cuò)碼 代數(shù)編碼 卷積碼 網(wǎng)絡(luò)信道 網(wǎng)絡(luò)信息理論 網(wǎng)絡(luò)最佳碼 保密理論 保密系統(tǒng)的 信息理論 保密碼 信息論之父 ? The Father of Information Theory—— Claude Elwood Shannon ? Born: 30 April 1916 in Gaylord, Michigan, USA ? Died: 24 Feb 2023 in Medford, Massachusetts, USA 熵 ?定義： ? 設(shè)隨機(jī)變量 X，取值空間 Ω ， Ω 為有限集合。 熵 為什么能夠進(jìn)行壓縮 信息論認(rèn)為：若信源編碼的熵大于信源的實(shí)際熵，該信源中一定存在冗余度（信息熵冗余）。 360B 480KB 數(shù)據(jù)冗余的類別 ?空間冗余 ?時(shí)間冗余 ?統(tǒng)計(jì)冗余 ?信息熵冗余 ?結(jié)構(gòu)冗余 ?知識(shí)冗余 ?視覺冗余 ?聽覺冗余 數(shù)據(jù)冗余的類別 ● 空間冗余 規(guī)則物體和規(guī)則背景的表面物理特性都具有相關(guān)性，數(shù)字化后表現(xiàn)為數(shù)據(jù)冗余。在播出該序列圖像時(shí)，時(shí)間發(fā)生了推移，但若干幅畫面的同一部位沒有變化，變化的只是其中某些地方，這就形成了時(shí)間冗余。 ● 統(tǒng)計(jì)冗余 ● 信息熵冗余 信息熵實(shí)際情況又稱編碼冗余。 ● 結(jié)構(gòu)冗余 數(shù)字化圖像中的物體表面紋理等結(jié)構(gòu)往往存在著冗余 數(shù)據(jù)冗余的類別 由圖像的記錄方式與人對(duì)圖像的知識(shí)差異所產(chǎn)生的冗余稱為知識(shí)冗余。 ● 視覺冗余 ● 聽覺冗余 人耳對(duì)不同頻率的聲音的敏感性是不同的，并不能察覺所有頻率的變化，對(duì)某些頻率不必特別關(guān)注，因此存在聽覺冗余。 統(tǒng)計(jì)冗余 ?從統(tǒng)計(jì)的觀點(diǎn)，某點(diǎn)像素的灰度與其鄰域灰度有密切關(guān)系。對(duì)于一個(gè)圖像，很多單個(gè)像素對(duì)視覺的貢獻(xiàn)是冗余的。 圖像相鄰像素之間色彩、 明度相同或相似，產(chǎn)生信息 （ 有意義的內(nèi)容 ）冗余 時(shí)間冗余 ?時(shí)間發(fā)生了推移，若干幅畫面的同一部位沒有變化，于是產(chǎn)生了冗余 t結(jié)構(gòu)冗余 數(shù)字化圖像中具有 規(guī)則紋理的表面產(chǎn)生的 冗余。 33K 15K 數(shù)據(jù)壓縮的評(píng)價(jià) 壓縮比 ? 設(shè)： n1和 n2是輸入數(shù)據(jù)和輸出數(shù)據(jù) 壓縮比為： CR = n1 / n2 例如：圖像 512 480， 24位 輸入＝ (512 480 24)/8=737280B 輸出 15000B 壓縮比＝ 737280/15000＝ 49 ? 相對(duì)數(shù)據(jù)冗余： ? RD = 1 – 1/CR=(n1n2)/n2 數(shù)據(jù)壓縮的評(píng)價(jià) 壓縮質(zhì)量 ?客觀質(zhì)量評(píng)價(jià)：壓縮過程對(duì)信息的損失能夠表示為原始信息與壓縮并解壓縮后信息的函數(shù)。 例如：通過視覺比較兩個(gè)圖像，給出一個(gè)定性的評(píng)價(jià)，如很粗、粗、稍粗、相同、稍好、較好、很好等，可以對(duì)所有人的感覺評(píng)分計(jì)算平均感覺分來衡量。所以，壓縮、解壓速度分別估計(jì)。 壓縮編碼的分類 ?數(shù)據(jù)壓縮 (data pression) 與信號(hào)編碼(signal coding)往往含義相同 ?壓縮 (press) ?解壓縮 /還原 /重構(gòu) (depress) ?編碼 (encode/coding) ?解碼 /譯碼 (decode) ?相關(guān)學(xué)科：信息論、數(shù)學(xué)、信號(hào)處理、數(shù)據(jù)壓縮、編碼理論和方法 壓縮編碼的分類 ?編碼壓縮的方法目前有很多，其分類方法根據(jù)出發(fā)點(diǎn)不同而有差異。 ?有損壓縮 是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。圖像、聲音 壓縮編碼的分類 壓縮 有損壓縮 無損壓縮 行程編碼 LZW編碼 哈夫曼編碼 算術(shù)編碼 無損預(yù)測(cè)編碼 位平面編碼 有損預(yù)測(cè)編碼 分形編碼 模型編碼 子帶編碼 神經(jīng)網(wǎng)絡(luò)編碼 變換編碼 KL變換 Haar變換 離散余弦變換 離散傅立葉變換 斜變換 小波變換 壓縮編碼的分類 ?從信息語義角度分為：熵編碼、源編碼和混合編碼 ?熵編碼 (entropy encoding)（也稱 平均信息量編碼 ） 熵編碼是一種泛指那些不考慮被壓縮信息的性質(zhì)的無損編碼。也就是說，平均信息量編碼 忽略被壓縮信息的語義內(nèi)容 。 壓縮編碼的分類 ?源編碼 (Source Coding) 源編碼的冗余壓縮取決于初始信號(hào)的類型、前后的相關(guān)性、信號(hào)的語義內(nèi)容等。當(dāng)然壓縮的程度主要取決于數(shù)據(jù)的語義內(nèi)容，比起平均信息量編碼，它的壓縮比更大。如： 預(yù)測(cè)編碼： DM、 ADPCM 變換編碼： DCT、 DWT 分層編碼：如子采樣、子帶編碼 其他編碼：如矢量量化、運(yùn)動(dòng)補(bǔ)償、音感編碼 壓縮編碼的分類 ?混合編碼 (hybrid coding) 混合編碼 = 熵編碼 + 源編碼 大多數(shù)壓縮標(biāo)準(zhǔn)都采用混合編碼的方法進(jìn)行數(shù)據(jù)壓縮，一般是先利用信源編碼進(jìn)行有損壓縮，再利用熵編碼做進(jìn)一步的無損壓縮。 壓縮編碼的分類 此外，也可根據(jù)不同的依據(jù)對(duì)數(shù)據(jù)的壓縮算法 進(jìn)行其它不同的分類，如： ?按作用域在空間域或頻率域：空間方法、變換方法、混合方法 ?按是否自適應(yīng)：自適應(yīng)性編碼和非適應(yīng)性（靜態(tài)）編碼 ?按碼長(zhǎng)：定長(zhǎng)碼和變長(zhǎng)碼 香農(nóng) 范諾 ?香農(nóng) 范諾編碼 (Shannon–Fano coding) ? 在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量 ? 在計(jì)算熵時(shí)，如果對(duì)數(shù)的底數(shù)用 2，熵的單位就用 “ 香農(nóng) (Sh)‖，也稱 “ 位 (bit)‖ 。 ? 最早闡述和實(shí)現(xiàn) “ 從上到下 ” 的熵編碼方法的人是 Shannon(1948年 )和 Fano(1949年 )，因此稱為香農(nóng) 范諾 (Shannon Fano)編碼法 香農(nóng) 范諾編碼舉例 ? 有一幅 40個(gè)像素組成的灰度圖像，灰度共有 5級(jí)，分別用符號(hào) A， B， C， D和 E表示。這就意味每個(gè)像素用 3位，編碼這幅圖像總共需要 120位。首先按照符號(hào)出現(xiàn)的頻度或概率排序，然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù) 香農(nóng) 范諾編碼舉例 （ 3）壓縮比的實(shí)際值 ? 按照這種方法進(jìn)行編碼需要的總位數(shù)為30+14+14+18+15＝ 91，實(shí)際的壓縮比為120:91≈ : 1 霍夫曼編碼 ?霍夫曼編碼 (Huffman coding) ? 霍夫曼 (. Huffman)在 1952年提出和描述的 “ 從下到上 ” 的熵編碼方法 ? 根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計(jì)壓縮編碼方法。 ? 統(tǒng)計(jì)符號(hào)的出現(xiàn)概率，建立一個(gè)概率統(tǒng)計(jì)表 ?將最常出現(xiàn) (概率大的 )的符號(hào)用最短的編碼， ?最少出現(xiàn)的符號(hào)用最長(zhǎng)的編碼。 ?輸入符號(hào)數(shù)受限于可實(shí)現(xiàn)的碼表尺寸 ?譯碼復(fù)雜 ?需要實(shí)現(xiàn)知道輸入符號(hào)集的概率分布 ?沒有錯(cuò)誤保護(hù)功能 應(yīng)用舉例 在圖像的編碼中 ?首先計(jì)算頻率并以二叉樹方式進(jìn)行排序來獲得編碼值，其次用編碼值取代圖像數(shù)據(jù)進(jìn)入圖像文件中。例如：分成 8 8 的子塊，就可以大大降低不同灰度值的個(gè)數(shù)（最多是 64而不是 256）。短的碼不會(huì)成為更長(zhǎng)碼的啟始部分； ? Huffman編碼的平均碼長(zhǎng)接近于熵 ? 缺點(diǎn)：需要多次排序，耗費(fèi)時(shí)間 算術(shù)編碼 ?Huffman 編碼的局限性： Huffman 編碼使用整數(shù)個(gè)二進(jìn)制位對(duì)符號(hào)進(jìn)行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。可以想象，整個(gè)信息的 80% 在壓縮后都幾乎相當(dāng)于理想長(zhǎng)度的 3倍左右。 消息序列中的每個(gè)元素都要用來縮短這個(gè)區(qū)間。 ?采用算術(shù)編碼每個(gè)符號(hào)的平均編碼長(zhǎng)度可以為小數(shù) 算術(shù)編碼 ? 符號(hào)串編碼：將串中使用的符號(hào)表按原編碼（如字符的ASCII編碼、數(shù)字的二進(jìn)制編碼）從小到大順序排列成表。 其中， dj = rj lj為區(qū)間 Ij的寬度，初值 l0 = 0， r0 = 1， d0 = 1。 ? 串的最后一個(gè)符號(hào)所對(duì)應(yīng)區(qū)間的下限 ln就是該符號(hào)串的算術(shù)編碼值 . 算術(shù)編碼 ? 通常，對(duì)任意序列 x = x1x2? xn 只需知道信源的 cdf，即信源的概率模型 算術(shù)編碼：編碼和解碼過程都只涉及算術(shù)運(yùn)算（加、減、乘、除） 舉例 2 字符 概率 a b aba 要編的字符串 算術(shù)編碼 0 1 a b a [0,) b [,1) “ aba‖ 0 a b 第一個(gè)為 a，編碼范圍限制在 0～ 1 算術(shù)編碼 0 a b 0 a b 1 對(duì)已知區(qū)間進(jìn)行再次分割 第二個(gè)為 b，編碼范圍限制在 ～ 0 a b 算術(shù)編碼 a b 0 a b 對(duì)已知區(qū)間進(jìn)行再次分割 第 3個(gè)為 a，編碼范圍限制在 [,)范圍內(nèi) 9 a b 算術(shù)編碼 ?在 [,) 中任選一個(gè)浮點(diǎn)數(shù)來標(biāo)識(shí)這個(gè)區(qū)間，如 ，即可表示我們要編的消息為“ aba‖ ?把該浮點(diǎn)數(shù)轉(zhuǎn)變?yōu)槎M(jìn)制編碼 : 0010 ?特性： 區(qū)間越窄，說明符號(hào)串越長(zhǎng)，二進(jìn)制碼長(zhǎng)越長(zhǎng) 舉例 2 ? 假設(shè)信源符號(hào)為 {00, 01, 10, 11}，它們的 概率分別為 { , , , } ? 對(duì)二進(jìn)制消息序列 10 00 11 00 10 11 01 … 進(jìn)行算術(shù)編碼 算術(shù)編碼 ?初始化： 根據(jù)信源符號(hào)的概率把間隔 [0, 1)分成如表 2 4所示的 4個(gè)子間隔： [0, ), [, ), [, ), [, 1)。 ?算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔 [0, 1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。 算術(shù)編碼 ? 算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在自適應(yīng)算術(shù)編碼中，信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。 E1(x) = 2x ? E2: [0. 5,1) = [0, 1)。 主要應(yīng)用于圖象表達(dá)、處理。在這些圖塊中，許多行上都具有相同的顏色，或者在一行