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

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

一个对话框会出现。

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

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

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

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

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

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

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

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

第一步,缩小尺寸。

将图片[……]

阅读全文

王小龙,数学,计算机视觉,图形图像处理

神经网络很萌的!

0. 分类

神经网络最重要的用途是分类,为了让大家对分类有个直观的认识,咱们先看几个例子:

  • 垃圾邮件识别:现在有一封电子邮件,把出现在里面的所有词汇提取出来,送进一个机器里,机器需要判断这封邮件是否是垃圾邮件。
  • 疾病判断:病人到医院去做了一大堆肝功、尿检测验,把测验结果送进一个机器里,机器需要判断这个病人是否得病,得的什么病。
  • 猫狗分类:有一大堆猫、狗照片,把每一张照片送进一个机器里,机器需要判断这幅照片里的东西是猫还是狗。

这种能自动对输入的东西进行分类的机器,就叫做分类器。

分类器的输入是一个数值向量,叫做特征(向量)。在第一个例子里,分类器的输入是一堆 0、1 值,表示字典里的每一个词是否在邮件中出现,比如向量 (1,1,0,0,0……) 就表示这封邮件里只出现了两个词 abandon 和 abnormal;第二个例子里,分类器的输入是一堆化验指标;第三个例子里,分类器的输入是照片,假如每一张照片都是 320*240 像素的红绿蓝三通道彩[……]

阅读全文

0、写在前面的话

我个人一直很喜欢算法一类的东西,在我看来算法是人类智慧的精华,其中蕴含着无与伦比的美感。而每次将学过的算法应用到实际中,并解决了实际问题后,那种快感更是我在其它地方体会不到的。

一直想写关于算法的博文,也曾写过零散的两篇,但也许是相比于工程性文章来说太小众,并没有引起大家的兴趣。最近面临毕业找工作,为了能给自己增加筹码,决定再次复习算法方面的知识,我决定趁这个机会,写一系列关于算法的文章。这样做,主要是为了加强自己复习的效果,我想,如果能将复习的东西用自己的理解写成文章,势必比单纯的读书做题掌握的更牢固,也更能触发自己的思考。如果能有感兴趣的朋友从中有所收获,那自然更好。

这个系列我将其命名为“算法杂货铺”,其原因就是这些文章一大特征就是“杂”,我不会专门讨论堆栈、链表、二叉树、查找、排序等任何一本数据结构教科书都会讲的基础内容,我会从一个“专题”出发,如概率算法、分类算法、NP问题、遗传算法等,然后做一个引申,可能会涉及到算法与数据结构、离散数学、概率论、统计学、运筹学、数据挖掘、形式语言与自动机等诸多方面,因此其内容结构就像一个杂货铺。当然,我会竭尽[……]

阅读全文

ps里面的魔棒工具非常好用,是图像处理中非常常用的一个工具,它现在已经是我的c++工具箱中很重要的一员了,我会在以后的时间里把我的工具箱逐渐介绍给大家。

魔棒工具的核心算法是RegionGrow区域成长法,它的概念很简单,首先在要处理的图片上选取一个种子点,然后以此点为起点,向四周辐射形成一个区域。最初成长区域只有种子点这一个点,然后不断把周围的点归并入该成长区域,条件是该点的值与成长区域边界点的值之差小于阈值。当成长区域不能再继续扩大时,算法停止。

r_regiongrow

算法说明:

区域成长法的思想很好理解,代码实现对于初学者有一定难度。对于满足条件的像素点,函数会把它们一个个的压入队列的尾部,然后从队列的头部一个个的取出来,形成成长区域。M是一个点名册,用来记录每一个像素是否被处理过。start和end用来记录队列的头和尾,当start==end时,说明所有所有像素已经处理完,函数结束。

附上JAVA实现:

循环实现:

	private StarSet getStarRegionByLoop(int y, int x, boolean[][] hasCalced) {[......]

阅读全文

图像处理的数学算法,已经发展到令人叹为观止的地步。

Scriptol列出了几种神奇的图像处理算法,让我们一起来看一下。

一、像素图生成向量图的算法

数字时代早期的图片,分辨率很低。尤其是一些电子游戏的图片,放大后就是一个个像素方块。Depixelizing算法可以让低分辨率的像素图转化为高质量的向量图。

二、黑白图片的着色算法

让老照片自动变成彩色的算法

三、消除阴影的算法

不留痕迹地去掉照片上某件东西的阴影的算法

四、HDR照片的算法

所谓”HDR照片”,就是扩大亮部与暗部的对比效果,亮的地方变得非常亮,暗的地方变得非常暗,亮暗部的细节都很明显。

实现HDR的软件有很多,这里推荐G’MIC。它是GIMP图像编辑软件的一个插件,代码全部开源。

五、消除杂物的算法

所谓”消除杂物”,就是在照片上划出一块区域,然后用背景自动填补。Resynthesizer可以做到这一点,它也是GIMP的一个插件。

六、自动合成照片的算法

根据一张草图,选择原始照片,然后把它们合成在一起,生成新照片。这是[……]

阅读全文