基于离散Fréchet距离的判别曲线相似性的算法  

Curve Similarity Judgment Based on the Discrete Fréchet Distance

作　　者：朱洁[1] 黄樟灿[1] 彭晓琳[1] 

机构地区：[1]武汉理工大学理学院,湖北武汉430070

出　　处：《武汉大学学报（理学版）》2009年第2期227-232,共6页Journal of Wuhan University:Natural Science Edition

基　　金：国家自然科学基金资助项目(69672014)

摘　　要：提取出离散曲线中的关键特征至高点与至低点,并且用离散Fréchet距离作为距离的测度来对至高点与至低点进行研究,建立了一种判断离散曲线相似性的数学模型,此模型不需要对曲线进行平移和伸缩变换.由于模型的求解是NP困难问题,针对这种情况,提出了一种新的多项式的求解算法,以在线手写签名验证为例验证数学模型,然后对随机的150个测试签名进行检验,结果成功匹配率为91.33%,误纳率为6%,误拒率为2.67%.In this paper, we submit the key characters of the curves, namly vertices and rock bottom, and introduce a new curve similarity definition based on the discrete Frechet distance. We present a new mathematical model for the discrete curve similarity judgment, which does not need to carry on translation and stretching to the curves. Because the model solution is one kind of NP difficult problem, we propose a new multinomial solution algorithm, and finally take online handwriting signature verification as example to confirm the mathematical model. For 150 test signatures that we choose randomly, the successful matching rate is 91.33%, the wrong reacceptance is 6% and the wrong reject rate is 2.67%.

关 键 词：签名验证 离散Fréchet距离 组合步 Fréchet排列 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]