基于空间索引搜索的鱼眼图像校正方法

2021-01-18杭鹏程余艳梅陶青川

现代计算机 2020年32期

杭鹏程，余艳梅，陶青川

（四川大学电子信息学院，成都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个点。本文方法降低了每个像素点需要排序的点个数，因此速度更快。