闲暇之时偶然翻出了一个几年前用Java写的预约课程工具。看这创建时间,尘土相当后了。
* @version $$Id: Main, v 0.1 2018/5/9 12:49
在看到她的那一刻,瞬间勾起了有些遗憾的记忆。说起这位“老友”,当时还真帮了我的大忙。
话说是因为要在网站上预约课程。预约课程的流程与在电商平台购物有些相似,登录,根据日期查询当天是否有可预约的课程,如果有则从列表中找到合适的时间段,最后预订。当操作了几次之后,就觉得很麻烦。程序员最怕这样的麻烦!如果别人也觉得上述情况麻烦,那Ta只能忍着继续操作,但作为程序员可不会惯着它。随即,F12走起。综上,我这位“老友”便诞生了,而且之后还给我带来了意外惊喜。
这个预约课程工具本身很简单,用java.net包下与HTTP相关的类便很快搞定了登录和约课的功能,但这两个功能在操作时都需要将图片验证码中的字符一并提交给服务器。完成代码后,之前需要在页面上完成的输入,则改为在代码启动后的控制台进行输入。那图片验证码是怎么在控制台输出的?先来看看验证码图片的样子。
这是放大了一千多倍的验证码图片,就是这样的。说白了,上面的每个像素点也只是不同的数字而已,数值越大则颜色越深。那么上面这个图在经过代码处理后,在控制台打印出来是这样的。
0
0 0
0
0
0 0
0
0000 000 000000000 000
0000000 000000000 000
00 0 0000
0 00 00 00 0 00 00 0
0 00 0 00000 0 0 0 00
0 00 00 00 0000 0 00 00 0
0 0 00 00 00 000000
0 0000 000 00 00000000
0000 000 00 00 00
000 00 00 000 00
00 00 000 00 000
0
0
怎么样,经过处理后打印出来还是很好辨识的吧。将用人肉辨识出来的字符输入到控制台上,然后直接预约课程即可,省去了登录,查询,浏览,选择这些过程,直接就可以预约自己指定时间的课程,如果在自己指定的时间没有可供预约的课程,则程序给出相应提示,如果预约成功,则返回预约成功课程的时间地点等信息。在测试代码的过程中,还给了我前面提到的意外惊喜————程序可以预约在网站上查询不到的课程。这个意外收获直接促使了我提前完成所有课程,简直有点降维打击的感觉,如同菜还没上桌,你已经在厨房吃饱了。不过作为程序员要注意,这虽然算不上是一个bug,但肯定算是一个缺陷,即前台与后台的没有统一。
从这位“老友”第一次为我成功预约课程后,我就一直想着怎么再把她捯饬的漂亮些————把人肉识别验证码变成自动识别验证码,这样就又可以省去敲四下键盘的巨大工作量了。为此,当时还特意买了一本《模式识别》。之所以买这本书而不是关于机器学习的,是因为当时想要用数学模型将每个字符描述出来,而且我当时感觉这个数学模型还没办法通过机器学习得到,得自己通过对字符规律进行总结后给出。其实《模式识别》中的内容与机器学习的内容有很多相似之处。不过后来随着课程的完毕,自动识别验证码的想法也就被搁置了,直到今天她又重见天日。如今某家要誓补当年之憾。
前段时间抽空用Java弥补了下这个当年的遗憾,总的来说识别效果还不错。具体的识别方法也是在下面将要介绍的实现过程中几经调整。
之所以人可以识别图片中的那些字符,是因为我们认识图片中的每一个字符,但如果让一个未识字的幼儿来指出这些字符是什么,那么他肯定是做不到的。如果想让他辨识字符,那就要先告诉他这些字符是什么。这时,计算机就是这个尚未识字的幼儿。首先要做的就是让计算机认识并记住它要识别的每个字符。这些字符包括0~9,a~z,A~Z。可以用数学模型或记录有效像素两种方法来让计算机认识它将要识别的字符。用数学模型给出每个字符的描述,也就是说要写出六十多个方程组,这工作量实在太可观了。虽然数学模型可以节省空间,并在识别效果不准时可对其进行参数调整,不过这种方法会出现与机器学习中的过拟合类似的问题,也就是对一个字符的某个样子识别准确了,但同一个字符的其他样子的识别能力就降低了,还可能把其他字符识别成这个字符,属于按下葫芦起了瓢,还是算了吧。那就只能用记录描述字符的有效像素的方法来让计算机认识每个字符了。这个方法的缺点是要记录每个字符的所有可能的样子,如果有一个样子没记录,那么就识别不出来或是识别成其他字符。不过也有优点,那就是简单,只要发现了未识别的字符,就将该字符的有效像素描述记录下来,并给与标记即可。总结就是,数学模型复杂但灵活,像素描述简单但死板。事儿就是这么个事儿,情况就是这么个情况。
用记录字符有效像素这种方法则需要在识别前保存同一个字符的所有可能的样子,这也是我评估了两种方法的工作量之后的选择。文中提到的有效像素指的是表示出字符轮廓的像素。于是我用文本文件开始记录每个字符的出现过的样子。看几个例子。
0 00 000 00 000 00 0 000 00 000
0 0000 00 00 0000 00 0 0000 00 0 0000 0
00 0000 000 000 0000 00 00 0000 00 00 0 00 0
00 0000 00 00 0000 00 00 0000 00 00 0000 00
00 00 0 00 00 0 0 00 00 00 0 00 00 00 00 00
00000 00 00 00000 00 0 00 0 00 00 00 0 00 00
0000 0000 0000 0000 0000 00 00 0000 00 00
0000 0000 0000 000 0000 0000 0000 000
0000 000 0000 000 0000 000 0000 000
000 000 000 000 000 000 000 000
00 000 00 00 00 000 00 000
这是大写W在图片验证码中可能的样子,当然这四个有效像素描述分别位于文件名中包含大写W的四个文件中,像下图这样。
用这样的方法就需要在发现未能识别的字符时,将这个字符的有效像素描述保存为上图中的文件。缺点是,随着文件的增多,识别速度会变慢,而且会造成误识别为其他字符的情况增多。所以上述文件并不是越多越好。
有了上面这些文件,就距离让计算机识别出图片中的验证码进了一步。此时计算机已经知道了每个字符在验证码图片中的样子了。接下来就可以开始进行比较了。在比较有效像素的过程中,同时计算与字符集中每个字符的相似度,并返回相似度最高的那个字符对应的文件名,而从也就识别出了图片中的字符。
上面的txt文件中保存的是单个字符的有效像素描述,但验证码图片上的那些字符可是连接一起的。所以在与字符描述集中的字符进行比较前先得将图片中的字符切分成一个一个的,然后再进行比较。这也是最常规的识别手段。现在,真正的重点来了————从图片中切分出可以识别的字符。
从前面的图片可以看出,验证码图片上的字符间的像素值显然是高于用于显示字符轮廓像素的值的。因此,这自然的就成为了字符的切分标准。仿佛又接近了目标一步。然而,现实总是残酷的,如果能仅凭这个标准就可将所有图片都准确的切分成四个可供识别的图片那可就太美好了。来看下这张图片。
K和W还好说,可是9和 j 的下方存在2个有效像素在同一X轴上,所以用有效像素个数为0的标准来拆分上面这个图时,只能切分出3个字符,即K,W,和9j,9和j是连接在一起的。如果这个切分标准放宽些,比如当X轴上有一个,两个或三个有效字符也允许切分,那确实可以将9和 j 切分开,但对于其他图片就有可能出现误切,比如下面这个两个图。
如果以小于等于两个或三个有效像素的标准来切分上面两个图的话,则前一个图中的L和后一个图中的 m 将被拆分成两个以上且无法识别或是被识别成其他字符的部分。因此,要是切分后得到的字符少于4个,就不宜再用有效像素法进行处理了,必须换个思路。
起初,我采用的是当切分出的字符少于4个时,就找出其中最宽的那个,然后放宽切分条件再次进行切分。这中方法有一定的效果,但问题是最宽的那部分并非一定是由多个字符组成的。比如,三个小写 j 也没有一个大写的W宽,还是会出现误切分。那就再用另一种办法试试,从所有切分出的部分中找出在X轴上有效像素最少的那段,然后以这个X轴为界再次进行切分。只能说也有一定效果,但当识别出了一个图片后,对其他图片的识别能力便减弱了,这显然不行。我试着用这两种方法分别再次处理无法切分出4个字符的图片。因为这里要得到两种方法怎么交替结合运行才能给出最高相似度,看到“最”这个字,一下想到了用动态规划算法试试。随后结合动态规划,将上述两种方法结合了起来,效果还是不理想,而且代码也越来越复杂。不行,还得换思路。
事实证明,当没有好的思路的时候,先暂时放下,干点别的事,也许灵感大爷自己就找上门来了。这不,骑车出去浪一圈,打会儿篮球,思路就有了。不是有个KMP算法吗,可以借鉴一下。既然更换切分标准会误伤友军,那干脆就不切分了,反正我现在已经有了一堆字符描述文件,直接比对不就可以了。
具体做法就是从候选字符集中取一个字符描述,然后根据这个字符描述的宽度,从图片右侧开始比对与该宽度相等的范围内所有像素,比对完之后计算出一个相似度,然后再取下一个字符描述重复这个过程,直到比对完全部字符集,随后便得到了最高相似度的那个字符描述,接着缩小图片范围,重复上述全部过程,直到图片范围缩小到0。核心代码如下。
private static final float SIMILARITY_THRESHOLD = 0.9f;
private static Set selectMaxSimilarityChar(CharRange charRange, int height) {
//从图片右侧开始依次比对字符集所有字符,取相似度最高者
Map map = new HashMap<>();
CharRange recognizedCharRange = new CharRange(charRange.startX, charRange.endX);
while (recognizedCharRange.startX >= charRange.startX) {
MatchedChar bestMatchedChar = null, matchedChar = null, lastMc = new MatchedChar(null, 0, null);
for (Map.Entry entry : CharSetLoader.getCharDict().entrySet()) {
int startX = recognizedCharRange.endX - entry.getKey()[0].length;
if (startX < 0) {
continue;
}
if (!isValidPixelCountEnough(startX, recognizedCharRange.endX, height)) {
continue;
}
matchedChar = getMatchedChar(new CharRange(startX, recognizedCharRange.endX));
if (matchedChar.similarity >= SIMILARITY_THRESHOLD) {
if (lastMc.similarity > matchedChar.similarity) {
bestMatchedChar = lastMc;
} else {
bestMatchedChar = matchedChar;
}
}
}
if (bestMatchedChar == null) {
recognizedCharRange.startX--;
continue;
}
recognizedCharRange.endX = bestMatchedChar.charRange.startX - 1;
recognizedCharRange.startX = bestMatchedChar.charRange.startX - 2;
map.put(bestMatchedChar.charRange, bestMatchedChar);
}
return new TreeSet<>(map.values());
}
private static MatchedChar getMatchedChar(CharRange charRange) {
MatchedChar matchedChar = new MatchedChar(null, 0f, charRange);
for (Map.Entry candidateChar : CharSetLoader.getCharDict().entrySet()) {
int candidateCharWidth = candidateChar.getKey()[0].length, recognizeCharWidth = charRange.endX - charRange.startX + 1;
//过滤掉宽度不一致的字符
if (recognizeCharWidth != candidateCharWidth) {
continue;
}
//以候选字符的矩阵进行比较,可以得到很高的相似度,但对于有重叠情况的字符有误判,如 q 和 o
float bingo = getBingoByCandidateChar(charRange, candidateChar);
float similarity = bingo / (candidateChar.getKey().length * candidateChar.getKey()[0].length);
if (similarity > matchedChar.similarity) {
matchedChar.aChar = candidateChar.getValue();
matchedChar.similarity = similarity;
}
}
return matchedChar;
}
这个方法的效果要优于之前的两个方法,不过也存在误判,这取决于字符描述集中不同字符的相似程度,这也就是之前所说的,字符描述集合中的文件不易太多的原因,就像布隆过滤器一样,随着数据的增多,误判率也会随之增长。
未识别文件:[{文件名:DBYc | 识别结果:DEYc} {文件名:ewfr | 识别结果:Efr} {文件名:jwwk | 识别结果:JWk} {文件名:l4am | 识别结果:AM} {文件名:phcw | 识别结果:HCw} {文件名:rmlf | 识别结果:rmf} ]
共计 83.0 文件,识别正确数量:76.0 正确率:0.91566265
程序识别的正确率还是比较邻人满意的。
经过这么一通折腾,我积累了下面这些数据,当然不能让它们闲着,等有时间整理下Spark机器学习和TensorFlow对这些图片处理的资料,然后再来码一篇。
未完待续。。。



