by pluskid, on 2010-01-25, in 
验证码的识别可以说是一个非常困难的问题，更何况现在有一些验证码让人来辨认都有些不容易，当然正如我标题里说的，我这里讨论的是一种简单的验证码，具体来说就是经过旋转、缩放之后再加上一些随机线条作为干扰而得到的图片，如右图所示。其实这个问题最开始是 MSTC 第四届趣味程序设计竞赛中的一道题，这个学期上了一门《计算机视觉》课，最后要求交一个 Project ，老师给了一些题目，也可以自己想主题，于是我就定了这个主题。
由于最近各种 deadline ，我也没空把详细过程再用 blog 的方式写一遍了，如果感兴趣可以直接看我的 Report 文档以及完整的代码。
其实这个问题我在当时趣味程序设计竞赛的时候就尝试解决过，不过我当时用的办法是 PCA ，事实上，我尝试了 PCA 、LPP 以及 NPE ，从各种 paper 上还有理论推导中的道理来看，似乎都是后两者要更加先进一些，然而结果却是 PCA 最好，当时就令我有些诧异。其实我一直以来都有一些极端的“理想”，就是总希望有那么一些非常“自动化”或者“傻瓜化”的方法，把问题放进去就能得出结果，例如我在中学的时候凡是遇到几何题，几乎都是首先尝试建立坐标系用解析几何的方法来做，虽然构造各种精巧的辅助线来解决问题是许多人的最爱，然而我似乎不太喜欢这种“专门针对某一个问题要重新想一个方法”的方式，却更偏爱通用性更强的办法，就算有时候计算会变得很繁琐，但是最后通常总是能算出来的。在这里也一样，我似乎有一种愿望，或者甚至是一种错觉，我们可以有一种算法，只要把数据放进去，就能得出最完美的结果来，比如通常特征提取和构造的问题，我似乎不太喜欢使用太多 domain 相关的先验知识来人工构造 feature 的方式，而比较偏爱直接使用最原始的 feature ，然后使用降维来自动选择——我甚至在想，是不是首先通过升维（例如，使用 Kernel 的方法）来够找更多的特征以增加数据的区分度，然后再紧接着用降维的方法来提炼，是不是就可以完美地解决一切特征构造和抽取的问题了？
当然，现在我知道这只是一个美好的愿望，其实我一直也都知道这只是一个愿望了，只是仍然有点不自觉地往那个方向倾斜。其实这样的问题，也许如果我们可以得到无穷多的训练数据和无穷多的计算资源的话，应该是可以实现的啦，哈哈！ 😀
总的来说，我正在纠正自己的一些偏见，所以在学习了《计算机视觉》这门课之后我决定做一些尝试，特别是在知道了有一种叫做 SIFT 的特征可以保持旋转和缩放的不变性的时候，我就在想——这不就是正好是解决这个问题所需要的吗？所以我定了这个题目。然而不幸的是当我做出最后结果的时候发现实际结果并不好，还是经典的 PCA 最强。当然，到这个 deadline 前夕，肯定不能再换题目了，另一方面，虽然我一开始的设想被验证是错误的，但是这个 project 并不是没有意义的，我把它和 PCA 做了一些对比，并对结论做了一些分析，自己的理解也更深刻了一些，可以说还是收获挺多的。
另外就是这次我对噪音过滤的方法做了不少对比和尝试，最后的结论是中值滤镜最好，我印象中自己在做趣味程序设计竞赛的时候只做了非常简单的处理，于是好奇地找出以前的代码来看了一下，发现居然就是一个中值滤镜而已！不过当时不知道 OpenCV 也没有学过滤镜什么的，怎么找到这么个方法的来着？真是想不起来了。不过，有时候翻翻自己以前写的代码，确实会如同在论坛上考古一样别有一番趣味的，代码里也散发着岁月的味道，不是吗？ 😉
Report 文档以及完整的代码
2个ms给了相同的地址……
我也喜欢一种“通用的方法”，高中几何题上来就会把坐标系弄好然后弄一堆向量乘来乘去。现实有太多为效率和便捷性考虑的许多不能如愿，各种为了优化的硬编码，像GL下面的一个函数都有那么多版本，又如ent.ftp的gbk和utf8等。
我自己还不自觉地不太喜欢某些不能得到唯一结果的算法，这可能是ACM带来的习惯吧，总是希望对一个问题能“多快好省”地得到最优解，然而现实是╮(╯_╰)╭这样的。
@discret
fixed 额，总是犯这样的错误啊……
@quark
找个平衡吧，不是说 life is all about balance 吗？ 🙂
原来你也上这课，我还在研究SIFT的稳定的Matching方法。今天。。。哦是昨天晚上刚考完最后一门，BT的CAGD…
不错的project，请问FreeMind，你们试过这两种验证码吗：1 字体有变形；2 字符粘连；http://en.wikipedia.org/wiki/CAPTCHA
@maxint
啊,momo，CADG 这个是什么课？
@hebby
这个就没有试验过了，那样问题就变得真的很难了呢！
@pluskid
Comuter Aided Geometry Design，数学系的课，是王老（王国谨）上的，讲Bezier、B样条曲线(e.g. NURBS)等。他上课很严谨，所以比较BT。总算结束了，如果是自己看书，打死也不会去看那些东西。
so complicated ……
SFIT嘎复杂的。这次打算project搞，后来一看，发现我3个礼拜搞不定，于是就算了
Free Mind 你好。
在你的report里，分析了不同出噪声算法对于字符提取的影响。
但我有个问题，你使用何种方法把用了中值滤波后被损伤的字符提取出来的。我做的是用高斯滤波，labeling，然后再根据不同的label分割图像，然后normalization， 在提取特征。
由于labeling过程中，单个字符的某一部分会被标记成两个不同的label，后面的所有工作都是错误的。
你的方法是什么，请赐教。
不知道你是怎么做 labeling 的，我提取字符是用了比较简单的加了一点启发式的方法来搜索字符的框架的，具体你可以看一下我给出的代码。
你所使用的编程语言我不熟悉，请见谅。
我看了一下，你的方法是不是首先定义一个字符的宽窄阈值，在这个阈值定义的窗口下搜索字符的框架。如果我分析的没错的话，那对于大篇幅的字符这个方法也适用吗？
我用的方法是对于除噪声后二值化的图像应用connect component labeling中Two-Pass（union find）算法4-connectivity的label标记法，这种方法相对简单一些。但在现在的测试中，经常会把字符拆分。
你觉得哪种方法跟适合大篇幅的字符提取或是标记？
谢谢
嗯，差不多就是你说的那样。不过，对于大篇幅的字符我就不清楚了，因为噪音不能完美去除，而且去除噪音的时候也会“误伤”真实的部分，所以有很多困难。我想可以尽可能加一些先验的知识进去，以期望能提高精确度，比如字符平均大小之类的。
你所谓的visual word，在计算机视觉领域确实很常用，但SIFT和SURF是角点检测算子，然后提取一些他们定义的特征，估计你没有观察过SURF提取出来的角点的样子，如果观察过，你会明白为什么实验效果那么差。
特征最后用的有点对了，分类器完全错误，就是GMM也比KNN好。只是你的分类样本太简单，所以能到90%，有空的时候可以看看QDF和MQDF，这个题就容易很多了。另外笔画宽度信息很重要。可以考虑进去。
确实当时对 SIFT/SURF 这些局部特征具体是怎么回事完全不了解，只是听说有旋转不变就直接拿来用，另外接触的机器学习相关的东西还是比较学院派的。当然不是所机器学习的理论和算法研究没有用处，而是着眼点不同，总的来说一般涉及到具体领域的应用问题的话，领域相关的知识应该是非常重要的一部分。
至于这个 QDF 和 MQDF ，大致搜了一下，似乎是专门为字符识别设计的方法？嗯，如果以后有要做这方面的事情，会去仔细了解一下的。非常感谢你的建议!
有个问题想请教你一下~
我有一些分割好的 大小统一的 英文字符 想提取每个字符的特征值，不晓得能用你的程序中的那些代码呢，就是想把这些字符的特征值提出成若干维的 向量。
然后还想得到 扫描图片的 每个文字的特征值
不晓得你能给我个指点吗~？
你好，你如果要做真正的识别的话，建议去参考一下上面提到的 QDF 和 MQDF ，而不是用这个课程作业里的代码。
求教，请问这种级别的验证码识别难度如何？
http://icode.renren.com/getcode.do?t=login
能加的干扰全加上了，旋转，字体，粘连，彩色，干扰线，噪点，色块
非常困难……
我也觉得选feature的时候如果加了先验的话是很cheating的做法，而且往往越多的先验效果越好，诱使人一直加下去。
但是我觉得降维选择feature的时候一般都有feature之间iid的假设
也是一种局限