本文由東華大學(xué)蔡棽副教授、上海交通大學(xué)嚴(yán)駿馳教授和中國(guó)科學(xué)院自動(dòng)化所申抒含研究員共同指導(dǎo)并撰寫(xiě)，四名學(xué)生作者為東華大學(xué)視覺(jué)與幾何感知實(shí)驗(yàn)室的吳展豪、郭凌希、王佳純、張斯禹。

一、論文簡(jiǎn)介

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

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

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

二、問(wèn)題介紹

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

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

令，去除齊次性，可得

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

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

三、本文方法

核心思想

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

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

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

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

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

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

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

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

• 【正方形模板的簡(jiǎn)化】

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

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

四、實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)主要集中在評(píng)估 4 點(diǎn)單應(yīng)求解器在不同場(chǎng)景下的運(yùn)行時(shí)間，下面給出了 CPU 和 GPU 計(jì)算一個(gè)單應(yīng)的平均運(yùn)行時(shí)間對(duì)比。

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

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

五、總結(jié)與展望

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

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