文档介绍：微机发展,2003,9
图像中给定图形的搜索定位算法
张林1，俞扬
有 S 个黑点，设 t(X)为对 X 个点进行操作的时间，则总时间
为 t(N*N-M+M*S)。一般 M 与 N*N 为相同数量级，M*S>N*N。由于 N、M 无法改变，就将注意力集中到 S 上。
图 1 中左侧的图像中可以看出，与 Pattern 中极点对应重合的点只有 10 个（不包括有残缺的和比例有变化的），
这样的点在图像中的比例 a<=1/S，可见没有必要操作 M*S 个点。故将 Pattern 的存储数据分组。
算法改为：发现是黑点时，以该点为基点，对应图形中的极点并逐分判断与图形重合与否，一旦某组不重
合即认为不重合，不再比较。
将数据平均分为 q 组，这样的时间为 t(N*N-M+M*1/S*S+M*(S-1)/S*S/q) =t(N*N+M*(S-1)/q)。当 q=100 时，
上面实验只需 秒（包括绘图）。分组的方法在后面有进一步分析。搜索结果如图 2。图中搜索出的图形加粗
了。
图 2 中下方有两个残缺图像，由于没有完全匹配而没有搜索出来。在原算法中可以很简单的加入对残缺图像
的匹配。原算法中已将 Pattern 分组比较，可以在分组比较时返回比较的匹配度。图 3 为在 70%匹配度情况下的结
果。
p=100 100% match p=100 70% match
图 2 p=100, 100%匹配 图 3 p=100, 70%匹配
2 变比例搜索
以上我们已经实现了基本的算法，下面我们要做的是在源图中寻找与 Pattern 同样形状而比例不同的图形。
这将使算法的复杂度增加，因此专门讨论。我们先找出 Pattern 的高度，既是其最高点到其最低点的长度，然后
记录下每个点相对于基准点的半径与其的比值。在对源图进行比较时，也同样加入一个相同定义的比值，在两点
的比值也相同时命中。不同的是由于我们事先无法知道源图中图像