仿射不变性的特征提取

武汉理工大学毕业设计（论文）

目录

摘要.................................................................................................................. I ABSTRACT .......................................................................................................... II 绪论.. (1)

1 论文工作及章节安排 (2)

1.1论文的主要工作 (2)

1.2论文的组织结构 (2)

2 结构设计与方案选择 (3)

2.1 仿射不变性的特征提取系统结构 (3)

2.2 特征提取的方案选择 (4)

2.2.1 数据处理软件的选择 (5)

2.2.1.1 用MATLAB进行处理 (5)

2.2.1.2 用VC++进行处理 (6)

2.2.2 特征提取方案选择 (6)

2.2.2.1 利用仿射几何的仿射不变性提取方法 (6)

2.2.2.2 局域仿射不变性特征点提取 (8)

3仿射理论基础 (9)

3.1 图像的预处理 (9)

3.1.1 滤波方法 (9)

3.1.2 二值化 (9)

3.2 图像分割技术 (10)

3.2.1 K-means算法介绍 (10)

3.2.2 K-means图像分割 (13)

3.3 Hu不变矩 (13)

4 算法的设计 (14)

4.1 传统仿射算法 (14)

4.2 精简算法的实现 (15)

4.2.1 八向识别法 (15)

4.2.2 链码识别 (16)

4.2.3 Hu矩识别 (16)

5 识别结果分析 (19)

5.1 几何变换识别 (19)

5.2 加噪及缺损识别 (20)

6 总结与展望 (22)

致谢 (23)

参考文献 (24)

附录 (25)

武汉理工大学毕业设计（论文）

摘要

随着图像识别在社会各个领域的广泛应用，图像识别技术也逐渐成为计算机视觉和图像配准领域的主要研究方向之一。该论文从不同的角度对图像进行识别，匹配。主要研究了仿射不变性在图像识别技术领域的应用。

仿射变换是一类重要的线性几何变换，许多成像过程及其变化可以模型化为仿射变换，如图像在图像平面上的平移或旋转可以模型化为坐标系的平移或旋转，成像距离的变化可以模型化为不同坐标系之问的变换。若一个图形具有某种性质或者某个量，在平行射影下，如果不变，称这个性质为仿射不变性质，这个量称为仿射不变量。经过仿射对应它们也是不变的。同素性、结合性都是仿射不变性质（也就是说，仿射对应把共点的线变成共点的线，把共线的点变成共线的点）。平行四边形在仿射对应下的象还是平行四边形。

本文使用了K－means，以颜色分量（或几何性状）作为坐标参数，对景象图进行聚类。然后分割之后。通过聚类后的特征点提取，来进行匹配，从而达到仿射不变性的证明问题。对于几何变换的路标图像分析较为准确，在提取和匹配时，用三种方法进行比较论证。

关键词：K—means;仿射不变性；聚类；特征提取；仿射变换；几何变换

I

武汉理工大学毕业设计（论文）

ABSTRACT

With image recognition in all areas of society widely used, image recognition technology also has become a computer vision and image registration in the field of one of the main research direction. The paper from different angles on image recognition, matching. The main research the affine invariant image recognition technology in areas of application.

Affine transformation is a kind of important linear geometry transform, many imaging process and its change can model into affine transformation, such as image in the image plane of translation or rotating can model of translation into coordinate system or rotating, imaging range change can model of different coordinate system to ask transformation. If a graphics has some kind of nature or a certain amount, in parallel projective, if the same, says the nature of affine invariant properties, this volume called affine invariant. After affine corresponding to them is constant. Sex, combining with the element is affine invariant properties (that is, the affine total points corresponding to the line into the line, the total points of the dot into line with the line points). A parallelogram in affine under the corresponding like or a parallelogram.

This thesis used the K-means, with color component (or geometric characters) as coordinates parameter, scene graph clustering. And then after segmentation. Through the clustering characteristics after the extraction point, to match, so as to achieve the affine invariant proof of the problem. For geometry transform road signs image analysis is more accurate, in extracting and matching, with three method are demonstrated.

Keywords: K-means：Affine invariant; Clustering; Feature extraction; Affine transformation

II

武汉理工大学毕业设计（论文）

绪论

在现实生活中，往往人的视觉系统辨别物体的能力会出现偏差，比如同一个物体，在从不同的角度，不同的光照亮度，不同的高度来观察时，所得到的效果以及结论可能就不同。但是，在计算机信息技术高度发达的现在，用计算机进行识别物体已经越来越普及，如何准确高效的识别物体也逐渐引起了人们的关注，社会对于图像处理和识别的要求也越来越高。

在数字图像处理高度发展的今天可以看出，图像在人类感知中扮演最重要的角色。据调查研究表明：60%~80%的信息来自图像，并且成像及其可以覆盖几乎所有的电磁波谱。而现在，计算机技术的发展和通信手段的发展为图形提供了客观的可能性，以FFT为代表的数字信号处理算法和现代信号处理方法的准确性、灵活性和通用性。为数字图像技术的发展铺平了道路。而对于形状的识别，检测和判断，一直是数字图形技术不可或缺的一部分。

仿射不变性的理论基础是仿射变换。仿射变换是一类重要的线性几何变换，许多成像过程及其变化可以模型化为仿射变换，如图像在图像平面上的平移或旋转可以模型化为坐标系的平移或旋转，成像距离的变化可以模型化为不同坐标系之问的变换。图像在仿射变换下保持不变的特征称为仿射不变特征。仿射不变特征在遥感数据匹配、图像目标识别等方面都有广泛的应用。

仿射不变特征可分为全局和局部仿射不变特征。利用整幅图像的信息提取的不变特征是全局不变特征。Hu于1962年提出Hu矩特征J，此后矩特征被广泛应用，Yang利用仿射几何特性构造了一种交叉加权矩(Cross—WeightedMoment)并证明了其对仿射变换具有不变性，Esa Rahtu将概率模型引入图像不变特征构造，提出了多尺度自卷积(Multi—Scale Autoconvolution，MSA) 变换方法，利用MSA提取的不变特征具有良好的抗噪声能力和仿射不变性。

现在我们常用的仿射不变性的特征提取方法是仿射不变性局部区域特征提取。图像的局部不变特征在图像匹配、目标识别、全景拼接、图像检索等需要确定图像问匹配位置的领域有广泛的应用．局部不变特征包括两个基本的问题：首先，在哪里提取特征，即需要在图像中首先确定提取特征的位置或局部区域；其次，提取什么特征，即在前面提取的位置或局部区域中计算某种局部不变特征描述。

论文主要是基于局部仿射不变性理论的基础上，提出了一直八个方向提取仿射不变特征点的算法，算法是基于聚类的理论基础得出的。论文通过聚类的方法在局部不变的区域内，对路标图像分八个方向提取特征点，特别是对几何变换的路标图像，其识别能力较为明显。

1

武汉理工大学毕业设计（论文）

1 论文工作及章节安排

1.1论文的主要工作

论文主要的工作是实现对路标的识别，仿射不变性的证明，识别不同的路标以及相同路标的变换后的仿射不变性，围绕如何有效的提取路标图像的特征点并加以匹配。

1.2论文的组织结构

论文首先对现有形状分析方法进行了总结和分析，以确定全文的研究目标和出发点；然后根据不同的应用场合对形状仿射不变特征提取和形状匹配的需求，研究了形状的相似不变特征提取、仿射不变特征提取、完整形状的匹配和缺损形状的匹配，论文整体框架和章节安排。

第一章概述了论文研究的背景及意义，介绍了论文的主要工作和组织结构。

第二章对所有做的路标识别绘出一个大致的框架和步骤。现有的理论基础进行对比分析，并选出适用于自己的理论基础，同时，选出最优方案。在回顾以往方案的基础上，对比分析，分析其各个方案的优劣，突出所选用的方案优点，找出所需要的软件、知识、书籍等，为自己找出算法和理论做好先前工作。主要分析了所选软件MATLAB和VC++的去吧和实用性，方便性。最后选择MATLAB 为编程工具。同时对现有的仿射不变性的特征提取方法进行了简要的分析，得出想要的结论。

第三章主要讲的是论文所用的理论基础，顺序结构是从导入图像开始，一直到匹配识别图像结束的理论。首先讲的是如何对图像进行预处理，在图形导入之后，首要要做的便是预处理，而随着数字图像技术的高速发展，滤波技术的方式和多样性也逐渐增多，同时，计算机所能识别的图像，只是简单的0、1数据，那么二值化是必不可少的，而最后经过预处理所得到的图像，针对其分析可以知道，要想有效的快速的提取出特征点，算法设计是必要的，但是理论基础更为重要。在对图像进行分割时。分割所用到的技术便是聚类，K-means聚类法可以有效的聚类，而且可以到处想要处理的图像部分，K-means理论基础较为复杂，所涉及到的数据比较多，计算难度较大。仿射不变性的特征便是仿射不变，而仿射不变是基于几何变换的基础上得来的。在现有的理论中，Hu不变矩对于几何变换的处理非常有效，论文介绍了Hu不变矩的由来以及生成形式等。最后，本章节着重讲了仿射变换的由来，从物体到相机，以及成像的变换等都有所讲解，可以直观的理解何为仿射不变性，仿射不变性特征提取所要做的工作又是什么等一些知识。

第四章主要如何进行仿射不变性的特征提取。首先，对于现有的技术进行总结归纳并进行实验验证，同时，得出现有的特征提取方法的局限性和有效性。提出算法，来优化现有的特征提取算法。论文利用三个特征匹配算法对路标图像进行识别，比较得出结论，准确性好，。论文提出了一种新的算法，八向识别法，在基于很好的局部聚类之后得到的图像进行八个方向识别，这样就可以得到几何变换仿射不变的证明。通过实验验证所得结论，可以发现，该算法实用性较强，

2

武汉理工大学毕业设计（论文）

准确性较高。

第五章主要研究了算法对于加噪之后以及形变后的图像的识别，通过变换之后的图像模糊，对于计算机的识别难度较大，而如何可以讲模糊的图像识别出来，是一大问题。本章算法所用的三种识别方法，可以识别这类图像。最后，通过实验统一分析了论文所提形状仿射不变特征有效性和适用性。

第六章为全文的总结与展望，对本文需要进一步研究的内容进行了阐述，并对可能的研究方向进行了展望。

2 结构设计与方案选择

2.1 仿射不变性的特征提取系统结构

仿射不变性的特征提取，其所针对的对象是图像，本文主要采样目标是路标的采样和识别，由于在路标识别的过程中，其背景比较复杂，并且各种干扰比较大，所以用传统的，或者新型的图像处理方法会不准确。本文采用的主要是首先对采集到的图像进行滤波、去噪等预处理，从而可以得到其先对单一、容易让计算机识别的图像。在处理图像时，首先要用K-means算法将所要处理的图像分割出来，然后再对其进行二值化出来，将分割出来的图像转换成计算机可以识别的二值化图像。然后在对其进行膨胀腐蚀出来，可以得到相对统一，大小适中的黑色区域，对这些黑色的局部稳定区域，进行分析可以得到一些仿射不变的特征区域，对这些特征区域用论文中的算法提取出特征变量，证明其仿射不变性质。运用进行匹配校正证明。显示匹配结果。其系统框图如图2-1所示：

3

武汉理工大学毕业设计（论文）

图2-1 放射不变系统框图

2.2 特征提取的方案选择

随着现在数据处理工具、方法逐渐的完善，对特征提取的方案选择性也越来越强。同时，各种数据处理的软件功能也越来越完善、简洁。

4

武汉理工大学毕业设计（论文）

2.2.1 数据处理软件的选择

对数据和图像进行处理，有两个比较好的软件，一个是matlab ,一个是VC++。两者各有优劣。

2.2.1.1 用MATLAB进行处理

MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks 公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。本文主要用到的是MATLAB部分。

MATLAB是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。

Matlab是一个高级的矩阵/阵列语言，具有简单易用的程序语言，它包含控制语句、函数、数据结构、输入和输出和面向对象编程特点。用户可以在命令窗口中将输入语句与执行命令同步，也可以先编写好一个较大的复杂的应用程序（M文件）后再一起运行。新版本的MATLAB语言是基于最为流行的C++语言基础上的，因此语法特征与C++语言极为相似，而且更加简单，更加符合科技人员对数学表达式的书写格式。使之更利于非计算机专业的科技人员使用。而且这种语言可移植性好、可拓展性极强，这也是MATLAB能够深入到科学研究及工程计算各个领域的重要原因。

MATLAB是一个包含大量计算算法的集合。其拥有600多个工程中要用到的数学运算函数，可以方便的实现用户所需的各种计算功能。函数中所使用的算法都是科研和工程计算中的最新研究成果，而前经过了各种优化和容错处理。在通常情况下，可以用它来代替底层编程语言，如C和C++ 。在计算要求相同的情况下，使用MATLAB的编程工作量会大大减少。MATLAB的这些函数集包括从最简单最基本的函数到诸如矩阵，特征向量、快速傅立叶变换的复杂函数。函数所能解决的问题其大致包括矩阵运算和线性方程组的求解、微分方程及偏微分方程的组的求解、符号运算、傅立叶变换和数据的统计分析、工程中的优化问题、稀疏矩阵运算、复数的各种运算、三角函数和其他初等数学运算、多维数组操作以及建模动态仿真等。

MATLAB出色的图形处理功能。自产生之日起就具有方便的数据可视化功能，以将向量和矩阵用图形表现出来，并且可以对图形进行标注和打印。高层次的作图包括二维和三维的可视化、图象处理、动画和表达式作图。可用于科学计算和工程绘图。新版本的MATLAB对整个图形处理功能作了很大的改进和完善，使它不仅在一般数据可视化软件都具有的功能（例如二维曲线和三维曲面的绘制和处理等）方面更加完善，而且对于一些其他软件所没有的功能（例如图形的光照处理、色度处理以及四维数据的表现等），MATLAB同样表现了出色的处理能力。同时对一些特殊的可视化要求，例如图形对话等，MATLAB也有相应的

5

武汉理工大学毕业设计（论文）

6 功能函数，保证了用户不同层次的要求。另外新版本的MATLAB 还着重在图形用户界面（GUI ）的制作上作了很大的改善，对这方面有特殊要求的用户也可以得到满足。

2.2.1.2 用VC++进行处理

Microsoft Visual C++，（简称Visual C++、MSVC 、VC++或VC ）微软公司的C++开发工具，具有集成开发环境，可提供编辑C 语言，C++以及C++/CLI 等编程语言。VC++整合了便利的除错工具，特别是整合了微软视窗程式设计（Windows API ）、三维动画DirectX API ，Microsoft .NET 框架。目前最新的版本是Microsoft Visual C++ 2010。

Microsoft Visual C++是Microsoft 公司推出的开发Win32环境程序，面向对象的可视化集成编程系统。它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2，WinSock 网络、3D 控制界面，它以拥有“语法高亮”，IntelliSense （自动编译功能）以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及建置系统以预编译头文件、最小重建功能及累加连结著称。这些特征明显缩短程式编辑、编译及连结的时间花费，在大型软件计划上尤其显著。

但在图像处理应用中，其编程量相对复杂。

综上所述。由于可以用较小的工作量来处理大量的图像数据，选择MATLAB 作为应用软件。

2.2.2 特征提取方案选择

2.2.2.1 利用仿射几何的仿射不变性提取方法

仿射几何的仿射不变性提取方法是通过提取质心来作为特征点来构造仿射不变性模型的。因为特征点的提取容易受噪声、灰度变化等的影响，所以质心成为理想的选择。区域的质心可以通过下面的公式求解：

f (x,y)dxdy f (x,y)dxdy

x x =???? （2-1） f (x,y)dxdy f (x,y)dxdy

y y =???? （2-2） f ( x, y )为像素点( x, y )处的灰度值。不难证明, 对应区域的质心也满足仿射变换关系。为了形成区域, 需要提取不少于3个的质心, 为此我们引入扩展质心的概念, 并对扩展质心给出了更一般性的定义。首先, 设fe ( x, y ) 为图像灰度函数f ( x, y )各次幂的组合, 并称为扩展函数, 如下式所示:

武汉理工大学毕业设计（论文）

7 112121(,)(,)(,)...(,)n e n n f x y a f x y a f x y a f x y a ααα--=++++ （2-3）

式中 为扩展函数的系数， 为扩展函数的幂数。用

代替式2-1、2-2中的 就可以得到新的点(,)e e x y ，我们称之为扩展质心（为

了简便，有时也简称为质心）：

f (x,y)dxdy f (x,y)dxdy e e

e e x x =???? （2-4）

f (x,y)dxdy f (x,y)dxdy e e e e

y y =???? （2-5） 不难证明，两图像中对应区域的扩展质心也满足仿射变换。

假设已经得到了区域的质心 和扩展质心 ，那么整个区域被它们的连线分割成两部分, 如图1所示。然后再分别计算两部分的质心, 并标记为 和, 同样, 连接 ,整个区域分成两部分, 分别计算两部分的质心,记为 和 ,， 连接 得质心 和 , 如此循环迭代, 可以得到任意多个质心坐标。但是需要注意的是, 得到的质心有可能出现重叠, 特别是当区域的结构和灰度值近似 成对称情况时。

图1 质心连线对仿射区域的分割

提取出质心后, 接下来利用它们构造合适的区域。作为最简单的情况, 3 个点组成的三角形经常被使用到。但是当组成三角形的3个顶点接近共线时, 三角形的面积将会非常小, 那么计算得到的特征值将会非常大甚至无穷。由噪声等引起的顶点位置少许的变化将会导致特征值非常大的改变, 即所谓的病态现象。为了解决这个问题, 用四边形作为基本的区域来构造特征值。选择四边形的4个顶点中, 有两个是把整个区域分割成两部分的质心, 两个是两分割区域的质心, 这样可以避免四边形的4个顶点共线或者接近共线情况, 如图2所示。

1p 12,,...n a a a 121,,...n ααα-(,)e f x y (,)f x y 3p 2p 4p 13p p 14p p 7p 8p 5p 6p

武汉理工大学毕业设计（论文）

8

图2 由质心形成的四边形

假设质心i p 的坐标为(,)i i x y ，区域1536p p p p 的面积可以通过下面的公式计算得到：

1

11

11536

556

63

33

31111112

2

11x y x y s abs x y abs x y x y x y ????

???

?

=+????????????

（2-6） 假设已经得到了12个质心1212,,...,p p p ，按照上述规则，可以得到5个四边形，即为1324p p p p 、1536p p p p 、1748p p p p 、29310p p p p 、211412p p p p ，他们的面积分别为12345,,,,S S S S S ，那么可以得到如下仿射不变特征矢量：

1234

(,,,)F f f f f = （2-7） 式中1i

i i s f s

+= 。

2.2.2.2 局域仿射不变性特征点提取

局部仿射不变性的提取，是用图像中灰度极值点作为“关键点”，灰度极值不受仿射变换的影响，因而其“关键点”在仿射变换前后易检出。但是图像中灰度极值点的数量不确定，也易受遮障和噪声等因素的影响。为使“关键点”能够较好克服上述影响，论文将选择单一的灰度极值点扩展到根据图像信息选择某个灰度取值范围，通过阀值分割获得图像若干块状连通区域，将区域的几何中线点作为“关键点” 。

经过比较和验证，如果以路标图像为验证对象，局部仿射不变性提取方法，会更加简单、实用，效果也更加明显。所以。选择用局域仿射不变性特征点提取的方法，来进行特征点的提取工作。

武汉理工大学毕业设计（论文）

3仿射理论基础

本文主要做的是对路标图像的处理，对路标图像的处理分为图片预处理、图像分割等几大模块，每个部分所运用的理论基础有很多区别。

3.1 图像的预处理

在MATLAB读取到图像之后，图像往往有缺损、雾化、噪化等现在，如果直接对读取的图像进行分割提取，得到的结果的准确度很低。那么，也就意味着要对图像进行预处理。图像的预处理包括去噪、二值化等子模块。

3.1.1 滤波方法

论文采用均值滤波的方法。均值滤波是典型的线性滤波算法，其采用的主要方法为邻域平均法。即对待处理的当前像素点(x，y)，选择一个模板，该模板由其近邻的M个像素组成，求模板中所有像素的均值，再把该均值赋予当前像素的算术平均值，作为邻域平均处理后的灰度。

该方法运算简单。对高斯噪声具有良好的去噪能力。均值滤波可归结为矩形窗加权的有限冲激响应线性滤波器，第一个“旁瓣”比主峰大约低13分贝。因此，均值滤波相当于低通滤波器。这种低通性能在平滑噪声的同时。必定也会模糊信号的细节和边缘，即在消除噪声的同时也会对图像的高频细节成分造成破坏和损失，使图像模糊。均值滤波对高斯噪声，乘性噪声的抑制是比较好的，但对椒盐噪声的抑制作用不好，椒盐噪声仍然存在，只不过被削弱了而已。为了改善均值滤波细节对比度不好、区域边界模糊的缺陷，常用门限法来抑制椒盐噪声和保护细小纹理。用加权法来改善图像的边界模糊，用选择平均的自适应技术来保持图像的边界。

3.1.2 二值化

滤波之后，我们就要对图像进行二值化，因为我们读取的图像一般都是有很多色彩和色素，而计算机所能识别的像素只有黑白两种，所以，我们必须要多其进行二值化。

一幅图像包括目标物体、背景还有噪声，要想从多值的数字图像中直接提取出目标物体，最常用的方法就是设定一个阈值T，用T将图像的数据分成两部分：大于T的像素群和小于T的像素群。这是研究灰度变换的最特殊的方法，称为图像的二值化（BINARIZATION）。

图像的二值化，就是将图像上的像素点的灰度值设置为0或255，也就是将整个图像呈现出明显的只有黑和白的视觉效果。我们在做二值化处理时，通常用到的方法有全局二值化和局部二值化两种。全局二值化的定义是设定一个全局的阈值T，用T将图像的数据分成两部分：大于T的像素群和小于T的像素群。将大于T的像素群的像素值设定为白色（或者黑色），小于T的像素群的像素值

9

武汉理工大学毕业设计（论文）

10 设定为黑色（或者白色）。全局二值化，在表现图像细节方面存在很大缺陷。为了弥补这个缺陷，出现了局部二值化方法。局部二值化的方法就是按照一定的规则将整幅图像划分为N 个窗口，对这N 个窗口中的每一个窗口再按照一个统一的阈值T 将该窗口内的像素划分为两部分，进行二值化处理。

3.2 图像分割技术

在现在图像处理技术以相对成熟的今天，图像分割的方法也越来越多，相对于其他的图像分割方法，论文选择了K-means 算法进行图像分割。

3.2.1 K-means 算法介绍

J ．B ．MacQue 既在1967年提出的K-means 算法，是一种被广泛应用于科学研究和工业应用中的经典聚类算法。

K-means 算法的核心思想是把一个数据对象划分为k 个聚类，使每个聚类中的数据点到该聚类中心的平方和最小，算法处理过程：

输入：聚类个数k ，包含九个数据对象的数据集。

输出：k 个聚类。

(1)从疗个数据对象中任意选取k 个对象作为初始的聚类中心。

(2)分别计算每个对象到各个聚类中心的距离，把对象分配到距离最近的聚类中。

(3)所有对象分配完成后，重新计算k 个聚类的中心。

(4)与前一次计算得到的k 个聚类中心比较，如果聚类中心发生变化，转(2)，否则

转(5)。

(5)输出聚类结果。

K-means 算法的工作流程如图3.1所示。

首先从n 个数据对象中任意选择k 个对象作为初始聚类中心；而对于所剩下的其它对象，则根据他们与这些聚类中心的相似度(距离)，分别将他们分配给与其最相似的(聚类中心所代表的)聚类。

然后再计算每个所新聚类的聚类中心(该聚类中所有对象的均值)。不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下：

2

1||i k i i p c E p m =∈=-∑∑ （3-1）

其中E 味数据库中所有对象的均方差之和；

P 为代表对象的空间中的一个点；

i m 为聚类的Ci 的均值（都是多维的）。

公式（3-1）所示聚类标准旨在使所获得的k 个聚类具有以下特点：各聚类本事尽可能的紧凑，从而各聚类间尽可能的分开。

武汉理工大学毕业设计（论文）

图3.1 K-means流程图

K-means算法优点是可以处理大数据集，K-means算法是相对可伸缩的和高效率的，因为它的计算复杂度为O（nkt），其中n为对象个数，k为聚类个数，t 为迭代次数，通常有t n，k n，因此它的复杂度通常也用O（n）表示。

下面以一组二维数据为例，简要说明K-means的聚类过程。

11

武汉理工大学毕业设计（论文）

12

表3-1 一组二维数据

空间分布如图3-2所示：

图3-2 空间分布

输入k=3，1k =1x ，2k =2x ，3k =3x 。

算法初始分别选定前三个数据作为初始聚类中心，进行一次迭代后的聚类如图3-3所示。

图3-3 一次迭代

经过反复迭代后，最后的最佳聚类结果如图3-4所示。

武汉理工大学毕业设计（论文）

13

图3-4 聚类结果

此外K-means 算法不依赖于顺序，给定一个初始类分布，无论样本点的顺序如何，生成的数据分类都一样。

3.2.2 K-means 图像分割

图像分割是指将图像分解成各具特性的区域并提取出感兴趣目标的技术和过程。它是图像理解、模式识别和计算机视觉领域中一个十分重要又十分困难的问题，是计算机视觉技术中首要的关键步骤。图像分割的基础就是像素间的相似性和跳变性。所谓的相似性是指在某个区域内像素具有某种相似的特性；所谓跳变性，是指特性的不连续。所以图像处理的关键之处就是对包含有大量各式各样景物信息的图像进行分解。分解的最终结果是图像被分解成一些具有某种特征的最小成分，称为图像的基元。相对于整幅图像来说，这种基元更容易被快速处理。

图像分割在工业自动化、在线产品检测、生产过程控制。文档图像处理、遥感和生物医学图像分析、图像编码、保安监视，以及军事、体育和农业工程等方面已得到广泛的应用。

K-means 算法在图像分割的应用，主要是在灰度的基础上，通过聚类分析，提取出想要处理的图像部分。通过改变K 值的不同，可以提取不同的图像部位。简单实用。

论文是利用K-means 算法，将图片PIC 中的红色分量，论文软件计算出阀值的大小，根据阀值的大小进行分割和提取。

3.3 Hu 不变矩

不变矩理论是模式识别和计算机视觉中的一个重要内容。常用的基于区域的矩不变理论最早由Hu 提出来, 并获得不断发展和广泛的应用。Hu 矩不变量提出以后, 已经被应用于图像、字符识别以及工业质量检测等许多领域。但是, Hu 矩不变量是基于区域的, 而且与图像的灰度值密切相关, 计算量大。

Hu 不变矩应用较为广泛，其理论较为复杂，论文对其进行了简单的分析。设f ( x, y )是一幅数字图像, 其( p + q )阶矩定义为

11(,)M N

p q pq x y m x y f x y ===∑∑ （3-2）

武汉理工大学毕业设计（论文）

14 其中p ，q 的取值范围为（0,1,2，…）。

其（p+q ）阶中心矩定义为：

0011()()(,)M N

p q pq x y x x y y f x y μ===--∑∑ （3-3）

1962年, Hu 将代数不变量理论应用于上述尺度规范化矩, 构造出如下7 个著名的Hu 矩不变量：

12,00,2φμμ=+， （3-4）

2222,00,21,1()4φμμμ=-+， （3-5）

2233,01,22,10,3(3)(3)φμμμμ=-+-， （3-6）

2243,01,22,10,3()()φμμμμ=+++， （3-7）

…

这些Hu 不变矩具有旋转、平移和尺度不变性。

4 算法的设计

论文主要工作是对路标图像的识别以及仿射不变性的提取。在传统的算法中，在对路标的提取中，往往做不到准确，论文以一种新的算法为基础，设计设别几何变换下的路标。

4.1 传统仿射算法

在传统的路标设别算法中，大部分都是用中心法识别。因为目标区域具有很强的方向性。对图像从左至右进行扫描，记录每一列目标区域点的数目，目标区域点的数目最多的一列作为基准，计算基准两边目标区域点的数目，当左边点的数目远远大于右边的时候，表示箭头朝左边；反之，箭头朝右。

下面以一组路标为例进行识别，如图4-1所示：

图4-1 路标原理图

通过上述图像我们可以更加直观地体现中心法识别的思想，从左边往右扫秒

武汉理工大学毕业设计（论文）

15 得到中心轴，并用红线标记，从上图可以看出，中心轴左边的黑色像素点的数目为170，右边的黑色像素点的数目为355，355>>170，可以推断出右边肯定有一个箭头。

同理，也可以知道上方有一个箭头。通过箭头判断，就可以知道该图片是禁止右前。识别结果如图4-2所示：

图4-2 识别结果

但是在该方法识别路面路标时，所得的结果会很不准确，因为在路面路标识别时，会出现几何变换问题，入拉伸，收缩，旋转等。得不到想要的结果。

4.2 精简算法的实现

在对路标图像的，方法有很多种，论文采用的是精简算法，论文采用三种方法来识别路标的标志，三种方法分别为八向识别法、链码识别、Hu 矩识别采用Hu 矩识别是判断清晰的，稳定的图像，链码识别也是如此，而八向识别法则是对加噪或者缺失的图像进行判断。下面我们一一来进行介绍。

4.2.1 八向识别法

在做路标的基本处理时，发现路标图像，特别是二值化图像时。图像具有一个共性，那就是在指示方向性时，箭头的标示会特别明显，而且是一个极其稳定的局部区域，而且，仅仅在路边识别时，会发现，如果在路标区域内，正分八个方向，如图4-3所示，那么，根据提取到的有效的特征点，就可以判断出路边的类型。

图4-3路标二值化和特征标记

由图3-7可以看出，将路标图像分为八个方向判断，找出路标的中心，然后竖直方向可以看出上下有特征点，特别是正上方，有一个明显的局部稳定区域，可以检测到箭头的位置，同样，在水平方向，也是如此，在另外两个方向，是为了判断是否有禁止符号，如有禁止符号，能显示的特征值为1，即为禁止方向通行，没有，则显示该方向可以行使。

武汉理工大学毕业设计（论文）

16 4.2.2 链码识别

利用边界链码串可以得到目标区域几个重要的几何形状特征，例如，区域周长、形状参数、体态比等。

但能否利用链码来识别路标我们需要考虑一下几个方面，区域周长、区域面积跟图形的大小、边界链码的光滑程度直接相关，不能用于识别。体态比有跟图像被拍摄的角度关系很大，因此唯一可能可行的是利用其密集度。如表4-1所示，可以直观的看出其特征及其结果

，

，

表4-1 链码识别结果从上述表格可以看出，四个标准的图片的密集度一次增加，分别为2.3785，

2.4776，2.8814，1.9101，初看好像有能区分的可能，但是从第一、二组图片可以看出，实际采样路标的密集区比标准路标的密集度相差甚大，没法仅仅利用密度比来加以区分。究其原因，实际的图片在拍摄过程当中，因为拍摄距离、光线、相机本身等产生干扰，导致图片失真，在预处理阶段，又导致图片像素错分，使得实际的路标的密集度远离标准路标的密集度。

4.2.3 Hu 矩识别

不变矩的方法是一种比较经典的特征提取方法，1962年，Hu 发表了他一篇关于应用图像2-D 矩进行模式识别的论文，在该论文中，Hu 首先提出了代数不变矩的概念，并给出了一组基于通用矩组合的代数矩阵不变量，这些矩具有平移、旋转、和尺度不变性，被称为Hu 不变矩，已被成功应用于很多领域。

p+q 阶普通矩的定义：

11(,)M N

p q pq x y m x y f x y ===∑∑ （4-1）

p+q 阶中心矩的定义：

22

43,01,22,10,3253,01,23,01,23,01,2()()(3)()/()3

φμμμμφμμμμμμ=+++=-++- （4-2）

归一化中心距：

002,()2

pq pq r p q y r μμ++== (4-2)

武汉理工大学毕业设计（论文）

17

Hu 的二阶和三阶中心距构造的七个不变矩1234567,,,,,,φφφφφφφ。

在对Hu 的计算中，论文以限速40的四幅图像、禁止左前转5幅图像、禁止右前转5幅图像的Hu 矩1237,,,φφφφ进行计算分析。其分析图像如表4-2、4-3、

表4-2 限速40Hu 矩统计

表4-4禁止右前转Hu 矩统计

分析表格可以发现，同一类路标的Hu 距有区别，但差别较小，不同类的路标之间的Hu 矩差别很大，利用这些Hu 距就可以很好地区分不同的路标。每个图像涉及到4个Hu 距，直接求取带识别的路标到数据库中各类路标的欧式距离，会因为每个Hu 距的绝对大小的差异导致权重失衡。因此引入相对误差的概念，求取带识别的路标Hu 距的误差百分比到数据库中各类路标的距离，距离越小，表明与给类的特征更加相似。

通过上述三种方法，我们可以发现预处理是八向识别法和Hu 矩识别法的前提和基础，只有经过合理的预处理，得到路标特征，方便后续操作。八向识别法

武汉理工大学毕业设计（论文）

18 需要寻找‘中心点’，再统计‘点’八个方向的像素个数，比较像素的多少，再判断箭头的方向。Hu 距需要计算几何中心，需要计算中心距，再归一化，最后计算Hu 距，计算比较复杂，计算量较大，难以实现实时路标识别。

上面我们分析过，只是做路标的简单识别，没有做到在路标经过几何变换后的识别，如果路标经过旋转、平移、斜视、等比例放大缩小、拉伸、加噪之后，是否能够识别呢？论文加入了一些算法，因为在这些几何变换中，最难做出识别的便是旋转，平移，斜视等等，可以通过校正的方法很简单的就可以还原，而拉伸放大缩小在上述算法中没有影响，对旋转的处理，因为计算机的判断只是以所能读到我图像为准，那么在导入一个图像之后，论文加入了一个循环。当导入的图像利用三种匹配方法都没有得到匹配值时，因论文在没有得到匹配值时显示为禁止通行，此时我们对图像进行旋转，因为一周是360度，那么每次旋转的角度为10度，做36次旋转，在这 36次旋转中，如果有一种旋转，在匹配中，得到匹配值，那么，就说明此路标以被识别，循环结束，得出结果。如果在36次旋转结束仍没有得到匹配值，那么结果显示为禁止通行。实验处理结果如图4-4 、4-5所示：

图4-4 左旋90度

本文来源：https://www.bwwdw.com/article/y07q.html