·146· 智能系统学报 第3卷 Hausdorff距离为 f+1(x,以是视频序列中相邻的连续3帧。 H(A,B)=max(h(A,B)h(B.A))= d(x,以=f+1(x,以-f,(x,以表示连续2帧的差 1D1D2|=|DD4I. 分，对d,和d.1分别滤波后取交集，即可获得当前 式中D1D|和D3D4|分别表示D到D2及D 帧运动对象D。(x,以，差分算法原理见图2 到D4的距离.可以看出，如果让模板G沿O和O 所在的直线向圆G靠拢，则H(A,B)逐步减小，当 模板的圆C与待检测的圆G完全重合时，D,= D2=D3=D,H(A,B)=0,此时匹配效果最好 对于上述理想情况，Hausdorff距离很好地反 映了集合A和B的匹配程度.但是，在实际的应用 图2差分算法原理 中，一幅图像除了有与模板相同或相似的物体外，还 Fig.2 The principle of difference algorithm 存在着其他的边缘点，如图1(d)所示，G的圆心O 通过实验可知，三帧差分算法计算简单，有运算 上有一孤点，当D与D2的距离|DD2|大于 速度快的优点，能够达到实时的要求.但是，差分法 |D2O|时，有H(A,B)=|D1D2.实际上，当两圆 缺陷在于所提取出的轮廓往往不是单像素的，且无 G与CG2完全重合时应有最好的匹配程度，但此时 法将运动物体全部提取出来，如图3所示」 却有H(A,B)>H2(A,B),因此Hausdorff距离 不能直接用于实际的图像匹配中。 (a)实拍图像 (b)三帧差分的结果 (a)原图 (b)模板 图3三帧差分算法效果 Fig.3 The effect of three differential algorithm D 1.3主动轮廓算法 算法中设有一条可变空间曲线v(s,)由2个参 (c)2个理想圆的匹配 (d)圆C的圆心上有 数s(空间位置)和t时间)决定，s与t分别定义在区 一点时的匹配 间2与T上.v由具有相同参数的2个变量xy构 图1 Hausdorff距离匹配示意图 成即 Fig.I The sketch of Hausdorff distance matching v(x,=(xs,,y(s,d,s∈P,t∈T.2) Hausdorff距离可以自然地推广到部分Haus 这样，Snake的势能函数ESmake可以定义为 doff距离，以便匹配2个集合A和B的某个部分 对于2个有限点集A={am,m,ap}和B={h, R=支E》+E》+ Ereld(v(s）lds (3) 血，bp},A、B之间的部分Hausdorff距离定义为 式中：Ei代表Snake的内部能量，Eeu为图像能量， Hu(A,B)max(h(B,A)h (A,B)).(1) Eneld为外部能量. 式中：：(A,B)称为集合A到集合B的部分有向 然而，主动轮廓算法也有许多局限，该算法强烈 Hausdorf距离，其中1≤k≤p,1≤I≤q, 地依赖于轮廓的初始位置，且捕捉范围小，不仅因进 hk(B,A)=K8 ea min‖a-b‖，h加(A,B)=Le 入凹陷区域困难而常常陷于能量局部极值，而且不 m‖b-aⅡ，这里表示从集合B到集合A排 支持拓扑改变，另外在外力很小时，轮廓会收缩到一 序后的距离值集合中的第K值，L出4表示从A集合 点.针对初始位置敏感的问题，有些文献提出了利用 到B集合排序后的距离值集合中的第L个值， 遗传算法来处理，因为它的优势在于能保证能量全 1.2三帧差分算法 局最小化.但是其缺点是计算量会随搜索空间的增 三帧差分算法中，设f1(x,y以、f,(x,以、 大而增长迅速.难以实时应用 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.netHausdorff 距离为 H ( A , B) = max ( h( A , B) , h( B , A) ) = | D1 D2 | =| D3 D4 | . 式中 :| D1 D2 | 和| D3 D4 | 分别表示 D1 到 D2 及 D3 到 D4 的距离. 可以看出 ,如果让模板 C2 沿 O1 和 O2 所在的直线向圆 C1 靠拢 ,则 H ( A , B) 逐步减小 ,当 模板的圆 C2 与待检测的圆 C1 完全重合时 , D1 = D2 = D3 = D4 , H ( A , B) = 0 ,此时匹配效果最好. 对于上述理想情况 , Hausdorff 距离很好地反 映了集合 A 和 B 的匹配程度. 但是 ,在实际的应用 中 ,一幅图像除了有与模板相同或相似的物体外 ,还 存在着其他的边缘点 ,如图 1 (d) 所示 ,C1 的圆心 O1 上有一孤点 , 当 D1 与 D2 的距离 | D1 D2 | 大 于 | D2 O1 | 时 ,有 H2 ( A , B) = | D1 D2 | . 实际上 ,当两圆 C1 与 C2 完全重合时应有最好的匹配程度 ,但此时 却有 H1 ( A , B) > H2 ( A , B) ,因此 Hausdorff 距离 不能直接用于实际的图像匹配中. 图 1 Hausdorff 距离匹配示意图 Fig. 1 The sketch of Hausdorff distance matching Hausdorff 距离可以自然地推广到部分 Haus2 dorff 距离 ,以便匹配 2 个集合 A 和 B 的某个部分. 对于 2 个有限点集 A = { a1 , a2 , …, ap } 和 B = { b1 , b2 , …, bp } , A 、B 之间的部分 Hausdorff 距离定义为 Hkl ( A , B) = max ( hk ( B , A) , hl ( A , B) ) . (1) 式中 : hk ( A , B) 称为集合 A 到集合 B 的部分有向 Hausdorff 距 离 , 其 中 1 ≤ k ≤ p , 1 ≤ l ≤ q , hk ( B , A) = K th b∈B min a∈A ‖a - b ‖, hl ( A , B ) = L th a ∈A min b∈B ‖b - a ‖,这里 K th b∈B表示从集合 B 到集合 A 排 序后的距离值集合中的第 K 值 , L th a∈A表示从 A 集合 到 B 集合排序后的距离值集合中的第 L 个值. 1. 2 三帧差分算法 三帧差分算法中 , 设 f t - 1 ( x , y ) 、f t ( x , y ) 、 f t + 1 ( x , y) 是 视 频 序 列 中 相 邻 的 连 续 3 帧 , dt ( x , y) = f t + 1 ( x , y) - f t ( x , y) 表示连续 2 帧的差 分 ,对 dt 和 d t - 1分别滤波后取交集 ,即可获得当前 帧运动对象 Do ( x , y) ,差分算法原理见图 2. 图 2 差分算法原理 Fig. 2 The principle of difference algorithm 通过实验可知 ,三帧差分算法计算简单 ,有运算 速度快的优点 ,能够达到实时的要求. 但是 ,差分法 缺陷在于所提取出的轮廓往往不是单像素的 ,且无 法将运动物体全部提取出来 ,如图 3 所示. 图 3 三帧差分算法效果 Fig. 3 The effect of three differential algorithm 1. 3 主动轮廓算法 算法中设有一条可变空间曲线 v (s, t) 由 2 个参 数 s(空间位置) 和 t(时间) 决定 ,s 与 t 分别定义在区 间Ω与 T 上. v 由具有相同参数的 2 个变量 x、y 构 成 ,即 v ( x , t) = ( x (s, t) , y (s, t) ) ,s ∈Ω, t ∈ T. (2) 这样 ,Snake 的势能函数 ESnake可以定义为 ESnake = 1 2∫Ω [ Eint ( v (s) ) + Eext ( v (s) ) + Efield ( v (s) ) ]ds. (3) 式中 : Eint代表 Snake 的内部能量 , Eext 为图像能量 , Efield为外部能量. 然而 ,主动轮廓算法也有许多局限 ,该算法强烈 地依赖于轮廓的初始位置 ,且捕捉范围小 ,不仅因进 入凹陷区域困难而常常陷于能量局部极值 ,而且不 支持拓扑改变 ;另外在外力很小时 ,轮廓会收缩到一 点. 针对初始位置敏感的问题 ,有些文献提出了利用 遗传算法来处理 ,因为它的优势在于能保证能量全 局最小化. 但是其缺点是计算量会随搜索空间的增 大而增长迅速. 难以实时应用. ·146 · 智 能 系 统 学 报 第 3 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net