Assignment

楔子

函數是「對應」與「變換」兩種概念的結合。對應:兩堆東西一一連結。變換:一個東西變成另一個東西。

接下來進一步討論「指派」與「對齊」。指派:找到對應關係。對齊:找到變換函數。

Assignment(Correspondence)

「指派」。已知甲堆數據、乙堆數據,求得對應方式。

指派之後,進一步求得距離總和,作為兩堆數據的差異多寡。

隨隨便便就能想到一大堆對應方式。佗一个較好?我曷知。

一、甲堆到乙堆,距離最近的那兩筆數據。
二、窮舉甲堆到乙堆的所有兩兩配對。
三、窮舉甲堆每一筆數據,分別找到乙堆之中距離最近的那筆數據。
四、甲乙對調。
五、三四相加。
六、三四聯集。
七、三四交集。
八、距離最近改為距離前K短。

進階問題Optimal Transport:採用特殊的距離函數。

One-to-one Assignment(Bipartite Matching)

一配一。可獨身,不重婚。

當兩堆數據一樣多,稱作Bijective Assignment或Perfect Bipartite Matching。

請見本站文件「Bipartite Matching」。

Nearest Neighbor Assignment

窮舉甲堆每一筆數據,分別找到乙堆之中距離最近的那筆數據。

尋找最近點,簡易的方式是窮舉法,進階的方式是乙堆套用分割區域的資料結構,諸如Uniform Grid、KD-Tree。

請見本站文件「Region」。

Alignment

Alignment

「對齊」。已知甲堆數據、乙堆數據,求得變換函數。

變換函數變化無窮,總是可以對齊數據,缺乏討論意義。只好增加限制,採用特定的變換函數。

採用特定的變換函數,強硬地對齊數據,通常無法完美密合。只好採用最佳化的套路:甲堆實施變換、乙堆,令兩者差異盡量小。

為了更密合,有人採取對稱方式:甲堆正向變換與乙堆的差異、乙堆反向變換與甲堆的差異,正向反向一併計入。

為了衡量差異,必須指定指派類型、誤差類型。大家習慣採用最佳一對一指派、距離平方總和。

為了節省計算時間,甚至預定指派結果。大家習慣讓兩堆數據一樣多,依照索引值一一對應。

進階問題Optimal Registration:多堆數據的組裝。

Affine Alignment

兩堆數據一樣多,依照索引值一一對應。

solve Apᵢ + b = p̕ᵢ
minimize sum ‖p̕ᵢ - (Apᵢ + b)‖²
minimize ‖Y - (AX + B)‖F²
transformation matrix  A₃ₓ₃ = (Y - Ȳ) X⁺ = (Y - Ȳ) Xᵀ(XXᵀ)⁻¹
translation vector     b₃ₓ₁ = mean(p̕ᵢ - Apᵢ) = mean(p̕ᵢ) - A mean(pᵢ)

大家習慣在最初添加一個位移,調整甲堆數據。原本那個位移,移項至另一側,調整乙堆數據。仍是仿射變換。

優點:數學公式更漂亮,兩堆數據各自中心化。優點:縮小數值範圍,減少浮點數誤差,也避免浮點數溢位。缺點:計算步驟較多。

solve A(pᵢ - t) = (p̕ᵢ - t̕)
minimize sum ‖(p̕ᵢ - t̕) - A(pᵢ - t)‖²
minimize ‖(Y - T̕) - A(X - T)‖F²
transformation matrix  A₃ₓ₃ = (Y - Ȳ)(X - X̄)⁺ = Ỹ X̃⁺ = ỸX̃ᵀ(X̃X̃ᵀ)⁻¹
translation vector     t₃ₓ₁ = mean(pᵢ)
translation vector     t̕₃ₓ₁ = mean(p̕ᵢ)

一次迴歸是仿射對齊:甲堆是多維數據,乙堆是一維數據。

《Image Deformation Using Moving Least Squares》

Similar Alignment(Procrustes Analysis)

兩堆數據一樣多,依照索引值一一對應。

相似變換:旋轉、縮放、位移。大家習慣在最初添加一個位移。

solve sR(pᵢ - t) = (p̕ᵢ - t̕)
minimize sum ‖(p̕ᵢ - t̕) - sR(pᵢ - t)‖²
minimize ‖(Y - T̕) - sR(X - T)‖F²
covariance matrix  C₃ₓ₃ = (Y - Ȳ)(X - X̄)ᵀ = Ỹ X̃ᵀ = U Σ Vᵀ
rotation matrix    R₃ₓ₃ = U Vᵀ
scaling factor     s₁ₓ₁ = trace(Σ) / ‖X̃‖F² ≈ ‖Ỹ‖F / ‖X̃‖F
translation vector t₃ₓ₁ = mean(pᵢ)
translation vector t̕₃ₓ₁ = mean(p̕ᵢ)
http://perception.inrialpes.fr/people/Horaud/Courses/pdf/Horaud_3DS_6.pdf

證明請見本站文件「Orthogonal Procrustes Theorem」,其中A換成X、B換成Y。位移不影響最佳旋轉與最佳縮放,位移最後處理。

偵測鏡射:檢查旋轉矩陣的determinant,無鏡射det(R) = +1,有鏡射det(R) = -1。

去除鏡射:最小的奇異值變號。因為旋轉矩陣公式沒有納入奇異值,所以改成對應的奇異向量變號(左右擇一變號)。

《Estimating 3-D rigid body transformations: a comparison of four major algorithms》

Rigid Alignment

同前,倍率為1。

Principal Scaling Alignment【尚待確認】

特徵縮放變換:在互相垂直的方向上進行縮放?

x̕ = UΣVᵀx + t   (U and V are orthonormal, Σ is nonnegative diagonal)

數據X變數據Y,最近似特徵縮放變換是ỸX̃ᵀ?

minimize ‖(Y - T̕) - M(X - T)‖F²
principal scaling matrix M₃ₓ₃ = ỸX̃ᵀ = UΣVᵀ

YXᵀ可以解讀成先除以X、再乘以Y、得到比率Y/X。

此定理相當強,但是從未有人提到。靠你了。

Projective Alignment(Direct Linear Transformation)

兩堆數據一樣多,依照索引值一一對應。

位移併入變換矩陣。

歐氏幾何化:新添尺度、實施變換、隱藏尺度。

solve dehomogenize(P homogenize(pᵢ)) = p̕ᵢ
minimize sum ‖p̕ᵢ - dehomogenize(P homogenize(pᵢ))‖²
minimize ‖Y - dehomogenize(P homogenize(X))‖F²
solve dehomogenize(P homogenize(p)) = p̕     單筆數據

solve dehomogenize(P pₕ) = p̕

              [ —— v₁ —— ] [ x ]     [ x̕ ]
dehomogenize( [ —— v₂ —— ] [ y ] ) = [ y̕ ]
              [ —— v₃ —— ] [ 1 ]

              [ v₁∙pₕ ]     [ x̕ ]
dehomogenize( [ v₂∙pₕ ] ) = [ y̕ ]
              [ v₃∙pₕ ]

{ (v₁∙pₕ) / (v₃∙pₕ) = x̕
{ (v₂∙pₕ) / (v₃∙pₕ) = y̕

{ (v₁∙pₕ) = x̕ (v₃∙pₕ)
{ (v₂∙pₕ) = y̕ (v₃∙pₕ)

{ (v₁∙pₕ) - x̕ (v₃∙pₕ) = 0
{ (v₂∙pₕ) - y̕ (v₃∙pₕ) = 0

{ pₕᵀv₁ - x̕ pₕᵀv₃ = 0
{ pₕᵀv₂ - y̕ pₕᵀv₃ = 0

[ pₕᵀ 0   -x̕ pₕᵀ ] [v₁]
[ 0   pₕᵀ -y̕ pₕᵀ ] [v₂] = 0
                  [v₃]

[ p₁ₕᵀ 0    -x̕₁ p₁ₕᵀ ]
[ 0    p₁ₕᵀ -y̕₁ p₁ₕᵀ ] [v₁]
[ p₂ₕᵀ 0    -x̕₂ p₂ₕᵀ ] [v₂] = 0     多筆數據
[ 0    p₂ₕᵀ -y̕₂ p₂ₕᵀ ] [v₃]
[ :    :       :    ]
         A₂ₙₓ₉         v₉ₓ₁

solve Av = 0                            homogeneous linear equation

minimize ‖Av‖²  subject to ‖v‖² = 1     射影幾何不在乎倍率,
                                        令‖P‖F² = ‖v‖² = 1。
v = E₁ (AᵀA = EΛEᵀ)                     最小的特徵值的特徵向量

v = V₁ (A = UΣVᵀ)                       最小的奇異值的右奇異向量

奇異值分解A = UΣVᵀ,最小的奇異值的右奇異向量V₁,切斷並排得到P。

《As-Projective-As-Possible Image Stitching with Moving DLT》

Correlation Alignment(Principal Component Analysis)

兩堆數據不知道對應關係,甚至不一樣多。

兩堆數據各自求得主成分,然後對齊主成分。

變換過程:位移、旋轉、縮放、旋轉、位移。

covariance matrix     C₃ₓ₃ = (X - X̄)(X - X̄)ᵀ = X̃X̃ᵀ = EDEᵀ
covariance matrix     C̕₃ₓ₃ = (Y - Ȳ)(Y - Ȳ)ᵀ = ỸỸᵀ = E̕D̕E̕ᵀ
rotation matrix       R₃ₓ₃ = E⁻¹ = Eᵀ
rotation matrix       R̕₃ₓ₃ = E̕
scaling matrix        S₃ₓ₃ = sqrt(D⁻¹)
scaling matrix        S̕₃ₓ₃ = sqrt(D̕)
transformation matrix A₃ₓ₃ = E̕ sqrt(D̕ D⁻¹) Eᵀ
translation vector    t₃ₓ₁ = mean(pᵢ)
translation vector    t̕₃ₓ₁ = mean(p̕ᵢ)
data centering        X̃₃ₓ₃ = X - X̄ = X̃ = UΣVᵀ
data centering        Ỹ₃ₓ₃ = Y - Ȳ = Ỹ = U̕Σ̕V̕ᵀ
transformation matrix A₃ₓ₃ = U̕Σ̕ Σ⁻¹Uᵀ
translation vector    t₃ₓ₁ = mean(pᵢ)
translation vector    t̕₃ₓ₁ = mean(p̕ᵢ)
http://www.cs.tau.ac.il/~dcor/Graphics/cg-slides/svd_pca.pptx
http://www.cse.wustl.edu/~taoju/cse554/lectures/lect07_Alignment.pdf

兩種做法:有方位主成分、無方位主成分。

一、有方位主成分:兩堆數據各自求得共變異矩陣,實施特徵分解。兩邊的特徵向量,依照特徵值大小一一對應。

位移:數據中心的差距。旋轉:特徵向量的夾角。縮放:特徵值平方根的比例。

偵測鏡射:檢查旋轉矩陣的determinant,無鏡射det(R) = +1,有鏡射det(R) = -1。去除鏡射:最小的特徵值的特徵向量,變號顛倒方向,誤差增加最少。

亦得採用最小的奇異值的左奇異向量。三維的情況下,我不確定奇異值分解是否佔到便宜。

二、無方位主成分:主成分重新指定方位。二維有兩種方位,三維有四種方位。兩堆數據的主成分,分別窮舉所有方位,找到旋轉角度最小、也就是trace(R)最小的旋轉矩陣。

Inlier / Outlier

真實世界的數據並非完美,常有例外。

兩堆數據不一樣多,不知道對應關係。其中有些點是例外,不適合納入計算。

演算法(RANSAC)

一、甲堆隨機抓幾點,乙堆隨機抓幾點,點數一樣多,推定它們依序一一對應。
  換句話說,隨機的、限量的、雙射指派。
二、依照對應關係,實施對齊,求得對齊函數。
三、計算「甲堆套用函數」與「乙堆」的誤差大小。
四、重複上述步驟,取誤差最小者。

其實就是隨機窮舉法。

演算法(Iterative Closest Point)

一、初始化:
 甲、實施相關對齊(PCA),求得對齊函數。
 乙、甲堆套用函數。讓甲堆靠近乙堆。
二、重複此步驟,直到最近點不變為止:
 甲、實施最近鄰指派:甲堆每一點找到在乙堆的最近點。暫時無視乙堆其餘點。
 乙、依照對應關係,實施對齊,求得對齊函數。
 丙、甲堆套用函數。讓甲堆更靠近乙堆。
三、甲堆套用的所有函數,依序複合就是最理想的對齊函數。
 甲、多個仿射變換,複合之後,仍是仿射變換。
   相似變換、剛體變換、射影變換,亦復如是。
 乙、相關對齊得到仿射變換。
   亦可退化,得到相似變換、剛體變換。

其實就是最陡下降法。目前最好的方法。

照理來說,梯度下降法、模擬退火法應該也行。然而我沒見過。

Drawing

Drawing

「畫畫」。製造數據,盡量形成均勻造型。

兩種連接形式:

圖:可以討論點與邊。
網格:進一步形成三角剖分(二維)、四面體剖分(三維)。還可以討論面。

兩種連接形態:

點雲:沒有任何特色,隨便連。
表面:形成空間中的一層曲面。

相對距離盡量均勻(兩兩距離平方總和盡量小)

我們希望數據盡量集中、盡量不要四處散落。我們設計一個簡單的最佳化目標函數:兩兩距離平方總和盡量小。

根據Graph Laplacian Analysis,此最佳化目標亦是:相對距離盡量均勻。

min sum ‖pᵢ - pⱼ‖²
 p (i,j)

引入Adjacency Matrix,只考慮部分的兩兩距離。

引入非負權重,伸縮各個兩兩距離。權重越大,距離越短。

min sum wᵢⱼ ‖pᵢ - pⱼ‖²
 p (i,j)

引入Laplacian Matrix,改寫成二次型。

每個維度可以分開處理,分開最佳化。

min xᵀLx  +  min yᵀLy     where pᵢ = (xᵢ, yᵢ)
 x            y

最小值位於一次微分等於零的地方,改寫成一次方程組。

每個維度可以分開處理,分開求解。

solve Lx = 0   and   solve Ly = 0               (wᵢⱼ is symmetric)
solve (L+Lᵀ)x = 0   and   solve (L+Lᵀ)y = 0     (wᵢⱼ is non-symmetric)

無向圖:L是對稱、半正定、對角優勢矩陣。

有向圖:(L+Lᵀ)是對稱、半正定、對角優勢矩陣。

答案是所有點聚在一點、所有點皆相等,缺乏討論意義。大家習慣追加其他限制條件,後面小節逐一介紹。

位置必須固定

釘住某些點。挑選一些點,設定明確座標。

min sum ‖pᵢ - pⱼ‖²   subject to pₖ = cₖ for certain k
 p (i,j)

解的一部分變成了定值。撰寫數學式子的時候,重新排列維度,將定值排在一起,比較清爽。

    [ x₁ ]ᵀ[ — row₁ — ] [ x₁ ]          [ x₁ ]ᵀ[ — row₁ — ] [ x₁ ]
    [ x₂ ] [ — row₂ — ] [ x₂ ]          [ x₃ ] [ — row₃ — ] [ x₃ ]
min [ x₃ ] [ — row₃ — ] [ x₃ ] ---> min [ x₅ ] [ — row₅ — ] [ x₅ ]
    [ x₄ ] [ — row₄ — ] [ x₄ ]          [ x₂ ] [ — row₂ — ] [ x₂ ]
    [ x₅ ] [ — row₅ — ] [ x₅ ]          [ x₄ ] [ — row₄ — ] [ x₄ ]

      x₂ and x₄ are constant           lower variables are constant 

撰寫數學式子的時候,變數常數分別形成區塊,比較簡潔。

    [ x ]ᵀ[ L₀₀ | L₀₁ ] [ x ]               [ x₁ ]
min [---] [-----+-----] [---]     where x = [ x₃ ] , c = [ x₂ ]
    [ c ] [ L₁₀ | L₁₁ ] [ c ]               [ x₅ ]       [ x₄ ]

改寫成一次方程組。

min xᵀL₀₀x + xᵀL₀₁c + cᵀL₁₀x + cᵀL₁₁c               展開
solve (L₀₀ + L₀₀ᵀ)x + (L₀₁ + L₁₀ᵀ)c = 0             微分
solve (L₀₀ + L₀₀ᵀ)x = -(L₀₁ + L₁₀ᵀ)c                移項
solve L₀₀x = -L₀₁c                                  對稱矩陣。同除以二。
      [ (L₀₀ + L₀₀ᵀ) | (L₀₁ + L₁₀ᵀ) ] [ x ]   [ 0 ]
solve [--------------+--------------] [---] = [---] 先微分(怪怪的)
      [ (L₁₀ + L₀₁ᵀ) | (L₁₁ + L₁₁ᵀ) ] [ c ]   [ 0 ]
solve (L₀₀ + L₀₀ᵀ)x + (L₀₁ + L₁₀ᵀ)c = 0             再展開(只取一式)
solve (L₀₀ + L₀₀ᵀ)x = -(L₀₁ + L₁₀ᵀ)c                移項
solve L₀₀x = -L₀₁c                                  對稱矩陣。同除以二。

每個連通成分至少釘選一點,則L₀₀有反矩陣、有唯一解。

L₀₀是對稱、正定、對角優勢矩陣。矩陣求解,有許多演算法。

相對位置盡量固定、絕對位置盡量固定

v是相對位置差異,z是絕對位置,w u是權重。

min sum { wᵢⱼ ‖(pᵢ - pⱼ) - vᵢⱼ‖² } + sum { uᵢ ‖pᵢ - zᵢ‖² }

改寫成二次型、一次方程組。

min (Dx-v)ᵀW(Dx-v) + (x-z)ᵀU(x-z)
solve Lx = b     where L = DᵀWD + U and b = DᵀWv + Uz
W and U are diagonal matrices: diagonals are wᵢⱼ and uᵢ.
D is difference matrix: in each row, column i is 1 and column j is -1.
x:n×1, v:n²×1, D:n²×n, W:n²×n², z:n×1, U:n×n, L:n×n, b:n×1.

L仍然是對稱、半正定、對角優勢矩陣。

《Efficient Preconditioning of Laplacian Matrices for Computer Graphics》

相對距離盡量固定

d是相對距離。

min sum (‖pᵢ - pⱼ‖ - dᵢⱼ)²

如果指定了所有的兩兩距離,可以視作Multidimensional Scaling。如果指定了部分的兩兩距離,可以視作Matrix Completion,補足所有的兩兩距離。

Matrix Completion of D:
D = M⊙M       距離平方
D = UΣVᵀ       SVD(D)
Dₖ = UₖΣₖVₖᵀ     保留前k大的奇異值暨奇異向量們,作為距離矩陣。
D̃ = ½(Dₖ+Dₖᵀ)   調整成對稱矩陣。距離矩陣必須是對稱矩陣。

Multidimensional Scaling of D̃:
XᵀX = -½CD̃C    行列中心化、去掉係數
XᵀX = EΛEᵀ     Eigen(YᵀY)
X = √Λ₃E₃ᵀ     保留前三大的特徵值暨特徵向量們

《Localization From Incomplete Euclidean Distance Matrix: Performance Analysis for the SVD–MDS Approach》

彈力位能盡量小

w是彈性係數,d是彈簧長度,整體是彈力位能總和。

min sum wᵢⱼ (‖pᵢ - pⱼ‖ - dᵢⱼ)²

我不知道能不能使用MDS。等你發論文。

演算法是數值模擬。各點各自求得加速度、更新速度、更新座標。請見本站文件「Particle Simulation」。

宛如梯度下降法的改良版本。我不知道收斂條件為何。

《Graph Drawing by Stress Majorization》

面積盡量均勻:外心面積公式

網格可以討論面。

外心面積公式:三條中垂線得到外心,外心將三角形切三塊。

1. 三中垂線交於一點
2. 三個等腰三角形
3. θ=a+b,邊ij對頂角是2θ=2a+2b,對半分是θ=a+b
4. 底乘以高除以二就是半個等腰三角形面積
5. 底(‖pᵢ-pⱼ‖/2)  高(‖pᵢ-pⱼ‖/2)⋅cot(θ)
6. 半個等腰三角形面積,係數1/8
7. 三個等腰三角形面積,係數1/4

採用此公式,「三角形面積總和」可以改寫成「兩兩距離平方總和」的形式。計算面積,只需調整權重。

  min sum area(c)                                   三角形面積總和
   p   c

= min sum  sum  ½ ‖pᵢ - pⱼ‖ ½ ‖pᵢ - pⱼ‖ cot(θᵢⱼ)    外心面積公式
  p,θ  c  (i,j)   ~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~
         ∈cell(c)  bottom          height

= min sum  sum  ¼ cot(θᵢⱼ) ‖pᵢ - pⱼ‖²               整理
  p,θ  c  (i,j) 
         ∈cell(c)

= min  sum  (¼ cot(θᵢⱼ⁺) + ¼ cot(θᵢⱼ⁻)) ‖pᵢ - pⱼ‖²   主角從面變邊
  p,θ (i,j) ~~~~~~~~~~~~~~~~~~~~~~~~~~~
                        wᵢⱼ

= min xᵀLcotx  +  min yᵀLcoty                        主角從邊變點
  x,θ             y,θ

每個面負責三個小三角形=每條邊負責兩個小三角形。至於邊界上的邊,只負責一個小三角形。

wᵢⱼ = { ¼ cot(θᵢⱼ⁺) + ¼ cot(θᵢⱼ⁻)   if (i,j) is not boundary
      { ¼ cot(θᵢⱼ⁺)                 if (i,j) is boundary

未知數包含角度和位置,答案無限多個,缺乏討論意義。大家習慣指定角度大小,以便求解。例如各點頂角均分、參考其他網格。

注意:0°和180°導致cot(θ)無限大,矩陣求解無法進行。

Lcot缺陷:鈍角導致外心落在外部,面積為負值,cot(θ)為負值。可能導致負權重。可能導致非正定、非對角優勢。歹剃頭。

沒有鈍角,Lcot才保證是對稱、半正定、對角優勢矩陣。

面積盡量均勻:內心面積公式

更換面積公式,不必擔心鈍角。

內心面積公式:三條角平分線得到內心,內心將三角形切三塊。

1. 三角平分線交於一點
2. 三個小三角形
3. 小三角形,高r,左右底角½α ½β,左右底長h/tan(½θᵢ) h/tan(½θⱼ)
5. 小三角形,總底長‖pᵢ-pⱼ‖ = h/tan(½θᵢ) + h/tan(½θⱼ)
6. 通分並移項,高h = (tan(½θᵢ) ⋅ tan(½θⱼ)) / (tan(½θᵢ) + tan(½θⱼ))
7. 底乘以高除以二就是小三角形面積
8. 底‖pᵢ-pⱼ‖  高‖pᵢ-pⱼ‖ ⋅ (tan(½θᵢ) ⋅ tan(½θⱼ)) / (tan(½θᵢ) + tan(½θⱼ))
9. 一個小三角形面積,係數1/2
10. 三個小三角形面積,係數1/2
  min sum area(c)
   p   c
                                      tan(½θᵢ) ⋅ tan(½θⱼ)
= min sum  sum  ½ ‖pᵢ - pⱼ‖ ‖pᵢ - pⱼ‖ ———————————————————
  p,θ  c  (i,j)                       tan(½θᵢ) + tan(½θⱼ)
         ∈cell(c) ~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                    bottom              height

                  tan(½θᵢ) ⋅ tan(½θⱼ)
= min sum  sum  ½ ——————————————————— ‖pᵢ - pⱼ‖²
  p,θ  c  (i,j)   tan(½θᵢ) + tan(½θⱼ)
         ∈cell(c)

               tan(½θᵢ⁺)⋅tan(½θⱼ⁺)     tan(½θᵢ⁻)⋅tan(½θⱼ⁻)
= min  sum  (½ ——————————————————— + ½ ———————————————————) ‖pᵢ - pⱼ‖²
  p,θ (i,j)    tan(½θᵢ⁺)+tan(½θⱼ⁺)     tan(½θᵢ⁻)+tan(½θⱼ⁻)
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                                  wᵢⱼ

= min xᵀLtanx  +  min yᵀLtany
  x,θ             y,θ

注意:180°導致tan(½θ)無限大,矩陣求解無法進行。

Ltan仍是對稱、半正定、對角優勢矩陣。

Deformation

Deformation(Topology-Preserving Transformation)

「形變」。調整數據,盡量保持原始造型。

「形變」。已知甲堆數據,求得乙堆數據、變換函數。

採用全域變換,造型死板無法微調,於是大家採用局部變換。

圖的局部變換:

點變換:各點擁有變換函數。
    p̕ᵢ = Fᵢ(pᵢ)

網格擁有面,多了一種方式:

面變換:各面擁有變換函數,作用於頂點。
    p̕ᵢ = Fc(pᵢ)   for i∈cell(c)

圖的局部對齊:

點變換、點誤差:各點擁有變換函數。自身與鄰點實施變換,統計各點差異。
        min sum { ‖p̕ᵢ - Fᵢ(pᵢ)‖² + sum ‖p̕ⱼ - Fᵢ(pⱼ)‖² }
        F,p̕  i                   j∈adj(i)
點變換、邊誤差:各點擁有變換函數。自身與鄰點實施變換,統計各邊(向量)差異。
        min sum sum ‖(p̕ᵢ - p̕ⱼ) - (Fᵢ(pᵢ) - Fᵢ(pⱼ))‖²
        F,p̕  i j∈adj(i)
點變換、角誤差:各點擁有變換函數。自身與鄰點實施變換,統計各角差異。
        min sum sum ‖θ̕ⱼ - Fᵢ(θⱼ)‖²
        F,p̕  i j∈adj(i)
        where θ̕ⱼ     = ∠p̕ⱼp̕ᵢp̕ⱼ₊₁
              Fᵢ(θⱼ) = ∠Fᵢ(pⱼ)Fᵢ(pᵢ)Fᵢ(pⱼ₊₁)

網格擁有面,多了三種方式:

面變換、點誤差:各面擁有變換函數。頂點實施變換,統計各點差異。
        min sum sum ‖p̕ᵢ - Fc(pᵢ)‖²
        F,p̕  c i∈cell(c)
面變換、邊誤差:各面擁有變換函數。頂點實施變換,統計各邊(向量)差異。
        min sum sum ‖(p̕ᵢ - p̕ⱼ) - (Fc(pᵢ) - Fc(pⱼ))‖²
        F,p̕  c (i,j)∈cell(c)
面變換、角誤差:各點擁有變換函數。頂點實施變換,統計各角差異。
        min sum sum ‖θ̕ᵢ - Fc(θᵢ)‖²
        F,p̕  c i∈cell(c)
        where θ̕ᵢ     = ∠p̕ᵢ₋₁p̕ᵢp̕ᵢ₊₁
              Fc(θᵢ) = ∠Fc(pᵢ₋₁)Fc(pᵢ)Fc(pᵢ₊₁)

Affine Deformation

點變換、點誤差。

min sum { ‖p̕ᵢ - (Aᵢ(pᵢ) + b)‖² + sum ‖p̕ⱼ - (Aᵢ(pⱼ) + b)‖² }
F,p̕  i                         j∈adj(i)

保留局部造型,鄰角一齊變化,角度大小穩定。

演算法是大規模稀疏矩陣、一次最小平方方程組、公式解。

點仿射變換,邊無法疊合。邊重新畫上即可。

《Laplacian Surface Editing》

Affine Deformation

面變換、點誤差。

min sum sum ‖p̕ᵢ - (Ac(pᵢ) + b)‖²
F,p̕  c i∈cell(c)

可以完全對齊,毫無誤差。三角形任選一點作為原點,其兩鄰邊作為基底。

solve A(pᵢ - t) = (p̕ᵢ - t̕)     for i = 1,2,3
solve A(pᵢ - p₁) = (p̕ᵢ - p̕₁)   for i = 2,3
    [   |     |   ]       [   |     |   ]
V = [ p₂-p₁ p₃-p₁ ]   V̕ = [ p̕₂-p̕₁ p̕₃-p̕₁ ]
    [   |     |   ]       [   |     |   ]
AV = V̕
A = V̕V⁻¹

不會維持形狀,缺乏討論意義。

Laplacian Preserving Deformation

恆等變換(點面無區別)、邊誤差。

min sum wᵢⱼ ‖(p̕ᵢ - p̕ⱼ) - (pᵢ - pⱼ)‖²
 p̕ (i,j)

效果是盡量保持形狀。附帶效果是相對距離盡量均勻。

改寫成二次型、一次方程組。恰是「圖論版本的保梯散變換」!

min (x̕-x)ᵀL(x̕-x)  +  min (y̕-y)ᵀL(y̕-y)     where pᵢ = (xᵢ, yᵢ)
 x̕                    y̕                         p̕ᵢ = (x̕ᵢ, y̕ᵢ)
solve Lx̕ = Lx   and   solve Ly̕ = Ly

演算法請參考先前章節:相對距離盡量均勻。

答案是直接複製貼上,缺乏討論意義。大家習慣追加其他限制條件,例如某些點位置必須固定。

solve L₀₀x̕ = L₀₀x - L₀₁c   and   solve L₀₀y̕ = L₀₀y - L₀₁d

Rigid Deformation / Similar Deformation

點變換、邊誤差。

min sum sum ‖(p̕ᵢ - p̕ⱼ) - Rᵢ(pᵢ - pⱼ)‖²
R,p̕  i j∈adj(i)

演算法是區塊座標下降法:固定p̕求得R、固定R求得p̕,不斷輪流。Rigid Alignment與Laplacian Preserving Deformation不斷輪流。

固定p̕求得R:(pᵢ - pⱼ)和(p̕ᵢ - p̕ⱼ)視作點,化作Rigid Alignment。公式解。

鄰點們的平均數是定值。預先中心化,以便快速求解。

YXᵀ = UΣVᵀ
R = UVᵀ

固定R求得p̕:Rᵢ(pᵢ - pⱼ) = (Rᵢpᵢ - Rᵢpⱼ)視作兩點相減,化作Laplacian Preserving Deformation。矩陣求解。

Laplacian Matrix是定值。預先做Cholesky Decomposition,以便快速求解。

solve Lx̕ = Lx
solve MMᵀx̕ = Lx     where L = MMᵀ

點剛體變換,邊無法疊合。最後得到類似剛體的變換。不是剛體變換,不是盡量剛體變換(奇異值與1的平方誤差總和盡量小)。

《As-Rigid-As-Possible Surface Modeling》

Rigid Deformation / Similar Deformation

面變換、邊誤差。

min sum sum ‖(p̕ᵢ - p̕ⱼ) - Rc(pᵢ - pⱼ)‖²
R,p̕  c (i,j)∈cell(c)

演算法是區塊座標下降法。

固定p̕求得R:化作三個點的Rigid Alignment。

固定R求得p̕:無法化作Laplacian Preserving Deformation,原始論文搞錯了。正確方法請參考先前章節:相對位置盡量固定。

面剛體變換,面無法接合。區塊座標下降法最後一步不能停在Rigid Alignment。

最後得到類似剛體的變換。不是剛體變換,不是盡量剛體變換。

時間複雜度較高,缺乏討論意義。

《A Local/Global Approach to Mesh Parameterization》

Isotropic Scaling Deformation

面變換、邊誤差。

min sum sum ‖(p̕ᵢ - p̕ⱼ) - sc(pᵢ - pⱼ)‖²
s,p̕  c (i,j)∈cell(c)

演算法是區塊座標下降法。

固定p̕求得s:簡易公式解,不必奇異值分解。

固定s求得p̕:同先前小節。

min sum sum ‖(p̕ᵢ - p̕ⱼ) - sc(pᵢ - pⱼ)‖²
 s   c (i,j)∈cell(c)

solve sum sum { 2 (p̕ᵢ - p̕ⱼ)ᵀ(pᵢ - pⱼ) - 2 sc ‖pᵢ - pⱼ‖² } = 0
       c (i,j)∈cell(c)

sc = [ sum (p̕ᵢ - p̕ⱼ)ᵀ(pᵢ - pⱼ) ] ÷ [ sum ‖pᵢ - pⱼ‖² ]
      (i,j)∈cell(c)                (i,j)∈cell(c)

不允許旋轉,只允許縮放,三角形容易交疊。額外拿向量長度做regularization,維持局部造型,避免交疊。

...... + sum sum ‖(p̕ᵢ - p̕ⱼ) - lᵢⱼ(pᵢ - pⱼ)‖²
          c (i,j)∈cell(c)

where lᵢⱼ = ‖p̕ᵢ - p̕ⱼ‖ ÷ ‖pᵢ - pⱼ‖

演算法是區塊座標下降法:固定p̕求得s和l、固定s和l求得p̕,不斷輪流。

為了方便求解,原始論文偷吃步,固定l求得p̕。然而l包含p̕,不能拆開計算。只好改拿上一步的向量長度做regularization。

...... + sum sum ‖(p̕ᵢ⁽ᵗ⁾ - p̕ⱼ⁽ᵗ⁾) - lᵢⱼ(pᵢ - pⱼ)‖²
          c (i,j)∈cell(c)

where lᵢⱼ = ‖p̕ᵢ⁽ᵗ⁻¹⁾ - p̕ⱼ⁽ᵗ⁻¹⁾‖ ÷ ‖pᵢ - pⱼ‖

自我審查之後,就可以使用區塊座標下降法了。工程精神!

《Optimized Scale-and-Stretch for Image Resizing》

Isogonal Affine Deformation

面變換、角誤差。

min sum { ‖θ̕₁ - θ₁‖² + ‖θ̕₂ - θ₂‖² + ‖θ̕₃ - θ₃‖² }
 θ̕   c
subject to all θ̕₁ + θ̕₂ + θ̕₃ = π                三角形內角和180°
            c
           all sum { θ̕₁ } = 2π                 鄰角和360°
            i c∈adj(i)
           all pro { sin(θ̕₂) ÷ sin(θ̕₃) } = 1   鄰邊長度比,繞一圈為1
            i c∈adj(i)
           all θ̕₁, θ̕₂, θ̕₃ ≥ 0                  角度非負
            c

一旦確定角度,也就決定網格(可能鏡射)。因此直接求角度。

二次規劃。演算法是牛頓拉格朗日乘數法。

直接拷貝,就是保角,缺乏討論意義。因此大家討論其他情況,例如重新釘住某些點,例如三維表面變成二維平面。

《ABF++: Fast and Robust Angle Based Flattening》

Isogonal Affine Deformation

網格的變換,可以用經典數學領域來詮釋:微積分的分段變換(連續雙射)、圖論的局部變換(面變換)。微積分考慮所有地點,圖論僅考慮點與邊。

網格的仿射變換,擁有許多特殊性質:

一、輸入輸出劃定網格,各三角形各自實施仿射變換。
二、輸入輸出劃定網格,只有唯一一種仿射變換。
三、微積分分段仿射=圖論局部仿射。
  註:三角形處處做仿射變換=三頂點做仿射變換+內部做仿射座標系。
四、微積分保長≠圖論保長。註:圖論保長未定義。
五、微積分保距≠圖論保距。
六、微積分保角=圖論保角。
七、微積分和諧≠圖論和諧。
八、微積分保角≠微積分和諧。
九、當面積固定,微積分盡量保角=微積分盡量和諧。
十、微積分能量=圖論能量(使用Lcot)。

第十項,能量是指Dirichlet Energy。證明如下:

微積分能量:處處梯度平方和。用於函數。用於區域。
圖論能量:兩兩距離平方和。用於圖。用於點與邊。
  ∫ ‖∇F‖F²               微積分能量

= sum ∫c ‖∇FcF²         分段變換
   c

= sum area(c) ‖Acᵀ‖F²     分段仿射變換 p̕ = Ap + b
   c

= eigher [DDG2016 at TU Berlin] or [Pinkall93]


= sum sum ¼ cot(θᵢⱼ) ‖p̕ᵢ - p̕ⱼ‖²                 原網格的夾角
   c (i,j)∈cell(c)                              新網格的邊長

= sum  (¼ cot(θᵢⱼ⁺) + ¼ cot(θᵢⱼ⁻)) ‖p̕ᵢ - p̕ⱼ‖²   主角從面變邊
 (i,j) ^^^^^^^^^^^^^^^^^^^^^^^^^^^
                   wᵢⱼ

= x̕ᵀLcotx̕ + y̕ᵀLcoty̕        主角從邊變點,圖論能量

宛如外心面積公式Lcot。不知是否能換成內心面積公式Ltan

總結:當面積固定,圖論盡量保角=微積分盡量保角=微積分盡量和諧=微積分能量盡量小=圖論能量盡量小(使用Lcot)。

min x̕ᵀLcotx̕  +  min y̕ᵀLcoty̕     where p̕ᵢ = (x̕ᵢ, y̕ᵢ)
 x               y
solve Lcotx̕ = 0   and   solve Lcoty̕ = 0

問題得以化作先前章節:面積盡量均勻。沿用原網格的夾角。

令新網格邊界是凸多邊形,釘住網格邊界,以保證面積固定。

令原網格是Delaunay Triangulation,以保證除了邊界以外的wᵢⱼ非負,以保證L₀₀有反矩陣、有唯一解。

《Spectral Conformal Parameterization》

凸包性質(Mean Value Property)

Graph Laplacian Analysis精髓:各點更新為鄰點的加權平均。

GLA不允許負權重。因此各點位於鄰點的凸包內部。

釘住某些點,形變之後,所有點都將位於釘點的凸包內部。

平面圖性質(Tutte's Spring Theorem)

僅適用網格。

當釘點們形成凸多邊形,網格形變之後仍是網格。所有點不會超出凸多邊形,所有邊不會交叉,所有角不會翻面。

當釘點們形成凸多邊形,而且位於網格邊界,網格形變之後不會退化。點邊角不會疊合在一起。

當釘點們形成凹多邊形,網格形變之後可能是網格、可能不是網格。表面積公式有可能失效。

對稱正定性質(Rippa's Theorem)

能量盡量小(使用Lcot)、最小角盡量大,兩者密切相關。

給邊求點(釘住邊界上所有點、補滿邊界上所有邊):
可以採用Dirichlet Energy Minimization (Lcot)。
恰好形成Delaunay Triangulation。

給點求邊:
可以採用Delaunay Triangulation。
恰好形成Dirichlet Energy Minimization (Lcot)。

最小角盡量大=兩個相鄰三角形的共用邊不可翻轉=對頂角的cot值總和非負。

Delaunay triangulation iff wᵢⱼ = ¼ cot(θᵢⱼ⁺) + ¼ cot(θᵢⱼ⁻) ≥ 0
where (i,j) is not boundary

Delaunay Triangulation可能有鈍角,但是保證wᵢⱼ非負(不含邊界),進而保證L₀₀是對稱正定矩陣(釘住邊界)。

《A Spectral Characterization of the Delaunay Triangulation》

Minimum Energy Deformation

(minimal surface of membrane ⇒ laplaican)
smoothing energy: min sum ‖J(Fc)‖F²  ⇒  solve Lcotx = 0
                   F   c

(minimal curvature of thin plate ⇒ bilaplaican)
bending energy:   min sum ‖H(Fc)‖F²  ⇒  solve Lcot²x = 0
                   F   c
J(F) = ∇Fᵀ    最近似線性變換矩陣
‖J(F)‖²       能量
min ‖J(F)‖²   盡量和諧

變換函數的一次微分的長度盡量小,化作一階梯散方程式求解。

物理意義:面積盡量小。盡量拉緊。適用於薄膜,例如肥皂泡。

變換函數的二次微分的長度盡量小,化作二階梯散方程式求解。

物理意義:曲率盡量小。盡量壓平。適用於薄片,例如厚紙板。

次方越高,形狀越圓。

《Polygon Mesh Processing》

Rigid Deformation / Similar Deformation

rigid energy:   min sum ‖Rc - J(Fc)‖F²
                F,R  c
similar energy: min sum ‖Sc - J(Fc)‖F²
                F,S  c

方才的數學式子,追加特定變換函數,形成了剛體、相似。

如果已知F,那麼R和S有公式解。R和S改寫成F的形式之後,未知數只剩下F。

目前沒有演算法。大家沿用之前的演算法,矩陣改成Lcot

isometric energy: min sum { area(c) [(σ₁ - 1)² + (σ₂ - 1)²] }
                  F,σ  c
isogonal energy:  min sum { area(c) (σ₁ - σ₂)² }
                  F,σ  c

順帶一提,有人將數學式子改寫成奇異值的形式。奇異值是絕對值,省略了正負號,包含了鏡射,形成了保距、保角。

《Variational Harmonic Maps for Space Deformation》

Boundary-free Deformation

不釘住邊界,而是自由調整邊界,讓網格更加均勻。

min Ed(M,M̕) + λ₁ Eb(B) + λ₂ Ed(S,S̕)

Ed(.,.) = sum ‖J(Fc)‖F² + ‖J(Fc⁻¹)‖F²
           c
Eb(.) = sum   sum  max(0, ε / dᵢⱼₖ - 1)²
       (i,j) k≠i,j
dᵢⱼₖ = ‖pᵢ - pₖ‖ + ‖pⱼ - pₖ‖ - ‖pᵢ - pⱼ‖   triangle inequality

λ₁ λ₂ ε are positive constants

不釘住邊界,讓邊界盡量保持相同,方法是追加最佳化目標。

一、網格M,能量盡量小(對稱方式)。

二、邊界B,鄰點距離盡量小、非鄰點距離盡量大。

三、邊界包覆一層薄薄的網格S,能量盡量小(對稱方式)。

《Efficient Bijective Parameterizations》

Equiareal Affine Deformation

目前沒有演算法。這裡介紹一個大概差不多的演算法。

能量=變換矩陣元素平方和=奇異值平方和=縮放倍率平方和。

一個頂點的平均能量sᵢ:相鄰三角形的能量的加權平均數。權重是面積。

sᵢ = sum { area(c) ‖Ac‖² } ÷ sum { area(c) }
   c∈adj(i)                 c∈adj(i)

平均能量sⱼ,開根號,當作邊長縮放率sqrt(sⱼ)。

邊長縮放率取倒數當作權重。權重越大,距離越短。

min sum wᵢⱼ ‖p̕ᵢ - p̕ⱼ‖²     where wᵢⱼ = 1 / sqrt(sⱼ)

每個想法乍看合情合理,但是沒有數學證明。論文聲稱的盡量不伸縮也只是推測。

演算法是區塊座標下降法:固定q求得A、固定A求得q,不斷輪流。

《A Fast and Simple Stretch-Minimizing Mesh Parameterization》

備忘:Gradient-Laplacian Deformation

目前沒有論文、也沒有實際用處。

我們希望指定數據造型。我們設計一個複雜的最佳化目標函數:梯度差異(邊)、梯散差異(點:鄰邊和),平方總和盡量小。

min { sum ‖(pᵢ-pⱼ) - (p̕ᵢ-p̕ⱼ)‖² + sum ‖sum (pᵢ-pⱼ) - sum (p̕ᵢ-p̕ⱼ)‖² }
 p̕   (i,j)                        i  j∈adj(i)      j∈adj(i)
          ~~~~~~~~~~~~~~~~~~~~       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        gradient diff (edge diff)    laplacian diff (vertex diff)

改寫成向量。

min { sum ‖vᵢⱼ - v̕ᵢⱼ‖² + sum ‖sum vᵢⱼ - sum v̕ᵢⱼ‖² }
 p̕   (i,j)                i  j∈adj(i)  j∈adj(i)

where vᵢⱼ = pᵢ - pⱼ , v̕ᵢⱼ = p̕ᵢ - p̕ⱼ

每個維度可以分開處理,分開最佳化。

引入Adjacency Matrix,改寫成矩陣運算。

vᵢⱼ的x座標,視作矩陣Ax。vᵢⱼ的y座標,視作矩陣Ay

  min { ‖Ax - A̕xF² + ‖Dx - D̕xF² }
   x̕
+ min { ‖Ay - A̕yF² + ‖Dy - D̕yF² }     where p̕ᵢ = (x̕ᵢ, y̕ᵢ)
   y̕

引入Laplacian Matrix,合併A與D。

A沒有對角線,D只有對角線。

min ‖Lx - L̕xF² + min ‖Ly - L̕yF²     where p̕ᵢ = (x̕ᵢ, y̕ᵢ)
 x̕                 y̕

演算法是梯度下降法。每一步皆以當前的x̕求得L̕x

gradient are 2(L̕x - Lx)𝟏   and   2(L̕y - Ly)𝟏

答案是直接拷貝,缺乏討論意義。大家習慣讓vᵢⱼ是任意非負對稱矩陣,不必是兩兩相減。大家也習慣追加其他限制條件。

Homotopy

Homotopy(Shape Interpolation)

「同倫」。形變只有結果:t=1。同倫包括過程:t∈[0,1]。

三種策略:內插、外插、公式。本文介紹內插,至於外插請見本站文件「Simulation」,公式請見物理教科書。

內插:先形變t=1,再內插t∈[0,1]。用來製造人工行為。
外插:時間增量Δt,逐步形變t+=Δt。用來模擬自然現象。
公式:設計數學公式,直接求得位置。兩者兼備。

仿射變換的內插

利用上個章節的演算法,得到仿射變換函數。

affine transformation: p̕ = Ap + b

位移向量、變換矩陣,兩者分開內插。

位移向量的內插:時刻變化是位移比例。直接乘上t。
變換矩陣的內插:三種方法。特徵分解、奇異值分解、極分解。
一、特徵分解:特徵值矩陣[0,1]次方。
  缺點:不一定能特徵分解(等價於有歪斜?)。
  缺點:非整數次方難以計算。
二、奇異值分解:兩個旋轉矩陣(左右奇異向量)、縮放矩陣(奇異值),各自內插。
  旋轉矩陣:旋轉軸固定,旋轉角內插。
  縮放矩陣:矩陣元素各自內插。
三、極分解:旋轉矩陣(正規正交矩陣)、對稱正定矩陣(特徵縮放矩陣),各自內插。
translation interpolation:
1. b⁽ᵗ⁾ = lerp(0,b) = tb

transformation matrix interpolation:
1. A = EDE⁻¹            , A⁽ᵗ⁾ = EDᵗE⁻¹
2. A = UΣVᵀ             , A⁽ᵗ⁾ = slerp(0,U) lerp(I,Σ) slerp(0,Vᵀ)
3. A = (UVᵀ)(VΣVᵀ) = RS , A⁽ᵗ⁾ = slerp(0,R) lerp(I,S)
lerp(I,S) = (1-t)I + tS
slerp(0,R) = https://en.wikipedia.org/wiki/Slerp

極分解的視覺效果最好。大家都用極分解。

記得偵測鏡射、去除鏡射。

簡易方式:通通變號(維度必須為奇數,例如三維)。
進階方式:最小的奇異值變號、對應的向量變號。
3a. A = (UVᵀ)(VΣVᵀ) = QP = (-Q)(-P)
{ R = Q and S = P            if det(Q) = +1
{ R = -Q and S = -P          if det(Q) = -1
when n is odd.

3b. A = (UVᵀ)(VΣVᵀ) = QP = QDD⁻¹P
{ R = Q and S = P            if det(Q) = +1
{ R = QD and S = D⁻¹P = DP   if det(Q) = -1
where D = diag([1 1 ... 1 det(Q)]) = D⁻¹   奇異值暨奇異向量由大到小排列

《Matrix Animation and Polar Decomposition》

仿射變換盡量固定

面變換。指定每一個三角形的仿射變換Ac⁽⁰⁾。

目標條件:令變換矩陣盡量相同。追加限制條件:相鄰三角形共用頂點(貼齊三角形)。

min sum ‖Ac - Ac⁽⁰⁾‖²   subject to all A₁(pᵢ) + b₁ = A₂(pᵢ) + b₂ = ......
A,p  c                              i

劃定網格,只有唯一一種仿射變換。三角形任選一點作為原點,其兩鄰邊作為基底,得到仿射變換。Ac改寫成p的形式,以解p。

演算法是大規模稀疏矩陣、一次最小平方方程組、公式解。

《Deformation Transfer for Triangle Meshes》

Affine Homotopy

面變換、仿射變換內插。綜合前面兩個小節。

一、仿射變換內插。
  A⁽ᵗ⁾ = slerp(0,R) lerp(I,S)     where A = (UVᵀ)(VΣVᵀ) = RS
  b⁽ᵗ⁾ = lerp(0,b)
二、點座標內插。
  p⁽ᵗ⁾ = A⁽ᵗ⁾p⁽⁰⁾ + b⁽ᵗ⁾
三、盡量接近內插結果。
  min sum ‖Ac - Ac⁽ᵗ⁾‖²
四、追加限制條件:相鄰三角形共用頂點(貼齊三角形)。
  subject to all A₁(pᵢ) + b₁ = A₂(pᵢ) + b₂ = ......
五、追加限制條件:釘住某些點。部分p⁽ᵗ⁾已知。
 回、釘點是仿射變換內插。p = A⁽ᵗ⁾p⁽⁰⁾ + b⁽ᵗ⁾
 回、釘點是自訂路徑。設計不同的路徑,得到不同的形狀。

《As-Rigid-As-Possible Shape Interpolation》

Laplacian Preserving Homotopy

點變換、梯散內插。

一、仿射變換內插。
  A⁽ᵗ⁾ = slerp(0,R) lerp(I,S)     where A = (UVᵀ)(VΣVᵀ) = RS
  b⁽ᵗ⁾ = lerp(0,b)
二、點座標內插。
  p⁽ᵗ⁾ = A⁽ᵗ⁾p⁽⁰⁾ + b⁽ᵗ⁾
三、梯散內插。
  ∆p⁽ᵗ⁾ = ∆(lerp(p⁽⁰⁾, p⁽¹⁾))     where ∆p⁽ᵗ⁾ = sum (pᵢ⁽ᵗ⁾ - pⱼ⁽ᵗ⁾)
        = lerp(∆p⁽⁰⁾, ∆p⁽¹⁾)                  j∈adj(i)
四、Laplacian Preserving Deformation。
  solve Lx = ∆px⁽ᵗ⁾   and   solve Ly = ∆py⁽ᵗ⁾

利用Laplacian Preserving Deformation,貼齊三角形。

梯散、內插,恰是線性函數。先內插再梯散=先梯散再內插。預先計算原始梯散、最終梯散,以便快速內插。

演算法是矩陣求解。Laplacian Matrix是定值。預先做Cholesky Decomposition,以便快速求解。

每個連通成分釘住至少一點,以得到唯一解。

Laplacian Preserving Deformation和Laplacian Preserving Homotopy,兩者的差異僅在於梯散的取得方式。前者是原圖的梯散,後者是內插的梯散。

《Poisson Shape Interpolation》

Rigid Homotopy / Similar Homotopy

同上。改成Rigid Deformation。

《Large Mesh Deformation Using the Volumetric Graph Laplacian》

Embedding

Embedding(Dimensionality Reduction)

「嵌入」。更換數據所在空間。例如從三維換成二維。例如從二維換成三維。例如從球面換成平面。例如從曲面換成環面。

這裡先不談太廣,僅討論最簡單的情況:數據從N維空間換成M維空間。細分為三種情況:維度變小、維度不變、維度變大。

後兩者缺乏討論意義──數據不變、數據補零不就好了。因此我們僅討論維度變小。此時「嵌入」的意義就變成了:找到一個函數,讓一堆數據經過函數變換,減少數據維度。

p = {{112,60,70},{130,70,78},{140,88,92},{140,112,108},{130,130,122},{112,140,130},{88,140,70},{70,130,78},{60,112,92},{60,88,108},{70,70,122},{88,60,130}}; Graphics3D[{Black, Specularity[White, 10], Sphere[p, 4]}, PlotRange -> {{50,150},{50,150},{50,150}}, Boxed -> False]

嵌入方式有許多種。例如投影就是其中一種嵌入方式。例如訂立座標系統並且實施座標轉換,也是其中一種嵌入方式。

嵌入時,我們通常希望儘量保留數據的原始特性。特性可以是數據的聚散程度、數據之間的距離遠近。計算學家針對各種特性,設計各種演算法。

演算法(Self-organizing Map)

嵌入時,盡量保持疏密相同。

早期的演算法。與其說是Embedding,不如說是Alignment。

低維度四邊形網格,對齊高維度數據。不知道索引值對應關係,於是隨時實施最近鄰指派。

梯度下降法。找到最近節點,鄰居一齊更新位置。

https://en.wikipedia.org/wiki/Self-organizing_map

演算法(Random Projection)

嵌入時,盡量保留兩兩距離。

隨機生成線性變換矩陣。隨機導致均勻,均勻導致正交,正交導致保距。絕智棄辯,民利百倍。

演算法(Multidimensional Scaling)

嵌入時,盡量保留兩兩距離。

求得距離矩陣,行列中心化,除以負二,得到點積矩陣。給定點積矩陣,求得數據矩陣,答案有無限多種。採用奇異值分解的內積分解,答案恰好等於PCA嵌入。

演算法(Principal Component Analysis)

嵌入時,採用垂直投影,盡量減少投影距離。

數據矩陣中心化X̃ = X - X̄。奇異值分解X̃ = UΣVᵀ。保留ΣVᵀ,取前k大的奇異值暨奇異向量,數據降為k維。

Graph Embedding

引入Adjacency Matrix,只考慮部分的兩兩距離。

建立Adjacency Matrix有許多細節。

一、挑選鄰居:距離較近的數據,成為鄰居。
  (全部、Fixed-radius Near Neighbor、K-Nearest Neighbor)
二、設定權重:距離作為權重。套用鐘形函數:超過一定距離,鄰居關係迅速減弱。
  (均一、Distance、RBF Kernel、Heat Kernel)

當演算法的原理是Graph Laplacian Analysis,需要進一步調整Adjacency Matrix的權重。也可以說是Laplacian Matrix的權重。

一、權重必須取倒數:權重越大,實施GLA,距離越近。
  (全域聚集:數據盡量集中。)
二、權重可以比例化:鄰邊越多,權重總和越大,權重比例化越小,鄰點越遠。
  (局部疏散:鄰邊越多、鄰點越遠。)

比例化有兩種選擇,一般採用橫條比例化。

normalized Laplacian matrix: D⁻¹L                  橫條比例化
symmetric normalized Laplacian matrix: √D⁻¹L√D⁻¹   直條橫條比例化

Normalized Laplacian Matrix其實是比例化。古人命名不精準。

proportionalize:比例化。令總和為1。
normalize:正規化。令平方和為1。

演算法清單:http://www.cs.cmu.edu/~liuy/distlearn.htm

也有人稱為「流形學習Manifold Learning」,然而此觀念既非流形、亦非學習,只是為了聽起來很屌,就好比乂煞氣a嵌入乂。

演算法(Isomap)

嵌入時,盡量保留兩兩距離。

一、Adjacency Matrix:挑選鄰居,設定權重。
二、All-Pairs Shortest Paths:所有數據兩兩距離。(使用上述權重)
三、Multidimensional Scaling:盡量保留兩兩距離。

《A Global Geometric Framework for Nonlinear Dimensionality Reduction》

演算法(Graph Laplacian Analysis)

嵌入時,盡量讓距離均勻。

一、Adjacency Matrix:挑選鄰居,設定權重。
二、Graph Laplacian Analysis:盡量讓距離均勻。

GLA有三種解法:二次型最佳化、一次方程組求解、特徵分解。降維適合採用特徵分解。

令特徵向量長度為1(變異數為1)。正解是最小的特徵值的特徵向量,缺乏討論意義。改取次k小的特徵值的特徵向量們,k個特徵向量構成k維數據。

minimize yᵀLy                  subject to ‖y‖² = yᵀy = 1
minimize yᵀLy - λ (yᵀy - 1)
solve Ly - λy = 0
solve Ly = λy

局部疏散:原始論文採用√D⁻¹L√D⁻¹。

廣義特徵向量。最後讓v變回y。也有人直接將v當作答案。

minimize yᵀ√D⁻¹L√D⁻¹y          subject to yᵀy = 1 
minimize vᵀLv                  subject to vᵀDv = 1   (let v = √D⁻¹y)
minimize vᵀLv - λ (vᵀDv - 1)
solve Lv - λDv = 0
solve Lv = λDv

其他稱呼:Laplacian Eigenmap、Diffusion Map、Harmonic Embedding。

《Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering》

演算法(Laplacian Principal Component Analysis)

嵌入時,盡量讓距離均勻,而且必須是線性變換。

一、Adjacency Matrix:挑選鄰居,設定權重。
二、LPCA:數據實施某種線性變換,盡量讓距離均勻。

線性變換抑制了GLA的效果,畫蛇添足。

取次k小的廣義特徵值的廣義特徵向量們,k個廣義特徵向量作為A的橫條,再以A和X求得Y。也有人直接將V當作X。

minimize Y√D⁻¹L√D⁻¹Yᵀ              subject to Y = AX and YYᵀ = I
minimize AX√D⁻¹L√D⁻¹XᵀAᵀ           subject to AXXᵀAᵀ = I
minimize AX√D⁻¹L√D⁻¹XᵀAᵀ - λ (AXXᵀAᵀ - I)
solve X√D⁻¹L√D⁻¹Xᵀa - λXXᵀa = 0
solve (X√D⁻¹L√D⁻¹Xᵀ)a = λ(XXᵀ)a
solve (VLVᵀ)a = λ(VDVᵀ)a           (let V = X√D⁻¹)

《Locality Preserving Projections》

演算法(Locally Linear Embedding)

嵌入時,盡量保持梯散為零。

一、Adjacency Matrix:挑選鄰居,但是不設定權重。
二、Laplacian Assignment:原數據,求得權重,盡量讓梯散為零。【尚無正式名稱】
三、Graph Laplacian Analysis:新數據,沿用權重,盡量保持梯散為零。

Laplacian Assignment:各點分開計算,令鄰邊權重總和等於鄰邊數量n,方便推導公式解。

局部疏散:最後一步不用乘回n。

solve LXᵀ = 0       subject to all sum Wᵢⱼ = n   (where L = I - W)
  W                             i   j
min ‖ sum {xₖ - Wₖᵢ adjᵢ(xₖ)} ‖² st sum Wₖᵢ = n   處理第k點xₖ。
 Wₖ    i                            i
min ‖ xₖ - sum {wᵢ adjᵢ(xₖ)} ‖² st sum wᵢ = 1    除以n。令wᵢ = Wₖᵢ / n。
 w          i                      i
Cᵢⱼ = (xₖ - adjᵢ(xₖ)) ∙ (xₖ - adjⱼ(xₖ))     xₖ所有鄰邊兩兩點積,形成矩陣。

wᵢ = (sum C⁻¹ᵢⱼ) / (sum sum C⁻¹ᵢⱼ)        C⁻¹第i橫條總和除以C⁻¹元素總和。
       j             i   j                【尚待確認】
Wₖᵢ = n wᵢ                                還原原本權重。也有人不這麼做。

GLA:標準作法是(L+Lᵀ)。原始論文則是最小平方法LᵀL,效果如同Bilaplacian。

solve LYᵀ = 0       subject to YYᵀ = I           (where L = I - W)
  Y
solve Ly = 0        subject to ‖y‖² = yᵀy = 1
min ‖Ly‖²           subject to ‖y‖² = yᵀy = 1
min (Ly)ᵀLy         subject to ‖y‖² = yᵀy = 1
min yᵀ(LᵀL)y        subject to ‖y‖² = yᵀy = 1
solve LᵀLy = λy

https://www.cnblogs.com/xbinworld/archive/2012/07/09/LLE.html

《Nonlinear Dimensionality Reduction by Locally Linear Embedding》

演算法(Stochastic Neighbor Embedding)

嵌入時,盡量保持分布相同。

原數據、新數據,分別求得高斯混合模型。令兩個分布的距離盡量小,距離採用Kullback-Leibler Divergence。

SNE:常態分布的混合模型。

t-SNE:學生t分布的混合模型,效果更好。

http://www.datakit.cn/blog/2017/02/05/t_sne_full.html

《Visualizing Data using t-SNE》

演算法(Stochastic Neighbor Embedding)

換個觀點。嵌入時,盡量保持內插函數相同。

數據添加一個新維度作為函數值,一律是1。原數據X、新數據Y,分別實施Inverse Distance Weighting Interpolation(原始論文的分母少了一項)。令兩個內插函數的誤差盡量小,誤差是N個函數值的差距的總和。

SNE:解放中二力,故意添加exp和log,效果變差。

t-SNE:封印中二力,未添加exp和log。

演算法(Stochastic Neighbor Embedding)

再換個觀點。嵌入時,盡量保持梯散相同。

一、Adjacency Matrix:挑選鄰居,設定權重。
二、Adaptive GLA:新數據,沿用權重,盡量保持梯散相同。【尚無正式名稱】

權重:距離平方倒數(原始論文將分母加一,避免除以零)。

局部疏散:矩陣橫條比例化。

GLA:自適應梯度下降法Momentum。

每回合不斷更新新數據的Laplacian Matrix LY

gradient is (LX - LY)y

Clustering

數據沒有類別。嵌入時,盡量同類相聚。

也有人稱作Unsupervised Manifold Learning。屌。

演算法(Spectral Clustering)

一、Adjacency Matrix:挑選鄰居,設定權重。
二、Graph Laplacian Analysis:盡量讓距離均勻。
三、K-Means Clustering:盡量讓相鄰數據歸類於同一組。

預先用Graph Laplacian Analysis調整數據形狀,才做K-Means Clustering。就這樣。跟Spectral沒有什麼太大關係。

有人聲稱此演算法等價於Maximum Cut近似解。我想應該是哪裡搞錯了。Maximum Cut當中,向量元素必須是0或1;而特徵向量元素通常不是0或1。

《On Spectral Clustering: Analysis and an Algorithm》

演算法(Markov Clustering)

Adjacency Matrix的無限大次方。隨機散步無限多步最終分布。

http://www.columbia.edu/~jwp2128/Teaching/W4721/Spring2017/slides/lecture_4-11-17.pdf

Classification

數據具有類別。嵌入時,盡量同類相聚。

也有人稱作Supervised Manifold Learning。屌。

演算法(Linear Discriminative Analysis)

援引Principal Component Analysis的概念。

尋找一條直線,數據投影到直線之後,各類數據的平均數的變異數盡量大(異類盡量散開),各類數據各自的變異數盡量小(同類盡量聚集)。

演算法(Neighborhood Component Analysis)

援引Stochastic Neighbor Embedding的概念。

尋找一個線性變換矩陣,同類數據的兩兩距離總和盡量小。距離矩陣橫條比例化。