【算法设计】快速计算积分图
2023-09-11 14:20:12 时间
积分图是图像中十分常用的方法,最初是在Haar特征的快速计算中学到(参考博文:利用积分图像法快速计算Haar特征),后来发现在均值滤波,二值化等图像处理方法中也十分常见。
积分图的简要介绍可以参考博文:利用积分图像法快速计算Haar特征,这里不再重复了。本篇主要是小记一下积分图的计算方法。
由于积分图中每个单元存储的信息是原图中此位置左上角所有像素之和,所以对一张W*H的图像直接求取积分图,需要:
(1+2+...+W-1)*H+(1+2+...+W)*(H=1) = (w-2)*H/(W-1)+2(W+1)*(H-1)/W
次加法。
一种简单的快速计算方法
最直接的快速计算方法是利用以计算积分求当前位置的积分,其思想正如快速计算Haar特征的方法。
即,Integral(i,j) = Integral(i,j-1) + Integral(i-1,j) - Integral(i-1,j-1) + Image(i,j);
于是,对一张W*H的图像直接求取积分图,需要:
(W-1)+(H-1)+3*(W-1)*(H-1)
次加法。代码如下:
void integral(unsigned char* inputMatrix, unsigned long* outputMatrix, int width, int height){ // calculate integral of the first line for(int i=0;i<width;i++){ outputMatrix[i] = inputMatrix[i]; if(i>0){ outputMatrix[i] += outputMatrix[i-1]; } } for (int i=1;i<height;i++){ int offset = i*width; // first column of each line outputMatrix[offset] = outputMatrix[offset-width]+inputMatrix[offset]; // other columns outputMatrix[offset+j] = outputMatrix[offset+j-1] + outputMatrix[offset-width] + outputMatrix[offset-width-1] + inputMatrix[offset]; } } return ; }
改进的快速计算方法
通过观察上一种方法,发现积分Integral(i,j) 并不需要由三个位置的积分计算出来,只需要左边Integral(i,j-1)加上当前列的和即可。
即,Integral(i,j) = Integral(i,j-1) + ColumnSum(j);
因此,对一张W*H的图像直接求取积分图,只需要:
(W-1)+(H-1)+2*(W-1)*(H-1)
次加法。代码如下:
void fastIntegral(unsigned char* inputMatrix, unsigned long* outputMatrix, int width, int height){ unsigned long *columnSum = new unsigned long[width]; // sum of each column // calculate integral of the first line for(int i=0;i<width;i++){ columnSum[i]=inputMatrix[i]; outputMatrix[i] = inputMatrix[i]; if(i>0){ outputMatrix[i] += outputMatrix[i-1]; } } for (int i=1;i<height;i++){ int offset = i*width; // first column of each line columnSum[0] +=inputMatrix[offset]; outputMatrix[offset] = columnSum[0]; // other columns for(int j=1;j<width;j++){ columnSum[j] += inputMatrix[offset+j]; outputMatrix[offset+j] = outputMatrix[offset+j-1] + columnSum[j]; } } return ; }
(转载请注明作者和出处:http://blog.csdn.net/xiaowei_cqu 未经允许请勿用于商业用途)
相关文章
- 力导向算法从入门到放弃!
- Java实现 蓝桥杯VIP 算法训练 步与血(递推 || DFS)
- Java实现 蓝桥杯VIP 算法提高 计算时间
- Java实现 蓝桥杯VIP 算法提高 陶陶摘苹果2
- Java实现 蓝桥杯VIP 算法训练 平方计算
- Java实现 蓝桥杯VIP 算法训练 薪水计算
- Java实现 蓝桥杯VIP 算法训练 最大值与最小值的计算
- Python实现的计算马氏距离算法示例
- Apache Spark源码走读(十一)浅谈mllib中线性回归的算法实现&Spark MLLib中拟牛顿法L-BFGS的源码实现
- 一个计算数字的步数算法
- C++11 用next_permutation算法计算排列组合数
- 内部元素一一对应的集合的算法优化,从list到hashmap
- 《安富莱嵌入式周报》第282期:CMSIS-DSP手册引入计算图,树莓派单片机RP2040超频到1GHz,COBS字节编码算法,纯手工为PS1打造全新亚克力外壳
- ML:数据科学/机器学习领域经验总结—对于特征个数大于样本量的高维数据集,用什么算法进行预测,效果会更好?
- 基于改进量子粒子群算法的电力系统经济调度(Matlab代码实现)
- m基于LOC-PCA算法的人脸重建算法matlab仿真,给定人物侧脸实现正脸重建
- 精英反向学习带扰动因子的混沌蚁狮算法-附代码
- C语言之linux内核实现平方根计算算法
- 【LeetCode-面试算法经典-Java实现】【008-String to Integer (atoi) (字符串转成整数)】
- 【Python算法】实验5-计算中值及分治技术
- 机器学习经典算法具体解释及Python实现--K近邻(KNN)算法
- 二分图匹配(对于匈牙利算法的一些理解)
- count算法计算容器中元素出现次数
- m基于BBV网络的节点强度分布算法matlab仿真
- 2021.12.5再肝算法(一)
- 目标检测系列算法:简单实现YOLO语音TTS报警系统(检测人员入侵室内或室外)
- 校园导航系统,生成图,图之间最短路径问题(温习迪杰斯特拉算法,普利姆算法)