jpeg-ls

nullJPEG-LSJPEG-LSISO 14495什么是JPEG-LS什么是JPEG-LS用于连续色调静态图像的无损或近无损的压缩 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 practiceJPEG-LS从哪里来？JPEG-LS从哪里来？JPEG-LS是一种新的针对连续色调图像的无损/近无损压缩标准， ISO-14495-1/ITU-T.87，该标准是基于LOCO-I算法(LOw COmplexity LOssless COmpression for Images)。(见：http://www.hpl.hp.com/loco/) 近无损是指：一种有损压缩算法，它重建的图像与原图像对应像素的差值，不超过一个预先指定的值(loss, 通常较小)；无损压缩指loss = 0.LOCO-ILOCO-IMarcelo J. Weinberger, Gadiel Seroussi, and Guillermo Sapiro(1996) “LOCO-I: A Low Complexity, Context-Based, Lossless Image Compression Algorithm”, in Proceedings of Data Compression Conference, J. Storer, editor, Los Alamitos, CA, IEEE Computer Society PressLOCO-I 简介LOCO-I 简介是一种利用Huffman编码和上下文模型的算法。关于无损压缩关于无损压缩无损压缩包含两个独立的过程：建立模型和编码。 把图像中的像素按时间处理作为一维的数据，xi=x1x2…xi ,模型的目的是希望通过假定的条件概率分布p( .|xi)去推断xi+1. 在新的无损压缩算法中，概率的分配被分成三项工作： 预测，通过xi的一个子集给出xi+1的一个预测xxi+1 确定xi+1的上下文，通常为过去子序列的一个函数 给定xi+1的上下文时预测误差ei+1 = xi+1-xxi+1,的概率模型LOCO-I的描述LOCO-I的描述预测 上下文模型 编码分布 上下文的确定 编码 Golomb-Rice编码 序列参数估计 偏差删除 嵌入字母扩展Causal Template for LOCO-ICausal Template for LOCO-ILOCO-I所使用的用于预测的因果模版： x是当前像素，a b c d e是其相邻像素。预测预测LOCO-I的预测是在检测水平和垂直边的存在与否基础上做出的。如果没有边，预测值为a+b-c. min( a, b) 若c>=max(a,b) X的预测值= max( a, b) 若c<=min(a, b) a + b - c 其它 所以预测值是三个预测值a, b, a+b-c 的中间那个 。上下文模型上下文模型在上下文模型中，一个关键的目标是减少参数的数量，以避免上下文稀释作用”context dilution”。编码分布编码分布一般认为，对连续色调图像的预测误差近似地服从拉普拉斯分布。 对每一个上下文，选取适当的 Huffman编码表。上下文的确定上下文的确定上下文的确定从几个差值： g1=d−a; g2=a−c; g3=c−b, g4=b−e 开始，将g1,g2,g3量化成一些等概率的区域，g4由于远离预测点x，所以量化成较粗的值。 由于对称性，可以假设g1,g2,g3各量化成2R+1个区域，g4量化成2T+1个区域，T= 15},和它们对称的区域。g4的量化区域为：|g4| < 5, g4>=5, 和 g4<=−5.编码编码编码 Golomb-Rice编码 序列参数估计 偏差删除编码- Golomb-Rice编码编码- Golomb-Rice编码对于给定的正整数m，一个非负整数n用Golomb码Gm编码为两部分：n mod m的二进制表示，n/m的整数部分的一元码表示。 Golomb码对分布Q(n) = (1− p)pn 是最优的，对每一个这种形式的分布，存在一个m，使Gm产生平均最短的整数编码。 m = ceiling[ log(1 +p) / log(p−1)] Golomb-Rice是指m=2k时，记为：Rk n的编码为：n的低k位 + (n mod 2^k 的一元码表示) 所以码长为：k+1+floor[n/2k]编码- Golomb-Rice编码（续）编码- Golomb-Rice编码（续）因为待编码的预测误差可正可负，所以需作变换M(e)将-α/2<=e<=α/2-1变换至 0<=M(e)<=α-1： M(e) = 2e if e>=0 -2e-1 if e<0 如果e服从以0为中心的拉普拉斯分布，则M(e)近似地服从几何分布，所以适合采用Golomb-Rice编码。编码-序列参数估计编码-序列参数估计Golomb-Rice编码中k的确定是至关重要的。LOCO-I是在估计E(|e|)的基础上进行k的估计的。 考虑-α/2<=e<=α/2-1，预测误差e的离散拉普拉斯分布：P(e) = p0r|e| (0= A} 也可以用一行C代码求得： for ( k=0; (N<=0.5时增加，<=-0.5时减少，这将使平均预测误差趋向于-.5和.5之间）。 这种方法也有利于处理Golomb-Rice编码的另外一个缺陷：由于M(e)的影响，当k>0时，最好的分布是均值为-1/2, 而k=0时，为-2/9，所以平均（修正）预测误差可以在[-1, 0]之间，所以如果k=0并且B/N<-.5，编码为M(-1-e).嵌入字母表扩展嵌入字母表扩展Golomb-Rice编码，和其它的Huffman编码一样，对于理论编码位数小于1的符号，其实际的编码效率不高（平均码长大于理论值)。LOCO-I的办法是在上下文条件中嵌入字母表扩展。 当a=b=c=d，编码器进入游程模式。JPEG-LSJPEG-LSFrom: 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, Vol. 9, August 2000, pp.1309-1324. http://www.hpl.hp.com/loco/HPL-98-193R1.pdf JPEG-LS结构图JPEG-LS结构图JPEG-LS描述JPEG-LS描述JPEG-LS中的预测和模型是基于不同的因果模版。 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 Embedded alphabet extension (run coding) Summary of encoding proceduresPredictionPrediction 如果在当前像素左边有垂直边存在，用b预测x; 如果当前像素上面有水平的边存在，用b预测x; 没有检测到边时用a+b-c预测x. a, b, a+b-c 的中值（中值边检测MED）Context ModelingContext ModelingParameterization The TSGD model. Error residual alphabet in JPEG-LS. Context determination General approach. Contexts in JPEG-LS. Adaptive correction Bias estimation. Bias computation in JPEG-LS.Context Modeling.Context Modeling.Parameterization The TSGD model. 预测误差ϵ的概率正比于 实际上会考虑偏差，所以 其中Context Modeling..Context Modeling..Parameterization The TSGD model. Error residual alphabet in JPEG-LS. 预测误差Context Modeling…Context Modeling…Parameterization Context determination General approach. 个数（考虑对称性） Contexts in JPEG-LS. T=4, 365上下文Context Modeling....Context Modeling....Parameterization Context determination Adaptive correction Bias estimation. N: 上下文出现的数量 D: 预测误差的累计和 所以，校正值 用来加到 Bias computation in JPEG-LS.Context Modeling.....Context Modeling.....Adaptive correction Bias estimation. Bias computation in JPEG-LS.CodingCodingGolomb codes and optimal prefix codes for the TSGD Coding.Coding.Sequential parameter estimation 对每个上下文，令A是累计预测误差大小的和，B,N如上下文模型中的定义，计算k使： 如果k>0, 选择 如果k=0并且2B>-N, 选 其它， 选择Coding..Coding..Limited-length Golomb codes 若k=0，编码-128，需要256比特。 解决办法，设定qmax，超出时用qmax的编码后跟直接的2进制表示。Qmax作为转义码。ResetsResets同LOCO-IEmbedded alphabet extension Embedded alphabet extension Embedded alphabet extension (run coding) Motivation. Mode selection. Adaptive run length coding. Run interruption coding.Summary of encoding proceduresSummary of encoding procedures在图像边界处因果模版的未定义像素，这样处理：第一行，假设b=c=d=0；在第一列和最后一列，如果未定义，a和d假设为b，而c用编码上一行时赋给a的值。Summary of encoding procedures.Summary of encoding procedures.JPEG-LS: encoding of a single component.Summary of encoding procedures..Summary of encoding procedures..JPEG-LS: encoding of a single component..Summary of encoding procedures...Summary of encoding procedures...JPEG-LS: Run mode processing.