踏上重新安家之路，经过长时间的血泪史，这次终于搬好了家，到了一家很奇怪的vps公司，directspace，它家的价格白菜得简直令人不敢相信，2刀一月就有这种配置：

硬盘，内存，流量无一不极品，性能可能会缩水，但是流量不会啊，罕见的2TB流量，代理翻墙分流VPN干什么都够了；官方宣称硬盘是RAID10，相比磁盘性能也该不俗；另外同样是openvz，user_beancounters也是什么都不限制

unixbench 4.1.2-wht-2 成绩也很亮眼

但从成绩上看是不输给ramhost的，实际使用中从编译性能的体验来说也是很强。

客服态度和反应时间也很快，搬了半个月了出了一次网络问题，纠结了一个下午也算是帮我搞定了。

不尽如人意的地方：网络，习惯了ramhost的40MBits的网络，再回到10MBits就觉得有点慢了，尤其是连接ubuntu镜像的速度显得不够快，其他倒是差不了太多。

另外没有额外备份也在一定程度上降低了这个plan的实用性，不过2刀的价格，比共享主机都便宜，要求就不要太多了，呵呵。

总之directspace这家性价比超高，时间长了会出现啥状况如何不好说，但是就目前来看相当地nice，这么个性能有那么白菜的价格实在是不容易，准备一系列搬迁行动了。^_^

搬家顺便升级了wordpress到3.1，发现这个主题不错就放弃老版本了，原来的站点在 http://69.163.35.68/old/，什么都没有改。

安装

开玩笑，自从ubuntu 9.10引入grub2以后，尝试新系统还用得着安装？
刻录Live CD？制作启动U盘？太落伍了，俺们要直接从iso镜像文件启动
·
在/boot/grub/grub.cfg中加入一个启动项如下：

menuentry "Ubuntu 10.04 beta1 desktop" {
        loopback loop /boot/iso/ubuntu-10.04-beta1-desktop-i386.iso
        linux (loop)/casper/vmlinuz boot=casper iso-scan/filename=/boot/iso/ubuntu-10.04-beta1-desktop-i386.iso noeject noprompt --
        initrd (loop)/casper/initrd.lz
}

重新启动后选择的启动项即可。
不知道是不是我的特例，启动时黑屏了很久，我还以为失败了，结果多等了会就进去了，害得我还以为grub项没写对很是折腾了会。

使用

`
感谢祖国，感谢CCAV，最后感谢一下canonical，主界面终于改了，便便色的主题用了n年终于换了

`
文件夹，发现果然把关闭按钮等很奇葩地放到了左上角

`
Terminal，这个配色是怎样！我太感动了，终于不是刺眼的白底了，我就说嘛，terminal必须得是深色底白色字用着才舒服啊，canonical太赞了，就冲这shell的配色我就对10.04迫不及待了。注意看，terminal居然还是半透明的，很pp啊

`
vim语法高亮的效果图，这看着真是太愉悦了

`
默认的中文字体好像改了？看着也蛮舒服的`

`

我燃了

`
从9.10开始，ubuntu就不停地给我惊喜，虽然才是用了下”Live iso”，10.04给我感觉已经是远超我的预期了，本来听说争议很大还以为被他们改了个什么四不像出来呢，呵呵。
`
Ubuntu 10.04, 我燃了

西厢计划原理的进一步思考

`
我看了西厢计划项目的wiki还是云里雾里的，好在youxu大大的西厢计划原理小解解释的非常清楚，在这里我也简单归纳一下，西厢计划就是在TCP建立连接之初通过插入发送完全符合协议的TCP包欺骗GFW连接已经终结，来达到穿墙的目的。原理据说如下图。


`
根据“原理”的说法，张生同学实际上是利用了GFW本身的特性。（事实上，墙可以视作一种网络入侵检测系统，有着所有NIDS系统的弱点。）因为性能原因，墙作为一个旁观者，它无法做到对每一条TCP包都进行检查来过滤敏感词汇。tek4小组的大牛们，据说也就是西厢计划的探索者，经过长时间对墙的研究，发现墙很聪明地只会在连接发起的时候进行检测。
`
这样做是可以说的通的。中国的出国带宽应该早已破T，如果墙需要检查所有的TCP包，会是很大的负担。所以墙才会检查TCP会话的状态，当发现是死老虎状态时，直接放跑所有后继TCP会话。
`
然而我有一个百思不得其解的问题让我怀疑墙是否只在连接发起时进行过滤。我做了两个测试：
我建立了一个网页http://test.app-base.com/link.html，这个网页中含有falun词汇，并且有一个链接访问”/?falun”
测试1. 访问link.html。结论正常。
测试2. 访问link.html，再点击falun链接，结果被重置。
`
测试一结束后，我和服务器已经完成了三次握手，并且有来有回地发送了GET和获取了网页，这个时候我还有keep-alive属性，根据我对http 1.1的理解，这时候并没有终止TCP连接，而是立即回应了另一个请求，但是这个请求却被墙重置了，所以墙只在TCP连接发起时进行过滤这个说法我觉得有问题。当然我对网络协议还是很一知半解的，有说错的话请及时更正我，谢谢。
`
按照我的上述实验来看，墙并非只在TCP连接发起时进行过滤，而是对每一个TCP包都做检查，发现是GET请求就进行过滤，发现是回应则PASS（至少测试1没有被过滤，如果它扫描的话那就说明基于不同规则。）
`
然而西厢计划的成功实施，说明墙是保存连接信息的，所以它在记录两个主机的连接“终止”以后，放跑了所有这两个主机间的流量。那么关键的问题是，如果墙取消这么一个设定，不“放跑”已经“终止”的两个主机之间的流量，会对墙造成很大负担吗？

`

如果会，那么墙想要干掉西厢计划还是很困难的；如果不会，那么修正这个破绽简直轻而易举。

`
上述问题等价于：实际应用中，是否有很多正常的应用会在RST终止以后还是罗里罗嗦地发送一堆包？出于网络延时我觉得RST以后确实可能会发送一堆包，但是这个数量相对于正常应用的TCP包来说应该是小巫见大巫。那么为什么墙要做那么一个古怪的限制呢？为什么墙要记录TCP连接状态，阻断连接以后就直接无视后续的包呢？
`
思索了半天，我所能想到的唯一一个理由就是墙那么做是为了避免DDoS攻击。如果墙还要继续监控数据包，这可能会造成潜在的攻击点：攻击者不断地发送同样的数据包，墙必须一次又一次地拦截并且发送RST给攻击者，大规模地攻击下，墙的过滤系统资源将被耗尽，从而无法进行正常的运作。而如果墙能够确认连接已经重置，就算仅仅是出于性能优化考虑，判断主机IP决定是否过滤也要高效得多。
`

如果我是墙，会怎么应对？

1. 无视reset信号，不记录主机间的连接状态，所有TCP包都加入过滤。
`
这是最容易的一种处理方法，但是也是（据我推测）有安全和性能隐患的一种处理方式，理由见前文。
`
2. 记录三次握手序号，封锁西厢计划。
`
西厢计划骗墙认为receiver已经死老虎是通过发送一个序号不对的RST给sender，sender会无视，墙却会中招以为是死老虎。
`
如果墙想逮住”死老虎”，他必须记录sender给receiver的SYN/ACK握手的序号，并且和receiver再次返回给sender的ACK序号进行比对才能确定这个是否是西厢计划的一次欺骗。从数据结构上来看，需要多保存一个SEQ号，这是一个32bit的数，相比原来多占1/3的空间；而且如果墙是硬件实现的话（我觉得是），改变数据结构可不容易；从性能上来看，要多做一次主机的匹配和ACK序号的比对，性能开销也不小；而且墙一旦这么做了，隐患更大，之前因为不太了解墙的工作模式，想攻击都没法攻击，既然你用这么个办法来堵漏洞，那我就有的放矢直接灌水各种RST信号，那么墙就真的悲剧了。
`
看起来我觉得这种补救方式更加得不偿失。
`
3. 直接用IP封锁。（黑名单）
`
好像很犀利，不过可以直接通过代理绕过去，以前用代理因为有关键字过滤所以也没什么用，有了西厢计划，再加上代理，封IP就变得非常徒劳了。至于什么代理？什么都可以，squid、web代理、反向代理等、只要在墙外就行。
`
4. 白名单。
`
真的是大中华局域网了么，@@
这种情况下除非有白名单中包含国外主机，那还能通过代理出去，否则，就一个局域网怎么翻墙？这是最狠的一招，我觉得不太可能发生，但是永远不要低估某些人的脑残程度，万一……
`

为何不直接对内容过滤？从TCP协议的角度来看

`
根据我自己的测试，GFW似乎没有对内容进行过滤。不考虑处理能力的问题，理论上GFW似乎可以通过随机检查TCP包，然后发送阻断包终止连接。
`
然而他真的能发送阻断包吗？扫了一下TCP/IP协议，我发现它能干的事情有限。这是因为一旦连接建立，慢启动过后，TCP就开始高速运转了，sender同时会发送n个包给receiver，墙截取了当前的包，发觉有问题，这时候他想干扰传输有两个选择，要么发RST，要么发FIN(RFC1122,4.2.2.13)。可是这时候墙无法推测下一个序列号，因为他无法知道该死的sender到底同时发了多少个包给receiver，只能靠猜。
`
但是并不是说墙没有办法，根据TCP协议的Flow Control部分，receiver会给sender发一个windows size的参数，规定sender只能发那么多数据，之后要等待receiver的ACK表示收到。发送ACK表示收到的同时，receiver还会告诉sender它的acknownledge number，表示他预期下一个序列号是什么，这时候墙就能能乘虚而入伪造RST/FIN数据给receiver了。
`
这又是一个复杂的实现+性能和安全隐患，我想这也是为啥墙一般不直接做内容过滤，而是更倾向于url扫描和dns污染的另一个理由吧。
`

结论

西厢计划很好很强大，让我看到了墙的脆弱性，随着对墙的越来越深入的了解，越来越多牛人加入翻墙的研究，墙终究会变得不堪一击。道高一尺，魔高一丈。通过这次对墙的原理的学习，我突然觉得墙其实还是很千疮百孔的，并没有我原来想象的那么强大。就那么个破东西，国家花了无数纳税人的钱，只为了阻止纳税人们了解真实的世界，唉，很是无语啊。
`
最后补充一下，我本人对TCP的了解仅限于学得很是不行的“计算机网络”的知识，而且因为从来不用基本忘光，如果狗屁不通错误连篇也请谅解，如果能指出错误就更好了。
`

3月22日更新

首先，tek4小组在完成西厢计划后已经解散，解散之后他们发布了对GFW和西厢计划的一个总结，更宏观地解释了GFW的应对方式，证实了西厢计划并没有那么强大，见参考资料11。
`
其次，由西厢计划得到启发，结合“第八组第三次作业”中提到的忽略RST穿墙法（参考资料12），西厢计划似乎可以简化实现，并且由于实施单方面忽略RST而不是企图欺骗墙的关系，性能和无解程度会大大增强。如果和参考资料10的判断IDS结合起来，说不定会有很好的效果。
`
最后，第一次感觉不在墙内真是遗憾，那么有趣的技术没有办法实践，sigh…
`

3月23日更新

西厢计划出“第二季”了，其实和西厢计划没什么关系，可以说应该只是受到了西厢计划的启发。
`
这是一个很赞的实现，充分展示了墙的脆弱性，真是千疮百孔啊，未来没准第三季、第四季还会陆续有来。
`

参考资料

1. TCP协议
2. RFC1122(TCP部分,82-92)
3. IPv4
4. 西厢计划原理小解
5. 西厢计划提到的那篇论文，我扫了一眼居然发现了和我看了协议以后做的推理一样的某些段落，不禁小得意一下。
6. 穿越GFW的技术，很不错的总结。
7. GFW技术，研究与工具这个博客上面的内容都很有趣，值得一读。
8. 深入理解GFW，内部结构也是上面这个博客的内容，很强大。
9. NIDS网络入侵检测系统的缺陷。GFW作为一个NIDS，我们可以利用的漏洞都有总结，有些可以用，有些不行。
10. 一篇关于如何发现虚假RST攻击的论文，扫了一下觉得挺有用，以后可能用得到。
11. 原班人马对西厢计划弱点和GFW应对的解释，很有趣，我也算是千分之一了吧。
12. 第八组第三次作业中提出了直接忽略GFW的RST包也可以完成翻墙，结合参考文章10，我觉得西厢计划可以有更简单和更强大的实现。

NoSQL vs SQL

传统SQL数据库为了实现ACID(atomicity, consistency, isolation, durability)，往往需要频繁应用文件锁，这使得其在现代的web2.0应用中越来越捉襟见肘。现在SNS网站每一个点击都是一条/多条查询，对数据库写的并发要求非常之高，而传统数据库无法很好地应对这种需求。而仔细想来SNS中大部分需求并不要求ACID，比如Like/Unlike投票等等。

NoSQL吸取了教训，比如有些NoSQL采用了eventually consistency的概念，在没有Update操作一段时间后，数据库将最终是“consistency”的，显然这样的数据库将能更好的支持高并发读写。
`
SQL数据库是基于schema的，这对时时刻刻更新着的web2.0应用开发者来说是个噩梦：随时随地有新的应用出现，旧的数据库无法适应新的应用，只能不停地更新schema，或者做补丁表，如此一来要么schema越发混乱，要么就是数据库频繁升级而耗时耗力耗钱。
`
NoSQL一般就没有schema这种概念，大部分NoSQL都直接保存json类的Row，比如一个记录可以是
{ ‘id’ = 1, name = ‘Bob’, phone = 38492839 }，这样扩展升级非常方便，比如需要地址信息直接加入 address=’blahblah’ 即可。
`
传统SQL很难进行分布式应用，即使可以也往往代价高昂。而NoSQL则很好地解决了这个问题：他们一般都直接从分布式系统中吸取了Map/Reduce方法，从而很容易就可以处理规模急速增加的问题。
`
推荐robbin牛的NoSQL数据库探讨之一 － 为什么要用非关系数据库？一文，介绍了主流的一些NoSQL系统，还有这个站http://nosql-database.org/收集了基本上目前所有的NoSQL系统。
`
总结一下我对NoSQL的看法，NoSQL出现的目的就是为了解决高并发读写的问题，而高并发应用往往需要分布式的数据库来实现高性能和高可靠性，所以NoSQL的关键字就是concurrency和scalability。
`

我的瓶颈

我之前主要关注数据库的select性能也就是read性能，在读性能方面SQL数据库并没有明显的劣势，应该说纯粹高并发读的性能的话往往要优于NoSQL数据库，然而一旦涉及写，事情就不一样了。
`
我本来以为自己不会遇到大量写的问题，后来发现即使在simplecd这种简单的应用环境下也会产生大量的并发写：这就是爬VC用户评论的时候。事实上，sqlite3在处理这个问题上非常的力不从心，所以我产生了换个数据库的想法。
`
既然我是要求能高并发读写，干脆就不用SQL了，但是同时我也想测试一下其他SQL的写性能。
我的数据有180万条，总共350M，测试用了10个线程，每个线程做若干次100个数据的bulk写入，然后记录总共耗时。结果如下。
`
innodb: 15.19
myiasm: 14.34
pgsql: 23.41
sqlite3: 锁住了
sqlite3(单线程): 300+
mongodb: 3.82
couchdb: 90
couchdb(单线程）:66
`
作为一个MySQL黑，看到这组测试数据我表示压力很大。在SQL数据库中，mysql意外地取得了最佳的成绩，好于pgsql，远好于sqlite。更令人意外的是myisam居然优于号称insert比较快的innodb。不管如何，对我的应用来说，用mysql保存评论数据是一个更为明智的选择。我对mysql彻底改观了，我宣布我是mysql半黑。以后select-intensive的应用我还是会选择sqlite，但是insert/update-intensive的应用我就会改用mysql了。
`
MongoDB和CouchDB同为NoSQL，表现却截然相反，MongoDB性能很高，CouchDB的并发性能我只能ORZ，这种性能实在太抱歉了。
`

NoSQL的碎碎念

其实我本来还打算测试cassandra的，可是cassandra用的是java，这首先让我眉头一皱，内存大户我养不起啊，其次看了cassandra的文档，立刻崩溃，这简直就是没有文档么。（BTW，CouchDB也好不到哪里去，我都是用python-couchdb然后help(couchdb.client)看用法的）
`
至于CouchDB，可能是因为采用http方式发送请求，所以并发性能糟糕的一塌糊涂，很怀疑它是否有存在的理由。
`
MongoDB是我用下来最讨人喜欢的一个NoSQL。不但文档丰富，使用简单，性能也非常好，它的Map/Reduce查询(很多NoSQL都有)让我惊叹，数据库可以非常简单地就扩大规模，完全不用理会什么分区分表之类繁琐的问题，可惜这方面我暂时没有需求。但是MongoDB有两大致命问题。
`
第一是删除锁定问题，当批量删除记录时，数据库还是会锁定不让读写。这意味着进行数据清理时会让网站应用失去响应。见locking problems
`
第二是内存占用问题，MongoDB用了操作系统的内存文件映射，这导致操作系统会把所有空闲内存都分配给MongoDB，当MongoDB有这个需要时。更可怕的是，MongoDB从来不主动释放已经霸占的内存，它只会滚雪球一样越滚越大，除非重启数据库。这样的上下文环境下，MongoDB只适合一台主机就一个数据库，而没有其他应用的环境，否则一会儿功夫MongoDB就会吃光内存，然后你都fork不出新进程，彻底悲剧。见memory limit
`
总之NoSQL虽然让我眼前一亮，可是目前尝试的一些产品都让人望而生畏，现在的NoSQL都把目光放在了巨型网站上，而没有一个小型的，可以在VPS里面应用的高性能NoSQL，令我有点失望。NoSQL尚未成熟，很期待它的将来发展，目前来说MySQL还是更好的选择。

推荐一些相关文章

详细介绍了为何从MySQL转移到MongoDB的一篇文章，还指出了迁移过程中遇到的问题和他们的解决方法： http://blog.boxedice.com/2009/07/25/choosing-a-non-relational-database-why-we-migrated-from-mysql-to-mongodb/

MySQL,MongoDB,Tokyo Cabinet的性能测试对比，写得很好： http://jayant7k.blogspot.com/2009/08/document-oriented-data-stores.html

从概念上比较了MongoDB和CouchDB实现的不同： http://www.mongodb.org/display/DOCS/Comparing+Mongo+DB+and+Couch+DB

1.切块

其实我觉得最好的切块算法就是前文提及的聚类算法，在去噪正确的前提下，用聚类算法一聚就完了。因为我之前没想到聚类算法，使用了很直观的直接按列扫描划分的办法，但是后来发现Discuz有部分验证码这样是无法划分的，必须得聚类，again我偷懒了，因为已经有能用的现成代码，效果虽然差了点，也能过得去了，于是就懒得改了。
`
这部分代码写得很难看，但是能用，就不贴出来丢人现眼了。
`

2.规范化

所谓规范化其实就是旋转。为什么要旋转？因为旋转能够极大地减少样本库的个数，提升比对速度。之前有童鞋建议说可以采样不同角度的字母作为样本，可是我上哪找不同角度旋转后的样本？自己旋转经常会旋转得不伦不类的，要是直接采样那得采集多少个样本才能覆盖完整啊，1千个？1万个？想想就不高兴弄了，所以为了让我的生成特征库的工作省点力气，我决定还是规范化一下来得省力。
`
怎样旋转一个字母才算是转正了呢？我用了一个很土的算法：先旋转，再去掉边缘的空白边，然后计算该图形的“密度”（字体部分与整个像素之比），我定义密度最小的那个旋转体就是“规范化”的字母。事实上也可以这样定义：定义上下高度最窄的旋转体为规范化体。这两种定义应该是差不多等效的。
`
规范化代码如下

def normalize(im):
    # divide im
    regions = imdiv(im)  # 这是划分方法1
    if len(regions)!=4:
        regoins = imdiv2(im) # 这是划分方法2
 
    for k in range(len(regions)):
        regions[k] = dorotate(regions[k])  #干的就是旋转的事
        regions[k] = purify( docrop(regions[k]) )  #切边，然后把涂上预定义颜色
 
    return regions

`
这个正规化算法看起来没几行，其实干的事情挺复杂的，几乎调用了一遍里面所有的函数，比如getcrop(),docrop()是用来切除白边的；dorotate调用了rotate(),density()等一系列函数，干什么的根据名字就可以推断出来了，因为是比较直观但是却繁琐的“体力劳动”代码，我就不贴出来了。
`
规范化以后效果如下：

`

3.训练样本库

这里所谓的训练样本库，其实就是让程序显示一个规范化后的字母，然后告诉它这应该是啥，让它记住，仅此而已。
`
训练的代码如下：

def train(im):
    global samples
    try:
        samples = pickle.load(open('samples.pk','rb'))
    except:
        samples = {}
        pickle.dump(samples,open('samples.pk','wb'))
 
    regions = normalize(im)
    for region in regions:
        printregion(region)
        smps = loadsamples()
        print match(region,smps).upper()
        print 'enter [0-9a-z] to add to library: '
        ans = raw_input()
        if len(ans) == 1:
            key = (region.size,region.tostring())
            samples[key] = ans[0]
            pickle.dump(samples,open('samples.pk','wb'))

`
首先第一部分运用到了python的pickle模块，这是一个类似序列化工具的东东，用来读取/保存样本库，也就是samples.pk文件。
`
其次载入验证码图片，并规范化之，这时候会生成4个规范化字母，程序将会打印出规范化字母的样子，并且打印出目前特征库对他的比对（通过match函数，过会讲）。如果特征比对有错，则输入正确的值，让特征库记住它；否则就很好很强大继续比对下一个值。
`
这里面比较有疑问的就是 smps = loadsamples()， 和 match(region,smps).upper() 了，前一个函数做的事情就是把samples从序列化的strings还原成regions（Image模块的一个图形类别）。后一个函数就是比对函数。
`

4.比对

虽然我口口声声说要训练特征库，但是实际上我却没有那么做。因为一般的特征库都会降维，从而不可避免地会影响比对准确性，比如人脸识别的著名的PCA技术就是如此。PCA相比这个东东有个优势就是它的图像是彩色的，距离函数还好定一点；我们这个字体都是单色的，这个比对因为旋转的原因东少一块西缺一块，本来就悬乎了，更别说还要降维了，还嫌不够准么@@
`
其实和前文的判断samecolor类似，比对这个东西，最核心就是“距离函数”，怎样定义字母图形之间的“距离”，使得“距离”最短极为最相似。距离函数搞好了，那么就准了，搞烂了，那么就烂了。
`
我这个特殊的例子中，由于经历了偷懒版去噪算法和偷懒版旋转算法，所得的规范化字母往往东缺一块西少一块，普通的p-范数类的距离函数还真搞不定它，往往把字母都给搞混了。
`
经过调试，我定义了这样的一个距离函数，准确率还算可以：

def distance(r1,r2):
    den1 = density(r1)
    den2 = density(r2)
    if 1.0*den1/den2>1:
        (den1,den2) = (den2,den1)
    r1 = r1.resize(r2.size)
    d1 = r1.getdata()
    d2 = r2.getdata()
    same = [0,0]
    total = [0,0]
    for i in xrange(len(d1)):
        if d1[i] != BACKGROUND:
            total[0] += 1
            if d1[i] == d2[i]:
                same[0] += 1
        if d2[i] != BACKGROUND:
            total[1] += 1
            if d1[i] == d2[i]:
                same[1] += 1
    return 1 - 1.0*same[0]/total[0] * 1.0*same[1]/total[1] * 1.0*den1/den2

`
首先我想计算出相似度，我认为相似度可以一分为三：
1.相似的字母其密度一定相似，所以den1/den2越接近于1越相似
2.对r1来说，r1的点中在r2出现的频率越高越好，same[0]/total[0]越大越相似
3.反之对r2来说，…… same[1]/total[1]越大越相似
以上三点综合考虑，相似度即为以上这三个值相乘，距离即为1-相似度，于是就是上面那个函数。
`
其他辅助函数就不做说明了。
`

5.破解

其实到上面那一步，有点技术含量（或者说“技术含量可以有（但我不一定使用了）”）的部分就结束了，留下了一堆函数残渣，还需要一个“方便”的接口，输入验证码，输出4个字母。就是如下

def crackcode(im):
    global samples
    regions = normalize(im)
    s = []
    ans = []
    for r in regions:
        s.append(match(r,samples).upper())
    messup = ['TFY','FE','38','72YT','CQGR6','G6','XK','HK','89B','YV']
    for i in range(len(s)):
        for mess in messup:
            if s[i] == mess[0]:
                s[i] = mess
    if len(s) != 4:
        return 'failed'
    else:
        for s1 in s[0]:
            for s2 in s[1]:
                for s3 in s[2]:
                    for s4 in s[3]:
                        t = s1+s2+s3+s4
                        ans.append(t)
    return ans

这个函数需要说明一下那个messup数组，因为有些顽疾比如程序总是喜欢把8认作3等等，所以列了一个表用来给出辅助的可能答案。
`

6.测试

我从新建立的crackdz论坛上面采集了240个验证码，120个用来补充原先80个训练样本，构成总共200个训练样本，120个用来做测试。
`
结果如下：
直接命中：40个
messup数组的补充命中：14个
分块成功但是识别错误：27个
去噪或分块失败： 39个
`
可以看到识别率在33%-45%，还行，可以实战了，下一步就是写个注册机直接把我自己的论坛给淹了，哇哈哈哈哈。
`

7.源码

根据惯例附上源码
这次代码要说明一下，为了加速使用了psyco，请安装先psyco或者屏蔽一开始的psyco调用
还有训练的用法是：
python seccode3.py 目录名 #有两个目录，train和train2
识别的用法直接 python seccode3.py 即可，注意要把terminal字体缩放到很小，才能正常显示。
里面还有ttf字体版本的遗留代码，但是应该不能正常工作（？)，无视就好了。
包含了训练库所以有15M之巨的源码：seccode3.tar.gz

重新去噪

基于距离的去噪方式，后来可耻地失败了，所以兜兜转转绕回了色板方案：也就是说把相同颜色的色块挑出来，然后挑出最像验证码的色块。这里我绕了第一个圈子。
`
先稍微讲解一下gif的文件格式，众所周知gif可以有256种颜色，可是这256种颜色却是可以随便在RGB24位色中选择的，也就是说用得好的话其实gif效果和RGB效果也差不了太多。所以GIF是有调色板这么个概念的。
`
调色板有个问题就是不同的调色板可以存放同一种颜色。这样你就要判断哪两个调色板的颜色是相同的，然后再进行去噪。因为任意一个调色板都有可能存放字体颜色，而验证码色块颜色是非常随机的，可是去噪必须得设置背景色块，这样设置背景色块的调色板号成了一个难题。
`
这个难题后来被我用Image.convert()绕过去了，我把GIF格式转为了RGB模式，然后把纯白色(255,255,255)作为背景，一下子就解决了这个问题。
`
第二个问题是去背景，因为背景是固定的，所以可以通过gif图片不同帧的比较来挑出相同帧，一般即为背景。
`
如何判断颜色相同是另一个问题，因为视觉上的相同和RGB位色的相同是不一样的，比如白色可以是(255,255,255)，然则你用(254,254,254)显示的也还是几乎白色，肉眼很难看出区别。
`
我用了这么个方法：把颜色”矩阵”的1-norm（1-范数）值和一个预定义阈值做比较，在阈值范围内我就认为是相同的颜色。当然也可以取其他范数比如2-范数，我不知道人眼是怎么区分位色的，随便挑了个范数，觉得效果还行。
`
到此，去噪的第一部分完成了。

    #选取验证码帧和背景帧
    im = Image.open(fname)
    frame = None
    bkframe = []
    for i in range(10):
        im.seek(i)
        if im.info['duration']>DURATION:
            im = im.convert('RGB')
            frame = im.load()
            break
        else:
            bkframe.append(im.convert('RGB').load())
    #背景比较，去噪
    for k in range(len(bkframe)):
        for i in xrange(WIDTH):
            for j in xrange(HEIGHT):
                if samecolor( bkframe[k][i,j] , frame[i,j] ):
                    frame[i,j] = BACKGROUND

然后是samecolor函数判断是否同色

def samecolor(rgb1,rgb2):
    diff = 0
    for i in range(3):
        diff += abs(rgb1[i]-rgb2[i])
    if diff < COLORDIFF:
        return True
    else:
        return False

`
这一步过后，图形去噪如下：

`
可以看到大部分背景已经去掉了，剩下的都是些线条什么的。
`
接下来就要用到聚类算法了，这应该是模式识别里面的范畴，著名算法有k-means和其衍生品QT算法等，k-means要求预定义聚类个数，扔了；QT算法实现起来很复杂，我懒得实现，更懒得去研究那些locality sensitive hashing和什么Formal concept analysis了。
`
因为偷懒，这里我用了最土鳖的聚类算法，直接用samecolor扫一遍，一样的标记为同组，不一样的就跳过。这个土鳖算法有个问题就是它会选定某些点作为中心点，所有和这些点的1-范数距离小于阈值（也就是符合samecolor条件）的点都当作同色，而显然聚类算法的中心点不一定会是样本点，万一这个算法不小心选了个边缘点，聚类就直接聚错了，会比较悲剧。这里可能也是导致最后去噪效果仍不尽如人意的原因之一吧。MARK之，有时间以后改进。
`
聚类并且把颜色最多的色块挑出来，代码如下：

    # denoize2: group similar color
    cgrp = {}
    for k in d.keys():
        cgrp[k] = k
    for k1 in cgrp.keys():
        for k2 in cgrp.keys():
            if k1 != k2 and cgrp[k1] == k1 and samecolor(k1,k2):
                cgrp[k2]=k1
    d = {}
    for i in xrange(WIDTH):
        for j in xrange(HEIGHT):
            k = frame[i,j]
            k = cgrp[k]  # 选取聚类色，单独类就是本身
            if d.has_key(k):
                d[k][0] += 1
                d[k].append((i,j))
            else:
                d[k] = [1,(i,j)]
    topd = sorted(d.items(),cmp=lambda x,y:cmp(y[1][0],x[1][0]))

`
有些噪音点数也很多，很难通过色块所包含点的数量来判断是否是噪音，还得根据其聚类性来做辅助判断来进一步去噪。
`
这个函数也很难写，我写的不太好，最后效果也就不太好，有些圆弧形噪音和正常字符特征相似，唯一不一样的就是“粗细”较细，可是如何判断“粗细”也是个伤脑筋的问题，因为色块中还有噪音的存在……总之目前这个版本大概能有60-70%的去噪成功率，可以去噪出人眼能识别的验证码，我就凑活着继续用下去了。
`

def isnoise(points):
    '''Determine if the points are noisy points'''
    #如果点的个数小于10，过滤之
    if len(points)<10:         return False     # center point     left = 255     right = 0     upper = 255     lower = 0     center = [0,0]     for point in points:         center[0]+=point[0]         center[1]+=point[1]     center[0]/=len(points)     center[1]/=len(points)     distance = 0     farpoints = 0     for point in points:         dd = (point[0]-center[0])*(point[0]-center[0])+(point[1]-center[1])*(point[1]-center[1])         distance += dd         if dd > DIAMETER*DIAMETER:
            farpoints += 1
        if point[0]right:
            right = point[0]
        if point[1]lower:
            lower = point[1]
    #算区域面积
    area = abs(left-right)*abs(upper-lower)
 
    #如果有5个以上离中心太远的点，并且点在其所在区域的密度小于0.2，则为噪音
    if (farpoints>5 and (area==0 or 1.0*len(points)/area<0.2)):
        return True
    else:
        return False

`
接下来没有多少步骤了，去噪和去独立噪音点

    found = 0
    for (k,v) in topd[1:]:
        if not isnoise(v[1:]):
            for point in v[1:]:
                frame[point[0],point[1]]=k
            found += 1
        if found == 4:
            break
 
    # denoize again
    for i in xrange(WIDTH):
        for j in xrange(HEIGHT):
            if frame[i,j] != BACKGROUND:
                count = 0
                for m in xrange( max(0,i-1), min(i+2,WIDTH) ):
                    for n in xrange( max(0,j-1), min(j+2,HEIGHT) ):
                        if frame[m,n] != BACKGROUND:
                            count += 1
                if count <= 1:
                    frame[i,j] = BACKGROUND

`
大功告成：

`
这个算法到这里成功率已经大概有60-70%，（基于我的样本库：80个discuz随机生成的验证码）。今天先写到这里吧，后面的代码到验证码破解部分都已经完成了，贴文速度就取决于我的码字速度了，因为开学了所以也别太抱期望就是了。
`
按照惯例提供源码打包下载：
seccode2.tar.gz