計算機視覺中,目前有哪些成熟的匹配定位演算法?
對於這樣任務氣息極其濃烈的問題,我就想……如果知乎有打賞功能就好了,但是它沒有……沒有也好,這樣即便是答飄了也不用覺得特別難為情……對吧,題主?
我是一個對實際問題十分感興趣的人,所以前幾天就關注了這個帖。當時瀏覽了一下幾個『答案』,覺得可能會有人出馬來Pia Ji一下,弄一個切中要害的答案,這樣我也可以從中學習一番。
其實我應該再等等的。
昨天下午從廁所回來的走廊上,遇到隊友安德魯,他從很遠的那頭下身僵硬腳步謹慎地往這邊走來,他今天不舒服,這讓我想起一個月前我拉肚子那次,差不多同樣的時間,他在我趕去廁所的路上攔住了我,一臉無辜地問了我個無聊的問題……於是我老早就對他露出笑臉,他想低頭矇混過去,我說嘿,安德魯,能問你一個問題嗎?他楞了一下,說當然。我說……其實當時並沒有想好問啥,我一味地沉浸在逮到復仇機會的喜悅里而沒能及時準備好問題。我說呃……給你兩張沒啥特徵帶來的紋理圖,大概有個旋轉平移再加上一些噪音,怎麼去做配准?他一聽慌了,問題有點抽象有點大,其實我就隨便亂說的,講出來也發現這並不是一個好問題,他吭哧了兩聲,看著廁所的方向,說,要不等一下再跟我討論,我瞥了一眼他的臉色,感覺不大妙,於是趕緊說當然……當然可以。
其實稍後我並沒有跟安德魯深入討論這個問題,相反這個猥瑣的復仇讓我想起這個關注了幾天的問題。既然想到了,又是安逸的周六,習慣性地寫點吧。
再不寫估計題主都忘了這事了。
幾個答案里都提到使用SIFT之類的特徵點,並且大都對特徵點的方法很有信心……這讓我想起八年前剛接觸視覺的我,帶我的好心博士大哥哥扔給我幾篇經典的論文讓我讀透,其中就包括SIFT和SURF。
那個時候什麼都不懂,一個詞一個詞的琢磨,論文上的論點也是一個一個的推敲證明。幾篇論文讀了兩三個月,博士大哥有些不滿,給我下了一個死期,讓給寫個PPT在周會上講一下。
當時我就是一個愣頭愣腦,硬著頭皮在實驗室打雜的大三生,每次參加周會都是坐在最後排最右邊的那個『愛國愛黨』的『黨』字下,強打著精神,看著遙遠的講台上推導著我完全看不懂的數學公式的博士大哥哥,搖搖欲睡。我是從不敢想自己站在那個講台上的樣子的,我覺得自己什麼都不知道,知道的又十分膚淺不足為外人道,你這突然讓我整個PPT出來,萬一白白浪費了大哥大姐們的時間……可如何是好?
沒辦法,不行就湊吧。
經過一本正經的考慮,我略微謹慎地找了兩個點:圖像的建模和尺度空間。大概是講了下圖像的成像原理,討論了一下將圖像以二維矩陣來建模的優缺點,另外一方面是講尺度空間是什麼,怎麼構造,為什麼用高斯核來構造,理論基礎是什麼。結束後博士大哥說很多東西大家都當作公理一樣直接用,沒必要講這麼細。我當時反駁,我說一方面是我自己沒有弄懂這些,另外一方面,我不是針對你,我是說在座的各位也都沒有弄懂……呵呵,我當然不可能這麼說。我跟大部分朋友一樣,慚愧地低下頭,細聲說『是,是,下次一定會注意的!』
題主你看,我跑偏了。
那麼,其實我想說的是,在遇到實際問題的時候,就要從實際出發,從真實環境真實數據出發,而不是說到配准就想到特徵點,說到特徵點就想到SIFT之類。這種當作公理一樣拿來用的方式是很可笑的,因為你拿著樣圖稍微端詳一下就能發現……如此對稱的,噪音嚴重的圖,這要用SIFT特徵點的話,在另外一張不同的圖裡,很可能就得不到穩定的匹配點。這樣的直覺,在理解了SIFT、SURF這類特徵點的實現之後,都是應該具……當然我不能這麼說,沒有關係,我們也可以用一些工具 (在Github上搜索Find-Object) 實際看看。
在題主這種工業環境下,通常對精確率的要求非常高,檢測特徵點,然後匹配成點對往往只是開始,通常點對裡面有很多錯誤的匹配,而且真實情況裡面應該允許一對多的情況,有了點對,接下來面臨的第一個問題就是怎麼寫一個好的RANSAC的演算法來提升準確率。
這裡插一句,眾多的圖像特徵中(點特徵,邊特徵,拓撲類特徵),點特徵有一個非常大優勢:受到圖像畸變的影響最小。但點在不同尺度下,也會有難處……比如圖像放大四倍,之前圖像上的一個黑點,現在變成了四個,所以一般點的匹配會涉及不同的尺度,怎麼找到匹配的尺度對匹配結果有很大的影響。邊特徵的一個優點是,其方向(orientation)特徵通常比較可靠。
回到RANSAC,RANSAC其實只是一個抽象的框架,在實際的應用裡面,幾乎總會加入先驗知識重新實現。比如題主的問題里,圖像之間的尺度變化是很小的,選中的bounding box的大小是提前知道的,所以選擇估算變換矩陣的最小點對集合的時候,就不要完全隨機了……比如你明知道當前的點對根本得不到正確的變換矩陣,就不用往下走了。這裡講究的地方很多,再說多就太細了……
如果我們最終沒有得到變換矩陣,怎麼辦?如果得到了一個變換矩陣,怎麼去驗證這個矩陣是準確的?如何衡量這個矩陣的優劣?如果這個矩陣是錯的,那麼可以直接扔掉,如果是對的,但是精確度差了點,有什麼辦法進一步提高精確度?
如果我們不用特徵點,就用圖像的原始數據去做align,能怎麼做?如果沒有尺度變化,也沒有旋轉,只有平移,那麼直接去sliding window就可以找到,對吧。如果加上旋轉,該怎麼做?當然你可以把模板繞中心每一度旋轉一下,弄成180個模板,然後再去sliding window匹配,是不是就可以找到精確度為1度以內的解?如果再加上小範圍的尺度變化……發現原來最後整個問題變成了一個搜索問題,但是解空間太大了……傻傻地去遍歷的話,肯定太慢……怎麼辦?
怎麼辦,怎麼辦?(搖)
這就要說到數學優化了。學習計算機視覺並不是懂個opencv懂幾個特徵幾個經典演算法就夠了的,那些僅僅屬於技法,數學優化則是屬於心法,是區分老司機和嫩司機的分水嶺。這裡考慮到篇幅(主要是沒有打賞),我也不說太細了。
其實從一開始我就覺得在題主這類問題里,最終的系統是少不了優化這一步的。比如上面提到特徵點給出的變換矩陣不夠好,那麼可以用ICP來fine-tune一下。如果發現特徵點沒多少穩定的,可以用邊特徵,如果發現邊特徵比較容易受到運動模糊的影響,那用intensity也不是不可行的,因為你在尺度上變化不大,可以參考一下ESM(Efficient second-order minimization)中的優化方式,說不定結果就很不錯呢……
最後的系統可能包含SIFT、SURF這類經典特徵點,也可能包含邊,也可能包含online learning的一些特徵點,也可能會包含使用原始數據直接通過優化來做的方法,總之,多個臭皮匠,頂個諸葛亮(這裡僅僅是說工程實踐里的套路,並沒有暗指Boosting方法)。
看到這裡,題主,你可能明白,你這任務如果要做到精確度和準確率都很高,還是很有挑戰性的……我也只能幫到這了,你自己要加油。基於灰度的匹配一般被稱為模版匹配,直接以灰度進行匹配效果不好,對光照很敏感,所以一般會以灰度歸一化互相關(NCC)作為匹配依據,增強光照變化下的魯棒性,為了降低計算量,多採用圖像金字塔來實現先粗後精的方式加快匹配速度,匹配出像素位置後,會進一步做亞像素插值,使匹配出的位置達到更高的精度,處理旋轉和縮放也很直接,就是在限定的角度範圍和縮放比例內,取一定的步長生成多張模版,一一進行匹配。模版匹配處理遮擋比較困難,對光照變化想當敏感,如果有遮擋,一般情況下就不好使了。
基於特徵的匹配一般稱為圖像配准,這方面的論文很多很多,當然現在的已不是研究熱點,至少二維的情況是這樣,三維以及高維的間或會冒出來那麼一兩篇。基於特徵的匹配,就如你所寫的那樣,提取特徵點,用演算法迭代求出相互匹配的特徵,求出這些匹配特徵點之間的變換關係。處理旋轉縮放也很直接,選用具有仿射或投影不變性的特徵即可。基於特徵的匹配,對光照不太敏感,也可以一定程度上處理遮擋,提速和提高精度的方法和模版匹配里提到的基本相同,當然如果圖像中提取不到足夠多的特徵點的話,這個方法就很難奏效了。
還有匹配方法是基於幾何形狀信息,就是提取模版中的邊緣和梯度,梯度方向等圖像高頻的部分,作為匹配的依據,對抗旋轉縮放,提速,提高精度也和上面的類似。這一部分完整公開可用的代碼很少,幾乎沒有,opencv里也沒涉及,但這個演算法被絕大多數商業庫採用,因為它可以在光照變化,形變以及遮擋的情況下達到很高的魯棒性。
樓主可以看一下主流的商業機器視覺庫,比如Halcon,康耐視的VisionPro及它的PatMax專利演算法,OpeneVision里的Match和Find模塊,這些商業庫里的匹配演算法都佔有很高的篇幅和重要性,而它們的魯棒性也不是一般演算法可以比擬的。
再推薦給你一本書,機器視覺演算法及應用,是Halcon的資深研發人員寫的,有一章,模版匹配,里有介紹Halcon里實現的匹配演算法的實現原理。
如果有人有這方面的資料和代碼,歡迎交流和分享。
- SIFT演算法實時性能不好(除非去掉尺度不變性),你對性能有要求,最好使用ORB,FREAK等特徵速度快,效果也不錯。當然需要根據你的實際情況多測試一下對參數的調整。匹配完畢後要用RANSAC或者PROSAC進行篩選。對於特徵比較好的圖一般都可以得到不錯的結果。
- 對於你給出的例子,圖像噪點較多感覺特徵點的質量不好保證。可以考慮一下其他辦法比如以下:
- 有較多特徵,但是噪點比較大的可以想辦法去除一下噪點(比如小範圍高斯模糊,參數要多次試驗)。另外在小尺度上進行匹配也可能會很大程度上提高效果。
- 如果沒有什麼特徵(比如最後那一組圖),使用上面的估計就沒什麼效果了。這種情況下如果待匹配圖和原圖相比,Pose變化不大,可以參考ESM ,Linear Predictor之類的方式採用整體圖像作為模版。
- 在4的基礎上,如果Pose變化較大但是還有規律。比如匹配圖只會圍繞某一個軸旋轉,可以加入多次訓練,針對這個規律訓練不同的原圖去匹配,最終把所有結果中最好的選出來。
- 在5的基礎上,如果Pose變化較大還沒規律。但是圖中只有待檢測目標。沒有無關背景圖案干擾(看你的圖都是白色背景)。可以對原圖進行大量隨機Pose訓練,然後訓練圖和待匹配圖提取bounding box後,使用上面的ESM或者最簡單的SSD NCC匹配,選取結果最好的。
- 個人也是入門級,一些想法,不一定對。
謝謝邀請,這是我第一次在知乎回答問題。
目前在計算機視覺領域,匹配定位的演算法有很多,如果一一列出的話恐怕我的水平還達不到。所以我只給您推薦一種演算法,即OpenCV官方提出的「解決方案」:Features2D + Homography to find a known object。地址:Features2D + Homography to find a known object。該方案先用SURF來提取特徵點然後用FLANN進行匹配,過濾出足夠好的匹配點之後,用一個矩形來定位出被探測的物體。如下圖:
順便一提,如果如果您已經嘗試過SIFT和SURF,那麼我想您一定對ORB特徵提取演算法不陌生。它的性能較前兩者更優,還完全免費。論文地址:http://www.willowgarage.com/sites/default/files/orb_final.pdf。所以推薦您用ORB特徵提取演算法來代替SIFT和SURF,之後再用前文提到的Homography的方法進行定位。正如c++ - Algorithm improvement for Coca-Cola can shape recognition所提到的。
希望簡略的回答能讓您滿意,如果有什麼問題歡迎聯繫我一起探討,我也正在用OpenCV做相關項目。也希望我的回答能夠拋磚引玉,招引專業的大神來指點。
教研室有師姐是做草圖檢索的,剛發了tip導師前陣子過來和我們聊天的時候,就談到如果碰到零配件檢索的時候,可以考慮都簡化為草圖之後再進行處理,可能會有特殊的效果。不過現在草圖檢索方面,旋轉還是個難點,似乎還沒有看到特別好的解決方案
在實際的工程應用中很少採用基於特徵點的方法。因為這樣做很不穩定,容易錯誤匹配,而且定位的精度也不高。在商業的視覺軟體中,halcon的shape-based match和cognex的patmax演算法可以滿足你的需要,他們都是輪廓匹配演算法,可以抗旋轉、縮放和部分遮擋而且精度是亞像素。但是只能定位兩個方向的平移和旋轉,典型應用是工業中傳送帶上物體的抓放定位。halcon的輪廓匹配演算法是通過邊緣的梯度方向和梯度值計算匹配度,根據設定的旋轉步長和縮放係數預先建立各個角度和縮放比例下的模板,是一種窮舉方法,因此如果寫的不好演算法是十分耗時的。二值化, 最小外包四邊形, 求一個euclidean transform。估計都對齊了。
如果精度有更高的要求,在初對齊之後,在加限制條件(比如配準的點距離要小於一定閾值)做一些特徵匹配,來個二次配准。 加了這些限制條件之後,誤匹配大體都會被剔除。精度應該也會不錯了。
至於特徵點用什麼,魯棒估計是ransac 還是 weight median。其實工程中最好的方法就是試一遍。
「」有介紹Halcon里實現的匹配演算法的實現原理。「請百度 geomatch,在codeproject上有halcon原作者的文章,opencv實現。
看著挺熱鬧,我也來說下。直接利用,特徵點匹配,應該不太好用。因為你紋理信息不太豐富,匹配的時候會出現錯誤的匹配點。建議,先用邊緣進行下處理,去除光照影響,再利用圖像金字塔加hu矩進行搜索匹配。
1. 特徵點的檢測和具體的圖像密切相關,直接套用已有的方法可能會出問題。可能需要花時間多進行參數的調試。2. 不同類型的圖像使用同一方法可能效果不佳。第一組圖像應該好做一點,第二組和第三組圖像特徵點不明顯。3. 如果僅僅是剛體變換(平移+旋轉),後面兩組圖像可以考慮使用基於灰度的配準的方法。二維圖像旋轉和平移的搜索應該是可以承受的,相似度函數可以考慮對光照不敏感的normalized gradient field。但是如果有遮擋,這個方法不好用。4.第二組圖像還可以考慮hough變換。
你給出的例子,sift+ransac足夠了。你說的問題主要是沒有去除outlier造成的。如果追求速度,freak,orb什麼的問題應該也不大
GHT如何匹配定位,求指導。我只知道hough變換原理,不知道怎麼用來求平移、旋轉。求文獻推薦
我記得有fast match,siftflow,有源碼(patchmatch忘了是否是)
樓主,你這個項目其實更適合用其他方法來解決,比如先通過找圓定位工件的圓心,再通過找線等一些相對位置關係來做定位,想通過編寫通用的模板匹配恐怕不合適,難度不是一個等級的
OpenCV3中reg模塊,注意該模塊不在主倉庫中,而在contrib倉庫下。http://docs.opencv.org/3.1.0/db/d61/group__reg.html可參考例子example_reg_map_test演示了cv::reg模塊中5種Mapper(皆為基於像素的方法,同時還支持金字塔計算)的使用方法. 同時演示cv::features2d和cv::xfeatures2d中的基於特徵的方法, 並與基於像素方法進行了對比.
Feature based methods have some advantages over pixel based methods when we are trying to register pictures that have been shoot under different lighting conditions or exposition times, or when the images overlap only partially. On the other hand, the main advantage of pixel-based methods when compared to feature based methods is their better precision for some pictures (those shoot under similar lighting conditions and that have a significative overlap), due to the fact that we are using all the information available in the image, which allows us to achieve subpixel accuracy. This is particularly important for certain applications like multi-frame denoising or super-resolution.
圖像配准兩種方法:1.基於像素的方法;2.基於特徵的方法. 基於像素的方法可以充分用圖像信息,在某些圖像上可以獲得更高的甚至是亞像素級別的精度,如多幀去噪,超解析度等應用; 基於特徵的方法優勢是對於光照條件不敏感, 可用於重疊區域較少的圖像.
In fact, pixel and feature registration methods can complement each other: an application could first obtain a coarse registration using features and then refine the registration using a pixel based method on the overlapping area of the images. The code developed allows this use case.
兩種方法可以混合使用: 先通過基於特徵的方法進行粗配准; 然後通過基於像素的方法在重疊區域進行精配准. cv::reg支持此種情況.
這個東西,根本就不是特徵點匹配方面的原理去實現的。是應用了梯度信息,但要怎麼組織特徵,需要動腦筋,本人也在做這個演算法,但實時性很差這種問題根本不能使sift
不如自己寫靠譜規則圖像的雷同區域太多 在形狀和大體位置已知的前提下 可以考慮用特徵點的相對位置進行篩選 比如分成3x3 9x9的區域
另外可以嘗試對圖形轉換成邊緣圖像後再尋找特徵點,甚至可以考慮HSV等色彩空間轉換後選取其中一個通道進行
演算法大家都差不多,怎麼使用就是不停的試,試演算法組合,試參數值大小。
我是做人像磨皮的,以前曾經做過stitch,歡迎大家互相探討
可以考慮基於形狀的匹配,例如chamfer matching 及它的variant。
不知道你的應用場景是什麼,但是總得來說,都是兩幅圖的對應點來計算一個矩陣。計算時間主要花在:1.提取特徵點,2.特徵點匹配(含去除outliers)。如果是自然場景,那用SIFT之類的,但是根據我的經驗應該是比較慢的。如果是在VR/AR環境中用的話,一般用的是marker來定位。比如ARToolKitPlus
sift/surf+flann+ransac,一般情況都好使。實時性的話,要看你的要求
金字塔匹配-SPM
推薦閱讀:
※人工智慧未來會最先在哪個領域實現應用?
※如何通過人工神經網路實現圖像識別?
※單目SLAM在移動端應用的實現難點有哪些?
※到日本東大讀修士,然後再申請到美國top10的PHD可行么?
※orb-slam在眾多SLAM方法中處於怎樣的地位?