Computation of Irradiance from Triangles by Adaptive Sampling

We introduce an algorithm for sample positioning in a planar triangle, which can be used to make numerical integration of an arbitrary function defined on it. This algorithm has some interesting properties which make it suitable for applications in the context of realistic rendering. We use an adaptive triangle partitioning procedure, driven by an appropriate measure of the error. The underlying variance is shown to be bounded, and in fact it can be controlled, so that it approaches the minimum possible value. We show results obtained when applying the method to irradiance computation, in the context of final-gather algorithms. We also describe a C++ class which offers all required functionality, and we made available its source code.     

基于时空划分的数据流挖掘

基于时空划分的思想,设计概要数据结构的在线生成算法。概要数据结构保存流数据不同时刻的分布状态,以支持离线阶段的分类、聚类和关联规则发现等数据挖掘操作。研究时间粒度、量化向量调整和子区域索引等3项内存需求控制策略,以平衡概要数据结构的内存需求和内外存之间的I／O次数。     

基于时空划分的数据流挖掘

基于时空划分的思想,设计概要数据结构的在线生成算法。概要数据结构保存流数据不同时刻的分布状态,以支持离线阶段的分类、聚类和关联规则发现等数据挖掘操作。研究时间粒度、量化向量调整和子区域索引等3项内存需求控制策略,以平衡概要数据结构的内存需求和内外存之间的I/O次数。     

Improved Binary Space Partition merging

This paper presents a new method for evaluating boolean set operations between Binary Space Partition (BSP) trees. Our algorithm has many desirable features, including both numerical robustness and O(n) output sensitive time complexity, while simultaneously admitting a straightforward implementation. To achieve these properties, we present two key algorithmic improvements. The first is a method for eliminating null regions within a BSP tree using linear programming. This replaces previous techniques based on polygon cutting and tree splitting. The second is an improved method for compressing BSP trees based on a similar approach within binary decision diagrams. The performance of the new method is analyzed both theoretically and experimentally. Given the importance of boolean set operations, our algorithms can be directly applied to many problems in graphics, CAD and computational geometry.     

基于划分策略和填充曲线的抖动模式研究

抖动处理是计算机图形学和图像处理中的一项关键技术,抖动算法的好坏直接关系互图像打印质量的优劣,针对利用评价函数生成较大抖动模式比较困难的问题,提出了划分初始模式的方法,并渐进生成较大抖动模式,针对模式抖动中出现的边界赝象,引入填充曲线机制加以消除,实验表明,采用以上方法得到的结果比较令人满意。     

采用元组聚类的增量式数据分区方法

数据分区是提升数据库可扩展能力的有效方法。在事务查询密集的系统中,合理的分区策略可减少分布式事务查询数量,并提高事务查询响应速度。提出了一种基于元组聚类的增量式分区方法,通过将元组聚簇和采用分区感知的数据筛选策略来降低算法的复杂度。首先依据时间窗口模型聚类元组,并构建簇节点图,然后利用分区感知策略对图进行删减,最后采用图划分算法对图进行子图划分来得到分区。与现有方法相比,该方法减少了分区响应时间,保证了较少的分布式事务数量,并提高了分区事务查询速度。     

二值图像矩形划分优化编码研究

针对二值图像矩形划分编码在表示矩形顶点时存在的冗余位,提出了两种优化编码方法。一种是缩减信源的自适应算术编码,通过增加运算复杂度提高编码效率,另一种是列等分相邻位置关联编码（CA-APRE）,CA-APRE充分利用了图像的行列先验结构信息,可减小复杂二值图像的码长15%-30%以上,且编码运算量与原方法相同,CA-RPRE在运算复杂度和编码效率方面明显优于自适应算术编码。     

Weight-proportional Space Partitioning Using Adaptive Voronoi Diagrams

Traditional application of Voronoi diagrams for space partitioning results in Voronoi regions, each with a specific area determined by the generators’ relative locations and weights. Particularly in the area of information space (re)construction, however, there is a need for inverse solutions; i.e., finding weights that result in regions with predefined area ratios. In this paper, we formulate an adaptive Voronoi solution and propose a raster-based optimization method for finding the associated weight set. The solution consists of a combination of simple, fixed-point iteration with an optional spatial resolution refinement along the regions’ boundaries using quadtree decomposition. We present the corresponding algorithm and its complexity analysis. The method is successfully tested on a series of ideal–typical cases and the interactions between the adaptive technique and boundary resolution refinement are explored and assessed.

Linear Size Binary Space Partitions for Uncluttered Scenes

We describe a new and simple method for constructing binary space partitions (BSPs) in arbitrary dimensions. We also introduce the concept of uncluttered scenes, which are scenes with a certain property that we suspect many realistic scenes exhibit, and we show that our method constructs a BSP of size O(n) for an uncluttered scene consisting of n objects. The construction time is O(n log n) . Because any set of disjoint fat objects is uncluttered, our result implies an efficient method to construct a linear size BSP for fat objects. We use our BSP to develop a data structure for point location in uncluttered scenes. The query time of our structure is O( log n) , and the amount of storage is O(n) . This result can in turn be used to perform range queries with not-too-small ranges in scenes consisting of disjoint fat objects or, more generally, in so-called low-density scenes. Received December 11, 1997; revised May 9, 1998.     

基于形体补偿的多面体二维消隐算法

三维形体的二维图形消隐一般被认为是不可能的。基于形体补偿的方法,提出了在没有直接给予深度信息的二维空间中对二维图形进行消隐藏面的方法。省去了物空间或象空间消隐算法中常用的深度求交与相关性测试,直接利用二维补偿环与候选可见面环之间的相关性进行布尔运算,取得了满意的效果。     

基于灾变遗传算法的二叉判定图最小化算法

二叉判定图广泛应用于形式验证,但相关算法存在节点规模过大的问题。提出了一种基于灾变遗传算法的二叉判定图最小化算法,它能在不扩大种群规模的情况下增加个体多样性,改善遗传算法局部收敛的问题。试验结果表明该算法的全局特性显著优于传统遗传算法,能够进一步减小节点规模,改善程度最高可达25%。而且,由于使用何种进化策略并不影响灾变的发生,因此,算法可扩展性好,极易与其他改进策略结合起来,在原有特性的基础上引入全局优势,以进一步减小节点规模。     

基于谱聚类的在线数据库垂直分区多阶段生成方法

垂直数据分区技术从逻辑上将满足一定语义条件的数据库表属性存放在同一个物理块中,进而降低数据访问成本,提高查询效率.数据库查询负载中的每条查询通常只与数据库表中的部分属性有关,因此只需使用数据库表的某个属性子集便可以得到准确的查询结果.合理的垂直数据分区方式可以使大多数查询负载不需要扫描完整数据库就可以完成查询任务,从而达到减少数据访问量,提高查询处理效率的目的.传统的数据库垂直分区方法主要基于专家设置的启发式规则,分区策略粒度较粗,且不能根据负载的特征进行有针对性的分区优化.同时,当负载规模较大或者属性个数较多时,现有垂直分区方法执行时间过长,尤其无法满足数据库在线实时调优的性能需求.为此,提出在线环境下基于谱聚类的垂直数据分区方法（spectral clustering based vertical partitioning,SCVP）,采用分阶段求解的思想,减少算法时间复杂度,加快分区执行速度.首先通过增加约束条件缩小解空间（即根据谱聚类生成初始分区）,然后对解空间设计算法进行精细的搜索（即采用频繁项集和贪心搜索相结合的策略对初始分区进行优化）.为了进一步提升SCVP在高维属性下的性能,提出了SCVP的改进版本SCVP-R （spectral clustering based vertical partitioning redesign）.SCVP-R通过引入同域竞争机制、双败淘汰机制和循环机制,对SCVP在分区优化过程中的合并方案进行了进一步优化.在不同数据集上的实验结果表明,相比于目前最好的垂直分区方法,SCVP和SCVP-R有着更快的执行时间和更好的性能表现.     

基于差异频度的类别空间模型的二值分类

针对目前文本分类中对向量空间模型的依赖以及文档频率（DF）特征提取方法在二值分类方面的不足,提出了基于差异频度的类别空间模型的二值分类方法,该方法突破了向量空间模型的限制,采用改进DF的差异频度方法进行特征提取,实现了二值分类功能。实验结果表明,改进的方法是有效的,其分类结果中精确率、召回率、F1测试值均有改善,提高了分类的准确率。并且本文的方法在其他领域的二值分类中同样值得借鉴。     

超图划分问题的元胞自动机模型及算法研究

对超图划分问题运用元胞自动机理论进行分析建模,提出一种元胞自动机模型以及基于该模型的赋权超图划分优化算法。在该模型中,元胞对应于赋权超图中的结点,邻接元胞对应于邻接超边所包含的结点,元胞的状态对应于所在的划分子集。引入二维辅助数组存储每条超边在划分子集中的结点个数,给出快速的元胞收益值和划分割切值的计算方法,从而避免遍历超边中的结点。实验结果表明,与赋权图划分算法和迁移方法相比,该算法可以取得更优的划分,且时间复杂度和空间复杂度较低。     

基于散度差准则的隐空间特征抽取方法

本文提出了一种新的非线性特征抽取方法——基于散度差准则的隐空间特征抽取方法。该方法的主要思想就是首先利用一核函数将原始输入空间非线性变换到隐空间，然后，在该隐空间中，利用类间离散度与类内离散度之差作为鉴别准则进行特征抽取。与现有的核特征抽取方法不同，该方法不需要核函数满足Mercer定理，从而增加了核函数的选择范围。更为重要的是，由于采用了散度差作为鉴别准则，从根本上避免了传统的Fisher线性鉴别分析所遇到的小样本问题。在ORL人脸数据库和AR标准人脸库上的试验结果验证了本文方法的有效性。     

基于多维整数空间的安全策略冲突检测与消解

针对当前大部分安全策略冲突检测与消解算法缺少灵活性和扩展性等缺点,提出一种基于多维整数空间的安全策略形式化描述方法,在此基础上设计了一种可扩展的安全策略冲突检测与消解算法,并证明其正确性,设计并实现能够自动对安全策略进行冲突检测与消解的工具SPCDRT。     

基于熵聚类模糊神经网络味觉信号识别系统的研究

提出了一种基于熵聚类的模糊神经网络味觉信号识别系统模型,该模型利用聚类方法实现模糊输入空间划分和模糊IF-THEN规则提取,并使用梯度下降法对系统参数进行精炼,系统兼具有良好的可解释性和学习能力,对11种矿泉水味觉信号的识别实验结果表明了该系统的可行性和有效性。     

一种基于HSV颜色空间的车辆牌照提取方法

给出了一种根据车牌底的彩色信息,利用HSV颜色空间对输入的含有汽车牌照的彩色图像直接进行处理,从而快速提取车牌照的方法。该方法的主要思想是通过选取合适的彩色空间将输入的彩色图像直接转换为二值图像,再用空问聚类技术进行滤波消噪,最后利用二值图像的水平垂直投影来分割提取车牌区域。     

基于二元光学的多通道SPR传感芯片及其系统设计

提出一种基于二元光学的新型多通道SPR传感芯片,及采用这种芯片的传感系统的设计方案。传感芯片集成有多组二元光学器件,取代传统光路中的透镜,实现光线的角向会聚。这种设计方案提高了SPR传感系统集成度,而且满足阵列化、多通道的检测要求。采用新型芯片设计制作的SPR传感系统能够完成对包含多个通道的敏感膜阵列的快速扫描和检测,与棱镜耦合结构相比还具有集成度高、灵敏度高、机械调节误差小、制作成本较低等优点。