几何图形的识别和编辑的设计与实现

内容摘要
  本论文主要讲述了图像文件（bmp）文件格式下中简单图形的识别，主要是直线和圆的识别，这在工程图的识别和其他领域中都有很多的应用。
  第一章到第三章主要介绍了在本论文中涉及到的知识及算法。
  第四章是程序的实现方法和过程及结果等。
  第五章是结束语
关键词：
图形识别 、图像处理、霍夫变换、单义域、多义域    

Content Abstract

  This thesis is mainly focused on the Simple Graph Recognition in Image of .bmp. The Line Recognition and the Circle Recognition, these is good use of on Engineering Graphicis.
   The first part to the third part is mainly focused on some points and algorithms for my thesis.
  The fourth part is about the methodologys 、courses and outcome of the program.
  The last part is the end-words.
Key Words
图形识别    (Graph Recognition)
图像处理    (Image Processing)
霍夫变换    (Hough Transform)
单义域      (Unity Region)
多义域      (Multi-Region)

计算机技术的发展，使人类社会进入了信息化和自动化，计算机智能识别也随着计算机的发展得到了迅速的发展。特别是图形图像的计算机处理技术更是有了前所未有的进步和应用。计算机识别也逐渐的从图形图像处理的大环境下分离出来作为一门新的高科技研究领域出现。图形图像的识别涉及到的学科很多，包括数字信号处理、工程数学、信息论、运筹学、等，它与计算机、自动化、生物学、关学、视觉心里和生理学、人工智能、智能信息处理等众多领域交叉、综合集成，有广泛的应用。
本论文实现的是基础的图形识别，bmp图像文件格式中对图形的矢量化。识别基本的图元直线和圆。直线和圆是二值图像中最基本的组成元素，也是最常见的图形元素。在工程图的数字化识别中有很大的应用。
关于理想情况的几点说明：
1. 所识别的bmp图像文件是经过处理的，没有“噪音”等，在本论文中直接采用的是用Windows中的画图软件画出的图像。
2. 本论文中图像中的图元都是单一的线性，即线宽是一个象素的情况。

第二节 在工程图的识别中常用的方法
图形的识别最主要的是图形特征的提取，在这个阶段，常用的方法是全局特征方法（包括：不变距，自回归模型、傅立叶描述符、霍夫变换等），全局特征的特征提取方法是理论比较完善的，计算过程比较清楚。针对不同的特征提取处理，采用相对应的模式匹配方法来将图形分类，模式识别迄今已有很多方法，有模板匹配、统计模式识别、句法模式识别、模糊识别和神经网络识别等。
在二值图像的处理中，人们常用的数据结果有游程编码－考虑了扫描行上相邻象素间的相关性；行相邻图法（Line Adjeceney Gragh），是由Pavlidis提出的一种二值图的数据结构，LAG还考虑了相邻行黑游程之间的相邻关系，遍历时很方便；BAG（Bloek Adjeceney Gragh）是由余斌提出的，它是相邻图LAG在两个方向上的推广。在本论文中就是利用了LAG的数据结构思想与c++ builder的数据结构相结合的方法即：用下一个象素点是与链表头相邻还是和尾相邻来描述其相邻的关系。
本论文中对交点的处理。目前对交点的处理有下面几类算法：
1. 基于网格算法，该算法是通过网格加大搜索步长来跳过交点。
2. 基于图段合并的算法，是根据交点处行程段的连通性，以交点为界将图线分割成图段，记录各段之间的连接及从属关系，然后连接或延长各分支图段，然后得到整条图线。
在本论文中采用了第二种方法，基于图段合并的算法。

 算法及数学基础
1. 霍夫变换（Hough Transform）
霍夫变换是图像处理中从图像中识别几何形状的基本方法之一。其基本思想就是把图像平面上的点对应到参数平面上的曲线，最后通过统计特性来解决问题。自1962年Hough公布了该算法以来，由于其良好的抗噪声性能和对部分遮盖的不敏感等特性，霍夫变换在模式识别领域得到广泛的应用，如直线、圆、椭圆、矩形等几何图形检测，任意形状区域的边界提取，二维或三维运动的参数估计等。
下面就于本论文相关的直线和圆的识别进行简单的介绍。
1.1  霍夫变换识别直线
霍夫变换识别直线，是将图像空间中的一点变换为参数空间中的一条直线。图像空间中同一直线上的点，经霍夫变换所形成的直线相交于参数空间中的一点，该点坐标代表图像空间中直线的斜率及截距。利用累加数组累计参数空间中通过该点的直线条数，即代表图像空间中直线上的点数。
 
设已知一黑白图像上画了一条直线，要求出这条直线所在的位置。我们知道，直线的方程可以用 来表示，其中k和b是参数，分别是斜率和截距。过某一点 的所有直线的参数都会满足方程 。即图像空间中的一点 确定了参数空间中的一族直线。方程 在参数k--b平面上是一条直线。这样，图像x--y平面上的一个前景像素点就对应到参数平面上的一条直线。
霍夫变换识别直线的算法描述如下：
Step1. 初始化一块缓冲区，对应于参数平面，将其所有数据置为0。
Step2. 对于图像上每一前景点，求出参数平面对应的直线，把这直线上的所有点的值都加１。
Step3. 找到参数平面上峰值点的位置，这些位置的坐标就是原图像上直线的参数，每个位置对应于原图像上的一条直线。
上面是霍夫变换识别直线的基本思想。在实际应用中， 形式的直线方程没有办法表示x=c形式的直线（这时候，直线的斜率为无穷大）。所以实际应用中，是采用参数方程：
 
这样，图像平面(x, y)空间上的一个点就对应到参数 空间中的一条正弦曲线上。在变换后的空间中这条正弦曲线上的任意一点对应于原始图像平面(x, y)空间的一条直线，这条直线必通过 这个点，而(x, y)空间中所有共线的点经过变换后所对应的各正弦曲线都相交于一点。

霍夫变换识别圆
1） 半径已知的圆的识别
利用霍夫变换检测出半径已知的圆形，是将图像平面上的每一点对应到参数平面上的一个以已知半径为半径的圆。经过霍夫变换，在参数平面上得到圆相交于一点，这个点的坐标即为原图形坐标平面上待识别的圆心坐标。
算法可以简单描述为：取和图像平面一样的参数平面，以图像上每一个前景点为圆心，以已知的半径在参数平面上画圆，并把结果进行累加。最后找出参数平面上的峰值点，这个位置就对应了图像上的圆心。
2） 未知半径的圆的识别
在第一个问题基础上，把参数平面扩大称为三维空间，即x--y--R三维，对应圆的圆心和半径。图像平面上的每一点就对应于参数空间中每个半径下的一个圆，在参数的三维空间中得到一个圆锥。最后找出参数空间中的峰值点，即得到待识别的圆的圆心和半径。

由于霍夫变换具有良好的抗噪声性能和对部分遮盖的不敏感等特性，又不受图像旋转的影响，在很多领域都有广泛的应用，有关霍夫变换的研究和改进也很多。例如广义霍夫变换、随机霍夫变换、快速霍夫变换等等，就是针对直线的霍夫变换也有很多改进算法。由于时间的原因，在本软件中，只是使用了标准的霍夫变换算法。
2. 基于单义域的直线及圆识别算法
霍夫变换为几何图形的识别的一个重要算法，但是由于该标准算法的时间复杂度和空间复杂度都是 ，其中m是参数坐标的维数，虽然有不少针对具体问题（例如直线识别）的改进算法，其在实际使用中也存在计算量大的问题。针对本论文的工作的实际情况，参考文献【1】，并进行了适当的简化，完成了论文的识别部分。下面就对这个基于单义域的识别算法进行简单的介绍。
2.1  多义域的获得
单义域是指对待识别的图形进行分割得到的具有单一的几何意义（线段或圆弧）点的集合。对图片进行从上往下、从左往右的扫描，根据交点进行分割得到多义域，多义域中的点构成一个连通区域。对多义域进行识别并分割得到单义域。
多义域由链表实现。
算法描述如下：
1． 对图形进行从上往下、从左往右的扫描；
2． 对每一个前景点，判断其是否为交点；
3． 将该点与现有的多义域的头（如果其头节点不是交点）、尾（如果其尾节点不是交点）节点进行比较，如果与头节点相邻，将其插入到该多义域的头节点之前；如果与尾节点相邻，将其插入到该多义域的尾节点之后。
4． 如果该前景点不属于任何现有多义域，则以该点为头节点生成新的多义域。
5． 直到图形扫描完毕。
注：交点的判断。
由此得到的多义域将是一个线段、一个圆弧或者线段和圆弧的组合。在后续的识别过程中将把不是单义域的进行分裂。
2.2  最小二乘法拟合直线和圆
最小二乘法首先由Karl Gauss为进行行星轨道预测的研究而提出的。现在最小二乘法已经变成从实验数据来进行参数估计的主要手段。由最小二乘法获得的估计在一定条件下有最佳的统计特性：一致、无偏、有效。它提供给我们一个数学程式，通过它能获得一个在最小方差意义上与实验数据最好拟合助模型。

目    录
第二章 概述 6
第一节 引言 6
第二节 在工程图的识别中常用的方法 6
第三章 论文的工作基础和工作环境 8
第一节 数字图像处理技术 8
1. 图像处理的基本内容 8
2. 主要的图像处理技术 8
第二节 图像格式－BMP格式 9
第三节 算法及数学基础 10
1. 霍夫变换（Hough Transform） 10
2. 基于单义域的直线及圆识别算法 13
3. 主要技术 16
第四章 直线和圆的识别和编辑的实现 17
第一节 系统的层次结构的图示 17
第二节 系统数据结构及类的设计 18
1. 主要类的层次结构 18
2. 图形基类（CShape） 19
3. 图形类（CLine、CCircle） 20
4. 图形容器类（CShapes） 22
5. 点类（CPoint） 23
6. 单义域类（CSegment） 23
7. 基于单义域识别类（CSegments） 24
8. 霍夫变换识别直线类（CHTLine） 25
9. 霍夫变换识别圆类（CHTCircle） 25
第三节 主程序实现 26
第四节 系统功能介绍 26
第五节 总结及展望 31
第五章 结束语 32
参考文献 34