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

呂福起

（重慶財(cái)經(jīng)學(xué)院軟件學(xué)院 重慶 401320）

1 引言

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

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

圖2 直立樹(shù)到偏向樹(shù)自交變形序列

2 幾何法圖形漸變序列算法及存在問(wèn)題分析

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

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

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

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

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

3 本文采用算法

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)及分析

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

圖3 三角形變形序列

圖4 長(zhǎng)角羚羊到短角羚羊變形序列

圖5 直立樹(shù)到偏向樹(shù)變形序列

5 結(jié)語(yǔ)

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