基于KNN图层区分的优化式着色算法

盛家川，杨 巍

天津财经大学 理工学院，天津 300200

1 引言

着色是图像编辑领域中一个活跃的、有挑战性的研究课题，不仅可以解决黑白电影或图像的彩色化问题，也可以给现有彩色视频和图像重新换色，生成具有多种多样颜色风格的彩色效果。近年来出现的优化式着色方法，一般由人工在目标图像上标注一系列彩色线条作为输入，将着色过程转换为优化问题。这类方法既可以直接选色，也便于修改，还避免了分割法出现的颜色分块，作为一类新的着色机制实现着色，因此得到广泛的应用[1-5]。Levin等[6]假设空间相邻像素的颜色与亮度存在相似关系，以用户输入的彩色线条作为基础在YUV颜色空间上进行色彩扩展与传播，实现对灰度图像的着色。之后Yatziv等[7]在YCbCr颜色空间中提出了类似的快速着色方法，大大提高了着色速度。Sheng等[8]假设颜色与特征空间存在相似关系，采用纹理特征分类方法实现灰度图像的着色。Wang等[9]在计算相似度时采用类KNN最近邻搜索结果作为近邻。但与Levin方法一样，该类优化式着色在实际着色过程中存在以下不足之处：

（1）着色结果对用户的输入要求很高，灰度图像上的不同颜色的笔触信息决定了彩色化后的效果，用户交互复杂度较高。

（2）着色结果对颜色标记分布敏感，在弱边缘区域容易失真，易发生颜色区域的不连续或是溢出。

彩色图像的二次着色是着色领域一个具有研究价值的分支[10]，灰度图像的彩色化技术大多可以应用到彩色图像的二次着色之中，但直接使用这些方法将会忽略掉原始图像中的色彩信息。本文在基于Levin所提出的相邻像素亮度相近则颜色相近的颜色融合方法基础上，通过对原图进行图层区分获得图层信息，来减少用户交互工作量，提出一种彩色图像二次着色方法。本文算法将灰度信息和图层信息构建成一个全局权值函数，不受内部纹理、边界缺口和不精确标色的影响，能够更准确地划分着色区域。通过实验结果分析可以说明，这种方法大大简化了用户交互过程，速度快、质量好，还能够避免计算结果依赖于彩色线条位置而容易出现的颜色渗漏问题。

2 KNN图层区分

Chen[11]提出了KNN图层区分算法，采用闭合式解决思路，合理利用共轭梯度法（PCG）的先决条件，在极少的用户注释前提下，花费少量时间就获得非常清晰的自然图像图层区分结果。

与非局部图层区分相类似，KNN算法建立连接关系时采用非局部原则，结果每个图层都得到高质量的图组。非局部原则的假设是降噪像素i是具有与函数k(i,j)给定权值的相似外观的像素点权值之和[12]。

KNN图层区分非常容易在颜色空间中扩展并处理SVBRDF或高维数据。对于自然抠图，为了加强空间相干性，给定像素点的i的特征向量X(i)可以被定义为：

其中，h,s,v代表HSV坐标，(x,y)表示像素点i的空间坐标系。

在实践中KNN图层区分输出的阈值基本上在[0，1]内。当涉及到多层提取，阈值层被认为是前景，而其他作为背景。

3 彩色图像二次着色算法

3.1 算法流程概述

本文受到KNN图层区分的启发，提出基于KNN图层区分的图像二次着色算法，对图像中易发生颜色渗漏的部分进行图层区分，并将该结果作为约束条件引入到优化式着色算法中，对一幅图像进行着色处理。算法流程如图1所示。

图1 算法流程图

（1）给定灰度图和用户着色笔道图，作为优化式着色算法的输入进行着色，得出着色结果，发现部分图像物体边界处渗色。

（2）选择有渗色问题的图像作为目标图像，给定原彩色图像和用户标记注释图，作为基于KNN的图像前背景区分算法的输入进行图层区分，采用封闭式解决方案获得图层区分结果，并得到每个像素点的阈值。

（3）阈值作为约束条件引入优化式着色算法中，生成含灰度信息和阈值的权值函数，并以此作为着色基础，改善颜色渗漏的问题，生成颜色分布精确的图像。

从上述计算过程可以看出本文算法中引入灰度信息和图层信息构建全局权值函数，生成有效的边界防渗漏信息，同时始终控制参与着色计算的图像像素点矩阵规模，提高计算速度。本文在计算过程中使用YUV颜色空间完成基于KNN图层区分的优化式着色计算并获得最后的着色结果。

3.2 图层信息的计算

为了最小化像素点和相邻像素点的颜色信息的差别，强化图像中物体的边缘信息，本文引入新的约束条件阈值α，α参数的期望值是：

其中，α是所有输入图像α值的向量，f(m,n)给定了与像素点m有相似外观的像素点n在计算中所占权值，T(m)是由像素点m信息计算得来的特征向量，(r,g,b)代表RGB坐标，(x,y)表示像素点m的空间坐标系，dmn是像素点m和n之间的像素距离，||·||g是由高斯中心权值加权得出的准则，h1，h2是本文通过反复实验确定的常量。

3.3 基于KNN图层区分的优化式着色算法

在Levin方法[6]基础上，本文算法提出在YUV颜色空间中，其中Y是单色亮度通道，一般以强度简化。U和V是色度通道，为颜色编码。基于一个简单的假设：“灰度图像中空间上相邻的像素点如果它们的灰度相近，则它们的颜色也相近。”算法输入一个强度信息Y(x,y,s)，输出两个颜色信息U(x,y,s)和V(x,y,s)。为简化标记，文中采用字母（如m,n）表示(x,y,s)。于是，Y(m)是特定像素的强度。

图2 新算法实现过程示意图

wmn是权值函数总和为1，当Y(m)与Y(n)相同时权值最大，当两者不同时权值最小。结合灰度信息Y与图层信息α，对式（7）中权值函数赋予如下定义：

σm是m周围像素点灰度值的方差，βm是m周围像素点α值的方差。wmn是权值函数总和为1，当Y(m)与Y(n)相同，并且α(m)与α(n)相同时权值最大，当两两不同时权值最小。相类似的权值函数在图像分割算法中得到广泛的应用[13-14]，通常被当作吸引函数。

通过假设颜色和灰度及α值的局部线性关系可以得到相关吸引。假设一个像素点的颜色信息U(m)是灰度信息Y(m)和α值信息α(m)的线性函数：

对于m周围的像素点线性参数am和bm是相同的。这个假设在经验上可以得到判断[15]，直观上意味着灰度值是连续的，颜色也是连续的，当灰度值处于边缘时颜色也达到边缘（尽管边缘的两边可以是任何两个数）。需要注意的是，由于用户着色笔道分布不均，或是物体边界处可能与背景灰度值相近，就会出现颜色渗漏的情况，针对此问题，本文引入新的约束条件α值，强化边界信息，有效区分像素点计算得到的颜色信息U(m)，从而避免当灰度值相近时颜色渗漏。这种模式给每个图像窗口增加了一对变量，基于吸引函数的相关性可消除am，bm变量。

4 实验结果与分析

实验平台采用Math Work公司开发的Matlab R2012b 8.0软件环境，在英特尔第三代酷睿i5-3317U、主频为1.70 GHz的双核处理器、4 GB内存、操作系统为Windows7旗舰版64位SP1的计算机上，对本文彩色图像二次着色算法予以实现。

图2为本文算法着色过程示意图，图2（e）是Levin方法的实验结果，图中编织球与彩色背景相互晕染，是典型的物体边界处发生颜色渗漏的案例。为了改善该颜色渗漏问题，通过输入彩色原图2（c）和用户注释笔道图2（d），获得KNN 图像前后景区分结果图2（f），提取编织球为前景，其余的为背景，同时获得代表前景所占比例的α值。通过添加约束条件α值与灰度信息Y生成全局权值函数，对图像重新着色，修正有颜色溢出的图像着色结果，获得颜色分布精确的清晰图像图2（g）。同时，比较本文算法结果图2（g）与原图像图2（c），两者图像画面颜色质量相当，本文着色算法结果清晰，优于Levin方法。

相对于一般优化式着色算法，本文算法不要求进行复杂的彩色线条标记，就能够确保彩色图像二次着色结果的质量，较好地解决了着色结果依赖于彩色线条初始分布位置的缺陷。

图3（a）中出于对比参照的目的首先按照优化式着色方法的要求，为花瓣、树叶区域逐一进行彩色线条的标记。图3（b）是使用Levin方法获得的结果，着色结果的细节取决于用户标记的彩色线条的准确性。图3（c）尝试减少用户标记的数量，仅在上述区域分别标记一条彩色线条，可以注意到图3（d）所得到的着色结果中，出现了比较严重的颜色渗漏问题，可见笔画位置的分布对Levin方法着色结果有着显著的影响。图3（e）采用与图3（c）同样的用户输入，使用本文方法的着色结果如图3（f），对比图3（b），它在减少了用户输入的前提下能够保持着色结果的准确性和合理性。

图4（a）（b）（c）依次是对花瓣采用红、紫、蓝三种不同彩色线条标记下获得的着色结果，图像边缘清晰，颜色细腻均匀，色彩也比较真实，取得了较好的彩色化结果。实验结果说明本文算法能够实现多种色彩标记下的彩色图像的二次化着色，且着色结果具有稳定性。

图3 新算法与Levin方法着色效果的比较

图4 多种颜色标记的本文算法着色效果

为了证明本文算法在优化式着色算法领域具有优势，进行了多组对比实验。图5（a）中按照优化式着色方法的要求进行彩色线条的标记，用户需要细致地为图像的各个区域逐一指定颜色；图5（b）（c）（d）依次是 Levin算法[6]，Yatziv 算法[7]，Zhang算法[16]获得的结果，可以注意到图5（b）（c）（d）所得到的着色结果中，出现了不同程度的颜色渗漏问题；本文算法的着色结果如图5（e），在采用与图5（b）（c）（d）同样的用户输入前提下，能够保持着色结果的准确性和合理性。从本文给出的所有实验结果可以发现，本文算法由于强调了图像的边界信息，更准确判断了着色区域的边界，所以取得了更好的彩色化结果。

与现有的优化式着色技术相比，本文提出的基于KNN图层区分的优化式着色算法有两点主要贡献：

（1）鲁棒的初始交互笔触标色。精确的用户笔触对于复杂的场景经常损耗大量的用户精力，影响用户的体验满意度。本文算法支持简单的着色输入，即可完善着色到整个图像中，且能保持更好的细节。

（2）最优的物体边界检测。本文算法在边界有缺口、区域内部有纹理或者零散封闭区域的情况下依然能够正确地判断区域边界，并且能够传递到连续邻接的区域，生成物体边界处无渗漏颜色的图像。

5 结论

现有的优化式着色研究存在用户交互复杂和在边界处容易发生颜色渗漏两大不足。针对灰度图像彩色化技术应用于彩色图像二次着色时往往忽略掉原始图像所带的色彩信息的问题，本文探索了简洁有效的图像二次着色方法，提出基于KNN图层区分的优化式着色算法，对图像中易发生颜色渗漏的部分进行图像前背景区分，并将图层区分阈值作为新的约束条件引入到着色算法中，生成新的权值函数。实验结果表明，本文算法能有效改善物体边界处发生颜色渗漏的问题，得到颜色分布精确的图像，并能形成简洁有效的着色工作框架。

图5 新算法与Levin算法、Yatziv算法和Zhang算法的边界信息比较

预期研究成果将为影视、医疗、太空探索及其他许多工业和科学领域提供便利，并可根据各个领域的特殊需求调整算法和参数，达到成果最优化。

[1]Lee S，Park S W，Oh P，et al，Colorization-based compression using optimization[J].IEEE Transactions on Image Processing，2013，22（7）：2627-2636.

[2]Sheng B，Sun H Q，Magnor M，et al.Video colorization using parallel optimization in feature space[J].IEEE Transactions on Circuits and Systems for Video Technology，2014，24（3）：407-417.

[3]Uruma K，Konishi K，Takahashi T，et al.An image colorization algorithm using sparse optimization[C]//2013 IEEE International Conference on Acoustics，Speech and Signal Processing（ICASSP），2013：1588-1592.

[4]蔡宇文，盛斌，马利庄.优化分割的手绘图像彩色化技术[J].计算机辅助设计与图形学学报，2013，25（6）：774-781.

[5]张可为，陈秋凤，申群太.基于多种易用标记的图像着色[J].光电子·激光，2014，25（2）：386-392.

[6]Levin A，Lischinski D.Colorization using optimization[J].Acm Transactions on Graphics，2004，23（3）：689-694.

[7]Yatziv L，Sapiro G.Fast image and video colorization using chrominance blending[J].IEEE Transactions on Image Processing，2006，15（5）：1120-1129.

[8]Sheng B，Sun H Q，Chen S B，et al.Colorization using the rotation-invariant feature space[J].IEEE Computer Graphics and Applications，2011，31（2）：24-35.

[9]Wang H J，Gan Z L，Zhang Y B，et al.Novel colorization method based on correlation neighborhood similarity pixels priori[C]//Proceedings of 11th International Conference on Signal Processing，Beijing，China：IEEE，2012：885-888.

[10]金舟，孙济洲，张怡.基于颜色融合的交互式图像二次着色方法[J].计算机应用研究，2011，28（9）：3545-3550.

[11]Chen Q F，Li D Z Y，Tang C K.KNN matting[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition（CVPR），2012：520-526.

[12]Gastal E S L，Oliveira M M.Shared sampling for realtime alpha matting[J].Computer Graphics Forum，2010，29（2）：575-584.

[13]魏国剑，侯志强，李武，等.融合多特征的运动一致性图像分割[J].中国图象图形学报，2014，19（5）：701-707.

[14]张晗，何东健.一种融合纹理信息与图论的图像分割方法[J].计算机工程与应用，2014，50（1）：180-184.

[15]孙琰玥，何小海，宋海英，等.一种用于视频超分辨率重建的块匹配图像配准方法[J].自动化学报，2011，37（1）：37-43.

[16]张可为，申群太.优化式着色算法的混色机制[J].电子与信息学报，2013，35（7）：1612-1618.