精确排序的四面体体数据快速可视化

采用投影四面体法进行可视化时需要对所有四面体进行排序,而四面体的不规则性和较强的依赖性导致并行排序的难度很大,为此提出一种精确排序的并行化算法.该算法在排序阶段逐层并行提取互不遮挡的四面体,并在绘制阶段采用区域求和表、提前终止等技术直接减少处理的四面体个数,再将四面体数据集进行有序投影得到最终的绘制结果.实验结果表明,采用文中算法的GPU实现比基于CPU的精确排序快91％;对于大尺度数据集(大于百万个四面体),提前终止的算法使绘制效率提高10％以上.     

并行精确排序的快速投影四面体体绘制

投影四面体法需要对四面体集合进行逐帧排序,而相邻四面体之间的顺序制约和依赖性限制了并行排序的效率.基于以上问题,提出一种视点相关的、基于逻辑切割的快速四面体集合精确排序方法.该方法分为4个串行步骤:首先沿视线方向将四面体集合所在空间剖分成一列有序的深度区间,每个区间包含一组四面体子集;然后并行地对每个区间的子集逐层提取互不遮挡的四面体,完成精确排序;再将区间边界上的四面体进行逻辑切割,并采用分段积分计算所有四面体在区间内的颜色贡献;最后按序沿视线方向累积所有区间的颜色贡献.实验结果表明,文中方法提高了四面体拓扑排序的并行度,极大地降低了排序时间,并大幅度地改进了绘制效率.     

基于自适应八叉树划分的高精度四面体可视化

利用八叉树结构将四面体数据转化为规则网格数据,能有效提高系统的交互性能.八叉树的划分层次越高,绘制效果越好,但数据的存储空间以及处理时间也将大幅增多.提出自适应的规则化表示方法来构建八叉树结构,改进原有的单一采样策略,并结合深度信息将采样结果转换成适用于GPU的八叉树纹理结构.然后采用光线投射算法来对体数据进行绘制,根据各区域深度不一的特点,提出了变步长的采样绘制策略.实验结果表明,本文方法降低了数据的空间存储量和处理时间,同时在绘制质量、绘制效率方面都得到了较大提高.     

一种新的多路归并排序网络

文中提出了一种新的多路归并排序网络,该网络基于倾斜与振荡多路归并排序算法．该网络有两个主要特点．一是其基本构件为ｋ－ｓｏｒｔｅｒｓ,即ｋ个数的排序器,ｋ为任意素数,而传统的排序网络的基本构件为两个数的排序,即２－ｓｏｒｔｅｒｓ．二是该网络的延迟可以小于传统的基于２－ｓｏｒｔｅｒｓ的Ｂａｔｃｈｅｒ排序网络．文中给出了该排序网络的具体实现;作为实例给出了Ｎ＝２７,ｋ＝３时的排序网络;分析了该网络的时间延迟;通过具体设计排序网络的基本构件２－ｓｏｒｔｅｒｓ和３－ｓｏｒｔｅｒｓ,表明这种新的多路归并排序网络和Ｂａｔｃｈｅｒ排序网络相比是一种高速的排序网络．     

一种三路划分快速排序的改进算法

快速排序是一种经典的排序算法,它的平均性能非常突出。针对快速排序在某些特殊情况下(如数据已有序或重复数据较多时)效率较低的问题进行了研究,对三路快速排序进行改进,使快速排序在特殊情况下也能保持较好的效率。通过大量的数据测试发现,该算法在最好情况下其性能在几个数量级上优于普通快速排序,在最坏情况下,其性能较普通快速排序无明显差距。改进后的三路快速排序是一种通用高效的排序算法,因此在某些情况下选用、该算法会获得更好的效率。     

基于体元投影的一种非规则数据场体绘制方法

随着科学计算可视化的发展及其在实践中的应用,非规则数据场的可视化已成为当前的研究热点之一。由于非规则场中样点的大小、形状和分布是不一致的,在成像时面临更多的困难。常用的方法有光线投射法,单元投影法,以及单元投影与光线投射相结合等算法。吸取了上述算法的优点,同时利用非规则数据场的一些特性,采用了一些加速措施来加速绘制。通过实验验证,可以达到比较理想的效果。     

基于快速求交的自适应光线投射法

光线投射是一个重要的体绘制算法,但直线上采样点的确定是非常费时的,也是影响体绘制实时性的重要因素。该文利用直线和平面族的交点可以快速求得直线上的采样点及其特征值,该方法充分利用了直线的相关性,避免了大量的三线性插值计算。该文还基于快速求交提出了自适应采用方法,以提高绘制图像的质量。     

基于多条件的单链表快速排序算法研究

单链表由于其存储结构的局限性,通常采用插入算法实现排序,速度很慢,满足不了大规模问题的速度要求。在分析了单链表结构特征及快速排序算法思想的基础之上,作者提出并实现了在单链表中基于多个条件的快速排序算法,从而极大提高了排序的效率。     

基于重心的多目标方案排序理论

一、引言多目标方案排序是个老问题,隶属于多元分析,是系统工程的必要环节之一,以往用得最多的方法     

适用于GPU的四面体体数据规则化与可视化

为实现三维不规则体数据场的高效绘制,提出一种适用于GPU的四面体体数据规则化和可视化算法.将以四面体为基本单元的稀疏体数据用一个有限深度的八叉树结构逼近,并将逼近误差表达为一个离散的完全空间哈希结构;然后将半规则的八叉树转换为规则的八叉树纹理(三维),并将完全空间哈希表转换为三维查找表,两者均可在绘制时快速随机取值,故可直接作为三维纹理在GPU中访问.通过这种双规则化的表示方法,可将四面体体数据的可视化转化为在GPU中并行地绘制2种三维纹理.实验结果表明,该算法在处理空间稀疏体数据时保证了较高的精度,同时减少了数据存储量.     

基于Quick Sorting的快速分页排序算法

提出了分页排序的概念和基于Quick Sorting的快速分页排序算法(Quick Page Sorting)以及基于Hinl缓存机制的算法实现技术。实验表明,在数万至数百万数据总量情况下,Quick Pagc Soring的速度比Quick Sorting快10倍左右,大大提高了应用系统的响应速度。     

任意类型的分类数据的快速排序

快速排序在数据部分相等或有序时,时间复杂度最坏为O（n2）。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O（n）,空间复杂度为O（1）。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。     

一种新型快速的排序算法

提出了一种简单快速的新的排序算法，并对其性能与快速排序算法的性能进行了实验比较。     

一种实型数据的快速排序算法

提出了一种针对实型数据的快速排序算法,并给出了算法的分析和关键的源程序段。该算法的时间复杂度为O(N),且附加存储空间极小,特别适合于数据量大的场合。     

基于医学体数据生成四面体网格的方法

为了从医学体数据直接构造四面体网格,提出一种基于栅格的网格生成算法.该算法的主要思想是从背景栅格中提取并填充代表区域边界的等值面.首先,对医学体数据进行预处理与采样,构建一个背景栅格.其次,用对偶方法从栅格提取三角表面网格,用于分段线性逼近等值面.然后,对栅格中所有位于等值面之内或与等值面相交的立方体,用预定义的模板分解成四面体单元.最后,用Laplacian平滑技术优化四面体网格.在均匀网格的基础上,研究了自适应网格生成算法,在保持网格几何精度的同时精简单元数量,以提高有限元计算效率.给出了从CT数据生成人体股骨远端四面体网格的实例,该网格模型被用于虚拟膝关节镜手术.     

基于数据分布特性的快速排序

文中提出了一种基于数据分析特性的快速排序算法，根据被排数据的分布行性，选择数据比较次数和数据移动次数较少的排序算法，当被排数据存在ｍ个有序序列时，其算法的时间复杂度为Ｏ（ｎｌｏｇ２ｍ）其中ｍ∈（１，ｃｆ√ｎ），ｃ为某一常数，其最佳性能为Ｏ（ｎ）。当ｍ≥ｃ（√ｎ）时，保持快速排序的最佳平均性能，使排序运行于较优状态下。     

一种针对异常点的自适应回归特征选择方法

数据集中含有不相关特征和冗余特征会使学习任务难度提高,特征选择可以有效解决该问题,从而提高学习效率和学习器性能.现有的特征选择方法大多针对分类问题,面向回归问题的较少,特别是当数据集含异常点时,现有方法对异常点敏感.虽然某些方法可以通过给样本损失函数加权来提高其稳健性,但是其权值一般都已预先设定好,且在特征选择和学习器训练过程中固定不变,因此方法的自适应性不强.针对上述问题,提出了一种针对异常点的回归特征选择方法(adaptive weight LASSO, AWLASSO),它首先根据回归系数更新样本误差,并通过自适应正则项将误差大于当前阈值的样本的损失函数赋予较小权重,误差小于阈值的样本的损失函数赋予较大权重,再在更新权重后的加权损失函数下重新估计回归系数,不断迭代上述过程.AWLASSO算法采用阈值来控制样本是否参与回归系数的估计,在阈值作用下,误差较小的样本才可参与估计,所以迭代完成后会获得较优的回归系数估计.另外,AWLASSO算法的阈值不是固定不变的,而是不断增大的(为使初始回归系数估计值较准确,其初始值较小),这样误判为异常点的样本可以重新进入训练集,并保证训练集含有足够的样本.对于误差大于最大阈值的样本点,由于其学习代价较大,算法将其识别为异常点,令其损失函数权重为0,从而有效降低了异常点的影响.在构造数据和标准数据上的实验结果表明：对于含有异常点的数据集,提出的方法比经典方法具有更好的稳健性和稀疏性.