HK1258161B - 用於渲染彩色图像的方法 - Google Patents

Description

用于渲染彩色图像的方法

相关申请

本申请涉及美国公开No.2014/0340430；美国公开No.2016/0091770；以及美国专利No.9,383,623和9,170,468。其他相关申请和专利将在下面讨论。

技术领域

本发明涉及一种用于渲染彩色图像的方法。更具体地，本发明涉及一种用于在一组有限的原色可用的情况下对彩色图像进行半色调(half toning)的方法，并且该有限的组可能没有被很好地构造。本发明的方法特别地但不排他地用于彩色电泳显示器。

背景技术

半色调已经在印刷工业中使用了数十年，以通过用黑色墨水覆盖白纸的每个像素的不同比例来表示灰色调。类似的半色调方案可以与CMY或CMYK彩色印刷系统一起使用，颜色通道彼此独立地变化。

然而，存在许多颜色系统，其中颜色通道不能彼此独立地变化，因为每个像素可以显示一组有限的原色中的任何一种(这种系统在下文中可以称为“有限调色板显示器”或“LPD”)；ECD专利彩色显示器属于这种类型。为了产生其他颜色，原色必须在空间上抖动以产生正确的色感。已知通过对任何期望颜色仅使用包含期望颜色的四面体的顶点处的原色来实现这种空间抖动；参见例如：

Arad,N.,Shaked,D.,Baharav,Z.,&Lin,Q.(1999).Barycentric Screening以及

Ostromoukhov,Victor,和Roger D.Hersch."Multi-color and artisticdithering."Proceedings of the 26th annual conference on Computer graphics andinteractive techniques.ACM Press/Addison-Wesley Publishing Co.,1999。

这两个文献都通过基于阈值阵列的筛选方法实现抖动，这是一种简单的抖动方法，已经发现它不能在ECD专利显示器中给出好的结果。

标准的抖动算法，诸如误差扩散算法(其中通过以与该像素理论上所需的颜色不同的特定颜色印刷一个像素而引入的“误差”在相邻像素之间分布，从而产生总体上正确的色感)可以用于有限调色板显示器。然而，在原色之间的适当颜色空间中的距离基本恒定的意义上，这种标准算法通常旨在与“良好构造”的有限调色板一起使用。关于设计在误差扩散方面表现良好的最佳调色板的问题有相当多的文献；参见例如：

Kolpatzik,Bernd W.,和Charles A.Bouman."Optimized Universal ColorPalette Design for Error Diffusion."Journal of Electronic Imaging 4.2(1995):131-143。

然而，在ECD和类似的有限调色板显示器中，其中有限调色板由能够由系统生成的颜色定义，有限调色板可能没有被很好地构造，即，颜色空间中的各种原色之间的距离可能相互之间差别很大。

附图的图1是现有技术的基于调色板的误差扩散方法的示意性流程图，总体标记为100。在输入102处，将颜色值x_i,j馈送到处理器104，在处理器104中将它们添加到误差滤波器106(下面描述)的输出以产生修改的输入u_i,j。修改的输入u_i,j被馈送到量化器108，量化器108还接收输出装置的调色板{P_k}的细节。量化器108确定正在考虑的像素的适当颜色，由下式给出：

并将适当的颜色馈送给装置控制器(或存储颜色值以便稍后传输到装置控制器)。修改的输入u_i,j和输出y_i,j都被馈送到处理器110，处理器110计算误差值e_i,j，其中：

ei_,j＝ui_,j-yi_,j

然后将误差值e_i,j馈送到误差滤波器106，误差滤波器106用于在一个或多个所选像素上分布误差值。例如，如果在图像中从上到下并在每行中从左到右对像素执行误差扩散，则误差滤波器106可以将误差分布在正在处理的行中的下一个像素上，以及在向下的下一行中处理的像素的三个最近邻居。可替换地，误差滤波器106可以将误差分布在正被处理的行中的接下来的两个像素上，以及在向下的接下来的两行中处理的像素的最近邻居。应当理解，误差滤波器不需要将相同比例的误差应用于分布误差的每个像素；例如，当误差滤波器106将误差分布在正在处理的行中的下一个像素上，以及在向下的下一行中处理的像素的三个最近邻居时，可能适当的是，将更多的误差分配给正在处理的行中的下一像素和紧挨在正在处理的像素下面的像素，以及将更少的误差分配给正在处理的像素的两个对角邻居。

不幸的是，已经发现，如果试图对ECD和类似的有限调色板显示器使用诸如图1中所示的传统误差扩散方法，则会产生严重的伪影，这可能使得到的图像不可用。例如，在一种类型的伪影(以下称为“瞬态”伪影)中，当从一种输入颜色步进到下一种非常不同的颜色时，空间瞬态可能会很长，以至于输出即使在整个要渲染的对象的大小上也永远不会达到正确的平均值。在另一种类型的伪影(下文称为“模式跳跃”伪影)中，对于恒定颜色输入图像，输出在图像中看似随机的位置处在两组不同的原色之间跳跃。尽管两组原色应该理想地产生接近所请求颜色的输出，但是所得到的输出不稳健，因为系统中的微小变化可能导致这两组之间的这种切换，并且在这种跳跃时的纹理变化也是明显且令人不愉快的。

发明内容

本发明试图提供一种渲染彩色图像的方法，其可以与没有被良好构造并且可能很大的调色板一起使用，而不会产生标准误差扩散方法易受其影响的瞬态和模式跳跃伪影。

在一个方面，本发明提供一种在显示器上渲染图像的方法，该方法包括：

接收表示要渲染的像素的颜色的输入数据；

将输入数据与从先前渲染的至少一个像素生成的误差数据组合以形成修改的输入数据；

在颜色空间中确定包围修改的输入数据的单纯形，以及与该单纯形相关联的显示器原色；

将修改的图像数据转换为基于该单纯形的重心坐标，并将输出数据设置为具有最大重心坐标的原色；

计算修改的输入数据和像素的输出数据之间的差值，从而生成像素的误差数据；

将由此生成的误差数据应用于至少一个稍后渲染的像素；以及

将多个像素的输出数据提供给显示器，从而在显示器上渲染图像。

在该过程的一种形式中，测试所述修改的输入数据，以确定它是否在所述显示器的色域之内，并且如果所述修改的输入数据在该色域之外，修改的输入数据通过被投影到色域上来被进一步修改。可以沿着恒定亮度和色调的线朝向颜色空间的中性轴来实现该投影。可替换地，所述投影可以朝向由所述像素的输入数据表示的颜色实现，直到达到所述色域边界。典型地，所使用的颜色空间将是三维的，以使得所述单纯形将是四面体。所述误差数据可以并且典型地将分布在多于一个像素上。例如，如果使用从上到下和从左到右的像素处理顺序实现本发明的方法，则误差数据通常将分布在至少正在渲染的像素的右侧的像素和下面的像素上。可替换地，误差数据可以分布在正在渲染的像素的右侧的像素以及正在渲染的像素下面的且与该正在渲染的像素相邻的三个像素上。特别地，在后一种情况下，不必将相等比例的误差数据分布在它所分散的所有像素上；例如，当误差分布在右侧的像素和下一行中的三个相邻像素上时，将更多的误差数据分配给与正在渲染的像素共享边缘的两个像素(与仅共享顶点的两个像素相比)可能是有利的。

本发明扩展至一种设备，包括：显示装置，其具有多个像素，每个像素被布置成显示多种原色中的任何一种；以及计算装置，其能够执行本发明的方法并将其输出数据供给到显示装置，从而使显示装置显示图像。

本发明还扩展到一种非暂时性计算机存储介质，其包括当由处理器执行时使所述处理器执行本发明的方法的指令。

附图说明

如已经指出的，附图的图1是用于渲染彩色图像的现有技术方法的流程图。

图2是示出本发明的方法的类似流程图。

具体实施方式

本发明基于以下认识：上面讨论的瞬态和模式跳跃伪影是由于量化器(图1中的108)具有可用的欠约束原色列表的事实。在三维颜色空间中，可以通过仅抖动四个原色来渲染装置色域中的任何颜色，并且本发明基于以适当的方式约束原色的选择以确保在量化期间仅使用受限制的一组原色。

可以在抖动模式中使用以表示给定颜色的原色的子集不是唯一的；例如，在三维颜色空间中，可以在抖动模式中使用限定在颜色空间中包围给定颜色的体积的任何一组四个或更多个原色。即使将原色的子集限制为仅四个，也可以使用定义包围给定颜色的四面体的任何一组四个原色。然而，为了避免模式跳跃伪影，应该以这样的方式将原色的子集分配给特定颜色，以使得通过颜色空间的任何参数路径导致相对于参数使用的各种原色的比例的平滑变化。这可以通过将系统的总色域(所有原色的凸包)分解成具有原色作为顶点的四面体并且然后向要渲染的每个颜色分配与其包围四面体的顶点对应的原色的子集来实现。这可以通过Delaunay三角化来实现，其将原色的凸包分解成一组四面体，其外接球不包围来自另一个四面体的任何顶点。这很方便，但色域的其他分解也可能是有益的；例如，为了减少半色调颗粒度，可以选择原色的子集以具有低的亮度变化。应当理解，可以通过针对所涉及的维度数量使用合适的单纯形来代替使用三维空间中的四面体来将分解方法推广到任何数量的维度的颜色空间。

本发明的过程的优选实施例在附图的图2中示出，图2是与图1大致相似的示意流程图。与图1所示的现有技术的方法中一样，图2所示的方法开始于输入102，其中颜色值x_i,j被馈送到处理器104，其中它们被添加到误差滤波器106的输出以产生修改的输入u_i,j。(同样，该描述假定输入值x_i,j使得修改的输入u_i,j在装置的色域内。如果不是这种情况，则输入或修改的输入的一些初步修改可能是必须的以确保它们位于适当的色域内。)然而，修改的输入u_i,j被馈送到色域投影器206。

提供色域投影器206以处理以下可能性：即使输入值x_i,j在系统的色域内，修改的输入u_i,j也可能不在系统的色域内，即由误差滤波器106引入的误差校正可能将修改的输入u_i,j置于系统的色域之外。在这种情况下，不可能为修改的输入u_i,j选择原色的子集，因为它将位于所有定义的四面体之外。尽管可以设想该问题的其他方式，但是已经发现给出稳定结果的唯一方法是在进一步处理之前将修改值u_i,j投影到系统的色域上。这种投影可以通过多种方式完成；例如，可以沿着恒定的亮度和色调朝向中性轴进行投影。然而，优选的投影方法是朝向输入颜色投影，直到到达色域边界。

将投影的输入u’_i,j值馈送到单纯形查找器，其将适当的原色的子集{P_ks}返回到处理器210，处理器210还接收投影的输入u’_i,j值，并且将它们转换为由原色的子集{P_ks}定义的四面体(或其他单纯形)的重心坐标。虽然看起来原色的子集{P_ks}应该基于分配给输入像素颜色x_i,j的那些，但这不起作用；原色的子集必须基于投影的输入u’_i,j值。处理器210的输出λ被提供给量化器212，量化器212的功能与图1所示的量化器108的功能非常不同。量化器212选择与最大重心坐标相关联的原色，而不是执行传统的误差扩散。这相当于利用阈值(1/3,1/3,1/3)的重心阈值化(参见上述Arad等人的文献)，其不相当于图1中的量化器108执行的最小距离确定。然后，来自量化器212的输出y_i,j以通常方式发送到装置控制器，或者被存储。

输出y_i,j值以及修改的输入值u_i,j或投影的输入值u’_i,j(如图2中的虚线所示)被提供给处理器214，处理器214通过以下计算误差值e_i,j：

e_i,j＝u’_i,j-y_i,j或

e_i,j＝u_i,j-y_i,j

(取决于正在使用哪组输入值)并以与上面参考图1所述相同的方式将该误差信号传递到误差滤波器106。

理论上，似乎应该使用原始修改的输入值u_i,j而不是投影的输入值u’_i,j计算误差值e_i,j，因为前者准确地表示了像素的期望颜色和实际颜色之间的差异；实际上，使用后者的值“抛弃了”投影步骤引入的误差。根据经验，已经发现使用哪组输入值对颜色表示的准确性没有重大影响。此外，在决定在误差计算中使用在投影之前还是之后的输入值时，必须考虑由色域投影器206实现的投影的类型。某些类型的投影，例如沿着恒定色调和亮度的线的投影，提供量化器域边界到色域外体积的连续和固定的扩展，因此允许在误差计算中使用未投影的输入值而没有输出值不稳定的风险。其他类型的投影不提供量化器域边界的连续和固定的扩展；例如，向输入颜色投影直到达到色域边界未能提供量化器域边界的固定扩展，而是量化器域随输入值而变化，并且在这些情况下，应使用投影的输入值来确定误差值，因为使用未投影的值可能会导致不稳定的方法，其中误差值可以无限制地增大。

从上述内容可以看出，本发明可以在有限调色板显示器中提供改进的颜色，其具有比使用传统误差扩散技术获得的伪影更少的伪影。本发明可以用于能够显示连续颜色(或至少非常多的颜色)的显示系统，但是其中可用的原色不是均匀地遍布整个色域；例如，控制间隙宽度的基于干涉的显示器可以在每个像素处显示大量的颜色，但是在原色中具有预定的结构，其位于一维流形(one-dimensional manifold)上。本发明还可以与电致变色显示器一起使用。

对于可应用本发明的彩色显示系统的进一步细节，读者可参考上述ECD专利(其还详细讨论电泳显示器)以及以下专利和出版物：

美国专利No.6,017,584；6,545,797；6,664,944；6,788,452；6,864,875；6,914,714；6,972,893；7,038,656；7,038,670；7,046,228；7,052,571；7,075,502；7,167,155；7,385,751；7,492,505；7,667,684；7,684,108；7,791,789；7,800,813；7,821,702；7,839,564；7,910,175；7,952,790；7,956,841；7,982,941；8,040,594；8,054,526；8,098,418；8,159,636；8,213,076；8,363,299；8,422,116；8,441,714；8,441,716；8,466,852；8,503,063；8,576,470；8,576,475；8,593,721；8,605,354；8,649,084；8,670,174；8,704,756；8,717,664；8,786,935；8,797,634；8,810,899；8,830,559；8,873,129；8,902,153；8,902,491；8,917,439；8,964,282；9,013,783；9,116,412；9,146,439；9,164,207；9,170,467；9,170,468；9,182,646；9,195,111；9,199,441；9,268,191；9,285,649；9,293,511；9,341,916；9,360,733；9,361,836；9,383,623；和9,423,666；以及美国专利申请公开No.2008/0043318；2008/0048970；2009/0225398；2010/0156780；2011/0043543；2012/0326957；2013/0242378；2013/0278995；2014/0055840；2014/0078576；2014/0340430；2014/0340736；2014/0362213；2015/0103394；2015/0118390；2015/0124345；2015/0198858；2015/0234250；2015/0268531；2015/0301246；2016/0011484；2016/0026062；2016/0048054；2016/0116816；2016/0116818；和2016/0140909。

Claims (13)

1.一种在显示器的多个像素上渲染图像的方法，其中所述多个像素中的每个像素能够显示一组原色中的任何一种，所述方法包括：

接收表示要渲染的所述多个像素的颜色的输入数据(102)；

按顺序对于所述多个像素中的每个像素：

将所述输入数据与从先前渲染的至少一个像素生成的误差数据(e_i,j)组合(104)以形成修改的输入数据(u_i,j)；

在颜色空间中确定(208)包围所述修改的输入数据(u_i,j)的单纯形和与所述单纯形相关联的显示器原色{P_ks}；

将所述修改的输入数据(u_i,j)转换(210)为基于所述单纯形的重心坐标，并将所述像素的输出数据(y_i,j)设置(212)为具有最大重心坐标的原色；以及

计算(214)所述修改的输入数据(u_i,j)与所述像素的输出数据(y_i,j)之间的差值，从而生成所述像素的误差数据(e_i,j)；

将由此生成的误差数据(e_i,j)应用(106)到至少一个稍后渲染的像素；以及

将所述多个像素的输出数据(y_i,j)提供给所述显示器，从而在所述显示器的所述多个像素上渲染所述图像。

2.根据权利要求1所述的方法，还包括测试(206)所述修改的输入数据(u_i,j)，以确定它是否在所述显示器的色域之内，并且如果所述修改的输入数据在所述色域之外，则通过将所述修改的输入数据投影到所述色域上来进一步修改所述修改的输入数据。

3.根据权利要求2所述的方法，其中，沿着恒定亮度和色调的线朝向所述颜色空间的中性轴实现所述修改的输入数据的所述投影。

4.根据权利要求2所述的方法，其中，朝向由所述像素的输入数据表示的颜色实现所述修改的输入数据的所述投影，直到达到色域边界。

5.根据权利要求2所述的方法，其中，所述投影的输入数据(u’_i,j)用于至重心坐标的转换(210)和用于所述误差数据的生成(214)。

6.根据权利要求2所述的方法，其中，所述投影的输入数据(u’_i,j)用于至重心坐标的转换(210)，但是所述投影之前的修改的图像数据(u_i,j)用于所述误差数据的生成(214)。

7.根据权利要求1所述的方法，其中，所述颜色空间是三维的，以使得所述单纯形是四面体。

8.根据权利要求1所述的方法，其中，所述误差数据(e_i,j)分布在多于一个像素上。

9.根据权利要求1所述的方法，其中，所述误差数据(e_i,j)分布在至少四个像素上。

10.根据权利要求9所述的方法，其中，应用于不同像素的所述误差数据的比例是变化的。

11.根据权利要求1所述的方法，其中，所述显示器是电泳显示器。

12.一种设备，包括：显示器，其具有多个像素，每个像素被布置成显示多种原色中的任何一种；以及计算装置，其能够执行根据权利要求1至11中任一项所述的方法并将其所述多个像素的输出数据供给到所述显示器，从而使所述显示器显示图像。

13.一种非暂时性计算机存储介质，包括当由处理器执行时使所述处理器执行根据权利要求1至11中任一项所述的方法的程序。