Jove's Blog

I love what I do

发表于 更新于

前面一篇文章讲过了关于验证码的一些简单的识别技术（验证码识别入门）

其中一个很大的局限性，就是我的字符分割是根据我事先在图片上量取的尺寸，换句话说，加入同样的代码换个图片来源就会出错，更不谈位置不规则的验证码。

后来找了一些资料，实现了智能切割字符，可以实现自动识别字符的位置，对位置不规则的尤其有效。下面一点点的来分析这个实现。

比如这个验证码：
1

可能看不是很清楚，简单二值去噪点，然后放大后：
2

各个字符的位置都是不确定的，但是我们来分析下横轴上的像素点分布，利用一段python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
img=Image.open(dir+'3.jpg')
#初始化一个数组，统计横轴上每处的像素点数
flagx=[0 for x in range(img.size[0])]
pix=img.load()
#横坐标上的像素分布
for x in range(img.size[0]):
    for y in range(img.size[1]):
	if pix[x,y][0]<90:
	    flagx[x]+=1
print flagx


```>[0, 0, 0, 0, 0, 1, 1, 3, 3, 4, 6, 6, 4, 5, 5, 5, 5, 4, 7, 7, 17, 24, 25, 25, 20, 13, 6, 2, 0, 1, 1, 3, 12, 21, 12, 9, 8, 8, 7, 7, 7, 7, 8, 9, 9, 10, 10, 19, 21, 6, 0, 0, 0, 0, 6, 9, 15, 14, 8, 3, 5, 9, 13, 15, 13, 8, 0, 0, 0, 0, 3, 4, 4, 5, 5, 7, 17, 19, 19, 18, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

也就是从左到右每列上的像素点分别为0,0.......那么我们关注两个地方分别是0->n和n->0的地方，比如从左往右发现第5个开始不是0,28开始又变成0，我们很容易分析地一个字母的横坐标为5-28,然后用同样的方法，针对5-28的横坐标在纵坐标上取出像素分布：


>[0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 4, 5, 6, 7, 8, 7, 7, 7, 7, 7, 7, 11, 15, 11, 8, 8, 9, 11, 11, 10, 7, 9, 6, 3, 0, 0, 0, 0, 0, 0, 0]

这样可以分析第一个字母的纵坐标为8-34。代码实现是这样的：

```python
for i in range(img.size[0]):
    if flagx[i]>0 and flagx[i-1]<=0:
	tmp=i#记录0->n的坐标
    if flagx[i]>0 and flagx[i+1]<=0:
	#完成一个字符的横坐标扫描，针对这段用同样的方法扫描纵坐标
	flagy=[0 for x in range(img.size[1])]
	for y in range(img.size[1]):
	    for x in range(i+1)[tmp:]:
	        if pix[x,y][0]<90:
	            flagy[y]+=1
	#用flagy记录纵坐标像素分布
	for j in range(img.size[1]):
	    if flagy[j]>0 and flagy[j-1]<=0:
	        ttmp=j#记录0->n的点
	    if flagy[j]>0 and flagy[j+1]<=0:
	        result.append([tmp,i,ttmp+1,j+1])
print result


[[5, 28, 8, 34], [29, 50, 3, 26], [54, 66, 11, 29], [70, 83, 12, 31]]

这就是四个字符的坐标，然后把这些坐标来切割图像字符就能很好的抠出来了，我的结果是这样的

3

发表于 更新于

验证码识别是一个有意思的项目，很多时候多用于非法抓取，批量处理之类的，给网站运营者造成了一定的损失，这里我们研究验证码识别单纯研究图像识别技术。

文章主要利用python代码演示，就算你不懂，相信python简洁的自然语言话的语法也能让你理解，图像处理主要用PIL库

先来看看一个验证码，来自http://www.ruanko.com/validateImage.jsp

1

利用一些图像处理或者图像查看软件来看看，验证码尺寸为60×20每个字母的尺寸为13×9而且验证码位置相对固定，这就是一个很适合我们初学者学习的一个例子，对于字体的分割相对容易一点

我们批量下载50个验证码来取字库，python提供方便的下载功能，脚本如下

1
2
3
4
5
6
7
import urllib
for i in range(50):
    url = 'http://www.ruanko.com/validateImage.jsp'
    print "download", i
    file("./code/%04d.jpg" % i, "wb").write(urllib.urlopen(url).read())


然后适当处理图片将其二值化，这里可以利用我前面一篇文章里面的算法（python图像处理之二值去噪）代码不罗列了，处理之后会得到这样的效果

2

然后分割字符，这里利用PIL中图像分割的一块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import os ,Image
j = 1
dir="./code/"
for f in os.listdir(dir):
    if f.endswith(".jpg"):
	img = Image.open(dir+f)
	for i in range(4):  
	    x = 7 + i*13  
	    y = 3  
	    img.crop((x, y, x+9, y+13)).save("font/%d.jpg" % j)  
	    print "j=",j  
	    j += 1


3

手工从其中选出比较完整的一套字模，如图

4

这样我们一个字库就完成了，在来谈谈匹配算法，相似度匹配，我们马上想法哦了异或算法，即把不同的去出来，然后进行一个计数，不同的点越少，相似读越高，例如这样一个图

5

进行异或运算,得到

6

在PIL中实现如下

1
2
3
4
5
6
for yi in range(13):
    for xi in range(9):
	if mod[1].getpixel((xi, yi)) != target.getpixel((xi, yi)):
	    diffs += 1


总结一下前面的步骤，我们来看看完整代码

#!/usr/bin/env python
# −*− coding: UTF−8 −*−
import os, Image

def binary(f):
    img = Image.open(f)
    #img = img.convert('1')
    pixdata = img.load()
    for y in xrange(img.size[1]):
    for x in xrange(img.size[0]):
        if pixdata[x, y][0] < 90:
            pixdata[x, y] = (0, 0, 0, 255)
    for y in xrange(img.size[1]):
    for x in xrange(img.size[0]):
        if pixdata[x, y][1] < 136:
            pixdata[x, y] = (0, 0, 0, 255)
    for y in xrange(img.size[1]):
    for x in xrange(img.size[0]):
        if pixdata[x, y][2] > 0:
            pixdata[x, y] = (255, 255, 255, 255)
    return img


def division(img):
    font=[]
    for i in range(4):
    x=7+i*13
    y=3
    font.append(img.crop((x,y,x+9,y+13)))
    return font

def recognize(img):
    fontMods = []
    for i in range(10):
    fontMods.append((str(i), Image.open("./num/%d.bmp" % i)))
    result=""
    font=division(img)
    for i in font:
    target=i
    points = []
    for mod in fontMods:
        diffs = 0
        for yi in range(13):
            for xi in range(9):
                if mod[1].getpixel((xi, yi)) != target.getpixel((xi, yi)):
                    diffs += 1
        points.append((diffs, mod[0]))
    points.sort()
    result += points[0][1]
    return result

if __name__ == '__main__':
    codedir="./code/"
    for imgfile in os.listdir(codedir):
    if imgfile.endswith(".jpg"):
        dir="./result/"
        img=binary(codedir+imgfile)
        num=recognize(img)
        dir += (num+".png")
        print "save to", dir
        img.save(dir)


```![7](https://jovesky-wordpress.stor.sinaapp.com/uploads/2012/10/DeepinScrot-5424.png)

发表于 更新于

好久没有写什么文章了，最近一直忙于学习各种知识，没有一个整体的知识体系也就没有贸然写文章，其实我想慢慢提高文章质量，话不多说，今天说说我验证码识别的第一步处理，也就是验证码的二值化和去噪点

我们先来看看一张简单的验证码，这张也是我一直在使用的一个例子（懒得找。。。）

2

下面我使用的python-image库简称PIL库，下面一个算法由一个网友提供：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from PIL import Image

img = Image.open('tmp.jpg') # 读入图片
img = img.convert("RGBA")

pixdata = img.load()

#二值化

for y in xrange(img.size[1]):
    for x in xrange(img.size[0]):
	if pixdata[x, y][0] < 90:
	    pixdata[x, y] = (0, 0, 0, 255)

for y in xrange(img.size[1]):
    for x in xrange(img.size[0]):
	if pixdata[x, y][1] < 136:
	    pixdata[x, y] = (0, 0, 0, 255)

for y in xrange(img.size[1]):
    for x in xrange(img.size[0]):
	if pixdata[x, y][2] > 0:
	    pixdata[x, y] = (255, 255, 255, 255)

img.save("input-black.gif", "GIF")

#放大图像 方便识别
im_orig = Image.open('input-black.gif')
big = im_orig.resize((1000, 500), Image.NEAREST)



2

效果还不错

PS：最近烦恼软件界面的设计

发表于 更新于

一直觉得linux上网没有windows那么快，网上搜索了下，推介通过软件缓存dns解析数据从而加快dns解析，下面我选择了pdnsd来完成这艰巨的使命！

1:安装pdnsd

sudo pacman -S pdnsd

2:配置默认配置文件

sudo cp /etc/pdnsd.conf.sample /etc/pdnsd.conf

打开/etc/pdnsd.conf

server段修改为

server {
    label= "myisp";
    ip = 114.114.114.114, 8.8.8.8;  # Put your ISP's DNS-server address(es) here.
    timeout=4;         # Server timeout; this may be much shorter
    interval=30m;      # Check every 30 minutes.
    purge_cache=off;   # Keep stale cache entries in case the ISP's
}


```还有一点可选

>query_method=tcp_only;<

这可以避免dns污染，不过如果你写的是google的dns也就没必要担心

global段修改为

>min_ttl=96h;  
>max_ttl=1w;  

这里配置的是dns缓存保存的时间!

3：开机启动服务
打开rc.conf在networkmanage后面添加pdnsd

PS：理论上这样就可以使用了，在配置网络的时候选则dns 127.0.0.1即可！
我使用过程中重启就无法解析，重新启动一次pdnsd就可以，不知道这个是不是特例，后再安装networkmanager-dispatcher-pdnsd解决的

发表于 更新于

好久没有更新博客了，感觉自己的知识体系停滞了好久，一方面是为了考试复习在，另一方面是自己走到了大学生的一个犹豫的时期，犹豫走向IT事业的那个方向。

自从决定不从事android后，自己的视野有一定的提升，当然人都是逼出来的，我有时也质疑是否太过于松懈，其实linux很好，为什么那么多人看不到呢，其实我现在可以提议去带个linux小组搞开发，但是实在没有在学校找到志同道合的人，去年学习了python，每年学些新东西，我决定开始学习ruby，了解点前端知识，因为我的只是体系中web开发的知识还比较缺乏，借这个机会来了解点吧！

也许有人我以后会走上rails的路，也许吧，自己的路老是不由得自己，但是有一点没错，前沿的技术，融洽的学习氛围，这些都是我喜欢的，还真像有些人说的，学多了，就觉得自己学少了。我希望的是自己做出来的东西能被大家看到，认可，小小的赚下成就感！

发表于 更新于

题目链接：http://poj.org/problem?id=1627

字符串暴力匹配，根据题意，我们为每个单词加上权，然后输出后面给出的一句话的总权值，

没什么解法，利用结构体去保存每个单词和对应的权值，然后依次去匹配就可以了，居然可以0MS，可见他的测试数据一般，不复杂，不然这样的傻办法应该会花很多时间的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*Problem: 2403		User: awq123
**Memory: 252K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

struct NODE
{
    char str[20];
    long int num;
}node[1005];

int main()
{
    int i,n,m;
    long int sum;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
	cin>>node[i].str>>node[i].num;
    }
    while(m--)
    {
	sum=0;
	char tmp[20];
	while(cin>>tmp)
	{
	    if(tmp[0]=='.')
	    {
	        cout<<sum<<endl;
	        break;
	    }
	    for(i=1;i<=n;i++)
	    {
	        if(strcmp(tmp,node[i].str)==0)
	            sum+=node[i].num;
	    }
	}
    }

}

发表于 更新于

题目链接：http://poj.org/problem?id=1887

最长下降序列问题。和最长上升序列类似，有多种方法，我这里用动态规划解题，动态转移方程如下

dp[i]=max(dp[j])+1,(j∈[1, i-1]);

这里，思路就是用dp数组，记录到每一位的最长下降序列，然后输出其中最大的，详细看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*Problem: 1887		User: awq123
**Memory: 288K		Time: 47MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    int tmp,num[5005],dp[5005],n=1;
    while(cin>>tmp)
    {
	if(tmp==-1)
	    break;
	num[1]=tmp;
	int i,j,count=2;
	while(1)
	{
	    cin>>num[count];
	    if(num[count]==-1)
	        break;
	    count++;
	}
	int max=0;
	for(i=1;i<count;i++)
	{
	    dp[i]=1;
	    for(j=1;j<i;j++)
	    {
	        if(num[i]<num[j]&&dp;[i]<dp[j]+1)
	            dp[i]=dp[j]+1;
	    }
	    if(dp[i]>max)
	        max=dp[i];
	}
	cout<<"Test #"<<n<<":"<<endl;
	cout<<"  maximum possible interceptions: "<<max<<endl<<endl;
	n++;
    }
}

发表于 更新于

题目链接：http://poj.org/problem?id=1621

不解释题意了，看了示例输出就知道了，给出输入的四句话的字母分布图

我利用一个num数组统计每个字母出现的次数，然后画图，这题主要有几个问题：
1是读入字符串的时候用cin，半天num数组都有问题，后来调试发现cin不能读入带空格的字符串，果断换回gets，
2是输出*号的时候那个

if(j%2==1&&(i>max-num[(j-1)/2]))

中的>写成了>=，不过这个错一会就发现了。

总的来说，这个题不难，但是考基本功，以及细心，不要被这样一个简单的题吓到了！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*Problem: 2136		User: awq123
**Memory: 172K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    char str[80];
    int i,j,num[26];
    //初始化数组
    for(i=0;i<26;i++)
	num[i]=0;
    //读入字符串
    for(i=0;i<4;i++)
    {
	gets(str);
	int len=strlen(str);
	//逐个分析，利用数组标记
	for(j=0;j<len;j++)
	{
	    if(str[j]>='A'&&str;[j]<='Z')
	        num[str[j]-'A']++;
	}
    }
    int max=0;
	//找出最大值，便于后面行数决定
    for(i=0;i<26;i++)
	if(num[i]>max)
	    max=num[i];
    //输出*部分
    for(i=1;i<=max;i++)
    {
	for(j=1;j<=51;j++)
	{
			//如果是奇数列而且到了计数部分
	    if(j%2==1&&(i>max-num[(j-1)/2]))
	        cout<<"*";
	    else
	        cout<<" ";
	}
	cout<<endl;
    }
    //输出下面一行字母
    for(i=1;i<=51;i++)
	if(i%2==1)
	    cout<<char('A'+(i-1)/2);
	else
	    cout<<" ";
}

发表于 更新于

题目链接：http://poj.org/problem?id=1852

这个题有点弯转，解释下题意，在一个长度为len的木条上分布着num个蚂蚁，他们可以以相同的速度向任意两个方向走，每碰到一个蚂蚁，反向移动，问蚂蚁全部走完，所需要的最短时间和最长时间，之前被转向迷惑了，其实速度相同，蚂蚁也相同，两个同时转向相当与穿过去了，那么我们只要考虑每个蚂蚁，离开木条的时间就可以了，这里我将近路径和min比较，远路径和max比较，然后输出！

思路比较简单，但是这题启发我们，分析题目的时候应该主要要排除一些干扰条件，脑筋要会转弯！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*Problem: 1852		User: awq123
**Memory: 220K		Time: 625MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n,len,num,min,max,tmp;
    cin>>n;
    while(n--)
    {
	cin>>len>>num;
	max=0,min=0;
	while(num--)
	{
	    cin>>tmp;
	    if(tmp>len-tmp)
	        tmp=len-tmp;
	    if(tmp>min)
	        min=tmp;
	    if(len-tmp>max)
	        max=len-tmp;
	}
	cout<<min<<" "<<max<<endl;
    }
}

发表于 更新于

题目链接：http://poj.org/problem?id=2636

水题，问一堆插座相互相接后有多少个插孔可以用

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*Problem: 2636		User: awq123
**Memory: 252K		Time: 0MS
**Language: C++		Result: Accepted
/*
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n;
	cin>>n;
	while(n--)
	{
		int m;
		cin>>m;
		int sum=1-m;
		while(m--)
		{
			int t;
			cin>>t;
			sum+=t;
		}
		cout<<sum<<endl;
	}
}