本文由東華大學蔡棽副教授、上海交通大學嚴駿馳教授和中國科學院自動化所申抒含研究員共同指導并撰寫，四名學生作者為東華大學視覺與幾何感知實驗室的吳展豪、郭凌希、王佳純、張斯禹。

一、論文簡介

東華大學、上海交通大學、中科院自動化所的研究團隊最新提出：兩種基于幾何的單應矩陣分解，極大地減少了四點求解單應的計算量（相比目前通用的求解稀疏線性方程組方法減少 95% 以上），可在二維碼掃描等典型視覺應用中顯著減少計算消耗，并有望應用于其他射影幾何、計算機視覺和圖形學問題中。

論文已被 IEEE T-PAMI 期刊接收。

• 論文標題：Fast and Interpretable 2D Homography Decomposition: Similarity-Kernel-Similarity and Af?ne-Core-Af?ne Transformations
• 論文主頁鏈接（含論文、代碼、視頻介紹、獎金激勵）：http://www.cscvlab.com/research/SKS-Homography

二、問題介紹

平面單應，又稱為二維射影變換，可表示為 3×3 的 8 自由度矩陣（在相差一個尺度因子下）。源平面到目標平面的單應求解最小配置為 4 組對應點，每組對應點提供對的兩個約束。記源平面上的四個點為，目標平面上的四個點為。一組對應點的齊次向量形式為，提供的約束可記為，這里表示齊次相等。

以往的直接線性變換（Direct Linear Transformation, DLT）方法利用上述約束構建稀疏線性方程組進行單應求解，其中常用的一種非齊次線性方程組構建方法為：

令，去除齊次性，可得

將 4 組點對的約束疊在一起，可得形如的稀疏線性方程組，并可通過對 8×8 系數矩陣的 LU 分解完成求解，在 OpenCV 庫中實現此算法的計算量（浮點運算次數）約為 2000。

后續一些改進方法，利用了上面系數矩陣的稀疏特性，設計了：（1）簡化的 3×3 系數矩陣的 SVD 分解，計算量約為 1800；（2）定制化的高斯消元法（放棄了選主元操作）求解，計算量約為 220。額外的，針對單應計算一類常見的應用場景 —— 掃描二維碼，可簡單地將源平面（二維碼模版）的正方形四頂點坐標設置為，，和，此時上述線性方程組的系數矩陣將進一步大幅化簡，但未見過相關工作研究這種更為特殊線性方程組的簡化求解。

三、本文方法

核心思想

基于幾何變換的層次性（相似 - 仿射 - 射影），逐步利用部分點求出子變換，從而將單應矩陣分解為多個子變換完成分別求解并相乘。

• 【相似 - 相似射影核 - 相似（Similariry-Kernel-Similarity, SKS）變換】

如下圖所示，SKS 利用兩組對應點分別計算源、目標平面上的相似變換和，即將這兩個點分別變換成標準點（齊次坐標表示）。和分別經過相似變換后，兩個平面和間的相似射影核變換定義了射影畸變（形變）。進一步，可被分解為若干變換的乘積，這里表示一個初等變換，將標準點變為直角雙曲點；表示雙曲相似變換，并可分解為兩個平移，及表示雙曲尺度和旋轉的。

最終，單應矩陣由上述 SKS 變換形成的分解形式為：

其中四參數的相似射影核變換表示為

• 【仿射 - 仿射射影核 - 仿射（Affine-Core-Affine, ACA）變換】

類似地，可由三組對應點分別計算源、目標平面的仿射變換和，將它們分別變換為定義的標準點（齊次坐標表示）。如下圖所示，平面和分別經過仿射變換后，平面和間的仿射射影核變換定義了射影畸變。如右側所示，有兩個自由度，因此可通過分別仿射變換后的第四組點對求得。在 ACA 變換下，單應矩陣分解為：

ACA 變換是極其高效的，其計算單應矩陣的浮點運算次數統計見下表。在相差一個比例因子下單應計算共計 85 次浮點運算。表下方同時給出了一些計算量統計的細節（可通過其中加、減、乘號的數目進行統計）。

• 【正方形模板的簡化】

當四個源點構成一個特殊形狀，ACA 算法的計算過程可以進一步簡化。以下算法展示了矩形（或正方形）模版與其圖像間單應的計算過程，分別需要 47 和 44 次浮點運算。

更進一步地，當使用正方形進行相機標定（聚焦于內參數）或二維碼檢測時，平面坐標系的位置通常無關緊要。一個簡單的設置可假設左上角頂點為原點，并且正方形的邊長為 1（即寬高比和寬度都為 1）。此時單應計算僅需 29 次浮點運算。

四、實驗結果

實驗主要集中在評估 4 點單應求解器在不同場景下的運行時間，下面給出了 CPU 和 GPU 計算一個單應的平均運行時間對比。

更多的實驗結果，如集成在 RANSAC 流程、集成在深度單應估計網絡中求取單應，詳見論文原文。

結果顯示，使用雙精度浮點數，ACA 分解完成一次四點單應計算的平均時間僅為 17 納秒。與 DLT+LU 相比，SKS 和 ACA 在開啟編譯器默認的 O2 優化下分別實現了 29 倍和 43 倍的實際加速比。這兩個數值遠超理論上 FLOPs 的 11 倍和 20 倍比值，部分因為以往方法的實現涉及條件判斷、數據拷貝等操作拖慢了執行速度，而這些操作并沒有被 FLOPs 統計所覆蓋。

五、總結與展望

平面單應計算可廣泛應用于相機標定、圖像拼接、增強現實、三維重建等視覺任務中，因此本方法可集成在眾多視覺處理程序中，替換以往的單應算法。更為常見的是，二維碼掃描中需要計算正方形（原始二維碼模版）到其圖像的單應，以校正圖像后進行二維碼信息解碼。據估算目前中國的日均二維碼掃描已達百億次，本文提出計算正方形模版的單應僅需 29 次浮點運算，因此相比傳統的 DLT+LU 方法，每天可減少浮點運算量約。

作為一項幾何視覺理論研究，本文提出的 SKS 與 ACA 方法可廣泛應用于基于平面的視覺或圖形學任務中。目前，研究團隊在深度學習估計單應的幾何參數、基于平面單應的 P3P 姿態估計、N 維單應矩陣分解等問題開展了后續研究，取得了一些初步成果。