基于KNN圖層區(qū)分的優(yōu)化式著色算法

盛家川，楊 巍

天津財經(jīng)大學(xué) 理工學(xué)院，天津 300200

1 引言

著色是圖像編輯領(lǐng)域中一個活躍的、有挑戰(zhàn)性的研究課題，不僅可以解決黑白電影或圖像的彩色化問題，也可以給現(xiàn)有彩色視頻和圖像重新?lián)Q色，生成具有多種多樣顏色風(fēng)格的彩色效果。近年來出現(xiàn)的優(yōu)化式著色方法，一般由人工在目標(biāo)圖像上標(biāo)注一系列彩色線條作為輸入，將著色過程轉(zhuǎn)換為優(yōu)化問題。這類方法既可以直接選色，也便于修改，還避免了分割法出現(xiàn)的顏色分塊，作為一類新的著色機制實現(xiàn)著色，因此得到廣泛的應(yīng)用[1-5]。Levin等[6]假設(shè)空間相鄰像素的顏色與亮度存在相似關(guān)系，以用戶輸入的彩色線條作為基礎(chǔ)在YUV顏色空間上進(jìn)行色彩擴展與傳播，實現(xiàn)對灰度圖像的著色。之后Yatziv等[7]在YCbCr顏色空間中提出了類似的快速著色方法，大大提高了著色速度。Sheng等[8]假設(shè)顏色與特征空間存在相似關(guān)系，采用紋理特征分類方法實現(xiàn)灰度圖像的著色。Wang等[9]在計算相似度時采用類KNN最近鄰搜索結(jié)果作為近鄰。但與Levin方法一樣，該類優(yōu)化式著色在實際著色過程中存在以下不足之處：

（1）著色結(jié)果對用戶的輸入要求很高，灰度圖像上的不同顏色的筆觸信息決定了彩色化后的效果，用戶交互復(fù)雜度較高。

（2）著色結(jié)果對顏色標(biāo)記分布敏感，在弱邊緣區(qū)域容易失真，易發(fā)生顏色區(qū)域的不連續(xù)或是溢出。

彩色圖像的二次著色是著色領(lǐng)域一個具有研究價值的分支[10]，灰度圖像的彩色化技術(shù)大多可以應(yīng)用到彩色圖像的二次著色之中，但直接使用這些方法將會忽略掉原始圖像中的色彩信息。本文在基于Levin所提出的相鄰像素亮度相近則顏色相近的顏色融合方法基礎(chǔ)上，通過對原圖進(jìn)行圖層區(qū)分獲得圖層信息，來減少用戶交互工作量，提出一種彩色圖像二次著色方法。本文算法將灰度信息和圖層信息構(gòu)建成一個全局權(quán)值函數(shù)，不受內(nèi)部紋理、邊界缺口和不精確標(biāo)色的影響，能夠更準(zhǔn)確地劃分著色區(qū)域。通過實驗結(jié)果分析可以說明，這種方法大大簡化了用戶交互過程，速度快、質(zhì)量好，還能夠避免計算結(jié)果依賴于彩色線條位置而容易出現(xiàn)的顏色滲漏問題。

2 KNN圖層區(qū)分

Chen[11]提出了KNN圖層區(qū)分算法，采用閉合式解決思路，合理利用共軛梯度法（PCG）的先決條件，在極少的用戶注釋前提下，花費少量時間就獲得非常清晰的自然圖像圖層區(qū)分結(jié)果。

與非局部圖層區(qū)分相類似，KNN算法建立連接關(guān)系時采用非局部原則，結(jié)果每個圖層都得到高質(zhì)量的圖組。非局部原則的假設(shè)是降噪像素i是具有與函數(shù)k(i,j)給定權(quán)值的相似外觀的像素點權(quán)值之和[12]。

KNN圖層區(qū)分非常容易在顏色空間中擴展并處理SVBRDF或高維數(shù)據(jù)。對于自然摳圖，為了加強空間相干性，給定像素點的i的特征向量X(i)可以被定義為：

其中，h,s,v代表HSV坐標(biāo)，(x,y)表示像素點i的空間坐標(biāo)系。

在實踐中KNN圖層區(qū)分輸出的閾值基本上在[0，1]內(nèi)。當(dāng)涉及到多層提取，閾值層被認(rèn)為是前景，而其他作為背景。

3 彩色圖像二次著色算法

3.1 算法流程概述

本文受到KNN圖層區(qū)分的啟發(fā)，提出基于KNN圖層區(qū)分的圖像二次著色算法，對圖像中易發(fā)生顏色滲漏的部分進(jìn)行圖層區(qū)分，并將該結(jié)果作為約束條件引入到優(yōu)化式著色算法中，對一幅圖像進(jìn)行著色處理。算法流程如圖1所示。

圖1 算法流程圖

（1）給定灰度圖和用戶著色筆道圖，作為優(yōu)化式著色算法的輸入進(jìn)行著色，得出著色結(jié)果，發(fā)現(xiàn)部分圖像物體邊界處滲色。

（2）選擇有滲色問題的圖像作為目標(biāo)圖像，給定原彩色圖像和用戶標(biāo)記注釋圖，作為基于KNN的圖像前背景區(qū)分算法的輸入進(jìn)行圖層區(qū)分，采用封閉式解決方案獲得圖層區(qū)分結(jié)果，并得到每個像素點的閾值。

（3）閾值作為約束條件引入優(yōu)化式著色算法中，生成含灰度信息和閾值的權(quán)值函數(shù)，并以此作為著色基礎(chǔ)，改善顏色滲漏的問題，生成顏色分布精確的圖像。

從上述計算過程可以看出本文算法中引入灰度信息和圖層信息構(gòu)建全局權(quán)值函數(shù)，生成有效的邊界防滲漏信息，同時始終控制參與著色計算的圖像像素點矩陣規(guī)模，提高計算速度。本文在計算過程中使用YUV顏色空間完成基于KNN圖層區(qū)分的優(yōu)化式著色計算并獲得最后的著色結(jié)果。

3.2 圖層信息的計算

為了最小化像素點和相鄰像素點的顏色信息的差別，強化圖像中物體的邊緣信息，本文引入新的約束條件閾值α，α參數(shù)的期望值是：

其中，α是所有輸入圖像α值的向量，f(m,n)給定了與像素點m有相似外觀的像素點n在計算中所占權(quán)值，T(m)是由像素點m信息計算得來的特征向量，(r,g,b)代表RGB坐標(biāo)，(x,y)表示像素點m的空間坐標(biāo)系，dmn是像素點m和n之間的像素距離，||·||g是由高斯中心權(quán)值加權(quán)得出的準(zhǔn)則，h1，h2是本文通過反復(fù)實驗確定的常量。

3.3 基于KNN圖層區(qū)分的優(yōu)化式著色算法

在Levin方法[6]基礎(chǔ)上，本文算法提出在YUV顏色空間中，其中Y是單色亮度通道，一般以強度簡化。U和V是色度通道，為顏色編碼?；谝粋€簡單的假設(shè)：“灰度圖像中空間上相鄰的像素點如果它們的灰度相近，則它們的顏色也相近?！彼惴ㄝ斎胍粋€強度信息Y(x,y,s)，輸出兩個顏色信息U(x,y,s)和V(x,y,s)。為簡化標(biāo)記，文中采用字母（如m,n）表示(x,y,s)。于是，Y(m)是特定像素的強度。

圖2 新算法實現(xiàn)過程示意圖

wmn是權(quán)值函數(shù)總和為1，當(dāng)Y(m)與Y(n)相同時權(quán)值最大，當(dāng)兩者不同時權(quán)值最小。結(jié)合灰度信息Y與圖層信息α，對式（7）中權(quán)值函數(shù)賦予如下定義：

σm是m周圍像素點灰度值的方差，βm是m周圍像素點α值的方差。wmn是權(quán)值函數(shù)總和為1，當(dāng)Y(m)與Y(n)相同，并且α(m)與α(n)相同時權(quán)值最大，當(dāng)兩兩不同時權(quán)值最小。相類似的權(quán)值函數(shù)在圖像分割算法中得到廣泛的應(yīng)用[13-14]，通常被當(dāng)作吸引函數(shù)。

通過假設(shè)顏色和灰度及α值的局部線性關(guān)系可以得到相關(guān)吸引。假設(shè)一個像素點的顏色信息U(m)是灰度信息Y(m)和α值信息α(m)的線性函數(shù)：

對于m周圍的像素點線性參數(shù)am和bm是相同的。這個假設(shè)在經(jīng)驗上可以得到判斷[15]，直觀上意味著灰度值是連續(xù)的，顏色也是連續(xù)的，當(dāng)灰度值處于邊緣時顏色也達(dá)到邊緣（盡管邊緣的兩邊可以是任何兩個數(shù)）。需要注意的是，由于用戶著色筆道分布不均，或是物體邊界處可能與背景灰度值相近，就會出現(xiàn)顏色滲漏的情況，針對此問題，本文引入新的約束條件α值，強化邊界信息，有效區(qū)分像素點計算得到的顏色信息U(m)，從而避免當(dāng)灰度值相近時顏色滲漏。這種模式給每個圖像窗口增加了一對變量，基于吸引函數(shù)的相關(guān)性可消除am，bm變量。

4 實驗結(jié)果與分析

實驗平臺采用Math Work公司開發(fā)的Matlab R2012b 8.0軟件環(huán)境，在英特爾第三代酷睿i5-3317U、主頻為1.70 GHz的雙核處理器、4 GB內(nèi)存、操作系統(tǒng)為Windows7旗艦版64位SP1的計算機上，對本文彩色圖像二次著色算法予以實現(xiàn)。

圖2為本文算法著色過程示意圖，圖2（e）是Levin方法的實驗結(jié)果，圖中編織球與彩色背景相互暈染，是典型的物體邊界處發(fā)生顏色滲漏的案例。為了改善該顏色滲漏問題，通過輸入彩色原圖2（c）和用戶注釋筆道圖2（d），獲得KNN 圖像前后景區(qū)分結(jié)果圖2（f），提取編織球為前景，其余的為背景，同時獲得代表前景所占比例的α值。通過添加約束條件α值與灰度信息Y生成全局權(quán)值函數(shù)，對圖像重新著色，修正有顏色溢出的圖像著色結(jié)果，獲得顏色分布精確的清晰圖像圖2（g）。同時，比較本文算法結(jié)果圖2（g）與原圖像圖2（c），兩者圖像畫面顏色質(zhì)量相當(dāng)，本文著色算法結(jié)果清晰，優(yōu)于Levin方法。

相對于一般優(yōu)化式著色算法，本文算法不要求進(jìn)行復(fù)雜的彩色線條標(biāo)記，就能夠確保彩色圖像二次著色結(jié)果的質(zhì)量，較好地解決了著色結(jié)果依賴于彩色線條初始分布位置的缺陷。

圖3（a）中出于對比參照的目的首先按照優(yōu)化式著色方法的要求，為花瓣、樹葉區(qū)域逐一進(jìn)行彩色線條的標(biāo)記。圖3（b）是使用Levin方法獲得的結(jié)果，著色結(jié)果的細(xì)節(jié)取決于用戶標(biāo)記的彩色線條的準(zhǔn)確性。圖3（c）嘗試減少用戶標(biāo)記的數(shù)量，僅在上述區(qū)域分別標(biāo)記一條彩色線條，可以注意到圖3（d）所得到的著色結(jié)果中，出現(xiàn)了比較嚴(yán)重的顏色滲漏問題，可見筆畫位置的分布對Levin方法著色結(jié)果有著顯著的影響。圖3（e）采用與圖3（c）同樣的用戶輸入，使用本文方法的著色結(jié)果如圖3（f），對比圖3（b），它在減少了用戶輸入的前提下能夠保持著色結(jié)果的準(zhǔn)確性和合理性。

圖4（a）（b）（c）依次是對花瓣采用紅、紫、藍(lán)三種不同彩色線條標(biāo)記下獲得的著色結(jié)果，圖像邊緣清晰，顏色細(xì)膩均勻，色彩也比較真實，取得了較好的彩色化結(jié)果。實驗結(jié)果說明本文算法能夠?qū)崿F(xiàn)多種色彩標(biāo)記下的彩色圖像的二次化著色，且著色結(jié)果具有穩(wěn)定性。

圖3 新算法與Levin方法著色效果的比較

圖4 多種顏色標(biāo)記的本文算法著色效果

為了證明本文算法在優(yōu)化式著色算法領(lǐng)域具有優(yōu)勢，進(jìn)行了多組對比實驗。圖5（a）中按照優(yōu)化式著色方法的要求進(jìn)行彩色線條的標(biāo)記，用戶需要細(xì)致地為圖像的各個區(qū)域逐一指定顏色；圖5（b）（c）（d）依次是 Levin算法[6]，Yatziv 算法[7]，Zhang算法[16]獲得的結(jié)果，可以注意到圖5（b）（c）（d）所得到的著色結(jié)果中，出現(xiàn)了不同程度的顏色滲漏問題；本文算法的著色結(jié)果如圖5（e），在采用與圖5（b）（c）（d）同樣的用戶輸入前提下，能夠保持著色結(jié)果的準(zhǔn)確性和合理性。從本文給出的所有實驗結(jié)果可以發(fā)現(xiàn)，本文算法由于強調(diào)了圖像的邊界信息，更準(zhǔn)確判斷了著色區(qū)域的邊界，所以取得了更好的彩色化結(jié)果。

與現(xiàn)有的優(yōu)化式著色技術(shù)相比，本文提出的基于KNN圖層區(qū)分的優(yōu)化式著色算法有兩點主要貢獻(xiàn)：

（1）魯棒的初始交互筆觸標(biāo)色。精確的用戶筆觸對于復(fù)雜的場景經(jīng)常損耗大量的用戶精力，影響用戶的體驗滿意度。本文算法支持簡單的著色輸入，即可完善著色到整個圖像中，且能保持更好的細(xì)節(jié)。

（2）最優(yōu)的物體邊界檢測。本文算法在邊界有缺口、區(qū)域內(nèi)部有紋理或者零散封閉區(qū)域的情況下依然能夠正確地判斷區(qū)域邊界，并且能夠傳遞到連續(xù)鄰接的區(qū)域，生成物體邊界處無滲漏顏色的圖像。

5 結(jié)論

現(xiàn)有的優(yōu)化式著色研究存在用戶交互復(fù)雜和在邊界處容易發(fā)生顏色滲漏兩大不足。針對灰度圖像彩色化技術(shù)應(yīng)用于彩色圖像二次著色時往往忽略掉原始圖像所帶的色彩信息的問題，本文探索了簡潔有效的圖像二次著色方法，提出基于KNN圖層區(qū)分的優(yōu)化式著色算法，對圖像中易發(fā)生顏色滲漏的部分進(jìn)行圖像前背景區(qū)分，并將圖層區(qū)分閾值作為新的約束條件引入到著色算法中，生成新的權(quán)值函數(shù)。實驗結(jié)果表明，本文算法能有效改善物體邊界處發(fā)生顏色滲漏的問題，得到顏色分布精確的圖像，并能形成簡潔有效的著色工作框架。

圖5 新算法與Levin算法、Yatziv算法和Zhang算法的邊界信息比較

預(yù)期研究成果將為影視、醫(yī)療、太空探索及其他許多工業(yè)和科學(xué)領(lǐng)域提供便利，并可根據(jù)各個領(lǐng)域的特殊需求調(diào)整算法和參數(shù)，達(dá)到成果最優(yōu)化。

[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]蔡宇文，盛斌，馬利莊.優(yōu)化分割的手繪圖像彩色化技術(shù)[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2013，25（6）：774-781.

[5]張可為，陳秋鳳，申群太.基于多種易用標(biāo)記的圖像著色[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].計算機應(yīng)用研究，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].中國圖象圖形學(xué)報，2014，19（5）：701-707.

[14]張晗，何東健.一種融合紋理信息與圖論的圖像分割方法[J].計算機工程與應(yīng)用，2014，50（1）：180-184.

[15]孫琰玥，何小海，宋海英，等.一種用于視頻超分辨率重建的塊匹配圖像配準(zhǔn)方法[J].自動化學(xué)報，2011，37（1）：37-43.

[16]張可為，申群太.優(yōu)化式著色算法的混色機制[J].電子與信息學(xué)報，2013，35（7）：1612-1618.