python匹配算法（验证码识别之模板匹配方法）

本文目录

• 验证码识别之模板匹配方法
• 用python解一道通配符匹配的算法题
• 模板匹配概述
• Python如何实现组织算法pairwise（高效测试用例）
• python两个图片的坐标判断图片是否平移

验证码识别之模板匹配方法

在写爬虫的时候难免会遇到验证码识别的问题，常见的验证码识别的流程为：

- 图像灰度化

- 图像去噪(如图像二值化)

- 切割图片

- 提取特征

- 训练

但这种方法要切割图片，而且破解验证码的重点和难点就在于 能否成功分割字符 。

本文要介绍的算法 不需要进行图片切割，也不需要进行机器训练 ，这种方法就是模板匹配：将待识别的文字切割成一个个模板，在待识别的图像中去匹配模板。

这篇文章将分为两个部分：

第一部分介绍模板匹配的基本概念以及模板匹配的一种实现算法：快速归一化互相关匹配算法；

第二部分是一个具体实例。

模板匹配是在图像中寻找目标的方法之一，目的就是在一幅图像中寻找和模板图像最相似的区域。

模板匹配的大致过程是这样的：通过在输入图像上滑动图像块对实际的图像块和输入图像进行匹配。

假设我们有一张100x100的输入图像，有一张10x10的模板图像，查找的过程是这样的：

从输入图像的左上角(0,0)开始，切割一块(0,0)至(10,10)的临时图像；

用某种方法得出临时图像与模板的相似度c,存放到相似度矩阵中（矩阵大小为91 x91）；

切割输入图像从(0,1)至(10,11)的临时图像，对比，并记录到相似度矩阵；

重复上述步骤，直到输入图像的右下角。

最终得到一个相似度矩阵，找到矩阵中的最大或最小值，最大值（最小值）对应的临时图像即为与模板最相似的图像。

在步骤b中，求模板与图像的相似度有多种方法，如平均绝对差算法（MAD）、绝对误差和算法（SAD）、误差平方和算法（SSD）、归一化互相关算法（NCC），本文使用的是归一化互相关算法。

什么是归一化互相关？

从几何图形上来看，空间中的两个向量，同方向平行时，归一化互相关系数为1，表示两个向量最相似，反方向平行时归一化互相关系数为-1，垂直时为0，表示最不相似（用互相垂直的三个向量来代表整个空间也是这个道理，垂直的向量之间不包含对方的信息，相关系数为0），存在一定夹角时处于（-1，1），是不是跟余弦函数很像，cos(0)=1,cos(pi/2)=0,cos(pi)=-1。就是这个样子的，相关系数可以看作是两个向量之间夹角的cosine函数。

在数学中是这么计算cosine函数的，假设两个n维向量X,Y，对应的坐标分别为(x1，x2，…xn), (y1，y2，…yn) 则：

（如果想要了解更多，请参考文献【2】）

但这是一维的，在模板匹配中要再加一个维度 （具体算法请参考文献【3】） ，简要说一下文献【3】的内容：如果直接计算二维相似度的话计算复杂度会非常高，文献【3】利用快速傅里叶变换与积分图像快速算法来降低计算复杂度。

接下来让我们看一个具体的应用。

模板匹配识别验证码的具体步骤为：

1. 找出图片中所有可能出现的字符，制作成模板集合

2. 图像灰度化

3. 图片去噪（二值化）

4. 模板匹配

5. 匹配结果优化

要识别的图片如下，以识别图片中的加字为例：

要从image中找到与模板最匹配的部分，Template图像是事先从image图像中截取的一部分。所用的为python模块skimage中的match_template方法，match_template方法使用的是快速归一化互相关算法 【2】 。

遍历模板图像集合，与图像匹配，如果dist大于阈值h，则认为此模板在图像中存在，否则不存在，继续匹配下一个模板，直到遍历完所有模板。

以模板‘加’为例，图像大小为40x260，模板大小27x27，result是一个大小为（14，234）的矩阵，即上文提到的相似度矩阵，矩阵中的数值属于，找到result中最大值所处的对应位置即为与模板最匹配的图像位置:x=66,y=11，正好对应模板图像在image中所处的位置。 （更多内容请参阅参考文献【4】）

但这是比较好的情况，因为在匹配时遍历了所有的模板，而一张图片中出现的模板数量是有限的，比如数字’四’在图片中是没有的，这时就要根据某种规则去掉这些在图片中没有出现的模板：程序中使用dist变量来过滤匹配结果，如果dist变量大于某个值则认为此模板在图像中不存在。

最后的result_list中可能仍然存在一些图片中不存在的模板或者匹配不精确的模板，比如数字‘一’在模板中不存在，但仍然可以匹配到，因为数字‘二’中可以匹配到‘一’，需要进一步优化，优化方法有很多，比如当匹配到的两个模板距离过近时，选择较大的那个模板，其余方法留给读者自行考虑吧。

后续将会推出如何使用深度学习识别验证码，敬请期待~

参考文献：

***隐藏网址***

***隐藏网址***

J. P. Lewis, “Fast Normalized Cross-Correlation”, Industrial Light and Magic.

***隐藏网址***

本文作者 ：李晖（点融黑帮），毕业于电子科技大学，现就职于点融成都Data部门，对一切新鲜事物充满好奇，对跳舞毫无抵抗力的活力女青年一枚。

用python解一道通配符匹配的算法题

假设输入的字符串为s，匹配串为p，代码如下

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        sIndex, pIndex = 0, 0
        sLen = len(s)
        pLen = len(p)
        sPrevIndex, pPrevIndex = 1, pLen
        while sIndex 《 sLen:
            #当两个串对应位置字母可以等价时，各自索引均向后
            if pIndex 《 pLen and (s == ’?’):
                sIndex += 1
                pIndex += 1
            #当模式串为*时，先以匹配0个的方式暂时匹配
            elif pIndex 《 pLen and p == ’*’:
                sPrevIndex = sIndex + 1
                pPrevIndex = pIndex
                pIndex += 1
            #当暂时匹配失败时，以匹配多1个的方式继续匹配
            elif pPrevIndex 《 pLen:
                sIndex, pIndex = sPrevIndex, pPrevIndex
            #匹配失败
            else:
                return False
        #看模式串剩下的字母是否均为*
        for i in range(pIndex, pLen):
            if p != ’*’:
                return False
        return True

模板匹配概述

模板匹配是通过一张模板图片去另一张图中找到与模板相似部分的一种算法。一个模板是一张小图片，这个图片有一定的尺寸，有角度（一般是不旋转的矩形， 角度为0）。

模板匹配算法一般是通过滑窗的方式在待匹配的图像上滑动，通过比较模板与子图的相似度，找到相似度最大的子图。这种算法最核心部分在于如何设计一个相似性函数。
最容易想到的一个相似性函数便是欧式距离：

将这个相似性函数展开，可以得：

可以看出，只有第二项是有意义的，因为第一项和第三项的值在选定模板后是固定的。对于欧式距离相似函数，值越大表示越不相似，也就是说，第二项的值越小则越不相似。

将第二项进行归一化：

那么当R(i, j)为1时，表示模板与子图完全相等。

cv::matchTemplate(const CvArr* image, 　　//欲搜索的图像。它应该是单通道、8-比特或32-比特 浮点数图像
const CvArr* template,　　//搜索模板，不能大于输入图像，且与输入图像具有一样的数据类型
CvArr* result, 　　　　//比较结果的映射图像。单通道、32-比特浮点数.
　　　　　　　　　　　　若图像是W×H而templ是w×h，则result一定是(W-w+1）×(H-h+1）
int method　　　　　　//CV_TM_SQDIFF、CV_TM_SQDIFF_NORMED、CV_TM_CCORR、
　　　　　　　　　　　　CV_TM_CCORR_NORMED、CV_TM_CCOEFF、CV_TM_CCOEFF_NORMED
);

函数来进行模板匹配。其中的method参数具体如下:

在通过matchTemplate函数进行模板匹配后，可以得到一个映射图，这张图中最大值的地方便是匹配度最大的子图的左上角坐标，可以使用cv::minMaxLoc函数获得子图位置和相应分数，再进行后续操作。

使用传统的模板匹配速度较快，但是无法应对旋转和缩放问题。要解决旋转不变的 问题，必须要得到旋转不变的特征量，例如特征点。

使用SIFT或SURF计算得到模板和待匹配图像的特征点，然后使用RANSAC或者FLANN进行特征点匹配， 最后进行仿射变换便可得到匹配的位置。

python opencv实现（surf）：
# - - coding:utf-8 - -
author = ’Microcosm’

运行的具体信息如下：
操作系统：ubuntu 14.04
运行环境：
opencv版本：opencv 3.0
模板大小：126x96 png
匹配图像大小：750x407 jpg
特征提取时间：0.15 s
KNN匹配时间：0.0024s
匹配效果：

Python如何实现组织算法pairwise（高效测试用例）

下面小编就为大家带来一篇高效测试用例组织算法pairwise之Python实现方法。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧
开篇：
测试过程中，对于多参数参数多值的情况进行测试用例组织，之前一直使用【正交分析法】进行用例组织，说白了就是把每个参数的所有值分别和其他参数的值做一个全量组合，用Python脚本实现，就是itertools模块中product方法（又称笛卡尔积法）。
正交分析法的优点是测试用例覆盖率100%，缺点测试用例数量庞大，执行用例消耗的人工巨大。
Pairwise （结对）算法源于对传统的正交分析方法优化后得到的产物，它的理论来自于数学统计。毫不避讳的说，本人看不懂数学统计中的学术论文，只能从网上找一些通俗简单的说法来理解其基本含义。
网上很多人都实例都是用 【操作系统，浏览器，语言环境】来举例的，本人也做同样示例：
操作系统： W（Windows）,L（Linux）,Mac （Mac） ；浏览器：M（Firefox）,O(Opera)，IE；语言环境：C（中文），E（英文）
按照正交分析法：会产生3x3x2=18种组合方式 ，测试用例覆盖率100%。
Pairwise结对测试用例组织法，可压缩到9种组合方式。因此有点是 测试用例数量少，缺点是一定会有漏测。
引论：
Pairwise算法的核心理念
1、一组测试用例（每个用例有3个参数的值组成，如）；
2、如果这第一组测试用两两组合出的3种组合方式，对比原则：只会和其他组中第二个元素对比。。；
这三个元素分别出现在其余有效组位置相同的元素中，就可以认为这一组Case为多余Case，并进行删除。
名词解释：【有效组】表示未被删除的组和未被对比过的组。举例：第1,3组被删除，则第4组要对比的有效组为第2,5,6,7...18组。有效组这里踩过坑%》_《%
3、最终得到测试用例，就是结对算法计算出来的最优测试用例集合。
牛逼闪闪的学术证明
Pairwise是L. L. Thurstone(29 May1887 _ 30 September 1955)在1927年首先提出来的。他是美国的一位心理统计学家。Pairwise也正是基于数学统计和对传统的正交分析法进行优化后得到的产物。
Pairwise基于如下2个假设：
（1）每一个维度都是正交的，即每一个维度互相都没有交集。
（2）根据数学统计分析，73%的缺陷（单因子是35%，双因子是38%）是由单因子或2个因子相互作用产生的。19%的缺陷是由3个因子相互作用产生的。
因此，pairwise基于覆盖所有2因子的交互作用产生的用例集合性价比最高而产生的。
正文
一、思路
对一个测试场景如何从何从输入被测条件，到产出Pairwise测试用例，使用Python编程思路如下：
1、将allparams=进行笛卡尔积全组合处理，生成正则分析法产生的全量测试用例集合的一维数组（len=N）；
2、将全量测试用例中的每个测试用例，都进行两两组合的分解处理，生成与全量测试用例集合 长度相同的二维数组(一维 len=N）；
3、使用Python版Pairwise算法剔除无效测试用例，最终得到有效的结对测试用例集合；
代码第1,2函数利用Python自带数学计算库itertools编写，代码第3函数为本人死磕出来的代码。
二、直接上代码
# -*- coding: utf-8 -*-
from datetime import *
import random,os,copy,time
import logging
import itertools
’’’
#Author:Kuzaman
#Time:2017-07-18
’’’
class utils2 :
#1、笛卡尔积 对参数分组全排列
def product(self,tuple1):
newlist=
for x in eval(’itertools.product’+str(tuple(tuple1))):
newlist.append(x)
return newlist

#2、对笛卡尔积处理后的二维原始数据进行N配对处理，得到Pairwise计算之前的数据
def get_pairslist(self,lista):
pwlist =
for i in lista:
subtemplist =
for sublista in itertools.combinations(i, 2):
subtemplist.append(sublista)
pwlist.append(subtemplist)
return pwlist

#3、进行Pirwise算法计算
def pairwise(self,listb):
sublistlen = len(listb)
flag = *sublistlen
templistb = copy.deepcopy(listb)
delmenu =
holdmenu=
self.pprint (listb)
print (’--’*25)
for lb in listb:
for sublb in lb:
for k in templistb:
Xa = lb.index(sublb)
Ya = listb.index(lb)
if k != lb and sublb == k:
# print (sublb,’===》’ ,k,’相等了。。’)
flag = 1
break
else:
# print (sublb,’===》’ ,k,’不不不等了。。’)
flag = 0
# print (’下标%d,子元素 %s 双匹配对比结果flag:%s’%(listb.index(lb),lb,flag))
if 0 not in flag:
num = listb.index(lb)
delmenu.append(num)
templistb.remove(lb)
# print (’下标为%d行应删除,内容=%s,’%(num,lb))
# print (’delmenu:’,delmenu)
else:
num2 = listb.index(lb)
holdmenu.append(num2)
# print (’下标为%d行应保留,内容=%s,’%(num2,lb))
# print(’holdmenu=’,holdmenu)
# print (’***’*20)
print (’保留元素列表：%s
匹配重复元素列表：%s’%(holdmenu,delmenu))
return templistb
def pwresult(self,slist,delmenu):
for x in delmenu:
slist.remove(slist)
return slist
def pprint(self,list):
for i in list:
print (’line %d:’%(list.index(i)+1),i)
if __name__ == ’__main__’:
u2 = utils2()
allparams=
str = u2.product(allparams)
strpc = u2.get_pairslist(str)
finallist = u2.pairwise(strpc)
print(’最终保留测试用例个数：%d 个’%(len(finallist)))
u2.pprint(finallist)代码解读：
第三for循环代码39~48行，主要是垂直判断 待检测元素 与 相同位置的元素是否有相同的
第二for循环代码38~48行，把一组测试用例中的两两配对，从左至右分别和同位置的元素作对比
第一for循环代码37~48行，遍历每一组测试用例。
第50~58行代码，判断一组用例的两两配对在其他组同位置上从上到下都能找到相同元素，则将改无效Case从templistb中删除，保持templistb的有效性。
执行结果：
line 1: 《---第二个函数get_pairslist(self,lista)处理后的两两配对组合
line 2: 《---同第一行解释
line 3:
line 4:
line 5:
line 6:
line 7:
line 8:
line 9:
line 10:
line 11:
line 12:
line 13:
line 14:
line 15:
line 16:
line 17:
line 18: 《----同第一行解释
--------------------------------------------------
保留元素列表： 《----有效用例在数组中下标
匹配重复元素列表： 《----被剔除的无效测试用例在数组中下标
最终保留测试用例个数：9 个
line 1:
line 2:
line 3:
line 4:
line 5:
line 6:
line 7:
line 8:
line 9:
三、代码核心内容白话解释
pairwise(self,listb)函数包含3层for循环，先画一个二维数组：
i
listb.index(i)=0 :
listb.index(i)=1 :
listb.index(i) :
listb.index(i) :
listb.index(i) :
listb.index(i) :
listb.index(i) :
listb.index(i) :
listb.index(i) :
listb.index(i) :
listb.index(i)=n : 从上之下与有效组 templistb通位置元素的对比。
1、第n行的i元素对比（第三for），如果有相等的，记录一个标识 如 flag1=True，如果没有相等的记录falg1=False；
2、直到第二for中的i，所有flag=True则该行为无效用例
3、第一for遍历全部组合，最终得到保留下来的有效templistb
见图：
完结篇
以上是自己编写的pairwise的全部内容，此算法共耗时3天：
第一天在确定这究竟是什么算法，看了很多学术文献，看不懂；
第二天开始写程序，for的嵌套循环设计耽误很久；
第三天程序成型，有执行结果，发现与参考文章结论不同，随后再仔细研读参考文章，发现掉坑里了。重新推翻代码按照正确思路，用1个小时完成最终结果。
本人做测试的，还不是专业的测试开发，写代码比较费劲，真正应了设计占70%，编码占30%的理。如果像基础在差点，逻辑在乱点，就只能用时间堆了。

python两个图片的坐标判断图片是否平移

对于判断两个图片是否平移，可以通过比较图片中特定点的坐标来进行判断。如果两个图片平移，则对应的特定点在两张图片中的坐标应该保持不变。
具体步骤如下：
1. 首先，选择两张图片中具有明显特征的点作为参考点，可以选择角点、边缘交点或者其他具有独特性的点。
2. 然后，通过图像处理技术，如特征提取算法（如SIFT、SURF等）或者边缘检测算法，获取到这些参考点在两张图片中的坐标。
3. 对比两张图片中对应点的坐标，如果这些点的坐标之间的差异非常小（可以通过设置一个阈值来判断），则可以认为两张图片是平移的。
原因解释：
当两个图片进行平移时，图片中的特征点的相对位置关系是保持不变的。因此，通过比较两张图片中特定点的坐标，可以判断图片是否平移。
拓展内容：
除了判断平移，我们还可以通过比较特定点的坐标来判断图片是否发生了旋转、缩放等变换。对于旋转和缩放的判断，可以通过计算特征点的旋转角度和尺度变化来进行判断。
此外，还可以利用更高级的图像处理算法，如光流法（optical flow）等，来实现更精确的平移判断。光流法可以通过分析图像中像素的运动来估计图像之间的平移关系。
总之，通过比较特定点的坐标，我们可以判断图片是否发生了平移，而且可以利用图像处理算法来实现更精确的判断，并可以应用于其他类型的图像变换的判断。