{"action":"created","issue":{"url":"https://api.github.com/repos/100steps/Blogs/issues/43","repository_url":"https://api.github.com/repos/100steps/Blogs","labels_url":"https://api.github.com/repos/100steps/Blogs/issues/43/labels{/name}","comments_url":"https://api.github.com/repos/100steps/Blogs/issues/43/comments","events_url":"https://api.github.com/repos/100steps/Blogs/issues/43/events","html_url":"https://github.com/100steps/Blogs/issues/43","id":165979958,"number":43,"title":"验证码识别","user":{"login":"SunDoge","id":16167062,"avatar_url":"https://avatars.githubusercontent.com/u/16167062?v=3","gravatar_id":"","url":"https://api.github.com/users/SunDoge","html_url":"https://github.com/SunDoge","followers_url":"https://api.github.com/users/SunDoge/followers","following_url":"https://api.github.com/users/SunDoge/following{/other_user}","gists_url":"https://api.github.com/users/SunDoge/gists{/gist_id}","starred_url":"https://api.github.com/users/SunDoge/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SunDoge/subscriptions","organizations_url":"https://api.github.com/users/SunDoge/orgs","repos_url":"https://api.github.com/users/SunDoge/repos","events_url":"https://api.github.com/users/SunDoge/events{/privacy}","received_events_url":"https://api.github.com/users/SunDoge/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":8,"created_at":"2016-07-17T14:51:57Z","updated_at":"2016-07-23T03:35:13Z","closed_at":null,"body":"这个锅本来是若花的，然而不知不觉就甩我背上了。你说我一个学电气的，怎么就跑来写验证码识别了呢。波小跟我说，组织上决定了，由我来写这个。我当时就念了两句代码，print \"苟....\r\n\r\n言归正传，验证码识别主要分两部分：图像分割和识别。其中，分割验证码是最麻烦的，因为基本没有一劳永逸的分割方法。  \r\n\r\n本文基于[opencv2.4](http://opencv.org/)，有兴趣的可以去了解一下。  \r\n\r\n## 图像分割  \r\n我们先来看看教务的验证码。  \r\n \r\n![image](https://cloud.githubusercontent.com/assets/16167062/16900910/a6c5e884-4c65-11e6-9bf7-a4bb64ccb9e4.png)   \r\n \r\n可以看到，是个72x27像素的矩形，而且每个字符的颜色都是一样的，所以只要提取那个颜色的像素就可以分离出字符了。听起来很简单是不是？ \r\n \r\n首先我要表扬一下若花，因为若花的项目虽然tj了，里面用到的分割算法确是非常赞的。那么我们先来看一下若花是怎样做的。   \r\n\r\n![image](http://static.wooyun.org/20131004/2013100410270648577.gif)  \r\n\r\n这个GIF所演示的就大致是若花的算法了，若花当时对我说的是“染色”，也就是[油漆桶算法（又叫种子填充算法，Floodfill）](http://drops.wooyun.org/tips/141)。说实话看了若花的代码，我深有感触。首先，若花自己一个人写了前端和后台，前端用了npm、bootstrap，还用了ajax，要是让我来写。。。。。。估计又要在群上喊耀宗了。其次是算法的实现都是若花都是用php写的，php在这方面有点先天弱势，但是若花还是写出来了，所以要给若花点个赞。 \r\n   \r\n但是说了这么多，我最终还是没有采用这个算法。为什么呢？  \r\n  \r\n因为这个算法有个致命的问题，对于ij这样带有非联通区域的字母，会把上面的点漏掉。。。。。。这就很尴尬了。我一开始想，能不能先给出每个字母的最小区间，再对区间内的字符颜色的像素染色，这样就有很大几率可以把点也染上，因为写过原生的php生成验证码的代码，知道字符虽然有旋转和位移，一开始的位置还是有规律的。如果想分离出单个字符，可以直接使用RGB中R的通道，第一个字符就+1，第二个+2，第三个+4，第四个+8，这样数一下R的大小就可以把字符分开，还可以知道哪些字符相连，然后相连字符再重新分隔。  \r\n\r\n但是后来我又放弃了，因为我<del>比若花还要懒</del>找到了更好的方法。之前的方案要统计一定数量的验证码来确定每个字符的最小染色起始区间，还要把php写的染色算法改写成python。  \r\n所以最后，我使用了opencv自带的k-means算法。这个算法的好处在于<del>有现成的函数可以偷懒</del>不但可以分割提取字符，还可以找出每个字符的中心点。中心点可是个好东西，不但可以确定字符的次序，还可以对每个字符标准化，方便后续的特征提取。  \r\n \r\n![image](https://cloud.githubusercontent.com/assets/16167062/16901219/8243f9ba-4c6f-11e6-8278-ab7df883d866.png)  \r\n\r\n说到特征提取，若花好像就是卡在这一步。他的分类器好像都基本写完了，而且是php写的，说实话真的很厉害。。。  \r\n  \r\n我这里使用了ocr例程里的方向梯度直方图Histogram of Oriented Gradients （HOG）作为特征向量。在计算 HOG 前还要使用图片的二阶矩对其进行抗扭斜（deskew）处理，然后把每个字符分成4块，我这里把27x27的字符分成了14x14的小方块，然后计算图像 X 方向和 Y 方向的 Sobel 导数（这个不是很懂，如果有人知道请告诉我）。然后计算得到每个像素的梯度的方向和大小。把这个梯度转换成 16 位的整数。将图像分为 4 个小的方块，对每一个小方块计算它们的朝向直方图（16 个 bin），使用梯度的大小做权重。这样每一个小方块都会得到一个含有 16 个成员的向量。4 个小方块的 4 个向量就组成了这个图像的特征向量（包含 64 个成员）。这就是我们要训练数据的特征向量。  \r\n\r\n## 图像识别  \r\n这里我用在knn和svm中选用了svm。knn每次识别都要遍历一遍现有数据，随着数据的增加识别速度会下降，而svm就没有这个问题。svm有很多相关资料可以查，比如[前面给的链接](http://drops.wooyun.org/tips/141)，这里就不细说。而且opencv自带的svm并不是最好的，3.0版还有bug，无法导入训练好的模型:(   \r\n\r\n![image](https://cloud.githubusercontent.com/assets/16167062/16901244/82e7cd00-4c70-11e6-8971-3cb58fe0657e.png)\r\n\r\n识别速度还算令人满意。\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/100steps/Blogs/issues/comments/234696678","html_url":"https://github.com/100steps/Blogs/issues/43#issuecomment-234696678","issue_url":"https://api.github.com/repos/100steps/Blogs/issues/43","id":234696678,"user":{"login":"SunDoge","id":16167062,"avatar_url":"https://avatars.githubusercontent.com/u/16167062?v=3","gravatar_id":"","url":"https://api.github.com/users/SunDoge","html_url":"https://github.com/SunDoge","followers_url":"https://api.github.com/users/SunDoge/followers","following_url":"https://api.github.com/users/SunDoge/following{/other_user}","gists_url":"https://api.github.com/users/SunDoge/gists{/gist_id}","starred_url":"https://api.github.com/users/SunDoge/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SunDoge/subscriptions","organizations_url":"https://api.github.com/users/SunDoge/orgs","repos_url":"https://api.github.com/users/SunDoge/repos","events_url":"https://api.github.com/users/SunDoge/events{/privacy}","received_events_url":"https://api.github.com/users/SunDoge/received_events","type":"User","site_admin":false},"created_at":"2016-07-23T03:35:13Z","updated_at":"2016-07-23T03:35:13Z","body":"辨别旋转角度很麻烦的，我也写不出来，而且教务验证码的像素太低，旋转的时候可能很多像素点就没了。。。"}}
{"actor":{"display_login":"SunDoge"}}