voronoi图的算法编程实现
悬赏分：10 |解决时间：2010-4-9 10:19 |提问者：craftboy000
给个代码，谢谢！
最佳答案
输入：点集S = {p1, p2, …, pn}。
1. 任取pi, pj, pk三点连成三角形
2. 求出此三角形的外心v和半径d
3. 对图中点计算距离d(pr, v)，r=1…n并据此将各点排序，得到p1, p2, …, pn-3。l←1。
4. if d(pl, v)>d then goto 6
5. 改取pl, pi, pj组成三角形。若有多点满足d(pl, v) 6. 判定pl在已有哪条有向边或哪两条有向边右侧 7. 修改pl所在多边形的边界及顶点 8. l←l+1，goto 6 直到l>n-3 步骤1，2，4，5，7时间为常数；步骤3要求n-3次计算距离及nlogn次比较；步骤5到步骤2的循环为常数次，步骤6需要O(n)次计算，步骤8 循环n-3次，代价3+4+…+n-1 = O(n2)，总时间复杂性为O(n2)。 或者 1. 划分S为规模近似相等的子集S1, S2 2. 递归地构造Vor (S1)和Vor(S2) 3. 构造折线B分开S1, S2，使得对B上任一点v及S1中的点a和S2中的点b，有d(a, v)=d(b, v)。 4. 删去B左侧的Vor(S2)的所有边和位于B右侧的Vor (S1)的所有边，得到Vor(S) 3 回答时间：2010-3-31 21:44 |我来评论 向TA求助 回答者：zhangsolomon|二级采纳率：25% 擅长领域：软件操作系统/系统故障程序设计秦皇岛市物理学 参加的活动： 提问者对于答案的评价： 谢谢帮助哈 数据结构与算法 课程设计报告 课程设计题目：图的算法实现专业班级：信息与计算科学1001班姓名：学号： 设计室号：理学院机房 设计时间： 2011-12-26 批阅时间：指导教师：成绩： 图的算法实现 目录 一．设计内容 二．功能设计流程 三．详细设计 四．调试 五．总结 六．参考文献 七．附录源代码 一、设计内容： 1.实验内容 图的算法实现 （1）将图的信息建立文件； （2）从文件读入图的信息，建立邻接矩阵和邻接表； （3）实现Prim、Kruskal、Dijkstra序算法。 2.实现的任务：从文件中读入图的信息，建立图的邻接矩阵和邻接表，实现Prim、Kruskal、Dijkstra 3.本系统涉及的知识点 Prim、Kruskal、Dijkstra、邻接矩阵和邻接表存储。 4.功能要求 1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户接口要求使用方便、简洁明了、美观大方、格式统一。 4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5．所有程序需调试通过。 二、功能设计流程： 图的算法 实现 邻接矩阵邻接表 Prim算法Kruskal算法Dijkstra算法 开始 辅助数组初始 输出生成树的边并计算其权值 新顶点并入U 集后重新选择最小边：遍历点，若g.edges[k][j]!=0 && g.edges[k][j] 本文主要介绍基于Retinex理论的雾霭天气图像增强及其实现。并通过编写两个程序来实现图像的去雾功能。 1 Rentinex理论 Retinex（视网膜“Retina”和大脑皮层“Cortex”的缩写）理论是一种建立在科学实验和科学分析基础上的基于人类视觉系统（Human Visual System）的图像增强理论。该算法的基本原理模型最早是由Edwin Land（埃德温?兰德）于1971年提出的一种被称为的色彩的理论，并在颜色恒常性的基础上提出的一种图像增强方法。Retinex 理论的基本内容是物体的颜色是由物体对长波（红）、中波（绿）和短波（蓝）光线的反射能力决定的，而不是由反射光强度的绝对值决定的；物体的色彩不受光照非均性的影响，具有一致性，即Retinex理论是以色感一致性（颜色恒常性）为基础的。 根据Edwin Land提出的理论，一幅给定的图像S(x,y)分解成两幅不同的图像：反射物体图像R(x,y)和入射光图像L(x,y)，其原理示意图如图8.3-1所示。 图-1 Retinex理论示意图 对于观察图像S中的每个点(x,y)，用公式可以表示为： S(x,y)=R(x,y)×L(x,y) （1.3.1）实际上，Retinex理论就是通过图像S来得到物体的反射性质R，也就是去除了入射光L的性质从而得到物体原本该有的样子。 2 基于Retinex理论的图像增强的基本步骤 步骤一: 利用取对数的方法将照射光分量和反射光分量分离，即： S＇(x, y)=r(x, y)+l(x, y)=log(R(x, y))+log(L(x, y))； 步骤二：用高斯模板对原图像做卷积，即相当于对原图像做低通滤波，得到低通滤波后的图像D(x,y)，F（x, y）表示高斯滤波函数： D(x, y)=S(x, y) *F（x, y）； 步骤三：在对数域中，用原图像减去低通滤波后的图像，得到高频增强的图像G （x, y）： G(x,y)=S＇(x, y)-log(D(x, y)) ； 计算几何课程设计报告 基于Voronoi图的简单多边形骨架提取 引言 骨架（Skeleton）又称中轴（Medial Axis），通常使用烧草模型和最大球（圆）模型来描述。骨架有着与原物体相同的拓扑和形状信息，是一种性能优良的几何特征，能够有效的描述物体，因此，在物体识别、路径规划、医学工程等领域多有应用。在物体识别等应用领域里，骨架提取的输入可以看作是空间内的点构成的多边形，对于多边形的骨架提取也成为了这些应用的基本技术，具有重要的应用意义。在此次课程设计中，我们实现了基于Voronoi 图的任意多边形的骨架提取，并提供了多边形骨架提取的演示界面。 多边形骨架 一个多边形的骨架，如上图所示，可以看作是由无数点对之间的骨架点组成的。两点间的骨架（skeleton）（等同于对中轴(medial axis)的求取）是到两点距离相等的点的轨迹，它是两点连线的垂直平分线，每一点所邻接的半平面是到其距离最小的点集相应地可扩展为离散点集的中轴定义。它是下列性质点的轨迹：其上任一点到最近两离散点距离相等，相应地也产生各点到其距离最小的点集；两线间的中轴是到两线距离相等的点的轨迹，它在两线相交时为角平分线——两线平行时为到两线距离——的平行线，每一线所邻接并以中轴为界的区域是到其距离最小的点集。一线和一点间的中轴是到该点(线距离相等的点的轨迹,它是以该点为焦点、该线为准线的抛物线。该点或线所邻接并以中轴为界的区域是到其距离最小的点集。 多边形骨架的几何算法 多边形骨架（中轴）的几何算法，是由多边形的某一点开始，找出参与中轴线计算的相应的线段与线段、点与线段、点与点，实质都转化为求某个特定点（中轴转折点）的问题， 图像拼接算法及实现（一） 来源：中国论文下载中心 [ 09-06-03 16:36:00 ] 作者：陈挺编辑：studa090420 论文关键词：图像拼接图像配准图像融合全景图 论文摘要：图像拼接(image mosaic)技术是将一组相互间重叠部分的图像序列进行空间匹配对准,经重采样合成后形成一幅包含各图像序列信息的宽视角场景的、完整的、高清晰的新图像的技术。图像拼接在摄影测量学、计算机视觉、遥感图像处理、医学图像分析、计算机图形学等领域有着广泛的应用价值。一般来说,图像拼接的过程由图像获取,图像配准,图像合成三步骤组成,其中图像配准是整个图像拼接的基础。本文研究了两种图像配准算法:基于特征和基于变换域的图像配准算法。在基于特征的配准算法的基础上,提出一种稳健的基于特征点的配准算法。首先改进Harris角点检测算法,有效提高所提取特征点的速度和精度。然后利用相似测度NCC(normalized cross correlation——归一化互相关),通过用双向最大相关系数匹配的方法提取出初始特征点对,用随机采样法RANSAC(Random Sample Consensus)剔除伪特征点对,实现特征点对的精确匹配。最后用正确的特征点匹配对实现图像的配准。本文提出的算法适应性较强,在重复性纹理、旋转角度比较大等较难自动匹配场合下仍可以准确实现图像配准。 Abstract：Image mosaic is a technology that carries on the spatial matching to a series of image which are overlapped with each other, and finally builds a seamless and high quality image which has high resolution and big eyeshot. Image mosaic has widely applications in the fields of photogrammetry, computer vision, remote sensing image processing, medical image analysis, computer graphic and so on. 。In general, the process of image mosaic by the image acquisition, image registration, image synthesis of three steps, one of image registration are the basis of the entire image mosaic. In this paper, two image registration algorithm: Based on the characteristics and transform domain-based image registration algorithm. In feature-based registration algorithm based on a robust feature-based registration algorithm points. First of all, to improve the Harris corner detection algorithm, effectively improve the extraction of feature points of the speed and accuracy. And the use of a similar measure of NCC (normalized cross correlation - Normalized cross-correlation), through the largest correlation coefficient with two-way matching to extract the feature points out the initial right, using random sampling method RANSAC (Random Sample Consensus) excluding pseudo-feature points right, feature points on the implementation of the exact match. Finally with the correct feature point matching for image registration implementation. In this paper, the algorithm adapted, in the repetitive texture, such as relatively large rotation more difficult to automatically match occasions can still achieve an accurate image registration. Key words: image mosaic, image registration, image fusion, panorama 第一章绪论 形态学运算：基本思想是具用一定结构形状的结构元素去度量和提取图像中的对应形状以达到对图像分析和识别的目的。 腐蚀运算：将结构元素中心遍历整个图像，当图像完全包含结构元素时的中心点的轨迹即为腐蚀后的图像，图像变细。腐蚀运算可用于滤波，选择适当大小和形状的结构元素，可以滤除掉所有不能完全包含结构元素的噪声点。当然利用腐蚀滤除噪声有一个缺点，即在去除噪声的同时，对图像中前景物体形状也会有影响，但当我们只关心物体的位置或者个数时，则影响不大。 膨胀运算：将结构元素中心遍历整个图像边缘，中心点的轨迹即为腐蚀后的图像，图像整体变粗。通常用于将图像原本断裂开来的同一物体桥接起来，对图像进行二值化之后，很容易是一个连通的物体断裂为两个部分，而这会给后续的图像分析造成干扰,此时就可借助膨胀桥接断裂的缝隙。 开运算：先腐蚀后膨胀，可以使图像的轮廓变得光滑，还能使狭窄的连接断开和消除细毛刺；但与腐蚀运算不同的是，图像大的轮廓并没有发生整体的收缩，物体位置也没有发生任何变化。可以去除比结构元素更小的明亮细节，同时保持所有灰度级和较大亮区特性相对不变，可用于补偿不均匀的背景亮度。与腐蚀运算相比，开运算在过滤噪声的同时，并没有对物体的形状轮廓造成明显的影响，但是如果我们只关心物体的位置或者个数时，物体形状的改变不会给我们带来困扰，此时腐蚀滤波具有处理速度上的优势。 闭运算：先膨胀后腐蚀，可以去除比结构元素更小的暗色细节。开闭运算经常组合起来平滑图像并去除噪声。可使轮廓变的平滑，它通常能弥合狭窄的间断，填补小的孔洞。腐蚀运算刚好和开运算相反，膨胀运算刚好和闭运算相反，开闭运算也是对偶的，然而与腐蚀、膨胀不同的是，对于某图像多次应用开或闭运算的效果相同。 击中击不中运算：先由结构元素腐蚀原图像，再将结构元素取反去腐蚀原图像的取反图，最后将两幅处理后的图像取交。主要用于图像中某些特定形状的精确定位。 顶帽变换：原图像减去开运算以后的图像。当图像的背景颜色不均匀时，使用阈值二值化会造成目标轮廓的边缘缺失，此时可用开运算（结构元素小于目标轮廓）对整个图像背景进行合理估计，再用原图像减去开运算以后的图像就会是整个图像的灰度均匀，二值化后的图像不会有缺失。 Sobel算子： Prewitt算子： LOG算子： Canny算子：力图在抗噪声干扰和精确定位之间尊求折中方案，主要步骤如下所示： 1、用高斯滤波器平滑图像； 2、用一阶偏导的有限差分来计算梯度的幅值和方向； 3、对梯度幅值进行非极大值抑制； 4、用双阈值算法检测和连接边缘。 Hough变换： 边缘检测： 数据结构课程设计报告 设计题目：图的算法实现 班级： 学号： 姓名： 数据结构课程设计报告内容 一．课程设计题目 图的算法实现 【基本要求】 （1）建立一文件，将图的信息存在此文件中； （2）从此文件读入图的信息，建立邻接矩阵和邻接表； （3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。 二．算法设计思想 （1）图的存储结构： 邻接矩阵：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。 邻接表：对图中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域指示与顶点Vi邻接的点在图中的位置，链域指示下一条边或弧的结点；数据域存储和边或弧相关的信息。每个链表上附设一个表头结点。在表头结点中，除了设有链域指向链表中第一个结点之外，还设有存储顶点Vi的名或其他相关信息的数据域。 （2）prim算法 是一种求图的最小生成树的算法。 假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。此时，TE中必有n-1条边，T=(V，TE)为G 的最小生成树。Prim算法的核心:始终保持TE中的边集构成一棵生成树。 （3）Kruskal算法 Kruskal算法是另一种求最小生成树的算法 他的基本思想是以边为主导地位，始终选择当前可用（所选的边不 能构成回路）的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。 具体实现过程如下： <1> 设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。 <2> 在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。 <3> 如此重复下去，直到所有顶点在同一连通分量上为止。 (4)Dijkstar算法 Dijkstra算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s 开始计算)。 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。…重复该操作，直到遍历完所有顶点。 操作步骤 <1>初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长 3. 要求对于邻接矩阵和邻接链表给出从G 到T G 的算法，并计算其复杂度。 对于邻接矩阵问题十分简单，直接求矩阵的转置即可，意味着把行换成列，把列换成行，对每行操作为O(|V|)，需要对|V|行操作，时间复杂度为O （|V|^2）。 对于邻接链表，很明显要遍历链表的所有结点来看：如果对于u 结点其指向的结点中有v,则在新的链表中，创建一条从v 的链表指向u 的路径，因此需要遍历所有的链表元素，因此时间复杂度为O （|V|+|E|）。 3. 给出一个多图（多图为包含重复边和自循环边的图）去除冗余边的复杂度为O(V+E)的算法。 遍历邻接链表的所有结点，对于结点u ，如果其链表中还有u ，则去除所有的u ；如果还有重复的v ，则去除除了第一个v 以外的v 结点（这里的标记方法有很多种，可以用个数组）。这样的复杂度应该在O(V+E)。 4. 求解平方图的问题 算法如下：遍历G 的邻接矩阵，对于结点u ，如果存在u 到v 的路径，则在G^2的邻接矩阵u 中加入v,然后再遍历v 结点的链表，如果存在v 到w ，则将w 也加入到G^2的邻接矩阵u 中。 时间复杂度：这样，再遍历u 的时候，如果遍历到了u →v 这条边，那就在看v 的链表，而v 的链表里最多有|V|个结点，因此总的复杂度为O （|V|+|V|·|E|）。 6. 邻接矩阵求通用汇点（入度为|V|-1但是出度为0）的算法 算法如下：从（1，1）开始扫描邻接矩阵，如果（i,j ）是0，则下一个扫描（i,j+1）;如果（i ，j ）是1，则下一个扫描（i+1，j ）,当i 或者j 任一方到达|V|时停止。 这样，在最坏的情况下，扫描一行加一列或者一列加一行的结点，一共有2*|V|-1时间复杂度，因此为O(V)。 7. 关联矩阵，说明BB^T 每个元素是什么意思。 其中bij = -1 （如果边j 从结点i 发出） 1（如果边j 进入i 结点） 0（其他） 此处需要分类讨论：要明白B^T 中i 行相当于B 中第i 列。 ①BB^T 对角线上的元素，T B B （i ，i ） = ∑=| E |1 j 2 bij ，这样如果存在一条由i 发出或者进 入i 的边，都会在T B B （i ，i ）中加一（因为就算是-1平方之后也是1），因此T B B （i ，i ）就是代表由多少条边从i 发出或者进入。 ②BB^T 非对角线元素，T B B （i ，j ） = ∑=| |1 k E jk ik b b ,由公式或者读者自己画矩阵图可以 得出，如果k 边从i 发出从j 进入，或者反过来，bik*bjk 就等于-1，否则就为0。原因是i,j 我国基本比例尺地形图分幅与编号的计算方法 韩丽蓉 (青海大学水电系,青海西宁 810016) 摘要:通过实例探讨了我国基本比例尺地形图分幅与编号的计算方法,此方法可以帮助使用者快速地由某点的经纬度值计算出高斯投影带带号和某比例尺地形图的图幅编号,在测绘工作中具有一定的实用性。 关键词:分幅;编号;六度带;中央子午线经度 中图分类号:K 99 文献标识码:B 文章编号:1006-8996(2006)06-0079-04 1 高斯分带投影 1.1 基本概念 在地理坐标中,经度是以经过英国格林威治天文台的子午面作为起算点(零度),自西向东逆时针至180°为东经,自东向西顺时针从0°至180°为西经,东、西经180°经线是重合的。地图投影是把不可展的 地球椭球体面上的经纬网,按照一定的数学法则转绘到平面上[1,2]。我国的8种国家基本比例尺地形图 (1:1000000～1:5000)中,除了1:1000000万地形图采用国际通用的正轴等角割圆锥投影外,其余7种国家基本比例尺地形图统一采用高斯投影。 高斯投影中限制长度变形的最有效方法是按一定经差将地球椭球面划分成若干投影带,通常投影分为六度带和三度带。分带时既要控制长度变形使其不大于测图误差,又要使带数不致过多以减少换带计算工作。我国1:500000～1:25000的比例尺地形图多采用六度带高斯投影,1:10000～1:5000的地形图采用三度带高斯投影。我国基本比例尺地形图的分幅与编号需要用到某地所在的1:1000000 地形图(经差6° )的中央子午线经度,故需计算该六度带的带号及中央子午线经度。1.2 投影带带号和中央子午线经度的计算方法 1.2.1 六度带 从格林威治零度经线起,每隔经差6°分为一个投影带,自西向东逆时针分带,全球依次编号为1,2, 3,……60,每带中间的子午线称为中央子午线[1,2]。 东半球从经度0°逆时针回算到东、西经180°,投影带号为1～30。假如知道东半球某地区的平均大地经度L 东,则其投影带带号M 东和中央子午线经度L 6东的计算公式为: M 东=[L 东Π6](取整数商)+1(有余数时);L 6东=(6M 东-3)° (东经)西半球投影带从东、西经180°逆时针回算到0°,投影带号为31～60,假如知道西半球某地区的平均大地经度L 西,则其投影带带号M 西和中央子午线经度L 6西的计算公式为: M 西=[(360°-L 西)Π6](取整数商)+1(有余数时)=[(180°-L 西)Π6](取整数商)+1(有余数时)+30;L 6西={360°-(6M 西-3)°}(西经) 1.2.2 三度带 自东经115°子午线起,每隔经差3°自西向东分带,依次编号为1,2,3,……120[1,2] 。 东半球有60个投影带,编号为1～60,假如知道东半球某地区的平均大地经度L 东,其投影带带号N 东和中央子午线经度L 3东的计算公式为: 收稿日期:2006-07-10 作者简介:韩丽蓉(1967—),女,撒拉族,青海循化人,副教授,硕士。第24卷 第6期2006年12月 青海大学学报(自然科学版)Journal of Qinghai University (Nature Science ) Vol 124No 16Dec 12006 数据结构课程设计报告 图的最短路径算法的实现 班级：计算机112班 姓名：李志龙 指导教师：郑剑 成绩：_______________ 信息工程学院 2013 年1 月11 日 目录 一、题目描述 -------------------------------------------------------------------- 1 1.1题目内容-------------------------------------------------------------------- 1 2.2题目要求-------------------------------------------------------------------- 1 二、设计概要 -------------------------------------------------------------------- 2 2.1程序的主要功能----------------------------------------------------------- 2 2.2数据结构-------------------------------------------------------------------- 2 2.3算法分析-------------------------------------------------------------------- 2 三、设计图示 -------------------------------------------------------------------- 4 四、详细设计 -------------------------------------------------------------------- 5 五、调试分析 -------------------------------------------------------------------- 8 六、运行结果 -------------------------------------------------------------------- 9 七、心得体会 ------------------------------------------------------------------- 11参考资料 ------------------------------------------------------------------------ 12 一、图的邻接矩阵存储 1.存储表示 #define vexnum 10 typedef struct{ vextype vexs[vexnum]; int arcs[vexnum][vexnum]; }mgraph; 2.建立无向图的邻接矩阵算法 void creat(mgraph *g, int e){ for(i=0;i for(i=0;i 基本数字图像处理算法的matlab实现 1.数字图像处理的简单介绍 所谓数字图像就是把传统图像的画面分割成为像素的小的离散点，各像素的灰度值也是用离散值来表示的。 数字图像处理是通过计算机对图像进行去除噪声、增强、复原、分割、提取特征等处理的方法和技术。 2.图像的显示与运算 2.1图像的显示 Matlab显示语句 imshow（I,[lowhigh]）%图像正常显示 I为要显示的图像矩阵。,[lowhigh]为指定显示灰度图像的灰度范围。高于high的像素被显示成白色；低于low的像素被显示成黑色；介于high和low之间的像素被按比例拉伸后显示为各种等级的灰色。 subplot(m,n,p) 打开一个有m行n列图像位置的窗口，并将焦点位于第p个位置上。 2.2图像的运算 灰度化将彩色图像转化成为灰度图像的过程成为图像的灰度化处理。彩色图像中的每个像素的颜色有R、G、B三个分量决定，而每个分量有255中值可取，这样一个像素点可以有1600多万（255*255*255）的颜色的变化范围。而灰度图像是R、G、B三个分量相同的一种特殊的彩色图像，其一个像素点的变化范围为255种，所以在数字图像处理种一般先将各种格式的图像转变成灰度图像以使后续的图像的计算量变得少一些。灰度图像的描述与彩色图像一样仍然反映了整幅图像的整体和局部的色度和亮度等级的分布和特征。图像的灰度化处理可用两种方法来实现。 第一种方法使求出每个像素点的R、G、B三个分量的平均值，然后将这个平均值赋予给这个像素的三个分量。 第二种方法是根据YUV的颜色空间中，Y的分量的物理意义是点的亮度，由该值反映亮度等级，根据RGB和YUV颜色空间的变化关系可建立亮度Y与R、G、B三个颜色分量的对应：Y=0.3R+0.59G+0.11B，以这个亮度值表达图像的灰度值。 灰度是灰度级的函数，它表示图象中具有每种灰度级的象素的个数，反映图象中每种灰度出现的频率。 图像增强的目标是改进图片的质量，例如增加对比度，去掉模糊和噪声，修正几何畸变等；图像复原是在假定已知模糊或噪声的模型时，试图估计原图像的一种技术。 Matlab图像格式转换语句 rgb2gray(I) %从RGB图创建灰度图 imhist(I) %画灰度直方图 图像的线性变换 D B=f(D A)=f A*D A+f B Matlab源代码： I1=imread('F:\图片2.jpg'); subplot(2,2,1);imshow(I1);title('原图'); I2=rgb2gray(I1); %灰度化图像 subplot(2,2,2);imshow(I2);title('灰度化后图'); [M,N]=size(I2); subplot(2,2,3) [counts,x]=imhist(I2,60); %画灰度直方图 counts=counts/M/N; stem(x,counts);title('灰度直方图'); g=zeros(M,N);%图像增强 一般图形Voronoi图的离散生成 ————————————————————————————————作者：————————————————————————————————日期： 一般图形Voronoi图的离散生成-工程论文 一般图形Voronoi图的离散生成 刘欣LIU Xin （承德石油高等专科学校社科与数理部，承德067000）（Department of Social Science and Mathematics，Chengde Petroleum College，Chengde 067000，China） 摘要：由于一般图形形状和位置的任意性，一般图形Voronoi图往往比较复杂，难以将传统的构造法直接应用到一般图形Voronoi图的构造中。本文介绍了一般图形Voronoi图的离散构造法，并给出算法步骤及优势分析。Abstract：Because of the random graph shape and position，the general Voronoi graph is often more complex，it is difficult to construct the traditional method of direct application to the general structure of Voronoi graph. This paper introduces the construction method of general discrete Voronoi graph，and puts forword the algorithm steps and its advantages. 关键词：一般图形；Voronoi图；离散生成 Key words：general graphs；Voronoi diagram；discrete generation 中图分类号：TP391 文献标识码：A 文章编号：1006-4311（2015）19-0162-02 基金项目：河北省高等学校科学技术研究项，编号为QN20131159；承德市软科学研究计划项目（承德市公交线路的发展现状与优化分析）：201422123。作者简介：刘欣（1977－），女，河北承德人，承德石油高等专科学校社科数 泰森多边形(Voronoi图)生成算法 一、文档目的 本文描述了在geomodel模块中，生成泰森多边形所使用的算法。 二、概述 GIS和地理分析中经常采用泰森多边形进行快速插值，和分析地理实体的影响区域，是解决邻接度问题的又一常用工具。 荷兰气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。如图1，其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图，或dirichlet图。 图1 泰森多边形 泰森多边形的特性是： ●每个泰森多边形内仅含有一个离散点数据 ●泰森多边形内的点到相应离散点的距离最近 ●位于泰森多边形边上的点到其两边的离散点的距离相等 泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。 在泰森多边形的构建中，首先要将离散点构成三角网。这种三角网称为Delaunay三角网。 三、Delaulay三角形的构建 Delaunay三角网的构建也称为不规则三角网的构建，就是由离散数据点构建三角网，如图2，即确定哪三个数据点构成一个三角形，也称为自动联接三角网。即对于平面上n个离散点，其平面坐标为(x i，y i)，i＝1，2，…，n，将其中相近的三点构成最佳三角形，使每个离散点都成为三角形的顶点。 图2 Delaunay三角网 图像二值化算法研究与实现 摘要：图像二值化是图像预处理中的一项重要技术，在模式识别、光学字符识别、医学成像等方面都有重要应用。论文介绍了图像及数字图像处理技术的一些概念和相关知识；对VC++ 软件的发展和软件在图像处理中的应用做了简要介绍；还介绍了图像二值化算法以及利用VC++软件工具进行算法的实现。论文重点实现了图像分割技术中常用灰度图像二值化算法，如Otsu算法、Bernsen算法，并对这些算法运行的实验结果进行分析与比较。 关键词：图像处理；二值化；VC++； 1.引言 1.1 图像与数字图像 图像就是用各种观测系统观测客观世界获得的且可以直接或间接作用与人眼而产生视觉的实体。视觉是人类从大自然中获取信息的最主要的手段。拒统计，在人类获取的信息中，视觉信息约占60%，听觉信息约占20%，其他方式加起来才约占20%。由此可见，视觉信息对人类非常重要。同时，图像又是人类获取视觉信息的主要途径，是人类能体验的最重要、最丰富、信息量最大的信息源。通常，客观事物在空间上都是三维的(3D)的，但是从客观景物获得的图像却是属于二维(2D)平面的。 数字图像：数字图像是将连续的模拟图像经过离散化处理后得到的计算机能够辨识的点阵图像。在严格意义上讲，数字图像是经过等距离矩形网格采样，对幅度进行等间隔量化的二维函数。因此，数字图像实际上就是被量化的二维采样数组。 1.2 数字图像处理技术内容与发展现状 数字图像处理就是采用一定的算法对数字图像进行处理，以获得人眼视觉或者某种接受系统所需要的图像处理过程。图像处理的基础是数字，主要任务是进行各种算法设计和算法实现。 图像处理技术的发展大致经历了初创期、发展期、普及期和实用化期4个阶段。初创期开始与20世纪60年代，当时的图像采用像素型光栅进行少秒显示，大多采用中、大型机对其处理。在这一时期，由于图像存储成本高、处理设备昂贵，其应用面很窄。进入20世纪70年代的发展期，开始大量采用中、小型机进行处理，图像处理也逐渐改用光栅扫描方式，特别是CT和卫星遥感图像的出现，对图像处理技术的发展起到了很好的推动作用。到了20世纪80年代，图像处理技术进入普及期，此时的微机已经能够担当起图形图像处理的任务。超大规模集成电路（Very Large Scale Integration, VLSI）的出现更使处理速度大大提高，设备造价也进一步降低，极大地促进了图形图像系统的普及和应用。20世纪90年代是图像处理技术的实用化时期，图像处理的信息量巨大，对处理速度的要求极高。 1.3 图像二值化原理及意义 图像二值化是指用灰度变换来研究灰度图像的一种常用方法，即设定某一阈值将灰度 //多段图问题的动态规划算法设计与实现 #include"stdio.h" #include"conio.h" #include"stdlib.h" #define n 12 /*图的顶点数*/ #define k 5 /*图的段数*/ #define MAX 1000 typedef int NodeNumber; /*节点编号*/ typedef int CostType; /*成本值类型*/ CostType cost[n][n]; NodeNumber path[k]; /*存储最短路径的数组*/ NodeNumber cur= -1; void creatgraph(CostType cost[n][n]) /*创建图的成本矩阵*/ { int i,j; printf("请输入图的成本矩阵:\n"); for(i=0;i 多边形的Voronoi图及其研究应用 Voronoi图是计算几何的重要几何结构之一，也是计算几何的重要研究内容之一。它按照对象集合中元素的最近属性将空间划分成许多单元区域。由于Voronoi图具有最近性、邻接性等众多性质和较完善的理论体系，如今已经在图形学、机械工程、虚拟现实、地理信息系统、机器人、图像处理、CAD等领域得到广泛应用，也是解决距离计算、碰撞检测、路径规划、Delaunay三角化、骨架计算、凸包计算以及可见性计算等计算几何其它问题的有效工具，因而受到人们的广泛关注。 目前，对Voronoi图的研究工作，从所在空间上来说，更多的集中在2维上；从生成对象上来说，更多的集中在离散点集上；在研究内容上来说，主要集中在其构造算法和相关应用研究上。对于多边形的Voronoi 图来说，则主要集中在多边形的内部Voronoi图的构造和相关应用上。 本论文对多边形的内部和外部Voronoi图的相关性质进行了较为深入的研究，并以此为基础研究解决在图形图像、虚拟现实等方面的研究工作中遇到的可见性计算、距离计算以及骨架计算等问题。 本论文的贡献主要有： 1、分析了M.Held给出的关于多边形内部Voronoi图顶点和边数的上界所存在的局限性：只适用于单边界多边形，对多边界多边形则不适用；给出了新的可适用于单边界和多边界多边形的内部Voronoi图顶点和边数上界估计；同时给出了多边形的外部Voronoi图顶点和边数上界估计；并对多边形的内部和外部Voronoi图的每一个Voronoi区域所包含的顶点和边数的平均值进行了估计。 2、提出了一种基于Voronoi图的计算多边形可见性的算法。我们用多边形的Voronoi图建立多边形的骨架，利用Voronoi图的邻近属性和最近特性等性质，沿着骨架在局部范围内确定可能产生遮挡的对象，从而确定多边形内任意一点的可见边。在预先建立一个多边形的骨架后，可在时间内确定多边形内任一观察点的可见边，其中为搜索过程中涉及到的Voronoi图中的骨架元素的数目。大部分情况和可见边数接近。本算法时间复杂度低，适用于任意多边形，且易于理解和编程实现。 3、给出了基于Voronoi图快速计算两个分离凸多边形距离的算法。算法利用两个分离凸多边形P和Q的外部Voronoi图的性质及其相互间的位置关系，采用二分法逐渐缩小搜索范围来快速查找最短距离对象对。算法首先根据多边形外部Voronoi图的性质确定最短距离对象对所在的初始搜索范围P(和Q(；然后取P(和Q(的中间顶点对象pm1和qm2，它们分别将P(，Q(平分成和，和四个子搜索范围，并根据pm1和qm2及其所在Voronoi 区域的位置关系，确定可删除的一个或两个子搜索范围；然后在剩余的子搜索范围继续用二分法查找最短距离图的算法实现课程设计
基于matlab的图像去雾算法详细讲解与实现-附matlab实现源代码
基于 Voronoi 图的 简单多边形骨架提取
图像拼接算法及实现.doc
数字图像处理算法汇总
图的算法实现
基本的图算法
新旧图幅编号
图的最短路径算法的实现
图的两种存储结构及基本算法
基本数字(精选)图像处理算法的matlab实现
一般图形Voronoi图的离散生成
泰森多边形(Voronoi图)生成算法
图像二值化算法研究与实现
向前和向后处理多段图的算法设计和实现
多边形的Voronoi图及其研究应用
相关主题
文本预览