摘 要：morphing，一般翻譯為圖形漸變，是指將一給定的初始圖形在視覺上光滑、連續(xù)、自然的變化到目標圖形。本文討論一種基于“類人感知”的二維多邊形漸變中頂點對應問題的解決方法，并用java語言對其進行實現(xiàn)測試。

關(guān)鍵詞：morphing；多邊形；java

中圖分類號：TP391.41

圖形漸變（morphing），顧名思義就是采用某種方法使初始物體在視覺上連續(xù)、光滑變化到目標物體。隨著計算機技術(shù)的迅速發(fā)展，圖形漸變技術(shù)廣泛應用于計算機圖形學、工業(yè)產(chǎn)品設(shè)計、計算機動畫、虛擬現(xiàn)實、影視特技制作等領(lǐng)域。二維物體漸變是物體漸變的重要組成部分，不僅在關(guān)鍵幀動畫、模式識別，而且在曲面重建和三維造型中也有重要意義。

二維物體漸變的研究包含兩個問題：頂點對應問題和頂點插值路徑問題。本文所采用的算法是由劉立剛教授等在2004年研發(fā)出來的算法，在該方法中，對于在源圖形和目標圖形中尋找頂點對應關(guān)系的這個過程主要著眼于人類對多邊形形狀改變的感知方法，并采用java語言進行具體實現(xiàn)。

1 算法分析

本文所討論的方法可粗略的分為以下5個步驟：（1）把初始圖形S和目標圖形T定義為二維多邊形；（2）對初始圖形S和目標圖形T進行特征點檢測；（3）解決頂點對應問題；（4）解決頂點路徑問題；（5）產(chǎn)生漸變序列并顯示出來。

1.1 多邊形的定義

在本文中，二維形狀被定義為一個在二維水平面上的曲線，該曲線不可自交，可以是閉合的，也可以是非閉合的。多邊形是圖形的一個特例，多邊形中用來連接頂點之間的函數(shù)被限制為直線，頂點的集合稱為頂點集，頂點用Pi，表示，連接兩個頂點之間的線段叫做邊。

1.2 特征點的定義

在本文中，特征點描述的是在二維平面上的一個點。在特征點匹配的過程中，除了x和y坐標以外，還有一些其他的重要屬性。每個特征點都是某一個圖形的成員，每個圖形都能夠用隸屬于它的特征點依次的表示出來，當然會損失一些圖像信息。與平均分布采樣點不同，特征點在圖形上的分布并不是均勻的。在人類觀察者對于的圖形的感知中，具有高曲度的尖角點更容易引起注意，因此本文中的“類人感知”，就是獲取高曲度的頂點作為特征點。

對于普通的二維圖形，特征點需要通過采樣，通過特征點檢測函數(shù)進行判斷，來確保特征點采選的準確性。由于本文討論的對象是二維多邊形，因此，可以默認所有的特征點均出自頂點集，無須進行采樣只需判斷。

1.3 特征點的對應

當初始圖形和目標圖形的特征點都已經(jīng)確定，就要對這些特征點進行一一對應之后再morphing，為此我們需要一個對特征點進行判斷的準則。為此我們定義如下一些術(shù)語和標準：

1.3.1 領(lǐng)域（Region of Support）

1.3.2 特征變分

特征點Pi的特征變分定義為：

，其中，λN為垂直特征值，λT為切線特征值，如果Pi是凸特征點，則ξ=1，如果Pi是凹特征點，則ξ=-1。特征變分產(chǎn)生的是ROSh（Pi）中的點相對于 的位置信息。如果Pi附近區(qū)域的圖形相對扁平，臨近點都落在Pi的切線方向。σ（Pi）的值在閉區(qū)間[-1，1]中，如果σ（Pi）的值逼近1，說明點Pi是在一個尖角的端點上；如果σ（Pi）逼近0，則點Pi周圍的圖形比較平緩。

1.3.3 特征側(cè)面變分

特征側(cè)面變分定義為：

其中ROL（Pi）和ROR（Pi）分別是點 的左領(lǐng)域和右領(lǐng)域。對于每一個ROL（Pi）和ROR（Pi），都需要計算其協(xié)方差，對于ROL（Pi）產(chǎn)生特征值λNL和λTL，ROR（Pi）產(chǎn)生特征值λNR和λTR。使用這幾個特征值來定義σ（ROL（Pi））和σ（ROR（Pi）），定義 ， 。特征方面變分τ（Pi）用于獲取點Pi的左鄰域以及右鄰域的外觀信息。同特征變分相似，σ（ROL（Pi））和σ（ROR（Pi））的定義域是[0，1]（這里不用參數(shù)ξ以防出現(xiàn)負值）。如果 的值靠近0則說明區(qū)域圖像比較平緩，如果τ（Pi）的值較高就表示ROL或者ROR彎曲程度較大。

1.3.4 特征規(guī)模

特征規(guī)模定義為：

其中ρL（Pi）和ρR（Pi）指的是ROL（Pi）和ROR（Pi）相對于圖形周長的長度。ρ（Pi）實際上是一個指針，指示的是它在整個圖形中的重要性：如果ρ（Pi）產(chǎn)生的值非常小，則說明Pi的鄰域在整個圖形中只是一個比較小的部分，甚至不能給人類觀察者以明顯的印象（如果τ（Pi）和ρ（Pi）都很高的話，Pi的鄰域可能也不明顯）。如果ρ（Pi）獲得了一個很高的值，表明Pi的鄰域是整個圖形的重要部分，將會給觀察者一個很強的印象。

根據(jù)以上的定義和參數(shù)，我們可以用S={Si|i=0，1，…m}來描述初始圖形，用T={Tj|j=0，1，…n}來描述目標圖形。當S0=Sm，T0=Tn的時候分別表示源圖形和目標圖形閉合。每一對特征點Si和Tj的相似度值定義為

如果初始圖形和目標圖形的特征點數(shù)不相等，就不能夠做到初始圖形和目標圖形的特征點一一對應，此時就要舍棄掉不適合產(chǎn)生morphing序列的特征點。而且在尋找良好的morphing序列的過程中，也需要刪除一些不適合進行對應的特征點。為了判定刪除掉特征點對整個morphing序列的影響，我們引入一個價值函數(shù)。

通過計算如果Pi的拋棄代價非常小的話，那么說明Pi在整個圖形中的地位不是很重要。

相似度價值函數(shù)不僅可以用來衡量兩個特征點Si和Tj之間的相似度，而且可以為對應初始圖形S和目標圖形T整體賦值。在這里對應關(guān)系的意思就是從特征點S到特征點T的映射。如果我們把一個映射J看成：{Si}→{Tj}，就可以為S和T之間的映射建立一個相似度價值函數(shù)：

，

因為初始圖形S中有m個不同的特征點，根據(jù)相似度函數(shù)的特性，我們假設(shè)映射J是對應問題的最優(yōu)解決方案，只要使SimCosts（S，T，J）的結(jié)果最小即可。

2 程序設(shè)計

本程序采用java語言來實現(xiàn)。

2.1 類層次結(jié)構(gòu)

整個程序根據(jù)算法的需要主要封裝成7個包及40余個類，這7個包的名稱分別為shapes，emath，featureDetection，tools，morphing，control和application。

其中，shape包只是用來處理多邊形；emath包中包含的是計算算法中比較復雜的數(shù)學屬性的工具，包括有協(xié)方差，特征向量，特征值和頂點內(nèi)角的二分線等函數(shù)；featureDetection用來實現(xiàn)多邊形中的特征點檢測；tools包中的類都是其他類用作工具；controls包中大多數(shù)的類都是用來實現(xiàn)java.awt.event包中定義的ActionListener接口的，它們主要用來處理用戶和應用程序之間的交互，同時也可以對其他的類進行擴展；morph包是用來處理創(chuàng)建漸變序列的；Application則是用來構(gòu)建程序GUI的。

2.2 檢測特征點

前文中，我們討論了有關(guān)于特征點的檢測的問題，本文中討論的是二維圖形的特例多邊形，因此可以將算法進行簡化。在多邊形中，只有頂點可以作為特征點的候選，因此可以省略采樣這個步驟。同樣的，對于各種不同的三角形可以忽略本過程，因為三角形的構(gòu)造直接就滿足特征點對應的需求。

2.3 頂點對應問題

本文采用動態(tài)規(guī)劃的方法來解決頂點對應問題的最優(yōu)化。想要得到最優(yōu)的頂點對應組合，合理的做法是事先把拋棄代價和相似度值計算出來并存儲，然后用動態(tài)規(guī)劃的方法進行多次調(diào)用，規(guī)劃出最合理的頂點對應路徑。下面代碼中的函數(shù)calculateAllDeltaCosts（Polygon，Polygon，int）可以完成這項計算，參數(shù)skips制定了尋找動態(tài)規(guī)劃圖中的某一個結(jié)點的最佳前驅(qū)時，最多可以跳過的特征點的數(shù)目。整型變量dim1和dim2分別表示源圖形和目標圖形的特征點數(shù)目。接下來把所有的數(shù)據(jù)都保存在一個四維數(shù)組delta_field中，嵌套的for結(jié)構(gòu)就是把各個變量的值一次的放到對應的數(shù)據(jù)域中去。源圖形中的特征點 和目標圖形中的特征點 的對應關(guān)系存儲在deltaCosts[i][j][][]中。

3 結(jié)論和展望

3.1 測試結(jié)果

3.1.1 特征點檢測對漸變序列的影響

3.1.2 跳點數(shù)（skip）對漸變序列的影響

在動態(tài)規(guī)劃圖中允許最大的跳點數(shù)目對漸變序列有著巨大的影響，圖3對此進行了展示。所有的漸變序列除了最大跳點數(shù)以外的所有參數(shù)均采用相同的，圖a）中的跳點數(shù)設(shè)為0，這就導致了多邊形各部分的對應頂點移動距離都很大，同時由于使用的是直線路徑，非常容易產(chǎn)生自交。圖b）跳步數(shù)選擇為1，成功的避免了產(chǎn)生自交，看上去比圖a）效果要好很多，但在那個的上部依舊還是存在失真。圖c）中，這些沒必要的移動就完全的消失了，圖c）的最大跳步數(shù)設(shè)為2，漸變序列的結(jié)果要比圖a）和b）良好。

3.2 結(jié)論：特征點檢測這個步驟不僅能優(yōu)化算法，同時也能得到較好的漸變序列。適當?shù)脑O(shè)置最大的跳點數(shù)目可以避免漸變序列圖形產(chǎn)生自交，從而產(chǎn)生更優(yōu)的漸變序列。

參考文獻：

[1]Liu，Ligang，Wang，Guopu，Zhang，Bo，Guo，Baining，Shum，Heung-Yeung.Perceptually Based Approach for Planar Shape Mor-phing，2004：111-120.

[2]范自柱.一種圖像morphing效果的客觀度量方法[J].計算機工程與應用，2006（31）：37-39.

[3]賴志豪，康寶生.二維物體變形技術(shù)現(xiàn)狀與發(fā)展[J].計算機技術(shù)與發(fā)展，2007（10）：120-121.

作者簡介：袁媛（1981-），女，遼寧撫順人，講師，碩士，研究方向：計算機。

作者單位：撫順職業(yè)技術(shù)學院，遼寧撫順 113122