多媒體數(shù)字壓縮技術(shù).ppt

多媒體數(shù)據(jù)壓縮技術(shù) 什么是數(shù)據(jù)壓縮 數(shù)據(jù)壓縮就是在一定的精度損失條件下 以最少的數(shù)碼表示信源所發(fā)出的信號(hào) 分鐘數(shù)字音頻信號(hào)需要的存儲(chǔ)空間 1 分鐘數(shù)字視頻信號(hào)需要的存儲(chǔ)空間 1 壓縮編碼技術(shù)基礎(chǔ) 多媒體數(shù)據(jù)壓縮的必要性多媒體信息是海量信息 彩色電視信號(hào)信息量100Mb S 圖象 聲音多媒體海量信息的數(shù)據(jù)存儲(chǔ) 處理 傳輸是軟 硬件技術(shù)難題數(shù)據(jù)壓縮的可行性信息論觀點(diǎn) 信源數(shù)據(jù)是信息量 信源熵 和信息冗余量之和信息冗余 空間冗余 時(shí)間冗余 結(jié)構(gòu)冗余 知識(shí)冗余 視覺(jué)冗余等數(shù)據(jù)壓縮通過(guò)減少冗余量而盡可能保留信源信息量壓縮編碼方法分類冗余度壓縮 無(wú)損壓縮 信息保持編碼或熵編碼 可逆運(yùn)算信息量壓縮 有損壓縮 失真度編碼或熵壓縮編碼 不可逆 允許失真 空間冗余 一幅圖像表面上各采樣點(diǎn)的顏色之間往往存在著空間連貫性 基于離散像素采樣來(lái)表示物體表面顏色的像素存儲(chǔ)方式可利用空間連貫性 達(dá)到減少數(shù)據(jù)量的目的 例如 在靜態(tài)圖像中有一塊表面顏色均勻的區(qū)域 在此區(qū)域中所有點(diǎn)的光強(qiáng)和色彩以及飽和度都是相同的 因此數(shù)據(jù)有很大的空間冗余 時(shí)間冗余 運(yùn)動(dòng)圖像一般為位于一時(shí)間軸區(qū)間的一組連續(xù)畫(huà)面 其中的相鄰幀往往包含相同的背景和移動(dòng)物體 只不過(guò)移動(dòng)物體所在的空間位置略有不同 所以后一幀的數(shù)據(jù)與前一幀的數(shù)據(jù)有許多共同的地方 這種共同性是由于相鄰幀記錄了相鄰時(shí)刻的同一場(chǎng)景畫(huà)面 所以稱為時(shí)間冗余 同理 語(yǔ)音數(shù)據(jù)中也存在著時(shí)間冗余 視覺(jué)冗余 人類的視覺(jué)系統(tǒng)對(duì)圖像場(chǎng)的敏感度是非均勻的 但是 在記錄原始的圖像數(shù)據(jù)時(shí) 通常假定視覺(jué)系統(tǒng)近似線性的和均勻的 對(duì)視覺(jué)敏感和不敏感的部分同等對(duì)待 從而產(chǎn)生比理想編碼 即把視覺(jué)敏感和不敏感的部分區(qū)分開(kāi)來(lái)的編碼 更多的數(shù)據(jù) 這就是視覺(jué)冗余 時(shí)間域壓縮 迅速傳輸媒體信源頻率域壓縮 并行開(kāi)通更多業(yè)務(wù)空間域壓縮 降低存儲(chǔ)費(fèi)用能量域壓縮 降低發(fā)射功率 數(shù)據(jù)壓縮的好處 壓縮編碼的衡量指標(biāo) 壓縮比要大恢復(fù)后的失真小壓縮算法要簡(jiǎn)單 速度快壓縮能否用硬件實(shí)現(xiàn) 經(jīng)典數(shù)據(jù)壓縮理論 信息論中的信源編碼理論解決的主要問(wèn)題 1 數(shù)據(jù)壓縮的理論極限 2 數(shù)據(jù)壓縮的基本途徑 信源 信源被抽象為一個(gè)隨機(jī)變量序列 隨機(jī)過(guò)程 如果信源輸出的隨機(jī)變量取值于某一連續(xù)區(qū)間 就叫做連續(xù)信源 比如語(yǔ)音信號(hào)X t 如果信源輸出的隨機(jī)變量取值于某一離散符號(hào)集合 就叫做離散信源 比如平面圖像X x y 和電報(bào) 信源 X1 X2 X3 X4 離散信源 如果隨機(jī)序列中各個(gè)變量具有相同的概率分布 則稱為離散平穩(wěn)信源 如果離散平穩(wěn)信源的輸出序列中各個(gè)變量是相互獨(dú)立的 即前一個(gè)符號(hào)的出現(xiàn)不影響以后任何一個(gè)符號(hào)出現(xiàn)的概率 則稱為離散無(wú)記憶平穩(wěn)信源 否則稱為離散有記憶平穩(wěn)信源 信源 X1 X2 X3 X4 a1 a2 a3 am 信息量和熵 信息量的度量 信源S熵的定義 信源熵舉例一幅用256級(jí)灰度表示的圖象 每個(gè)像素點(diǎn)灰度的概率均等 編碼每個(gè)像素需8位40個(gè)像素組成的灰度圖象 灰度為5級(jí) ABCDE 出現(xiàn)每個(gè)灰度的像素個(gè)數(shù)不同 為 15 7 7 6 5 該圖象的熵為H s 2 196 40個(gè)像素需40 2 196 87 84位 信息量和熵 仙農(nóng)信息論把一個(gè)事件 字符a1 所攜帶的信息量定義為 I a1 log2 1 p log2p bit 其中p為事件發(fā)生 字符出現(xiàn) 的概率I a1 即隨機(jī)變量X取值為a1時(shí)所攜帶的信息量因?yàn)閄的信息量也是一個(gè)隨機(jī)變量 所以我們要研究它的統(tǒng)計(jì)特性 其數(shù)學(xué)期望為 稱H X 為一階信息熵或者簡(jiǎn)稱為熵 Entropy 熵 Entropy 在符號(hào)出現(xiàn)之前 熵表示符號(hào)集中的符號(hào)出現(xiàn)的平均不確定性 在符號(hào)出現(xiàn)之后 熵代表接收一個(gè)符號(hào)所獲得的平均信息量 根據(jù)直覺(jué) 信源編碼的數(shù)據(jù)輸出速率 平均碼長(zhǎng) 與信源熵之間應(yīng)該有某種對(duì)應(yīng)關(guān)系 信源的概率分布與熵的關(guān)系 熵的大小與信源的概率模型有著密切的關(guān)系 最大離散熵定理 當(dāng)與信源對(duì)應(yīng)的字符集中的各個(gè)字符為等概率分布時(shí) 熵具有極大值log2m m為字符集中字符個(gè)數(shù) 二進(jìn)制信源的熵 二進(jìn)制信源輸出一個(gè)二進(jìn)制數(shù)碼所攜帶的平均信息量最大為1bit 最大離散熵定理的應(yīng)用 對(duì)于同一個(gè)信源其總的信息量是不變的 如果能夠通過(guò)某種變換 編碼 使信源盡量等概率分布 則每個(gè)輸出符號(hào)所獨(dú)立攜帶的信息量增大 那么傳送相同信息量所需要的序列長(zhǎng)度就越短 離散無(wú)記憶信源的冗余度隱含在信源符號(hào)的非等概率分布之中 只要H X 小于log2m 就存在數(shù)據(jù)壓縮的可能 編碼 信源 X1 X2 X3 X4 a1 a2 a3 am 信源 X1 X2 X3 X4 b1 b2 b3 bn 0 1 平均碼長(zhǎng)與熵 如果對(duì)字符aj的編碼長(zhǎng)度為L(zhǎng)j 則X的平均碼長(zhǎng)為 根據(jù)前面對(duì)二進(jìn)制信源的分析 有 在Lj log2pj時(shí) 平均碼長(zhǎng)取得極小值H X 關(guān)于離散無(wú)記憶平穩(wěn)信源的結(jié)論 一階熵即為離散無(wú)記憶平穩(wěn)信源的壓縮極限 基本極限 只要信源不是等概率分布 就存在著數(shù)據(jù)壓縮的可能性 數(shù)據(jù)壓縮的基本途徑之一 使各字符的編碼長(zhǎng)度盡量等于字符的信息量 聯(lián)合熵與條件熵 設(shè)隨機(jī)變量X和Y分別取值于符號(hào)表 a1 a2 am 和 b1 b2 b3 bn 定義X與Y的聯(lián)合熵為 定義X關(guān)于Y的條件熵為 離散有記憶信源的冗余 聯(lián)合熵與其可能達(dá)到的最大值之間的差值反映了該有記憶信源所含的冗余度 這種冗余是由于隨機(jī)變量序列之間的相關(guān)性造成的 關(guān)于離散有記憶平穩(wěn)信源的結(jié)論 離散有記憶平穩(wěn)信源的壓縮極限為 壓縮的基本途徑之二 盡量去除各分量之間的相關(guān)性 再對(duì)各分量進(jìn)行獨(dú)立編碼 壓縮的基本途徑之三 可利用條件概率進(jìn)行編碼 階越高越有利 壓縮的基本途徑之四 可將多個(gè)分量合并成向量 利用其聯(lián)合概率進(jìn)行編碼 聯(lián)合的分量越多越有利 多媒體數(shù)據(jù)壓縮編碼分類 無(wú)損壓縮香農(nóng) 范諾編碼哈夫曼編碼算術(shù)編碼 前三個(gè)為統(tǒng)計(jì)編碼 RLE編碼 行程編碼 增量調(diào)制編碼詞典編碼 有損壓縮預(yù)測(cè)編碼 DPCM 運(yùn)動(dòng)補(bǔ)償?shù)让嫦蝾l率域方法 正交變換 DCT 子帶編碼等面向空間域方法 統(tǒng)計(jì)分塊編碼等基于重要性方法 濾波 子采樣 比特分配 矢量量化等模型方法 分形編碼 模型基編碼等 混合壓縮編碼JBIG JPEG MPEG H 261等技術(shù)標(biāo)準(zhǔn) 熵編碼 熵編碼包括香農(nóng) 范諾編碼 霍夫曼編碼和算術(shù)編碼 其宗旨在于找到一種編碼使得平均碼長(zhǎng)到達(dá)熵極限 基本思想就是對(duì)出現(xiàn)概率較大的符號(hào)取較短的碼長(zhǎng) 而對(duì)出現(xiàn)概率較小的符號(hào)取較大的碼長(zhǎng) 無(wú)損壓縮編碼算法 香農(nóng) 范諾編碼與哈夫曼編碼哈夫曼編碼 根據(jù)統(tǒng)計(jì)頻率生成Huffman樹(shù) 然后編碼前綴碼 編解碼簡(jiǎn)單實(shí)際使用時(shí) 對(duì)文件進(jìn)行兩遍掃描 第一遍統(tǒng)計(jì)頻率 第二遍編碼壓縮比不高對(duì)錯(cuò)誤敏感 沒(méi)有錯(cuò)誤保護(hù)功能 形成錯(cuò)誤傳播 霍夫曼編碼 具體步驟 1 初始化 2 合并概率最小的兩個(gè)事件 3 排序 4 如果事件個(gè)數(shù)大于2則重復(fù) 2 和 3 5 賦值 6 編碼 霍夫曼編碼舉例 H X 1 75L1 2L2 1 75 霍夫曼編碼的局限性 利用霍夫曼編碼 每個(gè)符號(hào)的編碼長(zhǎng)度只能為整數(shù) 所以如果源符號(hào)集的概率分布不是2負(fù)n次方的形式 則無(wú)法達(dá)到熵極限 輸入符號(hào)數(shù)受限于可實(shí)現(xiàn)的碼表尺寸譯碼復(fù)雜需要實(shí)現(xiàn)知道輸入符號(hào)集的概率分布沒(méi)有錯(cuò)誤保護(hù)功能 香農(nóng) 范諾編碼 香農(nóng) 范諾編碼與Huffman編碼相反 采用從上到下的方法 具體步驟為 1 首先將編碼字符集中的字符按照出現(xiàn)頻度和概率進(jìn)行排序 2 用遞歸的方法分成兩部分 使兩個(gè)部分的概率和接近于相等 直至不可再分 即每一個(gè)葉子對(duì)應(yīng)一個(gè)字符 3 編碼 香農(nóng) 范諾編碼舉例 0 1 0 1 0 0 1 1 無(wú)損壓縮編碼算法 算術(shù)編碼消息用0到1之間的實(shí)數(shù)進(jìn)行編碼兩個(gè)參數(shù) 符號(hào)的概率和它的編碼間隔信源符號(hào)的概率決定壓縮編碼的效率 也決定編碼過(guò)程中信源符號(hào)的間隔對(duì)錯(cuò)誤敏感 容易形成錯(cuò)誤傳播 算術(shù)編碼 Huffman編碼的局限性 Huffman編碼使用整數(shù)個(gè)二進(jìn)制位對(duì)符號(hào)進(jìn)行編碼 這種方法在許多情況下無(wú)法得到最優(yōu)的壓縮效果 假設(shè)某個(gè)字符的出現(xiàn)概率為80 該字符事實(shí)上只需要 log2 0 8 0 322位編碼 但Huffman編碼一定會(huì)為其分配一位0或一位1的編碼 可以想象 整個(gè)信息的80 在壓縮后都幾乎相當(dāng)于理想長(zhǎng)度的3倍左右 算術(shù)編碼 基本思想 算術(shù)編碼不是將單個(gè)信源符號(hào)映射成一個(gè)碼字 而是把真?zhèn)€信源表示為實(shí)數(shù)線上的0到1之間的一個(gè)區(qū)間 其長(zhǎng)度等于該序列的概率 再在該區(qū)間內(nèi)選擇一個(gè)代表性的小數(shù) 轉(zhuǎn)化為二進(jìn)制作為實(shí)際的編碼輸出 消息序列中的每個(gè)元素都要用來(lái)縮短這個(gè)區(qū)間 消息序列中元素越多 所得到的區(qū)間就越小 當(dāng)區(qū)間變小時(shí) 就需要更多的數(shù)位來(lái)表示這個(gè)區(qū)間 采用算術(shù)編碼每個(gè)符號(hào)的平均編碼長(zhǎng)度可以為小數(shù) 算術(shù)編碼舉例 一 算術(shù)編碼舉例 二 最后的子區(qū)間起始位置 85 256 0 01010101子區(qū)間長(zhǎng)度 27 256 0 00011011子區(qū)間尾 7 16 0 0111取編碼區(qū)間中的一個(gè)值 最后編碼為 011 信源分布 算術(shù)編碼的具體實(shí)現(xiàn) 因?yàn)閷?shí)際只能用有限長(zhǎng)的寄存器 這就要求將已編碼的高位碼字及時(shí)輸出 但又不能輸出過(guò)早 以免后續(xù)運(yùn)算還要調(diào)整已輸出的碼位 請(qǐng)看參考書(shū)上給出的算法 算術(shù)編碼每次遞推都要做乘法 所以效率比較低 二進(jìn)制算術(shù)編碼是一種實(shí)用的編碼算法 用移位代替了乘法 使效率大大提高 自適應(yīng)算術(shù)編碼可以在編碼過(guò)程中根據(jù)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)的修改分布概率 這樣可以避免在編碼之前必須精確求出信源概率的難題 自適應(yīng)算術(shù)編碼舉例 輸入序列為 bcc 行程編碼 RLE 行程編碼 Run LengthEncoding 它通過(guò)將信源中相同符號(hào)序列轉(zhuǎn)換成一個(gè)計(jì)數(shù)字段再加上一個(gè)重復(fù)字符標(biāo)志實(shí)現(xiàn)壓縮 例如 RTTTTTTTTABBCDG被轉(zhuǎn)換為 R 8TABBCDG 其中 作為轉(zhuǎn)義字符 表明其后所跟的字符表示長(zhǎng)度 行程編碼多用于黑白二值圖像的壓縮中 例如00000000111111111111000001111111被轉(zhuǎn)化為一系列黑串和白串長(zhǎng)度的編碼 81257 因?yàn)榇L(zhǎng)度并非等概率分布 所以一般要配合以統(tǒng)計(jì)編碼 Huffman編碼 無(wú)損壓縮編碼算法 RLE行程編碼一系列重復(fù)值有一個(gè)單獨(dú)值和計(jì)數(shù)值代替當(dāng)一行中有連續(xù)n n 63 個(gè)相同像素時(shí) 第一個(gè)字節(jié)最高兩位為11 低位為n 第二個(gè)字節(jié)為重復(fù)像素值當(dāng)一個(gè)像素與后續(xù)不同時(shí) 如果像素高位為11 則仍用兩個(gè)字節(jié)表示 但重復(fù)個(gè)數(shù)為1 即第一個(gè)為11000001 第二為像素值當(dāng)一個(gè)像素與后續(xù)不同且高位不為11時(shí) 直接存儲(chǔ)該像素壓縮比取決于圖象的連續(xù)性 無(wú)損壓縮編碼算法 詞典編碼通用數(shù)據(jù)流壓縮方法編碼前不需要構(gòu)造碼表 它從一個(gè)簡(jiǎn)單的表開(kāi)始隨著工作進(jìn)展構(gòu)建一個(gè)更有效的碼表用簡(jiǎn)單代碼替換比較復(fù)雜的字串 并用一個(gè)轉(zhuǎn)換表記錄這些替換關(guān)系轉(zhuǎn)換表通過(guò)動(dòng)態(tài)生成 且壓縮完畢后 無(wú)須記錄該轉(zhuǎn)換表 詞典編碼 詞典編碼主要利用數(shù)據(jù)本身包含許多重復(fù)的字符串的特性 例如 吃葡萄不吐葡萄皮 不吃葡萄倒吐葡萄皮 我們?nèi)绻靡恍┖?jiǎn)單的代號(hào)代替這些字符串 就可以實(shí)現(xiàn)壓縮 實(shí)際上就是利用了信源符號(hào)之間的相關(guān)性 字符串與代號(hào)的對(duì)應(yīng)表就是詞典 實(shí)用的詞典編碼算法的核心就是如何動(dòng)態(tài)地形成詞典 以及如何選擇輸出格式以減小冗余 第一類詞典編碼 第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過(guò) 然后用已經(jīng)出現(xiàn)過(guò)的字符串替代重復(fù)的部分 它的輸出僅僅是指向早期出現(xiàn)過(guò)的字符串的 指針 LZ77算法 LZ77算法在某種意義上又可以稱為 滑動(dòng)窗口壓縮 該算法將一個(gè)虛擬的 可以跟隨壓縮進(jìn)程滑動(dòng)的窗口作為詞典 要壓縮的字符串如果在該窗口中出現(xiàn) 則輸出其出現(xiàn)位置和長(zhǎng)度 使用固定大小窗口進(jìn)行詞語(yǔ)匹配 而不是在所有已經(jīng)編碼的信息中匹配 是因?yàn)槠ヅ渌惴ǖ臅r(shí)間消耗往往很多 必須限制詞典的大小才能保證算法的效率 隨著壓縮的進(jìn)程滑動(dòng)詞典窗口 使其中總包含最近編碼過(guò)的信息 是因?yàn)閷?duì)大多數(shù)信息而言 要編碼的字符串往往在最近的上下文中更容易找到匹配串 LZ77編碼的基本流程 1 從當(dāng)前壓縮位置開(kāi)始 考察未編碼的數(shù)據(jù) 并試圖在滑動(dòng)窗口中找出最長(zhǎng)的匹配字符串 如果找到 則進(jìn)行步驟2 否則進(jìn)行步驟3 2 輸出三元符號(hào)組 off len c 其中off為窗口中匹配字符串相對(duì)窗口邊界的偏移 len為可匹配的長(zhǎng)度 c為下一個(gè)字符 即不匹配的第一個(gè)字符 然后將窗口向后滑動(dòng)len 1個(gè)字符 繼續(xù)步驟1 3 輸出三元符號(hào)組 0 0 c 其中c為當(dāng)前字符 然后將窗口向后滑動(dòng)1個(gè)字符 繼續(xù)步驟1 LZ77算法 LZ77編碼舉例 LZSS算法 LZ77通過(guò)輸出真實(shí)字符解決了在窗口中出現(xiàn)沒(méi)有匹配串的問(wèn)題 但這個(gè)解決方案包含有冗余信息 冗余信息表現(xiàn)在兩個(gè)方面 一是空指針 二是編碼器可能輸出額外的字符 這種字符是指可能包含在下一個(gè)匹配串中的字符 LZSS算法的思想是如果匹配串的長(zhǎng)度比指針本身的長(zhǎng)度長(zhǎng)就輸出指針 匹配串長(zhǎng)度大于等于MIN LENGTH 否則就輸出真實(shí)字符 另外要輸出額外的標(biāo)志位區(qū)分是指針還是字符 LZSS編碼的基本流程 1 從當(dāng)前壓縮位置開(kāi)始 考察未編碼的字符 并試圖在滑動(dòng)窗口中找出最長(zhǎng)的匹配字符串 如果匹配串長(zhǎng)度len大于等于最小匹配串長(zhǎng)度 len MIN LENGTH 則進(jìn)行步驟2 否則進(jìn)行步驟3 2 輸出指針二元組 off len 其中off為窗口中匹配字符串相對(duì)窗口邊界的偏移 len為匹配串的長(zhǎng)度 然后將窗口向后滑動(dòng)len個(gè)字符 繼續(xù)步驟1 3 輸出當(dāng)前字符c 然后將窗口向后滑動(dòng)1個(gè)字符 繼續(xù)步驟1 LZSS編碼舉例 輸入數(shù)據(jù)流 編碼過(guò)程MIN LEN 2 LZSS算法 在相同的計(jì)算機(jī)環(huán)境下 LZSS算法比LZ77可獲得比較高的壓縮比 而譯碼同樣簡(jiǎn)單 這也就是為什么這種算法成為開(kāi)發(fā)新算法的基礎(chǔ) 許多后來(lái)開(kāi)發(fā)的文檔壓縮程序都使用了LZSS的思想 例如 PKZip GZip ARJ LHArc和ZOO等等 其差別僅僅是指針的長(zhǎng)短和窗口的大小等有所不同 LZSS同樣可以和熵編碼聯(lián)合使用 例如ARJ就與霍夫曼編碼聯(lián)用 而PKZip則與Shannon Fano聯(lián)用 它的后續(xù)版本也采用霍夫曼編碼 第二類詞典編碼 第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè) 短語(yǔ)詞典 dictionaryofthephrases 這種短語(yǔ)可以是任意字符的組合 編碼數(shù)據(jù)過(guò)程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的 短語(yǔ) 時(shí) 編碼器就輸出這個(gè)詞典中的短語(yǔ)的 索引號(hào) 而不是短語(yǔ)本身 LZ78算法 LZ78的編碼思想是不斷地從字符流中提取新的字符串 String 通俗地理解為新 詞條 然后用 代號(hào) 也就是碼字 Codeword 表示這個(gè) 詞條 這樣一來(lái) 對(duì)字符流的編碼就變成了用碼字 Codeword 去替換字符流 Charstream 生成碼字流 Codestream 從而達(dá)到壓縮數(shù)據(jù)的目的 LZ78編碼器的輸出是碼字 字符 W C 對(duì) 每次輸出一對(duì)到碼字流中 與碼字W相對(duì)應(yīng)的字符串 String 用字符C進(jìn)行擴(kuò)展生成新的字符串 String 然后添加到詞典中 LZ78編碼算法 步驟1 將詞典和當(dāng)前前綴P都初始化為空 步驟2 當(dāng)前字符C 字符流中的下一個(gè)字符 步驟3 判斷P C是否在詞典中 1 如果 是 則用C擴(kuò)展P 即讓P P C 返回到步驟2 2 如果 否 則輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字W和當(dāng)前字符C 即 W C 將P C添加到詞典中 令P 空值 并返回到步驟2 LZ78編碼舉例 輸入數(shù)據(jù)流 編碼過(guò)程 LZW算法 J Ziv和A Lempel在1978年首次發(fā)表了介紹第二類詞典編碼算法的文章 在他們的研究基礎(chǔ)上 TerryA Welch在1984年發(fā)表了改進(jìn)這種編碼算法的文章 因此把這種編碼方法稱為L(zhǎng)ZW Lempel ZivWalch 壓縮編碼 在編碼原理上 LZW與LZ78相比有如下差別 LZW只輸出代表詞典中的字符串 String 的碼字 codeword 這就意味在開(kāi)始時(shí)詞典不能是空的 它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符 即在編碼匹配時(shí) 至少可以在詞典中找到長(zhǎng)度為1的匹配串 LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來(lái)完成的 LZW算法的詞典 LZW編碼器 軟件編碼器或硬件編碼器 就是通過(guò)管理這個(gè)詞典完成輸入與輸出之間的轉(zhuǎn)換 LZW編碼器的輸入是字符流 Charstream 字符流可以是用8位ASCII字符組成的字符串 而輸出是用n位 例如12位 表示的碼字流 Codestream 碼字代表單個(gè)字符或多個(gè)字符組成的字符串 String LZW編碼算法 步驟1 將詞典初始化為包含所有可能的單字符 當(dāng)前前綴P初始化為空 步驟2 當(dāng)前字符C 字符流中的下一個(gè)字符 步驟3 判斷P C是否在詞典中 1 如果 是 則用C擴(kuò)展P 即讓P P C 返回到步驟2 2 如果 否 則輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字W 將P C添加到詞典中 令P C 并返回到步驟2 LZW編碼舉例 輸入數(shù)據(jù)流 編碼過(guò)程 LZW算法 LZW算法得到普遍采用 它的速度比使用LZ77算法的速度快 因?yàn)樗恍枰獔?zhí)行那么多的綴 符串比較操作 對(duì)LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長(zhǎng)度 以及在詞典中刪除老的綴 符串 在GIF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法 LZW算法取得了專利 專利權(quán)的所有者是美國(guó)的一個(gè)大型計(jì)算機(jī)公司 Unisys 優(yōu)利系統(tǒng)公司 除了商業(yè)軟件生產(chǎn)公司之外 可以免費(fèi)使用LZW算法 預(yù)測(cè)編碼 基本原理根據(jù)某種模型 利用以前的一個(gè)或多個(gè)樣本值 對(duì)當(dāng)前的樣本進(jìn)行預(yù)測(cè)對(duì)當(dāng)前樣本實(shí)際值和預(yù)測(cè)值之差進(jìn)行編碼若模型選取足夠好 圖象或聲音樣本時(shí)間相關(guān)性很強(qiáng) 壓縮比高特點(diǎn)算法簡(jiǎn)單 速度快 易于硬件實(shí)現(xiàn)編碼壓縮比不太高誤碼易于擴(kuò)散 抗干擾性差 預(yù)測(cè)編碼 預(yù)測(cè)編碼是數(shù)據(jù)壓縮理論的一個(gè)重要分支 它根據(jù)離散信號(hào)之間存在一定相關(guān)性的特點(diǎn) 利用前面的一個(gè)或多個(gè)信號(hào)對(duì)下一個(gè)信號(hào)進(jìn)行預(yù)測(cè) 然后對(duì)實(shí)際值和預(yù)測(cè)值的差 預(yù)測(cè)誤差 進(jìn)行編碼 如果預(yù)測(cè)比較準(zhǔn)確 那么誤差信號(hào)就會(huì)很小 就可以用較少的碼位進(jìn)行編碼 以達(dá)到數(shù)據(jù)壓縮的目的 第n個(gè)符號(hào)Xn的熵滿足 所以參與預(yù)測(cè)的符號(hào)越多 預(yù)測(cè)就越準(zhǔn)確 該信源的不確定性就越小 數(shù)碼率就可以降低 預(yù)測(cè)編碼 分類線性預(yù)測(cè)編碼和非線性預(yù)測(cè)編碼幀內(nèi)預(yù)測(cè)編碼和幀間預(yù)測(cè)編碼 量化器 編碼器 預(yù)測(cè)器 解碼器 預(yù)測(cè)器 信道 輸入XN 輸出XN 發(fā)送端 接收端 eNXN eN XN eN XN DPCM是有損型還是無(wú)損型關(guān)鍵看對(duì)預(yù)測(cè)誤差ek如何編碼 預(yù)測(cè)方程式 線性預(yù)測(cè) 如果ai是常數(shù) 則為時(shí)不變線性預(yù)測(cè) 否則為自適應(yīng)線性預(yù)測(cè) ADPCM 最簡(jiǎn)單的預(yù)測(cè)方程 最佳線性預(yù)測(cè) 使誤差函數(shù)達(dá)到最小值的預(yù)測(cè)方程式叫做最佳線性預(yù)測(cè) 求最佳線性預(yù)測(cè)的各個(gè)參數(shù)ai 列方程組 代入 得到聯(lián)立方程組 如果為一階線性預(yù)測(cè) 則可求得 圖像信號(hào)的預(yù)測(cè)編碼 一副數(shù)字圖像可以看成一個(gè)空間點(diǎn)陣 圖像信號(hào)不僅在水平方向是相關(guān)的 在垂直方向也是相關(guān)的 根據(jù)已知樣值與待預(yù)測(cè)樣值間的位置關(guān)系 可以分為 1 一維預(yù)測(cè) 行內(nèi)預(yù)測(cè) 利用同一行上相鄰的樣值進(jìn)行預(yù)測(cè) 2 二維預(yù)測(cè) 幀內(nèi)預(yù)測(cè) 利用同一行和前面幾行的數(shù)據(jù)進(jìn)行預(yù)測(cè) 3 三維預(yù)測(cè) 幀間預(yù)測(cè) 利用相鄰幾幀 或不同波段 上的取樣值進(jìn)行預(yù)測(cè) 靜止圖像的二維預(yù)測(cè)編碼 這種壓縮算法被應(yīng)用到JPEG標(biāo)準(zhǔn)的無(wú)損壓縮模式之中 中等復(fù)雜程度的圖像壓縮比可達(dá)到2 1 c a b x d 三鄰域預(yù)測(cè)法 活動(dòng)圖像的幀間預(yù)測(cè)編碼 視頻信號(hào)的冗余度主要體現(xiàn)在空間相關(guān)性 幀內(nèi) 時(shí)間相關(guān)性 幀間 和色度空間表示上的相關(guān)性 對(duì)于每秒25幀 30 的電視信號(hào) 其相繼幀之間存在極強(qiáng)的相關(guān)性 據(jù)統(tǒng)計(jì)256級(jí)灰度的黑白圖像序列 幀間差值超過(guò)3的象素?cái)?shù)不超過(guò)4 所以在活動(dòng)圖像序列中可以利用前面的幀來(lái)預(yù)測(cè)后面的幀 以實(shí)現(xiàn)數(shù)據(jù)壓縮 幀間預(yù)測(cè)編碼技術(shù)被廣泛應(yīng)用到H 261 H 263 MPEG 1和MPEG 2等視頻壓縮標(biāo)準(zhǔn)之中 具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測(cè) 活動(dòng)圖像序列中的一個(gè)畫(huà)面可以大致劃分為3個(gè)區(qū)域 1 背景區(qū) 相鄰兩個(gè)畫(huà)面的背景區(qū)基本相同 2 運(yùn)動(dòng)物體區(qū) 可以視為由前一個(gè)畫(huà)面的某一區(qū)域的像素平移而成 位移矢量 3 暴露區(qū) 指物體運(yùn)動(dòng)后而顯露出來(lái)的曾被遮蓋的背景區(qū)域 運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)就是將前一個(gè)畫(huà)面的背景區(qū) 平移后的運(yùn)動(dòng)物體區(qū)作為后一個(gè)畫(huà)面的預(yù)測(cè)值 運(yùn)動(dòng)補(bǔ)償幀間預(yù)測(cè)編碼 運(yùn)動(dòng)補(bǔ)償幀間預(yù)測(cè)從原理上包括如下幾個(gè)基本步驟 1 圖像分割 把圖像劃分為靜止的背景和若干運(yùn)動(dòng)的物體 各個(gè)物體可能有不同的位移 但構(gòu)成同一物體的所有像素的位移相同 2 運(yùn)動(dòng)矢量估值 考察前后兩個(gè)畫(huà)面 利用運(yùn)動(dòng)估值算法得到每個(gè)物體的位移矢量 3 運(yùn)動(dòng)補(bǔ)償 用運(yùn)動(dòng)矢量補(bǔ)償物體的運(yùn)動(dòng)效果再進(jìn)行預(yù)測(cè) 4 編碼 除了對(duì)實(shí)測(cè)值與預(yù)測(cè)值之間的差值進(jìn)行編碼傳送外 還要傳送位移矢量以及區(qū)域分割信息 運(yùn)動(dòng)補(bǔ)償幀間預(yù)測(cè)編碼 編碼器 運(yùn)動(dòng)補(bǔ)償 圖像輸入 運(yùn)動(dòng)矢量輸出 譯碼器 幀緩存 運(yùn)動(dòng)估值 預(yù)測(cè)誤差輸出 變換編碼 預(yù)測(cè)編碼希望通過(guò)對(duì)信源建模來(lái)盡可能的預(yù)測(cè)源數(shù)據(jù) 而變換編碼則考慮將原始數(shù)據(jù)變換到另一個(gè)表示空間 使數(shù)據(jù)在新的空間上盡可能相互獨(dú)立 而能量更集中 X Y X Y 變換編碼 基本思路先將空間域圖象通過(guò)某種正交變換 獲得一系列變換系數(shù)在變換過(guò)程中 使圖象變換系數(shù)能量相對(duì)集中再對(duì)其變換系數(shù)進(jìn)行區(qū)域量化 按其所含能量大小 分配不同數(shù)據(jù)量分類傅立葉變換 哈爾變換 沃爾西 哈達(dá)瑪變換 斜變換等 圖象 分塊變換 區(qū)域采樣 量化編碼 圖象再現(xiàn) 反變換 填零 譯碼 存儲(chǔ)或傳輸 混合編碼技術(shù)與國(guó)際標(biāo)準(zhǔn) JPEG編碼標(biāo)準(zhǔn)H 261標(biāo)準(zhǔn)簡(jiǎn)介MPEG標(biāo)準(zhǔn)概述MPEG 1標(biāo)準(zhǔn)MPEG 2標(biāo)準(zhǔn)MPEG 4標(biāo)準(zhǔn) 算法概要 JPEG JointPhotographicExpertsGroup 是一個(gè)由ISO和CCITT兩個(gè)組織機(jī)構(gòu)聯(lián)合組成的一個(gè)圖像專家小組 負(fù)責(zé)制定靜態(tài)的數(shù)字圖像數(shù)據(jù)壓縮編碼標(biāo)準(zhǔn) 這個(gè)專家組開(kāi)發(fā)的算法稱為JPEG算法 并且成為國(guó)際上通用的標(biāo)準(zhǔn) JPEG是一個(gè)適用范圍很廣的靜態(tài)圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn) 既可用于灰度圖像又可用于彩色圖像 JPEG不僅適于靜止圖像的壓縮 電視圖像的幀內(nèi)圖像的壓縮編碼 也常采用此算法 JPEG標(biāo)準(zhǔn)還可以大范圍地調(diào)節(jié)圖像壓縮率及其保真度 標(biāo)準(zhǔn)主要采用了兩種基本的壓縮算法 一種是采用以離散余弦變換 DCT 為基礎(chǔ)的有損壓縮算法 另一種是采用以預(yù)測(cè)技術(shù)為基礎(chǔ)的DPCM無(wú)損壓縮算法 JPEG編碼標(biāo)準(zhǔn) JPEG編碼標(biāo)準(zhǔn) 基于DPCM的無(wú)損編碼模式 壓縮比可以達(dá)到2 1 基于DCT的有損順序編碼模式 壓縮比可以達(dá)到10 1以上 基于DCT的遞增編碼模式基于DCT的分層編碼模式 JPEG規(guī)定了4種運(yùn)行模式 以滿足不同需要 JPEG有損順序編碼算法的主要計(jì)算步驟如下 1 將源圖像分成幾個(gè)顏色平面 分量圖像 2 分成8 8數(shù)據(jù)塊進(jìn)行正向離散余弦變換 FDCT 2 量化 quantization 3 Z字形排列量化結(jié)果 zigzagscan 4 使用差分脈沖編碼調(diào)制 differentialpulsecodemodulation DPCM 對(duì)直流系數(shù) DC 進(jìn)行編碼 5 使用行程長(zhǎng)度編碼 run lengthencoding RLE 對(duì)交流系數(shù) AC 進(jìn)行編碼 6 熵編碼 entropycoding JPEG編碼標(biāo)準(zhǔn) JPEG編碼標(biāo)準(zhǔn) 譯碼或者叫做解壓縮的過(guò)程與壓縮編碼過(guò)程正好相反 IDCT JPEG編碼標(biāo)準(zhǔn) 正向離散余弦變換 對(duì)每個(gè)單獨(dú)的彩色圖像分量 把整個(gè)分量圖像分成8 8的圖像塊 如圖所示 并作為兩維離散余弦變換DCT的輸入 通過(guò)DCT變換 把能量集中在少數(shù)幾個(gè)系數(shù)上 DCT變換使用下式計(jì)算 逆變換使用下式計(jì)算 JPEG編碼標(biāo)準(zhǔn) 量化 對(duì)于有損壓縮算法 JPEG算法使用如圖所示的均勻量化器進(jìn)行量化 量化步距是按照系數(shù)所在的位置和每種顏色分量的色調(diào)值來(lái)確定 JPEG編碼標(biāo)準(zhǔn) 量化 因?yàn)槿搜蹖?duì)亮度信號(hào)比對(duì)色差信號(hào)更敏感 因此使用了兩種量化表 亮度量化值和色差量化值 此外 由于人眼對(duì)低頻分量的圖像比對(duì)高頻分量的圖像更敏感 因此圖中的左上角的量化步距要比右下角的量化步距小 JPEG編碼標(biāo)準(zhǔn) DC系數(shù)DPCM編碼和AC系數(shù)Z形排列之后采用RLE編碼 JPEG編碼標(biāo)準(zhǔn) 熵編碼 使用熵編碼還可以對(duì)DPCM編碼后的直流DC系數(shù)和RLE編碼后的交流AC系數(shù)作進(jìn)一步的壓縮 JPEG標(biāo)準(zhǔn)規(guī)定了兩種熵編碼算法 哈夫曼編碼和自適應(yīng)算術(shù)編碼 哈夫曼編碼采用的一般是固定的哈夫曼編碼表 而不是臨時(shí)統(tǒng)計(jì)出來(lái)的 并且對(duì)亮度分量和色度分量采用了不同的哈夫曼表 JPEG編碼標(biāo)準(zhǔn) 基于DPCM的無(wú)損編碼模式 主要采用了三鄰域二維預(yù)測(cè)編碼和熵編碼 無(wú)失真編碼器 源圖像數(shù)據(jù) 壓縮的圖像數(shù)據(jù) 預(yù)測(cè)器 熵編碼器 表說(shuō)明 DPCM預(yù)測(cè)編碼框圖 JPEG編碼標(biāo)準(zhǔn) JPEG編碼標(biāo)準(zhǔn) 基于DCT的遞增編碼模式 此模式與順序模式編碼步驟基本一致 不同之處在于遞增模式每個(gè)圖像分量的編碼要經(jīng)過(guò)多次掃描才完成 第一次掃描只進(jìn)行一次粗糙的壓縮 然后根據(jù)此數(shù)據(jù)先重建一幅質(zhì)量低的圖像 以后的掃描再作較細(xì)的掃描 使重建圖像質(zhì)量不斷提高 直到滿意為止 遞增模式分為兩種 1 按頻段累進(jìn) 2 按位累進(jìn) JPEG編碼標(biāo)準(zhǔn) 基于DCT的分層編碼模式 1 降低原始圖像的空間分辨率 2 對(duì)已經(jīng)降低分辨率的圖像按照順序編碼模式進(jìn)行壓縮并存儲(chǔ)或傳輸 3 對(duì)低分辨率圖像進(jìn)行解碼 然后用插值法提高圖像的分辨率 4 將分辨率已經(jīng)升高的圖像作為原圖像的預(yù)測(cè)值 并把它與原圖像的差值進(jìn)行基于DCT的編碼 5 重復(fù)步驟3 4直到圖像達(dá)到完整的分辨率 H 261概述 H 261也稱P 64 這是ITU T 前身為CCITT 最早制定的關(guān)于視頻編碼的國(guó)際標(biāo)準(zhǔn) 考慮到ISDN的傳輸碼率以64kbps為單位 因此以p 64kbps p 1 30 作為為H 261的標(biāo)準(zhǔn)碼率 H 261標(biāo)準(zhǔn)主要用于電視電話和電視會(huì)議 它支持QCIF p 1 2 CIF p 2 兩種圖像輸入格式 H 261解決的問(wèn)題 第一是編碼算法問(wèn)題 確立了一種合理的 保證圖像質(zhì)量且為各國(guó)圖像編碼專家所公認(rèn)的統(tǒng)一的算法 算法必須能夠?qū)崟r(shí)操作 解碼延時(shí)要短 第二是與PCM標(biāo)準(zhǔn)兼容的問(wèn)題 編解碼器以64 1920kb s的工作速率去覆蓋N ISDN或PCM一次群的通道 第三 解決電視制式不同的問(wèn)題 為了使同一標(biāo)準(zhǔn)既能用于PAL 625 和NTSC 525 兩種電視制式系統(tǒng) 源編碼基于中間格式CIF格式 所以輸入輸必須經(jīng)轉(zhuǎn)換到CIF或QCIF格式再進(jìn)行源編碼 視頻編碼圖像格式一覽表 H 261的信源編碼算法 信源編碼算法的一般形式如下圖所示 主要由幀間預(yù)測(cè) 幀內(nèi)分塊和量化組成 H 261的信源編碼算法 一 將預(yù)測(cè)誤差或輸入圖像劃分成為8 8的象素塊 進(jìn)一步 將4個(gè)亮度像塊和兩個(gè)在空間位置上與之重疊的色差像塊符合成一個(gè)16 16的宏塊 MB 二 對(duì)于幀序列中的第一副圖像或景物變換后的第一副圖像 采用幀內(nèi)變換編碼 利用8 8的DCT實(shí)現(xiàn) 各DCT系數(shù)經(jīng)過(guò)線性量化 變長(zhǎng)編碼后進(jìn)入緩沖器 根據(jù)緩沖器的上溢和下溢 來(lái)反饋調(diào)節(jié)量化器的量化步長(zhǎng) 以控制視頻編碼位流使之與信倒速率相匹配 H 261的信源編碼算法 幀間預(yù)測(cè)采用混合方法 利用運(yùn)動(dòng)補(bǔ)償預(yù)測(cè) 當(dāng)預(yù)測(cè)誤差超過(guò)某個(gè)門限后 對(duì)誤差做DCT 視覺(jué)加權(quán)量化及熵編碼 運(yùn)動(dòng)矢量信息編碼后也送到緩沖器中 DCT去除空間冗余度 而使用有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測(cè)來(lái)去除時(shí)間上的冗余 這是一個(gè)典型的幀內(nèi) 幀間自適應(yīng)預(yù)測(cè)加DCT變換的混合算法 H 261的圖像復(fù)用編碼 H 261源編碼后進(jìn)行圖像復(fù)用編碼 實(shí)際上是把比特流分成圖像 Picture 像塊組 GOB Groupofblocks 宏塊 MB Macroblock 和像塊 Block 并附加相應(yīng)的信息 按照CIF格式 每幀CIF圖像包含12個(gè)GOB 每個(gè)GOB包含33個(gè)MB 每個(gè)MB包含4個(gè)亮度數(shù)據(jù)塊和各1個(gè)Cb Cr色度塊 每個(gè)B包含8 8象素 H 261的圖像復(fù)用編碼 H 261數(shù)據(jù)流結(jié)構(gòu) H 261視頻壓縮算法 利用二維DCT減少圖像的空間域的冗余度 利用運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)減少圖像的時(shí)間域冗余度 利用視覺(jué)加權(quán)量化減少圖像 灰度域 的冗余度 利用熵編碼來(lái)減少圖像的 頻率域 的冗余度 H 26標(biāo)準(zhǔn)系列 ITU T于1990年成立了 ATM視頻編碼專家組 負(fù)責(zé)制定適用于B ISDN信道ATM編碼傳輸標(biāo)準(zhǔn) 該專家組于1993年11月與ISO的MPEG專家組聯(lián)合提出了H 262建議草案 MPEG 2 用于數(shù)字存儲(chǔ)介質(zhì)和數(shù)字視頻通信中圖像信息的編碼表示和解碼規(guī)定 該標(biāo)準(zhǔn)向下兼容 能夠在很寬的范圍內(nèi)對(duì)不同分辨率和不同輸出比特的圖像信號(hào)有效的進(jìn)行壓縮 H 263是ITU制定的低比特率視頻信號(hào)壓縮標(biāo)準(zhǔn) 可以應(yīng)用于PSTN和移動(dòng)通信網(wǎng) 30Kb s MPEG標(biāo)準(zhǔn)概述 MPEG MovingPictureExpertGroup 是在1988年由國(guó)際標(biāo)準(zhǔn)化組織 ISO 和國(guó)際電工委員會(huì) IEC 聯(lián)合成立的專家組 負(fù)責(zé)開(kāi)發(fā)電視圖像數(shù)據(jù)和聲音數(shù)據(jù)的編碼 解碼和它們的同步等標(biāo)準(zhǔn) 這個(gè)專家組開(kāi)發(fā)的標(biāo)準(zhǔn)稱為MPEG標(biāo)準(zhǔn) MPEG