Background There are many regularly shaped objects in artificial environments.It is difficult to distinguish the poses of these objects when only geometric information is used.With the development of sensor technologi...Background There are many regularly shaped objects in artificial environments.It is difficult to distinguish the poses of these objects when only geometric information is used.With the development of sensor technologies,inclusion of other information can be used to solve this problem.Methods We propose an algorithm to register point clouds by integrating color information.The key idea of the algorithm is to jointly optimize the dense and edge terms.The dense term was built in a manner similar to that of the iterative closest point algorithm.To build the edge term,we extracted the edges of the images obtained by projecting point clouds.The edge term prevents the point clouds from sliding during registration.We used this loosely coupled method to fuse geometric and color information.Results The results of the experiments showed that the edge image approach improves precision,and the algorithm is robust.展开更多
In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, thr...In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, three algorithms are presented for answering this kind of query. Among of them, two-phase Range＋Join and Join＋Range algorithms adopt the strategy that changes the execution order of range and closest pairs queries, and constrained heap-based algorithm utilizes extended distance functions to prune search space and minimize the pruning distance. Experimental results show that constrained heap-base algorithm has better applicability and performance than two-phase algorithms.展开更多
The iterative closest point(ICP)algorithm has the advantages of high accuracy and fast speed for point set registration,but it performs poorly when the point set has a large number of noisy outliers.To solve this prob...The iterative closest point(ICP)algorithm has the advantages of high accuracy and fast speed for point set registration,but it performs poorly when the point set has a large number of noisy outliers.To solve this problem,we propose a new affine registration algorithm based on correntropy which works well in the affine registration of point sets with outliers.Firstly,we substitute the traditional measure of least squares with a maximum correntropy criterion to build a new registration model,which can avoid the influence of outliers.To maximize the objective function,we then propose a robust affine ICP algorithm.At each iteration of this new algorithm,we set up the index mapping of two point sets according to the known transformation,and then compute the closed-form solution of the new transformation according to the known index mapping.Similar to the traditional ICP algorithm,our algorithm converges to a local maximum monotonously for any given initial value.Finally,the robustness and high efficiency of affine ICP algorithm based on correntropy are demonstrated by 2D and 3D point set registration experiments.展开更多
For localisation of unknown non-cooperative targets in space,the existence of interference points causes inaccuracy of pose estimation while utilizing point cloud registration.To address this issue,this paper proposes...For localisation of unknown non-cooperative targets in space,the existence of interference points causes inaccuracy of pose estimation while utilizing point cloud registration.To address this issue,this paper proposes a new iterative closest point(ICP)algorithm combined with distributed weights to intensify the dependability and robustness of the non-cooperative target localisation.As interference points in space have not yet been extensively studied,we classify them into two broad categories,far interference points and near interference points.For the former,the statistical outlier elimination algorithm is employed.For the latter,the Gaussian distributed weights,simultaneously valuing with the variation of the Euclidean distance from each point to the centroid,are commingled to the traditional ICP algorithm.In each iteration,the weight matrix W in connection with the overall localisation is obtained,and the singular value decomposition is adopted to accomplish high-precision estimation of the target pose.Finally,the experiments are implemented by shooting the satellite model and setting the position of interference points.The outcomes suggest that the proposed algorithm can effectively suppress interference points and enhance the accuracy of non-cooperative target pose estimation.When the interference point number reaches about 700,the average error of angle is superior to 0.88°.展开更多
The numbers of local complimentary inequivalent graph states for 9, 10 and 11 qubit systems are 440, 3132, 40457, respectively. We calculate the entanglement, the lower and upper bounds of the entanglement and obtain ...The numbers of local complimentary inequivalent graph states for 9, 10 and 11 qubit systems are 440, 3132, 40457, respectively. We calculate the entanglement, the lower and upper bounds of the entanglement and obtain the closest product states for all these graph states. New patterns of closest product states are analyzed.展开更多
THREE months after the operation that gave her an artificial trachea, Mi Aiyun was able to breathe normally, and fit enough to work in the fields for three to four hours. On July 26, 2002, Zhao Fengrui, designer of th...THREE months after the operation that gave her an artificial trachea, Mi Aiyun was able to breathe normally, and fit enough to work in the fields for three to four hours. On July 26, 2002, Zhao Fengrui, designer of the artificial trachea and main operating surgeon, announced that his was the world’s first tracheal prosthesis capable of integrating completely with the human trachea.Six years ago, Mi Aiyun, a 48-year-old展开更多
基于点云的空间非合作目标位姿估计,常受到噪声影响.提出截断最小二乘估计与半定松弛(truncated least squares estimation and semidefinite relaxation,TEASER)与迭代最近点(iterative closest point,ICP)的结合算法,提升空间非合作...基于点云的空间非合作目标位姿估计,常受到噪声影响.提出截断最小二乘估计与半定松弛(truncated least squares estimation and semidefinite relaxation,TEASER)与迭代最近点(iterative closest point,ICP)的结合算法,提升空间非合作目标位姿估计精度与鲁棒性.该方法包括粗配准与精配准两个环节:在粗配准环节中,基于局部点云与模型点云的方向直方图特征(signature of histogram of orientation,SHOT)确定匹配对,利用TEASER算法求解初始位姿;在精配准环节中,可结合ICP算法优化位姿估计结果.北斗卫星仿真实验表明:在连续帧位姿估计中,噪声标准差为3倍点云分辨率时,基于TEASER的周期关键帧配准方法的平移误差小于3.33 cm,旋转误差小于2.18°;与传统ICP方法相比,平均平移误差与平均旋转误差均有所降低.这表明所提出的空间非合作目标位姿估计方法具有良好的精度和鲁棒性.展开更多
As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euc...As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to （3n lg n）/2, which is only half that of SH algorithm.展开更多
We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle...We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.展开更多
3D quality inspection is widely applied in many industrial fields including mould design, automotive and blade manufacturing, etc. A commonly used method is to obtain the point cloud of the inspected object and make a...3D quality inspection is widely applied in many industrial fields including mould design, automotive and blade manufacturing, etc. A commonly used method is to obtain the point cloud of the inspected object and make a comparison between the point cloud and the corresponding CAD model or template. Thus, it is important to align the point cloud with the template first and foremost. Moreover, for the purpose of automatization of quality inspection, this alignment process is expected to be completed without manual interference. In this paper, we propose to combine the particle swarm optimization （PSO） with iterative closest point （ICP） algorithm to achieve the automated point cloud alignment. The combination of the two algorithms can achieve a balance between the alignment speed and accuracy, and avoid the local optimal caused by bad initial position of the point cloud.展开更多
We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points, within a given set of points in the XY-plane. For this version of the algorithm we show that only two pairwi...We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points, within a given set of points in the XY-plane. For this version of the algorithm we show that only two pairwise comparisons are required in the combine step, for each point that lies in the 25-wide vertical slab. The correctness of the algorithm is shown for all Minkowski distances with p ≥ 1. We also show empirically that, although the time complexity of the algorithm is still O（n lgn）, the reduction in the total number of comparisons leads to a significant reduction in the total execution time, for inputs with size sufficiently large.展开更多
文摘Background There are many regularly shaped objects in artificial environments.It is difficult to distinguish the poses of these objects when only geometric information is used.With the development of sensor technologies,inclusion of other information can be used to solve this problem.Methods We propose an algorithm to register point clouds by integrating color information.The key idea of the algorithm is to jointly optimize the dense and edge terms.The dense term was built in a manner similar to that of the iterative closest point algorithm.To build the edge term,we extracted the edges of the images obtained by projecting point clouds.The edge term prevents the point clouds from sliding during registration.We used this loosely coupled method to fuse geometric and color information.Results The results of the experiments showed that the edge image approach improves precision,and the algorithm is robust.
基金Supported by National Natural Science Foundationof China (60073045)
文摘In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, three algorithms are presented for answering this kind of query. Among of them, two-phase Range＋Join and Join＋Range algorithms adopt the strategy that changes the execution order of range and closest pairs queries, and constrained heap-based algorithm utilizes extended distance functions to prune search space and minimize the pruning distance. Experimental results show that constrained heap-base algorithm has better applicability and performance than two-phase algorithms.
基金supported in part by the National Natural Science Foundation of China(61627811,61573274,61673126,U1701261)
文摘The iterative closest point(ICP)algorithm has the advantages of high accuracy and fast speed for point set registration,but it performs poorly when the point set has a large number of noisy outliers.To solve this problem,we propose a new affine registration algorithm based on correntropy which works well in the affine registration of point sets with outliers.Firstly,we substitute the traditional measure of least squares with a maximum correntropy criterion to build a new registration model,which can avoid the influence of outliers.To maximize the objective function,we then propose a robust affine ICP algorithm.At each iteration of this new algorithm,we set up the index mapping of two point sets according to the known transformation,and then compute the closed-form solution of the new transformation according to the known index mapping.Similar to the traditional ICP algorithm,our algorithm converges to a local maximum monotonously for any given initial value.Finally,the robustness and high efficiency of affine ICP algorithm based on correntropy are demonstrated by 2D and 3D point set registration experiments.
基金supported by the National Natural Science Foundation of China(51875535)the Natural Science Foundation for Young Scientists of Shanxi Province(201901D211242201701D221017)。
文摘For localisation of unknown non-cooperative targets in space,the existence of interference points causes inaccuracy of pose estimation while utilizing point cloud registration.To address this issue,this paper proposes a new iterative closest point(ICP)algorithm combined with distributed weights to intensify the dependability and robustness of the non-cooperative target localisation.As interference points in space have not yet been extensively studied,we classify them into two broad categories,far interference points and near interference points.For the former,the statistical outlier elimination algorithm is employed.For the latter,the Gaussian distributed weights,simultaneously valuing with the variation of the Euclidean distance from each point to the centroid,are commingled to the traditional ICP algorithm.In each iteration,the weight matrix W in connection with the overall localisation is obtained,and the singular value decomposition is adopted to accomplish high-precision estimation of the target pose.Finally,the experiments are implemented by shooting the satellite model and setting the position of interference points.The outcomes suggest that the proposed algorithm can effectively suppress interference points and enhance the accuracy of non-cooperative target pose estimation.When the interference point number reaches about 700,the average error of angle is superior to 0.88°.
文摘The numbers of local complimentary inequivalent graph states for 9, 10 and 11 qubit systems are 440, 3132, 40457, respectively. We calculate the entanglement, the lower and upper bounds of the entanglement and obtain the closest product states for all these graph states. New patterns of closest product states are analyzed.
文摘THREE months after the operation that gave her an artificial trachea, Mi Aiyun was able to breathe normally, and fit enough to work in the fields for three to four hours. On July 26, 2002, Zhao Fengrui, designer of the artificial trachea and main operating surgeon, announced that his was the world’s first tracheal prosthesis capable of integrating completely with the human trachea.Six years ago, Mi Aiyun, a 48-year-old
文摘基于点云的空间非合作目标位姿估计,常受到噪声影响.提出截断最小二乘估计与半定松弛(truncated least squares estimation and semidefinite relaxation,TEASER)与迭代最近点(iterative closest point,ICP)的结合算法,提升空间非合作目标位姿估计精度与鲁棒性.该方法包括粗配准与精配准两个环节:在粗配准环节中,基于局部点云与模型点云的方向直方图特征(signature of histogram of orientation,SHOT)确定匹配对,利用TEASER算法求解初始位姿;在精配准环节中,可结合ICP算法优化位姿估计结果.北斗卫星仿真实验表明:在连续帧位姿估计中,噪声标准差为3倍点云分辨率时,基于TEASER的周期关键帧配准方法的平移误差小于3.33 cm,旋转误差小于2.18°;与传统ICP方法相比,平均平移误差与平均旋转误差均有所降低.这表明所提出的空间非合作目标位姿估计方法具有良好的精度和鲁棒性.
基金This work is supported by the National Natural Science Foundation of China （Grant No. 60496321） and Shanghai Science and Technology Development Fund （Grant No. 025115032）.
文摘As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to （3n lg n）/2, which is only half that of SH algorithm.
基金This work is partially supported by Utah State University under Grant No.A13501.
文摘We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.
文摘3D quality inspection is widely applied in many industrial fields including mould design, automotive and blade manufacturing, etc. A commonly used method is to obtain the point cloud of the inspected object and make a comparison between the point cloud and the corresponding CAD model or template. Thus, it is important to align the point cloud with the template first and foremost. Moreover, for the purpose of automatization of quality inspection, this alignment process is expected to be completed without manual interference. In this paper, we propose to combine the particle swarm optimization （PSO） with iterative closest point （ICP） algorithm to achieve the automated point cloud alignment. The combination of the two algorithms can achieve a balance between the alignment speed and accuracy, and avoid the local optimal caused by bad initial position of the point cloud.
文摘We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points, within a given set of points in the XY-plane. For this version of the algorithm we show that only two pairwise comparisons are required in the combine step, for each point that lies in the 25-wide vertical slab. The correctness of the algorithm is shown for all Minkowski distances with p ≥ 1. We also show empirically that, although the time complexity of the algorithm is still O（n lgn）, the reduction in the total number of comparisons leads to a significant reduction in the total execution time, for inputs with size sufficiently large.
