前面的博文Deformable Parts Model (DPM) 检测加速算法简介中已经提到过，
[1] ECCV 2012 Exact Acceleration of Linear Object Detectors
一文借助FFT，将模型与HOG特征在空域中的卷积计算，转化为频域中对应位置元素的乘法运算，实现了DPM检测的加速。另外，这篇论文给出了整个DPM检测算法的C++实现，称为Fast Fourier Linear Detector，简称FFLD（点击下载代码），参考价值非常大。本文将对DPM算法检测流程进行简要回顾，然后简述[1]中采用FFT对卷积运算进行加速的方法FFLD，最后阐述如何在FFLD代码的基础上进行进一步的加速。
算法回顾
首先对DPM检测流程进行回顾，如图1所示。
图1 DPM检测标准流程
FFLD：采用FFT对卷积运算进行加速
[1]中对于为何FFT能够对模型与HOG特征的卷积计算进行加速做了较为详细并且浅显易懂的解释说明，这里不再重复。下面采用一维信号距离简单说明。
假设有两个长度为n的一维向量x和y，我们要在时域上直接计算这两个向量的卷积z，那么计算的复杂度是O(n*n)的。但是转换到频域计算就不一样了。时域上的卷积对应于频域上的相乘。对x和y进行FFT，得到X和Y，复杂度是O(nlogn)的，在频域上X和Y两个序列对应位置元素做复数乘法，得到频域序列Z，其复杂度是O(n)的，再将频域上的Z进行IFFT得到时域的z，复杂度是O(nlogn)的，所以利用FFT计算卷积能够将总的复杂度从O(n*n)降至O(nlogn)，并且序列长度越大，降低的程度就越多。
假设我们有模型F和三个HOG特征层HOG0，HOG1和HOG2，F和这三个HOG特征层的卷积结果分别记为R0，R1和R2，如图2所示，注意，在进行卷积计算时，F不会跨越到HOG特征之外，所以得到的卷积计算结果的尺寸会比HOG特征的尺寸要小。
图2 直接采用卷积计算
下面我们用FFT对卷积计算进行加速。由于HOG特征的尺寸和模型F的尺寸不一致，如果按照HOG特征和模型F各自的尺寸进行FFT，不能在频域上进行相乘。鉴于F的尺寸较小，所以需要对F进行填充，填充区域的值全部取零，然后再进行FFT。下面按照[1]中的表述给出三种FFT的实现方法。
第一种如图3所示。将F填充至HOG0，HOG1和HOG2的尺寸，进行FFT，在频域中分别相乘，再进行IFFT，选取反变换结果中的合适区域，得到卷积结果R0，R1和R2。这种实现方法的缺点是，需要对F进行多种尺寸的填充。DPM检测中HOG层尺寸多，而且根模型和部分模型众多，如果采用这种方法，需要在内存中保存很多的模型FFT，内存消耗较大。
图3 第一种FFT实现方法
第二种如图4所示。仅将F填充至HOG0的尺寸，进行FFT。HOG0无需填充直接进行FFT，HOG1和HOG2也填充至HOG1的尺寸，进行FFT，然后频域相乘，再进行IFFT，从反变换结果的适当区域中取出R0，R1和R2。这种做法的好处是只需要将模型填充至一种尺寸进行FFT，内存消耗较小，不妥之处是所有的频域相乘运算都是按照HOG特征的最大尺寸进行的，乘法次数多，IFFT运算的耗时也多，总的来说就是运算量大。
图4 第二种FFT实现方法
第三种如图5所示。将F填充至HOG0的尺寸，进行FFT。HOG0无需填充直接进行FFT。尺寸较小的HOG特征层进行非重合拼接，填入HOG0尺寸的矩形中，进行FFT。频域中相乘后，再进行IFFT，从反变换结果的适当区域中取出R0，R1和R2。这种方法避免了前两种方法的缺点。一方面，仅需要将模型填充至HOG0尺寸进行FFT计算，模型FFT消耗的内存小于前面所说的第一种方法。另一方面，不同层HOG特征不重叠地拼接至HOG0尺寸，再进行FFT，频域相乘，以及IFFT运算，HOG0尺寸的运算量比前面所说的第二种方法要少。所以实际中采用这种拼接组合的思想，用FFT对卷积运算进行加速。
图5 第三种FFT实现方法
采用FFT加速的DPM检测算法如图6所示，这也是FFLD程序的流程图。
图6 用FFT加速的DPM检测流程
FFLD程序的进一步优化
FFLD给出的只是一个示例程序，如果直接应用于实际的检测项目中，还存在一些不足之处。再加上别的论文中也提到了不少加速检测的方法，所以很自然的想法就是对FFLD程序进行进一步的优化。
对模型FFT进行缓存
FFLD中给出的检测示例程序中，对每一张图片进行检测，都需要走完图6中的各个步骤。如果需要检测的图片的尺寸都是相同的，那么模型FFT这部分的计算，实际上只需要进行一次，这样就能够给检测省下不少时间。
然而实际的应用环境中，图片的尺寸可能有很多种，我们也没有办法把这些图片缩放至同一种固定尺寸，在这样的情况下，我们需要寻找新的办法，避免重复多次的模型FFT的计算。
解决这一问题的一种思路，就是对模型FFT进行缓存操作。当要检测一张图片时，现在内存中查找适配该尺寸的模型FFT是否已经存在，如果已经存在，那么直接返回这部分内存，进行后续的检测运算；如果不存在，则计算这个尺寸的模型FFT并返回，进行后续的检测运算。每次要新建新的尺寸的模型FFT时，要看看模型FFT占用的内存是否已经达到预设的最大值，如果是，则删除某些已经长期未被使用的某些尺寸的模型FFT。这种优化思路下的检测流程如图7所示。
你不能左右天气，但你能转变你的心情
