As-rigid-as possible shape manipulation：優化1
- 2019 年 10 月 8 日
- 筆記
比如論文原作者Igarashi教授在09年發表的論文[1]說到，他們重新整理了論文，提出了新的方法，該方法相比05年論文[2]更清晰、更容易理解。作者在[1]中提出的方法有兩個改進，第一個改進是當用戶在圖形上交互時，不需要點擊圖形上三角化後的點，只需要點擊圖形內部任意坐標即可。第二個改進是使用「邊」為變形單位，提高了程式碼的簡潔性。最後作者將該方法應用到三維模型紋理展平，相比當時其他流行的紋理展平演算法同時兼具品質和性能。
我們直接看論文演算法。首先，演算法的處理單位從「三角形」變為「邊」。
在拖動控制點對圖形做變形時，如之前文章，我們期望變形後的圖形儘可能「接近」原始圖形。按照該論文思想，從數學上講，我們提出如下的優化方式。
其中 E 表示頂點序號為
的 「邊」的集合。
表示變形後的「邊」向量，
表示對應的「邊」向量。
表示用戶交互時點選的控制點坐標， C 表示控制點集合。把剛才提出的優化方式寫為數學公式如下。
其中，ω 表示權重變數，論文[1]中使用的 ω = 1000。
（註：論文[1]中的該公式是錯誤的，按照論文[1]後面的講述，ω應該在取模括弧內。）
這是一個線性的優化問題，論文[1]說可以把上述優化公式簡寫為
其中 v' 表示所有點的集合，
然後，我們對其做分解，下述表達形式是論文作者給我們推導的。
初看可能沒有那麼明顯。下面我來詳細說明。
首先，我們先確定點集 v' 的大小，係數矩陣 A 的大小，常數矩陣 b 的大小。
由點集中任一點都可表示為
那麼點集 v' 可表示為
拆分為兩個子矩陣，
則可以簡單表示 v' 為
就好像 v' 由兩個元素構成的向量一樣。
同理，b 也可以表示為這樣的形式。
最後表示 Av'-b
把 Av'-b 分解為兩個子矩陣，那麼可以把它看作由兩個元素構成的向量。如果對這個向量求模的平方，相當於把兩個元素分別取平方再求和。
對 Av'-b 取模的平方
那麼
很明顯可以看出來，只需要單獨看 x 分量或者 y 分量的優化方程即可知曉係數矩陣 A 和常數矩陣 b 的大概樣子。
我們再加一個理解過程。
再把原始的優化方程簡化一下。
我們換種方式寫一下。這兩個求和式子完全可以寫成 Av'-b 的形式。
以及
那麼可以寫成
終於回到論文作者推導的式子了。
我覺得寫到這，大家絕對能看出來，作者推導的這個式子是怎麼出來的。也知道這個式子里 A 中哪些元素是 1、-1、ω，常數向量 b 為什麼由邊向量和控制點構成，為什麼會這樣寫。我在這裡就不再贅述，如果還有問題，可以私信我。
最後，需要對這個最小二乘優化求偏導。
我們只需要通過解方程來求解變形後三角形的所有點的新坐標。
類似於[2]，論文[1]也用兩步變換來解決變形問題。
第一步，相似變換。
如果對於下圖這樣的邊
。
一般
都有四個鄰接點。如下。
但是當
是圖形的邊界，則鄰接點只有三個。
論文[1]里定義了一個旋轉變換
，
(註：T ⇦ Transformation, c ⇦ cos, s ⇦ sin)
這個旋轉變換的目的是讓這條邊
的鄰接點在變形時位置盡量不變。那麼用優化方程可以表示為
論文作者替我們做出了非常詳盡的推導過程。
最終結果表示，這個優化是一個線性的最小二乘優化。我們對
求偏導，並使偏導值為0，得到。
回到這篇文章最初的優化方程
我們只看其中的
現在就可以把優化方程寫成如下形式。
類似於如下形式。
可以看出來右邊的「邊」向量都是 0，也就反映了第一步演算法剛開始的對
的優化方程——對"點"的變換。求解這個優化方程有，
第二步，尺度適配。
使用第一步演算法的輸入為輸出，使用一個旋轉變換，類似的。
在這一步不同的是，我們要對該變換做歸一化。
再看完整的優化方程。
其中，
的計算在第一步演算法結束後，用第一步的結果算出來的。所以，
相對於第二步演算法來說是常量。所以，這個優化方程是線性的最小二乘優化，可以寫成如下形式。
同樣的，按照 x 分量和 y 分量分開計算。
和第一步演算法類似，只不過右邊的"邊"向量用第一步的結果生成。
同樣的，求偏導得如下等式，我們解方程即可。
最後，我們再完整的看一下實現細節。[1]和[2]相似，同樣有很多矩陣是可以預計算的。看一下這兩步的優化方程，
由於 A₁ 和 A₂ 類似。我們只看 A₁。
A₁ 的上半部分可以由原始圖形的點集來表示。所以這一部分，在讀取模型的同時就可以把這部分預計算。
A₁ 的下半部分在用戶點擊控制點時實時生成，每個元素都是固定的 ω 值構成的。所以這一部分，在每點擊一次控制點時預計算。
而 b₁ 和 b₂ 是由控制點的坐標生成，這一部分是用戶拖拉控制點時實時變化生成的。
下一篇文章，我們將用C++程式碼實現。
引用
[1] Igarashi T , Igarashi Y . Implementing As-Rigid-As-Possible Shape Manipulation and Surface Flattening[J]. Journal of Graphics Gpu & Game Tools, 2009, 14(1):17-30.
[2] Igarashi T . As-rigid-as-possible shape manipulation[J]. ACM Trans. Graph. 2005, 24.
