KNN 分类算法在停车场车牌识别系统中的应用

屠 菁，刘登胜，钟雪景

（1.合肥学院 人工智能与大数据学院，安徽 合肥 230601；2.东南大学 软件学院，江苏 苏州 215123）

车牌识别（Automatic license plate recognition，ALPR）［1］是先通过彩色、黑白或红外相机拍摄图像，然后由机器通过图像处理或模式识别相关算法达到自动识别车牌号码的目的，用于减轻人为的工作量以及提高管理效率。 但是，车牌类型或环境的不确定增加了车牌的检测和识别难度，如车辆型号和相机距离的不同， 会对车牌的定位造成困扰；另外环境和光线也给拍摄的图像识别造成了困难。

车牌识别技术在智能处理领域一直是国内外学者主要的研究方向。例如，以色列Hi-Tech 公司和新加坡Optasia 公司，都研制了比较成熟的产品［2-3］。我国学者也一直在进行相关识别算法的研究，如刘军等［4］使用两层高斯金字塔模型分析汉字图像，再由神经网络分类器实现汉辨别；陈宏照等［5］提出基于OpenCV 的车牌定位方法，即将色彩与纹理相结合；张变莲等［6］利用 SUSAN 算子和 SIFT 算法实现对车牌区域边缘检测和字符识别；林乾毕［7］提出通过 SVM 分类器判断图像中的车牌区域［8］，然后由ANN 神经网络完成字符识别。 国内外车牌的排列规则不同，虽然国外研究效果较好，但是并不适用国内。 而国内的研究注重对算法的理论研究，较少与实际应用场景相结合。

本文主要讨论基于K- nearest neighbor（KNN）分类算法的车牌识别在停车场中的具体应用，系统拟在原车辆信息管理的基础上，增加车牌自动识别模块。首先，预处理原始车辆图像，削弱噪声的影响并缓和图像模糊；其次，通过边缘检测定位车牌区域及目标图像，采用垂直投影的方法进行字符分割；然后，通过KNN 算法完成车牌号码的最终识别。最后， 通过与ANN 神经网络算法、SIFT 算法进行实验比较， 验证KNN 方法的精度和效率以及实际应用价值。

1 KNN（K-nearest neighbor）算法

在模式识别技术中，KNN 算法被广泛应用于基于小训练集的有监督机器学习算法， 它通过计算两点之间的距离来发现两点之间的相似性， 该算法的优点是易于开发构造和计算复杂度较低［9］［10］(P228-231)。该算法基于3 个主要原则：(1) 确定每个训练样本到目标点的距离；(2)通过距离的远近选择目标点最近的k 个邻居；(3)用k 个样本为目标点的投票，共同确定目标点的类别。图1 给出了KNN 算法的实现原理［11］。

Minkowski 距离是传统KNN 中广泛使用的距离度量之一。如果样本特征具有相同的规模和数据分布，那么Minkowski 距离可以表示两点之间的实际距离。 本文将特征值之间的差异指数设为2，即欧式距离，因为平方和有利于描述多维点距离。 当特征点的个数为m 时，计算训练样本p = (x1, … ,xm)和测试样本q =(y1, … , ym)之间的欧式距离为公式（1）所示：

两个点之间的距离越短，它们之间的相似性越大。 在计算所有点对的距离后，可确定测试样本的类别。KNN 分类算法易于实现、分类性能好，主要表现为：算法的性能只与训练集有关，当测试样本发生变化时不会产生影响，且样本集越大性能越好［12］；算法通用性强，对于不同场景问题，无需重复建模，只需调整参数。

2 车牌图像的预处理与字符分割

2.1 基于高斯滤波算法的车牌图片预处理

车牌图片采集时因为受环境或车型的影响，容易产生噪声干扰识别的稳定性， 需预处理车牌图像，主要步骤如下。

步骤 1：滤波去噪、高斯滤波（Gauss Filter）算法可以较好地消除白噪声。具体方法为：通过计算像素点和邻域内其他像素点的值的加权平均值后， 每一个像素点的高斯滤波值即可获得。如公式（2） 所示。

经过高斯滤波之后的图像和原图像对比的示例如图2 所示。

图2 原始彩色图像与滤波后的图像

步骤2：图像的灰度化。 灰度图像相比彩色图像而言，每个像素点只需要一个字节存放，既减少了计算量，又不会影响图像处理的正确率。 一般可以采用加权平均法进行灰度处理，将每一个像素点的原有三个颜色参数转换为一个参数值来代替。如公式（3）所示。

以图1 的图像为例，灰度化后的图像如图3 所示。对于灰度化后的图像可进一步通过大津法［13］将其二值化，主要思想是：(1)选取一个灰度阀值t，根据阀值t 将图像中的所有像素点分为两类C0和C1；（2）由公式（4）分别计算出 C0和 C1出现的概率W0和 W1，然后由公式（5）计算出类 C0和 C1的平均灰度值u0和u1，最后根据公式（6）计算出类间方差g（t）。 当所得到的类间方差最大时，此时对应的阀值t 即为目标最佳阀值。

2.2 基于边缘检测和数学形态学的车牌定位方法

要获得汽车的车牌内容，首先需要从复杂的车辆照片中准确定位车牌的位置。车牌定位算法主要是根据车牌的一些独有特征来获取图像中的车牌照［14］（P14-20）。 我国的车牌在几何、颜色和纹理特征等方面具有明显的特征，主要表现为：车牌为规则具有特定比例的矩形，车牌的颜色较为固定，且其中的字符排列规则，字符之间都有一定的距离。

图3 基于Canny 算法的边缘检测步骤

图4 数学形态学和连通域分析后的图像

图5 基于垂直投影的车牌分割流程

图6 基于垂直投影的车牌字符分割方法示例

车牌定位常使用基于边缘检测、基于数学形态学和基于数字特征等定位方法，其中边缘检测和数学形态学依赖于图像的纹理和边缘特征，研究综合了两者的优点，对光线较弱、有噪声干扰的的车牌图像也能实现快速的定位，具有良好的鲁棒性和准确性。车牌区域中字符与底色之间灰度有着明显性的变化特征， 车牌区域中的灰度变化幅度比较大，具有规律性［15］。 Canny 边缘检测算法使用了变分法(Calculus of variations)，通过优化特定功能的函数达到最优检边缘检测，Canny 算法包含许多可以调整的参数， 可调整优化算法计算的时间与实效。具体步骤如图3 所示：

若垂直和水平方向的差分分别为Gy （x, y）和Gx（x, y），根据一阶偏导有限差分，则梯度值 φ（x，方向 θ（x, y）=tan-1（Gy（x, y）/Gx（x, y））。

对于车牌位置对应形状的提取，可在不影响图细节和边缘的前提下，通过数学形态学简化形状结构来提取选取的元素内容，主要采用的闭运算和开运算后的图像，具体如图4 所示。

数学形态学处理后的图像中，往往会有多个连通候选区域， 根据对车牌照固定的长宽比的分析（大约为3.14），筛选出特定的连通候选区域。 由于拍照和处理过程中其他种种因素的影响，车牌图像的具体大小会发生变化，通过设置合适的车牌长宽比，可以达到剔除范围外区域、得到真正的车牌连通区域的目的，然后根据连通域中的坐标从原始图像中提取完整的车牌照。 分析结果如图4(C)所示。

2.3 基于垂直投影的车牌字符分割方法

对定位后的车牌照进行整体识别，难度既大而且识别率较低，需要先对车牌照进行字符分割。 为了具有良好的实时性和准确性，本文采用垂直投影法，具体流程如图5 所示。

图6 为字符分割过程的示例图。由图，可知，字符间的间距在经过垂直投影后会形成波谷，而字符处的投影则会形成波峰。根据波谷处的像素点为0 来进行分割，(c)表示的字符为垂直投影分割后的结果。

3 基于KNN 分类算法的车牌字符识别

分割字符之后，下一步需要对字符进行识别处理。传统的识别方法是将图像进行二值化处理转换成0, 1 矩阵， 但是字符特别是汉字字符的笔画断裂等现象会大大影响识别效果。HLBP［16］特征结合了LBP（局部二值化模式）特征和 Haar 型特征［17］（P511-518），更能有效地反映图像局部的灰度变化，该算子以对称的方式给出8 组编码模型，如图7 所示。

图7 HLBP 的8 组编码模型

其中， 中心点P0记录 Haar 型特征的纹理变化，以 P0为中心构成了 5×5 的小窗 W（x, y），图像中任意像素 I（x, y）对于其 W（x, y）的 HLBP 算子可由公式（7）计算得到。

其中Mk分别对应图8 中的编码模型，T 为灰度划分的阈值。对车牌汉字和数字进行HLBP 算子特征提取之后，就可以采用KNN 算法进行分类。为了识别方便，我们将全图像的HLBP 特征进行直方图统计，生成直方图向量。 采用此方法为训练样本集中的图像均做HLBP 特征分析与提取。为了后期分类方便，可将直方图进行归一化处理，具体如公式（8）所示。

其中，灰度区间［0, L］，rk为灰度值，nk是 rk的像素个数，p（rk）即为其出现的概率。

对于待识别字符， 可采用KNN 分类算法进行欧式距离的计算和识别， 实现分类和字符识别，具体如图8 KNN 算法所示。

图8 KNN 分类算法

关键步骤的Python 语言实现代码如下所示：

4 系统实现与性能分析

4.1 实验环境与数据准备

实验搭建的服务数据环境为：PC 电脑（硬件配置为: 酷睿 i5 四核，500 GB HDD，8 GB 内存），操作系统为Windows 8.1 中文版， 数据库版本为MySQL 5.5，采用 Python 3.7 作为开发工具。

实验模拟了小区停车场的应用场景，常见的车型（包括丰田、福特、东风等品牌），包含1 025 张车辆的前视图像，图像尺寸为1 200×900，图像拍摄于多种环境下，有晴天、阴天、逆光等，如图9 所示。

图9 测试集图像示例

4.2 车牌识别模块

系统模拟了停车场的车牌识别，通过获取摄像头拍摄到的图片后对其进行处理，如图10 所示，界面左侧显示预处理的车牌照片信息，右侧显示图像识别之后的结果。

图10 车牌识别结果界面

4.3 性能分析

车辆识别结果的性能评估，可根据车牌字符识别精度, 即车牌字符序列识别正确与否来定义，具体如公式（9）所示：

将ANN 神经网络算法、SIFT 算法和与本文中使用的KNN 算法进行比较， 针对1 000 张完整车牌进行实验，选取850 张车牌图像作为字符训练集和150 张车牌图像作为字符测试集，检测各算法的车牌识别效果。 实验结果如表1 所示。

表1 不同识别算法下的车牌识别准确率和速度性能

由表1 可知，ANN 虽然在训练集和测试集均能得到较高的识别准确率，但车牌整体识别的准确率较低且耗时较多，原因在于车牌是多个字符的组合。 SIFT 和KNN 在训练集精度和车牌识别率上均表现较好，但是KNN 的时间性能更加出色，且实现起来更为直观，通过调整参数对性能进行微调也较容易。因此，本文采用的KNN 分类算法总体性能上识别准确率更好，识别率高且耗时时间较少，且随着训练集样本增多，其识别精度还会更高。

5 结语

本文具体论述了车牌识别过程中的关键步骤与关键技术， 并介绍了KNN 分类算法在字符识别中的应用。经测试，应用KNN 分类算法的车牌识别本系统能够很好地对车牌图像进行识别和提取出正确的车牌号码。 但是测试过程中也发现一些不足，例如当车牌图片受天气、光线等因素影响时，由于图像噪声增多，会影响识别的正确率。 在今后的研究中，可以引入深度学习相关算法，如卷积神经网络等，以提高车牌识别精度和普适性。