【正文】 每次選出最小的兩個值，作為二叉樹的兩個葉子的節(jié)點(diǎn)，將它們的和作為其根節(jié)點(diǎn)。之后，這兩個葉子節(jié)點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較； （ 4）重復(fù)步驟 3，直到最后得到和為 1的根節(jié)點(diǎn)； （ 5）將形成的二叉樹的左節(jié)點(diǎn)標(biāo) 0，右節(jié)點(diǎn)標(biāo) 1。把從最上面的根節(jié)點(diǎn)到最下面的葉子 ? 節(jié)點(diǎn)途中遇到的 0， 1序列串起來，就得到了的編碼 。 Huffman編碼 2022/2/14 Huffman編碼 ? 產(chǎn)生 Huffman編碼需要對原始數(shù)據(jù)掃描兩遍。第一遍掃描要精確地統(tǒng)計(jì)出原始數(shù)據(jù)中每個值出現(xiàn)的頻率，第二遍是建立 Huffman樹并進(jìn)行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼，因此 Huffman編碼數(shù)據(jù)壓縮和還原速度都較慢。但是哈夫曼編碼簡單有效，因而得到了廣泛的應(yīng)用。 2022/2/14 ? 2．香農(nóng)編碼（ shannon coding） ? 香農(nóng)編碼的過程與哈夫曼編碼有些相似。其編碼步驟簡述如下。 ? (1)圖像灰度級按概率遞減順序排序； ? (2)將分成兩組，每組的概率和相同或相似。對第一組分配代碼 “ 0”，第二組分配代碼 “ 1”； ? (3)執(zhí)行步驟（ 2）后，若每組還是由兩個或兩個以上的灰度級組成，就重復(fù)上述步驟，直到每組只有一個灰度級。 ? 至此，可獲得表 ，由表 農(nóng)編碼的平均碼字長度。 統(tǒng)計(jì)編碼技術(shù) 2022/2/14 統(tǒng)計(jì)編碼技術(shù) ? 表 2022/2/14 無損預(yù)測編碼 ? 預(yù)測編碼的基本思想是通過僅對每個像素中提取的新信息編碼，來消除像素之間的冗余。這里一個像素的新信息定義為該像素的當(dāng)前或現(xiàn)實(shí)值與它預(yù)測值的差值。 ? 一個無損預(yù)測編碼系統(tǒng)主要由一個編碼器和一個解碼器組成，它們各有一個相同的預(yù)測器，如圖 。 2022/2/14 無損預(yù)測編碼 符 號 編 碼 器預(yù) 測 器符 號 解 碼 器預(yù) 測 器整 數(shù) 舍 入—輸 入 圖 像壓 縮 圖 像解 壓 圖 像??kfke? kf?kf?kf?圖 無損預(yù)測編碼系統(tǒng) 2022/2/14 無損預(yù)測編碼 ? 當(dāng)輸入圖像的像素序列逐個進(jìn)入編碼器時，預(yù)測器根據(jù)若干個過去的輸入產(chǎn)生對當(dāng)前輸入像素的預(yù)測值，也稱為估計(jì)值。將這個預(yù)測值進(jìn)行整數(shù)舍入，得到預(yù)測器的輸出值，則由此產(chǎn)生的預(yù)測誤差表示為 kkk ffe???2022/2/14 無損預(yù)測編碼 ? 預(yù)測誤差可以用符號編碼器，借助變長碼進(jìn)行編碼用以產(chǎn)生壓縮圖像數(shù)據(jù)流的下一個元素。利用解碼器，根據(jù)接收的變長碼字重建預(yù)測誤差，則解壓縮圖像的像素序列表示為 kkk fef???2022/2/14 無損預(yù)測編碼 ? 利用預(yù)測器，可以將對原始圖像序列的編碼轉(zhuǎn)換成對預(yù)測誤差的編碼。由于在預(yù)測比較時，預(yù)測誤差的動態(tài)范圍會遠(yuǎn)小于原始圖像序列的動態(tài)范圍，所以對預(yù)測誤差的編碼所需的比特數(shù)會大大減少，這是預(yù)測編碼可以獲得數(shù)據(jù)壓縮結(jié)果的原因。 ? 在多數(shù)情況下，可以通過將個先前的像素進(jìn)行線性組合得到預(yù)測值。 2022/2/14 無損預(yù)測編碼 ? 將 m個先前的像素進(jìn)行線性組合得到預(yù)測值。 ? 式中， m稱為線性預(yù)測器的階， R是舍入函數(shù)， ai是預(yù)測系數(shù)。下標(biāo) n為圖像序列的空間坐標(biāo)，在一維線性預(yù)測編碼中，設(shè)掃描沿行進(jìn)行，式（ ）可以表示為 ????????? ??? inmiin faRf1?2022/2/14 無損預(yù)測編碼 ? 一維線性預(yù)測僅是當(dāng)前行掃描到的先前像素的函數(shù)。在二維線性預(yù)測編碼中，預(yù)測是對圖像從左向右，從上向下進(jìn)行掃描時所掃描到的先前像素的函數(shù)。在三維線性預(yù)測編碼中，預(yù)測基于上述像素和前一幀的像素。預(yù)測誤差的概率密度函數(shù)一般用零均值不相關(guān)拉普拉斯概率密度函數(shù)表示為 ?????????? ??),(),(1yixfaRyxfmiin?2022/2/14 無損預(yù)測編碼 ? 式中， 是 e的標(biāo)準(zhǔn)差。 ???????? ??eeeeep??2e x p21)(e?2022/2/14 有損預(yù)測編碼 ? 有損預(yù)測編碼系統(tǒng)與無損預(yù)測編碼系統(tǒng)相比，主要增加了量化器。量化器的作用是將預(yù)測誤差映射到有限個輸出 中， 決定了有損預(yù)測編碼中的壓縮量和失真量。有損預(yù)測編碼系統(tǒng)組成如圖 。 ke?ke?2022/2/14 有損預(yù)測編碼 ∑ 量 化 器 符 號 編 碼 器預(yù) 測 器∑輸 入 圖 像 壓 縮 圖 像ke ke?kf?kf?_符 號 解 碼 器預(yù) 測 器∑解 壓 縮 圖 像kf?kf?ke? 圖 有損預(yù)測編碼系統(tǒng) 2022/2/14 有損預(yù)測編碼 ? 解碼器的輸出表示為 ? 式中， 為過去預(yù)測值， 為量化誤差函數(shù)， 為解碼器的輸出。如圖 輸出端產(chǎn)生誤差。 kkk fef??? ??kf? ke? kf?2022/2/14 圖像變換編碼基本原理 ? 圖像的變換編碼是利用某種變換將空間域里描述的圖像 ，變換為變換域中描述的 。對變換域中 編碼壓縮，比對空間域壓縮更為有效。因?yàn)樵陬l域中相關(guān)性明顯下降，能量主要集中于少數(shù)低頻分量系數(shù)上。通常采用正交變換。例如傅里葉變換、沃爾什變換、離散余弦變換等。以傅里葉變換為例，變換具有能量集中于少數(shù)低頻系數(shù)、各系數(shù)不相關(guān)、高頻分量衰減很快且能量較小等性質(zhì)。這些性質(zhì)都可以用于圖像數(shù)據(jù)壓縮。 ),( yxf ),( vuF ),( vuF2022/2/14 圖像變換編碼基本原理 ? 變換編碼就是對數(shù)字圖像經(jīng)過正交變換的系數(shù)矩陣進(jìn)行量化編碼。圖 。系統(tǒng)由五部分組成， 圖像輸入與變換 、 系數(shù)量化編碼 、 信道傳輸 、 解碼和逆變換 。在變換階段，將原始圖像劃分成若干子塊，對每個子塊進(jìn)行某種正交變換。通過變換，降低或消除相鄰像素之間或相鄰掃描行之間的相關(guān)性，提供用于編碼壓縮的變換系數(shù)矩陣。編碼過程實(shí)現(xiàn)圖像信息的壓縮。在變換域中，圖像信號的絕大部分能量集中在低頻分量部分，編碼中如果略去那些能量很小的高頻分量，或者給這些高頻分量分配較小的合適的比特數(shù)，就可以明顯減少圖像傳輸或存儲的數(shù)據(jù)量。 2022/2/14 圖像變換編碼基本原理 正交變換及編解碼框圖 二 維 正 交 變 換 系 數(shù) 量 化 編 碼 解 碼 逆 變 換信 道 傳 輸輸 入 圖 像輸 出 圖 像2022/2/14 視頻圖像編碼簡介 ? 隨著計(jì)算機(jī)網(wǎng)絡(luò)及通信技術(shù)的迅速發(fā)展，圖像通信受到該領(lǐng)域科技工作者的廣泛關(guān)注。國際標(biāo)準(zhǔn)化組織 (ISO)、國際電工委員會 (IEC)和國際電信聯(lián)盟 (ITU)下屬的國際電報電話咨詢委員會 (CCITT)等國際組織積極致力于圖像處理的標(biāo)準(zhǔn)化工作。特別是圖像編碼，涉及到多媒體、數(shù)字電視、可視電話、會議電視等圖像傳輸方面的廣泛應(yīng)用，為此制定的國際標(biāo)準(zhǔn)極大地推動了圖像編碼技術(shù)的發(fā)展與應(yīng)用。這些圖像編碼的國際標(biāo)準(zhǔn)有： JPEG、 MPEG、。 2022/2/14 JPEG標(biāo)準(zhǔn) ? 1986年， ISO和 CCITT成立了 “ 聯(lián)合圖片專家組 ”（ Joint Photographic Expert Group），主要任務(wù)是研究靜止圖像壓縮算法的國際標(biāo)準(zhǔn)。 1987年用 Y： U： V=4：2： 2，每像素 16比特，寬度為 4： 3的電視圖像進(jìn)行了測試，選擇出三個方案進(jìn)行評選，其中的 DCT方案得分最高，它制定的以自適應(yīng)離散余弦變換編碼（ ADCT）為基礎(chǔ)的 “ 連續(xù)色調(diào)靜止圖像壓縮編碼 ” JPEG標(biāo)準(zhǔn)于 1991年3月正式提出。 2022/2/14 JPEG標(biāo)準(zhǔn) ? JPEG標(biāo)準(zhǔn)根據(jù)不同的應(yīng)用場合對圖像的壓縮要求提出了幾種不同的編、解碼方法，主要分為基本系統(tǒng)、擴(kuò)展系統(tǒng)和信息保持型系統(tǒng)。所有符合 JPEG標(biāo)準(zhǔn)的編碼器都必須支持基本系統(tǒng)，而其他系統(tǒng)則作為不同應(yīng)用目的的選擇項(xiàng)。 ? 基本系統(tǒng)提供順序建立方式的高效有失真編碼，輸入圖像的精度為 8比特 /像素。圖 JPEG標(biāo)準(zhǔn)基本系統(tǒng)的編碼器結(jié)構(gòu)圖，圖中，量化用 Q表示， IQ表示反量化。編碼器對彩色圖像采用分量編碼。 2022/2/14 JPEG標(biāo)準(zhǔn) ? 圖 JPEG基本系統(tǒng)編碼器結(jié)構(gòu)圖 D C T Q熵 編 碼R G B Y U V熵 解 碼I QI D C TR G B Y U V2022/2/14 JPEG基本系統(tǒng)組成模塊 2022/2/14 JPEG標(biāo)準(zhǔn) ? （ 1）將整個圖像分為不重疊的 像素子塊，共有 Y、U、 V三幅數(shù)字圖像， Y表示圖像的亮度，即明暗程度， UV代表圖像色彩度。 ? （ 2）對各個子塊進(jìn)行 DCT變換， ? （ 3）對所有的系數(shù)進(jìn)行線性量化。量化的過程是對系數(shù)值的量化間距劃分后的簡單的取整運(yùn)算，量化步長取決于一個視覺閾值矩陣，它隨系數(shù)的位置而改變，并且對 Y和UV分量也不相同。利用這些閾值，在編碼率小于 1比特 /像素的條件下依然可以獲得非常好的圖像質(zhì)量。當(dāng)把量化步長乘以一個公共因數(shù)后，一般可以調(diào)整比特數(shù)，由此可以實(shí)現(xiàn)自適應(yīng)編碼。 88?2022/2/14 JPEG標(biāo)準(zhǔn) ? （ 4） 對 DCT量化系數(shù)進(jìn)行熵編碼，進(jìn)一步壓縮碼率?？梢圆捎盟銛?shù)編碼或 Huffman編碼（可變字長編碼 VLC）。對于當(dāng)前子塊的 DC系數(shù)與上一塊的 DC系數(shù)之差值進(jìn)行 VLC編碼壓縮數(shù)據(jù)，由于 DC分量是子塊的平均值，相鄰子塊間的相關(guān)性很強(qiáng)，同時，視覺上要求各子塊的平均灰度無明顯的跳躍，因此對 DC的差值作無失真的熵編碼是合適的。對于 AC系數(shù)不為零，采用 Z字形方式（ Zigzig）進(jìn)行一維掃描，然后將非零系數(shù)前面的 0的游程長度（個數(shù)）與該系數(shù)值一起作為統(tǒng)計(jì)事件進(jìn)行 VLC編碼。在基本系統(tǒng)中共推薦了兩組Huffman碼表，一組用于亮度信號 Y，另一組用于色差信號 U、V，每一組表又包括兩張表，一個用于 DC分量，一個用于 AC分量。 2022/2/14 MPEG標(biāo)準(zhǔn) ? 1987年， ISO和 CCITT成立了 “ 活動圖像專家組 ”（ Moving Picture