｜期刊分享｜機器視覺｜二進制關鍵點描述子評估

相機數碼相機英語機器學習與人工智能 2017-06-16

編者序：在計算機視覺相關應用中，經常會遇到特徵選擇與匹配問題。到底哪種特徵好呢，目前尚缺乏數學理論分析，仁者見仁智者見智。本週將連續推送三篇特徵比較的經典論文，供讀者參考。本文測試表明，性能排名依次為：BRISK、FREAK、ORB和BRIEF，但BRISK比其它描述子運算量高。

推薦指數 ☆☆☆☆☆

一、引言

越來越多的移動應用是基於圖像配準和識別的，如增強現實（Augmented Reality）等，導致出現了非常多的新型圖像配準技術。一種通用的圖像配準方法是利用明顯點，也就是關鍵點或特徵點，這些特徵點通常具有某種變換不變性。然後將這些描述子與數據庫中圖像中提取的描述子進行比較厚找出與之匹配的圖像。存在精確可靠的關鍵點檢測器和近似描述子是至關重要的一步，本文聚焦於評估特徵描述子性能。

SIFT是一種最廣為人知的關鍵點描述子，通過高斯差分DoG檢測關鍵點。儘管，SIFT提出已經好多年了，但仍可以與state-of-the-art方法相匹敵。後來提出了一些改進的類似SIFT的描述子，如ASIFT、PCA-SIFT等。SURF是最流行的改進，匹配性能與SIFT差不多，但計算更快。然而，SIFT-like類描述子的處理時間仍然太長，尤其是在計算能力和存儲容量受限的移動設備上的實時應用。

二進制關鍵點描述子旨在彌補這個隔閡，性能與SIFT-like描述子類似，但運算成本明顯降低。二進制描述子背後思想是：描述子中的每一位都是獨立的，相似度測量時可用Hamming距離替代Euclidean距離（The idea behind binary descriptors is that each bit in the descriptor is independent and the Hamming distance can be used as similarity measure instead of, e.g., the Euclidean distance）。最近4個最優前途的二進制特徵描述子是BRIEF（Binary Robust Independent Elementary Feature）、ORB（Oriented Fast and Rotated BRIEF）、BRISK（Binary Robust Invariant Scalable Keypoints）和FREAK（Fast Retina Keypoint）。

Mikolajczyk和Schmid在Oxford數據集上比較了特徵描述子的性能，提出了使用召回率（recall）和精確率（precision）作為衡量不同類型描述子性能的指標，但是並沒有比較二進制描述子。他們總結出：描述子的排名與特徵點檢測器很大程度上相互獨立，並且SIFT-like描述子性能最好（ the ranking of descriptors is mostly independent of the feature point detector and that SIFT-like descriptors yield best performance.）。最近，Heinly等人評估了二進制描述子BRIEF、ORB、BRISK和SURF、SIFT，仍採用Oxford數據集並分析不同檢測器和描述子組合的性能，主要結論有：（a）、描述子應與數據中呈現的轉換相適應（descriptors should be adapted to the transformations present in the data）；（b）、檢測器和描述子都應具有某些轉換不變性（both detector and descriptor should be invariant to the same set of transforms）；（c）、二進制描述子以匹配性能降低為代價獲得了加速（speed gains achieved by binary descriptors result (at worse) in marginal matching performance penalties）。他們引入了新的測量指標：熵（entropy）和候選測量頻率（a measure for the frequency of candidate measures）。然而，這些測量並沒有影響最終結論。Chandrasekhar等人給出了Stanford Mobile Visual Search（SMVS） data set。該數據集克服了一些其它數據集沒有ground truth等缺點。本文增加了FREAK描述子的評測，且使用的數據集是Chandrasekhar等人的。

二、數據集

算法評估有兩個數據集：Oxford數據集和SMVS數據集。Oxford數據集包括8種不同場景，每種場景包括一個以下挑戰：光照、視角、旋轉和尺度、JPEG壓縮或退化。數據集提供了每個場景的ground truth。然而現實中的場景更復雜。SMVS數據集包括很大範圍的圖片，8個種類的1200子類的3300張圖片。圖片使用若干不同類型的手機相機和數碼相機採集，並且包括室內和戶外不同光照不同背景下的圖片。SMVS缺點是針對移動研究產生的，ground truth是參考圖像，沒有變換後的ground truth。為了評估時不適用t transformation ground truth，本文進行了不同的測試。

本文實驗主要用SMVS數據集，並用Oxford數據集中的Bark子數據集作為尺度變化下的對比。

三、評估

本文評估4種二進制描述子：BRIEF、ORB、BRISK和FREAK，此外SIFT被用於參考描述子。BRIEF、BRISK和FREAK使用的是SURF檢測器，ORB描述子使用的是ORB檢測器。Heinly等人的評估表明ORB/ORB組合在大多數情況下由於SURF/ORB組合。此外，SURF關鍵點的旋轉和尺度不變性也滿足具有同樣特性的BRISK和FREAK描述子的需要。BRIEF的作者也是在SURF關鍵點上計算描述子，堅定了我們對關鍵點檢測器的選擇。

評估的第一步是在參考（reference）和查詢（query）圖像上檢測關鍵點，我們限定關鍵點的最大數量為500，然後計算上述關鍵點/描述子組合。特徵匹配採用brute-force匹配方法，每個關鍵點的最佳匹配點通過它們描述子的距離確定。如果第一最佳匹配測量距離非常小，並且第二最佳匹配很大，那麼第一最佳匹配點無疑是最好的選擇。如果第一和第二最佳匹配相差較小，出現錯誤的概率會很大，此時這兩個匹配點都拒絕。這種測試叫做Ratio Test，通過第一第二最佳匹配點之間的距離與指定門限間的關係確定。如果門限取0.8，可以消除90%的錯誤匹配而僅僅丟棄不到5%的正確匹配。

評估的下一步是一致隨機採樣（RANdom SAmple Consensus，RANSAC）。當兩個相機觀測到相同的場景，它們會看在不同視角看到相同元素。該方法允許利用兩視角間的極線約束（epipolar constraint）使得特徵匹配更可靠。原理很簡單：關鍵點匹配時，只接受落在相應極線上的匹配。然而，為了檢測該條件，需要知道基礎矩陣（fundamental matrix），或者正確的匹配需要顧及基礎矩陣。由於SMVS數據集沒有提供轉換的ground truth，因此需要聯合計算基礎矩陣的好的匹配（good matches）集合，這些集合被認為是正確的匹配。

評估的最後一步是計算精確率和召回率。

四評估結果和討論

性能評估指標有四個：關鍵點平均數、精確率、召回率和最佳匹配平均數，參考圖像上大概檢測到500個關鍵點，如果多於500個則只取前500個。下圖給出了二進制描述子在不同子數據集上的平均點數，從中可以看出，ORB和SIFT生成了400~500個關鍵點，其它描述子得到的特徵點明顯少些。

｜期刊分享｜機器視覺｜二進制關鍵點描述子評估