呂福起

（重慶財經(jīng)學院軟件學院 重慶 401320）

1 引言

將源圖形和目標圖形按照某種對應(yīng)方法[1]并采用合理的插值方法[2]，實現(xiàn)從源圖形到目標圖形的自然、流暢的過渡為圖形漸變技術(shù)的核心內(nèi)容。圖形漸變技術(shù)在圖像融合、計算機動畫、礦體形變、計算機視覺等領(lǐng)域都有一定的應(yīng)用價值，特別是計算機動畫技術(shù)中實現(xiàn)中間幀能夠大幅提高工作效率。圖形的對應(yīng)問題和插值路徑問題問圖形漸變技術(shù)的兩大重要問題。關(guān)于圖形的對應(yīng)有基于物理模型的對應(yīng)方法[3]和基于幾何圖形的對應(yīng)方法[4]，物理的方法是通過對物體的做功，將伸縮變換、旋轉(zhuǎn)變換和平移變換三個重要指標，應(yīng)用到頂點對應(yīng)中去，找到合理的初始圖形到目標圖形的對應(yīng)方式。幾何的方法是通過建立相似度量函數(shù)，通過求解該函數(shù)的最有解來尋找最佳對應(yīng)，該過程可以是動態(tài)的。關(guān)于插值路徑的方法有兩大類，一類是通過邊角的插值算法[5]，另一類是同構(gòu)三角網(wǎng)格剖分算法，把圖形的插值問題轉(zhuǎn)化成通過三角網(wǎng)格同構(gòu)剖分后的漸變問題[6]。通過頂點對應(yīng)方法和邊角插值法容易實現(xiàn)，但是對應(yīng)和插值中難以保證單調(diào)一致性的變化，從而出現(xiàn)自交或萎縮現(xiàn)象，見圖1和圖2。

圖1 三角形出現(xiàn)萎縮變形序列

圖2 直立樹到偏向樹自交變形序列

2 幾何法圖形漸變序列算法及存在問題分析

幾何法圖形漸變序列的形成，主要是基于邊角的插值方法，通過插值初始圖形和目標圖形的邊角，通過計算機不斷繪制中間圖形，從而形成變形序列。但由于方法存在的缺陷，很難在圖形的對應(yīng)中找到最合適的對應(yīng)，在漸變中出現(xiàn)圖形局部扭曲，局部缺失，或局部變動異常，出現(xiàn)圖形漸變中的不自然、不光滑現(xiàn)象。

為解決圖形漸變序列中的不足，需盡可能使圖形簡單化，從而更容易處理。為達到此目的，一個常用的方法是將圖形進行分解成一個個三角形狀態(tài)，對三角形頂點進行插值，形成漸變序列。假設(shè)初始三角形P和目標三角形Q，三個頂點為，三角形P通過插值算法漸變到Q，中間形成三角形漸變圖形序列，為得到光滑自然的變形序列，不出現(xiàn)如上圖1和圖2中的劇烈收縮直到一個點或者翻轉(zhuǎn)的情況。

三角形通過頂點插值方法從P到Q，需滿足,其中矩陣A為仿射變換矩陣，目的讓P的圖形逐漸過渡到Q的圖形，L為平移變換矩陣，通過平移P逐步過渡到Q位置，圖形的形狀沒有變化。在時間t∈ [0,1]某一中間幀的三角形，可由得到。

為保證變形序列的形態(tài)，采用SVD分解法。SVD分解法是指把仿射變換矩陣A分解成三個矩陣,,U S V，即A USV= ，U和V為旋轉(zhuǎn)矩陣，S為縮放矩陣。矩陣A的分解如下：

對于中間變形序列t時刻所需構(gòu)建的三角形，對應(yīng)的仿射矩陣為，采用線性插值矩陣D，即,得到中間變形序列的矩陣。這種分解方法在計算量不太大的基礎(chǔ)上，實現(xiàn)了較理想的漸變效果。

3 本文采用算法

本文采用的方法是綜合應(yīng)用圖形漸變對應(yīng)算法[1]，邊角分解與重構(gòu)算法[7]并基于SVD分解算法[8]和邊角插值法避免自交算法[9]對實驗圖形序列形成光滑、自然、流暢的漸變算法綜合。具體步驟如下。

step1:對初始圖形IA和目標圖形IB采用動態(tài)規(guī)劃模型建立點的對應(yīng)，在圖像漸變序列過程中，始終保持最佳對應(yīng)狀態(tài)。

step2：采用邊角分解與重構(gòu)算法，將初始圖形進行三角分解，并將對應(yīng)的頂點進行采用SVD分解算法并進行插值。

step3：將插值后圖形采用邊角分解與重構(gòu)算法，進行重構(gòu)。

step4：采用邊角插值法避免自交算法，對圖形進行邊角的自交檢查，并根據(jù)設(shè)置的閾值ρ0大小，處理圖形變形序列。

step5：根據(jù)輸出的變形序列，是否達到預計效果，調(diào)整閾值，重新執(zhí)行程序，得到合理變形序列圖形。

4 仿真實驗及分析

算法采用VB6.0計算機程序語言編寫，運行電腦采用DELL筆記本電腦，酷睿i5處理器。通過上述算法得到圖3、圖4和圖5。圖3是文中圖1提到的三角形變形序列中出現(xiàn)的萎縮現(xiàn)象，通過優(yōu)化算法，萎縮現(xiàn)象得到很好地控制。圖4是長角羚羊到短角羚羊變形序列，圖形復雜，邊角細長，但算法中很好地避免了自交現(xiàn)象。圖5是圖2中提到的直立樹到偏向樹自交變形序列，文中算法對自交現(xiàn)象進行了干預，將自交點剔除，實現(xiàn)了無自交情況，并得到了較自然流暢的漸變序列圖形。

圖3 三角形變形序列

圖4 長角羚羊到短角羚羊變形序列

圖5 直立樹到偏向樹變形序列

5 結(jié)語

通過算法可以得到較理想的圖形漸變序列。該算法綜合應(yīng)用了常用算法，具有一定的實用價值。算法的實現(xiàn)上，需要人工干預，比如閾值的設(shè)置。如果得到的圖形不滿足需要，需重新設(shè)置合理的閾值。此外，算法在圖形的形態(tài)上有一定的要求，盡量讓初始圖形和目標圖形在對應(yīng)時有較高的相似度，因此在設(shè)計相似度量函數(shù)時，要綜合考慮。對于進行插值的圖形，盡量讓圖形在形態(tài)上有較高的相似度，初始圖形和目標圖形不要有交叉圖形，不然在初始階段，算法很難保證有理想的漸變效果。算法避免自交是舍棄了部分自交點的邊和角，難免有一定的不合理情況，這需要算法設(shè)計人員再考慮更有效地處理方案，比如可以考慮在自交舍棄處采用更光滑的曲線連接方式，如貝塞爾曲線。希望各位科研人員能夠在該算法的基礎(chǔ)上，提出更優(yōu)秀的算法，或彌補算法的不足，得到更合理有效地圖形漸變算法。