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

一、論文簡介

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

論文已被 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

二、問題介紹

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

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

令，去除齊次性，可得

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

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

三、本文方法

核心思想

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

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

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

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

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

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

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

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

• 【正方形模板的簡化】

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

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

四、實驗結(jié)果

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

更多的實驗結(jié)果，如集成在 RANSAC 流程、集成在深度單應(yīng)估計網(wǎng)絡(luò)中求取單應(yīng)，詳見論文原文。

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

五、總結(jié)與展望

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

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