SLIC算法分割超像素原理及Python实现

超像素(SuperPixel),就是把原本多个像素点,组合成一个大的像素。比如,原本的图片有二十多万个像素,用超像素处理之后,就只有几千个像素了。后面做直方图等处理就会方便许多。经常作为图像处理的预处理步骤。

在超像素算法方面,SLIC Superpixels Compared to State-of-the-art Superpixel Methods这篇论文非常经典。论文中从算法效率,内存使用以及直观性比较了现有的几种超像素处理方法,并提出了一种更加实用,速度更快的算法——SLIC(simple linear iterative clustering),名字叫做简单的线性迭代聚类。其实是从k-means算法演化的,算法复杂度是O(n),只与图像的像素点数有关。

这个算法突破性的地方有二:

  1. 限制聚类时搜索的区域(2Sx2S),这样将k-means算法的复杂度降为常数。整个算法的复杂度为线性。
  2. 计算距离时考虑LAB颜色和XY距离,5维。这样就把颜色和距离都考虑进去了。通过M可以调整颜色和距离的比重,灵活性强,超像素更加规则。

SLIC算法原理

整个算法的输入只有一个,即超像素的个数K。

图片原有N个像素,要分割成K个像素,那么每个像素的大小是N/K。超像素之间的距离(即规则情况下超像素的边长)就是S=√N/K。

我们的目标是使代价函数(cost function)最小。具体到本算法中,就是每个像素到所属的中心点的距离之和最小。

首先,将K个超像素种子(也叫做聚类,即超像素的中心),均匀撒到图像的像素点上。

一次迭代的第一步,对每个超像素的中心,2S范围内的所有像素点,判断他们是否属于这个超像素。这样之后,就缩短了像素点到超像素中心的距离。

一次迭代的第二步,对每个超像素,将它的超像素中心移动到这个超像素的中点上。这样也缩短了像素点到超像素中心的距离。

一般来说,迭代10是聚类效果和计算成本折中的次数。

SLIC算法步骤

  1. 撒种子。将K个超像素中心分布到图像的像素点上。
  2. 微调种子的位置。以K为中心的3×3范围内,移动超像素中心到这9个点中梯度最小的点上。这样是为了避免超像素点落到噪点或者边界上。
  3. 初始化数据。取一个数组label保存每一个像素点属于哪个超像素。dis数组保存像素点到它属于的那个超像素中心的距离。
  4. 对每一个超像素中心x,它2S范围内的点:如果点到超像素中心x的距离(5维)小于这个点到它原来属于的超像素中心的距离,那么说明这个点属于超像素x。更新dis,更新label。
  5. 对每一个超像素中心,重新计算它的位置。
  6. 重复4 5 两步。

伪代码(来自论文)

Python实现SLIC

最新版本的代码请看这里:https://github.com/laixintao/slic-python-implementation

效果如下:

Lenna图像在M=30,K=500时第一次迭代产生的超像素图。

Lenna图像在M=30,K=500时第10次迭代产生的超像素图。

 

博客反垃圾评论之路

写博客的人(独立网站)都知道,博客经常会收到一些很奇怪的评论,这些评论的特点是:没有实际内容,一般为盲目称赞博文、与博文无关内容、类似水帖。这就是垃圾评论。这些评论的作用是把流量引向他们的网站,或者SEO。说白了,就是通过评论在你的网站上打广告。

在第三方的博客平台写的话也会遇到一些在评论里打广告的。但是这个反垃圾评论的任务就交给博客平台了。

独立网站也可以选择第三方的评论系统,但是这等于放弃了SEO。我非常喜欢Disqus,漂亮,稳定,可用性高。在反垃圾方面也是我用过的最好的。国内有多说,友言等等,但是这些反垃圾都比较差,经常看见很多多说评论里面有大量成人网站的广告,惨不忍睹。

目前,我用的是WordPress自带的评论系统。WordPress博客有个著名的反垃圾插件:Akismet。这个插件使用的是黑名单机制,如果你把一条评论手动定为垃圾评论,那么Akismet就会记住,然后下次出现相同的名字,ip或内容相似,就直接判为垃圾评论。

这和杀毒软件有点像,但不同的是,杀毒软件的病毒库是在本地,Akismet的数据库却是在服务器上,也就是说,用户每发一次评论,Akismet就会将评论提交给服务器,服务器判断是不是垃圾评论,然后Akismet根据结果来处理。大大降低了博客处理评论的速度,尤其是在国内,在我这里,发布一次评论基本上需要10s左右才会给用户响应(取决于你网站的网速,而不是用户的网速)。

虽然慢是慢了点,但是效果挺好的,基本上能阻挡90%的垃圾评论。

一般的垃圾评论比较蠢,带有大量的链接,不是中文,名字留的广告,网址也是广告,一看就是垃圾评论的。这类Akismet基本都能解决。

还有一些评论虽然没含什么广告,但是内容确是“写的不错” “深受启发”这样的没有意义的评论,疑似垃圾评论(留的链接可能指向广告),有时候能通过Akismet,但是我会手动删除。

今天遇到了更高级了,全都通过了Akismet。这类不光内容看似人畜无害,而是还是回复给已经存在的评论!

好在WordPress可以设置黑名单,直接在设置>讨论>黑名单ip里面封杀就好了。

 

VimScript学习笔记(10):正则表达式

一般的编程语言都有正则表达式的功能,对于Vim这种专门处理文本的编辑器来说,正则就更加重要了。在学习这一章节之前,你最好有一些正则表达式的基础。如果没有,可以参考《Learn Regex the Hard Way》来学。

设置高亮

通过下面这条命令,可以打开Vim的高亮设置。这样我们在搜索文本的时候,匹配的文本背景会用高亮的颜色显示。

hlsearch是控制按下回车之后,匹配的文本背景高亮。

incsearch是控制实时刷新匹配的文本高亮。

使用正则搜索

在Vim中,向后搜索按下/,向前搜索按下?。通常会配合executenormal构造字符串命令来执行搜索。

注意在命令中,像+这样的正则符号,需要前面加\进行转义,否则就会解释成字符+,而不是正则上面的含义(好奇怪,.符号默认是正则里面的.而不是符号,+却默认是符号而不是正则)。

而在字符串命令中,转义符号需要先用转义符号将其解释成转义符号,而非符号\。有些绕,举个例子,+在字符串命令中的正则含义需要这样表示: \\+

纯字符串

上一节中我们讨论过纯字符串,在纯字符串(单引号里面的内容)下,就可以不必使用双反斜杠表示转义了。但是需要注意的是,\<cr>这样并不能将其转义成回车。因为这里纯字符串不能解释<cr>。好在,Vim支持字符串拼接。

“魔术时刻”(Very Magic)

太疯狂了是不是,竟然有这么多模式。

如果你对其他语言的正则表达式熟悉的话,可以使用一个叫做Very Magic的模式(就是用\v开头的正则表达式)。

参考这个命令。

我个人比较喜欢这个方案。因为它把命令和正则分开了,而且兼容其他编程语言。

 

 

VimScript学习笔记(9):Excute和Normal

Execute

execute可以把一个字符串当做Vim的命令来执行。

这个命令的强大之处在于,可以通过字符串来构造不同需要的命令,然后进一步执行。

实验:创建file.txt并使用Vim打开,然后在Vim中执行 :edit foo.txt ,当前buffer会被foo.txt覆盖。最后执行下面的命令:

你会发现,窗口被分割成两个, 右边的窗口重新打开了file.txt

这个过程是:首先"rightbelow vsplit "字符串先和bufname("#")(这个命令的作用是,返回上一个buffer的路径)的结果进行连接。得到的字符串被执行。

Vim的Execute命令危险吗?

通常来说,一个语言的类似eval的命令都是比较危险的。因为这可能执行用户输入的代码,从而带来安全隐患。但是Vim不存在这个问题,原因有二:

第一,一般来说Vim只会接受一个人的输入,就是它的用户。如果用户想要输入一些危险的代码,也不是不可以,毕竟电脑是他们自己的。所以不存在什么安全隐患。

第二,VimScript有一些很奇怪的语法。这是execute可能是最简单的方式。况且,Vim可以在一行中写很多代码。

Normal

有一些命令是在Normal模式下有用的,比如说跳到最后一行的G。但是,通过normal命令,我们可以模拟这个键是在normal模式下按下的。

有时候,一些键映射到了别的功能。比如

我们使用normal!,将会忽略定义的映射。在vimrc文件中,就像我们应该永远使用noremap一样,我们也应该永远使用normal!

normal不会处理特殊字符。比如:normal! /foo<cr>,乍一看是搜索foo然后回车。但实际上,它会搜索foo左尖括号cr右尖括号的字符串,而没有按下回车。

要解决这个问题,就结合execute命令。

Execute Normal!

由于execute命令可以根据字符串执行命令,利用这个我们就可以使用Vim的字符串转义输入一些不可打印的字符。从而解决这个问题。

例子,下面的这个命令,可以在代码末尾添加一个分号,然后回到之前的位置。如果你看不懂,参考这里

 

 

VimScript学习笔记(8):函数

Vim的函数

Vim中使用function ... endfunction定义函数。

需要注意的是,Vim中的函数如果没有标明作用域(前缀s:),那么函数必须以大写字母开头。事实上,Vimer约定所有的函数都用大写字母开头,无论有没有作用域。

使用function!可以避免重复载入时候的冲突。

下面是定义一个简单的函数。

调用方法是:call Meow()

也可以使用返回值。

可以将返回值打印出来。

返回值

如果函数没有提供返回值,会返回数字0(即假)。

下面的这个判断宽度是不是太大的函数,在调用的时候就可以直接使用。

函数参数

Vim的函数当然也可以接受参数。下面的函数声明和调用展示了Vim的函数参数用法。

注意,变量的a:前缀是标志作用域。如果删去,Vim就找不到这个变量了。

在VimScript中,如果要函数接受变量,那么任何时候使用这个变量都要带上a:前缀,来告诉Vim他们在函数参数作用域中(argument scope)。

可变长度的参数

和Python,JavaScript一样,VimScript可以接受不确定数量的参数。见以下代码。

其中:

  • ... 表示这个函数可以接受任意数量的参数,和Python的*args一样
  • a:0表示这个函数的可变长度的参数的个数,我们传给Varg两个参数,那么a:0就是2
  • a:1 a:2 等等就是调用第n个参数
  • a:000 是所有可变长度参数组成的列表(数组),这里会打印出["a", "b"]

可变长度的参数可以和普通的参数一起用,和Python一样。

参数不能重新赋值

下面的代码,会抛出一个错误,因为Vim不允许对函数传进来的参数重新赋值。

为此,我们一般不直接使用传进来的参数,函数的开始一般会将进来的参数复制给新的变量,在函数中使用新的变量。