| 二维模式近似匹配的快速算法 |
| |
| 引用本文： | 桑梓勤,丁明跃,张天序.二维模式近似匹配的快速算法[J].中国图象图形学报,1997,2(12):883-889. |
| |
| 作者姓名： | 桑梓勤 丁明跃 张天序 |
| |
| 作者单位： | 华中理工大学图象识别与人工智能研究所图象信息处理与智能控制国家教委开放实验室 |
| |
| 摘 要： | 给定一个大小为ｎ×ｎ的文本Ｔ和一个大小为ｍ×ｍ的模板Ｐ，如果文本Ｔ中存在一个ｍ×ｍ的子块与模板Ｐ能够逐点匹配，称为精确匹配。如果最多有ｋ个元素不同，称为带有最多ｋ个误差的近似匹配。对于精确匹配，本文给出了一个时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜）的算法，∑＝｛ａ１，２，…，ａ｜∑｜｝，是模板的字符集。对于近似匹配，快速算法分为两步：（１）预选。利用精确匹配算法找出能精确匹配的ｓ×ｓ（０≤ｓ≤ｍ）子块，得到ｈ个候选的对准点；（２）验证。把模板对准候选点，逐点比较，以确定不相同的元素是否不超过ｋ个。近似匹配的时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜＋ｈｍ２）。
|
| 关 键 词： | 精确匹配 近似匹配 快速算法 图象识别 |
A Fast Approach to Two-Dimensional Pattern Matching |
| |
| Sang Zhiqin,Ding Mingyue and Zhang Tianxu.A Fast Approach to Two-Dimensional Pattern Matching[J].Journal of Image and Graphics,1997,2(12):883-889. |
| |
| Authors: | Sang Zhiqin Ding Mingyue and Zhang Tianxu |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《中国图象图形学报》浏览原始摘要信息 |
|
点击此处可从《中国图象图形学报》下载免费的PDF全文 |
