目录
- 概述
- 推导
- 知识沙漠中的一点扩展
如有纰漏错误，恳请指正:D
0. 概述
行列可分离卷积(separable convolution)主要应用于图像处理算法中，用于将一遍2D离散卷积(也称滤波，下文交替使用)操作分离成2遍1D卷积操作。如果图像像素数为 m m m，卷积核(也称卷积模板、模板)大小为 k ∗ k k*k k∗k，则行列分离卷积可以将时间复杂度由 m ∗ k 2 m*k^2 m∗k2次乘法，简化到 m ∗ 2 k m*2k m∗2k次乘法。
行列可分离技术应用的前提是卷积核是可分离的。
1. 推导
a. 卷积的定义
假设现在要对图像
A
m
∗
n
A_{m*n}
Am∗n(像素矩阵)应用模板核
D
k
∗
k
D_{k*k}
Dk∗k进行卷积操作，并且
D
D
D满足行列可分离性质。
即
R
i
,
j
=
∑
a
=
i
−
⌊
k
/
2
⌋
i
+
⌊
k
/
2
⌋
∑
b
=
i
−
⌊
k
/
2
⌋
i
+
⌊
k
/
2
⌋
A
a
,
b
∗
D
a
−
i
+
⌊
k
/
2
⌋
,
b
−
j
+
⌊
k
/
2
⌋
(1)
R_{i,j} = \sum_{a = i - \lfloor k/2\rfloor} ^ {i + \lfloor k/2 \rfloor} \sum_{b = i - \lfloor k/2\rfloor} ^ {i + \lfloor k/2 \rfloor} A_{a,b} * D_{a - i + \lfloor k/2\rfloor, b - j + \lfloor k/2\rfloor} \tag{1}
Ri,j=a=i−⌊k/2⌋∑i+⌊k/2⌋b=i−⌊k/2⌋∑i+⌊k/2⌋Aa,b∗Da−i+⌊k/2⌋,b−j+⌊k/2⌋(1)
其中， R R R为卷积后的结果图像矩阵，下表 X i , j X_{i,j} Xi,j表示 X X X矩阵的第i行第j列个元素。 ⌊ a ⌋ \lfloor a \rfloor ⌊a⌋表示对 a a a下取整。
上式表示目标图像矩阵的第 i , j i, j i,j个像素，是由原像素矩阵 A i , j A_{i,j} Ai,j周围大小为 k k k的方阵与卷积核 D D D内积而得。(更直观的解释请百度卷积/离散卷积)
b. 卷积核可分离的前提
而由于模板核 D D D满足行列可分离性质，有
D i , j = E i ∗ F j (2) D_{i,j} = E_i * F_j \tag{2} Di,j=Ei∗Fj(2)
其中， E E E为 k ∗ 1 k*1 k∗1的列向量， F F F为 1 ∗ k 1*k 1∗k的行向量，也就是说， k ∗ k k*k k∗k的模板核 D D D可以用两个1D的向量矩阵相乘表示。
c. 推导
将 ( 2 ) (2) (2)式代入 ( 1 ) (1) (1)式中可得，
R i , j = ∑ a ∑ b A a , b ∗ E a ∗ F b (3) R_{i,j} = \sum_a \sum_b A_{a,b} * E_a * F_b \tag{3} Ri,j=a∑b∑Aa,b∗Ea∗Fb(3)
为了简化表示，其中
E
,
F
E,F
E,F矩阵下标直接用
a
,
b
a,b
a,b代替。其值应为
a
−
i
+
⌊
k
/
2
⌋
,
b
−
j
+
⌊
k
/
2
⌋
a - i + \lfloor k/2\rfloor,b - j + \lfloor k/2\rfloor
a−i+⌊k/2⌋,b−j+⌊k/2⌋，对应范围
[
0
,
k
]
[0,k]
[0,k]。
上式内层求和号是对
b
b
b进行求和，
E
a
E_a
Ea项可看作常数提到
∑
b
\sum_b
∑b外面来，可得，
R i , j = ∑ a E a ∑ b A a , b ∗ F b (4) R_{i,j} = \sum_a E_a \sum_b A_{a,b} * F_b \tag{4} Ri,j=a∑Eab∑Aa,b∗Fb(4)
仔细看 ∑ b A a , b ∗ F b \sum_b A_{a,b} * F_b ∑bAa,b∗Fb这一项，由于 F b F_b Fb是一个一维行向量，所以这一项也可以写成 ∑ a = 1 1 ∑ b A a , b ∗ F a , b \sum_{a=1}^{1}\sum_b A_{a,b} * F_{a,b} ∑a=11∑bAa,b∗Fa,b。是的，这就是文章开头所提出的二维卷积的定义式，同理，我们可以将式 ( 4 ) (4) (4)变成如下形式，
T i , j = ∑ a = i i ∑ b A a , b ∗ F a , b (4.1) T_{i,j} = \sum_{a=i}^{i}\sum_b A_{a,b} * F_{a,b} \tag{4.1} Ti,j=a=i∑ib∑Aa,b∗Fa,b(4.1)
R i , j = ∑ b = j j ∑ a E a , b ∗ T a , b (4.2) R_{i,j} = \sum_{b=j}^j\sum_a E_{a,b} * T_{a,b} \tag{4.2} Ri,j=b=j∑ja∑Ea,b∗Ta,b(4.2)
其中， T i , j T_{i,j} Ti,j为使用行列分离之后的行向量卷积图像得到的中间结果。
至此，行列可分离卷积证明结束。
2. 拓展
在各种涉及到性能优化的卷积操作中，无论是人工智能(不太熟悉，只是看到过几篇文章提到了这个方法)，还是图像处理、实时渲染领域，都在寻求方法将卷积模板可分离化，来加速算法的执行。
或许在之后的优化工作中，考虑卷积的可分离性不失为一种方向。
在浅薄的知识里，Separable-Subsurface-Scattering [ 1 ] ^{[1]} [1]文中将一种图像后处理的模板近似成行列可分离的卷积核，并通过可分离的性质加速了对画面进行实时后处理滤波的速度，达到了很好的速度结果。
同时SVD分解 [ 2 ] ^{[2]} [2]提供了一种将矩阵低秩近似为行列可分离矩阵的方法，通过这种方法，既可以获得给定阶数下对目标矩阵能量损失最小，同时还能分离成目标行列数的方法。(在 Frobenius范数定义下的能量损失最小，实际上是 m i n ( ∑ i ∑ j A i , j ∗ B i , j ) min(\sum_i \sum_j A_{i,j} * B_{i,j}) min(∑i∑jAi,j∗Bi,j)，就是矩阵对应元素乘积，当两个矩阵相减，并且对应元素乘积最小就叫Frobenius范数定义下的能量损失最小)
参考文献
-
Separable Subsurface Scattering
-
THE APPROXIMATION OF ONE MATRIX BY
ANOTHER OF LOWER RANK文章来源：https://www.toymoban.com/news/detail-436715.html
如有纰漏错误，恳请指正:D * 2文章来源地址https://www.toymoban.com/news/detail-436715.html
到了这里，关于行列可分离卷积 separable convolution的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
