integral函数Opencv源码理解-leetcode动态规划的使用场景

        integral积分图有三种构建方式，定义如下。前两种sum，sqsum比如可以用在相似度匹配算法NCC， 第三种titled常用在人脸检测算法的Harr特征提取场景。

 integral的代码实现设计

        由定义可知，sum, sqsum两种积分图除了累加定义不同，其实现思路是一样的。为了描述方便，后面代码设计主要以sum，title两种方式为典型进行分析。

sum模式的代码实现设计

        把一张图按照从左到右，从上到下的顺序遍历，sum是以统计每个像素点的之前的像素值累计之和，那么如果没有优化思想，每个输出像素点都要重新从头开始遍历图像并累加和，那么时间复杂度就是O(H *W *(1+2+3+...+H*W)≈O（H*W）^2，实际上完全没有必要。

        根据定义，我们可以发现当前像素点的积分结果与其左边和上边一个是有关系的！利用这个关系，可以重复利用之前统计过的像素值，而不用重新统计新坐标位置之前的像素和了，实现“看一遍”就出结果的效果。

        如下图，假设原图用src表示, sum表示积分图结果。现在要计算p(x,y)的积分结果，可以有两种实现设计，其时间复杂度都是O(H*W), 只是空间复杂度不同。

设计一（左边）：

需要一个额外的空间数组Buf，长度和图像宽w相同。 buf[i]表示该列累计到i的像素和。

sum(x,y)=sum(x-1，y) +Buf(x-1)+src(x,y)

设计二（右边）：

需要一个额外空间变量Sx，表示该行累计到x坐标之前的像素和。

sum(x,y)=sum(x,y-1)+Sx+src(x,y)

titled模式的代码实现设计

        同样，我们也可以观察到titled模式的积分统计也是有规律的，当前像素的结果与其周边的几个点也有关系。最终也有两种实现设计方式。

        我们同样用src指代原图，用titled指代旋转45度的积分图结果。

设计一（左边）：

需要一个额外的空间数组Buf，长度和图像宽w相同。 buf[i]表示到第i行，其右斜对角的像素和。

titled(x,y)= titled(x-1,y-1)+Buf(x)+Buf(x+1)+src(x,y)

设计二（右边）：

titled(x,y)= titled(x-1,y-1)+ titled(x+1,y-1)- titled(x,y-2)+src(x,y)+src(x,y-1)

        另外对于titled模式，请注意，上面示意的只是中间位置像素点的计算，当第一行，或者第一列，最后一列时候的处理关系如下，上面两种设计对这种边界的处理是相同的。

• titled(x,y)=src(x,y),   if y=0
• titled(x,y)=titled(x+1,y-1)+src(x,y)+src(x,y-1),  if x=0
• titled(x,y)=titled(x-1,y-1)+src(x,y)+src(x,y-1),  if x=w-1

小结

        对于sum, titled，opencv的实现分别采用了设计2，设计1。并且为了使计算代码更简洁，在实现时候，sum,titled的内存分配都会比src多一行和一列。最终的结果在去掉这一行一列。

        至此，将integral积分图的代码实现流程已经分析完毕，sum, sqsum的计算比较容易复现，titled模式下，对维护每行斜对角累计像素和的Buf更新，有点不太容易理解。后面如果大家有需求，欢迎留言，再把我写的python实现代码贴一下，今天就到这里啦。

        整体代码实现的设计思路就是用到了动态规划的思想，想想自己之前刷过的题，感觉好亲切啊，有没有？