03月 21, 2013

上一次,我用TF-IDF算法自动提取关键词

今天,我们再来研究另一个相关的问题。有些时候,除了找到关键词,我们还希望找到与原文章相似的其他文章。比如,”Google新闻”在主新闻下方,还提供多条相似的新闻。

为了找出相似的文章,需要用到”余弦相似性“(cosine similiarity)。下面,我举一个例子来说明,什么是”余弦相似性”。

为了简单起见,我们先从句子着手。

句子A:我喜欢看电视,不喜欢看电影。

句子B:我不喜欢看电视,也不喜欢看电影。

请问怎样才能计算上面两句话的相似程度?

基本思路是:如果这两句话的用词越相似,它们的内容就应该越相似。因此,可以从词频入手,计算它们的相似程度。

第一步,分词

句子A:我/喜欢/看/电视,不/喜欢/看/电影。

句子B:我/不/喜欢/看/电视,也/不/喜欢/看/电影。

第二步,列出所有的词

我,喜欢,看,电视,电影,不,也。

第三步,计算词频

句子A:我 1,喜欢 2,看 2,电视 1,电影 1,不 1,也 0。

句子B:我 1,喜欢 2,看 2,电视 1,电影 1,不 2,也 1。

第四步,写出词频向量

句子A:[1, 2, 2, 1, 1, 1, 0]

句子B:[1, 2, 2, 1, 1, 2, 1]

到这里,问题就变成了如何计算这两个向量的相似程度。

我们可以把它们想象成空间中的两条线段,都是从原点([0, 0, ...])出发,指向不同的方向。两条线段之间形成一个夹角,如果夹角为0度,意味着方向相同、线段重合;如果夹角为90度,意味着形成直角,方向完全不相似;如果夹角为180度,意味着方向正好相反。因此,我们可以通过夹角的大小,来判断向量的相似程度。夹角越小,就代表越相似

以二维空间为例,上图的a和b是两个向量,我们要计算它们的夹角θ。余弦定理告诉我们,可以用下面的公式求得:

假定a向量是[x1, y1],b向量是[x2, y2],那么可以将余弦定理改写成下面的形式:

数学家已经证明,余弦的这种计算方法对n维向量也成立。假定A和B是两个n维向量,A是 [A1, A2, ..., An] ,B是 [B1, B2, ..., Bn] ,则A与B的夹角θ的余弦等于:

使用这个公式,我们就可以得到,句子A与句子B的夹角的余弦。

余弦值越接近1,就表明夹角越接近0度,也就是两个向量越相似,这就叫”余弦相似性”。所以,上面的句子A和句子B是很相似的,事实上它们的夹角大约为20.3度。

由此,我们就得到了”找出相似文章”的一种算法:

(1)使用TF-IDF算法,找出两篇文章的关键词;

(2)每篇文章各取出若干个关键词(比如20个),合并成一个集合,计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频);

(3)生成两篇文章各自的词频向量;

(4)计算两个向量的余弦相似度,值越大就表示越相似。

“余弦相似度”是一种非常有用的算法,只要是计算两个向量的相似程度,都可以采用它。

下一次,我想谈谈如何在词频统计的基础上,自动生成一篇文章的摘要。

Tags: ,.

这个标题看上去好像很复杂,其实我要谈的是一个很简单的问题。

有一篇很长的文章,我要用计算机提取它的关键词(Automatic Keyphrase extraction),完全不加以人工干预,请问怎样才能正确做到?

这个问题涉及到数据挖掘文本处理信息检索等很多计算机前沿领域,但是出乎意料的是,有一个非常简单的经典算法,可以给出令人相当满意的结果。它简单到都不需要高等数学,普通人只用10分钟就可以理解,这就是我今天想要介绍的TF-IDF算法

让我们从一个实例开始讲起。假定现在有一篇长文《中国的蜜蜂养殖》,我们准备用计算机提取它的关键词。

一个容易想到的思路,就是找到出现次数最多的词。如果某个词很重要,它应该在这篇文章中多次出现。于是,我们进行”词频”(Term Frequency,缩写为TF)统计。

结果你肯定猜到了,出现次数最多的词是—-”的”、”是”、”在”—-这一类最常用的词。它们叫做”停用词”(stop words),表示对找到结果毫无帮助、必须过滤掉的词。

假设我们把它们都过滤掉了,只考虑剩下的有实际意义的词。这样又会遇到了另一个问题,我们可能发现”中国”、”蜜蜂”、”养殖”这三个词的出现次数一样多。这是不是意味着,作为关键词,它们的重要性是一样的?

显然不是这样。因为”中国”是很常见的词,相对而言,”蜜蜂”和”养殖”不那么常见。如果这三个词在一篇文章的出现次数一样多,有理由认为,”蜜蜂”和”养殖”的重要程度要大于”中国”,也就是说,在关键词排序上面,”蜜蜂”和”养殖”应该排在”中国”的前面。

所以,我们需要一个重要性调整系数,衡量一个词是不是常见词。如果某个词比较少见,但是它在这篇文章中多次出现,那么它很可能就反映了这篇文章的特性,正是我们所需要的关键词

用统计学语言表达,就是在词频的基础上,要对每个词分配一个”重要性”权重。最常见的词(“的”、”是”、”在”)给予最小的权重,较常见的词(“中国”)给予较小的权重,较少见的词(“蜜蜂”、”养殖”)给予较大的权重。这个权重叫做”逆文档频率“(Inverse Document Frequency,缩写为IDF),它的大小与一个词的常见程度成反比。

知道了”词频”(TF)和”逆文档频率”(IDF)以后,将这两个值相乘,就得到了一个词的TF-IDF值。某个词对文章的重要性越高,它的TF-IDF值就越大。所以,排在最前面的几个词,就是这篇文章的关键词。

下面就是这个算法的细节。

第一步,计算词频

考虑到文章有长短之分,为了便于不同文章的比较,进行”词频”标准化。

或者

第二步,计算逆文档频率

这时,需要一个语料库(corpus),用来模拟语言的使用环境。

如果一个词越常见,那么分母就越大,逆文档频率就越小越接近0。分母之所以要加1,是为了避免分母为0(即所有文档都不包含该词)。log表示对得到的值取对数。

第三步,计算TF-IDF

可以看到,TF-IDF与一个词在文档中的出现次数成正比,与该词在整个语言中的出现次数成反比。所以,自动提取关键词的算法就很清楚了,就是计算出文档的每个词的TF-IDF值,然后按降序排列,取排在最前面的几个词。

还是以《中国的蜜蜂养殖》为例,假定该文长度为1000个词,”中国”、”蜜蜂”、”养殖”各出现20次,则这三个词的”词频”(TF)都为0.02。然后,搜索Google发现,包含”的”字的网页共有250亿张,假定这就是中文网页总数。包含”中国”的网页共有62.3亿张,包含”蜜蜂”的网页为0.484亿张,包含”养殖”的网页为0.973亿张。则它们的逆文档频率(IDF)和TF-IDF如下:

从上表可见,”蜜蜂”的TF-IDF值最高,”养殖”其次,”中国”最低。(如果还计算”的”字的TF-IDF,那将是一个极其接近0的值。)所以,如果只选择一个词,”蜜蜂”就是这篇文章的关键词。

除了自动提取关键词,TF-IDF算法还可以用于许多别的地方。比如,信息检索时,对于每个文档,都可以分别计算一组搜索词(“中国”、”蜜蜂”、”养殖”)的TF-IDF,将它们相加,就可以得到整个文档的TF-IDF。这个值最高的文档就是与搜索词最相关的文档。

TF-IDF算法的优点是简单快速,结果比较符合实际情况。缺点是,单纯以”词频”衡量一个词的重要性,不够全面,有时重要的词可能出现次数并不多。而且,这种算法无法体现词的位置信息,出现位置靠前的词与出现位置靠后的词,都被视为重要性相同,这是不正确的。(一种解决方法是,对全文的第一段和每一段的第一句话,给予较大的权重。)

下一次,我将用TF-IDF结合余弦相似性,衡量文档之间的相似程度

Tags: ,.
01月 31, 2013

软件开发是”抽象化”原则(Abstraction)的一种体现。

所谓”抽象化”,就是指从具体问题中,提取出具有共性的模式,再使用通用的解决方法加以处理。

开发软件的时候,一方面,我们总是希望使用别人已经写好的代码,另一方面,又希望自己写的代码尽可能重用,以求减少工作量。要做到这两个目标,这需要”抽象化”。

最近,我读到美国程序员Derick Bailey的一篇文章,谈到“抽象化”应该遵循的三个原则,觉得很有启发。

一、DRY原则

DRY是 Don’t repeat yourself 的缩写,意思是”不要重复自己”。

软件工程名著《The Pragmatic Programmer》首先提出了这个原则。它的涵义是,系统的每一个功能都应该有唯一的实现。也就是说,如果多次遇到同样的问题,就应该抽象出一个共同的解决方法,不要重复开发同样的功能。

这个原则有时也称为”一次且仅一次”原则(Once and Only Once)。

二、YAGNI原则

YAGNI是 You aren’t gonna need it 的缩写,意思是”你不会需要它”。

这是”极限编程”提倡的原则,指的是你自以为有用的功能,实际上都是用不到的。因此,除了最核心的功能,其他功能一概不要部署,这样可以大大加快开发。

它背后的指导思想,就是尽可能快、尽可能简单地让软件运行起来(do the simplest thing that could possibly work)。

但是,这里出现了一个问题。仔细推敲的话,你会发现DRY原则和YAGNI原则并非完全兼容。前者追求”抽象化”,要求找到通用的解决方法;后者追求”快和省”,意味着不要把精力放在抽象化上面,因为很可能”你不会需要它”。所以,就有了第三个原则。

三、Rule Of Three原则

Rule of three 称为”三次原则”,指的是当某个功能第三次出现时,才进行”抽象化”。

这是软件开发大家Martin Fowler在《Refactoring》一书中提出的。

它的涵义是,第一次用到某个功能时,你写一个特定的解决方法;第二次又用到的时候,你拷贝上一次的代码;第三次出现的时候,你才着手”抽象化”,写出通用的解决方法。

这样做有几个理由:

(1)省事。如果一种功能只有一到两个地方会用到,就不需要在”抽象化”上面耗费时间了。

(2)容易发现模式。”抽象化”需要找到问题的模式,问题出现的场合越多,就越容易看出模式,从而可以更准确地”抽象化”。

比如,对于一个数列来说,两个元素不足以判断出规律:

1, 2, _, _, _, _,

第三个元素出现后,规律就变得较清晰了:

1, 2, 4, _, _, _,

(3)防止过度冗余。如果一种功能同时有多个实现,管理起来非常麻烦,修改的时候需要修改多处。在实际工作中,重复实现最多可以容忍出现一次,再多就无法接受了。

综上所述,”三次原则”是DRY原则和YAGNI原则的折衷,是代码冗余和开发成本的平衡点,值得我们在”抽象化”时遵循。

Tags: ,,,.
12月 26, 2012

2009年,30岁的瑞典程序员Markus Persson写了一个小游戏Minecraft

这个游戏模拟了一个虚拟世界,玩家可以在里面无尽地漫游。

你看到各种别人建造的地标,也可以自己动手,随心所欲地建造自己的地标。

这个游戏大获成功,很多人试玩后都想购买。2010年9月,Markus Persson决定辞职,与朋友合资成立Mojang(瑞典语”组件”的意思)游戏公司,专职开发Minecraft。

看到这里,你可能以为,这篇文章讲的是Minecraft的故事。不是的,我其实要讲的是另一个故事。

早在2005年,美国波特兰有三个爱打游戏的年轻人。他们成立了一家名为2 Player Productions(简称2PP)的制片工作室,专门拍摄电子游戏的制作过程。

三个成员平时都有自己的工作,只有确定题材以后,才会凑时间动工拍摄,平均每年生产一部作品。当他们看到Mojang成立的消息,意识到这可能是一个重大事件,决定跟拍Mojang的第一年。可是,他们没钱,必须找到愿意资助这个项目的人。

2011年2月21日,他们把这个项目放上了融资网站Kickstarter,附上一段20分钟的试拍样片,恳求资助。《项目介绍》这样写道:

“本片将第一次深入展示,一家游戏软件公司在成立后第一年遭遇的挑战和取得的成绩。我们将分析Minecraft史无前例的成功,采访新闻记者和行业专家,访问游戏玩家。

您的资助将帮助我们前往瑞典和别的地方,使我们可以雇佣人手,制作特效,聘请原创配乐。”

资助者获得的回报如下:

原计划是4星期筹集15万美元,结果反响热烈超乎想象。2011年3月26日截止时,一共有3631人捐款,总金额21万297美元。捐款人数排在Kickstarter有史以来第三位。

有了这笔钱,2PP终于可以去瑞典拍摄Mojang的第一年了。事实证明,这是一个正确决定。在这一年里,Mojang取得了巨大成功,注册玩家达到1600万,游戏拷贝卖出了400万份。这是值得研究和纪念的一年。外界好奇地等待着这部纪录片,想看看这些成绩是如何取得的。

可是,2PP一直拖到三天前(2012年12月22日)才宣布正式上市:DVD套装定价20美元,视频文件下载定价8美元,音轨定价7美元。

令人震惊的是,第二天(12月23日)2PP就把这部电影放上了全世界最大的文件分享网站”海盗湾”,允许免费下载。说明档是这样写的:

“我们是这部纪录片的拍摄者,希望也是它的第一个上传者。因为我们知道,它迟早会被人放到这里,那还不如我们自己来放,希望你们能够看完下面的话。

盗版是一种生活方式,虽然无法在短期内得到推广,还可能受到惩罚,但是我们的态度比较现实。

我们都看过盗版电影,有时也确实需要盗版。比如,你可能没钱买DVD,也可能想在购买前试看一下,或者因为对我们的一些做法不满,盗版表示抗议。这些理由都很好。但是如果你盗版只是为了获取视频文件,那么请考虑购买我们的无DRM的版本,下载后可用任何方式观看。

我们只是三个想靠自己的兴趣爱好谋生的年轻人。我们热爱电子游戏,我们渴望让电子游戏变得更真实。如果你购买我们的影片,就是在支持我们的努力。我们之所以把这部影片放到Kickstarter筹款,就是因为我们的钱不够。即使筹款成功,它还是花掉了很大很大一笔我们自己的钱,更不要提我们投入的这两年的劳动了。

请观看这部影片,希望你喜欢它,理解我们想做的事情。请考虑支持我们,购买8美元的下载版或者20美元的DVD。

我们感到很幸运,能与电子游戏行业许多杰出人物共事,拍出我们想拍的电影。请让我们继续走在这条路上,让我们拍出更好的作品。”

下面就是海盗湾的磁力链接,你可以用它下载全片。在这之前,你不妨先看看2分钟预告片:Youtube / Youku。

magnet:?xt=urn:btih:41b2fd2403eba5a1dc23743fb08a15f968ac c1b5&dn=Minecraft%3A+The+Story+of+Mojang&tr=udp% 3A%2F%2Ftracker.openbittorrent.com%3A80&tr=udp%3A%2F %2Ftracker.publicbt.com%3A80&tr=udp%3A%2F%2Ftracker. istole.it%3A6969&tr=udp%3A%2F%2Ftracker.ccc.de%3A80

你下载下来的,是一个2.68GB的MOV高清文件。这是一个盗版,但是它的提供者就是版权所有人。

我觉得,这个事件很有启发。它提供了一个案例,让我们思考在互联网时代,内容提供商如何生存、如何应对盗版。

我从来不相信,强调版权保护、应用各种防盗版措施(比如DRM)是解决之道,但是确实不知道路在何方。在这方面,2PP采用网络融资、自己推动自己的盗版(gangnam style不也是这样吗),这些做法具有探索意义,令人耳目一新,而且具有可操作性,完全可以被其他项目仿效和借鉴。

(完)

Tags: ,,,,.
12月 14, 2012

1.

Kyle Rush是一个网站工程师。

2011年6月,他加入BarackObama.com,负责设计2012美国大选的奥巴马官网。

(图为2011年6月的奥巴马官网)

除了宣传,官网的主要目的就是筹款。

上一次大选,奥巴马筹到了6.9亿美元。这是一个很大的数字,但由于过去4年美国经济一直没有起色,本次大选势必要投入更多的资金,团队内部估计资金需求将达到创纪录的10亿美元。

一个筹集10亿美元的网站,历史上从来没有过。Kyle Rush不知道自己能否做到,但是他很清楚,如果筹不到钱,奥巴马没法赢得大选。

2.

2012年美国大选现在已经结束了,奥巴马有惊无险地击败了罗姆尼。他最终筹到了11亿美元,成为历史上筹款金额最高(也是花钱最多)的总统候选人。(排在第二位的就是罗姆尼,他也筹到了10亿美元。)

这11亿美元之中,线下筹集了4.1亿,线上筹集了6.9亿。单单BarackObama.com一个网站,就创造了2.5亿美元的捐款。

在6个月的时间里,BarackObama.com共有

* 17,807,917个访问者,81,548,259次页面访问

* 4,276,463次捐款

* 捐款转化率24%(每四个访问者,就有一人会捐款)

这样辉煌的成绩,是如何取得的?

3.

制作一个超大流量的、体验良好的、能够说服人们捐款、并能安全快速处理这些捐款的网站、绝非易事。

最近,Kyle Rush写了一篇文章,披露了许多内幕,从技术角度总结了BarackObama.com的制作心得。下面,我们就来看看奥巴马的技术团队是怎么做到的。

(图为2012年5月的奥巴马官网)

网站的制作班子,从2011年下半开始组建,Kyle Rush是第一个加入的前端工程师,负责网页的外观和用户体验。

一开始,网站放在团队自购的服务器上,运行和捐款都还算平稳。但是,随着竞争不断加剧,局势变得令人担忧了。到了2012年5月,罗姆尼当月的筹款金额第一次超过了奥巴马。

竞选总部决定,网站必须改版,尽一切可能争取捐款。于是,技术团队开始大规模的扩充,全职的前端工程师从1个人扩充到了14个人,其中6人专门负责制作筹款页面。

4.

技术团队做出的第一个决定是,使用静态网站生成器Jekyll,用静态网页取代动态网页,加快网页打开速度。网站的打开应该越快越好。有研究称,打开速度每慢100毫秒,Amazon的销售额就下降1%。

第二个决定是,将全部网页放上CDN,使用的服务商是Akamai。它是世界最大的CDN供应商,共部署了50000多台服务器,美国各地都能获得理想的访问速度。奥巴马芝加哥竞选总部,可以在20毫秒内载入官网的HTML网页。

第三个决定是,将捐款的后台做成API调用。这是因为有23%的访问者使用移动设备,所以必须部署多个前端(Web端和移动端)。使用API,可以让不同前端以相同方式与后台通信,彼此之间用JSON格式传递信息。

第四个决定是,后台用PHP语言开发,放在Amazon的EC2平台上。

第五个决定是,为了避免宕机,开发两个后台。一旦一个系统停止工作,立刻自动切换到另一个。这点很重要,因为宕机不仅影响士气,而且经济损失巨大。因为捐款每分钟都在涌入,最高记录是一小时300万美元,你不能让它停下来。

5.

新网站初步完成后,使用webpagetest.org进行测试,结果令人鼓舞。

原版页面4秒钟后还没载入,新版只用1秒就可以看到。整个平台的访问速度上升了60%,捐款转化率增加了14%。

接下来,就是微调页面的各种细节,一共进行了240次a/b测试,也就是说,至少迭代了240个版本。

调整后的页面,视觉效果和用户体验都有了巨大的提升(点击看大图),捐款转化率因此又提高了49%。。

随着奥巴马的当选,BarackObama.com共进行了1101次前端部署。

6.

事实证明,整个开发方案非常成功,顺利完成筹款任务,没有一分钟宕机。

Kyle Rush感到有必要总结,留下记录。除了上面的开发过程,他还提到前端团队使用的工具:版本控制Github ,a/b测试管理Optimizely,代码编译CodeKit。

Kyle Rush最后总结说:

“我百分之百肯定,这是我经历过的最好的开发环境。我们不断调整,捐款转化率的提高令人难以置信。整个团队感到无比满足。但是,最高兴的还是看到,2013年1月21日巴拉克·奥巴马依然是美国总统!”

Tags: ,,,.
12月 6, 2012

上个月(11月13日),83岁的柯达公司退休工程师布赖斯·拜尔(Bryce Bayer)去世。

一家国内杂志邀请我写纪念文章,回顾他对数码摄影的巨大贡献。

我看了一些材料,觉得这个题材很有意思,涉及数码相机的成像原理,使我对数字图像技术有了新的认识。但是,由于体例限制,杂志不允许我插入彩图。

下面,我把我的那篇文章配上图片,解释彩色数码照片是怎么拍出来的。
1.

为了更好地理解原理,让我们从照片的起源讲起。1825年,法国人涅普斯(Joseph Nicéphore Nièpce),拍出历史上第一张照片。
2.

他采用的感光剂是氯化银(silver chloride)。当光线照射氯化银,后者会分解成纯银和氯气,纯银在空气中很快氧化变成黑色。因此,底片颜色越深代表光线越强,颜色越浅代表光线越弱。黑白照片就是这样拍出来。
3.

19世纪中期,人们发现,人眼的圆锥细胞对三种颜色—-红、绿、蓝—-特别敏感。伟大的英国物理学家麦克斯韦因此假设,红绿蓝作为基色,可以拍出彩色照片。
4.

1861年,在麦克斯韦的指导下,人类的第一张彩色照片诞生了。
采用的方法是在镜头前,分别用红丝带、绿丝带、蓝丝带过滤光线,曝光形成三张底片,然后用三部放映机向同一处投影这三张底片,每部放映机的镜头前都拧上对应颜色的镜头,它们的合成效果就是一张彩照。
5.

真正意义上的彩色胶卷,1933年诞生于柯达公司,底片之上依次有三个感光层,分别对红、绿、蓝三种颜色进行曝光,最后叠加形成一张彩色底片。
6.

二战后,计算机诞生,科学家发现图像可以用数字形式表示。如果将光信号转变成电信号,就可以直接拍出数码照片。这意味着,照相机不再需要胶卷,而是需要一个图像传感器(image sensor)。
7.

图像传感器将光线转化成电流,光线越亮,电流的数值就越大;光线越暗,电流的数值就越小。所以,如果用0到255的范围,表示光线的亮度,最亮的光线是白光,数值是十六进制的FF,最暗的光线是黑光(没有光),数值是十六进制的00。
8.

图像传感器的表面,分成若干个捕捉点,每个点都会产生一个数值,表示该点感受到的光线亮度,这就叫做”像素”。像素越多,图像细节就越丰富。如果一台照机的像素是1600×1200,就说明图像传感器横向有1600个捕捉点,纵向有1200个,合计192万个。
9.

但是,图像传感器有一个很严重的缺陷:它只能感受光的强弱,无法感受光的波长。由于光的颜色由波长决定,所以图像传播器无法记录颜色,也就是说,它只能拍黑白照片,这肯定是不能接受的。
10.

一种解决方案是照相机内置三个图像传感器,分别记录红、绿、蓝三种颜色,然后再将这三个值合并。这种方法能产生最准确的颜色信息,但是成本太高,无法投入实用。
11.

1974年,柯达公司的工程师布赖斯·拜尔提出了一个全新方案,只用一块图像传感器,就解决了颜色的识别。他的做法是在图像传感器前面,设置一个滤光层(Color filter array),上面布满了滤光点,与下层的像素一一对应。也就是说,如果传感器是1600×1200像素,那么它的上层就有1600×1200个滤光点。
12.

每个滤光点只能通过红、绿、蓝之中的一种颜色,这意味着在它下层的像素点只可能有四种颜色:红、绿、蓝、黑(表示没有任何光通过)。
13.

不同颜色的滤光点的排列是有规律的:每个绿点的四周,分布着2个红点、2个蓝点、4个绿点。这意味着,整体上,绿点的数量是其他两种颜色点的两倍。这是因为研究显示人眼对绿色最敏感,所以滤光层的绿点最多。
14.

接下来的问题就是,如果一个像素只可能有四种颜色,那么怎么能拍出彩色照片呢?这就是布赖斯·拜尔聪明的地方,前面说了,每个滤光点周围有规律地分布其他颜色的滤光点,那么就有可能结合它们的值,判断出光线本来的颜色。以黄光为例,它由红光和绿光混合而成,那么通过滤光层以后,红点和绿点下面的像素都会有值,但是蓝点下面的像素没有值,因此看一个像素周围的颜色分布—-有红色和绿色,但是没有蓝色—-就可以推测出来这个像素点的本来颜色应该是黄色。
15.

这种计算颜色的方法,就叫做”去马赛克”(demosaicing)。上图的下半部分是图像传感器生成的”马赛克”图像,所有的像素只有红、绿、蓝、黑四种颜色;上半部分是”去马赛克”后的效果,这是用算法处理的结果。
16.

虽然,每个像素的颜色都是算出来的,并不是真正的值,但是由于计算的结果相当准确,因此这种做法得到广泛应用。目前,绝大部分的数码相机都采用它,来生成彩色数码照片。高级的数码相机,还提供未经算法处理的原始马赛克图像,这就是raw格式(raw image format)。
为了纪念发明者布赖斯·拜尔,它被称作”拜尔模式”或”拜尔滤光法” (Bayer filter)。
(完)

Tags: ,,,.
11月 30, 2012

几个月前,我介绍了Sass的用法。

Sass是一种”CSS预处理器”,可以让CSS的开发变得简单和可维护。但是,只有搭配Compass,它才能显出真正的威力。

本文介绍Compass的用法。毫不夸张地说,学会了Compass,你的CSS开发效率会上一个台阶。

本文假设你已经掌握了CSS的主要用法,如果你还懂Sass,那就更好了。但是不懂Sass,一样可以阅读本文。

一、Compass是什么?

简单说,Compass是Sass的工具库(toolkit)。

Sass本身只是一个编译器,Compass在它的基础上,封装了一系列有用的模块和模板,补充Sass的功能。它们之间的关系,有点像Javascript和jQuery、Ruby和Rails、python和Django的关系。

二、安装

Compass是用Ruby语言开发的,所以安装它之前,必须安装Ruby。

假定你的机器(Linux或OS X)已经安装好Ruby,那么在命令行模式下键入:

sudo gem install compass

如果你用的是Windows系统,那么要省略前面的sudo。

正常情况下,Compass(连同Sass)就安装好了。

三、项目初始化

接下来,要创建一个你的Compass项目,假定它的名字叫做myproject,那么在命令行键入:

compass create myproject

当前目录中就会生成一个myproject子目录。

进入该目录:

cd myproject

你会看到,里面有一个config.rb文件,这是你的项目的配置文件。还有两个子目录sass和stylesheets,前者存放Sass源文件,后者存放编译后的css文件。

接下来,就可以动手写代码了。

四、编译

在写代码之前,我们还要知道如何编译。因为我们写出来的是后缀名为scss的文件,只有编译成css文件,才能用在网站上。
Compass的编译命令是

compass compile

该命令在项目根目录下运行,会将sass子目录中的scss文件,编译成css文件,保存在stylesheets子目录中。

默认状态下,编译出来的css文件带有大量的注释。但是,生产环境需要压缩后的css文件,这时要使用–output-style参数。

compass compile –output-style compressed

Compass只编译发生变动的文件,如果你要重新编译未变动的文件,需要使用–force参数。

compass compile –force

除了一次性编译命令,compass还有自动编译命令

compass watch

运行该命令后,只要scss文件发生变化,就会被自动编译成css文件。

更多的compass命令行用法,请参考官方文档。

五、Compass的模块

Compass采用模块结构,不同模块提供不同的功能。目前,它内置五个模块:

* reset
* css3
* layout
* typography
* utilities

下面,我依次介绍这五个内置模块。它们提供Compass的主要功能,但是除了它们,你还可以自行加载网上的第三方模块,或者自己动手编写模块。

六、reset模块

通常,编写自己的样式之前,有必要重置浏览器的默认样式。

写法是

@import “compass/reset”;

上面的@import命令,用来指定加载模块,这里就是加载reset模块。编译后,会生成相应的css reset代码。

七、CSS3模块

目前,该模块提供19种CSS3命令。在这里,我介绍其中的三种:圆角、透明和行内区块。

7.1 圆角

圆角(border-radius)的写法是

@import “compass/css3″;
.rounded {
@include border-radius(5px);
}

上面的@include命令,表示调用某个mixin(类似于C语言的宏),5px是参数,这里用来指定圆角的半径。
编译后的代码为

.rounded {
-moz-border-radius: 5px;
-webkit-border-radius: 5px;
-o-border-radius: 5px;
-ms-border-radius: 5px;
-khtml-border-radius: 5px;
border-radius: 5px;
}

如果只需要左上角为圆角,写法为

@include border-corner-radius(top, left, 5px);

7.2 透明

透明(opacity)的写法为

@import “compass/css3″;
#opacity {
@include opacity(0.5);
}
编译后生成
#opacity {
filter: progid:DXImageTransform.Microsoft.Alpha(Opacity=0.5);
opacity: 0.5;
}

opacity的参数0.5,表示透明度为50%。

完全透明的写法是

@include opacity(0);

完全不透明则是

@include opacity(1);

7.3 行内区块

行内区块(inline-block)的写法为

@import “compass/css3″;
#inline-block {
@include inline-block;
}

编译后生成

#inline-block {
display: -moz-inline-stack;
display: inline-block;
vertical-align: middle;
*vertical-align: auto;
zoom: 1;
*display: inline;
}

八、layout模块

该模块提供布局功能。

比如,指定页面的footer部分总是出现在浏览器最底端:

@import “compass/layout”;
#footer {
@include sticky-footer(54px);
}

又比如,指定子元素占满父元素的空间:

@import “compass/layout”;
#stretch-full {
@include stretch;
}

九、typography模块

该模块提供版式功能。

比如,指定链接颜色的mixin为:

link-colors($normal, $hover, $active, $visited, $focus);

使用时写成:

@import “compass/typography”;
a {
@include link-colors(#00c, #0cc, #c0c, #ccc, #cc0);
}

十、utilities模块

该模块提供某些不属于其他模块的功能。

比如,清除浮动:
import “compass/utilities/”;
.clearfix {
@include clearfix;
}

再比如,表格:

@import “compass/utilities”;
table {
@include table-scaffolding;
}

编译后生成

table th {
text-align: center;
font-weight: bold;
}
table td,
table th {
padding: 2px;
}
table td.numeric,
table th.numeric {
text-align: right;
}

十一、Helper函数

除了模块,Compass还提供一系列函数。

有些函数非常有用,比如image-width()和image-height()返回图片的宽和高。

再比如,inline-image()可以将图片转为data协议的数据。

@import “compass”;
.icon { background-image: inline-image(“icon.png”);}

编译后得到

.icon { background-image: url(‘data:image/png;base64,iBROR…QmCC’);}

函数与mixin的主要区别是,不需要使用@include命令,可以直接调用。

(完)

Tags: ,,,.
11月 15, 2012

文/iDoNews资深作者 阮一峰

通常,图像处理软件会提供”模糊”(blur)滤镜,使图片产生模糊的效果。

“模糊”的算法有很多种,其中有一种叫做”高斯模糊”(Gaussian Blur)。它将正态分布(又名”高斯分布”)用于图像处理。

本文介绍”高斯模糊”的算法,你会看到这是一个非常简单易懂的算法。本质上,它是一种数据平滑技术(data smoothing),适用于多个场合,图像处理恰好提供了一个直观的应用实例。

一、高斯模糊的原理

所谓”模糊”,可以理解成每一个像素都取周边像素的平均值。

上图中,2是中间点,周边点都是1。

“中间点”取”周围点”的平均值,就会变成1。在数值上,这是一种”平滑化”。在图形上,就相当于产生”模糊”效果,”中间点”失去细节。

显然,计算平均值时,取值范围最大,”模糊效果”越强烈。

上面分别是原图、模糊半径3像素、模糊半径10像素的效果。模糊半径越大,图像就越模糊。从数值角度看,就是数值越平滑。

接下来的问题就是,既然每个点都要取周边像素的平均值,那么应该如何分配权重呢?

如果使用简单平均,显然不是很合理,因为图像都是连续的,越靠近的点关系越密切,越远离的点关系越疏远。因此,加权平均更合理,距离越近的点权重越大,距离越远的点权重越小。

二、正态分布的权重

正态分布显然是一种可取的权重分配模式。

在图形上,正态分布是一种钟形曲线,越接近中心,取值越大,越远离中心,取值越小。

计算平均值的时候,我们只需要将”中心点”作为原点,其他点按照其在正态曲线上的位置,分配权重,就可以得到一个加权平均值。

三、高斯函数

上面的正态分布是一维的,图像都是二维的,所以我们需要二维的正态分布。

正态分布的密度函数叫做”高斯函数”(Gaussian function)。它的一维形式是:

其中,μ是x的均值,σ是x的方差。因为计算平均值的时候,中心点就是原点,所以μ等于0。

根据一维高斯函数,可以推导得到二维高斯函数:

有了这个函数 ,就可以计算每个点的权重了。

四、权重矩阵

假定中心点的坐标是(0,0),那么距离它最近的8个点的坐标如下:

更远的点以此类推。

为了计算权重矩阵,需要设定σ的值。假定σ=1.5,则模糊半径为1的权重矩阵如下:

这9个点的权重总和等于0.4787147,如果只计算这9个点的加权平均,还必须让它们的权重之和等于1,因此上面9个值还要分别除以0.4787147,得到最终的权重矩阵。

五、计算高斯模糊

有了权重矩阵,就可以计算高斯模糊的值了。

假设现有9个像素点,灰度值(0-255)如下:

每个点乘以自己的权重值:

得到

将这9个值加起来,就是中心点的高斯模糊的值。

对所有点重复这个过程,就得到了高斯模糊后的图像。如果原图是彩色图片,可以对RGB三个通道分别做高斯模糊。

六、边界点的处理

如果一个点处于边界,周边没有足够的点,怎么办?

一个变通方法,就是把已有的点拷贝到另一面的对应位置,模拟出完整的矩阵。

七、参考文献

How to program a Gaussian Blur without using 3rd party libraries

======带个自私自利的小AD=========

只需你花一分钟,让业界听到你回声。如果你有更加丰满、独特的个性化点评视角,欢迎奔跑加入iDoNews点评团,私信@沸话小欧 即可。

转载请注明DoNews资深作者/阮一峰

Tags: ,,.
11月 8, 2012

文/DoNews资深作者 阮一峰

这个系列的第一部分第二部分,介绍了Javascript模块原型和理论概念,今天介绍如何将它们用于实战。

我采用的是一个非常流行的库require.js。

一、为什么要用require.js?

最早的时候,所有Javascript代码都写在一个文件里面,只要加载这一个文件就够了。后来,代码越来越多,一个文件不够了,必须分成多个文件,依次加载。下面的网页代码,相信很多人都见过。

<script src=”1.js”></script>
<script src=”2.js”></script>
<script src=”3.js”></script>
<script src=”4.js”></script>
<script src=”5.js”></script>
<script src=”6.js”></script>

这段代码依次加载多个js文件。

这样的写法有很大的缺点。首先,加载的时候,浏览器会停止网页渲染,加载文件越多,网页失去响应的时间就会越长;其次,由于js文件之间存在依赖关系,因此必须严格保证加载顺序(比如上例的1.js要在2.js的前面),依赖性最大的模块一定要放到最后加载,当依赖关系很复杂的时候,代码的编写和维护都会变得困难。

require.js的诞生,就是为了解决这两个问题:

(1)实现js文件的异步加载,避免网页失去响应;

(2)管理模块之间的依赖性,便于代码的编写和维护。

二、require.js的加载

使用require.js的第一步,是先去官方网站下载最新版本。

下载后,假定把它放在js子目录下面,就可以加载了。

<script src=”js/require.js”></script>

有人可能会想到,加载这个文件,也可能造成网页失去响应。解决办法有两个,一个是把它放在网页底部加载,另一个是写成下面这样:

<script src=”js/require.js” defer async=”true” ></script>

async属性表明这个文件需要异步加载,避免网页失去响应。IE不支持这个属性,只支持defer,所以把defer也写上。

加载require.js以后,下一步就要加载我们自己的代码了。假定我们自己的代码文件是main.js,也放在js目录下面。那么,只需要写成下面这样就行了:

<script src=”js/require.js” data-main=”js/main”></script>

data-main属性的作用是,指定网页程序的主模块。在上例中,就是js目录下面的main.js,这个文件会第一个被require.js加载。由于require.js默认的文件后缀名是js,所以可以把main.js简写成main。

三、主模块的写法

上一节的main.js,我把它称为”主模块”,意思是整个网页的入口代码。它有点像C语言的main()函数,所有代码都从这儿开始运行。

下面就来看,怎么写main.js。

如果我们的代码不依赖任何其他模块,那么可以直接写入javascript代码。

// main.js

alert(“加载成功!”);

但这样的话,就没必要使用require.js了。真正常见的情况是,主模块依赖于其他模块,这时就要使用AMD规范定义的的require()函数。

// main.js

require(['moduleA', 'moduleB', 'moduleC'], function (moduleA, moduleB, moduleC){

// some code here

});

require()函数接受两个参数。第一个参数是一个数组,表示所依赖的模块,上例就是['moduleA', 'moduleB', 'moduleC'],即主模块依赖这三个模块;第二个参数是一个回调函数,当前面指定的模块都加载成功后,它将被调用。加载的模块会以参数形式传入该函数,从而在回调函数内部就可以使用这些模块。

require()异步加载moduleA,moduleB和moduleC,浏览器不会失去响应;它指定的回调函数,只有前面的模块都加载成功后,才会运行,解决了依赖性的问题。

下面,我们看一个实际的例子。

假定主模块依赖jquery、underscore和backbone这三个模块,main.js就可以这样写:

require(['jquery', 'underscore', 'backbone'], function ($, _, Backbone){

// some code here

});

require.js会先加载jQuery、underscore和backbone,然后再运行回调函数。主模块的代码就写在回调函数中。

四、模块的加载

上一节最后的示例中,主模块的依赖模块是['jquery', 'underscore', 'backbone']。默认情况下,require.js假定这三个模块与main.js在同一个目录,文件名分别为jquery.js,underscore.js和backbone.js,然后自动加载。

使用require.config()方法,我们可以对模块的加载行为进行自定义。require.config()就写在主模块(main.js)的头部。参数就是一个对象,这个对象的paths属性指定各个模块的加载路径。

require.config({

paths: {

“jquery”: “jquery.min.js”,
“underscore”: “underscore.min.js”,
“backbone”: “backbone.min.js”

}

});

上面的代码给出了三个模块的文件名,路径默认与main.js在同一个目录(js子目录)。如果这些模块在其他目录,比如js/lib目录,则有两种写法。一种是逐一指定路径。

require.config({

paths: {

“jquery”: “lib/jquery.min.js”,
“underscore”: “lib/underscore.min.js”,
“backbone”: “lib/backbone.min.js”

}

});

另一种则是直接改变基目录(baseUrl)。

require.config({

baseUrl: “js/lib”,

paths: {

“jquery”: “jquery.min.js”,
“underscore”: “underscore.min.js”,
“backbone”: “backbone.min.js”

}

});

如果某个模块在另一台主机上,也可以直接指定它的网址,比如:

require.config({

paths: {

“jquery”: “https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min”

}

});

require.js要求,每个模块是一个单独的js文件。这样的话,如果加载多个模块,就会发出多次HTTP请求,会影响网页的加载速度。因此,require.js提供了一个优化工具,当模块部署完毕以后,可以用这个工具将多个模块合并在一个文件中,减少HTTP请求数。

五、AMD模块的写法

require.js加载的模块,采用AMD规范。也就是说,模块必须按照AMD的规定来写。

具体来说,就是模块必须采用特定的define()函数来定义。如果一个模块不依赖其他模块,那么可以直接定义在define()函数之中。

假定现在有一个math.js文件,它定义了一个math模块。那么,math.js就要这样写:

// math.js

define(function (){

var add = function (x,y){

return x+y;

};

return {

add: add
};

});

加载方法如下:

// main.js

require(['math'], function (math){

alert(math.add(1,1));

});

如果这个模块还依赖其他模块,那么define()函数的第一个参数,必须是一个数组,指明该模块的依赖性。

define(['myLib'], function(myLib){

function foo(){

myLib.doSomething();

}

return {

foo : foo

};

});

当require()函数加载上面这个模块的时候,就会先加载myLib.js文件。

六、加载非规范的模块

理论上,require.js加载的模块,必须是按照AMD规范、用define()函数定义的模块。但是实际上,虽然已经有一部分流行的函数库(比如jQuery)符合AMD规范,更多的库并不符合。那么,require.js是否能够加载非规范的模块呢?

回答是可以的。

这样的模块在用require()加载之前,要先用require.config()方法,定义它们的一些特征。

举例来说,underscore和backbone这两个库,都没有采用AMD规范编写。如果要加载它们的话,必须先定义它们的特征。

require.config({

shim: {

‘underscore’:{
exports: ‘_’
},

‘backbone’: {
deps: ['underscore', 'jquery'],
exports: ‘Backbone’
}

}

});

require.config()接受一个配置对象,这个对象除了有前面说过的paths属性之外,还有一个shim属性,专门用来配置不兼容的模块。具体来说,每个模块要定义(1)exports值(输出的变量名),表明这个模块外部调用时的名称;(2)deps数组,表明该模块的依赖性。

比如,jQuery的插件可以这样定义:

shim: {

‘jquery.scroll’: {

deps: ['jquery'],

exports: ‘jQuery.fn.scroll’

}

}

七、require.js插件

require.js还提供一系列插件,实现一些特定的功能。

domready插件,可以让回调函数在页面DOM结构加载完成后再运行。

require(['domready!'], function (doc){

// called once the DOM is ready

});

text和image插件,则是允许require.js加载文本和图片文件。

define([

'text!review.txt',

'image!cat.jpg'

],

function(review,cat){

console.log(review);

document.body.appendChild(cat);

}

);

类似的插件还有json和mdown,用于加载json文件和markdown文件。

(完)

======带个自私自利的小AD=========

欢迎向DoNews投递关于互联网业界的热点类、观点类、趣点类、分析类、爆料类稿件。地址:tougao@donews.com

转载请注明DoNews资深作者/阮一峰

Tags: ,.
10月 31, 2012

文/DoNews资深作者 阮一峰

这个系列的第一部分介绍了Javascript模块的基本写法,今天介绍如何规范地使用模块。

(接上文)

七、模块的规范

先想一想,为什么模块很重要?

因为有了模块,我们就可以更方便地使用别人的代码,想要什么功能,就加载什么模块。

但是,这样做有一个前提,那就是大家必须以同样的方式编写模块,否则你有你的写法,我有我的写法,岂不是乱了套!考虑到Javascript模块现在还没有官方规范,这一点就更重要了。

目前,通行的Javascript模块规范共有两种:CommonJS和AMD。我主要介绍AMD,但是要先从CommonJS讲起。

八、CommonJS

2009年,美国程序员Ryan Dahl创造了node.js项目,将javascript语言用于服务器端编程。

这标志”Javascript模块化编程”正式诞生。因为老实说,在浏览器环境下,没有模块也不是特别大的问题,毕竟网页程序的复杂性有限;但是在服务器端,一定要有模块,与操作系统和其他应用程序互动,否则根本没法编程。

node.js的模块系统,就是参照CommonJS规范实现的。在CommonJS中,有一个全局性方法require(),用于加载模块。假定有一个数学模块math.js,就可以像下面这样加载。

var math = require(‘math’);

然后,就可以调用模块提供的方法:

var math = require(‘math’);

math.add(2,3); // 5

因为这个系列主要针对浏览器编程,不涉及node.js,所以对CommonJS就不多做介绍了。我们在这里只要知道,require()用于加载模块就行了。

九、浏览器环境

有了服务器端模块以后,很自然地,大家就想要客户端模块。而且最好两者能够兼容,一个模块不用修改,在服务器和浏览器都可以运行。

但是,由于一个重大的局限,使得CommonJS规范不适用于浏览器环境。还是上一节的代码,如果在浏览器中运行,会有一个很大的问题,你能看出来吗?

var math = require(‘math’);

math.add(2, 3);

第二行Math.add(2, 3),在第一行require(‘math’)之后运行,因此必须等math.js加载完成。也就是说,如果加载时间很长,整个应用就会停在那里等。

这对服务器端不是一个问题,因为所有的模块都存放在本地硬盘,可以同步加载完成,等待时间就是硬盘的读取时间。但是,对于浏览器,这却是一个大问题,因为模块都放在服务器端,等待时间取决于网速的快慢,可能要等很长时间,浏览器处于”假死”状态。

因此,浏览器端的模块,不能采用”同步加载”(synchronous),只能采用”异步加载”(asynchronous)。这就是AMD规范诞生的背景。

十、AMD

AMD是”Asynchronous Module Definition”的缩写,意思就是”异步模块定义”。它采用异步方式加载模块,模块的加载不影响它后面语句的运行。所有依赖这个模块的语句,都定义在一个回调函数中,等到加载完成之后,这个回调函数才会运行。

AMD也采用require()语句加载模块,但是不同于CommonJS,它要求两个参数:

require([module], callback);

第一个参数[module],是一个数组,里面的成员就是要加载的模块;第二个参数callback,则是加载成功之后的回调函数。如果将前面的代码改写成AMD形式,就是下面这样:

require(['math'], function (math) {

math.add(2, 3);

});

math.add()与math模块加载不是同步的,浏览器不会发生假死。所以很显然,AMD比较适合浏览器环境。

目前,主要有两个Javascript库实现了AMD规范:require.js和curl.js。本系列的第三部分,将通过介绍require.js,进一步讲解AMD的用法,以及如何将模块化编程投入实战。

======带个自私自利的小AD=========

欢迎向DoNews投递关于互联网业界的热点类、观点类、趣点类、分析类、爆料类稿件。地址:tougao@donews.com

转载请注明DoNews资深作者/阮一峰

Tags: ,,.