[db:标题]

继去年上半年一鼓作气研究了几种不同的模版匹配算法后，这个方面的工作基本停滞了有七八个月没有去碰了，因为感觉已经遇到了瓶颈，无论是速度还是效率方面，以当时的理解感觉都到了顶了。年初，公司业务惨淡，也无心向佛，总要找点事情做一做，充实下自己，这里选择了前期一直想继续研究的基于离散夹角余弦相似度指标的形状匹配优化。 　　在前序的一些列文章里，我们也描述了我从linemod模型里抽取的一种相似度指标用于形状匹配，个人取名为离散夹角余弦，其核心是将传统的基于梯度点积相似度的的指标进行了离散化： 　　传统的梯度点积计算公式如下： 　　　　 　　对于任意的两个点，通过各自的梯度方向，按照上述公式可计算出他们的相似度。 　　那么离散夹角余弦的区别是，不直接计算两个梯度方向的余弦，而是提前进行一些定点化，比如，早期的linemod就是把360度角分为了8份，每份45度，这样[0,45]的梯度方向标记为0，[45,90]的梯度方向标记为1，依次类推，直到[315, 360]之间的梯度方向标记为7，这样共有8个标记，然后提前构建好8个标记之间的一个得分表，比如，下面这样的一个表： 　　 　　这个表的意思也很简单，就是描述不同标记之间的得分，比如两个点的梯度方向，都为3或者4或者5，那么他们的得分就比较高，可以取8，如果一个为1，一个为6，则得分就只有2， 一个为0，一个为5，则得分为0（即完全相反的两个方向）。 　　很明显，角度量化的越细，则得到的结果越和传统的梯度点积结果越接近。但是计算量可能也就越大， 　　关于这个过程，我去年的版本也有弄过8角度、16角度及32角度，个人觉得，在目前的计算机框架下，16角度应该是既能满足进度要求，又能在速度方面更为完美的一个选择。 　　这里记录下最近对基于16角度离散余弦夹角指标的形状匹配的进一步优化过程。 　　一、核心的优化策略 　　通过前面的描述，我们知道，这种方法的得分是通过查表获取的，而且，在大部分的计算中，是没有涉及到浮点计算的，我们通过适当的构造表的内容，可以通过简单的整数类型的加减乘除来得到最后的得分。这个的好处有很多，其中一个就是精度问题，在基于梯度点积的计算中，如果采用float类型来累计计算结果，通常或多或少的存在某些情况下的精度丢失，而且还不好定位哪里有问题。还有个好处就是真的可以加速，当然这个的加速主要是通过一个很特殊，但是又很有效的SSE指令集语句实现的，这个指令就是_mm_shuffle_epi8，其原型及相关介绍如下： 　　　　__m128i_mm_shuffle_epi8(__m128ia,__m128ib) 　　这是个很牛逼的东西，如果我们把a看成一个16个元素的字节数组，b也是一个16个元素的字节数据，则简单的理解他就是实现下述功能： 　　　　dst[i] = a[b[i]]; 即一个16个元素的查表功能。 　　很明显，b[i]要在0到15之间才有效，否则，就查不到元素了，但是该指令还有比较隐藏的功能是，当b[i]大于15时，dst就返回0了。 　　为什么说这个指令牛逼，我们看我们前面说的这个获取离散夹角余弦的过程，对于两个等面积的区域，假定一个区域的量化后的离散角度标记保存在QuantizedAngleT内存中，另外一个保存在QuantizedAngle内存中，他们的宽和高分别为ValidW和ValidH，则这两个区域按照前面定义的标准，其得分可用下述代码表示（这里SimilarityLut是16角度离散的）: int Score = 0; for (int Y = 0; Y < ValidH; Y++) { int Index = Y * ValidW; for (int X = 0; X < ValidW; X++) { Score += SimilarityLut[QuantizedAngleT[Index + X] * 16 + QuantizedAngle[Index + X]]; // Score += SimilarityLut[QuantizedAngleT[Index + X], QuantizedAngle[Index + X]]; } } 　　如果把SimilarityLut看成是二维的数组，上面注释掉的得分可能看起来更为清晰。 　　实际上，我们在进行模版匹配的时候大部分都是在进行这样的得分计算，因此，如果上面的过程能够提速，那么整体将提速很多。