首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 140 毫秒
1.
Singularity Analysis of Geometric Constraint Systems   总被引:1,自引:0,他引:1       下载免费PDF全文
Singularity analysis in an important subject of the geometric constraint satisfaction problem.In this paper,three kinds of singularities are described and corresponding identifcation methods are presented for both under0constrained systems and over-constrained systems,Another special but common singularity for under-constrained geometric systems,pseudo-singularity,is analyzed.Pseudo-singularity is caused by a variety of constraint mathching of under-constrained systems and can be removed by improving constraint distribution.To avoid pseudo-singularity and decide redundant constraints adaptively,a differentiaiton algorithm is proposed in the paper.Its corrctness and effciency have been validated through its practical applications in a 2D/3D geometric constraint solver CBA.  相似文献   

2.
The model for improving the robustness of sparse principal component analysis(PCA) is proposed in this paper. Instead of the l2-norm variance utilized in the conventional sparse PCA model,the proposed model maximizes the l1-norm variance,which is less sensitive to noise and outlier. To ensure sparsity,lp-norm(0 p 1) constraint,which is more general and effective than l1-norm,is considered. A simple yet efficient algorithm is developed against the proposed model. The complexity of the algorithm approximately linearly increases with both of the size and the dimensionality of the given data,which is comparable to or better than the current sparse PCA methods. The proposed algorithm is also proved to converge to a reasonable local optimum of the model. The efficiency and robustness of the algorithm is verified by a series of experiments on both synthetic and digit number image data.  相似文献   

3.
The situation of multi-region problem may oftem appear when boundary element method(BEM)is applied in practical problems especially in VLSI-CAD.It is difficult to deal with this problem if traditional methods are used.Particularly. when the problem to be solved contains a lot of materials,the advantages of using BEM such as simplicity,convenience and rapidity will be weakened due to the complexity of solving complex boundary element equation.In this paper a distributed algorithm for multi-region problem in BEM is presented.This algorithm has been implemented in a distributed system consisting of 3 workstations to extract VLSI layout parameters.The results show that the calculation time of this distributed algorithm is less than that of the traditional methods.The results also demonstrate that this algorithm can speed up the computation and has the features of parallelism and high efficiency.  相似文献   

4.
We note that some existing algorithms are based on the normalized least-mean square (NLMS) algorithm and aim to reduce the computational complexity of NLMS all inherited from the solution of the same optimization problem, but with different constraints. A new constraint is analyzed to substitute an extra searching technique in the set-membership partial-update NLMS algorithm (SM-PU-NLMS) which aims to get a variable number of updating coefficients for a further reduction of computational complexity. We get a closed form expression of the new constraint without extra searching technique to generate a novel set-membership variable-partial-update NLMS (SM-VPU-NLMS) algorithm. Note that tile SM-VPU-NLMS algorithm obtains a faster convergence and a smaller mean-squared error (MSE) than the existing SM-PU-NLMS. It is pointed out that the closed form expression can also be applied to the conventional variable-step-size partial-update NLMS (VSS-PU-NLMS) algorithm. The novel variable-step-size variable-partial-update NLMS (VSS-VPU-NLMS) algorithm is also verified to get a further computational complexity reduction. Simulation results verify that our analysis is reasonable and effective.  相似文献   

5.
This paper presents an adaptive sub-carrier and power allocation scheme for orthogonal frequency division multiple access (OFDMA) systems according to their different quality of service (QoS) requirements and traffic type. The algorithm maximized the transmission data rate while satisfying total power constraint and a certain bit error rate (BER) requirement. A greedy algorithm known to be the most efficient algorithm for this problem can provide a high quality optimal solution, but has the disadvantage of incurring a long computation time. This problem should be solved in a real-time environment. The proposed algorithm not only avoids the high complexity but also provides considerable universality and flexibility for both the fixed rate voice data and variable rate multimedia data of the broadband wireless communication. It mainly consists of two steps. The first is the allocation of sub-carriers and power alternately to the real-time user. The second is the residual resource distribution to the non-real-time users. The simulation results demonstrate that the scheme has computational advantages over the conventional algorithms while providing the QoS guarantee.  相似文献   

6.
A new geometric constraint model is described,which is hierarchical and suitable for parametric feature based modeling.In this model,different levels of geometric information are repesented to support various stages of a design process.An efficient approach to parametric feature based modeling is also presented,adopting the high level geometric constraint model.The low level geometric model such as B-reps can be derived automatically from the hig level geometric constraint model,enabling designers to perform their task of detailed design.  相似文献   

7.
An adaptive weighted stereo matching algorithm with multilevel and bidirectional dynamic programming based on ground control points (GCPs) is presented. To decrease time complexity without losing matching precision, using a multilevel search scheme, the coarse matching is processed in typical disparity space image, while the fine matching is processed in disparity-offset space image. In the upper level, GCPs are obtained by enhanced volumetric iterative algorithm enforcing the mutual constraint and the threshold constraint. Under the supervision of the highly reliable GCPs, bidirectional dynamic programming framework is employed to solve the inconsistency in the optimization path. In the lower level, to reduce running time, disparity-offset space is proposed to efficiently achieve the dense disparity image. In addition, an adaptive dual support-weight strategy is presented to aggregate matching cost, which considers photometric and geometric information. Further, post-processing algorithm can ameliorate disparity results in areas with depth discontinuities and related by occlusions using dual threshold algorithm, where missing stereo information is substituted from surrounding regions. To demonstrate the effectiveness of the algorithm, we present the two groups of experimental results for four widely used standard stereo data sets, including discussion on performance and comparison with other methods, which show that the algorithm has not only a fast speed, but also significantly improves the efficiency of holistic optimization.  相似文献   

8.
Terrain Visualization is an important part of visualization systems of battlefield, and the visualization of dynamic terrain is also important for dynamic battle environment. In this paper, special attention has been paid on real-time optimally adapting meshes (ROAM) algorithm, which is a candidate for dynamic terrain, and its mesh representation, mesh continuity algorithm and error metrics are discussed. The DEXTER-ROAM algorithm is discussed and analyzed. By revising the mesh representation of ROAM, a dynamic ROAM algorithm based on partial-regular grid is established. By introducing transition region, mesh discontinuity of dynamic partial-regular grid is resolved. Error metric blocks are removed for computation complexity and culling blocks are introduced to accelerate view frustum culling. The algorithm is implemented in a 3D rendering engine called OGRE. In the end, an example of dynamic crater is given to examine the dynamic ROAM algorithm.  相似文献   

9.
This paper is concerned with the resource allocation for multiple input multiple output and orthogo- nal frequency division multiplexing access (MIMO-OFDMA) downlink cognitive radio systems where a cognitive radio MIMO-OFDMA system is under spectrum sharing with an existing primary radio (PR) network. We use the channel learning scheme to estimate the channel information from cognitive radio transmitter (CR-TX) to PR and then make beamforming to transmit signal. Considering the interference from CR-TX to PR caused by the imperfect channel learning, we intend to maximize CR throughput under the interference power constraint at PR and CR transmit power constraint. A nearly optimal subcarrier and power allocation algorithm with linear complexity is proposed. The proposed algorithm is global optimal when the maximum transmit power is beyond certain threshold. Simulation results show that the proposed algorithm has a good performance very close to the global optimal algorithm.  相似文献   

10.
In order to improve the concurrency of multiversion database systems,a conservative MV locking-graph scheduler algorithm is proposed,which takes the power of MVS as a target.The algorithm combines the advantages of locking and graph,and does optimizing processes on read-only and write-only operations to reduce the blocks of transactions.The correctness and complexity of the algorithm are also provided.  相似文献   

11.
基于几何约束求解的完备方法   总被引:2,自引:0,他引:2  
针对参数化CAD在约束求解中的应用,提出了基于智能连杆的算法,该算法在扩充几何作图范围、改善算法复杂度方面都有明显的优势.将其同LIMO算法、几何变换方法、C-Tree算法、数值求解方法等方法相互融合,能够组成一套非常完备的几何约束求解框架,来完成对平面和空间几何约束问题的自动求解与图像生成.将该算法应用于智能动态几何软件的设计中,实验显示可以取得令人满意的结果.  相似文献   

12.
几何约束求解的方法关系到特征造型系统的性能,为提高几何约束求解的速度,将和声搜索算法应用于几何约束求解中。通过优先选择较小的和声库,利用最好解的评价值确定微调扰动的幅度,并将其嵌入到拉斯维加斯算法中,提高了和声搜索算法的性能。实验结果表明,改进的和声算法具有自适应性,能有效克服局部收敛问题,提高了求解速度。  相似文献   

13.
Most geometric construction methods of geometric constraint solving systems use line and circle (rule and compass) as basic drawing tools. In this paper, by introducing conics and linkages, we provide a set of complete drawing tools for the construction approach of geometric constraint solving. Using these tools, we may enlarge the drawing scope of the construction approach and still keep the elegant style of geometric solutions to geometric constraint solving. As applications, we obtain pure geometric solutions to three sets of well-known constraint problems: the 10 Apollonian drawing problems, the 13 cases of a smallest tri-connected constraint graph, and constraint problems with distance constraints only.  相似文献   

14.
This paper describes new ways to tackle several important problems encountered in geometric constraint solving, in the context of CAD, and which are linked to the handling of under- and over-constrained systems. It presents a powerful decomposition algorithm of such systems.Our methods are based on the witness principle whose theoretical background is recalled in a first step. A method to generate a witness is then explained. We show that having a witness can be used to incrementally detect over-constrainedness and thus to compute a well-constrained boundary system. An algorithm is introduced to check if anchoring a given subset of the coordinates brings the number of solutions to a finite number.An algorithm to efficiently identify all maximal well-constrained parts of a geometric constraint system is described. This allows us to design a powerful algorithm of decomposition, called W-decomposition, which is able to identify all well-constrained subsystems: it manages to decompose systems which were not decomposable by classic combinatorial methods.  相似文献   

15.
面向欠约束几何系统的一种同伦求解方法   总被引:3,自引:1,他引:3       下载免费PDF全文
针对几何约束系统的数值求解过程中,经常发生的数值不稳定性问题,构造了一种面向欠约束系统的同伦方法,并将其与现有的求解与分解方法有机地结合起来,提出了一种牛顿-同伦混合方法,在牛顿迭代失败的位置自动调用欠约束同伦法,既提高了几何约束求解器的效率,同时又保证了求解的效率。  相似文献   

16.
在基于有向图表达的几何约束系统中,几何约束的匹配方向、分布状态以及有向图中强连通分量的规模直接影响到整个约束系统的求解;如何对几何约束系统进行合理规划,得到正确有效的求解序列,是目前约束分解研究的重要内容。该文提出了一个规划分解算法,它针对欠约束几何系统的特点,能够优化约束的初始匹配方向,对于约束匹配过程中生成的强连通子图,通过调整约束匹配方向,自适应地改善约束分布,从而减小强连通子图的规模,以求得到几何约束系统正确而高效的求解序列。同时,基于规划分解算法,完成了约束的奇异性分析,提供了面向分解的奇异性分析算法。  相似文献   

17.
几何约束求解是CAD建模中的关键技术。针对求解质量不高和求解速度慢的问题,进行了研究。提出了一种鱼群算法和混沌算法相结合的几何约束求解方法。首先,将CAD模型中的几何约束关系表示为一组代数方程组;然后,利用代数方程组来构造目标函数。将几何约束求解问题转换为目标函数的优化问题。最后,使用混沌算法来改进鱼群算法以寻找目标函数的最优解。实验结果表明:该方法可以有效地解决几何约束问题。  相似文献   

18.
目的针对传统量子遗传算法无法充分利用种群中未成熟个体信息的不足,提出了基于交互更新模式的量子遗传算法(IUMQGA)并应用于几何约束求解中。方法几何约束问题的约束方程组可转化为优化模型,因此约束求解问题可以转化为优化问题。采用将遗传算法与量子理论相结合的量子遗传算法,使用双串量子染色体结构,使用交互更新策略将遗传算法中的交叉操作利用量子门变换来实现,根据不同情况采用不同的交互更新策略。这里的交互,指的是两个个体进行信息交换的过程,该过程用以产生新的个体。这不仅增加了个体间信息的交换而且充分利用了种群中未成熟个体的信息,提高了算法的收敛速度。结果通过非线性方程实例和几何约束实例测试并与其他方法比较表明,基于交互更新模式的量子遗传算法求解几何约束问题具有更好的求解精度和求解速率。双圆外公切线问题实例中,IUMQGA算法比QGA算法稳定;单圆填充问题和双圆外公切线问题实例中,通过实验求得各变量的最优值与其相应的精确值的误差在1E-2以下。结论采用交互更新模式的量子遗传算法可以很好地求解几何约束问题。  相似文献   

19.
A Constructive Approach to Solving Geometric Constraint Systems   总被引:1,自引:0,他引:1  
This paper proposes a constructive approach to solving geometric constraint systems.The approach incorporates graph-based and rule-based approaches, and achieves interactive speed.The paper presents a graph representation of geometric conStraint syStems, and discusses in detailthe algorithm of geometric reasoning based on poinl-cluster reduction. An example is made forillustration.  相似文献   

20.
提出一种基于分组重写的解决三维几何约束的方法,原有的算法在解决大型系统几何约束求解时效率较低,系统开销较大,并且由于算法规则的局限性,使得很多复杂系统无法解决,包括三维几何约束问题。该方法提出了两种新的分组表示类型,拓展子集和放射子集,使得分组更加直观,准确,并有效地提高了求解效率,减小了开销,方法在三维领域更能发挥其作用,能够满足计算机辅助造型中集合造型的需求。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号