基于固定长度编码的影像压缩方法及装置。该方法用于压缩包含复数个像素的区块，包含：根据所述像素的像素值，从所述像素中决定第一代表像素、第二代表像素及第三代表像素，其中该第一代表像素、该第二代表像素及该第三代表像素在所述像素所对应的一色彩空间中不共线；根据该第一代表像素及该第三代表像素内插产生复数个第一内插像素；根据该第二代表像素及该第三代表像素内插产生复数个第二内插像素；以及根据该第一代表像素、该第二代表像素、该第三代表像素、所述第一内插像素及所述第二内插像素，针对所述像素的每一像素产生一索引值。
1.一种基于固定长度编码的影像压缩方法，用于压缩包含复数个像素的区块，包含：根据所述像素的像素值，从所述像素中决定第一代表像素、第二代表像素及第三代表像素，其中该第一代表像素、该第二代表像素及该第三代表像素在所述像素所对应的色彩空间中不共线；
根据该第一代表像素及该第三代表像素内插产生复数个第一内插像素；
根据该第二代表像素及该第三代表像素内插产生复数个第二内插像素；以及根据该第一代表像素、该第二代表像素、该第三代表像素、所述第一内插像素及所述第二内插像素，针对所述像素的每一像素产生索引值，其中该第一代表像素、该第二代表像素、该第三代表像素、所述第一内插像素及所述第二内插像素构成复数个编码像素，所述针对所述像素的每一像素产生该索引值的步骤包括：编号所述编码像素，使每一编码像素具有编号；
从所述编码像素中决定在该色彩空间中与该目标像素距离最短的目标编码像素；以及以该目标编码像素的该编号作为该目标像素的该索引值。
以该第一代表像素、该第二代表像素、该第三代表像素的完整像素值或量化后的像素值及所述索引值代表该区块。
3.根据权利要求1所述的影像压缩方法，其中每一像素的像素值对应至复数个色彩通道，所述决定该第一代表像素、该第二代表像素及该第三代表像素的步骤包括：计算所述像素在所述色彩通道的复数个分布范围；
根据所述分布范围的最大分布范围，决定该第一代表像素及该第二代表像素，其中该第一代表像素及该第二代表像素分别包含对应于该最大分布范围的色彩通道的最大像素值及最小像素值；以及从所述像素中决定该第三代表像素，该第三代表像素不同于该第一代表像素及该第二代表像素，其中该第三代表像素与该第一代表像素及该第二代表像素在该色彩空间中所形成的三角形的面积大于其他像素与该第一代表像素及该第二代表像素所形成的三角形的面积。
4.根据权利要求1所述的影像压缩方法，其中所述索引值为第一索引值，该方法还包括：根据该第一代表像素及该第二代表像素内插产生复数个第三内插像素；
根据该第一代表像素、该第二代表像素及所述第三内插像素，针对所述像素的每一像素产生第二索引值；
调整该第一代表像素及该第二代表像素，以产生第一调整后代表像素及第二调整后代表像素；
根据该第一代表像素、该第二代表像素、该第三代表像素及所述第一索引值建立第一解码区块；
根据该第一调整后代表像素、该第二调整后代表像素及所述第二索引值建立第二解码区块；
根据该第一区块差值及该第二区块差值决定以该第一代表像素、该第二代表像素、该第三代表像素的完整像素值或量化后的像素值及所述第一索引值代表该区块，或是以该第一调整后代表像素、该第二调整后代表像素的完整像素值或量化后的像素值及所述第二索引值代表该区块。
5.一种基于固定长度编码的影像压缩装置，用于压缩包含复数个像素的区块，包括：存储器，储存所述像素的像素值；
比较电路，耦接该存储器，根据所述像素的像素值，从所述像素中决定第一代表像素、第二代表像素及第三代表像素，其中该第一代表像素、该第二代表像素及该第三代表像素在所述像素所对应的色彩空间中不共线；以及计算电路，耦接该存储器及该比较电路，执行以下步骤：根据该第一代表像素及该第三代表像素内插产生复数个第一内插像素，以及根据该第二代表像素及该第三代表像素内插产生复数个第二内插像素；以及根据该第一代表像素、该第二代表像素、该第三代表像素、所述第一内插像素及所述第二内插像素，针对所述像素的每一像素产生索引值，其中该第一代表像素、该第二代表像素、该第三代表像素、所述第一内插像素及所述第二内插像素构成复数个编码像素，所述针对所述像素的每一像素产生该索引值的步骤包括：编号所述编码像素，使每一编码像素具有编号；
从所述编码像素中决定在该色彩空间中与该目标像素距离最短的目标编码像素；以及以该目标编码像素的该编号作为该目标像素的该索引值。
6.一种基于固定长度编码的影像压缩方法，用于压缩包含复数个像素的区块，其中每一像素的像素值对应至复数个色彩通道，所述方法包括：根据所述像素的像素值，从所述像素中决定第一代表像素及第二代表像素，所述决定该第一代表像素及该第二代表像素的步骤包括：在所述色彩通道之一者中决定该第一代表像素及该第二代表像素，其中该第一代表像素及该第二代表像素分别包括对应于所述色彩通道之一者的最大像素值及最小像素值；
根据该第一代表像素及该第二代表像素内插产生复数个内插像素；
根据该第一代表像素、该第二代表像素及所述内插像素，针对所述像素的每一像素产生索引值，所述针对所述像素的每一像素产生该索引值的步骤包括：编号所述编码像素，使每一编码像素具有编号；
从所述编码像素中决定在所述像素所对应的色彩空间中与该目标像素距离最短的目标编码像素；以及以该目标编码像素的该编号作为该目标像素的该索引值；
调整该第一代表像素及该第二代表像素，以产生第一调整后代表像素及第二调整后代表像素；以及以该第一调整后代表像素、该第二调整后代表像素的完整像素值或量化后的像素值及所述索引值代表该区块。
7.根据权利要求6所述的影像压缩方法，所述决定该第一代表像素及该第二代表像素的步骤包括：计算所述像素在所述色彩通道的复数个分布范围；以及
根据所述分布范围的最大分布范围，决定该第一代表像素及该第二代表像素，其中该第一代表像素及该第二代表像素分别包括对应于该最大分布范围的色彩通道的最大像素值及最小像素值。
8.根据权利要求6所述的影像压缩方法，其中所述调整该第一代表像素及该第二代表像素的步骤包括：计算该区块的第一像素平均值；
根据该第一代表像素、该第二代表像素及所述索引值建立解码区块；
将该第一代表像素的像素值及该第二代表像素的像素值减去该第二像素平均值再加上该第一像素平均值，以分别产生该第一调整后代表像素及该第二调整后代表像素。
基于固定长度编码的影像压缩方法及装置
技术领域
[0001] 本申请是关于影像压缩，尤其是关于基于固定长度编码的影像压缩方法及装置背景技术
[0002] 在多媒体领域为了减少存储器储存空间以及数据传输的带宽(data bandwidth)，常会对影像进行压缩。影像压缩技术可分成两大类：可变长度编码(variable length code,VLC)以及固定长度编码(fixed length code,FLC)。固定长度编码中有一种针对影像纹理数据做编/解码的技术称为纹理压缩(Texture Compression)，S3纹理压缩(S3Texture Compression,S3TC)为其中一种常见的设计，主要包含下面二个步骤:(1)将影像切分成数个固定大小且不重迭的区块；及(2)对每个区块分别决定两个代表像素，并针对区块内每个像素的产生一索引值。
[0003] 美国专利US 8,594,441提出了一个决定代表像素的方法。然而该方法所决定的代表像素无法有效地代表该区块内的所有像素，导致压缩后的影像易产生色偏。
发明内容
[0004] 鉴于先前技术的不足，本发明的一目的在于提供一种影像压缩方法及装置，以提高影像压缩的品质。
[0005] 本发明公开一种基于固定长度编码的影像压缩方法，用于压缩包含复数个像素的一区块，包含：根据所述像素的像素值，从所述像素中决定一第一代表像素、一第二代表像素及一第三代表像素，其中该第一代表像素、该第二代表像素及该第三代表像素在所述像素所对应的一色彩空间中不共线；根据该第一代表像素及该第三代表像素内插产生复数个第一内插像素；根据该第二代表像素及该第三代表像素内插产生复数个第二内插像素；以及根据该第一代表像素、该第二代表像素、该第三代表像素、所述第一内插像素及所述第二内插像素，针对所述像素的每一像素产生一索引值。
[0006] 本发明另公开一种基于固定长度编码的影像压缩装置，用于压缩包含复数个像素的一区块，包含：一存储器，储存所述像素的像素值；一比较电路，耦接该存储器，系根据所述像素的像素值，从所述像素中决定一第一代表像素、一第二代表像素及一第三代表像素，其中该第一代表像素、该第二代表像素及该第三代表像素在所述像素所对应的一色彩空间中不共线；以及一计算电路，耦接该存储器及该比较电路，执行以下步骤：根据该第一代表像素及该第三代表像素内插产生复数个第一内插像素，以及根据该第二代表像素及该第三代表像素内插产生复数个第二内插像素；以及根据该第一代表像素、该第二代表像素、该第三代表像素、所述第一内插像素及所述第二内插像素，针对所述像素的每一像素产生一索引值。
[0007] 本发明另公开一种基于固定长度编码的影像压缩方法，用于压缩包含复数个像素的一区块，包含：根据所述像素的像素值，从所述像素中决定一第一代表像素及一第二代表像素；根据该第一代表像素及该第二代表像素内插产生复数个内插像素；根据该第一代表像素、该第二代表像素及所述内插像素，针对所述像素的每一像素产生一索引值；调整该第一代表像素及该第二代表像素，以产生一第一调整后代表像素及一第二调整后代表像素；以及以该第一调整后代表像素、该第二调整后代表像素的完整像素值或量化后的像素值及所述索引值代表该区块。
[0008] 本发明的影像压缩方法及装置决定更适合的代表像素，或是对代表像素进行调整，而达到更佳的影像压缩质量。相较于传统技术，本发明能够减少色偏。
附图说明
[0009] 图1为本申请的基于固定长度编码的影像压缩装置的一实施例的功能方块图；
[0010] 图2为本申请基于固定长度编码的第一影像压缩方法的流程图；
[0011] 图3为步骤S210的细节流程；
[0012] 图4为方法一的代表像素及内插像素于色彩空间中的示意图；
[0013] 图5为步骤S230的细节流程；
[0014] 图6为步骤S240的细节流程；
[0015] 图7为编码数据的结构的一范例；
[0016] 图8为本申请基于固定长度编码的第二影像压缩方法的流程图；
[0017] 图9为步骤S810的细节流程；
[0018] 图10为方法二的代表像素及内插像素于色彩空间中的示意图；以及
[0019] 图11为本申请的压缩方法的另一实施例的流程图。
具体实施方式
[0020] 以下说明内容的技术用语系参照本技术领域的习惯用语，如本说明书对部分用语有加以说明或定义，该部分用语的解释以本说明书的说明或定义为准。
[0021] 本申请的公开内容包含影像压缩方法及装置。本申请的影像压缩方法的部分或全部流程可以是软件及/或固件的形式，并且可藉由本申请的影像压缩装置或其等效装置来执行，在不影响该影像压缩方法的充分公开及可实施性的前提下，以下影像压缩方法的说明将着重于步骤内容而非硬件。
[0022] 图1为本申请的基于固定长度编码的影像压缩装置的一实施例的功能方块图。影像压缩装置100包含存储器110、比较电路120以及计算电路130。图2为本申请基于固定长度编码的第一影像压缩方法的流程图。存储器110储存一影像的像素的像素值。比较电路120从存储器110读取该影像的一区块，并且根据该区块的复数个像素的像素值，从所述像素中决定一第一代表像素及一第二代表像素(步骤S210)。具体地(如图3的细节流程所示)，比较电路120计算所述像素在色彩通道(例如RGB)的分布范围，亦即藉由比较得知该区块内的所有像素在三个通道分别的最大值及最小值(步骤S212)。对RGB色域来说即为区块内最大与最小的R值、G值及B值总共六个数值，并将相同通道的最大像素值与最小像素值相减得到三个差异量(即，Rmax-Rmin,Gmax-Gmin,Bmax-Bmin)(步骤S212)。接着，比较电路120根据所述分布范围的一最大分布范围，决定该第一代表像素及该第二代表像素。具体地，比较电路120找出差异量最大的通道，并将该通道的最大像素值及最小像素值所分别对应的两个像素当作代表像素(步骤S214)。代表像素决定后，计算电路130根据代表像素内插产生复数个内插像素(步骤S220)。图4为代表像素及内插像素在色彩空间中的示意图。三个轴分别代表像素的三个通道。两个代表像素标记为R0及R1，6个内插像素标记为I0～I5。内插像素的个数仅为示意。
[0023] 接下来计算电路130根据代表像素R0、R1及内插像素I0～I5，针对区块内的每一像素产生一索引值(步骤S230)。具体地(如图5的细节流程所示)，计算电路130先将所述像素(包含R0、R1及I0～I5，合称为编码像素)编号，例如将(R0,I0,I1,I2,I3,I4,I5,R1)编号为(0,1,2,3,4,5,6,7)(步骤S232)。压缩(或编码)的程序为区块中的每个像素决定一索引值以取代其像素值，索引值的位数与编码像素的个数有关。举例来说，8个编码像素对应的索引值为log2 8＝3位。反之，若索引值的位数已先决定(例如根据所需的压缩率决定)，便可推知所需的内插像素个数为2k-2个(k为索引值的位数)。接着，计算电路130以区块内的所有像素轮流作为目标像素(步骤S234)，并从所述编码像素中决定与该目标像素在该色彩空间中距离最短的目标编码像素(步骤S236)，再以该目标编码像素的编号作为该目标像素的索引值(步骤S238)。具体地，计算电路130计算目标像素与编码像素在该三个通道所组成的色彩空间内的距离。如图3所示，像素P0与P1为区块内其中两个像素，假设计算电路130选取P1作为目标像素，并计算其与8个编码像素的个别距离后得知目标编码像素I1与其最接近，计算电路130便可决定目标像素P1的索引值为目标编码像素I1的编号；同理，计算电路130决定像素P0的索引值为编码像素I3的编号。
[0024] 由于第一代表像素及第二代表像素系根据像素值分布范围最大的通道决定，所以实作上有可能出现以下情形：在另外两个通道上，代表像素的色彩趋势与所有像素的色彩趋势(表现在区块的低频成分)不符。此情形会导致编码产生色偏。换句话说，根据差异量最大的通道进行编码，区块内像素间的差异(表现在区块的高频成分)能被表示，但编码像素的低频成分则可能和原始区块的低频成分有落差。为了解决色偏的问题，计算电路130更调整该第一代表像素及该第二代表像素，以产生一第一调整后代表像素及一第二调整后代表像素(步骤S240)，目的在于使编码后的区块的低频成分与原始区块的低频成分一致。具体地(如图6的细节流程所示)，计算电路130先计算原始区块的像素平均值(针对三个通道分别计算)，以得到像素平均值Ravg、Gavg及Bavg(步骤S242)。之后计算电路130根据第一代表像素、第二代表像素及所述索引值建立一解码区块(步骤S244)，再计算该解码区块的像素平均值R′avg、G′avg及B′avg(步骤S246)。计算电路130再将第一代表像素的像素值及第二代表像素的像素值减去解码区块的像素平均值，再加上原始区块的像素平均值，以分别产生第一调整后代表像素及第二调整后代表像素(步骤S248)。具体地，若第一代表像素R0的像素值为(R0,G0,B0)，则第一调整后代表像素R0’的像素值为(R0-R′avg+Ravg,G0-G′avg+Gavg,B0-B′avg+Bavg)。此处计算区块的像素平均值为取得影像的低频成分的其中一实施例，其他任何能取得影像的低频成分的方法皆可适用于本发明。
[0025] 接下来，计算电路130将该第一调整后代表像素R0’与该第二调整后代表像素R1’的完整像素值或量化后的像素值，以及所述索引值存入存储器110中，所述存入的数据即为原始区块的压缩数据(或编码数据)，可用来代表该原始区块(步骤S250)。具体地，请参考图7所示的编码数据的结构，存入存储器110的数据报含索引表及代表像素。此范例中(对应方法一)，一个区块包含16个像素，每个索引值为3位，因此索引表的大小为48位。当第一调整后代表像素R0’及第二调整后代表像素R1’以完整的像素值(假设每个通道以8位(bit)表示，则一个像素的像素值为8x3＝24位)呈现时，则调整后的代表像素共包含48位。在不同的实施例中，可藉由牺牲次要的色彩细节来提高压缩率，例如将第一调整后代表像素R0’与第二调整后代表像素R1’改以21位表示(例如RGB三个通道经量化后各减去最低的1位)。如此便完成了一个区块的编码。该编码数据除了可以暂存至本地的存储器110之外，亦可通过有线或无线方式传输至另一装置(例如影像解码器)。
[0026] 图8为本发明基于固定长度编码的第二影像压缩方法的流程图。比较电路120从存储器110读取该影像的一原始区块，并且根据原始区块的复数个像素的像素值，从所述像素中决定一第一代表像素、一第二代表像素及一第三代表像素(步骤S810)。具体地(如图9的细节流程所示)，比较电路120执行步骤S812及S814(其细节与步骤S212及S214相似，不再赘述)以决定第一代表像素及第二代表像素，然后再从所述像素中决定不同于该第一代表像素及该第二代表像素的一第三代表像素(步骤S816)。具体地，如图10所示，比较电路120执行完步骤S810及S814之后得到第一代表像素R0及第二代表像素R1。接着，比较电路120比较每一像素在色彩空间中与R0及R1的连线的距离，并找到对应最长距离的像素作为第三代表像素R2。也就是说，第三代表像素R2与第一代表像素R0及第二代表像素R1在色彩空间中所形成的三角形的面积，大于其他像素与第一代表像素R0及第二代表像素R1所形成的三角形的面积。因此，该三个代表像素在色彩空间中不共线。
[0027] 从比较电路120得到该三个代表像素后，计算电路130根据第一代表像素R0及第三代表像素R2内插产生复数个第一内插像素(例如I0、I1)(步骤S820)，以及根据第二代表像素R1及第三代表像素R2内插产生复数个第二内插像素(例如I2、I3)(步骤S830)。第一内插像素的个数可以与第二内插像素的个数相同(如图10的范例)，以方便计算电路130进行内插运算。
[0028] 接下来计算电路130根据该三个代表像素(R0、R1、R2)及所述内插像素(I0～I3)，针对所述像素的每一像素产生一索引值(步骤S840)。由于步骤S840与步骤S230相似，故不再赘述。接着计算电路130以第一代表像素R0、第二代表像素R1、第三代表像素R2的完整像素值或量化后的像素值及所述索引值代表该区块(步骤S850)。请参考图7的方法二所对应的数据结构，此编码方法使用三个代表像素，因此若想要跟方法一有相同的压缩率，则必须量化三个代表像素的像素值。举例来说，三个代表像素经量化后的像素值各为16位(R、G、B分别减去最低的3位、2位及3位)。
[0029] 方法二利用片段线性(piecewise linear)的做法，以对区块内边缘以及差异大的色彩做较佳的保留，相较于方法一能保留更高的影像结构真实度。然而在相同压缩率的前提下，方法一较方法二更能呈现色彩的细节。由于各区块的特性不同，亦即方法一及方法二各有适用的情况，所以本发明更提出以软性决定的方式从两个方法中择一进行影像压缩。图11为本发明的压缩方法的另一实施例的流程图。一开始影像压缩装置100先从复数个不重迭的区块中选择一原始区块(步骤S1110)，接着分别以方法一及方法二对该原始区块进行编码(步骤S1120、S1130)，以分别得到第一编码数据及第二编码数据。接下来影像压缩装置100分别根据第一及第二编码数据计算编码后区块与原始区块的差值D1及D2(步骤S1140、S1150)。具体地，计算电路130解码第一编码数据来产生第一解码区块，并将第一解码区块与原始区块比较。例如差值D(D1或D2)可以由方程式(1)求得(但不以此为限)：
[0030]
[0031] 在方程式(1)中，l+1为原始区块的像素个数，(Ri，Gi，Bi)为原始区块的像素值，(R′i，G′i，B′i)为解码区块的像素值。之后比较电路120根据D1及D2的大小(步骤S1160)而选择对应较小差值的编码方法(步骤S1140、S1150)。因此编码后的区块可以更接近原始区块，减少影像失真。
[0032] 请注意，在图11的流程中，步骤S1130可以稍晚于步骤S1120执行，目的在于将执行步骤S816所需要的距离以步骤S236所计算出的距离来近似，以减少计算时间及电路功耗。
[0033] 对应图11的编码方法的解码流程，可以藉由判断索引值的范围得知某一区块是以方法一或方法二编码。具体地，续图4及图10的范例，对应方法一及方法二的索引值的范围分别为0～7及0～6，如此解码时便可得知编码方法以及如何解析图7的编码数据(需事先得知区块的像素个数及索引表的位数)，再根据索引值及代表像素即可进行解码程序。
[0034] 影像压缩装置100的比较电路120及计算电路130所实现的压缩(编码)算法亦可以藉由处理器(例如中央处理单元、微处理器、数字信号处理器等)执行程序代码或程序指令来完成。程序代码或程序指令可储存于存储器110中或其他储存媒介。
[0035] 由于本技术领域具有通常知识者可藉由本申请的装置发明的公开内容来了解本申请的方法发明的实施细节与变化，因此，为避免赘文，在不影响该方法发明的公开要求及可实施性的前提下，重复的说明在此予以节略。请注意，前揭图标中，组件的形状、尺寸、比例以及步骤的顺序等仅为示意，系供本技术领域具有通常知识者了解本发明的用，非用以限制本申请。
[0036] 虽然本申请的实施例如上所述，然而所述实施例并非用来限定本发明，本技术领域具有通常知识者可依据本发明的明示或隐含的内容对本发明的技术特征施以变化，凡此种种变化均可能属于本发明所寻求的专利保护范畴，换言的，本发明的专利保护范围须视本说明书的申请专利范围所界定者为准。
[0037] 【符号说明】
[0038] 100 影像压缩装置
[0039] 110 存储器
[0040] 120 比较电路
[0041] 130 计算电路
[0042] S210～S250、S810～S850、S1110～S1180 步骤。
