2011年7月21日星期四

阮一峰的网络日志

阮一峰的网络日志


相似图片搜索的原理

Posted: 21 Jul 2011 01:00 AM PDT

上个月,Google把"相似图片搜索"正式放上了首页。

你可以用一张图片,搜索互联网上所有与它相似的图片。点击搜索框中照相机的图标。

一个对话框会出现。

你输入网片的网址,或者直接上传图片,Google就会找出与其相似的图片。下面这张图片是美国女演员Alyson Hannigan。

上传后,Google返回如下结果:

类似的"相似图片搜索引擎"还有不少,TinEye甚至可以找出照片的拍摄背景。

==========================================================

这种技术的原理是什么?计算机怎么知道两张图片相似呢?

根据Neal Krawetz博士的解释,原理非常简单易懂。我们可以用一个快速算法,就达到基本的效果。

这里的关键技术叫做"感知哈希算法"(Perceptual hash algorithm),它的作用是对每张图片生成一个"指纹"(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。

下面是一个最简单的实现:

第一步,缩小尺寸。

将图片缩小到8x8的尺寸,总共64个像素。这一步的作用是去除图片的细节,只保留结构、明暗等基本信息,摒弃不同尺寸、比例带来的图片差异。

第二步,简化色彩。

将缩小后的图片,转为64级灰度。也就是说,所有像素点总共只有64种颜色。

第三步,计算平均值。

计算所有64个像素的灰度平均值。

第四步,比较像素的灰度。

将每个像素的灰度,与平均值进行比较。大于或等于平均值,记为1;小于平均值,记为0。

第五步,计算哈希值。

将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了。

= = 8f373714acfcf4d0

得到指纹以后,就可以对比不同的图片,看看64位中有多少位是不一样的。在理论上,这等同于计算"汉明距离"(Hamming distance)。如果不相同的数据位不超过5,就说明两张图片很相似;如果大于10,就说明这是两张不同的图片。

具体的代码实现,可以参见Wote用python语言写的imgHash.py。代码很短,只有53行。使用的时候,第一个参数是基准图片,第二个参数是用来比较的其他图片所在的目录,返回结果是两张图片之间不相同的数据位数量(汉明距离)。

这种算法的优点是简单快速,不受图片大小缩放的影响,缺点是图片的内容不能变更。如果在图片上加几个文字,它就认不出来了。所以,它的最佳用途是根据缩略图,找出原图。

实际应用中,往往采用更强大的pHash算法和SIFT算法,它们能够识别图片的变形。只要变形程度不超过25%,它们就能匹配原图。这些算法虽然更复杂,但是原理与上面的简便算法是一样的,就是先将图片转化成Hash字符串,然后再进行比较。

P.S.

我在网站首页加上了一些我喜欢的摄影作品,欢迎参观。

(完)

文档信息

2011年7月17日星期日

阮一峰的网络日志

阮一峰的网络日志


Stephen Wolfram自述

Posted: 16 Jul 2011 08:59 AM PDT

大家听说过Stephen Wolfram(斯蒂芬·沃尔夫勒姆)吗?

了解他的经历和成就吗?

我对他了解不多,但是读了下面这篇2005年的演讲,联想到2009年推出的知识引擎WolframAlpha,我觉得他真是传奇人物,在学术上可能与霍金一个级别。

=======================================================

Stephen Wolfram自述
  ----在Y Combinator创业学校的演讲

时间:2005年10月25日

地点:哈佛大学

翻译:阮一峰

原文:http://www.stephenwolfram.com/publications/recent/ycombinatorschool/


这里是创业学校,所以我觉得,应该跟你们讲一点我开公司的事情。

小时候,我从没想过开公司,我想成为一个物理学家。

(图一:1964年,5岁。)

这方面,我进展得很快,15岁就能发表论文了。

(图二:1976年,17岁,在伊顿公学。)

我一直认为,研究一定要用最好的工具。70年代中期,计算机在英国很稀罕。我第一次接触计算机,用的还是纸带。但是,我很快就成了一个相当厉害的程序员。

接下来几年,我在物理学研究中大量使用计算机。即使我用的是当时最先进的美国计算机,还是不断遇到故障。

二十岁那年,我拿到了博士学位,成为物理学家的梦想进展得很顺利。

(图三:1980年,21岁,博士毕业后立即被加州理工学院聘用。)

但是,我还是想要更好的工具,我明白,唯一的方法就是自己把它们造出来。所以,我就动手了。

1979年,最时髦的计算机语言是C。软件工具的第一个版本花了一年时间,代码有几十万行。主要部分是我写的,剩下的是其他七八个人写的,还有大概五六个人提供过帮助。

那时,我是加州理工学院的研究人员。我首先想到的是,让学校帮忙推广我的软件。这个想法太糟了,引发了许许多多的事情。但是,我在这里不打算说这些事,只告诉你们,我后来明白了,如果要推广这个软件,必须自己来干。

(图四:1981年,22岁,登上《纽约时报》。)

所以,我成立了一家公司,不过我仍然把自己看做一个学者。

那时,我对商业活动一无所知,我就找了一个CEO,然后筹到了一大笔风险投资。

不久,公司的管理人员对我说:"我们是专业人士,这些事情让我们管就行了。"我试图介入公司的运营,但是遇到了很多挫折。我觉得,很多经营决策都有问题,但是无能为力。

我记得,最大的问题就是各地的销售人员。他们希望销售人员分布在美国各地,但是我觉得,我们的产品很复杂,管理好外地的销售人员很困难,如果有重大的商业活动,应该直接派人从洛杉矶坐飞机过去。

我认为这是常识,结果却被告知,我对商业并不了解,最好不要插手。后来的事实证明我是对的,但是这样的事情还是一再发生,我就对自己说:"不行,太荒唐了,我得离开这里。"

(图五:1984年,25岁,开发的软件在Sun-2电脑上运行。)

我就去了普林斯顿大学,研究许多很有趣的科学问题,业余时间也做一些高科技的咨询顾问。

你们可能想知道,我的第一家公司后来怎么样了。我告诉你们吧,每一年只要新出现一个热点,风险投资商就让它跟进。结果,它每年都亏钱,但是每年都筹到更多的钱。

最终,在1995年前后,我收到了一大堆公司寄来的文件。我以为它进入破产诉讼了,但是令人万分震惊,事实是它要上市了。

(图六:1984年,25岁,与著名物理学家费曼在一起。)

还是回到我自己的故事,80年代中期,我做了大量的基础研究,主要与复杂性(complexity)的起源有关。看上去,我可以创造一个新的领域。这涉及到大量的工作,我就到处宣扬所谓的"复杂系统研究"(complex systems research),试图吸引别人投入这个领域。

我成立了一家小公司,出版这方面的专业杂志。这本杂志实际上直到今天还在发行。然后,又在一所大学里成立研究中心。不过,我必须很不好意思地承认,只过了几个星期,我就发现那所大学的管理风格不适合我。

如果我真的想把我的学科发扬光大,最佳策略就是自己做出最好的工具,然后自己用它们来搞研究。

那是1986年,正赶上个人电脑开始拥有足够的计算能力了。

我使用各种各样不同的软件,完成不同的研究。我就有一个想法,也许可以做出一个通用的计算系统,然后我只用这个系统就行了,其他人也会认为这个系统很有用。

这就是激励我做出Mathematica的原因。我下定决心要把它做出来。

(图七:1988年,第一本Mathematica书籍。)

我知道自己需要成立一家公司。

我不想再犯第一次成立公司时的错误,也不想重复我做咨询顾问时看到的别人的错误。这一次,我一定要自己来当CEO,就算犯错,也要按自己的想法行事。

那时,我已经有一点钱了,第一批招来的工作人员很多都是兼职,所以我不需要外部资金。没过多久,我就与NeXT公司、Sun公司、IBM公司达成协议,它们的机器会支持我们的软件。

一年半之前,1988年6月,Mathematica第一版发布了,引起轰动。

(图八:1988年运行Mathematica的Next电脑。)

我记得,那时我有15个雇员。我希望保持小公司的规模,只做一个纯粹的研发型公司。销售和推广的部分(至少销售部分),都留给硬件公司去做。

可惜这种想法行不通。尽管我的愿望很美好,也做了很多努力,但是不同公司的文化差异太大。不久,我就看出来了,所有的事情都必须自己的公司来做。

令人高兴的是,后来的事情都很顺利。从那时起,公司一直发展良好,已经超过18年了,而且持续盈利。我也仍然是CEO,一直努力让公司保持小规模,目前公司的核心部分也不过350人左右。

虽然小,但是公司运作得很好。过去17年来,在Mathematica的帮助下,无数新发现和新产品被做出来,全世界顶级的研发人员,大部分都习惯使用它,许许多多其他行业的人也在使用它。

(图九:1990年,Mathematica月刊开始出版。)

我们发明了大量的新技术。我组建了一支稳定的团队,里面有许多天赋高超的人,我真的很享受与他们一起工作。

1991年,公司盈利良好,已经可以上市了。但是,我决定不上市。我希望它始终是我自己的公司,这样我就能做自己想做的事情----那些长期的项目,比如我的科学研究。

我计划用一年的时间,投入基础研究。但是就像人们第一次使用望远镜,我将Mathematica投入计算,立刻就看到了各种意想不到、令人激动的发现。这种情况持续发生,已经十年了。

听上去有点疯狂。我每天很晚起床,远程管理一下公司,那时已经是下午了。然后,通宵达旦进行科学研究。

我逐渐创立了一门崭新的学科。我把它系统地写成了一本书,最终在2002年出版。

(图十:2002年,著作A New Kind Of Science出版。)

新兴的科学让我们看到自然界的大量秘密,通过使用技术,我们还将做到许多现在无法想象的事情。这让人激动,我很高兴自己的生活中可以干这些事情。

走到今天这一步,并不是轻而易举的。我非常幸运,年纪很小的时候,就在科学上取得了相当的成功,这允许我轻松地将自己的一生投入到科学研究之中。

我总是想做我自己的东西,使得我不可避免要成立自己的公司。这里面有一种交换关系,如果你愿意做更多乏味的事情,你可能赚到更多的钱;如果你不太关心钱,你可能就会得到更多的智力乐趣。

我非常满意现在的状况:我在做真正有趣的东西,而且还赚到足够的钱,可以一直做下去。

(图十一:1994年,35岁,埋头整理书稿。)

2002年以后,既然我的研究成果已经出版,我就把精力主要集中在研究工具上面,也就是Mathematica。

你们知道,Mathematica构建在一些有关计算的深刻的想法上面。过去十年来,我们逐渐意识到,这些观念和算法不仅可以用来构建Mathematica,还可以用来构建一些更大的东西。最终成果出来的时候,将非常令人激动,我想比Mathematica的第一版还令人激动。

你真正在乎你正在做的事情,这很重要。最近,我每天花大量时间来设计Mathematica,它的语言、功能、界面等等。我试图搞清楚这些事情的基本特性,我觉得这与科学研究的难度不相上下。我试图把那些基本的东西做对,尽可能做到简洁和强大。

我找来能干的人,与我一起工作。我把大量职责交给别人。但是,如果你想要保持整个系统协调和统一,那么有些事情你就必须自己来做。我坚持真正理解每件事。你们知道,每次我有什么地方不懂,就会出差错。

我想这是我管理公司的一个风格。一开始,所有事情都是CEO做,慢慢的,等你理解这些事情以后,你就雇其他人来做。但是如果你没有理解,就把责任委派给其他人,事情就会搞糟。

公司(尤其是私人公司)不可避免地多少带有一点领导人的个性。所以,我的公司就有点古怪,里面有很多聪明的人,每个人实际上都在从事创造,没有纯粹意义上的经理。每个人(包括我)把大部分时间都花在创造新东西上面。

(图十二:2002年,43岁,为新书签名。)

我的个人经历就是这样。

我的经验就是,你必须有一些自己真正热爱的东西,然后你应该致力于推动它的发展。如果你聪明的话,你很可能会掌握运营公司的诀窍。要让公司运营成功,你需要找到一些真正关心公司的人来领导它。但是,你不能把成立公司的核心动机,委托给其他人。

(完)

文档信息

2011年7月14日星期四

阮一峰的网络日志

阮一峰的网络日志


不要在功能上竞争

Posted: 13 Jul 2011 06:28 PM PDT

苹果公司的电子产品,最大的特点就是它的易用性(usability)----简单,美观,容易上手。

它们通常不是功能最强大的,但往往是最好用的。下图的左边是Mac,右边是PC,你觉得看上去哪个更好用?

很多产品经理都想模仿这些特点。但是,一个难题就会随之而来:

很难让一件产品保持简单,同时还具备大量的新功能。

如果你不断为产品添加新功能,在变得强大的同时,它还会变得越来越复杂,增加了用户的使用难度;如果你大力简化产品,在功能上比较单一,那么怎样与竞争对手抗衡呢?

每个产品经理都会面对这个难题。对于新产品,这个问题尤其重要。因为新产品通常很难打开市场,最容易想到的解决办法就是为它不断增加功能,直到引起市场注意为止。但是,这样做是否正确呢?

我对这个问题,一直很困惑,不知道开发新产品的时候,哪一个取向优先,多功能还是易用性?

昨天,我读到了硅谷产品经理Andrew Chen的文章,顿时醍醐灌顶,一下子就找到了答案。

他说,正确的做法,就是不要在功能上竞争。如果你的产品的核心概念行不通,那就重新定位这个产品,而不是为它添加新功能。你必须牢记在心,创造一个有竞争力的新产品,不要着眼于它的功能比别人多,而要着眼于它有一个截然不同的市场定位。

如果市场上都是复杂的企业级工具,那就开发一个针对个人用户的简化版;如果市场上都是很正式的高端葡萄酒,那就开发一种便宜的、针对年轻人的、更休闲的酒精饮料;如果市场上都是提供长篇Blog服务的网站,那就开发一个很简单的、每次只能写140个字的网站;如果市场上都是技术性的、廉价的电子设备,那就开发人性化的、高价的电子设备。

总之,你要做的不是添加功能,而是做一个市场定位不同的产品。

这主要有两个原因:

首先,你不太可能通过一个更多功能的新产品,战胜现有厂商。因为你开发出全面胜过别人的产品,需要很多时间;而且,等你开发出新功能,别人可能又做出了改进,或者拷贝了你的新功能。

其次,比起新功能,消费者更容易为一个特殊定位的产品掏钱。

所以,更好的策略是,开发一个简化的产品,突出某种不同的市场定位,争夺现有厂商的低端用户。这样的话,你不用开发一个全功能的产品,节省了时间,而且由于设计目标不同,更容易做出颠覆式创新(disruptive innovation)。

下面是开发新产品时,几点可行的做法:

  (1)你不是做一个比竞争对手"更好"的产品,而是做一个"不同"的产品。

  (2)你只提供部分功能,但是很好地满足了用户的需求。

  (3)如果新产品的市场反响不好,增加新功能并不能解决问题。你应该重新定位你的产品,想想它能向消费者提供哪些不同的价值。

  (4)在产品设计和推广的每一个环节,都突出它的不同定位。

(完)

文档信息

2011年7月12日星期二

阮一峰的网络日志

阮一峰的网络日志


数学公式生成器

Posted: 11 Jul 2011 07:12 AM PDT

上一篇文章《数学常数e的含义》,有很多数学公式。

但是,在网页上显示数学公式,是一件非常麻烦的事情。以下面的公式为例:

  

怎样才能把这个公式放到网页上呢?

传统的方式是,先在相关软件中把公式做出来,然后截图,再把图片贴到网页上,这样既麻烦又耗时。我就在想,有没有便捷的方法,可以生成数学公式。

我知道,Google Chart接受TeX语言,实时返回数学公式的图片。于是,我就用了一天时间,根据它的API,写出了一个"数学公式生成器"

经过初步测试,我自我感觉很不错,觉得写作数学公式从此不再麻烦了。我把这个作品推荐给大家,欢迎试用。

如果你懂得TeX语法,使用起来应该毫无困难。如果不懂,也没有关系,用起来很简单,下面我做一个初步介绍。

对于简单的公式,可以直接在文本框输入,比如"y=2x+8":

  

然后点击"查看"按钮,就会显示数学公式的图片,并且给出图片代码。

  

接着,就来看怎么生成本文开头那个稍微复杂一点的公式:

  

首先,按照顺序输入左括号、1、+:

  

加号后面是一个分数,这时就要用到TeX语法了,点击菜单里的"结构"选项,选择"分数"那一栏:

  

文本框中就会插入"\frac{1}{2}"这样的结构:

  

在TeX语法中,斜杠开头的语句表示命令,所以"\frac"表示后面要生成分数;命令后面的大括号,表示命令的参数,"\frac"后面的第一个大括号表示分子,第二个大括号表示分母。现在,依次在"分子"中填入"100%",在"分母"中填入"n"。

  

最后,加上右括号和"^n"。

  

点击"查看"按钮,这个公式就显示出来了。

  

其他公式的生成方法与其类似,大家可以自己摸索,任何时候都可以点击"查看"按钮,了解是否写错。

TeX几乎可以写出所有的数学公式(查看MediaWiki的参考网页),但是Google Chart只支持一部分的TeX语法,因此不保证所有时候都能得到想要的结果。

除了Google Chart,还有另一些服务,也能生成数学公式的图片,比如mathtran.orgmathurl.com,还有这里这里

(完)

文档信息

2011年7月9日星期六

阮一峰的网络日志

阮一峰的网络日志


数学常数e的含义

Posted: 08 Jul 2011 09:15 PM PDT

1.

e是一个重要的常数,但是我一直不知道,它的真正含义是什么。

它不像π。大家都知道,π代表了圆的周长与直径之比3.14159,可是如果我问你,e代表了什么。你能回答吗?

维基百科说:

"e是自然对数的底数。"

但是,你去看"自然对数",得到的解释却是:

"自然对数是以e为底的对数函数,e是一个无理数,约等于2.718281828。"

这就构成了循环定义,完全没有说e是什么。数学家选择这样一个无理数作为底数,还号称这种对数很"自然",这难道不是很奇怪的事情吗?

2.

昨天我读到一篇好文章,它把这个问题解释得非常清楚,而且一看就懂。

它说,什么是e?简单说,e就是增长的极限。

下面就是它的解释。

3.

假定有一种单细胞生物,它每过24小时分裂一次。

那么很显然,这种生物的数量,每天都会翻一倍。今天是1个,明天就是2个,后天就是4个。我们可以写出一个增长数量的公式:

  

上式中的x就表示天数。这种生物在x天的总数,就是2的x次方。这个式子可以被改成下面这样:

  

其中,1表示原有数量,100%表示单位时间内的增长率。

4.

我们继续假定:每过12个小时,也就是分裂进行到一半的时候,新产生的那半个细胞已经可以再次分裂了。

因此,一天24个小时可以分成两个阶段,每一个阶段都在前一个阶段的基础上增长50%。

  

当这一天结束的时候,我们一共得到了2.25个细胞。其中,1个是原有的,1个是新生的,另外的0.25个是新生细胞分裂到一半的。

如果我们继续修改假设,这种细胞每过8小时就具备独立分裂的能力,也就是将1天分成3个阶段。

  

那么,最后我们就可以得到大约2.37个细胞。

很自然地,如果我们进一步设想,这种分裂是连续不断进行的,新生细胞每分每秒都具备继续分裂的能力,那么一天最多可以得到多少个细胞呢?

  

当n趋向无限时,这个式子的极值等于2.718281828...。

  

因此,当增长率为100%保持不变时,我们在单位时间内最多只能得到2.71828个细胞。数学家把这个数就称为e,它的含义是单位时间内,持续的翻倍增长所能达到的极限值。

这个值是自然增长的极限,因此以e为底的对数,就叫做自然对数。

5.

有了这个值以后,计算银行的复利就非常容易。

假定有一家银行,每年的复利是100%,请问存入100元,一年后可以拿多少钱?

  

回答就是271.828元,等于100个e。

但是,实际生活中,银行的利息没有这么高,如果利息率只有5%,那么100元存一年可以拿到多少钱呢?

  

为了便于思考,我们取n等于50:

  

我们知道,在100%利息率的情况下,n=1000所得到的值非常接近e:

  

因此,5%利息率就相当于e的20分之一次方:

  

20分之一正好等于5%的利率率,所以我们可以把公式改写成:

  

上式的rate就代表增长率。这说明e可以用于任何增长率的计算,前提是它必须是持续不断的复合式增长。

6.

再考虑时间因素,如果把钱在银行里存2年,可以得到多少钱?

  

在时间t的情况下,通用公式就是:

  

上式就是计算增长量的万能公式,可以适用于任何时间、任何增长率。

7.

回到上面的例子,如果银行的利息率是5%的复利,请问100元存款翻倍需要多少时间?

  

计算结果是13.86年:

  

上式最后一个等号,表明用72除以增长率,可以得到翻倍的大致时间,这就是72法则的来源。

(完)

文档信息