二维模式近似匹配的快速算法

被引：2

作者：

桑梓勤

丁明跃

张天序

机构：

[1] 华中理工大学图象识别与人工智能研究所图象信息处理与智能控制国家教委开放实验室

来源：

中国图象图形学报 | 1997年 / 12期

关键词：

精确匹配，近似匹配，快速算法;

D O I：

暂无

中图分类号：

O157 [组合数学（组合学）];

学科分类号：

070101 [基础数学];

摘要：

给定一个大小为ｎ×ｎ的文本Ｔ和一个大小为ｍ×ｍ的模板Ｐ，如果文本Ｔ中存在一个ｍ×ｍ的子块与模板Ｐ能够逐点匹配，称为精确匹配。如果最多有ｋ个元素不同，称为带有最多ｋ个误差的近似匹配。对于精确匹配，本文给出了一个时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜）的算法，∑＝｛ａ１，２，…，ａ｜∑｜｝，是模板的字符集。对于近似匹配，快速算法分为两步：（１）预选。利用精确匹配算法找出能精确匹配的ｓ×ｓ（０≤ｓ≤ｍ）子块，得到ｈ个候选的对准点；（２）验证。把模板对准候选点，逐点比较，以确定不相同的元素是否不超过ｋ个。近似匹配的时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜＋ｈｍ２）。

引用

页数：7