1、 2期 高 劍等 : 一種基于 DD TW 的三維碎片自動(dòng)拼接方法 347 算法 1 . 重疊檢測算法 . Overlap ( 多邊形 1 ,多邊形 2 長越好 ,也就是說吻合部分內(nèi)點(diǎn)的數(shù)量占整個(gè)碎片 點(diǎn)集的百分比要大 . 以上評(píng)價(jià)原則均可在線性時(shí)間內(nèi)完成計(jì)算 . 綜合上述各部分內(nèi)容 , 最終得到兩塊碎片完整 的拼接算法 . 算法 2 . 拼接算法 . Match ( 碎片 1 ,碎片 2 任意選取一個(gè)多邊形上的一個(gè)頂點(diǎn) , 并與鄰接的兩 個(gè)頂點(diǎn)形成第一個(gè)三角片 ; while ( 仍存在度為 2 的頂點(diǎn) 以新選取的邊為新三角片的一邊 , 連接該邊兩端 點(diǎn)鄰接的兩新頂點(diǎn)形成兩個(gè)新的三角片 ,

2、設(shè)新三 角片的三個(gè)角分別為, 則選取形狀更接近正 三角形的一個(gè)作為選定的新三角片 , 選擇的原則 就是使 E = (- 60 + (- 60 + (- 60 最小 2 2 2 提取兩碎片邊緣輪廓 C1 , C2 , 查找角點(diǎn) , 因?yàn)樗槠?每個(gè)斷面有兩條輪廓線 , 所以劃分得四組子輪廓線集 i 合 ( 因?yàn)樗槠拿總€(gè)斷面有兩條輪廓線 : C11 = C11 | i i = 1 , 2 , , m , C12 = C12 | i = 1 , 2 , , m , C21 = ( 圖 6 中排除點(diǎn)劃線所示選擇方案 ; C21 | j = 1 , 2 , , n 和 C22 = C22 | j =

3、1 , 2 , , n ; j j 重復(fù)上述過程對(duì)另一個(gè)多邊形進(jìn)行三角化 ; 經(jīng)過上述處理兩個(gè)多邊形分別被劃分為兩個(gè)三角片 集合 T1 , T2 ; for ( 所有屬于 T1 的三角片 T ri1 do for ( 所有屬于 T2 的三角片 T ri2 do 計(jì)算每條子輪廓線的撓率特征串 ; i i do fo r C1 的每條子輪廓線對(duì) ( 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 所屬碎片進(jìn)行 若有匹配存

4、在 , 則對(duì) ( C21 , C22 i i 所屬 放縮和剛體變換 , 將其對(duì)接到 ( C11 , C12 if ( T ri1 和 T ri2 重疊 t hen ret urn t rue ; ret urn False ; 碎片上 ; if (Overlap ( C1 , C2 = = FAL SE t hen / / 兩碎片不重疊 實(shí)驗(yàn)表明 , 該算法能夠?qū)⒔^大多數(shù)重疊情況檢 測出來 ,并且基本沒有將無重疊的情況判斷為重疊 . 同時(shí)該算法的執(zhí)行不受輪廓曲線數(shù)據(jù)量的影響 , 可 在常數(shù)時(shí)間內(nèi)完成 ,效率很高 . 4. 4 兩塊碎片拼接的完整算法 經(jīng)過碎片尺寸的調(diào)整 、 空間位置方向的變換以

5、 及重疊檢測的排除 , 兩塊碎片已經(jīng)能夠拼接到一起 了 ,但有時(shí)這種拼接仍然不能作為最終的拼接結(jié)果 . 我們還需要附加一些經(jīng)驗(yàn)性原則才能得到更合理的 拼接結(jié)果 . 這些原則主要包含 : ( 1 誤差評(píng)價(jià) . 指的是碎片進(jìn)行拼接之后對(duì)應(yīng) 子輪廓線上的點(diǎn)應(yīng)具有較小的距離誤差 , 即點(diǎn)集間 的吻合度要高 , ( 2 局部變化度評(píng)價(jià) . 兩塊碎片拼接處若具有 較大的曲折變化則更好 . 首先確定兩碎片吻合部分 的所有點(diǎn) ,對(duì)于每個(gè)點(diǎn)求其與相鄰兩頂點(diǎn)構(gòu)成三角 形的面積 ,然后將所有這些面積求和得到近似曲折 能量 ,能量越大則越符合該評(píng)價(jià)標(biāo)準(zhǔn) . 此評(píng)價(jià)標(biāo)準(zhǔn)能 夠避免將那些平直的非斷面拼接在一起 , 而是有

6、選 擇地把一般化的彎曲斷面拼接起來 . ( 3 公共部分長度評(píng)價(jià) . 兩塊碎片公共部分越 將 match 加入到候選列表 matchList 中 ; 對(duì) matchList 中記錄的所有匹配按照評(píng)價(jià)標(biāo)準(zhǔn)排列 優(yōu)劣次序 , 選擇最好的作為最終結(jié)果返回 ; 5 總結(jié)與展望 多組實(shí)際數(shù)據(jù)的測試表明本文方法計(jì)算簡單 , 魯棒性強(qiáng) ,可以在 ( m n 時(shí)間內(nèi)找到兩塊碎片之間 合理和較為精確的匹配結(jié)果 . 這給以后的全局匹配 研究提供了有力的支持 . 圖 7 展示的是幾組使用本 文方法進(jìn)行實(shí)際數(shù)據(jù)匹配的結(jié)果 . 今后的努力方向 就是以本文的工作為基礎(chǔ) , 繼續(xù)研究并實(shí)現(xiàn)多碎片 全局最優(yōu)自動(dòng)拼接 . 隨著

7、該技術(shù)的成熟 ,必將會(huì)給相 關(guān)行業(yè)提供極大的方便 . 348 計(jì) 算 機(jī) 學(xué) 報(bào) 2009 年 圖7 實(shí)驗(yàn)結(jié)果 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 文 獻(xiàn) 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 的物體碎片自動(dòng)拼 接算法 . 計(jì)算機(jī)學(xué)報(bào) , 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、維碎片自動(dòng)拼接方法 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