基于四叉树的高效梯度域图像融合

戴幸奎+潘涛+尹思梦

（南京邮电大学，江苏 南京 210046）

【摘 要】随着科技的不断发展，数千万像素的图片很常见，由于面对这种大数量级的图片，传统的利用泊松图像编辑求解图像融合的方法已不再适用。虽然梯度域合成是强大的和广泛使用，但它具有较差的可扩展性。计算n像素复合需要求解具有n个变量的线性系统，当对于实际上常见的数千万像素复合材料执行时，解决这样大的系统，其求解的线性方程规模太大能快速地压倒标准计算机的主存储器，且耗时太长，甚至要占用很大的内存。为了降低泊松方程构建的线性系统的规模，提高运行效率，节约时间，本文描述了一种提高梯度域合成效率的分层方法，在此引入了四叉树这种层级空间数据结构，通过对融合图像的分解，选择出少量的像素点求解，最终通过线性插值的方法，补全其余像素点的差值，完成图像合成，来近似达到求解泊松方程构建完整线性系统的效果。

【关键词】图像编辑；梯度域合成；四叉树

现在是信息时代，图形是人们获取信息、表达信息、传递信息的一种手段。随着数字图像处理技术的兴起，人们生活在不知不觉间发生了翻天覆地的变化。图像、图形逐渐成为传播信息的主要的载体，虽然人眼识别高，可以找到成千上万的颜色，但在许多情况下，对图像来说人眼模糊甚至不可见。数字图像处理技术可以帮助人们理解世界更客观、准确地。因此，数字图像处理技术显得尤为重要。对图像处理有较好的理解。

图像合成是通过将源图像中的对象或区域嵌入到目标图像中，生成新的图像的一种解决问题的基本方案。在合成图像的过程中，为了使合成的图像更加自然，合成边界必须保持无缝。然而，如果原始图像和目标图像具有明显不同的纹理特征，那么直接合成的图像就会有一个清晰的边界。为了解决这一问题，一种利用构造的泊松方程求解像素最优值的方法就这样诞生了。这种方法不仅可以很好地融合源图像梯度信息，并且可以很好地融合源图像和目标图像的背景。该方法根据用户指定的边界条件求解泊松方程，在梯度域上实现连续性，实现边界的无缝融合。泊松图像编辑的主要思想是重建图像像素的复合区域，其采用了基于图像梯度信息和目标图像的边界信息的插值方法。Poisson图像编辑是计算摄影和视频中最广泛使用的算法之一；但是它不能很好地扩展到今天的百万像素数字图像。

随着科学技术的发展，如今的图片数百万甚至上千万像素都很常见。随着像素数量级的增大，Poisson图像编辑在时间和空间方面，求解线性系统所需的时间更长，需要的空间更大。因此，盡管梯度域技术的广泛适用性，但这种差的可扩展性限制了其在数字摄影软件中的采用。

在2007年Aseem Agarwala 发表了Efficient gradient-domain compositing using quadtrees.这篇论文在Poisson图像编辑的基础上引入了四叉树，减小了求解的线性系统的规模，不但提高了图像合成的效率，还减小了求解线性系统所需的时间空间。

本文研究的目的与意义了解了图像拼接的相关知识，学习和掌握数字图像处理的基本理论和方法；学习和掌握matlab等工具的使用；掌握基于四叉树的梯度域图像拼接算法的基本思想和处理流程；用实际图像进行大量的实验验证和分析；最后完成这个算法。

Efficient gradient-domain compositing using quadtrees这篇论文就是关于基于四叉树的梯度域图像拼接算法，也是我的本文研究。而我的研究就是，查阅相关文献，学习理解文献的图像处理算法，并完成算法的实现。

本文研究的目的与意义也是锻炼自己综合分析和解决问题的能力和独立工作能力、组织管理和社交能力，也是学习深化、拓宽、综合运用所学知识的重要过程；还是我对学习、研究与实践成果的全面总结。其次综合运用所学基础理论、专业知识及基本技能来分析和解决实际问题的能力。同时对于增强我的事业心和责任感，提高我的全面素质具有重要意义。

使用四叉树的有效的梯度域合成算法是建立在Poisson图像编辑的基础之上的。由于图片像素数量级的提升，原有的Poisson图像编辑在时间空间上逐渐无法满足图片合成的需求。由此引入了四叉树这个概念，对图像进行划分，从而选择部分有效的像素点去求解比原来较小的线性系统，最后通过线性插值，双线性插值等方法求解所有的像素点的值。

此算法可以分为三个阶段：构造四叉树；求解线性系统；线性插值。本论文讲述的算法的步骤，第一步是关于四叉树的原理，四叉树的构建以及四叉树如何划分图像，选择像素点等等。第二步是关于泊松图像编辑方面的相关知识，了解泊松方程的构建与计算，从而为后续梯度域合成做准备。第三步关于求解Poisson图像编辑的线性系统，获得算选像素点的初始值与合成后的差值，通过线性插值的方法计算所有像素的差值，最终完成梯度域的合成。通过做大量的实验，然后对算法和实验进行分析和论证，从而发现问题，查找原因。至此就完成了图像的合成。第五章是在完成算法的基础上，通过大量图片来进行相应的实验，通过分析和论证得出相应的结论，由此验证算法效果。

研究的内容就是使用四叉树的有效的梯度域合成算法的三个阶段，相关详细的论述会在后面相应的文章里讲述。

图像融合利用泊松图像编辑完成，他是一种利用构造的泊松方程求解像素最优值的方法。这种方法不仅可以很好地融合源图像梯度信息，并且可以很好地融合源图像和目标图像的背景。该方法根据用户指定的边界条件求解泊松方程，在梯度域上实现连续性，实现边界的无缝融合。泊松图像编辑的主要思想是重建图像像素的复合区域，其采用了基于图像梯度信息和目标图像的边界信息的插值方法。

该方法通过将可能出现在合成区域之间的边界处的高频伪像转换成分布在图像上的低频变化，来隐藏合成图像区域之间的接缝。

我们的方法在梯度域中合成图像区域非常有效；一个明显的扩展是对视频执行梯度域合成，其中可扩展性关注甚至更大。这个扩展应该是直接使用八叉而不是四叉树。

我们的技术是有效的，因为我们可以创建一个初始解到线性系统，其残差是稀疏的。同样可以说几个其他梯度域问题，如阴影去除，去除闪烁图像中的反射，以及照相表面的再现，因为在这些情况下，期望的梯度场大部分匹配原始图像，除了被衰减或设置为零的某些梯度。这一观察表明，我们的方法可以用来提高效率。然而，它不能直接应用于没有这样的初始解的其他梯度域问题。

我们还计划探索一个扩展，可以允许更有效的外核重建从一般梯度场。可以针对图像的每个图块独立地计算解，从而创建具有仅沿着图块边界的非零残差的初始解。然后，可以沿着这些瓦片边界对四叉树进行细分，并且用于计算对初始解的偏移。

虽然梯度域合成是一种非常有效的技术，用于合成图像和视频区域，它不是像以前简单地使用它用于大分辨率的图像的影像数据成像。我们的梯度域合成的近似方法，在产生视觉上相同的结果的同时，还可以在令人惊讶的很少的时间和记忆中计算，即使对于非常大的复合材料。我们希望我们的技术将成为解决计算摄影和视频算法的可扩展性的技术之一。