基于空間索引搜索的魚眼圖像校正方法

杭鵬程，余艷梅，陶青川

（四川大學電子信息學院，成都610065）

0 引言

由于魚眼鏡頭比普通鏡頭觀測區域更寬廣，因此其越來越多地被應用于汽車駕駛輔助[1-2]、醫用內窺鏡[3-4]、視頻監控[5-6]等領域。但魚眼圖像不可避免地會伴隨著桶形失真，為了減少畸變影響，通常方法包括坐標變換和魚眼圖像插值兩個步驟，其中坐標變換是建立失真圖像上的點與校正圖像上的點之間的對應關系，插值是填充坐標變換產生的空像素[7]。

經典的插值方法[8-11]如最近鄰插值、雙線性插值和雙三次插值常被用來校正桶形失真。文獻[5]中使用最近鄰插值法對兩臺魚眼相機拍攝到的圖像進行校正，然后對兩張圖片進行融合，以獲得更好的監控效果。文獻[6]中提出了一種基于雙線性插值的校正方案，以最小化魚眼鏡頭捕獲的視頻中的桶形失真。文獻[10]中使用雙三次插值來校正魚眼鏡頭引入的失真，以增強鳥瞰圖的效果。但是這些文獻中的插值系數是通過失真圖像上的距離進行計算的。

與上面的傳統方法用失真圖像上的距離計算插值系數不同，文獻[12]中提出了一種基于多重最近鄰的插值方法（Multiple Nearest-neighbor Based Interpolation，MNBI），通過在校正圖像上的距離來計算插值系數，從而改善了圖像質量。然而，MNBI方法試圖找到最近鄰點作為插值點，但是其找到的插值點并不總是準確的最近鄰點。

本文提出一種基于空間索引搜索的魚眼圖像校正方法，構建基于字典的空間索引，并利用先前點的鄰點信息和魚眼圖像的對稱性來加快計算速度，在魚眼圖像焦距變化時，仍然可以簡化計算，縮短運行時間。

1 MNBI算法

傳統的插值方法一般是使用失真圖像上的距離計算插值系數，而MNBI使用的是校正圖像上的距離以改善圖像質量。MNBI算法的主要思想如下：首先將校正圖像上的一點C通過公式（1）（其中F表示魚眼圖像焦距）映射到失真圖像上的對應點D；然后在失真圖像上找出D附近最近的16個點Dn（n=1，2，3…16），并全部通過公式（2）反向映射到校正圖像上得到Cn（n=1，2，3…16）；最后，分別計算Cn（n=1，2，3…16）到C的距離，選擇其中最近的四個點進行插值。MNBI的校正圖像如圖1（b）所示，可以看出與圖1（a）中的雙三次插值校正圖像相比，具有較弱的階梯現象。

圖1 校正圖像對比

MNBI雖然比傳統插值方法效果更好，但是仍還有一些需要改進的地方：①通過MNBI找到的插值點并不總是準確的最近鄰點；②MNBI中提出兩種的基于查找表的方法，即將當前焦距下各點的插值系數存儲為表格以供查找，從而減少反復計算量。但是當魚眼鏡頭焦距經常變化時（如魚眼變焦鏡頭），使用MNBI需要頻繁更新查找表，這兩種改進方法將無法起到加速的作用。

2 基于空間索引搜索的魚眼圖像校正方法

針對MNBI存在的主要問題，本文借鑒最近鄰搜索算法[13-14]的思想，提出了基于空間索引搜索的魚眼圖像校正方法，主要包括以下幾個部分：①首先提出了一種基于字典的空間索引方法，以便于后續的搜索工作；②然后為了精確找到待插值點的四個最近鄰點，對每行的起始點提出了一種基于空間索引的搜索，對每行的非起始點提出了一種基于先驗信息的搜索；③此外，利用魚眼圖像的對稱性來減少計算時間。流程圖如圖2所示。

圖2 基于空間索引搜索的魚眼圖像校正方法流程圖

2.1 建基于字典的空間索引

失真圖像上的點經過公式（1）變換后生成在校正圖像上，校正圖像上的點坐標通常不是整數，這使得鄰域搜索困難且耗時，因此本文提出了一種基于字典的空間索引。其步驟如下：①使用間距為一個像素的圖像坐標網格將整個校正圖像分割成許多小的網格正方形區域，如圖3（a）所示。網格區域覆蓋除網格下邊緣和右邊緣（圖3（b）中的虛線邊緣）之外的所有點，網格交點簡稱為網格點，其坐標必須是整數。②每個校正點C被分散到這些網格正方形區域中，該點的所有信息（坐標信息和RGB值信息（或灰度值信息））被存儲在所在區域左上角的網格點中，生成索引字典。字典由若干個網格點組成，只需搜索網格點就可以查找到其區域內存儲點的信息，當網格點的查詢結果為沒有信息時表示其索引的區域內不存在點。字典的結構如公式（3），其中E表示C所在區域左上角的網格點，即C在字典中的索引網格點，xC，yC表示C的坐標信息，IC表示C的RGB值信息（或灰度值信息）。

圖3 正方形網格區域

2.2 基于空間索引的搜索

構建完基于字典的空間索引，本文基于此索引提出一種搜索方法，主要包括初步搜索和精確搜索兩步，具體如下：

（1）初步搜索：搜索區域是以待插值點G為中心的正方形，搜索正方形的半徑從一個像素開始，每次增加一個像素，直到找到四個含有信息的網格點。如圖4所示，其中①表示半徑為一個像素的正方形，其區域內的網格點為G1、G2、G3和G；②表示半徑為兩個像素的正方形，依此類推。搜索區域覆蓋方格內和方格邊上的點，與建立空間索引時類似，無需考慮搜索正方形的右側和底部。

（2）精確搜索：首先用四個網格點中存儲的坐標信息分別和點G計算距離，取最大距離dmax并對其向上取整得到搜索半徑Rexact。接下來的新搜索區域如圖5中陰影區域所示，邊長為2×Rexact。然后在新搜索區域內找出所有包含信息的網格點，與現有的四個網格點一同作為鄰點。最后用鄰點中存儲的坐標信息分別與點G計算距離，選取最近的四個點作為插值點。

圖4 初步搜索區域

圖5 精確搜索區域

2.3 基于先驗信息的搜索

如果對每個點都使用基于空間索引的搜索，整體的計算復雜度會很高，為了加快運行速度，我們可以利用先前點的鄰點信息來簡化非行起始點的計算復雜度。具體操作如下：首先利用待插值點G（xi，yi）所在行的前一個網格點G’（xi-1，yi）的所有鄰點中存儲的坐標信息，與點G計算距離。然后找出四個最近點作為四個可能的最近鄰點，計算出dmax和Rexact，比較當前搜索半徑R當前和先前搜索半徑R先前之間的關系（如圖6）。

圖6 基于先驗信息的搜索中的三種情況

（1）如果R當前>R先前，則先前的搜索正方形周圍有許多新的待檢查點（圖6（a）中的圓點）；

（2）如果R當前=R先前，則先前的搜索正方形旁邊的列是新的待檢查點（圖6（b）中的圓點）；

（3）如果 R當前

接下來找出待檢查點中含有信息的網格點，并用包括當前四個可能的最近鄰點在內的所有含有信息的點中存儲的坐標信息，與點G進行距離計算，選出最近的四個點作為插值點。

在基于坐標空間的搜索和基于先驗信息的搜索之后，得到了所有點各自的插值點，提取出這些點中存儲的所有的信息，計算插值生成最終的校正圖像。

2.4 利用對稱性加速

魚眼圖像中的失真是對稱的[15-16]，也就是說，與中心具有相同向量距離的點具有相同的失真程度，當點P1和點 P2滿足以下等式（4）和（5）時，它們與中心 c具有相同的距離：

因此，只需對圖像的左上部分進行插值，然后利用對稱性得到校正后圖像的其余部分。例如，考慮到插值圖像右上角的像素和位于圖像左上角的像素是垂直軸對稱，插值點和插值系數也是對應一樣的。因此，在對圖像的左上部分進行插值后，我們可以在不搜索其他三部分的情況下進行校正插值。

3 實驗與分析

為了將基于空間索引搜索的魚眼圖像校正方法與MNBI方法進行比較，我們使用與文獻[12]中相同的測試圖像——柯達無損真彩色圖像集[17]中的24個測試圖像，其大小為768×512或512×768像素。在考慮光傳播條件的情況下，采用3×3高斯模糊核做模糊預處理。之后，將測試圖像變換為焦距為200像素的畸變圖像，并利用雙線性插值來填充空像素。

3.1 圖像質量比較與分析

圖7展示出了不同插值方法對測試圖像校正的效果。與現有的插值方法相比，本文方法減少了校正圖像中的階梯現象，提高了圖像的整體質量。比較不同插值方法下24幅測試圖像的PSNR和SSIM指數。如表1所示，本文方法的PSNR和SSIM高于其他兩種方法。

表1 不同方法校正后的圖像質量比較

圖7 采用不同插值方法的校正圖像

（a）原始圖像（從左到右為kodim01的左上角、kodim24的左下角、kodim12的右上角和kodim14的右下角），（b）模糊圖像，（c）雙三次插值，（d）MNBI和（e）本文方法

在對MNBI的進一步分析中，我們發現MNBI發現的四個插值點并不總是最臨近的四個點。MNBI的初選范圍是待插值點在失真圖像周圍最近的16個點，但有些待插值點的4個最近鄰點不全是在16個點的范圍內，因此MNBI方法存在缺陷。如表2所示，本文方法得到的插值點都是準確的最近鄰點，這意味著此方法可以獲得更好的校正效果。

表2 不同方法校正后的精度比較

3.2 速度比較

本文實驗的代碼都是在Visual Studio 2015中使用C++語言編寫，實驗電腦的配置是8GB RAM和英特爾酷睿i5 7000K。如圖8所示，基于空間索引搜索的魚眼圖像校正方法的速度比MNBI方法快75.51%，即使不利用魚眼圖像的對稱性進行加速，也比MNBI方法快26.24%。在MNBI中，任何像素點都需要對16個點進行排序才能得出最接近的4個點。本文方法降低了每個像素點需要排序的點個數，因此速度更快。

圖8 本文方法與MNBI方法運行時間的比較（單位：毫秒）

4 結語

本文提出了一種基于空間索引搜索的魚眼圖像校正方法，在校正桶形失真時能有效地找到精確的最近鄰點，與傳統的插值方法和MNBI相比，具有更好的插值效果和圖像質量，且速度比MNBI快得多。該算法不僅可以應用于魚眼圖像，還可以應用于圖像上最近點的搜索問題。進一步提高速度是今后工作的重要部分。