基于窗口与线段双重几何变换的线段裁剪新算法

鉴于裁剪算法中求交的时间复杂性和求交的技术必要性,如何尽快舍弃与窗口根本不相交的冗余线段成为提高裁剪效率的关键。鉴于传统编码技术取舍线段的高效性,引入一次编码技术;针对一次编码技术的局限性,文章首次提出窗口几何变换的概念,并引入二次编码技术,通过广义窗口高效舍弃冗余线段,尽量避免求交运算;后续流程引入线段几何变换技术实施裁剪,尽可能加快求交进程。窗口变换与线段变换集成的双重变换技术,将线段重新划分为六类,分别采取高效的处理策略,算法实现表明裁剪算法效率显著提高。该文算法具有一定的理论意义和普遍的应用意义。     

二维线段的矩形窗口逐边裁剪算法研究

本文详细介绍了一种二维线段的矩形窗口逐边裁剪算法。该算法充分利用了矩形窗口的凸性和窗口边界平行于坐标轴的特点，通过对二维线段与窗口边界的各种相对位置关系进行详细分类，以减少裁剪求交的次数，从而减少了算法的算术运算量，达到快速裁剪线段的目的。该算法原理简单，便于理解和实现，且运算速度较快。     

基于顶点编码的多边形窗口线裁剪高效算法

从多边形窗口线裁剪的本质特征出发，首次提出窗口顶点编码的新概念。以被裁剪直线为参照系，将多边形窗口划分为正区、负区和近零区三类区域，从而快速完成多边形窗口顶点编码。通过窗口顶点编码与传统的线段编码相结合，无须求交即可快速排除大部分窗外线段；进一步可以直接得到与直线相交的窗口边，加快了求交进程。更有意义的是，通过窗口顶点编码还可以准确判断并高效处理如下两类特殊相交情况：裁剪直线通过多边形的顶点、裁剪直线通过多边形的边。实验结果表明，新算法提高了裁剪效率并具有很好的稳定性。     

一种有效的圆形窗口线裁剪算法

根据线段两端点相对于圆形窗口的可能位置讨论裁剪结果。当两端点都在圆形窗口之外时,通过圆切线斜率与线段斜率的比较,及点区域判别来判断线段与窗口的相交情况。在确定线段与圆形窗口有交点的情况下,应用参数化形式求交运算,简化求交方程的构造。实验结果表明,新算法显著提高了裁剪效率。     

一种改进的Sutherland-Cohen裁剪算法

Cohen-Sutherland裁剪算法因直线与窗口边界求交点次数多而降低算法效率。提出了一种改进Sutherland-Cohen裁剪算法,将完全在窗口内和窗口外的直线判断出来,根据直线端点编码确定辅助线,利用平面上三点的关系判断直线与窗口的哪条边相交。改进的算法使得求交点次数降为最多两次,且避免计算斜率与距离,大大提高算法的效率。算法思想简单,操作方便,有利于硬件实现,对图形学的应用具有重要的实用价值。     

基于连续分区与串联编码的线段裁剪新算法

提出连续分区裁剪的新思想,按不同的方式多次将平面分成不同的区域,从而简单而快速地舍弃窗外线段,避免没有必要的求交运算。2次分区后提出串联编码技术,将2次编码技术中的两次编码串联起来,继承了第1次编码所做的工作,节省了很多时间;在此基础上,3次分区中提出点对称技术,并将其应用于多次分区,取得了较好的效果。点对称技术所划分平面区域边界的斜率为0°、±45°或无穷大,适合于程序的实现,且与2次编码技术相比,可以舍弃更多的窗外线段,避免更多的求交运算。算法实现清楚地表明该算法能明显提高线段裁剪效率。     

二维线段裁剪算法的分析与探索

线段裁剪是计算机图形学需要解决的基本问题之一。在对常见的线段裁剪算法分析的基础上,针对Cohen-Sotherland算法的改进进行了探索。利用合理构造分割窗口的辅助线,实现线段和窗口间位置关系的更精确判断,避免了无效交点的计算,提高了裁剪算法的整体效率。改进思路也同样适用于其他的裁剪算法。     

一种新的线段裁剪算法—四区域裁剪算法

本算法按裁剪窗口将整个图形区域划分为四个区 ,不仅提高了线段裁剪算法的效率 ,而且克服了一些算法要求裁剪窗口为矩形和对被裁剪线段端点进行编码的缺陷。     

-种新的线段裁剪算法-四区域裁剪算法

本算法按裁剪窗口将整个图形区域划分为四个区不仅提高了线段裁剪算法的效率,而且克服了一些算法要求裁剪窗口为矩形和对被裁剪线段端点进行编码的缺陷.     

基于裁剪窗口顶点和对角线的二维线段快速裁剪算法

根据二维线段与矩形窗口顶点和对角线的位置关系，介绍一种二维线段的矩形窗口裁剪算法，以减少裁剪求交的次数，从而减少算法的运算量，达到快速裁剪线段的目的。     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

3D Reconstruction from 2D Line Drawings only with Visible Vertices and Edges

The human vision system can reconstruct a 3D object easily from single 2D line drawings even if the hidden lines of the object are invisible. Now, there are many methods have emulated this ability, but when the hidden lines of the object are invisible, these methods cannot reconstruct a complete 3D object. Therefore, we put forward a new algorithm to settle this hard problem. Our approach consists of two steps： （1） infer the invisible vertices and edges to complete the line drawing, （2） propose a vertex-based optimization method to reconstruct a 3D object.     

一种基于梯度差的文档图像文本行检测算法

在分析文本行特点的基础上,提出了一种利用水平梯度差进行文档图像的文本行检测算法。该算法首先对输入的文档图像进行水平梯度差计算,然后在局部窗口中求解最大梯度差并进行文本行区域的合并,通过非文本区域过滤来消除字符阶跃的跳变,最后将文档图像以行块的形式进行显示。实验结果表明,与投影算法进行相比,该算法对于行间距较小的文档图像的检测效果较好,时间复杂度较低并且检测的正确率较高,具有一定的鲁棒性和较好的适应性。     

改进的自适应中值滤波算法

自适应中值滤波算法能有效地滤除图像的脉冲噪声,但是,随着噪声密度的增大,算法的滤波性能递减.当前对中值滤波算法进行改进的算法,也存在着相应的局限性.针对中值滤波算法的局限性,提出了改进的自适应中值滤波算法.算法根据滤波窗口的灰度极值进行噪声检测.对噪声点,用滤波窗口的灰度中值代替.如果中值为噪声点,则自适应地增大滤波窗口以取新的中值.如果窗口增大到允许的最大尺寸时,中值依然为噪声点,则取滤波窗口中除灰度极值外的其他像素的灰度均值.对标准图像和医学图像进行仿真实验,实验结果和数据证明,随着噪声密度的增大,标准的自适应中值滤波算法的滤波性能递减;改进的自适应中值滤波算法的滤波性能依然良好,在有效滤除噪声的同时,很好地保持图像的边缘和细节部分.     

基于适应性相关测试和点斜式查表求交的圆形窗口快速裁剪方法

在智能CAD、图形识别与理解等复杂图形应用系统中,由于图元数量多、 图元间关系复杂,且系统实时交互响应要求较高,现有圆形窗口裁剪算法较难满足要求。为 此提出圆形窗口对线段的一种新的快速裁剪算法。该算法由基于切线分隔的圆外线段快速适 应性测试方法、基于最小范围的圆内线段测试方法和基于点斜式查表的线段与窗口圆快速求 交方法三部分组成。通过按端点位置选择适应的测试方法、尽量避免不必要的操作、尽量以 简单操作代替复杂操作等措施,大大提高了圆形窗口对线段的裁剪速度。在图形识别及智能 CAD 等应用中的实验结果表明,采用文中算法可较大地提高效率。     

采用区域编码的椭圆对直线裁剪算法

裁剪算法的核心问题是速度问题,而求裁剪窗口和裁剪对象的交点是影响裁剪速度的主要因素。特别是椭圆对线段的裁剪,由于椭圆的方程是二次的,求椭圆与线段的交点 需要求解一元二次方程,涉及开方运算,非常浪费机器时间。为提高裁剪速度,设计出5位的区域编码,利用此技术能够迅速而准确地判断出椭圆和线段的位置关系。对于完全可见 或显然完全不可见的线段立即做出保留或弃掉的决定,避免求交运算;对于能够明确断定与椭圆相交的线段,采用中点分割算法求椭圆和线段的近似交点,避免求解一元二次方程 和开方运算;对于其他情形的线段通过求解一元二次方程来完成裁剪。基于前述思想设计出的椭圆对线段裁剪算法与现有的同类算法相比,算法实现简单,裁剪速度具有较大提高 。     

基于灰度最值和方向纹理的概率滤波算法

为了更高效地检测和滤除噪声,基于灰度最值和方向纹理的概率滤波算法根据灰度最值进行噪声检测,对检测出来的可疑噪声,根据四个方向纹理的平滑过渡性进行第二次噪声检测。运用滤波窗口中出现频次最高的信号像素取代噪声。如果窗口中不存在信号像素,增大滤波窗口,以使窗口包含信号像素。当滤波窗口增大到允许的最大尺寸时,窗口中依然没有信号像素,则用窗口中已处理的、出现频次最高的像素取代噪声。将算法与当前滤波性能最好的中值滤波算法用于图像滤波实验。从滤波结果的主观视觉效果和客观数据两方面进行的比较分析证明,相对于当前的中值滤波算法,基于灰度最值和方向纹理的概率滤波算法具有更加良好的滤波性能,在滤除噪声的同时,很好地保持图像的边缘和细节。     

分治法在中值滤波快速算法中的应用研究

设计并实现了一种基于分治法的中值滤波快速算法。本算法对邻域内所有像素值以行为单位进行分块,每块排序后求出其中值,然后再对得到的所有块的中值进行排序,再一次求中值,而不是把邻域内所有像素值作为整体进行排序。大量实验结果表明,与经典中值滤波算法相比,现在提出的算法大大减少了数据扫描与比较的次数,尤其在大窗口情况下非常有效,在保证整体数据质量的前提下大幅度提高了计算速度。