在很多功能的实现都离不开图像的匹配算法，如何又快又准的进行匹配，匹配的过程又是怎么实现的呢？最近趁着编译的空闲，初探了一下特征匹配的世界。
1 特征点匹配
图像的匹配并不是简单意义上的连连看，两幅图像的对比匹配中其实很难遇到两个一模一样像素区域，所以图像或者说内容的匹配实际还是特征的提取与描述。
1.1 简单原理
这里的点并不是像素点，而是一个包含着周边信息的特征点。分别在两幅图像上找到若干对这样的特征点，就能像连连看一样找到大概率匹配的部分。
那么想要判断两个匹配区域，最少需要几对点？其实1对就够，但1对点所能提供的信息以及匹配的准确度远远达不到我们的需求，它只能说明“这两幅图中确实都有这样一个相似的点”。
最基础的就是三点定位，通过三对点我们可以找到相似的区域以及这个区域经历的拉伸、反转、扭曲等变化。（比如下面lena的眼睛，点是我乱画的...但能很明显看出对应关系）
当然，实际应用的时候三对点还是远远不够，往往采取二十对乃至更多。
1.2 形变影响
特征点匹配有一个很让人头疼的问题，四周特征区域的变化：
由于在搜索特征时搜索器并不知道图像发生了什么变化，所以用于描述同一个点的信息仍然按照原来的规则，形变越明显越容易出现误差。
1.3 典型算法
所以往往提取时会尽量选择突出，且不会因光照，仿射变换和噪音等因素而变化的点，比如角点、边缘点、暗区的亮点及亮区的暗点等进行匹配。
SIFT算法参考博客从不同尺度空间上寻找特征点进行匹配，每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种表示，以允许比较大的局部形状的变形和光照变化。
SURF算法参考博客则是提出了一种具有尺度和旋转不变性特点的特征点提取和描述方法。使用积分图来计算卷积；然后使用Hessian响应来衡量某点是否为特征点，并创建描述子来描述该特征。
2 特征区域匹配
特征点的匹配考虑到了点周围的特征，实际上匹配的也是一个区域。如果直接用一个区域的整体特征进行匹配则不会出现上述的形变导致采样区域变化的问题了。
2.1 灰度特性匹配
区域特征中很有趣的一种特征描述就是灰度特性，即利用该区域中整体的灰度值特性进行描述与匹配。
如把灰度图看成高低起伏的地形图，其中灰度值看成海平面高度的话，MSER的作用就是在灰度图中找到符合条件的坑洼。条件为坑的最小高度，坑的大小，坑的倾斜程度，坑中如果已有小坑时大坑与小坑的变化率。（参考博客）
2.2 MSER
最大稳定极值区域MSER(Maximally Stable Extremal Regions)最早由J.Matas在2002年的一篇论文Robust Wide Baseline Stereo from Maximally Stable Extremal Regions中提出，是目前较为理想的一种仿射不变区域提取。
MSER看起来就像一个俯瞰一个开闸的水库，我们从(0,255)间连续选择一系列阈值对同一幅图像进行二值化处理。在这一些列的二值化图像中，有些连通区域随阈值变化而变化，而有些则变化很小。这些受阈值影响很小的连通区域，我们就称之为MSER。
我们用Qi表示第i个连通区域的面积，Δ表示微小的阈值变化，当vi小于给定阈值时认为该区域为MSER。
显然，这样检测得到的MSER内部灰度值是小于边界的，想象一副黑色背景白色区域的图片，显然这个区域是检测不到的。因此对原图进行一次MSER检测后需要将其反转，再做一次MSER检测，两次操作又称MSER+和MSER-
此部分参考博客：最大稳定极值区域（MSER）检测
2.3 需要符合条件的“坑”
一个水坑的变化如下图A，随着水位的提高，面积由Ra变为Rb在到Rc，Ra为Rb的父区域；判断极值区域的方法如图B，在delta水位差间两个区域面积是否满足一定条件；还有一个判断条件如图C，如果已经有一个候选区域Rstable了，Rcandidate是否可以作为一个极值区域，也就是大坑套小坑的情况。（参考博客）
用opencv在python下试着找了找lena的“坑”：
import cv2
img = cv2.imread('lena.png', cv2.COLOR_BGR2GRAY);
vis = img.copy()
mser = cv2.MSER_create()
regions = mser.detectRegions(img, None)
hulls = [cv2.convexHull(p.reshape(-1, 1, 2)) for p in regions]
cv2.polylines(vis, hulls, 1, (0, 255, 0))
cv2.imwrite('lena_mser.png', vis)
cv2.imshow('img', vis)
cv2.waitKey(0)
cv2.destroyAllWindows()
看看我们的MSERs：
