基于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.