基于自顶向下分裂聚类的图像匹配算法研究
- 格式：pdf
- 大小：1.30 MB
- 文档页数：4
第34卷第5期
2017年5月计算机应用研究
Application
Research
of
ComputersVol
. 34 No
. 5
May
2017
基于自顶向下分裂聚类的图像匹配算法研究+
谢宜婷，王爱平，邹海
(安徽大学计算机科学与技术学院，合肥
230601)
摘要：为了提高图像匹配的效果，提出一种自顶向下分裂聚类的图像匹配算法，该算法可以获得多个目标级
别的对应关系的聚类，进而找到两幅图像共存的多个目标。在互&近邻图表示模型的基础上，通过团检测方法
来获得图中的团，主要是利用分裂聚类的思想，并定义了一个团密度函数，根据此函数来确定分裂终止条件。根
据团检测技术获得的团恢复出团内的对应关系，从而达到图像匹配的目的。实验结果表明：该算法有较好的性
能，可以应用到很多图像匹配问题中。
关键词：图像匹配；互&近邻图；团检测；分裂聚类
中图分类号：
TP391;
TP301.6 文献标志码
：A 文章编号：1001-3695(2017)
05-1590-04
doi：10. 3969/
j.
issn. 1001-3695. 2017. 05. 070
Research of image matching algorithm based on top-down split clustering
Xie
Yiting,
Wang
Aiping,
Zou
Hai
(College
of
Computer
Science
& Technology
, Anhui
University
, Hefei
230601 , China
)
Abstract ：
In
order
to
improve
the
effect
of
image
matching
,this
paper
proposed
an
image
match
down
split
clustering
to
obtain
the
clustering
of
corresponding
relation
of
multiple
target
levels.
And
then
it
found
coexistent
multiple
targets
of
t-wo
images.
On
the
basis
of
mutual k
neighbor
graph
representation
model,the
cluster
of
the
figure
by
cluster
detection
method,
mainly
using
the
idea
of
split
clustering.
And
this
paper
defined
a
cluster
den
sity
function,
which
determined
split
termination
condition.
Finally,
the
algorithm
recovered
the
corresponding
relation
within
the
clusters
which
were
obtained
by
the
cluster
detection
technolog,
so
as
to
achieve
the
goal
of
image
matching.
The
experi
mental
results
show
that
the
algorithm
has
good
performance
and
it
can
be
applied
to
solve
a
lot
of
image
matching
problems.
Keywords:
image
matching；
mutual
k
neighbor
graph；
cluster
detection；
split
clustering
〇引言
图像匹配，是指在不同时间、不同成像条件下，通过一定的
匹配算法在两幅或多幅图像之间识别特征点从而建立几何对
应关系的过程。随着科学技术的发展，图像匹配技术已经成为
现代信息处理领域中一项十分重要的技术。相关研究表明，计
算机视觉领域中大约有40%的应用需要使用图像匹配技
术[1^3],所涉及到的领域有模式识别、图像数据库检索、天气预
报、环境研究、文字识别、指纹识别、医学诊断、自然资源分析以
及遥感图像处理等。因此，为了提高图像处理质量和识别精
度，深人研究图像匹配算法具有重要意义和实用价值。
很多图像匹配算法都用到了聚类的思想，所谓聚类就是根
据事物的某些属性，把事物聚集成类，使类内相似度尽量高、类
间相似度尽量低。聚类算法有分割聚类方法、层次聚类方法、
基于网格的方法、基于密度的方法、基于模型的方法等，目前最
常用的是层次聚类方法，典型的层次聚类方法有
BIRCH[45]、
CURE[6]、
ROCK[7]、
Chameleon[
s]等
。Zhang 等人提出了
BIRCH
算法主要用来对大规模数据集进行聚类。
BIRCH算法是一种
传统且有效的层次聚类方法，首先用自底向上的层次策略得到
初步结果，然后用迭代的重定位方法来改进结果，从而可以有
效地去除离群点。
CURE算法是使用代表点的层次聚类方法。该算法将传统对类的表示方法进行了改进，选择的是一种基于
质心和基于代表对象方法之间的中间策略。针对大型数据库，
CURE算法具有良好的伸缩性，采用的是随机取样和划分两种
方法的组合:一个随机样本首先被划分,每个划分再被部分聚
类。
ROCK算法是适用于枚举型数据的层次聚类方法。该算
法针对具有分类属性的数据使用了链接这一概念，即两个对象
间共同的近邻数目。
ROCK算法采用一种比较全局的观点，通
过考虑成对点的邻域情况进行聚类。如果两个相似的点同时
具有相似的邻域,那么这两个点可能属于同一个簇而合并。
Chamelen算法是采用动态建模来确定一对簇之间的相似度。
该算法首先使用一种图划分算法将
k最近邻图划分成大量相
对较小的子簇，然后使用层次聚类算法,基于子簇的相似度反
复地合并子簇。与以上算法相比,
Chameleon在发现高质量的
任意形状的簇方面具有很强的能力。
Cho等人[9]提出了一种基于自底向上的凝聚层次聚类方
法，即
ACC算法，该算法对于异常数据和变形都具有鲁棒性。
本文所提出的图像匹配算法与
ACC算法类似，都是采用聚类
的思想。本文采取的是自顶向下的分裂层次聚类方法,操作简
单，与
ACC方法不同。为了自动检测出两幅图像中共同拥有
的视觉物体,一种互
k近邻图模型被提出，在该模型中，顶点用
来表示特征点之间的对应关系。由于不同物体之间发生的变
收稿日期：2016
-03
-29;
修回日期：2016-05-23
基金项目：国家自然科学基金资助项目（61573022)
作者简介：谢宜婷（1992-),女
，安徽锏陵人
，硕士研究生
，主要研究方向为图像匹配与识别（
Hndaxie2016@163
. cm);王爱平（1955-),女
，教
授，
硕士，
主要研究方向为人工智能；邹海（1969-),
男，
副教授，
博士，
主要研究方向为智能计算.第5期
谢宜婷，等:基于自顶向下分裂聚类的图像匹配算法研究• 1591 •
换不同，在互
A近邻图模型中以不同的团显示。因此,本文采
用团检测技术来解决图像匹配问题。
1问题描述
从两幅图像上分别提取两组特征点集和
S,每个特征点
r表示成
r = 是特征点描述符,
r; = (*,
y)是
r点的坐
标。候选匹配关系集^
refi
and
s
se ,它包
含所有可能的对应关系。候选匹配集
i可以通过比较特征描
述符的相似性™或通过
BOF方法[11]构建。
对于每一个候选对应关系c, = (
r,)，特征相似性用来度
量特征点
r和之间的内容相似性。对于每一对对应关系（
c,,
c;)，其中
c,，^
e
i，几何相似性用来度量对应关系
c,和^之间
的几何变形。最终的目标是根据特征相似性和成对的几何相
似性来去除
i中的离群匹配，从而获得多个类,且每类中特征
对应关系是一致的。此结果可以表示为互不相交的对应关系
类集合0 =
I
Ci ,
C2，…,
C丄其中任意的
Q
e 0,
Q
C
i。
通常情况下,正确的匹配具有相似的特征，而
SIFT描述符
具有较好的特征描述性能,广泛应用于特征匹配问题中。因
此，对应关系
C = (
r，)的特征相似性
dapp(
c,)可以定义成特征
点厂和、的相应
SIFT描述符之间的欧氏距离，即& =/(夂，
〇0。其中必是特征点「的
SIFT特征向量，必是特征点
s的
SIFT特征向量，&代表特征向量必和《之间的欧氏距离。
本文采用互
A近邻图模型表示方法,通过检测图中的团体
结构来实现图像匹配。为了获得候选对应关系的互
A近邻图
模型表示,首先需要定义距离度量准则，来确定图中顶点的
A
近邻邻居。本文采用对应关系间的几何相容性作为度量准则。
几何相容性越高，对应关系之间越近邻。
为了得到几何相容性,本文利用仿射不变区域检测
MS-
ER[12]方法获取特征点，因
MSER具有较好的仿射不变性和稳
定性。为了描述的方便，，=(
r，)
ei也可表示为
c,=((，
〇，,），其中分别代表特征点
r的中心、的中心、到
^的单应矩阵。两个对应关系
C =((,,),
H,)和
c = ((，/)，
H;)的成对几何相容性‘（
cc) [1]定义为
^ =
mfix (-2( _
Hjj
I +
I- HJil
I)) ⑴
L
（c，
C)=『_ 了（ _
Hi/
z1 + 1
H, 1) ⑵
其中，•
i代表欧氏距离；
Pg。其实是一个转换误差。如果
H
和
H彼此相似，那么‘。将会很大。探索两个匹配关系之间
的单应关系而得到的几何相容性为本文的图像匹配算法提供
了一个区分团的准则。
2团密度
一般来说，团就是图中这样一种节点的集合:处于集合内
部的节点之间紧密连接在一起，而处于不同集合之间的节点则
较稀疏地连接在一起。
社团检测方法在社交网络中发挥着十分重要的作用，主要
有基于层次聚类的团检测方法[14]、基于模块度（
modularity)的
团检测方法[1]、基于主动学习的半监督团检测方法[1]、基于
标签传播的团检测方法[17]等。基于层次聚类的方法是团检测
方法中一类比较传统的方法，根据向网络中增添边还是移除
边，这类算法分为两种：)基于层次凝聚的团检测法;
b)基于
层次分裂的团检测法。
Girian和
Newman在2002年提出的
GN算法[1]是最流行的层次社团检测算法，提出了边介数的概念，
定义边介数为网络中所有节点间的最短路径通过这条边的路
径的个数。由于处于社团之间的边具有连接两个社团中节点
的功能，它们具有较高的边介数值，通过迭代地删除边介数最
高的边，直到整个图分解为完全孤立的点或者期望的子图个数
为止。在社团分裂过程中，
GN算法存在一个缺点，即它对团
体结构没有定量的定义，从而在聚类数目未知的情况下，无法
确定分裂应该进行到哪一步。对此,
Newman提出了模块度的
概念,也称为模块化度量值，是目前常用的一种衡量网络社区
结构强度的方法。模块度的定义为:
表示某一个社团内部连接各节点的边数占网络中所有边数的
比例，,=表示与第，个社团相连的边占网络中所有边
的比例。模块度
P是到目前为止用得最多且众所周知的度量
社团密度的函数。基于层次分裂的思想，结合图像匹配问题本
