金正猛,周 晨

(南京郵電大學理學院,江蘇南京 210023)

?

基于耦合全變差的快速圖像著色算法

金正猛,周 晨

(南京郵電大學理學院,江蘇南京 210023)

本文在YCbCr色彩空間機制下,結(jié)合目標灰度圖像的梯度信息,提出基于耦合全變差的圖像著色模型.然后,利用交替方向乘子算法(ADMM),設計所提模型的快速數(shù)值求解算法,并給出了該算法的收斂性結(jié)果.最后,數(shù)值實驗結(jié)果表明,該模型在快速著色的同時,能有效地防止顏色越界.

圖像處理；圖像著色；耦合全變差；交替方向乘子算法

1 引言

圖像著色技術(shù)是對灰度圖像人為加上彩色信息,以利于圖像研究者對于圖像的進一步分析和研究.圖像著色技術(shù)的使用范圍很廣泛,可用于古畫修復,給黑白影視上色、廣告設計等.近年來已經(jīng)出現(xiàn)的一些著色方法主要可分為兩類,一種是基于顏色轉(zhuǎn)移的著色方法,另一種是基于局部顏色擴張的著色方法.對基于顏色轉(zhuǎn)移的著色方法,需要輸入一幅和目標灰度圖像色調(diào)相似的彩色圖像作為參照圖,根據(jù)一定的算法將參照圖中的顏色轉(zhuǎn)移到目標灰度圖像中,這種方法對于參照圖像的選取較為困難；對基于局部顏色擴張的著色方法則是需要人為的在目標灰度圖像上畫出彩色線條,再利用一些算法使彩色線條中的色彩擴展到整幅圖像上,以達到著色的目的.這種方法最初由Horiuchi等人提出,他們基于“種子像素”的理念把圖像中所有像素與其臨近像素顏色差異的總和作為最小化目標,將圖像彩色化轉(zhuǎn)換為一個極值問題[1].這種方法雖在某種程度上解決圖像彩色化問題,但是著色效果較差,而且計算量很大.Levin等人利用圖像中所有像素與其鄰域像素的色度的加權(quán)平方和最小,以實現(xiàn)顏色擴展的方法取得了不錯的效果[2].Yatziv利用加權(quán)距離色度混合技術(shù),找出最短路徑進行快速圖像彩色化[3].Heu利用像素優(yōu)先確保著色后圖像中的重要區(qū)域的顏色準確[4].王朔中等人在文獻[5]中提出了一種各向異性的非線性擴散圖像彩色化方法,通過設置自適應的張量函數(shù),使顏色在平滑區(qū)域快速均勻擴散,在顏色交界處按各向異性方式擴散,然后采用有限差分法對擴散方程進行數(shù)值求解.近年來還出現(xiàn)了很多不同方法的圖像著色模型,例如基于概率距離變換的圖像著色[6],利用隨機數(shù)據(jù)對圖像重新著色已達到保邊緣的作用[7],通過判別結(jié)構(gòu)特征進行圖像著色[8],通過結(jié)構(gòu)張量改善著色效果[9]等.

本文關(guān)注的是基于局部顏色擴張變分偏微分方程著色方法.Sapiro首次將偏微分方程的方法引入到圖像著色中,此模型是最小化亮度通道Y的梯度與色度通道Cb的梯度之間的差值,以此使線條顏色擴展到整幅圖像[10].此模型不能很好的處理圖像邊界顏色定位問題,出現(xiàn)了邊界模糊和顏色越界現(xiàn)象.Sung等人[11]提出了全變差著色模型,將圖像著色看作圖像修復問題來處理,將未涂色區(qū)域作為要修復部分,通過解優(yōu)化問題得到圖像的色度信息,實現(xiàn)顏色擴展.但是該模型著色效果不夠理想,且計算速度較慢.

為了克服以上變分模型著色過程中容易出現(xiàn)顏色越界及計算速度較慢等缺陷.本文首先在YCbCr色彩空間中考慮圖像著色問題,提出一耦合亮度通道的全變差著色模型.另外,本文利用交替方向乘子算法(Alternating Direction Method of Multipliers,ADMM),給出了耦合全變差著色模型的快速數(shù)值求解算法,并證明該算法的收斂性.最后通過數(shù)值實驗驗證該模型的可行性與有效性.

2 模型介紹

對目標灰度圖像著色,需要在合適的色彩空間中進行.RGB彩色空間是計算機技術(shù)中使用最廣泛的色彩空間之一.其它典型的色彩空間有YIQ空間(luminance,hue,and saturation)、YCbCr空間(Luminance,two color-difference components)、CB空間(Chromaticity and Brightness)等,這些色彩空間一般可將顏色圖像分解為亮度(luminance)和色度(chrominance)兩部分,并且與RGB空間之間都滿足某種線性變換關(guān)系.以在YCbCr空間中著色為例,一般把灰度圖像的灰度值作為彩色圖像的亮度信息Y,如果通過某種合適的方法將該灰度圖像的色度信息(Cb,Cr)恢復出來,再通過與RGB空間之間的變換關(guān)系計算出相應的R、G和B三通道的像素值,即完成了灰度圖像彩色化的過程.

(1)

滿足

|C(x)|=1,x∈Ω

(2)

其中λ為權(quán)重系數(shù),BV(Ω;R3)為有界變差函數(shù)空間,Dc為待著色區(qū)域.由于此CB色彩空間是非凸的,導致S-R模型需滿足非凸約束(2).在文獻[11]中,作者用不動點算法對S-R模型進行求解.實驗結(jié)果表明:S-R模型不僅著色效果不夠理想,計算速度較慢,而且數(shù)值結(jié)果對參數(shù)的選取較為敏感.實際著色效果如圖1中(b)所示.

為了克服CB色彩空間非凸的缺陷,結(jié)合YCbCr凸的色彩空間,在S-R模型的基礎上,我們可以得到如下的全變差著色模型:

(3)

為了使擴展后的顏色與灰度圖像中物體的邊界充分吻合,且防止顏色越界.本文充分挖掘目標灰度圖像中物體的邊界信息(亮度的梯度),提出如下的耦合全變差著色模型:

(4)

其中:γ為亮度信息的權(quán)重系數(shù).由于該模型考慮到了目標灰度圖像中物體的邊緣信息,使得著色后的顏色能與目標灰度圖像中物體充分匹配,且能有效防止顏色越界.實際著色效果如圖1中的(d)所示.從圖1可以看出,使用本文模型色彩擴展效果較好.

通過簡單分析本文所提著色模型,不難發(fā)現(xiàn)式(4)中目標泛函關(guān)于變量V是凸的.因此我們可以利用基于凸優(yōu)化的交替方向乘子(ADMM)算法,給出所提著色模型的快速數(shù)值求解算法,并證明該算法的收斂性.

3 本文算法與收斂性分析

經(jīng)典的ADMM算法最早是由文獻[12]提出的,本文利用ADMM算法,給出耦合全變差模型(4)的快速數(shù)值求解方法,首先令R=(γY,Cb,Cr),則式(4)轉(zhuǎn)化為

(5)

min∫Ω|d|dx+λη∫Ω|z-V0|2dx

s.td=▽R,z=V

(6)

將式(6)轉(zhuǎn)化為求解無約束極值問題,得到其增廣Lagrange函數(shù)如下:

這里的λ=(λ1,λ2)是Lagrange乘子向量,γ1,γ2>0是處罰參數(shù).

下面分別對三個子問題d,z,V進行求解:

(1)求解關(guān)于d的子問題:

等價于

根據(jù)文獻[13,14],可求出

(7)

(2)求解z的子問題:

對z進行求導并令其為0,可以解得

(8)

(3)求解V的子問題:

由Euler-Lagrange方程得出

再利用快速Fourier變換求出

(9)

其中F和F-1分別為快速Fourier變換及其逆變換.

結(jié)合式(7)～式(9)式,給出本文算法的具體步驟為:

Step1:令k=0,V=z=λ2=0,d=λ1=0

Step2:迭代未停止,反復執(zhí)行如下步驟:

(6)k=k+1

Step3:迭代終止條件:||Vk+1-Vk||

結(jié)合經(jīng)典的ADMM算法的收斂性分析[12,15,16],下面給出本文算法的收斂性結(jié)果.由于其證明過程與文獻[15,16]中完全類似,故此處省略其證明過程.

4 著色具體操作步驟與實驗結(jié)果分析

結(jié)合本文算法的具體步驟,給出本文圖像著色的具體方法:

步驟1:輸入一幅灰度圖像,并在灰度圖像上繪出適當彩色線條,此時兩幅圖像都是在RGB色彩空間上的.

步驟2:將兩幅圖像轉(zhuǎn)換到Y(jié)CbCr色彩空間上,分別得到兩幅圖像的亮度Y與色度V0=(Cb,Cr)和V=(Cb,Cr),兩幅圖像的亮度Y相同,V0為灰度圖像的色度,V是帶有彩色線條的圖像.

步驟3:對λ、γ、γ1和γ2分別賦值,本文中令λ=9、γ=25、γ1=9、γ2=1,tol=10-3,利用文中所提算法求出V=(Cb,Cr),并將求出的色度賦值給原灰度圖像,得到Y(jié)CbCr空間上的新的圖像.

步驟4:將新圖像轉(zhuǎn)換到RGB空間上,輸出圖像.

為了驗證本文的算法,對大量圖像進行了著色處理,并同現(xiàn)有算法進行比較.這里用峰值信噪比(Peak Signal to Noise Ratio,PSNR)和均方誤差(Mean Square Error,MSE)來評價著色效果.其定義形式為:

其中,ftrue和f分別為原始彩色圖像和著色后圖像,若著色后圖像的PSNR的值越大,MSE的值越小則表明圖像著色后的圖像與真實彩色圖像越接近,著色效果越好.

實驗結(jié)果如圖2～圖4所示,其中(a)是待處理的灰度圖像,(b)是畫線圖像,(c)是計算S-R模型所得圖像,(d)和(e)分別是用梯度下降法和本文算法得到的圖像.(f)是真實的彩色圖像.

表1給出了S-R模型與本文模型著色后圖像的PSNR值和MSE值.表2列出了實驗分別采用S-R模型,梯度下降法和本文算法對應的迭代次數(shù)和運行時間.

從圖2～圖4可以看出,S-R模型的著色效果較差,顏色的擴展不均勻且在邊緣處有顏色越界的現(xiàn)象.本文耦合全變差模型在顏色擴展方面有較好效果,且能有效防止顏色越界.表1顯示,對于同一張圖片的著色,本文模型的PSNR值明顯高于S-R模型,本文模型的MSE值小于S-R模型,由此也可看出通過本文模型著色后的圖像與原彩色圖像更接近,因此著色效果更好.

表1 S-R模型與本文模型著色后圖像的PSNR值和MSE值

表2 S-R模型的不動點算法,本文模型的梯度下降法和本文快速算法對應的計算速度

圖像算法迭代次數(shù)運行時間(s)2S-R模型的不動點算法9432.291718梯度下降法287207.484684本文算法408.1819453S-R模型的不動點算法9618.886252梯度下降法12856.967205本文算法302.8577154S-R模型的不動點算法136104.225937梯度下降法285360.859803本文算法3710.573055

從表2可以看出,在迭代終止條件相同時,S-R模型使用的算法和梯度下降法迭代步數(shù)較多且運行速度較慢,本文算法大大減少了迭代步驟,使運行更加迅速.

5 結(jié)束語

本文研究基于顏色擴展的變分圖像著色方法,從TV著色模型(S-R模型)出發(fā),結(jié)合目標灰度圖像的梯度信息,提出了耦合全變差圖像著色模型,并給出了該模型的快速數(shù)值算法.實驗結(jié)果表明:該模型能有效防止著色過程中顏色在邊緣處的越界,使得整體著色效果更佳.而且,所提快速算法大大提高了計算速度.

[1]Takahiko Horiuchi.Colorization algorithm using probabilistic relaxation[J].Image and Vision Computing,2004,22(3):197-202.

[2]Levin A,Lischinski D,Weiss Y. Colorization using optimization[A].Proceedings of ACM SIGGRAPH[C].New York,2004.684-689.

[3]L Yatziv, G Sapiro. Fast image and video colorization using chrominance blending[J].IEEE Trans Image Process,2006,15(5):1120-1129.

[4]Junhee Heu,Dae-Young Hyun,Chang-Su Kim,Sang-Uk Lee.Image and video colorization based on prioritized source propagation[A]. IEEE International Conference on Image Processing[C].IEEE,2009.465-468.

[5]陳穎，王朔中.避免顏色越界的各向異性擴散圖像彩色化[J].電子與信息學報,2014,36(2)：271-277.

Chen Ying,Wang Shuo-zhong.Image colorization without edge crossover of colors based on anisotropic diffusion[A].Journal of Electronics and Information Technology,2014,36(2):271-277.(in Chinese)

[6]Przemyslaw Lagodzinski, Bogdan Smolka.Digital image colorization based on probabilistic distance transformation[A].International Symposium ELMAR[C]. IEEE,2008.495-498.

[7]Tae Hoon Kim, Kyoung Mu Lee, Sang Uk Lee.Edge-preserving colorization usingdata-driven random walks with restart[A].IEEE International Conference on Image Processing[C].IEEE,2010.1661-1664.

[8]Michal Kawulok,Jolanta Kawulok,Bogdan Smolka.Discriminative textural features for image and video colorization[J].IEICE Transactions on Information and Systems,95-D(2012):1722-1730.

[9]Mark S Drew, Graham D Finlayson. Improvement of colorization realism via the structure tensor[J]. International Journal on Image Graphics，2011,11:589-609.

[10]Sapiro G.Inpainting the colors[A].IEEE International Conference on Image Processing[C].IEEE,2005.698-701.

[11]Sung Ha Kang, Riccardo March.Variational models for image colorization via chromaticity and brightness decomposition[J].IEEE Transactions on Image Processing,2007,16(9):2251-2261.

[12]Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite-element approximations[J].Computer and Mathematics with Applications,1976,2(1):17-40.

[13]Wang Y, Yang J, Yin W, et al. A new alteranting minimization algorithm for total variation image reconstruction[J].SIAM Journal of Mathematical Imaging and Vision,2008,1(3):948-951.

[14]Yang J,Yin W,Zhang Y,et al.A fast algorithm for edge-preserving variational multichannel image restoration[J].SIAM Journal of Mathematical Imaging and Vision,2009,2(2):569-592.

[15]Boyd S,Parinkh N,Chu E,et al.Distributedoptimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends in Machine Learning,2010,3(1):1-122.

[16]Glowinski R, Marrocco A. Sur lapproximation parelements finis dordre un,et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires[J].Revue Francaise D’Automatique,Informatique,Recherch Operationnel，1975,9(2):41-76.

金正猛 男，1982年8月出生，博士，副教授，碩士生導師.現(xiàn)在南京郵電大學理學院任教，研究方向為非線性偏微分方程及其在圖像處理中的應用.

E-mail:jinzhm@njupt.edu.cn

周 晨 女，1990年6月出生.南京郵電大學應用數(shù)學專業(yè)碩士研究生，研究方向為基于偏微分方程的圖像處理.

E-mail:zhouchen1nana@126.com

A Fast Coupled Total Variation Algorithm for Image Colorization

JIN Zheng-meng,ZHOU Chen

(SchoolofScience,NanjingUniversityofPostsandTelecommunications,Nanjing,Jiangsu210023,China)

Under the YCbCr color space mechanism,we propose a coupled total variation model for image colorization by combining the gradient of target grayscale image.Then we design a fast algorithm to solve the proposed model numerically by incorporating the alternating direction method of multipliers(ADMM) algorithm,and give the convergence results of the proposed algorithm.Finally,experimental results are reported,demonstrating that the proposed model can effectively prevent colors from crossing over the edges of the target grayscale image during fast colorization.

image processing; image colorization; coupled total variation; alternating direction method of multipliers(ADMM) algorithm

2015-03-13;

2016-04-12;責任編輯:李勇鋒

國家自然科學基金重大研究計劃(培育項目)(No.91330101)；江蘇省高校自然科學基金(No.15KJB110018)；江蘇省省級重點STITP(No.SZDG2015028)；南京郵電大學科研基金(No.NY215088)

TN911.73

A

0372-2112 (2016)10-2364-06

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.012