1.ID : simakeng2.个人邮箱 1939802059@qq.com
3.原创技术文章：
目前没发表过，不过好像发点知识也能过审核？那这里发一点自己研究图形学所得好了。。。
《利用卷积计算法进行边缘查找算法以及GPU加速的一点研究》
<前排提醒：这篇文章是为了拿一个ID现写的，资料图片来自百度搜索，已注明出处>
图形卷积运算是一种对图像的运算方法，卷积操作有一个重要的概念，这里假定你知道什么是图形运算中的卷积核，不知道的可以参照下面这个图：
<图源：百度图片搜索>
常用于图形卷积的算子有很多，这里我用的是Sobel算子
他对一个灰度图进行运算可以有这样的效果：
<图源:百度百科词条图片>
常规的图形边缘查找算法就是对灰度图梯度求导，导数越大，梯度越大，就是一个边缘。
Sobel算子则是利用了这一种思想：
1 0 -1
2 0 -2
1 0 -1
这是一个横向的边缘查找算子，可以预料到，当这个算子碰到差异很大的边缘的时候，运算出来的结果必然很大，灰度基本相同的时候，结果几乎为0.
另外由于这个算子的和为0，计算的结果必定很暗，如果要做COC（文本识别）等运算可以考虑二值化，
下面是几个不同方向的Sobel算子：
垂直：
1 2 1
0 0 0
-1 -2 -1
倾斜：
2 1 0
1 0 -1
0 -1 -2
以及
0 -1 -2
-1 0 1
2 1 0
对一个灰度图用这个算子计算，得到的结果MAX或者均值都能得到不错的结果
代码：
[C++] 纯文本查看 复制代码 /**************************************************
* Sobel算子边缘检测
* parameter: srcData - 原始图像数据指针
* dstData - 存储处理后的图像
* lWidth,lHeight - 图像的宽和高
* dLineBites - 单行图像的字节数(4的倍数)
备注:务必注意这个算子只允许单色图形，彩色图形请使用色觉公式转换
**************************************************/
void WINAPI SobelEdgeDetect(LPBYTE srcData,LPBYTE dstData,LONG lWidth,LONG lHeight,DWORD dLineBites)
{
int KERNEL[4][9] = {{-1,0,1,-2,0,2,-1,0,1},
{-1,-2,-1,0,0,0,1,2,1},
{-2,-1,0,-1,0,1,0,1,2},
{0,-1,-2,1,0,-1,2,1,0}};
int i,j,k,kernel_sum,total_sum = 0,nMax = 0;
unsigned char* pTmpSrcData = NULL;
unsigned char* pTmpDstData = NULL;
for (i = 1;i < lHeight - 1;i++)
{
pTmpSrcData = srcData + dLineBites * i;
pTmpDstData = dstData + dLineBites * i;
for (j = 1;j < lWidth - 1; ++j)
{
total_sum = 0;
nMax = 0;
for (k = 0;k < 4;k++)
{
kernel_sum = *(pTmpSrcData + j - dLineBites - 1) * KERNEL[k][0]+
*(pTmpSrcData + j - dLineBites ) * KERNEL[k][1]+
*(pTmpSrcData + j - dLineBites + 1) * KERNEL[k][2]+
*(pTmpSrcData + j - 1) * KERNEL[k][3]+
*(pTmpSrcData + j ) * KERNEL[k][4]+
*(pTmpSrcData + j + 1) * KERNEL[k][5]+
*(pTmpSrcData + j + dLineBites - 1) * KERNEL[k][6]+
*(pTmpSrcData + j + dLineBites ) * KERNEL[k][7]+
*(pTmpSrcData + j + dLineBites + 1) * KERNEL[k][8];
kernel_sum = abs(kernel_sum);
//total_sum += abs(kernel_sum);
if(nMax < kernel_sum)
nMax = kernel_sum;
}
if(nMax > 255)
nMax = 255;
*(pTmpDstData + j) = (unsigned char)nMax;
}
}
}
由于卷积算法包含四个for循环（固定卷积核则是两个），他的复杂度为O(n2),为了提高速度，这里给出两个方法进行加速
1. 离散傅里叶变换加速
卷积定理：
[backcolor=rgba(128, 128, 128, 0.05)]如果两个时间序列h(k)和x(k)的DFT分别为H(m)和X(m)，那么h(k) * x(k)[backcolor=rgba(128, 128, 128, 0.05)]的DFT为H(m) 点乘X(m)[backcolor=rgba(128, 128, 128, 0.05)]，H(m) 点乘X(m)[backcolor=rgba(128, 128, 128, 0.05)]的IDFT为`h(k) * x(k)。
因为傅里叶变化是将时域上的信号变为了频域上的信号，所以会常常看到时域上的序列卷积等于它们对应频域上的点积的说法。
最后，如果已经看过了离散傅里叶的计算过程，会发现离散傅里叶的计算复杂度也是相当的大，当处理的信号N过大时耗费的时间非常多，这就有了计算傅里叶的快速方法——快速傅里叶变换(FFT)。快速傅里叶的算法思想并不太难，FFT应用的是分治算法，分而治之。具体到算法还是有些复杂的，不过思路就是讲N点的DFT不断等分，直到分到很小，计算2点，4点或者混合基的DFT，可以大大的降低计算DFT的计算复杂度。 从这也能看出，FFT不是新的理论，只是DFT的一种计算方法，而且计算的是DFT的精确结果，不是DFT的近似结果。
具体的实现这里先不谈，不过应用FFT也应考虑到FFT算法自身的开销（O(nlogn)）
2.GPU并行加速
利用GPU的高并行，高延迟架构，计算这种运算可以得到很大的加速
利用用DX11的ComputeShader可以很轻松的创建设备并加载贴图，在Shader定义好函数
我由于没有对显存读取做优化，提升并不明显，一张1024*1024的图像运算了大概0.04秒
我知道现写有点过分，但是高三狗真的没时间啊QuQ
望Hmily大大放过 :-) |
[复制链接]
吾爱游客
发表于 2017-10-27 23:46
发表于 2017-10-28 12:18
，要不等光棍节你自己来注册吧，不过都高三了，最后半年少上网吧，冲刺一下，明年暑假整个世界都是你的。
