一种基于DDTW的三维碎片自动拼接方法_图文

1、 2期 高 剑等 : 一种基于 DD TW 的三维碎片自动拼接方法 347 算法 1 . 重叠检测算法 . Overlap ( 多边形 1 ,多边形 2 长越好 ,也就是说吻合部分内点的数量占整个碎片 点集的百分比要大 . 以上评价原则均可在线性时间内完成计算 . 综合上述各部分内容 , 最终得到两块碎片完整 的拼接算法 . 算法 2 . 拼接算法 . Match ( 碎片 1 ,碎片 2 任意选取一个多边形上的一个顶点 , 并与邻接的两 个顶点形成第一个三角片 ; while ( 仍存在度为 2 的顶点 以新选取的边为新三角片的一边 , 连接该边两端 点邻接的两新顶点形成两个新的三角片 ,

2、设新三 角片的三个角分别为, 则选取形状更接近正 三角形的一个作为选定的新三角片 , 选择的原则 就是使 E = (- 60 + (- 60 + (- 60 最小 2 2 2 提取两碎片边缘轮廓 C1 , C2 , 查找角点 , 因为碎片的 每个断面有两条轮廓线 , 所以划分得四组子轮廓线集 i 合 ( 因为碎片的每个断面有两条轮廓线 : C11 = C11 | i i = 1 , 2 , , m , C12 = C12 | i = 1 , 2 , , m , C21 = ( 图 6 中排除点划线所示选择方案 ; C21 | j = 1 , 2 , , n 和 C22 = C22 | j =

3、1 , 2 , , n ; j j 重复上述过程对另一个多边形进行三角化 ; 经过上述处理两个多边形分别被划分为两个三角片 集合 T1 , T2 ; for ( 所有属于 T1 的三角片 T ri1 do for ( 所有属于 T2 的三角片 T ri2 do 计算每条子轮廓线的挠率特征串 ; i i do fo r C1 的每条子轮廓线对 ( C11 , C12 i i do fo r C2 的每条子轮廓线 ( C21 , C22 i i i i , ( C21 存 在 DD TW 匹 配 if ( ( C11 , C12 , C22 match t hen i i 所属碎片进行 若有匹配存

4、在 , 则对 ( C21 , C22 i i 所属 放缩和刚体变换 , 将其对接到 ( C11 , C12 if ( T ri1 和 T ri2 重叠 t hen ret urn t rue ; ret urn False ; 碎片上 ; if (Overlap ( C1 , C2 = = FAL SE t hen / / 两碎片不重叠 实验表明 , 该算法能够将绝大多数重叠情况检 测出来 ,并且基本没有将无重叠的情况判断为重叠 . 同时该算法的执行不受轮廓曲线数据量的影响 , 可 在常数时间内完成 ,效率很高 . 4. 4 两块碎片拼接的完整算法 经过碎片尺寸的调整 、 空间位置方向的变换以

5、 及重叠检测的排除 , 两块碎片已经能够拼接到一起 了 ,但有时这种拼接仍然不能作为最终的拼接结果 . 我们还需要附加一些经验性原则才能得到更合理的 拼接结果 . 这些原则主要包含 : ( 1 误差评价 . 指的是碎片进行拼接之后对应 子轮廓线上的点应具有较小的距离误差 , 即点集间 的吻合度要高 , ( 2 局部变化度评价 . 两块碎片拼接处若具有 较大的曲折变化则更好 . 首先确定两碎片吻合部分 的所有点 ,对于每个点求其与相邻两顶点构成三角 形的面积 ,然后将所有这些面积求和得到近似曲折 能量 ,能量越大则越符合该评价标准 . 此评价标准能 够避免将那些平直的非断面拼接在一起 , 而是有

6、选 择地把一般化的弯曲断面拼接起来 . ( 3 公共部分长度评价 . 两块碎片公共部分越 将 match 加入到候选列表 matchList 中 ; 对 matchList 中记录的所有匹配按照评价标准排列 优劣次序 , 选择最好的作为最终结果返回 ; 5 总结与展望 多组实际数据的测试表明本文方法计算简单 , 鲁棒性强 ,可以在 ( m n 时间内找到两块碎片之间 合理和较为精确的匹配结果 . 这给以后的全局匹配 研究提供了有力的支持 . 图 7 展示的是几组使用本 文方法进行实际数据匹配的结果 . 今后的努力方向 就是以本文的工作为基础 , 继续研究并实现多碎片 全局最优自动拼接 . 随着

7、该技术的成熟 ,必将会给相 关行业提供极大的方便 . 348 计 算 机 学 报 2009 年 图7 实验结果 11 Horn B K P. Closed2form solution of absolute orientation using quaternions. Journal of Optical Societ y of America , 1987 , 4 (4 : 6292642 12 13 Rabiner L , J uang B. Fundamentals of Speech Recognition. Englewood Cliff s , NJ : Prentice Hall

8、 , 1993 Keogh E , Pazzani M. Scaling up dynamic time warping for datamining applications/ / Proceedings of t he 6t h ACM SI GK2 DD International Conference on Knowledge Discovery and Data Mining. Boston , 2000 14 Yi B , J agadish H , Falout so s C. Efficient ret rieval of similar time sequences unde

9、r time warping/ / Proceedings of t he In2 ternational Conference of Data Engineering. Orlando Florida , U SA , 1998 : 2012208 15 Berndt D , Clifford J . U sing dynamic time warping to find pat terns in time series/ / Proceedings of t he AAA I294 Work2 shop on Knowledge Discovery in Databases ( KDD 2

10、94 . Seat 2 tle , Washington , 1994 : 3592370 16 Gavrila D M , Davis L S. Towards 32D model2based t racking and recognition of human movement : A multi2view ap2 proach/ / Proceedings of t he International Workshop on Auto2 matic Face 2 and Gest ure 2Recognition. IEEE Co mp uter Soci2 et y , Zurich ,

11、 1995 : 2722277 17 Schmill M , Oates T , Co hen P. Learned models for continu2 ous planning/ / Proceedings of t he 7t h International Workshop on Artificial Intelligence and Statistics. Florida , U SA , 1999 : 2782282 18 Gollmer K , Po sten C. Detection of distorted pat tern using dynamic time warpi

12、ng algorit hm and application for supervi2 sion of bioprocesses. On2Line Fault Detection and Supervi2 sion in t he Chemical Process Indust ries , 1995 19 Caiani E G , Porta A , Baselli G , Turiel M , Muzzupappa S , Pieruzzi F , Crema C , Malliani A , Cerut ti S. Warped2average template technique to

13、t rack on a cycle 2by2cycle basis t he car2 diac filling p hases on left ventricular volume. IEEE Computers in Cardiology. N Y , USA , 1998 , 25 :73276 20 Keogh E J , Pazzani M J . Derivative dynamic time warping/ / Proceedings of t he 1st SIAM International Conference on Da2 ta Mining ( SDM 22001 .

14、 Chicago , IL , U SA , 2001 : 2092211 参 考 1 文 献 Martin K , Robert S. On 3D mosaicing of rotationally sym2 met ric ceramic f ragment s/ / Proceedings of t he 17t h Interna2 tional Conference on Pattern Recognition ( ICPR 04 . Cam2 bridge , United Kingdo m , 2004 , 2 : 2652268 2 Ucoluk G , Toro sluI H

15、. Automatic reconst ruction of broken 32D surface object s. Comp uters and Grap hics , 1999 , 23 (4 : 5732582 3 Kong W , Kimia B B. On solving 2D and 3D puzzles using curve matching/ / Proceedings of t he CV PR. Hawaii , U SA , 2001 : 5832590 4 Pan Rong2Jiang , Meng Xiang2Xu , Tu Chang2 He. Fragment

16、 re 2assembly based on L CS matching. Chinese Journal of Co mp uters , 2005 , 28 (3 : 3502356 (in Chinese ( 潘荣江 ,孟祥旭 ,屠长河 . 一种基于 L CS 的物体碎片自动拼 接算法 . 计算机学报 , 2005 , 28 (3 : 3502356 5 Mo khtarian F , Mackwort h A K. A t heory of multi scale , curvat ure 2based shape representation for planar curves. I

17、EEE Transactions on Patten Analysis and Machine Intelli2 gence , 1992 , 14 (8 : 7902805 6 Medina R , Wahle A , Olszewski M E , Sonka M. Curvat ure and torsion estimation for coronary artery motion analysis/ / Proceedings of Medical Imaging 2004 : Physiology , Function , and St ruct ure f ro m Medica

18、l Images. San Diego , CA , U SA , 2004 , 5369 : 5042515 7 Peng Jia2 Gui , Chen Qing. Differential Geomet ry. Beijing : Higher Education Press , 2002 (in Chinese ( 彭家贵 , 陈卿 . 微分几何 . 北京 : 高等教育出版社 , 2002 8 9 10 Ro senfeld A , Jo hnston E. Angle detection in digital curves. IEEE Transactions on Comp ute

19、r , 1993 , C 222 (9 : 8752878 Cormen T H , Leiserson C E , Rivest R L . Int roduction to Algorit hms. 2nd Edition. U SA : The MI T Press , 2001 Greenberg R L . Fast and simple co mp utation of all longest common subsequences. 2002 , 11 : 128 Co mp uter Science , DS/ 0211001 , 2期 高 剑等 : 一种基于 DD TW 的三

20、维碎片自动拼接方法 GAO Jian , born in 1977 , Ph. D. candidate. His research interest s include co mp uter grap hics , co mp utational ge2 omet ry and image p rocessing. visualization and medical image p rocessing. 349 MENG Xiang2 Xu , bo rn in 1962 , Ph. D. , p rofesso r and Ph. D. supervisor. His main resea

21、rch interest s include co m2 p uter software and t heory , human2comp uter interactio n & virt ual reality , comp uter grap hics , CIMS , CAD/ CAM. FENG Zhi2 Quan , bo rn in 1964 , Ph. D. , p rofessor. His research interest s include grap hics and image p rocessing , ZHANG Cai2Ming , bo rn in 19

22、55 , Ph. D. , p rofesso r , Ph. D. supervisor. His research interest s include co mp uter grap hics , co mp uter2aided geomet ry design , co mp utatio nal V R , human2comp uter interactio n and t racking moving 3D hand. Background This wo rk is supported by t he Natio nal Key Basic Re2 search 973 Program of China ( 2006CB303102 , t he National Nat ure Science Fo undation of China ( No s1 60673003 , 60633030 . In t his p roject , 3D object s are scanned into 3D point clo ud. Among t hese object s , lot s of t hem are f ragmen2 ted. If we assembly t hem by hand , it would take a long peri2 o