基于ransac算法的sift特征匹配研究(OpenCV+VS2010)-朱萬革(最終版)

SHANGHAI學(xué)士學(xué)位論文THESISOFBACHELOR基于ransac算法的sift特征匹配研究〔OpenCV+VS2023〕上海交通大學(xué)畢業(yè)設(shè)計〔論文〕學(xué)術(shù)誠信聲明本人鄭重聲明：所呈交的畢業(yè)設(shè)計〔論文〕，是本人在導(dǎo)師的指導(dǎo)下，獨立進(jìn)行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。對本文的研究做出重要奉獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本人完全意識到本聲明的法律結(jié)果由本人承當(dāng)。作者簽名：日期：年月日上海交通大學(xué)畢業(yè)設(shè)計〔論文〕版權(quán)使用授權(quán)書本畢業(yè)設(shè)計〔論文〕作者同意學(xué)校保存并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)上海交通大學(xué)可以將本畢業(yè)設(shè)計〔論文〕的全部或局部內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本畢業(yè)設(shè)計〔論文〕。保密□，在年解密后適用本授權(quán)書。本論文屬于不保密□?！舱堅谝陨戏娇騼?nèi)打“√〞〕作者簽名：指導(dǎo)教師簽名：日期：年月日日期：年月日視頻圖像跟蹤系統(tǒng)摘要圖像〔Image〕--是客觀世界的景物通過光學(xué)系統(tǒng)作用后產(chǎn)生的影像。圖像直觀地反映了場景中物體的顏色、亮度等特征，從而使我們能清晰分辨他們的形狀、大小和空間位置。近30年來人們試圖研究基于計算機(jī)的視覺系統(tǒng)，并且試圖利用其系統(tǒng)來代替工業(yè)農(nóng)業(yè)上的有害勞動。這樣的視覺系統(tǒng)漸漸地進(jìn)入我們的生活，讓我們的生活變得很豐富，并且我們現(xiàn)在享受著圖像處理這學(xué)問的成果。在世界上的先進(jìn)的國家都設(shè)立了圖像處理研究所，研究解決國防部門所要的問題。本文將介紹基于OpenCV〔OpenSourceComputerVisionLibrary〕的視頻圖像匹配、拼接、融合和目標(biāo)跟蹤的算法以及方法。說到圖像拼接，本文中所用的圖像拼接算法是高效的SIFT特征算法。首先，用兩個通用的USB攝像頭來實時地進(jìn)行采集圖像，并對這兩幅圖像提取SIFT特征點。然后，進(jìn)行粗匹配。最后用RANSAC算法對所提取出來的SIFT特征點匹配對進(jìn)行提純以及估計模型參數(shù)。最后把兩幅圖像拼接成一幅完整的圖像，并且用加權(quán)平均算法進(jìn)行無縫拼接。再進(jìn)行攝像頭標(biāo)定，求出兩個通用攝像頭的內(nèi)外參數(shù)，最后進(jìn)行測距以及跟蹤。最終取得了令人滿意的結(jié)果。關(guān)鍵詞：SIFT，匹配,拼接，配準(zhǔn)，RANSACVIDEOTRACKINGSYSTEMABSTRACTFormanyyears,peoplehavebeenstudyinghowtomaketherobotorthecomputerabletoidentifytargetsandobtaininformationaboutthesurroundingenvironment.Wepeoplecaneasilyseeandidentifyeverykindofobjects,butforcomputersorrobots,thisisaverydifficulttaskanditisaprocessthatinvolvesalotofscientificknowledge.Themainpartofobjectrecognitionisdigitalimageprocessing.Aftertheinventionofthecomputer,peoplebegantodirecttheirresearchonhowtomakethecomputermorepowerfulanduseful.Forthispurpose,manyscientistshavededicatedtheirlifeforthedevelopmentofcomputer.Therapiddevelopmentofcomputercausesaveryfastdevelopmentofdigitalimageprocessing.Whywepeoplestudyscience?Ofcoursetheanswerwillbetomakeourlifeeasier,andtobeabletoliveinourdreamlife,sothatwecanenjoythelifeincomfortandhappiness.Nowadays,Imageprocessingtechnologyiseverywherearoundus,butsometimesbecauseweareusedtothistechnologysowedon’tpayattention.Forexample,thephone'shandwritinginputmethod,companyentrancefingerprintidentificationsystem,licenseplaterecognitionsystem,roboticssystemprogramforexploringthelunar,medicalimagingtechnology,facialrecognitionsystems,andsatelliteimagingsystemandsoon.Inthelastthreedecades,imageprocessingtechnologyhasmadearapiddevelopment,whichisinseparablefromthedevelopmentofcomputers,andmoreinseparablefromthedevelopmentofmaterialsscience.Wecannoticethatsciencenowhavepenetratedintoeveryprofessionalimageprocessingandtheimagecomestomanyareas.Thesedaysimageprocessingtechnologyisdirectlyrelatedtoourstandardlife,thistechnologyinvolvesimagerecognition,imageanalysisandimagestitching,etc.Imageprocessingisnowfacingenormouschallenges,duetothedevelopmentofmaterialsprocessingindustry,CNCmachinetoolsandcontroltheory,imageprocessingtechnologyrequirementsareveryhigh,Therefore,manyscientistshavespenttheirlifestudyingimageprocessingtechnology,tryingtodevelopmoreflexible,morereliable,moreaccurateimageprocessingtechnologyandimageprocessingalgorithms.Videotrackingsystemincludestheimagestitchingtechnology,whenwementionimagestitchingtechnology,wehavetotalkaboutimagematchingandimageregistration,becausethesetwomodulesarethecorepartsoftheimagestitching.Inthisstudy,IusedScale-invariantfeaturetransform(SIFT)algorithm,thisalgorithmfeaturesrepeatability,unique,localized,quantitative,accuracyandefficiency.Firstfromthetwocameras(peopleleftandrighteye)insynchronousreadstheimagesequence,andIappliedtheseimagesequencesRANSACalgorithmbasedonSIFTfeaturematchingandobtainedagoodimagestitching.Thenthisimagewithanimagetemplatematchingofimagerecognitionandtracking(basedonSIFT),whilesupportingthebinocularmeasurementstoobtaindistanceinformation.Typically,abouttwoamomenttoreadthetwocameraimageswithalotSIFTfeaturepoint,sotheneedtopurifythedatausingtheRANSACalgorithm,likethatfilter,however,sothereisstillasmallamountoffilteredwrongmatchingpairs.SoweuseRANSACmethodparameterestimationperspectivematrix.Theso-calledRANSACmethodisawidelyusedmodelparameterestimationalgorithm.Isthefirstofseveralrandomlymatchedpairs(thethesismustselectatleastfourpairsabove),weseeitasinteriorpoint,andthenestimatetheparameters,findoutifyoumeetenoughmatrixmatchingpairs,thenwethinkthatthismodeliscorrect.Ifthereisnotenoughtomeetmorethanamatchfor,orverylittle,thenwegiveup,andthenrandomlyselectedafewmatchesagainstrepeatedtheaboveprocedure.Experimentalresultsshowthatseeksoutsuchaperspectivematrixisright.Thispaperdescribesthestepsaccordingtotheabovevideotrackingsystemdevelopedandusedbytheprocess;Ihaveimprovedalgorithmandexperimentalresults.Keywords:SIFT,OpenCV,matching,RANSAC,videoimage目錄第一章緒論11.1論文研究背景21.2國內(nèi)外研究現(xiàn)狀31.3論文任務(wù)和工作4第二章SIFT特征算法52.1有關(guān)SIFT算法的術(shù)語52.2SIFT綜述62.3尺度空間和高斯濾波72.4關(guān)鍵點檢測122.5特征點方向確定以及SIFT特征向量的生成152.6SIFT特征點匹配162.7本章小結(jié)19第三章基于RANSAC算法的圖像拼接系統(tǒng)設(shè)計203.1對開源庫OpenCV的簡單的介紹203.2開發(fā)環(huán)境的搭建〔VS2023+OpenCV2.3.1〕203.3實時采集圖像213.4圖像變換模型〔矩陣〕223.5基于RANSAC的圖像拼接233.6本章小結(jié)27第四章基于OpenCV的攝像頭標(biāo)定以及測距284.1攝像機(jī)標(biāo)定一般模型〔針孔相機(jī)模型〕284.2基于OpenCV的測距原理304.3兩個攝像頭的標(biāo)定以及測距334.4本章小結(jié)41第五章總結(jié)以及未來的展望42參考文獻(xiàn)42謝辭44第一章緒論很多年來，人們一直研究怎么樣才能夠讓機(jī)器人或者計算機(jī)識別目標(biāo)、認(rèn)知周圍環(huán)境。在我們看來很簡單的物體，計算機(jī)或者機(jī)器人很難區(qū)分出來。這是一個很艱難的任務(wù)，也是一個涉及到很多科學(xué)的學(xué)問。我們所說的圖像處理主要局部是數(shù)字圖像處理。計算機(jī)的創(chuàng)造以后，人們開始著重研究怎么樣讓計算機(jī)的功能更強(qiáng)大更加具有實用性，隨著歲月的流逝，很多科學(xué)家為了計算機(jī)的開展奉獻(xiàn)了自己的一生。計算機(jī)的飛速開展給圖像處理帶來了飛速的開展。人類為什么要研究科學(xué)？無疑是為了讓我們的生活更加滋潤，讓我們活在我們所設(shè)想過的夢幻里。這樣我們舒舒服服的享受生活，幸福快樂地過著人生。數(shù)字圖像處理技術(shù)無處不在。只不過我們習(xí)慣了沒注意而已。比方說，的手寫輸入法、公司門口的指紋識別系統(tǒng)、交通統(tǒng)計時用到的車牌識別系統(tǒng)、探月機(jī)器人系統(tǒng)、醫(yī)學(xué)成像技術(shù)、臉部識別系統(tǒng)和衛(wèi)星拍攝系統(tǒng)等等。圖像處理技術(shù)近三十年來得到了飛速的開展，這離不開電腦開展的伴隨，更加離不開材料科學(xué)的開展?？梢?，現(xiàn)在科學(xué)的每個專業(yè)都滲透到圖像處理，而且圖像涉及到的領(lǐng)域很多。到哪兒都能感覺到圖像處理技術(shù)的強(qiáng)大。圖像處理技術(shù)的應(yīng)用方面很廣，小到我們所用的智能里，大到國防工業(yè)。在戰(zhàn)爭的時候，敵機(jī)發(fā)現(xiàn)是個很關(guān)鍵的問題，因為早發(fā)現(xiàn)可以早點做好戰(zhàn)斗準(zhǔn)備。用雷達(dá)發(fā)現(xiàn)敵機(jī)是主動的，所以容易被發(fā)現(xiàn)，但是，如果開發(fā)一個雙目跟蹤系統(tǒng)〔利用兩個已標(biāo)定好的攝像頭〕的話，不會被敵機(jī)發(fā)現(xiàn)，也就是說被動跟蹤方式。這樣的系統(tǒng)是降低本錢，而且不會被敵機(jī)發(fā)現(xiàn)，所以，其利用價值是無可限量的。圖像處理技術(shù)有圖像識別、圖像分析和圖像拼接等等。圖像處理現(xiàn)在面臨巨大的挑戰(zhàn)，隨著材料加工業(yè)、數(shù)控機(jī)床和控制理論的開展，各領(lǐng)域?qū)D像處理技術(shù)的要求非常的高。所以，很多科學(xué)家用自己的一生去研究圖像處理技術(shù)，試圖研發(fā)出更靈活、更加可靠、更高精度的圖像處理技術(shù)以及圖像處理算法。作為處理圖像的圖像處理數(shù)學(xué)工具，MATLAB和MATHCAD不可缺少。此外，C,C++和Java是目前為止最受歡送的視覺系統(tǒng)實現(xiàn)語言，這是因為它們在集成高級和低級功能方面力量強(qiáng)大而且編譯能力強(qiáng)。[1,11]除此以外OpenCV開源庫作為強(qiáng)大的圖像處理開源庫得到了廣泛的應(yīng)用。之所以得到了眾多科學(xué)家開發(fā)人員的好評，是因為它是開放的，也就是說免費的，任何人都可以去用，其次呢，是因為它所擁有的圖像處理功能非常之強(qiáng)大。比起其他圖像處理軟件，OpenCV的強(qiáng)大表現(xiàn)在它有很多封裝好的函數(shù)，這些函數(shù)各個都是一個功能，比方說要是用visualc++中實現(xiàn)的功能，在OpenCV上用簡單的幾個函數(shù)來實現(xiàn)。下面著重介紹本論文的研究背景、國內(nèi)外研究現(xiàn)狀以及論文內(nèi)容和組織結(jié)構(gòu)。1.1論文研究背景數(shù)字圖像處理起源于20世紀(jì)20年代，當(dāng)時通過海底電纜從英國的倫敦到美國的紐約采用數(shù)字壓縮技術(shù)傳輸了第一張數(shù)字照片。之后的開展有點緩慢，知道第三代計算機(jī)的問世，才開始迅速的開展。[3,6]作為圖像處理軟件，OpenCV近十年來一直被人矚目，一直被很多圖像處理科學(xué)家們收到寵愛。雖然MATLAB具有很強(qiáng)大的科學(xué)計算功能和圖像處理功能，但在圖像處理功能方面超不過OpenCV的。麻省理工學(xué)院計算機(jī)科學(xué)與人工智能實驗室的WilliamT.Freeman曾說過“OpenCV庫對從業(yè)人員而言非常有用，對初涉該領(lǐng)域的新手而言不失為一個優(yōu)秀工具。正如其廣而告之的那樣，它是一套高效的計算機(jī)視覺算法。〞OpenCV是一個開源的計算機(jī)視覺庫，是英特爾公司資助的兩大圖像處理利器之一。作為一個跨平臺的計算機(jī)視覺庫，它為圖像處理、模式識別、三維重建、物體跟蹤、機(jī)器學(xué)習(xí)和線性代數(shù)提供了各種各樣的算法。截止2023年8月，在網(wǎng)站的OpenCV下載次數(shù)超過2，200，000次。[4]過去一周〔從2023-05-16到2023-05-22〕，在的OpenCV下載次數(shù)超過了32，942次，這數(shù)字僅僅是一周的下載次數(shù)。OpenCV開源庫至今更新到OpenCV2.4.5。本人在論文中所提到的算法都是用VisualStudio2023和OpenCV2.3.1的搭建下寫程序編譯通過的。雖然OpenCV開源庫是給大家開放的圖像處理算法庫，但是，在國內(nèi)有關(guān)OpenCV的書籍和文獻(xiàn)極少，針對初涉該領(lǐng)域的新手們的教程只有兩本——“學(xué)習(xí)OpenCV〞〔中文版〕，“OpenCV教程——根底版〞。在網(wǎng)上有與OpenCV有關(guān)的資料，但是，也是很少，而且相當(dāng)零散。這種現(xiàn)象造成了很多喜歡玩OpenCV的人很難系統(tǒng)的學(xué)到OpenCV。不過，在互聯(lián)網(wǎng)的飛速的開展的情況下，這樣的現(xiàn)象漸漸地少了很多。因為互聯(lián)網(wǎng)上有關(guān)OpenCV的論壇很多，喜歡跟OpenCV打交道的人們可以通過互聯(lián)網(wǎng)上的論壇或者貼吧互相交流互相幫助。這樣在某種程度上形成了OpenCV培訓(xùn)所。寫這篇論文之前，本人也在互聯(lián)網(wǎng)上得到了很多人們的幫助，也幫助過很多人們。但是，這也是一定的范圍內(nèi)進(jìn)行的，也就是說局限在簡單的程序語法或者特定的函數(shù)用法等等。本人在論文中用到的算法是尺度不變特征點〔SIFT〕算法，尺度不變特征點具有可重復(fù)性、獨特性、局部性、數(shù)量型、準(zhǔn)確性和高效性。下面看看國內(nèi)外研究現(xiàn)狀。1.2國內(nèi)外研究現(xiàn)狀OpenCV的更新?lián)Q代地升級給我們帶來了很多好處，以前要寫很長的代碼完成某功能的操作不需要了，因為OpenCV的版本越高里面嵌在的函數(shù)的封裝性越來越好。這給了我們極大地好處，只要我們能夠了解怎么調(diào)用這些函數(shù)和圖像處理的根底理論就好辦了。視頻圖像跟蹤系統(tǒng)其本身包含了圖像拼接技術(shù)這領(lǐng)域，說道圖像拼接技術(shù)不得不提起圖像匹配和圖像配準(zhǔn)。因為這兩個模塊是圖像拼接的主要核心局部?，F(xiàn)在被廣泛使用的匹配有特征匹配和模板匹配等等。其中特征匹配是本論文所利用的。特征匹配的最后效果好壞取決于特征空間的選取，所謂的特征空間就是由參與匹配的圖像特征構(gòu)成的。特征點的類型很多：比方原始灰度、顯著特征點、邊緣輪廓、統(tǒng)計特征、局部描述符、高層結(jié)構(gòu)特征等。其中SIFT特征點幾年來最為被廣泛使用。利用SIFT特征空間的匹配大致分為三個步驟。第一步是特征提取，第二步是特征匹配。所謂的特征提取是指從具有共同局部的兩幅圖像提取共有的特征。特征匹配是對從兩幅圖像中提取出來的共有的特征點進(jìn)行對應(yīng)。Movarac在1980年提出了關(guān)于角點的最初算法。在這根底上1988年Harris把這個初始想法正式形式化為稱為結(jié)構(gòu)張量的兩個特征值性質(zhì)的問題。從此以后很多科學(xué)家參加到了這領(lǐng)域開始研究各種算法。Triggs和Kenney提出了廣義角點度量。這時候的算法都有著致命的弱點，那就是對廣義的視角的匹配效果并不好，就不適用。為了克服這問題，1995年，張正友提出了用興趣點附近的圖像區(qū)域進(jìn)行匹配的方法。但他的算法無法解決圖像旋轉(zhuǎn)、尺度變化、投影變化等問題。直到2004年Lowe完善了根據(jù)1999年基于Lindeberg的圖像尺度空間理論提出的SIFT〔ScaleInvariantFeatureTransform——尺度不變特征〕算法。之所以SIFT特征空間被廣泛使用，是因為它對縮放、旋轉(zhuǎn)、平移和投影變換等等具有不變性。SIFT特征點匹配算法具有較強(qiáng)的魯棒性，而且算法速度高、精度高。1.3論文任務(wù)和工作近幾年來SIFT特征算法成為了很多科學(xué)家以及研究員的研究熱點。它以自身的優(yōu)勢漸漸地成為了圖像匹配的主流算法。本論文圍繞著如何將SIFT特征算法應(yīng)用于視頻圖像跟蹤系統(tǒng)中，實現(xiàn)從兩個usb攝像頭中讀取的兩幅圖像進(jìn)行匹配，怎么樣提高匹配速度以及精度等問題開展研究。用SIFT算法進(jìn)行的特征點的提取和粗匹配后的，效果還是不太理想，因為畢竟存在錯誤的匹配。所以，要用RANSAC〔隨機(jī)抽樣一致性〕算法對粗匹配的匹配對進(jìn)行提純工作。兩個通用USB攝像頭畢竟存在畸變性，特別是徑向畸變厲害，所以，我們需要用OpenCV的自帶函數(shù)來進(jìn)行攝像頭標(biāo)定。在本論文采用的標(biāo)定方法是張氏法，需要格子板，本論文采用的標(biāo)定物正是具有9*6=54個角點的格子板標(biāo)定物。通過OpenCV自帶的標(biāo)定算法以及相關(guān)的函數(shù)來求出攝像頭的內(nèi)外參數(shù)。利用求出來的內(nèi)外參數(shù)進(jìn)行簡單的計算得到實際物體到攝像頭的距離信息。利用已經(jīng)標(biāo)定好的攝像頭進(jìn)行測距的時候不需要模板匹配，因為只要找到很強(qiáng)的SIFT匹配對，也就是說只要找到正確的匹配對〔當(dāng)然跟目標(biāo)相關(guān)的，其他的丟掉〕，就可以求出攝像頭到物體之間的距離信息。首要條件是把兩個攝像頭放置的時候它們的光心軸要平行，以使讓最后得出的距離接近實際的距離。下面來看看本論文理論結(jié)構(gòu)以及各章的中心內(nèi)容。下面就是論文主要內(nèi)容：：第一章為緒論，簡單的論述了本論文的研究背景和國內(nèi)外研究現(xiàn)狀等。對圖像處理經(jīng)典算法進(jìn)行了解剖，并論述了SIFT算法的優(yōu)越性。最后給出了本論文的內(nèi)容結(jié)構(gòu)以及論文內(nèi)容。：第二章主要介紹了有關(guān)SIFT算法的知識以及具體實現(xiàn)的方法。最后還簡單的介紹了RANSAC算法的一般原理。：第三章是作為本論文的重點，著重介紹了從兩個攝像頭中讀取的兩幅圖片中怎么樣提取SIFT特征點、怎么樣構(gòu)建特征點空間以及怎么樣粗匹配，最后介紹了經(jīng)過RANSAC算法以后圖像拼接以及配準(zhǔn)原理和方法。給出了評估模型的一般方法。：第四章講述了基于OpenCV的攝像機(jī)標(biāo)定原理和方法。針對雙目視頻跟蹤系統(tǒng)的研制開發(fā)講述了攝像機(jī)標(biāo)定的數(shù)學(xué)原理以及具體實現(xiàn)方法和實驗結(jié)果。：第五章為總結(jié)和展望。第二章SIFT特征算法作為一種局部描述子，尺度不變形特征變換，Sift(ScaleInvariantFeatureTransformation)被廣泛利用著。它具有尺度不變形，在圖像中找出關(guān)鍵點。從SIFT特征算法的誕生以來，出現(xiàn)了很多有關(guān)SIFT的算法，人們?yōu)榱四軌蛟诂F(xiàn)實中利用，而試圖改良它。這些局部特征被廣泛利用而且被研究的真正原因在于它能夠表述統(tǒng)計意義的圖像特征。接下來從下面開始著重看SIFT特征算法具體內(nèi)容。2.1有關(guān)SIFT算法的術(shù)語本節(jié)論述本論文常用的一些術(shù)語以及概念。特征點：特征點可以是一個點，可以是一個很小的局部區(qū)域，也可以是局部特征，這三個都是相同的概念，知識它們出現(xiàn)的歷史時期不一樣而已。當(dāng)然我們想要的特征點最好是一個點，可以理解為我們所研究的數(shù)字圖像離散化后得到的一個最小的單位--像素點。但是，我們在做研究的時候，我們所關(guān)心的就是特征點以及它的領(lǐng)域。因為特征點的領(lǐng)域所表現(xiàn)出來的是某個物體的邊緣或者特定的角點，所以特征點的領(lǐng)域?qū)ξ覀兒罄m(xù)的研究有很大的幫助。局部特征：特征可以分為全局特征和局部特征。我們很容易理解全局特征。比方說我們看一幅圖片中孤立的物體時，或者看彩色照片的時候很容易檢測到某個物體或者某個人的臉。因為我們?nèi)祟愃鶕碛械难坨R，也就是說人類的視覺系統(tǒng)是具有極高的全局特征區(qū)分能力，不過，讓計算機(jī)或者機(jī)器人能夠認(rèn)知這些全局特征，需要消耗很大的精力和資金的投入。即使做到了，也是在一定的范圍內(nèi)可行的。因為圖像處理技術(shù)雖然近幾十年開展到令人振奮的程度，但是實際應(yīng)用中還有很多海量的問題需要解決。幾何變換：幾何變形有平移變換、平移+旋轉(zhuǎn)變換、相似〔平移+縮放+旋轉(zhuǎn)〕變換、仿射變換和透視變換。仿射變換：他所指的是兩個互不相同的坐標(biāo)下的矢量之間的邊換。2.2SIFT綜述尺度不變特征轉(zhuǎn)換(Scale-invariant

feature

transform或SIFT)是一種電腦視覺的算法用來偵測與描述影像中的局部性特征，它在空間尺度中尋找極值點，并提取出其位置、尺度、旋轉(zhuǎn)不變量，此算法由

David

Lowe在1999年所發(fā)表，2004年完善總結(jié)。其應(yīng)用范圍包含物體辨識、機(jī)器人地圖感知與導(dǎo)航、影像縫合、3D模型建立、手勢辨識、影像追蹤和動作比對。此算法有其專利，專利擁有者為英屬哥倫比亞大學(xué)。局部影像特征的描述與偵測可以幫助辨識物體，SIFT

特征是基于物體上的一些局部外觀的興趣點而與影像的大小和旋轉(zhuǎn)無關(guān)。對于光線、噪聲、些微視角改變的容忍度也相當(dāng)高?；谶@些特性，它們是高度顯著而且相對容易擷取，在母數(shù)龐大的特征數(shù)據(jù)庫中，很容易辨識物體而且鮮有誤認(rèn)。使用

SIFT特征描述對于局部物體遮蔽的偵測率也相當(dāng)高，甚至只需要3個以上的SIFT物體特征就足以計算出位置與方位。在現(xiàn)今的電腦硬件速度下和小型的特征數(shù)據(jù)庫條件下，辨識速度可接近即時運(yùn)算。SIFT特征的信息量大，適合在海量數(shù)據(jù)庫中快速準(zhǔn)確匹配。SIFT算法的特點有：1)

SIFT特征是圖像的局部特征，其對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性；2)獨特性〔Distinctiveness〕好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進(jìn)行快速、準(zhǔn)確的匹配；3)多量性，即使少數(shù)的幾個物體也可以產(chǎn)生大量的SIFT特征向量；4)高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以到達(dá)實時的要求；5)可擴(kuò)展性，可以很方便的與其他形式的特征向量進(jìn)行聯(lián)合。SIFT算法可以解決的問題：目標(biāo)的自身狀態(tài)、場景所處的環(huán)境和成像器材的成像特性等因素影響圖像配準(zhǔn)/目標(biāo)識別跟蹤的性能。而SIFT算法在一定程度上可解決：1.)目標(biāo)的旋轉(zhuǎn)、縮放、平移〔RST〕2.)圖像仿射/投影變換〔視點viewpoint〕3.)光照影響〔illumination〕4.)目標(biāo)遮擋〔occlusion〕5.)雜物場景〔clutter〕6.)噪聲SIFT算法的實質(zhì)是在不同的尺度空間上查找關(guān)鍵點(特征點)，并計算出關(guān)鍵點的方向。SIFT所查找到的關(guān)鍵點是一些十分突出，不會因光照，仿射變換和噪音等因素而變化的點，如角點、邊緣點、暗區(qū)的亮點及亮區(qū)的暗點等。

Lowe將SIFT算法分解為如下四步：1.

尺度空間極值檢測：搜索所有尺度上的圖像位置。通過高斯微分函數(shù)來識別潛在的對于尺度和旋轉(zhuǎn)不變的興趣點。2.

關(guān)鍵點定位：在每個候選的位置上，通過一個擬合精細(xì)的模型來確定位置和尺度。關(guān)鍵點的選擇依據(jù)于它們的穩(wěn)定程度。3.

方向確定：基于圖像局部的梯度方向，分配給每個關(guān)鍵點位置一個或多個方向。所有后面的對圖像數(shù)據(jù)的操作都相對于關(guān)鍵點的方向、尺度和位置進(jìn)行變換，從而提供對于這些變換的不變性。4.

關(guān)鍵點描述：在每個關(guān)鍵點周圍的鄰域內(nèi)，在選定的尺度上測量圖像局部的梯度。這些梯度被變換成一種表示，這種表示允許比擬大的局部形狀的變形和光照變化。2.3尺度空間和高斯濾波當(dāng)用一個具有視覺系統(tǒng)的機(jī)器人在未知的場景下分析周圍環(huán)境的時候，機(jī)器人的視覺系統(tǒng)沒有方法預(yù)先知道圖像中物體的真正尺度。所以，需要考慮得到的圖像在多尺度下的描述，獲得所感興趣物體尺度。因此，尺度空間的很多處理算子跟哺乳動物視網(wǎng)膜和視覺系統(tǒng)有著極高的相似性。所以，尺度空間理論經(jīng)常與生物視覺系統(tǒng)相關(guān)聯(lián)。這一節(jié)將討論尺度空間的根本概念以及理論根底。并且利用幾個實際圖像實例來介紹尺度空間理論在場景分析中的應(yīng)用。2.2.1圖像的金字塔化圖像的金字塔化所指的是對圖像進(jìn)行低通濾波操作。在圖像的金字塔化中被利用的低通濾波器是高斯低通濾波器。具體地說，把一幅圖像和高斯濾波器進(jìn)行卷積運(yùn)算后，再對圖像進(jìn)行橫軸和縱軸的方向進(jìn)行抽樣。這樣得到的一些列圖像稱之為已金字塔化的圖像序列。不多，它雖然能夠表達(dá)出圖像在多尺度下的描述，但它缺少扎實的理論背景，很難分析圖像中物體的各種尺度。早在1983年，Witkin提出信號的尺度空間表達(dá)就是利用一系列單參數(shù)、款讀遞增的高斯濾波器將原始信號濾波的道德一組低頻信號。說道低通濾波器，雖然其種類很多，但是，Koenderink、Lindeberg、Florack等科學(xué)家利用精準(zhǔn)的數(shù)學(xué)理論通過不同途徑證明了高斯核就是實現(xiàn)尺度變換的唯一的變換核。[2,13]由不同高斯核組成的尺度空間是標(biāo)準(zhǔn)的和現(xiàn)行的，而且滿足一下的假設(shè)干性質(zhì)：平移不變性、尺度不變性和旋轉(zhuǎn)不變性等等。WItkin對尺度空間理論最重要的奉獻(xiàn)之一就是把這些表達(dá)與信號在不同尺度上的結(jié)構(gòu)用系統(tǒng)方法關(guān)聯(lián)在一起，從而將尺度這個維度很自然的參加到尺度空間表達(dá)中，使得跨尺度圖像結(jié)構(gòu)的某些行為能夠被捕獲。[2,13]2.2.2高斯尺度空間SIFT算法是在不同的尺度空間上查找關(guān)鍵點，而尺度空間的獲取使用高斯模糊來實現(xiàn)，Lindeberg等人已證明高斯卷積核是實現(xiàn)尺度變換的唯一變換核，并且是唯一的線性核。本節(jié)先介紹高斯模糊算法。1.二維高斯函數(shù) 高斯模糊是一種圖像濾波過程。高斯模糊所用到的函數(shù)就是高斯函數(shù)〔正態(tài)分布〕計算模糊模板。使用該模板與原圖像進(jìn)行卷積運(yùn)算，并且得到一系列模糊圖像。N維空間高斯函數(shù)方程為：(2-1)其中，是正態(tài)分布的標(biāo)準(zhǔn)差，值越大，圖像越模糊(平滑)。r為模糊半徑，模糊半徑是指模板元素到模板中心的距離。如二維模板大小為m*n，那么模板上的元素(x,y)對應(yīng)的高斯計算公式為：(2-2)在二維空間中，這個公式生成的曲面的等高線是從中心開始呈正態(tài)分布的同心圓，如圖2.1所示。高斯函數(shù)是圓對稱的分布不為零的像素組成的卷積矩陣與原始圖像做變換。每個像素的值都是周圍相鄰像素值的加權(quán)平均。原始像素的值有最大的高斯分布值，所以有最大的權(quán)重，相鄰像素隨著距離原始像素越來越遠(yuǎn)，其權(quán)重也越來越小。這樣進(jìn)行模糊處理比其它的均衡模糊濾波器更高地保存了邊緣效果。圖2.1理論上來講，圖像中每點的分布都不為零，這也就是說每個像素的計算都需要包含整幅圖像。在實際應(yīng)用中，在計算高斯函數(shù)的離散近似時，在大概3σ距離之外的像素都可以看作不起作用，這些像素的計算也就可以忽略。通常，圖像處理程序只需要計算(+1)*(+1)的矩陣就可以保證相關(guān)像素影響。2.圖像的二維高斯模糊根據(jù)σ的值，計算出高斯模板矩陣的大小(+1)*(+1)，使用公式(1-2)計算高斯模板矩陣的值，與原圖像做卷積，即可獲得原圖像的平滑(高斯模糊)圖像。為了確保模板矩陣中的元素在[0,1]之間，需將模板矩陣歸一化。5*5的高斯模板如表2.1所示。表2-1下列圖是5*5的高斯模板卷積計算示意圖。高斯模板是中心對稱的。圖2.33.尺度空間理論以及高斯金字塔的構(gòu)建尺度空間〔scalespace〕理論早在1962年被Iijima提出了以后，Witkin和Koenderink等人的推廣下，漸漸得到了眾多人們的關(guān)注，后來在計算機(jī)視覺領(lǐng)域內(nèi)被廣泛使用。尺度空間理論的根本思想是在圖像信息處理領(lǐng)域里引入一個參數(shù)〔我們稱之為尺度〕，通過聯(lián)系變化的尺度參數(shù)獲取多尺度下的空間序列，并對這些已獲取的序列進(jìn)行輪廓的提取，以該輪廓作為一個特征向量，實現(xiàn)角點、邊緣檢測以及不同分辨率上的特征提取等。尺度空間方法改變了傳統(tǒng)的單尺度圖像處理技術(shù)，進(jìn)一步實現(xiàn)了尺度連續(xù)變化的圖像動態(tài)分析框架。尺度是自然存在的，不是認(rèn)為創(chuàng)造的，高斯尺度空間只是表現(xiàn)尺度空間的一種形式。這樣，能夠更容易獲得原圖像的本質(zhì)特征。尺度空間中各尺度圖像的模糊程度逐漸變大，能夠模擬人在距離目標(biāo)由近到遠(yuǎn)時候的目標(biāo)在視網(wǎng)膜上的過程。尺度空間要滿足對圖像的分析和圖像的位置、大小、角度以及仿射變換無關(guān)，也就是說要滿足平移不變性、歐幾里得不變性、尺度不變性和仿射不變性?？偟膩碚f，要滿足視覺不變性。視覺不變性的解釋如下：比方拿我們?nèi)祟愃鶕碛械囊曈X系統(tǒng)解釋。當(dāng)我們用眼睛觀察一個物體的時候，假設(shè)物體所處的背景的光照變化了，我們的視網(wǎng)膜上形成的圖像的比照度和亮度水平就變了，而且我們和物體之間的距離變化的時候，在我們的視網(wǎng)膜上形成的圖像信息不同的，就是說我們的視網(wǎng)膜上形成的圖像的位置、大小、形狀以及角度是不同的。所以，我們所要利用的尺度空間要克服這些變化，總體來說要滿足尺度不變性、歐幾里得不變性、平移不變性以及仿射不變性。下面我們來看尺度空間如何表示.一幅圖像的尺度空間，定義為具有一個變化尺度的高斯函數(shù)與原圖像I(x,y)的卷積。即*。*表示卷積。上面的公式(2-3)下面的公式(2-4)X,y所指的是原圖像的每個點的像素值，也就是說在圖像坐標(biāo)的坐標(biāo)值。指的是尺度空間參數(shù)。值越小表示圖像被平滑的越少，相應(yīng)的尺度也就越小。大尺度對應(yīng)于圖像的概貌特征，小尺度對應(yīng)于圖像的細(xì)節(jié)特征。m，n表示高斯模板的維度。接下來要構(gòu)建金字塔，第一步首先利用上述的公式對原圖像進(jìn)行多尺度的高斯模糊，第二部再進(jìn)行采樣后得到一系列多尺度下的高斯金字塔。圖2.4如同上面的圖，可以看出所謂的金字塔模型就是對原圖像進(jìn)行降采樣，從大到小，從下到上，把采樣得到的圖像序列排列的。每個金字塔模型里有n層，第一層就是原圖像。金字塔的層數(shù)根據(jù)所用到的原圖像的大小以及最上面的圖像大小來決定。而且看圖片就可以不難發(fā)現(xiàn)每次濾波的尺度參數(shù)值就是前一個參數(shù)值的兩倍，而每次采樣時候我們采納了降采樣，就是個點采樣一次。所以大小隨著層次的上升就橫向縱向各取1/2采樣。2.4關(guān)鍵點檢測在這節(jié)里需要定義尺度空間，這尺度空間叫DoG尺度空間。在上述的內(nèi)容中提到了用函數(shù)表示了圖像的尺度空間。它是多尺度的高斯函數(shù)和原圖像卷積后得到的。DoG尺度空間的定義如下：K為響亮的兩個尺度空間倍數(shù)的常數(shù)。DoG在計算上相鄰圖像高斯平滑后的圖像詳見，可見簡化了計算。圖2.5這樣獲取的一系列高斯差分圖像是DoG尺度空間。我們只要看出圖像上的像素點變化情況就可以了，也就是說如果像素值變了就說明那個像素點和其領(lǐng)域內(nèi)存在特征點，如果沒有發(fā)生什么變化，那就說明沒有特征點。這樣找出的特征點連起來，往往都是我們所關(guān)心的目標(biāo)的主輪廓。下面的圖告訴我們DoG尺度空間所表達(dá)的信息以及其效果。從下面的一系列DoG圖像來看我們通過DoG空間，能夠獲取目標(biāo)的〔我們所關(guān)心的物體〕重要信息，比方輪廓。使用DoG對LoG金絲帶來的好處是顯而易見的。第一是LoG需要使用兩個方向的高斯二維微分卷積核，而DoG直接使用高斯卷積核，省去了對卷積核的生成的運(yùn)算量；第二是DoG保存了哥哥高斯尺度空間的圖像，這樣，在省城某以空間尺度的特征時候，可以直接使用產(chǎn)生的尺度空間圖像，而無需要重新再次聲稱該尺度的圖像；第三是作為LoG的近似和簡化，DoG具有與LoG相同的性質(zhì)，而且檢測特征點檢測更加穩(wěn)定。[2,81]圖2.6嚴(yán)密的來說，DoG尺度空間也是金字塔，原因很簡單。DoG尺度空間是從LoG尺度空間金字塔模型中獲取的。將圖像金字塔共分O組〔Octave〕，每組共有S層〔Level〕，下一組的圖像由上一組圖像按照隔點降采樣得到，這樣做的目的是為了減少卷積運(yùn)算的工作量。[2,81]圖2.7SIFT特征點空間生成示意圖上面的圖像就是高斯金字塔與DoG的獲取過程。高斯金字塔的第一組圖片中相鄰的圖像相減得到了對應(yīng)組的DoG空間第一組，要注意的是，這時候因計算的關(guān)系少了一個層次，也就是說高斯金字塔第一組里面共有五幅圖像，到DoG空間金字塔第一組里面變成了四幅圖像。第二組也是這樣得出的。以此類推，能夠得到高斯金字塔對應(yīng)的DoG圖像金字塔。[2,81]特征點的檢測是通過同一組內(nèi)各DoG相鄰層之間比擬完成的。[2,84]為了尋找尺度空間的極值點〔極大值和極小值〕，每個點〔這兒的“點〞就是采樣的點〕必須和它所在的層面上的8個領(lǐng)域點、相鄰的兩個層面上各取18個點，也就是說，要和相鄰的26個相鄰點進(jìn)行比擬，確定是否極值點。所以，要進(jìn)行比擬的領(lǐng)域點形成了3*3*3的立方體領(lǐng)域。這樣獲取的極值點并不是真正意義上的極值點，原因是所得到的極值點畢竟是采樣點，所以我們得到的極值點附近肯定存在連續(xù)圖像上的極值點。我們要用插值的方法進(jìn)行曲線擬合，并且要找到這極值點作為特征利用。利用的離散空間點插值得到連續(xù)空間極值點的方法叫做子像元插值方法。在這兒我們需要利用三元二次函數(shù)來擬合完成插值得到連續(xù)的函數(shù)，然后根據(jù)已得到的極值點來確定真正意義上的極值點。這樣就很正確的定位特征點的位置。2.5特征點方向確定以及SIFT特征向量的生成通過上面表達(dá)的一系列過程，得到特征點以后，需要給每個特征點賦予其方向，所謂的方向所指的是該特征點的方向參數(shù)。特征點方向確實定是一個不可缺少的一個極其重要的環(huán)節(jié)。因為要知道特征點的方向，就可以在后續(xù)的匹配過程中容易找到對應(yīng)的匹配點〔也可以是對象〕。這樣得出來的描述子就可以具備旋轉(zhuǎn)不變性。描述的目的是在關(guān)鍵點〔特征點〕計算后，用一組向量將這個關(guān)鍵點〔特征點〕描述出來，這個描述子不但包括關(guān)鍵點〔特征點〕，也包括關(guān)鍵點〔特征點〕周圍對其有奉獻(xiàn)的像素點。用來作為目標(biāo)匹配的依據(jù)，也可使關(guān)鍵點〔特征點〕具有更多的不變性，如光照變化、3D視點變化等。描述的思路：通過對關(guān)鍵點周圍圖像區(qū)域分塊，計算塊內(nèi)梯度直方圖，生成具有獨特性的向量，這個向量是該區(qū)域圖像信息的一種抽象，具有唯一性。下面的兩個式就是〔x，y〕點地圖的模值和角度〔方向〕。(2.5)(2.6)對每個特征點，利用上面兩個式進(jìn)行計算以后，再用直方圖對該特征點領(lǐng)域內(nèi)所有點的梯度方向進(jìn)行統(tǒng)計。梯度直方圖范圍為0~360度，我們每10度一個柱來表示直方圖，那就一共36個柱來表示了。主方向，也就是其主峰值對應(yīng)的方向。峰值大小為主峰值的百分之八十的就是該特征點對應(yīng)的輔方向。完了上面的整個過程以后，需要生成特征描述符。圖2.88個方向直方圖以及SIFT算法描述子生成示意圖上面是示意圖，首先取8*8大小的領(lǐng)域進(jìn)行統(tǒng)計，然后四個個4*4大小的領(lǐng)域里進(jìn)行統(tǒng)計，然后從這已經(jīng)統(tǒng)計好的四個資料再次進(jìn)行統(tǒng)計，最后得到該特征點〔關(guān)鍵點〕的直方圖。其中峰值最高的就是該關(guān)鍵點〔特征點〕的主方向〔第五個柱〕，而第二個正是需要的輔方向。這樣得到了關(guān)鍵點〔特征點〕的維數(shù)為128維，因為每個點具有8個方向信息，那么每個特征點就對應(yīng)著128維的向量。這樣獲得的向量就是對應(yīng)特征點的SIFT特征向量。為了提高匹配的穩(wěn)定性，Lowe建議對每個關(guān)鍵點使用4*4共16個種子來描述，這樣對于一個關(guān)鍵點就可以產(chǎn)生128維的數(shù)據(jù)，及最終形成128維的SIFT特征向量。此時的SIFT特征向量已經(jīng)消除掉了尺度變化、旋轉(zhuǎn)變化等幾何變形因素的影響，并具備了穩(wěn)定性、獨特性以及各種不變性〔尺度不變性、旋轉(zhuǎn)不變性等〕。接下來我們要采用特征點特征向量的歐氏距離來作為兩幅待匹配的圖像中特征點〔關(guān)鍵點〕的相似性進(jìn)行比擬。從左攝像機(jī)拍到的圖像中取某個特征點，并找出有攝像機(jī)拍下來的圖像中歐氏距離最近的前兩個特征點。在這兩個特征點中，如果最近的距離出一次近的距離小于某個比例閾值，那么接受這一對匹配點。如果我們把這閾值設(shè)成小一點，就不難想象，SIFT特征匹配點數(shù)目就會減少，但是其穩(wěn)定性很高。下一步要進(jìn)行匹配，具體的匹配方法在一節(jié)中詳細(xì)介紹。2.6SIFT特征點匹配從左右兩個攝像頭拍攝下來的兩幅圖像中，各取各圖片的SIFT特征點后，我們要進(jìn)行粗匹配。說道粗匹配，其實已經(jīng)表達(dá)過，在上一節(jié)內(nèi)容中提到過用BBF搜索法〔雖然在上述的內(nèi)容中沒有這么叫，但嚴(yán)格的說是BBF搜索法〕確定粗匹配對。但是，這些粗匹配對中正確地匹配也有，錯誤的匹配也存在。只靠最近鄰次近鄰距離比法確定粗匹配關(guān)系是可以的，而且已經(jīng)有很多經(jīng)典算法問世以后被廣泛利用著。但是，用這些經(jīng)典算法來得出來的匹配對在后續(xù)的精確匹配工作中會受到很多障礙，因為后續(xù)的精確匹配工作中被利用的算法是RANSAC算法。那么有什么經(jīng)典的算法、具體的BBF搜索法來得出的粗匹配集到底是什么樣以及為什么要利用RANSAC算法，我們就一個一個地來看看。2.6.1BBF搜索法當(dāng)進(jìn)行特征點粗匹配的時候，Lowe采用了基于特征點最近鄰次近鄰距離比的BBF〔BestBinFirst〕搜索算法。對特征點集進(jìn)行各種計算的時候，常常會用到窮盡搜索、分層搜索、牛頓法、最速下降法、動態(tài)規(guī)劃法、遺傳算法、方向加速發(fā)和神經(jīng)網(wǎng)絡(luò)等。2.6.2最近鄰次近鄰距離比首先定義兩個特征點特征向量之間的歐氏距離為兩個特征點之間的距離。從兩幅〔左右攝像機(jī)同步拍下來的〕圖像中各取SIFT特征點，這時候兩幅圖像各取的SIFT特征點數(shù)不一樣，這是因為左右兩個攝像機(jī)的內(nèi)外參數(shù)不一樣，比方焦距和畸形變形等。從左圖的特征點集中取個特征點，然后計算該點和右圖的每個特征點之間的距離，再次從左圖特征點集〔特征向量〕中取個特征點反復(fù)上次的計算，這樣計算下來得到一系列計算值。根據(jù)左右特征點之間的距離值，從小到大排序。然后選擇最小值和次小值，選擇完了這兩個距離值，我們進(jìn)行計算這兩個值之間的比值。如果比值大于已定好的閾值，就排除掉，如果小于閾值我們就認(rèn)為滿足這最近鄰次近鄰比的特征點視為左圖特征點對應(yīng)的右圖特征點，以此類推，我們得到了粗匹配集。當(dāng)然，這粗匹配集里存在錯匹配對。所以我們要用RANSAC算法精確提純數(shù)據(jù)并且計算正確地模型后，最后要進(jìn)行圖像配準(zhǔn)。最近鄰次近鄰比值范圍為從0到1之間。我們可以選取距離比閾值為0.8，也就是如果比值比0.8大的時候，我們拒絕該匹配對，如果小于0.8我們視為正確地匹配對。如果我們選取更小的最近鄰次近鄰比值，比方0.5，或者更小，這時候我們最終得到的匹配對中正確地匹配對占比很高，而且這時候正確匹配的損失也不多，這樣一來，保存的正確匹配〔還是存在錯誤的匹配點對，但是比例小了很多〕數(shù)目會少，不過，匹配對集變得更加穩(wěn)定。在實驗中證實了這理論，而且從實驗結(jié)果來得到一半選取0.3到0.6就可以到達(dá)我們所需要的精度。2.6.3RANSAC〔RANdomSAmpleConsensus〕算法所謂RANSAC〔RANdomSAmpleConsensus〕算法是隨機(jī)抽樣一致性。它是一種非常簡單而且被廣泛使用的算法，是由Fishler和Bolles最先提出的很好用的算法。下面簡單介紹RANSAC算法的一般原理。1)RANSAC算法的概述：輸入：包含很多局外點〔噪聲，感染?？梢钥闯刹贿m合正確模型的數(shù)據(jù)點〕的觀測數(shù)據(jù)。輸出：正確地模型〔或者個別參數(shù)〕或者模型參數(shù)。RANSAC理念很簡單就是首先隨機(jī)抽取觀測數(shù)據(jù)子集，我們假設(shè)視為這子集就是“內(nèi)點〞〔局內(nèi)點或者局內(nèi)數(shù)據(jù)〕。然后用這子集進(jìn)行相關(guān)的擬合來計算模型參數(shù)〔或者估計函數(shù)〕。找到這模型〔或者函數(shù)〕以后，利用觀測點〔數(shù)據(jù)〕進(jìn)行是否正確，如果求出來的模型能夠滿足足夠多的數(shù)據(jù)，我們視為很正確的數(shù)據(jù)。最后我們采納。但是，如果不適合，也就是說求出來的模型〔或者函數(shù)，也可以是模型參數(shù)〕滿足的數(shù)據(jù)點很少，我們就放棄，從新隨機(jī)抽取觀測數(shù)據(jù)子集，再進(jìn)行上述的操作。這樣的運(yùn)算進(jìn)行N次，然后進(jìn)行比擬，如果第M〔M<N〕次運(yùn)算求出來的模型滿足的觀測數(shù)據(jù)足夠多的話，我們視為最終正確的模型〔或者稱之為正確地擬合函數(shù)〕?？梢?，所謂的隨機(jī)抽樣一致性算法很適合對包含很多局外點〔噪聲，干擾等〕的觀測數(shù)據(jù)的擬合以及模型參數(shù)估計。當(dāng)然最小二乘法也是不錯的算法，但是，最小二乘法雖然功能強(qiáng)大，不過，它所適合的范圍沒有RANSAC那么廣。RANSAC算法具體偽代碼偽碼形式的算法如下所示：

輸入：

data：一組觀測數(shù)據(jù)

model：適應(yīng)于數(shù)據(jù)的模型

n：適用于模型的最少數(shù)據(jù)個數(shù)

k：算法的迭代次數(shù)

t：用于決定數(shù)據(jù)是否適應(yīng)于模型的閥值

d：判定模型是否適用于數(shù)據(jù)集的數(shù)據(jù)數(shù)目

輸出：

best_model：跟數(shù)據(jù)最匹配的模型參數(shù)〔如果沒有找到好的模型，返回null〕

best_consensus_set：估計出模型的數(shù)據(jù)點

best_error：跟數(shù)據(jù)相關(guān)的估計出的模型錯誤

//初始化

iterations=0

best_model=null

best_consensus_set=null

best_error=無窮大//進(jìn)行RANSAC算法

while(iterations<k)

maybe_inliers=從數(shù)據(jù)集中隨機(jī)選擇n個點

maybe_model=適合于maybe_inliers的模型參數(shù)

consensus_set=maybe_inliers

for(每個數(shù)據(jù)集中不屬于maybe_inliers的點〕

if(如果點適合于maybe_model，且錯誤小于t〕

將點添加到consensus_set

if〔consensus_set中的元素數(shù)目大于d〕

已經(jīng)找到了好的模型，現(xiàn)在測試該模型到底有多好

better_model=適合于consensus_set中所有點的模型參數(shù)

this_error=better_model究竟如何適合這些點的度量

if(this_error<best_error)

我們發(fā)現(xiàn)了比以前好的模型，保存該模型直到更好的模型出現(xiàn)

best_model=better_model

best_consensus_set=consensus_set

best_error=this_error

增加迭代次數(shù)

返回best_model,best_consensus_set,best_error

RANSAC算法的可能變化包括以下幾種：

〔1〕如果發(fā)現(xiàn)了一種足夠好的模型〔該模型有足夠小的錯誤率〕，那么跳出主循環(huán)。這樣可能會節(jié)約計算額外參數(shù)的時間。

〔2〕直接從maybe_model計算this_error，而不從consensus_set重新估計模型。這樣可能會節(jié)約比擬兩種模型錯誤的時間，但可能會對噪聲更敏感。

參數(shù)我們不得不根據(jù)特定的問題和數(shù)據(jù)集通過實驗來確定參數(shù)t和d。然而參數(shù)k〔迭代次數(shù)〕可以從理論結(jié)果推斷。當(dāng)我們從估計模型參數(shù)時，用p表示一些迭代過程中從數(shù)據(jù)集內(nèi)隨機(jī)選取出的點均為局內(nèi)點的概率；此時，結(jié)果模型很可能有用，因此p也表征了算法產(chǎn)生有用結(jié)果的概率。用w表示每次從數(shù)據(jù)集中選取一個局內(nèi)點的概率，如下式所示：

w=局內(nèi)點的數(shù)目/數(shù)據(jù)集的數(shù)目

通常情況下，我們事先并不知道w的值，但是可以給出一些魯棒的值。假設(shè)估計模型需要選定n個點，wn是所有n個點均為局內(nèi)點的概率；1?wn是n個點中至少有一個點為局外點的概率，此時說明我們從數(shù)據(jù)集中估計出了一個不好的模型。(1?wn)k表示算法永遠(yuǎn)都不會選擇到n個點均為局內(nèi)點的概率，它和1-p相同。因此，

1?p=(1?wn)k

我們對上式的兩邊取對數(shù)，得出

(2.7)

值得注意的是，這個結(jié)果假設(shè)n個點都是獨立選擇的；也就是說，某個點被選定之后，它可能會被后續(xù)的迭代過程重復(fù)選定到。這種方法通常都不合理，由此推導(dǎo)出的k值被看作是選取不重復(fù)點的上限。例如，要從上圖中的數(shù)據(jù)集尋找適合的直線，RANSAC算法通常在每次迭代時選取2個點，計算通過這兩點的直線maybe_model，要求這兩點必須唯一。

為了得到更可信的參數(shù)，標(biāo)準(zhǔn)偏差或它的乘積可以被加到k上。k的標(biāo)準(zhǔn)偏差定義為：

(2.8)4〕RANSAC算法的優(yōu)點與缺點RANSAC的優(yōu)點是它能魯棒地估計模型參數(shù)。例如，它能從包含大量局外點的數(shù)據(jù)集中估計出高精度的參數(shù)。RANSAC的缺點是它計算參數(shù)的迭代次數(shù)沒有上限；如果設(shè)置迭代次數(shù)的上限，得到的結(jié)果可能不是最優(yōu)的結(jié)果，甚至可能得到錯誤的結(jié)果。RANSAC只有一定的概率得到可信的模型，概率與迭代次數(shù)成正比。RANSAC的另一個缺點是它要求設(shè)置跟問題相關(guān)的閥值。

RANSAC只能從特定的數(shù)據(jù)集中估計出一個模型，如果存在兩個〔或多個〕模型，RANSAC不能找到別的模型。例子左圖為包含局外點的數(shù)據(jù)右圖為用RANSAC算法求出的模型內(nèi)點圖2.9RANSAC算法示意圖6)應(yīng)用方面它適合估計包含很多局外點的觀測數(shù)據(jù)的模型，魯棒性好。所以經(jīng)常在計算機(jī)視覺方面被廣泛利用，特別是圖像配準(zhǔn)和立體攝像機(jī)內(nèi)外參數(shù)估計。2.7本章小結(jié)本章里著重介紹了有關(guān)SIFT算法的原理以及提取，描述子的生成方法等。為后續(xù)的內(nèi)容奠定了根底。最后介紹了RANSAC算法的一般原理〔通用方法〕。第三章基于RANSAC算法的圖像拼接系統(tǒng)設(shè)計本章將介紹從左右兩個攝像頭中拍下來的圖片的無縫拼接過程，以及用OpenCV開源庫來設(shè)計拼接系統(tǒng)的時候所利用和改良的各種算法，以及遇到的困難和克服的方法。3.1對開源庫OpenCV的簡單的介紹本論文所采用的程序設(shè)計語言為VisualStudio2023和開源庫OpenCV2.3.1。OpenCV(OpenSourceComputerVisionLibrary)于1999年由Intel建立，如今由WillowGarage提供支持。OpenCV開源庫是一個基于〔開源〕發(fā)行的跨平臺計算機(jī)視覺庫，可以運(yùn)行在Linux、Windows和MacOS操作系統(tǒng)上。他輕量級而且高效由一系列C函數(shù)和少量C++雷構(gòu)成，同時提供了Python、Ruby、Matlab等語言的接口，實現(xiàn)了圖像處理和計算機(jī)視覺方面的很多同用算法。至今最新版本為2.4.5。OpenCV擁有包括300多個C函數(shù)的跨平臺和中、高層API，不依賴于其他的外部庫一一盡管也可以使用某些外部庫。OpenCV的歷史開展1999年1月，CVL工程啟動。主要目標(biāo)是人機(jī)界面，能被UI調(diào)用的實時計算機(jī)視覺庫，為Intel處理器做了特定優(yōu)化。2000年6月，第一個開源版本OpenCValpha3發(fā)布。2000年12月，針對linux平臺的OpenCVbeta1發(fā)布。期間，繼續(xù)各種研究。。。2006年，支持MacOS的OpenCV1.0發(fā)布。2023年9月，OpenCV1.2〔beta2.0〕發(fā)布。2023年10月1日，Version2.0發(fā)布。2023年12月6日，OpenCV2.2發(fā)布。2023年8月，OpenCV2.3發(fā)布。2023年4月2日，發(fā)布OpenCV2.4.OpenCV提供的視覺處理算法非常豐富，并且它局部以C語言編寫，加上其開源的特性，處理得當(dāng)，不需要添加新的外部支持也可以完整的編譯鏈接生成執(zhí)行程序，所以很多人用它來做算法的移植，OpenCV的代碼經(jīng)過適當(dāng)改寫可以正常的運(yùn)行在DSP系統(tǒng)和單片機(jī)系統(tǒng)中。而且對外開放的，也就是說非商業(yè)應(yīng)用和商業(yè)應(yīng)用都是免費的。3.2開發(fā)環(huán)境的搭建〔VS2023+OpenCV2.3.1〕第一步：解壓OpenCV2.3.1軟件包裝在D盤上。然后把軟件的路徑拷到電腦環(huán)境變量PATH里面。第二部：屬性頁下面的VC++里設(shè)置好包含目錄和庫目錄。就把OpenCV的lib文件夾 和include文件夾的路徑拷到里面去。圖3.1然后點擊鏈接器下面的輸入，然后再點擊右邊的附加依賴項，點擊最右邊的圖標(biāo)后出來的窗口中輸入OpenCV的.lib文件。這樣完成了VS2023和OpenCV2.3.1的搭建。圖3.23.3實時采集圖像本文所利用的攝像頭是兩個USB攝像頭。兩個攝像頭的像素數(shù)均為2MEGApixel。首先要設(shè)置禁用筆記本自帶的攝像頭，這樣能夠無錯誤的運(yùn)行兩個USB攝像頭。首先為了能夠?qū)崟r采集圖像我們需要聲明兩個CvCapture變量。利用cvCreateCameraCapture函數(shù)從攝像頭讀取每個幀信息。CvCapture*cap1；CvCapture*cap2；利用cvCreateCameraCapture函數(shù)從攝像頭讀取每個幀信息。然后需要從這些讀取的每次兩個幀轉(zhuǎn)換成兩個圖像處理有力的數(shù)據(jù)型。在OpenCV里Mat就是處理圖像的變量。Matframe1，frame2；然后利用cvQueryFrame函數(shù)從cap變量轉(zhuǎn)換成Mat變量，轉(zhuǎn)好了就顯示在屏幕上，這樣能夠知道是否正常運(yùn)行。3.4圖像變換模型〔矩陣〕從兩幅圖像的SIFT特征空間中找到包含少量局外點的觀測數(shù)據(jù)〔粗匹配的特征匹配對集〕中，我們要用變換模型來求出兩幅圖像之間的關(guān)系。因為兩個USB攝像頭的相對位置不同，也就是說他們在橫向有固定的距離，好比說人的兩個眼睛，所以從這兩個攝像頭拍下來的〔同步實時采集〕圖片中存在視差。也就是兩幅圖像各有共同區(qū)域。所以我們需要一個圖像利用變換矩陣變換到另一幅圖像坐標(biāo)下。這樣，我們能夠?qū)崿F(xiàn)統(tǒng)一視點下的圖像。下面來簡單介紹剛體變換、仿射變換和投影變換。3.4.1剛體變換矩陣圖像的大小跟圖像像素點位置關(guān)系都不變。這樣的變換矩陣如下所示：(3.1)其中是圖像旋轉(zhuǎn)的角度，h2和h5為平移量。這矩陣的自由度為3，理論上選擇至少兩隊點就可以確定H矩陣了。3.4.2仿射變換如果一幅圖像中的一條直線經(jīng)過變換后變換到另一幅圖像上，仍然是直線，而且保持平行關(guān)系，那么這樣的變換成為仿射變換，變換矩陣形式為如下：(3.2)如果一幅圖像中的一條直線經(jīng)過變換后變換到另一幅圖像上，仍然是直線，而且保持平行關(guān)系，那么這樣的變換成為仿射變換，變換矩陣形式為如下：看上面的矩陣形式就可以容易知道，這仿射變換矩陣有6個自由度。所以，理論上選擇至少三對不共線的控制點〔在本論文中為SIFT特征點〕就可以解出所有的參數(shù)。3.4.3投影變換從一個圖像平面到另外一個圖像平面的過程，我們稱為投影變換。變換矩陣為如下：(3.3)可見，上面的矩陣具有8個自由度。所以，我們選擇的時候，至少要選擇4對匹配對，這樣我們能夠求出H矩陣。3.5基于RANSAC的圖像拼接這一節(jié)著重介紹從左右攝像頭中讀取的兩幅圖像的拼接技術(shù)以及其實現(xiàn)過程。左右攝像頭每隔45ms采集一次，而且同步采集的。圖像拼接算法流程如下：右攝像頭左攝像頭右攝像頭左攝像頭圖像預(yù)處理圖像預(yù)處理圖像預(yù)處理圖像預(yù)處理SIFT特征點提取SIFT特征點提取SIFT特征點提取SIFT特征點提取進(jìn)行特征點匹配進(jìn)行特征點匹配獲取粗匹配后的獲取粗匹配后的特征點粗匹配對集利用利用RANSAC算法進(jìn)行透視矩陣參數(shù)估計利用求出來的透視矩陣進(jìn)行圖像配準(zhǔn)利用求出來的透視矩陣進(jìn)行圖像配準(zhǔn)圖3.3OpenCV提供了良好的通用算法。其中已經(jīng)有封裝好的SIFT特征點提取函數(shù)，我們通過上一節(jié)的理論內(nèi)容了解到了SIFT特征提取理論以及提取方法。在這兒不用在表達(dá)。下面通過簡單的代碼來看看已封裝好的SIFT特征點提取函數(shù)的利用方法以及內(nèi)部參數(shù)設(shè)置。利用OpenCV里面的cvtColor函數(shù)來對已采集的兩幅〔左右〕圖像進(jìn)行預(yù)處理，這兒的預(yù)處理就是把已經(jīng)讀入進(jìn)來的兩幅彩色圖像轉(zhuǎn)換成灰度圖。這時候三個通道色度的權(quán)值是默認(rèn)的，因為調(diào)整這些參數(shù)〔權(quán)值〕并不影響程序的速度以及最后結(jié)果。然后對兩幅灰度圖進(jìn)行SIFT特征點提取。這時候用SiftFeatureDetector類。首先聲明SiftFeatureDetector類的類變量。我們在這兒定為detector。用vector<KeyPoint>模板類，先聲明該類的變量。我們這兒聲明keypoint為該模板類的變量。然后用detector變量的成員函數(shù)detect來檢測第一幅和第二幅圖像的SIFT特征點。這樣我們就獲取了兩幅灰度圖的SIFT特征點集，而且各圖片的SIFT特征點存儲在keypoint1，keypoint2變量里面。在這兩個變量里頭的SIFT特征點數(shù)各不相同。因為左右攝像頭的內(nèi)外參數(shù)不同，而且他們所讀取的圖像中除了共同局部其他局部包含的SIFT特征點不一樣。用SiftDescriptorExtractor類，聲明extractor變量，然后利用其變量的成員函數(shù)compute進(jìn)行描述符的產(chǎn)生〔兩個圖像的描述字存儲在descriptor1，descriptor1里面〕。進(jìn)行了上面的編程過程以后，我們要對其進(jìn)行粗匹配。用BruteForceMatcher<L2<float>>模板類，聲明該類的變量為matcher。利用matcher變量的成員函數(shù)match進(jìn)行粗匹配。得到vector<DMatch>模板類變量matches。該變量存儲著兩個SIFT特征點集之間粗匹配后的狀態(tài)。它存儲著粗匹配后的粗匹配對數(shù)和具體對應(yīng)關(guān)系。圖3.4原圖像圖3.5圖像預(yù)處理后進(jìn)行SIFT特征點提取圖3.6SIFT特征點粗匹配為了提純數(shù)據(jù)，我們要利用OpenCV自帶的函數(shù)findFundamentalMat來進(jìn)行RANSAC提純操作。為了讓讀取粗匹配數(shù)據(jù)，首先要使用Point2f型變量Point1，Point2存儲matches里的粗匹配對信息。賦值過程進(jìn)行完了以后用上述的函數(shù)findFundamentalMat來進(jìn)行提純數(shù)據(jù)過程。這樣下來，我們就得到了vector<uchar>型變量m_ransacstatus，這變量里面以數(shù)組的形式存儲著提純數(shù)據(jù)過程以后〔過濾〕的匹配狀態(tài)。然后利用m_ransacstatus[i]的值，確認(rèn)是否可以利用在后續(xù)的程序。如果其動態(tài)為0表示外點，如果是1表示內(nèi)點。不過，這樣計算下來的最后匹配對里還存在錯誤匹配點。所以我們要用RANSAC算法進(jìn)行透視變換矩陣參數(shù)的估計。圖3.7RANSAC提純特征點后的匹配狀態(tài)〔還是存在少量錯誤匹配對〕RANSAC〔隨機(jī)抽樣一致性〕算法的具體的一般原理已經(jīng)在上述過。在這兒不用再表達(dá)。下面是本論文所設(shè)計的改良RANSAC算法流程圖。隨機(jī)抽取四對匹配點隨機(jī)抽取四對匹配點檢查是否存在任意的三個點共線檢查是否存在任意的三個點共線存在不存在利用四對匹配點的x，y坐標(biāo)建立8元1次線性方程組利用四對匹配點的x，y坐標(biāo)建立8元1次線性方程組利用高斯消元法對已建立的線性方程組求解。利用高斯消元法對已建立的線性方程組求解。用上面求出來的透視矩陣參數(shù)計算滿足其模型的匹配對數(shù)用上面求出來的透視矩陣參數(shù)計算滿足其模型的匹配對數(shù)圖3.8看上面的流程圖不難發(fā)現(xiàn)這樣計算出來的模型不一定很正確，所以，我們要進(jìn)行250次同樣的計算，這時候每次記錄每次計算出來的模型參數(shù)值以及對應(yīng)的內(nèi)點數(shù)。250次反復(fù)進(jìn)行以后根據(jù)滿足模型的內(nèi)點數(shù)來評估模型的好壞程度。顯然，滿足模型參數(shù)〔透視矩陣參數(shù)〕的內(nèi)點數(shù)最多的那一次的模型就是我們所期待的最好的模型。圖3.9用RANSAC算法后的圖像拼接用OpenCV來編程設(shè)計匹配系統(tǒng)的時候遇到過的問題以及解決的方法：確保建立的線性方程組系數(shù)矩陣的秩為8.隨機(jī)抽取四對匹配對后建立8元一次線性方程組。本人在本論文中所編程的求解線性方程組的方法為高斯消元方法。如果要能夠順利求解，要進(jìn)行檢查線性方程組系數(shù)矩陣的對角線的元素是否等于零。因為至少有一個主對角元素等于零，就會崩潰，因為計算機(jī)無法進(jìn)行除以零的計算。所以，本人在這問題上，為了能夠進(jìn)行求解，在理論上主對角線上等于零的行跟不為零的行進(jìn)行交換，這樣的交換對整個計算過程起不了什么作用，而且這樣求出來的解仍然不失一般性，符合要求的。拼接圖片中出現(xiàn)線條，還出現(xiàn)兩幅圖片的交界局部不融合拼接后結(jié)果圖中會出現(xiàn)線條，這不屬于圖片，是沒有找到最正確的模型而導(dǎo)致出現(xiàn)這樣的線條。這樣的錯誤可以優(yōu)化代碼來實現(xiàn)，而且已經(jīng)實現(xiàn)了。兩幅圖片中間可以看出交叉線，要想方法解決這錯誤，為了解決這問題，采取了加權(quán)平均法來進(jìn)行無縫拼接。所謂的無縫拼接無疑是進(jìn)行插值來消掉線條〔圖像變形而導(dǎo)致的〕。主要的插值方法有前向插值和后向插值。前向插值法是一個點的色度值映射在其映射點周圍四個點上，這樣就容易消掉線條等不均勻現(xiàn)象。但是，這樣的方法不能有效地實現(xiàn)光度的變化，因為兩個通用USB攝像頭中讀取的圖像都存在著顯眼的光度差異，也就是說攝像頭雖然型號一樣，但做不到他拍下來的圖像質(zhì)感一樣。所以，要采取加權(quán)平均算法來解決拼接后容易看出的縫條。3.6本章小結(jié) 本章里介紹了本論文最核心的兩幅實時采集的圖像的拼接以及配準(zhǔn)方法。還提出了其實現(xiàn)過程中遇到的問題以及解決方法。介紹了利用RANSAC算法估計透視矩陣參數(shù)的方法。最后著重介紹了本論文所采取的配準(zhǔn)方法。第四章基于OpenCV的攝像頭標(biāo)定以及測距針對雙目視頻圖像跟蹤系統(tǒng)研制過程中的攝像機(jī)標(biāo)定步驟，分析了計算機(jī)視覺函數(shù)庫OpenCV中的攝像機(jī)模型，其中的非線性畸變和徑向畸變，采用Bouguet角點提取算法，實現(xiàn)了基于OpenCV的攝像機(jī)標(biāo)定。該算法具有很高的標(biāo)定精度和計算效率、良好的跨平臺移植性，可以滿足雙目視頻跟蹤系統(tǒng)的需要。4.1攝像機(jī)標(biāo)定一般模型〔針孔相機(jī)模型〕說到雙攝像頭測距，首先要看看針孔相機(jī)模型測距原理。圖4.1.雙攝像頭模型俯視圖圖4.2,雙攝像頭模型立體視圖圖1解釋了雙攝像頭測距的原理，書中Z的公式如下：(4-1)(4-2)在OpenCV中，f的量綱是像素點，Tx的量綱由定標(biāo)棋盤格的實際尺寸和用戶輸入值確定，一般總是設(shè)成毫米，當(dāng)然為了精度提高也可以設(shè)置為0.1毫米量級，d=xl-xr的量綱也是像素點。因此分子分母約去，z的量綱與Tx相同。圖4.2解釋了雙攝像頭獲取空間中某點三維坐標(biāo)的原理?？臻g中某點的三維坐標(biāo)就是(X/W,Y/W,Z/W)。因此，為了精確地求得某個點在三維空間里的距離，我們需要獲得的參數(shù)有焦距f、視差d、攝像頭中心距Tx。如果還需要獲得X坐標(biāo)和Y坐標(biāo)的話，那么還需要額外知道左右像平面的坐標(biāo)系與立體坐標(biāo)系中原點的偏移Cx和Cy。其中f,Tx,cx和cy可以通過立體標(biāo)定獲得初始值，并通過立體校準(zhǔn)優(yōu)化，使得兩個攝像頭在數(shù)學(xué)上完全平行放置，并且左右攝像頭的cx,cy和f相同(也就是實現(xiàn)圖2中左右視圖完全平行對準(zhǔn)的理想形式)。而立體匹配所做的工作，就是在之前的根底上，求取最后一個變量：視差d(這個d一般需要到達(dá)亞像素精度)。從而最終完成求一個點三維坐標(biāo)所需要的準(zhǔn)備工作。在清楚了上述原理之后，我們也就知道了，所有的這幾步：標(biāo)定、校準(zhǔn)和匹配，都是圍繞著如何更加精確獲得f、d、Tx、Cx、Cy而設(shè)計的。4.2基于OpenCV的測距原理用上面的理論進(jìn)行基于OpenCV攝像頭標(biāo)定。如果按照LearningOp