Computing Minimum Area Homologies

Calculating and categorizing the similarity of curves is a fundamental problem which has generated much recent interest. However, to date there are no implementations of these algorithms for curves on surfaces with provable guarantees on the quality of the measure. In this paper, we present a similarity measure for any two cycles that are homologous, where we calculate the minimum area of any homology (or connected bounding chain) between the two cycles. The minimum area homology exists for broader classes of cycles than previous measures which are based on homotopy. It is also much easier to compute than previously defined measures, yielding an efficient implementation that is based on linear algebra tools. We demonstrate our algorithm on a range of inputs, showing examples which highlight the feasibility of this similarity measure.     

Automating correctness verification of artifact-centric business process models

ContextThe artifact-centric methodology has emerged as a new paradigm to support business process management over the last few years. This way, business processes are described from the point of view of the artifacts that are manipulated during the process.ObjectiveOne of the research challenges in this area is the verification of the correctness of this kind of business process models where the model is formed of various artifacts that interact among them.MethodIn this paper, we propose a fully automated approach for verifying correctness of artifact-centric business process models, taking into account that the state (lifecycle) and the values of each artifact (numerical data described by pre and postconditions) influence in the values and the state of the others. The lifecycles of the artifacts and the numerical data managed are modeled by using the Constraint Programming paradigm, an Artificial Intelligence technique.ResultsTwo correctness notions for artifact-centric business process models are distinguished (reachability and weak termination), and novel verification algorithms are developed to check them. The algorithms are complete: neither false positives nor false negatives are generated. Moreover, the algorithms offer precise diagnosis of the detected errors, indicating the execution causing the error where the lifecycle gets stuck.ConclusionTo the best of our knowledge, this paper presents the first verification approach for artifact-centric business process models that integrates pre and postconditions, which define the behavior of the services, and numerical data verification when the model is formed of more than one artifact. The approach can detect errors not detectable with other approaches.     

一种基于AOS格式的多相水平集快速分割方法

采用迎风格式的水平集算法实现需要在曲线演化过程中重新初始化水平集函数的要求,为保证算法的稳定,时间步长选取较小值,算法运行速度较慢。文中基于无须重新初始化的水平集方法,在算法数值实现中引入AOS半隐格式,对基于不同统计模型的水平集分割算法给出统一的数值实现。以二相水平集分割算法为基础提出一种新的多相水平集分割方法。该方法采用一个水平集函数进行多次演化实现多区域分割,其优点包括：1)采用AOS半隐格式,该格式无条件稳定,可采用较大的时间步长;2)对多个统计模型进行统一处理;3)采用单一的水平集函数进行演化,减少水平集演化方程的数量,算法更加灵活。实验结果表明,该方法具有较快的分割速度,对具有多个区域的图像能够进行较准确的分割。     

Designing Camera Networks by Convex Quadratic Programming

In this paper, we study the problem of automatic camera placement for computer graphics and computer vision applications. We extend the problem formulations of previous work by proposing a novel way to incorporate visibility constraints and camera‐to‐camera relationships. For example, the placement solution can be encouraged to have cameras that image the same important locations from different viewing directions, which can enable reconstruction and surveillance tasks to perform better. We show that the general camera placement problem can be formulated mathematically as a convex binary quadratic program (BQP) under linear constraints. Moreover, we propose an optimization strategy with a favorable trade‐off between speed and solution quality. Our solution is almost as fast as a greedy treatment of the problem, but the quality is significantly higher, so much so that it is comparable to exact solutions that take orders of magnitude more computation time. Because it is computationally attractive, our method also allows users to explore the space of solutions for variations in input parameters. To evaluate its effectiveness, we show a range of 3D results on real‐world floorplans (garage, hotel, mall, and airport).     

Construction-specific spatial information reasoning in Building Information Models

In recent years, there have been significant advances in modeling technology for object-oriented building products. However, the building models are still lacking of providing construction-specific spatial information required for construction planning. Consequently, construction planners visually analyze building product models and derive geometric characteristics such as bounded spaces and exterior perimeter to develop detailed construction plans. Such a process presents fragmented information flows, from building product information to construction planning, that rely on subjective decisions of construction planners. In order to overcome these drawbacks, this research proposes a geometric reasoning system that analyzes geometric information in building designs, derives the construction-specific spatial information, and uses the information to assist in construction planning. The scope of presented work includes detecting work packages formed by faces during construction, such as large work faces and bounded spaces, and using information in the work packages directly to support planning of selected indoor construction activities. The main features of the proposed system named Construction Spatial Information Reasoner (CSIR) include a set of relationship acquisition algorithms, building component relationship data structure, and interpretation of the relationship to support detailed construction activity planning. The relationship acquisition algorithms identify adjacency between building components that is stored in the relational data structure. Then, acquired adjacency relationships are transformed into a set of graphs that represent work packages. To implement the proposed approach, CSIR utilized a commercially-available Building Information Modeling (BIM) platform and the algorithms were imbedded to the BIM platform. For validation, CSIR was tested on a real commercial building. For interior ceiling grid installation activities, CSIR successfully detected existing work packages and analyzed the spatial characteristics impacting construction productivity. The major contribution of the presented research would be to enable a realistic analysis of building geometric condition that is not possible in current BIM and a seamless information flow from building product information to construction process plans. These can potentially reduce current manual and error-prone construction planning processes. Limitations and future research suggestions are also presented.     

搜索引擎系统：UML/OCL模型驱动开发

介绍一个搜索引擎系统的开发。运用UML用例图做系统的需求分析,运用UML类图、状态图、包图进行系统设计。以OCL表达式丰富状态图。使用C#语言和ASP.NET编程,SQL Server存储信息,系统运行在微软.NET环境上。遵循面向对象方法,如逐步求精和模块化,建立UML/OCL模型、组织程序,将系统逐层分解成具有特定功能的模块。系统由收集器、索引器、检索器三大部分组成,分别负责数据收集、数据分析和索引构建、用户检索接口。论文报告系统分析、设计和实现的思想和过程。     

基于OPENGL的树木场景渲染分析与实现

研究了基于OPENGL的树木生成算法与树木场景渲染模式,针对自然界中的植被场景中植物的三维建模难以实现高效、快速、准确的实时渲染的难题,为改善树木形态结构建模与实时渲染的效果和速度,提出了一种面向GPU的针对叶簇的渲染架构,给出了树木建模与渲染的具体实现算法,并完成了三维替代物渲染技术,结合叶簇不同形态,采用基于几何模型的枝干渲染和基于2.5维替代物的叶簇渲染,较大地提升了视觉效果的真实性,使树木建模与实时渲染效率和准确性均得到明显提高。仿真结果表明,树木场景渲染实现模式能够较好的满足图像处理需求。     

High Performance GPU‐based Proximity Queries using Distance Fields

Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.     

Reconstructing head models from photographs for individualized 3D‐audio processing

Visual fidelity and interactivity are the main goals in Computer Graphics research, but recently also audio is assuming an important role. Binaural rendering can provide extremely pleasing and realistic three‐dimensional sound, but to achieve best results it's necessary either to measure or to estimate individual Head Related Transfer Function (HRTF). This function is strictly related to the peculiar features of ears and face of the listener. Recent sound scattering simulation techniques can calculate HRTF starting from an accurate 3D model of a human head. Hence, the use of binaural rendering on large scale (i.e. video games, entertainment) could depend on the possibility to produce a sufficiently accurate 3D model of a human head, starting from the smallest possible input. In this paper we present a completely automatic system, which produces a 3D model of a head starting from simple input data (five photos and some key‐points indicated by user). The geometry is generated by extracting information from images and accordingly deforming a 3D dummy to reproduce user head features. The system proves to be fast, automatic, robust and reliable: geometric validation and preliminary assessments show that it can be accurate enough for HRTF calculation.     

Solving a real-time allocation problem with constraint programming

In this paper, we present an original approach (CPRTA for “Constraint Programming for solving Real-Time Allocation”) based on constraint programming to solve a static allocation problem of hard real-time tasks. This problem consists in assigning periodic tasks to distributed processors in the context of fixed priority preemptive scheduling. CPRTA is built on dynamic constraint programming together with a learning method to find a feasible processor allocation under constraints. Two efficient new approaches are proposed and validated with experimental results. Moreover, CPRTA exhibits very interesting properties. It is complete (if a problem has no solution, the algorithm is able to prove it); it is non-parametric (it does not require specific tuning) thus allowing a large diversity of models to be easily considered. Finally, thanks to its capacity to explain failures, it offers attractive perspectives for guiding the architectural design process.