图像拼接的改进算法
第15卷第11期2003年11月计算机辅助设计与图形学学报JO U RNAL OF COM PU T ER -AI DED DESIGN &COM PU T ER GRA PHI CS Vol 15, N o 11Nov , 2003
图像拼接的改进算法
方贤勇
1) (
2) 1) 潘志庚1) 徐 丹2) 浙江大学CAD&CG 国家重点实验室 杭州 310027) (云南大学信息学院 昆明 650091)
摘要 图像拼接在制作全景图的过程中具有重要作用, 但是现有的方法不能很好地处理鬼影和曝光差异 针对存在的问题, 提出了一种实现图像拼接的算法 首先利用动态规划的方法在要进行拼接的图像中找到一条最佳的缝合线, 然后利用多分辨率技术进行拼接, 解决了鬼影和曝光差异
关键词 图像拼接; 鬼影; 曝光差异; 动态规划; 多分辨率拼接
中图法分类号 T P391
An Improved Algorithm for Image Mosaics
Fang Xianyong 1) Pan Zhigeng 1) Xu Dan 2)
1) (
2) State K ey L aboratory of CA D &CG , Zhe j iang Univ ersity , Hangz hou 310027) (I nf ormation S c hool, Yu nnan University, K u nming 650091)
Abstract Image mosaics are very important in creating panorama and existing algorithms can not cope w ith ghosting and ex posure difference efficiently To solve these two problems, we present a new algorithm T he first step is to find a best seam -line to stitch the imag es based on dynam ic programming Then the mosaic image is created by a multiresolution method
Key words im age mosaics; ghosting; ex posure difference; dy namic programming; multiresoltion mo -saic
形成原因是由于拍摄时手的运动不在一个平面上,
1 引 言
-5]理想情况下, 全景图[1的制作是非专业用户这样拍得的相邻两幅图像之间不仅有平移关系, 还存在旋转关系, 使得配准不准确; 合成鬼影的形成原因是由于图像中存在运动物体, 这些物体因位移而
无法正确合成 彩图1(见彩图页i) 所示为鬼影的两
种情况, 彩图1a, 1b 经配准计算后用距离加权方式
合成得到的彩图1c 彩图1c 中标出了图像中存在
的两处鬼影, 其中, 有钢架的是配准计算不准确造成
的配准鬼影, 而有工作人员的是运动物体造成的合
成鬼影
(2) 曝光差异又称曝光瑕疵[7], 指相邻两幅图用手持的普通相机拍摄场景一周而得到一组数字图像的过程, 并且在不经任何交互的情况下由系统自动完成 但是现有的算法对手持相机拍摄的数字图像进行全景图制作时存在以下两个问题:(1) 鬼影, 是指合成得到的全景图中由于同一物体部分重叠而使物体变得模糊的图像 可以归纳为两种鬼影:配准鬼影和合成鬼影 配准鬼影的[6]
原稿收到日期:2002-11-19; 修改稿收到日期:2003-04-07 本课题得到国家自然科学基金重点项目(60033010) 、教育部优秀青年教师教学科研奖励基金、浙江省优秀人才基金(RC40008) 、云南省-浙江大学省院省校科技合作项目(2001JAALA02A022) 资助 方贤勇, 男, 1978年生, 博士研究生, 主要研究方向为基于图像的绘制技术 潘志庚, 男, 1965年生, 博士, 研究员, 博士生导师, 主要研究方向为基于图像的绘制、虚拟现实、分布式图形、智能虚拟环境 徐 丹, 女, 1968年生, 博士, 教授, 主要研究方向为基于图像的绘制、虚拟现实、图像处理、计算机视觉和多
11期方贤勇等:图像拼接的改进算法1363像由于曝光不同造成的拼接后图像色彩的明显不协
调 如彩图2a(见彩图页ii) 所示为用距离加权的合
成方法得到的图像, 在图像的左右两部分存在曝光
差异 产生曝光差异的原因一个是普通数码相机不
易被人工控制曝光时间, 还有一个原因是非专业用
户一般并不注意曝光调节
文献[6]提出通过计算光流的多次变换的方法
减少由于较小的配准误差引起的鬼影, 但是该方法
相当复杂 文献[8-9]则均是寻找一条最佳的缝合
线, 通过在缝合线两边只取一幅图像的内容实现两
幅图像的拼接, 达到消除鬼影的目的 其中, 文献
[8]利用复杂度很高的Dijkstra 算法找到最佳的缝
合线, 而文献[9]则是定义了一个准则, 利用动态规
划的思想找到最佳的缝合线, 其计算复杂度较低
本文的鬼影消除方法就是在文献[9]的基础上提出
的 文献[9]还通过一个线性的均衡器进行两幅图
像之间的曝光差异处理, 但是线性关系并不能正确
地反映相邻图像间的曝光关系, 所以也就无法很好
地解决曝光差异 文献[3]通过预先调整单幅图像
曝光的方式进行曝光差异的处理, 对于大量图片的
拼接来说这是相当费时的 文献[7]对鬼影和曝光
差异问题都进行了探讨, 对于鬼影是通过顶点覆盖
算法, 找到重叠区域应该从哪一幅图像中获取加以
解决; 对于曝光差异则采用基于块的调整算法解决
但是文献[7]处理鬼影的方法较为复杂, 处理曝光差
异的方法也不能取得较好的效果
可以看出, 已有的文献均未能很好地同时解决
鬼影和曝光差异问题 针对前人工作中存在的问
题, 我们提出一种新的实现图像拼接的算法 首先
使用相位校正方法对两幅原始图像进行配准; 然后
根据动态规划思想, 用一个简单且非常稳定的准则
在配准后的图像中寻找一条缝合线; 最后结合多分
辨率技术实现拼接 本文主要讨论对于两幅图像如
何建立最佳缝合线和多分辨率合成, 有关相位校正
方法见文献[10] 两幅原始图像上的颜色值之差最小; (2) 在几何结构上, 要求缝合线上的像素点在两幅原始图像上的结构最相似 但是, 由于实际的图像很难得到同时满足上述两个要求的缝合线, 因此需要寻找较好地满足上述两个条件的最佳缝合线 文献[9]提出了一个寻找最佳缝合线的准则, 但是在这个准则中存在着多个不确定的因素, 因而不易于求解出最佳缝合线 通过对图像的分析和实验, 我们推出最佳缝合线求解准则E (x , y ) =E color (x , y ) 2+E g e o metry (x , y ) (1) 其中, E c o l or 表示两幅原始图像上重叠像素点的颜色值之差, 而E g e o metry 表示两幅原始图像上重叠像素点的结构差值 E geometry 是通过修改梯度计算Sobel 算子实现的 利用Sobel 算子进行梯度计算时, 计算在x 方向和y 方向的梯度分别采用模板-10S x =-20-102和S y =-1-2-01020 实验表明, 由于这个计算方法没有考虑到像素点周围的相似性, 因此不能够准确地找到最佳缝合线 一个自然的想法是:应该强调像素点为中心的对角线方向的4个边缘像素点的相关性, 并将它们的差值作为几何结构相似度的评价标准 由此, 得到新的计算梯度的算子模板-20S x =-10-201和S y =1-2-1-02010 假定两幅原始图像为f (1) 中的E geometry 计算公式为和f 2, 则可以得到式E g e o metry =Diff (f 1(x , y ) , f 2(x , y ) ) ; Diff 的求解是通过计算两幅图像f 1和f 2在x 和y 方向的梯度之差的积得到 根据此准则, 将两幅图像重叠的部分作差运算
生成一幅差值图像; 然后对此差值图像运用动态规
划的思想从重叠区域的第一行出发, 建立以该行上
每一个像素为起点的缝合线; 最后从这些缝合线中
寻找一个最佳的缝合线 具体步骤如下:
Step1 初始化 第一行各列像素点对应为一条缝合线,
其强度值初始化为各个点的准则值, 该缝合线的当前点为其
所在的列值;
Step2 扩展 已经计算过缝合线强度的一行向下扩展,
直到最后一行为止 扩展的方法是将每一条缝合线的当前
3, 2 最佳缝合线的建立将两幅原始图像配准后的图像区域分成两部分, 每一部分对应一幅原始图像的相应部分, 如果分割得好的话, 则合成之后可以完全消除鬼影 我们定义具有如下特征的一条理想的缝合线对配准后的图像区域进行分割:,
1364计算机辅助设计与图形学学报2003年取最小强度值所对应的下一行的这3个像素的之一作为该
缝合线的扩展方向, 更新此缝合线的强度值为最小强度值,
并将缝合线的当前点更新为得到最小强度值所在的下一行
中的紧邻像素值所在的列;
Step3 选择最佳缝合线 从所有的缝合线中选择强度
值最小的作为最佳缝合线 带宽为一个倍频程, 那么这两幅图像拼接后就可以在缝合线两边实现平滑过渡, 从而不会出现鬼影和曝光差异 对需要拼接的两幅原始图像进行多分辨率拼接, 是指将它们各自分解成一系列带宽近似为一个倍频程的图像(称为拉普拉斯图像) , 拼接是在
所有相同频率范围的图像之间进行的, 最后将这样
拼接得到的图像进行相加, 就可以得到两幅原始图
像拼接后的图像 文献[11]提出了多分辨率的思想
并且首先将之应用到两幅图像拼接的平滑过渡处理
中, 文献[12]则在制作全景图时利用多分辨率技术
进行色彩变换(color w arp) 对于两幅要进行拼接的
原始图像f 1和f 2, 在求出缝合线后, 进行多分辨率
拼接的具体步骤如下:
Step1 以拼接后的图像大小为尺寸, 生成一幅区域图像
R , 将缝合线左边填充为白色, 右边填为黑色, 如彩图2(见彩
图页ii) 所示, 彩图2c(见彩图页ii) 所示为两幅原始图像拼接
得到的区域图像 将两幅原始图像f 1和f 2分别扩展到区域
图像大小, 扩大了的部分取各自原图的内容进行填充;
Step2 对两幅扩大了的原始图像f 1和f 2分别求解拉
普拉斯图像金字塔 对区域图像R 求解高斯图像金字塔;
Step3 计算拼接后的图像的拉普拉斯图像金字塔, 其方
法是对于拼接后的图像的拉普拉斯图像金字塔的第l 阶
L m l , 用区域图像的高斯图像金字塔的第l 阶GR l 的像素值
作为权值, 计算L m l 在该像素点处的像素值:
L m l =GR l (i , j ) Lf 1(i, j ) +(1-GR l (i, j ) ) Lf 2(i , j )
其中, Lf 1表示扩大了的原始图像f 1的拉普拉斯图像金字
塔的第l 阶, 而Lf 2表示扩大了的原始图像f 2的拉普拉斯
图像金字塔的第l 阶, (i, j ) 表示像素点的位置;
Step4 对拼接后图像的拉普拉斯图像金字塔, 从最高一图1说明了生成缝合线的开始两步 图中的黑点代表像素点, 左图表示初始化这样的一组缝合线, 右图表示缝合线初始化之后开始第一次扩展; 右图中经过第一行每个像素点的缝合线发出了3条线段指向下一行紧邻的3个像素点, 实线段则表示该缝合线的最小扩展方向 这样, 就可以在计算到最后一行时得出最佳缝合线, 实现图像拼接 彩图3a(见彩图页ii) 所示为彩图1a 和1b(见彩图页i) 通过建立最佳缝合线拼接的图像, 可以看出已经不存在任何鬼影; 彩图3b 中间的一条弯曲的白线给出了最佳缝合线的位置 比较彩图3a 与彩图1c 可以发现, 因为物体运动造成的合成鬼影和配准不准造成的物体重叠部分(即配准鬼影) 已经完全没有了 因为两幅原始图像的重叠部分在这些地方的像素值之差与几何结构之差较大, 经过这些区域的缝合线就不会被选为最佳的缝合线
图1 最佳缝合线搜索阶开始扩展并与下一阶相加, 将相加后的图像作为下一阶的
图像, 将得到的图像再扩展, 并与其下一阶的图像相加 重
复此过程, 直至与最底一阶相加完为止, 这样就得到了最终
的拼接好的没有曝光差的图像 彩图2d(见彩图页ii) 所示为
经过上述处理后得到的拼接后的图像, 此时已经看不出曝光
差异 3 多分辨率拼接3 1 拼接过程
由于普通数码相机在拍摄照片时会自动选取曝
光参数, 加之用户一般不会注意调节曝光时间, 因此
在拼接后的图像中存在曝光差异问题 若采用缝合
线思想进行图像拼接, 由于缝合线两边各取不同图
像的内容, 因此在两幅原始图像的曝光差别较大时,
拼接后的图像中缝合线两边会出现明显的明暗变
化 如彩图2(见彩图页ii) 中, 因为两个原始图像曝
光差别太大, 使得彩图2b(见彩图页ii) 在缝合线两
边的明暗变化非常明显
我们采用多分辨率拼接较好地解决了曝光差异 :3 2 多幅图像拼接两幅图像多分辨率拼接方法对于多幅图像同样可取得较好效果 如彩图4(见彩图页ii) 所示, 彩图4a~4e 是5幅用手持相机拍到的图像, 可以看出它们的曝光都不完全相同 利用多分辨率技术拼接后的图像如彩图4f(见彩图页ii) 所示, 可以看出该图像已经很好地处理了曝光差异 4 结束语
11期方贤勇等:图像拼接的改进算法
[3]1365法 该算法结合了动态规划和多分辨率两项技术,
与前人的算法相比, 有以下几个方面的优点:
(1) 用于动态规划的新准则没有任何不确定因
素, 其形式更加简单, 运算速度也较快;
(2) 将动态规划技术与多分辨率技术相结合的
多分辨率拼接是进行图像拼接的新的尝试, 可以同
时消除鬼影和曝光差异
实验表明, 该算法较好地解决了鬼影和曝光差
异问题, 具有较高的应用价值 但是, 该算法的速度
相对距离加权方法要慢一些 对于一台P , 512M
内存的PC 机, 我们选取的多分辨率运算的阶数分
别为2~4, 两幅640 480的图像拼接需要2~5s
不等; 对于多幅图像则会因为图像越来越大而速度
越来越慢, 对于15幅640 480的图像来说, 拼接时
间为1m20s~2m30s 不等, 如何提高运行速度有待
于进一步的研究 另外, 本文算法的精度在很大程
度上依赖于配准算法的精度 在配准误差大于2
时, 缝合线就会找不准, 拼接的结果就可能不够理
想, 因此, 如何提高配准精度也是进一步需要研究的
内容 第三个需要进一步研究的内容是如何处理第
一幅图像与最后一幅图像的拼接 Shenchang Eric Chen Qui ckTime VR An image -based ap -proach to virtual environment navigation [A] In:Computer Graphics Proceedings, Annual Conference Series, ACM SIG -GRAPH, Los Angeles, 1995 29~38[4]Qi Chi, Liu Qiang, S un Jiaguang Video mosai cs for panoramic image [J] Journal of Computer -Aided Design &Computer Graphics, 2001, 13(7) :605~609(in C hi n ese) (漆 驰, 刘 强, 孙家广 摄像机序列的全景图拼接[J] 计算机辅助设计与图形学学报, 2001, 13(7) :605~609) [5]Xu Dan, Pan Zhigeng, Shi Jiaoying Image -based rendering techniques in virtual reality [J] Journal of Image and Graphics, 1998, 3(12) :1005~1009(i n Chinese) (徐 丹, 潘志庚, 石教英 虚拟现实中基于图像的绘制技术[J] 中国图象图形学报, 1998, 3(12) :1005~1009) [6]H eung -Yeung Shum, Richard Sz eliski Construction of panoramic image mosaics w ith global and local alignment [J] Internati onal Journal of Computer Vision, 2000, 36(2) :101~130[7]M atthew Uyttendaele, Ashley Eden, Richard Szeliski Elim-i nati ng ghosti ng and exposure artifacts in image mosaics [A] In:Proceedings of IEEE Com puter S ociety Conference on Computer Visi on and Pattern Recognition, Haw aii, 2001 509~516[8]James Davis M osaics of scenes w ith movi ng objects [A] IEEE Computer Society Conference on Computer Vision and Pattern Recogniti on, Santa Barnara, 1998 354~360
[9]M arie -Lise Duplaquet Building large image mosaics w ith invis -i
ble seam -lines [A] In:Proceedings of S PIE Aerosense, Orlan -
do, Florida, 1998, 3387:369~377
[10]
[11]Lisa Gottesfeld Brow n A survey of image registration technolo -gies [J] ACM Computing S urvey, 1994, 24(4) :325~376Peter J Burt, Edward H Adelson A multiresolution spli n e w ith
application to image mosaics [J] ACM Transacti ons on Graph -
ics, 1983, 2(4) :217~236
[12]Shmuel Peleg, Joshua Herman Panorama mosaics by manifold
projection [A] In:Proceedi ngs of IEEE Computer Society
Conference on Com puter Vision and Pattern Recogni tion, Puerto
Rico, 1997 338~343致谢 本实验室石教英教授对本文提出宝贵的修改建议, 在此表示感谢! 参 考 文 献[1]Richard Szeliski Video mosaics for vi rtual environments [J] IEEE Computer Graphics and Applications, 1996, 16(2) :22~30[2]Richard Szeliski, Heung -Yeung S hum Creati ng full view panoramic image mosaics and environment maps [A] In:Com -
puter Graphics Proceedi ngs, Annual Conference Series, ACM
S IGGRAPH, Los Angeles, California, 1997 251~258