2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

图实现算法综述与评测分析

孙天元 王永才 李德英

孙天元, 王永才, 李德英. 图实现算法综述与评测分析. 自动化学报, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
引用本文: 孙天元, 王永才, 李德英. 图实现算法综述与评测分析. 自动化学报, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
SUN Tian-Yuan, WANG Yong-Cai, LI De-Ying. A Survey and Evaluation of Graph Realization Algorithms. ACTA AUTOMATICA SINICA, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
Citation: SUN Tian-Yuan, WANG Yong-Cai, LI De-Ying. A Survey and Evaluation of Graph Realization Algorithms. ACTA AUTOMATICA SINICA, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561

图实现算法综述与评测分析

doi: 10.16383/j.aas.2018.c170561
基金项目: 

国家自然科学基金面上项目 11671400

国家自然科学基金面上项目 61672524

国家自然科学基金面上项目 61972404

详细信息
    作者简介:

    孙天元  中国人民大学信息学院硕士研究生. 2015年获得中国人民大学信息学院学士学位.主要研究方向为图实现与虚拟现实. E-mail: suntyruc@163.com

    李德英  中国人民大学信息学院计算机科学与技术系教授. 1988年获得华中师范大学数学学士学位, 2004年获得香港城市大学计算机博士学位.主要研究方向为线传感器网络, 社会网络, 算法分析与设计. E-mail: deyingli@ruc.edu.cn

    通讯作者:

    王永才  中国人民大学计算机系副教授. 2001年获得清华大学自动化系学习学位, 2006年获得清华大学自动化系博士学位.主要研究方向为物联网, 机器人, 大数据挖掘与分析, 算法设计与分析.本文通信作者. E-mail: ycw@ruc.edu.cn

  • 本文责任编委 段书凯

A Survey and Evaluation of Graph Realization Algorithms

Funds: 

National Natural Science Foundation of China 11671400

National Natural Science Foundation of China 61672524

National Natural Science Foundation of China 61972404

More Information
    Author Bio:

    SUN Tian-Yuan   Master student in the Department of Computer Sciences, Renmin University of China. He received his bachelor degree from the Department of Computer Sciences, Renmin University of China in 2015. His research interest covers graph realization and VR

    LI De-Ying   Professor in the Department of Computer Science, Renmin University of China. She received her master degree in mathematics from Huazhong Normal University in 1988 and Ph.D. degree in computer science from City University of Hong Kong, China in 2004. Her research interest covers wireless networks, mobile computin, algorithm design and analysis

    Corresponding author: WANG Yong-Cai   Associate professor in the Department of Computer Sciences, Renmin University of China. He received his bachelor and Ph.D. degrees from Department of Automation Sciences and Engineering, Tsinghua University in 2001 and 2006, respectively. His research interest covers network localization algorithms, simultaneously locating and mapping algorithms, combinatorial optimization and applications. Corresponding author of this paper
  • Recommended by Associate Editor DUAN Shu-Kai
  • 摘要: 图实现(Graph realization)问题研究基于节点间全部或部分距离关系测量, 在$d$维空间中计算图的顶点坐标, 使得在所实现图中各节点之间实现距离与测量距离尽可能一致.图实现问题是一个典型的优化问题, 在传感器网络定位、蛋白质结构重建、数据可视化、社交网络分析、机器人同步定位与构图等领域有着广泛应用.图实现的研究同图刚性理论有着紧密的联系, 图的刚性与全局刚性决定图的可实现性.在可实现图中, 现有工作提出几类典型的代表性图实现算法, 包括: 1)基于三边测距类方法; 2)求解距离方程类方法; 3)基于全局优化类方法; 4)基于模块拼合类方法.本文对图实现的刚性理论, 四类图实现算法的设计思想、适用条件、算法流程等进行综述分析, 通过实验对算法进行准确性、计算复杂度、可靠性等方面的比较和分析.
    Recommended by Associate Editor DUAN Shu-Kai
    1)  本文责任编委 段书凯
  • 图  1  SMACOF算法示意图

    Fig.  1  The diagram of SMACOF

    图  2  模块拼合示意图

    Fig.  2  The diagram of module embedding

    图  3  定位误差统计图

    Fig.  3  Location error statistics

    ε $\sim$ N(0,52); degreeave = 10

    图  4  定位误差统计图

    Fig.  4  Location error statistics

    ε $\sim$ N(0,102); degreeave = 10

    图  5  定位误差统计图

    Fig.  5  Location error statistics

    ε $\sim$ N(0,52); degreeave = 8

    6a  稠密度比较拓扑图

    6a  Dense comparison topology

    6b  稠密度比较拓扑图

    6b  Dense comparison topology

    图  7  运行时间统计图

    Fig.  7  Time statistics

    图  8  平均误差统计图

    Fig.  8  Average error statistics

    $degree_{ave}=6$

    图  9  平均误差统计图

    Fig.  9  Average error statistics

    $degree_{ave}=8$

    图  10  平均误差统计图

    Fig.  10  Average error statistics

    $degree_{ave}=10$

    图  11  平均误差统计图

    Fig.  11  Average error statistics

    $degree_{ave}=12$

    表  1  算法分类表

    Table  1  Algorithm classification

    方法类型 算法 算法特点
    三边测量类方法 Trilateration 基于几何性质, 增量式求解结果
    距离方程类方法 MDS 求解完全图的实现方法
    SDP 以半正定规划求解问题
    全局优化类方法 $g^2o$ 基于最小二乘法的迭代搜索方法
    SMACOF 基于构造辅助函数的迭代搜索方法
    模块拼合类方法 AAAP 将部分模块变形, 以仿射变换拼合模块
    ARAP 以迭代搜索的策略, 优化拼合后结果的形状偏差
    ASAP 以矩阵特征向量求解模块拼合结果
    下载: 导出CSV

    表  2  计算符号说明表

    Table  2  Notation list

    符号 定义
    $n$ 节点数量, $|V|=n$
    $m$ 图中边的数量, $|E|=m$
    $t$ 迭代次数
    $g $ 节点最大度数
    $N $ 模块中节点数最大值
    下载: 导出CSV

    表  3  算法时间复杂度

    Table  3  Time complexity of different algorithms

    算法名称 时间复杂度
    Trilateration ${\rm O}(n^2)$
    MDS ${\rm O}(n^2)$
    SDP ${\rm O}(n^2m^{2.5}+m^{3.5})$
    $g^2o$ ${\rm O}(n^2t)$
    SMACOF ${\rm O}(n^2t)$
    AAAP ${\rm O}(mn^2)$
    ARAP ${\rm O}(mn^2+n^3t)$
    ASAP ${\rm O}(nN^2t+mn^2)$
    下载: 导出CSV

    表  4  算法比较表

    Table  4  Algorithm comparison

    方法类型 算法 准确性 计算效率 鲁棒性(稠密度) 鲁棒性(噪声)
    三边测量类方法 Trilateration $\bigstar$ $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar \bigstar$
    距离方程类方法 MDS $\bigstar \bigstar$ $\bigstar \bigstar \bigstar$ $\bigstar$ $\bigstar \bigstar$
    SDP $\bigstar \bigstar$ $\bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar \bigstar \bigstar$
    全局优化类方法 $g^2o$ $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$
    SMACOF $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$
    模块拼合类方法 AAAP $\bigstar$ $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar$
    ARAP $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar \bigstar$
    ASAP $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar$ $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$
    下载: 导出CSV
  • [1] Bulusu N, Heidemann J, Estrin D. GPS-less low-cost outdoor localization for very small devices. IEEE Personal Communications, 2000, 7(5): 28-34 doi: 10.1109/98.878533
    [2] Doherty L, Pister K S J, El Ghaoui L. Convex position estimation in wireless sensor networks. In: IEEE INFOCOM, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Anchorage, United States: IEEE, 2001. 1655-1663 https://www.researchgate.net/publication/3893900_Convex_position_estimation_in_wireless_sensor_networks
    [3] Hightower J, Borriello G. Location systems for ubiquitous computing. Computer, 2001, 34(8): 57-66 doi: 10.1109/2.940014
    [4] Savvides A, Han C C, Strivastava M B. Dynamic fine-grained localization in Ad-Hoc networks of sensors. In: Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. Rome, Italy: ACM, 2001. 166-179 https://www.researchgate.net/publication/220926176_Srivastava_Dynamic_Fine-grained_Localization_in_Ad-Hoc_Networks_of_Sensors
    [5] Savarese C, Rabaey J M, Langendoen K. Robust positioning algorithms for distributed Ad-Hoc wireless sensor networks. In: Proceedings of the General Track of the Annual Conference on USENIX Annual Technical Conference. Monterey, USA: USENIX Association, 2002. 317-327 https://www.researchgate.net/publication/2529202_Robust_Positioning_Algorithms_for_Distributed_Ad-Hoc_Wireless_Sensor_Networks
    [6] Hays P A. Proton nuclear magnetic resonance spectroscopy (NMR) methods for determining the purity of reference drug standards and illicit forensic drug seizures. Journal of Forensic Sciences, 2005, 50(6): 1342-1360 http://cn.bing.com/academic/profile?id=3517aaf1c734242ab4ed9eeb65736e5c&encoded=0&v=paper_preview&mkt=zh-cn
    [7] Kaufmann K W, Lemmon G H, DeLuca S L, Sheehan J H, Meiler J. Practically useful: what the Rosetta protein modeling suite can do for you. Biochemistry, 2010, 49(14): 2987-2998 doi: 10.1021/bi902153g
    [8] Sit A, Wu Z J, Yuan Y X. A geometric buildup algorithm for the solution of the distance geometry problem using least-squares approximation. Bulletin of Mathematical Biology, 2009, 71(8): 1914-1933 doi: 10.1007/s11538-009-9431-9
    [9] Sit A, Wu Z J. Solving a generalized distance geometry problem for protein structure determination. Bulletin of Mathematical Biology, 2011, 73(12): 2809-2836 doi: 10.1007/s11538-011-9644-6
    [10] 刘勘, 周晓峥, 周洞汝.数据可视化的研究与发展.计算机工程, 2002, 28(8): 1-2, 63 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjgc200208001

    Liu Kan, Zhou Xiao-Zheng, Zhou Dong-Ru. Data visualization research and development. Computer Engineering, 2002, 28(8): 1-2, 63 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjgc200208001
    [11] Wilkinson L. SYSTAT: the System for Statistics. Evanston, IL: SYSTAT, Inc., 1986.
    [12] Kümmerle R, Grisetti G, Strasdat H, Konolige K, Burgard W. $G.2o$: a general framework for graph optimization. In: IEEE International Conference on Robotics and Automation. Shanghai, China: IEEE, 2011. 3607-3613
    [13] Li Z, Trappe W, Zhang Y, Nath B. Robust statistical methods for securing wireless localization in sensor networks. In: Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. Boise, USA: IEEE, 2005. 91-98 https://www.researchgate.net/publication/4149846_Robust_statistical_methods_for_securing_wireless_localization_in_sensor_networks
    [14] Saxe J B. Embeddability of Weighted Graphs in K-Space is Strongly NP-Hard. Qatar: Carnegie-Mellon University, 1980.
    [15] Yemini Y. Some theoretical aspects of position-location problems. In: Proceedings of the 20th Annual Symposium on Foundations of Computer Science. Washington D. C., USA: IEEE, 1979. 1-8 http://www.sciencedirect.com/science/article/pii/001457938680151X
    [16] Jackson B, Jordán T. Connected rigidity matroids and unique realizations of graphs. Journal of Combinatorial Theory, Series B, 2005, 94(1): 1-29 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=593b97de641132c7f040a84dc72841fa
    [17] Thomas F, Ros L. Revisiting trilateration for robot localization. IEEE Transactions on Robotics, 2005, 21(1): 93-101 doi: 10.1109/TRO.2004.833793
    [18] Čapkun S, Buttyán L, Hubaux J P. SECTOR: secure tracking of node encounters in multi-hop wireless networks. In: Proceedings of the 1st ACM Workshop on Security of Ad Hoc and Sensor Networks. Fairfax, Virginia: ACM, 2003. 21-32 https://www.researchgate.net/publication/37402492_SECTOR_Secure_Tracking_of_Node_Encounters_in_Multi-hop_Wireless_Networks
    [19] Lazos L, Poovendran R. SeRLoc: secure range-independent localization for wireless sensor networks. In: Proceedings of the 3rd ACM Workshop on Wireless Security. Philadelphia, PA, USA: ACM, 2004. 21-30 https://www.researchgate.net/publication/221005650_SeRLoc_Secure_Range-Independent_Localization_for_Wireless_Sensor_Networks
    [20] Kusy B, Ledeczi A, Maroti M, Meertens L. Node-density independent localization. In: Proceedings of the 5th International Conference on Information Processing in Sensor Networks. Nashville, USA: IEEE, 2006. 441-448 https://www.researchgate.net/publication/224642430_Node-density_independent_localization
    [21] Hendrickson B. The molecule problem: exploiting structure in global optimization. Siam Journal on Optimization, 1995, 5(4): 835-857 doi: 10.1137/0805040
    [22] Shang Y, Ruml W, Zhang Y, Fromherz M P J. Localization from mere connectivity. In: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. Annapolis, Maryland, USA: ACM, 2003. 201-212 https://www.researchgate.net/publication/2892241_Localization_from_Mere_Connectivity
    [23] Shang Y, Ruml W. Improved MDS-based localization. In: EEE INFOCOM 2004. Hong Kong, China: IEEE, 2004. 2640-2651 https://www.researchgate.net/publication/4102894_Improved_MDS-based_localization
    [24] Shang Y, Ruml W, Zhang Y, Fromherz M. Localization from connectivity in sensor networks. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(11): 961-974 doi: 10.1109/TPDS.2004.67
    [25] Biswas P, Lian T C, Wang T C, Ye Y Y. Semidefinite programming based algorithms for sensor network localization. ACM Transactions on Sensor Networks, 2006, 2(2): 188-220 doi: 10.1145/1149283.1149286
    [26] Biswas P, Aghajan H, Ye Y Y. Semidefinite programming algorithms for sensor network localization using angle information. In: Proceedings of the Conference Record of the Thirty-Ninth Asilomar Conference on Signals, Systems and Computers. Pacific Grove, CA, USA: IEEE, 2005. 220-224 http://www.researchgate.net/publication/4225543_Semidefinite_Programming_Algorithms_for_Sensor_Network_Localization_using_Angle_Information
    [27] Biswas P, Liang T C, Toh K C, Ye Y, Wang T C. Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE Transactions on Automation Science and Engineering, 2006, 3(4): 360-371 doi: 10.1109/TASE.2006.877401
    [28] Zhu Z S, So A M C, Ye Y Y. Universal rigidity: towards accurate and efficient localization of wireless networks. In: Proceedings IEEE INFOCOM. San Diego, USA: IEEE, 2010. 1-9
    [29] Boyd S, El Ghaoui L, Feron E, Balakrishnan V. Linear Matrix Inequalities in System and Control Theory. Philadelphia: Society for Industrial and Applied Mathematics, 1994. http://library.wur.nl/WebQuery/clc/1669445
    [30] Liang T C, Wang T C, Ye Y Y. A Gradient Search Method to Round the Semidefinite Programming Relaxation Solution for Ad Hoc Wireless Sensor Network Localization, Technical Report, Department of Management Science and Engineering, Stanford University, 2004.
    [31] Cox T F, Cox M A A. Multidimensional Scaling (Second Edition). London: Chapman Hall/CRC, 2000.
    [32] Savvides A, Park H, Srivastava M B. The bits and flops of the n-hop multilateration primitive for node localization problems. In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta, USA: ACM, 2002. 112-121
    [33] Costa J A, Patwari N, Hero A O Ⅲ. Distributed weighted-multidimensional scaling for node localization in sensor networks. ACM Transactions on Sensor Networks, 2006, 2(1): 39-64 http://d.old.wanfangdata.com.cn/OAPaper/oai_doaj-articles_1757e346002855db37f97718c6d6e3b1
    [34] Groenen P J F. The Majorization Approach to Multidimensional Scaling: Some Problems and Extensions[Ph.D. dissertation], Leiden University, Leiden, The Netherlands, 1993 https://www.researchgate.net/publication/243785955_The_majorization_approach_to_multidimensional_scaling_some_problems_and_extensions
    [35] Press W H, Teukolsky S A, Vetterling W T, Flannery B P. Numerical Recipes (Second Edition). Cambridge: Cambridge University Press, 1992.
    [36] Lourakis M I A, Argyros A A. SBA: a software package for generic sparse bundle adjustment. ACM Transactions on Mathematical Software, 2009, 36(1): Article No. 2 http://d.old.wanfangdata.com.cn/Periodical/wjclxb200304024
    [37] Endres F, Hess J, Engelhard N, Sturm J, Cremers D, Burgard W. An evaluation of the RGB-D SLAM system. In: Proceedings of the 2012 IEEE International Conference on Robotics and Automation. Saint Paul, MN, USA: IEEE, 2012. 1691-1696 https://www.researchgate.net/publication/254041427_An_evaluation_of_the_RGB-D_SLAM_system
    [38] Sturm J, Engelhard N, Endres F, Burgard W, Cremers D. A benchmark for the evaluation of RGB-D SLAM systems. In: IEEE/RSJ International Conference on Intelligent Robots and Systems. Vilamoura, Portugal: IEEE, 2012. 573-580 https://www.researchgate.net/publication/261353760_A_benchmark_for_the_evaluation_of_RGB-D_SLAM_systems?ev=auth_pub
    [39] Engel J, Schōps T, Cremers D. LSD-SLAM: large-scale direct monocular SLAM. In: European Conference on Computer Vision. Zurich, Switzerland: Springer, 2014. 834-849 http://www.researchgate.net/publication/290620817_LSD-SLAM_Large-Scale_Direct_Monocular_SLAM
    [40] Forster C, Pizzoli M, Scaramuzza D. SVO: fast semi-direct monocular visual odometry. In: Proceedings of the 2014 IEEE International Conference on Robotics and Automation. Hong Kong, China: IEEE, 2014. 15-22 https://www.researchgate.net/publication/262378002_SVO_Fast_Semi-Direct_Monocular_Visual_Odometry
    [41] Fraundorfer F, Heng L, Honegger D, Lee G H, Meier L, Tanskanen P, et al. Vision-based autonomous mapping and exploration using a quadrotor MAV. In: Proceedings of the 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. Vilamoura, Portugal: IEEE, 2012. 4557-4564 http://www.researchgate.net/publication/261353707_Vision-based_autonomous_mapping_and_exploration_using_a_quadrotor_MAV
    [42] De Leeuw J. Applications of convex analysis to multidimensional scaling. Department of Statistics, UCLA, 2005. http://www.researchgate.net/publication/239417876_APPLICATIONS_OF_CONVEX_ANALYSIS_TO_MULTIDIMENSIONAL_SCALING
    [43] Borg I, Groenen P J F. Modern Multidimensional Scaling: Theory and Applications (Second Edition). New York, NY: Springer, 2005.
    [44] Moore D C. Robust distribution sensor network localization with noisy range measurements. Massachusetts Institute of Technology, 2005. 50-61 https://www.researchgate.net/publication/35943813_Robust_distribution_sensor_network_localization_with_noisy_range_measurements
    [45] Koren Y, Gotsman C, Ben-Chen M. PATCHWORK: efficient localization for sensor networks by distributed global optimization. Technical Report, 2005. https://www.researchgate.net/publication/254039773_PATCHWORK_Efficient_Localization_for_Sensor_Networks_by_Distributed_Global_Optimization
    [46] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000, 290(5500): 2323-2326 doi: 10.1126/science.290.5500.2323
    [47] Shi J B, Malik J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905 doi: 10.1109/34.868688
    [48] Zhang L, Liu L G, Gotsman C, Gortler S J. An as-rigid-as-possible approach to sensor network localization. ACM Transactions on Sensor Networks, 2010, 6(4): Article No. 35 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=fa857a82ca6af6ecf09b9cba6458a2e5
    [49] Sorkine O, Alexa M. As-rigid-as-possible surface modeling. In: Proceedings of the 5th Eurographics Symposium on Geometry Processing. Barcelona, Spain, 2007. 109-116 https://www.researchgate.net/publication/221316589_As-Rigid-As-Possible_Surface_Modeling
    [50] Alexa M, Cohen-Or D, Levin D. As-rigid-as-possible shape interpolation. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New Orleans, USA: ACM, 2000. 157-164 https://www.researchgate.net/publication/2538876_As-Rigid-As-Possible_Shape_Interpolation
    [51] Press W H, Teukolsky S A, Vetterling W T, Flannery B P. Numerical Recipes: The Art of Scientific Computing (3rd Edition). Cambridge: Cambridge University Press, 2007.
    [52] Cornilescu G, Marquardt J L, Ottiger M, Bax A. Validation of protein structure from anisotropic carbonyl chemical shifts in a dilute liquid crystalline phase. Journal of the American Chemical Society, 1998, 120(27): 6836-6837 doi: 10.1021/ja9812610
    [53] Hendrickson B. Conditions for unique graph realizations. SIAM Journal on Computing, 1992, 21(1): 65-84 doi: 10.1137/0221008
    [54] Gower J C, Dijksterhuis G B. Procrustes Problems. Oxford: Oxford University Press, 2004.
    [55] Golub G H, Van Loan C F. Matrix Computations (4th Edition). Baltimore, MD: Johns Hopkins University Press, 2012.
    [56] Gortler S J, Healy A D, Thurston D P. Characterizing generic global rigidity. American Journal of Mathematics, 2010, 132(4): 897-939 doi: 10.1353/ajm.0.0132
    [57] Cucuringu M, Lipman Y, Singer A. Sensor network localization by eigenvector synchronization over the euclidean group. ACM Transactions on Sensor Networks, 2012, 8(3): Article No. 19 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=51a43c69302e35adee96e330ee6450b8
    [58] Sobeih A, Hack M, Liu Z, Zhang L. Almost peer-to-peer clock synchronization. In: Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium. Rome: IEEE, 2007. 1-10 https://www.researchgate.net/publication/220951841_Almost_Peer-to-Peer_Clock_Synchronization?ev=prf_cit
    [59] Mainwaring A, Culler D, Polastre J, Szewczyk R, Anderson J. Wireless sensor networks for habitat monitoring. In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta, USA: ACM, 2002. 88-97
    [60] Brust M R, Akbaș M I, Turgut D. Multi-hop localization system for environmental monitoring in wireless sensor and actor networks. Concurrency and Computation: Practice and Experience, 2013, 25(5): 701-717 doi: 10.1002/cpe.1812
    [61] Wang X P, Liu Y H, Yang Z, Lu K, Luo J. Robust component-based localizationin sparse networks. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(5): 1317-1327 doi: 10.1109/TPDS.2013.85
    [62] Korniienko A, Khan U A, Scorletti G. Robust sensor localization with locally-computed, global $H_\infty$-design. In: Proceedings of the 2016 American Control Conference. Boston, USA: IEEE, 2016. 6375-6380
    [63] Khan U A, Kar S, Moura J M F. DILAND: an algorithm for distributed sensor localization with noisy distance measurements. IEEE Transactions on Signal Processing, 2010, 58(3): 1940-1947 doi: 10.1109/TSP.2009.2038423
    [64] Lin Z Y, Fu M Y, Diao Y F. Distributed self localization for relative position sensing networks in 2D space. IEEE Transactions on Signal Processing, 2015, 63(14): 3751-3761 doi: 10.1109/TSP.2015.2432739
    [65] Hubbell W L, Cafiso D S, Altenbach C. Identifying conformational changes with site-directed spin labeling. Nature Structural and Molecular Biology, 2000, 7(9): 735-739 doi: 10.1038/78956
    [66] Oh K J, Altenbach C, Collier R J, Hubbell W L. Site-directed spin labeling of proteins. Bacterial Toxins: Methods and Protocols. New York: Humana Press, 2000. 147-169
    [67] Dong Q F, Wu Z J. A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances. Journal of Global Optimization, 2002, 22(1-4): 365-375 https://www.researchgate.net/publication/227120408_A_linear-time_algorithm_for_solving_the_molecular_distance_geometry_problem_with_exact_inter-atomic_distances
    [68] Wu D, Wu Z J. An updated geometric build-up algorithm for solving the molecular distance geometry problems with sparse distance data. Journal of Global Optimization, 2007, 37(4): 661-673 doi: 10.1007/s10898-006-9080-6
    [69] Lavor C, Liberti L, Donald B, Worley B, Bardiaux B, Malliavin T E, Nilges M. Minimal NMR distance information for rigidity of protein graphs. Discrete Applied Mathematics, 2019, 256: 91-104 doi: 10.1016/j.dam.2018.03.071
    [70] Blumenthal L M. Theory and Applications of Distance Geometry. Oxford: Clarendon Press, 1953.
    [71] Moré J J, Wu Z J. Distance geometry optimization for protein structures. Journal of Global Optimization, 1999, 15(3): 219-234 doi: 10.1023/A:1008380219900
    [72] Cleveland W S, McGill M E. Dynamic Graphics for Statistics. Belmont, California: Wadsworth, 1988.
    [73] Littlefield R J. Using the glyph concept to create user-definable display formats. Pacific Northwest Lab, Richland, USA, 1983.
    [74] 柳萌萌, 赵书良, 韩玉辉, 苏东海, 李晓超, 陈敏.多尺度数据挖掘方法.软件学报, 2016, 27(12): 3030-3050 http://d.old.wanfangdata.com.cn/Periodical/jsjkx201904009

    Liu Meng-Meng, Zhao Shu-Liang, Han Yu-Hui, Su Dong-Hai, Li Xiao-Chao, Chen Min. Research on multi-scale data mining method. Journal of Software, 2016, 27(12): 3030-3050 http://d.old.wanfangdata.com.cn/Periodical/jsjkx201904009
    [75] Levy S. A cross-cultural analysis of the structure and levels of attitudes towards acts of political protest. Social Indicators Research, 1983, 12(3): 281-309 doi: 10.1007/BF00319806
    [76] Castellanos J A, Montiel J M M, Neira J, Tardos J D. The SPmap: a probabilistic framework for simultaneous localization and map building. IEEE Transactions on Robotics and Automation, 1999, 15(5): 948-952 doi: 10.1109/70.795798
    [77] Paz L M, Tardos J D, Neira J. Divide and conquer: EKF SLAM in O($n$). IEEE Transactions on Robotics, 2008, 24(5): 1107-1120 doi: 10.1109/TRO.2008.2004639
    [78] Montemerlo M, Thrun S, Koller D, Wegbreit B. FastSLAM: a factored solution to the simultaneous localization and mapping problem. In: Proceedings of the AAAI National Conference on Artificial Intelligence. San Francisco: AAAI, 2002. 593-598
    [79] Hahnel D, Burgard W, Fox D, Thrun S. An efficient fastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements. In: IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas, USA: IEEE, 2003. 206-211
    [80] Eustice R M, Singh H, Leonard J J. Exactly sparse delayed-state filters. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation. Barcelona, Spain: IEEE, 2005. 2417-2424 https://www.researchgate.net/publication/221077974_Exactly_Sparse_Delayed-State_Filters
    [81] Thrun S, Liu Y F, Koller D, Ng A Y, Ghahramani Z, Durrant-Whyte H. Simultaneous localization and mapping with sparse extended information filters. International Journal of Robotics Research, 2004, 23(7-8): 693-716 doi: 10.1177/0278364904045479
    [82] Grisetti G, Kummerle R, Stachniss C, Burgard W. A tutorial on graph-based SLAM. IEEE Intelligent Transportation Systems Magazine, 2010, 2(4): 31-43 doi: 10.1109/MITS.2010.939925
    [83] Saez J M, Hogue A, Escolano F, Jenkin M. Underwater 3D SLAM through entropy minimization. In: Proceedings of the 2006 IEEE International Conference on Robotics and Automation. Orlando, USA: IEEE, 2006. 3562-3567 http://www.researchgate.net/publication/221069355_Underwater_3D_SLAM_through_Entropy_Minimization
    [84] Kümmerle R, Steder B, Dornhege C, Kleiner A, Grisetti G, Burgard W. Large scale graph-based SLAM using aerial images as prior information. Autonomous Robots, 2011, 30(1): 25-39 doi: 10.1007/s10514-010-9204-1
    [85] 张毅, 汪龙峰, 余佳航.基于深度信息的移动机器人室内环境三维地图创建.计算机应用, 2014, 34(12): 3438-3440 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjyy201412015

    Zhang Yi, Wang Long-Feng, Yu Jia-Hang. Depth-image based 3D map reconstruction of indoor environment for mobile robots. Journal of Computer Applications, 2014, 34(12): 3438-3440 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjyy201412015
    [86] Levi Z, Gotsman C. Smooth rotation enhanced As-Rigid-As-Possible mesh animation. IEEE Transactions on Visualization and Computer Graphics, 2015, 21(2): 264-277 doi: 10.1109/TVCG.2014.2359463
    [87] Parashar S, Pizarro D, Bartoli A, Collins T. As-rigid-as-possible volumetric shape-from-template. In: Proceedings of the 2015 IEEE International Conference on Computer Vision. Santiago, Chile: IEEE, 2015. 891-899 https://www.researchgate.net/publication/300408305_As-Rigid-as-Possible_Volumetric_Shape-from-Template?ev=auth_pub
    [88] Jacobs D J, Hendrickson B. An algorithm for two-dimensional rigidity percolation: the pebble game. Journal of Computational Physics, 1997, 137(2): 346-365 doi: 10.1006/jcph.1997.5809
    [89] Connelly R. Generic global rigidity. Discrete & Computational Geometry, 2005, 33(4): 549-563 http://www.researchgate.net/profile/R_Connelly/publication/220453469_Generic_Global_Rigidity/links/5447b0890cf2f14fb8121c28?ev=pub_ext_doc_dl_meta
  • 加载中
图(12) / 表(4)
计量
  • 文章访问数:  1931
  • HTML全文浏览量:  1160
  • PDF下载量:  640
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-10-21
  • 录用日期:  2018-07-15
  • 刊出日期:  2020-04-24

目录

    /

    返回文章
    返回