Linemod算法研究 (一)
开始研究传统图像处理算法，近期不再做任何deep learning相关内容，请暂时不要咨询我deep learning相关的东西。。。
先了解一下大致工作流程：
ref：Gradient Response Maps for Real-TimeDetection of Textureless Objects
注册过程
注册过程需要提取特征点，后续滑窗的时候就值拿这些特征点在场景图上进行滑窗，而不是传统意义上的图片滑窗，这样可以大大加速匹配过程。
提取特征点可以根据模板图本身的梯度情况，将一些梯度较大的点保留作为模板点，因为图像梯度往往包含着形状相关的信息，并且模板点在基于形状的模板匹配的实际场景中往往二值图居多，基本反应的是形状边缘。
现在考虑匹配阶段。
分数计算
由于后面需要进行滑窗算分，算分的过程可以理解为相似度匹配的过程，那么特征点的信息一方面需要包含位置信息，另一方面也需要包含某种值信息，用于和场景图进行相似度运算。
linemod选择保留的值信息是梯度的方向，因此后续进行相似运算也是判断梯度方向的一致性。
再次的，为了加速运算，梯度方向被进行了量化处理，这样做的好处是将方向离散化，离散有限的数据就可以制表，因此相似运算可以变成查表运算。
如果不考虑离散化，梯度的相似度可以理解为两个向量的相似度，即\(cos(\theta_1 - \theta_2)\)，但是考虑到可能真实场景中会遇到一些黑白invert的情形，因此对这一结果加了绝对值，当然了，这种方式并非绝对的好，后续会探讨一下相似度函数和量化方式在某些corner case下不妥的情况，并给出改进。。
离散化之后，可以人为对一些情况进行赋分：
在一些code中，红色方向和红色方向的相似度赋值为4分，红色和蓝色为3分，以此类推，对于大于九十度的，根据公式也是有分的，毕竟是cos绝对值嘛，opencv官方code是给了分的，而在某些code实现中，大于90度的是认为0分。
具体的：
OpenCV：
meiqua实现：
我个人是支持90度以上0分处理的，毕竟invert并不是对称，0分合理。
关于制表的过程，后面细讲。
此外，滑窗匹配的过程中你并不能太绝对的对比特征点和其对应的点的相似度，宽松化处理是要比对特征点和其对应点周围的点的相似度，这样能够增加命中率。
梯度扩散
不考虑梯度扩散，我们直接用naive的滑窗匹配其实就已经结束了，梯度扩散的目的实际上是为了减少漏匹配，在将某一位置的梯度结果扩散给相邻位置，这样在后续匹配的时候其他位置也会有一定可能被匹配到，因此可以理解为宽松化的处理。
需要注意的是，仅对场景图做扩散处理，因为我们在匹配阶段模板就只有特征点这一信息了，到这一节点已经没有模板的图像信息了。
这一过程可以形象的用论文中的图表示：
即原本没有任何梯度信息的一些点也被赋予了梯度信息。
离散化处理
如上所说，离散化处理是为了查表加速。
比较简单，以5位二进制表示为例：
因此上述扩散图的二进制表示就变成了：
问题1：
咱们观察一下该二进制表示的特点，有些角度是组合的比如00011，按照非离散的理解，这俩方向应该可以合成一个方向表示，如果我们合成一个方向表示，会有问题吗？换言之，我们在梯度量化前进行梯度扩散，然后进行量化，理论上就没有这些组合情况了，在后续查表的时候就不需要考虑组合情况的制表，理论运算应该少很多呀。
问题2：
实际spread的过程是从哪里开始spread的呢，随机，还是直接选择左上角点？事实上spread起始点的选取对结果是有影响的，这里需要一定设计。
先解答一下问题1，二进制表示后进行梯度扩散的底层实现是位或实现的，因此速度快，如果不二进制表示扩散，实现下来就比较低效，因此哪种方式速度更快，后续我会贴一下实验。。
对于问题2，code中都选择的是从右下角开始扩散，扩散到左上角，这样信息会向坐上偏移，可能更符合对坐标的量化，即向下取整，实际实现的时候代码也是很高效的，后续探讨。
提前制表
前面说了，如果场景图完成了量化，那么理论上你的特征点在任意位置的得分都是可以穷举的，按照8位量化讨论，你也就8个方向，我提前算好场景图每个位置的8个方向的相似度，到时候你模板滑到这了，我就拿你模板的方向去我的表里查，立马就知道结果了。
因此，我们只需要8个2维表就可以完成这一任务了。
事实上，如果先完成场景图的量化再制表，就失去意义了，因为相当于你在匹配的时候花了更长的时间来做表格，之后再用。。。
所以，制表是发生在你写代码阶段的。
场景图的情况显然就不止8种方向了，因为场景图会存在因为spread过程导致的梯度叠加，8位的话就有\(2^8\)种叠加情况，因此你需要制作一个\(2^8 * 8 = 2048\)大小的表格。
但是实际上我们在看code的时候发现，人家8位用的是256的表格，这是一个优化。
在制作表格的时候，分为高8位和低八位分别制表，在匹配的时候可以低8位查一个分，高八位查一个分，最终结果取两者的最大值，和直接查2048的表格结果是一样的，更加形象的理解可以理解为向量可以分解为左半区间和右半区间两个分量，由于只考虑方向，所以你取两个分量分别相似度的最值即可。（当然了，这种理解其实经不起推敲。。）
因此最终制作的表格大小就是\(2^4 * 8 * 2 =256\)
线性化内存
先考虑一下什么时候需要线性化内存。
现代cpu读取数据的方式是一次加载他之后的若干数据位到cache中，称之为cache line，所以如果你要处理的数据不在一个cache line中，就意味着要加载多次数据，会造成浪费，称之为cache miss，因此一般通过内存重排，将较近可能处理到的数据放在一个cache line内，可以大大减少访存次数。
由于linemod要实现对所有点的滑窗，因此实现过程中可以一个点一个点的滑窗，所以数据间隔就是一个滑窗的stride，所以把每隔stride的数据排在一起，这样就能得到 stride x stride个重排数据了，每次丢一个重排数据进去处理即可。
实际的工程化过程中有一些优化如指令集加速等，后续会根据code分析可能存在的问题、分析code中的加速trick等。
目前正在复现一个easist demo，复现完成之后会po出来。
标签：code,匹配,滑窗,梯度,算法,图像,扩散,Linemod,模板 From： https://www.cnblogs.com/aoru45/p/16810996.html