二维图像处理中的可分离卷积核

谁践踏了优雅 2022-11-29 12:19 224阅读 0赞

本文参考书籍《Opencv算法精解》，作者：张平

*  ### 可分离卷积核的定义 ###

如果一个卷积核至少由两个尺寸比它小的卷积核full卷积而成，并且在计算过程中在所有边界处均进行扩充零的操作，且满足

![Kernel=kernel\_\{1\}\\bigstar kernel\_\{2\}\\bigstar\\cdots \\bigstar kernel\_\{n\}][Kernel_kernel_1_bigstar kernel_2_bigstar_cdots _bigstar kernel_n]

其中![kernel\_\{i\}][kernel_i]的尺寸比![Kernel][]小，![1\\leqslant i\\leq n][1_leqslant i_leq n]，则称该卷积核是可分离的。

在二维图像处理中经常将一个卷积核分为一维水平方向和一维垂直方向上的两个卷积核，例如：

![\\begin\{pmatrix\} 4 &8 & 12\\\\ 5& 10 &15 \\\\ 6& 12 & 18 \\end\{pmatrix\}=\\begin\{pmatrix\} 1 & 2 & 3 \\end\{pmatrix\}\\bigstar \\begin\{pmatrix\} 4\\\\ 5\\\\ 6 \\end\{pmatrix\}=\\begin\{pmatrix\} 4\\\\ 5\\\\ 6 \\end\{pmatrix\}\\bigstar \\begin\{pmatrix\} 1 & 2& 3 \\end\{pmatrix\}][begin_pmatrix_ 4 _8 _ 12_ 5_ 10 _15 _ 6_ 12 _ 18 _end_pmatrix_begin_pmatrix_ 1 _ 2 _ 3 _end_pmatrix_bigstar _begin_pmatrix_ 4_ 5_ 6 _end_pmatrix_begin_pmatrix_ 4_ 5_ 6 _end_pmatrix_bigstar _begin_pmatrix_ 1 _ 2_ 3 _end_pmatrix]

举例计算：

![gif.latex][]![\\begin\{pmatrix\} 1 & 2 & 3 \\end\{pmatrix\}\\bigstar \\begin\{pmatrix\} 4\\\\ 5\\\\ 6 \\end\{pmatrix\}][begin_pmatrix_ 1 _ 2 _ 3 _end_pmatrix_bigstar _begin_pmatrix_ 4_ 5_ 6 _end_pmatrix]

将卷积符号后面的矩阵当作卷积核，前面的矩阵当作图像。首先将卷积核逆时针旋转180度得到如下矩阵：

![\\begin\{pmatrix\} 6\\\\ 5\\\\ 4 \\end\{pmatrix\}][begin_pmatrix_ 6_ 5_ 4 _end_pmatrix]

计算过程中图像不动，按照先行后列的顺序移动卷积核，对应位置相乘然后求和。具体计算过程如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pnajEyMzMyMQ_size_16_color_FFFFFF_t_70][]

计算结果即为分离前的卷积核。注意full卷积是不满足交换律的，但是一维水平方向和一维垂直方向上的卷积核的full卷积是满足交换律的。

*  ### 离散卷积的性质 ###

如果卷积核Kernel是可分离的，且![Kernel=kernel\_\{1\}\\bigstar kernel\_\{2\}][Kernel_kernel_1_bigstar kernel_2]，则有：

![I\\bigstar Kernel=I\\bigstar (kernel\_\{1\}\\bigstar kernel\_\{2\})=(I\\bigstar kernel\_\{1\})\\bigstar kernel\_\{2\}][I_bigstar Kernel_I_bigstar _kernel_1_bigstar kernel_2_I_bigstar kernel_1_bigstar kernel_2]

*  ### 卷积核分离的意义 ###

假设图像矩阵![I][]的尺寸为![H\_\{1\}\*W\_\{1\}][H_1_W_1]，卷积核Kernel的尺寸为![H\_\{2\}\*W\_\{2\}][H_2_W_2]，那么进行same卷积的运算量大概为![(H\_\{1\}\*W\_\{1\})\*(H\_\{2\}\*W\_\{2\})][H_1_W_1_H_2_W_2]，即复杂度为![O(m^\{2\}\*n^\{2\})][O_m_2_n_2]。如果将卷积核分离为一维水平方向上![1\*W\_\{2\}][1_W_2]的卷积核和一维垂直方向上的![H\_\{2\}\*1][H_2_1]的卷积核，运算的复杂度减少为![O(m^\{2\}\*2n)][O_m_2_2n]，随着卷积核尺寸的增大，分离卷积核的运算优势更加明显。

*  ### 卷积核分离应用举例 ###

高斯卷积核和均值卷积核都是可分离的，高斯卷积核的构建可参考我的[另一篇博客][Link 1]。接下来主要讲解分离均值卷积核与图像卷积的操作步骤，均值卷积核可分解为如下形式：

![\\frac\{1\}\{9\} \\begin\{bmatrix\} 1 & 1 & 1\\\\ 1 & 1& 1\\\\ 1 & 1 & 1 \\end\{bmatrix\}=\\frac\{1\}\{3\}\\begin\{bmatrix\} 1\\\\ 1\\\\ 1 \\end\{bmatrix\}\*\\frac\{1\}\{3\}\\begin\{bmatrix\} 1 & 1&1 \\end\{bmatrix\}][frac_1_9_ _begin_bmatrix_ 1 _ 1 _ 1_ 1 _ 1_ 1_ 1 _ 1 _ 1 _end_bmatrix_frac_1_3_begin_bmatrix_ 1_ 1_ 1 _end_bmatrix_frac_1_3_begin_bmatrix_ 1 _ 1_1 _end_bmatrix]

第一步：假设有一副尺寸为3\*3的图像![I][]，想要使用尺寸为3\*3的卷积核进行均值滤波，对其进行边界扩充后（灰色部分为扩充的边界像素）表示如下：

![20190712143434977.png][]

第二步：使用一维水平方向上的卷积核 ![\\small \\begin\{bmatrix\} 1 & 1&1 \\end\{bmatrix\}][small _begin_bmatrix_ 1 _ 1_1 _end_bmatrix]，对边界扩充后的图像进行卷积，得到一个中间结果（由于卷积核宽度为3，因此第一列和最后一列无法进行卷积运算，因此保持初始化的值为0），如下所示：

![20190712144437138.png][]

第三步：使用一维垂直方向上的卷积核![\\begin\{bmatrix\} 1\\\\ 1\\\\ 1 \\end\{bmatrix\}][begin_bmatrix_ 1_ 1_ 1 _end_bmatrix]，对中间结果图像进行卷积（由于卷积核高度为3，因此第一行和最后一行无法进行卷积运算，因此保持初始化的值为0），如下所示：

![20190712145323258.png][]

第四步：将两次卷积得到的结果除以卷积核的面积，并赋值给结果图像，如下所示：

![20190712145855461.png][]

注意：在实际编程中，第三步和第四步通常合并到一起实现，提高算法效率

[Kernel_kernel_1_bigstar kernel_2_bigstar_cdots _bigstar kernel_n]: https://private.codecogs.com/gif.latex?Kernel%3Dkernel_%7B1%7D%5Cbigstar%20kernel_%7B2%7D%5Cbigstar%5Ccdots%20%5Cbigstar%20kernel_%7Bn%7D
[kernel_i]: https://private.codecogs.com/gif.latex?kernel_%7Bi%7D
[Kernel]: https://private.codecogs.com/gif.latex?Kernel
[1_leqslant i_leq n]: https://private.codecogs.com/gif.latex?1%5Cleqslant%20i%5Cleq%20n
[begin_pmatrix_ 4 _8 _ 12_ 5_ 10 _15 _ 6_ 12 _ 18 _end_pmatrix_begin_pmatrix_ 1 _ 2 _ 3 _end_pmatrix_bigstar _begin_pmatrix_ 4_ 5_ 6 _end_pmatrix_begin_pmatrix_ 4_ 5_ 6 _end_pmatrix_bigstar _begin_pmatrix_ 1 _ 2_ 3 _end_pmatrix]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbegin%7Bpmatrix%7D%204%20%268%20%26%2012%5C%5C%205%26%2010%20%2615%20%5C%5C%206%26%2012%20%26%2018%20%5Cend%7Bpmatrix%7D%3D%5Cbegin%7Bpmatrix%7D%201%20%26%202%20%26%203%20%5Cend%7Bpmatrix%7D%5Cbigstar%20%5Cbegin%7Bpmatrix%7D%204%5C%5C%205%5C%5C%206%20%5Cend%7Bpmatrix%7D%3D%5Cbegin%7Bpmatrix%7D%204%5C%5C%205%5C%5C%206%20%5Cend%7Bpmatrix%7D%5Cbigstar%20%5Cbegin%7Bpmatrix%7D%201%20%26%202%26%203%20%5Cend%7Bpmatrix%7D
[gif.latex]: https://private.codecogs.com/gif.latex?
[begin_pmatrix_ 1 _ 2 _ 3 _end_pmatrix_bigstar _begin_pmatrix_ 4_ 5_ 6 _end_pmatrix]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbegin%7Bpmatrix%7D%201%20%26%202%20%26%203%20%5Cend%7Bpmatrix%7D%5Cbigstar%20%5Cbegin%7Bpmatrix%7D%204%5C%5C%205%5C%5C%206%20%5Cend%7Bpmatrix%7D
[begin_pmatrix_ 6_ 5_ 4 _end_pmatrix]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbegin%7Bpmatrix%7D%206%5C%5C%205%5C%5C%204%20%5Cend%7Bpmatrix%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pnajEyMzMyMQ_size_16_color_FFFFFF_t_70]: /images/20221124/d045bae04f434977be91e5934b42ea6e.png
[Kernel_kernel_1_bigstar kernel_2]: https://private.codecogs.com/gif.latex?Kernel%3Dkernel_%7B1%7D%5Cbigstar%20kernel_%7B2%7D
[I_bigstar Kernel_I_bigstar _kernel_1_bigstar kernel_2_I_bigstar kernel_1_bigstar kernel_2]: https://private.codecogs.com/gif.latex?I%5Cbigstar%20Kernel%3DI%5Cbigstar%20%28kernel_%7B1%7D%5Cbigstar%20kernel_%7B2%7D%29%3D%28I%5Cbigstar%20kernel_%7B1%7D%29%5Cbigstar%20kernel_%7B2%7D
[I]: https://private.codecogs.com/gif.latex?I
[H_1_W_1]: https://private.codecogs.com/gif.latex?H_%7B1%7D*W_%7B1%7D
[H_2_W_2]: https://private.codecogs.com/gif.latex?H_%7B2%7D*W_%7B2%7D
[H_1_W_1_H_2_W_2]: https://private.codecogs.com/gif.latex?%28H_%7B1%7D*W_%7B1%7D%29*%28H_%7B2%7D*W_%7B2%7D%29
[O_m_2_n_2]: https://private.codecogs.com/gif.latex?O%28m%5E%7B2%7D*n%5E%7B2%7D%29
[1_W_2]: https://private.codecogs.com/gif.latex?1*W_%7B2%7D
[H_2_1]: https://private.codecogs.com/gif.latex?H_%7B2%7D*1
[O_m_2_2n]: https://private.codecogs.com/gif.latex?O%28m%5E%7B2%7D*2n%29
[Link 1]: https://blog.csdn.net/jgj123321/article/details/94448463
[frac_1_9_ _begin_bmatrix_ 1 _ 1 _ 1_ 1 _ 1_ 1_ 1 _ 1 _ 1 _end_bmatrix_frac_1_3_begin_bmatrix_ 1_ 1_ 1 _end_bmatrix_frac_1_3_begin_bmatrix_ 1 _ 1_1 _end_bmatrix]: https://private.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7B9%7D%20%5Cbegin%7Bbmatrix%7D%201%20%26%201%20%26%201%5C%5C%201%20%26%201%26%201%5C%5C%201%20%26%201%20%26%201%20%5Cend%7Bbmatrix%7D%3D%5Cfrac%7B1%7D%7B3%7D%5Cbegin%7Bbmatrix%7D%201%5C%5C%201%5C%5C%201%20%5Cend%7Bbmatrix%7D*%5Cfrac%7B1%7D%7B3%7D%5Cbegin%7Bbmatrix%7D%201%20%26%201%261%20%5Cend%7Bbmatrix%7D
[20190712143434977.png]: /images/20221124/7a108babaa0f4278bff279eb215719aa.png
[small _begin_bmatrix_ 1 _ 1_1 _end_bmatrix]: https://private.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Csmall%20%5Cbegin%7Bbmatrix%7D%201%20%26%201%261%20%5Cend%7Bbmatrix%7D
[20190712144437138.png]: /images/20221124/a3d682be8d814b5eb85c96cdcc36c25e.png
[begin_bmatrix_ 1_ 1_ 1 _end_bmatrix]: https://private.codecogs.com/gif.latex?%5Cbegin%7Bbmatrix%7D%201%5C%5C%201%5C%5C%201%20%5Cend%7Bbmatrix%7D
[20190712145323258.png]: /images/20221124/528c047317dd4811a62d56f21c3bef57.png
[20190712145855461.png]: /images/20221124/7202eae19b544bbd9620304b34cab573.png