基于徑向基函數的圖像變形算法與系統研究

陳杰龍 胡翔

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

關鍵詞：圖像變形;無網格法;徑向基函數;交互系統

DOI：10. 11907/rjdk. 201380 開放科學（資源服務）標識碼（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 引言

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

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

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

1 徑向基函數變形算法

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

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

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

基于徑向基函數的圖像變形能夠實現對控制點的精確插值，于是式（1）的插值條件可以表述如下：

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

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

聯合求解該[2N+6]的線性方程可得到變形函數。

2 不同參數的徑向基函數變形行為

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

2.1 徑向基函數表示形式

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

其中，[r]表示其它點與基函數采樣中心之間的距離，[λ]為常數，需根據網格規模加以選擇。

2.2 采樣中心個數與位置

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

2.3 基函數采用的距離形式

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

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

3 基于徑向基函數的圖像變形系統

3.1 算法實現

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

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

[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] 聶烜，趙榮椿，張曉燕. 一種改進的基于徑向基函數圖像變形方法[J]. 計算機科學，2005， 32（4）：102-103.

[10] 韓旭里，莊陳堅，劉新儒.? 基于徑向基函數與B樣條的散亂數據擬合方法[J]. 計算技術與自動化，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.

（責任編輯：孫 娟）