图像拼接算法的综述

发表于 2016-06-11 分类于算法与硬件阅读次数：

本文作者在2017年提出了L-ORB算法。速度是传统ORB算法的11倍、传统SIFT算法的639倍。将算法应用到嵌入式系统中性能提升了29倍，但其功耗低至10W。有兴趣的可以点击：**杜承垚,袁景凌,陈旻骋,李涛. GPU加速与L-ORB特征提取的全景视频实时拼接[J]. 计算机研究与发展, 2017, 54(6): 1316-1325.**

本文翻译自：Ghosh, Debabrata, and Naima Kaabouch. “A survey on image mosaicing techniques.” Journal of Visual Communication and Image Representation 34 (2016): 1-11.. 如有错误请指正。

一、简介

图像拼接在运动检测和跟踪、增强现实、分辨率增强、视频压缩和图像稳定等机器视觉领域有很大的应用。

如图所示，图像拼接分为四个步骤：图像匹配（registration）、重投影（reprojection）、缝合（stitching）和融合（blending）。

图1 图像拼接的步骤

图像匹配：是指一对描绘相同场景之间的几张图片的几何对应关系。一组照片可以是不同时间不同位置的拍摄，或者由多个传感器同时拍摄多张图像。
重投影：通过图像的几何变换，把一系列图片转换成一个共同的坐标系
缝合：通过合并重叠部分的像素值并保持没有重叠的像素值使之生成更大画布的图像
融合：通过几何和光度偏移错误通常导致对象的不连续，并在两个图像之间的边界附近产生可见的接缝。因此，为了减小接缝的出现，需要在缝合时或缝合之后使用混合算法.

不同的技术已被用于不同的拼接算法来处理多个颜色波段。例如，在¹⁸ ，¹⁹ ，²⁰ 和 ²¹中，综合所输入的RGB图像的颜色波段，获得的变换参数。在²² ，²³ 和 ²⁴中，该RGB图像首先被转换成灰度，然后得到变换参数。在这两种情况下，找到最佳变换参数后，对所有的颜色波段进行处理，实施重投影（reprojection）步骤。

二、图像拼接算法分类

“图像匹配”和“融合”是直接影响图像拼接性能两个显著的研究领域。作为图像拼接的第一个和最后一个步骤，如果没有正确的图像匹配和融合算法，几乎不可能进行成功的图像拼接。在本文中，我们对现存的图像拼接算法中“图像匹配”和“融合”的方法进行分类。

如图二所示，对“图像匹配方法”分类，图像拼接算法可分为基于“空间域”和“频域”。基于空间域的图像拼接可以进一步划分为基于区域的图像拼接和基于特征的图像拼接。基于特征的图像拼接可以再细分为基于底层特征的图像拼接（low level feature-based image mosaicing）和基于轮廓的图像拼接（contour-based image mosaicing）。基于底层特征的拼接可以分为四类：基于Harris角点检测器的拼接、基于FAST角点检测器的拼接、基于SIFT特征检测器的拼接、以及基于SURF特征检测器的拼接。
如图三所示，根据“融合方法”，拼接算法可分为基于平滑过渡（transition smoothening-based）和基于最佳接缝（optimal seam-based）。基于平滑过渡拼接可以进一步被分成基于羽化（feathering-based）、基于金字塔（pyramid-based）、和基于梯度（gradient-based）的拼接。

图3 根据融合方法的分类

三、对图像拼接的“图像匹配方法(registration)”分类

图像匹配不仅是图像拼接的重要一步，也是它的基础。对于相同的目标，但来自不同的传感器、不同的角度和不同的时间产生的多源图像进行匹配，通过观察各对图像之间的对应关系来计算最佳几何变换。这一过程通过预估的几何变换把多源图像排列在一个共同的参考系中。如果多源图像对应点排列在一起，则图像匹配成功。上述的对应关系可以通过匹配图像之间的模板，或通过匹配从图像中提取的特征，或者通过利用在频域中的相位相关属性来建立。基于所述图像配准不同类别的图像拼接算法将在以下两个小节论述。

3.1 基于空间域(Spatial domain)图像拼接算法

这类算法使用像素的属性进行图像匹配，因此它们是最直接的图像拼接的方法。现有的图像拼接算法大部分都属于这一类。图像拼接算法大部分都属于这一类。“基于空间域图像拼接算法”可以是基于区域（area-based）或基于特征（feature-based）的。“基于区域“的图像拼接算法依赖于计算待拼接的两个图像的“窗口”像素值¹⁸ 。基本方法是将图像有关联的“窗口”互相转移，看看有多少像素的匹配。随后，获得图像变换参数来弯曲和拼接图片。基于空间域的拼接算法通常被称为基于像素的拼接，因为它们使用的像素之间的匹配，而不是特征之间的匹配。的最常用的两个基于空间域的图像拼接算法是基于“归一化互相关”（normalized cross correlation）的拼接和基于“互信息”（mutual information）的拼接。这两种方法都提供了图像相似性的量度，这些指标的较大值来自匹配区域或“窗口”大小。

3.1.1 基于归一化互相关（Normalized Cross Correlation, NCC）的拼接

此方法计算在两个图像中的每个位移（shifts）的“窗口”之间的相似性。它被定义为²⁰：

且

$\overline{I_1} = {1\over N} \sum_i I_1(x_i)$

$\overline{I_2}=\frac{1}{N}\sum_i I_2(x_i+u)$

$\overline{I_1}$ 和 $\overline{I_2}$ 是窗口的平均值图像。$I_1(x,y)$和$I_2(x,y)$分别是两张图片。$N$是“窗口”大小，$x_i=(x_i,y_i)$ 是窗口的像素坐标，$u=(u,v)$ 是通过NCC系数计算出的位移或偏移。NCC系数的范围为[-1,1]。 NCC峰值相对应的位移参数表示两个图像之间的几何变换。此方法的优点是计算简单，但是速度特别慢。此外，此类算法要求源图像之间必须有显著的重叠。

为了解决上述问题，²⁷ ，⁴⁴ ，⁴⁵ ，⁴⁶几种技术已经被提出。Nasibov等人在图像匹配步骤之前使用的亮度校正矩阵，以便使算法对光照变化不敏感[27]。为了使计算速度更快，Berberidis等人提出的空间互相关来计算源的图像之间的位移的迭代算法⁴⁴。Zhao等人提出了通过基于调整根据规模，从源图像中提取兴趣点的方向的相关窗口方法等⁴⁵ ，以增加计算速度。为了提高算法的非刚性变形的存在下的性能，Vercauteren等人⁴⁶提出用黎曼统计（Riemannian statistics）与基于散乱数据拟合（scattered data fitting）的拼接。

3.1.2 基于互信息（Mutual Information, MI）的图像拼接

不同于基于图像强度值其计算相似性的NCC，互信息测量基于两个图像之间共享信息数量的相似性。两个图像$I_1(X,Y)$与$I_2(X,Y)$之间的MI以熵表示：

$MI(I_1,I_2)=E(I_1)+E(I_2)-E(I_1,I_2)$

$E(I_1)$和$E(I_2)$分别是$I_1(x,y)$和$I_2(x,y)$的熵。$E(I_1,I_2)$表示两个图像之间的联合熵。熵是一个随机变量的变异性指标。$I_1(x,y)$的变异性指标为：

$E(I_1)=-\sum_g p_{I_1}(g)log(p_{I_1}(g)) $

g是$I_1(x,y) $可能的灰度值，因此$p_{I_1}(g)$是g的概率分布函数。同理，$I_1(x,y)$和$I_2(x,y)$的联合变异性指标为：

$E(I_1,I_2)=-\sum_{g,h} p_{I_1,I_2}(g,h)log(p_{I_1,I_2}(g,h)) $

h是$I_2(x,y) $可能的灰度值，$P_{I_1,I_2}(g,h) $是g和h的联合概率分布函数。通常情况下，两个图像灰度值的联合直方图来用于衡量两个图像之间的联合概率分布。两个图像之间有更好的对齐，那么这两张图的MI值更大。因此，MI值为最大时，两张图像在变换中为几何对齐的。这种拼接方法的优点是对光线和咬合的变化不敏感。然而，这种于基于NCC的方法有计算速度慢、需要大面积输入图像的重叠等缺点。

为了解决上述的缺点，几个技术²⁹、⁴⁷和⁴⁸已被提出。在²⁹，Luna等人使用随机梯度算法（stochastic gradient optimization along with MI-based similarity measure）来加快算法的速度。Dame等人⁴⁷采用 B-spline function for normalized mutual probability density加快运算速度。他们进一步采用牛顿法（Newton’s method）来加快位移参数的估计。对于低重叠图片⁴⁸，Césare等人提出了一种模版匹配方法。

不同于基于区域（area-based）的方法，基于特征（feature-based）的拼接技术使用特征之间的匹配，来计算一对图像之间的几何变换。因此，这些方法主要依赖于能够提取显著特征的算法。显着特征是图像域的子集，通常是独立的点、连续曲线或连续区域⁴⁹。一般的方法是，从源图像检测几个相应的特征，然后使用可靠的对应关系估计单应性矩阵。利用单应矩阵图像进行扭曲然后缝合在一个共同的参考系。因为特征是出发点，整体算法往往会取决于特征提取算法。基于特征的拼接技术一般优于基于区域的技术，但是需要更高的计算成本。根据提取的特征类型，基于特征的拼接方法可分为底层特征的拼接和基于轮廓拼接。

3.1.3 基于底层特征的（Low-level feature）拼接

这些拼接方法不需要大量重叠区域的图像。

3.1.3.1 基于Harris角点检测器的拼接⁷⁹

Harris角点检测器在底层拼接中具有较强的鲁棒性。最初检测图像中的局部窗口。然后通过改变在不同的方向窗口的一个小的量来改变强度。⁴¹ ：

$E(u,v)=\sum_i w(x_i,y_i)[I(x_i+u,y_i+v)-I(x_i,y_i)]^2$

$w(x_i,y_i) $ 是检测窗口$(x_i,y_i) $ 的窗口函数。$I(x_i,y_i) $ 是在$(x_i,y_i)$位置的图像强度值，$I(x_i+u,y_i+v) $ 是到$(u,v)$的位移强度。本地纹理周围像素(local texture around pixel,$(x_i,y_i) $可表示为如下自相关矩阵:

$C=\sum_i w(x_i,y_i)
\begin{bmatrix}
I^2_{x_i} & I_{x_i}I_{y_i} \\
I_{x_i}I_{y_i} & I^2_{y_i} \\
\end{bmatrix}$

$I_{x_i}$和$I_{x_i}$是$I(x_i,y_i)$的导数。两个矩阵C对应的极大特征值对应着一个角点。窗口的中心点为一个角点的特征。为了使算法更强壮，可以用“cornerness”的R值来消除边缘点：

$R=Det(C)-\alpha Tr^2(C)$

$Tr(C) $ 是C的跟踪函数，$\alpha$的范围是$0.04 \leq \alpha \leq 0.06$。如果R的局部最大值高于阈值T，那么此点即为角点。两张图片的角点全部检测完成后，可以通过NCC或者SDD（Sum of Squared Difference）方法来确定其对应关系。随后利用算出的几何对应关系把图片统一到全局参考系中，以便进行拼接。采用Harris角点拼接算法计算简单，准确。

Harris 角点检测算法的缺点是会有大量密集的角点产生。然而，可以通过排除附近角点的方式来克服次缺点²³。用Harris角点方法的一个主要问题是，在旋转变化比较大时，往往会在拼接时产生重影。³⁰中通过在Harris角点匹配时使用“slope clustering”的“luminance center-weighting”算法来解决这个问题。另一个问题是在⁵⁰中提到的选择局部检测窗口的不确定性，⁵¹，其中使用的区域分割和匹配，来限制搜索窗口中潜在的同源点。

3.1.3.2 基于FAST角点检测器的拼接

FAST算法是一个在计算上更有效率且比大多数其他低级别特征提取方法快的角点检测算法，因此基于该算法的拼接方法特别适用于实时图像处理应用程序。算法首先围绕一个候选角点选择16个像素点。如果其中有n（n一般为12）个连续的像素都比候选角点加上一个阈值要高，或者比候选角点减去一个阈值要低，那么此点即为角点（如图4所示）。为了加快FAST算法的速度，通常会使用角点响应函数（a corner response function, CRF) 。CRF给出了基于在本地附近的图像强度的角点的“cornerness”的数值⁴¹通过计算出的CRF值检测局部最大值来确定角点。检测后，对每一对帧进行角点匹配。有时，“词袋”（Bag-of-Words, BoW）算法是用来表示每个图像作为一组角点的描述，以加快匹配过程³¹。然后，计算出单应矩阵（homography matrices），最后，把图像投射到一个共同的坐标得到最终的拼接图像。

图4 FAST算法的候选特征检测

选择最佳的阈值是在FAST的角点检测的算法的一个难点。但是，可以通过结合一个健壮的阈值选择算法⁵²来处理。为了从连续帧中匹配的角点，他们进一步提出了一个基于区域的灰度关联法的阈值学习方法。基于快速的算法的另一个主要问题是，对于增加变化的程度，算法不是特别健壮。为了解决这个问题，一个很好的方法是对16个像素点进行扩展采样区域，因为它提供给FAST角点更多的标志特征，进而使他们具有更大的不变性。

3.1.3.2 基于SIFT特征检测器的拼接

SIFT算法是一个检测关键点（distinctive features, also called “keypoints”）的底层特征检测算法。

3.1.3.2 基于SURF特征检测器的拼接

3.1.4 基于轮廓的拼接

3.2 基于频域（Frequency）图像拼接算法

四、对图像拼接的“融合方法（blending）”分类

4.1 基于平滑过渡（transition smoothing）融合的图像拼接算法

4.1.1 基于羽化（feathering）融合的图像拼接算法

4.1.2 基于金字塔（pyramid）融合的图像拼接算法

4.1.3 基于梯度（gradient）融合的图像拼接算法

4.2 基于最佳接缝（optimal seam）混合的图像拼接算法

This type of mosaicing algorithms attempt to minimize the visibility of seams by looking for optimal seams in the joining boundaries between the images. The objective of optimal seam technique is to allocate the optimal location of a seam line by looking into the overlapping region between a pair of images. The seam line placement should be such that it minimizes the photometric differences between the two sides of the line. At the same time the seam line should be able to determine the contribution of each of the images in the final mosaic. Once the placement and the contribution information are obtained, each image is copied to the corresponding side of the seam. When the difference between the two images on the seam line is zero, no seam gradients are produced in the mosaic. Unlike the mosaicing methods using transition smoothing-based blending, optimal seam-based mosaicing algorithms consider the information content of the scene in the overlapping region, allowing to deal with problems like moving objects or parallax. However, no information is fused in the overlapping region, thus the transition between the images can be easily noticeable when there are global intensity or exposure difference between the frames.

Different optimal seam finding methods have been used in mosaicing literature. For example, in [36] a modified region-of-difference method is used. In [77], authors proposed the use of an algorithm based on watershed segmentation and graph cut optimization. Another method based on dynamic programming and grey relational analysis is used in [78].

A general comparison of different categories of mosaicing algorithms based on image blending is presented in Table 3. Table 4 highlights the processing times of different mosaicing papers surveyed based on image blending.

Table 3.
Comparative overview of different categories of mosaicing methods based on image blending.

Category | Advantages| Disadvantages|
Feathering-based | Fast and good performer under exposure differences | Output often suffer from blur and ghosting effect
Pyramid-based | Good in preventing blur and edge duplication | Suffers from double contouring and ghosting when registration error significant
Gradient-based Output visually more appealing than other methods High computation required and registration error must be small for good performance
Optimal seam-based Good in dealing with moving objects and parallax Transition obvious when there are exposure differences

五、结论

Image mosaicing is an important task in the field of computer vision. Success of a mosaicing algorithm depends primarily on registration and blending methods. This paper provides a classification of image mosaicing methods based on image registration and blending algorithms. In addition to providing the description of the different categories, this paper discusses the advantages and disadvantages of each category. From the discussion, it is obvious that there is no single best image mosaicing category. At the same time, the continuous advent of new mosaicing methods in recent years makes it really difficult to choose an appropriate mosaicing algorithm for a specific purpose. Hence, this paper aims at providing a guide for selecting a suitable mosaicing method for a specific application. Although an extensive research has been done in the area of mosaicing, there are still problems to be addressed. For example, mosaicing in the presence of images with significant parallax is still a challenge. Another problem is the processing time. All mosaicing techniques are time consuming and cannot run on low power and low frequency devices. Addressing these issues would be where the future research might be directed at.