Fenrier Lab

如何实现一个卷积函数

本文,我们使用 C++ 来实现一个简单的卷积运算函数。卷积运算我们都不陌生了,它的过程其实就是卷积核在矩阵上面滑动,每停留一次就将卷积核及其所覆盖的区域进行 element-wise 相乘并求和,所有这样的求和结果就构成了输出矩阵的元素。 为了提高卷积运算的性能,采用并行计算的思想,我们可以令不同位置的卷积核同时开算,在足够理想的情况下,任意尺寸的矩阵卷积时间复杂度都将是 (\mathcal{O}(1))。 另一方面来看,单个卷积核的运算过程本质上可以看作是一维向量的点积。于是我们可以把卷积核及其所覆盖的矩阵块都展开成一维向量,然后使用向量点积来代替前述的 element-wise 相乘并求和。而这个矩阵展开的过程就叫做 im2col,通过 im2col,我们可以把卷积运算...
点我阅读更多...

使用CUDA实现一个简单的矩阵乘法

矩阵乘法可以说是高性能计算领域的新手村问题,同时也是很多重要应用的基石,它的基本算法相当简单,但是为了达到令人满意的速度,却需要花费相当大的精力来优化。下面,我们从最简单的实现开始 // VERSION 1 // A, B, C are all matrices // M, N are the dimensions C, and K is the columns of A and rows of B for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < K; k++) { C[i * N + j] += A[i *...
点我阅读更多...

使用 C++ 实现 im2col 操作

在上一篇文章中,我们介绍了 im2col 的基本概念,知道 im2col 是一种把图像卷积运算转换成矩阵乘法的巧妙方法。本篇文章我们将想办法自己动手实现一个 im2col 操作。首先定义函数 /** * @param data_im The image tensor. * @param im_c The number of channels in the image. * @param im_h The height of the image. * @param im_w The width of the image. * @param kh The height of the kernel. * @param kw The width of the kernel. *...
点我阅读更多...

图解卷积运算的 im2col 算法

卷积运算是一种提取图像特征的重要算法,它通过把给定的卷积核应用到图像上,从而缩减图像尺寸,达到提取特征的目的。卷积核在图像上每移动一次就对其覆盖的区域进行一次运算,具体的算法其实就是对应元素相乘然后求和,如果把参与运算的两个小矩阵 flatten 成一维的向量,那么这就是一次点积运算,正是因为这样的性质,使得卷积运算可以转换成矩阵乘法,从而利用现成的高性能矩阵乘法库实现对卷积的加速。下图展示了典型的卷积运算过程 如果我们把图像按卷积运算顺序分解成独立的小矩阵块 然后把每个小矩阵块 flatten 成行向量,再叠在一起,得到如下图所示的大矩阵 这就是所谓 im2col 过程,或者说 image to column,右边的展开矩阵就是图像的列表示形式。若假设图像尺寸为 \...
点我阅读更多...

如何检测出图片中的表格

通常,在我们使用 OCR 识别图片的时候,模型本身是无法知晓文档结构的,对于那些包含表格的文档,常出现的情况是识别出文字,但丢失了原有的表格结构。针对这一情况,我们来开发一个专门检测图片中表格的算法。 表格检测的具体思路很简单,考虑到表格是由多条线条构成的,因此我们可以首先把这些线条检测出来。在数字图像处理技术中,有一类比较经典的直线检测算法,被称为霍夫变换(Hough transform)。它的具体原理是利用直线极坐标方程 \[r = x \cos \theta + y \sin \theta\] 将 \(x-y\) 平面上的一个点 \((x_0, y_0)\) 变换成 \(\theta-r\) 平面上的曲线 \(r = x_0 \cos \theta + y_0 \sin \...
点我阅读更多...