再上一篇: 第 8 章  电  信
上一篇:8. 2  集成 TDMA 通信系统的数据吞吐量最大化
主页
下一篇:9. 2  模拟退火框架
再下一篇:9. 3  进化程序设计
文章列表

第 9 章  点模式匹配

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

形状识别是计算机视觉和模式识别中的一个重要任务。术语“形状”指的是一个物体的一组静态空间特征中的相对距离不变的几何性质。这些静态空间特征就是物体的形状特征[17]。人的眼睛所感受的很多视觉数据对于识别的目的来说是高度冗余的。从人的视觉系统的观点来看,沿物体轮廓的某些支配点具有丰富的信息含量,足以用来表征物体的形状。因此用来作为形状特征的点的点模式匹配(PPM,point patternmatching)是一项关键的视觉课题。

本章所讨论的PPM 问题就是在一个被观测的点模式中寻找这样一个子集,使其通过变换在某种最优意义上与一个模型点模式的子集相匹配。这些点的顺序信息是未知或已被提供。一般的情况是点分布在n维空间,且根据问题的几何和环境约束条件对变换加以规定。由于图象本来就是二维的,因此这里只考虑二维(2D)点模式,但是所提出的算法并不局限于二维点模式。大量文献报导过有关平面物体识别的研究工作,例如,文献[9],[16],[17],[18],[20],[21],[90],[148],[161],[140],[141],[142]。现有的用点作为特征的方法可能要求这些点排列顺序的先验知识。本章回顾了在不存在点的顺序知识的情况下,在文献[9]和[16]中讨论过的点模式匹配方法。

9. 1  问题的表述

给定下式定义的两个点集:

P = {Pi Pi∈RN;  i= 1,2,3,…,m}

N (9.1)

O= {Oi Oi∈R ;  i= 1,2,3,…,n}

求这样一个指派P′→O′,P′P 和O′O使T(P′)和O′之间的匹配误差最小化。下面要加以定义的匹配误差反映出了匹配程度。匹配误差越小,匹配品质越好。T 是预先确定的相似变换;T≡{旋转,平移,尺度}。应注意它不同于为了使两幅图象重合,用几何变换使图象对准的问题[135]。

令O是被观测的点模式,P 是模型点模式。二维相似变换由映射X→U定义,X 和U∈ 2,且

R

u = S cosθ sinθ x + e (9.2)

v - sinθ cosθ y f

式中

x u T

X = y , U= v (9.3)S= 尺度因子,θ= 旋转角,e= x 轴平移,f= y轴平移。令a= Scosθb, = Ssinθ,则相似变换

#第87页-

可以重新写成

u = a b x + e (9.4)

v - b a y f

为了确定模型点和被观测点之间的匹配程度,使P 最优映射到O的相似变换参数是在最小平方误差的意义上得到的。在变换T[(xi,yi)]= [(ui′,vi′)]下映射P,得

ui′= a b xi + e (9.5)

vi′ - b a yi f

模型点集和被观测点集之间的平方误差于是可以定义为

2 = (ui- ui′)2 + (vi- vi′)2

∑i= 1

n (9.6)

= ((ui- axi- byi- e)2 + (vi+ bxi- ayi- f)2)

i= 1

为了求取使平方误差最小的参数,只要对(9.6)式定义的平方误差对a,b,e和f 求偏导并使其等于0,即

2 n

ε= 2 ((ui- axi- byi- e)(- xi) + (vi+ bxi- ayi- f )(- yi)) = 0

a ∑

i= 1

2 n

ε= 2 ((ui- axi- byi- e)(- yi) + (vi+ bxi- ayi- f)(- xi)) = 0

b ∑

i= 1

2 n

ε= 2 (ui- axi- byi- e)(- 1) = 0和

e ∑

i= 1

2 n

ε= 2 (vi- bxi- ayi- f)(- 1) = 0

f ∑

i= 1

解以上方程,并重写成矩阵形式

A[a  b  e  f]T = C (9.7)其中

(xi2 + y2) 0 xi yi

∑ ∑ ∑

0 (xi2 + y2) yi - xi

A= ∑ ∑ ∑ (9.8)

∑xi ∑yi n 0

∑yi - ∑xi 0 n

∑(uixi+ viyi)

∑(uiyi- vixi)

C= (9.9)

∑ui

∑vi

可求得使平方误差最小的最优变换参数为

[a  b  e  f]T = [A- 1 C] (9.10)

#第88页-

但是这样得到的最小平方误差只是定量表征了模型点集的子集P′和被观测点集的子集O′之间的匹配程度。为了度量两个模式点集之间的全面的匹配程度,定义下式的启发式度量[17]

2 m- 2 m- 2

^ 1+ log2 k≥3

ε= S ¡¤k k- 2 k- 2 (9.11)

∞ k= 0,1,2

为匹配误差,它体现了对不完全匹配的惩罚。这里k表示匹配上被观测点的模型点的数量,S 表示尺度因子。应该注意,上述方程意味着两点或更少的点的匹配被认为是不确定的。对数项作为模式集合不完全匹配的惩罚因子。当两个模式所有的点都匹配上时(k=m),匹配误差就等于规范的最小平方误差。以上所定义的问题是一个组合优化问题,并可用前几章所阐述的技术很好地进行求解。这样一个问题的解空间的大小是

min{m,n} m n

∑ (i!) (9.12)

i= 0 i i

n n!

其中 = ;n! = n(n- 1)(n- 2)…(2)(1)

m m! (n- m)!

为了说明PPM问题,我们把它置于用模拟退火和进化方法求解的框架上来讨论。