图像压缩原理基础 连载3 时域模型与运动补偿

* 本文(包含其插图)严禁转载,并且不会同意您的转载请求。如有需要引用或介绍本文,您可以提供本文的连接。
时域模型的作用是消除连续帧之间的时域冗余。在时域模型中,当前帧减去参照帧得到残差图像,对残差图像进行编码,达到降低时域冗余的目的。参考帧选得越准确,所得到的残差图像能量越小,越容易压缩。
一个最简单的方法便是找过去的图像作为当前帧的参照帧。但这种方法有一个明显的不足,那就是残差图像的能量相对于我们的压缩需求来说依然过高,后续模型依然村在大量信息需要压缩。这个问题的主要原因是物体运动。因此要进一步降低数据量,必须对图像进行运动补偿。
基于块的运动估计和补偿:现在普遍采用的运动补偿方法是基于块(Block)的运动估计和补偿。这种运动补偿方法首先将图像向划分成若干个块,分别对每个块进行运动补偿。下面简要说明其过程。
首先在参照帧中搜索当前块的匹配块。将当前块于参考帧特定搜索区域中(一般是以当前块的位置为中心的一片区域)所有块进行比较,找到相减后残差能量最小的块作为最佳匹配块。这个过程称为运动估计。之后,将最佳匹配块作为当前块的参照块,当前块减去参照块得到相应的残差块。此过程被称作运动补偿。对残差块进行编码和传输,同时运动向量(当前块和参照块之间的相对位置)也被编码和传输。
Image
基于块的运动补偿有多种优势,如计算复杂度低、适用于长方形视频图像、适合分块变换(DCT、DWT等等,下一节会说到)。单其同样也有缺点,如真实物体很少是长方形的、物体运动经常是非整数块、较复杂的运动和较复杂的形状不适合这种补偿方式等等。但抛开不足,基于分块的运动补偿算法仍旧是标准时域模型的基础。
运动补偿的块:在大多重要的视频编码标准中(如MPEG-1、MPEG-2、MPEG-4等等),宏块(16*16像素大小)是运动补偿的基本运算单位。在运动估计时,编码器在参考帧中寻找与当前宏块匹配的16*16像素区域,使匹配准则达到最小的16*16区域即为最佳匹配。当前宏块的位置与最佳匹配宏块的相对位置为运动矢量,当前宏块减去最佳匹配宏块所得到的残差宏块将于运动矢量一同被编码和传输。
块的大小:事实证明,运动补偿的块越小,得到的残差图像的能量越小。然而,分块越小,块越多,算法复杂度越高,矢量数目越多。传输矢量所需的数据量很可能大于图像残差能量减小所节省的数据量,这样一来就会造成得不偿失的情况。比较好的解决方法就是使用自适应的分块大小,对细节较少的部分采用大的分块,对细节较多的地方采用较小的分块。
像素插值:在很多情况下,利用插值后的像素位置进行预测将提高运动补偿的精度,原因在于,在插值后的像素位置上进行搜索时,有可能找到更好的匹配。下面简要说明1/4像素插值的运动补偿过程:
首先编码器在整数像素上找到一个最佳匹配,之后编码器对该位置附近进行半像素插值,之后在半像素的位置上继续搜索,寻找更好的匹配位置。如果找到了更好的匹配位置,则在该位置附近进行1/4像素插值,之后寻找更好的匹配。最后由当前块减去最佳匹配块得到残差块。
理论上说,插值越精细,运算复杂度越高,运动补偿效果越好,即得到的残差能量越小。但事实上,随着插值变得精细,其对于运动补偿的改善作用也在逐渐下降。打个比方,如果1/2像素插值能提高30%的性能,那么1/4插值很可能只能带来15%的提升,而1/8像素插值则可能仅有3%(不同的图像其提升作用不完全相同,以上数据仅为举例)。
运动补偿的精度:从运算复杂度上来说4*4分块加上1/4像素插值的运动补偿比起没有插值的16*16分块运动补偿复杂得多。从信息量上来说,由于每块的运动矢量同样需要参与编码并传输给解码器用于重建图像,因此随着分块尺寸变小,所需要编码和传输的运动矢量数目激增。同样,半像素、1/4像素插值搜索会造成运动矢量产生小数,运动矢量的小数部分必须和整数部分一起编码,所以会消耗更多的比特数。
因此,运动补偿精度越高,编码运动矢量消耗的比特数越多,编码残差图像消耗的比特数越少;反之,运动补偿精度越低,编码运动矢量消耗的比特数越少,编码残差图像消耗的比特数越多。
基于区域的运动补偿:除了基于宏块的运动补偿之外,还有基于区域的运动补偿等方法。但由于实现这种技术还存在诸多困难,所以现在应用较少。MPEG-4提供一些基于区域的运动补偿的工具,有兴趣学习的读者可以找来相关的资料学习。

参考资料:
《H.264和MPEG-4视频压缩——新一代多媒体的视频编码技术》 [英]Iain E.G.Richardson 著 欧阳合、韩军 译 国防科技大学出版社 2004年11月第一版

Go Home~学期末纪念~

Image
转眼之间到了夏季学期的最后一天,转眼之间一个学期又到了头,转眼之间在大学的第一个学年也到了头。看到对面楼的学姐们开始准备搬家了才知道,原来大学生活过得是这么快,快到你根本来不及留意就在你眼前偷偷溜走。

Academics break the Great Firewall of China

Computer experts from the University of Cambridge claim not only to have breached the Great Firewall of China, but have found a way to use the firewall to launch denial-of-service attacks against specific Internet Protocol addresses in the country.

The firewall, which uses routers supplied by Cisco, works in part by inspecting Web traffic for certain keywords that the Chinese government wishes to censor, including political ideologies and groups it finds unacceptable.

The Cambridge research group tested the firewall by firing data packets containing the word “Falun” at it, a reference to the Falun Gong religious group, which is banned in China.

The researchers found that it was possible to circumvent the Chinese intrusion detection systems by ignoring the forged transmission control protocol resets injected by the Chinese routers, which would normally force the endpoints to abandon the connection.

“The machines in China allow data packets in and out, but send a burst of resets to shut connections if they spot particular keywords,” explained Richard Clayton of the University of Cambridge computer laboratory. “If you drop all the reset packets at both ends of the connection, which is relatively trivial to do, the Web page is transferred just fine.”

Clayton added that this means the Chinese firewall can be used to launch denial-of-service attacks against specific IP addresses within China, including those of the Chinese government itself.

The IDS uses a stateless server, which examines each data packet both going in and out of the firewall individually, unrelated to any previous request. By forging the source address of a packet containing a “sensitive” keyword, people could trigger the firewall to block access between source and destination addresses for up to an hour at a time.

If an attacker had identified the machines used by regional government offices, they could block access to Windows Update, or prevent Chinese embassies abroad from accessing specific Chinese Web content.

“Due to the design of the firewall, a single packet addressed from a high party official could block their Web access,” said Clayton.

Even though this technique would block communication between only two particular points on the Internet, the researchers calculated that a lone attacker using a single dial-up connection could still generate a “reasonably effective” denial-of-service attack. If an attacker generated 100 triggering packets per second, and each packet caused 20 minutes of disruption, 120,000 pairs of endpoints could be prevented from communicating at any one time.

Clayton, speaking at the Sixth Workshop on Privacy Enhancing Technologies in Cambridge last week, said that the researchers had reported their findings to the Chinese Computer Emergency Response Team.

微调Waki-Blog

最近两天调整了一下Waki-Blog程序,主要有一下几个方面:
1.RSS输出加入了换行。之后考虑改为全文输出+BBCODE代码解析。至少现在还没做好那样做的心里和物质准备 囧。
2.存档栏改为Ajax。这样可以剩下一个包含文件…间接提高了程序的效率。新的存档栏采用JavaScript读取XML显示。XML是由程序生成的,每次更新Blog的时候都检查是否有必要更新缓存与XML。以后页面可能会继续Ajax化。
由于Ajax的实现效果可能与浏览器有密切关系,所以可能会出现在不同浏览器中的兼容性问题。若您在浏览过程中出现问题,请联系我。目前测试过程中,FireFox尚未发现兼容性问题。使用IE浏览的过程中,第一次访问能顺利显示存档栏,但如果刷新的话就会出现存档栏无法显示的问题。
3.优化了缓存结构,节省一次数据库查询。
在Waki-Blog中不打算使用太多缓存,不然数据的同步与即时性就成了很大的问题。其实只要打开SuperTPL的静态页面功能,前台100%的页面都可以实现数据库0查询,甚至可以连缓存数据都不访问直接输出HTML,但是做到这一点却需要在后台和模板引擎中加入大量的代码来维护、同步缓存数据,得不偿失。

天高く、雲は流れ 第一卷 第一章 呼唤暴风雨的男人 2

* 本文(包含其插图)严禁转载,并且不会同意您的转载请求。如有需要引用或介绍本文,您可以提供本文的连接。

隔了两个月,终于又开始翻译了= =||说不定两个月前开始看的人都忘了剧情了……下面是序言和第一节的链接:
http://www.dgwxx.com/blog/index.php?blog:6
http://www.dgwxx.com/blog/index.php?blog:8

悠法这才发现,自己已经跑到了别的街道。
街道变得狭窄,建筑物也变得拥挤起来,因此明明是白天却怪异地显得有些昏暗。
“爸爸,你在哪。”
在没人经过的街道上,悠法一个人跌跌撞撞地走着。就像飞龙他们猜得那样,悠法迷路了。
爸爸在一边热烈地谈话,悠法觉得很无聊。这时,他看到了一个带着奇怪动物的人。那是一只后背隆起,提醒很大的动物,悠法从来没有见过。悠法出于好奇心追了上去,但没一会就跟丢了,因此不但离开了大道,而且完全迷失了方向。
“爸爸……”
悠法一边走着一边用紧握的小拳头擦着眼睛。一个人处在陌生的地方,由于不安和无助哭了起来。
“呜——妈妈——”
悠法一边哭一边在连方向都搞不清楚的街道上走着。忽然,从旁边的小路上突然飞出来了一个黑色的东西。
“啊!”
虽然被吓到了,但是悠法马上就绽开了笑颜。从小路飞出来的,是一只小狗。小狗全身漆黑,眼睛像红宝石一样,背上有银色的鬃毛,跑到悠法的脚边,使劲地摇着尾巴。
“哇,好小。”
悠法蹲下来,抱起小狗。抱在胸前的小狗热乎乎的、软软的。
Image
“你长得好怪啊,但是真漂亮。”
悠法抚摸着小狗的脑袋,小狗好像很高兴地舔着悠法的脸。
“好痒啊。”
摆脱了一个人的孤单,悠法高兴起来。

“在这。”
小狗飞出来的小路上,出现了一个中年男人。小狗在悠法的怀里发出了哀鸣。
“孩子,快把那只狗交给叔叔。”
中年男人一接近悠法,小狗突然狂叫起来。
“叔叔,你要干什么。”
悠法仿佛碰到了什么恶心的东西似的问那个男人。男人手里拿了一根棍棒似的东西,尽管藏到了身后,但是仍能隐约看到。
“小朋友,那只狗可是魔族中的魔犬啊。你仔细看看,它的眼睛像血一样红,背上连鬃毛都有,不可能是普通的狗。它又可怕又危险。乖,快把它给叔叔。”
男人一边用撒娇的声音说着,一边靠近悠法。悠法抱着小狗慢慢后退——
“不要,不给你!”
悠法突然意识到,如果给他的话,小狗就会被杀掉。
“明明这么小,只是因为被说是魔犬就要被杀掉……爸爸说过,虽然被叫做魔族,但他们跟人类、动物一样。”
悠法强硬地说道。

在这个大陆上,有着被叫做魔族的人们。他们因为是 “大黑暗”时代的后裔,所以拥有与常人相异的外表和特殊的力量。魔族除了人类,还包含动物和植物。
“怎么能叫他们魔族呢。不能只因为与别人不一样,就歧视他们。”
悠法想起了飞龙对他说过的话。睡觉前,飞龙经常在暖炉前讲各种各样的故事。这其中,也有关于“大黑暗”的事情。
“那是很久很久以前,这个大路上还有很多国家、有很多很多人的时候的故事了。”
这样说着,飞龙讲起了很久以前的故事。
有一天,一个不该存在于这个世界上的东西突然出现,于是被称作“大黑暗”的时代开始了。它放出红色的光,照着世界,浸在红光中的动植物变得狂暴。世界陷入了极大的混乱当中,很多人因此而死,很多国家也灭亡了。
这时,出现了七个魔法师。他们打倒变得狂暴的人们,或将他们封印在“世界的尽头”。
“大黑暗”就这样结束了。
但是,却还有很多外貌改变或拥有特殊力量,却没有变得狂暴的人们。人们害怕他们,称他们为魔族。只是因为不同,就厌恶他们。
“虽然说是不同,但这跟每个人的长相、声音都不同不是一个道理吗。为什么要排斥他们呢。”
飞龙露出悲伤的表情说着。总是很开朗的爸爸那时的表情,深深烙在了幼小的悠法心中。

“我跟它是朋友!不要把它给你!”
悠法紧紧咬着嘴唇,更加用力抱紧了胸前的小狗。男人恼怒地咂了一下嘴。
“真是不懂事的小鬼!那只狗是魔族,如果放任不管一定会去害人!在那之前杀了它是最好的!”
一边说着,一边把藏在背后的棍棒拿出来对着悠法。
“快把那只狗给我,不然就算是小孩我也不饶你。”
明显是在威胁。无论是多任性的孩子,听到这样的话都会这样想吧。但是——
“就是不给!”
悠法就这么抱着小狗,转过身去跑开了。
“喂!”
感觉到背后追来的男人,悠法拼命地向前跑。无论如何,都非跑不可。
“明明什么坏事都没做,这么小就要被杀,实在太可怜了!”
悠法拼命在昏暗的小路上跑着,甚至有好几次都产生了把小狗放下来的心思,但就算这样也要全力向前跑。然而,孩子终究是跑不过,马上就会被追上。
“小鬼!”
悠法被从后面揪住脖子,仰面倒在了地上。虽然后背猛地磕在了石板路上,痛得流出了眼泪,但就算这样悠法也不放开小狗。
“真是的,一开始就给我不就好了。”
俯视着悠法,男人恨恨地说。
男人在旁边蹲下,伸出手想要抓住小狗。这时悠法不假思索地撞向男人的下颚。
“哇!”
男人吃痛向后坐了下去。趁着这个工夫,悠法站了起来,又跑了出去。
悠法在迷宫似的小道上跑着,不时回头张望。虽然看不到男人,但咒骂声和杂乱的脚步声却不断接近。
“会被追上的!”
如果那样的话,大概会被那根棍子打吧。悠法越想越害怕,不由得闭上了眼睛。突然,嗵!好像撞到了什么东西上。
“唔——”
不知道撞上了什么东西,悠法按着额头哼着。
“没事吧?”
年轻男人的声音。正面向上看去,是一个裹着头巾的高个子男人。尖尖的、端正的脸,深青色的上衣和同样颜色的裤子,披着白色的披风。
悠法直直地凝视着这个青年。青年紫色的眼睛里有着狭长的瞳仁,像猫一样。
“像猫一样的眼睛。”悠法说道。
青年好像想要说什么一样动了动嘴唇。

“看你是个孩子才对你这么好的,竟然不识抬举!”
怒吼声爆发而出,那个高举着棍棒的男人出现在了小路上。本来以为会从后边追过来的男人竟然突然出现在了面前,悠法下了一大跳。
“快把魔犬交出来!必须杀了魔族!”
挥舞着棍棒的男人终于过来了。
“他要杀了它!”悠法梗起身子,紧紧地抱着小狗。
呜——小狗发出了悲鸣。正在悠法以为逃不掉、正要放弃的时候——
“必须杀掉魔族?别胡说了。”
青年又反了回来。突然,男人的脸色变了,手中的棍棒也落到了地上。
“帕、帕加!?”
“明明什么坏事都没做,只是因为是魔族就要被杀?而且还举着棍子追打小孩?”
被叫做帕加的青年用放光的紫色眼睛盯着男人。
“不、不好意思!刚才我不知道是你!”
因为位置的关系,男人只能看到青年的背影。男人发出“请绕了我吧”的悲鸣,用比来的时候快得惊人的速度逃走了。
悠法呆呆地望着逃走的男人的背影。
“这是你的狗吗?”
帕加摸着小狗的头,悠法摇摇头。
“但是如果爸爸同意的话,我就能养它了。”
悠法抚摸着小狗,小狗舔着悠法的脸,像摇旗似的摇着小小的尾巴。
“那只狗可是魔犬,你不害怕吗?”
被帕加这么一说,悠法一幅呆然的样子。
“为什么?”
被反问回来的帕加轻轻耸了耸肩。
“如果我弄错了实在不好意思……难道你是飞龙的儿子?”
帕加转换了话题。悠法使劲点头。

“嗯,我爸爸就是飞龙。”
悠法很精神地回答。帕加的一片眉毛轻轻地颤了一下。
“我叫悠法。嗯——帕加叔叔是爸爸的朋友吗?”
似乎是碰到了爸爸的朋友,悠法稍微放心了一些。但是帕加的回答似乎有些复杂。
“不是朋友,只是在一个道场互相认识而已。”
“……?”
悠法歪过头,似乎不知道“朋友”和“相识”的区别。
“话说回来,现在飞龙在哪?那个混蛋什么时候回首都来的?”
悠法被帕加连珠炮似地问着。但是,迷路的悠法怎么可能知道飞龙在哪。
好像只是看到悠法窘在那里不说话,帕加就全都察觉到了似的——
“原来迷路了啊。”
帕加苦笑道。悠法轻轻地点头,告诉帕加爸爸因为和一个叫埃伊卡的朋友说话,自己因为无聊,去追奇怪的动物,就迷了路。
“真是的,竟然聊天聊得忘了孩子,这个爹是怎么当的。好吧,去埃伊卡的店里吧。那样的话应该能见到飞龙吧。”
发完牢骚,帕加像是在说跟我来一样摆了摆手,快步走开。悠法放下小狗,跟着帕加。
“帕加叔叔走得好快啊。”悠法一边跑一边想。然而自己就算跑也追不上帕加。大人和孩子,无论步幅还是速度都差太多了。
“但是,一定要跟上。”
为了不被帕加落下,悠法拼命地跑着。小狗一边跑,一边顽皮地跟着悠法。
忽然,前面的帕加站住了。
“怎么了?”悠法不知道帕加为什么停下来了。
“帕加叔叔,怎么了?”
好不容易才追上的悠法一边喘着粗气一边问,但帕加没有回答。只是稍微看了一眼悠法,就继续无言地走了。
“?”
虽然不知道怎么回事,但是悠法还是继续跟着帕加。这次,悠法忽然感觉到帕加的速度变慢了。
“啊,慢下来了。”
虽然说相对于孩子来说还是很快,但现在至少不用跑就能跟上了。
不必担心有人追杀,又能轻松地跟上帕加,悠法开始高兴地跟帕加搭话。
“帕加叔叔,你跟爸爸在一个道场吧。道场是什么样的呢?你跟爸爸谁比较强?”
但是,帕加几乎都没有回答。就算回答,也是“啊”、“不知道”什么的,尽是些让人难以理解的回答。“如果是爸爸的话就会告诉我了。”如果是飞龙的话,肯定会说很多,但是帕加好像完全不同。
“好无聊。”
就算一个人不停地说也不好玩。没办法,悠法只能选择沉默。
两个人默默地走着。不知拐过了几个小道,穿过了多少街区,终于到了热闹的大道。
“啊,太好了!”
从昏暗的小路出来,正当悠法东张西望的时候,一直没说话的帕加终于开口了。
“东张西望的,小心又跟丢了。”
像被钉子刺到一样,悠法小声回答“是”。
在大路上走着,悠法注意道路上的人都躲开帕加。拿着棍棒追悠法的男人也是这样的,看到帕加马上就逃到不知道哪里去了。
就算不逃,也远远地用嫌恶的实现看着他,好像看到什么不吉利的东西一样。就算这样,也绝对不跟他对视。
“帕加叔叔……”
总觉得帕加很可怜。悠法抬起头看着他。
“别在乎周围的人。他们只是看我而已,没什么。”
帕加面无表情地说,无视他人的视线和沉重的气氛,至少看上去如此。
现在像帕加这样,从外表一眼就能看出来是魔族,并拥有特殊能力的人越来越少了。因为经过了漫长的岁月,血统变得稀薄了。但是在人们对魔族的恐惧完全消失之前,隐藏魔族血统生活着的人也为数不少。
“到底是为什么呢?”
似乎是遇到了自己还无法理解的事情,悠法咬着嘴唇。
“啊!找到了找到了”
冷清大街上想起了明亮的声音。
“来了吗,那个混蛋。”
朝着声音的来源瞥了一眼,帕加咬牙切齿地说道。悠法转过头,看到了一个朝这边跑过来的人影。
“爸爸!”
跑过来的正是飞龙。

今天更新了Waki-Blog!

今天小小更新了一下Waki-Blog,主要有以下几个方面:
1.修改了一下数据库结构,blog表增加一个字段cmds,记录该条Blog的评论数。
2.修改了Blog阅读页面的数据库查询,如果没有评论/Trackback的话,就不查询数据库,阅读既没有TB也没有评论的Blog的时候,可以节省两次数据库查询和两次循环。在某种意义上解决了Blog阅读页面的数据库查询稍多的情况。当然,如果有TB/评论,该查的还是得查= =||
3.增加了删除评论的功能。现在删除评论不用再跑到phpMyAdmin里面了~HOHO~网页的中的JavaScript借用了Z-Blog中的代码。这里感谢一下~HOHO

图像压缩原理基础 连载2 运动图像压缩基础(1)

* 本文(包含其插图)严禁转载,并且不会同意您的转载请求。如有需要引用或介绍本文,您可以提供本文的连接。

本节将抛开具体的编码器与运算原理,讲一讲一些运动图像压缩的基本思想与模型。
(1)运动图像压缩的可能性
信息(这里不仅仅指图像信息)可以被压缩,是因为其中包含着冗余。若将信息(数据)中的冗余去除,即可减少其数据量。
具体到运动图像信息的压缩,则是通过去除其中包含的统计冗余、空间冗余、时间冗余等来实现的压缩。我们经常提到的无损压缩,就是通过去除图像信息中的统计冗余来实现的。但是这样似乎并不够,因为目前对于视频的无损压缩算法只能获得很有限的压缩率。因此,现在多数使用的压缩技术是建立在有损压缩的基础之上的。有损压缩的代价是解压缩信号和原始信号不完全相同。因此,我们进行视频压缩的目的就是,在获得尽量高的压缩效率的同时使失真最小。

(2)视频编码器的模型
压缩是降低数据量的过程。而视频压缩,则是降低数字视频序列数据量的过程。视频压缩包括编码器(encoder)和解码器(decoder)两部分,合称为编解码器(CODEC)。
编码器需要通过某个模型来描述一段视频,这种模型既要兼顾压缩率,也要顾及压缩后的视频质量,使其尽可能地接近压缩前的图像。然而压缩率与质量通常是互相矛盾的:随着压缩率的提升,质量也随之下降。
下面的图示展示了一个典型的视频其编码模型:
Image
典型的编码模型包括三个主要部分,时域模型、频域模型、熵编码器。相邻的帧之间具有较大的相似性,因此未压缩的视频流输入时域模型之后,时域模型通过建立预测帧来降低时域冗余。频域模型输入的是残差图像,利用同一幅图象中相邻像素点的相似性,消除残差图像的频域冗余。熵编码器对运动向量和变换系数进行压缩,消除存在的统计冗余,最后输出用于传输或存储的数据。

预告:简单分析过视频编码器的典型模型之后,我们将逐个讲解时域模型、频域模型、熵编码器的简单原理。
时域模型中具体是如何消除时域冗余的呢?运动估计、运动补偿、1/2插值又是什么呢?请期待下一节时域模型的讲解。

参考资料:
1.《多媒体技术基础》 雷运发主编 中国水利水电出版社 2005年4月出版
2.《H.264和MPEG-4视频压缩——新一代多媒体的视频编码技术》 [英]Iain E.G.Richardson 著 欧阳合、韩军 译 国防科技大学出版社 2004年11月第一版

一段很经典的对话

这是一段发生在上个学期、我和老八之间的对话。
(背景:老八拿着某女同学的某不知名牌MP3听。)
老八:(对我,感叹状)看,这个耳机是苹果的。
我:哈?我看看……这个是假的(不知名MP3会附带苹果的耳机才怪)。
老八:(不服气状)你怎么知道是假的?
我:因为我见过真的。
老八:(无语状)囧……

再次说说Blog的人身安全

上次写了一篇文章叫“Blog的人身安全”。今天月光博客又发表了一篇文章,提到了Trakcback的问题。今天就再次来谈谈我在反SPAM上的一些小招数。

1.首先要做到的,也是最简单能做到的,就是将Trackback地址复杂化。
回顾今年3月份的Donews Trackback SPAM事件,正是因为Donews的Trackback地址采用了连续的ID作为Trackback的URL,所以才会使系统变得易被攻击。(话说Donews现在的TB URL貌似依然是连续ID,比如:http://tb.donews.net/TrackBack.aspx?PostId=930641)
一个方法是在TB URL中加入验证字串,比如tb.php?id=123&auth=78q34f,验证字串的算法可以使用标题或者文章内容的MD5 Hash中的一部分来充当。然而,这样增加了URL的长度和本来不应该有的信息量,似乎并不是最好的办法。那么,我们为什么不连ID一起加密掉呢?
我的做法是采用一个可逆加密算法(目前Waki-Blog使用的是我自己写的z-Enc),加密URL中的ID,Trackback程序收到字符串之后,解密、验证,若合格则继续,不合格则拒绝。同时起到了提高URL复杂度、隐藏ID、验证提交的作用。我的Blog中的TB URL中类似“response.php?tb::0a2MTc%3D”的部分,就是z-Enc编码的结果。
z-Enc的详细说明和源代码都可以在上面的链接中找到,希望能给Blog程序的作者们提供一丁点思路。

2.进行敏感关键词过滤。
为了进一步防止通过人工方式对某个Blog(甚至某个Blog系统)进行某些有“特殊目的”的SPAM,需要对Trackback以及留言评论的内容进行过滤。具体到程序上,就是检查接收到的信息中是否有规定的词汇。再细分,则是检查敏感词汇出现的次数是否超过了规定的次数(即敏感度,或者说宽容度)。如果出现违规的词汇,则予以拒绝。
为什么要采用一个“宽容度”设定呢?请看下面两句话:“Google Earth是Google提供的免费地图服务”、“免费激情小电影 观看免费电影”。同样是“免费”这个词语,出现在正常的句子当中和出现在广告SPAM中的频率是不同的。经过观察,在正常句子中“免费”出现的频率较小,而出现在广告中的时候则很可能大量出现。若没有宽容度,只要出现“免费”就一律杀掉,未免错杀无辜;若不过滤,则很可能漏掉广告。
下面是Waki-Blog的过滤代码:
function bad_word_detect($str){
include_once("./include/badword.php");
//英语垃圾词检查
$message_for_check_en = str_word_count(strtolower(preg_replace('~[^A-Z ]~i', '', $str)),1);
if(count(array_intersect($message_for_check_en,$bad_word_en)) > 0) return true;

//中文垃圾词检查
$message_for_check_cn = str_replace($bad_sign,"",preg_replace('~[A-Za-z0-9 ]~i', '', $str));
for ($i=0;$i<count($bad_word_cn);$i++){
if (substr_count($message_for_check_cn, $bad_word_cn[$i][0]) >= $bad_word_cn[$i][1]) {
return true;
}
}
}
Waki-Blog分别对英文和非英语敏感词汇进行过滤。敏感词汇列表储存在badword.php中,可以随时扩充。
(1)英文关键字过滤:
首先使用正则表达式过滤掉除大小写英文字母外的全部字符。之后使用PHP内建函数strtolower将全部字母转换为小写(防止使用类似pORn的乱序大小写来蒙混过关)。之后用str_word_count来分词,全部词语转换为数组$message_for_check_en,之后用array_intersect求其与$bad_word_en数组的交集,若存在交集,则判断内容中包含敏感词语,函数返回true。
(2)中文关键词过滤:
比起英文关键词过滤,因为中文关键词过滤引入了宽容度问题,所以要稍微复杂一些。
首先将所有的英文字母、0~9的阿拉伯数字、英文符号、中文符号都过滤掉组成纯非英语字符串$message_for_check_cn。之后进入循环,逐个检查每个敏感关键词在字符串中的含量。若发现超过宽容度的出现次数,则立即返回true中止循环。
这种方法虽然有些花费系统资源,但是过滤效果和灵活度方面都好一些。而且,这种方式的应用不仅限于此,如果将某些经常发广告的网站的网址列入敏感字符列表中,将容忍度设置为1(只要出现一次就block),那么敏感字符列表便充当了黑名单的作用。
当然,这种过滤方式当然也存在一些不足。比如无法防止汉字同音字代替,偏旁部首拼字等等的比较极端的办法,但防护一般的SPAM还是足够的。因为语言天生的复杂性,除非使用机器分词、语法语义分析、统计学分析过滤等等的技术,SPAM是没办法从根本上过滤的。然而遗憾的是,目前这些技术本身就不是很成熟,应用在SPAM过滤上就更有难度了。

越高级复杂的过滤与防护只能催生出来更加变本加厉的SPAM办法。在想办法不断对付没完没了的SPAM的同时,为什么不倡导响应中央“文明办网”的号召,让广大网站的发展都“文明”起来,不要SPAM呢?

选修课与旧书

Image
今天在大四学生的书摊上买了两本旧书,《摄影技术教程》和《日本历史》,前者原价¥32,后者原价¥13.8,买的时候一共花了¥15,还是很划算的。
下学期要求修4学分的选修课,我就选了摄影技术(2分)、日本地理(2分)、Linux操作系统(3分)。
《摄影技术教程》正好是下学期上课的教材,而《日本历史》是大三的必修课,所以也顺便买了回来。在大四学生的书摊上经常能买到一些非常超值的二手书。比如前些天买的《幕末新撰組》(池波正太郎,早春文库),定价590円,只花了5块钱就买了回来。