朱明¹, 焦会敏², 赵兴运¹
1. 河南工程学院 材料与化学工程学院, 河南 郑州 450007;
2. 齐鲁工业大学 轻工科学与工程学院, 山东 济南 250353
2020-06-28 收稿, 2020-08-28 录用
基金项目: 河南工程学院2020年度科研培育基金（PYXM202010）、国家新闻出版署"柔版印刷绿色制版与标准化"重点实验室资助项目（ZBKT202005）和2019年河南省高等学校大学生创新训练项目（S201911517005）
^*通讯作者: 朱明

摘要: 为了解决影视制作、动漫设计、医学成像、空间探索等领域中的灰度图像彩色化问题，本文提出了一种基于邻域优先搜索和纹理匹配的图像颜色转移算法。对于目标灰度图像中的待着色像素，该方法首先基于邻域优先搜索方案找到其候选匹配像素，然后定义纹理特征向量的概念来描述彩色像素和灰度像素之间的纹理相似度，并根据候选像素与目标像素之间的向量空间距离计算匹配误差，以确定最终匹配像素。针对初次匹配后不同图像内容因匹配误差接近而造成的匹配错误和色彩误传问题，本文在彩色图像和灰度图像中选择相对应的区域进行样窗匹配。在5个图像彩色化测试案例中，本文算法的效果均明显好于Welsh算法。本文算法在总体上具有一个合理的色彩转移效果。此外，针对色彩构成或语义内容较为复杂的图像，通过一个案例验证了样窗匹配的有效性，分析了其中的问题和不足。
关键词: 颜色转移邻域优先搜索纹理匹配
A Color Transfer Method based on Neighborhood-first Searching and Texture Similarity Matching
ZHU Ming¹, JIAO Huimin², ZHAO Xingyun¹
1. College of Materials and Chemical Engineering, Henan University of Engineering, Zhengzhou 450007, Henan, P. R. China;
2. School of Light Industry Science and Engineering, Qilu University of Technology, Jinan 250353, Shandong, P. R. China
^*Corresponding author: ZHU Ming
Abstract: To address the problem of grayscale image colorization in the fields of film and television, medical imaging, animation, space exploration and so on, a color transferring algorithm based on neighborhood-first search and texture similarity matching is proposed. For a pixel to be colorized in target grayscale image, the method first finds its candidate matching pixels based on the neighborhood-first searching scheme. Then, we define the concept of the texture eigenvector to describe the texture similarity between two pixels, and determine the final matching pixel by calculating the matching error based on the distance between the eigenvectors of the candidate pixels and the target pixel. To address the problem of image distortion occurred after global matching, the present method conducts one or more swatch matching procedures for the distortion regions of the colorized image. In the five test cases of image colorization, the proposed algorithm has a reasonable color transfer effect. Moreover, for the image with complex color composition or semantic content, this paper verifies the effectiveness of swatch matching through a case, and analyzes the problems and shortcomings of swatch matching.
Key words: color transferringneighborhood-first searchtexture similarity matching
1 引言颜色转移又称图像彩色化，其原理是将一幅彩色图像的颜色特征传递给一幅灰度图像，从而使灰度图像具有与该彩色图像相似的色彩特征。彩色图像以其蕴含的丰富颜色信息比灰度图像更具视觉意义。因此，随着数字技术的快速发展，颜色转移技术逐渐在影视处理、医学成像、动漫制作、空间探索、图像翻新等诸多领域得到了广泛应用^[1]。Welsh等^[2]在早期提出了较为经典的灰度图像彩色化方法，该方法基于像素的明度值和邻域方差值来计算彩色像素和灰度像素的匹配误差，作为控制颜色转移的判断依据。通过图像随机采样来降低像素搜索时间，并允许用户采用样窗匹配的方式来避免由彩色像素和灰度像素的明度值重合所导致的颜色误传。
Welsh算法的很多设计思路被之后的研究所借鉴，例如，李建明等^{[3, 4]}提出了邻域优先搜索的颜色转移算法，以缩小搜索范围，提升算法效率。随后，出现了基于图像纹理特征匹配的颜色转移算法^[5-9]和基于直方图回归的算法^[10]，均取得了一定的效果。近年来，基于深度学习的图像色彩转移算法成为一个研究热点，这类算法利用图像语义层级上的紧密对应实现精确的颜色传递^{[11, 12]}。它们往往需要在大量彩色图像中进行深度学习，利用深度神经网络训练出模型^{[13, 14]}，然后根据模型来着色其它灰度图像，因而没有传统方法的局限性和人为因素影响。本文借鉴邻域优先搜索算法的设计思路，提出了一种基于邻域优先搜索和纹理相似度匹配的颜色转移方法。
2 算法原理2.1 算法框架本文算法的整体框架如图 1所示，步骤如下：
图 1

图 1 算法流程图

(1) 颜色空间转换：首先将彩色参考图像和目标灰度图像从RGB颜色空间转换至CIELAB颜色空间，在CIELAB颜色空间内，明度与色度通道各自独立，因此便于进行颜色迁移。
(2) 明度重映射：本文算法需要比较目标灰度像素与彩色像素之间的明度值，作为像素匹配的依据，考虑到两者之间的整体明度差异，在比较之前必须对彩色参考图像进行明度(L通道)映射，使两者的明度直方图相匹配，映射方法如式(1)所示。其中，L_c为映射后的彩色像素明度值，L_{c_max}, L_{c_min}, L_{g_max}, L_{g_min}分别为彩色参考图像和目标灰度图像的明度最大值和最小值。

(1)

(3) 建立备选样本集：目的有两个，第一，如果待匹配像素位于灰度图像的第一行，第一列或最后一列，那么以其为中心寻找邻域像素时，会发生像素越界的问题，这时需要在备选样本集中寻找匹配像素；第二，当邻域优先匹配的匹配误差不满足条件时，也只能在备选样本集中寻找匹配像素。在备选采样时，如果对彩色参考图像中的所有像素逐一搜索，可能需要花费较长的计算时间。本文对彩色图像进行了规则的数据采样，即按像素扫描行顺序以10~20个像素为采样间隔，可使特殊位置的像素匹配效率提高10~20倍。
(4) 像素匹配：像素匹配过程如图 2所示，在逐行逐点扫描目标灰度图像时，如果待匹配像素位于灰度图像的第一行，第一列或最后一列，那么进行备选采样。其它位置的像素进入邻域优先匹配环节，计算匹配误差，如果误差不满足匹配条件，那么还要进行备选采样匹配。如果满足匹配条件，则进行邻域优先搜索和匹配。本文使用的邻域优先搜索算法参考文献[3]和[4]中的方法。
图 2

图 2 像素匹配过程

(5) 样窗匹配：在灰度图像和彩色图像中，可能存在明度和邻域明度方差相近而色度相差较大的像素，这可能会导致因颜色误传而产生的图像失真问题。此时还需在彩色和灰度图像中有针对性地选择色彩内容相近的区域作为样窗，根据实际情况可以设计一组或多组样窗，并在每组样窗之间进行再次匹配。由于样窗中的像素数量一般远小于图像总像素数，搜索时间较短。如图 3(c)所示案例中的“树木”和“草地”区域都被染上了紫色。此时可以在失真区域设置采样窗口，如图 3(d)中的“G1”、“G2”和“G3”，这三个区域相互之间存在一定的重叠，以保证样窗边界处色彩的平滑过渡。样窗“G1”和“G2”涉及绿色为主的“树木”和“草地”，它们首先与彩色图像中相应内容的“C1”、“C2”和“C3”样窗进行匹配。由于“G3”内既有“草地”也有紫色“薰衣草”，因此，在“C1”、“C2”和“C3”的基础上加上“C4”窗口，再与“G3”窗口进行匹配，如图 3(e)所示。图 3(f)显示了样窗匹配后的结果图像。
图 3

图 3 邻域优先匹配结果和样窗匹配结果

2.2 纹理相似性匹配图像纹理信息往往比亮度信息对色彩传递效果的影响更大。Welsh等^[2]提出的基于邻域统计的像素匹配算法本质上也是一种简单的纹理匹配方法。通过相关的研究和分析，本文提出了一个包含高频纹理信息的多维特征向量来描述图像像素间的纹理相似性。以像素“p”为中心的M×M像素邻域的明度标准差如式(2)所示，其中l_s是邻域中某个像素“s”的明度，l是邻域中所有像素的明度平均值。

(2)

M×M邻域中的每个像素都有一个明度标准差，该邻域中所有像素共有M²个标准差。为了描述目标像素邻域的高频变化，本文算法定义了n阶标准差的概念，即n阶明度变化率或纹理变化率。如式(3)所示，Std^n-1(s)是以目标像素“p”为中心的邻域内像素“s”的n-1阶标准差，Std^n-1是邻域内所有像素的n-1阶标准差的平均值。

(3)

像素从低频到高频的纹理特征由像素的明度及其1，2，…，n阶明度标准差共同构成。式(4)表示为中心像素“p”的纹理特征向量，其中“l_p”表示“p”的明度，“Stdⁿ”表示n阶标准差。

(4)

本文利用目标灰度像素与彩色像素之间的向量欧氏距离来描述两者间的匹配误差^[15]，如式(5)所示，其中“p”表示目标灰度图像中的待匹配像素。“x”表示与“p”的邻域像素相匹配的彩色像素，被作为候选匹配像素，“f(p)”和“f(x)”分别表示“x”和“p”的纹理特征向量。“Err”表示根据经验设置的误差阈值。“p”的最终匹配像素表示为“m”，即在所有候选匹配像素中，匹配误差小于“Err”且与f(p)的向量欧氏距离最短的像素被选为“p”的最终匹配像素。

(5)

理论上来说，如果两个像素的匹配误差固定不变时，其纹理特征向量的维数越高，两个像素间的纹理相似度就越高。但实际上，当向量维数增大到一定时，不仅无法优化颜色传递结果，反而会降低计算效率。图 4通过一个案例显示了不同维数纹理特征向量对应的色彩传递结果。在图 4(c)和(d)中，低维特征向量在彩色图像(特别是在颜色急剧变化的图像边缘位置)中产生了明显失真。随着维数的增加，图像失真随之减小。从图 4(e)、4(f)可以看出，当向量维数增加到3维时，图像失真几乎消失。此时继续增加维数只会带来很多无意义的计算。本文通过大量测试发现，3维特征向量能够满足大部分类型图像的颜色传递要求。
图 4

图 4 不同维数的纹理特征向量的色彩传递结果

2.3 匹配误差阈值的设置如式(5)所示，如果目标灰度像素与其候选像素之间的匹配误差大于阈值“Err”，则表明邻域匹配失败，需要执行备选采样匹配。误差阈值“Err”的设置对色彩传递结果和计算速度是有较大影响的。随着误差阈值的增大，越来越多的像素将会满足邻域匹配条件并参与邻域匹配过程，而参与全局匹配的像素则变得越来越少。众所周知，备选采样匹配比邻域匹配需要更多的计算时间，因此，匹配时间随着“Err”的增加而逐渐减少。但在实际应用中，如果阈值“Err”设置得太大，可能会有大量像素在误差较大的情况下仍然参与邻域匹配，从而导致图像失真。根据本文测试结果，在充分权衡算法效果和计算效率的基础上，对于大多数类型的图像来说，将误差阈值“Err”设定为0.5个向量欧式距离单位是比较合适的。
图 5

图 5 图像测试案例

3 算法评价3.1 图像测试效果为增强算法评价的说服力，实验所用测试图像包括人物肖像、自然景观、城市景观、夜晚场景等主题。图 5显示了5个灰度图像彩色化案例，用于测试本文算法和Welsh算法的色彩转移效果。图中每一个案例，从左至右依次为彩色参考图像、目标灰度图像、本文算法结果图像和Welsh算法结果图像。由图 5可以明显看出：对于所有案例，本文算法的图像彩色化效果均好于Welsh算法。例如案例2和3，Welsh算法在灰度图像的部分区域并没有完成彩色化，即彩色化后的图像中还存在明显的灰色区域，而本文算法则基本覆盖了图像所有区域，而在案例1和4中，Welsh算法产生了一些视觉可感知的失真，如图中的“天空白云”区域，这可能源于图像中语义内容不同的区域因具有相似的匹配误差而造成的颜色误传递。
除了图像质量的主观评价外，本文还利用色域可视化技术^[16]对上述5个案例中的算法结果图像进行了色域对比，如图 6所示，每个案例从左至右依次为彩色参考图像、本文算法结果图像及Welsh算法结果图像的色域。由于篇幅限制，这里只显示了3维空间色域的某个平面，每个色域图的右上角显示了计算得出的结果图像与原始图像的色域近似率。可以看出，在案例2、3和4中，Wlesh算法的结果图像与原图像的色域近似率比本文算法明显偏低。但在案例1和5中，两者色域近似率相差不大，这与上面的图像彩色化测试结果基本吻合。
图 6

图 6 算法测试结果图像的色域比较

3.2 样窗匹配的测试如果目标图像的色彩构成或语义内容较为复杂，就需要借助样窗匹配来获得满意的效果。图 7显示了图 5中案例3的样窗匹配过程。图 7(1)、(2)和(3)分别代表彩色参考图像、原始灰度图像和全局匹配后的结果图像。可以看出，全局匹配后的图像中很多区域依然呈现灰色，色彩转移效果较差，还需进行样窗匹配。图 7(4)为第一次样窗匹配的结果，主要将图 7(3)中的白色区域1与彩色参考图像的区域A进行单独匹配，使“黄色胸花”区域的颜色正确转移到了结果图像中的“生日帽”区域。与此类似，在第二次和第三次匹配中，分别将图像区域2、3和彩色参考图像中的区域B、C进行单独匹配，得到最终结果图像，如图 7(5)所示。在最终结果图像中，人物面部和上衣围巾等区域的颜色得到了明显改善。本文算法配合样窗匹配虽然可以改善图像的色彩转移效果，但仍然存在一些问题，如在样窗区域的边缘极易产生明显的边界效应，见图 7(5)中的白线区域，虽然可以在每次匹配的样窗之间设置一定的重叠区域，以保证样窗边界处颜色的平滑过渡，但仍然难以彻底消除边界效应。此外，在样窗位置的选择上还比较依赖人为经验。
图 7

图 7 样窗匹配的测试案例

4 结论针对灰度图像的彩色化问题，本文提出了一种基于邻域优先搜索和纹理相似度匹配的图像颜色转移方法。对于目标灰度图像中的待着色像素，该方法首先基于邻域优先搜索方案找到其候选匹配像素，然后定义纹理特征向量的概念来描述彩色像素和灰度像素之间的纹理相似度，并根据候选像素与目标像素之间的向量空间距离计算匹配误差，以确定最终匹配像素。通过5个图像测试和色域比较案例评价了Welsh经典算法和本文算法的效果，在一定程度上证明了本文算法的有效性。针对初次匹配后不同图像内容由于匹配误差接近而造成的匹配错误和色彩误传问题，在彩色图像和灰度图像中选择相对应的区域进行样窗匹配，并验证了样窗匹配的有效性。

参考文献

[1]	马贺贺, 周岳斌, 饶刚. 图像彩色化方法研究进展[J]. 包装工程, 2019, 40(3): 229-236.
[2]	Welsh T, Ashikhmin M, Mueller K. Transferring color to greyscale images[J]. ACM Transactions on Graphics, 2002, 21(3): 277-280.
[3]	李建明, 叶飞, 于守秋, 等. 一种快速灰度图像彩色化算法[J]. 中国图象图形学报, 2007, 12(3): 536-540.
[4]	陈倩. 一种改进的Welsh灰度图像彩色化算法[J]. 武汉理工大学学报, 2009, 31(22): 151-153.
[5]	滕秀花, 陈昭炯, 叶东毅. 基于多维特征向量及ANN技术的色彩传递算法[J]. 计算机应用, 2006, 26(12): 2866-2868.
[6]	王颍蓓.灰度图像颜色迁移算法研究[D].西安: 西安理工大学, 2016.12-40.
[7]	Liu S, Zhang X. Image colorization based on texture map[J]. Journal of Electronic Imaging, 2013, 22(1): 3011-3020.
[8]	Cao L, Jiao L, Li Z, et al. Grayscale image colorization using an adaptive weighted average method[J]. Journal of Imaging Science & Technology, 2017, 61(6): 1-9.
[9]	Arbelot B, Vergne R, Hurtut T, et al. Local texture-based color transfer and colorization[J]. Computers & Graphics, 2017, 62(2): 15-27.
[10]	Liu S, Zhang X. Automatic grayscale image colorization using histogram regression[J]. Pattern Recognition Letters, 2012, 33(13): 1673-1681. DOI:10.1016/j.patrec.2012.06.001
[11]	Zhao Y, Xu D, Zhang Y. Image colorization using convolutional neural network[J]. Communications in Computer and Information Science, 2016, 634: 238-244.
[12]	Xiao C, Han C, Zhang Z, et al. Example-based colourization via dense encoding pyramids[J]. Computer Graphics Forum, 2020, 39(1): 20-33.
[13]	Deshpande A, Rock J, Forsyth D. Learning large-scale automatic image colorization[C]. IEEE International Conference on Computer Vision (ICCV), 2015: 567-575.
[14]	Deshpande A, Lu J, Yeh M C, et al. Learning diverse image colorization[C]. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017: 2877-2885.
[15]	吴亮, 郭俊峰, 刘国英. 高斯曲率耦合相关性制约规则的图像匹配算法[J]. 包装工程, 2019, 40(1): 168-176.
[16]	朱明, 张志广, 田准. "Windows"平台下显示器色彩再现机理的研究和分析[J]. 液晶与显示, 2017, 32(11): 923-933.