非规则颜色的快速匹配“查表法”算法的研究与实现

严 惠

(江苏信息职业技术学院，无锡，214153)

0 引言

现实生活中绝大多数显示设备所能显示颜色都不一致，原因是总存在一些颜色会偏离这些规则象素值，其所显示颜色为非规则颜色。因此该颜色无法根据其索引值来计算其对应的RGB值，反之也无法根据RGB值获得索引值。而随着多媒体技术的发展和全球互连网络的兴起, 图像通信包括图像传输与图像显示日益重要。因此必须提高图像处理技术，尤其是彩色图像处理技术。由于人眼对高频细节敏感性较低，其相当于一个低通滤波器，本文针对非规则颜色存在，利用人眼视觉误差，提出一种查表法算法，在不影响图像质量前提下，提高了颜色匹配的速度。

1 颜色模型选择

彩色图像不仅要考虑图像的亮度信息，还要兼顾色彩对人眼的刺激。抖动方法的理论依据为通过欺骗人眼视觉来模仿出源目标颜色，从而获取近似于源区域的视觉图像。然而如何进行颜色误差扩散以及扩散的量值选取需要建立一种颜色模型去量化扩散的度。常见的颜色模型主要有RGB模型，CYMK模型，YUV模型，其他的颜色模型为这些颜色模型的变体或者衍变。

RGB颜色模型几乎包括了人类视力所能感知的所有颜色，是目前运用最广的颜色系统之一。CMYK颜色模型是通过对青(C)、洋红(M)、黄(Y)、黑(K)四个颜色变化以及它们相互之间的叠加来得到各种颜色，虽然CMYK颜色值可以完全转换为RGB值，但RGB到CMYK并不能一一对应，存在的问题是黑色部分的替换值取值问题。由于目前主流电子显示设备为”加色”显示设备，并且两者之间的转换也比较复杂，处理起来必然费时。由此，CMYK不适合彩色图像的抖动处理。YUV主要用于优化彩色视频信号的传输，处理彩色图像时，会出现 “差不多”亮度的颜色有若干个，但这若干个颜色的色系不同，有可能匹配出这若干个颜色中的一个，这样人眼就能容易地分辨出两者的不同，从而影响抖动的效果，而且在运算的过程中不得不进行浮点数运算，速度也降低了。HSV(HSI)模型较YUV模型差异较大，通过实验测试:目标图像效果也没有明显的提升，且速度慢。

2 颜色的快速匹配：查表法

2.1 传统算法与弊端

由于源颜色为非规则颜色，因此需要进行颜色的匹配，即寻找与其相近的点。为了匹配最最相近点，传统的算法是：遍历目标颜色表，计算源颜色与所有目标颜色的距离，从中找到距离最小的目标颜色。因此，在目标颜色的查询过程中就需要对所有点进行核准，从而会产生效率低下的问题。

2.2 查表法

查表法的思想是首先建立一张距离相等的表，表格内记录目标设备在这表格范围内颜色的集合，表格内可以有目标颜色点可以没有目标颜色点，可以有一个颜色点，也可以有多个颜色点。在匹配颜色时，首先计算源颜色对应的表格坐标,计算该表格内所有目标点的距离，挑出最近点，该点就是匹配到的点。如果该表格内没有目标颜色点该如何处理，这时将扩大搜索表格的数量，即再到包围当前格子的表格内查找，如果这些表格内仍没有目标颜色点则再扩大搜索表格，即再到包围当前表格的表格内查找。

如图1所示：

在二维空间中，第一次搜索一个格子即图1.1中S所在的黑色格子内的目标颜色点；如果没有第二次到图1.2中8个阴影格内搜索；若再没有到图1.3所示的16格内搜索，依次类推，直到找到为止，每次查询格子个数可采用下述公式计算。

N=（2T-1）2 -（2T-3）2

其中N为每次查询的格子个数，T为查询的次序（T=1，2，3…….）

由以上介绍可知，该方法先到最有可能出现的表内搜索目标点。从而搜索到目标点的几率就比较大。当查询到目标点所在表格时，如果目标表格中有多个点满足条件，则取距离最小的点。

图1 二维空间颜色匹配

采用同样的方法扩展到三维空间，RGB三个分量可以将其理解为三维空间的三个量，如图所示，黑色方框为源颜色所在方框区域，首先在第一个域即黑色方框所在域搜索，如果没有查询到符合条件的点；第二次再拓展到黑色立方块周围的26个格子寻找；若仍然未找到，第三次再拓展到周围的16个立方块里查询。依次类推直到查询到目标点为止。每次查询立方块的个数算法如下：

其中N为每次查询的格子个数，T为查询的次序（T=1，2，3…….）

与已有算法相比，查表法无须遍历所有颜色点，在性能上得到明显改善。当获取到目标点时，利用基于距离倒数的误差扩散发进行颜色的匹配。

图2 三维空间颜色匹配

3 软件设计

3.1 建查找表，加载颜色表

3.2 误差分配

3.2.1 区分奇偶行

误差传播有时会引起流水效应，即误差不断向下，向右累加传播。为了解决流水效应带来的影响，一般采用奇数行从左到右传播，偶数行从右到左传播。

3.2.2 计算误差

3.2.3 分配误差

传统的误差分配方法一般采用距离作为基准，本程序采用距离倒数作为基准，距离越近，分配误差比例越多。

4 验证

本文所提出的查表法通过触摸屏实验验证得知：采用查表法图像处理速度提高了一个数量级以上，同时也不影响人对图片的视觉质量。

[1]孙薇,张艳霞,何永保.基于空间- 色度多维向量模糊量化的彩色图像压缩[J].中国图像图形学报,1999.4(2):124-127.

[2]王文惠,楼生强,万建伟等.一种彩色图像的非线性自适应滤波算法[J].计算机工程与科,2001,23(4):18-20.

[3]叶玉芬，郭宝龙，马 佳。基于视觉差的误差扩散半色调算法[J].计算机工程, 2006.32(16):195-197.

[4]王品清，陈显尧.CYMK变换及其在图像处理与地学研究中的应用 [J].地质通报,2006,25（1-2）:308-313.

[5]童正宁,吴旭凡,高谷刚等.兼容YUV数据格式的LCD控制器[J].现代电子技术,2006,221(6):37-39(转42).

[6]丁鹭飞,耿富录.雷达原理[M].西安:西安电子科技大学出版社,2000.