STL模型特征面片自适应分层算法*

为获得聚苯乙烯泡沫塑料(EPS)异步快速成形机所需的加工路径,提出了一种基于特征面片的Stereolithography(STL)模型自适应分层算法。算法根据模型在分层方向上的特征面片和最小加工厚度来确定分层位置和切割平面,无需坐标变换,可沿任意方向直接获取切片两端截面轮廓信息。该算法采用了一种新方法快速分割边界面片,通过轮廓信息整理可得到点轮廓、非闭合环轮廓、闭合环轮廓。闭合环轮廓经三角化后,可封闭切片端面。本文算法均采用Visual C++ 6.0实现,经实验证明运行稳定有效。     

组合曲面的粗加工刀轨算法

利用Zmap模型在切削层上构造物体区域的行程编码，根据行程编码的连通关系链接节点形成边界，通过确定边界之间的包容关系构造边界描述树，从而得到切削区域的拓扑结构．该算法简单、效率高，能自动识别轮廓和岛屿，并已在实际中得到很好的应用．     

快速成型切片数据的优化算法研究

为了能够顺利地进行 STL模型切片轮廓数据的进一步处理 ,提出了对切片数据进行优化处理的算法 .对由于STL模型的缺陷造成切片之后的轮廓信息数据有大量的冗余数据 ,提出了一种冗余数据的滤除算法 ;针对切片轮廓的不封闭 ,给出了有效的修正算法 ;同时给出了对切片轮廓的内外边界进行自动识别的算法 .该算法高效简单 ,提高了后续的数据处理的效率和成型件的加工质量 ,改善了零件成型的加工性能     

基于三维表面模型的任意切割算法*

通过对三维表面模型进行切割,人们可以方便地观察物体的内部结构。针对三维表面模型,提出了一种任意切割算法。任意切割过程首先是交互生成切割曲线,生成切割面;然后通过切割面对表面模型进行切割,在切割面上生成交线序列;再由交线序列与切割面边界生成封闭的边界轮廓,确定各边界轮廓间的包含关系;最后对边界轮廓包围的截面区域进行Delaunay三角剖分并着色,得到完整的剖面。实验结果证明了该算法的有效性和可行性。     

基于工程图的连通域划分及邻接关系确定

在基于工艺信息与工艺过程驱动的三维工序模型重建研究中,连通域的划分和邻接关系的确定是二维工序图特征识别的核心.首先采用极右路径法和极左路径法分别获得视图的最外轮廓环及各个子环;然后,通过扫描线算法确定子环之间的邻接关系;最后,根据子环及其之间的邻接关系进行连通域的划分,并进一步确定连通域之间的邻接关系.以某一零件视图为例,对该方法的有效性进行了验证.     

基于节点区域分离的工程图纸整体识别方法

在工程图纸矢量化处理中着眼于图形的宏观特征,提出了一种整体识别方法,该方法中,引入节点区域的概念,通过节点区域与图段的连接关系确定图形的拓扑结构,并由节点区域分离分割图段,图段的跟踪识别以图段轮廓的方向码序列为引导实现。整体识别算法矢量化速度快,有较强的抗噪声能力。     

3维碎片拼合的算法研究

为实现艺术珍品保护或古器物修复中3维碎片的比对和拼接,提出了一种空间任意形状的3维碎片拼合算法。该算法首先对由实物测量数据建立的三角网格模型进行预处理,即去除模型中所存在的一些缺陷,以提取模型边界轮廓曲线;然后对碎片的边界轮廓离散点进行五次B样条插值,同时计算轮廓曲线上各个点的曲率、挠率和法矢,并据此分析3维碎片轮廓曲线的几何特性;接着根据轮廓曲线上各个点的总曲率来检测轮廓的特征点,并对轮廓进行分段;最后根据曲率、挠率的变化对不同轮廓上的特征段进行相似性度量,并运用法矢对相似性程度较高的轮廓段进行可匹配性验证,同时计算出可匹配轮廓段的坐标转换关系,以实现碎片的拼合。实例表明,该算法是高效、稳定的。     

磨牙修复体面区域提取方法研究

为精确加工出磨牙面的几何形状,以保证磨牙修复体的咬合功能,需将磨牙的面划分为一系列区内曲率相近的沟、窝、嵴等特征区域分别进行加工。介绍了在磨牙STL模型中,人机交互式确定特征区域边界的方法。提出了一种对边界线环进行偏置的算法,解决了偏置过程中的"点连通"、"尖角"以及"自相交"问题,实现了特征区域的STL数据的提取。最后给出了该方法在磨牙STL模型中的验证实例。     

分形模型的3D打印路径规划

为了在保证边缘细节的精度条件下最大限度地提高打印效率,提出了分形模型的3D打印路径规划算法.将分形模型分为3个打印区域:轮廓层,过渡层及内层.针对3个不同的区域采取不同的填充措施.文中算法主要分为以下4个步骤:(1)为了保证边缘细节的精度,利用轮廓平行算法的高保真性填充分形模型的轮廓层.将不同等距线进行特征点检测并设置相应的阈值来优化轮廓层层厚;(2)以过渡层的面积与过渡层内外边界是否相交为条件约束建立优化问题确定过渡层的最优层厚,并确定一条光顺的三次B样条曲线作为过渡层内边界(即内层边界);(3)针对过渡层和内层进行全局连续Fermat螺线填充,并提出Fermat螺线局部优化的算法;(4)将3个区域内部的填充曲线连接进行全局路径优化.实验结果表明,相比于传统的路径规划算法与连续Fermat螺线算法,文中算法具有更高的效率及更好的打印效果,并且适用于具有复杂边界及多连通区域的几何模型.     

基于向量角分线的离散刀轨环子域分割算法

为提高环切加工刀轨质量及生成效率,提出一种基于向量角分线的二维截面轮廓子区域的分割算法.结合Voronoi图的全局分解思想,通过改进中轴线中对多边形凹顶点的不均等处理的拓扑结构,提出有效向量角分线的概念;通过判断向量角分线交点的属性来合并角分线,同时生成子域结点关系树,最终把离散刀轨环分割成隶属于每个边界元素的子区域,并在子区域基础上生成无自交的等距线.实验结果表明,该算法运行高效,可提高刀位轨迹生成的效率和质量,并改善产品的加工性能.     

边界跟踪自动机与围线树结构的生成算法

定义八近邻图像的边界跟踪自动机,利用自动机跟踪图像所有区域边界,自动机的输出为边界的顶点链码,在自动机跟踪所有边界的同时生成围线的树结构.跟踪算法复杂度是线性的,能跟踪任意复杂图像区域.     

A new run-based algorithm for Euler number computing

The Euler number of a binary image is an important topological feature for many image processing, image analysis, pattern recognition, and computer vision applications. This paper proposes a new run-based Euler number computation algorithm. The conventional run-based algorithm processes rows of the given image one-by-one from top to bottom in a single phase. For each row, it finds the runs in the row and records the start and end locations of each run to compute neighbor runs. In contrast, our algorithm calculates the Euler number of an image in two phases. In the first phase, we process odd rows alternately to find runs and only record its end location. In the second phase, we process each of the remaining even rows to find runs and calculate neighboring runs between the current row and the rows immediately above and below using the recorded run data. Using this method, the number of accesses required to compute the Euler number decreases in almost all cases. Analysis of the time complexity and experimental results demonstrate that our algorithm outperforms conventional Euler number computation algorithms.     

Smart search space reduction for approximate computing: A low energy HEVC encoder case study

The approximate computing paradigm provides methods to optimize algorithms while considering both application quality of service and computational complexity. Approximate computing can be applied at different levels of abstraction, from algorithm level to application level. Approximate computing at algorithm level reduces the computational complexity by approximating or skipping computational blocks. A number of applications in the signal and image processing domain integrate algorithms based on discrete optimization techniques. These techniques minimize a cost function by exploring an application parameter search space. In this paper, a new methodology is proposed that exploits the computation-skipping approximate computing concept. The methodology, named Smart Search Space Reduction(Sssr), explores at design time the Pareto relationship between computational complexity and application quality. At run time, an approximation manager can then early select a good candidate configuration. Sssr reduces the run time search space and, in turn, reduces computational complexity. An efficient Sssr technique adjusts at design time the configuration selectivity while selecting at run time the most suitable functions to skip. The real time High Efficiency Video CodingHevc encoder in All Intra(AI) profile is used as a case study to illustrate the benefits of Sssr. In this application, two discrete optimizations are performed. They explore different coding parameters and select the values leading to the minimal cost in terms of a tradeoff between bitrate, quality and computational energy by acting on both the Hevc coding-tree partitioning and the intra-modes. Combining two Sssrs iterations on this use case, the energy consumption is reduced by up to 77%. Moreover, the combination of the two Sssrs iterations in comparison to using only one reduces the BD-BR bitrate/quality metric by 4% for the same energy consumption.     

一种二值图象边界提取算法

文中提出了一种新的二值图象边界提取算法。通过分析边界象素的特征,归纳出一个边界象素提取算子,该算子最多只需要计算象素的4邻域象素,运算量小,速度快,运用他能直接提取出二值图象的边界象素,得到单象素宽的边界。实验结果表明,该算法要优于传统的二值图象边界提取算法,实用性强。     

构造给定k错线性复杂度谱的2~n周期序列

k错线性复杂度是度量序列密码安全性的重要指标之一。基于方体理论和Games-Chan算法的逆向推导提出构造方法,构造了具有给定k错线性复杂度谱的2n周期序列。首先使用标准方体分解算法对k错线性复杂度具有第一下降点k=2、第二下降点k′=6、第三下降点k″=10的2n周期序列进行分类,再讨论每一类序列下降点线性复杂度参数之间的关系,最后给出每种参数关系下序列的计数公式以及构造过程。事实上,所使用的方法可以用于构造具有更多下降点的2n周期序列。     

Computing perimeters of regions in images represented by quadtrees

An algorithm is presented for computing the total perimeter of a region in a binary image represented by a quadtree. The algorithm explores each segment of the boundary of the region once and only once. Analysis of the algorithm shows that its average execution time is proportional to the number of leaf nodes in the quadtree.     

结合分水岭的Mean-Shift图像分割新算法

针对Mean-Shift图像分割算法需要对图像中每个像素点进行迭代计算、耗时多的问题,提出一种改进的图像分割算法.研究发现,分水岭算法可以将一幅图像划分为若干一致性较好的区域,这一优势恰好有利于Mean-Shift算法的处理.本文利用分水岭算法对图像进行初始分割,将以点阵形式表示的图像转化为块状表示,再运用改进的Mean-Shift算法对每个块进行迭代计算.实验结果和时间复杂性分析表明,新算法在很好地保持了原算法分割效果的前提下,时间效率有了很大程度的提高.     

摄像机位姿的高精度快速求解

目的 针对对应点个数大于等于6的摄像机位姿估计问题,提出一种既适用于已标定也适用于未标定摄像机的时间复杂度为 的高精度快速算法。 方法 首先选取四个非共面虚拟控制点,并根据空间点和虚拟控制点的空间关系以及空间点的图像建立线性方程组,以此求解虚拟控制点的图像坐标及摄像机内参,再由POSIT算法根据虚拟控制点及其图像坐标求解旋转矩阵和平移向量。 结果 模拟数据实验和真实图像实验表明该算法时间复杂度和计算精度均优于现有的已标定摄像机位姿的高精度快速求解算法EPnP。 结论 该算法能够同时估计摄像机内外参数,而且比现有算法具有更好的速度和精度。     

基于围线分层扫描的完全欧氏距离变换算法

围线扫描欧氏距离变换算法是一种快速的完全欧氏距离变换算法,其时间复杂度达到最优,但需在围线区域进行全局搜索,计算时间并未优化。针对此问题,提出了一种基 于围线分层扫描的完全欧氏距离算法。该算法首先根据中心像素的围线性质对二值图像像素点进行重新分类,然后按照围线区域像素与中心像素的空间关系,对中心像素的围线区 域进行分层搜索,并给出了搜索的终止条件。该算法保持了最优的时间复杂度,可通过定量分析单个像素的计算时间来证明其计算时间已得到优化。实验结果表明,该算法能够得到 准确的欧氏距离图像,且运行速度快。     

数据流中结构二叉树挖掘算法研究

针对传统数据流挖掘算法不能挖掘出频繁项之间的关系而且挖掘时间和空间复杂度高、准确度不高的问题,本文提出了一种数据流中结构二叉树挖掘算法（AMST）。该算法利用了二叉树结构的优势,将所处理事务数据库中的数据流转化成结构化二叉树,然后利用数据流矩阵对结构二叉树进行挖掘。整个过程只对事务数据库进行了一次扫描,大大提高了挖掘的效率。此外,算法还找出了具有层次关系的频繁子树。实验结果表明,AMST算法性能稳定,在时间复杂度和空间复杂度方面有很大的优越性,能够快速准确地对数据流进行挖掘。