图像拼接融合算法

第 9 卷　第 4 期 2004 年 4 月 中国图象图形学报 Jou rna l of Im age and Graph ics V o l. 9,N o. 4 A p r. 2004 基金项目: 973 国家重点基础研究发展规划项目 (G199803050522) 收稿日期: 2003208211; 改回日期: 2003211224 一种全自动稳健的图像拼接融合算法 赵向阳　杜利民 (中国科学院声学研究所语音交互室, 北京　100080) 摘　要　提出了一种全自动稳健的图像拼接融合算法。此算法采用H arris 角检测算子进行特征点提取, 使提取的 精度达到了亚像素级, 然后以特征点邻域灰度互相关法进行特征点匹配得到了初步的伪匹配集合, 并运用稳健的 RAN SA C 算法将伪匹配点集合划分为内点和外点, 在内点域上运用LM 优化算法精确地估计出了图像间的点变 换关系, 最后采用颜色插值对交接处进行颜色过渡。整个算法自动完成, 它对有较大误差或错误的特征点数据迭代 过滤, 并用提纯后的数据来做模型估计, 因而对图像噪声和特征点提取不准确有强健的承受能力。在参数估计时, 以特征点的坐标位置误差而不是亮度误差来构造优化函数, 克服了以往算法对光照的敏感性, 使算法更具有实用 性。实验结果表明, 该算法融合效果比较理想, 鲁棒性强, 具有较高的使用价值。 关键词　特征点提取和匹配　内点外点　优化估计　图像拼接 中图法分类号: T P31. 3　　文献标识码: A 　　文章编号: 100628961 (2004) 0420417206 An Automa tic and Robust Image M osa ic A lgor ithm ZHAO X iang2yang, DU L i2m in ( Institu te of A coustics, Ch inese A cad emy of S ciences, B eij ing 100080) Abstract　 In th is paper, an au tom atic and robust im age mo saic algo rithm is p resen ted. In th is algo rithm , H arris co rner detecto r is u sed to ex tract featu re po in ts, w h ich gain s sub2p ixel p recision fo r featu res ex tract ion. T hen, a p seudo m atch ing set is ob tained by comparing local neighbo rhoods of featu res th rough in tensity cro ss2co rrela t ion m ethod and these p seudo m atches are divided in to in liers and ou tliers u sing robust RAN SA C algo rithm. In the in2 liers sub2set, LM algo rithm is used to est im ate the po in t transfo rm ation m atrix betw een tw o im ages accu rately. In the end, the im age co lo r of the overlapp ing band is smoo thed w ith b ilinear in terpo lat ion techn ique. T he w ho le al2 go rithm is comp leted au tom atically. It filters the no isy o r w rong inpu t data iterat ively, then est im ates the model param eters th rough pure data, so it has strong erro r2to leran t capacity fo r the im age no ise and inaccu racy of featu re ex tract ion. W hen est im ating the model param eters, the energy function is constructed based on the po sit ion erro rs of featu res in stead of the featu res’ in tensity erro rs, w h ich conquers the o riginalm ethods’ sho rtcom ing of sensit ivity to illum inating condit ions and m akes th is algo rithm mo re p ract ical. Experim en tal resu lts show the im age mo saic ef2 fect is w onderfu l and the algo rithm is stab le very m uch. It is h igh valuab le in p ract ice. Keywords　ex tract ing and m atch ing featu re po in ts, in liers and ou tliers, op tim al est im ating, im age mo saic 1　引　言 由于摄像设备的机械限制, 广角的场景需要将 不同角度的成像进行平滑无缝的拼接融合, 从显微 镜、望远镜、手提摄像机到卫星成像系统也都需要用 图像融合技术来构造由一幅图片所不能表现的全景 图, 在计算机图像合成, 计算机视觉中, 也需要将融 合的静态纹理图像映射到 3D 模型上, 生成栩栩如 生的 3D 实体。对于这些图像的拼接融合, 目前普遍 的研究方法是通过两幅图像间的匹配特征点估计图 像间的点变换关系, 然后分别通过对两幅图像重采 样注册到一幅更大的空白图像中, 并在注册的过程 中在两幅图像的交接边界处进行颜色平滑过渡, 最 后形成一张融合的包含 2 幅图像信息的图像。整个 算法主要包含 3 步: 特征点的提取和匹配; 图像间点 变换的估计; 图像交接处的无缝过渡。对每步算法的 研究虽然已取得了一些成果, 但基本上还没有形成 一种稳健完全自动的拼接融合技术。R ichard 以手 动确定至少 4 对特征点[ 1 ] , 并以特征点像素的亮度 误差构造优化函数来估计图像间的点变换关系, 取 得了比较好的平面和深度场景融合效果, 但此算法 以亮度误差来做点变换估计, 这对图像的光照变化 非常敏感且整个算法的自动化程度不够。Po llefey 详细研究了特征点自动提取和匹配问题[ 2 ] , 但没有 针对图像处理做更深入的研究。Peter 分别运用多 分辨率样条技术和单调函数插值技术对图像的交接 处进行了有效的颜色平滑过渡[ 3 ] , 不过这是在特征 点匹配和点变换的准确估计基础上完成的。 基于以上算法的优缺点, 本文给出了一种从特 征点提取、匹配到图像间点变换估计和拼接融合的 全自动稳健算法。该算法的根本思想是对自动提取 的特征点集合, 以一种非常稳健的选择策略层层过 滤, 保证以提纯后准确的特征点数据来做点变换估 计, 这样就对自动的特征点提取和匹配的准确性放 松了限制条件, 把核心的任务移交给了特征点的过 滤策略和点变换的估计算法。 2　图像特征点提取和匹配 为了保证特征点的准确提取和匹配, 要求每幅 图像都用一样的特征提取算法, 每个特征点周围应 该提供足够的用于判定匹配的信息 (如靠近图像边 沿的特征点就剔除)。采用如下的H arris 角检测算 子来做特征点提取[ 2 ]: M = (5I ö5x ) 2 (5I ö5x ) (5I ö5y ) (5I ö5x ) (5I ö5y ) (5I ö5y ) 2 (1) 其中, I 为像素点亮度, (x , y ) 为像素点坐标。M 的 两个特征值的大小反映了像素点“突显”程度, 如果 (x , y ) 是一个特征点, 那么M 的两个特征值在以 (x , y )为中心的局部范围取得极大值。因此一幅图 像的所有特征点对应了一个特征点函数: R = detM - k ( t raceM ) 2 (2) 这里, k 是一个实验参数取值 (一般取 0. 04) , 特征点 就是此函数的局部极大值点。实践中, 应先对图像进 行低通滤波以减少图像的噪声。此方法特征点提取 精度可以达到亚像素级。提取特征点后, 每幅图像的 特征点有相当冗余, 采用以特征点为中心的灰度窗 互相关法来对有冗余的特征点进行匹配计算, 以像 素为中心选择一个 (2N + 1) × (2N + 1) 的灰度窗, 在 2 幅图像间做互相关运算 C = ∑ N i= - N 　∑ N j= - N ( I (x - i, y - i) ) - Iλ) ( I′(x ′- i, y ′- j ) - Iλ′) (3) 式中, I 和 I′为亮度值, Iλ 和 Iλ′为这个窗所有像素点 的亮度平均值。通过这样的匹配可以大幅度减少不 匹配的特征点, 当然留下的“匹配“特征点中也存在 一些伪匹配特征点。 3　图像间点变换的自动稳健估计 3. 1　图像间点变换的线性求解 图像A 和A′间的投影变换为(以齐次坐标表示) k x ′i y′i w ′i = h 0 h 3 h 6 h 1 h 4 h 7 h 2 h 5 h 8 x i y i w i 或向量形式: kx′i = H x i (4) 这里, k 是比例因子, H 有 8 个自由度, 理论上选择至少 4 对特征点就可以估计出H。通过叉积消去比例因子得 x′i ×H x i = 0 (5) 令, hTj 表示 H 的 j 行, 那么对每一对匹配点, 式 (5) 可以得到 2 个独立的线性方程组 0T - w′i xTi y′i xTi w′i xTi 0T - x′i xTi h 1 h 2 h 3 = 0　　 (6) 式 (6)解得的H 就一一对应地把一幅图像的点映射 到另一幅图像上了[ 4 ]。由于特征点检测的误差和选 取的 4 点中有 3 点可能共线, 这种线性解法的结果 往往很不稳定, 必须要通过一定数量的匹配特征点 集合来进行非线性优化。这里以对称投影位置误差 最小化来优化估计H , 其误差函数为 ∑ i d (x i, H - 1x′i ) 2 + d (x′i , H x i) 2 (7) 式中, d 表示距离。 一般地, 设特征点提取误差符合高斯分布, 那么 可以确定一个过滤噪声的阈值, 并定义 d v = d (x i, H - 1x′i ) 2 或 d v= d (x′i , H x i) 2 小于等于阈值的特征点 对为H 的内点, 大于阈值则为外点。很明显只有内 点才适合做点变换估计。由于第一步自动提取和匹 配得到的伪匹配特征点集合存在一些误匹配对和特 征点的精度误差, 因此需要一种容错能力很强的算 法来提纯内点。 3. 2　RANSAC 算法提纯数据 以直线拟合为例说明 RAN SA C 算法的思想: 814 中国图象图形学报 第 9 卷 在数据集合图 1 (a) 中随机选取两点形成一条直线, 并通过一定的阈值来寻找此直线的内点, 由这个内 点集合线性解出新的直线, 再根据此新直线寻找它 对应的内点, 不断地重复这样的随机采样, 直到某一 次采样使内点数量最大, 那么这次获得的直线估计 就是此集合的最好估计。如图 1 (b)所示, 直线 bc 获 得的内点较多, 它是这个集合的最好估计, 并有效地 剔除了外点。此方法的特点是充分地利用了所有的 测量数据, 并根据阈值把它们分成了内点和外点, 利 用内点数据比较准确的特点来进行参数估计而剔除 了不准确的测量数据, 因此, 得到的结果应该是一种 优化的结果[ 5 ]。针对这里的估计问题, 就需要随机选 取 4 对“匹配”点, 每次采样用 311 的方法计算H , 最 后根据提纯的内点集合来优化估计矩阵 H。显然 RAN SA C 算法有 3 个需要确定的量: 内点与外点的 距离阈值 t; 随机采样的次数N ; 多大的内点个数。 　　 (1) 距离阈值的确定　假设特征点提取误差是 符合均值为 0 标准差为 Ρ 的高斯分布, 这时, d 2v = d (x′i , H x i) 2是高斯变量的平方和, 它符合自由度为 m 的 ς2m 分布。由 ς2m 分布的积分性质知道: 符合 ς2m 分布的随机变量的概率小于积分的上限, 即 Fm (k 2) =∫k 2 0 ς2m (Ν) dΝ< k 2 (8) 那么阈值计算方法为 t2 = F - 1m (Α) Ρ2 (9) 则 内点 d 2v < t2 外点 d 2v ≥ t2 (10) 其中, Α表示符合内点条件的特征点对是内点的先 验概率, 一般取值 0195, 即符合式 (10) 判别条件的 点为内点的概率为 95%。通过 ς 2m 分布的查值表可 知 F - 14 (0. 95) Ρ2= 5. 99Ρ2, 因而对提取的特征点计算 出 Ρ就可以完全确定阈值。 (2)随机采样的次数　随机采样时, 理想情况是 搜索所有可能的组合, 但计算量非常巨大。如果模型 估计需要的匹配点为 s 对, 那么可以确定一个适当 的采样次数N , 以保证此时采样的 s 对匹配点都是 内点的概率足够高就可以了, 设以 p 来表示此概 率, 那么实践中只要保证此概率超过 95% 就能满足 实际应用了。设 p I 为任何一对匹配点是内点的概 率, 则 Ε= 1- p I 就是任何一对匹配点为外点的概 率。那么采样到N 次时有 (1 - p sI)N = 1 - p (11) 这样就可以确定需要采样的次数N 为 N = log (1 - p ) ölog (1 - (1 - Ε) s) (12) 以本文的模型为例: s= 4, 令 p = 0199, 则随着 Ε的增 加需要随机采样次数的变化情况如表 1 所示。 表 1　随机采样次数随外点多少的变化情况 集合中外点的比例 (% ) 5 10 20 30 40 50 60 70 80 需要的随 机采样次数 3 5 9 17 34 72 178 567 2 876 (3) 恰当的内点数的确定　如果总的特征点对 为 n 对, 则内点数为 (1- Ε) n。在实验中也可以多次 地迭代直到内点的数目基本趋于一致。 3. 3　H 的非线性估计 以式 (7)作为优化目标函数 F (H ) = ∑ i d (x i, H - 1x′i ) 2 + d (x′i, H x i) 2　 (13) 需要优化的参数为{h 0, h 1, ⋯, h 8}, 利用LM 非线性 优化算法来最小化式 (13) , 可以求得LM 算法所需 的近似H essian 矩阵 a 和加权梯度向量 b, 其各个分 量元素为 ak l= ∑ 5F (H )5h k 5F (H )5h l bk = - ∑F (H ) 5F (H )5h k (13) 这样就可以求得 H 参数增量: ∃H = (A + ΚI) - 1 b,Κ是一个随迭代步骤自动调节的因子[ 6 ] , 如果误差 F (H ) 减小则 Κ减小, 否则 Κ增大, 每一步更新参数 H (n+ 1) = H n+ ∃H 直到 F (H )下降到指定的精度。实 验表明此算法可以快速得到准确的变换矩阵H。 综上, RAN SA C 算法对 H 的自动稳健估计步 914第 4 期 赵向阳等: 一种全自动稳健的图像拼接融合算法 骤如下: (1) 运用H arris 角点检测算子提取 2 幅图各自 的特征点; (2) 用邻域像素灰度互相关法粗略估计 2 幅图 像的伪匹配点; (3) 运用RAN SA C 估计图像间变换矩阵: 重复 N 次随机采样 (a) 随机选取 4 对伪匹配点 (选取的 4 点应保 证H 的秩为 3) , 线性地计算变换矩阵H ; (b) 计算每对伪匹配点离H 的垂直距离 d v; (c) 根据内点距离小于阈值 d v< t= 21447Ρ 的 原则计算H 的内点, 并在此内点域上重新估计H ; (4) 由RAN SA C 的N 次随机采样得到了最大 内点集合, 运用LM 优化算法对H 进行优化估计; (5) 根据 H 再对所有数据进行内点计算, 直到 内点数目趋于一致。 4　图像交叠处的颜色融合 一旦准确地求得了图像间的点变换关系 H , 就 可以确定图像间交叠的准确位置, 并对两幅图像进 行重采样, 注册到一幅新的空白图像中形成一幅融 合图像。如图 2 所示, 求得了图像间的变换矩阵 H 12, H 32, H 2m , 就可以得到融合图像矩阵m 和图像 矩阵 1, 2, 3 之间的变换矩阵 H 1m , H 2m , H 3m , 根据此 变换对融合图像矩阵逐个像素地注册, 如像素 i 在 图像 1 中对应的像素 k 是由 k 周围的 4 个像素双线 性插值构成的, 因此注册过程是对图像的重采样过 程。在融合过程中, 可以对交叠处进行颜色插值或用 多分辨率样条技术进行颜色过渡[ 3, 7 ]。本文采用了简 单的双线性插值方法, 设图像 I 1 和 I 2 交叠区的 　　　 x 和 y 轴最大和最小值分别为 x m ax , x m in和 ym ax , ym in , 则融合图像 I 在交叠区的颜色值为 I = ΒI 1 (x , y ) + (1 - Β) I 2 (x , y ) (14) 其中, Β= (x m ax - x ) ö(x m ax - x m in) , 这种方法在多数 情况下都可以取得比较好的效果, 如果在交叠区 2 幅图像的亮度差别很明显时, 可以采用复杂的多分 辨率样条技术来解决。 图 2　图像的重采样注册融合示意图 5　实验结果 采用 800×533 和 1 024×768 的 24 位R GB 图 像, 在特征点提取阶段, 通过适当地限制特征点数目 来减少 RAN SA C 的随机选取次数, 特征点灰度窗 的大小为 15×15 像素。内点距离阈值为 t= 1125 像 素, 即特征点提取的标准差为 01510 7 像素。“书架” 匹配出了 45 对伪匹配点, RAN SA C 随机采样了 43 次, 以连续 2 次的内点数目相差不超过 1 为最终迭 代终止条件, LM 算法一般迭代 8 次左右就可以收 敛。“河岸”是 3 张照片融合成的,“研究室”是由 8 张照片融合而成的。图 3～ 图 9 给出了特征点提取, 特征点匹配和图像拼接融合的实验结果。 图 3　图像的特征点自动提取 024 中国图象图形学报 第 9 卷 图 4　基于灰度互相关法的伪特征点匹配集合 图 5　自动的图像拼接融合结果 图 6　河岸的 3 幅多角度原始图像 图 7　3 张河岸图像的自动拼接融合结果 124第 4 期 赵向阳等: 一种全自动稳健的图像拼接融合算法 图 8　“语音交互技术研究”室的 8 张多角度原始照片 图 9　“语音交互技术研究”室图像自动融合场景 6　结　论 本文提出了一种全自动图像拼接融合算法, 此算 法有这几个特点: 采用H arris 角检测算子提取的特征 点精度高; RAN SA C 把特征点分成内点和外点的策略 被理论地定量化, 为图像的自动拼接融合提供了强有 力的保证; 算法对数据层层过滤提纯数据的过程非常 稳健; LM 算法估计图像间点变换的域得到了优化, 保 证了LM 算法的精确估计和快速收敛。整个算法无论 是对输入数据本身还是图像的外部复杂光照条件都有 很强的容错能力, 是一种稳健有效的实用算法。 参 考 文 献 1　R ichard Szelisk i. V ideo mo saics fo r virtual environm ents [ J ]. IEEE Computer Graph ics and A pp lications, 1996, 16 (2) : 22～ 30. 2　Po llefeys M. Self2Calibration and M etric 3D Reconstruction from U ncalib rated Im age Sequences [D ]. Belgium: K. U. L eu2 ven, 1998. 3　Peter J Burt, Edw ard H A delson. A m ultireso lu tion sp line w ith app lication to im age mo saics [J ]. A CM T ransactions on Graph2 ics, 1983, 2 (4) : 217～ 236. 4　R ichard H artley, A ndrew Zisserm an. M ultip le V iew Geom etry in Computer V ision [M ]. Cam bridge: T he P ress Syndicate of T he U niversity of Cam bridge, U K, 2000. 5　F isch ler M A , Bo lles R C. Random samp le consensus: a paradigm fo r model fit t ing w ith app lication to im age analysis and autom ated cartography [ J ]. Comm unication A ssociation M a2 ch ine, 1981, 24 (6) : 381～ 395. 6　P ress W H , T euko lsky S A , V etterling W T , et a l. N uericla Recipes in C [M ]. Cam bridge: Cam bridge U niversity P ress, U K, 1992: 681～ 688. 7　R ichard Szelisk i, H eung2Yeung Shum. C reating fu ll view pano ram ic im age mo saics and tex ture2m apped models [J ]. S IG2 GRA PH 97 Conference P roceedings, 1997, 3 (1) : 251～ 258. 　　　赵向阳　1976 年生, 分别于 1999 年和 2002 年获得电子与信息工程专业学士和硕 士学位, 现在中国科学院声学研究所攻读 信号与信息处理专业博士学位。研究方向 为计算机视觉、语音驱动的人脸表情合成、 科学数据可视化等。 　　　杜利民　 1957 年生, 博士生导师, IEEE 高级会员, 1983 年、1987 年、1991 年 分别于北京大学、中国科大研究生院、中国 科学院声学研究所获理学学士、工学硕士、 理学博士学位。主要从事信号处理和语音 交互技术的研究。 224 中国图象图形学报 第 9 卷