Polygonal approximation of closed discrete curves

Optimal polygonal approximation of closed curves differs from the case of open curve in the sense that the location of the starting point must also be determined. Straightforward exhaustive search would take N times more time than the corresponding optimal algorithm for an open curve, because there are N possible points to be considered as the starting point. Faster sub-optimal solution can be found by iterating the search and heuristically selecting different starting point at each iteration. In this paper, we propose to find the optimal approximation of a cyclically extended closed curve of double size, and to select the best possible starting point by search in the extended search space for the curve. The proposed approach provides solution very close to the optimal one using at most twice as much time as required by the optimal algorithm for the corresponding open curve.     

A fast registration algorithm of rock point cloud based on spherical projection and feature extraction

Point cloud registration is an essential step in the process of 3D reconstruction. In this paper, a fast registration algorithm of rock mass point cloud is proposed based on the improved iterative closest point (ICP) algorithm. In our proposed algorithm, the point cloud data of single station scanner is transformed into digital images by spherical polar coordinates, then image features are extracted and edge points are removed, the features used in this algorithm is scale-invariant feature transform (SIFT). By analyzing the corresponding relationship between digital images and 3D points, the 3D feature points are extracted, from which we can search for the two-way correspondence as candidates. After the false matches are eliminated by the exhaustive search method based on random sampling, the transformation is computed via the Levenberg-Marquardt-Iterative Closest Point (LM-ICP) algorithm. Experiments on real data of rock mass show that the proposed algorithm has the similar accuracy and better registration efficiency compared with the ICP algorithm and other algorithms.     

An efficient approach for solving the straightness and the flatness problems at large number of data points

The construction of the convex hull as a critical step of solving the straightness and the flatness errors needs a great amount of computation, especially, when the number of data point is large, that limits the computational efficiency. To establish an efficient algorithm to solve these problems, three theorems are developed in this paper to show that the straightness and the flatness errors can be obtained without the construction of the whole convex hull. Theorem 1 shows how to identify the redundant data points that gives an efficient way to reduce the unnecessary computations. The optimum criterion defined in Theorem 2 shows that the optimum solution can be obtained by a small number of data points if these points meet the criterion. Theorem 3 offers an easy way to identify the potential candidates of the solution holders, which are data points on the vertices of the convex hull. The efficiency of the proposed algorithm is validated at the end of this paper. The validation results show that the computational efficiency of solving the straightness and the flatness problems is improved significantly through the proposed algorithm, especially, when the number of data point is large.     

Shape retrieval using triangle-area representation and dynamic space warping

In this paper, we present a shape retrieval method using triangle-area representation for nonrigid shapes with closed contours. The representation utilizes the areas of the triangles formed by the boundary points to measure the convexity/concavity of each point at different scales (or triangle side lengths). This representation is effective in capturing both local and global characteristics of a shape, invariant to translation, rotation, and scaling, and robust against noise and moderate amounts of occlusion. In the matching stage, a dynamic space warping (DSW) algorithm is employed to search efficiently for the optimal (least cost) correspondence between the points of two shapes. Then, a distance is derived based on the optimal correspondence. The performance of our method is demonstrated using four standard tests on two well-known shape databases. The results show the superiority of our method over other recent methods in the literature.     

改进的自适应快速整像素搜索算法

提出了一种改进的自适应快速整像素搜索算法。算法使用CSP进行粗定位搜索,并且根据分割块的尺寸,在SDSP和SSSP中选择合适的模板作为精确定位搜索的模板。为了进一步减少搜索点数,在粗定位搜索过程中加入由补偿数据和3个相邻块的SAD值确定的判断阈值,实现阈值的自适应变化。实验结果显示,与UMHSA和DSA相比,算法的搜索速率有较大的提高,同时亮度信号的平均峰值信噪比和编码字节数的变化不大。     

基于谱峰斜率进行变步长搜索的DOA估计方法

针对经典Capon方法存在计算量和存储量庞大、运行时间长、精准度不高的问题,提出一种低复杂度变步长的搜索算法.该方法首次搜索使用大步长的Capon算法,根据谱峰值确定波达方向(DOA)检测范围并求出其斜率值;然后根据斜率首次小于零确定谱峰在其左侧,记斜率小于零点为P,并从点P-2处开始向右进行变步长搜索;最后进行变步长的迭代逼近,得出期望信号的估计角度.所提方法避免了谱峰穷尽搜索,降低了计算量.仿真实验证明,在相同的信噪比下,所提算法准确性的精准度有近9倍的改善;在不同的信噪比下,所提算法的分辨成功率更高;同时,所提算法的均方根误差均明显优于经典的Capon算法.     

基于多分辨率搜索与多点云密度匹配的快速ICP-SLAM方法

针对激光SLAM（同步定位与地图创建）的实时性和定位精度问题,为了克服初始位姿不准确情况下增大搜索范围和位姿匹配分辨率对实时性的影响,本文在传统ICP-SLAM（迭代最近邻SLAM）基础上进行改进,提出了一种分层搜索与匹配的快速ICP-SLAM方法．首先,在搜索范围内采用由粗到细的分辨率进行全局搜索,并通过逐渐增加待匹配点的密度进行分步匹配计算．点云匹配过程中,通过构建距离像计算待匹配点的最近邻距离值,其计算复杂度降低为O（1）．其次,通过对点云匹配结果进行优先排序和剪枝,快速排除非最优解．最后,以半数全局最优与全数局部最优原则作为搜索结束判断条件,提高搜索效率．SLAM Benchmark数据集上的测试结果表明,相比于流行的激光SLAM算法Cartographer,所提出的方法取得了更小的平均误差和平方误差,计算效率为Cartographer算法的2~5倍．同时,工业AGV（自动导引车）的实际应用实验验证了在初始位姿未知的情况下,可实现实时的位姿估计与建图,重复定位精度优于1.5 cm．因此,这种快速ICP-SLAM方法能够保证实现准确的定位估计,具有良好的实时性．     

Adaptive random sample consensus approach for segmentation of building roof in airborne laser scanning point cloud

ABSTRACT

This work proposes a three-step method for segmenting the roof planes of buildings in Airborne Laser Scanning (ALS) data. The first step aims at mainly avoiding the exhaustive search for planar roof faces throughout the ALS point cloud. Standard algorithms for processing ALS point cloud are used to isolate building regions. The second step of the proposed method consists in segmenting roof planes within building regions previously delimited. We use the RANdom SAmple Consensus (RANSAC) algorithm to detect roof plane points, taking into account two adaptive parameters for checking the consistency of ALS building points with the candidate planes: the distance between ALS building points and candidate planes; and the angle between the gradient vectors at ALS building points and the candidate planes’ normal vector. Each ALS building point is classified as consistent if computed parameters are below corresponding thresholds, which are automatically determined by thresholding histograms constructed for both parameters. As the RANSAC algorithm can generate fragmented results, in the third step, a post-processing is accomplished to merge planes that are approximately collinear and spatially close. The results show that the proposed method works properly. However, failures occur mainly in regions affected by local anomalies such as trees and antennas. Average rates around 90% and higher than 95% have been obtained for the completeness and correction quality parameters, respectively.     

基于改进的SURF算子和透视变换模型的图像配准

对于传统的图像匹配算法存在特征信息少、错误匹配率高的问题,提出了一种基于改进的SURF算子和通过透视变换模型的图像配准算法。首先对传统的SURF描述符进行改进来进行特征点检测,然后用FLANN(Fast Library for Approximate Nearest Neighbors)搜索算法对检测出的角点进行粗匹配,再采用随机抽样一致(Random Samples Consensus,RANSAC)算法来消除粗匹配中误匹配的特征点对,最后将保留下来的精确匹配角点通过透视变换模型对图像进行配准。实验表明,该方法在光照、平移和模糊、旋转和尺度、视角变化具有更优的性能,提高了SURF算法的配准精度。     

An algorithm for the rapid generation of bas-reliefs based on point clouds

This paper proposes an algorithm for the rapid generation of bas-reliefs based on point clouds, which involves two steps: generation of a coarse model and establishment of fine mesh surfaces of the model. In the first step, a modified Z-Buffer algorithm is adopted to designate the visibility of every point before control points in a gridded distribution are arranged on the base plane of a relief. Afterwards, under the constraints of depth and normal information, the optimal compression ratio of the control points is obtained through use of a linear solution. For the compression ratio, bilinear interpolation is performed to generate an original model of the relief. In the establishment of the fine mesh surfaces, an index for measuring surface changes is proposed to adjust the height of the relief once again so as to highlight its detailed features. The aforementioned algorithm is verified by experimental work.     

并行机间歇过程生产调度的遗传局部搜索算法

研究了一类集成分批的并行机间歇过程调度问题(parallel machine batch process scheduling problem,简称PBPSP),将此问题转化为固定费用运输问题(6xed charge transportation problem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(genetic local search algorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明:GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率.     

Hybrid chaos optimization and affine scaling search algorithm for solving linear programming problems

In this study, we addressed Single Objective Linear Programming (SOLP). This article proposed a new combination of Chaos Optimization Algorithm (COA) with Affine Scaling Search (AFS) to be used as a Hybrid COA and AFS algorithm (Chaos AFS) for solving SOLP. The potential of COA as an emerging optimization algorithm to improve efficiency and effectiveness of AFS is investigated. Chaos AFS method is so-called numerical search algorithm that searches through the domain of decision variables of SOLP to obtain final feasible solution. An initial solution point, obtained from COA, will be used as starting solution point in AFS algorithm to improve the performance of AFS algorithm. The result shows that Hybrid COA and AFS for solving SOLP problems significantly improves the results of objective value compared to pure AFS and reduces the number of iteration steps compared to simplex and pure AFS.     

Organizing message transmission in AFDX networks

In this paper, a problem of periodical message transmission in the onboard networks based on the Avionics Full Duplex Ethernet (AFDX) standard is formalized and an algorithm for solving this problem is proposed. The algorithm combines the greedy approach with the limited exhaustive search and consists of several procedures to solve the problem step by step with respect to the constraints imposed. The results of the experimental research aimed at investigating the effectiveness of the proposed algorithm are presented.     

Projective Reconstruction from Multiple Views with Minimization of 2D Reprojection Error

The problem of projective reconstruction by minimization of the 2D reprojection error in multiple images is considered. Although bundle adjustment techniques can be used to minimize the 2D reprojection error, these methods being based on nonlinear optimization algorithms require a good starting point. Quasi-linear algorithms with better global convergence properties can be used to generate an initial solution before submitting it to bundle adjustment for refinement. In this paper, we propose a factorization-based method to integrate the initial search as well as the bundle adjustment into a single algorithm consisting of a sequence of weighted least-squares problems, in which a control parameter is initially set to a relaxed state to allow the search of a good initial solution, and subsequently tightened up to force the final solution to approach a minimum point of the 2D reprojection error. The proposed algorithm is guaranteed to converge. Our method readily handles images with missing points.     

A complete and efficient algorithm for searching 3-D form-closure grasps in the discrete domain

A complete and efficient algorithm is proposed for searching form-closure grasps of n hard fingers on the surface of a three-dimensional object represented by discrete points. Both frictional and frictionless cases are considered. This algorithm starts to search a form-closure grasp from a randomly selected grasp using an efficient local search procedure until encountering a local minimum. The local search procedure employs the powerful ray-shooting technique to search in the direction of reducing the distance between the convex hull corresponding to the grasp and the origin of the wrench space. When the distance reaches a local minimum in the local search procedure, the algorithm decomposes the problem into a few subproblems in subsets of the points according to the existence conditions of form-closure grasps. A search tree whose root represents the original problem is employed to perform the searching process. The subproblems are represented as children of the root node and the same procedure is recursively applied to the children. It is proved that the search tree generates O(KlnK/n) nodes in case a from-closure grasp exists, where K is the number of the local minimum points of the distance in the grasp space and n is the number of fingers. Compared to the exhaustive search, this algorithm is more efficient, and, compared to other heuristic algorithms, the proposed algorithm is complete in the discrete domain. The efficiency of this algorithm is demonstrated by numerical examples.     

基于多级顺序排除算法(MSEA)的改进

块匹配运动估计是视频编码国际标准中广泛采用的关键技术.许多快速块匹配法通过限制搜索点数来减少运算量,但与全搜索算法相比极易出现匹配误差.该文介绍了一种应用新的判别条件的多级顺序排除算法（MSEA）,并在此基础上提出一种新的算法,该算法引入了尺度化的部分失真消除（PDE）技术,用于尺度化累积部分误差和当前最小误差.实验证明,相对于一脉相承的同为穷举搜索算法的全搜索算法（FS）、顺序排除算法（SEA）、多级顺序排除算法（MSEA）等,该算法大幅度提高了搜索效率.与多级顺序排除算法相比,平均每宏块节省了大约75%的运算次数.该算法在保证图像质量的前提下,使视频编码的速度大大提高.     

A new fast heuristic for labeling points

In the point site labeling problem, we are given a set P={p₁,p₂,…,pn} of point sites in the plane. The label of a point pi is an axis-parallel rectangle of specified size. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. Here, we investigate a special class of the point site labeling problem where (i) height of the labels of all the points are same but their lengths may differ, (ii) the label of a point pi touches the point at one of its four corners, and (iii) the label of one point does not obscure any other point in P. We describe an efficient heuristic algorithm for this problem which runs in time in the worst case. We run our algorithm as well as the algorithm Rules proposed by Wagner et al. on randomly generated point sets and on the available benchmarks. The results produced by our algorithm are almost the same as Rules in most of the cases. But our algorithm is faster than Rules in dense instance. We have also computed the optimum solutions for all the examples we have considered by designing an algorithm, which performs an exhaustive search in the worst case. We found that the exhaustive search algorithm runs reasonably fast for most of the examples we have considered.     

A search algorithm for the minimum cost covering of 0–1 integer sets

This article presents an algorithm for the realization of the minimum cover on a 0–1 integer set with linear constraints. This is done through a search vector which, after each step along the gradient of the objective function, realigns itself on the polyhedra formed by the constraint hypersurfaces. The technique yields convergence to the solution point through fast and straightforward computations. Computational results are given to demonstrate the concepts involved.     

A technique for smoothing scattered data with conic sections

Piecewise rational quadratic curves are frequently used in many fields of computer science to represent curved shapes. For a large number of applications of computer aided design, the representation of data with a piecewise parametric curve that lies close to the data is an important consideration. This paper presents a geometric solution to the problem of automatically generating piecewise parametric rational quadratic polynomial approximations to shapes from sampled data. The algorithm takes a set of sample points, automatically generates tangents at some points and derives a piecewise rational quadratic curve that lies close to the data points. Combining this algorithm with the biquadratic search to subdivide the data if it cannot be represented with a single arc, we have a very stable algorithm that gives good results over a range of shapes and applications.     

文物点云模型的优化配准算法*

目的 针对带有噪声的文物点云模型,采用一种由粗到细的方法来实现其断裂面的精确配准。方法 首先采用一种变尺度点云配准算法实现粗配准,即配准测度函数的尺度参数由大到小逐渐变化,可避免算法陷入局部极值,并获得较高精度的初始配准结果。然后采用基于高斯概率模型的改进迭代最近点(iterative closest point, ICP)算法进行细配准,可以有效地抑制噪声对配准结果的影响,实现断裂面的快速精确匹配。结果 采用兵马俑文物碎块的配准结果表明,该优化配准算法能够实现文物断裂面的精确配准,而且在细配准阶段取得了较高的配准精度和收敛速度。结论 因此说,该优化配准算法是一种快速、精确、抗噪性强的文物点云配准方法。