mser算法中文的一些说明.doc

MSER说起来太简单了，但实现起来却有点头疼，又不想用别人的程序，从头自己写了一遍，想研究MSER算法的可以路过看看。先说说MSER介绍性的东东，MSER叫做Maximally Stable Extreme Region，这里容易搞晕的就是Maximally和Extreme，本来Maximally就是某种极值，Extreme也是，初看容易搞死人。先从为什么要MSER说起。MSER是为了图像检索、匹配服务。我们知道同一个物体往往会被拍了很多图片，什么角度，光照一般都不同。如何判断不同的照片中是否包含同一个物体是MSER要致力解决的问题。介绍性的信息太多了，有点不耐心，先跳过。大家科普去。说点比较复杂的部分，就是算法如何实现。为此明确几个定义：Region：Region就是区域，在连续空间中有严密的定义，容易让人头疼，但是我们到图像里面就简单多了，所谓一个Region就是图像的一部分，这个部分中的每任何两个点之间A，B，都要能从A沿着相邻像素扭扭区区的到达B，看下图，图A，图B都是Region，虽然B中间空了，C虽然空的不多，但是明显割裂开了，所以不是Region。如果不加任何条件，你可以列出图像极多的Region，但是木有什么意义，MSER研究的Region是有条件的，这个Region就是这么一步步搞来的，我们假设图像灰度是1255。对每个灰度i搞一次，搞的时候注意研究对象不再是原来所有的图像点了，而是灰度小于等于i的那些点，这样一来，如果你把那些点标出来看的话，就发现有些点之间不通了，比如有一行像素值是1，2，3，4，1，2，3，4，如果i2，你就发现第一、第二个像素连着的，第五、第六像素连着的，但是一二和五六之间被隔开了。ExtremeRegion：ExtremeRegion的定义是绑定到灰度值的（我们称这个灰度值为ExtremeRegion的代表灰度），脱离灰度值谈extreme木有意义，这一点很重要。一个图像在某个灰度上成为extremeregion的条件是你没有办法再从图像中找出另外的像素点来把你认为的ExtremeRegion扩大，当然这个像素点的灰度小于等于那个ExtremeRegion的代表灰度。有点绕口，但就是这么定义的。这里有一个点要注意的就是一个灰度可能对应多个ExtremeRegion，实际上往往是如此，比如五星红旗中的星星，每颗星星就是一个Extreme Region，但你不能把五颗星当作一个ExtremeRegion。另外随便哪颗星你都可以掰个角成为一个Region，但不是ExtremeRegion。介个Region和ExtremeRegion灰常关键，一定要在纸片上多画几个，着急不得。MSER主要研究的是ExtremeRegion，也就是五星红旗中的星星，Region没啥大用。现在要考虑的问题就是ExtremeRegion之间有什么关系，这个是最另人纠结的地方，因为你去看算法和原始论文这个地方容易卡壳，作者可能认为太简单了，也不怎么爱详细交代。论文上都写一个Forest，这个东西死要命。这里先直接给答案，然后再细细分析。首先我们说一个图像的所有ExtremeRegion按照一定的关系可以构成一个树，你当然可以把树看成只有一颗树的森林，但是我想强调的是如果想尝试把一幅图像的所有ExtremeRegion之间的关系理解成多个根的森林，那就只能死不瞑目了，能找到的资料上写是Forest也没错，但那是针对经过MSER条件筛选的ExtremeRegion集合。所以一步步来还是先分析ExtremeRegion为什么会成为一颗树。为了构造这个树，当然得先把ExtremeRegion的父子关系搞清楚。如果你把所有ExtremeRegion都找出来了，你在其中任选两个ExtremeRegion，你会发现无非是两种关系，一种是没有交集，一种是包含，这点很关键，也就是因为有这点关系才能构造树。如果ExtremeRegion A包含Extreme Region B，我们就说A是B的可能老爹。为什么会是可能老爹，因为A和B之间可能还包含其他ExtremeRegion，注意只有两者不包涵其他ExtremeRegion的时候才说是父子关系。下面说为什么一定是一棵树，所有的ExtremeRegion都归到一个老祖宗，因为很简单，我们的ExtremeRegion的定义是绑定到像素值的，而我们已经假设灰度是有最大值的255。老盯着ExtremeRegion想，可能会忘了像素。你可能会想有很多像素值是255，所以有可能有多个根。我们就此再多说几句。注意，ExtremeRegion是像素的集合，每个像素可以属于好多个ExtremeRegion（这个要好好理解）。回到那个五星红旗，这个红旗至少有6个ExtremeRegion，一是整面旗帜，其他五个是五个五角星。显然五角星中的任何一个像素都属于最大的那个ExtremeRegion，所以说一个像素可能属于多个ExtremeRegion。但你可能隐约觉得每个像素还对应着另外一个ExtremeRegion（我们称为“代表ExtremeRegion“），只是这个关联标准比较模糊。这个关联标准要重新思考ExtremeRegion的定义，记住一个ExtremeRegion有一个代表灰度，而一个像素有一个灰度值对应，我们从这个像素所在的所有ExtremeRegion中挑出代表灰度与像素灰度相同的作为代表ExtremeRegion，如果下了这个定义，你就会发现每个像素有且仅有一个（如何证明？无非是枚举各种可能，然后推出与定义的矛盾，不罗嗦，实际上我也没证）。到这里，基本上可以把ExtremeRegion的本质搞得差不多了，下一个问题是如何快速找ExtremeRegion，这里面就有技巧了，我一开始去找算法参考，后来看得头疼，就干脆自己从头写了。这里只写点思想，具体可以看我的代码对着读。思想是这样，我们构造那个树从下向上构造，也就是把像素按照灰度值升序排列，然后依次逐个像素处理。每处理一个像素，我们就确定它所在的ExtremeRegion，注意我们只能说截至到处理这个像素的时候，它所在的ExtremeRegion，因为我们后面像素还不知道是什么值，如果像素值严格不同，那没问题，但是有可能后面还有相同的像素值，而且这个值跟它相邻，所以不难理解。但不管怎么说，我们仍然能够处理截至到看到这个像素的时候，它所在的ExtremeRegion。我们假设像素x正在被处理，之前的所有像素已经找到了ExtremeRegion，并且ExtremeRegion之间的父子关系已经扯清楚了，在这种假设下，如果我们能够利用x之前的结果快速给x安置好，整个算法就解决了（为什么？归纳法），那看看怎么解决，无非就是枚举各种可能情况，实际上算法也就是复杂在这里。1、x周围有点被处理过了，也就是x周围有像素值小于等于x的像素值（不可能大于的啊，别忘了是排序过的）；2、x周围没有点被处理过。第二种情况就简单了，说明x目前是一个鼓励点，就该成为一个extremeregion，先建一个再说，然后把x的extremeregion关联过去。第一种情况就复杂咯，x周围有灰度小于或等于的像素（不妨记为y），注意小于和等于的两种情况处理方法完全不同。a）首先说简单的情况小于，按照前面的假设，我们已经知道y的extremeregion（什么叫做y的extremeregion，指代表extremeregion），那么新来的x会对y的extremeregion造成影响么？不会，因为灰度值不通。所以处理就简单了，只要产生一个新的extremeregion就行，创建这个新的region你可以再所有已处理的像素中找连通的子集，但这就傻了，而且找到后你还忘了这个新建的extremeregion的儿子有哪些。所以巧妙的办法是直接在y所在的extremeregion上增加一个像素，构成新的x所代表的extremeregion，注意这个region也有可能被后来的点代表（因为后来的像素值可能与x相同），这个新的extremeregion显然就成为y的extremereg