wincnn

一个简单的Python模块，用于计算卷积神经网络中使用的最小Winograd卷积算法（Winograd convolution algorithms），该算法由文献[1]提出。

安装

pip install wincnn

依赖项

• Python >= 3.8
• SymPy >= 1.9

示例：F(2,3)

对于F(m,r)，你需要选择m+r-2个多项式插值点。

在此示例中，我们使用插值点(0,1,-1)计算F(2,3)或F(2x2,3x3)的变换矩阵：

$ python3
>>> import wincnn
>>> wincnn.showCookToomFilter((0,1,-1), 2, 3)
AT = 
⎡1  1  1   0⎤
⎢           ⎥
⎣0  1  -1  1⎦

G = 
⎡ 1    0     0 ⎤
⎢              ⎥
⎢1/2  1/2   1/2⎥
⎢              ⎥
⎢1/2  -1/2  1/2⎥
⎢              ⎥
⎣ 0    0     1 ⎦

BT = 
⎡1  0   -1  0⎤
⎢            ⎥
⎢0  1   1   0⎥
⎢            ⎥
⎢0  -1  1   0⎥
⎢            ⎥
⎣0  -1  0   1⎦

AT*((G*g)(BT*d)) =
⎡d[0]⋅g[0] + d[1]⋅g[1] + d[2]⋅g[2]⎤
⎢                                 ⎥
⎣d[1]⋅g[0] + d[2]⋅g[1] + d[3]⋅g[2]⎦

最后一个矩阵是通过AT、G和BT变换在4元素信号d[0..3]和3元素滤波器g[0..2]上计算的1D卷积F(2,3)，用于验证变换的正确性。这是一个符号计算（symbolic computation），因此结果应该是精确的。

示例：F(4,3)

以下示例计算F(4,3)的变换矩阵：

>>> wincnn.showCookToomFilter((0,1,-1,2,-2), 4, 3)
AT = 
⎡1  1  1   1  1   0⎤
⎢                  ⎥
⎢0  1  -1  2  -2  0⎥
⎢                  ⎥
⎢0  1  1   4  4   0⎥
⎢                  ⎥
⎣0  1  -1  8  -8  1⎦

G = 
⎡1/4     0     0  ⎤
⎢                 ⎥
⎢-1/6  -1/6   -1/6⎥
⎢                 ⎥
⎢-1/6   1/6   -1/6⎥
⎢                 ⎥
⎢1/24  1/12   1/6 ⎥
⎢                 ⎥
⎢1/24  -1/12  1/6 ⎥
⎢                 ⎥
⎣ 0      0     1  ⎦

BT = 
⎡4  0   -5  0   1  0⎤
⎢                   ⎥
⎢0  -4  -4  1   1  0⎥
⎢                   ⎥
⎢0  4   -4  -1  1  0⎥
⎢                   ⎥
⎢0  -2  -1  2   1  0⎥
⎢                   ⎥
⎢0  2   -1  -2  1  0⎥
⎢                   ⎥
⎣0  4   0   -5  0  1⎦

AT*((G*g)(BT*d)) =
⎡d[0]⋅g[0] + d[1]⋅g[1] + d[2]⋅g[2]⎤
⎢                                 ⎥
⎢d[1]⋅g[0] + d[2]⋅g[1] + d[3]⋅g[2]⎥
⎢                                 ⎥
⎢d[2]⋅g[0] + d[3]⋅g[1] + d[4]⋅g[2]⎥
⎢                                 ⎥
⎣d[3]⋅g[0] + d[4]⋅g[1] + d[5]⋅g[2]⎦

线性卷积

如果你需要线性卷积算法而不是FIR滤波器，只需交换并转置数据和逆变换矩阵。这被称为变换原理（Transformation Principle）。

>>> wincnn.showCookToomConvolution((0,1,-1),2,3)
A = 
⎡1  0 ⎤
⎢     ⎥
⎢1  1 ⎥
⎢     ⎥
⎢1  -1⎥
⎢     ⎥
⎣0  1 ⎦

G = 
⎡ 1    0     0 ⎤
⎢              ⎥
⎢1/2  1/2   1/2⎥
⎢              ⎥
⎢1/2  -1/2  1/2⎥
⎢              ⎥
⎣ 0    0     1 ⎦

B = 
⎡1   0  0   0 ⎤
⎢             ⎥
⎢0   1  -1  -1⎥
⎢             ⎥
⎢-1  1  1   0 ⎥
⎢             ⎥
⎣0   0  0   1 ⎦

线性卷积: B*((G*g)(A*d)) =
⎡      d[0]⋅g[0]      ⎤
⎢                     ⎥
⎢d[0]⋅g[1] + d[1]⋅g[0]⎥
⎢                     ⎥
⎢d[0]⋅g[2] + d[1]⋅g[1]⎥
⎢                     ⎥
⎣      d[1]⋅g[2]      ⎦

示例：F(6,3)

此示例计算F(6,3)的变换矩阵。我们将使用分数插值点1/2和-1/2，因此使用sympy.Rational来保持符号计算的精确性（使用浮点数值会导致变换推导受到舍入误差影响）。

>>> from sympy import Rational
>>> wincnn.showCookToomFilter((0,1,-1,2,-2,Rational(1,2),-Rational(1,2)), 6, 3)
AT = 
⎡1  1  1   1    1    1      1    0⎤
⎢                                 ⎥
⎢0  1  -1  2   -2   1/2   -1/2   0⎥
⎢                                 ⎥
⎢0  1  1   4    4   1/4    1/4   0⎥
⎢                                 ⎥
⎢0  1  -1  8   -8   1/8   -1/8   0⎥
⎢                                 ⎥
⎢0  1  1   16  16   1/16  1/16   0⎥
⎢                                 ⎥
⎣0  1  -1  32  -32  1/32  -1/32  1⎦

G = 
⎡ 1      0     0  ⎤
⎢                 ⎥
⎢-2/9  -2/9   -2/9⎥
⎢                 ⎥
⎢-2/9   2/9   -2/9⎥
⎢                 ⎥
⎢1/90  1/45   2/45⎥
⎢                 ⎥
⎢1/90  -1/45  2/45⎥
⎢                 ⎥
⎢ 32    16        ⎥
⎢ ──    ──    8/45⎥
⎢ 45    45        ⎥
⎢                 ⎥
⎢ 32   -16        ⎥
⎢ ──   ────   8/45⎥
⎢ 45    45        ⎥
⎢                 ⎥
⎣ 0      0     1  ⎦

BT = 
⎡1   0    -21/4    0    21/4     0    -1  0⎤
⎢                                          ⎥
⎢0   1      1    -17/4  -17/4    1    1   0⎥
⎢                                          ⎥
⎢0   -1     1    17/4   -17/4   -1    1   0⎥
⎢                                          ⎥
⎢0  1/2    1/4   -5/2   -5/4     2    1   0⎥
⎢                                          ⎥
⎢0  -1/2   1/4    5/2   -5/4    -2    1   0⎥
⎢                                          ⎥
⎢0   2      4    -5/2    -5     1/2   1   0⎥
⎢                                          ⎥
⎢0   -2     4     5/2    -5    -1/2   1   0⎥
⎢                                          ⎥
⎣0   -1     0    21/4     0    -21/4  0   1⎦

AT*((G*g)(BT*d)) =
⎡d[0]⋅g[0] + d[1]⋅g[1] + d[2]⋅g[2]⎤
⎢                                 ⎥
⎢d[1]⋅g[0] + d[2]⋅g[1] + d[3]⋅g[2]⎥
⎢                                 ⎥
⎢d[2]⋅g[0] + d[3]⋅g[1] + d[4]⋅g[2]⎥
⎢                                 ⎥
⎢d[3]⋅g[0] + d[4]⋅g[1] + d[5]⋅g[2]⎥
⎢                                 ⎥
⎢d[4]⋅g[0] + d[5]⋅g[1] + d[6]⋅g[2]⎥
⎢                                 ⎥
⎣d[5]⋅g[0] + d[6]⋅g[1] + d[7]⋅g[2]⎦

引用wincnn

如果你在研究中使用wincnn，请引用该软件：

@software{lavin_wincnn,
  author       = {Lavin, Andrew},
  title        = {wincnn},
  year         = {2016},
  version      = {2.0.1},
  url          = {https://github.com/andravin/wincnn},
  license      = {Apache-2.0}
}

参考文献

[1] "Fast Algorithms for Convolutional Neural Networks" Lavin and Gray, CVPR 2016. http://www.cv-foundation.org/openaccess/content_cvpr_2016/papers/Lavin_Fast_Algorithms_for_CVPR_2016_paper.pdf

wincnn 快速上手指南

环境准备

• 系统要求：支持 Python 3.8+ 的操作系统（Windows/Linux/macOS）
• 前置依赖：
  • Python 3.8+
  • SymPy 1.9+（建议使用国内镜像源加速安装）

安装步骤

1. 使用 pip 安装（推荐国内镜像源）：

   pip install wincnn -i https://pypi.tuna.tsinghua.edu.cn/simple
   

基本使用

最简示例：计算 F(2,3) Winograd 卷积变换

import wincnn

# 计算 F(2,3) 的变换矩阵（插值点 (0,1,-1)）
wincnn.showCookToomFilter((0,1,-1), 2, 3)

输出结果说明：

• AT：输入特征变换矩阵
• G：滤波器变换矩阵
• BT：输出特征变换矩阵
• 最后一行显示卷积结果验证（符号计算确保精确性）

扩展示例：线性卷积（交换数据与逆变换矩阵）

wincnn.showCookToomConvolution((0,1,-1), 2, 3)

关键特性：

• 支持分数插值点（如 Rational(1,2)）避免浮点误差
• 符号计算保证数学精度（依赖 SymPy）