几何图形的识别和编辑

类型：课程设计题目：几何图形的识别和编辑主要是直线和圆的识别，这在工程图的识别和其他领域中都 4 4第二节在工程图的识别中常用的方法 4第三章论文的工作基础和工作环境 6第一节数字图像处理技术 6 6 6第二节图像格式－BMP格式 7第三节算法及数学基础 8 82.基于单义域的直线及圆识别算法 第四章直线和圆的识别和编辑的实现 第一节系统的层次结构的图示 第二节系统数据结构及类的设计 第三节主程序实现 第四节系统功能介绍 第五节总结及展望 错误!未定义书签。第一章概述计算机技术的发展，使人类社会进入了信息化和自动化，计算机智能识别也随着计算机的发展得到了迅速的发展。特别是图形图像的计算机处理技术更是有了前所未有的进步和应用。计算机识别也逐渐的从图形图像处理的大环境下分离出来作为一门新的高科技研究领域出现。图形图像的识别涉及到的学科很多，包括数字信号处理、工程数学、信息论、运筹学、等，它与计算机、自动化、生物学、关学、视觉心里和生理学、人工智能、智能信息处理等众多领域交叉、综合集成，有广泛的应用。识别基本的图元直线和圆。直线和圆是二值图像中最基本的组成元素，也是最常见的图形元素。在工程图的数字化识别中有很大的应用。2.本论文中图像中的图元都是单一的线性，即线宽是一个象素的情况。第二节在工程图的识别中常用的方法图形的识别最主要的是图形特征的提取，在这个阶段，常用的方法是全局特征方法（包括：不变距，自回归模型、傅立叶描述符、霍夫变换等），全局特征的特征提取方法是理论比较完善的，计算过程比较清楚。针对不同的特征在二值图像的处理中，人们常用的数据结果有游程编码－考虑了扫描行上），在两个方向上的推广。在本论文中就是利用了LAG的数据结构思想与c++builder的数据结构相结合的方法即：用下一个象素点是与链表头相邻还是和尾本论文中对交点的处理。目前对交点的处理有下面几类算法：1.基于网格算法，该算法是通过网格加大搜索步长来跳过交点。2.基于图段合并的算法，是根据交点处行程段的连通性，以交点为界将图线分割成图段，记录各段之间的连接及从属关系，然后连接或延长各分支图段，然后得到整条图线。在本论文中采用了第二种方法，基于图段合并的算法。第二章论文的工作基础和工作环境第一节数字图像处理技术将客观世界实体或图片等通过不同的量化(数字化)手段送入计算机，由计算机按使用要求进行图像的平滑、增强、复原、分割、重建、编码、存储、传输等种种不同的处理，需要时把加工处理后的图像重新输出，这个过程称为图像处理。因此，图像处理的含义是用计算机对图像进行加工处理以得到某种预期的效果，它本质上是一种二维数字信号处理技术。1.图像处理的基本内容以改变或强调图像信息的某些特点(增强有用信息，无用信息)，改善图2.描述图像的特征并进行特征抽取和分析。用某个标准衡量并进行分类比较，将抽取的特征归结为一定的模式，这属于模式识别的范围；对图像的某些部分合并或进行重新组织，这种技术是从N—1维的信息用某种算法得到N维的图像，例如计算机视觉就是这样的一种技术。2.主要的图像处理技术它不追究图像客观质量的降低原因。图像的视觉质量是因人而异的，其质量的高低和好坏受观看者的心理、爱好和文化素质等因素的影响。图像的恢复则致力于探索图像质量降低的原因，并尽可能消除图像质量的降低，恢复图彩色数字图像通常是由三个二维数组组成的，其信息量相当大，这给图像的传输、处理、存储和显示等带来很大的负担。但问题的另一方面是图像中又往往存在很多冗余信息，在传输和存储时可以对数字图像进行一定方式的编码，删除图像中的冗余信息，以提高图像传输和存储的效率。不同角度的投影图，通过计算可得到物钵内部的图像，这种技术称为投影重计算机按照一定的客观测度(例如灰度、颜色和几何性质等)将图像中包含的物体和区域从图像中区分出来，称为图像的分割。用适当的数学语言来表示被分割出来的物体或区域的结构和统计特性，或用数学语言表示区域问的关系，称为描述。图像经分别和描述后，可较为容易地分类和识别。第二节图像格式－BMP格式式与显示设备有关，因此把这种BMP图像文件格式称为设备相关位图位图文件的组成位图文件的组成位图文件头BITMAPFILEHEADER位图信息头BITMAPINFOHEADERBYTE第三节算法及数学基础1.霍夫变换（HoughTransform）霍夫变换是图像处理中从图像中识别几何形状的基本方法之一。其基本思想就是把图像平面上的点对应到参数平面上的曲线，最后通过统计特性来解决分遮盖的不敏感等特性，霍夫变换在模式识别领域得到广泛的应用，如直线、下面就于本论文相关的直线和圆的识别进行简单的介绍。图像空间中同一直线上的点，经霍夫变换所形成的直线相交于参数空间中的一点，该点坐标代表图像空间中直线的斜率及截距。利用累加数组累计参数空间中通过该点的直线条数，即代表图像空间中直线上的点数。设已知一黑白图像上画了一条直线，要求出这条直线所在的位置。我们知和截距。过某一点(x,y)的所有直线的参数都会满足方程y=kxx+b。即图像空间中的一点(x,y)确定了参数空间中的一族直线。方程y=kxx+b在参数k--b平面上是一条直线。这样，图像x--y平面上的一个前景像素点就对应到参数平面上的一条直线。Step2.对于图像上每一前景点，求出参数平面对应的直线，把这直线上的所有点的值都加1。Step3.找到参数平面上峰值点的位置，这些位置的坐标就是原图像上直线的参数，每个位置对应于原图像上的一条直线。的直线方程没有办法表示x=c形式的直线（这时候，直线的斜率为无穷大）。上。在变换后的空间中这条正弦曲线上的任意一点对应于原始图像平面(x,y)空过变换后所对应的各正弦曲线都相交于一点。利用霍夫变换检测出半径已知的圆形，是将图像平面上的每一点对应到参数平面上的一个以已知半径为半径的圆。经过霍夫变换，在参数平面上得到圆相交于一点，这个点的坐标即为原图形坐标平面上待识别的圆心坐标。算法可以简单描述为：取和图像平面一样的参数平面，以图像上每一个前景点为圆心，以已知的半径在参数平面上画圆，并把结果进行累加。最后找出参数平面上的峰值点，这个位置就对应了图像上的圆心。应圆的圆心和半径。图像平面上的每一点就对应于参数空间中每个半径下的一个圆，在参数的三维空间中得到一个圆锥。最后找出参数空间中的峰值点，即得到待识别的圆的圆心和半径。受图像旋转的影响，在很多领域都有广泛的应用，有关霍夫变换的研究和改进也很多。例如广义霍夫变换、随机霍夫变换、快速霍夫变换等等，就是针对直线的霍夫变换也有很多改进算法。由于时间的原因，在本软件中，只是使用了2.基于单义域的直线及圆识别算法霍夫变换为几何图形的识别的一个重要算法，但是由于该标准算法的时间复杂度和空间复杂度都是O(Nm),其中m是参数坐标的维数，虽然有不少针对具体问题（例如直线识别）的改进算法，其在实际使用中也存在计算量大的问题。针对本论文的工作的实际情况，参考文献【1】，并进行了适当的简化，单义域是指对待识别的图形进行分割得到的具有单一的几何意义（线段或圆弧）点的集合。对图片进行从上往下、从左往右的扫描，根据交点进行分割得到多义域，多义域中的点构成一个连通区域。对多义域进行识别并分割得到多义域由链表实现。算法描述如下：尾节点不是交点）节点进行比较，如果与头节点相邻，将其插入到该多义域的头节点之前；如果与尾节点相邻，将其插入到该多义域的尾节点之后。注：交点的判断。续的识别过程中将把不是单义域的进行分裂。2.2最小二乘法拟合直线和圆最小二乘法首先由KarlGauss为进行行星最小二乘法已经变成从实验数据来进行参数估计的主要手段。由最小二乘法获一个数学程式，通过它能获得一个在最小方差意义上与实验数据最好拟合助模运用最小二乘法进行圆的拟合公式如下：运用最小二乘法进行直线拟合的公式如下：2.3多义域分裂和单义域的识别对2.1中得到的多义域，运用最小二乘法进行拟合，对于拟合不成功的多义域运用首尾相连最大距离法进行分裂，得到单义域，并记录下各单义域的拟合结果，供全局考虑，识别直线和圆用。2．对选中的多义域运用最小二乘法进行圆的拟合；如果得到的平均径向弧的单义域；记录拟合的结果，作为总体识别的种子圆，转向5执行，3．对选中的多义域运用最小二乘法进行直线拟合；如果得到的平均距离段的单义域；记录拟合结果，作为总体识别的种子直线，转向5执行，4．该多义域为多个线段或圆弧的组合。将该多义域的头尾节点连接，计域进行分裂，得到两个新的多义域，取代原先的多义域；转向2执行。由此，所有的多义域都分裂为单义域，并对各单义域进行了拟合。2.4总体整合，识别直线和圆对2.3得到的单义域列表进行总体的整合，得到直线和圆。1．选取单义域列表中的第一个单义域，将其拟合的图形（直线或圆）作2．将列表中其他单义域的识别结果与种子图形进行比较，如果误差小于指定阈值，则属于同一直线或同一圆，将其与选定单一域进行合并，3.主要技术3.1BorlandC++Builder＋＋图形设备接口(GDI)，使得用户很方便地在应用程序添加图像或处理图像。第三章直线和圆的识别和编辑的实现第一节系统的层次结构的图示第二节系统数据结构及类的设计1.主要类的层次结构图形基类，提供所有图形的标准属性和方法。其他图形类（直线、圆）等都是该类的子类，继承其所有的public属性和方法，对其中的虚方法（virtual）该类为虚类，其成员函数主要为虚函数，为其所有子类提供统一的接口，但是没有实现。其他模块对图形进行操作时，除非生成新的实例（Instance现、扩充和维护提供很大方便。public:/*属性定义*///前景色（由于时间等的限制，本系统暂时只定义该图形的属性，其//他如：填充色，线条型，填充型等可扩充）/*编辑用属性*///编辑时标志该图形是否被选择//编辑操作所选中的点/*识别用属性*///识别的效果描述，值越小说明识别效果越好//最小二乘法的平均误差；//霍夫变换：1-参数空间中该图形的值/最大值//图形上点的数量/*成员函数定义*//*显示和描述用方法*///显示图形：在指定的位图上显示图形//描述图形：作为TtreeView的节点（主窗体使用）/*识别用*///直线上的两个线段；圆上面的两个圆弧//合并两个图形//经过判断为相同的图形进行合并，返回True；否则返回False。//判断图形存在的可能性（利用具体图形的几何规则）/*编辑用*///判断是否点击该图形，若选中则当前编辑的图形改为当前图形//取得鼠标形状：鼠标移动到选中图形的可操作点上时，显示为编辑形状//更新图形：将编辑点移动到(x,y)点。更新成功返回True，否则False。};3.图形类（CLine、CCircle）图形类是几何图形的具体实现，实现对应几何图形的描述和相关操作。图根据要求，本系统中实现了直线（CLine）和圆（CCircle）两个图形类。其他简单的几何图形如椭圆、矩形等也可以类似的方法实现，作为本系统的一斜式不能描述竖直直线，也避免极坐标方程转换的问题）。因为成比例的两组端点为轴进行旋转；2）线段的中点，选中中点并移动，是平移整个直线。publicpublic:/*初始化*//*直线的属性*///线段的两个端点/*对父类虚方法的实现*///在目标位图上画出直线（本系统中的实现为画线段）//在TTreeView中描述//返回描述用字符串//判断该直线是否与指定图形相同//将指定图形强制转化为CLine类型，比较其参数A,B,C，//若小于指定阈值，则返回Ture，否则返回False。//合并同一直线上的两个线段//若目标图形与该图形属同一直线，进行合并，返回True；//判断是否选择该直线进行编辑。//判断指定点(x,y)到该直线的距离，//如果小于指定阈值则返回True，否则False。//取得鼠标形状。//中点时返回垂直的四个方向箭头的形状表示移动//更新直线};public:/*初始化*/CCircle(intargX,intargY,intargR);/*圆的属性*///圆心//半径intR;/*对父类虚方法的实现*///在目标位图上画出圆//在TTreeView中描述//返回描述用字符串////判断该圆是否与指定图形相同//将指定图形强制转化为CCircle类型，比较其参数圆心坐标和半径，//若小于指定阈值，则返回Ture，否则返回False。//合并同一圆上的两个圆弧//若目标图形与该图形属同一圆，进行合并，返回True；//判断是否选择该圆进行编辑。//计算指定点(x,y)到圆心的距离，并与半径比较，//如果小于指定阈值则返回True，否则False。//取得鼠标形状。//圆上点时返回水平的双向箭头形状表示改变半径；//圆心时返回垂直的四个方向箭头的形状表示移动//更新圆};织对图像的识别结果、组织当前编辑工作的图形对象集。提供添加图形、删除public:/*初始化*///在目标位图上画出所有的图形//描述图形};5.点类（CPoint）点类对于与图像上的前景点。由于识别时需要判断是否为交点，在一般的public:/*初始化*//*属性：是否为交点*/};在“基于单义域的图形识别算法”中，单义域和多义域的唯一区别就是多义域不是单一的几何元素，其在存储结构上是一样的，在本系统中，都由删除点、判断该单义域是否有识别价值、识别该单义域等接口和方法。public:/*初始化*//*识别该单义域：实现算法中对单义域的识别部分*///如果识别成功（得到圆或线段）返回True，否则返回False/*尝试添加新的点到该单义域*///判断该点是否属于该单义域并确定是在头部还是在尾部，并将其插入到适当位置；如果该点为交点，则将相应的方向关闭增长；若加入成功返回True，/*/*判断该单义域是否有识别价值*///如果该单义域含有的点数太少，则没有价值返回False，否则返回True。/*属性：识别出的图形*/};基于单义域识别类是实现“基于单义域的直线和圆识别算法”的主要类。它实现了对目标图像的分割、对分割结果的显示、对识别得到的多义域进行分割、对单义域识别结果的总体考虑，最终得到识别结果集。得到。用来组织对图像的单义域分割后的结果。。public:/*构造和析构函数*//*扫描图像，得到多义域*///从上往下