基于徑向基函數(shù)的圖像變形算法與系統(tǒng)研究

陳杰龍 胡翔

摘 要：圖像變形技術(shù)可幫助用戶獲得新的圖像，其廣泛應(yīng)用于計算機圖形圖像領(lǐng)域，具有重要研究價值。基于無網(wǎng)格法的圖像變形采用線性混合的光滑基函數(shù)表示變形函數(shù)，往往具有天然光滑的性質(zhì)，其中徑向基函數(shù)是一種被廣泛采用、性能良好的光滑基函數(shù)。研究徑向基函數(shù)方法在不同參數(shù)下的變形行為，包括基函數(shù)采用的距離形式、采樣中心個數(shù)與位置，以及徑向基函數(shù)表示形式等。開發(fā)一個圖像變形系統(tǒng)，用戶可通過鼠標拖拽方式驅(qū)動圖像變形，用戶體驗良好。實驗結(jié)果表明，該變形效果光滑，且僅需2～6s即可完成變形和渲染?；趶较蚧瘮?shù)的圖像變形能獲得光滑效果，且選擇的參數(shù)將影響變形行為。

關(guān)鍵詞：圖像變形;無網(wǎng)格法;徑向基函數(shù);交互系統(tǒng)

DOI：10. 11907/rjdk. 201380 開放科學(xué)（資源服務(wù)）標識碼（OSID）：

中圖分類號：TP317.4 文獻標識碼：A 文章編號：1672-7800（2020）007-0227-05

Image Deformation Algorithm and System Based on Radial Basis Function

CHEN Jie-long1，HU Xiang2

（1. Fujian China Tobacco Industry Co.，Ltd.，Xiamen 361000，China;

2.School of Information， Zhejiang Sci-Tech University， Hangzhou 310018， China）

Abstract： Image deformation technology is used to help users obtain new images， and is widely used in computer graphics， and it has very important research value. The image deformation algorithms based on mesh-free method that use the linear mixed smooth basis function to express the deformation function， and they often have the feature of smoothness. The radial basis function is one kind of smooth basis functions， and it is widely used and has good properties. In this paper， we research the deformation behavior of the radial basis function method under the different parameters， including the distance form of the basis function， the number and position of the sampling centers， and the expression form of the radial basis function. In addition， in order to provide users a good interactive experience， we also develop an image deformation system which let users drive the image deformation by dragging the mouse. Experiment shows that the deformation results is smooth， and it only takes 2s ～ 6s to complete the deformation and rendering. Image deformation based on Radial Basis Function can obtain smooth deformation， and the selected parameters will affect the deformation behavior.

Key Words： image deformation; mesh-free method; radial basis function; interactive system

0 引言

圖像變形作為計算機圖形學(xué)的一個重要研究方向，受到越來越多研究者的青睞與關(guān)注。基于圖像變形算法，用戶要想獲得發(fā)生形變后的新圖像，可以對原圖像設(shè)置若干數(shù)量的控制點，通過改變控制點的位置使其發(fā)生變形。該技術(shù)隨著理論研究與應(yīng)用實踐的不斷深入，目前已廣泛應(yīng)用于形狀插值[1]、圖像編輯[2]、關(guān)鍵幀動畫[3]等領(lǐng)域。

無網(wǎng)格法是圖像變形中的一類重要方法，其變形函數(shù)通常采用線性混合的光滑基函數(shù)表示，使得變形具有天然光滑特性。早在20世紀90年代，Lee等[4]提出自由變形（Free-Form Deformation，F(xiàn)FD）方法，通過借助樣條函數(shù)以實現(xiàn)形狀變形。后來，誕生了諸如移動最小二乘法（Moving Least Squars， MLS）[5]、徑向基函數(shù)法（Radial Basis Function，RBF）[6]、線性混合蒙皮法（Linear Blending Skinning，LBS）[7]等一系列經(jīng)典無網(wǎng)格法。其中，徑向基函數(shù)法（RBF）是一種很常用的無網(wǎng)格法。Arad等[8]較早實現(xiàn)了基于RBF方法的圖像變形;聶烜等[9]提出一種改進的RBF變形方法，可以對多個控制點實現(xiàn)精確插值且變形效果平滑;韓旭里等[10]提出一種結(jié)合RBF函數(shù)的擬合方法，較好地解決了散亂數(shù)據(jù)插值和擬合不穩(wěn)定問題;Levi等[11]提出一種內(nèi)部RBF方法，通過保持內(nèi)部球體剛性以約束形狀變形，且采用測地距離作為基函數(shù)的距離形式，實現(xiàn)較為自然的變形。

以上方法均未針對不同參數(shù)下的徑向基函數(shù)變形行為進行綜合研究，這些對變形均會產(chǎn)生一定影響。為此，本文基于徑向基函數(shù)變形方法，著重比較不同參數(shù)下的變形行為及算法性能，包括基函數(shù)采用的距離形式、采樣中心個數(shù)與位置，以及徑向基函數(shù)的表示形式，彌補對變形參數(shù)選擇的不確定性。同時，開發(fā)一個圖像變形系統(tǒng)，用戶可通過鼠標拖拽方式驅(qū)動圖像發(fā)生變形，為用戶提供較好的交互式體驗環(huán)境。

1 徑向基函數(shù)變形算法

徑向基函數(shù)（RBF）是一種光滑性較好的基函數(shù)，常用于離散數(shù)據(jù)插值技術(shù)，它在概念上很容易理解，且算法實現(xiàn)較為方便。每個徑向基函數(shù)均具有對應(yīng)的采樣中心，以該中心為圓點，徑向基函數(shù)對沿著半徑方向的其它點呈現(xiàn)遞增或遞減變化。

為使得變形效果光滑，本文采用的變形函數(shù)由徑向基函數(shù)與一次多項式的線性混合組成，即：

其中，[？（r）]表示徑向基函數(shù)（[r=||u-ci||]），值域為[[0～∞]]，通常采用調(diào)和函數(shù)基，如常用的薄板樣條函數(shù)：[？（r）=r2lnr]，[u]是控制點，[C={ci∈R2×1}Ni=1]是基函數(shù)采樣中心點，[λi=（λ1i，λ2i）T∈R2×1]為基函數(shù)系數(shù)，即計算過程中需要求解的權(quán)值，[N]是基函數(shù)個數(shù)，[A]為[2×2]的仿射變換，[t]是平移量。

基于徑向基函數(shù)的圖像變形能夠?qū)崿F(xiàn)對控制點的精確插值，于是式（1）的插值條件可以表述如下：

由式（2）可以看出，該方程表示一個線性系統(tǒng)，需求解由權(quán)重[λk]組成的向量。于是，將式（2）表示的線性系統(tǒng)轉(zhuǎn)化為矩形形式進行求解，令[？i，k=？（ui-ck）]，最終將該線性系統(tǒng)轉(zhuǎn)化成如下形式：

在實際應(yīng)用中，通常將控制點集[c]設(shè)置為基函數(shù)的采樣中心集[p]，兩者重合，即[c=p]，由此可得到[2N]個線性方程：[f（p）=q]，聯(lián)合求解該[2N]的線性方程便可得到變形函數(shù)[f]。為使方程解唯一，需同時增加中心約束與正交約束：

聯(lián)合求解該[2N+6]的線性方程可得到變形函數(shù)。

2 不同參數(shù)的徑向基函數(shù)變形行為

徑向基函數(shù)變形能夠根據(jù)不同參數(shù)改變變形行為，為用戶提供更多交互控制，其變化形式主要有以下幾種。

2.1 徑向基函數(shù)表示形式

徑向基函數(shù)由一組徑向基線性組合而成，可以根據(jù)需要選擇不同的表示形式（式（1）中的[？（r）]）。選擇的基函數(shù)類型不同，產(chǎn)生的變形結(jié)果也不盡相同。幾種常用徑向基函數(shù)如下：①薄板樣條函數(shù)：[？（r）=r2lnr];②高斯函數(shù)：[？（r）=e-r2λ2];③Multiquadric函數(shù)：[？（r）=r2+λ2];④Inverse Multiquadric函數(shù)：[？（r）=1r2+λ2]。

其中，[r]表示其它點與基函數(shù)采樣中心之間的距離，[λ]為常數(shù)，需根據(jù)網(wǎng)格規(guī)模加以選擇。

2.2 采樣中心個數(shù)與位置

根據(jù)徑向基函數(shù)影響方式，基函數(shù)采樣中心個數(shù)與位置將直接影響圖像變形效果。對于具有骨架結(jié)構(gòu)的圖像，一般將基函數(shù)中心沿著骨架方向進行采樣，且采樣中心之間需要有一定間距，使得采樣中心在圖像上均勻分布。不同采樣中心個數(shù)與位置的基函數(shù)變形效果如圖1所示?？梢钥闯?，若圖像上的采樣中心較少且散亂（見圖1（a）），會導(dǎo)致不自然的變形效果（見圖1（b）），采用均勻分布的基函數(shù)采樣中心（見圖1（c））則能明顯改善變形效果（見圖1（d）），盡可能保持圖像局部形狀。其中，圖中的小圓點表示控制點，箭頭方向表示控制點移動方向。

2.3 基函數(shù)采用的距離形式

徑向基函數(shù)的影響方式與頂點距離基函數(shù)采樣中心距離有關(guān)。若采用傳統(tǒng)歐式距離作為基函數(shù)的距離度量，在求解具有骨架結(jié)構(gòu)的圖像時可能會造成不自然的變形結(jié)果。為此，本文引入測地距離作為基函數(shù)的距離度量。現(xiàn)有的測地距離求解算法有迪杰斯特拉算法、弗洛伊德算法，以及一些改進方法[12-14]。其中，由Crane等[14]提出的Heat Method（下文稱熱測地距離法）是一種利用熱運動方程計算測地距離的方法，該方法充分利用物理學(xué)上的熱擴散原理，將測地線類比于熱傳播線，易于理解和計算。相比其它方法，熱測地距離法在計算上更為高效，且實現(xiàn)起來更加容易。借助帶邊界采樣點約束的Delaunay三角化對其內(nèi)部進行節(jié)點均勻分布的網(wǎng)格剖分[15]，根據(jù)網(wǎng)格的內(nèi)部結(jié)構(gòu)計算出測地距離。最后，將變形后的網(wǎng)格結(jié)構(gòu)用紋理映射方式進行渲染，從而得到最終可視化效果。

使用Paraview軟件對計算出的歐式距離（見圖2（a））和測地距離（見圖2（b））進行可視化仿真。其中，熱源（基函數(shù)中心）位于深藍色部位，用熱測地距離法計算出所有頂點與該熱源的測地距離，顏色的漸進表示距離長短變化，紅色越深表示測地距離越長，藍色越深表示測地距離越短。可以看出，圖像中人物的兩只手在歐式距離上相隔很近，但它們的測地距離則相對較遠，而這取決于圖像中點與點之間的位置關(guān)系（彩圖掃描OSID碼可見）。

3 基于徑向基函數(shù)的圖像變形系統(tǒng)

3.1 算法實現(xiàn)

本文算法在Intel Pentium G4600 3.6GHz雙核CPU、16GB內(nèi)存的筆記本上基于C++語言實現(xiàn)，并運行于64位版本的Visual Studio 2017開發(fā)環(huán)境下，其中借助Eigen庫實現(xiàn)矩陣存儲和運算[16]，并采用CGAL庫計算網(wǎng)格上的測地距離[17]。

基于徑向基函數(shù)的圖像變形算法需根據(jù)設(shè)置的控制點和采樣中心進行求解，其中采樣中心個數(shù)和位置對基函數(shù)的變形行為會產(chǎn)生一定影響。本文利用LDLT分解法[16]求解徑向基函數(shù)插值，得到權(quán)重向量;在進行測地距離計算時，利用Triangulation庫[18]對形狀內(nèi)部進行節(jié)點均勻分布的Delaunay三角剖分，并根據(jù)標定的熱源位置，計算出所有點測地距離。對圖像進行基于徑向基函數(shù)的變形算法步驟如下：

[3] SHEN Y，MA L，LIU H. An MLS-based cartoon deformation[J].? The Visual Computer， 2010， 26（9）： 1229-1239.

[4] LEE S Y，CHWA K Y， SHIN S Y. Image metamorphosis using snakes and free-form deformations[C].? Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM Press， 1995： 439-448.

[5] SCHAEFER S，MCPHAIL T，WARREN J. Image deformation using moving least squares[J].? ACM Transactions on Graphics，2006，25（3）： 533-540.

[6] BUHMANN M D. Radial basis functions： theory and implementations[M]. Cambridge：Cambridge University Press，2003.

[7] JACOBSON A， BARAN I， POPOVIC J，et al. Bounded biharmonic weights for real-time deformation[J].? ACM Transactions on Graphics， 2011， 30（4）：78.

[8] ARAD N， DYN N， REISFELD D， et al. Image warping by radial basis functions： application to facial expressions[J].? CVGIP： Graphical Models and Image Processing， 1994， 56（2）： 161-172.

[9] 聶烜，趙榮椿，張曉燕. 一種改進的基于徑向基函數(shù)圖像變形方法[J]. 計算機科學(xué)，2005， 32（4）：102-103.

[10] 韓旭里，莊陳堅，劉新儒.? 基于徑向基函數(shù)與B樣條的散亂數(shù)據(jù)擬合方法[J]. 計算技術(shù)與自動化，2007，26（1）：65-67.

[11] LEVI Z，LEVIN D. Shape deformation via interior RBF[J]. IEEE Transactions on Visualization and Computer Graphics，2014，20（7）：1062-1075.

[12] HASSOUNA M S， FARAG A A. Multistencils fast marching methods： a highly accurate solution to the eikonal equation on cartesian domains[J].? IEEE Transactions on Pattern Analysis and Machine Intelligence， 2007，29（9）：1563-1574.

[13] RUSTAMOV R M，LIPMAN Y， FUNKHOUSER T. Interior distance using barycentric coordinates[J].? Proceedings of the Symposium on Geometry Processing （SGP）.? Eurographics， 2009.

[14] CRANE K，WEISCHEDEL C，WARDETZKY M. Geodesics in heat： a new approach to computing distance based on heat flow[J].? ACM Transactions on Graphics， 2013， 32（5）： 13-15.

[15] SHEEWCHUK J R. Triangle： engineering a 2D quality mesh generator and delaunay triangulator[C]. Heidelberg：Proceedings of Workshop on Applied Computational Geometry，1996： 203-222.

[16] GAEL G. Eigen 3.0-beta1[EB/OL].[2010-7-5].http：//eigen.tuxfamily.org.

[17] DMITRY A. CGAL 4.14[EB/OL].[2019-3-20].https：//cgal.org.

[18] JONATHAN R S. Triangle 1.6[EB/OL].[2005-7-78].http：//www.cs.cmu.edu/～quake/triangle.html.

[19] GIORGIO M. GLFW 3.0[EB/OL].[2013-6-17].https：//www.glfw.org.

[20] OMAR C. Dear-imgui 1.7[EB/OL].[2019-7-15].https：//discourse.dearimgui.org.

[21] KHRONOS GROUP. OpenGL 4.6[EB/OL].[2017-7-31].https：//www.opengl.org.

[22] BUHMANN M. A new class of radial basis functions with compact support[J]. Mathematics of Computation，2001，70（233）：307-318.

（責(zé)任編輯：孫 娟）