圖像處理第10章其他圖像編碼方法

第10章

其他圖像編碼方法圖像編碼：常借助許多其他數(shù)學工具和其他圖像技術，又有廣泛的應用領域，多年來已經(jīng)研究出許多特色的方法。有些基于特殊的理論和技術，有些則服務于特殊的領域。有對于頻域技術的變換編碼方法，有對于空域技術的預測編碼方法和其它方法。在圖像編碼中，壓縮率和失真是一對矛盾，對他們的折衷考慮也是許多編碼方法的初衷。本章主要內(nèi)容基于符號編碼矢量量化準無損編碼比較和評述第10章其他圖像編碼方法預測編碼LZW編碼10.1基于符號的編碼基本思路：在文本圖像編碼中，由于許多文字位圖會多次反復出現(xiàn)，所以可以考慮將每個文字看作一個基本符號或子圖象，而將文本圖象看作這些子圖象的集合;需要建立一個符號字典，存儲所有可能出現(xiàn)的符號（對每個符號賦一個碼）;對圖象的編碼→確定每個符號的碼字以及確定符號在圖象中的空間位置;一幅圖象可用一系列三元組來表示，即{(x1,y1,z1),(x2,y2,z2),……，}.（xi，yi）=位置，li=字典中位置標號編碼示例：設在需要編碼的圖象中有一個6字母的序列“ABABAB”。每個字母由一個7×5的象素矩陣來表示。設將象素矩陣用位圖來表示則每個字母，對應一幅含35個象素的位圖。圖10.1.1基于符號編碼的示例圖像表10.1.1基于編碼的結果將每個字母看作一個基本符號，則符號字典中有兩個符號“A”、“B”，分別為標號0和1，以圖10.1.1為例，左上角為坐標起點，則字母序列可以用一個三元組（前兩個表示符號左上角的坐標，第三個表示符號的坐標）序列表示。編碼的壓縮率：

原始圖象共有7行39列，需7×39=273個比特編碼后，原始圖象被表示成一個三元組序列。設對每個位置用一個字節(jié)（8個比特）來表示，每個三元組需24個比特，現(xiàn)有6個符號，所以需要144個比特。另外，字典需要70個比特，所以編碼結果需214個比特。此時壓縮率約為1.2757。將此字母序列的長度增加一倍，則壓縮率會增加到525/358=1.4665；對于分辨率較高的圖像，壓縮率也會較高。如上圖情況，但將圖像水平和垂直方向分辨率都增加1倍，則壓縮率2.5755。如果對位圖和三元數(shù)組也進行編碼，則總壓縮率還可提高?；诜柕慕獯a非常簡單，比編碼要快得多。只要讀出三元組序列中的各個標號，根據(jù)符號字典將對應符號的位圖寫在相應的坐標位置就可得到解碼的圖像。在國家標準JBIG2中，要編碼的圖像先被分割成重疊或不重疊的3個區(qū)域：文字區(qū)域、半調(diào)區(qū)域和一般其他區(qū)域。對前2個采用基于符號的編碼方法。10.2LZW編碼

LZW是一種信息保存型的編碼方式，能消除或減少圖象中的象素間冗余。LZW編碼對信源輸出的不同長度的符號序列分配固定長度的碼字，且不需要有關符號出現(xiàn)概率的知識（與哈夫曼碼等不同）。該編碼方法是UNIX操作系統(tǒng)中的標準文件壓縮方法，也用在GIF、TIFF、PDF中1、LZW編碼過程在編碼的開始階段要構造一個對信源符號進行編碼的碼本（字典）。在編碼器順序地掃描排成串象素的灰度時，算法要確定字典中還沒有出現(xiàn)過的灰度值序列的位置（如取下一個尚未用的位置），并建立（增加）一個新的碼字。字典的尺寸是一個重要的編碼器參數(shù)。如果太小，可用于匹配（放置）灰度值序列的位置會不夠；如果太大，表達碼字的比特數(shù)增加將影響對圖象壓縮的性能。LZW編碼過程示例：圖10.2.1一幅4×4的示例圖像表10.2.1初始字典設使用一個9比特可容納512個字的字典。先將字典前256個位置（碼字）對應分配給灰度初始字典值，后256個位置暫時空著。第257個位置用于下一個（目前尚未）出現(xiàn)的灰度值序列。

編碼的各個步驟和結果如書中表10.2.2所示。編碼器從左向右、從上向下對每個輸入像素掃描，作為編碼輸入，其灰度值如表中第2列所示。第3列的識別序列依此讀取上一個編碼輸入（開始為空）。第4列的拼接序列是由第2列編碼輸入和第3列同行中的識別序列相拼接（識別序列在前，稱為前綴串；編碼輸入在后，稱為擴展字符）而成的。對每個拼接序列都在字典中搜索，根據(jù)搜索結果可分為兩種情況：（1）如果找不到/尚沒有（如表中步驟2里用“—”表示），就對字典下一個還沒有使用的位置（如表中步驟2里從256開始）賦予這個拼接序列作為字典中的下一個新條目，并將同行的識別序列作為（第5列的）編碼輸出（如表中步驟2里是44）。（2）如果能找到/已有（如表中步驟3里用“+”表示），既不輸出字碼也不改變字典，而將這個拼接序列作為一個識別序列（如表中步驟4），并繼續(xù)考慮下一個步驟的編碼輸入。如果拼接了下一個編碼輸入后在字典中搜索不到這個新的拼接序列（如步驟4里仍用“—”表示），那么就將此時的識別序列用字典中的相應的碼字表示并作為編碼輸出，同時在字典中下一個還沒有使用的位置（如步驟4里是257）加一個新條目，以放置這個新的拼接序列。根據(jù)搜索結果分別按上述兩種情況進行，直到識別序列不再讀到新的編碼輸入，則將識別序列已有的字符作為最后一個編碼輸出（如表中步驟17）。最后的編碼輸出序列為第5列的9個碼字。在該例子中，共增加了8個新碼字，在編碼結束時，字典中共有264個碼字，每個碼字需9個比特來表示，用著264個碼字對全圖進行編碼。原始圖像共有16個像素，每個像素需用8個比特表示，全圖共需128個比特來表示。第五列編碼輸出為9個碼字，每個碼字需要9個比特來表示，共81個比特，該例中壓縮率為128/81≈1.58，或者說壓縮比1.58:1

LZW編碼的一個重要特性：前綴性，即如果一個碼字在字典中，那么它的前綴串也已在字典里。LZW編碼方法是一種自適應的壓縮方法，但它對輸入數(shù)據(jù)的適應比較慢，因為每次字典中的條目只增加一個，而且這個條目只比原有的條目增加了一個字符。LZW編碼中字典的尺寸與要編碼圖像的尺寸和內(nèi)容需要配合：在編碼初期，由于字典中碼字較少，字典對壓縮效果的貢獻也很少，此時主要進行字典的擴充；編碼后期，如果字典的容量有限，圖像太大時字典滿了，編碼效率也會受到限制。2、LZW解碼過程LZW編碼的特點是在編碼的同時建立了一個碼本。在LZW解碼時也會建立一個同樣的解碼碼本(編碼器和解碼器同步)。LZW解碼的步驟和結果如表10.2.3所示。首先依次讀取各個解碼輸入并判斷該碼字是否已在字典中（如第2列），然后構建拼接序列（如第3列），在構建字典（見最后兩列）的同時依次進行解碼（解碼輸出見第4列）。表10.2.3LZW解碼步驟和結果具體解碼時，先將第一個解碼輸入直接作為解碼輸出，然后從第2個解碼輸入開始，先考察其是否已在字典中，根據(jù)結果有兩種情況：（1）如果尚不在字典中，根據(jù)編碼過程和規(guī)則可知，一方面該字碼應是上一個解碼輸入的擴展，所以其前綴串應與上一個解碼輸入相同；另一方面其擴展字符也應與當前解碼輸入中的（從左數(shù)）第一個字符相同。所以如果當前解碼輸入為一個新碼字，則此時的拼接序列由上一個解碼輸入后接當前解碼輸入中的（從左數(shù))第一個字符而構成。據(jù)此就可在字典中加入對應當前解碼輸入的新條目，同時也可得到對應解碼輸入碼字的解碼輸出。（2）如果已在字典中，就將其直接作為解碼輸出；此時拼接序列也由上一個解碼輸入后接當前解碼輸入的第一個字符而構成，并將其放入字典新位置作為條目。10.3預測編碼預測編碼也能消除或減少圖像的像素間冗余。基本思路是通過僅提取每個像素中的新信息并對他們編碼來消除像素間的冗余。可分為無損預測編碼和有損預測編碼兩種。這里一個像素的新信息定義為該像素的當前或現(xiàn)實值與預測值的差。10.3.1無損預測編碼圖10.3.1無損預測編碼系統(tǒng)無損預測編碼系統(tǒng)，主要由一個編碼器和一個解碼器組成，它們各有一個相同的預測器。在無損編碼中，3個基本的步驟是預測、誤差映射、編碼。（首先根據(jù)某個像素的周邊條件即上下文對該像素的值進行預測，然后計算真實值與預測值的差，將差值進行一定映射后得到映射值，最后對該映射值進行編碼。）無損預測編碼過程：輸入序列：fn

(n=1,2,…)預測輸出:（舍入成整數(shù)）預測誤差：誤差編碼：在符號編碼器中用變長碼編碼誤差，解碼器利用接收到的變長碼字重建en解壓序列：

m階線性預測：1-D線性預測：m是線性預測器的階；round是舍入函數(shù)；ai是預測系數(shù)一階1-D線性預測：上式表示的預測器也稱為前值預測器，所對應的預測編碼方法也稱為差值編碼或前值編碼。2-D預測編碼中，預測是對圖像從左向右、從上向下進行掃描時所掃描到的先前像素的函數(shù)，3-D時，預測基于上述像素和前一幀的像素。通過預測可消除相當多的像素間冗余。10.3.2有損預測編碼（有損預測編碼雖然解碼圖像有些失真但可獲得較大的壓縮率）1、有損預測編碼系統(tǒng)在無損編碼系統(tǒng)上加一個量化器。

圖10.3.2有損預測編碼系統(tǒng)輸入序列：fn

(n=1,2,…)量化輸出：預測輸入：解壓序列：編碼誤差：相同德爾塔調(diào)制（DM）是一種簡單的有損預測編碼方法。預測器：量化器：預測系數(shù)a≤1，常數(shù)c>0是一個常數(shù)。DM方法得到的碼率是1比特/像素。圖例10.3.2,10.3.3顆粒噪聲：當C遠大于輸入中的最小變化時，如在n=0到n=3的相對平滑區(qū)，DM編碼會產(chǎn)生顆粒噪聲，即誤差正負波動。斜率過載:當c遠小于輸入中的最大變化時，如在n=5到n=9的相對陡峭區(qū)間，DM編碼會產(chǎn)生斜率過載，即(gn)變化跟不上fn的變換，有較大的正誤差。對大多數(shù)圖像來說，他們分別會導致圖像中目標邊緣發(fā)生模糊和整個圖像產(chǎn)生紋狀表面。這與所使用量化和預測方法及他們的相互作用有關，盡管有上面的相互作用，但預測器和量化器在設計中通常是獨立的。2、最優(yōu)預測最優(yōu)預測器滿足限制條件：最小化編碼器預測誤差：設量化誤差可以忽略基于這些條件的預測編碼方法稱為差值脈沖碼調(diào)制法（DPCM）設用一個四階線性預測器來預測：給上式中的系數(shù)賦予不同的值，可得到不同的預測器。4個例子如下：g4給出的是一個自適應預測器，它通過計算圖像的局部方向性來選擇合適的預測值已達到保持圖像邊緣的目的。系數(shù)之和一般設為小于或等于1：這個限制是為了使預測器的輸出落入允許的灰度值范圍內(nèi)和減少傳輸噪聲的影響，傳輸噪聲常使重建的圖像上出現(xiàn)水平的條紋。減少DPCM解碼器對輸入噪聲的敏感度是很重要的，因為在一定的條件下，只要有一個誤差就能影響其后所有的輸出而使輸出不穩(wěn)定。3、最優(yōu)量化梯狀函數(shù)：

重建電平

判別電平

量化函數(shù)

這個函數(shù)可完全由在第I象限的L/2個si和ti所描述。這些值給出的轉折點確定了函數(shù)的不連續(xù)性并被稱為量化器的判別電平和重建電平。

一個典型的量化函數(shù)

根據(jù)以上定義，量化器的設計就是要在給定優(yōu)化準則和輸入概率密度函數(shù)p(s)的條件選擇最優(yōu)的si和ti。優(yōu)化準則可以是統(tǒng)計的或心理視覺的準則。如果用最小均方量化誤差（即E｛s-ti｝2）作為準則，且p(s)是個偶函數(shù)，那么最小誤差條件為：(10.3.25)si=-s-iti=-t-i

(10.3.27)

式（10.3.25）表明重建電平是給定判別區(qū)間的p(s)曲線下面積的重心，式（10.3.26）指出判別值正好為兩個重建值的中指，式（10.3.27）可由q(s)是一個奇函數(shù)而得到。對任意L，滿足上面三個式子的si和ti在均方誤差意義下最優(yōu)。(10.3.26)10.4矢量量化矢量量化（VQ）:將一個有多個分量的矢量映射為一個只有較少分量的矢量。原則上，空域和頻域均可使用。矢量量化既可用于圖像編碼系統(tǒng)的量化模塊中，也可用作一種獨立的圖像編碼方法。他的理論基礎是率失真定理?；舅悸肥前研旁捶栃蛄蟹纸M作為矢量看待進行編碼。矢量量化考慮了以下兩個因素：(1)對符號串的壓縮比對單符號的壓縮更能取得好的效果（矢量編碼比標量編碼好）；(2)對自然圖象，空間上相鄰的象素之間有較大的相關性。1、矢量量化流程編碼過程如圖10.4.1所示。在編碼端，先將原始圖象劃分成小塊，用矢量來表示這些小塊并對矢量進行量化。構建一個碼本對圖象塊矢量編碼，在解碼端，根據(jù)矢量碼字的標號獲得碼矢量編好碼后，將矢量碼字的標號進行傳輸或存儲。在解碼端，解碼器根據(jù)矢量碼字的標號借助碼本獲得碼矢量，利用碼矢量重建出圖像塊并進而組成解碼圖像。圖10.4.1矢量量化編解碼流程2、矢量量化原理(1)將矢量空間分割為有限個子空間，它們覆蓋整個矢量空間且互相不相交。常用Voronoi區(qū)域劃分；(2)對每個子空間選擇一個代表矢量（如質(zhì)心），即碼矢量，作為量化結果。圖10.4.2Voronoi假設一幅圖可分為若干區(qū)域，現(xiàn)已知這些區(qū)域的重心，對于任意兩個重心點p和q，在它們之間都可以畫一條對分線，這條對分線將圖像分為兩半，其中一半包含與p較近的點，另一半包含與q較近的點，如果以p為參考，對所有其他重心點都當做q如上進行，就可得到一個包含p的多邊形，就是Voronoi多邊形。一個完整的矢量量化過程可看作由編碼器C和解碼器D兩個映射聯(lián)合構成，可分別寫為：其中：是標號集，每個標號對應一個碼矢量yi

;Y是碼本，包含N個碼矢量。C計算輸入矢量x與Y中各個碼矢量yi間的失真（誤差），然后輸出一個由映射確定的yi的標號i。D根據(jù)接收到的標號i從與編碼器相同的碼本中找到y(tǒng)i，并用yi代替輸入矢量x作為輸出矢量y。碼矢量標號i被編碼成由二進制表示的碼字對定長碼，為表示N個碼矢量標號需要每個碼有B=log2N個比特。對L維矢量,比特率（每像素的比特數(shù)）為:3、最優(yōu)碼本設計最優(yōu)的矢量量化應設計出能將平均失真降為最小的包含N個碼矢量的碼本。這里需要考慮兩個條件：(1)給定需量化的矢量x，最優(yōu)量化選擇碼矢量yi應能使x和yi間的失真最小(2)最優(yōu)量化選擇的碼矢量yi應能使對應子空間內(nèi)的平均失真最小，即yi為子空間的質(zhì)心。兩個條件表明，對給定的失真測度，確定碼矢量和分割子區(qū)間是相關的。確定了碼矢量，子區(qū)間的分割就確定了。反過來，分割了子區(qū)間，碼矢量也就確定了。典型的碼本設計方法是LBG算法（包括4個步驟），碼矢量由最小化訓練集X中的平均失真T得到：10.5準無損編碼

壓縮率和保真度常是一對矛盾。提高壓縮率常使解碼圖象的失真加大，而要求高保真度又常使壓縮率受到限制。準無損編碼可看作對無損編碼和有損編碼的一種折中，期望能在信息損失相對有損編碼不太大的情況下能達到比無損編碼更高的壓縮性能。

目前國際上以L∞范數(shù)來限定準無損編碼的壓縮率，即要使任意一個象素在壓縮前后其灰度差的絕對值都不大于某一預先給定的容限值。1、準無損壓縮算法分類（1）基于預測編碼的方法對誤差量化，即將誤差e量化為，然后對進行誤差映射和熵編碼。例子：（2）基于可逆變換的方法變換部分是無損的，但預處理過程及其逆過程中允許出現(xiàn)誤差（但不超過設定的容限值）(3)有損加準無損的方法先對圖像進行有損壓縮，然后對差值部分進行準無損壓縮。2、JPEG-LSJPEG-LS是基于上下文模型的空域壓縮算法，對量化誤差為0的象素采用游程編碼，游程編碼過程由游程檢測及游程長度編碼兩步完成。流程圖如下：

上下文模型對當前象素進行分類，用以選擇編碼方式及控制編碼各環(huán)節(jié)。圖10.5.2所示為當前編碼象素的上下文位置關系，進入游程編碼的上下文條件是：圖10.5.2JPEG-LS算法中的上下文位置關系3、準無損CALIC算法基于上下文的自適應圖像編碼（CALIC）是一種典型的無損/準無損壓縮方法，也稱基于上下文分類的自適應預測熵編碼，其基本流程如如圖10.5.3所示。各像素按光柵掃描的順序依次處理。圖10.5.3CALIC基本算法流程圖預測上下文：水平方向的dh和垂直方向的dv；誤差修正上下文w、熵編碼上下文s。10.6比較和評述10.6.1不同方法特性的比較●變換編碼方法可以較好地保持圖象的主觀質(zhì)量；●預測編碼方法的特點是用較小的計算代價就可取得較高的壓縮率；●矢量量化方法需要使用比較復雜的編碼器；●哈夫曼編碼把固定數(shù)目的符號轉變成可變長度的碼字；●算術編碼把可變數(shù)目的符號轉變成可變長度的碼字；●LZW編碼則把可變數(shù)目的符號轉變成固定長度的碼字。

現(xiàn)在我們來討論熵編碼中對圖像解碼時要考慮的兩個特性：即時性和唯一性（1）解碼的即時性指對任意一個有限長的碼符號串，可以對每個碼字分別解碼（2）解碼的唯一性也稱單義性，指對任意一個有限長的碼符號串，只有一種分解成其各個碼符號的方法（只能以一種方式解）。

即時碼一定是唯一可解碼，但唯一可解碼不一定是即時碼（如用算術編碼得到的是唯一可解碼但它并不是即時碼）。不是唯一可解碼肯定也不是即時碼，但不是即時碼并不能確定該碼是否為唯一可解碼。10.6.2其他編碼方法1