最小平方法於圖形比對的應用

本文的閱讀等級:中級

大學理工科系教導學生的東西多屬那些可以用原則、定理、規則、案例講述的「法典知識」(coded knowledge)。欲提昇個人競爭力,我們還必須透過「同化」(assimilation) 將這些濃縮的法典知識轉變為「非法典知識」(non-coded knowledge)。所謂同化意指將新的概念或方法融入整合至已經存在的體系裡,常見的程序是先抽離出專業實務領域裡的元素與架構,再利用其他領域 (例如數學) 所發展出的概念和工具來解決原本的問題。下面我以一個圖形比對 (pattern matching) 問題為例解釋同化的操作過程。見下圖,左圖P和右圖Q分別由相同數量的界標點描述其形狀,假設已知兩組界標點之間的對應關係 (如紅色虛線所示),我們的問題是設計一個不受位移、旋轉、伸縮和輕度形變影響的圖形相似度測量方式。

基於仿射變換的圖形比對

 
令圖P和圖Q的界標序列座標分別為 (x_{i1},x_{i2})(y_{i1},y_{i2})i=1,\ldots,nn\ge 3。明顯地,直接計算對應界標點之間的距離並不能反映實際的型態差異,我們必須先將兩圖形放在可供比較的基準上,對準 (alignment) 是常見的一種作法。設想變換 T:\mathbb{R}^2\to\mathbb{R}^2 將圖P的界標點映射至圖Q的對應界標點。考量位移、旋轉、伸縮和輕度形變不改變圖形的相似度,可設 T 為一個仿射變換 (見“仿射變換”),如下:

\begin{aligned} T(x_1,x_1)&=\begin{bmatrix} w_{11}&w_{12}\\ w_{21}&w_{22} \end{bmatrix}\begin{bmatrix} x_1\\ x_2 \end{bmatrix}+\begin{bmatrix} w_{10}\\ w_{20} \end{bmatrix}=\begin{bmatrix} w_{10}&w_{11}&w_{12}\\ w_{20}&w_{21}&w_{22} \end{bmatrix}\begin{bmatrix} 1\\ x_1\\ x_2 \end{bmatrix}\\ &=\begin{bmatrix} w_{10}+w_{11}x_1+w_{12}x_2\\ w_{20}+w_{21}x_1+w_{22}x_2 \end{bmatrix},\end{aligned}

上式中 w_{ij} 為未知參數。我們希望 T(x_1,x_2) 近似於對應的界標位置 \begin{bmatrix} y_1\\ y_2 \end{bmatrix},故令目標函數為所有映射界標的座標誤差平方之和:

\displaystyle\begin{aligned} E&=\sum_{i=1}^n\left\Vert\begin{bmatrix} y_{i1}\\ y_{i2} \end{bmatrix}-T(x_{i1},x_{i2})\right\Vert^2\\ &=\sum_{i=1}^n(y_{i1}-w_{10}-w_{11}x_{i1}-w_{12}x_{i2})^2+\sum_{i=1}^n(y_{i2}-w_{20}-w_{21}x_{i1}-w_{22}x_{i2})^2.\end{aligned}

最佳解 \hat{w}_{ij} 必須使 E 有最小值,設為 E^{\ast},此最小值可用來代表圖P和圖Q的「距離平方」或「不相似度」,也就是說,E^{\ast} 越大表示兩圖形越不相似。

 
接下來是計算工作。先將目標函數改寫成標準矩陣表達式,令

X=\begin{bmatrix} 1&x_{11}&x_{12}\\ 1&x_{21}&x_{22}\\ \vdots&\vdots&\vdots\\ 1&x_{n1}&x_{n2} \end{bmatrix},~~~Y=\begin{bmatrix} \mathbf{y}_1&\mathbf{y}_2 \end{bmatrix}=\begin{bmatrix} y_{11}&y_{12}\\ y_{21}&y_{22}\\ \vdots&\vdots\\ y_{n1}&y_{n2} \end{bmatrix}

不難驗證

\displaystyle E=\left\Vert\mathbf{y}_1-X\begin{bmatrix} w_{10}\\ w_{11}\\ w_{12} \end{bmatrix}\right\Vert^2+ \left\Vert\mathbf{y}_2-X\begin{bmatrix} w_{20}\\ w_{21}\\ w_{22} \end{bmatrix}\right\Vert^2

若圖P界標點不在同一直線上,X 有線性獨立的行向量,則 \mathrm{rank}(X^TX)=\mathrm{rank}X=3,可得上式兩項各自的最小平方近似解 (見“從線性變換解釋最小平方近似”):

\begin{bmatrix} \hat{w}_{10}\\ \hat{w}_{11}\\ \hat{w}_{12} \end{bmatrix}=(X^TX)^{-1}X^T\mathbf{y}_1,~~~\begin{bmatrix} \hat{w}_{20}\\ \hat{w}_{21}\\ \hat{w}_{22} \end{bmatrix}=(X^TX)^{-1}X^T\mathbf{y}_2

合併兩式,

\begin{bmatrix} \hat{w}_{10}&\hat{w}_{20}\\ \hat{w}_{11}&\hat{w}_{21}\\ \hat{w}_{12}&\hat{w}_{22}\end{bmatrix}=(X^TX)^{-1}X^T\begin{bmatrix} \mathbf{y}_1&\mathbf{y}_2 \end{bmatrix}=(X^TX)^{-1}X^TY

取轉置即得最佳配適仿射變換

\begin{bmatrix} \hat{w}_{10}&\hat{w}_{11}&\hat{w}_{12}\\ \hat{w}_{20}&\hat{w}_{21}&\hat{w}_{22} \end{bmatrix}=Y^TX(X^TX)^{-1}

兩圖形不相似度的度量,即最小誤差平方之和,整理如下:

\begin{aligned} E^{\ast}&=\left\Vert(I-X(X^TX)^{-1}X^T)\mathbf{y}_1\right\Vert^2+\left\Vert(I-X(X^TX)^{-1}X^T)\mathbf{y}_2\right\Vert^2\\ &=\left\Vert(I-X(X^TX)^{-1}X^T)Y\right\Vert^2_F\\ &=\left\Vert Y-X(X^TX)^{-1}X^TY\right\Vert^2_F,\end{aligned}

上式中 \Vert\cdot\Vert_F 代表 Frobenius 範數 (見“矩陣範數”)。

 
最後我們討論基於仿射變換的圖形比對相似度性質。

(1) 圖P的所有界標座標 (即 X 的兩個行向量) 經仿射變換 T 映射至 X(X^TX)^{-1}X^TY,最小目標函數 E^{\ast} 即是圖Q的座標矩陣 Y 和映射結果 X(X^TX)^{-1}X^TY 的差距矩陣範數平方。

(2) 3\times 3 階矩陣 X(X^TX)^{-1}X^TX 的行空間的正交投影矩陣,因此 X(X^TX)^{-1}X^TY 也可以解釋為圖Q座標矩陣 Y 的兩個行向量 \mathbf{y}_1\mathbf{y}_2X 行空間的正交投影。

(3) 若 n=3 且圖P的3個界標點不在一直線上,X 是可逆矩陣,則 X(X^TX)^{-1}X^T=I,不論 Y 的數值為何,E^{\ast}=0

(4) 為了方便,我們可以定義圖P和圖Q的距離如下:

\mathrm{dist}(P,Q)=\Vert Y-X(X^TX)^{-1}X^TY\Vert_F

不過,\mathrm{dist}(P,Q) 通常不等於 \mathrm{dist}(Q,P),所以 \mathrm{dist}(P,Q) 不是一個對稱度量。在實際應用時,可以考慮使用兩度量的平均數。

廣告
本篇發表於 線性代數專欄, 應用之道 並標籤為 , , , 。將永久鏈結加入書籤。

2 Responses to 最小平方法於圖形比對的應用

  1. 張盛東 說道:

    老師,請問一下統計學中的線性回歸,無論是單變數還是多變數,本質上都只是最小平方的延伸?

    • ccjou 說道:

      線性回歸因為有不同的模型假設與目標函數,所以存在很多種參數估計方法,最小平方(ordinary least squares)是最常用的方法之一。如果樣本誤差服從常態分佈,最大概似估計(max likelihood estimation)給出的估計方式即為最小平方。

      維基百科列舉了很多其他估計方法,請參考:
      http://en.wikipedia.org/wiki/Linear_regression

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s