基于矩陣分解的圖形漸變避免自交算法研究

呂福起

（重慶財經學院軟件學院 重慶 401320）

1 引言

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

圖1 三角形出現萎縮變形序列

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

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

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

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

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

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

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

3 本文采用算法

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

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

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

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

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

step5：根據輸出的變形序列，是否達到預計效果，調整閾值，重新執行程序，得到合理變形序列圖形。

4 仿真實驗及分析

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

圖3 三角形變形序列

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

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

5 結語

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