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

杭鵬程，余艷梅，陶青川

（四川大學(xué)電子信息學(xué)院，成都610065）

0 引言

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

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

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

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

1 MNBI算法

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

圖1 校正圖像對比

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

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

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

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

2.1 建基于字典的空間索引

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

圖3 正方形網(wǎng)格區(qū)域

2.2 基于空間索引的搜索

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

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

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

圖4 初步搜索區(qū)域

圖5 精確搜索區(qū)域

2.3 基于先驗(yàn)信息的搜索

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

圖6 基于先驗(yàn)信息的搜索中的三種情況

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

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

（3）如果 R當(dāng)前

接下來找出待檢查點(diǎn)中含有信息的網(wǎng)格點(diǎn)，并用包括當(dāng)前四個可能的最近鄰點(diǎn)在內(nèi)的所有含有信息的點(diǎn)中存儲的坐標(biāo)信息，與點(diǎn)G進(jìn)行距離計算，選出最近的四個點(diǎn)作為插值點(diǎn)。

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

2.4 利用對稱性加速

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

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

3 實(shí)驗(yàn)與分析

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

3.1 圖像質(zhì)量比較與分析

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

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

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

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

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

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

3.2 速度比較

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

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

4 結(jié)語

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