An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning

Human beings' intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic,so as to improve running efficiency and suitability of shortest path algorithm for traffic network.The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path.It is argued that the shortest path,no matter distance shortest or time shortest,is usually not the favorite of drivers in practice.Some factors difficult to expect or quantify influence the drivers' choice greatly.It makes the drivers prefer choosing a less shortest,but more reliable or flexible path to travel on.The presented optimum path algorithm,in addition to the improvement of the running efficiency of shortest path algorithms up to several times,reduces the emergence of those factors,conforms to the intellection characteristic of human beings,and is more easily accepted by drivers.Moreover,it does not require the completeness of networks in the lowest hierarchy and the applicability and fault tolerance of the algorithm have improved.The experiment result shows the advantages of the presented algorithm.The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks.     

An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning

Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms. It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic, so as to improve running efficiency and suitability of shortest path algorithm for traffic network. The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path. It is argued that the shortest path, no matter distance shortest or time shortest, is usually not the favorite of drivers in practice. Some factors difficult to expect or quantify influence the drivers’ choice greatly. It makes the drivers prefer choosing a less shortest, but more reliable or flexible path to travel on. The presented optimum path algorithm, in addition to the improvement of the running efficiency of shortest path algorithms up to several times, reduces the emergence of those factors, conforms to the intellection characteristic of human beings, and is more easily accepted by drivers. Moreover, it does not require the completeness of networks in the lowest hierachy and the applicability and fault tolerance of the algorithm have improved. The experiment result shows the advantages of the presented algorithm. The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks.     

加权路网分层的最优路径计算

为了弥补传统分层算法在平面最短路径计算中对出行者出行习惯考虑不充分的缺陷,该文提出了一种分层算法的优化策略,即加权路网分层:首先运用层次分析法计算选定的道路属性的权值,对道路属性权值进行组合相加,进而确定道路权值,然后根据确定的分层阈值对路网进行分层,最后运用双向A*算法进行试验,并与传统的分层路网计算结果进行比较。实验结果表明,加权分层策略充分考虑了出行者的出行习惯,能够适用于路径导航中的最优路径计算,具有可行性与实用性。     

深度优先搜索的地图着色算法

在分析地图着色本质以及深度优先搜索算法优缺点基础上,本文提出一种基于深度优先搜索的地图着色方法,并以全国地图和全国县级行政区划图对本文算法进行了实验验证,取得了较好的着色结果.     

改进的分层点云数据压缩算法

针对传统点云压缩算法主要对小型物件的小数据量精细点云进行压缩,在大型地物的海量数据压缩方面存在压缩时间长、效率低的不足,提出了一种改进的分层点云数据压缩算法。基于大型地物点云空间结构特点将分层压缩算法的速度优势和距离压缩算法的高效优势相结合,解决了传统压缩算法在大型地物点云压缩方面的不足,实现了海量点云的快速高效压缩。西安市大雁塔三维激光点云压缩实验结果表明:该算法可以快速地完成海量点云的压缩,较之传统压缩算法极大地缩短了压缩时间,提高压缩效率。     

彩色扫描地形图的分色方法

本文提出了一种新的地形图分色方法。首先去除背景像素,然后根据灰度梯度值提取主色像素,利用直方图模糊c-均值(FCM)聚类方法对主色像素进行颜色聚类,对去背景后的图像进行Canny算子的边缘检测。最后,利用加壳变换和障碍距离变换工具对符号周围的过渡像素进行聚类,从而实现黑棕兰绿四个分版图的提取。该方法效率较高,受图纸扫描质量的影响不大,分色效果较理想。     

城市级无人机影像匀色算法

无人机在获取影像时,受到天气、光照条件、相机传感器、主观人为等多种因素的影响,导致获取的影像内部或影像之间存在不同程度的亮度与色调分布不均匀,因此需要对无人机影像进行匀光匀色处理。本文提出了灰度值均值算法、基于相机响应函数的灰度值误差参数算法两种匀光匀色算法,并将其应用于镇江市实景三维数据建设无人机影像处理。试验结果表明,两种算法均能较好地去除色差,使色调过渡更缓和,可改善后期的实景三维整体效果,对城市级实景三维建设相关项目具有较好的借鉴作用。     

利用层次聚类对移动曲面拟合滤波算法快速分类的研究

经典移动曲面滤波算法由于算法简练,适用范围广泛且滤波效果较好,适用于多种地形。但是传统移动曲面滤波方法存在较多缺陷,如计算阈值参数难以确定、各个格网间阈值参数缺少相关性、分类主要依据高差阈值及水平距离相关性较小等缺点。文中提出层次聚类算法,将三维地形转换为二维平面,利用相邻点水平距离和高差构建数据集,进行聚类判断点云的属性,采用ISPRS提供的15组样本,定性和定量分析本算法的滤波精度。为验证本聚类算法的优越性和科学性,同时与改进型移动曲面和PTD滤波算法进行精度对比,充分说明本算法相较于其他算法的优越性和高效性。     

层次特征点控制的线状要素Morphing方法

针对多尺度表达中同名线要素的变换问题,提出一种层次特征点控制下的线状要素Morphing变换方法,在已有的线性插值Morphing变换基础上,利用层次特征点对线要素进行分段控制,按对应弧段的结点的相对位置在本弧段的相同的相对位置处插入点,提高插值过程中点的位置对应精度,使中间比例尺的插值表达得到优化,提高Morphing变换的精度。     

An adaptive dual clustering algorithm based on hierarchical structure: A case study of settlement zoning

Traditional dual clustering algorithms cannot adaptively perform clustering well without sufficient prior knowledge of the dataset. This article aims at accommodating both spatial and non‐spatial attributes in detecting clusters without the need to set parameters by default or prior knowledge. A novel adaptive dual clustering algorithm (ADC+) is proposed to obtain satisfactory clustering results considering the spatial proximity and attribute similarity with the presence of noise and barriers. In this algorithm, Delaunay triangulation is utilized to adaptively obtain spatial proximity and spatial homogenous patterns based on particle swarm optimization (PSO). Then, a hierarchical clustering method is employed to obtain clusters with similar attributes. The hierarchical clustering method adopts a discriminating coefficient to adaptively control the depth of the hierarchical architecture. The clustering results are further refined using an optimization approach. The advantages and practicability of the ADC+ algorithm are illustrated by experiments on both simulated datasets and real‐world applications. It is found that the proposed ADC+ algorithm can adaptively and accurately detect clusters with arbitrary shapes, similar attributes and densities under the consideration of barriers.     

A multiresolution hierarchical classification algorithm for filtering airborne LiDAR data

We presented a multiresolution hierarchical classification (MHC) algorithm for differentiating ground from non-ground LiDAR point cloud based on point residuals from the interpolated raster surface. MHC includes three levels of hierarchy, with the simultaneous increase of cell resolution and residual threshold from the low to the high level of the hierarchy. At each level, the surface is iteratively interpolated towards the ground using thin plate spline (TPS) until no ground points are classified, and the classified ground points are used to update the surface in the next iteration. 15 groups of benchmark dataset, provided by the International Society for Photogrammetry and Remote Sensing (ISPRS) commission, were used to compare the performance of MHC with those of the 17 other publicized filtering methods. Results indicated that MHC with the average total error and average Cohen’s kappa coefficient of 4.11% and 86.27% performs better than all other filtering methods.     

一种基于HVS和自适应小波变换的彩色图像水印算法

数字水印技术是实现数字产品产权保护的一种新方法。本文提出了一种基于HVS和自适应小波变换的彩色图像水印改进算法。首先利用改进的自适应小波变换对原始图像进行处理,然后采用混合置乱算法对水印图像进行处理。同时根据HVS的特点来确定水印的嵌入强度。实验证明这种算法具有较好的隐蔽性,对各种图像处理操作是鲁棒的。     

一种新型遥感影像快速匹配算法

An iterative algorithm to calculate mutual correlation using hierarchical key points and the search space mark principle is proposed. An effective algorithm is designed to improve the matching speed. By hierarchical key point algorithm and mutual correlation coefficients of the matching images, the important points can be iteratively calculated in the images hierarchically, and the correlation coefficient can be obtained with satisfactory precision. Massive spots in the parameter space which are impossible to match can be removed by the search space mark principle. Two approximate continuities in the correlation image matching process, the image gray level distribution continuity and the correlation coefficient value in the parameter space continuity, are considered in the method. The experiments show that the new algorithm can greatly enhance matching speed and achieve accurate matching results.     

嵌入式GIS中最优路径规划算法研究与实现

针对现有大区域范围路径规划算法存在的一些问题,提出一种多比例尺最优路径规划算法。该算法在进行路径规划时,在小区域范围内根据道路的属性信息对路网进行分层,在大区域范围内根据多比例尺信息对路网进行分级,在每级或每层内采用基于弧段的改进型A*算法。从实例分析可以看出,该算法能较好满足车载导航系统的需求。     

一种基于分层约束的露天矿DEM构建方法

针对边坡的台阶状地形特征是露天矿地形表达的关键和难点问题,该文基于边坡台阶要素的空间关系建立边坡层次关系模型,采用一种逐层加入扩展点和约束线的方法生成扩展约束TIN模型,将某露天煤矿作为实验区,实现了露天矿DEM的动态建模。结果表明:提高了边坡坡面的层级可视化效果,保持了地形结构的完整性,实现了边坡实体单元的分层次表达,能够获得不同水平层次的DEM数据。基于边坡特征分析的分层约束方法为露天矿DEM的构建提供了一种思路,可为边坡监测、灾变分析和灾情预测等领域提供精确的地形数据。     

A fewest-turn-and-shortest path algorithm based on breadth-first search

Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled. However, the optimality of paths for current navigation system is often judged purely on the distance travelled or time cost, and not the path simplicity. To balance these factors, this paper presented an algorithm to compute a path that not only possesses fewest turns but also is as short as possible by utilizing the breadth-first-search strategy. The proposed algorithm started searching from a starting point, and expanded layer by layer through searching zero-level reachable points until the endpoint is found, and then deleted unnecessary points in the reverse direction. The forward searching and backward cleaning strategies were presented to build a hierarchical graph of zero-level reachable points, and form a fewest-turn-path graph (G*). After that, a classic Dijkstra shortest path algorithm was executed on the G* to obtain a fewest-turn-and-shortest path. Comparing with the shortest path in Baidu map, the algorithm in this work has less than half of the turns but the nearly same length. The proposed fewest-turn-and-shortest path algorithm is proved to be more suitable for human beings according to human cognition research.     

A hierarchical indexing strategy for optimizing Apache Spark with HDFS to efficiently query big geospatial raster data

ABSTRACT

Earth observations and model simulations are generating big multidimensional array-based raster data. However, it is difficult to efficiently query these big raster data due to the inconsistency among the geospatial raster data model, distributed physical data storage model, and the data pipeline in distributed computing frameworks. To efficiently process big geospatial data, this paper proposes a three-layer hierarchical indexing strategy to optimize Apache Spark with Hadoop Distributed File System (HDFS) from the following aspects: (1) improve I/O efficiency by adopting the chunking data structure; (2) keep the workload balance and high data locality by building the global index (k-d tree); (3) enable Spark and HDFS to natively support geospatial raster data formats (e.g., HDF4, NetCDF4, GeoTiff) by building the local index (hash table); (4) index the in-memory data to further improve geospatial data queries; (5) develop a data repartition strategy to tune the query parallelism while keeping high data locality. The above strategies are implemented by developing the customized RDDs, and evaluated by comparing the performance with that of Spark SQL and SciSpark. The proposed indexing strategy can be applied to other distributed frameworks or cloud-based computing systems to natively support big geospatial data query with high efficiency.     

A Similarity-Based Approach for Improving the Efficiency of Drawing Spatiotemporal Point Features

ABSTRACT

The mapping of spatiotemporal point features plays an important role in geovisualization. However, such mapping suffers from low efficiency due to computational redundancy when similar symbols are used to visualize spatiotemporal point features. This paper presents a similarity-based approach to predict and avoid computational redundancy, which improves mapping efficiency. First, to identify computational redundancy, the similarity of point symbols is measured based on commonalities in symbol graphics and symbol drawing operations. Second, a similarity-enhanced method is proposed to comprehensively predict and avoid computational redundancies when mapping spatiotemporal point features. This approach was tested using two real-world spatiotemporal datasets. The results suggest that the proposed approach offers relatively large performance improvements.     

一种快速二维 Delaunay 三角网点定位算法

在构建二维Delaunay三角网的逐点插入法中,定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。针对目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,结合三角形重心的几何性质,对点定位算法进行改进,避免求三角形重心和相交边的过程。实验结果表明,文中算法较目前其他点定位算法能够有效地缩短搜索路径,减少点定位的计算时间,提高Delaunay三角网构网过程中点定位的效率。     

基于多尺度虚拟网格与坡度阈值的机载LiDAR点云滤波方法

点云滤波是机载LiDAR数据后处理的基础工作,本文提出一种基于多尺度虚拟网格与坡度阈值的机载LiDAR点云滤波方法。该方法采用类似影像金字塔的方式构建不同尺度即不同分辨率的虚拟网格,各级网格都以每个方格内最低点作为地面种子点,然后根据坡度阈值以分辨率由低到高的方式逐层对种子点进行平滑处理,最后以最高分辨率即最小尺度虚拟网格地面种子点作为基准种子点对整个数据集进行滤波处理。本文分别采用城区与郊区两块机载LiDAR数据进行了实验。实验表明,该方法能够有效地提取出地面点,运算效率也比较高,具有一定的实用价值。