数学小记之卷积

电玩女神 2022-04-12 04:36 277阅读 0赞

> 本文简述了1维卷积和2维卷积的实现

#### 一维卷积 ####

描述卷积的方式很多,譬如这个:

*  一个函数在另一个函数上的**加权叠加**

虽然各个解释都有助于我们对卷积的理解,但是个人感觉还是直接通过公式来了解卷积更为直观(简单起见,这里我们仅讨论卷积的离散定义):

f ( x ) ∗ g ( x ) = ∑ n = − ∞ ∞ f ( n ) g ( x − n ) f(x)\*g(x) = \\sum\_\{n=-\\infty\}^\{\\infty\}f(n)g(x - n) f(x)∗g(x)=n=−∞∑∞f(n)g(x−n)

注意一下这个公式,其所表达的意思是: ***f* 和 *g* 这两个函数在 *x* 处的卷积值,而这个在 *x* 处的卷积值是通过取遍自变量 *n* 的"所有值(从负无穷到正无穷)"而计算出来的**

当然,对于实际给出的 ***f* 函数(序列) 和 *g* 函数(序列)** 都不会是无穷的,所以计算过程中自变量 ***n*** 的取值自然也不会是无穷的,举个简单的例子,假设我们有以下的函数(序列):

f ( 0 ) = 1 , f ( 1 ) = 2 , f ( 2 ) = 3 g ( 0 ) = 4 , g ( 1 ) = 5 , g ( 2 ) = 6 f(0) = 1, f(1) = 2, f(2) = 3\\\\ g(0) = 4, g(1) = 5, g(2) = 6 f(0)=1,f(1)=2,f(2)=3g(0)=4,g(1)=5,g(2)=6

并设 ***f*** 和 ***g*** 的卷积结果为 ***h***, 那么 ***h(1)*** 等于多少呢?

f ( 1 ) ∗ g ( 1 ) = h ( 1 ) = ? f(1)\*g(1) = h(1) = ? f(1)∗g(1)=h(1)=?

我们来套用一下之前的公式:

f ( 1 ) ∗ g ( 1 ) = h ( 1 ) = ∑ n = − ∞ ∞ f ( n ) g ( 1 − n ) f(1)\*g(1) = h(1) = \\sum\_\{n=-\\infty\}^\{\\infty\}f(n)g(1 - n) f(1)∗g(1)=h(1)=n=−∞∑∞f(n)g(1−n)

考虑到 ***n*** 和 ***1 - n*** 的合法范围(***n*** 需为 ***f*** 的合法索引,***1 - n*** 需为 ***g*** 的合法索引),我们有:

0 = m i n \_ i n d e x ( f ) < = n < = m a x \_ i n d e x ( f ) = 2 0 = m i n \_ i n d e x ( g ) < = 1 − n < = m a x \_ i n d e x ( g ) = 2 &ThickSpace; ⟹ &ThickSpace; 0 < = n < = 1 0 = min\\\_index(f) <= n <= max\\\_index(f) = 2\\\\0 = min\\\_index(g) <= 1 - n <= max\\\_index(g) = 2\\\\\\implies0 <= n <= 1 0=min\_index(f)<=n<=max\_index(f)=20=min\_index(g)<=1−n<=max\_index(g)=2⟹0<=n<=1

所以对于 ***h(1)*** 来说 **自变量 *n*** 有两个合法取值: **0** 和 **1**, 于是我们有:

f ( 1 ) ∗ g ( 1 ) = h ( 1 ) = f ( 0 ) g ( 1 − 0 ) + f ( 1 ) g ( 1 − 1 ) = f ( 0 ) g ( 1 ) + f ( 1 ) g ( 0 ) = 1 ∗ 5 + 2 ∗ 4 = 13 f(1)\*g(1) = h(1) = f(0)g(1 - 0) + f(1)g(1 - 1) = f(0)g(1) + f(1)g(0) = 1 \* 5 + 2 \* 4 = 13 f(1)∗g(1)=h(1)=f(0)g(1−0)\+f(1)g(1−1)=f(0)g(1)\+f(1)g(0)=1∗5\+2∗4=13

其余的卷积数值也可以依样进行计算,有兴趣的朋友可以自行试下~

下面是使用 Lua 实现的一维卷积示例:

local function dimension(f)
        if type(f) == "table" then
            local dim = #f
            if dim > 0 then
                return dim, dimension(f[1])
            else
                return 0
            end
        end
    end
    
    local function value(f, ...)
        if f then
            local dim_index = { ... }
            for i = 1, #dim_index do
                local index = dim_index[i]
                f = f[index]
                if not f then
                    return 0
                end
            end
        end
        
        return f
    end
    
    -- 1d convolution, sample f(array with 3 elements) and g(array with 3 elements), h is convolution result(array index is from 0)
    -- h(0) = f(0) * g(0)
    -- h(1) = f(0) * g(1) + f(1) * g(0)
    -- h(2) = f(0) * g(2) + f(1) * g(1) + f(2) * g(0)
    -- h(3) = f(1) * g(2) + f(2) * g(1)
    -- h(4) = f(2) * g(2)
    
    function convolution_1d(f, g)
        local row_1 = dimension(f)
        local row_2 = dimension(g)
        if row_1 > 0 and row_2 > 0 then
            local h = {}
            
            local n = row_1 + row_2 - 2
            for i = 0, n do
                local sum = 0
                for j = 0, i do
                    sum = sum + value(f, j + 1) * value(g, i - j + 1)
                end
                table.insert(h, sum)
            end
            
            return h
        end
    end

示例中的 dimension函数 和 value函数 对于不熟悉 Lua 的朋友可能会造成些阅读障碍(对于示例来说确实有些过度技巧化了),在此我们可以简单理解:

*  dimension(f) 获取 f 的数组个数(支持多维数组)
 *  value(f, …) 获取 f 在 …(不定参数) 所给定的索引处的数值,数值不存在则返回 0 (支持多维数组)

#### 二维卷积 ####

二维卷积可以使用一维卷积来进行类比,在此仅给出(离散定义)公式和相关示例实现(使用 Lua):

f ( x , y ) ∗ g ( x , y ) = ∑ m = − ∞ ∞ ∑ n = − ∞ ∞ f ( m , n ) g ( x − m , y − n ) f(x, y)\*g(x, y) = \\sum\_\{m=-\\infty\}^\{\\infty\}\\sum\_\{n=-\\infty\}^\{\\infty\}f(m, n)g(x - m, y - n) f(x,y)∗g(x,y)=m=−∞∑∞n=−∞∑∞f(m,n)g(x−m,y−n)

示例代码如下,其中的 dimension函数 和 value函数 即来自于之前的示例代码,在此不再重复列出:

-- 2d convolution, sample f(matrix 3 * 3) and g(matrix 2 * 2), h is convolution result(matrix index is from (0, 0))
    -- h(0, 0) = f(0, 0) * g(0, 0)
    -- h(0, 1) = f(0, 0) * g(0, 1) + f(0, 1) * g(0, 0)
    -- h(0, 2) = f(0, 1) * g(0, 1) + f(0, 2) * g(0, 0)
    -- h(0, 3) = f(0, 2) * g(0, 1)
    -- h(1, 0) = f(0, 0) * g(1, 0) + f(1, 0) * g(0, 0)
    -- h(1, 1) = f(0, 0) * g(1, 1) + f(0, 1) * g(1, 0) + f(1, 0) * g(0, 1) + f(1, 1) * g(0, 0)
    -- h(1, 2) = f(0, 1) * g(1, 1) + f(0, 2) * g(1, 0) + f(1, 1) * g(0, 1) + f(1, 2) * g(0, 0)
    -- h(1, 3) = f(0, 2) * g(1, 1) + f(1, 2) * g(0, 1)
    -- h(2, 0) = f(1, 0) * g(1, 0) + f(2, 0) * g(0, 0)
    -- h(2, 1) = f(1, 0) * g(1, 1) + f(1, 1) * g(1, 0) + f(2, 0) * g(0, 1) + f(2, 1) * g(0, 0)
    -- h(2, 2) = f(1, 1) * g(1, 1) + f(1, 2) * g(1, 0) + f(2, 1) * g(0, 1) + f(2, 2) * g(0, 0)
    -- h(2, 3) = f(1, 2) * g(1, 1) + f(2, 2) * g(0, 1)
    -- h(3, 0) = f(2, 0) * g(1, 0)
    -- h(3, 1) = f(2, 0) * g(1, 1) + f(2, 1) * g(1, 0)
    -- h(3, 2) = f(2, 1) * g(1, 1) + f(2, 2) * g(1, 0)
    -- h(3, 3) = f(2, 2) * g(1, 1)
    
    function convolution_2d(f, g)
        local row_1, col_1 = dimension(f)
        local row_2, col_2 = dimension(g)
        if row_1 > 0 and col_1 > 0 and row_2 > 0 and col_2 > 0 then
            local h = {}
            
            local m = row_1 + row_2 - 2
            local n = col_1 + col_2 - 2
            for i = 0, m do
                for j = 0, n do
                    local sum = 0
                    for k1 = 0, i do
                        for k2 = 0, j do
                            sum = sum + value(f, k1 + 1, k2 + 1) * value(g, i - k1 + 1, j - k2 + 1)
                        end
                    end
                    h[i + 1] = h[i + 1] or {}
                    h[i + 1][j + 1] = sum
                end
            end
            
            return h
        end
    end

#### 参考 ####

1.  如何通俗地理解卷积?(很好的介绍文章,推荐首先阅读)
2.  [我对卷积的理解][Link 1]
3.  [最容易理解的对卷积(convolution)的解释][convolution]

[Link 1]: https://mengqi92.github.io/2015/10/06/convolution/
[convolution]: https://blog.csdn.net/bitcarmanlee/article/details/54729807