分区最大化色域边界描述器的空区插值算法

朱 明，赵兴运

河南工程学院，郑州450007

1 引言

在跨媒体图像复制中，需要把图像颜色从源设备色域映射到目标设备色域内。能否精确地描述图像和设备的色域边界直接影响着色域映射精度的高低[1-3]。在图像复制领域中，当前有两种应用较为广泛的色域边界描述器。第一种是基于凸壳“充放气”的色域边界描述算法[4-6]。该方法首先对颜色样本数据进行非线性变换，使得变换后的数据更接近凸集，然后进行凸壳计算，获得色域边界。凸壳算法需要将颜色样本点进行包扎，计算量较大，而且需要提前对色域形状作出假设。对于设备色域的计算来说，作出此假设非常有效。但对于图像色域来说，由于凸壳性并非图像色域的属性，因此该算法不能很好地描述非凸色域边界，可能会影响某些图像的色域边界计算精度。

针对凸壳算法存在的问题，Morovič J 和Luo M R又设计了分区最大化色域边界描述器（Segment Maxima Gamut Boundary Descriptor，SMGBD）[7-8]。该方法先根据明度轴和色调角将CIELAB 颜色空间按照球坐标进行区域等分，并将分割后的子区域内具有最大球坐标半径的颜色样本点进行存储，最后根据子区域的邻接关系把各分区的颜色样本点进行连接，以获得色域边界。SMGBD无需对色域形状作出预先假设，因此该方法对于设备和图像色域均有较好的描述效果。更重要的是，区域分割法还提供了线色域边界（Line Gamut Boundary，LGB）的计算方法，可以方便地应用于色域映射。

凭借上述优点，SMGBD 成为目前应用较为广泛的色域边界描述器。但该方法在提出时仍存在一些问题：（1）由于不同图像的颜色分布特征不同，因此在计算图像色域边界时，可能会出现许多分区缺失边界点的情况。这就需要对缺失边界点的分区进行插值，否则会严重影响图像色域边界的描述精度。（2）在空区插值后，针对相邻分区边界点连线与等色相面的重合所导致的线色域边界计算问题，也需要设计出合理的解决方案。本文在深入分析SMGBD的基础上，提出了一种基于相邻分区加权平均的空缺分区插值算法，并在此基础上研究了线色域边界的计算以及对异常问题的处理。借助色域映射的方式，本文设计了心理物理学实验来评价色域空区插值算法的效果，同时还测试了算法的计算效率。

2 基于相邻分区加权平均的色域空区插值算法

2.1 插值算法的设计原理

图1显示了SMGBD对CIELAB球体颜色空间的6×6区域分割情况，图中标识的分区即为一个边界点空缺分区。先将空缺分区的边界点位置确定在该分区的中心，在已知分区数量的情况下，可以很容易地求出该空缺分区边界点的球坐标角度α 和θ；然后再利用邻域加权平均法插值计算出该分区边界点的球坐标半径r ：即以空缺分区为中心，分别沿图2 所示的搜索路径（向上，下，顺时针，逆时针方向）查找相邻分区的边界点。可以明显看出：该插值搜索算法的基本原理是对各方向的邻域由近及远逐一搜索（若当前分区为空，则按箭头所指路径搜索下一分区，直到在这一方向上找到非空分区为止），这样才能确保最终得到的插值邻域为该方向距离中心最近的非空分区。搜索完成后，将各邻域分区边界点对应的球坐标半径r 进行加权平均，各相邻分区对应的权重值与其和中心空区的距离成反比。需要注意：插值计算完成后，需要根据插值边界点的球坐标半径r 再计算出边界点的明度值，并判断该值是否超出明度L*轴的范围[0，100]，若超出范围，则需要进行数据规范化处理。

图1 CIELAB球体颜色空间的区域分割情况（6×6分区）

图2 插值算法的搜索路径（从空缺分区向四个方向的相邻分区）

2.2 线色域边界的计算及异常问题的处理

空区插值完成后，针对色域映射的具体应用，还需要计算每个待映射颜色在等色相面内的线色域边界（LGB）。图3 显示了线色域边界的计算原理：首先在CIELAB球坐标系的水平方向上，逐行判断待映射颜色所处的等色相角平面的左右相邻分区，然后依次连接左右相邻两个分区的边界点，这些连线与等色相面的交点为线色域边界的节点（LGB Points），最后从上到下将这些节点连接起来形成线色域边界。求解LGB点的本质是求解左右两分区连线方程与等色相角平面方程所构成的线性方程组。

假定该等色相角平面在某行左右两个相邻分区的边界点为J(j1,j2,j3)和K(k1,k2,k3)，那么连接两点的直线方程可表示为式（1），其中P(p1,p2,p3)为该直线上任意一点，矢量u(k1-j1,k2-j2,k3-j3)固定不变，t 为可变参数。由于色相角已知，假定该等色相角平面过明度轴上已知两点M(m1,m2,m3),N(n1,n2,n3)和已知的待映射颜色点L(l1,l2,l3)，因此该平面方程可表示为式（2），其中Q(q1,q2,q3)为该平面上任意一点，矢量v,w 固定不变，r 和s 为可变参数。

图3 线色域边界的计算原理

为了得到相邻分区边界点连线与等色相面的交点，可将式（1）和（2）构成线性非齐次方程组（3），其中r,s,t为待求解变量。当系数矩阵与增广矩阵的秩相等，且都为3时，该方程组有唯一解，即为连线与平面的交点，此为大多数情况；但还需要注意另外两种特殊情况：（1）当系数矩阵与增广矩阵的秩相等，但小于3 时，该方程组有无穷解，此时说明该连线可能位于等色相面内；（2）当系数矩阵与增广矩阵的秩不相等，该方程组无解，此时说明该连线可能与等色相面平行，因此无交点。注意：在实际应用中，第二种情况是不会发生的。当第一种情况发生时，本文采用了一种简单而又合理的处理方式：令t=0，此时由式（1）可知，p1=j1,p2=j2,p3=j3，这意味着相邻分区连线与等色相面的交点被设定成其中一个分区的色域边界点，这样可以避免线色域边界和色域映射计算中出现的色域边界缺失问题。

2.3 方法分析

当使用SMGBD 和空区插值算法（6×6 分区）计算图4所示测试图像的色域边界时，所得的各分区色域边界点构成了色域边界描述矩阵（GBD_Matrix，GRD 矩阵），矩阵中各元素的CIELAB 值如表1 所示，表中的6行6列数据分别对应6×6的SMBGD分区。对于CIELAB值为（70.196，0，14.000）的某个图像像素来说，它处在色相角α 为90°的等色相面内。根据表中数据可知，该等色相面第1行（顶部）左右相邻分区边界点的CIELAB值分别为（100，0，0）和（99.2，-5，27），两点的色相角分别为0°和100°，因此其连线与90°等色相面的交点只有一个，即其中一个边界点本身。这时，从表2可以看出：前两个LGB点具有相同的CIELAB色度值，因此是互为重合的一个点。注意：在该案例中共有8 个LGB 点，分别对应垂直方向上6 个分区的LGB 点和明度轴的上下两个端点。

图4 原始图像及映射像素

另外，该等色相面第6行（底部）左右相邻分区边界点的CIELAB 值分别为（0，0，0）和（1.2，0，2），其对应的色相角分别是0°和90°，此时可以明显看出：这两个分区边界点连线与90°等色相面完全重合，即与上述第一种特殊情况对应。通过求解方程组（3）可知，系数矩阵与增广矩阵的秩相等，但都等于2（小于3），即有无穷解。这时利用本文的解决方案，令t 值为0，此时交点计算结果为其中一个边界点本身（CIELAB：0，0，0）。从表2可以看出：后两个LGB 点互相重合成了一个点。与计算设备色域所用的均匀采样色标不同，彩色图像的颜色分布较不规则，因此上述情况经常在计算图像色域时发生，且通常发生在LGB线色域边界的顶部或底部。

表1 原始图像对应的色域边界描述矩阵中各元素的CIELAB值（6×6分区）

表2 像素所在等色相面内的LGB点及其CIELAB值

3 算法的性能评价

3.1 评价实验的设计

准确地描述色域边界，其目的是为了在不同媒体之间准确地进行色域映射。如果对图像或设备的色域边界描述不准确，就会直接影响到色域映射精度。因此，通过色域映射手段来评价和验证色域边界描述器的性能是合理而且可行的。色域映射方法按原理可以划分为色域裁剪和色域压缩，前者是将色域外颜色裁剪到目标色域边界，而色域内颜色保持不变，因此它与图像色域边界描述并无关系，主要用于实现专色或图表颜色的精确复制；后者是根据源色域和目标色域的关系，将色域外颜色朝映射中心的方向等比例映射到目标色域内。为了更好地保持映射图像的阶调层次，色域内颜色也可能需要映射，因此该方法主要用于彩色图像复制。本文研究的SMGBD 空区插值算法主要针对图像色域边界的不规则性而提出，因此适宜选用色域压缩的方式来评价色域边界描述器的性能。

本文设计了基于图像成对比较的心理物理学实验来评价色域压缩算法的性能，实验在观察条件和实验方法等方面遵循了CIE TC 8-03 色域映射算法评价指导标准[9]。评价实验包括准确性测试和偏好性测试。前者将每种测试算法得到的图像分别与原始图像两两显示在显示屏上，观察者经过评判从中选出一幅最接近原始图像的图像；而后者分别将每种算法得到的图像两两显示在显示屏上，观察者经过评判从每对图像中选出一幅图像质量（颜色保真度、清晰度、彩度、局部细节等）最佳的图像。评价用测试图像从图像数据库TID2008[10]和CSIQ[11]中选取，如图5 所示，这12 幅测试图像涉及不同的颜色和阶调特征。不同于简单的色域裁剪，色域压缩既要考虑目标色域范围又要考虑源色域，因此为增强评价说服力，实验采用的源色域和目标色域不是完全的包含和被包含关系，而是在不同的区域范围有各自独立的部分。源色域和目标色域分别从Samsung C27F591FD显示器和HP z3200 喷墨打印机的ICC 特性文件中提取[12]，使用Gretag Macbeth 的Profile Editor 软件显示的源色域和目标色域如图6 所示，实验采用10×10 分区的SMGBD。实验所用的5 种色域映射测试算法[12-15]的详细信息如表3。

图5 测试图像的缩略图

图6 Samsung C27F591FD显示器色域和HP z3200打印机色域范围的比较

3.2 评价结果及分析

图7 显示的是根据准确性和偏好性评价实验结果计算的每种测试算法的Z分数[15]，以及使用瑟斯顿配对定律制作的95%置信区间的等距量表。实验观察者由10 名图像处理相关专业人员和10 名非专业人员组成。从图中可以看出：偏好性Z分数与准确性Z分数的分布较为相似。在所有测试算法中，不进行色域空区插值的色域映射算法C1和S1表现较差，带有空区插值的算法C2 和S2 表现较好，其中，算法S2 的性能甚至好于商业软件中的对应算法S3。

表3 评价实验所用的5种色域映射测试算法的详细信息

图7 5种测试算法的偏好性Z分数和准确性Z分数

图8显示了无空区插值的映射算法C1对测试图像I19 的映射效果，可以观察到图像中红色方框内的区域在映射后出现了明显的失真，如图8（a）和（b）。通过分析发现：对于该区域内位置邻近且颜色值非常接近的两点Color1和Color2，其等色相面内的目标色域边界外形非常相似，且比较规则；而图像色域边界相差很大，且很不规则。根据CUSP 色域压缩原理，在图8（c）中，在映射线OD 方向上的线段OD 大于OR（D 和R 分别是映射线与目标色域边界和源色域边界的交点），因此Color1无需映射。而在图8（d）中，线段OD 却小于OR，虽然Color2仍在目标色域内，但会按照压缩比例映射到P 点，这就造成图像色域内两个颜色接近的点，因为色域边界的描述误差在映射后变成了两个色差较大的像素点，从而造成了图像失真。通过实验发现：基于空区插值的图像色域边界描述更加精确，形状更加规则，类似问题可以得到明显改善，这也是测试算法C2 的性能明显高于C1的原因。

图8 映射算法C1对图像I19的效果分析

图9 映射算法C2对图像I23的效果分析

通过对图9案例的分析可以发现算法C2也存在着问题，图9（a）中红色方框区域的鹦鹉羽毛部位发生了明显的映射失真，如图9（b）。以该区域中位置邻近且颜色值相似的两个像素点Color1和Color2为例，在图9（c）和（d）中，颜色点Color1位于目标色域边界外，需要朝着映射中心O1 映射到目标色域内的P 点，导致映射后的彩度大幅度降低；Color2 位于目标色域内而不发生映射，彩度保持不变。这就造成了黄色羽毛部位在映射后出现了两种颜色分界的失真。由于SGCK 算法并不对所有色域内颜色进行映射，而是只针对目标色域的固定比例范围（默认比例范围是90%）进行压缩，因此不仅可以避免该问题，还能有效地保持部分图像细节。从图7还可以看出：算法S2 的性能明显好于S3（ICC 3D 软件中的SGCK），因为实验中发现ICC 3D软件中的SGCK算法对某些测试图像会产生一些失真，如图10，图中的红色区域即为映射后出现的失真区域，这也在某种程度上验证了空区插值算法对SMGBD改进的有效性。

图10 测试图像I23和sunsetcolor的映射失真

3.3 色域边界描述器计算效率

通过测试发现：无论是否进行空区插值，SMGBD对所有测试图像的色域边界计算效率都很高，且改进前后的计算时间不变（都在1 s 以内），这说明空区插值算法并不影响色域边界的计算效率。本文还将具有相同色相角的颜色分别收集在一起进行映射，避免了同色相颜色的线色域边界的重复计算，通过实验发现此举能够大幅提升色域映射速度。本文使用色域映射算子HPMinDE[16-17]对部分测试图像进行映射，计算时间如表4所示。可以看出：通过对图像中相同色相角的像素进行同批映射可以大幅提高映射效率。本文算法效率的测试环境为MATLAB平台（DELL OptiPlex，Inter®CoreTMi7-4770M CPU@3.40 GHz），源色域和目标色域的选择与3.1节相同。

表4 不同图像的色域映射时间 s

4 结论

本文研究了SMGBD 色域边界描述器的空区插值和线色域边界的计算方法，提出了基于相邻分区加权平均的色域空区插值算法，从而可以更加准确地计算出各分区的色域边界点。针对相邻分区边界点连线与等色相面重合所导致的色域边界计算和色域映射问题，本文给出了合理的解决方案，并通过案例分析验证了方案的可行性；在评价部分，本文借助色域映射的方式，利用心理物理学实验评价了空区插值算法的效果，同时还测试了算法的计算效率。评价结果显示：本文提出的色域空区插值算法能够有效提升色域边界描述器的精度，改善色域映射效果，而且并不影响色域边界的计算效率。