CN102999756A - 基于gpu实现pso-svm对道路标志的识别方法 - Google Patents

Abstract

本发明公开了一种基于GPU实现的自适应变异粒子群优化算法优化SVM对道路限速标志识别的方法，利用PSO优化SVM的参数，快速准确的识别道路限速标志的种类,基于粒子群在处理优化SVM参数过程中存在处理数据量大、计算时间长的特点，本发明利用GPU的并行计算特性来提高PSO算法的运行速度。本发明有益的效果是：采用GPU加速ALTMPSO优化支持向量机的方法，在道路限速标志识别准确率上优于传统的SVM，在算法收敛性和运行速度上优于标准PSO-SVM。

Description

基于GPU实现PSO-SVM对道路标志的识别方法

技术领域

本发明涉及支持向量机道路限速标志识别方法，属于智能交通领域，具体涉及利用GPU实现自适应变异粒子群优化支持向量机的道路限速标志识别方法。

背景技术

道路限速标志识别是智能交通研究的一个重要分支，有两方面的作用：第一，管理交通；第二，引导和警告驾驶者。道路限速标志的自动识别，有利于提高车辆的主动安全性能。道路限速标志识别主要包括两个基本的技术环节：（1）限速标志的检测，包括限速标志的定位及图像预处理；（2）限速标志的识别，包括限速标志的特征提取与分类。

随着计算智能技术的发展，模板匹配、人工神经网络等方法已在限速标志识别领域得到了成功的应用。基于结构风险最小化准则的支持向量机SVM（Support Vector Machine）对道路标志进行识别，具有良好的泛化能力和较高的识别能力，能够有效避免经典机器学习方法中存在的维数灾难、局部极小、过学习等问题。在SVM分类器中，其相关参数的设置对SVM的识别性能有着决定性影响。

粒子群优化算法(PSO)是由Kenned和Eberhart在1995年的IEEE国际神经网络学术会议上提出的一种基于群体智能方法的演化计算技术。与其他演化算法如遗传算法、蚁群算法比较，粒子群算法实现容易、参数较少，具很强的局部和全局搜索能力，可应用于大量非线性、多峰值的复杂问题的优化。近年来，粒子群优化算法已成功应用于函数优化、神经网络训练、模式识别、模糊系统控制等多个科学与工程领域。

为了避免粒子群优化算法存在的早熟收敛和精度差等局限，众多研究人员相继提出了多种改进措施，改进的方法主要表现为参数改变、粒子群初始化方法改进、进化方程改进和混合策略等。在解决计算速度慢的问题上，大多采用并行处理的方法。近年来，计算机图形处理器GPU（Graphics processing unit）绘制流水线的高速度和并行性以及近年来发展起来的可编程功能，使其在通用计算领域的应用有着巨大潜力。与CPU相比，GPU呈现出了许多优点。首先，GPU计算速度比CPU快。GPU投入更多晶体管去处理数据而不是数据缓存和流控制，这样能够进行每秒更多次的浮点计算；其次，GPU更适合大规模的密集型数据并行计算。它特别适合解决具有较高算法强度且可以被表达为并行数据计算的问题，通过将此类问题细分成众多数据元素然后并行执行，将具有更高的算术操作与存储操作之比。

本发明利用统一计算设备架构(compute unified device architecture, CUDA)，在GPU上实现了一种自适应变异粒子群优化算法对SVM的参数进行优化，并应用到道路限速标志的识别中。

发明内容

本发明针对现有技术存在的上述问题，在GPU上实现自适应变异粒子群优化支持向量机的道路限速标志识别，通过自适应变异粒子群优化支持向量机的参数提高道路限速标志的识别率，同时利用GPU加速自适应变异粒子群优化支持向量机参数的运行速度。

本发明解决上述技术问题所采用的技术方案是，提出一种基于GPU实现粒子群优化支持向量机对道路限速标志识别的方法，其特征在于，包括步骤：对道路限速标志进行二值化特征提取，得到的特征向量作为道路限速标志识别的样本数据库，从中随机选取一部分作为训练集，另一部分作为测试集；将CPU上的初始化种群拷贝到GPU的全局存储器中，映射种群中粒子为支持向量机道路限速标志识别模型中径向基核函数的宽度参数g和误差惩罚参数C；优化支持向量机道路限速标志识别模型中径向基核函数的宽度参数g和误差惩罚参数C，建立粒子群优化支持向量机道路限速标志识别模型；输入样本训练支持向量机道路限速标志识别模型，对训练集进行交叉验证的准确率作为适应度函数；获得最优位置适应度确定全局最优值Pg，将P_g映射为支持向量机道路限速标志识别模型的径向基核函数的宽度参数g和误差惩罚参数C，并从GPU传回到CPU作为优化结果输出，获得的识别率最高的训练模型去识别待识别样本。具体步骤如下：

对道路限速标志进行二值化特征提取,通过二值化特征提取得到的特征向量作为GPU-ALTMPSO-SVM（用计算机图像处理器实现自适应变异粒子群优化支持向量机）道路限速标志识别模型的样本数据库；构建支持向量机道路限速标志识别模型，优化支持向量机道路限速标志识别模型中的径向基核函数的宽度参数g和误差惩罚参数C，建立基于GPU的自适应变异粒子群优化支持向量机道路限速标志识别训练模型；利用训练模型识别待识别样本，输出待识别样本的种类，计算识别的准确率。 采用对训练集进行交叉验证准确率作为适应度函数：即调用公式：

确定适应度函数。如果数量为N的粒子群在连续S代过程中有P%的粒子没有发现全局最优值，则粒子群进行适当的变异，根据当前时刻t时粒子的位置x_ij(t)和速度v_ij(t)确定下一时刻粒子的位置x_ij(t+1)和速度v_ij(t+1)，其位置x_ij和速度v_ij变异更新的公式如下：

$\left\{\begin{array}{c}{x}_{\mathrm{ij}}(t+1)=x_{\mathrm{ij}}\left(t\right)+(\mathrm{\ρ}-0.5)\·x_{\mathrm{ij}}\left(t\right)\\ v_{\mathrm{ij}}(t+1)=v_{\mathrm{ij}}\left(t\right)+(\mathrm{\ρ}-0.5)\·v_{\mathrm{ij}}\left(t\right)\end{array}\right.$

还可采用如下公式确定位置和速度更新：

$\begin{array}{c}{v}_{\mathrm{ij}}(t+1)={\mathrm{wv}}_{\mathrm{ij}}\left(t\right)+(c_1+c_2)Y[{\mathrm{Zp}}_{\mathrm{bj}}\left(t\right)+(1-Z)p_{\mathrm{gj}}\left(t\right)-x_{\mathrm{ij}}\left(t\right)]\\ x_{\mathrm{ij}}(t+1)=x_{\mathrm{ij}}\left(t\right)+v_{\mathrm{ij}}(t+1)\end{array}$

其中ρ为0-1之间的随机数，i=1,2,...,N；j=1,2,...,D，t代表第t次迭代，w为惯性权重，c₁和c₂为非负常数，Z从1到0线性递减，Y服从[0,1]均匀分布；p_bj(t)为第t次迭代第j维局部最优值，p_gi(t)为第t次迭代第j维全局最优值。

当t大于最大迭代次数itermax，获得最优位置适应度确定全局最优值Pg，即更新完成最大迭代次数次迭代后，所获得的最优位置适应度最小值对应的位置为全局最优值Pg。

本发明，通过计算当前线程对应粒子的适应值、粒子个体最优值及位置、全局最优值及位置，速度和位置来完成整个算法在GPU上最优值的计算。能有效搜索SVM参数C和g的全局最优或近似最优解，同时基于GPU的并行计算能够加速该粒子群算法优化SVM的求解过程，减少运行时间，准确快速的识别道路限速标志。

附图说明

图1道路限速标志二值化处理流程图；

图2道路限速标志识别流程图；

图3基于GPU实现的自适应变异粒子群优化支持向量机工作流程图；

图4 粒子位置在GPU中的映射模型。

具体实施方式

下面结合附图和具体实施方式对本发明的技术方案作进一步详细的说明。

如样本数据集由4类国内道路上常见的限速标志组成（20、40、60、80km/h）， 把成功提取的图像的特征作为实验数据集。如可随机选取实验数据集中的64个样本作为训练集，剩下的样本作为待识别样本，数据集的特征向量为35维。利用GPU-ALTMPSO算法优化SVM参数，构建道路标志识别分类器，可以识别上述道路限速标志类别，与现有道路限速标志识别方法相比，提高道路限速标志识别的准确率。

参考图1，对道路限速标志进行特征提取，可采用如下二值化处理和特征提取。

(1)二值化处理。二值化是为了区分数字（黑色）和背景（白色），因此红色像素不计算在内。因为黑白两种颜色在R、G、B三个分量上都有很明显的差异，所以以R分量的平均值作为阈值即可取得较好的二值化结果(图1 b)。

(2)特征提取。特征提取首先要突出数字部分。找到数字边界，根据边界提取数字（图1c）。因为限速标志右边的0对分类没有贡献，所以只截取数字的左边部分。将限速标志左边部分划分成7×5个小方块并初始化为一个7×5向量，计算每个小方块内部白色像素的比例，如果该方块内白色像素的比例大于整幅图片中白色像素的比例，则对应的7×5向量位置标记为1（白色），否则标记为0（黑色）（图1d）。

图2道路限速标志识别流程图。通过二值化特征提取得到的特征向量作为GPU-ALTMPSO-SVM（用计算机图像处理器实现自适应变异粒子群优化支持向量机）道路限速标志识别模型的样本数据库；构建支持向量机道路限速标志识别模型，优化支持向量机道路限速标志识别模型中的径向基核函数的宽度参数g和误差惩罚参数C，建立基于GPU的自适应变异粒子群优化支持向量机道路限速标志识别训练模型；利用训练模型识别待识别样本，输出待识别样本的种类，计算识别的准确率。

将上述处理后的样本作为GPU-ALTMPSO-SVM道路限速标志识别模型的数据库样本，利用GPU实现自适应变异粒子群优化支持向量机道路限速标志识别模型中径向基核函数的宽度参数g和误差惩罚参数C。GPU-ALTMPS0-SVM工作流程参见图3，具体实现步骤如下：

在CPU中初始化粒子群参数，初始化粒子的速度x_i和位置v_i。如设置粒子总数N=100、维数D=2、最大迭代次数itermax=2000、加速因子c₁=2和c₂=2、惯性权重w=0.8和自适应变异中的学习因子Z的最大值Z_max=1、最小值Z_min=0，不健康因子P=20、迭代因子S=4、变异因子R=0.2。

在GPU全局存储器中分别建立以下一维数组：粒子的位置数组（Velocity[N*D]）、粒子的速度数组（Position[N*D]）、全局最优位置（Gbest_Position[N*D]）、局部最优位置（Pbest_Position[N*D]）、个体适应值（Fitness[N]）、全局最优适应值（Gbest_Fitness[N]）、局部最优适应值（Pbest_Fitness[N]），将CPU上的初始化种群拷贝到GPU的全局存储器中。

如图4所示，将每一个格（Grid）看作是一个大的二维数组Y，宽幅为WIDTH,b_x和b_y分别表示图像中当前块（Block）的标识号，其中t_x和t_y分别表示当前线程（Thread）的标识号，blockDim表示块的大小，x,y分别表示二维数组行和列所在位置（其中，x=b_x×blockDimx+t_x,y=b_y×blockDim.y+t_y），这样可以建立线程与数组的对应关系。

映射种群中粒子为支持向量机道路限速标志识别模型中径向基核函数的宽度参数g和误差惩罚参数C，  即x_i=[C,g],i=1,2,…,N。将x_i的各个分量载波到C和g的取值范围即可产生GPU-ALPSOTM初始位置：。

输入样本训练支持向量机训练模型，建立支持向量机道路限速标志识别模型，根据输入样本训练该道路限速标志识别模型。根据公式：

  确定适应度函数，式中i为粒子序号，将原始训练数据平均分为k组(k=5=5)，

为第i个粒子在第j组交叉验证测试中的识别率。

在GPU上计算适应度函数的主要步骤如下：

在当前线程的寄存器中建立临时的粒子位置P[i]数组，0≤i≤D，通过块与线程标识读取当前线程对应粒子的所有维数到共享存储器PS(t_y,t_x)，然后复制到P[i]中；

通过P[i]计算适应值函数，并将计算出来的适应值保存到全局存储器的数组（Fitness[y×WIDTH+x]）中；

更新局部最优值p_b和全局最优值p_g。对每个粒子，比较当前适应度f(x_i)和历史最优位置适应度f(p_b(i))，如果f(x_i)＜f(p_b(i))，则p_b(i)=x_i；比较每个粒子当前适应度f(x_i)和全局最优位置适应度f(p_b(i))，如果f(x_i)＞f(p_g(i))，则p_g(i)=x_i。当t大于最大迭代次数itermax，获得最优位置适应度确定全局最优值Pg，即更新完成最大迭代次数次迭代后，所获得的最优位置适应度最小值对应的位置为全局最优值Pg。

更新局部最优值p_b和全局最优值p_g在GPU上实现的具体步骤如下：

1）通过块和线程标识从全局存储器中读取当前线程对粒子的适应值和全局最优值分别到共享存储器FS(t_y,t_x)和DS(t_y,t_x)中；

2）通过比较后记录个体最优值和个体最优位置，并通过块和线程标识对应更新全局存储器中的局部数组Pbest_Fitness[y×WIDTH+x]和Pbest_Position[y×WIDTH+x]，通过比较记录全局最优值和全局最优值位置，并通过块和线程标识对应更新全局存储器中的全局数组Gbest_Fitness[y×WIDTH+x]和Gbest_Position[y×WIDTH+x]。

如果数量为N的粒子群在连续S代过程中有P%的粒子没有发现全局最优值，则粒子群进行适当的变异，根据当前时刻t时粒子的位置x_ij(t)和速度v_ij(t)确定下一时刻粒子的位置x_ij(t+1)和速度v_ij(t+1)，具体公式如下：

$\left\{\begin{array}{c}{x}_{\mathrm{ij}}(t+1)=x_{\mathrm{ij}}\left(t\right)+(\mathrm{\ρ}-0.5)\·x_{\mathrm{ij}}\left(t\right)\\ v_{\mathrm{ij}}(t+1)=v_{\mathrm{ij}}\left(t\right)+(\mathrm{\ρ}-0.5)\·v_{\mathrm{ij}}\left(t\right)\end{array}\right.$

或：

$\begin{array}{c}{v}_{\mathrm{ij}}(t+1)={\mathrm{wv}}_{\mathrm{ij}}\left(t\right)+(c_1+c_2)Y[{\mathrm{Zp}}_{\mathrm{bj}}\left(t\right)+(1-Z)p_{\mathrm{gj}}\left(t\right)-x_{\mathrm{ij}}\left(t\right)]\\ x_{\mathrm{ij}}(t+1)=x_{\mathrm{ij}}\left(t\right)+v_{\mathrm{ij}}(t+1)\end{array}$

其中ρ为0-1之间的随机数，i=1,2,...,N；j=1,2,...,D，t为迭代次数，w为惯性权重，c₁和c₂为非负常数，Z从1带0线性递减，Y服从[0,1]均匀分布；  p_bj(t)为第t次迭代第j维局部最优值，p_gi(t)为第t次迭代第j维全局最优值。

如果t大于最大迭代次数itermax，完成更新，将Pg映射为支持向量机道路限速标志识别模型的径向基核函数的宽度参数g和误差惩罚参数C，并从GPU中传回到CPU作为优化结果输出，获得的识别率最高的训练模型。利用该训练模型去识别待识别样本，输出待识别样本的种类，计算识别的准确率。

在GPU上更新当前全局最优值及位置。

初始化种群P(1)，t=1，t代表当前的迭代数，将CPU上的初始化种群拷贝到GPU的全局共享存储器中；在GPU上使用适应值内核函数（Fitness_kernel）计算当前线程对应粒子的适应值；使用局部最优值内核函数(Pbest_kernel)来更新当前线程对应粒子的个体最优值及位置；使用全局最优值内核函数(Gbest_kernel)来更新当前全局最优值及位置；使用更新下一代粒子位置和速度的函数（Update_kernel）来更新当前线程对应粒子位置，产生下一代群体P（t+1），t=t+1，直到迭代次数达到最大迭代次数；将最优值从GPU传回到CPU。

ALTMPSO算法流程中函数适应值的计算、粒子个体最优值及位置、全局最优值及位置，下一代粒子速度和位置在GPU上完成，通过计算当前线程对应粒子的适应值、粒子个体最优值及位置、全局最优值及位置，速度和位置来完成整个算法在GPU上最优值的计算。增强了粒子的全局搜索能力，避免了过早陷入局部最优，能有效搜索SVM参数C和g的全局最优或近似最优解；同时基于GPU的并行计算能够加速该粒子群算法优化SVM的求解过程，减少运行时间，从而更加准确快速的识别道路限速标志。

Claims (6)

1.一种基于GPU实现粒子群优化支持向量机对标志识别的方法，其特征在于，包括步骤：对道路限速标志进行二值化特征提取，得到的特征向量作为道路限速标志识别的样本数据库，从中随机选取一部分作为训练集，另一部分作为测试集；将CPU上的初始化种群拷贝到GPU的全局存储器中，映射种群中粒子为支持向量机道路限速标志识别模型中径向基核函数的宽度参数g和误差惩罚参数C；优化宽度参数g和误差惩罚参数C，建立粒子群优化支持向量机道路限速标志识别模型；输入样本训练支持向量机道路限速标志识别模型，对训练集进行交叉验证的准确率作为适应度函数；获得最优位置适应度确定全局最优值Pg，将P_g映射为支持向量机道路限速标志识别模型的径向基核函数的宽度参数g和误差惩罚参数C，并从GPU传回到CPU作为优化结果输出。

2.根据权利要求1所述的方法，其特征在于，所述对训练集进行交叉验证具体为，调用公式：

确定适应度函数，其中i为粒子序号，k为训练数据分组数，

为第i个粒子在第j组交叉验证测试中的识别率。

3.根据权利要求1所述的方法，其特征在于，所述确定全局最优值Pg具体包括，对每个粒子，比较当前适应度f(x_i)和历史最优位置适应度f(p_b(i))，如果f(x_i)＞f(p_b(i))，则p_b(i)=x_i；比较每个粒子当前适应度f(x_i)和全局最优位置适应度f(p_g(i))，如果f(x_i)＞f(p_g(i))，则p_g(i)=x_i，更新完成最大迭代次数次迭代后，所获得的最优位置适应度最小值对应的位置为全局最优值Pg。

4.根据权利要求3所述的方法，其特征在于，如果数量为N的粒子群在连续S次迭代过程中有P%的粒子没有发现全局最优值，则根据公式： $\left\{\begin{array}{c}{x}_{\mathrm{ij}}(t+1)=x_{\mathrm{ij}}\left(t\right)+(\mathrm{\ρ}-0.5)\·x_{\mathrm{ij}}\left(t\right)\\ v_{\mathrm{ij}}(t+1)=v_{\mathrm{ij}}\left(t\right)+(\mathrm{\ρ}-0.5)\·v_{\mathrm{ij}}\left(t\right)\end{array}\right.$ 对粒子群位置和速度进行更新，其中ρ为0-1之间的随机数，i=1,2,...,N；j=1,2,...,D，t迭代次数。

5.根据权利要求3所述的方法，其特征在于，如果数量为N的粒子群在连续S次迭代过程中有P%的粒子没有发现全局最优值，根据公式： $\begin{array}{c}{v}_{\mathrm{ij}}(t+1)={\mathrm{wv}}_{\mathrm{ij}}\left(t\right)+(c_1+c_2)Y[{\mathrm{Zp}}_{\mathrm{bj}}\left(t\right)+(1-Z)p_{\mathrm{gj}}\left(t\right)-x_{\mathrm{ij}}\left(t\right)]\\ x_{\mathrm{ij}}(t+1)=x_{\mathrm{ij}}\left(t\right)+v_{\mathrm{ij}}(t+1)\end{array}$ 对粒子群位置和速度进行更新，其中，w为惯性权重，c₁和c₂为非负常数，Z从1到0线性递减，Y服从[0,1]均匀分布。

6.根据权利要求3所述的方法，其特征在于， 更新局部最优值p_b和全局最优值p_g具体包括：通过块和线程标识从全局存储器中读取当前线程对粒子的适应值和全局最优值分别到共享存储器中，通过比较记录个体最优值和个体最优位置，并通过块和线程标识对应更新全局存储器中的局部数组，通过比较记录全局最优值和全局最优值位置，并通过块和线程标识对应更新全局存储器中的全局数组。

Images