Assignment(Under Construction!)

Mapping / Correspondence

「映射」。兩堆數據的一一連結。遵循函數定義。

「對應」。兩堆數據的一一連結。不必迎合函數定義。

Assignment

「指派」。一堆數據,經過對應,符合另一堆數據。已知甲堆數據、乙堆數據,求映射函數。

隨隨便便就能發明一大堆誤差公式。哪種誤差比較好?目前沒有定論。

一、窮舉甲堆到乙堆的所有兩兩配對,累計距離。
二、窮舉甲堆每一筆數據,分別找到乙堆之中距離最近的那筆數據,累計距離。
三、窮舉乙堆每一筆數據,分別找到甲堆之中距離最近的那筆數據,累計距離。
四、二與三相加。
五、二與三聯集。
六、上述誤差,改為只累計前K短的距離。
七、上述誤差,只考慮互相鄰近的K筆數據。(部分銜接的效果)

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

一對一(Bipartite Matching)

誤差是數據的距離總和。

Alignment(Under Construction!)

備忘

PCA     y = SRx + t   rows/dimensions of y are orthogonal. sqrt(xxᵀ).

[regression]
1. linear regression:
   give two data set, find affine transformation. (Normal Equation)
2. linear fitting:
   give one data set, find orthonormal basis. (PCA)

[3 big problem]
1. given a transformation, find affine transformation. (approximation)
 (1) global            ---> jacobian    (taylor)
 (2) piecewise         ---> hermitian interpolation ???
2. give two data set, find transformation. (alignment)
 (1) global affine     ---> large sparse matrix
     https://stackoverflow.com/questions/11687281/
 (2) piecewise affine  ---> exact solution (basis transform, barycentric)
 (3) total similar     ---> SVD
 (4) piecewise similar ---> nonsense ???
3. given a/no data set, find transformation and new data set. (deformation)
 (1) global basic3       ---> representation (PCA)
     XXᵀ = UΣVᵀ(UΣVᵀ)ᵀ = UΣΣUᵀ, A = Σ⁻¹U⁻¹
 (2) piecewise laplacian ---> representation (optimization/equation)
 (3) piecewise similar   ---> deformation (global/local)

Transformation

Alignment

「對齊」。一堆數據,經過變換,盡量符合另一堆數據。已知甲堆數據、乙堆數據,求變換函數。

函數具有特殊限制,增進討論意義。

一次迴歸是特例:甲堆是多維數據,乙堆是一維數據,使用仿射變換。

進階問題Optimal Registration:多堆數據組裝在一起。多堆數據的對齊。

仿射變換

當知道數據對應關係,並且兩堆數據一樣多。

誤差是對應數據的距離總和。

相似變換(Procrustes Analysis)

當知道數據對應關係,並且兩堆數據一樣多。

https://igl.ethz.ch/projects/ARAP/svd_rot.pdf
http://perception.inrialpes.fr/~Horaud/Courses/pdf/Horaud_3DS_6.pdf
http://nghiaho.com/?page_id=671
    [ x1.x x2.x ... xN.x ]       [ y1.x y2.x ... yN.x ]
X = [ x1.y x2.y ... xN.y ]   Y = [ y1.y y2.y ... yN.y ]
    [ x1.z x2.z ... xN.z ]       [ y1.z y2.z ... yN.z ]
                                  _____________________ 
solve s R X + t = Y              | t: translate vector |
                            2    | s: scalar vector    |
minimize ‖ Y - (s R X + t) ‖     | R: rotation matrix  |
                                  ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾ 
then t = Ȳ - s R X̄
      2      T         T          2        2
     s = ∑ Ŷi Ŷi ÷ ∑ X̂i X̂i = ‖ Ŷ ‖F ÷ ‖ X̂ ‖F
            T                  T       T
     R = V U    with C₃ₓ₃ = X̂ Ŷ = U Σ V 

令函數是位移、旋轉、縮放三個步驟。方便起見,把位移改為最終步驟。數據套用函數之後,令誤差越小越好。誤差訂為對應數據的距離的平方的總和。

最佳的位移量:兩堆數據各自的平均值相減,相減之前先讓第一個平均值套用函數。最佳的縮放量:兩堆數據各自的變異數相除。最佳的旋轉量:兩堆數據各自減去平均值(中心位移至原點)、除以變異數(大小縮放為相等),求得維度的共變異矩陣,實施奇異值分解,然後VUᵀ矩陣相乘,即是旋轉矩陣。

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

相關

不知道數據對應關係。兩堆數據數量不同。

兩堆數據各自計算PCA座標軸,然後對齊。

PCA座標軸容易因outlier而歪斜,導致此方法效果不佳。

http://www.cs.tau.ac.il/~dcor/Graphics/cg-slides/svd_pca.pptx
http://www.cse.wustl.edu/~taoju/cse554/lectures/lect07_Alignment.pdf
http://perception.inrialpes.fr/~Horaud/Courses/pdf/Horaud_3DS_5.pdf

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

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

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

Piecewise Alignment(Manifold Alignment)

https://en.wikipedia.org/wiki/Manifold_alignment

分段仿射變換

二維:三角形任取兩鄰邊當作座標軸。

三維:必須再加入法向量當作座標軸。

x4 = x1 + normal vector:
              (x2 - x1) × (x3 - x1)
x4 = x1 + -----------------------------
          sqrt(‖(x2 - x1) × (x3 - x1)‖)   為啥開根號

linear transformation of 3 vectors:
    [   |     |     |   ]        [   |     |     |   ]
V = [ x2-x1 x3-x1 x4-x1 ]    W = [ y2-y1 y3-y1 y4-y1 ]
    [   |     |     |   ]        [   |     |     |   ]
AV = W
A = WV⁻¹

affine transformation of 4 vertices:
A(xi - x1) = yi - y1   for i = 1~4
Axi - Ax1 + y1 = yi    for i = 1~4
Axi + b = yi   where b = y1 - Ax1

這種仿射變換的特色:內部、邊界、外部的點,變換之後,仍在內部、邊界、外部。

分段相似變換

追加限制條件:共用頂點。

留待Deformation章節介紹。

Inlier / Outlier

演算法(RANSAC)

一、甲堆隨機抓幾點,乙堆隨機抓幾點,點數一樣多,推定它們依序一一對應。
二、實施相似變換對齊(Procrustes Analysis),求得對齊函數。
三、計算「甲堆套用函數」與「乙堆」的誤差大小。
四、重複上述步驟,取誤差最小者。

適用於有outlier的情況。絕聖棄智,民利百倍。

演算法(Iterative Closest Point)

一、初始化:
 甲、實施相關對齊(PCA),求得對齊函數。
 乙、甲堆套用函數。讓甲堆靠近乙堆。
二、重複此步驟,直到最近點不變為止:
 甲、甲堆每一點找到在乙堆的最近點,建立對應關係。暫時無視乙堆其餘點。
 乙、依照對應關係,實施相似變換對齊(Procrustes Analysis),求得對齊函數。
 丙、甲堆套用函數。讓甲堆更靠近乙堆。
三、甲堆套用的所有函數,依序複合就是對齊函數。

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