喜欢2次
大家好，我们是大黄蜂队，编号是 CICC1948。此贴将简要介绍在目标追踪领域最为基础的模板匹配算法，并分析对其作硬件加速的思路。
一、目标追踪和图像识别
一般来说，提到机器视觉这个概念都会想到图像识别，比如人脸识别、文本识别等等，目标追踪这个概念在平时接触的相对比较少。但实际上，目标追踪可以理解为图像识别的动态过程：图像识别往往是先在一个静态的图象中寻找到某一片像素区域（比如从背景画面中框选出人脸或文字），然后再对这片像素区域作分析（比如提取人脸关键点信息等等）；而目标追踪则是在一段视频流中进行，它根据指定的追踪目标的信息在视频的每一帧图象中进行搜寻，获取每一帧中目标的大小和坐标。对视频流作目标追踪的好处是，我们不仅可以动态地对物体进行定位，还可以由此分析出被追踪物体的速度、加速度等参数，如下面这段动图所示：
二、目标追踪的分类与难点
目标追踪可以分为单目标跟踪、多目标跟踪、多目标多摄像头跟踪（MTMCT）、姿态跟踪等。相比于单纯地在一幅图中找到某一个物体，在一段视频流中执行的目标追踪往往会面临一些更加复杂的情况。比如：形态变化，即运动目标并不是一直保持同一个姿态。尤其是在对于运动员、行人等姿态在不断进行快速变化的目标的追踪中，往往会因此引入不少的噪声；尺度变化，即运动目标在视频中和摄像头的距离并不是一直不变的，当目标靠近或者远离摄像头的时候，在视频中就会表现出目标尺度大小的变化，这给算法的自适应能力带来了挑战；遮挡与消失，即目标物体在运动过程中可能会被其他物体短暂地遮挡，因此需要算法能够在目标重新出现在帧图象中时，迅速地重新捕捉到目标。
以上对目标追踪这一领域做了简要的说明，下面将会介绍目标追踪算法中最简单的一种 —— 模板匹配算法。
三、模板匹配算法
模板匹配（TemplateMatching）是在图像中寻找目标的方法之一。原理很简单，就是把待追踪的目标图像存于一个模板中，然后在视频的每一帧图像中寻找和模板图像最相似的区域。
那么，如何才能评估图像中某一片像素区域和模板图像的相似程度呢？常用的算法是计算两幅图像的 绝对误差和（SAD）。我们把图像区域和模板图像都转为灰度，这个用经典的心理学公式可以实现；然后把图像区域和模板中对应位置像素点的灰度值相减并取绝对值，这就代表了图像中每个像素点图像和模板间的差距，即“绝对误差”；最后把这所有的绝对误差相加得到绝对误差和（SAD），就可以代表正片图像区域和模板之间的差别，SAD 越小，就表明图像和模板之间的差别越小。
因此，模板匹配算法步骤就很明确了：用模板在整帧图像中扫描，对于一个超清视频（1280*720 P）如果我们用 50*50 大小的模板进行匹配，扫描完整个图像就需要运算（1280-50+1）*（720-50+1）= 826001 次。每次运算都会计算出一个 SAD 值，而我们只要找到这个最小的 SAD 值对应的模板所在位置，就可以认为找到了帧图像中和模板最为接近的一片像素区域。
四、硬件加速思路
在分析硬件加速之前，首先要弄明白这个算法在软件实现中有哪些冗余的操作：首先是遍历次数多（前文算出来的就已经达到了 82.6 万次），每次遍历都需要对 50 * 50=2500 个像素点作减法、再取绝对值、把 2500 个绝对值加到一起才得到最终的 SAD 值，这样的计算过程太过繁琐。另外，假如每一帧的图像都存放在内存中，那么每次遍历都需要额外从内存中读入一些像素点的灰度值，这段访存的操作带来了时间上的消耗；当视频的大小超过了内存的容量，很可能就需要把数据存放在外存，导致访存所需的时间进一步增加。
而硬件计算的好处，就是可以对很多个数据作并行操作，而不用像 CPU 那样只能串行的处理数据。并且，我们可以通过自定义一组寄存器阵列，将部分帧数据暂存于寄存器阵列中，就省下了之后访存所需的时间。比如我一次性把一大块像素区域都存在一个寄存器阵列中，那么每次匹配的时候，我可以直接从寄存器阵列里选出一片 50 * 50 的像素区域与模板进行比较，而不用访问存储器中原视频的帧数据；并且我可以同时对 2500 个像素点作减法，这在一个时钟周期就可以完成，速度会比软件实现快很多。
此外，在算法层面也可以作改进：比如我可以尝试预先判断某些区域是不是物体最可能移动到的位置，优先对这片区域的图像进行模板匹配，而在此之外的区域就可以不管。总之，软硬件层面加速的手段还是很多的。
以上就是我们对于目标追踪和模板匹配、及其硬件加速思路的分享，之后也会陆续更新一些图像处理相关的分享贴。由于我们整体的方案还是比较简单，所以希望大佬们轻喷（逃）
End
