A generalized greedy routing algorithm for 2-connected graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent, which makes this scheme infeasible in some applications.The essence of the geometric routing is the following: When an origin vertex u wants to send a message to a destination vertex w, it forwards the message to a neighbor t, solely based on the location information of u,w and all neighbors of u. In the greedy routing scheme, the decision is based on decreasing distance. For this idea to work, however, the decision needs not be based on decreasing distance. As long as the decision is made locally, this scheme will work fine.In this paper, we introduce a version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance, a generalized greedy routing algorithm uses other criteria to determine routing paths, solely based on local information. We present simple generalized greedy routing algorithms based on st-coordinates (consisting of two integers between 0 and n−1), which are derived from an st-orientation of a 2-connected plane graph. We also generalize this result to arbitrary trees. Both algorithms are natural and simple to be implemented.     

Blowing Bubbles for Multi-Scale Analysis and Decomposition of Triangle Meshes

Tools for the automatic decomposition of a surface into shape features will facilitate the editing, matching, texturing, morphing, compression and simplification of three-dimensional shapes. Different features, such as flats, limbs, tips, pits and various blending shapes that transition between them, may be characterized in terms of local curvature and other differential properties of the surface or in terms of a global skeletal organization of the volume it encloses. Unfortunately, both solutions are extremely sensitive to small perturbations in surface smoothness and to quantization effects when they operate on triangulated surfaces. Thus, we propose a multi-resolution approach, which not only estimates the curvature of a vertex over neighborhoods of variable size, but also takes into account the topology of the surface in that neighborhood. Our approach is based on blowing a spherical bubble at each vertex and studying how the intersection of that bubble with the surface evolves. We describe an efficient approach for computing these characteristics for a sampled set of bubble radii and for using them to identify features, based on easily formulated filters, that may capture the needs of a particular application.     

基于聚类的字典压缩技术在GIS中的应用研究

本文主要探讨了基于字典的矢量地图压缩中字典的设计问题,提出了一种新颖的基于聚类方式的字典设计方法,它可以使字典更好的近似于某种特定的数据集。实验证明只要字典结构适合,这种基于聚类方式的字典数据压缩技术可获得更好的压缩效果。     

HSC: A multi-resolution clustering strategy in Self-Organizing Maps applied to astronomical observations

This work presents a strategy for the classification of astronomical objects based on spectrophotometric data and the use of unsupervised neural networks and statistical classification algorithms. Our strategy constitutes an essential part of the preparation phase of the automatic classification and parameterization algorithms for the data that are to be collected by the Gaia satellite of the European Space Agency (ESA), whose launch is foreseen for the spring of 2012. The proposed algorithm is based on a hierarchical structure of neural networks composed of various tree-structured SOM networks. The classification of possible astronomical objects (stars, galaxies, quasars, multiple objects, etc.) basically consists in the iterative segmentation of the inputs space and the ensuing generation of initial classifications and increase in classification precision by means of a refining process. Apart from providing a classification, our technique also measures the quality and precision of the classifications and segments the objects for which it cannot determine whether or not they belong to a pre-established class of astronomical objects (outliers).     

一种新的地形图汉字注记自动提取算法

地形图中包含大量的汉字注记,为了实现地图要素自动识别,首先要将文字正确地提取出来。该文通过对汉字特征的分析,提出了一种新的汉字提取算法。首先根据地图图像的特点进行骨架运算,利用形态算子对汉字笔画进行分解,最后实现对汉字注记的笔画统计提取。该算法较好地解决了字线粘连、旋转等情况下的汉字提取问题,具有良好的稳定性。     

A*算法在矢量地图最优路径搜索中的应用

在交通地理信息系统应用中,如何既快速又准确地找到最优路径是一个关键的问题.将人工智能领域的A*算法引入到矢量地图的最优路径搜索中来,论述了应用于矢量地图最优路径搜索的A*算法是一种完备的算法.同时,针对交通矢量地图的特点,提出了一种将矢量地图本身节点的数据结构和A*算法需搜索的节点数据结构在索引时相互联系,在计算时又相互分离的策略,提高了A*算法的执行效率.实验表明这种改进数据结构的A*算法在准确性和快速性方面都取得了令人满意的效果.     

基于多尺度稀疏LSSVM的时间序列预测

最小二乘支持向量机在提高了支持向量机的运算速度的同时,失去了解的稀疏性.构造的多尺度稀疏最小二乘支持向量机,首先通过小波包分解对于数据进行多尺度描述,同时采用最小二乘支持向量机的学习算法获得数据之间的尺度相关性,可以实现解的稀疏性和可解释性,从而实现了系统的多尺度分解、子系统建模与合成的一体化.通过在时间序列预测上的应用可以发现,此模型在获得稀疏解的同时,极大地提高了系统的性能.而且,可以获得输出结果在不同尺度上的贡献度,增加了系统的可解释性.     

一种基于道路知识的矢量地图数据校正方法

准确完整的交通矢量地图是车辆导航、路径寻优等应用工作的良好基础.为了解决交通矢量地图的错误数据信息问题,在分析城市道路分布特点的基础上,提出了一种基于道路知识的矢量地图数据校正方法.将矢量数据信息中普遍存在的错误进行分类,通过对城市道路设计规范和城市道路相关知识的归纳,抽取出对各种类型错误的判定规则和校正算法,为矢量地图的校正提供了一种较新的思路.实验结果表明,该算法能够快速有效的检测和校正矢量地图数据信息中存在的各类问题,能够保证矢量地图拓扑的准确性和完整性.     

基于多尺度分析的地基云图自动识别的研究

研究地基云图自动识别问题.地基云图由于受光照旋转等影响,传统方法提取的特征难以准确描述图像特征,导致地基云图识别的精度较低,还无法达到实际应用的要求.为了提高地基云图识别精度,提出采用多尺度分析的地基云图自动识别算法.首先将地基云图划分为若干个大小相同互不重叠的子图,然后采用三种不同尺度的权重局部二值模式提取每一幅子图的纹理特征,最后将子图的纹理特征顺序排列获取最终鉴别特征.通过对积雨云,高积云和层积云三类地基云图进行分类识别,实验结果表明改进方法可以增强云图的局部特征描述能力,有效提高地基云图分类的精度.     

神经网络技术下多尺度时序数据离群点挖掘

在大量的网络数据中,可能隐藏着少许攻击序列,离群点是由异常机制产生,不服从数据的普遍分布规律,设计一个基于神经网络的多尺度时序数据离群点挖掘方法.采用对象与其类别聚类中心的相似度来测量对象属于聚类的程度,确定检测对象的邻域,采用神经网络技术对多尺度时序数据离群点挖掘,初始化BP神经网络,基于网络的实际输出和预期输出,判...     

Web mining based on Growing Hierarchical Self-Organizing Maps: Analysis of a real citizen web portal

This work is focused on the usage analysis of a citizen web portal, Infoville XXI (http://www.infoville.es) by means of Self-Organizing Maps (SOM). In this paper, a variant of the classical SOM has been used, the so-called Growing Hierarchical SOM (GHSOM). The GHSOM is able to find an optimal architecture of the SOM in a few iterations. There are also other variants which allow to find an optimal architecture, but they tend to need a long time for training, especially in the case of complex data sets. Another relevant contribution of the paper is the new visualization of the patterns in the hierarchical structure. Results show that GHSOM is a powerful and versatile tool to extract relevant and straightforward knowledge from the vast amount of information involved in a real citizen web portal.     

Self-Organizing Maps and Learning Vector Quantization for Feature Sequences

The Self-Organizing Map (SOM) and Learning Vector Quantization (LVQ) algorithms are constructed in this work for variable-length and warped feature sequences. The novelty is to associate an entire feature vector sequence, instead of a single feature vector, as a model with each SOM node. Dynamic time warping is used to obtain time-normalized distances between sequences with different lengths. Starting with random initialization, ordered feature sequence maps then ensue, and Learning Vector Quantization can be used to fine tune the prototype sequences for optimal class separation. The resulting SOM models, the prototype sequences, can then be used for the recognition as well as synthesis of patterns. Good results have been obtained in speaker-independent speech recognition.     

一种基于整体拓扑结构的对地图中线对象的细化算法

本文针对传统细化算法国有的局限性，结合地图中线对象的特点，提出一种新的细化算法。该算法基于图段，通过确定节点位置及其相互间连接关系，从全局上把握图形拓扑结构。充分利用整体信息，无需细化选代，减少了运算量，同时很好地避免了交点略变现象。     

适合地图数据库应用的可扩充数据模型研究

数据库地理信息系统（ＧＩＳ）的基础。复杂的ＧＩＳ应用要求它对用户定义的数据类型和操作具有扩充能力。该文针对用于ＧＩＳ的可扩充数据模型存在的问题。构造了一个适合地图数据库应用的可扩充数据模型。它以嵌套关系模型为基础。引入高阶算子定义操作。这些算子不但增强了代数操作的能力，而且利用它们能方便地扩充用户定义的几何操作、地图量算和几何变换。该模型具有较强的扩充能力，可以作主设计可扩充地图数据库系统的基础。     

无向图语言

无向图是图论中的基本概念,图半群是1991年提出的一个概念,形式语言与自动机理论是计算机科学与技术科学的重要基础理论。借助无向图和图半群,提出了无向图语言的概念,并研究了无向图语言的一个子类——平面图语言,给出了如下结论:一个无向图语言是平面图语言当且仅当它不包含K5语言或K3,3语言的剖分图语言。另外提出了几个开问题,其中之一是无向图语言与正则语言、上下文无关语言、上下文有关语言以及短语结构语言有何关系?     

SVG与矢量地图的Web发布技术

随着在近几年来人们利用Web作为交流与信息交换的重要方式的快速增长,图形、图像的重要性越来越突出。可以毫不夸张地说Web能够被越来越多的人所接受在很大程度上是由于Web上图形的出现。SVG是最近几年来在Web上很流行的矢量图形格式,它是一种基于XML的二维矢量图形,正在被越来越多的用户和业界所使用。文章将就其特点、在Web上使用的优势、以及用于地图发布使用的技术和应用前景做一全面的介绍。     

几何活动轮廓模型的多尺度扩散分割算法

提出了一种对几何活动轮廓模型中的停止速度场进行多尺度扩散的算法,它通过引进2个控制参数来定义停止速度场的目标边界、同质区域和过渡区域;对于不同复杂性的图像,采取不同的控制参数对其停止速度场进行多尺度扩散;并将多尺度扩散后的停止速度场应用于几何活动轮廓模型进行图像分割.实验结果表明:对1幅合成图像和2幅自然图像,该算法大大地减少了分割时间,在一定程度上也减少了边界泄漏.     

基于时空图的轮廓线模型研究

主动轮廓线模型(Snakes)具有能够结合先验知识和图像特征的理论价值,但由于能量局部极值问题的困扰,而鲜已用于实际问题。前人通过改进优化算法来提高其分割效果。文章则尝试从Snakes的外部力入手,引入时空图的光流特征,通过改造能量函数提高分割效果。实验对比验证在复杂背景下,基于时空图的轮廓线模型依然可以有效跟踪运动物体,此时普通Snakes模型必须做大量手动调整。而它同时也解决了帧差等视频分割方法难于识别、提取目标轮廓的问题。时空图轮廓线模型抓住了运动目标的图像特征,在简单的优化算法下依然可以得到较好的分割效果,可以用实时系统。     

地形环境的视点相关模型构造及仿真

实时显示大尺度地形环境是环境是视觉仿真系统的需要,地形的精细程度与视点相关是解决绘制精度和速度的有效手段之一。该文根据视点相关模型的原理,分析了地形模型构造的一般算法,对模型简化过程中的合法性检测,数据结构和排序提出了改进方法,并在微机上进行了仿真,取得较好的效果。