多尺度并行坐標(biāo)插值實(shí)時(shí)圖像克隆算法

沈曄湖 蔣全勝 汪幫富 朱其新

（蘇州科技大學(xué)機(jī)械工程學(xué)院，蘇州，215009）

引 言

作為一種圖像編輯技術(shù)，圖像克隆能夠?qū)⒃磮D像中的克隆區(qū)域嵌入目標(biāo)圖像的指定位置，并且實(shí)現(xiàn)該區(qū)域與目標(biāo)圖像背景的自然融合，使用戶在觀察目標(biāo)圖像時(shí)不會(huì)產(chǎn)生明顯的突兀感。

對(duì)人類視覺(jué)系統(tǒng)的研究表明：人類視覺(jué)系統(tǒng)對(duì)場(chǎng)景局部亮度差異的敏感度要遠(yuǎn)高于亮度的絕對(duì)值本身[1]?；谠摾碚?，傳統(tǒng)的圖像克隆技術(shù)在保持克隆區(qū)域內(nèi)部顏色梯度分布的前提下保證克隆區(qū)域的邊緣與目標(biāo)圖像對(duì)應(yīng)位置顏色的相似性，這一般通過(guò)求解泊松方程來(lái)實(shí)現(xiàn)。Perez等[2]證明求解泊松方程等價(jià)于求解包含狄利克雷邊界條件的拉普拉斯方程，該邊界條件設(shè)置為克隆區(qū)域邊界在源圖像和目標(biāo)圖像處的色彩差異。上述問(wèn)題最終可通過(guò)求解大規(guī)模稀疏線性系統(tǒng)來(lái)得到。Adobe公司從Photo?shop 7開(kāi)始支持類似于圖像克隆效果的修復(fù)筆刷工具。該筆刷工具通過(guò)求解四階偏微分方程的手段保證克隆區(qū)域內(nèi)部梯度值的連續(xù)性[3]。Agarwala等[4]提出將多張圖像中的內(nèi)容融合的算法，采用Graph-cut優(yōu)化技術(shù)選擇不同圖像中的最優(yōu)融合邊界，圖像融合仍通過(guò)求解泊松方程來(lái)實(shí)現(xiàn)。Jia等[5]發(fā)現(xiàn)泊松圖像編輯的效果依賴于克隆圖像區(qū)域的邊界，因此提出了采用最短閉合路徑算法來(lái)提取最優(yōu)的克隆區(qū)域邊界。

求解泊松方程的運(yùn)算復(fù)雜度和內(nèi)存消耗均較高。為了克服上述缺陷，Agarwala[6]利用自適應(yīng)四叉樹(shù)細(xì)分技術(shù)構(gòu)建了約簡(jiǎn)的線性系統(tǒng)進(jìn)行求解，該方法僅可以用于加速特定問(wèn)題如圖像拼接領(lǐng)域泊松方程的求解。McCann和Pollard[7]提出了基于GPU的多重網(wǎng)格泊松求解器，可以實(shí)現(xiàn)快速的圖像克隆，然而該算法的具體實(shí)現(xiàn)難度較大且運(yùn)行時(shí)對(duì)顯存的需求較高，作者在文中指出當(dāng)算法對(duì)內(nèi)存的需求超過(guò)顯存容量時(shí)，算法性能會(huì)大幅度下降。

除了上述復(fù)雜的求解泊松方程的方案，F(xiàn)arbman等[8]發(fā)現(xiàn)泊松圖像克隆的本質(zhì)是構(gòu)建一個(gè)調(diào)和插值從而將區(qū)域邊界的不一致性擴(kuò)散到區(qū)域內(nèi)部。他們利用均值坐標(biāo)技術(shù)直接通過(guò)圖像插值產(chǎn)生平滑的內(nèi)部區(qū)域，從而避免了求解泊松方程。由于該方法利用了圖像插值技術(shù)，所以算法實(shí)現(xiàn)非常容易。但是該方法插值系數(shù)的構(gòu)造計(jì)算量較大，導(dǎo)致其運(yùn)算復(fù)雜度很高。為此，作者提出了通過(guò)自適應(yīng)網(wǎng)格等預(yù)處理方法，從而在一定程度上降低了圖像插值階段的運(yùn)算復(fù)雜度。但預(yù)處理手段的引入導(dǎo)致圖像克隆整體過(guò)程無(wú)法實(shí)現(xiàn)實(shí)時(shí)運(yùn)算，而且預(yù)處理步驟較復(fù)雜，使得該算法實(shí)現(xiàn)的難度大幅上升。

近年來(lái)，圖像克隆研究主要集中在改善圖像克隆視覺(jué)效果方面。如Tanaka等[9]通過(guò)一種改進(jìn)的泊松方程實(shí)現(xiàn)了在克隆和背景區(qū)域顏色差異較大情況下的平緩過(guò)渡；李貝等[10]在均值坐標(biāo)技術(shù)基礎(chǔ)上提出了利用局部親和力傳播算法改善圖像克隆中的顏色不協(xié)調(diào)問(wèn)題；黃美玉等[11]通過(guò)構(gòu)建光照一致的數(shù)據(jù)約束和馬爾科夫隨機(jī)場(chǎng)函數(shù)進(jìn)行求解的方式解決了源圖像和目標(biāo)圖像光照環(huán)境不一致的問(wèn)題；文獻(xiàn)[12]通過(guò)引入顏色不變量模型得到圖像光照判斷參數(shù)，進(jìn)而對(duì)克隆選區(qū)進(jìn)行自適應(yīng)的顏色匹配。上述算法運(yùn)算復(fù)雜度均較高，處理100萬(wàn)像素的圖像克隆區(qū)域的時(shí)間均在秒級(jí)。

鑒于目前較少有針對(duì)圖像克隆算法的簡(jiǎn)易實(shí)時(shí)化研究，本文基于文獻(xiàn)[8]，提出了一種改進(jìn)的均值坐標(biāo)權(quán)重系數(shù)的計(jì)算策略，大幅降低權(quán)重系數(shù)的計(jì)算復(fù)雜度，避免了實(shí)現(xiàn)較復(fù)雜的預(yù)處理步驟。此外結(jié)合多尺度圖像處理技術(shù)以及并行加速技術(shù)進(jìn)一步實(shí)現(xiàn)加速，從而在當(dāng)前主流GPU上實(shí)現(xiàn)了對(duì)100萬(wàn)像素圖像區(qū)域的實(shí)時(shí)克隆。定性和定量實(shí)驗(yàn)結(jié)果均表明本文提出的方法得到的結(jié)果與文獻(xiàn)[8]十分接近。

1 均值坐標(biāo)圖像克隆

1.1 均值坐標(biāo)簡(jiǎn)介

為保證本文的可讀性，首先簡(jiǎn)要介紹2D均值坐標(biāo)的基本概念，詳細(xì)內(nèi)容參見(jiàn)文獻(xiàn)[13]。

如圖1所示，對(duì)于2D圖像內(nèi)的一個(gè)區(qū)域P，定義該區(qū)域的邊緣為?P，包含m個(gè)像素：p0,p1,…,pm-1,pi∈R2。為不失一般性，定義：pm=p0。從而區(qū)域P內(nèi)的像素x相對(duì)于?P的均值坐標(biāo)可定義為

圖1 圖像均值坐標(biāo)的定義Fig.1 Definition of mean-value coordinates

式中

式中||·||表示L2范數(shù)。

1.2 均值坐標(biāo)圖像克隆算法流程

實(shí)現(xiàn)圖像克隆算法的基本流程如下[8]

步驟1 計(jì)算均值坐標(biāo)。對(duì)于區(qū)域P內(nèi)的每一個(gè)像素x，根據(jù)式（1，2）計(jì)算其相對(duì)于?P的均值坐標(biāo)并保存。

步驟2 計(jì)算區(qū)域邊緣處的前背景色彩差。對(duì)于?P中的每一個(gè)像素pi，通過(guò)式(3)計(jì)算前背景色彩差并保存。

式中：It(pi)和Is(pi)分別為pi處目標(biāo)圖像和源圖像的RGB值組成的矢量。

步驟3 對(duì)于每一個(gè)區(qū)域P內(nèi)的像素x，計(jì)算其均值坐標(biāo)插值結(jié)果。首先利用下式計(jì)算顏色校正矢量

像素x的最終顏色值的計(jì)算方法為

2 本文方法

圖2給出了本文算法的總體流程圖。對(duì)于1.2節(jié)的算法，其運(yùn)算復(fù)雜度最高的部分是步驟1。假設(shè)區(qū)域P內(nèi)的像素個(gè)數(shù)為n，其邊緣?P包含m個(gè)像素，通常n?m。步驟1中調(diào)用式（2）計(jì)算次數(shù)的數(shù)量級(jí)為O(nm)。但是式（2）中需要計(jì)算兩個(gè)角的正切值，而且兩個(gè)角度本身還需通過(guò)余弦定理計(jì)算得到，因此復(fù)雜度較高，造成算法無(wú)法實(shí)現(xiàn)實(shí)時(shí)處理。為此，文獻(xiàn)[8]提出利用預(yù)處理算法減少n和m，從而降低式（1）的運(yùn)算復(fù)雜度以及調(diào)用式（2）的次數(shù)。但是為了減少n和m引入的預(yù)處理算法本身復(fù)雜度不低，文獻(xiàn)[8]中報(bào)告對(duì)于100萬(wàn)像素的克隆區(qū)域的預(yù)處理時(shí)間在1 s以上，因此導(dǎo)致圖像克隆算法整體無(wú)法實(shí)現(xiàn)實(shí)時(shí)處理。

圖2 算法總體流程圖Fig.2 Flowchart of the proposed algorithm

2.1 改進(jìn)的均值坐標(biāo)

與文獻(xiàn)[8]不同，本文提出的算法通過(guò)合理的近似技術(shù)直接簡(jiǎn)化式（2）的計(jì)算，以降低整體的運(yùn)算復(fù)雜度。

根據(jù)麥克勞林公式，當(dāng)x接近0時(shí)對(duì)tan(x)進(jìn)行級(jí)數(shù)展開(kāi)并取一階近似可得到

將式（6）代入式（2）可得

為不失一般性，假設(shè)?P是由4-連通的像素組成，因此對(duì)于?P上的任意兩個(gè)相鄰像素pi和pi-1，它們之間的距離恒為1?？梢则?yàn)證當(dāng)區(qū)域P內(nèi)的像素x與像素pi和pi-1之間距離在5個(gè)像素以上時(shí)，角度αi接近0，上述近似的誤差約為0.33%。因此對(duì)于區(qū)域P內(nèi)的絕大多數(shù)像素x，式（7）是對(duì)式（2）的較優(yōu)近似。

式（7）仍需要計(jì)算兩個(gè)角度 αi-1和 αi，為了進(jìn)一步簡(jiǎn)化式（7）的計(jì)算，本文提出了如下算法。如圖3所示，頂點(diǎn) pi-1,pi和 x組成三角形，αi-1=∠pixpi-1，虛線xq為αi-1的角平分線，它與邊pi-1pi的交點(diǎn)為p‘。圓弧piq是以x為圓心，||pi-x||為半徑的圓弧段。根據(jù)圓弧的定義，有

圖3 均值坐標(biāo)的簡(jiǎn)化計(jì)算Fig.3 Simplified calculations of mean-value coor?dinates

式中：||piq||a為圓弧piq的長(zhǎng)度。如前所述，||pi-pi-1||=1并且αi-1/2接近于0，因此可以將||piq||a近似為||pi-pi-1||的一半也即0.5，從而式（8）可以近似為（請(qǐng)參考附錄A關(guān)于該近似的可行性驗(yàn)證）

類似地可以得到

將式（9，10）代入式（7）可得

比較式（11）和式（2）可知式（11）只需計(jì)算pi和x的距離平方，無(wú)需計(jì)算任何角度，因此比式（2）節(jié)約了2次角度計(jì)算、2次正切計(jì)算和1次開(kāi)方計(jì)算，從而實(shí)現(xiàn)了大幅度的簡(jiǎn)化。

由于最終的克隆區(qū)域顏色校正結(jié)果可根據(jù)式（4）均值坐標(biāo)相對(duì)權(quán)重的線性組合來(lái)得到，而通常情況下邊緣?P包含的像素個(gè)數(shù)m在103數(shù)量級(jí)，因此通過(guò)式（11）計(jì)算得到的少量權(quán)重誤差通過(guò)上述線性組合的平均效應(yīng)后不會(huì)對(duì)最終的校正結(jié)果產(chǎn)生大的影響。這將在實(shí)驗(yàn)結(jié)果部分作詳細(xì)驗(yàn)證。

2.2 多尺度并行加速

根據(jù)式（5），克隆區(qū)域內(nèi)像素的最終顏色值取決于顏色校正矢量r(x)。r(x)是克隆區(qū)域邊緣像素處顏色差的線性組合。根據(jù)式（1，4，11），在克隆區(qū)域內(nèi)部r(x)是平緩變化的，受文獻(xiàn)[14]的啟發(fā)，本文提出采用多尺度并行的手段進(jìn)一步加速計(jì)算。首先將源圖像和目標(biāo)圖像降采樣[15]；其次對(duì)降采樣的克隆區(qū)域用并行加速手段計(jì)算每個(gè)像素的顏色校正矢量r(x)；然后將克隆區(qū)域?qū)?yīng)的顏色校正矢量r(x)進(jìn)行升采樣[15]，使得分辨率達(dá)到初始狀態(tài)；最后利用r(x)計(jì)算克隆區(qū)域內(nèi)像素x的最終顏色值。其具體步驟如下：

步驟1 利用并行雙線性插值算法[16]對(duì)It和Is進(jìn)行降采樣，降采樣的尺度為s，本文中s=1/2，得到降采樣后的圖像。

步驟2 利用并行加速手段計(jì)算降采樣圖像對(duì)應(yīng)的顏色校正矢量rd(x)。該步驟又可分為如下兩步：

(1)根據(jù)式（3）計(jì)算克隆區(qū)域邊緣處前背景色彩差并保存；

(2)通過(guò)GPU并行加速技術(shù)[17]計(jì)算降采樣的克隆區(qū)域Pd內(nèi)部每個(gè)像素x對(duì)應(yīng)的顏色校正矢量rd(x)，具體算法如本節(jié)后面描述。

步驟3 利用并行雙線性插值算法[16]對(duì)rd(x)進(jìn)行升采樣，升采樣的尺度為1/s，得到初始分辨率下的顏色校正矢量r(x)。

步驟4 計(jì)算克隆區(qū)域內(nèi)每個(gè)像素x的最終顏色值。

對(duì)于步驟2的第2步，可將每個(gè)線程設(shè)置為利用式（5）計(jì)算每個(gè)像素x對(duì)應(yīng)的顏色校正矢量rd(x)，算法步驟如下：

輸入：區(qū)域的邊緣像素集合?Pd，區(qū)域內(nèi)部像素集合Pdin，區(qū)域邊緣前背景色彩差集合diffd。

輸出：顏色校正矢量rd(x)。

（1）計(jì)算線程ID號(hào)i；

（2）提取第i個(gè)區(qū)域內(nèi)部像素x=Pdin(i)；

（3）對(duì)于?Pd中的每個(gè)像素pj，利用式（11）計(jì)算wj并保存；

（4）根據(jù)式（1）計(jì)算x對(duì)應(yīng)的均值坐標(biāo)并保存；

（5）根據(jù)式（4）計(jì)算顏色校正矢量rd(x)。

綜合上述算法描述，其偽代碼如下。

輸入：源圖像Is、目標(biāo)圖像It、克隆區(qū)域內(nèi)部像素掩模圖像Pin

輸出：克隆圖像Ic

Isd=downsample(Is,s) #利用文獻(xiàn)[16]算法對(duì)Is進(jìn)行并行降采樣，降采樣的尺度為s

Itd=downsample(It,s) #利用文獻(xiàn)[16]算法對(duì)It進(jìn)行并行降采樣，降采樣的尺度為s

Pind=downsample(Pin,s) #利用文獻(xiàn)[16]算法對(duì)Pin進(jìn)行并行降采樣，降采樣的尺度為s

for i=1 to md

diffi=Itd(pi)-Itd(pi) #根據(jù)式（3）計(jì)算降采樣后克隆區(qū)域邊緣處前背景色彩差并保存

end for

parallel for i=1 to nd#對(duì)每個(gè)像素并行處理

x=Pdin(i) #提取第i個(gè)克隆區(qū)域內(nèi)部像素

sum_w=0

for j=1 to md

sum_w=sum_w+wj

end for

rd(x)=0 #初始化為零向量

for j=1 to md

rd(x)=rd(x)+λj(x)?diffj#根據(jù)式（4）計(jì)算顏色校正矢量rd(x)

end for

end parallel for

r=upsample(rd,1/s) #利用文獻(xiàn)[16]算法對(duì)rd進(jìn)行并行升采樣，升采樣的尺度為1/s。

parallel for i=1 to n #對(duì)每個(gè)像素并行處理。

x=Pin(i) #提取第i個(gè)克隆區(qū)域內(nèi)部像素。

Ic(x)=Is(x)+r(x) #利用式（5）計(jì)算克隆圖像Ic內(nèi)部像素的顏色值。

end parallel for

3 實(shí)驗(yàn)結(jié)果

3.1 定性分析

本文構(gòu)建了一個(gè)包含20組測(cè)試圖像的數(shù)據(jù)集，每組測(cè)試圖像包含源圖像、目標(biāo)圖像、手工標(biāo)記的源圖像中需要克隆的區(qū)域和手工標(biāo)記的目標(biāo)圖像克隆放置區(qū)域。

圖4 第1組測(cè)試圖像實(shí)驗(yàn)結(jié)果Fig.4 Results of test example 1

圖5 第2組測(cè)試圖像實(shí)驗(yàn)結(jié)果Fig.5 Results of test example 2

圖6 第3組測(cè)試圖像實(shí)驗(yàn)結(jié)果Fig.6 Results of test example 3

圖4 —7展示了4組測(cè)試圖像的例子，比較圖4—6中的（d），（e）以及（f）可知本文提出的算法和文獻(xiàn)[12]以及文獻(xiàn)[8]中的算法結(jié)果差別細(xì)微，肉眼幾乎難以察覺(jué)。這也從定性角度驗(yàn)證了本文改進(jìn)均值坐標(biāo)方法的可行性。

圖7展示了“變臉”特效，美國(guó)總統(tǒng)特朗普和俄羅斯總統(tǒng)普京的臉部區(qū)域互換后的效果自然，驗(yàn)證了本文算法可以實(shí)現(xiàn)逼真的視覺(jué)特效。

圖7 “變臉”特效Fig.7 “Face/off“effect

3.2 客觀評(píng)價(jià)

本節(jié)以文獻(xiàn)[8]合成的克隆區(qū)域圖像為基準(zhǔn)，將本文提出算法合成的克隆區(qū)域圖像與其進(jìn)行比較，計(jì)算顏色誤差。圖8分別顯示了第1組和第3組測(cè)試圖像中的克隆區(qū)域顏色誤差分布圖像。在計(jì)算下述圖像中每個(gè)像素的誤差值時(shí)采用如下方式：用本文提出算法和文獻(xiàn)[8]合成算法計(jì)算每個(gè)像素處的顏色誤差，該顏色誤差的取值為R,G,B三個(gè)分量中誤差絕對(duì)值的最大值（每個(gè)像素三通道亮度級(jí)范圍是0～255）。本文還統(tǒng)計(jì)了20組測(cè)試圖像中克隆區(qū)域的平均顏色誤差值分布統(tǒng)計(jì)直方圖，結(jié)果如圖9所示。

從圖8,9可以看到，克隆區(qū)域內(nèi)大部分像素和文獻(xiàn)[8]算法的顏色誤差在2個(gè)亮度級(jí)以內(nèi)，誤差在4個(gè)亮度級(jí)以上的像素占比在0.9%以內(nèi)。同時(shí)還計(jì)算了本文算法合成結(jié)果相對(duì)于文獻(xiàn)[8]合成算法在克隆區(qū)域內(nèi)的峰值信噪比(Peak signal to noise ratio,PSNR)值[18]，結(jié)果如表1所示。從表1中的統(tǒng)計(jì)結(jié)果可知，本文方法克隆結(jié)果和文獻(xiàn)[8]克隆結(jié)果極為相似，這也從定量角度印證了3.1節(jié)中的定性分析結(jié)果。

圖8 克隆區(qū)域內(nèi)部的顏色誤差分布圖像Fig.8 Color error distribution images in the cloned region

圖9 克隆區(qū)域內(nèi)部平均顏色誤差值分布統(tǒng)計(jì)直方圖Fig.9 Color error distribution histogram in the cloned region

表1 20幅測(cè)試圖像中克隆區(qū)域的PSNR值Tab.1 PSNR in cloned regions of twenty test images d B

3.3 主觀評(píng)價(jià)

為了對(duì)比文獻(xiàn)[8]中算法與本文算法的主觀視覺(jué)效果，選取了20名被試者對(duì)20組測(cè)試圖像分別用兩種算法得到的結(jié)果進(jìn)行評(píng)分，評(píng)分范圍是1～10分。20名被試者男女各半，年齡范圍是19～40周歲，涵蓋了本科生、研究生以及學(xué)校教師，并且都與本文項(xiàng)目無(wú)關(guān)。

實(shí)驗(yàn)中每次在計(jì)算機(jī)屏幕上左右分別顯示一組測(cè)試圖在文獻(xiàn)[8]中算法與本文算法的結(jié)果。為了消除被試者打分的傾向性，在每組測(cè)試結(jié)果顯示過(guò)程中隨機(jī)設(shè)定兩種算法結(jié)果的左右顯示位置。被試者分別對(duì)左圖和右圖的主觀結(jié)果進(jìn)行打分。

實(shí)驗(yàn)結(jié)果表明14人對(duì)20幅測(cè)試圖像中兩種算法的結(jié)果打分完全相同，也就是說(shuō)有14人主觀評(píng)價(jià)認(rèn)為兩種方法克隆圖像的效果完全一致，另外6人的結(jié)果如表2所示。

由表2可知，6人中對(duì)兩種算法結(jié)果的評(píng)價(jià)分最大只相差1分，且兩種方法在20幅測(cè)試圖像中的平均得分非常接近，這也從一個(gè)側(cè)面表明文獻(xiàn)[8]中算法與本文算法的結(jié)果非常類似。

表2 20幅測(cè)試圖像中兩種算法主觀評(píng)分結(jié)果比較Tab.2 Comparisons of subjective scorins of two algorithms for twenty test images

3.4 降采樣尺度s的設(shè)定

在2.2節(jié)中，本文算法需要確定一個(gè)超參數(shù)降采樣尺度s，為此本節(jié)實(shí)驗(yàn)選擇了不同的 s值，分別為 1，1/2，1/4，1/8和1/16，對(duì)每組測(cè)試圖像分別獲得5張不同的克隆圖像結(jié)果。與3.2節(jié)類似，計(jì)算并比較了20組測(cè)試圖像在不同s值下的平均PSNR均值，結(jié)果如圖10所示。

由圖10可知當(dāng)s取1/2時(shí)，PSNR均值仍在45 d B以上，這與不進(jìn)行降采樣（即s=1）的結(jié)果接近。但當(dāng)s取1/4及以上時(shí)，PSNR均值有大幅衰減，已經(jīng)影響到主觀的評(píng)價(jià)結(jié)果。綜合考慮圖像克隆效果與運(yùn)算復(fù)雜度，本文中所有實(shí)驗(yàn)均取s=1/2。

3.5 執(zhí)行時(shí)間分析

實(shí)驗(yàn)平臺(tái)配置為Intel 3.4 GHz i7-4770 CPU，顯卡為NVidia Geforce GTX 960，內(nèi)存為8 GB。本節(jié)中比較了文獻(xiàn)[12]、文獻(xiàn)[8]方法和本文提出算法的執(zhí)行時(shí)間。由于文獻(xiàn)[8,12]并未開(kāi)源其代碼，因此本文實(shí)現(xiàn)了其算法。所有算法均用C++實(shí)現(xiàn)，其中GPU并行加速部分代碼利用CUDA實(shí)現(xiàn)。

圖11展示了平均的單次式（2）執(zhí)行時(shí)間和本文簡(jiǎn)化后的單次式（11）在CPU上執(zhí)行時(shí)間的對(duì)比。由圖11可見(jiàn)，本文簡(jiǎn)化后的式（11）執(zhí)行時(shí)間約為3.5 ns，從而達(dá)到了約30倍的速度提升，證明了本文算法對(duì)于簡(jiǎn)化均值坐標(biāo)權(quán)重計(jì)算的有效性。

表3展示了不同圖像克隆區(qū)域尺寸下本文算法運(yùn)行時(shí)間和文獻(xiàn)[8]以及文獻(xiàn)[12]算法之間的比較。表中第3列和第4列分別為文獻(xiàn)[12]和文獻(xiàn)[8]算法實(shí)現(xiàn)圖像克隆完整流程所需的時(shí)間，其中括號(hào)內(nèi)的數(shù)字為整個(gè)流程中預(yù)處理算法的耗時(shí)，本文算法提出的算法無(wú)需任何預(yù)處理步驟。由表3可見(jiàn)本文方法實(shí)現(xiàn)了對(duì)100萬(wàn)像素的圖像區(qū)域的實(shí)時(shí)克隆，即使當(dāng)克隆區(qū)域增大至400萬(wàn)像素的高分辨率時(shí)仍能達(dá)到5幀/s左右的速度。

圖10 不同s值時(shí)的PSNR均值比較Fig.10 Comparison of average PSNR un?der different values of s

圖11 式（2）和式（11）計(jì)算執(zhí)行時(shí)間對(duì)比Fig.11 Comparisons of execution time for Eq.（2）and Eq.（11）

表3 不同算法的運(yùn)算執(zhí)行時(shí)間結(jié)果比較Tab.3 Compar ison of execution time for differ ent algorithms

4 結(jié)束語(yǔ)

本文分析了傳統(tǒng)基于均值坐標(biāo)的圖像克隆算法的運(yùn)算瓶頸，通過(guò)提出一種簡(jiǎn)化的均值坐標(biāo)計(jì)算方案在無(wú)需任何預(yù)處理步驟的前提下大幅降低了均值坐標(biāo)的運(yùn)算復(fù)雜度，并進(jìn)一步利用多尺度GPU并行加速方案實(shí)現(xiàn)了對(duì)100萬(wàn)像素圖像區(qū)域的實(shí)時(shí)克隆?？陀^和主觀實(shí)驗(yàn)結(jié)果表明本文算法在克隆結(jié)果與文獻(xiàn)[8]中方法結(jié)果差別細(xì)微的前提下可以大幅提升高分辨率圖像的克隆效率。

附錄A 式（8）近似可行性的驗(yàn)證

由于pi和pi-1為兩個(gè)相鄰像素，不失一般性，假設(shè)在圖3中三角形兩邊長(zhǎng)相等,即||pi-x||=||pi-1-x||=a。又由于||pi-pi-1||=1，根據(jù)余弦定理可得

因此，對(duì)式（8）用式（9）進(jìn)行近似的相對(duì)誤差為

圖A 1顯示了相對(duì)誤差值e和三角形邊長(zhǎng)a之間的關(guān)系。

圖A 1 相對(duì)誤差值e和三角形邊長(zhǎng)a之間的關(guān)系
Fig.A 1 Relation between relative errors e with the triangle edge length a

由圖A 1可知，當(dāng)區(qū)域P內(nèi)的像素x與像素pi和pi-1之間距離在3個(gè)像素以上時(shí)，上述近似的誤差已經(jīng)低于0.5%,由此驗(yàn)證了式（9）近似式（8）的可行性。