9512.net
甜梦文库
当前位置:首页 >> 数学 >>

图像特征点匹配算法研究


南京理工大学 硕士学位论文 图像特征点匹配算法研究 姓名:刘莉娜 申请学位级别:硕士 专业:计算机应用技术 指导教师:朱近 20060601

硕士论文

翌像特征占昨配算往研究





特征点匹配是计算机视觉和模式识别领域中一个基本而重要的问题。有着广阔的 应用背景,如图像配准、物体识别、运动目标的检测与跟踪、手写体识别等。同时它


也是计算机视觉的一个难题,这不仅是因为在图像获取和特征提取阶段阈值选取不当 等过程中会产生不同程度的噪声,使得本来精确的特征点之间的对应关系变得难以确 定,而且点集中往往有出格点和非刚性形变的存在,使得点匹配变得艰难和复杂起来。 特征点匹配是要找到两点集之间的对应关系和空问映射关系。以点的位置表示点 特征是一种最简单的特征。在多数实际应用中,都是存在非刚性形变的情况下对特征 点进行匹配,因此本文针对非刚性特征点匹配给出了两种实用的匹配算法: (11提出基于寻找不变量的特征点匹配算法。它是对Chang等的点匹配算法pl进行 了改进,即利用原始算法的寻找匹配点对支持度方法来得到可靠的几何不变量,然后 给出了根据两点间距离不变量自上而下的推导出最大匹配点对集和仿射变换参数。理



论分析和实验结果表明本算法推理严密,在精确性和稳定性都有显著的改善,是一种
理想的特征点匹配算法。

(2)第二种特征点匹配算法是对基于确定性退火的点匹配算法进行改进,给出了适 合确定性退火算法求解的新的目标函数形式,提出采用相似性度量值来约束匹配矩 阵,加快了匹配矩阵收敛的速度从而减少计算量,在退火率较高时也能得到比较好的 解。实验也验证了在相同退火率的情况下能够得到比改进前算法好的匹配结果,并且
适当提高退火率时仍然能够得到比较理想的匹配结果.

关键词:匹配点对最大支持度 似性度量值

匹配集确定性退火匹配矩阵相



硕士论文

图像特莅点匹配算法研究

ABSTRACT

Feature points matching plays pattern recognition.It
call

an

basic and important role in computer vision

and

be widely used in

many areas

such

as

image registrtion,object

recognition,motion target detection on.At the same time,it is also


and tracking,handwritten

characters

recognition and
and

so

an difficult

tow problem in computer vision.Because the non。rigid

point

sets

not only have

different
the

degree of noise but also exist in outliers issue of points

lransformation,which make

matching

somewhat

difficult

and

complicated.
Feature points matching

intents

to

determine correspondence and transformation

between

two sets of points in space.It is the simplest by the point coordinate.In


form

of features that point features

represented
non-rigid

great number of pratical applications,there is

transformation

for points matching.So in this

thesis,two applied

feature points

matching algorithms are presented in allusion

to non-rigid feature points

matching:

(1)A based
● which improves

on

finding invariable approach for feature points matching is proposed

Chang’s points matching

matching pairs support method of invariable of

algorithms.The new original algorithms,and then
set and

approach

uses

finding

according as distance
to

two

points

between
set

one

another

set

from top

bottom gained

maximum matching pairs

and

affine

transformatin parameters.Theoretical analysis and
algorithm has rigorous consequence and

experimental results show that the bener accuracy and stability which is

improved


perfect feature points matching algorithm.

algorithm improve based on deterministic annealing point matching approach.The improved algorithm present the new form oftarget function which
(2)The second means
of fits for calculation of deterministic annealing
as

method,and

adopt

the comparability

measuring value matching matrix

restriction of matching matrix in order to accelerate convergence of reduce
can

and

quantity

of

calculate.when

anneal

ratio

is

relative

11igher,improved


algorithm

also receive perfect results.Experimental outcomes validate
are

that improved method’s reasults
ratio

better

than

original algorithms under the¥alTle anneal

and Can

attain perfect matching reasults all the same

when

anneal ration is

reduced

befittingly.

Key words:Matching pairs anneahng

Maximum support degree

Matching

set

Deterministic

Matching matrix

Comparability-measuring value
II


.‘

1001260





本学位论文是我在导师的指导下取得的研究成果,尽我所知,在 本学位论文中,除了加以标注和致谢的部分外,不包含其他人已经发 表或公布过的研究成果,也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。

研究生签名:

麴垫播

加g年5月27日

学位论文使用授权声明

南京理卫大学有权保存本学位论文的电子和纸质文档,可以借阅 或上网公布本学位论文的部分或全部内容,可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文,按保密的有关规定和程序处理。

研究生签名

麴蛰塑i

。彻孝万月)7日

硕士论文

图像特征点匹配算法研究



绪论

1.1引言
特征匹配问题一直是计算机视觉和模式识别领域中的一个非常基本而又重要的


工作。特征匹配是要找出对准两组或多组特征的空间变换。图像的特征反映了图像重 要信息,以这些特征作为模型进行匹配。局部特征有点、边缘、线条、较小的区域, 全局特征包括多边形和成为结构的复杂的图像内容描述。基于特征的匹配绝大多数都
是指基于点、线、和边缘的局部特征匹配。

特征点是图像内容最抽象的描述,与图像灰度相比,特征点相对于几何图像和辐 射度影响来说更不易变化,因此基于特征点的匹配方法可以克服利用图像灰度信息进 行匹配的缺点,由于图像的特征点比较象素点要少很多,大大减少了匹配过程的计算 量;同时,特征点匹配的度量值对位置的变化比较敏感,可以大大提高匹配的精度程
度;而且,特征点对图像噪声的影响,对灰度变化,图像形变以及遮挡等都有较好的

适应能力。所以基于图像特征点匹配在实际中的应用越来越广泛。 1.1.1气象图像配准
到目前为止,我国成功地发射的风云系列(FY)的气象卫星,为气象部门提供了

大量的气象云图,对于天气预报、各种灾害的监控和预防上,有着不可替代的作用,
而这些作用与气象卫星所提供的云图有着密切的关系。

本教研室的CCD成像仪多光谱图像配准项目是关于气象图像配准的研究,CCD成像 仪是气象卫星的主要载荷。经过调研在国内关于在不周谱段下成像获得的多幅气象图
像的配准问题的研究很少。正在研制中风云4号卫星,其核心的FY一4 CCD遥感器或称 为FY一4 CCD成像仪正在设计阶段。该卫星对同一个地区分时成像,得到一组多光谱的 图像和一组全色图像,由于更换滤光镜、转换压缩数据、传送数据给地面需要一定时

『日J,所以每次成像有大约20秒的间隔。因为是分时成像,在这个时J、日JI'甘J隔内,相机处


于一个非常复杂的运行状态。一方面卫星在轨道上向前飞行;另一方面,卫星又带有

随机的姿态变化,这个随机的姿惫变化可以分解为微小的方位旋转和微小的平移。以 上的因素将导致所得到的图像之『甘J有像差。由于像差的存在,在运用中会导致多光谱 和全色图像的信息融合不能很好地进行,进行像素级的数据融合则有很大的像差。所 以需要在具有20个像素的像差范围内,用30秒钟的时间,进行多光谱图像与全色图像
的配准,消除像差对多光谱和全色图像的信息融合所产生的影响,较好的将同一目标


颂士论文

图像特征点旺配算法研究

或区域的多个传感器的不同图像进行融合,从而提供信息更丰富、更真实、更清晰的 遥感图像,为进一步的分析处理做准备。


在研究中发现因为在多源图像融合时,由于多光谱图像灰度特征和图像的纹理信
息有差别,因此很难运用基于图像灰度的方法进行配准。而基于特征点的配准方法较

基于灰度信息的配准方法计算量小,抗噪能力强,不宜陷入局部最小值。特征点提取 后就需要特征点匹配,基于图像之间是刚性变换则可采用简化的仿射变换。由于待配


准的气象图像是R、G、B--通道在同一地区的分时成像,图像数据量大并且配准的实 时性要求高,试验中可知影响实时和准确性的关键是特征点的匹配算法,因此就需要 研究特征点匹配鲁棒性强,速度快,精度高的算法。 I.1.2医学图像配准 医学图像配准是医学图像融合的前提㈣,是目前医学图像处理中的热点之一,具 有重要的临床诊断和治疗价值。医学影像学为临床诊断提供了多种模态的医学图像, 如x线断层成像、MRI、fMRI、SPET、PET、DSA、超声成像、脑磁图等。不同的医学 影像可以提供人体相关脏器和组织的不同信息。如cT具有较高的空间分辨率,有利于 定位病灶,MRI对软组织成像清晰,有利于确定病灶范围。而PET和SPET虽然空间分 辨率较差,但却提供了脏器的功能和代谢信息。所以临床医生迫切希望对不同图像信 息进行适当的集成。然而不同模态的医学图像成像原理不同,分辨率不同,成像参数等 不同,因此在图像融合Ii{『必须先进行图像配准。。配准结果应使两幅图像上所有的解
剖点,或至少是所有具有诊断意义的点都达到匹配。 医学图像特征点匹配的方法从变换角度来分,可以分为用刚性的和用非刚性的



(包括仿射、投影,弹性变换)两种方法。由于刚性变换不考虑坐标轴的尺度缩放,仅
存在坐标轴的平移和旋转在用于同一模式和不同模式的医学配准中已经发展成熟并 且在临床中得到了应用。然而,刚性的特征匹配只适用于不存在变形或刚性体的配准,

如:由于大脑的变形基本上被颅骨限制,所以同一患者的大脑图像可以通过刚性变换 来联系。对于患者和图谱之『自J的匹配,不同患者之『BJ的配准以及存在变形的配准(肿
瘤,开颅手术等)刚性的特征点匹配都是不适用的。然而,医学图像配准中刚性体的


匹配只是很小的一部分,许多重要的临床应用需要非刚性变换柬描述图像之间的空间

关系。比如:
(1)在图像引导的神经外科和立体定向放射治疗中,为了提高定位的准确性和

自动化程度,需要将患者的图像和杯准图谱进行配准。在比较不同个体或人群大脑的
形状和功能的研究中,以及建立大脑的统计模型和图谱时,需要将不同患者的图像进 行配准。此时就需要非刚性特征点匹配来保证良好的配准效果。


硕士论文

图像特征点匹配算法研究

(2)在研究腹部以及胸部脏器的图像配准中,由于不自主的生理运动或患者移 动等使其内部的器官和组织的位置、尺寸和形状发生改变,以及在图像引导手术中由 于干涉引起的组织变形,需要非刚性变换的特征点匹配来补偿图像变形。 1.1.3运动目标的检测和跟踪 运动目标的检测和跟踪是计算机视觉和图像序列分析中重要的研究课题,它可以


应用于交通监视、导航控制、运动估计等领域。运动的目标根据相机的运动情况主要 分为两类:一类是相机不动,目标运动:另一类是相机和目标都在运动。这两类情况势 必会引起|;i『后两幅序列图像的非刚性空间变换。对运动物体的跟踪分为二维运动和三
维运动的跟踪,主要是确定物体的二维或三维平移、旋转参数,并籍此求出物体的运

动轨迹及规律。特征匹配法是的二维运动物体跟踪的离散方法中常用的一种。它是利 用特征匹配的方法找出两幅图像的对应部分及坐标,从而得出运动参数。文献[31] 就是采用抽取两个特征点即运动物体的形心点的然后作匹配的两点匹配算法来求出
运动物体的运动参数。由于点特征不仅特征明显,而且稳定性好,所以基于特征点匹配 技术估计全局运动矢量的应用也比较多【32】.这就需要有计算快捷、精度高、适应性强


的特征点匹配算法。 1.1.4手写体识别 手写体识别是字符高速、自动输入计算机的重要手段,是智能计算机接口的一个 重要组成部分,在文献检索、办公自动化、邮政系统、银行票据处理等方面有着广阔 的应用前景。目前印刷体汉字识别系统已经走出实验室,加入到办公自动化产品的行
列,得到了广泛应用。手写体识别从字体的形式来分有数字字符识别和汉字及其它字

符识别,从识别的手段来分又可分为联机手写体识别和脱机手写体识别。其中手写体
汉字识别一直是模式识别研究领域中的难点。正是手写体汉字的自身特点给手写体汉

字的识别带来诸多不利的影响。这些特点包括:①汉字的样本集类别多而且样本数量 巨大;②样本类别间的差距不平均,有些类别『日J的差别很大,而有些类别『日J的差别极 其细微;③不同的书写者书写的汉字样本风格于差月别,下笔轻重不同,笔划粗细不


同,样本的大小、旋转方向、倾斜角度不统一,有些字写得偏左、偏右、偏上或偏下
等。而脱机手写体识别由于缺少笔划和笔顺信息。识别难度远远大于联机手写体识别。

现有的脱机手写体识别方法有许多种,包括模糊的方法,网络神经元的方法和基于组
合特征的方法等。其中有一种识别方法先将手写体配准,再进行分类,根据不同的类

别确定字体所代表的含义,两特征点集之『日J的距离可以作为分类的杯准。


硕士论文

图像特征点匹配算法研究

1.2课题的目的和意义
特征点匹配是计算机视觉和模式识别领域中的一个基本且重要的问题,特征点匹 配的主要任务是,要找到两点集之间的对应关系和空间映射关系。它适用于解决计算 机视觉应用中的许多问题,如图像配准、物体识别、运动目标的检测与跟踪、手写体
识别、飞行器导航和姿态测定等。因此这种点模式匹配问题在图像匹配和图像配准中


有广泛的应用背景。传统的模板匹配算法精度较高,但它难以处理图像伸缩、旋转、 目标物体被部分遮挡等复杂情况下的位置测量,此外它的效率较低,特别是当搜索空 间的维数增加时其效率将急剧下降。点模式匹配在输入图像伸缩、旋转、平移、目标 物体被部分遮挡、存在非刚性形变等情况下,能快速有效地完成两个图像中特征点集
的匹配,具有很高的鲁棒性。

特征点匹配是模板点集和目标点集之间的匹配,图1.2.1显示了利用特征点匹配 进行图像匹配的流程:



蕊砑户
提取特征点集
图1.2.1图像匹配中的特征点匹配 图1.2.2图像配准中的特征点匹配

同时,特征点匹配在图像配准中是基于特征的图像配准中必要和重要的一步。图

1.2.2显示了利用特征点匹配进行图像配准的流程;其中特征点匹配的正确性和速度 直接影响了图像融合后的效果和整个配准的实时性。

从特征点匹配在图像匹配中的地位束分析。图像匹配可分成三大类:基于灰度相 关的方法,基于特征的匹配方法和基于解释的特征匹配方法。基于灰度相关的方法是


一种对图像以一定大小的狄度阵列按某种或几种相似性度量顺序进行搜索匹配的办
法。这种匹配一旦进入信息贫乏,或图像有较大的比例尺差异或扭曲的区域,匹配难 免失败,而基于解释的图像匹配技术需要建立在图片自动判读的专家系统上,目前尚 未取得突破性进展,所以基于特征的方法在图像匹配中就显得特别重要。基于特征的

匹配绝大多数都是指基于点、线、和边缘的局部特征匹配。而特征点是所有特征中对 图像噪声的影响,对灰度变化,图像形变以及遮挡等都有较好的适应能力。这使得特


硕士论文

图像特征点匹配算法研究

征点匹配在实际中的应用越来越广泛。 从实际应用的实时性和准确性要求角度来分析。在早期的图像匹配的算法研究中 主要是对两幅图像空间域上的灰度进行相关运算。常用的方法有:归一化互相关、统 计相关、平均绝对差、平均平方差;基于FFT频率域的频域相关,包括相位相关和功 率谱相关;不变矩;这些基于图像灰度相似性的匹配方法主要缺陷是计算量太大,因 为使用场合一般都有一定的速度要求,所以这些方法很少被使用。现在已经提出了一


些相关的快速算法,如幅度排序相关算法,FFT相关算法和分层搜索的序列判断算法 等。但是上述算法还存在如下缺陷:①影像(即图像)的灰度因获取的时间、季节,
天气等变化及不同传感器拍摄而产生的差异很大,甚至在局部有反转的情况。而且由

于基准图像的更新时间较长还会出现地形地物等内容发生变化,导致影像局部不相 似;②计算复杂度高;③对目标的旋转,形变以及遮挡比较敏感。所以采用基于图像 灰度相似性的匹配方法就显得不能满足匹配的要求。而点模式匹配方法可以克服利用 灰度信息进行匹配的缺点,因图像的特征点比像素点要少很多,大大减少了匹配的计 算量;同时特征点的匹配度量值对位置的变化比较敏感,可以大大提高匹配的精确程
度。

从硬件发展的水平来分析。利用机器视觉进行各种精密测量,主要有三个环节对


测量精度起到关键性的影响:摄像系统的物面分辨率,摄像系统的标定和误差修正精 度,图像中目标的定位精度。要提高测量精度,可以选用高分辨率的CCD摄像机, 提高光学成像系统的放大倍数,或采用特殊的光源进行照明。但是这些方法有很大的 局限性,如:高分辨率的CCD摄像机提高了对图像传输速度、存储容量的要求,过
高的放大倍数减小了视场范围和输出信号的强度。总之,通过提高硬件分辨率的方法 来提高测量精度是不经济的和有限制的。因此,需要用软件处理的方法来解决图像中

目标的高精度定位问题。 因此,从以上几个方面来看对特征点匹配算法的实际应用需求较多,对精度和时 间以及鲁棒性的不断提高从而适应不同的应用需求。同时,特征匹配基于点特征、线 特征、面特征三种方式,但是大多数情况下无论是线特征还是面特征最终也要归结为
点特征,如线特征的拐点、面特征的重心等。所以本课题就是从这方面的需求来出发,

基于现有的特征点匹配算法提出了两种改进的特征点匹配算法。


I.3本文的主要工作
1.3.i课题内容 本课题从特征点匹配算法的发展和现有有算法的讨论结合特征点匹配算法的应


硕士论文

图像特征卓匹配算法研究

用出发,首先讨论特征点匹配在气象图象医学图像等配准、运动目标检测和跟踪、手 写体识别等具体应用的角度分析TIE在对特征点匹配算法的需求,阐明了点匹配算法 的研究方向是根据应用向更精确,更快,更具有鲁棒性的趋势发展。 基于灰度相关的特征点匹配算法是以往常用的方法,但是算法要求特征点应该位 于灰度变化的区域的中心,例如孤立点、拐角点。且要求以特征点为中心,在其周边 方向上灰度差应当较大。这样,在特征点匹配时比较容易搜寻。如果在一条直线上,


选择了若干特征点,因为直线上特征点的灰度差为零,在另一幅图像的特征点匹配就 会发生混淆,以至于找不到对应得特征点【l】。同时这类算法对两幅图像灰度信息变化 较大、有部分遮挡、存在图像噪声的情况适应性不强,且通常都只针对刚性变换的匹
配,对于非刚性点和局部扭曲此类算法无法解决匹配问题。

不幸的是在多数实际应用中,都是存在非刚性形变的两幅图像特征点进行匹配, 因此本文以点的位置表示点特征,在非刚性形变的情况下,根据现有的两个特征点匹
配算法进行改进。

首先本文第三章的算法对Chang等的快速点模式匹配算法哪进行改进,即利用 Chang等的算法中寻找匹配点对支持度方法束得到本算法所需的可靠的几何不变量。
主要对Chang等的算法中确定匹配点对(MPD--Matching
Pairs

Determination)方法

进行改进,包括给出了两点间数量不变量,然后自上而下的推导出最大匹配点对集和
仿射变换参数。在算法描述中进行理论分析对原算法改进的原因和改进的措施。最后

针对仿真和真实图像的在抗噪能力和出格点的处理能力以及抗形变能力分别进行了
试验与分析,预期结果是在精确性和稳定性都有显著的提高。 其次本文第四章的算法对基于确定性退火的点匹配算法进行改进,给出了适合确

定性退火算法求解的新的目标函数形式。本算法提出采用相似性度量值来约束匹配矩 阵,加快了匹配矩阵收敛的速度从而减少计算星,在退火率较大时也能得到比较好的 解。预期在相同退火率的情况下能够得到比改进前算法好的匹配结果,并且适当提高
退火率时仍然能够得到比较理想的匹配结果, 1.3.2课题难点

由于国内对特征点匹配算法的研究还不系统,同时国内关于特征点匹配相关的资


料也较少,很多都只是将某种特征点匹配算法在一个具体问题中的应用,而且并没有 对其比较和研究,因此在本课题_丌=展的前期需要收集和阅读大量的外文文献,同时对 特征点匹配算法在实际应用中归纳总结,并且对典型的算法进行分析试验。
在前面已经介绍了点匹配技术所获得很大的进展,但它仍然存在不少困难,首先 在图像获取和特征提取阶段的阂值选取不当等过程中都会产生不同程度的噪声,使得








硕士论文

图像特征点匹配算往研究

1.5本文各章内容安排
本文分五章展开,其中第三章和第四章是本文的重点。
第一章首先概述了特征点匹配算法在图像配准、运动目标检测和跟踪、手写体识

别等领域的应用需求,然后说明本文研究的特征点匹配算法的目的和意义,接着将本 文的主要工作在课题内容里做了阐述。最后对本文采用的丌发工具简要介绍。


第二章对点匹配算法的研究现状做简要介绍,首先分析特征点及特征点对解决匹 配问题有利的一些特性,然后对现有的点匹配算法回顾分析与分类。最后给出本文中 要用到的相关知识,以便于的理解本文后面给出的两个算法。 第三章提出了基于寻找不变量的特征点匹配算法。这是对快速点匹配算法的改
进,首先对快速点模式匹配算法进行分析并说明对快速算法的改进方案,然后对改进

后算法进行详细的描述,给出了最大匹配集求解算法。通过仿真和真实图像的实验比 较原快速匹配算法,来说明本章改进后算法的在抗形变、抗噪声和抗出格点三方面性
能的提高。 第四章提出基于确定性退火的非刚性点匹配的算法。首先在给出新的点匹配目标

函数前,说明点匹配矩阵表达形式和满足的约束。紧接着本算法给出了适合确定性退


火求解的新的目标函数一股形式,并分别给出在仿射变换和薄板样条两种映射条件下 的目标函数。然后详细介绍相似性度量值及其计算,还有匹配矩阵的求解。最后推出
基于确定性退火的特征点匹配算法的整体框架,并进行实验比较与分析。

第五章,总结全文并指出本文算法的可行性以及需要进一步研究和解决的问题。















顿卜论文

图像特征点匹配算法研究

定的闽值。但该算法当有丢失点特征,或出现虚假点特征的等不利情况时,容易导致
错误匹配,从而得到错误的空间变换参数。Jezching和Anil也采用了松弛算法的匹

配策略ⅢI,并引入了匹配矩阵的概念,他们采用了双向匹配的思想。双向匹配的概 念是两个图像中的特征点均可以在另一个图像中选择匹配点。这种双向匹配的改进更 能够产生更多一致的匹配点对。但是他们的这个算法必须保证两个点集中能够存在一 半以上的有效点。Z.Zhang和R.Deriche给出了一个较好的基于互相关函数得点特征


匹配算法I…。该算法首先利用互相关获得点集之间得初始匹配;接着利用对极几何

约束改进精匹配。以上算法采用了不同的相关准则来度量特征点的相似度,通过初始 匹配和进一步加上一定约束条件来筛选匹配点对的模式来得到精确的特征点匹配点
对。

以上一些特征点匹配算法利用特征点附近某一个窗口内象素的灰度信息,根据不 同的获度统计特性的匹配准则(最常用的交叉相关准则)来判断特征点的相关性。但 是图像存在的遮挡和图像灰度变化较大的情况往往将影响算法的效果。还有一些算法 是利用特征点的位置信息及两个点集之间的不变量来确定特征点的对应关系。Lihua Zhang的仿射变换下基于遗传算法搜索策略的特征点匹配算法1”】,通过构造点集的特 征椭圆和遗传算法(GA)的并行机制来减少遗传算法的解空间,因此这种方法计算效


率较高匹配结果较理想,但是如果存在一个3一元组合错误的封闭于一个特征椭圆内
这将在另一个点集中找不到对应的3一元组合。Chang等人的快速点模式匹配算法p1用

聚类的方法确定匹配两个点集的旋转量0,然后根据旋转量0找出所有的匹配点对,
最后由最4,-乘法精确地确定出匹配参数仿射变换参数。这个算法在效率上有出色的 表现,但是由于算法中引入五个阂值使得算法的精确度和稳定性较差。Steven
Gold

等人提出一种点匹配的新算法【9】,采用确定性退火算法的搜索策略和软分配过程,该 算法对于噪声和高比例的丢失点及虚假点体现了较强的鲁棒性,但是该算法要求初始 温度足够高退火率足够低才能保证找到全局最优,这使得匹配时间消耗较大。Toru

Wakahara提出了一种类似于迭代匹配最近点(ICP)方法的算法I”】,它的思想是在迭
代每一步根据最近的一对点确定对应关系,再由对应关系找到空『日J变换。它同时提出 局部仿射变换(Local
Affine

Tansformation)的概念,使整体的空『日J映射具有更好

的自由度。国内对于解决特征点匹配问题的算法不是很多,但近几年也引起了许多学


者的关注,Pan Jun—Jun和Zhang Yan—ning提出了一种基于点位置相似性的点匹配 算法|’81,它采用了最小化欧几垦德距离总和的规则来匹配对应得点,使错误匹配减

少。该方法仅基于特征点的位霄特征以较少的时间消耗达到了最多的正确匹配点对。
Xiang—Yu

Yu等人的点匹配算法ll卵中引入了点集的凸核顶配对的思想。通过凸核顶配

对来减少特征点的数目,变换参数和点集间的匹配在迭代的每一步都被更新,然后由
点之间的顶和距离共同判断是否两个点是匹配的。变换参数的求解是当所有的点部被







颟十论文

图像特征点匹配算j杰研究

变换后仍然是直线,则这种变换成为刚体变换如图2.2.1.1。刚体变换可分解为平移、 旋转和反转(镜像)。在二维空间中,点(x,y)经刚体变换到点(x’,y’)的变 换公式为:

[;-]=。c。。ons妒9千_+d,iⅪ-缈.1。ryq.+[乏]


其中伊为旋角,瞳]为平移向量。

原始图像 图2,2.1.1刚体变换

变换后图像

◆仿射变换


经过变换后第一幅图像上的直线映射到第二幅图像仍为直线,并且保持平行关 系,这样的变换称为仿射变换如图2.2.1.2。仿射变换可以分解为线性(矩阵)变换和 平移变换。在2D空间中,变换公式为:

[;t]=。口a甜l o口篮q.。yq.+[≥]
仿射变换重要性质是“保直线”,仿射变换包括刚体变换。



原始图像 幽2.2.I.2仿射变换

变换后图像

◆投影变换

经过变换后第一幅图像上的直线映射到第二幅图像上仍为直线,但平行关系基本 不保持,这样的变换称为投影变换。投影变换具有更一般的形式,它适用于景物平面
13







硕}论文

图像特符点匹配算j杰研究

2.2.2最小二乘法求仿射变换参数 这一节将介绍最小二乘法估计两个特征点集的仿射变换参数,前提是已知两点集
的一对一的匹配关系。同时这一节的知识将在第三章的算法中用到。

如果在两点集P和Q中有k对匹配点对{(p,,q。)f i=l,…,k且k22}。我们需要 计算的仿射变换参数G(驭,ty,s,护)就是使一个点集中的点经过此变换后的坐标


与另一个点集中对应的点的坐标欧式距离的平方和S(tx,ty,s,口)最小的变换。令e.为 P,的坐标与q。变换后的坐标G(q.)的差。

=旺

S C +





X 以 一

、,● J

/,● L

JS

∞.口

口口



幽∞



口口

、 ● / ,.。 . L K% 、 ● ●,

,。. L y n 、● ● /



㈣-yq,ll--Yq’斟㈡
=(::囊

。斟㈡

~kp…s证盯,巳=∽囊≥]


C叽
,p

E=



厶厶
,. 。 L

C口2



…C


q色;气

、● ● ● J








C口‘

r一[至]

。:.:.:.2,



其中Pr=(pi

z…∥),Cr=(c:C妇r…c:)。


所以可以将S(tx,吼s,p)表达为:



S(t)=Zere,=(i《…《)
J。l















硕士论文

凰像特征苣匹配算法研究

2.2.3搜索策略 由于形变、出格点和噪声等多个因素的影响,使得特征点匹配过程本质上是一个 多参数的最优化问题,在给定目标函数的条件下,可能会出现多个局部极值,这就使 得求取一般单极值的算法无法完成此工作。而必需通过将目标函数嵌入到各种搜索策
略中求出匹配目标函数的全局极值,从而得到最优的匹配。所常用的搜索策略有:模


拟退火法、确定性退火法还有遗传算法等。本文的第四章算法用到确定性退火法,这
里将对点匹配算法中常用的搜索策略做简单介绍。 ◆模拟退火法

模拟退火算法是一种能使优化问题获得全局最优解得方法。该算法是由 Metropolis等人在1953年提出的,它代表了一类鲁棒的优化方法【”J。模拟退火算法 对表示复杂系统好坏的目标函数(代价函数)进行最小值搜索。它适用于NP完全的优 化问题;它并不保证找到全局最优解,但通常可以得到近似最优解。 Cernyl28】经常用下面的例子来说明模拟退火的原理。想象一个盛方糖的糖罐,通 常会有一些方糖与糖罐的形状不吻合,使得无法合上盖子。根据日常经验,每个人都
知道将糖罐摇一摇可以使方糖自动移到更合适的位置,于是就可以合上盖子了。换句


话说,将罐子中所装的方糖块数视为评价函数,摇动罐子可以得到近似最小解(对于

方糖所占的空间来说)。摇动罐子的程度时这个优化过程的一个参数,对应与下面要
说的加热和冷却过程。

模拟退火综合了两个基本的优化原理:分而治之和迭代改进。这样的结合使用可
以避免停止在局部最优上。模拟退火算法的思想,是基于固体物质的退火处理过程。

在对固体物质进行退火处理时,通常先将它高温加热,使其中的颗粒可以自由运动,
然后随着温度的逐渐下降,颗粒也逐渐形成了低能太的晶格。如果在凝结点附近的温

度下降速率(退火率)足够慢,则固体物质一定会形成最低能量的基态。 对于优化问题也存在着与固体物质退火处理相似的过程。在优化问题的解空间中 的每个点都代表了一个解,不同的解对应着不同的函数值,优化过程就是在解的空间
中寻找目标函数最小的解。在模拟退火算法中,如果系统的变量变化后,能量函数有 更低的值,那么就接收这种有益的变化;如果在系统的变量变化后,能量函数没有更


低的值,那么就按预先确定的概率分布接收这种变化。这就是说系统不但能接收能量 函数减小(性能改善)的变化,而且还以某种概率分布接收能量函数增大(性能变差) 的变化。这实际上给系统得变量引入一些“噪声”。使系统更有可能跳出能量函数的 局部最优区域面向全局最优区域搜索。 传统的启发式搜索算法,如快速下降法,都是向能量函数减小的方向搜索。这种

算法往往会导致搜索过程停留在系统得局部最优而不是全局最优的区域,因而是一种
17

硕士论文

图像特符点匹配算法研究

“贪心”算法,该算法的搜索过程如图2.2.2.1所示,模拟退火算法搜索过程如图2.2.2.2
所示。










、√.






、√。



图2.2.3.1“贪心”算法搜索示意图

图2.2.3.2模拟退火算法搜索示意图

结合以上基本思想,模拟退火算法的框架为: 1.令x为优化参数的向量,计算目标还书J(x)的值,T=T。。 2.将第3步和第4步重复n(T)次: 3.对参数向量X做轻微扰动,得到新向量x一,计算新的优化函数值J(x。)a 4.生成一个随机数rE(O,1),满足区N(O,1)上的平均分布。若:


,<唧{二垫堡)二型)}
‘【
,’



则令x=x。且J(x)=J(xnew)。

5.T=a+T,如果T>TM,则回到第2步,否则算法结束。
6.这时参数向量x表示优化问题的解。

注意,事先并不知道需要多少次迭代步骤,怎样的参数扰动(状态改变),选择 什么温度T、采用多快的冷却速度才能得到最好的结果,虽然有一些一般性原则可供 参考,但对于特定的问题有特定的合适参数。目前只知道对任一温度来说,退火过程
都应该足够长的时间来达到稳定状态。如糖罐的例子:开始时摇动会比较剧烈,然后 逐渐变缓已达到最好结果。

退火率和每个温度达到热平衡所需的迭代步数n称为退火进度。较大的迭代步数 n和较小的温度T变化步长可以产生的最终优化函数值也更低(解更接近于全局最


小),但需要较长的计算时『日J。较小的迭代步数n和较大的温度T的变化步长可以更 快结束,但结果也可能离全局最小比较远。因此需要仔细设置T和n的值,使得在可 以接受的时『日】内得到比较接近全局最小的解。然而目前还没有设计出退火进度的实用
方法。 ◆确定性退火法

确定性退火技术是由美国加州理工学院的K.Rose博士于1990年首先提出的陋1。

硕士论文

图像特征卢匹配算法研究

它类似于模拟退火算法,同样采用了物理学中通过缓慢降温可以将材料的能态降到最 低的理想热平很状态。不同的是这里的算法在每一个温度下,对最为变量的优化参数 施加的是确定性,而不是随机的值。它通过控制作为变量的优化参数的熵,使熵值由 最大值变到最小,在熵值变化的每一步对目标函数进行优化而逐渐求解出一个全局的 比较好的解。这样就把原来的可能存在多个极值点的非线性问题凸化。 与模拟退火法相比,它只需要较少的迭代次数便可在每一个温度下达到热平衡状


态。它在性能和计算复杂度两者之间作了一个很好的折衷。在实践中,确定性退火和
模拟退火给出相似的解。对于大规模的现实问题,确定性退火要快很多,有时可以快

2--3个数量级m1。因此确定性退火算法在特征点匹配尤其是对于非刚性点匹配的复杂 问题有较多的应用,如文献【5、7、8、9、40】。 将确定性退火法应用于特征点匹配具体实现方法为:定义点对应关系的匹配矩阵

H,然后在目标函数中加入一项表示H的熵的阻尼项:T∑气009k—1)。通过调整
退火温度T实现对H的熵的控制,迭代的求解空间映射和灯应关系,最终实现点匹
配。

确定性退火技术的求解框架: 1.取足够大的T。,令k---O,求解目标函数minF(X,Tk),设最优解为:X。(T k)。

2.Tk+I--aT

k,a为退火率且O<a<l,以x。(T k)为初始解,求解minF(x,Tk+1);

设最优解为X。(T。。)。 3.判断收敛性准则是否满足,若满足,则停,X。(T k+1)为最优解;否则转步 骤4。 4.k=k+1,转步骤2。

◆遗传算法

遗传算法是一种模拟自然选择和遗传得随机搜索算法。它由密执安大学John
Holland提出,最初用于研究自然系统得适应过程和设计具有自适应性能的软件。近

来,遗传算法作为问题求解和最优化的有效工具,引起越来越多的注意,在特征点匹
配问题也有应用,如文献[15、17]。 遗传算法是一种迭代算法。它在每一次迭代时都拥有一组解答。这组解答最初是


随机生成的。在每次迭代时又有一组新的解答由模拟进化和继承的遗传操作生成。每
个解答都由一个目标函数给予评价,而且这一过程不断重复,直至达到某种形式上的

收敛。新的~组解答不但可以有选择地保留一些目标函数值高的旧的解答,而且可以
包括一些经由其它解答结合而得的新的解答。

遗传算法的术语借鉴与自然遗传学。一个解称为一个符号串或染色体。染色体由 决定其特性的基因构成,而基因又可以有称为等位基因的不同取值。目标函数称为适







硕士论文

酗像特征皂匹配算法研究

3基于寻找不变量的特征点匹配算法

3.1引言
我们知道,一种优秀的点模式匹配算法是能够有效地利用几何的不变量(平移量、


旋转量、缩放量),在存在形变,局部扭曲和噪声以及虚假点和丢失(统称为出格点)

的情况下,将两个点集完全且正确的匹配。所谓完全匹配是得到两个点集中的最多的 匹配点对。 本章给出的基于寻找不变量的特征点匹配算法,是对Chang等快速点匹配算法【3】 的改进。首先简要介绍Chang等的算法并分析算法中存在的不足。 Chang等快速点匹配算法IJI是一种具代表性的点匹配算法。它是将Stockman等 给出的一种基于聚类的点匹配方法㈦进行了改进。将点集中的点矢量化,因此参数空 间维数由四个G(tx,ty,s,口)减少到两个G(s,p),提高了计算效率。算法分了三步:① 点对的最大支持度算法(MPS--Matching pairs support),用聚类算法来计算两个点集


中任意一对点的最大支持度。②通过确定缩放和旋转参数算法(SRF--Scale and
rotation finding

algorithm),找到两点集缩放和旋转量。⑧根据得到的缩放和旋转量,
pairs

用确定匹配点对算法(MPD---Matching

determination)来找到最终的匹配点对,

再用最小二乘法优化仿射变换参数。经过分析和实验其算法仍存在以下缺点: 1.第二步确定缩放和旋转参数的算法中,不但需要找到最大匹配支持度对应得缩 放量s还需要记录对应旋转量目。而且算法中引入了一个阚值P。,它的含义是足够
大的支持度,在算法中的作用是当两点集中的任意一对点的最大支持度如果大于该 值,那么算法结束这对点的最大支持度对应得缩放量和旋转量就是所要确定参数值。

对于不同的图像由于形变,噪声和局部扭曲程度以及匹配点对数目会不相同,而这些
因素在匹配前都是未知的,那么足够大的支持度匕就很难确定,这降低了算法的稳

定性。如果足够大的支持度设置不当,还使得确定的变换参数(s,口)的值不可靠, 拿不可靠的变换参数(s,占)束进行下一步的确定匹配点对本身就引入了一些误差,
降低了算法的准确性。


2.第三步确定匹配点对算法中,进行三次搜索可能匹配点对。根据已知的不可靠 的(S,口)计算可能匹配点对,又用得到的可能匹配点对计算近似仿射变换参数进 而来第二次和第三次搜索确定可能匹配点对;在此过程中引入了兰个阈值

(as,a目,ad),如果这些阂值设置不当则将导致丢失匹配点对和多对一的误匹配的情
况发生,同时降低了算法的稳定性和准确性。而且该算法能够解决一对多(模板点集





已得到的不变量定义出两点间的距离不变量(见定义3.3—1),然后根据这一不变量 利用自上而下的求得最大匹配集的方法,来得到最多的匹配点对。因而不需要Chang 的确定匹配点对算法在判断是否为匹配点对的约束条件中引入三个阈值(as,a口,ad)。
且最多的匹配点对确保求得的仿射变换参数是最优的。因此进一步提高了算法的准确 性和稳定性。

当给定的两个点集的点数与它们的最大匹配点对集的长度接近时(在很多实际应
用中的确如此),该算法的计算效率也不低于Chang的快速点匹配算法。本章将从理 论分析和实验环节中对两个算法进行详细讨论和性能分析。 为了便于本章后面的内容阐述,下面对点匹配问题进行描述。


有两个点集P和O。点集P是由第一张图像上提取的特征点,点数为n:

P={nP:.….P。}。点集Q是由第二张图像上提取的特征点,点数为m: Q一{口,.q2.….qm}。两点集可能存在有噪声和丢失点以及虚假点的情况,同时允许两个
图像有局部的轻微扭曲。每个点的位置特征由二维列向量(工,y)7来描述,x和Y分别
是点在图像上的横纵坐标。那么点集P和Q数学描述为:

JP={(‰,%)7 li=l,…,胛)和Q={(‰,Y。a)r Ij=l,…,m)
22

硕十论文

图像特征点匹配算法研究

存在唯一一个配准空间变换参数G似,纱,s,毋),匹配算法就是在满足该变换参数G
条件下,要找到点集P中的点只与点集Q中一个确定的点鼋,相对应(或者说相匹配)。

本章中G(tx,ty,s,目)是由四个变换参数5,口,tX和ty组成的仿射变换,其中s是缩放量、 0是旋转角度、tx和O,分别是沿X轴和Y轴平移量。由于两个图像的空间变换是仿射 变换类型,因此~个图像中的直线映射到另一个图像中仍然是直线,一个图像中的四 边形映射到另一个图像中仍然是四边形并且平行关系没有改变。这种仿射变换是针对 图像全局的而不是图像局部的变化,因此点集间的几何关系也是服从这一变换。



、T



、T

那么一个点P=lxp,Yp J和一个点q=1%,%)之间的变换关系为:
g=G

cp,j(;:)=(乏]+。s,x。c。io。s护B-,a。x。s。i。n口B,l。Cyxp,]
(3.1.1)

由于两点集中点的位置关系未知,因此G(p)也许不等于口。但对于两点集中每 对匹配点对只和q,(尽管我们现在还不知道两点集中点与点的对应关系)都有这样

的性质:G(只)是最接近点g,,即¨G(p)-q,11<11G(po)-q,II,其中口∈{1,…,H)且口≠f?
基于寻找不变量的特征点匹配算法的目标是寻找到点集P和点集Q之间最多的


匹配点对,从而能得到更精确的仿射变换参数。

3.2匹配点集矢量化
由等式(3.1.1)我们知道,有无限多的G(tx,ty,s,口)的解来满足等式(3.1.1),而

tx、ty、还有s和0是未知的。因此仿射变换参数不能够确定,点集的对应关系也
无法得到。 参考文献[3]Chang等的快速点模式匹配算法中的思想,我们可以假设,如果点集 P中有两个点P。、P,(p.≠p,)和点集Q中的两个点q。、qb(q。≠qb)存在对应 关系,那么由式(3.1.1)可知,存在唯一的配准函数G(tx,ty,s,O)使得q。=G(p,)和qb 。G(p,)成立?因此我们有以下定理:


定理3.2-l:存在唯一的匹配。在点集P和点集Q中,存在两对匹配点对:(肛,吼)

和(p,,吼),如果,P。≠p,且q。≠qb,那么存在唯一的仿射变换参数G(tx,ty?s,
0),使得q.=G(p.)ga
q h2G(p,)。

四个仿射变换参数分别为:
2,

硕士论文

留像特征点匹配算法研究

s2l瓦I/|嚆I
t。2
xq。一x

口=一而一口而

p1(sxcosS)+y p.(sx sin0)

tr=yq.一Xp,(sx sin0)+Yp。(sxcos0)
定理3.2--1的证明如下:


假设qa=G(pi)和qb=G晒)因此由式(3?1)可得:

[;:]=(::]+。s。x×c。o;ns口8-。s×x。s。i。n口0,1L(yXnp,]

(;q-]=[::]+Ls。x×c。ions。8-。s×x。s。i。n口O,lL(Xy巩pj]
那么吼一吼=G(p,)一G(只),可以得到:


(;::二;:]=(:]+。S。x×C。OinS口O- 。S×x。¥。i。n疗O八/IXyp丹,一- yX,p。,]
jqaqb2【o J+8×【sin口cos0 PJ
——ro、(cosO—sin0、一
口丽刮枷P一,Pj

≥l瓦I=s×I面I

一圈0=0刚--一-O--^
以及

t。2xq.一Xp.(s×cosO)+yp.(s×sinO)
ty=yq。一x

P.(s×sinO)+yp.(s×cosO)



在定理3.2.1中,仿射变换参数G(tx,ty,S,口)由点集P和点

配点对来确定。只要能够知道l磊I,I面I还有 ‰和O。--,,
(3.2.5)和式(3.2.6)计算出来。 匹配。那么我们就得到下面一个有用的推理:



从等式(3.2.2)和(3.2.3)显而易见:在新的仿射变换G(0…0 S口)下,







碗}论文

图像特征卢匹配算法研究

这个最大值等于k-I,其中产{1,…,n},b={1,…,m},lj j.i,b≠a。如果P。和

吼不是匹配的,那么在鬲和磊之间就不存在有k-1对匹配向量对,因此p,和吼
的M。。(s,臼)的最大值就小于k一1。
利用以上理论,匹配问题由点集转化到了矢量集,待确定的参数由4个(tx,ty,s, 口)减少到了2个(s,口),Chang运用聚类算法有效的计算出s和口,降低了空间


维数从而减少计算量。本算法正是基于这种有效的方法进而得到两点间的几何不变量

一缩放量s 3.3寻找不变量
从上一节的理论推导,使得匹配问题由点集转化到了矢量集,这一节在此基础上

为了得到两点间的距离不变量,因此需要先计算出可靠的缩放量s,这就是我们要寻
找的不变量。 定义3.3.1:所谓两点间的距离不变量是指,在点集P={P。,P 2,…,P。}和点集Q_-


(ql,q

2,…,q。)中,假设p。付q。,p,Hqb是两对匹配点(i,j∈{1,2,…,n};

a’b∈{l,2,…,m};且i≠j,a≠b),缩放量为S,那么两点间的距离不变量指:

l瓦I=s—I石卜
该定义由上一节的推论3.2-1很容易理解。 3.3.1计算点对的最大支持度

首先介绍支持点对的概念:对于任意一个点对P,付q。,若在点集P和Q中

存在其他的点对,比如p,Hq。,在映射(so,eo)下使得l瓦I*s。×li万l且
8q--m。80+口矗(之所以约等于是允许两个图像间有轻微扭曲),则称点对Pj÷÷q。
是点对P。Hq。的~个支持点对。


点对的支持度是指:在匹配一个点对P。+÷q。时,为之构造了一个累加数组M。
(s,口)。那么M。(s,p)的最大值W。,和其相应的变换参数(s,口),若W。2c,则

说明除了P.÷÷q。,还有c对点支持P,付q。是一对匹配点对,同时也说明了在(s, 口)的变换下存在c+l对匹配点对。因此我们称Wh为点对P.‘÷q。的支持度。 累加数组M。(s,们的计算方法是:对于一个点对P,¨q。,点集P和Q中的其

硕士论文

图像特征|占匹配算泫研究

它所有可能的点对P,付q b,其中jE 11,2,…,n),be{1,2,…,m)且j≠i,b≠a,

计算向量万万和—q。—qb的长度l万万I和Iq-XI还有幅角巳万和巳鬲,从而得

到s=l万il/l瓦瓦l还有p=0£i一0。--.,并在累加数组M..(s,们中加以记录,
即M,。(s,日)=M。(S,臼)+h遍历点集P、Q中所有可能的支持点对后,找出


累加数组M。(S,目)中的最大值u,u表明在相同的变换函数G(s,口)下,点集P、

Q中除点对P,Hq。外,还有m个点对存在稳定的一一对应的关系。 若点对P。付q。的支持数小于一定数目,我们可以认为点对P,Hq。不可能是一
个匹配的点对;显然,不匹配的点对不能作为其他任意点对的支持点对。反之,若支 持数大于一定数目,我们认为点对P。Hq。可能是一个匹配的点对,但仍需其他的步
骤加以确定。

我们将在两个点集中计算匹配所有可能的点对P.什q。的支持度,计算点对支持
度算法(MPS)的过程描述如下:

◆点对支持度算法(MPS--Matchingpairs


support):

1)累加数组M.。(0)=o;

2)forj=1,'--,n,j*i,计算1万万l和p而; 3)forb=l,…,m,b,a,计算Ii磊I和O如m如;
4)Forj=l,-,-n J≠I,for
b=l,…,m,b≠a:

4.1)如果match_flag[j][b]的值等于1,继续,否则转到5);

4.2)计算(s,跳s=I瓦l/l瓦I,0=0州--。一口而
4.3)如果(s,一)在累加数组M。(s,们中已存在,则将累加数组M。。(s,口)
的值加I,否则将(S,0)记录到Mi,a(s,口)中并且把M,。(s,p)的值置为



5)搜索M。。(s,口)的最大值w.,=max(M.。(s,p)),并且把w。,对应得(s,0) 记为(s。。,0。。),算法结束。 在点对支持度算法中,match_flag矩阵,它是11行m列且其中元素的值
match

flag[i】【j】∈(0,1},i∈{1,2,--.'Il}J∈{l,2,…皿}如果match flag[i][j]=l则表示点

集P中的P。与点集Q中的q,可能是一个匹配点对。如果match_flag[il[j]=O则表示P.

预t论文

图像特征点匹配算法研究

与q.不匹配。由于我们匹配前并不知道点集P和点集Q的对应关系,因此将match_flag
矩阵初始化为全l矩阵。

由于点对支持度算法采用聚类算法且只考虑两个变换参数s和0,因此算法的时 间复杂度降低至O((m-1)(n-1)),算法不需要考虑tx和ty的值。由于累加数组是一个 两维的数组因此搜索其最大值的时间开销很小。所以支持度算法的时间复杂度可以忽
略2)3)、5)步的时间。


3.3.2确定缩放量
为了得到两点间的距离不变量,我们需要确定缩放量的可靠值。这不同与Chang

的确定缩放和旋转参数算法是只需要关心缩放量的值。因此本章在这一步的算法比 Chang的算法简化些而且在此步中减少了一个不必要且不好确定的阈值。下面给出详
细阐述。

如果P,Hqb是具有最大支持度的点对,那么它肯定是{W。Ii=l,…,n:a=l,o-o



m}中的一个最大值。换句话说,如果wm是{w。li=1,…,n:a=l,…,m}中的一个


最大值,那么点对P.Hq。是最有可能匹配的点对。同时从很多实验结果来看,可以
相信P,Hqb就是一对匹配点对,那么有其他wm对点支持P JHq h是匹配的。因此, 我们用确定缩放量算法来找到在点集P和点集Q的所有可能点对中具有最大支持度的
点对,并且得到可靠的缩放量s。 ◆确定缩放量算法伪代码描述如下:

1)将记录最大支持度的p一初始化为零,N=min(n,m): 2)match flag初始化为n行m列的全1矩阵,表示所有点对均有可能匹配:
3)Fori=l。…,n:fora=l,…,m

3.1)用3.3.1节的MPS算法计算P,付q。的最大支持度w和最大支持度对应
的缩放量s。;

3.2)如果w小于给定的t,值,令match flag[i][a]--0:


3.3)如果P。小于W,那么令(p。,s。一)=(w,s。),Pair-i=i,Pair_a—a; 3.4)如果p。大于等于(N—i),那么找到了最大支持度,循环结束。
4)点对Pair


Pair_a具有最大的匹配支持度p。,并且s。。=s。,算法结束。

由于点集P和点集Q的对应关系是一一对应得,因此最大匹配支持度p,。的值小 于等于min(n,m)。在步骤3)中,首先对任意可能的点对Pf付q。用MPS算法计算 其最大支持度,例如:当i=l时,对于点集Q中的每个点q。(a=l,…m),用MPS算
28





来计算其他点对的支持数。

在Chang的算法中不但需要找到最大匹配支持度对应得缩放量s还需要记录对应
护,同时在本算法中的DS算法的33)和3.4)步骤中多加了一步判断并引入了一个 难以确定的阂值匕。Chang的这一个判断是:

“如果p。大于等于一个给定的支持度气,那么找到最大匹配支持度,转到步
骤4)。” 我们现在来讨论这一判断的必要性。显然,Chang的算法想要通过这一判断,能 够在已找到足够大的支持度匕的情况下结束循环提高确定匹配参数算法的效率。但 是,我们客观的分析对于不同的图像由于形变,噪声和局部扭曲的程度以及匹配点对 的数目会也相同,而且这些因素在匹配前是未知的,因此足够大的支持度P.,很难确 定,那么Chang的算法在提高一定效率的同时丧失了算法的稳定性。在应用Chang 的算法时,需要根据匹配的不同的图像调整阂值咒。如果足够大的支持度设置不当,


将使得变换参数(s,口)的值不可靠,拿不可靠的变换参数(s,口)柬进行下一步

的确定匹配点对本身就引入了一些误差,那么这又影响了算法的准确性。因此,在
DS算法中考虑到需要得到可靠的变换参数(s),而不需要加入此判断保证搜索到的

是最大的支持受,因此其对应的缩放量也是可靠的;同时也不需要考虑闽值气的取
值。

硕}‘论文

图像特征点匹配算往研究

3.4最大匹配集的求解
上文已经将几何不变量s的可靠值求出,利用定义3.3.1可以得到两点间的距离

不变量:|.吼J=s×l-p,I,其中pf Hq。,P,付q b是两对匹配点(i,j∈{l,2,…,n}:
a,b∈{l,2,…'m},且i≠j,a≠b)。下面介绍根据距离不变量来求解最大匹配点对集。
这里参考了文献E13]的Euclid变换下的点模式匹配算法将其推广到仿射变换的不完

全匹配情形下的对匹配点对求解得问题,给出了匹配集、支持点对、支持标准集、还


有支持集矩阵等概念和它们的一些性质及其证明,最后由这些理论知识推导出最大匹 配点对集的求解算法。该算法的目的就是求解尽可能多的匹配点对。

3.4.1理论知识 首先针对仿射变换不完全匹配情形下最大匹配点对集求解算法中用到的一些概
念。

定义3.4.1.1仿射变换下最大匹配点对集就是对于给定的两个点集(点模式)

肚{p,,…,P。}和Q一{q.,…,q。},仿射变换下的最大匹配点对就是要在P和Q
中找到尽可能多的对应点对,使得它们在一定误差容限下一致满足同一个仿射变换G


(tx,ty,s,占)。

定义3.4.1-2匹配集:它是匹配点对集的简称,指给定的两个点集P={p。,…,

¨和蛐∥”叽油标准集w-(0:矗ir]是P和Q的一个匹瞧其中
(n,m),当有如下关系成立:IS×d:lb—d:Jbl≤E,V a,b=l,2,…r,其中

屹打‰II=l赢卜。--I%飞-I|=|而|,s=离鼍。占
是给定的允许误差。当标准集W中的每一行均不存在相同的元素时,称为无歧异匹 配集。


特别的,如果在点集P和O中均不存在点『丑J距离小于£的情况,则P和Q的匹 配集必是无歧异匹配集。我们要求的最大匹配集不存在一对多或者多对一的对应关
系,因此最大匹配集必须是无歧异匹配集。通常,通过预处理,可将每幅图像中彼此 靠的很近的点合并为一个点,因而,不失一般性,以下文中不严格区分匹配集和无歧 异匹配集。此外由定义3.4.1.1和定义3.4.1-2可知,本文定义的仿射变换下的求解最

硕}论文

图像特征点匹配算法研究

大匹配集后,则可以根据最小二乘法求出仿射变换参数G(tx,ty,s,0).



定义,.4.。.,支持点对:给定点对p。∈P和。,∈Q,记为(:],若存在点对p,∈P q,eQ,记为(:],若满足Isxd,:一d:I≤占,其中。和占如定义。.禾:给出, 则称点对(:]是点对(i,]的一个支持点对。
定义3.4.1-4支持标准集:
准集,记作:

点对l jj
tlJ2/:tj2

fi1
的所有支持点对的集合,组成它的支持标

wj=一t,jj

足义3.4.1-5杯准集的长度和有效长度:一个标准榘W的长厦定义为它Jj}r包管点

对数目,记作Length(w),而它的有效长度定义为:LENGTH(W)--rain(NI,N:),这里, N。,N:分别是W的第一行和第二行中不同元素的个数。


显然,LENGTH(W)≤Length(W),对于无歧异匹配集,其长度就是有效长度。 定义3.4.1—6支持标准矩阵:对于给定的点集P和Q,点集P和点集O的势群(P)
=n,群(Q)=m,那么称以支持标准集作元素构成的n行m列矩阵为支持标准矩

阵,记作:W。=(w,,)…。
不难证明,支持点对、支持杯准集和支持标准矩阵有如下有用的性质:

性质,A。.。对于点对(i,]的支持标准集w。:(i,]∈w。
证明:因为d“,,--d。。=o,所以由定义3.4.1—3可知,V占≥o’Is×d:一d引≤占



因此(:]是其自己本身的一个支持点对。根掘定义。.4.。一4可知[:]∈w。。 性质,.4.。.:如果点对(:]∈w巧,那么(:]∈w。。,反之亦然。 矾(刁 ∈wij营ls×d,P。d,。l-占
营Is×d:一d:I≤占

颂t论文

图像特征点匹配算法研究

营【j J

f i]



Wst?

性质。.4.。.,给定一个点对(:],它在支持标准矩阵中出现的次数等于它的支
持标准集wij的长度。


定理3.4.1.1标准集w;fIl…lr 1是一个匹配集,当且仅当 Ljl…Jr/
Nw,kJk




§8×?:jl—d:】ll≤占,Vl【'l=l,2,…’r(由定义3.4.2可知J





营I J J∈wo业,Vk----1,2,…’r(由定义3.4-3和3.“可知’


营Wk】k2W,Vk=l,2,…,r

营nU业_D W
k=l

3.4.2最大匹配集求解算法



图3.4.2.1点模式P

图3.4.2.2点模式Q

基于上一节的理论知识,下面介绍最大匹配集求解算法。为了便于描述算法首先 我们举一个简单的例子并且应用上一节的理论柬说明。图3.4.2.1,是包含三个点的点

模式P,三个点分别用序号l,2和3,任意两点『日J的欧氏距离由线段中『日J带下划线的
值表示;图3.4,2.2,是包含了四个点的点摸式,分别用序号l,2,3和4表示,同样
32

硕士论文

图像特征卢匹配算法研究



是(翁:=阿竺。==蕊做
持标准集为w。:={:;:}。
那么我们可以同理得到其它任意点对【J J的支持标准集,其中i=l,2,3;j=1,
2,3,4。因此,根据定义3.4.1.6,不难求出此例子的支持标准矩阵:

f31

是(:)的一个支持点对,即[;]∈w。:。依次类推,可验证,点对[:]、二支
fi1

嘭=


(㈡(:㈡ (;;)(:㈡ (:㈡(:42习



2 2 2 3 3

/● ,L


、l』3
、● ● ,

(三


/,.。 L




2/●●●L

1,,‘l



l、●J

怂=就撼l感点雾
那么支持标准集wj,的长度也为3。我们从图3.4.2.1和图3.4.2.2中可以看出,

wr:匕2,刁为点集P和Q的最大匹配集,并由支持标准矩阵wx可知,


wl:nw:3 nwj。≥w;,由此也验证了定理3.4.1一l。
本章算法的目的是要找到尽量多的匹配点对以及其对应得仿射变换参数。我们在

给出最大匹配集求解算法之前首先给出两个基本要点113】:
(a)给定点数分别为n和ITI的点集P和Q,设最终求得的最大匹配集为W;。显

然,LENGTH(w;)=r_<min(n,m)。首先仞始化r=min(n,in),若在推









从而得到”f



f1

2 、

2 3

31



l;

在步骤5)继续判断,由于LENGTH(W,户3=r,因此继续执行下一步6h 在步骤6)中,由于LENGTH(w。)=LENGTH(W,)=3=r,算法结束。wf就是
我们要得到的最大匹配集。

由此我们可以直观的看出,由于在这个简单例子中,最大匹配集的实际长度刚好 等于最初r的设定值,因而算法不需要循环就得到最终结果。因此当匹配中,两点集


P和Q的最大匹配集的实际长度越接近min(n,m),那么该算法的循环次数就越少,算 法效率越高。 得到匹配集后利用前面第二章介绍的最小二乘法来计算出仿射变换参数,由于我
们的算法找到最大匹配集,因此在尽量多的匹配点对计算参数可以提高变换参数的 准确性。

与Chang的匹配点对确定算法相比,本文的最大匹配集求解算法利用两点间距离 不变量自上而下的寻找尽量多的匹配点对,有严密的推理相计算量小且结果可信度 高。而Chang的匹配点对确定算法中对进行三次搜索可能匹配点对,并且根据已知不
可靠的(s,疗)(不可靠的原因上节已经分析)计算可能匹配点对,又将可能匹配点


对计算仿射变换参数进而来第二次和第三次搜索可能匹配点对;在此过程中引入了三 个阈值(as,a占,ad),如果这些阈值设置不当则将导致丢失匹配点对和多对一的误匹
配的情况发生,同时降低了算法的稳定性和准确性。加上Chang的确定(s,口)算

法中引入的阂值pw,那么整个算法中共有四个闽值,算法的执行效果好坏很大程度 上依赖阌值取的合适与否,而且对于不同的点模式匹配问题需要不断调整这四个与算 法执行结果密切相关的阈值是一件复杂繁琐而不可避免的问题。

3.5算法的整体框架
通过上面对基于寻找不变量的特征点匹配中用到的算法进行详细的介绍和分 析,接下来给出基于寻找不变量的特征点匹配实现的整体框架: 1)初始化:模板点集P为nx2矩阵,存锗i点的位置信息(i_l,…,n) 同理,目标点集Q为rex2矩阵,存储a点的位冒信息(a=l,…,111);


r=min(n,mh

tw=(n-I)/4;matchfla州1)。。;p~20;Wf=o:

2)计算P中任意两点P,P,的长度和幅角和Q中任意两点q,qb的长度和幅角; 3)运用3.3.2节的确定缩放量算法,对于P和Q中任意两点p.Hq,(滓1,…, n:a=l,…,m)用3.3.1节介绍的点对支持度算法(MPS)计算其最大支
持度support,以及最大支持度对应得(s,口);

硕士论文

图像特征点匹配算垃研究

4)搜索P和Q中任意两点P。付q,的最大支持度的最大值p。---max(support) 并记录最大值p。对应得缩放量Scale=p。(s); 5)基于缩放量Scale,用3.4.2节给出的最大匹配集求解算法得到W,; 6)由w,中匹配的点对,用最小二乘法确定最终的仿射变换参数Gr(tx,ty,s,0); 7)返回Wf和(打,算法结束。 从上面的算法框架可以看出该算法采用将两个点集中的点矢量化找到两点间距


离不变量从而利用严密的推理得到最多的匹配点对和最优的仿射变换参数。

3.6实验
为了验证本算法的有效性,在这一部分,采用文献【4,5】所描述的实验方法,并 用仿真的方法在256x256范围内随机产生多组点集并进行实验。并且在仿射变换情 形下的本章算法与Chang等的快速点模式匹配算法进行对比测试。最后将本章算法用 于真实图像实验。 利用随机产生的点集对算法进行抗形变、抗噪声和出格点性能的三项测试:每项 实验中,首先给出仿真实验的结果,限于篇幅仅给出一组仿真点集的实验结果,从匹 配点对和仿射变换参数值以及执行时间三个方面来比较两个算法:其次在每项实验中 分别选择5组随机点集进行测试,用平均误差来比较两个算法。平均误差定义为应用
算法得到的变形模板与目标点集之间的均方距离。 (一)抗形变实验: (1)这是在无噪声和出格点的情况下,对模板点集施加一定程度的形变:缩放 量scale=1.1,旋转角度0=15,x轴平移量tx=12,y轴平移量ty=12; 测试数据与结果如下:



I茔|3.6.1点模式P

硕士论文

图像峙征占匹配算法研究



图3.6.1显示点模式P中的点用“?”表示;图3.6.2显示点模式Q中的点用“x”

表示。P和Q各有16个点。应用本章算法和Chang等的算法的结果如下:

\参数
本文算法

表3.6.1应用本章算法和Chang等的算法的结果
tX ty

scale



time

Error

剿\\
Chang等算法

(像素)
12.0830

(像素)
11.0714
11.2790

(度)
1,0915
1.0912 15 1392

(秒)
0.3319
0.6724

(平均误差)
0.415l 0.4437

12.9957

15 3482

表3.6.2应田本章算法和Chang等的算法得到的匹配苣对 本章算法得到的匹配点对Wf:
P 1 3 2 l 3 2 4 6 5 7

(16对)
6 5 7 4 8 8 9 9 10 1l 11 10 12 12 13 15 14 13 15 16 16 14



Chan口等算法得到的匹配苣对raatchflage:(16对)


。。。。‘。。。一 Q l



1 3

2 1

3 2

4 6

5 7

6 5

7 4

8 9

9 9

10 11

ll 10

12 12

13 15

14 13

15 16

16 14

说明:两表中数据均是将两个算法执行100次得到的平均值。
从上面两个对比数据表中可以看出在仅有形变的情况下本章算法的确得到了最

大匹配点对集;而Chang的算法产生了多对一(表3.6.2浅灰色格)误匹配的情况。 由于本章算法得到最多匹配点对确保计算仿射变换参数的正确宣比Chang的更高。同 时,当最大匹配点对集的长度接近点集P和Q中点数最小值时,本章算法的时间效 率毫不逊色于Chang等的算法。
(2)选择5组随机点集进行测试,用平均误差来比较两个算法。所得的结果如 图3.6.3所示。







硕士论文

图像特征点匹配算法研究







ll






l《
;5D
§≤ J0




7 3

§;




5 2 J










;3 嘲
i!
}佯


'《



图3.6.4点模式P

纛。%战忿;辫獭一鼎i。蛳。'∞嘲甚㈣150‰一《,m蕊磊。如勰灞




}!
翔0

w≈a目《∞%■‰wⅪPgⅫ∞%%m@‰㈣%㈣∞㈣∞■g《∞m㈣《∞㈣%≈gⅧ目㈣黼镕#戮l
● ● ●

l,




jO






i‘



声 ;;

● ●

2 。





} 三
》:
;。

£玑~;~辩。。。

礤~。:

图3.6.5点模式Q

1∞~强豫。一。:。葛鼠

图3.6.4显示点模式P中的点用“?”表示;图3.6.5显示点模式Q中的点用“X”

表示。P和Q各有10个点。应用本章算法和Chang等的算法的结果如下:
表3.6.3廊辟J本章算法和Chang等的算法得到的匹配由对 本章算法得到的匹配点对W,: 。10对)
4 3 5 4 6 7 7 8 8 6 9 9 10 lO



剖Ql

2 2

3 5

Chang等算法的剑的匹勇己点对matchflage:

(4对)
8 6 lO 10

刊Q







3}1

从上面匹配点对表中可以看出在形变一定的情况下,在目标点集中加入【0,5】的 随机噪声,本章算法的最大匹配点对集结果完全正确且得到最多的匹配点对;而
39

硕士论文

图像特征点匹配算法研究

CHENG的算法产生了丢失(表3.6.3浅灰色格)匹配点对的情况。 (2)选择5组随机点集进行测试,用平均误差来比较两个算法。所得的结果如
图3.6.6所示:



平均误差

嵘声等级

图3.6.6平均误差比较.实线表示本章算法,虚线表示Chang的算法,在不同噪声程度下的平
均误差。

图3.6.6中,横坐标为噪声程度,在无刚性形变和出格点的情况下,对目标点集


施加【O,仃】的随机噪声,口就是横坐标上的整数值。纵坐标为平均误差。从图中可 以看出来,本章算法对噪声抗噪能力要强于Chang的算法,在找到最大匹配点对集的 情况下得到更精确的配准参数,从而使得配准误差均小于Chang的算法。 (三)抗出格点实验
(1)这是在无非刚性形变即(tx,ty,scale,口)=(O,0,1,O)和噪声的情况下,在目标 点集中分尉去掉6个点,然后再加入6个虚假点,然后再分剐用两个算法进行匹配。

测试数据与结果如下: 图3.6.7显示点模式P中的点用“?”表示;图3.6.8显示点模式Q中的点用“X”
表示。P和Q各有16个点。
表3.6.4府}fj本章算法和Chang等的算法的结果

\\参群


tx

ty

scale



time

Error

算法\\
本文算法 Chang等算法

(像素)
O 一0.2443

(像素)
0 0.122l l 1

(度)
0 -0.6276

(秒)
0.662 0.572

(平均误羊)


0.9277

40







硕士论文

图像特征占匹配算法研究

出格点个数 图3.6.9平均误差比较。实线表示本章算法,虚线表示Chang的算法在无形变无噪声不同出 格点个数下的平均误差。

该五组随机点集均有16个点,横坐标表示在目标点集中删去真实点和添加虚假 点的个数。纵坐标如前面的实验表示平均误差。从图中我们可以看出,本章算法对出 格点的处理相当出色,在75%的出格点比率的情况下仍然能够正确的匹配点对并且 得到零误差的仿射变换参数。 (四)真实图像实验

图3.6.10操场图像S

图3.6.1l操场J墨l像O

硕士论文

图像特征点匹配算法研究

表3.6 6应用本章算法和Chang等的算法得到的匹配点对 本章算法得到的匹配点对W,:
P l 1 13 24 2 3 14 22 3 5 15 20 4 7 16 18

(17对)
5 9 17 16 (14对) 6 11 7 13 8 15 9 17 11 21 6 11 7 13 8 15 9 17 lO 19 ll 21 12 23







Chang等算法的到的匹配点是 。matchflage:
P 2 3 13 24 14 22 3 5 15 20 4 7 16 18 5 9 17 16






最后,我们还进行了多组真实图像的实验,限于篇幅这里仅举其中一例。图3.6.10 是用摄像机拍摄的某操场局部场景真实图像S,图3.6。11是将摄像机绕光轴旋转某个
角度后垂直光轴在同一平面平移一定量最后通过调焦距放大图像拍摄同一场景的真

实图像G。用Photoshop图像处理软件,在图像S和G中分别人工挑选22个和24个


特征点(主要是角点)构成模板点集P和目标点集Q。图中各点的序号是随意安排的, 为的是P、Q中的对应点不是序号相同的点。比较两图不难看出,点集P和Q有17

对匹配点对,P中的点18、19、20、2l、22在Q中无对应点,而Q中的点2、4、 6、8、10、12、14在P中无对应点。取允许误差占为5运行本章算法,得到的W,完 全正确如表3.6.6所示找到了全部17对点。而应用Chang的算法丢失了三对点如表
3.6.7所示。

3.7本章小结
本章对快速点模式匹配算法进行改进,不采用该算法中的匹配点对确定算法,但 是利用其寻找匹配点对支持度的算法来计算可靠的几何不变量S,然后自上而下的根 据两点间距离不变量的几何推理来求解出最大匹配点对集和最优仿射变换参数。本算
法针对仿射变换下解决特征点匹配问题,对于其它非刚性空间映射方式只要能在适当


条件下得到两点『日J的距离不变量也同样有效。从大量实验结果表明本章的基于寻找不 变量的特征点匹配算法在准确性和稳定性方面部好于快速点模式匹配算法,并且推理
严密,计算量小,当匹配点对数接近点集P和Q中点数较小值时(实际应用中往往

如此),本章算法的时间效率毫不逊色于Chang等的快速点匹配算法,是一种理想的
特征点匹配算法。

硕士论文

图像特征点匹配算法研究

4基于确定性退火的点匹配算法

4.1引言
点模式匹配是可以根据是否存在一一对应关系分为完全匹配和不完全匹配两种


情形。在很多实际应用中,由于存在图像噪声及视场限制还有不同时间和不同传感器 获取的图像等因素,待匹配的两幅图像中不可避免出现虚假点、丢失点以及非刚性形 变。因此不完全匹配的点模式匹配相对来说更加困难也更有意义。这种特有的研究难 度在本质上属于NP类【2l】的复杂的组合优化问题【2“。 对于点模式匹配这种有约束条件的最优化问题,近些年来出现了运用最优化方法 来解决的新算法,如文献【4-9,22-24】。来自予统计物理学的确定性退火算法是其中 比较成功的一种。它的基本思想就是模拟退火过程,将求解优化问题的最优点转化为 求一系列随温度变化的物理系统得自由能函数的极小。它能够使算法避开局部极小而 得到全局极小,具有广阔的应用前景。具代表性的有文献[5】和文献[9】分别在薄板样 条函数和仿射变换函数的空『BJ映射下构造目标函数用确定性退火算法联合求解点集



之问的匹配矩阵和映射参数。

本章算法是对文献[5、9】基于确定性退火的点匹配算法的进一步改进,该方法利 用确定性退火技术将求解匹配矩阵的组合优化问题转化为连续优化问题。通过退火温 度来控制匹配矩阵的模糊度,不仅增强了算法的鲁捧性,而且减少了陷入局部极值的 可能性。算法中引入松弛变量,可以处理出格点。本章算法的主要改进点是用相似性
度量值来约束匹配矩阵,加快了匹配矩阵收敛的速度减少计算量,在退火率较大时也 能得到比较好的解。给出了适合确定性退火算法求解的新的能量函数形式。 把特征点匹配问题置于确定性退火框架内求解需要一个编码方案(一种表示点模

式的方法)、一个合适的目杯函数、为生成新的指派的优化方法、冷却流程和收敛准
则。一旦确定了这些就可以将点匹配问题嵌入第二章讨论的确定性退火算法框架加以 求解。

?4.2编码方案
编码方案就是指表示点模式(具有一定模式的点集)的方法,确定点集之侧指 派(即点与点的对应关系)的数据结构。为了找到最佳的指派,描述点集闯的指派的
数据结构在以下方面构成最理想的裹示120l:
?

它是在问题定义域中的一个简单和直接的标记与指派,并且是模式点的一种







硕十论文

图像特征点匹配算法研究

为了更直观的理解,满足行列约束的匹配矩阵的一个例子如表4.2.1:
表4.2.1匹配矩阵

Hij
1 2

1 l O O O O

2 O O O O l

3 O 1 O O 0



5 O O O O l

6 O 0 O l

O O l O 0




4 5

说明:模扳点集P,个数为4:目标点集Q。个数为5

表4.2.1中,第五行和第六列是处理出格点的,那么可以从匹配矩阵H,x6中看出 匹配的点对有:p。,q,),Q:,q,)'(p,,q.);而第五行和第六列中值为一的项说明出格点 有:p4,q2,q5,这三个点分别在另外一个点集中没有对应得点。 现在匹配矩阵是一个离散的矩阵,每一个元素的值hij∈{O,1}。但是在匹配矩阵 的求解过程中往往需要其为连续值,因此我们将匹配矩阵连续化:hij∈【0,l】以便于
运算。

?

4.3算法研究与设计
4.3.1点匹配问题的目标函数 目标函数或代价函数应能反映不适当指派所造成的误差,并对不完全的匹配给以 惩罚。一个好的指派(匹配)应产生小的匹配误差,反之亦然,小的匹配误差对应的 匹配就更准确。从统计物理学的角受来看,一个解的代价类似于物质的一种状态能量。 点匹配问题可以表述为:在一个被观测的点模式(通常称为目标点集)中寻找这 样一个子集,使其通过变换在某种意义上与一个模型点模式(模扳点集)的子集相匹
配。~般情况点分白在n维空|'日J,且根据问题的几何和环境约束条件对变换加以规定。 由于图像本来就是二维的,因此这晕只考患二维(2D)点模式,但本章算法不局限 于二维点模式。



我们假设摸扳点集为P=-{p.1i_l,…,m},目标点集为Q={q,lj=l,…,n},Ill、
n分别是点集中的点数,按照4.2节定义满足行列约束(4.2.1)的匹配矩阵H=(h。) 。。。。目标函数的一般形式定义为:

E(H,妒):芝窆九llqj-|}f,(只)8+g(沙)+f(日)+T∑m+l∑n*1%(1。g%一1)
J=l,=1 I=I J=l







硕t论文

图像特征喜匹配算{击研究

以上两个过程是求解匹配矩阵再将其嵌入到确定性退火算法的框架中,如图 4.3.1.2所示,其中T。、H。、%分别是初始温度,匹配矩阵的初始值还有空间映射矩
阵的初始值,Tfmal是终止温度,a是退火率:



图4.3.112基于确定性退火的点匹配算法框架

Steven.Gold的算法是在仿射变换下的匹配而Haili Chui的空间映射是薄板样条。 由于他们算法中引入阻尼项为x(109x—1)的形式。而必须由迭代逼近的方法,而这种

方法有可能会降低算法本身的精确度,实际上任何满足一定条件的凸函数都可以作为


表示熵的项陋1。因此本章算法参考文献【8、23]的思想,将阻尼项变为x(x.1),这样目
标函数变为严格凸函数,所以可以不用Sinkhom交替归一法求解匹配矩阵,采用

Karush.Kuhn-Tucker必要性条件得到。这样减少了算法的计算量,提高了算法的精度。 此外,在图像配准中可以将局部小区域内近似的认为是刚性形变,因此可以对模 板点集P和目杯点集Q中任意一对点对的组合估计一个相似性度量值A1.,这个相似 性度量值表示两个点可能匹配的估量,相似性度量值越大两点匹配的可能性就越大反 之相似性度量值越小两点匹配的可能性就越小。将其做为匹配矩阵的一个反馈权,从 而使确定性退火算法的收敛速度加快,所以在目标函数中加入一项:

L(H州善善”xp[(A u-1)/T】


(4-3.1.2)

目标函数是H的正定二次式,因为二次函数的正定性由二次项决定和一次项无

关,在式(4.3.1.1)中加入式(4.3.1.2)后不影响目标函数的正定性。因此匹配矩阵
H仍可以采用K.K—T条件的求解。

综上所述,本算法的新的目杯函数为:

E(日,妒)=∑∑h。09,一y(p,)lI+g(P)+f(H)一
l-l,;l

善∑∑h,jex P[(A lJ.1)/T]+T∑∑^,,(^'】_1)

硕士论丈

图像特征占匹配算洼研究

(4.3.1.3)

由于本章v的空间映射方式为仿射变换函数和薄板样条函数两种形式,所以下面
分别给出在这两种映射下的目标函数。

4.3.2仿射变换函数

仿射变换矩阵为:

Affine=l—J

I 8COS口踯in01 sin0 COS0



戗与ty分别是横纵座标的平移量。







I其中s是缩放量,0为旋转量,

因此对应点的坐标变换为:【P,,P,,1】×彳朋,ze=[q;,q,】
式中(p;p,)是模板点集P中的坐标,(q,,q,)是目标点集Q中的坐标。所以仿 射变换下的目标函数为:

E(H,y)=∑∑氏IIq,一只4彬疗Pi|2十口×trace[(Affi,le一眨历"eo)7(AffinP一吃历甩%)】
f;I』=I m
n m n —

m+l

n+1

+p(∑h(。),+∑hi(n+1))一善∑∑h,jexp[(AIJ-1)/T]+T∑∑hy(^。一1)
J21 l;£ 1。l jal 1‘1 J2l

(4.3.2.1)

其中,trance表示求方阵的迹,右上标T表示矩阵的转置。第一项表示对匹配程 度的衡量;第二项是限制仿射变换的取值,口为参数,afiine.是仿射矩阵的初始值:
第三项是限制出格点的个数,妒越大对该点是否为出恪点的限制越宽松,反之p越小

对是否为出格点的限制就越严格。第四项为匹配矩阵的惩罚项,f为参数;最后一项 是带有温变T的阻尼项,它使得目标函数凸化能够保证收敛的正确陛。 由式(3.4.2.1)对Affine求导,就可以解出仿射变换矩阵:

钐聆P=(a13x3+prdiag(H…U∥(a
4.3.3薄板样条函数



affineo+prH.x.Q)

(4驰2)

其中,diag是向量的对角阵,I。是全1列向量,I。,是单位阵。

薄扳样条(TPS)能够将空间变换分解为一个全局仿射变换和一个局部非仿射变 换垆1。我们仍然只讨论二维空间(2D)的情况Booksteint矧首先将TPS应用于标志点 的匹配,它是一个非常有用的形状分析工具。薄扳洋条函数厂应用到匹配的能量函数
里是‘51:

硕士论文

匿像特征占匹配算法研究

‰c门=割‘叫心川2+A』』[[警]2+:(岳]2+(争]2蚴?。43。.。,
其中,Xa和Vi分别是模皈点集和目标点集中的点。通过点集V和X之间的匹 配最小化第一项匹配误差,但是非刚性映射存在无限r解能使第一项最小化,因此就 需要第二项平滑约束,用于调整映射,A控制扭曲程度。只有当^接近0时,就获得 了最精确的匹配。 对于给定的五,式(4.3.3.I)有唯一的极小值厂珊:

丘-n=V×d+①(V)洲

(4n2)

其中,d是(D+I)xD仿射变换矩阵,W是kxD扭曲系数矩阵,在这里D=2。

田(v)是薄板样条的核,它是lxk的行向量,对于Vv∈矿,o(v)=lly一匕旷10刨v—心0。
将式(4.3.3.2)代入到能量函数中,我们可以得到:

Eres(d,w)=∑IIx。一vad一中。wll2+2trace(w70w)
其中,o。是。也)薄扳样条的核。
根据式(4.3.3.3),我们薄扳样条下的目标函数就变为:

(4n3)

E(H—B

60)-XXh删IIq-p。曰一由:∞n口。trace[(B-Bo)7(B-Bo)]

+口2trace(c07巾∞)+妒(∑k+lJ+∑‰+1)一孝∑∑^vexPE(Aq一1)/T】
+T∑∑%(%-1) “’。1
(4.3.3.4)

其中,B为3×2的仿射变换矩阵,B。是仿射变换矩阵的初始值。中,是pi对应得
核即为孩矩阵的第i行,CO足扭曲系数矩阵∞中第i行向量。第三项是用于限制薄

板样条映射扭曲系数的取值范围。
将E(H,杪)分别对仿射变换系数B和扭曲系数彩求编导等于零,解得:

l B 1.1 q‘。3+∥。疣昭(瓦。。厶。。)P
l∞J l
①7dz昭(日二L1)P

P幽昭(E。。厶。。)中

P只。。Q+q局l
①。,k。O

at*+cDraiag(H。。L,1)①j l



(4.3.3.5)

50

■■■●’’一


硕}论文 巨像崎秆点匹配算痉酽究

4.3.4算法流程描述 将仿射变换下的目标函数式(4.3.2.1)和薄扳样条下的目标函数式(4.3.3.4)嵌 入到确定性退火算法中,则本章的算法流程描述如下: (1)初始化:T=T o,H=Ho,Affine=affineo; (2)计算匹配矩阵H中h。的相似度量值A。(净l,…m;j=l,…,n); (3)在仿射变换的情况下:由(5)式更新仿射变换矩阵; 在薄扳样条的情况下:由(10)式更新薄板样条参数;
(4)用K-K-T条件更新匹配矩阵H;

(5)若H收敛或者迭代次数大于iterl,执行(6);否则,转到(3);

(6)降低温度T-roT,,p-8÷;口=o.06xT(仿射变换);q—o.IT,“2可
(薄板样条)。若T≤T“,算法结束;否则,转到(3)。 从上述算法流程,步骤(3)到(6)是确定性退火算法过程。初始温度T o=√;磊,

终止温度T耐=o.02,退火率%=o.93,匹配矩阵初始化为H。2bi雾蒜j…。舯1),
f1 01
仿射变换矩阵初始值affine。=l
0 1

l,迭代次数上限iterl=5,匹配矩阵H的约束项

10 0j
中参数毒取经验值15。步骤(2)相似度量值的计算和步骤(4)匹配矩阵H的求解
将在下两节中介绍。

4.4相似性度量值
在巨像配准中可以将局部区域内近似的服从是刚睦形变,从这一思想出发,本章 算法中对摸扳点集P和目标点集Q中任意一对组合对应一个相似性度量值A¨,这个 相似性吏量直表示两个点可能匹配的估量。为使目标函数的收敛速变更快,用相似性 度量值做为指派h。的反馈权,在目标函数中加入一项对匹配矩阵的约束项:

L(H)=善∑∑^。expf(A 0-1)/T】
I。1 J=l

相似睦度量值得定义:假设将模扳点集中点P。与目标点集中的q。对齐后,其各 自周围的最近的n个点{p。1,…,P。。)和{qkI,…,qh}分别于p。和q。建立的向

颂士论文

图像特征点匹配算法研究

量:{瓦丙,…,瓦i),{瓦忑,…,瓦磊},然后计算两个向量集中两两向量
间的夹角,用聚类算法对相同央角计数,取其中所有夹角对应计数中的最大值N。。

那么P。与q¨的相似性度量值就是A。Ⅲ=N一/n。
对齐的p∞和q∞



Pa2

图4.4.1匹配情形,圆圈表示P中的点,十字表示Q中的点

不难理解,如果P。与q。。是一对匹配点对,相似性度量值就越大,反之,它们不 是一对匹配点对则气相似性度量值就很小。 为了近一步直观理解相似性度量值,我们举个简单得例子来说明如图4.4.1。图

中,我们假定(P。,q”)是一对匹配点对,点集P中,P.0的最近的n(n宅)个点

为{pa。,Pa2},它们对应得向量是:{石瓦,瓦元},Q中与p柚对齐的点q。的最


近的两个点为{qkl,qlc2),他们对应得向量是:{qkoqk,,q。q。}:那么由P向量集

中的每个向量对Q向量集中的每个向量求他们的夹角,结果是:

峙——=a目L——=b
P曲^lqkoq¨
p曲pIIqkoqiz

岔一———=c P曲p啦qkDqu

8一——=a
P曲Pazq¨qu

由聚类算法可得:Nh=2,N8呻=l,Nm=1;因此N~-2,fla此p柏与q¨的

相似性度量值就是A。=N。。/n=2/2=1?
我们可以看出,相似性度量值越大两点匹配的可能性就越大。匹配矩阵对应相似
性度量矩阵,用相似性度量值束约束点匹配矩阵,加快搜索速度使匹配矩阵收敛更快。 ◆相似性度量值计算的伪代码为: 初始化K,N(p)=叮,A=O;


如ri=l,…,m

forj=l,…,n
Do:

搜索与P.最接近的K个点,并计算P.与K个点对应向量的幅角; 搜索与q.最接近的K个点,并计算q。与K个点对应向量的幅角:

52

硕}论文

图像特征点匹配算法研究

口=9试一护丽;l_1,…,K,忙l,…,K;
N(0)=N(p)+1:

找出N(0)中的最大值N一;
计算(P.q,)对应得相似性度量值:Au=N。。/K
End ● End

4.5匹配矩阵H的求解
本章算法求解H参考文献[2310P由K-K-T条件求解匹配矩阵的方法。它是采用一 种类似于起作用集的方法Ⅲ1的寻优算法,针对严格凸规划问题。其寻优策略是无约 束条件限制下求解匹配矩阵H,接着判断约束是否满足,如果不满足则将约束加入起
作用集中再求解匹配矩阵H,然后再判断约束是否都满足,直到匹配笳阵的值全部都

满足约束条件算法结束。


求解匹配矩阵,略去目标函数(4.3.2.1)和(4.3.3.4)中没有H的项,则求解H 的目标函数变为:

E(日)=∑∑h,j、l,。一善∑∑hvexp[(AⅡ-1)/T]+Ty.∑^。(气一1)
l=I J=l I。I J=l 12l J=l

‘IJ)州m+l。n+l’

tlJ净(m+1,n+”

(4.5.1)

为了最小化目标函数同时满足约束(4.2.1),我们使用Lagrange乘子,则目标函
数成为:
卅+J n+I





m十I

n+I

E(日)=∑∑h,j甲。-4∑∑hoexp[(A,j-1)/T]+Ty'∑h,j(^。一1) ”㈠“
。盖,舄“。+ll


”:。嚣。“。+l,



,n+l



,rl十l



Ill+l

n+l

一∑五、I∑h。-l I一∑∥,l∑h。一l I一∑∑Yoh。
i-I



J=l



尸I

\J=l



a=l

I=1



(4.5.2)

其中是五,“、^是Lagrange乘子,用来将约束(4.2.1)中的三个条件加入到
目标函数中。其中甲。是:

硕十论文

图像峙征占匹配算庄研究

||lq,一p,Affine[]2

;i=l,…,nl,j=l,…,n :i=1,…,m,J21,…,n

(仿射变换)
(薄扳样条)

甲。=舢∥一p培一∞。∞112



;i=m+l,j=1,…,n或i=1,…,m,j=n+1
(4.5.3)



由E(H)对H求偏导数我们得到:

。l%+T(2h。一1)一Cexp[(Aq。1)/T]一五一,uj一‰;i=l,…,nl,j=l,…,n



Z凇:簿Z
心≥0

:≥描j Z

考虑到目标函数和约束的问题,我们令:

I,={(i'j)Ii=l,…,m+l,j21,…,n+1且 (i,j)≠(m+1,n+1)1,从而我们给出
(i,j)∈I。符合的Karush—Kuhn—Tucker条件㈣:
(4.5.5) (4.5.6)

堕:0
I删

巧吃=0
结合式(4.5.4)和式(4.5.6)式可得:

(4.5.7)

丸t+“|+y,+Cexp[(A。一1)/T]+T-y。
2丁

;i=1,…,m

j=l,…,n
(4.5.8)



∥,+y”+T—yv
v=

2r A,+yv+T一缈q 2r

;i=m+1

j=1,…’n

i=l,…,m

j=n+l

接下来我们定义两个集合D和历:D={(i,j)I%>o,(iJ)∈I。);石={(i,J)l

h:j=0,

(ij)∈I,}。由式(4.5.5)和式(4.5.7)式我们可以知道,当(i,j)∈D时,九=0,当 (i,j)∈D时,鱼,--0且7,j≥0。我们规定:

K:』1


“,j)∈D
,否则

10

由于有些吃的值可能为零,因此我们将约束(4.2.1)中的m行约束写和n列约
束又表示为:
H+1

∑~%=l,i=l,…'In
J=l



川∑Ⅲ

~%





,j—l,…,n

将式(4.5.8)代入上式可得:

硕十论文

图像晦征占匹配算往研究

¨∑一 丝玎

。∑一

q~: 一一『

¨∑川 等

鱼!!翌!坠二!!坚!. 。∑一
2r

¨∑一




i=1,…,m (4.5.9)

善丛+薯业+岁盟2T2T




2T

2T+喜 智

2r

豁警=t
j=l,…,Ix (4.5.10)

因为%%总等于0,所以将式(4.5.9)和(4.5.10)中的第三项去掉,那么这m+n

个线洼方程组得解比较容易求解,我们把其写为矩阵形式:

㈠l
A=(^,…,五。)7;∥=(∥。,…,∥。)7






~y 1● ● ● J -. 。. . 。L 兄∥1 1● ● ● j

(4.5.11)

K寺zag阻缸,…,纠
上=扣g隆蕾∥…拳t=l。]
R=寺k],i=””,m
j=l,…,


x=壤“‰)奋细”1)/m ,豁(M.小蔷n喵喇厶剖析J
,=I ,=l ’1Ⅲ+1 m m?1 m I‘

y2去I善%(r一‰)+萎K,善exp[(41-1)仃卜‘,善‰(z’一‰)+善%亭eXp[(丸一1)玎】j


从式(4.5.9)和(4.5.10)的(m+11)个线性方程组求解A和芦,由(4.5.11)式 我们可以得:
K2+尺∥+X=1 Rr兄+£“+Y=l
?

(4.5.12) (4.5.13)
55

硕’论文

图傍峙玎占匹配笋往酽究

由式(4.5.12)我们可得:

旯=K’1(1一X—R∥).
故而将式(4.5.14)代入到(4.5.13)式中,可得:

(4.5.14)

∥=P。1[1一】,一R7K。11-R7K。1X]
其中,P=I工一R7置’1R l。

(4.5.15)

一旦脚∥算得,我们可以由式(4.5.8)来更新鱼,的值。
◆匹配矩阵H的求解算法为:

初始化:由式(4.53)式初始化∥2(gr,1)(。+啦㈣1)
Do:

由初始化集合D和历,D={(i,j)I玩>o,(i,j)eI,};西={(i,j)I 锄)∈I。};
由(4.5.14)和(4.5.15)计算A和Ⅳ;

hy≤O,

若%6D,令%=o,由(4.5.8)计算%;
若%∈西,则%=0:
Until:Vi,,

^,≥0

4.6实验
为了验证本章算法的有效性,与前一章实验类似对算法抗形变抗噪声和抗出格点 三方面进行测试,然后参考文献[5、241中的实验方法,将算法用于手写汉字匹配并 与文献【5]和[9】比较,文献[5】的算法是在仿射变换下基于确定性退火的点匹配算法,
文献[9]的算法是在薄板样条下基于确定性退火的点匹配算法。最后进行对退火率敏 感性实验。

(一)抗形变,抗噪声,抗出格点三项实验:
对在256x256范围内随机产生的多组数据进行实验,每项实验中分别选择5组

随机点集进行测试,用平均误差来比较两个算法。平均误差定义为应用算法得到的变 形模皈与目标点集之间的均方距离,与3.6节的平均误差含义相同。


在抗形变测试中,没有噪声和出洛点的情况下同样我们将形变程度分为六级,每

级的形变指数分别为:0、0.2、0.4、0.6、0.8、l;形变参数的变化范围分别是:钦,tye[0, 25],p∈【0,15】,scalee[0,1.2]:每一级的形变参数就是各参数变化范围的最大值 乘以形变指数。在抗噪声的测试中无形变和出格点的情况下,对目标点集施加[0,盯】 的随机噪声,盯就是横坐标上的整数值。在抗出倍点的实验中,模板点集和目标点集 均有16个点,在无形变和噪声的情况下将两点集中加入虚假点和去掉真实点仿真出
S6

硕上论文

图像特征点匹配算法研究

格点,横坐标的整数值就是出格点个数。将本章算法和文献[9】得算法分别应用于每
项实验比较它们的平均误差,如图4.6.1。



形变手军度



平均误筹

山格点数

图4.6.1本章算法(直线表示)和文献f9】的算法(虚线)在二项实验中平均误筹的比较

硕士论文

图像特征点匹配算法研究

从图4.6.1的三张图中我们可以看出,本章算法在稳定性和准确性方面都好于文 献[9]Steven等利用软分配的确定性退火算法。在相同的退火率条件下,由于相似性 度量值对匹配矩阵的约束使得求解匹配矩阵H时往往只需要迭代较少的次数,尤其 是当T较大时,只需要迭代一次,同时引入x(x.1)作为阻尼项用KKT条件求解匹 配矩阵提高了算法精度,本章算法以较少的计算量得到更理想的结果。然而,Steven 等的算法稳定性不够好,因为软分配是迭代逼近的方法,有可能降低算法的精度。


(二)手写汉字匹配

接下来将算法用于手写汉字匹配,“福”字是点匹配算法实验中常采用的实验对 象,因为这个来自我国的字符它的模式已经相当复杂口1。本算法对“福”字的匹配在 仿射变换的情况下与文献[9】的算法比较,在薄板样条的情形下与文献【5】的算法比较。 结果图得右下角为平均误差,平均误差定义为应用算法得到的变形模板与目标点集之 间的均方距离。如图4.6.2和4.6.3:



(1)模板点集P

(2)目标点集Q



(3)未匹配前

(4)仿射变换F本文算法结果

硕士论文

图像特征点匹配算法研究



(5)仿射变换下文献[9】算法结果

(6)薄板样条下本文算法结果



(7)薄板样条下文献【5】的算法结果 图4.6.2“福”字符匹配的结果比较

在图4.6.2中,模板点集图(1)和目标点集图(2)中的“福”字均有99个点,且目
标点集有很大的非刚性形变。为看清楚起见,模板中的点用‘x’表示,目标中的点

用‘0’表示。在仿射变换的情形下,本算法较文献【9】的算法匹配的结果相对好一些,
在薄板样条的情形下,本算法好于文献【5】的算法匹配结果。由于薄板样条能够将空

『日J变换分解为一个全局仿射变换和局部非仿射变换,因此薄板样条的空『日J变换使得
“福”字匹配的更准确一些。


(三)退火率敏感性测试 参考文献[231的实验,采用的测试样本是手画的鱼形。将在不同的退火率下分别 进行鱼形配准。模板点集有55个点用‘X’表示,目标点集中有49个点用‘0’表示,
如图4.6.3:







硕士论文

图像特征苣匹配算法研究

B.退火率为0.5时



(a)本章算法仿射变换下配准结果

(b)文献【9】仿射变换下配准结果



(c)本章算法薄板样条下配准结果
C.

(b)文献【5】薄板样条下配准结果

退火率为O.1时



(a)本章算法仿射变换卜配准结果

(b)文献【9】仿射变换p配准结果



硕士论文

图像特征声匹配算法研究



(c)本章算法薄板样条下配准结果

(b)文献【5】薄板样条下配准结果

图4.6.4不同退火率下本章算法和文献【9】和【5】特征点匹配结果比较

退火率是退火算法重要的一个参数它决定冷却(即退火)过程中搜索解空间的多
少,提高运算速度的一个主要方法就是提高确定性退火算法的退火率。注意,退火率

的值小那么对应得退火率就高,退火速度快;退火率的值大则对应得退火率低,退火 速度慢。一般情况下,提高退火率必然使算法搜索区间减小而导致算法失败,因此在
基于退火算法的点匹配I 5’8..91一般将退火率设置为0.93。而本文算法中加入相似性度量


值,加快匹配矩阵的求解减少运算量,可以在解空间进行较少的搜索,在一定程度上

能够弥补退火速度过快造成的搜索不足。4.3.1节指出:目标函数或代价函数应能反 映不适当指派所造成的误差,一个好的指派(匹配)应产生小的匹配误差,反之亦然,
小的匹配误差对应的匹配就更准确。从而图4.6.4中,在退火率为0.93、0.5、0.1时

的实验结果可以看出,在适当降低退火率时,本章算法结束时目标函数的值仍然比较
小从而能够得到比文献【5]和【9]算法好的匹配结果。

4.7本章小结
本章算法是对基于确定性退火的点匹配算法【591的进一步改进,该方法利用确定 性退火技术将求解匹配矩阵的组合优化问题转化为连续优化问题。通过退火温度来控 制匹配矩阵的模糊度,不仅增强了算法的鲁棒性,而且减少了陷入局部极值的可能性。


在仿射变换和薄板样条的两种空间变换下,分别给出了适合确定性退火算法求解的新

的能量函数形式以及空间变换的求解。由于算法参考文献[8】的思想,采用X(X.1)形式
的熵做作为阻尼项,使得点匹配问题成为严格凸规划问题,因此可以用KKT条件求

解匹配矩阵H而代替软分配的迭代逼近的Sinkhom法,一定程度上提高了算法准确 性。本算法中主要改进点是引入相似性度量值束约束匹配矩阵,加快了匹配矩阵收敛
的速度减少计算量,使得目标函数能够以较少的搜索代价得到最小化函数值,实验也

额士论文

图像特征点匹配算法研究

验证了本算法在适当高的退火率时仍然能够得到理想的匹配结果。因此本算法对退火 率的要求并不苛刻,在实际应用中可以根据具体问题提高退火率(即减小退火率%的 值,退火进度l"=ro×To加快)以减少算法运算量并且能保证匹配矩阵收敛到全局最优
解或者近似全局最优解。







硕士论文

图像特征点匹配算法研究



总结与展望
特征点匹配问题一直是计算机视觉和模式识别领域中的一个非常基本而又重要

的工作。特征点匹配的主要任务是,将满足一定几何变换关系的同一场景的两幅图像 中的点匹配成对,从而识别和定位物体。它在图像配准、运动目标的监测与跟踪、手 写体识别等诸多领域中部有应用而且对最终的结果起了至关重要的作用。


在多数实际应用中,都是存在非刚性形变的两幅图像特征点进行匹配,因此针对
非刚性特征点匹配给出了两种不同的匹配算法。首先对Chang的算法f,1进行了改进,

利用其寻找匹配点对支持度算法来计算可靠的几何不变量S,然后给出了自上而下的 根据两点间距离不变量的几何推理来求解出最大匹配点对集和最优仿射变换参数。从
大量实验结果表明基于寻找不变量的特征点匹配算法在准确性和稳定性方面都好于

Chang的匹配算法,并且推理严密,计算量小,是一种理想的特征点匹配算法。其次,
本文给出了基于确定性退火的点匹配算法,该算法是对基于确定性退火的点匹配算法

[591的进一步改进,本算法中引入相似性度量值柬约束匹配矩阵,加快了匹配矩阵收 敛的速度减少计算量,使得目标函数能够以较少的搜索代价得到一定温度下的最小目


标函数值,实验也验证了本算法在适当高的退火率时仍然能够得到理想的匹配结果, 改变了以往需要保证较低的退火率,即尽量慢的退火进度才可以得到全局最优解,在 实际应用中可以根据具体问题提高退火率以减少算法运算量并且能保证匹配矩阵收 敛到全局最优解或近似全局最优解。 本文的基于寻找不变量的算法有严密的逻辑推理,计算量小,结果可信度高。而 第二个特征点匹配算法是基于确定性退火的智能方法,有较好的普适性。但是本文的 特征点匹配只考虑了两种空『日J映射方式:仿射变换和薄板样条,实际上对于其它形式 的空间映射,只要在适当的条件下也可以运用本文算法的思想。下一步的工作是对本
文的两个算法作进一步的改进,使其更快速,更正确适应性更强,同时由于时间有限

本文仅利用特征点的坐标信息柬进行特征点匹配,那么以后的工作可以将特征点信息 与灰度等信息结合起来解决其它一些特征匹配问题。



硕士论文

图像特征点匹配算;杰研究

致谢
本文的研究工作是在我的导师朱近还有夏德深教授和孙怀江教授的悉心指导下

完成的。我在603教研室学习和生活的两年多的时间黾,自始至终得到了夏教授、朱 老师和孙老师悉心的关怀和指导。他们严谨的治学态度、深厚的学术功底、敏锐的洞 察力以及平易近人的工作作风斗表现了当代学者风范,这一切令我终身难忘,并将长


期地激励和鞭策我在今后学习工作中更加发奋努力。在这两年多的时间里,夏教授为 我们提供了良好的科研软硬件环境、大量的科研课题与实践机会,使我能够顺利地完
成硕士阶段的学业和科研任务,同时在理论和实践方面都有了很大的提高。同时在生

活上,也得到了夏教授、朱老师和孙老师的关怀。在研究生生活即将结束之际,谨对
导师们两年来的辛勤培养和关怀表示衷心的感谢和崇高的敬意。

感谢本教研室的陈强、汤敏、尤建洁、朱立新、郑钰辉、刘复昌、梅园等博士,
以及教研室所有共同研究和讨论的兄弟姐妹们,他们是孔繁建、史栋林、张继、蒋斌、

欧阳晓丽、戴奇燕、胡哗、邱晓军、何询、邱军等,和他们在学术上的交流与讨论、 项目中的合作与互助使我能够集思广益、收益匪浅。


最后,我要感谢我的家人。他们一直给我精神上的鼓励、物质上的支持、学习上 的督促与激励,对他们的感激之情是我无法用言辞表达的。他们的关怀和鼓励,永远
是我前进的最大动力。





硕士论文

闰像特征点匹配舅法研究

参考文献
【l】夏德深,傅德胜.现代图像处理技术和应用.东南大学出版社,1997 【2】Stockman G,Kopstem 【3】3 Chang S
S.Benett S.Matching images to models for regastraanon and obJeCt detecanon via clustering.IEEE Transon Pattern Analysts and Machine H,Cheng F H,Hsu

Imelhgence,1992,PAMI-4(3):229-241



H,ct a1.Fast algonthm for pomt paRern matchmg:Invanant to

translation,rotaanon and scale changes.Pattem Recogmtlon,1997,30(2):31 1-320



f4】Belongie S,Malik

J,Puzacha J.Shape matehmg and object recogmanon using shap

contexts[J].IEEE
IEEE

Transactions On Pattern Analysis and Machme

Intelhgenee.2002,24(4):509—522 matching[A].Proceedings
Head

【5】ChmHmli,Rangarajan
Conference
Oll

A.A new algorithm for non-rigid point Vislon

Computer

and

Pattern

Recogni-anon[el,Hilton

Island,South

Carolina。USA,2000(2):44-51 【6】6 Wersmg,Helgc Rmer.Backtraeking Determmasanc Armeahng for Constraint Sausfacaon Problems.IEE Conf.On Amficml Nemal Networks。September,1999。7(10):868.873
Helko

忉张祥德,唐青松.确定性退火技术及其在点匹配中的应用.东北大学学报.2003(24):1n9一1122
【8】连玮,张洪才,潘泉.一种采用二次式作为阻尼项的点匹配算法.中国图像图形学 报,2004(9):1080.1089 f9】9
Steven Gold,Anand 2D

Rangarajan,Cluen
Matching:Pose

Ping Lu,Sugtma Pappu,Eric Mjolsness.New Algonthms for

and

3D

Pomt

Estanauon

And

Correspondence.Paaem Recogmton.

V01.31.No.8.1998:1019—1031

【10】Ranade,S.,A.Rosenfeld.Pomt
12(4):269-276.

pattern

mau:hmg

by

relaxauon[J].Pattern

Recogmanon,1980,

【ll】Jezelung

Ton,Anti K.Jam.Regtstermg Landsat Images by Pomt Matching.IEEE an'ansaeanons sensing,v01.27,no.5 1989:642-651 nnage matching using

on

geosctence and remote

[12】H.S.Bmrd.Model-based 【131
Xu

location.Ph.D.thesis,Dept.ofElec.Eng.and

Comput.

S01.,Princeton Umv.,Prmceton,NJ,1984.
Wenh,Zhang
Llhua.A geometnc reasoning based

algonthm

for point paaem matclmag.Science

in China(Series F),V01.44,No 6,200l:445-452

【14】z.Zhang.R.Denche.o Faugeras.A
Through the Recovery

Robust Technique of the

for Matctung Two Uncahbrated Images
Eplpolar

Unknown

Geometry[J].Arlafictal

Imelhgence,1995,78(1-2):87?119. 【15】Lihua Zhang,Wenli
RecogmUon Letters
Xu,Cheng Chang.Genetic algorithm for affme pomt panem matching.PaRem

2003(24):9?19
Hsuan
to

【16】Shah Chang,Fang
Matchmg:Invanant

Chcng,Wen

Hsmg,Guo

gila

Wu.Fast Algorithm for Point
Scale

Paaern

Translatmm,Rotaanons

and

Changes.Pattem

Recogmuon.
Usmg

V01.30.No.2.1997:31 1-320

【17】Tom

Wakahara。Kazumi

Odaka.Adaptive Normallzaanon

of

Handwntten

Characters

Global/Local A壤ne Tansformatmn.IEEE

Tans.PAMI,1998.20(12):1332?1341.
Points Matcbang Based On

【18】Pan Jan-Jun.Zhang Yan-nmg.Correspongdmg

Posmon

Smfilarity.IEEE

ProceedingsoftheComputerGraphics,ImagingandVsmn:NcwTrends.2005:5154.5158

硕士论文

图像特征点匹配算法研究 Matching via Iterative Convex Hull Vertices International Conference on Machine Learning and

[19]Xiang-Yu

Yu,Hong

Sun,Jun

Chen.Points

Pairing.IEEE Proceedings of the Fourth

Cybemetics,Guangzhou,18—21 August.2005:5350—5354.

[20]Ninvan 【22]F

Ansari Edwin Hou著,李军,边肇祺译用于最优化的计算智能.清华大学山版社,1999 [21】万仲平,费浦生.优化理论与方法武汉人学出版社,2004 L Bookstein.Principal warps:Thin-plate splines and the decomposi.tion

ofdeformations[J].IEEE

Tmns.1989,PAMI一1 1(6):567-585

[23】Swamp Medasani,Raghu Krishnapuram,and [24]Serge

YoungSik Choi.Graph Matching by Relaxation of

Fuzzy Assignments IEEE Trans.On Fuzzy Systems,

2001,9(1):173.182
shape

Belongie,Jitendra Malik,Jan Puzicha.Shape Matching and object Recognition using

contexts IEEE Transactins on Pattern Analysis and Maching

Interlligence.2002.24(24):509.522

【25]杨枝灵,王开.Visual c++数字图像获取处理及实践应用.人民邮电出版社,2003. 【26]杨冰.实用最优化方法及计算机程序哈尔滨船舶:[:程学院山版社,1994 [27】Milan Sonka,Vaclav Hlavac,Roger Boyle著,艾海舟,武勃等译.图像处理、分析与机器视觉f第二 版)人民邮电出版社,2003 【28]V 【29]K
Cemy,Thermodynamical approach
to

the仃avelling saleman

problem:An

efficient simulation

algorithm.Journal ofOptimizationTheoryandApplications.1985:41.51
Rose,E

Gurewitz et

a1.Statistical

mechanics and

phase transitions in clustering[J].Physical

Renew Lettem,1990,65:945-948

【30]俞皿青,田学隆,闩春红.医学图像配准方法分类及现状.重庆大学学报,2003(8):114.118 [31]蒋建国,钱源诚,蒋建军.一种跟踪运动物体算法的实现合肥一L业大学学报1994(6):16—22

[32]钟平,于前洋,金光.基丁特征点匹配技术的运动估计及补偿犯法.光电子馓光.2004,15(1),73。77
[33】MehrotraR,Nichani s.Comerdetection.PatternRecognition,1990.23(11):1223.1233 【34]Liu S T,Tsai W H.Moment-priserving comer detection.Pattem Recognition,1990,23(5):441.460. [35]Lee


s,Sun



N,Chen C

H,Tsai C

T.Wavelet based comer detection.PaRem Recognitio—

n,1993,26(6):853—865.

[36]李小春,陈鲸.一种鲁棒的匹配点检测算法.计算机应用,2004(9):25—26
[37]千东峰,张丽飞,刘小军,邹谋炎.基于广义特征点匹配的全自动图像配准.电子与信息学 报,2005(7):1013.1016 [38]Richard O.Duda,Peter 出版社2003.P291
E.Hart,David

GStork著,李宏东,姚天翔等泽.模式分类f第二版).机械工业

【39]胡少兴,轰红彬,马成林、基于遗传算法的种子图像目标点模式匹配.中国图像图形学
报,2003,V01.8(A),No.5,533.539

[40]孙冬梅,裘正定.基_丁确定性退火技术的鲁棒性的点匹配算法.计算机学报,V01(25).No.6,606.61 1 [41]Hath Chui,Anand Rangarajan A new point n_atching algorithm for non.rigid registration.Computer
Vision

and Image Understanding 89(2003):114—141
and

[42]A.Goshtasby 【43]S.Ranade

GC.Stockmm_1.Point

pattern

matching

using

convex

hull

edges IEEE

Trans.Systems Man Cybemet SMC-15(5).1985:631-637 and
A Rosenfeld,Point

pattem

matching

by

relaxation,Pattern

Recog.,

v01.12,PP.269—275,1980

67

图像特征点匹配算法研究
作者: 学位授予单位: 刘莉娜 南京理工大学

参考文献(43条) 1.夏德深.傅德胜 现代图像处理技术和应用 1997 2.Stockman G.Kopstein S.Benett S Matching images to models for registration and object detection via clustering 1992(03) 3.Chang S H.Cheng F H.Hsu W H Fast algorithm for point pattern matching:Invariant to translation,rotation and scale changes 1997(02) 4.Belongie S.Malik J.Puzicha J Shape matching and object recognition using shap contexts 2002(04) 5.ChuiHaili.Rangarajan A A new algorithm for non-rigid point matching 2000 6.Heiko Wersing.Helge Ritter Backtracking Deterministic Annealing for Constraint Satisfaction Problems 1999(10) 7.张祥德.唐青松 确定性退火技术及其在点匹配中的应用[期刊论文]-东北大学学报(自然科学版) 2003(11) 8.连玮.张洪才.潘泉 一种采用二次式作为阻尼项的点匹配算法[期刊论文]-中国图象图形学报A辑 2004(9) 9.Steven Gold.Anand Rangarajan.Chien Ping Lu.Suguna Pappu,Eric Mjolsness New Algorithms for 2D and 3D Point Matching:Pose Estimation And Correspondence 1998(08) 10.Ranade S.A Rosenfeld Point pattern matching by relaxation 1980(04) 11.Jezching Ton.Anil K Jain Registering Landsat Images by Point Matching 1989(05) 12.H S Baird Model-based image matching using location 1984 13.徐文立.张立华 A geometric reasoning based algorithm for point pattern matching[期刊论文]-中国科学 F辑(英文版) 2001(6) 14.Z Zhang.R Deriche.O Faugeras A Robust Technique for Matching Two Uncalibrated Images Through the Recovery of the Unknown Epipolar Geometry 1995(1-2) 15.Lihua Zhang.Wenli Xu.Cheng Chang Genetic algorithm for affine point pattern matching 2003(24) 16.Shih Chang.Fang Hsuan Cheng.Wen Hsing.Guo zua Wu Fast Algorithm for Point Pattern Matching:Invariant to Translations,Rotations and Scale Changes 1997(02) 17.Tom Wakahara.Kazumi Odaka Adaptive Normalization of Handwritten Characters Using Global/Local Affine Tansformation 1998(12) 18.Pan Jun-Jun.Zhang Yan-ning Correspongding Points Matching Based on Position Similarity 2005 19.Xiang-Yu Yu.Hong Sun.Jun Chen Points Matching via Iterative Convex Hull Vertices Pairing 2005 20.Nirwan Ansari.Edwin Hou.李军.边肇祺 用于最优化的计算智能 1999 21.万仲平.费浦生 优化理论与方法 2004 22.F L Bookstein Principal warps:Thin-plate splines and the decomposi-tion of deformations 1989(06) 23.Swarup Medasani.Raghu Krishnapuram.YoungSik Choi Graph Matching by Relaxation of Fuzzy Assignments 2001(01) 24.Serge Belongie.Jitendra Malik.Jan Puzicha Shape Matching and object Recognition using shape contexts 2002(24)

25.杨枝灵.王开 Visual C++ 数字图像获取处理及实践应用 2003 26.杨冰 实用最优化方法及计算机程序 1994 27.Milan Sonka.Vaclav Havac.Roger Boyle.艾海舟.武勃 图像处理、分析与机器视觉 2003 28.V Cemy Thermodynamical approach to the travelling saleman problem:An efficient simulation algorithm 1985 29.K Rose.E Gurewitz Statistical mechanics and phase transitions in clustering 1990 30.俞亚青.田学隆.闫春红 医学图像配准方法分类及现状[期刊论文]-重庆大学学报(自然科学版) 2003(8) 31.蒋建国.钱源诚.蒋建军 一种跟踪运动物体算法的实现 1994(06) 32.钟平.于前洋.金光 基于特征点匹配技术的运动估计及补偿方法[期刊论文]-光电子·激光 2004(1) 33.Mehrotra R.Nichani S Corner detection 1990(11) 34.Liu S T.Tsai W H Moment-priserving comer detection 1990(05) 35.Lee J S.Sun Y N.Chen C H.Tsai C T Wavelet based corner detection 1993(06) 36.李小春.陈鲸 一种鲁棒的匹配点检测算法[期刊论文]-计算机应用 2004(9) 37.王东峰.张丽飞.刘小军.邹谋炎 基于广义特征点匹配的全自动图像配准[期刊论文]-电子与信息学报 2005(7) 38.Richard O Duda.Peter E Hart.David G Stork.李宏东.姚天翔 模式分类 2003 39.胡少兴.查红彬.马成林 基于遗传算法的种子图象目标点模式匹配[期刊论文]-中国图象图形学报A辑 2003(5) 40.孙冬梅.裘正定 基于确定性退火技术的鲁棒性的点匹配算法[期刊论文]-计算机学报 2002(6) 41.Haili Chui.Anand Rangarajan A new point matching algorithm for non-rigid registration 2003 42.A Goshtasby.G C Stockman Point pattern matching using convex hull edges 1985(05) 43.S Ranade.A Rosenfeld Point pattern matching by relaxation 1980

相似文献(9条) 1.学位论文 陈铮铮 一种基于图像特征点的定位算法 2005
目前,自主式的景象匹配定位技术在某些飞行器导航系统中被采用,以提高导航定位精度。景象匹配算法分为两大类,灰度匹配算法和特征匹配算 法。灰度匹配算法是利用图像中像素的灰度强度作为匹配信息。特征匹配算法先从实时图中提取边缘、直线等特征作为匹配信息。 在特征匹配算 法中,如果采用边缘、直线、曲线作为匹配信息进行相关匹配,当图像出现几何畸变时,匹配误差较大,甚至失配。而用特征点匹配能在一定程度上克 服几何畸变带来的影响。 本文提出了一种基于特征点提取的定位算法。在该算法中,首先对实时图中的直线段进行特征提取,以它们的交点作为 特征点。特征点在参考图位置已知,只要获得了它们在实时图中的位置,就可以直接进行定位。 本文首先确定了直线特征提取方法,用于获取实 时图中特征交点。直线提取方法以模板滤波为主,为了克服滤波方法抗线性干扰能力不强的问题,提出了一种形态学滤波的方法,并以这两种算法的结 果为输入,采用一种融合算法消除了线性干扰的影响,并更好的抑制了噪声。此外还提出了一种改善信噪比的方法,以提高算法的适用性。 然后 根据参考图的先验信息,选用合理的逻辑判选求得定位所需的真正交点,进行定位。由于噪声的影响,所要处理的实时图中所得到的交点与参考图中的 交点并不一定是一一对应的。这比起研究两组点模一一对应情况下的点模匹配算法而言更具有实际意义。 该算法与灰度匹配算法相比,不受灰度 畸变影响;与一般特征相关算法相比,计算量小。

2.期刊论文 董瑞.梁栋.唐俊.王年.鲍文霞.DONG Rui.LIANG Dong.TANG Jun.WANG Nian.BAO Wen-xia 基于颜色和 几何特征的图像特征点匹配算法 -计算机技术与发展2006,16(12)
提出一种基于颜色和几何特征的图像特征点匹配算法.首先提取两幅图像特征点集邻域色调的局部累加直方图,然后结合图像特征点的几何特征构造 亲近矩阵,再对亲近矩阵进行奇异值分解(SVD),利用分解的结果构造出一个反应特征点之间匹配程度的关系矩阵,最后根据关系矩阵实现两幅图像的特征 点匹配.实验结果显示,这种图像特征点匹配算法对真实图像的平面旋转和立体旋转都具有较高的匹配精确度.

3.期刊论文 董瑞.梁栋.唐俊.鲍文霞.何韬.DONG Rui.LIANG Dong.TANG Jun.BAO Wen-xia.HE Dao 基于颜色梯度的 图像特征点匹配算法 -计算机工程2007,33(16)
提出了一种利用颜色梯度的彩色图像特征点的匹配方法.结合图像特征点的颜色梯度信息和几何特征分别构造两幅图像的Laplacian矩阵,并对这两个 矩阵进行奇异值分解.利用分解的结果构造出一个反映特征点之间匹配程度的关系矩阵,根据关系矩阵实现两幅图像的特征点匹配.大量实验结果表明,该 文提出的算法具有较高的匹配精度.

4.会议论文 古辉.陈光一.曹文明 基于特征点的门限图像匹配算法 2005
图像匹配在许多领域起着举足轻重的作用,例如,模式发现和识别.目前的图像匹配算法大都是基于模式匹配的改进算法.本文针对基于图像特征点的 匹配策略,通过合理的选取特征点,设定一些门限值,可以准确,快速的实现匹配,测试效果良好.

5.期刊论文 戚世贵.戚素娟.Qi Shigui.Qi Sujuan 一种基于图像特征点的图像匹配算法 -国外电子测量技术 2008,27(1)

图像匹配技术被广泛用于人脸识别、全景图像生成等领域.该文利用变比不变特征点 (Scale Invariance Feature Transform-SIFT)提取方法提取特 征点,并对SIFT方法提取出的特征点用最近邻算法 (Nearest Neighbor-NN)进行匹配,在搜索最近邻特征点和次近邻特征点时使用了在K-D树搜索算法基础 上进行改进的搜索算法BBF(Best Bin First)算法.实验证明该匹配算法具有匹配精度高,鲁棒性好的特点.

6.学位论文 童强 基于两视图的图像匹配算法研究 2006
图像匹配是计算机视觉研究领域中的一个非常重要的热点问题,也是许多计算机视觉理论和应用的基础,其研究成果可广泛应用于精密工业测量、 物体识别、虚拟现实、自动导航、生产自动化及军事等方面。同时,图像匹配又是计算机视觉领域的一个难点问题,许多重要的计算机视觉理论与应用 都是在假设匹配问题已解决的前提下展开的。因此图像匹配算法的研究不但具有重要的理论意义而且具有广泛的应用前景。 本文对基于两视图的 图像匹配算法进行了较为系统的研究,主要包括:基于极几何约束和单应约束的图像匹配、基于颜色和邻接矩阵的图像匹配、基于Laplacian矩阵的图像 匹配。本文的主要研究内容及研究成果如下: 1.在深入研究极几何、单应以及基本矩阵求解方法的基础上,提出了一种基于极几何约束和单应约 束的图像匹配算法,首先使用互相关法对图像特征点集进行初始匹配,然后运用RANSAC方法鲁棒地估计基本矩阵和单应矩阵并相应地剔除错误匹配点 ,最后利用优化后的基本矩阵和单应矩阵引导匹配以获得更多、更精确的匹配点。 2.在深入研究基于图谱理论的图像匹配方法的基础上,提出了 一种基于颜色和邻接矩阵的图像匹配算法。首先结合高斯加权函数和图像特征点邻域的颜色信息构造邻接矩阵,并对该矩阵进行奇异值分解(SVD),然后 利用分解的结果构造出一个反应特征点之间匹配程度的关系矩阵,最后根据关系矩阵实现两幅图像的特征点匹配。 3.在深入研究Laplacian矩阵基 础上,提出了一种基于Laplacian矩阵的图像匹配算法。首先分别构造两幅图像特征点集的Laplacian矩阵,并对这两个矩阵进行奇异值分解(SVD),然后 利用分解的结果构造出一个反应特征点之间匹配程度的关系矩阵,最后根据关系矩阵实现两幅图像的特征点匹配。大量实验结果表明,所提出的基于 Laplacian矩阵的图像特征匹配算法具有较高的匹配精度。

7.学位论文 杨利敏 图像特征点定位算法研究及其应用 2008
图像特征点定位是图像处理与模式识别领域中的重要环节,也是影响识别结果和效果的一个关键性问题。由于图像的复杂性以及需求的多样性,特 征点定位具有很大针对性,即对于不同类型的图像和不同的需求,往往要具体问题具体分析,采用不同的特征点定位方法。 本文主要对图像特征 点定位算法及其在不同领域的应用进行了研究。其中重点研究了指纹识别、人脸识别以及头影测量分析中的图像特征点定位算法。本文的主要贡献总结 如下: 1)提出一个基于奇异点的指纹图像粗匹配算法,此算法由于直接对灰度指纹图像进行操作,不需要进行大量的预处理,从而减少了预处理 过程带来的信息损失,提高了处理速度,适用于大型指纹库搜索中检索可能匹配的指纹;构建了一个新的四邻近特征向量(QNMV),并提出一个基于四邻 近特征向量的指纹匹配算法,在FVC指纹库上的实验结果表明此算法具有很好的快速性与精确性。 2)提出一个基于RGB色彩空间R通道的瞳孔精确定 位算法;在对主动形状模型(ASM)深入分析的基础上,提出一个基于瞳孔位置初始化的RGB三通道ASM面部特征点定位算法,此算法不仅很好的解决了 ASM平均模型位置初始化的问题,而且由于RGB三通道的采用,充分利用了人脸图像中的信息,提高了ASM定位算法的精度,与传统ASM算法相比具有很大 优势。 3)对已有头影图像测量分析中标志点定位方法归纳总结的基础上,分别对基于边缘跟踪和基于ASM的标志点定位算法进行了研究。实验结果 表明,两种算法的标志点定位精度与人工定位并无明显差异,而在定位速度上却远比人工定位要快。

8.期刊论文 陈望明.刘连芳.CHEN Wang-ming.LIU Lian-fang 宽基线图像特征点的立体匹配 -计算机应用研究 2008,25(12)
为了实现宽基线图像特征点的自动立体匹配,结合目前已有的算法,提出了一种新的分层匹配算法来获取最初的匹配点集,实现了基于对极几何约束的 图像特征点自动提取及自动匹配.

9.期刊论文 洪小伟.石守东.康丹.HONG Xiao-wei.SHI Shou-dong.KANG Dan 一种基于小波模极大值的图像特征匹 配算法 -宁波大学学报(理工版)2009,22(1)
针对移动机器人视觉图像间的连续特性,提出了一种基于小波模极大值的图像特征匹配算法,该算法利用小波模极大值提取图像轮廓及模方位矩阵,并 在轮廓图像中寻找极大区域,以该区域中心点作为图像特征点,且将区域小波模方位、特征点区域图像重心坐标和区域轮廓重心方向组合生成这些特征点 的特征向量,利用这些特征向量实现图像间的特征点匹配.并通过相应的实验证明提出的新算法高效可靠.

本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1001260.aspx 下载时间:2009年11月9日



更多相关文章:
图像特征点提取及匹配算法研究本科毕业论文.doc
图像特征点提取及匹配算法研究本科毕业论文 - 本科毕业设计 (论文 ) 题目名称:图像特征点提取及匹配算法研究 目录摘要 ......
图像特征点匹配算法研究与改进.pdf
图像特征点匹配算法研究与改进 - 图像特征点匹配算法研 究 与改进 付洪
基于sift特征点图像匹配方法研究.ppt
基于sift特征点的图像匹配方法研究 - 主要介绍特征点匹配的一些算法,重点是sift及其相关算法
基于特征图像匹配算法-毕业论文(含源代码).doc
基于特征点的快速匹配算法[J].电光与控制,2009,16(2), 65-66. [3] 王军,张明柱.图像匹配算法研究进展[J].大气与环境光学学报,2007,2(1), 12-15. ...
图像特征点提取及匹配算法研究_曹煦.pdf
图像特征点提取及匹配算法研究_曹煦 - INTELLIGENCE 科技天地 图像特征点提...
图像匹配算法研究.pdf
西安电子科技大学 硕士学位论文 图像匹配算法研究 姓名:张强 申请学位级别:硕士 ...关键词:图像匹配互相关特征点边缘检测毫米波 Abstract Imagematchingis all ...
图像特征点提取与描述算法研究.doc
图像特征点提取与描述算法研究 - 龙源期刊网 http://www.qikan.com.cn 图像特征点提取与描述算法研究 作者:孙莹 来源:《信息安全与技术》2016 年第 02 期 【...
Sift图像匹配算法研究.pdf
Sift图像匹配算法研究_计算机软件及应用_IT/计算机_专业资料。sift图像匹配算法的...基于特征点的图像匹配算法主要包括 三个部分:特征点提取,特征点描述和特征点匹配...
图像局部特征点检测算法综述.doc
图像局部特征点检测算法综述 - 图像局部特征点检测算法综述 研究图像特征检测已经有一段时间了,图像特征检测的方法很多,又加上各种算法 的变形, 所以难以在短时间内...
图像中角点(特征点)提取与匹配算法.doc
图像中角点(特征点)提取与匹配算法_工学_高等教育_教育专区。处理图像角点提取与匹配算法 该算法用matlab语言实现角点提取与匹配算法实验报告 角点提取与匹配算法实...
图像特征点匹配的强壮算法.pdf
图像特征点匹配的强壮算法 - 第 14 卷第 8 期 2002 年 8 月 计算
图像模板匹配快速算法研究.pdf
图像模板匹配快速算法研究 - 中南大学 硕士学位论文 图像模板匹配快速算法研究 姓名:刘锦峰 申请学位级别:硕士 专业:计算机应用技术 指导教师:沙莎 20070501 摘要 ...
基于颜色和几何特征的图像特征点匹配算法.pdf
基于颜色和几何特征的图像特征点匹配算法 - 计算机技术与发展 第 16 卷 第
基于DOG特征点的序列图像匹配算法_论文.pdf
基于DOG特征点的序列图像匹配算法 - 针对实时匹配的要求,提出一种基于DOG特征点的快速图像匹配算法,用以匹配只存在平移和较小旋转的序列图像。该算法通过求高斯差分...
图像快速匹配算法研究.doc
图像快速匹配算法研究 - 目 录 引言 ...
双目立体视觉中的特征点匹配算法研究.pdf
双目立体视觉中的特征点匹配算法研究 - 哈尔滨工程 大学硕士学位 论文 摘 要
基于空间纹理相似性的图像点特征匹配算法_论文.pdf
基于空间纹理相似性的图像点特征匹配算法 - 第3 3 卷第 l 2期 201 6年1 2月 计算机应用研究 Application Res ...
图像特征点提取及匹配技术.pdf
图像特征点提取及匹配技术 - 第 17 卷 第 9期 光学 精密工程 Optic
图像特征点匹配的强壮算法.pdf
图像特征点匹配的强壮算法 - 第 14 卷第 8 期 2002 年 8 月 计算
图像中角点(特征点)提取与匹配算法.pdf
图像中角点(特征点)提取与匹配算法 - 角点提取与匹配算法实验报告 1 说明 本文实验的目标是对于两幅相似的图像,通过角点检测算法,进而找出这两幅图像的共 同点...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图