任意拓扑三角形网格的全局参数化

提出了一种零亏格的任意拓扑流形三角形网格自动全局参数化方法 .算法首先采用顶点对合并的网格简化方法构造一个网格的累进表示 ,在进行网格简化的同时 ,对被删除的顶点相对于顶点合并操作所得到的新顶点的邻域进行局部参数化 ,由此得到一个带局部参数化信息的累进网格 ;然后将网格简化所得到的基网格进行中心投影到一个单位球面上 ,并采用累进恢复的方法将删除的顶点按与删除时相反的顺序逐次添加回网格上来 ,所添加顶点的坐标不再是其删除前的坐标值 ,而是由局部参数化信息计算得到 ,并且保证是位于单位球面上的 .由此得到原始网格的单位球面参数化网格     

基于特定边界的组合保角球面参数化

针对亏格为零的流形三角网格模型,提出一种基于特定边界的组合保角球面参数化方法。该方法采用平均值坐标计算出原始三角网格模型各顶点间相关的权数,然后用这个权数去修正球面域上的顶点坐标得到新的具有保角性质的顶点坐标,再利用Möbius变换把新生成的球面域质心转化为球心,使其面积的变形程度降低,最后得到一个精度更高的初始球面域。实验结果表明该方法是有效的,且具有变形小、效率高的特点。     

新颖的网格模型压缩算法——网格切片

针对三维(3D)网格模型的存储与网络传输问题,提出一种新颖的三维模型压缩算法。该算法基于对网格模型的切片处理,主要由以下三个步骤组成:切片顶点的计算、切片边界的均匀采样以及对切片所得图像的编码。对于一个给定的三维模型,首先,计算模型的包围盒;然后,沿包围盒长度最长的方向进行切片;同时计算切片与网格模型表面每条边的交点,构成一个多边形,这个多边形即为切片的边界;其次,对切片边界进行均匀的重采样,使每层切片具有相同的顶点数;最后,把每层的顶点坐标转化为极坐标形式,这样,所有层顶点的ρ-坐标以及θ-坐标能分别构成一张图像,原始的三维模型即能由这两张图像表示。这种表示方法具有以下两个明显的优势:第一,降低了数据的维度,有效减少了数据量;第二,具有极大的数据相关性,进一步减少了数据的熵。基于这两个优势,该算法对图像数据进行差值编码以及算术编码,最后得到压缩后的文件。与增量参数细化(IPR)方法相比,在解码模型同等质量的前提下,所提算法的编码效率提高了23%。实验结果表明,所提算法在模型存储和传输应用中能取得很好的压缩效率,有效减少了数据量。     

对称零空间准则下的LDA特征抽取方法

网格分割在网格参数化、纹理atlas图等几何处理问题中有着重要的应用.提出一种基于顶点或面凸凹信号的简单高效的网格分割算法.基于均匀支撑半径的顶点凸凹信号分析将顶点分为平坦点、凸点、凹点和特征点,先从平坦点进行平坦区域扩展,再从剩下的凸凹点出发进行凸凹区域扩展,最后根据顶点和边界边的光滑度进行区域竞争扩展;对于未能完全分割的简化程度高的模型,基于面的凸凹信号采用类似的过程进一步完成最后的分割.该算法可以快速地进行网格分割并能较好地保持网格特征,特别适用于CAD模型的分割.     

基于Surfel点云数据的压缩算法*

针对点云数据局部集中的特点,使用差值预测对点云数据进行预测处理;在预测的同时,根据IEEE754浮点数标准,简化浮点数的尾数,使用3.5 Byte来表示一个浮点数,以提高压缩效果;然后对预测数据中连续重复的字节使用该字节加该字节重复的次数的方式存储;最后对经过以上处理的数据使用一阶自适应算术编码进行压缩。最终得到的程序在压缩比和内存占用两个方面远优于WinRAR、WinZip压缩软件。     

基于STL文件的Laplacian网格优化算法

针对直接重构得到且以STL文件格式存储的网格模型质量不高的问题, 提出了一种基于Laplacian坐标的网格模型全局优化算法。该算法在提高三角面片质量的同时可以很好地保持原网格模型的局部几何特征, 其核心思想是通过在最小二乘意义下求解由权重控制的包含顶点位置和拉普拉斯坐标双重约束的线性系统来对网格顶点进行重新定位。从实验结果可以看出, 该算法较以往的Lapacian优化算法在对网格细节特征的保持上有一定优势。     

网格模型的三角形折叠化简方法研究

针对三维扫描仪所获取的模型数据量庞大,无法直接使用扫描仪的问题,为压缩模型数据量,提出了一种基于三角形折叠网格模型化简方法。通过对三角形曲面进行球面拟合来获取折叠后新顶点位置,以新顶点与关联三角形的距离平方之和作为折叠依据,能够有效保持原始网格模型的几何特征和拓扑结构,并进行仿真。通过系统仿真证明了方法的有效性,而且算法运算速度快,可以满足模型实时显示的要求。     

基于凸凹信号的网格分割

网格分割在网格参数化、纹理atlas图等几何处理问题中有着重要的应用,提出一种基于顶点或面凸凹信号的简单高效的网格分割算法,基于均匀支撑半径的顶点凸凹信号分析将顶点分为平坦点、凸点、凹点和特征点,先从平坦点进行平坦区域扩展,再从剩下的凸凹点出发进行凸凹区域扩展,最后根据顶点和边界边的光滑度进行区域竞争扩展;对于未能完全分割的简化程度高的模型,基于面的凸凹信号采用类似的过程进一步完成最后的分割,该算法可以快速地进行网格分割并能较好地保持网格特征,特别适用于CAD模型的分割。     

三角网格的自适应细分研究

提出面向三角网格全局细分和局部自适应的细分算法。在原三角网格模型上计算每个面片的中心坐标,据此生成的中心坐标点作为新的顶点坐标进行重新绘制得到三角基网格,然后进行多次迭代,达到基本的全局细分目标。在最后生成的基网格上,可以通过调节最大网格面积和平均网格面积之间的比例系数等,来得到更加均匀的三角网格。实验表明该方法能到得到质量较高的细分结果。     

基于内容认证的三维网格模型半脆弱水印算法

提出一种新的基于内容认证的半脆弱水印算法。在对三维网格模型进行主元分析校准处理后,以模型顶点几何数据构造生成球面坐标映射方阵实现二维参数化。嵌入的半脆弱水印为一幅二值图像,将其嵌入到方阵的系数得到三维网格模型的修改系数方阵,可通过检测可疑模型提取出的半脆弱水印的完整性来判断其是否经历过非法篡改。实验结果表明,算法嵌入的半脆弱水印可容忍多种类型的网格正常数据处理,例如网格平移、旋转、各向一致缩放处理,以及低强度的顶点坐标量化处理和顶点随机噪声等,对于恶意攻击(例如较高强度的顶点随机噪声)则表现敏感。     

On Computing the Exact Euclidean Distance Transform on Rectangular and Hexagonal Grids

In this paper we prove an equivalence relation between the distance transform of a binary image, where the underlying distance is based on a positive definite quadratic form, and the erosion of its characteristic function by an elliptic poweroid structuring element. The algorithms devised by Shih and Mitchell [18] and Huang and Mitchell [7], for calculating the exact Euclidean distance transform (EDT) of a binary digital image manifested on a square grid, are particular cases of this result. The former algorithm uses erosion by a circular cone to calculate the EDT whilst the latter uses erosion by an elliptic paraboloid (which allows for pixel aspect ratio correction) to calculate the square of the EDT. Huang and Mitchell's algorithm [7] is arguably the better of the two because: (i) the structuring element can be decomposed into a sequence of dilations by 3 × 3 structuring elements (a similar decomposition is not possible for the circular cone) thus reducing the complexity of the erosion, and (ii) the algorithm only requires integer arithmetic (it produces squared distance). The algorithm is amenable to both hardware implementation using a pipeline architecture and efficient implementation on serial machines. Unfortunately the algorithm does not directly transpose to, nor has a corresponding analogue on, the hexagonal grid (the same is also true for Shih and Mitchell's algorithm [7]). In this paper, however, we show that if the hexagonal grid image is embedded in a rectangular grid then Huang and Mitchell's algorithm [7] can be applied, with aspect ratio correction, to obtain the exact EDT on the hexagonal grid.     

改进的运动目标检测算法及其实现

在智能视频运动目标检测中,带掩膜的背景差方法存在会出现鬼影目标和计算复杂度大等不足。为此,提出一种改进算法,利用相关矩阵判别法去除鬼影目标,同时增加对光照变化的处理,使算法快速适应光照变化。将耗时的浮点运算转化为整型运算。变换后的算法可同时适应浮点和定点处理器,更具有通用性。在DM642嵌入式系统上进行实现,结果表明,该算法速度快、检测准确率高,满足实时性要求。     

基于整型DCT变换的图象编码研究

为了既能保证图象无失真压缩，又能提高编码效率，给出了一种新的基于整型可逆DCT变换的嵌入式编码方法，并实现了基于DCT的无失真编码和有失真编码方案的完美结合，该算法是首先通过计算DCT浮点变换的整数可逆矩阵分解，从而得到可以整数实现的可逆矩阵变换，然后再利用得到的分解矩阵依次对图象样本进行变换；最后将变换得到的系数用多种高效编码方法进行编码，实验结果表明，该新方法用于无损压缩编码时，整型DCT明显好于浮点DCT，而且没有残差的编码问题；用于有损压缩编码时，两者的编码效果相近。     

基于整数小波变换和子带比特平面编码的图象压缩算法

在分析图象整数小波变换的基础上 ,提出了基于子带比特平面编码的压缩算法 .该算法将整数小波系数按子带分为若干比特平面 ,称之为子带比特平面 ,并采用简单高效的率失真优化算法确定子带比特平面的编码顺序 ,且这一顺序与图象无关 .按此顺序对子带比特平面进行自适应 MQ算术编码 ,便得到嵌入式压缩码流 .该算法可以从无损到有损 ,以任意倍率或质量进行图象压缩 ,压缩效率达到了浮点 EZW算法和 JPEG2 0 0 0整数小波编码方案的水平 ,而速度远快于这两者的速度 .该算法还具有复杂度低 ,占用内存少的优点 .     

复杂背景下快速车牌定位算法

提出了一种复杂背景下的快速实时车牌定位算法。车牌定位的实时性和精确性是车牌识别系统高效运行的保障。提出了一种整型特殊核并利用差分运算来实现车牌定位。在分析了混合高斯函数卷积的车牌定位方法上的基础上,针对二维高斯核计算复杂度较高的问题提出了改进,直接在获取的垂直边缘图上进行混合高斯卷积,重新提出了一种整型的特征核,并用差分的方法代替了卷积,即用少量的加法操作代替了卷积大量的浮点乘法操作。对比分析了两种不同方法的定位效果和时间复杂度。实验结果表明在保持定位精度不变的情况下运行效率有较大提高,达到了实时性的要求。     

等球Packing问题的序列对称换位算法

为处理等球Packing问题,在基本拟物算法的基础上设计了序列对称换位策略,形成了一个启发式的序列对称换位算法。在球形容器内装填1～50个等球时,此算法改进了其中45项当前记录。特别地,此算法成功将68个半径为1的等球装进半径小于5的球形容器。此结果证否了一个猜想,该猜想认为半径为5的球形容器至多只能装下67个半径为1的等球。其结果的质量说明了序列对称换位算法的有效性。     

An efficient three-point arc algorithm

For many applications a 2-D circular arc can be conveniently specified by three points that lie on the arc. Since the radius of curvature grows without bound as the three points become collinear, any practical algorithm must avoid calculating the arc's radius or functions of the radius. An algorithm that achieves this objective is presented. It is very efficient because it uses exclusively integer arithmetic and requires only addition, subtraction, comparison, and branch operation in the inner loop     

一种适于串行机实现的图像并行细化算法

为解决现有的图像并行细化算法在串行机上的高效实现问题 ,首先提出了一种 4× 4邻域二值图像的双字节图像编码方案 ,由于在该方案中将每个 4× 4邻域的像素用一个双字节的整数来表示 ,从而将基于整个邻域 16个像素的细化处理转化为一个双字节整数的读、写和比较运算的问题 ;然后在此基础上提出了一种可在串行机上实现的并行细化算法。实验证明 ,该算法适用于当前通用的各种基于模板匹配的并行细化算法 ,其不仅可以取得完全相同的细化结果 ,而且可以大幅度提高图像细化过程在串行机上的执行速度 ;最后简要讨论了该算法利用 PC机中的 MMX技术来进一步提高并行粒度和运算效率方面所具有的潜力     

一种自适应k-最近邻算法的研究*

针对传统k-最近邻算法(k-Nearest Neighbor, kNN)存在搜索慢的缺陷,提出了一种改进型的自适应k-最近邻算法。该方法在以测试样本点为中心的超球内进行搜索,对超球半径的生长进行采样,建立半径生长的BP神经网络模型,逼近半径变化函数,并用该函数指导超球体的生长。该方法有效地缩小了搜索范围,减少了超球体半径生长的试探次数,对处理稀疏数据集有明显的优越性。     

A General Multi-step Algorithm for Voxel Traversing Along a Line

Traversing voxels along a three dimensional (3D) line is one of the most fundamental algorithms for voxel‐based applications. This paper presents a new 6‐connectivity integer algorithm for this task. The proposed algorithm accepts voxels having different sizes in x, y and z directions. To explain the idea of the proposed approach, a 2D algorithm is firstly considered and then extended in 3D. This algorithm is a multi‐step as up to three voxels may be added in one iteration. It accepts both integer and floating‐point input. The new algorithm was compared to other popular voxel traversing algorithms. Counting the number of arithmetic operations showed that the proposed algorithm requires the least amount of operations per traversed voxel. A comparison of spent CPU time using either integer or floating‐point arithmetic confirms that the proposed algorithm is the most efficient. This algorithm is simple, and in compact form which also makes it attractive for hardware implementation.