概述

GBDT全称Gradient Boosting Decision Trees，即梯度提升回归树。GBDT可以拆分2部分：GB+DT。GB是一种通用思想或者算法，GBDT只是众多GBM（Gradient Boosting Machine）里面的一种。所以先来看GB。

Boosting前面已经介绍过了，就是用多个弱学习器顺序迭代生成一个强学习器，GB里面的重点在于每次迭代的时候是拟合残差。所谓残差（residual）就是真实值和预测值的差值： $residual_i = y_i-f(x_i)$，它表示了数据模型中所不可能刻画的部分。所以GB的思想大致可以描述如下：

1. 初始：先有一个初始的弱学习器，然后用这个学习器去训练样本上面进行预测，得到每个样本的残差。
2. 第一轮：用训练样本作为属性，第一轮得到的残差作为target（而不是原始样本的target），训练得到第2个弱学习器。然后用这个弱学习器对样本进行预测得到预测值，并计算与真实值的残差，作为一下轮样本的target。
3. 第N轮：重复前面的步骤。每次变化的是使用上一轮计算的残差作为本轮样本的target。

N次迭代后得到最终的强学习器。所以可以看到GB其实就是不断的迭代拟合残差。但至此并没有看到任何关于Gradient的影子。接着往下看：假设现在有样本集 $(x_1,y_1),(x_2,y_2),...(x_n,y_n)$ ，然后用一个模型$f(x)$去拟合这些数据。如果是回归模型的话，我们一般使用均方误差作为损失函数，即：$L(\theta) = \frac{1}{2}\sum_{i=0}^n(y_i-f(x_i))^2$

然后最优化算法求解模型的参数$\theta$。常用的最优化求解方法之一就是梯度下降（gradient descent）。对损失函数求梯度得到：$\nabla L(\theta) = \sum_{i=0}^n{(f(x_i)-y_i)}$

至此，可以看到我们前面定义的残差就是这里的负梯度：$residual_i = y_i-f(x_i) = -(f(xi)-y_i)$。也就是说前面对残差的拟合，其实就是对负梯度的拟合，而根据残差来更新集成后的模型实际就是根据负梯度来更新。这样来看，梯度提升方法就变成了广义上的梯度下降。这就是GB中Gradient的部分。

需要注意的是：尽管这里残差和负梯度的值完全一样，但二者代表的含义却是不一样的：负梯度指向的是单个模型参数更新的方向，残差（即梯度提升）则表示了集成模型下一个模型的拟合目标。梯度的不断下降可以让模型的参数逐渐收敛到最优参数上，而残差的不断拟合则让集成之后的模型越来越解决真实数据的生成机制。换言之，

• 梯度下降是参数空间的优化：针对单个模型的参数优化，找到最优的一组参数；
• 梯度提升是函数空间的优化：用多个模型的组合来逼近问题的解，每个模型都是一个函数。

有了从残差转换到梯度的思路以后，又可以再继续改进，不再局限于残差，而是可以从损失函数的负梯度角度去构造更丰富的提升方法，即构造更多的损失函数。因为基于残差的损失函数有一个明显的缺点就是对异常值比较敏感。看下面的例子：

上面的例子中，5*是一个异常点。很明显，按照Boosting的思路，后续模型会对这个值关注过多，这不是一个好现象。所以一般回归类的损失函数会使用绝对损失（absolute loss）或者huber损失函数（huber loss）来代替平方损失函数：

如果GB中的弱学习器使用决策树，就是GBDT了。GBDT中一般使用CART决策树。

这便是GBDT算法，整体还是Boosting的思路，但具体到细节又和AdaBoost有明显的差别：AdaBoost中每个弱学习器的短板通过权重的加强得以凸显，而梯度提升中则将权重换成了梯度。

在解决分类问题时，GBDT 中的负梯度可以表示成样本归属于每个类别的真实概率和上一轮预测概率的差值，这个差值会被回归树拟合，拟合值与上一轮预测概率求和就是这一轮的输出。

算法

下图来自Wikipedia：https://en.wikipedia.org/wiki/Gradient_boosting

1. 初始化$F_0(x)$，表示第0棵树的预测值。那怎么初始化呢？取决于所选择的损失函数：

   1. 均方误差（mean square error，MSE）时：$F_0(x)=\bar y，\overline y$ 是样本真实值的平均值
   2. 平均绝对误差（mean absolute error，MAE）：$F_0(x)=median(y)$，即真实值的中位数
   3. Logit时（分类问题）： $F_0(x)=\frac{1}{2}*log\frac{\sum{y_i}}{\sum(1-y_i)}, y_i\in{0, 1}$

2. 假如进行M轮迭代（即M个弱分类器），则对于第m轮（$m=1,2,...,M$）：

   1. 计算上一轮模型的残差（即负梯度）$r_{im}$，即用真实值减去上一轮模型的预测值
   2. 将计算出来的残差作为本轮的target，得到本轮的训练数据：$(x_1, r_{1m}),(x_2, r_{2m}),...,(x_n, r_{nm})$。然后训练得到本轮的弱分类器是$h_m(x)$。
   3. 然后就是求解本轮弱分类器的权重$\gamma_m$了。迭代到本轮为止得到的强分类器为：$F_m(x)=F_{m-1}(x)+\gamma_mh_m(x)$，所以求解$\gamma_m$的方式就是：$\gamma_m = \mathop{\arg\min}\limits_{\theta}\sum_{i=1}^n{L(y_i,F_m(x_i))} = \mathop{\arg\min}\limits_{\theta}\sum_{i=1}^n{L(y_i,F_{m-1}(x_i)+\gamma h_m(x_i))}$
   4. 得到$\gamma_m$之后，本轮迭代之后得到模型就是：$F_m(x)=F_{m-1}(x)+\gamma_mh_m(x)$。
3. 得到最终的模型：$F_M(x)$。

再总结一下关键点：

1. 初始的时候先找一个常量模型$F_0$，计算初始的残差。之所以说是常量模型，是因为一般这个是直接计算的所有样本观测值（target）的“均值”（如果是分类问题的话，一般使用logit），然后样本观测值减去计算出来的“均值”就得到了初始的残差。然后就开始Boosting的迭代，每轮迭代的样本属性就是原始训练样本的属性，但样本观测值不是原始的观测值，而是计算出来的残差。第一轮使用初始算出的残差；第二轮使用第一轮模型预测的到的残差，...，第m轮使用第m-1轮模型预测得到的残差，以此类推。
2. 因为Boosting模型得到的最终强学习器形式为：$F_{strong\ learner}(x) = \sum_{i=1}^M{\gamma_i*h_i(x)} +const_{F_0}$
   其中的$const_{F_0}$就是初始计算的常量“均值”，所以每轮除了使用样本$(x_1, r_{1m}),(x_2, r_{2m}),...,(x_n, r_{nm})$ 训练得到本轮的弱分类器以外，还需要计算本轮弱分类器在最终强分类器中所占的权重$\gamma$，计算方式就是上面计算$\gamma_m$的方法。
3. 需要注意的是每轮训练时的target使用的是残差，而不是原始的target，所以该弱分类器模型后面预测出来的值也是残差，而不是原始样本的target。也即所以上面公式中的$\sum_{i=1}^M{\gamma_i*h_i(x)}$累加起来其实是M个弱分类器预测的“残差和”，需要加上最初始$F_0$算出来的“平均值”才是最终的预测值。

另外还需要说明一个概念：学习率（Learning Rate），背景是这样的：测试表明每次沿正确的方向前进一小步可以获得更好的预测性能，所以设计了一个超参learning rate，用来控制每轮模型的影响。一般会设置的比较小（比如0.1），以此来让模型使用更多的弱分类器。英文版：

It’s been shown through experimentation that taking small incremental steps towards the solution achieves a comparable bias with a lower overall vatiance (a lower variance leads to better accuracy on samples outside of the training data). Thus, to prevent overfitting, we introduce a hyperparameter called learning rate. When we make a prediction, each residual is multiplied by the learning rate. This forces us to use more decision trees, each taking a small step towards the final solution.

上面的算法流程里面没有给出来，但实际迭代的时候还会引入一个学习率$\nu$，完整的迭代公式是这样的：$F_m(x)=F_{m-1}(x)+\nu*\gamma_mH_m(x)$

一幅图表示就是（来自：How XGBoost Works）：

整个介绍起来比较抽象，可参考下面例子中的第一个：Gradient Boosting Decision Tree Algorithm Explained来感受一下整个流程。

例子

1. Gradient Boosting Decision Tree Algorithm Explained： 该例是一个使用GBDT解决回归的问题。见：gbdt-regression-demo.ipynb（参考自: Gradient Boosting Decision Tree Algorithm Explained）。
2. GBDT算法原理以及实例理解
3. Gradient Boosting In Classification: Not a Black Box Anymore!，是一个二分类例子。

XGBoost

概述

XGBoost（eXtreme Gradient Boosting）是对GBDT的优化和工程化的实现。优化可分为算法优化和工程实现方面的优化：

1. Algorithmic Enhancements:

   1. Regularization: It penalizes more complex models through both LASSO (L1) and Ridge (L2) regularization to prevent overfitting.
   2. Sparsity Awareness: XGBoost naturally admits sparse features for inputs by automatically ‘learning’ best missing value depending on training loss and handles different types of sparsity patterns in the data more efficiently.
   3. Weighted Quantile Sketch: XGBoost employs the distributed weighted Quantile Sketch algorithm to effectively find the optimal split points among weighted datasets.
   4. Cross-validation: The algorithm comes with built-in cross-validation method at each iteration, taking away the need to explicitly program this search and to specify the exact number of boosting iterations required in a single run.

2. System Optimization：

   1. Parallelization: XGBoost approaches the process of sequential tree building using parallelized implementation. This is possible due to the interchangeable nature of loops used for building base learners; the outer loop that enumerates the leaf nodes of a tree, and the second inner loop that calculates the features. This nesting of loops limits parallelization because without completing the inner loop (more computationally demanding of the two), the outer loop cannot be started. Therefore, to improve run time, the order of loops is interchanged using initialization through a global scan of all instances and sorting using parallel threads. This switch improves algorithmic performance by offsetting any parallelization overheads in computation.
   2. Tree Pruning: The stopping criterion for tree splitting within GBM framework is greedy in nature and depends on the negative loss criterion at the point of split. XGBoost uses ‘max_depth’ parameter as specified instead of criterion first, and starts pruning trees backward. This ‘depth-first’ approach improves computational performance significantly.

   3. Hardware Optimization: This algorithm has been designed to make efficient use of hardware resources. This is accomplished by cache awareness by allocating internal buffers in each thread to store gradient statistics. Further enhancements such as ‘out-of-core’ computing optimize available disk space while handling big data-frames that do not fit into memory.
      

      以上引用自：XGBoost Algorithm: Long May She Reign!

算法

从算法角度来说，XGBoost主要对GBDT的目标函数进行了优化。GBDT的目标函数：

$Obj_{gbdt} = \sum_{i=1}^N{L(f_m(x_i), y_i)}=\sum_{i=1}^N{L(f_{m-1}(x_i) + h_m(x_i), y_i)}$

而XGBoost对目标函数的优化有两方面：

1. 加了一个正则项；
2. 使用泰勒公式展开。

先看正则项：

$Obj_{xgboost} = \sum_{i=1}^N{L(f_m(x_i), y_i)} + \sum_{j=1}^m{\Omega f(x_j)}=\sum_{i=1}^N{L(f_{m-1}(x_i) + h_m(x_i), y_i) + \sum_{j=1}^m{\Omega f(x_j)}}$

加正则项就是Shrinkage的思想，可以防止过拟合、降低方差，获取更好的泛化效果。这个正则项的具体公式为：

$\Omega f(x_i) = \gamma T + \frac{1}{2}\lambda||\omega||^2$

其中$T$为树$f$的叶节点个数，$\omega$为所有叶节点输出回归值构成的向量，$\gamma,\lambda$为超参数。再看泰勒公式：

更细的部分可参考下面2篇文章：

• 机器学习|XGBoost详解（CSDN）
• XGBooost详解（知乎）

总结

梯度提升算法（Gradient Boosting Machine，GBM）其实是一类算法，GBDT只是其中一种，而XGBoost则是GBDT的一个优化版本（或者说是GBDT算法的一个具体的实现），这个优化不仅体现在算法层面，也包括很多工程实现方面的优化，比如并行、内存使用量少等。同类的还有微软开源的LightGBM，号称速度更快，内存使用更低，网上有很多对比评测文章，有兴趣的可以看看。

理解随机森林的关键点在于理解“相关度低甚至不相关的多个决策树组合在一起的效果好于其中任何一个决策树”。这里拿一个例子做论证（注：此例来自第一个参考文章），做一个游戏：使用一个均匀分布的随机数产生器产生一个数字，如果这个数字大于等于40，则算你赢，可以获得一些钱；如果小于40，则算你输，你需要给对方同样数额的钱。现在有三种玩法供选择：

• 玩法1（Game1）：玩100次，每次的筹码是1元。
• 玩法2（Game2）：玩10次，每次筹码是10元。
• 玩法3（Game3）：玩1次，筹码是100.

你会怎么选哪一个？我们计算一下赢钱的期望值：

• $E_1 = (0.6*1+0.4*(-1))*100=20$
• $E_2=(0.6*10+0.4*(-10))*100=20$
• $E_3=(0.6*100+0.4*(-100))=20$

三种选择赢钱的期望值是一样的，那到底该如何选？我们做一个模拟：每种情况都模拟10000次，代码如下：

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns

sns.set_theme()

# Game 1
simulations = 10000  # number of Monte Carlo Simulations
games = 100          # number of times the game is played
threshold = 40       # threshold where if greater than or equal to you win
bet = 1              # dollar bet for the game

# outer loop is Monte Carlo sims and inner loop is games played
sim_results_1 = []
for sim in range(simulations):
    result = []
    for g in range(games):
        number = int(np.random.uniform()*100)  # get a random number to see who wins
        if number >= threshold:
            result.append(bet)
        else:
            result.append(-bet)
    sim_results_1.append(sum(result))          # sim_results_1 stores results for Game 1
print('Game 1 Mean: ', round(np.mean(sim_results_1), 2))
print('Game 1 Prob Positive: ', round(sum([1 for i in sim_results_1 if i>0])/simulations, 2))
print('\n')
    

# Game 2 (structure of code is same as above)
simulations = 10000
games = 10
threshold = 40
bet = 10

sim_results_2 = []
for sim in range(simulations):
    result = []
    for g in range(games):
        number = int(np.random.uniform()*100)
        if number >= threshold:
            result.append(bet)
        else:
            result.append(-bet)
    sim_results_2.append(sum(result))
print('Game 2 Mean: ', round(np.mean(sim_results_2), 2))
print('Game 2 Prob Positive: ', round(sum([1 for i in sim_results_2 if i>0])/simulations, 2))
print('\n')
    
    
# Game 3 (structure of code is same as above)
simulations = 10000
games = 1
threshold = 40
bet = 100

sim_results_3 = []
for sim in range(simulations):
    result = []
    for g in range(games):
        number = int(np.random.uniform()*100)
        if number >= threshold:
            result.append(bet)
        else:
            result.append(-bet)
    sim_results_3.append(sum(result))
print('Game 3 Mean: ', round(np.mean(sim_results_3), 2))
print('Game 3 Prob Positive: ', round(sum([1 for i in sim_results_3 if i>0])/simulations, 2))

# Histogram that shows the distribution of the Monte Carlo Results for 2 spending levels
fig, ax = plt.subplots(figsize=(8,6))
sns.distplot(sim_results_1, kde=False, bins=60, label='Play 100 Times')
sns.distplot(sim_results_2, kde=False, bins=60, label='Play 10 Times', color='orange')
sns.distplot(sim_results_3, kde=False, bins=60, label='Play 1 Time', color='pink')

ax.set_xlabel('Money Won by You', fontsize=16)
ax.set_ylabel('Frequency',fontsize=16)
plt.legend()
plt.tight_layout()

plt.savefig(fname='game_hist', dpi=150)
plt.show()

模拟的输出以分布图如下：

# 代码输出
Game 1 Mean:  20.01
Game 1 Prob Positive:  0.97

Game 2 Mean:  20.2
Game 2 Prob Positive:  0.63

Game 3 Mean:  21.08
Game 3 Prob Positive:  0.61

那可以看到赢钱的均值和即我们先前计算的期望值是一致的，三种玩法都接近20（Game x Mean），但赢钱的概率却相差很大，玩法1是97%，玩法2是63%，玩法3是61%。当然模拟次数再多一些，还有有一些变化。随机森林的思想和这个是一样的，里面包含的决策树的个数就是这里玩的次数。

另外，随机森林还有一个非常关键的限定条件：各个决策树之间不相关或者关联度很低。类比到上面的游戏中，我们的假设是产生随机数的算法是遵从均匀分布的，也就是产生1~100之间的数字的概率是完全相等的。如果不是，那上面第一种玩法1最优的结论就不一定成立了。而随机森林实现各个决策树之间不相关或者关联度很低是通过“两个随机”实现的：

1. 数据随机：即每次只选取原始数据集的一个子集作为一个决策树的训练集，一般就是自助采样法（Bootstrap）。这是最核心的随机，主要是去除或者削弱各独立模型之间的相关性。
2. 属性随机：属性随机化的好处在于让每个单独的基学习器不会过分关注在训练集中具有高度预测性或者描述性的特征。

通过两个随机，可以降低最终生成的模型的方差。而且通过这种方式生成的树一般也无需剪枝。Wikipedia上面的描述是这样的：

Each decision tree in the forest considers a random subset of features when forming questions and only has access to a random set of the training data points. This increases diversity in the forest leading to more robust overall predictions and the name ‘random forest.’

随机森林还有一个变种：Extra Trees。也称Extremely Randomized Trees，一般翻译为极限树，是随机森林的一个变种，进行了更彻底的随机，主要有两点：

1. 训练各个决策树的时候使用全部数据集，而非一个采样的数据子集；
2. 在选择决策树的拆分点的时候，均匀随机选择一个特征，而不是像随机森林那样根据信息增益或者基尼不纯度进行选择。

极限树的两个改动点在大部分情况下会进一步的降低方差，但可能会稍微增大一些偏差。

总结一下，随机森林的思路就是“群众的眼睛是雪亮的”，通过使用多个决策树组成一个“委员会”来进行预测或者回归，这些“群众”就是集成算法中的“若分类器”，他们相互之间没有关联度或者关联度低，而且一般在某一个点表现还可以。这点是通过“两个随机”去实现的，也是随机森林最核心的地方。

References：

• Understanding Random Forest
• Wikipedia：Random Forest

AdaBoost是Adaptive Boosting的缩写，即自适应提升法，是最成功的Boosting算法。具体算法如下：

Step1: Initialise the dataset and assign equal weight to each of the data point.
Step2: Provide this as input to the model and identify the wrongly classified data points.
Step3: Increase the weight of the wrongly classified data points.
Step4: if (got required results)
            Goto step 5
        else
            Goto step 2 
Step5: End

即初始的时候，赋予每个训练样本相同的权重；然后每次迭代后，增加分类错误样本的权重（数据集还是原来的数据集，只不过各个样本的权重变了），使得下一轮迭代时更加关注这些样本。

AdaBoost一般选用决策树桩（decision stump）作为弱学习器。所谓stump是指由一个决策节点和两个叶子节点组成的二叉树：

下图是一个二分类问题的学习过程示例，包含了三轮迭代：

算法

AdaBoost的算法描述如下：

下面进行解释。

1. “输入”（Given）部分：输入训练数据集包含m个样本，其中$x_i$是属性，取值范围属于集合$X$(实数集的子集)，$y_i$是标签，取值是-1或+1.
2. “初始化”（Initialize）部分：$D$表示带权重的样本（有时也用$w$表示），$D_i$表示第$i$个权重的样本。刚开始的时候，所有样本权重相同为$D_i = 1/m$.

3. 然后开始循环：

   1. 使用权值分布为$D_t$的数据集，训练得到一个弱分类器$h_t$
   2. 计算$h_t$在训练数据上面的误差$\varepsilon_t$
   3. 根据训练误差$\varepsilon_t$计算出权重调整系数$\alpha_t$
   4. 更新所有训练样本的权重，用于下一次迭代
   5. 当训练误差比较低（比如错误率为0）或者弱分类器数目达到预先的设置值（超参控制），就停止循环
4. 最终的分类器就是各个各个弱分类器的加权求和，如果是分类问题，就再加上符号函数$sign$（输入数据大于0，输出1；等于0，输出0；小于0，输出-1）.

如何计算训练误差$\varepsilon_t$？公式如下：

$$ \varepsilon_t = \frac {\sum_{i=1}^N\omega_iI(y_i \neq h_t(x_i))}{\sum_{i=1}^N\omega_i} $$

其中$I(y_i \neq h_j(x_i))$的含义是如果$y_i \neq h_j(x_i)$ 成立，则返回1，否则返回0。下面看个具体的计算例子：

• 有4个样本的权重分别为：0.5，0.2，0.1，0.2，
• 弱分类器预测的值分别为：1，1，-1，-1
• 实际的真实值为：-1，1，-1，1
• 则$I$的值分别为：1，0，0，1

于是有

$$ \varepsilon_t = \frac{0.5*1+0.2*0+0.1*0+0.2*1}{0.5+0.2+0.1+0.2} = 0.7 $$

有时也称$\varepsilon_t$为“total error”表示的是“所有错误分类的样本权重之和”，其实和上面的公式是一致的，因为权重一般是做过归一化的，所以分母里面的所有权重之和其实为1；而且分子中分类正确的样本的$I$值为0，也就是上面的公式可以简化为：

$$ \varepsilon_t = \frac {\sum_{i=1}^N\omega_iI(y_i \neq h_t(x_i))}{\sum_{i=1}^N\omega_i} \\ = \sum_{i=1}^N\omega_iI(y_i \neq h_t(x_i)) = 错误分类样本的权重之和 = total\ error $$

那权重调整系数$\alpha_t$的作用是什么呢？看个具体的例子。假设现在有3个$\varepsilon$值：0.3、0.5、0.7。则对应的$\alpha$的值如下：

$$ \alpha(\varepsilon=0.3) = \frac{1}{2}*ln\frac{1-0.3}{0.3} = 0.42365 \\ \alpha(\varepsilon=0.5) = \frac{1}{2}*ln\frac{1-0.5}{0.5} = 0 \\ \alpha(\varepsilon=0.7) = \frac{1}{2}*ln\frac{1-0.7}{0.7} = -0.42365 \\ $$

可以看到，当弱分类器的准确率为0.5时，其权重为0；准确率大于0.5（即错误率小于0.5）时，权重大于0；准确率小于0.5（即错误率大于0.5）时，权重小于0。所以，错误率$\varepsilon$越小，$\alpha$越大，即当前模型的表现越好，在最终的生成器中占的权重就越大。所以$\alpha$也称为“amount of say”、“Performance”、“Importance”，都指的是当前分类器在最终分类器中的权重。另外注意计算的时候有时使用自然对数（$ln=log_e$），有时使用常用对数（$log_{10}$）。

再来看最重要的部分：样本权重更新。在Boosting的迭代中，我们每次要找的是错误率比较低的弱分类器。为了方便我们沿用上面$\alpha(\varepsilon=0.3)$的计算结果，看下分类错误和正确时计算出来的权重值：

• 当在样本$i$上预测正确（即$y_i = h_t(i)$），训练误差为0.3时，计算的新的权重如下：
• 当在样本$i$上预测错误（即$y_i \neq h_t(i)$），训练误差为0.3时，计算的新的权重如下：
  

可以看到当弱分类器在某个样本上分类正确的时候，该样本的权重会降低；否则就会提升，符合理论预期。最后提一下$Z_t$，这是一个规范化系数（normalization factor ），是为了让新计算出来的权重代表一个真正的分布，一般就是归一化。比如上面的例子所有样本的权重更新后加起来后做一下归一化。上面的公式可以简化一下：

• 对于分类正确的样本：$D_{t+1}(i)=\frac{D_t*e^{-\alpha_t}}{Z_t}$
• 对于分类错误的样本：$D_{t+1}(i)=\frac{D_t*e^{\alpha_t}}{Z_t}$

最后一个问题，增加了预测错误的样本的权重之后，如何在下一轮迭代中更关注他们呢？实质是通过权重影响每一轮迭代数据集的选择来实现：比如我们有一个包含N个样本的数据集，每个样本都有一个权重（第一轮时权重相同，均为1/N），然后每一轮选择本轮使用的$m(m \le N)$个样本时，是根据权重随机采样的。也就是有些样本可能会被选择多次，有的可能一次也不会被选中。特别是当样本的权重被更新后，权重大的样本就更容易被选中，甚至选中多次了。这样这些样本自然会对后面的弱分类器产生比较多的影响。比如Pandas的sample方法就可以实现在一个数据集上面按照权重采样。

另外，还有一种“Bucket”的方式，思路如下：原来有N个样本，每次选N个样本进行弱学习器的训练。第一轮大家权重一样，第二轮的时候，根据权重先将原数据集划分“Bucket”，权重高的样本会占据多个bucket。而每个bucket被选中的几率是一样的，所以权重高的样本就可能被多选几次。也就是第二轮的时候虽然还是N个样本，但某些权重低的可能没有被选，某些权重高的样本可能被选了多次。比如下面的例子（N=5，ref：AdaBoost Algorithm – A Complete Guide for Beginners）:

第一轮，所有样本权重一样，可以理解为每个样本就是一个bucket：

第一轮结束的时候，各个样本的权重已经发生了变化（假设第4条数据分错了，它的权重提升了）：

如上图，按照权重重新划分了数据集的bucket，分错的第2个样本占了比较多的bucket。所以在为第二轮迭代选择样本的时候，第4条被选中的概率就会比较大。比如算法随机的5个bucket是：0.38,0.26,0.98,0.40,0.55。那选出的样本就是下图：

可以看到，样本4在第二轮出现了3次，这样后面的分类器必然会对该样本倾斜。

上面的第一种情况其实是后面bucket这种方式的一种特殊情况。所以，需要注意的是，每轮迭代改变了样本的权重后，对下一轮的影响是体现在挑选数据集的时候。当数据集选好后，这些数据集又会被赋予相同的权重，开始新一轮的迭代。后续不断按此方式迭代，直到错误率降到某个阈值或者达到预设的迭代次数。

例子

下面看两个例子，第一个偏理论，第二个偏实现，都有助于理解整个算法的流程和内在逻辑。

A Mathematical Explanation of AdaBoost in 5 Minutes

该例引用自：A Mathematical Explanation of AdaBoost in 5 Minutes。

如下图：有一个包含6个样本的数据集，共3个属性：x1，x2，x3，输出为Y。其中T代表True，F代表False。

Step1：初始化，给每个样本赋予相同的权重，即1/6：

Step2：使用上面的数据生成弱学习器stump：分别计算各个属性的基尼不纯度（gini impurity）。

$$ Gini\ Impurity = 1- Pr_{true}^2-Pr_{false}^2 $$

这里以$x_2$属性为例进行计算：

$$ Total \ Impurity(x_2) = 0.375*(\frac{1+3}{6})+0*(\frac{2+0}{6}) = 0.25 $$

同理可以计算出$x_1$和$x_3$的不纯度为：

$$ Total\ Impurity(x_1)=(1-(\frac{2}{2+2})^2-(\frac{2}{2+2})^2)*(\frac{2+2}{6}) \\ + (1-(\frac{1}{1+0})^2-(\frac{0}{1+0})^2)*(\frac{1+0}{6}) \\ = 0.33 \\ \\ Total\ Impurity(x_3)=(1-(\frac{0}{0+1})^2-(\frac{1}{0+1})^2)*(\frac{0+1}{6}) \\ + (1-(\frac{3}{3+2})^2-(\frac{2}{3+2})^2)*(\frac{3+2}{6}) \\ = 0.4 $$

可以看到$x_2$的基尼不纯度最低，所以使用它生成第一个stump。

Step3：计算“amount of say”。使用x2属性生成的stump会将第1个样本分错，其它都正确。这样的话total error就是1/6。所以：

$$ Amount\ of\ say = \frac{1}{2}*log{\frac{1-\frac{1}{6}}{\frac{1}{6}}} = 0.35 $$

Step4：计算下一个弱分类器（stump）的样本权重。

• 分类错误的样本新权重 $w_{incorrect} = \frac{1}{6}* e^{0.35} = 0.24$
• 分类正确的样本新权重 $w_{correct} = \frac{1}{6}* e^{-0.35} = 0.12$

然后归一化得到下一个stump（即下一轮迭代）的样本及权重，如下图：

这样第一轮就结束了。第二轮迭代开始之前，要先根据样本权重选取训练数据，比如选择的样本可能如下（可以看到第一轮分类错误的样本这次被选了3次）：

然后，将选中的样本权重初始化为相等的值，继续重复前面的过程：

直到训练误差足够小，或者弱分类器个数达到限制，则迭代终止。对所有弱分类器加权求和得到最终的强分类器。

Implementing the AdaBoost Algorithm From Scratch

上面的例子比较偏理论性，这个例子则是具体到代码实现层面的，限于篇幅和格式，就不在文章里面贴了。具体可以参见我的Github: implement-adaboost-from-scratch.ipynb。里面会根据上面的算法实现一个AdaBoost，并且最终和scikit-learn的AdaBoostClassifier做对比。
​
该例参考自：Implementing the AdaBoost Algorithm From Scratch

总结

AdaBoost算法的思想还是比较简单的，算法也容易理解，主要需要理解下面几个关键点：

• 如何计算训练误差$\varepsilon_t$
• 理解权重调整系数$\alpha_t$的作用
• 样本权重是如何更新的，又是如何影响到下一轮迭代的

掌握了这些，在做模型的调优以及一些超参设置上也就可以游刃有余了。

决策树是一个非常简单的算法，至少其思想是非常简单的。生活中我们经常会使用，看几个例子。
场景1，母亲给女儿介绍男朋友，下面是二人的对话：

女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。

女儿通过年龄、长相、收入、是否是公务员将男人分为两个类别：见和不见。女孩选择见或不见的过程就是决策树决策的过程。假设女孩对男朋友的要求是：30岁以下、长相中等以上、高收入者或者中等收入以上的公务员。我们可以构造如下一个决策树：

其中，绿色节点表示判断条件，蓝色节点（叶子节点）表示决策结果，左右箭头称作分支。过去的专家系统往往就使用决策树。

再看一个例子，平面上有一些点，我们需要找到一个函数（曲线）把它们分开。如果是线性可分的情况，直觉上我们会画一条直线来切分平面，它的方程与x,y两个属性均有关，可以表示为：

而对于决策树，通常每次决策（平面划分）只与一个特征相关（x或y）。也就是说，我们只能画水平或竖直的线：

决策树同样适用于线性不可分的情况（并非最优划分）：

接下来，我们使用下面的数据集看下构造决策树的一些关键点。该数据集有2个特征：f1和f2，然后label是是否属于鱼类，共5条样本：

如何构造根据f1、f2两个特征判断是否属于鱼类的决策树？下面是2种可能的决策树：

哪个更好？为什么？构造决策树时，需要确定在哪个特征/属性上面划分数据集，我们称该属性为分裂属性。如何确定分裂属性？

大原则：划分后，让无序数据变得更加有序。

那如何评估数据的有序程度呢？有两种：信息增益（Information Gain）和基尼不纯度（Gini Impurity）。

我们平时说“xxx事情包含的信息量很大”，直观感受就是这个事情的不确定性很大。其实有专门一门学科是专门研究信息的：信息论（这个课还是我大学时的专业课，当时觉得太理论，没什么意思，现在...唉）。这个学科的创始人香农（Claude Elwood Shannon）提出了量化一个系统包含信息量多少的概念——熵（Entropy），单位是比特（bit），它衡量的是随机变量的不确定性。其定义如下：

如果有一个系统S内存在多个事件$S = {E_1,...,E_n}$，每个事件的概率分布$P = {p_1, ..., p_n}$，则每个事件本身的信息为（单位是bit）：$I_e=-log_2p_i$。
​

熵是信息的期望值，即整个系统的平均信息量：$H_s=\sum_{i=1}^n{p_iI_e}=-\sum_{i=1}^np_i{log_2p_i}$

举个例子，比如英语有26个字母，如果每个字母在文章中出现的次数均等的话，则在这篇文章中每个字母的信息量为：$I_e=-log_2\frac1{26}=4.7$。整个文章的熵为：$H_s=\sum_{i=1}^{26}\frac{1}{26}*4.7=\frac{1}{26}*4.7*26=4.7$。因为这里假设每个事件发生概率一样，所以单个事件信息量就等于整个系统的平均信息量。所以，熵描述的其实是随机变量的不确定性。对于确定的系统，熵为0。

那什么是信息增益？这就涉及到条件熵的概念：条件熵——在一个条件下，随机变量的不确定性。而信息增益就是“熵 - 条件熵”。表示在一个条件下，信息不确定性减少的程度。放到决策树这里，就是当选用某个特征划分数据集，系统前后信息发生的变化。计算公式为：$Gain_{split}=H(p)-\sum_{i=1}^k\frac{n_i}{n}H(i)$。即使用某个特征（split）划分数据集以后，得到的信息增益为划分前数据集的熵减去划分后的数据集的熵。下面以前面的鱼类为例，看具体如何计算：

划分前整个数据集为：{是，是，否，否，否} ，对应的熵为：$H=-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.97$

如果使用特征f1划分数据集，得到两个数据子集：

• f1=是，S1：{是，是，否}，对应的熵为：$H_{f1=是}=-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3}=0.92$
• f1=否：S2：{否，否}，对应的熵为：$H_{f1=否}=-1log_21=0$​

​所以，按f1划分后获得的信息增益为：

$$ Gain_{f1}=H-(\frac{3}{5}H_{f1=是}+\frac{2}{5}H_{f1=否})=0.97-\frac{3}{5}*0.92-\frac{2}{5}*0=0.42 $$

同理，可以计算按照f2划分数据集以后得到的信息增益为：

$$ Gain_{f2}=H-(\frac{4}{5}H_{f1=是}+\frac{1}{5}H_{f1=否})=0.97-\frac{4}{5}*1-\frac{1}{5}*0=0.17 $$

通过对比，使用f1划分数据集，获得的信息增益大于使用f2划分，也就是使用f1划分使得系统的不确定性下降的更多，所以使用f1优于f2.

除了信息增益，还有一种常用的评价标准——基尼不纯度（Gini Impurity）：将来自集合中的某种结果随机应用于集合中某一数据项的预期误差率。英文定义是这样的：

Gini impurity (named after Italian mathematician Corrado Gini) is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset.

英文的定义其实更好理解一些，就是你随机从一个集合里面选择一个元素，然后根据这个集合的分布情况随机给这个数据选择一个类别，选择错误可能性的一个描述。维基百科给的计算公式如下：

其中$p_i$是选中第$i$个样本的概率。根据公式可以看到，基尼不纯度的取值范围是[0, 1)。当一个集合完全去定，即里面只有一种元素，则基尼不纯度为0，因为你随机选一个样本，再随机猜一个类别，肯定是不会错的，因为集合里面就只有一种样本；如果一个集合里面全是不同的元素（即混乱程度比较高），则基尼不纯度趋于1，也好理解，你随机选一个样本，随便猜一个种类，因为每个样本都不一样，当n趋于无穷大的时候，猜对的概率几乎为0。所以，不管是信息熵，还是基尼不纯度，衡量的都是一个集合的混乱程度。值越大，越混乱，包含的信息量也越大。对于决策树，使用基尼不纯度和熵的差别非常小：

• 熵对于混乱集合的惩罚略重于基尼不纯度；
• 熵的计算量略大于基尼不纯度。

以二分决策为例，此时p1+p2=1，因此：

对应的曲线图如下：

有了树的划分标准以后，就是根据特征进行递归划分数据集，满足下面任一条件，递归结束：

• 遍历完所有划分数据集的属性
• 每个分支下的所有实例都具有相同的分类

如果遍历完所有属性，类标签仍不唯一，一般采用多数表决的方法决定该叶子节点的分类。

决策树的一个缺点在于很容易过拟合，一般通过剪枝操作来解决改问题，根据剪枝的时机分为两种：

• 预剪枝(prepruning)：在这种方法中，树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长。为了做到这一点，需要采用更具有限制性的结束条件，例如，当观察到的不纯性度量的增益（或估计的泛化误差的改进）低于某个确定的阈值时就停止扩展叶节点。这种方法的优点在于避免产生过分拟合训练数据的过于复杂的子树。然而，很难为提前终止选取正确的阈值。阈值太高将导致拟合不足的模型，而阈值太低就不能充分的解决过拟合的问题。此外，即便使用已有的属性得不到显著的增益，接下来的划分也可能产生较好的子树。

• 后剪枝(postpruning)：在该方法中，初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树。修剪有两种方法：

  • 用新的叶节点替换子树，该叶节点的类标号由子树下记录中的多数类确定。
  • 用子树中最常使用的分支代替子树。当模型不能再改进时终止剪枝步骤。

两种方法各有优劣：与先剪枝相比，后剪枝倾向于产生更好的结果，因为不像先剪枝，后剪枝是根据完全增长的决策树做出的剪枝决策，先剪枝则可能过早终止了决策树的生长。然而，对于后剪枝，当子树被剪掉后，生长完全决策树的额外计算就被浪费了。

目前常见的决策树算法有：

• ID3 (Iterative Dichotomiser 3) ：该算法只能处理标称型数据集。我们之前构造决策树中使用的方法就是ID3算法，该算法使用信息增益作为分裂特征选取的标准。ID3算法可以归纳为以下几点：

  • 使用所有没有使用的属性并计算与之相关的样本熵值
  • 选取其中熵值最小的属性
  • 生成包含该属性的节点

• C4.5：ID3的优化版本，主要有两个优化点：

  • 不仅可以处理标称型数据，还可以处理数值型数据。
  • 使用信息增益率而不是信息增益，改善了分裂特征偏向于具有大量值属性的问题。
• C5.0：C4.5的优化版本，更高效且内存占用更小，但注册了专利，所以使用的比较少。
• CART(Classification and Regression Trees)：CART算法采用一种二分递归分割的技术，算法总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶结点都只有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树。CART算法适用于样本特征的取值为是或非的场景，对于连续特征的处理则与C4.5算法相似。scikit-learn里面使用的就是优化过的CART算法。

其中除了CART使用基尼不纯度外，前面集中都是用的是信息增益作为选择分类属性的标准。下面看scikit-learn中决策树的一个例子：

from sklearn.datasets import load_iris
from sklearn import tree
import graphviz

iris = load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)

dot_data = tree.export_graphviz(clf, out_file=None,
                         feature_names=iris.feature_names,
                         class_names=iris.target_names,
                         filled=True, rounded=True,
                         special_characters=True)
graph = graphviz.Source(dot_data)
graph.render("iris")

上面的代码生成的决策树如下：

目前已经很少有单独使用决策树作为最终算法模型的场景了，一般都会选取基于决策树的更好的集成算法。下面是决策树大致发展过程的一个概括：

后面的文章会介绍这些集成算法。

refs：

• Wikipedia: Decision tree learning
• http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
• http://www.jiarui-blog.com/2017/08/10/决策树-1/
• http://www.jiarui-blog.com/2017/08/28/decision-tree-2/
• https://github.com/MangoLiu/mangoliu.github.io/blob/master/机器学习_决策树.md

最近准备整理一下之前关于集成学习的学习笔记，写一个关于集成学习的系列文章，毕竟目前用的比较多的机器学习算法基本都属于集成学习，整理一下，也算温习一下。有些笔记时间比较久了，里面的一些引用来源找不到了，所以有些引用可能附不全，敬请谅解。目前确定的几篇包括：

• 集成学习介绍（1）——Boosting && Bagging
• 集成学习介绍（2）——AdaBoost
• 集成学习介绍（3）——Random Forests
• 集成学习介绍（4）——GBDT
• 集成学习介绍（5）——XGBoost
• 后续待定...

后面可能会根据时间补充一下其它一些现在也比较流行的算法，比如LightGBM。
本文是第一篇。

集成学习（ensemble learning）是将多个基学习器（base learners）进行集成，得到比每个单独基学习器更优的强学习器（strong learner）的方法。每个用于集成的基学习器都是弱学习器（weak learner），即性能只比随机猜测好一点点或只在某些方面表现好一点的学习器（classifiers that produce prediction that is slightly better than random guessing）。
​
那如何保证多个弱学习器集成在一起会变的更好，而不是更差呢？即如何实现“1+1>2”的效果呢？这对弱学习器提出了一些要求：

1. 弱学习器的性能要有一定的保证，至少在某个方面要表现比较好。
2. 弱学习器的性能要有一定的差异，即擅长点要有所区分，这样组合后才能集百家之所长。

根据训练数据使用方法的不同，集成学习可以分为三种：

• 提升法（Boosting）：各弱学习器之间存在强依赖关系而必须串行生成的序列化方法，各个弱学习器在最终的强学习器中权重不同；
• 装袋法（Bagging）：各弱学习器之间不存在强依赖关系因而可以同时生成的并行化方法，各个弱学习器在最终的强学习器中权重相同；
• 堆叠法（Stacking）：融合提升法和装袋法的一种集成。

注意：

1. 集成学习属于机器学习，但它只是一种训练思路，而不是某种具体的算法。一般把他划归到元学习（meta learning）：关于学习的学习。
2. Boosting/Bagging的所使用的弱学习器一般是同类型的。

Boosting

提升法的是通过改变训练数据的权重（或概率分布）来训练不同的弱分类器，然后组合为强分类器。下面是两个示意图：

Boosting的重点在于取新模型之长补旧模型之短来降低偏差（bias），尽可能获得无偏估计。

Bagging

Bagging是Bootstrap Aggregation的缩写。Bootstrap也称为自助法，是一种有放回抽样方法。Bagging的的基本思想是对训练数据进行有放回抽样，每次抽样数据就训练一个模型，最终在这些模型上面取平均。具体算法如下：

• Step 1: Multiple subsets are created from the original data set with equal tuples, selecting observations with replacement.
• Step 2: A base model is created on each of these subsets.
• Step 3: Each model is learned in parallel from each training set and independent of each other.
• Step 4: The final predictions are determined by combining the predictions from all the models.

下面是一个示意图：

Bagging可以降低模型算法的方差，但并没有降低偏差的效果，所以也就没法提升预测的准确性，所以在选择弱分类器时要尽量选择偏差小的。​

为什么Bagging能降低模型的方差？因为“如果对N个相互独立且方差相同的高斯分布取平均值，新分布的方差就会变成原始方差的 $1/N$”。Bagging采用独立有放回抽样得到N份数据，并训练得到N个模型，预测的时候最终会取这N个结果的平均（分类的话是取多数），这样就可以降低方差。

对比

下面对Boosting和Bagging做了一些对比：

Stacking

除了提升法和装袋法之外，另一种知名度较低的集成方法是堆叠法。堆叠法（stacking）也叫堆叠泛化（stacked generalization），是层次化的集成方法，其思想和神经网络类似，只不过神经网络堆叠的对象是神经元和隐藏层，而集成方法堆叠的是同构或者异构的基学习器。
​

堆叠法先要用自助采样生成不同的数据子集，用数据子集训练第一层中不同的基学习器。第一层基学习器的输出再被送到第二层的元分类器（meta classifier）中作为输入，用来训练元分类器的参数。
​

堆叠法的思想和前两种方法有所不同。无论是提升法还是装袋法，其重点都落在单个模型的生成方式上，也就是如何训练出合适的基学习器，基学习器的形式一般是统一的。而堆叠法的重点在于如何将不同的基学习器的结果组合起来，研究的对象是让所有基学习器共同发挥出最大效果的组合策略。某种意义上说，堆叠法的训练数据不是原始的训练数据集，而是不同基学习器在训练数据集上的结果，起到的是模型平均（model averaging）的作用，提升法和装袋法都可以看成它的特例。正因如此，堆叠法除了被视为集成方法外，还可以看成是模型选择的一个手段。

以上这段摘自极客时间《机器学习40讲专栏》
​

关于偏差和方差

最后补充介绍一下偏差和方差这两个重要的概念。

一个机器学习模型的误差可分为两类：

• 经验误差（empirical error）：又称训练误差（training error），指模型在训练集上面的误差；
• 泛化误差（generalization error）：模型在测试集上面的误差。

其中泛化误差又可以分为三部分：

• 偏差（bias）：表示算法预测值与真实值之间的偏离程度，刻画的是模型的欠拟合（under-fitting）特性。偏差大，说明模型欠拟合。
• 方差（variance）：表示数据扰动对预测性能的影响，刻画的是模型过拟合（over-fitting）特性。方差大，说明模型过拟合。
• 噪声（noise）：表示在当前学习任务上所能达到的最小泛化误差，刻画的是任务本身的难度。

用公式可表示为：

$$ generalization\_error = bias^2 + variance + noise $$

一般很难做到同时将偏差和方差都降到很低，只能在二者之间做权衡。下图中，靶心的红色是是预测正确的值，越往外，预测结果越差。四个图分别描述了误差和方差的高低情况：

上图来自：Understanding the Bias-Variance Tradeoff一文，关于偏差和方差的更多细节，也可以参考这篇文章。

准备模型

首先从这里下载已经训练好的模型文件：

• deploy.prototxt：神经网络结构的描述文件
• mobilenet_iter_73000.caffemodel：神经网络的参数信息

这个模型是使用Caffe实现的Google MobileNet SSD检测模型。有个Caffe Zoo项目，收集了很多已经训练好的模型，有兴趣的可以看一下。下载好模型之后，在app/src/main/下面创建一个assets目录，把两个模型文件放进去。至此，模型的准备工作就完成了。

编写代码

布局文件activity_main.xml：

<?xml version="1.0" encoding="utf-8"?>
<androidx.constraintlayout.widget.ConstraintLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    tools:context=".MainActivity">

    <Button
        android:id="@+id/imageSelect"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_marginStart="32dp"
        android:layout_marginLeft="32dp"
        android:layout_marginTop="16dp"
        android:text="@string/image_select"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toTopOf="parent" />

    <Button
        android:id="@+id/recognize"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_marginStart="16dp"
        android:layout_marginLeft="16dp"
        android:layout_marginTop="16dp"
        android:text="@string/recognize"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintStart_toEndOf="@+id/imageSelect"
        app:layout_constraintTop_toTopOf="parent" />

    <ImageView
        android:id="@+id/imageView"
        android:layout_width="387dp"
        android:layout_height="259dp"
        android:layout_marginStart="8dp"
        android:layout_marginLeft="8dp"
        android:layout_marginTop="22dp"
        android:layout_marginEnd="8dp"
        android:layout_marginRight="8dp"
        android:contentDescription="images"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toBottomOf="@+id/imageSelect" />


</androidx.constraintlayout.widget.ConstraintLayout>

刚接触安卓开发没几天，布局是瞎写的，仅考虑了功能。

MainActivity.java代码：

package com.niyanchun.demo;

import androidx.annotation.Nullable;
import androidx.appcompat.app.AppCompatActivity;

import android.annotation.SuppressLint;
import android.content.Context;
import android.content.Intent;
import android.content.res.AssetManager;
import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.net.Uri;
import android.os.Bundle;
import android.util.Log;
import android.widget.Button;
import android.widget.EditText;
import android.widget.ImageView;
import android.widget.TextView;
import android.widget.Toast;

import org.opencv.android.OpenCVLoader;
import org.opencv.android.Utils;
import org.opencv.core.Core;
import org.opencv.core.Mat;
import org.opencv.core.Point;
import org.opencv.core.Scalar;
import org.opencv.core.Size;
import org.opencv.dnn.Dnn;
import org.opencv.dnn.Net;
import org.opencv.imgproc.Imgproc;

import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;

@SuppressLint("SetTextI18n")
public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        if (OpenCVLoader.initDebug()) {
            Log.i("CV", "load OpenCV Library Successful.");
        } else {
            Log.i("CV", "load OpenCV Library Failed.");
        }

        imageView = findViewById(R.id.imageView);
        imageView.setScaleType(ImageView.ScaleType.FIT_CENTER);
        Button selectBtn = findViewById(R.id.imageSelect);
        selectBtn.setOnClickListener(v -> {
            Intent intent = new Intent();
            intent.setType("image/*");
            intent.setAction(Intent.ACTION_GET_CONTENT);
            startActivityForResult(Intent.createChooser(intent, "选择图片"), PICK_IMAGE_REQUEST);
        });

        Button recognizeBtn = findViewById(R.id.recognize);
        recognizeBtn.setOnClickListener(v -> {
            // 确保加载完成
            if (net == null) {
                Toast.makeText(this, "正在加载模型，请稍后...", Toast.LENGTH_LONG).show();
                while (net == null) {
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
            recognize();
        });
    }

    @Override
    protected void onResume() {
        super.onResume();
        loadModel();
    }

    @Override
    protected void onActivityResult(int requestCode, int resultCode, @Nullable Intent data) {
        super.onActivityResult(requestCode, resultCode, data);

        if (requestCode == PICK_IMAGE_REQUEST && resultCode == RESULT_OK
                && data != null && data.getData() != null) {
            Uri uri = data.getData();
            try {
                Log.d("image-decode", "start to decode selected image now...");
                InputStream input = getContentResolver().openInputStream(uri);
                BitmapFactory.Options options = new BitmapFactory.Options();
                options.inJustDecodeBounds = true;
                BitmapFactory.decodeStream(input, null, options);
                int rawWidth = options.outWidth;
                int rawHeight = options.outHeight;
                int max = Math.max(rawWidth, rawHeight);
                int newWidth, newHeight;
                float inSampleSize = 1.0f;
                if (max > MAX_SIZE) {
                    newWidth = rawWidth / 2;
                    newHeight = rawHeight / 2;
                    while ((newWidth / inSampleSize) > MAX_SIZE || (newHeight / inSampleSize) > MAX_SIZE) {
                        inSampleSize *= 2;
                    }
                }

                options.inSampleSize = (int) inSampleSize;
                options.inJustDecodeBounds = false;
                options.inPreferredConfig = Bitmap.Config.ARGB_8888;

                image = BitmapFactory.decodeStream(getContentResolver().openInputStream(uri), null, options);
                imageView.setImageBitmap(image);
            } catch (Exception e) {
                Log.e("image-decode", "decode image error", e);
            }
        }
    }

    /**
     * 加载模型
     */
    private void loadModel() {
        if (net == null) {
            Toast.makeText(this, "开始加载模型...", Toast.LENGTH_LONG).show();
            String proto = getPath("MobileNetSSD_deploy.prototxt", this);
            String weights = getPath("mobilenet_iter_73000.caffemodel", this);
            net = Dnn.readNetFromCaffe(proto, weights);
            Log.i("model", "load model successfully.");
            Toast.makeText(this, "模型加载成功!", Toast.LENGTH_LONG).show();
        }
    }


    /**
     * 识别
     */
    private void recognize() {
        // 该网络的输入层要求的图片尺寸为 300*300
        final int IN_WIDTH = 300;
        final int IN_HEIGHT = 300;
        final float WH_RATIO = (float) IN_WIDTH / IN_HEIGHT;
        final double IN_SCALE_FACTOR = 0.007843;
        final double MEAN_VAL = 127.5;
        final double THRESHOLD = 0.2;

        Mat imageMat = new Mat();
        Utils.bitmapToMat(image, imageMat);
        Imgproc.cvtColor(imageMat, imageMat, Imgproc.COLOR_RGBA2RGB);
        Mat blob = Dnn.blobFromImage(imageMat, IN_SCALE_FACTOR,
                new Size(IN_WIDTH, IN_HEIGHT),
                new Scalar(MEAN_VAL, MEAN_VAL, MEAN_VAL),
                false, false);
        net.setInput(blob);
        Mat detections = net.forward();

        int cols = imageMat.cols();
        int rows = imageMat.rows();
        detections = detections.reshape(1, (int) detections.total() / 7);
        boolean detected = false;
        for (int i = 0; i < detections.rows(); ++i) {
            double confidenceTmp = detections.get(i, 2)[0];
            if (confidenceTmp > THRESHOLD) {
                detected = true;
                int classId = (int) detections.get(i, 1)[0];
                int left = (int) (detections.get(i, 3)[0] * cols);
                int top = (int) (detections.get(i, 4)[0] * rows);
                int right = (int) (detections.get(i, 5)[0] * cols);
                int bottom = (int) (detections.get(i, 6)[0] * rows);
                // Draw rectangle around detected object.
                Imgproc.rectangle(imageMat, new Point(left, top), new Point(right, bottom),
                        new Scalar(0, 255, 0), 4);
                String label = classNames[classId] + ": " + confidenceTmp;
                int[] baseLine = new int[1];
                Size labelSize = Imgproc.getTextSize(label, Core.FONT_HERSHEY_COMPLEX, 0.5, 5, baseLine);
                // Draw background for label.
                Imgproc.rectangle(imageMat, new Point(left, top - labelSize.height),
                        new Point(left + labelSize.width, top + baseLine[0]),
                        new Scalar(255, 255, 255), Core.FILLED);
                // Write class name and confidence.
                Imgproc.putText(imageMat, label, new Point(left, top),
                        Core.FONT_HERSHEY_COMPLEX, 0.5, new Scalar(0, 0, 0));
            }
        }

        if (!detected) {
            Toast.makeText(this, "没有检测到目标！", Toast.LENGTH_LONG).show();
            return;
        }

        Utils.matToBitmap(imageMat, image);
        imageView.setImageBitmap(image);
    }

    // Upload file to storage and return a path.
    private static String getPath(String file, Context context) {
        Log.i("getPath", "start upload file " + file);
        AssetManager assetManager = context.getAssets();
        BufferedInputStream inputStream = null;
        try {
            // Read data from assets.
            inputStream = new BufferedInputStream(assetManager.open(file));
            byte[] data = new byte[inputStream.available()];
            inputStream.read(data);
            inputStream.close();
            // Create copy file in storage.
            File outFile = new File(context.getFilesDir(), file);
            FileOutputStream os = new FileOutputStream(outFile);
            os.write(data);
            os.close();
            Log.i("getPath", "upload file " + file + "done");
            // Return a path to file which may be read in common way.
            return outFile.getAbsolutePath();
        } catch (IOException ex) {
            Log.e("getPath", "Failed to upload a file");
        }
        return "";
    }

    private static final int MAX_SIZE = 1024;
    private ImageView imageView;
    private Bitmap image;
    private Net net = null;
    private int PICK_IMAGE_REQUEST = 1;
    private static final String[] classNames = {"background",
            "aeroplane", "bicycle", "bird", "boat",
            "bottle", "bus", "car", "cat", "chair",
            "cow", "diningtable", "dog", "horse",
            "motorbike", "person", "pottedplant",
            "sheep", "sofa", "train", "tvmonitor"};
}

代码中的一些关键点说明如下：

• loadModel：实现了模型的加载，OpenCV提供了readNetFromCaffe方法用于加载Caffe训练的模型，其输入就是两个模型文件。
• onActivityResult：实现了选择图片后的图片处理和展示。
• recognize：实现利用加载的模型进行目标检测，并根据检测结果用框画出目标的位置。和之前的基于HOG特征的目标检测类似。

然后点击运行，效果如下：

可以看到，检测到了显示器、盆栽、猫、人等。对安卓还不太熟，后面有时间了弄一从摄像头视频中实时检测的App玩玩。

Reference:

• https://docs.opencv.org/4.2.0/d0/d6c/tutorial_dnn_android.html

我使用的环境是：

• MacOS 10.15.3
• Android Studio 3.6.1（下载，包含MacOS Android SDK）
• OpenCV Android SDK 3.4.9（下载）

环境准备

Android Studio的安装就不说了非常简单（只要你网络畅通），OpenCV Android SDK下载后直接解压即可。关于OpenCV Android SDK目前最新的4.x版本是4.2.0，我刚开始使用的是这个版本，但发现问题比较多，所以最后使用了3.x的最新版本3.4.9。也强烈建议你使用3.x版本。

OpenCV底层的算法都是使用C/C++实现的，并且编译成了.so/.a，所以安卓（Java）要使用这些库必须通过JNI，安卓提供了一个开发工具包NDK（Native Development Kit），可以更方便的帮助开发人员通过JNI访问本地代码。这个包默认是没有安装的，所以第一步就是安装NDK及其一些依赖包。

安装NDK

直接上图吧：

安装NDK和CMake。

创建项目

先创建一个Android的工程，按照下面的图来就行（重点地方已标记）：

项目创建成功后在build的时候可能会出现如下错误：

A problem occurred configuring project ':app'.
> NDK not configured. Download it with SDK manager. Preferred NDK version is '20.0.5594570'. Log: /Volumes/Files/Study/android/opencv/Demo/app/.cxx/ndk_locator_record.json

这个时候打开“Project Structure”设置一下NDK的路径即可（NDK安装完成后再Android SDK目录下）：

然后再Build，应该就没有什么错误了。接下来就是导入OpenCV SDK了。

导入OpenCV

右键工程，选择新增module：

module type选择Eclipse ADT Project：

然后就是选择模块的Source directory了，选择OpenCV Android SDK解压目录下面的sdk里面的java目录，如图所示：

选择以后，会自动生成一个模块名，自己也可以修改，建议使用默认值，因为随sdk的那些samples里面都用的是这个名字。4.x版本就没有这个贴心了。然后Next，后面都保持默认，直到Finish。

导入以后，修改导入的OpenCV模块的build.gradle文件。主要有这么几个修改点：

• 修改第一行的apply plugin: 'com.android.application'为apply plugin: 'com.android.library'，这样才能将导入的OpenCV作为模块使用。
• 用app的build.gradle里面的compileSdkVersion、buildToolsVersion、 minSdkVersion、 targetSdkVersion值替换掉OpenCV build.gradle里面对应的值。然后编译。有可能会提示“AndroidManifest.xml”文件里面不应该有版本之类的错误，直接根据提示移除即可，如下图：

修改完之后，确保build成功。

然后就是将导入的OpenCV添加为app的依赖：

确定即可。然后确保编译没有错误。到这里openCV依赖就算添加完了，只要编译没有错误，就可以在项目中使用OpenCV了。

但工作并没有完，OpenCV为了减小应用的体积，单独提供了一个OpenCV Manager的apk文件，这个文件包含了OpenCV的一些库。也就是要使用OpenCV，你的手机上面除了要安装你自己的app，还要安装OpenCV Manager才可以。如果没有装，你自己的app启动的时候，就会提示去Google Play下载。这里有几个坑：

1. 我试了一下，即使能访问Google Play，也搜索不到这个app。

2. 本来这个OpenCV Manager的apk文件是随sdk一起的，但4.2的版本里面没有这个文件了（我估计4.x的都没有），但3.x的sdk包里面却有，就在解压目录里面有个apk目录，里面有各个硬件架构的apk：

   

当然很多时候，让别人为了使用你的App，再去安装另外一个app不是很OK，所以也有一种方式可以将需要的OpenCV的库直接打到自己的这个App里面。操作方式如下（这里有很多坑，网上绝大多数都没有说清楚）：

• 将工程显示方式从Android切换为Project：

  

• 然后在app目录下面创建一个"jniLibs"目录，将OpenCV Android SDK的sdk->native->libs下面的目录拷贝到这个目录下（只拷贝需要的架构即可，一般手机都是arm64-v8a，模拟器一般都是x86、x86_64)，如下图：

  

  

• 然后在app目录下面的build.gradle文件的android里面添加如下内容（网上绝大多数教程都漏了这一步）：

  

  文字版：

      sourceSets {
          main {
              jni.srcDirs = []
              jniLibs.srcDirs = ['jniLibs']
          }
      }

最后就是验证环境是否完全部署好了：修改MainActivity.java文件，在onCreate里面增加一些内容，如下：

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        // Example of a call to a native method
        TextView tv = findViewById(R.id.sample_text);
        // tv.setText(stringFromJNI());

        if (OpenCVLoader.initDebug()) {
            Log.i("CV", "load OpenCV Library Successful.");
           tv.setText("load OpenCV Library successfully.");
        } else {
            Log.i("CV", "load OpenCV Library Failed.");
            tv.setText("load OpenCV Library failed.");;
        }
    }

然后连上你的手机或者模拟机，运行一下，如果提示加载OpenCV库成功，那整个环境搭建就算完成了：

至此，环境搭建就算完成了，总体来说，网上的文章有很多问题，包括官方那古老的文档。祝你好运！下篇文章介绍一下如何基于整个环境构建一个手机端的目标检测程序。

注：图片来自这里.

提取出特征之后，就可以使用一些分类算法进行模型训练了。当时论文作者使用线性SVM进行了模型的训练，所以现在HOG特征也都基本是和SVM一起使用的（记得以前有统计称普通机器学习算法中最受欢迎的就是SVM和随机森林了）。完整的流程如下（图片来自HOG的原始论文）：

OpenCV也支持基于HOG特征的目标检测，并且预先训练了一些模型，下面我们通过一个例子进行介绍:

import cv2

// 初始化HOG及SVM分类器
hog = cv2.HOGDescriptor()
hog.setSVMDetector(cv2.HOGDescriptor_getDefaultPeopleDetector())
vs = cv2.VideoCapture("/Users/allan/Downloads/TownCentreXVID.avi")
threshold = 0.7

while True:
    grabbed, frame = vs.read()
    if grabbed:
        frame = cv2.resize(frame, (1280, 720))
        gray_frame = cv2.cvtColor(frame, cv2.COLOR_RGB2GRAY)

        rects, weights = hog.detectMultiScale(gray_frame)
        for i, (x, y, w, h) in enumerate(rects):
            if weights[i] < 0.7:
                continue
            else:
                cv2.rectangle(frame, (x, y), (x + w, y + h), (0, 255, 0), 2)

        cv2.imshow("frame", frame)

    k = cv2.waitKey(1) & 0xFF
    if k == ord("q"):
        break

vs.release()
cv2.destroyAllWindows()

代码整体逻辑比较简单，和上篇文章代码非常相似。刚开始初始化HOG Descriptor，并设置SVM检测器为默认的行人检测器。然后从视频读取一帧帧的图片进行处理（文中的测试视频可在公众号回复"机器视觉实战3"获取）。

代码效果如下：

这里对检测函数detectMultiScale的返回值稍作说明。我们知道分类算法的结果一般返回的是label，也就是告诉你目标属于哪个类别。而检测类算法要更进一步，不仅要解决图片中有没有目标出现，如果有，还要给出在哪里。所以不论是上节的Haar Cascades，还是这节的HOG，检测函数的返回值都很相似，HOG返回的信息更多，我们以HOG为例介绍。HOG返回了两个列表：rects和weights。检测到多少个目标，列表中就会有多少个值，即列表的大小回答了图片中有没有目标的问题。rects中的每个值是包含四个元素的元组，比如(952, 3, 77, 82)，这四个值限定了图片中一个矩形，前两个值是矩形的一个顶点的坐标，后面两个值则是矩形的宽和高。而这个矩形就是检测出来的目标的位置，这些从代码中的cv2.rectangle也能看出来。相比于Haar，HOG还多返回了一个weights列表，这个列表的行和rects是一致的，它指的是识别出来的目标的权重，可以理解为可信度，DNN模型里面一般称为confidence。

对于目标检测来说，还有一个非常重要的知识点，就是NMS（Non Maximum Suppression），一般翻译为非极大值抑制。我们进行检测的时候，是用一个个滑框去获取特征值的，所以会产生大量的重复区域，效果就是最终返回的矩形有很多会产生重复。而NMS就是用来消除这些局部区域的极大值，最终获得最大值，从而消除重复，下面是一张效果图：

左侧是没有经过NMS处理的，右侧是经过NMS处理。这里推荐一篇文章：非极大值抑制(Non-Maximum Suppression). NMS的算法原理相对简单，需要的时候可以自己实现，也可以使用一些已有实现。这里推荐一个Python的：

# pip install imutils
from imutils.object_detection import non_max_suppression

rects = np.array([[x, y, x + w, y + h] for (x, y, w, h) in rects])
pick = non_max_suppression(rects, probs=None, overlapThresh=0.65)

Haar Cascades和Hog特征检测是DNN没有出来之前主要的目标检测算法，即使现在有很多基于DNN的模型，Haar Cascades和Hog在工业界依旧有很多应用场景。

References

• Pedestrian Detection OpenCV

然后用这些长方形去划过图片（非常类似于CNN里面的卷积核），每划一次，用白色框中的所有的像素值减去黑色框中所有像素的值，得到一个该特征的值。这样有了数据，有了特征，就可以训练分类器了，比如使用AdaBoost分类器对数据进行训练。目前这个算法已经非常成熟，本文演示一下如何借助OpenCV使用Haar Cascades进行目标检测。OpenCV已经集成了Haar Cascades，而且内置了一些训练好的模型，可以从这里获取和查看。

下面代码实现了通过Haar特征进行人脸和眼睛检测：

import cv2

from imutils.video import VideoStream

face_cascade = cv2.CascadeClassifier(cv2.data.haarcascades + "haarcascade_frontalface_default.xml")
eye_cascade = cv2.CascadeClassifier(cv2.data.haarcascades + "haarcascade_eye_tree_eyeglasses.xml")
vs = VideoStream(src=0).start()

while True:
    frame = vs.read()
    frame = cv2.resize(frame, (640, 480))
    # Haar Cascades必须使用灰度图
    gray_frame = cv2.cvtColor(frame, cv2.COLOR_RGB2GRAY)
    rects_face = face_cascade.detectMultiScale(gray_frame)

    for (x, y, w, h) in rects_face:
        cv2.rectangle(frame, (x, y), (x + w, y + h), (0, 255, 0), 2)
        y = y - 10 if y - 10 > 10 else y + 10
        cv2.putText(frame, "face", (x, y), cv2.FONT_HERSHEY_SIMPLEX, 0.45, (0, 255, 0), 1)

    rects_eye = eye_cascade.detectMultiScale(gray_frame)
    for (x, y, w, h) in rects_eye:
        cv2.rectangle(frame, (x, y), (x + w, y + h), (0, 0, 255), 2)
        y = y - 10 if y - 10 > 10 else y + 10
        cv2.putText(frame, "eye", (x, y), cv2.FONT_HERSHEY_SIMPLEX, 0.45, (0, 0, 255), 1)

    # 滤镜不能少...
    frame = cv2.bilateralFilter(frame, 0, 20, 5)
    cv2.imshow("preview", frame)
    k = cv2.waitKey(1) & 0xFF
    if k == ord("q"):
        break

代码见GitHub.

下面是检测效果（原谅我厚颜无耻的加了一点滤镜...）：

关于Haar Cascades算法需要知道以下几点：

1. Haar Cascades分类器的输入需要灰度图。
2. Haar特征是一种目标检测算法，可以用来训练各种目标的检测模型。但一个模型只能用来检测一种目标，比如上面代码中，检测人脸和眼睛是两个模型（其实光眼睛这一个也区分了两个模型，一个戴眼镜和一个不戴眼睛）。这和基于深度学习的目标检测模型是有区别的，后者一般一个模型可以检测多个目标。

虽然Haar Cascades一般没有一些基于深度学习的目标检测模型强大，但他也有自己的一些优势，比如容易训练、资源占用少等，所以仍旧有一定的使用场景。本文介绍的比较简单，一些细节会放在下篇文章中和另外一种目标检测算法一起讲解。

原文出处：Ball Tracking with OpenCV.

项目学习

代码学习

我使用的环境是：MacOS+Python3.7.4+OpenCV 4.2.0.

相比于原文，我对代码做了一些小修改，并且加了一些中文注释，方便你理解。整个项目代码如下：

import argparse
import time
from collections import deque
import cv2
import imutils
import numpy as np
from imutils.video import VideoStream

# 命令行参数
ap = argparse.ArgumentParser()
ap.add_argument("-v", "--video", help="path to video")
ap.add_argument("-b", "--buffer", type=int, default=64, help="max buffer size")
args = vars(ap.parse_args())

# 绿色球的HSV色域空间范围
greenLower = (29, 86, 6)
greenUpper = (64, 255, 255)
pts = deque(maxlen=args["buffer"])

# 判断是读入的视频文件，还是摄像头实时采集的，这里作区分是因为两种情况下后面的有些操作是有区别的
if args.get("video", None) is None:
    useCamera = True
    print("video is none, use camera...")
    vs = VideoStream(src=0).start()
else:
    useCamera = False
    vs = cv2.VideoCapture(args["video"])
    time.sleep(2.0)

while True:
    frame = vs.read()
    # 摄像头返回的数据格式为(帧数据)，而从视频抓取的格式为(grabbed, 帧数据)，grabbed表示是否读到了数据
    frame = frame if useCamera else frame[1]

    # 对于从视频读取的情况，frame为None表示数据读完了
    if frame is None:
        break

    # resize the frame(become small) to process faster(increase FPS)
    frame = imutils.resize(frame, width=600)
    # blur the frame to reduce high frequency noise, and allow
    # us to focus on the structural objects inside the frame
    # 通过高斯滤波去除掉一些高频噪声，使得重要的数据更加突出
    blurred = cv2.GaussianBlur(frame, (11, 11), 0)
    # convert frame to HSV color space
    hsv = cv2.cvtColor(blurred, cv2.COLOR_BGR2HSV)
    # handles the actual localization of the green ball in the frame
    # inRange的作用是根据阈值进行二值化:阈值内的像素设置为白色(255)，阈值外的设置为黑色(0)
    mask = cv2.inRange(hsv, greenLower, greenUpper)

    # A series of erosions and dilations remove any small blobs that may be left on the mask
    # 腐蚀(erode)和膨胀(dilate)的作用:
    # 1. 消除噪声;
    # 2. 分割(isolate)独立的图像元素，以及连接(join)相邻的元素;
    # 3. 寻找图像中的明显的极大值区域或极小值区域
    mask = cv2.erode(mask, None, iterations=2)
    mask = cv2.dilate(mask, None, iterations=2)

    # 寻找轮廓，不同opencv的版本cv2.findContours返回格式有区别，所以调用了一下imutils.grab_contours做了一些兼容性处理
    cnts = cv2.findContours(mask.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
    cnts = imutils.grab_contours(cnts)
    center = None

    # only proceed if at least one contour was found
    if len(cnts) > 0:
        # find the largest contour in the mask, then use it to compute the minimum enclosing circle
        # and centroid
        c = max(cnts, key=cv2.contourArea)
        ((x, y), radius) = cv2.minEnclosingCircle(c)
        M = cv2.moments(c)
        # 对于01二值化的图像，m00即为轮廓的面积, 一下公式用于计算中心距
        center = (int(M["m10"] / M["m00"]), int(M["m01"] / M["m00"]))

        # only proceed if the radius meets a minimum size
        if radius > 10:
            # draw the circle and centroid on the frame, then update the list of tracked points
            cv2.circle(frame, (int(x), int(y)), int(radius), (0, 255, 255), 2)
            cv2.circle(frame, center, 5, (0, 0, 255), -1)

        pts.appendleft(center)

    for i in range(1, len(pts)):
        # if either of the tracked points are None, ignore them
        if pts[i - 1] is None or pts[i] is None:
            continue

        # compute the thickness of the line and draw the connecting line
        thickness = int(np.sqrt(args["buffer"] / float(i + 1)) * 2.5)
        cv2.line(frame, pts[i - 1], pts[i], (0, 0, 255), thickness)

    cv2.imshow("Frame", frame)
    key = cv2.waitKey(1) & 0xFF

    if key == ord("q"):
        break

if useCamera:
    vs.stop()
else:
    vs.release()

cv2.destroyAllWindows()

该项目主要使用OpenCV实现，里面重要的地方我都已经加了注释说明，这里再理一下整个流程：

1. 处理命令行参数。
2. 定义绿色球在HSV色域空间的颜色范围，后面会根据这个范围进行二值化，从而实现轮廓检测。
3. 区分一下是直接从摄像头读取的数据还是处理的已经拍好的视频，这里作区分是因为两种情况下，后面有些代码要做不同处理。

4. 循环处理视频中的帧：

   1. 获取1帧的图像。对于从已有视频读的情况，如果读到的帧为空，则表示处理视频处理完了。
   2. 调整图片大小，主要是缩小一下图片，提高处理速度。
   3. 通过高斯滤波去除掉一些高频噪声，使得重要的数据更加突出。
   4. 将图像从BGR色域转换到HSV色域。
   5. 根据绿色球在HSV色域的颜色范围进行二值化。这样处理之后，绿色就会变成白色，其它都会变成黑色，方便后面提取球的轮廓。后面进行的腐蚀和膨胀操作也是为了消除噪声点（毛刺），更准确的提取小球轮廓。
   6. 提取轮廓。
   7. 后面就是根据提取出来的轮廓，画了一些小球的边沿，以及运动轨迹，就不细述了，代码里面很清楚。

图像处理效果展示

对于没有图像处理基础的人来说，可能不了解其中一些处理的作用，这里我把一些关键步骤处理的效果图放上来，方便你理解（以其中一帧图片为例）：

• resize后的效果：

  ​

  ​ 这一步除了尺寸有变化，其它都和原图一样。

• 高斯滤波后的效果：

  

滤掉了高频噪音，看着变模糊了。

• 转换到HSV色域后的效果：

  

• 二值化后的效果：

  

• 腐蚀和膨胀后的效果：

  

HSV颜色空间

先简单介绍下HSV颜色空间吧（其实还有个HSL，和HSV类似，但有些不同）。RGB是在笛卡尔坐标系来表示颜色的，而HSV则是在圆柱坐标系中表示颜色的，所以它能表示更多的信息。下图是一个HSV的图（图片来自维基百科）：

简单说就是HSV使用圆柱坐标系表示颜色，分三个维度（如上图中的e）：

• Hue：即色相，就是我们平时说的颜色名称，比如红色、黄色。H的取值为绕圆柱中心轴一圈的角度（即圆柱坐标系中的方位角），所以取值范围是0\~360。
• Saturation：即饱和度，是指色彩的纯度，越高色彩越纯，低则逐渐变灰，取0-100%的数值。S为圆柱的半径值（即圆柱坐标系中的径向距离）。
• Value：即明度，也称亮度，取0-100%的数值。V为圆柱坐标系中的高度。

圆柱的中心轴底部为黑色，顶部为白色，中间为灰色。更详细的信息请参加维基百科：HSV。

那为什么我们要将图像从RGB转到HSV再做颜色识别呢？因为虽然RGB通道对人眼来说比较友好，但却不能很好地反映出物体具体的颜色信息。相反，HSV空间能够非常直观的表达色彩的明暗，色调，以及鲜艳程度，方便进行颜色之间的对比。所以在通过颜色识别对象时，都是采用HSV颜色空间的。

最后说一下两个实战时需要注意的事项：

1. HSV标准中，Hue是角度，所以取值范围是0\~360，但在OpenCV中做了精简，实际范围变成了0\~180；S和V的取值是0\~100%，但OpenCV中是0\~255.所以使用OpenCV的时候需要注意一下。

2. 一个颜色在HSV中没有特别明确的值或者范围，实际使用的时候往往需要我们自己去观察测试进行确定。下面是一个常见颜色H值大致的范围参考（注意范围是0\~360）：

   • 红色(Red)：0\~60
   • 黄色(Yellow)：61\~120
   • 绿色(Green): 121\~180
   • 青色(Cyan): 181\~240
   • 蓝色(Blue): 241\~300
   • 品红(Magenta): 301\~360

资源信息

• 完整代码：code.
• 涉及的视频资源：在公众号回复“机器视觉实战1”获取下载链接。

通过这个项目我们可以学到如何通过颜色来做物体识别。