shape-context-算法及其应用.ppt

shapecontext,13.11.9,形状上下文算法概述,在形状上下文算法中,图像形状不是以某个区域或轮廓来表达,而是由一些离散并且分布均匀的特征点点集来表达,然后针对点集中的每一个特征点,计算其所对应的形状直方图,它记录了该特征点到其它所有特征点全部的矢量信息。最后将图像形状间的匹配问题转化为寻找两个特征点点集之间的对应点问题。,形状上下文算法概述,假设需要进行形状匹配的两幅图像分别为图像f和图像g,通过边缘检测和轮廓跟踪算法,所提取的包含n个特征点的点集分别为P=p1,p2,.pn和q1,q2，.qn。,形状上下文算法概述,对于图像f中的每一个特征点pi(1=i=n),我们需要在图像g中找到一个与其匹配代价最小的特征点qj(1=j=n),假设找出的对应结果为j=r(i)。则计算图像形状间的相似度问题就转化为求的最小值问题,形状上下文算法的框架图,图像边缘检测,由于原始的待检索的图像是二值图像,而在形状上下文中关心的只是图像形状的边缘,因此,本文首先要对其进行边缘检测以获取图像的形状边缘,具体的边缘检测算子有很多,如Sobel算子、Laplacian算子、Prewitt算子等（有函数可以直接调用）,形状轮廓跟踪,在形状上下文算法中,要求提取出的边缘特征点尽可能的分布均匀,因为这直接影响着形状直方图的计算结构,故需要对边缘图像进行轮廓跟踪,跟踪的结果是使得边缘点以边缘方向顺序进行队列。,边缘特征点选取,选取特征点是形状上下文中关键的一环,如果选取的特征点数目过多,会使算法的计算量很大,导致时间复杂度变大。但是选取的特征点数目过少,则会丢失很多边缘信息,导致检索错误。在传统的形状上下文中,特征点的数目一般选取为100或150。,形状直方图计算,对于任意一个边缘特征点,它与其它n-1个特征点可以构成n-1个特征向量,这n-1个向量包含了该特征点全部的信息特征。,形状直方图计算,如下页图示，将整个平面空间从方向上平均划分出12个方向,同时在半径上则均匀划分3份,整个平面空间被划分为36个区域，然后统计其它所有特征点落在每一个区域中的特征点的个数。,形状直方图计算,形状直方图计算,对于边缘轮廓上的任意一个特征点pi,可以用以pi点为中心的极坐标系中处于每一个特征区域内的像素点个数hi(k)对它的属性进行描述,公式计算如下:hi(k)=#qjpi&qjbin(k)其中,#表示统计第k个区域中的边缘特征点的个数。（K为二者乘积相同角度作为横轴）,形状直方图计算,令第i个边缘特征点的j个属性值为:ai,j=#qkpi|qkbin(j)则第i个边缘特征点的36个属性值能够构成一个序列(ai,1,ai,2,.,ai,36),所以可以用一个n*36形状矩阵来对图像形状进行描述:,形状直方图计算,任意一点pi的形状直方图过程中,都是以距离该点最远的边缘特征点的距离作为极坐标系的最大半径r,再将r均匀分成3份,这就使得当图像出现放大或缩小的情况时,每一个边缘特征点的形状直方图不变。,形状直方图计算,如下几页所示,(a)、(b)分别表示两幅马图像的边界取样点,(c)为在图像(a)中选取的点p的形状直方图,(d)为在图像(a)中选取的点q的形状直方图,而(e)为在图像(b)中选取的点r的形状直方图。从中可以发现,点p和点r所对应的形状直方图的相似程度比较大,这是由于这两个点在各自形状中的位置是对应的。,形状直方图计算,形状匹配,设pi为图像f上的一个边缘特征点,而qj是图像g上的一个边缘特征点。计算它们之间每个样本点之间的差别，即形状上下文的差别,定义这两个点的匹配代价cost值为Cij=C(pi,qj)，其定义如下:,形状匹配,其中,形状p中的pi点的形状直方图用hi(k)来表示，形状q中的qj点的形状直方图。根据上述公式可以计算得到pi和qj的匹配代价cost值。上述点的匹配问题即为典型的二分图的匹配问题,利用最优匹配算法,该问题可以得到解决。,形状匹配,运行一个最有匹配算法（如匈牙利算法等）找个一个最优匹配，使整个代价最小，最后基于这个最优匹配，得到整个形状代价，这个可以作为两个形状之间的差别衡量，代价越小，形状越相似。形状代价如下：,形状匹配,不过到这里还只是找到一个对应关系而已，需要进一步用一个变换T来衡量形状之间的转变，所以，最后的形状距离可以用估计的变换来表示，如下：最后基于这个形状距离可以基本衡量两个物体形状之间的区别。（二者采样点数目可能不同，故两边都得足以匹配）,形状上下文在害虫识别上的应用,在对害虫图像进行预处理得到二值图像的基础上，用形状上下文描述害虫的轮廓特征。首先，使用Robert算子，在二值图像中寻找害虫的轮廓并采样获取边界点集，然后利用边界点，通过改进的对数极坐标变化计算得到目标图像的形状直方图利用形状直方图进行2图像之间的相似性度量，计算出匹配代价，跟传统的图像识别技术相比，形状上下文只要获取有限的害虫轮廓边界点，就能有效地识别出害虫当图像发生二维变化时，改进的形状上下文算法提高了识别的准确度。,形状上下文在验证码识别中的应用,通常的验证码识别需要以下三个步骤。1图像进行二值化和细化处理。2去除干扰线，并进行图像切割，使得切割后的每幅图像只包含一个字符。3特征提取和单个字符识别。PS：用图形上下文进行字符识别首先，需要建立样本字符图库。即设置每幅图像的大小，对每个样本字符图像进行二值化和细化处理，得到了样本字符图库，接下来才能进行进行验证码图像实别。,用模糊形状上下文关系的红外与可见光图像匹配,具体方法是在提取图像边缘的基础上，用采样模板获取点特征图像，然后利用提出的不等分坐标空间提取局部形状统计信息的直方图，再以形状上下文特征开支与全局特征匹配开支的加权和作为相似性测度实现匹配。,其他应用,1.商标检索(用于检索从数据库中最接近的匹配的商标查询商标（用于检测商标侵权的）。)2.基于形状上下文的人脸匹配算法3.基于形状上下文描述子的步态识别4.基于相对形状上下文和谱匹