【正文】 選擇，算法被提出： 在另一個(gè)網(wǎng)格中查找最近點(diǎn)[Besl92]。這種計(jì)算可使用kd樹(shù)和/或closestpoint緩存方法加速[西門(mén)96] 查找從源點(diǎn)出發(fā)朝向具有目標(biāo)表面的源點(diǎn)法線的射線交點(diǎn)[陳91]。我們將把此稱(chēng)為“normal shooting“。 從目標(biāo)網(wǎng)狀范圍相機(jī)的視角點(diǎn)，投射源點(diǎn)到目標(biāo)網(wǎng)格上，[Blais 95, Neugebauer 97]。這也被稱(chēng)為“反向校準(zhǔn)。 “投射源點(diǎn)到目標(biāo)網(wǎng)格上，然后在目標(biāo)范圍圖像上進(jìn)行搜索。 搜索可能會(huì)使用基于點(diǎn)到點(diǎn)的距離度量標(biāo)準(zhǔn)[Benjemaa 97]，點(diǎn)到線的距離[Dorai 98]，或強(qiáng)度相容性[Weik 97]或顏色[普莉 97]。 上述任何方法，限制僅匹配根據(jù)一個(gè)給定的度量標(biāo)準(zhǔn)能與源點(diǎn)相容的點(diǎn)?；陬伾玔Godin 94]和法線間角度[Pulli 99]的相容性指標(biāo)已被探索過(guò)。由于我們沒(méi)有分析使用的顏色變種算法，所以我們將比較的特定變種算法是：最近點(diǎn)，最近相容點(diǎn)（45度法線內(nèi)），normal shooting，到相容點(diǎn)的normal shooting（45度法線內(nèi)），投影，和緊接搜索投影算法。，為試圖找到最近點(diǎn)，實(shí)際執(zhí)行搜索時(shí)采用的是最速下降鄰居到鄰居路程，在目標(biāo)網(wǎng)格中。我們選擇了這個(gè)變化，是因?yàn)樗鼛缀鹾驮谝恍┮暣爸芯o接窮舉搜索的投影算法效果一樣好，但卻消耗更少的運(yùn)行時(shí)間。首先，讓我們先來(lái)看看對(duì)“fractal”場(chǎng)景的性能（圖7）。對(duì)于這一場(chǎng)景，normal shooting 似乎產(chǎn)生了最好的結(jié)果，其次是投影算法。最近點(diǎn)算法，相反，表現(xiàn)相對(duì)較差。我們推測(cè)這個(gè)原因是，最近點(diǎn)算法對(duì)噪聲更敏感，它相對(duì)其他算法，往往會(huì)產(chǎn)生大量的不正確配對(duì)（圖8）。然而，在“incised plane”場(chǎng)景中情況是不同的（圖9）。在這里，最近點(diǎn)算法是唯一能收斂到正確解決方法的算法。因此，我們得出這樣的結(jié)論：雖然最近點(diǎn)算法對(duì)“簡(jiǎn)單”場(chǎng)景可能沒(méi)有最快收斂速度，但他們是最為強(qiáng)有力的，對(duì)“困難”的幾何圖形。雖然到目前為止我們一直將誤差看作一個(gè)迭代次數(shù)的函數(shù)，但也可以啟發(fā)性地將其看作為一個(gè)運(yùn)行時(shí)間函數(shù)。因?yàn)橥ǔCP匹配階段需要的時(shí)間最長(zhǎng)，而應(yīng)用需要ICP運(yùn)行迅速（不需要處理與幾何“難“例），所以必須選擇具有最快性能的匹配算法。因此，讓我們把誤差比較作為時(shí)間函數(shù)，在“fractal”的場(chǎng)景對(duì)這些算法進(jìn)行比較（圖10）。我們看到，雖然投影算法在每次迭代后不能呈現(xiàn)最好的收斂，但其每次迭代速度比迭代最近點(diǎn)查找或 normal shooting ，因?yàn)樗窃诤愣〞r(shí)間內(nèi)執(zhí)行的，而不涉及最接近點(diǎn)搜索（其中，即使由kd樹(shù)加速，需要O(1og n)的時(shí)間）。結(jié)果，基于投影的算法具有顯著的更快速度收斂與時(shí)間。請(qǐng)注意，除投影算法外，此圖不包括用來(lái)計(jì)算kd樹(shù)的時(shí)間。包括預(yù)計(jì)算時(shí)間（），會(huì)產(chǎn)生更有利的結(jié)果投影算法. 配對(duì)權(quán)重我們現(xiàn)在研究對(duì)前兩個(gè)步驟找到的對(duì)應(yīng)點(diǎn)分配不同權(quán)重后的效果。我們考慮四個(gè)不同的算法分配這些權(quán)重： 恒權(quán)重 分配較低權(quán)重給具有更大點(diǎn)到點(diǎn)距離的點(diǎn)對(duì)。這類(lèi)似于意圖降低那些點(diǎn)到點(diǎn)距離大于閥值的點(diǎn)對(duì)（見(jiàn)第），但后者方法避免了不連續(xù)。以下，[Godin 94],我們使用了： 基于正態(tài)相容性分配權(quán)重。顏色相容性加權(quán)也被使用[Godin 94]，雖然在這里我們不考慮。 基于對(duì)掃描噪聲在誤差度量上產(chǎn)生的預(yù)期效果不確定性加權(quán)。對(duì)點(diǎn)到面的誤差度量（），這取決于范圍內(nèi)點(diǎn)位置和曲面法線兩方面的不確定性。正如附錄中所展示的一個(gè)典型激光距離掃描儀的結(jié)果是不確定性較低，因而對(duì)那些傾斜遠(yuǎn)離距離相機(jī)的曲面應(yīng)該分配高的權(quán)重。我們先來(lái)看看一個(gè)“wave”場(chǎng)景中的版本（圖11）。額外噪音已加入以放大變種之間的差異。我們看到即使有額外的噪聲，所有的加權(quán)策略也有類(lèi)似表現(xiàn)，但帶有“不確定性”和“正態(tài)兼容性”選項(xiàng)的具有輕微地比別人更好的性能。對(duì)于“incisedplane” scene “場(chǎng)景（圖12），結(jié)果是相似的，雖然性能上存在差異較大。然而，我們闡釋這一結(jié)果時(shí)必須保持謹(jǐn)慎，因?yàn)橐圆淮_定性為基礎(chǔ)的加權(quán)分配更高的權(quán)重到那些法線指向遠(yuǎn)離距離掃描的模型上的點(diǎn)上。因此，對(duì)于這一場(chǎng)景不確定性加權(quán)分配了更高的權(quán)重到內(nèi)切口中點(diǎn)上，從而提高了收斂速度。在一般情況下，我們結(jié)論是，加權(quán)對(duì)收斂速度作用將會(huì)很小和高度數(shù)據(jù)依賴(lài)，選擇加權(quán)函數(shù)應(yīng)根據(jù)其他因素，例如最終結(jié)果的準(zhǔn)確性。我們期望在將來(lái)的論文中探索。 排除點(diǎn)對(duì)與對(duì)應(yīng)點(diǎn)對(duì)的權(quán)分配密切相關(guān)的是對(duì)確定配對(duì)完全排斥的情況。這樣做的目的通常是消除離群，當(dāng)進(jìn)行最小二乘最小化時(shí)，其中可能有很大的影響。下面拒絕策略已經(jīng)提出： 排除對(duì)應(yīng)的大于指定相隔距離（用戶指定）的點(diǎn)對(duì) 以某種度量為基礎(chǔ)，排除最差的n％點(diǎn)對(duì)，通常的度量方式是點(diǎn)到點(diǎn)的距離。作為建議[Pulli 99]，我們排斥10％的點(diǎn)對(duì)。 排除點(diǎn)到點(diǎn)間距離大與標(biāo)準(zhǔn)偏差某個(gè)倍數(shù)的點(diǎn)對(duì)。下面[Masuda 96]。 排除與鄰近點(diǎn)對(duì)不一致的點(diǎn)對(duì)，在假設(shè)曲面是剛性的情況下[Dorai 98]。這方案歸類(lèi)為兩個(gè)對(duì)應(yīng)(p1, p2)和(q1,q2)，當(dāng)且僅當(dāng)：大于某個(gè)閥值時(shí)不一致。下面[Dorai 98],我們用：作為閥值。然后，該算法排除了那些與大多數(shù)不相一致的對(duì)應(yīng)。請(qǐng)注意最初提出的算法，每步ICP迭代的運(yùn)行時(shí)間為O（n2）。為了減少運(yùn)行時(shí)間，我們選擇了只比較每個(gè)對(duì)應(yīng)其它10個(gè)，如果它與超過(guò)5個(gè)點(diǎn)不相容就，那就排除這個(gè)點(diǎn)。 排除包含網(wǎng)格邊界上點(diǎn)的點(diǎn)對(duì)[Turk 94]。后者策略，排除包含網(wǎng)格邊界點(diǎn)的點(diǎn)對(duì)的那個(gè)，在掃描間的重疊是不完整的情況下（圖13），對(duì)避免錯(cuò)誤配對(duì)尤為有用（那導(dǎo)致了變換估計(jì)中的系統(tǒng)性偏差）。由于其代價(jià)通常較低，在大多數(shù)應(yīng)用中它的使用有很少的缺陷，所以我們始終建議使用此策略，并且事實(shí)上，我們?cè)诒疚闹兴械谋容^中都使用了它。圖14比較了，在帶額外噪聲和離群“wave”場(chǎng)景中，無(wú)排除，最差10％拒絕，點(diǎn)對(duì)相容性排除。我們看到，奇異值排除不利于初始收斂。事實(shí)上，最為積極的點(diǎn)對(duì)排除算法（最差的10％排除）收斂速度趨于緩慢，在當(dāng)網(wǎng)格要對(duì)準(zhǔn)起來(lái)還比較遙遠(yuǎn)時(shí)。因此，我們總結(jié)出奇異點(diǎn)排除盡管對(duì)正確配準(zhǔn)確定的精度和穩(wěn)定性可能有效果，但一般提高不了收斂速度。在ICP算法的最后部分，我們將著眼于誤差度量和最小化誤差度量的算法。如下誤差度量已被使用： 對(duì)應(yīng)點(diǎn)間距離平方和。對(duì)這種形式的誤差度量標(biāo)準(zhǔn)，存在封閉形式解決方案以確定使誤差最小的剛體變換。解決方法主要有奇異值分解[Arun 87]，四元組[Horn 87]，正交矩陣 [Horn 88]，雙四元組[Walker 91]等。 Eggert et. al. 評(píng)估了各數(shù)值精度和穩(wěn)定性，總結(jié)了它們間細(xì)微的差異。 上面的“點(diǎn)到點(diǎn)”度量，同時(shí)考慮了點(diǎn)間距離和顏色差異[Johnson 97b]。 從每個(gè)源點(diǎn)到面距離的平方和包含了目標(biāo)點(diǎn)和于目標(biāo)法線正交的垂線[Chen 91]。在“點(diǎn)到面”的情況下，沒(méi)有封閉形式解決方案。使用一個(gè)通用的非線性最小二乘方程(即， LevenbergMarquardt), 或者通過(guò)簡(jiǎn)單的問(wèn)題線性化（即，假設(shè)增量旋轉(zhuǎn)很小，所以sin~1 ,cos ~1）可以解決。這有幾種方式擬定配準(zhǔn)搜索： 使用當(dāng)前的變換，反復(fù)生成對(duì)應(yīng)點(diǎn)集，并找到一個(gè)新的轉(zhuǎn)化使誤差度量最小[Chen 91]。 上述迭代最小化，結(jié)合了在變換空間中外插以加速收斂的方法[Besl 92]。 在初始條件時(shí)，以數(shù)起干擾開(kāi)始進(jìn)行迭代最小化, 然后選擇最好的結(jié)果[Simon 96]。這就避免了誤差函數(shù)里雜散的局部極小值，尤其是當(dāng)使用的是點(diǎn)到點(diǎn)的誤差度量時(shí)。 在進(jìn)行迭代最小化時(shí)，隨機(jī)選擇各種點(diǎn)子集，然后使用一個(gè)強(qiáng)大度量方式（最小中位數(shù)平方）來(lái)選擇最佳結(jié)果[Masuda 96]。 隨機(jī)尋找最佳的變換，利用模擬退火算法[Blais 95]。由于我們的重點(diǎn)是收斂速度，因?yàn)楹笳呷N方法往往趨于緩慢，我們的比較將著重于上述前兩種方法（即“經(jīng)典”ICP迭代算法，有或無(wú)外插）。我們使用的外插算法來(lái)源于一個(gè)由Besl和McKay所描述的算法[Besl92]，但我們進(jìn)行了兩個(gè)小的改動(dòng)，以提高效率和減少超調(diào)： 當(dāng)拋物線開(kāi)口向下和試圖二次外插時(shí)，我們使用最大X截距代替拋物線極值。 我們用一個(gè)抑制因素乘以外插數(shù)量，在我們的執(zhí)行中隨意設(shè)置到1/，雖然這偶爾減少了外插的好處，但這也增強(qiáng)了穩(wěn)定性，消除了許多超調(diào)引起的問(wèn)題。在“fractal”場(chǎng)景中, 我們看到點(diǎn)到面的誤差度量表現(xiàn)明顯比點(diǎn)到點(diǎn)度量更好，甚至在帶外插情況下（圖15）。對(duì)于“incisedplane” 場(chǎng)景, 不同處更為顯著（圖16）。在這里, 點(diǎn)至點(diǎn)的算法是不能夠得到正確的解決辦法, 因?yàn)槭褂玫狞c(diǎn)至點(diǎn)的誤差度量 does不允許面“過(guò)度滑動(dòng)”對(duì)方一樣容易。4 高速變種算法這種能使ICP實(shí)時(shí)執(zhí)行的能力（例如，在視頻率），將允許在計(jì)算機(jī)視覺(jué)和圖像中重要的新應(yīng)用。學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下進(jìn)行的研究工作所取得的成果。盡我所知，除文中已經(jīng)特別注明引用的內(nèi)容和致謝的地方外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式注明并表示感謝。本人完全意識(shí)到本聲明的法律結(jié)果由本人承擔(dān)。學(xué)位論文作者（本人簽名）： 年 月 日學(xué)位論文出版授權(quán)書(shū)本人及導(dǎo)師完全同意《中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù)出版章程》、《中國(guó)優(yōu)秀碩士學(xué)位論文全文數(shù)據(jù)庫(kù)出版章程》(以下簡(jiǎn)稱(chēng)“章程”)，愿意將本人的學(xué)位論文提交“中國(guó)學(xué)術(shù)期刊（光盤(pán)版）電子雜志社”在《中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù)》、《中國(guó)優(yōu)秀碩士學(xué)位論文全文數(shù)據(jù)庫(kù)》中全文發(fā)表和以電子、網(wǎng)絡(luò)形式公開(kāi)出版，并同意編入CNKI《中國(guó)知識(shí)資源總庫(kù)》，在《中國(guó)博碩士學(xué)位論文評(píng)價(jià)數(shù)據(jù)庫(kù)》中使用和在互聯(lián)網(wǎng)上傳播，同意按“章程”規(guī)定享受相關(guān)權(quán)益。論文密級(jí)：□公開(kāi) □保密（___年__月至__年__月）(保密的學(xué)位論文在解密后應(yīng)遵守此協(xié)議)作者簽名：_______ 導(dǎo)師簽名：______________年_____月_____日 _______年_____月_____日獨(dú) 創(chuàng) 聲 明本人鄭重聲明：所呈交的畢業(yè)設(shè)計(jì)(論文)，是本人在指導(dǎo)老師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果，成果不存在知識(shí)產(chǎn)權(quán)爭(zhēng)議。盡我所知，除文中已經(jīng)注明引用的內(nèi)容外，本設(shè)計(jì)（論文）不含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的作品成果。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體均已在文中以明確方式標(biāo)明。本聲明的法律后果由本人承擔(dān)。 作者簽名: 二〇一〇年九月二十日畢業(yè)設(shè)計(jì)（論文）使用授權(quán)聲明本人完全了解濱州學(xué)院關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定。本人愿意按照學(xué)校要求提交學(xué)位論文的印刷本和電子版，同意學(xué)校保存學(xué)位論文的印刷本和電子版，或采用影印、數(shù)字化或其它復(fù)制手段保存設(shè)計(jì)（論文）；同意學(xué)校在不以營(yíng)利為目的的前提下，建立目錄檢索與閱覽服務(wù)系統(tǒng)，公布設(shè)計(jì)（論文）的部分或全部?jī)?nèi)容，允許他人依法合理使用。（保密論文在解密后遵守此規(guī)定）作者簽名: 二〇一〇年九月二十日致 謝時(shí)間飛逝，大學(xué)的學(xué)習(xí)生活很快就要過(guò)去，在這四年的學(xué)習(xí)生活中，收獲了很多，而這些成績(jī)的取得是和一直關(guān)心幫助我的人分不開(kāi)的。首先非常感謝學(xué)校開(kāi)設(shè)這個(gè)課題，為本人日后從事計(jì)算機(jī)方面的工作提供了經(jīng)驗(yàn)，奠定了基礎(chǔ)。本次畢業(yè)設(shè)計(jì)大概持續(xù)了半年，現(xiàn)在終于到結(jié)尾了。本次畢業(yè)設(shè)計(jì)是對(duì)我大學(xué)四年學(xué)習(xí)下來(lái)最好的檢驗(yàn)。經(jīng)過(guò)這次畢業(yè)設(shè)計(jì)，我的能力有了很大的提高，比如操作能力、分析問(wèn)題的能力、合作精神、嚴(yán)謹(jǐn)?shù)墓ぷ髯黠L(fēng)等方方面面都有很大的進(jìn)步。這期間凝聚了很多人的心血，在此我表示由衷的感謝。沒(méi)有他們的幫助，我將無(wú)法順利完成這次設(shè)計(jì)。首先，我要特別感謝我的知道郭謙功老師對(duì)我的悉心指導(dǎo)，在我的論文書(shū)寫(xiě)及設(shè)計(jì)過(guò)程中給了我大量的幫助和指導(dǎo)，為我理清了設(shè)計(jì)思路和操作方法，并對(duì)我所做的課題提出了有效的改進(jìn)方案。郭謙功老師淵博的知識(shí)、嚴(yán)謹(jǐn)?shù)淖黠L(fēng)和誨人不倦的態(tài)度給我留下了深刻的印象。從他身上，我學(xué)到了許多能受益終生的東西。再次對(duì)周巍老師表示衷心的感謝。其次，我要感謝大學(xué)四年中所有的任課老師和輔導(dǎo)員在學(xué)習(xí)期間對(duì)我的嚴(yán)格要求，感謝他們對(duì)我學(xué)習(xí)上和生活上的幫助，使我了解了許多專(zhuān)業(yè)知識(shí)和為人的道理，能夠在今后的生活道路上有繼續(xù)奮斗的力量。另外，我還要感謝大學(xué)四年和我一起走過(guò)的同學(xué)朋友對(duì)我的關(guān)心與支持，與他們一起學(xué)習(xí)、生活，讓我在大學(xué)期間生活的很充實(shí)，給我留下了很多難忘的回憶。最后，我要感謝我的父母對(duì)我的關(guān)系和理解，如果沒(méi)有他們?cè)谖业膶W(xué)習(xí)生涯中的無(wú)私奉獻(xiàn)和默默支持，我將無(wú)法順利完成今天的學(xué)業(yè)。四年的大學(xué)生活就快走入尾聲，我們的校園生活就要?jiǎng)澤暇涮?hào)，心中是無(wú)盡的難舍與眷戀。從這里走出，對(duì)我的人生來(lái)說(shuō)，將是踏上一個(gè)新的征程，要把所學(xué)的知識(shí)應(yīng)用到實(shí)際工作中去?；厥姿哪辏〉昧诵┰S成績(jī)，生活中有快樂(lè)也有艱辛。感謝老師四年來(lái)對(duì)我孜孜不倦的教誨，對(duì)我成長(zhǎng)的關(guān)心和愛(ài)護(hù)。學(xué)友情深，情同兄妹。四年的風(fēng)風(fēng)雨雨，我們一同走過(guò)，充滿著關(guān)愛(ài)，給我留下了值得珍藏的最美好的記憶。在我的十幾年求學(xué)歷程里，離不開(kāi)父母的鼓勵(lì)和支持，是他們辛勤的勞作，無(wú)私的付出，為我創(chuàng)造良好的學(xué)習(xí)條件，我才能順利完成完成學(xué)業(yè)，感激他們一直以來(lái)對(duì)我的撫養(yǎng)與培育。最后，我要特別感謝我的導(dǎo)師趙達(dá)睿老師、和研究生助教熊偉麗老師。是他們?cè)谖耶厴I(yè)的最后關(guān)頭給了我們巨大的幫助與鼓勵(lì)，給了我很多解決問(wèn)題的思路，在此表示衷心的感激。老師們認(rèn)真負(fù)責(zé)的工作態(tài)度，嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神和深厚的理論水平都使我收益匪淺。他無(wú)論在理論上還是在實(shí)踐中，都給與我很大的幫助，使我得到不少的提高這對(duì)于我以后的工作和學(xué)習(xí)都有一種巨大的幫助，感謝他耐心的輔導(dǎo)。在論文的撰寫(xiě)過(guò)程中老師們給予我很大的幫助，幫助解決了不少的難點(diǎn)，使得論文能夠及時(shí)