用遗传算法提取基元

基元提取是基于模型的计算机视觉的一项重要任务。Ｈｏｕｇｈ变换是基元提取的最常用的方法,然而,在许多情况下,它的存贮开销太大而难以让人接受。近些年来,有些人用统计学方法来提取基元,但如何构造合适的代价函数角是一个困难问题。基元提取等同于寻找具有多个局部极小值的代价函数的最优解。遗传算法（Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ）能够有效地在搜索空间中找出全局最优解。为实现有效的基元提取,作者从几何数据点     

随机Hough变换与Tabu搜索算法在基元提取中的比较

Ｈｏｕｇｈ变换（ＨＴ）是目前应用最广的几何基元提取方法,其基本思想在于通过证据积累来提取基元。最近不少人又提出了通过代价函数的全局优化来提取几何基元的思想。随机Ｈｏｕｇｈ变换（ＲＨＴ）和Ｔａｂｕ搜索（ＴＳ）分别是Ｈｏｕｇｈ变换和优化方法中的佼佼者。ＲＨＴ和ＴＳ分别基于不同的策略,两种方法的相互比较在许多文献中已有提及,但目前尚无较完整的理论分析和系统的比较。本文在提取单个基元所需对最小点集的采样次     

应用遗传算法原理确定函数的最优解

本文主要介绍了一种新型的、随机性的全局优化方法即遗传算法.一般应用于在一个问题的解集中查找最优解情况,如是一个问题有多个答案,但是想查找一个最优答案的话,那么使用遗传算法可以达到更快更好的效果.即在浮点编码遗传算法中加入一个函数,构成适于不可微函数全局优化的遗传算法.该算法改善了遗传算法的局部搜索能力,显著提高了遗传算法求得全局解的概率.     

基于遗传算法的以线段和圆弧为基元的曲线拟合

采用线段和圆弧作逼近基元是数字曲线拟合中的一个难点。文中给出一种基于改进遗传算法的拟合方法。通过对点列进行二进制编码，以拟合段数较少和拟合误差较小为优化目标，变异概率和交叉概率自适应生成，并根据相关知识控制分界点间隙，所得最优解中值为1的基因对应数字曲线的分界点，对线段与圆弧相交和相切以及具有噪声等多种情况进行检测，可同时提取尖点和切点，还可得到逼近基元及其之间关系。较好地解决了用线段和圆弧拟合曲线问题。     

一种有效的面向多目标软硬件划分的遗传算法

软硬件划分是软硬件协同设计的关键技术之一,划分结果对最终的设计方案有非常重要的影响。软硬件划分根据优化目标的数量,可分为单目标划分和多目标划分。多目标划分问题是一个NP-hard问题,一般不存在传统意义上的“最优解”,而是存在一组互不支配的Pareto最优解。遗传算法因其具有并行、群体搜索的特点而非常适于求解多目标优化问题。通过抽象描述将一个实际SOC设计问题转化为多目标软硬件划分问题,采用遗传算法便可获得最优设计方案。为克服过早收敛及加快搜索速度,改进了适应度函数的定义,通过自适应参数调整,加入惩罚函数的适应度定义,提高了进化速度,从而有效地获得了Pareto最优解集。在实际问题的应用中,多目标软硬件划分遗传算法是能有效求取平衡系统成本、硬件面积、功耗和时间特性的最优化方案。     

一个基于插值的解非线性双层规划的遗传算法

非线性双层规划问题是一类递阶优化问题,相关的算法往往需要对每一个上层变量值求一个下层优化问题才能得到一个可行点,这使得算法的计算量很大.目前文献中的算法通常都是基于对每个确定的上层变量,下层最优解唯一的条件,这就意味着每个下层变量的分量都可以看成是上层变量的函数.基于这个思想,同时为了避免频繁计算下层优化问题,文中提出了一种新的方法.这种方法与已有方法的主要不同之处在于,它不需频繁求解下层规划,而是用插值函数近似下层最优解函数.其主要思想如下:首先,取一些上层变量值作为插值节点,计算它们对应的下层问题的最优解,这些最优解的第i个分量作为第i个插值函数的函数值,利用这些节点和函数值计算插值函数;其次,将插值函数代入上层问题,得到一个近似原问题的单层规划;最后用一个新的遗传算法求解该单层规划.由于插值节点和相应的插值函数在进化过程中自适应修正和更新,这样可使得该单层规划问题的最优解逐步逼近原问题的最优解,并且可减少计算量.对25个测试问题的仿真结果表明,该文所提出的算法能以较少的计算量找到这些问题的最好解.     

基于贪心算法和模拟退火算法的软硬件划分

软硬件划分是嵌入式系统设计过程中一个关键环节,已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛,且找到的全局最优解的质量不佳等问题,提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的0-1背包问题,在求解背包问题的算法基础上用贪心算法构造出初始划分解;然后,对代价函数的解空间进行合理的区域划分,并基于划分的区间设计新的代价函数,采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明,与目前已有的类似改进算法相比,新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右,具有高效性和实用性。     

基于遗传算法的圆柱几何特征信息的测量

研究了各种测量圆柱信息的方法,提出了用遗传算法实现圆柱几何特征信息全局最优解的评定。对需要求的圆柱几何特征信息之间增加约束关系,减少了需要遗传算法评价的参数个数,并提高了遗传算法的收敛速度。建立了用遗传算法实现圆柱度误差最小区域法评定时目标函数数学模型的计算方法。通过实验,在给定不同的遗传算法参数下进行多次评定,该方法都能收敛到全局最优解,并计算稳定,收敛速度快,在计算机上容易实现。     

基于遗传算法的摄像机自标定方法

针对摄像机自标定方法大多需要求解一个多元高维的非线性方程组,其求解过程非常困难,为此提出一种基于遗传算法的摄像机自标定方法,该方法通过二幅或多幅图像的多个对应匹配特征点,利用二个视图之间的极几何关系,建立某些相关约束,最后得到一个代价函数;然后,通过使用Matlab遗传算法工具箱来求解该函数的最小值,进而一次性求出摄像机所有内、外参数.因为该方法不必用到摄像机的外部信息,所以可推广到序列图像中的变参数情况下的摄像机自标定.实验结果表明,该方法简单、有效、快速,可用于摄像机自标定.     

基于遗传算法的汽车永磁发电机多目标优化设计

提出了一种基于遗传算法的汽车永磁发电机多目标优化设计。该设计通过改进的遗传算法进行多目标优化。改进的遗传算法采用二进制编码,规范化几何秩选择,混合交叉及均匀变异。优化结果表明,在单目标函数和多目标函数情形下均搜索到全局最优解,遗传算法为多目标优化提供了有效的途径。同时经过反复计算后,获得一些具有实用价值的经验数据,对永磁电机的设计起到一定指导作用。     

A tabu search method for geometric primitive extraction

In this paper, we propose a novel method for extracting the geometric primitives from geometric data, which is essentially an optimization problem. Specifically, we use tabu search to solve geometric primitive extraction problem. To the best of our knowledge, it is the first attempt that tabu search is used in computer vision. Our tabu search (TS) has a number of advantages: (1) TS avoids entrapment in local minima and continues the search to give a near-optimal final solution; (2) TS is very general and conceptually much simpler than either simulated annealing (SA) or genetic algorithm (GA); (3) TS has no special space requirement and is very easy to implement (the entire procedure only occupies a few lines of code); (4) our TS-based method can successfully extract some geometric primitives which are specially difficult for the traditional methods such as Hough Transform (HT) and Robust Statistics (RS). TS is a flexible framework of a variety of strategies originating from artificial intelligence and is therefore open to further improvement.     

Geometric primitive extraction using a genetic algorithm

Extracting geometric primitives from geometric sensor data is an important problem in model-based vision. A minimal subset is the smallest number of points necessary to define a unique instance of a geometric primitive. A genetic algorithm based on a minimal subset representation is used to perform primitive extraction. It is shown that the genetic approach is an improvement over random search and is capable of extracting more complex primitives than the Hough transform     

Constructing Isosurfaces from 3D Data Sets Taking Account of Depth Sorting of Polyhedra

Creating and rendering intermediate geometric primitives is one of the approaches to visualisze data sets in 3D space.Some algorithms have been developed to construct isosurface from uniformly distributed 3D data sets.These algorithms assume that the function value varies linearly along edges of each cell.But to irregular 3D data sets,this assumption is inapplicable.Moreover,the detth sorting of cells is more complicated for irregular data sets,which is indispensable for generating isosurface images or semitransparent isosurface images,if Z-buffer method is not adopted.In this paper,isosurface models based on the assumption that the function value has nonlinear distribution within a tetrahedron are proposed.The depth sorting algorithm and data structures are developed for the irregular data sets in which cells may be subdivided into tetrahedra.The implementation issues of this algorithm are discussed and experimental results are shown to illustrate potentials of this technique.     

WCL: A co-ordination language for geographically distributed agents

In this paper a tuple space based co-ordination language, and a run-time system which supports it, is described. The co-ordination language is called WCL, and it is designed to support agent co-ordination over the Internet between agents which are geographically distributed. WCL uses tuple spaces as used in Linda. WCL provides a richer set of primitives than traditional tuple space based systems, and provides asynchronous and synchronous tuple space access, bulk tuple primitives, and streaming primitives which, as a whole, provide a complete framework more suited to co-ordination over the Internet compared with the Linda primitives. The primitives emphasise efficiency and location transparency (of data and agents) and this is exploited in the current run-time system used to support WCL. The run-time system described in this paper is distributed and uses location transparency and dynamic analysis of tuple space usage to migrate tuple spaces around the distributed system. Some initial experimental results are given which demonstrate the performance gains of using the tuple space migration. The paper motivates the inclusion of many of the primitives, and demonstrates how a well designed set of primitives provides performance and efficiency. The JavaSpace primitives are used as an example of how the choice of primitives can detrimentally affect the efficiency of the language, and exclude required co-ordination constructs.     

Conceptual design, manufacturability evaluation and preliminary process planning using function-form relationships in stamped metal parts

A large number of design decisions are made during the conceptual design of a part. However, there are few representation and reasoning tools for decision support during conceptual design. The conceptual design stage is characterized by a lack of complete geometric information. Existing geometric modelers require complete geometric information, while a functional reasoning methodology using a <verb, noun > representation is typically too terse. In this paper, we present a new representation called sketching abstraction for conceptual design, using the function-form relations in a design. The functionally critical part of the geometry is presented using a set of functional features, while the rest of the geometry is abstracted as a set of linkages. Part functionality is correlated with the sketching abstraction using data structures called function-form matrices. The sketching abstraction is annotated using a set of primitives, and a set of grammar rules are used to extract canonical relationships between the functional features. The sketching abstraction can be used for extracting designs that are geometrically dissimilar but functionally similar, thus providing the designer with ideas for design alternatives. The sketching abstraction can also be used to carry out domain-dependent manufacturability evaluation checks. A further use of sketching abstractions is to initiate the development of a process plan for manufacturing. Sketching abstractions are related to the solid model of a part. Thus, this representation provides a link between pure functional and pure geometric representations. The domain of application is stamped metal parts. We present the part functionality and the features used in this domain. We also illustrate the use of sketching abstractions for conceptual design, manufacturability evaluation and preliminary process planning.     

随机Hough变换的概率模型:有限数据点

该文研究了基于有限个数据点的随机Hough变的的概率模型，在这个模型中，主要讨论了在随机Hough变换的基本算法中起相当关键作用的两个量，累加器数组的控制以及从图像中提取全部基元所需随机抽样的总次数，这两个量对随机Hough变换的算法设计及其终止规则是相当有用的。该文的主要结果包括两部分，其一是对累加器数组引入了多项分布，系统地研究了累加器数组的概率结构及其相互关系，同时也计算了提取全部基元所需的随机抽样总次数的分布，均值和方差，另者是基于不断的随机抽样而使得累加器数组的随机变化。作者引入了多维纯生过程，有了提取全部基元所需随机抽样的总次数服从离散的PH分布，从而它的各阶矩都可用简洁的矩阵形式统一地表出，针对于图像的固有因素，作者也讨论了基元的平稳提取概率，该文的结果为随机Hough变换的进一步研究和应用提供了较为严格的理论依据。     

Automated Derivation of Primitives for Movement Classification

We describe a new method for representing human movement compactly, in terms of a linear super-imposition of simpler movements termed primitives. This method is a part of a larger research project aimed at modeling motor control and imitation using the notion of perceptuo-motor primitives, a basis set of coupled perceptual and motor routines. In our model, the perceptual system is biased by the set of motor behaviors the agent can execute. Thus, an agent can automatically classify observed movements into its executable repertoire. In this paper, we describe a method for automatically deriving a set of primitives directly from human movement data.We used movement data gathered from a psychophysical experiment on human imitation to derive the primitives. The data were first filtered, then segmented, and principal component analysis was applied to the segments. The eigenvectors corresponding to a few of the highest eigenvalues provide us with a basis set of primitives. These are used, through superposition and sequencing, to reconstruct the training movements as well as novel ones. The validation of the method was performed on a humanoid simulation with physical dynamics. The effectiveness of the motion reconstruction was measured through an error metric. We also explored and evaluated a technique of clustering in the space of primitives for generating controllers for executing frequently used movements.     

From on-line sketching to 2D and 3D geometry: a system based on fuzzy knowledge

The paper describes the development of a fuzzy knowledge-based prototype system for conceptual design. This real time system is designed to infer user's sketching intentions, to segment sketched input and generate corresponding geometric primitives: straight lines, circles; arcs, ellipses, elliptical arcs, and B-spline curves. Topology information (connectivity, unitary constraints and pairwise constraints) is received dynamically from 2D sketched input and primitives. From the 2D topology information, a more accurate 2D geometry can be built up by applying a 2D geometric constraint solver. Subsequently, 3D geometry can be received feature by feature incrementally. Each feature can be recognised by inference knowledge in terms of matching its 2D primitive configurations and connection relationships. The system accepts not only sketched input, working as an automatic design tool, but also accepts user interactive input of both 2D primitives and special positional 3D primitives. This makes it easy and friendly to use. The system has been tested with a number of sketched inputs of 2D and 3D geometry.     

基于遗传算法的基元识别应用

基于遗传算法能提高图像处理的速度和准确率,在吸取前人实践经验的基础上,对遗传算法在基元识别和提取中的应用策略进行了研究,并得到了满意的结果.因此在简单分析遗传算法基础之上,设计了利用该算法进行基元识别和提取的模型,同时结合利用Visual C 数字图像处理的理论基础和应用框架搭建了一个能够进行完整的基元识别和提取的应用程序.最后通过图示展示了通过VC 实现了基于遗传算法的基元识别的部分仿真结果.     

Automatic and interactive evolution of vector graphics images with genetic algorithms

Vector graphics are popular in illustration and graphic design. Images are composed of discrete geometric shapes, such as circles, squares, and lines. The generation of vector images by evolutionary computation techniques, however, has been given little attention. JNetic is an implementation of a comprehensive evolutionary vector graphics tool. Vector primitives available range from simple geometric shapes (circles, polygons) to spline-based paint strokes. JNetic supports automatic and user-guided evolution, chromosome editing, and high-detail masks. Automatic evolution involves measuring the pixel-by-pixel colour distance between a candidate and target image. Masks can be painted over areas of the target image, which help reproduce the high-detail features within those areas. By creative selection of primitives and colour schemes, stylized interpretations of target images are produced. The system has been successfully used by the authors as a creative tool.