Transformation

Transformation

「變換」。數據套用函數。數據轉換姿態、產生變化。

每筆數據皆套用同一個函數。改變了數據數值、數據維度。

1D → 1D       2D → 2D            1D → 3D          3D → 1D
x̕  = 2x + 1   { x̕ = x + y        { x̕ = 2x + 1     x̕  = x + yz
              { y̕ = x² + y²      { y̕ = 3x + 2
                                 { z̕ = 5x + 3
R¹ → R¹       R² → R²            R¹ → R³          R³ → R¹
y = 2x + 1    { y₁ = x₁ + x₂     { y₁ = 2x + 1    y = x₁ + x₂x₃
              { y₂ = x₁² + x₂²   { y₂ = 3x + 2
                                 { y₃ = 5x + 3
{ x̕ = fx(x,y,z)         (x̕,y̕,z̕) = F(x,y,z)
{ y̕ = fy(x,y,z)
{ z̕ = fz(x,y,z)         F: (x,y,z) ↦ (x̕,y̕,z̕)
{ y₁ = f₁(x₁,x₂,x₃)     (y₁,y₂,y₃) = F(x₁,x₂,x₃)
{ y₂ = f₂(x₁,x₂,x₃)
{ y₃ = f₃(x₁,x₂,x₃)     F: (x₁,x₂,x₃) ↦ (y₁,y₂,y₃)

每筆數據套用不同函數,目前無人討論。增生數據、消滅數據,目前亦無人討論。這類變換,可以想成是擁有if判斷式的函數,每筆數據根據判斷結果實施不一樣的行為。可是數學家不討論這種函數,只討論連續函數、可微函數。

Inverse Transformation

「反向變換」。數據再套用反函數。數據打回原形。

原函數存在反函數,才能反向變換。

然而目前沒有演算法可以判斷反函數、求得反函數!除了少數特例:一元一次函數,以移項求得反函數;一次函數,以高斯喬登消去法求得反函數;數學家發明的特殊函數,例如傅立葉轉換,以推理方式求得反函數。

Dual Transformation【數學家稱作對合Involution】

「對偶變換」。原函數、反函數,兩者恰好相同。變換兩次等同變換零次。

例如f(x) = -x與f⁻¹(x) = -x。又例如f(x) = 1/x與f⁻¹(x) = 1/x。

對應運算【數學家稱作分配律Distributive Law】

針對一個變換,輸入和輸出有時候擁有某些對應運算。

例如f(x) = 2ˣ。輸入相加等同輸出相乘。我們可以先相加、再變換,也可以先變換、再相乘,效果相同。

存在反向變換時,運算可以繞路。

例如f(x) = log₂x與f⁻¹(x) = 2ˣ。輸入相乘等同輸出相加。我們可以直接相乘,也可以正向變換、相加、反向變換。

Dual Operation

存在對偶變換時,對應運算必定互相對稱,稱作「對偶運算」。

例如補集函數f(A) = Aᶜ與f⁻¹(A) = Aᶜ。輸入交集等同輸出聯集,輸入聯集也等同輸出交集。對偶運算是交集對聯集。

原函數、反函數,當兩者幾乎相同,有時候也會產生對偶運算。

例如正向傅立葉轉換、逆向傅立葉轉換,差異在於除與乘。對偶運算是乘法對卷積。

Preserving Transformation

X-Preserving Transformation
X-Invariant Transformation

「保X變換」。數據變換之後,特性X依然存在。

所謂的特性,就是替數據設立指數、指標,例如長度、距離、角度、中位數、平均數、變異數。

「X不變變換」。數據經過X修改,變換之後依然沒有差別。

所謂的修改,就是數據的運算、操作,例如取絕對值、取整數、取餘數、位移、縮放、旋轉。

事實上,所謂的特性、所謂的修改,本質都是函數X。

保X變換:輸入輸出套用X,結果一致。能夠保存精髓。
X不變變換:輸入套用X,輸出一致。能夠容忍異常。
X-preserving transformation: F:x↦x̕ where X(x) = X(x̕)
X-invariant transformation:  F:x↦x̕ where F(x) = F(X(x)) = x̕

事實上,保X變換、X不變變換,其實是F和X對調。

註:X-Preserving Transformation的X稱作「不變量Invariant」。X-Invariant Transformation故意採用相同單字,混淆視聽。

保長(Length Preserving)

任一點,變換前後,長度保持相同。

旋轉、鏡射是保長變換。位移、縮放、投影不是保長變換。

保距(Distance Preserving)(Isometric)

任兩點,變換前後,距離保持相同。

位移、旋轉、鏡射是保距變換。縮放、投影不是保距變換。

保角(Angle Preserving)(Isogonal)

任相鄰三點,變換前後,夾角保持相同。

位移、旋轉、鏡射、整體縮放是保角變換。投影不是保角變換。

除了實數函數,大家也討論複數函數。舉例來說,四則運算、倒數、平方、平方根是保角變換。有時格線呈現曲線。

保長則保距,保距則保角。

保定向(Orientation Preserving)

變換前後,方位保持相同。有旋轉、無鏡射。

共形(Shape Preserving)(Conformal)

變換前後,形狀保持相同。保角且保定向。

保角細分為:無鏡射保角Conformal、有鏡射保角Reflective Conformal、兩種混合Isogonal。

簡單來說:有向角度相同Conformal、有向角度變號Reflective Conformal、有向角度絕對值相同Isogonal。

位移不變(Translation Invariant)

即便輸入實施位移,輸出依然相同。

縮放不變(Scaling Invariant)

即便輸入實施縮放,輸出依然相同。

旋轉不變(Rotation Invariant)

即便輸入實施旋轉,輸出依然相同。

Harmonic Transformation

Differentiation of Transformation【尚無正式名稱】

變換函數,一次微分,得到各維度的各維度縮放倍率。

F: (x,y) ↦ (x̕,y̕)

∇F = [ ∂x̕/∂x ∂y̕/∂x ]
     [ ∂x̕/∂y ∂y̕/∂y ]

Fx = [ ∂x̕/∂x ]   Fy = [ ∂x̕/∂y ]
     [ ∂y̕/∂x ]        [ ∂y̕/∂y ]

∇F = [ — Fxᵀ — ]   J = ∇Fᵀ = [ Fx Fy ]
     [ — Fyᵀ — ]             [  |  | ]

想像∂x = ∂y = 1,還可以得到幾何量。

angle                      = (Fx ∙ Fy) / (‖Fx‖ ‖Fy‖)
area                       = ‖Fx × Fy‖
side length                = ‖Fx‖ and ‖Fy‖
sum of squared side length = ‖Fx‖² + ‖Fy‖² = ‖∇F‖F²

累計你喜歡的輸入範圍,得到對應的輸出範圍的幾何量。

total area                = ∫ ‖Fx × Fy‖
total squared side length = ∫ (‖Fx‖² + ‖Fy‖²) = ∫ ‖∇F‖F²
(Dirichlet energy)

順帶一提,寫成奇異值的形式,更加簡潔。

area                       = ‖Fx × Fy‖ = σ₁σ₂
sum of squared side length = ‖Fx‖² + ‖Fy‖² = ‖∇F‖F² = σ₁² + σ₂²

順帶一提,數學家比較喜歡Jacobian Matrix。微分並轉置是Jacobian Matrix。Fx和Fy是它的直條。轉置不影響矩陣長度。

squared sum of side length = ‖Fx‖² + ‖Fy‖² = ‖∇F‖F² = sum σᵢ²
                           = ‖Jᵀ‖F² = ‖J‖F²

Isogonal Transformation
Harmonic Transformation

「保角變換」。保留角度。梯度各維度,長度均等、角度垂直。

「和諧變換」。調勻長度。梯度各維度,兩側差異,總計為零。

F: (x,y,z) ↦ (x̕,y̕,z̕)

     [ ∂x̕/∂x ]         [ ∂²x̕/∂x² ]
Fx = [ ∂y̕/∂x ]   Fxx = [ ∂²y̕/∂x² ]
     [ ∂z̕/∂x ]         [ ∂²z̕/∂x² ]

     [ ∂x̕/∂y ]         [ ∂²x̕/∂y² ]
Fy = [ ∂y̕/∂y ]   Fyy = [ ∂²y̕/∂y² ]
     [ ∂z̕/∂y ]         [ ∂²z̕/∂y² ]

     [ ∂x̕/∂z ]         [ ∂²x̕/∂z² ]
Fz = [ ∂y̕/∂z ]   Fzz = [ ∂²y̕/∂z² ]
     [ ∂z̕/∂z ]         [ ∂²z̕/∂z² ]

isogonal: ‖Fx‖ = ‖Fy‖ = ‖Fz‖ and (Fx ⟂ Fy and Fy ⟂ Fz and Fx ⟂ Fz)
harmonic: Fxx + Fyy + Fzz = 0

Cauchy-Riemann Equation
Laplace Equation

二維的情況下,無鏡射保角是Cauchy-Riemann Equation。

任意維的情況下,和諧是Laplace Equation。

F: (x,y) ↦ (x̕,y̕)

∇F = [ ∂x̕/∂x ∂y̕/∂x ] = [ a b ]
     [ ∂x̕/∂y ∂y̕/∂y ]   [ c d ]

conformal (Cauchy-Riemann equation):
{ ∂x̕/∂x =  ∂y̕/∂y       { a =  d
{ ∂x̕/∂y = -∂y̕/∂x       { c = -b

reflective conformal:
{ ∂x̕/∂x = -∂y̕/∂y       { a = -d
{ ∂x̕/∂y =  ∂y̕/∂x       { c =  b

harmonic (Laplace equation of 2-vector):
{ ∂²x̕/∂x² + ∂²x̕/∂y² = 0
{ ∂²y̕/∂x² + ∂²y̕/∂y² = 0

定理:保角則和諧

Cauchy-Riemann Equation兩式分別對x和y微分,相加合併,得到Laplace Equation。

另一種解釋方式。顛倒Y軸,y改成-y,Cauchy-Riemann Equation兩式分別是無散場、無旋場。Laplace Equation是諧場。根據散旋諧分解,無散無旋必諧。

此處只證明了二維的情況。三維以上我不知道怎麼證明。

保長則保距,保距則保角,保角則和諧。四天王登場!

Optimization of Transformation【尚無正式名稱】

盡量保角:梯度差平方盡量小。

盡量和諧:梯度平方和盡量小。

梯度差平方當中,無鏡射保角轉+90°、有鏡射保角轉-90°。

least squares isogonal: minimize ‖Fy - ±Fx‖²
least squares harmonic: minimize ‖Fx‖² + ‖Fy‖² = ‖∇F‖F²

順帶一提,寫成奇異值的形式,更加簡潔。

least squares isogonal: minimize (σ₁ - σ₂)²
least squares harmonic: minimize (σ₁² + σ₂²)

定理:當面積固定,盡量保角即盡量和諧。

梯度平方和-梯度差平方=面積的兩倍。

數學式子可以寫成梯度形式、奇異值形式。

https://math.stackexchange.com/questions/2931675/

(‖Fx‖² + ‖Fy‖²) - ‖Fy - ±Fx‖² = ±2(Fx × Fy)      local
(σ₁² + σ₂²) - (σ₁ - σ₂)² = 2σ₁σ₂                  local
Dirichlet energy - isogonal energy = 2 ⋅ area     global

定理:面積最大值、梯度平方和最小值,兩者夾擠導致保角。

梯度平方和≥面積的兩倍。

等號成立時為保角。

  ‖Fx‖² + ‖Fy‖²            梯度平方和
≥ 2 ‖Fx‖ ‖Fy‖              算幾不等式
≥ 2 ‖Fx‖ ‖Fy‖ |sinθ|       0 ≤ |sinθ| ≤ 1
= 2 ‖Fx × Fy‖              面積的兩倍

等號成立時,‖Fx‖ = ‖Fy‖且|sinθ| = 0。
梯度相等且夾角±90度,也就是保角。

Affine Transformation

Linear Transformation
Affine Transformation

「線性變換」。變換時,採用線性函數。

「仿射變換」。變換時,採用仿射函數。

線性函數:加性函數、倍性函數
仿射函數:加性函數、倍性函數、常數項
linear function f             affine function g
1. f(x + y) = f(x) + f(y)     1. f(x + y) = f(x) + f(y)
2. f(kx) = k f(x)             2. f(kx) = k f(x)
                              3. g(x) = f(x) + c

計算學傾向討論狹義版本。

狹義線性函數:變數加變數、變數乘常數
狹義仿射函數:變數加變數、變數乘常數、變數加常數
linear function     affine function       non-affine function
{ x̕ = x + 2y        { x̕ = x + 2y + 1      { x̕ = xy
{ y̕ = 2(x + y)      { y̕ = 2(x + y + 5)    { y̕ = sin(x) + cos(y)

可以重新整理為標準形式。

狹義線性函數:變數乘上倍率,通通相加。
狹義仿射函數:線性函數,再加上常數項(位移)。
linear function     affine function       non-affine function
{ x̕ = x + 2y        { x̕ = x + 2y + 1      { x̕ = xy
{ y̕ = 2x + 2y       { y̕ = 2x + 2y + 5     { y̕ = sin(x) + cos(y)

可以重新整理為標準形式。向量版本。

狹義線性函數:任意矩陣
狹義仿射函數:任意矩陣→任意向量(位移)
linear transformation: x̕ = Ax
affine transformation: x̕ = Ax + b

Representation of Transformation【尚無正式名稱】

一筆數據的變換,可以寫成函數形式。

{ x̕ = fx(x,y,z) = ax + by + cz + p
{ y̕ = fy(x,y,z) = dx + ey + fz + q
{ z̕ = fz(x,y,z) = gx + hy + iz + r
  x̕      F(x)

一筆數據的線性變換、仿射變換,可以寫成矩陣形式。

[ x̕ ]   [ a b c ] [ x ]   [ p ]
[ y̕ ] = [ d e f ] [ y ] + [ q ]
[ z̕ ]   [ g h i ] [ z ]   [ r ]
  x̕         A       x       b

大量數據的線性變換、仿射變換,共兩種形式。

數學家:數據併成矩陣。

[ x̕₁ x̕₂     ]   [ a b c ] [ x₁ x₂     ]   [ p p     ]
[ y̕₁ y̕₂ ... ] = [ d e f ] [ y₁ y₂ ... ] + [ q q ... ]
[ z̕₁ z̕₂     ]   [ g h i ] [ z₁ z₂     ]   [ r r     ]
     X̕              A          X              B     

計算學家:數據併成向量,變換矩陣形成大規模稀疏矩陣。

[ x̕₁ ]   [ a b c 0 0 0 0 0 0 ... ] [ x₁ ]   [ p ]
[ y̕₁ ]   [ d e f 0 0 0 0 0 0 ... ] [ y₁ ]   [ q ]
[ z̕₁ ]   [ g h i 0 0 0 0 0 0 ... ] [ z₁ ]   [ r ]
[ x̕₂ ] = [ 0 0 0 a b c 0 0 0 ... ] [ x₂ ] + [ p ]
[ y̕₂ ]   [ 0 0 0 d e f 0 0 0 ... ] [ y₂ ]   [ q ]
[ z̕₂ ]   [ 0 0 0 g h i 0 0 0 ... ] [ z₂ ]   [ r ]
[ :  ]   [ : : : : : : : : :     ] [ :  ]   [ : ]
[ :  ]   [ : : : : : : : : :     ] [ :  ]   [ : ]
  x̕                  A               x        b

Homogeneous Coordinates

仿射函數偽裝成線性函數。新添一個變數,只能代入1,乘在常數項。這個手法稱作「齊次座標」。

affine function       homogeneous coordinates
{ x̕ = x + 2y + 1      { x̕ = x + 2y + 1z    (z = 1)
{ y̕ = 2x + 2y + 5     { y̕ = 2x + 2y + 5z   (z = 1)

換句話說。矩陣添加一個新維度,將常數項併入矩陣。數據隨之添加一個新維度,數值固定為1。這個手法稱作「齊次座標」。

affine function                      homogeneous coordinates
[ x̕ ]   [ a b c ] [ x ]   [ p ]      [ x̕ ]   [ a b c p ] [ x ]
[ y̕ ] = [ d e f ] [ y ] + [ q ]      [ y̕ ] = [ d e f q ] [ y ]
[ z̕ ]   [ g h i ] [ z ]   [ r ]      [ z̕ ]   [ g h i r ] [ z ]
  x̕         A       x       b        [ 1 ]   [ 0 0 0 1 ] [ 1 ]
                                       x̕ₕ         Aₕ       xₕ

優點:多個仿射變換可以複合成一個仿射變換,只需儲存一個變換矩陣。缺點:實施變換,計算步驟較多。

Differentiation of Transformation【尚無正式名稱】

給定變換函數,可以利用微分,求得變換矩陣。

d/dx (ax + b) = a。一次函數實施微分,得到首項係數。

d/dx (Ax + b) = Aᵀ。輸入推廣成向量,係數推廣成矩陣。

線性變換函數、仿射變換函數,微分並轉置,得到變換矩陣。

affine transformation
(x̕,y̕,z̕) = F(x,y,z)

function representation
{ x̕ = fx(x,y,z) = ax + by + cz + p
{ y̕ = fy(x,y,z) = dx + ey + fz + q
{ z̕ = fz(x,y,z) = gx + hy + iz + r

matrix representation
[ x̕ ]   [ a b c ] [ x ]   [ p ]
[ y̕ ] = [ d e f ] [ y ] + [ q ]
[ z̕ ]   [ g h i ] [ z ]   [ r ]

transpose of derivative is transformation matrix
                 [ ∂/∂x fx  ∂/∂y fx  ∂/∂z fx ]   [ a b c ]
F′(x,y,z)ᵀ = J = [ ∂/∂x fy  ∂/∂y fy  ∂/∂z fy ] = [ d e f ]
                 [ ∂/∂x fz  ∂/∂y fz  ∂/∂z fz ]   [ g h i ]

微分並轉置,就是Jacobian Matrix。導致大家鮮少講「Transformation Matrix」,數學家習慣講「Jacobian Matrix of Transformation」,物理學家習慣講「Deformation Gradient」。

derivative:            F′ = ∇F = Jᵀ = Aᵀ
transformation matrix: F′ᵀ = ∇Fᵀ = J = A
Dirichlet energy:      ‖F′‖F² = ‖∇F‖F² = ‖J‖F² = ‖A‖F²

Approximation of Transformation【尚無正式名稱】

一般的變換,通常無法求出最近似仿射變換。

標準做法是誤差盡量小。原本變換與最近似仿射變換,兩者的輸出的平方誤差,所有輸入通通計入。

誤差總和通常是無限大,最小值通常是不存在。

min sum ‖F(x) - Ax‖²
 A   x

一般的變換,只能求出局部的最近似仿射變換。

泰勒級數於特定點展開,一階係數(Jacobian Matrix)作為變換矩陣,剩餘部分作為位移向量。

Taylor series at (xₒ,yₒ,zₒ)
                                    [ x-xₒ ]
F(x,y,z) = F(xₒ,yₒ,zₒ) + F′(x,y,z)ᵀ [ y-yₒ ] + ...
                                    [ z-zₒ ]
           ^^^^^^^^^^^   ^^^^^^^^^^^^^^^^^^^
             order 0           order 1
                      [ x ]                            [ xₒ ]
F(x,y,z) = F′(x,y,z)ᵀ [ y ] + F(xₒ,yₒ,zₒ) - F′(x,y,z)ᵀ [ yₒ ] + ...
                      [ z ]                            [ zₒ ]
           ^^^^^^^^^^ ^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                A       x                        b
transformation matrix A: F′(x)ᵀ = J
   translation vector b: F(x) - F′(x)ᵀx = F(x) - Jx
一、最近似線性變換矩陣:變換函數,微分並轉置(Jacobian Matrix)。
二、最近似位移向量:變換函數,減去最近似線性變換。

最近似線性變換矩陣,恰好也是Jacobian Matrix。太棒了!

我不確定平方誤差是否最小。【尚待確認】

Decomposition of Transformation【尚無正式名稱】

變換矩陣可以分解,得到富有意義的矩陣們。

奇異值分解,得到旋轉鏡射矩陣、縮放矩陣、旋轉鏡射矩陣。

SVD(J) = UΣVᵀ
U and Vᵀ are rotation/reflection. (orthonormal)
Σ is scaling. (diagonal matrix)

極分解,得到旋轉鏡射矩陣、可正交對角化矩陣。

polar(J) = RS
R = UVᵀ is rotation/reflection. (orthonormal)
S = VΣVᵀ is orthogonally diagonalizable. (symmetric positive semidefinite)

另一種極分解,得到可正交對角化矩陣、旋轉鏡射矩陣。

polar(J) = SR
S = UΣUᵀ is orthogonally diagonalizable. (symmetric positive semidefinite)
R = UVᵀ is rotation/reflection. (orthonormal)

奇偶分解,得到主縮放矩陣、主旋轉矩陣。【尚待確認】

even(J) = (J + Jᵀ) / 2 is principal scaling. (symmetric)
odd(J)  = (J - Jᵀ) / 2 is principal rotation. (skew-symmetric)

經典的線性變換、仿射變換

大家經常使用仿射變換。優點是只有加法與倍率,相當單純,擁有漂亮數學性質,擁有高速演算法。缺點是單純導致功效不彰。期待大家發明更特別的變換!

單一數據的變換:位移translate、縮放scale、旋轉rotate、投影project、鏡射reflect。請見本站文件「Transformation」。

全體數據的變換:中心化centering、標準化standardization、白化whitening。請見本站文件「Correlation」。

局部數據的變換:均值mean filter、差分difference filter、加權平均weighted average filter。請見本站文件「Filter」。

Similar Transformation

楔子:仿射變換與四天王

保長仿射變換:旋轉、鏡射
保距仿射變換:旋轉、鏡射、位移
保角仿射變換:旋轉、鏡射、均勻縮放、位移
和諧仿射變換:旋轉、鏡射、縮放、位移

和諧仿射變換=仿射變換。一次函數的二次微分為零。

因此不需要再發明五人戰隊、六大屬性,到此為止了。

Isometric Affine Transformation
Isogonal Affine Transformation

「保距仿射變換」。形狀不變。

「保角仿射變換」。尺寸可變。

可以用經典變換湊得。任意數量、任意順序。

保距仿射變換:旋轉、鏡射、位移
保角仿射變換:旋轉、鏡射、均勻縮放、位移
isometric affine: rotation, reflection, translation
isogonal affine:  rotation, reflection, isotropic scaling, translation

可以重新整理為標準形式。依序各一個。

保距仿射變換:正規正交(旋轉鏡射)→位移
保角仿射變換:正規正交(旋轉鏡射)→均勻非負縮放→位移
linear:           x̕ = Ax
affine:           x̕ = Ax + b
isometric affine: x̕ = Qx + t    (Q is orthonormal)
isogonal affine:  x̕ = sQx + t   (Q is orthonormal and s ≥ 0)

Rigid Transformation
Similar Transformation

「剛體變換」。保距仿射變換,但不允許鏡射。

「相似變換」。保角仿射變換,但不允許鏡射。

可以用經典變換湊得。任意數量、任意順序。

剛體變換:旋轉、位移
相似變換:旋轉、均勻非負縮放、位移
rigid:   rotation, translation
similar: rotation, isotropic scaling, translation

數學式子可以重新整理為標準形式。依序各一個。

剛體變換:旋轉→位移
相似變換:旋轉→均勻非負縮放→位移
linear:  x̕ = Ax
affine:  x̕ = Ax + b
rigid:   x̕ = Rx + t    (R is orthonormal and det(R) = 1)
similar: x̕ = sRx + t   (R is orthonormal and det(R) = 1 and s ≥ 0)

Approximation of Transformation【尚無正式名稱】

一般的變換函數,可以利用泰勒級數、奇異值分解,求出局部的最近似剛體變換、最近似相似變換。

一、最近似線性變換矩陣:變換函數,微分並轉置(Jacobian Matrix)。
二、最近似位移向量:變換函數,減去最近似線性變換。
三、最近似旋轉矩陣、最近似縮放倍率:最近似線性變換矩陣,奇異值分解。
四、偵測鏡射、去除鏡射。

已經介紹一二,以下介紹三四。

奇異值分解可以得到最佳解。證明請見本站文件「Orthogonal Procrustes Theorem」,其中A換成I、B換成J。

最近似剛體變換:旋轉矩陣、最近似線性變換矩陣,令兩者差異盡量小。
最近似相似變換:旋轉矩陣乘上非負縮放倍率、最近似線性變換矩陣,令兩者差異盡量小。
best rigid:   minimize ‖R - J‖F²
best similar: minimize ‖sR - J‖F²

奇異值分解得到正規正交奇異向量、非負奇異值,恰好適合作為旋轉矩陣、非負縮放倍率。

最近似旋轉矩陣:奇異向量的兩個矩陣相乘
最近似縮放倍率:奇異值的平均數
SVD:           J = UΣVᵀ = u₁σ₁v₁ᵀ + u₂σ₂v₂ᵀ + ... + uₙσₙvₙᵀ
best rotation: R = UVᵀ = ⧚J⧛
best scalar:   s = trace(Σ)/n = (σ₁+σ₂+...+σₙ)/3
最近似剛體變換矩陣:奇異值分解,抽掉倍率。
最近似相似變換矩陣:倍率平均數。從中間提到左邊。
best rigid:   R = UVᵀ = ⧚J⧛
best similar: sR = trace(Σ)/n UVᵀ = (σ₁+σ₂+...+σₙ)/3 UVᵀ

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

去除鏡射:挑選一個奇異值變號。因為旋轉矩陣公式沒有納入奇異值,所以改成對應的奇異向量變號(u與v擇一變號)。挑選絕對值最小的奇異值的奇異向量,讓誤差增加最少。

旋轉:偵測鏡射:矩陣是左手座標系。去除鏡射:取一個向量變號。
倍率:偵測鏡射:倍率是負數。去除鏡射:取絕對值。(奇異值非負,不必檢查。)
位移:不必檢查。

誤差最小值:奇異值的差異平方總和。

去除鏡射的誤差最小值:最小的奇異值變號。

min ‖R - J‖F² = (1-σ₁)² + (1-σ₂)² + ... + (1-σₙ)²
min ‖sR - J‖F² = (σavg-σ₁)² + (σavg-σ₂)² + ... + (σavg-σₙ)²
  min ‖sR - J‖F²
= ‖sUVᵀ - UΣVᵀ‖F²
= ‖U(sI)Vᵀ - UΣVᵀ‖F²
= ‖U(sI-Σ)Vᵀ‖F²
= ‖sI-Σ‖F²
= (s-σ₁)² + (s-σ₂)² + ... + (s-σₙ)²
= (σavg-σ₁)² + (σavg-σ₂)² + ... + (σavg-σₙ)²

最近似演算法:轉換到頻域,修改高頻、保留低頻。

泰勒級數,取低頻,得到最近似仿射變換。奇異值分解,取低頻,得到最近似相似變換。所謂近似,就是低頻!

Approximation of Transformation【尚無正式名稱】

二維仿射變換函數,可以解方程組,求出最近似剛體變換、最近似相似變換。

best similar: min ‖S - A‖F²
best rigid:   min ‖R - A‖F²

二維旋轉矩陣有著特定形式。二維相似變換矩陣有著特定形式。

S = [ α -β ] , s = sqrt(α² + β²) , R = S / s
    [ β  α ]

min ‖S - A‖F²

min ‖ [ α -β ] - [ a b ] ‖²
    ‖ [ β  α ]   [ c d ] ‖F

min (α - a)² + (-β - b)² + (β - c)² + (α - d)²

solve { 2(α - a) + 2(α - d) = 0
      { -2(-β - b) + 2(β - c) = 0

{ α = (a + d) / 2
{ β = (c - b) / 2

S = [ (a+d)/2  (b-c)/2 ]
    [ (c-b)/2  (a+d)/2 ]

Decomposition of Transformation【尚無正式名稱】

剛體變換、相似變換,可以分解成縮放倍率、旋轉矩陣。

縮放倍率:變換矩陣任意向量的長度
旋轉矩陣:變換矩陣每個元素通通除以縮放倍率

亦得採用奇異值分解,但是時間複雜度較高。順帶一提,奇異值即是縮放倍率,奇異值可以判斷保距仿射、保角仿射、保容積仿射。

isometric affine: σ₁ = σ₂ = σ₃ = 1
isogonal affine:  σ₁ = σ₂ = σ₃
equiareal affine: σ₁σ₂σ₃ = 1

Optimization of Transformation【尚無正式名稱】

跟保距仿射變換、保角仿射變換的差異盡量小。

可以寫成奇異值形式。奇異值是縮放倍率的絕對值。

盡量保距仿射:令奇異值接近1
盡量保角仿射:令奇異值接近奇異值平均數
least squares isometric affine: minimize (σ₁-1)² + (σ₂-1)²
least squares isogonal affine:  minimize (σ₁-σavg)² + (σ₂-σavg

也可以寫成矩陣形式。奇偶分解,令偶部縮放、奇部旋轉。

盡量保距仿射:令偶部接近I【尚待確認】
盡量保角仿射:令偶部接近奇異值平均數乘上I【尚待確認】
least squares isometric affine: minimize ‖(A + Aᵀ)/2 - I‖²
least squares isogonal affine:  minimize ‖(A + Aᵀ)/2 - (trace(A)/n)I‖²

定理:盡量不鏡射保角仿射=盡量相似

根據定義,不鏡射保角仿射conformal affine=相似similar。

加上「盡量」兩個字,依然成立。

least squares conformal affine: minimize ‖Fy - Fx‖²
least squares similar:          minimize ‖S - A‖F²
∇F = Aᵀ = [ a b ]   Fx = [ a ]   Fy = [ c ]   Fx = [ -b ]
          [ c d ]        [ b ]        [ d ]          [  a ]

‖Fy - Fx‖² = (b + c)² + (d - a)² 

A = [ a c ]   S = [ ½(a+d) ½(c-b) ]   S - A = [ -½(a-d) -½(b+c) ]
    [ b d ]       [ ½(b-c) ½(a+d) ]           [ -½(b+c)  ½(a-d) ]

‖S - A‖F² = ½(b + c)² + ½(d - a)²

Degree of Freedom

「自由度」。所有變數的數值範圍的維度,是rank不是dim。

自由度用於估計窮舉法的時間複雜度、空間複雜度。

換句話說。實施窮舉時,至少需要的變數數量。想要精確表達每一個不同的變換,至少需要的參數數量。儘可能精簡數量。

                  preserve  dof (2D)    dof (3D)
--------------------------------------------------
isometric affine  distance  3 (2t1r  )  6 (3t3r  ) ↑ strong
isogonal affine   angle     4 (2t1r1s)  7 (3t3r1s) ↓ weak
equiareal affine  volume    4 (2t1r1s)  8 (3t3r2s)

不允許鏡射,自由度仍相同。

非負縮放倍率,數值範圍少了半邊。若想錙銖必較,也許將自由度減個0.5,但是沒人這麼做就是了。

         preserve                dof (2D)    dof (3D)  
-------------------------------------------------------
rigid    distance & orientation  3 (2t1r  )  6 (3t3r  ) ↑ strong
similar  angle & orientation     4 (2t1r1s)  7 (3t3r1s) ↓ weak

Projective Transformation

Projective Geometry

http://users.umiacs.umd.edu/~ramani/cmsc828d/ProjectiveGeometry.pdf

若隱若現的布幕上面,看見一個黑點影子,無法判斷實物位置,只好將一個黑點想成是源自一整條直線。表面上是點,背地裡是線。一個點代表一條線。

為了實現這個點子,數學家創造了「射影幾何」。

Element in Projective Geometry

射影幾何的基本元件是「過原點直線」。

過原點直線,各點皆平等,可以任選一點當代表。但是為了辨別不同的過原點直線,不得挑選原點當代表。

一條過原點直線簡化成一點。一點表示一條過原點直線。

過原點直線的代表點,座標值一齊乘上任意非零倍率,仍位於同一條直線,仍屬於同一個元件,仍是代表點。

我們可以隨意挑選代表點,也可以放置布幕得到代表點。布幕與過原點直線的交點,當作代表點。布幕可以是任意曲面,但是布幕與每一條過原點直線都必須剛好一個交點,以免產生混淆。

教科書繪製圖片,習慣放置布幕,令布幕是平面。

Operation in Projective Geometry

代表點、代表線(兩個代表點的連線)的運算。

點:過原點直線。點座標:方向向量。

線:過原點平面。線座標:法向量。

兩點外積得連線:兩條過原點直線的方向向量的外積,得到兩線構成的平面的法向量。

兩線外積得交點:兩個過原點平面的法向量的外積,得到兩面的交線的方向向量。

點(x,y,z)   ---> (x,y,z)     三個座標值一齊乘上任意非零倍率,視為相同元件
線ax+by+c=0 ---> (a,b,c)     三個座標值一齊乘上任意非零倍率,視為相同元件
兩點連線    ---> p₁ × p₂
兩線交點    ---> l₁ × l₂
點線相交    ---> p ∙ l = 0
兩線平行    ---> l₁ × l₂ = (-,-,0)

Function in Projective Geometry

射影幾何當中,函數的輸入輸出是代表點的座標值。

{ x̕ = fx(x,y,z)
{ y̕ = fy(x,y,z)   or   (x̕,y̕,z̕) = F(x,y,z)
{ z̕ = fz(x,y,z)

射影幾何當中,傾向討論倍性函數。代表點具備「乘上任意非零倍率,視為相同元件」之特性,為了滿足此特性,一種方式是採用倍性函數:輸入倍率等同輸入倍率。

(kx̕,ky̕,kz̕) = F(kx,ky,kz)

計算學家傾向討論線性函數。數學家傾向討論雙射線性函數。

[ x̕ ]   [ a b c ] [ x ]
[ y̕ ] = [ d e f ] [ y ]
[ z̕ ]   [ g h i ] [ z ]

射影幾何當中,這四項都等價於雙射線性。【尚待確認】

一、射影幾何的線性變換。且擁有反向變換。
二、射影幾何的保共線變換(直線對應到直線)。且擁有反向變換。
三、兩個平面布幕的透視變換。焦點在任意固定位置。
四、兩臺相機的剛體變換,拍攝同一平面。兩個焦點在任意固定位置。

射影幾何當中,雙射線性又稱作homography。名稱源自第四項:本質相同的透視作圖。homo-是指本質相同,-graphy是指描寫記錄。

台灣將homography的中文翻譯誤植為homographic的中文翻譯,通通稱作「單應」。比較適當的翻譯也許是「同射」。

射影幾何的函數化作歐氏幾何的函數

一、輸入數據,新添尺度,尺度設為1。(齊次座標化)
二、套用射影幾何的函數。
三、輸出數據,尺度調成1,隱藏尺度。(反齊次座標化)
   (x,y)                input
-> (x,y,1)              homogenization
-> (x̕,y̕,k̕) = F(x,y,1)   projective transformation
-> (x̕/k̕, y̕/k̕, 1)        scaling
-> (x̕/k̕, y̕/k̕)           output

Affine Transformation
Projective Transformation

「仿射變換」。射影幾何的保平行變換的歐氏幾何化。

「射影變換」。射影幾何的保共線變換的歐氏幾何化。

射影幾何當中,保平行等同保距離比。

射影幾何當中,保共線等同保交比。

可以用射影幾何的線性變換湊得。任意數量、任意順序。

可以重新整理為標準形式。只有一個。

[ x̕ ]   [ a b c ] [ x ]
[ y̕ ] = [ d e f ] [ y ]
[ k̕ ]   [ g h i ] [ 1 ]

Approximation of Transformation【尚無正式名稱】

查無資料。

Decomposition of Transformation【尚無正式名稱】

查無資料。

Optimization of Transformation【尚無正式名稱】

查無資料。

Degree of Freedom

            preserve      preserve        dof (2D)  dof (3D)
------------------------------------------------------------
linear      origin        length-ratio    4         9        ↑ strong
affine      parallel      distance-ratio  6         12       |
projective  collinearity  cross-ratio     8         15       ↓ weak

也許存在保和諧比變換,只是我不知道那是什麼。

Coordinate

集合(Set)、元組(Tuple)

多物視作一物。差別在於:

集合的元素不分先後,無視重複元素。採用大括號。

元組的元素區分先後,允許重複元素。採用小括號。

set       tuple
{4,5,7}   (5,4,7)
{1,2,3}   (1,1,2,2,3,3)
{●,▲,■}   (●,■,▲,◆,▲)
{}        ()

空間(Space)

空間即是集合,並且裝備特殊技能。

此處的空間,是數學術語,不是物理學術語。此處的空間,是指一堆東西,不是指立體容積。

常見的空間元件:幾何的「點」、代數的「向量」。

  topological space 拓樸空間 一堆點,裝備鄰居        彈性形狀
       metric space 距離空間 一堆點,裝備距離        相似程度
    Euclidean space 歐氏空間 一堆點,裝備長、角、位移、旋轉 幾何圖形
       vector space 向量空間 一堆向量,裝備加法、倍率    加權平均
inner product space 內積空間 一堆向量,裝備加法、倍率、內積 相對方位

座標(Coordinate)

空間裡每個元素,分別設定獨一無二的tuple,tuple裡面是數字。一種設定方式稱作一種「座標系coordinate system」。tuple的一個欄位稱作一種「座標coordinate」。中文則習慣把所有欄位合稱「座標coordinates」。

大家習慣令不同元素擁有不同座標、相鄰元素擁有相鄰座標、座標欄位數量符合維度大小。

歐氏空間的直角座標系(Cartesian Coordinate System)

大家熟知的一維數線、二維平面、三維空間,都是歐氏空間。

歐氏空間的點,無限多、無限小、無限綿密,不易製圖。製圖時,不會畫點,而是意思意思畫座標軸。

挑選任意一點作為原點,挑選任意方向作為X軸方向,其餘座標軸互相垂直,滿足右手座標系。

歐氏空間的其他經典的座標系

大家熟知的直角座標系,其實是歐氏空間的其中一種座標系。

tuple的每個欄位,設定成長度、角度,得到其他座標系。

  Cartesian coordinate system 直角座標系 長度、……     任意維
      polar coordinate system 極座標系  長度、角度    二維
  spherical coordinate system 球座標系  長度、角度、角度 三維
cylindrical coordinate system 圓柱座標系 長度、長度、角度 三維

製圖時,畫格線,容易辨認座標系。

UVa 12323

座標系寫成函數組

以直角座標系當作預設座標系,各種座標系得以寫成函數組。一個函數求得一個維度的座標。

函數組是一對一函數:不同地點擁有不同座標。函數組是連續函數:相鄰地點擁有相鄰座標。函數組的輸入變數與輸出變數一樣多:座標欄位數量符合維度大小。

更換座標系(Coordinate System Transformation)

拆成兩步驟:先套用舊座標系的反函數組、再套用新座標系的函數組。

數學當中,更換座標系是重新貼標籤,不會改變點。計算學當中,更換座標系是變換,用來改變數據。

Basis Coordinates

Basis Coordinates【尚無正式名稱】

「基底座標」。自行指定原點、座標軸。

座標變點:座標軸併成矩陣。套用矩陣,加上原點。

點變座標:減去原點,套用反矩陣。

Affine Coordinates【尚無正式名稱】

「仿射座標」。三個點決定唯一一種仿射變換。

採用射影幾何。三個點尺度設為一,當作基底,併成矩陣。

射影幾何不必在乎倍率。反矩陣改成伴隨矩陣。三點共線時,反矩陣不存在,而伴隨矩陣總是存在。

Projective Coordinates【尚無正式名稱】

「射影座標」。四個點決定唯一一種射影變換。

一、採用射影幾何。前三點尺度設為一,當作基底。求出第四點座標。

二、前三點分別乘上倍率,倍率是第四點座標。得到基底。

https://math.stackexchange.com/questions/296794/

Control Point

二維的情況下,仿射變換可以表示成三個控制點,投影變換可以表示成四個控制點。

控制點的位置,決定了變換函數。不同的控制點位置,得到不同的變換函數。

控制點初始位置,形成舊座標系。控制點當前位置,形成新座標系。變換函數就是更換座標系:先套用舊座標系的點變座標,再套用新座標系的座標變點。

當控制點形成凸多邊形,導致保凸變換:凸區域變換之後仍是凸區域。也就是說:控制點區域的內部/邊界/外部,變換之後,仍在內部/邊界/外部。

Natural Coordinates

Natural Coordinates(Weighted Average Coordinates)

運用加權平均數,創建座標系!

釘選數點,設定權重,令權重總和為一。

座標變點:給座標(權重),求點(加權平均數)。

點變座標:給點(加權平均數),求座標(權重)。

座標與點必須一一對應。以二維空間為例:兩點以下,不存在任何權重格式,可滿足一一對應;三點只有一種;四點以上有多種。

原理是Unisolvence Theorem。這裡就不證明了。

Triangular Coordinates(Affine Coordinates)

https://classes.soe.ucsc.edu/cmps160/Fall10/resources/barycentricInterpolation.pdf

「三角形座標」。等價於仿射變換。

座標變點:三個頂點的加權平均數。

點變座標:三塊三角形的面積比重。

Quadrilateral Coordinates

https://pdfs.semanticscholar.org/cdbb/5aa0b2ad612182dc9a75178082bb1804750a.pdf

https://www.particleincell.com/2012/quad-interpolation/

另一種「四邊形座標」。權重是斜對角的面積比重。由於權重太複雜,於是權重簡化為新參數。

座標變點:四個頂點的加權平均數。

點變座標:如連結。移項整理之後,解二次方程式。

Quadrilateral Coordinates

https://www.researchgate.net/publication/2534597

另一種「四邊形座標」。四個點,權重是對面邊界的距離比重。

座標變點:四個頂點的加權平均數。

點變座標:如連結。

Bilinear Interpolation

「雙一次內插」。四個點,權重是斜對角的面積比重。由於是矩形,兩個維度可以分開處理,權重是對面線段的長度比重。

座標變點:下方兩點做一次內插、左方兩點做一次內插。

點變座標:線段長度比重。

Barycentric Coordinates

「重心座標」。權重是面積比重,宛如求重心。

Triangular Coordinates
Quadrilateral Coordinates
Polygonal Coordinates

Polygonal Coordinates

「多邊形座標」。請參考專論《Barycentric Coordinates》

Wachspress Coordinates (convex polygon)
Mean Value Coordinates
Discrete Harmonic Coordinates

Cage Coordinates

額外的多邊形。請自行搜尋論文。

Green Coordinates
Cauchy‐Green Coordinates
Szegö Coordinates

Natural Neighbor Coordinates

大量點。請參考維基百科。

Sibson Coordinates
點變座標:加入該點,形成新的Voronoi Diagram。
新舊交集面積,當作權重。

Laplace Coordinates
點變座標:加入該點,形成新的Voronoi Diagram。
毗鄰區域的銜接處(二維是長度、三維是面積),除以兩點距離,當作權重。