第18卷 第4期
2009年10月
云南民族大学学报(自然科学版)
Journa l of Yunnan U n i ve rsity of N ati onaliti es(N atura l Sc i ences Ed iti on) V o. l 18 N o . 4O ct . 2009
曲线形态相似性的定义与度量
江 浩 褚衍东 郭丽峰
(兰州交通大学数理与软件工程学院, 甘肃兰州730070)
摘 要 提出了曲线形态相似性的定义与度量问题. 介绍了一种曲线的划分方法, 得到一个曲线的比值样本, 基于统计学原理, 给出了曲线相似性的定义与度量方法. 并通过算例验证了该相似性度量方法的可行性.
关键词 曲线; 相似性; 度量=中图分类号>O 211. 9; P282
=文献标识码>A
=文章编号>1672) 8513(2009) 04-0316-03
D efi n ition and M easure m ent o f Shape Sim il arit y f or Curves
Jiang H ao Chu Y andong Guo Lifeng
(Schoo l o fM athe m atics , Physics and Soft w are Eng i n eering , Lanzhou Ji a otong U niversity , Lanzhou 730070, Ch i n a)
Abst ract :The proble m of defi n iti o n and m easure m ent o f shape si m ilarity for curves is studied . It i n troduces a div i s ion m ethod of curves and gets a rati o sa m p l e . Based on the pri n c i p les of statisti c s , the defi n ition and m easure -m ent m ethod of shape si m ilarity fo r curves i s g iven . And an exa m p l e validates that thism easure m entm e t h od is fea -si b le .
K ey words :curve ; si m ilarity ; m easure m ent
1 问题的提出
随着地理信息系统(G I S) 在社会各领域的应用
和推广, 人们对G I S 的需求层次呈现多样化趋势, 空间数据的多尺度表达问题已经成为地理信息科学研究的热点问题之一, 它主要是利用自动综合的方法, 将一个特定尺度下的空间数据转换到另一个尺度下的空间数据, 转换的结果必然带来空间数据的变化, 这些变化不仅仅是简单的图形放缩过程, 在视觉上它直接表现为图形的几何形状和拓扑关系的变[1-3]化. 如图1所示, 相同城市A 、B 之间的连线随着尺度的变化, 图形所能表示的信息也有所变化(小比例尺s 2下, 若干不太重要的城镇P 、Q 、M 被删除), 与此同时曲线的几何形状也发生了变化. 产生这一些现象的主要原因是比例尺的改变和图形简化算法的使用, 导致了若干点被合并或删除.
相似性是同类或异类对象的本质特征, 相似性分析与定量描述在模式识别、计算机图形学、仿生学等领域有着广泛的应用. 同样衡量两个模型空间分
收稿日期:2009-03-30.
布特征是否能保持一致, 就必须对空间分布特征的相似性进行分析和度量, 其评价标准和评估方法必须定量化. 对于不同尺度下线状图形(图1), 通
常涉及到曲线的相似问题. 经典几何学中关于图形相似性的研究已经得到了相当丰富的成果, 如三角形相似、多边形相似、折线相似、相似变换等, 但是关于任意两条曲线相似性问题的报道目前还不多见. 本文主要从数学的角度, 借助于统计手段, 研究任意曲线几何形态相似性的定义、度量与应用问题
.
[4-5]
2 曲线相似性的定义与度量
假设有曲线A 1B 1、A 2B 2, 并将它们置于同一直
作者简介:江浩(1983~), 男, 硕士研究生. 主要研究方向:应用数学.
第4期 江 浩等:曲线形态相似性的定义与度量
角坐标系中. 连接点A 1、A 2与点B 1、B 2, 线段A 2A 1、的延长线相交于点O , 在曲线A 1B 1中除去端点A 、B 1的部分任意选取n -2个点, 连同端点A 1、B 1依次记为A 1, P 1, P 2, , , P n -2, B 1, 显然当n y ]时, 曲线A 1B 1可由集合
P ={A1, P 1, P 2, , , P n -2, B 1}
渐近近似地表出. 再将N A 2OB 2划分成n -2份:A 1, A 2, , , A , n -2. 在划分N A 2OB 2的过程中, 保证点P 1, P 2, , P n -2出现在不同的小角A , 2, , , n -2) 里. 在曲线i (i =1
A 2B 2中夹在角A i 的部分, 任意选取k i 个点, 依次记为Q i 1, Q i 2, , , Q ik i (ki I N +), 如图2所示. 同样, 当在曲线A 2B 2上选取的点数充分多时, 集合
Q ={A 2, Q 11, Q 12, , , Q 1k 1, Q 21, Q 22, , , Q 2k 2, , , Q n -2, 1, Q n -2, k n -2, B 2}
就可以将曲线A 2B 2渐近近似地表出
.
1
取点的方法与过程可知, 比值样本D ={d 1, d 2, , , d n }是服从或是渐近服从正态分布的. 下面
利用正态分布的区间估计方法给出曲线相似性的定义与度量方法.
定义 设D ={d 1, d 2, , , d n }是曲线L 、H 对应集合P 、Q 的比值样本, D 的均值是L , 方差R 为. 若d i 落在相应概率F (z ) 的置信区间时, 即有
d i I [L -z R , L +z R ], i I {1, 2, , , n },其中z 是相应概率F (z ) 的概率度, z 与F (z ) 之间常用的对应数值见表1.
表1 z 与F (z ) 之间的关系
z
1
1165
1196
2
2158
3
2
F (z ) [***********][***********]
则称曲线L 对应集合P 中第i 个点P i 与曲线H 对应集合Q 相似, 简称点P i 与集合Q 相似. 如果有k 个这样的点P i I P 与集合Q 相似,
k
那么就称为曲线L 、H 对应集合P 、Q 之间的
n 相似度, 记为S I M (P, Q ) =
n
当在曲线L 、H 上选取的点数充分多时, 对应集合P 、Q 就可以渐近近似地将两条曲线L 、H 表出, 这时曲线L 、H 的相似性就可以由对应集合P 、Q 之间的相似度进行度量, 即曲线L 、H 的相似度SI M (L,H ) =SI M (P,Q ).
当z =3时, 通常被一些实际工作者称为正态分布的/3R 0原则.
下面分别计算下列个值:
1n -2
E |OQ 1j |E |OQ n -2, j |
|OA 2|k 1j =1k n -2j =1|O B 2|
, , , , , |OA 1||O P 1||OP n -2||O B 1|其中|#|表示2点之间的距离, 即对于任意2点A (x A , y A ), B (x B , y B ),
|AB |=
(x A -x B ) +(y A -y B ) .
k
k
3 应用算例
将上述n 个值依次设为d 1, d 2, , , d n , 并称D ={d 1, d 2, , , d n }为曲线A 1B 1、A 2B 2对应集合P 、Q 的比值样本.
根据中心极限定理可知, 如果一个结果是由大量相互独立的随机因素的影响所造成, 而每一个个别因素在总影响中所起的作用不大, 则这种量都服从或近似服从正态分布. 进一步n 而言, 不论总体是什么分布, 均值=i E x 及
n =1i 其线性变换都是服从正态分布的
[6]
如图3所示, 有任意2条曲线L 1、L 2, 利用上述方法将这2条曲线划分成8份, 得到1组数据(见表
. 再由上述
云南民族大学学报(自然科学版) 第18卷
2). 表2中, D 1表示交点O 到曲线L 1中若干点的距离, D 2表示交点O 到曲线L 2中若干点的距离的平均值. D 表示D 1与D 2的比值样本.
下面用z =1来计算2条曲线的相似度. 此时, 比值样本的均值L =1. 7534, 均方差R =0. 1334,
D 1D 2D
[***********]
[***********]
[***********]
[***********]
概率为68. 27%的置信区间为[1. 6200, 1. 8869],曲线L 1、L 2的相似度为60%.同样可以计算z 取其
他值时, 2条曲线的相似度. 如当z =3时, 得到置信区间为[1. 3532, 2. 1537],此时两条曲线的相似度为100%.
[***********]
[***********]
[***********]
[***********]
[***********]
表2 曲线的距离样本
[***********]
通过计算可知, 当概率度z 选取不同的值时, 所计算得到的相似度有很大的不同. 我们猜想:z 的取
值可能与人们的实际经验、两图形之间的差异大小等因素有关, 需要对不同人群作进一步的调查问卷.
相似的定义与度量方法, 并通过算例验证了方法的可行性. 还有许多问题有待于进一步解决, 如该图形
相似性度量方法与传统相似判断方法有什么区别与联系; 如何在多尺度地理空间目标相似关系研究中应用此方法; 如何将该定义和方法推广到空间曲线曲面相似中去, 等等, 这些问题是作者以后将要深入研究的课题.
4 结语
本文基于概率与统计学原理, 给出了任意曲线参考文献:
[1] 丁虹. 空间相似性理论与计算模型的研究[D ].武汉:武汉大学资源与环境科学学院, 2004:13-34.
[2] 郭庆胜, 丁虹. 基于栅格数据的面状目标空间方向相似性研究[J]武汉大学学报:信息科学版, 2004, 29(5):447-465. [3] 吕秀琴, 吴凡. 多尺度空间对象拓扑相似关系的表达与计算[J].测绘信息与工程, 2006, 31(2):29-32. [4] 边丽华, 闫浩文, 刘纪平, 等. 多边形化简前后相似度计算的一种方法[J].测绘科学, 2008, 33(6):207-208. [5] 张永华, 程耀东, 闫浩文, 等. 多尺度空间线状实体形状相似关系的表达与度量[J].测绘科学, 2008, 33(6):83-86. [6] 陈家鼎, 郑忠国. 概率与统计[M].北京:北京大学出版社, 2007:94-167.
(责任编辑 万志琼)
(上接第315页)
则根据(1), (2) 式有:Y *(Y *X ) =(XH Y , H 则X *(X*Y) =(Y H X, H ).
从而有:Y *(Y *X ) =(X) =(XH Y, X H Y) =(Y H X, Y H X ) =X *(X*Y), 证毕. 我们规定:Y C X =Y *(Y *X ) =(XH Y , X H Y), 则Y C X =X C Y, 且有性质.
(7) Y C X [X, Y P X, Y I SC R (U ).
证明 因为有(1) X H Y A X, Y Z X H Y [X, Y ; (2)X H Y A X, Y Z X H Y [X, Y 所以有Y C X [X, Y . 由上述规定很容易证明X [Y Z Y C X =X 且Y C X 就是X, Y 的下确界. 限于篇幅, 对于粗代数格的研究, 将进一步探讨. 参考文献:
[1] 张文修. 粗糙集理论与方法[M ].科学出版社, 2006.
[2] 陈建飞. 关于粗糙集的一点注记[J].云南民族大学学报:自然科学版, 2002, 11(2):65-67.
[3] 邓方安. 关于粗糙集的若干注记(Ñ) ) ) ) 粗糙集与Stone 代数[J].汉中师范学院学报:2002, 20(2):1-4. [4] 乔全喜. 粗糙集代数与M V 代数[J].模糊系统与数学, 2008, 22(3) :152-155. [5] 胡庆平. BCI-代数[M].西安:陕西科技出版社, 1987.
[6] AHMAD B . Fuzzy BC I-a l g ebra[J].J F uzzy M ath , 1993, 1(2) :445-452.
(责任编辑 万志琼)
第18卷 第4期
2009年10月
云南民族大学学报(自然科学版)
Journa l of Yunnan U n i ve rsity of N ati onaliti es(N atura l Sc i ences Ed iti on) V o. l 18 N o . 4O ct . 2009
曲线形态相似性的定义与度量
江 浩 褚衍东 郭丽峰
(兰州交通大学数理与软件工程学院, 甘肃兰州730070)
摘 要 提出了曲线形态相似性的定义与度量问题. 介绍了一种曲线的划分方法, 得到一个曲线的比值样本, 基于统计学原理, 给出了曲线相似性的定义与度量方法. 并通过算例验证了该相似性度量方法的可行性.
关键词 曲线; 相似性; 度量=中图分类号>O 211. 9; P282
=文献标识码>A
=文章编号>1672) 8513(2009) 04-0316-03
D efi n ition and M easure m ent o f Shape Sim il arit y f or Curves
Jiang H ao Chu Y andong Guo Lifeng
(Schoo l o fM athe m atics , Physics and Soft w are Eng i n eering , Lanzhou Ji a otong U niversity , Lanzhou 730070, Ch i n a)
Abst ract :The proble m of defi n iti o n and m easure m ent o f shape si m ilarity for curves is studied . It i n troduces a div i s ion m ethod of curves and gets a rati o sa m p l e . Based on the pri n c i p les of statisti c s , the defi n ition and m easure -m ent m ethod of shape si m ilarity fo r curves i s g iven . And an exa m p l e validates that thism easure m entm e t h od is fea -si b le .
K ey words :curve ; si m ilarity ; m easure m ent
1 问题的提出
随着地理信息系统(G I S) 在社会各领域的应用
和推广, 人们对G I S 的需求层次呈现多样化趋势, 空间数据的多尺度表达问题已经成为地理信息科学研究的热点问题之一, 它主要是利用自动综合的方法, 将一个特定尺度下的空间数据转换到另一个尺度下的空间数据, 转换的结果必然带来空间数据的变化, 这些变化不仅仅是简单的图形放缩过程, 在视觉上它直接表现为图形的几何形状和拓扑关系的变[1-3]化. 如图1所示, 相同城市A 、B 之间的连线随着尺度的变化, 图形所能表示的信息也有所变化(小比例尺s 2下, 若干不太重要的城镇P 、Q 、M 被删除), 与此同时曲线的几何形状也发生了变化. 产生这一些现象的主要原因是比例尺的改变和图形简化算法的使用, 导致了若干点被合并或删除.
相似性是同类或异类对象的本质特征, 相似性分析与定量描述在模式识别、计算机图形学、仿生学等领域有着广泛的应用. 同样衡量两个模型空间分
收稿日期:2009-03-30.
布特征是否能保持一致, 就必须对空间分布特征的相似性进行分析和度量, 其评价标准和评估方法必须定量化. 对于不同尺度下线状图形(图1), 通
常涉及到曲线的相似问题. 经典几何学中关于图形相似性的研究已经得到了相当丰富的成果, 如三角形相似、多边形相似、折线相似、相似变换等, 但是关于任意两条曲线相似性问题的报道目前还不多见. 本文主要从数学的角度, 借助于统计手段, 研究任意曲线几何形态相似性的定义、度量与应用问题
.
[4-5]
2 曲线相似性的定义与度量
假设有曲线A 1B 1、A 2B 2, 并将它们置于同一直
作者简介:江浩(1983~), 男, 硕士研究生. 主要研究方向:应用数学.
第4期 江 浩等:曲线形态相似性的定义与度量
角坐标系中. 连接点A 1、A 2与点B 1、B 2, 线段A 2A 1、的延长线相交于点O , 在曲线A 1B 1中除去端点A 、B 1的部分任意选取n -2个点, 连同端点A 1、B 1依次记为A 1, P 1, P 2, , , P n -2, B 1, 显然当n y ]时, 曲线A 1B 1可由集合
P ={A1, P 1, P 2, , , P n -2, B 1}
渐近近似地表出. 再将N A 2OB 2划分成n -2份:A 1, A 2, , , A , n -2. 在划分N A 2OB 2的过程中, 保证点P 1, P 2, , P n -2出现在不同的小角A , 2, , , n -2) 里. 在曲线i (i =1
A 2B 2中夹在角A i 的部分, 任意选取k i 个点, 依次记为Q i 1, Q i 2, , , Q ik i (ki I N +), 如图2所示. 同样, 当在曲线A 2B 2上选取的点数充分多时, 集合
Q ={A 2, Q 11, Q 12, , , Q 1k 1, Q 21, Q 22, , , Q 2k 2, , , Q n -2, 1, Q n -2, k n -2, B 2}
就可以将曲线A 2B 2渐近近似地表出
.
1
取点的方法与过程可知, 比值样本D ={d 1, d 2, , , d n }是服从或是渐近服从正态分布的. 下面
利用正态分布的区间估计方法给出曲线相似性的定义与度量方法.
定义 设D ={d 1, d 2, , , d n }是曲线L 、H 对应集合P 、Q 的比值样本, D 的均值是L , 方差R 为. 若d i 落在相应概率F (z ) 的置信区间时, 即有
d i I [L -z R , L +z R ], i I {1, 2, , , n },其中z 是相应概率F (z ) 的概率度, z 与F (z ) 之间常用的对应数值见表1.
表1 z 与F (z ) 之间的关系
z
1
1165
1196
2
2158
3
2
F (z ) [***********][***********]
则称曲线L 对应集合P 中第i 个点P i 与曲线H 对应集合Q 相似, 简称点P i 与集合Q 相似. 如果有k 个这样的点P i I P 与集合Q 相似,
k
那么就称为曲线L 、H 对应集合P 、Q 之间的
n 相似度, 记为S I M (P, Q ) =
n
当在曲线L 、H 上选取的点数充分多时, 对应集合P 、Q 就可以渐近近似地将两条曲线L 、H 表出, 这时曲线L 、H 的相似性就可以由对应集合P 、Q 之间的相似度进行度量, 即曲线L 、H 的相似度SI M (L,H ) =SI M (P,Q ).
当z =3时, 通常被一些实际工作者称为正态分布的/3R 0原则.
下面分别计算下列个值:
1n -2
E |OQ 1j |E |OQ n -2, j |
|OA 2|k 1j =1k n -2j =1|O B 2|
, , , , , |OA 1||O P 1||OP n -2||O B 1|其中|#|表示2点之间的距离, 即对于任意2点A (x A , y A ), B (x B , y B ),
|AB |=
(x A -x B ) +(y A -y B ) .
k
k
3 应用算例
将上述n 个值依次设为d 1, d 2, , , d n , 并称D ={d 1, d 2, , , d n }为曲线A 1B 1、A 2B 2对应集合P 、Q 的比值样本.
根据中心极限定理可知, 如果一个结果是由大量相互独立的随机因素的影响所造成, 而每一个个别因素在总影响中所起的作用不大, 则这种量都服从或近似服从正态分布. 进一步n 而言, 不论总体是什么分布, 均值=i E x 及
n =1i 其线性变换都是服从正态分布的
[6]
如图3所示, 有任意2条曲线L 1、L 2, 利用上述方法将这2条曲线划分成8份, 得到1组数据(见表
. 再由上述
云南民族大学学报(自然科学版) 第18卷
2). 表2中, D 1表示交点O 到曲线L 1中若干点的距离, D 2表示交点O 到曲线L 2中若干点的距离的平均值. D 表示D 1与D 2的比值样本.
下面用z =1来计算2条曲线的相似度. 此时, 比值样本的均值L =1. 7534, 均方差R =0. 1334,
D 1D 2D
[***********]
[***********]
[***********]
[***********]
概率为68. 27%的置信区间为[1. 6200, 1. 8869],曲线L 1、L 2的相似度为60%.同样可以计算z 取其
他值时, 2条曲线的相似度. 如当z =3时, 得到置信区间为[1. 3532, 2. 1537],此时两条曲线的相似度为100%.
[***********]
[***********]
[***********]
[***********]
[***********]
表2 曲线的距离样本
[***********]
通过计算可知, 当概率度z 选取不同的值时, 所计算得到的相似度有很大的不同. 我们猜想:z 的取
值可能与人们的实际经验、两图形之间的差异大小等因素有关, 需要对不同人群作进一步的调查问卷.
相似的定义与度量方法, 并通过算例验证了方法的可行性. 还有许多问题有待于进一步解决, 如该图形
相似性度量方法与传统相似判断方法有什么区别与联系; 如何在多尺度地理空间目标相似关系研究中应用此方法; 如何将该定义和方法推广到空间曲线曲面相似中去, 等等, 这些问题是作者以后将要深入研究的课题.
4 结语
本文基于概率与统计学原理, 给出了任意曲线参考文献:
[1] 丁虹. 空间相似性理论与计算模型的研究[D ].武汉:武汉大学资源与环境科学学院, 2004:13-34.
[2] 郭庆胜, 丁虹. 基于栅格数据的面状目标空间方向相似性研究[J]武汉大学学报:信息科学版, 2004, 29(5):447-465. [3] 吕秀琴, 吴凡. 多尺度空间对象拓扑相似关系的表达与计算[J].测绘信息与工程, 2006, 31(2):29-32. [4] 边丽华, 闫浩文, 刘纪平, 等. 多边形化简前后相似度计算的一种方法[J].测绘科学, 2008, 33(6):207-208. [5] 张永华, 程耀东, 闫浩文, 等. 多尺度空间线状实体形状相似关系的表达与度量[J].测绘科学, 2008, 33(6):83-86. [6] 陈家鼎, 郑忠国. 概率与统计[M].北京:北京大学出版社, 2007:94-167.
(责任编辑 万志琼)
(上接第315页)
则根据(1), (2) 式有:Y *(Y *X ) =(XH Y , H 则X *(X*Y) =(Y H X, H ).
从而有:Y *(Y *X ) =(X) =(XH Y, X H Y) =(Y H X, Y H X ) =X *(X*Y), 证毕. 我们规定:Y C X =Y *(Y *X ) =(XH Y , X H Y), 则Y C X =X C Y, 且有性质.
(7) Y C X [X, Y P X, Y I SC R (U ).
证明 因为有(1) X H Y A X, Y Z X H Y [X, Y ; (2)X H Y A X, Y Z X H Y [X, Y 所以有Y C X [X, Y . 由上述规定很容易证明X [Y Z Y C X =X 且Y C X 就是X, Y 的下确界. 限于篇幅, 对于粗代数格的研究, 将进一步探讨. 参考文献:
[1] 张文修. 粗糙集理论与方法[M ].科学出版社, 2006.
[2] 陈建飞. 关于粗糙集的一点注记[J].云南民族大学学报:自然科学版, 2002, 11(2):65-67.
[3] 邓方安. 关于粗糙集的若干注记(Ñ) ) ) ) 粗糙集与Stone 代数[J].汉中师范学院学报:2002, 20(2):1-4. [4] 乔全喜. 粗糙集代数与M V 代数[J].模糊系统与数学, 2008, 22(3) :152-155. [5] 胡庆平. BCI-代数[M].西安:陕西科技出版社, 1987.
[6] AHMAD B . Fuzzy BC I-a l g ebra[J].J F uzzy M ath , 1993, 1(2) :445-452.
(责任编辑 万志琼)