chenpaopao – 第 69 页

leetcodeday20 —有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

思路：使用栈，先入栈，每当进入一个元素，判断是否和上一个匹配，如果匹配，他们两个出栈，如果括号方法相反，直接返回false，如果括号方向相同，继续下一元素入栈，知道全部都入栈，如果栈不空，返回false


# @lc code=start
class Solution:
    def isValid(self, s: str) -> bool:
        lens=len(s)
        sets={"(":")","{":"}","[":"]"}
        left=["(","[","{"]
        lists=list()
        lists.append(s[0])
        j=1
        while  j<=lens-1:
            if lists==[]:
                lists.append(s[j])
                j=j+1
                continue
            elif lists[-1] not in left:
                print(lists)
                return False
            elif sets[lists[-1]]==s[j]:
                j=j+1
                lists.pop()
               
            else:
                lists.append(s[j])
                j=j+1
        print(lists)
        return True if lists==[] else False

MAE:Masked Autoencoders Are Scalable Vision Learners

摘自 Jack Cui

马赛克，克星，真来了！

何恺明大神的新作论文：https://arxiv.org/abs/2111.06377

项目地址：https://github.com/facebookresearch/mae

简单讲：将图片随机遮挡，然后复原。并且遮挡的比例，非常大！超过整张图的 80% ，我们直接看效果：

第一列是遮挡图，第二列是修复结果，第三列是原图。图片太多，可能看不清，我们单看一个：

看这个遮挡的程度，表针、表盘几乎都看不见了。但是 MAE 依然能够修复出来：

这个效果真的很惊艳！甚至对于遮挡 95% 的面积的图片依然 work。

看左图，你能看出来被遮挡的是蘑菇吗？？MAE 却能轻松修复出来。接下来，跟大家聊聊 MAE。

Vit

讲解 MAE 之前不得不先说下 Vit。红遍大江南北的 Vision Transformer，ViT。领域内的小伙伴，或多或少都应该听说过。它将 Transformer 应用到了 CV 上面，将整个图分为 16 * 16 的小方块，每个方块做成一个词，然后放进 Transformer 进行训练。视觉transformer 和自然语言处理中的transformer可以进行类比，可以把一个图像块理解成一个单词。

MAE

MAE 结构设计的非常简单：

将一张图随机打 Mask，未 Mask 部分输入给 Encoder 进行编码学习，这个 Encoder 就是 Vit，然后得到每个块的特征。再将未 Mask 部分以及 Mask 部分全部输入给 Decoder 进行解码学习，最终目标是修复图片。而 Decoder 就是一个轻量化的 Transformer。它的损失函数就是普通的 MSE。所以说， MAE 的 Encoder 和 Decoder 结构不同，是非对称式的。Encoder 将输入编码为 latent representation，而 Decoder 将从 latent representation 重建原始信号。

项目提供了 Colab，如果你能登陆，那么可以直接体验：https://colab.research.google.com/github/facebookresearch/mae/blob/main/demo/mae_visualize.ipynb

如果不能登陆，可以直接本地部署，作者提供了预训练模型。

MAE 可以用来生成不存在的内容，就像 GAN 一样。

首先来看看神魔是 Transformer ：

Transformer 最初主要应用于一些自然语言处理场景，比如翻译、文本分类、写小说、写歌等。随着技术的发展，Transformer 开始征战视觉领域，分类、检测等任务均不在话下，逐渐走上了多模态的道路。

Transformer 是 Google 在 2017 年提出的用于机器翻译的模型。

Transformer 的内部，在本质上是一个 Encoder-Decoder 的结构，即编码器-解码器。

Transformer 中抛弃了传统的 CNN 和 RNN，整个网络结构完全由 Attention 机制组成，并且采用了 6 层 Encoder-Decoder 结构。

显然，Transformer 主要分为两大部分，分别是编码器和解码器。整个 Transformer 是由 6 个这样的结构组成，为了方便理解，我们只看其中一个Encoder-Decoder 结构。

以一个简单的例子进行说明：

Why do we work?，我们为什么工作？左侧红框是编码器，右侧红框是解码器，编码器负责把自然语言序列映射成为隐藏层（上图第2步），即含有自然语言序列的数学表达。解码器把隐藏层再映射为自然语言序列，从而使我们可以解决各种问题，如情感分析、机器翻译、摘要生成、语义关系抽取等。简单说下，上图每一步都做了什么：

输入自然语言序列到编码器: Why do we work?(为什么要工作)；
编码器输出的隐藏层，再输入到解码器；
输入 <𝑠𝑡𝑎𝑟𝑡> (起始)符号到解码器；
解码器得到第一个字”为”；
将得到的第一个字”为”落下来再输入到解码器；
解码器得到第二个字”什”；
将得到的第二字再落下来，直到解码器输出 <𝑒𝑛𝑑> (终止符)，即序列生成完成。

解码器和编码器的结构类似，本文以编码器部分进行讲解。即把自然语言序列映射为隐藏层的数学表达的过程，因为理解了编码器中的结构，理解解码器就非常简单了。为了方便学习，我将编码器分为 4 个部分，依次讲解。

1、位置嵌入（𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛𝑎𝑙 𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔）

我们输入数据 X 维度为[batch size, sequence length]的数据，比如我们为什么工作。batch size 就是 batch 的大小，这里只有一句话，所以 batch size 为 1，sequence length 是句子的长度，一共 7 个字，所以输入的数据维度是 [1, 7]。我们不能直接将这句话输入到编码器中，因为 Tranformer 不认识，我们需要先进行字嵌入，即得到图中的。简单点说，就是文字->字向量的转换，这种转换是将文字转换为计算机认识的数学表示，用到的方法就是 Word2Vec，Word2Vec 的具体细节，对于初学者暂且不用了解，这个是可以直接使用的。得到维度是 [batch size, sequence length, embedding dimension]，embedding dimension 的大小由 Word2Vec 算法决定，Tranformer 采用 512 长度的字向量。所以的维度是 [1, 7, 512]。至此，输入的我们为什么工作，可以用一个矩阵来简化表示。

我们知道，文字的先后顺序，很重要。比如吃饭没、没吃饭、没饭吃、饭吃没、饭没吃，同样三个字，顺序颠倒，所表达的含义就不同了。文字的位置信息很重要，Tranformer 没有类似 RNN 的循环结构，没有捕捉顺序序列的能力。为了保留这种位置信息交给 Tranformer 学习，我们需要用到位置嵌入。加入位置信息的方式非常多，最简单的可以是直接将绝对坐标 0,1,2 编码。Tranformer 采用的是 sin-cos 规则，使用了 sin 和 cos 函数的线性变换来提供给模型位置信息：

上式中 pos 指的是句中字的位置，取值范围是 [0, 𝑚𝑎𝑥 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝑙𝑒𝑛𝑔𝑡ℎ)，i 指的是字嵌入的维度, 取值范围是 [0, 𝑒𝑚𝑏𝑒𝑑𝑑𝑖𝑛𝑔 𝑑𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛)。就是 𝑒𝑚𝑏𝑒𝑑𝑑𝑖𝑛𝑔 𝑑𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛 的大小。上面有 sin 和 cos 一组公式，也就是对应着 𝑒𝑚𝑏𝑒𝑑𝑑𝑖𝑛𝑔 𝑑𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛 维度的一组奇数和偶数的序号的维度，从而产生不同的周期性变化。

# 导入依赖库
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import math

def get_positional_encoding(max_seq_len, embed_dim):
    # 初始化一个positional encoding
    # embed_dim: 字嵌入的维度
    # max_seq_len: 最大的序列长度
    positional_encoding = np.array([
        [pos / np.power(10000, 2 * i / embed_dim) for i in range(embed_dim)]
        if pos != 0 else np.zeros(embed_dim) for pos in range(max_seq_len)])
    positional_encoding[1:, 0::2] = np.sin(positional_encoding[1:, 0::2])  # dim 2i 偶数
    positional_encoding[1:, 1::2] = np.cos(positional_encoding[1:, 1::2])  # dim 2i+1 奇数
    # 归一化, 用位置嵌入的每一行除以它的模长
    # denominator = np.sqrt(np.sum(position_enc**2, axis=1, keepdims=True))
    # position_enc = position_enc / (denominator + 1e-8)
    return positional_encoding
    
positional_encoding = get_positional_encoding(max_seq_len=100, embed_dim=16)
plt.figure(figsize=(10,10))
sns.heatmap(positional_encoding)
plt.title("Sinusoidal Function")
plt.xlabel("hidden dimension")
plt.ylabel("sequence length")

可以看到，位置嵌入在 𝑒𝑚𝑏𝑒𝑑𝑑𝑖𝑛𝑔 𝑑𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛 （也是hidden dimension ）维度上随着维度序号增大，周期变化会越来越慢，而产生一种包含位置信息的纹理。

就这样，产生独一的纹理位置信息，模型从而学到位置之间的依赖关系和自然语言的时序特性。

最后，将Xembedding 和 位置嵌入 相加，送给下一层。

2、自注意力层（𝑠𝑒𝑙𝑓 𝑎𝑡𝑡𝑒𝑛𝑡𝑖𝑜𝑛 𝑚𝑒𝑐ℎ𝑎𝑛𝑖𝑠𝑚）

直接看下图笔记，讲解的非常详细。

多头的意义在于，$QK^{T}$ 得到的矩阵就叫注意力矩阵，它可以表示每个字与其他字的相似程度。因为，向量的点积值越大，说明两个向量越接近。

我们的目的是，让每个字都含有当前这个句子中的所有字的信息，用注意力层，我们做到了。

需要注意的是，在上面 𝑠𝑒𝑙𝑓 𝑎𝑡𝑡𝑒𝑛𝑡𝑖𝑜𝑛 的计算过程中，我们通常使用 𝑚𝑖𝑛𝑖 𝑏𝑎𝑡𝑐ℎ，也就是一次计算多句话，上文举例只用了一个句子。

每个句子的长度是不一样的，需要按照最长的句子的长度统一处理。对于短的句子，进行 Padding 操作，一般我们用 0 来进行填充。

3、残差链接和层归一化

加入了残差设计和层归一化操作，目的是为了防止梯度消失，加快收敛。

1) 残差设计

我们在上一步得到了经过注意力矩阵加权之后的 𝑉，也就是 𝐴𝑡𝑡𝑒𝑛𝑡𝑖𝑜𝑛(𝑄, 𝐾, 𝑉)，我们对它进行一下转置，使其和 𝑋𝑒𝑚𝑏𝑒𝑑𝑑𝑖𝑛𝑔 的维度一致, 也就是 [𝑏𝑎𝑡𝑐ℎ 𝑠𝑖𝑧𝑒, 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝑙𝑒𝑛𝑔𝑡ℎ, 𝑒𝑚𝑏𝑒𝑑𝑑𝑖𝑛𝑔 𝑑𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛] ，然后把他们加起来做残差连接，直接进行元素相加，因为他们的维度一致:

$$
X_{\text {embedding }}+\text { Attention }(Q, K, V)
$$

在之后的运算里，每经过一个模块的运算，都要把运算之前的值和运算之后的值相加，从而得到残差连接，训练的时候可以使梯度直接走捷径反传到最初始层：

$$
X+\text { SubLayer }(X)
$$

2) 层归一化

作用是把神经网络中隐藏层归一为标准正态分布，也就是 𝑖.𝑖.𝑑 独立同分布，以起到加快训练速度，加速收敛的作用。

$$
\mu_{i}=\frac{1}{m} \sum_{i=1}^{m} x_{i j}
$$

上式中以矩阵的行 (𝑟𝑜𝑤) 为单位求均值：

$$
\sigma_{j}^{2}=\frac{1}{m} \sum_{i=1}^{m}\left(x_{i j}-\mu_{j}\right)^{2}
$$

上式中以矩阵的行 (𝑟𝑜𝑤) 为单位求方差：

$$
\operatorname{LayerNorm}(x)=\alpha \odot \frac{x_{i j}-\mu_{i}}{\sqrt{\sigma_{i}^{2}+\epsilon}}+\beta
$$

然后用每一行的每一个元素减去这行的均值，再除以这行的标准差，从而得到归一化后的数值， $\epsilon$ 是为了防止除 0 ；之后引入两个可训练参数 $\alpha, \beta$ 来弥补归一化的过程中损失掉的信息，注意 $\odot$ 表示元素相乘而不是点积，我们一般初始化 $\alpha$ 为全 1 ，而$\beta$ 为全 0 。

代码层面非常简单，单头 attention 操作如下：

class ScaledDotProductAttention(nn.Module):
    ''' Scaled Dot-Product Attention '''

    def __init__(self, temperature, attn_dropout=0.1):
        super().__init__()
        self.temperature = temperature
        self.dropout = nn.Dropout(attn_dropout)

    def forward(self, q, k, v, mask=None):
        # self.temperature是论文中的d_k ** 0.5，防止梯度过大
        # QxK/sqrt(dk)
        attn = torch.matmul(q / self.temperature, k.transpose(2, 3))

        if mask is not None:
            # 屏蔽不想要的输出
            attn = attn.masked_fill(mask == 0, -1e9)
        # softmax+dropout
        attn = self.dropout(F.softmax(attn, dim=-1))
        # 概率分布xV
        output = torch.matmul(attn, v)

        return output, attn

Multi-Head Attention 实现在 ScaledDotProductAttention 基础上构建：

class MultiHeadAttention(nn.Module):
    ''' Multi-Head Attention module '''

    # n_head头的个数，默认是8
    # d_model编码向量长度，例如本文说的512
    # d_k, d_v的值一般会设置为 n_head * d_k=d_model，
    # 此时concat后正好和原始输入一样，当然不相同也可以，因为后面有fc层
    # 相当于将可学习矩阵分成独立的n_head份
    def __init__(self, n_head, d_model, d_k, d_v, dropout=0.1):
        super().__init__()
        # 假设n_head=8，d_k=64
        self.n_head = n_head
        self.d_k = d_k
        self.d_v = d_v
        # d_model输入向量，n_head * d_k输出向量
        # 可学习W^Q，W^K,W^V矩阵参数初始化
        self.w_qs = nn.Linear(d_model, n_head * d_k, bias=False)
        self.w_ks = nn.Linear(d_model, n_head * d_k, bias=False)
        self.w_vs = nn.Linear(d_model, n_head * d_v, bias=False)
        # 最后的输出维度变换操作
        self.fc = nn.Linear(n_head * d_v, d_model, bias=False)
        # 单头自注意力
        self.attention = ScaledDotProductAttention(temperature=d_k ** 0.5)
        self.dropout = nn.Dropout(dropout)
        # 层归一化
        self.layer_norm = nn.LayerNorm(d_model, eps=1e-6)

    def forward(self, q, k, v, mask=None):
        # 假设qkv输入是(b,100,512),100是训练每个样本最大单词个数
        # 一般qkv相等，即自注意力
        residual = q
        # 将输入x和可学习矩阵相乘，得到(b,100,512)输出
        # 其中512的含义其实是8x64，8个head，每个head的可学习矩阵为64维度
        # q的输出是(b,100,8,64),kv也是一样
        q = self.w_qs(q).view(sz_b, len_q, n_head, d_k)
        k = self.w_ks(k).view(sz_b, len_k, n_head, d_k)
        v = self.w_vs(v).view(sz_b, len_v, n_head, d_v)

        # 变成(b,8,100,64)，方便后面计算，也就是8个头单独计算
        q, k, v = q.transpose(1, 2), k.transpose(1, 2), v.transpose(1, 2)

        if mask is not None:
            mask = mask.unsqueeze(1)   # For head axis broadcasting.
        # 输出q是(b,8,100,64),维持不变,内部计算流程是：
        # q*k转置，除以d_k ** 0.5，输出维度是b,8,100,100即单词和单词直接的相似性
        # 对最后一个维度进行softmax操作得到b,8,100,100
        # 最后乘上V，得到b,8,100,64输出
        q, attn = self.attention(q, k, v, mask=mask)

        # b,100,8,64-->b,100,512
        q = q.transpose(1, 2).contiguous().view(sz_b, len_q, -1)
        q = self.dropout(self.fc(q))
        # 残差计算
        q += residual
        # 层归一化，在512维度计算均值和方差，进行层归一化
        q = self.layer_norm(q)

        return q, attn

4、前馈网络

这个层就没啥说的了，非常简单，直接看代码吧：

class PositionwiseFeedForward(nn.Module):
    ''' A two-feed-forward-layer module '''

    def __init__(self, d_in, d_hid, dropout=0.1):
        super().__init__()
        # 两个fc层，对最后的512维度进行变换
        self.w_1 = nn.Linear(d_in, d_hid) # position-wise
        self.w_2 = nn.Linear(d_hid, d_in) # position-wise
        self.layer_norm = nn.LayerNorm(d_in, eps=1e-6)
        self.dropout = nn.Dropout(dropout)

    def forward(self, x):
        residual = x

        x = self.w_2(F.relu(self.w_1(x)))
        x = self.dropout(x)
        x += residual

        x = self.layer_norm(x)

        return x

Transformer

Transformer 是 Google 在 2017 年提出的用于机器翻译的模型。

Transformer 的内部，在本质上是一个 Encoder-Decoder 的结构，即编码器-解码器。

Transformer 中抛弃了传统的 CNN 和 RNN，整个网络结构完全由 Attention 机制组成，并且采用了 6 层 Encoder-Decoder 结构。

以一个简单的例子进行说明：

输入自然语言序列到编码器: Why do we work?(为什么要工作)；
编码器输出的隐藏层，再输入到解码器；
输入 <𝑠𝑡𝑎𝑟𝑡> (起始)符号到解码器；
解码器得到第一个字”为”；
将得到的第一个字”为”落下来再输入到解码器；
解码器得到第二个字”什”；
将得到的第二字再落下来，直到解码器输出 <𝑒𝑛𝑑> (终止符)，即序列生成完成。

1、位置嵌入（𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛𝑎𝑙 𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔）

# 导入依赖库
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import math

def get_positional_encoding(max_seq_len, embed_dim):
    # 初始化一个positional encoding
    # embed_dim: 字嵌入的维度
    # max_seq_len: 最大的序列长度
    positional_encoding = np.array([
        [pos / np.power(10000, 2 * i / embed_dim) for i in range(embed_dim)]
        if pos != 0 else np.zeros(embed_dim) for pos in range(max_seq_len)])
    positional_encoding[1:, 0::2] = np.sin(positional_encoding[1:, 0::2])  # dim 2i 偶数
    positional_encoding[1:, 1::2] = np.cos(positional_encoding[1:, 1::2])  # dim 2i+1 奇数
    # 归一化, 用位置嵌入的每一行除以它的模长
    # denominator = np.sqrt(np.sum(position_enc**2, axis=1, keepdims=True))
    # position_enc = position_enc / (denominator + 1e-8)
    return positional_encoding
    
positional_encoding = get_positional_encoding(max_seq_len=100, embed_dim=16)
plt.figure(figsize=(10,10))
sns.heatmap(positional_encoding)
plt.title("Sinusoidal Function")
plt.xlabel("hidden dimension")
plt.ylabel("sequence length")

可以看到，位置嵌入在 𝑒𝑚𝑏𝑒𝑑𝑑𝑖𝑛𝑔 𝑑𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛 （也是hidden dimension ）维度上随着维度序号增大，周期变化会越来越慢，而产生一种包含位置信息的纹理。

就这样，产生独一的纹理位置信息，模型从而学到位置之间的依赖关系和自然语言的时序特性。

最后，将Xembedding 和 位置嵌入 相加，送给下一层。

2、自注意力层（𝑠𝑒𝑙𝑓 𝑎𝑡𝑡𝑒𝑛𝑡𝑖𝑜𝑛 𝑚𝑒𝑐ℎ𝑎𝑛𝑖𝑠𝑚）

直接看下图笔记，讲解的非常详细。

多头的意义在于，$QK^{T}$ 得到的矩阵就叫注意力矩阵，它可以表示每个字与其他字的相似程度。因为，向量的点积值越大，说明两个向量越接近。

我们的目的是，让每个字都含有当前这个句子中的所有字的信息，用注意力层，我们做到了。

每个句子的长度是不一样的，需要按照最长的句子的长度统一处理。对于短的句子，进行 Padding 操作，一般我们用 0 来进行填充。

3、残差链接和层归一化

加入了残差设计和层归一化操作，目的是为了防止梯度消失，加快收敛。

1) 残差设计

$$
X_{\text {embedding }}+\text { Attention }(Q, K, V)
$$

$$
X+\text { SubLayer }(X)
$$

2) 层归一化

作用是把神经网络中隐藏层归一为标准正态分布，也就是 𝑖.𝑖.𝑑 独立同分布，以起到加快训练速度，加速收敛的作用。

$$
\mu_{i}=\frac{1}{m} \sum_{i=1}^{m} x_{i j}
$$

上式中以矩阵的行 (𝑟𝑜𝑤) 为单位求均值：

$$
\sigma_{j}^{2}=\frac{1}{m} \sum_{i=1}^{m}\left(x_{i j}-\mu_{j}\right)^{2}
$$

上式中以矩阵的行 (𝑟𝑜𝑤) 为单位求方差：

$$
\operatorname{LayerNorm}(x)=\alpha \odot \frac{x_{i j}-\mu_{i}}{\sqrt{\sigma_{i}^{2}+\epsilon}}+\beta
$$

代码层面非常简单，单头 attention 操作如下：

class ScaledDotProductAttention(nn.Module):
    ''' Scaled Dot-Product Attention '''

    def __init__(self, temperature, attn_dropout=0.1):
        super().__init__()
        self.temperature = temperature
        self.dropout = nn.Dropout(attn_dropout)

    def forward(self, q, k, v, mask=None):
        # self.temperature是论文中的d_k ** 0.5，防止梯度过大
        # QxK/sqrt(dk)
        attn = torch.matmul(q / self.temperature, k.transpose(2, 3))

        if mask is not None:
            # 屏蔽不想要的输出
            attn = attn.masked_fill(mask == 0, -1e9)
        # softmax+dropout
        attn = self.dropout(F.softmax(attn, dim=-1))
        # 概率分布xV
        output = torch.matmul(attn, v)

        return output, attn

Multi-Head Attention 实现在 ScaledDotProductAttention 基础上构建：

class MultiHeadAttention(nn.Module):
    ''' Multi-Head Attention module '''

    # n_head头的个数，默认是8
    # d_model编码向量长度，例如本文说的512
    # d_k, d_v的值一般会设置为 n_head * d_k=d_model，
    # 此时concat后正好和原始输入一样，当然不相同也可以，因为后面有fc层
    # 相当于将可学习矩阵分成独立的n_head份
    def __init__(self, n_head, d_model, d_k, d_v, dropout=0.1):
        super().__init__()
        # 假设n_head=8，d_k=64
        self.n_head = n_head
        self.d_k = d_k
        self.d_v = d_v
        # d_model输入向量，n_head * d_k输出向量
        # 可学习W^Q，W^K,W^V矩阵参数初始化
        self.w_qs = nn.Linear(d_model, n_head * d_k, bias=False)
        self.w_ks = nn.Linear(d_model, n_head * d_k, bias=False)
        self.w_vs = nn.Linear(d_model, n_head * d_v, bias=False)
        # 最后的输出维度变换操作
        self.fc = nn.Linear(n_head * d_v, d_model, bias=False)
        # 单头自注意力
        self.attention = ScaledDotProductAttention(temperature=d_k ** 0.5)
        self.dropout = nn.Dropout(dropout)
        # 层归一化
        self.layer_norm = nn.LayerNorm(d_model, eps=1e-6)

    def forward(self, q, k, v, mask=None):
        # 假设qkv输入是(b,100,512),100是训练每个样本最大单词个数
        # 一般qkv相等，即自注意力
        residual = q
        # 将输入x和可学习矩阵相乘，得到(b,100,512)输出
        # 其中512的含义其实是8x64，8个head，每个head的可学习矩阵为64维度
        # q的输出是(b,100,8,64),kv也是一样
        q = self.w_qs(q).view(sz_b, len_q, n_head, d_k)
        k = self.w_ks(k).view(sz_b, len_k, n_head, d_k)
        v = self.w_vs(v).view(sz_b, len_v, n_head, d_v)

        # 变成(b,8,100,64)，方便后面计算，也就是8个头单独计算
        q, k, v = q.transpose(1, 2), k.transpose(1, 2), v.transpose(1, 2)

        if mask is not None:
            mask = mask.unsqueeze(1)   # For head axis broadcasting.
        # 输出q是(b,8,100,64),维持不变,内部计算流程是：
        # q*k转置，除以d_k ** 0.5，输出维度是b,8,100,100即单词和单词直接的相似性
        # 对最后一个维度进行softmax操作得到b,8,100,100
        # 最后乘上V，得到b,8,100,64输出
        q, attn = self.attention(q, k, v, mask=mask)

        # b,100,8,64-->b,100,512
        q = q.transpose(1, 2).contiguous().view(sz_b, len_q, -1)
        q = self.dropout(self.fc(q))
        # 残差计算
        q += residual
        # 层归一化，在512维度计算均值和方差，进行层归一化
        q = self.layer_norm(q)

        return q, attn

4、前馈网络

这个层就没啥说的了，非常简单，直接看代码吧：

class PositionwiseFeedForward(nn.Module):
    ''' A two-feed-forward-layer module '''

    def __init__(self, d_in, d_hid, dropout=0.1):
        super().__init__()
        # 两个fc层，对最后的512维度进行变换
        self.w_1 = nn.Linear(d_in, d_hid) # position-wise
        self.w_2 = nn.Linear(d_hid, d_in) # position-wise
        self.layer_norm = nn.LayerNorm(d_in, eps=1e-6)
        self.dropout = nn.Dropout(dropout)

    def forward(self, x):
        residual = x

        x = self.w_2(F.relu(self.w_1(x)))
        x = self.dropout(x)
        x += residual

        x = self.layer_norm(x)

        return x

最后，回顾下 𝑡𝑟𝑎𝑛𝑠𝑓𝑜𝑟𝑚𝑒𝑟 𝑒𝑛𝑐𝑜𝑑𝑒𝑟 的整体结构。

经过上文的梳理，我们已经基本了解了 𝑡𝑟𝑎𝑛𝑠𝑓𝑜𝑟𝑚𝑒𝑟 编码器的主要构成部分，我们下面用公式把一个 𝑡𝑟𝑎𝑛𝑠𝑓𝑜𝑟𝑚𝑒𝑟 𝑏𝑙𝑜𝑐𝑘 的计算过程整理一下：

1) 字向量与位置编码
$$X= EmbeddingLookup (X)+ PositionalEncoding$$

$$X \in \mathbb{R}^{\text {batch size } * \text { seq. len. * embed.dim. }}$$
2) 自注意力机制

$$
Q=\operatorname{Linear}(X)=X W_{Q}
$$

$$
K=\operatorname{Linear}(X)=X W_{K}
$$

$$
V=\operatorname{Linear}(X)=X W_{V}
$$

$$
X_{\text {attention }}=\text { SelfAttention }(Q, K, V)
$$

3) 残差连接与层归一化

$$
X_{\text {attention }}=X+X_{\text {attention }}
$$

$$
X_{\text {attention }}=\text { Layer Norm }\left(X_{\text {attention }}\right)
$$

4) 前向网络
其实就是两层线性映射并用激活函数激活，比如说 ReLU :
$$
X_{\text {hidden }}=\operatorname{Activate}\left(\text { Linear }\left(\text { Linear }\left(X_{\text {attention }}\right)\right)\right)
$$
5) 重复3)

$$
X_{\text {hidden }}=X_{\text {attention }}+X_{\text {hidden }}
$$

$$
X_{\text {hidden }}=\text { Layer } N \text { orm }\left(X_{\text {hidden }}\right)
$$

$$
X_{\text {hidden }} \in \mathbb{R}^{\text {batch size } * \text { seq. len. } * \text { embed. dim. }}
$$

级联分类器

在本教程中， – 我们将学习Haar级联对象检测的工作原理。 – 我们将使用基于Haar Feature的Cascade分类器了解人脸检测和眼睛检测的基础知识。 – 我们将使用**cv::CascadeClassifier**类来检测视频流中的对象。特别是，我们将使用以下函数： – **cv::CascadeClassifier::load**来加载.xml分类器文件。它可以是Haar或LBP分类器 – **cv::CascadeClassifier::detectMultiScale**来执行检测。

理论

使用基于Haar特征的级联分类器的对象检测是Paul Viola和Michael Jones在其论文“使用简单特征的增强级联进行快速对象检测”中于2001年提出的一种有效的对象检测方法。这是一种基于机器学习的方法，其中从许多正负图像中训练级联函数。然后用于检测其他图像中的对象。

在这里，我们将进行人脸检测。最初，该算法需要大量正图像（面部图像）和负图像（无面部图像）来训练分类器。然后，我们需要从中提取特征。为此，使用下图所示的Haar功能。它们就像我们的卷积核一样。每个特征都是通过从黑色矩形下的像素总和中减去白色矩形下的像素总和而获得的单个值。

现在，每个内核的所有可能大小和位置都用于计算许多功能。（试想一下它产生多少计算？即使是一个24×24的窗口也会产生超过160000个特征）。对于每个特征计算，我们需要找到白色和黑色矩形下的像素总和。为了解决这个问题，他们引入了整体图像。无论你的图像有多大，它都会将给定像素的计算减少到仅涉及四个像素的操作。很好，不是吗？它使事情变得更快。

但是在我们计算的所有这些特征中，大多数都不相关。例如，考虑下图。第一行显示了两个良好的特征。选择的第一个特征似乎着眼于眼睛区域通常比鼻子和脸颊区域更暗的性质。选择的第二个特征依赖于眼睛比鼻梁更黑的属性。但是，将相同的窗口应用于脸颊或其他任何地方都是无关紧要的。那么，我们如何从16万多个功能中选择最佳特征？它是由**Adaboost**实现的。

为此，我们将所有特征应用于所有训练图像。对于每个特征，它会找到最佳的阈值，该阈值会将人脸分为正面和负面。显然，会出现错误或分类错误。我们选择错误率最低的特征，这意味着它们是对人脸和非人脸图像进行最准确分类的特征。（此过程并非如此简单。在开始时，每个图像的权重均相等。在每次分类后，错误分类的图像的权重都会增加。然后执行相同的过程。将计算新的错误率。还要计算新的权重。继续进行此过程，直到达到所需的精度或错误率或找到所需的功能数量为止。

最终分类器是这些弱分类器的加权和。之所以称为弱分类，是因为仅凭它不能对图像进行分类，而是与其他分类一起形成强分类器。该论文说，甚至200个功能都可以提供95％的准确度检测。他们的最终设置具有大约6000个功能。（想象一下，从160000多个功能减少到6000个功能。这是很大的收获）。

因此，现在你拍摄一张照片。取每个24×24窗口。向其应用6000个功能。检查是否有脸。哇..这不是效率低下又费时吗？是的。作者对此有一个很好的解决方案。

在图像中，大多数图像是非面部区域。因此，最好有一种简单的方法来检查窗口是否不是面部区域。如果不是，请一次性丢弃它，不要再次对其进行处理。相反，应将重点放在可能有脸的区域。这样，我们将花费更多时间检查可能的面部区域。

为此，他们引入了级联分类器的概念。不是将所有6000个功能部件应用到一个窗口中，而是将这些功能部件分组到不同的分类器阶段，并一一应用。（通常前几个阶段将包含很少的功能）。如果窗口在第一阶段失败，则将其丢弃。我们不考虑它的其余功能。如果通过，则应用功能的第二阶段并继续该过程。经过所有阶段的窗口是一个面部区域。这个计划怎么样！

作者的检测器具有6000多个特征，具有38个阶段，在前五个阶段具有1、10、25、25和50个特征。（上图中的两个功能实际上是从Adaboost获得的最佳两个功能）。根据作者的说法，每个子窗口平均评估了6000多个特征中的10个特征。

因此，这是Viola-Jones人脸检测工作原理的简单直观说明。阅读本文以获取更多详细信息，或查看其他资源部分中的参考资料。

实现步骤：

使用Haar特征做检测；
使用积分图（Integral Image）对Haar特征求值进行加速；
使用AdaBoost算法训练区分人脸和非人脸的强分类器；
使用筛选式级联把强分类器级联到一起，提高准确率；

OpenCV中的Haar-级联检测器

OpenCV提供了一种训练方法（请参阅**Cascade分类器训练**）或预先训练的模型，可以使用**cv::CascadeClassifier::load**方法读取。预训练的模型位于OpenCV安装的data文件夹中，或在此处找到。

以下代码示例将使用预训练的Haar级联模型来检测图像中的面部和眼睛。首先，创建一个cv::CascadeClassifier并使用**cv::CascadeClassifier::load**方法加载必要的XML文件。然后，使用**cv::CascadeClassifier::detectMultiScale**方法完成检测，该方法返回检测到的脸部或眼睛的边界矩形。

from __future__ import print_function
import cv2 as cv
import argparse
def detectAndDisplay(frame):
    frame_gray = cv.cvtColor(frame, cv.COLOR_BGR2GRAY)
    frame_gray = cv.equalizeHist(frame_gray)
    #-- 检测面部
    faces = face_cascade.detectMultiScale(frame_gray)
    for (x,y,w,h) in faces:
        center = (x + w//2, y + h//2)
        frame = cv.ellipse(frame, center, (w//2, h//2), 0, 0, 360, (255, 0, 255), 4)
        faceROI = frame_gray[y:y+h,x:x+w]
        #-- 在每张面部上检测眼睛
        eyes = eyes_cascade.detectMultiScale(faceROI)
        for (x2,y2,w2,h2) in eyes:
            eye_center = (x + x2 + w2//2, y + y2 + h2//2)
            radius = int(round((w2 + h2)*0.25))
            frame = cv.circle(frame, eye_center, radius, (255, 0, 0 ), 4)
    cv.imshow('Capture - Face detection', frame)
parser = argparse.ArgumentParser(description='Code for Cascade Classifier tutorial.')
parser.add_argument('--face_cascade', help='Path to face cascade.', default='data/haarcascades/haarcascade_frontalface_alt.xml')
parser.add_argument('--eyes_cascade', help='Path to eyes cascade.', default='data/haarcascades/haarcascade_eye_tree_eyeglasses.xml')
parser.add_argument('--camera', help='Camera divide number.', type=int, default=0)
args = parser.parse_args()
face_cascade_name = args.face_cascade
eyes_cascade_name = args.eyes_cascade
face_cascade = cv.CascadeClassifier()
eyes_cascade = cv.CascadeClassifier()
#-- 1. 加载级联
if not face_cascade.load(cv.samples.findFile(face_cascade_name)):
    print('--(!)Error loading face cascade')
    exit(0)
if not eyes_cascade.load(cv.samples.findFile(eyes_cascade_name)):
    print('--(!)Error loading eyes cascade')
    exit(0)
camera_device = args.camera
#-- 2. 读取视频流
cap = cv.VideoCapture(camera_device)
if not cap.isOpened:
    print('--(!)Error opening video capture')
    exit(0)
while True:
    ret, frame = cap.read()
    if frame is None:
        print('--(!) No captured frame -- Break!')
        break
    detectAndDisplay(frame)
    if cv.waitKey(10) == 27:
        break

图像修补

你们大多数人家里都会有一些旧的旧化照片，上面有黑点，一些笔触等。你是否曾经想过将其还原？我们不能简单地在绘画工具中擦除它们，因为它将简单地用白色结构代替黑色结构，这是没有用的。在这些情况下，将使用一种称为图像修复的技术。基本思想很简单：用附近的像素替换那些不良区域，使其看起来和邻近的协调。考虑下面显示的图像（摘自Wikipedia）：

基于此目的设计了几种算法，OpenCV提供了其中两种。两者都可以通过相同的函数进行访问，cv.inpaint()

第一种算法基于Alexandru Telea在2004年发表的论文“基于快速行进方法的图像修补技术”。它基于快速行进方法。考虑图像中要修复的区域。算法从该区域的边界开始，并进入该区域内部，首先逐渐填充边界中的所有内容。在要修复的邻域上的像素周围需要一个小的邻域。该像素被附近所有已知像素的归一化加权总和所代替。权重的选择很重要。那些位于该点附近，边界法线附近的像素和那些位于边界轮廓线上的像素将获得更大的权重。修复像素后，将使用快速行进方法将其移动到下一个最近的像素。FMM确保首先修复已知像素附近的那些像素，以便像手动启发式操作一样工作。通过使用标志**cv.INPAINT_TELEA**启用此算法。

第二种算法基于Bertalmio，Marcelo，Andrea L. Bertozzi和Guillermo Sapiro在2001年发表的论文“ Navier-Stokes，流体动力学以及图像和视频修补”。该算法基于流体动力学并利用了偏微分方程。基本原理是启发式的。它首先沿着边缘从已知区域移动到未知区域（因为边缘是连续的）。它延续了等距线（线连接具有相同强度的点，就像轮廓线连接具有相同高程的点一样），同时在修复区域的边界匹配梯度矢量。为此，使用了一些流体动力学方法。获得它们后，将填充颜色以减少该区域的最小差异。通过使用标志**cv.INPAINT_NS**启用此算法。

代码

我们需要创建一个与输入图像大小相同的掩码，其中非零像素对应于要修复的区域。其他一切都很简单。我的图像因一些黑色笔画而旧化（我手动添加了）。我使用“绘画”工具创建了相应的笔触。

import numpy as np
import cv2 as cv
img = cv.imread('messi_2.jpg')
mask = cv.imread('mask2.png',0)
dst = cv.inpaint(img,mask,3,cv.INPAINT_TELEA)
cv.imshow('dst',dst)
cv.waitKey(0)
cv.destroyAllWindows()

请参阅下面的结果。第一张图片显示了降级的输入。第二个图像是掩码。第三个图像是第一个算法的结果，最后一个图像是第二个算法的结果。

### 附加资源 1. Bertalmio, Marcelo, Andrea L. Bertozzi, and Guillermo Sapiro. “Navier-stokes, fluid dynamics, and image and video inpainting.” In Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on, vol. 1, pp. I-355. IEEE, 2001. 2. Telea, Alexandru. “An image inpainting technique based on the fast marching method.” Journal of graphics tools 9.1 (2004): 23-34.

练习

OpenCV一个有关修复的交互式示例，samples/python/inpaint.py，请尝试一下。

#!/usr/bin/env python

'''
Inpainting sample.
Inpainting repairs damage to images by floodfilling
the damage with surrounding image areas.
Usage:
  inpaint.py [<image>]
Keys:
  SPACE - inpaint
  r     - reset the inpainting mask
  ESC   - exit
'''

# Python 2/3 compatibility
from __future__ import print_function

import numpy as np
import cv2 as cv

from common import Sketcher

def main():
    import sys
    try:
        fn = sys.argv[1]
    except:
        fn = 'fruits.jpg'

    img = cv.imread(cv.samples.findFile(fn))
    if img is None:
        print('Failed to load image file:', fn)
        sys.exit(1)

    img_mark = img.copy()
    mark = np.zeros(img.shape[:2], np.uint8)
    sketch = Sketcher('img', [img_mark, mark], lambda : ((255, 255, 255), 255))

    while True:
        ch = cv.waitKey()
        if ch == 27:
            break
        if ch == ord(' '):
            res = cv.inpaint(img_mark, mark, 3, cv.INPAINT_TELEA)
            cv.imshow('inpaint', res)
        if ch == ord('r'):
            img_mark[:] = img
            mark[:] = 0
            sketch.show()

    print('Done')


if __name__ == '__main__':
    print(__doc__)
    main()
    cv.destroyAllWindows()

图像去噪

通常认为噪声是零均值的随机变量。考虑一个有噪声的像素，p=p0+n，其中p0是像素的真实值，n是该像素中的噪声。你可以从不同的图像中获取大量相同的像素（例如N）并计算其平均值。理想情况下，由于噪声的平均值为零，因此应该得到p=p0。

你可以通过简单的设置自己进行验证。将静态相机固定在某个位置几秒钟。这将为你提供很多帧或同一场景的很多图像。然后编写一段代码，找到视频中所有帧的平均值（这对你现在应该太简单了）。比较最终结果和第一帧。你会看到噪声减少。不幸的是，这种简单的方法对摄像机和场景的运动并不稳健。通常，只有一张嘈杂的图像可用。

因此想法很简单，我们需要一组相似的图像来平均噪声。考虑图像中的一个小窗口（例如5×5窗口）。很有可能同一修补程序可能位于图像中的其他位置。有时在它周围的一个小社区中。一起使用这些相似的补丁并找到它们的平均值怎么办？对于那个特定的窗口，这很好。请参阅下面的示例图片：

图像中的蓝色补丁看起来很相似。绿色补丁看起来很相似。因此，我们获取一个像素，在其周围获取一个小窗口，在图像中搜索相似的窗口，对所有窗口求平均，然后用得到的结果替换该像素。此方法是“非本地均值消噪”。与我们之前看到的模糊技术相比，它花费了更多时间，但是效果非常好。更多信息和在线演示可在其他资源的第一个链接中找到。

对于彩色图像，图像将转换为CIELAB色彩空间，然后分别对L和AB分量进行降噪。

OpenCV中的图像去噪

OpenCV提供了此方法的四个变体。

cv.fastNlMeansDenoising()-处理单个灰度图像
cv.fastNlMeansDenoisingColored()-处理彩色图像。
cv.fastNlMeansDenoisingMulti()-处理在短时间内捕获的图像序列（灰度图像）
cv.fastNlMeansDenoisingColoredMulti()-与上面相同，但用于彩色图像。

常用参数为： – h：决定滤波器强度的参数。较高的h值可以更好地消除噪点，但同时也可以消除图像细节。（可以设为10） – hForColorComponents：与h相同，但仅用于彩色图像。（通常与h相同） – templateWindowSize：应为奇数。（建议设为7） – searchWindowSize：应为奇数。（建议设为21）

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
img = cv.imread('die.png')
dst = cv.fastNlMeansDenoisingColored(img,None,10,10,7,21)
plt.subplot(121),plt.imshow(img)
plt.subplot(122),plt.imshow(dst)
plt.show()

cv.fastNlMeansDenoisingMulti() 现在，我们将对视频应用相同的方法。第一个参数是噪声帧列表。第二个参数imgToDenoiseIndex指定我们需要去噪的帧，为此，我们在输入列表中传递帧的索引。第三是temporalWindowSize，它指定要用于降噪的附近帧的数量。应该很奇怪。在那种情况下，总共使用temporalWindowSize帧，其中中心帧是要被去噪的帧。例如，你传递了一个5帧的列表作为输入。令imgToDenoiseIndex = 2,temporalWindowSize =3。然后使用frame-1，frame-2和frame-3去噪frame-2。让我们来看一个例子。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
cap = cv.VideoCapture('vtest.avi')
# 创建5个帧的列表
img = [cap.read()[1] for i in xrange(5)]
# 将所有转化为灰度
gray = [cv.cvtColor(i, cv.COLOR_BGR2GRAY) for i in img]
# 将所有转化为float64
gray = [np.float64(i) for i in gray]
# 创建方差为25的噪声
noise = np.random.randn(*gray[1].shape)*10
# 在图像上添加噪声
noisy = [i+noise for i in gray]
# 转化为unit8
noisy = [np.uint8(np.clip(i,0,255)) for i in noisy]
# 对第三帧进行降噪
dst = cv.fastNlMeansDenoisingMulti(noisy, 2, 5, None, 4, 7, 35)
plt.subplot(131),plt.imshow(gray[2],'gray')
plt.subplot(132),plt.imshow(noisy[2],'gray')
plt.subplot(133),plt.imshow(dst,'gray')
plt.show()

计算需要花费大量时间。结果，第一个图像是原始帧，第二个是噪声帧，第三个是去噪图像。

附加资源

http://www.ipol.im/pub/art/2011/bcm_nlm/ (它包含详细信息，在线演示等。强烈建议访问。我们的测试图像是从此链接生成的)
Online course at coursera (这里拍摄的第一张图片)

opencv 视频对象追踪

1、背景分离方法

背景分离（BS）是一种通过使用静态相机来生成前景掩码（即包含属于场景中的移动对象像素的二进制图像）的常用技术。
顾名思义，BS计算前景掩码，在当前帧与背景模型之间执行减法运算，其中包含场景的静态部分，或者更一般而言，考虑到所观察场景的特征，可以将其视为背景的所有内容。

背景建模包括两个主要步骤： 1. 背景初始化； 2. 背景更新。

第一步，计算背景的初始模型，而在第二步中，更新模型以适应场景中可能的变化。

在本教程中，我们将学习如何使用OpenCV中的BS。

目标

在本教程中，您将学习如何： 1. 使用**cv::VideoCapture**从视频或图像序列中读取数据； 2. 通过使用**cv::BackgroundSubtractor**类创建和更新背景类； 3. 通过使用**cv::imshow**获取并显示前景蒙版；

代码

在下面，您可以找到源代码。我们将让用户选择处理视频文件或图像序列。在此示例中，我们将使用**cv::BackgroundSubtractorMOG2**生成前景掩码。

结果和输入数据将显示在屏幕上。

from __future__ import print_function
import cv2 as cv
import argparse
parser = argparse.ArgumentParser(description='This program shows how to use background subtraction methods provided by \
                                              OpenCV. You can process both videos and images.')
parser.add_argument('--input', type=str, help='Path to a video or a sequence of image.', default='vtest.avi')
parser.add_argument('--algo', type=str, help='Background subtraction method (KNN, MOG2).', default='MOG2')
args = parser.parse_args()
if args.algo == 'MOG2':
    backSub = cv.createBackgroundSubtractorMOG2()
else:
    backSub = cv.createBackgroundSubtractorKNN()
capture = cv.VideoCapture(cv.samples.findFileOrKeep(args.input))
if not capture.isOpened:
    print('Unable to open: ' + args.input)
    exit(0)
while True:
    ret, frame = capture.read()
    if frame is None:
        break

    fgMask = backSub.apply(frame)


    cv.rectangle(frame, (10, 2), (100,20), (255,255,255), -1)
    cv.putText(frame, str(capture.get(cv.CAP_PROP_POS_FRAMES)), (15, 15),
               cv.FONT_HERSHEY_SIMPLEX, 0.5 , (0,0,0))


    cv.imshow('Frame', frame)
    cv.imshow('FG Mask', fgMask)

    keyboard = cv.waitKey(30)
    if keyboard == 'q' or keyboard == 27:
        break

2、Meanshift和Camshift

Meanshift

Meanshift背后的直觉很简单，假设你有点的集合。（它可以是像素分布，例如直方图反投影）。你会得到一个小窗口（可能是一个圆形），并且必须将该窗口移到最大像素密度（或最大点数）的区域。如下图所示：

初始窗口以蓝色圆圈显示，名称为“C1”。其原始中心以蓝色矩形标记，名称为“C1_o”。但是，如果找到该窗口内点的质心，则会得到点“C1_r”（标记为蓝色小圆圈），它是窗口的真实质心。当然，它们不匹配。因此，移动窗口，使新窗口的圆与上一个质心匹配。再次找到新的质心。很可能不会匹配。因此，再次移动它，并继续迭代，以使窗口的中心及其质心落在同一位置（或在很小的期望误差内）。因此，最终您获得的是一个具有最大像素分布的窗口。它带有一个绿色圆圈，名为“C2”。正如您在图像中看到的，它具有最大的点数。整个过程在下面的静态图像上演示：

因此，我们通常会传递直方图反投影图像和初始目标位置。当对象移动时，显然该移动会反映在直方图反投影图像中。结果，meanshift算法将窗口移动到最大密度的新位置。

OpenCV中的Meanshift

要在OpenCV中使用meanshift，首先我们需要设置目标，找到其直方图，以便我们可以将目标反投影到每帧上以计算均值偏移。我们还需要提供窗口的初始位置。对于直方图，此处仅考虑色相。另外，为避免由于光线不足而产生错误的值，可以使用**cv.inRange**()函数丢弃光线不足的值。

import numpy as np
import cv2 as cv
import argparse
parser = argparse.ArgumentParser(description='This sample demonstrates the meanshift algorithm. \
                                              The example file can be downloaded from: \
                                              https://www.bogotobogo.com/python/OpenCV_Python/images/mean_shift_tracking/slow_traffic_small.mp4')
parser.add_argument('image', type=str, help='path to image file')
args = parser.parse_args()
cap = cv.VideoCapture(args.image)
# 视频的第一帧
ret,frame = cap.read()
# 设置窗口的初始位置
x, y, w, h = 300, 200, 100, 50 # simply hardcoded the values
track_window = (x, y, w, h)
# 设置初始ROI来追踪
roi = frame[y:y+h, x:x+w]
hsv_roi =  cv.cvtColor(roi, cv.COLOR_BGR2HSV)
mask = cv.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
roi_hist = cv.calcHist([hsv_roi],[0],mask,[180],[0,180])
cv.normalize(roi_hist,roi_hist,0,255,cv.NORM_MINMAX)
# 设置终止条件，可以是10次迭代，也可以至少移动1 pt
term_crit = ( cv.TERM_CRITERIA_EPS | cv.TERM_CRITERIA_COUNT, 10, 1 )
while(1):
    ret, frame = cap.read()
    if ret == True:
        hsv = cv.cvtColor(frame, cv.COLOR_BGR2HSV)
        dst = cv.calcBackProject([hsv],[0],roi_hist,[0,180],1)
        # 应用meanshift来获取新位置
        ret, track_window = cv.meanShift(dst, track_window, term_crit)
        # 在图像上绘制
        x,y,w,h = track_window
        img2 = cv.rectangle(frame, (x,y), (x+w,y+h), 255,2)
        cv.imshow('img2',img2)
        k = cv.waitKey(30) & 0xff
        if k == 27:
            break
    else:
        break

我使用的视频中的三帧如下：

Camshift

您是否密切关注了最后结果？这儿存在一个问题。无论汽车离相机很近或非常近，我们的窗口始终具有相同的大小。这是不好的。我们需要根据目标的大小和旋转来调整窗口大小。该解决方案再次来自“ OpenCV Labs”，它被称为Gary布拉德斯基（Gary Bradsky）在其1998年的论文“用于感知用户界面中的计算机视觉面部跟踪”中发表的CAMshift（连续自适应均值偏移）[26]。它首先应用Meanshift。一旦Meanshift收敛，它将更新窗口的大小为s = 2 \times \sqrt{\frac{M_{00}}{256}}。它还可以计算出最合适的椭圆的方向。再次将均值偏移应用于新的缩放搜索窗口和先前的窗口位置。该过程一直持续到达到要求的精度为止。

OpenCV中的Camshift

它与meanshift相似，但是返回一个旋转的矩形（即我们的结果）和box参数（用于在下一次迭代中作为搜索窗口传递）。请参见下面的代码：

import numpy as np
import cv2 as cv
import argparse
parser = argparse.ArgumentParser(description='This sample demonstrates the camshift algorithm. \
                                              The example file can be downloaded from: \
                                              https://www.bogotobogo.com/python/OpenCV_Python/images/mean_shift_tracking/slow_traffic_small.mp4')
parser.add_argument('image', type=str, help='path to image file')
args = parser.parse_args()
cap = cv.VideoCapture(args.image)
# 获取视频第一帧
ret,frame = cap.read()
# 设置初始窗口
x, y, w, h = 300, 200, 100, 50 # simply hardcoded the values
track_window = (x, y, w, h)
# 设置追踪的ROI窗口
roi = frame[y:y+h, x:x+w]
hsv_roi =  cv.cvtColor(roi, cv.COLOR_BGR2HSV)
mask = cv.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
roi_hist = cv.calcHist([hsv_roi],[0],mask,[180],[0,180])
cv.normalize(roi_hist,roi_hist,0,255,cv.NORM_MINMAX)
# 设置终止条件，可以是10次迭代，有可以至少移动1个像素
term_crit = ( cv.TERM_CRITERIA_EPS | cv.TERM_CRITERIA_COUNT, 10, 1 )
while(1):
    ret, frame = cap.read()
    if ret == True:
        hsv = cv.cvtColor(frame, cv.COLOR_BGR2HSV)
        dst = cv.calcBackProject([hsv],[0],roi_hist,[0,180],1)
        # 应用camshift 到新位置
        ret, track_window = cv.CamShift(dst, track_window, term_crit)
        # 在图像上画出来
        pts = cv.boxPoints(ret)
        pts = np.int0(pts)
        img2 = cv.polylines(frame,[pts],True, 255,2)
        cv.imshow('img2',img2)
        k = cv.waitKey(30) & 0xff
        if k == 27:
            break
    else:
        break

三帧的结果如下

图像傅里叶变换 and图像分割的经典算法：分水岭算法

摘自网络，侵权立删。

傅里叶变换的作用：

　　对于数字图像这种离散的信号，频率大小表示信号变换的剧烈程度或者说信号变化的快慢。频率越大，变换越剧烈，频率越小，信号越平缓，对应到的图像中，高频信号往往是图像中的边缘信号和噪声信号，而低频信号包含图像变化频繁的图像轮廓及背景灯信号。

　　需要说明的是：傅里叶变换得到的频谱图上的点与原图像上的点之间不存在一一对应的关系。

1，图像经过二维傅里叶的变换后，其变换稀疏矩阵具有如下性质：若交换矩阵原点设在中心，其频谱能量集中分布在变换稀疏矩阵的中心附近。若所用的二维傅里叶变换矩阵的云巅设在左上角，那么图像信号能量将集中在系数矩阵的四个角上。这是由二维傅里叶变换本身性质决定的。同时也表明一股图像能量集中低频区域。

2，图像灰度变化缓慢的区域，对应它变换后的低频分量部分；图像灰度呈阶跃变化的区域，对应变换后的高频分量部分。除颗粒噪音外，图像细节的边缘，轮廓处都是灰度变换突变区域，他们都具有变换后的高频分量特征。

右边为频率分布图谱，其中越靠近中心位置频率越低，越亮（灰度值越高）的位置代表该频率的信息振幅越大。

右边图中，每一个点：

1）它到中点的距离描述的是频率

2）中点到它的方向，是平面波的方向

3）那一点的灰度值描述的是它的幅值

OpenCV中的傅里叶变换

OpenCV为此提供了**cv.dft**()和**cv.idft**()函数。它返回与前一个相同的结果，但是有两个通道。第一个通道是结果的实部，第二个通道是结果的虚部。输入图像首先应转换为np.float32。我们来看看怎么做。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
img = cv.imread('messi5.jpg',0)
dft = cv.dft(np.float32(img),flags = cv.DFT_COMPLEX_OUTPUT)
dft_shift = np.fft.fftshift(dft)
magnitude_spectrum = 20*np.log(cv.magnitude(dft_shift[:,:,0],dft_shift[:,:,1]))
plt.subplot(121),plt.imshow(img, cmap = 'gray')
plt.title('Input Image'), plt.xticks([]), plt.yticks([])
plt.subplot(122),plt.imshow(magnitude_spectrum, cmap = 'gray')
plt.title('Magnitude Spectrum'), plt.xticks([]), plt.yticks([])
plt.show()

现在我们要做DFT的逆变换。在上一节中，我们创建了一个HPF，这次我们将看到如何删除图像中的高频内容，即我们将LPF应用到图像中。它实际上模糊了图像。为此，我们首先创建一个高值(1)在低频部分，即我们过滤低频内容，0在高频区。

rows, cols = img.shape
crow,ccol = rows/2 , cols/2
# 首先创建一个掩码，中心正方形为1，其余全为零
mask = np.zeros((rows,cols,2),np.uint8)
mask[crow-30:crow+30, ccol-30:ccol+30] = 1
# 应用掩码和逆DFT
fshift = dft_shift*mask
f_ishift = np.fft.ifftshift(fshift)
img_back = cv.idft(f_ishift)
img_back = cv.magnitude(img_back[:,:,0],img_back[:,:,1])
plt.subplot(121),plt.imshow(img, cmap = 'gray')
plt.title('Input Image'), plt.xticks([]), plt.yticks([])
plt.subplot(122),plt.imshow(img_back, cmap = 'gray')
plt.title('Magnitude Spectrum'), plt.xticks([]), plt.yticks([])
plt.show()

分水岭算法

图像的灰度空间很像地球表面的整个地理结构，每个像素的灰度值代表高度。其中的灰度值较大的像素连成的线可以看做山脊，也就是分水岭。其中的水就是用于二值化的gray threshold level，二值化阈值可以理解为水平面，比水平面低的区域会被淹没，刚开始用水填充每个孤立的山谷(局部最小值)。

当水平面上升到一定高度时，水就会溢出当前山谷，可以通过在分水岭上修大坝，从而避免两个山谷的水汇集，这样图像就被分成2个像素集，一个是被水淹没的山谷像素集，一个是分水岭线像素集。最终这些大坝形成的线就对整个图像进行了分区，实现对图像的分割。

在该算法中，空间上相邻并且灰度值相近的像素被划分为一个区域。

分水岭算法的整个过程：

把梯度图像中的所有像素按照灰度值进行分类，并设定一个测地距离阈值。
找到灰度值最小的像素点（默认标记为灰度值最低点），让threshold从最小值开始增长，这些点为起始点。
水平面在增长的过程中，会碰到周围的邻域像素，测量这些像素到起始点（灰度值最低点）的测地距离，如果小于设定阈值，则将这些像素淹没，否则在这些像素上设置大坝，这样就对这些邻域像素进行了分类。

4. 随着水平面越来越高，会设置更多更高的大坝，直到灰度值的最大值，所有区域都在分水岭线上相遇，这些大坝就对整个图像像素的进行了分区。

用上面的算法对图像进行分水岭运算，由于噪声点或其它因素的干扰，可能会得到密密麻麻的小区域，即图像被分得太细（over-segmented，过度分割），这因为图像中有非常多的局部极小值点，每个点都会自成一个小区域。

其中的解决方法：

对图像进行高斯平滑操作，抹除很多小的最小值，这些小分区就会合并。
不从最小值开始增长，可以将相对较高的灰度值像素作为起始点（需要用户手动标记），从标记处开始进行淹没，则很多小区域都会被合并为一个区域，这被称为基于图像标记(mark)的分水岭算法。

OpenCV中分水岭算法

在OpenCV中，我们需要给不同区域贴上不同的标签。用大于1的整数表示我们确定为前景或对象的区域，用1表示我们确定为背景或非对象的区域，最后用0表示我们无法确定的区域。然后应用分水岭算法，我们的标记图像将被更新，更新后的标记图像的边界像素值为-1。

下面对相互接触的硬币应用距离变换和分水岭分割。

先使用 Otsu’s 二值化对图像进行二值化。

import cv2
import numpy as np

img = cv2.imread('coins.png')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
ret, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)

先使用开运算去除图像中的细小白色噪点，然后通过腐蚀运算移除边界像素，得到的图像中的白色区域肯定是真实前景，即靠近硬币中心的区域（下面左边的图）；膨胀运算使得一部分背景成为了物体到的边界，得到的图像中的黑色区域肯定是真实背景，即远离硬币的区域（下面中间的图）。

剩下的区域（硬币的边界附近）还不能确定是前景还是背景。可通过膨胀图减去腐蚀图得到，下图中的白色部分为不确定区域（下面右边的图）。

# noise removal
kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (3,3))
opening = cv2.morphologyEx(thresh, cv2.MORPH_OPEN, kernel, iterations=2)

sure_bg = cv2.dilate(opening, kernel, iterations=2)  # sure background area
sure_fg = cv2.erode(opening, kernel, iterations=2)  # sure foreground area
unknown = cv2.subtract(sure_bg, sure_fg)  # unknown area

剩下的区域不确定是硬币还是背景，这些区域通常在前景和背景接触的区域(或者两个不同硬币接触的区域)，我们称之为边界。通过分水岭算法应该能找到确定的边界。

由于硬币之间彼此接触，我们使用另一个确定前景的方法，就是带阈值的距离变换。

下面左边的图为得到的距离转换图像，其中每个像素的值为其到最近的背景像素（灰度值为0）的距离，可以看到硬币的中心像素值最大（中心离背景像素最远）。对其进行二值处理就得到了分离的前景图（下面中间的图），白色区域肯定是硬币区域，而且还相互分离，下面右边的图为之前的膨胀图减去中间这个表示前景的图。

# Perform the distance transform algorithm
dist_transform = cv2.distanceTransform(opening, cv2.DIST_L2, 5)
# Normalize the distance image for range = {0.0, 1.0}
cv2.normalize(dist_transform, dist_transform, 0, 1.0, cv2.NORM_MINMAX)

# Finding sure foreground area
ret, sure_fg = cv2.threshold(dist_transform, 0.5*dist_transform.max(), 255, 0)

# Finding unknown region
sure_fg = np.uint8(sure_fg)
unknown = cv2.subtract(sure_bg,sure_fg)

现在我们可以确定哪些是硬币区域，哪些是背景区域。然后创建标记(marker，它是一个与原始图像大小相同的矩阵，int32数据类型)，表示其中的每个区域。分水岭算法将标记的0的区域视为不确定区域，将标记为1的区域视为背景区域，将标记大于1的正整数表示我们想得到的前景。

我们可以使用 cv2.connectedComponents() 来实现这个功能，它是用0标记图像的背景，用大于0的整数标记其他对象。所以我们需要对其进行加一，用1来标记图像的背景。

cv2.connectedComponents() 将传入图像中的白色区域视为组件（前景）。

# Marker labelling
ret, markers = cv2.connectedComponents(sure_fg)
# Add one to all labels so that sure background is not 0, but 1
markers = markers+1
# Now, mark the region of unknown with zero
markers[unknown==255] = 0

注意：得到的markers矩阵的元素类型为 int32，要使用 imshow() 进行显示，需要将其转换为 uint8 类型（ markers=np.uint8(markers) ）。

我们对得到的markers进行显示：

markers_copy = markers.copy()
markers_copy[markers==0] = 150  # 灰色表示背景
markers_copy[markers==1] = 0    # 黑色表示背景
markers_copy[markers>1] = 255   # 白色表示前景

markers_copy = np.uint8(markers_copy)

标记图像已经完成了，最后应用分水岭算法。然后标记图像将被修改，边界区域将被标记为-1。

# 使用分水岭算法执行基于标记的图像分割，将图像中的对象与背景分离
markers = cv2.watershed(img, markers)
img[markers==-1] = [0,0,255]  # 将边界标记为红色

经过分水岭算法得到的新的标记图像和分割后的图像如下图所示：

任何两个相邻连接的组件不一定被分水岭边界(-1的像素)分开；例如在传递给 watershed 函数的初始标记图像中的物体相互接触。

总结

我们通过一个例子介绍了分水岭算法的整个过程，主要分为以下几步：

对图进行灰度化和二值化得到二值图像
通过膨胀得到确定的背景区域，通过距离转换得到确定的前景区域，剩余部分为不确定区域
对确定的前景图像进行连接组件处理，得到标记图像
根据标记图像对原图像应用分水岭算法，更新标记图像

参考：

OpenCV Watershed Algorithm

IMAGE SEGMENTATION AND MATHEMATICAL MORPHOLOGY

Classic Watershed

https://zhuanlan.zhihu.com/p/67741538

图像直方图反向投影

理论

这是由**Michael J. Swain**和**Dana H. Ballard**在他们的论文《通过颜色直方图索引》中提出的。

用简单的话说是什么意思？它用于图像分割或在图像中查找感兴趣的对象。简而言之，它创建的图像大小与输入图像相同（但只有一个通道），其中每个像素对应于该像素属于我们物体的概率。用更简单的话来说，与其余部分相比，输出图像将在可能有对象的区域具有更多的白色值。好吧，这是一个直观的解释。（我无法使其更简单）。直方图反投影与camshift算法等配合使用。

我们该怎么做呢？我们创建一个图像的直方图，其中包含我们感兴趣的对象（在我们的示例中是背景，离开播放器等）。对象应尽可能填充图像以获得更好的效果。而且颜色直方图比灰度直方图更可取，因为对象的颜色对比灰度强度是定义对象的好方法。然后，我们将该直方图“反投影”到需要找到对象的测试图像上，换句话说，我们计算出属于背景的每个像素的概率并将其显示出来。在适当的阈值下产生的输出使我们仅获得背景。

假设我们现在有一个四行四列得灰度图，它得灰度值如下图：

说这幅图有什么特征呢？直观上看类似于一个边角，但这是直观上，怎么表示出来呢？深度学习是靠神经网络黑箱计算出来得，我们可以用直方图。

那我们就计算这幅灰度图得直方图，如果以组距为1计算直方图并反向投影到原图，得到得为下图：

可以大概表述一下边角得特征：左下角有6个像素值相同得三角形区域，中间斜向下有四个像素值相同得边界线，以此类推。这就是用直方图得到得边角得特征。

那如果以组距为2计算直方图呢？反向投影后为：

可以看到特征描述得更为广泛了，就像深度学习里，提取更高层次得特征，虽然更为普适，但也会忽略掉一些细节特征。

我们就是拿这个反向投影所表达得特征信息，去和整幅图做对比，来得到特征相似得部分，达到分割得效果。

为什么要归一化呢，直方图反向投影到原图后，原图各位置表示的是整幅图中等于该点像素值的数量，归一化后就变成概率了。

通过图像的反向投影矩阵，我们实际上把原图像简单化了，简单化的过程实际上就是提取出图像的某个特征。所以以后我们可以用这个特征来对比两幅图，如果两幅图的反向投影矩阵相似或相同，那么我们就可以判定这两幅图这个特征是相同的。

Numpy中的算法

首先，我们需要计算我们要查找的对象（使其为“ M”）和要搜索的图像（使其为“ I”）的颜色直方图。

import numpy as np
import cv2 as cvfrom matplotlib import pyplot as plt
#roi是我们需要找到的对象或对象区域
roi = cv.imread('rose_red.png')
hsv = cv.cvtColor(roi,cv.COLOR_BGR2HSV)
#目标是我们搜索的图像
target = cv.imread('rose.png')
hsvt = cv.cvtColor(target,cv.COLOR_BGR2HSV)
# 使用calcHist查找直方图。也可以使用np.histogram2d完成
M = cv.calcHist([hsv],[0, 1], None, [180, 256], [0, 180, 0, 256] )
I = cv.calcHist([hsvt],[0, 1], None, [180, 256], [0, 180, 0, 256] )

求出比值R=MI。然后反向投影R，即使用R作为调色板，并以每个像素作为其对应的目标概率创建一个新图像。即B(x,y) = R[h(x,y),s(x,y)] 其中h是色调，s是像素在(x，y)的饱和度。之后，应用条件B(x,y)=min[B(x,y),1]。

h,s,v = cv.split(hsvt)
B = R[h.ravel(),s.ravel()]
B = np.minimum(B,1)
B = B.reshape(hsvt.shape[:2])

现在对圆盘应用卷积，B=D∗B，其中D是圆盘内核。

disc = cv.getStructuringElement(cv.MORPH_ELLIPSE,(5,5))
cv.filter2D(B,-1,disc,B)
B = np.uint8(B)
cv.normalize(B,B,0,255,cv.NORM_MINMAX)

现在最大强度的位置给了我们物体的位置。如果我们期望图像中有一个区域，则对合适的值进行阈值处理将获得不错的结果。

ret,thresh = cv.threshold(B,50,255,0)

OpenCV的反投影

OpenCV提供了一个内建的函数**cv.calcBackProject**()。它的参数几乎与**cv.calchist**()函数相同。它的一个参数是直方图，也就是物体的直方图，我们必须找到它。另外，在传递给backproject函数之前，应该对对象直方图进行归一化。它返回概率图像。然后我们用圆盘内核对图像进行卷积并应用阈值。下面是我的代码和结果:

import numpy as np
import cv2 as cv
roi = cv.imread('rose_red.png')
hsv = cv.cvtColor(roi,cv.COLOR_BGR2HSV)
target = cv.imread('rose.png')
hsvt = cv.cvtColor(target,cv.COLOR_BGR2HSV)
# 计算对象的直方图
roihist = cv.calcHist([hsv],[0, 1], None, [180, 256], [0, 180, 0, 256] )
# 直方图归一化并利用反传算法
cv.normalize(roihist,roihist,0,255,cv.NORM_MINMAX)
dst = cv.calcBackProject([hsvt],[0,1],roihist,[0,180,0,256],1)
# 用圆盘进行卷积
disc = cv.getStructuringElement(cv.MORPH_ELLIPSE,(5,5))
cv.filter2D(dst,-1,disc,dst)
# 应用阈值作与操作
ret,thresh = cv.threshold(dst,50,255,0)
thresh = cv.merge((thresh,thresh,thresh))
res = cv.bitwise_and(target,thresh)
res = np.vstack((target,thresh,res))
cv.imwrite('res.jpg',res)

leetcodeday19 –删除链表的倒数第 N 个结点

总结方法：对于链表，一般在链表开头先添加一个头元素，该元素指向链表的第一个元素。

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

一般方法：两次for循环

第一次计算长度，第二次重构链表

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        
        dummy = ListNode(0, head)
        length = getLength(head)
        cur = dummy
        for i in range(1, length - n + 1):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

改进版：

双指针

思路与算法

我们也可以在不预处理出链表的长度，以及使用常数空间的前提下解决本题。由于我们需要找到倒数第n 个节点，因此我们可以使用两个指针first 和 second 同时对链表进行遍历，并且 first 比second 超前 n个节点。当first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。

具体地，初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 n。此时，first 和 second 之间间隔了 n−1 个节点，即 first 比second 超前了 n个节点。

在这之后，我们同时使用 first 和second 对链表进行遍历。当 first 遍历到链表的末尾（即 first 为空指针）时，second 恰好指向倒数第 n 个节点。

根据方法一和方法二，如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点，其余的操作步骤不变。这样一来，当first 遍历到链表的末尾时，second 的下一个节点就是我们需要删除的节点。

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next

复杂度分析

时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度: O(1)。