我估摸著這個應該是關于形狀匹配或者模版匹配的最后一篇文章了，其實大概是2個多月前這些東西都已經弄完了，只是一直靜不下來心整理文章，提醒一點，這篇文章后續可能會有多次修改（但不會重新發文章，而是在后臺直接修改或者增加），所以有需要的朋友可以隨時重復查看，
這次帶來的更新也是革命性和帶有建設性的，使得該演算法向工程化更加邁進了一步，不過嚴格意義上說和halcon還是有較大的差距的，
能夠帶來這次的變化和提升，其實也得益于偶爾的一次交流，一個微信好友給我發了一份可以不用配置就可以運行的linemod的代碼，因為可以運行，我就有興趣看其代碼的細節，也從中得到了更多的靈感，用于我自己的工程，從這個事情可以得出兩個小經驗：一個是要多交流，二是一個事情如果當前搞不定，不要一直搞，要有準備的等，說不定哪天就有意外的識訓， 就好似我們掉了一個東西，怎么找都找不到，但是有可能突然某一天他就冒出來了，
好，言歸正傳，后續的文字也不講究就邏輯性，想到啥說啥，
一、還是打擊下linemod的速度
linemod的程序包含了原圖的（被查找圖，也許很大）梯度角度量化（QuantizedOrientations）、計算回應圖（IM_ComputeResponseMaps）、梯度擴散等等程序，這些程序，就是使用特殊的指令集進行優化，對于稍微大一點的圖來說，也是相當耗時的，所以對于快速的目標識別來說linemod應該不是很好的方法，
另外，linemod的代碼里雖然有金字塔，但是他只是對特征方面用了金字塔，在旋轉角度上他確沒有進行下采樣，也就是說，如果底層金字塔有100個旋轉角度，第二層還是100個，第三個也還是100個，以此類對，而不是每層也減半的策略，這個可以從他的addTemplate含數里能看到細節，
二、從linemod中學到一些非常有用的東西，
1、創建模型時，直接旋轉0角度時識別的特征作為其他角度的特征，而非旋轉影像，然后在識別特征，
在前面所有的文章中，我們創建模型的時候，都是采用的先旋轉模版影像，然后再計算特征，并把這些特征保存起來，這樣做，可以解決問題，但是帶來了兩個大的麻煩：首先是創建模型的速度會有影響，特備是對于稍微大一點的模版圖，耗時非常嚇人，對于形狀匹配來說，是有不少場景的模版圖特別大的，甚至占到了被查找圖的一半以上的，這種情況，早期的方案基本就不能解決問題， 第二個麻煩是，我們存盤這些特征也會占用大量的記憶體，同樣對于大模版圖，存在記憶體不夠的風險，
這個問題其實很多寫模版匹配的朋友都有遇到過，而且早期我也沒有好的解決方案，曾經嘗試過旋轉特征，不過不知道為什么當時得到的結果總是有問題，
那么在linemod里我們發現這樣一段代碼：
int Detector::addTemplate_rotate(const string& class_id, int zero_id, float theta, cv::Point2f center) { std::vector<TemplatePyramid>& template_pyramids = class_templates[class_id]; int template_id = static_cast<int>(template_pyramids.size()); const auto& to_rotate_tp = template_pyramids[zero_id]; TemplatePyramid tp; tp.resize(pyramid_levels); for (int l = 0; l < pyramid_levels; ++l) { if (l > 0) center /= 2; for (auto& f : to_rotate_tp[l].features) { Point2f p; p.x = f.x + to_rotate_tp[l].tl_x; p.y = f.y + to_rotate_tp[l].tl_y; Point2f p_rot = rotatePoint(p, center, -theta / 180 * CV_PI); Feature f_new; f_new.x = int(p_rot.x + 0.5f); f_new.y = int(p_rot.y + 0.5f); f_new.theta = f.theta - theta; while (f_new.theta > 360) f_new.theta -= 360; while (f_new.theta < 0) f_new.theta += 360; f_new.label = int(f_new.theta * 16 / 360 + 0.5f); f_new.label &= 7; tp[l].features.push_back(f_new); } tp[l].pyramid_level = l; } cropTemplates(tp); template_pyramids.push_back(tp); return template_id; }
其中rotatePoint相關函式如下：
static cv::Point2f rotate2d(const cv::Point2f inPoint, const double angRad) { cv::Point2f outPoint; //CW rotation outPoint.x = std::cos(angRad) * inPoint.x - std::sin(angRad) * inPoint.y; outPoint.y = std::sin(angRad) * inPoint.x + std::cos(angRad) * inPoint.y; return outPoint; } static cv::Point2f rotatePoint(const cv::Point2f inPoint, const cv::Point2f center, const double angRad) { return rotate2d(inPoint - center, angRad) + center; }
這個反應了一些問題，首先，linemod現在的結果似憾訓比較靠譜，因此，這種直接旋轉特征的方法是可行的，其次，這個代碼也給我們提供了特征旋轉的計算公式，主要到那些sin cos了吧，就是那些公式，注意，這里的旋轉獲得不僅僅是旋轉后特征的坐標位置（可能需要取整），而且特征的本質屬性（對于linemod，是量化到0和8之間的角度值，對于我們標準的基于梯度的計算式，則是歸一化后的X和Y方向的梯度值）也同步予以獲取，
我們對這個做適當的擴展，
第一，我們看到linemod的代碼里這種旋轉前后的特征數量是沒有改變的，也就是說，如果0度模版圖有1000個特征，旋轉后的其他角度也會有1000個特征，這里其實有個隱藏的問題，因為一般而言，這些特征在0角度時很多的坐標是連續的，當旋轉取整后，一定概率上存在取整后的兩個坐標是相同的，但是可能僅僅是坐標相同，量化角度和歸一化的X和Y方向梯度確不一樣，這是個矛盾的東西，一個固定的位置只能有一個特征，因此，遇到這種情況，可能就要進行一定的取舍，在linemod的代碼里沒有見到這樣的內容和處理方案，我的做法時全部旋轉后，按照坐標進行一次去重的操作，至于重復的留下哪一個，那就看誰排在前面了，
第二、我們知道0度的時候的特征是有亞像素這個講法的，也就是說0度特征的坐標位置可以是亞像素的，所以我們用0度亞像素的位置作為旋轉的基礎，這樣可能帶來的旋轉特征更為準確，這就為自己實作類似于create_shape_model_xld這樣的介面提供了可能性，
第三、這個旋轉的方案是不帶縮放的，為了支持縮放，可以在這個基礎上加上X和Y方向的縮放因子，當X和Y方向的縮放因子相同時，就是多尺度匹配，當X和Y方向不相同時，即為各項異性匹配，
第四、還有個問題值得探討，就是所有金字塔層、所有角度的特征是都由最底層0角度的模版的特征經過縮放旋轉生成呢，還是由每層金字塔的0角度特征旋轉生成， 個人覺得，還是由每層金字塔的0角度特征旋轉生成更為合理， 畢竟這個特征比用基層的特征旋轉縮放少了一個縮放，準確度及精度上應該更為靠譜，
第五、上述方案帶來的最大好處時，我們不需要旋轉模版圖，再求這些特征了，因此，速度提升會非常明顯，而且本身旋轉這些特征的耗時基本可以忽略不計，甚至都可以實時計算，
第六、注意到上面的cropTemplates函式，其具體的代碼如下：
static Rect cropTemplates(std::vector<Template>& templates) { int min_x = std::numeric_limits<int>::max(); int min_y = std::numeric_limits<int>::max(); int max_x = std::numeric_limits<int>::min(); int max_y = std::numeric_limits<int>::min(); // First pass: find min/max feature x,y over all pyramid levels and modalities // 這里的templates.size()其實就等于金字塔的層數 for (int i = 0; i < (int)templates.size(); ++i) { Template& templ = templates[i]; for (int j = 0; j < (int)templ.features.size(); ++j) { // 在原始模板影像上對應的位置 int x = templ.features[j].x << templ.pyramid_level; int y = templ.features[j].y << templ.pyramid_level; min_x = std::min(min_x, x); min_y = std::min(min_y, y); max_x = std::max(max_x, x); max_y = std::max(max_y, y); } } // 以上代碼得到了所有模板特征點在原圖中的最大和最小位置 if (min_x % 2 == 1) --min_x; if (min_y % 2 == 1) --min_y; // 校正下位置 // Second pass: set width/height and shift all feature positions for (int i = 0; i < (int)templates.size(); ++i) { Template& templ = templates[i]; templ.width = (max_x - min_x) >> templ.pyramid_level; templ.height = (max_y - min_y) >> templ.pyramid_level; templ.tl_x = min_x >> templ.pyramid_level; templ.tl_y = min_y >> templ.pyramid_level; for (int j = 0; j < (int)templ.features.size(); ++j) { templ.features[j].x -= templ.tl_x; templ.features[j].y -= templ.tl_y; } } return Rect(min_x, min_y, max_x - min_x, max_y - min_y); }
這個的作用就是找到當前所有的特征的最小外接矩形，這個東西其實是個很好的屬性，他有個潛在的作用就是可以增加某些特性目標的識別，因為他縮小了旋轉后的特征的尺度，相當于變相的增加了識別結果的尺度，所以如果某個模版其有效特征（邊緣）在高度或寬度某個方向完全缺失，則即使這個目標在被識別影像的邊緣處，也有可能予以識別，比如下面這些目標：
如右圖兩處藍色箭頭所示，這兩處目標實際上是有一部磁區域位于了原圖之外，但是確實可以識別到，就是因為在模版圖的特征提取中，邊緣那些純色的部分不含有有效邊緣，在處理時把這部分的區域就去除了，給了這些位于邊緣之外的目標可被找到的概率， 但是如果是用NCC，則無論如何也是找不到這兩個目標的（或者有明顯的偏移），
這個東西有一個細節需要注意，就是在實作時，由于特征的位置進行了一定的裁剪，所以從金字塔的頂層向下定位的程序中，不能簡單的把坐標值乘以2，而必須考慮相關的偏移，這些偏移的資料也應該在創建模型的程序中予以記錄，這些編程的技巧也是相當麻煩的程序，
三、多尺度和各項異性匹配中縮放步長的自動確認
前面稍微提及了多尺度和各項異性的匹配，和標準的形狀匹配相比，他們實質上是沒有太多的變化的，而其中一個非常重要的地方就是縮放步長的自動計算，因為縮放步長設計的不合理，必然會丟失一些重要的節點資料，導致組中的目標無法準確識別，這個東西我們也是借用了halcon一篇專利里的演算法，其大概意思如下圖所示：
他首先計算所有特征點的X和Y方向的重心（X和Y方向坐標相加求平均值），然后再計算每個特征點和這個重心的距離（絕對值），取最大值的倒數作為縮放步長，這也是非常合理的一個程序，最大的距離表面可以考慮到每一個離散的狀態，
我實際測驗，一般來說用這個自動計算出的縮放步長是較為合理的，稍微手動修改就存在找不到的現象，而halcon的縮放步長的功能要強大很多，
四、自動對比度的確認
在早期的文章中，我有提到自動對比度可以使用模版圖的OSTU二值化閾值法得到，但是實際測驗時發現很多影像這樣的得到的對比度值非常不合適，會造成目標的丟失，后續有朋友提出應該用模版圖的Canny算子的程序中，經過非極大值抑制后的梯度影像，利用Otsu演算法算出一個閾值，將其作為一個高閾值TH，高閾值的一半作為低閾值TL，實際證明，這個方式是非常有效的，
五、Halcon里的計算相似度的公式和linemod計算式的關系
實際上，linemod里用到的夾角余弦的計算公式和halcon利用的梯度算式的實質是一樣的，借用一個網友的貼圖：
夾角余弦：
邊緣梯度：
只不過在linemod里，把夾角余弦有離散化到0和7之間了，
六、邊緣梯度的計算式里分母的開方和除法是不需要的
當我們都做歸一化處理時，我們發現邊緣梯度的相似度計算其實根本不需要計算分母里的開平方以及整個除法，只需要分子力的兩個乘法和一個加法，這個對計算量來說有很大的提升的，
七、最頂層候選點的選擇策略
這個是個很重要的程序，他不僅影響到了演算法的速度，而且對結果的準確性也會有直接的關聯，早期我是算出每個位置的可能角度的的分支，然后取最大值留下，得到了一副 各位置的綜合得分圖，然后利用一些區域最大值以及早期說的 滿水填充等奇技淫巧（現在看來都是歪門邪道）來得到頂層的候選點，這個在后續的測驗中發現會丟失目標，
一個可靠的選擇方式是候選點必須滿足下面2個特征：
1、 他必須大于最小得分（不同層的最小得分需要適當調整，越往金字塔頂端得分需越小），這可以去掉大部分點，
2、他必須是個區域最大得分點（可以是3*3或者5*5），
在網路上搜索這方面的資料時，有發現有篇類似的博客有提及到這個演算法：基于形狀的模板匹配之候選點選擇 ，我感覺沒有講到核心，大家也可以參考下，
注意，關于maxoverlap的選項，不建議用在候選點的篩選上，甚至在除了底層外，其他層也不應該用該選項來篩選，
八、最小組件尺寸選項
其實在Halcon的匹配里還隱藏了這個選項，在Contrast 選項里，我們綜合比較認為他應該就是一個最小連續邊緣的意思，如果某個連續的邊緣的個數小于這個尺寸，則不把他作為特征設計，予以剔除，這個選項有兩個作用，一個是可以減少一些較小特征或者說是噪音的影響，二是可以提高匹配的速度，如下圖所示：
不考慮最小組件尺寸 最小組件尺寸為100
當最小組件尺寸為100時，得到的特征就更為簡潔，同時，周邊一些不重要的特征予以剔除，
總結： 看似一個簡單的演算法，要做到極致和完美真的還是不容易，那怕是現在這個樣子，離我們傳說中的perferct還是以后很大的距離的，有的時候由不得不佩服那些創新的大神們，
針對夾角余弦以及正統的梯度邊緣，我分別實作兩個不同版本的基于邊緣的形狀匹配演算法，兩者似乎也沒有太大的性能區別，有興趣額的朋友可以試下下面的鏈接：
1、基于梯度邊緣的形狀匹配，
2、基于夾角余弦的形狀匹配（16角度）
如果想時刻關注本人的最新文章，也可關注公眾號或者添加本人微信： laviewpbt
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555597.html
標籤：其他
下一篇：返回列表