1、JPEG-LS,ISO 14495,什么是JPEG-LS,用于連續(xù)色調(diào)靜態(tài)圖像的無損或近無損的壓縮 specifies encoder processes for converting source image data to compressed image data specifies decoder processes for converting compressed image data to reconstructed image data provides guidance on how to implement these processes in practice,JPEG-

2、LS從哪里來？,JPEG-LS是一種新的針對(duì)連續(xù)色調(diào)圖像的無損/近無損壓縮標(biāo)準(zhǔn)， ISO-14495-1/ITU-T.87，該標(biāo)準(zhǔn)是基于LOCO-I算法(LOw COmplexity LOssless COmpression for Images)。(見： 近無損是指：一種有損壓縮算法，它重建的圖像與原圖像對(duì)應(yīng)像素的差值，不超過一個(gè)預(yù)先指定的值(loss, 通常較小)；無損壓縮指loss = 0.,LOCO-I,Marcelo J. Weinberger, Gadiel Seroussi, and Guillermo Sapiro(1996) “LOCO-I: A Low Complexity

3、, Context-Based, Lossless Image Compression Algorithm”, in Proceedings of Data Compression Conference, J. Storer, editor, Los Alamitos, CA, IEEE Computer Society Press,LOCO-I 簡(jiǎn)介,是一種利用Huffman編碼和上下文模型的算法。,關(guān)于無損壓縮,無損壓縮包含兩個(gè)獨(dú)立的過程：建立模型和編碼。 把圖像中的像素按時(shí)間處理作為一維的數(shù)據(jù)，xi=x1x2xi ,模型的目的是希望通過假定的條件概率分布p( .|xi)去推斷xi+1.

4、在新的無損壓縮算法中，概率的分配被分成三項(xiàng)工作： 預(yù)測(cè)，通過xi的一個(gè)子集給出xi+1的一個(gè)預(yù)測(cè)xxi+1 確定xi+1的上下文，通常為過去子序列的一個(gè)函數(shù) 給定xi+1的上下文時(shí)預(yù)測(cè)誤差ei+1 = xi+1-xxi+1,的概率模型,LOCO-I的描述,預(yù)測(cè) 上下文模型 編碼分布 上下文的確定 編碼 Golomb-Rice編碼 序列參數(shù)估計(jì) 偏差刪除 嵌入字母表擴(kuò)展,Causal Template for LOCO-I,LOCO-I所使用的用于預(yù)測(cè)的因果模版：x是當(dāng)前像素，a b c d e是其相鄰像素。,預(yù)測(cè),LOCO-I的預(yù)測(cè)是在檢測(cè)水平和垂直邊的存在與否基礎(chǔ)上做出的。如果沒有邊，預(yù)測(cè)值

5、為a+b-c. min( a, b) 若c=max(a,b)X的預(yù)測(cè)值= max( a, b) 若c=min(a, b) a + b - c 其它 所以預(yù)測(cè)值是三個(gè)預(yù)測(cè)值a, b, a+b-c 的中間那個(gè) 。,上下文模型,在上下文模型中，一個(gè)關(guān)鍵的目標(biāo)是減少參數(shù)的數(shù)量，以避免上下文稀釋作用”context dilution”。,編碼分布,一般認(rèn)為，對(duì)連續(xù)色調(diào)圖像的預(yù)測(cè)誤差近似地服從拉普拉斯分布。對(duì)每一個(gè)上下文，選取適當(dāng)?shù)腍uffman編碼表。,上下文的確定,上下文的確定從幾個(gè)差值：g1=da; g2=ac; g3=cb, g4=be 開始，將g1,g2,g3量化成一些等概率的區(qū)域，g4由于遠(yuǎn)離

6、預(yù)測(cè)點(diǎn)x，所以量化成較粗的值。 由于對(duì)稱性，可以假設(shè)g1,g2,g3各量化成2R+1個(gè)區(qū)域，g4量化成2T+1個(gè)區(qū)域，TR， 所以總共有(2T+1)(2R+1)3個(gè)不同上下文，但考慮對(duì)稱性：Probei+1 = |Ci = q1; q2; q3; q4 = Probei+1 = |Ci = q1;q2;q3;q4，所以上下文數(shù)量減少到：(2T+1)(2R+1)3+1)/2，所以如果取R=4,T=1，總共有1094個(gè)上下文,上下文的確定（續(xù)）,由于對(duì)稱上下文的合并，實(shí)際編碼的誤差可能是預(yù)測(cè)誤差的相反數(shù)，不過這是解碼器也可以預(yù)料的，所以能夠正常解碼。 對(duì)于每像素8位的字母表，g1,g2,g3的量化

7、區(qū)域可以是：0, 1, 2, 3, 4, 5, 6, 7, 8, , 14, e| e = 15,和它們對(duì)稱的區(qū)域。g4的量化區(qū)域?yàn)椋簗g4| =5, 和 g4=5.,編碼,編碼 Golomb-Rice編碼 序列參數(shù)估計(jì) 偏差刪除,編碼- Golomb-Rice編碼,對(duì)于給定的正整數(shù)m，一個(gè)非負(fù)整數(shù)n用Golomb碼Gm編碼為兩部分：n mod m的二進(jìn)制表示，n/m的整數(shù)部分的一元碼表示。 Golomb碼對(duì)分布Q(n) = (1 p)pn 是最優(yōu)的，對(duì)每一個(gè)這種形式的分布，存在一個(gè)m，使Gm產(chǎn)生平均最短的整數(shù)編碼。m = ceiling log(1 +p) / log(p1) Golomb-

8、Rice是指m=2k時(shí)，記為：Rk n的編碼為：n的低k位 + (n mod 2k 的一元碼表示)所以碼長(zhǎng)為：k+1+floorn/2k,編碼- Golomb-Rice編碼（續(xù)）,因?yàn)榇幋a的預(yù)測(cè)誤差可正可負(fù)，所以需作變換M(e)將-/2=0 -2e-1 if e0 如果e服從以0為中心的拉普拉斯分布，則M(e)近似地服從幾何分布，所以適合采用Golomb-Rice編碼。,編碼-序列參數(shù)估計(jì),Golomb-Rice編碼中k的確定是至關(guān)重要的。LOCO-I是在估計(jì)E(|e|)的基礎(chǔ)上進(jìn)行k的估計(jì)的。 考慮-/2=e=/2-1，預(yù)測(cè)誤差e的離散拉普拉斯分布：P(e) = p0r|e| (0r1,

9、p0取值使和為1). 則預(yù)測(cè)誤差大小的期望是：可以證明關(guān)于k的較好估計(jì)是：,編碼-序列參數(shù)估計(jì)（續(xù)）,為了估計(jì)k，編、解碼器對(duì)每一個(gè)上下文維護(hù)兩個(gè)變量 N：到當(dāng)前為止的預(yù)測(cè)誤差數(shù)量 A：到當(dāng)前為止的預(yù)測(cè)誤差累計(jì)大小 所以期望ar,可以用A/N估計(jì)，因此k=min k | 2k N = A也可以用一行C代碼求得：for ( k=0; (Nk)A; k+ ); 為了使這些計(jì)算更適應(yīng)圖像的局部特性，可以讓N超過一定閾值如N0時(shí)，讓N和A減半（或復(fù)位），一般可取N0為64到256中的數(shù)。,編碼- 偏差刪除,Golomb-Rice編碼很大地依賴于預(yù)測(cè)誤差的分布以0為中心、兩邊對(duì)稱、指數(shù)衰減，如果這些假設(shè)

10、不成立，編碼的效果就不好。 LOCO-I用來減少系統(tǒng)偏差的方法：對(duì)每個(gè)上下文，確定一些變量 N，上下文出現(xiàn)的個(gè)數(shù) B，上下文的累計(jì)預(yù)測(cè)誤差(在加上C之后) C，糾正值，用來加在x的估計(jì)值上（初始為0，如果修正后的預(yù)測(cè)誤差均值=0.5時(shí)增加，0時(shí)，最好的分布是均值為-1/2, 而k=0時(shí)，為-2/9，所以平均（修正）預(yù)測(cè)誤差可以在-1, 0之間，所以如果k=0并且B/N-.5，編碼為M(-1-e).,嵌入字母表擴(kuò)展,Golomb-Rice編碼，和其它的Huffman編碼一樣，對(duì)于理論編碼位數(shù)小于1的符號(hào)，其實(shí)際的編碼效率不高（平均碼長(zhǎng)大于理論值)。LOCO-I的辦法是在上下文條件中嵌入字母表擴(kuò)展

11、。 當(dāng)a=b=c=d，編碼器進(jìn)入游程模式。,JPEG-LS,From:M. Weinberger, G. Seroussi, G. Sapiro, The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS, Hewlett-Packard Laboratories Technical Report No. HPL-98-193R1, November 1998, revised October 1999. IEEE Trans. Image Processing, V

12、ol. 9, August 2000, pp.1309-1324. ,JPEG-LS結(jié)構(gòu)圖,JPEG-LS描述,JPEG-LS中的預(yù)測(cè)和模型是基于不同的因果模版。 Prediction Context Modeling Parameterization Context determination Adaptive correction Coding Golomb codes and optimal prefix codes for the TSGD Sequential parameter estimation Limited-length Golomb codes Resets Embedd

13、ed alphabet extension (run coding) Summary of encoding procedures,Prediction,如果在當(dāng)前像素左邊有垂直邊存在，用b預(yù)測(cè)x; 如果當(dāng)前像素上面有水平的邊存在，用b預(yù)測(cè)x; 沒有檢測(cè)到邊時(shí)用a+b-c預(yù)測(cè)x. a, b, a+b-c 的中值（中值邊檢測(cè)MED）,Context Modeling,Parameterization The TSGD model. Error residual alphabet in JPEG-LS. Context determination General approach. Context

14、s in JPEG-LS. Adaptive correction Bias estimation. Bias computation in JPEG-LS.,Context Modeling.,Parameterization The TSGD model. 預(yù)測(cè)誤差的概率正比于 實(shí)際上會(huì)考慮偏差，所以 其中,Context Modeling.,Parameterization The TSGD model. Error residual alphabet in JPEG-LS.預(yù)測(cè)誤差,Context Modeling,Parameterization Context determinat

15、ion General approach. 個(gè)數(shù)（考慮對(duì)稱性） Contexts in JPEG-LS.T=4, 365上下文,Context Modeling.,Parameterization Context determination Adaptive correction Bias estimation.N: 上下文出現(xiàn)的數(shù)量D: 預(yù)測(cè)誤差的累計(jì)和所以，校正值 用來加到 Bias computation in JPEG-LS.,Context Modeling.,Adaptive correction Bias estimation. Bias computation in JPEG-

16、LS.,Coding,Golomb codes and optimal prefix codes for the TSGD,Coding.,Sequential parameter estimation 對(duì)每個(gè)上下文，令A(yù)是累計(jì)預(yù)測(cè)誤差大小的和，B,N如上下文模型中的定義，計(jì)算k使：如果k0, 選擇如果k=0并且2B-N, 選其它， 選擇,Coding.,Limited-length Golomb codes 若k=0，編碼-128，需要256比特。解決辦法，設(shè)定qmax，超出時(shí)用qmax的編碼后跟直接的2進(jìn)制表示。Qmax作為轉(zhuǎn)義碼。,Resets,同LOCO-I,Embedded alphabet extension,Embedded alphabet extension (run coding) Motivation. Mode selection. Adaptive run length coding. Run interruption coding.,Summary of encoding procedures,在圖像邊界處因果模版的未定義像素，這樣處理：